su_alloc.c

Sofia SIP is an open-source SIP User-Agent library, compliant with the IETF RFC3261 specification.

/*
 * This file is part of the Sofia-SIP package
 *
 * Copyright (C) 2005 Nokia Corporation.
 *
 * Contact: Pekka Pessi <[e-mail]>
 *
 * 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, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 */

#include "config.h"

/**@defgroup su_alloc Memory Management Tutorial
 *
 * This page gives a short overview of home-based memory management used
 * with Sofia. Such home-based memory management is useful when a lot of
 * memory blocks are allocated for given task. The allocations are done via
 * the @e memory @e home, which keeps a reference to each block. When the
 * memory home is then freed, it will free all blocks to which it has
 * reference.
 *
 * Typically, there is a @e home @e object which contains a su_home_t
 * structure in the beginning of the object (sort of inheritance from
 * su_home_t):
 * @code
 * struct context {
 *   su_home_t ctx_home[1];
 *   other_t  *ctx_stuff;
 *   ...
 * }
 * @endcode
 * 
 * A new home memory pool can be created with su_home_new():
 * @code
 * struct context *ctx = su_home_new(sizeof (struct context));
 * @endcode
 *
 * It is also possible to create a secondary memory pool that can be
 * released separately:
 *
 * @code
 * struct context *ctx = su_home_clone(tophome, sizeof (struct context));
 * @endcode
 *
 * Note that the tophome has a reference to @a ctx structure; whenever
 * tophome is freed, the @a ctx is also freed.
 * 
 * You can also create an independent home object by passing NULL as @a
 * tophome argument. This is identical to the call to su_home_new().
 *
 * The memory allocations using @a ctx proceed then as follows:
 * @code
 *    zeroblock = su_zalloc(ctx->ctx_home, sizeof (*zeroblock));
 * @endcode
 *
 * The home memory pool - the home object and all the memory blocks
 * allocated using it - are freed when su_home_unref() is called:
 *
 * @code
 *    su_home_unref(ctx->ctx_home).
 * @endcode
 *
 * @note For historical reasons, su_home_unref() is also known as
 * su_home_zap().
 *
 * As you might have guessed, it is also possible to use reference counting
 * with home objects. The function su_home_ref() increases the reference
 * count, su_home_unref() decreases it. A newly allocated or initialized
 * home object has reference count of 1.
 *
 * @note Please note that while it is possible to create new references to
 * secondary home objects which have a parent home, the secondary home
 * objects will always be destroyed when the parent home is destroyed even
 * if there are other references left to them.
 *
 * The memory blocks in a cloned home object are freed when the object with
 * home itself is freed:
 * @code
 *    su_free(tophome, ctx);
 * @endcode
 * 
 * @note
 *
 * The su_home_destroy() function is deprecated as it does not free the home
 * object itself. Like su_home_deinit(), it should be called only on home
 * objects with reference count of 1.
 *
 * The function su_home_init() initializes a home object structure. When the
 * initialized home object is destroyed or deinitialized or its reference
 * count reaches zero, the memory allocate thorugh it reclaimed but the home
 * object structure itself is not freed.
 *
 * @section su_home_destructor_usage Destructors
 *
 * It is possible to give a destructor function to a home object. The
 * destructor releases other resources associated with the home object
 * besides memory. The destructor function will be called when the reference
 * count of home reaches zero (upon calling su_home_unref()) or the home
 * object is otherwise deinitialized (calling su_home_deinit() on
 * objects allocated from stack).
 *
 * @section su_home_move_example Combining Allocations
 *
 * In some cases, an operation that makes multiple memory allocations may
 * fail, making those allocations redundant. If the allocations are made
 * through a temporary home, they can be conveniently freed by calling
 * su_home_deinit(), for instance. If, however, the operation is successful,
 * and one wants to keep the allocations, the allocations can be combined
 * into an existing home with su_home_move(). For example,
 * @code
 * int example(su_home_t *home, ...) 
 * {
 *   su_home_t temphome[1] = { SU_HOME_INIT(temphome) };
 *   
 *   ... do lot of allocations with temphome ...
 *  
 *   if (success) 
 *     su_home_move(home, temphome);
 *   su_home_deinit(temphome);
 *
 *   return success;
 * }
 * @endcode
 *
 * Note that the @a temphome is deinitialized in every case, but when
 * operation is successful, the allocations are moved from @a temphome to @a
 * home.
 *
 * @section su_alloc_threadsafe Threadsafe Operation
 *
 * If multiple threads need to access same home object, it must be marked as
 * @e threadsafe by calling su_home_threadsafe() with the home pointer as
 * argument. The threadsafeness is not inherited by clones.
 *
 * The threadsafe home objects can be locked and unlocked with
 * su_home_mutex_lock() and su_home_mutex_unlock(). These operations are
 * no-op on home object that is not threadsafe.
 *
 * @section su_alloc_preloading Preloading a Memory Home
 *
 * In some situations there is quite heavy overhead if the global heap
 * allocator is used. The overhead caused by the large number of small
 * allocations can be reduced by using su_home_preload(): it allocates or
 * preloads some a memory to home to be used as a kind of private heap. The
 * preloaded memory area is then used to satisfy small enough allocations. 
 * For instance, the SIP parser typically preloads some 2K of memory when it
 * starts to parse the message.
 *
 * @section su_alloc_stack Using Stack
 *
 * In some situation, it is sensible to use memory allocated from stack for
 * some operations. The su_home_auto() function can be used for that
 * purpose. The memory area from stack is used to satisfy the allocations as
 * far as possible; if it is not enough, allocation is made from heap.
 *
 * The word @e auto refers to the automatic scope; however, the home object
 * that was initialized with su_home_auto() must be explicitly deinitialized
 * with su_home_deinit() or su_home_unref() when the program exits the scope
 * where the stack frame used in su_home_auto() was allocated.
 */

