lib/bup/_helpers.c

   1 #include "bupsplit.h"
   2 #include <Python.h>
   3 #include <assert.h>
   4 #include <stdint.h>
   5 #include <fcntl.h>
   6 #include <arpa/inet.h>
   7
   8 static PyObject *selftest(PyObject *self, PyObject *args)
   9 {
  10     if (!PyArg_ParseTuple(args, ""))
  11         return NULL;
  12
  13     return Py_BuildValue("i", !bupsplit_selftest());
  14 }
  15
  16
  17 static PyObject *blobbits(PyObject *self, PyObject *args)
  18 {
  19     if (!PyArg_ParseTuple(args, ""))
  20         return NULL;
  21     return Py_BuildValue("i", BUP_BLOBBITS);
  22 }
  23
  24
  25 static PyObject *splitbuf(PyObject *self, PyObject *args)
  26 {
  27     unsigned char *buf = NULL;
  28     int len = 0, out = 0, bits = -1;
  29
  30     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
  31         return NULL;
  32     out = bupsplit_find_ofs(buf, len, &bits);
  33     return Py_BuildValue("ii", out, bits);
  34 }
  35
  36
  37 static PyObject *bitmatch(PyObject *self, PyObject *args)
  38 {
  39     unsigned char *buf1 = NULL, *buf2 = NULL;
  40     int len1 = 0, len2 = 0;
  41     int byte, bit;
  42
  43     if (!PyArg_ParseTuple(args, "t#t#", &buf1, &len1, &buf2, &len2))
  44         return NULL;
  45
  46     bit = 0;
  47     for (byte = 0; byte < len1 && byte < len2; byte++)
  48     {
  49         int b1 = buf1[byte], b2 = buf2[byte];
  50         if (b1 != b2)
  51         {
  52             for (bit = 0; bit < 8; bit++)
  53                 if ( (b1 & (0x80 >> bit)) != (b2 & (0x80 >> bit)) )
  54                     break;
  55             break;
  56         }
  57     }
  58
  59     return Py_BuildValue("i", byte*8 + bit);
  60 }
  61
  62
  63 static PyObject *firstword(PyObject *self, PyObject *args)
  64 {
  65     unsigned char *buf = NULL;
  66     int len = 0;
  67     uint32_t v;
  68
  69     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
  70         return NULL;
  71
  72     if (len < 4)
  73         return NULL;
  74
  75     v = ntohl(*(uint32_t *)buf);
  76     return PyLong_FromUnsignedLong(v);
  77 }
  78
  79
  80 typedef struct {
  81     uint32_t high;
  82     unsigned char low;
  83 } bits40_t;
  84
  85
  86 static void to_bloom_address_bitmask4(const bits40_t *buf,
  87         const int nbits, uint64_t *v, unsigned char *bitmask)
  88 {
  89     int bit;
  90     uint64_t raw, mask;
  91
  92     mask = (1<<nbits) - 1;
  93     raw = (((uint64_t)ntohl(buf->high)) << 8) | buf->low;
  94     bit = (raw >> (37-nbits)) & 0x7;
  95     *v = (raw >> (40-nbits)) & mask;
  96     *bitmask = 1 << bit;
  97 }
  98
  99 static void to_bloom_address_bitmask5(const uint32_t *buf,
 100         const int nbits, uint32_t *v, unsigned char *bitmask)
 101 {
 102     int bit;
 103     uint32_t raw, mask;
 104
 105     mask = (1<<nbits) - 1;
 106     raw = ntohl(*buf);
 107     bit = (raw >> (29-nbits)) & 0x7;
 108     *v = (raw >> (32-nbits)) & mask;
 109     *bitmask = 1 << bit;
 110 }
 111
 112
 113 #define BLOOM_SET_BIT(name, address, itype, otype) \
 114 static void name(unsigned char *bloom, const void *buf, const int nbits)\
 115 {\
 116     unsigned char bitmask;\
 117     otype v;\
 118     address((itype *)buf, nbits, &v, &bitmask);\
 119     bloom[16+v] |= bitmask;\
 120 }
 121 BLOOM_SET_BIT(bloom_set_bit4, to_bloom_address_bitmask4, bits40_t, uint64_t)
 122 BLOOM_SET_BIT(bloom_set_bit5, to_bloom_address_bitmask5, uint32_t, uint32_t)
 123
 124
 125 #define BLOOM_GET_BIT(name, address, itype, otype) \
 126 static int name(const unsigned char *bloom, const void *buf, const int nbits)\
 127 {\
 128     unsigned char bitmask;\
 129     otype v;\
 130     address((itype *)buf, nbits, &v, &bitmask);\
 131     return bloom[16+v] & bitmask;\
 132 }
 133 BLOOM_GET_BIT(bloom_get_bit4, to_bloom_address_bitmask4, bits40_t, uint64_t)
 134 BLOOM_GET_BIT(bloom_get_bit5, to_bloom_address_bitmask5, uint32_t, uint32_t)
 135
 136
 137 static PyObject *bloom_add(PyObject *self, PyObject *args)
 138 {
 139     void (*bloom_set_bit)(unsigned char *, const void *, const int);
 140     unsigned char *sha = NULL, *bloom = NULL;
 141     unsigned char *end;
 142     int len = 0, blen = 0, nbits = 0, k = 0;
 143
 144     if (!PyArg_ParseTuple(args, "w#s#ii", &bloom, &blen, &sha, &len, &nbits, &k))
 145         return NULL;
 146
 147     if (k == 5)
 148     {
 149         if (nbits > 29)
 150             return NULL;
 151         bloom_set_bit = &bloom_set_bit5;
 152     }
 153     else if (k == 4)
 154     {
 155         if (nbits > 37)
 156             return NULL;
 157         bloom_set_bit = &bloom_set_bit4;
 158     }
 159     else
 160         return NULL;
 161
 162     if (blen < 16+(1<<nbits) || len % 20 != 0)
 163         return NULL;
 164
 165     for (end = sha + len; sha < end; sha += 20/k)
 166         (*bloom_set_bit)(bloom, sha, nbits);
 167
 168     return Py_BuildValue("i", len/20);
 169 }
 170
 171 static PyObject *bloom_contains(PyObject *self, PyObject *args)
 172 {
 173     int (*bloom_get_bit)(const unsigned char *, const void *, const int);
 174     unsigned char *sha = NULL, *bloom = NULL;
 175     int len = 0, blen = 0, nbits = 0, k = 0;
 176     unsigned char *end;
 177     int steps;
 178
 179     if (!PyArg_ParseTuple(args, "t#s#ii", &bloom, &blen, &sha, &len, &nbits, &k))
 180         return NULL;
 181
 182     if (len != 20)
 183         return NULL;
 184
 185     if (k == 5)
 186     {
 187         if (nbits > 29)
 188             return NULL;
 189         bloom_get_bit = &bloom_get_bit5;
 190     }
 191     else if (k == 4)
 192     {
 193         if (nbits > 37)
 194             return NULL;
 195         bloom_get_bit = &bloom_get_bit4;
 196     }
 197     else
 198         return NULL;
 199
 200     for (steps = 1, end = sha + 20; sha < end; sha += 20/k, steps++)
 201         if (!bloom_get_bit(bloom, sha, nbits))
 202             return Py_BuildValue("Oi", Py_None, steps);
 203
 204     return Py_BuildValue("Oi", Py_True, k);
 205 }
 206
 207
 208 static uint32_t _extract_bits(unsigned char *buf, int nbits)
 209 {
 210     uint32_t v, mask;
 211
 212     mask = (1<<nbits) - 1;
 213     v = ntohl(*(uint32_t *)buf);
 214     v = (v >> (32-nbits)) & mask;
 215     return v;
 216 }
 217 static PyObject *extract_bits(PyObject *self, PyObject *args)
 218 {
 219     unsigned char *buf = NULL;
 220     int len = 0, nbits = 0;
 221
 222     if (!PyArg_ParseTuple(args, "t#i", &buf, &len, &nbits))
 223         return NULL;
 224
 225     if (len < 4)
 226         return NULL;
 227
 228     return PyLong_FromUnsignedLong(_extract_bits(buf, nbits));
 229 }
 230
 231
 232 struct sha {
 233     unsigned char bytes[20];
 234 };
 235 struct idx {
 236     unsigned char *map;
 237     struct sha *cur;
 238     struct sha *end;
 239     uint32_t *cur_name;
 240     Py_ssize_t bytes;
 241     long name_base;
 242 };
 243
 244
 245 static int _cmp_sha(const struct sha *sha1, const struct sha *sha2)
 246 {
 247     int i;
 248     for (i = 0; i < 20; i++)
 249         if (sha1->bytes[i] != sha2->bytes[i])
 250             return sha1->bytes[i] - sha2->bytes[i];
 251     return 0;
 252 }
 253
 254
 255 static void _fix_idx_order(struct idx **idxs, long *last_i)
 256 {
 257     struct idx *idx;
 258     int low, mid, high, c = 0;
 259
 260     idx = idxs[*last_i];
 261     if (idxs[*last_i]->cur >= idxs[*last_i]->end)
 262     {
 263         idxs[*last_i] = NULL;
 264         PyMem_Free(idx);
 265         --*last_i;
 266         return;
 267     }
 268     if (*last_i == 0)
 269         return;
 270
 271     low = *last_i-1;
 272     mid = *last_i;
 273     high = 0;
 274     while (low >= high)
 275     {
 276         mid = (low + high) / 2;
 277         c = _cmp_sha(idx->cur, idxs[mid]->cur);
 278         if (c < 0)
 279             high = mid + 1;
 280         else if (c > 0)
 281             low = mid - 1;
 282         else
 283             break;
 284     }
 285     if (c < 0)
 286         ++mid;
 287     if (mid == *last_i)
 288         return;
 289     memmove(&idxs[mid+1], &idxs[mid], (*last_i-mid)*sizeof(struct idx *));
 290     idxs[mid] = idx;
 291 }
 292
 293
 294 static uint32_t _get_idx_i(struct idx *idx)
 295 {
 296     if (idx->cur_name == NULL)
 297         return idx->name_base;
 298     return ntohl(*idx->cur_name) + idx->name_base;
 299 }
 300
 301
 302 static PyObject *merge_into(PyObject *self, PyObject *args)
 303 {
 304     PyObject *ilist = NULL;
 305     unsigned char *fmap = NULL;
 306     struct sha *sha_ptr, *last = NULL;
 307     uint32_t *table_ptr, *name_ptr;
 308     struct idx **idxs = NULL;
 309     int flen = 0, bits = 0, i;
 310     uint32_t total, count, prefix;
 311     Py_ssize_t num_i;
 312     long last_i;
 313
 314     if (!PyArg_ParseTuple(args, "w#iIO", &fmap, &flen, &bits, &total, &ilist))
 315         return NULL;
 316
 317     num_i = PyList_Size(ilist);
 318     idxs = (struct idx **)PyMem_Malloc(num_i * sizeof(struct idx *));
 319
 320     for (i = 0; i < num_i; i++)
 321     {
 322         long len, sha_ofs, name_map_ofs;
 323         idxs[i] = (struct idx *)PyMem_Malloc(sizeof(struct idx));
 324         PyObject *itup = PyList_GetItem(ilist, i);
 325         PyObject_AsReadBuffer(PyTuple_GetItem(itup, 0),
 326                 (const void **)&idxs[i]->map, &idxs[i]->bytes);
 327         len = PyInt_AsLong(PyTuple_GetItem(itup, 1));
 328         sha_ofs = PyInt_AsLong(PyTuple_GetItem(itup, 2));
 329         name_map_ofs = PyInt_AsLong(PyTuple_GetItem(itup, 3));
 330         idxs[i]->cur = (struct sha *)&idxs[i]->map[sha_ofs];
 331         idxs[i]->end = &idxs[i]->cur[len];
 332         idxs[i]->cur_name = (uint32_t *)&idxs[i]->map[name_map_ofs];
 333         idxs[i]->name_base = PyInt_AsLong(PyTuple_GetItem(itup, 4));
 334     }
 335     table_ptr = (uint32_t *)&fmap[12];
 336     sha_ptr = (struct sha *)&table_ptr[1<<bits];
 337     name_ptr = (uint32_t *)&sha_ptr[total];
 338
 339     last_i = num_i-1;
 340     count = 0;
 341     prefix = 0;
 342     while (last_i >= 0)
 343     {
 344         struct idx *idx;
 345         uint32_t new_prefix;
 346         if (count % 102424 == 0)
 347             PySys_WriteStderr("midx: writing %.2f%% (%d/%d)\r",
 348                     count*100.0/total, count, total);
 349         idx = idxs[last_i];
 350         new_prefix = _extract_bits((unsigned char *)idx->cur, bits);
 351         while (prefix < new_prefix)
 352             table_ptr[prefix++] = htonl(count);
 353         if (last == NULL || _cmp_sha(last, idx->cur) != 0)
 354         {
 355             memcpy(sha_ptr++, idx->cur, 20);
 356             *name_ptr++ = htonl(_get_idx_i(idx));
 357             last = idx->cur;
 358         }
 359         ++idx->cur;
 360         if (idx->cur_name != NULL)
 361             ++idx->cur_name;
 362         _fix_idx_order(idxs, &last_i);
 363         ++count;
 364     }
 365     table_ptr[prefix] = htonl(count);
 366
 367     PyMem_Free(idxs);
 368     return PyLong_FromUnsignedLong(count);
 369 }
 370
 371
 372 // I would have made this a lower-level function that just fills in a buffer
 373 // with random values, and then written those values from python.  But that's
 374 // about 20% slower in my tests, and since we typically generate random
 375 // numbers for benchmarking other parts of bup, any slowness in generating
 376 // random bytes will make our benchmarks inaccurate.  Plus nobody wants
 377 // pseudorandom bytes much except for this anyway.
 378 static PyObject *write_random(PyObject *self, PyObject *args)
 379 {
 380     uint32_t buf[1024/4];
 381     int fd = -1, seed = 0, verbose = 0;
 382     ssize_t ret;
 383     long long len = 0, kbytes = 0, written = 0;
 384
 385     if (!PyArg_ParseTuple(args, "iLii", &fd, &len, &seed, &verbose))
 386         return NULL;
 387
 388     srandom(seed);
 389
 390     for (kbytes = 0; kbytes < len/1024; kbytes++)
 391     {
 392         unsigned i;
 393         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 394             buf[i] = random();
 395         ret = write(fd, buf, sizeof(buf));
 396         if (ret < 0)
 397             ret = 0;
 398         written += ret;
 399         if (ret < (int)sizeof(buf))
 400             break;
 401         if (verbose && kbytes/1024 > 0 && !(kbytes%1024))
 402             fprintf(stderr, "Random: %lld Mbytes\r", kbytes/1024);
 403     }
 404
 405     // handle non-multiples of 1024
 406     if (len % 1024)
 407     {
 408         unsigned i;
 409         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 410             buf[i] = random();
 411         ret = write(fd, buf, len % 1024);
 412         if (ret < 0)
 413             ret = 0;
 414         written += ret;
 415     }
 416
 417     if (kbytes/1024 > 0)
 418         fprintf(stderr, "Random: %lld Mbytes, done.\n", kbytes/1024);
 419     return Py_BuildValue("L", written);
 420 }
 421
 422
 423 static PyObject *random_sha(PyObject *self, PyObject *args)
 424 {
 425     static int seeded = 0;
 426     uint32_t shabuf[20/4];
 427     int i;
 428
 429     if (!seeded)
 430     {
 431         assert(sizeof(shabuf) == 20);
 432         srandom(time(NULL));
 433         seeded = 1;
 434     }
 435
 436     if (!PyArg_ParseTuple(args, ""))
 437         return NULL;
 438
 439     memset(shabuf, 0, sizeof(shabuf));
 440     for (i=0; i < 20/4; i++)
 441         shabuf[i] = random();
 442     return Py_BuildValue("s#", shabuf, 20);
 443 }
 444
 445
 446 static PyObject *open_noatime(PyObject *self, PyObject *args)
 447 {
 448     char *filename = NULL;
 449     int attrs, attrs_noatime, fd;
 450     if (!PyArg_ParseTuple(args, "s", &filename))
 451         return NULL;
 452     attrs = O_RDONLY;
 453 #ifdef O_NOFOLLOW
 454     attrs |= O_NOFOLLOW;
 455 #endif
 456 #ifdef O_LARGEFILE
 457     attrs |= O_LARGEFILE;
 458 #endif
 459     attrs_noatime = attrs;
 460 #ifdef O_NOATIME
 461     attrs_noatime |= O_NOATIME;
 462 #endif
 463     fd = open(filename, attrs_noatime);
 464     if (fd < 0 && errno == EPERM)
 465     {
 466         // older Linux kernels would return EPERM if you used O_NOATIME
 467         // and weren't the file's owner.  This pointless restriction was
 468         // relaxed eventually, but we have to handle it anyway.
 469         // (VERY old kernels didn't recognized O_NOATIME, but they would
 470         // just harmlessly ignore it, so this branch won't trigger)
 471         fd = open(filename, attrs);
 472     }
 473     if (fd < 0)
 474         return PyErr_SetFromErrnoWithFilename(PyExc_IOError, filename);
 475     return Py_BuildValue("i", fd);
 476 }
 477
 478
 479 static PyObject *fadvise_done(PyObject *self, PyObject *args)
 480 {
 481     int fd = -1;
 482     long long ofs = 0;
 483     if (!PyArg_ParseTuple(args, "iL", &fd, &ofs))
 484         return NULL;
 485 #ifdef POSIX_FADV_DONTNEED
 486     posix_fadvise(fd, 0, ofs, POSIX_FADV_DONTNEED);
 487 #endif
 488     return Py_BuildValue("");
 489 }
 490
 491
 492 static PyMethodDef faster_methods[] = {
 493     { "selftest", selftest, METH_VARARGS,
 494         "Check that the rolling checksum rolls correctly (for unit tests)." },
 495     { "blobbits", blobbits, METH_VARARGS,
 496         "Return the number of bits in the rolling checksum." },
 497     { "splitbuf", splitbuf, METH_VARARGS,
 498         "Split a list of strings based on a rolling checksum." },
 499     { "bitmatch", bitmatch, METH_VARARGS,
 500         "Count the number of matching prefix bits between two strings." },
 501     { "firstword", firstword, METH_VARARGS,
 502         "Return an int corresponding to the first 32 bits of buf." },
 503     { "bloom_contains", bloom_contains, METH_VARARGS,
 504         "Check if a bloom filter of 2^nbits bytes contains an object" },
 505     { "bloom_add", bloom_add, METH_VARARGS,
 506         "Add an object to a bloom filter of 2^nbits bytes" },
 507     { "extract_bits", extract_bits, METH_VARARGS,
 508         "Take the first 'nbits' bits from 'buf' and return them as an int." },
 509     { "merge_into", merge_into, METH_VARARGS,
 510         "Merges a bunch of idx and midx files into a single midx." },
 511     { "write_random", write_random, METH_VARARGS,
 512         "Write random bytes to the given file descriptor" },
 513     { "random_sha", random_sha, METH_VARARGS,
 514         "Return a random 20-byte string" },
 515     { "open_noatime", open_noatime, METH_VARARGS,
 516         "open() the given filename for read with O_NOATIME if possible" },
 517     { "fadvise_done", fadvise_done, METH_VARARGS,
 518         "Inform the kernel that we're finished with earlier parts of a file" },
 519     { NULL, NULL, 0, NULL },  // sentinel
 520 };
 521
 522 PyMODINIT_FUNC init_helpers(void)
 523 {
 524     Py_InitModule("_helpers", faster_methods);
 525 }