# kmem

**kmem** is a libk module that contains various functions for memory allocation and deallocation. it uses the **short** naming convention with the glyph `m`.

## module functions

**kmem** supplies two module-level functions, used to interact with the `kmptr` container type.

 * `kmfree(kmptr) → void` - free, downref, or ignore the pasted object as appropriate
 * `kmshred(kmptr) → void` - free, downref, or ignore the pasted object as appropriate. if deallocating, zero its contents
 * `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 = { kmptr_kind_static, raw, NULL }`.
 * `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.

## types

kmem defines the following types:
 
 * `struct kmptr` - abstract pointer object
	* `enum kmptr_kind`
 * `struct kmcell` - abstract memory cell
	* `enum kmcell_kind`
 * `struct kmref` - a reference-counted cell
 * `struct kmnode` - a node in an allocation tree
 * `struct kmpool` - a memory pool

`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)`)

### kmptr

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.

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.

a `kmptr` has the following layout:

 * `kmptr_kind kind` - codes the type of pointer
 * `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.
 * `void* ref` - the raw pointer enclosed by `cell`
 * `kmcell* cell` - a pointer to an object enclosure, typically either a memory pool or a referencing-counting object. NULL if not needed.
 
the convenience function `kmstat(void*) → kmptr` wraps a pointer to a static object in a `kmptr` struct.

#### kmptr_kind

`kmptr_kind` is an enum with one of the following values.

 * `kmptr_kind_none` - not a valid pointer
 * `kmptr_kind_static` - points to a static region of space. `kmptr` instances with this kind will be ignored by `kmfree`.
 * `kmptr_kind_heap` - a traditional heap pointer.
 * `kmptr_kind_pool` - points to a region stored in a memory pool.
 * `kmptr_kind_ref` - points to a reference-counted object.
 * `kmptr_kind_node` - points to a reference-counted object.

### kmcell

`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`.

 * `kmptr_kind kind` - kind of cell
 * `size_t sz` - kind of cell (data plus all fields)
 * `kmshred shred` - shredding flag

### kmref

`kmref` is a struct that constitutes the in-memory representation of a reference-counted cell.

 * `kmcell_kind kind = ref` - kind of cell
 * `size_t sz` - size of cell (data plus all fields)
 * `kmshred shred` - shredding flag
 * `size_t refs` - number of active references 
 * `kmcell* src` - source, if any
 * `char data[]` - content of cell

### kmnode

`kmnode` is a struct that constitutes the in-memory representation of a tree node.

 * `kmcell_kind kind = node` - kind of cell
 * `size_t sz` - size of cell (data plus all fields)
 * `kmshred shred` - shredding flag
 * `kmnode* parent` - parent node
 * `kmnode* child` - first child node
 * `kmnode* lastchild` - last child node
 * `kmnode* prev` - previous sibling, NULL if first
 * `kmnode* next` - next sibling, NULL if last
 * `char data[]` - content of cell

### kmpool

 * `kmcell_kind kind = pool` - indicates the kind of source
 * `size_t sz` - size of cell (data plus all fields)
 * `kmshred shred` - shredding flag
 * `size_t cellsz` - size of individual pool cells
 * `kmpoolcell* top` - pointer to most recently allocated pool cell
 * `kmpoolcell* bottom` - pointer to most recently freed pool cell
 * `kmpoolcell data[]` - content of cell

### kmpoolcell

 * `kmpoolcell* last` - pointer to last element allocated before this one
 * `char data[]` - pool data

### kmshred

`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.

 * `kmshred_yes` - marks an object to shred on free
 * `kmshred_no` - marks an object not to shred on free

## naming convention

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.

 * initialize [i]  - initializes a memory store on the heap
 * initialize fixed [if]  - initialize a memory store on the stack or in a fixed-size global
 * 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).
 * allocate pointer object [ao]  - like *allocate*, but returns a `kmptr` instead of a raw `void*`.
 * zero [z]  - allocate a new region of memory and zero it before returning it for writing. 
 * zero pointer object [zo]  - like *zero*, but returns a `kmptr` instead of a raw `void*`.
 * free [f]  - free a section of memory, either decrementing a reference count or returning it to whatever pool it came from.
 * shred [s]  - destroy whatever was in the segment of memory, then return it to the pool it came from.
 * destroy [x]  - tears down a memory store
 * upref [u] - increments a reference counter

## methods

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`

 * `heap` [af] - standard heap allocation
   * `kmheapa(size_t) → void*` - allocate
   * `kmheapz(size_t) → void*` - zero-allocate
   * `kmheapao(size_t) → kmptr` - allocate pointer object
   * `kmheapzo(size_t) → kmptr` - zero-allocate pointer object
   * `kmheapf(void*) → void` - free
   * `kmheaps(void*) → void` - shred
 * `ref` [afu] - reference-counted heap object
   * `kmrefa(kmcell*, size_t) → void*` - allocate
   * `kmrefz(kmcell*, size_t) → void*` - zero-allocate
   * `kmrefao(kmcell*, size_t) → void*` - allocate pointer object
   * `kmrefzo(kmcell*, size_t) → void*` - zero-allocate pointer object
   * `kmreff(void*) → void` - downref; free if last ref
   * `kmrefs(void*) → void` - downref and mark for shred on last ref
 * `pool` [ixaf] - memory pool
   * `kmpooli(kmcell*, size_t sz, size_t n) → kmpool*` - initialize a fixed memory pool (a pool of `n` cells of length `sz`)
   * `kmpoolx(kmpool*) → void` - tear down a memory pool
   * `kmpoola(kmpool*) → void*` - allocate from pool
   * `kmpoolz(kmpool*, size_t) → void*` - zero-allocate from pool
   * `kmpoolao(kmpool*, size_t) → void*` - allocate pointer object
   * `kmpoolzo(kmpool*, size_t) → void*` - zero-allocate pointer object
   * `kmpoolf(void*) → void` - downref; free if last ref
   * `kmpools(void*) → void` - downref and mark for shred on last ref
 * `tree` [af] - uses a node-child strategy. when a node is freed, all of its children are automatically freed as well.
   * `kmtreea(kmcell* src, void* parent, size_t) → void*` - create a tree node. if `parent` is NULL, the node will the top of a new tree. if src is null, allocate on-heap.
   * `kmtreez(kmcell* src, void* parent, size_t) → void*` - like `kmtreea` but zeroed 
   * `kmtreeao(kmcell* src, void* parent, size_t) → kmptr` - like `kmtreea` but returns a `kmptr` 
   * `kmtreezo(kmcell* src, void* parent, size_t) → kmptr` - like `kmtreez` but returns a `kmptr` 
   * `kmtreef(void*) → kmptr` - frees a node and all its children

