Weenix
Brown University Department of Computer Science Authored by Operating Systems Teaching Assistant Staff Edited by and J. Rassi
May 18, 2018
2
Contents
I Introduction 7
1 The Weenix OS 9 1.1 Motivation ………………………… 9 1.2 HowtoReadThisBook ………………….. 10 1.3 History ………………………….. 10 1.4 Acknowledgements …………………….. 10
2 Pro ject Management 13
2.1 Introduction………………………… 13
2.2 PreparingWeenixAssignments ………………. 13
2.2.1 QuickStart: GettingWeenixRunning . . . . . . . . . . . 13 2.2.2 GettingtheSource…………………. 13 2.2.3 Dependencies……………………. 13 2.2.4 Configuration……………………. 14 2.2.5 BlankingSolutions…………………. 14
2.3 ImplementingWeenixAssignments…………….. 15 2.3.1 AMessagetotheReader ……………… 16 2.3.2 BuildSystem ……………………. 16 2.3.3 AssignmentSpecification ……………… 17 2.3.4 Running………………………. 17 2.3.5 MakingChanges ………………….. 18
II Assignments 19
3 Processes and Threads 21 3.1 Introduction………………………… 21 3.2 KernelMemoryManagement ……………….. 21 3.3 BootSequence ………………………. 22 3.4 ProcessesandThreads…………………… 22 3.5 Scheduler …………………………. 23 3.6 SynchronizationPrimitives ………………… 24 3.7 Testing ………………………….. 24
3
4
CONTENTS
4 Drivers 27
4.1 Introduction………………………… 27
4.2 Object-OrientedC …………………….. 27
4.3 TTYDevice………………………… 28
4.3.1 LineDiscipline …………………… 28
4.3.2 TTYDriver…………………….. 29
4.4 DiskDeviceDriver…………………….. 29
4.5 MemoryDevices ……………………… 29
4.6 Testing ………………………….. 30
5 Virtual File System 33
5.1 Introduction………………………… 33 5.1.1 Constructors ……………………. 33 5.1.2 VirtualFunctions………………….. 34 5.1.3 Overview ……………………… 34 5.1.4 GettingStarted…………………… 37
5.2 TheramfsFileSystem…………………… 37
5.3 PathnametovnodeConversion………………. 38
5.4 OpeningFiles……………………….. 38
5.5 SystemCalls ……………………….. 38
5.6 Testing ………………………….. 38
6 System V File System 41
6.1 Introduction………………………… 41
6.2 DiskLayout………………………… 42
6.2.1 Superblock …………………….. 42 6.2.2 Inodes……………………….. 42 6.2.3 DataBlocks…………………….. 44 6.2.4 Directories …………………….. 44
6.3 Caching ………………………….. 45 6.3.1 PageFrameStates …………………. 46 6.3.2 LazyCleaning …………………… 47
6.4 ErrorHandling ………………………. 47
6.5 GettingStarted………………………. 47
6.6 Testing ………………………….. 48
7 Virtual Memory 49
7.1 Introduction………………………… 49
7.2 VirtualMemoryMaps …………………… 49
7.3 PageFaultHandler…………………….. 50
7.3.1 TheMemoryManagementUnit…………… 51
7.4 MemoryManagement …………………… 51 7.4.1 AnonymousObjects ………………… 51 7.4.2 ShadowObjects ………………….. 52
7.5 SystemCalls ……………………….. 53 7.5.1 KernelSystemCallInterface ……………. 53
CONTENTS 5
7.5.2 AccessingUserMemory ………………. 53 7.5.3 RunningUserlandPrograms ……………. 53 7.5.4 VM-RelatedSystemCalls……………… 54
7.6 fork()…………………………… 54
7.7 OddsandEnds………………………. 56
7.8 Testing ………………………….. 56
7.8.1 UserlandTests …………………… 56 7.8.2 ARelativelyDifficultTestSuite ………….. 58 7.8.3 DynamicLinking………………….. 59
7.9 Conclusion ………………………… 59
III Appendices 61
A Extra Assignments 63
A.1 Realisticprojects……………………… 63 A.1.1 Multithreadedprocesses………………. 64 A.1.2 Currentworkingdirectory……………… 64 A.1.3 Filesystemmounting ……………….. 64 A.1.4 Userspacepreemption ……………….. 65 A.1.5 Pipesandsynchronousmultiplexing . . . . . . . . . . . . 66 A.1.6 Asynchronousdiskdriver ……………… 66 A.1.7 Betterscheduling………………….. 67
A.2 Possiblelong-termprojects ………………… 67 A.2.1 Multi-core/processorsupport ……………. 67 A.2.2 Users ……………………….. 68 A.2.3 Signals……………………….. 68
A.3 “Abandonallhope,yewhoenterhere”. . . . . . . . . . . . . . . 69 A.3.1 Networkingstack………………….. 69 A.3.2 Xwindowsystem………………….. 69 A.3.3 64-bitsupport …………………… 69 A.3.4 Kernelpreemption …………………. 69
B Tools for Working in a Large Codebase 71
B.1 VersionControlwithgit …………………. 71
B.2 Takingnotes ……………………….. 71
B.3 TextEditorsandIDEs…………………… 71
B.3.1 Integrationwithcscope………………. 72
B.4 Debuggingwithgdb ……………………. 72
C Debugging 73
C.1 BeginningDebugging……………………. 73 C.1.1 Printing………………………. 73 C.1.2 PrintingUsingInfoFunctions……………. 74 C.1.3 UsingAssertions ………………….. 74
C.2 IntermediateDebugging ………………….. 75
6
C.3
CONTENTS
C.2.1 Prerequisites ……………………. 75 C.2.2 DebuggingMultipleThreads ……………. 76 C.2.3 UsingtheWeenixgdbScripts……………. 76 C.2.4 DisassemblingaProgram ……………… 77 C.2.5 UsingtheQEMUmonitor……………… 77 AdvancedDebuggingTechniques ……………… 77
C.3.1 DebuggingaPageFault………………. 77
C.3.2 Debugging processes from the kernel debugger . . . . . . 78
C.3.3 gdbandDYNAMIC………………….. 79
Part I Introduction
7
Chapter 1
The Weenix OS
1.1 Motivation
The Weenix operating system is a project for people interested in writing parts of a Unix kernel. The operating system was originally written in 1998 by teaching assistants for Brown University’s operating systems course, taught by Professor Tom Doeppner, and has been maintained by that course’s staff ever since. While the operating system is mostly based on early versions of Unix, it incorporates many recent developments in operating systems.
This book is intended to be a guide for students who are working on the Weenix operating system and those interested in contributing to it. Part 1 is an introduction to Weenix, including the basics of setting up your development environment, using the build system, and running the OS in a virtual machine. Part 2 contains five chapters, each of which specify an assignment. In the operating systems course taught at Brown, students have a choice between doing either:
• All five assignments.
• A separate threads library assignment followed by two of the Weenix as-
signments (VFS and S5FS).
Students pursuing the former option are assigned a mentor from the course staff who will be a source of clarification or hints if the student wishes. The latter option is provided to allow students who are not interested in a career in operating systems development to learn the basics of operating systems without spending the better part of their semester hacking the Weenix kernel. Each assignment chapter begins with an overview of the assignment, then describes the expected implementation in more detail, and ends with tips for testing. Part 3 describes the inner workings of some key parts of the kernel not typically explored during the assignments. This is mainly a resource for those wishing to contribute to the Weenix project. Finally, several appendices are included
9
10 CHAPTER 1. THE WEENIX OS which provide more details about development tools, online resources, and the
protocols of contributing new code.
1.2 How to Read This Book
We expect that there are at least two groups of people who will want to read this book. If you are someone who wants to see Weenix run right now, jump ahead to Quick Start: Getting Weenix Running. Everyone else should begin by reading Project Management and then can read the assignments, manual, and appendices in whatever order they please. However, if you plan to do the assignments, we recommend that you do them in order, as they build on top of one another.
1.3 History
The Weenix OS, and the course that it grew up with, have a long and illustrious history. Although the Brown operating systems course has been taught since the 1960s, Weenix was first written in the spring of 1998, running on what was known only as the Brown Simulator 2.0. The two pieces of software were written by , , , , and . The name Weenix (“little *nix”) was invented by , and the OS was designed based on early versions of Unix. In 2004, a competing Brown operating system based on Windows (named HipOS) was created by , whose effort was apparently completely vanquished. During 2007- 2009, Weenix moved off of the Brown Simulator and onto Xen virtual machines, an effort spearheaded by , , , and . In 2010, Weenix found its current home running on Bochs, a virtual machine including a simulated real machine. , , and were the major contributors for this move. Weenix has since moved onto QEMU, an x86 processor emulator.
The features of Weenix now include: • Intelligent multitasking
• Virtual memory
• Terminal emulation
• Polymorphic file system support
• Advanced device support (including APIC and PATA with BMIDE)
1.4 would not have been possible without the help of many earnest, devoted individuals. Thanks first to Professor Tom Doeppner, for his patient guidance and leadership.
1.4. ACKNOWLEDGEMENTS 11
Thanks also to the many course TAs since the creation of Weenix.
’98-’99 , , ,
’99-’00 , , , ,
’00-’01 , , , ,
’01-’02 , , -Mosavat, ,
’02-’03 Kit Colbert, , , ,
’03-’04 , , , ,
’04-’05 , , , ,
’05-’06 , , , ,
’06-’07 , , , ,
’07-’08 , , , Aurojit Panda, ,
’08-’09 , ’Donnell, , , ,
’09-’10 , , ,
’10-’11 , , , – lozzi,
’11-’12 , , J. Rassi, , , , ,
’12-’13 , , , , ,
’13-’14 , , , , , Zhix- iong Chen
’14-’15 DJ Hoffman, , Jake Ellis, , , ,
’15-’16 , , , , , Xiangyu (Tom) Yao
’16-’17 , , , , , Di Yang (Steven) Shi
’17-’18 , , , , Jake Saferstein, Di Yang (Steven) Shi
12 CHAPTER 1. THE WEENIX OS
In particular, many thanks to , , , , , and for their major contributions to the project.
Finally, thanks to the innumerable students who have implemented Weenix over the years. We hope the knowledge you gained in the process has served you well.
Chapter 2
Project Management
2.1 Introduction
The first section of this chapter guides the reader through the process of pro- ducing a Weenix assignment from the project’s complete source code (useful for course instructors), and the second explains how to set up a development environment for implementing the assignment yourself (useful for students).
2.2 Preparing Weenix Assignments
This section will walk you through a sample run of Weenix, and then shows you how to remove sections of code from the full implementation to allow you or your students to re-implement them.
2.2.1 Quick Start: Getting Weenix Running
See instructions in the top-level README file. 2.2.2 Getting the Source
Requests for a copy of Weenix may be made via email to 2.2.3 Dependencies
The following is required to run Weenix: • gcc, the GNU C compiler
• make, the GNU build system
• qemu,the processor emulator that Weenix runs on top of
13
14
•
•
•
CHAPTER 2. PROJECT MANAGEMENT
xorisso and grub-mkrescue (necessary to generate the disk image used by the emulator)
python, at least 2.6 (but 2.x only) bash
The following is optional, but recommended:
• git, the version control system
• gdb, the GNU debugger, and xterm
• cscope (for easier browsing of the Weenix source)
2.2.4 Configuration
Configuration for Weenix is available through editing the files Config.mk and Global.mk, which contain VARIABLE=value assignments in make syntax. Global.mk contains directives relevant to the environment that Weenix is running in (e.g. alternative locations for utilities like python or gdb), while Config.mk is used
to configure values that affect the behavior of Weenix itself (such as what mod- ules to enable during the compilation process, or the size of the virtual disk to create).
In particular, you should be aware of the directives that affect what assign- ment to enable. These are the first directives of Config.mk. For example, to enable the S5FS assignment, set the first three to 1 (DRIVERS=1, VFS=1, and S5FS=1).
2.2.5 Blanking Solutions
This section will teach you how to blank the solution for individual assignments. You will wish to do this before you attempt to complete the Weenix assignments (otherwise, you will find that they have already been done for you!) or before you assign them to others.
The script make-weenix-repo.py in the tools/ directory performs this task.
It removes the contents of specially-marked functions, putting a NOT YET IMPLEMENTED() marker in their place. It also initializes a fresh git repository in the root of the
source tree for you (or your students) to clone from.
1. Obtain an unmodified copy of the Weenix source tree.
If you skip this step, you will lose all of your work: the make-weenix-repo.py will obliterate any git history that exists in the current source tree, as well as the contents of assignments that are to be removed.
2. Change into the tools/ directory.
2.3. IMPLEMENTING WEENIX ASSIGNMENTS 15
3. Run./make-weenix-repo.py –cutextra all –cutsource [ASSIGNMENTS], where [ASSIGNMENTS] is a comma-delimited list of the projects you
want to assign (or “all”, without quotes).
For example, suppose you want to implement the S5FS and VM assign- ments. You should blank the solutions for these assignments, and leave the rest (PROCS, DRIVERS, and VFS) intact. This can be accomplished with the command:
$ ./make-weenix-repo.py –cutextra all –cutsource S5FS,VM
The order of the assignments is: PROCS, DRIVERS, VFS, S5FS, and lastly VM. Remember that each assignment depends on its predecessor in order to run. For example, if you wish to start with the VM assignment, do not blank any other assignments, or you will find yourself unable to run the VM code you write.
As another example, suppose you want start fresh from the first assign- ment. Run:
$ ./make-weenix-repo.py –cutextra all –cutsource all
4. Update the assignment directives in Config.mk to reflect the first assign-
ment you will work on.
These are described in detail in the Configuration section.
For example, if you are starting with the VFS assignment, set your as- signment directives to:
DRIVERS=1
VFS=1
S5FS=0
VM=0
DYNAMIC=0
If you are making use of the git repository, you will need to commit this change. For example:
$ git commit -m ’Updated Config.mk assignments directives’ Config.mk
Congratulations: you are now ready to start the assignment. If you need to distribute the assignment to others, have them copy (or git clone, if you are using git) this source tree to be their fresh copy to start working on.
2.3 Implementing Weenix Assignments
This section introduces some essential concepts in Weenix to e.g. a student who is interested in completing a Weenix assignment.
16 CHAPTER 2. PROJECT MANAGEMENT 2.3.1 A Message to the Reader
Although this section is ostensibly about getting to know the Weenix codebase, we realize this is also the last part of the book we can be certain everyone will read, so we would like to give a few pieces of advice.
• It is possible that this is your first exposure to a large code base. You should definitely spend some time poring over the existing code, thinking about what to implement. Take a look in Appendix B to learn more about working in large codebases.
• For this and future assignments, it may be helpful to draw out a call graph (which functions call which) for the code you will be writing. Taking notes about the code as you read it is a useful skill for any codebase.
• Become an expert at using your chosen development tools. This will save you countless hours of time and energy, whether you learn to use a de- bugger (see Appendix C), text editor/IDE, cscope, version control, or something else. Many of these are mentioned in the appendix, so take a look there for some tips for getting started.
• Be sure to ask questions! The course staff is friendly and has a great working knowledge of the OS because they have implemented it them- selves. Beyond that, getting Weenix working is far more rewarding if you understand why something is done a particular way, and the repercussions of choosing a different way to do something.
• Take breaks to relax. 🙂
2.3.2 Build System
The Weenix build system is based on the popular Unix utility make. It is meant to aid development by automating the compilation and linking of binaries, although it is used to automate several other things in the Weenix codebase as well.
In order to build the full operating system, make must be run in the top directory of the Weenix repository. Each make target corresponds to particular a set of commands listed in the Makefile located in the current directory. In the case of the top-level Makefile, make all simply descends into the kernel and user directories and executes make within each. The kernel and the userspace binaries can be built separately, by calling make from their respective directories. There are many different targets, such as individual object (.o) files, linked binaries and disk images, but the most useful targets are listed below.
To compile all the code using eight concurrent tasks, a user should run:
$ make -j 8 [all]
or potentially just:
2.3. IMPLEMENTING WEENIX ASSIGNMENTS 17 $ make all
$ make % defaults to target “all”
if the pretty output is more important than the speed of compilation. Sometimes, such as after a change in the configuration settings or compiler flags, it is necessary to compile all the source code from scratch. However, make will only rebuild a file if it has been modified since the last time it was built. To delete all the constructed binaries and force make to compile from scratch, a
user may run:
$ make clean; make all
2.3.3 Assignment Specification
To find out what to implement for a newly opened assignment, use the following command:
$ make nyi
This will produce a list of all the functions that are not yet written in the codebase with labels telling what file they are in and what assignment they are associated with.
Note that this command is only to be used with blanked assignments (oth- erwise, there’s nothing to implement!).
2.3.4 Running
The weenix script has been provided for running the operating system inside a virtual machine or hardware simulator. It should be invoked from the topmost directory of the Weenix repository. To run it, one may simply use the command:
$ ./weenix
Until there is a functional on-disk file system, this is all that is necessary to run Weenix. However, at that point, the ability to create disks becomes very important. It is necessary to create a fresh disk the first time S5FS runs, and also after any time the disk is corrupted by a buggy kernel or unclean shutdown. The following command will run Weenix with a newly constructed disk:
$ ./weenix -n
At some point, it may be helpful to use a debugger to aid in the development of the operating system. The following command will begin Weenix in a virtual machine and attach gdb to it (if the virtual machine in use supports this option).
$ ./weenix -d gdb
The QEMU monitor can produce additional useful debugging information from the virtual machine. The QEMU monitor will be displayed on stdout instead of your debug messages, allowing you to query the virtual machine directly. Refer to Appendix C for more on its useful commands.
18 CHAPTER 2. PROJECT MANAGEMENT $ ./weenix -d qemu
These options (and their exciting longer names –new-disk and –debug) are also visible at the command line.
$ ./weenix -h
2.3.5 Making Changes
Any time someone works on a large enough project, they will inevitably make difficult-to-reverse mistakes or accidentally delete their work. The best way to prepare oneself for this inevitability is to use a version control system. The Weenix repository uses the source control system git, and everyone who un- dertakes a project of this magnitude should become at least competent enough to make commits, revert a file back to a previous commit, and make feature branches for each new addition. The following list of steps are a highly recom- mended way to implement a new piece of Weenix.
1. Make a new branch to develop in with a descriptive name.
2. Write tests for the new feature, running them frequently.
3. Write code, committing relatively frequently to avoid losing any work.
4. Make sure all the tests pass and that they comprehensively cover the set of requirements.
5. Push the changes back onto the main branch once everything is functional.
6. Back up the entire project frequently using an external hard drive or (even better) an online backup and recovery service.
Even if you don’t follow these steps, please, for the love of all things holy, use source control. If you mess up your repository due to lack of experience, somebody will be able to help you out of the mess and you’ll be back where you were before, but if you mess up an unprotected directory, there is no going back! Having a student who loses all their Weenix code is awful, and being that student has been a recurring theme in many of our worst nightmares. If you have any questions or have never used source control before, feel absolutely free to reach out to the TA staff in setting it up.
Part II Assignments
19
Chapter 3
Processes and Threads
3.1 Introduction
This assignment, colloquially referred to as “Kernel 1,” will provide the basic building blocks for the Weenix operating system: threads, processes, and syn- chronization primitives. These objects are implemented fully in kernel code, and interactions with user-level processes and threads will not be possible until you implement virtual memory in a later assignment.
Writing an operating system can be complicated, so much of the code to do basic kernel operations such as memory allocation and page table management has already been written. These are either beyond the scope of the project or are too time consuming for too little value. While modifications to the support code are fully possible, significant changes to the provided interfaces make errors far more likely and make it harder to ask for help. However, it is important for you to be able to take ownership of the code. Though it is usually too time- consuming to write the entire system from scratch, by the end of the project, you should have a good (if high-level) understanding of all the code involved. This will certainly be true by VM, which will involve putting the final touches on the kernel.
At the end of this first assignment, the kernel will be able to run several threads and processes concurrently in kernel mode. It is important to emphasize that a strong test suite is critical. For this assignment, test code must be added directly into the boot sequence for the kernel, but in later assignments there will be several additional ways to add tests in a cleaner, more modular way.
3.2 Kernel Memory Management
As mentioned above, this has been fully implemented for you, but take a moment to look around include/kernel/mm/kmalloc.h, include/kernel/mm/slab.h and kernel/mm/slab.c to familiarize yourself with the memory management interface. The functions kmalloc() and kfree() exist as kernel-space worka-
21
22 CHAPTER 3. PROCESSES AND THREADS
likes for the standard library malloc() and free() functions. However, these should be used sparingly (for example, for incidental memory usage during test- ing). Most of the kernel memory management you will be doing using the slab allocators. A slab allocator, as used in Solaris and Linux, works like a cache for memory chunks of a particular size. This reduces both the loss of memory through fragmentation and the overhead from manipulating the heap directly. Refer to include/kernel/mm/slab.h for the slab allocation and free- ing functions you will be using.
3.3 Boot Sequence
Most of the boot sequence is handled by the support code. The last thing the boot loader does is execute the function kmain(), which initializes the support subsystems and then calls bootstrap().
At this point, we are still in the boot sequence, which means that we do not have a thread context in which to properly execute. We cannot block, and we cannot execute user code. The goal of bootstrap() is to set up the first kernel thread and process, which together are called the idle process, and execute its main routine. This should be a piece of cake once you have implemented threads and the scheduler.
The idle process performs further initialization and starts the init process. For now, all of your test code should be run in the init process. When your operating system is nearly complete, it will execute a binary program in user mode, but for now, be content to put together your own testing system for threads and processes in kernel mode.
3.4 Processes and Threads
Weenix is capable of running multiple processes and threads. There are a few important things to note about the Weenix threading model.
• There is no kernel mode preemption in Weenix (all threads run until they explicitly yield control of the processor). It is possible (but not required) to implement user mode preemption. Think about why this is much easier to do.
• Weenix is only running on one processor, so synchronization primitives don’t require atomic compare-and-swap instructions or memory barriers.
• Each process only has one thread associated with it, however the thread- ing code is actually structured so that it would be easy to have multiple threads per process. For example, each process keeps a list of its threads, even though that list currently never has more than one entry. If a function seems unnecessary to you, think of it in the context of multiple threads per process. For instance, when exiting a thread, you must alert the process
3.5. SCHEDULER 23 that one of its threads exited, even though each process should only ever
have one thread.
• Think of a process as a collection of some number of threads and some metadata. Killing a process is equivalent to killing its threads and vice- versa.
The lifecycle of threads and processes is relatively straightforward. When a process is created, a thread should be added to it and the process should be made runnable by adding its thread to the run queue. If a process exits and it still has child processes, it should reassign those children to the init process, which, after performing some system setup, will sit in a loop collecting orphaned processes. When a thread attempts to exit the current process, the process code must cancel any other threads in the same process (and join with them, if there are multiple) so that they can do any cleanup necessary for their current tasks. Once each thread finishes cleaning up its current task, it makes a call to the process code to indicate it is exiting so that the process can do any final cleanup on the thread data structure.
Once all its threads have exited, a process can exit and one of its ancestors (either its parent or the init process) will call do waitpid() and clean it up fully. The reason for this somewhat odd deallocation system is that some elements of the process and thread data structures can only be cleaned up from another thread’s context. During this assignment, you should determine what these items are, and clean up everything else in the process as quickly as possible. Also note that processes which are children of the idle process will not be cleaned up using this method; they are dealt with separately.
As a side note, you will be using linked lists extensively throughout Weenix. By this point, you may have looked at the code and seen that some data struc- tures contain list objects or link objects. We provide you with a circular doubly- linked list implementation where the links are stored inside of the objects that are in the list (hence the link fields inside the objects). Most of this list imple- mentation is provided as a set of macros which can be found in the codebase. You even get a couple of neat list iteration “primitives” that look like they’re straight out of your favorite scripting language!
The trickiest parts of this segment are do waitpid() and proc kill all(), not because they are conceptually difficult, but because it is very easy to acci- dentally introduce bugs that you will discover much later. As such, you should test the edge cases of these functions early and often throughout the develop- ment of your operating system.
3.5 Scheduler
Once you have created processes and threads, you will need a way to run these threads and switch between them. In most operating systems, you must worry about thread priorities or quality of service assurances, which requires wait queue as well as run queue optimizations, but the scheduler for Weenix consists
24 CHAPTER 3. PROCESSES AND THREADS
only of first-in-first-out queues, a function to switch between the contexts of two threads, and a few higher-level functions to abstract away the details of the queues from the caller.
In particular, there is a single run queue from which threads are dequeued (only when the running thread yields control explicitly) and switched onto the processor. There are also many wait queues in the system, most of which will be used as a part of some mutex. When a thread reaches the front of its wait queue, it can be woken up, which involves putting it on the run queue, waiting for it to reach the head of the run queue, and then being switched onto the processor by some other thread running the switching routine.
Switching between threads is the most tricky code to write in this area, and should be done carefully so as not to interact poorly with hardware interrupts. In order to write a correct switch function, you must take the first thread off of the run queue, set the global variables for current thread and current process to point at the new thread and its process, then switch into the new context, all with interrupts blocked (using the interrupt priority level, or IPL). If the run queue is empty, it’s possible that all otherwise-runnable threads are waiting for hardware interrupts, so you must have a way to check this as well. Don’t forget that hardware interrupts, when not masked, can occur between any two code instructions.
3.6 Synchronization Primitives
Since the kernel is multi-threaded, we need some way to ensure that certain critical paths are not executed simultaneously by multiple threads. Once your scheduling functions work, you should be able to implement synchronization primitives as well. The only synchronization primitive used in Weenix is the mutex, whose implementation uses a single FIFO thread queue, although you may also implement condition variables, semaphores, barriers, etc. if you wish to use them.
3.7 Testing
It is your responsibility to think of boundary conditions which could potentially cause problems in your kernel. Test code is an important part of software development, and if you cannot demonstrate that your kernel works properly, we will assume that it does not.
As mentioned earlier, you should run all your test code from the init process’s main function (for lack of a better location), although you can add a new file to hold your tests. To be in the best shape possible before moving on, you should be able to test all of the following situations.
• Run several threads and processes concurrently. Devise a way to show that multiple threads are running and that they are working properly.
3.7. TESTING 25
• Demonstrate that threads and processes exit cleanly.
• Ensure all the edge cases of do waitpid() work correctly.
• Try exiting your kernel both by running proc kill all() and by allowing all threads to terminate normally.
• Demonstrate that the synchronization primitives work.
• Create several child processes and force them to terminate out of order,
making sure they are cleaned up properly.
Keep in mind that this is not an exhaustive list, but that you should certainly be able to demonstrate each of these tests passing by the end of this assignment.
26 CHAPTER 3. PROCESSES AND THREADS
Chapter 4 Drivers
4.1 Introduction
Now that you have processes and threads working properly, you can begin writ- ing the device drivers for terminals, disks, and the memory devices /dev/zero and /dev/null. The code you will write for this part is in the drivers/ direc- tory.
There are two different types of devices: block devices and character devices. The disk devices you will be writing are block devices, while the terminals and memory devices are character devices. These are similar because they share the same interface, but there are significant differences in their implementation. In order to make the relationships between devices easier to manage we use some magic.
Remember to turn the DRIVERS project on in Config.mk and make clean your project before you try to run your changes.
4.2 Object-Oriented C
As you look through the struct definitions of the different devices in the header files, you should notice that the structs for more specific types of devices (e.g. ttys and disks, referred to as the sub-struct from here on) contain the structures for the generic devices (e.g. block and byte devices, referred to as the super- struct) as fields. These are not pointers; they occupy memory that is part of the sub-struct. This way, we can use memory offsets to cast both from sub- struct to super-struct, and vice versa. So, given a pointer to the struct of a byte device which you know is a terminal device, just subtract the size of the rest of the terminal device struct and you have a pointer to the beginning of the terminal device struct. There is a macro provided for the purpose of doing these pointer conversions called CONTAINER OF. In many cases, a more specific macro is defined using CONTAINER OF which converts from a super-struct to a specific sub-struct (for an example, see bd to tty in drivers/tty/tty.c).
27
28 CHAPTER 4. DRIVERS
You should also notice that one of the fields in the device structs is a pointer to a struct containing only function pointers. The generic device types (e.g. block and character devices) each specify that they expect certain operations to be available (e.g. read() and write()). This function pointer struct con- tains pointers to the functions which implement the expected operations so that we can perform the correct type of operation without actually knowing what type of device struct we are working with. The definitions of these function pointer structs are in the C source files of their respective types. Essentially, we are manually implementing a simple virtual function table (which is how C++ implements polymorphism).
4.3 TTY Device
Each tty device is represented by a tty device t struct. A tty consists of a driver and a line discipline. The driver is what interfaces directly with the hardware (keyboard and screen), while the line discipline interfaces with the user (by buffering and formatting their tty I/O). In Weenix, the main purpose of the tty subsystem is to glue together the low level driver and the high level line discipline. The advantage of this is that when a program wants to perform an I/O operation on a tty, it does not need to know the specifics of the hardware or the line discipline. All of these implementation details are abstracted away and dealt with by the functions in drivers/tty/tty.c.
Once you have a working virtual file system (after VFS) you will access the terminals through files, specifically in the files /dev/tty0, /dev/tty1, etc. Then you can read and write to the terminals using the do read and do write functions. Until then, you will need to use the bytedev lookup function to get devices and then explicitly call the device’s read/write functions in order to test your code. A convenient way to do this is by using the kernel shell. For more details, see the testing section at the end of this chapter.
4.3.1 Line Discipline
The line discipline is the high-level part of the tty. It provides the terminal semantics you are used to. Essentially, there are two things the line discipline is responsible for – buffering input it receives and telling the tty what characters to print. Buffering input is what allows users to edit a line in a terminal before pressing enter, or, as we call it, cooking the buffer. The buffer for a line disci- pline is split into two sections, raw and cooked, so that the buffer can be filled circularly. Before a circularly-contiguous segment of the buffer is cooked, the user is able to edit it by editing the current line of text on the screen. When the user presses enter, that segment of the buffer is cooked, a newline is echoed, and the text becomes available to the running program via the read system call. This is why the read system does not return until it receives a newline when reading from a terminal. For simplicity, do not store more input than you can put in the primary buffer (even though you could theoretically use the buffer
4.4. DISK DEVICE DRIVER 29
that the waiting program provided as well).
The other important job of the line discipline is telling the tty which char-
acters to echo. After all, when you type into a terminal, the characters you press appear on the screen. From the user’s perspective, this all happens au- tomatically. From your perspective (you being a kernel hacker), this must be done manually from the tty and the line discipline. The line discipline is also responsible for performing any required processing on characters which will be output to the tty via the write system call. In Weenix, the only characters that are not just echoed are the newline, backspace, and Ctrl+D characters.
The line discipline interface is located in drivers/tty/ldisc.h, and the default implementation of a line discipline, which is the only one you will be implementing, is located in drivers/tty/n tty.c. (It is named N TTY because that is the name of the default line discipline in the Linux kernel.)
4.3.2 TTY Driver
The tty driver is the low level part of the tty, and is responsible for communicat- ing with hardware. When a key is pressed, the appropriate tty driver is notified. If a handler was registered with the driver via the register callback handler function, the key press is sent off to the handler. In our case, the tty subsystem registers the tty global driver callback function with the driver, which calls the line discipline’s receive char method. Then, after any high level process- ing, any characters which need to be displayed on the screen are sent directly to the driver via the provide char function.
The tty driver is already implemented for you. For anyone feeling adventur- ous, feel free to take a look at drivers/tty/keyboard.c, drivers/tty/screen.c, and drivers/tty/virtterm.c.
4.4 Disk Device Driver
A block device is associated with each disk device. This structure contains information about what threads are waiting to perform I/O operations on the disk, any necessary synchronization primitives, the device ID, and any other information required by the ATA protocol. In Weenix, you can assume that all disk blocks are page-sized. We have defined the BLOCK SIZE macro for you to be the same size as the size of a page of memory; use it instead of a hard-coded value.
4.5 Memory Devices
You will also be writing two memory devices, a data sink and source. These will not really be necessary until VFS. Still, these fit will with the other device drivers so they are included in this part of the assignment.
If you have played around with a Linux/UNIX machine, you might be famil- iar with /dev/null and /dev/zero. These are both files that represent memory
30 CHAPTER 4. DRIVERS
devices. Writing to /dev/null will always succeed (the data is discarded), while reading from it will return EOF immediately. Writing to/dev/zero is the same as writing to /dev/null, but reading any amount from /dev/zero will always return as many zero bytes (’\0’) as you tried to read. The former is a data sink and the later is a data source. The low level drivers for both of these will be implemented in drivers/memdevs.c.
4.6 Testing
As always, it is important to stress test your terminal code.
• Have two threads read from the same terminal, which will cause each thread to read every other line. If you’re not sure why this is, ask.
• Make sure that, if the internal terminal buffer is full, Weenix cleanly dis- cards any excess data that comes in.
• Ensure that you can have two threads simultaneously writing to the same terminal.
• Stress test your disk code. This will not be needed until the S5FS assign- ment, but it is a good idea to make sure it works now.
• Make sure that you can have multiple threads reading, writing, and veri- fying data from multiple disk blocks.
• Think of ways that you can write to a disk and display the data stored there.
• Note that Weenix does not currently support Caps Lock
It is very important that you get this code working flawlessly, since it can be a constant source of headaches later on if you don’t. Note that the disk driver only works with page-aligned data, so you should use page alloc() to allocate the memory used in your test cases, not kmalloc().
Since you should now have a functional tty, you should try using the ker- nel shell to test it out. Once you are confident in your tty code, try imple- menting your own kshell commands to run further kernel tests. Below is what to add to initproc run (#include “test/kshell/kshell.h” at the top of kernel/main/kmain.c):
/* Add some commands to the shell */
kshell_add_command(“test1”, test1, “tests something…”);
kshell_add_command(“test2”, test2, “tests something else…”);
/* Create a kshell on a tty */
int err = 0;
kshell_t *ksh = kshell_create(ttyid);
4.6. TESTING 31 KASSERT(ksh && “did not create a kernel shell as expected”);
/* Run kshell commands until user exits */
while ((err = kshell_execute_next(ksh)) > 0);
KASSERT(err == 0 && “kernel shell exited with an error\n”);
kshell_destroy(ksh);
32 CHAPTER 4. DRIVERS
Chapter 5
Virtual File System
5.1 Introduction
The virtual file system, known as the “VFS,” provides a common interface between the operating system kernel and the various file systems. The VFS interface allows one to add many different types of file systems to one’s kernel and access them through the same UNIX-style interface: one can access one’s MS-DOS files via the vfat file system just as easily as one would access various device drivers through the dev file system, kernel internal information through the proc file system or standard on-disk files through the S5FS file system. For instance, here are three examples of writing to a “file”:
$ cat foo.txt > /home/bar.txt
$ cat foo.txt > /dev/tty0
$ cat foo.txt > /proc/123/mem
All of these commands look very similar, but their effect is vastly different. The first command writes the contents of foo.txt into a file on disk via the local file system. The second command writes the contents to a terminal via the device file system. The third command writes the contents of foo.txt into the address space of process 123.
Polymorphism is an important design property of VFS. Generic calls to VFS such as read() and write(), are implemented on a per-file system basis. Before we explain how the VFS works we will address how these “objects” are implemented in C.
5.1.1 Constructors
File systems are represented by a special type (a fs t struct) which needs to be initialized according to its specific file system type. Thus for each file system, there is a routine that initializes file system specific fields of the struct. The convention we use in Weenix for these “constructors” is to have a function called
33
34 CHAPTER 5. VIRTUAL FILE SYSTEM
be initialized is passed in to the function, not returned by the function, allowing us to leave the job of allocating and freeing space for the struct up to the caller. This is pretty standard in C. Additionally, some objects have a corresponding “destructor”
5.1.2 Virtual Functions
Virtual functions (functions which are defined in some “superclass” but may be “overridden” by some subclass specific definition) are implemented in the Weenix VFS via a struct of function pointers. Every file system type has its own function implementing each of the file system operations. Our naming con- vention for these functions is to prefix the function’s generic name with the file system type, so for example the read() function for the s5fs file system would be called s5fs read(). Every file system type has a struct of type fs ops t which lists all of the operations which can be performed on that file system. In the constructor for the file system, pointers to these fs ops t are added to the fs t struct being initialized. One can then call these functions through the pointers, and you have instant polymorphism.
5.1.3 Overview
This section describes how the VFS structures work together to create the vir- tual file system.
Each process has a file descriptor table associated with it (the proc t field p files). Elements in the array are pointers to open file objects (file t structs) in a system-wide list of all file t objects that are currently in use by any pro- cess. You can think of this as the system file table discussed in the “Operating Systems Design” lectures. Each process’s array is indexed by the file descrip- tors the process has open. If a file descriptor is not in use, the pointer for that entry is NULL. Otherwise, it must point to a valid file t. Note that multiple processes or even different file descriptor entries in the same process can point to the same file t in the system file table. Each file t contains a pointer to an active vnode t. Once again, multiple system file table entries can point to the same vnode t. You can think of the list of all active vnote ts as the active inode table discussed in the “Operating Systems Design” lectures. Through the vnode t function pointers you communicate with the underlying file system to manage the file the vnode represents.
With all of these pointers sitting around it becomes hard to tell when we can clean up our allocated vnode ts and file ts. This is where reference counting comes in.
5.1. INTRODUCTION 35 Reference Counting
As discussed in the overview of VFS, there are a lot of pointers to vnode ts and file ts, but we need to make sure that once all of the pointers to a structure disappear, the structure is cleaned up, otherwise we will leak resources! To this end vnode t and file t both have reference counts associated with them, which are distinct but generally follow each other. These reference counts tell Weenix when a structure is no longer in use and should be cleaned up.
Rather than allocating space for these structures directly, the *get() func- tions described below look up the structures in system tables and create new entries if the appropriate ones do not already exist. Similarly, rather than di- rectly cleaning these structures up, Weenix uses the *put() functions to decre- ment reference counts and perform cleanup when necessary. Other systems in Weenix use these functions together with the *ref() functions to manage reference counts properly.
For every new pointer to a vnode t or a file t, it may be necessary to increment the relevant reference count with the appropriate *ref() method if the new pointer will outlive the pointer it was copied from. For example, a process’s current di