libk  Check-in [5279674525]

Overview
Comment:fix kmheapa() and add kmheapf()
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 5279674525478386b960cc2c3cea164b95ce972979972d82867106e785d71485
User & Date: lexi on 2019-08-18 10:20:30
Other Links: manifest | tags
Context
2019-08-18
11:34
add memory functions check-in: 5393623a84 user: lexi tags: trunk
10:20
fix kmheapa() and add kmheapf() check-in: 5279674525 user: lexi tags: trunk
2019-07-27
05:28
port header macro files to m4; delete gpp infra; fix glaring syntax errors in kcore/type.h check-in: 0c20d256a6 user: lexi tags: trunk
Changes

Modified kcli/kcli.md from [91db6a8cad] to [09b7990027].

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
..
76
77
78
79
80
81
82

83
84
85
86
87
88
89
 * `size_t optc` - the number of options in the list to process.

a kcli_set might be used like so:

    #include <k/core.h>
    #include <k/io.h>
    #include <k/cli.h>
    u8 entry(kenv e) {
    	kcli_flag aardvark;
    	kcli_flag zebra;
    	char* user;
    	char* password;
		long age;
		kcli_param* params = {
    		{ "user", kcli_param_string, kcli_class_required,
    		  &user, "the user to log in as" }
			  // or Kcli_param(user,string,required,"the user to log in as"),

			{ "age", kcli_param_dec, kcli_class_optional,
    		  &age, "the age of the user" }
			  // or Kcli_param(age,dec,optional,"the age of the user"),
		};
    	kcli_opt* options = {
    		{ 'a', "aardvark", kcli_opt_flag, &aardvark,
    		  "a nocturnal burrowing mammal" },
			  // or Kcli_opt(aardvark, 'a', flag, "a nocturnal burrowing mammal")
    		{ 'z', "zebra", kcli_opt_flag, &zebra,
    		  "a striped equine" },
    		{ 'p', "password", kcli_opt_string, &password,
    		  "the password to log in with" }
    	};
    	kcli_set me = {
    		"demo", e.argc, e.argv,
    		"a demonstration of the kcli_set type",
			params, Kmsz(params),
			options, Kmsz(options)
    	},
		size_t args_parsed = kcli_parse(&me);
		if (args_parsed == 0) { kcli_usage(&me, e.err); return 1; }

		return 0;
	}

### struct kcli_opt
a `kcli_opt` is a representation of a command-line flag and its function. each option must have a unique `id` and/or a unique `name`.
................................................................................
 * `kcli_opt_string` - flag tells kcli to add a string to the list of expected parameters; appropriate string will be returned
 * `kcli_opt_oct` - flag tells kcli to add an octal number to the list of expected parameters
 * `kcli_opt_dec` - flag tells kcli to add a decimal number to the list of expected parameters
 * `kcli_opt_hex` - flag tells kcli to add a hexdecimal number to the list of expected parameters
 * `kcli_opt_flag` - flag is an option: will return `kcli_flag_on` if entered at least once, `kcli_flag_off` otherwise.
 * `kcli_opt_toggle` - flag toggles value on and off: will return `kcli_flag_on` if entered an odd number of times, `kcli_flag_off` otherwise.
 * `kcli_opt_accumulate` - flag increments a value every time it is entered; often used to implement `-v (--verbose)`-style options (e.g. `-vvvv` would return a value of `4`).


### struct kcli_param
`kcli_param` describes a parameter that may be passed to the program whether or not any flags are passed.

 * `const char* name` - a short name for the parameter
 * `kcli_param_kind kind` - the kind of parameter passed
 * `kcli_class class` - whether or not the parameter is optional







|





|








|








|





|







 







>







21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
..
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 * `size_t optc` - the number of options in the list to process.

a kcli_set might be used like so:

    #include <k/core.h>
    #include <k/io.h>
    #include <k/cli.h>
    stat entry(kenv e) {
    	kcli_flag aardvark;
    	kcli_flag zebra;
    	char* user;
    	char* password;
		long age;
		kcli_param params[] = {
    		{ "user", kcli_param_string, kcli_class_required,
    		  &user, "the user to log in as" }
			  // or Kcli_param(user,string,required,"the user to log in as"),

			{ "age", kcli_param_dec, kcli_class_optional,
    		  &age, "the age of the user" }
			  // or Kcli_param(age,dec,optional,"the age of the user"),
		};
    	kcli_opt options[] = {
    		{ 'a', "aardvark", kcli_opt_flag, &aardvark,
    		  "a nocturnal burrowing mammal" },
			  // or Kcli_opt(aardvark, 'a', flag, "a nocturnal burrowing mammal")
    		{ 'z', "zebra", kcli_opt_flag, &zebra,
    		  "a striped equine" },
    		{ 'p', "password", kcli_opt_string, &password,
    		  "the password to log in with" }
    	};
    	kcli_set argset = {
    		"demo", e.argc, e.argv,
    		"a demonstration of the kcli_set type",
			params, Kmsz(params),
			options, Kmsz(options)
    	},
		size_t args_parsed = kcli_parse(&argset);
		if (args_parsed == 0) { kcli_usage(&me, e.err); return 1; }

		return 0;
	}

