mpool.c

一个关于memory pool 的实例

/*
 * Memory pool routines.
 *
 * Copyright 1996 by Gray Watson.
 *
 * This file is part of the mpool package.
 *
 * Permission to use, copy, modify, and distribute this software for
 * any purpose and without fee is hereby granted, provided that the
 * above copyright notice and this permission notice appear in all
 * copies, and that the name of Gray Watson not be used in advertising
 * or publicity pertaining to distribution of the document or software
 * without specific, written prior permission.
 *
 * Gray Watson makes no representations about the suitability of the
 * software described herein for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * The author may be reached via http://256.com/gray/
 *
 * $Id: mpool.c,v 1.5 2006/05/31 20:28:31 gray Exp $
 */

/*
 * Memory-pool allocation routines.  I got sick of the GNU mmalloc
 * library which was close to what we needed but did not exactly do
 * what I wanted.
 *
 * The following uses mmap from /dev/zero.  It allows a number of
 * allocations to be made inside of a memory pool then with a clear or
 * close the pool can be reset without any memory fragmentation and
 * growth problems.
 */

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>

#ifdef DMALLOC
#include "dmalloc.h"
#endif

#define MPOOL_MAIN

#include "mpool.h"
#include "mpool_loc.h"

#ifdef __GNUC__
#ident "$Id: mpool.c,v 1.5 2006/05/31 20:28:31 gray Exp $"
#else
static char *rcs_id = "$Id: mpool.c,v 1.5 2006/05/31 20:28:31 gray Exp $";
#endif

/* version */
static	char *version = "mpool library version 2.1.0";

/* local variables */
static	int		enabled_b = 0;		/* lib initialized? */
static	unsigned int	min_bit_free_next = 0;	/* min size of next pnt */
static	unsigned int	min_bit_free_size = 0;	/* min size of next + size */
static	unsigned long	bit_array[MAX_BITS + 1]; /* size -> bit */

/****************************** local utilities ******************************/

/*
 * static void startup
 *
 * DESCRIPTION:
 *
 * Perform any library level initialization.
 *
 * RETURNS:
 *
 * None.
 *
 * ARGUMENTS:
 *
 * None.
 */
static	void	startup(void)
{
  int		bit_c;
  unsigned long	size = 1;
  
  if (enabled_b) {
    return;
  }
  
  /* allocate our free bit array list */
  for (bit_c = 0; bit_c <= MAX_BITS; bit_c++) {
    bit_array[bit_c] = size;
    
    /*
     * Note our minimum number of bits that can store a pointer.  This
     * is smallest address that we can have a linked list for.
     */
    if (min_bit_free_next == 0 && size >= sizeof(void *)) {
      min_bit_free_next = bit_c;
    }
    /*
     * Note our minimum number of bits that can store a pointer and
     * the size of the block.
     */
    if (min_bit_free_size == 0 && size >= sizeof(mpool_free_t)) {
      min_bit_free_size = bit_c;
    }
    
    size *= 2;
  }
  
  enabled_b = 1;
}

/*
 * static int size_to_bits
 *
 * DESCRIPTION:
 *
 * Calculate the number of bits in a size.
 *
 * RETURNS:
 *
 * Number of bits.
 *
 * ARGUMENTS:
 *
 * size -> Size of memory of which to calculate the number of bits.
 */
static	int	size_to_bits(const unsigned long size)
{
  int		bit_c = 0;
  
  for (bit_c = 0; bit_c <= MAX_BITS; bit_c++) {
    if (size <= bit_array[bit_c]) {
      break;
    }
  }
  
  return bit_c;
}

/*
 * static int size_to_free_bits
 *
 * DESCRIPTION:
 *
 * Calculate the number of bits in a size going on the free list.
 *
 * RETURNS:
 *
 * Number of bits.
 *
 * ARGUMENTS:
 *
 * size -> Size of memory of which to calculate the number of bits.
 */
static	int	size_to_free_bits(const unsigned long size)
{
  int		bit_c = 0;
  
  if (size == 0) {
    return 0;
  }
  
  for (bit_c = 0; bit_c <= MAX_BITS; bit_c++) {
    if (size < bit_array[bit_c]) {
      break;
    }
  }
  
  return bit_c - 1;
}

