15 #include "search_globals.h"
18 * Very simple allocator for fixed-size chunks of memory. Chunk size
19 * is set at construction time. Heap memory is only allocated at
20 * construction and deallocated at destruction.
25 * Initialize a new pool with an initial size of about 'bytes'
26 * bytes. Exit with an error message if we can't allocate it.
28 ChunkPool(uint32_t chunkSz, uint32_t totSz, bool verbose_) :
29 verbose(verbose_), patid(0), pool_(NULL), cur_(0),
30 chunkSz_(chunkSz), totSz_(totSz), lim_(totSz/chunkSz),
31 bits_(lim_), exhaustCrash_(false),
32 lastSkippedRead_(0xffffffff), readName_(NULL)
36 if((pool_ = new int8_t[totSz_]) == NULL) {
37 throw std::bad_alloc();
39 } catch(std::bad_alloc& e) {
40 ThreadSafe _ts(&gLock);
41 std::cerr << "Error: Could not allocate ChunkPool of "
42 << totSz << " bytes" << std::endl;
44 throw 1; // Exit if we haven't already
49 * Delete all the pools.
52 if(pool_ != NULL) delete[] pool_;
56 * Reset the pool, freeing all arrays that had been given out.
58 void reset(String<char>* name, uint32_t patid_) {
63 assert_eq(0, bits_.test(0));
67 * Return our current position.
74 * Return our current position.
76 uint32_t remaining() {
77 assert_geq(lim_, cur_);
82 * Allocate a single T from the pool.
85 assert_lt(cur_, lim_);
87 while(bits_.test(cur)) {
93 // Wrapped all the way around without finding a free
98 void * ptr = (void *)(&pool_[cur * chunkSz_]);
99 assert(!bits_.test(cur));
101 assert(bits_.test(cur));
104 ss << patid << ": Allocating chunk with offset: " << cur;
114 void free(void *ptr) {
115 uint32_t off = (uint32_t)((int8_t*)ptr - pool_);
116 assert_eq(0, off % chunkSz_);
120 ss << patid << ": Freeing chunk with offset: " << cur_;
129 uint32_t chunkSize() const {
136 uint32_t totalSize() const {
141 * Utility function to call when memory has been exhausted.
142 * Currently just prints a friendly message and quits.
145 if(patid != lastSkippedRead_) {
146 if(!exhaustCrash_ && !quiet) std::cerr << "Warning: ";
148 std::cerr << "Exhausted best-first chunk memory for read "
149 << (*readName_) << " (patid " << patid
150 << "); skipping read" << std::endl;
154 std::cerr << "Please try specifying a larger --chunkmbs <int> (default is 32)" << std::endl;
159 lastSkippedRead_ = patid;
167 int8_t* pool_; /// the memory pools
168 uint32_t cur_; /// index of next free element of pool_
169 const uint32_t chunkSz_;
170 const uint32_t totSz_;
171 uint32_t lim_; /// # elements held in pool_
173 bool exhaustCrash_; /// abort hard when memory's exhausted?
174 uint32_t lastSkippedRead_;
175 String<char>* readName_;
179 * Class for managing a pool of memory from which items of type T
180 * (which must have a default constructor) are allocated. Does not
181 * support freeing or resizing individual items - just allocation and
182 * then freeing all items at once.
185 class AllocOnlyPool {
186 typedef std::pair<uint32_t, uint32_t> U32Pair;
189 * Initialize a new pool with an initial size of about 'bytes'
190 * bytes. Exit with an error message if we can't allocate it.
192 AllocOnlyPool(ChunkPool* pool, const char *name) :
193 pool_(pool), name_(name), curPool_(0), cur_(0)
195 assert(pool != NULL);
196 lim_ = pool->chunkSize() / sizeof(T);
198 assert_gt(lim_, 1024);
202 * Reset the pool, freeing all arrays that had been given out.
206 lastCurInPool_.clear();
212 * Allocate a single T from the pool.
215 if(!lazyInit()) return NULL;
216 if(cur_ + 1 >= lim_) {
217 if(!allocNextPool()) return NULL;
220 return &pools_[curPool_][cur_ - 1];
224 * Allocate a single T from the pool and clear it.
229 memset(t, 0, sizeof(T));
235 * Allocate an array of Ts from the pool.
237 T* alloc(uint32_t num) {
238 if(!lazyInit()) return NULL;
239 if(cur_ + num >= lim_) {
240 if(!allocNextPool()) return NULL;
243 assert_leq(num, lim_);
245 return &pools_[curPool_][cur_ - num];
249 * Allocate an array of Ts and clear them.
251 T* allocC(uint32_t num) {
254 memset(t, 0, sizeof(T) * num);
260 * Return the current pool.
262 uint32_t curPool() const {
267 * Return the current position within the current pool.
269 uint32_t cur() const {
274 * Free a pointer allocated from this pool. Fow, we only know how
275 * to free the topmost element.
281 ss << pool_->patid << ": Freeing a " << name_;
284 if(cur_ > 0 && t == &pools_[curPool_][cur_-1]) {
286 ASSERT_ONLY(memset(&pools_[curPool_][cur_], 0, sizeof(T)));
287 if(cur_ == 0 && curPool_ > 0) {
294 * Free an array of pointers allocated from this pool. For now, we
295 * only know how to free the topmost array.
297 bool free(T* t, uint32_t num) {
301 ss << pool_->patid << ": Freeing " << num << " " << name_ << "s";
304 if(num <= cur_ && t == &pools_[curPool_][cur_ - num]) {
306 ASSERT_ONLY(memset(&pools_[curPool_][cur_], 0, num * sizeof(T)));
307 if(cur_ == 0 && curPool_ > 0) {
310 return true; // deallocated
312 return false; // didn't deallocate
316 * Return a unique (with respect to every other object allocated
317 * from this pool) identifier for the last object that was just
320 uint32_t lastId() const {
321 return (curPool_ << 16) | cur_;
326 assert(pools_.empty());
328 assert_eq(0, curPool_);
335 bool allocNextPool() {
336 assert_eq(curPool_+1, pools_.size());
339 if((pool = (T*)pool_->alloc()) == NULL) {
340 throw std::bad_alloc();
342 } catch(std::bad_alloc& e) {
343 ThreadSafe _ts(&gLock);
347 ASSERT_ONLY(memset(pool, 0, lim_ * sizeof(T)));
348 pools_.push_back(pool);
349 lastCurInPool_.push_back(cur_);
356 if(cur_ == 0 && pools_.empty()) {
359 if((pool = (T*)pool_->alloc()) == NULL) {
360 throw std::bad_alloc();
362 } catch(std::bad_alloc& e) {
363 ThreadSafe _ts(&gLock);
367 ASSERT_ONLY(memset(pool, 0, lim_ * sizeof(T)));
368 pools_.push_back(pool);
369 assert_eq(1, pools_.size());
371 assert(!pools_.empty());
376 assert_eq(curPool_+1, pools_.size());
377 assert_eq(curPool_, lastCurInPool_.size());
380 ss << pool_->patid << ": Freeing a " << name_ << " pool";
383 pool_->free(pools_.back());
386 assert_gt(lastCurInPool_.size(), 0);
387 cur_ = lastCurInPool_.back();
388 lastCurInPool_.pop_back();
393 std::vector<T*> pools_; /// the memory pools
394 uint32_t curPool_; /// pool we're current allocating from
395 std::vector<uint32_t> lastCurInPool_;
396 uint32_t lim_; /// # elements held in pool_
397 uint32_t cur_; /// index of next free element of pool_