/* GLIB sliced memory - fast concurrent memory chunk allocator

 * Copyright (C) 2005 Tim Janik

 * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.

 *

 * 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 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, write to the

 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

 * Boston, MA 02111-1307, USA.

 */

/* MT safe */

#include "config.h"

#if     defined HAVE_POSIX_MEMALIGN && defined POSIX_MEMALIGN_WITH_COMPLIANT_ALLOCS

#  define HAVE_COMPLIANT_POSIX_MEMALIGN 1

#endif

#ifdef HAVE_COMPLIANT_POSIX_MEMALIGN

#define _XOPEN_SOURCE 600       /* posix_memalign() */

#endif

#include <stdlib.h>             /* posix_memalign() */

#include <string.h>

#include <errno.h>

#include "gmem.h"               /* gslice.h */

#include "gthreadinit.h"

#include "galias.h"

#include "glib.h"

#ifdef HAVE_UNISTD_H

#include <unistd.h>             /* sysconf() */

#endif

#ifdef G_OS_WIN32

#include <windows.h>

#include <process.h>

#endif

#ifdef __SYMBIAN32__

#include <glib_wsd.h>

#endif /* __SYMBIAN32__ */

#if EMULATOR

#define g_thread_functions_for_glib_use (*_g_thread_functions_for_glib_use())

#define g_thread_use_default_impl (*_g_thread_use_default_impl())

#define g_mem_gc_friendly (*_g_mem_gc_friendly())

#endif /* EMULATOR */

/* the GSlice allocator is split up into 4 layers, roughly modelled after the slab

 * allocator and magazine extensions as outlined in:

 * + [Bonwick94] Jeff Bonwick, The slab allocator: An object-caching kernel

 *   memory allocator. USENIX 1994, http://citeseer.ist.psu.edu/bonwick94slab.html

 * + [Bonwick01] Bonwick and Jonathan Adams, Magazines and vmem: Extending the

 *   slab allocator to many cpu's and arbitrary resources.

 *   USENIX 2001, http://citeseer.ist.psu.edu/bonwick01magazines.html

 * the layers are:

 * - the thread magazines. for each (aligned) chunk size, a magazine (a list)

 *   of recently freed and soon to be allocated chunks is maintained per thread.

 *   this way, most alloc/free requests can be quickly satisfied from per-thread

 *   free lists which only require one g_private_get() call to retrive the

 *   thread handle.

 * - the magazine cache. allocating and freeing chunks to/from threads only

 *   occours at magazine sizes from a global depot of magazines. the depot

 *   maintaines a 15 second working set of allocated magazines, so full

 *   magazines are not allocated and released too often.

 *   the chunk size dependent magazine sizes automatically adapt (within limits,

 *   see [3]) to lock contention to properly scale performance across a variety

 *   of SMP systems.

 * - the slab allocator. this allocator allocates slabs (blocks of memory) close

 *   to the system page size or multiples thereof which have to be page aligned.

 *   the blocks are divided into smaller chunks which are used to satisfy

 *   allocations from the upper layers. the space provided by the reminder of

 *   the chunk size division is used for cache colorization (random distribution

 *   of chunk addresses) to improve processor cache utilization. multiple slabs

 *   with the same chunk size are kept in a partially sorted ring to allow O(1)

 *   freeing and allocation of chunks (as long as the allocation of an entirely

 *   new slab can be avoided).

 * - the page allocator. on most modern systems, posix_memalign(3) or

 *   memalign(3) should be available, so this is used to allocate blocks with

 *   system page size based alignments and sizes or multiples thereof.

 *   if no memalign variant is provided, valloc() is used instead and

 *   block sizes are limited to the system page size (no multiples thereof).

 *   as a fallback, on system without even valloc(), a malloc(3)-based page

 *   allocator with alloc-only behaviour is used.

 *

 * NOTES:

 * [1] some systems memalign(3) implementations may rely on boundary tagging for

 *     the handed out memory chunks. to avoid excessive page-wise fragmentation,

 *     we reserve 2 * sizeof (void*) per block size for the systems memalign(3),

 *     specified in NATIVE_MALLOC_PADDING.

 * [2] using the slab allocator alone already provides for a fast and efficient

 *     allocator, it doesn't properly scale beyond single-threaded uses though.

 *     also, the slab allocator implements eager free(3)-ing, i.e. does not

 *     provide any form of caching or working set maintenance. so if used alone,

 *     it's vulnerable to trashing for sequences of balanced (alloc, free) pairs

 *     at certain thresholds.

 * [3] magazine sizes are bound by an implementation specific minimum size and

 *     a chunk size specific maximum to limit magazine storage sizes to roughly

 *     16KB.

 * [4] allocating ca. 8 chunks per block/page keeps a good balance between

 *     external and internal fragmentation (<= 12.5%). [Bonwick94]

 */

