libk  Check-in [709ffb094d]

#include <error_table.h>

/* we define all our platform functions here, whether or not
 * they're for the correct platform - only the ones that are
 * called by the preprocessed form of the code will actually
 * be linked, linker errors are our friend here! */
extern void* kmem_platform_mmap(void* addr,
		unsigned long sz, unsigned long prot, unsigned long flags,
		unsigned long fd, unsigned long off);

kmcond kmheapa(void** where, sz len) {
	/* allocate an object on the heap and return
	 * a pointer, or NULL if the allocation failed. */
	union {
		void* raw;
		ubyte* byte;
................................................................................

		k_platform_syscall_arg args[] = {
			null, region_size, 
			posix_prot_read | posix_prot_write,
			posix_flag_anonymous | posix_map_shared,
			-1, 0
		};





		struct k_platform_syscall_answer r = k_platform_syscall
			(k_platform_syscall_mmap, Kmsz(args), args);

		if (r.error == 0) region.byte = (ubyte*)r.ret; else {
			switch (r.error) {
				case k_platform_error_EAGAIN: return kmcond_bad_lock;
				case k_platform_error_EINVAL: return kmcond_bad_size;
				case k_platform_error_EMFILE: return kmcond_too_many;
				case k_platform_error_ENOMEM: return kmcond_no_room;
				default: return kmcond_fail_assert;
			}
		}

		/* region.byte = kmem_platform_mmap(null, region_size, */
		/* 		posix_prot_read | posix_prot_write, */
		/* 		posix_flag_anonymous | posix_map_shared, -1, 0); */

		/* impl note: while per manpage fd is "ignored"
		 * for MAP_ANONYMOUS, "some implementations" require
		 * a value of -1 */

#	else
 	   Knoimpl(kmheapa,KVos);
#		error missing implementation
#	endif
	
	void* const object = (region.byte + sizeof (kmbox));

	region.header -> kind = kmkind_heap;
	region.header -> size = len;

	*where = object;
	return kmcond_ok;
}

#include <error_table.h>

/* we define all our platform functions here, whether or not
 * they're for the correct platform - only the ones that are
 * called by the preprocessed form of the code will actually
 * be linked, linker errors are our friend here! */




kmcond kmheapa(void** where, sz len) {
	/* allocate an object on the heap and return
	 * a pointer, or NULL if the allocation failed. */
	union {
		void* raw;
		ubyte* byte;
................................................................................

		k_platform_syscall_arg args[] = {
			null, region_size, 
			posix_prot_read | posix_prot_write,
			posix_flag_anonymous | posix_map_shared,
			-1, 0
		};

		/* impl note: while per manpage fd is "ignored"
		 * for MAP_ANONYMOUS, "some implementations" require
		 * a value of -1 */

		struct k_platform_syscall_answer r = k_platform_syscall
			(k_platform_syscall_mmap, Kmsz(args), args);

		if (r.error == 0) region.byte = (ubyte*)r.ret; else {
			switch (r.error) {
				case k_platform_error_EAGAIN: return kmcond_bad_lock;
				case k_platform_error_EINVAL: return kmcond_bad_size;
				case k_platform_error_EMFILE: return kmcond_too_many;
				case k_platform_error_ENOMEM: return kmcond_no_room;
				default: return kmcond_fail_assert;
			}
		}









#	else
 	   Knoimpl(kmheapa,KVos);
#		error missing implementation
#	endif
	
	void* const object = (region.byte + sizeof (kmbox));

	region.header -> kind = kmkind_heap;
	region.header -> size = len;

	*where = object;
	return kmcond_ok;
}

	if (header -> kind != kmkind_heap) return kmcond_mismatch;
#	ifdef KFenv_posix
		/* currently allocation is handled on posix by naive use
		 * of MAP_ANONYMOUS. munmap needs to be told the size of
		 * the region to unmap (free), which kmheapa() stores at
		 * (ptr - sizeof sz). see kmheap.c for details. */




		if(kmem_platform_munmap(header, total) == -1) {

			/* we don't need to bother recovering errno;
			 * there's only one possible munmap error */
			return kmcond_bad_address;
		}

#	else
		Knoimpl(kmheapf,KVos);
#		error missing implementation
#	endif
	return kmcond_ok;
}

	if (header -> kind != kmkind_heap) return kmcond_mismatch;
#	ifdef KFenv_posix
		/* currently allocation is handled on posix by naive use
		 * of MAP_ANONYMOUS. munmap needs to be told the size of
		 * the region to unmap (free), which kmheapa() stores at
		 * (ptr - sizeof sz). see kmheap.c for details. */
		k_platform_syscall_arg args[] = { (sz)header, total };
		struct k_platform_syscall_answer r = k_platform_syscall
			(k_platform_syscall_munmap, Kmsz(args), args);


		if(r.error==0) {
			/* we don't need to bother recovering the error
			 * code, there's only one possible munmap error */
			return kmcond_bad_address;
		}

#	else
		Knoimpl(kmheapf,KVos);
#		error missing implementation
#	endif
	return kmcond_ok;
}

