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 int zero_fd = -1;
#endif
#endif

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

  if (zero_fd < 0)
    outofmemory();
  fd_open(zero_fd, FD_FILE, "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, zero_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 = (unsigned char *)((unsigned char *)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);
      dlinkAdd(new_node->data, new_node, &walker->used_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();

  /* Is this block really on the used list? */
  assert(dlinkFind(&memblock->block->used_list, ptr) != NULL); 

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

  dlinkDelete(&memblock->self, &block->used_list);
  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;

  if (bh == NULL)
    return 1;

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