/* GLIB sliced memory - fast concurrent memory chunk allocator

 * Copyright (C) 2005 Tim Janik

 *

 * 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/>.

 */

/* MT safe */

#include "config.h"

#include "glibconfig.h"

#if     defined HAVE_POSIX_MEMALIGN && defined POSIX_MEMALIGN_WITH_COMPLIANT_ALLOCS

#  define HAVE_COMPLIANT_POSIX_MEMALIGN 1

#endif

#if defined(HAVE_COMPLIANT_POSIX_MEMALIGN) && !defined(_XOPEN_SOURCE)

#define _XOPEN_SOURCE 600       /* posix_memalign() */

#endif

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

#include <string.h>

#include <errno.h>

#ifdef G_OS_UNIX

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

#endif

#ifdef G_OS_WIN32

#include <windows.h>

#include <process.h>

#endif

#include <stdio.h>              /* fputs/fprintf */

#include "gslice.h"

#include "gmain.h"

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

#include "gstrfuncs.h"

#include "gutils.h"

#include "gtrashstack.h"

#include "gtestutils.h"

#include "gthread.h"

#include "glib_trace.h"

#include "valgrind.h"

/**

 * SECTION:memory_slices

 * @title: Memory Slices

 * @short_description: efficient way to allocate groups of equal-sized

 *     chunks of memory

 *

 * Memory slices provide a space-efficient and multi-processing scalable

 * way to allocate equal-sized pieces of memory, just like the original

 * #GMemChunks (from GLib 2.8), while avoiding their excessive

 * memory-waste, scalability and performance problems.

 *

 * To achieve these goals, the slice allocator uses a sophisticated,

 * layered design that has been inspired by Bonwick's slab allocator

 * ([Bonwick94](http://citeseer.ist.psu.edu/bonwick94slab.html)

 * Jeff Bonwick, The slab allocator: An object-caching kernel

 * memory allocator. USENIX 1994, and

 * [Bonwick01](http://citeseer.ist.psu.edu/bonwick01magazines.html)

 * Bonwick and Jonathan Adams, Magazines and vmem: Extending the

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

 *

 * It uses posix_memalign() to optimize allocations of many equally-sized

 * chunks, and has per-thread free lists (the so-called magazine layer)

 * to quickly satisfy allocation requests of already known structure sizes.

 * This is accompanied by extra caching logic to keep freed memory around

 * for some time before returning it to the system. Memory that is unused

 * due to alignment constraints is used for cache colorization (random

 * distribution of chunk addresses) to improve CPU cache utilization. The

 * caching layer of the slice allocator adapts itself to high lock contention

 * to improve scalability.

 *

 * The slice allocator can allocate blocks as small as two pointers, and

 * unlike malloc(), it does not reserve extra space per block. For large block

 * sizes, g_slice_new() and g_slice_alloc() will automatically delegate to the

 * system malloc() implementation. For newly written code it is recommended

 * to use the new `g_slice` API instead of g_malloc() and

 * friends, as long as objects are not resized during their lifetime and the

 * object size used at allocation time is still available when freeing.

 *

 * Here is an example for using the slice allocator:

 * |[ 

 * gchar *mem[10000];

 * gint i;

 *

 * // Allocate 10000 blocks.

 * for (i = 0; i < 10000; i++)

 *   {

 *     mem[i] = g_slice_alloc (50);

 *

 *     // Fill in the memory with some junk.

 *     for (j = 0; j < 50; j++)

 *       mem[i][j] = i * j;

 *   }

 *

 * // Now free all of the blocks.

 * for (i = 0; i < 10000; i++)

 *   g_slice_free1 (50, mem[i]);

 * ]|

 *

 * And here is an example for using the using the slice allocator

 * with data structures:

 * |[ 

 * GRealArray *array;

 *

 * // Allocate one block, using the g_slice_new() macro.

 * array = g_slice_new (GRealArray);

 *

 * // We can now use array just like a normal pointer to a structure.

 * array->data            = NULL;

 * array->len             = 0;

 * array->alloc           = 0;

 * array->zero_terminated = (zero_terminated ? 1 : 0);

 * array->clear           = (clear ? 1 : 0);

 * array->elt_size        = elt_size;

 *

 * // We can free the block, so it can be reused.

 * g_slice_free (GRealArray, array);

 * ]|

 */

/* 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 --- */

typedef struct _ChunkLink      ChunkLink;

typedef struct _SlabInfo       SlabInfo;

typedef struct _CachedMagazine CachedMagazine;

