• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
8    Copyright (C) 2011-2017 OpenWorks LLP info@open-works.co.uk,
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"
32 #include "pub_core_xarray.h"
33 #include "pub_core_poolalloc.h" /* self */
34 
35 struct _PoolAlloc {
36    UWord   nrRef;         /* nr reference to this pool allocator */
37    UWord   elemSzB;       /* element size */
38    UWord   nPerPool;      /* # elems per pool */
39    Alloc_Fn_t alloc_fn;   /* pool allocator */
40    const HChar*  cc;      /* pool allocator's cost centre */
41    Free_Fn_t free_fn;     /* pool allocator's free-er */
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 
VG_(newPA)51 PoolAlloc* VG_(newPA) ( UWord  elemSzB,
52                         UWord  nPerPool,
53                         Alloc_Fn_t alloc_fn,
54                         const  HChar* cc,
55                         Free_Fn_t free_fn )
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 */
61    vg_assert(alloc_fn);
62    vg_assert(cc);
63    vg_assert(free_fn);
64    pa = alloc_fn(cc, sizeof(*pa));
65    VG_(memset)(pa, 0, sizeof(*pa));
66    pa->nrRef    = 0;
67    pa->elemSzB  = elemSzB;
68    pa->nPerPool = nPerPool;
69    pa->pools    = NULL;
70    pa->alloc_fn = alloc_fn;
71    pa->cc       = cc;
72    pa->free_fn  = free_fn;
73    pa->pools    = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(void*) );
74    pa->nextFree = NULL;
75 
76    return pa;
77 }
78 
VG_(deletePA)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++)
84       pa->free_fn (*(UWord **)VG_(indexXA) ( pa->pools, i ));
85    VG_(deleteXA) (pa->pools);
86    pa->free_fn (pa);
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))
pal_add_new_pool(PoolAlloc * pa)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);
98    pool = pa->alloc_fn( pa->cc, pa->elemSzB * pa->nPerPool );
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 
VG_(sizePA)113 UWord VG_(sizePA) ( PoolAlloc* pa)
114 {
115    vg_assert(pa);
116    return pa->nPerPool * VG_(sizeXA) (pa->pools);
117 }
118 
VG_(allocEltPA)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 
VG_(freeEltPA)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 
VG_(addRefPA)139 void VG_(addRefPA) ( PoolAlloc* pa)
140 {
141    pa->nrRef++;
142 }
143 
VG_(releasePA)144 UWord VG_(releasePA)(PoolAlloc* pa)
145 {
146    UWord nrRef;
147 
148    vg_assert(pa->nrRef > 0);
149    nrRef = --pa->nrRef;
150    if (nrRef == 0)
151       VG_(deletePA)(pa);
152    return nrRef;
153 }
154