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.
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.
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.
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.
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.
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
48 static const int SCHEMA_MAJOR = 0;
49 static const int SCHEMA_MINOR = 11;
51 /* Helper function to prepare a statement for execution in the current
53 sqlite3_stmt *LocalDb::Prepare(const char *sql)
59 rc = sqlite3_prepare_v2(db, sql, strlen(sql), &stmt, &tail);
60 if (rc != SQLITE_OK) {
62 fatal(string("Error preparing statement: ") + sql);
68 void LocalDb::ReportError(int rc)
70 fprintf(stderr, "Result code: %d\n", rc);
71 fprintf(stderr, "Error message: %s\n", sqlite3_errmsg(db));
74 void LocalDb::Open(const char *path, const char *snapshot_name,
75 const char *snapshot_scheme)
79 rc = sqlite3_open(path, &db);
81 fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
83 fatal("Error opening local database");
86 rc = sqlite3_exec(db, "begin", NULL, NULL, NULL);
88 fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
90 fatal("Error starting transaction");
93 sqlite3_extended_result_codes(db, 1);
95 /* Check that the local database format is the correct version; if not,
97 sqlite3_stmt *stmt = Prepare("select major, minor from schema_version");
99 rc = sqlite3_step(stmt);
100 if (rc != SQLITE_ROW) {
101 fatal("Unable to read local database version from database");
102 } else if (rc == SQLITE_ROW) {
103 int major = sqlite3_column_int(stmt, 0);
104 int minor = sqlite3_column_int(stmt, 1);
105 if (major != SCHEMA_MAJOR || minor != SCHEMA_MINOR) {
107 "Local database does not have required schema version!\n"
108 " expected: %d.%d, found: %d.%d\n",
109 SCHEMA_MAJOR, SCHEMA_MINOR, major, minor);
110 fatal("Unable to continue.");
113 sqlite3_finalize(stmt);
115 if (snapshot_scheme == NULL)
116 snapshot_scheme = "";
118 /* Insert this snapshot into the database, and determine the integer key
119 * which will be used to identify it. */
120 stmt = Prepare("insert into snapshots(name, scheme, timestamp) "
121 "values (?, ?, julianday('now'))");
122 sqlite3_bind_text(stmt, 1, snapshot_name, strlen(snapshot_name),
124 sqlite3_bind_text(stmt, 2, snapshot_scheme, strlen(snapshot_scheme),
127 rc = sqlite3_step(stmt);
128 if (rc != SQLITE_DONE) {
131 fatal("Database execution error!");
134 snapshotid = sqlite3_last_insert_rowid(db);
135 sqlite3_finalize(stmt);
136 if (snapshotid == 0) {
139 fatal("Find snapshot id");
142 /* Create a temporary table which will be used to keep track of the objects
143 * used by this snapshot. When the database is closed, we will summarize
144 * the results of this table into segments_used. */
145 rc = sqlite3_exec(db,
146 "create temporary table snapshot_refs ("
147 " segmentid integer not null,"
148 " object text not null,"
149 " size integer not null"
150 ")", NULL, NULL, NULL);
151 if (rc != SQLITE_OK) {
154 fatal("Database initialization");
156 rc = sqlite3_exec(db,
157 "create unique index snapshot_refs_index "
158 "on snapshot_refs(segmentid, object)",
160 if (rc != SQLITE_OK) {
163 fatal("Database initialization");
167 void LocalDb::Close()
171 /* Summarize the snapshot_refs table into segment_utilization. */
172 sqlite3_stmt *stmt = Prepare(
173 "insert or replace into segment_utilization "
174 "select ? as snapshotid, segmentid, sum(size) "
175 "from snapshot_refs group by segmentid"
177 sqlite3_bind_int64(stmt, 1, snapshotid);
178 rc = sqlite3_step(stmt);
179 if (rc != SQLITE_OK && rc != SQLITE_DONE) {
182 fprintf(stderr, "DATABASE ERROR: Unable to create segment summary!\n");
184 sqlite3_finalize(stmt);
186 /* Commit changes to the database and close. */
187 rc = sqlite3_exec(db, "commit", NULL, NULL, NULL);
188 if (rc != SQLITE_OK) {
189 fprintf(stderr, "DATABASE ERROR: Can't commit database!\n");
195 int64_t LocalDb::SegmentToId(const string &segment)
201 stmt = Prepare("insert or ignore into segments(segment) values (?)");
202 sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
204 rc = sqlite3_step(stmt);
205 if (rc != SQLITE_DONE) {
206 fatal("Could not execute INSERT statement!");
208 sqlite3_finalize(stmt);
210 stmt = Prepare("select segmentid from segments where segment = ?");
211 sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
214 rc = sqlite3_step(stmt);
215 if (rc == SQLITE_DONE) {
216 fatal("No segment found by id");
217 } else if (rc == SQLITE_ROW) {
218 result = sqlite3_column_int64(stmt, 0);
220 fatal("Error executing find segment by id query");
223 sqlite3_finalize(stmt);
228 string LocalDb::IdToSegment(int64_t segmentid)
234 stmt = Prepare("select segment from segments where segmentid = ?");
235 sqlite3_bind_int64(stmt, 1, segmentid);
237 rc = sqlite3_step(stmt);
238 if (rc == SQLITE_DONE) {
239 fatal("No segment found by id");
240 } else if (rc == SQLITE_ROW) {
241 result = (const char *)sqlite3_column_text(stmt, 0);
243 fatal("Error executing find segment by id query");
246 sqlite3_finalize(stmt);
251 void LocalDb::StoreObject(const ObjectReference& ref, double age)
256 assert(ref.has_checksum());
257 string checksum = ref.get_checksum();
258 assert(ref.range_is_exact());
259 int64_t size = ref.get_range_length();
262 stmt = Prepare("insert into block_index("
263 "segmentid, object, checksum, size, timestamp) "
264 "values (?, ?, ?, ?, julianday('now'))");
266 stmt = Prepare("insert into block_index("
267 "segmentid, object, checksum, size, timestamp) "
268 "values (?, ?, ?, ?, ?)");
271 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
272 string obj = ref.get_sequence();
273 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
274 sqlite3_bind_text(stmt, 3, checksum.c_str(), checksum.size(),
276 sqlite3_bind_int64(stmt, 4, size);
278 sqlite3_bind_double(stmt, 5, age);
280 rc = sqlite3_step(stmt);
281 if (rc != SQLITE_DONE) {
282 fprintf(stderr, "Could not execute INSERT statement!\n");
286 sqlite3_finalize(stmt);
289 ObjectReference LocalDb::FindObject(const string &checksum, int64_t size)
295 stmt = Prepare("select segmentid, object from block_index "
296 "where checksum = ? and size = ? and expired is null");
297 sqlite3_bind_text(stmt, 1, checksum.c_str(), checksum.size(),
299 sqlite3_bind_int64(stmt, 2, size);
301 rc = sqlite3_step(stmt);
302 if (rc == SQLITE_DONE) {
303 } else if (rc == SQLITE_ROW) {
304 ref = ObjectReference(IdToSegment(sqlite3_column_int64(stmt, 0)),
305 (const char *)sqlite3_column_text(stmt, 1));
306 ref.set_range(0, size, true);
308 fprintf(stderr, "Could not execute SELECT statement!\n");
312 sqlite3_finalize(stmt);
317 bool LocalDb::IsOldObject(const string &checksum, int64_t size, double *age,
324 stmt = Prepare("select segmentid, object, julianday(timestamp), expired "
325 "from block_index where checksum = ? and size = ?");
326 sqlite3_bind_text(stmt, 1, checksum.c_str(), checksum.size(),
328 sqlite3_bind_int64(stmt, 2, size);
330 rc = sqlite3_step(stmt);
331 if (rc == SQLITE_DONE) {
333 } else if (rc == SQLITE_ROW) {
335 *age = sqlite3_column_double(stmt, 2);
336 *group = sqlite3_column_int(stmt, 3);
338 fprintf(stderr, "Could not execute SELECT statement!\n");
342 sqlite3_finalize(stmt);
347 /* Does this object still exist in the database (and not expired)? */
348 bool LocalDb::IsAvailable(const ObjectReference &ref)
354 // Special objects (such as the zero object) aren't stored in segments, and
355 // so are always available.
356 if (!ref.is_normal())
359 stmt = Prepare("select count(*) from block_index "
360 "where segmentid = ? and object = ? and expired is null");
361 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
362 sqlite3_bind_text(stmt, 2, ref.get_sequence().c_str(),
363 ref.get_sequence().size(), SQLITE_TRANSIENT);
365 rc = sqlite3_step(stmt);
366 if (rc == SQLITE_DONE) {
368 } else if (rc == SQLITE_ROW) {
369 if (sqlite3_column_int(stmt, 0) > 0)
372 fprintf(stderr, "Could not execute SELECT statement!\n");
376 sqlite3_finalize(stmt);
381 set<string> LocalDb::GetUsedSegments()
387 stmt = Prepare("select segment from segments "
388 "where segmentid in (select segmentid from snapshot_refs)");
391 rc = sqlite3_step(stmt);
392 if (rc == SQLITE_ROW) {
394 = reinterpret_cast<const char *>(sqlite3_column_text(stmt, 0));
395 result.insert(segment);
396 } else if (rc == SQLITE_DONE) {
403 sqlite3_finalize(stmt);
408 void LocalDb::UseObject(const ObjectReference& ref)
413 if (!ref.is_normal())
416 int64_t old_size = 0;
417 stmt = Prepare("select size from snapshot_refs "
418 "where segmentid = ? and object = ?");
419 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
420 string obj = ref.get_sequence();
421 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
422 rc = sqlite3_step(stmt);
423 if (rc == SQLITE_ROW) {
424 old_size = sqlite3_column_int64(stmt, 0);
426 sqlite3_finalize(stmt);
428 // Attempt to determine the underlying size of the object. This may
429 // require a database lookup if the length is not encoded into the object
430 // reference already.
431 int64_t object_size = 0;
432 if (ref.range_is_exact()) {
433 object_size = ref.get_range_length();
435 stmt = Prepare("select size from block_index "
436 "where segmentid = ? and object = ?");
437 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
438 obj = ref.get_sequence();
439 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
440 rc = sqlite3_step(stmt);
441 if (rc == SQLITE_ROW) {
442 object_size = sqlite3_column_int64(stmt, 0);
444 fprintf(stderr, "Warning: No block found in block_index for %s\n",
445 ref.to_string().c_str());
447 sqlite3_finalize(stmt);
450 // Possibly mark additional bytes as being referenced. The number of bytes
451 // referenced can only be increased (up to the object size). The bytes
452 // referenced will be set to the object size only if the entire object is
453 // referenced at once: a series of partial ranges that add up to the total
454 // size will have a reference size capped at just less than the full object
455 // size (we can't tell if some bytes were referenced multiple times, and
456 // thus we conservatively assume some bytes might still be unreferenced).
458 if (ref.has_range()) {
459 new_refs = ref.get_range_length();
461 new_refs = object_size;
463 int64_t new_size = old_size + new_refs;
464 if (old_size < object_size && new_refs < object_size)
465 new_size = min(new_size, object_size - 1);
466 new_size = min(object_size, new_size);
467 new_size = max(new_size, (int64_t)0);
469 if (new_size != old_size) {
470 stmt = Prepare("insert or replace "
471 "into snapshot_refs(segmentid, object, size) "
473 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
474 obj = ref.get_sequence();
475 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
476 sqlite3_bind_int64(stmt, 3, new_size);
478 rc = sqlite3_step(stmt);
479 if (rc != SQLITE_DONE) {
480 fprintf(stderr, "Could not execute INSERT statement!\n");
484 sqlite3_finalize(stmt);
488 void LocalDb::SetSegmentMetadata(const std::string &segment,
489 const std::string &path,
490 const std::string &checksum,
491 const std::string &type,
492 int data_size, int disk_size)
497 stmt = Prepare("update segments set path = ?, checksum = ?, "
498 "type = ?, data_size = ?, disk_size = ?, "
499 "timestamp = coalesce(julianday(timestamp), "
500 " julianday('now')) "
501 "where segmentid = ?");
502 sqlite3_bind_text(stmt, 1, path.c_str(), path.size(),
504 sqlite3_bind_text(stmt, 2, checksum.c_str(), checksum.size(),
506 sqlite3_bind_text(stmt, 3, type.c_str(), type.size(),
508 sqlite3_bind_int64(stmt, 4, data_size);
509 sqlite3_bind_int64(stmt, 5, disk_size);
510 sqlite3_bind_int64(stmt, 6, SegmentToId(segment));
512 rc = sqlite3_step(stmt);
513 if (rc != SQLITE_DONE) {
514 fprintf(stderr, "Could not update segment checksum in database!\n");
518 sqlite3_finalize(stmt);
521 map<string, string> LocalDb::GetSegmentMetadata(const string &segment)
525 map<string, string> info;
527 // Names in the returned map, in the order returned from the select
529 static const char *fields[] = {
530 "datetime", "path", "checksum", "data_size", "disk_size", "type", NULL
533 stmt = Prepare("select datetime(timestamp), path, checksum, "
534 " data_size, disk_size, type "
535 "from segments where segment = ?");
536 sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
539 rc = sqlite3_step(stmt);
540 if (rc == SQLITE_DONE) {
541 } else if (rc == SQLITE_ROW) {
542 info["segment"] = segment;
543 for (int i = 0; fields[i] != NULL; i++) {
544 const char *val = (const char *)sqlite3_column_text(stmt, i);
546 info[fields[i]] = val;
549 fprintf(stderr, "Could not execute SELECT statement!\n");
553 sqlite3_finalize(stmt);
558 /* Look up and return the packed representation of the subblock chunk
559 * signatures. Returns true if signatures were found for the specified object,
560 * and if so sets *buf to point at a buffer of memory (allocated with malloc;
561 * the caller should free it), and *len to the length of the buffer. */
562 bool LocalDb::LoadChunkSignatures(ObjectReference ref,
563 void **buf, size_t *len,
570 stmt = Prepare("select signatures, algorithm from subblock_signatures "
571 "where blockid = (select blockid from block_index "
572 " where segmentid = ? and object = ?)");
573 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
574 string obj = ref.get_sequence();
575 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
577 rc = sqlite3_step(stmt);
578 if (rc == SQLITE_DONE) {
579 } else if (rc == SQLITE_ROW) {
580 const void *data = sqlite3_column_blob(stmt, 0);
581 *len = sqlite3_column_bytes(stmt, 0);
586 memcpy(*buf, data, *len);
587 *algorithm = (const char *)sqlite3_column_text(stmt, 1);
592 fprintf(stderr, "Could not execute SELECT statement!\n");
596 sqlite3_finalize(stmt);
601 /* Store the subblock chunk signatures for a specified object. The object
602 * itself must have already been indexed in the database. */
603 void LocalDb::StoreChunkSignatures(ObjectReference ref,
604 const void *buf, size_t len,
605 const string& algorithm)
610 stmt = Prepare("select blockid from block_index "
611 "where segmentid = ? and object = ?");
612 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
613 string obj = ref.get_sequence();
614 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
616 rc = sqlite3_step(stmt);
617 if (rc != SQLITE_ROW) {
619 "Could not determine blockid in StoreChunkSignatures!\n");
621 fatal("Error getting blockid");
623 int64_t blockid = sqlite3_column_int64(stmt, 0);
624 sqlite3_finalize(stmt);
626 stmt = Prepare("insert or replace "
627 "into subblock_signatures(blockid, algorithm, signatures) "
629 sqlite3_bind_int64(stmt, 1, blockid);
630 sqlite3_bind_text(stmt, 2, algorithm.c_str(), algorithm.size(),
632 sqlite3_bind_blob(stmt, 3, buf, len, SQLITE_TRANSIENT);
634 rc = sqlite3_step(stmt);
635 if (rc != SQLITE_DONE) {
636 fprintf(stderr, "Could not insert sub-block checksums!\n");
640 sqlite3_finalize(stmt);