/**@ingroup su_alloc
 * @CFILE su_alloc.c  Home-based memory management.
 *
 * @author Pekka Pessi <[e-mail]>.
 * 
 * @date Created: Thu Aug 19 01:12:25 1999 ppessi
 */

#include <sofia-sip/su_config.h>
#include "sofia-sip/su_alloc.h"
#include "sofia-sip/su_alloc_stat.h"
#include "sofia-sip/su_errno.h"

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <memory.h>
#include <limits.h>

#include <assert.h>

int (*_su_home_locker)(void *mutex);
int (*_su_home_unlocker)(void *mutex);

int (*_su_home_mutex_locker)(void *mutex);
int (*_su_home_mutex_trylocker)(void *mutex);
int (*_su_home_mutex_unlocker)(void *mutex);

void (*_su_home_destroy_mutexes)(void *mutex);

#if HAVE_FREE_NULL
#define safefree(x) free((x))
#else
su_inline void safefree(void *b) { b ? free(b) : (void)0; }
#endif

#define MEMLOCK(h)   \
  ((void)((h) && (h)->suh_lock ? _su_home_locker((h)->suh_lock) : 0), (h)->suh_blocks)
#define UNLOCK(h) ((void)((h) && (h)->suh_lock ? _su_home_unlocker((h)->suh_lock) : 0), NULL)

#ifdef NDEBUG
#define MEMCHECK 0
#define MEMCHECK_EXTRA 0
#elif !defined(MEMCHECK)
/* Default settings for valgrinding */
#define MEMCHECK 1
#define MEMCHECK_EXTRA 0
#elif !defined(MEMCHECK_EXTRA)
#define MEMCHECK_EXTRA sizeof (size_t)
#endif

enum { 
  SUB_N = 31,			/**< Initial size */
  SUB_N_AUTO = 7,		/**< Initial size for autohome */
  SUB_P = 29			/**< Secondary probe.
				 * Secondary probe must be relative prime 
				 * with all sub_n values */
};		

#define ALIGNMENT (8)
#define ALIGN(n) (size_t)(((n) + (ALIGNMENT - 1)) & (size_t)~(ALIGNMENT - 1))
#define SIZEBITS (sizeof (unsigned) * 8 - 1)

typedef struct {
  unsigned sua_size:SIZEBITS;	/**< Size of the block */
  unsigned sua_home:1;		/**< Is this another home? */
  unsigned :0;
  void    *sua_data;		/**< Data pointer */
} su_alloc_t;

struct su_block_s {
  su_home_t  *sub_parent;	/**< Parent home */
  char       *sub_preload;	/**< Preload area */
  su_home_stat_t *sub_stats;	/**< Statistics.. */
  void      (*sub_destructor)(void *); /**< Destructor function */
  size_t      sub_ref;		/**< Reference count */
#define REF_MAX SIZE_MAX
  size_t      sub_used;		/**< Number of blocks allocated */
  size_t      sub_n;		/**< Size of hash table  */

  unsigned    sub_prsize:16;	/**< Preload size */
  unsigned    sub_prused:16;	/**< Used from preload */
  unsigned    sub_hauto:1;      /**< "Home" is not from malloc */
  unsigned    sub_auto:1;	/**< struct su_block_s is not from malloc */
  unsigned    sub_preauto:1;	/**< Preload is not from malloc */
  unsigned    sub_auto_all:1;	/**< Everything is from stack! */
  unsigned :0;

