SQLite

Check-in [e058f50937]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Update the SECURE_DELETE code to track the latest changes in the pager. (CVS 5928)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e058f509374e98e48eafeba2f1dadff9633d1190
User & Date: drh 2008-11-19 18:30:29.000
Context
2008-11-19
18:30
In bitvec.c: removed some of the recursion, minor optimizations, added comments, improved consistency. (CVS 5929) (check-in: 54d714fba6 user: shane tags: trunk)
18:30
Update the SECURE_DELETE code to track the latest changes in the pager. (CVS 5928) (check-in: e058f50937 user: drh tags: trunk)
16:52
Fix some compiler warnings that show up when building the amalgamation only. (CVS 5927) (check-in: d1abe8a1c9 user: danielk1977 tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/bitvec.c.
30
31
32
33
34
35
36
37
38
39
40

41

42
43
44







45



46


47


48






49
50
51
52
53
54
55
56
57
58
** Clear operations are exceedingly rare.  There are usually between
** 5 and 500 set operations per Bitvec object, though the number of sets can
** sometimes grow into tens of thousands or larger.  The size of the
** Bitvec object is the number of pages in the database file at the
** start of a transaction, and is thus usually less than a few thousand,
** but can be as large as 2 billion for a really big database.
**
** @(#) $Id: bitvec.c,v 1.8 2008/11/11 15:48:48 drh Exp $
*/
#include "sqliteInt.h"


#define BITVEC_SZ        512

/* Round the union size down to the nearest pointer boundary, since that's how 
** it will be aligned within the Bitvec struct. */
#define BITVEC_USIZE     (((BITVEC_SZ-12)/sizeof(Bitvec*))*sizeof(Bitvec*))







#define BITVEC_NCHAR     BITVEC_USIZE



#define BITVEC_NBIT      (BITVEC_NCHAR*8)


#define BITVEC_NINT      (BITVEC_USIZE/4)


#define BITVEC_MXHASH    (BITVEC_NINT/2)






#define BITVEC_NPTR      (BITVEC_USIZE/sizeof(Bitvec *))

#define BITVEC_HASH(X)   (((X)*37)%BITVEC_NINT)

/*
** A bitmap is an instance of the following structure.
**
** This bitmap records the existance of zero or more bits
** with values between 1 and iSize, inclusive.
**







|



>

>


|
>
>
>
>
>
>
>
|
>
>
>
|
>
>
|
>
>

>
>
>
>
>
>


<







30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

73
74
75
76
77
78
79
** Clear operations are exceedingly rare.  There are usually between
** 5 and 500 set operations per Bitvec object, though the number of sets can
** sometimes grow into tens of thousands or larger.  The size of the
** Bitvec object is the number of pages in the database file at the
** start of a transaction, and is thus usually less than a few thousand,
** but can be as large as 2 billion for a really big database.
**
** @(#) $Id: bitvec.c,v 1.9 2008/11/19 18:30:35 shane Exp $
*/
#include "sqliteInt.h"

/* Size of the Bitvec structure in bytes. */
#define BITVEC_SZ        512

/* Round the union size down to the nearest pointer boundary, since that's how 
** it will be aligned within the Bitvec struct. */
#define BITVEC_USIZE     (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*))

/* Type of the array "element" for the bitmap representation. 
** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE. 
** Setting this to the "natural word" size of your CPU may improve
** performance. */
#define BITVEC_TELEM     u8
/* Size, in bits, of the bitmap element. */
#define BITVEC_SZELEM    8
/* Number of elements in a bitmap array. */
#define BITVEC_NELEM     (BITVEC_USIZE/sizeof(BITVEC_TELEM))
/* Number of bits in the bitmap array. */
#define BITVEC_NBIT      (BITVEC_NELEM*BITVEC_SZELEM)

/* Number of u32 values in hash table. */
#define BITVEC_NINT      (BITVEC_USIZE/sizeof(u32))
/* Maximum number of entries in hash table before 
** sub-dividing and re-hashing. */
#define BITVEC_MXHASH    (BITVEC_NINT/2)
/* Hashing function for the aHash representation.
** Empirical testing showed that the *37 multiplier 
** (an arbitrary prime)in the hash function provided 
** no fewer collisions than the no-op *1. */
#define BITVEC_HASH(X)   (((X)*1)%BITVEC_NINT)

#define BITVEC_NPTR      (BITVEC_USIZE/sizeof(Bitvec *))



/*
** A bitmap is an instance of the following structure.
**
** This bitmap records the existance of zero or more bits
** with values between 1 and iSize, inclusive.
**
68
69
70
71
72
73
74
75
76

77



78
79
80
81
82
83
84
85
86
** handles up to iDivisor separate values of i.  apSub[0] holds
** values between 1 and iDivisor.  apSub[1] holds values between
** iDivisor+1 and 2*iDivisor.  apSub[N] holds values between
** N*iDivisor+1 and (N+1)*iDivisor.  Each subbitmap is normalized
** to hold deal with values between 1 and iDivisor.
*/
struct Bitvec {
  u32 iSize;      /* Maximum bit index */
  u32 nSet;       /* Number of bits that are set */

  u32 iDivisor;   /* Number of bits handled by each apSub[] entry */



  union {
    u8 aBitmap[BITVEC_NCHAR];    /* Bitmap representation */
    u32 aHash[BITVEC_NINT];      /* Hash table representation */
    Bitvec *apSub[BITVEC_NPTR];  /* Recursive representation */
  } u;
};

/*
** Create a new bitmap object able to handle bits between 0 and iSize,







|
|
>
|
>
>
>

|







89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
** handles up to iDivisor separate values of i.  apSub[0] holds
** values between 1 and iDivisor.  apSub[1] holds values between
** iDivisor+1 and 2*iDivisor.  apSub[N] holds values between
** N*iDivisor+1 and (N+1)*iDivisor.  Each subbitmap is normalized
** to hold deal with values between 1 and iDivisor.
*/
struct Bitvec {
  u32 iSize;      /* Maximum bit index.  Max iSize is 4,294,967,296. */
  u32 nSet;       /* Number of bits that are set - only valid for aHash element */
                  /* Max nSet is BITVEC_NINT.  For BITVEC_SZ of 512, this would be 125. */
  u32 iDivisor;   /* Number of bits handled by each apSub[] entry. */
                  /* Should >=0 for apSub element. */
                  /* Max iDivisor is max(u32) / BITVEC_NPTR + 1.  */
                  /* For a BITVEC_SZ of 512, this would be 34,359,739. */
  union {
    BITVEC_TELEM aBitmap[BITVEC_NELEM];    /* Bitmap representation */
    u32 aHash[BITVEC_NINT];      /* Hash table representation */
    Bitvec *apSub[BITVEC_NPTR];  /* Recursive representation */
  } u;
};

/*
** Create a new bitmap object able to handle bits between 0 and iSize,
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115






116
117
118
119
120
121
122
123
124
** Check to see if the i-th bit is set.  Return true or false.
** If p is NULL (if the bitmap has not been created) or if
** i is out of range, then return false.
*/
int sqlite3BitvecTest(Bitvec *p, u32 i){
  if( p==0 ) return 0;
  if( i>p->iSize || i==0 ) return 0;
  if( p->iSize<=BITVEC_NBIT ){
    i--;
    return (p->u.aBitmap[i/8] & (1<<(i&7)))!=0;
  }
  if( p->iDivisor>0 ){
    u32 bin = (i-1)/p->iDivisor;
    i = (i-1)%p->iDivisor + 1;
    return sqlite3BitvecTest(p->u.apSub[bin], i);






  }else{
    u32 h = BITVEC_HASH(i);
    while( p->u.aHash[h] ){
      if( p->u.aHash[h]==i ) return 1;
      h++;
      if( h>=BITVEC_NINT ) h = 0;
    }
    return 0;
  }







<
|
<
<
|
|
|
|
>
>
>
>
>
>
|
|







126
127
128
129
130
131
132

133


134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
** Check to see if the i-th bit is set.  Return true or false.
** If p is NULL (if the bitmap has not been created) or if
** i is out of range, then return false.
*/
int sqlite3BitvecTest(Bitvec *p, u32 i){
  if( p==0 ) return 0;
  if( i>p->iSize || i==0 ) return 0;

  i--;


  while( p->iDivisor ){
    u32 bin = i/p->iDivisor;
    i = i%p->iDivisor;
    p = p->u.apSub[bin];
    if (!p) {
      return 0;
    }
  }
  if( p->iSize<=BITVEC_NBIT ){
    return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0;
  } else{
    u32 h = BITVEC_HASH(i++);
    while( p->u.aHash[h] ){
      if( p->u.aHash[h]==i ) return 1;
      h++;
      if( h>=BITVEC_NINT ) h = 0;
    }
    return 0;
  }
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159




160



161









162
163
164
165
166




167
168
169
170
171
172
173
174
175
176
177
178
179


180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198


199



200
201
202
203
204
205
206
207






208
209
210
211
212
213
214
215
** Otherwise the behavior is undefined.
*/
int sqlite3BitvecSet(Bitvec *p, u32 i){
  u32 h;
  assert( p!=0 );
  assert( i>0 );
  assert( i<=p->iSize );
  if( p->iSize<=BITVEC_NBIT ){
    i--;
    p->u.aBitmap[i/8] |= 1 << (i&7);
    return SQLITE_OK;
  }
  if( p->iDivisor ){
    u32 bin = (i-1)/p->iDivisor;
    i = (i-1)%p->iDivisor + 1;
    if( p->u.apSub[bin]==0 ){
      sqlite3BeginBenignMalloc();
      p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );
      sqlite3EndBenignMalloc();
      if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM;
    }
    return sqlite3BitvecSet(p->u.apSub[bin], i);
  }




  h = BITVEC_HASH(i);



  while( p->u.aHash[h] ){









    if( p->u.aHash[h]==i ) return SQLITE_OK;
    h++;
    if( h==BITVEC_NINT ) h = 0;
  }
  p->nSet++;




  if( p->nSet>=BITVEC_MXHASH ){
    unsigned int j;
    int rc;
    u32 aiValues[BITVEC_NINT];
    memcpy(aiValues, p->u.aHash, sizeof(aiValues));
    memset(p->u.apSub, 0, sizeof(p->u.apSub[0])*BITVEC_NPTR);
    p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;
    rc = sqlite3BitvecSet(p, i);
    for(j=0; j<BITVEC_NINT; j++){
      if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);
    }
    return rc;
  }


  p->u.aHash[h] = i;
  return SQLITE_OK;
}

/*
** Clear the i-th bit.  Return 0 on success and an error code if
** anything goes wrong.
*/
void sqlite3BitvecClear(Bitvec *p, u32 i){
  assert( p!=0 );
  assert( i>0 );
  if( p->iSize<=BITVEC_NBIT ){
    i--;
    p->u.aBitmap[i/8] &= ~(1 << (i&7));
  }else if( p->iDivisor ){
    u32 bin = (i-1)/p->iDivisor;
    i = (i-1)%p->iDivisor + 1;
    if( p->u.apSub[bin] ){
      sqlite3BitvecClear(p->u.apSub[bin], i);


    }



  }else{
    unsigned int j;
    u32 aiValues[BITVEC_NINT];
    memcpy(aiValues, p->u.aHash, sizeof(aiValues));
    memset(p->u.aHash, 0, sizeof(p->u.aHash[0])*BITVEC_NINT);
    p->nSet = 0;
    for(j=0; j<BITVEC_NINT; j++){
      if( aiValues[j] && aiValues[j]!=i ){






        sqlite3BitvecSet(p, aiValues[j]);
      }
    }
  }
}

/*
** Destroy a bitmap object.  Reclaim all memory used.







<
|
<
<
<
|
|
|






|

>
>
>
>
|
>
>
>
|
>
>
>
>
>
>
>
>
>


|
<
|
>
>
>
>





|







>
>





|
<




<
|
<
|
|
|
|
<
>
>

>
>
>




|


|
>
>
>
>
>
>
|







165
166
167
168
169
170
171

172



173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

231
232
233
234

235

236
237
238
239

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
** Otherwise the behavior is undefined.
*/
int sqlite3BitvecSet(Bitvec *p, u32 i){
  u32 h;
  assert( p!=0 );
  assert( i>0 );
  assert( i<=p->iSize );

  i--;



  while((p->iSize > BITVEC_NBIT) && p->iDivisor) {
    u32 bin = i/p->iDivisor;
    i = i%p->iDivisor;
    if( p->u.apSub[bin]==0 ){
      sqlite3BeginBenignMalloc();
      p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );
      sqlite3EndBenignMalloc();
      if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM;
    }
    p = p->u.apSub[bin];
  }
  if( p->iSize<=BITVEC_NBIT ){
    p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1));
    return SQLITE_OK;
  }
  h = BITVEC_HASH(i++);
  /* if there wasn't a hash collision, and this doesn't */
  /* completely fill the hash, then just add it without */
  /* worring about sub-dividing and re-hashing. */
  if( !p->u.aHash[h] ){
    if (p->nSet<(BITVEC_NINT-1)) {
      goto bitvec_set_end;
    } else {
      goto bitvec_set_rehash;
    }
  }
  /* there was a collision, check to see if it's already */
  /* in hash, if not, try to find a spot for it */
  do {
    if( p->u.aHash[h]==i ) return SQLITE_OK;
    h++;
    if( h>=BITVEC_NINT ) h = 0;

  } while( p->u.aHash[h] );
  /* we didn't find it in the hash.  h points to the first */
  /* available free spot. check to see if this is going to */
  /* make our hash too "full".  */
