ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/ircd-hybrid-7.2/src/balloc.c
Revision: 368
Committed: Mon Jan 9 23:41:29 2006 UTC (18 years, 2 months ago) by michael
Content type: text/x-csrc
File size: 13243 byte(s)
Log Message:
- Forgot the half of the fix

File Contents

# 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 #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 fde_t dpfd;
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 int zero_fd = open("/dev/zero", O_RDWR);
112
113 if (zero_fd < 0)
114 outofmemory();
115 fd_open(&dpfd, zero_fd, 0, "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, dpfd.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 }

Properties

Name Value
svn:eol-style native
svn:keywords Id Revision