sqlite3/test/btree2.test

   1 # 2001 September 15
   2 #
   3 # The author disclaims copyright to this source code.  In place of
   4 # a legal notice, here is a blessing:
   5 #
   6 #    May you do good and not evil.
   7 #    May you find forgiveness for yourself and forgive others.
   8 #    May you share freely, never taking more than you give.
   9 #
  10 #***********************************************************************
  11 # This file implements regression tests for SQLite library.  The
  12 # focus of this script is btree database backend
  13 #
  14 # $Id: btree2.test,v 1.14 2005/01/11 10:25:07 danielk1977 Exp $
  15
  16
  17 set testdir [file dirname $argv0]
  18 source $testdir/tester.tcl
  19
  20 if {[info commands btree_open]!=""} {
  21
  22 # Create a new database file containing no entries.  The database should
  23 # contain 5 tables:
  24 #
  25 #     2   The descriptor table
  26 #     3   The foreground table
  27 #     4   The background table
  28 #     5   The long key table
  29 #     6   The long data table
  30 #
  31 # An explanation for what all these tables are used for is provided below.
  32 #
  33 do_test btree2-1.1 {
  34   expr srand(1)
  35   file delete -force test2.bt
  36   file delete -force test2.bt-journal
  37   set ::b [btree_open test2.bt 2000 0]
  38   btree_begin_transaction $::b
  39   btree_create_table $::b 0
  40 } {2}
  41 do_test btree2-1.2 {
  42   btree_create_table $::b 0
  43 } {3}
  44 do_test btree2-1.3 {
  45   btree_create_table $::b 0
  46 } {4}
  47 do_test btree2-1.4 {
  48   btree_create_table $::b 0
  49 } {5}
  50 do_test btree2-1.5 {
  51   btree_create_table $::b 0
  52 } {6}
  53 do_test btree2-1.6 {
  54   set ::c2 [btree_cursor $::b 2 1]
  55   btree_insert $::c2 {one} {1}
  56   btree_move_to $::c2 {one}
  57   btree_delete $::c2
  58   btree_close_cursor $::c2
  59   btree_commit $::b
  60   btree_integrity_check $::b 1 2 3 4 5 6
  61 } {}
  62
  63 # This test module works by making lots of pseudo-random changes to a
  64 # database while simultaneously maintaining an invariant on that database.
  65 # Periodically, the script does a sanity check on the database and verifies
  66 # that the invariant is satisfied.
  67 #
  68 # The invariant is as follows:
  69 #
  70 #   1.  The descriptor table always contains 2 enters.  An entry keyed by
  71 #       "N" is the number of elements in the foreground and background tables
  72 #       combined.  The entry keyed by "L" is the number of digits in the keys
  73 #       for foreground and background tables.
  74 #
  75 #   2.  The union of the foreground an background tables consists of N entries
  76 #       where each entry has an L-digit key. (Actually, some keys can be longer
  77 #       than L characters, but they always start with L digits.)  The keys
  78 #       cover all integers between 1 and N.  Whenever an entry is added to
  79 #       the foreground it is removed form the background and vice versa.
  80 #
  81 #   3.  Some entries in the foreground and background tables have keys that
  82 #       begin with an L-digit number but are followed by additional characters.
  83 #       For each such entry there is a corresponding entry in the long key
  84 #       table.  The long key table entry has a key which is just the L-digit
  85 #       number and data which is the length of the key in the foreground and
  86 #       background tables.
  87 #
  88 #   4.  The data for both foreground and background entries is usually a
  89 #       short string.  But some entries have long data strings.  For each
  90 #       such entries there is an entry in the long data type.  The key to
  91 #       long data table is an L-digit number.  (The extension on long keys
  92 #       is omitted.)  The data is the number of charaters in the data of the
  93 #       foreground or background entry.
  94 #
  95 # The following function builds a database that satisfies all of the above
  96 # invariants.
  97 #
  98 proc build_db {N L} {
  99   for {set i 2} {$i<=6} {incr i} {
 100     catch {btree_close_cursor [set ::c$i]}
 101     btree_clear_table $::b $i
 102     set ::c$i [btree_cursor $::b $i 1]
 103   }
 104   btree_insert $::c2 N $N
 105   btree_insert $::c2 L $L
 106   set format %0${L}d
 107   for {set i 1} {$i<=$N} {incr i} {
 108     set key [format $format $i]
 109     set data $key
 110     btree_insert $::c3 $key $data
 111   }
 112 }
 113
 114 # Given a base key number and a length, construct the full text of the key
 115 # or data.
 116 #
 117 proc make_payload {keynum L len} {
 118   set key [format %0${L}d $keynum]
 119   set r $key
 120   set i 1
 121   while {[string length $r]<$len} {
 122     append r " ($i) $key"
 123     incr i
 124   }
 125   return [string range $r 0 [expr {$len-1}]]
 126 }
 127
 128 # Verify the invariants on the database.  Return an empty string on
 129 # success or an error message if something is amiss.
 130 #
 131 proc check_invariants {} {
 132   set ck [btree_integrity_check $::b 1 2 3 4 5 6]
 133   if {$ck!=""} {
 134     puts "\n*** SANITY:\n$ck"
 135     exit
 136     return $ck
 137   }
 138   btree_move_to $::c3 {}
 139   btree_move_to $::c4 {}
 140   btree_move_to $::c2 N
 141   set N [btree_data $::c2]
 142   btree_move_to $::c2 L
 143   set L [btree_data $::c2]
 144   set LM1 [expr {$L-1}]
 145   for {set i 1} {$i<=$N} {incr i} {
 146     set key {}
 147     if {![btree_eof $::c3]} {
 148       set key [btree_key $::c3]
 149     }
 150     if {[scan $key %d k]<1} {set k 0}
 151     if {$k!=$i} {
 152       set key {}
 153       if {![btree_eof $::c4]} {
 154         set key [btree_key $::c4]
 155       }
 156       if {[scan $key %d k]<1} {set k 0}
 157       if {$k!=$i} {
 158         return "Key $i is missing from both foreground and background"
 159       }
 160       set data [btree_data $::c4]
 161       btree_next $::c4
 162     } else {
 163       set data [btree_data $::c3]
 164       btree_next $::c3
 165     }
 166     set skey [string range $key 0 $LM1]
 167     if {[btree_move_to $::c5 $skey]==0} {
 168       set keylen [btree_data $::c5]
 169     } else {
 170       set keylen $L
 171     }
 172     if {[string length $key]!=$keylen} {
 173       return "Key $i is the wrong size.\
 174               Is \"$key\" but should be \"[make_payload $k $L $keylen]\""
 175     }
 176     if {[make_payload $k $L $keylen]!=$key} {
 177       return "Key $i has an invalid extension"
 178     }
 179     if {[btree_move_to $::c6 $skey]==0} {
 180       set datalen [btree_data $::c6]
 181     } else {
 182       set datalen $L
 183     }
 184     if {[string length $data]!=$datalen} {
 185       return "Data for $i is the wrong size.\
 186               Is [string length $data] but should be $datalen"
 187     }
 188     if {[make_payload $k $L $datalen]!=$data} {
 189       return "Entry $i has an incorrect data"
 190     }
 191   }
 192 }
 193
 194 # Look at all elements in both the foreground and background tables.
 195 # Make sure the key is always the same as the prefix of the data.
 196 #
 197 # This routine was used for hunting bugs.  It is not a part of standard
 198 # tests.
 199 #
 200 proc check_data {n key} {
 201   global c3 c4
 202   incr n -1
 203   foreach c [list $c3 $c4] {
 204     btree_first $c  ;# move_to $c $key
 205     set cnt 0
 206     while {![btree_eof $c]} {
 207       set key [btree_key $c]
 208       set data [btree_data $c]
 209       if {[string range $key 0 $n] ne [string range $data 0 $n]} {
 210         puts "key=[list $key] data=[list $data] n=$n"
 211         puts "cursor info = [btree_cursor_info $c]"
 212         btree_page_dump $::b [lindex [btree_cursor_info $c] 0]
 213         exit
 214       }
 215       btree_next $c
 216     }
 217   }
 218 }
 219
 220 # Make random changes to the database such that each change preserves
 221 # the invariants.  The number of changes is $n*N where N is the parameter
 222 # from the descriptor table.  Each changes begins with a random key.
 223 # the entry with that key is put in the foreground table with probability
 224 # $I and it is put in background with probability (1.0-$I).  It gets
 225 # a long key with probability $K and long data with probability $D.
 226 #
 227 set chngcnt 0
 228 proc random_changes {n I K D} {
 229   global chngcnt
 230   btree_move_to $::c2 N
 231   set N [btree_data $::c2]
 232   btree_move_to $::c2 L
 233   set L [btree_data $::c2]
 234   set LM1 [expr {$L-1}]
 235   set total [expr {int($N*$n)}]
 236   set format %0${L}d
 237   for {set i 0} {$i<$total} {incr i} {
 238     set k [expr {int(rand()*$N)+1}]
 239     set insert [expr {rand()<=$I}]
 240     set longkey [expr {rand()<=$K}]
 241     set longdata [expr {rand()<=$D}]
 242     if {$longkey} {
 243       set x [expr {rand()}]
 244       set keylen [expr {int($x*$x*$x*$x*3000)+10}]
 245     } else {
 246       set keylen $L
 247     }
 248     set key [make_payload $k $L $keylen]
 249     if {$longdata} {
 250       set x [expr {rand()}]
 251       set datalen [expr {int($x*$x*$x*$x*3000)+10}]
 252     } else {
 253       set datalen $L
 254     }
 255     set data [make_payload $k $L $datalen]
 256     set basekey [format $format $k]
 257     if {[set c [btree_move_to $::c3 $basekey]]==0} {
 258       btree_delete $::c3
 259     } else {
 260       if {$c<0} {btree_next $::c3}
 261       if {![btree_eof $::c3]} {
 262         if {[string match $basekey* [btree_key $::c3]]} {
 263           btree_delete $::c3
 264         }
 265       }
 266     }
 267     if {[set c [btree_move_to $::c4 $basekey]]==0} {
 268       btree_delete $::c4
 269     } else {
 270       if {$c<0} {btree_next $::c4}
 271       if {![btree_eof $::c4]} {
 272         if {[string match $basekey* [btree_key $::c4]]} {
 273           btree_delete $::c4
 274         }
 275       }
 276     }
 277     set kx -1
 278     if {![btree_eof $::c4]} {
 279       if {[scan [btree_key $::c4] %d kx]<1} {set kx -1}
 280     }
 281     if {$kx==$k} {
 282       btree_delete $::c4
 283     }
 284     # For debugging - change the "0" to "1" to integrity check after
 285     # every change.
 286     if 0 {
 287       incr chngcnt
 288       puts check----$chngcnt
 289       set ck [btree_integrity_check $::b 1 2 3 4 5 6]
 290       if {$ck!=""} {
 291          puts "\nSANITY CHECK FAILED!\n$ck"
 292          exit
 293        }
 294     }
 295     if {$insert} {
 296       btree_insert $::c3 $key $data
 297     } else {
 298       btree_insert $::c4 $key $data
 299     }
 300     if {$longkey} {
 301       btree_insert $::c5 $basekey $keylen
 302     } elseif {[btree_move_to $::c5 $basekey]==0} {
 303       btree_delete $::c5
 304     }
 305     if {$longdata} {
 306       btree_insert $::c6 $basekey $datalen
 307     } elseif {[btree_move_to $::c6 $basekey]==0} {
 308       btree_delete $::c6
 309     }
 310     # For debugging - change the "0" to "1" to integrity check after
 311     # every change.
 312     if 0 {
 313       incr chngcnt
 314       puts check----$chngcnt
 315       set ck [btree_integrity_check $::b 1 2 3 4 5 6]
 316       if {$ck!=""} {
 317          puts "\nSANITY CHECK FAILED!\n$ck"
 318          exit
 319        }
 320     }
 321   }
 322 }
 323 set btree_trace 0
 324
 325 # Repeat this test sequence on database of various sizes
 326 #
 327 set testno 2
 328 foreach {N L} {
 329   10 2
 330   50 2
 331   200 3
 332   2000 5
 333 } {
 334   puts "**** N=$N L=$L ****"
 335   set hash [md5file test2.bt]
 336   do_test btree2-$testno.1 [subst -nocommands {
 337     set ::c2 [btree_cursor $::b 2 1]
 338     set ::c3 [btree_cursor $::b 3 1]
 339     set ::c4 [btree_cursor $::b 4 1]
 340     set ::c5 [btree_cursor $::b 5 1]
 341     set ::c6 [btree_cursor $::b 6 1]
 342     btree_begin_transaction $::b
 343     build_db $N $L
 344     check_invariants
 345   }] {}
 346   do_test btree2-$testno.2 {
 347     btree_close_cursor $::c2
 348     btree_close_cursor $::c3
 349     btree_close_cursor $::c4
 350     btree_close_cursor $::c5
 351     btree_close_cursor $::c6
 352     btree_rollback $::b
 353     md5file test2.bt
 354   } $hash
 355   do_test btree2-$testno.3 [subst -nocommands {
 356     btree_begin_transaction $::b
 357     set ::c2 [btree_cursor $::b 2 1]
 358     set ::c3 [btree_cursor $::b 3 1]
 359     set ::c4 [btree_cursor $::b 4 1]
 360     set ::c5 [btree_cursor $::b 5 1]
 361     set ::c6 [btree_cursor $::b 6 1]
 362     build_db $N $L
 363     check_invariants
 364   }] {}
 365   do_test btree2-$testno.4 {
 366     btree_commit $::b
 367     check_invariants
 368   } {}
 369   do_test btree2-$testno.5  {
 370     lindex [btree_pager_stats $::b] 1
 371   } {6}
 372   do_test btree2-$testno.6  {
 373     btree_close_cursor $::c2
 374     btree_close_cursor $::c3
 375     btree_close_cursor $::c4
 376     btree_close_cursor $::c5
 377     btree_close_cursor $::c6
 378     lindex [btree_pager_stats $::b] 1
 379   } {0}
 380   do_test btree2-$testno.7 {
 381     btree_close $::b
 382   } {}
 383
 384   # For each database size, run various changes tests.
 385   #
 386   set num2 1
 387   foreach {n I K D} {
 388     0.5 0.5 0.1 0.1
 389     1.0 0.2 0.1 0.1
 390     1.0 0.8 0.1 0.1
 391     2.0 0.0 0.1 0.1
 392     2.0 1.0 0.1 0.1
 393     2.0 0.0 0.0 0.0
 394     2.0 1.0 0.0 0.0
 395   } {
 396     set testid btree2-$testno.8.$num2
 397     set hash [md5file test2.bt]
 398     do_test $testid.0 {
 399       set ::b [btree_open test2.bt 2000 0]
 400       set ::c2 [btree_cursor $::b 2 1]
 401       set ::c3 [btree_cursor $::b 3 1]
 402       set ::c4 [btree_cursor $::b 4 1]
 403       set ::c5 [btree_cursor $::b 5 1]
 404       set ::c6 [btree_cursor $::b 6 1]
 405       check_invariants
 406     } {}
 407     set cnt 6
 408     for {set i 2} {$i<=6} {incr i} {
 409       if {[lindex [btree_cursor_info [set ::c$i]] 0]!=$i} {incr cnt}
 410     }
 411     do_test $testid.1 {
 412       btree_begin_transaction $::b
 413       lindex [btree_pager_stats $::b] 1
 414     } $cnt
 415     do_test $testid.2 [subst {
 416       random_changes $n $I $K $D
 417     }] {}
 418     do_test $testid.3 {
 419       check_invariants
 420     } {}
 421     do_test $testid.4 {
 422       btree_close_cursor $::c2
 423       btree_close_cursor $::c3
 424       btree_close_cursor $::c4
 425       btree_close_cursor $::c5
 426       btree_close_cursor $::c6
 427       btree_rollback $::b
 428       md5file test2.bt
 429     } $hash
 430     btree_begin_transaction $::b
 431     set ::c2 [btree_cursor $::b 2 1]
 432     set ::c3 [btree_cursor $::b 3 1]
 433     set ::c4 [btree_cursor $::b 4 1]
 434     set ::c5 [btree_cursor $::b 5 1]
 435     set ::c6 [btree_cursor $::b 6 1]
 436     do_test $testid.5 [subst {
 437       random_changes $n $I $K $D
 438     }] {}
 439     do_test $testid.6 {
 440       check_invariants
 441     } {}
 442     do_test $testid.7 {
 443       btree_commit $::b
 444       check_invariants
 445     } {}
 446     set hash [md5file test2.bt]
 447     do_test $testid.8 {
 448       btree_close_cursor $::c2
 449       btree_close_cursor $::c3
 450       btree_close_cursor $::c4
 451       btree_close_cursor $::c5
 452       btree_close_cursor $::c6
 453       lindex [btree_pager_stats $::b] 1
 454     } {0}
 455     do_test $testid.9 {
 456       btree_close $::b
 457       set ::b [btree_open test2.bt 2000 0]
 458       set ::c2 [btree_cursor $::b 2 1]
 459       set ::c3 [btree_cursor $::b 3 1]
 460       set ::c4 [btree_cursor $::b 4 1]
 461       set ::c5 [btree_cursor $::b 5 1]
 462       set ::c6 [btree_cursor $::b 6 1]
 463       check_invariants
 464     } {}
 465     do_test $testid.10 {
 466       btree_close_cursor $::c2
 467       btree_close_cursor $::c3
 468       btree_close_cursor $::c4
 469       btree_close_cursor $::c5
 470       btree_close_cursor $::c6
 471       lindex [btree_pager_stats $::b] 1
 472     } {0}
 473     do_test $testid.11 {
 474       btree_close $::b
 475     } {}
 476     incr num2
 477   }
 478   incr testno
 479   set ::b [btree_open test2.bt 2000 0]
 480 }
 481
 482 # Testing is complete.  Shut everything down.
 483 #
 484 do_test btree-999.1 {
 485   lindex [btree_pager_stats $::b] 1
 486 } {0}
 487 do_test btree-999.2 {
 488   btree_close $::b
 489 } {}
 490 do_test btree-999.3 {
 491   file delete -force test2.bt
 492   file exists test2.bt-journal
 493 } {0}
 494
 495 } ;# end if( not mem: and has pager_open command );
 496
 497 finish_test