Kernel memory manager

[vitiral]

I've decided to re-architect a few things with how words are compiled, where the dictionary is stored, what the dictionary is, etc.

• A 4KiB (2^12) block allocator will be added to the kernel with DV operations for adding/freeing blocks. You will pass the pointer to the block allocator which can allocate up to ~4MiB of memory (255 4K blocks, so the indexes fit in a single byte).
• Code and dictionary entries should be stored in 4KiB blocks. They will be stored together: code and names will grow up, dictionary entries will grow down. It will be the programmers job to use a NEW_BLOCK stanza when a new block is needed (tooling will be added to help determine where these should be placed and optimize them).
• The dictionary will be a BST instead of the current "organic growth" model (I'm not even sure what to call it) where it simply grows upwards with names and values. This will allow O(log n) lookups instead of the current O(n), as well as many other benefits.
  • The kernel will therefore have to implement a Red/Black BST. Creating/Getting dictionary entries will therefore use this directly
  • no more D_dict D_rdict, it will be D_bst. See below.

BST Operations

The kernel will expose D_bst for DV operations. FT will get a reference to the entry, SR will create an entry and return the reference. It will not populate any data by itself

The layout of an entry will be:

struct cBSTNode [ \ BST node using counted data (single byte len) key
  left, right: &BSTNode;
  key: &cdata;
  meta: U1;
]

Only the first bit of the meta byte is used as the red/black bit.

Costs and Improvements

• Cost: local variable implementation. The current approach of growing it from where the kdict is grown will be abandoned. Instead it will use a fresh 4k block which will be dropped before the next function. It will utilize both a SLL to determine order of adding items and metadata and will utilize it's own btree dict (ldict) for tracking types/etc.
• Benefit: initial constants will be defined in a "private" block and will be dropped. Folks can import them as a separate module if they are needed. This will free up a significant amount of space for folks who do not need the kernel constants (most programs!)
• Benefit: The ability to write code that will be dropped when the module is done. This includes inline tests (!!!), helper-macros or functions, constants, etc.
  • some of this will be implemented as separate modules. Modules can define "temporary imports" which import a module during it's instantiation and then drop it at the end. This can be used for loading constants and macros and then immediately dropping them.

[vitiral]

fixed by using civc