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