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