malloc_cache.h

Go to the documentation of this file.

#ifndef TBCI_MALLOC_CACHE_H
#define TBCI_MALLOC_CACHE_H

#define MALLOC_CACHE 1

#ifndef HAVE_NO_NEW_HEADERS_BUG
# include <cstdio>
#else
# include <stdio.h>
#endif

#ifdef TBCI_MALLOC_STATS
# include <typeinfo>
#endif

#ifdef HAVE_MALLOC_ATTR 
# define MALLOC __attribute__((malloc))
#else
# define MALLOC 
#endif

#ifdef HAVE_MALLOC_H    // memalign
# include <malloc.h>
#endif

#if defined(SMP) && !defined(TBCI_MALLOC_NOLOCK)
# define TBCI_MALLOC_LOCK 1
# include "tbci/smp.h"
#endif

#if defined(__GNUC__) && defined(SMP) && defined(TBCI_MALLOC_NOLOCK)
# warning "SMP support but no locking in memalloc_cache. Don't do memory\
 de/allocations from threads; otherwise you face corruption!"
#endif

//#pragma interface "malloc_cache.h"

#ifdef DEBUG_MALLOC     /* Ugly, but portable */
# define DEBUG_PRINTF1(arg1) CSTD__ fprintf(stderr, arg1)
# define DEBUG_PRINTF2(a1,a2) CSTD__ fprintf(stderr, a1, a2)
# define DEBUG_PRINTF3(a1,a2,a3) CSTD__ fprintf(stderr, a1, a2, a3)
# define DEBUG_PRINTF4(a1,a2,a3,a4) CSTD__ fprintf(stderr, a1, a2, a3, a4)
#else
# define DEBUG_PRINTF1(arg1) do {} while (0)
# define DEBUG_PRINTF2(a1,a2) do {} while (0)
# define DEBUG_PRINTF3(a1,a2,a3) do {} while (0)
# define DEBUG_PRINTF4(a1,a2,a3,a4) do {} while (0)
#endif

NAMESPACE_TBCI
#ifndef TBCI_MALLOC_POOLSZ
# define TBCI_MALLOC_POOLSZ 8
#endif
#ifndef TBCI_MALLOC_LIMIT
# define TBCI_MALLOC_LIMIT 8192
#endif

#if !defined(__GNUC__) && !defined(__BORLANDC__)        /*  __EDG__ */
# define DUMMY1 const T* const dummy
# define DUMMY2(TYPE) const TYPE * const dummy
# define DUMMY3(t)  (t*)0
# define FGD2  
#else   // GCC || Borland
# define DUMMY1  
# define DUMMY2(TYPE)  
# define DUMMY3(t)  
# define FGD2  FGDT
#endif
#ifndef MINLINE
# define MINLINE inline
#endif

// Some compilers don't understand the typical singleton construction :(
#if defined(__INTEL_COMPILER) || defined(_MSC_VER) || defined(__BORLANDC__) || (defined(_SGI_SOURCE) && defined(_COMPILER_VERSION) && !defined(__GNUC__))
# define NO_SINGLETON
# define NO_SINGLETON_PUBLIC public:
//#warning Intel C++ 6 does not understand the typical singleton construction. Sigh.
#else
# define NO_SINGLETON_PUBLIC 
#endif

template <typename T> class tbci_memalloc;
template <typename T> inline tbci_memalloc<T>& tbci_s_allocator (DUMMY1);
//template <> tbci_memalloc_base<double>& tbci_s_allocator<double> ();

template <typename T>
class tbci_memalloc {
   protected:
        // singleton construction ...
   NO_SINGLETON_PUBLIC
        tbci_memalloc() {}
        ~tbci_memalloc() {}
   public:
        friend tbci_memalloc<T>& tbci_s_allocator FGD2 (DUMMY1);
        static T* alloc(const unsigned long sz) 
        { return new T[sz]; }
        static void dealloc(const T* const ptr, const unsigned long sz) 
        { delete [] (T*)ptr; }
};