/* --- macros and constants --- */

#define LARGEALIGNMENT          (256)

#define P2ALIGNMENT             (2 * sizeof (gsize))                            /* fits 2 pointers (assumed to be 2 * GLIB_SIZEOF_SIZE_T below) */

#define ALIGN(size, base)       ((base) * (gsize) (((size) + (base) - 1) / (base)))

#define NATIVE_MALLOC_PADDING   P2ALIGNMENT                                     /* per-page padding left for native malloc(3) see [1] */

#define SLAB_INFO_SIZE          P2ALIGN (sizeof (SlabInfo) + NATIVE_MALLOC_PADDING)

#define MAX_MAGAZINE_SIZE       (256)                                           /* see [3] and allocator_get_magazine_threshold() for this */

#define MIN_MAGAZINE_SIZE       (4)

#define MAX_STAMP_COUNTER       (7)                                             /* distributes the load of gettimeofday() */

#define MAX_SLAB_CHUNK_SIZE(al) (((al)->max_page_size - SLAB_INFO_SIZE) / 8)    /* we want at last 8 chunks per page, see [4] */

#define MAX_SLAB_INDEX(al)      (SLAB_INDEX (al, MAX_SLAB_CHUNK_SIZE (al)) + 1)

#define SLAB_INDEX(al, asize)   ((asize) / P2ALIGNMENT - 1)                     /* asize must be P2ALIGNMENT aligned */

#define SLAB_CHUNK_SIZE(al, ix) (((ix) + 1) * P2ALIGNMENT)

#define SLAB_BPAGE_SIZE(al,csz) (8 * (csz) + SLAB_INFO_SIZE)

/* optimized version of ALIGN (size, P2ALIGNMENT) */

#if     GLIB_SIZEOF_SIZE_T * 2 == 8  /* P2ALIGNMENT */

#define P2ALIGN(size)   (((size) + 0x7) & ~(gsize) 0x7)

#elif   GLIB_SIZEOF_SIZE_T * 2 == 16 /* P2ALIGNMENT */

#define P2ALIGN(size)   (((size) + 0xf) & ~(gsize) 0xf)

#else

#define P2ALIGN(size)   ALIGN (size, P2ALIGNMENT)

#endif

/* special helpers to avoid gmessage.c dependency */

static void mem_error (const char *format, ...) G_GNUC_PRINTF (1,2);

#define mem_assert(cond)    do { if (G_LIKELY (cond)) ; else mem_error ("assertion failed: %s", #cond); } while (0)

/* --- structures --- */

#if !(EMULATOR)

typedef struct _ChunkLink      ChunkLink;

typedef struct _SlabInfo       SlabInfo;

#endif /* !(EMULATOR) */

typedef struct _CachedMagazine CachedMagazine;

#if !(EMULATOR)

struct _ChunkLink {

  ChunkLink *next;

  ChunkLink *data;

};

struct _SlabInfo {

  ChunkLink *chunks;

  guint n_allocated;

  SlabInfo *next, *prev;

};

#endif /* !(EMULATOR) */

typedef struct {

  ChunkLink *chunks;

  gsize      count;                     /* approximative chunks list length */

} Magazine;

typedef struct {

  Magazine   *magazine1;                /* array of MAX_SLAB_INDEX (allocator) */

  Magazine   *magazine2;                /* array of MAX_SLAB_INDEX (allocator) */

} ThreadMemory;

#if !(EMULATOR)

typedef struct {

  gboolean always_malloc;

  gboolean bypass_magazines;

  gsize    working_set_msecs;

  guint    color_increment;

} SliceConfig;

