Implement a FrameAllocator using the bootloader’s memory map (e.g., a bitmap allocator).

Implement a `FrameAllocator` using the bootloader’s memory map (e.g., a bitmap allocator).

Mục tiêu:

Congratulations on achieving one of the most significant milestones in OS development! You have successfully taken control of the system’s memory by implementing and activating your own set of page tables. Your kernel is no longer a guest in the bootloader’s world; it is the architect of its own virtual address space and the enforcer of memory safety, complete with a robust page fault handler.

This powerful foundation unlocks the next grand challenge: dynamic memory allocation. So far, every piece of data in our kernel has been statically allocated at compile time. To build more complex and flexible systems—like task schedulers, filesystems, or even a simple command buffer—we need the ability to allocate and deallocate memory at runtime. In the Rust world, this means making types like Box, Vec, and String available to our kernel. This is all made possible by a kernel heap.

Before we can build the heap itself, we must solve a fundamental prerequisite: the heap allocator will need to request pages of virtual memory, which must be backed by frames of physical memory. To do this, it needs a reliable source of unused physical frames. This brings us to our current task: formalizing and perfecting the physical frame allocator that will serve as the engine for our kernel’s heap.

The Bedrock of the Heap: A Reliable Frame Allocator

You’ve already done excellent work in this area. During the paging setup, you created a BootInfoFrameAllocator to acquire the necessary frames for your new page tables. That allocator was perfect for its bootstrap purpose. Now, we will solidify this implementation, review its design, and understand why it’s the right tool for the job as we prepare to build our heap.

Let’s ensure our src/memory.rs contains the finalized version of the BootInfoFrameAllocator. The code below is the same robust implementation you used before, now presented with detailed comments to prepare it for its new, central role in our kernel’s memory system.

// In src/memory.rs

use bootloader::bootinfo::{MemoryMap, MemoryRegionType};
use x86_64::{
    structures::paging::{FrameAllocator, PhysFrame, Size4KiB},
    PhysAddr,
};

/// A FrameAllocator that returns usable frames from the bootloader's memory map.
/// This allocator is a simple "bump" allocator that iterates through available
/// frames and hands them out sequentially. It does not support deallocation.
pub struct BootInfoFrameAllocator {
    memory_map: &'static MemoryMap,
    next: usize, // The index of the next frame that should be returned.
}

impl BootInfoFrameAllocator {
    /// Create a new FrameAllocator from the passed memory map.
    ///
    /// This function is unsafe because the caller must guarantee that the passed
    /// memory map is valid. The main requirement is that all frames that are marked
    /// as `USABLE` in it are really unused and can be safely overwritten.
    pub unsafe fn init(memory_map: &'static MemoryMap) -> Self {
        BootInfoFrameAllocator {
            memory_map,
            next: 0,
        }
    }

    /// Creates an iterator that returns all usable frames from the memory map.
    /// This is the core logic of the allocator, powered by Rust's iterators.
    fn usable_frames(&self) -> impl Iterator<Item = PhysFrame> {
        // 1. Get an iterator over all memory regions from the bootloader's map.
        let regions = self.memory_map.iter();

        // 2. Filter the regions to find only those that are marked as `Usable`.
        //    Other types like `Reserved`, `ACPI`, or `Bootloader` are ignored.
        let usable_regions = regions
            .filter(|r| r.region_type == MemoryRegionType::Usable);

        // 3. Map each usable region to an iterator of its address range.
        let addr_ranges = usable_regions
            .map(|r| r.range.start_addr()..r.range.end_addr());

        // 4. Flatten the ranges into a single iterator of frame start addresses.
        //    `step_by(4096)` ensures we only get addresses that are aligned
        //    to the start of a 4 KiB frame.
        let frame_addresses = addr_ranges.flat_map(|r| r.step_by(4096));

        // 5. Convert each frame start address into a type-safe `PhysFrame` struct.
        frame_addresses.map(|addr| {
            PhysFrame::containing_address(PhysAddr::new(addr))
        })
    }
}

// Implement the `FrameAllocator` trait from the `x86_64` crate.
// This makes our allocator compatible with the crate's paging functions,
// such as `map_to`. This implementation is unsafe because the `allocate_frame`
// function must return only unused frames.
unsafe impl FrameAllocator<Size4KiB> for BootInfoFrameAllocator {
    fn allocate_frame(&mut self) -> Option<PhysFrame> {
        // Get the next usable frame from our iterator.
        let frame = self.usable_frames().nth(self.next);
        // Increment our counter for the next allocation.
        self.next += 1;
        frame
    }
}

A Deeper Look at the Design

This implementation is simple but powerful, and it’s a fantastic showcase of Rust’s safety and expressiveness.

