Debian Codegraph @

lib/obstack.c

raw
1 /* obstack.c - subroutines used implicitly by object stack macros
2 Copyright (C) 1988-2026 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
20 #ifdef _LIBC
21 # include <obstack.h>
22 # include <shlib-compat.h>
23 #else
24 # include <libc-config.h>
25 # include "obstack.h"
26 #endif
27
28 /* NOTE BEFORE MODIFYING THIS FILE IN GNU LIBC: _OBSTACK_INTERFACE_VERSION in
29 gnu-versions.h must be incremented whenever callers compiled using an old
30 obstack.h can no longer properly call the functions in this file. */
31
32 /* If GCC, or if an oddball (testing?) host that #defines __alignof__,
33 use the already-supplied __alignof__. Otherwise, this must be Gnulib
34 (as glibc assumes GCC); defer to Gnulib's alignof. */
35 #if !defined __GNUC__ && !defined __alignof__
36 # define __alignof__(type) alignof (type)
37 #endif
38
39 #include <stdckdint.h>
40 #include <stddef.h>
41 #include <stdint.h>
42 #include <stdlib.h>
43
44 #ifndef _OBSTACK_NO_ERROR_HANDLER
45
46 /* The functions allocating more room by calling 'obstack_chunk_alloc'
47 jump to the handler pointed to by 'obstack_alloc_failed_handler'.
48 This can be set to a user defined function which should either
49 abort gracefully or use longjump - but shouldn't return. This
50 variable by default points to the internal function
51 'print_and_abort'. */
52 static __attribute_noreturn__ void print_and_abort (void);
53 __attribute_noreturn__ void (*obstack_alloc_failed_handler) (void)
54 = print_and_abort;
55
56 /* Exit value used when 'print_and_abort' is used. */
57 # ifdef _LIBC
58 int obstack_exit_failure = EXIT_FAILURE;
59 # else
60 # include "exitfail.h"
61 # define obstack_exit_failure exit_failure
62 # endif
63
64 #endif /* !_OBSTACK_NO_ERROR_HANDLER */
65
66 #if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
67 /* A looong time ago (before 1994, anyway; we're not sure) this global variable
68 was used by non-GNU-C macros to avoid multiple evaluation. The GNU C
69 library still exports it because somebody might use it. */
70 struct obstack *_obstack_compat = NULL;
71 compat_symbol (libc, _obstack_compat, _obstack, GLIBC_2_0);
72 #endif
73
74 /* Set *R to the least multiple of MASK + 1 that is not less than SIZE.
75 MASK + 1 must be a power of 2. Return true (setting *R = 0)
76 if the result overflows, false otherwise. */
77 static bool
78 align_chunk_size_up (_OBSTACK_CHUNK_SIZE_T *r, size_t mask,
79 _OBSTACK_CHUNK_SIZE_T size)
80 {
81 return ckd_add (r, mask & -size, size);
82 }
83
84 /* Call functions with either the traditional malloc/free calling
85 interface, or the mmalloc/mfree interface (that adds an extra first
86 argument), based on the value of use_extra_arg. */
87
88 static void *
89 call_chunkfun (struct obstack *h, _OBSTACK_CHUNK_SIZE_T size)
90 {
91 if (h->use_extra_arg)
92 return h->chunkfun.extra (h->extra_arg, size);
93 else
94 return h->chunkfun.plain (size);
95 }
96
97 static void
98 call_freefun (struct obstack *h, void *old_chunk)
99 {
100 if (h->use_extra_arg)
101 h->freefun.extra (h->extra_arg, old_chunk);
102 else
103 h->freefun.plain (old_chunk);
104 }
105
106
107 /* Initialize an obstack H for use, with given CHUNK_SIZE (0 means default).
108 Objects start on multiples of ALIGNMENT (0 means use default).
109
110 Return nonzero if successful, calls obstack_alloc_failed_handler if
111 allocation fails. */
112
113 static int
114 _obstack_begin_worker (struct obstack *h,
115 _OBSTACK_INDEX_T chunk_size, _OBSTACK_INDEX_T alignment)
116 {
117 struct _obstack_chunk *chunk; /* points to new chunk */
118
119 if (alignment == 0)
120 alignment = __alignof__ (max_align_t);
121
122 /* The minimum size to request from the allocator, such that the
123 result is guaranteed to have enough room to start with the struct
124 _obstack_chunk sans contents, followed by minimal padding, up to
125 but possibly not including the start of an aligned object.
126 This value is zero if no size is large enough. */
127 _OBSTACK_CHUNK_SIZE_T aligned_prefix_size;
128 bool v = align_chunk_size_up (&aligned_prefix_size, alignment - 1,
129 offsetof (struct _obstack_chunk, contents));
130
131 _OBSTACK_CHUNK_SIZE_T size = chunk_size;
132 if (size < aligned_prefix_size)
133 {
134 size = aligned_prefix_size;
135
136 /* For speed in the typical case, allocate at least a "good" size. */
137 int good_size = 4000;
138 if (size < good_size)
139 size = good_size;
140 }
141
142 h->chunk_size = size;
143 h->alignment_mask = alignment - 1;
144
145 chunk = h->chunk = v ? NULL : call_chunkfun (h, size);
146 if (!chunk)
147 (*obstack_alloc_failed_handler) ();
148 h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,
149 alignment - 1);
150 h->chunk_limit = chunk->limit =
151 __PTR_ALIGN ((char *) chunk, (char *) chunk + size - (alignment - 1),
152 alignment - 1);
153 chunk->prev = NULL;
154 /* The initial chunk now contains no empty object. */
155 h->maybe_empty_object = 0;
156 h->alloc_failed = 0;
157 return 1;
158 }
159
160 int
161 _obstack_begin (struct obstack *h,
162 _OBSTACK_INDEX_T size, _OBSTACK_INDEX_T alignment,
163 void *(*chunkfun) (_OBSTACK_CHUNK_SIZE_T),
164 void (*freefun) (void *))
165 {
166 h->chunkfun.plain = chunkfun;
167 h->freefun.plain = freefun;
168 h->use_extra_arg = 0;
169 return _obstack_begin_worker (h, size, alignment);
170 }
171
172 int
173 _obstack_begin_1 (struct obstack *h,
174 _OBSTACK_INDEX_T size, _OBSTACK_INDEX_T alignment,
175 void *(*chunkfun) (void *, _OBSTACK_CHUNK_SIZE_T),
176 void (*freefun) (void *, void *),
177 void *arg)
178 {
179 h->chunkfun.extra = chunkfun;
180 h->freefun.extra = freefun;
181 h->extra_arg = arg;
182 h->use_extra_arg = 1;
183 return _obstack_begin_worker (h, size, alignment);
184 }
185
186 /* Allocate a new current chunk for the obstack *H
187 on the assumption that LENGTH bytes need to be added
188 to the current object, or a new object of length LENGTH allocated.
189 Fail if LENGTH <= 0, as this means obstack_grow0's length overflowed.
190 Copies any partial object from the end of the old chunk
191 to the beginning of the new one. */
192
193 void
194 _obstack_newchunk (struct obstack *h, _OBSTACK_INDEX_T length)
195 {
196 struct _obstack_chunk *old_chunk = h->chunk;
197 size_t obj_size = h->next_free - h->object_base;
198
199 /* Compute size for new chunk. */
200 _OBSTACK_CHUNK_SIZE_T s, new_size;
201 bool v = length < 0;
202 v |= ckd_add (&s, obj_size, length);
203 v |= align_chunk_size_up (&s, h->alignment_mask, s);
204 v |= ckd_add (&s, s,
205 (offsetof (struct _obstack_chunk, contents)
206 + h->alignment_mask));
207 if (ckd_add (&new_size, s, (obj_size >> 3) + 100))
208 new_size = s;
209 if (new_size < h->chunk_size)
210 new_size = h->chunk_size;
211
212 /* Allocate and initialize the new chunk. */
213 struct _obstack_chunk *new_chunk =
214 v ? NULL : call_chunkfun (h, new_size);
215 if (!new_chunk)
216 (*obstack_alloc_failed_handler)();
217 h->chunk = new_chunk;
218 new_chunk->prev = old_chunk;
219 new_chunk->limit = h->chunk_limit =
220 __PTR_ALIGN ((char *) new_chunk,
221 (char *) new_chunk + new_size - h->alignment_mask,
222 h->alignment_mask);
223
224 /* Compute an aligned object_base in the new chunk */
225 char *object_base =
226 __PTR_ALIGN ((char *) new_chunk, new_chunk->contents, h->alignment_mask);
227
228 /* Move the existing object to the new chunk. */
229 memcpy (object_base, h->object_base, obj_size);
230
231 /* If the object just copied was the only data in OLD_CHUNK,
232 free that chunk and remove it from the chain.
233 But not if that chunk might contain an empty object. */
234 if (!h->maybe_empty_object
235 && (h->object_base
236 == __PTR_ALIGN ((char *) old_chunk, old_chunk->contents,
237 h->alignment_mask)))
238 {
239 new_chunk->prev = old_chunk->prev;
240 call_freefun (h, old_chunk);
241 }
242
243 h->object_base = object_base;
244 h->next_free = h->object_base + obj_size;
245 /* The new chunk certainly contains no empty object yet. */
246 h->maybe_empty_object = 0;
247 }
248 libc_hidden_def (_obstack_newchunk)
249
250 /* Return nonzero if object OBJ has been allocated from obstack H.
251 This is here for debugging.
252 If you use it in a program, you are probably losing. */
253
254 /* Suppress -Wmissing-prototypes warning. We don't want to declare this in
255 obstack.h because it is just for debugging. */
256 int _obstack_allocated_p (struct obstack *h, void *obj) __attribute_pure__;
257
258 int
259 _obstack_allocated_p (struct obstack *h, void *obj)
260 {
261 struct _obstack_chunk *lp = /* below addr of any objects in this chunk */
262 h->chunk;
263 /* We use >= rather than > since the object cannot be exactly at
264 the beginning of the chunk but might be an empty object exactly
265 at the end of an adjacent chunk. */
266 while (lp != NULL && ((void *) lp >= obj || (void *) (lp)->limit < obj))
267 {
268 struct _obstack_chunk *plp = lp->prev; /* point to previous chunk */
269 lp = plp;
270 }
271 return lp != NULL;
272 }
273
274 /* Free objects in obstack H, including OBJ and everything allocate
275 more recently than OBJ. If OBJ is zero, free everything in H. */
276
277 void
278 __obstack_free (struct obstack *h, void *obj)
279 {
280 struct _obstack_chunk *lp = /* below addr of any objects in this chunk */
281 h->chunk;
282 /* We use >= because there cannot be an object at the beginning of a chunk.
283 But there can be an empty object at that address
284 at the end of another chunk. */
285 while (lp != NULL && ((void *) lp >= obj || (void *) (lp)->limit < obj))
286 {
287 struct _obstack_chunk *plp = lp->prev; /* point to previous chunk */
288 call_freefun (h, lp);
289 lp = plp;
290 /* If we switch chunks, we can't tell whether the new current
291 chunk contains an empty object, so assume that it may. */
292 h->maybe_empty_object = 1;
293 }
294 if (lp)
295 {
296 h->object_base = h->next_free = (char *) (obj);
297 h->chunk_limit = lp->limit;
298 h->chunk = lp;
299 }
300 else if (obj != NULL)
301 /* obj is not in any of the chunks! */
302 abort ();
303 }
304
305 /* Older versions of libc used a function _obstack_free intended to be
306 called by non-GCC compilers. */
307 #undef obstack_free
308 strong_alias (_obstack_free, obstack_free)
309
310 _OBSTACK_INDEX_T
311 _obstack_memory_used (struct obstack *h)
312 {
313 _OBSTACK_INDEX_T nbytes = 0;
314
315 for (struct _obstack_chunk *lp = h->chunk; lp != NULL; lp = lp->prev)
316 {
317 nbytes += lp->limit - (char *) lp;
318 }
319 return nbytes;
320 }
321
322 #ifndef _OBSTACK_NO_ERROR_HANDLER
323 /* Define the error handler. */
324 # include <stdio.h>
325
326 # ifdef _LIBC
327 # include <libintl.h>
328 # ifndef _
329 # define _(msgid) gettext (msgid)
330 # endif
331 # else
332 # include "gettext.h"
333 # ifndef _
334 # define _(msgid) dgettext (GNULIB_TEXT_DOMAIN, msgid)
335 # endif
336 # endif
337
338 # ifdef _LIBC
339 # include <libio/iolibio.h>
340 # endif
341
342 static __attribute_noreturn__ void
343 print_and_abort (void)
344 {
345 /* Don't change any of these strings. Yes, it would be possible to add
346 the newline to the string and use fputs or so. But this must not
347 happen because the "memory exhausted" message appears in other places
348 like this and the translation should be reused instead of creating
349 a very similar string which requires a separate translation. */
350 # ifdef _LIBC
351 (void) __fxprintf (NULL, "%s\n", _("memory exhausted"));
352 # else
353 fprintf (stderr, "%s\n", _("memory exhausted"));
354 # endif
355 exit (obstack_exit_failure);
356 }
357 #endif /* !_OBSTACK_NO_ERROR_HANDLER */