lib/util.c

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