util.c

   1 /*
   2 Copyright (c) 2003-2007 by Juliusz Chroboczek
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to deal
   6 in the Software without restriction, including without limitation the rights
   7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8 copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20 THE SOFTWARE.
  21 */
  22
  23 #include "polipo.h"
  24
  25 /* Note that this is different from GNU's strndup(3). */
  26 char *
  27 strdup_n(const char *restrict buf, int n)
  28 {
  29     char *s;
  30     s = malloc(n + 1);
  31     if(s == NULL)
  32         return NULL;
  33     memcpy(s, buf, n);
  34     s[n] = '\0';
  35     return s;
  36 }
  37
  38 int
  39 snnprintf(char *restrict buf, int n, int len, const char *format, ...)
  40 {
  41     va_list args;
  42     int rc;
  43     va_start(args, format);
  44     rc = snnvprintf(buf, n, len, format, args);
  45     va_end(args);
  46     return rc;
  47 }
  48
  49 int
  50 snnvprintf(char *restrict buf, int n, int len, const char *format, va_list args)
  51 {
  52     int rc = -1;
  53     if(n < 0) return -2;
  54     if(n < len)
  55         rc = vsnprintf(buf + n, len - n, format, args);
  56     if(rc >= 0 && n + rc <= len)
  57         return n + rc;
  58     else
  59         return -1;
  60 }
  61
  62 int
  63 snnprint_n(char *restrict buf, int n, int len, const char *s, int slen)
  64 {
  65     int i = 0;
  66     if(n < 0) return -2;
  67     while(i < slen && n < len)
  68         buf[n++] = s[i++];
  69     if(n < len)
  70         return n;
  71     else
  72         return -1;
  73 }
  74
  75 int
  76 strcmp_n(const char *string, const char *buf, int n)
  77 {
  78     int i;
  79     i = 0;
  80     while(string[i] != '\0' && i < n) {
  81         if(string[i] < buf[i])
  82             return -1;
  83         else if(string[i] > buf[i])
  84             return 1;
  85         i++;
  86     }
  87     if(string[i] == '\0' || i == n)
  88         return 0;
  89     else if(i == n)
  90         return 1;
  91     else
  92         return -1;
  93 }
  94
  95 int
  96 letter(char c)
  97 {
  98     if(c >= 'A' && c <= 'Z') return 1;
  99     if(c >= 'a' && c <= 'z') return 1;
 100     return 0;
 101 }
 102
 103 int
 104 digit(char c)
 105 {
 106     if(c >= '0' && c <= '9')
 107         return 1;
 108     return 0;
 109 }
 110
 111 char
 112 lwr(char a)
 113 {
 114     if(a >= 'A' && a <= 'Z')
 115         return a | 0x20;
 116     else
 117         return a;
 118 }
 119
 120 char *
 121 lwrcpy(char *restrict dst, const char *restrict src, int n)
 122 {
 123     int i;
 124     for(i = 0; i < n; i++)
 125         dst[i] = lwr(src[i]);
 126     return dst;
 127 }
 128
 129 int
 130 lwrcmp(const char *as, const char *bs, int n)
 131 {
 132     int i;
 133     for(i = 0; i < n; i++) {
 134         char a = lwr(as[i]), b = lwr(bs[i]);
 135         if(a < b)
 136             return -1;
 137         else if(a > b)
 138             return 1;
 139     }
 140     return 0;
 141 }
 142
 143 int
 144 strcasecmp_n(const char *string, const char *buf, int n)
 145 {
 146     int i;
 147     i = 0;
 148     while(string[i] != '\0' && i < n) {
 149         char a = lwr(string[i]), b = lwr(buf[i]);
 150         if(a < b)
 151             return -1;
 152         else if(a > b)
 153             return 1;
 154         i++;
 155     }
 156     if(string[i] == '\0' && i == n)
 157         return 0;
 158     else if(i == n)
 159         return 1;
 160     else
 161         return -1;
 162 }
 163
 164 int
 165 parseIntN(const char *restrict str, int m, int n, int min, int max,
 166           int base, int *value_return)
 167 {
 168     char buf[64];
 169     char *endp;
 170     long val;
 171     size_t len;
 172
 173     while (m < n && (str[m] == ' ' || str[m] == '\t'))
 174         m++;
 175
 176     if (m >= n)
 177         return -1;
 178
 179     /* We hope here that 63 bytes is more than enough to hold
 180        a number that won't overflow. */
 181     len = MIN(n - m, sizeof(buf) - 1);
 182     memcpy(buf, str + m, len);
 183     buf[len] = '\0';
 184
 185     errno = 0;
 186     val = strtol(buf, &endp, base);
 187     if (errno != 0 || endp == buf || val < min || val > max)
 188         return -1;
 189
 190     m += endp - buf;
 191
 192     *value_return = val;
 193     return m;
 194 }
 195
 196 int
 197 parseInt(const char *restrict str, int m, int min, int max,
 198          int base, int *value_return)
 199 {
 200     char *endp;
 201     long val;
 202
 203     errno = 0;
 204     val = strtol(str + m, &endp, base);
 205     if (errno != 0 || endp == str + m || val < min || val > max)
 206         return -1;
 207
 208     m = endp - str;
 209
 210     *value_return = val;
 211     return m;
 212 }
 213
 214 int
 215 isWhitespace(const char *string)
 216 {
 217     while(*string != '\0') {
 218         if(*string == ' ' || *string == '\t')
 219             string++;
 220         else
 221             return 0;
 222     }
 223     return 1;
 224 }
 225
 226 #ifndef HAVE_MEMRCHR
 227 void *
 228 memrchr(const void *s, int c, size_t n)
 229 {
 230     const unsigned char *p = s + n;
 231     const unsigned char *begin = s;
 232     unsigned char cc = c;
 233
 234     while (--p >= begin) {
 235         if (*p == cc)
 236             return (void*)p;
 237     }
 238
 239     return NULL;
 240 }
 241 #endif
 242
 243 int
 244 h2i(char h)
 245 {
 246     if(h >= '0' && h <= '9')
 247         return h - '0';
 248     else if(h >= 'a' && h <= 'f')
 249         return h - 'a' + 10;
 250     else if(h >= 'A' && h <= 'F')
 251         return h - 'A' + 10;
 252     else
 253         return -1;
 254 }
 255
 256 char
 257 i2h(int i)
 258 {
 259     if(i < 0 || i >= 16)
 260         return '?';
 261     if(i < 10)
 262         return i + '0';
 263     else
 264         return i - 10 + 'A';
 265 }
 266
 267 /* floor(log2(x)) */
 268 int
 269 log2_floor(int x)
 270 {
 271     int i, j;
 272
 273     assert(x > 0);
 274
 275     i = 0;
 276     j = 1;
 277     while(2 * j <= x) {
 278         i++;
 279         j *= 2;
 280     }
 281     return i;
 282 }
 283
 284 /* ceil(log2(x)) */
 285 int
 286 log2_ceil(int x)
 287 {
 288     int i, j;
 289
 290     assert(x > 0);
 291
 292     i = 0;
 293     j = 1;
 294     while(j < x) {
 295         i++;
 296         j *= 2;
 297     }
 298     return i;
 299 }
 300
 301 #ifdef HAVE_ASPRINTF
 302 char *
 303 vsprintf_a(const char *f, va_list args)
 304 {
 305     char *r;
 306     int rc;
 307
 308     rc = vasprintf(&r, f, args);
 309     if(rc < 0)
 310         return NULL;
 311     return r;
 312
 313 }
 314
 315 #else
 316
 317 /* This is not going to work if va_list is interesting.  But then, if you
 318    have a non-trivial implementation of va_list, you should have va_copy. */
 319 #ifndef va_copy
 320 #define va_copy(a, b) do { a = b; } while(0)
 321 #endif
 322
 323 char*
 324 vsprintf_a(const char *f, va_list args)
 325 {
 326     int n, size;
 327     char buf[64];
 328     char *string;
 329     va_list args_copy;
 330
 331     va_copy(args_copy, args);
 332     n = vsnprintf(buf, 64, f, args_copy);
 333     if(n >= 0 && n < 64) {
 334         return strdup_n(buf, n);
 335     }
 336     if(n >= 64)
 337         size = n + 1;
 338     else
 339         size = 96;
 340
 341     while(1) {
 342         string = malloc(size);
 343         if(!string)
 344             return NULL;
 345         va_copy(args_copy, args);
 346         n = vsnprintf(string, size, f, args_copy);
 347         if(n >= 0 && n < size)
 348             return string;
 349         else if(n >= size)
 350             size = n + 1;
 351         else
 352             size = size * 3 / 2;
 353         free(string);
 354         if(size > 16 * 1024)
 355             return NULL;
 356     }
 357     /* NOTREACHED */
 358 }
 359 #endif
 360
 361 char*
 362 sprintf_a(const char *f, ...)
 363 {
 364     char *s;
 365     va_list args;
 366     va_start(args, f);
 367     s = vsprintf_a(f, args);
 368     va_end(args);
 369     return s;
 370 }
 371
 372 unsigned int
 373 hash(unsigned int seed, const void *restrict key, int key_size,
 374      unsigned int hash_size)
 375 {
 376     int i;
 377     unsigned int h;
 378
 379     h = seed;
 380     for(i = 0; i < key_size; i++)
 381         h = (h << 5) + (h >> (hash_size - 5)) +
 382             ((unsigned char*)key)[i];
 383     return h & ((1 << hash_size) - 1);
 384 }
 385
 386 char *
 387 pstrerror(int e)
 388 {
 389     char *s;
 390     static char buf[20];
 391
 392     switch(e) {
 393     case EDOSHUTDOWN: s = "Immediate shutdown requested"; break;
 394     case EDOGRACEFUL: s = "Graceful shutdown requested"; break;
 395     case EDOTIMEOUT: s = "Timeout"; break;
 396     case ECLIENTRESET: s = "Connection reset by client"; break;
 397     case ESYNTAX: s = "Incorrect syntax"; break;
 398     case EREDIRECTOR: s = "Redirector error"; break;
 399     case EDNS_HOST_NOT_FOUND: s = "Host not found"; break;
 400     case EDNS_NO_ADDRESS: s = "No address"; break;
 401     case EDNS_NO_RECOVERY: s = "Permanent name server failure"; break;
 402     case EDNS_TRY_AGAIN: s = "Temporary name server failure"; break;
 403     case EDNS_INVALID: s = "Invalid reply from name server"; break;
 404     case EDNS_UNSUPPORTED: s = "Unsupported DNS reply"; break;
 405     case EDNS_FORMAT: s = "Invalid DNS query"; break;
 406     case EDNS_REFUSED: s = "DNS query refused by server"; break;
 407     case EDNS_CNAME_LOOP: s = "DNS CNAME loop"; break;
 408 #ifndef NO_SOCKS
 409     case ESOCKS_PROTOCOL: s = "SOCKS protocol error"; break;
 410     case ESOCKS_REJECT_FAIL: s = "SOCKS request rejected or failed"; break;
 411     case ESOCKS_REJECT_IDENTD: s = "SOCKS request rejected: "
 412                                    "server couldn't connect to identd";
 413         break;
 414     case ESOCKS_REJECT_UID_MISMATCH: s = "SOCKS request rejected: "
 415                                          "uid mismatch";
 416         break;
 417     case ESOCKS5_BASE: s = "SOCKS success"; break;
 418     case ESOCKS5_BASE + 1: s = "General SOCKS server failure"; break;
 419     case ESOCKS5_BASE + 2: s = "SOCKS connection not allowed"; break;
 420     case ESOCKS5_BASE + 3: s = "SOCKS error: network unreachable"; break;
 421     case ESOCKS5_BASE + 4: s = "SOCKS error: host unreachable"; break;
 422     case ESOCKS5_BASE + 5: s = "SOCKS error: connection refused"; break;
 423     case ESOCKS5_BASE + 6: s = "SOCKS error: TTL expired"; break;
 424     case ESOCKS5_BASE + 7: s = "SOCKS command not supported"; break;
 425     case ESOCKS5_BASE + 8: s = "SOCKS error: address type not supported";
 426         break;
 427 #endif
 428     case EUNKNOWN: s = "Unknown error"; break;
 429     default: s = NULL; break;
 430     }
 431     if(!s) s = strerror(e);
 432 #ifdef WIN32 /*MINGW*/
 433     if(!s) {
 434         if(e >= WSABASEERR && e <= WSABASEERR + 2000) {
 435             /* This should be okay, as long as the caller discards the
 436                pointer before another error occurs. */
 437             snprintf(buf, 20, "Winsock error %d", e);
 438             s = buf;
 439         }
 440     }
 441 #endif
 442     if(!s) {
 443         snprintf(buf, 20, "Unknown error %d", e);
 444         s = buf;
 445     }
 446     return s;
 447 }
 448
 449 /* Like mktime(3), but UTC rather than local time */
 450 #if defined(HAVE_TIMEGM)
 451 time_t
 452 mktime_gmt(struct tm *tm)
 453 {
 454     return timegm(tm);
 455 }
 456 #elif defined(HAVE_TM_GMTOFF)
 457 time_t
 458 mktime_gmt(struct tm *tm)
 459 {
 460     time_t t;
 461     struct tm *ltm;
 462
 463     t = mktime(tm);
 464     if(t < 0)
 465         return -1;
 466     ltm = localtime(&t);
 467     if(ltm == NULL)
 468         return -1;
 469     return t + ltm->tm_gmtoff;
 470 }
 471 #elif defined(HAVE_TZSET)
 472 #ifdef HAVE_SETENV
 473 /* Taken from the Linux timegm(3) man page. */
 474 time_t
 475 mktime_gmt(struct tm *tm)
 476 {
 477     time_t t;
 478     char *tz;
 479
 480     tz = getenv("TZ");
 481     setenv("TZ", "GMT", 1);
 482     tzset();
 483     t = mktime(tm);
 484     if(tz)
 485         setenv("TZ", tz, 1);
 486     else
 487         unsetenv("TZ");
 488     tzset();
 489     return t;
 490 }
 491 #else
 492 time_t
 493 mktime_gmt(struct tm *tm)
 494 {
 495     time_t t;
 496     char *tz;
 497     static char *old_tz = NULL;
 498
 499     tz = getenv("TZ");
 500     putenv("TZ=GMT");
 501     tzset();
 502     t = mktime(tm);
 503     if(old_tz)
 504         free(old_tz);
 505     if(tz)
 506         old_tz = sprintf_a("TZ=%s", tz);
 507     else
 508         old_tz = strdup("TZ");  /* XXX - non-portable? */
 509     if(old_tz)
 510         putenv(old_tz);
 511     tzset();
 512     return t;
 513 }
 514 #endif
 515 #else
 516 #error no mktime_gmt implementation on this platform
 517 #endif
 518
 519
 520 AtomPtr
 521 expandTilde(AtomPtr filename)
 522 {
 523     char *buf;
 524     char *home;
 525     int len;
 526     AtomPtr ret;
 527
 528     if(filename == NULL || filename->length < 1 ||
 529        filename->string[0] != '~' || filename->string[1] != '/')
 530         return filename;
 531
 532     home = getenv("HOME");
 533     if(home == NULL) {
 534         return NULL;
 535     }
 536     len = strlen(home);
 537     buf = malloc(len + 1 + 1 + filename->length - 2);
 538     if(buf == NULL) {
 539         do_log(L_ERROR, "Could not allocate buffer.\n");
 540         return NULL;
 541     }
 542
 543     memcpy(buf, home, len);
 544     if(buf[len - 1] != '/')
 545         buf[len++] = '/';
 546     memcpy(buf + len, filename->string + 2, filename->length - 2);
 547     len += filename->length - 2;
 548     ret = internAtomN(buf, len);
 549     free(buf);
 550     if(ret != NULL)
 551         releaseAtom(filename);
 552     return ret;
 553 }
 554
 555 #ifdef HAVE_FORK
 556 void
 557 do_daemonise(int noclose)
 558 {
 559     int rc;
 560
 561     fflush(stdout);
 562     fflush(stderr);
 563
 564     rc = fork();
 565     if(rc < 0) {
 566         do_log_error(L_ERROR, errno, "Couldn't fork");
 567         exit(1);
 568     }
 569
 570     if(rc > 0)
 571         exit(0);
 572
 573     if(!noclose) {
 574         int fd;
 575         close(0);
 576         close(1);
 577         close(2);
 578         /* Leaving the default file descriptors free is not a good
 579            idea, as it will cause library functions such as abort to
 580            thrash the on-disk cache. */
 581         fd = open("/dev/null", O_RDONLY);
 582         if(fd > 0) {
 583             dup2(fd, 0);
 584             close(fd);
 585         }
 586         fd = open("/dev/null", O_WRONLY);
 587         if(fd >= 0) {
 588             if(fd != 1)
 589                 dup2(fd, 1);
 590             if(fd != 2)
 591                 dup2(fd, 2);
 592             if(fd != 1 && fd != 2)
 593                 close(fd);
 594         }
 595     }
 596     rc = setsid();
 597     if(rc < 0) {
 598         do_log_error(L_ERROR, errno, "Couldn't create new session");
 599         exit(1);
 600     }
 601 }
 602
 603 #else
 604
 605 void
 606 do_daemonise(int noclose)
 607 {
 608     do_log(L_ERROR, "Cannot daemonise on this platform");
 609     exit(1);
 610 }
 611 #endif
 612
 613
 614 void
 615 writePid(char *pidfile)
 616 {
 617     int fd, n, rc;
 618     char buf[16];
 619
 620     fd = open(pidfile, O_WRONLY | O_CREAT | O_EXCL, 0666);
 621     if(fd < 0) {
 622         do_log_error(L_ERROR, errno,
 623                      "Couldn't create pid file %s", pidfile);
 624         exit(1);
 625     }
 626     n = snprintf(buf, 16, "%ld\n", (long)getpid());
 627     if(n < 0 || n >= 16) {
 628         close(fd);
 629         unlink(pidfile);
 630         do_log(L_ERROR, "Couldn't format pid.\n");
 631         exit(1);
 632     }
 633     rc = write(fd, buf, n);
 634     if(rc != n) {
 635         close(fd);
 636         unlink(pidfile);
 637         do_log_error(L_ERROR, errno, "Couldn't write pid");
 638         exit(1);
 639     }
 640
 641     close(fd);
 642     return;
 643 }
 644
 645 static const char b64[64] =
 646 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
 647
 648 /* "/" replaced with "-" */
 649 static const char b64fss[64] =
 650 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-";
 651
 652 int
 653 b64cpy(char *restrict dst, const char *restrict src, int n, int fss)
 654 {
 655     const char *b = fss ? b64fss: b64;
 656     int i, j;
 657
 658     j = 0;
 659     for(i = 0; i < n; i += 3) {
 660         unsigned char a0, a1, a2;
 661         a0 = src[i];
 662         a1 = i < n - 1 ? src[i + 1] : 0;
 663         a2 = i < n - 2 ? src[i + 2] : 0;
 664         dst[j++] = b[(a0 >> 2) & 0x3F];
 665         dst[j++] = b[((a0 << 4) & 0x30) | ((a1 >> 4) & 0x0F)];
 666         if(i < n - 1)
 667             dst[j++] = b[((a1 << 2) & 0x3C) | ((a2 >> 6) & 0x03)];
 668         else
 669             dst[j++] = '=';
 670         if(i < n - 2)
 671             dst[j++] = b[a2 & 0x3F];
 672         else
 673             dst[j++] = '=';
 674     }
 675     return j;
 676 }
 677
 678 int
 679 b64cmp(const char *restrict a, int an, const char *restrict b, int bn)
 680 {
 681     char *buf;
 682     int r;
 683
 684     if(an % 4 != 0)
 685         return -1;
 686     if((bn + 2) / 3 != an / 4)
 687         return -1;
 688     buf = malloc(an);
 689     if(buf == NULL)
 690         return -1;
 691     b64cpy(buf, b, bn, 0);
 692     r = memcmp(buf, a, an);
 693     free(buf);
 694     return r;
 695 }
 696
 697 IntListPtr
 698 makeIntList(int size)
 699 {
 700     IntListPtr list;
 701     if(size <= 0)
 702         size = 4;
 703
 704     list = malloc(sizeof(IntListRec));
 705     if(list == NULL)
 706         return NULL;
 707
 708     list->ranges = malloc(size * sizeof(IntRangeRec));
 709     if(list->ranges == NULL) {
 710         free(list);
 711         return NULL;
 712     }
 713
 714     list->length = 0;
 715     list->size = size;
 716     return list;
 717 }
 718
 719 void
 720 destroyIntList(IntListPtr list)
 721 {
 722     free(list->ranges);
 723     free(list);
 724 }
 725
 726 int
 727 intListMember(int n, IntListPtr list)
 728 {
 729     int lo = 0, hi = list->length - 1;
 730     int mid;
 731     while(hi >= lo) {
 732         mid = (hi + lo) / 2;
 733         if(list->ranges[mid].from > n)
 734             hi = mid - 1;
 735         else if(list->ranges[mid].to < n)
 736             lo = mid + 1;
 737         else
 738             return 1;
 739     }
 740     return 0;
 741 }
 742
 743 static int
 744 deleteRange(IntListPtr list, int i)
 745 {
 746     assert(list->length > i);
 747     if(list->length > i + 1)
 748         memmove(list->ranges + i, list->ranges + i + 1,
 749                 (list->length - i - 1) * sizeof(IntRangeRec));
 750     list->length--;
 751     return 1;
 752 }
 753
 754 static int
 755 insertRange(int from, int to, IntListPtr list, int i)
 756 {
 757     assert(i >= 0 && i <= list->length);
 758     assert(i == 0 || list->ranges[i - 1].to < from - 1);
 759     assert(i == list->length || list->ranges[i].from > to + 1);
 760
 761     if(list->length >= list->size) {
 762         int newsize = list->size * 2 + 1;
 763         IntRangePtr newranges =
 764             realloc(list->ranges, newsize * sizeof(IntRangeRec));
 765         if(newranges == NULL)
 766             return -1;
 767         list->size = newsize;
 768         list->ranges = newranges;
 769     }
 770
 771     if(i < list->length)
 772         memmove(list->ranges + i + 1, list->ranges + i,
 773                 list->length - i);
 774     list->length++;
 775     list->ranges[i].from = from;
 776     list->ranges[i].to = to;
 777     return 1;
 778 }
 779
 780 static int
 781 maybeMergeRanges(IntListPtr list, int i)
 782 {
 783     int rc;
 784
 785     while(i > 0 && list->ranges[i].from <= list->ranges[i - 1].to + 1) {
 786             list->ranges[i - 1].from =
 787                 MIN(list->ranges[i - 1].from, list->ranges[i].from);
 788             list->ranges[i - 1].to =
 789                 MAX(list->ranges[i - 1].to, list->ranges[i].to);
 790             rc = deleteRange(list, i);
 791             if(rc < 0) return -1;
 792             i--;
 793     }
 794
 795     while(i < list->length - 1 &&
 796           list->ranges[i].to >= list->ranges[i + 1].from - 1) {
 797             list->ranges[i + 1].from =
 798                 MIN(list->ranges[i + 1].from, list->ranges[i].from);
 799             list->ranges[i - 1].to =
 800                 MAX(list->ranges[i + 1].to, list->ranges[i].to);
 801             rc = deleteRange(list, i);
 802             if(rc < 0) return -1;
 803     }
 804     return 1;
 805 }
 806
 807 int
 808 intListCons(int from, int to, IntListPtr list)
 809 {
 810     int i;
 811
 812     /* Don't bother with the dichotomy. */
 813     for(i = 0; i < list->length; i++) {
 814         if(list->ranges[i].to >= from - 1)
 815             break;
 816     }
 817
 818     if(i < list->length &&
 819        (from >= list->ranges[i].from - 1 || to <= list->ranges[i].to + 1)) {
 820         if(from <= list->ranges[i].from)
 821             list->ranges[i].from = from;
 822         if(to >= list->ranges[i].to)
 823             list->ranges[i].to = to;
 824         return maybeMergeRanges(list, i);
 825     }
 826     return insertRange(from, to, list, i);
 827 }
 828
 829 /* Return the amount of physical memory on the box, -1 if unknown or
 830    over two gigs. */
 831 #if defined(__linux__)
 832
 833 #include <sys/sysinfo.h>
 834 int
 835 physicalMemory()
 836 {
 837     int rc;
 838     struct sysinfo info;
 839
 840     rc = sysinfo(&info);
 841     if(rc < 0)
 842         return -1;
 843
 844     if(info.totalram <= 0x7fffffff / info.mem_unit)
 845         return (int)(info.totalram * info.mem_unit);
 846
 847     return -1;
 848 }
 849
 850 #elif defined(__FreeBSD__)
 851
 852 #include <sys/sysctl.h>
 853 int
 854 physicalMemory()
 855 {
 856     unsigned long membytes;
 857     size_t len;
 858     int res;
 859
 860     len = sizeof(membytes);
 861     res = sysctlbyname("hw.physmem", &membytes, &len, NULL, 0);
 862     if (res || membytes > INT_MAX)
 863         return -1;
 864
 865     return (int)membytes;
 866 }
 867
 868 #else
 869
 870 int
 871 physicalMemory()
 872 {
 873     return -1;
 874 }
 875 #endif