libk  Check-in [acb4a9944e]

Overview
Comment:add kmlini() and kmlina() functions; restructure allocation functions to work more reasonably (returning a tuple struct instead of making a user pass in a void**); update docs accordingly
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: acb4a9944e5a48cbab044b5ec26e822496624e9a7e7f74abf8cb9ace70b86e81
User & Date: lexi on 2019-08-22 08:44:29
Other Links: manifest | tags
Context
2019-08-22
08:45
check in missing files check-in: 269baab90a user: lexi tags: trunk
08:44
add kmlini() and kmlina() functions; restructure allocation functions to work more reasonably (returning a tuple struct instead of making a user pass in a void**); update docs accordingly check-in: acb4a9944e user: lexi tags: trunk
04:31
finish moving heap allocation/free functions to the posix syscall apparatus and deprecate the direct assembly implementations of platform_mmap; update the kmem docs to match new function signatures (and remove typos) check-in: 709ffb094d user: lexi tags: trunk
Changes

Modified arch/posix/syscalls from [24a70b57fd] to [f436d656b4].

     1      1   exit
     2      2   read
     3      3   write
     4      4   mmap
     5      5   munmap
            6  +brk

Modified mod/kcore/testbin.exe.c from [ae0ed8cd11] to [2c9c964882].

    18     18   
    19     19   	if (kiosend(e.std, ptr, null) == kiocond_ok) {
    20     20   		/* great, continue */
    21     21   	} else {
    22     22   		return kbad_io;
    23     23   	}
    24     24   
    25         -	void* region;
    26         -	kmcond alloc = kmheapa(&region, 2048);
    27         -	if (alloc != kmcond_ok) return kbad_mem;
    28         -
           25  +	kmres alloc = kmheapa(2048);
           26  +	if (alloc.cond != kmcond_ok) return kbad_mem;
           27  +	
           28  +	void* region = alloc.raw;
    29     29   	kmzero(region,2048);
    30     30   
    31     31   	if (kmheapf(region) >= kmcond_fail) return kbad_mem;
    32     32   
    33     33   	return kbad_ok;
    34     34   }

Modified mod/kmem/free.fn.c from [cc32756862] to [bac849b7ff].

     8      8    * kmfree() frees memory allocated in any manner.
     9      9    * it ignores non-dynamically allocated memory,
    10     10    * returning kmcond_unnecessary. to check for
    11     11    * success, compare result < kmcond_fail.
    12     12    */
    13     13   
    14     14   kmcond kmfree(kmptr ptr) {
    15         -	if (ptr.kind <= kmkind_fail) return kmcond_unnecessary;
           15  +	if (ptr.kind <= kmkind_broken) return kmcond_unnecessary;
    16     16   	switch (ptr.kind) {
    17     17   		case kmkind_heap: return kmheapf(ptr.ref);
    18     18   	}
    19     19   
    20     20   	return kmcond_unhandled;
    21     21   }
    22     22   