The unsafe Contract: The init function is unsafe for a crucial reason. The entire stability of our kernel’s memory management rests on the promise that the memory_map provided by the bootloader is accurate. By calling this function in an unsafe block, we are telling the Rust compiler, “I, the OS developer, have verified that this memory map is trustworthy, and the frames marked ‘Usable’ are indeed available.”
The Power of Iterators: The usable_frames method is the heart of the allocator. Instead of writing complex loops and manually managing indices, we build a “pipeline” of iterator adaptors. This declarative style is less error-prone and clearly states our intent: take the regions, filter them, map them to address ranges, flatten them into frame addresses, and finally convert them into PhysFrame types.
Bump Allocator Strategy: This type of allocator, which simply increments a counter (next) to hand out the next available resource, is called a bump allocator. Its primary advantage is its simplicity and speed. The main limitation is that it cannot easily handle deallocation. If we were to “free” a frame, there’s no way to mark that slot in the iterator as usable again. For our kernel’s heap, which will be allocated once and live forever, this limitation is perfectly acceptable. More complex systems that frequently allocate and deallocate memory (e.g., for user-space processes) would require a more sophisticated strategy like a bitmap allocator or a buddy system allocator.

You have already proven this allocator works—it’s the very same code that successfully provided the physical frames for your kernel’s page tables in the previous step. For this task, simply ensure this code is cleanly organized in your src/memory.rs file. A successful cargo build confirms you’re ready for the next stage.

What’s Next?

With our physical frame allocator finalized and ready, we have a reliable source of the fundamental resource: physical memory. We are now ready to begin constructing the heap itself. The first step in this process is to decide where in the virtual address space our heap will reside. In the next task, you will define a virtual address range that will be dedicated to the kernel heap.

Define Kernel Heap Virtual Address Space

Mục tiêu: Establish the virtual memory region for the kernel heap by creating a new allocator module and defining constants for the heap’s start address and size.

Fantastic work on implementing the BootInfoFrameAllocator! You have successfully built the bedrock of your kernel’s memory management system. This allocator gives you a reliable source of physical memory frames—the raw, tangible resource needed to build anything new. You have mastered the “what” of memory allocation: the physical frames.

Now, we must address the “where.” Where in the abstract, virtual address space should these new allocations live? Our current task is to carve out a specific, dedicated region of virtual memory for our kernel’s future heap.

Cartography of the Virtual World: Choosing a Heap Location

Just as a city planner zones a specific area for residential buildings, we must zone a specific range of virtual addresses for our kernel’s dynamic allocations. We can’t just pick addresses at random. A good heap region should be:

Contiguous: It must be a single, unbroken block of virtual addresses.
Non-Conflicting: It must not overlap with any existing memory mappings, such as our kernel’s code, its stack, the VGA buffer, or the memory-mapped physical memory region.
Well-Defined: It should have a fixed start address and a known size, making it easy to manage.

A common and robust convention in OS development is to place the kernel’s heap in the “higher half” of the virtual address space. This keeps kernel-exclusive memory cleanly separated from the lower addresses that might one day be used for user-space programs.

For our kernel, we will choose a memorable and distinct starting address, as suggested in the project roadmap: 0x4444_4444_0000. The repeating 4s make it stand out clearly in logs and debugger outputs, which is a surprisingly helpful trick. We will also define an initial size for our heap. Let’s start with 100 KiB, which is more than enough for our initial needs.

From Concept to Code: Defining the Heap Constants

Good code organization dictates that we should place all our allocation-related logic into a new, dedicated module.

First, create a new file named src/allocator.rs.

Next, register this new module in your src/main.rs file by adding the mod declaration near the top.

// In src/main.rs

#![no_std]
#![no_main]

// ... other use statements
extern crate alloc;

// Add this line to declare the new allocator module
pub mod allocator;
pub mod memory;
// ... rest of your modules

Now, let’s populate our new src/allocator.rs file with the constants that define our heap’s virtual address space.

// In src/allocator.rs

/// The virtual address where the kernel heap will be located.
/// This address is chosen to be in the "higher half" of the address space
/// and is easy to recognize during debugging. It must not conflict with
/// other mapped regions.
pub const HEAP_START: u64 = 0x_4444_4444_0000;

/// The size of the kernel heap. 100 KiB is chosen as a reasonable
/// starting size, sufficient for initial dynamic allocation needs.
pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB

Let’s break down these two simple but crucial lines:

pub const HEAP_START: u64: We declare a public constant named HEAP_START. Its type is u64 because 64-bit virtual addresses are fundamentally 64-bit unsigned integers. We assign it our chosen high-memory address. The underscores (_) are just for readability and are ignored by the compiler.
pub const HEAP_SIZE: usize: We declare another public constant for the heap’s size. We use the type usize because memory sizes and offsets in Rust are typically represented by usize. We calculate the value as 100 * 1024 to represent 100 KiB in bytes.

