lib/util.c

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