Operating System Development: Memory Map

It has been a while since there we any updates to this, the in-depth guide to toy operating system development! But oh well, what’s thirteen years between friends? When last we were here, we had built first and second-stage boot loaders, and a kernel that said “Hello world”, then hung. It’s high time to move on.

In this section, we’ll be looking at the system’s memory map. As we’ll soon need to write memory management (to be done by our brand new kernel), we’ll need to know which areas of memory we can touch, and which are off-limits. Overwriting the kernel itself, for example, would be bad, and overwriting the global interrupt table would bring the system down, as well.

This article is part of a series on toy operating system development.

View the series index

After we hit protected mode, all memory of the system becomes available to our kernel: vast fields of bytes, ready to be written, read, shifted, or fondled in other ways. But not all memory is equal! Some memory can’t be written to (ROM), and it’d be bad if we tried. Other memory is directly mapped to devices: the VGA card, for example, is tied to a specific area of memory. But there’s more: our kernel doesn’t even know how much memory our system has. It literally can’t see the end of those vast fields of bytes.

Which areas of memory are actually not available to us is something that varies from machine to machine. A different graphics card would use a different area of memory (CGA cards where at 0xB800, VGA at 0xA000). Our kernel doesn’t know these things - but the BIOS knows. The BIOS has a special interrupt that gets us a nice memory map: a list of sections, each marked as usable or reserved.

There’s but one catch: this is a BIOS interrupt, so it has to be called from real mode. This means we must call it before we ever go into protected mode, and so the code that we write in this article must be inserted into our second-stage bootloader. While that’s not a problem, we must also find a way to pass the memory map we obtain to the kernel, which will make use of it. This means we must place the map somewhere in memory - temporarily - and let the kernel find it there.

The interrupt

The interrupt that’ll get us our memory map is int 0x15, subfunction 0xe820. It’s documented here and here

The input is:

And the call will return:

The Address Range Descriptior that the BIOS will place at es:di looks like this:

… where “type” can be one of:

A “reserved” area of memory could be ROM, RAM in use by ROM, or memory mapped to a system device.

ACPI 3.0

In 2004, the Advanced Configuration and Power Interface specification (ACPI) added (among other things) a change to the memory map interrupt: rather than returning 20 bytes, it would now return 24 bytes. The last 32 bits have the following meaning:

A proper kernel will have to take these ACPI improvements into account, but also deal with older BIOSes that don’t carry them. More ifs and thens, therefore.

Getting the map - a recipe

Right, so there’s one interrupt, which we need to call repeatedly, until the return value indicates that there are no more ~lands to conquer~ memory runs to be found. We also need to take a potential ACPI extension into account. Note that the OSDev wiki’s page for memory detection discusses still other interrupts that might be used to detect memory, but interrupt 0x15/E820 is 99% of the process - since we’re not currently trying to build the new Linux, we’ll stick with it.

Our steps therefore:

• Select an area of memory where the memory map must be stored as it comes in from the interrupt. We must be careful not to overwrite other things. However, this is temporary: once the kernel is booted, it’ll move the memory map to a different, more suitable location.
• Call the interrupt
• Check the interrupt’s return value:
  • If the buffer > 20 bytes, then there is ACPI data. If not, assume the ACPI value for a usable memory run.
  • If the buffer is 0 bytes, the call returned no run and we continue.
  • If the Address Range Descriptior has a length of 0, then the BIOS reported a zero-byte run of memory. We’ll ignore it and continue.
• Advance the pointer where the interrupt stores descriptors.
• If a continuation value is present, do it all again.

Memory structure

We’re collecting our list of physical memory runs in the second-stage boot loader. This information has yet to make it to the kernel, which at this point hasn’t booted yet. We must therefore create a contract between the bootloader and the kernel: a precise definition of what the bootloader will place in memory, and where. In addition to the address range descriptors themselves, we’ll also want to tell the kernel how many descriptors were found. Let’s also stick a magic value on top, just to the kernel can verify that the memory map arrived to it unmolested.

In C terms, this’ll look like this:

