A physical memory allocator is a component of an operating system responsible for managing the system's physical memory (RAM). Its primary role is to allocate and deallocate blocks of physical memory (often referred to as “pages”) to various system processes, kernel tasks, or other system components that need memory.

Key Concepts

• Physical Memory: This refers to the actual hardware memory (RAM) installed in the system. The OS interacts with this memory directly, allocating blocks for various tasks.
• Page: In modern systems, memory is typically divided into fixed-size blocks called pages. The most common page size is 4 KB (4096 bytes). The physical memory allocator manages these pages.
• Allocation: When a process or a part of the kernel requires memory, the allocator assigns one or more free pages of physical memory.
• Deallocation: When the memory is no longer needed (e.g., when a process exits or a buffer is freed), the allocator releases the allocated pages, marking them as free so they can be reused.

Responsibilities of a Physical Memory Allocator

1. Tracking Free and Used Memory: The allocator must keep track of which portions of physical memory are in use and which are free. This is often done using data structures like:
   • Bitmap: A data structure where each bit represents a page. A bit is 1 if the page is used, and 0 if it is free.
   • Free List: A linked list of free memory regions or pages.
2. Allocating Memory: The allocator should provide an efficient mechanism to find and allocate free memory pages. This could mean finding the first available page (first fit), or finding the smallest block that fits the requested size (best fit).
3. Deallocating (Freeing) Memory: Once a process no longer needs the memory, the allocator frees the pages, making them available for other uses.
4. Handling Reserved or Special Memory Regions: Certain parts of physical memory are reserved or cannot be allocated to user processes (e.g., memory reserved for the kernel, BIOS, or device memory). The allocator should respect these regions and not allocate them.
5. Fragmentation Management: The allocator should try to minimize fragmentation (when small, unusable gaps of free memory appear between allocated blocks). Fragmentation can waste memory and reduce system performance.

Physical Memory Allocator

For any memory allocator, two fundamental components are essential:

• Memory Region: A defined area of memory that can be allocated or deallocated.
• Status Indicator: A mechanism to determine whether a given portion of memory is free or occupied.

There are several ways to implement a status indicator for tracking the allocation status of memory in a memory allocator. Here are some common approaches:

1 Bitmap:

• Description: A bitmap is an array of bits where each bits represents a fixed-size block of memory (e.g., a page). A bit set to 1 indicates that the corresponding block is allocated, while a bit set to 0 indicates that it is free.
• Advantages:
  • Fast allocation and deallocation operations due to direct bit manipulation.
  • Compact representation of memory status.
• Disadvantages:
  • Requires contiguous memory for the bitmap.
  • Can lead to fragmentation if small allocations are made frequently.

2 Free List:

• Description: A free list is a linked list that maintains pointers to free memory blocks. Each free block typically contains a pointer to the next free block.
• Advantages:
  • Dynamic size that can grow or shrink as needed, allowing for flexible memory management.
  • Reduces fragmentation by grouping free blocks together.
• Disadvantages:
  • Overhead of maintaining pointers.
  • Slower allocation and deallocation compared to bitmaps due to traversal of the list.

3Buddy Allocation:

• Description: This method divides memory into blocks of sizes that are powers of two. When a block is allocated, the allocator searches for the smallest block that can satisfy the request and may split larger blocks into smaller "buddies."
• Advantages:
  • Reduces fragmentation by merging adjacent free blocks.
  • Faster allocation and deallocation compared to free lists due to predictable block sizes.
• Disadvantages:
  • Can lead to internal fragmentation if allocated memory is significantly less than the block size.
  • Requires careful management of buddy pairs.

4 Segregated Free Lists:

• Description: Multiple free lists are maintained for different block sizes. Allocations are serviced from the appropriate list based on the requested size.
• Advantages:
  • Efficient allocation for different sizes, reducing fragmentation.
  • Fast allocation and deallocation as each list targets a specific size.
