/*

 * $Id: ptmalloc3.c,v 1.8 2006/03/31 15:57:28 wg Exp $

 * 

ptmalloc3 -- wrapper for Doug Lea's malloc-2.8.3 with concurrent

             allocations

Copyright (c) 2005, 2006 Wolfram Gloger  <ptmalloc@malloc.de>

Permission to use, copy, modify, distribute, and sell this software

and its documentation for any purpose is hereby granted without fee,

provided that (i) the above copyright notices and this permission

notice appear in all copies of the software and related documentation,

and (ii) the name of Wolfram Gloger may not be used in any advertising

or publicity relating to the software.

THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,

EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY

WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

IN NO EVENT SHALL WOLFRAM GLOGER BE LIABLE FOR ANY SPECIAL,

INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY

DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,

WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY

OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR

PERFORMANCE OF THIS SOFTWARE.

 */

/*

 * TODO: optimization / better integration with malloc.c (partly done)

 *       malloc_{get,set}_state (probably hard to keep compatibility)

 *       debugging hooks

 *       better mstats

 */

#include <sys/types.h>   /* For size_t */

#include <sys/mman.h>    /* for mmap */

#include <errno.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>      /* for memset */

#include <malloc-machine.h>

#include "malloc-2.8.3.h"

/* ----------------------------------------------------------------------- */

/* The following section is replicated from malloc.c */

#include "malloc-private.h"

/* end of definitions replicated from malloc.c */

#define munmap_chunk(mst, p) do {                         \

  size_t prevsize = (p)->prev_foot & ~IS_MMAPPED_BIT;     \

  size_t psize = chunksize(p) + prevsize + MMAP_FOOT_PAD; \

  if (CALL_MUNMAP((char*)(p) - prevsize, psize) == 0)     \

    ((struct malloc_state*)(mst))->footprint -= psize;    \

} while (0)

/* ---------------------------------------------------------------------- */

/* Minimum size for a newly created arena.  */

#ifndef ARENA_SIZE_MIN

# define ARENA_SIZE_MIN	   (128*1024)

#endif

#define HAVE_MEMCPY        1

/* If THREAD_STATS is non-zero, some statistics on mutex locking are

   computed.  */

#ifndef THREAD_STATS

# define THREAD_STATS 0

#endif

#ifndef MALLOC_DEBUG

# define MALLOC_DEBUG 0

#endif

#define my_powerof2(x) ((((x)-1)&(x))==0)

/* Already initialized? */

int __malloc_initialized = -1;

#ifndef RETURN_ADDRESS

# define RETURN_ADDRESS(X_) (NULL)

#endif

#if THREAD_STATS

# define THREAD_STAT(x) x

#else

# define THREAD_STAT(x) do ; while(0)

#endif

#ifdef _LIBC

/* Special defines for the GNU C library.  */

#define public_cALLOc    __libc_calloc

#define public_fREe      __libc_free

#define public_cFREe     __libc_cfree

#define public_mALLOc    __libc_malloc

#define public_mEMALIGn  __libc_memalign

#define public_rEALLOc   __libc_realloc

#define public_vALLOc    __libc_valloc

#define public_pVALLOc   __libc_pvalloc

#define public_pMEMALIGn __posix_memalign

#define public_mALLINFo  __libc_mallinfo

#define public_mALLOPt   __libc_mallopt

#define public_mTRIm     __malloc_trim

#define public_mSTATs    __malloc_stats

#define public_mUSABLe   __malloc_usable_size

#define public_iCALLOc   __libc_independent_calloc

#define public_iCOMALLOc __libc_independent_comalloc

#define public_gET_STATe __malloc_get_state

#define public_sET_STATe __malloc_set_state

#define malloc_getpagesize __getpagesize()

#define open             __open

#define mmap             __mmap

#define munmap           __munmap

#define mremap           __mremap

#define mprotect         __mprotect

#define MORECORE         (*__morecore)

#define MORECORE_FAILURE 0

void * __default_morecore (ptrdiff_t);

void *(*__morecore)(ptrdiff_t) = __default_morecore;

#else /* !_LIBC */

#define public_cALLOc    calloc

#define public_fREe      free

#define public_cFREe     cfree

#define public_mALLOc    malloc

#define public_mEMALIGn  memalign

#define public_rEALLOc   realloc

#define public_vALLOc    valloc

