diff options
Diffstat (limited to 'libraries/eina/src/modules/mp/buddy/eina_buddy.c')
-rw-r--r-- | libraries/eina/src/modules/mp/buddy/eina_buddy.c | 292 |
1 files changed, 0 insertions, 292 deletions
diff --git a/libraries/eina/src/modules/mp/buddy/eina_buddy.c b/libraries/eina/src/modules/mp/buddy/eina_buddy.c deleted file mode 100644 index 7d830db..0000000 --- a/libraries/eina/src/modules/mp/buddy/eina_buddy.c +++ /dev/null | |||
@@ -1,292 +0,0 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2009 Jorge Luis Zapata Muga | ||
3 | * | ||
4 | * This library is free software; you can redistribute it and/or | ||
5 | * modify it under the terms of the GNU Lesser General Public | ||
6 | * License as published by the Free Software Foundation; either | ||
7 | * version 2.1 of the License, or (at your option) any later version. | ||
8 | * | ||
9 | * This library is distributed in the hope that it will be useful, | ||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
12 | * Lesser General Public License for more details. | ||
13 | * | ||
14 | * You should have received a copy of the GNU Lesser General Public | ||
15 | * License along with this library; | ||
16 | * if not, see <http://www.gnu.org/licenses/>. | ||
17 | */ | ||
18 | |||
19 | /* | ||
20 | * This is a naive 'buddy' allocator following Knuth's documentation. | ||
21 | * The main difference is that we dont store the block information | ||
22 | * on the block memory itself but on another malloc'd area. | ||
23 | * This is useful for managing memory which isn't as fast as the main | ||
24 | * memory like the video memory | ||
25 | * The algorithm uses an area to store the linked list of blocks. | ||
26 | * Each block size is equal to the minimum allocatable block size for | ||
27 | * the memory pool and the number of blocks is equal to the size of the | ||
28 | * memory pool divided by the block size. | ||
29 | */ | ||
30 | #ifdef HAVE_CONFIG_H | ||
31 | # include "config.h" | ||
32 | #endif | ||
33 | |||
34 | #include <stdio.h> | ||
35 | |||
36 | #include "eina_types.h" | ||
37 | #include "eina_inlist.h" | ||
38 | #include "eina_module.h" | ||
39 | #include "eina_mempool.h" | ||
40 | #include "eina_private.h" | ||
41 | |||
42 | typedef struct _Block | ||
43 | { | ||
44 | EINA_INLIST; | ||
45 | Eina_Bool available : 1; | ||
46 | unsigned short int order : 7; /* final order is order + min_order */ | ||
47 | } Block; | ||
48 | |||
49 | typedef struct _Buddy | ||
50 | { | ||
51 | void *heap; /* start address of the heap */ | ||
52 | size_t size; /* total size in bytes of the heap */ | ||
53 | unsigned int min_order; /* minimum size is 1 << min_order */ | ||
54 | unsigned int max_order; /* maximum size is 1 << max_order */ | ||
55 | unsigned int num_order; /* number of orders */ | ||
56 | Eina_Inlist **areas; /* one area per order */ | ||
57 | Block *blocks; /* the allocated block information */ | ||
58 | } Buddy; | ||
59 | |||
60 | /* get the minimum order greater or equal to size */ | ||
61 | static inline unsigned int _get_order(Buddy *b, size_t size) | ||
62 | { | ||
63 | unsigned int i; | ||
64 | size_t bytes; | ||
65 | |||
66 | bytes = 1 << b->min_order; | ||
67 | for (i = 0; bytes < size && i < b->num_order; i++) | ||
68 | { | ||
69 | bytes += bytes; | ||
70 | } | ||
71 | //printf("order for size %d is %d\n", size, i + b->min_order); | ||
72 | return i; | ||
73 | } | ||
74 | |||
75 | static inline void *_get_offset(Buddy *b, Block *block) | ||
76 | { | ||
77 | void *ret; | ||
78 | |||
79 | ret = (char *)b->heap + ((block - &b->blocks[0]) << b->min_order); | ||
80 | return ret; | ||
81 | } | ||
82 | |||
83 | static void *_init(__UNUSED__ const char *context, | ||
84 | __UNUSED__ const char *options, | ||
85 | va_list args) | ||
86 | { | ||
87 | Buddy *b; | ||
88 | int i; | ||
89 | size_t bytes; | ||
90 | size_t size; | ||
91 | size_t min_order; | ||
92 | void *heap; | ||
93 | |||
94 | heap = va_arg(args, void *); | ||
95 | size = va_arg(args, size_t); | ||
96 | min_order = va_arg(args, int); | ||
97 | /* the minimum order we support is 15 (32K) */ | ||
98 | min_order = min_order < 15 ? 15 : min_order; | ||
99 | bytes = 1 << min_order; | ||
100 | for (i = 0; bytes <= size; i++) | ||
101 | { | ||
102 | bytes += bytes; | ||
103 | } | ||
104 | if (!i) | ||
105 | return NULL; | ||
106 | |||
107 | b = malloc(sizeof(Buddy)); | ||
108 | b->heap = heap; | ||
109 | b->size = size; | ||
110 | b->min_order = min_order; | ||
111 | b->max_order = min_order + i - 1; | ||
112 | b->num_order = i; | ||
113 | b->areas = calloc(b->num_order, sizeof(Eina_Inlist *)); | ||
114 | b->blocks = calloc(1 << (b->num_order - 1), sizeof(Block)); | ||
115 | /* setup the initial free area */ | ||
116 | b->blocks[0].available = EINA_TRUE; | ||
117 | b->areas[b->num_order - 1] = EINA_INLIST_GET(&(b->blocks[0])); | ||
118 | |||
119 | return b; | ||
120 | } | ||
121 | |||
122 | static void _shutdown(void *data) | ||
123 | { | ||
124 | Buddy *b = data; | ||
125 | |||
126 | free(b->blocks); | ||
127 | free(b->areas); | ||
128 | free(b); | ||
129 | } | ||
130 | |||
131 | static void _free(void *data, void *element) | ||
132 | { | ||
133 | Buddy *b = data; | ||
134 | Block *block, *buddy; | ||
135 | size_t offset; | ||
136 | size_t idx; | ||
137 | |||
138 | offset = (unsigned char *)element - (unsigned char *)b->heap; | ||
139 | if (offset > b->size) | ||
140 | return; | ||
141 | |||
142 | idx = offset >> b->min_order; | ||
143 | block = &b->blocks[idx]; | ||
144 | |||
145 | //printf("free %x idx = %d order = %d buddy = %d\n", offset, idx, block->order, idx ^ (1 << block->order)); | ||
146 | /* we should always work with the buddy at right */ | ||
147 | if (idx & (1 << block->order)) | ||
148 | { | ||
149 | Block *left; | ||
150 | |||
151 | idx = idx ^ (1 << block->order); | ||
152 | left = &b->blocks[idx]; | ||
153 | if (!left->available) | ||
154 | goto end; | ||
155 | else | ||
156 | { | ||
157 | buddy = block; | ||
158 | block = left; | ||
159 | b->areas[block->order] = eina_inlist_remove(b->areas[block->order], | ||
160 | EINA_INLIST_GET(block)); | ||
161 | block->order++; | ||
162 | } | ||
163 | } | ||
164 | |||
165 | check: | ||
166 | /* already on the last order */ | ||
167 | if (block->order + b->min_order == b->max_order) | ||
168 | { | ||
169 | goto end; /* get the buddy */ | ||
170 | |||
171 | } | ||
172 | |||
173 | buddy = &b->blocks[idx ^ (1 << block->order)]; | ||
174 | if (!buddy->available) | ||
175 | { | ||
176 | goto end; /* merge two blocks */ | ||
177 | |||
178 | } | ||
179 | |||
180 | b->areas[block->order] = eina_inlist_remove(b->areas[block->order], | ||
181 | EINA_INLIST_GET(buddy)); | ||
182 | block->order++; | ||
183 | goto check; | ||
184 | end: | ||
185 | /* add the block to the free list */ | ||
186 | block->available = EINA_TRUE; | ||
187 | b->areas[block->order] = eina_inlist_append(b->areas[block->order], | ||
188 | EINA_INLIST_GET(block)); | ||
189 | } | ||
190 | |||
191 | static void *_alloc(void *data, unsigned int size) | ||
192 | { | ||
193 | Buddy *b = data; | ||
194 | Block *block, *buddy; | ||
195 | unsigned int k, j; | ||
196 | |||
197 | k = j = _get_order(b, size); | ||
198 | /* get a free list of order k where k <= j <= max_order */ | ||
199 | while ((j < b->num_order) && !b->areas[j]) | ||
200 | j++; | ||
201 | /* check that the order is on our range */ | ||
202 | if (j + b->min_order > b->max_order) | ||
203 | return NULL; | ||
204 | |||
205 | /* get a free element on this order, if not, go splitting until we find one */ | ||
206 | //printf("getting order %d (%d) for size %d\n", j, k, size); | ||
207 | found: | ||
208 | if (j == k) | ||
209 | { | ||
210 | void *ret; | ||
211 | |||
212 | block = EINA_INLIST_CONTAINER_GET(b->areas[j], Block); | ||
213 | block->available = EINA_FALSE; | ||
214 | block->order = j; | ||
215 | /* remove the block from the list */ | ||
216 | b->areas[j] = eina_inlist_remove(b->areas[j], EINA_INLIST_GET(block)); | ||
217 | ret = _get_offset(b, block); | ||
218 | |||
219 | return ret; | ||
220 | } | ||
221 | |||
222 | block = EINA_INLIST_CONTAINER_GET(b->areas[j], Block); | ||
223 | /* split */ | ||
224 | b->areas[j] = eina_inlist_remove(b->areas[j], EINA_INLIST_GET(block)); | ||
225 | j--; | ||
226 | b->areas[j] = eina_inlist_append(b->areas[j], EINA_INLIST_GET(block)); | ||
227 | buddy = block + (1 << j); | ||
228 | buddy->order = j; | ||
229 | buddy->available = EINA_TRUE; | ||
230 | b->areas[j] = eina_inlist_append(b->areas[j], EINA_INLIST_GET(buddy)); | ||
231 | |||
232 | goto found; | ||
233 | } | ||
234 | |||
235 | static void _statistics(void *data) | ||
236 | { | ||
237 | Buddy *b = data; | ||
238 | unsigned int i; | ||
239 | |||
240 | printf("Information:\n"); | ||
241 | printf( | ||
242 | "size = %zu, min_order = %d, max_order = %d, num_order = %d, num_blocks = %d (%uKB)\n", | ||
243 | b->size, | ||
244 | b->min_order, | ||
245 | b->max_order, | ||
246 | b->num_order, | ||
247 | 1 << b->num_order, | ||
248 | ((1 << (b->num_order)) * sizeof(Block)) / 1024); | ||
249 | printf("Area dumping:"); | ||
250 | /* iterate over the free lists and dump the maps */ | ||
251 | for (i = 0; i < b->num_order; i++) | ||
252 | { | ||
253 | Block *block; | ||
254 | |||
255 | printf("\n2^%d:", b->min_order + i); | ||
256 | EINA_INLIST_FOREACH(b->areas[i], block) | ||
257 | { | ||
258 | printf(" %d", (block - &b->blocks[0])); | ||
259 | } | ||
260 | } | ||
261 | printf("\nBlocks dumping:\n"); | ||
262 | } | ||
263 | |||
264 | static Eina_Mempool_Backend _backend = { | ||
265 | "buddy", | ||
266 | &_init, | ||
267 | &_free, | ||
268 | &_alloc, | ||
269 | NULL, /* realloc */ | ||
270 | NULL, /* garbage collect */ | ||
271 | &_statistics, | ||
272 | &_shutdown, | ||
273 | NULL /* repack */ | ||
274 | }; | ||
275 | |||
276 | Eina_Bool buddy_init(void) | ||
277 | { | ||
278 | return eina_mempool_register(&_backend); | ||
279 | } | ||
280 | |||
281 | void buddy_shutdown(void) | ||
282 | { | ||
283 | eina_mempool_unregister(&_backend); | ||
284 | } | ||
285 | |||
286 | |||
287 | #ifndef EINA_STATIC_BUILD_BUDDY | ||
288 | |||
289 | EINA_MODULE_INIT(buddy_init); | ||
290 | EINA_MODULE_SHUTDOWN(buddy_shutdown); | ||
291 | |||
292 | #endif /* ! EINA_STATIC_BUILD_BUDDY */ | ||