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 || type == REF_ZERO) {
 101             sprintf(buf, "[%zu]", range_length);
 102         } else {
 103             sprintf(buf, "[%zu+%zu]", range_start, range_length);
 104         }
 105         result += buf;
 106     }
 107
 108     return result;
 109 }
 110
 111 /* Parse a string object reference and return a pointer to a new
 112  * ObjectReference.  The caller is responsible for freeing the object.  NULL is
 113  * returned if there is an error in the syntax. */
 114 ObjectReference ObjectReference::parse(const std::string& str)
 115 {
 116     const char *s = str.c_str();
 117     const char *t;
 118     ObjectReference::RefType type = ObjectReference::REF_NORMAL;
 119
 120     // Special case: explicit zero objects
 121     if (strncmp(s, "zero", 4) == 0) {
 122         type = ObjectReference::REF_ZERO;
 123         s += 4;
 124     }
 125
 126     // Segment
 127     t = s;
 128     if (type == ObjectReference::REF_NORMAL) {
 129         while ((*t >= '0' && *t <= '9') || (*t >= 'a' && *t <= 'f')
 130                || (*t == '-'))
 131             t++;
 132         if (*t != '/')
 133             return ObjectReference();
 134     }
 135     string segment(s, t - s);
 136
 137     // Object sequence number
 138     if (type == ObjectReference::REF_NORMAL) {
 139         t++;
 140         s = t;
 141         while ((*t >= '0' && *t <= '9') || (*t >= 'a' && *t <= 'f'))
 142             t++;
 143         if (*t != '\0' && *t != '(' && *t != '[')
 144             return ObjectReference();
 145     }
 146     string object(s, t - s);
 147
 148     // Checksum
 149     string checksum;
 150     if (*t == '(') {
 151         t++;
 152         s = t;
 153         while (*t != ')' && *t != '\0')
 154             t++;
 155         if (*t != ')')
 156             return ObjectReference();
 157         checksum = string(s, t - s);
 158         t++;
 159     }
 160
 161     // Range
 162     bool have_range = false, range_exact = false;
 163     int64_t range1 = 0, range2 = 0;
 164     if (*t == '[') {
 165         t++;
 166
 167         // An equal sign was once used for a length assertion but is now
 168         // deprecated.  Skip it if present, and mark that we are expecting a
 169         // length-only reference.
 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             range_exact = true;
 184         } else {
 185             if (*t != '+')
 186                 return ObjectReference();
 187             if (range_exact)
 188                 return ObjectReference();
 189
 190             string val(s, t - s);
 191             range1 = atoll(val.c_str());
 192
 193             t++;
 194             s = t;
 195             while (*t >= '0' && *t <= '9')
 196                 t++;
 197             if (*t != ']')
 198                 return ObjectReference();
 199
 200             val = string(s, t - s);
 201             range2 = atoll(val.c_str());
 202         }
 203
 204         have_range = true;
 205     }
 206
 207     ObjectReference ref;
 208     switch (type) {
 209     case ObjectReference::REF_ZERO:
 210         ref = ObjectReference(ObjectReference::REF_ZERO);
 211         break;
 212     case ObjectReference::REF_NORMAL:
 213         ref = ObjectReference(segment, object);
 214         break;
 215     default:
 216         return ObjectReference();
 217     }
 218
 219     if (checksum.size() > 0)
 220         ref.set_checksum(checksum);
 221
 222     if (have_range)
 223         ref.set_range(range1, range2, range_exact);
 224
 225     return ref;
 226 }
 227
 228 /* Attempt to merge a new object reference into the current one.  Returns a
 229  * boolean indicating success; if successful this reference is modified so that
 230  * it refers to the range of bytes originally covered by this reference plus
 231  * the reference passed in.  Merging only succeeds if both references refer to
 232  * the same object and the byte ranges are contiguous. */
 233 bool ObjectReference::merge(ObjectReference ref)
 234 {
 235     // Exception: We can always merge into a null object
 236     if (is_null()) {
 237         *this = ref;
 238         return true;
 239     }
 240
 241     if (segment != ref.segment)
 242         return false;
 243     if (object != ref.object)
 244         return false;
 245
 246     // TODO: Allow the case where only one checksum was filled in
 247     if (checksum_valid != ref.checksum_valid || checksum != ref.checksum)
 248         return false;
 249
 250     if (!range_valid || !ref.range_valid)
 251         return false;
 252
 253     if (range_exact || ref.range_exact)
 254         return false;
 255
 256     if (range_start + range_length == ref.range_start) {
 257         range_length += ref.range_length;
 258         return true;
 259     } else {
 260         return false;
 261     }
 262 }