1 /* Cumulus: Smart Filesystem Backup to Dumb Servers
3 * Copyright (C) 2007-2008 The Regents of the University of California
4 * Written by Michael Vrable <mvrable@cs.ucsd.edu>
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, write to the Free Software Foundation, Inc.,
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 /* When creating backup snapshots, maintain a local database of data blocks and
22 * checksums, in addition to the data contents (which may be stored remotely).
23 * This database is consulted when attempting to build incremental snapshots,
24 * as it says which objects can be reused.
26 * The database is implemented as an SQLite3 database, but this implementation
27 * detail is kept internal to this file, so that the storage format may be
45 /* Helper function to prepare a statement for execution in the current
47 sqlite3_stmt *LocalDb::Prepare(const char *sql)
53 rc = sqlite3_prepare_v2(db, sql, strlen(sql), &stmt, &tail);
54 if (rc != SQLITE_OK) {
56 fatal(string("Error preparing statement: ") + sql);
62 void LocalDb::ReportError(int rc)
64 fprintf(stderr, "Result code: %d\n", rc);
65 fprintf(stderr, "Error message: %s\n", sqlite3_errmsg(db));
68 void LocalDb::Open(const char *path, const char *snapshot_name,
69 const char *snapshot_scheme, double intent)
73 rc = sqlite3_open(path, &db);
75 fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
77 fatal("Error opening local database");
80 rc = sqlite3_exec(db, "begin", NULL, NULL, NULL);
82 fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db));
84 fatal("Error starting transaction");
87 sqlite3_extended_result_codes(db, 1);
89 if (snapshot_scheme == NULL)
92 /* Insert this snapshot into the database, and determine the integer key
93 * which will be used to identify it. */
94 sqlite3_stmt *stmt = Prepare("insert into "
95 "snapshots(name, scheme, timestamp, intent) "
96 "values (?, ?, julianday('now'), ?)");
97 sqlite3_bind_text(stmt, 1, snapshot_name, strlen(snapshot_name),
99 sqlite3_bind_text(stmt, 2, snapshot_scheme, strlen(snapshot_scheme),
101 sqlite3_bind_double(stmt, 3, intent);
103 rc = sqlite3_step(stmt);
104 if (rc != SQLITE_DONE) {
107 fatal("Database execution error!");
110 snapshotid = sqlite3_last_insert_rowid(db);
111 sqlite3_finalize(stmt);
112 if (snapshotid == 0) {
115 fatal("Find snapshot id");
118 /* Create a temporary table which will be used to keep track of the objects
119 * used by this snapshot. When the database is closed, we will summarize
120 * the results of this table into segments_used. */
121 rc = sqlite3_exec(db,
122 "create temporary table snapshot_refs ("
123 " segmentid integer not null,"
124 " object text not null,"
125 " size integer not null"
126 ")", NULL, NULL, NULL);
127 if (rc != SQLITE_OK) {
130 fatal("Database initialization");
132 rc = sqlite3_exec(db,
133 "create unique index snapshot_refs_index "
134 "on snapshot_refs(segmentid, object)",
136 if (rc != SQLITE_OK) {
139 fatal("Database initialization");
143 void LocalDb::Close()
147 /* Summarize the snapshot_refs table into segments_used. */
148 sqlite3_stmt *stmt = Prepare(
149 "insert or replace into segments_used "
150 "select ? as snapshotid, segmentid, max(utilization) from ("
151 " select segmentid, cast(used as real) / size as utilization "
153 " (select segmentid, sum(size) as used from snapshot_refs "
154 " group by segmentid) "
155 " join segments using (segmentid) "
157 " select segmentid, utilization from segments_used "
158 " where snapshotid = ? "
159 ") group by segmentid"
161 sqlite3_bind_int64(stmt, 1, snapshotid);
162 sqlite3_bind_int64(stmt, 2, snapshotid);
163 rc = sqlite3_step(stmt);
164 if (rc != SQLITE_OK && rc != SQLITE_DONE) {
167 fprintf(stderr, "DATABASE ERROR: Unable to create segment summary!\n");
169 sqlite3_finalize(stmt);
171 /* Commit changes to the database and close. */
172 rc = sqlite3_exec(db, "commit", NULL, NULL, NULL);
173 if (rc != SQLITE_OK) {
174 fprintf(stderr, "DATABASE ERROR: Can't commit database!\n");
180 int64_t LocalDb::SegmentToId(const string &segment)
186 stmt = Prepare("insert or ignore into segments(segment) values (?)");
187 sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
189 rc = sqlite3_step(stmt);
190 if (rc != SQLITE_DONE) {
191 fatal("Could not execute INSERT statement!");
193 sqlite3_finalize(stmt);
195 stmt = Prepare("select segmentid from segments where segment = ?");
196 sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
199 rc = sqlite3_step(stmt);
200 if (rc == SQLITE_DONE) {
201 fatal("No segment found by id");
202 } else if (rc == SQLITE_ROW) {
203 result = sqlite3_column_int64(stmt, 0);
205 fatal("Error executing find segment by id query");
208 sqlite3_finalize(stmt);
213 string LocalDb::IdToSegment(int64_t segmentid)
219 stmt = Prepare("select segment from segments where segmentid = ?");
220 sqlite3_bind_int64(stmt, 1, segmentid);
222 rc = sqlite3_step(stmt);
223 if (rc == SQLITE_DONE) {
224 fatal("No segment found by id");
225 } else if (rc == SQLITE_ROW) {
226 result = (const char *)sqlite3_column_text(stmt, 0);
228 fatal("Error executing find segment by id query");
231 sqlite3_finalize(stmt);
236 void LocalDb::StoreObject(const ObjectReference& ref,
237 const string &checksum, int64_t size,
244 stmt = Prepare("insert into block_index("
245 "segmentid, object, checksum, size, timestamp) "
246 "values (?, ?, ?, ?, julianday('now'))");
248 stmt = Prepare("insert into block_index("
249 "segmentid, object, checksum, size, timestamp) "
250 "values (?, ?, ?, ?, ?)");
253 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
254 string obj = ref.get_sequence();
255 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
256 sqlite3_bind_text(stmt, 3, checksum.c_str(), checksum.size(),
258 sqlite3_bind_int64(stmt, 4, size);
260 sqlite3_bind_double(stmt, 5, age);
262 rc = sqlite3_step(stmt);
263 if (rc != SQLITE_DONE) {
264 fprintf(stderr, "Could not execute INSERT statement!\n");
268 sqlite3_finalize(stmt);
271 stmt = Prepare("update segments "
272 "set mtime = coalesce(max(mtime, ?), ?) "
273 "where segmentid = ?");
274 sqlite3_bind_double(stmt, 1, age);
275 sqlite3_bind_double(stmt, 2, age);
276 sqlite3_bind_int64(stmt, 3, SegmentToId(ref.get_segment()));
277 rc = sqlite3_step(stmt);
278 sqlite3_finalize(stmt);
282 ObjectReference LocalDb::FindObject(const string &checksum, int64_t size)
288 stmt = Prepare("select segmentid, object from block_index "
289 "where checksum = ? and size = ? and expired is null");
290 sqlite3_bind_text(stmt, 1, checksum.c_str(), checksum.size(),
292 sqlite3_bind_int64(stmt, 2, size);
294 rc = sqlite3_step(stmt);
295 if (rc == SQLITE_DONE) {
296 } else if (rc == SQLITE_ROW) {
297 ref = ObjectReference(IdToSegment(sqlite3_column_int64(stmt, 0)),
298 (const char *)sqlite3_column_text(stmt, 1));
299 ref.set_range(0, size, true);
301 fprintf(stderr, "Could not execute SELECT statement!\n");
305 sqlite3_finalize(stmt);
310 bool LocalDb::IsOldObject(const string &checksum, int64_t size, double *age,
317 stmt = Prepare("select segmentid, object, timestamp, expired "
318 "from block_index where checksum = ? and size = ?");
319 sqlite3_bind_text(stmt, 1, checksum.c_str(), checksum.size(),
321 sqlite3_bind_int64(stmt, 2, size);
323 rc = sqlite3_step(stmt);
324 if (rc == SQLITE_DONE) {
326 } else if (rc == SQLITE_ROW) {
328 *age = sqlite3_column_double(stmt, 2);
329 *group = sqlite3_column_int(stmt, 3);
331 fprintf(stderr, "Could not execute SELECT statement!\n");
335 sqlite3_finalize(stmt);
340 /* Does this object still exist in the database (and not expired)? */
341 bool LocalDb::IsAvailable(const ObjectReference &ref)
347 // Special objects (such as the zero object) aren't stored in segments, and
348 // so are always available.
349 if (!ref.is_normal())
352 stmt = Prepare("select count(*) from block_index "
353 "where segmentid = ? and object = ? and expired is null");
354 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
355 sqlite3_bind_text(stmt, 2, ref.get_sequence().c_str(),
356 ref.get_sequence().size(), SQLITE_TRANSIENT);
358 rc = sqlite3_step(stmt);
359 if (rc == SQLITE_DONE) {
361 } else if (rc == SQLITE_ROW) {
362 if (sqlite3_column_int(stmt, 0) > 0)
365 fprintf(stderr, "Could not execute SELECT statement!\n");
369 sqlite3_finalize(stmt);
374 void LocalDb::UseObject(const ObjectReference& ref)
379 if (!ref.is_normal())
382 int64_t old_size = 0;
383 stmt = Prepare("select size from snapshot_refs "
384 "where segmentid = ? and object = ?");
385 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
386 string obj = ref.get_sequence();
387 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
388 rc = sqlite3_step(stmt);
389 if (rc == SQLITE_ROW) {
390 old_size = sqlite3_column_int64(stmt, 0);
392 sqlite3_finalize(stmt);
394 int64_t block_size = 0;
395 stmt = Prepare("select size from block_index "
396 "where segmentid = ? and object = ?");
397 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
398 obj = ref.get_sequence();
399 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
400 rc = sqlite3_step(stmt);
401 if (rc == SQLITE_ROW) {
402 block_size = sqlite3_column_int64(stmt, 0);
404 string refstr = ref.to_string();
405 fprintf(stderr, "No block found in block_index for %s\n",
407 sqlite3_finalize(stmt);
410 sqlite3_finalize(stmt);
412 int64_t new_size = old_size;
413 if (ref.has_range()) {
414 new_size += ref.get_range_length();
415 new_size = min(new_size, block_size);
417 new_size = block_size;
420 if (new_size != old_size) {
421 stmt = Prepare("insert or replace "
422 "into snapshot_refs(segmentid, object, size) "
424 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
425 obj = ref.get_sequence();
426 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
427 sqlite3_bind_int64(stmt, 3, new_size);
429 rc = sqlite3_step(stmt);
430 if (rc != SQLITE_DONE) {
431 fprintf(stderr, "Could not execute INSERT statement!\n");
435 sqlite3_finalize(stmt);
439 void LocalDb::UseSegment(const std::string &segment, double utilization)
444 stmt = Prepare("insert or replace "
445 "into segments_used(snapshotid, segmentid, utilization) "
447 sqlite3_bind_int64(stmt, 1, snapshotid);
448 sqlite3_bind_int64(stmt, 2, SegmentToId(segment));
449 sqlite3_bind_double(stmt, 3, utilization);
451 rc = sqlite3_step(stmt);
452 if (rc != SQLITE_DONE) {
453 fprintf(stderr, "Could not insert segment use record!\n");
457 sqlite3_finalize(stmt);
460 void LocalDb::SetSegmentChecksum(const std::string &segment,
461 const std::string &path,
462 const std::string &checksum,
468 stmt = Prepare("update segments set path = ?, checksum = ?, size = ?, "
469 "mtime = coalesce(mtime, julianday('now')) "
470 "where segmentid = ?");
471 sqlite3_bind_text(stmt, 1, path.c_str(), path.size(),
473 sqlite3_bind_text(stmt, 2, checksum.c_str(), checksum.size(),
475 sqlite3_bind_int64(stmt, 3, size);
476 sqlite3_bind_int64(stmt, 4, SegmentToId(segment));
478 rc = sqlite3_step(stmt);
479 if (rc != SQLITE_DONE) {
480 fprintf(stderr, "Could not update segment checksum in database!\n");
484 sqlite3_finalize(stmt);
487 bool LocalDb::GetSegmentChecksum(const string &segment,
489 string *seg_checksum)
496 stmt = Prepare("select path, checksum from segments where segment = ?");
497 sqlite3_bind_text(stmt, 1, segment.c_str(), segment.size(),
500 rc = sqlite3_step(stmt);
501 if (rc == SQLITE_DONE) {
502 } else if (rc == SQLITE_ROW) {
506 val = (const char *)sqlite3_column_text(stmt, 0);
512 val = (const char *)sqlite3_column_text(stmt, 1);
518 fprintf(stderr, "Could not execute SELECT statement!\n");
522 sqlite3_finalize(stmt);
527 /* Look up and return the packed representation of the subblock chunk
528 * signatures. Returns true if signatures were found for the specified object,
529 * and if so sets *buf to point at a buffer of memory (allocated with malloc;
530 * the caller should free it), and *len to the length of the buffer. */
531 bool LocalDb::LoadChunkSignatures(ObjectReference ref,
532 void **buf, size_t *len,
539 stmt = Prepare("select signatures, algorithm from subblock_signatures "
540 "where blockid = (select blockid from block_index "
541 " where segmentid = ? and object = ?)");
542 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
543 string obj = ref.get_sequence();
544 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
546 rc = sqlite3_step(stmt);
547 if (rc == SQLITE_DONE) {
548 } else if (rc == SQLITE_ROW) {
549 const void *data = sqlite3_column_blob(stmt, 0);
550 *len = sqlite3_column_bytes(stmt, 0);
555 memcpy(*buf, data, *len);
556 *algorithm = (const char *)sqlite3_column_text(stmt, 1);
561 fprintf(stderr, "Could not execute SELECT statement!\n");
565 sqlite3_finalize(stmt);
570 /* Store the subblock chunk signatures for a specified object. The object
571 * itself must have already been indexed in the database. */
572 void LocalDb::StoreChunkSignatures(ObjectReference ref,
573 const void *buf, size_t len,
574 const string& algorithm)
579 stmt = Prepare("select blockid from block_index "
580 "where segmentid = ? and object = ?");
581 sqlite3_bind_int64(stmt, 1, SegmentToId(ref.get_segment()));
582 string obj = ref.get_sequence();
583 sqlite3_bind_text(stmt, 2, obj.c_str(), obj.size(), SQLITE_TRANSIENT);
585 rc = sqlite3_step(stmt);
586 if (rc != SQLITE_ROW) {
588 "Could not determine blockid in StoreChunkSignatures!\n");
590 fatal("Error getting blockid");
592 int64_t blockid = sqlite3_column_int64(stmt, 0);
593 sqlite3_finalize(stmt);
595 stmt = Prepare("insert or replace "
596 "into subblock_signatures(blockid, algorithm, signatures) "
598 sqlite3_bind_int64(stmt, 1, blockid);
599 sqlite3_bind_text(stmt, 2, algorithm.c_str(), algorithm.size(),
601 sqlite3_bind_blob(stmt, 3, buf, len, SQLITE_TRANSIENT);
603 rc = sqlite3_step(stmt);
604 if (rc != SQLITE_DONE) {
605 fprintf(stderr, "Could not insert sub-block checksums!\n");
609 sqlite3_finalize(stmt);