17. Low-Level Allocation

17.1 Basic Heap Allocation

17.2 Stack Allocation

17.3 Dynamic Arrays

The Dynarr type implements a dynamic array, which is similar to a standard C array but has no fixed limit on the number of elements it can contain. Dynamic arrays can hold elements of any type, and when you add a new element, the array automatically resizes itself if it isn’t big enough. Dynarrs are extensively used in the redisplay mechanism.

A “dynamic array” is a contiguous array of fixed-size elements where there is no upper limit (except available memory) on the number of elements in the array. Because the elements are maintained contiguously, space is used efficiently (no per-element pointers necessary) and random access to a particular element is in constant time. At any one point, the block of memory that holds the array has an upper limit; if this limit is exceeded, the memory is realloc()ed into a new array that is twice as big. Assuming that the time to grow the array is on the order of the new size of the array block, this scheme has a provably constant amortized time (i.e. average time over all additions).

When you add elements or retrieve elements, pointers are used. Note that the element itself (of whatever size it is), and not the pointer to it, is stored in the array; thus you do not have to allocate any heap memory on your own. Also, returned pointers are only guaranteed to be valid until the next operation that changes the length of the array.

This is a container object. Declare a dynamic array of a specific type as follows:

typedef struct { Dynarr_declare (mytype); } mytype_dynarr;

Use the following functions/macros:

