245 lines
8.0 KiB
C
245 lines
8.0 KiB
C
#include "c_Buddy.h"
|
||
#include <stdlib.h>
|
||
#include <stdio.h>
|
||
#include <stdalign.h> // C11 標準
|
||
#include <c_Memory.h>
|
||
|
||
// 2. 測試用例函數宣告
|
||
void test_buddy_basic_alloc();
|
||
void test_buddy_alignment();
|
||
void test_buddy_oom();
|
||
void test_buddy_coalescing();
|
||
void test_1024(void);
|
||
|
||
int main(int argc, char** argv){
|
||
printf("--- 開始執行 c_Buddy_t 夥伴分配器測試 ---\n");
|
||
|
||
test_buddy_basic_alloc();
|
||
test_buddy_alignment();
|
||
test_buddy_oom();
|
||
test_buddy_coalescing();
|
||
test_1024();
|
||
printf("--- 所有測試用例通過！ ---\n");
|
||
return 0;
|
||
}
|
||
|
||
void c_Buddy_PrintStatus(c_Buddy_t *b) {
|
||
if (!b || !b->head || !b->tail) {
|
||
printf("[Buddy] 錯誤：分配器尚未初始化或為空指標。\n");
|
||
return;
|
||
}
|
||
|
||
printf("\n=================== Buddy Allocator Status ===================\n");
|
||
printf("總記憶體範圍: %p ~ %p\n", (void*)b->head, (void*)b->tail);
|
||
printf("最小對齊基準 (Alignment): %d 位元組\n", b->alignment);
|
||
printf("--------------------------------------------------------------\n");
|
||
printf("%-5s | %-16s | %-12s | %-10s\n", "編號", "區塊記憶體位址", "區塊大小(Size)", "狀態");
|
||
printf("--------------------------------------------------------------\n");
|
||
|
||
c_BuddyBlock_t *curr = b->head;
|
||
int block_index = 0;
|
||
int total_free = 0;
|
||
int total_allocated = 0;
|
||
|
||
// 使用與之前相同的單指針步進遍歷
|
||
while (curr < b->tail) {
|
||
printf("[%3d] | %p | %-12d(%dKB) | %s\n",
|
||
block_index++,
|
||
(void*)curr,
|
||
curr->size,
|
||
curr->size/1024,
|
||
curr->is_free ? "FREE (空閒)" : "ALLOCATED (已佔用)");
|
||
|
||
if (curr->is_free) {
|
||
total_free += curr->size;
|
||
} else {
|
||
total_allocated += curr->size;
|
||
}
|
||
|
||
// 精確前進到下一個區塊
|
||
curr = (c_BuddyBlock_t *)((uint8_t *)curr + curr->size);
|
||
}
|
||
|
||
printf("--------------------------------------------------------------\n");
|
||
printf("摘要統計：已使用: %d 總位元組 | 剩餘空閒: %d 總位元組\n", total_allocated, total_free);
|
||
printf("==============================================================\n\n");
|
||
}
|
||
|
||
#define KB 1024
|
||
|
||
void test_1024(void) {
|
||
void* block = c_Memory_Aligned_Alloc(1024*KB, 8, __FILE__, __LINE__);
|
||
|
||
c_Buddy_t buddy;
|
||
c_Buddy_Init(&buddy, block, 1024*KB, 8);
|
||
|
||
printf("Step 1: Alloc A=70KB\n");
|
||
void* A = c_Buddy_Alloc(&buddy, 70*KB);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 2: Alloc B=35KB\n");
|
||
void* B = c_Buddy_Alloc(&buddy, 35*KB);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 3: Alloc C=80KB\n");
|
||
void* C = c_Buddy_Alloc(&buddy, 80*KB);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 4: Free A\n");
|
||
c_Buddy_Free(&buddy, A);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 5: Alloc D=60KB\n");
|
||
void* D = c_Buddy_Alloc(&buddy, 60*KB);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 6: Free B\n");
|
||
c_Buddy_Free(&buddy, B);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 7: Free D\n");
|
||
c_Buddy_Free(&buddy, D);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 8: Free C\n");
|
||
c_Buddy_Free(&buddy, C);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 9: Alloc E=600KB\n");
|
||
void* E = c_Buddy_Alloc(&buddy, 600*KB); // 实际分配 1024KB
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
printf("Step 10: Free E\n");
|
||
c_Buddy_Free(&buddy, E);
|
||
c_Buddy_PrintStatus(&buddy);
|
||
|
||
c_Memory_Aligned_Free(block, __FILE__, __LINE__);
|
||
}
|
||
|
||
// ==========================================
|
||
// 測試用例 1：基礎初始化與 2 的冪次方裂變分配
|
||
// ==========================================
|
||
void test_buddy_basic_alloc() {
|
||
printf("[測試] 基礎裂變分配...\n");
|
||
|
||
// 建立 1024 位元組的底層記憶體，對齊設為 8
|
||
uint8_t* backing_buffer = (uint8_t*)malloc(1024);
|
||
c_Buddy_t buddy;
|
||
|
||
c_Buddy_Init(&buddy, backing_buffer, 1024, 8);
|
||
assert(buddy.alignment == 8);
|
||
|
||
// 請求分配 120 位元組（夥伴系統通常會向上對齊到 128 或包含 Block Header 的 2 的冪次方）
|
||
void* p1 = c_Buddy_Alloc(&buddy, 120);
|
||
assert(p1 != NULL);
|
||
|
||
// 再次分配相同大小，地址應當緊鄰第一個區塊（按 2 冪次步進）
|
||
void* p2 = c_Buddy_Alloc(&buddy, 120);
|
||
assert(p2 != NULL);
|
||
assert(p2 > p1);
|
||
|
||
// 清理記憶體池內部分配
|
||
c_Buddy_Free(&buddy, p1);
|
||
c_Buddy_Free(&buddy, p2);
|
||
free(backing_buffer);
|
||
printf(" => 基礎分配測試成功\n");
|
||
}
|
||
|
||
// ==========================================
|
||
// 測試用例 2：記憶體對齊（Alignment）邊界驗證
|
||
// ==========================================
|
||
void test_buddy_alignment() {
|
||
printf("[測試] 記憶體對齊要求...\n");
|
||
|
||
uint8_t* backing_buffer = (uint8_t*)C_ALIGNED_ALLOC(2048, 64);
|
||
c_Buddy_t buddy;
|
||
|
||
// 強制對齊要求為 64 位元組
|
||
c_Buddy_Init(&buddy, backing_buffer, 2048, 64);
|
||
|
||
void* p1 = c_Buddy_Alloc(&buddy, 100);
|
||
void* p2 = c_Buddy_Alloc(&buddy, 100);
|
||
|
||
assert(p1 != NULL);
|
||
assert(p2 != NULL);
|
||
|
||
// 驗證返回的記憶體地址是否符合 64 位元組對齊
|
||
assert(((uintptr_t)p1 % 64) == 0);
|
||
assert(((uintptr_t)p2 % 64) == 0);
|
||
|
||
c_Buddy_Free(&buddy, p1);
|
||
c_Buddy_Free(&buddy, p2);
|
||
C_ALIGNED_FREE(backing_buffer);
|
||
printf(" => 對齊邊界測試成功\n");
|
||
}
|
||
|
||
// ==========================================
|
||
// 測試用例 3：記憶體溢出（OOM）
|
||
// ==========================================
|
||
void test_buddy_oom() {
|
||
printf("[測試] 記憶體溢出邊界...\n");
|
||
|
||
uint8_t* backing_buffer = (uint8_t*)malloc(512);
|
||
c_Buddy_t buddy;
|
||
c_Buddy_Init(&buddy, backing_buffer, 512, 8);
|
||
|
||
// 嘗試分配超出整塊夥伴系統大小的記憶體
|
||
void* p1 = c_Buddy_Alloc(&buddy, 600);
|
||
assert(p1 == NULL);
|
||
|
||
// 分配剛好極限的記憶體（需扣除或包含 Header 空間，依實作而定）
|
||
void* p2 = c_Buddy_Alloc(&buddy, 256);
|
||
assert(p2 != NULL);
|
||
|
||
void* p3 = c_Buddy_Alloc(&buddy, 256);
|
||
// 由於 512 已被完全填滿，此時應觸發 OOM
|
||
void* p4 = c_Buddy_Alloc(&buddy, 8);
|
||
assert(p4 == NULL);
|
||
|
||
if (p2) c_Buddy_Free(&buddy, p2);
|
||
if (p3) c_Buddy_Free(&buddy, p3);
|
||
free(backing_buffer);
|
||
printf(" => OOM 邊界測試成功\n");
|
||
}
|
||
|
||
// ==========================================
|
||
// 測試用例 4：核心邏輯——夥伴自動合併（Coalescing）
|
||
// ==========================================
|
||
// 說明：當 A 和 B 互為夥伴區塊，且 A 分配出去後，若 A 與 B 均被釋放，
|
||
// 夥伴系統必須將兩者合併回原本更大的 2 的冪次方區塊。
|
||
void test_buddy_coalescing() {
|
||
printf("[測試] 夥伴區塊自動合併（Coalescing）...\n");
|
||
|
||
uint8_t* backing_buffer = (uint8_t*)malloc(1024);
|
||
c_Buddy_t buddy;
|
||
// 初始化一個 1024 總大小的區塊
|
||
c_Buddy_Init(&buddy, backing_buffer, 1024, 8);
|
||
|
||
// 1. 將其切碎：連續分配 4 個 256 的空間（假設總空間剛好能切 4 塊）
|
||
void* p1 = c_Buddy_Alloc(&buddy, 200); // 裂變為 256
|
||
void* p2 = c_Buddy_Alloc(&buddy, 200); // 裂變為 256
|
||
void* p3 = c_Buddy_Alloc(&buddy, 200); // 裂變為 256
|
||
void* p4 = c_Buddy_Alloc(&buddy, 200); // 裂變為 256
|
||
|
||
assert(p1 != NULL && p2 != NULL && p3 != NULL && p4 != NULL);
|
||
|
||
// 2. 此時剩餘空間為 0，嘗試分配 512 必然失敗
|
||
void* p_large_fail = c_Buddy_Alloc(&buddy, 500);
|
||
assert(p_large_fail == NULL);
|
||
|
||
// 3. 釋放相鄰的夥伴 p1 與 p2
|
||
c_Buddy_Free(&buddy, p1);
|
||
c_Buddy_Free(&buddy, p2);
|
||
|
||
// 4. 關鍵驗證：如果實作了自動合併，p1 和 p2 釋放後應融合成一個 512 的大區塊
|
||
// 此時再次申請 512 位元組（要求大小約 500），應該要能分配成功！
|
||
void* p_large_success = c_Buddy_Alloc(&buddy, 500);
|
||
assert(p_large_success != NULL);
|
||
|
||
// 清理剩餘記憶體
|
||
c_Buddy_Free(&buddy, p_large_success);
|
||
c_Buddy_Free(&buddy, p3);
|
||
c_Buddy_Free(&buddy, p4);
|
||
free(backing_buffer);
|
||
printf(" => 夥伴自動合併測試成功\n");
|
||
} |