1 @node Memory, Character Handling, Error Reporting, Top
2 @chapter Virtual Memory Allocation And Paging
3 @c %MENU% Allocating virtual memory and controlling paging
4 @cindex memory allocation
5 @cindex storage allocation
7 This chapter describes how processes manage and use memory in a system
10 @Theglibc{} has several functions for dynamically allocating
11 virtual memory in various ways. They vary in generality and in
12 efficiency. The library also provides functions for controlling paging
13 and allocation of real memory.
17 * Memory Concepts:: An introduction to concepts and terminology.
18 * Memory Allocation:: Allocating storage for your program data
19 * Resizing the Data Segment:: @code{brk}, @code{sbrk}
20 * Locking Pages:: Preventing page faults
23 Memory mapped I/O is not discussed in this chapter. @xref{Memory-mapped I/O}.
28 @section Process Memory Concepts
30 One of the most basic resources a process has available to it is memory.
31 There are a lot of different ways systems organize memory, but in a
32 typical one, each process has one linear virtual address space, with
33 addresses running from zero to some huge maximum. It need not be
34 contiguous; i.e., not all of these addresses actually can be used to
37 The virtual memory is divided into pages (4 kilobytes is typical).
38 Backing each page of virtual memory is a page of real memory (called a
39 @dfn{frame}) or some secondary storage, usually disk space. The disk
40 space might be swap space or just some ordinary disk file. Actually, a
41 page of all zeroes sometimes has nothing at all backing it -- there's
42 just a flag saying it is all zeroes.
44 @cindex frame, real memory
46 @cindex page, virtual memory
48 The same frame of real memory or backing store can back multiple virtual
49 pages belonging to multiple processes. This is normally the case, for
50 example, with virtual memory occupied by @glibcadj{} code. The same
51 real memory frame containing the @code{printf} function backs a virtual
52 memory page in each of the existing processes that has a @code{printf}
55 In order for a program to access any part of a virtual page, the page
56 must at that moment be backed by (``connected to'') a real frame. But
57 because there is usually a lot more virtual memory than real memory, the
58 pages must move back and forth between real memory and backing store
59 regularly, coming into real memory when a process needs to access them
60 and then retreating to backing store when not needed anymore. This
61 movement is called @dfn{paging}.
63 When a program attempts to access a page which is not at that moment
64 backed by real memory, this is known as a @dfn{page fault}. When a page
65 fault occurs, the kernel suspends the process, places the page into a
66 real page frame (this is called ``paging in'' or ``faulting in''), then
67 resumes the process so that from the process' point of view, the page
68 was in real memory all along. In fact, to the process, all pages always
69 seem to be in real memory. Except for one thing: the elapsed execution
70 time of an instruction that would normally be a few nanoseconds is
71 suddenly much, much, longer (because the kernel normally has to do I/O
72 to complete the page-in). For programs sensitive to that, the functions
73 described in @ref{Locking Pages} can control it.
77 Within each virtual address space, a process has to keep track of what
78 is at which addresses, and that process is called memory allocation.
79 Allocation usually brings to mind meting out scarce resources, but in
80 the case of virtual memory, that's not a major goal, because there is
81 generally much more of it than anyone needs. Memory allocation within a
82 process is mainly just a matter of making sure that the same byte of
83 memory isn't used to store two different things.
85 Processes allocate memory in two major ways: by exec and
86 programmatically. Actually, forking is a third way, but it's not very
87 interesting. @xref{Creating a Process}.
89 Exec is the operation of creating a virtual address space for a process,
90 loading its basic program into it, and executing the program. It is
91 done by the ``exec'' family of functions (e.g. @code{execl}). The
92 operation takes a program file (an executable), it allocates space to
93 load all the data in the executable, loads it, and transfers control to
94 it. That data is most notably the instructions of the program (the
95 @dfn{text}), but also literals and constants in the program and even
96 some variables: C variables with the static storage class (@pxref{Memory
102 Once that program begins to execute, it uses programmatic allocation to
103 gain additional memory. In a C program with @theglibc{}, there
104 are two kinds of programmatic allocation: automatic and dynamic.
105 @xref{Memory Allocation and C}.
107 Memory-mapped I/O is another form of dynamic virtual memory allocation.
108 Mapping memory to a file means declaring that the contents of certain
109 range of a process' addresses shall be identical to the contents of a
110 specified regular file. The system makes the virtual memory initially
111 contain the contents of the file, and if you modify the memory, the
112 system writes the same modification to the file. Note that due to the
113 magic of virtual memory and page faults, there is no reason for the
114 system to do I/O to read the file, or allocate real memory for its
115 contents, until the program accesses the virtual memory.
116 @xref{Memory-mapped I/O}.
117 @cindex memory mapped I/O
118 @cindex memory mapped file
119 @cindex files, accessing
121 Just as it programmatically allocates memory, the program can
122 programmatically deallocate (@dfn{free}) it. You can't free the memory
123 that was allocated by exec. When the program exits or execs, you might
124 say that all its memory gets freed, but since in both cases the address
125 space ceases to exist, the point is really moot. @xref{Program
127 @cindex execing a program
128 @cindex freeing memory
129 @cindex exiting a program
131 A process' virtual address space is divided into segments. A segment is
132 a contiguous range of virtual addresses. Three important segments are:
138 The @dfn{text segment} contains a program's instructions and literals and
139 static constants. It is allocated by exec and stays the same size for
140 the life of the virtual address space.
143 The @dfn{data segment} is working storage for the program. It can be
144 preallocated and preloaded by exec and the process can extend or shrink
145 it by calling functions as described in @xref{Resizing the Data
146 Segment}. Its lower end is fixed.
149 The @dfn{stack segment} contains a program stack. It grows as the stack
150 grows, but doesn't shrink when the stack shrinks.
156 @node Memory Allocation
157 @section Allocating Storage For Program Data
159 This section covers how ordinary programs manage storage for their data,
160 including the famous @code{malloc} function and some fancier facilities
161 special @theglibc{} and GNU Compiler.
164 * Memory Allocation and C:: How to get different kinds of allocation in C.
165 * Unconstrained Allocation:: The @code{malloc} facility allows fully general
167 * Allocation Debugging:: Finding memory leaks and not freed memory.
168 * Obstacks:: Obstacks are less general than malloc
169 but more efficient and convenient.
170 * Variable Size Automatic:: Allocation of variable-sized blocks
171 of automatic storage that are freed when the
172 calling function returns.
176 @node Memory Allocation and C
177 @subsection Memory Allocation in C Programs
179 The C language supports two kinds of memory allocation through the
180 variables in C programs:
184 @dfn{Static allocation} is what happens when you declare a static or
185 global variable. Each static or global variable defines one block of
186 space, of a fixed size. The space is allocated once, when your program
187 is started (part of the exec operation), and is never freed.
188 @cindex static memory allocation
189 @cindex static storage class
192 @dfn{Automatic allocation} happens when you declare an automatic
193 variable, such as a function argument or a local variable. The space
194 for an automatic variable is allocated when the compound statement
195 containing the declaration is entered, and is freed when that
196 compound statement is exited.
197 @cindex automatic memory allocation
198 @cindex automatic storage class
200 In GNU C, the size of the automatic storage can be an expression
201 that varies. In other C implementations, it must be a constant.
204 A third important kind of memory allocation, @dfn{dynamic allocation},
205 is not supported by C variables but is available via @glibcadj{}
207 @cindex dynamic memory allocation
209 @subsubsection Dynamic Memory Allocation
210 @cindex dynamic memory allocation
212 @dfn{Dynamic memory allocation} is a technique in which programs
213 determine as they are running where to store some information. You need
214 dynamic allocation when the amount of memory you need, or how long you
215 continue to need it, depends on factors that are not known before the
218 For example, you may need a block to store a line read from an input
219 file; since there is no limit to how long a line can be, you must
220 allocate the memory dynamically and make it dynamically larger as you
221 read more of the line.
223 Or, you may need a block for each record or each definition in the input
224 data; since you can't know in advance how many there will be, you must
225 allocate a new block for each record or definition as you read it.
227 When you use dynamic allocation, the allocation of a block of memory is
228 an action that the program requests explicitly. You call a function or
229 macro when you want to allocate space, and specify the size with an
230 argument. If you want to free the space, you do so by calling another
231 function or macro. You can do these things whenever you want, as often
234 Dynamic allocation is not supported by C variables; there is no storage
235 class ``dynamic'', and there can never be a C variable whose value is
236 stored in dynamically allocated space. The only way to get dynamically
237 allocated memory is via a system call (which is generally via a @glibcadj{}
238 function call), and the only way to refer to dynamically
239 allocated space is through a pointer. Because it is less convenient,
240 and because the actual process of dynamic allocation requires more
241 computation time, programmers generally use dynamic allocation only when
242 neither static nor automatic allocation will serve.
244 For example, if you want to allocate dynamically some space to hold a
245 @code{struct foobar}, you cannot declare a variable of type @code{struct
246 foobar} whose contents are the dynamically allocated space. But you can
247 declare a variable of pointer type @code{struct foobar *} and assign it the
248 address of the space. Then you can use the operators @samp{*} and
249 @samp{->} on this pointer variable to refer to the contents of the space:
254 = (struct foobar *) malloc (sizeof (struct foobar));
256 ptr->next = current_foobar;
257 current_foobar = ptr;
261 @node Unconstrained Allocation
262 @subsection Unconstrained Allocation
263 @cindex unconstrained memory allocation
264 @cindex @code{malloc} function
265 @cindex heap, dynamic allocation from
267 The most general dynamic allocation facility is @code{malloc}. It
268 allows you to allocate blocks of memory of any size at any time, make
269 them bigger or smaller at any time, and free the blocks individually at
273 * Basic Allocation:: Simple use of @code{malloc}.
274 * Malloc Examples:: Examples of @code{malloc}. @code{xmalloc}.
275 * Freeing after Malloc:: Use @code{free} to free a block you
276 got with @code{malloc}.
277 * Changing Block Size:: Use @code{realloc} to make a block
279 * Allocating Cleared Space:: Use @code{calloc} to allocate a
281 * Efficiency and Malloc:: Efficiency considerations in use of
283 * Aligned Memory Blocks:: Allocating specially aligned memory.
284 * Malloc Tunable Parameters:: Use @code{mallopt} to adjust allocation
286 * Heap Consistency Checking:: Automatic checking for errors.
287 * Hooks for Malloc:: You can use these hooks for debugging
288 programs that use @code{malloc}.
289 * Statistics of Malloc:: Getting information about how much
290 memory your program is using.
291 * Summary of Malloc:: Summary of @code{malloc} and related functions.
294 @node Basic Allocation
295 @subsubsection Basic Memory Allocation
296 @cindex allocation of memory with @code{malloc}
298 To allocate a block of memory, call @code{malloc}. The prototype for
299 this function is in @file{stdlib.h}.
302 @comment malloc.h stdlib.h
304 @deftypefun {void *} malloc (size_t @var{size})
305 This function returns a pointer to a newly allocated block @var{size}
306 bytes long, or a null pointer if the block could not be allocated.
309 The contents of the block are undefined; you must initialize it yourself
310 (or use @code{calloc} instead; @pxref{Allocating Cleared Space}).
311 Normally you would cast the value as a pointer to the kind of object
312 that you want to store in the block. Here we show an example of doing
313 so, and of initializing the space with zeros using the library function
314 @code{memset} (@pxref{Copying and Concatenation}):
319 ptr = (struct foo *) malloc (sizeof (struct foo));
320 if (ptr == 0) abort ();
321 memset (ptr, 0, sizeof (struct foo));
324 You can store the result of @code{malloc} into any pointer variable
325 without a cast, because @w{ISO C} automatically converts the type
326 @code{void *} to another type of pointer when necessary. But the cast
327 is necessary in contexts other than assignment operators or if you might
328 want your code to run in traditional C.
330 Remember that when allocating space for a string, the argument to
331 @code{malloc} must be one plus the length of the string. This is
332 because a string is terminated with a null character that doesn't count
333 in the ``length'' of the string but does need space. For example:
338 ptr = (char *) malloc (length + 1);
342 @xref{Representation of Strings}, for more information about this.
344 @node Malloc Examples
345 @subsubsection Examples of @code{malloc}
347 If no more space is available, @code{malloc} returns a null pointer.
348 You should check the value of @emph{every} call to @code{malloc}. It is
349 useful to write a subroutine that calls @code{malloc} and reports an
350 error if the value is a null pointer, returning only if the value is
351 nonzero. This function is conventionally called @code{xmalloc}. Here
356 xmalloc (size_t size)
358 void *value = malloc (size);
360 fatal ("virtual memory exhausted");
365 Here is a real example of using @code{malloc} (by way of @code{xmalloc}).
366 The function @code{savestring} will copy a sequence of characters into
367 a newly allocated null-terminated string:
372 savestring (const char *ptr, size_t len)
374 char *value = (char *) xmalloc (len + 1);
376 return (char *) memcpy (value, ptr, len);
381 The block that @code{malloc} gives you is guaranteed to be aligned so
382 that it can hold any type of data. On @gnusystems{}, the address is
383 always a multiple of eight on 32-bit systems, and a multiple of 16 on
384 64-bit systems. Only rarely is any higher boundary (such as a page
385 boundary) necessary; for those cases, use @code{aligned_alloc} or
386 @code{posix_memalign} (@pxref{Aligned Memory Blocks}).
388 Note that the memory located after the end of the block is likely to be
389 in use for something else; perhaps a block already allocated by another
390 call to @code{malloc}. If you attempt to treat the block as longer than
391 you asked for it to be, you are liable to destroy the data that
392 @code{malloc} uses to keep track of its blocks, or you may destroy the
393 contents of another block. If you have already allocated a block and
394 discover you want it to be bigger, use @code{realloc} (@pxref{Changing
397 @node Freeing after Malloc
398 @subsubsection Freeing Memory Allocated with @code{malloc}
399 @cindex freeing memory allocated with @code{malloc}
400 @cindex heap, freeing memory from
402 When you no longer need a block that you got with @code{malloc}, use the
403 function @code{free} to make the block available to be allocated again.
404 The prototype for this function is in @file{stdlib.h}.
407 @comment malloc.h stdlib.h
409 @deftypefun void free (void *@var{ptr})
410 The @code{free} function deallocates the block of memory pointed at
416 @deftypefun void cfree (void *@var{ptr})
417 This function does the same thing as @code{free}. It's provided for
418 backward compatibility with SunOS; you should use @code{free} instead.
421 Freeing a block alters the contents of the block. @strong{Do not expect to
422 find any data (such as a pointer to the next block in a chain of blocks) in
423 the block after freeing it.} Copy whatever you need out of the block before
424 freeing it! Here is an example of the proper way to free all the blocks in
425 a chain, and the strings that they point to:
435 free_chain (struct chain *chain)
439 struct chain *next = chain->next;
447 Occasionally, @code{free} can actually return memory to the operating
448 system and make the process smaller. Usually, all it can do is allow a
449 later call to @code{malloc} to reuse the space. In the meantime, the
450 space remains in your program as part of a free-list used internally by
453 There is no point in freeing blocks at the end of a program, because all
454 of the program's space is given back to the system when the process
457 @node Changing Block Size
458 @subsubsection Changing the Size of a Block
459 @cindex changing the size of a block (@code{malloc})
461 Often you do not know for certain how big a block you will ultimately need
462 at the time you must begin to use the block. For example, the block might
463 be a buffer that you use to hold a line being read from a file; no matter
464 how long you make the buffer initially, you may encounter a line that is
467 You can make the block longer by calling @code{realloc}. This function
468 is declared in @file{stdlib.h}.
471 @comment malloc.h stdlib.h
473 @deftypefun {void *} realloc (void *@var{ptr}, size_t @var{newsize})
474 The @code{realloc} function changes the size of the block whose address is
475 @var{ptr} to be @var{newsize}.
477 Since the space after the end of the block may be in use, @code{realloc}
478 may find it necessary to copy the block to a new address where more free
479 space is available. The value of @code{realloc} is the new address of the
480 block. If the block needs to be moved, @code{realloc} copies the old
483 If you pass a null pointer for @var{ptr}, @code{realloc} behaves just
484 like @samp{malloc (@var{newsize})}. This can be convenient, but beware
485 that older implementations (before @w{ISO C}) may not support this
486 behavior, and will probably crash when @code{realloc} is passed a null
490 Like @code{malloc}, @code{realloc} may return a null pointer if no
491 memory space is available to make the block bigger. When this happens,
492 the original block is untouched; it has not been modified or relocated.
494 In most cases it makes no difference what happens to the original block
495 when @code{realloc} fails, because the application program cannot continue
496 when it is out of memory, and the only thing to do is to give a fatal error
497 message. Often it is convenient to write and use a subroutine,
498 conventionally called @code{xrealloc}, that takes care of the error message
499 as @code{xmalloc} does for @code{malloc}:
503 xrealloc (void *ptr, size_t size)
505 void *value = realloc (ptr, size);
507 fatal ("Virtual memory exhausted");
512 You can also use @code{realloc} to make a block smaller. The reason you
513 would do this is to avoid tying up a lot of memory space when only a little
515 @comment The following is no longer true with the new malloc.
516 @comment But it seems wise to keep the warning for other implementations.
517 In several allocation implementations, making a block smaller sometimes
518 necessitates copying it, so it can fail if no other space is available.
520 If the new size you specify is the same as the old size, @code{realloc}
521 is guaranteed to change nothing and return the same address that you gave.
523 @node Allocating Cleared Space
524 @subsubsection Allocating Cleared Space
526 The function @code{calloc} allocates memory and clears it to zero. It
527 is declared in @file{stdlib.h}.
530 @comment malloc.h stdlib.h
532 @deftypefun {void *} calloc (size_t @var{count}, size_t @var{eltsize})
533 This function allocates a block long enough to contain a vector of
534 @var{count} elements, each of size @var{eltsize}. Its contents are
535 cleared to zero before @code{calloc} returns.
538 You could define @code{calloc} as follows:
542 calloc (size_t count, size_t eltsize)
544 size_t size = count * eltsize;
545 void *value = malloc (size);
547 memset (value, 0, size);
552 But in general, it is not guaranteed that @code{calloc} calls
553 @code{malloc} internally. Therefore, if an application provides its own
554 @code{malloc}/@code{realloc}/@code{free} outside the C library, it
555 should always define @code{calloc}, too.
557 @node Efficiency and Malloc
558 @subsubsection Efficiency Considerations for @code{malloc}
559 @cindex efficiency and @code{malloc}
566 @c No longer true, see below instead.
567 To make the best use of @code{malloc}, it helps to know that the GNU
568 version of @code{malloc} always dispenses small amounts of memory in
569 blocks whose sizes are powers of two. It keeps separate pools for each
570 power of two. This holds for sizes up to a page size. Therefore, if
571 you are free to choose the size of a small block in order to make
572 @code{malloc} more efficient, make it a power of two.
573 @c !!! xref getpagesize
575 Once a page is split up for a particular block size, it can't be reused
576 for another size unless all the blocks in it are freed. In many
577 programs, this is unlikely to happen. Thus, you can sometimes make a
578 program use memory more efficiently by using blocks of the same size for
579 many different purposes.
581 When you ask for memory blocks of a page or larger, @code{malloc} uses a
582 different strategy; it rounds the size up to a multiple of a page, and
583 it can coalesce and split blocks as needed.
585 The reason for the two strategies is that it is important to allocate
586 and free small blocks as fast as possible, but speed is less important
587 for a large block since the program normally spends a fair amount of
588 time using it. Also, large blocks are normally fewer in number.
589 Therefore, for large blocks, it makes sense to use a method which takes
590 more time to minimize the wasted space.
594 As opposed to other versions, the @code{malloc} in @theglibc{}
595 does not round up block sizes to powers of two, neither for large nor
596 for small sizes. Neighboring chunks can be coalesced on a @code{free}
597 no matter what their size is. This makes the implementation suitable
598 for all kinds of allocation patterns without generally incurring high
599 memory waste through fragmentation.
601 Very large blocks (much larger than a page) are allocated with
602 @code{mmap} (anonymous or via @code{/dev/zero}) by this implementation.
603 This has the great advantage that these chunks are returned to the
604 system immediately when they are freed. Therefore, it cannot happen
605 that a large chunk becomes ``locked'' in between smaller ones and even
606 after calling @code{free} wastes memory. The size threshold for
607 @code{mmap} to be used can be adjusted with @code{mallopt}. The use of
608 @code{mmap} can also be disabled completely.
610 @node Aligned Memory Blocks
611 @subsubsection Allocating Aligned Memory Blocks
613 @cindex page boundary
614 @cindex alignment (with @code{malloc})
616 The address of a block returned by @code{malloc} or @code{realloc} in
617 @gnusystems{} is always a multiple of eight (or sixteen on 64-bit
618 systems). If you need a block whose address is a multiple of a higher
619 power of two than that, use @code{aligned_alloc} or @code{posix_memalign}.
620 @code{aligned_alloc} and @code{posix_memalign} are declared in
624 @deftypefun {void *} aligned_alloc (size_t @var{alignment}, size_t @var{size})
625 The @code{aligned_alloc} function allocates a block of @var{size} bytes whose
626 address is a multiple of @var{alignment}. The @var{alignment} must be a
627 power of two and @var{size} must be a multiple of @var{alignment}.
629 The @code{aligned_alloc} function returns a null pointer on error and sets
630 @code{errno} to one of the following values:
634 There was insufficient memory available to satisfy the request.
637 @var{alignment} is not a power of two.
639 This function was introduced in @w{ISO C11} and hence may have better
640 portability to modern non-POSIX systems than @code{posix_memalign}.
647 @deftypefun {void *} memalign (size_t @var{boundary}, size_t @var{size})
648 The @code{memalign} function allocates a block of @var{size} bytes whose
649 address is a multiple of @var{boundary}. The @var{boundary} must be a
650 power of two! The function @code{memalign} works by allocating a
651 somewhat larger block, and then returning an address within the block
652 that is on the specified boundary.
654 The @code{memalign} function returns a null pointer on error and sets
655 @code{errno} to one of the following values:
659 There was insufficient memory available to satisfy the request.
662 @var{alignment} is not a power of two.
666 The @code{memalign} function is obsolete and @code{aligned_alloc} or
667 @code{posix_memalign} should be used instead.
672 @deftypefun int posix_memalign (void **@var{memptr}, size_t @var{alignment}, size_t @var{size})
673 The @code{posix_memalign} function is similar to the @code{memalign}
674 function in that it returns a buffer of @var{size} bytes aligned to a
675 multiple of @var{alignment}. But it adds one requirement to the
676 parameter @var{alignment}: the value must be a power of two multiple of
677 @code{sizeof (void *)}.
679 If the function succeeds in allocation memory a pointer to the allocated
680 memory is returned in @code{*@var{memptr}} and the return value is zero.
681 Otherwise the function returns an error value indicating the problem.
682 The possible error values returned are:
686 There was insufficient memory available to satisfy the request.
689 @var{alignment} is not a power of two multiple of @code{sizeof (void *)}.
693 This function was introduced in POSIX 1003.1d. Although this function is
694 superseded by @code{aligned_alloc}, it is more portable to older POSIX
695 systems that do not support @w{ISO C11}.
698 @comment malloc.h stdlib.h
700 @deftypefun {void *} valloc (size_t @var{size})
701 Using @code{valloc} is like using @code{memalign} and passing the page size
702 as the value of the second argument. It is implemented like this:
708 return memalign (getpagesize (), size);
712 @ref{Query Memory Parameters} for more information about the memory
715 The @code{valloc} function is obsolete and @code{aligned_alloc} or
716 @code{posix_memalign} should be used instead.
719 @node Malloc Tunable Parameters
720 @subsubsection Malloc Tunable Parameters
722 You can adjust some parameters for dynamic memory allocation with the
723 @code{mallopt} function. This function is the general SVID/XPG
724 interface, defined in @file{malloc.h}.
727 @deftypefun int mallopt (int @var{param}, int @var{value})
728 When calling @code{mallopt}, the @var{param} argument specifies the
729 parameter to be set, and @var{value} the new value to be set. Possible
730 choices for @var{param}, as defined in @file{malloc.h}, are:
733 @comment TODO: @item M_ARENA_MAX
734 @comment - Document ARENA_MAX env var.
735 @comment TODO: @item M_ARENA_TEST
736 @comment - Document ARENA_TEST env var.
737 @comment TODO: @item M_CHECK_ACTION
739 The maximum number of chunks to allocate with @code{mmap}. Setting this
740 to zero disables all use of @code{mmap}.
741 @item M_MMAP_THRESHOLD
742 All chunks larger than this value are allocated outside the normal
743 heap, using the @code{mmap} system call. This way it is guaranteed
744 that the memory for these chunks can be returned to the system on
745 @code{free}. Note that requests smaller than this threshold might still
746 be allocated via @code{mmap}.
747 @comment TODO: @item M_MXFAST
749 If non-zero, memory blocks are filled with values depending on some
750 low order bits of this parameter when they are allocated (except when
751 allocated by @code{calloc}) and freed. This can be used to debug the
752 use of uninitialized or freed heap memory. Note that this option does not
753 guarantee that the freed block will have any specific values. It only
754 guarantees that the content the block had before it was freed will be
757 This parameter determines the amount of extra memory to obtain from the
758 system when a call to @code{sbrk} is required. It also specifies the
759 number of bytes to retain when shrinking the heap by calling @code{sbrk}
760 with a negative argument. This provides the necessary hysteresis in
761 heap size such that excessive amounts of system calls can be avoided.
762 @item M_TRIM_THRESHOLD
763 This is the minimum size (in bytes) of the top-most, releasable chunk
764 that will cause @code{sbrk} to be called with a negative argument in
765 order to return memory to the system.
770 @node Heap Consistency Checking
771 @subsubsection Heap Consistency Checking
773 @cindex heap consistency checking
774 @cindex consistency checking, of heap
776 You can ask @code{malloc} to check the consistency of dynamic memory by
777 using the @code{mcheck} function. This function is a GNU extension,
778 declared in @file{mcheck.h}.
783 @deftypefun int mcheck (void (*@var{abortfn}) (enum mcheck_status @var{status}))
784 Calling @code{mcheck} tells @code{malloc} to perform occasional
785 consistency checks. These will catch things such as writing
786 past the end of a block that was allocated with @code{malloc}.
788 The @var{abortfn} argument is the function to call when an inconsistency
789 is found. If you supply a null pointer, then @code{mcheck} uses a
790 default function which prints a message and calls @code{abort}
791 (@pxref{Aborting a Program}). The function you supply is called with
792 one argument, which says what sort of inconsistency was detected; its
793 type is described below.
795 It is too late to begin allocation checking once you have allocated
796 anything with @code{malloc}. So @code{mcheck} does nothing in that
797 case. The function returns @code{-1} if you call it too late, and
798 @code{0} otherwise (when it is successful).
800 The easiest way to arrange to call @code{mcheck} early enough is to use
801 the option @samp{-lmcheck} when you link your program; then you don't
802 need to modify your program source at all. Alternatively you might use
803 a debugger to insert a call to @code{mcheck} whenever the program is
804 started, for example these gdb commands will automatically call @code{mcheck}
805 whenever the program starts:
809 Breakpoint 1, main (argc=2, argv=0xbffff964) at whatever.c:10
811 Type commands for when breakpoint 1 is hit, one per line.
812 End with a line saying just "end".
819 This will however only work if no initialization function of any object
820 involved calls any of the @code{malloc} functions since @code{mcheck}
821 must be called before the first such function.
825 @deftypefun {enum mcheck_status} mprobe (void *@var{pointer})
826 The @code{mprobe} function lets you explicitly check for inconsistencies
827 in a particular allocated block. You must have already called
828 @code{mcheck} at the beginning of the program, to do its occasional
829 checks; calling @code{mprobe} requests an additional consistency check
830 to be done at the time of the call.
832 The argument @var{pointer} must be a pointer returned by @code{malloc}
833 or @code{realloc}. @code{mprobe} returns a value that says what
834 inconsistency, if any, was found. The values are described below.
837 @deftp {Data Type} {enum mcheck_status}
838 This enumerated type describes what kind of inconsistency was detected
839 in an allocated block, if any. Here are the possible values:
842 @item MCHECK_DISABLED
843 @code{mcheck} was not called before the first allocation.
844 No consistency checking can be done.
846 No inconsistency detected.
848 The data immediately before the block was modified.
849 This commonly happens when an array index or pointer
850 is decremented too far.
852 The data immediately after the block was modified.
853 This commonly happens when an array index or pointer
854 is incremented too far.
856 The block was already freed.
860 Another possibility to check for and guard against bugs in the use of
861 @code{malloc}, @code{realloc} and @code{free} is to set the environment
862 variable @code{MALLOC_CHECK_}. When @code{MALLOC_CHECK_} is set, a
863 special (less efficient) implementation is used which is designed to be
864 tolerant against simple errors, such as double calls of @code{free} with
865 the same argument, or overruns of a single byte (off-by-one bugs). Not
866 all such errors can be protected against, however, and memory leaks can
867 result. If @code{MALLOC_CHECK_} is set to @code{0}, any detected heap
868 corruption is silently ignored; if set to @code{1}, a diagnostic is
869 printed on @code{stderr}; if set to @code{2}, @code{abort} is called
870 immediately. This can be useful because otherwise a crash may happen
871 much later, and the true cause for the problem is then very hard to
874 There is one problem with @code{MALLOC_CHECK_}: in SUID or SGID binaries
875 it could possibly be exploited since diverging from the normal programs
876 behavior it now writes something to the standard error descriptor.
877 Therefore the use of @code{MALLOC_CHECK_} is disabled by default for
878 SUID and SGID binaries. It can be enabled again by the system
879 administrator by adding a file @file{/etc/suid-debug} (the content is
880 not important it could be empty).
882 So, what's the difference between using @code{MALLOC_CHECK_} and linking
883 with @samp{-lmcheck}? @code{MALLOC_CHECK_} is orthogonal with respect to
884 @samp{-lmcheck}. @samp{-lmcheck} has been added for backward
885 compatibility. Both @code{MALLOC_CHECK_} and @samp{-lmcheck} should
886 uncover the same bugs - but using @code{MALLOC_CHECK_} you don't need to
887 recompile your application.
889 @node Hooks for Malloc
890 @subsubsection Memory Allocation Hooks
891 @cindex allocation hooks, for @code{malloc}
893 @Theglibc{} lets you modify the behavior of @code{malloc},
894 @code{realloc}, and @code{free} by specifying appropriate hook
895 functions. You can use these hooks to help you debug programs that use
896 dynamic memory allocation, for example.
898 The hook variables are declared in @file{malloc.h}.
903 @defvar __malloc_hook
904 The value of this variable is a pointer to the function that
905 @code{malloc} uses whenever it is called. You should define this
906 function to look like @code{malloc}; that is, like:
909 void *@var{function} (size_t @var{size}, const void *@var{caller})
912 The value of @var{caller} is the return address found on the stack when
913 the @code{malloc} function was called. This value allows you to trace
914 the memory consumption of the program.
919 @defvar __realloc_hook
920 The value of this variable is a pointer to function that @code{realloc}
921 uses whenever it is called. You should define this function to look
922 like @code{realloc}; that is, like:
925 void *@var{function} (void *@var{ptr}, size_t @var{size}, const void *@var{caller})
928 The value of @var{caller} is the return address found on the stack when
929 the @code{realloc} function was called. This value allows you to trace the
930 memory consumption of the program.
936 The value of this variable is a pointer to function that @code{free}
937 uses whenever it is called. You should define this function to look
938 like @code{free}; that is, like:
941 void @var{function} (void *@var{ptr}, const void *@var{caller})
944 The value of @var{caller} is the return address found on the stack when
945 the @code{free} function was called. This value allows you to trace the
946 memory consumption of the program.
951 @defvar __memalign_hook
952 The value of this variable is a pointer to function that @code{aligned_alloc},
953 @code{memalign}, @code{posix_memalign} and @code{valloc} use whenever they
954 are called. You should define this function to look like @code{aligned_alloc};
958 void *@var{function} (size_t @var{alignment}, size_t @var{size}, const void *@var{caller})
961 The value of @var{caller} is the return address found on the stack when
962 the @code{aligned_alloc}, @code{memalign}, @code{posix_memalign} or
963 @code{valloc} functions are called. This value allows you to trace the
964 memory consumption of the program.
967 You must make sure that the function you install as a hook for one of
968 these functions does not call that function recursively without restoring
969 the old value of the hook first! Otherwise, your program will get stuck
970 in an infinite recursion. Before calling the function recursively, one
971 should make sure to restore all the hooks to their previous value. When
972 coming back from the recursive call, all the hooks should be resaved
973 since a hook might modify itself.
977 @defvar __malloc_initialize_hook
978 The value of this variable is a pointer to a function that is called
979 once when the malloc implementation is initialized. This is a weak
980 variable, so it can be overridden in the application with a definition
984 void (*@var{__malloc_initialize_hook}) (void) = my_init_hook;
988 An issue to look out for is the time at which the malloc hook functions
989 can be safely installed. If the hook functions call the malloc-related
990 functions recursively, it is necessary that malloc has already properly
991 initialized itself at the time when @code{__malloc_hook} etc. is
992 assigned to. On the other hand, if the hook functions provide a
993 complete malloc implementation of their own, it is vital that the hooks
994 are assigned to @emph{before} the very first @code{malloc} call has
995 completed, because otherwise a chunk obtained from the ordinary,
996 un-hooked malloc may later be handed to @code{__free_hook}, for example.
998 In both cases, the problem can be solved by setting up the hooks from
999 within a user-defined function pointed to by
1000 @code{__malloc_initialize_hook}---then the hooks will be set up safely
1003 Here is an example showing how to use @code{__malloc_hook} and
1004 @code{__free_hook} properly. It installs a function that prints out
1005 information every time @code{malloc} or @code{free} is called. We just
1006 assume here that @code{realloc} and @code{memalign} are not used in our
1010 /* Prototypes for __malloc_hook, __free_hook */
1013 /* Prototypes for our hooks. */
1014 static void my_init_hook (void);
1015 static void *my_malloc_hook (size_t, const void *);
1016 static void my_free_hook (void*, const void *);
1018 /* Override initializing hook from the C library. */
1019 void (*__malloc_initialize_hook) (void) = my_init_hook;
1024 old_malloc_hook = __malloc_hook;
1025 old_free_hook = __free_hook;
1026 __malloc_hook = my_malloc_hook;
1027 __free_hook = my_free_hook;
1031 my_malloc_hook (size_t size, const void *caller)
1034 /* Restore all old hooks */
1035 __malloc_hook = old_malloc_hook;
1036 __free_hook = old_free_hook;
1037 /* Call recursively */
1038 result = malloc (size);
1039 /* Save underlying hooks */
1040 old_malloc_hook = __malloc_hook;
1041 old_free_hook = __free_hook;
1042 /* @r{@code{printf} might call @code{malloc}, so protect it too.} */
1043 printf ("malloc (%u) returns %p\n", (unsigned int) size, result);
1044 /* Restore our own hooks */
1045 __malloc_hook = my_malloc_hook;
1046 __free_hook = my_free_hook;
1051 my_free_hook (void *ptr, const void *caller)
1053 /* Restore all old hooks */
1054 __malloc_hook = old_malloc_hook;
1055 __free_hook = old_free_hook;
1056 /* Call recursively */
1058 /* Save underlying hooks */
1059 old_malloc_hook = __malloc_hook;
1060 old_free_hook = __free_hook;
1061 /* @r{@code{printf} might call @code{free}, so protect it too.} */
1062 printf ("freed pointer %p\n", ptr);
1063 /* Restore our own hooks */
1064 __malloc_hook = my_malloc_hook;
1065 __free_hook = my_free_hook;
1074 The @code{mcheck} function (@pxref{Heap Consistency Checking}) works by
1075 installing such hooks.
1077 @c __morecore, __after_morecore_hook are undocumented
1078 @c It's not clear whether to document them.
1080 @node Statistics of Malloc
1081 @subsubsection Statistics for Memory Allocation with @code{malloc}
1083 @cindex allocation statistics
1084 You can get information about dynamic memory allocation by calling the
1085 @code{mallinfo} function. This function and its associated data type
1086 are declared in @file{malloc.h}; they are an extension of the standard
1092 @deftp {Data Type} {struct mallinfo}
1093 This structure type is used to return information about the dynamic
1094 memory allocator. It contains the following members:
1098 This is the total size of memory allocated with @code{sbrk} by
1099 @code{malloc}, in bytes.
1102 This is the number of chunks not in use. (The memory allocator
1103 internally gets chunks of memory from the operating system, and then
1104 carves them up to satisfy individual @code{malloc} requests; see
1105 @ref{Efficiency and Malloc}.)
1108 This field is unused.
1111 This is the total number of chunks allocated with @code{mmap}.
1114 This is the total size of memory allocated with @code{mmap}, in bytes.
1117 This field is unused.
1120 This field is unused.
1123 This is the total size of memory occupied by chunks handed out by
1127 This is the total size of memory occupied by free (not in use) chunks.
1130 This is the size of the top-most releasable chunk that normally
1131 borders the end of the heap (i.e., the high end of the virtual address
1132 space's data segment).
1139 @deftypefun {struct mallinfo} mallinfo (void)
1140 This function returns information about the current dynamic memory usage
1141 in a structure of type @code{struct mallinfo}.
1144 @node Summary of Malloc
1145 @subsubsection Summary of @code{malloc}-Related Functions
1147 Here is a summary of the functions that work with @code{malloc}:
1150 @item void *malloc (size_t @var{size})
1151 Allocate a block of @var{size} bytes. @xref{Basic Allocation}.
1153 @item void free (void *@var{addr})
1154 Free a block previously allocated by @code{malloc}. @xref{Freeing after
1157 @item void *realloc (void *@var{addr}, size_t @var{size})
1158 Make a block previously allocated by @code{malloc} larger or smaller,
1159 possibly by copying it to a new location. @xref{Changing Block Size}.
1161 @item void *calloc (size_t @var{count}, size_t @var{eltsize})
1162 Allocate a block of @var{count} * @var{eltsize} bytes using
1163 @code{malloc}, and set its contents to zero. @xref{Allocating Cleared
1166 @item void *valloc (size_t @var{size})
1167 Allocate a block of @var{size} bytes, starting on a page boundary.
1168 @xref{Aligned Memory Blocks}.
1170 @item void *aligned_alloc (size_t @var{size}, size_t @var{alignment})
1171 Allocate a block of @var{size} bytes, starting on an address that is a
1172 multiple of @var{alignment}. @xref{Aligned Memory Blocks}.
1174 @item int posix_memalign (void **@var{memptr}, size_t @var{alignment}, size_t @var{size})
1175 Allocate a block of @var{size} bytes, starting on an address that is a
1176 multiple of @var{alignment}. @xref{Aligned Memory Blocks}.
1178 @item void *memalign (size_t @var{size}, size_t @var{boundary})
1179 Allocate a block of @var{size} bytes, starting on an address that is a
1180 multiple of @var{boundary}. @xref{Aligned Memory Blocks}.
1182 @item int mallopt (int @var{param}, int @var{value})
1183 Adjust a tunable parameter. @xref{Malloc Tunable Parameters}.
1185 @item int mcheck (void (*@var{abortfn}) (void))
1186 Tell @code{malloc} to perform occasional consistency checks on
1187 dynamically allocated memory, and to call @var{abortfn} when an
1188 inconsistency is found. @xref{Heap Consistency Checking}.
1190 @item void *(*__malloc_hook) (size_t @var{size}, const void *@var{caller})
1191 A pointer to a function that @code{malloc} uses whenever it is called.
1193 @item void *(*__realloc_hook) (void *@var{ptr}, size_t @var{size}, const void *@var{caller})
1194 A pointer to a function that @code{realloc} uses whenever it is called.
1196 @item void (*__free_hook) (void *@var{ptr}, const void *@var{caller})
1197 A pointer to a function that @code{free} uses whenever it is called.
1199 @item void (*__memalign_hook) (size_t @var{size}, size_t @var{alignment}, const void *@var{caller})
1200 A pointer to a function that @code{aligned_alloc}, @code{memalign},
1201 @code{posix_memalign} and @code{valloc} use whenever they are called.
1203 @item struct mallinfo mallinfo (void)
1204 Return information about the current dynamic memory usage.
1205 @xref{Statistics of Malloc}.
1208 @node Allocation Debugging
1209 @subsection Allocation Debugging
1210 @cindex allocation debugging
1211 @cindex malloc debugger
1213 A complicated task when programming with languages which do not use
1214 garbage collected dynamic memory allocation is to find memory leaks.
1215 Long running programs must assure that dynamically allocated objects are
1216 freed at the end of their lifetime. If this does not happen the system
1217 runs out of memory, sooner or later.
1219 The @code{malloc} implementation in @theglibc{} provides some
1220 simple means to detect such leaks and obtain some information to find
1221 the location. To do this the application must be started in a special
1222 mode which is enabled by an environment variable. There are no speed
1223 penalties for the program if the debugging mode is not enabled.
1226 * Tracing malloc:: How to install the tracing functionality.
1227 * Using the Memory Debugger:: Example programs excerpts.
1228 * Tips for the Memory Debugger:: Some more or less clever ideas.
1229 * Interpreting the traces:: What do all these lines mean?
1232 @node Tracing malloc
1233 @subsubsection How to install the tracing functionality
1237 @deftypefun void mtrace (void)
1238 When the @code{mtrace} function is called it looks for an environment
1239 variable named @code{MALLOC_TRACE}. This variable is supposed to
1240 contain a valid file name. The user must have write access. If the
1241 file already exists it is truncated. If the environment variable is not
1242 set or it does not name a valid file which can be opened for writing
1243 nothing is done. The behavior of @code{malloc} etc. is not changed.
1244 For obvious reasons this also happens if the application is installed
1245 with the SUID or SGID bit set.
1247 If the named file is successfully opened, @code{mtrace} installs special
1248 handlers for the functions @code{malloc}, @code{realloc}, and
1249 @code{free} (@pxref{Hooks for Malloc}). From then on, all uses of these
1250 functions are traced and protocolled into the file. There is now of
1251 course a speed penalty for all calls to the traced functions so tracing
1252 should not be enabled during normal use.
1254 This function is a GNU extension and generally not available on other
1255 systems. The prototype can be found in @file{mcheck.h}.
1260 @deftypefun void muntrace (void)
1261 The @code{muntrace} function can be called after @code{mtrace} was used
1262 to enable tracing the @code{malloc} calls. If no (successful) call of
1263 @code{mtrace} was made @code{muntrace} does nothing.
1265 Otherwise it deinstalls the handlers for @code{malloc}, @code{realloc},
1266 and @code{free} and then closes the protocol file. No calls are
1267 protocolled anymore and the program runs again at full speed.
1269 This function is a GNU extension and generally not available on other
1270 systems. The prototype can be found in @file{mcheck.h}.
1273 @node Using the Memory Debugger
1274 @subsubsection Example program excerpts
1276 Even though the tracing functionality does not influence the runtime
1277 behavior of the program it is not a good idea to call @code{mtrace} in
1278 all programs. Just imagine that you debug a program using @code{mtrace}
1279 and all other programs used in the debugging session also trace their
1280 @code{malloc} calls. The output file would be the same for all programs
1281 and thus is unusable. Therefore one should call @code{mtrace} only if
1282 compiled for debugging. A program could therefore start like this:
1288 main (int argc, char *argv[])
1297 This is all what is needed if you want to trace the calls during the
1298 whole runtime of the program. Alternatively you can stop the tracing at
1299 any time with a call to @code{muntrace}. It is even possible to restart
1300 the tracing again with a new call to @code{mtrace}. But this can cause
1301 unreliable results since there may be calls of the functions which are
1302 not called. Please note that not only the application uses the traced
1303 functions, also libraries (including the C library itself) use these
1306 This last point is also why it is no good idea to call @code{muntrace}
1307 before the program terminated. The libraries are informed about the
1308 termination of the program only after the program returns from
1309 @code{main} or calls @code{exit} and so cannot free the memory they use
1312 So the best thing one can do is to call @code{mtrace} as the very first
1313 function in the program and never call @code{muntrace}. So the program
1314 traces almost all uses of the @code{malloc} functions (except those
1315 calls which are executed by constructors of the program or used
1318 @node Tips for the Memory Debugger
1319 @subsubsection Some more or less clever ideas
1321 You know the situation. The program is prepared for debugging and in
1322 all debugging sessions it runs well. But once it is started without
1323 debugging the error shows up. A typical example is a memory leak that
1324 becomes visible only when we turn off the debugging. If you foresee
1325 such situations you can still win. Simply use something equivalent to
1326 the following little program:
1336 signal (SIGUSR1, enable);
1343 signal (SIGUSR2, disable);
1347 main (int argc, char *argv[])
1351 signal (SIGUSR1, enable);
1352 signal (SIGUSR2, disable);
1358 I.e., the user can start the memory debugger any time s/he wants if the
1359 program was started with @code{MALLOC_TRACE} set in the environment.
1360 The output will of course not show the allocations which happened before
1361 the first signal but if there is a memory leak this will show up
1364 @node Interpreting the traces
1365 @subsubsection Interpreting the traces
1367 If you take a look at the output it will look similar to this:
1371 @ [0x8048209] - 0x8064cc8
1372 @ [0x8048209] - 0x8064ce0
1373 @ [0x8048209] - 0x8064cf8
1374 @ [0x80481eb] + 0x8064c48 0x14
1375 @ [0x80481eb] + 0x8064c60 0x14
1376 @ [0x80481eb] + 0x8064c78 0x14
1377 @ [0x80481eb] + 0x8064c90 0x14
1381 What this all means is not really important since the trace file is not
1382 meant to be read by a human. Therefore no attention is given to
1383 readability. Instead there is a program which comes with @theglibc{}
1384 which interprets the traces and outputs a summary in an
1385 user-friendly way. The program is called @code{mtrace} (it is in fact a
1386 Perl script) and it takes one or two arguments. In any case the name of
1387 the file with the trace output must be specified. If an optional
1388 argument precedes the name of the trace file this must be the name of
1389 the program which generated the trace.
1392 drepper$ mtrace tst-mtrace log
1396 In this case the program @code{tst-mtrace} was run and it produced a
1397 trace file @file{log}. The message printed by @code{mtrace} shows there
1398 are no problems with the code, all allocated memory was freed
1401 If we call @code{mtrace} on the example trace given above we would get a
1405 drepper$ mtrace errlog
1406 - 0x08064cc8 Free 2 was never alloc'd 0x8048209
1407 - 0x08064ce0 Free 3 was never alloc'd 0x8048209
1408 - 0x08064cf8 Free 4 was never alloc'd 0x8048209
1413 0x08064c48 0x14 at 0x80481eb
1414 0x08064c60 0x14 at 0x80481eb
1415 0x08064c78 0x14 at 0x80481eb
1416 0x08064c90 0x14 at 0x80481eb
1419 We have called @code{mtrace} with only one argument and so the script
1420 has no chance to find out what is meant with the addresses given in the
1421 trace. We can do better:
1424 drepper$ mtrace tst errlog
1425 - 0x08064cc8 Free 2 was never alloc'd /home/drepper/tst.c:39
1426 - 0x08064ce0 Free 3 was never alloc'd /home/drepper/tst.c:39
1427 - 0x08064cf8 Free 4 was never alloc'd /home/drepper/tst.c:39
1432 0x08064c48 0x14 at /home/drepper/tst.c:33
1433 0x08064c60 0x14 at /home/drepper/tst.c:33
1434 0x08064c78 0x14 at /home/drepper/tst.c:33
1435 0x08064c90 0x14 at /home/drepper/tst.c:33
1438 Suddenly the output makes much more sense and the user can see
1439 immediately where the function calls causing the trouble can be found.
1441 Interpreting this output is not complicated. There are at most two
1442 different situations being detected. First, @code{free} was called for
1443 pointers which were never returned by one of the allocation functions.
1444 This is usually a very bad problem and what this looks like is shown in
1445 the first three lines of the output. Situations like this are quite
1446 rare and if they appear they show up very drastically: the program
1449 The other situation which is much harder to detect are memory leaks. As
1450 you can see in the output the @code{mtrace} function collects all this
1451 information and so can say that the program calls an allocation function
1452 from line 33 in the source file @file{/home/drepper/tst-mtrace.c} four
1453 times without freeing this memory before the program terminates.
1454 Whether this is a real problem remains to be investigated.
1457 @subsection Obstacks
1460 An @dfn{obstack} is a pool of memory containing a stack of objects. You
1461 can create any number of separate obstacks, and then allocate objects in
1462 specified obstacks. Within each obstack, the last object allocated must
1463 always be the first one freed, but distinct obstacks are independent of
1466 Aside from this one constraint of order of freeing, obstacks are totally
1467 general: an obstack can contain any number of objects of any size. They
1468 are implemented with macros, so allocation is usually very fast as long as
1469 the objects are usually small. And the only space overhead per object is
1470 the padding needed to start each object on a suitable boundary.
1473 * Creating Obstacks:: How to declare an obstack in your program.
1474 * Preparing for Obstacks:: Preparations needed before you can
1476 * Allocation in an Obstack:: Allocating objects in an obstack.
1477 * Freeing Obstack Objects:: Freeing objects in an obstack.
1478 * Obstack Functions:: The obstack functions are both
1479 functions and macros.
1480 * Growing Objects:: Making an object bigger by stages.
1481 * Extra Fast Growing:: Extra-high-efficiency (though more
1482 complicated) growing objects.
1483 * Status of an Obstack:: Inquiries about the status of an obstack.
1484 * Obstacks Data Alignment:: Controlling alignment of objects in obstacks.
1485 * Obstack Chunks:: How obstacks obtain and release chunks;
1486 efficiency considerations.
1487 * Summary of Obstacks::
1490 @node Creating Obstacks
1491 @subsubsection Creating Obstacks
1493 The utilities for manipulating obstacks are declared in the header
1494 file @file{obstack.h}.
1499 @deftp {Data Type} {struct obstack}
1500 An obstack is represented by a data structure of type @code{struct
1501 obstack}. This structure has a small fixed size; it records the status
1502 of the obstack and how to find the space in which objects are allocated.
1503 It does not contain any of the objects themselves. You should not try
1504 to access the contents of the structure directly; use only the functions
1505 described in this chapter.
1508 You can declare variables of type @code{struct obstack} and use them as
1509 obstacks, or you can allocate obstacks dynamically like any other kind
1510 of object. Dynamic allocation of obstacks allows your program to have a
1511 variable number of different stacks. (You can even allocate an
1512 obstack structure in another obstack, but this is rarely useful.)
1514 All the functions that work with obstacks require you to specify which
1515 obstack to use. You do this with a pointer of type @code{struct obstack
1516 *}. In the following, we often say ``an obstack'' when strictly
1517 speaking the object at hand is such a pointer.
1519 The objects in the obstack are packed into large blocks called
1520 @dfn{chunks}. The @code{struct obstack} structure points to a chain of
1521 the chunks currently in use.
1523 The obstack library obtains a new chunk whenever you allocate an object
1524 that won't fit in the previous chunk. Since the obstack library manages
1525 chunks automatically, you don't need to pay much attention to them, but
1526 you do need to supply a function which the obstack library should use to
1527 get a chunk. Usually you supply a function which uses @code{malloc}
1528 directly or indirectly. You must also supply a function to free a chunk.
1529 These matters are described in the following section.
1531 @node Preparing for Obstacks
1532 @subsubsection Preparing for Using Obstacks
1534 Each source file in which you plan to use the obstack functions
1535 must include the header file @file{obstack.h}, like this:
1538 #include <obstack.h>
1541 @findex obstack_chunk_alloc
1542 @findex obstack_chunk_free
1543 Also, if the source file uses the macro @code{obstack_init}, it must
1544 declare or define two functions or macros that will be called by the
1545 obstack library. One, @code{obstack_chunk_alloc}, is used to allocate
1546 the chunks of memory into which objects are packed. The other,
1547 @code{obstack_chunk_free}, is used to return chunks when the objects in
1548 them are freed. These macros should appear before any use of obstacks
1551 Usually these are defined to use @code{malloc} via the intermediary
1552 @code{xmalloc} (@pxref{Unconstrained Allocation}). This is done with
1553 the following pair of macro definitions:
1556 #define obstack_chunk_alloc xmalloc
1557 #define obstack_chunk_free free
1561 Though the memory you get using obstacks really comes from @code{malloc},
1562 using obstacks is faster because @code{malloc} is called less often, for
1563 larger blocks of memory. @xref{Obstack Chunks}, for full details.
1565 At run time, before the program can use a @code{struct obstack} object
1566 as an obstack, it must initialize the obstack by calling
1567 @code{obstack_init}.
1571 @deftypefun int obstack_init (struct obstack *@var{obstack-ptr})
1572 Initialize obstack @var{obstack-ptr} for allocation of objects. This
1573 function calls the obstack's @code{obstack_chunk_alloc} function. If
1574 allocation of memory fails, the function pointed to by
1575 @code{obstack_alloc_failed_handler} is called. The @code{obstack_init}
1576 function always returns 1 (Compatibility notice: Former versions of
1577 obstack returned 0 if allocation failed).
1580 Here are two examples of how to allocate the space for an obstack and
1581 initialize it. First, an obstack that is a static variable:
1584 static struct obstack myobstack;
1586 obstack_init (&myobstack);
1590 Second, an obstack that is itself dynamically allocated:
1593 struct obstack *myobstack_ptr
1594 = (struct obstack *) xmalloc (sizeof (struct obstack));
1596 obstack_init (myobstack_ptr);
1601 @defvar obstack_alloc_failed_handler
1602 The value of this variable is a pointer to a function that
1603 @code{obstack} uses when @code{obstack_chunk_alloc} fails to allocate
1604 memory. The default action is to print a message and abort.
1605 You should supply a function that either calls @code{exit}
1606 (@pxref{Program Termination}) or @code{longjmp} (@pxref{Non-Local
1607 Exits}) and doesn't return.
1610 void my_obstack_alloc_failed (void)
1612 obstack_alloc_failed_handler = &my_obstack_alloc_failed;
1617 @node Allocation in an Obstack
1618 @subsubsection Allocation in an Obstack
1619 @cindex allocation (obstacks)
1621 The most direct way to allocate an object in an obstack is with
1622 @code{obstack_alloc}, which is invoked almost like @code{malloc}.
1626 @deftypefun {void *} obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
1627 This allocates an uninitialized block of @var{size} bytes in an obstack
1628 and returns its address. Here @var{obstack-ptr} specifies which obstack
1629 to allocate the block in; it is the address of the @code{struct obstack}
1630 object which represents the obstack. Each obstack function or macro
1631 requires you to specify an @var{obstack-ptr} as the first argument.
1633 This function calls the obstack's @code{obstack_chunk_alloc} function if
1634 it needs to allocate a new chunk of memory; it calls
1635 @code{obstack_alloc_failed_handler} if allocation of memory by
1636 @code{obstack_chunk_alloc} failed.
1639 For example, here is a function that allocates a copy of a string @var{str}
1640 in a specific obstack, which is in the variable @code{string_obstack}:
1643 struct obstack string_obstack;
1646 copystring (char *string)
1648 size_t len = strlen (string) + 1;
1649 char *s = (char *) obstack_alloc (&string_obstack, len);
1650 memcpy (s, string, len);
1655 To allocate a block with specified contents, use the function
1656 @code{obstack_copy}, declared like this:
1660 @deftypefun {void *} obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1661 This allocates a block and initializes it by copying @var{size}
1662 bytes of data starting at @var{address}. It calls
1663 @code{obstack_alloc_failed_handler} if allocation of memory by
1664 @code{obstack_chunk_alloc} failed.
1669 @deftypefun {void *} obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
1670 Like @code{obstack_copy}, but appends an extra byte containing a null
1671 character. This extra byte is not counted in the argument @var{size}.
1674 The @code{obstack_copy0} function is convenient for copying a sequence
1675 of characters into an obstack as a null-terminated string. Here is an
1680 obstack_savestring (char *addr, int size)
1682 return obstack_copy0 (&myobstack, addr, size);
1687 Contrast this with the previous example of @code{savestring} using
1688 @code{malloc} (@pxref{Basic Allocation}).
1690 @node Freeing Obstack Objects
1691 @subsubsection Freeing Objects in an Obstack
1692 @cindex freeing (obstacks)
1694 To free an object allocated in an obstack, use the function
1695 @code{obstack_free}. Since the obstack is a stack of objects, freeing
1696 one object automatically frees all other objects allocated more recently
1697 in the same obstack.
1701 @deftypefun void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
1702 If @var{object} is a null pointer, everything allocated in the obstack
1703 is freed. Otherwise, @var{object} must be the address of an object
1704 allocated in the obstack. Then @var{object} is freed, along with
1705 everything allocated in @var{obstack} since @var{object}.
1708 Note that if @var{object} is a null pointer, the result is an
1709 uninitialized obstack. To free all memory in an obstack but leave it
1710 valid for further allocation, call @code{obstack_free} with the address
1711 of the first object allocated on the obstack:
1714 obstack_free (obstack_ptr, first_object_allocated_ptr);
1717 Recall that the objects in an obstack are grouped into chunks. When all
1718 the objects in a chunk become free, the obstack library automatically
1719 frees the chunk (@pxref{Preparing for Obstacks}). Then other
1720 obstacks, or non-obstack allocation, can reuse the space of the chunk.
1722 @node Obstack Functions
1723 @subsubsection Obstack Functions and Macros
1726 The interfaces for using obstacks may be defined either as functions or
1727 as macros, depending on the compiler. The obstack facility works with
1728 all C compilers, including both @w{ISO C} and traditional C, but there are
1729 precautions you must take if you plan to use compilers other than GNU C.
1731 If you are using an old-fashioned @w{non-ISO C} compiler, all the obstack
1732 ``functions'' are actually defined only as macros. You can call these
1733 macros like functions, but you cannot use them in any other way (for
1734 example, you cannot take their address).
1736 Calling the macros requires a special precaution: namely, the first
1737 operand (the obstack pointer) may not contain any side effects, because
1738 it may be computed more than once. For example, if you write this:
1741 obstack_alloc (get_obstack (), 4);
1745 you will find that @code{get_obstack} may be called several times.
1746 If you use @code{*obstack_list_ptr++} as the obstack pointer argument,
1747 you will get very strange results since the incrementation may occur
1750 In @w{ISO C}, each function has both a macro definition and a function
1751 definition. The function definition is used if you take the address of the
1752 function without calling it. An ordinary call uses the macro definition by
1753 default, but you can request the function definition instead by writing the
1754 function name in parentheses, as shown here:
1759 /* @r{Use the macro}. */
1760 x = (char *) obstack_alloc (obptr, size);
1761 /* @r{Call the function}. */
1762 x = (char *) (obstack_alloc) (obptr, size);
1763 /* @r{Take the address of the function}. */
1764 funcp = obstack_alloc;
1768 This is the same situation that exists in @w{ISO C} for the standard library
1769 functions. @xref{Macro Definitions}.
1771 @strong{Warning:} When you do use the macros, you must observe the
1772 precaution of avoiding side effects in the first operand, even in @w{ISO C}.
1774 If you use the GNU C compiler, this precaution is not necessary, because
1775 various language extensions in GNU C permit defining the macros so as to
1776 compute each argument only once.
1778 @node Growing Objects
1779 @subsubsection Growing Objects
1780 @cindex growing objects (in obstacks)
1781 @cindex changing the size of a block (obstacks)
1783 Because memory in obstack chunks is used sequentially, it is possible to
1784 build up an object step by step, adding one or more bytes at a time to the
1785 end of the object. With this technique, you do not need to know how much
1786 data you will put in the object until you come to the end of it. We call
1787 this the technique of @dfn{growing objects}. The special functions
1788 for adding data to the growing object are described in this section.
1790 You don't need to do anything special when you start to grow an object.
1791 Using one of the functions to add data to the object automatically
1792 starts it. However, it is necessary to say explicitly when the object is
1793 finished. This is done with the function @code{obstack_finish}.
1795 The actual address of the object thus built up is not known until the
1796 object is finished. Until then, it always remains possible that you will
1797 add so much data that the object must be copied into a new chunk.
1799 While the obstack is in use for a growing object, you cannot use it for
1800 ordinary allocation of another object. If you try to do so, the space
1801 already added to the growing object will become part of the other object.
1805 @deftypefun void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
1806 The most basic function for adding to a growing object is
1807 @code{obstack_blank}, which adds space without initializing it.
1812 @deftypefun void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
1813 To add a block of initialized space, use @code{obstack_grow}, which is
1814 the growing-object analogue of @code{obstack_copy}. It adds @var{size}
1815 bytes of data to the growing object, copying the contents from
1821 @deftypefun void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{data}, int @var{size})
1822 This is the growing-object analogue of @code{obstack_copy0}. It adds
1823 @var{size} bytes copied from @var{data}, followed by an additional null
1829 @deftypefun void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{c})
1830 To add one character at a time, use the function @code{obstack_1grow}.
1831 It adds a single byte containing @var{c} to the growing object.
1836 @deftypefun void obstack_ptr_grow (struct obstack *@var{obstack-ptr}, void *@var{data})
1837 Adding the value of a pointer one can use the function
1838 @code{obstack_ptr_grow}. It adds @code{sizeof (void *)} bytes
1839 containing the value of @var{data}.
1844 @deftypefun void obstack_int_grow (struct obstack *@var{obstack-ptr}, int @var{data})
1845 A single value of type @code{int} can be added by using the
1846 @code{obstack_int_grow} function. It adds @code{sizeof (int)} bytes to
1847 the growing object and initializes them with the value of @var{data}.
1852 @deftypefun {void *} obstack_finish (struct obstack *@var{obstack-ptr})
1853 When you are finished growing the object, use the function
1854 @code{obstack_finish} to close it off and return its final address.
1856 Once you have finished the object, the obstack is available for ordinary
1857 allocation or for growing another object.
1859 This function can return a null pointer under the same conditions as
1860 @code{obstack_alloc} (@pxref{Allocation in an Obstack}).
1863 When you build an object by growing it, you will probably need to know
1864 afterward how long it became. You need not keep track of this as you grow
1865 the object, because you can find out the length from the obstack just
1866 before finishing the object with the function @code{obstack_object_size},
1867 declared as follows:
1871 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
1872 This function returns the current size of the growing object, in bytes.
1873 Remember to call this function @emph{before} finishing the object.
1874 After it is finished, @code{obstack_object_size} will return zero.
1877 If you have started growing an object and wish to cancel it, you should
1878 finish it and then free it, like this:
1881 obstack_free (obstack_ptr, obstack_finish (obstack_ptr));
1885 This has no effect if no object was growing.
1887 @cindex shrinking objects
1888 You can use @code{obstack_blank} with a negative size argument to make
1889 the current object smaller. Just don't try to shrink it beyond zero
1890 length---there's no telling what will happen if you do that.
1892 @node Extra Fast Growing
1893 @subsubsection Extra Fast Growing Objects
1894 @cindex efficiency and obstacks
1896 The usual functions for growing objects incur overhead for checking
1897 whether there is room for the new growth in the current chunk. If you
1898 are frequently constructing objects in small steps of growth, this
1899 overhead can be significant.
1901 You can reduce the overhead by using special ``fast growth''
1902 functions that grow the object without checking. In order to have a
1903 robust program, you must do the checking yourself. If you do this checking
1904 in the simplest way each time you are about to add data to the object, you
1905 have not saved anything, because that is what the ordinary growth
1906 functions do. But if you can arrange to check less often, or check
1907 more efficiently, then you make the program faster.
1909 The function @code{obstack_room} returns the amount of room available
1910 in the current chunk. It is declared as follows:
1914 @deftypefun int obstack_room (struct obstack *@var{obstack-ptr})
1915 This returns the number of bytes that can be added safely to the current
1916 growing object (or to an object about to be started) in obstack
1917 @var{obstack} using the fast growth functions.
1920 While you know there is room, you can use these fast growth functions
1921 for adding data to a growing object:
1925 @deftypefun void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{c})
1926 The function @code{obstack_1grow_fast} adds one byte containing the
1927 character @var{c} to the growing object in obstack @var{obstack-ptr}.
1932 @deftypefun void obstack_ptr_grow_fast (struct obstack *@var{obstack-ptr}, void *@var{data})
1933 The function @code{obstack_ptr_grow_fast} adds @code{sizeof (void *)}
1934 bytes containing the value of @var{data} to the growing object in
1935 obstack @var{obstack-ptr}.
1940 @deftypefun void obstack_int_grow_fast (struct obstack *@var{obstack-ptr}, int @var{data})
1941 The function @code{obstack_int_grow_fast} adds @code{sizeof (int)} bytes
1942 containing the value of @var{data} to the growing object in obstack
1948 @deftypefun void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
1949 The function @code{obstack_blank_fast} adds @var{size} bytes to the
1950 growing object in obstack @var{obstack-ptr} without initializing them.
1953 When you check for space using @code{obstack_room} and there is not
1954 enough room for what you want to add, the fast growth functions
1955 are not safe. In this case, simply use the corresponding ordinary
1956 growth function instead. Very soon this will copy the object to a
1957 new chunk; then there will be lots of room available again.
1959 So, each time you use an ordinary growth function, check afterward for
1960 sufficient space using @code{obstack_room}. Once the object is copied
1961 to a new chunk, there will be plenty of space again, so the program will
1962 start using the fast growth functions again.
1969 add_string (struct obstack *obstack, const char *ptr, int len)
1973 int room = obstack_room (obstack);
1976 /* @r{Not enough room. Add one character slowly,}
1977 @r{which may copy to a new chunk and make room.} */
1978 obstack_1grow (obstack, *ptr++);
1985 /* @r{Add fast as much as we have room for.} */
1988 obstack_1grow_fast (obstack, *ptr++);
1995 @node Status of an Obstack
1996 @subsubsection Status of an Obstack
1997 @cindex obstack status
1998 @cindex status of obstack
2000 Here are functions that provide information on the current status of
2001 allocation in an obstack. You can use them to learn about an object while
2006 @deftypefun {void *} obstack_base (struct obstack *@var{obstack-ptr})
2007 This function returns the tentative address of the beginning of the
2008 currently growing object in @var{obstack-ptr}. If you finish the object
2009 immediately, it will have that address. If you make it larger first, it
2010 may outgrow the current chunk---then its address will change!
2012 If no object is growing, this value says where the next object you
2013 allocate will start (once again assuming it fits in the current
2019 @deftypefun {void *} obstack_next_free (struct obstack *@var{obstack-ptr})
2020 This function returns the address of the first free byte in the current
2021 chunk of obstack @var{obstack-ptr}. This is the end of the currently
2022 growing object. If no object is growing, @code{obstack_next_free}
2023 returns the same value as @code{obstack_base}.
2028 @deftypefun int obstack_object_size (struct obstack *@var{obstack-ptr})
2029 This function returns the size in bytes of the currently growing object.
2030 This is equivalent to
2033 obstack_next_free (@var{obstack-ptr}) - obstack_base (@var{obstack-ptr})
2037 @node Obstacks Data Alignment
2038 @subsubsection Alignment of Data in Obstacks
2039 @cindex alignment (in obstacks)
2041 Each obstack has an @dfn{alignment boundary}; each object allocated in
2042 the obstack automatically starts on an address that is a multiple of the
2043 specified boundary. By default, this boundary is aligned so that
2044 the object can hold any type of data.
2046 To access an obstack's alignment boundary, use the macro
2047 @code{obstack_alignment_mask}, whose function prototype looks like
2052 @deftypefn Macro int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
2053 The value is a bit mask; a bit that is 1 indicates that the corresponding
2054 bit in the address of an object should be 0. The mask value should be one
2055 less than a power of 2; the effect is that all object addresses are
2056 multiples of that power of 2. The default value of the mask is a value
2057 that allows aligned objects to hold any type of data: for example, if
2058 its value is 3, any type of data can be stored at locations whose
2059 addresses are multiples of 4. A mask value of 0 means an object can start
2060 on any multiple of 1 (that is, no alignment is required).
2062 The expansion of the macro @code{obstack_alignment_mask} is an lvalue,
2063 so you can alter the mask by assignment. For example, this statement:
2066 obstack_alignment_mask (obstack_ptr) = 0;
2070 has the effect of turning off alignment processing in the specified obstack.
2073 Note that a change in alignment mask does not take effect until
2074 @emph{after} the next time an object is allocated or finished in the
2075 obstack. If you are not growing an object, you can make the new
2076 alignment mask take effect immediately by calling @code{obstack_finish}.
2077 This will finish a zero-length object and then do proper alignment for
2080 @node Obstack Chunks
2081 @subsubsection Obstack Chunks
2082 @cindex efficiency of chunks
2085 Obstacks work by allocating space for themselves in large chunks, and
2086 then parceling out space in the chunks to satisfy your requests. Chunks
2087 are normally 4096 bytes long unless you specify a different chunk size.
2088 The chunk size includes 8 bytes of overhead that are not actually used
2089 for storing objects. Regardless of the specified size, longer chunks
2090 will be allocated when necessary for long objects.
2092 The obstack library allocates chunks by calling the function
2093 @code{obstack_chunk_alloc}, which you must define. When a chunk is no
2094 longer needed because you have freed all the objects in it, the obstack
2095 library frees the chunk by calling @code{obstack_chunk_free}, which you
2098 These two must be defined (as macros) or declared (as functions) in each
2099 source file that uses @code{obstack_init} (@pxref{Creating Obstacks}).
2100 Most often they are defined as macros like this:
2103 #define obstack_chunk_alloc malloc
2104 #define obstack_chunk_free free
2107 Note that these are simple macros (no arguments). Macro definitions with
2108 arguments will not work! It is necessary that @code{obstack_chunk_alloc}
2109 or @code{obstack_chunk_free}, alone, expand into a function name if it is
2110 not itself a function name.
2112 If you allocate chunks with @code{malloc}, the chunk size should be a
2113 power of 2. The default chunk size, 4096, was chosen because it is long
2114 enough to satisfy many typical requests on the obstack yet short enough
2115 not to waste too much memory in the portion of the last chunk not yet used.
2119 @deftypefn Macro int obstack_chunk_size (struct obstack *@var{obstack-ptr})
2120 This returns the chunk size of the given obstack.
2123 Since this macro expands to an lvalue, you can specify a new chunk size by
2124 assigning it a new value. Doing so does not affect the chunks already
2125 allocated, but will change the size of chunks allocated for that particular
2126 obstack in the future. It is unlikely to be useful to make the chunk size
2127 smaller, but making it larger might improve efficiency if you are
2128 allocating many objects whose size is comparable to the chunk size. Here
2129 is how to do so cleanly:
2132 if (obstack_chunk_size (obstack_ptr) < @var{new-chunk-size})
2133 obstack_chunk_size (obstack_ptr) = @var{new-chunk-size};
2136 @node Summary of Obstacks
2137 @subsubsection Summary of Obstack Functions
2139 Here is a summary of all the functions associated with obstacks. Each
2140 takes the address of an obstack (@code{struct obstack *}) as its first
2144 @item void obstack_init (struct obstack *@var{obstack-ptr})
2145 Initialize use of an obstack. @xref{Creating Obstacks}.
2147 @item void *obstack_alloc (struct obstack *@var{obstack-ptr}, int @var{size})
2148 Allocate an object of @var{size} uninitialized bytes.
2149 @xref{Allocation in an Obstack}.
2151 @item void *obstack_copy (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
2152 Allocate an object of @var{size} bytes, with contents copied from
2153 @var{address}. @xref{Allocation in an Obstack}.
2155 @item void *obstack_copy0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
2156 Allocate an object of @var{size}+1 bytes, with @var{size} of them copied
2157 from @var{address}, followed by a null character at the end.
2158 @xref{Allocation in an Obstack}.
2160 @item void obstack_free (struct obstack *@var{obstack-ptr}, void *@var{object})
2161 Free @var{object} (and everything allocated in the specified obstack
2162 more recently than @var{object}). @xref{Freeing Obstack Objects}.
2164 @item void obstack_blank (struct obstack *@var{obstack-ptr}, int @var{size})
2165 Add @var{size} uninitialized bytes to a growing object.
2166 @xref{Growing Objects}.
2168 @item void obstack_grow (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
2169 Add @var{size} bytes, copied from @var{address}, to a growing object.
2170 @xref{Growing Objects}.
2172 @item void obstack_grow0 (struct obstack *@var{obstack-ptr}, void *@var{address}, int @var{size})
2173 Add @var{size} bytes, copied from @var{address}, to a growing object,
2174 and then add another byte containing a null character. @xref{Growing
2177 @item void obstack_1grow (struct obstack *@var{obstack-ptr}, char @var{data-char})
2178 Add one byte containing @var{data-char} to a growing object.
2179 @xref{Growing Objects}.
2181 @item void *obstack_finish (struct obstack *@var{obstack-ptr})
2182 Finalize the object that is growing and return its permanent address.
2183 @xref{Growing Objects}.
2185 @item int obstack_object_size (struct obstack *@var{obstack-ptr})
2186 Get the current size of the currently growing object. @xref{Growing
2189 @item void obstack_blank_fast (struct obstack *@var{obstack-ptr}, int @var{size})
2190 Add @var{size} uninitialized bytes to a growing object without checking
2191 that there is enough room. @xref{Extra Fast Growing}.
2193 @item void obstack_1grow_fast (struct obstack *@var{obstack-ptr}, char @var{data-char})
2194 Add one byte containing @var{data-char} to a growing object without
2195 checking that there is enough room. @xref{Extra Fast Growing}.
2197 @item int obstack_room (struct obstack *@var{obstack-ptr})
2198 Get the amount of room now available for growing the current object.
2199 @xref{Extra Fast Growing}.
2201 @item int obstack_alignment_mask (struct obstack *@var{obstack-ptr})
2202 The mask used for aligning the beginning of an object. This is an
2203 lvalue. @xref{Obstacks Data Alignment}.
2205 @item int obstack_chunk_size (struct obstack *@var{obstack-ptr})
2206 The size for allocating chunks. This is an lvalue. @xref{Obstack Chunks}.
2208 @item void *obstack_base (struct obstack *@var{obstack-ptr})
2209 Tentative starting address of the currently growing object.
2210 @xref{Status of an Obstack}.
2212 @item void *obstack_next_free (struct obstack *@var{obstack-ptr})
2213 Address just after the end of the currently growing object.
2214 @xref{Status of an Obstack}.
2217 @node Variable Size Automatic
2218 @subsection Automatic Storage with Variable Size
2219 @cindex automatic freeing
2220 @cindex @code{alloca} function
2221 @cindex automatic storage with variable size
2223 The function @code{alloca} supports a kind of half-dynamic allocation in
2224 which blocks are allocated dynamically but freed automatically.
2226 Allocating a block with @code{alloca} is an explicit action; you can
2227 allocate as many blocks as you wish, and compute the size at run time. But
2228 all the blocks are freed when you exit the function that @code{alloca} was
2229 called from, just as if they were automatic variables declared in that
2230 function. There is no way to free the space explicitly.
2232 The prototype for @code{alloca} is in @file{stdlib.h}. This function is
2238 @deftypefun {void *} alloca (size_t @var{size})
2239 The return value of @code{alloca} is the address of a block of @var{size}
2240 bytes of memory, allocated in the stack frame of the calling function.
2243 Do not use @code{alloca} inside the arguments of a function call---you
2244 will get unpredictable results, because the stack space for the
2245 @code{alloca} would appear on the stack in the middle of the space for
2246 the function arguments. An example of what to avoid is @code{foo (x,
2248 @c This might get fixed in future versions of GCC, but that won't make
2249 @c it safe with compilers generally.
2252 * Alloca Example:: Example of using @code{alloca}.
2253 * Advantages of Alloca:: Reasons to use @code{alloca}.
2254 * Disadvantages of Alloca:: Reasons to avoid @code{alloca}.
2255 * GNU C Variable-Size Arrays:: Only in GNU C, here is an alternative
2256 method of allocating dynamically and
2257 freeing automatically.
2260 @node Alloca Example
2261 @subsubsection @code{alloca} Example
2263 As an example of the use of @code{alloca}, here is a function that opens
2264 a file name made from concatenating two argument strings, and returns a
2265 file descriptor or minus one signifying failure:
2269 open2 (char *str1, char *str2, int flags, int mode)
2271 char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
2272 stpcpy (stpcpy (name, str1), str2);
2273 return open (name, flags, mode);
2278 Here is how you would get the same results with @code{malloc} and
2283 open2 (char *str1, char *str2, int flags, int mode)
2285 char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
2288 fatal ("virtual memory exceeded");
2289 stpcpy (stpcpy (name, str1), str2);
2290 desc = open (name, flags, mode);
2296 As you can see, it is simpler with @code{alloca}. But @code{alloca} has
2297 other, more important advantages, and some disadvantages.
2299 @node Advantages of Alloca
2300 @subsubsection Advantages of @code{alloca}
2302 Here are the reasons why @code{alloca} may be preferable to @code{malloc}:
2306 Using @code{alloca} wastes very little space and is very fast. (It is
2307 open-coded by the GNU C compiler.)
2310 Since @code{alloca} does not have separate pools for different sizes of
2311 block, space used for any size block can be reused for any other size.
2312 @code{alloca} does not cause memory fragmentation.
2316 Nonlocal exits done with @code{longjmp} (@pxref{Non-Local Exits})
2317 automatically free the space allocated with @code{alloca} when they exit
2318 through the function that called @code{alloca}. This is the most
2319 important reason to use @code{alloca}.
2321 To illustrate this, suppose you have a function
2322 @code{open_or_report_error} which returns a descriptor, like
2323 @code{open}, if it succeeds, but does not return to its caller if it
2324 fails. If the file cannot be opened, it prints an error message and
2325 jumps out to the command level of your program using @code{longjmp}.
2326 Let's change @code{open2} (@pxref{Alloca Example}) to use this
2331 open2 (char *str1, char *str2, int flags, int mode)
2333 char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
2334 stpcpy (stpcpy (name, str1), str2);
2335 return open_or_report_error (name, flags, mode);
2340 Because of the way @code{alloca} works, the memory it allocates is
2341 freed even when an error occurs, with no special effort required.
2343 By contrast, the previous definition of @code{open2} (which uses
2344 @code{malloc} and @code{free}) would develop a memory leak if it were
2345 changed in this way. Even if you are willing to make more changes to
2346 fix it, there is no easy way to do so.
2349 @node Disadvantages of Alloca
2350 @subsubsection Disadvantages of @code{alloca}
2352 @cindex @code{alloca} disadvantages
2353 @cindex disadvantages of @code{alloca}
2354 These are the disadvantages of @code{alloca} in comparison with
2359 If you try to allocate more memory than the machine can provide, you
2360 don't get a clean error message. Instead you get a fatal signal like
2361 the one you would get from an infinite recursion; probably a
2362 segmentation violation (@pxref{Program Error Signals}).
2365 Some @nongnusystems{} fail to support @code{alloca}, so it is less
2366 portable. However, a slower emulation of @code{alloca} written in C
2367 is available for use on systems with this deficiency.
2370 @node GNU C Variable-Size Arrays
2371 @subsubsection GNU C Variable-Size Arrays
2372 @cindex variable-sized arrays
2374 In GNU C, you can replace most uses of @code{alloca} with an array of
2375 variable size. Here is how @code{open2} would look then:
2378 int open2 (char *str1, char *str2, int flags, int mode)
2380 char name[strlen (str1) + strlen (str2) + 1];
2381 stpcpy (stpcpy (name, str1), str2);
2382 return open (name, flags, mode);
2386 But @code{alloca} is not always equivalent to a variable-sized array, for
2391 A variable size array's space is freed at the end of the scope of the
2392 name of the array. The space allocated with @code{alloca}
2393 remains until the end of the function.
2396 It is possible to use @code{alloca} within a loop, allocating an
2397 additional block on each iteration. This is impossible with
2398 variable-sized arrays.
2401 @strong{NB:} If you mix use of @code{alloca} and variable-sized arrays
2402 within one function, exiting a scope in which a variable-sized array was
2403 declared frees all blocks allocated with @code{alloca} during the
2404 execution of that scope.
2407 @node Resizing the Data Segment
2408 @section Resizing the Data Segment
2410 The symbols in this section are declared in @file{unistd.h}.
2412 You will not normally use the functions in this section, because the
2413 functions described in @ref{Memory Allocation} are easier to use. Those
2414 are interfaces to a @glibcadj{} memory allocator that uses the
2415 functions below itself. The functions below are simple interfaces to
2420 @deftypefun int brk (void *@var{addr})
2422 @code{brk} sets the high end of the calling process' data segment to
2425 The address of the end of a segment is defined to be the address of the
2426 last byte in the segment plus 1.
2428 The function has no effect if @var{addr} is lower than the low end of
2429 the data segment. (This is considered success, by the way).
2431 The function fails if it would cause the data segment to overlap another
2432 segment or exceed the process' data storage limit (@pxref{Limits on
2435 The function is named for a common historical case where data storage
2436 and the stack are in the same segment. Data storage allocation grows
2437 upward from the bottom of the segment while the stack grows downward
2438 toward it from the top of the segment and the curtain between them is
2439 called the @dfn{break}.
2441 The return value is zero on success. On failure, the return value is
2442 @code{-1} and @code{errno} is set accordingly. The following @code{errno}
2443 values are specific to this function:
2447 The request would cause the data segment to overlap another segment or
2448 exceed the process' data storage limit.
2451 @c The Brk system call in Linux (as opposed to the GNU C Library function)
2452 @c is considerably different. It always returns the new end of the data
2453 @c segment, whether it succeeds or fails. The GNU C library Brk determines
2454 @c it's a failure if and only if the system call returns an address less
2455 @c than the address requested.
2462 @deftypefun void *sbrk (ptrdiff_t @var{delta})
2463 This function is the same as @code{brk} except that you specify the new
2464 end of the data segment as an offset @var{delta} from the current end
2465 and on success the return value is the address of the resulting end of
2466 the data segment instead of zero.
2468 This means you can use @samp{sbrk(0)} to find out what the current end
2469 of the data segment is.
2476 @section Locking Pages
2477 @cindex locking pages
2481 You can tell the system to associate a particular virtual memory page
2482 with a real page frame and keep it that way --- i.e., cause the page to
2483 be paged in if it isn't already and mark it so it will never be paged
2484 out and consequently will never cause a page fault. This is called
2485 @dfn{locking} a page.
2487 The functions in this chapter lock and unlock the calling process'
2491 * Why Lock Pages:: Reasons to read this section.
2492 * Locked Memory Details:: Everything you need to know locked
2494 * Page Lock Functions:: Here's how to do it.
2497 @node Why Lock Pages
2498 @subsection Why Lock Pages
2500 Because page faults cause paged out pages to be paged in transparently,
2501 a process rarely needs to be concerned about locking pages. However,
2502 there are two reasons people sometimes are:
2507 Speed. A page fault is transparent only insofar as the process is not
2508 sensitive to how long it takes to do a simple memory access. Time-critical
2509 processes, especially realtime processes, may not be able to wait or
2510 may not be able to tolerate variance in execution speed.
2511 @cindex realtime processing
2512 @cindex speed of execution
2514 A process that needs to lock pages for this reason probably also needs
2515 priority among other processes for use of the CPU. @xref{Priority}.
2517 In some cases, the programmer knows better than the system's demand
2518 paging allocator which pages should remain in real memory to optimize
2519 system performance. In this case, locking pages can help.
2522 Privacy. If you keep secrets in virtual memory and that virtual memory
2523 gets paged out, that increases the chance that the secrets will get out.
2524 If a password gets written out to disk swap space, for example, it might
2525 still be there long after virtual and real memory have been wiped clean.
2529 Be aware that when you lock a page, that's one fewer page frame that can
2530 be used to back other virtual memory (by the same or other processes),
2531 which can mean more page faults, which means the system runs more
2532 slowly. In fact, if you lock enough memory, some programs may not be
2533 able to run at all for lack of real memory.
2535 @node Locked Memory Details
2536 @subsection Locked Memory Details
2538 A memory lock is associated with a virtual page, not a real frame. The
2539 paging rule is: If a frame backs at least one locked page, don't page it
2542 Memory locks do not stack. I.e., you can't lock a particular page twice
2543 so that it has to be unlocked twice before it is truly unlocked. It is
2544 either locked or it isn't.
2546 A memory lock persists until the process that owns the memory explicitly
2547 unlocks it. (But process termination and exec cause the virtual memory
2548 to cease to exist, which you might say means it isn't locked any more).
2550 Memory locks are not inherited by child processes. (But note that on a
2551 modern Unix system, immediately after a fork, the parent's and the
2552 child's virtual address space are backed by the same real page frames,
2553 so the child enjoys the parent's locks). @xref{Creating a Process}.
2555 Because of its ability to impact other processes, only the superuser can
2556 lock a page. Any process can unlock its own page.
2558 The system sets limits on the amount of memory a process can have locked
2559 and the amount of real memory it can have dedicated to it. @xref{Limits
2562 In Linux, locked pages aren't as locked as you might think.
2563 Two virtual pages that are not shared memory can nonetheless be backed
2564 by the same real frame. The kernel does this in the name of efficiency
2565 when it knows both virtual pages contain identical data, and does it
2566 even if one or both of the virtual pages are locked.
2568 But when a process modifies one of those pages, the kernel must get it a
2569 separate frame and fill it with the page's data. This is known as a
2570 @dfn{copy-on-write page fault}. It takes a small amount of time and in
2571 a pathological case, getting that frame may require I/O.
2572 @cindex copy-on-write page fault
2573 @cindex page fault, copy-on-write
2575 To make sure this doesn't happen to your program, don't just lock the
2576 pages. Write to them as well, unless you know you won't write to them
2577 ever. And to make sure you have pre-allocated frames for your stack,
2578 enter a scope that declares a C automatic variable larger than the
2579 maximum stack size you will need, set it to something, then return from
2582 @node Page Lock Functions
2583 @subsection Functions To Lock And Unlock Pages
2585 The symbols in this section are declared in @file{sys/mman.h}. These
2586 functions are defined by POSIX.1b, but their availability depends on
2587 your kernel. If your kernel doesn't allow these functions, they exist
2588 but always fail. They @emph{are} available with a Linux kernel.
2590 @strong{Portability Note:} POSIX.1b requires that when the @code{mlock}
2591 and @code{munlock} functions are available, the file @file{unistd.h}
2592 define the macro @code{_POSIX_MEMLOCK_RANGE} and the file
2593 @code{limits.h} define the macro @code{PAGESIZE} to be the size of a
2594 memory page in bytes. It requires that when the @code{mlockall} and
2595 @code{munlockall} functions are available, the @file{unistd.h} file
2596 define the macro @code{_POSIX_MEMLOCK}. @Theglibc{} conforms to
2601 @deftypefun int mlock (const void *@var{addr}, size_t @var{len})
2603 @code{mlock} locks a range of the calling process' virtual pages.
2605 The range of memory starts at address @var{addr} and is @var{len} bytes
2606 long. Actually, since you must lock whole pages, it is the range of
2607 pages that include any part of the specified range.
2609 When the function returns successfully, each of those pages is backed by
2610 (connected to) a real frame (is resident) and is marked to stay that
2611 way. This means the function may cause page-ins and have to wait for
2614 When the function fails, it does not affect the lock status of any
2617 The return value is zero if the function succeeds. Otherwise, it is
2618 @code{-1} and @code{errno} is set accordingly. @code{errno} values
2619 specific to this function are:
2625 At least some of the specified address range does not exist in the
2626 calling process' virtual address space.
2628 The locking would cause the process to exceed its locked page limit.
2632 The calling process is not superuser.
2635 @var{len} is not positive.
2638 The kernel does not provide @code{mlock} capability.
2642 You can lock @emph{all} a process' memory with @code{mlockall}. You
2643 unlock memory with @code{munlock} or @code{munlockall}.
2645 To avoid all page faults in a C program, you have to use
2646 @code{mlockall}, because some of the memory a program uses is hidden
2647 from the C code, e.g. the stack and automatic variables, and you
2648 wouldn't know what address to tell @code{mlock}.
2654 @deftypefun int munlock (const void *@var{addr}, size_t @var{len})
2656 @code{munlock} unlocks a range of the calling process' virtual pages.
2658 @code{munlock} is the inverse of @code{mlock} and functions completely
2659 analogously to @code{mlock}, except that there is no @code{EPERM}
2666 @deftypefun int mlockall (int @var{flags})
2668 @code{mlockall} locks all the pages in a process' virtual memory address
2669 space, and/or any that are added to it in the future. This includes the
2670 pages of the code, data and stack segment, as well as shared libraries,
2671 user space kernel data, shared memory, and memory mapped files.
2673 @var{flags} is a string of single bit flags represented by the following
2674 macros. They tell @code{mlockall} which of its functions you want. All
2675 other bits must be zero.
2680 Lock all pages which currently exist in the calling process' virtual
2684 Set a mode such that any pages added to the process' virtual address
2685 space in the future will be locked from birth. This mode does not
2686 affect future address spaces owned by the same process so exec, which
2687 replaces a process' address space, wipes out @code{MCL_FUTURE}.
2688 @xref{Executing a File}.
2692 When the function returns successfully, and you specified
2693 @code{MCL_CURRENT}, all of the process' pages are backed by (connected
2694 to) real frames (they are resident) and are marked to stay that way.
2695 This means the function may cause page-ins and have to wait for them.
2697 When the process is in @code{MCL_FUTURE} mode because it successfully
2698 executed this function and specified @code{MCL_CURRENT}, any system call
2699 by the process that requires space be added to its virtual address space
2700 fails with @code{errno} = @code{ENOMEM} if locking the additional space
2701 would cause the process to exceed its locked page limit. In the case
2702 that the address space addition that can't be accommodated is stack
2703 expansion, the stack expansion fails and the kernel sends a
2704 @code{SIGSEGV} signal to the process.
2706 When the function fails, it does not affect the lock status of any pages
2707 or the future locking mode.
2709 The return value is zero if the function succeeds. Otherwise, it is
2710 @code{-1} and @code{errno} is set accordingly. @code{errno} values
2711 specific to this function are:
2717 At least some of the specified address range does not exist in the
2718 calling process' virtual address space.
2720 The locking would cause the process to exceed its locked page limit.
2724 The calling process is not superuser.
2727 Undefined bits in @var{flags} are not zero.
2730 The kernel does not provide @code{mlockall} capability.
2734 You can lock just specific pages with @code{mlock}. You unlock pages
2735 with @code{munlockall} and @code{munlock}.
2742 @deftypefun int munlockall (void)
2744 @code{munlockall} unlocks every page in the calling process' virtual
2745 address space and turn off @code{MCL_FUTURE} future locking mode.
2747 The return value is zero if the function succeeds. Otherwise, it is
2748 @code{-1} and @code{errno} is set accordingly. The only way this
2749 function can fail is for generic reasons that all functions and system
2750 calls can fail, so there are no specific @code{errno} values.
2758 @c This was never actually implemented. -zw
2759 @node Relocating Allocator
2760 @section Relocating Allocator
2762 @cindex relocating memory allocator
2763 Any system of dynamic memory allocation has overhead: the amount of
2764 space it uses is more than the amount the program asks for. The
2765 @dfn{relocating memory allocator} achieves very low overhead by moving
2766 blocks in memory as necessary, on its own initiative.
2769 @c * Relocator Concepts:: How to understand relocating allocation.
2770 @c * Using Relocator:: Functions for relocating allocation.
2773 @node Relocator Concepts
2774 @subsection Concepts of Relocating Allocation
2777 The @dfn{relocating memory allocator} achieves very low overhead by
2778 moving blocks in memory as necessary, on its own initiative.
2781 When you allocate a block with @code{malloc}, the address of the block
2782 never changes unless you use @code{realloc} to change its size. Thus,
2783 you can safely store the address in various places, temporarily or
2784 permanently, as you like. This is not safe when you use the relocating
2785 memory allocator, because any and all relocatable blocks can move
2786 whenever you allocate memory in any fashion. Even calling @code{malloc}
2787 or @code{realloc} can move the relocatable blocks.
2790 For each relocatable block, you must make a @dfn{handle}---a pointer
2791 object in memory, designated to store the address of that block. The
2792 relocating allocator knows where each block's handle is, and updates the
2793 address stored there whenever it moves the block, so that the handle
2794 always points to the block. Each time you access the contents of the
2795 block, you should fetch its address anew from the handle.
2797 To call any of the relocating allocator functions from a signal handler
2798 is almost certainly incorrect, because the signal could happen at any
2799 time and relocate all the blocks. The only way to make this safe is to
2800 block the signal around any access to the contents of any relocatable
2801 block---not a convenient mode of operation. @xref{Nonreentrancy}.
2803 @node Using Relocator
2804 @subsection Allocating and Freeing Relocatable Blocks
2807 In the descriptions below, @var{handleptr} designates the address of the
2808 handle. All the functions are declared in @file{malloc.h}; all are GNU
2813 @c @deftypefun {void *} r_alloc (void **@var{handleptr}, size_t @var{size})
2814 This function allocates a relocatable block of size @var{size}. It
2815 stores the block's address in @code{*@var{handleptr}} and returns
2816 a non-null pointer to indicate success.
2818 If @code{r_alloc} can't get the space needed, it stores a null pointer
2819 in @code{*@var{handleptr}}, and returns a null pointer.
2824 @c @deftypefun void r_alloc_free (void **@var{handleptr})
2825 This function is the way to free a relocatable block. It frees the
2826 block that @code{*@var{handleptr}} points to, and stores a null pointer
2827 in @code{*@var{handleptr}} to show it doesn't point to an allocated
2833 @c @deftypefun {void *} r_re_alloc (void **@var{handleptr}, size_t @var{size})
2834 The function @code{r_re_alloc} adjusts the size of the block that
2835 @code{*@var{handleptr}} points to, making it @var{size} bytes long. It
2836 stores the address of the resized block in @code{*@var{handleptr}} and
2837 returns a non-null pointer to indicate success.
2839 If enough memory is not available, this function returns a null pointer
2840 and does not modify @code{*@var{handleptr}}.
2848 @comment No longer available...
2850 @comment @node Memory Warnings
2851 @comment @section Memory Usage Warnings
2852 @comment @cindex memory usage warnings
2853 @comment @cindex warnings of memory almost full
2856 You can ask for warnings as the program approaches running out of memory
2857 space, by calling @code{memory_warnings}. This tells @code{malloc} to
2858 check memory usage every time it asks for more memory from the operating
2859 system. This is a GNU extension declared in @file{malloc.h}.
2863 @comment @deftypefun void memory_warnings (void *@var{start}, void (*@var{warn-func}) (const char *))
2864 Call this function to request warnings for nearing exhaustion of virtual
2867 The argument @var{start} says where data space begins, in memory. The
2868 allocator compares this against the last address used and against the
2869 limit of data space, to determine the fraction of available memory in
2870 use. If you supply zero for @var{start}, then a default value is used
2871 which is right in most circumstances.
2873 For @var{warn-func}, supply a function that @code{malloc} can call to
2874 warn you. It is called with a string (a warning message) as argument.
2875 Normally it ought to display the string for the user to read.
2878 The warnings come when memory becomes 75% full, when it becomes 85%
2879 full, and when it becomes 95% full. Above 95% you get another warning
2880 each time memory usage increases.