From 6fa29a75085184256d842966a81ab9bede197146 Mon Sep 17 00:00:00 2001 From: turran Date: Fri, 8 Jan 2010 12:10:14 +0000 Subject: [PATCH] + Add the efl-research buddy allocator here git-svn-id: http://svn.enlightenment.org/svn/e/trunk/eina@44976 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- configure.ac | 3 + src/lib/eina_mempool.c | 10 +- src/modules/mp/Makefile.am | 4 +- src/modules/mp/buddy/Makefile.am | 28 ++++ src/modules/mp/buddy/eina_buddy.c | 271 ++++++++++++++++++++++++++++++++++++++ 5 files changed, 312 insertions(+), 4 deletions(-) create mode 100644 src/modules/mp/buddy/Makefile.am create mode 100644 src/modules/mp/buddy/eina_buddy.c diff --git a/configure.ac b/configure.ac index f077927..5adf00c 100644 --- a/configure.ac +++ b/configure.ac @@ -399,6 +399,7 @@ EINA_CHECK_MODULE([ememoa-fixed], [${enable_ememoa}], [ememoa fixed]) EINA_CHECK_MODULE([ememoa-unknown], [${enable_ememoa}], [ememoa unknown]) EINA_CHECK_MODULE([fixed-bitmap], [yes], [fixed bitmap]) EINA_CHECK_MODULE([pass-through], [yes], [pass through]) +EINA_CHECK_MODULE([buddy], [yes], [buddy]) ### Make the debug preprocessor configurable @@ -453,6 +454,7 @@ src/modules/mp/ememoa_fixed/Makefile src/modules/mp/ememoa_unknown/Makefile src/modules/mp/pass_through/Makefile src/modules/mp/fixed_bitmap/Makefile +src/modules/mp/buddy/Makefile src/tests/Makefile ]) @@ -502,6 +504,7 @@ echo " Ememoa fixed.......: ${enable_ememoa_fixed}" echo " Ememoa unknown.....: ${enable_ememoa_unknown}" echo " Fixed bitmap.......: ${enable_fixed_bitmap}" echo " Pass through.......: ${enable_pass_through}" +echo " Buddy..............: ${enable_buddy}" echo echo "Compilation............: make (or gmake)" echo " CPPFLAGS.............: $CPPFLAGS" diff --git a/src/lib/eina_mempool.c b/src/lib/eina_mempool.c index 002a513..4934b96 100644 --- a/src/lib/eina_mempool.c +++ b/src/lib/eina_mempool.c @@ -60,7 +60,7 @@ static int _eina_mempool_log_dom = -1; static Eina_Mempool * -_new_from_buffer(const char *name, const char *context, const char *options, va_list args) +_new_va(const char *name, const char *context, const char *options, va_list args) { Eina_Mempool_Backend *be; Eina_Mempool *mp; @@ -202,6 +202,9 @@ eina_mempool_init(void) #ifdef EINA_STATIC_BUILD_FIXED_BITMAP fixed_bitmap_init(); #endif +#ifdef EINA_STATIC_BUILD_BUDDY + buddy_init(); +#endif return EINA_TRUE; @@ -231,6 +234,9 @@ eina_mempool_shutdown(void) #ifdef EINA_STATIC_BUILD_FIXED_BITMAP fixed_bitmap_shutdown(); #endif +#ifdef EINA_STATIC_BUILD_BUDDY + buddy_shutdown(); +#endif /* dynamic backends */ eina_module_list_flush(_modules); if (_modules) @@ -268,7 +274,7 @@ eina_mempool_add(const char *name, const char *context, const char *options, ... name, context ? context : "", options ? options : ""); va_start(args, options); - mp = _new_from_buffer(name, context, options, args); + mp = _new_va(name, context, options, args); va_end(args); DBG("name=%s, context=%s, options=%s, mp=%p", diff --git a/src/modules/mp/Makefile.am b/src/modules/mp/Makefile.am index 641127c..fd093b9 100644 --- a/src/modules/mp/Makefile.am +++ b/src/modules/mp/Makefile.am @@ -1,4 +1,4 @@ -SUBDIRS = chained_pool ememoa_fixed pass_through ememoa_unknown fixed_bitmap +SUBDIRS = chained_pool ememoa_fixed pass_through ememoa_unknown fixed_bitmap buddy MAINTAINERCLEANFILES = \ -Makefile.in \ No newline at end of file +Makefile.in diff --git a/src/modules/mp/buddy/Makefile.am b/src/modules/mp/buddy/Makefile.am new file mode 100644 index 0000000..2006d62 --- /dev/null +++ b/src/modules/mp/buddy/Makefile.am @@ -0,0 +1,28 @@ +MAINTAINERCLEANFILES = Makefile.in + +AM_CPPFLAGS = \ +-I. \ +-I$(top_srcdir)/src/include \ +-I$(top_builddir)/src/include \ +@EINA_CPPFLAGS@ \ +@EFL_EINA_BUILD@ + +if EINA_BUILD_BUDDY +if !EINA_STATIC_BUILD_BUDDY + +controllerdir = $(libdir)/eina/mp +controller_LTLIBRARIES = eina_buddy.la + +eina_buddy_la_SOURCES = \ +eina_buddy.c + +eina_buddy_la_CFLAGS = @EINA_CFLAGS@ +eina_buddy_la_LIBADD = $(top_builddir)/src/lib/libeina.la @EINA_LIBS@ +eina_buddy_la_LDFLAGS = -no-undefined @lt_enable_auto_import@ -module -avoid-version +eina_buddy_la_LIBTOOLFLAGS = --tag=disable-static + +endif +endif + +clean-local: + rm -rf *.gcno diff --git a/src/modules/mp/buddy/eina_buddy.c b/src/modules/mp/buddy/eina_buddy.c new file mode 100644 index 0000000..21cbd32 --- /dev/null +++ b/src/modules/mp/buddy/eina_buddy.c @@ -0,0 +1,271 @@ +/* EINA - EFL data type library + * Copyright (C) 2009 Jorge Luis Zapata Muga + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + */ + +/* + * This is a naive 'buddy' allocator following Knuth's documentation. + * The main difference is that we dont store the block information + * on the block memory itself but on another malloc'd area. + * This is useful for managing memory which isnt as fast as the main + * memory like the video memory + * The algorithm uses an area to store the linked list of blocks. + * Each block size is equal to the minimum allocatable block size for + * the memory pool and the number of blocks is equal to the size of the + * memory pool divided by the block size. + */ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include + +#include "eina_types.h" +#include "eina_inlist.h" +#include "eina_module.h" +#include "eina_mempool.h" +#include "eina_private.h" + +typedef struct _Block +{ + EINA_INLIST; + Eina_Bool available : 1; + unsigned short int order : 7; /* final order is order + min_order */ +} Block; + +typedef struct _Buddy +{ + void *heap; /* start address of the heap */ + size_t size; /* total size in bytes of the heap */ + unsigned int min_order; /* minimum size is 1 << min_order */ + unsigned int max_order; /* maximum size is 1 << max_order */ + unsigned int num_order; /* number of orders */ + Eina_Inlist **areas; /* one area per order */ + Block *blocks; /* the allocated block information */ +} Buddy; + +/* get the minimum order greater or equal to size */ +static inline unsigned int _get_order(Buddy *b, size_t size) +{ + unsigned int i; + size_t bytes; + + bytes = 1 << b->min_order; + for (i = 0; bytes < size && i < b->num_order; i++) + { + bytes += bytes; + } + //printf("order for size %d is %d\n", size, i + b->min_order); + return i; +} + +static inline void * _get_offset(Buddy *b, Block *block) +{ + void *ret; + + ret = (char *)b->heap + ((block - &b->blocks[0]) << b->min_order); + return ret; +} + +static void *_init(__UNUSED__ const char *context, __UNUSED__ const char *options, va_list args) +{ + Buddy *b; + int i; + size_t bytes; + size_t size; + size_t min_order; + void *heap; + + heap = va_arg(args, void *); + size = va_arg(args, size_t); + min_order = va_arg(args, int); + /* the minimum order we support is 15 (32K) */ + min_order = min_order < 15 ? 15 : min_order; + bytes = 1 << min_order; + for (i = 0; bytes <= size; i++) + { + bytes += bytes; + } + if (!i) + { + return NULL; + } + b = malloc(sizeof(Buddy)); + b->heap = heap; + b->size = size; + b->min_order = min_order; + b->max_order = min_order + i - 1; + b->num_order = i; + b->areas = calloc(b->num_order, sizeof(Eina_Inlist *)); + b->blocks = calloc(1 << (b->num_order - 1), sizeof(Block)); + /* setup the initial free area */ + b->blocks[0].available = EINA_TRUE; + b->areas[b->num_order - 1] = EINA_INLIST_GET(&(b->blocks[0])); + + return b; +} + +static void _shutdown(void *data) +{ + Buddy *b = data; + + free(b->blocks); + free(b->areas); + free(b); +} + +static void _free(void *data, void *element) +{ + Buddy *b = data; + Block *block, *buddy; + unsigned int offset; + unsigned int index; + + offset = element - b->heap; + if (offset > b->size) + return; + index = offset >> b->min_order; + block = &b->blocks[index]; + + //printf("free %x index = %d order = %d buddy = %d\n", offset, index, block->order, index ^ (1 << block->order)); + /* we should always work with the buddy at right */ + if (index & (1 << block->order)) + { + Block *left; + + index = index ^ (1 << block->order); + left = &b->blocks[index]; + if (!left->available) + goto end; + else + { + buddy = block; + block = left; + b->areas[block->order] = eina_inlist_remove(b->areas[block->order], EINA_INLIST_GET(block)); + block->order++; + } + } +check: + /* already on the last order */ + if (block->order + b->min_order == b->max_order) + goto end; + /* get the buddy */ + buddy = &b->blocks[index ^ (1 << block->order)]; + if (!buddy->available) + goto end; + /* merge two blocks */ + b->areas[block->order] = eina_inlist_remove(b->areas[block->order], EINA_INLIST_GET(buddy)); + block->order++; + goto check; +end: + /* add the block to the free list */ + block->available = EINA_TRUE; + b->areas[block->order] = eina_inlist_append(b->areas[block->order], EINA_INLIST_GET(block)); +} + +static void *_alloc(void *data, unsigned int size) +{ + Buddy *b = data; + Block *block, *buddy; + unsigned int k, j; + + k = j = _get_order(b, size); + /* get a free list of order k where k <= j <= max_order */ + while ((j < b->num_order) && !b->areas[j]) + j++; + /* check that the order is on our range */ + if (j + b->min_order > b->max_order) + return NULL; + + /* get a free element on this order, if not, go splitting until we find one */ + //printf("getting order %d (%d) for size %d\n", j, k, size); +found: + if (j == k) + { + void *ret; + + block = EINA_INLIST_CONTAINER_GET(b->areas[j], Block); + block->available = EINA_FALSE; + block->order = j; + /* remove the block from the list */ + b->areas[j] = eina_inlist_remove(b->areas[j], EINA_INLIST_GET(block)); + ret = _get_offset(b, block); + + return ret; + } + block = EINA_INLIST_CONTAINER_GET(b->areas[j], Block); + /* split */ + b->areas[j] = eina_inlist_remove(b->areas[j], EINA_INLIST_GET(block)); + j--; + b->areas[j] = eina_inlist_append(b->areas[j], EINA_INLIST_GET(block)); + buddy = block + (1 << j); + buddy->order = j; + buddy->available = EINA_TRUE; + b->areas[j] = eina_inlist_append(b->areas[j], EINA_INLIST_GET(buddy)); + + goto found; +} + +static void _statistics(void *data) +{ + Buddy *b = data; + unsigned int i; + + printf("Information:\n"); + printf("size = %d, min_order = %d, max_order = %d, num_order = %d, num_blocks = %d (%dKB)\n", b->size, b->min_order, b->max_order, b->num_order, 1 << b->num_order, ((1 << (b->num_order)) * sizeof(Block)) / 1024); + printf("Area dumping:"); + /* iterate over the free lists and dump the maps */ + for (i = 0; i < b->num_order; i++) + { + Block *block; + + printf("\n2^%d:", b->min_order + i); + EINA_INLIST_FOREACH(b->areas[i], block) + { + printf(" %d", (block - &b->blocks[0])); + } + } + printf("\nBlocks dumping:\n"); +} + +static Eina_Mempool_Backend _backend = { + "buddy", + &_init, + &_free, + &_alloc, + NULL, /* realloc */ + NULL, /* garbage collect */ + &_statistics, + &_shutdown +}; + +Eina_Bool buddy_init(void) +{ + return eina_mempool_register(&_backend); +} + +void buddy_shutdown(void) +{ + eina_mempool_unregister(&_backend); +} + + +#ifndef EINA_STATIC_BUILD_BUDDY + +EINA_MODULE_INIT(buddy_init); +EINA_MODULE_SHUTDOWN(buddy_shutdown); + +#endif /* ! EINA_STATIC_BUILD_BUDDY */ -- 2.7.4