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