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