  su_alloc_t  sub_nodes[SUB_N];	/**< Pointers to data/lower blocks */
};

static void su_home_check_blocks(su_block_t const *b);

static void su_home_stats_alloc(su_block_t *, void *p, void *preload,
				size_t size, int zero);
static void su_home_stats_free(su_block_t *sub, void *p, void *preload,
			       unsigned size);

static void _su_home_deinit(su_home_t *home);

#define SU_ALLOC_STATS 1

#if SU_ALLOC_STATS
size_t count_su_block_find, count_su_block_find_loop;
size_t size_su_block_find, used_su_block_find;
size_t max_size_su_block_find, max_used_su_block_find;
size_t su_block_find_collision, su_block_find_collision_used, 
  su_block_find_collision_size;
#endif

su_inline su_alloc_t *su_block_find(su_block_t const *b, void const *p)
{
  size_t h, h0, probe;

#if SU_ALLOC_STATS  
  size_t collision = 0;

  count_su_block_find++;
  size_su_block_find += b->sub_n;
  used_su_block_find += b->sub_used;
  if (b->sub_n > max_size_su_block_find)
    max_size_su_block_find = b->sub_n;
  if (b->sub_used > max_used_su_block_find)
    max_used_su_block_find = b->sub_used;
#endif

  assert(p != NULL);

  h = h0 = (size_t)((uintptr_t)p % b->sub_n);

  probe = (b->sub_n > SUB_P) ? SUB_P : 1;

  do {
    if (b->sub_nodes[h].sua_data == p) {
      su_alloc_t const *retval = &b->sub_nodes[h];
      return (su_alloc_t *)retval; /* discard const */
    }
    h += probe;
    if (h >= b->sub_n)
      h -= b->sub_n;
#if SU_ALLOC_STATS
    if (++collision > su_block_find_collision)
      su_block_find_collision = collision, 
	su_block_find_collision_used = b->sub_used,
	su_block_find_collision_size = b->sub_n;
    count_su_block_find_loop++;
#endif
  } while (h != h0);

  return NULL;
}

su_inline su_alloc_t *su_block_add(su_block_t *b, void *p)
{
  size_t h, probe;

  assert(p != NULL);

  h = (size_t)((uintptr_t)p % b->sub_n);

  probe = (b->sub_n > SUB_P) ? SUB_P : 1;

  while (b->sub_nodes[h].sua_data) {
    h += probe;
    if (h >= b->sub_n)
      h -= b->sub_n;
  }

  b->sub_used++;
  b->sub_nodes[h].sua_data = p;

  return &b->sub_nodes[h];
}

su_inline int su_is_preloaded(su_block_t const *sub, char *data)
{
  return
    sub->sub_preload && 
    sub->sub_preload <= data && 
    sub->sub_preload + sub->sub_prsize > data;
}

su_inline int su_alloc_check(su_block_t const *sub, su_alloc_t const *sua)
{
#if MEMCHECK_EXTRA
  size_t size, term;
  assert(sua);
  if (sua) {
    size = (size_t)sua->sua_size;
    memcpy(&term, (char *)sua->sua_data + size, sizeof (term));
    assert(size - term == 0);
    return size - term == 0;
  }
  else
    return 0;
#endif
  return sua != NULL;
}

/** Allocate the block hash table.
 *
 * @internal
 *
 * Allocate a block hash table of @a n elements.
 *
 * @param home  pointer to home object
 * @param n     number of buckets in hash table
 *
 * @return
 *   This function returns a pointer to the allocated hash table or
 *   NULL if an error occurred.
 */
su_inline su_block_t *su_hash_alloc(size_t n)
{
  su_block_t *b = calloc(1, offsetof(su_block_t, sub_nodes[n]));

  if (b) {
    /* Implicit su_home_init(); */
    b->sub_ref = 1;
    b->sub_hauto = 1;
    b->sub_n = n;
  }

  return b;
}

enum sub_zero { do_malloc, do_calloc, do_clone };

/** Allocate a memory block.
 *
 * @internal
 *
 * Precondition: locked home
 *
 * @param home home to allocate
 * @param sub  block structure used to allocate
 * @param size
 * @param zero if true, zero allocated block;
 *             if > 1, allocate a subhome
 *
 */
static 
void *sub_alloc(su_home_t *home, 
		su_block_t *sub,
		size_t size,
		enum sub_zero zero)
{
  void *data, *preload = NULL;
  
  assert (size < (((size_t)1) << SIZEBITS));

  if (size >= ((size_t)1) << SIZEBITS)
    return (void)(errno = ENOMEM), NULL;