### struct kcli_opt
a `kcli_opt` is a representation of a command-line flag and its function. each option must have a unique `id` and/or a unique `name`.
................................................................................
 * `kcli_opt_string` - flag tells kcli to add a string to the list of expected parameters; appropriate string will be returned
 * `kcli_opt_oct` - flag tells kcli to add an octal number to the list of expected parameters
 * `kcli_opt_dec` - flag tells kcli to add a decimal number to the list of expected parameters
 * `kcli_opt_hex` - flag tells kcli to add a hexdecimal number to the list of expected parameters
 * `kcli_opt_flag` - flag is an option: will return `kcli_flag_on` if entered at least once, `kcli_flag_off` otherwise.
 * `kcli_opt_toggle` - flag toggles value on and off: will return `kcli_flag_on` if entered an odd number of times, `kcli_flag_off` otherwise.
 * `kcli_opt_accumulate` - flag increments a value every time it is entered; often used to implement `-v (--verbose)`-style options (e.g. `-vvvv` would return a value of `4`).
 * `kcli_opt_enum` - flag is one of a series of enumerated values, which will be matched against a table to yield the associated integer.

### struct kcli_param
`kcli_param` describes a parameter that may be passed to the program whether or not any flags are passed.

 * `const char* name` - a short name for the parameter
 * `kcli_param_kind kind` - the kind of parameter passed
 * `kcli_class class` - whether or not the parameter is optional

Modified kcore/def.h.m from [694c1d32cc] to [2981fff8c9].

1
2
3
4
5
6
7
8

9



10
11
12
13
14
15
16
17














18

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
dnl kcore/def.h.m → <k/def.h>
dnl ~ lexi hale <lexi@hale.su>
dnl this file gathers information on the environment it's
dnl being compiled in, setting macros that other headers
dnl need. it will be emitted as <k/def.h>.
dnl vim: ft=c
#ifndef KIdef
#define KIdef

