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->first);
 227         out->write_s64(i->second);
 228     }
 229
 230     static const char signature2[] = "LBSEND";
 231     out->write(signature2, strlen(signature2));
 232     out->write_s64(index_offset);
 233     out->write_u32(objects.size());
 234
 235     /* Finally, append a checksum to the end of the file, so that its integrity
 236      * (against accidental, not malicious, corruption) can be verified. */
 237     const uint8_t *csum = out->finish_and_checksum();
 238     raw_out->write(csum, out->checksum_size());
 239
 240     /* The SegmentWriter takes ownership of the OutputStream it is writing to,
 241      * and destroys it automatically when done with the segment. */
 242     delete out;
 243     delete raw_out;
 244 }
 245
 246 OutputStream *SegmentWriter::new_object(int *id)
 247 {
 248     if (object_stream)
 249         finish_object();
 250
 251     object_start_offset = out->get_pos();
 252     object_stream = new WrapperOutputStream(*out);
 253
 254     if (id != NULL) {
 255         *id = objects.size();
 256     }
 257
 258     return object_stream;
 259 }
 260
 261 void SegmentWriter::finish_object()
 262 {
 263     assert(object_stream != NULL);
 264
 265     // store (start, length) information for locating this object
 266     objects.push_back(std::make_pair(object_start_offset,
 267                                      object_stream->get_pos()));
 268
 269     delete object_stream;
 270     object_stream = NULL;
 271 }
 272
 273 struct uuid SegmentWriter::generate_uuid()
 274 {
 275     struct uuid u;
 276
 277     uuid_generate(u.bytes);
 278
 279     return u;
 280 }
 281
 282 string SegmentWriter::format_uuid(const struct uuid u)
 283 {
 284     // A UUID only takes 36 bytes, plus the trailing '\0', so this is safe.
 285     char buf[40];
 286
 287     uuid_unparse_lower(u.bytes, buf);
 288
 289     return string(buf);
 290 }
 291
 292 SegmentStore::SegmentStore(const string &path)
 293     : directory(path)
 294 {
 295 }
 296
 297 SegmentWriter *SegmentStore::new_segment()
 298 {
 299     struct uuid id = SegmentWriter::generate_uuid();
 300     string filename = directory + "/" + SegmentWriter::format_uuid(id);
 301
 302     FILE *f = fopen(filename.c_str(), "wb");
 303     if (f == NULL)
 304         throw IOException("Unable to open new segment");
 305
 306     return new SegmentWriter(new FileOutputStream(f), id);
 307 }
 308
 309 SegmentPartitioner::SegmentPartitioner(SegmentStore *s)
 310     : store(s),
 311       segment(NULL),
 312       object(NULL)
 313 {
 314     // Default target size is around 1 MB
 315     target_size = 1024 * 1024;
 316 }
 317
 318 SegmentPartitioner::~SegmentPartitioner()
 319 {
 320     if (segment)
 321         delete segment;
 322 }
 323
 324 OutputStream *SegmentPartitioner::new_object(struct uuid *uuid, int *id)
 325 {
 326     if (segment != NULL && segment->get_size() > target_size) {
 327         delete segment;
 328         segment = NULL;
 329     }
 330
 331     if (segment == NULL)
 332         segment = store->new_segment();
 333
 334     if (uuid != NULL)
 335         *uuid = segment->get_uuid();
 336
 337     return segment->new_object(id);
 338 }