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