src/modules/mp/buddy/eina_buddy.c

   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 */