Allocating objects from object caches

A.k.a. Ariadne doesn't like malloc(2), because of potential issues with fragmentation, compaction, limiting memory usage, syscall filtering, not-invented-here and wouldn't-this-be-cool-to-use-from-a-signal-handler (even though that is not -- yet -- supported, it should be doable).

An object cache is a pool of mostly pre-allocated memory, of limited size, divided into little chunks of constant (for a single cache) size, from which one can allocate objects and give unused individuals back.

#include <sHT/resource.h>

A cache is created with sHT_alloc_cache and freed with sHT_free_cache. Objects are allocated from a cache with sHT_alloc and freed with sHT_free.

These functions are (or will be) defined in worker/alloc.c.

The following subsection described how this might eventually be implemented. For now, however, the code only does a single mmap(2).

Structure

An object cache's memory is divided into the index, page list, the freelist, all objects and padding, which are, except for the last and first, allocated consecutively.

(More typical would be to intermix freelists and objects, which would allow changing the maximum size at run time. But if you really want to do that, you could also just migrate all agents into a new worker. That's the whole point of sHT (or rather, a single point).)

(TODO: improve migration performance by migrate objects by remapping object pages, instead of copying)

Note the use of the word 'consecutively', instead of contiguously. An object cache may be spread over multiple, not necessarily adjectant pages.

Page allocation

We try to use huge pages when possible, to reduce pressure on the TLB, but we do not insist.

Some pools are very small, so 4KiB may suffice on x86-64 if that's all we need. Some are rather large, e.g. 10 million IO buffers of 512 bytes each requires 5GiB of memory. Another variable, or rather a constraint, is that virtual memory may become fragmented.

Some object caches may grow over time, up to a predetermined limit.

To accommodate for variations in size, the preferred page size is taken to encompass the whole structure. To deal with fragmentation, progressively smaller page sizes are chosen, so the page size is variable. Not all pages are allocated from the beginning, so some may be null.

Freelists

A freelist is a structure that keeps that of objects that are not used anywhere and can therefore be returned by an allocation routine, provided it is then removed from the list.

It is conceptually a stack of pointers. The pointers are real, but the stack may be split over multiple pages.

Index

The index contains statistics, the element size of the object, a pointer into the freelist and a list of all pages (possibly split in two halves: allocated and non-allocated.) It is contiguous.

The number of pages may be variable due to memory fragmentation. To avoid complexity, the page list, however, allows for the maximal number of pages (taking in account restrictions imposed by object sizes). (TODO: there is an oppurtunity for reducing memory usage for the pre-allocated half.)

The index starts on the first page, and must fit. (On 64-bit, a 1MiB page list can refer to 65536 pages. If these are each 1MiB in size, 64GiB can be used for other things. Seems reasonable.)

Position of these structures within pages

index, freelist and objects, in that order.

No C-object crosses a page boundary. The first C-object in a page starts at index 0. Other C-objects are placed after the previous, minimising distance but still having a preferred alignment, if it fits within the current page. If it doesn't fit, it starts on the next page, at index 0.

The code can determine the preferred alignment of each allocated object with __alignof__(max_align_t) when using GCC. (TODO: cache lines, let the last element end at the end of the page?)

Legal

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

memory-allocation.md 4.5 KB Permanentný odkaz História Raw