【DIY kernel】為context switch做準備, 實作Task

這部分程式已經提交到gitHub上

故不將所有程式碼貼在網誌上瞜~~



task 共有四種狀態，分別是 ready, running, block(類似在休息, 記憶體不會被釋放), close

目前無法真正的將cpu使用權切換給其他task使用

只能修改各task的狀態

等下次將context switch實作之後才會有作用

這部分程式主要就是在這些狀態中切換

所以需要

list_t ready_list[MAX_PRIO];
list_t blocked_list;
list_t termination_list;

這三種list紀錄某種狀態下有哪些task

然後用

u32int task_table[MAX_TASK_NUM];

來放所有task, 有task設為1其餘為0 (所以這個os只能run MAX_TASK_NUM 個 task)

最後還有一個

u8int prioExistFlag[MAX_PRIO];

這是為了取出priority最高的 ready_list 所建的table (array)。

task 的結構如下


struct task{
node_t node;

void *sp;
void *entry;
void *parameter;
void *stack_addr;
u16int stack_size;

u8int priority;

u32int init_tick;
u32int remaining_tick;

u32int task_id;
TASK_STATE state;
char name[NAME_MAXLENTH];

timer_t *timer;
};

比較特別的是 void *sp (stack point)這指向 task 的 stack

void *entry 這指向這task要做的事情的function

void *stack_addr 就是指向stack的開頭摟

總共要實作的function有這些


task_t *task_create( const char *name,
void (*entry)(void *parameter),
void *parameter,
u16int stackSize,
u8int priority,
u16int tick);
s8int task_start( task_t *task );
s8int task_delete( task_t *task );
void task_yield();
s8int task_sleep( u32int tick );
s8int task_suspend( task_t *task );
s8int task_resume( task_t *task );
void task_remove( task_t *task );
void task_addReady( task_t *task );
task_t *ready_task( u8int priority );
u8int get_top_prio();
u32int get_task_id();

static void task_timeout(void *parameter);

在task_create裡


task_t *task_create( const char *name,
void (*entry)(void *parameter),
void *parameter,
u16int stackSize,
u8int priority,
u16int tick){

task_t *task;
u32int *stackAddr;
u32int task_id;

task_id = get_task_id();
if( task_id < 0 ){
return NULL;
}

task = (task_t *)kmalloc(sizeof(task_t));
if(task == NULL)
return NULL;

stackAddr = (void *)kmalloc(stackSize);
if( stackAddr == NULL ){
kfree(task);
return NULL;
}

for( int temp=0; temp<NAME_MAXLENTH; temp++ ){
task->name[temp] = name[temp];
}

task->task_id = task_id;
task->entry = (void *)entry;
task->parameter = parameter;
task->stack_addr = stackAddr;
task->stack_size = stackSize;
task->node.next = NULL;
task->node.prev = NULL;

task->init_tick = tick;
task->remaining_tick = tick;
task->priority = priority;
task->sp = (void *)( (void *)stackAddr + stackSize -4 );

memset( (u8int *)task->stack_addr, '?', task->stack_size );
task->sp = (void *)init_stack(task->sp,
 task->entry,
 task->parameter);
task_table[task->task_id] = 1;

task->timer = timer_create(task->name,
  task_timeout,
  task,
  0,
  SET_ONESHOT);

return task;
}

首先會取得task_id

就是從task_table裡取出value是0的key

之後就是初始化的動作

其中的init_stack在下次context switch時再一併講解

其餘工具的演算法或流程也不難

從一個狀態切換到下個狀態主要是

從原本的list裡移除(critical region)再加入另一個狀態的list中

詳細程式碼請至gitHub下載或線上參考~~

https://github.com/herb123456/DIY_Kernel

============================================

後來想想，還是直接在這寫下 init_stack 吧XD

init_stack在 stack.c 裡實作

是每個 task 專屬的一塊記憶體

裡面放的東西長這樣:

之後context switch 時 會將程式狀態存在這塊stack裡

詳細流程會在下一篇在講~~

