[irc/rqf/shadowircd.git] / libratbox / src / balloc.c

/*
 *  ircd-ratbox: A slightly useful ircd.
 *  balloc.c: A block allocator.
 *
 * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
 * Copyright (C) 1996-2002 Hybrid Development Team
 * Copyright (C) 2002-2006 ircd-ratbox development team
 *
 *  Below are the orignal headers from the old blalloc.c 
 *
 *  File:   blalloc.c
 *  Owner:  Wohali (Joan Touzet)
 *  
 *  Modified 2001/11/29 for mmap() support by Aaron Sethman <androsyn@ratbox.org>
 *
 *  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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
 *  USA
 *
 *  $Id: balloc.c 26100 2008-09-20 01:27:19Z androsyn $
 */

/* 
 * About the block allocator
 *
 * Basically we have three ways of getting memory off of the operating
 * system. Below are this list of methods and the order of preference.
 *
 * 1. mmap() anonymous pages with the MMAP_ANON flag.
 * 2. mmap() via the /dev/zero trick.
 * 3. HeapCreate/HeapAlloc (on win32) 
 * 4. malloc() 
 *
 * The advantages of 1 and 2 are this.  We can munmap() the pages which will
 * return the pages back to the operating system, thus reducing the size 
 * of the process as the memory is unused.  malloc() on many systems just keeps
 * a heap of memory to itself, which never gets given back to the OS, except on
 * exit.  This of course is bad, if say we have an event that causes us to allocate
 * say, 200MB of memory, while our normal memory consumption would be 15MB.  In the
 * malloc() case, the amount of memory allocated to our process never goes down, as
 * malloc() has it locked up in its heap.  With the mmap() method, we can munmap()
 * the block and return it back to the OS, thus causing our memory consumption to go
 * down after we no longer need it.
 * 
 *
 *
 */
#include <libratbox_config.h>
#include <ratbox_lib.h>

#ifndef NOBALLOC
#ifdef HAVE_MMAP		/* We've got mmap() that is good */
#include <sys/mman.h>
/* HP-UX sucks */
#ifdef MAP_ANONYMOUS
#ifndef MAP_ANON
#define MAP_ANON MAP_ANONYMOUS
#endif
#endif
#endif
#endif

static uintptr_t offset_pad;

/* status information for an allocated block in heap */
struct rb_heap_block
{
	size_t alloc_size;
	rb_dlink_node node;
	unsigned long free_count;
	void *elems;		/* Points to allocated memory */
};
typedef struct rb_heap_block rb_heap_block;

/* information for the root node of the heap */
struct rb_bh
{
	rb_dlink_node hlist;
	size_t elemSize;	/* Size of each element to be stored */
	unsigned long elemsPerBlock;	/* Number of elements per block */
	rb_dlink_list block_list;
	rb_dlink_list free_list;
	char *desc;
};

#ifndef NOBALLOC
static int newblock(rb_bh *bh);
static void rb_bh_gc_event(void *unused);
#endif /* !NOBALLOC */
static rb_dlink_list *heap_lists;

#if defined(WIN32)
static HANDLE block_heap;
#endif

#define rb_bh_fail(x) _rb_bh_fail(x, __FILE__, __LINE__)

static void
_rb_bh_fail(const char *reason, const char *file, int line)
{
	rb_lib_log("rb_heap_blockheap failure: %s (%s:%d)", reason, file, line);
	abort();
}

#ifndef NOBALLOC
/*
 * static inline void free_block(void *ptr, size_t size)
 *
 * Inputs: The block and its size
 * Output: None
 * Side Effects: Returns memory for the block back to the OS
 */
static inline void
free_block(void *ptr, size_t size)
{
#ifdef HAVE_MMAP
	munmap(ptr, size);
#else
#ifdef _WIN32
	HeapFree(block_heap, 0, ptr);
#else
	free(ptr);
#endif
#endif
}
#endif /* !NOBALLOC */

/*
 * void rb_init_bh(void)
 * 
 * Inputs: None
 * Outputs: None
 * Side Effects: Initializes the block heap
 */

void
rb_init_bh(void)
{
	heap_lists = rb_malloc(sizeof(rb_dlink_list));
	offset_pad = sizeof(void *);
	/* XXX if you get SIGBUS when trying to use a long long..here is where you need to
	 * fix your shit
	 */
#ifdef __sparc__
	if((offset_pad % __alignof__(long long)) != 0)
	{
		offset_pad += __alignof__(long long);
		offset_pad &= ~(__alignof__(long long) - 1);
	}
#endif

#ifndef NOBALLOC
#ifdef _WIN32
	block_heap = HeapCreate(HEAP_NO_SERIALIZE, 0, 0);
#endif
	rb_event_addish("rb_bh_gc_event", rb_bh_gc_event, NULL, 300);
#endif /* !NOBALLOC */
}

#ifndef NOBALLOC
/*
 * static inline void *get_block(size_t size)
 * 
 * Input: Size of block to allocate
 * Output: Pointer to new block
 * Side Effects: None
 */
static inline void *
get_block(size_t size)
{
	void *ptr;
#ifdef HAVE_MMAP
#ifdef MAP_ANON
	ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
#else
	int zero_fd;
	zero_fd = open("/dev/zero", O_RDWR);
	if(zero_fd < 0)
		rb_bh_fail("Failed opening /dev/zero");
	ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, zero_fd, 0);
	close(zero_fd);
