Review of my OS's microkernel

[AndrewAPrice]

During my great rewrite of my kernel (from C++ -> D), I'm revising my microkernel's system call layout. Before you look through my syscall list I'll describe a little about the functions of my kernel, so they you have a better idea of if these goals can be achieved with the syscalls I have layed out and if I'm missing anything.

It is a microkernel, so there aren't any drivers built in (except for a basic text console driver in the case of kernel panics), they all run in userspace and that is not part of this specification.

The first function of my microkernel is to handle processes, devices, and threads. Processes and devices both exist within their own name systems, they are not part of any VFS. The VFS server (which again, is not part of the microkernel) may decide to integrate these in with files (e.g. put processes under "/processes/" and devices under "/devices/").

Processes can belong to one of 3 classes; drivers, servers, applications. These are all ring 3 processes, but the former classes are able to perform more system calls than the latter classes (their special privileges will be described below).

Drivers (the process name will be prefixed with "d\") can access IO ports, terminate a process/thread belonging to another process, send processes to sleep/wake them up, map physical memory locations into their local space, create/destroy device objects (which are merely references to the driver processes, with a unique per-device ID), listen if an IRQ fires, and transform in to (and back out of) a VM86 task.

The purpose of a driver is to abstract away system devices into "device objects". "Device objects" are merely a name (e.g. "disks\floppy\0") with a the ID of the driver and the ID device, then you communicate with the driver (through a common interface yet to be determined, but will consist of functions like get the type of device, initialise the device, and more specific functions depending on the type of device) using the kernel's IPC system and passing the ID of the device as a parameter.

Drivers can enter/leave VM86 mode freely, though in VM86 mode they can only access the first megabyte of their virtual memory (but they can execute any VM86 instructions they want) and fire an interrupt to leave VM86 mode. Some drivers (e.g. VESA drivers) will take advantage of this so they can access the BIOS (though not too often as it can slow down the entire system).

Applications shouldn't access drivers directly, but they can (though the driver can tell the class of the process, so to make sure that some actions (like writing to a disk) can only be performed by a server). A full-screen game is an example of when an application can access a driver directly (to perform 3D operations, or have exclusive control over the screen and audio output).

Examples of drivers include;
- DMA
- Floppy disk
- Hard drive
- Sound card
- Keyboard
- Video card

Servers (the process name will be prefixed with a "s\") can terminate a process/thread belonging to another process, and send processes to sleep/wake them up. Servers provide the core operating system functions.

Example of servers:
- Window manager
- VFS
- Task manager (which acts more like an application that can be launched when needed, but is classed as a server because it has the ability to kill/pause other processes)

Servers are NOT the same as web servers, file servers, etc - in this OS they would run as applications.

Applications (the process name will be prefixed with an "a\") can only directly modify themselves. They can communicate with other processes (particularly with servers) through the kernel's IPC facilities. These make up the majority (hopefully, ALL) of the user's programs.

Examples of applications:
- Web browsers
- Word processors
- File managers
- Games
- Media players

Rather than dealing with IPC directly to access servers and drivers, they will provide an interface/library (e.g. instead of sending a message, creating a pipe, pass through a buffer of commands, you will have a C interface with functions like WindowManager_Initialise(), WindowManager_CreateWindow(int x, int y, char *name)), drivers though will have a standard interface/library that you can use to access ALL devices of particular type/subtype (e.g. a device library which lets you access GetType() which tells you it's a storage device, then you'd use the storage device library to call GetSize(), Read(), GetMedia(). If the media is a CD, then you can use another interface which defines Eject()).

Memory management is the second function of the kernel. Processes can request more memory (by asking the kernel for another 4KB page or a series of pages) and release unused pages. They can also share pages of memory with other processes (see below).

Scheduling is the third function of the kernel, to ensure we have pseudo-concurrent execution of tasks. The kernel controls which processes are allowed execution type on the processor(s). Processes have a priority based on their class; servers and applications will not get processing time if their is an awake driver, and applications will not get processing time if their is an awake server. Processes (drivers, servers, most applications, though excluding some applications like games) will spend the majority of their time sleeping unless they have a task to perform. All awake threads of the same class will get equal priority.

Inter process communication is the fourth function of the kernel and is important in a microkernel. There are three levels of IPC; messages, pipes, and shared memory.

Dynamic sized messages can be sent freely between processes. Example usage of messages:
- Tell the window manager to create a window.
- Request to initialise a pipe with another process.

Pipes are 4KB of memory that any process can join and write to or read from (the process will sleep if they try to read more than there is in the pipe or write more than there is available in the buffer). Example usage of pipes:
- Stream audio to the sound driver.
- Read a file stream from the VFS.

Shared memory is reference counted memory (divided into 4KB pages) that can exist in more than one process's virtual address space. Shared memory and pipes are random keys as well as their ID to somewhat delay a malicious process from eavesdropping where they shouldn't. Example usage of shared memory:
- Share the application's window's contents with the window manager and/or the graphics driver.
- Implement an application specific method of IPC over shared memory.

There are also "events", which are messages directly from the kernel. The process can get the next event (which can return NULL if nothing is waiting) or atomically sleep until an event is available and then get it (which servers, drivers, and event-driven applications will likely do). Examples of events:
- A message has been received (including the message's ID and size).
- A process has released a pipe or shared memory.
- An IRQ has fired (drivers only).

Though the kernel is designed to be independent of the rest of the operating system (in that it does not care how you implement any drivers or servers), there is exception to this:
- Kernel output (e.g. when a textual message that a process has been terminated because it caused a page fault) is sent as messages to "a\log". "a\log" can be implemented however it wants (printf the message in a text environment, pop up a window in a GUI environment). If "a\log" does not exist, the kernel will panic (it could display the message in text but this brings up the issue of the kernel being dependent on video drivers to switch back to a text-based mode, so the best option would be to send an event telling every process to save its state (if possible) then reboot after a time out).

If you are wondering how the initial processes are loaded (before there is a VFS server or disk drivers loaded), GRUB loads the most minimal requires processes as modules which are used to bootstrap the operating system. An example configuration would be a floppy or hard disk driver, the VFS server, and an initialise program (which handles detecting and loading other drivers and setting up a user environment). These modules are loaded with "driver" privileges, and should downgrade their privileges to an appropriate level.

I have attached my list of system calls (along with what registers they use), though you would likely call these from a high level C interface. For an applications programmer, all of this (system calls, communicating with servers, etc) will be wrapped behind a framework which exposes them as functions like fopen, printf, CreateWindow, OnClick, but that is beyond the scope of this post.

One thing I would like a suggestion on is loading processes. In my current system a process spawns another process by passing a pointer to an executable file in that process's memory. The alternative is that you pass the kernel a path, but I chose this method for these advantages;
- The new process's executable does not have to exist on the file system (it could be extracted from an archive, or streamed over a network).
- It's possible to wrap the ELF executable within a custom file container to provide resources (overcomes the disadvantage below).
The disadvantage of this method is:
- It requires more memory since the the complete ELF executable file must be already in memory of another processes to load it (it can not stream it from disk as it loads). This could be an issue for things like self-extracting archives which may be a 1GB+ executable, but as mentioned above, it is possible for the operating system built on top of this kernel to implement it's own executable file format with the ELF executable being a small subsection of this larger file (then once it is loaded the process can access the rest of it's resources).
- The kernel will be dependent on the VFS.

Processes can also only spawn other processes of an equal or lower class (Drivers->Servers->Applications). How the kernel is bootstrapped is mentioned above.

That is an overview of what my kernel does and is in charge of. Remember that this is a microkernel, and in a microkernel the "kernel" (what is described above) is only a very small part of an operating system. The operating system services like the file system, user management, device management (initialising devices, sorting them), input management, and window management is provided within servers, and their implementation is completely independent of the kernel. I have a large number of servers designed that will run on top of my kernel, as well as an interface for how devices and drivers will communicate, as well as how my application framework will fit in to this design. However, the topic of this thread is strictly the kernel, and I feel that this post has become long enough, and as to not bore potential readers (if I haven't bored you already) I won't begin to explain about the greater OS.

I would also like other people who are working on microkernel to provide an in depth discussion of their kernel, offer suggestions for mine, and share ideas.

[JohnnyTheDon]

Sounds good. A few things I would like to comment on...

Applications (the process name will be prefixed with an "a\") can only directly modify themselves. They can communicate with other processes (particularly with servers) through the kernel's IPC facilities. These make up the majority (hopefully, ALL) of the user's programs.

I would recommend preventing applications from talking to drivers under most conditions. Everything should probably be done through the servers, which will help prevent race conditions and will allow you to do all you permissions checking in the servers instead of the drivers. There will be instances where certain drivers may want to directly expose themselves to user programs, but this should be done on a per-driver basis.

One thing I would like a suggestion on is loading processes. In my current system a process spawns another process by passing a pointer to an executable file in that process's memory.

I would say this is a BAD IDEA. It helps in certain situations, but two big problems with this approach are:
- This will make it easier for any buffer overflow security vulnerabilities to be exploited. Insertion code could consist of a valid ELF excecutable and the few instructions needed to pull off the 'load elf from memory' system call.
- The memory that contains the program code + read only data is now going to be swapped to disk into the normal swapfile. It is much more efficient when the ELF file can be directly mapped from its file on disk and run from there.

Overall a good design. Good luck.

[jal]

Since the design of my nano-kernel is still not getting full shape, I cannot comment on it too much. Basically, it's fully asynchronous, with pieces of code (codelets?) being able to receive a message. Not until a message is sent, a thread is created to run the code. Threads can never block. Once they are done processing, they quit. If a codelet wants exclusive access to some (process) shared variables, it is marked as such (i.e. it doesn't 'ask' for a certain critical section, the critical section is a property of it). Well, this all may change, it's just something we're exploring right now. Being kinda fed up with traditional OS approaches :).


JAL

[itisiuk]

There are also "events", which are messages directly from the kernel. The process can get the next event (which can return NULL if nothing is waiting) or atomically sleep until an event is available and then get it (which servers, drivers, and event-driven applications will likely do). Examples of events:
- A message has been received (including the message's ID and size).
- A process has released a pipe or shared memory.
- An IRQ has fired (drivers only).

im writing a microkernel and ive been working on my event handler.
it seems to get really messy.

currently i just loop and wait to receive a msg as normal but,
it seems to get really slow once events start to increase and as i add more
drivers.

other ways i have found are to used a thread to wait for the event, or a signal handler which messes with the process context.
however i currently not sure how to use threads yet and i really dont want to mess with the process context.

is there a better way todo this.

[elderK]

Messiah, you never seem to answer my questions - how rude.

This is not a Microkernel. You have memory management, scheduling, threading all in the core.

Can you hotswap the kernel's core allocator or schedulers, at runtime?
(If it's a microkernel, you should be able to - since it is not in the kernel)

If so, how do you do the handshaking or phase-out between the core services/servers/tasks, the transmission of state data?

Hotswapping periphery servers is no major issue - a transient error during some userspace request can just be retried.
It's far different when you are dealing with the system's core allocators, interrupt routers, schedulers...
A loss of data there, means the loss of the system.
And deciding to cop out, and cram them all into a static kernel binary, stops you from achieving all kinds of neat things.

Oh and, contrary to popular belief, you can actually have all of the flexibility of a microkernel, without sacrificing speed or
suffering from huge TLB hits or Intel-specific Segmentation.

- Drivers should not be inside of the kernel core.
- Scheduling, should not be inside of the kernel core.
- Interrupt routing - can be run privileged - but need not be part of the kernel core...

Microkernel, people. Pay attention to the /micro/...

~k

[JohnnyTheDon]

This is not a Microkernel. You have memory management, scheduling, threading all in the core

That doesn't mean he HAS to implement it this way. Whens the last time you even thought about switching out your scheduler, let alone while running? Frankly I think keeping everything that makes processes tick in the kernel is a better way to do it. No matter how fast IPC is, a switch from ring 0 -> 3 -> 0 whenever the scheduler needs to run is kind off slow.

[AndrewAPrice]

Messiah, you never seem to answer my questions - how rude.

Ummm...? I don't recall you asking me anything?

This is not a Microkernel. You have memory management, scheduling, threading all in the core.

A microkernel by my definition (which apparently differs from yours) is a kernel where the drivers and the majority of services (except mentioned in my original post) run in userspace.
Exactly what would the kernel do if none of that was in the kernel (well I guess IPC)? With my current design all drivers/servers/applications exist in ring 3. For a driver/server to be able to control memory management COMPLETELY outside of the kernel (and access the page directory) they must have an elevated ring level.

Can you hotswap the kernel's core allocator or schedulers, at runtime?

No. On an end user perspective, what benefit would it have it the scheduler could be hotswapped?

(If it's a microkernel, you should be able to - since it is not in the kernel)

From the OSDev Wiki:

A Microkernel tries to run most services - like networking, filesystem, etc. - as daemons / servers in user space. All that's left to do for the kernel are basic services, like memory allocation, scheduling, and messaging (Inter Process Communication).

What you're describing is more of an exokernel or a nano/picokernel than a microkernel.

If so, how do you do the handshaking or phase-out between the core services/servers/tasks, the transmission of state data?

The kernel provide the IPC primitives and the rest it up to the protocols built on top of it.

It's far different when you are dealing with the system's core allocators, interrupt routers, schedulers...
A loss of data there, means the loss of the system.

I honestly don't see any practical point in hotswapping an allocator, or interrupt routing in my kernel. Your operating system may have a reason for doing this at runtime, however in a desktop OS (which this kernel is part of) I don't see a purpose.

All my kernel's allocator does is map a free page into the process's address space. You may say certain architectures require memory to be allocated in certain areas depending on it's purpose for better performance, and if my kernel ever gets ported to one of those architectures then I will deal with that issue then. But these are architecture specific things (they will be compiled into an architecture specific build of my kernel). The purpose of my kernel still remains; to provide a secure multitasking environment for all processes, they should not be required to deal with architecture specifics (though to a certain extent, drivers will).

- Drivers should not be inside of the kernel core.

Mine aren't.

- Scheduling, should not be inside of the kernel core.

For this a server must be allowed to access the page directory and along with touching task structures.

- Interrupt routing - can be run privileged - but need not be part of the kernel core...

These are, but I believe it would sacrifice security to allow drivers (or an interrupt driver) to write directly to the IDT.

I know we have different views of what a microkernel is, and I appreciate you sharing your opinion. The purpose of my kernel is to provide a an environment for processes to run in that
- is safe from tampering with or being tampered by other processes.
- provides primitives (not protocols) to communicate with other processes.
- gives the illusion that is the only process running (it does not have to be aware of sharing memory/CPU resources with other processes).
- hides architecture specific implementation of features (it needs not know a page table is or that it's running in ring 3).

[jal]

- Scheduling, should not be inside of the kernel core.

For this a server must be allowed to access the page directory and along with touching task structures.

Not necessarily. In my OS design, the scheduler runs in user space, being only concerned with which thread to run when (and on which processor). When it has decided that, it tells the kernel to run that thread, who then updates stuff. My kernel is like a mighty giant - it is stupid, but powerful, and needs its masters to tell him what to do.

- Interrupt routing - can be run privileged - but need not be part of the kernel core...

These are, but I believe it would sacrifice security to allow drivers (or an interrupt driver) to write directly to the IDT.

In my OS design, there's an interrupt manager (running in user space), routing interrupts the kernel has received (and has passed to the intmgr) to the driver(s) that may want them.


JAL

[jal]

Frankly I think keeping everything that makes processes tick in the kernel is a better way to do it. No matter how fast IPC is, a switch from ring 0 -> 3 -> 0 whenever the scheduler needs to run is kind off slow.

Heh, I'll publish the specs of my OS once the basics are running. Currently we're going for a nanokernel, so a simple time tick triggering a thread switch will bounce from 0 to 3 a few times before the new thread runs :). Yes, it is slow, but who cares (well, I don't).

Lemethink: IRQ fires, so switch from 3 -> 0. IRQ message passed to interrupt manager, 0 -> 3. Interrupt manager sends message to timer IRQ handler, 3 -> 0 -> 3. Timer IRQ handler informs scheduler, 3 -> 0 -> 3. Scheduler schedules new thread, tells kernel to do so, 3 -> 0. Kernel runs new thread, 0 -> 3. So that's 8 switches :))).

JAL

[Colonel Kernel]

Frankly I think keeping everything that makes processes tick in the kernel is a better way to do it. No matter how fast IPC is, a switch from ring 0 -> 3 -> 0 whenever the scheduler needs to run is kind off slow.

Heh, I'll publish the specs of my OS once the basics are running. Currently we're going for a nanokernel, so a simple time tick triggering a thread switch will bounce from 0 to 3 a few times before the new thread runs . Yes, it is slow, but who cares (well, I don't).

Lemethink: IRQ fires, so switch from 3 -> 0. IRQ message passed to interrupt manager, 0 -> 3. Interrupt manager sends message to timer IRQ handler, 3 -> 0 -> 3. Timer IRQ handler informs scheduler, 3 -> 0 -> 3. Scheduler schedules new thread, tells kernel to do so, 3 -> 0. Kernel runs new thread, 0 -> 3. So that's 8 switches )).

JAL

That's worse than Minix!

[jal]

That's worse than Minix! :P

Far worse. But then, Minix has a microkernel, we're going for as nano as possible :). It is even very possible that those 8 aren't all. We're seriously contemplating of adding a userland postmaster to manage all the trafic, so that would add at least another two. It just doesn't feel good to have all those blocked messages (yes, we haven't got blocked threads but blocked messages) hanging around in the kernel...


JAL

[elderK]

I don't need to do context switches just to switch a thread
Or, whenever the scheduler fires.

Amethyst is less of a kernel and more of a scaffold, framework, meta-thing.
It is, so that everything else can be

It is dynamic, to the extremes.
Everything and anything, is replaceable at runtime.
Entire "kernel" subsystems can be updated, removed - even when they are in execution.
(Figure that out).

The bootloader isn't complete at time of boot.
Neither is the "kernel".
/Everything/ is dynamic.
Everything, in a weird way, is Objective.

The goal of Amethyst is to offer /extreme/ flexibility, with zero increase to memory overhead.
And, of course, negligible impact to run-time speed.

And, these goals are /indeed/ being achieved.

But, hey, for the record, I do not classify Amethyst as Microkernel.
If anything, It would be a mixture of Nano and Exo.
But, then, It's far crazier than them both.
I just call it a Scaffold. A frame.

It should be noted, too, that it is quite specialized in it's objective.
That and, the backers of my project are quite forceful in the "IT MUST BE PRACTICAL!?!?!?!!?" thinking...

~k, the black mage.
Jal, It's good to see you still around, dude. You're idea seems interesting. It'd be cool to talk about it, in depth, sometime.

[AndrewAPrice]

One thing I would like a suggestion on is loading processes. In my current system a process spawns another process by passing a pointer to an executable file in that process's memory.

I would say this is a BAD IDEA. It helps in certain situations, but two big problems with this approach are:
- This will make it easier for any buffer overflow security vulnerabilities to be exploited. Insertion code could consist of a valid ELF excecutable and the few instructions needed to pull off the 'load elf from memory' system call.
- The memory that contains the program code + read only data is now going to be swapped to disk into the normal swapfile. It is much more efficient when the ELF file can be directly mapped from its file on disk and run from there.

Spawning and loading new processes is what I really need to finalise at this point (it what I'm implementing next). These are some of the methods I'm thinking of:

- The kernel does the loading. A process makes a system call and passes a string containing the file to load, and the kernel spawns a new process and loads the executable. This creates several disadvantages including:

• * The kernel must be made aware of the VFS. Which removes kernel independence.
  * The OS is limited to only loading executable formats that the kernel knows of.
  * The executable must exist on the VFS (we can't load programs from the network, out of an archive, etc, that the VFS does not know about).

- An already running process passes a pointer to the ELF executable (JohnnyTheDon, assume the kernel does bound checks before everything and doesn't overflow). The disadvantages of this system:

• * The executable does need to exist as a file on the VFS.
  * A really large executable will take up memory in the process executing the spawn, though temporarily (mentioned above).
  * The OS is limited to only loading executable formats that the kernel knows of.
  * The kernel is still dependent on the VFS to load dynamically linked libraries.

- An already executing process forks, then calls a library function that loads the new executable in. The loading function call then exist in the application's "high memory" (e.g. 2.95GB (my kernel starts at 3GB)), and the library handles loading the executable from disk, extracting it into memory, then launching it. The points of this are (mixture of disadvantages and advantages):

• * The process must execute it's own writable memory (cannot support Executor Or Write).
  * There must be a quick way for the loading function to release all pages used by the previous process and start in a clean environment (a system call that unmaps every page within a certain range - the loading function can instantly release every page between 0 and 2.95GB).
  * The process is in charge of where it loads the executable from (you can swap the library call for your own to load an executable from a network stream or archive), what executable formats it can read, and loading dynamic libraries (kernel is completely independent from the VFS).
  * Executables must make sure they don't request the loader to allocate/initialise any memory above 2.95GB.
  * This could temporarily use up a lot more memory, imagine a 2GB database program forking to launch a utility. When it initially forks, most page directory/table entries for the forker and forkee are the identical, meanwhile between the time the process was forked and the forkee has done a disk read (to find the path of the file to launch) (before the loading function releases all memory under 2.95GB), the forker has continued to do it task and randomly written to pages throughout the memory, causing each one of these pages to have a local copy inside of the forkee (which may be gigabytes worth of duplicates). This is by far my biggest fear.

- There is a dedicated loader built into the kernel (it's own program, loaded as a GRUB module). A process makes a system call with a path (or other unique string identifying what to load) to the kernel. The kernel sets up a process, copies the loader program into the process's memory
and passes the loader the unique string. The loader program (operating in user mode) then is responsible for retrieving the executable and loading it.

• * The loader can be replaced to support custom executable formats, and also loading files from alternative sources (as long as the source can be serialised), but the system needs to be rebooted to modify this (unless a second stage loader is then called which takes over).
  * The loader is in charge of loading dynamically linked libraries and the sort, freeing the kernel from being dependent on the VFS.

The third method of forking then using the library function seems like the best way to go. I'm also looking for various methods that I haven't thought of yet.

[JohnnyTheDon]

How about an execution server? The execution server can handle interacting with the VFS and any file formats you want to use. It just needs system calls from the kernel to create a new process and edit the address space (map in executable file, setup .data,.bss, etc). Depending on how you plan to do disk mapping this should work just fine. This also allows you to support fork as well.

[AndrewAPrice]

How about an execution server? The execution server can handle interacting with the VFS and any file formats you want to use. It just needs system calls from the kernel to create a new process and edit the address space (map in executable file, setup .data,.bss, etc). Depending on how you plan to do disk mapping this should work just fine. This also allows you to support fork as well.

I like the idea of an execution server, I will need a few changes to the kernel to support this;

• - A server must be able to spawn a blank process. This is fair enough, but how would you spawn drivers? (Processes can only give themselves less privileges not more.) Could not a malicious server spawn a new process as a driver, and copy itself into the new process? (Unless the execution server was actually an execution driver, or instead of the linear privilege levels of Driver->Server->Application, Server could branch into 2 different directions, Driver and Manager (manager being able to spawn processes of any privilege level and access their memory)).
  - A server (or manager) must be able to set the instruction pointer and access other processes' memory without the permission (I could introduce a "spawning" state for processes, and this is only possible while in the spawning state).

Spawning processes within an execution server will also allow the flexibility to introduce security without any change to the kernel (e.g. check that the requesting process's user privileges allow it to execute this file).

I'm writing a design document which I'll post here when I've finalised the kernel's design (including overview and reasoning, implementation, and programming guide). It won't be final because the kernel is likely to evolve as I run into challenges along the way.