mallocとfreeの実装

ガベージコレクションのアルゴリズムと実装の参考資料でもあるminigcのmalloc/free部分の実装を抜き出して、自分でも書いてみました。sbrk(2)は呼び出すたびに、ヒープ領域を伸ばします。my_freeは、ヒープ領域を解放するわけではなく、my_freeしたヒープ領域を再利用できるようにfree_listに追加しています。my_malloc(size_t req_size)はfree_listの中からreq_size以上のメモリ領域を探します。見つかった場合は、そこからreq_sizeだけ確保します。もしも、無い場合は必要な大きさだけ、ヒープ領域を確保してから、その領域をfree_listに追加(sbrkした領域をmy_freeする)してから検索し直します。ただし、はじめてmy_mallocを呼ぶとき(free_list==NULL)は、sbrkを使ってヒープ領域を確保してfree_listに追加してからreq_size以上のメモリ領域を探します。sbrkはunix系のシステムコールなので、windowsでは動きません。そこはまた調べてみようと思います。(gccなら動くみたいです。)

コード

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>
struct Header {
  size_t flags;
  size_t size;
  struct Header* next_free;
};
static struct Header* free_list = NULL;
#define PTR_SIZE (size_t)(sizeof (void*))
#define HEADER_SIZE (size_t)(sizeof (struct Header))
#define NEXT_HEADER(x) (struct Header*)((size_t)(x+1) + x->size)
#define ALIGN(x,a) ((x + (a-1)) & ~(a-1))
#define TINY_HEAP_SIZE 0x4000

struct Header* add_heap(size_t size) {
void* p;
struct Header* align_p;
  if(size < TINY_HEAP_SIZE)
    size = TINY_HEAP_SIZE;
  if((p = sbrk(PTR_SIZE + HEADER_SIZE + size)) == (void*)-1)
    return NULL;
  align_p = (struct Header*)p;
  align_p->flags = 0;
  align_p->size = size;
  align_p->next_free = align_p;
  return align_p;
}
void my_free(void*);
struct Header* grow(size_t req_size) {
struct Header *cp;
  if((cp = add_heap(req_size)) == NULL)
    return NULL;
  my_free((void *)(cp+1));
  return free_list;
}

void* my_malloc(size_t req_size) {
  req_size = ALIGN(req_size, PTR_SIZE);
  if(req_size <= 0)
    return NULL;
struct Header *p, *prevp;
  if((prevp = free_list) == NULL) {
    if((p = add_heap(TINY_HEAP_SIZE)) == NULL)
      return NULL;
    prevp = free_list = p;
  }
  for(p = prevp->next_free; ; prevp = p, p = p->next_free) {
    if(p->size >= req_size) {
      if(p->size == req_size) 
        prevp->next_free = p->next_free;
      else {
        p->size -= HEADER_SIZE + req_size;
        p = NEXT_HEADER(p);
        p->size = req_size;
      }
      return (void*)(p+1); 
    }
    if(p == free_list)
      if((p = grow(req_size)) == NULL)
        return NULL;
  }
  return NULL;
}
void my_free(void* p) {
struct Header *target, *hit;
  target = (struct Header*)p -1;
  hit = free_list;
  while(1) {
    if(hit < hit->next_free && (hit < target && target < hit->next_free))
      break;
    if(hit >= hit->next_free && (hit < target || hit->next_free > target))
      break;
    hit = hit->next_free;
  }
  free_list = hit;
  if(NEXT_HEADER(target) == free_list->next_free) {
    target->size += free_list->next_free->size + HEADER_SIZE;
    target->next_free = free_list->next_free->next_free;
  } else {
    target->next_free = free_list->next_free;
  }
  
  if(NEXT_HEADER(free_list) == target) {
    free_list->size += target->size + HEADER_SIZE; 
    free_list->next_free = target->next_free;
  } else {
    free_list->next_free = target;
  }
}
void free_list_reset(void) {
struct Header* iter = free_list->next_free;
int i = 0;  
  if(NEXT_HEADER(free_list) != iter)i++;
  while(iter != free_list) {
    free_list->size += iter->size + HEADER_SIZE;
    struct Header* next = iter->next_free;
    if(NEXT_HEADER(iter) != iter->next_free)i++;
    iter = iter->next_free;
  }
  assert(i == 1);
  free_list->next_free = free_list;
}
void test(void);
int main(void) {
  test();
  return 0;
}