bitvec_set_rehash:
  if( p->nSet>=BITVEC_MXHASH ){
    unsigned int j;
    int rc;
    u32 aiValues[BITVEC_NINT];
    memcpy(aiValues, p->u.aHash, sizeof(aiValues));
    memset(p->u.apSub, 0, sizeof(aiValues));
    p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;
    rc = sqlite3BitvecSet(p, i);
    for(j=0; j<BITVEC_NINT; j++){
      if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);
    }
    return rc;
  }
bitvec_set_end:
  p->nSet++;
  p->u.aHash[h] = i;
  return SQLITE_OK;
}

/*
** Clear the i-th bit.

*/
void sqlite3BitvecClear(Bitvec *p, u32 i){
  assert( p!=0 );
  assert( i>0 );

  i--;

  while( p->iDivisor ){
    u32 bin = i/p->iDivisor;
    i = i%p->iDivisor;
    p = p->u.apSub[bin];

    if (!p) {
      return;
    }
  }
  if( p->iSize<=BITVEC_NBIT ){
    p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1)));
  }else{
    unsigned int j;
    u32 aiValues[BITVEC_NINT];
    memcpy(aiValues, p->u.aHash, sizeof(aiValues));
    memset(p->u.aHash, 0, sizeof(aiValues));
    p->nSet = 0;
    for(j=0; j<BITVEC_NINT; j++){
      if( aiValues[j] && aiValues[j]!=(i+1) ){
        u32 h = BITVEC_HASH(aiValues[j]-1);
        p->nSet++;
        while( p->u.aHash[h] ){
          h++;
          if( h>=BITVEC_NINT ) h = 0;
        }
        p->u.aHash[h] = aiValues[j];
      }
    }
  }
}

