summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMartin Mares <mj@ucw.cz>2000-06-05 13:41:41 +0200
committerMartin Mares <mj@ucw.cz>2000-06-05 13:41:41 +0200
commit5cc1e1f805934952f38ceb2ca6947c6d2e704937 (patch)
treeea409d5772742e5eb15e781dff397c2e51b665b5
parent9238b06a2c6faac8b16e990821c91affde4072c4 (diff)
downloadbird-5cc1e1f805934952f38ceb2ca6947c6d2e704937.tar
bird-5cc1e1f805934952f38ceb2ca6947c6d2e704937.zip
Documented memory resources.
-rw-r--r--lib/Doc2
-rw-r--r--lib/mempool.c62
-rw-r--r--lib/resource.c116
-rw-r--r--lib/resource.sgml50
-rw-r--r--lib/slab.c40
5 files changed, 265 insertions, 5 deletions
diff --git a/lib/Doc b/lib/Doc
index a57516e..6367cd7 100644
--- a/lib/Doc
+++ b/lib/Doc
@@ -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>
diff --git a/lib/slab.c b/lib/slab.c
index 75a55c6..736dcb8 100644
--- a/lib/slab.c
+++ b/lib/slab.c
@@ -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)
{