#include <k/core.h>
#include <k/mem.h>
/* heapao.fn.c - kmheapao() "allocate heap object"
 * ~ lexi hale <lexi@hale.su>
 * kmheapao() allocates a region in heap memory
 * and returns a kmptr struct referencing that
 * newly allocated region.
 */

kmcond kmheapao(kmptr* where, sz size) {
	void* ptr;
	kmcond e = kmheapa(&ptr, size);
	if (e != kmcond_ok) return e;
	kmptr p = {
		.kind = (ptr != null ? kmkind_heap : kmkind_fail),
		.ref = ptr,
		.shred = false,
	};
	*where = p;
	return kmcond_ok;
}

#include <k/core.h>
#include <k/mem.h>
/* heapo.fn.c - kmheapo() "allocate heap object"
 * ~ lexi hale <lexi@hale.su>
 * kmheapo() allocates a region in heap memory
 * and returns a kmptr struct referencing that
 * newly allocated region.
 */

kmcond kmheapo(kmptr* where, sz size) {
	void* ptr;
	kmcond e = kmheapa(&ptr, size);
	if (e != kmcond_ok) return e;
	kmptr p = {
		.kind = (ptr != null ? kmkind_heap : kmkind_fail),
		.ref = ptr,
		.shred = false,
	};
	*where = p;
	return kmcond_ok;
}

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

 * `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 }`.
 * `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.
 * `kmzero(void*,sz) → void` - zeroes a region of memory
 * `kmozero(kmptr) → void` - zeroes an object in memory
 * `kmcopy(void* dest, void* src, sz) → void` - copies one region of memory to another
 * `kmdup(kmptr) → kmptr` - duplicates an object in memory, allocating it as sibling of the original

## types

kmem defines the following types:
 
 * `enum kmkind` - enumerates allocation strategies
 * `struct kmptr` - abstract pointer object
 * `struct kmcell` - abstract memory cell
 * `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)`)


### kmkind

`kmkind` is an enum that specifies an allocation function.
 
 * `kmkind_none` - no allocation
 * `kmkind_lin` - linear heap allocation
 * `kmkind_heap` - random heap allocation
 * `kmkind_pool` - pool allocation
 * `kmkind_ref` - reference-counting allocation
 * `kmkind_tree` - tree allocation

### 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:

................................................................................
 * `kmkind kind` - codes the type of pointer; `kmkind_none` indicates a non-allocated pointer to a static (global or on-stack) object.
 * `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.

### 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 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

### struct kmref

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

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

### struct kmnode

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

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

### struct kmpool

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

#### struct kmpoolcell

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

### 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_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.

 * 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

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

# description

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.

 * `kmfree(kmptr) → kmcond` - free, downref, or ignore the passed object as appropriate
 * `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.
 * `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 }`.
 * `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.
 * `kmzero(void*,sz) → void` - zeroes a region of memory
 * `kmozero(kmptr) → void` - zeroes an object in memory
 * `kmcopy(void* dest, void* src, sz) → void` - copies one region of memory to another
 * `kmdup(kmptr) → kmptr` - duplicates an object in memory, allocating it as sibling of the original

# types

kmem defines the following types:
 
 * `enum kmkind` - enumerates allocation strategies
 * `struct kmptr` - abstract pointer object
 * `struct kmcell` - abstract memory cell
 * `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)`)


## kmkind

`kmkind` is an enum that specifies an allocation function.
 
 * `kmkind_none` - no allocation
 * `kmkind_lin` - linear heap allocation
 * `kmkind_heap` - random heap allocation
 * `kmkind_pool` - pool allocation
 * `kmkind_ref` - reference-counting allocation
 * `kmkind_tree` - tree allocation

## 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:

................................................................................
 * `kmkind kind` - codes the type of pointer; `kmkind_none` indicates a non-allocated pointer to a static (global or on-stack) object.
 * `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.

## 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 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

## struct kmref

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

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

## struct kmnode

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

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

## struct kmpool

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

### struct kmpoolcell

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

## 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_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.

 * 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]  -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`.
 * allocate pointer object [o]  - like *allocate*, but fills in a `kmptr` instead of a raw `void*`. takes parameters `kmptr* where, size_t sz`.
 * 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