typedef struct {

  /* const after initialization */

  gsize         min_page_size, max_page_size;

  SliceConfig   config;

  gsize         max_slab_chunk_size_for_magazine_cache;

  /* magazine cache */

  GMutex       *magazine_mutex;

  ChunkLink   **magazines;                /* array of MAX_SLAB_INDEX (allocator) */

  guint        *contention_counters;      /* array of MAX_SLAB_INDEX (allocator) */

  gint          mutex_counter;

  guint         stamp_counter;

  guint         last_stamp;

  /* slab allocator */

  GMutex       *slab_mutex;

  SlabInfo    **slab_stack;                /* array of MAX_SLAB_INDEX (allocator) */

  guint        color_accu;

} Allocator;

#endif /* !(EMULATOR)

/* --- prototypes --- */

static gpointer     slab_allocator_alloc_chunk       (gsize      chunk_size);

static void         slab_allocator_free_chunk        (gsize      chunk_size,

                                                      gpointer   mem);

static void         private_thread_memory_cleanup    (gpointer   data);

static gpointer     allocator_memalign               (gsize      alignment,

                                                      gsize      memsize);

static void         allocator_memfree                (gsize      memsize,

                                                      gpointer   mem);

static inline void  magazine_cache_update_stamp      (void);

#if EMULATOR

static inline gsize allocator_get_magazine_threshold (Allocator *allocator1,

                                                      guint      ix);

#else

static inline gsize allocator_get_magazine_threshold (Allocator *allocator,

                                                      guint      ix);

#endif /* EMULATOR */

/* --- variables --- */

#if EMULATOR

PLS(private_thread_memory,gslice,GPrivate *)

PLS(sys_page_size,gslice,gsize)

PLS_ARRAY(allocator,gslice,Allocator)

PLS(slice_config,gslice,SliceConfig)

#define private_thread_memory  (*FUNCTION_NAME(private_thread_memory ,gslice)())

#define sys_page_size  (*FUNCTION_NAME(sys_page_size ,gslice)())

#define allocator  (FUNCTION_NAME(allocator ,gslice)())

#define slice_config  (*FUNCTION_NAME(slice_config ,gslice)())

#else

static GPrivate   *private_thread_memory = NULL;

static gsize       sys_page_size = 0;

static Allocator   allocator[1] = { { 0, }, };

static SliceConfig slice_config = {

  FALSE,        /* always_malloc */

  FALSE,        /* bypass_magazines */

  15 * 1000,    /* working_set_msecs */

  1,            /* color increment, alt: 0x7fffffff */

};

#endif /* EMULATOR */

/* --- auxillary funcitons --- */

void

g_slice_set_config (GSliceConfig ckey,

                    gint64       value)

{

  g_return_if_fail (sys_page_size == 0);

  switch (ckey)

    {

    case G_SLICE_CONFIG_ALWAYS_MALLOC:

      slice_config.always_malloc = value != 0;

      break;

    case G_SLICE_CONFIG_BYPASS_MAGAZINES:

      slice_config.bypass_magazines = value != 0;

      break;

    case G_SLICE_CONFIG_WORKING_SET_MSECS:

      slice_config.working_set_msecs = value;

      break;

    case G_SLICE_CONFIG_COLOR_INCREMENT:

      slice_config.color_increment = value;

    default: ;

    }

}

gint64

g_slice_get_config (GSliceConfig ckey)

{

  switch (ckey)

    {

    case G_SLICE_CONFIG_ALWAYS_MALLOC:

      return slice_config.always_malloc;

    case G_SLICE_CONFIG_BYPASS_MAGAZINES:

      return slice_config.bypass_magazines;

    case G_SLICE_CONFIG_WORKING_SET_MSECS:

      return slice_config.working_set_msecs;

    case G_SLICE_CONFIG_CHUNK_SIZES:

      return MAX_SLAB_INDEX (allocator);

    case G_SLICE_CONFIG_COLOR_INCREMENT:

      return slice_config.color_increment;

    default:

      return 0;

    }

}

gint64*

g_slice_get_config_state (GSliceConfig ckey,

                          gint64       address,

                          guint       *n_values)

{

  guint i = 0;

  g_return_val_if_fail (n_values != NULL, NULL);

  *n_values = 0;

  switch (ckey)

    {

      gint64 array[64];

    case G_SLICE_CONFIG_CONTENTION_COUNTER:

      array[i++] = SLAB_CHUNK_SIZE (allocator, address);

      array[i++] = allocator->contention_counters[address];

      array[i++] = allocator_get_magazine_threshold (allocator, address);

      *n_values = i;

      return g_memdup (array, sizeof (array[0]) * *n_values);

    default:

      return NULL;

    }

}

