ircd-hybrid-7.3/src/balloc.c

/*
 *  ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd).
 *
 *  Copyright (C) 2002 by the past and present ircd coders, and others.
 *  Original credit lines follow:
 *
 *  File:   balloc.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., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 *  USA
 */

/*! \file balloc.c
 * \brief A block allocator
 * \version $Id$
 * 
 * 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.\n
 * 2. mmap() via the /dev/zero trick.\n
 * 3. malloc()\n
 *
 * 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 "stdinc.h"

#if USE_BLOCK_ALLOC
#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 /* MAP_ANONYMOUS */
#endif

#include "ircd.h"
#include "balloc.h"
#include "irc_string.h"
#include "tools.h"
#include "client.h"
#include "send.h"
#include "numeric.h"
#include "fdlist.h"
#include "event.h"


static BlockHeap *heap_list = NULL;

static int BlockHeapGarbageCollect(BlockHeap *);
static void heap_garbage_collection(void *);

/*! \brief Returns memory for the block back to either the malloc heap
 *         in case of !HAVE_MMAP, or back to the OS otherwise.
 * \param ptr  Pointer to memory to be freed
 * \param size The size of the memory space
 */
static inline void
free_block(void *ptr, size_t size)
{
#ifdef HAVE_MMAP
  munmap(ptr, size);
#else
  free(ptr);
#endif
}

#ifdef HAVE_MMAP
#ifndef MAP_ANON /* But we cannot mmap() anonymous pages */
                 /* So we mmap() /dev/zero, which is just as good */
static fde_t dpfd;
#endif
#endif

/*! \brief Opens /dev/zero and saves the file handle for
 * future allocations.
 */
void
initBlockHeap(void)
{
#ifdef HAVE_MMAP
#ifndef MAP_ANON
  int zero_fd = open("/dev/zero", O_RDWR);

  if (zero_fd < 0)
    outofmemory();
  fd_open(&dpfd, zero_fd, 0, "Anonymous mmap()");
#endif
  eventAdd("heap_garbage_collection", &heap_garbage_collection, NULL, 119);
#endif
}

/*!
 * \param size Size of block to allocate
 * \return Address pointer to allocated data space
 */
static inline void *
get_block(size_t size)
{
#ifdef HAVE_MMAP
  void *ptr = NULL;

#ifndef MAP_ANON
  ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, dpfd.fd, 0);
#else
  ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
#endif
  return ptr == MAP_FAILED ? NULL : ptr;
#else
  return malloc(size);
#endif
}

static void
heap_garbage_collection(void *arg)
{
  BlockHeap *bh;

  for (bh = heap_list; bh != NULL; bh = bh->next)
    BlockHeapGarbageCollect(bh);
}

/*! \brief Allocates a new block for addition to a blockheap
 * \param bh Pointer to parent blockheap
 * \return 0 if successful, 1 if not
 */
static int
newblock(BlockHeap *bh)
{
  MemBlock *newblk = NULL;
  Block *b = NULL;
  int i = 0;
  void *offset = NULL;

  /* Setup the initial data structure. */
  if ((b = calloc(1, sizeof(Block))) == NULL)
    return 1;

  b->freeElems = bh->elemsPerBlock;
  b->next = bh->base;
  b->alloc_size = bh->elemsPerBlock * (bh->elemSize + sizeof(MemBlock));
  b->elems = get_block(b->alloc_size);

  if (b->elems == NULL)
    return 1;

  offset = b->elems;

  /* Setup our blocks now */
  for (; i < bh->elemsPerBlock; ++i)
  {
    void *data;

    newblk = offset;
    newblk->block = b;
    data = (void *)((size_t)offset + sizeof(MemBlock));

    dlinkAdd(data, &newblk->self, &b->free_list);
    offset = (void *)((size_t)offset + bh->elemSize + sizeof(MemBlock));
  }

  ++bh->blocksAllocated;
  bh->freeElems += bh->elemsPerBlock;
  bh->base = b;

  return 0;
}

