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 // FIXME: replace this with a not-stupid rolling checksum algorithm,
  13 // such as the one used in rsync (Adler32?)
  14 static uint32_t stupidsum_add(uint32_t old, uint8_t drop, uint8_t add)
  15 {
  16     return ((old<<1) | (old>>31)) ^ drop ^ add;
  17 }
  18
  19
  20 static int find_ofs(const unsigned char *buf, int len, int *bits)
  21 {
  22     unsigned char window[WINDOWSIZE];
  23     uint32_t sum = 0;
  24     int i = 0, count;
  25     memset(window, 0, sizeof(window));
  26
  27     for (count = 0; count < len; count++)
  28     {
  29         sum = stupidsum_add(sum, window[i], buf[count]);
  30         window[i] = buf[count];
  31         i = (i + 1) % WINDOWSIZE;
  32         if ((sum & (BLOBSIZE-1)) == ((~0) & (BLOBSIZE-1)))
  33         {
  34             if (bits)
  35             {
  36                 *bits = BLOBBITS;
  37                 sum >>= BLOBBITS;
  38                 for (*bits = BLOBBITS; (sum >>= 1) & 1; (*bits)++)
  39                     ;
  40             }
  41             return count+1;
  42         }
  43     }
  44     return 0;
  45 }
  46
  47
  48 static PyObject *blobbits(PyObject *self, PyObject *args)
  49 {
  50     if (!PyArg_ParseTuple(args, ""))
  51         return NULL;
  52     return Py_BuildValue("i", BLOBBITS);
  53 }
  54
  55
  56 static PyObject *splitbuf(PyObject *self, PyObject *args)
  57 {
  58     unsigned char *buf = NULL;
  59     int len = 0, out = 0, bits = -1;
  60
  61     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
  62         return NULL;
  63     out = find_ofs(buf, len, &bits);
  64     return Py_BuildValue("ii", out, bits);
  65 }
  66
  67
  68 static PyObject *bitmatch(PyObject *self, PyObject *args)
  69 {
  70     unsigned char *buf1 = NULL, *buf2 = NULL;
  71     int len1 = 0, len2 = 0;
  72     int byte, bit;
  73
  74     if (!PyArg_ParseTuple(args, "t#t#", &buf1, &len1, &buf2, &len2))
  75         return NULL;
  76
  77     bit = 0;
  78     for (byte = 0; byte < len1 && byte < len2; byte++)
  79     {
  80         int b1 = buf1[byte], b2 = buf2[byte];
  81         if (b1 != b2)
  82         {
  83             for (bit = 0; bit < 8; bit++)
  84                 if ( (b1 & (0x80 >> bit)) != (b2 & (0x80 >> bit)) )
  85                     break;
  86             break;
  87         }
  88     }
  89
  90     return Py_BuildValue("i", byte*8 + bit);
  91 }
  92
  93
  94 // I would have made this a lower-level function that just fills in a buffer
  95 // with random values, and then written those values from python.  But that's
  96 // about 20% slower in my tests, and since we typically generate random
  97 // numbers for benchmarking other parts of bup, any slowness in generating
  98 // random bytes will make our benchmarks inaccurate.  Plus nobody wants
  99 // pseudorandom bytes much except for this anyway.
 100 static PyObject *write_random(PyObject *self, PyObject *args)
 101 {
 102     uint32_t buf[1024/4];
 103     int fd = -1, seed = 0;
 104     ssize_t ret;
 105     long long len = 0, kbytes = 0, written = 0;
 106
 107     if (!PyArg_ParseTuple(args, "iLi", &fd, &len, &seed))
 108         return NULL;
 109
 110     srandom(seed);
 111
 112     for (kbytes = 0; kbytes < len/1024; kbytes++)
 113     {
 114         int i;
 115         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 116             buf[i] = random();
 117         ret = write(fd, buf, sizeof(buf));
 118         if (ret < 0)
 119             ret = 0;
 120         written += ret;
 121         if (ret < sizeof(buf))
 122             break;
 123         if (kbytes/1024 > 0 && !(kbytes%1024))
 124             fprintf(stderr, "Random: %lld Mbytes\r", kbytes/1024);
 125     }
 126
 127     // handle non-multiples of 1024
 128     if (len % 1024)
 129     {
 130         int i;
 131         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 132             buf[i] = random();
 133         ret = write(fd, buf, len % 1024);
 134         if (ret < 0)
 135             ret = 0;
 136         written += ret;
 137     }
 138
 139     if (kbytes/1024 > 0)
 140         fprintf(stderr, "Random: %lld Mbytes, done.\n", kbytes/1024);
 141     return Py_BuildValue("L", written);
 142 }
 143
 144
 145 static PyObject *open_noatime(PyObject *self, PyObject *args)
 146 {
 147     char *filename = NULL;
 148     int attrs, attrs_noatime, fd;
 149     if (!PyArg_ParseTuple(args, "s", &filename))
 150         return NULL;
 151     attrs = O_RDONLY;
 152 #ifdef O_NOFOLLOW
 153     attrs |= O_NOFOLLOW;
 154 #endif
 155 #ifdef O_LARGEFILE
 156     attrs |= O_LARGEFILE;
 157 #endif
 158     attrs_noatime = attrs;
 159 #ifdef O_NOATIME
 160     attrs_noatime |= O_NOATIME;
 161 #endif
 162     fd = open(filename, attrs_noatime);
 163     if (fd < 0 && errno == EPERM)
 164     {
 165         // older Linux kernels would return EPERM if you used O_NOATIME
 166         // and weren't the file's owner.  This pointless restriction was
 167         // relaxed eventually, but we have to handle it anyway.
 168         // (VERY old kernels didn't recognized O_NOATIME, but they would
 169         // just harmlessly ignore it, so this branch won't trigger)
 170         fd = open(filename, attrs);
 171     }
 172     if (fd < 0)
 173         return PyErr_SetFromErrnoWithFilename(PyExc_IOError, filename);
 174     return Py_BuildValue("i", fd);
 175 }
 176
 177
 178 static PyObject *fadvise_done(PyObject *self, PyObject *args)
 179 {
 180     int fd = -1;
 181     long long ofs = 0;
 182     if (!PyArg_ParseTuple(args, "iL", &fd, &ofs))
 183         return NULL;
 184 #ifdef POSIX_FADV_DONTNEED
 185     posix_fadvise(fd, 0, ofs, POSIX_FADV_DONTNEED);
 186 #endif
 187     return Py_BuildValue("");
 188 }
 189
 190
 191 static PyMethodDef hashsplit_methods[] = {
 192     { "blobbits", blobbits, METH_VARARGS,
 193         "Return the number of bits in the rolling checksum." },
 194     { "splitbuf", splitbuf, METH_VARARGS,
 195         "Split a list of strings based on a rolling checksum." },
 196     { "bitmatch", bitmatch, METH_VARARGS,
 197         "Count the number of matching prefix bits between two strings." },
 198     { "write_random", write_random, METH_VARARGS,
 199         "Write random bytes to the given file descriptor" },
 200     { "open_noatime", open_noatime, METH_VARARGS,
 201         "open() the given filename for read with O_NOATIME if possible" },
 202     { "fadvise_done", fadvise_done, METH_VARARGS,
 203         "Inform the kernel that we're finished with earlier parts of a file" },
 204     { NULL, NULL, 0, NULL },  // sentinel
 205 };
 206
 207 PyMODINIT_FUNC init_hashsplit(void)
 208 {
 209     Py_InitModule("_hashsplit", hashsplit_methods);
 210 }