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