struct _ChunkLink {

  ChunkLink *next;

  ChunkLink *data;

};

struct _SlabInfo {

  ChunkLink *chunks;

  guint n_allocated;

  SlabInfo *next, *prev;

};

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;

typedef struct {

  gboolean always_malloc;

  gboolean bypass_magazines;

  gboolean debug_blocks;

  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;

/* --- g-slice 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);

static inline gsize allocator_get_magazine_threshold (Allocator *allocator,

                                                      guint      ix);

/* --- g-slice memory checker --- */

static void     smc_notify_alloc  (void   *pointer,

                                   size_t  size);

static int      smc_notify_free   (void   *pointer,

                                   size_t  size);

/* --- variables --- */

static GPrivate    private_thread_memory = G_PRIVATE_INIT (private_thread_memory_cleanup);

static gsize       sys_page_size = 0;

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

static SliceConfig slice_config = {

  FALSE,        /* always_malloc */

  FALSE,        /* bypass_magazines */

  FALSE,        /* debug_blocks */

  15 * 1000,    /* working_set_msecs */

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

};

static GMutex      smc_tree_mutex; /* mutex for G_SLICE=debug-blocks */

/* --- auxiliary 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)

{

  const gchar *val;

  *config = slice_config;

  val = getenv ("G_SLICE");

  if (val != NULL)

    {

      gint flags;

      const GDebugKey keys[] = {

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

        { "debug-blocks",  1 << 1 },

      };

      flags = g_parse_debug_string (val, keys, G_N_ELEMENTS (keys));

      if (flags & (1 << 0))

        config->always_malloc = TRUE;

      if (flags & (1 << 1))

        config->debug_blocks = TRUE;

    }

  else

    {

      /* G_SLICE was not specified, so check if valgrind is running and

       * disable ourselves if it is.

       *

       * This way it's possible to force gslice to be enabled under

       * valgrind just by setting G_SLICE to the empty string.

       */

      if (RUNNING_ON_VALGRIND)

        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);

  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 increasing 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

  if (allocator->config.always_malloc)

    {

      allocator->contention_counters = NULL;

      allocator->magazines = NULL;

      allocator->slab_stack = NULL;

    }

  else

    {

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

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

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

    }

  allocator->mutex_counter = 0;

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

  allocator->last_stamp = 0;

  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 */

}

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 */

  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() */

}

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))

    {

      static GMutex init_mutex;

      guint n_magazines;

      g_mutex_lock (&init_mutex);

      if G_UNLIKELY (sys_page_size == 0)

        g_slice_init_nomessage ();

      g_mutex_unlock (&init_mutex);

      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 *allocator,

                                  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.

   */

  gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);

  guint threshold = MAX (MIN_MAGAZINE_SIZE, allocator->max_page_size / MAX (5 * chunk_size, 5 * 32));

  guint contention_counter = allocator->contention_counters[ix];

  if (G_UNLIKELY (contention_counter))  /* single CPU bias */

    {

      /* adapt contention counter thresholds to chunk sizes */

      contention_counter = contention_counter * 64 / chunk_size;

      threshold = MAX (threshold, contention_counter);

    }

  return threshold;

}

/* --- magazine cache --- */

static inline void

magazine_cache_update_stamp (void)

