simple_allocator

A simple, poorly-performing memory allocator
git clone https://git.bracken.jp/simple_allocator.git
Log | Files | Refs | Submodules | README | LICENSE

memory.c (3280B)


      1 #include "memory.h"
      2 
      3 #include <pthread.h>
      4 #include <stdio.h>
      5 #include <unistd.h>
      6 
      7 // An allocation header block.
      8 //
      9 // Allocation header blocks sit immediately before the allocated pointer in
     10 // memory and form a linked list staring at |head| and ending at |tail|.
     11 struct header_t {
     12   size_t size;
     13   struct header_t *next;
     14   unsigned char is_free;
     15 };
     16 
     17 static struct header_t *head, *tail;
     18 static pthread_mutex_t global_malloc_lock;
     19 
     20 // Returns the first free block of at least the specified size, or null if
     21 // no such block exists.
     22 static struct header_t *get_free_block(size_t size);
     23 
     24 // Print header struct debug dump.
     25 void print_header(struct header_t *header);
     26 
     27 static struct header_t *get_free_block(size_t size) {
     28   struct header_t *curr = head;
     29   while (curr) {
     30     if (curr->is_free && curr->size >= size)
     31       return curr;
     32     curr = curr->next;
     33   }
     34   return NULL;
     35 }
     36 
     37 void *malloc(size_t size) {
     38   size_t total_size;
     39   void *block;
     40   struct header_t *header;
     41 
     42   if (!size)
     43     return NULL;
     44 
     45   // Check for free previously-allocated block of the right size.
     46   pthread_mutex_lock(&global_malloc_lock);
     47   header = get_free_block(size);
     48   if (header) {
     49     header->is_free = 0;
     50     pthread_mutex_unlock(&global_malloc_lock);
     51     return (void*)(header + 1);
     52   }
     53 
     54   // If none, allocate a new block.
     55   total_size = sizeof(struct header_t) + size;
     56   block = sbrk((int)total_size);
     57   if (block == (void*)-1) {
     58     pthread_mutex_unlock(&global_malloc_lock);
     59     return NULL;
     60   }
     61 
     62   header = (struct header_t*)block;
     63   header->size = size;
     64   header->is_free = 0;
     65   header->next = NULL;
     66   if (!head)
     67     head = header;
     68   if (tail)
     69     tail->next = header;
     70   tail = header;
     71   pthread_mutex_unlock(&global_malloc_lock);
     72   return (void*)(header + 1);
     73 }
     74 
     75 void free(void *block) {
     76   if (!block)
     77     return;
     78 
     79   pthread_mutex_lock(&global_malloc_lock);
     80 
     81   // Get block header.
     82   struct header_t *header = (struct header_t*)block - 1;
     83 
     84   void *program_break = sbrk(0);
     85   if ((char*)block + header->size == program_break) {
     86     // If we're the last allocated block before brk, decrement it.
     87     if (head == tail) {
     88       head = tail = NULL;
     89     } else {
     90       for (struct header_t *p = head; p != NULL; p = p->next) {
     91         if (p->next == tail) {
     92           p->next = NULL;
     93           tail = p;
     94         }
     95       }
     96     }
     97     size_t total_size = sizeof(struct header_t) + header->size;
     98     sbrk(-(int)total_size);
     99     pthread_mutex_unlock(&global_malloc_lock);
    100     return;
    101   } else {
    102     // Otherwise, mark the block as free.
    103     header->is_free = 1;
    104   }
    105 
    106   pthread_mutex_unlock(&global_malloc_lock);
    107 }
    108 
    109 void print_brk() {
    110   void *p = sbrk(0);
    111   if (p == (void*)(-1))
    112     fprintf(stderr, "sbrk() failed\n");
    113   printf("brk: %p\n", p);
    114 }
    115 
    116 void print_header(struct header_t *header) {
    117   printf("hdr:  %p\n", header);
    118   printf("sizeof(hdr): %#zx\n", sizeof(struct header_t));
    119   if (!header) {
    120     return;
    121   }
    122   printf("size: %#zx\n", header->size);
    123   printf("free: %s\n", header->is_free ? "true" : "false");
    124 }
    125 
    126 void print_block(void *block) {
    127   printf("addr: %p\n", block);
    128   if (!block)
    129     return;
    130   struct header_t *h = (struct header_t*)(block) - 1;
    131   print_header(h);
    132 }
    133 
    134 void print_alloc_list() {
    135   printf("== head\n");
    136   print_header(head);
    137   printf("== tail\n");
    138   print_header(tail);
    139 }
    140