localdb.cc

   1 /* Cumulus: Efficient Filesystem Backup to the Cloud
   2  * Copyright (C) 2007-2008 The Cumulus Developers
   3  * See the AUTHORS file for a list of contributors.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 /* When creating backup snapshots, maintain a local database of data blocks and
  21  * checksums, in addition to the data contents (which may be stored remotely).
  22  * This database is consulted when attempting to build incremental snapshots,
  23  * as it says which objects can be reused.
  24  *
  25  * The database is implemented as an SQLite3 database, but this implementation
  26  * detail is kept internal to this file, so that the storage format may be
  27  * changed later. */
  28
  29 #include <assert.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32 #include <sqlite3.h>
  33
  34 #include <algorithm>
  35 #include <string>
  36
  37 #include "localdb.h"
  38 #include "store.h"
  39 #include "util.h"
  40
  41 using std::min;
  42 using std::string;
  43
  44 /* Helper function to prepare a statement for execution in the current
  45  * database. */
  46 sqlite3_stmt *LocalDb::Prepare(const char *sql)
  47 {
  48     sqlite3_stmt *stmt;
  49     int rc;
  50     const char *tail;
  51
  52     rc = sqlite3_prepare_v2(db, sql, strlen(sql), &stmt, &tail);
  53     if (rc != SQLITE_OK) {
  54         ReportError(rc);
  55         fatal(string("Error preparing statement: ") + sql);
  56     }
  57
  58     return stmt;
  59 }
  60
  61 void LocalDb::ReportError(int rc)
  62 {
  63     fprintf(stderr, "Result code: %d\n", rc);
  64     fprintf(stderr, "Error message: %s\n", sqlite3_errmsg(db));
  65 }
  66
  67 void LocalDb::Open(const char *path, const char *snapshot_name,
  68                    const char *snapshot_scheme, double intent)
  69 {
  70     int rc;
  71
  72     rc = sqlite3_open(path, &db);
  73     if (rc) {
  74         fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
  75         sqlite3_close(db);
  76         fatal("Error opening local database");
  77     }
  78
  79     rc = sqlite3_exec(db, "begin", NULL, NULL, NULL);
  80     if (rc) {
  81         fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
  82         sqlite3_close(db);
  83         fatal("Error starting transaction");
  84     }
  85
  86     sqlite3_extended_result_codes(db, 1);
  87
  88     if (snapshot_scheme == NULL)
  89         snapshot_scheme = "";
  90
  91     /* Insert this snapshot into the database, and determine the integer key
  92      * which will be used to identify it. */
  93     sqlite3_stmt *stmt = Prepare("insert into "
  94                                  "snapshots(name, scheme, timestamp, intent) "
  95                                  "values (?, ?, julianday('now'), ?)");
  96     sqlite3_bind_text(stmt, 1, snapshot_name, strlen(snapshot_name),
  97                       SQLITE_TRANSIENT);
  98     sqlite3_bind_text(stmt, 2, snapshot_scheme, strlen(snapshot_scheme),
  99                       SQLITE_TRANSIENT);
 100     sqlite3_bind_double(stmt, 3, intent);
 101
 102     rc = sqlite3_step(stmt);
 103     if (rc != SQLITE_DONE) {
 104         ReportError(rc);
 105         sqlite3_close(db);
 106         fatal("Database execution error!");
 107     }
 108
 109     snapshotid = sqlite3_last_insert_rowid(db);
 110     sqlite3_finalize(stmt);
 111     if (snapshotid == 0) {
 112         ReportError(rc);
 113         sqlite3_close(db);
 114         fatal("Find snapshot id");
 115     }
 116
 117     /* Create a temporary table which will be used to keep track of the objects
 118      * used by this snapshot.  When the database is closed, we will summarize
 119      * the results of this table into segments_used. */
 120     rc = sqlite3_exec(db,
 121                       "create temporary table snapshot_refs ("
 122                       "    segmentid integer not null,"
 123                       "    object text not null,"
 124                       "    size integer not null"
 125                       ")", NULL, NULL, NULL);
 126     if (rc != SQLITE_OK) {
 127         ReportError(rc);
 128         sqlite3_close(db);
 129         fatal("Database initialization");
 130     }
 131     rc = sqlite3_exec(db,
 132                       "create unique index snapshot_refs_index "
 133                       "on snapshot_refs(segmentid, object)",
 134                       NULL, NULL, NULL);
 135     if (rc != SQLITE_OK) {
 136         ReportError(rc);
 137         sqlite3_close(db);
 138         fatal("Database initialization");
 139     }
 140 }
 141
 142 void LocalDb::Close()
 143 {
 144     int rc;
 145
 146     /* Summarize the snapshot_refs table into segments_used. */
 147     sqlite3_stmt *stmt = Prepare(
 148         "insert or replace into segments_used "
 149         "select ? as snapshotid, segmentid, max(utilization) from ("
 150         "    select segmentid, cast(used as real) / size as utilization "
 151         "    from "
 152         "    (select segmentid, sum(size) as used from snapshot_refs "
 153         "       group by segmentid) "
 154         "    join segments using (segmentid) "
 155         "  union "
 156         "    select segmentid, utilization from segments_used "
 157         "    where snapshotid = ? "
 158         ") group by segmentid"
 159     );
 160     sqlite3_bind_int64(stmt, 1, snapshotid);
 161     sqlite3_bind_int64(stmt, 2, snapshotid);
 162     rc = sqlite3_step(stmt);
 163     if (rc != SQLITE_OK && rc != SQLITE_DONE) {
 164         ReportError(rc);
 165         sqlite3_close(db);
 166         fprintf(stderr, "DATABASE ERROR: Unable to create segment summary!\n");
 167     }
 168     sqlite3_finalize(stmt);
 169
 170     /* Commit changes to the database and close. */
 171     rc = sqlite3_exec(db, "commit", NULL, NULL, NULL);
 172     if (rc != SQLITE_OK) {
 173         fprintf(stderr, "DATABASE ERROR: Can't commit database!\n");
 174         ReportError(rc);
 175     }
 176     sqlite3_close(db);
 177 }
 178
 179 int64_t LocalDb::SegmentToId(const string &segment)
 180 {
 181     int rc;
 182     sqlite3_stmt *stmt;
 183     int64_t result;
 184
 185     stmt = Prepare("insert or ignore into segments(segment) values (?)");
 186     sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
 187                       SQLITE_TRANSIENT);
 188     rc = sqlite3_step(stmt);
 189     if (rc != SQLITE_DONE) {
 190         fatal("Could not execute INSERT statement!");
 191     }
 192     sqlite3_finalize(stmt);
 193
 194     stmt = Prepare("select segmentid from segments where segment = ?");
 195     sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
 196                       SQLITE_TRANSIENT);
 197
 198     rc = sqlite3_step(stmt);
 199     if (rc == SQLITE_DONE) {
 200         fatal("No segment found by id");
 201     } else if (rc == SQLITE_ROW) {
 202         result = sqlite3_column_int64(stmt, 0);
 203     } else {
 204         fatal("Error executing find segment by id query");
 205     }
 206
 207     sqlite3_finalize(stmt);
 208
 209     return result;
 210 }
 211
 212 string LocalDb::IdToSegment(int64_t segmentid)
 213 {
 214     int rc;
 215     sqlite3_stmt *stmt;
 216     string result;
 217
 218     stmt = Prepare("select segment from segments where segmentid = ?");
 219     sqlite3_bind_int64(stmt, 1, segmentid);
 220
 221     rc = sqlite3_step(stmt);
 222     if (rc == SQLITE_DONE) {
 223         fatal("No segment found by id");
 224     } else if (rc == SQLITE_ROW) {
 225         result = (const char *)sqlite3_column_text(stmt, 0);
 226     } else {
 227         fatal("Error executing find segment by id query");
 228     }
 229
 230     sqlite3_finalize(stmt);
 231
 232     return result;
 233 }
 234
 235 void LocalDb::StoreObject(const ObjectReference& ref,
 236                           const string &checksum, int64_t size,
 237                           double age)
 238 {
 239     int rc;
 240     sqlite3_stmt *stmt;
 241
 242     if (age == 0.0) {
 243         stmt = Prepare("insert into block_index("
 244                        "segmentid, object, checksum, size, timestamp) "
 245                        "values (?, ?, ?, ?, julianday('now'))");
 246     } else {
 247         stmt = Prepare("insert into block_index("
 248                        "segmentid, object, checksum, size, timestamp) "
 249                        "values (?, ?, ?, ?, ?)");
 250     }
 251
 252     sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 253     string obj = ref.get_sequence();
 254     sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
 255     sqlite3_bind_text(stmt, 3, checksum.c_str(), checksum.size(),
 256                       SQLITE_TRANSIENT);
 257     sqlite3_bind_int64(stmt, 4, size);
 258     if (age != 0.0)
 259         sqlite3_bind_double(stmt, 5, age);
 260
 261     rc = sqlite3_step(stmt);
 262     if (rc != SQLITE_DONE) {
 263         fprintf(stderr, "Could not execute INSERT statement!\n");
 264         ReportError(rc);
 265     }
 266
 267     sqlite3_finalize(stmt);
 268
 269     if (age != 0.0) {
 270         stmt = Prepare("update segments "
 271                        "set mtime = coalesce(max(mtime, ?), ?) "
 272                        "where segmentid = ?");
 273         sqlite3_bind_double(stmt, 1, age);
 274         sqlite3_bind_double(stmt, 2, age);
 275         sqlite3_bind_int64(stmt, 3, SegmentToId(ref.get_segment()));
 276         rc = sqlite3_step(stmt);
 277         sqlite3_finalize(stmt);
 278     }
 279 }
 280
 281 ObjectReference LocalDb::FindObject(const string &checksum, int64_t size)
 282 {
 283     int rc;
 284     sqlite3_stmt *stmt;
 285     ObjectReference ref;
 286
 287     stmt = Prepare("select segmentid, object from block_index "
 288                    "where checksum = ? and size = ? and expired is null");
 289     sqlite3_bind_text(stmt, 1, checksum.c_str(), checksum.size(),
 290                       SQLITE_TRANSIENT);
 291     sqlite3_bind_int64(stmt, 2, size);
 292
 293     rc = sqlite3_step(stmt);
 294     if (rc == SQLITE_DONE) {
 295     } else if (rc == SQLITE_ROW) {
 296         ref = ObjectReference(IdToSegment(sqlite3_column_int64(stmt, 0)),
 297                               (const char *)sqlite3_column_text(stmt, 1));
 298         ref.set_range(0, size, true);
 299     } else {
 300         fprintf(stderr, "Could not execute SELECT statement!\n");
 301         ReportError(rc);
 302     }
 303
 304     sqlite3_finalize(stmt);
 305
 306     return ref;
 307 }
 308
 309 bool LocalDb::IsOldObject(const string &checksum, int64_t size, double *age,
 310                           int *group)
 311 {
 312     int rc;
 313     sqlite3_stmt *stmt;
 314     bool found = false;
 315
 316     stmt = Prepare("select segmentid, object, timestamp, expired "
 317                    "from block_index where checksum = ? and size = ?");
 318     sqlite3_bind_text(stmt, 1, checksum.c_str(), checksum.size(),
 319                       SQLITE_TRANSIENT);
 320     sqlite3_bind_int64(stmt, 2, size);
 321
 322     rc = sqlite3_step(stmt);
 323     if (rc == SQLITE_DONE) {
 324         found = false;
 325     } else if (rc == SQLITE_ROW) {
 326         found = true;
 327         *age = sqlite3_column_double(stmt, 2);
 328         *group = sqlite3_column_int(stmt, 3);
 329     } else {
 330         fprintf(stderr, "Could not execute SELECT statement!\n");
 331         ReportError(rc);
 332     }
 333
 334     sqlite3_finalize(stmt);
 335
 336     return found;
 337 }
 338
 339 /* Does this object still exist in the database (and not expired)? */
 340 bool LocalDb::IsAvailable(const ObjectReference &ref)
 341 {
 342     int rc;
 343     sqlite3_stmt *stmt;
 344     bool found = false;
 345
 346     // Special objects (such as the zero object) aren't stored in segments, and
 347     // so are always available.
 348     if (!ref.is_normal())
 349         return true;
 350
 351     stmt = Prepare("select count(*) from block_index "
 352                    "where segmentid = ? and object = ? and expired is null");
 353     sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 354     sqlite3_bind_text(stmt, 2, ref.get_sequence().c_str(),
 355                       ref.get_sequence().size(), SQLITE_TRANSIENT);
 356
 357     rc = sqlite3_step(stmt);
 358     if (rc == SQLITE_DONE) {
 359         found = false;
 360     } else if (rc == SQLITE_ROW) {
 361         if (sqlite3_column_int(stmt, 0) > 0)
 362             found = true;
 363     } else {
 364         fprintf(stderr, "Could not execute SELECT statement!\n");
 365         ReportError(rc);
 366     }
 367
 368     sqlite3_finalize(stmt);
 369
 370     return found;
 371 }
 372
 373 void LocalDb::UseObject(const ObjectReference& ref)
 374 {
 375     int rc;
 376     sqlite3_stmt *stmt;
 377
 378     if (!ref.is_normal())
 379         return;
 380
 381     int64_t old_size = 0;
 382     stmt = Prepare("select size from snapshot_refs "
 383                    "where segmentid = ? and object = ?");
 384     sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 385     string obj = ref.get_sequence();
 386     sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
 387     rc = sqlite3_step(stmt);
 388     if (rc == SQLITE_ROW) {
 389         old_size = sqlite3_column_int64(stmt, 0);
 390     }
 391     sqlite3_finalize(stmt);
 392
 393     int64_t block_size = 0;
 394     stmt = Prepare("select size from block_index "
 395                    "where segmentid = ? and object = ?");
 396     sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 397     obj = ref.get_sequence();
 398     sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
 399     rc = sqlite3_step(stmt);
 400     if (rc == SQLITE_ROW) {
 401         block_size = sqlite3_column_int64(stmt, 0);
 402     } else {
 403         string refstr = ref.to_string();
 404         fprintf(stderr, "No block found in block_index for %s\n",
 405                 refstr.c_str());
 406         sqlite3_finalize(stmt);
 407         return;
 408     }
 409     sqlite3_finalize(stmt);
 410
 411     int64_t new_size = old_size;
 412     if (ref.has_range()) {
 413         new_size += ref.get_range_length();
 414         new_size = min(new_size, block_size);
 415     } else {
 416         new_size = block_size;
 417     }
 418
 419     if (new_size != old_size) {
 420         stmt = Prepare("insert or replace "
 421                        "into snapshot_refs(segmentid, object, size) "
 422                        "values (?, ?, ?)");
 423         sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 424         obj = ref.get_sequence();
 425         sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
 426         sqlite3_bind_int64(stmt, 3, new_size);
 427
 428         rc = sqlite3_step(stmt);
 429         if (rc != SQLITE_DONE) {
 430             fprintf(stderr, "Could not execute INSERT statement!\n");
 431             ReportError(rc);
 432         }
 433
 434         sqlite3_finalize(stmt);
 435     }
 436 }
 437
 438 void LocalDb::UseSegment(const std::string &segment, double utilization)
 439 {
 440     int rc;
 441     sqlite3_stmt *stmt;
 442
 443     stmt = Prepare("insert or replace "
 444                    "into segments_used(snapshotid, segmentid, utilization) "
 445                    "values (?, ?, ?)");
 446     sqlite3_bind_int64(stmt, 1, snapshotid);
 447     sqlite3_bind_int64(stmt, 2, SegmentToId(segment));
 448     sqlite3_bind_double(stmt, 3, utilization);
 449
 450     rc = sqlite3_step(stmt);
 451     if (rc != SQLITE_DONE) {
 452         fprintf(stderr, "Could not insert segment use record!\n");
 453         ReportError(rc);
 454     }
 455
 456     sqlite3_finalize(stmt);
 457 }
 458
 459 void LocalDb::SetSegmentChecksum(const std::string &segment,
 460                                  const std::string &path,
 461                                  const std::string &checksum,
 462                                  int size)
 463 {
 464     int rc;
 465     sqlite3_stmt *stmt;
 466
 467     stmt = Prepare("update segments set path = ?, checksum = ?, size = ?, "
 468                    "mtime = coalesce(mtime, julianday('now')) "
 469                    "where segmentid = ?");
 470     sqlite3_bind_text(stmt, 1, path.c_str(), path.size(),
 471                       SQLITE_TRANSIENT);
 472     sqlite3_bind_text(stmt, 2, checksum.c_str(), checksum.size(),
 473                       SQLITE_TRANSIENT);
 474     sqlite3_bind_int64(stmt, 3, size);
 475     sqlite3_bind_int64(stmt, 4, SegmentToId(segment));
 476
 477     rc = sqlite3_step(stmt);
 478     if (rc != SQLITE_DONE) {
 479         fprintf(stderr, "Could not update segment checksum in database!\n");
 480         ReportError(rc);
 481     }
 482
 483     sqlite3_finalize(stmt);
 484 }
 485
 486 bool LocalDb::GetSegmentChecksum(const string &segment,
 487                                  string *seg_path,
 488                                  string *seg_checksum)
 489 {
 490     int rc;
 491     sqlite3_stmt *stmt;
 492     ObjectReference ref;
 493     int found = false;
 494
 495     stmt = Prepare("select path, checksum from segments where segment = ?");
 496     sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
 497                       SQLITE_TRANSIENT);
 498
 499     rc = sqlite3_step(stmt);
 500     if (rc == SQLITE_DONE) {
 501     } else if (rc == SQLITE_ROW) {
 502         found = true;
 503         const char *val;
 504
 505         val = (const char *)sqlite3_column_text(stmt, 0);
 506         if (val == NULL)
 507             found = false;
 508         else
 509             *seg_path = val;
 510
 511         val = (const char *)sqlite3_column_text(stmt, 1);
 512         if (val == NULL)
 513             found = false;
 514         else
 515             *seg_checksum = val;
 516     } else {
 517         fprintf(stderr, "Could not execute SELECT statement!\n");
 518         ReportError(rc);
 519     }
 520
 521     sqlite3_finalize(stmt);
 522
 523     return found;
 524 }
 525
 526 /* Look up and return the packed representation of the subblock chunk
 527  * signatures.  Returns true if signatures were found for the specified object,
 528  * and if so sets *buf to point at a buffer of memory (allocated with malloc;
 529  * the caller should free it), and *len to the length of the buffer. */
 530 bool LocalDb::LoadChunkSignatures(ObjectReference ref,
 531                                   void **buf, size_t *len,
 532                                   string *algorithm)
 533 {
 534     int rc;
 535     sqlite3_stmt *stmt;
 536     int found = false;
 537
 538     stmt = Prepare("select signatures, algorithm from subblock_signatures "
 539                    "where blockid = (select blockid from block_index "
 540                    "                 where segmentid = ? and object = ?)");
 541     sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 542     string obj = ref.get_sequence();
 543     sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
 544
 545     rc = sqlite3_step(stmt);
 546     if (rc == SQLITE_DONE) {
 547     } else if (rc == SQLITE_ROW) {
 548         const void *data = sqlite3_column_blob(stmt, 0);
 549         *len = sqlite3_column_bytes(stmt, 0);
 550
 551         if (*len > 0) {
 552             *buf = malloc(*len);
 553             if (*buf != NULL) {
 554                 memcpy(*buf, data, *len);
 555                 *algorithm = (const char *)sqlite3_column_text(stmt, 1);
 556                 found = true;
 557             }
 558         }
 559     } else {
 560         fprintf(stderr, "Could not execute SELECT statement!\n");
 561         ReportError(rc);
 562     }
 563
 564     sqlite3_finalize(stmt);
 565
 566     return found;
 567 }
 568
 569 /* Store the subblock chunk signatures for a specified object.  The object
 570  * itself must have already been indexed in the database. */
 571 void LocalDb::StoreChunkSignatures(ObjectReference ref,
 572                                    const void *buf, size_t len,
 573                                    const string& algorithm)
 574 {
 575     int rc;
 576     sqlite3_stmt *stmt;
 577
 578     stmt = Prepare("select blockid from block_index "
 579                    "where segmentid = ? and object = ?");
 580     sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
 581     string obj = ref.get_sequence();
 582     sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
 583
 584     rc = sqlite3_step(stmt);
 585     if (rc != SQLITE_ROW) {
 586         fprintf(stderr,
 587                 "Could not determine blockid in StoreChunkSignatures!\n");
 588         ReportError(rc);
 589         fatal("Error getting blockid");
 590     }
 591     int64_t blockid = sqlite3_column_int64(stmt, 0);
 592     sqlite3_finalize(stmt);
 593
 594     stmt = Prepare("insert or replace "
 595                    "into subblock_signatures(blockid, algorithm, signatures) "
 596                    "values (?, ?, ?)");
 597     sqlite3_bind_int64(stmt, 1, blockid);
 598     sqlite3_bind_text(stmt, 2, algorithm.c_str(), algorithm.size(),
 599                       SQLITE_TRANSIENT);
 600     sqlite3_bind_blob(stmt, 3, buf, len, SQLITE_TRANSIENT);
 601
 602     rc = sqlite3_step(stmt);
 603     if (rc != SQLITE_DONE) {
 604         fprintf(stderr, "Could not insert sub-block checksums!\n");
 605         ReportError(rc);
 606     }
 607
 608     sqlite3_finalize(stmt);
 609 }