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 "ovs-thread.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
 344     assert_single_threaded();
 345
 346     program_name = slash ? slash + 1 : argv0;
 347
 348     free(program_version);
 349
 350     if (!strcmp(version, VERSION)) {
 351         program_version = xasprintf("%s (Open vSwitch) "VERSION"\n"
 352                                     "Compiled %s %s\n",
 353                                     program_name, date, time);
 354     } else {
 355         program_version = xasprintf("%s %s\n"
 356                                     "Open vSwitch Library "VERSION"\n"
 357                                     "Compiled %s %s\n",
 358                                     program_name, version, date, time);
 359     }
 360 }
 361
 362 /* Returns a pointer to a string describing the program version.  The
 363  * caller must not modify or free the returned string.
 364  */
 365 const char *
 366 get_program_version(void)
 367 {
 368     return program_version;
 369 }
 370
 371 /* Print the version information for the program.  */
 372 void
 373 ovs_print_version(uint8_t min_ofp, uint8_t max_ofp)
 374 {
 375     printf("%s", program_version);
 376     if (min_ofp || max_ofp) {
 377         printf("OpenFlow versions %#x:%#x\n", min_ofp, max_ofp);
 378     }
 379 }
 380
 381 /* Writes the 'size' bytes in 'buf' to 'stream' as hex bytes arranged 16 per
 382  * line.  Numeric offsets are also included, starting at 'ofs' for the first
 383  * byte in 'buf'.  If 'ascii' is true then the corresponding ASCII characters
 384  * are also rendered alongside. */
 385 void
 386 ovs_hex_dump(FILE *stream, const void *buf_, size_t size,
 387              uintptr_t ofs, bool ascii)
 388 {
 389   const uint8_t *buf = buf_;
 390   const size_t per_line = 16; /* Maximum bytes per line. */
 391
 392   while (size > 0)
 393     {
 394       size_t start, end, n;
 395       size_t i;
 396
 397       /* Number of bytes on this line. */
 398       start = ofs % per_line;
 399       end = per_line;
 400       if (end - start > size)
 401         end = start + size;
 402       n = end - start;
 403
 404       /* Print line. */
 405       fprintf(stream, "%08jx  ", (uintmax_t) ROUND_DOWN(ofs, per_line));
 406       for (i = 0; i < start; i++)
 407         fprintf(stream, "   ");
 408       for (; i < end; i++)
 409         fprintf(stream, "%02hhx%c",
 410                 buf[i - start], i == per_line / 2 - 1? '-' : ' ');
 411       if (ascii)
 412         {
 413           for (; i < per_line; i++)
 414             fprintf(stream, "   ");
 415           fprintf(stream, "|");
 416           for (i = 0; i < start; i++)
 417             fprintf(stream, " ");
 418           for (; i < end; i++) {
 419               int c = buf[i - start];
 420               putc(c >= 32 && c < 127 ? c : '.', stream);
 421           }
 422           for (; i < per_line; i++)
 423             fprintf(stream, " ");
 424           fprintf(stream, "|");
 425         }
 426       fprintf(stream, "\n");
 427
 428       ofs += n;
 429       buf += n;
 430       size -= n;
 431     }
 432 }
 433
 434 bool
 435 str_to_int(const char *s, int base, int *i)
 436 {
 437     long long ll;
 438     bool ok = str_to_llong(s, base, &ll);
 439     *i = ll;
 440     return ok;
 441 }
 442
 443 bool
 444 str_to_long(const char *s, int base, long *li)
 445 {
 446     long long ll;
 447     bool ok = str_to_llong(s, base, &ll);
 448     *li = ll;
 449     return ok;
 450 }
 451
 452 bool
 453 str_to_llong(const char *s, int base, long long *x)
 454 {
 455     int save_errno = errno;
 456     char *tail;
 457     errno = 0;
 458     *x = strtoll(s, &tail, base);
 459     if (errno == EINVAL || errno == ERANGE || tail == s || *tail != '\0') {
 460         errno = save_errno;
 461         *x = 0;
 462         return false;
 463     } else {
 464         errno = save_errno;
 465         return true;
 466     }
 467 }
 468
 469 bool
 470 str_to_uint(const char *s, int base, unsigned int *u)
 471 {
 472     return str_to_int(s, base, (int *) u);
 473 }
 474
 475 bool
 476 str_to_ulong(const char *s, int base, unsigned long *ul)
 477 {
 478     return str_to_long(s, base, (long *) ul);
 479 }
 480
 481 bool
 482 str_to_ullong(const char *s, int base, unsigned long long *ull)
 483 {
 484     return str_to_llong(s, base, (long long *) ull);
 485 }
 486
 487 /* Converts floating-point string 's' into a double.  If successful, stores
 488  * the double in '*d' and returns true; on failure, stores 0 in '*d' and
 489  * returns false.
 490  *
 491  * Underflow (e.g. "1e-9999") is not considered an error, but overflow
 492  * (e.g. "1e9999)" is. */
 493 bool
 494 str_to_double(const char *s, double *d)
 495 {
 496     int save_errno = errno;
 497     char *tail;
 498     errno = 0;
 499     *d = strtod(s, &tail);
 500     if (errno == EINVAL || (errno == ERANGE && *d != 0)
 501         || tail == s || *tail != '\0') {
 502         errno = save_errno;
 503         *d = 0;
 504         return false;
 505     } else {
 506         errno = save_errno;
 507         return true;
 508     }
 509 }
 510
 511 /* Returns the value of 'c' as a hexadecimal digit. */
 512 int
 513 hexit_value(int c)
 514 {
 515     switch (c) {
 516     case '0': case '1': case '2': case '3': case '4':
 517     case '5': case '6': case '7': case '8': case '9':
 518         return c - '0';
 519
 520     case 'a': case 'A':
 521         return 0xa;
 522
 523     case 'b': case 'B':
 524         return 0xb;
 525
 526     case 'c': case 'C':
 527         return 0xc;
 528
 529     case 'd': case 'D':
 530         return 0xd;
 531
 532     case 'e': case 'E':
 533         return 0xe;
 534
 535     case 'f': case 'F':
 536         return 0xf;
 537
 538     default:
 539         return -1;
 540     }
 541 }
 542
 543 /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
 544  * UINT_MAX if one of those "digits" is not really a hex digit.  If 'ok' is
 545  * nonnull, '*ok' is set to true if the conversion succeeds or to false if a
 546  * non-hex digit is detected. */
 547 unsigned int
 548 hexits_value(const char *s, size_t n, bool *ok)
 549 {
 550     unsigned int value;
 551     size_t i;
 552
 553     value = 0;
 554     for (i = 0; i < n; i++) {
 555         int hexit = hexit_value(s[i]);
 556         if (hexit < 0) {
 557             if (ok) {
 558                 *ok = false;
 559             }
 560             return UINT_MAX;
 561         }
 562         value = (value << 4) + hexit;
 563     }
 564     if (ok) {
 565         *ok = true;
 566     }
 567     return value;
 568 }
 569
 570 /* Returns the current working directory as a malloc()'d string, or a null
 571  * pointer if the current working directory cannot be determined. */
 572 char *
 573 get_cwd(void)
 574 {
 575     long int path_max;
 576     size_t size;
 577
 578     /* Get maximum path length or at least a reasonable estimate. */
 579     path_max = pathconf(".", _PC_PATH_MAX);
 580     size = (path_max < 0 ? 1024
 581             : path_max > 10240 ? 10240
 582             : path_max);
 583
 584     /* Get current working directory. */
 585     for (;;) {
 586         char *buf = xmalloc(size);
 587         if (getcwd(buf, size)) {
 588             return xrealloc(buf, strlen(buf) + 1);
 589         } else {
 590             int error = errno;
 591             free(buf);
 592             if (error != ERANGE) {
 593                 VLOG_WARN("getcwd failed (%s)", strerror(error));
 594                 return NULL;
 595             }
 596             size *= 2;
 597         }
 598     }
 599 }
 600
 601 static char *
 602 all_slashes_name(const char *s)
 603 {
 604     return xstrdup(s[0] == '/' && s[1] == '/' && s[2] != '/' ? "//"
 605                    : s[0] == '/' ? "/"
 606                    : ".");
 607 }
 608
 609 /* Returns the directory name portion of 'file_name' as a malloc()'d string,
 610  * similar to the POSIX dirname() function but thread-safe. */
 611 char *
 612 dir_name(const char *file_name)
 613 {
 614     size_t len = strlen(file_name);
 615     while (len > 0 && file_name[len - 1] == '/') {
 616         len--;
 617     }
 618     while (len > 0 && file_name[len - 1] != '/') {
 619         len--;
 620     }
 621     while (len > 0 && file_name[len - 1] == '/') {
 622         len--;
 623     }
 624     return len ? xmemdup0(file_name, len) : all_slashes_name(file_name);
 625 }
 626
 627 /* Returns the file name portion of 'file_name' as a malloc()'d string,
 628  * similar to the POSIX basename() function but thread-safe. */
 629 char *
 630 base_name(const char *file_name)
 631 {
 632     size_t end, start;
 633
 634     end = strlen(file_name);
 635     while (end > 0 && file_name[end - 1] == '/') {
 636         end--;
 637     }
 638
 639     if (!end) {
 640         return all_slashes_name(file_name);
 641     }
 642
 643     start = end;
 644     while (start > 0 && file_name[start - 1] != '/') {
 645         start--;
 646     }
 647
 648     return xmemdup0(file_name + start, end - start);
 649 }
 650
 651 /* If 'file_name' starts with '/', returns a copy of 'file_name'.  Otherwise,
 652  * returns an absolute path to 'file_name' considering it relative to 'dir',
 653  * which itself must be absolute.  'dir' may be null or the empty string, in
 654  * which case the current working directory is used.
 655  *
 656  * Returns a null pointer if 'dir' is null and getcwd() fails. */
 657 char *
 658 abs_file_name(const char *dir, const char *file_name)
 659 {
 660     if (file_name[0] == '/') {
 661         return xstrdup(file_name);
 662     } else if (dir && dir[0]) {
 663         char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
 664         return xasprintf("%s%s%s", dir, separator, file_name);
 665     } else {
 666         char *cwd = get_cwd();
 667         if (cwd) {
 668             char *abs_name = xasprintf("%s/%s", cwd, file_name);
 669             free(cwd);
 670             return abs_name;
 671         } else {
 672             return NULL;
 673         }
 674     }
 675 }
 676
 677 /* Like readlink(), but returns the link name as a null-terminated string in
 678  * allocated memory that the caller must eventually free (with free()).
 679  * Returns NULL on error, in which case errno is set appropriately. */
 680 char *
 681 xreadlink(const char *filename)
 682 {
 683     size_t size;
 684
 685     for (size = 64; ; size *= 2) {
 686         char *buf = xmalloc(size);
 687         ssize_t retval = readlink(filename, buf, size);
 688         int error = errno;
 689
 690         if (retval >= 0 && retval < size) {
 691             buf[retval] = '\0';
 692             return buf;
 693         }
 694
 695         free(buf);
 696         if (retval < 0) {
 697             errno = error;
 698             return NULL;
 699         }
 700     }
 701 }
 702
 703 /* Returns a version of 'filename' with symlinks in the final component
 704  * dereferenced.  This differs from realpath() in that:
 705  *
 706  *     - 'filename' need not exist.
 707  *
 708  *     - If 'filename' does exist as a symlink, its referent need not exist.
 709  *
 710  *     - Only symlinks in the final component of 'filename' are dereferenced.
 711  *
 712  * The caller must eventually free the returned string (with free()). */
 713 char *
 714 follow_symlinks(const char *filename)
 715 {
 716     struct stat s;
 717     char *fn;
 718     int i;
 719
 720     fn = xstrdup(filename);
 721     for (i = 0; i < 10; i++) {
 722         char *linkname;
 723         char *next_fn;
 724
 725         if (lstat(fn, &s) != 0 || !S_ISLNK(s.st_mode)) {
 726             return fn;
 727         }
 728
 729         linkname = xreadlink(fn);
 730         if (!linkname) {
 731             VLOG_WARN("%s: readlink failed (%s)", filename, strerror(errno));
 732             return fn;
 733         }
 734
 735         if (linkname[0] == '/') {
 736             /* Target of symlink is absolute so use it raw. */
 737             next_fn = linkname;
 738         } else {
 739             /* Target of symlink is relative so add to 'fn''s directory. */
 740             char *dir = dir_name(fn);
 741
 742             if (!strcmp(dir, ".")) {
 743                 next_fn = linkname;
 744             } else {
 745                 char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
 746                 next_fn = xasprintf("%s%s%s", dir, separator, linkname);
 747                 free(linkname);
 748             }
 749
 750             free(dir);
 751         }
 752
 753         free(fn);
 754         fn = next_fn;
 755     }
 756
 757     VLOG_WARN("%s: too many levels of symlinks", filename);
 758     free(fn);
 759     return xstrdup(filename);
 760 }
 761
 762 /* Pass a value to this function if it is marked with
 763  * __attribute__((warn_unused_result)) and you genuinely want to ignore
 764  * its return value.  (Note that every scalar type can be implicitly
 765  * converted to bool.) */
 766 void ignore(bool x OVS_UNUSED) { }
 767
 768 /* Returns an appropriate delimiter for inserting just before the 0-based item
 769  * 'index' in a list that has 'total' items in it. */
 770 const char *
 771 english_list_delimiter(size_t index, size_t total)
 772 {
 773     return (index == 0 ? ""
 774             : index < total - 1 ? ", "
 775             : total > 2 ? ", and "
 776             : " and ");
 777 }
 778
 779 /* Given a 32 bit word 'n', calculates floor(log_2('n')).  This is equivalent
 780  * to finding the bit position of the most significant one bit in 'n'.  It is
 781  * an error to call this function with 'n' == 0. */
 782 int
 783 log_2_floor(uint32_t n)
 784 {
 785     ovs_assert(n);
 786
 787 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 788 #error "Someone screwed up the #includes."
 789 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 790     return 31 - __builtin_clz(n);
 791 #else
 792     {
 793         int log = 0;
 794
 795 #define BIN_SEARCH_STEP(BITS)                   \
 796         if (n >= (1 << BITS)) {                 \
 797             log += BITS;                        \
 798             n >>= BITS;                         \
 799         }
 800         BIN_SEARCH_STEP(16);
 801         BIN_SEARCH_STEP(8);
 802         BIN_SEARCH_STEP(4);
 803         BIN_SEARCH_STEP(2);
 804         BIN_SEARCH_STEP(1);
 805 #undef BIN_SEARCH_STEP
 806         return log;
 807     }
 808 #endif
 809 }
 810
 811 /* Given a 32 bit word 'n', calculates ceil(log_2('n')).  It is an error to
 812  * call this function with 'n' == 0. */
 813 int
 814 log_2_ceil(uint32_t n)
 815 {
 816     return log_2_floor(n) + !is_pow2(n);
 817 }
 818
 819 /* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
 820 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 821 #error "Someone screwed up the #includes."
 822 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 823 /* Defined inline in util.h. */
 824 #else
 825 static int
 826 raw_ctz(uint32_t n)
 827 {
 828     unsigned int k;
 829     int count = 31;
 830
 831 #define CTZ_STEP(X)                             \
 832     k = n << (X);                               \
 833     if (k) {                                    \
 834         count -= X;                             \
 835         n = k;                                  \
 836     }
 837     CTZ_STEP(16);
 838     CTZ_STEP(8);
 839     CTZ_STEP(4);
 840     CTZ_STEP(2);
 841     CTZ_STEP(1);
 842 #undef CTZ_STEP
 843
 844     return count;
 845 }
 846 #endif
 847
 848 /* Returns the number of 1-bits in 'x', between 0 and 32 inclusive. */
 849 unsigned int
 850 popcount(uint32_t x)
 851 {
 852     /* In my testing, this implementation is over twice as fast as any other
 853      * portable implementation that I tried, including GCC 4.4
 854      * __builtin_popcount(), although nonportable asm("popcnt") was over 50%
 855      * faster. */
 856 #define INIT1(X)                                \
 857     ((((X) & (1 << 0)) != 0) +                  \
 858      (((X) & (1 << 1)) != 0) +                  \
 859      (((X) & (1 << 2)) != 0) +                  \
 860      (((X) & (1 << 3)) != 0) +                  \
 861      (((X) & (1 << 4)) != 0) +                  \
 862      (((X) & (1 << 5)) != 0) +                  \
 863      (((X) & (1 << 6)) != 0) +                  \
 864      (((X) & (1 << 7)) != 0))
 865 #define INIT2(X)   INIT1(X),  INIT1((X) +  1)
 866 #define INIT4(X)   INIT2(X),  INIT2((X) +  2)
 867 #define INIT8(X)   INIT4(X),  INIT4((X) +  4)
 868 #define INIT16(X)  INIT8(X),  INIT8((X) +  8)
 869 #define INIT32(X) INIT16(X), INIT16((X) + 16)
 870 #define INIT64(X) INIT32(X), INIT32((X) + 32)
 871
 872     static const uint8_t popcount8[256] = {
 873         INIT64(0), INIT64(64), INIT64(128), INIT64(192)
 874     };
 875
 876     return (popcount8[x & 0xff] +
 877             popcount8[(x >> 8) & 0xff] +
 878             popcount8[(x >> 16) & 0xff] +
 879             popcount8[x >> 24]);
 880 }
 881
 882 /* Returns true if the 'n' bytes starting at 'p' are zeros. */
 883 bool
 884 is_all_zeros(const uint8_t *p, size_t n)
 885 {
 886     size_t i;
 887
 888     for (i = 0; i < n; i++) {
 889         if (p[i] != 0x00) {
 890             return false;
 891         }
 892     }
 893     return true;
 894 }
 895
 896 /* Returns true if the 'n' bytes starting at 'p' are 0xff. */
 897 bool
 898 is_all_ones(const uint8_t *p, size_t n)
 899 {
 900     size_t i;
 901
 902     for (i = 0; i < n; i++) {
 903         if (p[i] != 0xff) {
 904             return false;
 905         }
 906     }
 907     return true;
 908 }
 909
 910 /* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
 911  * starting from bit 'dst_ofs' in 'dst'.  'src' is 'src_len' bytes long and
 912  * 'dst' is 'dst_len' bytes long.
 913  *
 914  * If you consider all of 'src' to be a single unsigned integer in network byte
 915  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 916  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
 917  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
 918  * 2], and so on.  Similarly for 'dst'.
 919  *
 920  * Required invariants:
 921  *   src_ofs + n_bits <= src_len * 8
 922  *   dst_ofs + n_bits <= dst_len * 8
 923  *   'src' and 'dst' must not overlap.
 924  */
 925 void
 926 bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
 927              void *dst_, unsigned int dst_len, unsigned int dst_ofs,
 928              unsigned int n_bits)
 929 {
 930     const uint8_t *src = src_;
 931     uint8_t *dst = dst_;
 932
 933     src += src_len - (src_ofs / 8 + 1);
 934     src_ofs %= 8;
 935
 936     dst += dst_len - (dst_ofs / 8 + 1);
 937     dst_ofs %= 8;
 938
 939     if (src_ofs == 0 && dst_ofs == 0) {
 940         unsigned int n_bytes = n_bits / 8;
 941         if (n_bytes) {
 942             dst -= n_bytes - 1;
 943             src -= n_bytes - 1;
 944             memcpy(dst, src, n_bytes);
 945
 946             n_bits %= 8;
 947             src--;
 948             dst--;
 949         }
 950         if (n_bits) {
 951             uint8_t mask = (1 << n_bits) - 1;
 952             *dst = (*dst & ~mask) | (*src & mask);
 953         }
 954     } else {
 955         while (n_bits > 0) {
 956             unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
 957             unsigned int chunk = MIN(n_bits, max_copy);
 958             uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
 959
 960             *dst &= ~mask;
 961             *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
 962
 963             src_ofs += chunk;
 964             if (src_ofs == 8) {
 965                 src--;
 966                 src_ofs = 0;
 967             }
 968             dst_ofs += chunk;
 969             if (dst_ofs == 8) {
 970                 dst--;
 971                 dst_ofs = 0;
 972             }
 973             n_bits -= chunk;
 974         }
 975     }
 976 }
 977
 978 /* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.  'dst' is
 979  * 'dst_len' bytes long.
 980  *
 981  * If you consider all of 'dst' to be a single unsigned integer in network byte
 982  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 983  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 984  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 985  * 2], and so on.
 986  *
 987  * Required invariant:
 988  *   dst_ofs + n_bits <= dst_len * 8
 989  */
 990 void
 991 bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 992              unsigned int n_bits)
 993 {
 994     uint8_t *dst = dst_;
 995
 996     if (!n_bits) {
 997         return;
 998     }
 999
1000     dst += dst_len - (dst_ofs / 8 + 1);
1001     dst_ofs %= 8;
1002
1003     if (dst_ofs) {
1004         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
1005
1006         *dst &= ~(((1 << chunk) - 1) << dst_ofs);
1007
1008         n_bits -= chunk;
1009         if (!n_bits) {
1010             return;
1011         }
1012
1013         dst--;
1014     }
1015
1016     while (n_bits >= 8) {
1017         *dst-- = 0;
1018         n_bits -= 8;
1019     }
1020
1021     if (n_bits) {
1022         *dst &= ~((1 << n_bits) - 1);
1023     }
1024 }
1025
1026 /* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
1027  * 'dst' is 'dst_len' bytes long.
1028  *
1029  * If you consider all of 'dst' to be a single unsigned integer in network byte
1030  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1031  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1032  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1033  * 2], and so on.
1034  *
1035  * Required invariant:
1036  *   dst_ofs + n_bits <= dst_len * 8
1037  */
1038 void
1039 bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
1040             unsigned int n_bits)
1041 {
1042     uint8_t *dst = dst_;
1043
1044     if (!n_bits) {
1045         return;
1046     }
1047
1048     dst += dst_len - (dst_ofs / 8 + 1);
1049     dst_ofs %= 8;
1050
1051     if (dst_ofs) {
1052         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
1053
1054         *dst |= ((1 << chunk) - 1) << dst_ofs;
1055
1056         n_bits -= chunk;
1057         if (!n_bits) {
1058             return;
1059         }
1060
1061         dst--;
1062     }
1063
1064     while (n_bits >= 8) {
1065         *dst-- = 0xff;
1066         n_bits -= 8;
1067     }
1068
1069     if (n_bits) {
1070         *dst |= (1 << n_bits) - 1;
1071     }
1072 }
1073
1074 /* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
1075  * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_len'
1076  * bytes long.
1077  *
1078  * If you consider all of 'dst' to be a single unsigned integer in network byte
1079  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1080  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1081  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1082  * 2], and so on.
1083  *
1084  * Required invariant:
1085  *   dst_ofs + n_bits <= dst_len * 8
1086  */
1087 bool
1088 bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
1089                      unsigned int n_bits)
1090 {
1091     const uint8_t *p = p_;
1092
1093     if (!n_bits) {
1094         return true;
1095     }
1096
1097     p += len - (ofs / 8 + 1);
1098     ofs %= 8;
1099
1100     if (ofs) {
1101         unsigned int chunk = MIN(n_bits, 8 - ofs);
1102
1103         if (*p & (((1 << chunk) - 1) << ofs)) {
1104             return false;
1105         }
1106
1107         n_bits -= chunk;
1108         if (!n_bits) {
1109             return true;
1110         }
1111
1112         p--;
1113     }
1114
1115     while (n_bits >= 8) {
1116         if (*p) {
1117             return false;
1118         }
1119         n_bits -= 8;
1120         p--;
1121     }
1122
1123     if (n_bits && *p & ((1 << n_bits) - 1)) {
1124         return false;
1125     }
1126
1127     return true;
1128 }
1129
1130 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
1131  * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
1132  *
1133  * If you consider all of 'dst' to be a single unsigned integer in network byte
1134  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1135  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1136  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1137  * 2], and so on.
1138  *
1139  * Required invariants:
1140  *   dst_ofs + n_bits <= dst_len * 8
1141  *   n_bits <= 64
1142  */
1143 void
1144 bitwise_put(uint64_t value,
1145             void *dst, unsigned int dst_len, unsigned int dst_ofs,
1146             unsigned int n_bits)
1147 {
1148     ovs_be64 n_value = htonll(value);
1149     bitwise_copy(&n_value, sizeof n_value, 0,
1150                  dst, dst_len, dst_ofs,
1151                  n_bits);
1152 }
1153
1154 /* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
1155  * which is 'src_len' bytes long.
1156  *
1157  * If you consider all of 'src' to be a single unsigned integer in network byte
1158  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1159  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1160  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1161  * 2], and so on.
1162  *
1163  * Required invariants:
1164  *   src_ofs + n_bits <= src_len * 8
1165  *   n_bits <= 64
1166  */
1167 uint64_t
1168 bitwise_get(const void *src, unsigned int src_len,
1169             unsigned int src_ofs, unsigned int n_bits)
1170 {
1171     ovs_be64 value = htonll(0);
1172
1173     bitwise_copy(src, src_len, src_ofs,
1174                  &value, sizeof value, 0,
1175                  n_bits);
1176     return ntohll(value);
1177 }