util.c

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