#endif /* MAP_ANON */
	if(ptr == MAP_FAILED)
		ptr = NULL;
#else
#ifdef _WIN32
	ptr = HeapAlloc(block_heap, 0, size);
#else
	ptr = malloc(size);
#endif
#endif
	return (ptr);
}


static void
rb_bh_gc_event(void *unused)
{
	rb_dlink_node *ptr;
	RB_DLINK_FOREACH(ptr, heap_lists->head)
	{
		rb_bh_gc(ptr->data);
	}
}

/* ************************************************************************ */
/* FUNCTION DOCUMENTATION:                                                  */
/*    newblock                                                              */
/* Description:                                                             */
/*    Allocates a new block for addition to a blockheap                     */
/* Parameters:                                                              */
/*    bh (IN): Pointer to parent blockheap.                                 */
/* Returns:                                                                 */
/*    0 if successful, 1 if not                                             */
/* ************************************************************************ */

static int
newblock(rb_bh *bh)
{
	rb_heap_block *b;
	unsigned long i;
	uintptr_t offset;
	rb_dlink_node *node;
	/* Setup the initial data structure. */
	b = rb_malloc(sizeof(rb_heap_block));

	b->alloc_size = bh->elemsPerBlock * bh->elemSize;

	b->elems = get_block(b->alloc_size);
	if(rb_unlikely(b->elems == NULL))
	{
		return (1);
	}
	offset = (uintptr_t)b->elems;
	/* Setup our blocks now */
	for(i = 0; i < bh->elemsPerBlock; i++, offset += bh->elemSize)
	{
		*((void **)offset) = b;
		node = (void *)(offset + offset_pad);
		rb_dlinkAdd((void *)offset, node, &bh->free_list);
	}
	rb_dlinkAdd(b, &b->node, &bh->block_list);
	b->free_count = bh->elemsPerBlock;
	return (0);
}
#endif /* !NOBALLOC */

/* ************************************************************************ */
/* FUNCTION DOCUMENTATION:                                                  */
/*    rb_bh_create                                                       */
/* Description:                                                             */
/*   Creates a new blockheap from which smaller blocks can be allocated.    */
/*   Intended to be used instead of multiple calls to malloc() when         */
/*   performance is an issue.                                               */
/* Parameters:                                                              */
/*   elemsize (IN):  Size of the basic element to be stored                 */
/*   elemsperblock (IN):  Number of elements to be stored in a single block */
/*         of memory.  When the blockheap runs out of free memory, it will  */
/*         allocate elemsize * elemsperblock more.                          */
/* Returns:                                                                 */
/*   Pointer to new rb_bh, or NULL if unsuccessful                      */
/* ************************************************************************ */
rb_bh *
rb_bh_create(size_t elemsize, int elemsperblock, const char *desc)
{
	rb_bh *bh;
	lrb_assert(elemsize > 0 && elemsperblock > 0);
	lrb_assert(elemsize >= sizeof(rb_dlink_node));

	/* Catch idiotic requests up front */
	if((elemsize == 0) || (elemsperblock <= 0))
	{
		rb_bh_fail("Attempting to rb_bh_create idiotic sizes");
	}

	if(elemsize < sizeof(rb_dlink_node))
		rb_bh_fail("Attempt to rb_bh_create smaller than sizeof(rb_dlink_node)");

	/* Allocate our new rb_bh */
	bh = rb_malloc(sizeof(rb_bh));
#ifndef NOBALLOC
	elemsize += offset_pad;
	if((elemsize % sizeof(void *)) != 0)
	{
		/* Pad to even pointer boundary */
		elemsize += sizeof(void *);
		elemsize &= ~(sizeof(void *) - 1);
	}
#endif

	bh->elemSize = elemsize;
	bh->elemsPerBlock = elemsperblock;
	if(desc != NULL)
		bh->desc = rb_strdup(desc);

#ifndef NOBALLOC
	/* Be sure our malloc was successful */
	if(newblock(bh))
	{
		if(bh != NULL)
			free(bh);
		rb_lib_log("newblock() failed");
		rb_outofmemory();	/* die.. out of memory */
	}
#endif /* !NOBALLOC */

	if(bh == NULL)
	{
		rb_bh_fail("bh == NULL when it shouldn't be");
	}
	rb_dlinkAdd(bh, &bh->hlist, heap_lists);
	return (bh);
}

/* ************************************************************************ */
/* FUNCTION DOCUMENTATION:                                                  */
/*    rb_bh_alloc                                                        */
/* Description:                                                             */
/*    Returns a pointer to a struct within our rb_bh that's free for    */
/*    the taking.                                                           */
/* Parameters:                                                              */
/*    bh (IN):  Pointer to the Blockheap.                                   */
/* Returns:                                                                 */
/*    Pointer to a structure (void *), or NULL if unsuccessful.             */
/* ************************************************************************ */