• Disadvantages:
  • Increased complexity in managing multiple lists.
  • Potential for wasted space if there are many small allocations.

5 Allocation Counters:

• Description: Keep track of the number of allocated and free blocks using counters. This method can be used alongside other methods like bitmaps or free lists.
• Advantages:
  • Easy to implement and maintain.
  • Useful for monitoring memory usage.
• Disadvantages:
  • Does not directly represent the status of individual blocks, limiting its utility for allocation.

6 Hybrid Approaches:

• Description: Combine different techniques (e.g., a bitmap for tracking allocation status alongside a free list for free blocks) to leverage the advantages of each method.
• Advantages:
  • Can optimize performance and reduce fragmentation.
  • Flexible and adaptable to different allocation patterns.
• Disadvantages:
  • Increased complexity in implementation and management.

We will use the Bitmap method for the status indicator.

Idea:

1 Memory Map:

During the stage2 memory initialization, you might recall we loaded the memory map into a known location in the memory. We did that so that physical allocator can access it later.

During that process:

• We loaded the memory map returned by the BIOS E820 function at a known location which is:

  %define MEMLOCATION_MEMORY_MAP 0x9000

  The E820 function of bios returns the memory layout of a system on subsequent calls.

• We do count the returned regions as well such that while looping we get to know how much memory regions to loop through.
• We get the low and high memory size through the E801 bios function. We get the system's total available memory by just adding the low and high memory.

2 Get the pages count:

We will divide the whole memory regions into pages. A single page would be of 4086 bytes (4 KB) in size.

We can calculate the pages count by just dividing the whole available memory by the page size.

pages count = available memory / PAGE_SIZE

3 Dedicate a location for the Bitmap:

We would store the Bitmap as the status indicator for free or allocated memory.

That dedicated region would be the 0x300000.

4 Calculate the size for the Bitmap:

The bitmap size would be the large enough to hold a bit for the total pages.

Since we already calculated the pages count in step 2. 

If the pages count is 100 that means we would need 100 bits for the all pages for the status indicator.

Which is equivalent to 100/8 in bytes. 

Thus we can say that we would need pages count/ 8 bytes for the bitmap.

5 Initialize the Bitmap to Indicate all pages to be allocated:

Initialize the bitmap to indicate that all pages are allocated by setting all bits to 1. We will do so using the memset function.

6 For every memory map (regions) which we determined in step 1.

If type of that memory region is 1, which means that memory region is available to use. Every memory region have start address base and size of the region.

• Calculate the Frame by: Base / PAGE_SIZE
• Count the number of frames for this region: Size / PAGE_SIZE
• Until Count is not zero, do:
  • Unset the Bitmap for this page
  • Decrement the blocks used

Complete Code:

1 Loading Memory Map:

In the stage2 we have already loaded the memory region to a known location which is 0x9000. So we don't cover this part here. Below is the things which did during that process:

• Store the memory map loading location into the BootHeader data structure.
• Load the memory map to the 0x9000 location by using bios function E820 by using subsequent calls, and even count the memory map regions as well, store that in the BootHeader as the Memory Map Length.
  • We have loaded the returned memory map region to that location so that to be used later on by the kernel.
• Obtain the total available low and high memory in the system. Store those as well in the BootHeader as Memory Low and Memory High.

2 Calculate Total Memory Size & Blocks

Since we already determined the amount of the low and high memory in the stage2 while loading the memory map in step 1 and even we stored that in the boot descriptor which is passed from the stage 2 to the kernel. So we have the low and high memory amount.

• The low memory is in bytes ranging from 0 to 16 MB.
  • It is already in Bytes.
• The high memory is in 64 KB blocks in range from 16 MB to the highest available.

  • It is in 64 KB blocks and needs conversion to bytes.

    /* Get information from multiboot struct 
    	 * The memory-high part is 64kb blocks 
    	 * whereas the memory-low part is bytes of memory
    */
    	MemorySize = (BootDesc->MemoryHigh * 64 * 1024);
    	MemorySize += BootDesc->MemoryLow; // This is in bytes

