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 <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_start == 0) {
 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;
 163     int64_t range1 = 0, range2 = 0;
 164     if (*t == '[') {
 165         t++;
 166         s = t;
 167         while (*t >= '0' && *t <= '9')
 168             t++;
 169
 170         // Abbreviated-length only range?
 171         if (*t == ']') {
 172             string val(s, t - s);
 173             range2 = atoll(val.c_str());
 174         } else {
 175             if (*t != '+')
 176                 return ObjectReference();
 177
 178             string val(s, t - s);
 179             range1 = atoll(val.c_str());
 180
 181             t++;
 182             s = t;
 183             while (*t >= '0' && *t <= '9')
 184                 t++;
 185             if (*t != ']')
 186                 return ObjectReference();
 187
 188             val = string(s, t - s);
 189             range2 = atoll(val.c_str());
 190         }
 191
 192         have_range = true;
 193     }
 194
 195     ObjectReference ref;
 196     switch (type) {
 197     case ObjectReference::REF_ZERO:
 198         ref = ObjectReference(ObjectReference::REF_ZERO);
 199         break;
 200     case ObjectReference::REF_NORMAL:
 201         ref = ObjectReference(segment, object);
 202         break;
 203     default:
 204         return ObjectReference();
 205     }
 206
 207     if (checksum.size() > 0)
 208         ref.set_checksum(checksum);
 209
 210     if (have_range)
 211         ref.set_range(range1, range2);
 212
 213     return ref;
 214 }
 215
 216 /* Attempt to merge a new object reference into the current one.  Returns a
 217  * boolean indicating success; if successful this reference is modified so that
 218  * it refers to the range of bytes originally covered by this reference plus
 219  * the reference passed in.  Merging only succeeds if both references refer to
 220  * the same object and the byte ranges are contiguous. */
 221 bool ObjectReference::merge(ObjectReference ref)
 222 {
 223     // Exception: We can always merge into a null object
 224     if (is_null()) {
 225         *this = ref;
 226         return true;
 227     }
 228
 229     if (segment != ref.segment)
 230         return false;
 231     if (object != ref.object)
 232         return false;
 233
 234     // TODO: Allow the case where only one checksum was filled in
 235     if (checksum_valid != ref.checksum_valid || checksum != ref.checksum)
 236         return false;
 237
 238     if (!range_valid || !ref.range_valid)
 239         return false;
 240
 241     if (range_start + range_length == ref.range_start) {
 242         range_length += ref.range_length;
 243         return true;
 244     } else {
 245         return false;
 246     }
 247 }