void *
rb_bh_alloc(rb_bh *bh)
{
#ifndef NOBALLOC
	rb_dlink_node *new_node;
	rb_heap_block **block;
	void *ptr;
#endif
	lrb_assert(bh != NULL);
	if(rb_unlikely(bh == NULL))
	{
		rb_bh_fail("Cannot allocate if bh == NULL");
	}

#ifdef NOBALLOC
	return (rb_malloc(bh->elemSize));
#else
	if(bh->free_list.head == NULL)
	{
		/* Allocate new block and assign */
		/* newblock returns 1 if unsuccessful, 0 if not */

		if(rb_unlikely(newblock(bh)))
		{
			rb_lib_log("newblock() failed");
			rb_outofmemory();	/* Well that didn't work either...bail */
		}
		if(bh->free_list.head == NULL)
		{
			rb_lib_log("out of memory after newblock()...");
			rb_outofmemory();
		}
	}

	new_node = bh->free_list.head;
	block = (rb_heap_block **) new_node->data;
	ptr = (void *)((uintptr_t)new_node->data + (uintptr_t)offset_pad);
	rb_dlinkDelete(new_node, &bh->free_list);
	(*block)->free_count--;
	memset(ptr, 0, bh->elemSize - offset_pad);
	return (ptr);
#endif
}


/* ************************************************************************ */
/* FUNCTION DOCUMENTATION:                                                  */
/*    rb_bh_free                                                          */
/* Description:                                                             */
/*    Returns an element to the free pool, does not free()                  */
/* Parameters:                                                              */
/*    bh (IN): Pointer to rb_bh containing element                        */
/*    ptr (in):  Pointer to element to be "freed"                           */
/* Returns:                                                                 */
/*    0 if successful, 1 if element not contained within rb_bh.           */
/* ************************************************************************ */
int
rb_bh_free(rb_bh *bh, void *ptr)
{
#ifndef NOBALLOC
	rb_heap_block *block;
	void *data;
#endif
	lrb_assert(bh != NULL);
	lrb_assert(ptr != NULL);

	if(rb_unlikely(bh == NULL))
	{
		rb_lib_log("balloc.c:rb_bhFree() bh == NULL");
		return (1);
	}

	if(rb_unlikely(ptr == NULL))
	{
		rb_lib_log("balloc.rb_bhFree() ptr == NULL");
		return (1);
	}

#ifdef NOBALLOC
	rb_free(ptr);
#else
	data = (void *)((uintptr_t)ptr - (uintptr_t)offset_pad);
	block = *(rb_heap_block **) data;
	/* XXX */
	if(rb_unlikely
	   (!((uintptr_t)ptr >= (uintptr_t)block->elems
	      && (uintptr_t)ptr < (uintptr_t)block->elems + (uintptr_t)block->alloc_size)))
	{
		rb_bh_fail("rb_bh_free() bogus pointer");
	}
	block->free_count++;

	rb_dlinkAdd(data, (rb_dlink_node *)ptr, &bh->free_list);
#endif /* !NOBALLOC */
	return (0);
}


/* ************************************************************************ */
/* FUNCTION DOCUMENTATION:                                                  */
/*    rb_bhDestroy                                                      */
/* Description:                                                             */
/*    Completely free()s a rb_bh.  Use for cleanup.                     */
/* Parameters:                                                              */
/*    bh (IN):  Pointer to the rb_bh to be destroyed.                   */
/* Returns:                                                                 */
/*   0 if successful, 1 if bh == NULL                                       */
/* ************************************************************************ */
int
rb_bh_destroy(rb_bh *bh)
{
#ifndef NOBALLOC
	rb_dlink_node *ptr, *next;
	rb_heap_block *b;
#endif
	if(bh == NULL)
		return (1);

#ifndef NOBALLOC
	RB_DLINK_FOREACH_SAFE(ptr, next, bh->block_list.head)
	{
		b = ptr->data;
		free_block(b->elems, b->alloc_size);
		rb_free(b);
	}
#endif /* !NOBALLOC */

	rb_dlinkDelete(&bh->hlist, heap_lists);
	rb_free(bh->desc);
	rb_free(bh);

	return (0);
}

void
rb_bh_usage(rb_bh *bh, size_t *bused, size_t *bfree, size_t *bmemusage, const char **desc)
{
#ifndef NOBALLOC
	size_t used, freem, memusage;

	if(bh == NULL)
	{
		return;
	}

	freem = rb_dlink_list_length(&bh->free_list);
	used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
	memusage = used * bh->elemSize;
	if(bused != NULL)
		*bused = used;
	if(bfree != NULL)
		*bfree = freem;
	if(bmemusage != NULL)
		*bmemusage = memusage;
	if(desc != NULL)
		*desc = bh->desc;
#else
	static char *noballoc = "no blockheap";
	*bused = 0;
	*bfree = 0;
	*bmemusage = 0;
	*desc = noballoc;
#endif
}

void
rb_bh_usage_all(rb_bh_usage_cb *cb, void *data)
{
	rb_dlink_node *ptr;
	rb_bh *bh;
	size_t used, freem, memusage, heapalloc;
	static const char *unnamed = "(unnamed_heap)";
	const char *desc = unnamed;

	if(cb == NULL)
		return;

	RB_DLINK_FOREACH(ptr, heap_lists->head)
	{
		bh = (rb_bh *)ptr->data;
		freem = rb_dlink_list_length(&bh->free_list);
		used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
		memusage = used * bh->elemSize;
		heapalloc = (freem + used) * bh->elemSize;
		if(bh->desc != NULL)
			desc = bh->desc;
		cb(used, freem, memusage, heapalloc, desc, data);
	}
	return;
}