/*
** Destroy a bitmap object.  Reclaim all memory used.
Changes to src/pager.c.
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.505 2008/11/19 10:22:33 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"

/*
** Macros for troubleshooting.  Normally turned off
*/







|







14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.506 2008/11/19 18:30:29 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"

/*
** Macros for troubleshooting.  Normally turned off
*/
3484
3485
3486
3487
3488
3489
3490

3491
3492
3493
3494
3495
3496
3497
3498
   || sqlite3BitvecTest(pPager->pAlwaysRollback, pPg->pgno)
   || pPg->pgno>pPager->origDbSize
  ){
    return;
  }

#ifdef SQLITE_SECURE_DELETE

  if( (pPg->flags & PGHDR_IN_JOURNAL)!=0 || pPg->pgno>pPager->origDbSize ){
    return;
  }
#endif

  /* If SECURE_DELETE is disabled, then there is no way that this
  ** routine can be called on a page for which sqlite3PagerDontWrite()
  ** has not been previously called during the same transaction.







>
|







3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
   || sqlite3BitvecTest(pPager->pAlwaysRollback, pPg->pgno)
   || pPg->pgno>pPager->origDbSize
  ){
    return;
  }

#ifdef SQLITE_SECURE_DELETE
  if( sqlite3BitvecTest(pPager->pInJournal, pPg->pgno)!=0
   || pPg->pgno>pPager->origDbSize ){
    return;
  }
#endif

  /* If SECURE_DELETE is disabled, then there is no way that this
  ** routine can be called on a page for which sqlite3PagerDontWrite()
  ** has not been previously called during the same transaction.
Changes to test/bitvec.test.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2008 February 18
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# Unit testing of the Bitvec object.
#
# $Id: bitvec.test,v 1.2 2008/03/21 16:45:48 drh Exp $
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# The built-in test logic must be operational in order for
# this test to work.













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2008 February 18
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# Unit testing of the Bitvec object.
#
# $Id: bitvec.test,v 1.3 2008/11/19 18:30:35 shane Exp $
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# The built-in test logic must be operational in order for
# this test to work.
181
182
183
184
185
186
187
188
189
190
191
set go 1
for {set n 1} {$go} {incr n} {
  bitvec_malloc_test bitvec-3.3.$n $n 50000 {1 50000 1 1 0}
}

finish_test
return



finish_test







<
<
<
<
181
182
183
184
185
186
187




set go 1
for {set n 1} {$go} {incr n} {
  bitvec_malloc_test bitvec-3.3.$n $n 50000 {1 50000 1 1 0}
}

finish_test
return