struct bootinfo
{
  uint32_t magic;           // BOOTINFO_MAGIC
  uint32_t e820_count;      // zero means the BIOS returned nothing
  uint32_t e820_addr;       // -> struct e820_entry[e820_count]
  uint32_t boot_drive;      // what the BIOS put in dl at 0x7C00
} __attribute__((packed));
struct e820_entry
{
  uint32_t base_low,   base_high;
  uint32_t length_low, length_high;
  uint32_t type;
  uint32_t attrs;
} __attribute__((packed));

As for where to store this information… here is a list of what we’ve got going in memory up to the point that we start the kernel:

A diverse collection of things, but it’s important to note that virtually all of it is important only to the second-stage bootloader. It loaded an IDT and GDT just to be able to switch to protected mode. It has its own stack, we have the boot sector floating around as loaded by the BIOS, the FAT table, and the second stage’s own code. All of this can disappear as soon as the kernel runs, and the memory it occupies can be released.

I’ve picked 0x8000 to place the bootinfo structure, for the simple reason that it is free. The kernel will know where to pick it up, and then move it to somewhere more sensible - plenty of options, since just about everything else will disappear. The kernel will create its own IDT and GDT, and store them where it wants.

Calling the BIOS

Let’s actually call the BIOS then, and get down to assembly code. We’ll define a few things:

BOOTINFO_ADDR  = 0x8000        # 32 bytes (only 16 used)
E820_ADDR      = 0x8020        # memory map
# 32 entries of 24 bytes = 768 bytes, ending at 0x8320. It's not likely that
# real machines will have more entries, but the kernel will warn if that
# happens.
E820_MAX       = 32 # entry count
E820_ENTRY_SZ  = 24 # entry size
SMAP           = 0x534D4150    # 'SMAP'; magic signature that the BIOS returns
                               # to report the call went well.
# A little safety check. The pointer we pass to the kernel is used much later,
# so this helps us check that information wasn't clobbered anywhere.
BOOTINFO_MAGIC = 0xB007B007

These are all values we’ve gone over above, defined as constants for readability further on. Neat!

The call to the BIOS, then is done in a loop, since we must retrieve multiple runs of memory until the BIOS says that there are no more. We’ll do a quick setup:

xor   ax, ax                       # ax=0
mov   es, ax                       # es:di is then a linear address
mov   di, E820_ADDR                # es:di points to the memory map we'll build
xor   ebx, ebx                     # ebx=0: first call, not a continuation
xor   si, si                       # si=0: 0 entries stored so far
                                   #   (not part of interrupt call)

Now for the loop:

detect_memory__loop:
  mov   eax, 0xE820                  # Interrupt subfunction
  mov   edx, SMAP                    # magic code 
  mov   ecx, E820_ENTRY_SZ           # ask for 24 bytes: 20 of range, plus the
                                     # ACPI 3.0 attribute word
  int   0x15

Carry flag means end-of-list, or that E820 is not supported. We stop:

  jc    detect_memory__finished

Let’s check that the magic code (“SMAP”) is present on the response. Otherwise we give up:

  cmp   eax, SMAP                    # the BIOS must echo 'SMAP' back
  jne   detect_memory__finished      # If no 'SMAP', then done.

If the buffer size is 0, it’s not a valid run of memory so we skip it:

  test  ecx, ecx                     # cx = 0?
  jz    detect_memory__next          # skip

A little special treatment for ACPI 3.0. We’ve asked for 24 bytes to be returned; if the BIOS returns only 20, then there’s no ACPI extension. In that case we just pad the entry to 24 bytes and consider it “in use”.

  cmp   ecx, 20
  jne   detect_memory__have_attrs
  mov   es:[di+20], dword ptr 1      # A word value of 0x0001: memory in use.
detect_memory__have_attrs:

The BIOS may return memory runs of length 0. While these are valid, they are not useful to us and we skip them:

  # Zero-length regions may be returned but we don't want them. Skip.
  mov   eax, es:[di+8]               # length, low half
  or    eax, es:[di+12]              # ... or high half
  jz    detect_memory__next          # skip if eax=0

