Differences From
Artifact [73d0a96333]:
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 +
5 +# description
4 6
5 7 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 8
7 -## module functions
9 +# module functions
8 10
9 11 kmem supplies two module-level functions, used to interact with the `kmptr` container type.
10 12
11 - * `kmfree(kmptr) → void` - free, downref, or ignore the pasted object as appropriate
12 - * `kmshred(kmptr) → void` - free, downref, or ignore the pasted object as appropriate. if deallocating, zero its contents
13 + * `kmfree(kmptr) → kmcond` - free, downref, or ignore the passed object as appropriate
14 + * `kmshred(kmptr) → void` - free, downref, or zero the passed object as appropriate. if downref'ing, mark underlying object to be shredded. otherwise, zero its contents, then deallocate if appropriate.
13 15 * `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 }`.
14 16 * `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.
15 17 * `kmzero(void*,sz) → void` - zeroes a region of memory
16 18 * `kmozero(kmptr) → void` - zeroes an object in memory
17 19 * `kmcopy(void* dest, void* src, sz) → void` - copies one region of memory to another
18 20 * `kmdup(kmptr) → kmptr` - duplicates an object in memory, allocating it as sibling of the original
19 21
20 -## types
22 +# types
21 23
22 24 kmem defines the following types:
23 25
24 26 * `enum kmkind` - enumerates allocation strategies
25 27 * `struct kmptr` - abstract pointer object
26 28 * `struct kmcell` - abstract memory cell
27 29 * `struct kmref` - a reference-counted cell
28 30 * `struct kmnode` - a node in an allocation tree
29 31 * `struct kmpool` - a memory pool
30 32
31 33 `kmptr` and `kmcell` are both very similar. the difference is that a kmptr points to a region in memory and can be passed around freely. a `kmcell` is the actual in-memory representation of an allocation cell. a `kmcell` cannot be usefully instantiated; rather, it is downcast from an actual cell type (e.g. `kmnode n; kmcell* s = (kmcell*)(&n)`)
32 34
33 35
34 -### kmkind
36 +## kmkind
35 37
36 38 `kmkind` is an enum that specifies an allocation function.
37 39
38 40 * `kmkind_none` - no allocation
39 41 * `kmkind_lin` - linear heap allocation
40 42 * `kmkind_heap` - random heap allocation
41 43 * `kmkind_pool` - pool allocation
42 44 * `kmkind_ref` - reference-counting allocation
43 45 * `kmkind_tree` - tree allocation
44 46
45 -### kmptr
47 +## kmptr
46 48
47 49 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.
48 50
49 51 memory pointed at by `kmptr` pointers can be freed either with the usual specialized function, or by passing the `kmptr` structure itself to the generic function `kmfree`, which will handle it appropriately, even if it's a pointer to a garbage-collected object or to a static region of memory.
50 52
51 53 a `kmptr` has the following layout:
52 54
................................................................................
53 55 * `kmkind kind` - codes the type of pointer; `kmkind_none` indicates a non-allocated pointer to a static (global or on-stack) object.
54 56 * `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.
55 57 * `void* ref` - the raw pointer enclosed by `cell`
56 58 * `kmcell* cell` - a pointer to an object enclosure, typically either a memory pool or a referencing-counting object. NULL if not needed.
57 59
58 60 the convenience function `kmstat(void*) → kmptr` wraps a pointer to a static object in a `kmptr` struct.
59 61
60 -### struct kmcell
62 +## struct kmcell
61 63
62 64 `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`.
63 65
64 66 * `kmkind kind` - kind of cell
65 67 * `size_t size` - size of cell (data plus all fields)
66 68 * `kmshred shred` - shredding flag
67 69
68 -### struct kmref
70 +## struct kmref
69 71
70 72 `kmref` is a struct that constitutes the in-memory representation of a reference-counted cell.
71 73
72 74 * `kmcell id = { .kind = kmkind_ref, … } ` - kind of cell
73 75 * `size_t refs` - number of active references
74 76 * `kmcell* src` - source, if any
75 77 * `char data[]` - content of cell
76 78
77 -### struct kmnode
79 +## struct kmnode
78 80
79 81 `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.
80 82
81 83 * `kmcell id = { .kind = kmkind_tree, … } ` - kind of cell
82 84 * `kmnode* parent` - parent node
83 85 * `kmnode* child` - first child node
84 86 * `kmnode* lastchild` - last child node
85 87 * `kmnode* prev` - previous sibling, NULL if first
86 88 * `kmnode* next` - next sibling, NULL if last
87 89
88 -### struct kmpool
90 +## struct kmpool
89 91
90 92 * `kmcell id = { .kind = kmkind_pool, … } ` - kind of cell
91 93 * `size_t cellsz` - size of individual pool cells
92 94 * `kmpoolcell* top` - pointer to most recently allocated pool cell
93 95 * `kmpoolcell* bottom` - pointer to most recently freed pool cell
94 96 * `kmpoolcell data[]` - content of cell
95 97
96 -#### struct kmpoolcell
98 +### struct kmpoolcell
97 99
98 100 * `kmpoolcell* last` - pointer to last element allocated before this one
99 101 * `char data[]` - pool data
100 102
101 -### enum kmshred
103 +## enum kmshred
102 104
103 105 `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 106
105 107 * `kmshred_no = 0` - marks an object not to shred on free
106 108 * `kmshred_yes = 1` - marks an object to shred on free
107 109
108 -## naming convention
110 +# naming convention
109 111
110 112 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 113
112 114 * initialize [i] - initializes a memory store on the heap
113 115 * initialize fixed [if] - initialize a memory store on the stack or in a fixed-size global
114 - * allocate [a] - return a raw pointer to a new region of memory of the given size, ready to write, or NULL if not possible. contents of that region undefined. takes parameter (size_t sz).
115 - * allocate pointer object [ao] - like *allocate*, but returns a `kmptr` instead of a raw `void*`.
116 + * allocate [a] -a llocate a new region of memory of the given size, ready to write, and write a pointer to it into argument `where`. returns a value of `kmcond`; always check this to ensure allocation succeeded. contents of that region undefined. takes parameters `void** where, size_t sz`.
117 + * allocate pointer object [o] - like *allocate*, but fills in a `kmptr` instead of a raw `void*`. takes parameters `kmptr* where, size_t sz`.
116 118 * zero [z] - allocate a new region of memory and zero it before returning it for writing.
117 119 * zero pointer object [zo] - like *zero*, but returns a `kmptr` instead of a raw `void*`.
118 120 * free [f] - free a section of memory, either decrementing a reference count or returning it to whatever pool it came from.
119 121 * shred [s] - destroy whatever was in the segment of memory, then return it to the pool it came from.
120 122 * destroy [x] - tears down a memory store
121 123 * upref [u] - increments a reference counter
122 124