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 = (void *)((size_t)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 |
assert(new_node->data != NULL); |
289 |
|
290 |
memset(new_node->data, 0, bh->elemSize); |
291 |
return new_node->data; |
292 |
} |
293 |
} |
294 |
|
295 |
assert(0 == 1); |
296 |
outofmemory(); |
297 |
return NULL; |
298 |
} |
299 |
|
300 |
/*! \brief Returns an element to the free pool, does not free() |
301 |
* \param bh Pointer to BlockHeap containing element |
302 |
* \param ptr Pointer to element to be "freed" |
303 |
* \return 0 if successful, 1 if element not contained within BlockHeap |
304 |
*/ |
305 |
int |
306 |
BlockHeapFree(BlockHeap *bh, void *ptr) |
307 |
{ |
308 |
Block *block = NULL; |
309 |
struct MemBlock *memblock = NULL; |
310 |
|
311 |
assert(bh != NULL); |
312 |
assert(ptr != NULL); |
313 |
|
314 |
memblock = (void *)((size_t)ptr - sizeof(MemBlock)); |
315 |
assert(memblock->block != NULL); |
316 |
|
317 |
if (memblock->block == NULL) |
318 |
outofmemory(); |
319 |
|
320 |
block = memblock->block; |
321 |
++bh->freeElems; |
322 |
++block->freeElems; |
323 |
mem_frob(ptr, bh->elemSize); |
324 |
|
325 |
dlinkAdd(ptr, &memblock->self, &block->free_list); |
326 |
return 0; |
327 |
} |
328 |
|
329 |
/*! \brief Performs garbage collection on the block heap. |
330 |
* |
331 |
* Performs garbage collection on the block heap. Any blocks that are |
332 |
* completely unallocated are removed from the heap. Garbage collection |
333 |
* will \b never remove the root node of the heap. |
334 |
* |
335 |
* \param bh Pointer to the BlockHeap to be cleaned up |
336 |
* \return 0 if successful, 1 if bh == NULL |
337 |
*/ |
338 |
static int |
339 |
BlockHeapGarbageCollect(BlockHeap *bh) |
340 |
{ |
341 |
Block *walker = NULL, *last = NULL; |
342 |
|
343 |
assert(bh != NULL); |
344 |
|
345 |
if (bh->freeElems < bh->elemsPerBlock || bh->blocksAllocated == 1) |
346 |
{ |
347 |
/* There couldn't possibly be an entire free block. Return. */ |
348 |
return 0; |
349 |
} |
350 |
|
351 |
walker = bh->base; |
352 |
|
353 |
while (walker != NULL) |
354 |
{ |
355 |
if (walker->freeElems == bh->elemsPerBlock) |
356 |
{ |
357 |
free_block(walker->elems, walker->alloc_size); |
358 |
|
359 |
if (last != NULL) |
360 |
{ |
361 |
last->next = walker->next; |
362 |
|
363 |
if (walker != NULL) |
364 |
free(walker); |
365 |
walker = last->next; |
366 |
} |
367 |
else |
368 |
{ |
369 |
bh->base = walker->next; |
370 |
|
371 |
if (walker != NULL) |
372 |
free(walker); |
373 |
walker = bh->base; |
374 |
} |
375 |
|
376 |
--bh->blocksAllocated; |
377 |
bh->freeElems -= bh->elemsPerBlock; |
378 |
} |
379 |
else |
380 |
{ |
381 |
last = walker; |
382 |
walker = walker->next; |
383 |
} |
384 |
} |
385 |
|
386 |
return 0; |
387 |
} |
388 |
|
389 |
/*! \brief Completely free()s a BlockHeap. Use for cleanup. |
390 |
* \param bh Pointer to the BlockHeap to be destroyed |
391 |
* \return 0 if successful, 1 if bh == NULL |
392 |
*/ |
393 |
int |
394 |
BlockHeapDestroy(BlockHeap *bh) |
395 |
{ |
396 |
Block *walker = NULL, *next = NULL; |
397 |
|
398 |
if (bh == NULL) |
399 |
return 1; |
400 |
|
401 |
for (walker = bh->base; walker != NULL; walker = next) |
402 |
{ |
403 |
next = walker->next; |
404 |
free_block(walker->elems, walker->alloc_size); |
405 |
|
406 |
if (walker != NULL) |
407 |
free(walker); |
408 |
} |
409 |
|
410 |
if (heap_list == bh) |
411 |
heap_list = bh->next; |
412 |
else { |
413 |
BlockHeap *prev; |
414 |
|
415 |
for (prev = heap_list; prev->next != bh; prev = prev->next) |
416 |
/* nothing */ ; |
417 |
prev->next = bh->next; |
418 |
} |
419 |
|
420 |
free(bh); |
421 |
return 0; |
422 |
} |
423 |
|
424 |
/*! \brief Returns the number of bytes being used |
425 |
* \param bh Pointer to a BlockHeap |
426 |
* \return Number of bytes being used |
427 |
*/ |
428 |
static size_t |
429 |
block_heap_get_used_mem(const BlockHeap *const bh) |
430 |
{ |
431 |
return(((bh->blocksAllocated * |
432 |
bh->elemsPerBlock)-bh->freeElems) * |
433 |
(bh->elemSize + sizeof(MemBlock))); |
434 |
} |
435 |
|
436 |
/*! \brief Returns the number of bytes being free for further allocations |
437 |
* \param bh Pointer to a BlockHeap |
438 |
* \return Number of bytes being free for further allocations |
439 |
*/ |
440 |
static size_t |
441 |
block_heap_get_free_mem(const BlockHeap *const bh) |
442 |
{ |
443 |
return(bh->freeElems * (bh->elemSize + sizeof(MemBlock))); |
444 |
} |
445 |
|
446 |
/*! \brief Returns the total number of bytes of memory belonging to a heap |
447 |
* \param bh Pointer to a BlockHeap |
448 |
* \return Total number of bytes of memory belonging to a heap |
449 |
*/ |
450 |
static size_t |
451 |
block_heap_get_size_mem(const BlockHeap *const bh) |
452 |
{ |
453 |
return(((bh->blocksAllocated * |
454 |
bh->elemsPerBlock)) * |
455 |
(bh->elemSize + sizeof(MemBlock))); |
456 |
} |
457 |
|
458 |
/*! \brief Returns the number of elements being used. |
459 |
* \param bh Pointer to a BlockHeap |
460 |
* \return Number of elements being free for further allocations |
461 |
*/ |
462 |
static unsigned int |
463 |
block_heap_get_used_elm(const BlockHeap *const bh) |
464 |
{ |
465 |
return((bh->blocksAllocated * |
466 |
bh->elemsPerBlock)-bh->freeElems); |
467 |
} |
468 |
|
469 |
/*! \brief Returns the number of elements being free for further allocations. |
470 |
* \param bh Pointer to a BlockHeap |
471 |
* \return Number of elements being free for further allocations |
472 |
*/ |
473 |
static unsigned int |
474 |
block_heap_get_free_elm(const BlockHeap *const bh) |
475 |
{ |
476 |
return(bh->freeElems); |
477 |
} |
478 |
|
479 |
/*! \brief Returns the number of total elements belonging to a heap. |
480 |
* Includes \b free and \b used elements. |
481 |
* \param bh Pointer to a BlockHeap |
482 |
* \return Number of total elements belonging to a heap |
483 |
*/ |
484 |
static unsigned int |
485 |
block_heap_get_size_elm(const BlockHeap *const bh) |
486 |
{ |
487 |
return(bh->blocksAllocated * bh->elemsPerBlock); |
488 |
} |
489 |
|
490 |
void |
491 |
block_heap_report_stats(struct Client *client_p) |
492 |
{ |
493 |
const BlockHeap *bh = NULL; |
494 |
|
495 |
for (bh = heap_list; bh != NULL; bh = bh->next) |
496 |
sendto_one(client_p, ":%s %d %s z :%s mempool: used %u/%u free %u/%u (size %u/%u)", |
497 |
me.name, RPL_STATSDEBUG, client_p->name, bh->name, |
498 |
block_heap_get_used_elm(bh), |
499 |
block_heap_get_used_mem(bh), |
500 |
block_heap_get_free_elm(bh), |
501 |
block_heap_get_free_mem(bh), |
502 |
block_heap_get_size_elm(bh), |
503 |
block_heap_get_size_mem(bh)); |
504 |
} |