Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Expanded documentation on test coverage. Added the "th3.html" page for describing the TH3 program. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
6bac79211300fa524c879e970460718b |
User & Date: | drh 2009-07-31 20:36:31.000 |
Context
2009-08-01
| ||
18:38 | Updates in preparation for version 3.6.17. (check-in: c5059a139a user: drh tags: trunk) | |
2009-07-31
| ||
20:36 | Expanded documentation on test coverage. Added the "th3.html" page for describing the TH3 program. (check-in: 6bac792113 user: drh tags: trunk) | |
2009-07-30
| ||
10:51 | Update documentation to talk about 100% test coverage in SQLite. (check-in: f7aa8bfebf user: drh tags: trunk) | |
Changes
Changes to pages/features.in.
︙ | ︙ | |||
23 24 25 26 27 28 29 | <li><a href="speed.html">Faster</a> than popular client/server database engines for most common operations.</li> <li>Simple, easy to use <a href="c3ref/intro.html">API</a>.</li> <li>Written in ANSI-C. <a href="tclsqlite.html">TCL bindings</a> included. Bindings for dozens of other languages <a href="http://www.sqlite.org/cvstrac/wiki?p=SqliteWrappers"> available separately.</a></li> | | > | 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | <li><a href="speed.html">Faster</a> than popular client/server database engines for most common operations.</li> <li>Simple, easy to use <a href="c3ref/intro.html">API</a>.</li> <li>Written in ANSI-C. <a href="tclsqlite.html">TCL bindings</a> included. Bindings for dozens of other languages <a href="http://www.sqlite.org/cvstrac/wiki?p=SqliteWrappers"> available separately.</a></li> <li>Well-commented source code with [test coverage |100% branch test coverage].</li> <li>Available as a <a href="amalgamation.html">single ANSI-C source-code file</a> that you can easily drop into another project. <li><a href="selfcontained.html">Self-contained</a>: no external dependencies.</li> <li>Cross-platform: Unix (Linux and Mac OS X), OS/2, and Windows (Win32 and WinCE) |
︙ | ︙ |
Changes to pages/testing.in.
︙ | ︙ | |||
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | By comparison, the project has <tcl> hd_puts "[expr {int($stat(totalSLOC)/$stat(coreSLOC))}] times as much" </tcl> test code and test scripts - <tcl>KB {$stat(totalSLOC)}</tcl> KSLOC.</p> <h2>2.0 Test Harnesses</h2> <p>There are three independent test harnesses used for testing the core SQLite library. Each test harness is designed, maintained, and managed separately from the others. </p> <ol> <li><p> | > | | | | | > > | | 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 | By comparison, the project has <tcl> hd_puts "[expr {int($stat(totalSLOC)/$stat(coreSLOC))}] times as much" </tcl> test code and test scripts - <tcl>KB {$stat(totalSLOC)}</tcl> KSLOC.</p> <tcl>hd_fragment {harnesses} {test harness} {three test harnesses}</tcl> <h2>2.0 Test Harnesses</h2> <p>There are three independent test harnesses used for testing the core SQLite library. Each test harness is designed, maintained, and managed separately from the others. </p> <ol> <li><p> The <b>TCL Tests</b> are the oldest set of tests for SQLite. The TCL tests are contained in the same source tree as the SQLite core and like the SQLite core are in the public domain. The TCL tests are the primary tests used during development. The TCL tests are written using the <a href="http://www.tcl.tk/">TCL scripting language</a>. The TCL test harness itself consists of <tcl>KB {$stat(tclcSLOC)}</tcl> KSLOC of C code used to create the TCL interface. The test scripts are contained in <tcl>N {$stat(tclsNFile)}</tcl> files totaling <tcl>MiB {$stat(tclsNByte)}</tcl>MB in size. There are <tcl>N {$stat(tclNTest)}</tcl> distinct test cases, but many of the test cases are parameterized and run multiple times (with different parameters) so that on a full test run, about <tcl>MB {$stat(tclNEval)}</tcl> million separate tests are performed. </p> </li> <li><p> The <b>TH3</b> test harness is a set of proprietary tests, written in C that provide 100% branch test coverage (and 100% MC/DC test coverage) to the core SQLite library. The TH3 tests are designed to run on embedded and specialized platforms that would not easily support TCL or other workstation services. TH3 tests use only the published SQLite interfaces. TH3 is free to [SQLite Consortium] members and is available by license to others. TH3 consists of about <tcl>MB {$stat(th3NByte)}</tcl> MB or <tcl>KB {$stat(th3SLOC)}</tcl> KSLOC of C code implementing <tcl>N {$stat(th3NTest)}</tcl> distinct test cases. TH3 tests are heavily parameterized, though, so a full test runs about <tcl>MB {$stat(th3NEval)}</tcl> million different test instances. Additional information on TH3 is [TH3 | available separately].</p></li> <li><p> <tcl>hd_fragment slt {SLT} {SQL Logic Tests}</tcl> The <b>SQL Logic Test</b> or SLT test harness is used to run huge numbers of SQL statements against both SQLite and several other SQL database engines and verify that they all get the same answers. SLT currently compares SQLite against PostgreSQL, MySQL, Microsoft SQL Server, and Oracle 10g. SLT runs <tcl>MB {$stat(sltNTest)}</tcl> million queries comprising <tcl>GB {$stat(sltsNByte)}</tcl>GB of test data. </p></li> </ol> <p>All of the tests above must run successfully, on multiple platforms and under multiple compile-time configurations, |
︙ | ︙ | |||
189 190 191 192 193 194 195 | <h3>3.1 Out-Of-Memory Testing</h3> <p>SQLite, like all SQL database engines, makes extensive use of malloc() (See the separate report on [memory allocation | dynamic memory allocation in SQLite] for additional detail.) | | | 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 | <h3>3.1 Out-Of-Memory Testing</h3> <p>SQLite, like all SQL database engines, makes extensive use of malloc() (See the separate report on [memory allocation | dynamic memory allocation in SQLite] for additional detail.) On servers and workstations, malloc() never fails in practice and so correct handling of out-of-memory (OOM) errors is not particularly important. But on embedded devices, OOM errors are frightenly common and since SQLite is frequently used on embedded devices, it is important that SQLite be able to gracefully handle OOM errors.</p> <p>OOM testing is accomplished by simulating OOM errors. SQLite allows an application to substitute an alternative malloc() |
︙ | ︙ | |||
287 288 289 290 291 292 293 294 295 296 297 298 299 300 | completed, the filesystem is reverted to the snapshot and random file damage is introduced that is characteristic of the kinds of damage one expects to see following a power loss. Then the database is opened and checks are made to ensure that it is well-formed and that the transaction either ran to completion or was completely rolled back. The interior of the loop is repeated multiple times for each snapshot with different random damage each time.</p> <h2>4.0 Fuzz Testing</h2> <p><a href="http://en.wikipedia.org/wiki/Fuzz_testing">Fuzz testing</a> seeks to establish that SQLite response correctly to invalid, out-of-range, or malformed inputs.</p> | > > > > > > > | 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 | completed, the filesystem is reverted to the snapshot and random file damage is introduced that is characteristic of the kinds of damage one expects to see following a power loss. Then the database is opened and checks are made to ensure that it is well-formed and that the transaction either ran to completion or was completely rolled back. The interior of the loop is repeated multiple times for each snapshot with different random damage each time.</p> <h3>3.3 Compound failure tests</h3> <p>The test suites for SQLite also explore the result of stacking multiple failures. For example, tests are run to insure correct behavior when an I/O error or OOM fault occurs while trying to recover from a prior crash. <h2>4.0 Fuzz Testing</h2> <p><a href="http://en.wikipedia.org/wiki/Fuzz_testing">Fuzz testing</a> seeks to establish that SQLite response correctly to invalid, out-of-range, or malformed inputs.</p> |
︙ | ︙ | |||
316 317 318 319 320 321 322 | <h3>4.2 Malformed Database Files</h3> <p>There are numerous test cases that verify that SQLite is able to deal with malformed database files. These tests first build a well-formed database file, then add corruption by changing one or more bytes in the file by some means other than SQLite. Then SQLite is used to read the database. | | | > | > | | 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 | <h3>4.2 Malformed Database Files</h3> <p>There are numerous test cases that verify that SQLite is able to deal with malformed database files. These tests first build a well-formed database file, then add corruption by changing one or more bytes in the file by some means other than SQLite. Then SQLite is used to read the database. In some cases, the bytes changes are in the middle of data. This causes the content of the databse to change while keeping the database well-formed. In other cases, unused bytes of the file are modified, which as no effect on the integrity of the database. The interesting cases are when bytes of the file that define database structure get changed. The malformed database tests verify that SQLite finds the file format errors and reports them using the SQLITE_CORRUPT return code without overflowing buffers, dereferencing NULL pointers, or performing other unwholesome actions.</p> <h3>4.3 Boundary Value Tests</h3> |
︙ | ︙ | |||
363 364 365 366 367 368 369 370 371 | No special configuration or setup is required. The test harnesses are especially vigilant with regard to memory leaks. If a change causes a memory leak, the test harnesses will recognize this quickly. SQLite is designed to never leak memory, even after an exception such as an OOM error or disk I/O error. The test harnesses are zealous to enforce this.</p> <h2>7.0 Test Coverage</h2> | > > > | > | | > > > > > | < > | < < | | < | | | < < < | 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 | No special configuration or setup is required. The test harnesses are especially vigilant with regard to memory leaks. If a change causes a memory leak, the test harnesses will recognize this quickly. SQLite is designed to never leak memory, even after an exception such as an OOM error or disk I/O error. The test harnesses are zealous to enforce this.</p> <tcl>hd_fragment coverage {test coverage}</tcl> <h2>7.0 Test Coverage</h2> <p>The SQLite core has 100% branch test coverage under [TH3] as of 2009-07-25, in its default configuration as measured by <a href="http://gcc.gnu.org/onlinedocs/gcc/Gcov.html">gcov</a> utility on SuSE Linux 10.1 on x86 hardware with the GCC 4.0.1 compiler.</p> <p>The "SQLite core" in the previous paragraph excludes the operating-system dependent [sqlite3_vfs | VFS] backends, since it is not possible to write cross-platform tests for those modules. Extensions such as FTS3 and RTree are also excluded from the analysis.</p> <h3>7.1 Statement versus branch coverage</h3> <p>There are many ways to measure test coverage. The most popular metric is "statement coverage". When you hear someone say that their program as "XX% test coverage" without further qualification, they usually mean statement coverage. Statement coverage measures what percentage of lines of code are executed at least once by the test suite.</p> <p>Branch coverage is more rigorous than statement coverage. Branch coverage measure the number of machine-code branch instructions that are evaluated at least once on both directions.</p> <p>To illustrate the difference between statement coverage and branch coverage, consider the following hypothetical line of C code:</p> <blockquote><pre> if( a>b && c!=25 ){ d++; } |
︙ | ︙ | |||
412 413 414 415 416 417 418 | <p><ul> <li> a<=b <li> a>b && c==25 <li> a>b && c!=25 </ul></p> | > > > > > | > > > > | | > > > > | 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 | <p><ul> <li> a<=b <li> a>b && c==25 <li> a>b && c!=25 </ul></p> <p>Any one of the above test cases would provide 100% statement coverage but all three are required for 100% branch coverage. Generally speaking, 100% branch coverage implies 100% statement coverage, but the converse is not true. To reemphasize, the [TH3] test harness for SQLite provides the stronger form of test coverage - 100% branch test coverage.</p> <h3>7.2 Coverage testing of defensive code</h3> <p>A well-written C program will typically contain some defensive tests which in practice are always true or always false. This leads to a programming delimma: Does one remove defensive code in order to obtain 100% branch coverage?</p> <p>In SQLite, the answer to the previous question is "no". For testing purposes, the SQLite source code defines macros called ALWAYS() and NEVER(). The ALWAYS() macro surrounds conditions which are expected to always evaluated to true and NEVER() surrounds conditions that are always evaluate to false. These macros serve as comments to indicate that the conditions are defensive code. For standard builds, these macros are pass-throughs:</p> |
︙ | ︙ | |||
440 441 442 443 444 445 446 | #define ALWAYS(X) ((X)?1:assert(0),0) #define NEVER(X) ((X)?assert(0),1:0) </pre></blockquote> <p>When measuring test coverage, these macros are defined to be constant truth values so that they do not generate assembly language branch instructions, and hence do not come into play when calculating the | | > > > > > > > > > | 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 | #define ALWAYS(X) ((X)?1:assert(0),0) #define NEVER(X) ((X)?assert(0),1:0) </pre></blockquote> <p>When measuring test coverage, these macros are defined to be constant truth values so that they do not generate assembly language branch instructions, and hence do not come into play when calculating the branch coverage:</p> <blockquote><pre> #define ALWAYS(X) (1) #define NEVER(X) (0) </pre></blockquote> <p>The test suite is designed to be run three times, once for each of the ALWAYS() and NEVER() definitions shown above. All three test runs should yield exactly the same result. There is a run-time test using the [sqlite3_test_control]([SQLITE_TESTCTRL_ALWAYS], ...) interface that can be used to verify that the macros are correctly set to the first form (the pass-through form) for deployment.</p> <h3>7.3 Forcing coverage of boundary values and boolean vector tests</h3> <p>Another macro used in conjuction with test coverage measurement is the <tt>testcase()</tt> macro. The argument is a condition for which we want test cases that evaluate to both true and false. In non-coverage builds (that is to so, in release builds) the testcase() macro is a no-op:</p> <blockquote><pre> |
︙ | ︙ | |||
499 500 501 502 503 504 505 | <blockquote><pre> testcase( mask & SQLITE_OPEN_MAIN_DB ); testcase( mask & SQLITE_OPEN_TEMP_DB ); if( (mask & (SQLITE_OPEN_MAIN_DB|SQLITE_OPEN_TEMP_DB))!=0 ){ ... } </pre></blockquote> | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | > | | | | | 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 | <blockquote><pre> testcase( mask & SQLITE_OPEN_MAIN_DB ); testcase( mask & SQLITE_OPEN_TEMP_DB ); if( (mask & (SQLITE_OPEN_MAIN_DB|SQLITE_OPEN_TEMP_DB))!=0 ){ ... } </pre></blockquote> <tcl>hd_fragment {mcdc} {MC/DC}</tcl> <h3>7.4 Branch coverage versus MC/DC</h3> <p>Two methods of measuring test coverage were described above: "statement" and "branch" coverage. There are many other test coverage metrics besides these two. Another popular metric is "Modified Condition/Decision Coverage" or MC/DC. <a href="http://en.wikipedia.org/wiki/Modified_Condition/Decision_Coverage"> Wikipedia</a> defines MC/DC as follows:</p> <ul> <li> Each decision tries every possible outcome. <li> Each condition in a decision takes on every possible outcome. <li> Each entry and exit point is invoked. <li> Each condition in a decision is shown to independently affect the outcome of the decision. </ul> <p>In the C programming langauge where the <tt>&&</tt> and <tt>||</tt> operator are "short-circuit" operators, MC/DC and branch coverage are very nearly the same thing. The primary difference is in boolean vector tests. One can test for any of several bits in bit-vector and still obtain 100% branch test coverage even though the second element of MC/DC - the requirement that each condition in a decision take on every possible outcome - might not be satisfied.</p> <p>SQLite uses <tt>testcase()</tt> macros as described in the previous subsection to make sure that every condition in a bit-vector decision takes on every possible outcome. In this way, SQLite also achieves 100% MC/DC in addition to 100% branch coverage.</p> <h3>7.5 Experience with full test coverage</h3> <p>The developers of SQLite have found that full coverage testing is an extremely productive method for preventing the introduction of new bugs as the system evolves. Because every single branch insteruction in SQLite core code is covered by test cases, the developers can be confident that changes they make in one part of the code do not have unintended consequences in other parts of the code. It would extremely difficult maintain the quality of SQLite without such assurances.</p> <h2>8.0 Dynamic Analysis</h2> <p>Dynamic analysis refers to internal and external checks on the SQLite code which are performed while the code is live and running. Dynamic analysis has proven to be a great help in maintaining the quality of SQLite.</p> |
︙ | ︙ |
Added pages/th3.in.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | <title>SQLite TH3</title> <tcl>hd_keywords {TH3}</tcl> <h1 align="center">TH3: SQLite Test Harness #3</h1> <h2>1.0 Overview</h2> <p>SQLite Test Harness #3 (hereafter "TH3") is one of [three test harnesses] used for testing SQLite. TH3 is designed to meet the following objectives:</p> <ul> <li><p> TH3 will work on embedded platforms that lack the support infrastructure of workstations.</p></li> <li><p> TH3 will test SQLite in an as-delivered configuration, without the need to enable special test hooks in the core SQLite library. </p></li> <li><p> TH3 will test SQLite's response to out-of-memory errors, disk I/O errors, and power loss during transaction commit. </p></li> <li><p> TH3 will test SQLite in a variety of configurations (UTF8 vs UTF16, different pages sizes, varying journal modes, etc.) </p></li> <li><p> TH3 will achieve 100% MC/DC test coverage. </p></li> </ul> <p>TH3 is intended for validation testing. Though it could be used for testing during development and debugging, TH3 is not designed for that purpose. The original TCL-based test suite for SQLite will continue to serve as the primary platform for development and debug testing. The reason that TH3 exists is that it meets other objectives that are difficult to achieve with the TCL-based tests.</p> <h2>2.0 Operation</h3> <p>TH3 is a test program generator. The output of TH3 is a program written in ANSI-C and intended to be linked against the SQLite library under test. The generated test program is compiled and run on the target platform in order to verify correct operation of SQLite on that platform.</p> <p>The inputs to TH3 are test modules written in C or SQL and small configuration files that determine how to initialize SQLite. The TH3 package eventually will include hundreds of test modules and dozens of configuration files. New modules and configurations can be added to customize TH3 for specialized applications. Each time TH3 is run, it reads a subset of the available test modules and configuration files to generate a custom C program the performs all of the specified tests under all configurations. A complete test of SQLite normally involves running TH3 multiple times to generate multiple test programs covering different aspects of SQLite's operation, then linking all test programs against a common SQLite library and running them separately on the target platform. SQLite will be found to work if all test programs pass.</p> <p>There are no arbitrary limits in TH3. One could generate a single test program that contained all test modules and configuration files. However, such a test program might be too large to deploy on embedded platforms. Hence, TH3 provides the ability to break the library of test modules up into smaller, more easily digested pieces.</p> <p>Each individual test module might contain dozens, hundreds, or thousands of separate tests. The test modules can be written in C or as scripts of SQL. Test modules done SQL are very easy to write and the test modules written in C are not as nearly as cumbersome to write as one might suppose. The TH3 system provides high-level interfaces that simplify test writing. A typical C-language test case in TH3 might contains slightly more syntax that the corresponding TCL-script test, but the difference is not that great. The test modules written as SQL contain special comments that define the boundaries and operation of each test case and the expected results.</p> <p>Each test module file contains a header which describes the circumstances under which the test is valid. For a particular configuration, only those modules that are compatible with the configuration are run. </p> <h2>3.0 Generating A Test Program</h2> <p>The TH3 program generator is a TCL script named "<tt>mkth3.tcl</tt>". To generate a test program, one has merely to run this script and supply the names of files containing test modules and configurations on the command line. TH3 does not force any specific names for test modules or configuration files, but it is customary to use suffixes "<tt>.test</tt>" and "<tt>.cfg</tt>". With these conventions, one might generate a test program as follows:</p> <blockquote><pre> tclsh mkth3.tcl *.test *.cfg >testprog1.c </pre></blockquote> <p>The output from the mkth3.tcl script is a C program that contains everything needed to run the tests - everything that is except for the SQLite library itself. The generated test program contains implementations for all of the support interfaces used by the test modules and it contains the <tt>main()</tt> routine that drives the tests. To convert the test program into a working executable, simply compile it against SQLite:</p> <blockquote><pre> cc -o testprog1 testprog1.c sqlite3.c </pre></blockquote> <p>The compilation step shown immediately above is merely representative. In a working installation, one would normally want to specify optimization parameters and compile-time switches on the compiler command line.</p> <p>Once the test program is generated, it is run with no arguments to perform the tests. Progress information as well as error diagnostics appear on standard output. The program returns zero if there are no errors and non-zero if any problems were detected.</p> <h2>4.0 Test Coverage</h2> <p>Using one particular subset of the available TH3 test modules (the "cov1" tests) SQLite obtained [test coverage | 100% branch test coverage] and 100% [MC/DC] as measured by <a href="http://gcc.gnu.org/onlinedocs/gcc/Gcov.html">gcov</a> on SuSE Linux 10.1 on x86 hardware on 2009-07-25. The SQLite developers are committed to maintaining 100% branch coverage and MC/DC for all future releases of SQLite.</p> <p>The cov1 test set used to obtain 100% branch test coverage are only a subset of the tests currently implemented using TH3. New test modules are added on a regular basis.</p> <h2>5.0 TH3 License</h2> <p>SQLite itself is in the <a href="copyright.html">public domain</a> and can be used for any purpose. But TH3 is proprietary and requires a license. Members of the [SQLite Consortium] get free and unlimited access to TH3. Others can contact the SQLite developers for information on how to obtain a license to access and use TH3.</p> <p>Licensees of TH3 are given read access to the software configuration management system used to manage TH3 and so can download the latest version of TH3 (or any historical version) whenever they like.</p> <p>Even though open-source users do not have direct access to TH3, all users of SQLite benefit from TH3 indirectly since version of SQLite is validated by TH3 prior to release. So anyone using an official release of SQLite can deploy their application with the confidence of knowing that it has been tested using TH3. They simply cannot rerun those tests themselves without purchasing a TH3 license.</p> |