#ifndef TBCI_SIMD_ALIGN
# ifdef AVX512
#  define TBCI_SIMD_ALIGN 64
# elif defined(__AVX__)
#  define TBCI_SIMD_ALIGN 32
# else
#  define TBCI_SIMD_ALIGN 16
# endif
#endif
#ifndef TBCI_MALLOC_ALIGN_FACT
# define TBCI_MALLOC_ALIGN_FACT 1
#endif

#if !defined(__SSE2__) || defined(__x86_64__) || !defined(HAVE_MALLOC_H)
# define _MC_NEW(T,SZ) new T[SZ]
# define _MC_DELETE(T,PTR) delete[] (T*)PTR
# ifndef __x86_64__
#  define SSE_VARS_MAY_BE_UNALIGNED
# endif
#else
# define _MC_NEW(T,SZ) (T*)memalign(TBCI_SIMD_ALIGN*TBCI_MALLOC_ALIGN_FACT, SZ*sizeof(T))
# define _MC_DELETE(T,PTR) free((T*)PTR)
#endif

#if defined(__x86_64__) || defined(__i386__)
# define INC(x) asm volatile ("lock incl %0" : "=m" (x): "m" (x));
#else   
# define INC(x) ++x;
#endif

#if defined(HAVE_TLS) && !defined(TBCI_MALLOC_FORCESPINLOCK)
# define TBCI_MALLOC_NOSPINLOCK
#endif

#if !defined(TBCI_MALLOC_NOSPINLOCK) && defined(HAVE_PTHREAD_SPINLOCK) && defined(TBCI_MALLOC_LOCK)

#define TBCI_MALLOC_SPINLOCK
#include <errno.h>

#if defined(__i386__) || defined(__x86_64__)
# define _cpu_relax() asm ("rep; nop")
#else
# define _cpu_relax()
#endif

#ifndef TBCI_MAXLOCKTRIES
# define TBCI_MAXLOCKTRIES 4
#endif

#ifdef TBCI_MALLOC_STATS
static volatile unsigned long locks_taken = 0;
static volatile unsigned long locks_tried = 0;
static volatile unsigned long locks_direct = 0;
static volatile unsigned long locks_yield = 0;
#endif

/* TODO: Can we find a more efficient way to do spinlocks than
 * pthread_spin_lock() ? These seem to be rather heavyweight
 * and seem to involve the kernel (even in the fast path).
 * Can we do something with futexes?
 */

static inline void _spin_lock(pthread_spinlock_t* lock)
{
        unsigned int tries = 0;
        int err;
        while (0 != (err = pthread_spin_trylock(lock))) {
#ifdef PARANOIA
                if (UNLIKELY(err != EBUSY)) {
                        fprintf(stderr, "LOCKING ERROR: %s\n", strerror(err));
                        abort();
                }
#endif
                if (0 == ++tries % TBCI_MAXLOCKTRIES) {
#ifdef TBCI_MALLOC_STATS
                        INC(locks_yield);
#endif
                        sched_yield();
                }
                _cpu_relax();
        }
#ifdef TBCI_MALLOC_STATS
        INC(locks_taken);
        locks_tried += tries;
        if (!tries)
                INC(locks_direct);
#endif
}

static inline void _spin_unlock(pthread_spinlock_t* lock)
{
        pthread_spin_unlock(lock);
}

# define SMP_LOCK _spin_lock(&this->lock)
# define SMP_UNLOCK _spin_unlock(&this->lock)

#else   /* TBCI_MALLOC_SPINLOCK */
# define SMP_LOCK
# define SMP_UNLOCK
#endif

