1 /* 2 ** 2008 February 16 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** This file implements an object that represents a fixed-length 13 ** bitmap. Bits are numbered starting with 1. 14 ** 15 ** A bitmap is used to record what pages a database file have been 16 ** journalled during a transaction. Usually only a few pages are 17 ** journalled. So the bitmap is usually sparse and has low cardinality. 18 ** But sometimes (for example when during a DROP of a large table) most 19 ** or all of the pages get journalled. In those cases, the bitmap becomes 20 ** dense. The algorithm needs to handle both cases well. 21 ** 22 ** The size of the bitmap is fixed when the object is created. 23 ** 24 ** All bits are clear when the bitmap is created. Individual bits 25 ** may be set or cleared one at a time. 26 ** 27 ** Test operations are about 100 times more common that set operations. 28 ** Clear operations are exceedingly rare. There are usually between 29 ** 5 and 500 set operations per Bitvec object, though the number of sets can 30 ** sometimes grow into tens of thousands or larger. The size of the 31 ** Bitvec object is the number of pages in the database file at the 32 ** start of a transaction, and is thus usually less than a few thousand, 33 ** but can be as large as 2 billion for a really big database. 34 ** 35 ** @(#) $Id: bitvec.c,v 1.3 2008/03/21 16:45:47 drh Exp $ 36 */ 37 #include "sqliteInt.h" 38 39 #define BITVEC_SZ 512 40 /* Round the union size down to the nearest pointer boundary, since that's how 41 ** it will be aligned within the Bitvec struct. */ 42 #define BITVEC_USIZE (((BITVEC_SZ-12)/sizeof(Bitvec*))*sizeof(Bitvec*)) 43 #define BITVEC_NCHAR BITVEC_USIZE 44 #define BITVEC_NBIT (BITVEC_NCHAR*8) 45 #define BITVEC_NINT (BITVEC_USIZE/4) 46 #define BITVEC_MXHASH (BITVEC_NINT/2) 47 #define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *)) 48 49 #define BITVEC_HASH(X) (((X)*37)%BITVEC_NINT) 50 51 /* 52 ** A bitmap is an instance of the following structure. 53 ** 54 ** This bitmap records the existance of zero or more bits 55 ** with values between 1 and iSize, inclusive. 56 ** 57 ** There are three possible representations of the bitmap. 58 ** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight 59 ** bitmap. The least significant bit is bit 1. 60 ** 61 ** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is 62 ** a hash table that will hold up to BITVEC_MXHASH distinct values. 63 ** 64 ** Otherwise, the value i is redirected into one of BITVEC_NPTR 65 ** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap 66 ** handles up to iDivisor separate values of i. apSub[0] holds 67 ** values between 1 and iDivisor. apSub[1] holds values between 68 ** iDivisor+1 and 2*iDivisor. apSub[N] holds values between 69 ** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized 70 ** to hold deal with values between 1 and iDivisor. 71 */ 72 struct Bitvec { 73 u32 iSize; /* Maximum bit index */ 74 u32 nSet; /* Number of bits that are set */ 75 u32 iDivisor; /* Number of bits handled by each apSub[] entry */ 76 union { 77 u8 aBitmap[BITVEC_NCHAR]; /* Bitmap representation */ 78 u32 aHash[BITVEC_NINT]; /* Hash table representation */ 79 Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */ 80 } u; 81 }; 82 83 /* 84 ** Create a new bitmap object able to handle bits between 0 and iSize, 85 ** inclusive. Return a pointer to the new object. Return NULL if 86 ** malloc fails. 87 */ 88 Bitvec *sqlite3BitvecCreate(u32 iSize){ 89 Bitvec *p; 90 assert( sizeof(*p)==BITVEC_SZ ); 91 p = sqlite3MallocZero( sizeof(*p) ); 92 if( p ){ 93 p->iSize = iSize; 94 } 95 return p; 96 } 97 98 /* 99 ** Check to see if the i-th bit is set. Return true or false. 100 ** If p is NULL (if the bitmap has not been created) or if 101 ** i is out of range, then return false. 102 */ 103 int sqlite3BitvecTest(Bitvec *p, u32 i){ 104 if( p==0 ) return 0; 105 if( i>p->iSize || i==0 ) return 0; 106 if( p->iSize<=BITVEC_NBIT ){ 107 i--; 108 return (p->u.aBitmap[i/8] & (1<<(i&7)))!=0; 109 } 110 if( p->iDivisor>0 ){ 111 u32 bin = (i-1)/p->iDivisor; 112 i = (i-1)%p->iDivisor + 1; 113 return sqlite3BitvecTest(p->u.apSub[bin], i); 114 }else{ 115 u32 h = BITVEC_HASH(i); 116 while( p->u.aHash[h] ){ 117 if( p->u.aHash[h]==i ) return 1; 118 h++; 119 if( h>=BITVEC_NINT ) h = 0; 120 } 121 return 0; 122 } 123 } 124 125 /* 126 ** Set the i-th bit. Return 0 on success and an error code if 127 ** anything goes wrong. 128 */ 129 int sqlite3BitvecSet(Bitvec *p, u32 i){ 130 u32 h; 131 assert( p!=0 ); 132 assert( i>0 ); 133 if( p->iSize<=BITVEC_NBIT ){ 134 i--; 135 p->u.aBitmap[i/8] |= 1 << (i&7); 136 return SQLITE_OK; 137 } 138 if( p->iDivisor ){ 139 u32 bin = (i-1)/p->iDivisor; 140 i = (i-1)%p->iDivisor + 1; 141 if( p->u.apSub[bin]==0 ){ 142 sqlite3FaultBenign(SQLITE_FAULTINJECTOR_MALLOC, 1); 143 p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor ); 144 sqlite3FaultBenign(SQLITE_FAULTINJECTOR_MALLOC, 0); 145 if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM; 146 } 147 return sqlite3BitvecSet(p->u.apSub[bin], i); 148 } 149 h = BITVEC_HASH(i); 150 while( p->u.aHash[h] ){ 151 if( p->u.aHash[h]==i ) return SQLITE_OK; 152 h++; 153 if( h==BITVEC_NINT ) h = 0; 154 } 155 p->nSet++; 156 if( p->nSet>=BITVEC_MXHASH ){ 157 int j, rc; 158 u32 aiValues[BITVEC_NINT]; 159 memcpy(aiValues, p->u.aHash, sizeof(aiValues)); 160 memset(p->u.apSub, 0, sizeof(p->u.apSub[0])*BITVEC_NPTR); 161 p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR; 162 rc = sqlite3BitvecSet(p, i); 163 for(j=0; j<BITVEC_NINT; j++){ 164 if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]); 165 } 166 return rc; 167 } 168 p->u.aHash[h] = i; 169 return SQLITE_OK; 170 } 171 172 /* 173 ** Clear the i-th bit. Return 0 on success and an error code if 174 ** anything goes wrong. 175 */ 176 void sqlite3BitvecClear(Bitvec *p, u32 i){ 177 assert( p!=0 ); 178 assert( i>0 ); 179 if( p->iSize<=BITVEC_NBIT ){ 180 i--; 181 p->u.aBitmap[i/8] &= ~(1 << (i&7)); 182 }else if( p->iDivisor ){ 183 u32 bin = (i-1)/p->iDivisor; 184 i = (i-1)%p->iDivisor + 1; 185 if( p->u.apSub[bin] ){ 186 sqlite3BitvecClear(p->u.apSub[bin], i); 187 } 188 }else{ 189 int j; 190 u32 aiValues[BITVEC_NINT]; 191 memcpy(aiValues, p->u.aHash, sizeof(aiValues)); 192 memset(p->u.aHash, 0, sizeof(p->u.aHash[0])*BITVEC_NINT); 193 p->nSet = 0; 194 for(j=0; j<BITVEC_NINT; j++){ 195 if( aiValues[j] && aiValues[j]!=i ){ 196 sqlite3BitvecSet(p, aiValues[j]); 197 } 198 } 199 } 200 } 201 202 /* 203 ** Destroy a bitmap object. Reclaim all memory used. 204 */ 205 void sqlite3BitvecDestroy(Bitvec *p){ 206 if( p==0 ) return; 207 if( p->iDivisor ){ 208 int i; 209 for(i=0; i<BITVEC_NPTR; i++){ 210 sqlite3BitvecDestroy(p->u.apSub[i]); 211 } 212 } 213 sqlite3_free(p); 214 } 215 216 #ifndef SQLITE_OMIT_BUILTIN_TEST 217 /* 218 ** Let V[] be an array of unsigned characters sufficient to hold 219 ** up to N bits. Let I be an integer between 0 and N. 0<=I<N. 220 ** Then the following macros can be used to set, clear, or test 221 ** individual bits within V. 222 */ 223 #define SETBIT(V,I) V[I>>3] |= (1<<(I&7)) 224 #define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7)) 225 #define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0 226 227 /* 228 ** This routine runs an extensive test of the Bitvec code. 229 ** 230 ** The input is an array of integers that acts as a program 231 ** to test the Bitvec. The integers are opcodes followed 232 ** by 0, 1, or 3 operands, depending on the opcode. Another 233 ** opcode follows immediately after the last operand. 234 ** 235 ** There are 6 opcodes numbered from 0 through 5. 0 is the 236 ** "halt" opcode and causes the test to end. 237 ** 238 ** 0 Halt and return the number of errors 239 ** 1 N S X Set N bits beginning with S and incrementing by X 240 ** 2 N S X Clear N bits beginning with S and incrementing by X 241 ** 3 N Set N randomly chosen bits 242 ** 4 N Clear N randomly chosen bits 243 ** 5 N S X Set N bits from S increment X in array only, not in bitvec 244 ** 245 ** The opcodes 1 through 4 perform set and clear operations are performed 246 ** on both a Bitvec object and on a linear array of bits obtained from malloc. 247 ** Opcode 5 works on the linear array only, not on the Bitvec. 248 ** Opcode 5 is used to deliberately induce a fault in order to 249 ** confirm that error detection works. 250 ** 251 ** At the conclusion of the test the linear array is compared 252 ** against the Bitvec object. If there are any differences, 253 ** an error is returned. If they are the same, zero is returned. 254 ** 255 ** If a memory allocation error occurs, return -1. 256 */ 257 int sqlite3BitvecBuiltinTest(int sz, int *aOp){ 258 Bitvec *pBitvec = 0; 259 unsigned char *pV = 0; 260 int rc = -1; 261 int i, nx, pc, op; 262 263 /* Allocate the Bitvec to be tested and a linear array of 264 ** bits to act as the reference */ 265 pBitvec = sqlite3BitvecCreate( sz ); 266 pV = sqlite3_malloc( (sz+7)/8 + 1 ); 267 if( pBitvec==0 || pV==0 ) goto bitvec_end; 268 memset(pV, 0, (sz+7)/8 + 1); 269 270 /* Run the program */ 271 pc = 0; 272 while( (op = aOp[pc])!=0 ){ 273 switch( op ){ 274 case 1: 275 case 2: 276 case 5: { 277 nx = 4; 278 i = aOp[pc+2] - 1; 279 aOp[pc+2] += aOp[pc+3]; 280 break; 281 } 282 case 3: 283 case 4: 284 default: { 285 nx = 2; 286 sqlite3_randomness(sizeof(i), &i); 287 break; 288 } 289 } 290 if( (--aOp[pc+1]) > 0 ) nx = 0; 291 pc += nx; 292 i = (i & 0x7fffffff)%sz; 293 if( (op & 1)!=0 ){ 294 SETBIT(pV, (i+1)); 295 if( op!=5 ){ 296 if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end; 297 } 298 }else{ 299 CLEARBIT(pV, (i+1)); 300 sqlite3BitvecClear(pBitvec, i+1); 301 } 302 } 303 304 /* Test to make sure the linear array exactly matches the 305 ** Bitvec object. Start with the assumption that they do 306 ** match (rc==0). Change rc to non-zero if a discrepancy 307 ** is found. 308 */ 309 rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1) 310 + sqlite3BitvecTest(pBitvec, 0); 311 for(i=1; i<=sz; i++){ 312 if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){ 313 rc = i; 314 break; 315 } 316 } 317 318 /* Free allocated structure */ 319 bitvec_end: 320 sqlite3_free(pV); 321 sqlite3BitvecDestroy(pBitvec); 322 return rc; 323 } 324 #endif /* SQLITE_OMIT_BUILTIN_TEST */ 325