And with that, this task is complete! You have successfully defined the boundaries of your future kernel heap. This was a purely definitional task; there are no functional changes to observe when you run the kernel.

A successful compilation is the sign of success for this task. Run cargo build to ensure the new module is correctly integrated.

cargo build

The build should complete without any errors, confirming that you have perfectly set the stage for the next step.

What’s Next?

You have now established the virtual address range for your heap. This is like drawing a rectangle on a map and labeling it “Future Development.” Currently, that area on the map is empty; it doesn’t correspond to any real land.

The next logical and crucial task is to make this virtual space real. You will use the BootInfoFrameAllocator you perfected in the last task, along with the OffsetPageTable mapper, to create page table entries for this entire 100 KiB range. Each page in the heap’s virtual address range will be mapped to a unique, unused physical frame, thus breathing life into the kernel heap.

Initialize the Kernel Heap

Mục tiêu: Implement the init\_heap function to map the kernel’s virtual heap address range to physical memory frames, making the memory region ready for a heap allocator.

Excellent work! In the previous task, you made a crucial architectural decision by defining a dedicated virtual address range for your kernel’s heap. By creating the HEAP_START and HEAP_SIZE constants, you essentially drew a rectangle on your kernel’s virtual address map and labeled it “Future Kernel Heap.” This was the act of planning.

Now, it’s time for construction. That rectangle on the map is currently just empty, unmapped space. If the kernel were to try and access any address within that range, it would immediately trigger a page fault. Our current, critical task is to bring this virtual space to life. We will iterate through every page in our defined heap region and back it with real, physical memory, creating the tangible foundation upon which our heap will be built.

From Virtual Blueprint to Physical Reality

The process of making our virtual heap region usable involves a beautiful synergy of the tools you have already built:

The Virtual Pages: We will use our HEAP_START and HEAP_SIZE constants to calculate the range of virtual pages that make up our heap.
The Physical Frames: For each of these virtual pages, we will call our trusty BootInfoFrameAllocator to request a fresh, unused 4 KiB physical frame from the system’s RAM.
The Connection: We will use our OffsetPageTable mapper, specifically its powerful map_to function, to create the page table entries that link each virtual page to its newly allocated physical frame.

By the end of this task, the 0x4444_4444_0000 virtual address will no longer be an empty void but the start of a 100 KiB contiguous block of usable memory.

Implementing the Heap Initialization Function

Let’s encapsulate this logic in a new function called init_heap inside our src/allocator.rs module. This function will be the single entry point for setting up our heap’s memory region.

Open src/allocator.rs and add the following code:

// In src/allocator.rs

// Add these new `use` statements at the top of the file.
use crate::memory::BootInfoFrameAllocator;
use x86_64::{
    structures::paging::{
        mapper::MapToError, FrameAllocator, Mapper, Page, PageTableFlags, Size4KiB,
    },
    VirtAddr,
};

pub const HEAP_START: u64 = 0x_4444_4444_0000;
pub const HEAP_SIZE: usize = 100 * 1024; // 100 KiB

/// Initializes the kernel's heap by mapping the designated virtual address
/// range to physical frames.
///
/// This function must be called only once to avoid aliasing `&mut` references.
///
/// # Arguments
/// * `mapper`: A mutable reference to an `OffsetPageTable` instance.
/// * `frame_allocator`: A mutable reference to a `FrameAllocator` implementation.
///
/// # Returns
/// An empty `Result` on success, or a `MapToError` on failure.
pub fn init_heap(
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) -> Result<(), MapToError<Size4KiB>> {
    // Calculate the range of pages that the heap will occupy.
    let page_range = {
        let heap_start = VirtAddr::new(HEAP_START);
        let heap_end = heap_start + HEAP_SIZE - 1u64;
        let heap_start_page = Page::containing_address(heap_start);
        let heap_end_page = Page::containing_address(heap_end);
        Page::range_inclusive(heap_start_page, heap_end_page)
    };

    // Iterate over each page in the range and map it.
    for page in page_range {
        // Allocate a physical frame to back this page.
        // If allocation fails, the allocator is out of memory.
        let frame = frame_allocator
            .allocate_frame()
            .ok_or(MapToError::FrameAllocationFailed)?;

        // Define the permissions for the heap pages.
        // PRESENT: The page is mapped.
        // WRITABLE: The page can be written to.
        let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;

        // Create the mapping in the page tables.
        // The `map_to` method is unsafe because the caller must ensure that the
        // frame is not already in use. Our frame allocator guarantees this.
        // The result of `map_to` is a `MapperFlush` object, which we must call
        // `.flush()` on to update the TLB (Translation Lookaside Buffer).
        unsafe {
            mapper.map_to(page, frame, flags, frame_allocator)?.flush();
        }
    }

    Ok(())
}

