store.h

   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 #ifndef _LBS_STORE_H
   9 #define _LBS_STORE_H
  10
  11 #include <stdint.h>
  12
  13 #include <exception>
  14 #include <map>
  15 #include <string>
  16 #include <sstream>
  17 #include <vector>
  18
  19 #include "sha1.h"
  20
  21 /* In memory datatype to represent key/value pairs of information, such as file
  22  * metadata.  Currently implemented as map<string, string>. */
  23 typedef std::map<std::string, std::string> dictionary;
  24
  25 /* In-memory representation of a UUID (Universally-Unique Identifier), which is
  26  * used to name a segment. */
  27 struct uuid {
  28     uint8_t bytes[16];
  29 };
  30
  31 /* IOException will be thrown if an error occurs while reading or writing in
  32  * one of the I/O wrappers.  Depending upon the context; this may be fatal or
  33  * not--typically, errors reading/writing the store will be serious, but errors
  34  * reading an individual file are less so. */
  35 class IOException : public std::exception {
  36 private:
  37     std::string error;
  38 public:
  39     explicit IOException(const std::string &err) { error = err; }
  40     virtual ~IOException() throw () { }
  41     std::string getError() const { return error; }
  42 };
  43
  44 /* OutputStream is an abstract interface for writing data without seeking.
  45  * Output could be to a file, to an object within a segment, or even to a
  46  * memory buffer to help serialize data. */
  47 class OutputStream {
  48 public:
  49     OutputStream();
  50     virtual ~OutputStream() { }
  51
  52     // Write the given data buffer
  53     void write(const void *data, size_t len);
  54
  55     // Return the total number of bytes written so far
  56     int64_t get_pos() const { return bytes_written; }
  57
  58     // Convenience functions for writing other data types.  Values are always
  59     // written out in little-endian order.
  60     void write_u8(uint8_t val);
  61     void write_u16(uint16_t val);
  62     void write_u32(uint32_t val);
  63     void write_u64(uint64_t val);
  64
  65     void write_s32(int32_t val) { write_u32((uint32_t)val); }
  66     void write_s64(int64_t val) { write_u64((uint64_t)val); }
  67
  68     void write_varint(uint64_t val);
  69
  70     void write_uuid(const struct uuid &u);
  71     void write_string(const std::string &s);
  72     void write_dictionary(const dictionary &d);
  73
  74 protected:
  75     // Function which actually causes a write: must be overridden by
  76     // implementation.
  77     virtual void write_internal(const void *data, size_t len) = 0;
  78
  79 private:
  80     int64_t bytes_written;
  81 };
  82
  83 /* An OutputStream implementation which writes data to memory and returns the
  84  * result as a string. */
  85 class StringOutputStream : public OutputStream {
  86 public:
  87     StringOutputStream();
  88     std::string contents() const { return buf.str(); }
  89
  90 protected:
  91     virtual void write_internal(const void *data, size_t len);
  92
  93 private:
  94     std::stringstream buf;
  95 };
  96
  97 /* An OutputStream implementation which writes data via the C stdio layer. */
  98 class FileOutputStream : public OutputStream {
  99 public:
 100     explicit FileOutputStream(FILE *file);
 101     virtual ~FileOutputStream();
 102
 103 protected:
 104     virtual void write_internal(const void *data, size_t len);
 105
 106 private:
 107     FILE *f;
 108 };
 109
 110 /* An OutputStream which is simply sends writes to another OutputStream, but
 111  * does provide separate tracking of bytes written. */
 112 class WrapperOutputStream : public OutputStream {
 113 public:
 114     explicit WrapperOutputStream(OutputStream &o);
 115     virtual ~WrapperOutputStream() { }
 116
 117 protected:
 118     virtual void write_internal(const void *data, size_t len);
 119
 120 private:
 121     OutputStream &real;
 122 };
 123
 124 /* Like WrapperOutputStream, but additionally computes a checksum of data as it
 125  * is written. */
 126 class ChecksumOutputStream : public OutputStream {
 127 public:
 128     explicit ChecksumOutputStream(OutputStream &o);
 129     virtual ~ChecksumOutputStream() { }
 130
 131     /* Once a checksum is computed, no further data should be written to the
 132      * stream. */
 133     const uint8_t *finish_and_checksum();
 134     size_t checksum_size() const { return csum.checksum_size(); }
 135
 136 protected:
 137     virtual void write_internal(const void *data, size_t len);
 138
 139 private:
 140     OutputStream &real;
 141     SHA1Checksum csum;
 142 };
 143
 144 /* Simple wrappers that encode integers using a StringOutputStream and return
 145  * the encoded result. */
 146 std::string encode_u16(uint16_t val);
 147 std::string encode_u32(uint32_t val);
 148 std::string encode_u64(uint64_t val);
 149 std::string encode_objref(const struct uuid &segment, uint32_t object);
 150
 151 /* A class which is used to pack multiple objects into a single segment, with a
 152  * lookup table to quickly locate each object.  Call new_object() to get an
 153  * OutputStream to which a new object may be written, and optionally
 154  * finish_object() when finished writing the current object.  Only one object
 155  * may be written to a segment at a time; if multiple objects must be written
 156  * concurrently, they must be to different segments. */
 157 class SegmentWriter {
 158 public:
 159     SegmentWriter(OutputStream *output, struct uuid u);
 160     ~SegmentWriter();
 161
 162     struct uuid get_uuid() const { return id; }
 163
 164     // Start writing out a new object to this segment.
 165     OutputStream *new_object(int *id, const char *type);
 166     void finish_object();
 167
 168     // Determine size of segment data written out so far.
 169     size_t get_size() const { return raw_out->get_pos(); }
 170
 171     // Utility functions for generating and formatting UUIDs for display.
 172     static struct uuid generate_uuid();
 173     static std::string format_uuid(const struct uuid u);
 174
 175 private:
 176     struct index_info {
 177         int64_t offset;         // File offset at which object starts
 178         int64_t size;           // Size of object in bytes
 179         char type[4];           // Object type code
 180     };
 181
 182     typedef std::vector<struct index_info> object_table;
 183
 184     ChecksumOutputStream *out;  // Output stream with checksumming enabled
 185     OutputStream *raw_out;      // Raw output stream, without checksumming
 186     struct uuid id;
 187
 188     OutputStream *object_stream;
 189
 190     object_table objects;
 191 };
 192
 193 /* A SegmentStore, as the name suggests, is used to store the contents of many
 194  * segments.  The SegmentStore internally tracks where data should be placed
 195  * (such as a local directory or remote storage), and allows new segments to be
 196  * easily created as needed. */
 197 class SegmentStore {
 198 public:
 199     // New segments will be stored in the given directory.
 200     SegmentStore(const std::string &path);
 201
 202     SegmentWriter *new_segment();
 203
 204 private:
 205     std::string directory;
 206 };
 207
 208 /* A SegmentPartitioner helps to divide objects up among a collection of
 209  * segments to meet a rough size limit per segment.  Like a SegmentWriter, only
 210  * one object should be written at a time; however, multiple
 211  * SegmentPartitioners can be created using the same base SegmentStore. */
 212 class SegmentPartitioner {
 213 public:
 214     explicit SegmentPartitioner(SegmentStore *s);
 215     ~SegmentPartitioner();
 216
 217     OutputStream *new_object(struct uuid *uuid, int *id, const char *type);
 218
 219 private:
 220     size_t target_size;
 221
 222     SegmentStore *store;
 223     SegmentWriter *segment;
 224     OutputStream *object;
 225 };
 226
 227 #endif // _LBS_STORE_H