/*
 * static int bits_to_size
 *
 * DESCRIPTION:
 *
 * Calculate the size represented by a number of bits.
 *
 * RETURNS:
 *
 * Number of bits.
 *
 * ARGUMENTS:
 *
 * bit_n -> Number of bits
 */
static	unsigned long	bits_to_size(const int bit_n)
{
  if (bit_n > MAX_BITS) {
    return bit_array[MAX_BITS];
  }
  else {
    return bit_array[bit_n];
  }
}

/*
 * static void *alloc_pages
 *
 * DESCRIPTION:
 *
 * Allocate space for a number of memory pages in the memory pool.
 *
 * RETURNS:
 *
 * Success - New pages of memory
 *
 * Failure - NULL
 *
 * ARGUMENTS:
 *
 * mp_p <-> Pointer to our memory pool.
 *
 * page_n -> Number of pages to alloc.
 *
 * error_p <- Pointer to integer which, if not NULL, will be set with
 * a mpool error code.
 */
static	void	*alloc_pages(mpool_t *mp_p, const unsigned int page_n,
			     int *error_p)
{
  void		*mem, *fill_mem;
  unsigned long	size, fill;
  int		state;
  
  /* are we over our max-pages? */
  if (mp_p->mp_max_pages > 0 && mp_p->mp_page_c >= mp_p->mp_max_pages) {
    SET_POINTER(error_p, MPOOL_ERROR_NO_PAGES);
    return NULL;
  }
  
  size = SIZE_OF_PAGES(mp_p, page_n);
  
#ifdef DEBUG
  (void)printf("allocating %u pages or %lu bytes\n", page_n, size);
#endif
  
  if (BIT_IS_SET(mp_p->mp_flags, MPOOL_FLAG_USE_SBRK)) {
    mem = sbrk(size);
    if (mem == (void *)-1) {
      SET_POINTER(error_p, MPOOL_ERROR_NO_MEM);
      return NULL;
    }
    fill = (unsigned long)mem % mp_p->mp_page_size;
    
    if (fill > 0) {
      fill = mp_p->mp_page_size - fill;
      fill_mem = sbrk(fill);
      if (fill_mem == (void *)-1) {
	SET_POINTER(error_p, MPOOL_ERROR_NO_MEM);
	return NULL;
      }
      if ((char *)fill_mem != (char *)mem + size) {
	SET_POINTER(error_p, MPOOL_ERROR_SBRK_CONTIG);
	return NULL;
      }
      mem = (char *)mem + fill;
    }
  }
  else {
    state = MAP_PRIVATE;
#ifdef MAP_FILE
    state |= MAP_FILE;
#endif
#ifdef MAP_VARIABLE
    state |= MAP_VARIABLE;
#endif
    
    /* mmap from /dev/zero */
    mem = mmap((caddr_t)mp_p->mp_addr, size, PROT_READ | PROT_WRITE, state,
	       mp_p->mp_fd, mp_p->mp_top);
    if (mem == (void *)MAP_FAILED) {
      if (errno == ENOMEM) {
	SET_POINTER(error_p, MPOOL_ERROR_NO_MEM);
      }
      else {
	SET_POINTER(error_p, MPOOL_ERROR_MMAP);
      }
      return NULL;
    }
    mp_p->mp_top += size;
    if (mp_p->mp_addr != NULL) {
      mp_p->mp_addr = (char *)mp_p->mp_addr + size;
    }
  }
  
  mp_p->mp_page_c += page_n;
  
  SET_POINTER(error_p, MPOOL_ERROR_NONE);
  return mem;
}

/*
 * static int free_pages
 *
 * DESCRIPTION:
 *
 * Free previously allocated pages of memory.
 *
 * RETURNS:
 *
 * Success - MPOOL_ERROR_NONE
 *
 * Failure - Mpool error code
 *
 * ARGUMENTS:
 *
 * pages <-> Pointer to memory pages that we are freeing.
 *
 * size -> Size of the block that we are freeing.
 *
 * sbrk_b -> Set to one if the pages were allocated with sbrk else mmap.
 */