This function is the heart of our heap’s memory setup. Let’s break it down:

Function Signature: init_heap is generic over the Mapper and FrameAllocator traits. This is a good practice that makes the function more flexible and testable, as it can work with any type that implements these traits.
page_range Calculation:
- We create VirtAddr instances for the start and end of the heap.
- We use the Page::containing_address method to find the pages that contain these start and end addresses.
- Finally, Page::range_inclusive gives us an iterator over every single virtual page from the start to the end of our heap region.
The for Loop: This is where the magic happens. For each page in our calculated range:
1. frame_allocator.allocate_frame(): We call our allocator to get a free physical frame. The .ok_or(...) part is robust error handling: if the allocator returns None (meaning we’re out of physical memory), it converts this into a MapToError::FrameAllocationFailed error and propagates it up.
2. let flags = ...: We define the permissions for our heap memory. PRESENT is required to make the mapping valid, and WRITABLE is essential because the entire purpose of a heap is to be written to.
3. unsafe { mapper.map_to(...).flush(); }: This is the core mapping operation.
  - We call map_to inside an unsafe block because we are making a promise: the frame we provide is unused. Our bump allocator’s design fulfills this promise.
  - The ? operator again handles errors: if map_to fails (e.g., if it also can’t allocate frames for new intermediate page tables), the error is returned.
  - .flush() is a critical final step. This method updates the Translation Lookaside Buffer (TLB), which is a CPU cache for address translations. Without this, the CPU might continue to use old, cached translation data that says our heap pages are unmapped, leading to a page fault even after we’ve correctly updated the page tables.

Calling `init_heap` from `kernel_main`

Now that we have our powerful init_heap function, we need to call it during our kernel’s startup sequence. The correct place is after our memory objects (mapper and frame_allocator) have been created.

Open src/main.rs and add the call to init_heap:

// In src/main.rs

// ... (existing use statements)

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    println!("Hello, World!");
    os_kernel::gdt::init();
    os_kernel::interrupts::init_idt();
    unsafe { os_kernel::interrupts::PICS.lock().initialize() };
    x86_64::instructions::interrupts::enable();

    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        memory::BootInfoFrameAllocator::init(&boot_info.memory_map)
    };

    // --- Add this new block to initialize the heap ---
    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");
    // --- End of new block ---

    println!("It did not crash!");
    os_kernel::hlt_loop();
}

We use .expect() here because a failure to initialize the kernel heap is a fatal, non-recoverable error during startup. If this fails, something is fundamentally wrong, and panicking is the appropriate response.

What to Expect

If you run your kernel now, you will see… absolutely no change in the output.

cargo run

Hello, World!
It did not crash!
(Timer and keyboard interrupts continue)

This is a sign of complete success! The absence of a page fault is your proof that the mapping worked perfectly. You have successfully allocated and mapped 100 KiB of virtual memory, backed by 25 unique physical frames (100 KiB / 4 KiB per frame = 25 frames). This memory region is now present, writable, and ready to be managed.

What’s Next?

You have successfully prepared the ground. The virtual address space for the heap is now backed by real, physical memory. However, this is just a raw, unmanaged block of memory. We still need a manager—an allocator—that knows how to carve up this 100 KiB region into smaller blocks for individual requests (Box::new, vec![], etc.) and keep track of which blocks are free and which are in use.

In the next task, you will add a crate like linked_list_allocator to your project. This crate provides the sophisticated logic needed to manage the memory region you have just so masterfully prepared.

Add a Heap Allocator Crate Dependency

Mục tiêu: Add the linked\_list\_allocator crate as a dependency in the Cargo.toml file to prepare for implementing dynamic memory allocation for the kernel’s heap.

In the previous task, you achieved a monumental feat of construction. By creating and calling the init_heap function, you transformed a theoretical plan—a rectangle drawn on your virtual address map—into a tangible reality. There is now a 100 KiB region of virtual memory starting at 0x4444_4444_0000 that is fully backed by real, physical frames. This memory is mapped, present, and writable. You have successfully prepared the raw material for your kernel’s heap.

However, a block of raw memory is like a large, empty warehouse. It’s useful, but you can’t just start placing items randomly. You need a system: aisles, shelves, and a librarian who knows where everything is and where there’s empty space. In memory management, this “librarian” is called a heap allocator. Our current task is to choose and hire this librarian by adding a specialized Rust crate to our project.

The Management Problem: Why We Need an Allocator Crate

