PatchworkOS

PatchworkOS is currently in a very early stage of development, and may have both known and unknown bugs.

desktop screenshot

Patchwork is a monolithic non-POSIX operating system for the x86_64 architecture that rigorously follows an "everything is a file" philosophy. Built from scratch in C it takes many ideas from Unix, Plan9 and others while simplifying them and adding in some new ideas of its own.

In the end this is a project made for fun, however the goal is still to make a feature-complete and experimental operating system which attempts to use unique algorithms and designs over tried and tested ones. Sometimes this leads to bad results, and sometimes, hopefully, good ones.

Additionally, the OS aims to, in spite of its experimental nature, remain approachable and educational, something that can work as a middle ground between fully educational operating systems like xv6 and production operating system like Linux.

Features

Kernel

• Multithreading with a constant-time scheduler, fully preemptive and tickless
• Symmetric Multi Processing without any "big locks"
• Physical and virtual memory management is O(1) per page and O(n) where n is the number of pages per allocation/mapping operation, see benchmarks for more info
• Dynamic kernel and user stack allocation
• File based IPC including pipes, shared memory, sockets and Plan9 inspired "signals" called notes
• File based device APIs, including framebuffers, keyboards, mice and more
• Synchronization primitives including mutexes, read-write locks and futexes
• SIMD support

ACPI

• From scratch and heavily documented AML parser
• Tested on real hardware, see Tested Configurations
• ACPI implementation was made to be easy to understand and useful for educational purposes
• Tested against ACPICA's runtime test suite (WIP)
• ACPI support is still work in progress, check acpi.h for a checklist

File System

• Unix-style VFS with mountpoints, hardlinks, per-process namespaces, etc.
• Strict adherence to "everything is a file" philosophy
• Custom image format (.fbmp)
• Custom font format (.grf)

User Space

• Custom C standard library and system libraries
• Highly modular shared memory based desktop environment
• Theming via config files
• Note that currently a heavy focus has been placed on the kernel and low-level stuff, so user space is quite small... for now

And much more...

Notable Differences with POSIX

• Replaced fork(), exec() with spawn()
• No "user" concept
• Non-POSIX standard library
• Even heavier focus on "everything is a file"
• File flags instead of file modes/permissions

Limitations

• Currently limited to RAM disks only (Waiting for USB support)
• Only support for x86_64

Notable Future Plans

• openat() and fchdir() systems calls
• File flags performance improvements and refactor
• Read, write, execute, create permissions
• Capability style per-process permissions, as a replacement for per-user permissions, via namespace mountpoints with read/write/execute permissions
• Add configurability to spawn() for namespace inheritance
• Asynchronous I/O
• Modular kernel <- Currently being worked on
• Shared libraries
• USB support (The holy grail)

---

Doxygen Documentation

As one of the main goals of PatchworkOS is to be educational, I have tried to document the codebase as much as possible along with providing citations to any sources used. Currently, this is still a work in progress, but as old code is refactored and new code is added, I try to add documentation.

If you are interested in knowing more, then you can check out the Doxygen generated documentation.

Benchmarks

All benchmarks were run on real hardware using a Lenovo ThinkPad E495. For comparison, I've decided to use the Linux kernel, specifically Fedora since It's what I normally use.

Note that Fedora will obviously have a lot more background processes running and security features that might impact performance, so these benchmarks are not exactly apples to apples, but they should still give a good baseline for how PatchworkOS performs.

All code for benchmarks can be found in the benchmark program, all tests were run using the optimization flag -O3.

Memory Allocation/Mapping

The test maps and unmaps memory in varying page amounts for a set amount of iterations using generic mmap and munmap functions. Below is the results from PatchworkOS as of commit 4b00a88 and Fedora 40, kernel version 6.14.5-100.fc40.x86_64.