We come to the end of the loop. We keep track of how many runs we’ve found so far, and if there’s a continuation value, we jump to the loop again. Otherwise, we are done:

  inc   si                           # +1 areas found
  add   di, E820_ENTRY_SZ            # Move to next position in memory map
detect_memory__next:
  test  ebx, ebx                     # Continuation value of 0: last entry
  jz    detect_memory__finished      # so we are done.
  cmp   si, E820_MAX                 # out of room; the kernel will warn
  jb    detect_memory__loop          # LOOP AGAIN if there's room

At this point, we end up with the memory map in memory at our desired address, i.e. 0x8020. We’ll now prepend the boot information at 0x8000.

  movzx ebx, byte ptr iBootDrive
  xor   cx, cx
  mov   es, cx
  mov   di, BOOTINFO_ADDR                      # es:di=0:BOOTINFO_ADDR
  mov   es:[di],    dword ptr BOOTINFO_MAGIC
  movzx ecx, ax
  mov   es:[di+4],  ecx                        # e820_count
  mov   es:[di+8],  dword ptr E820_ADDR        # e820_addr
  mov   es:[di+12], ebx                        # boot_drive

… and that is that: the full structure is now sitting at 0x8000.

Handing over to the kernel

The structure’s ready, but we’re not quite done yet: the kernel has no idea that the boot info structure exists, much less where it is. This is easy to remedy: the kernel code simply reads the memory at 0x8000, and consults the memory map there. That’s not a very robust approach though: if we ever change the code to place the memory map somewhere else, the both the bootloader and the kernel must be updated. It’s prettier to pass a pointer to the kernel, so that the structure placement is entirely the bootloader’s decision.

.macro mJumpToKernel bootinfo
  mov ebx, \bootinfo
  jmp 0x08:0x20000
.endm

This give the kernel an additional responsibility though: it must not change the ebx register until the pointer is used. When the time comes to jump to C code, we simply push ebx onto the stack and call:

  push   ebx
  call   kernel_main

and the kernel’s C entry point looks like this:

void kernel_main(struct bootinfo *bi)

When making changes to the bootloader and the kernel’s assembly entry point, it’s easy to mess up this fragile way of handing the kernel a pointer. We may inadvertently change the pointer value, or overwrite the memory it points to, and it’d be difficult to debug when that happens. For this reason, and extra bonus points, we place a magic value at the boot info structure’s address, just before the actual boot info - then check it later:

if (handed_over == 0 || handed_over->magic != BOOTINFO_MAGIC) {
  kprintf("bootinfo: BAD MAGIC at %p - no memory map\n", (uint32_t)handed_over);
  return 0;
}

Getting the information into the kernel

At this point, our boot info structure lives at address 0x8000, and continues to be there as we load the kernel into memory, set up the IDT, GDT, and jump to protected mode, finally long-jumping to the kernel’s C code.

Before doing anything else in the kernel, we need to “adopt” the boot info structure, moving it into memory the kernel owns. We do this by copying the data into the kernel’s .bss section, which is the section for uninitialized variables. With that done, the data is safe. We can then mark the area at 0x8000 as “available”!

Summary

Somewhere down the line, we’ll want our kernel to manage the system’s memory, handing it out to processes as they start, and checking that those processes aren’t naughty and try to write beyond their allocated memory. Before we’re in a position to do so, however, the first thing to do is to create a map of the existing physical memory: how much of it is there, and which parts are reserved? Some of the memory is ROM, other memory is mapped to physical devices, yet other memory might be faulty. The BIOS can provide us with this information, so it is important we call it while we’re still in real mode - in protected mode, we can’t talk to the BIOS anymore.

In this section, we show how to call BIOS interrupt 0x15/E820 repeatedly to populate a physical memory map (in real mode). After we jump to protected mode, we then have the kernel move it to an area of its choosing, finally freeing up all the memory that was used by the second-stage boot loader, boot sector, and FAT tables.

Continue on to the next part of this guide!