path: root/libraries/eina/src/modules/mp/chained_pool/eina_chained_mempool.c

/* EINA - EFL data type library
 * Copyright (C) 2008-2010 Cedric BAIL, Vincent Torri
 *
 * 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 <http://www.gnu.org/licenses/>.
 */

#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#include <stdlib.h>
#include <string.h>

#ifdef EFL_HAVE_POSIX_THREADS
#include <pthread.h>

# ifdef EFL_DEBUG_THREADS
#  include <assert.h>
# endif
#endif

#ifdef EINA_DEBUG_MALLOC
# include <malloc.h>
#endif

#ifdef EFL_HAVE_WIN32_THREADS
# define WIN32_LEAN_AND_MEAN
# include <windows.h>
# undef WIN32_LEAN_AND_MEAN
#endif

#include "eina_inlist.h"
#include "eina_error.h"
#include "eina_module.h"
#include "eina_mempool.h"
#include "eina_trash.h"
#include "eina_rbtree.h"
#include "eina_lock.h"

#include "eina_private.h"

#ifndef NVALGRIND
# include <memcheck.h>
#endif

#if defined DEBUG || defined EINA_DEBUG_MALLOC
#include <assert.h>
#include "eina_log.h"

static int _eina_chained_mp_log_dom = -1;

#ifdef INF
#undef INF
#endif
#define INF(...) EINA_LOG_DOM_INFO(_eina_chained_mp_log_dom, __VA_ARGS__)
#endif

typedef struct _Chained_Mempool Chained_Mempool;
struct _Chained_Mempool
{
   Eina_Inlist *first;
   Eina_Rbtree *root;
   const char *name;
   int item_alloc;
   int pool_size;
   int alloc_size;
   int group_size;
   int usage;
#ifdef EINA_DEBUG_MALLOC
   int minimal_size;
#endif
#ifdef EFL_DEBUG_THREADS
   pthread_t self;
#endif
   Eina_Lock mutex;
};

typedef struct _Chained_Pool Chained_Pool;
struct _Chained_Pool
{
   EINA_INLIST;
   EINA_RBTREE;
   Eina_Trash *base;
   int usage;

   unsigned char *last;
   unsigned char *limit;
};

static inline Eina_Rbtree_Direction
_eina_chained_mp_pool_cmp(const Eina_Rbtree *left, const Eina_Rbtree *right, __UNUSED__ void *data)
{
   if (left < right) return EINA_RBTREE_LEFT;
   return EINA_RBTREE_RIGHT;
}

static inline int
_eina_chained_mp_pool_key_cmp(const Eina_Rbtree *node, const void *key,
                              __UNUSED__ int length, __UNUSED__ void *data)
{
   const Chained_Pool *r = EINA_RBTREE_CONTAINER_GET(node, const Chained_Pool);

   if (key > (void *) r->limit) return -1;
   if (key < (void *) r) return 1;
   return 0;
}

static inline Chained_Pool *
_eina_chained_mp_pool_new(Chained_Mempool *pool)
{
   Chained_Pool *p;
   unsigned char *ptr;
   unsigned int alignof;

   eina_error_set(0);
   p = malloc(pool->alloc_size);
   if (!p)
     {
        eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
        return NULL;
     }

#ifdef EINA_DEBUG_MALLOC
   {
      size_t sz;

      sz = malloc_usable_size(p);
      if (sz - pool->minimal_size > 0)
        INF("Just allocated %0.2f%% to much memory in '%s' for one block of size %i that means %i bytes to much.",
            ((float)(sz - pool->minimal_size) * 100) / (float) (pool->alloc_size),
            pool->name,
            pool->alloc_size,
            sz - pool->minimal_size);
   }
#endif

   alignof = eina_mempool_alignof(sizeof(Chained_Pool));
   ptr = (unsigned char *)p + alignof;
   p->usage = 0;
   p->base = NULL;

   p->last = ptr;
   p->limit = ptr + pool->item_alloc * pool->pool_size;

#ifndef NVALGRIND
   VALGRIND_MAKE_MEM_NOACCESS(ptr, pool->alloc_size - alignof);
#endif

   return p;
}

