[solanum.git] / librb / 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
 *
 */

/*
 * 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 <librb_config.h>
#include <rb_lib.h>

static void _rb_bh_fail(const char *reason, const char *file, int line) __attribute__((noreturn));

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

static rb_dlink_list *heap_lists;

#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();
}

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

/* ************************************************************************ */
/* 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));
	bh->elemSize = elemsize;
	bh->elemsPerBlock = elemsperblock;
	if(desc != NULL)
		bh->desc = rb_strdup(desc);

	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)
{
	lrb_assert(bh != NULL);
	if(rb_unlikely(bh == NULL))
	{
		rb_bh_fail("Cannot allocate if bh == NULL");
	}

	return (rb_malloc(bh->elemSize));
}


/* ************************************************************************ */
/* 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)
{
	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);
	}

	rb_free(ptr);
	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)
{
	if(bh == NULL)
		return (1);

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

	return (0);
}

void
rb_bh_usage(rb_bh *bh __attribute__((unused)), size_t *bused, size_t *bfree, size_t *bmemusage, const char **desc)
{
	if(bused != NULL)
		*bused = 0;
	if(bfree != NULL)
		*bfree = 0;
	if(bmemusage != NULL)
		*bmemusage = 0;
	if(desc != NULL)
		*desc = "no blockheap";
}

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;
}
Commit	Line	Data
db137867 AC	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	*
55abcbb2	9	* Below are the orignal headers from the old blalloc.c
db137867 AC	10	*
	11	* File: blalloc.c
	12	* Owner: Wohali (Joan Touzet)
55abcbb2	13	*
db137867 AC	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	*
db137867 AC	31	*/
db137867 AC	32
55abcbb2	33	/*
db137867 AC	34	* About the block allocator
	35	*
	36	* Basically we have three ways of getting memory off of the operating
	37	* system. Below are this list of methods and the order of preference.
	38	*
	39	* 1. mmap() anonymous pages with the MMAP_ANON flag.
	40	* 2. mmap() via the /dev/zero trick.
55abcbb2 KB	41	* 3. HeapCreate/HeapAlloc (on win32)
55abcbb2 KB	42	* 4. malloc()
db137867 AC	43	*
db137867 AC	44	* The advantages of 1 and 2 are this. We can munmap() the pages which will
55abcbb2	45	* return the pages back to the operating system, thus reducing the size
db137867 AC	46	* of the process as the memory is unused. malloc() on many systems just keeps
	47	* a heap of memory to itself, which never gets given back to the OS, except on
	48	* exit. This of course is bad, if say we have an event that causes us to allocate
	49	* say, 200MB of memory, while our normal memory consumption would be 15MB. In the
	50	* malloc() case, the amount of memory allocated to our process never goes down, as
	51	* malloc() has it locked up in its heap. With the mmap() method, we can munmap()
	52	* the block and return it back to the OS, thus causing our memory consumption to go
	53	* down after we no longer need it.
55abcbb2	54	*
db137867 AC	55	*
	56	*
	57	*/
fe037171 EM	58	#include <librb_config.h>
fe037171 EM	59	#include <rb_lib.h>
db137867	60
92706fd5 AJ	61	static void _rb_bh_fail(const char reason, const char file, int line) __attribute__((noreturn));
92706fd5 AJ	62
ce1c921c VY	63	static uintptr_t offset_pad;
ce1c921c VY	64
db137867 AC	65	/* status information for an allocated block in heap */
	66	struct rb_heap_block
	67	{
	68	size_t alloc_size;
	69	rb_dlink_node node;
	70	unsigned long free_count;
	71	void elems; / Points to allocated memory */
	72	};
	73	typedef struct rb_heap_block rb_heap_block;
	74
db137867 AC	75	/* information for the root node of the heap */
	76	struct rb_bh
	77	{
	78	rb_dlink_node hlist;
	79	size_t elemSize; /* Size of each element to be stored */
	80	unsigned long elemsPerBlock; /* Number of elements per block */
	81	rb_dlink_list block_list;
	82	rb_dlink_list free_list;
	83	char *desc;
	84	};
	85
db137867 AC	86	static rb_dlink_list *heap_lists;
db137867 AC	87
db137867 AC	88	#define rb_bh_fail(x) _rb_bh_fail(x, __FILE__, __LINE__)
	89
	90	static void
	91	_rb_bh_fail(const char reason, const char file, int line)
	92	{
	93	rb_lib_log("rb_heap_blockheap failure: %s (%s:%d)", reason, file, line);
	94	abort();
	95	}
