What is virtual memory?

Lately I have been working on the virtual memory system. Now most of you out there won’t know what virtual memory is, so here is a brief explanation.

Virtual memory is the mechanism used to make all tasks think they’re the only task running on that system at any given time, unless communication through memory is desired, in which the operating system makes that possible through a mechanism called shared memory.

That’s virtual memory in one full sentence. If you still don’t get it, that’s perfectly understandable. So here is an explanation which is a tiny bit longer. It explains the goals of virtual memory and explains different approaches to solving the very same problem.

When writing the code for any particular task on any system it’s a nuisance, to say the least, to have to keep the possible existence of other tasks on that system into account. The sole role of the operating system is to help other tasks run, and so what it does, is try to give the entire memory space, to each and every task.

While the whole memory space won’t be possible due to technical restrictions (the kernel itself must be somewhere in memory as well), quite a lot can be made available to user space (that’s where user tasks run).

One of the ways to get this all to work is to have each task ask the kernel for more memory each time they need it, while keeping all the data available to all the other processes. Sometimes, on architectures which don’t support memory protection, this is the only way to go forward.

Another way is to have the processor translate the virtual addresses into physical ones while the kernel concerns itself with the allocation of physical pages (a page is a chunk of memory of a predefined size). When a process isn’t allowed to access a particular physical page, it is simply not mapped to any virtual address at the moment that task is running (again, besides the kernel, but this region of memory has other ways to protect itself).

The advantage of the latter approach is that in this model it isn’t possible for one task to modify critical data or code in the other task. When it is desired to have two tasks sharing a region of space, that can be accomplished by mapping virtual pages in both tasks to the very same physical pages.

Printf flavours

I’ve been working on several things in the kernel lately. Among them are the slab allocator and the different flavours of the printf function (some of them).

I’ve now finished work (mostly) on these printf functions and I’m happy to present:

1. sprintf,
2. vsprintf,
3. fprintf and
4. vfprintf.

These functions have better formatting support than the current printf function. So in order to use these new formatting features one will have to make a string, format it using sprintf and then print it using printf.

As soon as we have a better self cleaning buffer in the kernel, we’ll implement it in the vga-text driver and make a new printf function that uses fprintf to write to stdout (which is connected to the driver).

Also work on the slab allocator is progressing, albeit slowly. There’s a lot of thinking involved in building a slab allocator, and I’m hoping to do it well the first time. This means there’s even more thinking involved.

Also this slab allocator will have to be used for page allocation, which makes the slab allocator come with a couple of restrictions (we can’t just assume we’ve got space everywhere outside of the text segment and annoying details like that). So for now we’re still using the slob (single list of blocks) allocator to do all the memory allocation for us, but we’re looking forward to a functional slab allocator (probably done in a couple of weeks).

That’s it for now!

OSdev resources

I know a couple of people interested in OS development but no clue on where to start, and even though I occasionally show them one or two of the sites I get my information from this blog post is supposed to give them a better set of pointers to documentation.

I started programming in C using a good tutorial on cprogramming.com. Now I understand if this isn't enough for you and one book I highly recommend is the C programming language by Kernighan and Ritchie. Those are the two men behind the language and they've found a way to describe the language in a simple and brief way.

Also something worth learning, although not absolutely necessary when joining an existing project is a form of assembly language. I personally got started with the art of assembly, and honestly haven't found a better resource yet.

Now we have some grasp of what it means to be a programmer, we can start thinking about a simple kernel. For that we'll go to a man called James Molloy. He's written a tutorial which is very easy to understand. It might not be the most powerful and flexible kernel out there, but it'll get the job done for a first kernel. Also there's this beautiful wiki on how to do some things not covered in the tutorial.

Another tutorial that may interest you is one that follows the Windows path a little bit more as opposed to the Unix route used by James Molloy. I'm now talking about the brokenthorn web book. This is one of the first tutorials I've found on the subject and although I didn't take it's path it has taught me quite a lot.

The VFS

The virtual file system(VFS) is one of the most important parts of the operating system. It handles communication with permanent storage. In our case the VFS doesn't handle the file operation them selves but requires the file system to give us function pointers to work with.

A file in our VFS is nothing more than a data structure with a pointer to the file system driver file, which itself is attached to one of the permanent storage devices. This might seem complex but it does provide us with a whole lot of possibilities, which are provided not only by our system but also by others like Linux and BSD.

