Chapter-2 : Dividing RAM [RexOS Dev]

Github Link: https://github.com/Arpit-Mohapatra007/RexOS-riscv

Moving further, after a successful boot, we need to divide our entire physical memory into usable, small chunks of 4 KB called “pages” so we can allocate them to processes in the future.

To achieve this feat, we need to find the absolute start and end of our RAM. We can fetch the start address from our earlier hard-coded memory layout, but we must dynamically determine the end of the RAM using the Device Tree Blob (DTB) parser we discussed in the previous article.

Let’s discuss how I crafted our DTB parser to determine the end of RAM, referred to as the Pool Horizon in our code.

Reference : https://devicetree-specification.readthedocs.io/en/stable/flattened-format.html#sect-fdt-strings-block

Before we dive into parsing the DTB, we need a handy tool to swap endianness. Due to historical reasons (dating back to PowerPC), the data stored inside a DTB is strictly mandated to be in Big-Endian format. However, our RISC-V CPU interprets data in Little-Endian format. If we don’t swap the bytes, our CPU will read a 128MB RAM size as a massive, corrupted 2GB size, causing absolute chaos.

To hunt for our required data in the tree, we first need its root pointer. This heavy lifting is done by QEMU, which acts as our direct bare-metal bootloader. Right before it hands over control, QEMU’s internal circuitry hardwires the current core’s ID into register a0, places the physical address of the generated DTB into register a1, and jumps straight to our _start code at 0x80000000.

We fetch this value from a1 and store it into a variable in the .data section.

Note: We can’t store it in the .bss section because our boot assembly loop literally zeroes that entire section out!

With the start point secured, I crafted an untidy-looking C function that parses through the DTB to fill my struct ram_meta with two crucial fields: ram_base_address and ram_total_size.

Here is the sequence of the parser:

1. I extracted the Header of this DTB in order to identify the exact offset of Structure Block ( off_dt_struct ) and offset of String Block ( off_dt_strings ). Struct Block-> describes the structure and contents of the devicetree itself. It is composed of a sequence of tokens with data. String Block-> contains strings representing all the property names used in the tree. These null terminated strings are simply concatenated together in this section, and referred to from the structure block by an offset into the strings block.
2. We loop through all the tokens present in Structure Block until we find a FDT_BEGIN_NODE (0x00000001) whose device name begins with “memory”.
3. If we find one, we mark it as we are now inside_memory. Then we look for FDT_PROP (0x00000003) and extract its two fields : the length of the property’s value in bytes and an offset into the strings block at which the property’s name is stored as a null-terminated string.
4. We run math and check if the name of property is “reg”, if so then we parse the property further in 4 Byte aligned slices and determine our both target properties, i.e. ram_base_address and ram_total_size by putting those bits together.

Initializing Allocation of Memory Blocks :

Now, as we know the true limits of our memory pool, we begin to draw lines in order to divide memory into purpose-specific chunks.

RAM Layout of RexOS

RAM Layout of RexOS:

1. Kernel Space (0x80000000 to _bss_end): This is the static footprint of our operating system. The moment the OS is compiled, this size is locked. It contains our compiled C instructions, hard-coded strings (like our RexOS banner), and the 8KB boot stack we set up in start.S.
2. Metadata (metadata_start to metadata_end): Because we calculated metadata_start right after _bss_end (rounded up to the nearest 4KB), this acts as the "accounting book" for our RAM. It contains the massive array of struct page objects, representing the status (free, allocated, order size) of every single 4KB block of RAM that exists in the system.
3. User Pool (free_pool_start to ram_end): This is the vast majority of our RAM stick. It starts strictly aligned to our largest buddy block size (MAX_ORDER). When our kernel calls kalloc(), or when a future user application asks for memory, this is the pool that gets carved up and handed out to them.

To allocate and free pages we use an established and widely used philosophy known as “Buddy Memory Allocator”.

What is a Buddy Memory Allocator ? — Every memory block in this system has an order, where the order is an integer ranging from 0 to a specified upper limit ( MAX_ORDER or 12 in our RexOS) .

THE BUDDY ALLOCATOR: POWER-OF-TWO BLOCK HIERARCHY

Order 3 │────────────────────────────── 32 KB ──────────────────────────────│
        │                                                                   │
Order 2 │────────────── 16 KB ─────────────│────────────── 16 KB ───────────│
        │                                  |                                │
Order 1 │────── 8 KB ──────│────── 8 KB ───│────── 8 KB ──────│─── 8 KB ─-──│
        │                  │               │                  │             │
Order 0 │─ 4 KB ─│─ 4 KB ─-│─ 4 KB ─│─ 4 KB│─ 4 KB ─│─ 4 KB ─-│─ 4 KB│ 4 KB │

           ▲          ▲
           └────--────┘
       These two 4KB blocks are "Unique Buddies". 
       They can only merge with each other to form the 8KB block above them.

