(Feature Test Macros): Add _POSIX_C_SOURCE definition.
[kopensolaris-gnu/glibc.git] / manual / memory.texi
1 @comment !!! describe mmap et al (here?)
2 @c !!! doc brk/sbrk
3
4 @node Memory Allocation, Character Handling, Error Reporting, Top
5 @chapter Memory Allocation
6 @cindex memory allocation
7 @cindex storage allocation
8
9 The GNU system provides several methods for allocating memory space
10 under explicit program control.  They vary in generality and in
11 efficiency.
12
13 @iftex
14 @itemize @bullet
15 @item
16 The @code{malloc} facility allows fully general dynamic allocation.
17 @xref{Unconstrained Allocation}.
18
19 @item
20 Obstacks are another facility, less general than @code{malloc} but more
21 efficient and convenient for stacklike allocation.  @xref{Obstacks}.
22
23 @item
24 The function @code{alloca} lets you allocate storage dynamically that
25 will be freed automatically.  @xref{Variable Size Automatic}.
26 @end itemize
27 @end iftex
28
29 @menu
30 * Memory Concepts::             An introduction to concepts and terminology.
31 * Dynamic Allocation and C::    How to get different kinds of allocation in C.
32 * Unconstrained Allocation::    The @code{malloc} facility allows fully general
33                                  dynamic allocation.
34 * Obstacks::                    Obstacks are less general than malloc
35                                  but more efficient and convenient.
36 * Variable Size Automatic::     Allocation of variable-sized blocks
37                                  of automatic storage that are freed when the
38                                  calling function returns.
39 * Relocating Allocator::        Waste less memory, if you can tolerate
40                                  automatic relocation of the blocks you get.
41 @end menu
42
43 @node Memory Concepts
44 @section Dynamic Memory Allocation Concepts
45 @cindex dynamic allocation
46 @cindex static allocation
47 @cindex automatic allocation
48
49 @dfn{Dynamic memory allocation} is a technique in which programs
50 determine as they are running where to store some information.  You need
51 dynamic allocation when the number of memory blocks you need, or how
52 long you continue to need them, depends on the data you are working on.
53
54 For example, you may need a block to store a line read from an input file;
55 since there is no limit to how long a line can be, you must allocate the
56 storage dynamically and make it dynamically larger as you read more of the
57 line.
58
59 Or, you may need a block for each record or each definition in the input
60 data; since you can't know in advance how many there will be, you must
61 allocate a new block for each record or definition as you read it.
62
63 When you use dynamic allocation, the allocation of a block of memory is an
64 action that the program requests explicitly.  You call a function or macro
65 when you want to allocate space, and specify the size with an argument.  If
66 you want to free the space, you do so by calling another function or macro.
67 You can do these things whenever you want, as often as you want.
68
69 @node Dynamic Allocation and C
70 @section Dynamic Allocation and C
71
72 The C language supports two kinds of memory allocation through the variables
73 in C programs:
74
75 @itemize @bullet
76 @item
77 @dfn{Static allocation} is what happens when you declare a static or
78 global variable.  Each static or global variable defines one block of
79 space, of a fixed size.  The space is allocated once, when your program
80 is started, and is never freed.
81
82 @item
83 @dfn{Automatic allocation} happens when you declare an automatic
84 variable, such as a function argument or a local variable.  The space
85 for an automatic variable is allocated when the compound statement
86 containing the declaration is entered, and is freed when that
87 compound statement is exited.
88
89 In GNU C, the length of the automatic storage can be an expression
90 that varies.  In other C implementations, it must be a constant.
91 @end itemize
92
93 Dynamic allocation is not supported by C variables; there is no storage
94 class ``dynamic'', and there can never be a C variable whose value is
95 stored in dynamically allocated space.  The only way to refer to
96 dynamically allocated space is through a pointer.  Because it is less
97 convenient, and because the actual process of dynamic allocation
98 requires more computation time, programmers generally use dynamic
99 allocation only when neither static nor automatic allocation will serve.
100
101 For example, if you want to allocate dynamically some space to hold a
102 @code{struct foobar}, you cannot declare a variable of type @code{struct
103 foobar} whose contents are the dynamically allocated space.  But you can
104 declare a variable of pointer type @code{struct foobar *} and assign it the
105 address of the space.  Then you can use the operators @samp{*} and
106 @samp{->} on this pointer variable to refer to the contents of the space:
107
108 @smallexample
109 @{
110   struct foobar *ptr
111      = (struct foobar *) malloc (sizeof (struct foobar));
112   ptr->name = x;
113   ptr->next = current_foobar;
114   current_foobar = ptr;
115 @}
116 @end smallexample
117
118 @node Unconstrained Allocation
119 @section Unconstrained Allocation
120 @cindex unconstrained storage allocation
121 @cindex @code{malloc} function
122 @cindex heap, dynamic allocation from
123
124 The most general dynamic allocation facility is @code{malloc}.  It
125 allows you to allocate blocks of memory of any size at any time, make
126 them bigger or smaller at any time, and free the blocks individually at
127 any time (or never).
128
129 @menu
130 * Basic Allocation::            Simple use of @code{malloc}.
131 * Malloc Examples::             Examples of @code{malloc}.  @code{xmalloc}.
132 * Freeing after Malloc::        Use @code{free} to free a block you
133                                  got with @code{malloc}.
134 * Changing Block Size::         Use @code{realloc} to make a block
135                                  bigger or smaller.
136 * Allocating Cleared Space::    Use @code{calloc} to allocate a
137                                  block and clear it.
138 * Efficiency and Malloc::       Efficiency considerations in use of
139                                  these functions.
140 * Aligned Memory Blocks::       Allocating specially aligned memory:
141                                  @code{memalign} and @code{valloc}.
142 * Malloc Tunable Parameters::   Use @code{mallopt} to adjust allocation
143                                  parameters.
144 * Heap Consistency Checking::   Automatic checking for errors.
145 * Hooks for Malloc::            You can use these hooks for debugging
146                                  programs that use @code{malloc}.
147 * Statistics of Malloc::        Getting information about how much
148                                  memory your program is using.
149 * Summary of Malloc::           Summary of @code{malloc} and related functions.
150 @end menu
151
152 @node Basic Allocation
153 @subsection Basic Storage Allocation
154 @cindex allocation of memory with @code{malloc}
155
156 To allocate a block of memory, call @code{malloc}.  The prototype for
157 this function is in @file{stdlib.h}.
158 @pindex stdlib.h
159
160 @comment malloc.h stdlib.h
161 @comment ISO
162 @deftypefun {void *} malloc (size_t @var{size})
163 This function returns a pointer to a newly allocated block @var{size}
164 bytes long, or a null pointer if the block could not be allocated.
165 @end deftypefun
166
167 The contents of the block are undefined; you must initialize it yourself
168 (or use @code{calloc} instead; @pxref{Allocating Cleared Space}).
169 Normally you would cast the value as a pointer to the kind of object
170 that you want to store in the block.  Here we show an example of doing
171 so, and of initializing the space with zeros using the library function
172 @code{memset} (@pxref{Copying and Concatenation}):
173
174 @smallexample
175 struct foo *ptr;
176 @dots{}
177 ptr = (struct foo *) malloc (sizeof (struct foo));
178 if (ptr == 0) abort ();
179 memset (ptr, 0, sizeof (struct foo));
180 @end smallexample
181
182 You can store the result of @code{malloc} into any pointer variable
183 without a cast, because @w{ISO C} automatically converts the type
184 @code{void *} to another type of pointer when necessary.  But the cast
185 is necessary in contexts other than assignment operators or if you might
186 want your code to run in traditional C.
187
188 Remember that when allocating space for a string, the argument to
189 @code{malloc} must be one plus the length of the string.  This is
190 because a string is terminated with a null character that doesn't count
191 in the ``length'' of the string but does need space.  For example:
192
193 @smallexample
194 char *ptr;
195 @dots{}
196 ptr = (char *) malloc (length + 1);
197 @end smallexample
198
199 @noindent
200 @xref{Representation of Strings}, for more information about this.
201
202 @node Malloc Examples
203 @subsection Examples of @code{malloc}
204
205 If no more space is available, @code{malloc} returns a null pointer.
206 You should check the value of @emph{every} call to @code{malloc}.  It is
207 useful to write a subroutine that calls @code{malloc} and reports an
208 error if the value is a null pointer, returning only if the value is
209 nonzero.  This function is conventionally called @code{xmalloc}.  Here
210 it is:
211
212 @smallexample
213 void *
214 xmalloc (size_t size)
215 @{
216   register void *value = malloc (size);
217   if (value == 0)
218     fatal ("virtual memory exhausted");
219   return value;
220 @}
221 @end smallexample
222
223 Here is a real example of using @code{malloc} (by way of @code{xmalloc}).
224 The function @code{savestring} will copy a sequence of characters into
225 a newly allocated null-terminated string:
226
227 @smallexample
228 @group
229 char *
230 savestring (const char *ptr, size_t len)
231 @{
232   register char *value = (char *) xmalloc (len + 1);
233   memcpy (value, ptr, len);
234   value[len] = '\0';
235   return value;
236 @}
237 @end group
238 @end smallexample
239
240 The block that @code{malloc} gives you is guaranteed to be aligned so
241 that it can hold any type of data.  In the GNU system, the address is
242 always a multiple of eight on most systems, and a multiple of 16 on
243 64-bit systems.  Only rarely is any higher boundary (such as a page
244 boundary) necessary; for those cases, use @code{memalign} or
245 @code{valloc} (@pxref{Aligned Memory Blocks}).
246
247 Note that the memory located after the end of the block is likely to be
248 in use for something else; perhaps a block already allocated by another
249 call to @code{malloc}.  If you attempt to treat the block as longer than
250 you asked for it to be, you are liable to destroy the data that
251 @code{malloc} uses to keep track of its blocks, or you may destroy the
252 contents of another block.  If you have already allocated a block and
253 discover you want it to be bigger, use @code{realloc} (@pxref{Changing
254 Block Size}).
255
256 @node Freeing after Malloc
257 @subsection Freeing Memory Allocated with @code{malloc}
258 @cindex freeing memory allocated with @code{malloc}
259 @cindex heap, freeing memory from
260
261 When you no longer need a block that you got with @code{malloc}, use the
262 function @code{free} to make the block available to be allocated again.
263 The prototype for this function is in @file{stdlib.h}.
264 @pindex stdlib.h
265
266 @comment malloc.h stdlib.h
267 @comment ISO
268 @deftypefun void free (void *@var{ptr})
269 The @code{free} function deallocates the block of storage pointed at
270 by @var{ptr}.
271 @end deftypefun
272
273 @comment stdlib.h
274 @comment Sun
275 @deftypefun void cfree (void *@var{ptr})
276 This function does the same thing as @code{free}.  It's provided for
277 backward compatibility with SunOS; you should use @code{free} instead.
278 @end deftypefun
279
280 Freeing a block alters the contents of the block.  @strong{Do not expect to
281 find any data (such as a pointer to the next block in a chain of blocks) in
282 the block after freeing it.}  Copy whatever you need out of the block before
283 freeing it!  Here is an example of the proper way to free all the blocks in
284 a chain, and the strings that they point to:
285
286 @smallexample
287 struct chain
288   @{
289     struct chain *next;
290     char *name;
291   @}
292
293 void
294 free_chain (struct chain *chain)
295 @{
296   while (chain != 0)
297     @{
298       struct chain *next = chain->next;
299       free (chain->name);
300       free (chain);
301       chain = next;
302     @}
303 @}
304 @end smallexample
305
306 Occasionally, @code{free} can actually return memory to the operating
307 system and make the process smaller.  Usually, all it can do is allow a
308 later call to @code{malloc} to reuse the space.  In the meantime, the
309 space remains in your program as part of a free-list used internally by
310 @code{malloc}.
311
312 There is no point in freeing blocks at the end of a program, because all
313 of the program's space is given back to the system when the process
314 terminates.
315
316 @node Changing Block Size
317 @subsection Changing the Size of a Block
318 @cindex changing the size of a block (@code{malloc})
319
320 Often you do not know for certain how big a block you will ultimately need
321 at the time you must begin to use the block.  For example, the block might
322 be a buffer that you use to hold a line being read from a file; no matter
323 how long you make the buffer initially, you may encounter a line that is
324 longer.
325
326 You can make the block longer by calling @code{realloc}.  This function
327 is declared in @file{stdlib.h}.
328 @pindex stdlib.h
329
330 @comment malloc.h stdlib.h
331 @comment ISO
332 @deftypefun {void *} realloc (void *@var{ptr}, size_t @var{newsize})
333 The @code{realloc} function changes the size of the block whose address is
334 @var{ptr} to be @var{newsize}.
335
336 Since the space after the end of the block may be in use, @code{realloc}
337 may find it necessary to copy the block to a new address where more free
338 space is available.  The value of @code{realloc} is the new address of the
339 block.  If the block needs to be moved, @code{realloc} copies the old
340 contents.
341
342 If you pass a null pointer for @var{ptr}, @code{realloc} behaves just
343 like @samp{malloc (@var{newsize})}.  This can be convenient, but beware
344 that older implementations (before @w{ISO C}) may not support this
345 behavior, and will probably crash when @code{realloc} is passed a null
346 pointer.
347 @end deftypefun
348
349 Like @code{malloc}, @code{realloc} may return a null pointer if no
350 memory space is available to make the block bigger.  When this happens,
351 the original block is untouched; it has not been modified or relocated.
352
353 In most cases it makes no difference what happens to the original block
354 when @code{realloc} fails, because the application program cannot continue
355 when it is out of memory, and the only thing to do is to give a fatal error
356 message.  Often it is convenient to write and use a subroutine,
357 conventionally called @code{xrealloc}, that takes care of the error message
358 as @code{xmalloc} does for @code{malloc}:
359
360 @smallexample
361 void *
362 xrealloc (void *ptr, size_t size)
363 @{
364   register void *value = realloc (ptr, size);
365   if (value == 0)
366     fatal ("Virtual memory exhausted");
367   return value;
368 @}
369 @end smallexample
370
371 You can also use @code{realloc} to make a block smaller.  The reason you
372 is needed.
373 @comment The following is no longer true with the new malloc.
374 @comment But it seems wise to keep the warning for other implementations.
375 In several allocation implementations, making a block smaller sometimes
376 necessitates copying it, so it can fail if no other space is available.
377
378 If the new size you specify is the same as the old size, @code{realloc}
379 is guaranteed to change nothing and return the same address that you gave.
380
381 @node Allocating Cleared Space
382 @subsection Allocating Cleared Space
383
384 The function @code{calloc} allocates memory and clears it to zero.  It
385 is declared in @file{stdlib.h}.
386 @pindex stdlib.h
387
388 @comment malloc.h stdlib.h
389 @comment ISO
390 @deftypefun {void *} calloc (size_t @var{count}, size_t @var{eltsize})
391 This function allocates a block long enough to contain a vector of
392 @var{count} elements, each of size @var{eltsize}.  Its contents are
393 cleared to zero before @code{calloc} returns.
394 @end deftypefun
395
396 You could define @code{calloc} as follows:
397
398 @smallexample
399 void *
400 calloc (size_t count, size_t eltsize)
401 @{
402   size_t size = count * eltsize;
403   void *value = malloc (size);
404   if (value != 0)
405     memset (value, 0, size);
406   return value;
407 @}
408 @end smallexample
409
410 But in general, it is not guaranteed that @code{calloc} calls
411 @code{malloc} internally.  Therefore, if an application provides its own
412 @code{malloc}/@code{realloc}/@code{free} outside the C library, it
413 should always define @code{calloc}, too.
414
415 @node Efficiency and Malloc
416 @subsection Efficiency Considerations for @code{malloc}
417 @cindex efficiency and @code{malloc}
418
419 @ignore
420
421 @c No longer true, see below instead.
422 To make the best use of @code{malloc}, it helps to know that the GNU
423 version of @code{malloc} always dispenses small amounts of memory in
424 blocks whose sizes are powers of two.  It keeps separate pools for each
425 power of two.  This holds for sizes up to a page size.  Therefore, if
426 you are free to choose the size of a small block in order to make
427 @code{malloc} more efficient, make it a power of two.
428 @c !!! xref getpagesize
429
430 Once a page is split up for a particular block size, it can't be reused
431 for another size unless all the blocks in it are freed.  In many
432 programs, this is unlikely to happen.  Thus, you can sometimes make a
433 program use memory more efficiently by using blocks of the same size for
434 many different purposes.
435
436 When you ask for memory blocks of a page or larger, @code{malloc} uses a
437 different strategy; it rounds the size up to a multiple of a page, and
438 it can coalesce and split blocks as needed.
439
440 The reason for the two strategies is that it is important to allocate
441 and free small blocks as fast as possible, but speed is less important
442 for a large block since the program normally spends a fair amount of
443 time using it.  Also, large blocks are normally fewer in number.
444 Therefore, for large blocks, it makes sense to use a method which takes
445 more time to minimize the wasted space.
446
447 @end ignore
448
449 As apposed to other versions, the @code{malloc} in GNU libc does not
450 round up block sizes to powers of two, neither for large nor for small
451 sizes.  Neighboring chunks can be coalesced on a @code{free} no matter
452 what their size is.  This makes the implementation suitable for all
453 kinds of allocation patterns without generally incurring high memory
454 waste through fragmentation.
455
456 Very large blocks (much larger than a page) are allocated with
457 @code{mmap} (anonymous or via @code{/dev/zero}) by this implementation.
458 This has the great advantage that these chunks are returned to the
459 system immediately when they are freed.  Therefore, it cannot happen
460 that a large chunk becomes ``locked'' in between smaller ones and even
461 after calling @code{free} wastes memory.  The size threshold for
462 @code{mmap} to be used can be adjusted with @code{mallopt}.  The use of
463 @code{mmap} can also be disabled completely.
464
465 @node Aligned Memory Blocks
466 @subsection Allocating Aligned Memory Blocks
467
468 @cindex page boundary
469 @cindex alignment (with @code{malloc})
470 @pindex stdlib.h
471 The address of a block returned by @code{malloc} or @code{realloc} in
472 the GNU system is always a multiple of eight (or sixteen on 64-bit
473 systems).  If you need a block whose address is a multiple of a higher
474 power of two than that, use @code{memalign} or @code{valloc}.  These
475 functions are declared in @file{stdlib.h}.
476
477 With the GNU library, you can use @code{free} to free the blocks that
478 @code{memalign} and @code{valloc} return.  That does not work in BSD,
479 however---BSD does not provide any way to free such blocks.
480
481 @comment malloc.h stdlib.h
482 @comment BSD
483 @deftypefun {void *} memalign (size_t @var{boundary}, size_t @var{size})
484 The @code{memalign} function allocates a block of @var{size} bytes whose
485 address is a multiple of @var{boundary}.  The @var{boundary} must be a
486 power of two!  The function @code{memalign} works by allocating a
487 somewhat larger block, and then returning an address within the block
488 that is on the specified boundary.
489 @end deftypefun
490
491 @comment malloc.h stdlib.h
492 @comment BSD
493 @deftypefun {void *} valloc (size_t @var{size})
494 Using @code{valloc} is like using @code{memalign} and passing the page size
495 as the value of the second argument.  It is implemented like this:
496
497 @smallexample
498 void *
499 valloc (size_t size)
500 @{
501   return memalign (getpagesize (), size);
502 @}
503 @end smallexample
504 @c !!! xref getpagesize
505 @end deftypefun
506
507 @node Malloc Tunable Parameters
508 @subsection Malloc Tunable Parameters
509
510 You can adjust some parameters for dynamic memory allocation with the
511 @code{mallopt} function.  This function is the general SVID/XPG
512 interface, defined in @file{malloc.h}.
513 @pindex malloc.h
514
515 @deftypefun int mallopt (int @var{param}, int @var{value})
516 When calling @code{mallopt}, the @var{param} argument specifies the
517 parameter to be set, and @var{value} the new value to be set.  Possible
518 choices for @var{param}, as defined in @file{malloc.h}, are:
519
520 @table @code
521 @item M_TRIM_THRESHOLD
522 This is the minimum size (in bytes) of the top-most, releaseable chunk
523 that will cause @code{sbrk} to be called with a negative argument in
524 order to return memory to the system.
525 @item M_TOP_PAD
526 This parameter determines the amount of extra memory to obtain from the
527 system when a call to @code{sbrk} is required.  It also specifies the
528 number of bytes to retain when shrinking the heap by calling @code{sbrk}
529 with a negative argument.  This provides the necessary hysteresis in
530 heap size such that excessive amounts of system calls can be avoided.
531 @item M_MMAP_THRESHOLD
532 All chunks larger than this value are allocated outside the normal
533 heap, using the @code{mmap} system call.  This way it is guaranteed
534 that the memory for these chunks can be returned to the system on
535 @code{free}.
536 @item M_MMAP_MAX
537 The maximum number of chunks to allocate with @code{mmap}.  Setting this
538 to zero disables all use of @code{mmap}.
539 @end table
540
541 @end deftypefun
542
543 @node Heap Consistency Checking
544 @subsection Heap Consistency Checking
545
546 @cindex heap consistency checking
547 @cindex consistency checking, of heap
548
549 You can ask @code{malloc} to check the consistency of dynamic storage by
550 using the @code{mcheck} function.  This function is a GNU extension,
551 declared in @file{malloc.h}.
552 @pindex malloc.h
553
554 @comment malloc.h
555 @comment GNU
556 @deftypefun int mcheck (void (*@var{abortfn}) (enum mcheck_status @var{status}))
557 Calling @code{mcheck} tells @code{malloc} to perform occasional
558 consistency checks.  These will catch things such as writing
559 past the end of a block that was allocated with @code{malloc}.
560
561 The @var{abortfn} argument is the function to call when an inconsistency
562 is found.  If you supply a null pointer, then @code{mcheck} uses a
563 default function which prints a message and calls @code{abort}
564 (@pxref{Aborting a Program}).  The function you supply is called with
565 one argument, which says what sort of inconsistency was detected; its
566 type is described below.
567
568 It is too late to begin allocation checking once you have allocated
569 anything with @code{malloc}.  So @code{mcheck} does nothing in that
570 case.  The function returns @code{-1} if you call it too late, and
571 @code{0} otherwise (when it is successful).
572
573 The easiest way to arrange to call @code{mcheck} early enough is to use
574 the option @samp{-lmcheck} when you link your program; then you don't
575 need to modify your program source at all.
576 @end deftypefun
577
578 @deftypefun {enum mcheck_status} mprobe (void *@var{pointer})
579 The @code{mprobe} function lets you explicitly check for inconsistencies
580 in a particular allocated block.  You must have already called
581 @code{mcheck} at the beginning of the program, to do its occasional
582 checks; calling @code{mprobe} requests an additional consistency check
583 to be done at the time of the call.
584
585 The argument @var{pointer} must be a pointer returned by @code{malloc}
586 or @code{realloc}.  @code{mprobe} returns a value that says what
587 inconsistency, if any, was found.  The values are described below.
588 @end deftypefun
589
590 @deftp {Data Type} {enum mcheck_status}
591 This enumerated type describes what kind of inconsistency was detected
592 in an allocated block, if any.  Here are the possible values:
593
594 @table @code
595 @item MCHECK_DISABLED
596 @code{mcheck} was not called before the first allocation.
597 No consistency checking can be done.
598 @item MCHECK_OK
599 No inconsistency detected.
600 @item MCHECK_HEAD
601 The data immediately before the block was modified.
602 This commonly happens when an array index or pointer
603 is decremented too far.
604 @item MCHECK_TAIL
605 The data immediately after the block was modified.
606 This commonly happens when an array index or pointer
607 is incremented too far.
608 @item MCHECK_FREE
609 The block was already freed.
610 @end table
611 @end deftp
612
613 @node Hooks for Malloc
614 @subsection Storage Allocation Hooks
615 @cindex allocation hooks, for @code{malloc}
616
617 The GNU C library lets you modify the behavior of @code{malloc},
618 @code{realloc}, and @code{free} by specifying appropriate hook
619 functions.  You can use these hooks to help you debug programs that use
620 dynamic storage allocation, for example.
621
622 The hook variables are declared in @file{malloc.h}.
623 @pindex malloc.h
624
625 @comment malloc.h
626 @comment GNU
627 @defvar __malloc_hook
628 The value of this variable is a pointer to function that @code{malloc}
629 uses whenever it is called.  You should define this function to look
630 like @code{malloc}; that is, like:
631
632 @smallexample
633 void *@var{function} (size_t @var{size})
634 @end smallexample
635 @end defvar
636
637 @comment malloc.h
638 @comment GNU
639 @defvar __realloc_hook
640 The value of this variable is a pointer to function that @code{realloc}
641 uses whenever it is called.  You should define this function to look
642 like @code{realloc}; that is, like:
643
644 @smallexample
645 void *@var{function} (void *@var{ptr}, size_t @var{size})
646 @end smallexample
647 @end defvar
648
649 @comment malloc.h
650 @comment GNU
651 @defvar __free_hook
652 The value of this variable is a pointer to function that @code{free}
653 uses whenever it is called.  You should define this function to look
654 like @code{free}; that is, like:
655
656 @smallexample
657 void @var{function} (void *@var{ptr})
658 @end smallexample
659 @end defvar
660
661 You must make sure that the function you install as a hook for one of
662 these functions does not call that function recursively without restoring
663 the old value of the hook first!  Otherwise, your program will get stuck
664 in an infinite recursion.
665
666 Here is an example showing how to use @code{__malloc_hook} properly.  It
667 installs a function that prints out information every time @code{malloc}
668 is called.
669
670 @smallexample
671 static void *(*old_malloc_hook) (size_t);
672 static void *
673 my_malloc_hook (size_t size)
674 @{
675   void *result;
676   __malloc_hook = old_malloc_hook;
677   result = malloc (size);
678   /* @r{@code{printf} might call @code{malloc}, so protect it too.} */
679   printf ("malloc (%u) returns %p\n", (unsigned int) size, result);
680   __malloc_hook = my_malloc_hook;
681   return result;
682 @}
683
684 main ()
685 @{
686   ...
687   old_malloc_hook = __malloc_hook;
688   __malloc_hook = my_malloc_hook;
689   ...
690 @}
691 @end smallexample
692
693 The @code{mcheck} function (@pxref{Heap Consistency Checking}) works by
694 installing such hooks.
695
696 @c __morecore, __after_morecore_hook are undocumented
697 @c It's not clear whether to document them.
698
699 @node Statistics of Malloc
700 @subsection Statistics for Storage Allocation with @code{malloc}
701
702 @cindex allocation statistics
703 You can get information about dynamic storage allocation by calling the
704 @code{mallinfo} function.  This function and its associated data type
705 are declared in @file{malloc.h}; they are an extension of the standard
706 SVID/XPG version.
707 @pindex malloc.h
708
709 @comment malloc.h
710 @comment GNU
711 @deftp {Data Type} {struct mallinfo}
712 This structure type is used to return information about the dynamic
713 storage allocator.  It contains the following members:
714
715 @table @code
716 @item int arena
717 This is the total size of memory allocated with @code{sbrk} by
718 @code{malloc}, in bytes.
719
720 @item int ordblks
721 This is the number of chunks not in use.  (The storage allocator
722 internally gets chunks of memory from the operating system, and then
723 carves them up to satisfy individual @code{malloc} requests; see
724 @ref{Efficiency and Malloc}.)
725
726 @item int smblks
727 This field is unused.
728
729 @item int hblks
730 This is the total number of chunks allocated with @code{mmap}.
731
732 @item int hblkhd
733 This is the total size of memory allocated with @code{mmap}, in bytes.
734
735 @item int usmblks
736 This field is unused.
737
738 @item int fsmblks
739 This field is unused.
740
741 @item int uordblks
742 This is the total size of memory occupied by chunks handed out by
743 @code{malloc}.
744
745 @item int fordblks
746 This is the total size of memory occupied by free (not in use) chunks.
747
748 @item int keepcost
749 This is the size of the top-most, releaseable chunk that normally
750 borders the end of the heap (i.e. the ``brk'' of the process).
751
752 @end table
753 @end deftp
754
755 @comment malloc.h
756 @comment SVID
757 @deftypefun {struct mallinfo} mallinfo (void)
758 This function returns information about the current dynamic memory usage
759 in a structure of type @code{struct mallinfo}.
760 @end deftypefun
761
762 @node Summary of Malloc
763 @subsection Summary of @code{malloc}-Related Functions
764
765 Here is a summary of the functions that work with @code{malloc}:
766
767 @table @code
768 @item void *malloc (size_t @var{size})
769 Allocate a block of @var{size} bytes.  @xref{Basic Allocation}.
770
771 @item void free (void *@var{addr})
772 Free a block previously allocated by @code{malloc}.  @xref{Freeing after
773 Malloc}.
774
775 @item void *realloc (void *@var{addr}, size_t @var{size})
776 Make a block previously allocated by @code{malloc} larger or smaller,
777 possibly by copying it to a new location.  @xref{Changing Block Size}.
778
779 @item void *calloc (size_t @var{count}, size_t @var{eltsize})
780 Allocate a block of @var{count} * @var{eltsize} bytes using
781 @code{malloc}, and set its contents to zero.  @xref{Allocating Cleared
782 Space}.
783
784 @item void *valloc (size_t @var{size})
785 Allocate a block of @var{size} bytes, starting on a page boundary.
786 @xref{Aligned Memory Blocks}.
787
788 @item void *memalign (size_t @var{size}, size_t @var{boundary})
789 Allocate a block of @var{size} bytes, starting on an address that is a
790 multiple of @var{boundary}.  @xref{Aligned Memory Blocks}.
791
792 @item int mallopt (int @var{param}, int @var{value})
793 Adjust a tunable parameter.  @xref{Malloc Tunable Parameters}
794
795 @item int mcheck (void (*@var{abortfn}) (void))
796 Tell @code{malloc} to perform occasional consistency checks on
797 dynamically allocated memory, and to call @var{abortfn} when an
798 inconsistency is found.  @xref{Heap Consistency Checking}.
799
800 @item void *(*__malloc_hook) (size_t @var{size})
801 A pointer to a function that @code{malloc} uses whenever it is called.
802
803 @item void *(*__realloc_hook) (void *@var{ptr}, size_t @var{size})
804 A pointer to a function that @code{realloc} uses whenever it is called.
805
806 @item void (*__free_hook) (void *@var{ptr})
807 A pointer to a function that @code{free} uses whenever it is called.
808
809 @item struct mallinfo mallinfo (void)
810 Return information about the current dynamic memory usage.
811 @xref{Statistics of Malloc}.
812 @end table
813
814 @node Obstacks
815 @section Obstacks
816 @cindex obstacks
817
818 An @dfn{obstack} is a pool of memory containing a stack of objects.  You
819 can create any number of separate obstacks, and then allocate objects in
820 specified obstacks.  Within each obstack, the last object allocated must
821 always be the first one freed, but distinct obstacks are independent of
822 each other.
823
824 Aside from this one constraint of order of freeing, obstacks are totally
825 general: an obstack can contain any number of objects of any size.  They
826 are implemented with macros, so allocation is usually very fast as long as
827 the objects are usually small.  And the only space overhead per object is
828 the padding needed to start each object on a suitable boundary.
829
830 @menu
831 * Creating Obstacks::           How to declare an obstack in your program.
832 * Preparing for Obstacks::      Preparations needed before you can
833                                  use obstacks.
834 * Allocation in an Obstack::    Allocating objects in an obstack.
835 * Freeing Obstack Objects::     Freeing objects in an obstack.
836 * Obstack Functions::           The obstack functions are both
837                                  functions and macros.
838 * Growing Objects::             Making an object bigger by stages.
839 * Extra Fast Growing::          Extra-high-efficiency (though more
840                                  complicated) growing objects.
841 * Status of an Obstack::        Inquiries about the status of an obstack.
842 * Obstacks Data Alignment::     Controlling alignment of objects in obstacks.
843 * Obstack Chunks::              How obstacks obtain and release chunks;
844                                  efficiency considerations.
845 * Summary of Obstacks::
846 @end menu
847
848 @node Creating Obstacks
849 @subsection Creating Obstacks
850
851 The utilities for manipulating obstacks are declared in the header
852 file @file{obstack.h}.
853 @pindex obstack.h
854
855 @comment obstack.h
856 @comment GNU
857 @deftp {Data Type} {struct obstack}
858 An obstack is represented by a data structure of type @code{struct
859 obstack}.  This structure has a small fixed size; it records the status
860 of the obstack and how to find the space in which objects are allocated.
861 It does not contain any of the objects themselves.  You should not try
862 to access the contents of the structure directly; use only the functions
863 described in this chapter.
864 @end deftp
865
866 You can declare variables of type @code{struct obstack} and use them as
867 obstacks, or you can allocate obstacks dynamically like any other kind
868 of object.  Dynamic allocation of obstacks allows your program to have a
869 variable number of different stacks.  (You can even allocate an
870 obstack structure in another obstack, but this is rarely useful.)
871
872 All the functions that work with obstacks require you to specify which
873 obstack to use.  You do this with a pointer of type @code{struct obstack
874 *}.  In the following, we often say ``an obstack'' when strictly
875 speaking the object at hand is such a pointer.
876
877 The objects in the obstack are packed into large blocks called
878 @dfn{chunks}.  The @code{struct obstack} structure points to a chain of
879 the chunks currently in use.
880
881 The obstack library obtains a new chunk whenever you allocate an object
882 that won't fit in the previous chunk.  Since the obstack library manages
883 chunks automatically, you don't need to pay much attention to them, but
884 you do need to supply a function which the obstack library should use to
885 get a chunk.  Usually you supply a function which uses @code{malloc}
886 directly or indirectly.  You must also supply a function to free a chunk.
887 These matters are described in the following section.
888
889 @node Preparing for Obstacks
890 @subsection Preparing for Using Obstacks
891
892 Each source file in which you plan to use the obstack functions
893 must include the header file @file{obstack.h}, like this:
894
895 @smallexample
896 #include <obstack.h>
897 @end smallexample
898
899 @findex obstack_chunk_alloc
900 @findex obstack_chunk_free
901 Also, if the source file uses the macro @code{obstack_init}, it must
902 declare or define two functions or macros that will be called by the
903 obstack library.  One, @code{obstack_chunk_alloc}, is used to allocate
904 the chunks of memory into which objects are packed.  The other,
905 @code{obstack_chunk_free}, is used to return chunks when the objects in
906 them are freed.  These macros should appear before any use of obstacks
907 in the source file.
908
909 Usually these are defined to use @code{malloc} via the intermediary
910 @code{xmalloc} (@pxref{Unconstrained Allocation}).  This is done with
911 the following pair of macro definitions:
912
913 @smallexample
914 #define obstack_chunk_alloc xmalloc
915 #define obstack_chunk_free free
916 @end smallexample
917
918 @noindent
919 Though the storage you get using obstacks really comes from @code{malloc},
920 using obstacks is faster because @code{malloc} is called less often, for
921 larger blocks of memory.  @xref{Obstack Chunks}, for full details.
922
923 At run time, before the program can use a @code{struct obstack} object
924 as an obstack, it must initialize the obstack by calling
925 @code{obstack_init}.
926
927 @comment obstack.h
928 @comment GNU
929 @deftypefun int obstack_init (struct obstack *@var{obstack-ptr})
930 Initialize obstack @var{obstack-ptr} for allocation of objects.  This
931 function calls the obstack's @code{obstack_chunk_alloc} function.  It
932 returns 0 if @code{obstack_chunk_alloc} returns a null pointer, meaning
933 that it is out of memory.  Otherwise, it returns 1.  If you supply an
934 @code{obstack_chunk_alloc} function that calls @code{exit}
935 (@pxref{Program Termination}) or @code{longjmp} (@pxref{Non-Local
936 Exits}) when out of memory, you can safely ignore the value that
937 @code{obstack_init} returns.
938 @end deftypefun
939
940 Here are two examples of how to allocate the space for an obstack and
941 initialize it.  First, an obstack that is a static variable:
942
943 @smallexample
944 static struct obstack myobstack;
945 @dots{}
946 obstack_init (&myobstack);
947 @end smallexample
948
949 @noindent
950 Second, an obstack that is itself dynamically allocated:
951
952 @smallexample
953 struct obstack *myobstack_ptr
954   = (struct obstack *) xmalloc (sizeof (struct obstack));
955
956 obstack_init (myobstack_ptr);
957 @end smallexample
958
959 @node Allocation in an Obstack
960 @subsection Allocation in an Obstack
961 @cindex allocation (obstacks)
962
963 The most direct way to allocate an object in an obstack is with
964 @code{obstack_alloc}, which is invoked almost like @code{malloc}.
965
966 @comment obstack.h
967 @comment GNU
968 @deftypefun {void *} obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
969 This allocates an uninitialized block of @var{size} bytes in an obstack
970 and returns its address.  Here @var{obstack-ptr} specifies which obstack
971 to allocate the block in; it is the address of the @code{struct obstack}
972 object which represents the obstack.  Each obstack function or macro
973 requires you to specify an @var{obstack-ptr} as the first argument.
974
975 This function calls the obstack's @code{obstack_chunk_alloc} function if
976 it needs to allocate a new chunk of memory; it returns a null pointer if
977 @code{obstack_chunk_alloc} returns one.  In that case, it has not
978 changed the amount of memory allocated in the obstack.  If you supply an
979 @code{obstack_chunk_alloc} function that calls @code{exit}
980 (@pxref{Program Termination}) or @code{longjmp} (@pxref{Non-Local
981 Exits}) when out of memory, then @code{obstack_alloc} will never return
982 a null pointer.
983 @end deftypefun
984
985 For example, here is a function that allocates a copy of a string @var{str}
986 in a specific obstack, which is in the variable @code{string_obstack}:
987
988 @smallexample
989 struct obstack string_obstack;
990
991 char *
992 copystring (char *string)
993 @{
994   size_t len = strlen (string) + 1;
995   char *s = (char *) obstack_alloc (&string_obstack, len);
996   memcpy (s, string, len);
997   return s;
998 @}
999 @end smallexample
1000
1001 To allocate a block with specified contents, use the function
1002 @code{obstack_copy}, declared like this:
1003
1004 @comment obstack.h
1005 @comment GNU
1006 @deftypefun {void *} obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1007 This allocates a block and initializes it by copying @var{size}
1008 bytes of data starting at @var{address}.  It can return a null pointer
1009 under the same conditions as @code{obstack_alloc}.
1010 @end deftypefun
1011
1012 @comment obstack.h
1013 @comment GNU
1014 @deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1015 Like @code{obstack_copy}, but appends an extra byte containing a null
1016 character.  This extra byte is not counted in the argument @var{size}.
1017 @end deftypefun
1018
1019 The @code{obstack_copy0} function is convenient for copying a sequence
1020 of characters into an obstack as a null-terminated string.  Here is an
1021 example of its use:
1022
1023 @smallexample
1024 char *
1025 obstack_savestring (char *addr, int size)
1026 @{
1027   return obstack_copy0 (&myobstack, addr, size);
1028 @}
1029 @end smallexample
1030
1031 @noindent
1032 Contrast this with the previous example of @code{savestring} using
1033 @code{malloc} (@pxref{Basic Allocation}).
1034
1035 @node Freeing Obstack Objects
1036 @subsection Freeing Objects in an Obstack
1037 @cindex freeing (obstacks)
1038
1039 To free an object allocated in an obstack, use the function
1040 @code{obstack_free}.  Since the obstack is a stack of objects, freeing
1041 one object automatically frees all other objects allocated more recently
1042 in the same obstack.
1043
1044 @comment obstack.h
1045 @comment GNU
1046 @deftypefun void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
1047 If @var{object} is a null pointer, everything allocated in the obstack
1048 is freed.  Otherwise, @var{object} must be the address of an object
1049 allocated in the obstack.  Then @var{object} is freed, along with
1050 everything allocated in @var{obstack} since @var{object}.
1051 @end deftypefun
1052
1053 Note that if @var{object} is a null pointer, the result is an
1054 uninitialized obstack.  To free all storage in an obstack but leave it
1055 valid for further allocation, call @code{obstack_free} with the address
1056 of the first object allocated on the obstack:
1057
1058 @smallexample
1059 obstack_free (obstack_ptr, first_object_allocated_ptr);
1060 @end smallexample
1061
1062 Recall that the objects in an obstack are grouped into chunks.  When all
1063 the objects in a chunk become free, the obstack library automatically
1064 frees the chunk (@pxref{Preparing for Obstacks}).  Then other
1065 obstacks, or non-obstack allocation, can reuse the space of the chunk.
1066
1067 @node Obstack Functions
1068 @subsection Obstack Functions and Macros
1069 @cindex macros
1070
1071 The interfaces for using obstacks may be defined either as functions or
1072 as macros, depending on the compiler.  The obstack facility works with
1073 all C compilers, including both @w{ISO C} and traditional C, but there are
1074 precautions you must take if you plan to use compilers other than GNU C.
1075
1076 If you are using an old-fashioned @w{non-ISO C} compiler, all the obstack
1077 ``functions'' are actually defined only as macros.  You can call these
1078 macros like functions, but you cannot use them in any other way (for
1079 example, you cannot take their address).
1080
1081 Calling the macros requires a special precaution: namely, the first
1082 operand (the obstack pointer) may not contain any side effects, because
1083 it may be computed more than once.  For example, if you write this:
1084
1085 @smallexample
1086 obstack_alloc (get_obstack (), 4);
1087 @end smallexample
1088
1089 @noindent
1090 you will find that @code{get_obstack} may be called several times.
1091 If you use @code{*obstack_list_ptr++} as the obstack pointer argument,
1092 you will get very strange results since the incrementation may occur
1093 several times.
1094
1095 In @w{ISO C}, each function has both a macro definition and a function
1096 definition.  The function definition is used if you take the address of the
1097 function without calling it.  An ordinary call uses the macro definition by
1098 default, but you can request the function definition instead by writing the
1099 function name in parentheses, as shown here:
1100
1101 @smallexample
1102 char *x;
1103 void *(*funcp) ();
1104 /* @r{Use the macro}.  */
1105 x = (char *) obstack_alloc (obptr, size);
1106 /* @r{Call the function}.  */
1107 x = (char *) (obstack_alloc) (obptr, size);
1108 /* @r{Take the address of the function}.  */
1109 funcp = obstack_alloc;
1110 @end smallexample
1111
1112 @noindent
1113 This is the same situation that exists in @w{ISO C} for the standard library
1114 functions.  @xref{Macro Definitions}.
1115
1116 @strong{Warning:} When you do use the macros, you must observe the
1117 precaution of avoiding side effects in the first operand, even in @w{ISO C}.
1118
1119 If you use the GNU C compiler, this precaution is not necessary, because
1120 various language extensions in GNU C permit defining the macros so as to
1121 compute each argument only once.
1122
1123 @node Growing Objects
1124 @subsection Growing Objects
1125 @cindex growing objects (in obstacks)
1126 @cindex changing the size of a block (obstacks)
1127
1128 Because storage in obstack chunks is used sequentially, it is possible to
1129 build up an object step by step, adding one or more bytes at a time to the
1130 end of the object.  With this technique, you do not need to know how much
1131 data you will put in the object until you come to the end of it.  We call
1132 this the technique of @dfn{growing objects}.  The special functions
1133 for adding data to the growing object are described in this section.
1134
1135 You don't need to do anything special when you start to grow an object.
1136 Using one of the functions to add data to the object automatically
1137 starts it.  However, it is necessary to say explicitly when the object is
1138 finished.  This is done with the function @code{obstack_finish}.
1139
1140 The actual address of the object thus built up is not known until the
1141 object is finished.  Until then, it always remains possible that you will
1142 add so much data that the object must be copied into a new chunk.
1143
1144 While the obstack is in use for a growing object, you cannot use it for
1145 ordinary allocation of another object.  If you try to do so, the space
1146 already added to the growing object will become part of the other object.
1147
1148 @comment obstack.h
1149 @comment GNU
1150 @deftypefun void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
1151 The most basic function for adding to a growing object is
1152 @code{obstack_blank}, which adds space without initializing it.
1153 @end deftypefun
1154
1155 @comment obstack.h
1156 @comment GNU
1157 @deftypefun void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
1158 To add a block of initialized space, use @code{obstack_grow}, which is
1159 the growing-object analogue of @code{obstack_copy}.  It adds @var{size}
1160 bytes of data to the growing object, copying the contents from
1161 @var{data}.
1162 @end deftypefun
1163
1164 @comment obstack.h
1165 @comment GNU
1166 @deftypefun void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
1167 This is the growing-object analogue of @code{obstack_copy0}.  It adds
1168 @var{size} bytes copied from @var{data}, followed by an additional null
1169 character.
1170 @end deftypefun
1171
1172 @comment obstack.h
1173 @comment GNU
1174 @deftypefun void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{c})
1175 To add one character at a time, use the function @code{obstack_1grow}.
1176 It adds a single byte containing @var{c} to the growing object.
1177 @end deftypefun
1178
1179 @comment obstack.h
1180 @comment GNU
1181 @deftypefun void obstack_ptr_grow (struct obstack *@var{obstack-ptr}, void *@var{data})
1182 Adding the value of a pointer one can use the function
1183 @code{obstack_ptr_grow}.  It adds @code{sizeof (void *)} bytes
1184 containing the value of @var{data}.
1185 @end deftypefun
1186
1187 @comment obstack.h
1188 @comment GNU
1189 @deftypefun void obstack_int_grow (struct obstack *@var{obstack-ptr}, int @var{data})
1190 A single value of type @code{int} can be added by using the
1191 @code{obstack_int_grow} function.  It adds @code{sizeof (int)} bytes to
1192 the growing object and initializes them with the value of @var{data}.
1193 @end deftypefun
1194
1195 @comment obstack.h
1196 @comment GNU
1197 @deftypefun {void *} obstack_finish (struct obstack *@var{obstack-ptr})
1198 When you are finished growing the object, use the function
1199 @code{obstack_finish} to close it off and return its final address.
1200
1201 Once you have finished the object, the obstack is available for ordinary
1202 allocation or for growing another object.
1203
1204 This function can return a null pointer under the same conditions as
1205 @code{obstack_alloc} (@pxref{Allocation in an Obstack}).
1206 @end deftypefun
1207
1208 When you build an object by growing it, you will probably need to know
1209 afterward how long it became.  You need not keep track of this as you grow
1210 the object, because you can find out the length from the obstack just
1211 before finishing the object with the function @code{obstack_object_size},
1212 declared as follows:
1213
1214 @comment obstack.h
1215 @comment GNU
1216 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1217 This function returns the current size of the growing object, in bytes.
1218 Remember to call this function @emph{before} finishing the object.
1219 After it is finished, @code{obstack_object_size} will return zero.
1220 @end deftypefun
1221
1222 If you have started growing an object and wish to cancel it, you should
1223 finish it and then free it, like this:
1224
1225 @smallexample
1226 obstack_free (obstack_ptr, obstack_finish (obstack_ptr));
1227 @end smallexample
1228
1229 @noindent
1230 This has no effect if no object was growing.
1231
1232 @cindex shrinking objects
1233 You can use @code{obstack_blank} with a negative size argument to make
1234 the current object smaller.  Just don't try to shrink it beyond zero
1235 length---there's no telling what will happen if you do that.
1236
1237 @node Extra Fast Growing
1238 @subsection Extra Fast Growing Objects
1239 @cindex efficiency and obstacks
1240
1241 The usual functions for growing objects incur overhead for checking
1242 whether there is room for the new growth in the current chunk.  If you
1243 are frequently constructing objects in small steps of growth, this
1244 overhead can be significant.
1245
1246 You can reduce the overhead by using special ``fast growth''
1247 functions that grow the object without checking.  In order to have a
1248 robust program, you must do the checking yourself.  If you do this checking
1249 in the simplest way each time you are about to add data to the object, you
1250 have not saved anything, because that is what the ordinary growth
1251 functions do.  But if you can arrange to check less often, or check
1252 more efficiently, then you make the program faster.
1253
1254 The function @code{obstack_room} returns the amount of room available
1255 in the current chunk.  It is declared as follows:
1256
1257 @comment obstack.h
1258 @comment GNU
1259 @deftypefun int obstack_room (struct obstack *@var{obstack-ptr})
1260 This returns the number of bytes that can be added safely to the current
1261 growing object (or to an object about to be started) in obstack
1262 @var{obstack} using the fast growth functions.
1263 @end deftypefun
1264
1265 While you know there is room, you can use these fast growth functions
1266 for adding data to a growing object:
1267
1268 @comment obstack.h
1269 @comment GNU
1270 @deftypefun void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{c})
1271 The function @code{obstack_1grow_fast} adds one byte containing the
1272 character @var{c} to the growing object in obstack @var{obstack-ptr}.
1273 @end deftypefun
1274
1275 @comment obstack.h
1276 @comment GNU
1277 @deftypefun void obstack_ptr_grow_fast (struct obstack *@var{obstack-ptr}, void *@var{data})
1278 The function @code{obstack_ptr_grow_fast} adds @code{sizeof (void *)}
1279 bytes containing the value of @var{data} to the growing object in
1280 obstack @var{obstack-ptr}.
1281 @end deftypefun
1282
1283 @comment obstack.h
1284 @comment GNU
1285 @deftypefun void obstack_int_grow_fast (struct obstack *@var{obstack-ptr}, int @var{data})
1286 The function @code{obstack_int_grow_fast} adds @code{sizeof (int)} bytes
1287 containing the value of @var{data} to the growing object in obstack
1288 @var{obstack-ptr}.
1289 @end deftypefun
1290
1291 @comment obstack.h
1292 @comment GNU
1293 @deftypefun void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1294 The function @code{obstack_blank_fast} adds @var{size} bytes to the
1295 growing object in obstack @var{obstack-ptr} without initializing them.
1296 @end deftypefun
1297
1298 When you check for space using @code{obstack_room} and there is not
1299 enough room for what you want to add, the fast growth functions
1300 are not safe.  In this case, simply use the corresponding ordinary
1301 growth function instead.  Very soon this will copy the object to a
1302 new chunk; then there will be lots of room available again.
1303
1304 So, each time you use an ordinary growth function, check afterward for
1305 sufficient space using @code{obstack_room}.  Once the object is copied
1306 to a new chunk, there will be plenty of space again, so the program will
1307 start using the fast growth functions again.
1308
1309 Here is an example:
1310
1311 @smallexample
1312 @group
1313 void
1314 add_string (struct obstack *obstack, const char *ptr, int len)
1315 @{
1316   while (len > 0)
1317     @{
1318       int room = obstack_room (obstack);
1319       if (room == 0)
1320         @{
1321           /* @r{Not enough room. Add one character slowly,}
1322              @r{which may copy to a new chunk and make room.}  */
1323           obstack_1grow (obstack, *ptr++);
1324           len--;
1325         @}
1326       else
1327         @{
1328           if (room > len)
1329             room = len;
1330           /* @r{Add fast as much as we have room for.} */
1331           len -= room;
1332           while (room-- > 0)
1333             obstack_1grow_fast (obstack, *ptr++);
1334         @}
1335     @}
1336 @}
1337 @end group
1338 @end smallexample
1339
1340 @node Status of an Obstack
1341 @subsection Status of an Obstack
1342 @cindex obstack status
1343 @cindex status of obstack
1344
1345 Here are functions that provide information on the current status of
1346 allocation in an obstack.  You can use them to learn about an object while
1347 still growing it.
1348
1349 @comment obstack.h
1350 @comment GNU
1351 @deftypefun {void *} obstack_base (struct obstack *@var{obstack-ptr})
1352 This function returns the tentative address of the beginning of the
1353 currently growing object in @var{obstack-ptr}.  If you finish the object
1354 immediately, it will have that address.  If you make it larger first, it
1355 may outgrow the current chunk---then its address will change!
1356
1357 If no object is growing, this value says where the next object you
1358 allocate will start (once again assuming it fits in the current
1359 chunk).
1360 @end deftypefun
1361
1362 @comment obstack.h
1363 @comment GNU
1364 @deftypefun {void *} obstack_next_free (struct obstack *@var{obstack-ptr})
1365 This function returns the address of the first free byte in the current
1366 chunk of obstack @var{obstack-ptr}.  This is the end of the currently
1367 growing object.  If no object is growing, @code{obstack_next_free}
1368 returns the same value as @code{obstack_base}.
1369 @end deftypefun
1370
1371 @comment obstack.h
1372 @comment GNU
1373 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1374 This function returns the size in bytes of the currently growing object.
1375 This is equivalent to
1376
1377 @smallexample
1378 obstack_next_free (@var{obstack-ptr}) - obstack_base (@var{obstack-ptr})
1379 @end smallexample
1380 @end deftypefun
1381
1382 @node Obstacks Data Alignment
1383 @subsection Alignment of Data in Obstacks
1384 @cindex alignment (in obstacks)
1385
1386 Each obstack has an @dfn{alignment boundary}; each object allocated in
1387 the obstack automatically starts on an address that is a multiple of the
1388 specified boundary.  By default, this boundary is 4 bytes.
1389
1390 To access an obstack's alignment boundary, use the macro
1391 @code{obstack_alignment_mask}, whose function prototype looks like
1392 this:
1393
1394 @comment obstack.h
1395 @comment GNU
1396 @deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
1397 The value is a bit mask; a bit that is 1 indicates that the corresponding
1398 bit in the address of an object should be 0.  The mask value should be one
1399 less than a power of 2; the effect is that all object addresses are
1400 multiples of that power of 2.  The default value of the mask is 3, so that
1401 addresses are multiples of 4.  A mask value of 0 means an object can start
1402 on any multiple of 1 (that is, no alignment is required).
1403
1404 The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
1405 so you can alter the mask by assignment.  For example, this statement:
1406
1407 @smallexample
1408 obstack_alignment_mask (obstack_ptr) = 0;
1409 @end smallexample
1410
1411 @noindent
1412 has the effect of turning off alignment processing in the specified obstack.
1413 @end deftypefn
1414
1415 Note that a change in alignment mask does not take effect until
1416 @emph{after} the next time an object is allocated or finished in the
1417 obstack.  If you are not growing an object, you can make the new
1418 alignment mask take effect immediately by calling @code{obstack_finish}.
1419 This will finish a zero-length object and then do proper alignment for
1420 the next object.
1421
1422 @node Obstack Chunks
1423 @subsection Obstack Chunks
1424 @cindex efficiency of chunks
1425 @cindex chunks
1426
1427 Obstacks work by allocating space for themselves in large chunks, and
1428 then parceling out space in the chunks to satisfy your requests.  Chunks
1429 are normally 4096 bytes long unless you specify a different chunk size.
1430 The chunk size includes 8 bytes of overhead that are not actually used
1431 for storing objects.  Regardless of the specified size, longer chunks
1432 will be allocated when necessary for long objects.
1433
1434 The obstack library allocates chunks by calling the function
1435 @code{obstack_chunk_alloc}, which you must define.  When a chunk is no
1436 longer needed because you have freed all the objects in it, the obstack
1437 library frees the chunk by calling @code{obstack_chunk_free}, which you
1438 must also define.
1439
1440 These two must be defined (as macros) or declared (as functions) in each
1441 source file that uses @code{obstack_init} (@pxref{Creating Obstacks}).
1442 Most often they are defined as macros like this:
1443
1444 @smallexample
1445 #define obstack_chunk_alloc xmalloc
1446 #define obstack_chunk_free free
1447 @end smallexample
1448
1449 Note that these are simple macros (no arguments).  Macro definitions with
1450 arguments will not work!  It is necessary that @code{obstack_chunk_alloc}
1451 or @code{obstack_chunk_free}, alone, expand into a function name if it is
1452 not itself a function name.
1453
1454 If you allocate chunks with @code{malloc}, the chunk size should be a
1455 power of 2.  The default chunk size, 4096, was chosen because it is long
1456 enough to satisfy many typical requests on the obstack yet short enough
1457 not to waste too much memory in the portion of the last chunk not yet used.
1458
1459 @comment obstack.h
1460 @comment GNU
1461 @deftypefn Macro int obstack_chunk_size (struct obstack *@var{obstack-ptr})
1462 This returns the chunk size of the given obstack.
1463 @end deftypefn
1464
1465 Since this macro expands to an lvalue, you can specify a new chunk size by
1466 assigning it a new value.  Doing so does not affect the chunks already
1467 allocated, but will change the size of chunks allocated for that particular
1468 obstack in the future.  It is unlikely to be useful to make the chunk size
1469 smaller, but making it larger might improve efficiency if you are
1470 allocating many objects whose size is comparable to the chunk size.  Here
1471 is how to do so cleanly:
1472
1473 @smallexample
1474 if (obstack_chunk_size (obstack_ptr) < @var{new-chunk-size})
1475   obstack_chunk_size (obstack_ptr) = @var{new-chunk-size};
1476 @end smallexample
1477
1478 @node Summary of Obstacks
1479 @subsection Summary of Obstack Functions
1480
1481 Here is a summary of all the functions associated with obstacks.  Each
1482 takes the address of an obstack (@code{struct obstack *}) as its first
1483 argument.
1484
1485 @table @code
1486 @item void obstack_init (struct obstack *@var{obstack-ptr})
1487 Initialize use of an obstack.  @xref{Creating Obstacks}.
1488
1489 @item void *obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
1490 Allocate an object of @var{size} uninitialized bytes.
1491 @xref{Allocation in an Obstack}.
1492
1493 @item void *obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1494 Allocate an object of @var{size} bytes, with contents copied from
1495 @var{address}.  @xref{Allocation in an Obstack}.
1496
1497 @item void *obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1498 Allocate an object of @var{size}+1 bytes, with @var{size} of them copied
1499 from @var{address}, followed by a null character at the end.
1500 @xref{Allocation in an Obstack}.
1501
1502 @item void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
1503 Free @var{object} (and everything allocated in the specified obstack
1504 more recently than @var{object}).  @xref{Freeing Obstack Objects}.
1505
1506 @item void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
1507 Add @var{size} uninitialized bytes to a growing object.
1508 @xref{Growing Objects}.
1509
1510 @item void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1511 Add @var{size} bytes, copied from @var{address}, to a growing object.
1512 @xref{Growing Objects}.
1513
1514 @item void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1515 Add @var{size} bytes, copied from @var{address}, to a growing object,
1516 and then add another byte containing a null character.  @xref{Growing
1517 Objects}.
1518
1519 @item void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{data-char})
1520 Add one byte containing @var{data-char} to a growing object.
1521 @xref{Growing Objects}.
1522
1523 @item void *obstack_finish (struct obstack *@var{obstack-ptr})
1524 Finalize the object that is growing and return its permanent address.
1525 @xref{Growing Objects}.
1526
1527 @item int obstack_object_size (struct obstack *@var{obstack-ptr})
1528 Get the current size of the currently growing object.  @xref{Growing
1529 Objects}.
1530
1531 @item void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1532 Add @var{size} uninitialized bytes to a growing object without checking
1533 that there is enough room.  @xref{Extra Fast Growing}.
1534
1535 @item void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{data-char})
1536 Add one byte containing @var{data-char} to a growing object without
1537 checking that there is enough room.  @xref{Extra Fast Growing}.
1538
1539 @item int obstack_room (struct obstack *@var{obstack-ptr})
1540 Get the amount of room now available for growing the current object.
1541 @xref{Extra Fast Growing}.
1542
1543 @item int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
1544 The mask used for aligning the beginning of an object.  This is an
1545 lvalue.  @xref{Obstacks Data Alignment}.
1546
1547 @item int obstack_chunk_size (struct obstack *@var{obstack-ptr})
1548 The size for allocating chunks.  This is an lvalue.  @xref{Obstack Chunks}.
1549
1550 @item void *obstack_base (struct obstack *@var{obstack-ptr})
1551 Tentative starting address of the currently growing object.
1552 @xref{Status of an Obstack}.
1553
1554 @item void *obstack_next_free (struct obstack *@var{obstack-ptr})
1555 Address just after the end of the currently growing object.
1556 @xref{Status of an Obstack}.
1557 @end table
1558
1559 @node Variable Size Automatic
1560 @section Automatic Storage with Variable Size
1561 @cindex automatic freeing
1562 @cindex @code{alloca} function
1563 @cindex automatic storage with variable size
1564
1565 The function @code{alloca} supports a kind of half-dynamic allocation in
1566 which blocks are allocated dynamically but freed automatically.
1567
1568 Allocating a block with @code{alloca} is an explicit action; you can
1569 allocate as many blocks as you wish, and compute the size at run time.  But
1570 all the blocks are freed when you exit the function that @code{alloca} was
1571 called from, just as if they were automatic variables declared in that
1572 function.  There is no way to free the space explicitly.
1573
1574 The prototype for @code{alloca} is in @file{stdlib.h}.  This function is
1575 a BSD extension.
1576 @pindex stdlib.h
1577
1578 @comment stdlib.h
1579 @comment GNU, BSD
1580 @deftypefun {void *} alloca (size_t @var{size});
1581 The return value of @code{alloca} is the address of a block of @var{size}
1582 bytes of storage, allocated in the stack frame of the calling function.
1583 @end deftypefun
1584
1585 Do not use @code{alloca} inside the arguments of a function call---you
1586 will get unpredictable results, because the stack space for the
1587 @code{alloca} would appear on the stack in the middle of the space for
1588 the function arguments.  An example of what to avoid is @code{foo (x,
1589 alloca (4), y)}.
1590 @c This might get fixed in future versions of GCC, but that won't make
1591 @c it safe with compilers generally.
1592
1593 @menu
1594 * Alloca Example::              Example of using @code{alloca}.
1595 * Advantages of Alloca::        Reasons to use @code{alloca}.
1596 * Disadvantages of Alloca::     Reasons to avoid @code{alloca}.
1597 * GNU C Variable-Size Arrays::  Only in GNU C, here is an alternative
1598                                  method of allocating dynamically and
1599                                  freeing automatically.
1600 @end menu
1601
1602 @node Alloca Example
1603 @subsection @code{alloca} Example
1604
1605 As an example of use of @code{alloca}, here is a function that opens a file
1606 name made from concatenating two argument strings, and returns a file
1607 descriptor or minus one signifying failure:
1608
1609 @smallexample
1610 int
1611 open2 (char *str1, char *str2, int flags, int mode)
1612 @{
1613   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1614   stpcpy (stpcpy (name, str1), str2);
1615   return open (name, flags, mode);
1616 @}
1617 @end smallexample
1618
1619 @noindent
1620 Here is how you would get the same results with @code{malloc} and
1621 @code{free}:
1622
1623 @smallexample
1624 int
1625 open2 (char *str1, char *str2, int flags, int mode)
1626 @{
1627   char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
1628   int desc;
1629   if (name == 0)
1630     fatal ("virtual memory exceeded");
1631   stpcpy (stpcpy (name, str1), str2);
1632   desc = open (name, flags, mode);
1633   free (name);
1634   return desc;
1635 @}
1636 @end smallexample
1637
1638 As you can see, it is simpler with @code{alloca}.  But @code{alloca} has
1639 other, more important advantages, and some disadvantages.
1640
1641 @node Advantages of Alloca
1642 @subsection Advantages of @code{alloca}
1643
1644 Here are the reasons why @code{alloca} may be preferable to @code{malloc}:
1645
1646 @itemize @bullet
1647 @item
1648 Using @code{alloca} wastes very little space and is very fast.  (It is
1649 open-coded by the GNU C compiler.)
1650
1651 @item
1652 Since @code{alloca} does not have separate pools for different sizes of
1653 block, space used for any size block can be reused for any other size.
1654 @code{alloca} does not cause storage fragmentation.
1655
1656 @item
1657 @cindex longjmp
1658 Nonlocal exits done with @code{longjmp} (@pxref{Non-Local Exits})
1659 automatically free the space allocated with @code{alloca} when they exit
1660 through the function that called @code{alloca}.  This is the most
1661 important reason to use @code{alloca}.
1662
1663 To illustrate this, suppose you have a function
1664 @code{open_or_report_error} which returns a descriptor, like
1665 @code{open}, if it succeeds, but does not return to its caller if it
1666 fails.  If the file cannot be opened, it prints an error message and
1667 jumps out to the command level of your program using @code{longjmp}.
1668 Let's change @code{open2} (@pxref{Alloca Example}) to use this
1669 subroutine:@refill
1670
1671 @smallexample
1672 int
1673 open2 (char *str1, char *str2, int flags, int mode)
1674 @{
1675   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1676   stpcpy (stpcpy (name, str1), str2);
1677   return open_or_report_error (name, flags, mode);
1678 @}
1679 @end smallexample
1680
1681 @noindent
1682 Because of the way @code{alloca} works, the storage it allocates is
1683 freed even when an error occurs, with no special effort required.
1684
1685 By contrast, the previous definition of @code{open2} (which uses
1686 @code{malloc} and @code{free}) would develop a storage leak if it were
1687 changed in this way.  Even if you are willing to make more changes to
1688 fix it, there is no easy way to do so.
1689 @end itemize
1690
1691 @node Disadvantages of Alloca
1692 @subsection Disadvantages of @code{alloca}
1693
1694 @cindex @code{alloca} disadvantages
1695 @cindex disadvantages of @code{alloca}
1696 These are the disadvantages of @code{alloca} in comparison with
1697 @code{malloc}:
1698
1699 @itemize @bullet
1700 @item
1701 If you try to allocate more storage than the machine can provide, you
1702 don't get a clean error message.  Instead you get a fatal signal like
1703 the one you would get from an infinite recursion; probably a
1704 segmentation violation (@pxref{Program Error Signals}).
1705
1706 @item
1707 Some non-GNU systems fail to support @code{alloca}, so it is less
1708 portable.  However, a slower emulation of @code{alloca} written in C
1709 is available for use on systems with this deficiency.
1710 @end itemize
1711
1712 @node GNU C Variable-Size Arrays
1713 @subsection GNU C Variable-Size Arrays
1714 @cindex variable-sized arrays
1715
1716 In GNU C, you can replace most uses of @code{alloca} with an array of
1717 variable size.  Here is how @code{open2} would look then:
1718
1719 @smallexample
1720 int open2 (char *str1, char *str2, int flags, int mode)
1721 @{
1722   char name[strlen (str1) + strlen (str2) + 1];
1723   stpcpy (stpcpy (name, str1), str2);
1724   return open (name, flags, mode);
1725 @}
1726 @end smallexample
1727
1728 But @code{alloca} is not always equivalent to a variable-sized array, for
1729 several reasons:
1730
1731 @itemize @bullet
1732 @item
1733 A variable size array's space is freed at the end of the scope of the
1734 name of the array.  The space allocated with @code{alloca}
1735 remains until the end of the function.
1736
1737 @item
1738 It is possible to use @code{alloca} within a loop, allocating an
1739 additional block on each iteration.  This is impossible with
1740 variable-sized arrays.
1741 @end itemize
1742
1743 @strong{Note:} If you mix use of @code{alloca} and variable-sized arrays
1744 within one function, exiting a scope in which a variable-sized array was
1745 declared frees all blocks allocated with @code{alloca} during the
1746 execution of that scope.
1747
1748
1749 @node Relocating Allocator
1750 @section Relocating Allocator
1751
1752 @cindex relocating memory allocator
1753 Any system of dynamic memory allocation has overhead: the amount of
1754 space it uses is more than the amount the program asks for.  The
1755 @dfn{relocating memory allocator} achieves very low overhead by moving
1756 blocks in memory as necessary, on its own initiative.
1757
1758 @menu
1759 * Relocator Concepts::          How to understand relocating allocation.
1760 * Using Relocator::             Functions for relocating allocation.
1761 @end menu
1762
1763 @node Relocator Concepts
1764 @subsection Concepts of Relocating Allocation
1765
1766 @ifinfo
1767 The @dfn{relocating memory allocator} achieves very low overhead by
1768 moving blocks in memory as necessary, on its own initiative.
1769 @end ifinfo
1770
1771 When you allocate a block with @code{malloc}, the address of the block
1772 never changes unless you use @code{realloc} to change its size.  Thus,
1773 you can safely store the address in various places, temporarily or
1774 permanently, as you like.  This is not safe when you use the relocating
1775 memory allocator, because any and all relocatable blocks can move
1776 whenever you allocate memory in any fashion.  Even calling @code{malloc}
1777 or @code{realloc} can move the relocatable blocks.
1778
1779 @cindex handle
1780 For each relocatable block, you must make a @dfn{handle}---a pointer
1781 object in memory, designated to store the address of that block.  The
1782 relocating allocator knows where each block's handle is, and updates the
1783 address stored there whenever it moves the block, so that the handle
1784 always points to the block.  Each time you access the contents of the
1785 block, you should fetch its address anew from the handle.
1786
1787 To call any of the relocating allocator functions from a signal handler
1788 is almost certainly incorrect, because the signal could happen at any
1789 time and relocate all the blocks.  The only way to make this safe is to
1790 block the signal around any access to the contents of any relocatable
1791 block---not a convenient mode of operation.  @xref{Nonreentrancy}.
1792
1793 @node Using Relocator
1794 @subsection Allocating and Freeing Relocatable Blocks
1795
1796 @pindex malloc.h
1797 In the descriptions below, @var{handleptr} designates the address of the
1798 handle.  All the functions are declared in @file{malloc.h}; all are GNU
1799 extensions.
1800
1801 @comment malloc.h
1802 @comment GNU
1803 @deftypefun {void *} r_alloc (void **@var{handleptr}, size_t @var{size})
1804 This function allocates a relocatable block of size @var{size}.  It
1805 stores the block's address in @code{*@var{handleptr}} and returns
1806 a non-null pointer to indicate success.
1807
1808 If @code{r_alloc} can't get the space needed, it stores a null pointer
1809 in @code{*@var{handleptr}}, and returns a null pointer.
1810 @end deftypefun
1811
1812 @comment malloc.h
1813 @comment GNU
1814 @deftypefun void r_alloc_free (void **@var{handleptr})
1815 This function is the way to free a relocatable block.  It frees the
1816 block that @code{*@var{handleptr}} points to, and stores a null pointer
1817 in @code{*@var{handleptr}} to show it doesn't point to an allocated
1818 block any more.
1819 @end deftypefun
1820
1821 @comment malloc.h
1822 @comment GNU
1823 @deftypefun {void *} r_re_alloc (void **@var{handleptr}, size_t @var{size})
1824 The function @code{r_re_alloc} adjusts the size of the block that
1825 @code{*@var{handleptr}} points to, making it @var{size} bytes long.  It
1826 stores the address of the resized block in @code{*@var{handleptr}} and
1827 returns a non-null pointer to indicate success.
1828
1829 If enough memory is not available, this function returns a null pointer
1830 and does not modify @code{*@var{handleptr}}.
1831 @end deftypefun
1832
1833 @ignore
1834 @comment No longer available...
1835
1836 @comment @node Memory Warnings
1837 @comment @section Memory Usage Warnings
1838 @comment @cindex memory usage warnings
1839 @comment @cindex warnings of memory almost full
1840
1841 @pindex malloc.c
1842 You can ask for warnings as the program approaches running out of memory
1843 space, by calling @code{memory_warnings}.  This tells @code{malloc} to
1844 check memory usage every time it asks for more memory from the operating
1845 system.  This is a GNU extension declared in @file{malloc.h}.
1846
1847 @comment malloc.h
1848 @comment GNU
1849 @comment @deftypefun void memory_warnings (void *@var{start}, void (*@var{warn-func}) (const char *))
1850 Call this function to request warnings for nearing exhaustion of virtual
1851 memory.
1852
1853 The argument @var{start} says where data space begins, in memory.  The
1854 allocator compares this against the last address used and against the
1855 limit of data space, to determine the fraction of available memory in
1856 use.  If you supply zero for @var{start}, then a default value is used
1857 which is right in most circumstances.
1858
1859 For @var{warn-func}, supply a function that @code{malloc} can call to
1860 warn you.  It is called with a string (a warning message) as argument.
1861 Normally it ought to display the string for the user to read.
1862 @end deftypefun
1863
1864 The warnings come when memory becomes 75% full, when it becomes 85%
1865 full, and when it becomes 95% full.  Above 95% you get another warning
1866 each time memory usage increases.
1867
1868 @end ignore