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