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', or 32 if 'n' is 0. */
 794 int
 795 ctz(uint32_t n)
 796 {
 797     if (!n) {
 798         return 32;
 799     } else {
 800 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 801 #error "Someone screwed up the #includes."
 802 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
 803         return __builtin_ctz(n);
 804 #else
 805         unsigned int k;
 806         int count = 31;
 807
 808 #define CTZ_STEP(X)                             \
 809         k = n << (X);                           \
 810         if (k) {                                \
 811             count -= X;                         \
 812             n = k;                              \
 813         }
 814         CTZ_STEP(16);
 815         CTZ_STEP(8);
 816         CTZ_STEP(4);
 817         CTZ_STEP(2);
 818         CTZ_STEP(1);
 819 #undef CTZ_STEP
 820
 821         return count;
 822 #endif
 823     }
 824 }
 825
 826 /* Returns true if the 'n' bytes starting at 'p' are zeros. */
 827 bool
 828 is_all_zeros(const uint8_t *p, size_t n)
 829 {
 830     size_t i;
 831
 832     for (i = 0; i < n; i++) {
 833         if (p[i] != 0x00) {
 834             return false;
 835         }
 836     }
 837     return true;
 838 }
 839
 840 /* Returns true if the 'n' bytes starting at 'p' are 0xff. */
 841 bool
 842 is_all_ones(const uint8_t *p, size_t n)
 843 {
 844     size_t i;
 845
 846     for (i = 0; i < n; i++) {
 847         if (p[i] != 0xff) {
 848             return false;
 849         }
 850     }
 851     return true;
 852 }
 853
 854 /* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
 855  * starting from bit 'dst_ofs' in 'dst'.  'src' is 'src_len' bytes long and
 856  * 'dst' is 'dst_len' bytes long.
 857  *
 858  * If you consider all of 'src' to be a single unsigned integer in network byte
 859  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 860  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
 861  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
 862  * 2], and so on.  Similarly for 'dst'.
 863  *
 864  * Required invariants:
 865  *   src_ofs + n_bits <= src_len * 8
 866  *   dst_ofs + n_bits <= dst_len * 8
 867  *   'src' and 'dst' must not overlap.
 868  */
 869 void
 870 bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
 871              void *dst_, unsigned int dst_len, unsigned int dst_ofs,
 872              unsigned int n_bits)
 873 {
 874     const uint8_t *src = src_;
 875     uint8_t *dst = dst_;
 876
 877     src += src_len - (src_ofs / 8 + 1);
 878     src_ofs %= 8;
 879
 880     dst += dst_len - (dst_ofs / 8 + 1);
 881     dst_ofs %= 8;
 882
 883     if (src_ofs == 0 && dst_ofs == 0) {
 884         unsigned int n_bytes = n_bits / 8;
 885         if (n_bytes) {
 886             dst -= n_bytes - 1;
 887             src -= n_bytes - 1;
 888             memcpy(dst, src, n_bytes);
 889
 890             n_bits %= 8;
 891             src--;
 892             dst--;
 893         }
 894         if (n_bits) {
 895             uint8_t mask = (1 << n_bits) - 1;
 896             *dst = (*dst & ~mask) | (*src & mask);
 897         }
 898     } else {
 899         while (n_bits > 0) {
 900             unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
 901             unsigned int chunk = MIN(n_bits, max_copy);
 902             uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
 903
 904             *dst &= ~mask;
 905             *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
 906
 907             src_ofs += chunk;
 908             if (src_ofs == 8) {
 909                 src--;
 910                 src_ofs = 0;
 911             }
 912             dst_ofs += chunk;
 913             if (dst_ofs == 8) {
 914                 dst--;
 915                 dst_ofs = 0;
 916             }
 917             n_bits -= chunk;
 918         }
 919     }
 920 }
 921
 922 /* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.  'dst' is
 923  * 'dst_len' bytes long.
 924  *
 925  * If you consider all of 'dst' to be a single unsigned integer in network byte
 926  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 927  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 928  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 929  * 2], and so on.
 930  *
 931  * Required invariant:
 932  *   dst_ofs + n_bits <= dst_len * 8
 933  */
 934 void
 935 bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 936              unsigned int n_bits)
 937 {
 938     uint8_t *dst = dst_;
 939
 940     if (!n_bits) {
 941         return;
 942     }
 943
 944     dst += dst_len - (dst_ofs / 8 + 1);
 945     dst_ofs %= 8;
 946
 947     if (dst_ofs) {
 948         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
 949
 950         *dst &= ~(((1 << chunk) - 1) << dst_ofs);
 951
 952         n_bits -= chunk;
 953         if (!n_bits) {
 954             return;
 955         }
 956
 957         dst--;
 958     }
 959
 960     while (n_bits >= 8) {
 961         *dst-- = 0;
 962         n_bits -= 8;
 963     }
 964
 965     if (n_bits) {
 966         *dst &= ~((1 << n_bits) - 1);
 967     }
 968 }
 969
 970 /* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
 971  * 'dst' is 'dst_len' bytes long.
 972  *
 973  * If you consider all of 'dst' to be a single unsigned integer in network byte
 974  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
 975  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
 976  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
 977  * 2], and so on.
 978  *
 979  * Required invariant:
 980  *   dst_ofs + n_bits <= dst_len * 8
 981  */
 982 void
 983 bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 984             unsigned int n_bits)
 985 {
 986     uint8_t *dst = dst_;
 987
 988     if (!n_bits) {
 989         return;
 990     }
 991
 992     dst += dst_len - (dst_ofs / 8 + 1);
 993     dst_ofs %= 8;
 994
 995     if (dst_ofs) {
 996         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
 997
 998         *dst |= ((1 << chunk) - 1) << dst_ofs;
 999
1000         n_bits -= chunk;
1001         if (!n_bits) {
1002             return;
1003         }
1004
1005         dst--;
1006     }
1007
1008     while (n_bits >= 8) {
1009         *dst-- = 0xff;
1010         n_bits -= 8;
1011     }
1012
1013     if (n_bits) {
1014         *dst |= (1 << n_bits) - 1;
1015     }
1016 }
1017
1018 /* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
1019  * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_len'
1020  * bytes long.
1021  *
1022  * If you consider all of 'dst' to be a single unsigned integer in network byte
1023  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1024  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1025  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1026  * 2], and so on.
1027  *
1028  * Required invariant:
1029  *   dst_ofs + n_bits <= dst_len * 8
1030  */
1031 bool
1032 bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
1033                      unsigned int n_bits)
1034 {
1035     const uint8_t *p = p_;
1036
1037     if (!n_bits) {
1038         return true;
1039     }
1040
1041     p += len - (ofs / 8 + 1);
1042     ofs %= 8;
1043
1044     if (ofs) {
1045         unsigned int chunk = MIN(n_bits, 8 - ofs);
1046
1047         if (*p & (((1 << chunk) - 1) << ofs)) {
1048             return false;
1049         }
1050
1051         n_bits -= chunk;
1052         if (!n_bits) {
1053             return true;
1054         }
1055
1056         p--;
1057     }
1058
1059     while (n_bits >= 8) {
1060         if (*p) {
1061             return false;
1062         }
1063         n_bits -= 8;
1064         p--;
1065     }
1066
1067     if (n_bits && *p & ((1 << n_bits) - 1)) {
1068         return false;
1069     }
1070
1071     return true;
1072 }
1073
1074 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
1075  * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
1076  *
1077  * If you consider all of 'dst' to be a single unsigned integer in network byte
1078  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1079  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1080  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1081  * 2], and so on.
1082  *
1083  * Required invariants:
1084  *   dst_ofs + n_bits <= dst_len * 8
1085  *   n_bits <= 64
1086  */
1087 void
1088 bitwise_put(uint64_t value,
1089             void *dst, unsigned int dst_len, unsigned int dst_ofs,
1090             unsigned int n_bits)
1091 {
1092     ovs_be64 n_value = htonll(value);
1093     bitwise_copy(&n_value, sizeof n_value, 0,
1094                  dst, dst_len, dst_ofs,
1095                  n_bits);
1096 }
1097
1098 /* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
1099  * which is 'src_len' bytes long.
1100  *
1101  * If you consider all of 'src' to be a single unsigned integer in network byte
1102  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1103  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1104  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1105  * 2], and so on.
1106  *
1107  * Required invariants:
1108  *   src_ofs + n_bits <= src_len * 8
1109  *   n_bits <= 64
1110  */
1111 uint64_t
1112 bitwise_get(const void *src, unsigned int src_len,
1113             unsigned int src_ofs, unsigned int n_bits)
1114 {
1115     ovs_be64 value = htonll(0);
1116
1117     bitwise_copy(src, src_len, src_ofs,
1118                  &value, sizeof value, 0,
1119                  n_bits);
1120     return ntohll(value);
1121 }