3 * Funded by IPA̤Ƨ¥½¥Õ¥È¥¦¥§¥¢ÁϤ»ö¶È 2001 8/15
5 * $Id: alloc.c,v 1.12 2002/05/15 11:21:10 yusuke Exp $
7 * Copyright (C) 2005 YOSHIDA Yuichi
8 * Copyright (C) 2000-2005 TABATA Yusuke, UGAWA Tomoharu
9 * Copyright (C) 2002, 2005 NIIBE Yutaka
13 * ¥Ú¡¼¥¸Ãæ¤Î¥Õ¥ê¡¼¤Êchunk¤ÏñÊý¸þ¥ê¥¹¥È¤Ë·Ñ¤¬¤ì¤Æ¤¤¤ë
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.
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.
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
36 #include <anthy/alloc.h>
37 #include <anthy/logger.h>
40 #define PAGE_MAGIC 0x12345678
41 #define PAGE_SIZE 2048
43 /* ¥Ú¡¼¥¸»ÈÍÑÎ̤ιç·×¡¢¥Ç¥Ð¥Ã¥°¤Î»þÅù¤ËÍѤ¤¤ë */
46 /* pageÆâ¤Î¥ª¥Ö¥¸¥§¥¯¥È¤òɽ¤¹¥ª¥Ö¥¸¥§¥¯¥È */
50 #define CHUNK_HEADER_SIZE ((size_t)&((struct chunk *)0)->storage)
51 /* CPU¤â¤·¤¯¤Ï¡¢OS¤Î¼ïÎà¤Ë¤è¤Ã¤ÆÍ׵ᤵ¤ì¤ë¥¢¥é¥¤¥á¥ó¥È */
52 #define CHUNK_ALIGN (sizeof(double))
56 * max_obj = (PAGE_SIZE - PAGE_HEADER_SIZE) / (size + CHUNK_HEADER_SIZE)¸Ä¤Î
57 * ¥¹¥í¥Ã¥È¤¬¤¢¤ë¡£¤½¤Î¤¦¤Áuse_count¸Ä¤Î¥¹¥í¥Ã¥È¤¬free_list¤Ë¤Ä¤Ê¤¬¤Ã¤Æ¤¤¤ë¡¢
58 * ¤â¤·¤¯¤Ï»ÈÍÑÃæ¤Ç¤¢¤ë¡£
62 struct page *prev, *next;
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)])
73 struct allocator_priv {
76 /* ¥Ú¡¼¥¸Æâ¤ËÆþ¤ì¤ë¤³¤È¤¬¤Ç¤¤ë¥ª¥Ö¥¸¥§¥¯¥È¤Î¿ô */
79 ¼ÂºÝ¤Î¥Ç¡¼¥¿¤¬³ÊǼ¤µ¤ì»Ï¤á¤ë¾ì½ê¤Î¥ª¥Õ¥»¥Ã¥È
80 ¥Ú¡¼¥¸Ãæ¤Î¤³¤ì¤è¤ê¼êÁ°¤Ë¤ÏÂбþ¤¹¤ë¾ì½ê¤Î¥Ç¡¼¥¿¤¬»È¤ï¤ì¤Æ¤¤¤ë¤«¤É¤¦¤«¤ò0/1¤Çɽ¤¹
84 /* ¤³¤Îallocator¤¬»ÈÍѤ·¤Æ¤¤¤ë¥Ú¡¼¥¸¤Î¥ê¥¹¥È */
85 struct page page_list;
86 /* allocator¤Î¥ê¥¹¥È */
87 struct allocator_priv *next;
88 /* sfree¤·¤¿ºÝ¤Ë¸Æ¤Ð¤ì¤ë */
92 static struct allocator_priv *allocator_list;
94 static int bit_test(unsigned char* bits, int pos)
97 bit_get¤È¤Û¤ÜƱ¤¸¤À¤¬bit != 0¤Î»þ¤Ë0°Ê³°¤òÊÖ¤¹¤³¤È¤·¤«Êݾڤ·¤Ê¤¤
99 return bits[pos >> 3] & (1 << (7 - (pos & 0x7)));
103 static int bit_set(unsigned char* bits, int pos, int bit)
105 unsigned char filter = 1 << (7 - (pos & 0x7));
107 return bits[pos >> 3] &= ~filter;
109 return bits[pos >> 3] |= filter;
114 static struct chunk *
115 get_chunk_address(void *s)
117 return (struct chunk *)
118 ((unsigned long)s - CHUNK_HEADER_SIZE);
122 alloc_page(struct allocator_priv *ator)
125 unsigned char* avail;
127 p = malloc(PAGE_SIZE);
132 p->magic = PAGE_MAGIC;
133 avail = PAGE_AVAIL(p);
134 memset(avail, 0, (ator->max_num >> 3) + 1);
138 static struct chunk *
139 get_chunk_from_page(allocator a, struct page *p)
143 int num = a->max_num;
144 unsigned char* avail = PAGE_AVAIL(p);
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);
156 roundup_align(int num)
158 num = num + (CHUNK_ALIGN - 1);
165 calc_max_num(int size)
169 * ¸·Ì©¤ÊºÇŬ²ò¤Ç¤Ï¤Ê¤¤
171 area = (PAGE_SIZE - PAGE_HEADER_SIZE - CHUNK_ALIGN) * 8;
172 bits = (size + CHUNK_HEADER_SIZE) * 8 + 1;
173 return (int)(area / bits);
177 anthy_create_allocator(int size, void (*dtor)(void *))
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");
185 a = malloc(sizeof(*a));
187 anthy_log(0, "Fatal error: Failed to allocate memory.\n");
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);*/
195 a->page_list.next = &a->page_list;
196 a->page_list.prev = &a->page_list;
197 a->next = allocator_list;
203 anthy_free_allocator_internal(allocator a)
205 struct page *p, *p_next;
207 /* ³Æ¥Ú¡¼¥¸¤Î¥á¥â¥ê¤ò²òÊü¤¹¤ë */
208 for (p = a->page_list.next; p != &a->page_list; p = p_next) {
209 unsigned char* avail = PAGE_AVAIL(p);
214 for (i = 0; i < a->max_num; i++) {
215 if (bit_test(avail, i)) {
218 bit_set(avail, i, 0);
219 c = PAGE_CHUNK(a, p, i);
231 anthy_free_allocator(allocator a)
233 allocator a0, *a_prev_p;
235 /* ¥ê¥¹¥È¤«¤éa¤ÎÁ°¤ÎÍ×ÁǤò¸«ÉÕ¤±¤ë */
236 a_prev_p = &allocator_list;
237 for (a0 = allocator_list; a0; a0 = a0->next) {
241 a_prev_p = &a0->next;
243 /* a¤ò¥ê¥¹¥È¤«¤é³°¤¹ */
246 anthy_free_allocator_internal(a);
250 anthy_smalloc(allocator a)
255 /* ¶õ¤¤¤Æ¤ë¥Ú¡¼¥¸¤ò¤µ¤¬¤¹ */
256 for (p = a->page_list.next; p != &a->page_list; p = p->next) {
257 c = get_chunk_from_page(a, p);
262 /* ¥Ú¡¼¥¸¤òºî¤Ã¤Æ¡¢¥ê¥ó¥¯¤¹¤ë */
265 anthy_log(0, "Fatal error: Failed to allocate memory.\n");
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;
275 return anthy_smalloc(a);
279 anthy_sfree(allocator a, void *ptr)
281 struct chunk *c = get_chunk_address(ptr);
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) {
293 if (!p || p->magic != PAGE_MAGIC) {
294 anthy_log(0, "sfree()ing Invalid Object\n");
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);
303 /* ¥Ç¥¹¥È¥é¥¯¥¿¤ò¸Æ¤Ö */
310 anthy_quit_allocator(void)
313 for (a = allocator_list; a; a = a_next) {
315 anthy_free_allocator_internal(a);
317 allocator_list = NULL;