chunk.cc

   1 /* Cumulus: Smart Filesystem Backup to Dumb Servers
   2  *
   3  * Copyright (C) 2006-2008  The Regents of the University of California
   4  * Written by Michael Vrable <mvrable@cs.ucsd.edu>
   5  *
   6  * Much of the code in this file is taken from LBFS, which is
   7  * Copyright (C) 1998, 1999 David Mazieres (dm@uun.org)
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write to the Free Software Foundation, Inc.,
  21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  22  */
  23
  24 /* Compute incremental backups at a sub-file level by chopping files up into
  25  * blocks in a content-sensitive manner (using Rabin fingerprints).  This code
  26  * is largely taken from LBFS, primarily the files:
  27  *   liblbfs/fingerprint.C  (fingerprint.C,v 1.1 2001/01/29 22:49:13 benjie Exp)
  28  *   liblbfs/rabinpoly.h  (rabinpoly.h,v 1.4 2002/01/07 21:30:21 athicha Exp)
  29  *   liblbfs/rabinpoly.C  (rabinpoly.C,v 1.1 2001/01/29 22:49:13 benjie Exp)
  30  *   async/msb.h  (msb.h,v 1.6 1998/12/26 18:21:51 dm Exp)
  31  *   async/msb.C  (msb.C,v 1.4 1998/12/26 18:21:51 dm Exp)
  32  * but adapted and slimmed down to fit within Cumulus. */
  33
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <stdint.h>
  37 #include <assert.h>
  38 #include <fcntl.h>
  39 #include <string.h>
  40 #include <unistd.h>
  41 #include <sys/types.h>
  42 #include <sys/stat.h>
  43
  44 #include <string>
  45
  46 #include "chunk.h"
  47
  48 using std::string;
  49
  50 // Functions/data only needed internally go in a separate namespace.  Public
  51 // interfaces (at the end of the file) are in the global namespace.
  52 namespace {
  53
  54 #define FINGERPRINT_PT  0xbfe6b8a5bf378d83LL
  55 #define BREAKMARK_VALUE 0x78
  56 #define MIN_CHUNK_SIZE  2048
  57 #define MAX_CHUNK_SIZE  65535
  58 #define TARGET_CHUNK_SIZE  4096
  59
  60 #define SFS_DEV_RANDOM "/dev/random"
  61
  62 #define INT64(n) n##LL
  63 #define MSB64 INT64(0x8000000000000000)
  64
  65 template<class R> inline R
  66 implicit_cast (R r)
  67 {
  68   return r;
  69 }
  70
  71 /* Highest bit set in a byte */
  72 static const char bytemsb[0x100] = {
  73   0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
  74   5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  75   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7,
  76   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  77   7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  78   7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  79   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  80   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  81   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  82   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  83   8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  84 };
  85
  86 /* Find last set (most significant bit) */
  87 static inline u_int fls32 (uint32_t) __attribute__ ((const));
  88 static inline u_int
  89 fls32 (u_int32_t v)
  90 {
  91   if (v & 0xffff0000) {
  92     if (v & 0xff000000)
  93       return 24 + bytemsb[v>>24];
  94     else
  95       return 16 + bytemsb[v>>16];
  96   }
  97   if (v & 0x0000ff00)
  98     return 8 + bytemsb[v>>8];
  99   else
 100     return bytemsb[v];
 101 }
 102
 103 static inline u_int fls64 (u_int64_t) __attribute__ ((const));
 104 static inline u_int
 105 fls64 (u_int64_t v)
 106 {
 107   u_int32_t h;
 108   if ((h = v >> 32))
 109     return 32 + fls32 (h);
 110   else
 111     return fls32 ((u_int32_t) v);
 112 }
 113
 114 static uint64_t
 115 polymod (uint64_t nh, uint64_t nl, uint64_t d)
 116 {
 117   assert (d);
 118   int k = fls64 (d) - 1;
 119   d <<= 63 - k;
 120
 121   if (nh) {
 122     if (nh & MSB64)
 123       nh ^= d;
 124     for (int i = 62; i >= 0; i--)
 125       if (nh & INT64 (1) << i) {
 126         nh ^= d >> (63 - i);
 127         nl ^= d << (i + 1);
 128       }
 129   }
 130   for (int i = 63; i >= k; i--)
 131     if (nl & INT64 (1) << i)
 132       nl ^= d >> (63 - i);
 133   return nl;
 134 }
 135
 136 static void
 137 polymult (uint64_t *php, uint64_t *plp, uint64_t x, uint64_t y)
 138 {
 139   uint64_t ph = 0, pl = 0;
 140   if (x & 1)
 141     pl = y;
 142   for (int i = 1; i < 64; i++)
 143     if (x & (INT64 (1) << i)) {
 144       ph ^= y >> (64 - i);
 145       pl ^= y << i;
 146     }
 147   if (php)
 148     *php = ph;
 149   if (plp)
 150     *plp = pl;
 151 }
 152
 153 static uint64_t
 154 polymmult (uint64_t x, uint64_t y, uint64_t d)
 155 {
 156   uint64_t h, l;
 157   polymult (&h, &l, x, y);
 158   return polymod (h, l, d);
 159 }
 160
 161 #if 0
 162 static uint64_t
 163 polygcd (uint64_t x, uint64_t y)
 164 {
 165   for (;;) {
 166     if (!y)
 167       return x;
 168     x = polymod (0, x, y);
 169     if (!x)
 170       return y;
 171     y = polymod (0, y, x);
 172   }
 173 }
 174
 175 static bool
 176 polyirreducible (uint64_t f)
 177 {
 178   uint64_t u = 2;
 179   int m = (fls64 (f) - 1) >> 1;
 180   for (int i = 0; i < m; i++) {
 181     u = polymmult (u, u, f);
 182     if (polygcd (f, u ^ 2) != 1)
 183       return false;
 184   }
 185   return true;
 186 }
 187
 188 static uint64_t
 189 polygen (u_int degree)
 190 {
 191   assert (degree > 0 && degree < 64);
 192   uint64_t msb = INT64 (1) << degree;
 193   uint64_t mask = msb - 1;
 194   uint64_t f;
 195   int rfd = open (SFS_DEV_RANDOM, O_RDONLY);
 196   if (rfd < 0) {
 197     fprintf (stderr, "%s: %m\n", SFS_DEV_RANDOM);
 198     exit(1);
 199   }
 200   do {
 201     if (read (rfd, &f, sizeof (f)) != implicit_cast<ssize_t> (sizeof (f))) {
 202       fprintf (stderr, "%s: read failed\n", SFS_DEV_RANDOM);
 203       exit(1);
 204     }
 205     f = (f & mask) | msb;
 206   } while (!polyirreducible (f));
 207   close (rfd);
 208   return f;
 209 }
 210 #endif
 211
 212 class rabinpoly {
 213   int shift;
 214   uint64_t T[256];              // Lookup table for mod
 215   void calcT ();
 216 public:
 217   const uint64_t poly;          // Actual polynomial
 218
 219   explicit rabinpoly (uint64_t poly);
 220   uint64_t append8 (uint64_t p, uint8_t m) const
 221     { return ((p << 8) | m) ^ T[p >> shift]; }
 222 };
 223
 224 void
 225 rabinpoly::calcT ()
 226 {
 227   assert (poly >= 0x100);
 228   int xshift = fls64 (poly) - 1;
 229   shift = xshift - 8;
 230   uint64_t T1 = polymod (0, INT64 (1) << xshift, poly);
 231   for (int j = 0; j < 256; j++)
 232     T[j] = polymmult (j, T1, poly) | ((uint64_t) j << xshift);
 233 }
 234
 235 rabinpoly::rabinpoly (uint64_t p)
 236   : poly (p)
 237 {
 238   calcT ();
 239 }
 240
 241 class window : public rabinpoly {
 242 public:
 243   enum {size = 48};
 244   //enum {size = 24};
 245 private:
 246   uint64_t fingerprint;
 247   int bufpos;
 248   uint64_t U[256];
 249   uint8_t buf[size];
 250
 251 public:
 252   window (uint64_t poly);
 253   uint64_t slide8 (uint8_t m) {
 254     if (++bufpos >= size)
 255       bufpos = 0;
 256     uint8_t om = buf[bufpos];
 257     buf[bufpos] = m;
 258     return fingerprint = append8 (fingerprint ^ U[om], m);
 259   }
 260   void reset () {
 261     fingerprint = 0;
 262     bzero (buf, sizeof (buf));
 263   }
 264 };
 265
 266 window::window (uint64_t poly)
 267   : rabinpoly (poly), fingerprint (0), bufpos (-1)
 268 {
 269   uint64_t sizeshift = 1;
 270   for (int i = 1; i < size; i++)
 271     sizeshift = append8 (sizeshift, 0);
 272   for (int i = 0; i < 256; i++)
 273     U[i] = polymmult (i, sizeshift, poly);
 274   bzero (buf, sizeof (buf));
 275 }
 276
 277 } // end anonymous namespace
 278
 279 /* Public interface to this module. */
 280 int chunk_compute_max_num_breaks(size_t buflen)
 281 {
 282     return (buflen / MIN_CHUNK_SIZE) + 1;
 283 }
 284
 285 int chunk_compute_breaks(const char *buf, size_t len, size_t *breakpoints)
 286 {
 287     size_t start, pos;
 288     window w(FINGERPRINT_PT);
 289
 290     int i = 0;
 291     start = 0;
 292     for (pos = 0; pos < len; pos++) {
 293         uint64_t sig = w.slide8(buf[pos]);
 294         size_t block_len = pos - start + 1;
 295         if ((sig % TARGET_CHUNK_SIZE == BREAKMARK_VALUE
 296              && block_len >= MIN_CHUNK_SIZE) || block_len >= MAX_CHUNK_SIZE) {
 297             breakpoints[i] = pos;
 298             start = pos + 1;
 299             i++;
 300             w.reset();
 301         }
 302     }
 303
 304     if (start < len) {
 305         breakpoints[i] = len - 1;
 306         i++;
 307     }
 308
 309     return i;
 310 }
 311
 312 string chunk_algorithm_name()
 313 {
 314     char buf[64];
 315     sprintf(buf, "%s-%d", "lbfs", TARGET_CHUNK_SIZE);
 316     return buf;
 317 }