README updates: explain restores in more detail.
[cumulus.git] / localdb.cc
1 /* Cumulus: Smart Filesystem Backup to Dumb Servers
2  *
3  * Copyright (C) 2007-2008  The Regents of the University of California
4  * Written by Michael Vrable <mvrable@cs.ucsd.edu>
5  *
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.
10  *
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.
15  *
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.
19  */
20
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.
25  *
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
28  * changed later. */
29
30 #include <assert.h>
31 #include <stdio.h>
32 #include <string.h>
33 #include <sqlite3.h>
34
35 #include <algorithm>
36 #include <string>
37
38 #include "localdb.h"
39 #include "store.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         throw IOException(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         throw IOException("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         throw IOException("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         throw IOException("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         throw IOException("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         throw IOException("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         throw IOException("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         throw IOException("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         throw IOException("No segment found by id");
201     } else if (rc == SQLITE_ROW) {
202         result = sqlite3_column_int64(stmt, 0);
203     } else {
204         throw IOException("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         throw IOException("No segment found by id");
224     } else if (rc == SQLITE_ROW) {
225         result = (const char *)sqlite3_column_text(stmt, 0);
226     } else {
227         throw IOException("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);
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         throw IOException("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 }