  if (sub == NULL || 3 * sub->sub_used > 2 * sub->sub_n) {
    /* Resize the hash table */
    size_t i, n, n2, used;
    su_block_t *b2;

    if (sub)
      n = home->suh_blocks->sub_n, n2 = 4 * n + 3, used = sub->sub_used;
    else
      n = 0, n2 = SUB_N, used = 0;

#if 0
    printf("su_alloc(home = %p): realloc block hash of size %d\n", home, n2);
#endif

    if (!(b2 = su_hash_alloc(n2)))
      return NULL;

    for (i = 0; i < n; i++) {
      if (sub->sub_nodes[i].sua_data)
	su_block_add(b2, sub->sub_nodes[i].sua_data)[0] = sub->sub_nodes[i];
    }

    if (sub) {
      b2->sub_parent = sub->sub_parent;
      b2->sub_ref = sub->sub_ref;
      b2->sub_preload = sub->sub_preload;
      b2->sub_prsize = sub->sub_prsize;
      b2->sub_prused = sub->sub_prused;
      b2->sub_hauto = sub->sub_hauto;
      b2->sub_preauto = sub->sub_preauto;
      b2->sub_destructor = sub->sub_destructor;
      /* auto_all is not copied! */
      b2->sub_stats = sub->sub_stats;
    }

    home->suh_blocks = b2;

    if (sub && !sub->sub_auto)
      free(sub);
    sub = b2;
  }

  if (size && sub && zero < do_clone &&
      sub->sub_preload && size <= sub->sub_prsize) {
    /* Use preloaded memory */
    size_t prused = sub->sub_prused + size + MEMCHECK_EXTRA; 
    prused = ALIGN(prused);
    if (prused <= sub->sub_prsize) {
      preload = (char *)sub->sub_preload + sub->sub_prused;
      sub->sub_prused = (unsigned)prused;
    }
  }

  if (preload && zero)
    data = memset(preload, 0, size);
  else if (preload)
    data = preload;
  else if (zero)
    data = calloc(1, size + MEMCHECK_EXTRA);
  else
    data = malloc(size + MEMCHECK_EXTRA);

  if (data) {
    su_alloc_t *sua;

#if MEMCHECK_EXTRA
    size_t term = 0 - size;
    memcpy((char *)data + size, &term, sizeof (term));
#endif

    if (!preload)
      sub->sub_auto_all = 0;

    if (zero >= do_clone) {
      /* Prepare cloned home */ 
      su_home_t *subhome = data;

      assert(preload == 0);

      subhome->suh_blocks = su_hash_alloc(SUB_N);
      if (!subhome->suh_blocks) 
	return (void)safefree(data), NULL;

      subhome->suh_size = (unsigned)size;
      subhome->suh_blocks->sub_parent = home;
      subhome->suh_blocks->sub_hauto = 0;
    }

    /* OK, add the block to the hash table. */

    sua = su_block_add(sub, data); assert(sua);
    sua->sua_size = (unsigned)size;
    sua->sua_home = zero > 1;

    if (sub->sub_stats)
      su_home_stats_alloc(sub, data, preload, size, zero);
  }

  return data;
}

/**Create a new su_home_t object.
 *
 * Create a home object used to collect multiple memory allocations under
 * one handle. The memory allocations made using this home object is freed
 * either when this home is destroyed. 
 *
 * The maximum @a size of a home object is INT_MAX (2 gigabytes).
 *
 * @param size    size of home object
 *
 * The memory home object allocated with su_home_new() can be reclaimed with
 * su_home_unref().
 *
 * @return
 * This function returns a pointer to an su_home_t object, or NULL upon
 * an error.
 */
void *su_home_new(isize_t size)
{
  su_home_t *home;

  assert(size >= sizeof (*home));

  if (size < sizeof (*home))
    return (void)(errno = EINVAL), NULL;
  else if (size > INT_MAX)
    return (void)(errno = ENOMEM), NULL;

  home = calloc(1, size);
  if (home) {
    home->suh_size = (int)size;
    home->suh_blocks = su_hash_alloc(SUB_N);
    if (home->suh_blocks)
      home->suh_blocks->sub_hauto = 0;
    else
      safefree(home), home = NULL;
  }

  return home;
}

/** Create a new reference to a home object. */
void *su_home_ref(su_home_t const *home)
{
  if (home) {
    su_block_t *sub = MEMLOCK(home);

    if (sub == NULL || sub->sub_ref == 0) {
      assert(sub && sub->sub_ref != 0);
      UNLOCK(home);
      return NULL;
    }
    
    if (sub->sub_ref != REF_MAX)