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