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