In my system...
Low Memory = 16384 bytes
High Memory = 117309440 bytes
Total Memory = 117325824 bytes

Memory Blocks:

We would logically partition whole physical memory into blocks, whose size would be of 1 Page Size, 4 KB (4096 bytes).

How we do so?

Memory Blocks = MemorySize / PAGE_SIZE
              = 117324800 / 4096
              = 28643 blocks
              
// We would allocate memory on the basis of blocks.
// Either none or complete block.

We would use a bit to represent 1 Memory Block (Page)'s allocation status in Bitmap. Since we have 28643 memory blocks, Thus we need 28643 bits to represent the allocation status of all of them.

1 memory blocks requires 1 bit for the allocation status
28643 memory blocks would requires 28643*1 bits for the allocation status

How much bytes do we exactly needs for the bitmap?

As we know that we would need 28643 bits for allocation status of all the memory blocks.

Convert them to bytes by just dividing by the size of byte which is 8 and rounding up.

#define DIVUP(a, b) ((a / b) + (((a % b) > 0) ? 1 : 0))

BitmapSize = DIVUP(Memory Blocks, 8)
           = DIVUP(28643, 8)
           = 3580 + 1

#define DIVUP(a, b) ((a / b) + (((a % b) > 0) ? 1 : 0))

This macro divides a by b and rounds up the result if there's a remainder.

a / b: This is standard integer division. If a is not perfectly divisible by b, the result will be truncated (i.e., it discards the decimal part). For example, 5 / 2 would result in 2, not 2.5.

a % b: This calculates the remainder of the division. If there’s any remainder (a % b > 0), this indicates that a is not evenly divisible by b.

(a % b) > 0 ? 1 : 0: This part checks if there's a remainder from the division:

If a % b > 0 (i.e., there's a remainder), it adds 1 to the result of a / b, effectively rounding up.
If a % b == 0 (no remainder), it adds 0, keeping the result as-is.

Example 1:
    DIVUP(5, 2):

    a / b = 5 / 2 = 2
    a % b = 5 % 2 = 1 (there’s a remainder)
    Since 1 > 0, add 1: 2 + 1 = 3
    Result: DIVUP(5, 2) = 3

Example 2:
    DIVUP(28643, 8):
        a / b = 28643 / 8 = 3580
        a % b = 28643 % 8 = 3 (there's a remainder)
        Since 3 > 0, add 1: 3580 + 1 = 3281
        Result = DIVUP(28643, 8) = 3581

Thus we would need a total of 3581 bytes as the bitmap for the blocks.

3581 = 0xdfd

3 Memory Bitmap Location and Initialize as to be Allocated:

We would use the Bitmap method as the status indicator for the allocated region.

The Bitmap Location is 0x300000 and in the previous step we determined the size of the required bitmap memory, which is 3581 bytes (28643 bits).

Initialize whole Bitmap with 1, means whole memory is allocated

	 memset((void*)MemoryBitmap, 0xFFFFFFFF, MemoryBitmapSize); // MemoryBitmapSize = 3581

4 Loop through the Memory Regions of Memory Map

As in step 1, we have read and stored the memory map to a memory location 0x9000. Now we will loop through every memory region and on the basis of type we will unset the corresponding bit in the Bitmap memory of particular block (page).

• If the region's type is 1, which means it is available to be used.
• Free this region in bitmap:
  • As the memory region would have a starting address and the length.

  • Calculate the Frame of the starting address and count of frames for the entire region as follows:

    int frame = starting_address / PAGE_SIZE; // PAGE_SIZE = 4096.
    
    int count = length_of_the_region / PAGE_SIZE;

    • Do until count is 0:
      • Unset the corresponding bit of the frame in the bitmap memory.
      • Increment the frame to refer to the next block.
      • Decrement the count.
      • Decrement the MemoryBlocksUsed.