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