path: root/libtnttk/cache.c

/*
 * Copyright (C) 2006,2007 Richard Braun <syn@sceen.net>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <errno.h>
#include <stdio.h>
#include <assert.h>
#include <stdint.h>
#include <unistd.h>
#include <pthread.h>
#include <sys/mman.h>

#include <tnttk/list.h>
#include <tnttk/cache.h>

static long page_size;
static long page_mask;

/*
 * Page alignment.
 */
static inline size_t
round_page(size_t offset)
{
  return (offset + (page_size - 1)) & ~page_mask;
}

/*
 * Word alignment.
 */
static inline size_t
round_word(size_t offset)
{
  return (offset + (sizeof(size_t) - 1)) & ~(sizeof(size_t) - 1);
}

/*
 * Color size and mask.
 */
#define SLAB_COLOR_SIZE	sizeof(size_t)
#define SLAB_COLOR_MASK	(SLAB_COLOR_SIZE - 1)

/*
 * Color alignment.
 */
static inline size_t
slab_color_align(size_t size)
{
  return (size + (SLAB_COLOR_SIZE - 1)) & ~SLAB_COLOR_MASK;
}

/*
 * Bufctl, a descriptor of a buffer in a slab.
 *
 * If the buffer is allocated, slab points to the owning slab,
 * otherwise next points to the next buffer in the free list.
 */
union bufctl
{
  struct slab *slab;
  union bufctl *next;
};

typedef union bufctl * bufctl_t;
#define BUFCTL_NULL ((bufctl_t)0)

/*
 * Slab, a block of cached objects.
 */
struct slab
{
  list_link_t link;
  struct cache *cache;
  unsigned int ref_count;
  bufctl_t free_buffers;
  void *address;
};

typedef struct slab * slab_t;
#define SLAB_NULL ((slab_t)0)

/*
 * Cache of objects, using the slab as the base unit of allocation.
 */
struct cache
{
  list_link_t cache_link;
  list_link_t reap_cache_link;
  list_head_t slabs;
  pthread_mutex_t mutex;
  slab_t alloc_slab;
  unsigned int flags;
  const char *name;
  size_t object_size;
  size_t buffer_size;
  size_t slab_size;
  size_t slab_real_size;
  unsigned int objects_per_slab;
  unsigned int free_object_count;
  unsigned int color_offset;
  unsigned int color_max_offset;
  cache_constructor_t constructor;
  cache_destructor_t destructor;
};

/*
 * List of all caches.
 */
static list_head_t cache_list;

/*
 * Lock for cache list.
 */
static pthread_mutex_t cache_list_mutex;

/*
 * List of caches from which pages can be reclaimed by the VM system.
 */
static list_head_t reap_cache_list;

/*
 * Lock for reap cache list.
 */
static pthread_mutex_t reap_cache_list_mutex;

/*
 * Cache of cache objects.
 */
static struct cache cache_cache_store;
static cache_t cache_cache;

/*
 * Lock a cache.
 */
static inline void
cache_lock(cache_t cache)
{
  pthread_mutex_lock(&cache->mutex);
}

/*
 * Unlock a cache.
 */
static inline void
cache_unlock(cache_t cache)
{
  pthread_mutex_unlock(&cache->mutex);
}

/*
 * Check that cache allocation properties are consistent, i.e. that
 * cache->free_objects_count is 0 if and only if cache->alloc_slab indicates
 * there is no slab to allocate from.
 *
 * Return 1 if the cache allocation properties are consistent, 0 otherwise.
 *
 * cache must be locked.
 */
static inline int
cache_alloc_consistent(cache_t cache)
{
  return ((cache->free_object_count == 0) == list_end(cache->alloc_slab));
}

/*
 * Align, compute and set the sizes of objects and buffers in the given cache.
 *
 * cache must be locked.
 */
static inline void
cache_set_object_size(cache_t cache, size_t object_size)
{
  cache->object_size = round_word(object_size);
  cache->buffer_size = cache->object_size + sizeof(union bufctl);
  cache->buffer_size = slab_color_align(cache->buffer_size);
}

/*
 * Compute and set the slab size of a cache. cache_set_object_size()
 * must be called on this cache prior to calling this function.
 *
 * cache must be locked.
 */