3202e249	96
db137867 AC	97	/*
db137867 AC	98	* void rb_init_bh(void)
55abcbb2	99	*
db137867 AC	100	* Inputs: None
	101	* Outputs: None
	102	* Side Effects: Initializes the block heap
	103	*/
	104
	105	void
	106	rb_init_bh(void)
	107	{
	108	heap_lists = rb_malloc(sizeof(rb_dlink_list));
ce1c921c VY	109	offset_pad = sizeof(void *);
	110	/* XXX if you get SIGBUS when trying to use a long long..here is where you need to
	111	* fix your shit
	112	*/
	113	#ifdef __sparc__
	114	if((offset_pad % __alignof__(long long)) != 0)
	115	{
	116	offset_pad += __alignof__(long long);
	117	offset_pad &= ~(__alignof__(long long) - 1);
	118	}
3202e249	119	#endif
db137867	120	}
db137867 AC	121
	122	/* ************************************************************************ */
	123	/* FUNCTION DOCUMENTATION: */
	124	/* rb_bh_create */
	125	/* Description: */
	126	/* Creates a new blockheap from which smaller blocks can be allocated. */
	127	/* Intended to be used instead of multiple calls to malloc() when */
	128	/* performance is an issue. */
	129	/* Parameters: */
	130	/* elemsize (IN): Size of the basic element to be stored */
	131	/* elemsperblock (IN): Number of elements to be stored in a single block */
	132	/* of memory. When the blockheap runs out of free memory, it will */
	133	/* allocate elemsize * elemsperblock more. */
	134	/* Returns: */
	135	/* Pointer to new rb_bh, or NULL if unsuccessful */
	136	/* ************************************************************************ */
	137	rb_bh *
	138	rb_bh_create(size_t elemsize, int elemsperblock, const char *desc)
	139	{
	140	rb_bh *bh;
	141	lrb_assert(elemsize > 0 && elemsperblock > 0);
	142	lrb_assert(elemsize >= sizeof(rb_dlink_node));
ce1c921c	143
db137867	144	/* Catch idiotic requests up front */
c2ac22cc	145	if((elemsize == 0) \|\| (elemsperblock <= 0))
db137867 AC	146	{
	147	rb_bh_fail("Attempting to rb_bh_create idiotic sizes");
	148	}
3202e249	149
db137867 AC	150	if(elemsize < sizeof(rb_dlink_node))
db137867 AC	151	rb_bh_fail("Attempt to rb_bh_create smaller than sizeof(rb_dlink_node)");
3202e249	152
db137867 AC	153	/* Allocate our new rb_bh */
db137867 AC	154	bh = rb_malloc(sizeof(rb_bh));
db137867 AC	155	bh->elemSize = elemsize;
	156	bh->elemsPerBlock = elemsperblock;
	157	if(desc != NULL)
	158	bh->desc = rb_strdup(desc);
	159
db137867 AC	160	if(bh == NULL)
	161	{
	162	rb_bh_fail("bh == NULL when it shouldn't be");
	163	}
	164	rb_dlinkAdd(bh, &bh->hlist, heap_lists);
	165	return (bh);
	166	}
	167
	168	/* ************************************************************************ */
	169	/* FUNCTION DOCUMENTATION: */
	170	/* rb_bh_alloc */
	171	/* Description: */
	172	/* Returns a pointer to a struct within our rb_bh that's free for */
	173	/* the taking. */
	174	/* Parameters: */
	175	/* bh (IN): Pointer to the Blockheap. */
	176	/* Returns: */
	177	/* Pointer to a structure (void ), or NULL if unsuccessful. /
	178	/* ************************************************************************ */
	179
	180	void *
3202e249	181	rb_bh_alloc(rb_bh *bh)
db137867	182	{
db137867	183	lrb_assert(bh != NULL);
c2ac22cc	184	if(rb_unlikely(bh == NULL))
db137867 AC	185	{
	186	rb_bh_fail("Cannot allocate if bh == NULL");
	187	}
	188
3202e249	189	return (rb_malloc(bh->elemSize));
db137867 AC	190	}
	191
	192
	193	/* ************************************************************************ */
	194	/* FUNCTION DOCUMENTATION: */
	195	/* rb_bh_free */
	196	/* Description: */
	197	/* Returns an element to the free pool, does not free() */
	198	/* Parameters: */
	199	/* bh (IN): Pointer to rb_bh containing element */
	200	/* ptr (in): Pointer to element to be "freed" */
	201	/* Returns: */
	202	/* 0 if successful, 1 if element not contained within rb_bh. */
	203	/* ************************************************************************ */
	204	int