/*! \brief Creates a new blockheap
 *
 * 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.
 *
 * \param name          Name of the blockheap
 * \param elemsize      Size of the basic element to be stored
 * \param elemsperblock 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.
 * \return Pointer to new BlockHeap, or NULL if unsuccessful
 */
BlockHeap *
BlockHeapCreate(const char *const name, size_t elemsize, int elemsperblock)
{
  BlockHeap *bh = NULL;
  assert(elemsize > 0 && elemsperblock > 0);

  /* Catch idiotic requests up front */
  if ((elemsize <= 0) || (elemsperblock <= 0))
    outofmemory();    /* die.. out of memory */

  /* Allocate our new BlockHeap */
  if ((bh = calloc(1, sizeof(BlockHeap))) == NULL)
    outofmemory();    /* die.. out of memory */

  if ((elemsize % sizeof(void *)) != 0)
  {
    /* Pad to even pointer boundary */
    elemsize += sizeof(void *);
    elemsize &= ~(sizeof(void *) - 1);
  }

  bh->name = name;
  bh->elemSize = elemsize;
  bh->elemsPerBlock = elemsperblock;

  /* Be sure our malloc was successful */
  if (newblock(bh))
  {
    if (bh != NULL)
      free(bh);

     outofmemory();    /* die.. out of memory */
  }

  assert(bh);

  bh->next = heap_list;
  heap_list = bh;

  return bh;
}

/*! \brief Returns a pointer to a struct within our BlockHeap that's free for
 *         the taking.
 * \param bh Pointer to the Blockheap
 * \return Address pointer to allocated data space, or NULL if unsuccessful
 */
void *
BlockHeapAlloc(BlockHeap *bh)
{
  Block *walker = NULL;
  dlink_node *new_node = NULL;

  assert(bh != NULL);

  if (bh->freeElems == 0)
  {   
    /* Allocate new block and assign */
    /* newblock returns 1 if unsuccessful, 0 if not */
    if (newblock(bh))
    {
      /* That didn't work..try to garbage collect */
      BlockHeapGarbageCollect(bh);  

      if (newblock(bh))
        outofmemory(); /* Well that didn't work either...bail */
    }
  }
      
  for (walker = bh->base; walker != NULL; walker = walker->next)
  {
    if (walker->freeElems > 0)
    {
      --bh->freeElems;
      --walker->freeElems;
      new_node = walker->free_list.head;

      dlinkDelete(new_node, &walker->free_list);
      assert(new_node->data != NULL);

      memset(new_node->data, 0, bh->elemSize);
      return new_node->data;
    }
  }

  assert(0 == 1);
  outofmemory();
  return NULL;
}

/*! \brief Returns an element to the free pool, does not free()
 * \param bh  Pointer to BlockHeap containing element
 * \param ptr Pointer to element to be "freed"
 * \return 0 if successful, 1 if element not contained within BlockHeap
 */
int
BlockHeapFree(BlockHeap *bh, void *ptr)
{
  Block *block = NULL;
  struct MemBlock *memblock = NULL;
    
  assert(bh != NULL);
  assert(ptr != NULL);

  memblock = (void *)((size_t)ptr - sizeof(MemBlock));
  assert(memblock->block != NULL);

  if (memblock->block == NULL)
    outofmemory();

  block = memblock->block;
  ++bh->freeElems;
  ++block->freeElems;
  mem_frob(ptr, bh->elemSize);

  dlinkAdd(ptr, &memblock->self, &block->free_list);
  return 0;
}

/*! \brief Performs garbage collection on the block heap.
 *
 * Performs garbage collection on the block heap.  Any blocks that are
 * completely unallocated are removed from the heap.  Garbage collection
 * will \b never remove the root node of the heap.
 *
 * \param bh Pointer to the BlockHeap to be cleaned up
 * \return 0 if successful, 1 if bh == NULL
 */
