Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch integrity-check-heap Excluding Merge-Ins
This is equivalent to a diff from d3c00d61 to 5619c959
2015-05-21
| ||
02:07 | When parsing the schema, ignore any SQL that does not begin with "CREATE". Cherrypick of [d3c00d61581c] with additional changes. (check-in: 09784f37 user: drh tags: branch-3.7.11) | |
2015-05-20
| ||
19:57 | When parsing the schema, ignore any SQL that does not begin with "CREATE". Cherrypick of [d3c00d61581c]. (check-in: 0da229b8 user: dan tags: branch-3.8.6) | |
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) | |
07:19 | Ensure the sqlite3Select() routine always returns non-zero if an error has occurred. (check-in: b51028ed user: dan tags: trunk) | |
04:20 | Merge updates from trunk. (Closed-Leaf check-in: 22827542 user: mistachkin tags: expShell) | |
03:24 | Merge updates from trunk. Make OSTRACE changes work on Linux. (check-in: cd154266 user: mistachkin tags: winTest) | |
00:26 | When parsing the schema, ignore any SQL that does not begin with "CREATE". (check-in: d3c00d61 user: drh tags: trunk) | |
2015-04-15
| ||
19:25 | Fix a potential one-byte buffer overread in the command-line shell. (check-in: e018f4bf user: drh tags: trunk) | |
Changes to src/btree.c.
︙ | ︙ | |||
8523 8524 8525 8526 8527 8528 8529 8530 8531 8532 8533 8534 8535 8536 | } #endif iPage = get4byte(pOvflData); sqlite3PagerUnref(pOvflPage); } } #endif /* SQLITE_OMIT_INTEGRITY_CHECK */ #ifndef SQLITE_OMIT_INTEGRITY_CHECK /* ** Do various sanity checks on a single page of a tree. Return ** the tree depth. Root pages return 0. Parents of root pages ** return 1, and so forth. ** | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 8523 8524 8525 8526 8527 8528 8529 8530 8531 8532 8533 8534 8535 8536 8537 8538 8539 8540 8541 8542 8543 8544 8545 8546 8547 8548 8549 8550 8551 8552 8553 8554 8555 8556 8557 8558 8559 8560 8561 8562 8563 8564 8565 8566 8567 8568 8569 8570 8571 8572 8573 8574 8575 8576 8577 8578 8579 8580 8581 8582 8583 8584 8585 8586 8587 | } #endif iPage = get4byte(pOvflData); sqlite3PagerUnref(pOvflPage); } } #endif /* SQLITE_OMIT_INTEGRITY_CHECK */ /* ** An implementation of a min-heap. ** ** aHeap[0] is the number of elements on the heap. aHeap[1] is the ** root element. For element aHeap[N] the daughter nodes are aHeap[N*2] ** and aHeap[N*2+1]. ** ** The heap property is this: Every node is less than or equal to both ** of its daughter nodes. A consequence of the heap property is that the ** root node aHeap[1] is always the minimum value current in the heap. ** ** The btreeHeapInsert() routine inserts an unsigned 32-bit number onto ** the heap, preserving the heap property. The btreeHeapPull() routine ** removes the root element from the heap (the minimum value in the heap) ** and then move other nodes around as necessary to preserve the heap ** property. ** ** This heap is used for cell overlap and coverage testing. Each u32 ** entry represents the span of a cell or freeblock on a btree page. ** The upper 16 bits are the index of the first byte of a range and the ** lower 16 bits are the index of the last byte of that range. */ static void btreeHeapInsert(u32 *aHeap, u32 x){ u32 j, i = ++aHeap[0]; aHeap[i] = x; while( i>1 && aHeap[j=i/2]>aHeap[i] ){ x = aHeap[j]; aHeap[j] = aHeap[i]; aHeap[i] = x; i = j; } } static int btreeHeapPull(u32 *aHeap, u32 *pOut){ u32 j, i, x; if( (x = aHeap[0])==0 ) return 0; *pOut = aHeap[1]; aHeap[1] = aHeap[x]; aHeap[x] = 0xffffffff; aHeap[0]--; i = 1; while( (j = i*2)<=aHeap[0] ){ if( aHeap[j]>aHeap[j+1] ) j++; if( aHeap[i]<aHeap[j] ) break; x = aHeap[i]; aHeap[i] = aHeap[j]; aHeap[j] = x; i = j; } return 1; } #ifndef SQLITE_OMIT_INTEGRITY_CHECK /* ** Do various sanity checks on a single page of a tree. Return ** the tree depth. Root pages return 0. Parents of root pages ** return 1, and so forth. ** |
︙ | ︙ | |||
8556 8557 8558 8559 8560 8561 8562 | MemPage *pPage; int i, rc, depth, d2, pgno, cnt; int hdr, cellStart; int nCell; u8 *data; BtShared *pBt; int usableSize; | | > | 8607 8608 8609 8610 8611 8612 8613 8614 8615 8616 8617 8618 8619 8620 8621 8622 | MemPage *pPage; int i, rc, depth, d2, pgno, cnt; int hdr, cellStart; int nCell; u8 *data; BtShared *pBt; int usableSize; u32 *heap = 0; u32 x, prev; i64 nMinKey = 0; i64 nMaxKey = 0; const char *saved_zPfx = pCheck->zPfx; int saved_v1 = pCheck->v1; int saved_v2 = pCheck->v2; /* Check that the page exists |
︙ | ︙ | |||
8701 8702 8703 8704 8705 8706 8707 | } } /* Check for complete coverage of the page */ data = pPage->aData; hdr = pPage->hdrOffset; | | | | | < | | < < | > > > > | | > > > > | | 8753 8754 8755 8756 8757 8758 8759 8760 8761 8762 8763 8764 8765 8766 8767 8768 8769 8770 8771 8772 8773 8774 8775 8776 8777 8778 8779 8780 8781 8782 8783 8784 8785 8786 8787 8788 8789 8790 8791 8792 8793 8794 8795 8796 8797 8798 8799 8800 8801 8802 8803 8804 8805 8806 8807 8808 8809 8810 8811 8812 8813 8814 8815 8816 8817 8818 8819 8820 8821 8822 8823 8824 8825 8826 8827 8828 8829 8830 8831 8832 8833 8834 8835 8836 8837 8838 8839 8840 8841 8842 8843 8844 8845 | } } /* Check for complete coverage of the page */ data = pPage->aData; hdr = pPage->hdrOffset; heap = (u32*)sqlite3PageMalloc( pBt->pageSize ); pCheck->zPfx = 0; if( heap==0 ){ pCheck->mallocFailed = 1; }else{ int contentOffset = get2byteNotZero(&data[hdr+5]); assert( contentOffset<=usableSize ); /* Enforced by btreeInitPage() */ heap[0] = 0; btreeHeapInsert(heap, contentOffset-1); /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the ** number of cells on the page. */ nCell = get2byte(&data[hdr+3]); /* EVIDENCE-OF: R-23882-45353 The cell pointer array of a b-tree page ** immediately follows the b-tree page header. */ cellStart = hdr + 12 - 4*pPage->leaf; /* EVIDENCE-OF: R-02776-14802 The cell pointer array consists of K 2-byte ** integer offsets to the cell contents. */ for(i=0; i<nCell; i++){ int pc = get2byte(&data[cellStart+i*2]); u32 size = 65536; if( pc<=usableSize-4 ){ size = cellSizePtr(pPage, &data[pc]); } if( (int)(pc+size-1)>=usableSize ){ pCheck->zPfx = 0; checkAppendMsg(pCheck, "Corruption detected in cell %d on page %d",i,iPage); }else{ btreeHeapInsert(heap, (pc<<16)|(pc+size-1)); } } /* EVIDENCE-OF: R-20690-50594 The second field of the b-tree page header ** is the offset of the first freeblock, or zero if there are no ** freeblocks on the page. */ i = get2byte(&data[hdr+1]); while( i>0 ){ int size, j; assert( i<=usableSize-4 ); /* Enforced by btreeInitPage() */ size = get2byte(&data[i+2]); assert( i+size<=usableSize ); /* Enforced by btreeInitPage() */ btreeHeapInsert(heap, (i<<16)|(i+size-1)); /* EVIDENCE-OF: R-58208-19414 The first 2 bytes of a freeblock are a ** big-endian integer which is the offset in the b-tree page of the next ** freeblock in the chain, or zero if the freeblock is the last on the ** chain. */ j = get2byte(&data[i]); /* EVIDENCE-OF: R-06866-39125 Freeblocks are always connected in order of ** increasing offset. */ assert( j==0 || j>i+size ); /* Enforced by btreeInitPage() */ assert( j<=usableSize-4 ); /* Enforced by btreeInitPage() */ i = j; } cnt = 0; assert( heap[0]>0 ); assert( (heap[1]>>16)==0 ); btreeHeapPull(heap,&prev); while( btreeHeapPull(heap,&x) ){ if( (prev&0xffff)+1>(x>>16) ){ checkAppendMsg(pCheck, "Multiple uses for byte %u of page %d", x>>16, iPage); break; }else{ cnt += (x>>16) - (prev&0xffff) - 1; prev = x; } } cnt += usableSize - (prev&0xffff) - 1; /* EVIDENCE-OF: R-43263-13491 The total number of bytes in all fragments ** is stored in the fifth field of the b-tree page header. ** EVIDENCE-OF: R-07161-27322 The one-byte integer at offset 7 gives the ** number of fragmented free bytes within the cell content area. */ if( cnt!=data[hdr+7] ){ checkAppendMsg(pCheck, "Fragmentation of %d bytes reported as %d on page %d", cnt, data[hdr+7], iPage); } } sqlite3PageFree(heap); releasePage(pPage); end_of_check: pCheck->zPfx = saved_zPfx; pCheck->v1 = saved_v1; pCheck->v2 = saved_v2; return depth+1; |
︙ | ︙ |