diff options
author | David Walter Seikel | 2012-01-04 18:41:13 +1000 |
---|---|---|
committer | David Walter Seikel | 2012-01-04 18:41:13 +1000 |
commit | dd7595a3475407a7fa96a97393bae8c5220e8762 (patch) | |
tree | e341e911d7eb911a51684a7412ef7f7c7605d28e /libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c | |
parent | Add the skeleton. (diff) | |
download | SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.zip SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.tar.gz SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.tar.bz2 SledjHamr-dd7595a3475407a7fa96a97393bae8c5220e8762.tar.xz |
Add the base Enlightenment Foundation Libraries - eina, eet, evas, ecore, embryo, and edje.
Note that embryo wont be used, but I'm not sure yet if you can build edje without it.
Diffstat (limited to 'libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c')
-rw-r--r-- | libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c | 547 |
1 files changed, 547 insertions, 0 deletions
diff --git a/libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c b/libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c new file mode 100644 index 0000000..009b62b --- /dev/null +++ b/libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c | |||
@@ -0,0 +1,547 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2008-2010 Cedric BAIL, Vincent Torri | ||
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 | #ifdef HAVE_CONFIG_H | ||
20 | # include "config.h" | ||
21 | #endif | ||
22 | |||
23 | #include <stdlib.h> | ||
24 | #include <string.h> | ||
25 | |||
26 | #ifdef EFL_HAVE_POSIX_THREADS | ||
27 | #include <pthread.h> | ||
28 | |||
29 | # ifdef EFL_DEBUG_THREADS | ||
30 | # include <assert.h> | ||
31 | # endif | ||
32 | #endif | ||
33 | |||
34 | #ifdef EFL_HAVE_WIN32_THREADS | ||
35 | # define WIN32_LEAN_AND_MEAN | ||
36 | # include <windows.h> | ||
37 | # undef WIN32_LEAN_AND_MEAN | ||
38 | #endif | ||
39 | |||
40 | #include "eina_inlist.h" | ||
41 | #include "eina_error.h" | ||
42 | #include "eina_module.h" | ||
43 | #include "eina_mempool.h" | ||
44 | #include "eina_trash.h" | ||
45 | #include "eina_rbtree.h" | ||
46 | #include "eina_lock.h" | ||
47 | |||
48 | #include "eina_private.h" | ||
49 | |||
50 | #ifndef NVALGRIND | ||
51 | # include <valgrind/memcheck.h> | ||
52 | #endif | ||
53 | |||
54 | #ifdef DEBUG | ||
55 | #include <assert.h> | ||
56 | #include "eina_log.h" | ||
57 | |||
58 | static int _eina_chained_mp_log_dom = -1; | ||
59 | |||
60 | #ifdef INF | ||
61 | #undef INF | ||
62 | #endif | ||
63 | #define INF(...) EINA_LOG_DOM_INFO(_eina_chained_mp_log_dom, __VA_ARGS__) | ||
64 | #endif | ||
65 | |||
66 | typedef struct _Chained_Mempool Chained_Mempool; | ||
67 | struct _Chained_Mempool | ||
68 | { | ||
69 | Eina_Inlist *first; | ||
70 | Eina_Rbtree *root; | ||
71 | const char *name; | ||
72 | int item_alloc; | ||
73 | int pool_size; | ||
74 | int alloc_size; | ||
75 | int group_size; | ||
76 | int usage; | ||
77 | #ifdef EFL_DEBUG_THREADS | ||
78 | pthread_t self; | ||
79 | #endif | ||
80 | Eina_Lock mutex; | ||
81 | }; | ||
82 | |||
83 | typedef struct _Chained_Pool Chained_Pool; | ||
84 | struct _Chained_Pool | ||
85 | { | ||
86 | EINA_INLIST; | ||
87 | EINA_RBTREE; | ||
88 | Eina_Trash *base; | ||
89 | int usage; | ||
90 | |||
91 | unsigned char *last; | ||
92 | unsigned char *limit; | ||
93 | }; | ||
94 | |||
95 | static inline Eina_Rbtree_Direction | ||
96 | _eina_chained_mp_pool_cmp(const Eina_Rbtree *left, const Eina_Rbtree *right, __UNUSED__ void *data) | ||
97 | { | ||
98 | if (left < right) return EINA_RBTREE_LEFT; | ||
99 | return EINA_RBTREE_RIGHT; | ||
100 | } | ||
101 | |||
102 | static inline int | ||
103 | _eina_chained_mp_pool_key_cmp(const Eina_Rbtree *node, const void *key, | ||
104 | __UNUSED__ int length, __UNUSED__ void *data) | ||
105 | { | ||
106 | const Chained_Pool *r = EINA_RBTREE_CONTAINER_GET(node, const Chained_Pool); | ||
107 | |||
108 | if (key > (void *) r->limit) return -1; | ||
109 | if (key < (void *) r) return 1; | ||
110 | return 0; | ||
111 | } | ||
112 | |||
113 | static inline Chained_Pool * | ||
114 | _eina_chained_mp_pool_new(Chained_Mempool *pool) | ||
115 | { | ||
116 | Chained_Pool *p; | ||
117 | unsigned char *ptr; | ||
118 | unsigned int alignof; | ||
119 | |||
120 | eina_error_set(0); | ||
121 | p = malloc(pool->alloc_size); | ||
122 | if (!p) | ||
123 | { | ||
124 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
125 | return NULL; | ||
126 | } | ||
127 | |||
128 | alignof = eina_mempool_alignof(sizeof(Chained_Pool)); | ||
129 | ptr = (unsigned char *)p + alignof; | ||
130 | p->usage = 0; | ||
131 | p->base = NULL; | ||
132 | |||
133 | p->last = ptr; | ||
134 | p->limit = ptr + pool->item_alloc * pool->pool_size; | ||
135 | |||
136 | #ifndef NVALGRIND | ||
137 | VALGRIND_MAKE_MEM_NOACCESS(ptr, pool->alloc_size - alignof); | ||
138 | #endif | ||
139 | |||
140 | return p; | ||
141 | } | ||
142 | |||
143 | static inline void | ||
144 | _eina_chained_mp_pool_free(Chained_Pool *p) | ||
145 | { | ||
146 | free(p); | ||
147 | } | ||
148 | |||
149 | static int | ||
150 | _eina_chained_mempool_usage_cmp(const Eina_Inlist *l1, const Eina_Inlist *l2) | ||
151 | { | ||
152 | const Chained_Pool *p1; | ||
153 | const Chained_Pool *p2; | ||
154 | |||
155 | p1 = EINA_INLIST_CONTAINER_GET(l1, const Chained_Pool); | ||
156 | p2 = EINA_INLIST_CONTAINER_GET(l2, const Chained_Pool); | ||
157 | |||
158 | return p2->usage - p1->usage; | ||
159 | } | ||
160 | |||
161 | static void * | ||
162 | _eina_chained_mempool_alloc_in(Chained_Mempool *pool, Chained_Pool *p) | ||
163 | { | ||
164 | void *mem; | ||
165 | |||
166 | if (p->last) | ||
167 | { | ||
168 | mem = p->last; | ||
169 | p->last += pool->item_alloc; | ||
170 | if (p->last >= p->limit) | ||
171 | p->last = NULL; | ||
172 | } | ||
173 | else | ||
174 | { | ||
175 | #ifndef NVALGRIND | ||
176 | VALGRIND_MAKE_MEM_DEFINED(p->base, pool->item_alloc); | ||
177 | #endif | ||
178 | // Request a free pointer | ||
179 | mem = eina_trash_pop(&p->base); | ||
180 | } | ||
181 | |||
182 | // move to end - it just filled up | ||
183 | if (!p->base && !p->last) | ||
184 | pool->first = eina_inlist_demote(pool->first, EINA_INLIST_GET(p)); | ||
185 | |||
186 | p->usage++; | ||
187 | pool->usage++; | ||
188 | |||
189 | #ifndef NVALGRIND | ||
190 | VALGRIND_MEMPOOL_ALLOC(pool, mem, pool->item_alloc); | ||
191 | #endif | ||
192 | |||
193 | return mem; | ||
194 | } | ||
195 | |||
196 | static Eina_Bool | ||
197 | _eina_chained_mempool_free_in(Chained_Mempool *pool, Chained_Pool *p, void *ptr) | ||
198 | { | ||
199 | void *pmem; | ||
200 | |||
201 | // pool mem base | ||
202 | pmem = (void *)(((unsigned char *)p) + sizeof(Chained_Pool)); | ||
203 | |||
204 | // is it in pool mem? | ||
205 | if (ptr < pmem) | ||
206 | { | ||
207 | #ifdef DEBUG | ||
208 | INF("%p is inside the private part of %p pool from %p Chained_Mempool (could be the sign of a buffer underrun).", ptr, p, pool); | ||
209 | #endif | ||
210 | return EINA_FALSE; | ||
211 | } | ||
212 | |||
213 | // freed node points to prev free node | ||
214 | eina_trash_push(&p->base, ptr); | ||
215 | // next free node is now the one we freed | ||
216 | p->usage--; | ||
217 | pool->usage--; | ||
218 | if (p->usage == 0) | ||
219 | { | ||
220 | // free bucket | ||
221 | pool->first = eina_inlist_remove(pool->first, EINA_INLIST_GET(p)); | ||
222 | pool->root = eina_rbtree_inline_remove(pool->root, EINA_RBTREE_GET(p), | ||
223 | _eina_chained_mp_pool_cmp, NULL); | ||
224 | _eina_chained_mp_pool_free(p); | ||
225 | |||
226 | return EINA_TRUE; | ||
227 | } | ||
228 | else | ||
229 | { | ||
230 | // move to front | ||
231 | pool->first = eina_inlist_promote(pool->first, EINA_INLIST_GET(p)); | ||
232 | } | ||
233 | |||
234 | return EINA_FALSE; | ||
235 | } | ||
236 | |||
237 | static void * | ||
238 | eina_chained_mempool_malloc(void *data, __UNUSED__ unsigned int size) | ||
239 | { | ||
240 | Chained_Mempool *pool = data; | ||
241 | Chained_Pool *p = NULL; | ||
242 | void *mem; | ||
243 | |||
244 | if (!eina_lock_take(&pool->mutex)) | ||
245 | { | ||
246 | #ifdef EFL_DEBUG_THREADS | ||
247 | assert(pthread_equal(pool->self, pthread_self())); | ||
248 | #endif | ||
249 | } | ||
250 | |||
251 | // Either we have some free space in the first one, or there is no free space. | ||
252 | if (pool->first) p = EINA_INLIST_CONTAINER_GET(pool->first, Chained_Pool); | ||
253 | |||
254 | // base is not NULL - has a free slot | ||
255 | if (p && !p->base && !p->last) | ||
256 | p = NULL; | ||
257 | |||
258 | #ifdef DEBUG | ||
259 | if (p == NULL) | ||
260 | EINA_INLIST_FOREACH(pool->first, p) | ||
261 | assert(!p->base && !p->last); | ||
262 | #endif | ||
263 | |||
264 | // we have reached the end of the list - no free pools | ||
265 | if (!p) | ||
266 | { | ||
267 | p = _eina_chained_mp_pool_new(pool); | ||
268 | if (!p) | ||
269 | { | ||
270 | eina_lock_release(&pool->mutex); | ||
271 | return NULL; | ||
272 | } | ||
273 | |||
274 | pool->first = eina_inlist_prepend(pool->first, EINA_INLIST_GET(p)); | ||
275 | pool->root = eina_rbtree_inline_insert(pool->root, EINA_RBTREE_GET(p), | ||
276 | _eina_chained_mp_pool_cmp, NULL); | ||
277 | } | ||
278 | |||
279 | mem = _eina_chained_mempool_alloc_in(pool, p); | ||
280 | |||
281 | eina_lock_release(&pool->mutex); | ||
282 | |||
283 | return mem; | ||
284 | } | ||
285 | |||
286 | static void | ||
287 | eina_chained_mempool_free(void *data, void *ptr) | ||
288 | { | ||
289 | Chained_Mempool *pool = data; | ||
290 | Eina_Rbtree *r; | ||
291 | Chained_Pool *p; | ||
292 | |||
293 | // look 4 pool | ||
294 | if (!eina_lock_take(&pool->mutex)) | ||
295 | { | ||
296 | #ifdef EFL_DEBUG_THREADS | ||
297 | assert(pthread_equal(pool->self, pthread_self())); | ||
298 | #endif | ||
299 | } | ||
300 | |||
301 | // searching for the right mempool | ||
302 | r = eina_rbtree_inline_lookup(pool->root, ptr, 0, _eina_chained_mp_pool_key_cmp, NULL); | ||
303 | |||
304 | // related mempool not found | ||
305 | if (!r) | ||
306 | { | ||
307 | #ifdef DEBUG | ||
308 | INF("%p is not the property of %p Chained_Mempool", ptr, pool); | ||
309 | #endif | ||
310 | goto on_error; | ||
311 | } | ||
312 | |||
313 | p = EINA_RBTREE_CONTAINER_GET(r, Chained_Pool); | ||
314 | |||
315 | _eina_chained_mempool_free_in(pool, p, ptr); | ||
316 | |||
317 | on_error: | ||
318 | #ifndef NVALGRIND | ||
319 | if (ptr) | ||
320 | { | ||
321 | VALGRIND_MEMPOOL_FREE(pool, ptr); | ||
322 | } | ||
323 | #endif | ||
324 | |||
325 | eina_lock_release(&pool->mutex); | ||
326 | return; | ||
327 | } | ||
328 | |||
329 | static void | ||
330 | eina_chained_mempool_repack(void *data, | ||
331 | Eina_Mempool_Repack_Cb cb, | ||
332 | void *cb_data) | ||
333 | { | ||
334 | Chained_Mempool *pool = data; | ||
335 | Chained_Pool *start; | ||
336 | Chained_Pool *tail; | ||
337 | |||
338 | /* FIXME: Improvement - per Chained_Pool lock */ | ||
339 | if (!eina_lock_take(&pool->mutex)) | ||
340 | { | ||
341 | #ifdef EFL_DEBUG_THREADS | ||
342 | assert(pthread_equal(pool->self, pthread_self())); | ||
343 | #endif | ||
344 | } | ||
345 | |||
346 | pool->first = eina_inlist_sort(pool->first, | ||
347 | (Eina_Compare_Cb) _eina_chained_mempool_usage_cmp); | ||
348 | |||
349 | /* | ||
350 | idea : remove the almost empty pool at the beginning of the list by | ||
351 | moving data in the last pool with empty slot | ||
352 | */ | ||
353 | tail = EINA_INLIST_CONTAINER_GET(pool->first->last, Chained_Pool); | ||
354 | while (tail && tail->usage == pool->pool_size) | ||
355 | tail = EINA_INLIST_CONTAINER_GET((EINA_INLIST_GET(tail)->prev), Chained_Pool); | ||
356 | |||
357 | while (tail) | ||
358 | { | ||
359 | unsigned char *src; | ||
360 | unsigned char *dst; | ||
361 | |||
362 | start = EINA_INLIST_CONTAINER_GET(pool->first, Chained_Pool); | ||
363 | |||
364 | if (start == tail || start->usage == pool->pool_size) | ||
365 | break; | ||
366 | |||
367 | for (src = start->limit - pool->group_size; | ||
368 | src != start->limit; | ||
369 | src += pool->item_alloc) | ||
370 | { | ||
371 | Eina_Bool is_free = EINA_FALSE; | ||
372 | Eina_Bool is_dead; | ||
373 | |||
374 | /* Do we have something inside that piece of memory */ | ||
375 | if (start->last != NULL && src >= start->last) | ||
376 | { | ||
377 | is_free = EINA_TRUE; | ||
378 | } | ||
379 | else | ||
380 | { | ||
381 | Eina_Trash *over = start->base; | ||
382 | |||
383 | while (over != NULL && (unsigned char*) over != src) | ||
384 | over = over->next; | ||
385 | |||
386 | if (over == NULL) | ||
387 | is_free = EINA_TRUE; | ||
388 | } | ||
389 | |||
390 | if (is_free) continue ; | ||
391 | |||
392 | /* get a new memory pointer from the latest most occuped pool */ | ||
393 | dst = _eina_chained_mempool_alloc_in(pool, tail); | ||
394 | /* move data from one to another */ | ||
395 | memcpy(dst, src, pool->item_alloc); | ||
396 | /* notify caller */ | ||
397 | cb(dst, src, cb_data); | ||
398 | /* destroy old pointer */ | ||
399 | is_dead = _eina_chained_mempool_free_in(pool, start, src); | ||
400 | |||
401 | /* search last tail with empty slot */ | ||
402 | while (tail && tail->usage == pool->pool_size) | ||
403 | tail = EINA_INLIST_CONTAINER_GET((EINA_INLIST_GET(tail)->prev), | ||
404 | Chained_Pool); | ||
405 | /* no more free space */ | ||
406 | if (!tail || tail == start) break; | ||
407 | if (is_dead) break; | ||
408 | } | ||
409 | } | ||
410 | |||
411 | /* FIXME: improvement - reorder pool so that the most used one get in front */ | ||
412 | eina_lock_release(&pool->mutex); | ||
413 | } | ||
414 | |||
415 | static void * | ||
416 | eina_chained_mempool_realloc(__UNUSED__ void *data, | ||
417 | __UNUSED__ void *element, | ||
418 | __UNUSED__ unsigned int size) | ||
419 | { | ||
420 | return NULL; | ||
421 | } | ||
422 | |||
423 | static void * | ||
424 | eina_chained_mempool_init(const char *context, | ||
425 | __UNUSED__ const char *option, | ||
426 | va_list args) | ||
427 | { | ||
428 | Chained_Mempool *mp; | ||
429 | int item_size; | ||
430 | size_t length; | ||
431 | |||
432 | length = context ? strlen(context) + 1 : 0; | ||
433 | |||
434 | mp = calloc(1, sizeof(Chained_Mempool) + length); | ||
435 | if (!mp) | ||
436 | return NULL; | ||
437 | |||
438 | item_size = va_arg(args, int); | ||
439 | mp->pool_size = va_arg(args, int); | ||
440 | |||
441 | if (length) | ||
442 | { | ||
443 | mp->name = (const char *)(mp + 1); | ||
444 | memcpy((char *)mp->name, context, length); | ||
445 | } | ||
446 | |||
447 | mp->item_alloc = eina_mempool_alignof(item_size); | ||
448 | mp->group_size = mp->item_alloc * mp->pool_size; | ||
449 | mp->alloc_size = mp->group_size + eina_mempool_alignof(sizeof(Chained_Pool)); | ||
450 | |||
451 | #ifndef NVALGRIND | ||
452 | VALGRIND_CREATE_MEMPOOL(mp, 0, 1); | ||
453 | #endif | ||
454 | |||
455 | #ifdef EFL_DEBUG_THREADS | ||
456 | mp->self = pthread_self(); | ||
457 | #endif | ||
458 | |||
459 | eina_lock_new(&mp->mutex); | ||
460 | |||
461 | return mp; | ||
462 | } | ||
463 | |||
464 | static void | ||
465 | eina_chained_mempool_shutdown(void *data) | ||
466 | { | ||
467 | Chained_Mempool *mp; | ||
468 | |||
469 | mp = (Chained_Mempool *)data; | ||
470 | |||
471 | while (mp->first) | ||
472 | { | ||
473 | Chained_Pool *p = (Chained_Pool *)mp->first; | ||
474 | |||
475 | #ifdef DEBUG | ||
476 | if (p->usage > 0) | ||
477 | INF("Bad news we are destroying not an empty mempool [%s]\n", | ||
478 | mp->name); | ||
479 | |||
480 | #endif | ||
481 | |||
482 | mp->first = eina_inlist_remove(mp->first, mp->first); | ||
483 | mp->root = eina_rbtree_inline_remove(mp->root, EINA_RBTREE_GET(p), | ||
484 | _eina_chained_mp_pool_cmp, NULL); | ||
485 | _eina_chained_mp_pool_free(p); | ||
486 | } | ||
487 | |||
488 | #ifdef DEBUG | ||
489 | if (mp->root) | ||
490 | INF("Bad news, list of pool and rbtree are out of sync for %p !", mp); | ||
491 | #endif | ||
492 | |||
493 | #ifndef NVALGRIND | ||
494 | VALGRIND_DESTROY_MEMPOOL(mp); | ||
495 | #endif | ||
496 | |||
497 | eina_lock_free(&mp->mutex); | ||
498 | |||
499 | #ifdef EFL_DEBUG_THREADS | ||
500 | assert(pthread_equal(mp->self, pthread_self())); | ||
501 | #endif | ||
502 | |||
503 | free(mp); | ||
504 | } | ||
505 | |||
506 | static Eina_Mempool_Backend _eina_chained_mp_backend = { | ||
507 | "chained_mempool", | ||
508 | &eina_chained_mempool_init, | ||
509 | &eina_chained_mempool_free, | ||
510 | &eina_chained_mempool_malloc, | ||
511 | &eina_chained_mempool_realloc, | ||
512 | NULL, | ||
513 | NULL, | ||
514 | &eina_chained_mempool_shutdown, | ||
515 | &eina_chained_mempool_repack | ||
516 | }; | ||
517 | |||
518 | Eina_Bool chained_init(void) | ||
519 | { | ||
520 | #ifdef DEBUG | ||
521 | _eina_chained_mp_log_dom = eina_log_domain_register("eina_mempool", | ||
522 | EINA_LOG_COLOR_DEFAULT); | ||
523 | if (_eina_chained_mp_log_dom < 0) | ||
524 | { | ||
525 | EINA_LOG_ERR("Could not register log domain: eina_mempool"); | ||
526 | return EINA_FALSE; | ||
527 | } | ||
528 | |||
529 | #endif | ||
530 | return eina_mempool_register(&_eina_chained_mp_backend); | ||
531 | } | ||
532 | |||
533 | void chained_shutdown(void) | ||
534 | { | ||
535 | eina_mempool_unregister(&_eina_chained_mp_backend); | ||
536 | #ifdef DEBUG | ||
537 | eina_log_domain_unregister(_eina_chained_mp_log_dom); | ||
538 | _eina_chained_mp_log_dom = -1; | ||
539 | #endif | ||
540 | } | ||
541 | |||
542 | #ifndef EINA_STATIC_BUILD_CHAINED_POOL | ||
543 | |||
544 | EINA_MODULE_INIT(chained_init); | ||
545 | EINA_MODULE_SHUTDOWN(chained_shutdown); | ||
546 | |||
547 | #endif /* ! EINA_STATIC_BUILD_CHAINED_POOL */ | ||