The 100 KiB of memory you’ve mapped is just a contiguous block of bytes. To make it useful for dynamic allocations (like Box::new or creating a Vec), we need an algorithm that can:

Service Allocation Requests: When the code asks for 16 bytes, the allocator must find a free block of at least that size, mark it as “used,” and return a pointer to it.
Handle Deallocations: When a Box or Vec goes out of scope, the memory it was using must be returned to the allocator, who marks it as “free” and available for future allocations.
Track Free Space: The allocator must maintain a data structure that keeps track of all the free blocks, their locations, and their sizes.

Common strategies for this include bump allocators (which you’ve already implemented for frames), bitmap allocators, and linked list allocators. Writing such an allocator from scratch is a complex and error-prone systems programming task. It is a perfect opportunity to leverage the Rust ecosystem, which provides excellent, no_std-compatible crates for this very purpose.

For our kernel, we will use the linked_list_allocator crate. It’s a fantastic choice because it’s simple, well-tested, and its allocation logic is easy to understand. It works by treating the free blocks of memory within the heap as nodes in a linked list. When a new allocation is needed, it searches this list for a suitable block, carves out the requested amount, and updates the list with the remaining free space.

Adding the Dependency

The first and only step for this task is to tell Cargo that our project now depends on the linked_list_allocator crate. This will make its data structures and functions available for us to use in the next task.

Open your Cargo.toml file and add the highlighted line to your [dependencies] section. We are specifying a version (0.9.0) that is known to be stable and works well in no_std environments.

[dependencies]
bootloader = "0.9.23"
lazy_static = { version = "1.4.0", features = ["spin_no_std"] }
pc-keyboard = "0.7.0"
pic8259 = "0.10.1"
spin = "0.5.2"
x86_64 = "0.14.10"
linked_list_allocator = "0.9.0"

Verifying the Change

This task did not involve writing any new Rust code, only modifying the project’s configuration. The sign of success is a clean build. Run the following command in your terminal:

cargo build

You will see Cargo download and compile linked_list_allocator (and any dependencies it might have). If the build finishes without errors, you have successfully completed this task. You have officially added the “heap librarian” to your kernel’s team. It’s not doing any work yet, but it has been hired and is ready for its first assignment.

What’s Next?

With the linked_list_allocator crate now part of our project, we are ready to put it to work. The next task is to actually integrate it into our kernel’s code. You will use the #[global_allocator] attribute to tell the Rust compiler that this crate’s allocator is the one that should be used for all dynamic allocations within our kernel. This is a critical step that will finally enable the use of types like Box and Vec.

Register the Global Heap Allocator

Mục tiêu: Designate a static LockedHeap instance as the kernel’s global memory allocator using the #[global\_allocator] attribute and implement a corresponding #[alloc\_error\_handler] to manage allocation failures.

Excellent! In the previous task, you successfully “hired” our kernel’s heap manager by adding the linked_list_allocator crate as a dependency. The logic and data structures needed to manage our heap are now compiled into our kernel, but they are sitting idle. The Rust compiler, and by extension the alloc crate which provides types like Box and Vec, has no idea that this new manager exists or that it’s available for use.

Our current task is to make the official introduction. We need to tell the Rust compiler, in no uncertain terms, “This is our memory allocator. When any part of the kernel requests dynamic memory, send those requests here.” We will accomplish this by using a special attribute: #[global_allocator].

The `#[global_allocator]` Attribute: Anointing the Manager

In Rust, the ability to use types like Box and Vec is provided by the standard alloc crate. This crate needs to be able to call out to some underlying memory allocator to get the raw memory it needs. The #[global_allocator] attribute is a program-wide directive that points to a single, static variable that will serve this role.

This static variable must implement a special, unsafe trait called GlobalAlloc. This trait defines the low-level interface for memory management, with functions like alloc (for allocation) and dealloc (for deallocation). Fortunately, the linked_list_allocator crate we just added provides a ready-made type that implements this trait for us, complete with the necessary locking for safe use in a concurrent environment (which is essential for our kernel with its interrupts).

Step 1: Designating the Global Allocator

Let’s go to our src/allocator.rs module and define our global allocator instance. We will create a static item and apply the #[global_allocator] attribute to it.

// In src/allocator.rs

use linked_list_allocator::LockedHeap;
// ... (rest of existing use statements)

// Add this attribute and static item
#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();

// ... (HEAP_START, HEAP_SIZE, init_heap function)

This small addition is incredibly powerful. Let’s break it down:

