Contents

  1. Learning Objectives
  2. Overview
  3. Pages
  4. Page Allocator
  5. Memory Byte Alignment
  6. Bookkeeping
  7. Initializing
  8. Allocating a Page
  9. Deallocating (freeing) a Page
  10. No-waste Page Allocator

Learning Objectives

  • Understand what a memory pool is and how to manage it.
  • Understand what aligning a memory address means.
  • Be able to import linker-script symbols into a higher-level language.
  • Be able to align a memory address to a given power of 2.
  • Understand what bookkeeping is used for when allocating and deallocating pages.
  • Be able to initialize a memory pool.
  • Be able to implement a page-grained allocator.
  • Understand why we might want to zero (clear) all newly allocated pages.
  • Be able to implement a page-grained deallocator.

Overview

The operating system is managing just a pool of memory. For the first time in a long time, we’re actually managing physical memory. Our linker script will provide us two symbols, _heap_start and _heap_end to give us the heap range.

Importing these symbols into C is a little bit of a challenge. The issue is that the memory address of the symbol is the value of the symbol. So, the symbols do not actually have a value, but the memory address that our high level language thinks it is in is the actual value we’re looking for. This is a bit of a mind bender, but if we’re careful and add utilities, we can set it and forget it.

// symbols.h
#pragma once
extern void *_heap_start;
extern void *_heap_end;
extern void *_stack_start;
extern void *_stack_end;
extern void *_bss_start;
extern void *_bss_end;
extern void *_data_start;
extern void *_data_end;
extern void *_text_start;
extern void *_text_end;
extern void *_rodata_start;
extern void *_rodata_end;
extern void *_memory_start;
extern void *_memory_end;

