Ensure metadata file is written prior to calculating checksum.
[cumulus.git] / ref.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 /* Backups are structured as a collection of objects, which may refer to other
21  * objects.  Object references are used to name other objects or parts of them.
22  * This file defines the class for representing object references and the
23  * textual representation of these references. */
24
25 #include <assert.h>
26 #include <stdio.h>
27 #include <stdint.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <uuid/uuid.h>
31
32 #include <string>
33
34 #include "ref.h"
35
36 using std::string;
37
38 /* Generate a new UUID, and return the text representation of it.  This is
39  * suitable for generating the name for a new segment. */
40 string generate_uuid()
41 {
42     uint8_t uuid[16];
43     char buf[40];
44
45     uuid_generate(uuid);
46     uuid_unparse_lower(uuid, buf);
47     return string(buf);
48 }
49
50 ObjectReference::ObjectReference()
51     : type(REF_NULL), segment(""), object("")
52 {
53     clear_checksum();
54     clear_range();
55 }
56
57 ObjectReference::ObjectReference(RefType t)
58     : type(t), segment(""), object("")
59 {
60     clear_checksum();
61     clear_range();
62 }
63
64 ObjectReference::ObjectReference(const std::string& segment, int sequence)
65     : type(REF_NORMAL), segment(segment)
66 {
67     char seq_buf[64];
68     sprintf(seq_buf, "%08x", sequence);
69     object = seq_buf;
70
71     clear_checksum();
72     clear_range();
73 }
74
75 ObjectReference::ObjectReference(const std::string& segment,
76                                  const std::string& sequence)
77     : type(REF_NORMAL), segment(segment), object(sequence)
78 {
79     clear_checksum();
80     clear_range();
81 }
82
83 string ObjectReference::to_string() const
84 {
85     if (type == REF_NULL)
86         return "null";
87
88     string result;
89     if (type == REF_ZERO) {
90         result = "zero";
91     } else if (type == REF_NORMAL) {
92         result = segment + "/" + object;
93
94         if (checksum_valid)
95             result += "(" + checksum + ")";
96     }
97
98     if (range_valid) {
99         char buf[64];
100         if (range_exact) {
101             sprintf(buf, "[=%zu]", range_length);
102         } else if (type == REF_ZERO) {
103             sprintf(buf, "[%zu]", range_length);
104         } else {
105             sprintf(buf, "[%zu+%zu]", range_start, range_length);
106         }
107         result += buf;
108     }
109
110     return result;
111 }
112
113 /* Parse a string object reference and return a pointer to a new
114  * ObjectReference.  The caller is responsible for freeing the object.  NULL is
115  * returned if there is an error in the syntax. */
116 ObjectReference ObjectReference::parse(const std::string& str)
117 {
118     const char *s = str.c_str();
119     const char *t;
120     ObjectReference::RefType type = ObjectReference::REF_NORMAL;
121
122     // Special case: explicit zero objects
123     if (strncmp(s, "zero", 4) == 0) {
124         type = ObjectReference::REF_ZERO;
125         s += 4;
126     }
127
128     // Segment
129     t = s;
130     if (type == ObjectReference::REF_NORMAL) {
131         while ((*t >= '0' && *t <= '9') || (*t >= 'a' && *t <= 'f')
132                || (*t == '-'))
133             t++;
134         if (*t != '/')
135             return ObjectReference();
136     }
137     string segment(s, t - s);
138
139     // Object sequence number
140     if (type == ObjectReference::REF_NORMAL) {
141         t++;
142         s = t;
143         while ((*t >= '0' && *t <= '9') || (*t >= 'a' && *t <= 'f'))
144             t++;
145         if (*t != '\0' && *t != '(' && *t != '[')
146             return ObjectReference();
147     }
148     string object(s, t - s);
149
150     // Checksum
151     string checksum;
152     if (*t == '(') {
153         t++;
154         s = t;
155         while (*t != ')' && *t != '\0')
156             t++;
157         if (*t != ')')
158             return ObjectReference();
159         checksum = string(s, t - s);
160         t++;
161     }
162
163     // Range
164     bool have_range = false, range_exact = false;
165     int64_t range1 = 0, range2 = 0;
166     if (*t == '[') {
167         t++;
168
169         if (*t == '=') {
170             range_exact = true;
171             t++;
172         }
173
174         s = t;
175         while (*t >= '0' && *t <= '9')
176             t++;
177
178         // Abbreviated-length only range?
179         if (*t == ']') {
180             string val(s, t - s);
181             range2 = atoll(val.c_str());
182         } else {
183             if (*t != '+')
184                 return ObjectReference();
185             if (range_exact)
186                 return ObjectReference();
187
188             string val(s, t - s);
189             range1 = atoll(val.c_str());
190
191             t++;
192             s = t;
193             while (*t >= '0' && *t <= '9')
194                 t++;
195             if (*t != ']')
196                 return ObjectReference();
197
198             val = string(s, t - s);
199             range2 = atoll(val.c_str());
200         }
201
202         have_range = true;
203     }
204
205     ObjectReference ref;
206     switch (type) {
207     case ObjectReference::REF_ZERO:
208         ref = ObjectReference(ObjectReference::REF_ZERO);
209         break;
210     case ObjectReference::REF_NORMAL:
211         ref = ObjectReference(segment, object);
212         break;
213     default:
214         return ObjectReference();
215     }
216
217     if (checksum.size() > 0)
218         ref.set_checksum(checksum);
219
220     if (have_range)
221         ref.set_range(range1, range2, range_exact);
222
223     return ref;
224 }
225
226 /* Attempt to merge a new object reference into the current one.  Returns a
227  * boolean indicating success; if successful this reference is modified so that
228  * it refers to the range of bytes originally covered by this reference plus
229  * the reference passed in.  Merging only succeeds if both references refer to
230  * the same object and the byte ranges are contiguous. */
231 bool ObjectReference::merge(ObjectReference ref)
232 {
233     // Exception: We can always merge into a null object
234     if (is_null()) {
235         *this = ref;
236         return true;
237     }
238
239     if (segment != ref.segment)
240         return false;
241     if (object != ref.object)
242         return false;
243
244     // TODO: Allow the case where only one checksum was filled in
245     if (checksum_valid != ref.checksum_valid || checksum != ref.checksum)
246         return false;
247
248     if (!range_valid || !ref.range_valid)
249         return false;
250
251     if (range_exact || ref.range_exact)
252         return false;
253
254     if (range_start + range_length == ref.range_start) {
255         range_length += ref.range_length;
256         return true;
257     } else {
258         return false;
259     }
260 }