#if __WORDSIZE == 64
template <typename T>
struct tbci_memalloc_cache_tls
{
        const T *free_pt[TBCI_MALLOC_POOLSZ];           /* pointers to slots */
        unsigned int free_sz[TBCI_MALLOC_POOLSZ];       /* sizes of free slots (0 => in use) */
        unsigned int free_idx;                                          /* next free (RR): guess */
        //unsigned int pad[3];                                          /* padding */
        volatile unsigned int hit, srch, all, miss;
} ALIGN(64);
#else
template <typename T>
struct tbci_memalloc_cache_tls
{
        const T *free_pt[TBCI_MALLOC_POOLSZ];           /* pointers to slots */
        unsigned short free_sz[TBCI_MALLOC_POOLSZ];     /* sizes of free slots (0 => in use) */
        unsigned char free_idx;                 /* next free (RR): guess */
        volatile unsigned int miss:24;
        volatile unsigned int hit, srch, all;
} ALIGN(64);
#endif

template <typename T>
struct tbci_memalloc_cache
{
        tbci_memalloc_cache_tls<T>      *malloc_tls;
#ifdef TBCI_MALLOC_SPINLOCK
        pthread_spinlock_t lock;
#endif
#ifdef SMP
        int nthr;
#endif

        int  find_by_sz(const unsigned ln) const;
        void enter(const T* const ptr, const unsigned ln);
        void free_and_enter(const T* const ptr, const unsigned ln);
        void rmv(const unsigned idx);
        const T *  find_and_rmv(const unsigned sz);
        T *  alloc(const unsigned long) MALLOC;
        void dealloc(const T* const, const unsigned long);
#ifdef SMP
        static void _init(tbci_memalloc_cache<T>* th, const int thr) 
        {   
                if (th->nthr >= thr)
                        return;
                tbci_memalloc_cache_tls<T> *new_malloc_tls;
                new_malloc_tls = (tbci_memalloc_cache_tls<T>*) 
                                memalign(128, sizeof(tbci_memalloc_cache_tls<T>) *(thr+1));
                memcpy(new_malloc_tls, th->malloc_tls, 
                                sizeof(tbci_memalloc_cache_tls<T>) *(th->nthr+1));
                SWAP(new_malloc_tls, th->malloc_tls);
                th->nthr = thr;
                free(new_malloc_tls);
                th->smp_init(); 
        }
        static void _deinit(tbci_memalloc_cache<T>* th, const int thr) 
        { th->smp_deinit(); }
#endif
        void deinit(const int thr);
        void init(const int thr)
        {
#ifdef SMP
                BCHK(thr > nthr, NumErr, thread malloc not allocated, thr, );
#endif
                tbci_memalloc_cache_tls<T> * const pool = malloc_tls+thr;
                CSTD__ memset(pool, 0, sizeof(struct tbci_memalloc_cache_tls<T>));
                pool->free_idx = TBCI_MALLOC_POOLSZ-1;
#ifdef TBCI_MALLOC_SPINLOCK
                pthread_spin_init(&lock, 0);
#endif
                //fprintf(stderr, "Init pool %i @ %p\n", thr, pool);
        }
#ifdef SMP
        void smp_init() 
        {
                //CSTD__ fprintf(stderr, "malloc_cache<%s>: smp_init(%i)\n",
                //      typeid(T).name(), nthr);
                for (int t = 1; t <= nthr; ++t) 
                        init(t);
        }
#endif
        void smp_deinit()
        {
#ifdef TBCI_MALLOC_STATS
                unsigned int hit, srch, all, miss;
                hit = srch = all = miss = 0;
#endif
#ifdef SMP
                if (nthr) {
                        //CSTD__ fprintf(stderr, "malloc_cache<%s>: smp_deinit(%i)\n",
                        //      typeid(T).name(), nthr);
                        for (int t = nthr; t > 0; --t) {
#ifdef TBCI_MALLOC_STATS
                                hit += malloc_tls[t].hit; srch += malloc_tls[t].srch;
                                all += malloc_tls[t].all; miss += malloc_tls[t].miss;
#endif
                                deinit(t);
                        }
                        nthr = 0; thrno = 0;
                }
#endif
#ifdef TBCI_MALLOC_STATS
                hit += malloc_tls[0].hit; srch += malloc_tls[0].srch;
                all += malloc_tls[0].all; miss += malloc_tls[0].miss;
                CSTD__ fprintf(stderr, "malloc_cache<%s>: %i hits, %i misses, %i searches, %i allocs\n", 
                                typeid(T).name(), hit, miss, srch, all);
#ifdef TBCI_MALLOC_SPINLOCK
                CSTD__ fprintf(stderr, "malloc_cache<%s>: %lu locks, %lu tries, %lu direct, %lu yields\n",
                                typeid(T).name(), locks_taken, locks_tried, locks_direct, locks_yield);
#endif
#endif
        }
        tbci_memalloc_cache()
#ifdef SMP
        : nthr(num_threads)
#endif
        {
                //malloc_tls = new tbci_memalloc_cache_tls<T>[num_threads+1];
                malloc_tls = (tbci_memalloc_cache_tls<T>*) 
                        memalign(128, sizeof(tbci_memalloc_cache_tls<T>) *(num_threads+1));
                init(0);
#ifdef SMP
                if (nthr) {
                        smp_init();
                        //fprintf(stderr, "Directly init per-thread vars %p: %zi\n", 
                        //              malloc_tls, sizeof(*malloc_tls));
                } 
                thread_reg_callback((cbackfn*) &_init,
                                    (cbackfn*) &_deinit, (void*)this);
#endif
        }
        ~tbci_memalloc_cache()
        {
#ifdef SMP
                thread_dereg_callback((cbackfn*) &_init,
                                        (cbackfn*) &_deinit, (void*)this);
#endif
                smp_deinit();
                deinit(0);
                //delete[] malloc_tls;
                free(malloc_tls);
        }
};