void
rb_bh_total_usage(size_t *total_alloc, size_t *total_used)
{
	rb_dlink_node *ptr;
	size_t total_memory = 0, used_memory = 0, used, freem;
	rb_bh *bh;

	RB_DLINK_FOREACH(ptr, heap_lists->head)
	{
		bh = (rb_bh *)ptr->data;
		freem = rb_dlink_list_length(&bh->free_list);
		used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
		used_memory += used * bh->elemSize;
		total_memory += (freem + used) * bh->elemSize;
	}

	if(total_alloc != NULL)
		*total_alloc = total_memory;
	if(total_used != NULL)
		*total_used = used_memory;
}

#ifndef NOBALLOC
int
rb_bh_gc(rb_bh *bh)
{
	rb_heap_block *b;
	rb_dlink_node *ptr, *next;
	unsigned long i;
	uintptr_t offset;

	if(bh == NULL)
	{
		/* somebody is smoking some craq..(probably lee, but don't tell him that) */
		return (1);
	}

	if((rb_dlink_list_length(&bh->free_list) < bh->elemsPerBlock)
	   || rb_dlink_list_length(&bh->block_list) == 1)
	{
		/* There couldn't possibly be an entire free block.  Return. */
		return (0);
	}

	RB_DLINK_FOREACH_SAFE(ptr, next, bh->block_list.head)
	{
		b = ptr->data;
		if(rb_dlink_list_length(&bh->block_list) == 1)
			return (0);

		if(b->free_count == bh->elemsPerBlock)
		{
			/* i'm seriously going to hell for this.. */

			offset = (uintptr_t)b->elems;
			for(i = 0; i < bh->elemsPerBlock; i++, offset += (uintptr_t)bh->elemSize)
			{
				rb_dlinkDelete((rb_dlink_node *)(offset + offset_pad),
					       &bh->free_list);
			}
			rb_dlinkDelete(&b->node, &bh->block_list);
			free_block(b->elems, b->alloc_size);
			rb_free(b);
		}

	}
	return (0);
}
#endif /* !NOBALLOC */
Commit	Line	Data
b57f37fb WP	1	/*
	2	* ircd-ratbox: A slightly useful ircd.
	3	* balloc.c: A block allocator.
	4	*
	5	* Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
	6	* Copyright (C) 1996-2002 Hybrid Development Team
	7	* Copyright (C) 2002-2006 ircd-ratbox development team
	8	*
	9	* Below are the orignal headers from the old blalloc.c
	10	*
	11	* File: blalloc.c
	12	* Owner: Wohali (Joan Touzet)
	13	*
	14	* Modified 2001/11/29 for mmap() support by Aaron Sethman <androsyn@ratbox.org>
	15	*
	16	* This program is free software; you can redistribute it and/or modify
	17	* it under the terms of the GNU General Public License as published by
	18	* the Free Software Foundation; either version 2 of the License, or
	19	* (at your option) any later version.
	20	*
	21	* This program is distributed in the hope that it will be useful,
	22	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	23	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	24	* GNU General Public License for more details.
	25	*
	26	* You should have received a copy of the GNU General Public License
	27	* along with this program; if not, write to the Free Software
	28	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
	29	* USA
	30	*
94b4fbf9	31	* $Id: balloc.c 26100 2008-09-20 01:27:19Z androsyn $
b57f37fb WP	32	*/
	33
	34	/*
	35	* About the block allocator
	36	*
	37	* Basically we have three ways of getting memory off of the operating
	38	* system. Below are this list of methods and the order of preference.
	39	*
	40	* 1. mmap() anonymous pages with the MMAP_ANON flag.
	41	* 2. mmap() via the /dev/zero trick.
	42	* 3. HeapCreate/HeapAlloc (on win32)
	43	* 4. malloc()
	44	*
	45	* The advantages of 1 and 2 are this. We can munmap() the pages which will
	46	* return the pages back to the operating system, thus reducing the size
	47	* of the process as the memory is unused. malloc() on many systems just keeps
	48	* a heap of memory to itself, which never gets given back to the OS, except on
	49	* exit. This of course is bad, if say we have an event that causes us to allocate
	50	* say, 200MB of memory, while our normal memory consumption would be 15MB. In the
	51	* malloc() case, the amount of memory allocated to our process never goes down, as
	52	* malloc() has it locked up in its heap. With the mmap() method, we can munmap()
	53	* the block and return it back to the OS, thus causing our memory consumption to go
	54	* down after we no longer need it.
	55	*
	56	*
	57	*
	58	*/
	59	#include <libratbox_config.h>
	60	#include <ratbox_lib.h>
	61
94b4fbf9	62	#ifndef NOBALLOC
b57f37fb WP	63	#ifdef HAVE_MMAP /* We've got mmap() that is good */
	64	#include <sys/mman.h>
	65	/* HP-UX sucks */
	66	#ifdef MAP_ANONYMOUS
	67	#ifndef MAP_ANON
	68	#define MAP_ANON MAP_ANONYMOUS
	69	#endif
	70	#endif
	71	#endif
