]>
Commit | Line | Data |
---|---|---|
4dd8e7c0 | 1 | /* Allocation from a fixed-size buffer. |
d614a753 | 2 | Copyright (C) 2017-2020 Free Software Foundation, Inc. |
4dd8e7c0 FW |
3 | This file is part of the GNU C Library. |
4 | ||
5 | The GNU C Library is free software; you can redistribute it and/or | |
6 | modify it under the terms of the GNU Lesser General Public | |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
9 | ||
10 | The GNU C Library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | Lesser General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU Lesser General Public | |
16 | License along with the GNU C Library; if not, see | |
5a82c748 | 17 | <https://www.gnu.org/licenses/>. */ |
4dd8e7c0 FW |
18 | |
19 | /* Allocation buffers are used to carve out sub-allocations from a | |
20 | larger allocation. Their primary application is in writing NSS | |
21 | modules, which receive a caller-allocated buffer in which they are | |
22 | expected to store variable-length results: | |
23 | ||
24 | void *buffer = ...; | |
25 | size_t buffer_size = ...; | |
26 | ||
27 | struct alloc_buffer buf = alloc_buffer_create (buffer, buffer_size); | |
28 | result->gr_name = alloc_buffer_copy_string (&buf, name); | |
29 | ||
30 | // Allocate a list of group_count groups and copy strings into it. | |
31 | char **group_list = alloc_buffer_alloc_array | |
32 | (&buf, char *, group_count + 1); | |
33 | if (group_list == NULL) | |
34 | return ...; // Request a larger buffer. | |
35 | for (int i = 0; i < group_count; ++i) | |
36 | group_list[i] = alloc_buffer_copy_string (&buf, group_list_src[i]); | |
37 | group_list[group_count] = NULL; | |
38 | ... | |
39 | ||
40 | if (alloc_buffer_has_failed (&buf)) | |
41 | return ...; // Request a larger buffer. | |
42 | result->gr_mem = group_list; | |
43 | ... | |
44 | ||
45 | Note that it is not necessary to check the results of individual | |
46 | allocation operations if the returned pointer is not dereferenced. | |
47 | Allocation failure is sticky, so one check using | |
48 | alloc_buffer_has_failed at the end covers all previous failures. | |
49 | ||
50 | A different use case involves combining multiple heap allocations | |
51 | into a single, large one. In the following example, an array of | |
52 | doubles and an array of ints is allocated: | |
53 | ||
54 | size_t double_array_size = ...; | |
55 | size_t int_array_size = ...; | |
56 | ||
57 | void *heap_ptr; | |
58 | struct alloc_buffer buf = alloc_buffer_allocate | |
59 | (double_array_size * sizeof (double) + int_array_size * sizeof (int), | |
60 | &heap_ptr); | |
61 | _Static_assert (__alignof__ (double) >= __alignof__ (int), | |
62 | "no padding after double array"); | |
63 | double *double_array = alloc_buffer_alloc_array | |
64 | (&buf, double, double_array_size); | |
65 | int *int_array = alloc_buffer_alloc_array (&buf, int, int_array_size); | |
66 | if (alloc_buffer_has_failed (&buf)) | |
67 | return ...; // Report error. | |
68 | ... | |
69 | free (heap_ptr); | |
70 | ||
71 | The advantage over manual coding is that the computation of the | |
72 | allocation size does not need an overflow check. In case of an | |
73 | overflow, one of the subsequent allocations from the buffer will | |
74 | fail. The initial size computation is checked for consistency at | |
75 | run time, too. */ | |
76 | ||
77 | #ifndef _ALLOC_BUFFER_H | |
78 | #define _ALLOC_BUFFER_H | |
79 | ||
80 | #include <inttypes.h> | |
81 | #include <stdbool.h> | |
82 | #include <stddef.h> | |
83 | #include <stdlib.h> | |
84 | #include <sys/param.h> | |
85 | ||
86 | /* struct alloc_buffer objects refer to a region of bytes in memory of a | |
87 | fixed size. The functions below can be used to allocate single | |
88 | objects and arrays from this memory region, or write to its end. | |
89 | On allocation failure (or if an attempt to write beyond the end of | |
90 | the buffer with one of the copy functions), the buffer enters a | |
91 | failed state. | |
92 | ||
93 | struct alloc_buffer objects can be copied. The backing buffer will | |
94 | be shared, but the current write position will be independent. | |
95 | ||
96 | Conceptually, the memory region consists of a current write pointer | |
97 | and a limit, beyond which the write pointer cannot move. */ | |
98 | struct alloc_buffer | |
99 | { | |
100 | /* uintptr_t is used here to simplify the alignment code, and to | |
101 | avoid issues undefined subtractions if the buffer covers more | |
102 | than half of the address space (which would result in differences | |
103 | which could not be represented as a ptrdiff_t value). */ | |
104 | uintptr_t __alloc_buffer_current; | |
105 | uintptr_t __alloc_buffer_end; | |
106 | }; | |
107 | ||
108 | enum | |
109 | { | |
110 | /* The value for the __alloc_buffer_current member which marks the | |
111 | buffer as invalid (together with a zero-length buffer). */ | |
112 | __ALLOC_BUFFER_INVALID_POINTER = 0, | |
113 | }; | |
114 | ||
115 | /* Internal function. Terminate the process using __libc_fatal. */ | |
116 | void __libc_alloc_buffer_create_failure (void *start, size_t size); | |
117 | ||
118 | /* Create a new allocation buffer. The byte range from START to START | |
119 | + SIZE - 1 must be valid, and the allocation buffer allocates | |
120 | objects from that range. If START is NULL (so that SIZE must be | |
121 | 0), the buffer is marked as failed immediately. */ | |
122 | static inline struct alloc_buffer | |
123 | alloc_buffer_create (void *start, size_t size) | |
124 | { | |
125 | uintptr_t current = (uintptr_t) start; | |
126 | uintptr_t end = (uintptr_t) start + size; | |
127 | if (end < current) | |
128 | __libc_alloc_buffer_create_failure (start, size); | |
129 | return (struct alloc_buffer) { current, end }; | |
130 | } | |
131 | ||
132 | /* Internal function. See alloc_buffer_allocate below. */ | |
133 | struct alloc_buffer __libc_alloc_buffer_allocate (size_t size, void **pptr) | |
134 | __attribute__ ((nonnull (2))); | |
135 | ||
136 | /* Allocate a buffer of SIZE bytes using malloc. The returned buffer | |
137 | is in a failed state if malloc fails. *PPTR points to the start of | |
138 | the buffer and can be used to free it later, after the returned | |
139 | buffer has been freed. */ | |
140 | static __always_inline __attribute__ ((nonnull (2))) | |
141 | struct alloc_buffer alloc_buffer_allocate (size_t size, void **pptr) | |
142 | { | |
143 | return __libc_alloc_buffer_allocate (size, pptr); | |
144 | } | |
145 | ||
146 | /* Mark the buffer as failed. */ | |
147 | static inline void __attribute__ ((nonnull (1))) | |
148 | alloc_buffer_mark_failed (struct alloc_buffer *buf) | |
149 | { | |
150 | buf->__alloc_buffer_current = __ALLOC_BUFFER_INVALID_POINTER; | |
151 | buf->__alloc_buffer_end = __ALLOC_BUFFER_INVALID_POINTER; | |
152 | } | |
153 | ||
154 | /* Return the remaining number of bytes in the buffer. */ | |
155 | static __always_inline __attribute__ ((nonnull (1))) size_t | |
156 | alloc_buffer_size (const struct alloc_buffer *buf) | |
157 | { | |
158 | return buf->__alloc_buffer_end - buf->__alloc_buffer_current; | |
159 | } | |
160 | ||
161 | /* Return true if the buffer has been marked as failed. */ | |
162 | static inline bool __attribute__ ((nonnull (1))) | |
163 | alloc_buffer_has_failed (const struct alloc_buffer *buf) | |
164 | { | |
165 | return buf->__alloc_buffer_current == __ALLOC_BUFFER_INVALID_POINTER; | |
166 | } | |
167 | ||
168 | /* Add a single byte to the buffer (consuming the space for this | |
169 | byte). Mark the buffer as failed if there is not enough room. */ | |
170 | static inline void __attribute__ ((nonnull (1))) | |
171 | alloc_buffer_add_byte (struct alloc_buffer *buf, unsigned char b) | |
172 | { | |
173 | if (__glibc_likely (buf->__alloc_buffer_current < buf->__alloc_buffer_end)) | |
174 | { | |
175 | *(unsigned char *) buf->__alloc_buffer_current = b; | |
176 | ++buf->__alloc_buffer_current; | |
177 | } | |
178 | else | |
179 | alloc_buffer_mark_failed (buf); | |
180 | } | |
181 | ||
182 | /* Obtain a pointer to LENGTH bytes in BUF, and consume these bytes. | |
183 | NULL is returned if there is not enough room, and the buffer is | |
184 | marked as failed, or if the buffer has already failed. | |
185 | (Zero-length allocations from an empty buffer which has not yet | |
32d85c11 | 186 | failed succeed.) The buffer contents is not modified. */ |
4dd8e7c0 FW |
187 | static inline __attribute__ ((nonnull (1))) void * |
188 | alloc_buffer_alloc_bytes (struct alloc_buffer *buf, size_t length) | |
189 | { | |
190 | if (length <= alloc_buffer_size (buf)) | |
191 | { | |
192 | void *result = (void *) buf->__alloc_buffer_current; | |
193 | buf->__alloc_buffer_current += length; | |
194 | return result; | |
195 | } | |
196 | else | |
197 | { | |
198 | alloc_buffer_mark_failed (buf); | |
199 | return NULL; | |
200 | } | |
201 | } | |
202 | ||
203 | /* Internal function. Statically assert that the type size is | |
204 | constant and valid. */ | |
205 | static __always_inline size_t | |
206 | __alloc_buffer_assert_size (size_t size) | |
207 | { | |
208 | if (!__builtin_constant_p (size)) | |
209 | { | |
210 | __errordecl (error, "type size is not constant"); | |
211 | error (); | |
212 | } | |
213 | else if (size == 0) | |
214 | { | |
215 | __errordecl (error, "type size is zero"); | |
216 | error (); | |
217 | } | |
218 | return size; | |
219 | } | |
220 | ||
221 | /* Internal function. Statically assert that the type alignment is | |
222 | constant and valid. */ | |
223 | static __always_inline size_t | |
224 | __alloc_buffer_assert_align (size_t align) | |
225 | { | |
226 | if (!__builtin_constant_p (align)) | |
227 | { | |
228 | __errordecl (error, "type alignment is not constant"); | |
229 | error (); | |
230 | } | |
231 | else if (align == 0) | |
232 | { | |
233 | __errordecl (error, "type alignment is zero"); | |
234 | error (); | |
235 | } | |
236 | else if (!powerof2 (align)) | |
237 | { | |
238 | __errordecl (error, "type alignment is not a power of two"); | |
239 | error (); | |
240 | } | |
241 | return align; | |
242 | } | |
243 | ||
244 | /* Internal function. Obtain a pointer to an object. */ | |
245 | static inline __attribute__ ((nonnull (1))) void * | |
246 | __alloc_buffer_alloc (struct alloc_buffer *buf, size_t size, size_t align) | |
247 | { | |
248 | if (size == 1 && align == 1) | |
249 | return alloc_buffer_alloc_bytes (buf, size); | |
250 | ||
251 | size_t current = buf->__alloc_buffer_current; | |
252 | size_t aligned = roundup (current, align); | |
253 | size_t new_current = aligned + size; | |
254 | if (aligned >= current /* No overflow in align step. */ | |
255 | && new_current >= size /* No overflow in size computation. */ | |
256 | && new_current <= buf->__alloc_buffer_end) /* Room in buffer. */ | |
257 | { | |
258 | buf->__alloc_buffer_current = new_current; | |
259 | return (void *) aligned; | |
260 | } | |
261 | else | |
262 | { | |
263 | alloc_buffer_mark_failed (buf); | |
264 | return NULL; | |
265 | } | |
266 | } | |
267 | ||
268 | /* Obtain a TYPE * pointer to an object in BUF of TYPE. Consume these | |
269 | bytes from the buffer. Return NULL and mark the buffer as failed | |
a122dbfb | 270 | if there is not enough room in the buffer, or if the buffer has |
4dd8e7c0 FW |
271 | failed before. */ |
272 | #define alloc_buffer_alloc(buf, type) \ | |
273 | ((type *) __alloc_buffer_alloc \ | |
274 | (buf, __alloc_buffer_assert_size (sizeof (type)), \ | |
275 | __alloc_buffer_assert_align (__alignof__ (type)))) | |
276 | ||
277 | /* Internal function. Obtain a pointer to an object which is | |
278 | subsequently added. */ | |
279 | static inline const __attribute__ ((nonnull (1))) void * | |
280 | __alloc_buffer_next (struct alloc_buffer *buf, size_t align) | |
281 | { | |
282 | if (align == 1) | |
283 | return (const void *) buf->__alloc_buffer_current; | |
284 | ||
285 | size_t current = buf->__alloc_buffer_current; | |
286 | size_t aligned = roundup (current, align); | |
287 | if (aligned >= current /* No overflow in align step. */ | |
288 | && aligned <= buf->__alloc_buffer_end) /* Room in buffer. */ | |
289 | { | |
290 | buf->__alloc_buffer_current = aligned; | |
291 | return (const void *) aligned; | |
292 | } | |
293 | else | |
294 | { | |
295 | alloc_buffer_mark_failed (buf); | |
296 | return NULL; | |
297 | } | |
298 | } | |
299 | ||
300 | /* Like alloc_buffer_alloc, but do not advance the pointer beyond the | |
301 | object (so a subseqent call to alloc_buffer_next or | |
302 | alloc_buffer_alloc returns the same pointer). Note that the buffer | |
32d85c11 FW |
303 | is still aligned according to the requirements of TYPE, potentially |
304 | consuming buffer space. The effect of this function is similar to | |
305 | allocating a zero-length array from the buffer. | |
306 | ||
307 | It is possible to use the return pointer to write to the buffer and | |
308 | consume the written bytes using alloc_buffer_alloc_bytes (which | |
309 | does not change the buffer contents), but the calling code needs to | |
310 | perform manual length checks using alloc_buffer_size. For example, | |
311 | to read as many int32_t values that are available in the input file | |
312 | and can fit into the remaining buffer space, you can use this: | |
313 | ||
314 | int32_t array = alloc_buffer_next (buf, int32_t); | |
315 | size_t ret = fread (array, sizeof (int32_t), | |
316 | alloc_buffer_size (buf) / sizeof (int32_t), fp); | |
317 | if (ferror (fp)) | |
318 | handle_error (); | |
319 | alloc_buffer_alloc_array (buf, int32_t, ret); | |
320 | ||
321 | The alloc_buffer_alloc_array call makes the actually-used part of | |
322 | the buffer permanent. The remaining part of the buffer (not filled | |
323 | with data from the file) can be used for something else. | |
324 | ||
325 | This manual length checking can easily introduce errors, so this | |
326 | coding style is not recommended. */ | |
4dd8e7c0 | 327 | #define alloc_buffer_next(buf, type) \ |
32d85c11 | 328 | ((type *) __alloc_buffer_next \ |
4dd8e7c0 FW |
329 | (buf, __alloc_buffer_assert_align (__alignof__ (type)))) |
330 | ||
331 | /* Internal function. Allocate an array. */ | |
332 | void * __libc_alloc_buffer_alloc_array (struct alloc_buffer *buf, | |
333 | size_t size, size_t align, | |
334 | size_t count) | |
335 | __attribute__ ((nonnull (1))); | |
336 | ||
337 | /* Obtain a TYPE * pointer to an array of COUNT objects in BUF of | |
338 | TYPE. Consume these bytes from the buffer. Return NULL and mark | |
a122dbfb | 339 | the buffer as failed if there is not enough room in the buffer, |
4dd8e7c0 FW |
340 | or if the buffer has failed before. (Zero-length allocations from |
341 | an empty buffer which has not yet failed succeed.) */ | |
342 | #define alloc_buffer_alloc_array(buf, type, count) \ | |
343 | ((type *) __libc_alloc_buffer_alloc_array \ | |
344 | (buf, __alloc_buffer_assert_size (sizeof (type)), \ | |
345 | __alloc_buffer_assert_align (__alignof__ (type)), \ | |
346 | count)) | |
347 | ||
348 | /* Internal function. See alloc_buffer_copy_bytes below. */ | |
349 | struct alloc_buffer __libc_alloc_buffer_copy_bytes (struct alloc_buffer, | |
350 | const void *, size_t) | |
351 | __attribute__ ((nonnull (2))); | |
352 | ||
353 | /* Copy SIZE bytes starting at SRC into the buffer. If there is not | |
354 | enough room in the buffer, the buffer is marked as failed. No | |
355 | alignment of the buffer is performed. */ | |
356 | static inline __attribute__ ((nonnull (1, 2))) void | |
357 | alloc_buffer_copy_bytes (struct alloc_buffer *buf, const void *src, size_t size) | |
358 | { | |
359 | *buf = __libc_alloc_buffer_copy_bytes (*buf, src, size); | |
360 | } | |
361 | ||
362 | /* Internal function. See alloc_buffer_copy_string below. */ | |
363 | struct alloc_buffer __libc_alloc_buffer_copy_string (struct alloc_buffer, | |
364 | const char *) | |
365 | __attribute__ ((nonnull (2))); | |
366 | ||
367 | /* Copy the string at SRC into the buffer, including its null | |
368 | terminator. If there is not enough room in the buffer, the buffer | |
369 | is marked as failed. Return a pointer to the string. */ | |
370 | static inline __attribute__ ((nonnull (1, 2))) char * | |
371 | alloc_buffer_copy_string (struct alloc_buffer *buf, const char *src) | |
372 | { | |
373 | char *result = (char *) buf->__alloc_buffer_current; | |
374 | *buf = __libc_alloc_buffer_copy_string (*buf, src); | |
375 | if (alloc_buffer_has_failed (buf)) | |
376 | result = NULL; | |
377 | return result; | |
378 | } | |
379 | ||
380 | #ifndef _ISOMAC | |
381 | libc_hidden_proto (__libc_alloc_buffer_alloc_array) | |
382 | libc_hidden_proto (__libc_alloc_buffer_allocate) | |
383 | libc_hidden_proto (__libc_alloc_buffer_copy_bytes) | |
384 | libc_hidden_proto (__libc_alloc_buffer_copy_string) | |
385 | libc_hidden_proto (__libc_alloc_buffer_create_failure) | |
386 | #endif | |
387 | ||
388 | #endif /* _ALLOC_BUFFER_H */ |