dthain / basekernel

A simple OS kernel for research, teaching, and fun.

The Basekernel Operating System Kernel

Basekernel is a simple operating system kernel for research, teaching, and fun.

Basekernel is not a complete operating system, but it is a starting point for those who wish to study and develop new operating system code. If you want to build something different than Windows, Linux, or Multics, Basekernel may be a good place to try out your new ideas.

Basekernel can boot an Intel PC-compatible virtual machine in 32-bit protected mode, with support for VESA framebuffer graphics, ATA hard disks, ATAPI optical devices, process management, memory protection, simple graphics, and basic filesystem. From there, it's your job to write user-level programs and expand the system.

To be clear, this is raw low-level code, not a production system. If you want to hack code and learn about operating system, you will like Basekernel. If you are looking for a new OS to run on your laptop, then this is not what you want.

This project is led by Prof. Douglas Thain at the University of Notre Dame. A variety of students have contributed to the code, including Jack Mazanec, Douglas Smith, Ethan Williams, Jon Westhoff, and Kevin Wern.

To learn more, see the Basekernel Wiki.

Quick Start Instructions

If you are building on a Linux-X86 machine and have the QEMU virtual machine installed:

git clone https://github.com/dthain/basekernel
cd basekernel
make
qemu-system-i386 -cdrom basekernel.iso

And you should see something like this:

After some initial boot messages, you will see the kernel shell prompt. This allows you to take some simple actions before running the first user level program. To automatically boot the first available filesystem, whether on cdrom or harddisk, run automount:

automount

Then use the list command to examine the root directory:

list /

And use the run command to run a program. For example, /bin/manager.exe runs a simple four-pane window manager with several tasks in parallel. (Use TAB to switch focus between programs, and tilde to cancel out of the window manager.)

run /bin/manager.exe

Press TAB to change the focus between windows, and you can interact with each process in turn.

Cross-Compiling Instructions

If you are building on any other type of machine, you will probably need to build a cross-compiler using build-cross-compiler.sh and then edit Makefile.config to use the cross compiler binaries, then execute make to create basekernel.iso

basekernel's Issues

Process Memory Management

Right now, a process is allowed to touch any page within its virtual address space. If the page does not have a frame allocated, the page fault handler allocates and puts one it. That makes things easy for the user, but doesn't allow us to rationally limit the memory used by each process.

Implement a more controlled management scheme similar to that of Unix:
1 - Allow a process to request an increase/decrease in heap size relative to the original break point.
2 - Allow a process to automatically extend the stack by touching the page just below the current stack top.

There are some boundary cases to consider, if the page allocation should fail, or the heap run into the stack.

Process window API

We need a syscall for updating a window. I am working on it here: https://github.com/JohnathonNow/basekernel/tree/feature/windows
but there are a few questions that need to be answered:

1. Should the process be aware of anything about a window it owns?
2. Should processes be allowed to have more than one window?
3. When a process constructs a command for redrawing a window, should this command be stored internally as readable text, or should it be stored in some other form, such as an array of bytes, where a byte might indicate what command follows, along with some bytes following the command byte as arguments?

test.exe no longer works

On the current master when I do run TEST.EXE I get the following output:

Mixed tabs/spaces

In some areas (e.g. kshell.c), we have a mix of tab and 4-space indentations. We should probably do a quick search/replace to get everything back to only tab characters.

Sort Out I/O Abstractions

(Project notes have very limited text, so this seems like a better place to document a discussion.)

We need several kinds of abstractions related to I/O in the kernel that will sit on top of some of the existing code. For example, sys_run invokes cdromfs directly since that's the only filesystem we have. But we need abstractions that will hide and unify multiple implementations.

The ones that come to mind are:

• File (e.g. /etc/hosts)
• Filesystem (e.g. cdrom or ufs)
• Device (e.g. ata or scsi)
• Stream (e.g. pipe or terminal)

Before writing a whole mess of code, try sketching this out in the form of a header file that defines the operations possible on each one, and let's argue about that for a while before digging into the implementation.

Crash on filesystem access.

@kevinwern with the latest merge including kevinfs, loading a program from the cdromfs results in a crash, please take a look:

Can't access root dir in qemu

Run these commands to reproduce with a freshly-cloned copy:

make
qemu-system-i386 -fda basekernel.img

Am I doing something wrong (if so, we should adjust README.md) or is this a bug in the OS?

Try Basekernel on Real Hardware

Burn a basekernel cdrom and try it on real hardware, see how far it gets, and report back on any problems.

(Access to a suitable VBE video mode in BIOS may be a problem.)

Makefile Issue with target all

Using make with a clean project (without test.exe prebuilt), the build fails:

genisoimage: No such file or directory. Invalid node - 'test.exe'.
Makefile:13: recipe for target 'basekernel.iso' failed
make: *** [basekernel.iso] Error 2

I think the traget all should be:
all: test.exe basekernel.iso

Add Process Numbers

Here is a small project to gain familiarity with all of the various layers of the system:
Add system calls to return the current process number (getpid) and the parent process (getppid):

• Modify process.[ch] to generate a unique incrementing id each time a process is created.
• Modify syscall_handler.[ch] to handle the new system calls.
• Modify syscalls.c to implement the user side of the system calls.
• Modify test.c so the user level program can invoke them and print the results.

@JohnathonNow this would be a good one for you to work on.

More precise formatting

Maybe not such high priority, but, for instance, it's hard to create a real-time clock with 0 padding because format modifiers such as %02d are not available.

graphics_line negative w/h support

Very minor: graphics_line requires w and h have the same sign, but it might be useful to allow for opposite signs, for things like drawing a polygon as a list of line segments.

Terminal does not like capital 'W'

And the reason why isn't readily apparent...

Add debugging page to wiki.

@kevinwern please add a page to the wiki describing the gdb-qemu technique that we discusses this week.

Mount command hangs on qemu

So mount 2 will not work, but hard coding 2 where it is needed will make it run correctly.

Not sure what the reason for that is.

Help Command in Kernel Shell

Easy one: help should show a list of commands in the kernel shell.

Add Current Time Call

Add a gettimeofday system call which pulls the current time out of the rtc device and presents it seconds-since-the epoch to the user.

Console doesn't show all of error messages / process dumps

When the exception handler calls process_dump, it is likely to cause the console to overflow and clear, which causes most of the dump to be invisible as it has been cleared.

I would suggest adding "\f" to the start of the console_printf calls on line 44 of interupt.c and line 54 of interupt.c. This would allow the whole error message and process dump to be visible to the user.

Lowercase CDROM filesystem

Currently, the CDROM filesystem reports back all files in uppercase, which is quaint but not really necessary. Fix this as follows:

• Adjust the driver to report back all file names in lower case.
• Adjust the file name matching so that names provided in lower-case match the internal upper-case.
• Adjust our documentation to match.

This will be handy down the road when we want the cdrom filesystem to be swappable for other more capable filesystems...

Change Console Userland Commands to use kobjects and not shortcut

Mount Command in Kernel Shell

Add a new command mount to the kernel shell which takes a device number, attempts to load a filesystem, and then stores the root dirent as a global variable root_directory. Then, you can make list and run relative to the current working directory and mount whichever unit you want.

Fix dot and dot-dot in cdromfs

cdromfs_readdir handles dot and dot-dot, but cdromfs_lookup does not.
@TBurchfield will fix it.

Switch video modes from inside kernel?

I see work being done on querying the video mode before the kernel boots up. Could it be done such that switching video modes is possible from within the kernel? The only example of such code Ive seen using VESA is using a virtual x86 mode thread and making the switch, but I dont know enough about VESA to be certain.

btw, thanks for your efforts. Im seriously considering switching my project to use your core, but I really need a VESA method to switch from 320x640x256, 640x480, and text 25x80. (Mine just uses a VGA driver)

https://github.com/xlar54/emudore64

(Edit: I also have the beginnings of a FAT32 filesystem that may be useful to this project, unless filesystems are outside the scope and intent)

printf_putint: can overflow for large ints

In the code where we determine the highest place value for large ints, we have:

    while((i/f)>0) {
            f*=10;
    }
    f=f/10;

Problem is, this means f must go one place value higher than the actual number. Meaning that 2*10^9 will require f to be 10^10, which would overflow for 32-bit ints and render the remaining calculations incorrect.

Build a user-level shell.