94b4fbf9	72	#endif
b57f37fb	73
670f0c24 VY	74	static uintptr_t offset_pad;
670f0c24 VY	75
b57f37fb WP	76	/* status information for an allocated block in heap */
	77	struct rb_heap_block
	78	{
	79	size_t alloc_size;
	80	rb_dlink_node node;
	81	unsigned long free_count;
	82	void elems; / Points to allocated memory */
	83	};
	84	typedef struct rb_heap_block rb_heap_block;
	85
b57f37fb WP	86	/* information for the root node of the heap */
	87	struct rb_bh
	88	{
	89	rb_dlink_node hlist;
	90	size_t elemSize; /* Size of each element to be stored */
	91	unsigned long elemsPerBlock; /* Number of elements per block */
	92	rb_dlink_list block_list;
	93	rb_dlink_list free_list;
	94	char *desc;
	95	};
	96
	97	#ifndef NOBALLOC
94b4fbf9	98	static int newblock(rb_bh *bh);
b57f37fb WP	99	static void rb_bh_gc_event(void *unused);
	100	#endif /* !NOBALLOC */
	101	static rb_dlink_list *heap_lists;
	102
	103	#if defined(WIN32)
	104	static HANDLE block_heap;
	105	#endif
	106
	107	#define rb_bh_fail(x) _rb_bh_fail(x, __FILE__, __LINE__)
	108
	109	static void
	110	_rb_bh_fail(const char reason, const char file, int line)
	111	{
	112	rb_lib_log("rb_heap_blockheap failure: %s (%s:%d)", reason, file, line);
	113	abort();
	114	}
94b4fbf9	115
b57f37fb WP	116	#ifndef NOBALLOC
	117	/*
	118	* static inline void free_block(void *ptr, size_t size)
	119	*
	120	* Inputs: The block and its size
	121	* Output: None
	122	* Side Effects: Returns memory for the block back to the OS
	123	*/
	124	static inline void
	125	free_block(void *ptr, size_t size)
	126	{
	127	#ifdef HAVE_MMAP
	128	munmap(ptr, size);
	129	#else
94b4fbf9	130	#ifdef _WIN32
b57f37fb WP	131	HeapFree(block_heap, 0, ptr);
	132	#else
	133	free(ptr);
	134	#endif
	135	#endif
	136	}
	137	#endif /* !NOBALLOC */
	138
	139	/*
	140	* void rb_init_bh(void)
	141	*
	142	* Inputs: None
	143	* Outputs: None
	144	* Side Effects: Initializes the block heap
	145	*/
	146
	147	void
	148	rb_init_bh(void)
	149	{
	150	heap_lists = rb_malloc(sizeof(rb_dlink_list));
670f0c24 VY	151	offset_pad = sizeof(void *);
	152	/* XXX if you get SIGBUS when trying to use a long long..here is where you need to
	153	* fix your shit
	154	*/
	155	#ifdef __sparc__
	156	if((offset_pad % __alignof__(long long)) != 0)
	157	{
	158	offset_pad += __alignof__(long long);
	159	offset_pad &= ~(__alignof__(long long) - 1);
	160	}
94b4fbf9 VY	161	#endif
94b4fbf9 VY	162
b57f37fb	163	#ifndef NOBALLOC
94b4fbf9 VY	164	#ifdef _WIN32
94b4fbf9 VY	165	block_heap = HeapCreate(HEAP_NO_SERIALIZE, 0, 0);
b57f37fb WP	166	#endif
	167	rb_event_addish("rb_bh_gc_event", rb_bh_gc_event, NULL, 300);
	168	#endif /* !NOBALLOC */
	169	}
	170
	171	#ifndef NOBALLOC
	172	/*
	173	* static inline void *get_block(size_t size)
	174	*
	175	* Input: Size of block to allocate
	176	* Output: Pointer to new block
	177	* Side Effects: None
	178	*/
	179	static inline void *
	180	get_block(size_t size)
	181	{
	182	void *ptr;
	183	#ifdef HAVE_MMAP
	184	#ifdef MAP_ANON
	185	ptr = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE \| MAP_ANON, -1, 0);
	186	#else
	187	int zero_fd;
	188	zero_fd = open("/dev/zero", O_RDWR);
	189	if(zero_fd < 0)
	190	rb_bh_fail("Failed opening /dev/zero");
	191	ptr = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE, zero_fd, 0);
	192	close(zero_fd);
	193	#endif /* MAP_ANON */
	194	if(ptr == MAP_FAILED)
94b4fbf9	195	ptr = NULL;
b57f37fb	196	#else
94b4fbf9	197	#ifdef _WIN32
b57f37fb	198	ptr = HeapAlloc(block_heap, 0, size);
94b4fbf9	199	#else
b57f37fb WP	200	ptr = malloc(size);
	201	#endif
	202	#endif
94b4fbf9	203	return (ptr);
b57f37fb WP	204	}
	205
	206
	207	static void
	208	rb_bh_gc_event(void *unused)
	209	{
	210	rb_dlink_node *ptr;
	211	RB_DLINK_FOREACH(ptr, heap_lists->head)
	212	{
	213	rb_bh_gc(ptr->data);
	214	}
	215	}
	216
	217	/* ************************************************************************ */
	218	/* FUNCTION DOCUMENTATION: */
	219	/* newblock */
	220	/* Description: */
	221	/* Allocates a new block for addition to a blockheap */
	222	/* Parameters: */
	223	/* bh (IN): Pointer to parent blockheap. */
	224	/* Returns: */
	225	/* 0 if successful, 1 if not */
	226	/* ************************************************************************ */
	227
	228	static int