static	int	free_pages(void *pages, const unsigned long size,
			   const int sbrk_b)
{
  if (! sbrk_b) {
    (void)munmap((caddr_t)pages, size);
  }
  
  return MPOOL_ERROR_NONE;
}

/*
 * static int check_magic
 *
 * DESCRIPTION:
 *
 * Check for the existance of the magic ID in a memory pointer.
 *
 * RETURNS:
 *
 * Success - MPOOL_ERROR_NONE
 *
 * Failure - Mpool error code
 *
 * ARGUMENTS:
 *
 * addr -> Address inside of the block that we are tryign to locate.
 *
 * size -> Size of the block.
 */
static	int	check_magic(const void *addr, const unsigned long size)
{
  const unsigned char	*mem_p;
  
  /* set our starting point */
  mem_p = (unsigned char *)addr + size;
  
  if (*mem_p == FENCE_MAGIC0 && *(mem_p + 1) == FENCE_MAGIC1) {
    return MPOOL_ERROR_NONE;
  }
  else {
    return MPOOL_ERROR_PNT_OVER;
  }
}

/*
 * static void write_magic
 *
 * DESCRIPTION:
 *
 * Write the magic ID to the address.
 *
 * RETURNS:
 *
 * None.
 *
 * ARGUMENTS:
 *
 * addr -> Address where to write the magic.
 */
static	void	write_magic(const void *addr)
{
  *(unsigned char *)addr = FENCE_MAGIC0;
  *((unsigned char *)addr + 1) = FENCE_MAGIC1;
}

/*
 * static void free_pointer
 *
 * DESCRIPTION:
 *
 * Moved a pointer into our free lists.
 *
 * RETURNS:
 *
 * Success - MPOOL_ERROR_NONE
 *
 * Failure - Mpool error code
 *
 * ARGUMENTS:
 *
 * mp_p <-> Pointer to the memory pool.
 *
 * addr <-> Address where to write the magic.  We may write a next
 * pointer to it.
 *
 * size -> Size of the address space.
 */
static	int	free_pointer(mpool_t *mp_p, void *addr,
			     const unsigned long size)
{
  unsigned int	bit_n;
  unsigned long	real_size;
  mpool_free_t	free_pnt;
  
#ifdef DEBUG
  (void)printf("freeing a block at %lx of %lu bytes\n", (long)addr, size);
#endif
  
  if (size == 0) {
    return MPOOL_ERROR_NONE;
  }
  
  /*
   * if the user size is larger then can fit in an entire block then
   * we change the size
   */
  if (size > MAX_BLOCK_USER_MEMORY(mp_p)) {
    real_size = SIZE_OF_PAGES(mp_p, PAGES_IN_SIZE(mp_p, size)) -
      sizeof(mpool_block_t);
  }
  else {
    real_size = size;
  }
  
  /*
   * We use a specific free bits calculation here because if we are
   * freeing 10 bytes then we will be putting it into the 8-byte free
   * list and not the 16 byte list.  size_to_bits(10) will return 4
   * instead of 3.
   */
  bit_n = size_to_free_bits(real_size);
  
  /*
   * Minimal error checking.  We could go all the way through the
   * list however this might be prohibitive.
   */
  if (mp_p->mp_free[bit_n] == addr) {
    return MPOOL_ERROR_IS_FREE;
  }
  
  /* add the freed pointer to the free list */
  if (bit_n < min_bit_free_next) {
    /*
     * Yes we know this will lose 99% of the allocations but what else
     * can we do?  No space for a next pointer.
     */
    if (mp_p->mp_free[bit_n] == NULL) {
      mp_p->mp_free[bit_n] = addr;
    }
  }
  else if (bit_n < min_bit_free_size) {
    /* we copy, not assign, to maintain the free list */
    memcpy(addr, mp_p->mp_free + bit_n, sizeof(void *));
    mp_p->mp_free[bit_n] = addr;
  }
  else {
    
    /* setup our free list structure */
    free_pnt.mf_next_p = mp_p->mp_free[bit_n];
    free_pnt.mf_size = real_size;
    
    /* we copy the structure in since we don't know about alignment */
    memcpy(addr, &free_pnt, sizeof(free_pnt));
    mp_p->mp_free[bit_n] = addr;
  }
  
  return MPOOL_ERROR_NONE;
}

