lib/bup/_hashsplit.c

   1 #include <Python.h>
   2 #include <assert.h>
   3 #include <stdint.h>
   4 #include <fcntl.h>
   5
   6 #define BLOBBITS (13)
   7 #define BLOBSIZE (1<<BLOBBITS)
   8 #define WINDOWBITS (7)
   9 #define WINDOWSIZE (1<<(WINDOWBITS-1))
  10
  11
  12 typedef struct {
  13     uint32_t sum;
  14     uint8_t window[WINDOWSIZE];
  15     int wofs;
  16 } Rollsum;
  17
  18
  19 // FIXME: replace this with a not-stupid rolling checksum algorithm,
  20 // such as the one used in rsync (Adler32?)
  21 static void rollsum_add(Rollsum *r, uint8_t drop, uint8_t add)
  22 {
  23     r->sum = ((r->sum<<1) | (r->sum>>31)) ^ drop ^ add;
  24 }
  25
  26
  27 static void rollsum_init(Rollsum *r)
  28 {
  29     r->sum = r->wofs = 0;
  30     memset(r->window, 0, WINDOWSIZE);
  31 }
  32
  33
  34 // For some reason, gcc 4.3 (at least) optimizes badly if find_ofs()
  35 // is static and rollsum_roll is an inline function.  Let's use a macro
  36 // here instead to help out the optimizer.
  37 #define rollsum_roll(r, ch) do { \
  38     rollsum_add((r), (r)->window[(r)->wofs], (ch)); \
  39     (r)->window[(r)->wofs] = (ch); \
  40     (r)->wofs = ((r)->wofs + 1) % WINDOWSIZE; \
  41 } while (0)
  42
  43
  44 static uint32_t rollsum_sum(uint8_t *buf, size_t ofs, size_t len)
  45 {
  46     int count;
  47     Rollsum r;
  48     rollsum_init(&r);
  49     for (count = ofs; count < len; count++)
  50         rollsum_roll(&r, buf[count]);
  51     return r.sum;
  52 }
  53
  54
  55 static PyObject *selftest(PyObject *self, PyObject *args)
  56 {
  57     uint8_t buf[100000];
  58     uint32_t sum1a, sum1b, sum2a, sum2b, sum3a, sum3b;
  59     int count;
  60
  61     if (!PyArg_ParseTuple(args, ""))
  62         return NULL;
  63
  64     srandom(1);
  65     for (count = 0; count < sizeof(buf); count++)
  66         buf[count] = random();
  67
  68     sum1a = rollsum_sum(buf, 0, sizeof(buf));
  69     sum1b = rollsum_sum(buf, 1, sizeof(buf));
  70     sum2a = rollsum_sum(buf, sizeof(buf) - WINDOWSIZE*5/2,
  71                         sizeof(buf) - WINDOWSIZE);
  72     sum2b = rollsum_sum(buf, 0, sizeof(buf) - WINDOWSIZE);
  73     sum3a = rollsum_sum(buf, 0, WINDOWSIZE+3);
  74     sum3b = rollsum_sum(buf, 3, WINDOWSIZE+3);
  75
  76     fprintf(stderr, "sum1a = 0x%08x\n", sum1a);
  77     fprintf(stderr, "sum1b = 0x%08x\n", sum1b);
  78     fprintf(stderr, "sum2a = 0x%08x\n", sum2a);
  79     fprintf(stderr, "sum2b = 0x%08x\n", sum2b);
  80     fprintf(stderr, "sum3a = 0x%08x\n", sum3a);
  81     fprintf(stderr, "sum3b = 0x%08x\n", sum3b);
  82
  83     return Py_BuildValue("i", sum1a==sum1b && sum2a==sum2b && sum3a==sum3b);
  84 }
  85
  86
  87 static int find_ofs(const unsigned char *buf, int len, int *bits)
  88 {
  89     Rollsum r;
  90     int count;
  91
  92     rollsum_init(&r);
  93     for (count = 0; count < len; count++)
  94     {
  95         rollsum_roll(&r, buf[count]);
  96         if ((r.sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)))
  97         {
  98             if (bits)
  99             {
 100                 *bits = BLOBBITS;
 101                 r.sum >>= BLOBBITS;
 102                 for (*bits = BLOBBITS; (r.sum >>= 1) & 1; (*bits)++)
 103                     ;
 104             }
 105             return count+1;
 106         }
 107     }
 108     return 0;
 109 }
 110
 111
 112 static PyObject *blobbits(PyObject *self, PyObject *args)
 113 {
 114     if (!PyArg_ParseTuple(args, ""))
 115         return NULL;
 116     return Py_BuildValue("i", BLOBBITS);
 117 }
 118
 119
 120 static PyObject *splitbuf(PyObject *self, PyObject *args)
 121 {
 122     unsigned char *buf = NULL;
 123     int len = 0, out = 0, bits = -1;
 124
 125     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
 126         return NULL;
 127     out = find_ofs(buf, len, &bits);
 128     return Py_BuildValue("ii", out, bits);
 129 }
 130
 131
 132 static PyObject *bitmatch(PyObject *self, PyObject *args)
 133 {
 134     unsigned char *buf1 = NULL, *buf2 = NULL;
 135     int len1 = 0, len2 = 0;
 136     int byte, bit;
 137
 138     if (!PyArg_ParseTuple(args, "t#t#", &buf1, &len1, &buf2, &len2))
 139         return NULL;
 140
 141     bit = 0;
 142     for (byte = 0; byte < len1 && byte < len2; byte++)
 143     {
 144         int b1 = buf1[byte], b2 = buf2[byte];
 145         if (b1 != b2)
 146         {
 147             for (bit = 0; bit < 8; bit++)
 148                 if ( (b1 & (0x80 >> bit)) != (b2 & (0x80 >> bit)) )
 149                     break;
 150             break;
 151         }
 152     }
 153
 154     return Py_BuildValue("i", byte*8 + bit);
 155 }
 156
 157
 158 // I would have made this a lower-level function that just fills in a buffer
 159 // with random values, and then written those values from python.  But that's
 160 // about 20% slower in my tests, and since we typically generate random
 161 // numbers for benchmarking other parts of bup, any slowness in generating
 162 // random bytes will make our benchmarks inaccurate.  Plus nobody wants
 163 // pseudorandom bytes much except for this anyway.
 164 static PyObject *write_random(PyObject *self, PyObject *args)
 165 {
 166     uint32_t buf[1024/4];
 167     int fd = -1, seed = 0;
 168     ssize_t ret;
 169     long long len = 0, kbytes = 0, written = 0;
 170
 171     if (!PyArg_ParseTuple(args, "iLi", &fd, &len, &seed))
 172         return NULL;
 173
 174     srandom(seed);
 175
 176     for (kbytes = 0; kbytes < len/1024; kbytes++)
 177     {
 178         int i;
 179         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 180             buf[i] = random();
 181         ret = write(fd, buf, sizeof(buf));
 182         if (ret < 0)
 183             ret = 0;
 184         written += ret;
 185         if (ret < sizeof(buf))
 186             break;
 187         if (kbytes/1024 > 0 && !(kbytes%1024))
 188             fprintf(stderr, "Random: %lld Mbytes\r", kbytes/1024);
 189     }
 190
 191     // handle non-multiples of 1024
 192     if (len % 1024)
 193     {
 194         int i;
 195         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 196             buf[i] = random();
 197         ret = write(fd, buf, len % 1024);
 198         if (ret < 0)
 199             ret = 0;
 200         written += ret;
 201     }
 202
 203     if (kbytes/1024 > 0)
 204         fprintf(stderr, "Random: %lld Mbytes, done.\n", kbytes/1024);
 205     return Py_BuildValue("L", written);
 206 }
 207
 208
 209 static PyObject *open_noatime(PyObject *self, PyObject *args)
 210 {
 211     char *filename = NULL;
 212     int attrs, attrs_noatime, fd;
 213     if (!PyArg_ParseTuple(args, "s", &filename))
 214         return NULL;
 215     attrs = O_RDONLY;
 216 #ifdef O_NOFOLLOW
 217     attrs |= O_NOFOLLOW;
 218 #endif
 219 #ifdef O_LARGEFILE
 220     attrs |= O_LARGEFILE;
 221 #endif
 222     attrs_noatime = attrs;
 223 #ifdef O_NOATIME
 224     attrs_noatime |= O_NOATIME;
 225 #endif
 226     fd = open(filename, attrs_noatime);
 227     if (fd < 0 && errno == EPERM)
 228     {
 229         // older Linux kernels would return EPERM if you used O_NOATIME
 230         // and weren't the file's owner.  This pointless restriction was
 231         // relaxed eventually, but we have to handle it anyway.
 232         // (VERY old kernels didn't recognized O_NOATIME, but they would
 233         // just harmlessly ignore it, so this branch won't trigger)
 234         fd = open(filename, attrs);
 235     }
 236     if (fd < 0)
 237         return PyErr_SetFromErrnoWithFilename(PyExc_IOError, filename);
 238     return Py_BuildValue("i", fd);
 239 }
 240
 241
 242 static PyObject *fadvise_done(PyObject *self, PyObject *args)
 243 {
 244     int fd = -1;
 245     long long ofs = 0;
 246     if (!PyArg_ParseTuple(args, "iL", &fd, &ofs))
 247         return NULL;
 248 #ifdef POSIX_FADV_DONTNEED
 249     posix_fadvise(fd, 0, ofs, POSIX_FADV_DONTNEED);
 250 #endif
 251     return Py_BuildValue("");
 252 }
 253
 254
 255 static PyMethodDef hashsplit_methods[] = {
 256     { "selftest", selftest, METH_VARARGS,
 257         "Check that the rolling checksum rolls correctly (for unit tests)." },
 258     { "blobbits", blobbits, METH_VARARGS,
 259         "Return the number of bits in the rolling checksum." },
 260     { "splitbuf", splitbuf, METH_VARARGS,
 261         "Split a list of strings based on a rolling checksum." },
 262     { "bitmatch", bitmatch, METH_VARARGS,
 263         "Count the number of matching prefix bits between two strings." },
 264     { "write_random", write_random, METH_VARARGS,
 265         "Write random bytes to the given file descriptor" },
 266     { "open_noatime", open_noatime, METH_VARARGS,
 267         "open() the given filename for read with O_NOATIME if possible" },
 268     { "fadvise_done", fadvise_done, METH_VARARGS,
 269         "Inform the kernel that we're finished with earlier parts of a file" },
 270     { NULL, NULL, 0, NULL },  // sentinel
 271 };
 272
 273 PyMODINIT_FUNC init_hashsplit(void)
 274 {
 275     Py_InitModule("_hashsplit", hashsplit_methods);
 276 }