statcache.cc

   1 /* LBS: An LFS-inspired filesystem backup system Copyright (C) 2007  Michael
   2  * Vrable
   3  *
   4  * To speed backups, we maintain a "stat cache" containing selected information
   5  * about all regular files, including modification times and the list of blocks
   6  * that comprised the file in the last backup.  If the file has not changed
   7  * according to a stat() call, we may re-use the information contained in the
   8  * stat cache instead of re-reading the entire file.  It is always safe to
   9  * discard information from the stat cache; this will only cause a file to be
  10  * re-read to determine that it contains the same data as before.
  11  *
  12  * The stat cache is stored in a file called "statcache" in the local backup
  13  * directory.  During a backup, a new statcache file is written out with a
  14  * suffix based on the current time; at the end of a successful backup this
  15  * file is renamed over the original statcache file.
  16  *
  17  * The information in the statcache file is stored in sorted order as we
  18  * traverse the filesystem, so that we can read and write it in a purely
  19  * streaming manner.  (This is why we don't include the information in the
  20  * SQLite local database; doing so is likely less efficient.)
  21  */
  22
  23 #include <assert.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <ctype.h>
  27
  28 #include <fstream>
  29 #include <iostream>
  30 #include <map>
  31 #include <string>
  32
  33 #include "format.h"
  34 #include "ref.h"
  35 #include "statcache.h"
  36
  37 using std::list;
  38 using std::map;
  39 using std::string;
  40 using std::getline;
  41 using std::ifstream;
  42 using std::ofstream;
  43
  44 /* Like strcmp, but sorts in the order that files will be visited in the
  45  * filesystem.  That is, we break paths apart at slashes, and compare path
  46  * components separately. */
  47 static int pathcmp(const char *path1, const char *path2)
  48 {
  49     /* Find the first component in each path. */
  50     const char *slash1 = strchr(path1, '/');
  51     const char *slash2 = strchr(path2, '/');
  52
  53     {
  54         string comp1, comp2;
  55         if (slash1 == NULL)
  56             comp1 = path1;
  57         else
  58             comp1 = string(path1, slash1 - path1);
  59
  60         if (slash2 == NULL)
  61             comp2 = path2;
  62         else
  63             comp2 = string(path2, slash2 - path2);
  64
  65         /* Directly compare the two components first. */
  66         if (comp1 < comp2)
  67             return -1;
  68         if (comp1 > comp2)
  69             return 1;
  70     }
  71
  72     if (slash1 == NULL && slash2 == NULL)
  73         return 0;
  74     if (slash1 == NULL)
  75         return -1;
  76     if (slash2 == NULL)
  77         return 1;
  78
  79     return pathcmp(slash1 + 1, slash2 + 1);
  80 }
  81
  82 void StatCache::Open(const char *path, const char *snapshot_name)
  83 {
  84     oldpath = path;
  85     oldpath += "/statcache";
  86     newpath = oldpath + "." + snapshot_name;
  87
  88     oldcache = new ifstream(oldpath.c_str());
  89     newcache = new ofstream(newpath.c_str());
  90
  91     /* Read the first entry from the old stat cache into memory before we
  92      * start. */
  93     ReadNext();
  94 }
  95
  96 void StatCache::Close()
  97 {
  98     if (oldcache != NULL)
  99         delete oldcache;
 100
 101     delete newcache;
 102
 103     if (rename(newpath.c_str(), oldpath.c_str()) < 0) {
 104         fprintf(stderr, "Error renaming statcache from %s to %s: %m\n",
 105                 newpath.c_str(), oldpath.c_str());
 106     }
 107 }
 108
 109 /* Read the next entry from the old statcache file and cache it in memory. */
 110 void StatCache::ReadNext()
 111 {
 112     if (oldcache == NULL) {
 113         end_of_cache = true;
 114         return;
 115     }
 116
 117     std::istream &cache = *oldcache;
 118     map<string, string> fields;
 119
 120     old_is_validated = false;
 121     old_mtime = -1;
 122     old_ctime = -1;
 123     old_inode = -1;
 124     old_size = -1;
 125     old_checksum = "";
 126     old_contents.clear();
 127
 128     /* First, read in the filename. */
 129     getline(cache, old_name);
 130     if (!cache) {
 131         end_of_cache = true;
 132         return;
 133     }
 134     old_name = uri_decode(old_name);
 135
 136     /* Start reading in the fields which follow the filename. */
 137     string field = "";
 138     while (!cache.eof()) {
 139         string line;
 140         getline(cache, line);
 141         const char *s = line.c_str();
 142
 143         /* Is the line blank?  If so, we have reached the end of this entry. */
 144         if (s[0] == '\0' || s[0] == '\n')
 145             break;
 146
 147         /* Is this a continuation line?  (Does it start with whitespace?) */
 148         if (isspace(s[0]) && field != "") {
 149             fields[field] += line;
 150             continue;
 151         }
 152
 153         /* For lines of the form "Key: Value" look for ':' and split the line
 154          * apart. */
 155         const char *value = strchr(s, ':');
 156         if (value == NULL)
 157             continue;
 158         field = string(s, value - s);
 159
 160         value++;
 161         while (isspace(*value))
 162             value++;
 163
 164         fields[field] = value;
 165     }
 166
 167     /* Parse the easy fields: mtime, ctime, inode, checksum, ... */
 168     if (fields.count("validated"))
 169         old_is_validated = true;
 170     if (fields.count("mtime"))
 171         old_mtime = parse_int(fields["mtime"]);
 172     if (fields.count("ctime"))
 173         old_ctime = parse_int(fields["ctime"]);
 174     if (fields.count("inode"))
 175         old_inode = parse_int(fields["inode"]);
 176     if (fields.count("size"))
 177         old_size = parse_int(fields["size"]);
 178
 179     old_checksum = fields["checksum"];
 180
 181     /* Parse the list of blocks. */
 182     const char *s = fields["blocks"].c_str();
 183     while (*s != '\0') {
 184         if (isspace(*s)) {
 185             s++;
 186             continue;
 187         }
 188
 189         string ref = "";
 190         while (*s != '\0' && !isspace(*s)) {
 191             char buf[2];
 192             buf[0] = *s;
 193             buf[1] = '\0';
 194             ref += buf;
 195             s++;
 196         }
 197
 198         ObjectReference *r = ObjectReference::parse(ref);
 199         if (r != NULL) {
 200             old_contents.push_back(*r);
 201             delete r;
 202         }
 203     }
 204
 205     end_of_cache = false;
 206 }
 207
 208 /* Find information about the given filename in the old stat cache, if it
 209  * exists. */
 210 bool StatCache::Find(const string &path, const struct stat *stat_buf)
 211 {
 212     while (!end_of_cache && pathcmp(old_name.c_str(), path.c_str()) < 0)
 213         ReadNext();
 214
 215     /* Could the file be found at all? */
 216     if (end_of_cache)
 217         return false;
 218     if (old_name != path)
 219         return false;
 220
 221     /* Do we trust cached stat information? */
 222     if (!old_is_validated)
 223         return false;
 224
 225     /* Check to see if the file is unchanged. */
 226     if (stat_buf->st_mtime != old_mtime)
 227         return false;
 228     if (stat_buf->st_ctime != old_ctime)
 229         return false;
 230     if ((long long)stat_buf->st_ino != old_inode)
 231         return false;
 232     if (stat_buf->st_size != old_size)
 233         return false;
 234
 235     /* File looks to be unchanged. */
 236     return true;
 237 }
 238
 239 /* Save stat information about a regular file for future invocations. */
 240 void StatCache::Save(const string &path, struct stat *stat_buf,
 241                      const string &checksum, const list<string> &blocks)
 242 {
 243     /* Was this file in the old stat cache, and is the information unchanged?
 244      * If so, mark the information "validated", which means we are confident
 245      * that we can use it to accurately detect changes.  (Stat information may
 246      * not be updated if, for example, there are two writes within a single
 247      * second and we happen to make the first stat call between them.  However,
 248      * if two stat calls separated in time agree, then we will trust the
 249      * values.) */
 250     bool validated = false;
 251     if (!end_of_cache && path == old_name) {
 252         if (stat_buf->st_mtime == old_mtime
 253             && stat_buf->st_ctime == old_ctime
 254             && (long long)stat_buf->st_ino == old_inode
 255             && old_checksum == checksum)
 256             validated = true;
 257     }
 258
 259     *newcache << uri_encode(path) << "\n";
 260     *newcache << "mtime: " << encode_int(stat_buf->st_mtime) << "\n"
 261               << "ctime: " << encode_int(stat_buf->st_ctime) << "\n"
 262               << "inode: " << encode_int(stat_buf->st_ino) << "\n"
 263               << "size: " << encode_int(stat_buf->st_size) << "\n"
 264               << "checksum: " << checksum << "\n";
 265
 266     *newcache << "blocks:";
 267     if (blocks.size() == 0)
 268         *newcache << "\n";
 269     for (list<string>::const_iterator i = blocks.begin();
 270          i != blocks.end(); ++i) {
 271         *newcache << " " << *i << "\n";
 272     }
 273
 274     if (validated)
 275         *newcache << "validated: true\n";
 276
 277     *newcache << "\n";
 278 }