third_party/chunk.cc

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