lib/util.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 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 <ctype.h>
  20 #include <errno.h>
  21 #include <limits.h>
  22 #include <pthread.h>
  23 #include <stdarg.h>
  24 #include <stdint.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <sys/stat.h>
  29 #include <unistd.h>
  30 #include "bitmap.h"
  31 #include "byte-order.h"
  32 #include "coverage.h"
  33 #include "ovs-rcu.h"
  34 #include "ovs-thread.h"
  35 #include "socket-util.h"
  36 #include "openvswitch/vlog.h"
  37 #ifdef HAVE_PTHREAD_SET_NAME_NP
  38 #include <pthread_np.h>
  39 #endif
  40
  41 VLOG_DEFINE_THIS_MODULE(util);
  42
  43 COVERAGE_DEFINE(util_xalloc);
  44
  45 /* argv[0] without directory names. */
  46 char *program_name;
  47
  48 /* Name for the currently running thread or process, for log messages, process
  49  * listings, and debuggers. */
  50 DEFINE_PER_THREAD_MALLOCED_DATA(char *, subprogram_name);
  51
  52 /* --version option output. */
  53 static char *program_version;
  54
  55 /* Buffer used by ovs_strerror() and ovs_format_message(). */
  56 DEFINE_STATIC_PER_THREAD_DATA(struct { char s[128]; },
  57                               strerror_buffer,
  58                               { "" });
  59
  60 static char *xreadlink(const char *filename);
  61
  62 void
  63 ovs_assert_failure(const char *where, const char *function,
  64                    const char *condition)
  65 {
  66     /* Prevent an infinite loop (or stack overflow) in case VLOG_ABORT happens
  67      * to trigger an assertion failure of its own. */
  68     static int reentry = 0;
  69
  70     switch (reentry++) {
  71     case 0:
  72         VLOG_ABORT("%s: assertion %s failed in %s()",
  73                    where, condition, function);
  74         OVS_NOT_REACHED();
  75
  76     case 1:
  77         fprintf(stderr, "%s: assertion %s failed in %s()",
  78                 where, condition, function);
  79         abort();
  80
  81     default:
  82         abort();
  83     }
  84 }
  85
  86 void
  87 out_of_memory(void)
  88 {
  89     ovs_abort(0, "virtual memory exhausted");
  90 }
  91
  92 void *
  93 xcalloc(size_t count, size_t size)
  94 {
  95     void *p = count && size ? calloc(count, size) : malloc(1);
  96     COVERAGE_INC(util_xalloc);
  97     if (p == NULL) {
  98         out_of_memory();
  99     }
 100     return p;
 101 }
 102
 103 void *
 104 xzalloc(size_t size)
 105 {
 106     return xcalloc(1, size);
 107 }
 108
 109 void *
 110 xmalloc(size_t size)
 111 {
 112     void *p = malloc(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 xrealloc(void *p, size_t size)
 122 {
 123     p = realloc(p, size ? size : 1);
 124     COVERAGE_INC(util_xalloc);
 125     if (p == NULL) {
 126         out_of_memory();
 127     }
 128     return p;
 129 }
 130
 131 void *
 132 xmemdup(const void *p_, size_t size)
 133 {
 134     void *p = xmalloc(size);
 135     memcpy(p, p_, size);
 136     return p;
 137 }
 138
 139 char *
 140 xmemdup0(const char *p_, size_t length)
 141 {
 142     char *p = xmalloc(length + 1);
 143     memcpy(p, p_, length);
 144     p[length] = '\0';
 145     return p;
 146 }
 147
 148 char *
 149 xstrdup(const char *s)
 150 {
 151     return xmemdup0(s, strlen(s));
 152 }
 153
 154 char *
 155 xvasprintf(const char *format, va_list args)
 156 {
 157     va_list args2;
 158     size_t needed;
 159     char *s;
 160
 161     va_copy(args2, args);
 162     needed = vsnprintf(NULL, 0, format, args);
 163
 164     s = xmalloc(needed + 1);
 165
 166     vsnprintf(s, needed + 1, format, args2);
 167     va_end(args2);
 168
 169     return s;
 170 }
 171
 172 void *
 173 x2nrealloc(void *p, size_t *n, size_t s)
 174 {
 175     *n = *n == 0 ? 1 : 2 * *n;
 176     return xrealloc(p, *n * s);
 177 }
 178
 179 /* The desired minimum alignment for an allocated block of memory. */
 180 #define MEM_ALIGN MAX(sizeof(void *), 8)
 181 BUILD_ASSERT_DECL(IS_POW2(MEM_ALIGN));
 182 BUILD_ASSERT_DECL(CACHE_LINE_SIZE >= MEM_ALIGN);
 183
 184 /* Allocates and returns 'size' bytes of memory in dedicated cache lines.  That
 185  * is, the memory block returned will not share a cache line with other data,
 186  * avoiding "false sharing".  (The memory returned will not be at the start of
 187  * a cache line, though, so don't assume such alignment.)
 188  *
 189  * Use free_cacheline() to free the returned memory block. */
 190 void *
 191 xmalloc_cacheline(size_t size)
 192 {
 193 #ifdef HAVE_POSIX_MEMALIGN
 194     void *p;
 195     int error;
 196
 197     COVERAGE_INC(util_xalloc);
 198     error = posix_memalign(&p, CACHE_LINE_SIZE, size ? size : 1);
 199     if (error != 0) {
 200         out_of_memory();
 201     }
 202     return p;
 203 #else
 204     void **payload;
 205     void *base;
 206
 207     /* Allocate room for:
 208      *
 209      *     - Up to CACHE_LINE_SIZE - 1 bytes before the payload, so that the
 210      *       start of the payload doesn't potentially share a cache line.
 211      *
 212      *     - A payload consisting of a void *, followed by padding out to
 213      *       MEM_ALIGN bytes, followed by 'size' bytes of user data.
 214      *
 215      *     - Space following the payload up to the end of the cache line, so
 216      *       that the end of the payload doesn't potentially share a cache line
 217      *       with some following block. */
 218     base = xmalloc((CACHE_LINE_SIZE - 1)
 219                    + ROUND_UP(MEM_ALIGN + size, CACHE_LINE_SIZE));
 220
 221     /* Locate the payload and store a pointer to the base at the beginning. */
 222     payload = (void **) ROUND_UP((uintptr_t) base, CACHE_LINE_SIZE);
 223     *payload = base;
 224
 225     return (char *) payload + MEM_ALIGN;
 226 #endif
 227 }
 228
 229 /* Like xmalloc_cacheline() but clears the allocated memory to all zero
 230  * bytes. */
 231 void *
 232 xzalloc_cacheline(size_t size)
 233 {
 234     void *p = xmalloc_cacheline(size);
 235     memset(p, 0, size);
 236     return p;
 237 }
 238
 239 /* Frees a memory block allocated with xmalloc_cacheline() or
 240  * xzalloc_cacheline(). */
 241 void
 242 free_cacheline(void *p)
 243 {
 244 #ifdef HAVE_POSIX_MEMALIGN
 245     free(p);
 246 #else
 247     if (p) {
 248         free(*(void **) ((uintptr_t) p - MEM_ALIGN));
 249     }
 250 #endif
 251 }
 252
 253 char *
 254 xasprintf(const char *format, ...)
 255 {
 256     va_list args;
 257     char *s;
 258
 259     va_start(args, format);
 260     s = xvasprintf(format, args);
 261     va_end(args);
 262
 263     return s;
 264 }
 265
 266 /* Similar to strlcpy() from OpenBSD, but it never reads more than 'size - 1'
 267  * bytes from 'src' and doesn't return anything. */
 268 void
 269 ovs_strlcpy(char *dst, const char *src, size_t size)
 270 {
 271     if (size > 0) {
 272         size_t len = strnlen(src, size - 1);
 273         memcpy(dst, src, len);
 274         dst[len] = '\0';
 275     }
 276 }
 277
 278 /* Copies 'src' to 'dst'.  Reads no more than 'size - 1' bytes from 'src'.
 279  * Always null-terminates 'dst' (if 'size' is nonzero), and writes a zero byte
 280  * to every otherwise unused byte in 'dst'.
 281  *
 282  * Except for performance, the following call:
 283  *     ovs_strzcpy(dst, src, size);
 284  * is equivalent to these two calls:
 285  *     memset(dst, '\0', size);
 286  *     ovs_strlcpy(dst, src, size);
 287  *
 288  * (Thus, ovs_strzcpy() is similar to strncpy() without some of the pitfalls.)
 289  */
 290 void
 291 ovs_strzcpy(char *dst, const char *src, size_t size)
 292 {
 293     if (size > 0) {
 294         size_t len = strnlen(src, size - 1);
 295         memcpy(dst, src, len);
 296         memset(dst + len, '\0', size - len);
 297     }
 298 }
 299
 300 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 301  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 302  * the message inside parentheses.  Then, terminates with abort().
 303  *
 304  * This function is preferred to ovs_fatal() in a situation where it would make
 305  * sense for a monitoring process to restart the daemon.
 306  *
 307  * 'format' should not end with a new-line, because this function will add one
 308  * itself. */
 309 void
 310 ovs_abort(int err_no, const char *format, ...)
 311 {
 312     va_list args;
 313
 314     va_start(args, format);
 315     ovs_abort_valist(err_no, format, args);
 316 }
 317
 318 /* Same as ovs_abort() except that the arguments are supplied as a va_list. */
 319 void
 320 ovs_abort_valist(int err_no, const char *format, va_list args)
 321 {
 322     ovs_error_valist(err_no, format, args);
 323     abort();
 324 }
 325
 326 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 327  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 328  * the message inside parentheses.  Then, terminates with EXIT_FAILURE.
 329  *
 330  * 'format' should not end with a new-line, because this function will add one
 331  * itself. */
 332 void
 333 ovs_fatal(int err_no, const char *format, ...)
 334 {
 335     va_list args;
 336
 337     va_start(args, format);
 338     ovs_fatal_valist(err_no, format, args);
 339 }
 340
 341 /* Same as ovs_fatal() except that the arguments are supplied as a va_list. */
 342 void
 343 ovs_fatal_valist(int err_no, const char *format, va_list args)
 344 {
 345     ovs_error_valist(err_no, format, args);
 346     exit(EXIT_FAILURE);
 347 }
 348
 349 /* Prints 'format' on stderr, formatting it like printf() does.  If 'err_no' is
 350  * nonzero, then it is formatted with ovs_retval_to_string() and appended to
 351  * the message inside parentheses.
 352  *
 353  * 'format' should not end with a new-line, because this function will add one
 354  * itself. */
 355 void
 356 ovs_error(int err_no, const char *format, ...)
 357 {
 358     va_list args;
 359
 360     va_start(args, format);
 361     ovs_error_valist(err_no, format, args);
 362     va_end(args);
 363 }
 364
 365 /* Same as ovs_error() except that the arguments are supplied as a va_list. */
 366 void
 367 ovs_error_valist(int err_no, const char *format, va_list args)
 368 {
 369     const char *subprogram_name = get_subprogram_name();
 370     int save_errno = errno;
 371
 372     if (subprogram_name[0]) {
 373         fprintf(stderr, "%s(%s): ", program_name, subprogram_name);
 374     } else {
 375         fprintf(stderr, "%s: ", program_name);
 376     }
 377
 378     vfprintf(stderr, format, args);
 379     if (err_no != 0) {
 380         fprintf(stderr, " (%s)", ovs_retval_to_string(err_no));
 381     }
 382     putc('\n', stderr);
 383
 384     errno = save_errno;
 385 }
 386
 387 /* Many OVS functions return an int which is one of:
 388  * - 0: no error yet
 389  * - >0: errno value
 390  * - EOF: end of file (not necessarily an error; depends on the function called)
 391  *
 392  * Returns the appropriate human-readable string. The caller must copy the
 393  * string if it wants to hold onto it, as the storage may be overwritten on
 394  * subsequent function calls.
 395  */
 396 const char *
 397 ovs_retval_to_string(int retval)
 398 {
 399     return (!retval ? ""
 400             : retval == EOF ? "End of file"
 401             : ovs_strerror(retval));
 402 }
 403
 404 /* This function returns the string describing the error number in 'error'
 405  * for POSIX platforms.  For Windows, this function can be used for C library
 406  * calls.  For socket calls that are also used in Windows, use sock_strerror()
 407  * instead.  For WINAPI calls, look at ovs_lasterror_to_string(). */
 408 const char *
 409 ovs_strerror(int error)
 410 {
 411     enum { BUFSIZE = sizeof strerror_buffer_get()->s };
 412     int save_errno;
 413     char *buffer;
 414     char *s;
 415
 416     if (error == 0) {
 417         /*
 418          * strerror(0) varies among platforms:
 419          *
 420          *   Success
 421          *   No error
 422          *   Undefined error: 0
 423          *
 424          * We want to provide a consistent result here because
 425          * our testsuite has test cases which strictly matches
 426          * log messages containing this string.
 427          */
 428         return "Success";
 429     }
 430
 431     save_errno = errno;
 432     buffer = strerror_buffer_get()->s;
 433
 434 #if STRERROR_R_CHAR_P
 435     /* GNU style strerror_r() might return an immutable static string, or it
 436      * might write and return 'buffer', but in either case we can pass the
 437      * returned string directly to the caller. */
 438     s = strerror_r(error, buffer, BUFSIZE);
 439 #else  /* strerror_r() returns an int. */
 440     s = buffer;
 441     if (strerror_r(error, buffer, BUFSIZE)) {
 442         /* strerror_r() is only allowed to fail on ERANGE (because the buffer
 443          * is too short).  We don't check the actual failure reason because
 444          * POSIX requires strerror_r() to return the error but old glibc
 445          * (before 2.13) returns -1 and sets errno. */
 446         snprintf(buffer, BUFSIZE, "Unknown error %d", error);
 447     }
 448 #endif
 449
 450     errno = save_errno;
 451
 452     return s;
 453 }
 454
 455 /* Sets global "program_name" and "program_version" variables.  Should
 456  * be called at the beginning of main() with "argv[0]" as the argument
 457  * to 'argv0'.
 458  *
 459  * 'version' should contain the version of the caller's program.  If 'version'
 460  * is the same as the VERSION #define, the caller is assumed to be part of Open
 461  * vSwitch.  Otherwise, it is assumed to be an external program linking against
 462  * the Open vSwitch libraries.
 463  *
 464  * The 'date' and 'time' arguments should likely be called with
 465  * "__DATE__" and "__TIME__" to use the time the binary was built.
 466  * Alternatively, the "ovs_set_program_name" macro may be called to do this
 467  * automatically.
 468  */
 469 void
 470 ovs_set_program_name__(const char *argv0, const char *version, const char *date,
 471                        const char *time)
 472 {
 473     char *basename;
 474 #ifdef _WIN32
 475     size_t max_len = strlen(argv0) + 1;
 476
 477     SetErrorMode(GetErrorMode() | SEM_NOGPFAULTERRORBOX);
 478     _set_output_format(_TWO_DIGIT_EXPONENT);
 479
 480     basename = xmalloc(max_len);
 481     _splitpath_s(argv0, NULL, 0, NULL, 0, basename, max_len, NULL, 0);
 482 #else
 483     const char *slash = strrchr(argv0, '/');
 484     basename = xstrdup(slash ? slash + 1 : argv0);
 485 #endif
 486
 487     assert_single_threaded();
 488     free(program_name);
 489     /* Remove libtool prefix, if it is there */
 490     if (strncmp(basename, "lt-", 3) == 0) {
 491         char *tmp_name = basename;
 492         basename = xstrdup(basename + 3);
 493         free(tmp_name);
 494     }
 495     program_name = basename;
 496
 497     free(program_version);
 498     if (!strcmp(version, VERSION)) {
 499         program_version = xasprintf("%s (Open vSwitch) "VERSION"\n"
 500                                     "Compiled %s %s\n",
 501                                     program_name, date, time);
 502     } else {
 503         program_version = xasprintf("%s %s\n"
 504                                     "Open vSwitch Library "VERSION"\n"
 505                                     "Compiled %s %s\n",
 506                                     program_name, version, date, time);
 507     }
 508 }
 509
 510 /* Returns the name of the currently running thread or process. */
 511 const char *
 512 get_subprogram_name(void)
 513 {
 514     const char *name = subprogram_name_get();
 515     return name ? name : "";
 516 }
 517
 518 /* Sets 'subprogram_name' as the name of the currently running thread or
 519  * process.  (This appears in log messages and may also be visible in system
 520  * process listings and debuggers.) */
 521 void
 522 set_subprogram_name(const char *subprogram_name)
 523 {
 524     char *pname = xstrdup(subprogram_name ? subprogram_name : program_name);
 525     free(subprogram_name_set(pname));
 526
 527 #if HAVE_GLIBC_PTHREAD_SETNAME_NP
 528     pthread_setname_np(pthread_self(), pname);
 529 #elif HAVE_NETBSD_PTHREAD_SETNAME_NP
 530     pthread_setname_np(pthread_self(), "%s", pname);
 531 #elif HAVE_PTHREAD_SET_NAME_NP
 532     pthread_set_name_np(pthread_self(), pname);
 533 #endif
 534 }
 535
 536 /* Returns a pointer to a string describing the program version.  The
 537  * caller must not modify or free the returned string.
 538  */
 539 const char *
 540 ovs_get_program_version(void)
 541 {
 542     return program_version;
 543 }
 544
 545 /* Returns a pointer to a string describing the program name.  The
 546  * caller must not modify or free the returned string.
 547  */
 548 const char *
 549 ovs_get_program_name(void)
 550 {
 551     return program_name;
 552 }
 553
 554 /* Print the version information for the program.  */
 555 void
 556 ovs_print_version(uint8_t min_ofp, uint8_t max_ofp)
 557 {
 558     printf("%s", program_version);
 559     if (min_ofp || max_ofp) {
 560         printf("OpenFlow versions %#x:%#x\n", min_ofp, max_ofp);
 561     }
 562 }
 563
 564 /* Writes the 'size' bytes in 'buf' to 'stream' as hex bytes arranged 16 per
 565  * line.  Numeric offsets are also included, starting at 'ofs' for the first
 566  * byte in 'buf'.  If 'ascii' is true then the corresponding ASCII characters
 567  * are also rendered alongside. */
 568 void
 569 ovs_hex_dump(FILE *stream, const void *buf_, size_t size,
 570              uintptr_t ofs, bool ascii)
 571 {
 572   const uint8_t *buf = buf_;
 573   const size_t per_line = 16; /* Maximum bytes per line. */
 574
 575   while (size > 0)
 576     {
 577       size_t start, end, n;
 578       size_t i;
 579
 580       /* Number of bytes on this line. */
 581       start = ofs % per_line;
 582       end = per_line;
 583       if (end - start > size)
 584         end = start + size;
 585       n = end - start;
 586
 587       /* Print line. */
 588       fprintf(stream, "%08"PRIxMAX"  ", (uintmax_t) ROUND_DOWN(ofs, per_line));
 589       for (i = 0; i < start; i++)
 590         fprintf(stream, "   ");
 591       for (; i < end; i++)
 592         fprintf(stream, "%02x%c",
 593                 buf[i - start], i == per_line / 2 - 1? '-' : ' ');
 594       if (ascii)
 595         {
 596           for (; i < per_line; i++)
 597             fprintf(stream, "   ");
 598           fprintf(stream, "|");
 599           for (i = 0; i < start; i++)
 600             fprintf(stream, " ");
 601           for (; i < end; i++) {
 602               int c = buf[i - start];
 603               putc(c >= 32 && c < 127 ? c : '.', stream);
 604           }
 605           for (; i < per_line; i++)
 606             fprintf(stream, " ");
 607           fprintf(stream, "|");
 608         }
 609       fprintf(stream, "\n");
 610
 611       ofs += n;
 612       buf += n;
 613       size -= n;
 614     }
 615 }
 616
 617 bool
 618 str_to_int(const char *s, int base, int *i)
 619 {
 620     long long ll;
 621     bool ok = str_to_llong(s, base, &ll);
 622     *i = ll;
 623     return ok;
 624 }
 625
 626 bool
 627 str_to_long(const char *s, int base, long *li)
 628 {
 629     long long ll;
 630     bool ok = str_to_llong(s, base, &ll);
 631     *li = ll;
 632     return ok;
 633 }
 634
 635 bool
 636 str_to_llong(const char *s, int base, long long *x)
 637 {
 638     int save_errno = errno;
 639     char *tail;
 640     errno = 0;
 641     *x = strtoll(s, &tail, base);
 642     if (errno == EINVAL || errno == ERANGE || tail == s || *tail != '\0') {
 643         errno = save_errno;
 644         *x = 0;
 645         return false;
 646     } else {
 647         errno = save_errno;
 648         return true;
 649     }
 650 }
 651
 652 bool
 653 str_to_uint(const char *s, int base, unsigned int *u)
 654 {
 655     long long ll;
 656     bool ok = str_to_llong(s, base, &ll);
 657     if (!ok || ll < 0 || ll > UINT_MAX) {
 658         *u = 0;
 659         return false;
 660     } else {
 661         *u = ll;
 662         return true;
 663     }
 664 }
 665
 666 /* Converts floating-point string 's' into a double.  If successful, stores
 667  * the double in '*d' and returns true; on failure, stores 0 in '*d' and
 668  * returns false.
 669  *
 670  * Underflow (e.g. "1e-9999") is not considered an error, but overflow
 671  * (e.g. "1e9999)" is. */
 672 bool
 673 str_to_double(const char *s, double *d)
 674 {
 675     int save_errno = errno;
 676     char *tail;
 677     errno = 0;
 678     *d = strtod(s, &tail);
 679     if (errno == EINVAL || (errno == ERANGE && *d != 0)
 680         || tail == s || *tail != '\0') {
 681         errno = save_errno;
 682         *d = 0;
 683         return false;
 684     } else {
 685         errno = save_errno;
 686         return true;
 687     }
 688 }
 689
 690 /* Returns the value of 'c' as a hexadecimal digit. */
 691 int
 692 hexit_value(int c)
 693 {
 694     switch (c) {
 695     case '0': case '1': case '2': case '3': case '4':
 696     case '5': case '6': case '7': case '8': case '9':
 697         return c - '0';
 698
 699     case 'a': case 'A':
 700         return 0xa;
 701
 702     case 'b': case 'B':
 703         return 0xb;
 704
 705     case 'c': case 'C':
 706         return 0xc;
 707
 708     case 'd': case 'D':
 709         return 0xd;
 710
 711     case 'e': case 'E':
 712         return 0xe;
 713
 714     case 'f': case 'F':
 715         return 0xf;
 716
 717     default:
 718         return -1;
 719     }
 720 }
 721
 722 /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
 723  * UINTMAX_MAX if one of those "digits" is not really a hex digit.  Sets '*ok'
 724  * to true if the conversion succeeds or to false if a non-hex digit is
 725  * detected. */
 726 uintmax_t
 727 hexits_value(const char *s, size_t n, bool *ok)
 728 {
 729     uintmax_t value;
 730     size_t i;
 731
 732     value = 0;
 733     for (i = 0; i < n; i++) {
 734         int hexit = hexit_value(s[i]);
 735         if (hexit < 0) {
 736             *ok = false;
 737             return UINTMAX_MAX;
 738         }
 739         value = (value << 4) + hexit;
 740     }
 741     *ok = true;
 742     return value;
 743 }
 744
 745 /* Parses the string in 's' as an integer in either hex or decimal format and
 746  * puts the result right justified in the array 'valuep' that is 'field_width'
 747  * big. If the string is in hex format, the value may be arbitrarily large;
 748  * integers are limited to 64-bit values. (The rationale is that decimal is
 749  * likely to represent a number and 64 bits is a reasonable maximum whereas
 750  * hex could either be a number or a byte string.)
 751  *
 752  * On return 'tail' points to the first character in the string that was
 753  * not parsed as part of the value. ERANGE is returned if the value is too
 754  * large to fit in the given field. */
 755 int
 756 parse_int_string(const char *s, uint8_t *valuep, int field_width, char **tail)
 757 {
 758     unsigned long long int integer;
 759     int i;
 760
 761     if (!strncmp(s, "0x", 2) || !strncmp(s, "0X", 2)) {
 762         uint8_t *hexit_str;
 763         int len = 0;
 764         int val_idx;
 765         int err = 0;
 766
 767         s += 2;
 768         hexit_str = xmalloc(field_width * 2);
 769
 770         for (;;) {
 771             uint8_t hexit;
 772             bool ok;
 773
 774             s += strspn(s, " \t\r\n");
 775             hexit = hexits_value(s, 1, &ok);
 776             if (!ok) {
 777                 *tail = CONST_CAST(char *, s);
 778                 break;
 779             }
 780
 781             if (hexit != 0 || len) {
 782                 if (DIV_ROUND_UP(len + 1, 2) > field_width) {
 783                     err = ERANGE;
 784                     goto free;
 785                 }
 786
 787                 hexit_str[len] = hexit;
 788                 len++;
 789             }
 790             s++;
 791         }
 792
 793         val_idx = field_width;
 794         for (i = len - 1; i >= 0; i -= 2) {
 795             val_idx--;
 796             valuep[val_idx] = hexit_str[i];
 797             if (i > 0) {
 798                 valuep[val_idx] += hexit_str[i - 1] << 4;
 799             }
 800         }
 801
 802         memset(valuep, 0, val_idx);
 803
 804 free:
 805         free(hexit_str);
 806         return err;
 807     }
 808
 809     errno = 0;
 810     integer = strtoull(s, tail, 0);
 811     if (errno) {
 812         return errno;
 813     }
 814
 815     for (i = field_width - 1; i >= 0; i--) {
 816         valuep[i] = integer;
 817         integer >>= 8;
 818     }
 819     if (integer) {
 820         return ERANGE;
 821     }
 822
 823     return 0;
 824 }
 825
 826 /* Returns the current working directory as a malloc()'d string, or a null
 827  * pointer if the current working directory cannot be determined. */
 828 char *
 829 get_cwd(void)
 830 {
 831     long int path_max;
 832     size_t size;
 833
 834     /* Get maximum path length or at least a reasonable estimate. */
 835 #ifndef _WIN32
 836     path_max = pathconf(".", _PC_PATH_MAX);
 837 #else
 838     path_max = MAX_PATH;
 839 #endif
 840     size = (path_max < 0 ? 1024
 841             : path_max > 10240 ? 10240
 842             : path_max);
 843
 844     /* Get current working directory. */
 845     for (;;) {
 846         char *buf = xmalloc(size);
 847         if (getcwd(buf, size)) {
 848             return xrealloc(buf, strlen(buf) + 1);
 849         } else {
 850             int error = errno;
 851             free(buf);
 852             if (error != ERANGE) {
 853                 VLOG_WARN("getcwd failed (%s)", ovs_strerror(error));
 854                 return NULL;
 855             }
 856             size *= 2;
 857         }
 858     }
 859 }
 860
 861 static char *
 862 all_slashes_name(const char *s)
 863 {
 864     return xstrdup(s[0] == '/' && s[1] == '/' && s[2] != '/' ? "//"
 865                    : s[0] == '/' ? "/"
 866                    : ".");
 867 }
 868
 869 #ifndef _WIN32
 870 /* Returns the directory name portion of 'file_name' as a malloc()'d string,
 871  * similar to the POSIX dirname() function but thread-safe. */
 872 char *
 873 dir_name(const char *file_name)
 874 {
 875     size_t len = strlen(file_name);
 876     while (len > 0 && file_name[len - 1] == '/') {
 877         len--;
 878     }
 879     while (len > 0 && file_name[len - 1] != '/') {
 880         len--;
 881     }
 882     while (len > 0 && file_name[len - 1] == '/') {
 883         len--;
 884     }
 885     return len ? xmemdup0(file_name, len) : all_slashes_name(file_name);
 886 }
 887
 888 /* Returns the file name portion of 'file_name' as a malloc()'d string,
 889  * similar to the POSIX basename() function but thread-safe. */
 890 char *
 891 base_name(const char *file_name)
 892 {
 893     size_t end, start;
 894
 895     end = strlen(file_name);
 896     while (end > 0 && file_name[end - 1] == '/') {
 897         end--;
 898     }
 899
 900     if (!end) {
 901         return all_slashes_name(file_name);
 902     }
 903
 904     start = end;
 905     while (start > 0 && file_name[start - 1] != '/') {
 906         start--;
 907     }
 908
 909     return xmemdup0(file_name + start, end - start);
 910 }
 911 #endif /* _WIN32 */
 912
 913 /* If 'file_name' starts with '/', returns a copy of 'file_name'.  Otherwise,
 914  * returns an absolute path to 'file_name' considering it relative to 'dir',
 915  * which itself must be absolute.  'dir' may be null or the empty string, in
 916  * which case the current working directory is used.
 917  *
 918  * Returns a null pointer if 'dir' is null and getcwd() fails. */
 919 char *
 920 abs_file_name(const char *dir, const char *file_name)
 921 {
 922     if (file_name[0] == '/') {
 923         return xstrdup(file_name);
 924     } else if (dir && dir[0]) {
 925         char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
 926         return xasprintf("%s%s%s", dir, separator, file_name);
 927     } else {
 928         char *cwd = get_cwd();
 929         if (cwd) {
 930             char *abs_name = xasprintf("%s/%s", cwd, file_name);
 931             free(cwd);
 932             return abs_name;
 933         } else {
 934             return NULL;
 935         }
 936     }
 937 }
 938
 939 /* Like readlink(), but returns the link name as a null-terminated string in
 940  * allocated memory that the caller must eventually free (with free()).
 941  * Returns NULL on error, in which case errno is set appropriately. */
 942 static char *
 943 xreadlink(const char *filename)
 944 {
 945     size_t size;
 946
 947     for (size = 64; ; size *= 2) {
 948         char *buf = xmalloc(size);
 949         ssize_t retval = readlink(filename, buf, size);
 950         int error = errno;
 951
 952         if (retval >= 0 && retval < size) {
 953             buf[retval] = '\0';
 954             return buf;
 955         }
 956
 957         free(buf);
 958         if (retval < 0) {
 959             errno = error;
 960             return NULL;
 961         }
 962     }
 963 }
 964
 965 /* Returns a version of 'filename' with symlinks in the final component
 966  * dereferenced.  This differs from realpath() in that:
 967  *
 968  *     - 'filename' need not exist.
 969  *
 970  *     - If 'filename' does exist as a symlink, its referent need not exist.
 971  *
 972  *     - Only symlinks in the final component of 'filename' are dereferenced.
 973  *
 974  * For Windows platform, this function returns a string that has the same
 975  * value as the passed string.
 976  *
 977  * The caller must eventually free the returned string (with free()). */
 978 char *
 979 follow_symlinks(const char *filename)
 980 {
 981 #ifndef _WIN32
 982     struct stat s;
 983     char *fn;
 984     int i;
 985
 986     fn = xstrdup(filename);
 987     for (i = 0; i < 10; i++) {
 988         char *linkname;
 989         char *next_fn;
 990
 991         if (lstat(fn, &s) != 0 || !S_ISLNK(s.st_mode)) {
 992             return fn;
 993         }
 994
 995         linkname = xreadlink(fn);
 996         if (!linkname) {
 997             VLOG_WARN("%s: readlink failed (%s)",
 998                       filename, ovs_strerror(errno));
 999             return fn;
1000         }
1001
1002         if (linkname[0] == '/') {
1003             /* Target of symlink is absolute so use it raw. */
1004             next_fn = linkname;
1005         } else {
1006             /* Target of symlink is relative so add to 'fn''s directory. */
1007             char *dir = dir_name(fn);
1008
1009             if (!strcmp(dir, ".")) {
1010                 next_fn = linkname;
1011             } else {
1012                 char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/";
1013                 next_fn = xasprintf("%s%s%s", dir, separator, linkname);
1014                 free(linkname);
1015             }
1016
1017             free(dir);
1018         }
1019
1020         free(fn);
1021         fn = next_fn;
1022     }
1023
1024     VLOG_WARN("%s: too many levels of symlinks", filename);
1025     free(fn);
1026 #endif
1027     return xstrdup(filename);
1028 }
1029
1030 /* Pass a value to this function if it is marked with
1031  * __attribute__((warn_unused_result)) and you genuinely want to ignore
1032  * its return value.  (Note that every scalar type can be implicitly
1033  * converted to bool.) */
1034 void ignore(bool x OVS_UNUSED) { }
1035
1036 /* Returns an appropriate delimiter for inserting just before the 0-based item
1037  * 'index' in a list that has 'total' items in it. */
1038 const char *
1039 english_list_delimiter(size_t index, size_t total)
1040 {
1041     return (index == 0 ? ""
1042             : index < total - 1 ? ", "
1043             : total > 2 ? ", and "
1044             : " and ");
1045 }
1046
1047 /* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
1048 #if __GNUC__ >= 4 || _MSC_VER
1049 /* Defined inline in util.h. */
1050 #else
1051 /* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
1052 int
1053 raw_ctz(uint64_t n)
1054 {
1055     uint64_t k;
1056     int count = 63;
1057
1058 #define CTZ_STEP(X)                             \
1059     k = n << (X);                               \
1060     if (k) {                                    \
1061         count -= X;                             \
1062         n = k;                                  \
1063     }
1064     CTZ_STEP(32);
1065     CTZ_STEP(16);
1066     CTZ_STEP(8);
1067     CTZ_STEP(4);
1068     CTZ_STEP(2);
1069     CTZ_STEP(1);
1070 #undef CTZ_STEP
1071
1072     return count;
1073 }
1074
1075 /* Returns the number of leading 0-bits in 'n'.  Undefined if 'n' == 0. */
1076 int
1077 raw_clz64(uint64_t n)
1078 {
1079     uint64_t k;
1080     int count = 63;
1081
1082 #define CLZ_STEP(X)                             \
1083     k = n >> (X);                               \
1084     if (k) {                                    \
1085         count -= X;                             \
1086         n = k;                                  \
1087     }
1088     CLZ_STEP(32);
1089     CLZ_STEP(16);
1090     CLZ_STEP(8);
1091     CLZ_STEP(4);
1092     CLZ_STEP(2);
1093     CLZ_STEP(1);
1094 #undef CLZ_STEP
1095
1096     return count;
1097 }
1098 #endif
1099
1100 #if NEED_COUNT_1BITS_8
1101 #define INIT1(X)                                \
1102     ((((X) & (1 << 0)) != 0) +                  \
1103      (((X) & (1 << 1)) != 0) +                  \
1104      (((X) & (1 << 2)) != 0) +                  \
1105      (((X) & (1 << 3)) != 0) +                  \
1106      (((X) & (1 << 4)) != 0) +                  \
1107      (((X) & (1 << 5)) != 0) +                  \
1108      (((X) & (1 << 6)) != 0) +                  \
1109      (((X) & (1 << 7)) != 0))
1110 #define INIT2(X)   INIT1(X),  INIT1((X) +  1)
1111 #define INIT4(X)   INIT2(X),  INIT2((X) +  2)
1112 #define INIT8(X)   INIT4(X),  INIT4((X) +  4)
1113 #define INIT16(X)  INIT8(X),  INIT8((X) +  8)
1114 #define INIT32(X) INIT16(X), INIT16((X) + 16)
1115 #define INIT64(X) INIT32(X), INIT32((X) + 32)
1116
1117 const uint8_t count_1bits_8[256] = {
1118     INIT64(0), INIT64(64), INIT64(128), INIT64(192)
1119 };
1120 #endif
1121
1122 /* Returns true if the 'n' bytes starting at 'p' are zeros. */
1123 bool
1124 is_all_zeros(const void *p_, size_t n)
1125 {
1126     const uint8_t *p = p_;
1127     size_t i;
1128
1129     for (i = 0; i < n; i++) {
1130         if (p[i] != 0x00) {
1131             return false;
1132         }
1133     }
1134     return true;
1135 }
1136
1137 /* Returns true if the 'n' bytes starting at 'p' are 0xff. */
1138 bool
1139 is_all_ones(const void *p_, size_t n)
1140 {
1141     const uint8_t *p = p_;
1142     size_t i;
1143
1144     for (i = 0; i < n; i++) {
1145         if (p[i] != 0xff) {
1146             return false;
1147         }
1148     }
1149     return true;
1150 }
1151
1152 /* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits'
1153  * starting from bit 'dst_ofs' in 'dst'.  'src' is 'src_len' bytes long and
1154  * 'dst' is 'dst_len' bytes long.
1155  *
1156  * If you consider all of 'src' to be a single unsigned integer in network byte
1157  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1158  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1159  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1160  * 2], and so on.  Similarly for 'dst'.
1161  *
1162  * Required invariants:
1163  *   src_ofs + n_bits <= src_len * 8
1164  *   dst_ofs + n_bits <= dst_len * 8
1165  *   'src' and 'dst' must not overlap.
1166  */
1167 void
1168 bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs,
1169              void *dst_, unsigned int dst_len, unsigned int dst_ofs,
1170              unsigned int n_bits)
1171 {
1172     const uint8_t *src = src_;
1173     uint8_t *dst = dst_;
1174
1175     src += src_len - (src_ofs / 8 + 1);
1176     src_ofs %= 8;
1177
1178     dst += dst_len - (dst_ofs / 8 + 1);
1179     dst_ofs %= 8;
1180
1181     if (src_ofs == 0 && dst_ofs == 0) {
1182         unsigned int n_bytes = n_bits / 8;
1183         if (n_bytes) {
1184             dst -= n_bytes - 1;
1185             src -= n_bytes - 1;
1186             memcpy(dst, src, n_bytes);
1187
1188             n_bits %= 8;
1189             src--;
1190             dst--;
1191         }
1192         if (n_bits) {
1193             uint8_t mask = (1 << n_bits) - 1;
1194             *dst = (*dst & ~mask) | (*src & mask);
1195         }
1196     } else {
1197         while (n_bits > 0) {
1198             unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs);
1199             unsigned int chunk = MIN(n_bits, max_copy);
1200             uint8_t mask = ((1 << chunk) - 1) << dst_ofs;
1201
1202             *dst &= ~mask;
1203             *dst |= ((*src >> src_ofs) << dst_ofs) & mask;
1204
1205             src_ofs += chunk;
1206             if (src_ofs == 8) {
1207                 src--;
1208                 src_ofs = 0;
1209             }
1210             dst_ofs += chunk;
1211             if (dst_ofs == 8) {
1212                 dst--;
1213                 dst_ofs = 0;
1214             }
1215             n_bits -= chunk;
1216         }
1217     }
1218 }
1219
1220 /* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.  'dst' is
1221  * 'dst_len' bytes long.
1222  *
1223  * If you consider all of 'dst' to be a single unsigned integer in network byte
1224  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1225  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1226  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1227  * 2], and so on.
1228  *
1229  * Required invariant:
1230  *   dst_ofs + n_bits <= dst_len * 8
1231  */
1232 void
1233 bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
1234              unsigned int n_bits)
1235 {
1236     uint8_t *dst = dst_;
1237
1238     if (!n_bits) {
1239         return;
1240     }
1241
1242     dst += dst_len - (dst_ofs / 8 + 1);
1243     dst_ofs %= 8;
1244
1245     if (dst_ofs) {
1246         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
1247
1248         *dst &= ~(((1 << chunk) - 1) << dst_ofs);
1249
1250         n_bits -= chunk;
1251         if (!n_bits) {
1252             return;
1253         }
1254
1255         dst--;
1256     }
1257
1258     while (n_bits >= 8) {
1259         *dst-- = 0;
1260         n_bits -= 8;
1261     }
1262
1263     if (n_bits) {
1264         *dst &= ~((1 << n_bits) - 1);
1265     }
1266 }
1267
1268 /* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'.
1269  * 'dst' is 'dst_len' bytes long.
1270  *
1271  * If you consider all of 'dst' to be a single unsigned integer in network byte
1272  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1273  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1274  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1275  * 2], and so on.
1276  *
1277  * Required invariant:
1278  *   dst_ofs + n_bits <= dst_len * 8
1279  */
1280 void
1281 bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
1282             unsigned int n_bits)
1283 {
1284     uint8_t *dst = dst_;
1285
1286     if (!n_bits) {
1287         return;
1288     }
1289
1290     dst += dst_len - (dst_ofs / 8 + 1);
1291     dst_ofs %= 8;
1292
1293     if (dst_ofs) {
1294         unsigned int chunk = MIN(n_bits, 8 - dst_ofs);
1295
1296         *dst |= ((1 << chunk) - 1) << dst_ofs;
1297
1298         n_bits -= chunk;
1299         if (!n_bits) {
1300             return;
1301         }
1302
1303         dst--;
1304     }
1305
1306     while (n_bits >= 8) {
1307         *dst-- = 0xff;
1308         n_bits -= 8;
1309     }
1310
1311     if (n_bits) {
1312         *dst |= (1 << n_bits) - 1;
1313     }
1314 }
1315
1316 /* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits.
1317  * Returns false if any 1-bits are found, otherwise true.  'dst' is 'dst_len'
1318  * bytes long.
1319  *
1320  * If you consider all of 'dst' to be a single unsigned integer in network byte
1321  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1322  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1323  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1324  * 2], and so on.
1325  *
1326  * Required invariant:
1327  *   dst_ofs + n_bits <= dst_len * 8
1328  */
1329 bool
1330 bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs,
1331                      unsigned int n_bits)
1332 {
1333     const uint8_t *p = p_;
1334
1335     if (!n_bits) {
1336         return true;
1337     }
1338
1339     p += len - (ofs / 8 + 1);
1340     ofs %= 8;
1341
1342     if (ofs) {
1343         unsigned int chunk = MIN(n_bits, 8 - ofs);
1344
1345         if (*p & (((1 << chunk) - 1) << ofs)) {
1346             return false;
1347         }
1348
1349         n_bits -= chunk;
1350         if (!n_bits) {
1351             return true;
1352         }
1353
1354         p--;
1355     }
1356
1357     while (n_bits >= 8) {
1358         if (*p) {
1359             return false;
1360         }
1361         n_bits -= 8;
1362         p--;
1363     }
1364
1365     if (n_bits && *p & ((1 << n_bits) - 1)) {
1366         return false;
1367     }
1368
1369     return true;
1370 }
1371
1372 /* Scans the bits in 'p' that have bit offsets 'start' (inclusive) through
1373  * 'end' (exclusive) for the first bit with value 'target'.  If one is found,
1374  * returns its offset, otherwise 'end'.  'p' is 'len' bytes long.
1375  *
1376  * If you consider all of 'p' to be a single unsigned integer in network byte
1377  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1378  * with value 1 in p[len - 1], bit 1 is the bit with value 2, bit 2 is the bit
1379  * with value 4, ..., bit 8 is the bit with value 1 in p[len - 2], and so on.
1380  *
1381  * Required invariant:
1382  *   start <= end
1383  */
1384 unsigned int
1385 bitwise_scan(const void *p, unsigned int len, bool target, unsigned int start,
1386              unsigned int end)
1387 {
1388     unsigned int ofs;
1389
1390     for (ofs = start; ofs < end; ofs++) {
1391         if (bitwise_get_bit(p, len, ofs) == target) {
1392             break;
1393         }
1394     }
1395     return ofs;
1396 }
1397
1398 /* Scans the bits in 'p' that have bit offsets 'start' (inclusive) through
1399  * 'end' (exclusive) for the first bit with value 'target', in reverse order.
1400  * If one is found, returns its offset, otherwise 'end'.  'p' is 'len' bytes
1401  * long.
1402  *
1403  * If you consider all of 'p' to be a single unsigned integer in network byte
1404  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1405  * with value 1 in p[len - 1], bit 1 is the bit with value 2, bit 2 is the bit
1406  * with value 4, ..., bit 8 is the bit with value 1 in p[len - 2], and so on.
1407  *
1408  * To scan an entire bit array in reverse order, specify start == len * 8 - 1
1409  * and end == -1, in which case the return value is nonnegative if successful
1410  * and -1 if no 'target' match is found.
1411  *
1412  * Required invariant:
1413  *   start >= end
1414  */
1415 int
1416 bitwise_rscan(const void *p, unsigned int len, bool target, int start, int end)
1417 {
1418     const uint8_t *s = p;
1419     int start_byte = len - (start / 8 + 1);
1420     int end_byte = len - (end / 8 + 1);
1421     int ofs_byte;
1422     int ofs;
1423     uint8_t the_byte;
1424
1425     /* Find the target in the start_byte from starting offset */
1426     ofs_byte = start_byte;
1427     the_byte = s[ofs_byte];
1428     for (ofs = start % 8; ofs >= 0; ofs--) {
1429         if (((the_byte & (1u << ofs)) != 0) == target) {
1430             break;
1431         }
1432     }
1433     if (ofs < 0) {
1434         /* Target not found in start byte, continue searching byte by byte */
1435         for (ofs_byte = start_byte + 1; ofs_byte <= end_byte; ofs_byte++) {
1436             if ((target && s[ofs_byte])
1437                     || (!target && (s[ofs_byte] != 0xff))) {
1438                break;
1439             }
1440         }
1441         if (ofs_byte > end_byte) {
1442             return end;
1443         }
1444         the_byte = s[ofs_byte];
1445         /* Target is in the_byte, find it bit by bit */
1446         for (ofs = 7; ofs >= 0; ofs--) {
1447             if (((the_byte & (1u << ofs)) != 0) == target) {
1448                 break;
1449             }
1450         }
1451     }
1452     int ret = (len - ofs_byte) * 8 - (8 - ofs);
1453     if (ret < end) {
1454         return end;
1455     }
1456     return ret;
1457 }
1458
1459 /* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits
1460  * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long.
1461  *
1462  * If you consider all of 'dst' to be a single unsigned integer in network byte
1463  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1464  * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is
1465  * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len -
1466  * 2], and so on.
1467  *
1468  * Required invariants:
1469  *   dst_ofs + n_bits <= dst_len * 8
1470  *   n_bits <= 64
1471  */
1472 void
1473 bitwise_put(uint64_t value,
1474             void *dst, unsigned int dst_len, unsigned int dst_ofs,
1475             unsigned int n_bits)
1476 {
1477     ovs_be64 n_value = htonll(value);
1478     bitwise_copy(&n_value, sizeof n_value, 0,
1479                  dst, dst_len, dst_ofs,
1480                  n_bits);
1481 }
1482
1483 /* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src',
1484  * which is 'src_len' bytes long.
1485  *
1486  * If you consider all of 'src' to be a single unsigned integer in network byte
1487  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1488  * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is
1489  * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len -
1490  * 2], and so on.
1491  *
1492  * Required invariants:
1493  *   src_ofs + n_bits <= src_len * 8
1494  *   n_bits <= 64
1495  */
1496 uint64_t
1497 bitwise_get(const void *src, unsigned int src_len,
1498             unsigned int src_ofs, unsigned int n_bits)
1499 {
1500     ovs_be64 value = htonll(0);
1501
1502     bitwise_copy(src, src_len, src_ofs,
1503                  &value, sizeof value, 0,
1504                  n_bits);
1505     return ntohll(value);
1506 }
1507
1508 /* Returns the value of the bit with offset 'ofs' in 'src', which is 'len'
1509  * bytes long.
1510  *
1511  * If you consider all of 'src' to be a single unsigned integer in network byte
1512  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1513  * with value 1 in src[len - 1], bit 1 is the bit with value 2, bit 2 is the
1514  * bit with value 4, ..., bit 8 is the bit with value 1 in src[len - 2], and so
1515  * on.
1516  *
1517  * Required invariants:
1518  *   ofs < len * 8
1519  */
1520 bool
1521 bitwise_get_bit(const void *src_, unsigned int len, unsigned int ofs)
1522 {
1523     const uint8_t *src = src_;
1524
1525     return (src[len - (ofs / 8 + 1)] & (1u << (ofs % 8))) != 0;
1526 }
1527
1528 /* Sets the bit with offset 'ofs' in 'dst', which is 'len' bytes long, to 0.
1529  *
1530  * If you consider all of 'dst' to be a single unsigned integer in network byte
1531  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1532  * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
1533  * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
1534  * on.
1535  *
1536  * Required invariants:
1537  *   ofs < len * 8
1538  */
1539 void
1540 bitwise_put0(void *dst_, unsigned int len, unsigned int ofs)
1541 {
1542     uint8_t *dst = dst_;
1543
1544     dst[len - (ofs / 8 + 1)] &= ~(1u << (ofs % 8));
1545 }
1546
1547 /* Sets the bit with offset 'ofs' in 'dst', which is 'len' bytes long, to 1.
1548  *
1549  * If you consider all of 'dst' to be a single unsigned integer in network byte
1550  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1551  * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
1552  * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
1553  * on.
1554  *
1555  * Required invariants:
1556  *   ofs < len * 8
1557  */
1558 void
1559 bitwise_put1(void *dst_, unsigned int len, unsigned int ofs)
1560 {
1561     uint8_t *dst = dst_;
1562
1563     dst[len - (ofs / 8 + 1)] |= 1u << (ofs % 8);
1564 }
1565
1566 /* Sets the bit with offset 'ofs' in 'dst', which is 'len' bytes long, to 'b'.
1567  *
1568  * If you consider all of 'dst' to be a single unsigned integer in network byte
1569  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1570  * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
1571  * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
1572  * on.
1573  *
1574  * Required invariants:
1575  *   ofs < len * 8
1576  */
1577 void
1578 bitwise_put_bit(void *dst, unsigned int len, unsigned int ofs, bool b)
1579 {
1580     if (b) {
1581         bitwise_put1(dst, len, ofs);
1582     } else {
1583         bitwise_put0(dst, len, ofs);
1584     }
1585 }
1586
1587 /* Flips the bit with offset 'ofs' in 'dst', which is 'len' bytes long.
1588  *
1589  * If you consider all of 'dst' to be a single unsigned integer in network byte
1590  * order, then bit N is the bit with value 2**N.  That is, bit 0 is the bit
1591  * with value 1 in dst[len - 1], bit 1 is the bit with value 2, bit 2 is the
1592  * bit with value 4, ..., bit 8 is the bit with value 1 in dst[len - 2], and so
1593  * on.
1594  *
1595  * Required invariants:
1596  *   ofs < len * 8
1597  */
1598 void
1599 bitwise_toggle_bit(void *dst_, unsigned int len, unsigned int ofs)
1600 {
1601     uint8_t *dst = dst_;
1602
1603     dst[len - (ofs / 8 + 1)] ^= 1u << (ofs % 8);
1604 }
1605 \f
1606 /* ovs_scan */
1607
1608 struct scan_spec {
1609     unsigned int width;
1610     enum {
1611         SCAN_DISCARD,
1612         SCAN_CHAR,
1613         SCAN_SHORT,
1614         SCAN_INT,
1615         SCAN_LONG,
1616         SCAN_LLONG,
1617         SCAN_INTMAX_T,
1618         SCAN_PTRDIFF_T,
1619         SCAN_SIZE_T
1620     } type;
1621 };
1622
1623 static const char *
1624 skip_spaces(const char *s)
1625 {
1626     while (isspace((unsigned char) *s)) {
1627         s++;
1628     }
1629     return s;
1630 }
1631
1632 static const char *
1633 scan_int(const char *s, const struct scan_spec *spec, int base, va_list *args)
1634 {
1635     const char *start = s;
1636     uintmax_t value;
1637     bool negative;
1638     int n_digits;
1639
1640     negative = *s == '-';
1641     s += *s == '-' || *s == '+';
1642
1643     if ((!base || base == 16) && *s == '0' && (s[1] == 'x' || s[1] == 'X')) {
1644         base = 16;
1645         s += 2;
1646     } else if (!base) {
1647         base = *s == '0' ? 8 : 10;
1648     }
1649
1650     if (s - start >= spec->width) {
1651         return NULL;
1652     }
1653
1654     value = 0;
1655     n_digits = 0;
1656     while (s - start < spec->width) {
1657         int digit = hexit_value(*s);
1658
1659         if (digit < 0 || digit >= base) {
1660             break;
1661         }
1662         value = value * base + digit;
1663         n_digits++;
1664         s++;
1665     }
1666     if (!n_digits) {
1667         return NULL;
1668     }
1669
1670     if (negative) {
1671         value = -value;
1672     }
1673
1674     switch (spec->type) {
1675     case SCAN_DISCARD:
1676         break;
1677     case SCAN_CHAR:
1678         *va_arg(*args, char *) = value;
1679         break;
1680     case SCAN_SHORT:
1681         *va_arg(*args, short int *) = value;
1682         break;
1683     case SCAN_INT:
1684         *va_arg(*args, int *) = value;
1685         break;
1686     case SCAN_LONG:
1687         *va_arg(*args, long int *) = value;
1688         break;
1689     case SCAN_LLONG:
1690         *va_arg(*args, long long int *) = value;
1691         break;
1692     case SCAN_INTMAX_T:
1693         *va_arg(*args, intmax_t *) = value;
1694         break;
1695     case SCAN_PTRDIFF_T:
1696         *va_arg(*args, ptrdiff_t *) = value;
1697         break;
1698     case SCAN_SIZE_T:
1699         *va_arg(*args, size_t *) = value;
1700         break;
1701     }
1702     return s;
1703 }
1704
1705 static const char *
1706 skip_digits(const char *s)
1707 {
1708     while (*s >= '0' && *s <= '9') {
1709         s++;
1710     }
1711     return s;
1712 }
1713
1714 static const char *
1715 scan_float(const char *s, const struct scan_spec *spec, va_list *args)
1716 {
1717     const char *start = s;
1718     long double value;
1719     char *tail;
1720     char *copy;
1721     bool ok;
1722
1723     s += *s == '+' || *s == '-';
1724     s = skip_digits(s);
1725     if (*s == '.') {
1726         s = skip_digits(s + 1);
1727     }
1728     if (*s == 'e' || *s == 'E') {
1729         s++;
1730         s += *s == '+' || *s == '-';
1731         s = skip_digits(s);
1732     }
1733
1734     if (s - start > spec->width) {
1735         s = start + spec->width;
1736     }
1737
1738     copy = xmemdup0(start, s - start);
1739     value = strtold(copy, &tail);
1740     ok = *tail == '\0';
1741     free(copy);
1742     if (!ok) {
1743         return NULL;
1744     }
1745
1746     switch (spec->type) {
1747     case SCAN_DISCARD:
1748         break;
1749     case SCAN_INT:
1750         *va_arg(*args, float *) = value;
1751         break;
1752     case SCAN_LONG:
1753         *va_arg(*args, double *) = value;
1754         break;
1755     case SCAN_LLONG:
1756         *va_arg(*args, long double *) = value;
1757         break;
1758
1759     case SCAN_CHAR:
1760     case SCAN_SHORT:
1761     case SCAN_INTMAX_T:
1762     case SCAN_PTRDIFF_T:
1763     case SCAN_SIZE_T:
1764         OVS_NOT_REACHED();
1765     }
1766     return s;
1767 }
1768
1769 static void
1770 scan_output_string(const struct scan_spec *spec,
1771                    const char *s, size_t n,
1772                    va_list *args)
1773 {
1774     if (spec->type != SCAN_DISCARD) {
1775         char *out = va_arg(*args, char *);
1776         memcpy(out, s, n);
1777         out[n] = '\0';
1778     }
1779 }
1780
1781 static const char *
1782 scan_string(const char *s, const struct scan_spec *spec, va_list *args)
1783 {
1784     size_t n;
1785
1786     for (n = 0; n < spec->width; n++) {
1787         if (!s[n] || isspace((unsigned char) s[n])) {
1788             break;
1789         }
1790     }
1791     if (!n) {
1792         return NULL;
1793     }
1794
1795     scan_output_string(spec, s, n, args);
1796     return s + n;
1797 }
1798
1799 static const char *
1800 parse_scanset(const char *p_, unsigned long *set, bool *complemented)
1801 {
1802     const uint8_t *p = (const uint8_t *) p_;
1803
1804     *complemented = *p == '^';
1805     p += *complemented;
1806
1807     if (*p == ']') {
1808         bitmap_set1(set, ']');
1809         p++;
1810     }
1811
1812     while (*p && *p != ']') {
1813         if (p[1] == '-' && p[2] != ']' && p[2] > *p) {
1814             bitmap_set_multiple(set, *p, p[2] - *p + 1, true);
1815             p += 3;
1816         } else {
1817             bitmap_set1(set, *p++);
1818         }
1819     }
1820     if (*p == ']') {
1821         p++;
1822     }
1823     return (const char *) p;
1824 }
1825
1826 static const char *
1827 scan_set(const char *s, const struct scan_spec *spec, const char **pp,
1828          va_list *args)
1829 {
1830     unsigned long set[BITMAP_N_LONGS(UCHAR_MAX + 1)];
1831     bool complemented;
1832     unsigned int n;
1833
1834     /* Parse the scan set. */
1835     memset(set, 0, sizeof set);
1836     *pp = parse_scanset(*pp, set, &complemented);
1837
1838     /* Parse the data. */
1839     n = 0;
1840     while (s[n]
1841            && bitmap_is_set(set, (unsigned char) s[n]) == !complemented
1842            && n < spec->width) {
1843         n++;
1844     }
1845     if (!n) {
1846         return NULL;
1847     }
1848     scan_output_string(spec, s, n, args);
1849     return s + n;
1850 }
1851
1852 static const char *
1853 scan_chars(const char *s, const struct scan_spec *spec, va_list *args)
1854 {
1855     unsigned int n = spec->width == UINT_MAX ? 1 : spec->width;
1856
1857     if (strlen(s) < n) {
1858         return NULL;
1859     }
1860     if (spec->type != SCAN_DISCARD) {
1861         memcpy(va_arg(*args, char *), s, n);
1862     }
1863     return s + n;
1864 }
1865
1866 static bool
1867 ovs_scan__(const char *s, int *n, const char *format, va_list *args)
1868 {
1869     const char *const start = s;
1870     bool ok = false;
1871     const char *p;
1872
1873     p = format;
1874     while (*p != '\0') {
1875         struct scan_spec spec;
1876         unsigned char c = *p++;
1877         bool discard;
1878
1879         if (isspace(c)) {
1880             s = skip_spaces(s);
1881             continue;
1882         } else if (c != '%') {
1883             if (*s != c) {
1884                 goto exit;
1885             }
1886             s++;
1887             continue;
1888         } else if (*p == '%') {
1889             if (*s++ != '%') {
1890                 goto exit;
1891             }
1892             p++;
1893             continue;
1894         }
1895
1896         /* Parse '*' flag. */
1897         discard = *p == '*';
1898         p += discard;
1899
1900         /* Parse field width. */
1901         spec.width = 0;
1902         while (*p >= '0' && *p <= '9') {
1903             spec.width = spec.width * 10 + (*p++ - '0');
1904         }
1905         if (spec.width == 0) {
1906             spec.width = UINT_MAX;
1907         }
1908
1909         /* Parse type modifier. */
1910         switch (*p) {
1911         case 'h':
1912             if (p[1] == 'h') {
1913                 spec.type = SCAN_CHAR;
1914                 p += 2;
1915             } else {
1916                 spec.type = SCAN_SHORT;
1917                 p++;
1918             }
1919             break;
1920
1921         case 'j':
1922             spec.type = SCAN_INTMAX_T;
1923             p++;
1924             break;
1925
1926         case 'l':
1927             if (p[1] == 'l') {
1928                 spec.type = SCAN_LLONG;
1929                 p += 2;
1930             } else {
1931                 spec.type = SCAN_LONG;
1932                 p++;
1933             }
1934             break;
1935
1936         case 'L':
1937         case 'q':
1938             spec.type = SCAN_LLONG;
1939             p++;
1940             break;
1941
1942         case 't':
1943             spec.type = SCAN_PTRDIFF_T;
1944             p++;
1945             break;
1946
1947         case 'z':
1948             spec.type = SCAN_SIZE_T;
1949             p++;
1950             break;
1951
1952         default:
1953             spec.type = SCAN_INT;
1954             break;
1955         }
1956
1957         if (discard) {
1958             spec.type = SCAN_DISCARD;
1959         }
1960
1961         c = *p++;
1962         if (c != 'c' && c != 'n' && c != '[') {
1963             s = skip_spaces(s);
1964         }
1965         switch (c) {
1966         case 'd':
1967             s = scan_int(s, &spec, 10, args);
1968             break;
1969
1970         case 'i':
1971             s = scan_int(s, &spec, 0, args);
1972             break;
1973
1974         case 'o':
1975             s = scan_int(s, &spec, 8, args);
1976             break;
1977
1978         case 'u':
1979             s = scan_int(s, &spec, 10, args);
1980             break;
1981
1982         case 'x':
1983         case 'X':
1984             s = scan_int(s, &spec, 16, args);
1985             break;
1986
1987         case 'e':
1988         case 'f':
1989         case 'g':
1990         case 'E':
1991         case 'G':
1992             s = scan_float(s, &spec, args);
1993             break;
1994
1995         case 's':
1996             s = scan_string(s, &spec, args);
1997             break;
1998
1999         case '[':
2000             s = scan_set(s, &spec, &p, args);
2001             break;
2002
2003         case 'c':
2004             s = scan_chars(s, &spec, args);
2005             break;
2006
2007         case 'n':
2008             if (spec.type != SCAN_DISCARD) {
2009                 *va_arg(*args, int *) = s - start;
2010             }
2011             break;
2012         }
2013
2014         if (!s) {
2015             goto exit;
2016         }
2017     }
2018     if (n) {
2019         *n = s - start;
2020     }
2021
2022     ok = true;
2023 exit:
2024     return ok;
2025 }
2026
2027 /* This is an implementation of the standard sscanf() function, with the
2028  * following exceptions:
2029  *
2030  *   - It returns true if the entire format was successfully scanned and
2031  *     converted, false if any conversion failed.
2032  *
2033  *   - The standard doesn't define sscanf() behavior when an out-of-range value
2034  *     is scanned, e.g. if a "%"PRIi8 conversion scans "-1" or "0x1ff".  Some
2035  *     implementations consider this an error and stop scanning.  This
2036  *     implementation never considers an out-of-range value an error; instead,
2037  *     it stores the least-significant bits of the converted value in the
2038  *     destination, e.g. the value 255 for both examples earlier.
2039  *
2040  *   - Only single-byte characters are supported, that is, the 'l' modifier
2041  *     on %s, %[, and %c is not supported.  The GNU extension 'a' modifier is
2042  *     also not supported.
2043  *
2044  *   - %p is not supported.
2045  */
2046 bool
2047 ovs_scan(const char *s, const char *format, ...)
2048 {
2049     va_list args;
2050     bool res;
2051
2052     va_start(args, format);
2053     res = ovs_scan__(s, NULL, format, &args);
2054     va_end(args);
2055     return res;
2056 }
2057
2058 /*
2059  * This function is similar to ovs_scan(), with an extra parameter `n` added to
2060  * return the number of scanned characters.
2061  */
2062 bool
2063 ovs_scan_len(const char *s, int *n, const char *format, ...)
2064 {
2065     va_list args;
2066     bool success;
2067     int n1;
2068
2069     va_start(args, format);
2070     success = ovs_scan__(s + *n, &n1, format, &args);
2071     va_end(args);
2072     if (success) {
2073         *n = *n + n1;
2074     }
2075     return success;
2076 }
2077
2078 void
2079 xsleep(unsigned int seconds)
2080 {
2081     ovsrcu_quiesce_start();
2082 #ifdef _WIN32
2083     Sleep(seconds * 1000);
2084 #else
2085     sleep(seconds);
2086 #endif
2087     ovsrcu_quiesce_end();
2088 }
2089
2090 /* Determine whether standard output is a tty or not. This is useful to decide
2091  * whether to use color output or not when --color option for utilities is set
2092  * to `auto`.
2093  */
2094 bool
2095 is_stdout_a_tty(void)
2096 {
2097     char const *t = getenv("TERM");
2098     return (isatty(STDOUT_FILENO) && t && strcmp(t, "dumb") != 0);
2099 }
2100
2101 #ifdef _WIN32
2102 \f
2103 char *
2104 ovs_format_message(int error)
2105 {
2106     enum { BUFSIZE = sizeof strerror_buffer_get()->s };
2107     char *buffer = strerror_buffer_get()->s;
2108
2109     if (error == 0) {
2110         /* See ovs_strerror */
2111         return "Success";
2112     }
2113
2114     FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
2115                   NULL, error, 0, buffer, BUFSIZE, NULL);
2116     return buffer;
2117 }
2118
2119 /* Returns a null-terminated string that explains the last error.
2120  * Use this function to get the error string for WINAPI calls. */
2121 char *
2122 ovs_lasterror_to_string(void)
2123 {
2124     return ovs_format_message(GetLastError());
2125 }
2126
2127 int
2128 ftruncate(int fd, off_t length)
2129 {
2130     int error;
2131
2132     error = _chsize_s(fd, length);
2133     if (error) {
2134         return -1;
2135     }
2136     return 0;
2137 }
2138
2139 OVS_CONSTRUCTOR(winsock_start) {
2140     WSADATA wsaData;
2141     int error;
2142
2143     error = WSAStartup(MAKEWORD(2, 2), &wsaData);
2144     if (error != 0) {
2145         VLOG_FATAL("WSAStartup failed: %s", sock_strerror(sock_errno()));
2146    }
2147 }
2148 #endif