Fix an example command in the README.
[cumulus.git] / metadata.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 /* Handling of metadata written to backup snapshots.  This manages the writing
22  * of file metadata into new backup snapshots, including breaking the metadata
23  * log apart across separate objects.  Eventually this should include unified
24  * handling of the statcache, and re-use of metadata between snapshots.
25  */
26
27 #include <string>
28 #include <iostream>
29 #include <map>
30
31 #include "metadata.h"
32 #include "localdb.h"
33 #include "ref.h"
34 #include "store.h"
35 #include "util.h"
36
37 using std::list;
38 using std::map;
39 using std::string;
40 using std::ostream;
41 using std::ostringstream;
42
43 static const size_t LBS_METADATA_BLOCK_SIZE = 65536;
44
45 // If true, forces a full write of metadata: will not include pointers to
46 // metadata in old snapshots.
47 bool flag_full_metadata = false;
48
49 /* TODO: Move to header file */
50 extern LocalDb *db;
51 void add_segment(const string& segment);
52
53 /* Like strcmp, but sorts in the order that files will be visited in the
54  * filesystem.  That is, we break paths apart at slashes, and compare path
55  * components separately. */
56 static int pathcmp(const char *path1, const char *path2)
57 {
58     /* Find the first component in each path. */
59     const char *slash1 = strchr(path1, '/');
60     const char *slash2 = strchr(path2, '/');
61
62     {
63         string comp1, comp2;
64         if (slash1 == NULL)
65             comp1 = path1;
66         else
67             comp1 = string(path1, slash1 - path1);
68
69         if (slash2 == NULL)
70             comp2 = path2;
71         else
72             comp2 = string(path2, slash2 - path2);
73
74         /* Directly compare the two components first. */
75         if (comp1 < comp2)
76             return -1;
77         if (comp1 > comp2)
78             return 1;
79     }
80
81     if (slash1 == NULL && slash2 == NULL)
82         return 0;
83     if (slash1 == NULL)
84         return -1;
85     if (slash2 == NULL)
86         return 1;
87
88     return pathcmp(slash1 + 1, slash2 + 1);
89 }
90
91 /* Encode a dictionary of string key/value pairs into a sequence of lines of
92  * the form "key: value".  If it exists, the key "name" is treated specially
93  * and will be listed first. */
94 static string encode_dict(const map<string, string>& dict)
95 {
96     string result;
97
98     if (dict.find("name") != dict.end()) {
99         result += "name: " + dict.at("name") + "\n";
100     }
101
102     for (map<string, string>::const_iterator i = dict.begin();
103          i != dict.end(); ++i) {
104         if (i->first == "name")
105             continue;
106         result += i->first + ": " + i->second + "\n";
107     }
108
109     return result;
110 }
111
112 MetadataWriter::MetadataWriter(TarSegmentStore *store,
113                                const char *path,
114                                const char *snapshot_name,
115                                const char *snapshot_scheme)
116 {
117     statcache_path = path;
118     statcache_path += "/statcache2";
119     if (snapshot_scheme != NULL && strlen(snapshot_scheme) > 0)
120         statcache_path = statcache_path + "-" + snapshot_scheme;
121     statcache_tmp_path = statcache_path + "." + snapshot_name;
122
123     statcache_in = fopen(statcache_path.c_str(), "r");
124
125     statcache_out = fopen(statcache_tmp_path.c_str(), "w");
126     if (statcache_out == NULL) {
127         fprintf(stderr, "Error opening statcache %s: %m\n",
128                 statcache_tmp_path.c_str());
129         throw IOException("Error opening statcache");
130     }
131
132     old_metadata_eof = false;
133
134     this->store = store;
135     chunk_size = 0;
136 }
137
138 /* Read the next entry from the old statcache file, loading it into
139  * old_metadata. */
140 void MetadataWriter::read_statcache()
141 {
142     if (statcache_in == NULL) {
143         old_metadata_eof = true;
144         return;
145     }
146
147     old_metadata.clear();
148
149     char *buf = NULL;
150     size_t n = 0;
151     string field = "";          // Last field to be read in
152
153     /* Look for a first line starting with "@@", which tells where the metadata
154      * can be found in the metadata log of an old snapshot. */
155     if (getline(&buf, &n, statcache_in) < 0
156         || buf == NULL || buf[0] != '@' || buf[1] != '@') {
157         old_metadata_eof = true;
158         return;
159     }
160
161     if (strchr(buf, '\n') != NULL)
162         *strchr(buf, '\n') = '\0';
163     old_metadata_loc = buf + 2;
164
165     /* After the initial line follows the metadata, as key-value pairs. */
166     while (!feof(statcache_in)) {
167         if (getline(&buf, &n, statcache_in) < 0)
168             break;
169
170         char *eol = strchr(buf, '\n');
171         if (eol != NULL)
172             *eol = '\0';
173
174         /* Is the line blank?  If so, we have reached the end of this entry. */
175         if (buf[0] == '\0')
176             break;
177
178         /* Is this a continuation line?  (Does it start with whitespace?) */
179         if (isspace(buf[0]) && field != "") {
180             old_metadata[field] += string("\n") + buf;
181             continue;
182         }
183
184         /* For lines of the form "Key: Value" look for ':' and split the line
185          * apart. */
186         char *value = strchr(buf, ':');
187         if (value == NULL)
188             continue;
189         *value = '\0';
190         field = buf;
191
192         value++;
193         while (isspace(*value))
194             value++;
195
196         old_metadata[field] = value;
197     }
198
199     if (feof(statcache_in) && old_metadata.size() == 0) {
200         old_metadata_eof = true;
201     }
202
203     free(buf);
204 }
205
206 bool MetadataWriter::find(const string& path)
207 {
208     const char *path_str = path.c_str();
209     while (!old_metadata_eof) {
210         string old_path = uri_decode(old_metadata["name"]);
211         int cmp = pathcmp(old_path.c_str(), path_str);
212         if (cmp == 0)
213             return true;
214         else if (cmp > 0)
215             return false;
216         else
217             read_statcache();
218     }
219
220     return false;
221 }
222
223 /* Does a file appear to be unchanged from the previous time it was backed up,
224  * based on stat information? */
225 bool MetadataWriter::is_unchanged(const struct stat *stat_buf)
226 {
227     if (old_metadata.find("volatile") != old_metadata.end()
228         && parse_int(old_metadata["volatile"]) != 0)
229         return false;
230
231     if (old_metadata.find("ctime") == old_metadata.end())
232         return false;
233     if (stat_buf->st_ctime != parse_int(old_metadata["ctime"]))
234         return false;
235
236     if (old_metadata.find("mtime") == old_metadata.end())
237         return false;
238     if (stat_buf->st_mtime != parse_int(old_metadata["mtime"]))
239         return false;
240
241     if (old_metadata.find("size") == old_metadata.end())
242         return false;
243     if (stat_buf->st_size != parse_int(old_metadata["size"]))
244         return false;
245
246     if (old_metadata.find("inode") == old_metadata.end())
247         return false;
248     string inode = encode_int(major(stat_buf->st_dev))
249         + "/" + encode_int(minor(stat_buf->st_dev))
250         + "/" + encode_int(stat_buf->st_ino);
251     if (inode != old_metadata["inode"])
252         return false;
253
254     return true;
255 }
256
257 list<ObjectReference> MetadataWriter::get_blocks()
258 {
259     list<ObjectReference> blocks;
260
261     /* Parse the list of blocks. */
262     const char *s = old_metadata["data"].c_str();
263     while (*s != '\0') {
264         if (isspace(*s)) {
265             s++;
266             continue;
267         }
268
269         string ref = "";
270         while (*s != '\0' && !isspace(*s)) {
271             char buf[2];
272             buf[0] = *s;
273             buf[1] = '\0';
274             ref += buf;
275             s++;
276         }
277
278         ObjectReference r = ObjectReference::parse(ref);
279         if (!r.is_null())
280             blocks.push_back(r);
281     }
282
283     return blocks;
284 }
285
286 /* Ensure contents of metadata are flushed to an object. */
287 void MetadataWriter::metadata_flush()
288 {
289     int offset = 0;
290
291     ostringstream metadata;
292     ObjectReference indirect;
293     for (list<MetadataItem>::iterator i = items.begin();
294          i != items.end(); ++i) {
295         // If indirectly referencing any other metadata logs, be sure those
296         // segments are properly referenced.
297         if (i->reused) {
298             add_segment(i->ref.get_segment());
299             db->UseSegment(i->ref.get_segment(), 1.0);
300         }
301
302         // Write out an indirect reference to any previous objects which could
303         // be reused
304         if (!i->reused || !indirect.merge(i->ref)) {
305             if (!indirect.is_null()) {
306                 string refstr = indirect.to_string();
307                 metadata << "@" << refstr << "\n";
308                 offset += refstr.size() + 2;
309                 if (!i->reused) {
310                     metadata << "\n";
311                     offset += 1;
312                 }
313             }
314             if (i->reused)
315                 indirect = i->ref;
316             else
317                 indirect = ObjectReference();
318         }
319
320         if (!i->reused) {
321             metadata << i->text;
322             i->offset = offset;
323             offset += i->text.size();
324         }
325     }
326     if (!indirect.is_null()) {
327         string refstr = indirect.to_string();
328         metadata << "@" << refstr << "\n";
329         offset += refstr.size() + 2;
330         indirect = ObjectReference();
331     }
332
333     string m = metadata.str();
334     if (m.size() == 0)
335         return;
336
337     /* Write current metadata information to a new object. */
338     LbsObject *meta = new LbsObject;
339     meta->set_group("metadata");
340     meta->set_data(m.data(), m.size());
341     meta->write(store);
342     meta->checksum();
343
344     /* Write a reference to this block in the root. */
345     ObjectReference ref = meta->get_ref();
346     metadata_root << "@" << ref.to_string() << "\n";
347     add_segment(ref.get_segment());
348     db->UseSegment(ref.get_segment(), 1.0);
349
350     delete meta;
351
352     /* Write these files out to the statcache, and include a reference to where
353      * the metadata lives (so we can re-use it if it has not changed). */
354     for (list<MetadataItem>::const_iterator i = items.begin();
355          i != items.end(); ++i) {
356         ObjectReference r = ref;
357         r.set_range(i->offset, i->text.size());
358
359         if (i->reused)
360             r = i->ref;
361
362         string refstr = r.to_string();
363         fprintf(statcache_out, "@@%s\n%s", refstr.c_str(), i->text.c_str());
364     }
365
366     chunk_size = 0;
367     items.clear();
368 }
369
370 void MetadataWriter::add(dictionary info)
371 {
372     MetadataItem item;
373     item.offset = 0;
374     item.reused = false;
375     item.text += encode_dict(info) + "\n";
376
377     if (info == old_metadata && !flag_full_metadata) {
378         ObjectReference ref = ObjectReference::parse(old_metadata_loc);
379         if (!ref.is_null()) {
380             item.reused = true;
381             item.ref = ref;
382         }
383     }
384
385     items.push_back(item);
386     chunk_size += item.text.size();
387
388     if (chunk_size > LBS_METADATA_BLOCK_SIZE)
389         metadata_flush();
390 }
391
392 ObjectReference MetadataWriter::close()
393 {
394     metadata_flush();
395     const string root_data = metadata_root.str();
396
397     LbsObject *root = new LbsObject;
398     root->set_group("metadata");
399     root->set_data(root_data.data(), root_data.size());
400     root->write(store);
401     root->checksum();
402     add_segment(root->get_ref().get_segment());
403     db->UseSegment(root->get_ref().get_segment(), 1.0);
404
405     ObjectReference ref = root->get_ref();
406     delete root;
407
408     fclose(statcache_out);
409     if (rename(statcache_tmp_path.c_str(), statcache_path.c_str()) < 0) {
410         fprintf(stderr, "Error renaming statcache from %s to %s: %m\n",
411                 statcache_tmp_path.c_str(), statcache_path.c_str());
412     }
413
414     return ref;
415 }