diff options
Diffstat (limited to 'doc/threads/04_memory_management.md')
-rw-r--r-- | doc/threads/04_memory_management.md | 223 |
1 files changed, 223 insertions, 0 deletions
diff --git a/doc/threads/04_memory_management.md b/doc/threads/04_memory_management.md new file mode 100644 index 00000000..24ef89d3 --- /dev/null +++ b/doc/threads/04_memory_management.md @@ -0,0 +1,223 @@ +# BIRD Journey to Threads. Chapter 4: Memory and other resource management. + +BIRD is mostly a large specialized database engine, storing mega/gigabytes of +Internet routing data in memory. To keep accounts of every byte of allocated data, +BIRD has its own resource management system which must be adapted to the +multithreaded environment. The resource system has not changed much, yet it +deserves a short chapter. + +BIRD is a fast, robust and memory-efficient routing daemon designed and +implemented at the end of 20th century. We're doing a significant amount of +BIRD's internal structure changes to make it run in multiple threads in parallel. + +## Resources + +Inside BIRD, (almost) every piece of allocated memory is a resource. To achieve this, +every such memory block includes a generic `struct resource` header. The node +is enlisted inside a linked list of a *resource pool* (see below), the class +pointer defines basic operations done on resources. + +``` +typedef struct resource { + node n; /* Inside resource pool */ + struct resclass *class; /* Resource class */ +} resource; + +struct resclass { + char *name; /* Resource class name */ + unsigned size; /* Standard size of single resource */ + void (*free)(resource *); /* Freeing function */ + void (*dump)(resource *); /* Dump to debug output */ + resource *(*lookup)(resource *, unsigned long); /* Look up address (only for debugging) */ + struct resmem (*memsize)(resource *); /* Return size of memory used by the resource, may be NULL */ +}; + +void *ralloc(pool *, struct resclass *); +``` + +Resource cycle begins with an allocation of a resource. To do that, you should call `ralloc()`, +passing the parent pool and the appropriate resource class as arguments. BIRD +allocates a memory block of size given by the given class member `size`. +Beginning of the block is reserved for `struct resource` itself and initialized +by the given arguments. Therefore, you may sometimes see an idiom where a structure +has a first member `struct resource r;`, indicating that this item should be +allocated as a resource. + +The counterpart is resource freeing. This may be implicit (by resource pool +freeing) or explicit (by `rfree()`). In both cases, the `free()` function of +the appropriate class is called to cleanup the resource before final freeing. + +To account for `dump` and `memsize` calls, there are CLI commands `dump +resources` and `show memory`, using these to dump resources or show memory +usage as perceived by BIRD. + +The last, `lookup`, is quite an obsolete way to identify a specific pointer +from a debug interface. You may call `rlookup(pointer)` and BIRD should dump +that resource to the debug output. This mechanism is probably incomplete as no +developer uses it actively for debugging. + +Resources can be also moved between pools by `rmove` when needed. + +## Resource pools + +The first internal resource class is a recursive resource – a resource pool. In +the singlethreaded version, this is just a simple structure: + +``` +struct pool { + resource r; + list inside; + struct birdloop *loop; /* In multithreaded version only */ + const char *name; +}; +``` + +Resource pools are used for grouping resources together. There are pools everywhere +and it is a common idiom inside BIRD to just `rfree` the appropriate pool when +e.g. a protocol or table is going down. Everything left there is cleaned up. + +There are anyway several classes which must be freed with care. In the +singlethreaded version, the *slab* allocator (see below) must be empty before +it may be freed and this is kept to the multithreaded version while other +restrictions have been added. + +There is also a global pool, `root_pool`, containing every single resource BIRD +knows about, either directly or via another resource pool. + +### Thread safety in resource pools + +In the multithreaded version, every resource pool is bound to a specific IO +loop and therefore includes an IO loop pointer. This is important for allocations +as the resource list inside the pool is thread-unsafe. All pool operations +therefore require the IO loop to be entered to do anything with them, if possible. +(In case of `rfree`, the pool data structure is not accessed at all so no +assert is possible. We're currently relying on the caller to ensure proper locking. +In future, this may change.) + +Each IO loop also has its base resource pool for its allocations. All pools +inside the IO loop pool must belong to the same loop or to a loop with a +subordinate lock (see the previous chapter for lock ordering). If there is a +need for multiple IO loops to access one shared data structure, it must be +locked by another lock and allocated in such a way that is independent on these +accessor loops. + +The pool structure should follow the locking order. Any pool should belong to +either the same loop as its parent or its loop lock should be after its parent +loop lock in the locking order. This is not enforced explicitly, yet it is +virtually impossible to write some working code violating this recommendation. + +### Resource pools in the wilderness + +Root pool contains (among others): + +* route attributes and sources +* routing tables +* protocols +* interfaces +* configuration data + +Each table has its IO loop and uses the loop base pool for allocations. +The same holds for protocols. Each protocol has its pool; it is either its IO +loop base pool or an ordinary pool bound to main loop. + +## Memory allocators + +BIRD stores data in memory blocks allocated by several allocators. There are 3 +of them: simple memory blocks, linear pools and slabs. + +### Simple memory block + +When just a chunk of memory is needed, `mb_alloc()` or `mb_allocz()` is used +to get it. The first with `malloc()` semantics, the other is also zeroed. +There is also `mb_realloc()` available, `mb_free()` to explicitly free such a +memory and `mb_move()` to move that memory to another pool. + +Simple memory blocks consume a fixed amount of overhead memory (32 bytes on +systems with 64-bit pointers) so they are suitable mostly for big chunks, +taking advantage of the default *stdlib* allocator which is used by this +allocation strategy. There are anyway some parts of BIRD (in all versions) +where this allocator is used for little blocks. This will be fixed some day. + +### Linear pools + +Sometimes, memory is allocated temporarily. When the data may just sit on +stack, we put it there. Anyway, many tasks need more structured execution where +stack allocation is incovenient or even impossible (e.g. when callbacks from +parsers are involved). For such a case, a *linpool* is the best choice. + +This data structure allocates memory blocks of requested size with negligible +overhead in functions `lp_alloc()` (uninitialized) or `lp_allocz()` (zeroed). +There is anyway no `realloc` and no `free` call; to have a larger chunk, you +need to allocate another block. All this memory is freed at once by `lp_flush()` +when it is no longer needed. + +You may see linpools in parsers (BGP, Linux netlink, config) or in filters. + +In the multithreaded version, linpools have received an update, allocating +memory pages directly by `mmap()` instead of calling `malloc()`. More on memory +pages below. + +### Slabs + +To allocate lots of same-sized objects, a [slab allocator](https://en.wikipedia.org/wiki/Slab_allocation) +is an ideal choice. In versions until 2.0.8, our slab allocator used blocks +allocated by `malloc()`, every object included a *slab head* pointer and free objects +were linked into a single-linked list. This led to memory inefficiency and to +contra-intuitive behavior where a use-after-free bug could do lots of damage +before finally crashing. + +Versions from 2.0.9, and also all the multithreaded versions, are coming with +slabs using directly allocated memory pages and usage bitmaps instead of +single-linking the free objects. This approach however relies on the fact that +pointers returned by `mmap()` are always divisible by page size. Freeing of a +slab object involves zeroing (mostly) 13 least significant bits of its pointer +to get the page pointer where the slab head resides. + +This update helps with memory consumption by about 5% compared to previous +versions; exact numbers depend on the usage pattern. + +## Raw memory pages + +Until 2.0.8 (incl.), BIRD allocated all memory by `malloc()`. This method is +suitable for lots of use cases, yet when gigabytes of memory should be +allocated by little pieces, BIRD uses its internal allocators to keep track +about everything. This brings some ineffectivity as stdlib allocator has its +own overhead and doesn't allocate aligned memory unless asked for. + +Slabs and linear pools are backed by blocks of memory of kilobyte sizes. As a +typical memory page size is 4 kB, it is a logical step to drop stdlib +allocation from these allocators and to use `mmap()` directly. This however has +some drawbacks, most notably the need of a syscall for every memory mapping and +unmapping. For allocations, this is not much a case and the syscall time is typically +negligible compared to computation time. When freeing memory, this is much +worse as BIRD sometimes frees gigabytes of data in a blink of eye. + +To minimize the needed number of syscalls, there is a per-thread page cache, +keeping pages for future use: + +* When a new page is requested, first the page cache is tried. +* When a page is freed, the per-thread page cache keeps it without telling the kernel. +* When the number of pages in any per-thread page cache leaves a pre-defined range, + a cleanup routine is scheduled to free excessive pages or request more in advance. + +This method gives the multithreaded BIRD not only faster memory management than +ever before but also almost immediate shutdown times as the cleanup routine is +not scheduled on shutdown at all. + +## Other resources + +Some objects are not only a piece of memory; notable items are sockets, owning +the underlying mechanism of I/O, and *object locks*, owning *the right to use a +specific I/O*. This ensures that collisions on e.g. TCP port numbers and +addresses are resolved in a predictable way. + +All these resources should be used with the same locking principles as the +memory blocks. There aren't many checks inside BIRD code to ensure that yet, +nevertheless violating this recommendation may lead to multiple-access issues. + +*It's still a long road to the version 2.1. This series of texts should document +what is needed to be changed, why we do it and how. The +[previous chapter](TODO) +showed the locking system and how the parallel execution is done. +The next chapter will cover a bit more detailed explanation about route sources +and route attributes and how lockless data structures are employed there. Stay tuned!* |