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