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