94b4fbf9	229	newblock(rb_bh *bh)
b57f37fb WP	230	{
	231	rb_heap_block *b;
	232	unsigned long i;
4414eb3c	233	uintptr_t offset;
670f0c24	234	rb_dlink_node *node;
b57f37fb WP	235	/* Setup the initial data structure. */
	236	b = rb_malloc(sizeof(rb_heap_block));
	237
670f0c24	238	b->alloc_size = bh->elemsPerBlock * bh->elemSize;
b57f37fb WP	239
b57f37fb WP	240	b->elems = get_block(b->alloc_size);
033be687	241	if(rb_unlikely(b->elems == NULL))
b57f37fb WP	242	{
	243	return (1);
	244	}
4414eb3c	245	offset = (uintptr_t)b->elems;
b57f37fb	246	/* Setup our blocks now */
94b4fbf9	247	for(i = 0; i < bh->elemsPerBlock; i++, offset += bh->elemSize)
b57f37fb	248	{
670f0c24 VY	249	((void *)offset) = b;
	250	node = (void *)(offset + offset_pad);
	251	rb_dlinkAdd((void *)offset, node, &bh->free_list);
b57f37fb WP	252	}
b57f37fb WP	253	rb_dlinkAdd(b, &b->node, &bh->block_list);
94b4fbf9	254	b->free_count = bh->elemsPerBlock;
b57f37fb WP	255	return (0);
	256	}
	257	#endif /* !NOBALLOC */
	258
	259	/* ************************************************************************ */
	260	/* FUNCTION DOCUMENTATION: */
	261	/* rb_bh_create */
	262	/* Description: */
	263	/* Creates a new blockheap from which smaller blocks can be allocated. */
	264	/* Intended to be used instead of multiple calls to malloc() when */
	265	/* performance is an issue. */
	266	/* Parameters: */
	267	/* elemsize (IN): Size of the basic element to be stored */
	268	/* elemsperblock (IN): Number of elements to be stored in a single block */
	269	/* of memory. When the blockheap runs out of free memory, it will */
	270	/* allocate elemsize * elemsperblock more. */
	271	/* Returns: */
	272	/* Pointer to new rb_bh, or NULL if unsuccessful */
	273	/* ************************************************************************ */
	274	rb_bh *
	275	rb_bh_create(size_t elemsize, int elemsperblock, const char *desc)
	276	{
	277	rb_bh *bh;
	278	lrb_assert(elemsize > 0 && elemsperblock > 0);
	279	lrb_assert(elemsize >= sizeof(rb_dlink_node));
670f0c24	280
b57f37fb	281	/* Catch idiotic requests up front */
033be687	282	if((elemsize == 0) \|\| (elemsperblock <= 0))
b57f37fb WP	283	{
	284	rb_bh_fail("Attempting to rb_bh_create idiotic sizes");
	285	}
94b4fbf9	286
b57f37fb WP	287	if(elemsize < sizeof(rb_dlink_node))
b57f37fb WP	288	rb_bh_fail("Attempt to rb_bh_create smaller than sizeof(rb_dlink_node)");
94b4fbf9	289
b57f37fb WP	290	/* Allocate our new rb_bh */
b57f37fb WP	291	bh = rb_malloc(sizeof(rb_bh));
b57f37fb	292	#ifndef NOBALLOC
670f0c24	293	elemsize += offset_pad;
b57f37fb WP	294	if((elemsize % sizeof(void *)) != 0)
	295	{
	296	/* Pad to even pointer boundary */
	297	elemsize += sizeof(void *);
	298	elemsize &= ~(sizeof(void *) - 1);
	299	}
670f0c24	300	#endif
b57f37fb WP	301
	302	bh->elemSize = elemsize;
	303	bh->elemsPerBlock = elemsperblock;
	304	if(desc != NULL)
	305	bh->desc = rb_strdup(desc);
	306
	307	#ifndef NOBALLOC
	308	/* Be sure our malloc was successful */
	309	if(newblock(bh))
	310	{
	311	if(bh != NULL)
	312	free(bh);
	313	rb_lib_log("newblock() failed");
	314	rb_outofmemory(); /* die.. out of memory */
	315	}
	316	#endif /* !NOBALLOC */
	317
	318	if(bh == NULL)
	319	{
	320	rb_bh_fail("bh == NULL when it shouldn't be");
	321	}
	322	rb_dlinkAdd(bh, &bh->hlist, heap_lists);
	323	return (bh);
	324	}
	325
	326	/* ************************************************************************ */
	327	/* FUNCTION DOCUMENTATION: */
	328	/* rb_bh_alloc */
	329	/* Description: */
	330	/* Returns a pointer to a struct within our rb_bh that's free for */
	331	/* the taking. */
	332	/* Parameters: */
	333	/* bh (IN): Pointer to the Blockheap. */
	334	/* Returns: */
	335	/* Pointer to a structure (void ), or NULL if unsuccessful. /
	336	/* ************************************************************************ */
	337
	338	void *