#define public_pVALLOc   pvalloc

#define public_pMEMALIGn posix_memalign

#define public_mALLINFo  mallinfo

#define public_mALLOPt   mallopt

#define public_mTRIm     malloc_trim

#define public_mSTATs    malloc_stats

#define public_mUSABLe   malloc_usable_size

#define public_iCALLOc   independent_calloc

#define public_iCOMALLOc independent_comalloc

#define public_gET_STATe malloc_get_state

#define public_sET_STATe malloc_set_state

#endif /* _LIBC */

#if !defined _LIBC && (!defined __GNUC__ || __GNUC__<3)

#define __builtin_expect(expr, val) (expr)

#endif

#if MALLOC_DEBUG

#include <assert.h>

#else

#undef assert

#define assert(x) ((void)0)

#endif

/* USE_STARTER determines if and when the special "starter" hook

   functions are used: not at all (0), during ptmalloc_init (first bit

   set), or from the beginning until an explicit call to ptmalloc_init

   (second bit set).  This is necessary if thread-related

   initialization functions (e.g.  pthread_key_create) require

   malloc() calls (set USE_STARTER=1), or if those functions initially

   cannot be used at all (set USE_STARTER=2 and perform an explicit

   ptmalloc_init() when the thread library is ready, typically at the

   start of main()). */

#ifndef USE_STARTER

# ifndef _LIBC

#  define USE_STARTER 1

# else

#  if USE___THREAD || (defined USE_TLS && !defined SHARED)

    /* These routines are never needed in this configuration.  */

#   define USE_STARTER 0

#  else

#   define USE_STARTER (USE_TLS ? 4 : 1)

#  endif

# endif

#endif

/*----------------------------------------------------------------------*/

/* Arenas */

static tsd_key_t arena_key;

static mutex_t list_lock;

/* Arena structure */

struct malloc_arena {

  /* Serialize access.  */

  mutex_t mutex;

  /* Statistics for locking.  Only used if THREAD_STATS is defined.  */

  long stat_lock_direct, stat_lock_loop, stat_lock_wait;

  long stat_starter;

  /* Linked list */

  struct malloc_arena *next;

  /* Space for mstate.  The size is just the minimum such that

     create_mspace_with_base can be successfully called.  */

  char buf_[pad_request(sizeof(struct malloc_state)) + TOP_FOOT_SIZE +

	    CHUNK_ALIGN_MASK + 1];

};

#define MSPACE_OFFSET (((offsetof(struct malloc_arena, buf_) \

			 + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK))

#define arena_to_mspace(a) ((void *)chunk2mem((char*)(a) + MSPACE_OFFSET))

/* check for chunk from non-main arena */

#define chunk_non_main_arena(p) ((p)->head & NON_MAIN_ARENA)

static struct malloc_arena* _int_new_arena(size_t size);

/* Buffer for the main arena. */

static struct malloc_arena main_arena;

/* For now, store arena in footer.  This means typically 4bytes more

   overhead for each non-main-arena chunk, but is fast and easy to

   compute.  Note that the pointer stored in the extra footer must be

   properly aligned, though. */

#define FOOTER_OVERHEAD \

 (2*sizeof(struct malloc_arena*) - SIZE_T_SIZE)

#define arena_for_chunk(ptr) \

 (chunk_non_main_arena(ptr) ? *(struct malloc_arena**)              \

  ((char*)(ptr) + chunksize(ptr) - (FOOTER_OVERHEAD - SIZE_T_SIZE)) \

  : &main_arena)

/* special because of extra overhead */

#define arena_for_mmap_chunk(ptr) \

 (chunk_non_main_arena(ptr) ? *(struct malloc_arena**)             \

  ((char*)(ptr) + chunksize(ptr) - sizeof(struct malloc_arena*))   \

  : &main_arena)

#define set_non_main_arena(mem, ar_ptr) do {                   		      \

  mchunkptr P = mem2chunk(mem);                                               \

  size_t SZ = chunksize(P) - (is_mmapped(P) ? sizeof(struct malloc_arena*)    \

                              : (FOOTER_OVERHEAD - SIZE_T_SIZE));             \

  assert((unsigned long)((char*)(P) + SZ)%sizeof(struct malloc_arena*) == 0); \

  *(struct malloc_arena**)((char*)(P) + SZ) = (ar_ptr);                       \

  P->head |= NON_MAIN_ARENA;                                                  \

} while (0)

