1/* Allocation from a fixed-size buffer.
2 Copyright (C) 2017-2023 Free Software Foundation, Inc.
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
17 <https://www.gnu.org/licenses/>. */
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. */
98struct 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
108enum
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. */
116void __libc_alloc_buffer_create_failure (void *start, size_t size);
117#ifndef _ISOMAC
118libc_hidden_proto (__libc_alloc_buffer_create_failure)
119#endif
120
121/* Create a new allocation buffer. The byte range from START to START
122 + SIZE - 1 must be valid, and the allocation buffer allocates
123 objects from that range. If START is NULL (so that SIZE must be
124 0), the buffer is marked as failed immediately. */
125static inline struct alloc_buffer
126alloc_buffer_create (void *start, size_t size)
127{
128 uintptr_t current = (uintptr_t) start;
129 uintptr_t end = (uintptr_t) start + size;
130 if (end < current)
131 __libc_alloc_buffer_create_failure (start, size);
132 return (struct alloc_buffer) { current, end };
133}
134
135/* Internal function. See alloc_buffer_allocate below. */
136struct alloc_buffer __libc_alloc_buffer_allocate (size_t size, void **pptr)
137 __attribute__ ((nonnull (2)));
138#ifndef _ISOMAC
139libc_hidden_proto (__libc_alloc_buffer_allocate)
140#endif
141
142/* Allocate a buffer of SIZE bytes using malloc. The returned buffer
143 is in a failed state if malloc fails. *PPTR points to the start of
144 the buffer and can be used to free it later, after the returned
145 buffer has been freed. */
146static __always_inline __attribute__ ((nonnull (2)))
147struct alloc_buffer alloc_buffer_allocate (size_t size, void **pptr)
148{
149 return __libc_alloc_buffer_allocate (size, pptr);
150}
151
152/* Mark the buffer as failed. */
153static inline void __attribute__ ((nonnull (1)))
154alloc_buffer_mark_failed (struct alloc_buffer *buf)
155{
156 buf->__alloc_buffer_current = __ALLOC_BUFFER_INVALID_POINTER;
157 buf->__alloc_buffer_end = __ALLOC_BUFFER_INVALID_POINTER;
158}
159
160/* Return the remaining number of bytes in the buffer. */
161static __always_inline __attribute__ ((nonnull (1))) size_t
162alloc_buffer_size (const struct alloc_buffer *buf)
163{
164 return buf->__alloc_buffer_end - buf->__alloc_buffer_current;
165}
166
167/* Return true if the buffer has been marked as failed. */
168static inline bool __attribute__ ((nonnull (1)))
169alloc_buffer_has_failed (const struct alloc_buffer *buf)
170{
171 return buf->__alloc_buffer_current == __ALLOC_BUFFER_INVALID_POINTER;
172}
173
174/* Add a single byte to the buffer (consuming the space for this
175 byte). Mark the buffer as failed if there is not enough room. */
176static inline void __attribute__ ((nonnull (1)))
177alloc_buffer_add_byte (struct alloc_buffer *buf, unsigned char b)
178{
179 if (__glibc_likely (buf->__alloc_buffer_current < buf->__alloc_buffer_end))
180 {
181 *(unsigned char *) buf->__alloc_buffer_current = b;
182 ++buf->__alloc_buffer_current;
183 }
184 else
185 alloc_buffer_mark_failed (buf);
186}
187
188/* Obtain a pointer to LENGTH bytes in BUF, and consume these bytes.
189 NULL is returned if there is not enough room, and the buffer is
190 marked as failed, or if the buffer has already failed.
191 (Zero-length allocations from an empty buffer which has not yet
192 failed succeed.) The buffer contents is not modified. */
193static inline __attribute__ ((nonnull (1))) void *
194alloc_buffer_alloc_bytes (struct alloc_buffer *buf, size_t length)
195{
196 if (length <= alloc_buffer_size (buf))
197 {
198 void *result = (void *) buf->__alloc_buffer_current;
199 buf->__alloc_buffer_current += length;
200 return result;
201 }
202 else
203 {
204 alloc_buffer_mark_failed (buf);
205 return NULL;
206 }
207}
208
209/* Internal function. Statically assert that the type size is
210 constant and valid. */
211static __always_inline size_t
212__alloc_buffer_assert_size (size_t size)
213{
214 if (!__builtin_constant_p (size))
215 {
216 __errordecl (error, "type size is not constant");
217 error ();
218 }
219 else if (size == 0)
220 {
221 __errordecl (error, "type size is zero");
222 error ();
223 }
224 return size;
225}
226
227/* Internal function. Statically assert that the type alignment is
228 constant and valid. */
229static __always_inline size_t
230__alloc_buffer_assert_align (size_t align)
231{
232 if (!__builtin_constant_p (align))
233 {
234 __errordecl (error, "type alignment is not constant");
235 error ();
236 }
237 else if (align == 0)
238 {
239 __errordecl (error, "type alignment is zero");
240 error ();
241 }
242 else if (!powerof2 (align))
243 {
244 __errordecl (error, "type alignment is not a power of two");
245 error ();
246 }
247 return align;
248}
249
250/* Internal function. Obtain a pointer to an object. */
251static inline __attribute__ ((nonnull (1))) void *
252__alloc_buffer_alloc (struct alloc_buffer *buf, size_t size, size_t align)
253{
254 if (size == 1 && align == 1)
255 return alloc_buffer_alloc_bytes (buf, size);
256
257 uintptr_t current = buf->__alloc_buffer_current;
258 uintptr_t aligned = roundup (current, align);
259 uintptr_t new_current = aligned + size;
260 if (aligned >= current /* No overflow in align step. */
261 && new_current >= size /* No overflow in size computation. */
262 && new_current <= buf->__alloc_buffer_end) /* Room in buffer. */
263 {
264 buf->__alloc_buffer_current = new_current;
265 return (void *) aligned;
266 }
267 else
268 {
269 alloc_buffer_mark_failed (buf);
270 return NULL;
271 }
272}
273
274/* Obtain a TYPE * pointer to an object in BUF of TYPE. Consume these
275 bytes from the buffer. Return NULL and mark the buffer as failed
276 if there is not enough room in the buffer, or if the buffer has
277 failed before. */
278#define alloc_buffer_alloc(buf, type) \
279 ((type *) __alloc_buffer_alloc \
280 (buf, __alloc_buffer_assert_size (sizeof (type)), \
281 __alloc_buffer_assert_align (__alignof__ (type))))
282
283/* Internal function. Obtain a pointer to an object which is
284 subsequently added. */
285static inline const __attribute__ ((nonnull (1))) void *
286__alloc_buffer_next (struct alloc_buffer *buf, size_t align)
287{
288 if (align == 1)
289 return (const void *) buf->__alloc_buffer_current;
290
291 uintptr_t current = buf->__alloc_buffer_current;
292 uintptr_t aligned = roundup (current, align);
293 if (aligned >= current /* No overflow in align step. */
294 && aligned <= buf->__alloc_buffer_end) /* Room in buffer. */
295 {
296 buf->__alloc_buffer_current = aligned;
297 return (const void *) aligned;
298 }
299 else
300 {
301 alloc_buffer_mark_failed (buf);
302 return NULL;
303 }
304}
305
306/* Like alloc_buffer_alloc, but do not advance the pointer beyond the
307 object (so a subsequent call to alloc_buffer_next or
308 alloc_buffer_alloc returns the same pointer). Note that the buffer
309 is still aligned according to the requirements of TYPE, potentially
310 consuming buffer space. The effect of this function is similar to
311 allocating a zero-length array from the buffer.
312
313 It is possible to use the return pointer to write to the buffer and
314 consume the written bytes using alloc_buffer_alloc_bytes (which
315 does not change the buffer contents), but the calling code needs to
316 perform manual length checks using alloc_buffer_size. For example,
317 to read as many int32_t values that are available in the input file
318 and can fit into the remaining buffer space, you can use this:
319
320 int32_t array = alloc_buffer_next (buf, int32_t);
321 size_t ret = fread (array, sizeof (int32_t),
322 alloc_buffer_size (buf) / sizeof (int32_t), fp);
323 if (ferror (fp))
324 handle_error ();
325 alloc_buffer_alloc_array (buf, int32_t, ret);
326
327 The alloc_buffer_alloc_array call makes the actually-used part of
328 the buffer permanent. The remaining part of the buffer (not filled
329 with data from the file) can be used for something else.
330
331 This manual length checking can easily introduce errors, so this
332 coding style is not recommended. */
333#define alloc_buffer_next(buf, type) \
334 ((type *) __alloc_buffer_next \
335 (buf, __alloc_buffer_assert_align (__alignof__ (type))))
336
337/* Internal function. Allocate an array. */
338void * __libc_alloc_buffer_alloc_array (struct alloc_buffer *buf,
339 size_t size, size_t align,
340 size_t count)
341 __attribute__ ((nonnull (1)));
342#ifndef _ISOMAC
343libc_hidden_proto (__libc_alloc_buffer_alloc_array)
344#endif
345
346/* Obtain a TYPE * pointer to an array of COUNT objects in BUF of
347 TYPE. Consume these bytes from the buffer. Return NULL and mark
348 the buffer as failed if there is not enough room in the buffer,
349 or if the buffer has failed before. (Zero-length allocations from
350 an empty buffer which has not yet failed succeed.) */
351#define alloc_buffer_alloc_array(buf, type, count) \
352 ((type *) __libc_alloc_buffer_alloc_array \
353 (buf, __alloc_buffer_assert_size (sizeof (type)), \
354 __alloc_buffer_assert_align (__alignof__ (type)), \
355 count))
356
357/* Internal function. See alloc_buffer_copy_bytes below. */
358struct alloc_buffer __libc_alloc_buffer_copy_bytes (struct alloc_buffer,
359 const void *, size_t)
360 __attribute__ ((nonnull (2)));
361#ifndef _ISOMAC
362libc_hidden_proto (__libc_alloc_buffer_copy_bytes)
363#endif
364
365/* Copy SIZE bytes starting at SRC into the buffer. If there is not
366 enough room in the buffer, the buffer is marked as failed. No
367 alignment of the buffer is performed. */
368static inline __attribute__ ((nonnull (1, 2))) void
369alloc_buffer_copy_bytes (struct alloc_buffer *buf, const void *src, size_t size)
370{
371 *buf = __libc_alloc_buffer_copy_bytes (*buf, src, size);
372}
373
374/* Internal function. See alloc_buffer_copy_string below. */
375struct alloc_buffer __libc_alloc_buffer_copy_string (struct alloc_buffer,
376 const char *)
377 __attribute__ ((nonnull (2)));
378#ifndef _ISOMAC
379libc_hidden_proto (__libc_alloc_buffer_copy_string)
380#endif
381
382/* Copy the string at SRC into the buffer, including its null
383 terminator. If there is not enough room in the buffer, the buffer
384 is marked as failed. Return a pointer to the string. */
385static inline __attribute__ ((nonnull (1, 2))) char *
386alloc_buffer_copy_string (struct alloc_buffer *buf, const char *src)
387{
388 char *result = (char *) buf->__alloc_buffer_current;
389 *buf = __libc_alloc_buffer_copy_string (*buf, src);
390 if (alloc_buffer_has_failed (buf))
391 result = NULL;
392 return result;
393}
394
395#endif /* _ALLOC_BUFFER_H */
396