@@ -1,11 +1,13 @@
 # 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`.
 
+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()`
+
 ## module functions
 
-**kmem** supplies two module-level functions, used to interact with the `kmptr` container type.
+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 = { kmkind_none, raw, NULL }`.
@@ -29,9 +31,10 @@
 
 `kmkind` is an enum that specifies an allocation function.
  
  * `kmkind_none` - no allocation
- * `kmkind_heap` - heap allocation
+ * `kmkind_lin` - linear heap allocation
+ * `kmkind_heap` - random heap allocation
  * `kmkind_pool` - pool allocation
  * `kmkind_ref` - reference-counting allocation
  * `kmkind_tree` - tree allocation
 
@@ -49,62 +52,55 @@
  * `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.
 
-### kmcell
+### struct 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`.
+`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`.
 
  * `kmkind kind` - kind of cell
  * `size_t size` - size of cell (data plus all fields)
  * `kmshred shred` - shredding flag
 
-### kmref
+### struct kmref
 
 `kmref` is a struct that constitutes the in-memory representation of a reference-counted cell.
 
- * `kmkind kind = kmkind_ref` - kind of cell
- * `size_t sz` - size of cell (data plus all fields)
- * `kmshred shred` - shredding flag
+ * `kmcell id = { .kind = kmkind_ref, … } ` - kind of cell
  * `size_t refs` - number of active references 
  * `kmcell* src` - source, if any
  * `char data[]` - content of cell
 
-### kmnode
+### struct kmnode
 
-`kmnode` is a struct that constitutes the in-memory representation of a tree node.
+`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.
 
- * `kmkind kind = kmkind_tree` - kind of cell
- * `size_t sz` - size of cell (data plus all fields)
- * `kmshred shred` - shredding flag
+ * `kmcell id = { .kind = kmkind_tree, … } ` - kind of cell
  * `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
+### struct kmpool
 
- * `kmkind kind = kmkind_pool` - indicates the kind of source
- * `size_t sz` - size of cell (data plus all fields)
- * `kmshred shred` - shredding flag
+ * `kmcell id = { .kind = kmkind_pool, … } ` - kind of cell
  * `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
+#### struct kmpoolcell
 
  * `kmpoolcell* last` - pointer to last element allocated before this one
  * `char data[]` - pool data
 
-### kmshred
+### enum 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
+ * `kmshred_no = 0` - marks an object not to shred on free
+ * `kmshred_yes = 1` - marks an object 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.
@@ -121,11 +117,18 @@
  * 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`
+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`.
+
+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.
 
- * `heap` [af] - standard heap allocation
+ * `lin` [iax] - linear heap allocator
+   * `kmlini(void) → void*` - return a pointer to the current top of the heap
+   * `kmlina(size_t) → void*` - allocate space on the heap and increase its size appropriately
+   * `kmlinz(size_t) → void*` - allocate zero-filled space on the heap and increase its size appropriately
+   * `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
+ * `heap` [af] - random 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