Gated uses the operating system memory management functionality for some situations. However, to optimize memory usage for the most common case of allocating control blocks, Gated provides its own memory management routines. The memory management code is part of the task module probably for historical reasons.
Protocol modules (and other support modules as well) allocate memory in Gated in two distinctly different ways. For dynamic allocation of fixed size descriptors, Gated uses the memory allocator described below. For variable sized blocks (e.g. the BGP attribute descriptor structure as_path), Gated uses malloc(). (Actually, Gated optimizes this latter allocation as well, using malloc() only for the uncommon case and allocating fixed sized blocks for the common case).
The fixed block allocation model is optimized for the case when a module repeatedly requests the same sized block. The module first contacts the memory manager to obtain a descriptor block (called a task_block, see below) which indicates the size of blocks it will request in the future. To later allocate a block, it calls the memory manager with this descriptor block; the memory manager returns a pointer to the appropriately sized block.
The fixed block allocator has two main data structures, a task_block and a task_size_block. The task_block, which is the descriptor block referred to above, contains size of each allocation request and some bookkeeping data.
A task_size_block is a descriptor for a block allocation of a particular size. It contains a linked-list of task_blocks for blocks of that size. In addition, it contains a pointer to a free-list of blocks of that particular size.
Protocol modules register with the memory manager by calling task_block_init() and specifying the size of allocations it expects to make with this registration.
Macros task_block_alloc() and task_block_free() respectively allocate and free a block out of the requested size. The memory allocation strategy is explained below.
Some protocol modules allocate data in units of pages directly. For example, the task module allocates its send and receive buffers this way. These modules may explicitly free these pages by calling task_block_reclaim(). These pages go into a global free list, out which the memory manager may allocate data for its block allocator.
The internals of the memory manager can be explained with the aid of the following example. Suppose a protocol module registers with the memory manager for a block allocation of 16 bytes. The memory manager returns to the protocol module a task_block descriptor, after linking that descriptor to the task_size_block descriptor for 16 byte blocks.
The latter descriptor maintains a linked list of free 16 byte blocks. Freed blocks are linked in a singly-linked list (even though the pointer to a free block is cast into the head of a doubly-linked list, only the forward pointer is used in the free list). Whenever the free list for a task_size_block is empty, the memory manager allocates a page, then carves up the page into a linked list of appropriately sized blocks (the fragment of the page that doesn't fit into one block, called a runt, is linked into a free list corresponding to its size).
Allocations are done out of this free list. When a protocol module frees up a block, the freed block goes back on the free list.