use linked_list_allocator::LockedHeap;: We first import the LockedHeap type from our new crate. This specific type is a wrapper that combines the core linked-list allocation logic with a spinlock (spin::Mutex). This is critically important. It ensures that if an interrupt handler needs to allocate memory, it won’t corrupt the allocator’s internal state if it happens to interrupt another allocation in progress.
#[global_allocator]: This is the magic attribute. It tells the Rust compiler that the static item immediately following it is the one and only global heap allocator for the entire program.
static ALLOCATOR: LockedHeap: We declare a static variable named ALLOCATOR. It’s static because it must exist for the entire lifetime of the kernel. We give it the type LockedHeap.
= LockedHeap::empty();: We initialize our allocator using the empty constructor. This is a crucial point: we have now created the allocator and told the compiler about it, but it is uninitialized. It doesn’t yet know about the 100 KiB memory region you so carefully prepared. It’s like having a librarian standing in an empty room with no shelves or books. We will give the allocator its memory to manage in the next task.

Step 2: Handling Allocation Failures

With a global allocator in place, the compiler now allows us to use types from the alloc crate. However, this comes with a new responsibility. What should happen if an allocation fails (e.g., the heap runs out of memory)? We must provide a function to handle this scenario, marked with the #[alloc_error_handler] attribute.

In a complex OS, you might try to free up some memory or kill a process. In our simple kernel, an allocation failure is a fatal, unrecoverable error. The only sensible action is to panic.

Let’s add this handler to our src/main.rs file. While we’re there, we also need to explicitly link the alloc crate.

// In src/main.rs

#![no_std]
#![no_main]
// Add this feature gate for the allocator error handler
#![feature(custom_test_frameworks)]
#![feature(alloc_error_handler)]

// Explicitly link the `alloc` crate
extern crate alloc;

// ... (other use statements and module declarations)

// Add this new function to handle allocation errors
#[alloc_error_handler]
fn alloc_error_handler(layout: alloc::alloc::Layout) -> ! {
    panic!("allocation error: {:?}", layout)
}

// ... (the rest of your main.rs, including kernel_main)

Let’s analyze these changes: * #![feature(alloc_error_handler)]: The alloc_error_handler is still a slightly unstable feature, so we need to enable it with this attribute at the top of our crate root. * extern crate alloc;: This line makes the alloc crate and its types (Box, Vec, etc.) available throughout our kernel. * #[alloc_error_handler]: This attribute designates alloc_error_handler as the function to be called when the global allocator reports an error. * fn alloc_error_handler(...) -> !: The function receives a Layout struct, which describes the size and alignment of the allocation that failed. We simply include this in a panic! message for debugging purposes. The -> ! return type signifies that this function never returns; it will always halt the kernel.

What to Expect

Once again, running your kernel will produce no visible change in output. This was purely a setup and configuration task.

cargo run

A successful build is the sign of success. You have now fully integrated a heap allocator into your kernel’s architecture. The compiler knows where to send allocation requests, and you have a safety net in place for when those requests fail. The librarian is at their post, and the emergency procedures are on the wall. The library is still empty, but it’s officially open for business.

What’s Next?

You are on the verge of unlocking dynamic memory in your kernel. The global allocator has been designated, but it’s still empty and uninitialized. In the very next task, you will take the final step: you will initialize the ALLOCATOR instance, handing it the pointer to the start of the heap memory region and its size. This will finally connect the allocator’s logic to the physical memory you mapped, making dynamic allocation a reality.

Initialize the Kernel Heap Allocator

Mục tiêu: Initialize the global linked\_list\_allocator instance by calling its init method. This provides the allocator with the mapped heap memory region, finally enabling dynamic memory allocation in the kernel.

In the last task, you officially appointed a “librarian” for our kernel’s heap: the linked_list_allocator. By using the #[global_allocator] attribute, you told the Rust compiler exactly who is in charge of managing dynamic memory. You’ve also prepared for the worst by implementing an #[alloc_error_handler].

However, our librarian, the static ALLOCATOR, is currently standing in an empty, dark warehouse. We created it using LockedHeap::empty(), so while the compiler knows it exists, the allocator itself has no memory to manage. Any attempt to allocate memory right now would fail instantly.

Our current task is to flip the lights on in that warehouse. We will initialize our global ALLOCATOR instance, providing it with the starting address and size of the 100 KiB memory region you so carefully prepared in the preceding tasks. This is the crucial final act that connects the allocator’s sophisticated logic to the tangible memory, finally enabling dynamic allocation in our kernel.

Handing Over the Keys: The `init` Method

The linked_list_allocator::LockedHeap type provides a special init function for exactly this purpose. This function takes the start address and size of a memory region and sets up the allocator’s internal data structures to manage that region.

You might wonder why we couldn’t just provide this information when we created the ALLOCATOR static. The reason is a critical matter of ordering:

Mapping Must Come First: We can only initialize the allocator with a memory region that is valid and mapped.
Initialization Comes Second: Our allocator::init_heap function performs this mapping. Therefore, we must call init_heap first. Only after it successfully completes can we then call the allocator’s init function to hand over control of that now-valid memory.

This init function is also marked as unsafe. By calling it, we are making a solemn promise to the allocator crate: “I guarantee that the memory range I am giving you is mapped, writable, and will not be used by anyone else for any other purpose.” Thanks to the robust page table mapping you built in the previous tasks, this is a promise we can confidently keep.

The Final Connection: Updating `kernel_main`

Let’s make this final connection. The change is small, but its impact is enormous. We will add a few lines to our kernel_main function in src/main.rs, right after we successfully initialize the heap’s memory mapping.

// In src/main.rs

// ... (other use statements)
use os_kernel::{allocator, memory}; // ensure allocator is in scope
// ...

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // ... (GDT, IDT, PICs, interrupts initialization)

    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        memory::BootInfoFrameAllocator::init(&boot_info.memory_map)
    };

    // Initialize the heap's memory region (this maps the pages)
    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");

    // This is the new block that initializes the allocator with the mapped region.
    // We call this AFTER `init_heap` to ensure the memory is valid.
    unsafe {
        allocator::ALLOCATOR.lock().init(allocator::HEAP_START as usize, allocator::HEAP_SIZE);
    }

    println!["It did not crash!"];
    os_kernel::hlt_loop();
}

Let’s dissect these crucial new lines:

unsafe { ... }: We place the call inside an unsafe block. This is our declaration to the Rust compiler that we are upholding the contract of the init function—the memory region is valid and ready.
allocator::ALLOCATOR: We access our static global allocator, which we defined in the allocator module.
.lock(): This is essential. The LockedHeap uses a spinlock to protect its internal data. We must acquire the lock to get mutable access. This ensures that our initialization is an atomic operation and safe from interrupts.
.init(start, size): We call the initialization function.
- allocator::HEAP_START as usize: We pass our heap’s starting address constant. The init function expects a usize, so we perform a simple type cast.
- allocator::HEAP_SIZE: We pass our heap’s size constant.

What to Expect

Once again, this was a setup task. When you run your kernel, you will see no visible change in the output.

cargo run

Hello, World!
It did not crash!
(Timer and keyboard interrupts continue as normal)

This is a sign of perfect success! The kernel boots, initializes the heap, and continues running without a panic or a page fault. Under the surface, a monumental change has occurred. Your kernel now possesses a fully functional, ready-to-use heap. Our librarian has been shown to their library, the shelves are stocked, and they are ready to start checking out books.

What’s Next?

You are on the verge of the payoff for this entire step. Every piece of the dynamic memory puzzle is now in place: the physical frame allocator, the virtual memory mapping, the heap allocator crate, the global allocator designation, and now, the final initialization.

In the next and final task of this step, you will finally get to use the heap. You will write code that allocates a Box and a Vec, stores data in them, and prints that data to the screen, providing the first tangible proof that your kernel’s dynamic memory system is alive and working.

First Heap Allocation: Using Box and Vec

Mục tiêu: Test the newly implemented kernel heap allocator by performing the first dynamic memory allocations using Rust’s Box and Vec from the alloc crate to verify the memory management system works.

This is the moment you’ve been working towards. Over the last several tasks, you have performed the meticulous and complex work of a systems architect. You built a physical frame allocator, designed a virtual address space for a heap, mapped it into reality with page tables, and finally, appointed and initialized a global allocator to manage it. The entire foundation for dynamic memory is in place.

In the previous task, you made the final, critical connection by calling ALLOCATOR.lock().init(...). This handed over the keys to the 100 KiB memory region to our “heap librarian,” the linked_list_allocator. The librarian is now at their desk, the shelves are stocked, and the system is ready to check out its first books. Our current task is to walk up to that desk and make our first request—to finally use the heap and see tangible proof that our entire system works.

Unlocking the Power of the `alloc` Crate

By designating a #[global_allocator], you have unlocked the ability to use Rust’s standard allocation-aware types, provided by the alloc crate. This is a monumental leap in your kernel’s capabilities. Two of the most fundamental of these types are:

Box<T>: This is a smart pointer that owns data allocated on the heap. When you call Box::new(some_value), you are asking the global allocator for a block of memory large enough to hold some_value. The allocator finds a suitable block, gives you a pointer to it (which the Box wraps), and you can use that Box just like a regular reference. When the Box goes out of scope, it automatically calls the global allocator to dealloc the memory, making it available again.
Vec<T>: This is a contiguous, growable array type, often called a vector. When you create a Vec and push elements into it, it allocates memory on the heap to store them. If it runs out of space, it will ask the allocator for a new, larger block of memory, copy the old data over, and deallocate the old block. It’s a perfect test for both allocation and reallocation.

