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_mtime = -1;
 121     old_ctime = -1;
 122     old_inode = -1;
 123     old_checksum = "";
 124     old_contents.clear();
 125
 126     /* First, read in the filename. */
 127     getline(cache, old_name);
 128     if (!cache) {
 129         end_of_cache = true;
 130         return;
 131     }
 132
 133     /* Start reading in the fields which follow the filename. */
 134     string field = "";
 135     while (!cache.eof()) {
 136         string line;
 137         getline(cache, line);
 138         const char *s = line.c_str();
 139
 140         /* Is the line blank?  If so, we have reached the end of this entry. */
 141         if (s[0] == '\0' || s[0] == '\n')
 142             break;
 143
 144         /* Is this a continuation line?  (Does it start with whitespace?) */
 145         if (isspace(s[0]) && field != "") {
 146             fields[field] += line;
 147             continue;
 148         }
 149
 150         /* For lines of the form "Key: Value" look for ':' and split the line
 151          * apart. */
 152         const char *value = strchr(s, ':');
 153         if (value == NULL)
 154             continue;
 155         field = string(s, value - s);
 156
 157         value++;
 158         while (isspace(*value))
 159             value++;
 160
 161         fields[field] = value;
 162     }
 163
 164     /* Parse the easy fields: mtime, ctime, inode, checksum, ... */
 165     if (fields.count("mtime"))
 166         old_mtime = parse_int(fields["mtime"]);
 167     if (fields.count("ctime"))
 168         old_ctime = parse_int(fields["ctime"]);
 169     if (fields.count("inode"))
 170         old_inode = parse_int(fields["inode"]);
 171
 172     old_checksum = fields["checksum"];
 173
 174     /* Parse the list of blocks. */
 175     const char *s = fields["blocks"].c_str();
 176     while (*s != '\0') {
 177         if (isspace(*s)) {
 178             s++;
 179             continue;
 180         }
 181
 182         string ref = "";
 183         while (*s != '\0' && !isspace(*s)) {
 184             char buf[2];
 185             buf[0] = *s;
 186             buf[1] = '\0';
 187             ref += buf;
 188             s++;
 189         }
 190
 191         ObjectReference *r = ObjectReference::parse(ref);
 192         if (r != NULL) {
 193             old_contents.push_back(*r);
 194             delete r;
 195         }
 196     }
 197
 198     end_of_cache = false;
 199 }
 200
 201 /* Find information about the given filename in the old stat cache, if it
 202  * exists. */
 203 bool StatCache::Find(const string &path, const struct stat *stat_buf)
 204 {
 205     while (!end_of_cache && pathcmp(old_name.c_str(), path.c_str()) < 0)
 206         ReadNext();
 207
 208     /* Could the file be found at all? */
 209     if (end_of_cache)
 210         return false;
 211     if (old_name != path)
 212         return false;
 213
 214     /* Check to see if the file is unchanged. */
 215     if (stat_buf->st_mtime != old_mtime)
 216         return false;
 217     if (stat_buf->st_ctime != old_ctime)
 218         return false;
 219     if ((long long)stat_buf->st_ino != old_inode)
 220         return false;
 221
 222     /* File looks to be unchanged. */
 223     return true;
 224 }
 225
 226 /* Save stat information about a regular file for future invocations. */
 227 void StatCache::Save(const string &path, struct stat *stat_buf,
 228                      const string &checksum, const list<string> &blocks)
 229 {
 230     *newcache << uri_encode(path) << "\n";
 231     *newcache << "mtime: " << encode_int(stat_buf->st_mtime) << "\n"
 232               << "ctime: " << encode_int(stat_buf->st_ctime) << "\n"
 233               << "inode: " << encode_int(stat_buf->st_ino) << "\n"
 234               << "checksum: " << checksum << "\n";
 235
 236     *newcache << "blocks:";
 237     if (blocks.size() == 0)
 238         *newcache << "\n";
 239     for (list<string>::const_iterator i = blocks.begin();
 240          i != blocks.end(); ++i) {
 241         *newcache << " " << *i << "\n";
 242     }
 243
 244     *newcache << "\n";
 245 }