{

  if (allocator->stamp_counter >= MAX_STAMP_COUNTER)

    {

      GTimeVal tv;

      g_get_current_time (&tv;;

      allocator->last_stamp = tv.tv_sec * 1000 + tv.tv_usec / 1000; /* milli seconds */

      allocator->stamp_counter = 0;

    }

  else

    allocator->stamp_counter++;

}

static inline ChunkLink*

magazine_chain_prepare_fields (ChunkLink *magazine_chunks)

{

  ChunkLink *chunk1;

  ChunkLink *chunk2;

  ChunkLink *chunk3;

  ChunkLink *chunk4;

  /* checked upon initialization: mem_assert (MIN_MAGAZINE_SIZE >= 4); */

  /* ensure a magazine with at least 4 unused data pointers */

  chunk1 = magazine_chain_pop_head (&magazine_chunks);

  chunk2 = magazine_chain_pop_head (&magazine_chunks);

  chunk3 = magazine_chain_pop_head (&magazine_chunks);

  chunk4 = magazine_chain_pop_head (&magazine_chunks);

  chunk4->next = magazine_chunks;

  chunk3->next = chunk4;

  chunk2->next = chunk3;

  chunk1->next = chunk2;

  return chunk1;

}

/* access the first 3 fields of a specially prepared magazine chain */

#define magazine_chain_prev(mc)         ((mc)->data)

#define magazine_chain_stamp(mc)        ((mc)->next->data)

#define magazine_chain_uint_stamp(mc)   GPOINTER_TO_UINT ((mc)->next->data)

#define magazine_chain_next(mc)         ((mc)->next->next->data)

#define magazine_chain_count(mc)        ((mc)->next->next->next->data)

static void

magazine_cache_trim (Allocator *allocator,

                     guint      ix,

                     guint      stamp)

{

  /* g_mutex_lock (allocator->mutex); done by caller */

  /* trim magazine cache from tail */

  ChunkLink *current = magazine_chain_prev (allocator->magazines[ix]);

  ChunkLink *trash = NULL;

  while (ABS (stamp - magazine_chain_uint_stamp (current)) >= allocator->config.working_set_msecs)

    {

      /* unlink */

      ChunkLink *prev = magazine_chain_prev (current);

      ChunkLink *next = magazine_chain_next (current);

      magazine_chain_next (prev) = next;

      magazine_chain_prev (next) = prev;

      /* clear special fields, put on trash stack */

      magazine_chain_next (current) = NULL;

      magazine_chain_count (current) = NULL;

      magazine_chain_stamp (current) = NULL;

      magazine_chain_prev (current) = trash;

      trash = current;

      /* fixup list head if required */

      if (current == allocator->magazines[ix])

        {

          allocator->magazines[ix] = NULL;

          break;

        }

      current = prev;

    }

  g_mutex_unlock (&allocator->magazine_mutex);

  /* free trash */

  if (trash)

    {

      const gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);

      g_mutex_lock (&allocator->slab_mutex);

      while (trash)

        {

          current = trash;

          trash = magazine_chain_prev (current);

          magazine_chain_prev (current) = NULL; /* clear special field */

          while (current)

            {

              ChunkLink *chunk = magazine_chain_pop_head (¤t;;

              slab_allocator_free_chunk (chunk_size, chunk);

            }

        }

      g_mutex_unlock (&allocator->slab_mutex);

    }

}

static void

magazine_cache_push_magazine (guint      ix,

                              ChunkLink *magazine_chunks,

                              gsize      count) /* must be >= MIN_MAGAZINE_SIZE */

{

  ChunkLink *current = magazine_chain_prepare_fields (magazine_chunks);

  ChunkLink *next, *prev;

  g_mutex_lock (&allocator->magazine_mutex);

  /* add magazine at head */

  next = allocator->magazines[ix];

  if (next)

    prev = magazine_chain_prev (next);

  else

    next = prev = current;

  magazine_chain_next (prev) = current;

  magazine_chain_prev (next) = current;

  magazine_chain_prev (current) = prev;

  magazine_chain_next (current) = next;

  magazine_chain_count (current) = (gpointer) count;

  /* stamp magazine */

  magazine_cache_update_stamp();

  magazine_chain_stamp (current) = GUINT_TO_POINTER (allocator->last_stamp);

  allocator->magazines[ix] = current;

  /* free old magazines beyond a certain threshold */

  magazine_cache_trim (allocator, ix, allocator->last_stamp);

  /* g_mutex_unlock (allocator->mutex); was done by magazine_cache_trim() */

}

static ChunkLink*

magazine_cache_pop_magazine (guint  ix,

                             gsize *countp)

{

  g_mutex_lock_a (&allocator->magazine_mutex, &allocator->contention_counters[ix]);

  if (!allocator->magazines[ix])

    {

      guint magazine_threshold = allocator_get_magazine_threshold (allocator, ix);

      gsize i, chunk_size = SLAB_CHUNK_SIZE (allocator, ix);

      ChunkLink *chunk, *head;

      g_mutex_unlock (&allocator->magazine_mutex);

      g_mutex_lock (&allocator->slab_mutex);

      head = slab_allocator_alloc_chunk (chunk_size);

      head->data = NULL;

      chunk = head;

      for (i = 1; i < magazine_threshold; i++)

        {

          chunk->next = slab_allocator_alloc_chunk (chunk_size);

          chunk = chunk->next;

          chunk->data = NULL;

        }

      chunk->next = NULL;

      g_mutex_unlock (&allocator->slab_mutex);

      *countp = i;

      return head;

    }

  else

    {

      ChunkLink *current = allocator->magazines[ix];

      ChunkLink *prev = magazine_chain_prev (current);

      ChunkLink *next = magazine_chain_next (current);

      /* unlink */

      magazine_chain_next (prev) = next;

      magazine_chain_prev (next) = prev;

      allocator->magazines[ix] = next == current ? NULL : next;

      g_mutex_unlock (&allocator->magazine_mutex);

      /* clear special fields and hand out */

      *countp = (gsize) magazine_chain_count (current);

      magazine_chain_prev (current) = NULL;

      magazine_chain_next (current) = NULL;

      magazine_chain_count (current) = NULL;

      magazine_chain_stamp (current) = NULL;

      return current;

    }

}

/* --- thread magazines --- */

static void

private_thread_memory_cleanup (gpointer data)

{

  ThreadMemory *tmem = data;

  const guint n_magazines = MAX_SLAB_INDEX (allocator);

  guint ix;

  for (ix = 0; ix < n_magazines; ix++)

    {

      Magazine *mags[2];

      guint j;

      mags[0] = &tmem->magazine1[ix];

      mags[1] = &tmem->magazine2[ix];

      for (j = 0; j < 2; j++)

        {

          Magazine *mag = mags[j];

          if (mag->count >= MIN_MAGAZINE_SIZE)

            magazine_cache_push_magazine (ix, mag->chunks, mag->count);

          else

            {

              const gsize chunk_size = SLAB_CHUNK_SIZE (allocator, ix);

              g_mutex_lock (&allocator->slab_mutex);

              while (mag->chunks)

                {

                  ChunkLink *chunk = magazine_chain_pop_head (&mag->chunks);

                  slab_allocator_free_chunk (chunk_size, chunk);

                }

              g_mutex_unlock (&allocator->slab_mutex);

            }

        }

    }

  g_free (tmem);

}

static void

thread_memory_magazine1_reload (ThreadMemory *tmem,

                                guint         ix)

{

  Magazine *mag = &tmem->magazine1[ix];

  mem_assert (mag->chunks == NULL); /* ensure that we may reset mag->count */

  mag->count = 0;

  mag->chunks = magazine_cache_pop_magazine (ix, &mag->count);

}

static void

thread_memory_magazine2_unload (ThreadMemory *tmem,

                                guint         ix)

{

  Magazine *mag = &tmem->magazine2[ix];

  magazine_cache_push_magazine (ix, mag->chunks, mag->count);

  mag->chunks = NULL;

  mag->count = 0;

}

static inline void

thread_memory_swap_magazines (ThreadMemory *tmem,

                              guint         ix)

{

  Magazine xmag = tmem->magazine1[ix];

  tmem->magazine1[ix] = tmem->magazine2[ix];

  tmem->magazine2[ix] = xmag;

}

static inline gboolean

thread_memory_magazine1_is_empty (ThreadMemory *tmem,

                                  guint         ix)

{

  return tmem->magazine1[ix].chunks == NULL;

}

static inline gboolean

thread_memory_magazine2_is_full (ThreadMemory *tmem,

                                 guint         ix)

{

  return tmem->magazine2[ix].count >= allocator_get_magazine_threshold (allocator, ix);

}

static inline gpointer

thread_memory_magazine1_alloc (ThreadMemory *tmem,

                               guint         ix)

{

  Magazine *mag = &tmem->magazine1[ix];

  ChunkLink *chunk = magazine_chain_pop_head (&mag->chunks);

  if (G_LIKELY (mag->count > 0))

    mag->count--;

  return chunk;

}

static inline void

thread_memory_magazine2_free (ThreadMemory *tmem,

                              guint         ix,

                              gpointer      mem)

{

  Magazine *mag = &tmem->magazine2[ix];

  ChunkLink *chunk = mem;

  chunk->data = NULL;

  chunk->next = mag->chunks;

  mag->chunks = chunk;

  mag->count++;

}

/* --- API functions --- */

/**

 * g_slice_new:

 * @type: the type to allocate, typically a structure name

 *

 * A convenience macro to allocate a block of memory from the

 * slice allocator.

 *

 * It calls g_slice_alloc() with `sizeof (@type)` and casts the

 * returned pointer to a pointer of the given type, avoiding a type

 * cast in the source code. Note that the underlying slice allocation

 * mechanism can be changed with the [`G_SLICE=always-malloc`][G_SLICE]

 * environment variable.

 *

 * This can never return %NULL as the minimum allocation size from

 * `sizeof (@type)` is 1 byte.

 *

 * Returns: (not nullable): a pointer to the allocated block, cast to a pointer

 *    to @type