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 }