GR8NIX

GR8NIX, the breadboard operating system

GR8NIX, first time running a program.

GR8NIX, first time running a program.

GR8NIX is an operating system inspired by Unix, a simple multi-user, multitasking operating system made in the 1970s. Modern operating systems based on unix's ideas include Linux, MacOS and Android, among others.
GR8NIX is written in assembly, for GR8CPU Rev3. It is made of over 2000 lines of hand-written assembly, totalling over 5 kilobytes and counting.
Technical details include:

  • Multithreading supporting 32 concurrent threads.
  • A theoretically unlimited number of running programs, limited by number of threads.
  • Dynamic memory allocation, with a current size of up to 8 kilobytes.
  • True position-independent execution for programs.

However, GR8NIX isn't perfect.
Due to hardware constraints, GR8NIX cannot:

  • Protect memory from a process.
  • Recover from attempting to run an invalid instruction.
  • Reliably prevent memory leaks after a process exits.

initial development & memory management

The first 37 lines of the memory allocation code for GR8NIX.

37 of the 600+ lines of the code for memory allocation.

The initial development of GR8NIX was slow. Indeed, months after starting the project, i just finished running programs.
In the image, you see only 37 of the 600+ lines of memory allocation code. Memory allocation is one of the first features is started work on, due to it's importance in nearly everything else. Everything from typing in a command to running scheduled tasks relies heavily on the ability to get memory on demand.
This feature wasn't easy to make: not only was it the first that i started work on, but also it was relatively hard. I took a look at how modern systems implement memory allocation: basically a linked list of free chunks of memory. There is a problem with that approach in that pointers may be fast, but they're really hard to deal with.

How malloc uses a table to signify what memory is used.

How malloc uses a table to signify what memory is used.

My implementation of malloc works by having a table of 256 bytes in size. This table uses one byte to represent 32 byte "blocks" memory. This then allows 8192 bytes (8 kilobytes) to be allocated in total, unless i make blocks bigger or add more of them. A byte in the table corresponds directly to a fixed place in memory, and works as follows:

  • 0x00 is free memory that may be allocated.
  • 0x03 is the first "block" of allocated memory.
  • 0x01 is a number of blocks after 0x03, used to know the size of an allocated area. There may be any given number of these, from none to filling up the entire table.
  • 0x02 is reserved memory that may never be allocated.
  • Any other combination will not be allocated either.

This way of implementing malloc allows me to easily test various things that need memory, with a quick overview of what memory is and is not in use. I will likely make the area that can be allocated much larger in the future.

the filesystem

A file loading successfully from disk.

A file loading successfully from disk.

After getting the memory management workable, it's on to filesystems. The filesystem is essential to the Unix philosophy, as it states that everything is a file. Even without that, the filesystem is required to run programs and store data more permanently than RAM.
So, i had to think up my own filesystem. This, too was no easy task. What i decided to do in the end was borrow an idea from the FAT (ms-dos) filesystem. The FAT filesystem has a table describing all of the space on disk, as a sort of list where each block points to the next. This filesystem can store up to 65535 blocks of 256 bytes, for a total just under 16 megabytes.

An overview of how SimplexFS works.

An overview of how SimplexFS works.

This image illustrates what i just said: just like with memory allocation, there is a table which describes what part of the disk is in use. In this case, however, this also forms a chain of blocks, a linked list if you will. This list is used when reading a file, allowing a file to be larger than 256 bytes. An entry in the allocation table is one of the following:

  • 0x0000 is free space on disk.
  • 0xffff is used space on disk, the last block of a file. This is used as both the first and last block at once, given the file size does not exceed 256 bytes.
  • Any other number is a pointer to the next block, as well as used space on disk. This part creates the linked list that is large files.

Although not yet implemented, writing files is relatively simple: All you do is write to disk, finding yourself a new free block to use every 256 bytes.

programs & exec

In the video you can see gr8nix come to life: it successfully loads and runs a shell program, which in turn loads and runs any other programs you wish.

How a program loads and runs.

How a program loads and runs.

Now, it's time for real talk: how does a program get executed?
First, exec is called: exec is the function responsible for loading programs and running them. Exec first does some sanity checks: does the file exist? is it a program file? is it a valid one? Next, exec goes to find the length of the executable by checking every section entry and adding it's offset to it's length. The length found by exec is the highest of these calculated lengths.
After this, exec calls thread_launch, a method used to prepare to start a thread. Exec finishes by adding some metadata to the process: it's PID, it's user ID, a pointer to the memory allocated, how long said memory is, the command line that was run, and the working directory among a number of other things.

where i am now

GR8NIX, first time running a program.

GR8NIX, first time running a program.

From here, i need to make a list of other features to make programs more useful. The most important features include:

  • Writing to the filesystem.
  • File descriptors.
  • Path to working directory.
  • Device drivers.