【DIY kernel】實作 timer

timer 要做的事情也不難

了解整個過程之後code就比較好理解

首先 timer create 之後就將 timer 加入 timer_list

之後在每100個clock發生的interrupt內檢查timer_list

是否有timeout的timer和不是periodic mode(週期模式)的timer

發生timeout就執行 timeout handler

不是periodic mode 就設為inactive

然後還有額外的控制函數

timer_stop, timer_delete, timer_control(可控制timer mode)

接下來的code只會在比較特別的地方做講解!

先定義 timer 的結構和狀態

#define NAME_MAXLEN 20

struct timer{

node_t node;

char name[NAME_MAXLEN];

u8int flag;

void (*timeout_func)(void *parameter);

void *parameter;

u32int init_tick;

u32int timeout_tick;

};

typedef struct timer timer_t;

#define ACTIVATED 1<<0

#define PERIODIC 1<<1

typedef enum{

SET_TIME = 0,

GET_TIME,

SET_ONESHOT,

SET_PERIODIC

} TIMER_CMD_TYPE;

接下來就實作會用到的 function

void init_system_timer(){

init_list( &timer_list );

}

timer_t *timer_create( const char *name, void (*timeout)(void *parameter), void *parameter, u32int time, TIMER_CMD_TYPE flag ){

timer_t *timer = kmalloc( sizeof(timer_t) );

if( timer == NULL ){

kprintf("timer == NULL \n");

return NULL;

}else{

kprintf("timer != NULL \n");

}

timer_init(timer, name, timeout, parameter, time, flag);

return timer;

}

void timer_init( timer_t *timer, const char *name, void(*timeout)(void *parameter), void *parameter, u32int time, TIMER_CMD_TYPE flag ){

if( timer == NULL )

return;

switch(flag){

case SET_ONESHOT:

timer->flag &= ~PERIODIC;

break;

case SET_PERIODIC:

timer->flag |= PERIODIC;

break;

}

timer->flag &= ~ACTIVATED;

timer->timeout_func = timeout;

timer->parameter = parameter;

timer->timeout_tick = 0;

timer->init_tick = time;

}

timer_list 是個 list_t 型態的全域變數

list_t timer_list;

接著是實作 timer_start (將 timer 丟進 timer_list裡，並按照timeout大小排列)

和 timer_check (檢查timer_list是否有timeout的timer)

s8int timer_start( timer_t *timer ){

if( timer == NULL || timer->flag & ACTIVATED )

return ERROR;

timer_t *ptimer;

node_t *pnode, *last_node;

timer->timeout_tick = get_tick() + timer->init_tick;

disableInterrupt();

if( !is_Empty( &timer_list ) ){

pnode = first_node( &timer_list );

last_node = &timer_list.tail;

while( pnode != last_node || pnode == NULL ){

ptimer = (timer_t *)pnode;

if( ptimer->timeout_tick > timer->timeout_tick ){

append_list(pnode->prev, &timer->node);

break;

}else{

pnode = pnode->next;

}

}

if( pnode == last_node ){

insert_rear(&timer_list, &timer->node);

}

}else{

insert_rear(&timer_list, &timer->node);

}

enableInterrupt();

timer->flag |= ACTIVATED;

print_list(&timer_list);

return OK;

}

void timer_check(){

timer_t *ptimer;

node_t *pnode;

u32int current_tick = get_tick();

disableInterrupt();

if( !is_Empty(&timer_list) ){

pnode = first_node(&timer_list);

while( pnode != &timer_list.tail ){

ptimer = (timer_t *)pnode;

if( current_tick >= ptimer->timeout_tick ){

remove_node(&ptimer->node);

ptimer->timeout_func(ptimer->parameter);

if( (ptimer->flag & PERIODIC) && (ptimer->flag & ACTIVATED) ){

ptimer->flag &= ~ACTIVATED;

print_list(&timer_list);

timer_start(ptimer);

}else{

ptimer->flag &= ~ACTIVATED;

}

current_tick = get_tick();

pnode = pnode->next;

}else{

//kprintf("while break \n");

break;

}

}

}

enableInterrupt();

}

