【DIY kernel】簡單實作 malloc, free

其實建置環境的下一堂課是在講 GDT & IDT

但實在太深奧

憑我的智商還很難自己寫一篇文章來介紹~~

所以自動跳過XD

改來實作比較有趣的吧

平常我們在 C/C++ 裡所使用的 malloc 

功能是像 os 要一塊記憶體空間

參數是這塊空間的大小

則 free 就是把給出的空間還給 os

現在就要來實作這個功能

下圖是整個工作流程示意圖

從heap.h開始看我們需要哪些功能


#ifndef __HEAP_H__
#define __HEAP_H__

#define BLOCKHEAD_SIGNATURE 0x0000F00D
typedef struct blockHead {
u32int signature;
u8int   allocated;
u32int size;
struct blockHead *next;
struct blockHead *prev;
} blockHead_t;

blockHead_t *gHeapBase;

bool init_heap(u32int heapStarAddress, u32int size);
void *kmalloc( u32int requireSize );
bool kfree(void *block);
bool compactedHeap( blockHead_t *currentHeadPtr );
void compact_forward( blockHead_t *currentHeadPtr );
void compact_backward( blockHead_t *currentHeadPtr );

#endif


我們定義了 blockHead 用來紀錄每塊分配記憶體的資訊

和 BLOCKHEAD_SIGNATURE 來識別這塊記憶體是否為我分配的

還有一個 gHeapBase 在 init_heap 時會將它指向記憶體最頂端

剩下的功能就是分配、釋放記憶體

和釋放之後合併附近區塊記憶體的功能

首先在kernel.c裡我們要呼叫初始化記憶體的函式

u32int memsize = (mboot_ptr->mem_lower + mboot_ptr->mem_upper) * 1024; init_heap(end_address, memsize - end_address );

mboot_ptr 是從 kernel_start 傳進來的參數

是 GRUB 的 multiboot 在開機時從BIOS得來的系統資訊

在 asm 呼叫 kernel_start 時丟進去的參數