Build a simple user-level shell that can take simple actions on the filesystem (mount, list, copy, etc) and stop and start child processes. Use this opportunity to make sure that all of the needed functionality is available via well-formed system calls. Once this is working, remove the kernel shell and replace it with an invocation of the user-level shell.

Dynamically Console Devices on top of Graphics

ATAPI Probe on Virtual Box

ATAPI (CDROM) devices are not detected when running on VirtualBox.
(They are detected with Bochs)

Add section to wiki about kernel objects

Use a cross-compiler

You should not use the system compiler for operating system development. Use a cross-compiler instead. You should not pass -m32 and -march to your compiler. Your system gcc is likely to come from the package management of your distro, so you have no way of knowing what release it will break. Additionally, your system compiler targets a hosted Linux requirement, which obviously is not a freestanding environment. Lastly, compiling the kernel on a different architecture will obviously break everything (try compiling this on a Raspberry Pi!). System compilers are too different and will break the code way too often, likely even in silent ways you won't notice right now but will some time down the road in the form of mysterious bugs.

Backspacing doesn't handle characters, just moves cursor back and overwrites character

Which means that newlines are treated like single spaces extending to the end of the line.

Add a few standard library headers (suggestion)

If we want to start working on support for the C standard library, we should add a few of these headers: stdarg.h, stddef.h, stdint.h, limits.h, stdnoreturn.h, stdalign.h, and stdbool.h.

Add VBE Mode Querying

Right now we just use preset VBE modes, but these have been deprecated. I am working on adding querying on a branch of my fork: https://github.com/JohnathonNow/basekernel/tree/feature/video-mode

Implement ELF Format

Currently, programs are loaded in the form of a "binary blob". We just take the raw assembly, dump it into user space, and jump to the first location.

Let's take the next step towards loading the a.out binary format (Linux variant). This is pretty straightforward: read the program header, allocate space for code, data, and bss, load the code and data into the appropriate place, and then jump to the proper program entry point.

(@JohnathonNow observed that the current binary blob doesn't event convert bss into data, so empty globals don't even appear in the program image!)

Filesystem

See here.

Basically, I created an inode-like filesystem and I think it would be worthwhile to use this as a starting point. I've been using the function calls directly to test it, but I think that if we can get something simple that "just works" out of this, that'd be great.

We can discuss this on Thursday, but my goals would probably be something along the lines of:

• A user can easily format a blank disk and have a bootable image that primarily uses this FS.
• You can do very basic operations to read/write files.
• At a normal user level, things do not break (easily)

There are definitely tons of things I haven't done, like enforcing allowed characters, implementing multi-level path strings, and reserving a boot section for booting from the same disk. Then, there things that can be simplified--inodes/data could be a union instead of being a buffer, "commit types" have an unnecessary level of distinction/verbosity.

Maybe we can call this a meta-issue? I'm not sure if Git Issues has that concept.

VirtualBox Crash after running ~10 Processes

If I do

mount 1
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE
run TEST.EXE

on a build of the current master of basekernel in VirtualBox, I get the following error:

Cross compiler build fails

When I run the build script for the cross compiler on an installation of Arch Linux it fails:

g++ -no-pie   -g  -DIN_GCC  -DCROSS_DIRECTORY_STRUCTURE   -fno-exceptions -fno-rtti -fasynchronous-unwind-tables -W -Wall -Wno-narrowing -Wwrite-strings -Wcast-qual -Wmissing-format-attribute -Woverloaded-virtual -pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings   -DHAVE_CONFIG_H -static-libstdc++ -static-libgcc  -o lto1 \
	lto/lto-lang.o lto/lto.o lto/lto-object.o attribs.o lto/lto-partition.o lto/lto-symtab.o libbackend.a main.o libcommon-target.a libcommon.a ../libcpp/libcpp.a ../libdecnumber/libdecnumber.a  -lmpc -lmpfr -lgmp -rdynamic -ldl  -L./../zlib -lz libcommon.a ../libcpp/libcpp.a   ../libbacktrace/.libs/libbacktrace.a ../libiberty/libiberty.a ../libdecnumber/libdecnumber.a 
collect2: error: ld returned 1 exit status
make: *** [../../gcc-7.2.0/gcc/lto/Make-lang.in:81: lto1] Error 1

I am running the 4.9.69-1-lts kernel with gcc version 7.2.1 20171128.

