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