start:


    ;push esp ;stack location (GRUB doesn't tell us)
    ; Load multiboot information:
    mov esp, end+0x1000
    push    ebx


    ; Execute the kernel:
    cli                         ; Disable interrupts.
    call _kernelStart           ; call our main() function.
    jmp $                       ; Enter an infinite loop, to stop the processor
                                ; executing whatever rubbish is in the memory
                                ; after our kernel!


所以可以藉此了解整塊記憶體的大小

end_address 是 load 完這支 kernel 之後的位置

是從linker 得來的


/* Link.ld -- Linker script for the kernel - ensure everything goes in the */
/*            Correct place.  */
/*            Original file taken from Bran's Kernel Development */
/*            tutorials: http://www.osdever.net/bkerndev/index.php. */

ENTRY(start)
/*OUTPUT_FORMAT(elf32-i386)*/
SECTIONS
{

    .text 0x100000 :
    {
        code = .; _code = .; __code = .;
        *(.text)
        . = ALIGN(4096);
    }

    .data :
    {
        data = .; _data = .; __data = .;
        *(.data)
        *(.rodata)
        . = ALIGN(4096);
    }

    .bss :
    {
        bss = .; _bss = .; __bss = .;
        *(.bss)
        . = ALIGN(4096);
    }

    end = .; _end = .; __end = .;
}



接下來看 init_heap 做了些什麼


bool init_heap(u32int heapStarAddress, u32int size){
if( gHeapBase != NULL )
return FALSE;

gHeapBase = (blockHead_t *)heapStarAddress;
gHeapBase->allocated = FALSE;
gHeapBase->signature = BLOCKHEAD_SIGNATURE;
gHeapBase->next = NULL;
gHeapBase->prev = NULL;
gHeapBase->size = size - sizeof(blockHead_t);

return TRUE;
}


第一行先判斷是否重複呼叫 init_heap

如果曾經呼叫過則 gHeapBase 就會指向最頂端的 blockHead 而不是NULL

如果沒呼叫過就初始化 gHeapBase

之後若有人呼叫 kmalloc, kernel 就要回傳分配的記憶體位置

void *kmalloc( u32int requireSize ){
blockHead_t *blockPtr = gHeapBase;
blockHead_t *newBlock;

while( blockPtr != NULL ){
if( !blockPtr->allocated && blockPtr->size >= requireSize ){ //check size enough
blockPtr->allocated = TRUE;
if( (blockPtr->size - requireSize) > sizeof(blockHead_t) ){ //check block head size enough
// ______
// |____| ->blockPtr
// | |
// | | ->requireSize
// |____|
// |____| ->newBlock
// | |
// | |
// | | ->newBlock->size
// | |
// | |
// |____|
//

newBlock = (void *)blockPtr + sizeof(blockHead_t) + requireSize;
newBlock->size = blockPtr->size - requireSize - sizeof(blockHead_t);
newBlock->allocated = FALSE;
newBlock->signature = BLOCKHEAD_SIGNATURE;
newBlock->prev = blockPtr;
newBlock->next = blockPtr->next;

if( blockPtr->next != NULL ){
blockPtr->next->prev = newBlock;
}
blockPtr->next = newBlock;
blockPtr->size = requireSize;

}

break;
}

blockPtr = blockPtr->next;
}

return (blockPtr != NULL) ? ( (void *)blockPtr + sizeof(blockHead_t) ) : NULL;
}



一開始先宣告一個指向開頭的指標

和將要新加區域的指標

然後用while從頭開始找 沒有被配置過 而且空間也夠大 的區塊
if( !blockPtr->allocated && blockPtr->size >= requireSize )

如果沒有就指向下一個區塊的 blockHead

若很幸運的有這個區塊

則把這個區塊設為已被配置過
blockPtr->allocated = TRUE;

再判斷該空間是否配置完後有剩餘空間建立新的 blockHead
if( (blockPtr->size - requireSize) > sizeof(blockHead_t) )

如果不夠，則不建立新的 blockHead 並把目前這個 blockHead 位置回傳

如果夠，則建立新的 blockHead (新的 blockHead 是新的未配置的區域)

newBlock = (void *)blockPtr + sizeof(blockHead_t) + requireSize;
newBlock->size = blockPtr->size - requireSize - sizeof(blockHead_t);
newBlock->allocated = FALSE;
newBlock->signature = BLOCKHEAD_SIGNATURE;
newBlock->prev = blockPtr;
newBlock->next = blockPtr->next;

if( blockPtr->next != NULL ){
blockPtr->next->prev = newBlock;
}
blockPtr->next = newBlock;
blockPtr->size = requireSize;


free 的部分比較簡單

就是把已配置的旗標，改成FALSE(未配置)即可

最後再合併上下未配置的區塊成為一個大的區塊


bool kfree(void *block){
blockHead_t *headPtr;

if(block == NULL)
return FALSE;

if( (void *)block < (void *)gHeapBase ){
return FALSE;
}

//
// |----| -> headPtr
// | |      | sizeof(blockHead_t)
// |----| -> block
// | |
// | |
// | | -> data
// | |
// | |
// |    |
// | |
// |----|
//

headPtr = (blockHead_t *)( (void *)block - sizeof(blockHead_t) );
if( headPtr->signature != BLOCKHEAD_SIGNATURE )
return FALSE;

headPtr->allocated = FALSE;

return compactedHeap(headPtr);
}


傳進來的參數是指向 data 的位置

所以要設置 blockHead 的 allocated 要先把位置往上移一個 blockHead 的大小
headPtr = (blockHead_t *)( (void *)block - sizeof(blockHead_t) );

並且判斷 signature 是否跟我設的一致
if( headPtr->signature != BLOCKHEAD_SIGNATURE )

如果都符合，就把 allocated 設為 FALSE

並呼叫合併函式 compactedHeap(headPtr);


bool compactedHeap( blockHead_t *currentHeadPtr ){
if( currentHeadPtr->next != NULL ){
compact_forward( currentHeadPtr );
}
if( currentHeadPtr->prev != NULL ){
compact_backward( currentHeadPtr );
}
}


判斷是否有上一個或下一個

有的話就進行合併


void compact_forward( blockHead_t *currentHeadPtr ){
// ______
// |____| -> currentHeadPtr
// | |
// | |   compact two blocks
// |____|
// |____| -> currentHeadPtr->next
// | |
// | |
// | |
// | |
// | |
// |____|
// |____|
// | |
// | |
// | |
// |____|
//
blockHead_t *nextPtr;
nextPtr = currentHeadPtr->next;
if( nextPtr != NULL && !nextPtr->allocated && nextPtr != currentHeadPtr ){
currentHeadPtr->next = nextPtr->next;
if( nextPtr->next != NULL ){
nextPtr->next->prev = currentHeadPtr;
}
currentHeadPtr->size = currentHeadPtr->size + nextPtr->size + sizeof(blockHead_t);
}
}

void compact_backward( blockHead_t *currentHeadPtr ){
blockHead_t *prevPtr;
prevPtr = currentHeadPtr->prev;
if( prevPtr != NULL && !prevPtr->allocated && prevPtr != currentHeadPtr ){
prevPtr->next = currentHeadPtr->next;
if( currentHeadPtr->next != NULL ){
currentHeadPtr->next->prev = prevPtr;
}
prevPtr->size = prevPtr->size + currentHeadPtr->size + sizeof(blockHead_t);
}
}



至此就完成簡單的 malloc和free了

當然這只是很基礎的演算法

要怎麼配置和回收記憶體

就看個人要怎麼實作了