Graphics: from pixels to windows

Current state of the GUI With SnowflakeOS starting to have more of the pieces a proper hobby OS should have, it was time to make this state of affair visible from the outside. Graphics! Ironically, by switching away from text mode, we lose the immediate ability to print text, but as you’ll see we’re going to get it all back. At some point anyway; what’s presented here is the beginning of this process.

The boring part: switching video mode

A prerequisite to doing anything is to get the screen in a state in which we can access individual pixels instead of just characters. The traditional way of doing so is to manually call BIOS functions to get available modes and choose one while the computer is still executing in real mode. In the case of SnowflakeOS, this isn’t practical: the kernel is loaded by GRUB, so it starts executing in protected mode, where we can’t access BIOS functions. There are two ways around that:

  • Enable virtual 8086 mode - an emulation of real mode - long enough to set the video mode, then get back to protected mode
  • Ask GRUB to set the correct video mode before loading our kernel

The first option is the one most advertised on the osdev wiki, and at first it was the only one I knew about. Switching to virtual 8086 mode is easy enough, it involves faking an interrupt return in order to set the VM bit in the eflags register, kind of how we switched to ring 3 for the first usermode process. I don’t known much about this mode given that I didn’t end up implementing support for it, but there were several issues I could see taking a lot of work to resolve: how does execution get back to the kernel? do I have to implement support for virtual 8086 tasks within my scheduler? do I need to compile the executing code in 16-bit mode? what happens to my kernel stack?… Far too much work that feels like writing boilerplate code. I was very happy to discover an alternative.

The second option is simpler by a long shot. Asking GRUB to set the video mode is as easy as modifying the multiboot header that’s sitting at the very beginning of our kernel binary:

.section .multiboot
    .long MAGIC
    .long FLAGS_PAGE_ALIGN | FLAGS_MEMORY | FLAGS_GRAPHICS
    .long -(MAGIC + FLAGS) # checksum
    .long 0x00000000
    .long 0x00000000
    .long 0x00000000
    .long 0x00000000
    .long 0x00000000
    .long 0    # 0 for a linear framebuffer, 1 for text mode
    .long 1024 # width
    .long 768  # height
    .long 32   # bpp

The downside is that you can’t choose a resolution or bit depth dynamically: if the precise mode you asked for isn’t available, GRUB will choose one for you. That sounds like a fair tradeoff to me.

GRUB gives us a framebuffer described by the following entries in the multiboot structure:

typedef struct {
    uint64_t address;
    uint32_t pitch;
    uint32_t width;
    uint32_t height;
    uint8_t bpp;
    uint8_t type;
    // Technically, the layout of the following fields depends on the value of `type`
    uint8_t red_position, red_mask_size;
    uint8_t green_position, green_mask_size;
    uint8_t blue_position, blue_mask_size;
} __attribute__ ((packed)) fb_info_t;

Some fields are a bit obscure here: pitch is the number of bytes per rows, bpp is the bit depth, type should be 0 (otherwise GRUB gave us text buffer), and the color fields indicate the pixel layout.
I think the reason pitch is given here is that there can be padding bytes between each “line” of pixels, so it may not necessarily equal width*bpp/8, though it does for QEMU and Bochs.

The address field refers to a physical address, so we mustn’t forget to map it after enabling paging. For a 1024x768x32 mode, the framebuffer is 3 MiB large, so it’s not exactly a trivial allocation in the kernel heap, where I chose to map it. An alternative would be to map it on request in processes’ address spaces where addresses are aplenty, but I’d rather not expose it raw to usermode applications.

Rocking that framebuffer

Plotting pixels

Now that we have an address to write to, plotting a pixel is a matter of computing its offset and knowing its format. The address of the pixel at (x, y) is given by

uint32_t* offset = (uint32_t*) (address + y*pitch + x*bpp/8);

Once you’re there, all that remains is implementing some drawing primitives. Rectangles, lines, borders…
Line drawing algorithms are somewhat convoluted, there are several and I ended up implementing Bresenham’s algorithm which is well-detailed on wikipedia.

Getting our text back, the PSF format

128 characters ought to be enough for anybody

The most straightforward way to draw text has to be through bitmap fonts. In a bitmap font, a character is represented by an array of bits, with say each n bits representing a line of pixels in the character. For example, here’s a very crude ‘O’:

0 1 0
1 0 1
0 1 0

It turns out there’s a dead easy format still in wide use: PSF, for PC Screen Font, used by virtual consoles in Linux.

There are two versions of this format:

  • PSF1: fixed number of characters, 8 pixels wide, variable character height
  • PSF2: variable number of characters, variable character size

Both formats have a short header at the beginning of the file. On my machine, all fonts in /usr/share/kbd/consolefonts seem to be PSF1. In this format, the header looks like this:

typedef struct {
    uint8_t magic[2];
    uint8_t mode;
    uint8_t height;
} font_header_t;

Where magic should equal 0x36, 0x04, mode contains information about the number of characters and unicode support (which I haven’t dealt with), and height is the height of each character in pixels.
The actual font starts right after the header, so the offset of an ASCII character c in the font file, in bytes, is given by

uint32_t offset = sizeof(font_header_t) + c*height;

Drawing a character is then a matter of checking individual bits, line by line, and plotting pixels accordingly.
I extracted the font used in my console with

setfont -o font.psf; xxd -i font.psf > font.h

and used that one. The characters are those shown in the image above, in 8x16 format.