void *Dynarr_new(type)
   [MACRO] Create a new dynamic-array object, with each element of the
   specified type.  The return value is cast to (type##_dynarr).
   This requires following the convention that types are declared in
   such a way that this type concatenation works.  In particular, TYPE
   must be a symbol, not an arbitrary C type.

Dynarr_add(d, el)
   [MACRO] Add an element to the end of a dynamic array.  EL is a pointer
   to the element; the element itself is stored in the array, however.
   No function call is performed unless the array needs to be resized.

Dynarr_add_many(d, base, len)
   [MACRO] Add LEN elements to the end of the dynamic array.  The elements
   should be contiguous in memory, starting at BASE.  If BASE if NULL,
   just make space for the elements; don't actually add them.

Dynarr_insert_many_at_start(d, base, len)
   [MACRO] Append LEN elements to the beginning of the dynamic array.
   The elements should be contiguous in memory, starting at BASE.
   If BASE if NULL, just make space for the elements; don't actually
   add them.

Dynarr_insert_many(d, base, len, start)
   Insert LEN elements to the dynamic array starting at position
   START.  The elements should be contiguous in memory, starting at BASE.
   If BASE if NULL, just make space for the elements; don't actually
   add them.

Dynarr_delete(d, i)
   [MACRO] Delete an element from the dynamic array at position I.

Dynarr_delete_many(d, start, len)
   Delete LEN elements from the dynamic array starting at position
   START.

Dynarr_delete_by_pointer(d, p)
   [MACRO] Delete an element from the dynamic array at pointer P,
   which must point within the block of memory that stores the data.
   P should be obtained using Dynarr_atp().

int Dynarr_length(d)
   [MACRO] Return the number of elements currently in a dynamic array.

int Dynarr_largest(d)
   [MACRO] Return the maximum value that Dynarr_length(d) would
   ever have returned.

type Dynarr_at(d, i)
   [MACRO] Return the element at the specified index (no bounds checking
   done on the index).  The element itself is returned, not a pointer
   to it.

type *Dynarr_atp(d, i)
   [MACRO] Return a pointer to the element at the specified index (no
   bounds checking done on the index).  The pointer may not be valid
   after an element is added to or removed from the array.

Dynarr_reset(d)
   [MACRO] Reset the length of a dynamic array to 0.

Dynarr_free(d)
   Destroy a dynamic array and the memory allocated to it.

Use the following global variable:

   Dynarr_min_size
      Minimum allowable size for a dynamic array when it is resized.

17.4 Allocation by Blocks

The Blocktype type efficiently manages the allocation of fixed-size blocks by minimizing the number of times that malloc() and free() are called. It allocates memory in large chunks, subdivides the chunks into blocks of the proper size, and returns the blocks as requested. When blocks are freed, they are placed onto a linked list, so they can be efficiently reused. This data type is not much used in XEmacs currently, because it’s a fairly new addition.

A “block-type object” is used to efficiently allocate and free blocks of a particular size. Freed blocks are remembered in a free list and are reused as necessary to allocate new blocks, so as to avoid as much as possible making calls to malloc() and free().

This is a container object. Declare a block-type object of a specific type as follows:

struct mytype_blocktype { Blocktype_declare (mytype); };

Use the following functions/macros:

structype *Blocktype_new(structype)
   [MACRO] Create a new block-type object of the specified type.
   The argument to this call should be the type of object to be
   created, e.g. foobar_blocktype.
type *Blocktype_alloc(b)
   [MACRO] Allocate a block of the proper type for the specified
   block-type object and return a pointer to it.
Blocktype_free(b, block)
   Free a block of the type corresponding to the specified block-type
   object.
Blocktype_delete(b)
   Destroy a block-type object and the memory allocated to it.

17.5 Modules for Allocation

‘alloca.c’
‘free-hook.c’
‘getpagesize.h’
‘gmalloc.c’
‘malloc.c’
‘mem-limits.h’
‘ralloc.c’
‘vm-limit.c’

These handle basic C allocation of memory. ‘alloca.c’ is an emulation of the stack allocation function alloca() on machines that lack this. (XEmacs makes extensive use of alloca() in its code.)

‘gmalloc.c’ and ‘malloc.c’ are two implementations of the standard C functions malloc(), realloc() and free(). They are often used in place of the standard system-provided malloc() because they usually provide a much faster implementation, at the expense of additional memory use. ‘gmalloc.c’ is a newer implementation that is much more memory-efficient for large allocations than ‘malloc.c’, and should always be preferred if it works. (At one point, ‘gmalloc.c’ didn’t work on some systems where ‘malloc.c’ worked; but this should be fixed now.)

‘ralloc.c’ is the relocating allocator. It provides functions similar to malloc(), realloc() and free() that allocate memory that can be dynamically relocated in memory. The advantage of this is that allocated memory can be shuffled around to place all the free memory at the end of the heap, and the heap can then be shrunk, releasing the memory back to the operating system. The use of this can be controlled with the configure option --rel-alloc; if enabled, memory allocated for buffers will be relocatable, so that if a very large file is visited and the buffer is later killed, the memory can be released to the operating system. (The disadvantage of this mechanism is that it can be very slow. On systems with the mmap() system call, the XEmacs version of ‘ralloc.c’ uses this to move memory around without actually having to block-copy it, which can speed things up; but it can still cause noticeable performance degradation.)

On Linux systems using ‘glibc 2’, these strategies are built in to the so-called “Doug Lea malloc.” See, for example, Doug Lea’s home page, especially “A Memory Allocator”. The source file, ‘malloc.c’ (available at the same place) is copiously (and usefully!) commented. Wolfram Gloger’s home page may also be useful.

‘free-hook.c’ contains some debugging functions for checking for invalid arguments to free().

‘vm-limit.c’ contains some functions that warn the user when memory is getting low. These are callback functions that are called by ‘gmalloc.c’ and ‘malloc.c’ at appropriate times.

‘getpagesize.h’ provides a uniform interface for retrieving the size of a page in virtual memory. ‘mem-limits.h’ provides a uniform interface for retrieving the total amount of available virtual memory. Both are similar in spirit to the ‘sys*.h’ files described in section J, below.

‘blocktype.c’
‘blocktype.h’
‘dynarr.c’

These implement a couple of basic C data types to facilitate memory allocation.

This document was generated by Aidan Kehoe on December 27, 2016 using texi2html 1.82.