dd1b51b8540bd00bfc7040f811baaf7abef16b84
[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   __malloc_hook = my_malloc_hook;
614   printf ("malloc (%u) returns %p\n", (unsigned int) size, result);
615   return result;
616 @}
617
618 main ()
619 @{
620   ...
621   old_malloc_hook = __malloc_hook;
622   __malloc_hook = my_malloc_hook;
623   ...
624 @}
625 @end smallexample
626
627 The @code{mcheck} function (@pxref{Heap Consistency Checking}) works by
628 installing such hooks.
629
630 @c __morecore, __after_morecore_hook are undocumented
631 @c It's not clear whether to document them.
632
633 @node Statistics of Malloc
634 @subsection Statistics for Storage Allocation with @code{malloc}
635
636 @cindex allocation statistics
637 You can get information about dynamic storage allocation by calling the
638 @code{mstats} function.  This function and its associated data type are
639 declared in @file{malloc.h}; they are a GNU extension.
640 @pindex malloc.h
641
642 @comment malloc.h
643 @comment GNU
644 @deftp {Data Type} {struct mstats}
645 This structure type is used to return information about the dynamic
646 storage allocator.  It contains the following members:
647
648 @table @code
649 @item size_t bytes_total
650 This is the total size of memory managed by @code{malloc}, in bytes.
651
652 @item size_t chunks_used
653 This is the number of chunks in use.  (The storage allocator internally
654 gets chunks of memory from the operating system, and then carves them up
655 to satisfy individual @code{malloc} requests; see @ref{Efficiency and
656 Malloc}.)
657
658 @item size_t bytes_used
659 This is the number of bytes in use.
660
661 @item size_t chunks_free
662 This is the number of chunks which are free -- that is, that have been
663 allocated by the operating system to your program, but which are not
664 now being used.
665
666 @item size_t bytes_free
667 This is the number of bytes which are free.
668 @end table
669 @end deftp
670
671 @comment malloc.h
672 @comment GNU
673 @deftypefun {struct mstats} mstats (void)
674 This function returns information about the current dynamic memory usage
675 in a structure of type @code{struct mstats}.
676 @end deftypefun
677
678 @node Summary of Malloc
679 @subsection Summary of @code{malloc}-Related Functions
680
681 Here is a summary of the functions that work with @code{malloc}:
682
683 @table @code
684 @item void *malloc (size_t @var{size})
685 Allocate a block of @var{size} bytes.  @xref{Basic Allocation}.
686
687 @item void free (void *@var{addr})
688 Free a block previously allocated by @code{malloc}.  @xref{Freeing after
689 Malloc}.
690
691 @item void *realloc (void *@var{addr}, size_t @var{size})
692 Make a block previously allocated by @code{malloc} larger or smaller,
693 possibly by copying it to a new location.  @xref{Changing Block Size}.
694
695 @item void *calloc (size_t @var{count}, size_t @var{eltsize})
696 Allocate a block of @var{count} * @var{eltsize} bytes using
697 @code{malloc}, and set its contents to zero.  @xref{Allocating Cleared
698 Space}.
699
700 @item void *valloc (size_t @var{size})
701 Allocate a block of @var{size} bytes, starting on a page boundary.
702 @xref{Aligned Memory Blocks}.
703
704 @item void *memalign (size_t @var{size}, size_t @var{boundary})
705 Allocate a block of @var{size} bytes, starting on an address that is a
706 multiple of @var{boundary}.  @xref{Aligned Memory Blocks}.
707
708 @item int mcheck (void (*@var{abortfn}) (void))
709 Tell @code{malloc} to perform occasional consistency checks on
710 dynamically allocated memory, and to call @var{abortfn} when an
711 inconsistency is found.  @xref{Heap Consistency Checking}.
712
713 @item void *(*__malloc_hook) (size_t @var{size})
714 A pointer to a function that @code{malloc} uses whenever it is called.
715
716 @item void *(*__realloc_hook) (void *@var{ptr}, size_t @var{size})
717 A pointer to a function that @code{realloc} uses whenever it is called.
718
719 @item void (*__free_hook) (void *@var{ptr})
720 A pointer to a function that @code{free} uses whenever it is called.
721
722 @item struct mstats mstats (void)
723 Return information about the current dynamic memory usage.
724 @xref{Statistics of Malloc}.
725 @end table
726
727 @node Obstacks
728 @section Obstacks
729 @cindex obstacks
730
731 An @dfn{obstack} is a pool of memory containing a stack of objects.  You
732 can create any number of separate obstacks, and then allocate objects in
733 specified obstacks.  Within each obstack, the last object allocated must
734 always be the first one freed, but distinct obstacks are independent of
735 each other.
736
737 Aside from this one constraint of order of freeing, obstacks are totally
738 general: an obstack can contain any number of objects of any size.  They
739 are implemented with macros, so allocation is usually very fast as long as
740 the objects are usually small.  And the only space overhead per object is
741 the padding needed to start each object on a suitable boundary.
742
743 @menu
744 * Creating Obstacks::           How to declare an obstack in your program.
745 * Preparing for Obstacks::      Preparations needed before you can
746                                  use obstacks.
747 * Allocation in an Obstack::    Allocating objects in an obstack.
748 * Freeing Obstack Objects::     Freeing objects in an obstack.
749 * Obstack Functions::           The obstack functions are both
750                                  functions and macros.
751 * Growing Objects::             Making an object bigger by stages.
752 * Extra Fast Growing::          Extra-high-efficiency (though more
753                                  complicated) growing objects.
754 * Status of an Obstack::        Inquiries about the status of an obstack.
755 * Obstacks Data Alignment::     Controlling alignment of objects in obstacks.
756 * Obstack Chunks::              How obstacks obtain and release chunks;
757                                  efficiency considerations.
758 * Summary of Obstacks::         
759 @end menu
760
761 @node Creating Obstacks
762 @subsection Creating Obstacks
763
764 The utilities for manipulating obstacks are declared in the header
765 file @file{obstack.h}.
766 @pindex obstack.h
767
768 @comment obstack.h
769 @comment GNU
770 @deftp {Data Type} {struct obstack}
771 An obstack is represented by a data structure of type @code{struct
772 obstack}.  This structure has a small fixed size; it records the status
773 of the obstack and how to find the space in which objects are allocated.
774 It does not contain any of the objects themselves.  You should not try
775 to access the contents of the structure directly; use only the functions
776 described in this chapter.
777 @end deftp
778
779 You can declare variables of type @code{struct obstack} and use them as
780 obstacks, or you can allocate obstacks dynamically like any other kind
781 of object.  Dynamic allocation of obstacks allows your program to have a
782 variable number of different stacks.  (You can even allocate an
783 obstack structure in another obstack, but this is rarely useful.)
784
785 All the functions that work with obstacks require you to specify which
786 obstack to use.  You do this with a pointer of type @code{struct obstack
787 *}.  In the following, we often say ``an obstack'' when strictly
788 speaking the object at hand is such a pointer.
789
790 The objects in the obstack are packed into large blocks called
791 @dfn{chunks}.  The @code{struct obstack} structure points to a chain of
792 the chunks currently in use.
793
794 The obstack library obtains a new chunk whenever you allocate an object
795 that won't fit in the previous chunk.  Since the obstack library manages
796 chunks automatically, you don't need to pay much attention to them, but
797 you do need to supply a function which the obstack library should use to
798 get a chunk.  Usually you supply a function which uses @code{malloc}
799 directly or indirectly.  You must also supply a function to free a chunk.
800 These matters are described in the following section.
801
802 @node Preparing for Obstacks
803 @subsection Preparing for Using Obstacks
804
805 Each source file in which you plan to use the obstack functions
806 must include the header file @file{obstack.h}, like this:
807
808 @smallexample
809 #include <obstack.h>
810 @end smallexample
811
812 @findex obstack_chunk_alloc
813 @findex obstack_chunk_free
814 Also, if the source file uses the macro @code{obstack_init}, it must
815 declare or define two functions or macros that will be called by the
816 obstack library.  One, @code{obstack_chunk_alloc}, is used to allocate
817 the chunks of memory into which objects are packed.  The other,
818 @code{obstack_chunk_free}, is used to return chunks when the objects in
819 them are freed.  These macros should appear before any use of obstacks
820 in the source file.
821
822 Usually these are defined to use @code{malloc} via the intermediary
823 @code{xmalloc} (@pxref{Unconstrained Allocation}).  This is done with
824 the following pair of macro definitions:
825
826 @smallexample
827 #define obstack_chunk_alloc xmalloc
828 #define obstack_chunk_free free
829 @end smallexample
830
831 @noindent
832 Though the storage you get using obstacks really comes from @code{malloc},
833 using obstacks is faster because @code{malloc} is called less often, for
834 larger blocks of memory.  @xref{Obstack Chunks}, for full details.
835
836 At run time, before the program can use a @code{struct obstack} object
837 as an obstack, it must initialize the obstack by calling
838 @code{obstack_init}.
839
840 @comment obstack.h
841 @comment GNU
842 @deftypefun int obstack_init (struct obstack *@var{obstack-ptr})
843 Initialize obstack @var{obstack-ptr} for allocation of objects.  This
844 function calls the obstack's @code{obstack_chunk_alloc} function.  It
845 returns 0 if @code{obstack_chunk_alloc} returns a null pointer, meaning
846 that it is out of memory.  Otherwise, it returns 1.  If you supply an
847 @code{obstack_chunk_alloc} function that calls @code{exit}
848 (@pxref{Program Termination}) or @code{longjmp} (@pxref{Non-Local
849 Exits}) when out of memory, you can safely ignore the value that
850 @code{obstack_init} returns.
851 @end deftypefun
852
853 Here are two examples of how to allocate the space for an obstack and
854 initialize it.  First, an obstack that is a static variable:
855
856 @smallexample
857 static struct obstack myobstack;
858 @dots{}
859 obstack_init (&myobstack);
860 @end smallexample
861
862 @noindent
863 Second, an obstack that is itself dynamically allocated:
864
865 @smallexample
866 struct obstack *myobstack_ptr
867   = (struct obstack *) xmalloc (sizeof (struct obstack));
868
869 obstack_init (myobstack_ptr);
870 @end smallexample
871
872 @node Allocation in an Obstack
873 @subsection Allocation in an Obstack
874 @cindex allocation (obstacks)
875
876 The most direct way to allocate an object in an obstack is with
877 @code{obstack_alloc}, which is invoked almost like @code{malloc}.
878
879 @comment obstack.h
880 @comment GNU
881 @deftypefun {void *} obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
882 This allocates an uninitialized block of @var{size} bytes in an obstack
883 and returns its address.  Here @var{obstack-ptr} specifies which obstack
884 to allocate the block in; it is the address of the @code{struct obstack}
885 object which represents the obstack.  Each obstack function or macro
886 requires you to specify an @var{obstack-ptr} as the first argument.
887
888 This function calls the obstack's @code{obstack_chunk_alloc} function if
889 it needs to allocate a new chunk of memory; it returns a null pointer if
890 @code{obstack_chunk_alloc} returns one.  In that case, it has not
891 changed the amount of memory allocated in the obstack.  If you supply an
892 @code{obstack_chunk_alloc} function that calls @code{exit}
893 (@pxref{Program Termination}) or @code{longjmp} (@pxref{Non-Local
894 Exits}) when out of memory, then @code{obstack_alloc} will never return
895 a null pointer.
896 @end deftypefun
897
898 For example, here is a function that allocates a copy of a string @var{str}
899 in a specific obstack, which is in the variable @code{string_obstack}:
900
901 @smallexample
902 struct obstack string_obstack;
903
904 char *
905 copystring (char *string)
906 @{
907   char *s = (char *) obstack_alloc (&string_obstack,
908                                     strlen (string) + 1);
909   memcpy (s, string, strlen (string));
910   return s;
911 @}
912 @end smallexample
913
914 To allocate a block with specified contents, use the function
915 @code{obstack_copy}, declared like this:
916
917 @comment obstack.h
918 @comment GNU
919 @deftypefun {void *} obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
920 This allocates a block and initializes it by copying @var{size}
921 bytes of data starting at @var{address}.  It can return a null pointer
922 under the same conditions as @code{obstack_alloc}.
923 @end deftypefun
924
925 @comment obstack.h
926 @comment GNU
927 @deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
928 Like @code{obstack_copy}, but appends an extra byte containing a null
929 character.  This extra byte is not counted in the argument @var{size}.
930 @end deftypefun
931
932 The @code{obstack_copy0} function is convenient for copying a sequence
933 of characters into an obstack as a null-terminated string.  Here is an
934 example of its use:
935
936 @smallexample
937 char *
938 obstack_savestring (char *addr, int size)
939 @{
940   return obstack_copy0 (&myobstack, addr, size);
941 @}
942 @end smallexample
943
944 @noindent
945 Contrast this with the previous example of @code{savestring} using
946 @code{malloc} (@pxref{Basic Allocation}).
947
948 @node Freeing Obstack Objects
949 @subsection Freeing Objects in an Obstack
950 @cindex freeing (obstacks)
951
952 To free an object allocated in an obstack, use the function
953 @code{obstack_free}.  Since the obstack is a stack of objects, freeing
954 one object automatically frees all other objects allocated more recently
955 in the same obstack.
956
957 @comment obstack.h
958 @comment GNU
959 @deftypefun void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
960 If @var{object} is a null pointer, everything allocated in the obstack
961 is freed.  Otherwise, @var{object} must be the address of an object
962 allocated in the obstack.  Then @var{object} is freed, along with
963 everything allocated in @var{obstack} since @var{object}.
964 @end deftypefun
965
966 Note that if @var{object} is a null pointer, the result is an
967 uninitialized obstack.  To free all storage in an obstack but leave it
968 valid for further allocation, call @code{obstack_free} with the address
969 of the first object allocated on the obstack:
970
971 @smallexample
972 obstack_free (obstack_ptr, first_object_allocated_ptr);
973 @end smallexample
974
975 Recall that the objects in an obstack are grouped into chunks.  When all
976 the objects in a chunk become free, the obstack library automatically
977 frees the chunk (@pxref{Preparing for Obstacks}).  Then other
978 obstacks, or non-obstack allocation, can reuse the space of the chunk.
979
980 @node Obstack Functions
981 @subsection Obstack Functions and Macros
982 @cindex macros
983
984 The interfaces for using obstacks may be defined either as functions or
985 as macros, depending on the compiler.  The obstack facility works with
986 all C compilers, including both ANSI C and traditional C, but there are
987 precautions you must take if you plan to use compilers other than GNU C.
988
989 If you are using an old-fashioned non-ANSI C compiler, all the obstack
990 ``functions'' are actually defined only as macros.  You can call these
991 macros like functions, but you cannot use them in any other way (for
992 example, you cannot take their address).
993
994 Calling the macros requires a special precaution: namely, the first
995 operand (the obstack pointer) may not contain any side effects, because
996 it may be computed more than once.  For example, if you write this:
997
998 @smallexample
999 obstack_alloc (get_obstack (), 4);
1000 @end smallexample
1001
1002 @noindent
1003 you will find that @code{get_obstack} may be called several times.
1004 If you use @code{*obstack_list_ptr++} as the obstack pointer argument,
1005 you will get very strange results since the incrementation may occur
1006 several times.
1007
1008 In ANSI C, each function has both a macro definition and a function
1009 definition.  The function definition is used if you take the address of the
1010 function without calling it.  An ordinary call uses the macro definition by
1011 default, but you can request the function definition instead by writing the
1012 function name in parentheses, as shown here:
1013
1014 @smallexample
1015 char *x;
1016 void *(*funcp) ();
1017 /* @r{Use the macro}.  */
1018 x = (char *) obstack_alloc (obptr, size);
1019 /* @r{Call the function}.  */
1020 x = (char *) (obstack_alloc) (obptr, size);
1021 /* @r{Take the address of the function}.  */
1022 funcp = obstack_alloc;
1023 @end smallexample
1024
1025 @noindent
1026 This is the same situation that exists in ANSI C for the standard library
1027 functions.  @xref{Macro Definitions}.
1028
1029 @strong{Warning:} When you do use the macros, you must observe the
1030 precaution of avoiding side effects in the first operand, even in ANSI
1031 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_finish (struct obstack *@var{obstack-ptr})
1096 When you are finished growing the object, use the function
1097 @code{obstack_finish} to close it off and return its final address.
1098
1099 Once you have finished the object, the obstack is available for ordinary
1100 allocation or for growing another object.
1101
1102 This function can return a null pointer under the same conditions as
1103 @code{obstack_alloc} (@pxref{Allocation in an Obstack}).
1104 @end deftypefun
1105
1106 When you build an object by growing it, you will probably need to know
1107 afterward how long it became.  You need not keep track of this as you grow
1108 the object, because you can find out the length from the obstack just
1109 before finishing the object with the function @code{obstack_object_size},
1110 declared as follows:
1111
1112 @comment obstack.h
1113 @comment GNU
1114 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1115 This function returns the current size of the growing object, in bytes.
1116 Remember to call this function @emph{before} finishing the object.
1117 After it is finished, @code{obstack_object_size} will return zero.
1118 @end deftypefun
1119
1120 If you have started growing an object and wish to cancel it, you should
1121 finish it and then free it, like this:
1122
1123 @smallexample
1124 obstack_free (obstack_ptr, obstack_finish (obstack_ptr));
1125 @end smallexample
1126
1127 @noindent
1128 This has no effect if no object was growing.
1129
1130 @cindex shrinking objects
1131 You can use @code{obstack_blank} with a negative size argument to make
1132 the current object smaller.  Just don't try to shrink it beyond zero
1133 length---there's no telling what will happen if you do that.
1134
1135 @node Extra Fast Growing
1136 @subsection Extra Fast Growing Objects
1137 @cindex efficiency and obstacks
1138
1139 The usual functions for growing objects incur overhead for checking
1140 whether there is room for the new growth in the current chunk.  If you
1141 are frequently constructing objects in small steps of growth, this
1142 overhead can be significant.
1143
1144 You can reduce the overhead by using special ``fast growth''
1145 functions that grow the object without checking.  In order to have a
1146 robust program, you must do the checking yourself.  If you do this checking
1147 in the simplest way each time you are about to add data to the object, you
1148 have not saved anything, because that is what the ordinary growth
1149 functions do.  But if you can arrange to check less often, or check
1150 more efficiently, then you make the program faster.
1151
1152 The function @code{obstack_room} returns the amount of room available
1153 in the current chunk.  It is declared as follows:
1154
1155 @comment obstack.h
1156 @comment GNU
1157 @deftypefun int obstack_room (struct obstack *@var{obstack-ptr})
1158 This returns the number of bytes that can be added safely to the current
1159 growing object (or to an object about to be started) in obstack
1160 @var{obstack} using the fast growth functions.
1161 @end deftypefun
1162
1163 While you know there is room, you can use these fast growth functions
1164 for adding data to a growing object:
1165
1166 @comment obstack.h
1167 @comment GNU
1168 @deftypefun void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{c})
1169 The function @code{obstack_1grow_fast} adds one byte containing the
1170 character @var{c} to the growing object in obstack @var{obstack-ptr}.
1171 @end deftypefun
1172
1173 @comment obstack.h
1174 @comment GNU
1175 @deftypefun void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1176 The function @code{obstack_blank_fast} adds @var{size} bytes to the
1177 growing object in obstack @var{obstack-ptr} without initializing them.
1178 @end deftypefun
1179
1180 When you check for space using @code{obstack_room} and there is not
1181 enough room for what you want to add, the fast growth functions
1182 are not safe.  In this case, simply use the corresponding ordinary
1183 growth function instead.  Very soon this will copy the object to a
1184 new chunk; then there will be lots of room available again. 
1185
1186 So, each time you use an ordinary growth function, check afterward for
1187 sufficient space using @code{obstack_room}.  Once the object is copied
1188 to a new chunk, there will be plenty of space again, so the program will
1189 start using the fast growth functions again.
1190
1191 Here is an example:
1192
1193 @smallexample
1194 @group
1195 void
1196 add_string (struct obstack *obstack, const char *ptr, int len)
1197 @{
1198   while (len > 0)
1199     @{
1200       int room = obstack_room (obstack);
1201       if (room == 0)
1202         @{
1203           /* @r{Not enough room. Add one character slowly,}
1204              @r{which may copy to a new chunk and make room.}  */
1205           obstack_1grow (obstack, *ptr++);
1206           len--;
1207         @}
1208       else 
1209         @{
1210           if (room > len)
1211             room = len;
1212           /* @r{Add fast as much as we have room for.} */
1213           len -= room;
1214           while (room-- > 0)
1215             obstack_1grow_fast (obstack, *ptr++);
1216         @}
1217     @}
1218 @}
1219 @end group
1220 @end smallexample
1221
1222 @node Status of an Obstack
1223 @subsection Status of an Obstack
1224 @cindex obstack status
1225 @cindex status of obstack
1226
1227 Here are functions that provide information on the current status of
1228 allocation in an obstack.  You can use them to learn about an object while
1229 still growing it.
1230
1231 @comment obstack.h
1232 @comment GNU
1233 @deftypefun {void *} obstack_base (struct obstack *@var{obstack-ptr})
1234 This function returns the tentative address of the beginning of the
1235 currently growing object in @var{obstack-ptr}.  If you finish the object
1236 immediately, it will have that address.  If you make it larger first, it
1237 may outgrow the current chunk---then its address will change!
1238
1239 If no object is growing, this value says where the next object you
1240 allocate will start (once again assuming it fits in the current
1241 chunk).
1242 @end deftypefun
1243
1244 @comment obstack.h
1245 @comment GNU
1246 @deftypefun {void *} obstack_next_free (struct obstack *@var{obstack-ptr})
1247 This function returns the address of the first free byte in the current
1248 chunk of obstack @var{obstack-ptr}.  This is the end of the currently
1249 growing object.  If no object is growing, @code{obstack_next_free}
1250 returns the same value as @code{obstack_base}.
1251 @end deftypefun
1252
1253 @comment obstack.h
1254 @comment GNU
1255 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1256 This function returns the size in bytes of the currently growing object.
1257 This is equivalent to
1258
1259 @smallexample
1260 obstack_next_free (@var{obstack-ptr}) - obstack_base (@var{obstack-ptr})
1261 @end smallexample
1262 @end deftypefun
1263
1264 @node Obstacks Data Alignment
1265 @subsection Alignment of Data in Obstacks
1266 @cindex alignment (in obstacks)
1267
1268 Each obstack has an @dfn{alignment boundary}; each object allocated in
1269 the obstack automatically starts on an address that is a multiple of the
1270 specified boundary.  By default, this boundary is 4 bytes.
1271
1272 To access an obstack's alignment boundary, use the macro
1273 @code{obstack_alignment_mask}, whose function prototype looks like
1274 this:
1275
1276 @comment obstack.h
1277 @comment GNU
1278 @deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
1279 The value is a bit mask; a bit that is 1 indicates that the corresponding
1280 bit in the address of an object should be 0.  The mask value should be one
1281 less than a power of 2; the effect is that all object addresses are
1282 multiples of that power of 2.  The default value of the mask is 3, so that
1283 addresses are multiples of 4.  A mask value of 0 means an object can start
1284 on any multiple of 1 (that is, no alignment is required).
1285
1286 The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
1287 so you can alter the mask by assignment.  For example, this statement:
1288
1289 @smallexample
1290 obstack_alignment_mask (obstack_ptr) = 0;
1291 @end smallexample
1292
1293 @noindent
1294 has the effect of turning off alignment processing in the specified obstack.
1295 @end deftypefn
1296
1297 Note that a change in alignment mask does not take effect until
1298 @emph{after} the next time an object is allocated or finished in the
1299 obstack.  If you are not growing an object, you can make the new
1300 alignment mask take effect immediately by calling @code{obstack_finish}.
1301 This will finish a zero-length object and then do proper alignment for
1302 the next object.
1303
1304 @node Obstack Chunks
1305 @subsection Obstack Chunks
1306 @cindex efficiency of chunks
1307 @cindex chunks
1308
1309 Obstacks work by allocating space for themselves in large chunks, and
1310 then parceling out space in the chunks to satisfy your requests.  Chunks
1311 are normally 4096 bytes long unless you specify a different chunk size.
1312 The chunk size includes 8 bytes of overhead that are not actually used
1313 for storing objects.  Regardless of the specified size, longer chunks
1314 will be allocated when necessary for long objects.
1315
1316 The obstack library allocates chunks by calling the function
1317 @code{obstack_chunk_alloc}, which you must define.  When a chunk is no
1318 longer needed because you have freed all the objects in it, the obstack
1319 library frees the chunk by calling @code{obstack_chunk_free}, which you
1320 must also define.
1321
1322 These two must be defined (as macros) or declared (as functions) in each
1323 source file that uses @code{obstack_init} (@pxref{Creating Obstacks}).
1324 Most often they are defined as macros like this:
1325
1326 @smallexample
1327 #define obstack_chunk_alloc xmalloc
1328 #define obstack_chunk_free free
1329 @end smallexample
1330
1331 Note that these are simple macros (no arguments).  Macro definitions with
1332 arguments will not work!  It is necessary that @code{obstack_chunk_alloc}
1333 or @code{obstack_chunk_free}, alone, expand into a function name if it is
1334 not itself a function name.
1335
1336 If you allocate chunks with @code{malloc}, the chunk size should be a
1337 power of 2.  The default chunk size, 4096, was chosen because it is long
1338 enough to satisfy many typical requests on the obstack yet short enough
1339 not to waste too much memory in the portion of the last chunk not yet used.
1340
1341 @comment obstack.h
1342 @comment GNU
1343 @deftypefn Macro int obstack_chunk_size (struct obstack *@var{obstack-ptr})
1344 This returns the chunk size of the given obstack.
1345 @end deftypefn
1346
1347 Since this macro expands to an lvalue, you can specify a new chunk size by
1348 assigning it a new value.  Doing so does not affect the chunks already
1349 allocated, but will change the size of chunks allocated for that particular
1350 obstack in the future.  It is unlikely to be useful to make the chunk size
1351 smaller, but making it larger might improve efficiency if you are
1352 allocating many objects whose size is comparable to the chunk size.  Here
1353 is how to do so cleanly:
1354
1355 @smallexample
1356 if (obstack_chunk_size (obstack_ptr) < @var{new-chunk-size})
1357   obstack_chunk_size (obstack_ptr) = @var{new-chunk-size};
1358 @end smallexample
1359
1360 @node Summary of Obstacks
1361 @subsection Summary of Obstack Functions
1362
1363 Here is a summary of all the functions associated with obstacks.  Each
1364 takes the address of an obstack (@code{struct obstack *}) as its first
1365 argument.
1366
1367 @table @code
1368 @item void obstack_init (struct obstack *@var{obstack-ptr})
1369 Initialize use of an obstack.  @xref{Creating Obstacks}.
1370
1371 @item void *obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
1372 Allocate an object of @var{size} uninitialized bytes.
1373 @xref{Allocation in an Obstack}.
1374
1375 @item void *obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1376 Allocate an object of @var{size} bytes, with contents copied from
1377 @var{address}.  @xref{Allocation in an Obstack}.
1378
1379 @item void *obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1380 Allocate an object of @var{size}+1 bytes, with @var{size} of them copied
1381 from @var{address}, followed by a null character at the end.
1382 @xref{Allocation in an Obstack}.
1383
1384 @item void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
1385 Free @var{object} (and everything allocated in the specified obstack
1386 more recently than @var{object}).  @xref{Freeing Obstack Objects}.
1387
1388 @item void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
1389 Add @var{size} uninitialized bytes to a growing object.
1390 @xref{Growing Objects}.
1391
1392 @item void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1393 Add @var{size} bytes, copied from @var{address}, to a growing object.
1394 @xref{Growing Objects}.
1395
1396 @item void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1397 Add @var{size} bytes, copied from @var{address}, to a growing object,
1398 and then add another byte containing a null character.  @xref{Growing
1399 Objects}.
1400
1401 @item void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{data-char})
1402 Add one byte containing @var{data-char} to a growing object.
1403 @xref{Growing Objects}.
1404
1405 @item void *obstack_finish (struct obstack *@var{obstack-ptr})
1406 Finalize the object that is growing and return its permanent address.
1407 @xref{Growing Objects}.
1408
1409 @item int obstack_object_size (struct obstack *@var{obstack-ptr})
1410 Get the current size of the currently growing object.  @xref{Growing
1411 Objects}.
1412
1413 @item void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1414 Add @var{size} uninitialized bytes to a growing object without checking
1415 that there is enough room.  @xref{Extra Fast Growing}.
1416
1417 @item void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{data-char})
1418 Add one byte containing @var{data-char} to a growing object without
1419 checking that there is enough room.  @xref{Extra Fast Growing}.
1420
1421 @item int obstack_room (struct obstack *@var{obstack-ptr})
1422 Get the amount of room now available for growing the current object.
1423 @xref{Extra Fast Growing}.
1424
1425 @item int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
1426 The mask used for aligning the beginning of an object.  This is an
1427 lvalue.  @xref{Obstacks Data Alignment}.
1428
1429 @item int obstack_chunk_size (struct obstack *@var{obstack-ptr})
1430 The size for allocating chunks.  This is an lvalue.  @xref{Obstack Chunks}.
1431
1432 @item void *obstack_base (struct obstack *@var{obstack-ptr})
1433 Tentative starting address of the currently growing object.
1434 @xref{Status of an Obstack}.
1435
1436 @item void *obstack_next_free (struct obstack *@var{obstack-ptr})
1437 Address just after the end of the currently growing object.
1438 @xref{Status of an Obstack}.
1439 @end table
1440
1441 @node Variable Size Automatic
1442 @section Automatic Storage with Variable Size
1443 @cindex automatic freeing
1444 @cindex @code{alloca} function
1445 @cindex automatic storage with variable size
1446
1447 The function @code{alloca} supports a kind of half-dynamic allocation in
1448 which blocks are allocated dynamically but freed automatically.
1449
1450 Allocating a block with @code{alloca} is an explicit action; you can
1451 allocate as many blocks as you wish, and compute the size at run time.  But
1452 all the blocks are freed when you exit the function that @code{alloca} was
1453 called from, just as if they were automatic variables declared in that
1454 function.  There is no way to free the space explicitly.
1455
1456 The prototype for @code{alloca} is in @file{stdlib.h}.  This function is
1457 a BSD extension.
1458 @pindex stdlib.h
1459
1460 @comment stdlib.h
1461 @comment GNU, BSD
1462 @deftypefun {void *} alloca (size_t @var{size});
1463 The return value of @code{alloca} is the address of a block of @var{size}
1464 bytes of storage, allocated in the stack frame of the calling function.
1465 @end deftypefun
1466
1467 Do not use @code{alloca} inside the arguments of a function call---you
1468 will get unpredictable results, because the stack space for the
1469 @code{alloca} would appear on the stack in the middle of the space for
1470 the function arguments.  An example of what to avoid is @code{foo (x,
1471 alloca (4), y)}.
1472 @c This might get fixed in future versions of GCC, but that won't make
1473 @c it safe with compilers generally.
1474
1475 @menu
1476 * Alloca Example::              Example of using @code{alloca}.
1477 * Advantages of Alloca::        Reasons to use @code{alloca}.
1478 * Disadvantages of Alloca::     Reasons to avoid @code{alloca}.
1479 * GNU C Variable-Size Arrays::  Only in GNU C, here is an alternative
1480                                  method of allocating dynamically and
1481                                  freeing automatically.
1482 @end menu
1483
1484 @node Alloca Example
1485 @subsection @code{alloca} Example
1486
1487 As an example of use of @code{alloca}, here is a function that opens a file
1488 name made from concatenating two argument strings, and returns a file
1489 descriptor or minus one signifying failure:
1490
1491 @smallexample
1492 int
1493 open2 (char *str1, char *str2, int flags, int mode)
1494 @{
1495   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1496   strcpy (name, str1);
1497   strcat (name, str2);
1498   return open (name, flags, mode);
1499 @}
1500 @end smallexample
1501
1502 @noindent
1503 Here is how you would get the same results with @code{malloc} and
1504 @code{free}:
1505
1506 @smallexample
1507 int
1508 open2 (char *str1, char *str2, int flags, int mode)
1509 @{
1510   char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
1511   int desc;
1512   if (name == 0)
1513     fatal ("virtual memory exceeded");
1514   strcpy (name, str1);
1515   strcat (name, str2);
1516   desc = open (name, flags, mode);
1517   free (name);
1518   return desc;
1519 @}
1520 @end smallexample
1521
1522 As you can see, it is simpler with @code{alloca}.  But @code{alloca} has
1523 other, more important advantages, and some disadvantages.
1524
1525 @node Advantages of Alloca
1526 @subsection Advantages of @code{alloca}
1527
1528 Here are the reasons why @code{alloca} may be preferable to @code{malloc}:
1529
1530 @itemize @bullet
1531 @item
1532 Using @code{alloca} wastes very little space and is very fast.  (It is
1533 open-coded by the GNU C compiler.)
1534
1535 @item
1536 Since @code{alloca} does not have separate pools for different sizes of
1537 block, space used for any size block can be reused for any other size.
1538 @code{alloca} does not cause storage fragmentation.
1539
1540 @item
1541 @cindex longjmp
1542 Nonlocal exits done with @code{longjmp} (@pxref{Non-Local Exits})
1543 automatically free the space allocated with @code{alloca} when they exit
1544 through the function that called @code{alloca}.  This is the most
1545 important reason to use @code{alloca}.
1546
1547 To illustrate this, suppose you have a function
1548 @code{open_or_report_error} which returns a descriptor, like
1549 @code{open}, if it succeeds, but does not return to its caller if it
1550 fails.  If the file cannot be opened, it prints an error message and
1551 jumps out to the command level of your program using @code{longjmp}.
1552 Let's change @code{open2} (@pxref{Alloca Example}) to use this
1553 subroutine:@refill
1554
1555 @smallexample
1556 int
1557 open2 (char *str1, char *str2, int flags, int mode)
1558 @{
1559   char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
1560   strcpy (name, str1);
1561   strcat (name, str2);
1562   return open_or_report_error (name, flags, mode);
1563 @}
1564 @end smallexample
1565
1566 @noindent
1567 Because of the way @code{alloca} works, the storage it allocates is
1568 freed even when an error occurs, with no special effort required.
1569
1570 By contrast, the previous definition of @code{open2} (which uses
1571 @code{malloc} and @code{free}) would develop a storage leak if it were
1572 changed in this way.  Even if you are willing to make more changes to
1573 fix it, there is no easy way to do so.
1574 @end itemize
1575
1576 @node Disadvantages of Alloca
1577 @subsection Disadvantages of @code{alloca}
1578
1579 @cindex @code{alloca} disadvantages
1580 @cindex disadvantages of @code{alloca}
1581 These are the disadvantages of @code{alloca} in comparison with
1582 @code{malloc}:
1583
1584 @itemize @bullet
1585 @item
1586 If you try to allocate more storage than the machine can provide, you
1587 don't get a clean error message.  Instead you get a fatal signal like
1588 the one you would get from an infinite recursion; probably a
1589 segmentation violation (@pxref{Program Error Signals}).
1590
1591 @item
1592 Some non-GNU systems fail to support @code{alloca}, so it is less
1593 portable.  However, a slower emulation of @code{alloca} written in C
1594 is available for use on systems with this deficiency.
1595 @end itemize
1596
1597 @node GNU C Variable-Size Arrays
1598 @subsection GNU C Variable-Size Arrays
1599 @cindex variable-sized arrays
1600
1601 In GNU C, you can replace most uses of @code{alloca} with an array of
1602 variable size.  Here is how @code{open2} would look then:
1603
1604 @smallexample
1605 int open2 (char *str1, char *str2, int flags, int mode)
1606 @{
1607   char name[strlen (str1) + strlen (str2) + 1];
1608   strcpy (name, str1);
1609   strcat (name, str2);
1610   return open (name, flags, mode);
1611 @}
1612 @end smallexample
1613
1614 But @code{alloca} is not always equivalent to a variable-sized array, for
1615 several reasons:
1616
1617 @itemize @bullet
1618 @item
1619 A variable size array's space is freed at the end of the scope of the
1620 name of the array.  The space allocated with @code{alloca}
1621 remains until the end of the function.
1622
1623 @item
1624 It is possible to use @code{alloca} within a loop, allocating an
1625 additional block on each iteration.  This is impossible with
1626 variable-sized arrays.
1627 @end itemize
1628
1629 @strong{Note:} If you mix use of @code{alloca} and variable-sized arrays
1630 within one function, exiting a scope in which a variable-sized array was
1631 declared frees all blocks allocated with @code{alloca} during the
1632 execution of that scope.
1633
1634
1635 @node Relocating Allocator
1636 @section Relocating Allocator
1637
1638 @cindex relocating memory allocator
1639 Any system of dynamic memory allocation has overhead: the amount of
1640 space it uses is more than the amount the program asks for.  The
1641 @dfn{relocating memory allocator} achieves very low overhead by moving
1642 blocks in memory as necessary, on its own initiative.
1643
1644 @menu
1645 * Relocator Concepts::          How to understand relocating allocation.
1646 * Using Relocator::             Functions for relocating allocation.
1647 @end menu
1648
1649 @node Relocator Concepts
1650 @subsection Concepts of Relocating Allocation
1651
1652 @ifinfo
1653 The @dfn{relocating memory allocator} achieves very low overhead by
1654 moving blocks in memory as necessary, on its own initiative.
1655 @end ifinfo
1656
1657 When you allocate a block with @code{malloc}, the address of the block
1658 never changes unless you use @code{realloc} to change its size.  Thus,
1659 you can safely store the address in various places, temporarily or
1660 permanently, as you like.  This is not safe when you use the relocating
1661 memory allocator, because any and all relocatable blocks can move
1662 whenever you allocate memory in any fashion.  Even calling @code{malloc}
1663 or @code{realloc} can move the relocatable blocks.
1664
1665 @cindex handle
1666 For each relocatable block, you must make a @dfn{handle}---a pointer
1667 object in memory, designated to store the address of that block.  The
1668 relocating allocator knows where each block's handle is, and updates the
1669 address stored there whenever it moves the block, so that the handle
1670 always points to the block.  Each time you access the contents of the
1671 block, you should fetch its address anew from the handle.
1672
1673 To call any of the relocating allocator functions from a signal handler
1674 is almost certainly incorrect, because the signal could happen at any
1675 time and relocate all the blocks.  The only way to make this safe is to
1676 block the signal around any access to the contents of any relocatable
1677 block---not a convenient mode of operation.  @xref{Nonreentrancy}.
1678
1679 @node Using Relocator
1680 @subsection Allocating and Freeing Relocatable Blocks
1681
1682 @pindex malloc.h
1683 In the descriptions below, @var{handleptr} designates the address of the
1684 handle.  All the functions are declared in @file{malloc.h}; all are GNU
1685 extensions.
1686
1687 @comment malloc.h
1688 @comment GNU
1689 @deftypefun {void *} r_alloc (void **@var{handleptr}, size_t @var{size})
1690 This function allocates a relocatable block of size @var{size}.  It
1691 stores the block's address in @code{*@var{handleptr}} and returns
1692 a non-null pointer to indicate success.
1693
1694 If @code{r_alloc} can't get the space needed, it stores a null pointer
1695 in @code{*@var{handleptr}}, and returns a null pointer.
1696 @end deftypefun
1697
1698 @comment malloc.h
1699 @comment GNU
1700 @deftypefun void r_alloc_free (void **@var{handleptr})
1701 This function is the way to free a relocatable block.  It frees the
1702 block that @code{*@var{handleptr}} points to, and stores a null pointer
1703 in @code{*@var{handleptr}} to show it doesn't point to an allocated
1704 block any more.
1705 @end deftypefun
1706
1707 @comment malloc.h
1708 @comment GNU
1709 @deftypefun {void *} r_re_alloc (void **@var{handleptr}, size_t @var{size})
1710 The function @code{r_re_alloc} adjusts the size of the block that
1711 @code{*@var{handleptr}} points to, making it @var{size} bytes long.  It
1712 stores the address of the resized block in @code{*@var{handleptr}} and
1713 returns a non-null pointer to indicate success.
1714
1715 If enough memory is not available, this function returns a null pointer
1716 and does not modify @code{*@var{handleptr}}.
1717 @end deftypefun
1718
1719 @node Memory Warnings
1720 @section Memory Usage Warnings
1721 @cindex memory usage warnings
1722 @cindex warnings of memory almost full
1723
1724 @pindex malloc.c
1725 You can ask for warnings as the program approaches running out of memory
1726 space, by calling @code{memory_warnings}.  This tells @code{malloc} to
1727 check memory usage every time it asks for more memory from the operating
1728 system.  This is a GNU extension declared in @file{malloc.h}.
1729
1730 @comment malloc.h
1731 @comment GNU
1732 @deftypefun void memory_warnings (void *@var{start}, void (*@var{warn-func}) (const char *))
1733 Call this function to request warnings for nearing exhaustion of virtual
1734 memory.
1735
1736 The argument @var{start} says where data space begins, in memory.  The
1737 allocator compares this against the last address used and against the
1738 limit of data space, to determine the fraction of available memory in
1739 use.  If you supply zero for @var{start}, then a default value is used
1740 which is right in most circumstances.
1741
1742 For @var{warn-func}, supply a function that @code{malloc} can call to
1743 warn you.  It is called with a string (a warning message) as argument.
1744 Normally it ought to display the string for the user to read.
1745 @end deftypefun
1746
1747 The warnings come when memory becomes 75% full, when it becomes 85%
1748 full, and when it becomes 95% full.  Above 95% you get another warning
1749 each time memory usage increases.
1750