void align_test(void) {
size_t i, j;  
  for(i = 0; i < 10; i++)
    for(j = 1 + PTR_SIZE * i; j <= PTR_SIZE * (i+1); j++)
      assert(PTR_SIZE* (i+1) == ALIGN(j, PTR_SIZE));
}
void my_malloc_test1(void) {
// case:free_list == NULL
  assert(NULL == free_list);
  assert(NULL == my_malloc(0));
char* str = (char*)my_malloc(5);
  strcpy(str, "hello");
  assert(!strcmp("hello", str));
struct Header* hdr = (struct Header*)str -1;
  assert(ALIGN(5, PTR_SIZE) == hdr->size);
  assert(NEXT_HEADER(free_list) == hdr);
  assert(TINY_HEAP_SIZE - ALIGN(5, PTR_SIZE) - HEADER_SIZE == free_list->size);
  my_free(str);
  assert(TINY_HEAP_SIZE  == free_list->size);
// case: free_list != NULL

char* str2 = (char*)my_malloc(5);
  assert(!strcmp("hello", str2));
  strcpy(str2, "world");
  assert(!strcmp("world", str2));
  assert(TINY_HEAP_SIZE - ALIGN(5, PTR_SIZE) - HEADER_SIZE == free_list->size);

  my_free(str2);
  assert(TINY_HEAP_SIZE  == free_list->size);
}

void my_malloc_test2(void) {
// case: free_list != NULL
  assert(NULL != free_list);
char *str1, *str2;
  str1 = (char*) my_malloc(5);
  strcpy(str1, "hello");  
  str2 = (char*) my_malloc(5);
  strcpy(str2, "world");
  assert(!strcmp("hello", str1));
  assert(!strcmp("world", str2));
  assert(TINY_HEAP_SIZE - 2*ALIGN(5, PTR_SIZE) - 2*HEADER_SIZE == free_list->size);
  my_free(str1);
  struct Header* hdr1 = (struct Header*)str1 -1;
  assert(free_list->next_free == hdr1);
  assert(hdr1->next_free == free_list);
  assert(TINY_HEAP_SIZE - 2*ALIGN(5, PTR_SIZE) - 2*HEADER_SIZE == free_list->size);
  assert(ALIGN(5, PTR_SIZE) == hdr1->size);
  my_free(str2);
  assert(TINY_HEAP_SIZE == free_list->size);
}

void my_malloc_test3(void) {
{
//  assert(NULL != free_list);
void *p1, *p2, *p3;
  p1 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  p2 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  p3 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  assert(TINY_HEAP_SIZE/4 == free_list->size);
  my_free(p2);
  struct Header* old = free_list;
  my_free(p1);
  assert(old->next_free == free_list);
  assert(free_list->next_free == old);
  assert((size_t)((struct Header*)p2 -1) == (size_t)free_list);
  assert(TINY_HEAP_SIZE/2 - HEADER_SIZE == free_list->size);
  my_free(p3);
  assert(old == free_list);
  assert(old->next_free == old);
  assert(TINY_HEAP_SIZE == free_list->size);
}

{
//  assert(NULL != free_list);
void *p1, *p2, *p3, *p4;
  p1 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  p2 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  p3 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  p4 = my_malloc(TINY_HEAP_SIZE/4 - HEADER_SIZE);
  assert(0 == free_list->size);
  struct Header* old = free_list;
  my_free(p3);
  assert(old == free_list);
  assert((size_t)((struct Header*)p3 -1) == (size_t)free_list->next_free);
  assert((size_t)((struct Header*)p3 -1)->next_free == (size_t)free_list);
  my_free(p1);
  assert((size_t)((struct Header*)p3 -1) == (size_t)free_list);
  assert((size_t)((struct Header*)p1 -1) == (size_t)free_list->next_free);
  assert((size_t)old == (size_t)free_list->next_free->next_free);
  assert(TINY_HEAP_SIZE/4 - HEADER_SIZE == free_list->size);
  my_free(p4);
  assert(old == free_list);
  assert(TINY_HEAP_SIZE/2 == free_list->size);
  assert(TINY_HEAP_SIZE/4 - HEADER_SIZE == ((struct Header*)p1 -1)->size);
  my_free(p2);
  assert(old == free_list);
  assert(TINY_HEAP_SIZE == free_list->size);
}
}
void reuse_heap_test(void) {
void *p1, *p2, *p3, *p4;
  p1 = my_malloc(10);
  p2 = my_malloc(20);
  p3 = my_malloc(30);
  my_free(p2);
  p4 = my_malloc(20);
  assert(p4 == p2);
  my_free(p1);
  my_free(p3);
  my_free(p4);
  assert(TINY_HEAP_SIZE == free_list->size);
}
void grow_test(void) {
  assert(TINY_HEAP_SIZE == free_list->size);
  struct Header* hdr = grow(ALIGN(10, PTR_SIZE));
  assert(hdr->next_free->size == TINY_HEAP_SIZE);
  void *p;
  p = my_malloc(TINY_HEAP_SIZE + 100);
  assert(hdr->next_free == free_list);
  assert(TINY_HEAP_SIZE + 100 == ((struct Header*)p -1)->size);
  my_free(p);
}
void test(void) {
  align_test();
  my_malloc_test1();
  my_malloc_test2();
  my_malloc_test3();
  reuse_heap_test();
  grow_test();
}