94b4fbf9	339	rb_bh_alloc(rb_bh *bh)
b57f37fb WP	340	{
	341	#ifndef NOBALLOC
	342	rb_dlink_node *new_node;
94b4fbf9	343	rb_heap_block **block;
670f0c24	344	void *ptr;
94b4fbf9	345	#endif
b57f37fb	346	lrb_assert(bh != NULL);
033be687	347	if(rb_unlikely(bh == NULL))
b57f37fb WP	348	{
	349	rb_bh_fail("Cannot allocate if bh == NULL");
	350	}
	351
	352	#ifdef NOBALLOC
94b4fbf9	353	return (rb_malloc(bh->elemSize));
b57f37fb WP	354	#else
	355	if(bh->free_list.head == NULL)
	356	{
	357	/* Allocate new block and assign */
	358	/* newblock returns 1 if unsuccessful, 0 if not */
	359
033be687	360	if(rb_unlikely(newblock(bh)))
b57f37fb WP	361	{
	362	rb_lib_log("newblock() failed");
	363	rb_outofmemory(); /* Well that didn't work either...bail */
	364	}
	365	if(bh->free_list.head == NULL)
	366	{
	367	rb_lib_log("out of memory after newblock()...");
	368	rb_outofmemory();
	369	}
	370	}
	371
	372	new_node = bh->free_list.head;
94b4fbf9 VY	373	block = (rb_heap_block **) new_node->data;
94b4fbf9 VY	374	ptr = (void *)((uintptr_t)new_node->data + (uintptr_t)offset_pad);
b57f37fb	375	rb_dlinkDelete(new_node, &bh->free_list);
94b4fbf9	376	(*block)->free_count--;
670f0c24	377	memset(ptr, 0, bh->elemSize - offset_pad);
94b4fbf9	378	return (ptr);
b57f37fb WP	379	#endif
	380	}
	381
	382
	383	/* ************************************************************************ */
	384	/* FUNCTION DOCUMENTATION: */
	385	/* rb_bh_free */
	386	/* Description: */
	387	/* Returns an element to the free pool, does not free() */
	388	/* Parameters: */
	389	/* bh (IN): Pointer to rb_bh containing element */
	390	/* ptr (in): Pointer to element to be "freed" */
	391	/* Returns: */
	392	/* 0 if successful, 1 if element not contained within rb_bh. */
	393	/* ************************************************************************ */
	394	int
94b4fbf9	395	rb_bh_free(rb_bh bh, void ptr)
b57f37fb WP	396	{
b57f37fb WP	397	#ifndef NOBALLOC
670f0c24 VY	398	rb_heap_block *block;
670f0c24 VY	399	void *data;
b57f37fb WP	400	#endif
	401	lrb_assert(bh != NULL);
	402	lrb_assert(ptr != NULL);
	403
033be687	404	if(rb_unlikely(bh == NULL))
b57f37fb	405	{
033be687	406	rb_lib_log("balloc.c:rb_bhFree() bh == NULL");
b57f37fb WP	407	return (1);
	408	}
	409
033be687	410	if(rb_unlikely(ptr == NULL))
b57f37fb	411	{
033be687	412	rb_lib_log("balloc.rb_bhFree() ptr == NULL");
b57f37fb WP	413	return (1);
	414	}
	415
	416	#ifdef NOBALLOC
	417	rb_free(ptr);
	418	#else
94b4fbf9 VY	419	data = (void *)((uintptr_t)ptr - (uintptr_t)offset_pad);
94b4fbf9 VY	420	block = (rb_heap_block *) data;
b57f37fb	421	/* XXX */
94b4fbf9 VY	422	if(rb_unlikely
	423	(!((uintptr_t)ptr >= (uintptr_t)block->elems
	424	&& (uintptr_t)ptr < (uintptr_t)block->elems + (uintptr_t)block->alloc_size)))
b57f37fb WP	425	{
	426	rb_bh_fail("rb_bh_free() bogus pointer");
	427	}
670f0c24	428	block->free_count++;
94b4fbf9	429
670f0c24	430	rb_dlinkAdd(data, (rb_dlink_node *)ptr, &bh->free_list);
b57f37fb WP	431	#endif /* !NOBALLOC */
	432	return (0);
	433	}
	434
	435
	436	/* ************************************************************************ */
	437	/* FUNCTION DOCUMENTATION: */
	438	/* rb_bhDestroy */
	439	/* Description: */
	440	/* Completely free()s a rb_bh. Use for cleanup. */
	441	/* Parameters: */
	442	/* bh (IN): Pointer to the rb_bh to be destroyed. */
	443	/* Returns: */
	444	/* 0 if successful, 1 if bh == NULL */
	445	/* ************************************************************************ */
	446	int
94b4fbf9	447	rb_bh_destroy(rb_bh *bh)
b57f37fb WP	448	{
	449	#ifndef NOBALLOC
	450	rb_dlink_node ptr, next;
	451	rb_heap_block *b;
	452	#endif
	453	if(bh == NULL)
	454	return (1);
	455
	456	#ifndef NOBALLOC
	457	RB_DLINK_FOREACH_SAFE(ptr, next, bh->block_list.head)
	458	{
	459	b = ptr->data;
	460	free_block(b->elems, b->alloc_size);
	461	rb_free(b);
	462	}
	463	#endif /* !NOBALLOC */
94b4fbf9	464
b57f37fb WP	465	rb_dlinkDelete(&bh->hlist, heap_lists);
	466	rb_free(bh->desc);
	467	rb_free(bh);
	468
	469	return (0);
	470	}
	471
	472	void
