/ Check-in [08566718]
Login

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: 085667180b230587abb82abfdd14da8859e23620994d5cf152236b64c756dd04
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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