Kernel Window Manager and Network Driver - Description
This project was the final project for the honors operating systems course I took the Fall 2014 semester. This project was open-ended -- each student was allowed to choose what to do.
I worked in a group on this project with Yuqian (Linda) Jiang.
This course consisted of building a kernel and operating system from scratch over the course of the semester. The final version included process management, virtual memory, system calls, multithreading, interrupt handling, system calls, user mode and protected mode execution, a file system, a shell, timers, etc. User code is loaded from the file system -- any compiled program using the ELF format should work, as long as it only uses system calls we have implemented.
For the final project, we implemented a graphical Window Manager with desktop window composition and full stack Networking with support for a custom UDP-like protocol (and IPv4) we designed for this project, as well as ping. We did all of the research on how to do this ourself.
This is the github link to our project: cs439hp12 repository
The following is a summary of the report we wrote for this project.
This video shows two instances of the operating system running in two separate QEMU emulators. It shows a multiplayer Pong game running. The Pong games in the two windows are connected to each other over the network. The dedicated server runs in the instance on the right. I only control one paddle in this video because it's difficult to switch QEMU's focus to the other window before losing. It also demonstrates the Window Manager's ability to switch which window is in the foreground, as well the ability to move the currently selected window.
The Window Manager is a user program running in user mode. We implemented system calls for acessing and locking access to the GPU VGA memory. The Window Manager performs desktop window composition to render multiple process windows.
It is set to be run automatically by the shell when the system starts. The user can cycle the foreground window by pressing 'p'; the user can move the current foreground window with i,j,k,l.
A process resource called ScreenBuffer was created for this. The screen buffer allows a process to write to VGA memory. Any process may request a screen buffer - the first process to request a screen buffer resource is granted a lock on writing to vga memory. A process only (and automatically) creates a window if it requests a screen buffer resource. This instance of screen buffer is also tracked globally. Subsequent processes requesting a screen buffer still receive one. But their buffer writes (via the WriteScreenBuffer() syscall) do not go directly to vga memory, but instead to the screen buffer's personal memory. The screen buffers are stored as children of the main buffer. The process owning the main buffer can request the buffer memory of its screen buffer resource's child screen buffers, and then compose the buffers as it wishes. This allows the window manager process to correctly combine the displays of overlapping windows.
When a new process requests a screen buffer resource, the request action is added to a queue in the main screen buffer. The owner of the main screen buffer can use the syscall GetNewWindowRequests() and GetBufferRequestCount() (these functions have the side effect of removing the item as well from the queue) to query for new request actions in this queue. The window manager uses these functions every update frame so that it can create new window objects with the process id of the child process and manage them.
The window manager keeps a list of these window objects, and each frame, requests the video buffer memory from each child (with the syscall GetChildBuffer(char* buffer, isn't processId)). It then writes the child buffer into its own buffer. Finally, after copying the data from every child buffer, it uses the WriteScreenBuffer() syscall to write to VGA memory.
The window manager maintains an ordered list of process windows. The foreground window is always rendered on top.
The syscalls LockScreenBuffer(int id) and UnlockScreenBuffer(int Id) allow the buffer to be locked so that it is not read and written at the same time. A process writing to a buffer should lock it first.
The window manager also manages routing key input to the foreground process window (the qemu program window must be selected - input from the console is not routed). The controls for managing windows (p, I, j, k, l) are intercepted by the window manager and not routed).
The syscall GetKeyPresses(char* buf, int bufferLength) has the keyboard interrupt bounded buffer be copied into a buffer to be read by the requesting process and clears the buffer. In this case, only the window manager calls this function.
The syscall QueueChildKeyInput(int childProcessId, char key) allows the window manager to pass the key input it reads from GetKeyPresses() to the current foreground window processes's key input buffer. Each process can use the syscalls GetQueuedKeyPressCount() and GetQueuedKeyPresses(char* buf, int bufferLength) to retrieve key input from their own process's local key input queue).
- GetScreenBuffer(int width, int height) //create screen buffer resource
- WriteScreenBuffer(int resourceId, unsigned char* buf) //copy user video buffer to system
- GetNewWindowRequests(int* buf) //get process ids and dimensions for process who have requested a window to be created and clears the window request queue
- GetBufferRequestCount() // get the number of processes who have requested a window since the request queue was last cleared
- GetChildBuffer(unsigned char* buf, int processId) //get the last written graphics data written by a particular process
- LockScreenBuffer(int resourceId) //lock read / write access to buffer
- UnlockScreenBuffer(int resourcdId) //unlock read / write access to buffer
We implemented a full network stack from scratch. We wrote a kernel driver for the RTL8139 network card (an ancient piece of technology), and implemented support for IPv4, ICMP, and P439 (P439 is what we named our custom protocol) and user-mode-accessible socket descriptors.
- TestDraw() // initializes the network
- Ping(unsigned char destIP) //ping
- OpenSocket(int protocol, int port) //open socket resource for process, using specified protocol to listen on specified port
- ReadSocket(int socketDescriptor, unsigned char srcIP, unsigned char* buffer, unsigned int bufferSize) //read up to bufferSize bytes from the the next queued packet on the calling process's received packet queue.
- WriteSocket(int socketDescriptor, const unsigned char destinationIP, const unsigned char* const buffer, int bufferSize, int port) //send bufferSize bytes to dest IP:port using protocol of specified socket
We implemented a driver for the RTL8139 network card. We use DMA and IRQ interrupts to handle sending and receiving data. Our driver initializes the network card with the PCI, handles buffer management, etc. The driver interprets data in its abstract form from processes and converts it into data the network card should read, for the correct protocols.
The P439 protocol is similar to UDP, but the only data in its header field is a port number.
We supported ARP, ICMP via IPv4 and P439 via IPv4.
The class Network contains the low level code for interacting directly with the network card and for handling the details of each particular protocol, and our ARP cache. The class NetworkProcess handles the high-level communication between the network and other processes.
Network process is a new process that runs forever in the background to manage the destinations of network packets. Packets are never sent or received directly by processes. They are sent to the NetworkProcess process, which queues them, and during NetworkProcess's run(), it handles sending and receiving the queued packets.
When a new packet is received, it is dissected by the Network class. If it is found to be a packet whose protocol uses the socket table, it is passed to Process::networkProcess- >QueueNetworkReceive(packet); and queued to be later sent to the destination process. At this point, the packet data itself has been stripped of its header data.
Each time the NetworkProcess Run()'s, it directs the packets in its receive queue to the correct receive queues of the destination process the packet is intended for. The correct destination process of a packet is determined by looking at the port number in the header of the packet. The port number is an index into the static socket table. The user program can use syscalls to read its own packet receive queue.
When a new packet is sent using a syscall, it is sent into NetworkProcess's send queue. When NetworkProcess Run()'s, it empties its send queue into Network::SendPacket().
Packets sent from syscalls contain no headers. It is the job of Network::SendPacket() to finally build the header immediately before the packet is sent. This is so that the user never has to worry about any header data - it just calls send with a socket and a data buffer. We skipped a layer of our network stack and just had the driver handle this.
If, when attempting to build the header, the Network::SendPacket() finds a miss in the ARP cache, failure is returned with the side effect that SendPacket() queues its own ARP request packet, and the NetworkClass requeues the failed packet for a send attempt 100 milliseconds later.
For sending packets to 127.0.0.1, packets are routed directly to the receive queue of NetworkProcess and skip the network card.
Networked Pong Game with Dedicated Server
To see this game being run, watch the video at the top of this page.
This pong game uses a dedicated server user program which can be launched on any instance of the kernel. Two instances of the pong program can be launched from any computer with the IP address of the server as an argument. The players press 't' to send a packet to the server notifying it is ready to start. When at least two clients have connected to the server, the game starts. All game logic is performed server-side -- the client program sends player input to the server; the server constantly sends ball position information to each client that is connected. When a player loses, its background changes to a frown face, and the winner's background becomes a somewhat mildly happy face. We wrote an image loader to support drawing the faces.
Network Drawing Program
This program is a peer-to-peer network program allows the user to draw on the window of this program running on a different computer. The user runs this program by supplying the destination IP address of the other computer running this program, as well as the port to send data to, and the port to listen for incoming drawing data. The user can use the w,a,s,d keys to draw.
Both comptuers running the program can draw on each other's window.