static void

slice_config_init (SliceConfig *config)

{

  /* don't use g_malloc/g_message here */

  gchar buffer[1024];

  const gchar *val = _g_getenv_nomalloc ("G_SLICE", buffer);

  static const GDebugKey keys[] = {

    { "always-malloc", 1 << 0 },

  };

  gint flags = !val ? 0 : g_parse_debug_string (val, keys, G_N_ELEMENTS (keys));

  *config = slice_config;

  if (flags & (1 << 0))         /* always-malloc */

    {

      config->always_malloc = TRUE;

    }

}

static void

g_slice_init_nomessage (void)

{

  /* we may not use g_error() or friends here */

  mem_assert (sys_page_size == 0);

  mem_assert (MIN_MAGAZINE_SIZE >= 4);

#ifdef G_OS_WIN32

  {

    SYSTEM_INFO system_info;

    GetSystemInfo (&system_info);

    sys_page_size = system_info.dwPageSize;

  }

#else

  sys_page_size = sysconf (_SC_PAGESIZE); /* = sysconf (_SC_PAGE_SIZE); = getpagesize(); */

#endif

  mem_assert (sys_page_size >= 2 * LARGEALIGNMENT);

  mem_assert ((sys_page_size & (sys_page_size - 1)) == 0);

  slice_config_init (&allocator->config);

  // If the allocator is configured in such a way that the glib always uses

  // system malloc, then we dont need to allocate the book keeping array.

  // Thats why we return after that check and when it is successful.

#ifdef __SYMBIAN32__

  if(allocator->config.always_malloc)

  	return;

#endif /* __SYMBIAN32__ */

  allocator->min_page_size = sys_page_size;

#if HAVE_COMPLIANT_POSIX_MEMALIGN || HAVE_MEMALIGN

  /* allow allocation of pages up to 8KB (with 8KB alignment).

   * this is useful because many medium to large sized structures

   * fit less than 8 times (see [4]) into 4KB pages.

   * we allow very small page sizes here, to reduce wastage in

   * threads if only small allocations are required (this does

   * bear the risk of incresing allocation times and fragmentation

   * though).

   */

  allocator->min_page_size = MAX (allocator->min_page_size, 4096);

  allocator->max_page_size = MAX (allocator->min_page_size, 8192);

  allocator->min_page_size = MIN (allocator->min_page_size, 128);

#else

  /* we can only align to system page size */

  allocator->max_page_size = sys_page_size;

#endif

  allocator->magazine_mutex = NULL;     /* _g_slice_thread_init_nomessage() */

  allocator->magazines = g_new0 (ChunkLink*, MAX_SLAB_INDEX (allocator));

  allocator->contention_counters = g_new0 (guint, MAX_SLAB_INDEX (allocator));

  allocator->mutex_counter = 0;

  allocator->stamp_counter = MAX_STAMP_COUNTER; /* force initial update */

  allocator->last_stamp = 0;

  allocator->slab_mutex = NULL;         /* _g_slice_thread_init_nomessage() */

  allocator->slab_stack = g_new0 (SlabInfo*, MAX_SLAB_INDEX (allocator));

  allocator->color_accu = 0;

  magazine_cache_update_stamp();

  /* values cached for performance reasons */

  allocator->max_slab_chunk_size_for_magazine_cache = MAX_SLAB_CHUNK_SIZE (allocator);

  if (allocator->config.always_malloc || allocator->config.bypass_magazines)

    allocator->max_slab_chunk_size_for_magazine_cache = 0;      /* non-optimized cases */

  /* at this point, g_mem_gc_friendly() should be initialized, this

   * should have been accomplished by the above g_malloc/g_new calls

   */

}

static inline guint

allocator_categorize (gsize aligned_chunk_size)

