philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 1 | /*------------------------------------------------------------------------*/ |
| 2 | /*--- A simple pool (memory) allocator implementation. m_poolalloc.c --- */ |
| 3 | /*------------------------------------------------------------------------*/ |
| 4 | /* |
| 5 | This file is part of Valgrind, a dynamic binary instrumentation |
| 6 | framework. |
| 7 | |
sewardj | b3a1e4b | 2015-08-21 11:32:26 +0000 | [diff] [blame] | 8 | Copyright (C) 2011-2015 OpenWorks LLP info@open-works.co.uk, |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 9 | Philippe Waroquiers philippe.waroquiers@skynet.be |
| 10 | |
| 11 | This program is free software; you can redistribute it and/or |
| 12 | modify it under the terms of the GNU General Public License as |
| 13 | published by the Free Software Foundation; either version 2 of the |
| 14 | License, or (at your option) any later version. |
| 15 | |
| 16 | This program is distributed in the hope that it will be useful, but |
| 17 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 19 | General Public License for more details. |
| 20 | |
| 21 | You should have received a copy of the GNU General Public License |
| 22 | along with this program; if not, write to the Free Software |
| 23 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 24 | 02111-1307, USA. |
| 25 | |
| 26 | The GNU General Public License is contained in the file COPYING. |
| 27 | */ |
| 28 | |
| 29 | #include "pub_core_basics.h" |
| 30 | #include "pub_core_libcbase.h" |
| 31 | #include "pub_core_libcassert.h" |
florian | c91f584 | 2013-09-15 10:42:26 +0000 | [diff] [blame] | 32 | #include "pub_core_xarray.h" |
| 33 | #include "pub_core_poolalloc.h" /* self */ |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 34 | |
| 35 | struct _PoolAlloc { |
| 36 | UWord nrRef; /* nr reference to this pool allocator */ |
| 37 | UWord elemSzB; /* element size */ |
| 38 | UWord nPerPool; /* # elems per pool */ |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 39 | void* (*alloc_fn)(const HChar*, SizeT); /* pool allocator */ |
| 40 | const HChar* cc; /* pool allocator's cost centre */ |
| 41 | void (*free_fn)(void*); /* pool allocator's free-er */ |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 42 | /* XArray of void* (pointers to pools). The pools themselves. |
| 43 | Each element is a pointer to a block of size (elemSzB * |
| 44 | nPerPool) bytes. */ |
| 45 | XArray* pools; |
| 46 | /* next free element. Is a pointer to an element in one of the |
| 47 | pools pointed to by .pools */ |
| 48 | void* nextFree; |
| 49 | }; |
| 50 | |
| 51 | PoolAlloc* VG_(newPA) ( UWord elemSzB, |
| 52 | UWord nPerPool, |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 53 | void* (*alloc_fn)(const HChar*, SizeT), |
florian | 54fe202 | 2012-10-27 23:07:42 +0000 | [diff] [blame] | 54 | const HChar* cc, |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 55 | void (*free_fn)(void*) ) |
| 56 | { |
| 57 | PoolAlloc* pa; |
| 58 | vg_assert(0 == (elemSzB % sizeof(UWord))); |
| 59 | vg_assert(elemSzB >= sizeof(UWord)); |
| 60 | vg_assert(nPerPool >= 100); /* let's say */ |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 61 | vg_assert(alloc_fn); |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 62 | vg_assert(cc); |
| 63 | vg_assert(free_fn); |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 64 | pa = alloc_fn(cc, sizeof(*pa)); |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 65 | VG_(memset)(pa, 0, sizeof(*pa)); |
| 66 | pa->nrRef = 0; |
| 67 | pa->elemSzB = elemSzB; |
| 68 | pa->nPerPool = nPerPool; |
| 69 | pa->pools = NULL; |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 70 | pa->alloc_fn = alloc_fn; |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 71 | pa->cc = cc; |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 72 | pa->free_fn = free_fn; |
| 73 | pa->pools = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(void*) ); |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 74 | pa->nextFree = NULL; |
florian | 91ed8cc | 2014-09-15 18:50:17 +0000 | [diff] [blame] | 75 | |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 76 | return pa; |
| 77 | } |
| 78 | |
| 79 | void VG_(deletePA) ( PoolAlloc* pa) |
| 80 | { |
| 81 | Word i; |
| 82 | vg_assert(pa->nrRef == 0); |
| 83 | for (i = 0; i < VG_(sizeXA) (pa->pools); i++) |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 84 | pa->free_fn (*(UWord **)VG_(indexXA) ( pa->pools, i )); |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 85 | VG_(deleteXA) (pa->pools); |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 86 | pa->free_fn (pa); |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 87 | } |
| 88 | |
| 89 | /* The freelist is empty. Allocate a new pool and put all the new |
| 90 | elements in it onto the freelist. */ |
| 91 | __attribute__((noinline)) |
| 92 | static void pal_add_new_pool ( PoolAlloc* pa ) |
| 93 | { |
| 94 | Word i; |
| 95 | UWord* pool; |
| 96 | vg_assert(pa); |
| 97 | vg_assert(pa->nextFree == NULL); |
florian | 6a65074 | 2014-09-14 22:44:53 +0000 | [diff] [blame] | 98 | pool = pa->alloc_fn( pa->cc, pa->elemSzB * pa->nPerPool ); |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 99 | /* extend the freelist through the new pool. Place the freelist |
| 100 | pointer in the first word of each element. That's why the |
| 101 | element size must be at least one word. */ |
| 102 | for (i = pa->nPerPool-1; i >= 0; i--) { |
| 103 | UChar* elemC = ((UChar*)pool) + i * pa->elemSzB; |
| 104 | UWord* elem = (UWord*)elemC; |
| 105 | vg_assert(0 == (((UWord)elem) % sizeof(UWord))); |
| 106 | *elem = (UWord)pa->nextFree; |
| 107 | pa->nextFree = elem; |
| 108 | } |
| 109 | /* and add to our collection of pools */ |
| 110 | VG_(addToXA)( pa->pools, &pool ); |
| 111 | } |
| 112 | |
philippe | 71ed3c9 | 2015-05-17 19:32:42 +0000 | [diff] [blame] | 113 | UWord VG_(sizePA) ( PoolAlloc* pa) |
| 114 | { |
| 115 | vg_assert(pa); |
| 116 | return pa->nPerPool * VG_(sizeXA) (pa->pools); |
| 117 | } |
| 118 | |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 119 | void* VG_(allocEltPA) ( PoolAlloc* pa) |
| 120 | { |
| 121 | UWord* elem; |
| 122 | if (UNLIKELY(pa->nextFree == NULL)) { |
| 123 | pal_add_new_pool(pa); |
| 124 | } |
| 125 | elem = pa->nextFree; |
| 126 | pa->nextFree = (void*)*elem; |
| 127 | *elem = 0; /* unnecessary, but just to be on the safe side */ |
| 128 | return elem; |
| 129 | } |
| 130 | |
| 131 | void VG_(freeEltPA) ( PoolAlloc* pa, void* p) |
| 132 | { |
| 133 | UWord* elem = (UWord*)p; |
| 134 | *elem = (UWord)pa->nextFree; |
| 135 | pa->nextFree = elem; |
| 136 | } |
| 137 | |
| 138 | |
| 139 | void VG_(addRefPA) ( PoolAlloc* pa) |
| 140 | { |
| 141 | pa->nrRef++; |
| 142 | } |
| 143 | |
bart | 6e07448 | 2012-01-18 08:12:16 +0000 | [diff] [blame] | 144 | UWord VG_(releasePA)(PoolAlloc* pa) |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 145 | { |
bart | 6e07448 | 2012-01-18 08:12:16 +0000 | [diff] [blame] | 146 | UWord nrRef; |
| 147 | |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 148 | vg_assert(pa->nrRef > 0); |
bart | 6e07448 | 2012-01-18 08:12:16 +0000 | [diff] [blame] | 149 | nrRef = --pa->nrRef; |
| 150 | if (nrRef == 0) |
| 151 | VG_(deletePA)(pa); |
| 152 | return nrRef; |
philippe | 6643e96 | 2012-01-17 21:16:30 +0000 | [diff] [blame] | 153 | } |