template <typename T>
inline int tbci_memalloc_cache<T>::find_by_sz(const unsigned sz) const
{
        DEBUG_PRINTF2("Search for free chunk of sz %i: ", sz);
        tbci_memalloc_cache_tls<T> * const pool = malloc_tls+thrno;
#ifdef SMP
        BCHK(thrno > nthr, NumErr, thread malloc_cache too small, thrno, -1);
#endif
        for (unsigned int _i = 1; _i <= TBCI_MALLOC_POOLSZ; ++_i) {
                const unsigned fidx = pool->free_idx;
                const unsigned int i = (fidx + _i) % TBCI_MALLOC_POOLSZ;
                DEBUG_PRINTF2("%i ", i);
                if (sz == pool->free_sz[i]) {
                        DEBUG_PRINTF1("(found)\n");
#ifdef TBCI_MALLOC_STATS
                        ++pool->hit;
#endif
                        return i;
                }
#ifdef TBCI_MALLOC_STATS
                ++pool->srch;
#endif
        }
        DEBUG_PRINTF1("not found!\n");
#ifdef TBCI_MALLOC_STATS
        ++pool->miss;
#endif
        return -1;
}

template <typename T>
inline void tbci_memalloc_cache<T>::enter(const T* const ptr, const unsigned ln)
{
        tbci_memalloc_cache_tls<T> * const pool = malloc_tls+thrno;
        const unsigned fidx = pool->free_idx;
        pool->free_pt[fidx] = ptr;
        pool->free_sz[fidx] = ln;
        pool->free_idx = (TBCI_MALLOC_POOLSZ + fidx - 1) % TBCI_MALLOC_POOLSZ;
}

template <typename T>
inline void tbci_memalloc_cache<T>::rmv(const unsigned idx)
{
        tbci_memalloc_cache_tls<T> * const pool = malloc_tls+thrno;
        pool->free_sz[idx] = 0;
        pool->free_idx = idx;
}

template <typename T>
inline const T* tbci_memalloc_cache<T>::find_and_rmv(const unsigned sz)
{
        SMP_LOCK;
        const T* ptr = 0;
        const int idx = find_by_sz(sz);
        if (LIKELY(idx >= 0)) {
                rmv(idx);
                ptr = malloc_tls[thrno].free_pt[idx];
        }
        SMP_UNLOCK;
        return ptr;
}