xychart-beta
title "Blue: PatchworkOS, Green: Linux (Fedora), Lower is Better"
x-axis "Page Amount (in 50s)" [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
y-axis "Time (ms)" 0 --> 40000
line [157, 275, 420, 519, 622, 740, 838, 955, 1068, 1175, 1251, 1392, 1478, 1601, 1782, 1938, 2069, 2277, 2552, 2938, 3158, 3473, 3832, 4344, 4944, 5467, 6010, 6554, 7114, 7486]
line [1138, 2226, 3275, 4337, 5453, 6537, 7627, 8757, 9921, 11106, 12358, 13535, 14751, 16081, 17065, 18308, 20254, 21247, 22653, 23754, 25056, 26210, 27459, 28110, 29682, 31096, 33547, 34840, 36455, 37660]

We see that PatchworkOS performs better across the board, and the performance difference increases as we increase the page count.

There are a few potential reasons for this, one is that PatchworkOS does not use a separate structure to manage virtual memory, instead it embeds metadata directly into the page tables, and since accessing a page table is just walking some pointers, its highly efficient, additionally it provides better caching since the page tables are likely already in the CPU cache.

In the end we end up with a $O(1)$ complexity per page operation, or technically, since the algorithm for finding unmapped memory sections is $O(r)$ in the worst case where $r$ is the size of the address region to check in pages, having more memory allocated would potentially actually improve performance but only by a very small amount. We do of course get $O(n)$ complexity per allocation/mapping operation where $n$ is the number of pages.

Note that as the number of pages increases we start to see less and less linear performance, this is most likely due to CPU cache saturation.

For fun, we can throw the results into desmos to se that around $800$ to $900$ pages there is a "knee" in the curve. Saying that $x$ is the number of pages per iteration and $y$ is the time in milliseconds let us split the data into two sets. We can now perform linear regression which gives us

y =
\begin{cases}
2.25874x+53.95918 & \text{if } x \leq 850, \quad R^2=0.9987,\\
8.68659x-5762.6044 & \text{if } x > 850, \quad R^2=0.9904.
\end{cases}

Performing quadratic regression on the same data gives us

y =
\begin{cases}
0.000237618x^{2}+2.06855x+77.77119 & \text{if } x \leq 850, \quad R^2=0.9979,\\
0.00626813x^{2}-6.04352x+2636.69231 & \text{if } x > 850, \quad R^2=0.9973.
\end{cases}

From this we see that for $x \le 850$ the linear regression has a slightly better fit while for $x > 850$ the quadratic regression has a slightly better fit, this is most likely due to the CPU or TLB caches starting to get saturated. All in all this did not tell us much more than we already knew, but it was fun to do regardless.

Of course, there are limitations to this approach, for example, it is in no way portable (which isn't a concern in our case), each address space can only contain $2^8 - 1$ unique shared memory regions, and copy-on-write would not be easy to implement (however, the need for this is reduced due to PatchworkOS using a spawn() instead of a fork()).

All in all, this algorithm would not be a viable replacement for existing algorithms, but for PatchworkOS, it serves its purpose very efficiently.

VMM Doxygen Documentation

Paging Doxygen Documentation

Shell Utilities

Patchwork includes its own shell utilities designed around its file flags system. Included is a brief overview with some usage examples. For convenience the shell utilities are named after their POSIX counterparts, however they are not drop-in replacements.

<tt>touch</tt>

Opens a file path and then immediately closes it.

# Create the file.txt file only if it does not exist.
touch file.txt:create:excl
 
# Create the mydir directory.
touch mydir:create:dir

<tt>cat</tt>

Reads from stdin or provided files and outputs to stdout.

# Read the contents of file1.txt and file2.txt.
cat file1.txt file2.txt
 
# Read process exit status (blocks until process exits)
cat /proc/1234/wait
 
# Copy contents of file.txt to dest.txt and create it.
cat < file.txt > dest.txt:create

<tt>echo</tt>

Writes to stdout.

# Write to file.txt.
echo "..." > file.txt
 
# Append to file.txt, makes ">>" unneeded.
echo "..." > file.txt:append

<tt>ls</tt>

Reads the contents of a directory to stdout.

# Prints the contents of mydir.
ls mydir
 
# Recursively print the contents of mydir.
ls mydir:recur

<tt>rm</tt>

Removes a file or directory.

# Remove file.txt.
rm file.txt
 
# Recursively remove mydir and its contents.
rm mydir:dir:recur

There are other utils available that work as expected, for example stat and link.

Everything is a File

Patchwork strictly follows the "everything is a file" philosophy in a way similar to Plan9, this can often result in unorthodox APIs or could just straight up seem overly complicated, but it has its advantages. We will use sockets to demonstrate the kinds of APIs this produces.

Sockets

In order to create a local seqpacket socket, you open the /net/local/seqpacket file. The opened file will act as the handle for your socket. Reading from the handle will return the ID of your created socket so, for example, you can do

char id[32] = {0};
readfile("/net/local/seqpacket", id, 31, 0); // Helper function that opens, reads and closes a file.

Note that even when the handle is closed the socket will persist until the process that created it and all its children have exited. The ID that the handle returns is the name of a directory that has been created in the /net/local directory, in which are three files, these include:

• data - used to send and retrieve data
• ctl - used to send commands
• accept - used to accept incoming connections

So, for example, the sockets data file is located at /net/local/[id]/data.

Say we want to make our socket into a server, we would then use the bind and listen commands with the ctl file, we can then write

fd_t ctl = openf("/net/local/%s/ctl", id);
writef(ctl, "bind myserver");
writef(ctl, "listen");
close(ctl);

Note the use of openf() which allows us to open files via a formatted path and that we name our server myserver. If we wanted to accept a connection using our newly created server, we just open its accept file by writing

fd_t fd = openf("/net/local/%s/accept", id);

The returned file descriptor can be used to send and receive data, just like when calling accept() in for example Linux or other POSIX operating systems. Note that the entire socket API does attempt to mimic the POSIX socket API, apart from using these weird files everything (should) work as expected.

For the sake of completeness, if we wanted to connect to this server, we can do

char id[32] = {0};
readfile("/net/local/seqpacket", id, 31, 0);
 
fd_t ctl = openf("/net/local/%s/ctl", id);
writef(ctl, "connect myserver");
close(ctl);

which would create a new socket and connect it to the server named myserver.

Doxygen Documentation

Namespaces

Namespaces are a set of mountpoints that is unique per process with each process able to access the mountpoints in its parent's namespace, which allows each process a unique view of the file system and is utilized for access control.

Think of it like this, in the common case, for instance on Linux, you can mount a drive to /mnt/mydrive and all processes can then open the /mnt/mydrive path and see the contents of that drive. In PatchworkOS, this is also possible, but for security reasons we might not want every process to be able to see that drive, instead processes should see the original contents of /mnt/mydrive which might just be an empty directory. The exception is for the process that created the mountpoint and its children as they would have that mountpoint in their namespace.

For example, the "id" directories mentioned in the socket example are a separate "sysfs" instance mounted in the namespace of the creating process, meaning that only that process and its children can see their contents.

Doxygen Documentation

Namespace Sharing

It's possible for two processes to voluntarily share a mountpoint in their namespaces using bind() in combination with two new system calls share() and claim().

For example, if process A wants to share its /net/local/5 directory from the socket example with process B, they can do

// In process A
fd_t dir = open("/net/local/5:dir");
 
// Create a "key" for the file descriptor, this is a unique one time use randomly generated token that can be used to retrieve the file descriptor in another process.
key_t key;
share(&key, dir, CLOCKS_PER_SEC * 60); // Key valid for 60 seconds (CLOCKS_NEVER is also allowed)
 
// In process B
// The key is somehow communicated to B via IPC, for example a pipe, socket, argv, etc.
key_t key = ...;
 
// Use the key to open a file descriptor to the directory, this will invalidate the key.
fd_t dir = claim(key);
// Will error here if the original file descriptor in process A has been closed, process A exited, or the key expired.
 
// Make "dir" ("/net/local/5" in A) available in B's namespace at "/any/path/it/wants". In practice it might be best to bind it to the same path as in A to avoid confusion.
bind(dir, "/any/path/it/wants");
 
// Its also possible to just open paths in the shared directory without polluting the namespace using openat().
fd_t somePath = openat(dir, "data"); // To be implemented
 
// Finally, it could also use fchdir() to change its current working directory to the shared directory.
fchdir(dir); // To be implemented

This system guarantees consent between processes, and can be used to implement more complex access control systems.

An interesting detail is that when process A opens the net/local/5 directory, the dentry underlying the file descriptor is the root of the mounted file system, if process B were to try to open this directory, it would still succeed as the directory itself is visible, however process B would instead retrieve the dentry of the directory in the parent superblock, and would instead see the content of that directory in the parent superblock. If this means nothing to you, don't worry about it.

Doxygen Documentation

File Flags?

You may have noticed that in the above section sections, the open() function does not take in a flags argument. This is because flags are part of the file path directly so if you wanted to create a non-blocking socket, you can write

fd_t handle = open("/net/local/seqpacket:nonblock");

Multiple flags are allowed, just separate them with the : character, this means flags can be easily appended to a path using the openf() function. It is also possible to just specify the first letter of a flag, so instead of :nonblock you can use :n.

Doxygen Documentation

---

Directories

Directory	Description
include	Public API
src	Source code
root	Files copied to the root directory of the generated .img
tools	Build scripts (hacky alternative to cross-compiler)
make	Make files
lib	Third party dependencies
meta	Screenshots and repo metadata

Sections

• boot: Minimal UEFI bootloader that collects system info and loads the kernel
• kernel: The monolithic kernel handling everything from scheduling to IPC
• libstd: C standard library extension with system call wrappers
• libpatchwork: Higher-level library for windowing and user space services
• programs: Shell utilities, services, and desktop applications

Setup

Requirements

Requirement	Details
OS	Linux (WSL might work, but I make no guarantees)
Tools	GCC, make, NASM, mtools, QEMU (optional)

Build and Run

# Clone this repository, you can also use the green Code button at the top of the Github.
git clone https://github.com/KaiNorberg/PatchworkOS
cd PatchworkOS
 
# Build (creates PatchworkOS.img in bin/)
make all
 
# Run using QEMU
make run

Additional commands

# Clean build files
make clean
 
# Build with debug mode enabled
make all DEBUG=1
 
# Build with debug mode enabled and testing enabled (you will need to have iasl installed)
make all DEBUG=1 TESTING=1
 
# Debug using qemu with one cpu and GDB
make all run DEBUG=1 QEMU_CPUS=1 GDB=1
 
# Generate doxygen documentation
make doxygen
 
# Create compile commands file
make compile_commands

Grub Loopback

For frequent testing, it might be inconvenient to frequently flash to a USB. You can instead set up the .img file as a loopback device in GRUB.

Add this entry to the /etc/grub.d/40_custom file:

menuentry "Patchwork OS" {
        set root="[The grub identifer for the drive. Can be retrived using: sudo grub2-probe --target=drive /boot]"
        loopback loop0 /PatchworkOS.img # Might need to be modified based on your setup.
        set root=(loop0)
        chainloader /efi/boot/bootx64.efi
}

Regenerate grub configuration using sudo grub2-mkconfig -o /boot/grub2/grub.cfg.

Finally copy the generated .img file to your /boot directory, this can also be done with make grub_loopback.

You should now see a new entry in your GRUB boot menu allowing you to boot into the OS, like dual booting, but without the need to create a partition.

Troubleshooting

• QEMU boot failure: Check if you are using QEMU version 10.0.0, as that version has previously caused issues. These issues appear to be fixed currently however consider using version 9.2.3
• Any other errors?: If an error not listed here occurs or is not resolvable, please open an issue in the GitHub repository.

Testing

Testing uses a GitHub action that compiles the project and runs it for some amount of time using QEMU both with the DEBUG=1 and TESTING=1 flags enabled. This will run some additional tests in the kernel (for example it will clone ACPICA and run all its runtime tests), and if it has not crashed by the end of the allotted time, it is considered a success.

Tested Configurations

• QEMU emulator version 9.2.3 (qemu-9.2.3-1.fc42)
• Lenovo ThinkPad E495
• Ryzen 5 3600X | 32GB 3200MHZ Corsair Vengeance

Currently untested on Intel hardware. Let me know if you have different hardware, and it runs (or doesn't) for you!

Contributing

Contributions are welcome! Anything from bug reports/fixes, performance improvements, new features, or even just fixing typos or adding documentation!

If you are unsure where to start, try searching for any "TODO" comments in the codebase.

Check out the contribution guidelines to get started.

Nostalgia

The first Reddit post and image of PatchworkOS from back when getting to user space was a massive milestone and the kernel was supposed to be a microkernel.