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