Sunday, October 02, 2005

Writing multiboot PE kernels using Visual C++ - Part II

My earlier post explained “how” you can write a multiboot kernel using VC++. This post will explain “why” I wrote the kernel the way I did.
  • The linker (link.exe) puts machine code of functions in the source text into the .text section in the order it finds them in the source.

  • All PE headers never add up to a total size that exceeds 4K. So when file alignment is 4K (== memory alignment), the .text section is guaranteed to start at offset 4K (4096) in the PE file. This is a good place to put the multiboot header (which anyways needs to be present in its entirety within the first 8192 bytes)

  • The multiboot header forms the first 48 bytes of the .text section

  • __declspec(naked) is an attribute that makes the compiler generate code _WITHOUT_ a prolog or epilog. This is important because we want the multiboot header to start at offset 4096. Without the naked attribute, the function (and hence the .text section) would start with the bytes 55 8B EC which stand for the following instructions
    55         push   ebp
    8B EC  mov   ebp,  esp
    which is the prolog. Because of this the multiboot header would be pushed to offset 4099 and Grub would refuse to load the kernel because the multiboot header isn’t 4K longword aligned. [Updated: 10/6/2005, 12:23 PM].

  • Compiler switches

    • /Gd : forces the use of __cdecl calling convention. I’m not really sure why I included this

    • /Fm: names the map file which might be useful when the kernel gets large

    • /Tc: compile the file as .c

    • /c: compile only, no link

  • Linker switches

    • /safeseh:no: disables generating the symbols related to Safe SEH handlers (__safe_se_handler_table and __safe_se_handler_count)

    • /filealign:0x1000: this is an undocumented switch that aligns sections in the file based on this value. I’ve set it to 0x1000 (4K) so that sections are aligned on a 4K boundary on the image also (this is the default in-memory alignment). This is required because, Grub doesn’t seem to load images whose file alignment is different from in-memory alignment.

    • /base:0x100000: this makes the linker generate code assuming that the .text section starts at physical address 0x101000 and .data section at physical address 0x102000. This is what we want because Grub actually loads the image at 0x100000 which forces the .text and .data section into these addresses automatically and we need not relocate the kernel. (Now you probably understand why we set the file alignment to 4096 bytes as well).

    • /entry:__multiboot_entry__: sets the entry point

    • /nodefaultlib:libc: forces the linker to ignore libc while resolving external references. The idea is to be able to use names like memcpy etc in the kernel, and make sure the libc’s functions don’t get linked in.
    • /subsystem:console: This sets a bit in one of the headers that tells windows which subsystem to use to execute this application. This doesn’t make any sense here, but I guess I included this to keep the linker happy.

    • /out: kernel.exe: the name of the kernel

Saturday, October 01, 2005

Writing multiboot PE kernels using Visual C++

Update [1/29/2012]: Source code now available here.

Aspiring operating system developers who target x86 often don’t get beyond writing a boot sector (seldom do they even complete it) because of the inordinate amount of time needed to understand the “tricks” required to get the processor into a “sane” mode of operation before the kernel can start executing. That’s why newbie kernel developers are always advised to use an alternative like Grub to bootstrap their kernel so that they can concentrate on implementing the kernel itself rather than the plumbing. Why Grub? Because it is one of the bootloaders that implements the “Multiboot” specification (correctly?).

This specification details the steps that OS / bootloader developers need to follow in order to be compatible with (and usable by) each other. In very simple terms, multiboot compliant operating systems need to have a 48 byte structure called the Multiboot header (in its entirety), somewhere within the first 8192 bytes of the kernel image, longword aligned. on a 4K boundary. [Updated: 10/6/2005, 12:23 PM]. Actual details about the fields are documented in the Multiboot specification here.

Every other “roll your own OS” tutorial invariably talks about how you can make your kernel bootable by Grub. But all of these assume that you are using the GCC toolset. If you are from a windows background you are out of luck. The GCC toolset itself is not very difficult to learn, but I’m sure you’d feel more at home using the tools you’re familiar with for a long time. At least I do and that’s why I set out writing this post about how you can make grub boot your VC++ kernel.

