Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Prevent an infinite loop in rtree that can result from a corrupt shadow table. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA3-256: |
085667180b230587abb82abfdd14da88 |
| User & Date: | drh 2018-12-21 16:53:58 |
Context
|
2018-12-21
| ||
| 17:51 | Fix a potential NULL-pointer deference in RTREE due to corrupt shadow tables. (check-in: 1fdd3604 user: drh tags: trunk) | |
| 16:53 | Prevent an infinite loop in rtree that can result from a corrupt shadow table. (check-in: 08566718 user: drh tags: trunk) | |
| 15:13 | Fix the RTree extension so that it correctly ignores constraints that it does not understand, even if they are against a dimension column. (check-in: ed8531e5 user: drh tags: trunk) | |
Changes
Changes to ext/rtree/rtree.c.
124 124 u8 nDim; /* Number of dimensions */ 125 125 u8 nDim2; /* Twice the number of dimensions */ 126 126 u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */ 127 127 u8 nBytesPerCell; /* Bytes consumed per cell */ 128 128 u8 inWrTrans; /* True if inside write transaction */ 129 129 u8 nAux; /* # of auxiliary columns in %_rowid */ 130 130 u8 nAuxNotNull; /* Number of initial not-null aux columns */ 131 +#ifdef SQLITE_DEBUG 132 + u8 bCorrupt; /* Shadow table corruption detected */ 133 +#endif 131 134 int iDepth; /* Current depth of the r-tree structure */ 132 135 char *zDb; /* Name of database containing r-tree table */ 133 136 char *zName; /* Name of r-tree table */ 134 137 u32 nBusy; /* Current number of users of this structure */ 135 138 i64 nRowEst; /* Estimated number of rows in this table */ 136 139 u32 nCursor; /* Number of open cursors */ 137 140 u32 nNodeRef; /* Number RtreeNodes with positive nRef */ ................................................................................ 183 186 # define RTREE_ZERO 0 184 187 #else 185 188 typedef double RtreeDValue; /* High accuracy coordinate */ 186 189 typedef float RtreeValue; /* Low accuracy coordinate */ 187 190 # define RTREE_ZERO 0.0 188 191 #endif 189 192 193 +/* 194 +** Set the Rtree.bCorrupt flag 195 +*/ 196 +#ifdef SQLITE_DEBUG 197 +# define RTREE_IS_CORRUPT(X) ((X)->bCorrupt = 1) 198 +#else 199 +# define RTREE_IS_CORRUPT(X) 200 +#endif 201 + 190 202 /* 191 203 ** When doing a search of an r-tree, instances of the following structure 192 204 ** record intermediate results from the tree walk. 193 205 ** 194 206 ** The id is always a node-id. For iLevel>=1 the id is the node-id of 195 207 ** the node that the RtreeSearchPoint represents. When iLevel==0, however, 196 208 ** the id is of the parent node and the cell that RtreeSearchPoint ................................................................................ 667 679 sqlite3_free(zTab); 668 680 } 669 681 if( rc ){ 670 682 nodeBlobReset(pRtree); 671 683 *ppNode = 0; 672 684 /* If unable to open an sqlite3_blob on the desired row, that can only 673 685 ** be because the shadow tables hold erroneous data. */ 674 - if( rc==SQLITE_ERROR ) rc = SQLITE_CORRUPT_VTAB; 686 + if( rc==SQLITE_ERROR ){ 687 + rc = SQLITE_CORRUPT_VTAB; 688 + RTREE_IS_CORRUPT(pRtree); 689 + } 675 690 }else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){ 676 691 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize); 677 692 if( !pNode ){ 678 693 rc = SQLITE_NOMEM; 679 694 }else{ 680 695 pNode->pParent = pParent; 681 696 pNode->zData = (u8 *)&pNode[1]; ................................................................................ 696 711 ** are the leaves, and so on. If the depth as specified on the root node 697 712 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt. 698 713 */ 699 714 if( pNode && iNode==1 ){ 700 715 pRtree->iDepth = readInt16(pNode->zData); 701 716 if( pRtree->iDepth>RTREE_MAX_DEPTH ){ 702 717 rc = SQLITE_CORRUPT_VTAB; 718 + RTREE_IS_CORRUPT(pRtree); 703 719 } 704 720 } 705 721 706 722 /* If no error has occurred so far, check if the "number of entries" 707 723 ** field on the node is too large. If so, set the return code to 708 724 ** SQLITE_CORRUPT_VTAB. 709 725 */ 710 726 if( pNode && rc==SQLITE_OK ){ 711 727 if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){ 712 728 rc = SQLITE_CORRUPT_VTAB; 729 + RTREE_IS_CORRUPT(pRtree); 713 730 } 714 731 } 715 732 716 733 if( rc==SQLITE_OK ){ 717 734 if( pNode!=0 ){ 718 735 nodeHashInsert(pRtree, pNode); 719 736 }else{ 720 737 rc = SQLITE_CORRUPT_VTAB; 738 + RTREE_IS_CORRUPT(pRtree); 721 739 } 722 740 *ppNode = pNode; 723 741 }else{ 724 742 if( pNode ){ 725 743 pRtree->nNodeRef--; 726 744 sqlite3_free(pNode); 727 745 } ................................................................................ 939 957 */ 940 958 static void rtreeRelease(Rtree *pRtree){ 941 959 pRtree->nBusy--; 942 960 if( pRtree->nBusy==0 ){ 943 961 pRtree->inWrTrans = 0; 944 962 assert( pRtree->nCursor==0 ); 945 963 nodeBlobReset(pRtree); 946 - assert( pRtree->nNodeRef==0 ); 964 + assert( pRtree->nNodeRef==0 || pRtree->bCorrupt ); 947 965 sqlite3_finalize(pRtree->pWriteNode); 948 966 sqlite3_finalize(pRtree->pDeleteNode); 949 967 sqlite3_finalize(pRtree->pReadRowid); 950 968 sqlite3_finalize(pRtree->pWriteRowid); 951 969 sqlite3_finalize(pRtree->pDeleteRowid); 952 970 sqlite3_finalize(pRtree->pReadParent); 953 971 sqlite3_finalize(pRtree->pWriteParent); ................................................................................ 1271 1289 assert( nCell<200 ); 1272 1290 for(ii=0; ii<nCell; ii++){ 1273 1291 if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){ 1274 1292 *piIndex = ii; 1275 1293 return SQLITE_OK; 1276 1294 } 1277 1295 } 1296 + RTREE_IS_CORRUPT(pRtree); 1278 1297 return SQLITE_CORRUPT_VTAB; 1279 1298 } 1280 1299 1281 1300 /* 1282 1301 ** Return the index of the cell containing a pointer to node pNode 1283 1302 ** in its parent. If pNode is the root node, return -1. 1284 1303 */ ................................................................................ 2133 2152 */ 2134 2153 static int AdjustTree( 2135 2154 Rtree *pRtree, /* Rtree table */ 2136 2155 RtreeNode *pNode, /* Adjust ancestry of this node. */ 2137 2156 RtreeCell *pCell /* This cell was just inserted */ 2138 2157 ){ 2139 2158 RtreeNode *p = pNode; 2159 + int cnt = 0; 2140 2160 while( p->pParent ){ 2141 2161 RtreeNode *pParent = p->pParent; 2142 2162 RtreeCell cell; 2143 2163 int iCell; 2144 2164 2145 - if( nodeParentIndex(pRtree, p, &iCell) ){ 2165 + if( (++cnt)>1000 || nodeParentIndex(pRtree, p, &iCell) ){ 2166 + RTREE_IS_CORRUPT(pRtree); 2146 2167 return SQLITE_CORRUPT_VTAB; 2147 2168 } 2148 2169 2149 2170 nodeGetCell(pRtree, pParent, iCell, &cell); 2150 2171 if( !cellContains(pRtree, &cell, pCell) ){ 2151 2172 cellUnion(pRtree, &cell, pCell); 2152 2173 nodeOverwriteCell(pRtree, pParent, &cell, iCell); ................................................................................ 2606 2627 for(pTest=pLeaf; pTest && pTest->iNode!=iNode; pTest=pTest->pParent); 2607 2628 if( !pTest ){ 2608 2629 rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent); 2609 2630 } 2610 2631 } 2611 2632 rc = sqlite3_reset(pRtree->pReadParent); 2612 2633 if( rc==SQLITE_OK ) rc = rc2; 2613 - if( rc==SQLITE_OK && !pChild->pParent ) rc = SQLITE_CORRUPT_VTAB; 2634 + if( rc==SQLITE_OK && !pChild->pParent ){ 2635 + RTREE_IS_CORRUPT(pRtree); 2636 + rc = SQLITE_CORRUPT_VTAB; 2637 + } 2614 2638 pChild = pChild->pParent; 2615 2639 } 2616 2640 return rc; 2617 2641 } 2618 2642 2619 2643 static int deleteCell(Rtree *, RtreeNode *, int, int); 2620 2644 ................................................................................ 3555 3579 pRtree->zDb, pRtree->zName 3556 3580 ); 3557 3581 rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize); 3558 3582 if( rc!=SQLITE_OK ){ 3559 3583 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); 3560 3584 }else if( pRtree->iNodeSize<(512-64) ){ 3561 3585 rc = SQLITE_CORRUPT_VTAB; 3586 + RTREE_IS_CORRUPT(pRtree); 3562 3587 *pzErr = sqlite3_mprintf("undersize RTree blobs in \"%q_node\"", 3563 3588 pRtree->zName); 3564 3589 } 3565 3590 } 3566 3591 3567 3592 sqlite3_free(zSql); 3568 3593 return rc;
Changes to ext/rtree/rtreefuzz001.test.
18 18 19 19 ifcapable !deserialize||!rtree { 20 20 finish_test 21 21 return 22 22 } 23 23 database_may_be_corrupt 24 24 25 -# In the following database file, there is 384 bytes of free space 26 -# on page 8 that does not appear on the freeblock list. 27 -# 28 25 do_test rtreefuzz001-100 { 29 26 sqlite3 db {} 30 27 db deserialize [decode_hexdb { 31 28 | size 24576 pagesize 4096 filename c1b.db 32 29 | page 1 offset 0 33 30 | 0: 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00 SQLite format 3. 34 31 | 16: 10 00 01 01 00 40 20 20 00 00 00 03 00 00 00 06 .....@ ........ ................................................................................ 468 465 | end c1b.db 469 466 }] 470 467 catchsql { 471 468 SELECT rtreecheck('t1'); 472 469 } 473 470 } {1 {SQL logic error}} 474 471 472 +do_test rtreefuzz001-200 { 473 + sqlite3 db {} 474 + db deserialize [decode_hexdb { 475 +.open --hexdb 476 +| size 16384 pagesize 4096 filename c3.db 477 +| page 1 offset 0 478 +| 0: 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00 SQLite format 3. 479 +| 16: 10 00 01 01 00 40 20 20 00 00 00 00 00 00 00 04 .....@ ........ 480 +| 32: 00 00 00 00 01 00 00 00 00 00 00 04 00 00 00 04 ................ 481 +| 48: 00 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 ................ 482 +| 96: 00 00 00 00 0d 00 00 00 04 0e 9c 00 0f ad 0f 4f ...............O 483 +| 112: 0e fc 0e 9c 00 00 00 00 00 00 00 00 00 00 00 00 ................ 484 +| 3728: 00 00 00 00 00 00 00 00 00 00 00 00 5e 04 07 17 ............^... 485 +| 3744: 1f 1f 01 81 0b 74 61 62 6c 65 74 31 5f 70 61 72 .....tablet1_par 486 +| 3760: 65 6e 74 74 31 5f 70 61 72 65 6e 74 04 43 52 45 entt1_parent.CRE 487 +| 3776: 41 54 45 20 54 41 42 4c 45 20 22 74 31 5f 70 61 ATE TABLE "t1_pa 488 +| 3792: 72 65 6e 74 22 28 6e 6f 64 65 6e 6f 20 49 4e 54 rent"(nodeno INT 489 +| 3808: 45 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59 EGER PRIMARY KEY 490 +| 3824: 2c 70 61 72 65 6e 74 6e 6f 64 65 29 51 03 06 17 ,parentnode)Q... 491 +| 3840: 1b 1b 01 7b 74 61 62 6c 65 74 31 5f 6e 6f 64 65 ....tablet1_node 492 +| 3856: 74 31 5f 6e 6f 64 65 03 43 52 45 41 54 45 20 54 t1_node.CREATE T 493 +| 3872: 41 42 4c 45 20 22 74 31 5f 6e 6f 64 65 22 28 6e ABLE "t1_node"(n 494 +| 3888: 6f 64 65 6e 6f 20 49 4e 54 45 47 45 52 20 50 52 odeno INTEGER PR 495 +| 3904: 49 4d 41 52 59 20 4b 45 59 2c 64 61 74 61 29 5c IMARY KEY,data)\ 496 +| 3920: 02 07 17 1d 1d 01 81 0b 74 61 62 6c 65 74 31 5f ........tablet1_ 497 +| 3936: 72 6f 77 69 64 74 31 5f 72 6f 77 69 64 02 43 52 rowidt1_rowid.CR 498 +| 3952: 45 41 54 45 20 54 41 42 4c 45 20 22 74 31 5f 72 EATE TABLE "t1_r 499 +| 3968: 6f 77 69 64 22 28 72 6f 77 69 64 20 49 4e 54 45 owid"(rowid INTE 500 +| 3984: 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59 2c GER PRIMARY KEY, 501 +| 4000: 6e 6f 64 65 6e 6f 2c 61 30 2c 61 31 29 51 01 07 nodeno,a0,a1)Q.. 502 +| 4016: 17 11 11 08 81 0f 74 61 62 6c 65 74 31 74 31 43 ......tablet1t1C 503 +| 4032: 52 45 41 54 45 20 56 49 52 54 55 41 4c 20 54 41 REATE VIRTUAL TA 504 +| 4048: 42 4c 45 20 74 31 20 55 53 49 4e 47 20 72 74 72 BLE t1 USING rtr 505 +| 4064: 65 65 28 69 64 2c 78 30 2c 78 31 2c 79 30 2c 79 ee(id,x0,x1,y0,y 506 +| 4080: 31 2c 2b 6c 61 62 65 6c 2c 2b 6f 74 68 65 72 29 1,+label,+other) 507 +| page 2 offset 4096 508 +| 0: 0d 00 00 00 0e 0e f7 00 0f e8 0f d0 0f b7 0f 9e ................ 509 +| 16: 0f 91 0f 81 0f 70 0f 5e 0f 4f 0f 39 0f 29 0f 18 .....p.^.O.9.).. 510 +| 32: 0f 06 0e f7 00 00 00 00 00 00 00 00 00 00 00 00 ................ 511 +| 3824: 00 00 00 00 00 00 00 0d 0e 05 00 09 1d 00 74 6f ..............to 512 +| 3840: 70 20 68 61 6c 66 10 0d 05 00 09 23 00 62 6f 74 p half.....#.bot 513 +| 3856: 74 6f 6d 20 68 61 6c 66 0f 0c 05 00 09 21 00 72 tom half.....!.r 514 +| 3872: 69 67 68 74 20 68 61 6c 66 0e 0b 05 00 09 1f 00 ight half....... 515 +| 3888: 6c 65 66 74 20 68 61 6c 66 14 0a 05 00 09 2b 00 left half.....+. 516 +| 3904: 74 68 65 20 77 68 6f 6c 65 20 74 68 69 6e 67 0d the whole thing. 517 +| 3920: 09 05 00 09 1d 00 74 6f 70 20 65 64 67 65 10 08 ......top edge.. 518 +| 3936: 05 00 09 23 00 62 6f 74 74 6f 6d 20 65 64 67 65 ...#.bottom edge 519 +| 3952: 0f 07 05 00 09 21 00 72 69 67 68 74 20 65 64 67 .....!.right edg 520 +| 3968: 65 0e 06 05 00 09 1f 00 6c 65 66 74 20 65 64 67 e.......left edg 521 +| 3984: 65 0b 05 05 00 09 19 00 63 65 6e 74 65 72 17 04 e.......center.. 522 +| 4000: 05 00 09 31 00 75 70 70 65 72 2d 72 69 67 68 74 ...1.upper-right 523 +| 4016: 20 63 6f 72 6e 65 72 17 03 05 00 09 31 00 6c 6f corner.....1.lo 524 +| 4032: 77 65 72 2d 72 69 67 68 74 27 60 f6 32 6e 65 72 wer-right'`.2ner 525 +| 4048: 16 02 05 00 09 2f 00 75 70 70 65 72 2d 6c 65 66 ...../.upper-lef 526 +| 4064: 74 20 63 6f 72 6e 65 72 16 01 05 00 09 2f 00 6c t corner...../.l 527 +| 4080: 6f 77 65 72 2d 6c 65 66 74 20 63 6f 72 6e 65 72 ower-left corner 528 +| page 3 offset 8192 529 +| 0: 0d 00 00 00 02 0b 2d 00 0b 2d 00 00 00 00 00 00 ......-..-...... 530 +| 2848: 00 00 00 00 00 00 00 00 00 00 00 00 00 89 50 01 ..............P. 531 +| 2864: 04 00 93 24 00 00 00 0e 00 00 00 00 00 00 00 01 ...$............ 532 +| 2880: 00 00 00 00 41 20 00 00 00 00 00 00 41 20 01 00 ....A ......A .. 533 +| 2896: 00 00 00 00 00 00 00 02 00 00 00 00 41 00 00 04 ............A... 534 +| 2912: 2b 40 00 0c 42 c8 00 00 00 00 00 00 00 00 00 03 +@..B........... 535 +| 2928: 42 b4 00 00 42 c8 00 00 00 00 00 00 41 20 00 00 B...B.......A .. 536 +| 2944: 00 00 00 00 00 00 00 04 42 b4 00 00 42 c8 00 00 ........B...B... 537 +| 2960: 42 b4 00 00 42 c8 00 00 00 00 00 00 00 00 00 05 B...B........... 538 +| 2976: 42 20 00 00 42 70 00 00 42 20 00 00 42 70 00 00 B ..Bp..B ..Bp.. 539 +| 2992: 00 00 00 00 00 00 00 60 00 00 00 04 0a 00 00 00 .......`........ 540 +| 3008: 00 00 00 42 c8 00 00 00 00 00 00 00 00 00 07 42 ...B...........B 541 +| 3024: be 00 00 42 c8 00 00 00 00 00 00 42 c8 00 00 00 ...B.......B.... 542 +| 3040: 00 00 00 00 00 00 08 00 00 00 00 42 c8 00 00 00 ...........B.... 543 +| 3056: 00 00 00 40 a0 00 00 00 00 00 00 00 00 00 09 00 ...@............ 544 +| 3072: 00 00 00 42 c8 00 00 42 be 00 00 42 c8 00 00 00 ...B...B...B.... 545 +| 3088: 00 00 00 00 00 00 0a 00 00 00 00 42 c8 00 00 00 ...........B.... 546 +| 3104: 00 00 00 42 c8 00 00 00 00 00 00 00 00 00 0b 00 ...B............ 547 +| 3120: 00 00 00 42 48 00 00 00 00 00 04 2c 80 00 00 00 ...BH......,.... 548 +| 3136: 00 00 00 00 00 00 c4 24 c0 00 04 2c 80 00 00 00 .......$...,.... 549 +| 3152: 00 00 04 2c 80 00 00 00 00 00 00 00 00 00 d0 00 ...,............ 550 +| 3168: 00 00 04 2c 80 00 00 00 00 00 04 24 80 00 00 00 ...,.......$.... 551 +| 3184: 00 00 00 00 00 00 e0 00 00 00 04 2c 80 00 04 24 ...........,...$ 552 +| 3200: c0 00 04 2c 00 00 00 00 00 00 00 00 00 00 00 00 ...,............ 553 +| page 4 offset 12288 554 +| 0: 0d 00 00 00 00 10 00 00 00 00 00 00 00 00 00 00 ................ 555 +| end c3.db 556 + }] 557 + catchsql { 558 + WITH RECURSIVE 559 + c1(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c1 WHERE x<99), 560 + c2(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM c2 WHERE y<99) 561 + INSERT INTO t1(id, x0,x1,y0,y1,label) 562 + SELECT 1000+x+y*100, x, x+1, y, y+1, printf('box-%d,%d',x,y) FROM c1, c2; 563 + } 564 +} {1 {malformed database schema (?)}} 565 +do_test rtreefuzz001-210 { 566 + catchsql { 567 + SELECT rtreecheck('t1'); 568 + } 569 +} {1 {database disk image is malformed}} 570 + 475 571 finish_test