Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add new file rtreeA.test, to test that the r-tree extension doesn't crash if it encounters a corrupt or inconsistent database. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
68a305fd5ac917317fee2ef6670ac389 |
User & Date: | dan 2010-09-22 14:19:53.000 |
Context
2010-09-22
| ||
19:06 | Further tests and changes to make the r-tree module more robust. (check-in: 7ff3574b9c user: dan tags: trunk) | |
14:19 | Add new file rtreeA.test, to test that the r-tree extension doesn't crash if it encounters a corrupt or inconsistent database. (check-in: 68a305fd5a user: dan tags: trunk) | |
2010-09-21
| ||
19:00 | Add new file e_delete.test. (check-in: 14e8659e57 user: dan tags: trunk) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
8 9 10 11 12 13 14 15 16 17 18 19 20 21 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains code for implementations of the r-tree and r*-tree ** algorithms packaged as an SQLite virtual table module. */ #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) /* ** This file contains an implementation of a couple of different variants ** of the r-tree algorithm. See the README file for further details. The ** same data-structure is used for all, but the algorithms for insert and | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains code for implementations of the r-tree and r*-tree ** algorithms packaged as an SQLite virtual table module. */ /* ** Database Format of R-Tree Tables ** -------------------------------- ** ** The data structure for a single virtual r-tree table is stored in three ** native SQLite tables declared as follows. In each case, the '%' character ** in the table name is replaced with the user-supplied name of the r-tree ** table. ** ** CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB) ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER) ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER) ** ** The data for each node of the r-tree structure is stored in the %_node ** table. For each node that is not the root node of the r-tree, there is ** an entry in the %_parent table associating the node with its parent. ** And for each row of data in the table, there is an entry in the %_rowid ** table that maps from the entries rowid to the id of the node that it ** is stored on. ** ** The root node of an r-tree always exists, even if the r-tree table is ** empty. The nodeno of the root node is always 1. All other nodes in the ** table must be the same size as the root node. The content of each node ** is formatted as follows: ** ** 1. If the node is the root node (node 1), then the first 2 bytes ** of the node contain the tree depth as a big-endian integer. ** For non-root nodes, the first 2 bytes are left unused. ** ** 2. The next 2 bytes contain the number of entries currently ** stored in the node. ** ** 3. The remainder of the node contains the node entries. Each entry ** consists of a single 8-byte integer followed by an even number ** of 4-byte coordinates. For leaf nodes the integer is the rowid ** of a record. For internal nodes it is the node number of a ** child page. */ #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) /* ** This file contains an implementation of a couple of different variants ** of the r-tree algorithm. See the README file for further details. The ** same data-structure is used for all, but the algorithms for insert and |
︙ | ︙ | |||
146 147 148 149 150 151 152 153 154 155 156 157 158 159 | ** If an R*-tree "Reinsert" operation is required, the same number of ** cells are removed from the overfull node and reinserted into the tree. */ #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3) #define RTREE_REINSERT(p) RTREE_MINCELLS(p) #define RTREE_MAXCELLS 51 /* ** An rtree cursor object. */ struct RtreeCursor { sqlite3_vtab_cursor base; RtreeNode *pNode; /* Node cursor is currently pointing at */ int iCell; /* Index of current cell in pNode */ | > > > > > > > > > | 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | ** If an R*-tree "Reinsert" operation is required, the same number of ** cells are removed from the overfull node and reinserted into the tree. */ #define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3) #define RTREE_REINSERT(p) RTREE_MINCELLS(p) #define RTREE_MAXCELLS 51 /* ** The smallest possible node-size is (512-64)==448 bytes. And the largest ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates). ** Therefore all non-root nodes must contain at least 3 entries. Since ** 2^40 is greater than 2^64, an r-tree structure always has a depth of ** 40 or less. */ #define RTREE_MAX_DEPTH 40 /* ** An rtree cursor object. */ struct RtreeCursor { sqlite3_vtab_cursor base; RtreeNode *pNode; /* Node cursor is currently pointing at */ int iCell; /* Index of current cell in pNode */ |
︙ | ︙ | |||
195 196 197 198 199 200 201 | #define RTREE_LT 0x43 #define RTREE_GE 0x44 #define RTREE_GT 0x45 #define RTREE_MATCH 0x46 /* ** An rtree structure node. | < < < < < < < < < < < < < < < | 243 244 245 246 247 248 249 250 251 252 253 254 255 256 | #define RTREE_LT 0x43 #define RTREE_GE 0x44 #define RTREE_GT 0x45 #define RTREE_MATCH 0x46 /* ** An rtree structure node. */ struct RtreeNode { RtreeNode *pParent; /* Parent node */ i64 iNode; int nRef; int isDirty; u8 *zData; |
︙ | ︙ | |||
366 367 368 369 370 371 372 | /* ** Search the node hash table for node iNode. If found, return a pointer ** to it. Otherwise, return 0. */ static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ RtreeNode *p; | < | 399 400 401 402 403 404 405 406 407 408 409 410 411 412 | /* ** Search the node hash table for node iNode. If found, return a pointer ** to it. Otherwise, return 0. */ static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ RtreeNode *p; for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext); return p; } /* ** Add node pNode to the node hash table. */ |
︙ | ︙ | |||
442 443 444 445 446 447 448 | pNode->pParent = pParent; } pNode->nRef++; *ppNode = pNode; return SQLITE_OK; } | > > > > > | | < | | | | | | | | < < < < < < | | < < < | | < > > > > > > > > > > > > > > > > > > > > > | | | | > > > > > | 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 | pNode->pParent = pParent; } pNode->nRef++; *ppNode = pNode; return SQLITE_OK; } sqlite3_bind_int64(pRtree->pReadNode, 1, iNode); rc = sqlite3_step(pRtree->pReadNode); if( rc==SQLITE_ROW ){ const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0); if( pRtree->iNodeSize==sqlite3_column_bytes(pRtree->pReadNode, 0) ){ pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize); if( !pNode ){ rc = SQLITE_NOMEM; }else{ pNode->pParent = pParent; pNode->zData = (u8 *)&pNode[1]; pNode->nRef = 1; pNode->iNode = iNode; pNode->isDirty = 0; pNode->pNext = 0; memcpy(pNode->zData, zBlob, pRtree->iNodeSize); nodeReference(pParent); } } } rc = sqlite3_reset(pRtree->pReadNode); /* If the root node was just loaded, set pRtree->iDepth to the height ** of the r-tree structure. A height of zero means all data is stored on ** the root node. A height of one means the children of the root node ** 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; } } /* 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. */ if( pNode && rc==SQLITE_OK ){ if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){ rc = SQLITE_CORRUPT; } } if( rc==SQLITE_OK ){ if( pNode!=0 ){ nodeHashInsert(pRtree, pNode); }else{ rc = SQLITE_CORRUPT; } *ppNode = pNode; }else{ sqlite3_free(pNode); *ppNode = 0; } return rc; } /* ** Overwrite cell iCell of node pNode with the contents of pCell. |
︙ | ︙ | |||
530 531 532 533 534 535 536 | ){ int nCell; /* Current number of cells in pNode */ int nMaxCell; /* Maximum number of cells for pNode */ nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; nCell = NCELL(pNode); | | < | 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 | ){ int nCell; /* Current number of cells in pNode */ int nMaxCell; /* Maximum number of cells for pNode */ nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; nCell = NCELL(pNode); assert( nCell<=nMaxCell ); if( nCell<nMaxCell ){ nodeOverwriteCell(pRtree, pNode, pCell, nCell); writeInt16(&pNode->zData[2], nCell+1); pNode->isDirty = 1; } return (nCell==nMaxCell); |
︙ | ︙ | |||
2572 2573 2574 2575 2576 2577 2578 | ){ Rtree *pRtree = (Rtree *)pVtab; int rc = SQLITE_OK; rtreeReference(pRtree); assert(nData>=1); | < < < | 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 | ){ Rtree *pRtree = (Rtree *)pVtab; int rc = SQLITE_OK; rtreeReference(pRtree); assert(nData>=1); /* If azData[0] is not an SQL NULL value, it is the rowid of a ** record to delete from the r-tree table. The following block does ** just that. */ if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){ i64 iDelete; /* The rowid to delete */ |
︙ | ︙ |
Added ext/rtree/rtreeA.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | # 2010 September 22 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file contains tests for the r-tree module. Specifically, it tests # that corrupt or inconsistent databases do not cause crashes in the r-tree # module. # if {![info exists testdir]} { set testdir [file join [file dirname [info script]] .. .. test] } source $testdir/tester.tcl ifcapable !rtree { finish_test ; return } proc create_t1 {} { db close forcedelete test.db sqlite3 db test.db execsql { CREATE VIRTUAL TABLE t1 USING rtree(id, x1, x2, y1, y2); } } proc populate_t1 {} { execsql BEGIN for {set i 0} {$i < 500} {incr i} { set x2 [expr $i+5] set y2 [expr $i+5] execsql { INSERT INTO t1 VALUES($i, $i, $x2, $i, $y2) } } execsql COMMIT } proc truncate_node {nodeno nTrunc} { set blob [db one {SELECT data FROM t1_node WHERE nodeno=$nodeno}] if {$nTrunc<0} {set nTrunc "end-$nTrunc"} set blob [string range $blob 0 $nTrunc] db eval { UPDATE t1_node SET data = $blob WHERE nodeno=$nodeno } } proc set_tree_depth {tbl {newvalue ""}} { set blob [db one "SELECT data FROM ${tbl}_node WHERE nodeno=1"] if {$newvalue == ""} { binary scan $blob Su oldvalue return $oldvalue } set blob [binary format Sua* $newvalue [string range $blob 2 end]] db eval "UPDATE ${tbl}_node SET data = \$blob WHERE nodeno=1" return [set_tree_depth $tbl] } proc set_entry_count {tbl nodeno {newvalue ""}} { set blob [db one "SELECT data FROM ${tbl}_node WHERE nodeno=$nodeno"] if {$newvalue == ""} { binary scan [string range $blob 2 end] Su oldvalue return $oldvalue } set blob [binary format a*Sua* \ [string range $blob 0 1] $newvalue [string range $blob 4 end] ] db eval "UPDATE ${tbl}_node SET data = \$blob WHERE nodeno=$nodeno" return [set_entry_count $tbl $nodeno] } proc do_corruption_tests {prefix args} { set testarray [lindex $args end] set errormsg {database disk image is malformed} foreach {z value} [lrange $args 0 end-1] { set n [string length $z] if {$n>=2 && [string equal -length $n $z "-error"]} { set errormsg $value } } foreach {tn sql} $testarray { do_catchsql_test $prefix.$tn $sql [list 1 $errormsg] } } #------------------------------------------------------------------------- # Test the libraries response if the %_node table is completely empty # (i.e. the root node is missing), or has been removed from the database # entirely. # create_t1 populate_t1 do_execsql_test rtreeA-1.0 { DELETE FROM t1_node; } {} do_corruption_tests rtreeA-1.1 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" 4 "SELECT * FROM t1 WHERE x1<10 AND x2>12" } do_execsql_test rtreeA-1.2.0 { DROP TABLE t1_node } {} do_corruption_tests rtreeA-1.2 -error "SQL logic error or missing database" { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" 4 "SELECT * FROM t1 WHERE x1<10 AND x2>12" } #------------------------------------------------------------------------- # Test the libraries response if some of the entries in the %_node table # are the wrong size. # create_t1 populate_t1 do_test rtreeA-2.1.0 { set nodes [db eval {select nodeno FROM t1_node}] foreach {a b c} $nodes { truncate_node $c 200 } } {} do_corruption_tests rtreeA-2.1 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" 4 "SELECT * FROM t1 WHERE x1<10 AND x2>12" } create_t1 populate_t1 do_test rtreeA-2.2.0 { truncate_node 1 200 } {} do_corruption_tests rtreeA-2.2 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" 4 "SELECT * FROM t1 WHERE x1<10 AND x2>12" } #------------------------------------------------------------------------- # Set the "depth" of the tree stored on the root node incorrectly. Test # that this does not cause any problems. # create_t1 populate_t1 do_test rtreeA-3.1.0.1 { set_tree_depth t1 } {1} do_test rtreeA-3.1.0.2 { set_tree_depth t1 3 } {3} do_corruption_tests rtreeA-3.1 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" } do_test rtreeA-3.2.0 { set_tree_depth t1 1000 } {1000} do_corruption_tests rtreeA-3.2 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" } create_t1 populate_t1 do_test rtreeA-3.3.0 { execsql { DELETE FROM t1 WHERE rowid = 0 } set_tree_depth t1 65535 } {65535} do_corruption_tests rtreeA-3.3 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" } #------------------------------------------------------------------------- # Set the "number of entries" field on some nodes incorrectly. # create_t1 populate_t1 do_test rtreeA-4.1.0 { set_entry_count t1 1 4000 } {4000} breakpoint do_corruption_tests rtreeA-4.1 { 1 "SELECT * FROM t1" 2 "SELECT * FROM t1 WHERE rowid=5" 3 "INSERT INTO t1 VALUES(1000, 1, 2, 3, 4)" 4 "SELECT * FROM t1 WHERE x1<10 AND x2>12" } #------------------------------------------------------------------------- # Remove entries from the %_parent table and check that this does not # cause a crash. # create_t1 populate_t1 do_execsql_test rtreeA-5.1.0 { DELETE FROM t1_parent } {} do_corruption_tests rtreeA-5.1 { 1 "DELETE FROM t1 WHERE rowid = 5" 2 "DELETE FROM t1" } finish_test |