Differences From
Artifact [18509d6a57]:
1 1 # kmem
2 2
3 3 **kmem** is a libk module that contains various functions for memory allocation and deallocation. it uses the **short** naming convention with the glyph `m`.
4 4
5 +kmem allocators can work in several different ways. they can allocate memory directly from the heap (like `kmheapa()` and `kmlina()`), use a header that has already been allocated by another function, or allocate memory only from a pre-allocated pool. linear allocation with pool allocation is particularly useful, as it permits the very rapid allocation and deallocation of lots of objects with only a few adjustments to the heap, and no possibility of fragmentation or need for expensive algorithms like `malloc()` or `kmheapa()`
6 +
5 7 ## module functions
6 8
7 -**kmem** supplies two module-level functions, used to interact with the `kmptr` container type.
9 +kmem supplies two module-level functions, used to interact with the `kmptr` container type.
8 10
9 11 * `kmfree(kmptr) → void` - free, downref, or ignore the pasted object as appropriate
10 12 * `kmshred(kmptr) → void` - free, downref, or ignore the pasted object as appropriate. if deallocating, zero its contents
11 13 * `kmstat(void*) → kmptr` - convenience function to wrap a pointer to a non-managed object in a `kmptr` struct, so it can be passed to functions that accept arbitrary objects. `kmptr p = kmstat(raw)` is equivalent to `kmptr p = { kmkind_none, raw, NULL }`.
12 14 * `kmtaint(&kmptr) → void` - "taints" a `kmptr` object by setting it to be shredded when freed. this may be desirable if the object pointed to contains privileged information.
13 15
14 16 ## types
................................................................................
26 28
27 29
28 30 ### kmkind
29 31
30 32 `kmkind` is an enum that specifies an allocation function.
31 33
32 34 * `kmkind_none` - no allocation
33 - * `kmkind_heap` - heap allocation
35 + * `kmkind_lin` - linear heap allocation
36 + * `kmkind_heap` - random heap allocation
34 37 * `kmkind_pool` - pool allocation
35 38 * `kmkind_ref` - reference-counting allocation
36 39 * `kmkind_tree` - tree allocation
37 40
38 41 ### kmptr
39 42
40 43 kmem functions can operate on both raw pointers and the `kmptr` struct type. `kmptr` is a generic struct that can contain any kind of pointer. this is useful if you wish to allocate different objects in different manners, but pass them on into a single interface.
................................................................................
46 49 * `kmkind kind` - codes the type of pointer; `kmkind_none` indicates a non-allocated pointer to a static (global or on-stack) object.
47 50 * `kmshred shred` - an enum. if `kmshred_yes`, the value will be zeroed or otherwise made unreadable on free. if no, `kmfree` will consult `src` for shred policy if it is not NULL.
48 51 * `void* ref` - the raw pointer enclosed by `cell`
49 52 * `kmcell* cell` - a pointer to an object enclosure, typically either a memory pool or a referencing-counting object. NULL if not needed.
50 53
51 54 the convenience function `kmstat(void*) → kmptr` wraps a pointer to a static object in a `kmptr` struct.
52 55
53 -### kmcell
56 +### struct kmcell
54 57
55 -`kmcell` is a stub struct used to disambiguate between source types.a "source" is an object that can hold an allocated object, such as the heap, a memory pool, a fixed-length array on stack, or a fixed-length global array. all values produced by a kmem allocation function point to within a `kmcell`.
58 +`kmcell` is a stub struct used to disambiguate between source types. a "source" is an object that can hold an allocated object, such as the heap, a memory pool, a fixed-length array on stack, or a fixed-length global array. all values produced by a kmem allocation function can be cast to `kmcell*`, and have an intial field `id` that contains a `kmcell`.
56 59
57 60 * `kmkind kind` - kind of cell
58 61 * `size_t size` - size of cell (data plus all fields)
59 62 * `kmshred shred` - shredding flag
60 63
61 -### kmref
64 +### struct kmref
62 65
63 66 `kmref` is a struct that constitutes the in-memory representation of a reference-counted cell.
64 67
65 - * `kmkind kind = kmkind_ref` - kind of cell
66 - * `size_t sz` - size of cell (data plus all fields)
67 - * `kmshred shred` - shredding flag
68 + * `kmcell id = { .kind = kmkind_ref, … } ` - kind of cell
68 69 * `size_t refs` - number of active references
69 70 * `kmcell* src` - source, if any
70 71 * `char data[]` - content of cell
71 72
72 -### kmnode
73 +### struct kmnode
73 74
74 -`kmnode` is a struct that constitutes the in-memory representation of a tree node.
75 +`kmnode` is the header struct for tree nodes. all tree nodes pointers can yield a `kmnode` structure by subtracting `sizeof (kmnode)` from the pointer. a utility function and macro are made available to automate this safely.
75 76
76 - * `kmkind kind = kmkind_tree` - kind of cell
77 - * `size_t sz` - size of cell (data plus all fields)
78 - * `kmshred shred` - shredding flag
77 + * `kmcell id = { .kind = kmkind_tree, … } ` - kind of cell
79 78 * `kmnode* parent` - parent node
80 79 * `kmnode* child` - first child node
81 80 * `kmnode* lastchild` - last child node
82 81 * `kmnode* prev` - previous sibling, NULL if first
83 82 * `kmnode* next` - next sibling, NULL if last
84 - * `char data[]` - content of cell
85 83
86 -### kmpool
84 +### struct kmpool
87 85
88 - * `kmkind kind = kmkind_pool` - indicates the kind of source
89 - * `size_t sz` - size of cell (data plus all fields)
90 - * `kmshred shred` - shredding flag
86 + * `kmcell id = { .kind = kmkind_pool, … } ` - kind of cell
91 87 * `size_t cellsz` - size of individual pool cells
92 88 * `kmpoolcell* top` - pointer to most recently allocated pool cell
93 89 * `kmpoolcell* bottom` - pointer to most recently freed pool cell
94 90 * `kmpoolcell data[]` - content of cell
95 91
96 -#### kmpoolcell
92 +#### struct kmpoolcell
97 93
98 94 * `kmpoolcell* last` - pointer to last element allocated before this one
99 95 * `char data[]` - pool data
100 96
101 -### kmshred
97 +### enum kmshred
102 98
103 99 `kmshred` is an enum used to indicate whether an object should be "shredded" (written over) in memory when it's deleted. this is a useful means to ensure that privileged information is not accidentally left in memory after use. if the shredding mechanism is not useful, compile libk with the flag `KFmem_noshred` to exclude its functions and fields.
104 100
105 - * `kmshred_yes` - marks an object to shred on free
106 - * `kmshred_no` - marks an object not to shred on free
101 + * `kmshred_no = 0` - marks an object not to shred on free
102 + * `kmshred_yes = 1` - marks an object to shred on free
107 103
108 104 ## naming convention
109 105
110 106 kmem function names are based on the **method** of allocation and the **action** being performed. methods are listed in the section below. kmem defines a number of standardized actions, though not every method uses every action. the character listed in brackets is suffixed to the name of the method to produce a function name: for instance, `kmheapa` will allocate memory on the heap, while `kmrefd` will decrement the reference count of its argument.
111 107
112 108 * initialize [i] - initializes a memory store on the heap
113 109 * initialize fixed [if] - initialize a memory store on the stack or in a fixed-size global
................................................................................
118 114 * free [f] - free a section of memory, either decrementing a reference count or returning it to whatever pool it came from.
119 115 * shred [s] - destroy whatever was in the segment of memory, then return it to the pool it came from.
120 116 * destroy [x] - tears down a memory store
121 117 * upref [u] - increments a reference counter
122 118
123 119 ## methods
124 120
125 -kmem currently supports the following methods of memory management, along with which methods are defined for it. (note that `a` implies `z` and `f` implies `s`). a method may be excluded from a libk binary by defining the flag `KFmem_no[name]`, e.g. `KFmem_noheap`
121 +kmem currently supports the following methods of memory management, along with which methods are defined for it. (note that `a` implies `z` and `f` implies `s`). a method may be excluded from a libk binary by defining the flag `KFmem_no[name]`, e.g. `KFmem_noheap`.
122 +
123 +the fastest allocator is the linear allocator, which should be sufficient for most simple programs. it allocates and deallocates memory simply by resizing the stack; there is no fragmentation, but objects must be freed in the order they are allocated. however, entire groups of objects can be freed at once at very little cost.
126 124
127 - * `heap` [af] - standard heap allocation
125 + * `lin` [iax] - linear heap allocator
126 + * `kmlini(void) → void*` - return a pointer to the current top of the heap
127 + * `kmlina(size_t) → void*` - allocate space on the heap and increase its size appropriately
128 + * `kmlinz(size_t) → void*` - allocate zero-filled space on the heap and increase its size appropriately
129 + * `kmlinx(void*) → void*` - returns the top of the heap to the location specified, freeing all memory allocated since the call to kmlini() or `kmlina()` that produced it
130 + * `heap` [af] - random heap allocation
128 131 * `kmheapa(size_t) → void*` - allocate
129 132 * `kmheapz(size_t) → void*` - zero-allocate
130 133 * `kmheapao(size_t) → kmptr` - allocate pointer object
131 134 * `kmheapzo(size_t) → kmptr` - zero-allocate pointer object
132 135 * `kmheapf(void*) → void` - free
133 136 * `kmheaps(void*) → void` - shred
134 137 * `ref` [afu] - reference-counted heap object