lib/bup/_helpers.c

   1 #define _LARGEFILE64_SOURCE 1
   2 #define PY_SSIZE_T_CLEAN 1
   3 #undef NDEBUG
   4 #include "../../config/config.h"
   5
   6 // According to Python, its header has to go first:
   7 //   http://docs.python.org/2/c-api/intro.html#include-files
   8 #include <Python.h>
   9
  10 #include <assert.h>
  11 #include <errno.h>
  12 #include <fcntl.h>
  13 #include <arpa/inet.h>
  14 #include <stddef.h>
  15 #include <stdint.h>
  16 #include <stdlib.h>
  17 #include <stdio.h>
  18
  19 #ifdef HAVE_SYS_MMAN_H
  20 #include <sys/mman.h>
  21 #endif
  22 #ifdef HAVE_SYS_TYPES_H
  23 #include <sys/types.h>
  24 #endif
  25 #ifdef HAVE_SYS_STAT_H
  26 #include <sys/stat.h>
  27 #endif
  28 #ifdef HAVE_UNISTD_H
  29 #include <unistd.h>
  30 #endif
  31
  32 #ifdef HAVE_LINUX_FS_H
  33 #include <linux/fs.h>
  34 #endif
  35 #ifdef HAVE_SYS_IOCTL_H
  36 #include <sys/ioctl.h>
  37 #endif
  38
  39 #ifdef HAVE_TM_TM_GMTOFF
  40 #include <time.h>
  41 #endif
  42
  43 #include "bupsplit.h"
  44
  45 #if defined(FS_IOC_GETFLAGS) && defined(FS_IOC_SETFLAGS)
  46 #define BUP_HAVE_FILE_ATTRS 1
  47 #endif
  48
  49 /*
  50  * Check for incomplete UTIMENSAT support (NetBSD 6), and if so,
  51  * pretend we don't have it.
  52  */
  53 #if !defined(AT_FDCWD) || !defined(AT_SYMLINK_NOFOLLOW)
  54 #undef HAVE_UTIMENSAT
  55 #endif
  56
  57 #ifndef FS_NOCOW_FL
  58 // Of course, this assumes it's a bitfield value.
  59 #define FS_NOCOW_FL 0
  60 #endif
  61
  62
  63 typedef unsigned char byte;
  64
  65 static int istty2 = 0;
  66
  67
  68 #ifndef htonll
  69 // This function should technically be macro'd out if it's going to be used
  70 // more than ocasionally.  As of this writing, it'll actually never be called
  71 // in real world bup scenarios (because our packs are < MAX_INT bytes).
  72 static uint64_t htonll(uint64_t value)
  73 {
  74     static const int endian_test = 42;
  75
  76     if (*(char *)&endian_test == endian_test) // LSB-MSB
  77         return ((uint64_t)htonl(value & 0xFFFFFFFF) << 32) | htonl(value >> 32);
  78     return value; // already in network byte order MSB-LSB
  79 }
  80 #endif
  81
  82
  83 #define INTEGRAL_ASSIGNMENT_FITS(dest, src)                             \
  84     ({                                                                  \
  85         *(dest) = (src);                                                \
  86         *(dest) == (src) && (*(dest) < 1) == ((src) < 1);               \
  87     })
  88
  89
  90 // At the moment any code that calls INTGER_TO_PY() will have to
  91 // disable -Wtautological-compare for clang.  See below.
  92
  93 #define INTEGER_TO_PY(x) \
  94     (((x) >= 0) ? PyLong_FromUnsignedLongLong(x) : PyLong_FromLongLong(x))
  95
  96
  97 static int bup_ulong_from_pyint(unsigned long *x, PyObject *py,
  98                                 const char *name)
  99 {
 100     const long tmp = PyInt_AsLong(py);
 101     if (tmp == -1 && PyErr_Occurred())
 102     {
 103         if (PyErr_ExceptionMatches(PyExc_OverflowError))
 104             PyErr_Format(PyExc_OverflowError, "%s too big for unsigned long",
 105                          name);
 106         return 0;
 107     }
 108     if (tmp < 0)
 109     {
 110         PyErr_Format(PyExc_OverflowError,
 111                      "negative %s cannot be converted to unsigned long", name);
 112         return 0;
 113     }
 114     *x = tmp;
 115     return 1;
 116 }
 117
 118
 119 static int bup_ulong_from_py(unsigned long *x, PyObject *py, const char *name)
 120 {
 121     if (PyInt_Check(py))
 122         return bup_ulong_from_pyint(x, py, name);
 123
 124     if (!PyLong_Check(py))
 125     {
 126         PyErr_Format(PyExc_TypeError, "expected integer %s", name);
 127         return 0;
 128     }
 129
 130     const unsigned long tmp = PyLong_AsUnsignedLong(py);
 131     if (PyErr_Occurred())
 132     {
 133         if (PyErr_ExceptionMatches(PyExc_OverflowError))
 134             PyErr_Format(PyExc_OverflowError, "%s too big for unsigned long",
 135                          name);
 136         return 0;
 137     }
 138     *x = tmp;
 139     return 1;
 140 }
 141
 142
 143 static int bup_uint_from_py(unsigned int *x, PyObject *py, const char *name)
 144 {
 145     unsigned long tmp;
 146     if (!bup_ulong_from_py(&tmp, py, name))
 147         return 0;
 148
 149     if (tmp > UINT_MAX)
 150     {
 151         PyErr_Format(PyExc_OverflowError, "%s too big for unsigned int", name);
 152         return 0;
 153     }
 154     *x = tmp;
 155     return 1;
 156 }
 157
 158 static int bup_ullong_from_py(unsigned PY_LONG_LONG *x, PyObject *py,
 159                               const char *name)
 160 {
 161     if (PyInt_Check(py))
 162     {
 163         unsigned long tmp;
 164         if (bup_ulong_from_pyint(&tmp, py, name))
 165         {
 166             *x = tmp;
 167             return 1;
 168         }
 169         return 0;
 170     }
 171
 172     if (!PyLong_Check(py))
 173     {
 174         PyErr_Format(PyExc_TypeError, "integer argument expected for %s", name);
 175         return 0;
 176     }
 177
 178     const unsigned PY_LONG_LONG tmp = PyLong_AsUnsignedLongLong(py);
 179     if (tmp == (unsigned long long) -1 && PyErr_Occurred())
 180     {
 181         if (PyErr_ExceptionMatches(PyExc_OverflowError))
 182             PyErr_Format(PyExc_OverflowError,
 183                          "%s too big for unsigned long long", name);
 184         return 0;
 185     }
 186     *x = tmp;
 187     return 1;
 188 }
 189
 190
 191 // Probably we should use autoconf or something and set HAVE_PY_GETARGCARGV...
 192 #if __WIN32__ || __CYGWIN__
 193
 194 // There's no 'ps' on win32 anyway, and Py_GetArgcArgv() isn't available.
 195 static void unpythonize_argv(void) { }
 196
 197 #else // not __WIN32__
 198
 199 // For some reason this isn't declared in Python.h
 200 extern void Py_GetArgcArgv(int *argc, char ***argv);
 201
 202 static void unpythonize_argv(void)
 203 {
 204     int argc, i;
 205     char **argv, *arge;
 206
 207     Py_GetArgcArgv(&argc, &argv);
 208
 209     for (i = 0; i < argc-1; i++)
 210     {
 211         if (argv[i] + strlen(argv[i]) + 1 != argv[i+1])
 212         {
 213             // The argv block doesn't work the way we expected; it's unsafe
 214             // to mess with it.
 215             return;
 216         }
 217     }
 218
 219     arge = argv[argc-1] + strlen(argv[argc-1]) + 1;
 220
 221     if (strstr(argv[0], "python") && argv[1] == argv[0] + strlen(argv[0]) + 1)
 222     {
 223         char *p;
 224         size_t len, diff;
 225         p = strrchr(argv[1], '/');
 226         if (p)
 227         {
 228             p++;
 229             diff = p - argv[0];
 230             len = arge - p;
 231             memmove(argv[0], p, len);
 232             memset(arge - diff, 0, diff);
 233             for (i = 0; i < argc; i++)
 234                 argv[i] = argv[i+1] ? argv[i+1]-diff : NULL;
 235         }
 236     }
 237 }
 238
 239 #endif // not __WIN32__ or __CYGWIN__
 240
 241
 242 static int write_all(int fd, const void *buf, const size_t count)
 243 {
 244     size_t written = 0;
 245     while (written < count)
 246     {
 247         const ssize_t rc = write(fd, buf + written, count - written);
 248         if (rc == -1)
 249             return -1;
 250         written += rc;
 251     }
 252     return 0;
 253 }
 254
 255
 256 static int uadd(unsigned long long *dest,
 257                 const unsigned long long x,
 258                 const unsigned long long y)
 259 {
 260     const unsigned long long result = x + y;
 261     if (result < x || result < y)
 262         return 0;
 263     *dest = result;
 264     return 1;
 265 }
 266
 267
 268 static PyObject *append_sparse_region(const int fd, unsigned long long n)
 269 {
 270     while (n)
 271     {
 272         off_t new_off;
 273         if (!INTEGRAL_ASSIGNMENT_FITS(&new_off, n))
 274             new_off = INT_MAX;
 275         const off_t off = lseek(fd, new_off, SEEK_CUR);
 276         if (off == (off_t) -1)
 277             return PyErr_SetFromErrno(PyExc_IOError);
 278         n -= new_off;
 279     }
 280     return NULL;
 281 }
 282
 283
 284 static PyObject *record_sparse_zeros(unsigned long long *new_pending,
 285                                      const int fd,
 286                                      unsigned long long prev_pending,
 287                                      const unsigned long long count)
 288 {
 289     // Add count additional sparse zeros to prev_pending and store the
 290     // result in new_pending, or if the total won't fit in
 291     // new_pending, write some of the zeros to fd sparsely, and store
 292     // the remaining sum in new_pending.
 293     if (!uadd(new_pending, prev_pending, count))
 294     {
 295         PyObject *err = append_sparse_region(fd, prev_pending);
 296         if (err != NULL)
 297             return err;
 298         *new_pending = count;
 299     }
 300     return NULL;
 301 }
 302
 303
 304 static const byte * find_not_zero(const byte * const start,
 305                                   const byte * const end)
 306 {
 307     // Return a pointer to first non-zero byte between start and end,
 308     // or end if there isn't one.
 309     assert(start <= end);
 310     const unsigned char *cur = start;
 311     while (cur < end && *cur == 0)
 312         cur++;
 313     return cur;
 314 }
 315
 316
 317 static const byte * const find_trailing_zeros(const byte * const start,
 318                                               const byte * const end)
 319 {
 320     // Return a pointer to the start of any trailing run of zeros, or
 321     // end if there isn't one.
 322     assert(start <= end);
 323     if (start == end)
 324         return end;
 325     const byte * cur = end;
 326     while (cur > start && *--cur == 0) {}
 327     if (*cur == 0)
 328         return cur;
 329     else
 330         return cur + 1;
 331 }
 332
 333
 334 static const byte *find_non_sparse_end(const byte * const start,
 335                                        const byte * const end,
 336                                        const unsigned long long min_len)
 337 {
 338     // Return the first pointer to a min_len sparse block in [start,
 339     // end) if there is one, otherwise a pointer to the start of any
 340     // trailing run of zeros.  If there are no trailing zeros, return
 341     // end.
 342     if (start == end)
 343         return end;
 344     assert(start < end);
 345     assert(min_len);
 346     // Probe in min_len jumps, searching backward from the jump
 347     // destination for a non-zero byte.  If such a byte is found, move
 348     // just past it and try again.
 349     const byte *candidate = start;
 350     // End of any run of zeros, starting at candidate, that we've already seen
 351     const byte *end_of_known_zeros = candidate;
 352     while (end - candidate >= min_len) // Handle all min_len candidate blocks
 353     {
 354         const byte * const probe_end = candidate + min_len;
 355         const byte * const trailing_zeros =
 356             find_trailing_zeros(end_of_known_zeros, probe_end);
 357         if (trailing_zeros == probe_end)
 358             end_of_known_zeros = candidate = probe_end;
 359         else if (trailing_zeros == end_of_known_zeros)
 360         {
 361             assert(candidate >= start);
 362             assert(candidate <= end);
 363             assert(*candidate == 0);
 364             return candidate;
 365         }
 366         else
 367         {
 368             candidate = trailing_zeros;
 369             end_of_known_zeros = probe_end;
 370         }
 371     }
 372
 373     if (candidate == end)
 374         return end;
 375
 376     // No min_len sparse run found, search backward from end
 377     const byte * const trailing_zeros = find_trailing_zeros(end_of_known_zeros,
 378                                                             end);
 379
 380     if (trailing_zeros == end_of_known_zeros)
 381     {
 382         assert(candidate >= start);
 383         assert(candidate < end);
 384         assert(*candidate == 0);
 385         assert(end - candidate < min_len);
 386         return candidate;
 387     }
 388
 389     if (trailing_zeros == end)
 390     {
 391         assert(*(end - 1) != 0);
 392         return end;
 393     }
 394
 395     assert(end - trailing_zeros < min_len);
 396     assert(trailing_zeros >= start);
 397     assert(trailing_zeros < end);
 398     assert(*trailing_zeros == 0);
 399     return trailing_zeros;
 400 }
 401
 402
 403 static PyObject *bup_write_sparsely(PyObject *self, PyObject *args)
 404 {
 405     int fd;
 406     unsigned char *buf = NULL;
 407     Py_ssize_t sbuf_len;
 408     PyObject *py_min_sparse_len, *py_prev_sparse_len;
 409     if (!PyArg_ParseTuple(args, "it#OO",
 410                           &fd, &buf, &sbuf_len,
 411                           &py_min_sparse_len, &py_prev_sparse_len))
 412         return NULL;
 413     unsigned long long min_sparse_len, prev_sparse_len, buf_len;
 414     if (!bup_ullong_from_py(&min_sparse_len, py_min_sparse_len, "min_sparse_len"))
 415         return NULL;
 416     if (!bup_ullong_from_py(&prev_sparse_len, py_prev_sparse_len, "prev_sparse_len"))
 417         return NULL;
 418     if (sbuf_len < 0)
 419         return PyErr_Format(PyExc_ValueError, "negative bufer length");
 420     if (!INTEGRAL_ASSIGNMENT_FITS(&buf_len, sbuf_len))
 421         return PyErr_Format(PyExc_OverflowError, "buffer length too large");
 422
 423     const byte * block = buf; // Start of pending block
 424     const byte * const end = buf + buf_len;
 425     unsigned long long zeros = prev_sparse_len;
 426     while (1)
 427     {
 428         assert(block <= end);
 429         if (block == end)
 430             return PyLong_FromUnsignedLongLong(zeros);
 431
 432         if (*block != 0)
 433         {
 434             // Look for the end of block, i.e. the next sparse run of
 435             // at least min_sparse_len zeros, or the end of the
 436             // buffer.
 437             const byte * const probe = find_non_sparse_end(block + 1, end,
 438                                                            min_sparse_len);
 439             // Either at end of block, or end of non-sparse; write pending data
 440             PyObject *err = append_sparse_region(fd, zeros);
 441             if (err != NULL)
 442                 return err;
 443             int rc = write_all(fd, block, probe - block);
 444             if (rc)
 445                 return PyErr_SetFromErrno(PyExc_IOError);
 446
 447             if (end - probe < min_sparse_len)
 448                 zeros = end - probe;
 449             else
 450                 zeros = min_sparse_len;
 451             block = probe + zeros;
 452         }
 453         else // *block == 0
 454         {
 455             // Should be in the first loop iteration, a sparse run of
 456             // zeros, or nearly at the end of the block (within
 457             // min_sparse_len).
 458             const byte * const zeros_end = find_not_zero(block, end);
 459             PyObject *err = record_sparse_zeros(&zeros, fd,
 460                                                 zeros, zeros_end - block);
 461             if (err != NULL)
 462                 return err;
 463             assert(block <= zeros_end);
 464             block = zeros_end;
 465         }
 466     }
 467 }
 468
 469
 470 static PyObject *selftest(PyObject *self, PyObject *args)
 471 {
 472     if (!PyArg_ParseTuple(args, ""))
 473         return NULL;
 474
 475     return Py_BuildValue("i", !bupsplit_selftest());
 476 }
 477
 478
 479 static PyObject *blobbits(PyObject *self, PyObject *args)
 480 {
 481     if (!PyArg_ParseTuple(args, ""))
 482         return NULL;
 483     return Py_BuildValue("i", BUP_BLOBBITS);
 484 }
 485
 486
 487 static PyObject *splitbuf(PyObject *self, PyObject *args)
 488 {
 489     unsigned char *buf = NULL;
 490     Py_ssize_t len = 0;
 491     int out = 0, bits = -1;
 492
 493     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
 494         return NULL;
 495     assert(len <= INT_MAX);
 496     out = bupsplit_find_ofs(buf, len, &bits);
 497     if (out) assert(bits >= BUP_BLOBBITS);
 498     return Py_BuildValue("ii", out, bits);
 499 }
 500
 501
 502 static PyObject *bitmatch(PyObject *self, PyObject *args)
 503 {
 504     unsigned char *buf1 = NULL, *buf2 = NULL;
 505     Py_ssize_t len1 = 0, len2 = 0;
 506     Py_ssize_t byte;
 507     int bit;
 508
 509     if (!PyArg_ParseTuple(args, "t#t#", &buf1, &len1, &buf2, &len2))
 510         return NULL;
 511
 512     bit = 0;
 513     for (byte = 0; byte < len1 && byte < len2; byte++)
 514     {
 515         int b1 = buf1[byte], b2 = buf2[byte];
 516         if (b1 != b2)
 517         {
 518             for (bit = 0; bit < 8; bit++)
 519                 if ( (b1 & (0x80 >> bit)) != (b2 & (0x80 >> bit)) )
 520                     break;
 521             break;
 522         }
 523     }
 524
 525     assert(byte <= (INT_MAX >> 3));
 526     return Py_BuildValue("i", byte*8 + bit);
 527 }
 528
 529
 530 static PyObject *firstword(PyObject *self, PyObject *args)
 531 {
 532     unsigned char *buf = NULL;
 533     Py_ssize_t len = 0;
 534     uint32_t v;
 535
 536     if (!PyArg_ParseTuple(args, "t#", &buf, &len))
 537         return NULL;
 538
 539     if (len < 4)
 540         return NULL;
 541
 542     v = ntohl(*(uint32_t *)buf);
 543     return PyLong_FromUnsignedLong(v);
 544 }
 545
 546
 547 #define BLOOM2_HEADERLEN 16
 548
 549 static void to_bloom_address_bitmask4(const unsigned char *buf,
 550         const int nbits, uint64_t *v, unsigned char *bitmask)
 551 {
 552     int bit;
 553     uint32_t high;
 554     uint64_t raw, mask;
 555
 556     memcpy(&high, buf, 4);
 557     mask = (1<<nbits) - 1;
 558     raw = (((uint64_t)ntohl(high) << 8) | buf[4]);
 559     bit = (raw >> (37-nbits)) & 0x7;
 560     *v = (raw >> (40-nbits)) & mask;
 561     *bitmask = 1 << bit;
 562 }
 563
 564 static void to_bloom_address_bitmask5(const unsigned char *buf,
 565         const int nbits, uint32_t *v, unsigned char *bitmask)
 566 {
 567     int bit;
 568     uint32_t high;
 569     uint32_t raw, mask;
 570
 571     memcpy(&high, buf, 4);
 572     mask = (1<<nbits) - 1;
 573     raw = ntohl(high);
 574     bit = (raw >> (29-nbits)) & 0x7;
 575     *v = (raw >> (32-nbits)) & mask;
 576     *bitmask = 1 << bit;
 577 }
 578
 579 #define BLOOM_SET_BIT(name, address, otype) \
 580 static void name(unsigned char *bloom, const unsigned char *buf, const int nbits)\
 581 {\
 582     unsigned char bitmask;\
 583     otype v;\
 584     address(buf, nbits, &v, &bitmask);\
 585     bloom[BLOOM2_HEADERLEN+v] |= bitmask;\
 586 }
 587 BLOOM_SET_BIT(bloom_set_bit4, to_bloom_address_bitmask4, uint64_t)
 588 BLOOM_SET_BIT(bloom_set_bit5, to_bloom_address_bitmask5, uint32_t)
 589
 590
 591 #define BLOOM_GET_BIT(name, address, otype) \
 592 static int name(const unsigned char *bloom, const unsigned char *buf, const int nbits)\
 593 {\
 594     unsigned char bitmask;\
 595     otype v;\
 596     address(buf, nbits, &v, &bitmask);\
 597     return bloom[BLOOM2_HEADERLEN+v] & bitmask;\
 598 }
 599 BLOOM_GET_BIT(bloom_get_bit4, to_bloom_address_bitmask4, uint64_t)
 600 BLOOM_GET_BIT(bloom_get_bit5, to_bloom_address_bitmask5, uint32_t)
 601
 602
 603 static PyObject *bloom_add(PyObject *self, PyObject *args)
 604 {
 605     unsigned char *sha = NULL, *bloom = NULL;
 606     unsigned char *end;
 607     Py_ssize_t len = 0, blen = 0;
 608     int nbits = 0, k = 0;
 609
 610     if (!PyArg_ParseTuple(args, "w#s#ii", &bloom, &blen, &sha, &len, &nbits, &k))
 611         return NULL;
 612
 613     if (blen < 16+(1<<nbits) || len % 20 != 0)
 614         return NULL;
 615
 616     if (k == 5)
 617     {
 618         if (nbits > 29)
 619             return NULL;
 620         for (end = sha + len; sha < end; sha += 20/k)
 621             bloom_set_bit5(bloom, sha, nbits);
 622     }
 623     else if (k == 4)
 624     {
 625         if (nbits > 37)
 626             return NULL;
 627         for (end = sha + len; sha < end; sha += 20/k)
 628             bloom_set_bit4(bloom, sha, nbits);
 629     }
 630     else
 631         return NULL;
 632
 633
 634     return Py_BuildValue("n", len/20);
 635 }
 636
 637 static PyObject *bloom_contains(PyObject *self, PyObject *args)
 638 {
 639     unsigned char *sha = NULL, *bloom = NULL;
 640     Py_ssize_t len = 0, blen = 0;
 641     int nbits = 0, k = 0;
 642     unsigned char *end;
 643     int steps;
 644
 645     if (!PyArg_ParseTuple(args, "t#s#ii", &bloom, &blen, &sha, &len, &nbits, &k))
 646         return NULL;
 647
 648     if (len != 20)
 649         return NULL;
 650
 651     if (k == 5)
 652     {
 653         if (nbits > 29)
 654             return NULL;
 655         for (steps = 1, end = sha + 20; sha < end; sha += 20/k, steps++)
 656             if (!bloom_get_bit5(bloom, sha, nbits))
 657                 return Py_BuildValue("Oi", Py_None, steps);
 658     }
 659     else if (k == 4)
 660     {
 661         if (nbits > 37)
 662             return NULL;
 663         for (steps = 1, end = sha + 20; sha < end; sha += 20/k, steps++)
 664             if (!bloom_get_bit4(bloom, sha, nbits))
 665                 return Py_BuildValue("Oi", Py_None, steps);
 666     }
 667     else
 668         return NULL;
 669
 670     return Py_BuildValue("ii", 1, k);
 671 }
 672
 673
 674 static uint32_t _extract_bits(unsigned char *buf, int nbits)
 675 {
 676     uint32_t v, mask;
 677
 678     mask = (1<<nbits) - 1;
 679     v = ntohl(*(uint32_t *)buf);
 680     v = (v >> (32-nbits)) & mask;
 681     return v;
 682 }
 683
 684
 685 static PyObject *extract_bits(PyObject *self, PyObject *args)
 686 {
 687     unsigned char *buf = NULL;
 688     Py_ssize_t len = 0;
 689     int nbits = 0;
 690
 691     if (!PyArg_ParseTuple(args, "t#i", &buf, &len, &nbits))
 692         return NULL;
 693
 694     if (len < 4)
 695         return NULL;
 696
 697     return PyLong_FromUnsignedLong(_extract_bits(buf, nbits));
 698 }
 699
 700
 701 struct sha {
 702     unsigned char bytes[20];
 703 };
 704
 705
 706 struct idx {
 707     unsigned char *map;
 708     struct sha *cur;
 709     struct sha *end;
 710     uint32_t *cur_name;
 711     Py_ssize_t bytes;
 712     int name_base;
 713 };
 714
 715
 716 static int _cmp_sha(const struct sha *sha1, const struct sha *sha2)
 717 {
 718     int i;
 719     for (i = 0; i < sizeof(struct sha); i++)
 720         if (sha1->bytes[i] != sha2->bytes[i])
 721             return sha1->bytes[i] - sha2->bytes[i];
 722     return 0;
 723 }
 724
 725
 726 static void _fix_idx_order(struct idx **idxs, int *last_i)
 727 {
 728     struct idx *idx;
 729     int low, mid, high, c = 0;
 730
 731     idx = idxs[*last_i];
 732     if (idxs[*last_i]->cur >= idxs[*last_i]->end)
 733     {
 734         idxs[*last_i] = NULL;
 735         PyMem_Free(idx);
 736         --*last_i;
 737         return;
 738     }
 739     if (*last_i == 0)
 740         return;
 741
 742     low = *last_i-1;
 743     mid = *last_i;
 744     high = 0;
 745     while (low >= high)
 746     {
 747         mid = (low + high) / 2;
 748         c = _cmp_sha(idx->cur, idxs[mid]->cur);
 749         if (c < 0)
 750             high = mid + 1;
 751         else if (c > 0)
 752             low = mid - 1;
 753         else
 754             break;
 755     }
 756     if (c < 0)
 757         ++mid;
 758     if (mid == *last_i)
 759         return;
 760     memmove(&idxs[mid+1], &idxs[mid], (*last_i-mid)*sizeof(struct idx *));
 761     idxs[mid] = idx;
 762 }
 763
 764
 765 static uint32_t _get_idx_i(struct idx *idx)
 766 {
 767     if (idx->cur_name == NULL)
 768         return idx->name_base;
 769     return ntohl(*idx->cur_name) + idx->name_base;
 770 }
 771
 772 #define MIDX4_HEADERLEN 12
 773
 774 static PyObject *merge_into(PyObject *self, PyObject *args)
 775 {
 776     PyObject *py_total, *ilist = NULL;
 777     unsigned char *fmap = NULL;
 778     struct sha *sha_ptr, *sha_start = NULL;
 779     uint32_t *table_ptr, *name_ptr, *name_start;
 780     struct idx **idxs = NULL;
 781     Py_ssize_t flen = 0;
 782     int bits = 0, i;
 783     unsigned int total;
 784     uint32_t count, prefix;
 785     int num_i;
 786     int last_i;
 787
 788     if (!PyArg_ParseTuple(args, "w#iOO",
 789                           &fmap, &flen, &bits, &py_total, &ilist))
 790         return NULL;
 791
 792     if (!bup_uint_from_py(&total, py_total, "total"))
 793         return NULL;
 794
 795     num_i = PyList_Size(ilist);
 796     idxs = (struct idx **)PyMem_Malloc(num_i * sizeof(struct idx *));
 797
 798     for (i = 0; i < num_i; i++)
 799     {
 800         long len, sha_ofs, name_map_ofs;
 801         idxs[i] = (struct idx *)PyMem_Malloc(sizeof(struct idx));
 802         PyObject *itup = PyList_GetItem(ilist, i);
 803         if (!PyArg_ParseTuple(itup, "t#llli", &idxs[i]->map, &idxs[i]->bytes,
 804                     &len, &sha_ofs, &name_map_ofs, &idxs[i]->name_base))
 805             return NULL;
 806         idxs[i]->cur = (struct sha *)&idxs[i]->map[sha_ofs];
 807         idxs[i]->end = &idxs[i]->cur[len];
 808         if (name_map_ofs)
 809             idxs[i]->cur_name = (uint32_t *)&idxs[i]->map[name_map_ofs];
 810         else
 811             idxs[i]->cur_name = NULL;
 812     }
 813     table_ptr = (uint32_t *)&fmap[MIDX4_HEADERLEN];
 814     sha_start = sha_ptr = (struct sha *)&table_ptr[1<<bits];
 815     name_start = name_ptr = (uint32_t *)&sha_ptr[total];
 816
 817     last_i = num_i-1;
 818     count = 0;
 819     prefix = 0;
 820     while (last_i >= 0)
 821     {
 822         struct idx *idx;
 823         uint32_t new_prefix;
 824         if (count % 102424 == 0 && istty2)
 825             fprintf(stderr, "midx: writing %.2f%% (%d/%d)\r",
 826                     count*100.0/total, count, total);
 827         idx = idxs[last_i];
 828         new_prefix = _extract_bits((unsigned char *)idx->cur, bits);
 829         while (prefix < new_prefix)
 830             table_ptr[prefix++] = htonl(count);
 831         memcpy(sha_ptr++, idx->cur, sizeof(struct sha));
 832         *name_ptr++ = htonl(_get_idx_i(idx));
 833         ++idx->cur;
 834         if (idx->cur_name != NULL)
 835             ++idx->cur_name;
 836         _fix_idx_order(idxs, &last_i);
 837         ++count;
 838     }
 839     while (prefix < (1<<bits))
 840         table_ptr[prefix++] = htonl(count);
 841     assert(count == total);
 842     assert(prefix == (1<<bits));
 843     assert(sha_ptr == sha_start+count);
 844     assert(name_ptr == name_start+count);
 845
 846     PyMem_Free(idxs);
 847     return PyLong_FromUnsignedLong(count);
 848 }
 849
 850 #define FAN_ENTRIES 256
 851
 852 static PyObject *write_idx(PyObject *self, PyObject *args)
 853 {
 854     char *filename = NULL;
 855     PyObject *py_total, *idx = NULL;
 856     PyObject *part;
 857     unsigned char *fmap = NULL;
 858     Py_ssize_t flen = 0;
 859     unsigned int total = 0;
 860     uint32_t count;
 861     int i, j, ofs64_count;
 862     uint32_t *fan_ptr, *crc_ptr, *ofs_ptr;
 863     uint64_t *ofs64_ptr;
 864     struct sha *sha_ptr;
 865
 866     if (!PyArg_ParseTuple(args, "sw#OO",
 867                           &filename, &fmap, &flen, &idx, &py_total))
 868         return NULL;
 869
 870     if (!bup_uint_from_py(&total, py_total, "total"))
 871         return NULL;
 872
 873     if (PyList_Size (idx) != FAN_ENTRIES) // Check for list of the right length.
 874         return PyErr_Format (PyExc_TypeError, "idx must contain %d entries",
 875                              FAN_ENTRIES);
 876
 877     const char idx_header[] = "\377tOc\0\0\0\002";
 878     memcpy (fmap, idx_header, sizeof(idx_header) - 1);
 879
 880     fan_ptr = (uint32_t *)&fmap[sizeof(idx_header) - 1];
 881     sha_ptr = (struct sha *)&fan_ptr[FAN_ENTRIES];
 882     crc_ptr = (uint32_t *)&sha_ptr[total];
 883     ofs_ptr = (uint32_t *)&crc_ptr[total];
 884     ofs64_ptr = (uint64_t *)&ofs_ptr[total];
 885
 886     count = 0;
 887     ofs64_count = 0;
 888     for (i = 0; i < FAN_ENTRIES; ++i)
 889     {
 890         int plen;
 891         part = PyList_GET_ITEM(idx, i);
 892         PyList_Sort(part);
 893         plen = PyList_GET_SIZE(part);
 894         count += plen;
 895         *fan_ptr++ = htonl(count);
 896         for (j = 0; j < plen; ++j)
 897         {
 898             unsigned char *sha = NULL;
 899             Py_ssize_t sha_len = 0;
 900             PyObject *crc_py, *ofs_py;
 901             unsigned int crc;
 902             unsigned PY_LONG_LONG ofs_ull;
 903             uint64_t ofs;
 904             if (!PyArg_ParseTuple(PyList_GET_ITEM(part, j), "t#OO",
 905                                   &sha, &sha_len, &crc_py, &ofs_py))
 906                 return NULL;
 907             if(!bup_uint_from_py(&crc, crc_py, "crc"))
 908                 return NULL;
 909             if(!bup_ullong_from_py(&ofs_ull, ofs_py, "ofs"))
 910                 return NULL;
 911             assert(crc <= UINT32_MAX);
 912             assert(ofs_ull <= UINT64_MAX);
 913             ofs = ofs_ull;
 914             if (sha_len != sizeof(struct sha))
 915                 return NULL;
 916             memcpy(sha_ptr++, sha, sizeof(struct sha));
 917             *crc_ptr++ = htonl(crc);
 918             if (ofs > 0x7fffffff)
 919             {
 920                 *ofs64_ptr++ = htonll(ofs);
 921                 ofs = 0x80000000 | ofs64_count++;
 922             }
 923             *ofs_ptr++ = htonl((uint32_t)ofs);
 924         }
 925     }
 926
 927     int rc = msync(fmap, flen, MS_ASYNC);
 928     if (rc != 0)
 929         return PyErr_SetFromErrnoWithFilename(PyExc_IOError, filename);
 930
 931     return PyLong_FromUnsignedLong(count);
 932 }
 933
 934
 935 // I would have made this a lower-level function that just fills in a buffer
 936 // with random values, and then written those values from python.  But that's
 937 // about 20% slower in my tests, and since we typically generate random
 938 // numbers for benchmarking other parts of bup, any slowness in generating
 939 // random bytes will make our benchmarks inaccurate.  Plus nobody wants
 940 // pseudorandom bytes much except for this anyway.
 941 static PyObject *write_random(PyObject *self, PyObject *args)
 942 {
 943     uint32_t buf[1024/4];
 944     int fd = -1, seed = 0, verbose = 0;
 945     ssize_t ret;
 946     long long len = 0, kbytes = 0, written = 0;
 947
 948     if (!PyArg_ParseTuple(args, "iLii", &fd, &len, &seed, &verbose))
 949         return NULL;
 950
 951     srandom(seed);
 952
 953     for (kbytes = 0; kbytes < len/1024; kbytes++)
 954     {
 955         unsigned i;
 956         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 957             buf[i] = random();
 958         ret = write(fd, buf, sizeof(buf));
 959         if (ret < 0)
 960             ret = 0;
 961         written += ret;
 962         if (ret < (int)sizeof(buf))
 963             break;
 964         if (verbose && kbytes/1024 > 0 && !(kbytes%1024))
 965             fprintf(stderr, "Random: %lld Mbytes\r", kbytes/1024);
 966     }
 967
 968     // handle non-multiples of 1024
 969     if (len % 1024)
 970     {
 971         unsigned i;
 972         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 973             buf[i] = random();
 974         ret = write(fd, buf, len % 1024);
 975         if (ret < 0)
 976             ret = 0;
 977         written += ret;
 978     }
 979
 980     if (kbytes/1024 > 0)
 981         fprintf(stderr, "Random: %lld Mbytes, done.\n", kbytes/1024);
 982     return Py_BuildValue("L", written);
 983 }
 984
 985
 986 static PyObject *random_sha(PyObject *self, PyObject *args)
 987 {
 988     static int seeded = 0;
 989     uint32_t shabuf[20/4];
 990     int i;
 991
 992     if (!seeded)
 993     {
 994         assert(sizeof(shabuf) == 20);
 995         srandom(time(NULL));
 996         seeded = 1;
 997     }
 998
 999     if (!PyArg_ParseTuple(args, ""))
1000         return NULL;
1001
1002     memset(shabuf, 0, sizeof(shabuf));
1003     for (i=0; i < 20/4; i++)
1004         shabuf[i] = random();
1005     return Py_BuildValue("s#", shabuf, 20);
1006 }
1007
1008
1009 static int _open_noatime(const char *filename, int attrs)
1010 {
1011     int attrs_noatime, fd;
1012     attrs |= O_RDONLY;
1013 #ifdef O_NOFOLLOW
1014     attrs |= O_NOFOLLOW;
1015 #endif
1016 #ifdef O_LARGEFILE
1017     attrs |= O_LARGEFILE;
1018 #endif
1019     attrs_noatime = attrs;
1020 #ifdef O_NOATIME
1021     attrs_noatime |= O_NOATIME;
1022 #endif
1023     fd = open(filename, attrs_noatime);
1024     if (fd < 0 && errno == EPERM)
1025     {
1026         // older Linux kernels would return EPERM if you used O_NOATIME
1027         // and weren't the file's owner.  This pointless restriction was
1028         // relaxed eventually, but we have to handle it anyway.
1029         // (VERY old kernels didn't recognized O_NOATIME, but they would
1030         // just harmlessly ignore it, so this branch won't trigger)
1031         fd = open(filename, attrs);
1032     }
1033     return fd;
1034 }
1035
1036
1037 static PyObject *open_noatime(PyObject *self, PyObject *args)
1038 {
1039     char *filename = NULL;
1040     int fd;
1041     if (!PyArg_ParseTuple(args, "s", &filename))
1042         return NULL;
1043     fd = _open_noatime(filename, 0);
1044     if (fd < 0)
1045         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, filename);
1046     return Py_BuildValue("i", fd);
1047 }
1048
1049
1050 static PyObject *fadvise_done(PyObject *self, PyObject *args)
1051 {
1052     int fd = -1;
1053     long long llofs, lllen = 0;
1054     if (!PyArg_ParseTuple(args, "iLL", &fd, &llofs, &lllen))
1055         return NULL;
1056     off_t ofs, len;
1057     if (!INTEGRAL_ASSIGNMENT_FITS(&ofs, llofs))
1058         return PyErr_Format(PyExc_OverflowError,
1059                             "fadvise offset overflows off_t");
1060     if (!INTEGRAL_ASSIGNMENT_FITS(&len, lllen))
1061         return PyErr_Format(PyExc_OverflowError,
1062                             "fadvise length overflows off_t");
1063 #ifdef POSIX_FADV_DONTNEED
1064     posix_fadvise(fd, ofs, len, POSIX_FADV_DONTNEED);
1065 #endif
1066     return Py_BuildValue("");
1067 }
1068
1069
1070 // Currently the Linux kernel and FUSE disagree over the type for
1071 // FS_IOC_GETFLAGS and FS_IOC_SETFLAGS.  The kernel actually uses int,
1072 // but FUSE chose long (matching the declaration in linux/fs.h).  So
1073 // if you use int, and then traverse a FUSE filesystem, you may
1074 // corrupt the stack.  But if you use long, then you may get invalid
1075 // results on big-endian systems.
1076 //
1077 // For now, we just use long, and then disable Linux attrs entirely
1078 // (with a warning) in helpers.py on systems that are affected.
1079
1080 #ifdef BUP_HAVE_FILE_ATTRS
1081 static PyObject *bup_get_linux_file_attr(PyObject *self, PyObject *args)
1082 {
1083     int rc;
1084     unsigned long attr;
1085     char *path;
1086     int fd;
1087
1088     if (!PyArg_ParseTuple(args, "s", &path))
1089         return NULL;
1090
1091     fd = _open_noatime(path, O_NONBLOCK);
1092     if (fd == -1)
1093         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1094
1095     attr = 0;  // Handle int/long mismatch (see above)
1096     rc = ioctl(fd, FS_IOC_GETFLAGS, &attr);
1097     if (rc == -1)
1098     {
1099         close(fd);
1100         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1101     }
1102     close(fd);
1103     assert(attr <= UINT_MAX);  // Kernel type is actually int
1104     return PyLong_FromUnsignedLong(attr);
1105 }
1106 #endif /* def BUP_HAVE_FILE_ATTRS */
1107
1108
1109
1110 #ifdef BUP_HAVE_FILE_ATTRS
1111 static PyObject *bup_set_linux_file_attr(PyObject *self, PyObject *args)
1112 {
1113     int rc;
1114     unsigned long orig_attr;
1115     unsigned int attr;
1116     char *path;
1117     PyObject *py_attr;
1118     int fd;
1119
1120     if (!PyArg_ParseTuple(args, "sO", &path, &py_attr))
1121         return NULL;
1122
1123     if (!bup_uint_from_py(&attr, py_attr, "attr"))
1124         return NULL;
1125
1126     fd = open(path, O_RDONLY | O_NONBLOCK | O_LARGEFILE | O_NOFOLLOW);
1127     if (fd == -1)
1128         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1129
1130     // Restrict attr to modifiable flags acdeijstuADST -- see
1131     // chattr(1) and the e2fsprogs source.  Letter to flag mapping is
1132     // in pf.c flags_array[].
1133     attr &= FS_APPEND_FL | FS_COMPR_FL | FS_NODUMP_FL | FS_EXTENT_FL
1134     | FS_IMMUTABLE_FL | FS_JOURNAL_DATA_FL | FS_SECRM_FL | FS_NOTAIL_FL
1135     | FS_UNRM_FL | FS_NOATIME_FL | FS_DIRSYNC_FL | FS_SYNC_FL
1136     | FS_TOPDIR_FL | FS_NOCOW_FL;
1137
1138     // The extents flag can't be removed, so don't (see chattr(1) and chattr.c).
1139     orig_attr = 0; // Handle int/long mismatch (see above)
1140     rc = ioctl(fd, FS_IOC_GETFLAGS, &orig_attr);
1141     assert(orig_attr <= UINT_MAX);  // Kernel type is actually int
1142     if (rc == -1)
1143     {
1144         close(fd);
1145         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1146     }
1147     attr |= ((unsigned int) orig_attr) & FS_EXTENT_FL;
1148
1149     rc = ioctl(fd, FS_IOC_SETFLAGS, &attr);
1150     if (rc == -1)
1151     {
1152         close(fd);
1153         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1154     }
1155
1156     close(fd);
1157     return Py_BuildValue("O", Py_None);
1158 }
1159 #endif /* def BUP_HAVE_FILE_ATTRS */
1160
1161
1162 #ifndef HAVE_UTIMENSAT
1163 #ifndef HAVE_UTIMES
1164 #error "cannot find utimensat or utimes()"
1165 #endif
1166 #ifndef HAVE_LUTIMES
1167 #error "cannot find utimensat or lutimes()"
1168 #endif
1169 #endif
1170
1171 #define ASSIGN_PYLONG_TO_INTEGRAL(dest, pylong, overflow) \
1172     ({                                                     \
1173         int result = 0;                                                 \
1174         *(overflow) = 0;                                                \
1175         const long long lltmp = PyLong_AsLongLong(pylong);              \
1176         if (lltmp == -1 && PyErr_Occurred())                            \
1177         {                                                               \
1178             if (PyErr_ExceptionMatches(PyExc_OverflowError))            \
1179             {                                                           \
1180                 const unsigned long long ulltmp = PyLong_AsUnsignedLongLong(pylong); \
1181                 if (ulltmp == (unsigned long long) -1 && PyErr_Occurred()) \
1182                 {                                                       \
1183                     if (PyErr_ExceptionMatches(PyExc_OverflowError))    \
1184                     {                                                   \
1185                         PyErr_Clear();                                  \
1186                         *(overflow) = 1;                                \
1187                     }                                                   \
1188                 }                                                       \
1189                 if (INTEGRAL_ASSIGNMENT_FITS((dest), ulltmp))           \
1190                     result = 1;                                         \
1191                 else                                                    \
1192                     *(overflow) = 1;                                    \
1193             }                                                           \
1194         }                                                               \
1195         else                                                            \
1196         {                                                               \
1197             if (INTEGRAL_ASSIGNMENT_FITS((dest), lltmp))                \
1198                 result = 1;                                             \
1199             else                                                        \
1200                 *(overflow) = 1;                                        \
1201         }                                                               \
1202         result;                                                         \
1203         })
1204
1205
1206 #ifdef HAVE_UTIMENSAT
1207
1208 static PyObject *bup_utimensat(PyObject *self, PyObject *args)
1209 {
1210     int rc;
1211     int fd, flag;
1212     char *path;
1213     PyObject *access_py, *modification_py;
1214     struct timespec ts[2];
1215
1216     if (!PyArg_ParseTuple(args, "is((Ol)(Ol))i",
1217                           &fd,
1218                           &path,
1219                           &access_py, &(ts[0].tv_nsec),
1220                           &modification_py, &(ts[1].tv_nsec),
1221                           &flag))
1222         return NULL;
1223
1224     int overflow;
1225     if (!ASSIGN_PYLONG_TO_INTEGRAL(&(ts[0].tv_sec), access_py, &overflow))
1226     {
1227         if (overflow)
1228             PyErr_SetString(PyExc_ValueError,
1229                             "unable to convert access time seconds for utimensat");
1230         return NULL;
1231     }
1232     if (!ASSIGN_PYLONG_TO_INTEGRAL(&(ts[1].tv_sec), modification_py, &overflow))
1233     {
1234         if (overflow)
1235             PyErr_SetString(PyExc_ValueError,
1236                             "unable to convert modification time seconds for utimensat");
1237         return NULL;
1238     }
1239     rc = utimensat(fd, path, ts, flag);
1240     if (rc != 0)
1241         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1242
1243     return Py_BuildValue("O", Py_None);
1244 }
1245
1246 #endif /* def HAVE_UTIMENSAT */
1247
1248
1249 #if defined(HAVE_UTIMES) || defined(HAVE_LUTIMES)
1250
1251 static int bup_parse_xutimes_args(char **path,
1252                                   struct timeval tv[2],
1253                                   PyObject *args)
1254 {
1255     PyObject *access_py, *modification_py;
1256     long long access_us, modification_us; // POSIX guarantees tv_usec is signed.
1257
1258     if (!PyArg_ParseTuple(args, "s((OL)(OL))",
1259                           path,
1260                           &access_py, &access_us,
1261                           &modification_py, &modification_us))
1262         return 0;
1263
1264     int overflow;
1265     if (!ASSIGN_PYLONG_TO_INTEGRAL(&(tv[0].tv_sec), access_py, &overflow))
1266     {
1267         if (overflow)
1268             PyErr_SetString(PyExc_ValueError, "unable to convert access time seconds to timeval");
1269         return 0;
1270     }
1271     if (!INTEGRAL_ASSIGNMENT_FITS(&(tv[0].tv_usec), access_us))
1272     {
1273         PyErr_SetString(PyExc_ValueError, "unable to convert access time nanoseconds to timeval");
1274         return 0;
1275     }
1276     if (!ASSIGN_PYLONG_TO_INTEGRAL(&(tv[1].tv_sec), modification_py, &overflow))
1277     {
1278         if (overflow)
1279             PyErr_SetString(PyExc_ValueError, "unable to convert modification time seconds to timeval");
1280         return 0;
1281     }
1282     if (!INTEGRAL_ASSIGNMENT_FITS(&(tv[1].tv_usec), modification_us))
1283     {
1284         PyErr_SetString(PyExc_ValueError, "unable to convert modification time nanoseconds to timeval");
1285         return 0;
1286     }
1287     return 1;
1288 }
1289
1290 #endif /* defined(HAVE_UTIMES) || defined(HAVE_LUTIMES) */
1291
1292
1293 #ifdef HAVE_UTIMES
1294 static PyObject *bup_utimes(PyObject *self, PyObject *args)
1295 {
1296     char *path;
1297     struct timeval tv[2];
1298     if (!bup_parse_xutimes_args(&path, tv, args))
1299         return NULL;
1300     int rc = utimes(path, tv);
1301     if (rc != 0)
1302         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1303     return Py_BuildValue("O", Py_None);
1304 }
1305 #endif /* def HAVE_UTIMES */
1306
1307
1308 #ifdef HAVE_LUTIMES
1309 static PyObject *bup_lutimes(PyObject *self, PyObject *args)
1310 {
1311     char *path;
1312     struct timeval tv[2];
1313     if (!bup_parse_xutimes_args(&path, tv, args))
1314         return NULL;
1315     int rc = lutimes(path, tv);
1316     if (rc != 0)
1317         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
1318
1319     return Py_BuildValue("O", Py_None);
1320 }
1321 #endif /* def HAVE_LUTIMES */
1322
1323
1324 #ifdef HAVE_STAT_ST_ATIM
1325 # define BUP_STAT_ATIME_NS(st) (st)->st_atim.tv_nsec
1326 # define BUP_STAT_MTIME_NS(st) (st)->st_mtim.tv_nsec
1327 # define BUP_STAT_CTIME_NS(st) (st)->st_ctim.tv_nsec
1328 #elif defined HAVE_STAT_ST_ATIMENSEC
1329 # define BUP_STAT_ATIME_NS(st) (st)->st_atimespec.tv_nsec
1330 # define BUP_STAT_MTIME_NS(st) (st)->st_mtimespec.tv_nsec
1331 # define BUP_STAT_CTIME_NS(st) (st)->st_ctimespec.tv_nsec
1332 #else
1333 # define BUP_STAT_ATIME_NS(st) 0
1334 # define BUP_STAT_MTIME_NS(st) 0
1335 # define BUP_STAT_CTIME_NS(st) 0
1336 #endif
1337
1338
1339 #pragma clang diagnostic push
1340 #pragma clang diagnostic ignored "-Wtautological-compare" // For INTEGER_TO_PY().
1341
1342 static PyObject *stat_struct_to_py(const struct stat *st,
1343                                    const char *filename,
1344                                    int fd)
1345 {
1346     // We can check the known (via POSIX) signed and unsigned types at
1347     // compile time, but not (easily) the unspecified types, so handle
1348     // those via INTEGER_TO_PY().  Assumes ns values will fit in a
1349     // long.
1350     return Py_BuildValue("OKOOOOOL(Ol)(Ol)(Ol)",
1351                          INTEGER_TO_PY(st->st_mode),
1352                          (unsigned PY_LONG_LONG) st->st_ino,
1353                          INTEGER_TO_PY(st->st_dev),
1354                          INTEGER_TO_PY(st->st_nlink),
1355                          INTEGER_TO_PY(st->st_uid),
1356                          INTEGER_TO_PY(st->st_gid),
1357                          INTEGER_TO_PY(st->st_rdev),
1358                          (PY_LONG_LONG) st->st_size,
1359                          INTEGER_TO_PY(st->st_atime),
1360                          (long) BUP_STAT_ATIME_NS(st),
1361                          INTEGER_TO_PY(st->st_mtime),
1362                          (long) BUP_STAT_MTIME_NS(st),
1363                          INTEGER_TO_PY(st->st_ctime),
1364                          (long) BUP_STAT_CTIME_NS(st));
1365 }
1366
1367 #pragma clang diagnostic pop  // ignored "-Wtautological-compare"
1368
1369 static PyObject *bup_stat(PyObject *self, PyObject *args)
1370 {
1371     int rc;
1372     char *filename;
1373
1374     if (!PyArg_ParseTuple(args, "s", &filename))
1375         return NULL;
1376
1377     struct stat st;
1378     rc = stat(filename, &st);
1379     if (rc != 0)
1380         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, filename);
1381     return stat_struct_to_py(&st, filename, 0);
1382 }
1383
1384
1385 static PyObject *bup_lstat(PyObject *self, PyObject *args)
1386 {
1387     int rc;
1388     char *filename;
1389
1390     if (!PyArg_ParseTuple(args, "s", &filename))
1391         return NULL;
1392
1393     struct stat st;
1394     rc = lstat(filename, &st);
1395     if (rc != 0)
1396         return PyErr_SetFromErrnoWithFilename(PyExc_OSError, filename);
1397     return stat_struct_to_py(&st, filename, 0);
1398 }
1399
1400
1401 static PyObject *bup_fstat(PyObject *self, PyObject *args)
1402 {
1403     int rc, fd;
1404
1405     if (!PyArg_ParseTuple(args, "i", &fd))
1406         return NULL;
1407
1408     struct stat st;
1409     rc = fstat(fd, &st);
1410     if (rc != 0)
1411         return PyErr_SetFromErrno(PyExc_OSError);
1412     return stat_struct_to_py(&st, NULL, fd);
1413 }
1414
1415
1416 #ifdef HAVE_TM_TM_GMTOFF
1417 static PyObject *bup_localtime(PyObject *self, PyObject *args)
1418 {
1419     long long lltime;
1420     time_t ttime;
1421     if (!PyArg_ParseTuple(args, "L", &lltime))
1422         return NULL;
1423     if (!INTEGRAL_ASSIGNMENT_FITS(&ttime, lltime))
1424         return PyErr_Format(PyExc_OverflowError, "time value too large");
1425
1426     struct tm tm;
1427     tzset();
1428     if(localtime_r(&ttime, &tm) == NULL)
1429         return PyErr_SetFromErrno(PyExc_OSError);
1430
1431     // Match the Python struct_time values.
1432     return Py_BuildValue("[i,i,i,i,i,i,i,i,i,i,s]",
1433                          1900 + tm.tm_year, tm.tm_mon + 1, tm.tm_mday,
1434                          tm.tm_hour, tm.tm_min, tm.tm_sec,
1435                          tm.tm_wday, tm.tm_yday + 1,
1436                          tm.tm_isdst, tm.tm_gmtoff, tm.tm_zone);
1437 }
1438 #endif /* def HAVE_TM_TM_GMTOFF */
1439
1440
1441 #ifdef BUP_MINCORE_BUF_TYPE
1442 static PyObject *bup_mincore(PyObject *self, PyObject *args)
1443 {
1444     const char *src;
1445     Py_ssize_t src_ssize;
1446     Py_buffer dest;
1447     PyObject *py_src_n, *py_src_off, *py_dest_off;
1448     if (!PyArg_ParseTuple(args, "s#OOw*O",
1449                           &src, &src_ssize, &py_src_n, &py_src_off,
1450                           &dest, &py_dest_off))
1451         return NULL;
1452
1453     unsigned long long src_size, src_n, src_off, dest_size, dest_off;
1454     if (!(bup_ullong_from_py(&src_n, py_src_n, "src_n")
1455           && bup_ullong_from_py(&src_off, py_src_off, "src_off")
1456           && bup_ullong_from_py(&dest_off, py_dest_off, "dest_off")))
1457         return NULL;
1458
1459     if (!INTEGRAL_ASSIGNMENT_FITS(&src_size, src_ssize))
1460         return PyErr_Format(PyExc_OverflowError, "invalid src size");
1461     unsigned long long src_region_end;
1462
1463     if (!uadd(&src_region_end, src_off, src_n))
1464         return PyErr_Format(PyExc_OverflowError, "(src_off + src_n) too large");
1465     if (src_region_end > src_size)
1466         return PyErr_Format(PyExc_OverflowError, "region runs off end of src");
1467
1468     if (!INTEGRAL_ASSIGNMENT_FITS(&dest_size, dest.len))
1469         return PyErr_Format(PyExc_OverflowError, "invalid dest size");
1470     if (dest_off > dest_size)
1471         return PyErr_Format(PyExc_OverflowError, "region runs off end of dest");
1472
1473     size_t length;
1474     if (!INTEGRAL_ASSIGNMENT_FITS(&length, src_n))
1475         return PyErr_Format(PyExc_OverflowError, "src_n overflows size_t");
1476     int rc = mincore((void *)(src + src_off), src_n,
1477                      (BUP_MINCORE_BUF_TYPE *) (dest.buf + dest_off));
1478     if (rc != 0)
1479         return PyErr_SetFromErrno(PyExc_OSError);
1480     return Py_BuildValue("O", Py_None);
1481 }
1482 #endif /* def BUP_MINCORE_BUF_TYPE */
1483
1484
1485 static PyMethodDef helper_methods[] = {
1486     { "write_sparsely", bup_write_sparsely, METH_VARARGS,
1487       "Write buf excepting zeros at the end. Return trailing zero count." },
1488     { "selftest", selftest, METH_VARARGS,
1489         "Check that the rolling checksum rolls correctly (for unit tests)." },
1490     { "blobbits", blobbits, METH_VARARGS,
1491         "Return the number of bits in the rolling checksum." },
1492     { "splitbuf", splitbuf, METH_VARARGS,
1493         "Split a list of strings based on a rolling checksum." },
1494     { "bitmatch", bitmatch, METH_VARARGS,
1495         "Count the number of matching prefix bits between two strings." },
1496     { "firstword", firstword, METH_VARARGS,
1497         "Return an int corresponding to the first 32 bits of buf." },
1498     { "bloom_contains", bloom_contains, METH_VARARGS,
1499         "Check if a bloom filter of 2^nbits bytes contains an object" },
1500     { "bloom_add", bloom_add, METH_VARARGS,
1501         "Add an object to a bloom filter of 2^nbits bytes" },
1502     { "extract_bits", extract_bits, METH_VARARGS,
1503         "Take the first 'nbits' bits from 'buf' and return them as an int." },
1504     { "merge_into", merge_into, METH_VARARGS,
1505         "Merges a bunch of idx and midx files into a single midx." },
1506     { "write_idx", write_idx, METH_VARARGS,
1507         "Write a PackIdxV2 file from an idx list of lists of tuples" },
1508     { "write_random", write_random, METH_VARARGS,
1509         "Write random bytes to the given file descriptor" },
1510     { "random_sha", random_sha, METH_VARARGS,
1511         "Return a random 20-byte string" },
1512     { "open_noatime", open_noatime, METH_VARARGS,
1513         "open() the given filename for read with O_NOATIME if possible" },
1514     { "fadvise_done", fadvise_done, METH_VARARGS,
1515         "Inform the kernel that we're finished with earlier parts of a file" },
1516 #ifdef BUP_HAVE_FILE_ATTRS
1517     { "get_linux_file_attr", bup_get_linux_file_attr, METH_VARARGS,
1518       "Return the Linux attributes for the given file." },
1519 #endif
1520 #ifdef BUP_HAVE_FILE_ATTRS
1521     { "set_linux_file_attr", bup_set_linux_file_attr, METH_VARARGS,
1522       "Set the Linux attributes for the given file." },
1523 #endif
1524 #ifdef HAVE_UTIMENSAT
1525     { "bup_utimensat", bup_utimensat, METH_VARARGS,
1526       "Change path timestamps with nanosecond precision (POSIX)." },
1527 #endif
1528 #ifdef HAVE_UTIMES
1529     { "bup_utimes", bup_utimes, METH_VARARGS,
1530       "Change path timestamps with microsecond precision." },
1531 #endif
1532 #ifdef HAVE_LUTIMES
1533     { "bup_lutimes", bup_lutimes, METH_VARARGS,
1534       "Change path timestamps with microsecond precision;"
1535       " don't follow symlinks." },
1536 #endif
1537     { "stat", bup_stat, METH_VARARGS,
1538       "Extended version of stat." },
1539     { "lstat", bup_lstat, METH_VARARGS,
1540       "Extended version of lstat." },
1541     { "fstat", bup_fstat, METH_VARARGS,
1542       "Extended version of fstat." },
1543 #ifdef HAVE_TM_TM_GMTOFF
1544     { "localtime", bup_localtime, METH_VARARGS,
1545       "Return struct_time elements plus the timezone offset and name." },
1546 #endif
1547 #ifdef BUP_MINCORE_BUF_TYPE
1548     { "mincore", bup_mincore, METH_VARARGS,
1549       "For mincore(src, src_n, src_off, dest, dest_off)"
1550       " call the system mincore(src + src_off, src_n, &dest[dest_off])." },
1551 #endif
1552     { NULL, NULL, 0, NULL },  // sentinel
1553 };
1554
1555
1556 PyMODINIT_FUNC init_helpers(void)
1557 {
1558     // FIXME: migrate these tests to configure.  Check against the
1559     // type we're going to use when passing to python.  Other stat
1560     // types are tested at runtime.
1561     assert(sizeof(ino_t) <= sizeof(unsigned PY_LONG_LONG));
1562     assert(sizeof(off_t) <= sizeof(PY_LONG_LONG));
1563     assert(sizeof(blksize_t) <= sizeof(PY_LONG_LONG));
1564     assert(sizeof(blkcnt_t) <= sizeof(PY_LONG_LONG));
1565     // Just be sure (relevant when passing timestamps back to Python above).
1566     assert(sizeof(PY_LONG_LONG) <= sizeof(long long));
1567     assert(sizeof(unsigned PY_LONG_LONG) <= sizeof(unsigned long long));
1568
1569     // Originally required by append_sparse_region()
1570     {
1571         off_t probe;
1572         if (!INTEGRAL_ASSIGNMENT_FITS(&probe, INT_MAX))
1573         {
1574             fprintf(stderr, "off_t can't hold INT_MAX; please report.\n");
1575             exit(1);
1576         }
1577     }
1578
1579     char *e;
1580     PyObject *m = Py_InitModule("_helpers", helper_methods);
1581     if (m == NULL)
1582         return;
1583
1584 #pragma clang diagnostic push
1585 #pragma clang diagnostic ignored "-Wtautological-compare" // For INTEGER_TO_PY().
1586     {
1587         PyObject *value;
1588         value = INTEGER_TO_PY(INT_MAX);
1589         PyObject_SetAttrString(m, "INT_MAX", value);
1590         Py_DECREF(value);
1591         value = INTEGER_TO_PY(UINT_MAX);
1592         PyObject_SetAttrString(m, "UINT_MAX", value);
1593         Py_DECREF(value);
1594     }
1595 #ifdef HAVE_UTIMENSAT
1596     {
1597         PyObject *value;
1598         value = INTEGER_TO_PY(AT_FDCWD);
1599         PyObject_SetAttrString(m, "AT_FDCWD", value);
1600         Py_DECREF(value);
1601         value = INTEGER_TO_PY(AT_SYMLINK_NOFOLLOW);
1602         PyObject_SetAttrString(m, "AT_SYMLINK_NOFOLLOW", value);
1603         Py_DECREF(value);
1604         value = INTEGER_TO_PY(UTIME_NOW);
1605         PyObject_SetAttrString(m, "UTIME_NOW", value);
1606         Py_DECREF(value);
1607     }
1608 #endif
1609 #ifdef BUP_HAVE_MINCORE_INCORE
1610     {
1611         PyObject *value;
1612         value = INTEGER_TO_PY(MINCORE_INCORE);
1613         PyObject_SetAttrString(m, "MINCORE_INCORE", value);
1614         Py_DECREF(value);
1615     }
1616 #endif
1617 #pragma clang diagnostic pop  // ignored "-Wtautological-compare"
1618
1619     e = getenv("BUP_FORCE_TTY");
1620     istty2 = isatty(2) || (atoi(e ? e : "0") & 2);
1621     unpythonize_argv();
1622 }