(_hurd_sig_post): __sig_post renamed to __msg_sig_post.
[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 ANSI
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 ANSI 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 ANSI
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 ANSI
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 ANSI 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 ANSI
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{size}, size_t @var{boundary})
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 (size, getpagesize ());
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 ANSI 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 non-ANSI 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 ANSI 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 ANSI 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 ANSI
1032 C.
1033
1034 If you use the GNU C compiler, this precaution is not necessary, because
1035 various language extensions in GNU C permit defining the macros so as to
1036 compute each argument only once.
1037
1038 @node Growing Objects
1039 @subsection Growing Objects
1040 @cindex growing objects (in obstacks)
1041 @cindex changing the size of a block (obstacks)
1042
1043 Because storage in obstack chunks is used sequentially, it is possible to
1044 build up an object step by step, adding one or more bytes at a time to the
1045 end of the object.  With this technique, you do not need to know how much
1046 data you will put in the object until you come to the end of it.  We call
1047 this the technique of @dfn{growing objects}.  The special functions
1048 for adding data to the growing object are described in this section.
1049
1050 You don't need to do anything special when you start to grow an object.
1051 Using one of the functions to add data to the object automatically
1052 starts it.  However, it is necessary to say explicitly when the object is
1053 finished.  This is done with the function @code{obstack_finish}.
1054
1055 The actual address of the object thus built up is not known until the
1056 object is finished.  Until then, it always remains possible that you will
1057 add so much data that the object must be copied into a new chunk.
1058
1059 While the obstack is in use for a growing object, you cannot use it for
1060 ordinary allocation of another object.  If you try to do so, the space
1061 already added to the growing object will become part of the other object.
1062
1063 @comment obstack.h
1064 @comment GNU
1065 @deftypefun void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
1066 The most basic function for adding to a growing object is
1067 @code{obstack_blank}, which adds space without initializing it.
1068 @end deftypefun
1069
1070 @comment obstack.h
1071 @comment GNU
1072 @deftypefun void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
1073 To add a block of initialized space, use @code{obstack_grow}, which is
1074 the growing-object analogue of @code{obstack_copy}.  It adds @var{size}
1075 bytes of data to the growing object, copying the contents from
1076 @var{data}.
1077 @end deftypefun
1078
1079 @comment obstack.h
1080 @comment GNU
1081 @deftypefun void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
1082 This is the growing-object analogue of @code{obstack_copy0}.  It adds
1083 @var{size} bytes copied from @var{data}, followed by an additional null
1084 character.
1085 @end deftypefun
1086
1087 @comment obstack.h
1088 @comment GNU
1089 @deftypefun void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{c})
1090 To add one character at a time, use the function @code{obstack_1grow}.
1091 It adds a single byte containing @var{c} to the growing object.
1092 @end deftypefun
1093
1094 @comment obstack.h
1095 @comment GNU
1096 @deftypefun {void *} obstack_finish (struct obstack *@var{obstack-ptr})
1097 When you are finished growing the object, use the function
1098 @code{obstack_finish} to close it off and return its final address.
1099
1100 Once you have finished the object, the obstack is available for ordinary
1101 allocation or for growing another object.
1102
1103 This function can return a null pointer under the same conditions as
1104 @code{obstack_alloc} (@pxref{Allocation in an Obstack}).
1105 @end deftypefun
1106
1107 When you build an object by growing it, you will probably need to know
1108 afterward how long it became.  You need not keep track of this as you grow
1109 the object, because you can find out the length from the obstack just
1110 before finishing the object with the function @code{obstack_object_size},
1111 declared as follows:
1112
1113 @comment obstack.h
1114 @comment GNU
1115 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1116 This function returns the current size of the growing object, in bytes.
1117 Remember to call this function @emph{before} finishing the object.
1118 After it is finished, @code{obstack_object_size} will return zero.
1119 @end deftypefun
1120
1121 If you have started growing an object and wish to cancel it, you should
1122 finish it and then free it, like this:
1123
1124 @smallexample
1125 obstack_free (obstack_ptr, obstack_finish (obstack_ptr));
1126 @end smallexample
1127
1128 @noindent
1129 This has no effect if no object was growing.
1130
1131 @cindex shrinking objects
1132 You can use @code{obstack_blank} with a negative size argument to make
1133 the current object smaller.  Just don't try to shrink it beyond zero
1134 length---there's no telling what will happen if you do that.
1135
1136 @node Extra Fast Growing
1137 @subsection Extra Fast Growing Objects
1138 @cindex efficiency and obstacks
1139
1140 The usual functions for growing objects incur overhead for checking
1141 whether there is room for the new growth in the current chunk.  If you
1142 are frequently constructing objects in small steps of growth, this
1143 overhead can be significant.
1144
1145 You can reduce the overhead by using special ``fast growth''
1146 functions that grow the object without checking.  In order to have a
1147 robust program, you must do the checking yourself.  If you do this checking
1148 in the simplest way each time you are about to add data to the object, you
1149 have not saved anything, because that is what the ordinary growth
1150 functions do.  But if you can arrange to check less often, or check
1151 more efficiently, then you make the program faster.
1152
1153 The function @code{obstack_room} returns the amount of room available
1154 in the current chunk.  It is declared as follows:
1155
1156 @comment obstack.h
1157 @comment GNU
1158 @deftypefun int obstack_room (struct obstack *@var{obstack-ptr})
1159 This returns the number of bytes that can be added safely to the current
1160 growing object (or to an object about to be started) in obstack
1161 @var{obstack} using the fast growth functions.
1162 @end deftypefun
1163
1164 While you know there is room, you can use these fast growth functions
1165 for adding data to a growing object:
1166
1167 @comment obstack.h
1168 @comment GNU
1169 @deftypefun void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{c})
1170 The function @code{obstack_1grow_fast} adds one byte containing the
1171 character @var{c} to the growing object in obstack @var{obstack-ptr}.
1172 @end deftypefun
1173
1174 @comment obstack.h
1175 @comment GNU
1176 @deftypefun void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1177 The function @code{obstack_blank_fast} adds @var{size} bytes to the
1178 growing object in obstack @var{obstack-ptr} without initializing them.
1179 @end deftypefun
1180
1181 When you check for space using @code{obstack_room} and there is not
1182 enough room for what you want to add, the fast growth functions
1183 are not safe.  In this case, simply use the corresponding ordinary
1184 growth function instead.  Very soon this will copy the object to a
1185 new chunk; then there will be lots of room available again. 
1186
1187 So, each time you use an ordinary growth function, check afterward for
1188 sufficient space using @code{obstack_room}.  Once the object is copied
1189 to a new chunk, there will be plenty of space again, so the program will
1190 start using the fast growth functions again.
1191
1192 Here is an example:
1193
1194 @smallexample
1195 @group
1196 void
1197 add_string (struct obstack *obstack, const char *ptr, int len)
1198 @{
1199   while (len > 0)
1200     @{
1201       int room = obstack_room (obstack);
1202       if (room == 0)
1203         @{
1204           /* @r{Not enough room. Add one character slowly,}
1205              @r{which may copy to a new chunk and make room.}  */
1206           obstack_1grow (obstack, *ptr++);
1207           len--;
1208         @}
1209       else 
1210         @{
1211           if (room > len)
1212             room = len;
1213           /* @r{Add fast as much as we have room for.} */
1214           len -= room;
1215           while (room-- > 0)
1216             obstack_1grow_fast (obstack, *ptr++);
1217         @}
1218     @}
1219 @}
1220 @end group
1221 @end smallexample
1222
1223 @node Status of an Obstack
1224 @subsection Status of an Obstack
1225 @cindex obstack status
1226 @cindex status of obstack
1227
1228 Here are functions that provide information on the current status of
1229 allocation in an obstack.  You can use them to learn about an object while
1230 still growing it.
1231
1232 @comment obstack.h
1233 @comment GNU
1234 @deftypefun {void *} obstack_base (struct obstack *@var{obstack-ptr})
1235 This function returns the tentative address of the beginning of the
1236 currently growing object in @var{obstack-ptr}.  If you finish the object
1237 immediately, it will have that address.  If you make it larger first, it
1238 may outgrow the current chunk---then its address will change!
1239
1240 If no object is growing, this value says where the next object you
1241 allocate will start (once again assuming it fits in the current
1242 chunk).
1243 @end deftypefun
1244
1245 @comment obstack.h
1246 @comment GNU
1247 @deftypefun {void *} obstack_next_free (struct obstack *@var{obstack-ptr})
1248 This function returns the address of the first free byte in the current
1249 chunk of obstack @var{obstack-ptr}.  This is the end of the currently
1250 growing object.  If no object is growing, @code{obstack_next_free}
1251 returns the same value as @code{obstack_base}.
1252 @end deftypefun
1253
1254 @comment obstack.h
1255 @comment GNU
1256 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1257 This function returns the size in bytes of the currently growing object.
1258 This is equivalent to
1259
1260 @smallexample
1261 obstack_next_free (@var{obstack-ptr}) - obstack_base (@var{obstack-ptr})
1262 @end smallexample
1263 @end deftypefun
1264
1265 @node Obstacks Data Alignment
1266 @subsection Alignment of Data in Obstacks
1267 @cindex alignment (in obstacks)
1268
1269 Each obstack has an @dfn{alignment boundary}; each object allocated in
1270 the obstack automatically starts on an address that is a multiple of the
1271 specified boundary.  By default, this boundary is 4 bytes.
1272
1273 To access an obstack's alignment boundary, use the macro
1274 @code{obstack_alignment_mask}, whose function prototype looks like
1275 this:
1276
1277 @comment obstack.h
1278 @comment GNU
1279 @deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
1280 The value is a bit mask; a bit that is 1 indicates that the corresponding
1281 bit in the address of an object should be 0.  The mask value should be one
1282 less than a power of 2; the effect is that all object addresses are
1283 multiples of that power of 2.  The default value of the mask is 3, so that
1284 addresses are multiples of 4.  A mask value of 0 means an object can start
1285 on any multiple of 1 (that is, no alignment is required).
1286
1287 The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
1288 so you can alter the mask by assignment.  For example, this statement:
1289
1290 @smallexample
1291 obstack_alignment_mask (obstack_ptr) = 0;
1292 @end smallexample
1293
1294 @noindent
1295 has the effect of turning off alignment processing in the specified obstack.
1296 @end deftypefn
1297
1298 Note that a change in alignment mask does not take effect until
1299 @emph{after} the next time an object is allocated or finished in the
1300 obstack.  If you are not growing an object, you can make the new
1301 alignment mask take effect immediately by calling @code{obstack_finish}.
1302 This will finish a zero-length object and then do proper alignment for
1303 the next object.
1304
1305 @node Obstack Chunks
1306 @subsection Obstack Chunks
1307 @cindex efficiency of chunks
1308 @cindex chunks
1309
1310 Obstacks work by allocating space for themselves in large chunks, and
1311 then parceling out space in the chunks to satisfy your requests.  Chunks
1312 are normally 4096 bytes long unless you specify a different chunk size.
1313 The chunk size includes 8 bytes of overhead that are not actually used
1314 for storing objects.  Regardless of the specified size, longer chunks
1315 will be allocated when necessary for long objects.
1316
1317 The obstack library allocates chunks by calling the function
1318 @code{obstack_chunk_alloc}, which you must define.  When a chunk is no
1319 longer needed because you have freed all the objects in it, the obstack
1320 library frees the chunk by calling @code{obstack_chunk_free}, which you
1321 must also define.
1322
1323 These two must be defined (as macros) or declared (as functions) in each
1324 source file that uses @code{obstack_init} (@pxref{Creating Obstacks}).
1325 Most often they are defined as macros like this:
1326
1327 @smallexample
1328 #define obstack_chunk_alloc xmalloc
1329 #define obstack_chunk_free free
1330 @end smallexample
1331
1332 Note that these are simple macros (no arguments).  Macro definitions with
1333 arguments will not work!  It is necessary that @code{obstack_chunk_alloc}
1334 or @code{obstack_chunk_free}, alone, expand into a function name if it is
1335 not itself a function name.
1336
1337 If you allocate chunks with @code{malloc}, the chunk size should be a
1338 power of 2.  The default chunk size, 4096, was chosen because it is long
1339 enough to satisfy many typical requests on the obstack yet short enough
1340 not to waste too much memory in the portion of the last chunk not yet used.
1341
1342 @comment obstack.h
1343 @comment GNU
1344 @deftypefn Macro int obstack_chunk_size (struct obstack *@var{obstack-ptr})
1345 This returns the chunk size of the given obstack.
1346 @end deftypefn
1347
1348 Since this macro expands to an lvalue, you can specify a new chunk size by
1349 assigning it a new value.  Doing so does not affect the chunks already
1350 allocated, but will change the size of chunks allocated for that particular
1351 obstack in the future.  It is unlikely to be useful to make the chunk size
1352 smaller, but making it larger might improve efficiency if you are
1353 allocating many objects whose size is comparable to the chunk size.  Here
1354 is how to do so cleanly:
1355
1356 @smallexample
1357 if (obstack_chunk_size (obstack_ptr) < @var{new-chunk-size})
1358   obstack_chunk_size (obstack_ptr) = @var{new-chunk-size};
1359 @end smallexample
1360
1361 @node Summary of Obstacks
1362 @subsection Summary of Obstack Functions
1363
1364 Here is a summary of all the functions associated with obstacks.  Each
1365 takes the address of an obstack (@code{struct obstack *}) as its first
1366 argument.
1367
1368 @table @code
1369 @item void obstack_init (struct obstack *@var{obstack-ptr})
1370 Initialize use of an obstack.  @xref{Creating Obstacks}.
1371
1372 @item void *obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
1373 Allocate an object of @var{size} uninitialized bytes.
1374 @xref{Allocation in an Obstack}.
1375
1376 @item void *obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1377 Allocate an object of @var{size} bytes, with contents copied from
1378 @var{address}.  @xref{Allocation in an Obstack}.
1379
1380 @item void *obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1381 Allocate an object of @var{size}+1 bytes, with @var{size} of them copied
1382 from @var{address}, followed by a null character at the end.
1383 @xref{Allocation in an Obstack}.
1384
1385 @item void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
1386 Free @var{object} (and everything allocated in the specified obstack
1387 more recently than @var{object}).  @xref{Freeing Obstack Objects}.
1388
1389 @item void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
1390 Add @var{size} uninitialized bytes to a growing object.
1391 @xref{Growing Objects}.
1392
1393 @item void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1394 Add @var{size} bytes, copied from @var{address}, to a growing object.
1395 @xref{Growing Objects}.
1396
1397 @item void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1398 Add @var{size} bytes, copied from @var{address}, to a growing object,
1399 and then add another byte containing a null character.  @xref{Growing
1400 Objects}.
1401
1402 @item void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{data-char})
1403 Add one byte containing @var{data-char} to a growing object.
1404 @xref{Growing Objects}.
1405
1406 @item void *obstack_finish (struct obstack *@var{obstack-ptr})
1407 Finalize the object that is growing and return its permanent address.
1408 @xref{Growing Objects}.
1409
1410 @item int obstack_object_size (struct obstack *@var{obstack-ptr})
1411 Get the current size of the currently growing object.  @xref{Growing
1412 Objects}.
1413
1414 @item void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1415 Add @var{size} uninitialized bytes to a growing object without checking
1416 that there is enough room.  @xref{Extra Fast Growing}.
1417
1418 @item void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{data-char})
1419 Add one byte containing @var{data-char} to a growing object without
1420 checking that there is enough room.  @xref{Extra Fast Growing}.
1421
1422 @item int obstack_room (struct obstack *@var{obstack-ptr})
1423 Get the amount of room now available for growing the current object.
1424 @xref{Extra Fast Growing}.
1425
1426 @item int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
1427 The mask used for aligning the beginning of an object.  This is an
1428 lvalue.  @xref{Obstacks Data Alignment}.
1429
1430 @item int obstack_chunk_size (struct obstack *@var{obstack-ptr})
1431 The size for allocating chunks.  This is an lvalue.  @xref{Obstack Chunks}.
1432
1433 @item void *obstack_base (struct obstack *@var{obstack-ptr})
1434 Tentative starting address of the currently growing object.
1435 @xref{Status of an Obstack}.
1436
1437 @item void *obstack_next_free (struct obstack *@var{obstack-ptr})
1438 Address just after the end of the currently growing object.
1439 @xref{Status of an Obstack}.
1440 @end table
1441
1442 @node Variable Size Automatic
1443 @section Automatic Storage with Variable Size
1444 @cindex automatic freeing
1445 @cindex @code{alloca} function
1446 @cindex automatic storage with variable size
1447
1448 The function @code{alloca} supports a kind of half-dynamic allocation in
1449 which blocks are allocated dynamically but freed automatically.
1450
1451 Allocating a block with @code{alloca} is an explicit action; you can
1452 allocate as many blocks as you wish, and compute the size at run time.  But
1453 all the blocks are freed when you exit the function that @code{alloca} was
1454 called from, just as if they were automatic variables declared in that
1455 function.  There is no way to free the space explicitly.
1456
1457 The prototype for @code{alloca} is in @file{stdlib.h}.  This function is
1458 a BSD extension.
1459 @pindex stdlib.h
1460
1461 @comment stdlib.h
1462 @comment GNU, BSD
1463 @deftypefun {void *} alloca (size_t @var{size});
1464 The return value of @code{alloca} is the address of a block of @var{size}
1465 bytes of storage, allocated in the stack frame of the calling function.
1466 @end deftypefun
1467
1468 Do not use @code{alloca} inside the arguments of a function call---you
1469 will get unpredictable results, because the stack space for the
1470 @code{alloca} would appear on the stack in the middle of the space for
1471 the function arguments.  An example of what to avoid is @code{foo (x,
1472 alloca (4), y)}.
1473 @c This might get fixed in future versions of GCC, but that won't make
1474 @c it safe with compilers generally.
1475
1476 @menu
1477 * Alloca Example::              Example of using @code{alloca}.
1478 * Advantages of Alloca::        Reasons to use @code{alloca}.
1479 * Disadvantages of Alloca::     Reasons to avoid @code{alloca}.
1480 * GNU C Variable-Size Arrays::  Only in GNU C, here is an alternative
1481                                  method of allocating dynamically and
1482                                  freeing automatically.
1483 @end menu
1484
1485 @node Alloca Example
1486 @subsection @code{alloca} Example
1487
1488 As an example of use of @code{alloca}, here is a function that opens a file
1489 name made from concatenating two argument strings, and returns a file
1490 descriptor or minus one signifying failure:
1491
1492 @smallexample
1493 int
1494 open2 (char *str1, char *str2, int flags, int mode)
1495 @{
1496   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1497   strcpy (name, str1);
1498   strcat (name, str2);
1499   return open (name, flags, mode);
1500 @}
1501 @end smallexample
1502
1503 @noindent
1504 Here is how you would get the same results with @code{malloc} and
1505 @code{free}:
1506
1507 @smallexample
1508 int
1509 open2 (char *str1, char *str2, int flags, int mode)
1510 @{
1511   char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
1512   int desc;
1513   if (name == 0)
1514     fatal ("virtual memory exceeded");
1515   strcpy (name, str1);
1516   strcat (name, str2);
1517   desc = open (name, flags, mode);
1518   free (name);
1519   return desc;
1520 @}
1521 @end smallexample
1522
1523 As you can see, it is simpler with @code{alloca}.  But @code{alloca} has
1524 other, more important advantages, and some disadvantages.
1525
1526 @node Advantages of Alloca
1527 @subsection Advantages of @code{alloca}
1528
1529 Here are the reasons why @code{alloca} may be preferable to @code{malloc}:
1530
1531 @itemize @bullet
1532 @item
1533 Using @code{alloca} wastes very little space and is very fast.  (It is
1534 open-coded by the GNU C compiler.)
1535
1536 @item
1537 Since @code{alloca} does not have separate pools for different sizes of
1538 block, space used for any size block can be reused for any other size.
1539 @code{alloca} does not cause storage fragmentation.
1540
1541 @item
1542 @cindex longjmp
1543 Nonlocal exits done with @code{longjmp} (@pxref{Non-Local Exits})
1544 automatically free the space allocated with @code{alloca} when they exit
1545 through the function that called @code{alloca}.  This is the most
1546 important reason to use @code{alloca}.
1547
1548 To illustrate this, suppose you have a function
1549 @code{open_or_report_error} which returns a descriptor, like
1550 @code{open}, if it succeeds, but does not return to its caller if it
1551 fails.  If the file cannot be opened, it prints an error message and
1552 jumps out to the command level of your program using @code{longjmp}.
1553 Let's change @code{open2} (@pxref{Alloca Example}) to use this
1554 subroutine:@refill
1555
1556 @smallexample
1557 int
1558 open2 (char *str1, char *str2, int flags, int mode)
1559 @{
1560   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1561   strcpy (name, str1);
1562   strcat (name, str2);
1563   return open_or_report_error (name, flags, mode);
1564 @}
1565 @end smallexample
1566
1567 @noindent
1568 Because of the way @code{alloca} works, the storage it allocates is
1569 freed even when an error occurs, with no special effort required.
1570
1571 By contrast, the previous definition of @code{open2} (which uses
1572 @code{malloc} and @code{free}) would develop a storage leak if it were
1573 changed in this way.  Even if you are willing to make more changes to
1574 fix it, there is no easy way to do so.
1575 @end itemize
1576
1577 @node Disadvantages of Alloca
1578 @subsection Disadvantages of @code{alloca}
1579
1580 @cindex @code{alloca} disadvantages
1581 @cindex disadvantages of @code{alloca}
1582 These are the disadvantages of @code{alloca} in comparison with
1583 @code{malloc}:
1584
1585 @itemize @bullet
1586 @item
1587 If you try to allocate more storage than the machine can provide, you
1588 don't get a clean error message.  Instead you get a fatal signal like
1589 the one you would get from an infinite recursion; probably a
1590 segmentation violation (@pxref{Program Error Signals}).
1591
1592 @item
1593 Some non-GNU systems fail to support @code{alloca}, so it is less
1594 portable.  However, a slower emulation of @code{alloca} written in C
1595 is available for use on systems with this deficiency.
1596 @end itemize
1597
1598 @node GNU C Variable-Size Arrays
1599 @subsection GNU C Variable-Size Arrays
1600 @cindex variable-sized arrays
1601
1602 In GNU C, you can replace most uses of @code{alloca} with an array of
1603 variable size.  Here is how @code{open2} would look then:
1604
1605 @smallexample
1606 int open2 (char *str1, char *str2, int flags, int mode)
1607 @{
1608   char name[strlen (str1) + strlen (str2) + 1];
1609   strcpy (name, str1);
1610   strcat (name, str2);
1611   return open (name, flags, mode);
1612 @}
1613 @end smallexample
1614
1615 But @code{alloca} is not always equivalent to a variable-sized array, for
1616 several reasons:
1617
1618 @itemize @bullet
1619 @item
1620 A variable size array's space is freed at the end of the scope of the
1621 name of the array.  The space allocated with @code{alloca}
1622 remains until the end of the function.
1623
1624 @item
1625 It is possible to use @code{alloca} within a loop, allocating an
1626 additional block on each iteration.  This is impossible with
1627 variable-sized arrays.
1628 @end itemize
1629
1630 @strong{Note:} If you mix use of @code{alloca} and variable-sized arrays
1631 within one function, exiting a scope in which a variable-sized array was
1632 declared frees all blocks allocated with @code{alloca} during the
1633 execution of that scope.
1634
1635
1636 @node Relocating Allocator
1637 @section Relocating Allocator
1638
1639 @cindex relocating memory allocator
1640 Any system of dynamic memory allocation has overhead: the amount of
1641 space it uses is more than the amount the program asks for.  The
1642 @dfn{relocating memory allocator} achieves very low overhead by moving
1643 blocks in memory as necessary, on its own initiative.
1644
1645 @menu
1646 * Relocator Concepts::          How to understand relocating allocation.
1647 * Using Relocator::             Functions for relocating allocation.
1648 @end menu
1649
1650 @node Relocator Concepts
1651 @subsection Concepts of Relocating Allocation
1652
1653 @ifinfo
1654 The @dfn{relocating memory allocator} achieves very low overhead by
1655 moving blocks in memory as necessary, on its own initiative.
1656 @end ifinfo
1657
1658 When you allocate a block with @code{malloc}, the address of the block
1659 never changes unless you use @code{realloc} to change its size.  Thus,
1660 you can safely store the address in various places, temporarily or
1661 permanently, as you like.  This is not safe when you use the relocating
1662 memory allocator, because any and all relocatable blocks can move
1663 whenever you allocate memory in any fashion.  Even calling @code{malloc}
1664 or @code{realloc} can move the relocatable blocks.
1665
1666 @cindex handle
1667 For each relocatable block, you must make a @dfn{handle}---a pointer
1668 object in memory, designated to store the address of that block.  The
1669 relocating allocator knows where each block's handle is, and updates the
1670 address stored there whenever it moves the block, so that the handle
1671 always points to the block.  Each time you access the contents of the
1672 block, you should fetch its address anew from the handle.
1673
1674 To call any of the relocating allocator functions from a signal handler
1675 is almost certainly incorrect, because the signal could happen at any
1676 time and relocate all the blocks.  The only way to make this safe is to
1677 block the signal around any access to the contents of any relocatable
1678 block---not a convenient mode of operation.  @xref{Nonreentrancy}.
1679
1680 @node Using Relocator
1681 @subsection Allocating and Freeing Relocatable Blocks
1682
1683 @pindex malloc.h
1684 In the descriptions below, @var{handleptr} designates the address of the
1685 handle.  All the functions are declared in @file{malloc.h}; all are GNU
1686 extensions.
1687
1688 @comment malloc.h
1689 @comment GNU
1690 @deftypefun {void *} r_alloc (void **@var{handleptr}, size_t @var{size})
1691 This function allocates a relocatable block of size @var{size}.  It
1692 stores the block's address in @code{*@var{handleptr}} and returns
1693 a non-null pointer to indicate success.
1694
1695 If @code{r_alloc} can't get the space needed, it stores a null pointer
1696 in @code{*@var{handleptr}}, and returns a null pointer.
1697 @end deftypefun
1698
1699 @comment malloc.h
1700 @comment GNU
1701 @deftypefun void r_alloc_free (void **@var{handleptr})
1702 This function is the way to free a relocatable block.  It frees the
1703 block that @code{*@var{handleptr}} points to, and stores a null pointer
1704 in @code{*@var{handleptr}} to show it doesn't point to an allocated
1705 block any more.
1706 @end deftypefun
1707
1708 @comment malloc.h
1709 @comment GNU
1710 @deftypefun {void *} r_re_alloc (void **@var{handleptr}, size_t @var{size})
1711 The function @code{r_re_alloc} adjusts the size of the block that
1712 @code{*@var{handleptr}} points to, making it @var{size} bytes long.  It
1713 stores the address of the resized block in @code{*@var{handleptr}} and
1714 returns a non-null pointer to indicate success.
1715
1716 If enough memory is not available, this function returns a null pointer
1717 and does not modify @code{*@var{handleptr}}.
1718 @end deftypefun
1719
1720 @node Memory Warnings
1721 @section Memory Usage Warnings
1722 @cindex memory usage warnings
1723 @cindex warnings of memory almost full
1724
1725 @pindex malloc.c
1726 You can ask for warnings as the program approaches running out of memory
1727 space, by calling @code{memory_warnings}.  This tells @code{malloc} to
1728 check memory usage every time it asks for more memory from the operating
1729 system.  This is a GNU extension declared in @file{malloc.h}.
1730
1731 @comment malloc.h
1732 @comment GNU
1733 @deftypefun void memory_warnings (void *@var{start}, void (*@var{warn-func}) (const char *))
1734 Call this function to request warnings for nearing exhaustion of virtual
1735 memory.
1736
1737 The argument @var{start} says where data space begins, in memory.  The
1738 allocator compares this against the last address used and against the
1739 limit of data space, to determine the fraction of available memory in
1740 use.  If you supply zero for @var{start}, then a default value is used
1741 which is right in most circumstances.
1742
1743 For @var{warn-func}, supply a function that @code{malloc} can call to
1744 warn you.  It is called with a string (a warning message) as argument.
1745 Normally it ought to display the string for the user to read.
1746 @end deftypefun
1747
1748 The warnings come when memory becomes 75% full, when it becomes 85%
1749 full, and when it becomes 95% full.  Above 95% you get another warning
1750 each time memory usage increases.
1751