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