Debian Codegraph @

libdrgn/util.h

raw
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 */