{

  /* speed up the likely path */

  if (G_LIKELY (aligned_chunk_size && aligned_chunk_size <= allocator->max_slab_chunk_size_for_magazine_cache))

    return 1;           /* use magazine cache */

  /* the above will fail (max_slab_chunk_size_for_magazine_cache == 0) if the

   * allocator is still uninitialized, or if we are not configured to use the

   * magazine cache.

   */

  if (!sys_page_size)

    g_slice_init_nomessage ();

  // If the allocator is configured in such a way that the glib always uses

  // system malloc, then we dont need to allocate the book keeping array.

  // Thats why we return 0 after that check and when it is successful.

#ifdef __SYMBIAN32__

  if(allocator->config.always_malloc)

  	return 0;

#endif /* __SYMBIAN32__*/

  if (!allocator->config.always_malloc &&

      aligned_chunk_size &&

      aligned_chunk_size <= MAX_SLAB_CHUNK_SIZE (allocator))

    {

      if (allocator->config.bypass_magazines)

        return 2;       /* use slab allocator, see [2] */

      return 1;         /* use magazine cache */

    }

  return 0;             /* use malloc() */

}

void

_g_slice_thread_init_nomessage (void)

{

  /* we may not use g_error() or friends here */

  if (!sys_page_size)

    g_slice_init_nomessage();

  private_thread_memory = g_private_new (private_thread_memory_cleanup);

  allocator->magazine_mutex = g_mutex_new();

  allocator->slab_mutex = g_mutex_new();

}

static inline void

g_mutex_lock_a (GMutex *mutex,

                guint  *contention_counter)

{

  gboolean contention = FALSE;

  if (!g_mutex_trylock (mutex))

    {

      g_mutex_lock (mutex);

      contention = TRUE;

    }

  if (contention)

    {

      allocator->mutex_counter++;

      if (allocator->mutex_counter >= 1)        /* quickly adapt to contention */

        {

          allocator->mutex_counter = 0;

          *contention_counter = MIN (*contention_counter + 1, MAX_MAGAZINE_SIZE);

        }

    }

  else /* !contention */

    {

      allocator->mutex_counter--;

      if (allocator->mutex_counter < -11)       /* moderately recover magazine sizes */

        {

          allocator->mutex_counter = 0;

          *contention_counter = MAX (*contention_counter, 1) - 1;

        }

    }

}

static inline ThreadMemory*

thread_memory_from_self (void)

{

  ThreadMemory *tmem = g_private_get (private_thread_memory);

  if (G_UNLIKELY (!tmem))

    {

      const guint n_magazines = MAX_SLAB_INDEX (allocator);

      tmem = g_malloc0 (sizeof (ThreadMemory) + sizeof (Magazine) * 2 * n_magazines);

      tmem->magazine1 = (Magazine*) (tmem + 1);

      tmem->magazine2 = &tmem->magazine1[n_magazines];

      g_private_set (private_thread_memory, tmem);

    }

  return tmem;

}

static inline ChunkLink*

magazine_chain_pop_head (ChunkLink **magazine_chunks)

{

  /* magazine chains are linked via ChunkLink->next.

   * each ChunkLink->data of the toplevel chain may point to a subchain,

   * linked via ChunkLink->next. ChunkLink->data of the subchains just

   * contains uninitialized junk.

   */

  ChunkLink *chunk = (*magazine_chunks)->data;

  if (G_UNLIKELY (chunk))

    {

      /* allocating from freed list */

      (*magazine_chunks)->data = chunk->next;

    }

  else

    {

      chunk = *magazine_chunks;

      *magazine_chunks = chunk->next;

    }

  return chunk;

}

#if 0 /* useful for debugging */

static guint

magazine_count (ChunkLink *head)

{

  guint count = 0;

  if (!head)

    return 0;

  while (head)

    {

      ChunkLink *child = head->data;

      count += 1;

      for (child = head->data; child; child = child->next)

        count += 1;

      head = head->next;

    }

  return count;

}

#endif

static inline gsize

allocator_get_magazine_threshold (Allocator *allocator1,

                                  guint      ix)

{

  /* the magazine size calculated here has a lower bound of MIN_MAGAZINE_SIZE,

   * which is required by the implementation. also, for moderately sized chunks

   * (say >= 64 bytes), magazine sizes shouldn't be much smaller then the number

   * of chunks available per page/2 to avoid excessive traffic in the magazine

   * cache for small to medium sized structures.

   * the upper bound of the magazine size is effectively provided by

   * MAX_MAGAZINE_SIZE. for larger chunks, this number is scaled down so that

   * the content of a single magazine doesn't exceed ca. 16KB.

   */