Enhance the command-line completion extension to return the names of
[sqlite.git] / ext / misc / scrub.c
blob4eb56b0fc275e5c234ab37ca9fa78b86bb68f3f5
1 /*
2 ** 2016-05-05
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.
11 ******************************************************************************
13 ** This file implements a utility function (and a utility program) that
14 ** makes a copy of an SQLite database while simultaneously zeroing out all
15 ** deleted content.
17 ** Normally (when PRAGMA secure_delete=OFF, which is the default) when SQLite
18 ** deletes content, it does not overwrite the deleted content but rather marks
19 ** the region of the file that held that content as being reusable. This can
20 ** cause deleted content to recoverable from the database file. This stale
21 ** content is removed by the VACUUM command, but VACUUM can be expensive for
22 ** large databases. When in PRAGMA secure_delete=ON mode, the deleted content
23 ** is zeroed, but secure_delete=ON has overhead as well.
25 ** This utility attempts to make a copy of a complete SQLite database where
26 ** all of the deleted content is zeroed out in the copy, and it attempts to
27 ** do so while being faster than running VACUUM.
29 ** Usage:
31 ** int sqlite3_scrub_backup(
32 ** const char *zSourceFile, // Source database filename
33 ** const char *zDestFile, // Destination database filename
34 ** char **pzErrMsg // Write error message here
35 ** );
37 ** Simply call the API above specifying the filename of the source database
38 ** and the name of the backup copy. The source database must already exist
39 ** and can be in active use. (A read lock is held during the backup.) The
40 ** destination file should not previously exist. If the pzErrMsg parameter
41 ** is non-NULL and if an error occurs, then an error message might be written
42 ** into memory obtained from sqlite3_malloc() and *pzErrMsg made to point to
43 ** that error message. But if the error is an OOM, the error might not be
44 ** reported. The routine always returns non-zero if there is an error.
46 ** If compiled with -DSCRUB_STANDALONE then a main() procedure is added and
47 ** this file becomes a standalone program that can be run as follows:
49 ** ./sqlite3scrub SOURCE DEST
51 #include "sqlite3.h"
52 #include <assert.h>
53 #include <stdio.h>
54 #include <stdlib.h>
55 #include <stdarg.h>
56 #include <string.h>
58 typedef struct ScrubState ScrubState;
59 typedef unsigned char u8;
60 typedef unsigned short u16;
61 typedef unsigned int u32;
64 /* State information for a scrub-and-backup operation */
65 struct ScrubState {
66 const char *zSrcFile; /* Name of the source file */
67 const char *zDestFile; /* Name of the destination file */
68 int rcErr; /* Error code */
69 char *zErr; /* Error message text */
70 sqlite3 *dbSrc; /* Source database connection */
71 sqlite3_file *pSrc; /* Source file handle */
72 sqlite3 *dbDest; /* Destination database connection */
73 sqlite3_file *pDest; /* Destination file handle */
74 u32 szPage; /* Page size */
75 u32 szUsable; /* Usable bytes on each page */
76 u32 nPage; /* Number of pages */
77 u32 iLastPage; /* Page number of last page written so far*/
78 u8 *page1; /* Content of page 1 */
81 /* Store an error message */
82 static void scrubBackupErr(ScrubState *p, const char *zFormat, ...){
83 va_list ap;
84 sqlite3_free(p->zErr);
85 va_start(ap, zFormat);
86 p->zErr = sqlite3_vmprintf(zFormat, ap);
87 va_end(ap);
88 if( p->rcErr==0 ) p->rcErr = SQLITE_ERROR;
91 /* Allocate memory to hold a single page of content */
92 static u8 *scrubBackupAllocPage(ScrubState *p){
93 u8 *pPage;
94 if( p->rcErr ) return 0;
95 pPage = sqlite3_malloc( p->szPage );
96 if( pPage==0 ) p->rcErr = SQLITE_NOMEM;
97 return pPage;
100 /* Read a page from the source database into memory. Use the memory
101 ** provided by pBuf if not NULL or allocate a new page if pBuf==NULL.
103 static u8 *scrubBackupRead(ScrubState *p, int pgno, u8 *pBuf){
104 int rc;
105 sqlite3_int64 iOff;
106 u8 *pOut = pBuf;
107 if( p->rcErr ) return 0;
108 if( pOut==0 ){
109 pOut = scrubBackupAllocPage(p);
110 if( pOut==0 ) return 0;
112 iOff = (pgno-1)*(sqlite3_int64)p->szPage;
113 rc = p->pSrc->pMethods->xRead(p->pSrc, pOut, p->szPage, iOff);
114 if( rc!=SQLITE_OK ){
115 if( pBuf==0 ) sqlite3_free(pOut);
116 pOut = 0;
117 scrubBackupErr(p, "read failed for page %d", pgno);
118 p->rcErr = SQLITE_IOERR;
120 return pOut;
123 /* Write a page to the destination database */
124 static void scrubBackupWrite(ScrubState *p, int pgno, const u8 *pData){
125 int rc;
126 sqlite3_int64 iOff;
127 if( p->rcErr ) return;
128 iOff = (pgno-1)*(sqlite3_int64)p->szPage;
129 rc = p->pDest->pMethods->xWrite(p->pDest, pData, p->szPage, iOff);
130 if( rc!=SQLITE_OK ){
131 scrubBackupErr(p, "write failed for page %d", pgno);
132 p->rcErr = SQLITE_IOERR;
134 if( (u32)pgno>p->iLastPage ) p->iLastPage = pgno;
137 /* Prepare a statement against the "db" database. */
138 static sqlite3_stmt *scrubBackupPrepare(
139 ScrubState *p, /* Backup context */
140 sqlite3 *db, /* Database to prepare against */
141 const char *zSql /* SQL statement */
143 sqlite3_stmt *pStmt;
144 if( p->rcErr ) return 0;
145 p->rcErr = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
146 if( p->rcErr ){
147 scrubBackupErr(p, "SQL error \"%s\" on \"%s\"",
148 sqlite3_errmsg(db), zSql);
149 sqlite3_finalize(pStmt);
150 return 0;
152 return pStmt;
156 /* Open the source database file */
157 static void scrubBackupOpenSrc(ScrubState *p){
158 sqlite3_stmt *pStmt;
159 int rc;
160 /* Open the source database file */
161 p->rcErr = sqlite3_open_v2(p->zSrcFile, &p->dbSrc,
162 SQLITE_OPEN_READWRITE |
163 SQLITE_OPEN_URI | SQLITE_OPEN_PRIVATECACHE, 0);
164 if( p->rcErr ){
165 scrubBackupErr(p, "cannot open source database: %s",
166 sqlite3_errmsg(p->dbSrc));
167 return;
169 p->rcErr = sqlite3_exec(p->dbSrc, "SELECT 1 FROM sqlite_master; BEGIN;",
170 0, 0, 0);
171 if( p->rcErr ){
172 scrubBackupErr(p,
173 "cannot start a read transaction on the source database: %s",
174 sqlite3_errmsg(p->dbSrc));
175 return;
177 rc = sqlite3_wal_checkpoint_v2(p->dbSrc, "main", SQLITE_CHECKPOINT_FULL,
178 0, 0);
179 if( rc ){
180 scrubBackupErr(p, "cannot checkpoint the source database");
181 return;
183 pStmt = scrubBackupPrepare(p, p->dbSrc, "PRAGMA page_size");
184 if( pStmt==0 ) return;
185 rc = sqlite3_step(pStmt);
186 if( rc==SQLITE_ROW ){
187 p->szPage = sqlite3_column_int(pStmt, 0);
188 }else{
189 scrubBackupErr(p, "unable to determine the page size");
191 sqlite3_finalize(pStmt);
192 if( p->rcErr ) return;
193 pStmt = scrubBackupPrepare(p, p->dbSrc, "PRAGMA page_count");
194 if( pStmt==0 ) return;
195 rc = sqlite3_step(pStmt);
196 if( rc==SQLITE_ROW ){
197 p->nPage = sqlite3_column_int(pStmt, 0);
198 }else{
199 scrubBackupErr(p, "unable to determine the size of the source database");
201 sqlite3_finalize(pStmt);
202 sqlite3_file_control(p->dbSrc, "main", SQLITE_FCNTL_FILE_POINTER, &p->pSrc);
203 if( p->pSrc==0 || p->pSrc->pMethods==0 ){
204 scrubBackupErr(p, "cannot get the source file handle");
205 p->rcErr = SQLITE_ERROR;
209 /* Create and open the destination file */
210 static void scrubBackupOpenDest(ScrubState *p){
211 sqlite3_stmt *pStmt;
212 int rc;
213 char *zSql;
214 if( p->rcErr ) return;
215 p->rcErr = sqlite3_open_v2(p->zDestFile, &p->dbDest,
216 SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE |
217 SQLITE_OPEN_URI | SQLITE_OPEN_PRIVATECACHE, 0);
218 if( p->rcErr ){
219 scrubBackupErr(p, "cannot open destination database: %s",
220 sqlite3_errmsg(p->dbDest));
221 return;
223 zSql = sqlite3_mprintf("PRAGMA page_size(%u);", p->szPage);
224 if( zSql==0 ){
225 p->rcErr = SQLITE_NOMEM;
226 return;
228 p->rcErr = sqlite3_exec(p->dbDest, zSql, 0, 0, 0);
229 sqlite3_free(zSql);
230 if( p->rcErr ){
231 scrubBackupErr(p,
232 "cannot set the page size on the destination database: %s",
233 sqlite3_errmsg(p->dbDest));
234 return;
236 sqlite3_exec(p->dbDest, "PRAGMA journal_mode=OFF;", 0, 0, 0);
237 p->rcErr = sqlite3_exec(p->dbDest, "BEGIN EXCLUSIVE;", 0, 0, 0);
238 if( p->rcErr ){
239 scrubBackupErr(p,
240 "cannot start a write transaction on the destination database: %s",
241 sqlite3_errmsg(p->dbDest));
242 return;
244 pStmt = scrubBackupPrepare(p, p->dbDest, "PRAGMA page_count;");
245 if( pStmt==0 ) return;
246 rc = sqlite3_step(pStmt);
247 if( rc!=SQLITE_ROW ){
248 scrubBackupErr(p, "cannot measure the size of the destination");
249 }else if( sqlite3_column_int(pStmt, 0)>1 ){
250 scrubBackupErr(p, "destination database is not empty - holds %d pages",
251 sqlite3_column_int(pStmt, 0));
253 sqlite3_finalize(pStmt);
254 sqlite3_file_control(p->dbDest, "main", SQLITE_FCNTL_FILE_POINTER, &p->pDest);
255 if( p->pDest==0 || p->pDest->pMethods==0 ){
256 scrubBackupErr(p, "cannot get the destination file handle");
257 p->rcErr = SQLITE_ERROR;
261 /* Read a 32-bit big-endian integer */
262 static u32 scrubBackupInt32(const u8 *a){
263 u32 v = a[3];
264 v += ((u32)a[2])<<8;
265 v += ((u32)a[1])<<16;
266 v += ((u32)a[0])<<24;
267 return v;
270 /* Read a 16-bit big-endian integer */
271 static u32 scrubBackupInt16(const u8 *a){
272 return (a[0]<<8) + a[1];
276 ** Read a varint. Put the value in *pVal and return the number of bytes.
278 static int scrubBackupVarint(const u8 *z, sqlite3_int64 *pVal){
279 sqlite3_int64 v = 0;
280 int i;
281 for(i=0; i<8; i++){
282 v = (v<<7) + (z[i]&0x7f);
283 if( (z[i]&0x80)==0 ){ *pVal = v; return i+1; }
285 v = (v<<8) + (z[i]&0xff);
286 *pVal = v;
287 return 9;
291 ** Return the number of bytes in a varint.
293 static int scrubBackupVarintSize(const u8 *z){
294 int i;
295 for(i=0; i<8; i++){
296 if( (z[i]&0x80)==0 ){ return i+1; }
298 return 9;
302 ** Copy the freelist trunk page given, and all its descendents,
303 ** zeroing out as much as possible in the process.
305 static void scrubBackupFreelist(ScrubState *p, int pgno, u32 nFree){
306 u8 *a, *aBuf;
307 u32 n, mx;
309 if( p->rcErr ) return;
310 aBuf = scrubBackupAllocPage(p);
311 if( aBuf==0 ) return;
313 while( pgno && nFree){
314 a = scrubBackupRead(p, pgno, aBuf);
315 if( a==0 ) break;
316 n = scrubBackupInt32(&a[4]);
317 mx = p->szUsable/4 - 2;
318 if( n<mx ){
319 memset(&a[n*4+8], 0, 4*(mx-n));
321 scrubBackupWrite(p, pgno, a);
322 pgno = scrubBackupInt32(a);
323 #if 0
324 /* There is really no point in copying the freelist leaf pages.
325 ** Simply leave them uninitialized in the destination database. The
326 ** OS filesystem should zero those pages for us automatically.
328 for(i=0; i<n && nFree; i++){
329 u32 iLeaf = scrubBackupInt32(&a[i*4+8]);
330 if( aZero==0 ){
331 aZero = scrubBackupAllocPage(p);
332 if( aZero==0 ){ pgno = 0; break; }
333 memset(aZero, 0, p->szPage);
335 scrubBackupWrite(p, iLeaf, aZero);
336 nFree--;
338 #endif
340 sqlite3_free(aBuf);
344 ** Copy an overflow chain from source to destination. Zero out any
345 ** unused tail at the end of the overflow chain.
347 static void scrubBackupOverflow(ScrubState *p, int pgno, u32 nByte){
348 u8 *a, *aBuf;
350 aBuf = scrubBackupAllocPage(p);
351 if( aBuf==0 ) return;
352 while( nByte>0 && pgno!=0 ){
353 a = scrubBackupRead(p, pgno, aBuf);
354 if( a==0 ) break;
355 if( nByte >= (p->szUsable)-4 ){
356 nByte -= (p->szUsable) - 4;
357 }else{
358 u32 x = (p->szUsable - 4) - nByte;
359 u32 i = p->szUsable - x;
360 memset(&a[i], 0, x);
361 nByte = 0;
363 scrubBackupWrite(p, pgno, a);
364 pgno = scrubBackupInt32(a);
366 sqlite3_free(aBuf);
371 ** Copy B-Tree page pgno, and all of its children, from source to destination.
372 ** Zero out deleted content during the copy.
374 static void scrubBackupBtree(ScrubState *p, int pgno, int iDepth){
375 u8 *a;
376 u32 i, n, pc;
377 u32 nCell;
378 u32 nPrefix;
379 u32 szHdr;
380 u32 iChild;
381 u8 *aTop;
382 u8 *aCell;
383 u32 x, y;
384 int ln = 0;
387 if( p->rcErr ) return;
388 if( iDepth>50 ){
389 scrubBackupErr(p, "corrupt: b-tree too deep at page %d", pgno);
390 return;
392 if( pgno==1 ){
393 a = p->page1;
394 }else{
395 a = scrubBackupRead(p, pgno, 0);
396 if( a==0 ) return;
398 nPrefix = pgno==1 ? 100 : 0;
399 aTop = &a[nPrefix];
400 szHdr = 8 + 4*(aTop[0]==0x02 || aTop[0]==0x05);
401 aCell = aTop + szHdr;
402 nCell = scrubBackupInt16(&aTop[3]);
404 /* Zero out the gap between the cell index and the start of the
405 ** cell content area */
406 x = scrubBackupInt16(&aTop[5]); /* First byte of cell content area */
407 if( x>p->szUsable ){ ln=__LINE__; goto btree_corrupt; }
408 y = szHdr + nPrefix + nCell*2;
409 if( y>x ){ ln=__LINE__; goto btree_corrupt; }
410 if( y<x ) memset(a+y, 0, x-y); /* Zero the gap */
412 /* Zero out all the free blocks */
413 pc = scrubBackupInt16(&aTop[1]);
414 if( pc>0 && pc<x ){ ln=__LINE__; goto btree_corrupt; }
415 while( pc ){
416 if( pc>(p->szUsable)-4 ){ ln=__LINE__; goto btree_corrupt; }
417 n = scrubBackupInt16(&a[pc+2]);
418 if( pc+n>(p->szUsable) ){ ln=__LINE__; goto btree_corrupt; }
419 if( n>4 ) memset(&a[pc+4], 0, n-4);
420 x = scrubBackupInt16(&a[pc]);
421 if( x<pc+4 && x>0 ){ ln=__LINE__; goto btree_corrupt; }
422 pc = x;
425 /* Write this one page */
426 scrubBackupWrite(p, pgno, a);
428 /* Walk the tree and process child pages */
429 for(i=0; i<nCell; i++){
430 u32 X, M, K, nLocal;
431 sqlite3_int64 P;
432 pc = scrubBackupInt16(&aCell[i*2]);
433 if( pc <= szHdr ){ ln=__LINE__; goto btree_corrupt; }
434 if( pc > p->szUsable-3 ){ ln=__LINE__; goto btree_corrupt; }
435 if( aTop[0]==0x05 || aTop[0]==0x02 ){
436 if( pc+4 > p->szUsable ){ ln=__LINE__; goto btree_corrupt; }
437 iChild = scrubBackupInt32(&a[pc]);
438 pc += 4;
439 scrubBackupBtree(p, iChild, iDepth+1);
440 if( aTop[0]==0x05 ) continue;
442 pc += scrubBackupVarint(&a[pc], &P);
443 if( pc >= p->szUsable ){ ln=__LINE__; goto btree_corrupt; }
444 if( aTop[0]==0x0d ){
445 X = p->szUsable - 35;
446 }else{
447 X = ((p->szUsable - 12)*64/255) - 23;
449 if( P<=X ){
450 /* All content is local. No overflow */
451 continue;
453 M = ((p->szUsable - 12)*32/255)-23;
454 K = M + ((P-M)%(p->szUsable-4));
455 if( aTop[0]==0x0d ){
456 pc += scrubBackupVarintSize(&a[pc]);
457 if( pc > (p->szUsable-4) ){ ln=__LINE__; goto btree_corrupt; }
459 nLocal = K<=X ? K : M;
460 if( pc+nLocal > p->szUsable-4 ){ ln=__LINE__; goto btree_corrupt; }
461 iChild = scrubBackupInt32(&a[pc+nLocal]);
462 scrubBackupOverflow(p, iChild, (u32)(P-nLocal));
465 /* Walk the right-most tree */
466 if( aTop[0]==0x05 || aTop[0]==0x02 ){
467 iChild = scrubBackupInt32(&aTop[8]);
468 scrubBackupBtree(p, iChild, iDepth+1);
471 /* All done */
472 if( pgno>1 ) sqlite3_free(a);
473 return;
475 btree_corrupt:
476 scrubBackupErr(p, "corruption on page %d of source database (errid=%d)",
477 pgno, ln);
478 if( pgno>1 ) sqlite3_free(a);
482 ** Copy all ptrmap pages from source to destination.
483 ** This routine is only called if the source database is in autovacuum
484 ** or incremental vacuum mode.
486 static void scrubBackupPtrmap(ScrubState *p){
487 u32 pgno = 2;
488 u32 J = p->szUsable/5;
489 u32 iLock = (1073742335/p->szPage)+1;
490 u8 *a, *pBuf;
491 if( p->rcErr ) return;
492 pBuf = scrubBackupAllocPage(p);
493 if( pBuf==0 ) return;
494 while( pgno<=p->nPage ){
495 a = scrubBackupRead(p, pgno, pBuf);
496 if( a==0 ) break;
497 scrubBackupWrite(p, pgno, a);
498 pgno += J+1;
499 if( pgno==iLock ) pgno++;
501 sqlite3_free(pBuf);
504 int sqlite3_scrub_backup(
505 const char *zSrcFile, /* Source file */
506 const char *zDestFile, /* Destination file */
507 char **pzErr /* Write error here if non-NULL */
509 ScrubState s;
510 u32 n, i;
511 sqlite3_stmt *pStmt;
513 memset(&s, 0, sizeof(s));
514 s.zSrcFile = zSrcFile;
515 s.zDestFile = zDestFile;
517 /* Open both source and destination databases */
518 scrubBackupOpenSrc(&s);
519 scrubBackupOpenDest(&s);
521 /* Read in page 1 */
522 s.page1 = scrubBackupRead(&s, 1, 0);
523 if( s.page1==0 ) goto scrub_abort;
524 s.szUsable = s.szPage - s.page1[20];
526 /* Copy the freelist */
527 n = scrubBackupInt32(&s.page1[36]);
528 i = scrubBackupInt32(&s.page1[32]);
529 if( n ) scrubBackupFreelist(&s, i, n);
531 /* Copy ptrmap pages */
532 n = scrubBackupInt32(&s.page1[52]);
533 if( n ) scrubBackupPtrmap(&s);
535 /* Copy all of the btrees */
536 scrubBackupBtree(&s, 1, 0);
537 pStmt = scrubBackupPrepare(&s, s.dbSrc,
538 "SELECT rootpage FROM sqlite_master WHERE coalesce(rootpage,0)>0");
539 if( pStmt==0 ) goto scrub_abort;
540 while( sqlite3_step(pStmt)==SQLITE_ROW ){
541 i = (u32)sqlite3_column_int(pStmt, 0);
542 scrubBackupBtree(&s, i, 0);
544 sqlite3_finalize(pStmt);
546 /* If the last page of the input db file is a free-list leaf, then the
547 ** backup file on disk is still smaller than the size indicated within
548 ** the database header. In this case, write a page of zeroes to the
549 ** last page of the backup database so that SQLite does not mistakenly
550 ** think the db is corrupt. */
551 if( s.iLastPage<s.nPage ){
552 u8 *aZero = scrubBackupAllocPage(&s);
553 if( aZero ){
554 memset(aZero, 0, s.szPage);
555 scrubBackupWrite(&s, s.nPage, aZero);
556 sqlite3_free(aZero);
560 scrub_abort:
561 /* Close the destination database without closing the transaction. If we
562 ** commit, page zero will be overwritten. */
563 sqlite3_close(s.dbDest);
565 /* But do close out the read-transaction on the source database */
566 sqlite3_exec(s.dbSrc, "COMMIT;", 0, 0, 0);
567 sqlite3_close(s.dbSrc);
568 sqlite3_free(s.page1);
569 if( pzErr ){
570 *pzErr = s.zErr;
571 }else{
572 sqlite3_free(s.zErr);
574 return s.rcErr;
577 #ifdef SCRUB_STANDALONE
578 /* Error and warning log */
579 static void errorLogCallback(void *pNotUsed, int iErr, const char *zMsg){
580 const char *zType;
581 switch( iErr&0xff ){
582 case SQLITE_WARNING: zType = "WARNING"; break;
583 case SQLITE_NOTICE: zType = "NOTICE"; break;
584 default: zType = "ERROR"; break;
586 fprintf(stderr, "%s: %s\n", zType, zMsg);
589 /* The main() routine when this utility is run as a stand-alone program */
590 int main(int argc, char **argv){
591 char *zErr = 0;
592 int rc;
593 if( argc!=3 ){
594 fprintf(stderr,"Usage: %s SOURCE DESTINATION\n", argv[0]);
595 exit(1);
597 sqlite3_config(SQLITE_CONFIG_LOG, errorLogCallback, 0);
598 rc = sqlite3_scrub_backup(argv[1], argv[2], &zErr);
599 if( rc==SQLITE_NOMEM ){
600 fprintf(stderr, "%s: out of memory\n", argv[0]);
601 exit(1);
603 if( zErr ){
604 fprintf(stderr, "%s: %s\n", argv[0], zErr);
605 sqlite3_free(zErr);
606 exit(1);
608 return 0;
610 #endif