| 1 |
// Copyright (c) Meta Platforms, Inc. and affiliates. |
| 2 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 3 |
|
| 4 |
/** |
| 5 |
* @file |
| 6 |
* |
| 7 |
* Miscellanous utility functions. |
| 8 |
*/ |
| 9 |
|
| 10 |
#ifndef DRGN_UTIL_H |
| 11 |
#define DRGN_UTIL_H |
| 12 |
|
| 13 |
#include <assert.h> |
| 14 |
#include <errno.h> |
| 15 |
#include <limits.h> |
| 16 |
#include <stdbool.h> |
| 17 |
#include <stdint.h> |
| 18 |
#include <stdlib.h> |
| 19 |
#include <string.h> |
| 20 |
|
| 21 |
#define _unused_ __attribute__((__unused__)) |
| 22 |
|
| 23 |
#ifndef LIBDRGN_PUBLIC |
| 24 |
#define LIBDRGN_PUBLIC __attribute__((__visibility__("default"))) |
| 25 |
#endif |
| 26 |
|
| 27 |
#if defined(__has_attribute) && __has_attribute(__fallthrough__) |
| 28 |
#define fallthrough __attribute__((__fallthrough__)) |
| 29 |
#else |
| 30 |
#define fallthrough do {} while (0) |
| 31 |
#endif |
| 32 |
|
| 33 |
#ifdef NDEBUG |
| 34 |
#define UNREACHABLE() __builtin_unreachable() |
| 35 |
#else |
| 36 |
#define UNREACHABLE() assert(false && "should not be reachable") |
| 37 |
#endif |
| 38 |
|
| 39 |
#define HOST_LITTLE_ENDIAN (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) |
| 40 |
|
| 41 |
/** |
| 42 |
* Switch statement with an enum controlling expression that must have a case |
| 43 |
* for every enumeration value and a default case. |
| 44 |
* |
| 45 |
* m4/my_c_switch_enum.m4 checks whether this works and defines a stub version |
| 46 |
* if not. Keep this definition in sync with the check. |
| 47 |
*/ |
| 48 |
#ifndef SWITCH_ENUM |
| 49 |
#define SWITCH_ENUM(expr) \ |
| 50 |
_Pragma("GCC diagnostic push") \ |
| 51 |
_Pragma("GCC diagnostic error \"-Wswitch-enum\"") \ |
| 52 |
_Pragma("GCC diagnostic error \"-Wswitch-default\"") \ |
| 53 |
switch (expr) \ |
| 54 |
_Pragma("GCC diagnostic pop") |
| 55 |
#endif |
| 56 |
|
| 57 |
#define likely(x) __builtin_expect(!!(x), 1) |
| 58 |
#define unlikely(x) __builtin_expect(!!(x), 0) |
| 59 |
|
| 60 |
/** Return whether two types or expressions have compatible types. */ |
| 61 |
#define types_compatible(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) |
| 62 |
|
| 63 |
/** Return whether an expression is an array. */ |
| 64 |
#define is_array(x) (!types_compatible(x, &(x)[0])) |
| 65 |
|
| 66 |
/** |
| 67 |
* `static_assert(assert_expression, message)` as an expression that evaluates |
| 68 |
* to `eval_expression`. |
| 69 |
*/ |
| 70 |
#define static_assert_expression(assert_expression, message, eval_expression) \ |
| 71 |
_Generic(sizeof(struct { _Static_assert(assert_expression, message); int _; }),\ |
| 72 |
default: (eval_expression)) |
| 73 |
|
| 74 |
#define sizeof_member(type, member) sizeof(((type *)0)->member) |
| 75 |
|
| 76 |
#define typeof_member(type, member) typeof(((type *)0)->member) |
| 77 |
|
| 78 |
#define container_of(ptr, type, member) \ |
| 79 |
static_assert_expression( \ |
| 80 |
types_compatible(*(ptr), ((type *)0)->member) \ |
| 81 |
|| types_compatible(*(ptr), void), \ |
| 82 |
"pointer does not match member type", \ |
| 83 |
(type *)((char *)(ptr) - offsetof(type, member)) \ |
| 84 |
) |
| 85 |
|
| 86 |
static inline bool strstartswith(const char *s, const char *prefix) |
| 87 |
{ |
| 88 |
return strncmp(s, prefix, strlen(prefix)) == 0; |
| 89 |
} |
| 90 |
|
| 91 |
static inline void *malloc_array(size_t nmemb, size_t size) |
| 92 |
{ |
| 93 |
size_t bytes; |
| 94 |
|
| 95 |
if (__builtin_mul_overflow(nmemb, size, &bytes)) { |
| 96 |
errno = ENOMEM; |
| 97 |
return NULL; |
| 98 |
} |
| 99 |
return malloc(bytes); |
| 100 |
} |
| 101 |
|
| 102 |
static inline void *malloc_flexible_array_impl(size_t struct_size, |
| 103 |
size_t element_size, |
| 104 |
size_t count) |
| 105 |
{ |
| 106 |
size_t bytes; |
| 107 |
if (__builtin_mul_overflow(element_size, count, &bytes) |
| 108 |
|| __builtin_add_overflow(bytes, struct_size, &bytes)) { |
| 109 |
errno = ENOMEM; |
| 110 |
return NULL; |
| 111 |
} |
| 112 |
return malloc(bytes); |
| 113 |
} |
| 114 |
|
| 115 |
/** |
| 116 |
* Allocate a structure with a flexible array member. |
| 117 |
* |
| 118 |
* @param[in] type Structure type. |
| 119 |
* @param[in] member Name of flexible array member in @p type. |
| 120 |
* @param[in] count Number of flexible array elements to allocate. |
| 121 |
*/ |
| 122 |
#define malloc_flexible_array(type, member, count) \ |
| 123 |
malloc_flexible_array_impl(sizeof(type), \ |
| 124 |
static_assert_expression(is_array(((type *)0)->member), \ |
| 125 |
"not an array", \ |
| 126 |
sizeof(((type *)0)->member[0])), \ |
| 127 |
count) |
| 128 |
|
| 129 |
static inline void *malloc64(uint64_t size) |
| 130 |
{ |
| 131 |
if (size > SIZE_MAX) |
| 132 |
return NULL; |
| 133 |
return malloc(size); |
| 134 |
} |
| 135 |
|
| 136 |
// glibc added reallocarray() in 2.26, but since it's so trivial, it's easier to |
| 137 |
// duplicate it here than it is to do feature detection. |
| 138 |
static inline void *realloc_array(void *ptr, size_t nmemb, size_t size) |
| 139 |
{ |
| 140 |
size_t bytes; |
| 141 |
if (__builtin_mul_overflow(nmemb, size, &bytes)) { |
| 142 |
errno = ENOMEM; |
| 143 |
return NULL; |
| 144 |
} |
| 145 |
return realloc(ptr, bytes); |
| 146 |
} |
| 147 |
|
| 148 |
static inline void *memdup(const void *ptr, size_t size) |
| 149 |
{ |
| 150 |
void *copy = malloc(size); |
| 151 |
if (copy) |
| 152 |
memcpy(copy, ptr, size); |
| 153 |
return copy; |
| 154 |
} |
| 155 |
|
| 156 |
static inline bool alloc_or_reuse(void **buf, size_t *capacity, size_t size) |
| 157 |
{ |
| 158 |
if (size > *capacity) { |
| 159 |
free(*buf); |
| 160 |
*buf = malloc(size); |
| 161 |
if (!*buf) { |
| 162 |
*capacity = 0; |
| 163 |
return false; |
| 164 |
} |
| 165 |
*capacity = size; |
| 166 |
} |
| 167 |
return true; |
| 168 |
} |
| 169 |
|
| 170 |
/** Return the maximum value of an @p n-byte unsigned integer. */ |
| 171 |
static inline uint64_t uint_max(int n) |
| 172 |
{ |
| 173 |
assert(n >= 1 && n <= 8); |
| 174 |
return UINT64_MAX >> (64 - 8 * n); |
| 175 |
} |
| 176 |
|
| 177 |
/* |
| 178 |
* Calculate the number of decimal digits in 2^n. |
| 179 |
* |
| 180 |
* The number of decimal digits in a positive integer x is floor(log10(x)) + 1. |
| 181 |
* By the power rule of logarithms, log10(2^n) = n * log10(2). |
| 182 |
* Therefore, the number of decimal digits in 2^n is floor(n * log10(2))) + 1. |
| 183 |
* 643 / 2136 is an approximation of log10(2) which is accurate enough that |
| 184 |
* floor(n * 643 / 2136) = floor(n * log10(2))) for 1 <= n <= 15436. |
| 185 |
*/ |
| 186 |
#define max_decimal_length_impl(n) ((n) * 643 / 2136 + 1) |
| 187 |
|
| 188 |
/** |
| 189 |
* Get the maximum number of characters required to format an integer type in |
| 190 |
* base 10. This is an integer constant expression. |
| 191 |
*/ |
| 192 |
#define max_decimal_length(type) \ |
| 193 |
((type)-1 < 0 \ |
| 194 |
/* \ |
| 195 |
* Let f(x) = floor(log10(x)) + 1, which is the number of decimal \ |
| 196 |
* digits in a positive integer x. \ |
| 197 |
* \ |
| 198 |
* For an n-bit two's-complement integer, the worst case is the minimum \ |
| 199 |
* value, -2^(n - 1), which is f(2^(n - 1)) decimal digits plus the \ |
| 200 |
* minus sign. \ |
| 201 |
*/ \ |
| 202 |
? max_decimal_length_impl(sizeof(type) * CHAR_BIT - 1) + 1 \ |
| 203 |
/* \ |
| 204 |
* For an n-bit unsigned integer, the worst case is the maximum value, \ |
| 205 |
* 2^n - 1. Note that for any positive integer x, 2^x is not a power of \ |
| 206 |
* 10, so floor(log10(2^x - 1)) = floor(log10(2^x)). Therefore, \ |
| 207 |
* f(2^x - 1) \ |
| 208 |
* = floor(log10(2^x - 1)) + 1 \ |
| 209 |
* = floor(log10(2^x)) + 1 \ |
| 210 |
* = f(2^x). \ |
| 211 |
*/ \ |
| 212 |
: max_decimal_length_impl(sizeof(type) * CHAR_BIT)) |
| 213 |
|
| 214 |
/** |
| 215 |
* Safely add to a pointer which may be `NULL`. |
| 216 |
* |
| 217 |
* `NULL + 0` is undefined behavior, but it often arises naturally, like when |
| 218 |
* computing the end of a dynamic array: `arr + length`. This works around the |
| 219 |
* undefined behavior: `add_to_possibly_null_pointer(NULL, 0)` is defined as |
| 220 |
* `NULL`. |
| 221 |
* |
| 222 |
* A more natural definition would be `i == 0 ? ptr : ptr + i`, but some |
| 223 |
* versions of GCC and Clang generate an unnecessary branch or conditional move |
| 224 |
* (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97225). Note that in standard |
| 225 |
* C, it is undefined behavior to cast to `uintptr_t`, do arithmetic, and cast |
| 226 |
* back, but GCC allows this as long as the result is within the same object: |
| 227 |
* https://gcc.gnu.org/onlinedocs/gcc/Arrays-and-pointers-implementation.html. |
| 228 |
*/ |
| 229 |
#define add_to_possibly_null_pointer(ptr, i) \ |
| 230 |
((typeof(ptr))((uintptr_t)(ptr) + (i) * sizeof(*(ptr)))) |
| 231 |
|
| 232 |
/** |
| 233 |
* Similar to qsort_r (passes @a arg to @a compar) but **not** reentrant |
| 234 |
* |
| 235 |
* The qsort_r() function's main feature is that it is reentrant, but also adds |
| 236 |
* the convenience of including an argument to the callback function. |
| 237 |
* Unfortunately it is a glibc extension. This provides a similar API but it is |
| 238 |
* only thread-safe, not reentrant. See qsort_r(3) for details. |
| 239 |
*/ |
| 240 |
void qsort_arg(void *base, size_t nmemb, size_t size, |
| 241 |
int (*compar)(const void *, const void *, void*), void *arg); |
| 242 |
|
| 243 |
struct uint64_range { |
| 244 |
uint64_t start, end; |
| 245 |
}; |
| 246 |
|
| 247 |
#endif /* DRGN_UTIL_H */ |