接下來是工具

s8int timer_stop( timer_t *timer ){

if( timer == NULL || !(timer->flag & ACTIVATED) )

return ERROR;

timer->flag &= ~ACTIVATED;

disableInterrupt();

remove_node(&timer->node);

enableInterrupt();

return OK;

}

s8int timer_delete( timer_t *timer ){

if( timer == NULL )

return ERROR;

disableInterrupt();

remove_node(&timer->node);

enableInterrupt();

kfree(timer);

return OK;

}

s8int timer_control( timer_t *timer, TIMER_CMD_TYPE cmd, u32int arg ){

if( timer == NULL )

return ERROR;

switch( cmd ){

case SET_TIME:

timer->init_tick = arg;

break;

case GET_TIME:

return timer->init_tick;

case SET_ONESHOT:

timer->flag &= ~PERIODIC;

break;

case SET_PERIODIC:

timer->flag |= PERIODIC;

break;

default:

return ERROR;

}

return OK;

}

我在gitHub上開了個 project

有興趣的人可以去看看

https://github.com/herb123456/DIY_Kernel

【DIY kernel】實作簡單資料結構 - Doubly Linked List (雙向鏈結串列)

借用老師投影片的圖~~

實作 timer 之前必須要有基本的資料結構

這部分跟寫作業一樣

只要有修過資料結構的都有寫過

所以就不贅述細節了

先定義 list 和 node 的結構



struct node
{
struct node *next;
struct node *prev;
};
typedef struct node node_t;

struct list
{
node_t head;
node_t tail;
};
typedef struct list list_t;



接下來就是實作double linked list需要用到的方法：

//判斷是否為第一個node
u8int isHeadnode (node_t *node);
//判斷是否為中間的node

u8int isInternalNode (node_t * node);
//判斷是否為最後一個node
u8int isTailNode (node_t * node);
//初始化List
void init_list (list_t * list);
//取得第一個node
node_t *first_node (list_t * list);
//取得最後一個node
node_t *last_node(list_t * list);
//判斷該list是否為空
u8int is_Empty (list_t * list);
//將node依附在某個node之後
void append_list (node_t * before, node_t * node);
//將node插入最前面
void insert_front (list_t * list, node_t * node);
//將node插入最後面
void insert_rear (list_t * list, node_t * node);
//將node刪除
void remove_node (node_t * node);
//將第一個node刪除
node_t *remove_firstNode (list_t * list);
//將最後一個node移除
node_t *remove_lastNode (list_t * list);

以下附上投影片上的程式碼


u8int isHeadNode (node_t *node){
return (node != NULL) && (node->prev == NULL) && (node->next != NULL);
}

u8int isInternalNode (node_t *node){
return (node != NULL) && (node->prev != NULL) && (node->next != NULL);

}

u8int isTailNode (node_t *node){
return (node != NULL) && (node->prev != NULL) && (node->next == NULL);
}

u8int is_Empty (list_t *list){
return (list->head.next == &list->tail);
}

void init_list (list_t *list){
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}

node_t *first_node (list_t *list){
if (is_Empty (list))
return NULL;
return list->head.next;
}

node_t *last_node (list_t *list){
if (is_Empty (list))
return NULL;
return list->tail.prev;
}

void append_list (node_t *before, node_t *node){
if( before->next != NULL )
before->next->prev = node;
node->prev = before;
node->next = before->next;
before->next = node;
}

void insert_front (list_t *list, node_t *node){
append_list( &list->head, node );
}

void insert_rear (list_t *list, node_t *node){
append_list( list->tail.prev, node );
}

void remove_node (node_t *node){
if (isInternalNode (node)){
node->prev->next = node->next;
node->next->prev = node->prev;
node->next = NULL;
node->prev = NULL;
}
}

node_t *remove_firstNode (list_t *list){
node_t *node = first_node (list);
if (node != NULL)
remove_node (node);

return node;
}

