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