| blob | 45c0203a52273b45c8a6208d6ee39671567bf06a |
2 #pragma ident "%Z%%M% %I% %E% SMI"
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 $
20 set testdir [file dirname $argv0]
21 source $testdir/tester.tcl
23 if {[info commands btree_open]!=""} {
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 #
36 do_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}
44 do_test btree2-1.2 {
45 btree_create_table $::b
46 } {4}
47 do_test btree2-1.3 {
48 btree_create_table $::b
49 } {5}
50 do_test btree2-1.4 {
51 btree_create_table $::b
52 } {6}
53 do_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 } {}
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 #
97 proc 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 }
113 # Given a base key number and a length, construct the full text of the key
114 # or data.
115 #
116 proc 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 }
127 # Verify the invariants on the database. Return an empty string on
128 # success or an error message if something is amiss.
129 #
130 proc 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 }
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 #
198 set chngcnt 0
199 proc 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 }
275 # Repeat this test sequence on database of various sizes
276 #
277 set testno 2
278 foreach {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 } {}
333 after 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 }
434 # Testing is complete. Shut everything down.
435 #
436 do_test btree-999.1 {
437 lindex [btree_pager_stats $::b] 1
438 } {0}
439 do_test btree-999.2 {
440 btree_close $::b
441 } {}
442 do_test btree-999.3 {
443 file delete -force test2.bt
444 file exists test2.bt-journal
445 } {0}
447 } ;# end if( not mem: and has pager_open command );
449 finish_test