ircd-hybrid-7.2/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"
#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));
}
Revision:	912
Committed:	Wed Nov 7 22:47:44 2007 UTC (16 years, 5 months ago) by michael
Content type:	text/x-csrc
File size:	12991 byte(s)
Log Message:	- Implemented libtool-ltdl. Only shared modules are supported currently - Several build fixes and cleanups. ircd now builds and runs without any problems - Added back all files to SVN that are needed to built the daemon I really don't want to force other people that want to test the snapshots or svn versions to install yyacc, lex, automake, autoconf and libtool... No problem having required files in svn - Removed some automake maintainer stuff which is kinda useless for us
#	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	#ifdef HAVE_MMAP /* We've got mmap() that is good */
56	#include <sys/mman.h>
57
58	/* HP-UX sucks */
59	#ifdef MAP_ANONYMOUS
60	#ifndef MAP_ANON
61	#define MAP_ANON MAP_ANONYMOUS
62	#endif
63	#endif /* MAP_ANONYMOUS */
64	#endif
65
66	#include "ircd.h"
67	#include "balloc.h"
68	#include "irc_string.h"
69	#include "tools.h"
70	#include "client.h"
71	#include "send.h"
72	#include "numeric.h"
73	#include "fdlist.h"
74	#include "event.h"
75
76
77	static BlockHeap *heap_list = NULL;
78
79	static int BlockHeapGarbageCollect(BlockHeap *);
80	static void heap_garbage_collection(void *);
81
82	/*! \brief Returns memory for the block back to either the malloc heap
83	* in case of !HAVE_MMAP, or back to the OS otherwise.
84	* \param ptr Pointer to memory to be freed
85	* \param size The size of the memory space
86	*/
87	static inline void
88	free_block(void *ptr, size_t size)
89	{
90	#ifdef HAVE_MMAP
91	munmap(ptr, size);
92	#else
93	free(ptr);
94	#endif
95	}
96
97	#ifdef HAVE_MMAP
98	#ifndef MAP_ANON /* But we cannot mmap() anonymous pages */
99	/* So we mmap() /dev/zero, which is just as good */
100	static fde_t dpfd;
101	#endif
102	#endif
103
104	/*! \brief Opens /dev/zero and saves the file handle for
105	* future allocations.
106	*/
107	void
108	initBlockHeap(void)
109	{
110	#ifdef HAVE_MMAP
111	#ifndef MAP_ANON
112	int zero_fd = open("/dev/zero", O_RDWR);
113
114	if (zero_fd < 0)
115	outofmemory();
116	fd_open(&dpfd, zero_fd, 0, "Anonymous mmap()");
117	#endif
118	eventAdd("heap_garbage_collection", &heap_garbage_collection, NULL, 119);
119	#endif
120	}
121
122	/*!
123	* \param size Size of block to allocate
124	* \return Address pointer to allocated data space
125	*/
126	static inline void *
127	get_block(size_t size)
128	{
129	#ifdef HAVE_MMAP
130	void *ptr = NULL;
131
132	#ifndef MAP_ANON
133	ptr = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE, dpfd.fd, 0);
134	#else
135	ptr = mmap(NULL, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE \| MAP_ANON, -1, 0);
136	#endif
137	return ptr == MAP_FAILED ? NULL : ptr;
138	#else
139	return malloc(size);
140	#endif
141	}
142
143	static void
144	heap_garbage_collection(void *arg)
145	{
146	BlockHeap *bh;
147
148	for (bh = heap_list; bh != NULL; bh = bh->next)
149	BlockHeapGarbageCollect(bh);
150	}
151
152	/*! \brief Allocates a new block for addition to a blockheap
153	* \param bh Pointer to parent blockheap
154	* \return 0 if successful, 1 if not
155	*/
156	static int
157	newblock(BlockHeap *bh)
158	{
159	MemBlock *newblk = NULL;
160	Block *b = NULL;
161	int i = 0;
162	void *offset = NULL;
163
164	/* Setup the initial data structure. */
165	if ((b = calloc(1, sizeof(Block))) == NULL)
166	return 1;
167
168	b->freeElems = bh->elemsPerBlock;
169	b->next = bh->base;
170	b->alloc_size = bh->elemsPerBlock * (bh->elemSize + sizeof(MemBlock));
171	b->elems = get_block(b->alloc_size);
172
173	if (b->elems == NULL)
174	return 1;
175
176	offset = b->elems;
177
178	/* Setup our blocks now */
179	for (; i < bh->elemsPerBlock; ++i)
180	{
181	void *data;
182
183	newblk = offset;
184	newblk->block = b;
185	data = (void *)((size_t)offset + sizeof(MemBlock));
186
187	dlinkAdd(data, &newblk->self, &b->free_list);
188	offset = (void *)((size_t)offset + bh->elemSize + sizeof(MemBlock));
189	}
190
191	++bh->blocksAllocated;
192	bh->freeElems += bh->elemsPerBlock;
193	bh->base = b;
194
195	return 0;
196	}
197
198	/*! \brief Creates a new blockheap
199	*
200	* Creates a new blockheap from which smaller blocks can be allocated.
201	* Intended to be used instead of multiple calls to malloc() when
202	* performance is an issue.
203	*
204	* \param name Name of the blockheap
205	* \param elemsize Size of the basic element to be stored
206	* \param elemsperblock Number of elements to be stored in a single block of
207	* memory. When the blockheap runs out of free memory,
208	* it will allocate elemsize * elemsperblock more.
209	* \return Pointer to new BlockHeap, or NULL if unsuccessful
210	*/
211	BlockHeap *
212	BlockHeapCreate(const char *const name, size_t elemsize, int elemsperblock)
213	{
214	BlockHeap *bh = NULL;
215	assert(elemsize > 0 && elemsperblock > 0);
216
217	/* Catch idiotic requests up front */
218	if ((elemsize <= 0) \|\| (elemsperblock <= 0))
219	outofmemory(); /* die.. out of memory */
220
221	/* Allocate our new BlockHeap */
222	if ((bh = calloc(1, sizeof(BlockHeap))) == NULL)
223	outofmemory(); /* die.. out of memory */
224
225	if ((elemsize % sizeof(void *)) != 0)
226	{
227	/* Pad to even pointer boundary */
228	elemsize += sizeof(void *);
229	elemsize &= ~(sizeof(void *) - 1);
230	}
231
232	bh->name = name;
233	bh->elemSize = elemsize;
234	bh->elemsPerBlock = elemsperblock;
235
236	/* Be sure our malloc was successful */
237	if (newblock(bh))
238	{
239	if (bh != NULL)
240	free(bh);
241
242	outofmemory(); /* die.. out of memory */
243	}
244
245	assert(bh);
246
247	bh->next = heap_list;
248	heap_list = bh;
249
250	return bh;
251	}
252
253	/*! \brief Returns a pointer to a struct within our BlockHeap that's free for
254	* the taking.
255	* \param bh Pointer to the Blockheap
256	* \return Address pointer to allocated data space, or NULL if unsuccessful
257	*/
258	void *
259	BlockHeapAlloc(BlockHeap *bh)
260	{
261	Block *walker = NULL;
262	dlink_node *new_node = NULL;
263
264	assert(bh != NULL);
265
266	if (bh->freeElems == 0)
267	{
268	/* Allocate new block and assign */
269	/* newblock returns 1 if unsuccessful, 0 if not */
270	if (newblock(bh))
271	{
272	/* That didn't work..try to garbage collect */
273	BlockHeapGarbageCollect(bh);
274
275	if (newblock(bh))
276	outofmemory(); /* Well that didn't work either...bail */
277	}
278	}
279
280	for (walker = bh->base; walker != NULL; walker = walker->next)
281	{
282	if (walker->freeElems > 0)
283	{
284	--bh->freeElems;
285	--walker->freeElems;
286	new_node = walker->free_list.head;
287
288	dlinkDelete(new_node, &walker->free_list);
289	assert(new_node->data != NULL);
290
291	memset(new_node->data, 0, bh->elemSize);
292	return new_node->data;
293	}
294	}
295
296	assert(0 == 1);
297	outofmemory();
298	return NULL;
299	}
300
301	/*! \brief Returns an element to the free pool, does not free()
302	* \param bh Pointer to BlockHeap containing element
303	* \param ptr Pointer to element to be "freed"
304	* \return 0 if successful, 1 if element not contained within BlockHeap
305	*/
306	int
307	BlockHeapFree(BlockHeap bh, void ptr)
308	{
309	Block *block = NULL;
310	struct MemBlock *memblock = NULL;
311
312	assert(bh != NULL);
313	assert(ptr != NULL);
314
315	memblock = (void *)((size_t)ptr - sizeof(MemBlock));
316	assert(memblock->block != NULL);
317
318	if (memblock->block == NULL)
319	outofmemory();
320
321	block = memblock->block;
322	++bh->freeElems;
323	++block->freeElems;
324	mem_frob(ptr, bh->elemSize);
325
326	dlinkAdd(ptr, &memblock->self, &block->free_list);
327	return 0;
328	}
329
330	/*! \brief Performs garbage collection on the block heap.
331	*
332	* Performs garbage collection on the block heap. Any blocks that are
333	* completely unallocated are removed from the heap. Garbage collection
334	* will \b never remove the root node of the heap.
335	*
336	* \param bh Pointer to the BlockHeap to be cleaned up
337	* \return 0 if successful, 1 if bh == NULL
338	*/
339	static int
340	BlockHeapGarbageCollect(BlockHeap *bh)
341	{
342	Block walker = NULL, last = NULL;
343
344	assert(bh != NULL);
345
346	if (bh->freeElems < bh->elemsPerBlock \|\| bh->blocksAllocated == 1)
347	{
348	/* There couldn't possibly be an entire free block. Return. */
349	return 0;
350	}
351
352	walker = bh->base;
353
354	while (walker != NULL)
355	{
356	if (walker->freeElems == bh->elemsPerBlock)
357	{
358	free_block(walker->elems, walker->alloc_size);
359
360	if (last != NULL)
361	{
362	last->next = walker->next;
363
364	if (walker != NULL)
365	free(walker);
366	walker = last->next;
367	}
368	else
369	{
370	bh->base = walker->next;
371
372	if (walker != NULL)
373	free(walker);
374	walker = bh->base;
375	}
376
377	--bh->blocksAllocated;
378	bh->freeElems -= bh->elemsPerBlock;
379	}
380	else
381	{
382	last = walker;
383	walker = walker->next;
384	}
385	}
386
387	return 0;
388	}
389
390	/*! \brief Completely free()s a BlockHeap. Use for cleanup.
391	* \param bh Pointer to the BlockHeap to be destroyed
392	* \return 0 if successful, 1 if bh == NULL
393	*/
394	int
395	BlockHeapDestroy(BlockHeap *bh)
396	{
397	Block walker = NULL, next = NULL;
398
399	if (bh == NULL)
400	return 1;
401
402	for (walker = bh->base; walker != NULL; walker = next)
403	{
404	next = walker->next;
405	free_block(walker->elems, walker->alloc_size);
406
407	if (walker != NULL)
408	free(walker);
409	}
410
411	if (heap_list == bh)
412	heap_list = bh->next;
413	else {
414	BlockHeap *prev;
415
416	for (prev = heap_list; prev->next != bh; prev = prev->next)
417	/* nothing */ ;
418	prev->next = bh->next;
419	}
420
421	free(bh);
422	return 0;
423	}
424
425	/*! \brief Returns the number of bytes being used
426	* \param bh Pointer to a BlockHeap
427	* \return Number of bytes being used
428	*/
429	static size_t
430	block_heap_get_used_mem(const BlockHeap *const bh)
431	{
432	return(((bh->blocksAllocated *
433	bh->elemsPerBlock)-bh->freeElems) *
434	(bh->elemSize + sizeof(MemBlock)));
435	}
436
437	/*! \brief Returns the number of bytes being free for further allocations
438	* \param bh Pointer to a BlockHeap
439	* \return Number of bytes being free for further allocations
440	*/
441	static size_t
442	block_heap_get_free_mem(const BlockHeap *const bh)
443	{
444	return(bh->freeElems * (bh->elemSize + sizeof(MemBlock)));
445	}
446
447	/*! \brief Returns the total number of bytes of memory belonging to a heap
448	* \param bh Pointer to a BlockHeap
449	* \return Total number of bytes of memory belonging to a heap
450	*/
451	static size_t
452	block_heap_get_size_mem(const BlockHeap *const bh)
453	{
454	return(((bh->blocksAllocated *
455	bh->elemsPerBlock)) *
456	(bh->elemSize + sizeof(MemBlock)));
457	}
458
459	/*! \brief Returns the number of elements being used.
460	* \param bh Pointer to a BlockHeap
461	* \return Number of elements being free for further allocations
462	*/
463	static unsigned int
464	block_heap_get_used_elm(const BlockHeap *const bh)
465	{
466	return((bh->blocksAllocated *
467	bh->elemsPerBlock)-bh->freeElems);
468	}
469
470	/*! \brief Returns the number of elements being free for further allocations.
471	* \param bh Pointer to a BlockHeap
472	* \return Number of elements being free for further allocations
473	*/
474	static unsigned int
475	block_heap_get_free_elm(const BlockHeap *const bh)
476	{
477	return(bh->freeElems);
478	}
479
480	/*! \brief Returns the number of total elements belonging to a heap.
481	* Includes \b free and \b used elements.
482	* \param bh Pointer to a BlockHeap
483	* \return Number of total elements belonging to a heap
484	*/
485	static unsigned int
486	block_heap_get_size_elm(const BlockHeap *const bh)
487	{
488	return(bh->blocksAllocated * bh->elemsPerBlock);
489	}
490
491	void
492	block_heap_report_stats(struct Client *client_p)
493	{
494	const BlockHeap *bh = NULL;
495
496	for (bh = heap_list; bh != NULL; bh = bh->next)
497	sendto_one(client_p, ":%s %d %s z :%s mempool: used %u/%u free %u/%u (size %u/%u)",
498	me.name, RPL_STATSDEBUG, client_p->name, bh->name,
499	block_heap_get_used_elm(bh),
500	block_heap_get_used_mem(bh),
501	block_heap_get_free_elm(bh),
502	block_heap_get_free_mem(bh),
503	block_heap_get_size_elm(bh),
504	block_heap_get_size_mem(bh));
505	}