HYDROGEN: Extensibility (by alaric)
Memory management
C is delightfully vague about the structure of memory. It guarantees that if you allocate an array you'll be able to get from one end of the array to the other by doing arithmetic on a pointer obtained by using the & operator on any array element; but that's about it. C's requirement to support things like the 8086 segmented memory model means that it's perfectly valid for a C runtime to never let you allocate more than 64KB in one object, while supporting any amount of actual memory. Which means that portable C programs have a hard time actually doing things like image manipulation; when images are likely to be several megabytes in size.
In practice, people don't tend to write portable C; instead, they look at the capabilities of a given class of platforms, and code for that. So somebody writing an image editor for real-mode DOS would explicitly write a system for splitting the image into pages of up to 64KB, probably with a manual virtual-memory system to page them to and from a file on disk. While somebody writing one for a UNIX platform would just malloc() as many bytes as they wanted, and treat failure as an out-of-memory error.
My take is that the C standard has ended up making something useless, in its quest to support archaic platforms such as the 8086. In practice, people code to poorly-defined de-facto profiles such as 32-bit or better flat memory model C where sizeof(int) == sizeof(int*), but there's no portable way to declare that dependency in their code, meaning that it might compile fine but then not work (such as our image editor that tries to malloc() 192KiB for a 256x256x3 image on a DOS system - which will probably fail even before getting to malloc() as the multiplication of the width and height and depth of the image overflows the 16-bit int).
So, for HYDROGEN, I'm mandating that pointers are a machine word in size. I'm not too bothered about 8086 real-mode support! But I'm not saying that pointers address individual bytes - instead, pointers address "allocation units", or AUs. Most platforms will have an AU of a byte, but on some systems, they might be a machine word, or something in between. Either way, we have no invariants like sizeof(u8) == 1; indeed, due to the considerations given above, sizeof(u8) == sizeof(u16) == sizeof(u32) is perfectly legal (although we do mandate that sizeof(u8) == sizeof(s8) == sizeof(c8)).
The address space has to be linear, but it needn't be contiguous. An application can request a number of AUs and be returned a pointer to the start of that region, as a cell-sized value that can be manipulated with u+ to offset into the block; but the effects of reading and writing addresses outside of memory blocks the system has given to the application is undefined.
Memory allocation
Now, FORTH's memory allocation system is almost painfully simple. In FORTH, memory is a contiguous linear span, and memory is allocated by moving a pointer up through memory; everything below that pointer is in use, and where that pointer points and beyond is free, up to some limit. This is simple, and compact - the only memory wasted in memory management is a single cell to store that pointer, and the code to allocate memory is tiny. Memory can only be freed in the reverse order that it was allocated; one might record the value of the pointer, then load and run an application, then when it quits, just restore the pointer, thereby undoing all the allocation that application performed (including its compiled code).
But this doesn't sit well at all with a modern multiprocessing system. For a start, FORTH's assumption that it can build up variable-length structures by just allocating lots of small objects and assuming they'll end up contiguous relies on only one process allocating memory at once, as two processes will end up interleaving.
So in HYDROGEN, we provide two interfaces for memory allocation. One requests a single block of memory, of a known size in AUs, and you get a pointer back. The other is for variable-length objects, and is called the stream interface; to create a variable-length block, one creates a stream context (and gets a handle for it), then appends objects of various sizes to the stream (with the option of platform-dependent encodings for u8s and the like, or more specific portable encodings such as "big endian packed s16"). At any time, the application can ask for the offset into the stream in AUs. When it's done, it can seal the stream context, at which point it gets back a pointer to a contiguous region of memory containing the data provided, which it can add any saved offsets onto to get pointers to members of the object.
The most basic implementation of all this is precisely FORTHs - there's just an advancing pointer through a flat memory space. Allocating a block just moves the pointer; creating a stream context just saves this pointer in a global variable; asking for the current stream offset just subtracts the saved pointer from the current allocation pointer; and sealing the stream just returns the saved pointer. If a memory block is freed, then it's just added to a free list, but the free list is never used. If the system has mulitiple contiguous blocks of memory initially available, the largest one is picked as the heap to linearly allocate from; all the others are just put on the free list.
In an SMP system, the allocation pointer will be protected by a lock, so multiple processes can allocate blocks at once, but only one heap stream is allowed to exist at once, systemwide.
However, the application is free to take over and implement its own heap, once it's bootstrapped one on top of the basic allocator. All of the memory allocation words are actually indirected, and an application can install its own implementations of them. When it does so, it will find a free list containing details of all other memory regions in the system, and regions of memory from the linear heap that have been freed; and it will be able to read the allocation pointer and the top-of-linear-heap pointer, and thus add an extra free-list entry for the remaining memory in the linear heap. Given that free list, it can then implement its own heap on top of it; any memory that was allocated linearly but is subsequently freed can be detected as it will be within the linear region between the start of the linear heap and the allocation pointer at the time the replacement heap took over, if it requires special handling.
External memory
But what of systems where all of memory can't be accessed linearly? Back in the DOS days, we had EMS and XMS, which were memory regions inaccessible to the CPU directly, but that could be paged or copied into normal memory via an API, thus allowing you to have more memory than could fit into the processor's limited address space. More recently, things like PAE lets 32-bit processors have more than 4GiB of physical memory, but only 4GiB of memory can be accessed in one contiguous address space, due to the 32-bit pointers. Such extra memory can be used as a form of intermediate storage, between main memory and things like disks.
In order to support those, we provide a cache feature, which allows the application to allocate such memory blocks and to request to pin them. Once pinned, a block gains a real memory address, which remains valid until it's unpinned. This pinning interface allows implementations that can map memory directly into our address space, as well as implementations that need to copy it back and forth.
We can assign a drop priority to every block, and if external memory becomes full, the implementatino may drop blocks, ordered by priority. A block may have a drop subroutine handle attached, which is called before dropping the block, so its contents can be squirrelled away to disk if they are needed.
Memory management units
MMUs perform two main functions: virtual memory, and Memory protection.
And, to be honest, neither of those are actually critical for ARGON. Virtual memory was very useful when RAM was highly expensive, but nowadays, the speed difference between RAM and disk is so vast that if a machine starts to swap, its performance drops to such unacceptable levels that we consider it broken. I think it's far more important to think about operating system architectures that make better use of RAM (such as ARGON's!) than to implement virtual memory.
But, having said that, I don't want to entirely discount the possibility. When running on top of POSIX, for a start, we inherit the underlying platform's virtual memory system; and there's no reason why a bare-metal implementation can't use the same trick, with the HYDROGEN 'kernel' wired into memory so that it can make sure the code and data required to handle paging in is always available. The problem is that this paging is then happening below the level of process scheduling - which happens above HYDROGEN, such as in the HELIUM resource manager - so there may be wastage as an entire CPU is blocked while code or data it requires is paged in.
It might be possible to provide a way to portably control paging hardware, with page faults being passed back to the application as HYDROGEN callbacks, and providing a way for the application to mark certain code and data as having to be wired into memory (perhaps by explicitly switching into "wired allocation mode" before compiling the code and allocating the memory, then switching back) - but, to be honest, I have no current desire to do so, so will leave that until somebody wants it.
Memory protection is a more interesting issue, however. ARGON doesn't need it, as only "kernel code" will be written directly in HYDROGEN; all "user code" will be written in CHROME, which is the compiled using the HYDROGEN code generator, but with the compiler ensuring pointer safety at the language level (so all code runs in independent sandboxes).
But memory protection is very useful for virtualization. And I'd like to support that. So I've sketched a series of optional features that implement various virtual machines, from x86 to HYDROGEN itself.
An implementation on bare-metal x86 can provide a virtual x86 by using the memory protection hardware to create an isolated unprivileged address space, that the host can poke code and data into, and register to provide virtual hardware at certain memory or I/O addresses, or syscall interfaces into the host. Features such as virtual 8086 mode, Xen/VMware hypervisor support, or full virtualisation (letting the guest code think it's running in ring 0) and so on can be enabled if required, subject to support in the implementation. So the virtual-machine system can be used to create thin VMs that run code explicitly compiled to live in such a VM (which is what userland binaries in POSIX systems basically are), or can do full virtualisation to run guest OSes unaware.
While an implementation on an ARM processor, or x86 without access to the MMU, could implement x86 VMs through emulation.
Wed 15th Jul 2009 11:05 pm 
Subscribe