/*
 * static int split_block
 *
 * DESCRIPTION:
 *
 * When freeing space in a multi-block chunk we have to create new
 * blocks out of the upper areas being freed.
 *
 * RETURNS:
 *
 * Success - MPOOL_ERROR_NONE
 *
 * Failure - Mpool error code
 *
 * ARGUMENTS:
 *
 * mp_p <-> Pointer to the memory pool.
 *
 * free_addr -> Address that we are freeing.
 *
 * size -> Size of the space that we are taking from address.
 */
static	int	split_block(mpool_t *mp_p, void *free_addr,
			    const unsigned long size)
{
  mpool_block_t	*block_p, *new_block_p;
  int		ret, page_n;
  void		*end_p;
  
  /*
   * 1st we find the block pointer from our free addr.  At this point
   * the pointer must be the 1st one in the block if it is spans
   * multiple blocks.
   */
  block_p = (mpool_block_t *)((char *)free_addr - sizeof(mpool_block_t));
  if (block_p->mb_magic != BLOCK_MAGIC
      || block_p->mb_magic2 != BLOCK_MAGIC) {
    return MPOOL_ERROR_POOL_OVER;
  }
  
  page_n = PAGES_IN_SIZE(mp_p, size);
  
  /* we are creating a new block structure for the 2nd ... */
  new_block_p = (mpool_block_t *)((char *)block_p +
				  SIZE_OF_PAGES(mp_p, page_n));
  new_block_p->mb_magic = BLOCK_MAGIC;
  /* New bounds is 1st block bounds.  The 1st block's is reset below. */
  new_block_p->mb_bounds_p = block_p->mb_bounds_p;
  /* Continue the linked list.  The 1st block will point to us below. */
  new_block_p->mb_next_p = block_p->mb_next_p;
  new_block_p->mb_magic2 = BLOCK_MAGIC;
  
  /* bounds for the 1st block are reset to the 1st page only */
  block_p->mb_bounds_p = (char *)new_block_p;
  /* the next block pointer for the 1st block is now the new one */
  block_p->mb_next_p = new_block_p;
  
  /* only free the space in the 1st block if it is only 1 block in size */
  if (page_n == 1) {
    /* now free the rest of the 1st block block */
    end_p = (char *)free_addr + size;
    ret = free_pointer(mp_p, end_p,
		       (char *)block_p->mb_bounds_p - (char *)end_p);
    if (ret != MPOOL_ERROR_NONE) {
      return ret;
    }
  }
  
  /* now free the rest of the block */
  ret = free_pointer(mp_p, FIRST_ADDR_IN_BLOCK(new_block_p),
		     MEMORY_IN_BLOCK(new_block_p));
  if (ret != MPOOL_ERROR_NONE) {
    return ret;
  }
  
  return MPOOL_ERROR_NONE;
}

/*
 * static void *get_space
 *
 * DESCRIPTION:
 *
 * Moved a pointer into our free lists.
 *
 * RETURNS:
 *
 * Success - New address that we can use.
 *
 * Failure - NULL
 *
 * ARGUMENTS:
 *
 * mp_p <-> Pointer to the memory pool.
 *
 * byte_size -> Size of the address space that we need.
 *
 * error_p <- Pointer to integer which, if not NULL, will be set with
 * a mpool error code.
 */
static	void	*get_space(mpool_t *mp_p, const unsigned long byte_size,
			   int *error_p)
{
  mpool_block_t	*block_p;
  mpool_free_t	free_pnt;
  int		ret;
  unsigned long	size;
  unsigned int	bit_c, page_n, left;
  void		*free_addr = NULL, *free_end;
  
  size = byte_size;
  while ((size & (sizeof(void *) - 1)) > 0) {