lib/util.h

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 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 #ifndef UTIL_H
  18 #define UTIL_H 1
  19
  20 #include <sys/types.h>
  21 #include <netinet/in.h>
  22 #include <arpa/inet.h>
  23 #include <inttypes.h>
  24 #include <limits.h>
  25 #include <stdarg.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include "compiler.h"
  30 #include "util.h"
  31 #include "openvswitch/util.h"
  32
  33 extern char *program_name;
  34
  35 #define __ARRAY_SIZE_NOCHECK(ARRAY) (sizeof(ARRAY) / sizeof((ARRAY)[0]))
  36 #if __GNUC__ && !defined(__cplusplus)
  37 /* return 0 for array types, 1 otherwise */
  38 #define __ARRAY_CHECK(ARRAY)                                    \
  39     !__builtin_types_compatible_p(typeof(ARRAY), typeof(&ARRAY[0]))
  40
  41 /* compile-time fail if not array */
  42 #define __ARRAY_FAIL(ARRAY) (sizeof(char[-2*!__ARRAY_CHECK(ARRAY)]))
  43 #define __ARRAY_SIZE(ARRAY)                                     \
  44     __builtin_choose_expr(__ARRAY_CHECK(ARRAY),                 \
  45         __ARRAY_SIZE_NOCHECK(ARRAY), __ARRAY_FAIL(ARRAY))
  46 #elif defined(__cplusplus)
  47 #define __ARRAY_SIZE(ARRAY) ( \
  48    0 * sizeof(reinterpret_cast<const ::Bad_arg_to_ARRAY_SIZE *>(ARRAY)) + \
  49    0 * sizeof(::Bad_arg_to_ARRAY_SIZE::check_type((ARRAY), &(ARRAY))) + \
  50    sizeof(ARRAY) / sizeof((ARRAY)[0]) )
  51
  52 struct Bad_arg_to_ARRAY_SIZE {
  53    class Is_pointer;
  54    class Is_array {};
  55    template <typename T>
  56    static Is_pointer check_type(const T *, const T * const *);
  57    static Is_array check_type(const void *, const void *);
  58 };
  59 #else
  60 #define __ARRAY_SIZE(ARRAY) __ARRAY_SIZE_NOCHECK(ARRAY)
  61 #endif
  62
  63
  64 /* This system's cache line size, in bytes.
  65  * Being wrong hurts performance but not correctness. */
  66 #define CACHE_LINE_SIZE 64
  67 BUILD_ASSERT_DECL(IS_POW2(CACHE_LINE_SIZE));
  68
  69 /* Cacheline marking is typically done using zero-sized array.
  70  * However MSVC doesn't like zero-sized array in struct/union.
  71  * C4200: https://msdn.microsoft.com/en-us/library/79wf64bc.aspx
  72  */
  73 typedef uint8_t OVS_CACHE_LINE_MARKER[1];
  74
  75 static inline void
  76 ovs_prefetch_range(const void *start, size_t size)
  77 {
  78     const char *addr = (const char *)start;
  79     size_t ofs;
  80
  81     for (ofs = 0; ofs < size; ofs += CACHE_LINE_SIZE) {
  82         OVS_PREFETCH(addr + ofs);
  83     }
  84 }
  85
  86 #ifndef MIN
  87 #define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
  88 #endif
  89
  90 #ifndef MAX
  91 #define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
  92 #endif
  93
  94 /* Comparisons for ints with modular arithmetic */
  95 #define INT_MOD_LT(a,b)     ((int) ((a)-(b)) < 0)
  96 #define INT_MOD_LEQ(a,b)    ((int) ((a)-(b)) <= 0)
  97 #define INT_MOD_GT(a,b)     ((int) ((a)-(b)) > 0)
  98 #define INT_MOD_GEQ(a,b)    ((int) ((a)-(b)) >= 0)
  99
 100 #define INT_MOD_MIN(a, b)   ((INT_MOD_LT(a, b)) ? (a) : (b))
 101 #define INT_MOD_MAX(a, b)   ((INT_MOD_GT(a, b)) ? (a) : (b))
 102
 103 #define OVS_NOT_REACHED() abort()
 104
 105 /* Use "%"PRIuSIZE to format size_t with printf(). */
 106 #ifdef _WIN32
 107 #define PRIdSIZE "Id"
 108 #define PRIiSIZE "Ii"
 109 #define PRIoSIZE "Io"
 110 #define PRIuSIZE "Iu"
 111 #define PRIxSIZE "Ix"
 112 #define PRIXSIZE "IX"
 113 #else
 114 #define PRIdSIZE "zd"
 115 #define PRIiSIZE "zi"
 116 #define PRIoSIZE "zo"
 117 #define PRIuSIZE "zu"
 118 #define PRIxSIZE "zx"
 119 #define PRIXSIZE "zX"
 120 #endif
 121
 122 #ifndef _WIN32
 123 typedef uint32_t HANDLE;
 124 #endif
 125
 126 #ifdef  __cplusplus
 127 extern "C" {
 128 #endif
 129
 130 #define set_program_name(name) \
 131         ovs_set_program_name(name, OVS_PACKAGE_VERSION)
 132
 133 const char *get_subprogram_name(void);
 134     void set_subprogram_name(const char *);
 135
 136 unsigned int get_page_size(void);
 137 long long int get_boot_time(void);
 138
 139 void ctl_timeout_setup(unsigned int secs);
 140
 141 void ovs_print_version(uint8_t min_ofp, uint8_t max_ofp);
 142
 143 OVS_NO_RETURN void out_of_memory(void);
 144 void *xmalloc(size_t) MALLOC_LIKE;
 145 void *xcalloc(size_t, size_t) MALLOC_LIKE;
 146 void *xzalloc(size_t) MALLOC_LIKE;
 147 void *xrealloc(void *, size_t);
 148 void *xmemdup(const void *, size_t) MALLOC_LIKE;
 149 char *xmemdup0(const char *, size_t) MALLOC_LIKE;
 150 char *xstrdup(const char *) MALLOC_LIKE;
 151 char *nullable_xstrdup(const char *) MALLOC_LIKE;
 152 bool nullable_string_is_equal(const char *a, const char *b);
 153 char *xasprintf(const char *format, ...) OVS_PRINTF_FORMAT(1, 2) MALLOC_LIKE;
 154 char *xvasprintf(const char *format, va_list) OVS_PRINTF_FORMAT(1, 0) MALLOC_LIKE;
 155 void *x2nrealloc(void *p, size_t *n, size_t s);
 156
 157 void *xmalloc_cacheline(size_t) MALLOC_LIKE;
 158 void *xzalloc_cacheline(size_t) MALLOC_LIKE;
 159 void free_cacheline(void *);
 160
 161 void ovs_strlcpy(char *dst, const char *src, size_t size);
 162 void ovs_strzcpy(char *dst, const char *src, size_t size);
 163
 164 int string_ends_with(const char *str, const char *suffix);
 165
 166 /* The C standards say that neither the 'dst' nor 'src' argument to
 167  * memcpy() may be null, even if 'n' is zero.  This wrapper tolerates
 168  * the null case. */
 169 static inline void
 170 nullable_memcpy(void *dst, const void *src, size_t n)
 171 {
 172     if (n) {
 173         memcpy(dst, src, n);
 174     }
 175 }
 176
 177 /* The C standards say that the 'dst' argument to memset may not be
 178  * null, even if 'n' is zero.  This wrapper tolerates the null case. */
 179 static inline void
 180 nullable_memset(void *dst, int c, size_t n)
 181 {
 182     if (n) {
 183         memset(dst, c, n);
 184     }
 185 }
 186
 187 /* Copy string SRC to DST, but no more bytes than the shorter of DST or SRC.
 188  * DST and SRC must both be char arrays, not pointers, and with GNU C, this
 189  * raises a compiler error if either DST or SRC is a pointer instead of an
 190  * array. */
 191 #define ovs_strlcpy_arrays(DST, SRC) \
 192     ovs_strlcpy(DST, SRC, MIN(ARRAY_SIZE(DST), ARRAY_SIZE(SRC)))
 193
 194 OVS_NO_RETURN void ovs_abort(int err_no, const char *format, ...)
 195     OVS_PRINTF_FORMAT(2, 3);
 196 OVS_NO_RETURN void ovs_abort_valist(int err_no, const char *format, va_list)
 197     OVS_PRINTF_FORMAT(2, 0);
 198 OVS_NO_RETURN void ovs_fatal(int err_no, const char *format, ...)
 199     OVS_PRINTF_FORMAT(2, 3);
 200 OVS_NO_RETURN void ovs_fatal_valist(int err_no, const char *format, va_list)
 201     OVS_PRINTF_FORMAT(2, 0);
 202 void ovs_error(int err_no, const char *format, ...) OVS_PRINTF_FORMAT(2, 3);
 203 void ovs_error_valist(int err_no, const char *format, va_list)
 204     OVS_PRINTF_FORMAT(2, 0);
 205 const char *ovs_retval_to_string(int);
 206 const char *ovs_strerror(int);
 207 void ovs_hex_dump(FILE *, const void *, size_t, uintptr_t offset, bool ascii);
 208
 209 bool str_to_int(const char *, int base, int *);
 210 bool str_to_long(const char *, int base, long *);
 211 bool str_to_llong(const char *, int base, long long *);
 212 bool str_to_llong_with_tail(const char *, char **, int base, long long *);
 213 bool str_to_uint(const char *, int base, unsigned int *);
 214 bool str_to_ullong(const char *, int base, unsigned long long *);
 215 bool str_to_llong_range(const char *, int base, long long *, long long *);
 216
 217 bool ovs_scan(const char *s, const char *format, ...) OVS_SCANF_FORMAT(2, 3);
 218 bool ovs_scan_len(const char *s, int *n, const char *format, ...);
 219
 220 bool str_to_double(const char *, double *);
 221
 222 int hexit_value(unsigned char c);
 223 uintmax_t hexits_value(const char *s, size_t n, bool *ok);
 224
 225 int parse_int_string(const char *s, uint8_t *valuep, int field_width,
 226                      char **tail);
 227
 228 const char *english_list_delimiter(size_t index, size_t total);
 229
 230 char *get_cwd(void);
 231 #ifndef _WIN32
 232 char *dir_name(const char *file_name);
 233 char *base_name(const char *file_name);
 234 #endif
 235 char *abs_file_name(const char *dir, const char *file_name);
 236 bool is_file_name_absolute(const char *);
 237
 238 char *follow_symlinks(const char *filename);
 239
 240 void ignore(bool x OVS_UNUSED);
 241 \f
 242 /* Bitwise tests. */
 243
 244 /* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
 245 #if __GNUC__ >= 4
 246 static inline int
 247 raw_ctz(uint64_t n)
 248 {
 249     /* With GCC 4.7 on 32-bit x86, if a 32-bit integer is passed as 'n', using
 250      * a plain __builtin_ctzll() here always generates an out-of-line function
 251      * call.  The test below helps it to emit a single 'bsf' instruction. */
 252     return (__builtin_constant_p(n <= UINT32_MAX) && n <= UINT32_MAX
 253             ? __builtin_ctz(n)
 254             : __builtin_ctzll(n));
 255 }
 256
 257 static inline int
 258 raw_clz64(uint64_t n)
 259 {
 260     return __builtin_clzll(n);
 261 }
 262 #elif _MSC_VER
 263 static inline int
 264 raw_ctz(uint64_t n)
 265 {
 266 #ifdef _WIN64
 267     unsigned long r = 0;
 268     _BitScanForward64(&r, n);
 269     return r;
 270 #else
 271     unsigned long low = n, high, r = 0;
 272     if (_BitScanForward(&r, low)) {
 273         return r;
 274     }
 275     high = n >> 32;
 276     _BitScanForward(&r, high);
 277     return r + 32;
 278 #endif
 279 }
 280
 281 static inline int
 282 raw_clz64(uint64_t n)
 283 {
 284 #ifdef _WIN64
 285     unsigned long r = 0;
 286     _BitScanReverse64(&r, n);
 287     return 63 - r;
 288 #else
 289     unsigned long low, high = n >> 32, r = 0;
 290     if (_BitScanReverse(&r, high)) {
 291         return 31 - r;
 292     }
 293     low = n;
 294     _BitScanReverse(&r, low);
 295     return 63 - r;
 296 #endif
 297 }
 298 #else
 299 /* Defined in util.c. */
 300 int raw_ctz(uint64_t n);
 301 int raw_clz64(uint64_t n);
 302 #endif
 303
 304 /* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
 305 static inline int
 306 ctz32(uint32_t n)
 307 {
 308     return n ? raw_ctz(n) : 32;
 309 }
 310
 311 /* Returns the number of trailing 0-bits in 'n', or 64 if 'n' is 0. */
 312 static inline int
 313 ctz64(uint64_t n)
 314 {
 315     return n ? raw_ctz(n) : 64;
 316 }
 317
 318 /* Returns the number of leading 0-bits in 'n', or 32 if 'n' is 0. */
 319 static inline int
 320 clz32(uint32_t n)
 321 {
 322     return n ? raw_clz64(n) - 32 : 32;
 323 }
 324
 325 /* Returns the number of leading 0-bits in 'n', or 64 if 'n' is 0. */
 326 static inline int
 327 clz64(uint64_t n)
 328 {
 329     return n ? raw_clz64(n) : 64;
 330 }
 331
 332 /* Given a word 'n', calculates floor(log_2('n')).  This is equivalent
 333  * to finding the bit position of the most significant one bit in 'n'.  It is
 334  * an error to call this function with 'n' == 0. */
 335 static inline int
 336 log_2_floor(uint64_t n)
 337 {
 338     return 63 - raw_clz64(n);
 339 }
 340
 341 /* Given a word 'n', calculates ceil(log_2('n')).  It is an error to
 342  * call this function with 'n' == 0. */
 343 static inline int
 344 log_2_ceil(uint64_t n)
 345 {
 346     return log_2_floor(n) + !is_pow2(n);
 347 }
 348
 349 /* unsigned int count_1bits(uint64_t x):
 350  *
 351  * Returns the number of 1-bits in 'x', between 0 and 64 inclusive. */
 352 #if UINTPTR_MAX == UINT64_MAX
 353 static inline unsigned int
 354 count_1bits(uint64_t x)
 355 {
 356 #if __GNUC__ >= 4 && __POPCNT__
 357     return __builtin_popcountll(x);
 358 #else
 359     /* This portable implementation is the fastest one we know of for 64
 360      * bits, and about 3x faster than GCC 4.7 __builtin_popcountll(). */
 361     const uint64_t h55 = UINT64_C(0x5555555555555555);
 362     const uint64_t h33 = UINT64_C(0x3333333333333333);
 363     const uint64_t h0F = UINT64_C(0x0F0F0F0F0F0F0F0F);
 364     const uint64_t h01 = UINT64_C(0x0101010101010101);
 365     x -= (x >> 1) & h55;               /* Count of each 2 bits in-place. */
 366     x = (x & h33) + ((x >> 2) & h33);  /* Count of each 4 bits in-place. */
 367     x = (x + (x >> 4)) & h0F;          /* Count of each 8 bits in-place. */
 368     return (x * h01) >> 56;            /* Sum of all bytes. */
 369 #endif
 370 }
 371 #else /* Not 64-bit. */
 372 #if __GNUC__ >= 4 && __POPCNT__
 373 static inline unsigned int
 374 count_1bits_32__(uint32_t x)
 375 {
 376     return __builtin_popcount(x);
 377 }
 378 #else
 379 #define NEED_COUNT_1BITS_8 1
 380 extern const uint8_t count_1bits_8[256];
 381 static inline unsigned int
 382 count_1bits_32__(uint32_t x)
 383 {
 384     /* This portable implementation is the fastest one we know of for 32 bits,
 385      * and faster than GCC __builtin_popcount(). */
 386     return (count_1bits_8[x & 0xff] +
 387             count_1bits_8[(x >> 8) & 0xff] +
 388             count_1bits_8[(x >> 16) & 0xff] +
 389             count_1bits_8[x >> 24]);
 390 }
 391 #endif
 392 static inline unsigned int
 393 count_1bits(uint64_t x)
 394 {
 395     return count_1bits_32__(x) + count_1bits_32__(x >> 32);
 396 }
 397 #endif
 398
 399 /* Returns the rightmost 1-bit in 'x' (e.g. 01011000 => 00001000), or 0 if 'x'
 400  * is 0. */
 401 static inline uintmax_t
 402 rightmost_1bit(uintmax_t x)
 403 {
 404     return x & -x;
 405 }
 406
 407 /* Returns 'x' with its rightmost 1-bit changed to a zero (e.g. 01011000 =>
 408  * 01010000), or 0 if 'x' is 0. */
 409 static inline uintmax_t
 410 zero_rightmost_1bit(uintmax_t x)
 411 {
 412     return x & (x - 1);
 413 }
 414
 415 /* Returns the index of the rightmost 1-bit in 'x' (e.g. 01011000 => 3), or an
 416  * undefined value if 'x' is 0. */
 417 static inline int
 418 rightmost_1bit_idx(uint64_t x)
 419 {
 420     return ctz64(x);
 421 }
 422
 423 /* Returns the index of the leftmost 1-bit in 'x' (e.g. 01011000 => 6), or an
 424  * undefined value if 'x' is 0. */
 425 static inline uint32_t
 426 leftmost_1bit_idx(uint64_t x)
 427 {
 428     return log_2_floor(x);
 429 }
 430
 431 /* Return a ovs_be32 prefix in network byte order with 'plen' highest bits set.
 432  * Shift with 32 is undefined behavior, but we rather use 64-bit shift than
 433  * compare. */
 434 static inline ovs_be32 be32_prefix_mask(int plen)
 435 {
 436     return htonl((uint64_t)UINT32_MAX << (32 - plen));
 437 }
 438 \f
 439 bool is_all_zeros(const void *, size_t);
 440 bool is_all_ones(const void *, size_t);
 441 bool is_all_byte(const void *, size_t, uint8_t byte);
 442 void bitwise_copy(const void *src, unsigned int src_len, unsigned int src_ofs,
 443                   void *dst, unsigned int dst_len, unsigned int dst_ofs,
 444                   unsigned int n_bits);
 445 void bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 446                   unsigned int n_bits);
 447 void bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs,
 448                  unsigned int n_bits);
 449 bool bitwise_is_all_zeros(const void *, unsigned int len, unsigned int ofs,
 450                           unsigned int n_bits);
 451 unsigned int bitwise_scan(const void *, unsigned int len,
 452                           bool target, unsigned int start, unsigned int end);
 453 int bitwise_rscan(const void *, unsigned int len, bool target,
 454                   int start, int end);
 455 void bitwise_put(uint64_t value,
 456                  void *dst, unsigned int dst_len, unsigned int dst_ofs,
 457                  unsigned int n_bits);
 458 uint64_t bitwise_get(const void *src, unsigned int src_len,
 459                      unsigned int src_ofs, unsigned int n_bits);
 460 bool bitwise_get_bit(const void *src, unsigned int len, unsigned int ofs);
 461 void bitwise_put0(void *dst, unsigned int len, unsigned int ofs);
 462 void bitwise_put1(void *dst, unsigned int len, unsigned int ofs);
 463 void bitwise_put_bit(void *dst, unsigned int len, unsigned int ofs, bool);
 464 void bitwise_toggle_bit(void *dst, unsigned int len, unsigned int ofs);
 465
 466 /* Returns non-zero if the parameters have equal value. */
 467 static inline int
 468 ovs_u128_equals(const ovs_u128 a, const ovs_u128 b)
 469 {
 470     return (a.u64.hi == b.u64.hi) && (a.u64.lo == b.u64.lo);
 471 }
 472
 473 /* Returns true if 'val' is 0. */
 474 static inline bool
 475 ovs_u128_is_zero(const ovs_u128 val)
 476 {
 477     return !(val.u64.hi || val.u64.lo);
 478 }
 479
 480 /* Returns true if 'val' is all ones. */
 481 static inline bool
 482 ovs_u128_is_ones(const ovs_u128 val)
 483 {
 484     return ovs_u128_equals(val, OVS_U128_MAX);
 485 }
 486
 487 /* Returns non-zero if the parameters have equal value. */
 488 static inline int
 489 ovs_be128_equals(const ovs_be128 a, const ovs_be128 b)
 490 {
 491     return (a.be64.hi == b.be64.hi) && (a.be64.lo == b.be64.lo);
 492 }
 493
 494 /* Returns true if 'val' is 0. */
 495 static inline bool
 496 ovs_be128_is_zero(const ovs_be128 val)
 497 {
 498     return !(val.be64.hi || val.be64.lo);
 499 }
 500
 501 static inline ovs_u128
 502 ovs_u128_and(const ovs_u128 a, const ovs_u128 b)
 503 {
 504     ovs_u128 dst;
 505
 506     dst.u64.hi = a.u64.hi & b.u64.hi;
 507     dst.u64.lo = a.u64.lo & b.u64.lo;
 508
 509     return dst;
 510 }
 511
 512 void xsleep(unsigned int seconds);
 513 void xnanosleep(uint64_t nanoseconds);
 514
 515 bool is_stdout_a_tty(void);
 516
 517 #ifdef _WIN32
 518 \f
 519 char *ovs_format_message(int error);
 520 char *ovs_lasterror_to_string(void);
 521 int ftruncate(int fd, off_t length);
 522 #endif
 523
 524 #ifdef  __cplusplus
 525 }
 526 #endif
 527
 528 #endif /* util.h */