static inline void
_eina_chained_mp_pool_free(Chained_Pool *p)
{
   free(p);
}

static int
_eina_chained_mempool_usage_cmp(const Eina_Inlist *l1, const Eina_Inlist *l2)
{
  const Chained_Pool *p1;
  const Chained_Pool *p2;

  p1 = EINA_INLIST_CONTAINER_GET(l1, const Chained_Pool);
  p2 = EINA_INLIST_CONTAINER_GET(l2, const Chained_Pool);

  return p2->usage - p1->usage;
}

static void *
_eina_chained_mempool_alloc_in(Chained_Mempool *pool, Chained_Pool *p)
{
  void *mem;

  if (p->last)
    {
      mem = p->last;
      p->last += pool->item_alloc;
      if (p->last >= p->limit)
	p->last = NULL;
    }
  else
    {
#ifndef NVALGRIND
      VALGRIND_MAKE_MEM_DEFINED(p->base, pool->item_alloc);
#endif
      // Request a free pointer
      mem = eina_trash_pop(&p->base);
    }
  
  // move to end - it just filled up
  if (!p->base && !p->last)
    pool->first = eina_inlist_demote(pool->first, EINA_INLIST_GET(p));
  
  p->usage++;
  pool->usage++;

#ifndef NVALGRIND
   VALGRIND_MEMPOOL_ALLOC(pool, mem, pool->item_alloc);
#endif

  return mem;
}

static Eina_Bool
_eina_chained_mempool_free_in(Chained_Mempool *pool, Chained_Pool *p, void *ptr)
{
   void *pmem;
  
   // pool mem base
   pmem = (void *)(((unsigned char *)p) + sizeof(Chained_Pool));

   // is it in pool mem?
   if (ptr < pmem)
     {
#ifdef DEBUG
        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);
#endif
        return EINA_FALSE;
     }

   // freed node points to prev free node
   eina_trash_push(&p->base, ptr);
   // next free node is now the one we freed
   p->usage--;
   pool->usage--;
   if (p->usage == 0)
     {
        // free bucket
        pool->first = eina_inlist_remove(pool->first, EINA_INLIST_GET(p));
        pool->root = eina_rbtree_inline_remove(pool->root, EINA_RBTREE_GET(p),
                                               _eina_chained_mp_pool_cmp, NULL);
        _eina_chained_mp_pool_free(p);

	return EINA_TRUE;
     }
   else
     {
        // move to front
        pool->first = eina_inlist_promote(pool->first, EINA_INLIST_GET(p));
     }

   return EINA_FALSE;
}

static void *
eina_chained_mempool_malloc(void *data, __UNUSED__ unsigned int size)
{
   Chained_Mempool *pool = data;
   Chained_Pool *p = NULL;
   void *mem;

   if (!eina_lock_take(&pool->mutex))
     {
#ifdef EFL_DEBUG_THREADS
        assert(pthread_equal(pool->self, pthread_self()));
#endif
     }

   // Either we have some free space in the first one, or there is no free space.
   if (pool->first) p = EINA_INLIST_CONTAINER_GET(pool->first, Chained_Pool);

   // base is not NULL - has a free slot
   if (p && !p->base && !p->last)
     p = NULL;

#ifdef DEBUG
   if (p == NULL)
     EINA_INLIST_FOREACH(pool->first, p)
       assert(!p->base && !p->last);
#endif

   // we have reached the end of the list - no free pools
   if (!p)
     {
        p = _eina_chained_mp_pool_new(pool);
        if (!p)
          {
             eina_lock_release(&pool->mutex);
             return NULL;
          }

        pool->first = eina_inlist_prepend(pool->first, EINA_INLIST_GET(p));
        pool->root = eina_rbtree_inline_insert(pool->root, EINA_RBTREE_GET(p),
                                               _eina_chained_mp_pool_cmp, NULL);
     }

   mem = _eina_chained_mempool_alloc_in(pool, p);

   eina_lock_release(&pool->mutex);

   return mem;
}

