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