CS4284 Systems Capstone

Open Ended Project§

The open-ended project should pursue a line of experimentation and implementation that extends the structured Pintos projects in some way.

We are a little late in our planning, so we'll need to get started right away. We'll use March 17 + 18 for initial group meetings.

Please come to the meeting prepared to discuss an initial idea.

The following are possible ideas, listed in no particular order.

Project Ideas§

The Hardware Track

Pintos currently runs on various virtual machines that emulate previous generation (or even older) PC hardware. A few years ago, some support for PCI and support for first generation USB (USB 1.0/1.1 via UHCI controllers) was added. This support has not recently been tested and has not been updated to the SMP version.

The goal of this project would be to add the necessary support to boot Pintos on current hardware. Likely, this will require adding support for xHCI and possibly for hubs.

Success criteria: boot Pintos into its shell on a physical machine using USB and the xHCI controller.

The Networking Track

Pintos currently does not have any support for networking, which obviously is not a great situation. The networking track adds support for TCP/IP networking to Pintos.

One way to accomplish this support includes:

writing a device driver for a network interface controller (NIC). You would be using the Intel E1000 card. The E1000 is a complicated card with lots of features, but you'll only have to implement a few to get basic Ethernet working.
incorporating the lwIP stack or a similar user-level stack for a TCP/IP implementation.
Writing the necessary system call stubs and the file descriptor glue code to interact with lwIP, as well as the glue code to integrate lwIP with Pintos.

Success criteria: demonstrate a TCP/IP server that interacts with the outside world, e.g. a web server running on Pintos serving HTML pages.

The Parallel Track

Pintos 2017 supports multiple CPUs/cores, each of which can run separate threads/processes. However, each process contains only one thread. Consequently, shared-memory parallelism is difficult to exploit. This project adds support for multi-threading to Pintos!

Support for multi-threading involves separating the thread control block data structure from a to-be-created process control block. All decisions that assume that a process has only a single thread will need to be revisited and proper synchronization mechanisms introduced (e.g. related to file descriptor and VM management).

A user-level API, possibly modeled after POSIX Threads, would need to be introduced to allow starting additional threads.

Synchronization primitives (locks, semaphores, condition variables) need to be made available to threads. A simple way of doing this involves mapping them to system calls, but doing so is slow. For instance, the common case of acquiring an uncontended lock should not involve a system call. As an additional optimization, you could explore ways of avoiding this system call overhead by implementing a facility similar to futexes.

Implementing this project may require adding support for user-level memory allocation (malloc + sbrk).

Success criteria: run your CS 3214 fork-join thread pool (or a similar, multi-threaded application) on Pintos and demonstrate application speedup when executing on KVM.

The Unix Track

Pintos 2017, as an educational OS, provides a simplified model with respect to process and file descriptor management when compared to Unix systems such as Linux. For instance, file descriptors are not inherited to child processes, there is no way to reassign file descriptors (e.g. dup2()); file descriptors are also not reference-counted and cannot be referred to from multiple processes. Consequently, it is impossible to implement pipes, a cornerstone of Unix since 1972, when Dennis Ritchie added them, calling it a "relatively simple job".

In this project, implement support for a Unix-like model of process and file descriptor management that allows the use of pipes.

One way to accomplish this would be to model Unix itself: instead of embedding file descriptors in each process's file descriptor table, file descriptors would become independent, reference-counted kernel objects. Instead of the current Pintos exec() call, which combines the creation of a new process with the start of a new program, provide separate fork() and execve() calls that just start a new process or just execute a new program.

Another way would be to keep the current exec() semantics, but augment it with a way for the parent process to control to which file descriptors a child has access. In fact, such a model, while lacking the generality of fork(), may have the potential to drastically simplify the implementation of shells by focusing only on the shell's use case for pipes and I/O redirection.

Implementing this project will require adding support for user-level memory allocation (malloc + sbrk).

Success criteria: run your CS 3214 cush (or a subset thereof, which supports pipes) on Pintos!

The Security Track

Currently, Pintos lacks any notion of security whatsoever, including security principals, access control, authentication, authorization, or privilege escalation. Make Pintos more secure!

Introduce some kind of user principal abstraction for Pintos, e.g. process uids that represent the principal on whose behalf the kernel is asked to act.
Introduce authentication (probably password-based) and the necessary password database management.
Introduce access control. At a minimum, you would want to protect files and directories, but possibly others actions, perhaps similar to SE Linux or AppArmor
Implement (controlled) privilege elevation - a way for an authorized user to perform actions that require elevation of privileges, e.g. setuid binaries.

Success criteria: provide a way to log-in to your system (via password), maintain a database of users and privileges (e.g. /etc/passwd), then demonstrate that the kernel respects those privileges in its operations.

The File System Track

The file system project is probably the project in which the educational simplifications are farthest from the current state of the art. The traditional Unix file system model which we suggest you implement in project 4 pretty much lacks any of the performance innovations introduced in the last 30 years, and it also lacks the ability to recover after a crash.

The goal of this project would be to implement one advanced file system feature, such as

A scalable directory implementation, perhaps using B-trees.
Recovery after a crash. Either traditional fsck, or some version of physical logging.
A log-based file system, or ZFS-style copy-on-write snapshots.
A unified page cache (for VM pages and file system data)

This could double as your project 4 implementation (if your advanced filesystem passes project 4 or a set of equivalent tests).

Success criteria: demonstrate robust load/fault injection tests that show your feature works successfully!

Other possible ideas§

64-bit Pintos. Run Pintos in 64-bit mode. This would require updating the toolchain and changing all assumptions that are currently inherent to the use Intel's IA32 to use x86_64 instead. There have been reported attempts by others, also here but their code may not be available.
A dynamic memory-checker tool for Pintos, e.g. valgrind for Pintos. This can be accomplished by instrumenting Bochs (simpler) or Qemu (harder). Success criteria: find memory bugs in your Pintos implementation.
A dynamic race condition-checker for Pintos, e.g. helgrind for Pintos. This can be accomplished by instrumenting Bochs (simpler) or Qemu (harder). Success criteria: find concurrency bugs in your Pintos implementation. This would require choosing an implementing a race condition detection algorithm.
A "transparent" VM. Augment an existing VMM to display actions of interest during the execution of Pintos, e.g. VM exits, page table updates, page table activations, context switches, mode switches, the process environments, etc. and visualize the execution of the entire system (user processes + kernel) in some useful way.
Implement exceptionless system calls, such as in the form of IO Uring
Implement RCU for Pintos
Implement support for other interesting devices, e.g. graphics drivers, or GPUs.
Possible others, to be discussed. In general, I am looking for a project that is in some ways related to the structured projects, e.g., builds on them.