pool.h

   1 /*
   2  * pool.h
   3  */
   4
   5 #ifndef POOL_H_
   6 #define POOL_H_
   7
   8 #include <iostream>
   9 #include <vector>
  10 #include <stdexcept>
  11 #include <string.h>
  12 #include <stdlib.h>
  13 #include "bitset.h"
  14 #include "log.h"
  15 #include "search_globals.h"
  16
  17 /**
  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.
  21  */
  22 class ChunkPool {
  23 public:
  24         /**
  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.
  27          */
  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)
  33         {
  34                 assert_gt(lim_, 0);
  35                 try {
  36                         if((pool_ = new int8_t[totSz_]) == NULL) {
  37                                 throw std::bad_alloc();
  38                         }
  39                 } catch(std::bad_alloc& e) {
  40                         ThreadSafe _ts(&gLock);
  41                         std::cerr << "Error: Could not allocate ChunkPool of "
  42                                   << totSz << " bytes" << std::endl;
  43                         exhausted();
  44                         throw 1; // Exit if we haven't already
  45                 }
  46         }
  47
  48         /**
  49          * Delete all the pools.
  50          */
  51         ~ChunkPool() {
  52                 if(pool_ != NULL) delete[] pool_;
  53         }
  54
  55         /**
  56          * Reset the pool, freeing all arrays that had been given out.
  57          */
  58         void reset(String<char>* name, uint32_t patid_) {
  59                 patid = patid_;
  60                 readName_ = name;
  61                 cur_ = 0;
  62                 bits_.clear();
  63                 assert_eq(0, bits_.test(0));
  64         }
  65
  66         /**
  67          * Return our current position.
  68          */
  69         uint32_t pos() {
  70                 return cur_;
  71         }
  72
  73         /**
  74          * Return our current position.
  75          */
  76         uint32_t remaining() {
  77                 assert_geq(lim_, cur_);
  78                 return lim_ - cur_;
  79         }
  80
  81         /**
  82          * Allocate a single T from the pool.
  83          */
  84         void* alloc() {
  85                 assert_lt(cur_, lim_);
  86                 uint32_t cur = cur_;
  87                 while(bits_.test(cur)) {
  88                         cur++;
  89                         if(cur >= lim_) {
  90                                 cur = 0;
  91                         }
  92                         if(cur == cur_) {
  93                                 // Wrapped all the way around without finding a free
  94                                 // chunk
  95                                 return NULL;
  96                         }
  97                 }
  98                 void * ptr = (void *)(&pool_[cur * chunkSz_]);
  99                 assert(!bits_.test(cur));
 100                 bits_.set(cur);
 101                 assert(bits_.test(cur));
 102                 if(verbose) {
 103                         stringstream ss;
 104                         ss << patid << ": Allocating chunk with offset: " << cur;
 105                         glog.msg(ss.str());
 106                 }
 107                 cur_ = cur;
 108                 return ptr;
 109         }
 110
 111         /**
 112          *
 113          */
 114         void free(void *ptr) {
 115                 uint32_t off = (uint32_t)((int8_t*)ptr - pool_);
 116                 assert_eq(0, off % chunkSz_);
 117                 off /= chunkSz_;
 118                 if(verbose) {
 119                         stringstream ss;
 120                         ss << patid << ": Freeing chunk with offset: " << cur_;
 121                         glog.msg(ss.str());
 122                 }
 123                 bits_.clear(off);
 124         }
 125
 126         /**
 127          *
 128          */
 129         uint32_t chunkSize() const {
 130                 return chunkSz_;
 131         }
 132
 133         /**
 134          *
 135          */
 136         uint32_t totalSize() const {
 137                 return totSz_;
 138         }
 139
 140         /**
 141          * Utility function to call when memory has been exhausted.
 142          * Currently just prints a friendly message and quits.
 143          */
 144         void exhausted() {
 145                 if(patid != lastSkippedRead_) {
 146                         if(!exhaustCrash_ && !quiet) std::cerr << "Warning: ";
 147                         if(!quiet) {
 148                                 std::cerr << "Exhausted best-first chunk memory for read "
 149                                           << (*readName_) << " (patid " << patid
 150                                           << "); skipping read" << std::endl;
 151                         }
 152                         if(exhaustCrash_) {
 153                                 if(!quiet) {
 154                                         std::cerr << "Please try specifying a larger --chunkmbs <int> (default is 32)" << std::endl;
 155                                 }
 156                                 throw 1;
 157                         }
 158                 }
 159                 lastSkippedRead_ = patid;
 160         }
 161
 162         bool verbose;
 163         uint32_t patid;
 164
 165 protected:
 166
 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_
 172         FixedBitset2 bits_;
 173         bool exhaustCrash_; /// abort hard when memory's exhausted?
 174         uint32_t lastSkippedRead_;
 175         String<char>* readName_;
 176 };
 177
 178 /**
 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.
 183  */
 184 template<typename T>
 185 class AllocOnlyPool {
 186         typedef std::pair<uint32_t, uint32_t> U32Pair;
 187 public:
 188         /**
 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.
 191          */
 192         AllocOnlyPool(ChunkPool* pool, const char *name) :
 193                 pool_(pool), name_(name), curPool_(0), cur_(0)
 194         {
 195                 assert(pool != NULL);
 196                 lim_ = pool->chunkSize() / sizeof(T);
 197                 assert_gt(lim_, 0);
 198                 assert_gt(lim_, 1024);
 199         }
 200
 201         /**
 202          * Reset the pool, freeing all arrays that had been given out.
 203          */
 204         void reset() {
 205                 pools_.clear();
 206                 lastCurInPool_.clear();
 207                 cur_ = 0;
 208                 curPool_ = 0;
 209         }
 210
 211         /**
 212          * Allocate a single T from the pool.
 213          */
 214         T* alloc() {
 215                 if(!lazyInit()) return NULL;
 216                 if(cur_ + 1 >= lim_) {
 217                         if(!allocNextPool()) return NULL;
 218                 }
 219                 cur_ ++;
 220                 return &pools_[curPool_][cur_ - 1];
 221         }
 222
 223         /**
 224          * Allocate a single T from the pool and clear it.
 225          */
 226         T* allocC() {
 227                 T* t = alloc();
 228                 if(t != NULL) {
 229                         memset(t, 0, sizeof(T));
 230                 }
 231                 return t;
 232         }
 233
 234         /**
 235          * Allocate an array of Ts from the pool.
 236          */
 237         T* alloc(uint32_t num) {
 238                 if(!lazyInit()) return NULL;
 239                 if(cur_ + num >= lim_) {
 240                         if(!allocNextPool()) return NULL;
 241                         assert_eq(0, cur_);
 242                 }
 243                 assert_leq(num, lim_);
 244                 cur_ += num;
 245                 return &pools_[curPool_][cur_ - num];
 246         }
 247
 248         /**
 249          * Allocate an array of Ts and clear them.
 250          */
 251         T* allocC(uint32_t num) {
 252                 T* t = alloc(num);
 253                 if(t != NULL) {
 254                         memset(t, 0, sizeof(T) * num);
 255                 }
 256                 return t;
 257         }
 258
 259         /**
 260          * Return the current pool.
 261          */
 262         uint32_t curPool() const {
 263                 return curPool_;
 264         }
 265
 266         /**
 267          * Return the current position within the current pool.
 268          */
 269         uint32_t cur() const {
 270                 return cur_;
 271         }
 272
 273         /**
 274          * Free a pointer allocated from this pool.  Fow, we only know how
 275          * to free the topmost element.
 276          */
 277         void free(T* t) {
 278                 assert(t != NULL);
 279                 if(pool_->verbose) {
 280                         stringstream ss;
 281                         ss << pool_->patid << ": Freeing a " << name_;
 282                         glog.msg(ss.str());
 283                 }
 284                 if(cur_ > 0 && t == &pools_[curPool_][cur_-1]) {
 285                         cur_--;
 286                         ASSERT_ONLY(memset(&pools_[curPool_][cur_], 0, sizeof(T)));
 287                         if(cur_ == 0 && curPool_ > 0) {
 288                                 rewindPool();
 289                         }
 290                 }
 291         }
 292
 293         /**
 294          * Free an array of pointers allocated from this pool.  For now, we
 295          * only know how to free the topmost array.
 296          */
 297         bool free(T* t, uint32_t num) {
 298                 assert(t != NULL);
 299                 if(pool_->verbose) {
 300                         stringstream ss;
 301                         ss << pool_->patid << ": Freeing " << num << " " << name_ << "s";
 302                         glog.msg(ss.str());
 303                 }
 304                 if(num <= cur_ && t == &pools_[curPool_][cur_ - num]) {
 305                         cur_ -= num;
 306                         ASSERT_ONLY(memset(&pools_[curPool_][cur_], 0, num * sizeof(T)));
 307                         if(cur_ == 0 && curPool_ > 0) {
 308                                 rewindPool();
 309                         }
 310                         return true; // deallocated
 311                 }
 312                 return false; // didn't deallocate
 313         }
 314
 315         /**
 316          * Return a unique (with respect to every other object allocated
 317          * from this pool) identifier for the last object that was just
 318          * allocated.
 319          */
 320         uint32_t lastId() const {
 321                 return (curPool_ << 16) | cur_;
 322         }
 323
 324 #ifndef NDEBUG
 325         bool empty() const {
 326                 assert(pools_.empty());
 327                 assert_eq(0, cur_);
 328                 assert_eq(0, curPool_);
 329                 return true;
 330         }
 331 #endif
 332
 333 protected:
 334
 335         bool allocNextPool() {
 336                 assert_eq(curPool_+1, pools_.size());
 337                 T *pool;
 338                 try {
 339                         if((pool = (T*)pool_->alloc()) == NULL) {
 340                                 throw std::bad_alloc();
 341                         }
 342                 } catch(std::bad_alloc& e) {
 343                         ThreadSafe _ts(&gLock);
 344                         pool_->exhausted();
 345                         return false;
 346                 }
 347                 ASSERT_ONLY(memset(pool, 0, lim_ * sizeof(T)));
 348                 pools_.push_back(pool);
 349                 lastCurInPool_.push_back(cur_);
 350                 curPool_++;
 351                 cur_ = 0;
 352                 return true;
 353         }
 354
 355         bool lazyInit() {
 356                 if(cur_ == 0 && pools_.empty()) {
 357                         T *pool;
 358                         try {
 359                                 if((pool = (T*)pool_->alloc()) == NULL) {
 360                                         throw std::bad_alloc();
 361                                 }
 362                         } catch(std::bad_alloc& e) {
 363                                 ThreadSafe _ts(&gLock);
 364                                 pool_->exhausted();
 365                                 return false;
 366                         }
 367                         ASSERT_ONLY(memset(pool, 0, lim_ * sizeof(T)));
 368                         pools_.push_back(pool);
 369                         assert_eq(1, pools_.size());
 370                 }
 371                 assert(!pools_.empty());
 372                 return true;
 373         }
 374
 375         void rewindPool() {
 376                 assert_eq(curPool_+1, pools_.size());
 377                 assert_eq(curPool_, lastCurInPool_.size());
 378                 if(pool_->verbose) {
 379                         stringstream ss;
 380                         ss << pool_->patid << ": Freeing a " << name_ << " pool";
 381                         glog.msg(ss.str());
 382                 }
 383                 pool_->free(pools_.back());
 384                 pools_.pop_back();
 385                 curPool_--;
 386                 assert_gt(lastCurInPool_.size(), 0);
 387                 cur_ = lastCurInPool_.back();
 388                 lastCurInPool_.pop_back();
 389         }
 390
 391         ChunkPool*      pool_;
 392         const char     *name_;
 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_
 398 };
 399
 400 #endif /* POOL_H_ */
 401