16643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe/*------------------------------------------------------------------------*/ 26643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe/*--- A simple pool (memory) allocator implementation. m_poolalloc.c --- */ 36643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe/*------------------------------------------------------------------------*/ 46643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe/* 56643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe This file is part of Valgrind, a dynamic binary instrumentation 66643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe framework. 76643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 8b3a1e4bffbdbbf38304f216af405009868f43628sewardj Copyright (C) 2011-2015 OpenWorks LLP info@open-works.co.uk, 96643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe Philippe Waroquiers philippe.waroquiers@skynet.be 106643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 116643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe This program is free software; you can redistribute it and/or 126643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe modify it under the terms of the GNU General Public License as 136643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe published by the Free Software Foundation; either version 2 of the 146643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe License, or (at your option) any later version. 156643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 166643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe This program is distributed in the hope that it will be useful, but 176643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe WITHOUT ANY WARRANTY; without even the implied warranty of 186643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 196643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe General Public License for more details. 206643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 216643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe You should have received a copy of the GNU General Public License 226643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe along with this program; if not, write to the Free Software 236643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 246643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 02111-1307, USA. 256643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 266643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe The GNU General Public License is contained in the file COPYING. 276643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe*/ 286643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 296643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#include "pub_core_basics.h" 306643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#include "pub_core_libcbase.h" 316643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#include "pub_core_libcassert.h" 32c91f58449e6fc2a4ce0851639a342c4277612fbbflorian#include "pub_core_xarray.h" 33c91f58449e6fc2a4ce0851639a342c4277612fbbflorian#include "pub_core_poolalloc.h" /* self */ 346643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 356643e96a72e8530a7c8830c02ffb2fb4aee74c88philippestruct _PoolAlloc { 366643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord nrRef; /* nr reference to this pool allocator */ 376643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord elemSzB; /* element size */ 386643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord nPerPool; /* # elems per pool */ 396a65074829be219b2d4a6b15d2d25c5491da9a72florian void* (*alloc_fn)(const HChar*, SizeT); /* pool allocator */ 406a65074829be219b2d4a6b15d2d25c5491da9a72florian const HChar* cc; /* pool allocator's cost centre */ 416a65074829be219b2d4a6b15d2d25c5491da9a72florian void (*free_fn)(void*); /* pool allocator's free-er */ 426643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe /* XArray of void* (pointers to pools). The pools themselves. 436643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe Each element is a pointer to a block of size (elemSzB * 446643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe nPerPool) bytes. */ 456643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe XArray* pools; 466643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe /* next free element. Is a pointer to an element in one of the 476643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pools pointed to by .pools */ 486643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe void* nextFree; 496643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe}; 506643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 516643e96a72e8530a7c8830c02ffb2fb4aee74c88philippePoolAlloc* VG_(newPA) ( UWord elemSzB, 526643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord nPerPool, 536a65074829be219b2d4a6b15d2d25c5491da9a72florian void* (*alloc_fn)(const HChar*, SizeT), 5454fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorian const HChar* cc, 556643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe void (*free_fn)(void*) ) 566643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 576643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe PoolAlloc* pa; 586643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(0 == (elemSzB % sizeof(UWord))); 596643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(elemSzB >= sizeof(UWord)); 606643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(nPerPool >= 100); /* let's say */ 616a65074829be219b2d4a6b15d2d25c5491da9a72florian vg_assert(alloc_fn); 626643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(cc); 636643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(free_fn); 646a65074829be219b2d4a6b15d2d25c5491da9a72florian pa = alloc_fn(cc, sizeof(*pa)); 656643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe VG_(memset)(pa, 0, sizeof(*pa)); 666643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nrRef = 0; 676643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->elemSzB = elemSzB; 686643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nPerPool = nPerPool; 696643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->pools = NULL; 706a65074829be219b2d4a6b15d2d25c5491da9a72florian pa->alloc_fn = alloc_fn; 716643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->cc = cc; 726a65074829be219b2d4a6b15d2d25c5491da9a72florian pa->free_fn = free_fn; 736a65074829be219b2d4a6b15d2d25c5491da9a72florian pa->pools = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(void*) ); 746643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nextFree = NULL; 7591ed8ccd3dae8a6abfaa45cc0d250df47b45187fflorian 766643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe return pa; 776643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 786643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 796643e96a72e8530a7c8830c02ffb2fb4aee74c88philippevoid VG_(deletePA) ( PoolAlloc* pa) 806643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 816643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe Word i; 826643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(pa->nrRef == 0); 836643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe for (i = 0; i < VG_(sizeXA) (pa->pools); i++) 846a65074829be219b2d4a6b15d2d25c5491da9a72florian pa->free_fn (*(UWord **)VG_(indexXA) ( pa->pools, i )); 856643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe VG_(deleteXA) (pa->pools); 866a65074829be219b2d4a6b15d2d25c5491da9a72florian pa->free_fn (pa); 876643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 886643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 896643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe/* The freelist is empty. Allocate a new pool and put all the new 906643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe elements in it onto the freelist. */ 916643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe__attribute__((noinline)) 926643e96a72e8530a7c8830c02ffb2fb4aee74c88philippestatic void pal_add_new_pool ( PoolAlloc* pa ) 936643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 946643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe Word i; 956643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord* pool; 966643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(pa); 976643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(pa->nextFree == NULL); 986a65074829be219b2d4a6b15d2d25c5491da9a72florian pool = pa->alloc_fn( pa->cc, pa->elemSzB * pa->nPerPool ); 996643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe /* extend the freelist through the new pool. Place the freelist 1006643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pointer in the first word of each element. That's why the 1016643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe element size must be at least one word. */ 1026643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe for (i = pa->nPerPool-1; i >= 0; i--) { 1036643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UChar* elemC = ((UChar*)pool) + i * pa->elemSzB; 1046643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord* elem = (UWord*)elemC; 1056643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe vg_assert(0 == (((UWord)elem) % sizeof(UWord))); 1066643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe *elem = (UWord)pa->nextFree; 1076643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nextFree = elem; 1086643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe } 1096643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe /* and add to our collection of pools */ 1106643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe VG_(addToXA)( pa->pools, &pool ); 1116643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 1126643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 11371ed3c9382fa816a84731e9a2ddb9eda7d5624a6philippeUWord VG_(sizePA) ( PoolAlloc* pa) 11471ed3c9382fa816a84731e9a2ddb9eda7d5624a6philippe{ 11571ed3c9382fa816a84731e9a2ddb9eda7d5624a6philippe vg_assert(pa); 11671ed3c9382fa816a84731e9a2ddb9eda7d5624a6philippe return pa->nPerPool * VG_(sizeXA) (pa->pools); 11771ed3c9382fa816a84731e9a2ddb9eda7d5624a6philippe} 11871ed3c9382fa816a84731e9a2ddb9eda7d5624a6philippe 1196643e96a72e8530a7c8830c02ffb2fb4aee74c88philippevoid* VG_(allocEltPA) ( PoolAlloc* pa) 1206643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 1216643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord* elem; 1226643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe if (UNLIKELY(pa->nextFree == NULL)) { 1236643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pal_add_new_pool(pa); 1246643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe } 1256643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe elem = pa->nextFree; 1266643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nextFree = (void*)*elem; 1276643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe *elem = 0; /* unnecessary, but just to be on the safe side */ 1286643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe return elem; 1296643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 1306643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 1316643e96a72e8530a7c8830c02ffb2fb4aee74c88philippevoid VG_(freeEltPA) ( PoolAlloc* pa, void* p) 1326643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 1336643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe UWord* elem = (UWord*)p; 1346643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe *elem = (UWord)pa->nextFree; 1356643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nextFree = elem; 1366643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 1376643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 1386643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 1396643e96a72e8530a7c8830c02ffb2fb4aee74c88philippevoid VG_(addRefPA) ( PoolAlloc* pa) 1406643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 1416643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe pa->nrRef++; 1426643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 1436643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 1446e07448898bce224dea3741093ba67f9b1d72a5bbartUWord VG_(releasePA)(PoolAlloc* pa) 1456643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 1466e07448898bce224dea3741093ba67f9b1d72a5bbart UWord nrRef; 1476643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 1486e07448898bce224dea3741093ba67f9b1d72a5bbart vg_assert(pa->nrRef > 0); 1496e07448898bce224dea3741093ba67f9b1d72a5bbart nrRef = --pa->nrRef; 1506e07448898bce224dea3741093ba67f9b1d72a5bbart if (nrRef == 0) 1516e07448898bce224dea3741093ba67f9b1d72a5bbart VG_(deletePA)(pa); 1526e07448898bce224dea3741093ba67f9b1d72a5bbart return nrRef; 1536643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 154