template <typename T>
inline T* tbci_memalloc_cache<T>::alloc(const unsigned long sz)
{       
        BCHK(!sz, NumErr, alloc 0 bytes, sz, (T*)0);
#ifdef TBCI_MALLOC_STATS
        ++malloc_tls[thrno].all;
#endif
#if defined(TBCI_MALLOC_LOCK) && !defined(TBCI_MALLOC_SPINLOCK)

        if (0 && !ismainthread)
                return _MC_NEW(T, sz);
#endif
        if (UNLIKELY (sz > TBCI_MALLOC_LIMIT/sizeof(T)))
                return _MC_NEW(T, sz);

        const T* ptr = find_and_rmv(sz);
        if (!ptr) 
                ptr = _MC_NEW(T, sz);

        DEBUG_PRINTF3("Allocated %p (%li)\n", ptr, sz);
        return (T*) ptr;
}

template <typename T>
inline void tbci_memalloc_cache<T>::free_and_enter(const T* const ptr, const unsigned sz)
{
        const T* tofree = 0;
        SMP_LOCK;
        /* replace free slot? */
        tbci_memalloc_cache_tls<T> * const pool = malloc_tls+thrno;
        const unsigned fidx = pool->free_idx;
        if (UNLIKELY(pool->free_sz[fidx] != 0)) 
                tofree = pool->free_pt[fidx];
        DEBUG_PRINTF4("\"Freed\" %p (%li) -> %i\n", ptr, sz, fidx);
        enter(ptr, sz);
        SMP_UNLOCK;
        if (LIKELY(!tofree))
                return;
        _MC_DELETE(T, tofree);
}
        
template <typename T>
inline void tbci_memalloc_cache<T>::dealloc(const T* const ptr, const unsigned long sz)
{
        BCHK (!ptr||!sz, NumErr, dealloc null ptr or 0 bytes, (long)ptr, );
        
#ifdef MALLOC_POISON
        CSTD__ memset((void*)ptr, 0xa5, sz*sizeof(T));
#endif
#if defined(TBCI_MALLOC_LOCK) && !defined(TBCI_MALLOC_SPINLOCK)
        if (0 && !ismainthread) {
                _MC_DELETE(T, ptr); return;
        }
#endif

        if (UNLIKELY (sz > TBCI_MALLOC_LIMIT/sizeof(T)))
                _MC_DELETE(T, ptr); 
        else 
                free_and_enter(ptr, sz);
}

template <typename T>
inline void tbci_memalloc_cache<T>::deinit(const int thr)
{
        DEBUG_PRINTF1("Freeing memory pool ...\n");
        //int * ptr = 0; *ptr = 0;
        tbci_memalloc_cache_tls<T> * const pool = malloc_tls+thr;

        for (int _i = 0; _i < TBCI_MALLOC_POOLSZ; ++_i) {
                if (pool->free_sz[_i]) {
                        DEBUG_PRINTF3("Freeing mem %p (size %i)\n",
                                      pool->free_pt[_i], pool->free_sz[_i]);
                        pool->free_sz[_i] = 0;
                        _MC_DELETE(T, pool->free_pt[_i]);
                }
        }
#ifdef TBCI_MALLOC_SPINLOCK
        pthread_spin_destroy(&lock);
#endif
}

#define SPECIALIZE_MEMALLOC_CLASS(TYPE) \
template <>                                                             \
class tbci_memalloc<TYPE > {                    \
        typedef TYPE T;                                         \
    protected:                                                  \
        tbci_memalloc_cache<T > m_cache;        \
    NO_SINGLETON_PUBLIC                                 \
        tbci_memalloc() {}                                      \
        ~tbci_memalloc() {}                                     \
    public:                                                             \
        friend tbci_memalloc<T >& tbci_s_allocator FGD2 (DUMMY1);               \
        T* alloc(const unsigned long sz) { return m_cache.alloc(sz); }  \
        void dealloc(const T* const ptr, const unsigned long sz)                \
        { m_cache.dealloc(ptr,sz); }            \
};

