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_checksum = "";
 125     old_contents.clear();
 126
 127     /* First, read in the filename.  TODO: Unescaping. */
 128     getline(cache, old_name);
 129     if (!cache) {
 130         end_of_cache = true;
 131         return;
 132     }
 133
 134     /* Start reading in the fields which follow the filename. */
 135     string field = "";
 136     while (!cache.eof()) {
 137         string line;
 138         getline(cache, line);
 139         const char *s = line.c_str();
 140
 141         /* Is the line blank?  If so, we have reached the end of this entry. */
 142         if (s[0] == '\0' || s[0] == '\n')
 143             break;
 144
 145         /* Is this a continuation line?  (Does it start with whitespace?) */
 146         if (isspace(s[0]) && field != "") {
 147             fields[field] += line;
 148             continue;
 149         }
 150
 151         /* For lines of the form "Key: Value" look for ':' and split the line
 152          * apart. */
 153         const char *value = strchr(s, ':');
 154         if (value == NULL)
 155             continue;
 156         field = string(s, value - s);
 157
 158         value++;
 159         while (isspace(*value))
 160             value++;
 161
 162         fields[field] = value;
 163     }
 164
 165     /* Parse the easy fields: mtime, ctime, inode, checksum, ... */
 166     if (fields.count("validated"))
 167         old_is_validated = true;
 168     if (fields.count("mtime"))
 169         old_mtime = parse_int(fields["mtime"]);
 170     if (fields.count("ctime"))
 171         old_ctime = parse_int(fields["ctime"]);
 172     if (fields.count("inode"))
 173         old_inode = parse_int(fields["inode"]);
 174
 175     old_checksum = fields["checksum"];
 176
 177     /* Parse the list of blocks. */
 178     const char *s = fields["blocks"].c_str();
 179     while (*s != '\0') {
 180         if (isspace(*s)) {
 181             s++;
 182             continue;
 183         }
 184
 185         string ref = "";
 186         while (*s != '\0' && !isspace(*s)) {
 187             char buf[2];
 188             buf[0] = *s;
 189             buf[1] = '\0';
 190             ref += buf;
 191             s++;
 192         }
 193
 194         ObjectReference *r = ObjectReference::parse(ref);
 195         if (r != NULL) {
 196             old_contents.push_back(*r);
 197             delete r;
 198         }
 199     }
 200
 201     end_of_cache = false;
 202 }
 203
 204 /* Find information about the given filename in the old stat cache, if it
 205  * exists. */
 206 bool StatCache::Find(const string &path, const struct stat *stat_buf)
 207 {
 208     while (!end_of_cache && pathcmp(old_name.c_str(), path.c_str()) < 0)
 209         ReadNext();
 210
 211     /* Could the file be found at all? */
 212     if (end_of_cache)
 213         return false;
 214     if (old_name != path)
 215         return false;
 216
 217     /* Do we trust cached stat information? */
 218     if (!old_is_validated)
 219         return false;
 220
 221     /* Check to see if the file is unchanged. */
 222     if (stat_buf->st_mtime != old_mtime)
 223         return false;
 224     if (stat_buf->st_ctime != old_ctime)
 225         return false;
 226     if ((long long)stat_buf->st_ino != old_inode)
 227         return false;
 228
 229     /* File looks to be unchanged. */
 230     return true;
 231 }
 232
 233 /* Save stat information about a regular file for future invocations. */
 234 void StatCache::Save(const string &path, struct stat *stat_buf,
 235                      const string &checksum, const list<string> &blocks)
 236 {
 237     /* Was this file in the old stat cache, and is the information unchanged?
 238      * If so, mark the information "validated", which means we are confident
 239      * that we can use it to accurately detect changes.  (Stat information may
 240      * not be updated if, for example, there are two writes within a single
 241      * second and we happen to make the first stat call between them.  However,
 242      * if two stat calls separated in time agree, then we will trust the
 243      * values.) */
 244     bool validated = false;
 245     if (!end_of_cache && path == old_name) {
 246         if (stat_buf->st_mtime == old_mtime
 247             && stat_buf->st_ctime == old_ctime
 248             && (long long)stat_buf->st_ino == old_inode
 249             && old_checksum == checksum)
 250             validated = true;
 251     }
 252
 253     *newcache << uri_encode(path) << "\n";
 254     *newcache << "mtime: " << encode_int(stat_buf->st_mtime) << "\n"
 255               << "ctime: " << encode_int(stat_buf->st_ctime) << "\n"
 256               << "inode: " << encode_int(stat_buf->st_ino) << "\n"
 257               << "checksum: " << checksum << "\n";
 258
 259     *newcache << "blocks:";
 260     if (blocks.size() == 0)
 261         *newcache << "\n";
 262     for (list<string>::const_iterator i = blocks.begin();
 263          i != blocks.end(); ++i) {
 264         *newcache << " " << *i << "\n";
 265     }
 266
 267     if (validated)
 268         *newcache << "validated: true\n";
 269
 270     *newcache << "\n";
 271 }