Any advice?

cdromfs checks volume 0 forever (or at least longer than I care to wait)

If I load the basekernel.img file as a floppy, if an IDE disk controller is present but there is no disk, in both qemu and virtualbox it hangs forever. Disabling the unused IDE controller gets around this.

Process stack virtual address calculation

I noticed when working on setting up passing argv and argc to processes that I could not write to any address in the stack before 0x0FF0 bytes down. That seemed strange, until I realized that the stack starts 0xF from the end of memory, meaning that I couldn't write to the page assigned to the end of memory at all. I eventually thought it might be related to how pages are assigned, so I did some math. So, for the top of the stack, 0xFFFFFFF0, we have 0xFFFFFFF0 - 0x00001000 passed in as the argument to to pagetable_alloc here.
0xFFFFFFF0 - 0x00001000 = 0xFFFFE000 0xFFFFE000 & 0xFFFFF000 = 0xFFFFE000, which is the page before the one we wanted. To test, I added a debug message to the page fault handler, and sure enough, as soon as a process starts it page faults and gets the top page allocated for it.

This isn't intended, right? Should the line in process.c read
pagetable_alloc(p->pagetable,PROCESS_STACK_INIT-stack_size + 0x10,stack_size,PAGE_FLAG_USER|PAGE_FLAG_READWRITE); instead?

Add User-Space Functions

We are going to need some simple user-space libraries in order to build slightly less non-trivial user-level programs. The kernel module string.c is a good starting put, since that is fairly pure code, excepting the use of console_write in printf. Adapt that module so it can be used in a user-level program, so that printf invokes debug. Then, you can use printf from user space.

@JohnathonNow also a good one for you to work on, after adding the system calls.

Automated testing

Pick something and use it as a starting point for automated testing. Preferably something that's easily comparable, as things like graphics/console/disk would require code to be able to compare outputs. My thought is either memory allocation (perform some memory operations and see that memory is structured how we expect), data structures (list), or output formatting (although that would require some modification so we have an interim string before printf happens).

Solve Race Condition in ATA

When issuing an ata/atapi read/write, the ata driver should generally call process_wait() to wait for an interrupt to arrive. However, on "fast" virtual hardware, the interrupt is often delivered even before process_wait() has been called. Hence, the current code has these waits commented out, and just does a busy-wait on drive status.

Fix the race condition by blocking interrupts in the critical section, so that we can properly handle "slow" real hardware without busy waiting.

See PR #72 for an instance of the problem and PR #82 for the temporary workaround.

Different video mode, strange output

VirtualBox, setting mode to 800x600.

Linker errors on GCC 6.3 and 7.1

Using GCC 6.3.0, running make yields:

cc -Wall -c -ffreestanding -m32 -march=i386 bootblock.S -o bootblock.o
ld -m elf_i386 -Ttext 0 -s --oformat binary bootblock.o -o bootblock
cc -Wall -c -ffreestanding -m32 -march=i386 kernelcore.S -o kernelcore.o
cc -Wall -c -ffreestanding -m32 -march=i386 main.c -o main.o
cc -Wall -c -ffreestanding -m32 -march=i386 console.c -o console.o
cc -Wall -c -ffreestanding -m32 -march=i386 memory.c -o memory.o
cc -Wall -c -ffreestanding -m32 -march=i386 keyboard.c -o keyboard.o
cc -Wall -c -ffreestanding -m32 -march=i386 mouse.c -o mouse.o
cc -Wall -c -ffreestanding -m32 -march=i386 clock.c -o clock.o
cc -Wall -c -ffreestanding -m32 -march=i386 interrupt.c -o interrupt.o
cc -Wall -c -ffreestanding -m32 -march=i386 kmalloc.c -o kmalloc.o
cc -Wall -c -ffreestanding -m32 -march=i386 pic.c -o pic.o
cc -Wall -c -ffreestanding -m32 -march=i386 ata.c -o ata.o
cc -Wall -c -ffreestanding -m32 -march=i386 cdromfs.c -o cdromfs.o
cdromfs.c: In function 'cdrom_dirent_readdir':
cdromfs.c:95:5: warning: assignment from incompatible pointer type [-Wincompatible-pointer-types]
   d = ((char*)d)+d->descriptor_length;
     ^
