alloc.c

00001 /*! @file
00002   @brief
00003   mrubyc memory management.
00004 
00005   <pre>
00006   Copyright (C) 2015 Kyushu Institute of Technology.
00007   Copyright (C) 2015 Shimane IT Open-Innovation Center.
00008 
00009   This file is distributed under BSD 3-Clause License.
00010 
00011   Memory management for objects in mruby/c.
00012 
00013   </pre>
00014 */
00015 
00016 #include <stddef.h>
00017 #include <string.h>
00018 #include "alloc.h"
00019 #include "console.h "
00020 
00021 //
00022 #define ALLOC_TOTAL_MEMORY_SIZE 0x2800
00023 
00024 // address space 16bit, 64KB
00025 #define ALLOC_MAX_BIT 16
00026 
00027 // Layer 1st(f) and 2nd(s) model
00028 // last 4bit is ignored
00029 // f : size
00030 // 0 : 0000-007f
00031 // 1 : 0080-00ff
00032 // 2 : 0100-01ff
00033 // 3 : 0200-03ff
00034 // 4 : 0400-07ff
00035 // 5 : 0800-0fff
00036 // 6 : 1000-1fff
00037 // 7 : 2000-3fff
00038 // 8 : 4000-7fff
00039 // 9 : 8000-ffff
00040 
00041 #define ALLOC_1ST_LAYER 8
00042 #define ALLOC_1ST_LAYER_BIT ALLOC_1ST_LAYER
00043 #define ALLOC_1ST_LAYER_MASK 0xff80
00044 
00045 // 2nd layer size
00046 #define ALLOC_2ND_LAYER 8
00047 #define ALLOC_2ND_LAYER_BIT 3
00048 #define ALLOC_2ND_LAYER_MASK 0x0070
00049 
00050 // memory
00051 static uint8_t memory_pool[ALLOC_TOTAL_MEMORY_SIZE];
00052 
00053 // define flags
00054 #define FLAG_TAIL_BLOCK 1
00055 #define FLAG_NOT_TAIL_BLOCK 0
00056 #define FLAG_FREE_BLOCK 1
00057 #define FLAG_USED_BLOCK 0
00058 
00059 // memory block header
00060 struct USED_BLOCK {
00061   unsigned int t: 1;  /* FLAG_TAIL_BLOCK or FLAG_NOT_TAIL_BLOCK */
00062   unsigned int f: 1;  /* FLAG_FREE_BLOCK or BLOCK_IS_NOT_FREE */
00063   unsigned int size: 14; /* block size, header included */
00064   struct USED_BLOCK *prev;  /* link to previous block */
00065   uint8_t data[];
00066 };
00067 
00068 struct FREE_BLOCK {
00069   unsigned int t: 1;  /* 0: not tail,  1: tail */
00070   unsigned int f: 1;  /* 0: not free,  1: free */
00071   unsigned int size: 14; /* block size, header included */
00072   struct FREE_BLOCK *prev;  /* link to previous block */
00073   struct FREE_BLOCK *next_free;
00074   struct FREE_BLOCK *prev_free;
00075 };
00076 
00077 // free memory bitmap
00078 static struct FREE_BLOCK *free_blocks[ALLOC_1ST_LAYER * ALLOC_2ND_LAYER];
00079 
00080 
00081 // calc f and s, and returns index of free_blocks
00082 static int calc_index(uint32_t alloc_size)
00083 {
00084   if( alloc_size < 16 ) alloc_size = 16;
00085 
00086   // 1st layer
00087   int f = 0;
00088   uint32_t f_bit = ALLOC_1ST_LAYER_MASK;
00089   uint32_t s_bit = ALLOC_2ND_LAYER_MASK;
00090   while( (alloc_size & f_bit) != 0 ){
00091     f++;
00092     f_bit <<= 1;
00093     s_bit <<= 1;
00094   }
00095 
00096   // 2nd layer
00097   int s = (alloc_size & s_bit) >> (f + 4);
00098 
00099   return f * ALLOC_2ND_LAYER + s;
00100 }
00101 
00102 
00103 //
00104 static void add_free_block(struct FREE_BLOCK *block)
00105 {
00106   block->f = FLAG_FREE_BLOCK;
00107   int index = calc_index(block->size);
00108 
00109   block->prev_free = NULL;
00110   block->next_free = free_blocks[index];
00111   if( free_blocks[index] != NULL ){
00112     free_blocks[index]->prev_free = block;
00113   }
00114   free_blocks[index] = block;
00115 }
00116 
00117 
00118 // initialize free block
00119 void mrbc_init_alloc(void)
00120 {
00121   // clear links to free block
00122   int i;
00123   for( i=0 ; i<ALLOC_1ST_LAYER*ALLOC_2ND_LAYER ; i++ ){
00124     free_blocks[i] = NULL;
00125   }
00126 
00127   // memory pool
00128   struct FREE_BLOCK *block = (struct FREE_BLOCK *)memory_pool;
00129   block->t = FLAG_TAIL_BLOCK;
00130   block->size = ALLOC_TOTAL_MEMORY_SIZE;
00131   add_free_block(block);
00132 }
00133 
00134 // split block *alloc by size
00135 static struct FREE_BLOCK *split_block(struct FREE_BLOCK *alloc, int size)
00136 {
00137   if( alloc->size < size + 24 ) return NULL;
00138 
00139   // split block, free
00140   uint8_t *p = (uint8_t *)alloc;
00141   struct FREE_BLOCK *split = (struct FREE_BLOCK *)(p + size);
00142   struct FREE_BLOCK *next = (struct FREE_BLOCK *)(p + alloc->size);
00143   split->size = alloc->size - size;
00144   split->prev = alloc;
00145   split->f = FLAG_FREE_BLOCK;
00146   split->t = alloc->t;
00147   alloc->size = size;
00148   alloc->f = FLAG_USED_BLOCK;
00149   alloc->t = FLAG_NOT_TAIL_BLOCK;
00150   if( split->t == FLAG_NOT_TAIL_BLOCK ){
00151     next->prev = split;
00152   }
00153 
00154   return split;
00155 }
00156 
00157 
00158 // just remove the free_block *remove from index
00159 static void remove_index(struct FREE_BLOCK *remove)
00160 {
00161   // remove is top of linked list?
00162   if( remove->prev_free == NULL ){
00163     int index = calc_index(remove->size);
00164     free_blocks[index] = remove->next_free;
00165     if( free_blocks[index] != NULL ){
00166       free_blocks[index]->prev = NULL;
00167     }
00168   } else {
00169     remove->prev_free->next_free = remove->next_free;
00170     if( remove->next_free != NULL ){
00171       remove->next_free->prev_free = remove->prev_free;
00172     }
00173   }
00174 }
00175 
00176 // memory allocation
00177 uint8_t *mrbc_raw_alloc(uint32_t size)
00178 {
00179   uint32_t alloc_size = size + sizeof(struct USED_BLOCK);
00180 
00181   int index = calc_index(alloc_size);
00182   while( index < ALLOC_1ST_LAYER*ALLOC_2ND_LAYER && free_blocks[index] == NULL ){
00183     index++;
00184   }
00185   if( index >= ALLOC_1ST_LAYER*ALLOC_2ND_LAYER ){
00186     // out of memory
00187     console_print ("Fatal error: Out of memory.\n");
00188     return NULL;
00189   }
00190 
00191   // alloc a free block
00192   struct FREE_BLOCK *alloc = free_blocks[index];
00193   alloc->f = FLAG_USED_BLOCK;
00194   remove_index(alloc);
00195 
00196   // split a block
00197   struct FREE_BLOCK *release = split_block(alloc, alloc_size);
00198   if( release != NULL ){
00199     // split alloc -> alloc + release
00200     int index = calc_index(release->size);
00201     release->next_free = free_blocks[index];
00202     release->prev_free = NULL;
00203     free_blocks[index] = release;
00204     if( release->next_free != NULL ){
00205       release->next_free->prev_free = release;
00206     }
00207   }
00208 
00209   return ((struct USED_BLOCK *)alloc)->data;
00210 }
00211 
00212 
00213 // merge ptr1 and ptr2
00214 // ptr2 will disappear
00215 static void merge(struct FREE_BLOCK *ptr1, struct FREE_BLOCK *ptr2)
00216 {
00217   // merge ptr1 and ptr2
00218   ptr1->t = ptr2->t;
00219   ptr1->size += ptr2->size;
00220 
00221   // update block info
00222   if( ptr1->t == FLAG_NOT_TAIL_BLOCK ){
00223     uint8_t *p = (uint8_t *)ptr1;
00224     struct FREE_BLOCK *next = (struct FREE_BLOCK *)(p + ptr1->size);
00225     next->prev = ptr1;
00226   }
00227 }
00228 
00229 // memory release
00230 void mrbc_raw_free(void *ptr)
00231 {
00232   // get free block
00233   uint8_t *p = ptr;
00234   struct FREE_BLOCK *free_ptr = (struct FREE_BLOCK *)(p - sizeof(struct USED_BLOCK));
00235   free_ptr->f = FLAG_FREE_BLOCK;
00236 
00237   // check next block, merge?
00238   p = (uint8_t *)free_ptr;
00239   struct FREE_BLOCK *next_ptr = (struct FREE_BLOCK *)(p + free_ptr->size);
00240   if( free_ptr->t == FLAG_NOT_TAIL_BLOCK && next_ptr->f == FLAG_FREE_BLOCK ){
00241     remove_index(next_ptr);
00242     merge(free_ptr, next_ptr);
00243   }
00244 
00245   // check prev block, merge?
00246   struct FREE_BLOCK *prev_ptr = free_ptr->prev;
00247   if( prev_ptr != NULL && prev_ptr->f == FLAG_FREE_BLOCK ){
00248     remove_index(prev_ptr);
00249     merge(prev_ptr, free_ptr);
00250     free_ptr = prev_ptr;
00251   }
00252 
00253   // free, add to index
00254   add_free_block(free_ptr);
00255 }
00256 
00257 
00258 // simple realloc
00259 uint8_t *mrbc_raw_realloc(uint8_t *ptr, uint32_t size)
00260 {
00261   uint8_t *new_ptr = mrbc_raw_alloc(size);
00262   if( new_ptr == NULL ) return NULL;  // ENOMEM
00263 
00264   // get block info
00265   uint8_t *src_ptr = ptr;
00266   struct USED_BLOCK *src_block = (struct USED_BLOCK *)(src_ptr - sizeof(struct USED_BLOCK));
00267 
00268   // copy size
00269   int copy_size;
00270   if( size > src_block->size-sizeof(struct USED_BLOCK) ){
00271     copy_size = src_block->size - sizeof(struct USED_BLOCK);
00272   } else {
00273     copy_size = size;
00274   }
00275 
00276   // copy and free
00277   memcpy(new_ptr, src_ptr, copy_size);
00278   mrbc_raw_free(ptr);
00279 
00280   return new_ptr;
00281 }
00282 
00283 // for debug
00284 #ifdef MRBC_DEBUG
00285 #include <stdio.h>
00286 void mrbc_alloc_debug(void)
00287 {
00288   struct FREE_BLOCK *ptr = (struct FREE_BLOCK *)memory_pool;
00289   printf("-----\naddress f size\n");
00290   do {
00291     uint8_t *p = (uint8_t *)ptr;
00292     printf("%p: %d %x\n", p, ptr->f, ptr->size);
00293     if( ptr->t == FLAG_TAIL_BLOCK ) break;
00294     p += ptr->size;
00295     ptr = (struct FREE_BLOCK *)p;
00296   } while(1);
00297 
00298   printf("-----\n");
00299   int i;
00300   for( i=0 ; i<ALLOC_1ST_LAYER * ALLOC_2ND_LAYER ; i++ ){
00301     if( free_blocks[i] == NULL ) continue;
00302     printf("free[%d]\n", i);
00303     struct FREE_BLOCK *ptr = free_blocks[i];
00304     while( ptr != NULL ){
00305       printf("  %p: size=%d\n", ptr, ptr->size);
00306       ptr = ptr->next_free;
00307     }
00308   }
00309 }
00310 #endif
00311 
00312 //// for mruby/c
00313 
00314 struct MEM_WITH_VM {
00315   uint8_t vm_id;
00316   uint8_t data[];
00317 };
00318 
00319 uint8_t *mrbc_alloc(mrb_vm *vm, int size)
00320 {
00321   int alloc_size = size + sizeof(struct MEM_WITH_VM);
00322   struct MEM_WITH_VM *alloc_block =
00323       (struct MEM_WITH_VM *)mrbc_raw_alloc(alloc_size);
00324   if( alloc_block == NULL ) return NULL;  // ENOMEM
00325 
00326   alloc_block->vm_id = (vm != NULL) ? vm->vm_id : 0;
00327   return alloc_block->data;
00328 }
00329 
00330 
00331 uint8_t *mrbc_realloc(mrb_vm *vm, void *ptr, int size)
00332 {
00333   int alloc_size = size + sizeof(struct MEM_WITH_VM);
00334   struct MEM_WITH_VM *alloc_block =
00335       (struct MEM_WITH_VM *)mrbc_raw_realloc(ptr, alloc_size);
00336   if( alloc_block == NULL ) return NULL;  // ENOMEM
00337 
00338   alloc_block->vm_id = (vm != NULL) ? vm->vm_id : 0;
00339   return alloc_block->data;
00340 }
00341 
00342 
00343 void mrbc_free(mrb_vm *vm, void *ptr)
00344 {
00345   if( ptr == NULL ) return;
00346 
00347   uint8_t *p = (uint8_t *)ptr;
00348   struct MEM_WITH_VM *free_block = (struct MEM_WITH_VM *)(p - sizeof(struct MEM_WITH_VM));
00349   mrbc_raw_free(free_block);
00350 }
00351 
00352 
00353 void mrbc_free_all(mrb_vm *vm)
00354 {
00355   int vm_id = vm->vm_id;
00356 
00357   struct USED_BLOCK *ptr = (struct USED_BLOCK *)memory_pool;
00358   while( ptr->t != FLAG_TAIL_BLOCK ){
00359     struct MEM_WITH_VM *vm_ptr = (struct MEM_WITH_VM *)(ptr->data);
00360     if( ptr->f == FLAG_FREE_BLOCK || vm_ptr->vm_id != vm_id ){
00361       uint8_t *p = (uint8_t *)ptr;
00362       ptr = (struct USED_BLOCK *)(p + ptr->size);
00363       continue;
00364     }
00365     if( vm_ptr->vm_id != vm_id ) continue;
00366     // free a block
00367     struct USED_BLOCK *next_ptr = ptr->prev;
00368     if( next_ptr == NULL ) next_ptr = ptr;
00369     mrbc_raw_free(ptr->data);
00370     ptr = next_ptr;
00371   }  
00372 }
00373