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-2013 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
35struct _PoolAlloc {
36   UWord   nrRef;         /* nr reference to this pool allocator */
37   UWord   elemSzB;       /* element size */
38   UWord   nPerPool;      /* # elems per pool */
39   void*   (*alloc)(const HChar*, SizeT); /* pool allocator */
40   const HChar*  cc; /* pool allocator's cc */
41   void    (*free)(void*); /* 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
51PoolAlloc* VG_(newPA) ( UWord  elemSzB,
52                        UWord  nPerPool,
53                        void*  (*alloc)(const HChar*, SizeT),
54                        const  HChar* cc,
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 */
61   vg_assert(alloc);
62   vg_assert(cc);
63   vg_assert(free_fn);
64   pa = alloc(cc, sizeof(*pa));
65   vg_assert(pa);
66   VG_(memset)(pa, 0, sizeof(*pa));
67   pa->nrRef    = 0;
68   pa->elemSzB  = elemSzB;
69   pa->nPerPool = nPerPool;
70   pa->pools    = NULL;
71   pa->alloc    = alloc;
72   pa->cc       = cc;
73   pa->free     = free_fn;
74   pa->pools    = VG_(newXA)( alloc, cc, free_fn, sizeof(void*) );
75   pa->nextFree = NULL;
76   vg_assert(pa->pools);
77   return pa;
78}
79
80void VG_(deletePA) ( PoolAlloc* pa)
81{
82   Word i;
83   vg_assert(pa->nrRef == 0);
84   for (i = 0; i < VG_(sizeXA) (pa->pools); i++)
85      pa->free (*(UWord **)VG_(indexXA) ( pa->pools, i ));
86   VG_(deleteXA) (pa->pools);
87   pa->free (pa);
88}
89
90/* The freelist is empty.  Allocate a new pool and put all the new
91   elements in it onto the freelist. */
92__attribute__((noinline))
93static void pal_add_new_pool ( PoolAlloc* pa )
94{
95   Word   i;
96   UWord* pool;
97   vg_assert(pa);
98   vg_assert(pa->nextFree == NULL);
99   pool = pa->alloc( pa->cc, pa->elemSzB * pa->nPerPool );
100   vg_assert(pool);
101   /* extend the freelist through the new pool.  Place the freelist
102      pointer in the first word of each element.  That's why the
103      element size must be at least one word. */
104   for (i = pa->nPerPool-1; i >= 0; i--) {
105      UChar* elemC = ((UChar*)pool) + i * pa->elemSzB;
106      UWord* elem  = (UWord*)elemC;
107      vg_assert(0 == (((UWord)elem) % sizeof(UWord)));
108      *elem = (UWord)pa->nextFree;
109      pa->nextFree = elem;
110   }
111   /* and add to our collection of pools */
112   VG_(addToXA)( pa->pools, &pool );
113}
114
115void* VG_(allocEltPA) ( PoolAlloc* pa)
116{
117   UWord* elem;
118   if (UNLIKELY(pa->nextFree == NULL)) {
119      pal_add_new_pool(pa);
120   }
121   elem = pa->nextFree;
122   pa->nextFree = (void*)*elem;
123   *elem = 0; /* unnecessary, but just to be on the safe side */
124   return elem;
125}
126
127void VG_(freeEltPA) ( PoolAlloc* pa, void* p)
128{
129   UWord* elem = (UWord*)p;
130   *elem = (UWord)pa->nextFree;
131   pa->nextFree = elem;
132}
133
134
135void VG_(addRefPA) ( PoolAlloc* pa)
136{
137   pa->nrRef++;
138}
139
140UWord VG_(releasePA)(PoolAlloc* pa)
141{
142   UWord nrRef;
143
144   vg_assert(pa->nrRef > 0);
145   nrRef = --pa->nrRef;
146   if (nrRef == 0)
147      VG_(deletePA)(pa);
148   return nrRef;
149}
150