lib/util.c

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