static int
BlockHeapGarbageCollect(BlockHeap *bh)
{
  Block *walker = NULL, *last = NULL;

  assert(bh != NULL);

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

  walker = bh->base;

  while (walker != NULL)
  {
    if (walker->freeElems == bh->elemsPerBlock)
    {
      free_block(walker->elems, walker->alloc_size);

      if (last != NULL)
      {
        last->next = walker->next;

        if (walker != NULL)
          free(walker);
        walker = last->next;
      }
      else
      {
        bh->base = walker->next;

        if (walker != NULL)
          free(walker);
        walker = bh->base;
      }

      --bh->blocksAllocated;
      bh->freeElems -= bh->elemsPerBlock;
    }
    else
    {
      last = walker;
      walker = walker->next;
    }
  }

  return 0;
}

/*! \brief Completely free()s a BlockHeap.  Use for cleanup.
 * \param bh Pointer to the BlockHeap to be destroyed
 * \return 0 if successful, 1 if bh == NULL
 */
int
BlockHeapDestroy(BlockHeap *bh)
{
  Block *walker = NULL, *next = NULL;

  if (bh == NULL)
    return 1;

  for (walker = bh->base; walker != NULL; walker = next)
  {
    next = walker->next;
    free_block(walker->elems, walker->alloc_size);

    if (walker != NULL)
      free(walker);
  }

  if (heap_list == bh)
    heap_list = bh->next;
  else {
    BlockHeap *prev;

    for (prev = heap_list; prev->next != bh; prev = prev->next)
      /* nothing */ ;
    prev->next = bh->next;
  }

  free(bh);
  return 0;
}

/*! \brief Returns the number of bytes being used
 * \param bh Pointer to a BlockHeap
 * \return Number of bytes being used
 */
static size_t
block_heap_get_used_mem(const BlockHeap *const bh)
{
  return(((bh->blocksAllocated *
           bh->elemsPerBlock)-bh->freeElems) *
          (bh->elemSize + sizeof(MemBlock)));
}

/*! \brief Returns the number of bytes being free for further allocations
 * \param bh Pointer to a BlockHeap
 * \return Number of bytes being free for further allocations
 */
static size_t
block_heap_get_free_mem(const BlockHeap *const bh)
{
  return(bh->freeElems * (bh->elemSize + sizeof(MemBlock)));
}

/*! \brief Returns the total number of bytes of memory belonging to a heap
 * \param bh Pointer to a BlockHeap
 * \return Total number of bytes of memory belonging to a heap
 */
static size_t
block_heap_get_size_mem(const BlockHeap *const bh)
{
  return(((bh->blocksAllocated *
           bh->elemsPerBlock)) *
          (bh->elemSize + sizeof(MemBlock)));
}

/*! \brief Returns the number of elements being used.
 * \param bh Pointer to a BlockHeap
 * \return Number of elements being free for further allocations
 */
static unsigned int
block_heap_get_used_elm(const BlockHeap *const bh)
{
  return((bh->blocksAllocated *
          bh->elemsPerBlock)-bh->freeElems);
}

/*! \brief Returns the number of elements being free for further allocations.
 * \param bh Pointer to a BlockHeap
 * \return Number of elements being free for further allocations
 */
static unsigned int
block_heap_get_free_elm(const BlockHeap *const bh)
{
  return(bh->freeElems);
}

/*! \brief Returns the number of total elements belonging to a heap.
 *         Includes \b free and \b used elements.
 * \param bh Pointer to a BlockHeap
 * \return Number of total elements belonging to a heap
 */
static unsigned int
block_heap_get_size_elm(const BlockHeap *const bh)
{
  return(bh->blocksAllocated * bh->elemsPerBlock);
}

void
block_heap_report_stats(struct Client *client_p)
{
  const BlockHeap *bh = NULL;

  for (bh = heap_list; bh != NULL; bh = bh->next)
    sendto_one(client_p, ":%s %d %s z :%s mempool: used %u/%u free %u/%u (size %u/%u)",
               me.name, RPL_STATSDEBUG, client_p->name, bh->name,
               block_heap_get_used_elm(bh),
               block_heap_get_used_mem(bh),
               block_heap_get_free_elm(bh),
               block_heap_get_free_mem(bh),
               block_heap_get_size_elm(bh),
               block_heap_get_size_mem(bh));
}