node_t *remove_lastNode (list_t *list){
node_t *node = last_node (list);
if (node != NULL)
remove_node (node);

return node;
}



【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了

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

要怎麼配置和回收記憶體

就看個人要怎麼實作了

【DIY Kernel】環境建置

這學期修了一門 "作業系統工程" 的課
教的是自己製作一個OS Kernel
這是一門有趣又好玩但是很難的課程!!
以後每個禮拜都要把筆記寫下來
免得太困難的部分未來會忘掉

先補上第一次上課的內容
也就是環境建置
這篇有可能會用到的工具可以在此下載

首先要熟悉電腦開機流程
可參考
http://people.cs.nctu.edu.tw/~huangmc/works/web/Boot_x86/Boot_x86.html

實際上
不可能真的修改boot loader
一直重開機會很耗時
所以用虛擬的環境bochs來模擬x86環境
http://bochs.sourceforge.net/
選擇GRUB當boot loader

並且使用VFD(Virtual Floopy Disk)來製作與修改磁碟片映像檔

還需要一個已經具有GRUB開機管理程式的印象檔
來製作自己的印象檔(這步驟可省略，可直接拿已有寫入MBR的Image來修改)

並使用cygwin模擬Linux環境
並選擇安裝
gcc
nasm
automake
用來編譯kernel

工具都準備好之後
就可以開始建置開發環境了

製作自己的可開機印象檔

首先將bochs和vfd解壓縮與安裝好
開啟vfd(Vista以上請使用管理員身分執行)
建立一個空的image檔案

這時可以打開A磁碟
發現裡面是空的
之後將GRUB解壓縮丟進去

然後存檔

之後開啟Bochs
Edit Option 選擇 Disk & Boot
再選旁邊的Edit

Floopy Option 選擇已經可開機 Image (floopy.img)

然後按OK和Start
順利的話可看見grub commend line

按左上角A磁碟的圖示
修改掛載的A磁碟 Image 為我們剛製作的Image

就可以看見bochs出現掛載的訊息
這時我們在grub輸入 setup (fd0)
這樣就完成自己製作的可開機印象檔了

製作menu.lst

menu.lst可說是grub的開機選單

方便我們可以製作多個kernel並選擇要用哪個kernel啟動

首先掛載剛剛製作好的Image

並在A:\boot\grub

下建立一個純文字檔案

並輸入

title MyOS
root (fd0)
kernel /boot/kernel.elf
boot

title就是要顯示的名稱
root 是kernel 所在的根目錄
kernel 是以root為基礎的 kernel 相對位置

可以依據自己的喜好來設定

編譯Kernel

老師對我們很好

提供了一個最基礎的kernel

以後就方便在上面加東西啦

用管理員身分打開cygwin(這樣就等於有root權限)

進入放著原始kernel的資料夾

發現已經有Makefile

所以直接輸入指令 make

即可編譯

(kernel的source code細節略過)

編號成功後發現多了一個檔案叫kernel.elf

把這個kernel.elf丟進掛載好的Image裡

對應menu.lst的路徑

重新啟動bochs就可以用自己編譯的kernel開機了!

建立自動執行檔

目前為止，整個流程大致如下

編譯完kernel

複製kernel.elf到印象檔裡

然後儲存印象檔

開啟bochs

選擇disk&boot

選擇我們的印象檔

開機

如果每次編譯完都要執行這一串步驟

肯定會很累

所以要寫一個屬於自己的自動執行檔

簡化以上的步驟

首先在make完之後直接將kernel.elf複製到A磁碟

所以修改Makefile

在objcopy下一行加入

cp -a kernel.elf /cygdrive/a/boot/kernel.elf

再另外寫一個run.sh

要做的事有

1. 存檔

2. 用bochs開啟印象檔

#!/bin/bash

/your/vfd/path/vfd.exe save

/your/bochs/path/bochs -f bochsrc.bxrc -q

而bochsrc.bxrc則是從bochs選擇完你的Image

之後左邊有個Save

可以把設定儲存起來

這樣就完成自動執行的腳本了