Red Echo

July 30, 2015

Trindle kernel interface exploration

A computer’s fundamental resources are blocks of memory, interfaces to other pieces of hardware, and (for a portable device) a supply of battery power. An operating system’s fundamental job is to allow a computer to run more than one program at a time by dividing those resources among them in some fashion consistent with the priorities of the machine’s owner. The design of an OS kernel therefore begins with its mechanisms for allocating resources to specific programs and the interface through which it allows programs to manipulate them.

The fundamental tool of permission management is the MMU, and the MMU’s finest granularity is the 4K page, so we’ll give each system object a unique page-aligned address.
typedef void *object_t;

The operations a process may apply to an object are defined by an array of permission bits; an object may inspect an object address to find out what it can do.
enum permission_t {
  PERMISSION_READ = 1, // can supply data
  PERMISSION_WRITE = 2, // can receive data
  PERMISSION_EXECUTE = 4, // contains machine code
  PERMISSION_DIRECT = 8, // backed by physical storage
  PERMISSION_PIPE = 16 // contains a transfer queue
permission_t inspect(object_t obj);

A buffer is a contiguous group of writable pages beginning at its identifying address, which will have PERMISSION_READ|PERMISSION_WRITE|PERMISSION_DIRECT.
typedef object_t buffer_t;

Allocate a range of address space as a new buffer. Each page will be mapped against the zerofill page and reassigned to physical storage when it receives its first write.
buffer_t allocate(size_t page_count);

Truncate the buffer down to some number of pages, splitting the remaining pages off as a new, independent buffer and returning its address.
buffer_t split(buffer_t buf, size_t page_count);

Move the contents of these buffers into a new, contiguous buffer, releasing the original buffers in the process.
buffer_t join(buffer_t head, buffer_t tail);

Copy a range of pages into a new buffer; the source address must be page-aligned but may come from any region where the process has read permission.
buffer_t copy(void *source, size_t page_count);

A shared resource is an immutable buffer, which means that it can be owned by more than one process at a time. It offers PERMISSION_READ|PERMISSION_DIRECT.
typedef object_t resource_t;

Create a new shared resource by cloning the contents of an existing mutable buffer.
resource_t share(buffer_t data);

One process may communicate an object to another by transmitting it through a pipe. Unless the object is a shared resource, this transfers ownership from the sender to the receiver, and the object is removed from the sender’s access space. The pipe contains a queue, allowing communication to happen asynchronously.

An output is the end of the pipe you send objects into. It has PERMISSION_PIPE|PERMISSION_WRITE.
typedef object_t output_t;

Transmit a list of objects, one at a time, until they are all sent or the pipe’s queue has filled up. Returns the number of objects which were successfully transmitted.
size_t transmit(output_t dest, const object_t objs[], size_t count);

An input is the end of the pipe you receive objects from. It offers PERMISSION_PIPE|PERMISSION_READ.
typedef object_t input_t;

Receive objects from the pipe until its queue empties or the destination array fills up, then return the number of objects which were received, if any.
size_t receive(input_t src, object_t objs[], size_t array_size);

Allocate a new pipe able to queue up a certain number of elements, populating the variables pointed at by in and out with the pipe’s endpoint objects.
void pipe(size_t entries, input_t *in, output_t *out);

Close a pipe by releasing its input or output. The object representing the pipe’s other end will lose PERMISSION_READ or PERMISSION_WRITE and retain only PERMISSION_PIPE.

An executable is a shared resource which contains machine code. Since it is an immutable shared resource, it can be owned by more than one process at a time. It offers PERMISSION_EXECUTE|PERMISSION_DIRECT.
typedef object_t executable_t;

Create a new executable by cloning the contents of an existing shared resource.
executable_t prepare_code(resource_t text);

Create a new process in suspended state, configure its saved instruction pointer and stack pointer, and assign it ownership of some objects (thereby releasing all but the shared resources, as usual). The process will begin executing when the scheduler next gets around to granting it a timeslice and “resuming” it.
void launch(object_t bundle[], size_t bundle_count, void *entrypoint, void *stack);

Delete the current process and release all of its resources.
void exit();

Suspend the process until an empty input starts to fill, a blocked output starts to drain, a pipe closes, or a certain number of milliseconds have elapsed. If woken by an event involving a pipe, the call will return the relevant input or output, otherwise it will return zero.
object_t sleep(uint64_t milliseconds);

I’m starting to lose track of all the Trindle draft documents I’ve written, rewritten, replaced, and abandoned, scattered as they are across three laptops, my home desktop, and a remote server. This is either my fifth or sixth attempt at a concrete design for the system interface, but it’s the first time I’ve made it all the way through without discovering a fatal flaw, and that feels like progress.