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 atoi_n(const char *restrict string, int n, int len, int *value_return)
 166 {
 167     int i = n;
 168     int val = 0;
 169
 170     if(i >= len || !digit(string[i]))
 171         return -1;
 172
 173     while(i < len && digit(string[i])) {
 174         val = val * 10 + (string[i] - '0');
 175         i++;
 176     }
 177     *value_return = val;
 178     return i;
 179 }
 180
 181 int
 182 isWhitespace(const char *string)
 183 {
 184     while(*string != '\0') {
 185         if(*string == ' ' || *string == '\t')
 186             string++;
 187         else
 188             return 0;
 189     }
 190     return 1;
 191 }
 192
 193 #ifndef HAVE_MEMRCHR
 194 void *
 195 memrchr(const void *s, int c, size_t n)
 196 {
 197     const unsigned char *ss = s;
 198     unsigned char cc = c;
 199     size_t i;
 200     for(i = n - 1; i >= 0; i--)
 201         if(ss[i] == cc)
 202             return (void*)(ss + i);
 203     return NULL;
 204 }
 205 #endif
 206
 207 int
 208 h2i(char h)
 209 {
 210     if(h >= '0' && h <= '9')
 211         return h - '0';
 212     else if(h >= 'a' && h <= 'f')
 213         return h - 'a' + 10;
 214     else if(h >= 'A' && h <= 'F')
 215         return h - 'A' + 10;
 216     else
 217         return -1;
 218 }
 219
 220 char
 221 i2h(int i)
 222 {
 223     if(i < 0 || i >= 16)
 224         return '?';
 225     if(i < 10)
 226         return i + '0';
 227     else
 228         return i - 10 + 'A';
 229 }
 230
 231 /* floor(log2(x)) */
 232 int
 233 log2_floor(int x)
 234 {
 235     int i, j;
 236
 237     assert(x > 0);
 238
 239     i = 0;
 240     j = 1;
 241     while(2 * j <= x) {
 242         i++;
 243         j *= 2;
 244     }
 245     return i;
 246 }
 247
 248 /* ceil(log2(x)) */
 249 int
 250 log2_ceil(int x)
 251 {
 252     int i, j;
 253
 254     assert(x > 0);
 255
 256     i = 0;
 257     j = 1;
 258     while(j < x) {
 259         i++;
 260         j *= 2;
 261     }
 262     return i;
 263 }
 264
 265 #ifdef HAVE_ASPRINTF
 266 char *
 267 vsprintf_a(const char *f, va_list args)
 268 {
 269     char *r;
 270     int rc;
 271     rc = vasprintf(&r, f, args);
 272     if(rc < 0)
 273         return NULL;
 274     return r;
 275
 276 }
 277 #else
 278 char*
 279 vsprintf_a(const char *f, va_list args)
 280 {
 281     int n, size;
 282     char buf[64];
 283     char *string;
 284
 285     n = vsnprintf(buf, 64, f, args);
 286     if(n >= 0 && n < 64) {
 287         return strdup_n(buf, n);
 288     }
 289     if(n >= 64)
 290         size = n + 1;
 291     else
 292         size = 96;
 293
 294     while(1) {
 295         string = malloc(size);
 296         if(!string)
 297             return NULL;
 298         n = vsnprintf(string, size, f, args);
 299         if(n >= 0 && n < size)
 300             return string;
 301         else if(n >= size)
 302             size = n + 1;
 303         else
 304             size = size * 3 / 2;
 305         free(string);
 306         if(size > 16 * 1024)
 307             return NULL;
 308     }
 309     /* NOTREACHED */
 310 }
 311 #endif
 312
 313 char*
 314 sprintf_a(const char *f, ...)
 315 {
 316     char *s;
 317     va_list args;
 318     va_start(args, f);
 319     s = vsprintf_a(f, args);
 320     va_end(args);
 321     return s;
 322 }
 323
 324 unsigned int
 325 hash(unsigned int seed, const void *restrict key, int key_size,
 326      unsigned int hash_size)
 327 {
 328     int i;
 329     unsigned int h;
 330
 331     h = seed;
 332     for(i = 0; i < key_size; i++)
 333         h = (h << 5) + (h >> (hash_size - 5)) +
 334             ((unsigned char*)key)[i];
 335     return h & ((1 << hash_size) - 1);
 336 }
 337
 338 char *
 339 pstrerror(int e)
 340 {
 341     char *s;
 342     static char buf[20];
 343
 344     switch(e) {
 345     case EDOSHUTDOWN: s = "Immediate shutdown requested"; break;
 346     case EDOGRACEFUL: s = "Graceful shutdown requested"; break;
 347     case EDOTIMEOUT: s = "Timeout"; break;
 348     case ECLIENTRESET: s = "Connection reset by client"; break;
 349     case ESYNTAX: s = "Incorrect syntax"; break;
 350     case EREDIRECTOR: s = "Redirector error"; break;
 351     case EDNS_HOST_NOT_FOUND: s = "Host not found"; break;
 352     case EDNS_NO_ADDRESS: s = "No address"; break;
 353     case EDNS_NO_RECOVERY: s = "Permanent name server failure"; break;
 354     case EDNS_TRY_AGAIN: s = "Temporary name server failure"; break;
 355     case EDNS_INVALID: s = "Invalid reply from name server"; break;
 356     case EDNS_UNSUPPORTED: s = "Unsupported DNS reply"; break;
 357     case EDNS_FORMAT: s = "Invalid DNS query"; break;
 358     case EDNS_REFUSED: s = "DNS query refused by server"; break;
 359     case EDNS_CNAME_LOOP: s = "DNS CNAME loop"; break;
 360 #ifndef NO_SOCKS
 361     case ESOCKS_PROTOCOL: s = "SOCKS protocol error"; break;
 362     case ESOCKS_REJECT_FAIL: s = "SOCKS request rejected or failed"; break;
 363     case ESOCKS_REJECT_IDENTD: s = "SOCKS request rejected: "
 364                                    "server couldn't connect to identd";
 365     case ESOCKS_REJECT_UID_MISMATCH: s = "SOCKS request rejected: "
 366                                          "uid mismatch";
 367         break;
 368     case ESOCKS5_BASE: s = "SOCKS success"; break;
 369     case ESOCKS5_BASE + 1: s = "General SOCKS server failure"; break;
 370     case ESOCKS5_BASE + 2: s = "SOCKS connection not allowed"; break;
 371     case ESOCKS5_BASE + 3: s = "SOCKS error: network unreachable"; break;
 372     case ESOCKS5_BASE + 4: s = "SOCKS error: host unreachable"; break;
 373     case ESOCKS5_BASE + 5: s = "SOCKS error: connection refused"; break;
 374     case ESOCKS5_BASE + 6: s = "SOCKS error: TTL expired"; break;
 375     case ESOCKS5_BASE + 7: s = "SOCKS command not supported"; break;
 376     case ESOCKS5_BASE + 8: s = "SOCKS error: address type not supported";
 377         break;
 378 #endif
 379     case EUNKNOWN: s = "Unknown error"; break;
 380     default: s = NULL; break;
 381     }
 382     if(!s) s = strerror(e);
 383 #ifdef MINGW
 384     if(!s) {
 385         if(e >= WSABASEERR && e <= WSABASEERR + 2000) {
 386             /* This should be okay, as long as the caller discards the
 387                pointer before another error occurs. */
 388             snprintf(buf, 20, "Winsock error %d", e);
 389             s = buf;
 390         }
 391     }
 392 #endif
 393     if(!s) {
 394         snprintf(buf, 20, "Unknown error %d", e);
 395         s = buf;
 396     }
 397     return s;
 398 }
 399
 400 /* Like mktime(3), but UTC rather than local time */
 401 #if defined(HAVE_TIMEGM)
 402 time_t
 403 mktime_gmt(struct tm *tm)
 404 {
 405     return timegm(tm);
 406 }
 407 #elif defined(HAVE_TM_GMTOFF)
 408 time_t
 409 mktime_gmt(struct tm *tm)
 410 {
 411     time_t t;
 412     struct tm *ltm;
 413
 414     t = mktime(tm);
 415     if(t < 0)
 416         return -1;
 417     ltm = localtime(&t);
 418     if(ltm == NULL)
 419         return -1;
 420     return t + ltm->tm_gmtoff;
 421 }
 422 #elif defined(HAVE_TZSET)
 423 #ifdef HAVE_SETENV
 424 /* Taken from the Linux timegm(3) man page. */
 425 time_t
 426 mktime_gmt(struct tm *tm)
 427 {
 428     time_t t;
 429     char *tz;
 430
 431     tz = getenv("TZ");
 432     setenv("TZ", "", 1);
 433     tzset();
 434     t = mktime(tm);
 435     if(tz)
 436         setenv("TZ", tz, 1);
 437     else
 438         unsetenv("TZ");
 439     tzset();
 440     return t;
 441 }
 442 #else
 443 time_t
 444 mktime_gmt(struct tm *tm)
 445 {
 446     time_t t;
 447     char *tz;
 448     static char *old_tz = NULL;
 449
 450     tz = getenv("TZ");
 451     putenv("TZ=");
 452     tzset();
 453     t = mktime(tm);
 454     if(old_tz)
 455         free(old_tz);
 456     if(tz)
 457         old_tz = sprintf_a("TZ=%s", tz);
 458     else
 459         old_tz = strdup("TZ");  /* XXX - non-portable? */
 460     if(old_tz)
 461         putenv(old_tz);
 462     tzset();
 463     return t;
 464 }
 465 #endif
 466 #else
 467 #error no mktime_gmt implementation on this platform
 468 #endif
 469
 470
 471 AtomPtr
 472 expandTilde(AtomPtr filename)
 473 {
 474     char *buf;
 475     char *home;
 476     int len;
 477     AtomPtr ret;
 478
 479     if(filename == NULL || filename->length < 1 ||
 480        filename->string[0] != '~' || filename->string[1] != '/')
 481         return filename;
 482
 483     home = getenv("HOME");
 484     if(home == NULL) {
 485         return NULL;
 486     }
 487     len = strlen(home);
 488     buf = malloc(len + 1 + 1 + filename->length - 2);
 489     if(buf == NULL) {
 490         do_log(L_ERROR, "Could not allocate buffer.\n");
 491         return NULL;
 492     }
 493
 494     memcpy(buf, home, len);
 495     if(buf[len - 1] != '/')
 496         buf[len++] = '/';
 497     memcpy(buf + len, filename->string + 2, filename->length - 2);
 498     len += filename->length - 2;
 499     ret = internAtomN(buf, len);
 500     free(buf);
 501     if(ret != NULL)
 502         releaseAtom(filename);
 503     return ret;
 504 }
 505
 506 #ifdef HAVE_FORK
 507 void
 508 do_daemonise(int noclose)
 509 {
 510     int rc;
 511
 512     fflush(stdout);
 513     fflush(stderr);
 514
 515     rc = fork();
 516     if(rc < 0) {
 517         do_log_error(L_ERROR, errno, "Couldn't fork");
 518         exit(1);
 519     }
 520
 521     if(rc > 0)
 522         exit(0);
 523
 524     if(!noclose) {
 525         close(0);
 526         close(1);
 527         close(2);
 528     }
 529     rc = setsid();
 530     if(rc < 0) {
 531         do_log_error(L_ERROR, errno, "Couldn't create new session");
 532         exit(1);
 533     }
 534 }
 535
 536 #else
 537
 538 void
 539 do_daemonise(int noclose)
 540 {
 541     do_log(L_ERROR, "Cannot daemonise on this platform");
 542     exit(1);
 543 }
 544 #endif
 545
 546
 547 void
 548 writePid(char *pidfile)
 549 {
 550     int fd, n, rc;
 551     char buf[16];
 552
 553     fd = open(pidfile, O_WRONLY | O_CREAT | O_EXCL, 0666);
 554     if(fd < 0) {
 555         do_log_error(L_ERROR, errno,
 556                      "Couldn't create pid file %s", pidfile);
 557         exit(1);
 558     }
 559     n = snprintf(buf, 16, "%ld\n", (long)getpid());
 560     if(n < 0 || n >= 16) {
 561         close(fd);
 562         unlink(pidfile);
 563         do_log(L_ERROR, "Couldn't format pid.\n");
 564         exit(1);
 565     }
 566     rc = write(fd, buf, n);
 567     if(rc != n) {
 568         close(fd);
 569         unlink(pidfile);
 570         do_log_error(L_ERROR, errno, "Couldn't write pid");
 571         exit(1);
 572     }
 573
 574     close(fd);
 575     return;
 576 }
 577
 578 static const char b64[64] =
 579 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
 580
 581 /* "/" replaced with "-" */
 582 static const char b64fss[64] =
 583 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-";
 584
 585 int
 586 b64cpy(char *restrict dst, const char *restrict src, int n, int fss)
 587 {
 588     const char *b = fss ? b64fss: b64;
 589     int i, j;
 590
 591     j = 0;
 592     for(i = 0; i < n; i += 3) {
 593         unsigned char a0, a1, a2;
 594         a0 = src[i];
 595         a1 = i < n - 1 ? src[i + 1] : 0;
 596         a2 = i < n - 2 ? src[i + 2] : 0;
 597         dst[j++] = b[(a0 >> 2) & 0x3F];
 598         dst[j++] = b[((a0 << 4) & 0x30) | ((a1 >> 4) & 0x0F)];
 599         if(i < n - 1)
 600             dst[j++] = b[((a1 << 2) & 0x3C) | ((a2 >> 6) & 0x03)];
 601         else
 602             dst[j++] = '=';
 603         if(i < n - 2)
 604             dst[j++] = b[a2 & 0x3F];
 605         else
 606             dst[j++] = '=';
 607     }
 608     return j;
 609 }
 610
 611 int
 612 b64cmp(const char *restrict a, int an, const char *restrict b, int bn)
 613 {
 614     char *buf;
 615     int r;
 616
 617     if(an % 4 != 0)
 618         return -1;
 619     if((bn + 2) / 3 != an / 4)
 620         return -1;
 621     buf = malloc(an);
 622     if(buf == NULL)
 623         return -1;
 624     b64cpy(buf, b, bn, 0);
 625     r = memcmp(buf, a, an);
 626     free(buf);
 627     return r;
 628 }
 629
 630 IntListPtr
 631 makeIntList(int size)
 632 {
 633     IntListPtr list;
 634     if(size <= 0)
 635         size = 4;
 636
 637     list = malloc(sizeof(IntListRec));
 638     if(list == NULL)
 639         return NULL;
 640
 641     list->ranges = malloc(size * sizeof(IntRangeRec));
 642     if(list->ranges == NULL) {
 643         free(list);
 644         return NULL;
 645     }
 646
 647     list->length = 0;
 648     list->size = size;
 649     return list;
 650 }
 651
 652 void
 653 destroyIntList(IntListPtr list)
 654 {
 655     free(list->ranges);
 656     free(list);
 657 }
 658
 659 int
 660 intListMember(int n, IntListPtr list)
 661 {
 662     int lo = 0, hi = list->length - 1;
 663     int mid;
 664     while(hi >= lo) {
 665         mid = (hi + lo) / 2;
 666         if(list->ranges[mid].from > n)
 667             hi = mid - 1;
 668         else if(list->ranges[mid].to < n)
 669             lo = mid + 1;
 670         else
 671             return 1;
 672     }
 673     return 0;
 674 }
 675
 676 static int
 677 deleteRange(IntListPtr list, int i)
 678 {
 679     assert(list->length > i);
 680     if(list->length > i + 1)
 681         memmove(list->ranges + i, list->ranges + i + 1,
 682                 (list->length - i - 1) * sizeof(IntRangeRec));
 683     list->length--;
 684     return 1;
 685 }
 686
 687 static int
 688 insertRange(int from, int to, IntListPtr list, int i)
 689 {
 690     assert(i >= 0 && i <= list->length);
 691     assert(i == 0 || list->ranges[i - 1].to < from - 1);
 692     assert(i == list->length || list->ranges[i].from > to + 1);
 693
 694     if(list->length >= list->size) {
 695         int newsize = list->size * 2 + 1;
 696         IntRangePtr newranges =
 697             realloc(list->ranges, newsize * sizeof(IntRangeRec));
 698         if(newranges == NULL)
 699             return -1;
 700         list->size = newsize;
 701         list->ranges = newranges;
 702     }
 703
 704     if(i < list->length)
 705         memmove(list->ranges + i + 1, list->ranges + i,
 706                 list->length - i);
 707     list->length++;
 708     list->ranges[i].from = from;
 709     list->ranges[i].to = to;
 710     return 1;
 711 }
 712
 713 static int
 714 maybeMergeRanges(IntListPtr list, int i)
 715 {
 716     int rc;
 717
 718     while(i > 0 && list->ranges[i].from <= list->ranges[i - 1].to + 1) {
 719             list->ranges[i - 1].from =
 720                 MIN(list->ranges[i - 1].from, list->ranges[i].from);
 721             list->ranges[i - 1].to =
 722                 MAX(list->ranges[i - 1].to, list->ranges[i].to);
 723             rc = deleteRange(list, i);
 724             if(rc < 0) return -1;
 725             i--;
 726     }
 727
 728     while(i < list->length - 1 &&
 729           list->ranges[i].to >= list->ranges[i + 1].from - 1) {
 730             list->ranges[i + 1].from =
 731                 MIN(list->ranges[i + 1].from, list->ranges[i].from);
 732             list->ranges[i - 1].to =
 733                 MAX(list->ranges[i + 1].to, list->ranges[i].to);
 734             rc = deleteRange(list, i);
 735             if(rc < 0) return -1;
 736     }
 737     return 1;
 738 }
 739
 740 int
 741 intListCons(int from, int to, IntListPtr list)
 742 {
 743     int i;
 744
 745     /* Don't bother with the dichotomy. */
 746     for(i = 0; i < list->length; i++) {
 747         if(list->ranges[i].to >= from - 1)
 748             break;
 749     }
 750
 751     if(i < list->length &&
 752        (from >= list->ranges[i].from - 1 || to <= list->ranges[i].to + 1)) {
 753         if(from <= list->ranges[i].from)
 754             list->ranges[i].from = from;
 755         if(to >= list->ranges[i].to)
 756             list->ranges[i].to = to;
 757         return maybeMergeRanges(list, i);
 758     }
 759     return insertRange(from, to, list, i);
 760 }
 761
 762 /* Return the amount of physical memory on the box, -1 if unknown or
 763    over two gigs. */
 764 #if defined(__linux__)
 765
 766 #include <sys/sysinfo.h>
 767 int
 768 physicalMemory()
 769 {
 770     int rc;
 771     struct sysinfo info;
 772
 773     rc = sysinfo(&info);
 774     if(rc < 0)
 775         return -1;
 776
 777     if(info.totalram <= 0x7fffffff / info.mem_unit)
 778         return (int)(info.totalram * info.mem_unit);
 779
 780     return -1;
 781 }
 782
 783 #elif defined(__FreeBSD__)
 784
 785 #include <sys/sysctl.h>
 786 int
 787 physicalMemory()
 788 {
 789     int membytes;
 790     size_t len;
 791     int res;
 792
 793     len = sizeof(membytes);
 794     res = sysctlbyname("hw.physmem", &membytes, &len, NULL, 0);
 795     if (res)
 796         return -1;
 797
 798     return membytes;
 799 }
 800
 801 #else
 802
 803 int
 804 physicalMemory()
 805 {
 806     return -1;
 807 }
 808 #endif