static inline void
cache_compute_slab_size(cache_t cache)
{
  size_t slab_size;

  /*
   * A slab must be able to contain at least one buffer and its own descriptor.
   */
  slab_size = round_page(cache->buffer_size + sizeof(struct slab));
  cache->slab_real_size = slab_size;
  cache->slab_size = slab_size - sizeof(struct slab);
  cache->objects_per_slab = cache->slab_size / cache->buffer_size;
}

/*
 * Compute and set the coloring properties of a cache.
 * cache_compute_slab_size() must be called on this cache prior to calling
 * this function.
 *
 * cache must be locked.
 */
static inline void
cache_compute_coloring(cache_t cache)
{
  size_t used_size;

  used_size = cache->buffer_size * cache->objects_per_slab;
  cache->color_max_offset = cache->slab_size - used_size;
  cache->color_offset = 0;
}

/*
 * No op constructor and destructor.
 */
static void
null_constructor(void *object)
{
}

static void
null_destructor(void *object)
{
}

/*
 * Allocate a slab into the given cache.
 *
 * cache must be locked.
 *
 * Return 0 if successful, !0 otherwise.
 */
static int
cache_grow(cache_t cache)
{
  cache_constructor_t constructor;
  bufctl_t bufctl;
  void *slab_data;
  slab_t slab;
  size_t i;

  assert(cache_alloc_consistent(cache));
  slab_data = mmap(NULL, cache->slab_real_size,
                   PROT_READ | PROT_WRITE | PROT_EXEC,
                   MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);

  if (slab_data == NULL)
    return ENOMEM;

  slab = slab_data + cache->slab_size;

  /*
   * Initialize the slab.
   */
  slab->cache = cache;
  slab->ref_count = 0;
  slab->address = slab_data;

  /*
   * cache->alloc_slab is a pointer to a slab which has at least one
   * free object.
   */
  if (list_end(cache->alloc_slab))
    cache->alloc_slab = slab;

  /*
   * Handle cache coloring.
   */
  slab_data += cache->color_offset;
  cache->color_offset += SLAB_COLOR_SIZE;

  if (cache->color_offset >= cache->color_max_offset)
    cache->color_offset = 0;

  /*
   * Set constructor.
   */
  if (cache->constructor == CACHE_CONSTRUCTOR_NULL)
    constructor = null_constructor;

  else
    constructor = cache->constructor;

  /*
   * Initialize bufctls and objects.
   */
  bufctl = slab_data + cache->object_size;
  slab->free_buffers = bufctl;

  for (i = 1; i < cache->objects_per_slab; i++)
    {
      constructor(slab_data);
      slab_data += cache->buffer_size;
      bufctl->next = slab_data + cache->object_size;
      bufctl = bufctl->next;
    }

  constructor(slab_data);
  bufctl->next = BUFCTL_NULL;
  list_insert_tail(&cache->slabs, slab, link);
  cache->free_object_count += cache->objects_per_slab;
  assert(cache_alloc_consistent(cache));
  return 0;
}

/*
 * Remove fully free slabs from the cache, destroy all objects within the
 * slab and release the underlying pages.
 *
 * cache must be locked.
 */
static void
cache_reap(cache_t cache)
{
  cache_destructor_t destructor;
  slab_t slab, prev_slab;
  bufctl_t bufctl;
  void *object;
  int error;

  assert(cache_alloc_consistent(cache));

  /*
   * Set destructor.
   */
  if (cache->destructor == CACHE_DESTRUCTOR_NULL)
    destructor = null_destructor;

  else
    destructor = cache->destructor;

  /*
   * Process the list in reverse order since fully free slabs are at the end.
   */
  for (slab = list_last(&cache->slabs, slab_t);
       !list_end(slab) && (slab->ref_count == 0);
       slab = prev_slab)
    {
      assert(list_end(list_next(slab, link)));
      bufctl = slab->free_buffers;

      while (bufctl != BUFCTL_NULL)
        {
          object = ((void *)bufctl) - cache->object_size;
          destructor(object);
          bufctl = bufctl->next;
        }

      prev_slab = list_prev(slab, link);

      /*
       * Can't use this slab anymore. Use next, which is the list end. There
       * can't be any free slabs left, as cache->alloc_slab always points to
       * the first free (or partially free) slab, and all slabs after this one
       * have already been deleted.
       */
      if (cache->alloc_slab == slab)
        cache->alloc_slab = list_next(slab, link);

      list_remove(&cache->slabs, slab, link);
      cache->free_object_count -= cache->objects_per_slab;
      error = munmap(slab->address, cache->slab_real_size);
      assert(!error);
      assert(cache_alloc_consistent(cache));
    }

  pthread_mutex_lock(&reap_cache_list_mutex);
  list_remove(&reap_cache_list, cache, reap_cache_link);
  pthread_mutex_unlock(&reap_cache_list_mutex);
}

