ext/repair/checkfreelist.c

   1 /*
   2 ** 2017 October 11
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 **
  13 ** This module exports a single C function:
  14 **
  15 **   int sqlite3_check_freelist(sqlite3 *db, const char *zDb);
  16 **
  17 ** This function checks the free-list in database zDb (one of "main",
  18 ** "temp", etc.) and reports any errors by invoking the sqlite3_log()
  19 ** function. It returns SQLITE_OK if successful, or an SQLite error
  20 ** code otherwise. It is not an error if the free-list is corrupted but
  21 ** no IO or OOM errors occur.
  22 **
  23 ** If this file is compiled and loaded as an SQLite loadable extension,
  24 ** it adds an SQL function "checkfreelist" to the database handle, to
  25 ** be invoked as follows:
  26 **
  27 **   SELECT checkfreelist(<database-name>);
  28 **
  29 ** This function performs the same checks as sqlite3_check_freelist(),
  30 ** except that it returns all error messages as a single text value,
  31 ** separated by newline characters. If the freelist is not corrupted
  32 ** in any way, an empty string is returned.
  33 **
  34 ** To compile this module for use as an SQLite loadable extension:
  35 **
  36 **   gcc -Os -fPIC -shared checkfreelist.c -o checkfreelist.so
  37 */
  38
  39 #include "sqlite3ext.h"
  40 SQLITE_EXTENSION_INIT1
  41
  42 #ifndef SQLITE_AMALGAMATION
  43 # include <string.h>
  44 # include <stdio.h>
  45 # include <stdlib.h>
  46 # include <assert.h>
  47 # if defined(SQLITE_COVERAGE_TEST) || defined(SQLITE_MUTATION_TEST)
  48 #   define SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS 1
  49 # endif
  50 # if defined(SQLITE_OMIT_AUXILIARY_SAFETY_CHECKS)
  51 #   define ALWAYS(X)      (1)
  52 #   define NEVER(X)       (0)
  53 # elif !defined(NDEBUG)
  54 #   define ALWAYS(X)      ((X)?1:(assert(0),0))
  55 #   define NEVER(X)       ((X)?(assert(0),1):0)
  56 # else
  57 #   define ALWAYS(X)      (X)
  58 #   define NEVER(X)       (X)
  59 # endif
  60   typedef unsigned char u8;
  61   typedef unsigned short u16;
  62   typedef unsigned int u32;
  63 #define get4byte(x) (        \
  64     ((u32)((x)[0])<<24) +    \
  65     ((u32)((x)[1])<<16) +    \
  66     ((u32)((x)[2])<<8) +     \
  67     ((u32)((x)[3]))          \
  68 )
  69 #endif
  70
  71 /*
  72 ** Execute a single PRAGMA statement and return the integer value returned
  73 ** via output parameter (*pnOut).
  74 **
  75 ** The SQL statement passed as the third argument should be a printf-style
  76 ** format string containing a single "%s" which will be replace by the
  77 ** value passed as the second argument. e.g.
  78 **
  79 **   sqlGetInteger(db, "main", "PRAGMA %s.page_count", pnOut)
  80 **
  81 ** executes "PRAGMA main.page_count" and stores the results in (*pnOut).
  82 */
  83 static int sqlGetInteger(
  84   sqlite3 *db,                    /* Database handle */
  85   const char *zDb,                /* Database name ("main", "temp" etc.) */
  86   const char *zFmt,               /* SQL statement format */
  87   u32 *pnOut                      /* OUT: Integer value */
  88 ){
  89   int rc, rc2;
  90   char *zSql;
  91   sqlite3_stmt *pStmt = 0;
  92   int bOk = 0;
  93
  94   zSql = sqlite3_mprintf(zFmt, zDb);
  95   if( zSql==0 ){
  96     rc = SQLITE_NOMEM;
  97   }else{
  98     rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
  99     sqlite3_free(zSql);
 100   }
 101
 102   if( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
 103     *pnOut = (u32)sqlite3_column_int(pStmt, 0);
 104     bOk = 1;
 105   }
 106
 107   rc2 = sqlite3_finalize(pStmt);
 108   if( rc==SQLITE_OK ) rc = rc2;
 109   if( rc==SQLITE_OK && bOk==0 ) rc = SQLITE_ERROR;
 110   return rc;
 111 }
 112
 113 /*
 114 ** Argument zFmt must be a printf-style format string and must be
 115 ** followed by its required arguments. If argument pzOut is NULL,
 116 ** then the results of printf()ing the format string are passed to
 117 ** sqlite3_log(). Otherwise, they are appended to the string
 118 ** at (*pzOut).
 119 */
 120 static int checkFreelistError(char **pzOut, const char *zFmt, ...){
 121   int rc = SQLITE_OK;
 122   char *zErr = 0;
 123   va_list ap;
 124
 125   va_start(ap, zFmt);
 126   zErr = sqlite3_vmprintf(zFmt, ap);
 127   if( zErr==0 ){
 128     rc = SQLITE_NOMEM;
 129   }else{
 130     if( pzOut ){
 131       *pzOut = sqlite3_mprintf("%s%z%s", *pzOut?"\n":"", *pzOut, zErr);
 132       if( *pzOut==0 ) rc = SQLITE_NOMEM;
 133     }else{
 134       sqlite3_log(SQLITE_ERROR, "checkfreelist: %s", zErr);
 135     }
 136     sqlite3_free(zErr);
 137   }
 138   va_end(ap);
 139   return rc;
 140 }
 141
 142 static int checkFreelist(
 143   sqlite3 *db,
 144   const char *zDb,
 145   char **pzOut
 146 ){
 147   /* This query returns one row for each page on the free list. Each row has
 148   ** two columns - the page number and page content.  */
 149   const char *zTrunk =
 150     "WITH freelist_trunk(i, d, n) AS ("
 151       "SELECT 1, NULL, sqlite_readint32(data, 32) "
 152       "FROM sqlite_dbpage(:1) WHERE pgno=1 "
 153         "UNION ALL "
 154       "SELECT n, data, sqlite_readint32(data) "
 155       "FROM freelist_trunk, sqlite_dbpage(:1) WHERE pgno=n "
 156     ")"
 157     "SELECT i, d FROM freelist_trunk WHERE i!=1;";
 158
 159   int rc, rc2;                    /* Return code */
 160   sqlite3_stmt *pTrunk = 0;       /* Compilation of zTrunk */
 161   u32 nPage = 0;                  /* Number of pages in db */
 162   u32 nExpected = 0;              /* Expected number of free pages */
 163   u32 nFree = 0;                  /* Number of pages on free list */
 164
 165   if( zDb==0 ) zDb = "main";
 166
 167   if( (rc = sqlGetInteger(db, zDb, "PRAGMA %s.page_count", &nPage))
 168    || (rc = sqlGetInteger(db, zDb, "PRAGMA %s.freelist_count", &nExpected))
 169   ){
 170     return rc;
 171   }
 172
 173   rc = sqlite3_prepare_v2(db, zTrunk, -1, &pTrunk, 0);
 174   if( rc!=SQLITE_OK ) return rc;
 175   sqlite3_bind_text(pTrunk, 1, zDb, -1, SQLITE_STATIC);
 176   while( rc==SQLITE_OK && sqlite3_step(pTrunk)==SQLITE_ROW ){
 177     u32 i;
 178     u32 iTrunk = (u32)sqlite3_column_int(pTrunk, 0);
 179     const u8 *aData = (const u8*)sqlite3_column_blob(pTrunk, 1);
 180     u32 nData = (u32)sqlite3_column_bytes(pTrunk, 1);
 181     u32 iNext = get4byte(&aData[0]);
 182     u32 nLeaf = get4byte(&aData[4]);
 183
 184     if( nLeaf>((nData/4)-2-6) ){
 185       rc = checkFreelistError(pzOut,
 186           "leaf count out of range (%d) on trunk page %d",
 187           (int)nLeaf, (int)iTrunk
 188       );
 189       nLeaf = (nData/4) - 2 - 6;
 190     }
 191
 192     nFree += 1+nLeaf;
 193     if( iNext>nPage ){
 194       rc = checkFreelistError(pzOut,
 195           "trunk page %d is out of range", (int)iNext
 196       );
 197     }
 198
 199     for(i=0; rc==SQLITE_OK && i<nLeaf; i++){
 200       u32 iLeaf = get4byte(&aData[8 + 4*i]);
 201       if( iLeaf==0 || iLeaf>nPage ){
 202         rc = checkFreelistError(pzOut,
 203             "leaf page %d is out of range (child %d of trunk page %d)",
 204             (int)iLeaf, (int)i, (int)iTrunk
 205         );
 206       }
 207     }
 208   }
 209
 210   if( rc==SQLITE_OK && nFree!=nExpected ){
 211     rc = checkFreelistError(pzOut,
 212         "free-list count mismatch: actual=%d header=%d",
 213         (int)nFree, (int)nExpected
 214     );
 215   }
 216
 217   rc2 = sqlite3_finalize(pTrunk);
 218   if( rc==SQLITE_OK ) rc = rc2;
 219   return rc;
 220 }
 221
 222 int sqlite3_check_freelist(sqlite3 *db, const char *zDb){
 223   return checkFreelist(db, zDb, 0);
 224 }
 225
 226 static void checkfreelist_function(
 227   sqlite3_context *pCtx,
 228   int nArg,
 229   sqlite3_value **apArg
 230 ){
 231   const char *zDb;
 232   int rc;
 233   char *zOut = 0;
 234   sqlite3 *db = sqlite3_context_db_handle(pCtx);
 235
 236   assert( nArg==1 );
 237   zDb = (const char*)sqlite3_value_text(apArg[0]);
 238   rc = checkFreelist(db, zDb, &zOut);
 239   if( rc==SQLITE_OK ){
 240     sqlite3_result_text(pCtx, zOut?zOut:"ok", -1, SQLITE_TRANSIENT);
 241   }else{
 242     sqlite3_result_error_code(pCtx, rc);
 243   }
 244
 245   sqlite3_free(zOut);
 246 }
 247
 248 /*
 249 ** An SQL function invoked as follows:
 250 **
 251 **   sqlite_readint32(BLOB)           -- Decode 32-bit integer from start of blob
 252 */
 253 static void readint_function(
 254   sqlite3_context *pCtx,
 255   int nArg,
 256   sqlite3_value **apArg
 257 ){
 258   const u8 *zBlob;
 259   int nBlob;
 260   int iOff = 0;
 261   u32 iRet = 0;
 262
 263   if( nArg!=1 && nArg!=2 ){
 264     sqlite3_result_error(
 265         pCtx, "wrong number of arguments to function sqlite_readint32()", -1
 266     );
 267     return;
 268   }
 269   if( nArg==2 ){
 270     iOff = sqlite3_value_int(apArg[1]);
 271   }
 272
 273   zBlob = sqlite3_value_blob(apArg[0]);
 274   nBlob = sqlite3_value_bytes(apArg[0]);
 275
 276   if( nBlob>=(iOff+4) ){
 277     iRet = get4byte(&zBlob[iOff]);
 278   }
 279
 280   sqlite3_result_int64(pCtx, (sqlite3_int64)iRet);
 281 }
 282
 283 /*
 284 ** Register the SQL functions.
 285 */
 286 static int cflRegister(sqlite3 *db){
 287   int rc = sqlite3_create_function(
 288       db, "sqlite_readint32", -1, SQLITE_UTF8, 0, readint_function, 0, 0
 289   );
 290   if( rc!=SQLITE_OK ) return rc;
 291   rc = sqlite3_create_function(
 292       db, "checkfreelist", 1, SQLITE_UTF8, 0, checkfreelist_function, 0, 0
 293   );
 294   return rc;
 295 }
 296
 297 /*
 298 ** Extension load function.
 299 */
 300 #ifdef _WIN32
 301 __declspec(dllexport)
 302 #endif
 303 int sqlite3_checkfreelist_init(
 304   sqlite3 *db,
 305   char **pzErrMsg,
 306   const sqlite3_api_routines *pApi
 307 ){
 308   SQLITE_EXTENSION_INIT2(pApi);
 309   return cflRegister(db);
 310 }