From rectangles to windows: a window manager

Until now we’ve only drawn shapes the the screen. What turns a shape into a window? By my definition, a window manager (WM).

Design

In SnowflakeOS, the window manager handles only two concepts:

  • windows: those are rectangular buffers with an (x, y) position, a z-order and a few flags
  • focus: who gets user input?

It knows nothing of window decorations, concepts of desktop background, taskbar, or even mouse pointer. Those things will be windows, managed by userspace applications, clients of the WM.
As far as I know, this minimalist approach is somewhat close to how weston works, a window manager for wayland.

The WM needs to communicate with applications wishing to use windows. Usually, the WM is a userspace program, so this is done using a form of inter-process communication. I decided against implementing such a system for now - I tried my hand at a virtual file system, pipes and all, but I felt I didn’t have enough background to properly design anything, or to implement the usual APIs of Unixes.
Thus, I implemented the WM in the kernel, and programs communicate with it through system calls. It’s a pretty crude and non-general way of communicating, but it works for now.

The userspace API

I introduced a library for SnowflakeOS programs, thoughtfully named snow, which wraps system calls in pretty C functions.
It offers a snow_open_window function which allocates a buffer of the window’s size. Drawing functions then write to that buffer, and the program asks for that window to be drawn to screen by calling snow_render_window. There are no GUI functions right now - only mockups - but they’ll sit between those two calls. Closing the window is then done though snow_close_window.

Here’s an example of what can be done right now:

#include <snow.h>
#include <string.h>

int main() {
    window_t* win = snow_open_window("A static window", 300, 150, WM_NORMAL);

    snow_draw_window(win); // Draws the title bar and borders
    snow_draw_string(win->fb, "Lorem Ipsum", 45, 55, 0x00AA1100);
    snow_draw_border(win->fb, 40, 50, strlen("Lorem Ipsum")*8+10, 26, 0x000000);

    while (true) {
        snow_render_window(win);
    }

    snow_close_window(win);

    return 0;
}

Giving this result:

that look has to change, I know

Implementation

Registering a window

This means appending a given buffer to a list of windows to be drawn, and assigning it a z-order and unique id, a window being defined as

typedef struct _wm_window_t {
    struct _wm_window_t* next;
    struct _wm_window_t* prev;
    fb_t fb;
    uint32_t x;
    uint32_t y;
    uint32_t z;
    uint32_t id;
    uint32_t flags;
} wm_window_t;

This is my second use of intrusive lists in SnowflakeOS. I really ought to make a utility library to handle those, as I’ve had to write some very repetitive code in functions such as wm_find_with_id, wm_find_with_flags or wm_find_with_z. The lack of lambdas in C can really be felt in this situation.

Handling z-order

This was less trivial than anticipated! Here’s how I handled it. Z-orders are consecutive natural numbers, with 0 being the least visible window (e.g. a desktop background), and higher numbers being drawn on top of lower numbers.
A newly opened window is assigned the highest z-order. When a window is closed, z-orders are shifted so that there is no gap between 0 and the highest z.
Windows with a flag like WM_FOREGROUND will always stay on top of others, and similarly, those with WM_BACKGROUND fight for the lowest z-order.

I’m making things up as I go, to be honest. I’m sure I’ll figure out the good from the bad in due time :)

Drawing a full frame

Edit: this is a poor implementation, see the next post for a better one.

The goal here is to draw windows in the correct z-order. Keeping in mind that window buffers are in the clients’ address spaces, we have at least two options:

  1. at a regular interval, iterate over our windows in correct z-order, switch to their respective address space and copy their buffer to the screen
  2. when a client tells the WM that its window can be drawn, check if it’s their turn and if so draw them. Otherwise, lose a frame for that window.

With option 1, I don’t know how to avoid drawing a window to the screen when its buffer may be in a “partially drawn” state, plus the method of switching address spaces is pretty barbaric, and I’m sure very slow.

I went for option 2, which I believe the code can explain quite well:

void wm_render_window(uint32_t win_id) {
    wm_window_t* win = wm_get_window(win_id);

    // If it's not our turn, return
    if (win->z != current_z) {
        return;
    }

    // Render the window to the off-screen buffer
    uint32_t* off = (uint32_t*) (fb.address + win->y*fb.pitch + win->x*fb.bpp/8);

    for (uint32_t i = 0; i < win->fb.height; i++) {
        memcpy(off, (void*) (win->fb.address + i*win->fb.pitch), win->fb.pitch);
        off = (uint32_t*) ((uintptr_t) off + fb.pitch);
    }

    // If all windows are drawn, write to the screen
    if (current_z == wm_get_max_z()) {
        current_z = 0;
        fb_render(fb);
    } else {
        current_z++;
    }
}

Apart from dropping draw calls, this method has the downside that a slow client will slow the whole thing down: the WM will wait for its draw call and drop all others in the mean time.
Good thing SnowflakeOS apps are always lightning fast ;)

The next steps

In no particular order, this is what I want to get to:

  • cleaning up the code: these changes brought a lot of mess
  • windows need to get keyboard and mouse events
    • a mouse pointer
    • moving windows around
    • porting my “Mandelbrot visualizer” app to SnowflakeOS
  • C++ support in userspace
  • a GUI system

Long time no C

It’s been a while since the last entry in this blog, but I’m hoping to pick up the pace. I’ve been very busy programming-wise with school projects, but less so now.
One can’t reasonably spend their time writing C#, can they?

Written on December 15, 2019