Index: kcli/kcli.md ================================================================== --- kcli/kcli.md +++ kcli/kcli.md @@ -23,41 +23,41 @@ a kcli_set might be used like so: #include #include #include - u8 entry(kenv e) { + stat entry(kenv e) { kcli_flag aardvark; kcli_flag zebra; char* user; char* password; long age; - kcli_param* params = { + 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 = { + 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 = { + 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(&me); + size_t args_parsed = kcli_parse(&argset); if (args_parsed == 0) { kcli_usage(&me, e.err); return 1; } return 0; } @@ -78,10 +78,11 @@ * `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 Index: kcore/def.h.m ================================================================== --- kcore/def.h.m +++ kcore/def.h.m @@ -1,23 +1,42 @@ dnl kcore/def.h.m → dnl ~ lexi hale 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 . -dnl vim: ft=c +dnl vim: ft=m4 #ifndef KIdef #define KIdef -define(`def',`#define $1 $2') +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)') -def(KVtarget,target) -def(KVos,atom_target_os) -def(KVarch,atom_target_arch) +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', @@ -27,8 +46,8 @@ #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]) +def(`Knoimpl(fn)', Kerror(no implementation of fn for platform target)) #endif Index: kcore/testbin.exe.c ================================================================== --- kcore/testbin.exe.c +++ kcore/testbin.exe.c @@ -7,11 +7,11 @@ u8 a; s16 b; bool c; }; -kbad entry(kenv e) { +stat_long entry(kenv e) { const char msg[] = "hello from libk\n"; ksraw ptr = { Kmsz(msg), msg }; bool maybe = true; maybe = no; @@ -21,11 +21,13 @@ } else { return kbad_io; } struct object* block = kmheapa(sizeof (struct object) * 4); - if (block == null) return kbad_mem; else return kbad_ok; + if (block == null) return kbad_mem; block[1].a = 5; + + if (kmheapf(block) != kmcond_ok) return kbad_mem; return kbad_ok; } Index: kmem/heapa.fn.c ================================================================== --- kmem/heapa.fn.c +++ kmem/heapa.fn.c @@ -1,7 +1,9 @@ #include #include +#include +#include /* heapa.c - kmheapa() "heap alloc" * ~ lexi hale * kmheapa() allocates a pointer on the heap à la libc malloc() * see also: kmheapf() "heap free" */ @@ -9,52 +11,53 @@ /* 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, +extern void* kmem_platform_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); + /* 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 (val == (void*) -1) return null; + 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; } Index: kmem/kmem.md ================================================================== --- kmem/kmem.md +++ kmem/kmem.md @@ -1,12 +1,14 @@ # 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 }`. * `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. @@ -28,11 +30,12 @@ ### kmkind `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 ### kmptr @@ -48,64 +51,57 @@ * `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 +### 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. @@ -120,13 +116,20 @@ * 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` +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 * `kmheapf(void*) → void` - free Index: kmem/mem.h ================================================================== --- kmem/mem.h +++ kmem/mem.h @@ -7,10 +7,15 @@ #endif #ifdef __cplusplus extern "C" { #endif + +typedef enum kmcond { + kmcond_ok, + kmcond_bad_address, +} kmcond; typedef enum kmkind { kmkind_none, kmkind_heap, kmkind_pool, @@ -27,11 +32,10 @@ kmkind kind; sz size; kmshred shred; sz refs; struct kmcell* src; - char data[]; } kmcell; typedef struct kmptr { kmkind kind; kmshred shred; @@ -39,13 +43,13 @@ kmcell* cell; } kmptr; /* heap functions */ -void* kmheapa(sz); -void kmheapf(void*); +void* kmheapa(sz); +kmcond kmheapf(void*); #ifdef __cplusplus } #endif #endif ADDED kmem/platform.mmap.fn.x86.lin.64.s Index: kmem/platform.mmap.fn.x86.lin.64.s ================================================================== --- kmem/platform.mmap.fn.x86.lin.64.s +++ kmem/platform.mmap.fn.x86.lin.64.s @@ -0,0 +1,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.2, ccall.reg.1 ;nop - rsi → rsi + mov sys.reg.3, ccall.reg.2 ;nop - rdx → rdx + mov sys.reg.4, ccall.reg.3 ; OP - rcx → r10 + 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 DELETED kmem/posix_mmap.fn.x86.lin.64.s Index: kmem/posix_mmap.fn.x86.lin.64.s ================================================================== --- kmem/posix_mmap.fn.x86.lin.64.s +++ kmem/posix_mmap.fn.x86.lin.64.s @@ -1,24 +0,0 @@ -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.2, ccall.reg.1 ;nop - rsi → rsi - mov sys.reg.3, ccall.reg.2 ;nop - rdx → rdx - mov sys.reg.4, ccall.reg.3 ; OP - rcx → r10 - 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 Index: makefile ================================================================== --- makefile +++ makefile @@ -2,10 +2,11 @@ # 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 Index: modmake ================================================================== --- modmake +++ modmake @@ -11,11 +11,11 @@ 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} +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}