static void
eina_chained_mempool_free(void *data, void *ptr)
{
   Chained_Mempool *pool = data;
   Eina_Rbtree *r;
   Chained_Pool *p;

   // look 4 pool
   if (!eina_lock_take(&pool->mutex))
     {
#ifdef EFL_DEBUG_THREADS
        assert(pthread_equal(pool->self, pthread_self()));
#endif
     }

   // searching for the right mempool
   r = eina_rbtree_inline_lookup(pool->root, ptr, 0, _eina_chained_mp_pool_key_cmp, NULL);

   // related mempool not found
   if (!r)
     {
#ifdef DEBUG
        INF("%p is not the property of %p Chained_Mempool", ptr, pool);
#endif
        goto on_error;
     }

   p = EINA_RBTREE_CONTAINER_GET(r, Chained_Pool);

   _eina_chained_mempool_free_in(pool, p, ptr);

 on_error:
#ifndef NVALGRIND
   if (ptr)
     {
        VALGRIND_MEMPOOL_FREE(pool, ptr);
     }
#endif

   eina_lock_release(&pool->mutex);
   return;
}

static void
eina_chained_mempool_repack(void *data,
			    Eina_Mempool_Repack_Cb cb,
			    void *cb_data)
{
  Chained_Mempool *pool = data;
  Chained_Pool *start;
  Chained_Pool *tail;

  /* FIXME: Improvement - per Chained_Pool lock */
   if (!eina_lock_take(&pool->mutex))
     {
#ifdef EFL_DEBUG_THREADS
        assert(pthread_equal(pool->self, pthread_self()));
#endif
     }

   pool->first = eina_inlist_sort(pool->first,
				  (Eina_Compare_Cb) _eina_chained_mempool_usage_cmp);

   /*
     idea : remove the almost empty pool at the beginning of the list by
     moving data in the last pool with empty slot
    */
   tail = EINA_INLIST_CONTAINER_GET(pool->first->last, Chained_Pool);
   while (tail && tail->usage == pool->pool_size)
     tail = EINA_INLIST_CONTAINER_GET((EINA_INLIST_GET(tail)->prev), Chained_Pool);

   while (tail)
     {
       unsigned char *src;
       unsigned char *dst;

       start = EINA_INLIST_CONTAINER_GET(pool->first, Chained_Pool);

       if (start == tail || start->usage == pool->pool_size)
	 break;

       for (src = start->limit - pool->group_size;
	    src != start->limit;
	    src += pool->item_alloc)
	 {
	   Eina_Bool is_free = EINA_FALSE;
	   Eina_Bool is_dead;

	   /* Do we have something inside that piece of memory */
	   if (start->last != NULL && src >= start->last)
	     {
	       is_free = EINA_TRUE;
	     }
	   else
	     {
	       Eina_Trash *over = start->base;

	       while (over != NULL && (unsigned char*) over != src)
		 over = over->next;

	       if (over == NULL)
		 is_free = EINA_TRUE;
	     }

	   if (is_free) continue ;

	   /* get a new memory pointer from the latest most occuped pool */
	   dst = _eina_chained_mempool_alloc_in(pool, tail);
	   /* move data from one to another */
	   memcpy(dst, src, pool->item_alloc);
	   /* notify caller */
	   cb(dst, src, cb_data);
	   /* destroy old pointer */
	   is_dead = _eina_chained_mempool_free_in(pool, start, src);

	   /* search last tail with empty slot */
	   while (tail && tail->usage == pool->pool_size)
	     tail = EINA_INLIST_CONTAINER_GET((EINA_INLIST_GET(tail)->prev),
					      Chained_Pool);
	   /* no more free space */
	   if (!tail || tail == start) break;
	   if (is_dead) break;
	 }
     }

   /* FIXME: improvement - reorder pool so that the most used one get in front */
   eina_lock_release(&pool->mutex);
}