/* Default allocator, just a wrapper to new[] and delete[] */
template <typename T> \
MINLINE tbci_memalloc<T>& tbci_s_allocator (DUMMY1)
{
        static tbci_memalloc<T> _tbci_s_alloc_ANON; /* the one and only */
        return _tbci_s_alloc_ANON;
}

#if defined(__MINGW32__)
#define SPECIALIZE_MEMALLOC(TYPE) /* nothing */
#define SPECIALIZE_MEMALLOC2(TYPE,SHTP) /* even less */
#else
/* Specializations */
#define SPECIALIZE_MEMALLOC(TYPE)               \
SPECIALIZE_MEMALLOC_CLASS(TYPE)                 \
template <>                                     \
MINLINE tbci_memalloc<TYPE >& tbci_s_allocator<TYPE > (DUMMY2(TYPE)) \
{       /* the one and only */                  \
        static tbci_memalloc<TYPE > _tbci_s_alloc_##TYPE;       \
        return _tbci_s_alloc_##TYPE;            \
}
/* Specializations */
#define SPECIALIZE_MEMALLOC2(TYPE,SHTP) \
SPECIALIZE_MEMALLOC_CLASS(TYPE)                 \
template <>                                     \
MINLINE tbci_memalloc<TYPE >& tbci_s_allocator<TYPE > (DUMMY2(TYPE)) \
{       /* the one and only */                  \
        static tbci_memalloc<TYPE > _tbci_s_alloc_##SHTP;       \
        return _tbci_s_alloc_##SHTP;            \
}
#endif  /* ! __MINGW32__ */

/* TODO: Add define, controlling instantiation */

#if 0   // defined(TBCI_SELECTIVE_INST) && !defined(TBCI_INSTANTIATE) && !defined(AUTO_DECL)
# include "malloc_cache_gd.h"
#else

SPECIALIZE_MEMALLOC(double)
typedef double* doubleptr;
SPECIALIZE_MEMALLOC(doubleptr)
SPECIALIZE_MEMALLOC(float)
typedef float* floatptr;
SPECIALIZE_MEMALLOC(floatptr)
SPECIALIZE_MEMALLOC(unsigned)
typedef unsigned int* uintptr;
SPECIALIZE_MEMALLOC(uintptr)
SPECIALIZE_MEMALLOC(int)
typedef int* intptr;
SPECIALIZE_MEMALLOC(intptr)
SPECIALIZE_MEMALLOC2(unsigned char, uchar)
SPECIALIZE_MEMALLOC2(signed char, schar)
typedef char* charptr;
SPECIALIZE_MEMALLOC(charptr)
typedef unsigned char* ucharptr;
SPECIALIZE_MEMALLOC(ucharptr)
SPECIALIZE_MEMALLOC(long)
typedef long* longptr;
SPECIALIZE_MEMALLOC(longptr)
SPECIALIZE_MEMALLOC2(unsigned long, ulong)
typedef unsigned long* ulongptr;
SPECIALIZE_MEMALLOC(ulongptr)
SPECIALIZE_MEMALLOC2(unsigned short, ushort)
typedef void* voidptr;
SPECIALIZE_MEMALLOC(voidptr)

#endif  // TBCI_SELECTIVE_INST

#define NEW(t, s) tbci_s_allocator<t>(DUMMY3(t)).alloc(s)
#define TBCIDELETE(t, v, sz) tbci_s_allocator<t>(DUMMY3(t)).dealloc(v, sz)
#define TBCIDELETE_RO(t, v, sz) tbci_s_allocator<t>(DUMMY3(t)).dealloc(v, sz)
#define REALLOC(v, os, t, s)  do {              \
        t *ptr = NEW(t, s);                             \
        if (LIKELY(v)) {                                        \
                TBCICOPY(ptr, v, t, MIN(os, s));\
                TBCIDELETE(t, v, os);                   \
        }                                                                       \
        v = ptr;                                                        \
} while (0)

NAMESPACE_END
#endif  /* TBCI_MALLOC_CACHE_H */