store.cc

   1 /* LBS: An LFS-inspired filesystem backup system
   2  * Copyright (C) 2006  Michael Vrable
   3  *
   4  * Backup data is stored in a collection of objects, which are grouped together
   5  * into segments for storage purposes.  This file provides interfaces for
   6  * reading and writing objects and segments. */
   7
   8 #include <assert.h>
   9 #include <uuid/uuid.h>
  10
  11 #include "store.h"
  12
  13 using std::string;
  14
  15 OutputStream::OutputStream()
  16     : bytes_written(0)
  17 {
  18 }
  19
  20 void OutputStream::write(const void *data, size_t len)
  21 {
  22     write_internal(data, len);
  23     bytes_written += len;
  24 }
  25
  26 void OutputStream::write_u8(uint8_t val)
  27 {
  28     write(&val, 1);
  29 }
  30
  31 void OutputStream::write_u16(uint16_t val)
  32 {
  33     unsigned char buf[2];
  34
  35     buf[0] = val & 0xff;
  36     buf[1] = (val >> 8) & 0xff;
  37     write(buf, 2);
  38 }
  39
  40 void OutputStream::write_u32(uint32_t val)
  41 {
  42     unsigned char buf[4];
  43
  44     buf[0] = val & 0xff;
  45     buf[1] = (val >> 8) & 0xff;
  46     buf[2] = (val >> 16) & 0xff;
  47     buf[3] = (val >> 24) & 0xff;
  48     write(buf, 4);
  49 }
  50
  51 void OutputStream::write_u64(uint64_t val)
  52 {
  53     unsigned char buf[8];
  54
  55     buf[0] = val & 0xff;
  56     buf[1] = (val >> 8) & 0xff;
  57     buf[2] = (val >> 16) & 0xff;
  58     buf[3] = (val >> 24) & 0xff;
  59     buf[4] = (val >> 32) & 0xff;
  60     buf[5] = (val >> 40) & 0xff;
  61     buf[6] = (val >> 48) & 0xff;
  62     buf[7] = (val >> 56) & 0xff;
  63     write(buf, 8);
  64 }
  65
  66 /* Writes an integer to an output stream using a variable-sized representation:
  67  * seven bits are written at a time (little-endian), and the eigth bit of each
  68  * byte is set if more data follows. */
  69 void OutputStream::write_varint(uint64_t val)
  70 {
  71     do {
  72         uint8_t remainder = (val & 0x7f);
  73         val >>= 7;
  74         if (val)
  75             remainder |= 0x80;
  76         write_u8(remainder);
  77     } while (val);
  78 }
  79
  80 void OutputStream::write_uuid(const struct uuid &u)
  81 {
  82     write(u.bytes, 16);
  83 }
  84
  85 /* Write an arbitrary string by first writing out the length, followed by the
  86  * data itself. */
  87 void OutputStream::write_string(const string &s)
  88 {
  89     size_t len = s.length();
  90     write_varint(len);
  91     write(s.data(), len);
  92 }
  93
  94 void OutputStream::write_dictionary(const dictionary &d)
  95 {
  96     size_t size = d.size();
  97     size_t written = 0;
  98
  99     write_varint(size);
 100
 101     for (dictionary::const_iterator i = d.begin(); i != d.end(); ++i) {
 102         write_string(i->first);
 103         write_string(i->second);
 104         written++;
 105     }
 106
 107     assert(written == size);
 108 }
 109
 110 StringOutputStream::StringOutputStream()
 111     : buf(std::ios_base::out)
 112 {
 113 }
 114
 115 void StringOutputStream::write_internal(const void *data, size_t len)
 116 {
 117     buf.write((const char *)data, len);
 118     if (!buf.good())
 119         throw IOException("error writing to StringOutputStream");
 120 }
 121
 122 FileOutputStream::FileOutputStream(FILE *file)
 123 {
 124     f = file;
 125 }
 126
 127 FileOutputStream::~FileOutputStream()
 128 {
 129     fclose(f);
 130 }
 131
 132 void FileOutputStream::write_internal(const void *data, size_t len)
 133 {
 134     size_t res;
 135
 136     res = fwrite(data, 1, len, f);
 137     if (res != len) {
 138         throw IOException("write error");
 139     }
 140 }
 141
 142 WrapperOutputStream::WrapperOutputStream(OutputStream &o)
 143     : real(o)
 144 {
 145 }
 146
 147 void WrapperOutputStream::write_internal(const void *data, size_t len)
 148 {
 149     real.write(data, len);
 150 }
 151
 152 /* Provide checksumming of a data stream. */
 153 ChecksumOutputStream::ChecksumOutputStream(OutputStream &o)
 154     : real(o)
 155 {
 156 }
 157
 158 void ChecksumOutputStream::write_internal(const void *data, size_t len)
 159 {
 160     real.write(data, len);
 161     csum.process(data, len);
 162 }
 163
 164 const uint8_t *ChecksumOutputStream::finish_and_checksum()
 165 {
 166     return csum.checksum();
 167 }
 168
 169 /* Utility functions, for encoding data types to strings. */
 170 string encode_u16(uint16_t val)
 171 {
 172     StringOutputStream s;
 173     s.write_u16(val);
 174     return s.contents();
 175 }
 176
 177 string encode_u32(uint32_t val)
 178 {
 179     StringOutputStream s;
 180     s.write_u32(val);
 181     return s.contents();
 182 }
 183
 184 string encode_u64(uint64_t val)
 185 {
 186     StringOutputStream s;
 187     s.write_u64(val);
 188     return s.contents();
 189 }
 190
 191 string encode_objref(const struct uuid &segment, uint32_t object)
 192 {
 193     StringOutputStream s;
 194     s.write_uuid(segment);
 195     s.write_u32(object);
 196     return s.contents();
 197 }
 198
 199 SegmentWriter::SegmentWriter(OutputStream *output, struct uuid u)
 200     : raw_out(output),
 201       id(u),
 202       object_stream(NULL)
 203 {
 204     /* All output data will be checksummed except the very last few bytes,
 205      * which are the checksum itself. */
 206     out = new ChecksumOutputStream(*raw_out);
 207
 208     /* Write out the segment header first. */
 209     static const char signature[] = "LBSSEG0\n";
 210     out->write(signature, strlen(signature));
 211     out->write_uuid(id);
 212 }
 213
 214 SegmentWriter::~SegmentWriter()
 215 {
 216     if (object_stream)
 217         finish_object();
 218
 219     // Write out the object table which gives the sizes and locations of all
 220     // objects, and then add the trailing signature, which indicates the end of
 221     // the segment and gives the offset of the object table.
 222     int64_t index_offset = out->get_pos();
 223
 224     for (object_table::const_iterator i = objects.begin();
 225          i != objects.end(); ++i) {
 226         out->write_s64(i->offset);
 227         out->write_s64(i->size);
 228         out->write(i->type, sizeof(i->type));
 229     }
 230
 231     static const char signature2[] = "LBSEND";
 232     out->write(signature2, strlen(signature2));
 233     out->write_s64(index_offset);
 234     out->write_u32(objects.size());
 235
 236     /* Finally, append a checksum to the end of the file, so that its integrity
 237      * (against accidental, not malicious, corruption) can be verified. */
 238     const uint8_t *csum = out->finish_and_checksum();
 239     raw_out->write(csum, out->checksum_size());
 240
 241     /* The SegmentWriter takes ownership of the OutputStream it is writing to,
 242      * and destroys it automatically when done with the segment. */
 243     delete out;
 244     delete raw_out;
 245 }
 246
 247 OutputStream *SegmentWriter::new_object(int *id, const char *type)
 248 {
 249     if (object_stream)
 250         finish_object();
 251
 252     if (id != NULL)
 253         *id = objects.size();
 254
 255     struct index_info info;
 256     info.offset = out->get_pos();
 257     info.size = -1;             // Will be filled in when object is finished
 258     strncpy(info.type, type, sizeof(info.type));
 259     objects.push_back(info);
 260
 261     object_stream = new WrapperOutputStream(*out);
 262     return object_stream;
 263 }
 264
 265 void SegmentWriter::finish_object()
 266 {
 267     assert(object_stream != NULL);
 268
 269     // Fill in object size, which could not be stored at start
 270     objects.back().size = object_stream->get_pos();
 271
 272     delete object_stream;
 273     object_stream = NULL;
 274 }
 275
 276 struct uuid SegmentWriter::generate_uuid()
 277 {
 278     struct uuid u;
 279
 280     uuid_generate(u.bytes);
 281
 282     return u;
 283 }
 284
 285 string SegmentWriter::format_uuid(const struct uuid u)
 286 {
 287     // A UUID only takes 36 bytes, plus the trailing '\0', so this is safe.
 288     char buf[40];
 289
 290     uuid_unparse_lower(u.bytes, buf);
 291
 292     return string(buf);
 293 }
 294
 295 SegmentStore::SegmentStore(const string &path)
 296     : directory(path)
 297 {
 298 }
 299
 300 SegmentWriter *SegmentStore::new_segment()
 301 {
 302     struct uuid id = SegmentWriter::generate_uuid();
 303     string filename = directory + "/" + SegmentWriter::format_uuid(id);
 304
 305     FILE *f = fopen(filename.c_str(), "wb");
 306     if (f == NULL)
 307         throw IOException("Unable to open new segment");
 308
 309     return new SegmentWriter(new FileOutputStream(f), id);
 310 }
 311
 312 SegmentPartitioner::SegmentPartitioner(SegmentStore *s)
 313     : store(s),
 314       segment(NULL),
 315       object(NULL)
 316 {
 317     // Default target size is around 1 MB
 318     target_size = 1024 * 1024;
 319 }
 320
 321 SegmentPartitioner::~SegmentPartitioner()
 322 {
 323     if (segment)
 324         delete segment;
 325 }
 326
 327 OutputStream *SegmentPartitioner::new_object(struct uuid *uuid, int *id,
 328                                              const char *type)
 329 {
 330     if (segment != NULL && segment->get_size() > target_size) {
 331         delete segment;
 332         segment = NULL;
 333     }
 334
 335     if (segment == NULL)
 336         segment = store->new_segment();
 337
 338     if (uuid != NULL)
 339         *uuid = segment->get_uuid();
 340
 341     return segment->new_object(id, type);
 342 }