#endif
Revision:	908
Committed:	Sun Nov 4 23:21:51 2007 UTC (17 years, 9 months ago) by stu
Content type:	text/x-csrc
Original Path:	*ircd-hybrid-7.2/src/balloc.c*
File size:	13020 byte(s)
Log Message:	Completely redo the build system. Now uses libtool and automake. Suggest you clean out your tree and then do ./autogen.sh.
#	Content
1	/*
2	* ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd).
3	*
4	* Copyright (C) 2002 by the past and present ircd coders, and others.
5	* Original credit lines follow:
6	*
7	* File: balloc.c
8	* Owner: Wohali (Joan Touzet)
9	*
10	* Modified 2001/11/29 for mmap() support by Aaron Sethman <androsyn@ratbox.org>
11	*
12	* This program is free software; you can redistribute it and/or modify
13	* it under the terms of the GNU General Public License as published by
14	* the Free Software Foundation; either version 2 of the License, or
15	* (at your option) any later version.
16	*
17	* This program is distributed in the hope that it will be useful,
18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20	* GNU General Public License for more details.
21	*
22	* You should have received a copy of the GNU General Public License
23	* along with this program; if not, write to the Free Software
24	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
25	* USA
26	*/
27
28	/*! \file balloc.c
29	* \brief A block allocator
30	* \version $Id$
31	*
32	* About the block allocator
33	*
34	* Basically we have three ways of getting memory off of the operating
35	* system. Below are this list of methods and the order of preference.
36	*
37	* 1. mmap() anonymous pages with the MMAP_ANON flag.\n
38	* 2. mmap() via the /dev/zero trick.\n
39	* 3. malloc()\n
40	*
41	* The advantages of 1 and 2 are this. We can munmap() the pages which will
42	* return the pages back to the operating system, thus reducing the size
43	* of the process as the memory is unused. malloc() on many systems just keeps
44	* a heap of memory to itself, which never gets given back to the OS, except on
45	* exit. This of course is bad, if say we have an event that causes us to allocate
46	* say, 200MB of memory, while our normal memory consumption would be 15MB. In the
47	* malloc() case, the amount of memory allocated to our process never goes down, as
48	* malloc() has it locked up in its heap. With the mmap() method, we can munmap()
49	* the block and return it back to the OS, thus causing our memory consumption to go
50	* down after we no longer need it.
51	*/
52
53
54	#include "stdinc.h"
55
56	#if USE_BLOCK_ALLOC
57	#ifdef HAVE_MMAP /* We've got mmap() that is good */
58	#include <sys/mman.h>
59
60	/* HP-UX sucks */
61	#ifdef MAP_ANONYMOUS
62	#ifndef MAP_ANON
63	#define MAP_ANON MAP_ANONYMOUS
64	#endif
65	#endif /* MAP_ANONYMOUS */
66	#endif
67
68	#include "ircd.h"
69	#include "balloc.h"
70	#include "irc_string.h"
71	#include "tools.h"
72	#include "client.h"
73	#include "send.h"
74	#include "numeric.h"
75	#include "fdlist.h"
76	#include "event.h"
77
78
79	static BlockHeap *heap_list = NULL;
80
81	static int BlockHeapGarbageCollect(BlockHeap *);
82	static void heap_garbage_collection(void *);
83
84	/*! \brief Returns memory for the block back to either the malloc heap
85	* in case of !HAVE_MMAP, or back to the OS otherwise.
86	* \param ptr Pointer to memory to be freed
87	* \param size The size of the memory space
88	*/
89	static inline void
90	free_block(void *ptr, size_t size)
91	{
92	#ifdef HAVE_MMAP
93	munmap(ptr, size);
94	#else
95	free(ptr);
96	#endif
97	}
98
99	#ifdef HAVE_MMAP
100	#ifndef MAP_ANON /* But we cannot mmap() anonymous pages */
101	/* So we mmap() /dev/zero, which is just as good */
102	static fde_t dpfd;
103	#endif
104	#endif
105
106	/*! \brief Opens /dev/zero and saves the file handle for
107	* future allocations.
108	*/
109	void
110	initBlockHeap(void)
111	{
112	#ifdef HAVE_MMAP
113	#ifndef MAP_ANON
114	int zero_fd = open("/dev/zero", O_RDWR);
115
116	if (zero_fd < 0)
117	outofmemory();
118	fd_open(&dpfd, zero_fd, 0, "Anonymous mmap()");
119	#endif
120	eventAdd("heap_garbage_collection", &heap_garbage_collection, NULL, 119);
121	#endif
122	}
123
124	/*!
125	* \param size Size of block to allocate
126	* \return Address pointer to allocated data space
127	*/
128	static inline void *
129	get_block(size_t size)
130	{
131	#ifdef HAVE_MMAP
132	void *ptr = NULL;
133
134	#ifndef MAP_ANON
135	ptr = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE, dpfd.fd, 0);
136	#else
137	ptr = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE \| MAP_ANON, -1, 0);
138	#endif
139	return ptr == MAP_FAILED ? NULL : ptr;
140	#else
141	return malloc(size);
142	#endif
143	}
144
145	static void
146	heap_garbage_collection(void *arg)
147	{
148	BlockHeap *bh;
149
150	for (bh = heap_list; bh != NULL; bh = bh->next)
151	BlockHeapGarbageCollect(bh);
152	}
153
154	/*! \brief Allocates a new block for addition to a blockheap
155	* \param bh Pointer to parent blockheap
156	* \return 0 if successful, 1 if not
157	*/
158	static int
159	newblock(BlockHeap *bh)
160	{
161	MemBlock *newblk = NULL;
162	Block *b = NULL;
163	int i = 0;
164	void *offset = NULL;
165
166	/* Setup the initial data structure. */
167	if ((b = calloc(1, sizeof(Block))) == NULL)
168	return 1;
169
170	b->freeElems = bh->elemsPerBlock;
171	b->next = bh->base;
172	b->alloc_size = bh->elemsPerBlock * (bh->elemSize + sizeof(MemBlock));
173	b->elems = get_block(b->alloc_size);
174
175	if (b->elems == NULL)
176	return 1;
177
178	offset = b->elems;
179
180	/* Setup our blocks now */
181	for (; i < bh->elemsPerBlock; ++i)
182	{
183	void *data;
184
185	newblk = offset;
186	newblk->block = b;
187	data = (void *)((size_t)offset + sizeof(MemBlock));
188
189	dlinkAdd(data, &newblk->self, &b->free_list);
190	offset = (void *)((size_t)offset + bh->elemSize + sizeof(MemBlock));
191	}
192
193	++bh->blocksAllocated;
194	bh->freeElems += bh->elemsPerBlock;
195	bh->base = b;
196
197	return 0;
198	}
199
200	/*! \brief Creates a new blockheap
201	*
202	* Creates a new blockheap from which smaller blocks can be allocated.
203	* Intended to be used instead of multiple calls to malloc() when
204	* performance is an issue.
205	*
206	* \param name Name of the blockheap
207	* \param elemsize Size of the basic element to be stored
208	* \param elemsperblock Number of elements to be stored in a single block of
209	* memory. When the blockheap runs out of free memory,
210	* it will allocate elemsize * elemsperblock more.
211	* \return Pointer to new BlockHeap, or NULL if unsuccessful
212	*/
213	BlockHeap *
214	BlockHeapCreate(const char *const name, size_t elemsize, int elemsperblock)
215	{
216	BlockHeap *bh = NULL;
217	assert(elemsize > 0 && elemsperblock > 0);
218
219	/* Catch idiotic requests up front */
220	if ((elemsize <= 0) \|\| (elemsperblock <= 0))
221	outofmemory(); /* die.. out of memory */
222
223	/* Allocate our new BlockHeap */
224	if ((bh = calloc(1, sizeof(BlockHeap))) == NULL)
225	outofmemory(); /* die.. out of memory */
226
227	if ((elemsize % sizeof(void *)) != 0)
228	{
229	/* Pad to even pointer boundary */
230	elemsize += sizeof(void *);
231	elemsize &= ~(sizeof(void *) - 1);
232	}
233
234	bh->name = name;
235	bh->elemSize = elemsize;
236	bh->elemsPerBlock = elemsperblock;
237
238	/* Be sure our malloc was successful */
239	if (newblock(bh))
240	{
241	if (bh != NULL)
242	free(bh);
243
244	outofmemory(); /* die.. out of memory */
245	}
246
247	assert(bh);
248
249	bh->next = heap_list;
250	heap_list = bh;
251
252	return bh;
253	}
254
255	/*! \brief Returns a pointer to a struct within our BlockHeap that's free for
256	* the taking.
257	* \param bh Pointer to the Blockheap
258	* \return Address pointer to allocated data space, or NULL if unsuccessful
259	*/
260	void *
261	BlockHeapAlloc(BlockHeap *bh)
262	{
263	Block *walker = NULL;
264	dlink_node *new_node = NULL;
265
266	assert(bh != NULL);
267
268	if (bh->freeElems == 0)
269	{
270	/* Allocate new block and assign */
271	/* newblock returns 1 if unsuccessful, 0 if not */
272	if (newblock(bh))
273	{
274	/* That didn't work..try to garbage collect */
275	BlockHeapGarbageCollect(bh);
276
277	if (newblock(bh))
278	outofmemory(); /* Well that didn't work either...bail */
279	}
280	}
281
282	for (walker = bh->base; walker != NULL; walker = walker->next)
283	{
284	if (walker->freeElems > 0)
285	{
286	--bh->freeElems;
287	--walker->freeElems;
288	new_node = walker->free_list.head;
289
290	dlinkDelete(new_node, &walker->free_list);
291	assert(new_node->data != NULL);
292
293	memset(new_node->data, 0, bh->elemSize);
294	return new_node->data;
295	}
296	}
297
298	assert(0 == 1);
299	outofmemory();
300	return NULL;
301	}
302
303	/*! \brief Returns an element to the free pool, does not free()
304	* \param bh Pointer to BlockHeap containing element
305	* \param ptr Pointer to element to be "freed"
306	* \return 0 if successful, 1 if element not contained within BlockHeap
307	*/
308	int
309	BlockHeapFree(BlockHeap bh, void ptr)
310	{
311	Block *block = NULL;
312	struct MemBlock *memblock = NULL;
313
314	assert(bh != NULL);
315	assert(ptr != NULL);
316
317	memblock = (void *)((size_t)ptr - sizeof(MemBlock));
318	assert(memblock->block != NULL);
319
320	if (memblock->block == NULL)
321	outofmemory();
322
323	block = memblock->block;
324	++bh->freeElems;
325	++block->freeElems;
326	mem_frob(ptr, bh->elemSize);
327
328	dlinkAdd(ptr, &memblock->self, &block->free_list);
329	return 0;
330	}
331
332	/*! \brief Performs garbage collection on the block heap.
333	*
334	* Performs garbage collection on the block heap. Any blocks that are
335	* completely unallocated are removed from the heap. Garbage collection
336	* will \b never remove the root node of the heap.
337	*
338	* \param bh Pointer to the BlockHeap to be cleaned up
339	* \return 0 if successful, 1 if bh == NULL
340	*/
341	static int
342	BlockHeapGarbageCollect(BlockHeap *bh)
343	{
344	Block walker = NULL, last = NULL;
345
346	assert(bh != NULL);
347
348	if (bh->freeElems < bh->elemsPerBlock \|\| bh->blocksAllocated == 1)
349	{
350	/* There couldn't possibly be an entire free block. Return. */
351	return 0;
352	}
353
354	walker = bh->base;
355
356	while (walker != NULL)
357	{
358	if (walker->freeElems == bh->elemsPerBlock)
359	{
360	free_block(walker->elems, walker->alloc_size);
361
362	if (last != NULL)
363	{
364	last->next = walker->next;
365
366	if (walker != NULL)
367	free(walker);
368	walker = last->next;
369	}
370	else
371	{
372	bh->base = walker->next;
373
374	if (walker != NULL)
375	free(walker);
376	walker = bh->base;
377	}
378
379	--bh->blocksAllocated;
380	bh->freeElems -= bh->elemsPerBlock;
381	}
382	else
383	{
384	last = walker;
385	walker = walker->next;
386	}
387	}
388
389	return 0;
390	}
391
392	/*! \brief Completely free()s a BlockHeap. Use for cleanup.
393	* \param bh Pointer to the BlockHeap to be destroyed
394	* \return 0 if successful, 1 if bh == NULL
395	*/
396	int
397	BlockHeapDestroy(BlockHeap *bh)
398	{
399	Block walker = NULL, next = NULL;
400
401	if (bh == NULL)
402	return 1;
403
404	for (walker = bh->base; walker != NULL; walker = next)
405	{
406	next = walker->next;
407	free_block(walker->elems, walker->alloc_size);
408
409	if (walker != NULL)
410	free(walker);
411	}
412
413	if (heap_list == bh)
414	heap_list = bh->next;
415	else {
416	BlockHeap *prev;
417
418	for (prev = heap_list; prev->next != bh; prev = prev->next)
419	/* nothing */ ;
420	prev->next = bh->next;
421	}
422
423	free(bh);
424	return 0;
425	}
426
427	/*! \brief Returns the number of bytes being used
428	* \param bh Pointer to a BlockHeap
429	* \return Number of bytes being used
430	*/
431	static size_t
432	block_heap_get_used_mem(const BlockHeap *const bh)
433	{
434	return(((bh->blocksAllocated *
435	bh->elemsPerBlock)-bh->freeElems) *
436	(bh->elemSize + sizeof(MemBlock)));
437	}
438
439	/*! \brief Returns the number of bytes being free for further allocations
440	* \param bh Pointer to a BlockHeap
441	* \return Number of bytes being free for further allocations
442	*/
443	static size_t
444	block_heap_get_free_mem(const BlockHeap *const bh)
445	{
446	return(bh->freeElems * (bh->elemSize + sizeof(MemBlock)));
447	}
448
449	/*! \brief Returns the total number of bytes of memory belonging to a heap
450	* \param bh Pointer to a BlockHeap
451	* \return Total number of bytes of memory belonging to a heap
452	*/
453	static size_t
454	block_heap_get_size_mem(const BlockHeap *const bh)
455	{
456	return(((bh->blocksAllocated *
457	bh->elemsPerBlock)) *
458	(bh->elemSize + sizeof(MemBlock)));
459	}
460
461	/*! \brief Returns the number of elements being used.
462	* \param bh Pointer to a BlockHeap
463	* \return Number of elements being free for further allocations
464	*/
465	static unsigned int
466	block_heap_get_used_elm(const BlockHeap *const bh)
467	{
468	return((bh->blocksAllocated *
469	bh->elemsPerBlock)-bh->freeElems);
470	}
471
472	/*! \brief Returns the number of elements being free for further allocations.
473	* \param bh Pointer to a BlockHeap
474	* \return Number of elements being free for further allocations
475	*/
476	static unsigned int
477	block_heap_get_free_elm(const BlockHeap *const bh)
478	{
479	return(bh->freeElems);
480	}
481
482	/*! \brief Returns the number of total elements belonging to a heap.
483	* Includes \b free and \b used elements.
484	* \param bh Pointer to a BlockHeap
485	* \return Number of total elements belonging to a heap
486	*/
487	static unsigned int
488	block_heap_get_size_elm(const BlockHeap *const bh)
489	{
490	return(bh->blocksAllocated * bh->elemsPerBlock);
491	}
492
493	void
494	block_heap_report_stats(struct Client *client_p)
495	{
496	const BlockHeap *bh = NULL;
497
498	for (bh = heap_list; bh != NULL; bh = bh->next)
499	sendto_one(client_p, ":%s %d %s z :%s mempool: used %u/%u free %u/%u (size %u/%u)",
500	me.name, RPL_STATSDEBUG, client_p->name, bh->name,
501	block_heap_get_used_elm(bh),
502	block_heap_get_used_mem(bh),
503	block_heap_get_free_elm(bh),
504	block_heap_get_free_mem(bh),
505	block_heap_get_size_elm(bh),
506	block_heap_get_size_mem(bh));
507	}
508
509	#endif