The size of a block of order n is proportional to 2^n, so that the blocks are exactly twice the size of blocks that are one order lower. Power-of-two block sizes make address computation simple, because all buddies are aligned on memory address boundaries that are powers of two. When a larger block is split, it is divided into two smaller blocks, and each smaller block becomes a unique buddy to the other. A split block can only be merged with its unique buddy block, which then reforms the larger block they were split from.

Let’s first discuss the Memory Layout of struct page :

1. **order (Offset 0x00):* Tracks the block size magnitude. If order is 0, this page represents a 4KB block. If order is 2, it represents a 16KB block ( 2² 4 KB ).
2. **flag (Offset 0x04):** Tracks the allocation status. We are using 0 for free, 1 for allocated, and 2 for internal/split pages.
3. **next_idx & prev_idx (Offsets 0x08 and 0x10): **Instead of using expensive memory pointers, I chose to use index integers (unsigned long) to link free pages together in a doubly-linked list.
4. **alloc_caller (Offset 0x18): **It will help us during future debugging phases. When a page is allocated, we save [__builtin_return_address(0)](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html#Getting-the-Return-or-Frame-Address-of-a-Function) here to track exactly which C function requested the memory.

On our 64-bit architecture, this structure adds up to exactly 32 bytes with zero wasted memory padding, meaning it perfectly maximizes hardware cache efficiency!

So now, while initializing all pages which include pages from kernel space, metadata space and user space, we do the following :

We run a loop and force-filled all fields of all pages and pushed them to a Page Array which sits at the start of Metadata block in order to achieve uniformity and lock all pages in our Kernel space and Metadata space.

• order -> 0
• flag -> 2
• next_idx -> 0xFFFFFFFF ( just a marker chosen by me )
• prev_idx -> 0xFFFFFFFF
• alloc_caller -> 0 Why? Because the RAM right after our .bss section is completely uninitialized. It contains raw, random electromagnetic garbage left over from when the motherboard powered on. If we don't manually zero this out, future debugging tools will think pages were allocated by wild, phantom memory addresses!

Next, we want to set up Free Lists, just next to Page Array in memory.

Free lists are data structures used to manage available memory blocks of specific sizes. The system maintains multiple free lists, with one list dedicated to each permitted block size, which are typically powers of two.

To initialize our free lists we mark the start of all our free lists start as 0xFFFFFFFF.

After this, we need to unlock our user-space pages so we force-fill them with values and inter-connect them into a massive chunk and connect the header of the array to the free list for order MAX_ORDER-1.

• order -> MAX_ORDER-1
• flag -> 0
• next_idx -> free_lists[MAX_ORDER-1]
• prev_idx of previous page -> current page
• prev_idx of header page -> 0xFFFFFFFF

Now we are done with the initialization of Pages, our Page Array, and our Free Lists. Next, we need to write the logic that actually hands this memory out to user applications or kernel functions when they call kalloc(order) .

If a process asks for an Order 0 block (4 KB), but our free lists only have a massive Order 2 block (16 KB) available, we can’t just hand over the whole 16 KB chunk, that would waste 12 KB of RAM! We have to intelligently slice it.

Here is how our allocation engine handles the hunt:

1. We start by checking if the free_lists array has a block at the demanded order. If it is empty (0xFFFFFFFF), we climb up the ladder of orders until we find a list that contains an available block.
2. Once we find a block, we detach it from its current free list by updating the prev_idx and next_idx of the surrounding blocks.
3. If the block we found is a higher order than what we need, we enter a while (curr_order > demanded_order) loop. We split the block exactly in half. We hand over the left half to the caller. We take the right half (the newly born buddy), mark it as free, and demote it into the lower-order free list.

How do we calculate the exact index of that right-half buddy without searching through RAM? Using this elegant bitwise formula:

Buddy Index = Index + ( 1 << Current Order )

We lock the left block to flag = 1 (allocated), record our alloc_caller to trap bugs, calculate the physical RAM address, and hand it to the user.

Lets visually see when a user requests a 4 KB (Order 0) block, but the system only has a free 32 KB (Order 3) block available. The allocator splits the blocks recursively until it reaches the exact requested size.

ALLOCATION: REQUESTING A 4KB BLOCK (ORDER 0)

1. Initial State (One free 32 KB block in Order 3 list)
   ┌─────────────────────────────────────────────────────────────────────────┐
   │                              32 KB (FREE)                               │
   └─────────────────────────────────────────────────────────────────────────┘

2. Split 1: 32 KB splits into two 16 KB buddies. 
   (Left is kept for further splitting, Right goes to Order 2 free list)
   ┌───────────────────────────────────┬───────────────────────────────────┐
   │           16 KB (SPLIT)           │           16 KB (FREE)            │
   └───────────────────────────────────┴───────────────────────────────────┘

3. Split 2: The Left 16 KB splits into two 8 KB buddies.
   ┌─────────────────┬─────────────────┬───────────────────────────────────┐
   │  8 KB (SPLIT)   │   8 KB (FREE)   │           16 KB (FREE)            │
   └─────────────────┴─────────────────┴───────────────────────────────────┘

4. Split 3: The Left 8 KB splits into two 4 KB buddies. (Target Order Reached!)
   We hand the leftmost 4 KB to the caller and mark it as ALLOCATED.
   ┌────────┬────────┬─────────────────┬───────────────────────────────────┐
   │  4 KB  │  4 KB  │   8 KB (FREE)   │           16 KB (FREE)            │
   │(ALLOC) │ (FREE) │    (Order 1)    │             (Order 2)             │
   └────────┴────────┴─────────────────┴───────────────────────────────────┘

Allocating memory is easy; freeing it without fragmenting your RAM into a million unusable 4 KB pieces is the true engineering challenge.

When a process calls kfree(phys_addr), we first run a gauntlet of sanity checks:

• Is the address cleanly 4KB aligned?
• Is it inside our RAM bounds?
• Is it actually marked as allocated?

Once verified, we convert the physical address back into a page_array index. Now, the magic happens. We don't just mark the page as free, we actively hunt for its buddy to see if we can merge them back into a larger block. We enter a while loop to climb back up the order ladder.

Here is how we free allocated pages:

1. To find the exact index of our buddy, we don’t need memory pointers. We use the bitwise XOR operator

Buddy Index = Index ^ ( 1 << Order )

Why does this work? Because in a power-of-two allocator, two memory buddies are mathematically identical in their binary index, differing by exactly one single bit (the bit representing their order size). XORing that specific bit flips it, instantly revealing the exact index of the buddy in a fraction of a microsecond.

2. If the buddy is indeed free, we detach it from its free list. Now we have two free blocks (Left and Right) that need to combine into one larger block. But which index becomes the new “head” of this merged block? It must always be the Left (base) index. We enforce this using this mathematical formula :

Merged Base Index = Index & Buddy Index

or

Merged Index = Index & ~ ( 1 << Order )

We increment our order, mark the buddy as flag = 2 (internal/consumed), and let the while loop run again. This cascade continues merging 4KB into 8KB, 8KB into 16KB , until it hits an allocated buddy. Finally, we attach the newly formed massive block back to its rightful free list.

Lets visually see when the user calls kfree() on that 4 KB block, the allocator uses bitwise XOR to find the buddy, checks if it is free, and recursively merges them back up the ladder.

FREEING & MERGING: HEALING THE RAM

1. Initial State (User finishes program, calls kfree on the 4 KB block)
   ┌────────┬────────┬─────────────────┬───────────────────────────────────┐
   │  4 KB  │  4 KB  │   8 KB (FREE)   │           16 KB (FREE)            │
   │(ALLOC) │ (FREE) │                 │                                   │
   └────────┴────────┴─────────────────┴───────────────────────────────────┘

2. Step 1: 4 KB is freed. Allocator XORs the index, finds its 4 KB buddy 
   is also FREE, and merges them into an 8 KB block.
   ┌─────────────────┬─────────────────┬───────────────────────────────────┐
   │  8 KB (MERGED)  │   8 KB (FREE)   │           16 KB (FREE)            │
   │     (FREE)      │                 │                                   │
   └─────────────────┴─────────────────┴───────────────────────────────────┘

3. Step 2: Allocator climbs the ladder. XORs the 8 KB index, finds its 8 KB 
   buddy is also FREE, and merges them into a 16 KB block.
   ┌───────────────────────────────────┬───────────────────────────────────┐
   │          16 KB (MERGED)           │           16 KB (FREE)            │
   │              (FREE)               │                                   │
   └───────────────────────────────────┴───────────────────────────────────┘

4. Step 3: Allocator climbs again. XORs the 16 KB index, finds its 16 KB 
   buddy is also FREE. Merges them back into the massive 32 KB block!
   ┌─────────────────────────────────────────────────────────────────────────┐
   │                   32 KB (FULLY RESTORED & FREE)                         │
   └─────────────────────────────────────────────────────────────────────────┘

   *Zero fragmentation. The RAM has completely healed itself!*

Problems I faced during this :

1. I was stuck for hours trying to understand the magical bit manipulation happening, it was something I’d never witnessed before. It was elegant !
2. I had a long battle understanding why struct type *name and struct type name declarations are different, and why the -> method and . method of accessing fields are strictly separated in C.

• I realized that when we declare a struct using struct type name, we literally create a physical box of that exact size in memory, so we access its fields using .
• But when we declare struct type *name, the name is not the struct itself, it is just a lightweight label (a pointer) that points to the memory box. Hence, we must use -> to "shoot an arrow" over to the box and access its fields.