今天要配置一頁記憶體，寫入資料，釋放後再配置一次。
如果配置器確實回收了那一頁，我們應該拿到相同位址，而且上次留下的資料已經清成零。

到目前為止，核心的空間大多在連結時就決定了。
但行程數量與執行需求會改變，接下來需要一個能在執行期間追蹤空間使用情況的配置器。

Page 與 Frame，先分清楚管理的是哪一側

《Operating System Concepts》第 10 版第 9.3.1 節，把實體記憶體切成固定大小的 frame，邏輯記憶體則切成相同大小的 page。
分頁表負責建立兩邊的對應，讓邏輯上連續的程式可以使用分散的實體空間。

今天先實作實體空間的配置，不啟用位址轉譯。
名稱沿用核心開發常見的 Page Allocator，但實際發出去的是 4 KiB 實體區塊，每一頁大小為 4096 bytes。
分頁表要等 Day 14 才會加入，因此現在配置一頁並不代表已經擁有行程隔離。

《OS in 1,000 Lines》的〈記憶體分配〉使用往前推進指標的簡單配置方式。
本篇延伸出可釋放的版本，以小型表格追蹤連續配置區間，方便直接驗證回收和重複使用。
這些釋放檢查是本系列的教學擴充，不是教材原有配置器的功能。

先圈出可以使用的 RAM

接續 Day 08，在 30-days-os-kernel/tiny-kernel/kernel.ld 的 .stack 區段之後、SECTIONS 結尾之前加入：

    .page_pool (NOLOAD) : ALIGN(4096) {
        __free_ram = .;
        . += 16 * 4096;
        __free_ram_end = .;
    }
    ASSERT(__free_ram_end <= 0x88000000, "page pool exceeds 128 MiB RAM")

我們先管理 16 頁，也就是 64 KiB，讓耗盡測試能在短時間完成。
這段空間排在核心程式、靜態資料與啟動堆疊之後，避免互相覆蓋。

本文固定 QEMU virt 的 RAM 為 128 MiB，從 0x80000000 開始，到不包含 0x88000000 的位置結束。
這是此實驗的已知平台配置，並非從韌體自動發現完整記憶體地圖。
請在 Makefile 的 run 命令中，於 -machine virt 後加入 -m 128M -smp 1。

新增 memory.h：

#pragma once
#include "kernel.h"

#define PAGE_SIZE 4096u
#define POOL_PAGES 16u

void memory_init(void);
void *alloc_pages(unsigned int n);
void free_pages(void *ptr, unsigned int n);
unsigned int free_page_count(void);
void allocator_test(void);

一個小型表格記錄整筆配置

新增 memory.c：

#include "memory.h"

extern char __free_ram[], __free_ram_end[];
static unsigned int allocation[POOL_PAGES];
static unsigned int available;
static uintptr_t pool_begin;

void memory_init(void) {
    pool_begin = (uintptr_t) __free_ram;
    KASSERT((pool_begin & (PAGE_SIZE - 1)) == 0);
    KASSERT((uintptr_t) __free_ram_end - pool_begin == POOL_PAGES * PAGE_SIZE);
    memset(allocation, 0, sizeof(allocation));
    available = POOL_PAGES;
}

unsigned int free_page_count(void) {
    return available;
}

void *alloc_pages(unsigned int n) {
    if (n == 0 || n > POOL_PAGES)
        return NULL;
    for (unsigned int i = 0; i <= POOL_PAGES - n; i++) {
        unsigned int j = 0;
        while (j < n && allocation[i + j] == 0)
            j++;
        if (j != n)
            continue;
        allocation[i] = n;
        for (j = 1; j < n; j++)
            allocation[i + j] = UINT32_MAX;
        available -= n;
        void *ptr = (void *) (pool_begin + i * PAGE_SIZE);
        memset(ptr, 0, n * PAGE_SIZE);
        return ptr;
    }
    return NULL;
}

void free_pages(void *ptr, unsigned int n) {
    uintptr_t address = (uintptr_t) ptr;
    KASSERT(n > 0 && n <= POOL_PAGES);
    KASSERT(address >= pool_begin);
    KASSERT(address < (uintptr_t) __free_ram_end);
    KASSERT((address - pool_begin) % PAGE_SIZE == 0);
    unsigned int i = (address - pool_begin) / PAGE_SIZE;
    KASSERT(n <= POOL_PAGES - i);
    KASSERT(allocation[i] == n);
    for (unsigned int j = 1; j < n; j++)
        KASSERT(allocation[i + j] == UINT32_MAX);
    for (unsigned int j = 0; j < n; j++)
        allocation[i + j] = 0;
    available += n;
}