void *
cache_alloc(cache_t cache)
{
  bufctl_t bufctl;
  slab_t slab;
  void *object;

  cache_lock(cache);
  assert(cache_alloc_consistent(cache));

  if (list_end(cache->alloc_slab))
    {
      int error;

      error = cache_grow(cache);

      if (error)
        {
          cache_unlock(cache);
          return NULL;
        }
    }

  slab = cache->alloc_slab;
  bufctl = slab->free_buffers;
  object = ((void *)bufctl) - cache->object_size;
  slab->free_buffers = bufctl->next;
  bufctl->slab = slab;
  slab->ref_count++;
  cache->free_object_count--;

  /*
   * The current slab is full, handle cache->alloc_slab. We can directly take
   * the next slab since they are sorted (full slabs first, partially free
   * slabs next, fully free slabs at the end of the list). If there is no slab
   * left, cache->alloc_slab will be set to the list end.
   */
  if (slab->ref_count == cache->objects_per_slab)
    cache->alloc_slab = list_next(cache->alloc_slab, link);

  assert(cache_alloc_consistent(cache));
  cache_unlock(cache);
  return object;
}

void
cache_free(cache_t cache, void *address)
{
  bufctl_t bufctl;
  slab_t slab;

  cache_lock(cache);
  assert(cache_alloc_consistent(cache));
  bufctl = address + cache->object_size;
  slab = bufctl->slab;
  bufctl->next = slab->free_buffers;
  slab->free_buffers = bufctl;
  slab->ref_count--;
  cache->free_object_count++;

  /*
   * Special case optimized.
   */
  if ((cache->alloc_slab == SLAB_NULL)
      && (slab == list_last(&cache->slabs, slab_t)))
    cache->alloc_slab = slab;

  /*
   * This slab is now partially free. Keep the slab list sorted.
   */
  else if (slab->ref_count == (cache->objects_per_slab - 1))
    {
      list_remove(&cache->slabs, slab, link);

      if (cache->alloc_slab == SLAB_NULL)
        list_insert_tail(&cache->slabs, slab, link);

      else
        list_insert_before(&cache->slabs, cache->alloc_slab, slab, link);

      cache->alloc_slab = slab;
    }

  /*
   * This slab is now completely free, move it at the end of the list for
   * easy removal if memory is reclaimed.
   */
  else if (slab->ref_count == 0)
    {
      if (slab != list_last(&cache->slabs, slab_t))
        {
          if (slab == cache->alloc_slab)
            cache->alloc_slab = list_next(slab, link);

          list_remove(&cache->slabs, slab, link);
          list_insert_tail(&cache->slabs, slab, link);
        }

      if (list_link_null(cache, reap_cache_link))
        {
          pthread_mutex_lock(&reap_cache_list_mutex);
          list_insert_tail(&reap_cache_list, cache, reap_cache_link);
          pthread_mutex_unlock(&reap_cache_list_mutex);
        }
    }

  assert(cache_alloc_consistent(cache));
  cache_unlock(cache);
}

/*
 * Cache constructor.
 */
static void
cache_constructor(void *object)
{
  cache_t cache;

  cache = (cache_t)object;
  list_link_init(cache, reap_cache_link);
  list_init(&cache->slabs);
  pthread_mutex_init(&cache->mutex, NULL);
  cache->alloc_slab = list_last(&cache->slabs, slab_t);
  cache->free_object_count = 0;

  /*
   * XXX Currently unused.
   */
  cache->flags = 0;
}

