diff options
| -rw-r--r-- | lib/Doc | 2 | ||||
| -rw-r--r-- | lib/mempool.c | 62 | ||||
| -rw-r--r-- | lib/resource.c | 116 | ||||
| -rw-r--r-- | lib/resource.sgml | 50 | ||||
| -rw-r--r-- | lib/slab.c | 40 |
5 files changed, 265 insertions, 5 deletions
@@ -2,7 +2,7 @@ H Library functions S ip.c ipv4.c ipv6.c S lists.c S checksum.c bitops.c patmatch.c printf.c xmalloc.c -H Resources +D resource.sgml S resource.c S mempool.c S slab.c diff --git a/lib/mempool.c b/lib/mempool.c index f21b305..a27f2f4 100644 --- a/lib/mempool.c +++ b/lib/mempool.c @@ -1,11 +1,23 @@ /* * BIRD Resource Manager -- Memory Pools * - * (c) 1998--1999 Martin Mares <mj@ucw.cz> + * (c) 1998--2000 Martin Mares <mj@ucw.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ +/** + * DOC: Linear memory pools + * + * Linear memory pools are collections of memory blocks which + * support very fast allocation of new blocks, but are able to free only + * the whole collection at once. + * + * Example: Each configuration is described by a complex system of structures, + * linked lists and function trees which are all allocated from a single linear + * pool, thus they can be freed at once when the configuration is no longer used. + */ + #include <stdlib.h> #include "nest/bird.h" @@ -38,6 +50,15 @@ static struct resclass lp_class = { lp_lookup }; +/** + * lp_new - create a new linear memory pool + * @p: pool + * @blk: block size + * + * lp_new() creates a new linear memory pool resource inside the pool @p. + * The linear pool consists of a list of memory chunks of size at least + * @blk. + */ linpool *lp_new(pool *p, unsigned blk) { @@ -52,6 +73,20 @@ linpool return m; } +/** + * lp_alloc - allocate memory from a &linpool + * @m: linear memory pool + * @size: amount of memory + * + * lp_alloc() allocates @size bytes of memory from a &linpool @m + * and it returns a pointer to the allocated memory. + * + * It works by trying to find free space in the last memory chunk + * associated with the &linpool and creating a new chunk of the standard + * size (as specified during lp_new()) if the free space is too small + * to satisfy the allocation. If @size is too large to fit in a standard + * size chunk, an "overflow" chunk is created for it instead. + */ void * lp_alloc(linpool *m, unsigned size) { @@ -100,6 +135,16 @@ lp_alloc(linpool *m, unsigned size) } } +/** + * lp_allocu - allocate unaligned memory from a &linpool + * @m: linear memory pool + * @size: amount of memory + * + * lp_allocu() allocates @size bytes of memory from a &linpool @m + * and it returns a pointer to the allocated memory. It doesn't + * attempt to align the memory block, giving a very efficient way + * how to allocate strings without any space overhead. + */ void * lp_allocu(linpool *m, unsigned size) { @@ -114,6 +159,14 @@ lp_allocu(linpool *m, unsigned size) return lp_alloc(m, size); } +/** + * lp_allocz - allocate cleared memory from a &linpool + * @m: linear memory pool + * @size: amount of memory + * + * This function is identical to lp_alloc() except that it + * clears the allocated memory block. + */ void * lp_allocz(linpool *m, unsigned size) { @@ -123,6 +176,13 @@ lp_allocz(linpool *m, unsigned size) return z; } +/** + * lp_flush - flush a linear memory pool + * @m: linear memory pool + * + * This function frees the whole contents of the given &linpool @m, + * but leaves the pool itself. + */ void lp_flush(linpool *m) { diff --git a/lib/resource.c b/lib/resource.c index 3cfd065..a51e3ca 100644 --- a/lib/resource.c +++ b/lib/resource.c @@ -1,7 +1,7 @@ /* * BIRD Resource Manager * - * (c) 1998 Martin Mares <mj@ucw.cz> + * (c) 1998--2000 Martin Mares <mj@ucw.cz> * * Can be freely distributed and used under the terms of the GNU GPL. */ @@ -13,6 +13,20 @@ #include "lib/resource.h" #include "lib/string.h" +/** + * DOC: Resource pools + * + * Resource pools (&pool) are just containers holding a list of + * other resources. Freeing a pool causes all the listed resources + * to be freed as well. Each existing &resource is linked to some pool + * except for a root pool which isn't linked anywhere, so all the + * resources form a tree structure with internal nodes corresponding + * to pools and leaves being the other resources. + * + * Example: Almost all modules of BIRD have their private pool which + * is freed upon shutdown of the module. + */ + struct pool { resource r; list inside; @@ -35,6 +49,14 @@ pool root_pool; static int indent; +/** + * rp_new - create a resource pool + * @p: parent pool + * @name: pool name (to be included in debugging dumps) + * + * rp_new() creates a new resource pool inside the specified + * parent pool. + */ pool * rp_new(pool *p, char *name) { @@ -84,6 +106,16 @@ pool_lookup(resource *P, unsigned long a) return NULL; } +/** + * rfree - free a resource + * @res: resource + * + * rfree() frees the given resource and all information associated + * with it. In case it's a resource pool, it also frees all the objects + * living inside the pool. + * + * It works by calling a class-specific freeing function. + */ void rfree(void *res) { @@ -98,6 +130,15 @@ rfree(void *res) } } +/** + * rdump - dump a resource + * @res: resource + * + * This function prints out all available information about the given + * resource to the debugging output. + * + * It works by calling a class-specific dump function. + */ void rdump(void *res) { @@ -115,6 +156,16 @@ rdump(void *res) debug("NULL\n"); } +/** + * ralloc - create a resource + * @p: pool to create the resource in + * @c: class of the new resource + * + * This function is called by the resource classes to create a new + * resource of the specified class and link it to the given pool. + * Size of the resource structure is taken from the @size field + * of the &resclass. + */ void * ralloc(pool *p, struct resclass *c) { @@ -125,6 +176,17 @@ ralloc(pool *p, struct resclass *c) return r; } +/** + * rlookup - look up a memory location + * @a: memory address + * + * This function examines all existing resources to see whether + * the address @a is inside any resource. It's used for debugging + * purposes only. + * + * It works by calling a class-specific lookup function for each + * resource. + */ void rlookup(unsigned long a) { @@ -137,6 +199,13 @@ rlookup(unsigned long a) debug("Not found.\n"); } +/** + * resource_init - initialize the resource manager + * + * This function is called during BIRD startup. It initializes + * all data structures of the resource manager and creates the + * root pool. + */ void resource_init(void) { @@ -145,8 +214,17 @@ resource_init(void) init_list(&root_pool.inside); } -/* - * Memory blocks. +/** + * DOC: Memory blocks + * + * Memory blocks are pieces of contiguous allocated memory. + * They are a bit non-standard since they are represented not by a pointer + * to &resource, but by a void pointer to the start of data of the + * memory block. All memory block functions know how to locate the header + * given the data pointer. + * + * Example: All "unique" data structures such as hash tables are allocated + * as memory blocks. */ struct mblock { @@ -184,6 +262,19 @@ static struct resclass mb_class = { mbl_lookup }; +/** + * mb_alloc - allocate a memory block + * @p: pool + * @size: size of the block + * + * mb_alloc() allocates memory of a given size and creates + * a memory block resource representing this memory chunk + * in the pool @p. + * + * Please note that mb_alloc() returns a pointer to the memory + * chunk, not to the resource, hence you have to free it using + * mb_free(), not rfree(). + */ void * mb_alloc(pool *p, unsigned size) { @@ -195,6 +286,19 @@ mb_alloc(pool *p, unsigned size) return b->data; } +/** + * mb_allocz - allocate and clear a memory block + * @p: pool + * @size: size of the block + * + * mb_allocz() allocates memory of a given size, initializes it to + * zeroes and creates a memory block resource representing this memory + * chunk in the pool @p. + * + * Please note that mb_alloc() returns a pointer to the memory + * chunk, not to the resource, hence you have to free it using + * mb_free(), not rfree(). + */ void * mb_allocz(pool *p, unsigned size) { @@ -203,6 +307,12 @@ mb_allocz(pool *p, unsigned size) return x; } +/** + * mb_free - free a memory block + * @m: memory block + * + * mb_free() frees all memory associated with the block @m. + */ void mb_free(void *m) { diff --git a/lib/resource.sgml b/lib/resource.sgml new file mode 100644 index 0000000..4123dd6 --- /dev/null +++ b/lib/resource.sgml @@ -0,0 +1,50 @@ +<!-- + BIRD Programmer's Guide: Resources + + (c) 2000 Martin Mares <mj@ucw.cz> +--> + +<chapt>Resources + +<sect>Introduction + +<p>Most large software projects implemented in classical procedural +programming languages usually end up with lots of code taking care +of resource allocation and deallocation. Bugs in such code are often +very difficult to find, because they cause only `resource leakage', +that is keeping a lot of memory and other resources which nobody +references to. + +<p>We've tried to solve this problem by employing a resource tracking +system which keeps track of all the resources allocated by all the +modules of BIRD, deallocates everything automatically when a module +shuts down and it's is able to print out the list of resources and +the corresponding modules they are allocated by. + +<p>Each allocated resource (and from now we'll speak about allocated +resources only) is represented by a structure starting with a standard +header (struct <struct/resource/) consisting of a list node (resources are +often linked to various lists) and a pointer to <struct/resclass/ -- a resource +class structure pointing to functions implementing generic resource +operations (such as freeing of the resource) for the particular resource +type. + +<p>There exist the following types of resources: + +<itemize> +<item><it/Resource pools/ (<struct/pool/) +<item><it/Memory blocks/ +<item><it/Linear memory pools/ (<struct/linpool/) +<item><it/Slabs/ (<struct/slab/) +<item><it/Sockets/ (<struct/socket/) +<item><it/Events/ (<struct/event/) +<!-- + are there to keep track of deferred execution. + Since BIRD is single-threaded, it requires long lasting tasks to be split to smaller + parts, so that no module can monopolize the CPU. To split such a task, just create + an <struct/event/ resource, point it to the function you want to have called and call <func/ev_schedule()/ + to ask the core to run the event when nothing more important will require attention. + The actual implementation is system dependent. +--> +<item><it/Timers/ (<struct/timer/) +</itemize> @@ -8,6 +8,23 @@ * Can be freely distributed and used under the terms of the GNU GPL. */ +/** + * DOC: Slabs + * + * Slabs are collections of memory blocks of a fixed size. + * They support very fast allocation and freeing of such blocks, prevent memory + * fragmentation and optimize L2 cache usage. Slabs have been invented by Jeff Bonwick + * and published in USENIX proceedings as `The Slab Allocator: An Object-Caching Kernel + * Memory Allocator'. Our implementation follows this article except that we don't use + * constructors and destructors. + * + * When the |DEBUGGING| switch is turned on, we automatically fill all + * newly allocated and freed blocks with a special patterns to make detection + * of use of uninitialized or already freed memory easier. + * + * Example: Nodes of a FIB are allocated from a Slab. + */ + #include <stdlib.h> #include "nest/bird.h" @@ -139,6 +156,14 @@ struct sl_alignment { /* Magic structure for testing of alignment */ int x[0]; }; +/** + * sl_new - create a new Slab + * @p: resource pool + * @size: block size + * + * This function creates a new Slab resource from which + * objects of size @size can be allocated. + */ slab * sl_new(pool *p, unsigned size) { @@ -183,6 +208,13 @@ sl_new_head(slab *s) return h; } +/** + * sl_alloc - allocate an object from Slab + * @s: slab + * + * sl_alloc() allocates space for a single object from the + * Slab and returns a pointer to the object. + */ void * sl_alloc(slab *s) { @@ -223,6 +255,14 @@ no_partial: goto okay; } +/** + * sl_free - return a free object back to a Slab + * @s: slab + * @oo: object returned by sl_alloc() + * + * This function frees memory associated with the object @oo + * and returns it back to the Slab @s. + */ void sl_free(slab *s, void *oo) { |