Modified mod/kmem/heapa.fn.c from [c8ccec879e] to [c08b42ee14].

    16     16   #include <error_table.h>
    17     17   
    18     18   /* we define all our platform functions here, whether or not
    19     19    * they're for the correct platform - only the ones that are
    20     20    * called by the preprocessed form of the code will actually
    21     21    * be linked, linker errors are our friend here! */
    22     22   
    23         -kmcond kmheapa(void** where, sz len) {
           23  +kmres kmheapa(sz len) {
    24     24   	/* allocate an object on the heap and return
    25     25   	 * a pointer, or NULL if the allocation failed. */
    26     26   	union {
    27     27   		void* raw;
    28     28   		ubyte* byte;
    29     29   		kmbox* header;
    30     30   	} region;
    31     31   	/* we need to allocate space for the
    32     32   	 * header and for the actual object */
    33     33   	sz region_size = sizeof(kmbox) + len;
           34  +	kmres reply;
    34     35   
    35     36   #	ifdef KFenv_posix
    36     37   		/* posix  APIs  - we've  got  it  easy. currently  for
    37     38   		 * nonlinear  heap  allocation   kmheapa  simply  uses
    38     39   		 * m(un)map  and lets  the kernel  worry about  it. it
    39     40   		 * may  ultimately  be  worth replacing  this  with  a
    40     41   		 * more sophisticated  implementation, most  likely an
................................................................................
    64     65   		 * a value of -1 */
    65     66   
    66     67   		struct k_platform_syscall_answer r = k_platform_syscall
    67     68   			(k_platform_syscall_mmap, Kmsz(args), args);
    68     69   
    69     70   		if (r.error == 0) region.byte = (ubyte*)r.ret; else {
    70     71   			switch (r.error) {
    71         -				case k_platform_error_EAGAIN: return kmcond_bad_lock;
    72         -				case k_platform_error_EINVAL: return kmcond_bad_size;
    73         -				case k_platform_error_EMFILE: return kmcond_too_many;
    74         -				case k_platform_error_ENOMEM: return kmcond_no_room;
    75         -				default: return kmcond_fail_assert;
           72  +				case k_platform_error_EAGAIN: reply.cond = kmcond_bad_lock; break;
           73  +				case k_platform_error_EINVAL: reply.cond = kmcond_bad_size; break;
           74  +				case k_platform_error_EMFILE: reply.cond = kmcond_too_many; break;
           75  +				case k_platform_error_ENOMEM: reply.cond = kmcond_no_room;  break;
           76  +				default: reply.cond = kmcond_fail_assert;
    76     77   			}
           78  +			reply.raw = (void*)0;
           79  +			return reply;
    77     80   		}
    78     81   #	else
    79     82    	   Knoimpl(kmheapa,KVos);
    80     83   #		error missing implementation
    81     84   #	endif
    82     85   	
    83     86   	void* const object = (region.byte + sizeof (kmbox));
    84     87   
    85     88   	region.header -> kind = kmkind_heap;
    86     89   	region.header -> size = len;
    87     90   
    88         -	*where = object;
    89         -	return kmcond_ok;
           91  +	reply.cond = kmcond_ok;
           92  +	reply.raw = object;
           93  +
           94  +	return reply;
    90     95   }

Modified mod/kmem/heapo.fn.c from [70c3679214] to [5d74e5db6e].

     3      3   /* heapo.fn.c - kmheapo() "allocate heap object"
     4      4    * ~ lexi hale <lexi@hale.su>
     5      5    * kmheapo() allocates a region in heap memory
     6      6    * and returns a kmptr struct referencing that
     7      7    * newly allocated region.
     8      8    */
     9      9   
    10         -kmcond kmheapo(kmptr* where, sz size) {
    11         -	void* ptr;
    12         -	kmcond e = kmheapa(&ptr, size);
    13         -	if (e != kmcond_ok) return e;
           10  +kmres kmheapo(sz size) {
           11  +	kmres e = kmheapa(size);
           12  +	kmres reply;
           13  +
           14  +	if (e.cond != kmcond_ok) {
           15  +		reply.cond = e.cond;
           16  +		reply.ptr.ref = (void*)0;
           17  +		reply.ptr.kind = kmkind_broken;
           18  +		return reply;
           19  +	}
           20  +
    14     21   	kmptr p = {
    15         -		.kind = (ptr != null ? kmkind_heap : kmkind_fail),
    16         -		.ref = ptr,
           22  +		.kind = (e.raw != null ? kmkind_heap : kmkind_broken),
           23  +		.ref = e.raw,
    17     24   		.shred = false,
    18     25   	};
    19         -	*where = p;
    20         -	return kmcond_ok;
           26  +
           27  +	reply.ptr = p;
           28  +	reply.cond = kmcond_ok;
           29  +	return reply;
    21     30   }

Modified mod/kmem/kmem.md from [0e44a94bf4] to [35f7501adf].

     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      5   # description
     6      6   
     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()`
            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()`. functions that can return a value and an error condition always return a value of type `kmres`, a struct that contains the field `kmcond` with an error code, and one of `raw` (for functions that return raw pointers) or `ptr` (for functions that return `kmptr` objects).
     8      8   
     9      9   # module functions
    10     10   
    11     11   kmem supplies two module-level functions, used to interact with the `kmptr` container type.
    12     12   
    13     13    * `kmfree(kmptr) → kmcond` - free, downref, or ignore the passed object as appropriate
    14     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.
................................................................................
   109    109   
   110    110   # naming convention
   111    111   
   112    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.
   113    113   
   114    114    * initialize [i]  - initializes a memory store on the heap
   115    115    * initialize fixed [if]  - initialize a memory store on the stack or in a fixed-size global
   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  + * allocate [a]  - allocate a new region of memory of the given size, ready to write, and return a struct `kmres` containing an error code and, if the call succeeded, a pointer in the field `raw`. always check the `cond` field of its return value to ensure allocation succeeded. contents of the region specified by the `raw` field are undefined. takes parameter `size_t sz`.
          117  + * allocate pointer object [o]  - like *allocate*, but yields a `kmptr` in the `ptr` field of its return value instead of a raw `void*`. takes parameters `size_t sz`.
   118    118    * zero [z]  - allocate a new region of memory and zero it before returning it for writing. 
   119    119    * zero pointer object [zo]  - like *zero*, but returns a `kmptr` instead of a raw `void*`.
   120    120    * free [f]  - free a section of memory, either decrementing a reference count or returning it to whatever pool it came from.
   121    121    * shred [s]  - destroy whatever was in the segment of memory, then return it to the pool it came from.
   122    122    * destroy [x]  - tears down a memory store
   123    123    * upref [u] - increments a reference counter
   124    124   
   125    125   ## methods
   126    126   
   127    127   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`.
   128    128   
   129    129   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.
   130    130   
          131  +**caveat scriptor:** the linear allocation method is unfortunately complicated by the fact that the methods it uses make it fundamentally incompatible with use in the program of the "malloc" allocator used by libc. this should not be a problem for programs that only link libk, but if they link in any external libraries that depend on libc and which use malloc internally, **the linear allocator cannot be used.**
          132  +
   131    133    * `lin` [iax] - linear heap allocator
   132         -   * `kmlini(void) → void*` - return a pointer to the current top of the heap
   133         -   * `kmlina(size_t) → void*` - allocate space on the heap and increase its size appropriately
   134         -   * `kmlinz(size_t) → void*` - allocate zero-filled space on the heap and increase its size appropriately
   135         -   * `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
          134  +   * `kmlini` - return a pointer to the current top of the heap
          135  +   * `kmlina` - allocate space on the heap and increase its size appropriately
          136  +   * `kmlinz` - allocate zero-filled space on the heap and increase its size appropriately
          137  +   * `kmlinx` - returns the top of the heap to the location specified, freeing all memory allocated since the call to kmlini() or `kmlina()` that produced it
   136    138    * `heap` [af] - random heap allocation
   137         -   * `kmheapa(size_t) → void*` - allocate
   138         -   * `kmheapz(size_t) → void*` - zero-allocate
   139         -   * `kmheapao(size_t) → kmptr` - allocate pointer object
   140         -   * `kmheapzo(size_t) → kmptr` - zero-allocate pointer object
   141         -   * `kmheapf(void*) → void` - free
   142         -   * `kmheaps(void*) → void` - shred
          139  +   * `kmheapa` - allocate
          140  +   * `kmheapz` - zero-allocate
          141  +   * `kmheapo` - allocate pointer object
          142  +   * `kmheapzo` - zero-allocate pointer object
          143  +   * `kmheapf` - free
          144  +   * `kmheaps` - shred
   143    145    * `ref` [afu] - reference-counted heap object
   144         -   * `kmrefa(kmcell*, size_t) → void*` - allocate
   145         -   * `kmrefz(kmcell*, size_t) → void*` - zero-allocate
   146         -   * `kmrefao(kmcell*, size_t) → void*` - allocate pointer object
   147         -   * `kmrefzo(kmcell*, size_t) → void*` - zero-allocate pointer object
   148         -   * `kmreff(void*) → void` - downref; free if last ref
   149         -   * `kmrefs(void*) → void` - downref and mark for shred on last ref
          146  +   * `kmrefa` - allocate
          147  +   * `kmrefz` - zero-allocate
          148  +   * `kmrefo` - allocate pointer object
          149  +   * `kmrefzo` - zero-allocate pointer object
          150  +   * `kmreff` - downref; free if last ref
          151  +   * `kmrefs` - downref and mark for shred on last ref
   150    152    * `pool` [ixaf] - memory pool
   151    153      * `kmpooli(kmcell*, size_t sz, size_t n) → kmpool*` - initialize a fixed memory pool (a pool of `n` cells of length `sz`)
   152         -   * `kmpoolx(kmpool*) → void` - tear down a memory pool
   153         -   * `kmpoola(kmpool*) → void*` - allocate from pool
   154         -   * `kmpoolz(kmpool*, size_t) → void*` - zero-allocate from pool
   155         -   * `kmpoolao(kmpool*, size_t) → void*` - allocate pointer object
   156         -   * `kmpoolzo(kmpool*, size_t) → void*` - zero-allocate pointer object
   157         -   * `kmpoolf(void*) → void` - downref; free if last ref
   158         -   * `kmpools(void*) → void` - downref and mark for shred on last ref
          154  +   * `kmpoolx` - tear down a memory pool
          155  +   * `kmpoola` - allocate from pool
          156  +   * `kmpoolz` - zero-allocate from pool
          157  +   * `kmpoolo` - allocate pointer object
          158  +   * `kmpoolzo` - zero-allocate pointer object
          159  +   * `kmpoolf` - downref; free if last ref
          160  +   * `kmpools` - downref and mark for shred on last ref
   159    161    * `tree` [af] - uses a node-child strategy. when a node is freed, all of its children are automatically freed as well.
   160         -   * `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.
   161         -   * `kmtreez(kmcell* src, void* parent, size_t) → void*` - like `kmtreea` but zeroed 
   162         -   * `kmtreeao(kmcell* src, void* parent, size_t) → kmptr` - like `kmtreea` but returns a `kmptr` 
   163         -   * `kmtreezo(kmcell* src, void* parent, size_t) → kmptr` - like `kmtreez` but returns a `kmptr` 
   164         -   * `kmtreef(void*) → kmptr` - frees a node and all its children
          162  +   * `kmtreea` - create a tree node. if `parent` is NULL, the node will the top of a new tree. if src is null, allocate on-heap.
          163  +   * `kmtreez` - like `kmtreea` but zeroed 
          164  +   * `kmtreeao` - like `kmtreea` but returns a `kmptr` 
          165  +   * `kmtreezo` - like `kmtreez` but returns a `kmptr` 
          166  +   * `kmtreef` - frees a node and all its children
   165    167   
   166    168   ## macros
   167    169   
   168    170   kmem defines the following macros.
   169    171   
   170    172    * `Kmsz(array)` - a convenience macro to return the number of elements in a static array. inserts the text `( sizeof (array) / sizeof (array) [0] )`
   171    173    * `Kmszs(type, struct)` - a convenience macro to return the size of a struct. requires compound literals.
   172    174    * `Kmszsa(type, array)` - calculates the number of elements in an array of a given struct type. inserts the text `( sizeof ( (type) array ) / sizeof (type) )`
   173    175    * `Kmpsa(type, struct)` - a convenience macro to insert a "pascal struct array" - that is, a struct array prefixed with a size value. this is equivalent to `Kmszsa(type, array), array`

Modified mod/kmem/mem.h from [d8d36f64f5] to [0dc09a3b20].

    27     27   	/* when something truly should
    28     28   	 * never happen: */
    29     29   	kmcond_fail_assert,
    30     30   } kmcond;
    31     31   
    32     32   typedef enum kmkind {
    33     33   	kmkind_none,
    34         -	kmkind_fail,
           34  +	kmkind_broken,
    35     35   	kmkind_linear,
    36     36   	kmkind_heap,
    37     37   	kmkind_pool,
    38     38   	kmkind_ref,
    39     39   	kmkind_tree
    40     40   } kmkind;
    41     41   
................................................................................
    66     66   
    67     67   typedef struct kmptr {
    68     68   	kmkind kind;
    69     69   	kmshred shred;
    70     70   	void* ref;
    71     71   } kmptr;
    72     72   
           73  +/* this struct is used to return both a pointer
           74  + * and an error value at the same time. */
           75  +typedef struct kmres {
           76  +	kmcond cond;
           77  +	union {
           78  +		void* raw;
           79  +		kmptr ptr;
           80  +	};
           81  +} kmres;
    73     82   /* heap functions */
    74     83   
    75         -kmcond kmheapa (void**, sz);
    76         -kmcond kmheapao(kmptr*, sz);
           84  +kmres  kmheapa (sz);
           85  +kmres  kmheapo (sz);
    77     86   kmcond kmheapf (void*);
           87  +kmres  kmlina  (sz);
           88  +void*  kmlini  (void);
    78     89   
    79     90   /* generic functions */
    80     91   
    81     92   kmcond kmfree(kmptr);
    82         -kmkind kmtell(void*);
    83     93   void kmzero(void*,sz);
    84     94   void kmozero(kmptr);
    85     95   
    86     96   
    87     97   #ifdef __cplusplus
    88     98   }
    89     99   #endif
    90    100   
    91    101   #endif