#define sym_start(segment) \
    ((unsigned long)&_##segment##_start)

#define sym_end(segment) \
    ((unsigned long)&_##segment##_end)

I made two macros that allow you to substitute the segment. The segment can be one of the following: heap, stack, bss, data, text, rodata, or memory.

printf("MEMORY SECTION MAPPING\n");
printf("~~~~~~~~~~~~~~~~~~~~~~\n");
printf(" ...%-8s: 0x%08lx - 0x%08lx\n", "memory", sym_start(memory), sym_end(memory));
printf(" ...%-8s: 0x%08lx - 0x%08lx\n", "text", sym_start(text), sym_end(text));
printf(" ...%-8s: 0x%08lx - 0x%08lx\n", "rodata", sym_start(rodata), sym_end(rodata));
printf(" ...%-8s: 0x%08lx - 0x%08lx\n", "data", sym_start(data), sym_end(data));
printf(" ...%-8s: 0x%08lx - 0x%08lx\n", "bss", sym_start(bss), sym_end(bss));

Dynamic memory is going to be important for us since our environment itself will be dynamic. We don’t know how many processes we need, we don’t know how many buffers we need, and we will need to preserve data across context switches and system calls. Really, the only way to keep track of all of this is through dynamic memory.

The operating system itself is quite asynchronous. It is kind of weird to have your program “terminate”, but yet have an entry point through a trap vector. This will be the biggest shift in your thinking that you’ll need to make when writing an operating system.

Pages

I would usually let you bump into problems and let you refactor line after line of code, but in this case, I’ll spare you the misery. When we start using the memory management unit (MMU), we will need to access a granularity at the page level. The MMU cannot protect memory that is higher in resolution than this.

The RISC-V MMU we will be using is the SV39 mode. SV39 gives us 39-bit virtual addresses which translate into 56-bit physical addresses. At most, there are three level of page tables that we will need to address. These levels can give us a gigabyte page (leaf at level 2), a 2 megabyte page (leaf at level 1), and a 4 kilobyte page (leaf at level 0). Generally, we want to stick with the 4Kb pages to avoid wasting too much memory.

Page Allocator

Allocating pages and allocating bytes will be handled in two different ways. A page-grained allocator is much simpler because we know around the size we will be giving out, and we know for sure the size will be a multiple of 4Kb (or whatever the page size). However, with the byte-grained allocator, this will not be the case, so we will need to use a different technique.

Memory layout for page-grained allocator

The page-grained allocator will manage two sections: (1) the bookkeeping area, and (2) the individual pages.

The bookkeeping area will be necessary to keep track of how many pages are allocated and how many pages are free. We also need to keep track of an allocation of pages. This allows us to allocate contiguous pages, which will prove useful when dealing with I/O, which deals in physical memory, not virtual.

Memory Byte Alignment

The MMU’s resolution is at the 4Kb level. This means that any memory address we hand out, the last 3 hex digits must be 0. The reason is because 1 hex digit is 4 bits, and \(2^{12}=4,096\).

This means that the very first 4Kb chunk in our allocation area must be aligned to the next 4Kb address. In other words, the memory address of our first chunk must be an exact multiple of 4,096 (4Kb).

To do this, we need to check our alignment. If it is off, we need to pad out the bytes, essentially waste them, to make sure our chunk starts at a memory address which is a multiple of 4,096.

Alignment is fairly straight-forward. What we can do is make the last three hex digits of our memory address all 0. However, that could be the tail end of our bookkeeping bytes. So, instead, we add 4,095 to the next available memory address where the first chunk can start. We do \(4,096-1\) because if we naturally fall on a memory address that is a multiple of 4,096, we don’t want to waste a chunk. After we add 4,095, we can then strip off the last 12 bits of our memory address. This process is called aligning to 4,096. Yes, space is wasted, but there is nothing we can do due to the limitations of the MMU.

Bookkeeping

Recall that our bookkeeping area will need to keep track of how many pages we have allocated and allow for a contiguous allocation of pages. In this case, we can use a 2-bit integer for each page. This means that every 4,096 bytes of our memory is going to require 2-bits of bookkeeping. This isn’t a bad ratio, and it will make our lives easier.

The two bits will be as follows:

If the page has been allocated, the taken bit will be set to 1. If the page has not been allocated, the taken bit will be set to 0. This gives us the ability to track allocated pages. The last bit will be set to 0 if there are more contiguous allocations. The very last allocation in a long string of allocations will have the last bit set to 1. Take the following for example.

In the example above, we have a three page allocation. So, all three pages will have the associated bookkeeping taken bits set to 1. However, since we’ve allocated three contiguous pages, we mark the end of the chain of pages by setting the third page’s last bit to 1.

In this case, we can keep freeing allocations until we see the last bit set to 1. If we come across a non-taken (taken = 0) before we see last = 1, this is an error condition and could mark a problem, such as a double free, where we tried to free the memory twice.

We can further make optimizations to our page allocator, for example, since we have 2 bits per page, we can fit 4 pages into one byte of bookkeeping. It doesn’t matter where we locate the bookkeeping bytes (start or end), but the important part is to keep track of how to map the bookkeeping bits to the page.

Initializing

Before we can allocate pages, we need to initialize the memory in the bookkeeping area.

Since we must consider the bookkeeping area uninitialized, it may contain garbage values, which might set taken bits to 1 or last bits to 1 seemingly randomly. Therefore, it is imperative that we initialize the page pool by setting all taken bits to 0 and all last bits to 0.

The math works out that we have 4 pages per byte of bookkeeping (2 bits per page, 8 bits per byte, \(\frac{8~\text{bits-per-byte}}{2~\text{bits-per-page}} = \frac{8~\text{bits}}{1~\text{byte}}\times~\frac{1~\text{page}}{2~\text{bits}}=4~\text{pages-per-byte}\)). This will give you how many bits you need to set to 0 during initialization.

Allocating a Page

Our allocator will need to take one parameter, num_pages, which is the number of contiguous pages we need. So, to allocate we need to do the following.

  1. Search through the bookkeeping bytes for the first non-taken (taken = 0). Mark this point as start.
  2. Check the next page’s bookkeeping bytes and see if (taken = 0)
  3. If taken = 0, go to step 2 and repeat for num_pages times.
  4. If taken = 1, go back to step 1 with the next page as your starting point.
  5. If you’ve found num_pages of contiguous free pages, mark all of the pages as taken (taken = 1), and set the last page (last = 1).
  6. Take which bookkeeping page is the start of the allocation. Scale this value by 4,096. Add this value to the memory address of the very first 4Kb chunk.
  7. Test this value for alignment. If it is not a multiple of 4,096, the math got messed up.
  8. Return this memory address as your page.

You need to give the option to zero this memory. Many times we will share these pages amongst the operating system, the user processes, and so forth. We don’t want to leak privileged data by leaving data that was stored in one of our pages. So, setting all 4,096 bytes to 0 is probably a good idea, however it is slow. So, having two functions, one that zeros, and one that doesn’t will be useful when allocating pages to your operating system.

void *page_zalloc(void)
{
    return zero_4k_page(page_alloc());
}

As a side note, zeroing a 4k page needs to be written in such a way where it is efficient to zero large pages. We can copy byte-by-byte for smaller data structures, but pages can get quite large, especially at the 2-megabyte or 1-gigabyte page levels. Therefore, we need to be able to zero quickly, otherwise our loop might get bogged down copying one zero after another for each byte in a page.

enum PageSize {
    PS_4K = 1 << 12,
    PS_2M = 1 << 21,
    PS_1G = 1 << 30
};
void *zero_page(void *page, enum PageSize size)
{
    if (page == NULL)
        return NULL;

    for (int i = 0; i < (int)size; i += 8) {
        *((unsigned long *)((char*)page + i)) = 0;
    }
    return page;
}

If we use the optimizer, the for loop above can be unrolled easily. We also take the largest data size we can, which is 8 bytes for a 64-bit machine. Returning the pointer back is just a convenience so that we can allocate, zero, and return the pointer all in one line.

Deallocating a Page

Deallocating is slightly easier than allocating since we don’t need to search. Instead, the memory address of the page will tell us the starting point exactly.

The following steps will deallocate a page.

  1. Subtract the memory address of the very first 4Kb chunk from the given memory address of the page. This will leave you with a scaled value.
  2. Divide the scaled value by 4,096. This will give you the index where the bookkeeping bits will be located.
  3. Since there are two bookkeeping bits per page, multiply the index by 2.
  4. Iterate through this multiplied index setting all taken bits to 0. Look for the last = 1 bit. When you reach it, set both taken = 0 and last = 0, and you’re done. If you reach a taken = 0 before you reach a last = 1, that could mark corruption.

No-waste Page Allocator

The allocator above gives us the most flexibility by allowing our operating system to allocate contiguous pages. However, for an MMU equipped system, the need for contiguous pages is significantly reduced. Generally, we will only need contiguous pages for DMA (direct memory access), but we will use that infrequently for our operating system.

We can use a no-waste page allocator by creating a linked-list allocator. This will actually be easier than the byte-grained allocator because we will never need to coalesce pages.

So, we have a global data structure that stores the head. It doesn’t actually store anything but the next pointer. This head points to the very first free page. Since we’re handing out pages, these pages don’t need to be sequential. Each page entry has an Option<> where if another page follows, it is given Some, and if there are no more pages to allocate, it is given None.

One issue with this is that we have to allocate one page at a time. This isn’t that big of a deal, since we can use a for loop to allocate multiple pages. However, we cannot guarantee that the pages are sequential. However, with a memory management unit, we don’t really care.

struct Page {
    struct Page *next;
} *page_head;

void init_kernel_paging(void)
{
    unsigned long addr;
    struct Page *p = (struct Page *)sym_start(heap);
    for (addr = sym_start(heap) + 4096; addr < sym_end(heap); addr += 4096) {
        p->next = (struct Page *)addr;
        p = p->next;
    }
    p->next = NULL;
    page_head = (struct Page *)sym_start(heap);
}

Now that we initialized the pages by adding free page after free page to the linked list, we can allocate by simply pulling the top of the linked list and resetting the pointers. The sym_start and sym_end macros are explained above.

void *page_alloc(void)
{
    struct Page *ret = page_head;
    if (ret == NULL) {
        return NULL;
    }
    page_head = page_head->next;
    return ret;
}

Finally, we can deallocate by adding the page to the free list. This does have the problem that double frees may cause the same page being allocated twice.

void page_dealloc(void *addr)
{
    struct Page *p = page_head;
    page_head = (struct Page *)addr;
    page_head->next = p;
}

Contiguous Physical Pages

There are some occasions that require contiguous physical pages, meaning that the physical memory addresses are in consecutive order. These types of pages are used when mapping hardware registers to memory. This cannot be guaranteed with the no-waste allocator, except right after boot time. So, it is recommended to allocate a chunk of consecutive pages when the operating system first boots.

We can make virtual pages contiguous by simply setting the virtual address, but contiguous physical addresses require some pre-planning.