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;
//判斷是否為第一個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;
}
#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
u32int memsize = (mboot_ptr->mem_lower + mboot_ptr->mem_upper) * 1024;
init_heap(end_address, memsize - end_address );
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!
/* 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 = .;
}
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;
}
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;
}
if( !blockPtr->allocated && blockPtr->size >= requireSize )
blockPtr->allocated = TRUE;
if( (blockPtr->size - requireSize) > sizeof(blockHead_t) )
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;
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);
}
headPtr = (blockHead_t *)( (void *)block - sizeof(blockHead_t) );
if( headPtr->signature != BLOCKHEAD_SIGNATURE )
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);
}
}
