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 | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
e058f509374e98e48eafeba2f1dadff9 |
User & Date: | drh 2008-11-19 18:30:29 |
Context
2008-11-19
| ||
18:30 | In bitvec.c: removed some of the recursion, minor optimizations, added comments, improved consistency. (CVS 5929) check-in: 54d714fb user: shane tags: trunk | |
18:30 | Update the SECURE_DELETE code to track the latest changes in the pager. (CVS 5928) check-in: e058f509 user: drh tags: trunk | |
16:52 | Fix some compiler warnings that show up when building the amalgamation only. (CVS 5927) check-in: d1abe8a1 user: danielk1977 tags: trunk | |
Changes
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 .. 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 ... 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 ... 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 |
** 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. ** ................................................................................ ** 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, ................................................................................ ** 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; } ................................................................................ ** 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. |
| > > | > > > > > > > | > > > | > > | > > > > > > > > < | | > | > > > | < | < < | | | | > > > > > > | | < | < < < | | | | > > > > | > > > | > > > > > > > > > | < < > > > > > | > > | < | | | | | | | | | > > | | > > > > > > | |
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 .. 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 ... 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 ... 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 |
** 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. ** ................................................................................ ** 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, ................................................................................ ** 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; } ................................................................................ ** 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
....
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
|
** 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 */ ................................................................................ || 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. |
|
>
|
|
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
....
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
|
** 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 */ ................................................................................ || 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.
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
181
182
183
184
185
186
187
188
189
190
191
|
# 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. ................................................................................ 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 |
|
<
<
<
<
|
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
181
182
183
184
185
186
187
|
# 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. ................................................................................ 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 |