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