It is time to reap the rewards of your hard work during this semester. In this assigment, you implement an application of your choice. If possible, use several threads and synchronize them via semaphores.

Learning Objectives

Using threads and semaphores
Applying more comprehensive libraries
Having fun

Libraries

This assignment is meant to be a playground for you. To assist you in writing an application of your choice, the handout provides a multitude of libraries and infrastructure, including:

a simple random number generator
a file system and
a graphics mode
a dynamic allocator.

Equipped with these components, we encourage you to write (or port) a simple game, a minimal shell or an office program.

Random Number Generator

Random provides a pseudo-random number generator based on the Mersenne Twister. You have to initialize the instance with an initial value (a so called seed), and then it will return a new "random" number (32 bit) with every subsequent call to Random::number().

Note: Instances with the same initial value will return the same sequence of numbers (not very random, right?). You can use the RTC as seed for a (ostensibly) more non-deterministic behaviour. But better avoid using Random for cryptography!

Dynamic Memory Allocator

Can you still remember writing a dynamic memory allocator during your undergraduate studies (A4 in Betriebssysteme)? Well, the file system and parts of the graphics library (e.g. PNG or Font) need one to work properly. We provide you with an Buddy allocator. It is a very basic implementation providing malloc() and free() is: A pre-allocated memory block [array] with the management of memory blocks done in a linked list. If you are keen (and have too much spare time), you can try to implement more sophisticated allocation strategies for example. You can still write your own if you want. If so, you might want to check the correct behaviour in user space (easier than debugging in your kernel).

Note: For the graphics example, you have to ensure that the statically allocated memory is large enough (at least 16 MiB are required).

Having implemented the allocator, you can easily extend StuBS in such a way that it supports the C++ operators new and delete: Just define void *operator new(size_t) as a thin wrapper of malloc() (and extend void operator delete(void *) to use free()) in compiler/libcxx.cc – don't worry, it's just a one-liner!

Minix File System

Preface

The Minix (3) file system (extracted from Linux) may simplify your data management. Minix not only influenced the Linux kernel, but its file system also influenced the extended file system (you probably know or even use one of its successors ext2 and ext4).

The VFS offers you a POSIX-like interface (e.g., VFS::open() and VFS::read()) to access the contents.

Image Creation

The utility in fs/tool uses the same file system code as StuBS to access an image directly. Without requiring special privileges, you can copy and modify the files and folders with FTP-like commands.

To simplify things, we have already provided you an abstraction for building and executing the FSTool in your Makefile: it will automatically pack all files in the kernel folder ./initrd/ into a new initial ramdisk (stored in build/initrd.img), along with about one megabyte of free memory. You can change the directory location and the free memory (in bytes) using the Makefile variables ‘INITRD_DIR’ and ‘INITRD_FREE’ respectively.

If you want to manually create an file system image, you can do that using standard Linux tools. Here is an example that creates an image with a size of one megabyte:

dd if=/dev/zero of=~/file.img bs=1MiB count=1
mkfs.minix -3 /dev/loop0  # optional --inodes <number>

In order to add files to the image, you must mount it first, e.g. with mount ~/file.img /mnt/tmp/. In the lab this is not as easy due to security concerns (and the lack of a working FUSE file system). A possible solution would be libguestfs, which works internally with a virtual machine and thus allows access to the file system.

Usage in StuBS

You can provide the file system either using the ATA driver for (QEMU-) hard disks or via a temporary data carrier in main memory (e.g., the initrd).

While the second variant does not allow you to store changes persistently, it should nevertheless be used on the test hardware due to its easy deployment – the StuBS Makefile is already able to transfer your image file as initial ramdisk to the test systems or load it in Qemu/KVM.

If you now want to use it in StuBS, you must first initialize the Ramdisk (with the memory address provided by the Multiboot information) as a block-oriented device before you can mount the actual file system:

#include "boot/multiboot/data.h"
#include "fs/ramdisk.h"
#include "fs/vfs.h"
 
// ...
 
void main() {
    // ...
 
    // Load the ramdisk (= the first module)
    Multiboot::Module * initrd = Multiboot::getModule(0);
    if (initrd == nullptr) {
        kout << "No initial ramdisk - abort!" << endl;
        Core::die();
    }
 
    Ramdisk ramdisk(initrd->getStartAddress(), initrd->getSize());
 
    int error = VFS::mount("minix", &ramdisk, "");
    if (error != 0) {
        kout << "Error mounting ramdisk (minix): " << -error << endl;
        Core::die();
    }
 
    // ...
    // Open file with VFS::open() (or GuardedVFS::open() in an thread)
}

Graphics Mode

Graphics provides you with a simple interface to the VESA BIOS Extensions, a basic graphics mode. However, if you want to use it, you will need to do a little work.

Initialization

A suitable graphics mode might not be selected by the Multiboot-compatible boot loader. (It depends on the assigenment template.) Please go to boot/multiboot/config.inc, and ensure

MULTIBOOT_HEADER_FLAGS equ 0

is changed to

MULTIBOOT_HEADER_FLAGS equ MULTIBOOT_VIDEO_MODE