Making a boot loader like Grub boot a custom kernel is easy (at least compared to the effort it takes to create a new boot loader). The kernel itself is only a binary in some file format (AOUT, ELF, PE etc.). For example the Windows kernel (%WINDRIVE%\Windows\System32\NTOSKRNL.EXE) uses the PE file format (Try dumpbin /ALL %WINDRIVE%\Windows\System32\NTOSKRNL.EXE) that is also used by user mode programs under windows. Similarly, the Linux kernel probably gets compiled into the ELF file format. Now, expecting a bootloader to “know” all executable file formats is probably not a good idea. The multiboot specification takes a different approach to load a kernel image onto RAM. It uses fields in the multiboot header to denote the parts of the kernel image that needs to be loaded. Grub “knows” how to load an ELF binary, not a PE. So we are going to give it “hints” in our multiboot header that will help it load the kernel image properly. Time for some code…

/* kernel.h */
#ifndef __kernel_h__
#define __kernel_h__

#define dd(x)                            \
        __asm _emit (x)       & 0xff     \
        __asm _emit     (x) >> 8  & 0xff \
        __asm _emit     (x) >> 16 & 0xff \
        __asm _emit     (x) >> 24 & 0xff

#define KERNEL_STACK               0x00103fff
#define KERNEL_START               0x00101000
#define KERNEL_LENGTH               0x0000200F

void main(unsigned long, unsigned long);

#endif

/* kernel.c */
#include "kernel.h"

__declspec(naked) void __multiboot_entry__(void)
{
          __asm {
          
          multiboot_header:
                    dd(0x1BADB002)               ; magic
                    dd(1 << 16)                    ; flags
                    dd(-(0x1BADB002 + (1 << 16)))     ; checksum
                    dd(0x00101000)               ; header_addr
                    dd(0x00101000)               ; load_addr
                    dd(0x0010200F)               ; load_end_addr
                    dd(0x0010200F)               ; bss_end_addr
                    dd(0x00101030)               ; entry_addr
                    dd(0x00000000)               ; mode_type
                    dd(0x00000000)               ; width
                    dd(0x00000000)               ; height
                    dd(0x00000000)               ; depth

          kernel_entry:
                    mov     esp,     KERNEL_STACK

                    xor     ecx,     ecx
                    push     ecx
                    popf

                    push     eax
                    push     ebx
                    call     main

                    jmp     $
          }
}

void main(unsigned long magic, unsigned long addr)
{
          char *string = "Hello World!", *ch;
          unsigned short *vidmem = (unsigned short *) 0xB8000;
          int i;

          for(ch = string, i = 0; *ch; ch++, i++)
                    vidmem[i] = (unsigned char) *ch | 0x0700;
}

The first field in the header is a magic number that the bootloader will use to locate the start of the multiboot header in the image. The second field denotes the features that the OS expects from the boot loader. To keep the code simple, I’ve ignored bits 0-15 (about which you can read in the multiboot specification). I’ve set bit 16 of this field. This means that the fields at offsets 8-24 in the Multiboot header are valid, and the boot loader should use them instead of the fields in the actual executable header to calculate where to load the OS image. This mechanism enables the bootloader load kernel images whose format is not understood “natively”.

Before examining what the fields at offsets 8-24 mean, let’s take a look at the PE file format.

A PE image starts with a couple of standard headers (DOS / PE / File / Optional). Following these is a set of headers called the section headers that contain information about the different sections in the image. (For a more verbose explanation of the PE file format read Matt Pietrek’s article) A section typically contains either code or data. The above kernel if compiled with the following switches

cl      /Gd
/Fokernel.obj
/Fm
/TC
/c
kernel.c