cc -Wall -c -ffreestanding -m32 -march=i386 string.c -o string.o
cc -Wall -c -ffreestanding -m32 -march=i386 bitmap.c -o bitmap.o
cc -Wall -c -ffreestanding -m32 -march=i386 graphics.c -o graphics.o
cc -Wall -c -ffreestanding -m32 -march=i386 font.c -o font.o
cc -Wall -c -ffreestanding -m32 -march=i386 syscall.S -o syscall.o
cc -Wall -c -ffreestanding -m32 -march=i386 syscall_handler.c -o syscall_handler.o
cc -Wall -c -ffreestanding -m32 -march=i386 process.c -o process.o
cc -Wall -c -ffreestanding -m32 -march=i386 mutex.c -o mutex.o
cc -Wall -c -ffreestanding -m32 -march=i386 list.c -o list.o
cc -Wall -c -ffreestanding -m32 -march=i386 pagetable.c -o pagetable.o
cc -Wall -c -ffreestanding -m32 -march=i386 rtc.c -o rtc.o
ld -m elf_i386 -Ttext 0x10000 -s --oformat binary kernelcore.o main.o console.o memory.o keyboard.o mouse.o clock.o interrupt.o kmalloc.o pic.o ata.o cdromfs.o string.o bitmap.o graphics.o font.o syscall.o syscall_handler.o process.o mutex.o list.o pagetable.o rtc.o -o kernel
main.o: In function `kernel_main':
main.c:(.text+0xe): undefined reference to `_GLOBAL_OFFSET_TABLE_'
console.o: In function `console_reset':
console.c:(.text+0xc): undefined reference to `_GLOBAL_OFFSET_TABLE_'
console.o: In function `console_writechar':
console.c:(.text+0xf0): undefined reference to `_GLOBAL_OFFSET_TABLE_'
console.o: In function `console_heartbeat':
console.c:(.text+0x13c): undefined reference to `_GLOBAL_OFFSET_TABLE_'
console.o: In function `console_putchar':
console.c:(.text+0x1ce): undefined reference to `_GLOBAL_OFFSET_TABLE_'
console.o:console.c:(.text+0x2fa): more undefined references to `_GLOBAL_OFFSET_TABLE_' follow
Makefile:20: recipe for target 'kernel' failed
make: *** [kernel] Error 1

This does not happen with either GCC 4.7 or GCC 5.4.

Mount doesn't always work

If the first command I enter is mount 2 cdrom, the mount succeeds. Strangely, if I do anything before running that command, it hangs when I do. I was traced the problem to this statement:

return f->mount(device_no);

I think it's supposed to call this function, cdrom_volume_open, but a debug print statement at the beginning of it is never reached.

Add Wait System Call

Add a system call that causes the calling process to block for a specified amount of time using the kernel clock module. Update the sample user level program to use it.

Try Enabling Preemption

Once we have a basic libc and processes that can display their own pid, go into process.c and turn on allow_preempt which should enable periodic preemption via clock_interrupt(). Run two or more processes from main that display something different, and let's see if preemption works!

KevinFS: Add support for indirect blocks / large files.

Add support for indirect blocks to kevinfs, so that it can access files larger than a few kilobytes. Once that's working, try double-indirect and triply-indirect up to a reasonable maximum file size.

Implement Process Relationships

Next step: build up the user visible process management API. We are going to do things a bit differently from Unix, in order to have better control over resource management. Here is the idea:

• process_run( path, args ) - Creates a new child process running the indicated executable and arguments, returns the process id.
• process_exit( status ) - Terminates the current process and all of its children, indicating an integer status to the parent.
• process_kill( pid ) - Terminates the indicated process and all of its children, indicating that the process tree was killed to the parent.
• process_wait( &info, timeout ) - The caller waits to see if any of its children have terminated. If one has, then return the relevant information (pid, status, etc) into the info structure. This only works for the immediate parent of a process on its children.
• process_reap( id ) - Remove the termination record for process id

Kernel Objects Needs Window Type that points to Graphics Object

Once that works we want to collapse the window table into the file/kobject descriptor table.

Add caching layer to fs

We tend to favor looking up dirents/inodes repeatedly in cases where we need the properties of a directory or file multiple times, so create a caching layer to reduce our overhead from these lookups.