3202e249	205	rb_bh_free(rb_bh bh, void ptr)
db137867	206	{
db137867 AC	207	lrb_assert(bh != NULL);
	208	lrb_assert(ptr != NULL);
	209
c2ac22cc	210	if(rb_unlikely(bh == NULL))
db137867	211	{
c2ac22cc	212	rb_lib_log("balloc.c:rb_bhFree() bh == NULL");
db137867 AC	213	return (1);
	214	}
	215
c2ac22cc	216	if(rb_unlikely(ptr == NULL))
db137867	217	{
c2ac22cc	218	rb_lib_log("balloc.rb_bhFree() ptr == NULL");
db137867 AC	219	return (1);
	220	}
	221
db137867	222	rb_free(ptr);
db137867 AC	223	return (0);
	224	}
	225
	226
	227	/* ************************************************************************ */
	228	/* FUNCTION DOCUMENTATION: */
	229	/* rb_bhDestroy */
	230	/* Description: */
	231	/* Completely free()s a rb_bh. Use for cleanup. */
	232	/* Parameters: */
	233	/* bh (IN): Pointer to the rb_bh to be destroyed. */
	234	/* Returns: */
	235	/* 0 if successful, 1 if bh == NULL */
	236	/* ************************************************************************ */
	237	int
3202e249	238	rb_bh_destroy(rb_bh *bh)
db137867	239	{
db137867 AC	240	if(bh == NULL)
	241	return (1);
	242
db137867 AC	243	rb_dlinkDelete(&bh->hlist, heap_lists);
	244	rb_free(bh->desc);
	245	rb_free(bh);
	246
	247	return (0);
	248	}
	249
	250	void
8679c0fe	251	rb_bh_usage(rb_bh bh __attribute__((unused)), size_t bused, size_t bfree, size_t bmemusage, const char **desc)
db137867	252	{
74178a38 JT	253	if(bused != NULL)
	254	*bused = 0;
	255	if(bfree != NULL)
	256	*bfree = 0;
	257	if(bmemusage != NULL)
	258	*bmemusage = 0;
	259	if(desc != NULL)
	260	*desc = "no blockheap";
db137867 AC	261	}
db137867 AC	262
3202e249 VY	263	void
3202e249 VY	264	rb_bh_usage_all(rb_bh_usage_cb cb, void data)
db137867 AC	265	{
	266	rb_dlink_node *ptr;
	267	rb_bh *bh;
	268	size_t used, freem, memusage, heapalloc;
	269	static const char *unnamed = "(unnamed_heap)";
	270	const char *desc = unnamed;
	271
	272	if(cb == NULL)
	273	return;
	274
	275	RB_DLINK_FOREACH(ptr, heap_lists->head)
	276	{
3202e249	277	bh = (rb_bh *)ptr->data;
db137867 AC	278	freem = rb_dlink_list_length(&bh->free_list);
db137867 AC	279	used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
ce1c921c VY	280	memusage = used * bh->elemSize;
ce1c921c VY	281	heapalloc = (freem + used) * bh->elemSize;
db137867 AC	282	if(bh->desc != NULL)
db137867 AC	283	desc = bh->desc;
3202e249	284	cb(used, freem, memusage, heapalloc, desc, data);
db137867 AC	285	}
	286	return;
	287	}
	288
	289	void
	290	rb_bh_total_usage(size_t total_alloc, size_t total_used)
	291	{
	292	rb_dlink_node *ptr;
	293	size_t total_memory = 0, used_memory = 0, used, freem;
	294	rb_bh *bh;
3202e249	295
db137867 AC	296	RB_DLINK_FOREACH(ptr, heap_lists->head)
	297	{
	298	bh = (rb_bh *)ptr->data;
	299	freem = rb_dlink_list_length(&bh->free_list);
	300	used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
ce1c921c VY	301	used_memory += used * bh->elemSize;
ce1c921c VY	302	total_memory += (freem + used) * bh->elemSize;
db137867	303	}
3202e249	304
db137867 AC	305	if(total_alloc != NULL)
	306	*total_alloc = total_memory;
	307	if(total_used != NULL)
	308	*total_used = used_memory;
	309	}