12ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Copyright 2000 The RE2 Authors. All Rights Reserved. 22ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Use of this source code is governed by a BSD-style 32ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// license that can be found in the LICENSE file. 42ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 52ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#include "util/util.h" 62ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 72ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonnamespace re2 { 82ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 92ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena::UnsafeArena() 112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena::~UnsafeArena() 122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Destroying the arena automatically calls Reset() 132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian HodsonUnsafeArena::UnsafeArena(const size_t block_size) 172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson : block_size_(block_size), 182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_(NULL), // set for real in Reset() 192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson last_alloc_(NULL), 202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_(0), 212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson blocks_alloced_(1), 222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson overflow_blocks_(NULL) { 232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson assert(block_size > kDefaultAlignment); 242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson first_blocks_[0].mem = reinterpret_cast<char*>(malloc(block_size_)); 262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson first_blocks_[0].size = block_size_; 272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson Reset(); 292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian HodsonUnsafeArena::~UnsafeArena() { 322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson FreeBlocks(); 332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson assert(overflow_blocks_ == NULL); // FreeBlocks() should do that 342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // The first X blocks stay allocated always by default. Delete them now. 352ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson for (int i = 0; i < blocks_alloced_; i++) 362ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson free(first_blocks_[i].mem); 372ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 382ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 392ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 402ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena::Reset() 412ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Clears all the memory an arena is using. 422ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 432ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 442ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonvoid UnsafeArena::Reset() { 452ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson FreeBlocks(); 462ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_ = first_blocks_[0].mem; 472ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ = first_blocks_[0].size; 482ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson last_alloc_ = NULL; 492ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 502ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // We do not know for sure whether or not the first block is aligned, 512ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // so we fix that right now. 522ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const int overage = reinterpret_cast<uintptr_t>(freestart_) & 532ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson (kDefaultAlignment-1); 542ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (overage > 0) { 552ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const int waste = kDefaultAlignment - overage; 562ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_ += waste; 572ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ -= waste; 582ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 592ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_when_empty_ = freestart_; 602ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson assert(!(reinterpret_cast<uintptr_t>(freestart_)&(kDefaultAlignment-1))); 612ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 622ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 632ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ------------------------------------------------------------- 642ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena::AllocNewBlock() 652ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Adds and returns an AllocatedBlock. 662ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// The returned AllocatedBlock* is valid until the next call 672ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// to AllocNewBlock or Reset. (i.e. anything that might 682ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// affect overflow_blocks_). 692ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ------------------------------------------------------------- 702ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 712ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian HodsonUnsafeArena::AllocatedBlock* UnsafeArena::AllocNewBlock(const size_t block_size) { 722ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson AllocatedBlock *block; 732ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // Find the next block. 742ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if ( blocks_alloced_ < arraysize(first_blocks_) ) { 752ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // Use one of the pre-allocated blocks 762ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson block = &first_blocks_[blocks_alloced_++]; 772ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } else { // oops, out of space, move to the vector 782ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (overflow_blocks_ == NULL) overflow_blocks_ = new vector<AllocatedBlock>; 792ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // Adds another block to the vector. 802ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson overflow_blocks_->resize(overflow_blocks_->size()+1); 812ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // block points to the last block of the vector. 822ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson block = &overflow_blocks_->back(); 832ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 842ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 852ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson block->mem = reinterpret_cast<char*>(malloc(block_size)); 862ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson block->size = block_size; 872ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 882ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return block; 892ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 902ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 912ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 922ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena::GetMemoryFallback() 932ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// We take memory out of our pool, aligned on the byte boundary 942ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// requested. If we don't have space in our current pool, we 952ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// allocate a new block (wasting the remaining space in the 962ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// current block) and give you that. If your memory needs are 972ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// too big for a single block, we make a special your-memory-only 982ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// allocation -- this is equivalent to not using the arena at all. 992ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 1002ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1012ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonvoid* UnsafeArena::GetMemoryFallback(const size_t size, const int align) { 1022ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (size == 0) 1032ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return NULL; // stl/stl_alloc.h says this is okay 1042ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1052ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson assert(align > 0 && 0 == (align & (align - 1))); // must be power of 2 1062ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1072ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // If the object is more than a quarter of the block size, allocate 1082ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // it separately to avoid wasting too much space in leftover bytes 1092ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (block_size_ == 0 || size > block_size_/4) { 1102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // then it gets its own block in the arena 1112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson assert(align <= kDefaultAlignment); // because that's what new gives us 1122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // This block stays separate from the rest of the world; in particular 1132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // we don't update last_alloc_ so you can't reclaim space on this block. 1142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return AllocNewBlock(size)->mem; 1152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const int overage = 1182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson (reinterpret_cast<uintptr_t>(freestart_) & (align-1)); 1192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (overage) { 1202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const int waste = align - overage; 1212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_ += waste; 1222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (waste < remaining_) { 1232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ -= waste; 1242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } else { 1252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ = 0; 1262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (size > remaining_) { 1292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson AllocatedBlock *block = AllocNewBlock(block_size_); 1302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_ = block->mem; 1312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ = block->size; 1322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ -= size; 1342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson last_alloc_ = freestart_; 1352ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_ += size; 1362ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson assert((reinterpret_cast<uintptr_t>(last_alloc_) & (align-1)) == 0); 1372ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return reinterpret_cast<void*>(last_alloc_); 1382ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 1392ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1402ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 1412ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena::FreeBlocks() 1422ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Unlike GetMemory(), which does actual work, ReturnMemory() is a 1432ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// no-op: we don't "free" memory until Reset() is called. We do 1442ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// update some stats, though. Note we do no checking that the 1452ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// pointer you pass in was actually allocated by us, or that it 1462ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// was allocated for the size you say, so be careful here! 1472ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// FreeBlocks() does the work for Reset(), actually freeing all 1482ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// memory allocated in one fell swoop. 1492ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// ---------------------------------------------------------------------- 1502ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1512ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonvoid UnsafeArena::FreeBlocks() { 1522ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson for ( int i = 1; i < blocks_alloced_; ++i ) { // keep first block alloced 1532ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson free(first_blocks_[i].mem); 1542ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson first_blocks_[i].mem = NULL; 1552ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson first_blocks_[i].size = 0; 1562ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1572ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson blocks_alloced_ = 1; 1582ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if (overflow_blocks_ != NULL) { 1592ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson vector<AllocatedBlock>::iterator it; 1602ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson for (it = overflow_blocks_->begin(); it != overflow_blocks_->end(); ++it) { 1612ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson free(it->mem); 1622ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1632ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson delete overflow_blocks_; // These should be used very rarely 1642ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson overflow_blocks_ = NULL; 1652ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 1662ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 1672ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1682ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} // namespace re2 169