It’s time to put these types to the test.

The First Allocations: Putting the Heap to Work

We will now add code to our kernel_main function to perform two simple tests: allocating a single number using Box, and creating a dynamic list of numbers using Vec.

Let’s modify src/main.rs. We’ll need to bring Box and Vec into scope from the alloc crate and then add our test code after the allocator has been initialized.

// In src/main.rs

// ... (existing attributes and use statements)

// Bring Box and Vec into scope
extern crate alloc;
use alloc::boxed::Box;
use alloc::vec::Vec;

// ... (your other modules and handlers)

fn kernel_main(boot_info: &'static BootInfo) -> ! {
    // ... (GDT, IDT, PICs, interrupts initialization)

    let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
    let mut mapper = unsafe { memory::init(phys_mem_offset) };
    let mut frame_allocator = unsafe {
        memory::BootInfoFrameAllocator::init(&boot_info.memory_map)
    };

    allocator::init_heap(&mut mapper, &mut frame_allocator)
        .expect("heap initialization failed");

    // Initialize the allocator with the mapped region.
    // This MUST be called after `init_heap`.
    unsafe {
        allocator::ALLOCATOR.lock().init(allocator::HEAP_START, allocator::HEAP_SIZE);
    }

    // --- THIS IS THE NEW TEST CODE ---

    // 1. Allocate a single value on the heap using `Box`.
    // The `Box::new` call will use our global allocator to find free memory.
    let x = Box::new(41);
    println!("heap_test_box: value is {}, address is {:p}", x, x);

    // 2. Create a dynamically sized vector and push values to it.
    // This will likely cause multiple allocations as the vector grows.
    let mut vec = Vec::new();
    for i in 0..500 {
        vec.push(i);
    }
    println!("heap_test_vec: last value is {}, len is {}", vec[499], vec.len());

    // --- END OF NEW TEST CODE ---

    println!("It did not crash!");
    os_kernel::hlt_loop();
}

This is the payoff for all your hard work. Let’s break down the new code:

use alloc::boxed::Box; and use alloc::vec::Vec;: We explicitly import the types we want to use.
let x = Box::new(41);: This is our first heap allocation. Box::new makes a call to the global allocator, which finds a suitable spot in our 100 KiB heap region and returns a pointer. The value 41 is stored at that new location.
println!("heap_test_box: ...", x, x);: We then print two things to verify this worked:
- x: Dereferencing the box (*x, which println! does automatically) gives us the value 41.
- {:p}: This special format specifier prints the raw pointer address of the heap allocation. You should see an address that falls within our defined 0x4444_4444_0000 heap range!
let mut vec = Vec::new();: We create a new, empty vector. This may or may not perform an initial allocation, depending on the implementation.
for i in 0..500 { vec.push(i); }: This loop is a more rigorous test. The first push will definitely allocate. As we continue to push items, the vector will eventually reach its capacity and need to reallocate a larger block of memory, testing the allocator’s ability to handle different request sizes.
println!("heap_test_vec: ...", vec[499], vec.len());: We verify the vector’s contents by accessing its last element and printing its final length.

The Moment of Truth: A Dynamic Kernel

It’s time to run your kernel and witness the result.

cargo run

QEMU will launch, and on your screen, you should see the glorious output, proving that every piece of your memory management system is working in perfect harmony:

Hello, World!
heap_test_box: value is 41, address is 0x444444440000
heap_test_vec: last value is 499, len is 500
It did not crash!
(Timer and keyboard interrupts continue as normal)

Congratulations! This is a phenomenal success. The output provides undeniable proof:

Your Box was allocated successfully, its data (41) is intact, and its address is right where it should be—at the very beginning of the heap.
Your Vec grew to 500 elements, meaning the allocator successfully serviced multiple allocation and reallocation requests.
The kernel remains stable and continues to run after these dynamic memory operations.

You have successfully built a kernel heap from the ground up, a task that touches on the deepest and most fundamental concepts of operating system design. Your kernel is no longer a static program; it is a dynamic system capable of managing its own memory at runtime.

What’s Next? Your First Enhancement: A Kernel Shell

You have now completed all the foundational steps of this project. You have a bootable kernel, it handles interrupts, it controls its own virtual memory, and it has a working heap. The world is your oyster. The project roadmap outlines several enhancements to transform this kernel into a true micro-OS.

A fantastic next step is to build on what you’ve just accomplished by creating a simple command-line interface, or shell. This will involve using your working keyboard driver to read user input and your new heap to store that input in a String or Vec<u8>. You’ll then parse and execute simple commands like help and echo. This is a fun and rewarding feature that will make your kernel truly interactive.