You can specify the desired attributes in the file boot/multiboot/config.inc by setting MULTIBOOT_VIDEO_MODE in the MULTIBOOT_HEADER_FLAGS and adjusting MULTIBOOT_VIDEO_WIDTH, MULTIBOOT_VIDEO_HEIGHT and MULTIBOOT_VIDEO_BITDEPTH.

Attention: If the desired mode is not available, a similar mode will be selected. Hence, you cannot rely completely on the exact screen resolution.

Note: Qemu/KVM does not offer a real Multiboot compatible bootloader when started with the kernel parameter (which is used in the Makefile). Therefore, you have to create a full system image with an extra bootloader (e.g., Grub). This is already implemented in our Makefile. Just append -iso to the emulation targets, like make kvm-iso. However, PXELinux used for the netboot is compatible and does not require any special handling.

Similar to TextStream, you need a global instance of GuardedGraphics in your kernel, calling GuardedGraphics::init() during system initialization:

// Maximum visible display
const unsigned fb_width  = 1280;  
const unsigned fb_height = 1024;  
const unsigned fb_bpp    = 32;    
 
const unsigned fb_size = fb_width * fb_height * fb_bpp / sizeof(char);
char buffer_1[fb_size] __attribute__((aligned));
char buffer_2[fb_size] __attribute__((aligned));
GuardedGraphics graphics(fb_size, buffer_1, buffer_2);
 
// ...
 
void main() {
    // ...
    if (!graphics.init(true)) {
        kout << "Not able to initialize Framebuffer - abort!" << endl;
        Core::die();
    }
    // ...
}

Basic Usage

Additionally to initializing the graphics card's framebuffer, the example code above reserves two memory areas for double buffering:

The front buffer contains a full screen image ready to be displayed
Drawing operations are performed on the back buffer

The provided graphics primitives allow drawing lines and rectangles, output of text (like demonstrated in the example Title ) with different fonts and direct pixel manipulation (see example Fire).

After you have finished all drawing operations on the back buffer, call Graphics::switchBuffers() to atomically exchange both buffers: the back buffer will become the new front buffer and vice versa.

With Graphics::scanoutFrontbuffer() the contents of the front buffer are copied into the video memory. You can either call this method as part of the drawing loop whenever a new frame has been finished, or you can execute it in Watch::epilogue(), which ensures that the graphics card's frame buffer is updated at a fixed frequency. The GraphicsExample relies on the second variant. Hence, if you enable the GraphicsExample, ensure that Graphics::scanoutFrontbuffer() is called. Since the GraphicsExample relies on an initialized Graphics device, it must be dynamically allocated using new. The constructor makes use of the syscall interface, i.e., guarded objects. Hence, ensure that the object is created outside a guarded section.

Attention: Since the scanout is quite expensive, you should not execute it on every timer interrupt – it would cause a very high system load. A refresh every 20ms (corresponds to a maximum of 50 frames per second) is a good compromise between the frame rate and the overhead caused by the copy operations. Since your timer interrupt will usually occur every millisecond, you should perform the scanout only every twentieth epilogue. Hence, limit the execution of Graphics::scanoutFrontbuffer() to every twentieth epilogue. The PC example will measure and display the current refresh rate using a frame buffer console.

Bitmaps

If you want to include your own images like demonstrated in the Pong example, open/draw them in GIMP and export them as C source code (*.c). You should not use glib types. The resulting .c file contains the corresponding binary data in a struct (this structure is identical to GIMP), which can be displayed using the image method.

Attention: Embedding bitmaps directly in the source code can considerably increase the size of the resulting system image.

Portable Network Graphics

Using lossless compressed PNG files might solve problems of large binary files.

Note: The library (based on uPNG) requires dynamic memory management.

Attention: The library only supports RGB and grayscale images (with and without alpha channel) – but not images with a custom color palette.

You can either include the image as a static data array in C source code using xxd -i image.png > image.c, or you can simply use the file system by storing the PNG image at ./initrd/image.png, while using /image.png as path for a new PNG object in StuBS.

Attention: Since unpacking compressed images is resource-intensive, make sure you have enough memory – both stack and heap!

The methods provided by the graphics library also support sprite sheets, which can be used for animations (see example Cat)

Debugging

Since the messages written to the CGA TextMode are no longer visible on the screen after switching to the Graphics mode, it might be a good idea to redirect the debug output via the serial connection. It is quite easy to modify the existing DBG macro accordingly after replacing dout with a global SerialStream instance:

#include "device/serialstream.h"

SerialStream dout;

SerialStream

Console (VT100 compatible) via Serial interface.

Definition: serialstream.h:26

dout

TextStream dout[Core::MAX]

Debug window.

Definition: main.cc:7

serialstream.h

Serial output stream

Hall of Fame

Worthy solutions for this assignment from previous years can be found on the test hardware in the network boot menu entry Hall of Fame.

Note: Unfortunately, some of the old examples no longer work on out test computers due to the switch to the "new" test hardware (Intel Core i series, which is a bit more sensitive to the standard than the previous Intel Core 2 series). However, you can still run most of them in QEMU/KVM: kvm -kernel /fs/stubs/halloffame/13_schach.elf

You've created some amazing application? Please send them to us (preferably with source), and with a bit of luck it will soon be in the Hall of Fame as well!