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