94b4fbf9	473	rb_bh_usage(rb_bh bh, size_t bused, size_t bfree, size_t bmemusage, const char **desc)
b57f37fb	474	{
94b4fbf9	475	#ifndef NOBALLOC
b57f37fb WP	476	size_t used, freem, memusage;
	477
	478	if(bh == NULL)
	479	{
	480	return;
	481	}
	482
	483	freem = rb_dlink_list_length(&bh->free_list);
	484	used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
670f0c24	485	memusage = used * bh->elemSize;
b57f37fb WP	486	if(bused != NULL)
	487	*bused = used;
	488	if(bfree != NULL)
	489	*bfree = freem;
	490	if(bmemusage != NULL)
	491	*bmemusage = memusage;
	492	if(desc != NULL)
	493	*desc = bh->desc;
94b4fbf9 VY	494	#else
	495	static char *noballoc = "no blockheap";
	496	*bused = 0;
	497	*bfree = 0;
	498	*bmemusage = 0;
	499	*desc = noballoc;
	500	#endif
b57f37fb WP	501	}
b57f37fb WP	502
94b4fbf9 VY	503	void
94b4fbf9 VY	504	rb_bh_usage_all(rb_bh_usage_cb cb, void data)
b57f37fb WP	505	{
	506	rb_dlink_node *ptr;
	507	rb_bh *bh;
	508	size_t used, freem, memusage, heapalloc;
	509	static const char *unnamed = "(unnamed_heap)";
	510	const char *desc = unnamed;
	511
	512	if(cb == NULL)
	513	return;
	514
	515	RB_DLINK_FOREACH(ptr, heap_lists->head)
	516	{
94b4fbf9	517	bh = (rb_bh *)ptr->data;
b57f37fb WP	518	freem = rb_dlink_list_length(&bh->free_list);
b57f37fb WP	519	used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
670f0c24 VY	520	memusage = used * bh->elemSize;
670f0c24 VY	521	heapalloc = (freem + used) * bh->elemSize;
b57f37fb WP	522	if(bh->desc != NULL)
b57f37fb WP	523	desc = bh->desc;
94b4fbf9	524	cb(used, freem, memusage, heapalloc, desc, data);
b57f37fb WP	525	}
	526	return;
	527	}
	528
	529	void
	530	rb_bh_total_usage(size_t total_alloc, size_t total_used)
	531	{
	532	rb_dlink_node *ptr;
	533	size_t total_memory = 0, used_memory = 0, used, freem;
	534	rb_bh *bh;
94b4fbf9	535
b57f37fb WP	536	RB_DLINK_FOREACH(ptr, heap_lists->head)
	537	{
	538	bh = (rb_bh *)ptr->data;
	539	freem = rb_dlink_list_length(&bh->free_list);
	540	used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
670f0c24 VY	541	used_memory += used * bh->elemSize;
670f0c24 VY	542	total_memory += (freem + used) * bh->elemSize;
b57f37fb	543	}
94b4fbf9	544
b57f37fb WP	545	if(total_alloc != NULL)
	546	*total_alloc = total_memory;
	547	if(total_used != NULL)
	548	*total_used = used_memory;
	549	}
	550
	551	#ifndef NOBALLOC
	552	int
94b4fbf9	553	rb_bh_gc(rb_bh *bh)
b57f37fb WP	554	{
	555	rb_heap_block *b;
	556	rb_dlink_node ptr, next;
	557	unsigned long i;
	558	uintptr_t offset;
94b4fbf9	559
b57f37fb WP	560	if(bh == NULL)
	561	{
	562	/* somebody is smoking some craq..(probably lee, but don't tell him that) */
	563	return (1);
	564	}
	565
94b4fbf9 VY	566	if((rb_dlink_list_length(&bh->free_list) < bh->elemsPerBlock)
94b4fbf9 VY	567	\|\| rb_dlink_list_length(&bh->block_list) == 1)
b57f37fb WP	568	{
	569	/* There couldn't possibly be an entire free block. Return. */
	570	return (0);
	571	}
	572
	573	RB_DLINK_FOREACH_SAFE(ptr, next, bh->block_list.head)
	574	{
	575	b = ptr->data;
	576	if(rb_dlink_list_length(&bh->block_list) == 1)
	577	return (0);
94b4fbf9	578
b57f37fb WP	579	if(b->free_count == bh->elemsPerBlock)
	580	{
	581	/* i'm seriously going to hell for this.. */
	582
	583	offset = (uintptr_t)b->elems;
94b4fbf9	584	for(i = 0; i < bh->elemsPerBlock; i++, offset += (uintptr_t)bh->elemSize)
b57f37fb	585	{
94b4fbf9 VY	586	rb_dlinkDelete((rb_dlink_node *)(offset + offset_pad),
94b4fbf9 VY	587	&bh->free_list);
b57f37fb WP	588	}
	589	rb_dlinkDelete(&b->node, &bh->block_list);
	590	free_block(b->elems, b->alloc_size);
	591	rb_free(b);
	592	}
94b4fbf9	593
b57f37fb WP	594	}
	595	return (0);
	596	}
	597	#endif /* !NOBALLOC */