表格中的 0 表示未使用，一筆配置的第一格記錄頁數，後續頁面用 UINT32_MAX 表示它們屬於同一筆配置。
例如配置三頁，表格會出現 3, UINT32_MAX, UINT32_MAX。
釋放時因此能檢查起始位址與長度，避免把三頁配置中的第二頁誤當成獨立配置。

檢查全部通過後才清除紀錄，避免驗證到一半就已經破壞表格。
alloc_pages() 找不到足夠連續空間時回傳 NULL，呼叫者必須檢查結果。
free_pages() 收到錯誤參數則代表核心使用方式違反約定，所以進入 assertion。

memory_init() 只在開機時執行一次，不能在尚有配置被使用時再呼叫，否則會抹掉所有占用紀錄。
目前固定單核心且不從中斷處理器配置記憶體，尚未加入鎖。

讓回收、清零與耗盡都有檢查

新增 memory_test.c：

#include "memory.h"

void allocator_test(void) {
    unsigned int initial = free_page_count();
    uint32_t *a = alloc_pages(1);
    void *b = alloc_pages(2);
    KASSERT(a != NULL && b != NULL);
    KASSERT((uintptr_t) a % PAGE_SIZE == 0);
    KASSERT((uintptr_t) b % PAGE_SIZE == 0);
    KASSERT(free_page_count() == initial - 3);
    for (unsigned int i = 0; i < PAGE_SIZE / sizeof(*a); i++)
        a[i] = 0xdeadbeef;
    uintptr_t old_address = (uintptr_t) a;
    free_pages(a, 1);
    uint32_t *c = alloc_pages(1);
    KASSERT((uintptr_t) c == old_address);
    for (unsigned int i = 0; i < PAGE_SIZE / sizeof(*c); i++)
        KASSERT(c[i] == 0);
    printf("reuse=ok zero=ok free=%u\n", free_page_count());
    free_pages(c, 1);
    free_pages(b, 2);
    KASSERT(free_page_count() == initial);
    KASSERT(alloc_pages(0) == NULL);
    KASSERT(alloc_pages(POOL_PAGES + 1) == NULL);
    void *all = alloc_pages(POOL_PAGES);
    KASSERT(all != NULL);
    KASSERT(alloc_pages(1) == NULL);
    free_pages(all, POOL_PAGES);
    KASSERT(free_page_count() == initial);
    printf("exhaustion=ok recovered=%u\n", free_page_count());
}

在 Makefile 的 SOURCES 加入 memory.c memory_test.c，保留 Day 08 的來源檔。
在 kernel.c 加入 #include "memory.h"，並取代 kernel_main()：

void kernel_main(void) {
    WRITE_CSR(stvec, (unsigned int) trap_entry);
    memory_init();
    allocator_test();
    for (;;)
        __asm__ __volatile__("wfi");
}

在 tiny-kernel/ 執行 make 與 make run，預期看到：

reuse=ok zero=ok free=13
exhaustion=ok recovered=16

這裡的 reuse=ok 對應一個明確的 first-fit 搜尋結果：先釋放的第一頁，會再次成為掃描到的第一塊可用區域。
其他配置策略不一定保證同樣位址，但這份測試和我們目前的演算法一致。

還可以在實驗副本中，對同一筆配置連續呼叫兩次 free_pages()。
第二次應因配置紀錄不符而 Panic，不能讓可用頁數增加到 17。
這類故意觸發的錯誤請獨立執行，完成後保留正常通過的版本。

空間足夠，不代表連續空間足夠

假設空閒頁分散成四個單頁，要求一次配置三個連續頁面仍然可能失敗。
目前的 alloc_pages(n) 保證連續實體記憶體，因此有外部碎片的問題。
未來有分頁映射後，才有機會把不同實體頁組合成連續的虛擬範圍。

同樣地，只需要十幾個 bytes 卻配置整頁，頁內剩餘空間也會閒置。
今天先把配置粒度與邊界管理弄清楚，還沒有實作一般 malloc() 那樣的細粒度 heap。

今天新增 memory.h、memory.c 與 memory_test.c，修改 kernel.ld、kernel.c 與 Makefile。
建議 commit 訊息為：

day09: implement page allocator

Day 10 會用這個配置器替兩個核心行程各自準備堆疊，讓「這塊 RAM 屬於誰」開始有具體對象。

參考資料

• Silberschatz、Galvin、Gagne，《Operating System Concepts》第 10 版，第 9.3.1 節，pp. 360–362，Page、Frame 與碎片
• OS in 1,000 Lines：記憶體分配
• QEMU：RISC-V virt platform