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