define(`def',`#define $1 $2')




ifdef(`atom_target_bits',`
	define(`target',`atom_target_arch.atom_target_os.atom_target_bits')
	def(KVbits,atom_target_bits)',`
	define(`target',atom_target_arch.atom_target_os)')

def(KVtarget,target)
def(KVos,atom_target_os)














def(KVarch,atom_target_arch)


ifelse(target_unix,`yes',
		`def(`KFenv_unix',)
		def(`KFenv_posix',)',`
		ifelse(target_posix,`yes',
			`def(KFenv_posix)')')

#define Kpragma(p) _Pragma(#p)
#if defined(__GNUC__) || defined(__clang__)
#   define Kerror(msg) Kpragma(GCC error #msg) 
#else
#   define Kerror(msg) Kpragma(message #msg)
#endif
#define Knoimpl(fn) Kerror(no implementation of fn for platform [target])

#endif





|


>
|
>
>
>






|
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>













|


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
dnl kcore/def.h.m → <k/def.h>
dnl ~ lexi hale <lexi@hale.su>
dnl this file gathers information on the environment it's
dnl being compiled in, setting macros that other headers
dnl need. it will be emitted as <k/def.h>.
dnl vim: ft=m4
#ifndef KIdef
#define KIdef
define(`_atom',0)dnl
define(`def',`#define $1 $2')dnl
define(`defatom',`def($1,$2$3)')dnl
define(`newatom',`def($1,_atom)
	define(`_atom',incr(_atom))')dnl

ifdef(`atom_target_bits',`
	define(`target',`atom_target_arch.atom_target_os.atom_target_bits')
	def(KVbits,atom_target_bits)',`
	define(`target',atom_target_arch.atom_target_os)')

newatom(KA_os_lin)dnl
newatom(KA_os_fbsd)dnl
newatom(KA_os_obsd)dnl
newatom(KA_os_nbsd)dnl
newatom(KA_os_dar)dnl
newatom(KA_os_osx)dnl
newatom(KA_os_and)dnl
newatom(KA_os_hai)dnl
newatom(KA_os_win)dnl

newatom(KA_arch_x86)dnl
newatom(KA_arch_arm)dnl
newatom(KA_arch_ppc)dnl
newatom(KA_arch_mips)dnl
newatom(KA_arch_itan)dnl

defatom(KVos,KA_os_,atom_target_os)
defatom(KVarch,KA_arch_,atom_target_arch)

ifelse(target_unix,`yes',
		`def(`KFenv_unix',)
		def(`KFenv_posix',)',`
		ifelse(target_posix,`yes',
			`def(KFenv_posix)')')

#define Kpragma(p) _Pragma(#p)
#if defined(__GNUC__) || defined(__clang__)
#   define Kerror(msg) Kpragma(GCC error #msg) 
#else
#   define Kerror(msg) Kpragma(message #msg)
#endif
def(`Knoimpl(fn)', Kerror(no implementation of fn for platform target))

#endif

Modified kcore/testbin.exe.c from [5796abefa5] to [8406c82300].

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


29
30
31

struct object {
	u8 a;
	s16 b;
	bool c;
};

kbad entry(kenv e) {
	const char msg[] = "hello from libk\n";
	ksraw ptr = { Kmsz(msg), msg };

	bool maybe = true;
	maybe = no;

	if (kiosend(e.std, ptr, null) == kiocond_ok) {
		/* great, continue */
	} else {
		return kbad_io;
	}

	struct object* block = kmheapa(sizeof (struct object) * 4);
	if (block == null) return kbad_mem; else return kbad_ok;
	
	block[1].a = 5;



	return kbad_ok;
}







|













|


>
>



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

struct object {
	u8 a;
	s16 b;
	bool c;
};

stat_long entry(kenv e) {
	const char msg[] = "hello from libk\n";
	ksraw ptr = { Kmsz(msg), msg };

	bool maybe = true;
	maybe = no;

	if (kiosend(e.std, ptr, null) == kiocond_ok) {
		/* great, continue */
	} else {
		return kbad_io;
	}

	struct object* block = kmheapa(sizeof (struct object) * 4);
	if (block == null) return kbad_mem;
	
	block[1].a = 5;

	if (kmheapf(block) != kmcond_ok) return kbad_mem;

	return kbad_ok;
}

Modified kmem/heapa.fn.c from [f32eb209ee] to [aa6d2182a2].

1
2


3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


















45
46
47
48
49
50
51
52
53



54
55
56
57
58
59
60
#include <k/core.h>
#include <k/def.h>


/* heapa.c - kmheapa() "heap alloc"
 * ~ lexi hale <lexi@hale.su>
 * kmheapa() allocates a pointer on the heap à la libc malloc()
 * see also: kmheapf() "heap free"
 */

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

enum posix_prot {
	posix_prot_none  = 0,
	posix_prot_read  = 1 << 0,
	posix_prot_write = 1 << 1,
	posix_prot_exec  = 1 << 2
};

enum posix_map {
	posix_map_shared  = 1,
	posix_map_private = 2
};

enum posix_flag {
	posix_flag_fixed     = 0x10,
	posix_flag_anonymous = 0x20,

	/* platform flags */
	posix_flag_linux_hugetlb = 0x40000
};

void* kmheapa(sz len) {
	/* allocate an object on the heap and return
	 * a pointer, or NULL if the allocation failed. */
	void* val;

#	ifdef KFenv_posix
 	   /* posix APIs - we've got it easy */


















		val = kmem_posix_mmap(null, len, posix_prot_read | posix_prot_write,
				posix_flag_anonymous, -1, 0);
		/* impl note: while per manpage fd is "ignored"
		 * for MAP_ANONYMOUS, "some implementations" require
		 * a value of -1 */

		if (val == (void*) -1) return null;
		/* worth retrieving errno? discuss */




#	else
 	   Knoimpl(kmheapa,KVos);
#		error missing implementation
#	endif

	return val;
}


>
>











|



<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<






|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|




|


>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19




















20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <k/core.h>
#include <k/def.h>
#include <k/type.h>
#include <posix.h>
/* heapa.c - kmheapa() "heap alloc"
 * ~ lexi hale <lexi@hale.su>
 * kmheapa() allocates a pointer on the heap à la libc malloc()
 * see also: kmheapf() "heap free"
 */

/* we define all platform functions here,
 * whether or not they're for the correct
 * platform - only the ones actually called
 * by the generated code will 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);





















void* kmheapa(sz len) {
	/* allocate an object on the heap and return
	 * a pointer, or NULL if the allocation failed. */
	void* val;

#	ifdef KFenv_posix
 	   /* posix APIs - we've got it easy. currently for nonlinear
		* heap allocation kmheapa simply uses m(un)map and lets the 
		* kernel worry about it. it may ultimately be worth replacing
		* this with a more sophisticated implementation, most likely
		* an existing allocator like jemalloc, though i'm wary of
		* including outside code - it creates a licensing mess and
		* i'd prefer libk to be AGPLv3 across the board. possibility:
		* include hooks for multiple allocators, allowing the user
		* to select & link in her preferred allocator at compile time? */

		/* because munmap needs to be informed of the size of
		 * the region it is going to unmap, we need to store
		 * that information in the allocated region itself.
		 * the user will be given a pointer that can be
		 * adjusted to point a field of type size_t that
		 * contains the size of the allocate space.*/

		sz     const region_total = len + sizeof len;
		ubyte* const region = kmem_platform_mmap(null, region_total,
				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 */

		if (region == (void*) -1) return null;
		/* worth retrieving errno? discuss */

		*((sz*)region) = len;
		val = region + sizeof len;

#	else
 	   Knoimpl(kmheapa,KVos);
#		error missing implementation
#	endif

	return val;
}

Modified kmem/kmem.md from [18509d6a57] to [5405a3e53e].

1
2
3
4


5
6
7
8
9
10
11
12
13
14
..
26
27
28
29
30
31
32

33
34
35
36
37
38
39
40
..
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
...
118
119
120
121
122
123
124
125
126







127
128
129
130
131
132
133
134
# 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 = { 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.

## types
................................................................................


### kmkind

`kmkind` is an enum that specifies an allocation function.
 
 * `kmkind_none` - no allocation

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

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

 * `kmkind kind` - kind of cell
 * `size_t size` - size 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.

 * `kmkind kind = kmkind_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.

 * `kmkind kind = kmkind_tree` - 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

 * `kmkind kind = kmkind_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
................................................................................
 * 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




>
>


|







 







>
|







 







|

|





|



|
<
<




|

|

|
<
<





<

|

<
<
<
>





|




|



|
|







 







|

>
>
>
>
>
>
>
|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
..
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


69
70
71
72
73
74
75
76
77


78
79
80
81
82

83
84
85



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
...
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
# 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.

## types
................................................................................


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

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.

 * `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
   * `kmheapf(void*) → void` - free
   * `kmheaps(void*) → void` - shred
 * `ref` [afu] - reference-counted heap object

Modified kmem/mem.h from [e8670496c8] to [09be45a2b3].

5
6
7
8
9
10
11





12
13
14
15
16
17
18
..
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#ifndef KFclean
#	define Kmsz(e) ( sizeof (e) / sizeof (e) [0] )
#endif

#ifdef __cplusplus
extern "C" {
#endif






typedef enum kmkind {
	kmkind_none,
	kmkind_heap,
	kmkind_pool,
	kmkind_ref,
	kmkind_tree
................................................................................

typedef struct kmcell {
	kmkind kind;
	sz size;
	kmshred shred;
	sz refs;
	struct kmcell* src;
	char data[];
} kmcell;

typedef struct kmptr {
	kmkind kind;
	kmshred shred;
	void* ref;
	kmcell* cell;
} kmptr;

/* heap functions */

void* kmheapa(sz);
void  kmheapf(void*);

#ifdef __cplusplus
}
#endif

#endif







>
>
>
>
>







 







<











|
|






5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
30
31
32
33
34
35
36

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#ifndef KFclean
#	define Kmsz(e) ( sizeof (e) / sizeof (e) [0] )
#endif

#ifdef __cplusplus
extern "C" {
#endif

typedef enum kmcond {
	kmcond_ok,
	kmcond_bad_address,
} kmcond;

typedef enum kmkind {
	kmkind_none,
	kmkind_heap,
	kmkind_pool,
	kmkind_ref,
	kmkind_tree
................................................................................

typedef struct kmcell {
	kmkind kind;
	sz size;
	kmshred shred;
	sz refs;
	struct kmcell* src;

} kmcell;

typedef struct kmptr {
	kmkind kind;
	kmshred shred;
	void* ref;
	kmcell* cell;
} kmptr;

/* heap functions */

void*  kmheapa(sz);
kmcond kmheapf(void*);

#ifdef __cplusplus
}
#endif

#endif

Modified kmem/platform.mmap.fn.x86.lin.64.s from [0ee1179d8c] to [ceb93a428c].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
..
18
19
20
21
22
23
24

bits 64
%include "../arch/x86.lin.64.s"
%include "../arch/x86.cdecl.64.s"
; vim: ft=nasm

global kmem_posix_mmap
kmem_posix_mmap:
	; to call mmap, we need to translate the cdecl64
	; register arguments to their appropriate syscall64
	; registers. these are mostly the same, with one
	; obnoxious exception. the NOPs have been written
	; in as comments to aid in understanding.

	  mov sys.reg.1, ccall.reg.0 ;nop - rdi → rdi
................................................................................
	  mov sys.reg.5, ccall.reg.4 ;nop - r8 → r8
	  mov sys.reg.6, ccall.reg.5 ;nop - r9 → r9

	mov sys.reg.0, sys.mmap
	sys.call

	mov ccall.reg.ret, sys.reg.ret ; rax → rdi






|
|







 







>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
..
18
19
20
21
22
23
24
25
bits 64
%include "../arch/x86.lin.64.s"
%include "../arch/x86.cdecl.64.s"
; vim: ft=nasm

global kmem_platform_mmap
kmem_platform_mmap:
	; to call mmap, we need to translate the cdecl64
	; register arguments to their appropriate syscall64
	; registers. these are mostly the same, with one
	; obnoxious exception. the NOPs have been written
	; in as comments to aid in understanding.

	  mov sys.reg.1, ccall.reg.0 ;nop - rdi → rdi
................................................................................
	  mov sys.reg.5, ccall.reg.4 ;nop - r8 → r8
	  mov sys.reg.6, ccall.reg.5 ;nop - r9 → r9

	mov sys.reg.0, sys.mmap
	sys.call

	mov ccall.reg.ret, sys.reg.ret ; rax → rdi
	ret

Modified makefile from [7c13625dc8] to [d3e7936df2].

1
2
3
4
5
6

7
8
9
10
11
12
13
export OUT = $(PWD)/out

# TODO: calculate these using $(MAKE_HOST)
export ARCH = x86
export OS = lin
export BITS = 64

export TMP = $(PWD)/tmp

ifneq ($(BITS),)
    export TARGET = $(ARCH).$(OS).$(BITS)
else
    export TARGET = $(ARCH).$(OS)
endif






>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
export OUT = $(PWD)/out

# TODO: calculate these using $(MAKE_HOST)
export ARCH = x86
export OS = lin
export BITS = 64
export ROOT = $(PWD)
export TMP = $(PWD)/tmp

ifneq ($(BITS),)
    export TARGET = $(ARCH).$(OS).$(BITS)
else
    export TARGET = $(ARCH).$(OS)
endif

Modified modmake from [4d2e5850b0] to [5ed7cc8a39].

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
headers = $(wildcard *.h) $(gen-headers) $(patsubst %.m,%,$(wildcard *.h.m))

tools    = $(filter     %.exe.c,   $(src))
nontools = $(filter-out %.exe.c,   $(src))
cobjects = $(filter     %.c,       $(nontools))
sobjects = $(filter %.${TARGET}.s, $(nontools))

cflags = -std=c11 -isystem ${OUT} -fPIC -nostdlib ${COMPLIB} -L${OUT}

m-env = atom_target_arch=${ARCH}
m-env += atom_target_os=${OS}
ifneq (${BITS},) #!!! ifdef does NOT work with environment variables
    m-env += atom_target_bits=${BITS}
endif
m-env += target_posix=${POSIX}







|







9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
headers = $(wildcard *.h) $(gen-headers) $(patsubst %.m,%,$(wildcard *.h.m))

tools    = $(filter     %.exe.c,   $(src))
nontools = $(filter-out %.exe.c,   $(src))
cobjects = $(filter     %.c,       $(nontools))
sobjects = $(filter %.${TARGET}.s, $(nontools))

cflags = -std=c11 -isystem ${OUT} -isystem ${ROOT}/arch -fPIC -nostdlib ${COMPLIB} -L${OUT}

m-env = atom_target_arch=${ARCH}
m-env += atom_target_os=${OS}
ifneq (${BITS},) #!!! ifdef does NOT work with environment variables
    m-env += atom_target_bits=${BITS}
endif
m-env += target_posix=${POSIX}