/*
 * Cache destructor.
 */
static void
cache_destructor(void *object)
{
  cache_t cache;

  cache = (cache_t)object;
  assert(list_link_null(cache, reap_cache_link));
  assert(list_empty(&cache->slabs));
  pthread_mutex_destroy(&cache->mutex);
  assert(cache_alloc_consistent(cache));
  assert(cache->flags == 0);
}

cache_t
cache_create(const char *name, size_t object_size,
             cache_constructor_t constructor,
             cache_destructor_t destructor)
{
  cache_t cache;

  cache = cache_alloc(cache_cache);
  cache->name = name;
  cache_set_object_size(cache, object_size);
  cache_compute_slab_size(cache);
  cache_compute_coloring(cache);
  cache->constructor = constructor;
  cache->destructor = destructor;
  pthread_mutex_lock(&cache_list_mutex);
  list_insert_tail(&cache_list, cache, cache_link);
  pthread_mutex_unlock(&cache_list_mutex);
  return cache;
}

void
cache_destroy(cache_t cache)
{
  cache_lock(cache);
  assert(cache_alloc_consistent(cache));

  if (!list_end(cache->alloc_slab))
    cache_reap(cache);

  assert(list_empty(&cache->slabs));
  pthread_mutex_lock(&cache_list_mutex);
  list_remove(&cache_list, cache, cache_link);
  pthread_mutex_unlock(&cache_list_mutex);
  cache_unlock(cache);
  cache_free(cache_cache, cache);
}

void
cache_show_info(cache_t cache)
{
  if (cache == CACHE_NULL)
    {
      pthread_mutex_lock(&cache_list_mutex);

      list_for_each(&cache_list, cache, cache_link)
        cache_show_info(cache);

      pthread_mutex_unlock(&cache_list_mutex);
    }

  else
    {
      slab_t slab;
      size_t i;

      cache_lock(cache);
      printf("slab: cache info :\n");
      printf("slab: flags             : 0x0 (currently unused)\n");
      printf("slab: name              : %s\n", cache->name);
      printf("slab: object_size       : %u\n", cache->object_size);
      printf("slab: buffer size       : %u\n", cache->buffer_size);
      printf("slab: slab_size         : %u\n", cache->slab_size);
      printf("slab: slab_real_size    : %u\n", cache->slab_real_size);
      printf("slab: objects_per_slab  : %u\n", cache->objects_per_slab);
      printf("slab: free_object_count : %u\n", cache->free_object_count);
      printf("slab: color_offset      : %u\n", cache->color_offset);
      printf("slab: color_max_offset  : %u\n", cache->color_max_offset);

      i = 0;

      list_for_each(&cache->slabs, slab, link)
        {
          printf("slab:  slab %u : ref_count : %u %s\n", i, slab->ref_count,
                 (slab == cache->alloc_slab) ? "(is alloc slab)" : "");
          i++;
        }

      cache_unlock(cache);
    }
}

void
slab_reclaim(void)
{
  cache_t cache;

  pthread_mutex_lock(&reap_cache_list_mutex);

  while (!list_empty(&reap_cache_list))
    {
      cache = list_first(&reap_cache_list, cache_t);
      cache_lock(cache);
      cache_reap(cache);
      cache_unlock(cache);
    }

  pthread_mutex_unlock(&reap_cache_list_mutex);
}

void
slab_init(void)
{
  page_size = sysconf(_SC_PAGESIZE);
  page_mask = page_size - 1;

  /*
   * Manually create the cache of cache objects (we can't use
   * cache_create() here).
   */
  cache_cache = &cache_cache_store;
  cache_constructor(cache_cache);
  cache_cache->name = "cache";
  cache_set_object_size(cache_cache, sizeof(struct cache));
  cache_compute_slab_size(cache_cache);
  cache_compute_coloring(cache_cache);
  cache_cache->constructor = cache_constructor;
  cache_cache->destructor = cache_destructor;
  list_init(&cache_list);
  pthread_mutex_init(&cache_list_mutex, NULL);
  list_init(&reap_cache_list);
  pthread_mutex_init(&reap_cache_list_mutex, NULL);
  list_insert_tail(&cache_list, cache_cache, cache_link);
}