/* arena_get() acquires an arena and locks the corresponding mutex.

   First, try the one last locked successfully by this thread.  (This

   is the common case and handled with a macro for speed.)  Then, loop

   once over the circularly linked list of arenas.  If no arena is

   readily available, create a new one.  In this latter case, `size'

   is just a hint as to how much memory will be required immediately

   in the new arena. */

#define arena_get(ptr, size) do { \

  void *vptr = NULL; \

  ptr = (struct malloc_arena*)tsd_getspecific(arena_key, vptr); \

  if(ptr && !mutex_trylock(&ptr->mutex)) { \

    THREAD_STAT(++(ptr->stat_lock_direct)); \

  } else \

    ptr = arena_get2(ptr, (size)); \

} while(0)

static struct malloc_arena*

arena_get2(struct malloc_arena* a_tsd, size_t size)

{

  struct malloc_arena* a;

  int err;

  if(!a_tsd)

    a = a_tsd = &main_arena;

  else {

    a = a_tsd->next;

    if(!a) {

      /* This can only happen while initializing the new arena. */

      (void)mutex_lock(&main_arena.mutex);

      THREAD_STAT(++(main_arena.stat_lock_wait));

      return &main_arena;

    }

  }

  /* Check the global, circularly linked list for available arenas. */

 repeat:

  do {

    if(!mutex_trylock(&a->mutex)) {

      THREAD_STAT(++(a->stat_lock_loop));

      tsd_setspecific(arena_key, (void *)a);

      return a;

    }

    a = a->next;

  } while(a != a_tsd);

  /* If not even the list_lock can be obtained, try again.  This can

     happen during `atfork', or for example on systems where thread

     creation makes it temporarily impossible to obtain _any_

     locks. */

  if(mutex_trylock(&list_lock)) {

    a = a_tsd;

    goto repeat;

  }

  (void)mutex_unlock(&list_lock);

  /* Nothing immediately available, so generate a new arena.  */

  a = _int_new_arena(size);

  if(!a)

    return 0;

  tsd_setspecific(arena_key, (void *)a);

  mutex_init(&a->mutex);

  err = mutex_lock(&a->mutex); /* remember result */

  /* Add the new arena to the global list.  */

  (void)mutex_lock(&list_lock);

  a->next = main_arena.next;

  atomic_write_barrier ();

  main_arena.next = a;

  (void)mutex_unlock(&list_lock);

  if(err) /* locking failed; keep arena for further attempts later */

    return 0;

  THREAD_STAT(++(a->stat_lock_loop));

  return a;

}

/* Create a new arena with room for a chunk of size "size".  */

static struct malloc_arena*

_int_new_arena(size_t size)

{

  struct malloc_arena* a;

  size_t mmap_sz = sizeof(*a) + pad_request(size);

  void *m;

  if (mmap_sz < ARENA_SIZE_MIN)

    mmap_sz = ARENA_SIZE_MIN;

  /* conservative estimate for page size */

  mmap_sz = (mmap_sz + 8191) & ~(size_t)8191;

  a = CALL_MMAP(mmap_sz);

  if ((char*)a == (char*)-1)

    return 0;

  m = create_mspace_with_base((char*)a + MSPACE_OFFSET,

			      mmap_sz - MSPACE_OFFSET,

			      0);

  if (!m) { 

    CALL_MUNMAP(a, mmap_sz);

    a = 0;

  } else {

    /*a->next = NULL;*/

    /*a->system_mem = a->max_system_mem = h->size;*/

  }

  return a;

}

/*------------------------------------------------------------------------*/

/* Hook mechanism for proper initialization and atfork support. */

/* Define and initialize the hook variables.  These weak definitions must

   appear before any use of the variables in a function.  */

#ifndef weak_variable

#ifndef _LIBC

#define weak_variable /**/

#else

/* In GNU libc we want the hook variables to be weak definitions to

   avoid a problem with Emacs.  */

#define weak_variable weak_function

#endif

#endif

#if !(USE_STARTER & 2)

# define free_hook_ini     NULL

/* Forward declarations.  */

static void* malloc_hook_ini (size_t sz, const void *caller);

static void* realloc_hook_ini (void* ptr, size_t sz, const void* caller);