The file system mounts still have to be written though so I still can't go too deep into the implementation details of those.

One thing we already have working though is a special kind of file we call a buffer. When we open a file with the initialiser function of the buffer it loads all of its functions into the function pointers of the buffer and now allows us to read from, write to, seek in and close the buffer like it's a normal file somewhere on a disk. Internally it keeps all the data in the form of a tree and when it's time to close the buffer, while no other part of the application has opened it, it will remove all of it, which is quite unlike a normal file.

Because of the index variable, which is 64 bits, the buffer supports files of up to 16.000 PiB. If you don't know what that means. Well, lets just say that it's plenty for the coming decade if not more (I personally have trouble filling my 320 GiB, and that's roughly 0.002% of the buffer …).

The driver model

Since the beginning of this year we've been busy in the Andromeda team. One of the things we've been working at is the driver model. Our design is fairly simple, and I think I can explain it, so here we go.

The device model consists of a tree of devices. Starting with the root device. This is a virtual device to which everything is attached in some form. Attached to this device are for example the CPU's, memory, the PCI bus and some virtual buses.

The reason for choosing a tree instead of a plain list of devices is simple. When the system is to shut down or to suspend, we want to disable the devices first, then the buses and last the power supply (if necessary). If we're to walk a plain list things are to shut down in random order which might get interesting since for example the PCI bus has been shut down before the graphics card is so it never receives the shut down signal.

The reason why the CPU's, Memory and PCI are attached to the root device are simply the fact that they are at the head of the system. The reason for the virtual buses might not be so obvious yet.

There are 2 virtual buses. One for virtual devices which reside in memory and don't really have to be suspended, and can't have physical hardware attached to them, and then there's the legacy devices. These can be the VGA and PS/2 controller to name a few.

Devices in the model are nothing more than data structures with a file pointer, open function, name/unique identifier, driver pointer and a void pointer for special data structures. When interaction with the devices is needed, the device file can be opened and written to. The device might respond and by reading from the device file the answer can be retrieved.

In the case of a permanent storage device this file can hold pointers to partitions which can in turn hold files which can then be mounted to the VFS.

What we've been up to

I know, it's been a long while, and quite a bit has happened since.

A summary of what's been done:

1. A driver model has been designed and implemented and is nearing completion (aside from the actual implementation of drivers).
2. A virtual file system has been designed and implementations are on the way.
3. Network stack development is currently being done by Michel.
4. Ideas have formed on a new memory allocation algorithm.

Now this doesn't sound like much but for two people it's quite a bit of work, considering the fact that in the design of core features in the kernel we prefer to guarantee quality.

In following posts we'll go deeper into the separate items.

• The driver model
• The virtual file system

Cleaning up

Currently a lot of work is going into getting the repository clean again.

A lot of files have been placed in directories where they shouldn't be. For example, the directory src/sys shoudn't have existed.

We've been moving most files out to where they ought to be. For example, the error directory, which contained the panic function, has been moved to the kern directory, which by the way has been renamed to andromeda.

This generated a file name conflict with the output binary, and as such we renamed that to andromeda.bin.

In the mean time I've been working on support for multitasking. We've covered quite a lot of ground there, but as we speak a lot of code still has to be written. For example, we still don't have the possibility of switching contexts. Something I think is mandatory for multitasking. Now of course it can be done through some weird function pointer using scheduler, but I personally prefer to go with a traditional task switch.

What does that mean?

Well, basically it means that when an interrupt comes along, before we do anything else, we push all our registers to stack. When the interrupt is handled a couple more functions are called, probably pushing more onto the stack.

When the time comes to switch tasks, what we do is we only store the stack pointer, just before the moment we swap the memory context, by loading another page directory pointer.

When we have to load the old task again, all we have to do is first restore the directory pointer, and then use a link in kernel space (which is always present) to restore the stack pointer.

When we then return to the interrupt handler, the registers will be restored to the state when the process was interrupted and the interrupt will be finished.

Basically that's the normal task switch. Does it sound complex? A little. Does it have to be this way? No, but it sure is the most extensible way of doing things. When a new register is added, all we have to do is remember to push in onto the stack in the interrupt handler and the rest can be dealt with in a more generic location.