src/lib/misc.c

   1 /*
   2  * misc.c       Various miscellaneous functions.
   3  *
   4  * Version:     $Id$
   5  *
   6  *   This library is free software; you can redistribute it and/or
   7  *   modify it under the terms of the GNU Lesser General Public
   8  *   License as published by the Free Software Foundation; either
   9  *   version 2.1 of the License, or (at your option) any later version.
  10  *
  11  *   This library is distributed in the hope that it will be useful,
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  *   Lesser General Public License for more details.
  15  *
  16  *   You should have received a copy of the GNU Lesser General Public
  17  *   License along with this library; if not, write to the Free Software
  18  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  *
  20  * Copyright 2000,2006  The FreeRADIUS server project
  21  */
  22
  23 RCSID("$Id$")
  24
  25 #include        <freeradius-devel/libradius.h>
  26
  27 #include        <ctype.h>
  28 #include        <sys/file.h>
  29 #include        <fcntl.h>
  30
  31 #define FR_PUT_LE16(a, val)\
  32         do {\
  33                 a[1] = ((uint16_t) (val)) >> 8;\
  34                 a[0] = ((uint16_t) (val)) & 0xff;\
  35         } while (0)
  36
  37 #ifdef HAVE_PTHREAD_H
  38 static pthread_mutex_t autofree_context = PTHREAD_MUTEX_INITIALIZER;
  39 #  define PTHREAD_MUTEX_LOCK pthread_mutex_lock
  40 #  define PTHREAD_MUTEX_UNLOCK pthread_mutex_unlock
  41 #else
  42 #  define PTHREAD_MUTEX_LOCK(_x)
  43 #  define PTHREAD_MUTEX_UNLOCK(_x)
  44 #endif
  45
  46 bool    fr_dns_lookups = false;     /* IP -> hostname lookups? */
  47 bool    fr_hostname_lookups = true; /* hostname -> IP lookups? */
  48 int     fr_debug_flag = 0;
  49
  50 static char const *months[] = {
  51         "jan", "feb", "mar", "apr", "may", "jun",
  52         "jul", "aug", "sep", "oct", "nov", "dec" };
  53
  54 fr_thread_local_setup(char *, fr_inet_ntop_buffer);     /* macro */
  55
  56 /** Sets a signal handler using sigaction if available, else signal
  57  *
  58  * @param sig to set handler for.
  59  * @param func handler to set.
  60  */
  61 int fr_set_signal(int sig, sig_t func)
  62 {
  63 #ifdef HAVE_SIGACTION
  64         struct sigaction act;
  65
  66         memset(&act, 0, sizeof(act));
  67         act.sa_flags = 0;
  68         sigemptyset(&act.sa_mask);
  69         act.sa_handler = func;
  70
  71         if (sigaction(sig, &act, NULL) < 0) {
  72                 fr_strerror_printf("Failed setting signal %i handler via sigaction(): %s", sig, fr_syserror(errno));
  73                 return -1;
  74         }
  75 #else
  76         if (signal(sig, func) < 0) {
  77                 fr_strerror_printf("Failed setting signal %i handler via signal(): %s", sig, fr_syserror(errno));
  78                 return -1;
  79         }
  80 #endif
  81         return 0;
  82 }
  83
  84 /** Allocates a new talloc context from the root autofree context
  85  *
  86  * This function is threadsafe, whereas using the NULL context is not.
  87  *
  88  * @note The returned context must be freed by the caller.
  89  * @returns a new talloc context parented by the root autofree context.
  90  */
  91 TALLOC_CTX *fr_autofree_ctx(void)
  92 {
  93         static TALLOC_CTX *ctx = NULL, *child;
  94         PTHREAD_MUTEX_LOCK(&autofree_context);
  95         if (!ctx) {
  96                 ctx = talloc_autofree_context();
  97         }
  98
  99         child = talloc_new(ctx);
 100         PTHREAD_MUTEX_UNLOCK(&autofree_context);
 101
 102         return child;
 103 }
 104
 105 /*
 106  *      Explicitly cleanup the memory allocated to the error inet_ntop
 107  *      buffer.
 108  */
 109 static void _fr_inet_ntop_free(void *arg)
 110 {
 111         free(arg);
 112 }
 113
 114 /** Wrapper around inet_ntop, prints IPv4/IPv6 addresses
 115  *
 116  * inet_ntop requires the caller pass in a buffer for the address.
 117  * This would be annoying and cumbersome, seeing as quite often the ASCII
 118  * address is only used for logging output.
 119  *
 120  * So as with lib/log.c use TLS to allocate thread specific buffers, and
 121  * write the IP address there instead.
 122  *
 123  * @param af address family, either AF_INET or AF_INET6.
 124  * @param src pointer to network address structure.
 125  * @return NULL on error, else pointer to ASCII buffer containing text version of address.
 126  */
 127 char const *fr_inet_ntop(int af, void const *src)
 128 {
 129         char *buffer;
 130
 131         if (!src) {
 132                 return NULL;
 133         }
 134
 135         buffer = fr_thread_local_init(fr_inet_ntop_buffer, _fr_inet_ntop_free);
 136         if (!buffer) {
 137                 int ret;
 138
 139                 /*
 140                  *      malloc is thread safe, talloc is not
 141                  */
 142                 buffer = malloc(sizeof(char) * INET6_ADDRSTRLEN);
 143                 if (!buffer) {
 144                         fr_perror("Failed allocating memory for inet_ntop buffer");
 145                         return NULL;
 146                 }
 147
 148                 ret = fr_thread_local_set(fr_inet_ntop_buffer, buffer);
 149                 if (ret != 0) {
 150                         fr_perror("Failed setting up TLS for inet_ntop buffer: %s", fr_syserror(ret));
 151                         free(buffer);
 152                         return NULL;
 153                 }
 154         }
 155         buffer[0] = '\0';
 156
 157         return inet_ntop(af, src, buffer, INET6_ADDRSTRLEN);
 158 }
 159
 160 /*
 161  *      Return an IP address in standard dot notation
 162  *
 163  *      FIXME: DELETE THIS
 164  */
 165 char const *ip_ntoa(char *buffer, uint32_t ipaddr)
 166 {
 167         ipaddr = ntohl(ipaddr);
 168
 169         sprintf(buffer, "%d.%d.%d.%d",
 170                 (ipaddr >> 24) & 0xff,
 171                 (ipaddr >> 16) & 0xff,
 172                 (ipaddr >>  8) & 0xff,
 173                 (ipaddr      ) & 0xff);
 174         return buffer;
 175 }
 176
 177 /** Parse an IPv4 address or IPv4 prefix in presentation format (and others)
 178  *
 179  * @param out Where to write the ip address value.
 180  * @param value to parse, may be dotted quad [+ prefix], or integer, or octal number, or '*' (INADDR_ANY).
 181  * @param inlen Length of value, if value is \0 terminated inlen may be 0.
 182  * @param resolve If true and value doesn't look like an IP address, try and resolve value as a hostname.
 183  * @param fallback to IPv4 resolution if no A records can be found.
 184  * @return 0 if ip address was parsed successfully, else -1 on error.
 185  */
 186 int fr_pton4(fr_ipaddr_t *out, char const *value, size_t inlen, bool resolve, bool fallback)
 187 {
 188         char *p;
 189         unsigned int prefix;
 190         char *eptr;
 191
 192         /* Dotted quad + / + [0-9]{1,2} */
 193         char buffer[INET_ADDRSTRLEN + 3];
 194
 195         /*
 196          *      Copy to intermediary buffer if we were given a length
 197          */
 198         if (inlen > 0) {
 199                 if (inlen >= sizeof(buffer)) {
 200                         fr_strerror_printf("Invalid IPv4 address string \"%s\"", value);
 201                         return -1;
 202                 }
 203                 memcpy(buffer, value, inlen);
 204                 buffer[inlen] = '\0';
 205         }
 206
 207         p = strchr(value, '/');
 208         /*
 209          *      192.0.2.2 is parsed as if it was /32
 210          */
 211         if (!p) {
 212                 /*
 213                  *      Allow '*' as the wildcard address usually 0.0.0.0
 214                  */
 215                 if ((value[0] == '*') && (value[1] == '\0')) {
 216                         out->ipaddr.ip4addr.s_addr = htonl(INADDR_ANY);
 217                 /*
 218                  *      Convert things which are obviously integers to IP addresses
 219                  *
 220                  *      We assume the number is the bigendian representation of the
 221                  *      IP address.
 222                  */
 223                 } else if (is_integer(value)) {
 224                         out->ipaddr.ip4addr.s_addr = htonl(strtoul(value, NULL, 0));
 225                 } else if (!resolve) {
 226                         if (inet_pton(AF_INET, value, &(out->ipaddr.ip4addr.s_addr)) <= 0) {
 227                                 fr_strerror_printf("Failed to parse IPv4 address string \"%s\"", value);
 228                                 return -1;
 229                         }
 230                 } else if (ip_hton(out, AF_INET, value, fallback) < 0) return -1;
 231
 232                 out->prefix = 32;
 233                 out->af = AF_INET;
 234
 235                 return 0;
 236         }
 237
 238         /*
 239          *      Otherwise parse the prefix
 240          */
 241         if ((size_t)(p - value) >= INET_ADDRSTRLEN) {
 242                 fr_strerror_printf("Invalid IPv4 address string \"%s\"", value);
 243                 return -1;
 244         }
 245
 246         /*
 247          *      Copy the IP portion into a temporary buffer if we haven't already.
 248          */
 249         if (inlen == 0) memcpy(buffer, value, p - value);
 250         buffer[p - value] = '\0';
 251
 252         if (!resolve) {
 253                 if (inet_pton(AF_INET, buffer, &(out->ipaddr.ip4addr.s_addr)) <= 0) {
 254                         fr_strerror_printf("Failed to parse IPv4 address string \"%s\"", value);
 255                         return -1;
 256                 }
 257         } else if (ip_hton(out, AF_INET, buffer, fallback) < 0) return -1;
 258
 259         prefix = strtoul(p + 1, &eptr, 10);
 260         if (prefix > 32) {
 261                 fr_strerror_printf("Invalid IPv4 mask length \"%s\".  Should be between 0-32", p);
 262                 return -1;
 263         }
 264         if (eptr[0] != '\0') {
 265                 fr_strerror_printf("Failed to parse IPv4 address string \"%s\", "
 266                                    "got garbage after mask length \"%s\"", value, eptr);
 267                 return -1;
 268         }
 269
 270         if (prefix < 32) {
 271                 out->ipaddr.ip4addr = fr_inaddr_mask(&(out->ipaddr.ip4addr), prefix);
 272         }
 273
 274         out->prefix = (uint8_t) prefix;
 275         out->af = AF_INET;
 276
 277         return 0;
 278 }
 279
 280 /** Parse an IPv6 address or IPv6 prefix in presentation format (and others)
 281  *
 282  * @param out Where to write the ip address value.
 283  * @param value to parse.
 284  * @param inlen Length of value, if value is \0 terminated inlen may be 0.
 285  * @param resolve If true and value doesn't look like an IP address, try and resolve value as a hostname.
 286  * @param fallback to IPv4 resolution if no AAAA records can be found.
 287  * @return 0 if ip address was parsed successfully, else -1 on error.
 288  */
 289 int fr_pton6(fr_ipaddr_t *out, char const *value, size_t inlen, bool resolve, bool fallback)
 290 {
 291         char const *p;
 292         unsigned int prefix;
 293         char *eptr;
 294
 295         /* IPv6  + / + [0-9]{1,3} */
 296         char buffer[INET6_ADDRSTRLEN + 4];
 297
 298         /*
 299          *      Copy to intermediary buffer if we were given a length
 300          */
 301         if (inlen > 0) {
 302                 if (inlen >= sizeof(buffer)) {
 303                         fr_strerror_printf("Invalid IPv6 address string \"%s\"", value);
 304                         return -1;
 305                 }
 306                 memcpy(buffer, value, inlen);
 307                 buffer[inlen] = '\0';
 308         }
 309
 310         p = strchr(value, '/');
 311         if (!p) {
 312                 /*
 313                  *      Allow '*' as the wildcard address
 314                  */
 315                 if ((value[0] == '*') && (value[1] == '\0')) {
 316                         memset(&out->ipaddr.ip6addr.s6_addr, 0, sizeof(out->ipaddr.ip6addr.s6_addr));
 317                 } else if (!resolve) {
 318                         if (inet_pton(AF_INET6, value, &(out->ipaddr.ip6addr.s6_addr)) <= 0) {
 319                                 fr_strerror_printf("Failed to parse IPv6 address string \"%s\"", value);
 320                                 return -1;
 321                         }
 322                 } else if (ip_hton(out, AF_INET6, value, fallback) < 0) return -1;
 323
 324                 out->prefix = 128;
 325                 out->af = AF_INET6;
 326
 327                 return 0;
 328         }
 329
 330         if ((p - value) >= INET6_ADDRSTRLEN) {
 331                 fr_strerror_printf("Invalid IPv6 address string \"%s\"", value);
 332                 return -1;
 333         }
 334
 335         /*
 336          *      Copy string to temporary buffer if we didn't do it earlier
 337          */
 338         if (inlen == 0) memcpy(buffer, value, p - value);
 339         buffer[p - value] = '\0';
 340
 341         if (!resolve) {
 342                 if (inet_pton(AF_INET6, buffer, &(out->ipaddr.ip6addr.s6_addr)) <= 0) {
 343                         fr_strerror_printf("Failed to parse IPv6 address string \"%s\"", value);
 344                         return -1;
 345                 }
 346         } else if (ip_hton(out, AF_INET6, buffer, fallback) < 0) return -1;
 347
 348         prefix = strtoul(p + 1, &eptr, 10);
 349         if (prefix > 128) {
 350                 fr_strerror_printf("Invalid IPv6 mask length \"%s\".  Should be between 0-128", p);
 351                 return -1;
 352         }
 353         if (eptr[0] != '\0') {
 354                 fr_strerror_printf("Failed to parse IPv6 address string \"%s\", "
 355                                    "got garbage after mask length \"%s\"", value, eptr);
 356                 return -1;
 357         }
 358
 359         if (prefix < 128) {
 360                 struct in6_addr addr;
 361
 362                 addr = fr_in6addr_mask(&(out->ipaddr.ip6addr), prefix);
 363                 memcpy(&(out->ipaddr.ip6addr.s6_addr), &addr, sizeof(addr));
 364         }
 365
 366         out->prefix = (uint8_t) prefix;
 367         out->af = AF_INET6;
 368
 369         return 0;
 370 }
 371
 372 /** Simple wrapper to decide whether an IP value is v4 or v6 and call the appropriate parser.
 373  *
 374  * @param out Where to write the ip address value.
 375  * @param value to parse.
 376  * @param inlen Length of value, if value is \0 terminated inlen may be 0.
 377  * @param resolve If true and value doesn't look like an IP address, try and resolve value as a hostname.
 378  * @return 0 if ip address was parsed successfully, else -1 on error.
 379  */
 380 int fr_pton(fr_ipaddr_t *out, char const *value, size_t inlen, bool resolve)
 381 {
 382         size_t len, i;
 383
 384         len = (inlen == 0) ? strlen(value) : inlen;
 385         for (i = 0; i < len; i++) switch (value[i]) {
 386         /*
 387          *      Chars illegal in domain names and IPv4 addresses.
 388          *      Must be v6 and cannot be a domain.
 389          */
 390         case ':':
 391         case '[':
 392         case ']':
 393                 return fr_pton6(out, value, inlen, false, false);
 394
 395         /*
 396          *      Chars which don't really tell us anything
 397          */
 398         case '.':
 399         case '/':
 400                 continue;
 401
 402         default:
 403                 /*
 404                  *      Outside the range of IPv4 chars, must be a domain
 405                  *      Use A record in preference to AAAA record.
 406                  */
 407                 if ((value[i] < '0') || (value[i] > '9')) {
 408                         if (!resolve) return -1;
 409                         return fr_pton4(out, value, inlen, true, true);
 410                 }
 411                 break;
 412         }
 413
 414         /*
 415          *      All chars were in the IPv4 set [0-9/.], must be an IPv4
 416          *      address.
 417          */
 418         return fr_pton4(out, value, inlen, false, false);
 419 }
 420
 421 /** Check if the IP address is equivalent to INADDR_ANY
 422  *
 423  * @param addr to chec.
 424  * @return true if IP address matches INADDR_ANY or INADDR6_ANY (assumed to be 0), else false.
 425  */
 426 bool is_wildcard(fr_ipaddr_t *addr)
 427 {
 428         static struct in6_addr in6_addr;
 429
 430         switch (addr->af) {
 431         case AF_INET:
 432                 return (addr->ipaddr.ip4addr.s_addr == htons(INADDR_ANY));
 433
 434         case AF_INET6:
 435                 return (memcmp(addr->ipaddr.ip6addr.s6_addr, in6_addr.s6_addr, sizeof(in6_addr.s6_addr)) == 0) ? true :false;
 436
 437         default:
 438                 fr_assert(0);
 439                 return false;
 440         }
 441 }
 442
 443 int fr_ntop(char *out, size_t outlen, fr_ipaddr_t *addr)
 444 {
 445         char buffer[INET6_ADDRSTRLEN];
 446
 447         if (inet_ntop(addr->af, &(addr->ipaddr), buffer, sizeof(buffer)) == NULL) return -1;
 448
 449         return snprintf(out, outlen, "%s/%i", buffer, addr->prefix);
 450 }
 451
 452 /*
 453  *      Internal wrapper for locking, to minimize the number of ifdef's
 454  *
 455  *      Use fcntl or error
 456  */
 457 int rad_lockfd(int fd, int lock_len)
 458 {
 459 #ifdef F_WRLCK
 460         struct flock fl;
 461
 462         fl.l_start = 0;
 463         fl.l_len = lock_len;
 464         fl.l_pid = getpid();
 465         fl.l_type = F_WRLCK;
 466         fl.l_whence = SEEK_CUR;
 467
 468         return fcntl(fd, F_SETLKW, (void *)&fl);
 469 #else
 470 #error "missing definition for F_WRLCK, all file locks will fail"
 471
 472         return -1;
 473 #endif
 474 }
 475
 476 /*
 477  *      Internal wrapper for locking, to minimize the number of ifdef's
 478  *
 479  *      Lock an fd, prefer lockf() over flock()
 480  *      Nonblocking version.
 481  */
 482 int rad_lockfd_nonblock(int fd, int lock_len)
 483 {
 484 #ifdef F_WRLCK
 485         struct flock fl;
 486
 487         fl.l_start = 0;
 488         fl.l_len = lock_len;
 489         fl.l_pid = getpid();
 490         fl.l_type = F_WRLCK;
 491         fl.l_whence = SEEK_CUR;
 492
 493         return fcntl(fd, F_SETLK, (void *)&fl);
 494 #else
 495 #error "missing definition for F_WRLCK, all file locks will fail"
 496
 497         return -1;
 498 #endif
 499 }
 500
 501 /*
 502  *      Internal wrapper for unlocking, to minimize the number of ifdef's
 503  *      in the source.
 504  *
 505  *      Unlock an fd, prefer lockf() over flock()
 506  */
 507 int rad_unlockfd(int fd, int lock_len)
 508 {
 509 #ifdef F_WRLCK
 510         struct flock fl;
 511
 512         fl.l_start = 0;
 513         fl.l_len = lock_len;
 514         fl.l_pid = getpid();
 515         fl.l_type = F_WRLCK;
 516         fl.l_whence = SEEK_CUR;
 517
 518         return fcntl(fd, F_UNLCK, (void *)&fl);
 519 #else
 520 #error "missing definition for F_WRLCK, all file locks will fail"
 521
 522         return -1;
 523 #endif
 524 }
 525
 526 /*
 527  *      Return an interface-id in standard colon notation
 528  */
 529 char *ifid_ntoa(char *buffer, size_t size, uint8_t const *ifid)
 530 {
 531         snprintf(buffer, size, "%x:%x:%x:%x",
 532                  (ifid[0] << 8) + ifid[1], (ifid[2] << 8) + ifid[3],
 533                  (ifid[4] << 8) + ifid[5], (ifid[6] << 8) + ifid[7]);
 534         return buffer;
 535 }
 536
 537
 538 /*
 539  *      Return an interface-id from
 540  *      one supplied in standard colon notation.
 541  */
 542 uint8_t *ifid_aton(char const *ifid_str, uint8_t *ifid)
 543 {
 544         static char const xdigits[] = "0123456789abcdef";
 545         char const *p, *pch;
 546         int num_id = 0, val = 0, idx = 0;
 547
 548         for (p = ifid_str; ; ++p) {
 549                 if (*p == ':' || *p == '\0') {
 550                         if (num_id <= 0)
 551                                 return NULL;
 552
 553                         /*
 554                          *      Drop 'val' into the array.
 555                          */
 556                         ifid[idx] = (val >> 8) & 0xff;
 557                         ifid[idx + 1] = val & 0xff;
 558                         if (*p == '\0') {
 559                                 /*
 560                                  *      Must have all entries before
 561                                  *      end of the string.
 562                                  */
 563                                 if (idx != 6)
 564                                         return NULL;
 565                                 break;
 566                         }
 567                         val = 0;
 568                         num_id = 0;
 569                         if ((idx += 2) > 6)
 570                                 return NULL;
 571                 } else if ((pch = strchr(xdigits, tolower(*p))) != NULL) {
 572                         if (++num_id > 4)
 573                                 return NULL;
 574                         /*
 575                          *      Dumb version of 'scanf'
 576                          */
 577                         val <<= 4;
 578                         val |= (pch - xdigits);
 579                 } else
 580                         return NULL;
 581         }
 582         return ifid;
 583 }
 584
 585
 586 #ifndef HAVE_INET_PTON
 587 static int inet_pton4(char const *src, struct in_addr *dst)
 588 {
 589         int octet;
 590         unsigned int num;
 591         char const *p, *off;
 592         uint8_t tmp[4];
 593         static char const digits[] = "0123456789";
 594
 595         octet = 0;
 596         p = src;
 597         while (1) {
 598                 num = 0;
 599                 while (*p && ((off = strchr(digits, *p)) != NULL)) {
 600                         num *= 10;
 601                         num += (off - digits);
 602
 603                         if (num > 255) return 0;
 604
 605                         p++;
 606                 }
 607                 if (!*p) break;
 608
 609                 /*
 610                  *      Not a digit, MUST be a dot, else we
 611                  *      die.
 612                  */
 613                 if (*p != '.') {
 614                         return 0;
 615                 }
 616
 617                 tmp[octet++] = num;
 618                 p++;
 619         }
 620
 621         /*
 622          *      End of the string.  At the fourth
 623          *      octet is OK, anything else is an
 624          *      error.
 625          */
 626         if (octet != 3) {
 627                 return 0;
 628         }
 629         tmp[3] = num;
 630
 631         memcpy(dst, &tmp, sizeof(tmp));
 632         return 1;
 633 }
 634
 635
 636 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 637 /* int
 638  * inet_pton6(src, dst)
 639  *      convert presentation level address to network order binary form.
 640  * return:
 641  *      1 if `src' is a valid [RFC1884 2.2] address, else 0.
 642  * notice:
 643  *      (1) does not touch `dst' unless it's returning 1.
 644  *      (2) :: in a full address is silently ignored.
 645  * credit:
 646  *      inspired by Mark Andrews.
 647  * author:
 648  *      Paul Vixie, 1996.
 649  */
 650 static int inet_pton6(char const *src, unsigned char *dst)
 651 {
 652         static char const xdigits_l[] = "0123456789abcdef",
 653                           xdigits_u[] = "0123456789ABCDEF";
 654         u_char tmp[IN6ADDRSZ], *tp, *endp, *colonp;
 655         char const *xdigits, *curtok;
 656         int ch, saw_xdigit;
 657         u_int val;
 658
 659         memset((tp = tmp), 0, IN6ADDRSZ);
 660         endp = tp + IN6ADDRSZ;
 661         colonp = NULL;
 662         /* Leading :: requires some special handling. */
 663         if (*src == ':')
 664                 if (*++src != ':')
 665                         return (0);
 666         curtok = src;
 667         saw_xdigit = 0;
 668         val = 0;
 669         while ((ch = *src++) != '\0') {
 670                 char const *pch;
 671
 672                 if ((pch = strchr((xdigits = xdigits_l), ch)) == NULL)
 673                         pch = strchr((xdigits = xdigits_u), ch);
 674                 if (pch != NULL) {
 675                         val <<= 4;
 676                         val |= (pch - xdigits);
 677                         if (val > 0xffff)
 678                                 return (0);
 679                         saw_xdigit = 1;
 680                         continue;
 681                 }
 682                 if (ch == ':') {
 683                         curtok = src;
 684                         if (!saw_xdigit) {
 685                                 if (colonp)
 686                                         return (0);
 687                                 colonp = tp;
 688                                 continue;
 689                         }
 690                         if (tp + INT16SZ > endp)
 691                                 return (0);
 692                         *tp++ = (u_char) (val >> 8) & 0xff;
 693                         *tp++ = (u_char) val & 0xff;
 694                         saw_xdigit = 0;
 695                         val = 0;
 696                         continue;
 697                 }
 698                 if (ch == '.' && ((tp + INADDRSZ) <= endp) &&
 699                     inet_pton4(curtok, (struct in_addr *) tp) > 0) {
 700                         tp += INADDRSZ;
 701                         saw_xdigit = 0;
 702                         break;  /* '\0' was seen by inet_pton4(). */
 703                 }
 704                 return (0);
 705         }
 706         if (saw_xdigit) {
 707                 if (tp + INT16SZ > endp)
 708                         return (0);
 709                 *tp++ = (u_char) (val >> 8) & 0xff;
 710                 *tp++ = (u_char) val & 0xff;
 711         }
 712         if (colonp != NULL) {
 713                 /*
 714                  * Since some memmove()'s erroneously fail to handle
 715                  * overlapping regions, we'll do the shift by hand.
 716                  */
 717                 int const n = tp - colonp;
 718                 int i;
 719
 720                 for (i = 1; i <= n; i++) {
 721                         endp[- i] = colonp[n - i];
 722                         colonp[n - i] = 0;
 723                 }
 724                 tp = endp;
 725         }
 726         if (tp != endp)
 727                 return (0);
 728         /* bcopy(tmp, dst, IN6ADDRSZ); */
 729         memcpy(dst, tmp, IN6ADDRSZ);
 730         return (1);
 731 }
 732 #endif
 733
 734 /*
 735  *      Utility function, so that the rest of the server doesn't
 736  *      have ifdef's around IPv6 support
 737  */
 738 int inet_pton(int af, char const *src, void *dst)
 739 {
 740         if (af == AF_INET) {
 741                 return inet_pton4(src, dst);
 742         }
 743 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 744
 745         if (af == AF_INET6) {
 746                 return inet_pton6(src, dst);
 747         }
 748 #endif
 749
 750         return -1;
 751 }
 752 #endif
 753
 754 #ifndef HAVE_INET_NTOP
 755 /*
 756  *      Utility function, so that the rest of the server doesn't
 757  *      have ifdef's around IPv6 support
 758  */
 759 char const *inet_ntop(int af, void const *src, char *dst, size_t cnt)
 760 {
 761         if (af == AF_INET) {
 762                 uint8_t const *ipaddr = src;
 763
 764                 if (cnt <= INET_ADDRSTRLEN) return NULL;
 765
 766                 snprintf(dst, cnt, "%d.%d.%d.%d",
 767                          ipaddr[0], ipaddr[1],
 768                          ipaddr[2], ipaddr[3]);
 769                 return dst;
 770         }
 771
 772         /*
 773          *      If the system doesn't define this, we define it
 774          *      in missing.h
 775          */
 776         if (af == AF_INET6) {
 777                 struct in6_addr const *ipaddr = src;
 778
 779                 if (cnt <= INET6_ADDRSTRLEN) return NULL;
 780
 781                 snprintf(dst, cnt, "%x:%x:%x:%x:%x:%x:%x:%x",
 782                          (ipaddr->s6_addr[0] << 8) | ipaddr->s6_addr[1],
 783                          (ipaddr->s6_addr[2] << 8) | ipaddr->s6_addr[3],
 784                          (ipaddr->s6_addr[4] << 8) | ipaddr->s6_addr[5],
 785                          (ipaddr->s6_addr[6] << 8) | ipaddr->s6_addr[7],
 786                          (ipaddr->s6_addr[8] << 8) | ipaddr->s6_addr[9],
 787                          (ipaddr->s6_addr[10] << 8) | ipaddr->s6_addr[11],
 788                          (ipaddr->s6_addr[12] << 8) | ipaddr->s6_addr[13],
 789                          (ipaddr->s6_addr[14] << 8) | ipaddr->s6_addr[15]);
 790                 return dst;
 791         }
 792
 793         return NULL;            /* don't support IPv6 */
 794 }
 795 #endif
 796
 797 /** Wrappers for IPv4/IPv6 host to IP address lookup
 798  *
 799  * This function returns only one IP address, of the specified address family,
 800  * or the first address (of whatever family), if AF_UNSPEC is used.
 801  *
 802  * If fallback is specified and af is AF_INET, but no AF_INET records were
 803  * found and a record for AF_INET6 exists that record will be returned.
 804  *
 805  * If fallback is specified and af is AF_INET6, and a record with AF_INET4 exists
 806  * that record will be returned instead.
 807  *
 808  * @param out Where to write result.
 809  * @param af To search for in preference.
 810  * @param hostname to search for.
 811  * @param fallback to the other adress family, if no records matching af, found.
 812  * @return 0 on success, else -1 on failure.
 813  */
 814 int ip_hton(fr_ipaddr_t *out, int af, char const *hostname, bool fallback)
 815 {
 816         int rcode;
 817         struct addrinfo hints, *ai = NULL, *alt = NULL, *res = NULL;
 818
 819         if (!fr_hostname_lookups) {
 820 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 821                 if (af == AF_UNSPEC) {
 822                         char const *p;
 823
 824                         for (p = hostname; *p != '\0'; p++) {
 825                                 if ((*p == ':') ||
 826                                     (*p == '[') ||
 827                                     (*p == ']')) {
 828                                         af = AF_INET6;
 829                                         break;
 830                                 }
 831                         }
 832                 }
 833 #endif
 834
 835                 if (af == AF_UNSPEC) af = AF_INET;
 836
 837                 if (!inet_pton(af, hostname, &(out->ipaddr))) {
 838                         return -1;
 839                 }
 840
 841                 out->af = af;
 842                 return 0;
 843         }
 844
 845         memset(&hints, 0, sizeof(hints));
 846         hints.ai_family = af;
 847
 848 #ifdef TALLOC_DEBUG
 849         /*
 850          *      Avoid malloc for IP addresses.  This helps us debug
 851          *      memory errors when using talloc.
 852          */
 853         if (af == AF_INET) {
 854                 /*
 855                  *      If it's all numeric, avoid getaddrinfo()
 856                  */
 857                 if (inet_pton(af, hostname, &out->ipaddr.ip4addr) == 1) {
 858                         return 0;
 859                 }
 860         }
 861 #endif
 862
 863         if ((rcode = getaddrinfo(hostname, NULL, &hints, &res)) != 0) {
 864                 fr_strerror_printf("ip_hton: %s", gai_strerror(rcode));
 865                 return -1;
 866         }
 867
 868         for (ai = res; ai; ai = ai->ai_next) {
 869                 if ((af == ai->ai_family) || (af == AF_UNSPEC)) break;
 870                 if (!alt && fallback && ((ai->ai_family == AF_INET) || (ai->ai_family == AF_INET6))) alt = ai;
 871         }
 872
 873         if (!ai) ai = alt;
 874         if (!ai) {
 875                 fr_strerror_printf("ip_hton failed to find requested information for host %.100s", hostname);
 876                 freeaddrinfo(ai);
 877                 return -1;
 878         }
 879
 880         rcode = fr_sockaddr2ipaddr((struct sockaddr_storage *)ai->ai_addr,
 881                                    ai->ai_addrlen, out, NULL);
 882         freeaddrinfo(ai);
 883         if (!rcode) return -1;
 884
 885         return 0;
 886 }
 887
 888 /*
 889  *      Look IP addresses up, and print names (depending on DNS config)
 890  */
 891 char const *ip_ntoh(fr_ipaddr_t const *src, char *dst, size_t cnt)
 892 {
 893         struct sockaddr_storage ss;
 894         int error;
 895         socklen_t salen;
 896
 897         /*
 898          *      No DNS lookups
 899          */
 900         if (!fr_dns_lookups) {
 901                 return inet_ntop(src->af, &(src->ipaddr), dst, cnt);
 902         }
 903
 904         if (!fr_ipaddr2sockaddr(src, 0, &ss, &salen)) {
 905                 return NULL;
 906         }
 907
 908         if ((error = getnameinfo((struct sockaddr *)&ss, salen, dst, cnt, NULL, 0,
 909                                  NI_NUMERICHOST | NI_NUMERICSERV)) != 0) {
 910                 fr_strerror_printf("ip_ntoh: %s", gai_strerror(error));
 911                 return NULL;
 912         }
 913         return dst;
 914 }
 915
 916 /** Mask off a portion of an IPv4 address
 917  *
 918  * @param ipaddr to mask.
 919  * @param prefix Number of contiguous bits to mask.
 920  * @return an ipv6 address with the host portion zeroed out.
 921  */
 922 struct in_addr fr_inaddr_mask(struct in_addr const *ipaddr, uint8_t prefix)
 923 {
 924         uint32_t ret;
 925
 926         if (prefix > 32) {
 927                 prefix = 32;
 928         }
 929
 930         /* Short circuit */
 931         if (prefix == 32) {
 932                 return *ipaddr;
 933         }
 934
 935         ret = htonl(~((0x00000001UL << (32 - prefix)) - 1)) & ipaddr->s_addr;
 936         return (*(struct in_addr *)&ret);
 937 }
 938
 939 /** Mask off a portion of an IPv6 address
 940  *
 941  * @param ipaddr to mask.
 942  * @param prefix Number of contiguous bits to mask.
 943  * @return an ipv6 address with the host portion zeroed out.
 944  */
 945 struct in6_addr fr_in6addr_mask(struct in6_addr const *ipaddr, uint8_t prefix)
 946 {
 947         uint64_t const *p = (uint64_t const *) ipaddr;
 948         uint64_t ret[2], *o = ret;
 949
 950         if (prefix > 128) {
 951                 prefix = 128;
 952         }
 953
 954         /* Short circuit */
 955         if (prefix == 128) {
 956                 return *ipaddr;
 957         }
 958
 959         if (prefix >= 64) {
 960                 prefix -= 64;
 961                 *o++ = 0xffffffffffffffffULL & *p++;
 962         } else {
 963                 ret[1] = 0;
 964         }
 965
 966         *o = htonll(~((0x0000000000000001ULL << (64 - prefix)) - 1)) & *p;
 967
 968         return *(struct in6_addr *) &ret;
 969 }
 970
 971 /** Zeroes out the host portion of an fr_ipaddr_t
 972  *
 973  * @param[in,out] addr to mask
 974  * @param[in] prefix Length of the network portion.
 975  */
 976 void fr_ipaddr_mask(fr_ipaddr_t *addr, uint8_t prefix)
 977 {
 978
 979         switch (addr->af) {
 980         case AF_INET:
 981                 addr->ipaddr.ip4addr = fr_inaddr_mask(&addr->ipaddr.ip4addr, prefix);
 982                 break;
 983
 984         case AF_INET6:
 985                 addr->ipaddr.ip6addr = fr_in6addr_mask(&addr->ipaddr.ip6addr, prefix);
 986                 break;
 987
 988         default:
 989                 return;
 990         }
 991         addr->prefix = prefix;
 992 }
 993
 994 static char const *hextab = "0123456789abcdef";
 995
 996 /** Convert hex strings to binary data
 997  *
 998  * @param bin Buffer to write output to.
 999  * @param hex input string.
1000  * @param outlen length of output buffer (or length of input string / 2).
1001  * @return length of data written to buffer.
1002  */
1003 size_t fr_hex2bin(uint8_t *bin, char const *hex, size_t outlen)
1004 {
1005         size_t i;
1006         char *c1, *c2;
1007
1008         for (i = 0; i < outlen; i++) {
1009                 if(!(c1 = memchr(hextab, tolower((int) hex[i << 1]), 16)) ||
1010                    !(c2 = memchr(hextab, tolower((int) hex[(i << 1) + 1]), 16)))
1011                         break;
1012                  bin[i] = ((c1-hextab)<<4) + (c2-hextab);
1013         }
1014
1015         return i;
1016 }
1017
1018
1019 /** Convert binary data to a hex string
1020  *
1021  * Ascii encoded hex string will not be prefixed with '0x'
1022  *
1023  * @warning If the output buffer isn't long enough, we have a buffer overflow.
1024  *
1025  * @param[out] hex Buffer to write hex output.
1026  * @param[in] bin input.
1027  * @param[in] inlen of bin input.
1028  * @return length of data written to buffer.
1029  */
1030 size_t fr_bin2hex(char *hex, uint8_t const *bin, size_t inlen)
1031 {
1032         size_t i;
1033
1034         for (i = 0; i < inlen; i++) {
1035                 hex[0] = hextab[((*bin) >> 4) & 0x0f];
1036                 hex[1] = hextab[*bin & 0x0f];
1037                 hex += 2;
1038                 bin++;
1039         }
1040
1041         *hex = '\0';
1042         return inlen * 2;
1043 }
1044
1045
1046
1047 /** Consume the integer (or hex) portion of a value string
1048  *
1049  * @param value string to parse.
1050  * @param end pointer to the first non numeric char.
1051  * @return integer value.
1052  */
1053 uint32_t fr_strtoul(char const *value, char **end)
1054 {
1055         if ((value[0] == '0') && (value[1] == 'x')) {
1056                 return strtoul(value, end, 16);
1057         }
1058
1059         return strtoul(value, end, 10);
1060 }
1061
1062 /** Check whether the string is all whitespace
1063  *
1064  * @return true if the entirety of the string is whitespace, else false.
1065  */
1066 bool is_whitespace(char const *value)
1067 {
1068         do {
1069                 if (!isspace(*value)) return false;
1070         } while (*++value);
1071
1072         return true;
1073 }
1074
1075 /** Check whether the string is all numbers
1076  *
1077  * @return true if the entirety of the string is are numebrs, else false.
1078  */
1079 bool is_integer(char const *value)
1080 {
1081         do {
1082                 if (!isdigit(*value)) return false;
1083         } while (*++value);
1084
1085         return true;
1086 }
1087
1088 /** Check whether the string is allzeros
1089  *
1090  * @return true if the entirety of the string is are numebrs, else false.
1091  */
1092 bool is_zero(char const *value)
1093 {
1094         do {
1095                 if (*value != '0') return false;
1096         } while (*++value);
1097
1098         return true;
1099 }
1100
1101 /*
1102  *      So we don't have ifdef's in the rest of the code
1103  */
1104 #ifndef HAVE_CLOSEFROM
1105 int closefrom(int fd)
1106 {
1107         int i;
1108         int maxfd = 256;
1109
1110 #ifdef _SC_OPEN_MAX
1111         maxfd = sysconf(_SC_OPEN_MAX);
1112         if (maxfd < 0) {
1113           maxfd = 256;
1114         }
1115 #endif
1116
1117         if (fd > maxfd) return 0;
1118
1119         /*
1120          *      FIXME: return EINTR?
1121          *
1122          *      Use F_CLOSEM?
1123          */
1124         for (i = fd; i < maxfd; i++) {
1125                 close(i);
1126         }
1127
1128         return 0;
1129 }
1130 #endif
1131
1132 int fr_ipaddr_cmp(fr_ipaddr_t const *a, fr_ipaddr_t const *b)
1133 {
1134         if (a->af < b->af) return -1;
1135         if (a->af > b->af) return +1;
1136
1137         switch (a->af) {
1138         case AF_INET:
1139                 return memcmp(&a->ipaddr.ip4addr,
1140                               &b->ipaddr.ip4addr,
1141                               sizeof(a->ipaddr.ip4addr));
1142                 break;
1143
1144 #ifdef HAVE_STRUCT_SOCKADDR_IN6
1145         case AF_INET6:
1146                 if (a->scope < b->scope) return -1;
1147                 if (a->scope > b->scope) return +1;
1148
1149                 return memcmp(&a->ipaddr.ip6addr,
1150                               &b->ipaddr.ip6addr,
1151                               sizeof(a->ipaddr.ip6addr));
1152                 break;
1153 #endif
1154
1155         default:
1156                 break;
1157         }
1158
1159         return -1;
1160 }
1161
1162 int fr_ipaddr2sockaddr(fr_ipaddr_t const *ipaddr, uint16_t port,
1163                        struct sockaddr_storage *sa, socklen_t *salen)
1164 {
1165         if (ipaddr->af == AF_INET) {
1166                 struct sockaddr_in s4;
1167
1168                 *salen = sizeof(s4);
1169
1170                 memset(&s4, 0, sizeof(s4));
1171                 s4.sin_family = AF_INET;
1172                 s4.sin_addr = ipaddr->ipaddr.ip4addr;
1173                 s4.sin_port = htons(port);
1174                 memset(sa, 0, sizeof(*sa));
1175                 memcpy(sa, &s4, sizeof(s4));
1176
1177 #ifdef HAVE_STRUCT_SOCKADDR_IN6
1178         } else if (ipaddr->af == AF_INET6) {
1179                 struct sockaddr_in6 s6;
1180
1181                 *salen = sizeof(s6);
1182
1183                 memset(&s6, 0, sizeof(s6));
1184                 s6.sin6_family = AF_INET6;
1185                 s6.sin6_addr = ipaddr->ipaddr.ip6addr;
1186                 s6.sin6_port = htons(port);
1187                 s6.sin6_scope_id = ipaddr->scope;
1188                 memset(sa, 0, sizeof(*sa));
1189                 memcpy(sa, &s6, sizeof(s6));
1190 #endif
1191         } else {
1192                 return 0;
1193         }
1194
1195         return 1;
1196 }
1197
1198
1199 int fr_sockaddr2ipaddr(struct sockaddr_storage const *sa, socklen_t salen,
1200                        fr_ipaddr_t *ipaddr, uint16_t *port)
1201 {
1202         if (sa->ss_family == AF_INET) {
1203                 struct sockaddr_in      s4;
1204
1205                 if (salen < sizeof(s4)) {
1206                         fr_strerror_printf("IPv4 address is too small");
1207                         return 0;
1208                 }
1209
1210                 memcpy(&s4, sa, sizeof(s4));
1211                 ipaddr->af = AF_INET;
1212                 ipaddr->prefix = 32;
1213                 ipaddr->ipaddr.ip4addr = s4.sin_addr;
1214                 if (port) *port = ntohs(s4.sin_port);
1215
1216 #ifdef HAVE_STRUCT_SOCKADDR_IN6
1217         } else if (sa->ss_family == AF_INET6) {
1218                 struct sockaddr_in6     s6;
1219
1220                 if (salen < sizeof(s6)) {
1221                         fr_strerror_printf("IPv6 address is too small");
1222                         return 0;
1223                 }
1224
1225                 memcpy(&s6, sa, sizeof(s6));
1226                 ipaddr->af = AF_INET6;
1227                 ipaddr->prefix = 128;
1228                 ipaddr->ipaddr.ip6addr = s6.sin6_addr;
1229                 if (port) *port = ntohs(s6.sin6_port);
1230                 ipaddr->scope = s6.sin6_scope_id;
1231 #endif
1232
1233         } else {
1234                 fr_strerror_printf("Unsupported address famility %d",
1235                                    sa->ss_family);
1236                 return 0;
1237         }
1238
1239         return 1;
1240 }
1241
1242 /** Convert UTF8 string to UCS2 encoding
1243  *
1244  * @note Borrowed from src/crypto/ms_funcs.c of wpa_supplicant project (http://hostap.epitest.fi/wpa_supplicant/)
1245  *
1246  * @param[out] out Where to write the ucs2 string.
1247  * @param[in] outlen Size of output buffer.
1248  * @param[in] in UTF8 string to convert.
1249  * @param[in] inlen length of UTF8 string.
1250  * @return the size of the UCS2 string written to the output buffer (in bytes).
1251  */
1252 ssize_t fr_utf8_to_ucs2(uint8_t *out, size_t outlen, char const *in, size_t inlen)
1253 {
1254         size_t i;
1255         uint8_t *start = out;
1256
1257         for (i = 0; i < inlen; i++) {
1258                 uint8_t c, c2, c3;
1259
1260                 c = in[i];
1261                 if ((size_t)(out - start) >= outlen) {
1262                         /* input too long */
1263                         return -1;
1264                 }
1265
1266                 /* One-byte encoding */
1267                 if (c <= 0x7f) {
1268                         FR_PUT_LE16(out, c);
1269                         out += 2;
1270                         continue;
1271                 } else if ((i == (inlen - 1)) || ((size_t)(out - start) >= (outlen - 1))) {
1272                         /* Incomplete surrogate */
1273                         return -1;
1274                 }
1275
1276                 c2 = in[++i];
1277                 /* Two-byte encoding */
1278                 if ((c & 0xe0) == 0xc0) {
1279                         FR_PUT_LE16(out, ((c & 0x1f) << 6) | (c2 & 0x3f));
1280                         out += 2;
1281                         continue;
1282                 }
1283                 if ((i == inlen) || ((size_t)(out - start) >= (outlen - 1))) {
1284                         /* Incomplete surrogate */
1285                         return -1;
1286                 }
1287
1288                 /* Three-byte encoding */
1289                 c3 = in[++i];
1290                 FR_PUT_LE16(out, ((c & 0xf) << 12) | ((c2 & 0x3f) << 6) | (c3 & 0x3f));
1291                 out += 2;
1292         }
1293
1294         return out - start;
1295 }
1296
1297 /** Write 128bit unsigned integer to buffer
1298  *
1299  * @author Alexey Frunze
1300  *
1301  * @param out where to write result to.
1302  * @param outlen size of out.
1303  * @param num 128 bit integer.
1304  */
1305 size_t fr_prints_uint128(char *out, size_t outlen, uint128_t const num)
1306 {
1307         char buff[128 / 3 + 1 + 1];
1308         uint64_t n[2];
1309         char *p = buff;
1310         int i;
1311
1312         memset(buff, '0', sizeof(buff) - 1);
1313         buff[sizeof(buff) - 1] = '\0';
1314
1315         memcpy(n, &num, sizeof(n));
1316
1317         for (i = 0; i < 128; i++) {
1318                 ssize_t j;
1319                 int carry;
1320
1321                 carry = (n[1] >= 0x8000000000000000);
1322
1323                 // Shift n[] left, doubling it
1324                 n[1] = ((n[1] << 1) & 0xffffffffffffffff) + (n[0] >= 0x8000000000000000);
1325                 n[0] = ((n[0] << 1) & 0xffffffffffffffff);
1326
1327                 // Add s[] to itself in decimal, doubling it
1328                 for (j = sizeof(buff) - 2; j >= 0; j--) {
1329                         buff[j] += buff[j] - '0' + carry;
1330                         carry = (buff[j] > '9');
1331                         if (carry) {
1332                                 buff[j] -= 10;
1333                         }
1334                 }
1335         }
1336
1337         while ((*p == '0') && (p < &buff[sizeof(buff) - 2])) {
1338                 p++;
1339         }
1340
1341         return strlcpy(out, p, outlen);
1342 }
1343
1344 /** Calculate powers
1345  *
1346  * @author Orson Peters
1347  * @note Borrowed from the gist here: https://gist.github.com/nightcracker/3551590.
1348  *
1349  * @param base a 32bit signed integer.
1350  * @param exp amount to raise base by.
1351  * @return base ^ pow, or 0 on underflow/overflow.
1352  */
1353 int64_t fr_pow(int32_t base, uint8_t exp) {
1354         static const uint8_t highest_bit_set[] = {
1355                 0, 1, 2, 2, 3, 3, 3, 3,
1356                 4, 4, 4, 4, 4, 4, 4, 4,
1357                 5, 5, 5, 5, 5, 5, 5, 5,
1358                 5, 5, 5, 5, 5, 5, 5, 5,
1359                 6, 6, 6, 6, 6, 6, 6, 6,
1360                 6, 6, 6, 6, 6, 6, 6, 6,
1361                 6, 6, 6, 6, 6, 6, 6, 6,
1362                 6, 6, 6, 6, 6, 6, 6, 255, // anything past 63 is a guaranteed overflow with base > 1
1363                 255, 255, 255, 255, 255, 255, 255, 255,
1364                 255, 255, 255, 255, 255, 255, 255, 255,
1365                 255, 255, 255, 255, 255, 255, 255, 255,
1366                 255, 255, 255, 255, 255, 255, 255, 255,
1367                 255, 255, 255, 255, 255, 255, 255, 255,
1368                 255, 255, 255, 255, 255, 255, 255, 255,
1369                 255, 255, 255, 255, 255, 255, 255, 255,
1370                 255, 255, 255, 255, 255, 255, 255, 255,
1371                 255, 255, 255, 255, 255, 255, 255, 255,
1372                 255, 255, 255, 255, 255, 255, 255, 255,
1373                 255, 255, 255, 255, 255, 255, 255, 255,
1374                 255, 255, 255, 255, 255, 255, 255, 255,
1375                 255, 255, 255, 255, 255, 255, 255, 255,
1376                 255, 255, 255, 255, 255, 255, 255, 255,
1377                 255, 255, 255, 255, 255, 255, 255, 255,
1378                 255, 255, 255, 255, 255, 255, 255, 255,
1379                 255, 255, 255, 255, 255, 255, 255, 255,
1380                 255, 255, 255, 255, 255, 255, 255, 255,
1381                 255, 255, 255, 255, 255, 255, 255, 255,
1382                 255, 255, 255, 255, 255, 255, 255, 255,
1383                 255, 255, 255, 255, 255, 255, 255, 255,
1384                 255, 255, 255, 255, 255, 255, 255, 255,
1385                 255, 255, 255, 255, 255, 255, 255, 255,
1386                 255, 255, 255, 255, 255, 255, 255, 255,
1387         };
1388
1389         uint64_t result = 1;
1390
1391         switch (highest_bit_set[exp]) {
1392         case 255: // we use 255 as an overflow marker and return 0 on overflow/underflow
1393                 if (base == 1) {
1394                         return 1;
1395                 }
1396
1397                 if (base == -1) {
1398                         return 1 - 2 * (exp & 1);
1399                 }
1400                 return 0;
1401         case 6:
1402                 if (exp & 1) result *= base;
1403                 exp >>= 1;
1404                 base *= base;
1405         case 5:
1406                 if (exp & 1) result *= base;
1407                 exp >>= 1;
1408                 base *= base;
1409         case 4:
1410                 if (exp & 1) result *= base;
1411                 exp >>= 1;
1412                 base *= base;
1413         case 3:
1414                 if (exp & 1) result *= base;
1415                 exp >>= 1;
1416                 base *= base;
1417         case 2:
1418                 if (exp & 1) result *= base;
1419                 exp >>= 1;
1420                 base *= base;
1421         case 1:
1422                 if (exp & 1) result *= base;
1423         default:
1424                 return result;
1425         }
1426 }
1427
1428 /*
1429  *      Sort of strtok/strsep function.
1430  */
1431 static char *mystrtok(char **ptr, char const *sep)
1432 {
1433         char    *res;
1434
1435         if (**ptr == 0) {
1436                 return NULL;
1437         }
1438
1439         while (**ptr && strchr(sep, **ptr)) {
1440                 (*ptr)++;
1441         }
1442         if (**ptr == 0) {
1443                 return NULL;
1444         }
1445
1446         res = *ptr;
1447         while (**ptr && strchr(sep, **ptr) == NULL) {
1448                 (*ptr)++;
1449         }
1450
1451         if (**ptr != 0) {
1452                 *(*ptr)++ = 0;
1453         }
1454         return res;
1455 }
1456
1457 /** Convert string in various formats to a time_t
1458  *
1459  * @param date_str input date string.
1460  * @param date time_t to write result to.
1461  * @return 0 on success or -1 on error.
1462  */
1463 int fr_get_time(char const *date_str, time_t *date)
1464 {
1465         int             i;
1466         time_t          t;
1467         struct tm       *tm, s_tm;
1468         char            buf[64];
1469         char            *p;
1470         char            *f[4];
1471         char            *tail = NULL;
1472
1473         /*
1474          * Test for unix timestamp date
1475          */
1476         *date = strtoul(date_str, &tail, 10);
1477         if (*tail == '\0') {
1478                 return 0;
1479         }
1480
1481         tm = &s_tm;
1482         memset(tm, 0, sizeof(*tm));
1483         tm->tm_isdst = -1;      /* don't know, and don't care about DST */
1484
1485         strlcpy(buf, date_str, sizeof(buf));
1486
1487         p = buf;
1488         f[0] = mystrtok(&p, " \t");
1489         f[1] = mystrtok(&p, " \t");
1490         f[2] = mystrtok(&p, " \t");
1491         f[3] = mystrtok(&p, " \t"); /* may, or may not, be present */
1492         if (!f[0] || !f[1] || !f[2]) return -1;
1493
1494         /*
1495          *      The time has a colon, where nothing else does.
1496          *      So if we find it, bubble it to the back of the list.
1497          */
1498         if (f[3]) {
1499                 for (i = 0; i < 3; i++) {
1500                         if (strchr(f[i], ':')) {
1501                                 p = f[3];
1502                                 f[3] = f[i];
1503                                 f[i] = p;
1504                                 break;
1505                         }
1506                 }
1507         }
1508
1509         /*
1510          *  The month is text, which allows us to find it easily.
1511          */
1512         tm->tm_mon = 12;
1513         for (i = 0; i < 3; i++) {
1514                 if (isalpha( (int) *f[i])) {
1515                         /*
1516                          *  Bubble the month to the front of the list
1517                          */
1518                         p = f[0];
1519                         f[0] = f[i];
1520                         f[i] = p;
1521
1522                         for (i = 0; i < 12; i++) {
1523                                 if (strncasecmp(months[i], f[0], 3) == 0) {
1524                                         tm->tm_mon = i;
1525                                         break;
1526                                 }
1527                         }
1528                 }
1529         }
1530
1531         /* month not found? */
1532         if (tm->tm_mon == 12) return -1;
1533
1534         /*
1535          *  The year may be in f[1], or in f[2]
1536          */
1537         tm->tm_year = atoi(f[1]);
1538         tm->tm_mday = atoi(f[2]);
1539
1540         if (tm->tm_year >= 1900) {
1541                 tm->tm_year -= 1900;
1542
1543         } else {
1544                 /*
1545                  *  We can't use 2-digit years any more, they make it
1546                  *  impossible to tell what's the day, and what's the year.
1547                  */
1548                 if (tm->tm_mday < 1900) return -1;
1549
1550                 /*
1551                  *  Swap the year and the day.
1552                  */
1553                 i = tm->tm_year;
1554                 tm->tm_year = tm->tm_mday - 1900;
1555                 tm->tm_mday = i;
1556         }
1557
1558         /*
1559          *  If the day is out of range, die.
1560          */
1561         if ((tm->tm_mday < 1) || (tm->tm_mday > 31)) {
1562                 return -1;
1563         }
1564
1565         /*
1566          *      There may be %H:%M:%S.  Parse it in a hacky way.
1567          */
1568         if (f[3]) {
1569                 f[0] = f[3];    /* HH */
1570                 f[1] = strchr(f[0], ':'); /* find : separator */
1571                 if (!f[1]) return -1;
1572
1573                 *(f[1]++) = '\0'; /* nuke it, and point to MM:SS */
1574
1575                 f[2] = strchr(f[1], ':'); /* find : separator */
1576                 if (f[2]) {
1577                   *(f[2]++) = '\0';     /* nuke it, and point to SS */
1578                   tm->tm_sec = atoi(f[2]);
1579                 }                       /* else leave it as zero */
1580
1581                 tm->tm_hour = atoi(f[0]);
1582                 tm->tm_min = atoi(f[1]);
1583         }
1584
1585         /*
1586          *  Returns -1 on error.
1587          */
1588         t = mktime(tm);
1589         if (t == (time_t) -1) return -1;
1590
1591         *date = t;
1592
1593         return 0;
1594 }
1595
1596 /** Compares two pointers
1597  *
1598  * @param a first pointer to compare.
1599  * @param b second pointer to compare.
1600  * @return -1 if a < b, +1 if b > a, or 0 if both equal.
1601  */
1602 int8_t fr_pointer_cmp(void const *a, void const *b)
1603 {
1604         if (a < b) return -1;
1605         if (a == b) return 0;
1606
1607         return 1;
1608 }
1609
1610 static int _quick_partition(void const *to_sort[], int min, int max, fr_cmp_t cmp) {
1611         void const *pivot = to_sort[min];
1612         int i = min;
1613         int j = max + 1;
1614         void const *tmp;
1615
1616         for (;;) {
1617                 do ++i; while((cmp(to_sort[i], pivot) <= 0) && i <= max);
1618                 do --j; while(cmp(to_sort[j], pivot) > 0);
1619
1620                 if (i >= j) break;
1621
1622                 tmp = to_sort[i];
1623                 to_sort[i] = to_sort[j];
1624                 to_sort[j] = tmp;
1625         }
1626
1627         tmp = to_sort[min];
1628         to_sort[min] = to_sort[j];
1629         to_sort[j] = tmp;
1630
1631         return j;
1632 }
1633
1634 /** Quick sort an array of pointers using a comparator
1635  *
1636  * @param to_sort array of pointers to sort.
1637  * @param min_idx the lowest index (usually 0).
1638  * @param max_idx the highest index (usually length of array - 1).
1639  * @param cmp the comparison function to use to sort the array elements.
1640  */
1641 void fr_quick_sort(void const *to_sort[], int min_idx, int max_idx, fr_cmp_t cmp)
1642 {
1643         int part;
1644
1645         if (min_idx >= max_idx) return;
1646
1647         part = _quick_partition(to_sort, min_idx, max_idx, cmp);
1648         fr_quick_sort(to_sort, min_idx, part - 1, cmp);
1649         fr_quick_sort(to_sort, part + 1, max_idx, cmp);
1650 }
1651
1652 #ifdef TALLOC_DEBUG
1653 void fr_talloc_verify_cb(UNUSED const void *ptr, UNUSED int depth,
1654                          UNUSED int max_depth, UNUSED int is_ref,
1655                          UNUSED void *private_data)
1656 {
1657         /* do nothing */
1658 }
1659 #endif