src/modules/mp/chained_pool/eina_chained_mempool.c

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