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