link     /safeseh:no
/filealign:0x1000
/BASE:0x100000
/MAP: kernel.map
/ENTRY:__multiboot_entry__ kernel.obj
/NODEFAULTLIB:LIBC
/SUBSYSTEM:CONSOLE
/OUT: kernel.exe

Produces a .EXE with two sections named .text and .data. Sections are aligned on a 4K boundary using the undocumented linker switch /filealign:0x1000.

Armed with this information about the PE file format, lets examine the fields at offset 8-24 in the multiboot header.

dd(0x1BADB002)               ; magic
dd(1 << 16)                    ; flags
dd(-(0x1BADB002 + (1 << 16)))     ; checksum
dd(0x00101000)               ; header_addr
dd(0x00101000)               ; load_addr
dd(0x0010200F)               ; load_end_addr
dd(0x0010200F)               ; bss_end_addr
dd(0x00101030)               ; entry_addr
dd(0x00000000)               ; mode_type
dd(0x00000000)               ; width
dd(0x00000000)               ; height
dd(0x00000000)               ; depth

The field at offset 8, Checksum, needs to be set to – (magic + flags). Grub loads the .text section of the kernel into physical address 0x100000 (1 MB) + Offset by default. The offset is specified indirectly using the header_addr and load_addr fields. According to the specification header_addr “Contains the address corresponding to the beginning of the Multiboot header”. IMHO, this is a bit confusing. What it really means is, if the image file is loaded at 0x100000, the physical address of the starting of the multiboot header is header_addr. The next field load_addr contains the physical address of the beginning of the .text section. (In our case both are the same because the multiboot header is the first 48 bytes of the .text section). The next field load_end_addr is used to determine how many bytes of the image file actually needs to be loaded. (Note that the .text and .data sections need to be successive in the image for this to work). In our case 0x102000 is where data section starts and it has a size of 0xF bytes and hence the value 0x10200F for load_end_addr. Grub, now knows it needs to load 0x10200F – 0x101000 bytes. The next field according to the multiboot specification, needs to be set to 0 if a bss section doesn’t exist. (As in our case). However Grub refuses to load the image if bss_end_addr is set to 0, so I set it to 0x10200F (same as the previous). The rest of the code is perhaps obvious and hence doesn’t deserve an explanation.

Our multiboot compliant PE kernel is now ready :)

Sunday, September 04, 2005

Thursday, August 11, 2005

(Incomplete) Rotor GC notes

  1. All threads running managed code are suspended (after bringing it to a “GC safe” place)
  2. One or more generations are condemned
  3. Liveliness trace is used to distinguish live from dead objects in
    - Gen 0 alone for ephemeral collection
    - Gen 0 + 1 for full collection
  4. If ephemeral collection (copying collection)
    1. Live ephemeral objects are promoted into the elder generation by copying
      1. Live objects are located using a recursive scan
        1. Elder generation and large-object heap are scanned first for references pointing into ephemeral generation. Such objects are marked as live (card table)
        2. The stack of each managed thread is traced to find roots (Interior pointers are also traced)
        3. Handle table is traced for references to objects in  the ephemeral generation
        4. Finalization queue is traced for references to objects in the ephemeral generation
      2. Live objects are copied into the elder generation
      3. References to copied objects are updated to reflect their new locations
  5. If full collection (ephemeral + mark and sweep collection (Gen 1))
    1. Ephemeral collection is done first
    2. Live objects in Gen 1 are traced
      1. Cross generational references (i.e. the Gen 0 objects that are pointed to by a Gen 1 object reference) are not visited because they already have their mark bit set (as a result of ephemeral collection)
        1. Stack references are traced
        2. Handle table references are traced
        3. Finalization queue is scanned for references to objects in Gen 1
    3. Sweep of the elder generation for dead objects
      1. Mark and pin bits of live objects are cleared
      2. Dead objects are linked together (if contiguous) into a free list *
      3. Brick table is cleared to reflect the disappearance of dead objects
  6. Weak reference fix up and building finalizer queue follow

* There is no compaction. Dead objects that lie next to each other are treated as one dead zone in the free list.