static void* memalign_hook_ini (size_t alignment, size_t sz,

				const void* caller);

#else

# define free_hook_ini     free_starter

# define malloc_hook_ini   malloc_starter

# define realloc_hook_ini  NULL

# define memalign_hook_ini memalign_starter

#endif

void weak_variable (*__malloc_initialize_hook) (void) = NULL;

void weak_variable (*__free_hook) (void * __ptr, const void *)

     = free_hook_ini;

void * weak_variable (*__malloc_hook) (size_t __size, const void *)

     = malloc_hook_ini;

void * weak_variable (*__realloc_hook)

     (void * __ptr, size_t __size, const void *) = realloc_hook_ini;

void * weak_variable (*__memalign_hook)

  (size_t __alignment, size_t __size, const void *) = memalign_hook_ini;

/*void weak_variable (*__after_morecore_hook) (void) = NULL;*/

/* The initial hooks just call the initialization routine, then do the

   normal work. */

#if !(USE_STARTER & 2)

static

#endif

void ptmalloc_init(void);

#if !(USE_STARTER & 2)

static void*

malloc_hook_ini(size_t sz, const void * caller)

{

  __malloc_hook = NULL;

  ptmalloc_init();

  return public_mALLOc(sz);

}

static void *

realloc_hook_ini(void *ptr, size_t sz, const void * caller)

{

  __malloc_hook = NULL;

  __realloc_hook = NULL;

  ptmalloc_init();

  return public_rEALLOc(ptr, sz);

}

static void*

memalign_hook_ini(size_t alignment, size_t sz, const void * caller)

{

  __memalign_hook = NULL;

  ptmalloc_init();

  return public_mEMALIGn(alignment, sz);

}

#endif /* !(USE_STARTER & 2) */

/*----------------------------------------------------------------------*/

#if !defined NO_THREADS && USE_STARTER

/* The following hooks are used when the global initialization in

   ptmalloc_init() hasn't completed yet. */

static void*

malloc_starter(size_t sz, const void *caller)

{

  void* victim;

  /*ptmalloc_init_minimal();*/

  victim = mspace_malloc(arena_to_mspace(&main_arena), sz);

  THREAD_STAT(++main_arena.stat_starter);

  return victim;

}

static void*

memalign_starter(size_t align, size_t sz, const void *caller)

{

  void* victim;

  /*ptmalloc_init_minimal();*/

  victim = mspace_memalign(arena_to_mspace(&main_arena), align, sz);

  THREAD_STAT(++main_arena.stat_starter);

  return victim;

}

static void

free_starter(void* mem, const void *caller)

{

  if (mem) {

    mchunkptr p = mem2chunk(mem);

    void *msp = arena_to_mspace(&main_arena);

    if (is_mmapped(p))

      munmap_chunk(msp, p);

    else

      mspace_free(msp, mem);

  }

  THREAD_STAT(++main_arena.stat_starter);

}

#endif /* !defined NO_THREADS && USE_STARTER */

/*----------------------------------------------------------------------*/

#ifndef NO_THREADS

/* atfork support.  */

static void * (*save_malloc_hook) (size_t __size, const void *);

# if !defined _LIBC || !defined USE_TLS || (defined SHARED && !USE___THREAD)

static void * (*save_memalign_hook) (size_t __align, size_t __size,

				     const void *);

# endif

static void   (*save_free_hook) (void * __ptr, const void *);

static void*  save_arena;

/* Magic value for the thread-specific arena pointer when

   malloc_atfork() is in use.  */

#define ATFORK_ARENA_PTR ((void*)-1)

/* The following hooks are used while the `atfork' handling mechanism

   is active. */

static void*

malloc_atfork(size_t sz, const void *caller)

{

  void *vptr = NULL;

  tsd_getspecific(arena_key, vptr);

  if(vptr == ATFORK_ARENA_PTR) {

    /* We are the only thread that may allocate at all.  */

    return mspace_malloc(arena_to_mspace(&main_arena), sz);

  } else {

    /* Suspend the thread until the `atfork' handlers have completed.

       By that time, the hooks will have been reset as well, so that

       mALLOc() can be used again. */

    (void)mutex_lock(&list_lock);

    (void)mutex_unlock(&list_lock);

    return public_mALLOc(sz);

  }

}

static void

free_atfork(void* mem, const void *caller)

{

  void *vptr = NULL;