2 * ircd-ratbox: A slightly useful ircd.
3 * balloc.c: A block allocator.
5 * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
6 * Copyright (C) 1996-2002 Hybrid Development Team
7 * Copyright (C) 2002-2006 ircd-ratbox development team
9 * Below are the orignal headers from the old blalloc.c
12 * Owner: Wohali (Joan Touzet)
14 * Modified 2001/11/29 for mmap() support by Aaron Sethman <androsyn@ratbox.org>
16 * This program is free software; you can redistribute it and/or modify
17 * it under the terms of the GNU General Public License as published by
18 * the Free Software Foundation; either version 2 of the License, or
19 * (at your option) any later version.
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
26 * You should have received a copy of the GNU General Public License
27 * along with this program; if not, write to the Free Software
28 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
31 * $Id: balloc.c 25048 2008-01-23 18:34:02Z androsyn $
35 * About the block allocator
37 * Basically we have three ways of getting memory off of the operating
38 * system. Below are this list of methods and the order of preference.
40 * 1. mmap() anonymous pages with the MMAP_ANON flag.
41 * 2. mmap() via the /dev/zero trick.
42 * 3. HeapCreate/HeapAlloc (on win32)
45 * The advantages of 1 and 2 are this. We can munmap() the pages which will
46 * return the pages back to the operating system, thus reducing the size
47 * of the process as the memory is unused. malloc() on many systems just keeps
48 * a heap of memory to itself, which never gets given back to the OS, except on
49 * exit. This of course is bad, if say we have an event that causes us to allocate
50 * say, 200MB of memory, while our normal memory consumption would be 15MB. In the
51 * malloc() case, the amount of memory allocated to our process never goes down, as
52 * malloc() has it locked up in its heap. With the mmap() method, we can munmap()
53 * the block and return it back to the OS, thus causing our memory consumption to go
54 * down after we no longer need it.
59 #include <libratbox_config.h>
60 #include <ratbox_lib.h>
62 #ifdef HAVE_MMAP /* We've got mmap() that is good */
67 #define MAP_ANON MAP_ANONYMOUS
72 /* status information for an allocated block in heap */
77 unsigned long free_count
;
78 void *elems
; /* Points to allocated memory */
80 typedef struct rb_heap_block rb_heap_block
;
82 struct rb_heap_memblock
87 char data
[1]; /* stub pointer..this is ugly */
91 typedef struct rb_heap_memblock rb_heap_memblock
;
93 /* information for the root node of the heap */
97 size_t elemSize
; /* Size of each element to be stored */
98 unsigned long elemsPerBlock
; /* Number of elements per block */
99 rb_dlink_list block_list
;
100 rb_dlink_list free_list
;
105 static int newblock(rb_bh
* bh
);
106 static void rb_bh_gc_event(void *unused
);
107 #endif /* !NOBALLOC */
108 static rb_dlink_list
*heap_lists
;
111 static HANDLE block_heap
;
114 #define rb_bh_fail(x) _rb_bh_fail(x, __FILE__, __LINE__)
117 _rb_bh_fail(const char *reason
, const char *file
, int line
)
119 rb_lib_log("rb_heap_blockheap failure: %s (%s:%d)", reason
, file
, line
);
125 * static inline void free_block(void *ptr, size_t size)
127 * Inputs: The block and its size
129 * Side Effects: Returns memory for the block back to the OS
132 free_block(void *ptr
, size_t size
)
138 HeapFree(block_heap
, 0, ptr
);
144 #endif /* !NOBALLOC */
147 * void rb_init_bh(void)
151 * Side Effects: Initializes the block heap
157 heap_lists
= rb_malloc(sizeof(rb_dlink_list
));
160 block_heap
= HeapCreate(HEAP_NO_SERIALIZE
, 0, 0);
162 rb_event_addish("rb_bh_gc_event", rb_bh_gc_event
, NULL
, 300);
163 #endif /* !NOBALLOC */
168 * static inline void *get_block(size_t size)
170 * Input: Size of block to allocate
171 * Output: Pointer to new block
175 get_block(size_t size
)
180 ptr
= mmap(NULL
, size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
| MAP_ANON
, -1, 0);
183 zero_fd
= open("/dev/zero", O_RDWR
);
185 rb_bh_fail("Failed opening /dev/zero");
186 ptr
= mmap(NULL
, size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
, zero_fd
, 0);
188 #endif /* MAP_ANON */
189 if(ptr
== MAP_FAILED
)
193 ptr
= HeapAlloc(block_heap
, 0, size
);
203 rb_bh_gc_event(void *unused
)
206 RB_DLINK_FOREACH(ptr
, heap_lists
->head
)
212 /* ************************************************************************ */
213 /* FUNCTION DOCUMENTATION: */
216 /* Allocates a new block for addition to a blockheap */
218 /* bh (IN): Pointer to parent blockheap. */
220 /* 0 if successful, 1 if not */
221 /* ************************************************************************ */
230 /* Setup the initial data structure. */
231 b
= rb_malloc(sizeof(rb_heap_block
));
233 b
->alloc_size
= bh
->elemsPerBlock
* (bh
->elemSize
+ sizeof(rb_heap_block
*));
235 b
->elems
= get_block(b
->alloc_size
);
236 if(unlikely(b
->elems
== NULL
))
240 offset
= (rb_uintptr_t
)b
->elems
;
241 /* Setup our blocks now */
242 for (i
= 0; i
< bh
->elemsPerBlock
; i
++, offset
+= (bh
->elemSize
+ sizeof(rb_heap_block
*)))
244 rb_heap_memblock
*memblock
= (rb_heap_memblock
*)offset
;
246 rb_dlinkAdd(memblock
, &memblock
->ndata
.node
, &bh
->free_list
);
248 rb_dlinkAdd(b
, &b
->node
, &bh
->block_list
);
249 b
->free_count
= bh
->elemsPerBlock
;
252 #endif /* !NOBALLOC */
254 /* ************************************************************************ */
255 /* FUNCTION DOCUMENTATION: */
258 /* Creates a new blockheap from which smaller blocks can be allocated. */
259 /* Intended to be used instead of multiple calls to malloc() when */
260 /* performance is an issue. */
262 /* elemsize (IN): Size of the basic element to be stored */
263 /* elemsperblock (IN): Number of elements to be stored in a single block */
264 /* of memory. When the blockheap runs out of free memory, it will */
265 /* allocate elemsize * elemsperblock more. */
267 /* Pointer to new rb_bh, or NULL if unsuccessful */
268 /* ************************************************************************ */
270 rb_bh_create(size_t elemsize
, int elemsperblock
, const char *desc
)
273 lrb_assert(elemsize
> 0 && elemsperblock
> 0);
274 lrb_assert(elemsize
>= sizeof(rb_dlink_node
));
275 /* Catch idiotic requests up front */
276 if((elemsize
<= 0) || (elemsperblock
<= 0))
278 rb_bh_fail("Attempting to rb_bh_create idiotic sizes");
281 if(elemsize
< sizeof(rb_dlink_node
))
282 rb_bh_fail("Attempt to rb_bh_create smaller than sizeof(rb_dlink_node)");
284 /* Allocate our new rb_bh */
285 bh
= rb_malloc(sizeof(rb_bh
));
288 if((elemsize
% sizeof(void *)) != 0)
290 /* Pad to even pointer boundary */
291 elemsize
+= sizeof(void *);
292 elemsize
&= ~(sizeof(void *) - 1);
294 #endif /* !NOBALLOC */
296 bh
->elemSize
= elemsize
;
297 bh
->elemsPerBlock
= elemsperblock
;
299 bh
->desc
= rb_strdup(desc
);
302 /* Be sure our malloc was successful */
307 rb_lib_log("newblock() failed");
308 rb_outofmemory(); /* die.. out of memory */
310 #endif /* !NOBALLOC */
314 rb_bh_fail("bh == NULL when it shouldn't be");
316 rb_dlinkAdd(bh
, &bh
->hlist
, heap_lists
);
320 /* ************************************************************************ */
321 /* FUNCTION DOCUMENTATION: */
324 /* Returns a pointer to a struct within our rb_bh that's free for */
327 /* bh (IN): Pointer to the Blockheap. */
329 /* Pointer to a structure (void *), or NULL if unsuccessful. */
330 /* ************************************************************************ */
333 rb_bh_alloc(rb_bh
* bh
)
336 rb_dlink_node
*new_node
;
337 rb_heap_memblock
*memblock
;
339 lrb_assert(bh
!= NULL
);
340 if(unlikely(bh
== NULL
))
342 rb_bh_fail("Cannot allocate if bh == NULL");
346 return(rb_malloc(bh
->elemSize
));
348 if(bh
->free_list
.head
== NULL
)
350 /* Allocate new block and assign */
351 /* newblock returns 1 if unsuccessful, 0 if not */
353 if(unlikely(newblock(bh
)))
355 rb_lib_log("newblock() failed");
356 rb_outofmemory(); /* Well that didn't work either...bail */
358 if(bh
->free_list
.head
== NULL
)
360 rb_lib_log("out of memory after newblock()...");
365 new_node
= bh
->free_list
.head
;
366 memblock
= new_node
->data
;
367 rb_dlinkDelete(new_node
, &bh
->free_list
);
368 memblock
->block
->free_count
--;
369 memset((void *)memblock
->ndata
.data
, 0, bh
->elemSize
);
370 return((void *)memblock
->ndata
.data
);
375 /* ************************************************************************ */
376 /* FUNCTION DOCUMENTATION: */
379 /* Returns an element to the free pool, does not free() */
381 /* bh (IN): Pointer to rb_bh containing element */
382 /* ptr (in): Pointer to element to be "freed" */
384 /* 0 if successful, 1 if element not contained within rb_bh. */
385 /* ************************************************************************ */
387 rb_bh_free(rb_bh
* bh
, void *ptr
)
390 rb_heap_memblock
*memblock
;
392 lrb_assert(bh
!= NULL
);
393 lrb_assert(ptr
!= NULL
);
395 if(unlikely(bh
== NULL
))
397 rb_lib_log("balloc.c:rb_bhFree() bh == NULL");
401 if(unlikely(ptr
== NULL
))
403 rb_lib_log("balloc.rb_bhFree() ptr == NULL");
410 memblock
= (rb_heap_memblock
*) ((uintptr_t)ptr
- sizeof(rb_heap_block
*));
412 if(unlikely(!((uintptr_t)ptr
>= (uintptr_t)memblock
->block
->elems
&& (uintptr_t)ptr
< (uintptr_t)memblock
->block
->elems
+ (uintptr_t)memblock
->block
->alloc_size
)))
414 rb_bh_fail("rb_bh_free() bogus pointer");
416 memblock
->block
->free_count
++;
417 rb_dlinkAdd(memblock
, &memblock
->ndata
.node
, &bh
->free_list
);
418 #endif /* !NOBALLOC */
423 /* ************************************************************************ */
424 /* FUNCTION DOCUMENTATION: */
427 /* Completely free()s a rb_bh. Use for cleanup. */
429 /* bh (IN): Pointer to the rb_bh to be destroyed. */
431 /* 0 if successful, 1 if bh == NULL */
432 /* ************************************************************************ */
434 rb_bh_destroy(rb_bh
* bh
)
437 rb_dlink_node
*ptr
, *next
;
444 RB_DLINK_FOREACH_SAFE(ptr
, next
, bh
->block_list
.head
)
447 free_block(b
->elems
, b
->alloc_size
);
450 #endif /* !NOBALLOC */
452 rb_dlinkDelete(&bh
->hlist
, heap_lists
);
460 rb_bh_usage(rb_bh
* bh
, size_t * bused
, size_t * bfree
, size_t * bmemusage
, const char **desc
)
462 size_t used
, freem
, memusage
;
469 freem
= rb_dlink_list_length(&bh
->free_list
);
470 used
= (rb_dlink_list_length(&bh
->block_list
) * bh
->elemsPerBlock
) - freem
;
471 memusage
= used
* (bh
->elemSize
+ sizeof(void *));
476 if(bmemusage
!= NULL
)
477 *bmemusage
= memusage
;
482 void rb_bh_usage_all(rb_bh_usage_cb
*cb
, void *data
)
486 size_t used
, freem
, memusage
, heapalloc
;
487 static const char *unnamed
= "(unnamed_heap)";
488 const char *desc
= unnamed
;
493 RB_DLINK_FOREACH(ptr
, heap_lists
->head
)
495 bh
= (rb_bh
*)ptr
->data
;
496 freem
= rb_dlink_list_length(&bh
->free_list
);
497 used
= (rb_dlink_list_length(&bh
->block_list
) * bh
->elemsPerBlock
) - freem
;
498 memusage
= used
* (bh
->elemSize
+ sizeof(void *));
499 heapalloc
= (freem
+ used
) * (bh
->elemSize
+ sizeof(void *));
502 cb(used
, freem
, memusage
, heapalloc
, desc
, data
);
508 rb_bh_total_usage(size_t *total_alloc
, size_t *total_used
)
511 size_t total_memory
= 0, used_memory
= 0, used
, freem
;
514 RB_DLINK_FOREACH(ptr
, heap_lists
->head
)
516 bh
= (rb_bh
*)ptr
->data
;
517 freem
= rb_dlink_list_length(&bh
->free_list
);
518 used
= (rb_dlink_list_length(&bh
->block_list
) * bh
->elemsPerBlock
) - freem
;
519 used_memory
+= used
* (bh
->elemSize
+ sizeof(void *));
520 total_memory
+= (freem
+ used
) * (bh
->elemSize
+ sizeof(void *));
523 if(total_alloc
!= NULL
)
524 *total_alloc
= total_memory
;
525 if(total_used
!= NULL
)
526 *total_used
= used_memory
;
534 rb_dlink_node
*ptr
, *next
;
540 /* somebody is smoking some craq..(probably lee, but don't tell him that) */
544 if((rb_dlink_list_length(&bh
->free_list
) < bh
->elemsPerBlock
) || rb_dlink_list_length(&bh
->block_list
) == 1)
546 /* There couldn't possibly be an entire free block. Return. */
550 RB_DLINK_FOREACH_SAFE(ptr
, next
, bh
->block_list
.head
)
553 if(rb_dlink_list_length(&bh
->block_list
) == 1)
556 if(b
->free_count
== bh
->elemsPerBlock
)
558 /* i'm seriously going to hell for this.. */
560 offset
= (uintptr_t)b
->elems
;
561 for (i
= 0; i
< bh
->elemsPerBlock
; i
++, offset
+= ((uintptr_t)bh
->elemSize
+ sizeof(rb_heap_memblock
*)))
563 rb_heap_memblock
*memblock
= (rb_heap_memblock
*)offset
;
564 rb_dlinkDelete(&memblock
->ndata
.node
, &bh
->free_list
);
566 rb_dlinkDelete(&b
->node
, &bh
->block_list
);
567 free_block(b
->elems
, b
->alloc_size
);
574 #endif /* !NOBALLOC */