といっても，まずは作成とテストがしやすいように，Linux上の普通のアプリとして実装してます．
大体動いているので，次はこれを，オレオレカーネルに移植します．
一応，ページ単位のメモリ管理は作ってあるので，移植時の変更点はinit_kmalloc_area()でmallocしているところを，
ページ単位でメモリ確保して，その領域をmalloc()，free()で使うような感じにします．
実装はこんな感じです．
メモリはバイト単位で指定しますが，内部的にはsizeof(void *)の倍数を確保してます．
こうすると，確保する領域の先頭アドレスの下位ビットが0になるので，そこをフラグに使ってます．
あとは，オレオレカーネルで使用するのはフラットなページ単位の領域で，今はフラットなメモリ領域を使ってるので，キャストが多用されてます．
メモリ上のデータをstruct kmalloc_header *にキャストして，色々やってます．
#include <stdio.h> #include <string.h> #include <stdlib.h> struct kmalloc_header { unsigned long prev; u_int32_t size; }; static char *kmalloc_area; static struct kmalloc_header *base; static struct kmalloc_header *next_free_area; #define KMALLOC_MAX_SIZE 512 #define KMALLOC_ALIGN sizeof(void *) #define KMALLOC_USED 0x01 int init_kmalloc_area(void) { unsigned long n; kmalloc_area = malloc(1024 * 2); if (!kmalloc_area) return -1; memset(kmalloc_area, 0, 1024 * 2); n = (unsigned long) kmalloc_area; n = (n &0xFFFFFFFFFFFFF000) + 0x400; base = (struct kmalloc_header *) n; base->size = 1024; base->prev = 0; next_free_area = base; printf("base address is 0x%x\n", base); return 0; } void *kmalloc(size_t size) { struct kmalloc_header *p; void *ret = NULL; if (size > KMALLOC_MAX_SIZE) return NULL; // Ceilling size = (size + sizeof(struct kmalloc_header) + KMALLOC_ALIGN - 1) & -KMALLOC_ALIGN; // printf("header size = %d : kmalloc size = %d\n", sizeof(struct kmalloc_header), size); p = next_free_area; do { if (p->size >= size) { next_free_area = (struct kmalloc_header *) ((char *) p + size); next_free_area->size = p->size - size; next_free_area->prev = (unsigned long) p; ((struct kmalloc_header *) next_free_area->prev)->prev = p->prev; // This address is using. next_free_area->prev ^= KMALLOC_USED; p->size = size; printf("free size is %d : alloc address is 0x%x : next_free_area->prev is 0x%x, prev->prev is 0x%x\n", next_free_area->size, p, next_free_area->prev, ((struct kmalloc_header *) next_free_area->prev)->prev); ret = (void *) ((char *) p + sizeof(struct kmalloc_header)); break; } else printf("next_free_area->size is %d. so not enough size to allocate %d byte(0x%x)\n", next_free_area->size, size, p); if (p->prev & KMALLOC_USED) { while (p->prev & KMALLOC_USED) p = (struct kmalloc_header *) (p->prev ^ KMALLOC_USED); } else { p = (struct kmalloc_header *) p->prev; } } while (p != base); return ret; } void kfree(void *ptr) { unsigned long addr = 0; struct kmalloc_header *p, *prev; struct kmalloc_header *tmp; u_int32_t new_size = 0; if (!ptr) return ; addr = (unsigned long) (((char *) ptr) - sizeof(struct kmalloc_header)); p = next_free_area; do { if ((p->prev ^ KMALLOC_USED) == addr) { p->prev ^= KMALLOC_USED; tmp = (struct kmalloc_header *) p->prev; printf("%d byte is going to be freed\n", tmp->size); // if next_free_area is free area, make big free area. if (next_free_area == p) { new_size = next_free_area->size + tmp->size; next_free_area = (struct kmalloc_header *) p->prev; next_free_area->size = new_size; } // if previous header isn't used, make big free area prev = (struct kmalloc_header *) tmp->prev; if (prev && !(prev->prev & KMALLOC_USED)) { new_size = prev->size + next_free_area->size; next_free_area = prev; next_free_area->size = new_size; } break; } p = (struct kmalloc_header *) (p->prev ^ KMALLOC_USED); } while (p != base); } int main(int argc, char **argv) { char *p, *pp; if (init_kmalloc_area()) { printf("init_kmalloc_area is failed\n"); exit(-1); } p = kmalloc(400); printf("ret is 0x%x\n", p); kfree(p); p = kmalloc(400); printf("ret is 0x%x\n", p); pp = kmalloc(400); printf("ret is 0x%x\n", pp); kfree(p); p = kmalloc(500); printf("ret is 0x%x\n", p); kfree(pp); p = kmalloc(500); printf("ret is 0x%x\n", p); return 0; }
追記：
オレオレカーネルに移植しました．
