Assignment 7: Application for StuBS

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 is exercise is meant to be a playground for you. Therefore, we provide you with a multitude of libraries and infrastructure that will assist you in writing an application. You are provided with a simple random number generator, a file system, a graphics mode, and a simple dynamic memory allocator. Equipped with these components, we encourage you to write a simple game, a minimal shell or an office program.

A short explanation of all additional components follows.

x87 Floating Point Unit

x87 Floating Point Unit contains a tutorial on how to enable hardware support for floating point operations. This can be useful if your app heavily relies on floats (e.g. for rendering).

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?). Without implementing a driver for the RTC, you have no proper source of randomness for the seed. Therefore, better avoid using Random for cryptography!

Dynamic Memory Allocator

Can you still remember writing a dynamic memory allocator during your undergraduate studies ? Well, the file system and parts of the graphics library (e.g. PNG) rely on a proper allocator for variable sized objects to work properly.

In order to lift the burden of implementing an allocator, you have already done enough this semester, we provide you with a simple buddy allocator that distribures a pre-allocated memory block [array]. The allocator provides you with malloc() and free() and lives in utils/alloc.h and utils/alloc_buddy.h.

Furthermore, we also extended the template to provide the C++ operators new and delete: Both are just thin wrappers around malloc() and free(). The implementation of this lives in compiler/libcxx.cc.

Minix File System

We provide you with a driver for Minix file systems. The "disk" for this driver is supplied by an initial ramdisk (initrd) that is loaded by the bootloader into memory.

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

You can easily create file system images 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 ~/file.img # optional --inodes <number>

In order to add files to the image, you must mount it first, e.g. with mount ~/file.img /mnt/tmp/.

However, 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.

Usage in StuBS

The data for the file system lives in the main memory in an initial ramdisk.

While using a proper disk drive (e.g. ATA) would allow us to make changes persistently, it is easier for this exercise to rely on transient memory. 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)
    int fd = VFS::open("title.txt", O_RDONLY);
    if (fd >= 0) {
        char buffer[200];
        int n = VFS::read(fd, buffer, sizeof(buffer) - 1);
        buffer[n] = 0;
        kout << buffer << endl;
    }
}

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 is already selected by the Multiboot-compatible boot loader. 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:

// enthält extern GuardedGraphics graphics;
#include "syscall/guarded_graphics.h"
 
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 uses the second variant.

Note

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. The PC example will measure and display the current refresh rate using a frame buffer console.

Minimal Working Example

After initializing the graphics subsystem, you can just use the following code to print a moving "Hello":

#include "syscall/guarded_graphics.h"
...
void main() {
    ....
    Color fg(0x33, 0x88, 0xcc);
    int x = 0;
    while(1) {
        graphics.clear();
        graphics.text({.x=230+x, .y=10+x}, "Hallo", 5, fg);
        x = (x + 1) % 20;
        graphics.switchBuffers();
        graphics.scanoutFrontbuffer();
    }
}

Example Application

We also ship with a larger example application in user/graphic/example.h. In order to activate that, create an appropriate thread object and hand it to the scheduler.

#include "user/graphic/example.h"
...
void main() {
    ...
    GraphicsExample * graphicsExample = new GraphicsExample();
    scheduler.ready(graphicsExample);

Attention

For this application it is required to GuardedGraphics::scanoutFrontbuffer() periodically. Most probably you want to place it in the Watch::epilogue().

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.

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;