lib/util.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "util.h"
  19 #include <errno.h>
  20 #include <limits.h>
  21 #include <stdarg.h>
  22 #include <stdint.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <sys/stat.h>
  27 #include <unistd.h>
  28 #include "byte-order.h"
  29 #include "coverage.h"
  30 #include "vlog.h"
  31
  32 VLOG_DEFINE_THIS_MODULE(util);
  33
  34 COVERAGE_DEFINE(util_xalloc);
  35
  36 /* argv[0] without directory names. */
  37 const char *program_name;
  38
  39 /* Ordinarily "" but set to "monitor" for a monitor process or "worker" for a
  40  * worker process. */
  41 const char *subprogram_name = "";
  42
  43 /* --version option output. */
  44 static char *program_version;
  45
  46 void
  47 ovs_assert_failure(const char *where, const char *function,
  48                    const char *condition)
  49 {
  50     /* Prevent an infinite loop (or stack overflow) in case VLOG_ABORT happens
  51      * to trigger an assertion failure of its own. */
  52     static int reentry = 0;
  53
  54     switch (reentry++) {
  55     case 0:
  56         VLOG_ABORT("%s: assertion %s failed in %s()",
  57                    where, condition, function);
  58         NOT_REACHED();
  59
  60     case 1:
  61         fprintf(stderr, "%s: assertion %s failed in %s()",
  62                 where, condition, function);
  63         abort();
  64
  65     default:
  66         abort();
  67     }
  68 }
  69
  70 void
  71 out_of_memory(void)
  72 {
  73     ovs_abort(0, "virtual memory exhausted");
  74 }
  75
  76 void *
  77 xcalloc(size_t count, size_t size)
  78 {
  79     void *p = count && size ? calloc(count, size) : malloc(1);
  80     COVERAGE_INC(util_xalloc);
  81     if (p == NULL) {
  82         out_of_memory();
  83     }
  84     return p;
  85 }
  86
  87 void *
  88 xzalloc(size_t size)
  89 {
  90     return xcalloc(1, size);
  91 }
  92
  93 void *
  94 xmalloc(size_t size)
  95 {
  96     void *p = malloc(size ? size : 1);
  97     COVERAGE_INC(util_xalloc);
  98     if (p == NULL) {
  99         out_of_memory();
 100     }
 101     return p;
 102 }
 103
 104 void *
 105 xrealloc(void *p, size_t size)
 106 {
 107     p = realloc(p, size ? size : 1);
 108     COVERAGE_INC(util_xalloc);
 109     if (p == NULL) {
 110         out_of_memory();
 111     }
 112     return p;
 113 }
 114
 115 void *
 116 xmemdup(const void *p_, size_t size)
 117 {
 118     void *p = xmalloc(size);
 119     memcpy(p, p_, size);
 120     return p;
 121 }
 122
 123 char *
 124 xmemdup0(const char *p_, size_t length)
 125 {
 126     char *p = xmalloc(length + 1);
 127     memcpy(p, p_, length);
 128     p[length] = '\0';
 129     return p;
 130 }
 131
 132 char *
 133 xstrdup(const char *s)
 134 {
 135     return xmemdup0(s, strlen(s));
 136 }
 137
 138 char *
 139 xvasprintf(const char *format, va_list args)
 140 {
 141     va_list args2;
 142     size_t needed;
 143     char *s;
 144
 145     va_copy(args2, args);
 146     needed = vsnprintf(NULL, 0, format, args);
 147
 148     s = xmalloc(needed + 1);
 149
 150     vsnprintf(s, needed + 1, format, args2);
 151     va_end(args2);
 152
 153     return s;
 154 }
 155
 156 void *
 157 x2nrealloc(void *p, size_t *n, size_t s)
 158 {
 159     *n = *n == 0 ? 1 : 2 * *n;
 160     return xrealloc(p, *n * s);
 161 }
 162
 163 char *
 164 xasprintf(const char *format, ...)
 165 {
 166     va_list args;
 167     char *s;
 168
 169     va_start(args, format);
 170     s = xvasprintf(format, args);
 171     va_end(args);
 172
 173     return s;
 174 }
 175
 176 /* Similar to strlcpy() from OpenBSD, but it never reads more than 'size - 1'
 177  * bytes from 'src' and doesn't return anything. */
 178 void
 179 ovs_strlcpy(char *dst, const char *src, size_t size)
 180 {
 181     if (size > 0) {
 182         size_t len = strnlen(src, size - 1);
 183         memcpy(dst, src, len);
 184         dst[len] = '\0';
 185     }
 186 }
 187
 188 /* Copies 'src' to 'dst'.  Reads no more than 'size - 1' bytes from 'src'.
 189  * Always null-terminates 'dst' (if 'size' is nonzero), and writes a zero byte
 190  * to every otherwise unused byte in 'dst'.
 191  *
 192  * Except for performance, the following call:
 193  *     ovs_strzcpy(dst, src, size);
 194  * is equivalent to these two calls:
 195  *     memset(dst, '\0', size);
 196  *     ovs_strlcpy(dst, src, size);
 197  *
 198  * (Thus, ovs_strzcpy() is similar to strncpy() without some of the pitfalls.)
 199  */
 200 void
 201 ovs_strzcpy(char *dst, const char *src, size_t size)
 202 {
 203     if (size > 0) {
 204         size_t len = strnlen(src, size - 1);
 205         memcpy(dst, src, len);
 206         memset(dst + len, '\0', size - len);
 207     }
 208 }
 209
 210 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 211  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 212  * the message inside parentheses.  Then, terminates with abort().
 213  *
 214  * This function is preferred to ovs_fatal() in a situation where it would make
 215  * sense for a monitoring process to restart the daemon.
 216  *
 217  * 'format' should not end with a new-line, because this function will add one
 218  * itself. */
 219 void
 220 ovs_abort(int err_no, const char *format, ...)
 221 {
 222     va_list args;
 223
 224     va_start(args, format);
 225     ovs_abort_valist(err_no, format, args);
 226 }
 227
 228 /* Same as ovs_abort() except that the arguments are supplied as a va_list. */
 229 void
 230 ovs_abort_valist(int err_no, const char *format, va_list args)
 231 {
 232     ovs_error_valist(err_no, format, args);
 233     abort();
 234 }
 235
 236 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 237  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 238  * the message inside parentheses.  Then, terminates with EXIT_FAILURE.
 239  *
 240  * 'format' should not end with a new-line, because this function will add one
 241  * itself. */
 242 void
 243 ovs_fatal(int err_no, const char *format, ...)
 244 {
 245     va_list args;
 246
 247     va_start(args, format);
 248     ovs_fatal_valist(err_no, format, args);
 249 }
 250
 251 /* Same as ovs_fatal() except that the arguments are supplied as a va_list. */
 252 void
 253 ovs_fatal_valist(int err_no, const char *format, va_list args)
 254 {
 255     ovs_error_valist(err_no, format, args);
 256     exit(EXIT_FAILURE);
 257 }
 258
 259 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 260  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 261  * the message inside parentheses.
 262  *
 263  * 'format' should not end with a new-line, because this function will add one
 264  * itself. */
 265 void
 266 ovs_error(int err_no, const char *format, ...)
 267 {
 268     va_list args;
 269
 270     va_start(args, format);
 271     ovs_error_valist(err_no, format, args);
 272     va_end(args);
 273 }
 274
 275 /* Same as ovs_error() except that the arguments are supplied as a va_list. */
 276 void
 277 ovs_error_valist(int err_no, const char *format, va_list args)
 278 {
 279     int save_errno = errno;
 280
 281     if (subprogram_name[0]) {
 282         fprintf(stderr, "%s(%s): ", program_name, subprogram_name);
 283     } else {
 284         fprintf(stderr, "%s: ", program_name);
 285     }
 286
 287     vfprintf(stderr, format, args);
 288     if (err_no != 0) {
 289         fprintf(stderr, " (%s)", ovs_retval_to_string(err_no));
 290     }
 291     putc('\n', stderr);
 292
 293     errno = save_errno;
 294 }
 295
 296 /* Many OVS functions return an int which is one of:
 297  * - 0: no error yet
 298  * - >0: errno value
 299  * - EOF: end of file (not necessarily an error; depends on the function called)
 300  *
 301  * Returns the appropriate human-readable string. The caller must copy the
 302  * string if it wants to hold onto it, as the storage may be overwritten on
 303  * subsequent function calls.
 304  */
 305 const char *
 306 ovs_retval_to_string(int retval)
 307 {
 308     static char unknown[48];
 309
 310     if (!retval) {
 311         return "";
 312     }
 313     if (retval > 0) {
 314         return strerror(retval);
 315     }
 316     if (retval == EOF) {
 317         return "End of file";
 318     }
 319     snprintf(unknown, sizeof unknown, "***unknown return value: %d***", retval);
 320     return unknown;
 321 }
 322
 323 /* Sets global "program_name" and "program_version" variables.  Should
 324  * be called at the beginning of main() with "argv[0]" as the argument
 325  * to 'argv0'.
 326  *
 327  * 'version' should contain the version of the caller's program.  If 'version'
 328  * is the same as the VERSION #define, the caller is assumed to be part of Open
 329  * vSwitch.  Otherwise, it is assumed to be an external program linking against
 330  * the Open vSwitch libraries.
 331  *
 332  * The 'date' and 'time' arguments should likely be called with
 333  * "__DATE__" and "__TIME__" to use the time the binary was built.
 334  * Alternatively, the "set_program_name" macro may be called to do this
 335  * automatically.
 336  */
 337 void
 338 set_program_name__(const char *argv0, const char *version, const char *date,
 339                    const char *time)
 340 {
 341     const char *slash = strrchr(argv0, '/');
 342     program_name = slash ? slash + 1 : argv0;
 343
 344     free(program_version);
 345
 346     if (!strcmp(version, VERSION)) {
 347         program_version = xasprintf("%s (Open vSwitch) "VERSION"\n"
 348                                     "Compiled %s %s\n",
 349                                     program_name, date, time);
 350     } else {
 351         program_version = xasprintf("%s %s\n"
 352                                     "Open vSwitch Library "VERSION"\n"
 353                                     "Compiled %s %s\n",
 354                                     program_name, version, date, time);
 355     }
 356 }
 357
 358 /* Returns a pointer to a string describing the program version.  The
 359  * caller must not modify or free the returned string.
 360  */
 361 const char *
 362 get_program_version(void)
 363 {
 364     return program_version;
 365 }
 366
 367 /* Print the version information for the program.  */
 368 void
 369 ovs_print_version(uint8_t min_ofp, uint8_t max_ofp)
 370 {
 371     printf("%s", program_version);
 372     if (min_ofp || max_ofp) {
 373         printf("OpenFlow versions %#x:%#x\n", min_ofp, max_ofp);
 374     }
 375 }
 376
 377 /* Writes the 'size' bytes in 'buf' to 'stream' as hex bytes arranged 16 per
 378  * line.  Numeric offsets are also included, starting at 'ofs' for the first
 379  * byte in 'buf'.  If 'ascii' is true then the corresponding ASCII characters
 380  * are also rendered alongside. */
 381 void
 382 ovs_hex_dump(FILE *stream, const void *buf_, size_t size,
 383              uintptr_t ofs, bool ascii)
 384 {
 385   const uint8_t *buf = buf_;
 386   const size_t per_line = 16; /* Maximum bytes per line. */
 387
 388   while (size > 0)
 389     {
 390       size_t start, end, n;
 391       size_t i;
 392
 393       /* Number of bytes on this line. */
 394       start = ofs % per_line;
 395       end = per_line;
 396       if (end - start > size)
 397         end = start + size;
 398       n = end - start;
 399
 400       /* Print line. */
 401       fprintf(stream, "%08jx  ", (uintmax_t) ROUND_DOWN(ofs, per_line));
 402       for (i = 0; i < start; i++)
 403         fprintf(stream, "   ");
 404       for (; i < end; i++)
 405         fprintf(stream, "%02hhx%c",
 406                 buf[i - start], i == per_line / 2 - 1? '-' : ' ');
 407       if (ascii)
 408         {
 409           for (; i < per_line; i++)
 410             fprintf(stream, "   ");
 411           fprintf(stream, "|");
 412           for (i = 0; i < start; i++)
 413             fprintf(stream, " ");
 414           for (; i < end; i++) {
 415               int c = buf[i - start];
 416               putc(c >= 32 && c < 127 ? c : '.', stream);
 417           }
 418           for (; i < per_line; i++)
 419             fprintf(stream, " ");
 420           fprintf(stream, "|");
 421         }
 422       fprintf(stream, "\n");
 423
 424       ofs += n;
 425       buf += n;
 426       size -= n;
 427     }
 428 }
 429
 430 bool
 431 str_to_int(const char *s, int base, int *i)
 432 {
 433     long long ll;
 434     bool ok = str_to_llong(s, base, &ll);
 435     *i = ll;
 436     return ok;
 437 }
 438
 439 bool
 440 str_to_long(const char *s, int base, long *li)
 441 {
 442     long long ll;
 443     bool ok = str_to_llong(s, base, &ll);
 444     *li = ll;
 445     return ok;
 446 }
 447
 448 bool
 449 str_to_llong(const char *s, int base, long long *x)
 450 {
 451     int save_errno = errno;
 452     char *tail;
 453     errno = 0;
 454     *x = strtoll(s, &tail, base);
 455     if (errno == EINVAL || errno == ERANGE || tail == s || *tail != '\0') {
 456         errno = save_errno;
 457         *x = 0;
 458         return false;
 459     } else {
 460         errno = save_errno;
 461         return true;
 462     }
 463 }
 464
 465 bool
 466 str_to_uint(const char *s, int base, unsigned int *u)
 467 {
 468     return str_to_int(s, base, (int *) u);
 469 }
 470
 471 bool
 472 str_to_ulong(const char *s, int base, unsigned long *ul)
 473 {
 474     return str_to_long(s, base, (long *) ul);
 475 }
 476
 477 bool
 478 str_to_ullong(const char *s, int base, unsigned long long *ull)
 479 {
 480     return str_to_llong(s, base, (long long *) ull);
 481 }
 482
 483 /* Converts floating-point string 's' into a double.  If successful, stores
 484  * the double in '*d' and returns true; on failure, stores 0 in '*d' and
 485  * returns false.
 486  *
 487  * Underflow (e.g. "1e-9999") is not considered an error, but overflow
 488  * (e.g. "1e9999)" is. */
 489 bool
 490 str_to_double(const char *s, double *d)
 491 {
 492     int save_errno = errno;
 493     char *tail;
 494     errno = 0;
 495     *d = strtod(s, &tail);
 496     if (errno == EINVAL || (errno == ERANGE && *d != 0)
 497         || tail == s || *tail != '\0') {
 498         errno = save_errno;
 499         *d = 0;
 500         return false;
 501     } else {
 502         errno = save_errno;
 503         return true;
 504     }
 505 }
 506
 507 /* Returns the value of 'c' as a hexadecimal digit. */
 508 int
 509 hexit_value(int c)
 510 {
 511     switch (c) {
 512     case '0': case '1': case '2': case '3': case '4':
 513     case '5': case '6': case '7': case '8': case '9':
 514         return c - '0';
 515
 516     case 'a': case 'A':
 517         return 0xa;
 518
 519     case 'b': case 'B':
 520         return 0xb;
 521
 522     case 'c': case 'C':
 523         return 0xc;
 524
 525     case 'd': case 'D':
 526         return 0xd;
 527
 528     case 'e': case 'E':
 529         return 0xe;
 530
 531     case 'f': case 'F':
 532         return 0xf;
 533
 534     default:
 535         return -1;
 536     }
 537 }
 538
 539 /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
 540  * UINT_MAX if one of those "digits" is not really a hex digit.  If 'ok' is
 541  * nonnull, '*ok' is set to true if the conversion succeeds or to false if a
 542  * non-hex digit is detected. */
 543 unsigned int
 544 hexits_value(const char *s, size_t n, bool *ok)
 545 {
 546     unsigned int value;
 547     size_t i;
 548
 549     value = 0;
 550     for (i = 0; i < n; i++) {
 551         int hexit = hexit_value(s[i]);
 552         if (hexit < 0) {
 553             if (ok) {
 554                 *ok = false;
 555             }
 556             return UINT_MAX;
 557         }
 558         value = (value << 4) + hexit;
 559     }
 560     if (ok) {
 561         *ok = true;
 562     }
 563     return value;
 564 }
 565
 566 /* Returns the current working directory as a malloc()'d string, or a null
 567  * pointer if the current working directory cannot be determined. */
 568 char *
 569 get_cwd(void)
 570 {
 571     long int path_max;
 572     size_t size;
 573
 574     /* Get maximum path length or at least a reasonable estimate. */
 575     path_max = pathconf(".", _PC_PATH_MAX);
 576     size = (path_max < 0 ? 1024
 577             : path_max > 10240 ? 10240
 578             : path_max);
 579
 580     /* Get current working directory. */
 581     for (;;) {
 582         char *buf = xmalloc(size);
 583         if (getcwd(buf, size)) {
 584             return xrealloc(buf, strlen(buf) + 1);
 585         } else {
 586             int error = errno;
 587             free(buf);
 588             if (error != ERANGE) {
 589                 VLOG_WARN("getcwd failed (%s)", strerror(error));
 590                 return NULL;
 591             }
 592             size *= 2;
 593         }
 594     }
 595 }
 596
 597 static char *
 598 all_slashes_name(const char *s)
 599 {
 600     return xstrdup(s[0] == '/' && s[1] == '/' && s[2] != '/' ? "//"
 601                    : s[0] == '/' ? "/"
 602                    : ".");
 603 }
 604
 605 /* Returns the directory name portion of 'file_name' as a malloc()'d string,
 606  * similar to the POSIX dirname() function but thread-safe. */
 607 char *
 608 dir_name(const char *file_name)
 609 {
 610     size_t len = strlen(file_name);
 611     while (len > 0 && file_name[len - 1] == '/') {
 612         len--;
 613     }
 614     while (len > 0 && file_name[len - 1] != '/') {
 615         len--;
 616     }
 617     while (len > 0 && file_name[len - 1] == '/') {
 618         len--;
 619     }
 620     return len ? xmemdup0(file_name, len) : all_slashes_name(file_name);
 621 }
 622
 623 /* Returns the file name portion of 'file_name' as a malloc()'d string,
 624  * similar to the POSIX basename() function but thread-safe. */
 625 char *
 626 base_name(const char *file_name)
 627 {
 628     size_t end, start;
 629
 630     end = strlen(file_name);
 631     while (end > 0 && file_name[end - 1] == '/') {
 632         end--;
 633     }
 634
 635     if (!end) {
 636         return all_slashes_name(file_name);
 637     }
 638
 639     start = end;
 640     while (start > 0 && file_name[start - 1] != '/') {
 641         start--;
 642     }
 643
 644     return xmemdup0(file_name + start, end - start);
 645 }
 646
 647 /* If 'file_name' starts with '/', returns a copy of 'file_name'.  Otherwise,
 648  * returns an absolute path to 'file_name' considering it relative to 'dir',
 649  * which itself must be absolute.  'dir' may be null or the empty string, in
 650  * which case the current working directory is used.
 651  *
 652  * Returns a null pointer if 'dir' is null and getcwd() fails. */
 653 char *
 654 abs_file_name(const char *dir, const char *file_name)
 655 {
 656     if (file_name[0] == '/') {
 657         return xstrdup(file_name);
 658     } else if (dir && dir[0]) {
 659         char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
 660         return xasprintf("%s%s%s", dir, separator, file_name);
 661     } else {
 662         char *cwd = get_cwd();
 663         if (cwd) {
 664             char *abs_name = xasprintf("%s/%s", cwd, file_name);
 665             free(cwd);
 666             return abs_name;
 667         } else {
 668             return NULL;
 669         }
 670     }
 671 }
 672
 673 /* Like readlink(), but returns the link name as a null-terminated string in
 674  * allocated memory that the caller must eventually free (with free()).
 675  * Returns NULL on error, in which case errno is set appropriately. */
 676 char *
 677 xreadlink(const char *filename)
 678 {
 679     size_t size;
 680
 681     for (size = 64; ; size *= 2) {
 682         char *buf = xmalloc(size);
 683         ssize_t retval = readlink(filename, buf, size);
 684         int error = errno;
 685
 686         if (retval >= 0 && retval < size) {
 687             buf[retval] = '\0';
 688             return buf;
 689         }
 690
 691         free(buf);
 692         if (retval < 0) {
 693             errno = error;
 694             return NULL;
 695         }
 696     }
 697 }
 698
 699 /* Returns a version of 'filename' with symlinks in the final component
 700  * dereferenced.  This differs from realpath() in that:
 701  *
 702  *     - 'filename' need not exist.
 703  *
 704  *     - If 'filename' does exist as a symlink, its referent need not exist.
 705  *
 706  *     - Only symlinks in the final component of 'filename' are dereferenced.
 707  *
 708  * The caller must eventually free the returned string (with free()). */
 709 char *
 710 follow_symlinks(const char *filename)
 711 {
 712     struct stat s;
 713     char *fn;
 714     int i;
 715
 716     fn = xstrdup(filename);
 717     for (i = 0; i < 10; i++) {
 718         char *linkname;
 719         char *next_fn;
 720
 721         if (lstat(fn, &s) != 0 || !S_ISLNK(s.st_mode)) {
 722             return fn;
 723         }
 724
 725         linkname = xreadlink(fn);
 726         if (!linkname) {
 727             VLOG_WARN("%s: readlink failed (%s)", filename, strerror(errno));
 728             return fn;
 729         }
 730
 731         if (linkname[0] == '/') {
 732             /* Target of symlink is absolute so use it raw. */
 733             next_fn = linkname;
 734         } else {
 735             /* Target of symlink is relative so add to 'fn''s directory. */
 736             char *dir = dir_name(fn);
 737
 738             if (!strcmp(dir, ".")) {
 739                 next_fn = linkname;
 740             } else {
 741                 char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
 742                 next_fn = xasprintf("%s%s%s", dir, separator, linkname);
 743                 free(linkname);
 744             }
 745
 746             free(dir);
 747         }
 748
 749         free(fn);
 750         fn = next_fn;
 751     }
 752
 753     VLOG_WARN("%s: too many levels of symlinks", filename);
 754     free(fn);
 755     return xstrdup(filename);
 756 }
 757
 758 /* Pass a value to this function if it is marked with
 759  * __attribute__((warn_unused_result)) and you genuinely want to ignore
 760  * its return value.  (Note that every scalar type can be implicitly
 761  * converted to bool.) */
 762 void ignore(bool x OVS_UNUSED) { }
 763
 764 /* Returns an appropriate delimiter for inserting just before the 0-based item
 765  * 'index' in a list that has 'total' items in it. */
 766 const char *
 767 english_list_delimiter(size_t index, size_t total)
 768 {
 769     return (index == 0 ? ""
 770             : index < total - 1 ? ", "
 771             : total > 2 ? ", and "
 772             : " and ");
 773 }
 774
 775 /* Given a 32 bit word 'n', calculates floor(log_2('n')).  This is equivalent
 776  * to finding the bit position of the most significant one bit in 'n'.  It is
 777  * an error to call this function with 'n' == 0. */
 778 int
 779 log_2_floor(uint32_t n)
 780 {
 781     ovs_assert(n);
 782
 783 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 784 #error "Someone screwed up the #includes."
 785 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 786     return 31 - __builtin_clz(n);
 787 #else
 788     {
 789         int log = 0;
 790
 791 #define BIN_SEARCH_STEP(BITS)                   \
 792         if (n >= (1 << BITS)) {                 \
 793             log += BITS;                        \
 794             n >>= BITS;                         \
 795         }
 796         BIN_SEARCH_STEP(16);
 797         BIN_SEARCH_STEP(8);
 798         BIN_SEARCH_STEP(4);
 799         BIN_SEARCH_STEP(2);
 800         BIN_SEARCH_STEP(1);
 801 #undef BIN_SEARCH_STEP
 802         return log;
 803     }
 804 #endif
 805 }
 806
 807 /* Given a 32 bit word 'n', calculates ceil(log_2('n')).  It is an error to
 808  * call this function with 'n' == 0. */
 809 int
 810 log_2_ceil(uint32_t n)
 811 {
 812     return log_2_floor(n) + !is_pow2(n);
 813 }
 814
 815 /* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
 816 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 817 #error "Someone screwed up the #includes."
 818 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 819 /* Defined inline in util.h. */
 820 #else
 821 static int
 822 raw_ctz(uint32_t n)
 823 {
 824     unsigned int k;
 825     int count = 31;
 826
 827 #define CTZ_STEP(X)                             \
 828     k = n << (X);                               \
 829     if (k) {                                    \
 830         count -= X;                             \
 831         n = k;                                  \
 832     }
 833     CTZ_STEP(16);
 834     CTZ_STEP(8);
 835     CTZ_STEP(4);
 836     CTZ_STEP(2);
 837     CTZ_STEP(1);
 838 #undef CTZ_STEP
 839
 840     return count;
 841 }
 842 #endif
 843
 844 /* Returns the number of 1-bits in 'x', between 0 and 32 inclusive. */
 845 unsigned int
 846 popcount(uint32_t x)
 847 {
 848     /* In my testing, this implementation is over twice as fast as any other
 849      * portable implementation that I tried, including GCC 4.4
 850      * __builtin_popcount(), although nonportable asm("popcnt") was over 50%
 851      * faster. */
 852 #define INIT1(X)                                \
 853     ((((X) & (1 << 0)) != 0) +                  \
 854      (((X) & (1 << 1)) != 0) +                  \
 855      (((X) & (1 << 2)) != 0) +                  \
 856      (((X) & (1 << 3)) != 0) +                  \
 857      (((X) & (1 << 4)) != 0) +                  \
 858      (((X) & (1 << 5)) != 0) +                  \
 859      (((X) & (1 << 6)) != 0) +                  \
 860      (((X) & (1 << 7)) != 0))
 861 #define INIT2(X)   INIT1(X),  INIT1((X) +  1)
 862 #define INIT4(X)   INIT2(X),  INIT2((X) +  2)
 863 #define INIT8(X)   INIT4(X),  INIT4((X) +  4)
 864 #define INIT16(X)  INIT8(X),  INIT8((X) +  8)
 865 #define INIT32(X) INIT16(X), INIT16((X) + 16)
 866 #define INIT64(X) INIT32(X), INIT32((X) + 32)
 867
 868     static const uint8_t popcount8[256] = {
 869         INIT64(0), INIT64(64), INIT64(128), INIT64(192)
 870     };
 871
 872     return (popcount8[x & 0xff] +
 873             popcount8[(x >> 8) & 0xff] +
 874             popcount8[(x >> 16) & 0xff] +
 875             popcount8[x >> 24]);
 876 }
 877
 878 /* Returns true if the 'n' bytes starting at 'p' are zeros. */
 879 bool
 880 is_all_zeros(const uint8_t *p, size_t n)
 881 {
 882     size_t i;
 883
 884     for (i = 0; i < n; i++) {
 885         if (p[i] != 0x00) {
 886             return false;
 887         }
 888     }
 889     return true;
 890 }
 891
 892 /* Returns true if the 'n' bytes starting at 'p' are 0xff. */
 893 bool
 894 is_all_ones(const uint8_t *p, size_t n)
 895 {
 896     size_t i;
 897
 898     for (i = 0; i < n; i++) {
 899         if (p[i] != 0xff) {
 900             return false;
 901         }
 902     }
 903     return true;
 904 }
 905
 906 /* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
 907  * starting from bit 'dst_ofs' in 'dst'.  'src' is 'src_len' bytes long and
 908  * 'dst' is 'dst_len' bytes long.
 909  *
 910  * If you consider all of 'src' to be a single unsigned integer in network byte
 911  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 912  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
 913  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
 914  * 2], and so on.  Similarly for 'dst'.
 915  *
 916  * Required invariants:
 917  *   src_ofs + n_bits <= src_len * 8
 918  *   dst_ofs + n_bits <= dst_len * 8
 919  *   'src' and 'dst' must not overlap.
 920  */
 921 void
 922 bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
 923              void *dst_, unsigned int dst_len, unsigned int dst_ofs,
 924              unsigned int n_bits)
 925 {
 926     const uint8_t *src = src_;
 927     uint8_t *dst = dst_;
 928
 929     src += src_len - (src_ofs / 8 + 1);
 930     src_ofs %= 8;
 931
 932     dst += dst_len - (dst_ofs / 8 + 1);
 933     dst_ofs %= 8;
 934
 935     if (src_ofs == 0 && dst_ofs == 0) {
 936         unsigned int n_bytes = n_bits / 8;
 937         if (n_bytes) {
 938             dst -= n_bytes - 1;
 939             src -= n_bytes - 1;
 940             memcpy(dst, src, n_bytes);
 941
 942             n_bits %= 8;
 943             src--;
 944             dst--;
 945         }
 946         if (n_bits) {
 947             uint8_t mask = (1 << n_bits) - 1;
 948             *dst = (*dst & ~mask) | (*src & mask);
 949         }
 950     } else {
 951         while (n_bits > 0) {
 952             unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
 953             unsigned int chunk = MIN(n_bits, max_copy);
 954             uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
 955
 956             *dst &= ~mask;
 957             *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
 958
 959             src_ofs += chunk;
 960             if (src_ofs == 8) {
 961                 src--;
 962                 src_ofs = 0;
 963             }
 964             dst_ofs += chunk;
 965             if (dst_ofs == 8) {
 966                 dst--;
 967                 dst_ofs = 0;
 968             }
 969             n_bits -= chunk;
 970         }
 971     }
 972 }
 973
 974 /* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.  'dst' is
 975  * 'dst_len' bytes long.
 976  *
 977  * If you consider all of 'dst' to be a single unsigned integer in network byte
 978  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 979  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 980  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 981  * 2], and so on.
 982  *
 983  * Required invariant:
 984  *   dst_ofs + n_bits <= dst_len * 8
 985  */
 986 void
 987 bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 988              unsigned int n_bits)
 989 {
 990     uint8_t *dst = dst_;
 991
 992     if (!n_bits) {
 993         return;
 994     }
 995
 996     dst += dst_len - (dst_ofs / 8 + 1);
 997     dst_ofs %= 8;
 998
 999     if (dst_ofs) {
1000         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
1001
1002         *dst &= ~(((1 << chunk) - 1) << dst_ofs);
1003
1004         n_bits -= chunk;
1005         if (!n_bits) {
1006             return;
1007         }
1008
1009         dst--;
1010     }
1011
1012     while (n_bits >= 8) {
1013         *dst-- = 0;
1014         n_bits -= 8;
1015     }
1016
1017     if (n_bits) {
1018         *dst &= ~((1 << n_bits) - 1);
1019     }
1020 }
1021
1022 /* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
1023  * 'dst' is 'dst_len' bytes long.
1024  *
1025  * If you consider all of 'dst' to be a single unsigned integer in network byte
1026  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1027  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1028  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1029  * 2], and so on.
1030  *
1031  * Required invariant:
1032  *   dst_ofs + n_bits <= dst_len * 8
1033  */
1034 void
1035 bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
1036             unsigned int n_bits)
1037 {
1038     uint8_t *dst = dst_;
1039
1040     if (!n_bits) {
1041         return;
1042     }
1043
1044     dst += dst_len - (dst_ofs / 8 + 1);
1045     dst_ofs %= 8;
1046
1047     if (dst_ofs) {
1048         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
1049
1050         *dst |= ((1 << chunk) - 1) << dst_ofs;
1051
1052         n_bits -= chunk;
1053         if (!n_bits) {
1054             return;
1055         }
1056
1057         dst--;
1058     }
1059
1060     while (n_bits >= 8) {
1061         *dst-- = 0xff;
1062         n_bits -= 8;
1063     }
1064
1065     if (n_bits) {
1066         *dst |= (1 << n_bits) - 1;
1067     }
1068 }
1069
1070 /* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
1071  * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_len'
1072  * bytes long.
1073  *
1074  * If you consider all of 'dst' to be a single unsigned integer in network byte
1075  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1076  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1077  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1078  * 2], and so on.
1079  *
1080  * Required invariant:
1081  *   dst_ofs + n_bits <= dst_len * 8
1082  */
1083 bool
1084 bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
1085                      unsigned int n_bits)
1086 {
1087     const uint8_t *p = p_;
1088
1089     if (!n_bits) {
1090         return true;
1091     }
1092
1093     p += len - (ofs / 8 + 1);
1094     ofs %= 8;
1095
1096     if (ofs) {
1097         unsigned int chunk = MIN(n_bits, 8 - ofs);
1098
1099         if (*p & (((1 << chunk) - 1) << ofs)) {
1100             return false;
1101         }
1102
1103         n_bits -= chunk;
1104         if (!n_bits) {
1105             return true;
1106         }
1107
1108         p--;
1109     }
1110
1111     while (n_bits >= 8) {
1112         if (*p) {
1113             return false;
1114         }
1115         n_bits -= 8;
1116         p--;
1117     }
1118
1119     if (n_bits && *p & ((1 << n_bits) - 1)) {
1120         return false;
1121     }
1122
1123     return true;
1124 }
1125
1126 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
1127  * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
1128  *
1129  * If you consider all of 'dst' to be a single unsigned integer in network byte
1130  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1131  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1132  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1133  * 2], and so on.
1134  *
1135  * Required invariants:
1136  *   dst_ofs + n_bits <= dst_len * 8
1137  *   n_bits <= 64
1138  */
1139 void
1140 bitwise_put(uint64_t value,
1141             void *dst, unsigned int dst_len, unsigned int dst_ofs,
1142             unsigned int n_bits)
1143 {
1144     ovs_be64 n_value = htonll(value);
1145     bitwise_copy(&n_value, sizeof n_value, 0,
1146                  dst, dst_len, dst_ofs,
1147                  n_bits);
1148 }
1149
1150 /* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
1151  * which is 'src_len' bytes long.
1152  *
1153  * If you consider all of 'src' to be a single unsigned integer in network byte
1154  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1155  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1156  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1157  * 2], and so on.
1158  *
1159  * Required invariants:
1160  *   src_ofs + n_bits <= src_len * 8
1161  *   n_bits <= 64
1162  */
1163 uint64_t
1164 bitwise_get(const void *src, unsigned int src_len,
1165             unsigned int src_ofs, unsigned int n_bits)
1166 {
1167     ovs_be64 value = htonll(0);
1168
1169     bitwise_copy(src, src_len, src_ofs,
1170                  &value, sizeof value, 0,
1171                  n_bits);
1172     return ntohll(value);
1173 }