ref.cc

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