static void *
eina_chained_mempool_realloc(__UNUSED__ void *data,
                             __UNUSED__ void *element,
                             __UNUSED__ unsigned int size)
{
   return NULL;
}

static void *
eina_chained_mempool_init(const char *context,
                          __UNUSED__ const char *option,
                          va_list args)
{
   Chained_Mempool *mp;
   int item_size;
   size_t length;

   length = context ? strlen(context) + 1 : 0;

   mp = calloc(1, sizeof(Chained_Mempool) + length);
   if (!mp)
      return NULL;

   item_size = va_arg(args, int);
   mp->pool_size = va_arg(args, int);

   if (length)
     {
        mp->name = (const char *)(mp + 1);
        memcpy((char *)mp->name, context, length);
     }

#ifdef EINA_DEBUG_MALLOC
   mp->minimal_size = item_size * mp->pool_size + sizeof(Chained_Pool);
#endif

   mp->item_alloc = eina_mempool_alignof(item_size);
   mp->group_size = mp->item_alloc * mp->pool_size;
   mp->alloc_size = mp->group_size + eina_mempool_alignof(sizeof(Chained_Pool));

#ifndef NVALGRIND
   VALGRIND_CREATE_MEMPOOL(mp, 0, 1);
#endif

#ifdef EFL_DEBUG_THREADS
   mp->self = pthread_self();
#endif

   eina_lock_new(&mp->mutex);

   return mp;
}

static void
eina_chained_mempool_shutdown(void *data)
{
   Chained_Mempool *mp;

   mp = (Chained_Mempool *)data;

   while (mp->first)
     {
        Chained_Pool *p = (Chained_Pool *)mp->first;

#ifdef DEBUG
        if (p->usage > 0)
           INF("Bad news we are destroying not an empty mempool [%s]\n",
               mp->name);

#endif

        mp->first = eina_inlist_remove(mp->first, mp->first);
        mp->root = eina_rbtree_inline_remove(mp->root, EINA_RBTREE_GET(p),
                                             _eina_chained_mp_pool_cmp, NULL);
        _eina_chained_mp_pool_free(p);
     }

#ifdef DEBUG
   if (mp->root)
     INF("Bad news, list of pool and rbtree are out of sync for %p !", mp);
#endif

#ifndef NVALGRIND
   VALGRIND_DESTROY_MEMPOOL(mp);
#endif

   eina_lock_free(&mp->mutex);

#ifdef EFL_DEBUG_THREADS
   assert(pthread_equal(mp->self, pthread_self()));
#endif

   free(mp);
}

static Eina_Mempool_Backend _eina_chained_mp_backend = {
   "chained_mempool",
   &eina_chained_mempool_init,
   &eina_chained_mempool_free,
   &eina_chained_mempool_malloc,
   &eina_chained_mempool_realloc,
   NULL,
   NULL,
   &eina_chained_mempool_shutdown,
   &eina_chained_mempool_repack
};

Eina_Bool chained_init(void)
{
#if defined DEBUG || defined EINA_DEBUG_MALLOC
   _eina_chained_mp_log_dom = eina_log_domain_register("eina_mempool",
                                                       EINA_LOG_COLOR_DEFAULT);
   if (_eina_chained_mp_log_dom < 0)
     {
        EINA_LOG_ERR("Could not register log domain: eina_mempool");
        return EINA_FALSE;
     }

#endif
   return eina_mempool_register(&_eina_chained_mp_backend);
}

void chained_shutdown(void)
{
   eina_mempool_unregister(&_eina_chained_mp_backend);
#if defined DEBUG || defined EINA_DEBUG_MALLOC
   eina_log_domain_unregister(_eina_chained_mp_log_dom);
   _eina_chained_mp_log_dom = -1;
#endif
}

#ifndef EINA_STATIC_BUILD_CHAINED_POOL

EINA_MODULE_INIT(chained_init);
EINA_MODULE_SHUTDOWN(chained_shutdown);

#endif /* ! EINA_STATIC_BUILD_CHAINED_POOL */