1: /*
    2:  * 構造体アロケータ
    3:  * Funded by IPA未踏ソフトウェア創造事業 2001 8/15
    4:  *
    5:  * $Id: alloc.c,v 1.12 2002/05/15 11:21:10 yusuke Exp $
    6:  *
    7:  * Copyright (C) 2005 YOSHIDA Yuichi
    8:  * Copyright (C) 2000-2005 TABATA Yusuke, UGAWA Tomoharu
    9:  * Copyright (C) 2002, 2005 NIIBE Yutaka
   10:  *
   11:  * dtor: destructor
   12:  * 
   13:  * ページ中のフリーなchunkは単方向リストに継がれている
   14:  *
   15:  */
   16: /*
   17:   This library is free software; you can redistribute it and/or
   18:   modify it under the terms of the GNU Lesser General Public
   19:   License as published by the Free Software Foundation; either
   20:   version 2 of the License, or (at your option) any later version.
   21: 
   22:   This library is distributed in the hope that it will be useful,
   23:   but WITHOUT ANY WARRANTY; without even the implied warranty of
   24:   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   25:   Lesser General Public License for more details.
   26: 
   27:   You should have received a copy of the GNU Lesser General Public
   28:   License along with this library; if not, write to the Free Software
   29:   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
   30:  */
   31: 
   32: #include <stdio.h>
   33: #include <stdlib.h>
   34: #include <string.h>
   35: 
   36: #include <anthy/alloc.h>
   37: #include <anthy/logger.h>
   38: 
   39: /**/
   40: #define PAGE_MAGIC 0x12345678
   41: #define PAGE_SIZE 2048
   42: 
   43: /* ページ使用量の合計、デバッグの時等に用いる */
   44: static int nr_pages;
   45: 
   46: /* page内のオブジェクトを表すオブジェクト */
   47: struct chunk {
   48:   void *storage[1];
   49: };
   50: #define CHUNK_HEADER_SIZE ((size_t)&((struct chunk *)0)->storage)
   51: /* CPUもしくは、OSの種類によって要求されるアライメント */
   52: #define CHUNK_ALIGN (sizeof(double))
   53: 
   54: /*
   55:  * pageのstorage中には 
   56:  * max_obj = (PAGE_SIZE - PAGE_HEADER_SIZE) / (size + CHUNK_HEADER_SIZE)個の
   57:  * スロットがある。そのうちuse_count個のスロットがfree_listにつながっている、
   58:  * もしくは使用中である。
   59:  */
   60: struct page {
   61:   int magic;
   62:   struct page *prev, *next;
   63: };
   64: 
   65: 
   66: #define PAGE_HEADER_SIZE (sizeof(struct page))
   67: #define PAGE_AVAIL(p) ((unsigned char*)p + sizeof(struct page))
   68: #define PAGE_STORAGE(a, p) (((unsigned char *)p) + (a->storage_offset))
   69: #define PAGE_CHUNK(a, p, i) (struct chunk*)(&PAGE_STORAGE(a, p)[((a->size) + CHUNK_HEADER_SIZE) * (i)])
   70: 
   71: 
   72: /**/
   73: struct allocator_priv {
   74:   /* 構造体のサイズ */
   75:   int size;
   76:   /* ページ内に入れることができるオブジェクトの数 */
   77:   int max_num;
   78:   /* 
   79:      実際のデータが格納され始める場所のオフセット 
   80:      ページ中のこれより手前には対応する場所のデータが使われているかどうかを0/1で表す
   81:      ビットマップがある
   82:    */
   83:   int storage_offset;
   84:   /* このallocatorが使用しているページのリスト */
   85:   struct page page_list;
   86:   /* allocatorのリスト */
   87:   struct allocator_priv *next;
   88:   /* sfreeした際に呼ばれる */
   89:   void (*dtor)(void *);
   90: };
   91: 
   92: static struct allocator_priv *allocator_list;
   93: 
   94: static int bit_test(unsigned char* bits, int pos)
   95: {
   96:   /*
   97:      bit_getとほぼ同じだがbit != 0の時に0以外を返すことしか保証しない
   98:    */
   99:   return bits[pos >> 3] & (1 << (7 - (pos & 0x7)));
  100: }
  101: 
  102: 
  103: static int bit_set(unsigned char* bits, int pos, int bit)
  104: {
  105:   unsigned char filter = 1 << (7 - (pos & 0x7));
  106:   if (bit == 0) {
  107:     return bits[pos >> 3] &= ~filter;
  108:   } else {
  109:     return bits[pos >> 3] |= filter;
  110:   }
  111: }
  112: 
  113: 
  114: static struct chunk *
  115: get_chunk_address(void *s)
  116: {
  117:   return (struct chunk *)
  118:     ((unsigned long)s - CHUNK_HEADER_SIZE);
  119: }
  120: 
  121: static struct page *
  122: alloc_page(struct allocator_priv *ator)
  123: {
  124:   struct page *p;
  125:   unsigned char* avail;
  126:     
  127:   p = malloc(PAGE_SIZE);
  128:   if (!p) {
  129:     return NULL;
  130:   }
  131: 
  132:   p->magic = PAGE_MAGIC;
  133:   avail = PAGE_AVAIL(p);
  134:   memset(avail, 0, (ator->max_num >> 3) + 1);
  135:   return p;
  136: }
  137: 
  138: static struct chunk *
  139: get_chunk_from_page(allocator a, struct page *p)
  140: {
  141:   int i;
  142: 
  143:   int num = a->max_num;
  144:   unsigned char* avail = PAGE_AVAIL(p);
  145: 
  146:   for (i = 0; i < num; ++i) {
  147:     if (bit_test(avail, i) == 0) {
  148:       bit_set(avail, i, 1);
  149:       return PAGE_CHUNK(a, p, i);
  150:     }
  151:   }
  152:   return NULL;  
  153: }
  154: 
  155: static int
  156: roundup_align(int num)
  157: {
  158:   num = num + (CHUNK_ALIGN - 1);
  159:   num /= CHUNK_ALIGN;
  160:   num *= CHUNK_ALIGN;
  161:   return num;
  162: }
  163: 
  164: static int
  165: calc_max_num(int size)
  166: {
  167:   int area, bits;
  168:   /* ビット数で計算
  169:    * 厳密な最適解ではない
  170:    */
  171:   area = (PAGE_SIZE - PAGE_HEADER_SIZE - CHUNK_ALIGN) * 8;
  172:   bits = (size + CHUNK_HEADER_SIZE) * 8 + 1;
  173:   return (int)(area / bits);
  174: }
  175: 
  176: allocator
  177: anthy_create_allocator(int size, void (*dtor)(void *))
  178: {
  179:   allocator a;
  180: size=roundup_align(size);
  181:   if (size > (int)(PAGE_SIZE - PAGE_HEADER_SIZE - CHUNK_HEADER_SIZE)) {
  182:     anthy_log(0, "Fatal error: too big allocator is requested.\n");
  183:     exit(1);
  184:   }
  185:   a = malloc(sizeof(*a));
  186:   if (!a) {
  187:     anthy_log(0, "Fatal error: Failed to allocate memory.\n");
  188:     exit(1);
  189:   }
  190:   a->size = size;
  191:   a->max_num = calc_max_num(size); 
  192:   a->storage_offset = roundup_align(sizeof(struct page) + a->max_num / 8 + 1);
  193:   /*printf("size=%d max_num=%d offset=%d area=%d\n", size, a->max_num, a->storage_offset, size*a->max_num + a->storage_offset);*/
  194:   a->dtor = dtor;
  195:   a->page_list.next = &a->page_list;
  196:   a->page_list.prev = &a->page_list;
  197:   a->next = allocator_list;
  198:   allocator_list = a;
  199:   return a;
  200: }
  201: 
  202: static void
  203: anthy_free_allocator_internal(allocator a)
  204: {
  205:   struct page *p, *p_next;
  206: 
  207:   /* 各ページのメモリを解放する */
  208:   for (p = a->page_list.next; p != &a->page_list; p = p_next) {
  209:     unsigned char* avail = PAGE_AVAIL(p);
  210:     int i;
  211: 
  212:     p_next = p->next;
  213:     if (a->dtor) {
  214:       for (i = 0; i < a->max_num; i++) {
  215:         if (bit_test(avail, i)) {
  216:           struct chunk *c;
  217: 
  218:           bit_set(avail, i, 0);
  219:           c = PAGE_CHUNK(a, p, i);
  220:           a->dtor(c->storage);
  221:         }
  222:       }
  223:     }
  224:     free(p);
  225:     nr_pages--;
  226:   }
  227:   free(a);
  228: }
  229: 
  230: void
  231: anthy_free_allocator(allocator a)
  232: {
  233:   allocator a0, *a_prev_p;
  234: 
  235:   /* リストからaの前の要素を見付ける */
  236:   a_prev_p = &allocator_list;
  237:   for (a0 = allocator_list; a0; a0 = a0->next) {
  238:     if (a == a0)
  239:       break;
  240:     else
  241:       a_prev_p = &a0->next;
  242:   }
  243:   /* aをリストから外す */
  244:   *a_prev_p = a->next;
  245: 
  246:   anthy_free_allocator_internal(a);
  247: }
  248: 
  249: void *
  250: anthy_smalloc(allocator a)
  251: {
  252:   struct page *p;
  253:   struct chunk *c;
  254: 
  255:   /* 空いてるページをさがす */
  256:   for (p = a->page_list.next; p != &a->page_list; p = p->next) {
  257:     c = get_chunk_from_page(a, p);
  258:     if (c) {
  259:       return c->storage;
  260:     }
  261:   }
  262:   /* ページを作って、リンクする */
  263:   p = alloc_page(a);
  264:   if (!p) {
  265:     anthy_log(0, "Fatal error: Failed to allocate memory.\n");
  266:     return NULL;
  267:   }
  268:   nr_pages++;
  269: 
  270:   p->next = a->page_list.next;
  271:   p->prev = &a->page_list;
  272:   a->page_list.next->prev = p;
  273:   a->page_list.next = p;
  274:   /* やり直す */
  275:   return anthy_smalloc(a);
  276: }
  277: 
  278: void
  279: anthy_sfree(allocator a, void *ptr)
  280: {
  281:   struct chunk *c = get_chunk_address(ptr);
  282:   struct page *p;
  283:   int index;
  284:   /* ポインタの含まれるページを探す */
  285:   for (p = a->page_list.next; p != &a->page_list; p = p->next) {
  286:     if ((unsigned long)p < (unsigned long)c &&
  287:         (unsigned long)c < (unsigned long)p + PAGE_SIZE) {
  288:       break;
  289:     }
  290:   }
  291: 
  292:   /* sanity check */
  293:   if (!p || p->magic != PAGE_MAGIC) {
  294:     anthy_log(0, "sfree()ing Invalid Object\n");
  295:     abort();
  296:   }
  297: 
  298:   /* ページ中の何番目のオブジェクトかを求める */
  299:   index = ((unsigned long)c - (unsigned long)PAGE_STORAGE(a, p)) /
  300:     (a->size + CHUNK_HEADER_SIZE);  
  301:   bit_set(PAGE_AVAIL(p), index, 0);
  302: 
  303:   /* デストラクタを呼ぶ */
  304:   if (a->dtor) {
  305:     a->dtor(ptr);
  306:   }
  307: }
  308: 
  309: void
  310: anthy_quit_allocator(void)
  311: {
  312:   allocator a, a_next;
  313:   for (a = allocator_list; a; a = a_next) {
  314:     a_next = a->next;
  315:     anthy_free_allocator_internal(a);
  316:   }
  317:   allocator_list = NULL;
  318: }