Heap Management

Heap management represents the way SYSLINUX handles the dynamic memory allocation requests of modules through malloc(). This page describes how SYSLINUX implements a fast and efficient heap manager for its modules.

Data Structures

After the module is loaded, the space between the module text + data segments and the SYSLINUX labels (stored at the end of physical RAM) remains to be shared between the module stack and heap (as can be seen from the memory map). The size of the stack is specified as the compile time constant __stack_size. In its current implementation, SYSLINUX leaves for the heap at least half of the total available space, regardless of the value of __stack_size. This space is organized as a memory arena, in the following manner:

• At any given moment, the entire memory arena is composed out of consecutive variable-size blocks of data, each block starting with a header structure, called the arena header, and continuing with user data until its end.
• Each block of data can contain either free data, or taken up data (allocated with malloc()). When the module is loaded, there is only a single big block of data covering the entire heap, and containing free space.
• The arena headers keep pointers to other headers, thus organizing themselves in double-linked lists. Therefore, memory management reduces to the traversal of these lists (whose organization will be explained briefly), splitting free blocks and merging adjacent free space.

At the base of memory arena functionality is the struct arena_header structure, present at the start of each block of data:

struct arena_header {
  size_t type;
  size_t size;                  /* Also gives the location of the next entry */
  struct free_arena_header *next, *prev;
};

The structure fields mean as follows:

• type encodes the type of the structure, and can have one of these values:
  • ARENA_TYPE_HEAD is the type of the statically allocated head of the linked lists. This header doesn't have any associated block (it does not reside in the heap, but in the .data section of the module), and is used only as a sentinel in the linked list.
  • ARENA_TYPE_FREE is the type associated with a free block of memory. This type also mean that after the struct arena_header fields follow more fields pertaining to free space management. Thus, the header is part of a larger header, called struct free_arena_header.
  • ARENA_TYPE_USED marks an allocated (used) block of memory.
• size is the size of the block of data (including the header information).
• next and prev represent pointers to the adjacent blocks in a linked list that contain all the blocks in the memory arena. The order of the blocks in this list match the order of the blocks in the heap.

As described earlier, free blocks have a larger header structure, called struct free_arena_header, with the following content:

struct free_arena_header {
  struct arena_header a;
  struct free_arena_header *next_free, *prev_free;
};

Thus, in addition to the standard header fields, the free block headers contain pointers to other free blocks, thus composing a list of all the free space at any given time. In order to allocate new memory, malloc() would only need to traverse this list and find the most suitable block of memory. Note that unlike the list of all blocks, the order of the free blocks in the free blocks list does not necessarily match their order in memory.

In conclusion, blocks of free or used data, with headers organized as two double linked lists are the data structure behind the SYSLINUX memory allocator.

Operations

Memory Allocation

The implementation of malloc() is straightforward:

1. The list of free blocks is traversed, until a block that would fit both the requested size plus the size of the block header is found. If no such block is found, malloc() returns NULL. Note that there might be sufficient total free memory available for the request (dispersed throughout the free blocks), but if the requested amount is not found in a single continuous block, the allocation fails.
2. If the requested size is smaller than the size of the block, it can be split into two blocks, one containing the allocation and the other one containing the remaining free space. Note that this is only possible if the size of the second block is large enough to fit an arena header structure, in order to be tracked by the memory management. Otherwise, no splitting is done (and the allocation is slightly larger than requested, but not larger than sizeof(struct free_arena_header)).
3. The header of the allocated block (and the one of the new free block resulted from splitting, when applicable), is modified accordingly.
4. The return value of malloc() is a pointer to the memory area right after the block arena header.

Memory Release

Memory release is even simpler. When called, the free() function performs as follows:

1. Checks for a valid (non-null) pointer, then obtains the base address of the block containing the user data, by subtracting the size of a struct arena_struct.
2. If the previous block in memory is also free, the two blocks are merged together by expanding the size of the previous block. Otherwise, the block is marked as free and added to the list of free blocks.
3. If the next block in memory is also free, the two blocks are merged toghether by expanding the size of the current block to eat up the next block, and the next block is also removed from the list of free blocks. The net result of the last two steps is that there will never be free consecutive blocks of memory in the heap, thus the size of the free blocks list is kept to a minimum, and allocation is faster.

See also

• SYSLINUX memory map

This page is known to be best accurate as of SYSLINUX version 3.70. Minor modifications may have occurred in subsequent versions, but the general idea presented in this page remains the same.