/ Check-in [5619c959]
Login

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

Overview
Comment:Use a heap instead of a bitmap for cell overlap and coverage testing of btree pages in PRAGMA integrity_check.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | integrity-check-heap
Files: files | file ages | folders
SHA1: 5619c959bf7babb19fd8ba8b228be7f090fe0ce3
User & Date: drh 2015-04-16 11:56:03
Context
2015-04-16
21:57
Use a heap rather than a bitmap for cell coverage and overlap testing on btree pages in PRAGMA integrity_check. check-in: e94b2ef2 user: drh tags: trunk
11:56
Use a heap instead of a bitmap for cell overlap and coverage testing of btree pages in PRAGMA integrity_check. Closed-Leaf check-in: 5619c959 user: drh tags: integrity-check-heap
00:26
When parsing the schema, ignore any SQL that does not begin with "CREATE". check-in: d3c00d61 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  8523   8523       }
  8524   8524   #endif
  8525   8525       iPage = get4byte(pOvflData);
  8526   8526       sqlite3PagerUnref(pOvflPage);
  8527   8527     }
  8528   8528   }
  8529   8529   #endif /* SQLITE_OMIT_INTEGRITY_CHECK */
         8530  +
         8531  +/*
         8532  +** An implementation of a min-heap.
         8533  +**
         8534  +** aHeap[0] is the number of elements on the heap.  aHeap[1] is the
         8535  +** root element.  For element aHeap[N] the daughter nodes are aHeap[N*2]
         8536  +** and aHeap[N*2+1].
         8537  +**
         8538  +** The heap property is this:  Every node is less than or equal to both
         8539  +** of its daughter nodes.  A consequence of the heap property is that the
         8540  +** root node aHeap[1] is always the minimum value current in the heap.
         8541  +**
         8542  +** The btreeHeapInsert() routine inserts an unsigned 32-bit number onto
         8543  +** the heap, preserving the heap property.  The btreeHeapPull() routine
         8544  +** removes the root element from the heap (the minimum value in the heap)
         8545  +** and then move other nodes around as necessary to preserve the heap
         8546  +** property.
         8547  +**
         8548  +** This heap is used for cell overlap and coverage testing.  Each u32
         8549  +** entry represents the span of a cell or freeblock on a btree page.  
         8550  +** The upper 16 bits are the index of the first byte of a range and the
         8551  +** lower 16 bits are the index of the last byte of that range.
         8552  +*/
         8553  +static void btreeHeapInsert(u32 *aHeap, u32 x){
         8554  +  u32 j, i = ++aHeap[0];
         8555  +  aHeap[i] = x;
         8556  +  while( i>1 && aHeap[j=i/2]>aHeap[i] ){
         8557  +    x = aHeap[j];
         8558  +    aHeap[j] = aHeap[i];
         8559  +    aHeap[i] = x;
         8560  +    i = j;
         8561  +  }
         8562  +}
         8563  +static int btreeHeapPull(u32 *aHeap, u32 *pOut){
         8564  +  u32 j, i, x;
         8565  +  if( (x = aHeap[0])==0 ) return 0;
         8566  +  *pOut = aHeap[1];
         8567  +  aHeap[1] = aHeap[x];
         8568  +  aHeap[x] = 0xffffffff;
         8569  +  aHeap[0]--;
         8570  +  i = 1;
         8571  +  while( (j = i*2)<=aHeap[0] ){
         8572  +    if( aHeap[j]>aHeap[j+1] ) j++;
         8573  +    if( aHeap[i]<aHeap[j] ) break;
         8574  +    x = aHeap[i];
         8575  +    aHeap[i] = aHeap[j];
         8576  +    aHeap[j] = x;
         8577  +    i = j;
         8578  +  }
         8579  +  return 1;  
         8580  +}
  8530   8581   
  8531   8582   #ifndef SQLITE_OMIT_INTEGRITY_CHECK
  8532   8583   /*
  8533   8584   ** Do various sanity checks on a single page of a tree.  Return
  8534   8585   ** the tree depth.  Root pages return 0.  Parents of root pages
  8535   8586   ** return 1, and so forth.
  8536   8587   ** 
................................................................................
  8556   8607     MemPage *pPage;
  8557   8608     int i, rc, depth, d2, pgno, cnt;
  8558   8609     int hdr, cellStart;
  8559   8610     int nCell;
  8560   8611     u8 *data;
  8561   8612     BtShared *pBt;
  8562   8613     int usableSize;
  8563         -  char *hit = 0;
         8614  +  u32 *heap = 0;
         8615  +  u32 x, prev;
  8564   8616     i64 nMinKey = 0;
  8565   8617     i64 nMaxKey = 0;
  8566   8618     const char *saved_zPfx = pCheck->zPfx;
  8567   8619     int saved_v1 = pCheck->v1;
  8568   8620     int saved_v2 = pCheck->v2;
  8569   8621   
  8570   8622     /* Check that the page exists
................................................................................
  8701   8753       }
  8702   8754     }
  8703   8755   
  8704   8756     /* Check for complete coverage of the page
  8705   8757     */
  8706   8758     data = pPage->aData;
  8707   8759     hdr = pPage->hdrOffset;
  8708         -  hit = sqlite3PageMalloc( pBt->pageSize );
         8760  +  heap = (u32*)sqlite3PageMalloc( pBt->pageSize );
  8709   8761     pCheck->zPfx = 0;
  8710         -  if( hit==0 ){
         8762  +  if( heap==0 ){
  8711   8763       pCheck->mallocFailed = 1;
  8712   8764     }else{
  8713   8765       int contentOffset = get2byteNotZero(&data[hdr+5]);
  8714   8766       assert( contentOffset<=usableSize );  /* Enforced by btreeInitPage() */
  8715         -    memset(hit+contentOffset, 0, usableSize-contentOffset);
  8716         -    memset(hit, 1, contentOffset);
         8767  +    heap[0] = 0;
         8768  +    btreeHeapInsert(heap, contentOffset-1);
  8717   8769       /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the
  8718   8770       ** number of cells on the page. */
  8719   8771       nCell = get2byte(&data[hdr+3]);
  8720   8772       /* EVIDENCE-OF: R-23882-45353 The cell pointer array of a b-tree page
  8721   8773       ** immediately follows the b-tree page header. */
  8722   8774       cellStart = hdr + 12 - 4*pPage->leaf;
  8723   8775       /* EVIDENCE-OF: R-02776-14802 The cell pointer array consists of K 2-byte
  8724   8776       ** integer offsets to the cell contents. */
  8725   8777       for(i=0; i<nCell; i++){
  8726   8778         int pc = get2byte(&data[cellStart+i*2]);
  8727   8779         u32 size = 65536;
  8728         -      int j;
  8729   8780         if( pc<=usableSize-4 ){
  8730   8781           size = cellSizePtr(pPage, &data[pc]);
  8731   8782         }
  8732   8783         if( (int)(pc+size-1)>=usableSize ){
  8733   8784           pCheck->zPfx = 0;
  8734   8785           checkAppendMsg(pCheck,
  8735   8786               "Corruption detected in cell %d on page %d",i,iPage);
  8736   8787         }else{
  8737         -        for(j=pc+size-1; j>=pc; j--) hit[j]++;
         8788  +        btreeHeapInsert(heap, (pc<<16)|(pc+size-1));
  8738   8789         }
  8739   8790       }
  8740   8791       /* EVIDENCE-OF: R-20690-50594 The second field of the b-tree page header
  8741   8792       ** is the offset of the first freeblock, or zero if there are no
  8742   8793       ** freeblocks on the page. */
  8743   8794       i = get2byte(&data[hdr+1]);
  8744   8795       while( i>0 ){
  8745   8796         int size, j;
  8746   8797         assert( i<=usableSize-4 );     /* Enforced by btreeInitPage() */
  8747   8798         size = get2byte(&data[i+2]);
  8748   8799         assert( i+size<=usableSize );  /* Enforced by btreeInitPage() */
  8749         -      for(j=i+size-1; j>=i; j--) hit[j]++;
         8800  +      btreeHeapInsert(heap, (i<<16)|(i+size-1));
  8750   8801         /* EVIDENCE-OF: R-58208-19414 The first 2 bytes of a freeblock are a
  8751   8802         ** big-endian integer which is the offset in the b-tree page of the next
  8752   8803         ** freeblock in the chain, or zero if the freeblock is the last on the
  8753   8804         ** chain. */
  8754   8805         j = get2byte(&data[i]);
  8755   8806         /* EVIDENCE-OF: R-06866-39125 Freeblocks are always connected in order of
  8756   8807         ** increasing offset. */
  8757   8808         assert( j==0 || j>i+size );  /* Enforced by btreeInitPage() */
  8758   8809         assert( j<=usableSize-4 );   /* Enforced by btreeInitPage() */
  8759   8810         i = j;
  8760   8811       }
  8761         -    for(i=cnt=0; i<usableSize; i++){
  8762         -      if( hit[i]==0 ){
  8763         -        cnt++;
  8764         -      }else if( hit[i]>1 ){
         8812  +    cnt = 0;
         8813  +    assert( heap[0]>0 );
         8814  +    assert( (heap[1]>>16)==0 );
         8815  +    btreeHeapPull(heap,&prev);
         8816  +    while( btreeHeapPull(heap,&x) ){
         8817  +      if( (prev&0xffff)+1>(x>>16) ){
  8765   8818           checkAppendMsg(pCheck,
  8766         -          "Multiple uses for byte %d of page %d", i, iPage);
         8819  +          "Multiple uses for byte %u of page %d", x>>16, iPage);
  8767   8820           break;
         8821  +      }else{
         8822  +        cnt += (x>>16) - (prev&0xffff) - 1;
         8823  +        prev = x;
  8768   8824         }
  8769   8825       }
         8826  +    cnt += usableSize - (prev&0xffff) - 1;
  8770   8827       /* EVIDENCE-OF: R-43263-13491 The total number of bytes in all fragments
  8771   8828       ** is stored in the fifth field of the b-tree page header.
  8772   8829       ** EVIDENCE-OF: R-07161-27322 The one-byte integer at offset 7 gives the
  8773   8830       ** number of fragmented free bytes within the cell content area.
  8774   8831       */
  8775   8832       if( cnt!=data[hdr+7] ){
  8776   8833         checkAppendMsg(pCheck,
  8777   8834             "Fragmentation of %d bytes reported as %d on page %d",
  8778   8835             cnt, data[hdr+7], iPage);
  8779   8836       }
  8780   8837     }
  8781         -  sqlite3PageFree(hit);
         8838  +  sqlite3PageFree(heap);
  8782   8839     releasePage(pPage);
  8783   8840   
  8784   8841   end_of_check:
  8785   8842     pCheck->zPfx = saved_zPfx;
  8786   8843     pCheck->v1 = saved_v1;
  8787   8844     pCheck->v2 = saved_v2;
  8788   8845     return depth+1;