src-diclib/alloc.c

   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 }