Stxxl
1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/mng/mng.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002-2004 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2007 Johannes Singler <singler@ira.uka.de> 00008 * Copyright (C) 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00009 * 00010 * Distributed under the Boost Software License, Version 1.0. 00011 * (See accompanying file LICENSE_1_0.txt or copy at 00012 * http://www.boost.org/LICENSE_1_0.txt) 00013 **************************************************************************/ 00014 00015 #ifndef STXXL_MNG_HEADER 00016 #define STXXL_MNG_HEADER 00017 00018 #include <memory> 00019 #include <iostream> 00020 #include <iomanip> 00021 #include <fstream> 00022 #include <vector> 00023 #include <list> 00024 #include <map> 00025 #include <algorithm> 00026 #include <string> 00027 #include <cstdlib> 00028 00029 #ifdef STXXL_BOOST_CONFIG 00030 #include <boost/config.hpp> 00031 #endif 00032 00033 #ifdef BOOST_MSVC 00034 #include <memory.h> 00035 #endif 00036 00037 #include <stxxl/bits/io/iobase.h> 00038 #include <stxxl/bits/noncopyable.h> 00039 #include <stxxl/bits/common/rand.h> 00040 #include <stxxl/bits/common/aligned_alloc.h> 00041 #include <stxxl/bits/common/debug.h> 00042 #include <stxxl/bits/parallel.h> 00043 #include <stxxl/bits/singleton.h> 00044 00045 #ifndef STXXL_VERBOSE_BLOCK_LIFE_CYCLE 00046 #define STXXL_VERBOSE_BLOCK_LIFE_CYCLE STXXL_VERBOSE2 00047 #endif 00048 #define FMT_BID(_bid_) "[" << (_bid_).storage->get_id() << "]0x" << std::hex << std::setfill('0') << std::setw(8) << (_bid_).offset << "/0x" << std::setw(8) << (_bid_).size 00049 00050 00051 __STXXL_BEGIN_NAMESPACE 00052 00057 00059 00061 template <unsigned SIZE> 00062 struct BID 00063 { 00064 enum 00065 { 00066 size = SIZE, 00067 t_size = SIZE 00068 }; 00069 file * storage; 00070 stxxl::int64 offset; 00071 BID() : storage(NULL), offset(0) { } 00072 bool valid() const 00073 { 00074 return storage; 00075 } 00076 BID(file * s, stxxl::int64 o) : storage(s), offset(o) { } 00077 BID(const BID & obj) : storage(obj.storage), offset(obj.offset) { } 00078 template <unsigned BlockSize> 00079 explicit BID(const BID<BlockSize> & obj) : storage(obj.storage), offset(obj.offset) { } 00080 }; 00081 00082 00084 00086 template <> 00087 struct BID<0> 00088 { 00089 file * storage; 00090 stxxl::int64 offset; 00091 unsigned size; 00092 enum 00093 { 00094 t_size = 0 00095 }; 00096 BID() : storage(NULL), offset(0), size(0) { } 00097 BID(file * f, stxxl::int64 o, unsigned s) : storage(f), offset(o), size(s) { } 00098 bool valid() const 00099 { 00100 return storage; 00101 } 00102 }; 00103 00104 template <unsigned blk_sz> 00105 bool operator == (const BID<blk_sz> & a, const BID<blk_sz> & b) 00106 { 00107 return (a.storage == b.storage) && (a.offset == b.offset) && (a.size == b.size); 00108 } 00109 00110 template <unsigned blk_sz> 00111 bool operator != (const BID<blk_sz> & a, const BID<blk_sz> & b) 00112 { 00113 return (a.storage != b.storage) || (a.offset != b.offset) || (a.size != b.size); 00114 } 00115 00116 00117 template <unsigned blk_sz> 00118 std::ostream & operator << (std::ostream & s, const BID<blk_sz> & bid) 00119 { 00120 s << " storage file addr: " << bid.storage; 00121 s << " offset: " << bid.offset; 00122 s << " size: " << bid.size; 00123 return s; 00124 } 00125 00126 00127 template <unsigned bytes> 00128 class filler_struct__ 00129 { 00130 typedef unsigned char byte_type; 00131 byte_type filler_array_[bytes]; 00132 00133 public: 00134 filler_struct__() { STXXL_VERBOSE2("filler_struct__ is allocated"); } 00135 }; 00136 00137 template <> 00138 class filler_struct__<0> 00139 { 00140 typedef unsigned char byte_type; 00141 00142 public: 00143 filler_struct__() { STXXL_VERBOSE2("filler_struct__ is allocated"); } 00144 }; 00145 00147 template <class T, unsigned Size_> 00148 class element_block 00149 { 00150 public: 00151 typedef T type; 00152 typedef T value_type; 00153 typedef T & reference; 00154 typedef const T & const_reference; 00155 typedef type * pointer; 00156 typedef pointer iterator; 00157 typedef const type * const_iterator; 00158 00159 enum 00160 { 00161 size = Size_ 00162 }; 00163 00165 T elem[size]; 00166 00167 element_block() { STXXL_VERBOSE2("element_block is allocated"); } 00168 00170 reference operator [] (int i) 00171 { 00172 return elem[i]; 00173 } 00174 00176 iterator begin() 00177 { 00178 return elem; 00179 } 00181 const_iterator begin() const 00182 { 00183 return elem; 00184 } 00186 const_iterator cbegin() const 00187 { 00188 return begin(); 00189 } 00191 iterator end() 00192 { 00193 return elem + size; 00194 } 00196 const_iterator end() const 00197 { 00198 return elem + size; 00199 } 00201 const_iterator cend() const 00202 { 00203 return end(); 00204 } 00205 }; 00206 00208 template <class T, unsigned Size_, unsigned RawSize_, unsigned NBids_ = 0> 00209 class block_w_bids : public element_block<T, Size_> 00210 { 00211 public: 00212 enum 00213 { 00214 raw_size = RawSize_, 00215 nbids = NBids_ 00216 }; 00217 typedef BID<raw_size> bid_type; 00218 00220 bid_type ref[nbids]; 00221 00223 bid_type & operator () (int i) 00224 { 00225 return ref[i]; 00226 } 00227 00228 block_w_bids() { STXXL_VERBOSE2("block_w_bids is allocated"); } 00229 }; 00230 00231 template <class T, unsigned Size_, unsigned RawSize_> 00232 class block_w_bids<T, Size_, RawSize_, 0>: public element_block<T, Size_> 00233 { 00234 public: 00235 enum 00236 { 00237 raw_size = RawSize_, 00238 nbids = 0 00239 }; 00240 typedef BID<raw_size> bid_type; 00241 00242 block_w_bids() { STXXL_VERBOSE2("block_w_bids is allocated"); } 00243 }; 00244 00246 template <class T_, unsigned RawSize_, unsigned NBids_, class InfoType_ = void> 00247 class block_w_info : 00248 public block_w_bids<T_, ((RawSize_ - sizeof(BID<RawSize_>) * NBids_ - sizeof(InfoType_)) / sizeof(T_)), RawSize_, NBids_> 00249 { 00250 public: 00252 typedef InfoType_ info_type; 00253 00255 info_type info; 00256 00257 enum { size = ((RawSize_ - sizeof(BID<RawSize_>) * NBids_ - sizeof(InfoType_)) / sizeof(T_)) }; 00258 00259 public: 00260 block_w_info() { STXXL_VERBOSE2("block_w_info is allocated"); } 00261 }; 00262 00263 template <class T_, unsigned RawSize_, unsigned NBids_> 00264 class block_w_info<T_, RawSize_, NBids_, void>: 00265 public block_w_bids<T_, ((RawSize_ - sizeof(BID<RawSize_>) * NBids_) / sizeof(T_)), RawSize_, NBids_> 00266 { 00267 public: 00268 typedef void info_type; 00269 enum { size = ((RawSize_ - sizeof(BID<RawSize_>) * NBids_) / sizeof(T_)) }; 00270 00271 public: 00272 block_w_info() { STXXL_VERBOSE2("block_w_info is allocated"); } 00273 }; 00274 00276 00289 template <unsigned RawSize_, class T_, unsigned NRef_ = 0, class InfoType_ = void> 00290 class typed_block : 00291 public block_w_info<T_, RawSize_, NRef_, InfoType_>, 00292 public filler_struct__<(RawSize_ - sizeof(block_w_info<T_, RawSize_, NRef_, InfoType_>))> 00293 { 00294 public: 00295 typedef T_ type; 00296 typedef T_ value_type; 00297 typedef T_ & reference; 00298 typedef const T_ & const_reference; 00299 typedef type * pointer; 00300 typedef pointer iterator; 00301 typedef type const * const_iterator; 00302 00303 enum { has_filler = (RawSize_ != sizeof(block_w_info<T_, RawSize_, NRef_, InfoType_>)) }; 00304 00305 typedef BID<RawSize_> bid_type; 00306 00307 typed_block() 00308 { 00309 STXXL_VERBOSE2("typed_block is allocated"); 00310 } 00311 00312 enum 00313 { 00314 raw_size = RawSize_, 00315 size = block_w_info<T_, RawSize_, NRef_, InfoType_>::size 00316 }; 00317 00323 request_ptr write(const BID<raw_size> & bid, 00324 completion_handler on_cmpl = default_completion_handler()) 00325 { 00326 STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:write " << FMT_BID(bid)); 00327 return bid.storage->awrite( 00328 this, 00329 bid.offset, 00330 raw_size, 00331 on_cmpl); 00332 } 00333 00339 request_ptr read(const BID<raw_size> & bid, 00340 completion_handler on_cmpl = default_completion_handler()) 00341 { 00342 STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:read " << FMT_BID(bid)); 00343 return bid.storage->aread(this, bid.offset, raw_size, on_cmpl); 00344 } 00345 00346 static void * operator new[] (size_t bytes) 00347 { 00348 unsigned_type meta_info_size = bytes % raw_size; 00349 STXXL_VERBOSE1("typed::block operator new[]: Meta info size: " << meta_info_size); 00350 00351 void * result = aligned_alloc<BLOCK_ALIGN>(bytes, meta_info_size); 00352 #ifdef STXXL_VALGRIND_TYPED_BLOCK_INITIALIZE_ZERO 00353 memset(result, 0, bytes); 00354 #endif 00355 char * tmp = (char *)result; 00356 STXXL_DEBUGMON_DO(block_allocated(tmp, tmp + bytes, RawSize_)); 00357 tmp += RawSize_; 00358 while (tmp < ((char *)result) + bytes) 00359 { 00360 STXXL_DEBUGMON_DO(block_allocated(tmp, ((char *)result) + bytes, RawSize_)); 00361 tmp += RawSize_; 00362 } 00363 return result; 00364 } 00365 00366 static void * operator new (size_t bytes) 00367 { 00368 unsigned_type meta_info_size = bytes % raw_size; 00369 STXXL_VERBOSE1("typed::block operator new: Meta info size: " << meta_info_size); 00370 00371 void * result = aligned_alloc<BLOCK_ALIGN>(bytes, meta_info_size); 00372 #ifdef STXXL_VALGRIND_TYPED_BLOCK_INITIALIZE_ZERO 00373 memset(result, 0, bytes); 00374 #endif 00375 char * tmp = (char *)result; 00376 STXXL_DEBUGMON_DO(block_allocated(tmp, tmp + bytes, RawSize_)); 00377 tmp += RawSize_; 00378 while (tmp < ((char *)result) + bytes) 00379 { 00380 STXXL_DEBUGMON_DO(block_allocated(tmp, ((char *)result) + bytes, RawSize_)); 00381 tmp += RawSize_; 00382 } 00383 return result; 00384 } 00385 00386 static void * operator new (size_t /*bytes*/, void * ptr) // construct object in existing memory 00387 { 00388 return ptr; 00389 } 00390 00391 static void operator delete[] (void * ptr) 00392 { 00393 STXXL_DEBUGMON_DO(block_deallocated((char *)ptr)); 00394 aligned_dealloc<BLOCK_ALIGN>(ptr); 00395 } 00396 00397 static void operator delete (void * ptr) 00398 { 00399 STXXL_DEBUGMON_DO(block_deallocated((char *)ptr)); 00400 aligned_dealloc<BLOCK_ALIGN>(ptr); 00401 } 00402 00403 static void operator delete (void *, void *) 00404 { } 00405 00406 // STRANGE: implementing destructor makes g++ allocate 00407 // additional 4 bytes in the beginning of every array 00408 // of this type !? makes aligning to 4K boundaries difficult 00409 // 00410 // http://www.cc.gatech.edu/grads/j/Seung.Won.Jun/tips/pl/node4.html : 00411 // "One interesting thing is the array allocator requires more memory 00412 // than the array size multiplied by the size of an element, by a 00413 // difference of delta for metadata a compiler needs. It happens to 00414 // be 8 bytes long in g++." 00415 // ~typed_block() { } 00416 }; 00417 00418 00419 #if 0 00420 template <unsigned BLK_SIZE> 00421 class BIDArray : public std::vector<BID<BLK_SIZE> > 00422 { 00423 public: 00424 BIDArray(std::vector<BID<BLK_SIZE> >::size_type size = 0) : std::vector<BID<BLK_SIZE> >(size) { } 00425 }; 00426 #endif 00427 00428 template <unsigned BLK_SIZE> 00429 class BIDArray : private noncopyable 00430 { 00431 protected: 00432 unsigned_type _size; 00433 BID<BLK_SIZE> * array; 00434 00435 public: 00436 typedef BID<BLK_SIZE> & reference; 00437 typedef BID<BLK_SIZE> * iterator; 00438 typedef const BID<BLK_SIZE> * const_iterator; 00439 BIDArray() : _size(0), array(NULL) 00440 { } 00441 iterator begin() 00442 { 00443 return array; 00444 } 00445 iterator end() 00446 { 00447 return array + _size; 00448 } 00449 00450 BIDArray(unsigned_type size) : _size(size) 00451 { 00452 array = new BID<BLK_SIZE>[size]; 00453 } 00454 unsigned_type size() const 00455 { 00456 return _size; 00457 } 00458 reference operator [] (int_type i) 00459 { 00460 return array[i]; 00461 } 00462 void resize(unsigned_type newsize) 00463 { 00464 if (array) 00465 { 00466 STXXL_MSG("Warning: resizing nonempty BIDArray"); 00467 BID<BLK_SIZE> * tmp = array; 00468 array = new BID<BLK_SIZE>[newsize]; 00469 memcpy((void *)array, (void *)tmp, 00470 sizeof(BID<BLK_SIZE>) * (STXXL_MIN(_size, newsize))); 00471 delete[] tmp; 00472 _size = newsize; 00473 } 00474 else 00475 { 00476 array = new BID<BLK_SIZE>[newsize]; 00477 _size = newsize; 00478 } 00479 } 00480 ~BIDArray() 00481 { 00482 if (array) 00483 delete[] array; 00484 } 00485 }; 00486 00487 00488 class DiskAllocator : private noncopyable 00489 { 00490 stxxl::mutex mutex; 00491 00492 typedef std::pair<stxxl::int64, stxxl::int64> place; 00493 struct FirstFit : public std::binary_function<place, stxxl::int64, bool> 00494 { 00495 bool operator () ( 00496 const place & entry, 00497 const stxxl::int64 size) const 00498 { 00499 return (entry.second >= size); 00500 } 00501 }; 00502 struct OffCmp 00503 { 00504 bool operator () (const stxxl::int64 & off1, const stxxl::int64 & off2) 00505 { 00506 return off1 < off2; 00507 } 00508 }; 00509 00510 DiskAllocator() 00511 { } 00512 00513 protected: 00514 typedef std::map<stxxl::int64, stxxl::int64> sortseq; 00515 sortseq free_space; 00516 // sortseq used_space; 00517 stxxl::int64 free_bytes; 00518 stxxl::int64 disk_bytes; 00519 00520 void dump(); 00521 00522 void check_corruption(stxxl::int64 region_pos, stxxl::int64 region_size, 00523 sortseq::iterator pred, sortseq::iterator succ) 00524 { 00525 if (pred != free_space.end()) 00526 { 00527 if (pred->first <= region_pos && pred->first + pred->second > region_pos) 00528 { 00529 STXXL_THROW(bad_ext_alloc, "DiskAllocator::check_corruption", "Error: double deallocation of external memory " << 00530 "System info: P " << pred->first << " " << pred->second << " " << region_pos); 00531 } 00532 } 00533 if (succ != free_space.end()) 00534 { 00535 if (region_pos <= succ->first && region_pos + region_size > succ->first) 00536 { 00537 STXXL_THROW(bad_ext_alloc, "DiskAllocator::check_corruption", "Error: double deallocation of external memory " 00538 << "System info: S " << region_pos << " " << region_size << " " << succ->first); 00539 } 00540 } 00541 } 00542 00543 public: 00544 inline DiskAllocator(stxxl::int64 disk_size); 00545 00546 inline stxxl::int64 get_free_bytes() const 00547 { 00548 return free_bytes; 00549 } 00550 inline stxxl::int64 get_used_bytes() const 00551 { 00552 return disk_bytes - free_bytes; 00553 } 00554 inline stxxl::int64 get_total_bytes() const 00555 { 00556 return disk_bytes; 00557 } 00558 00559 template <unsigned BLK_SIZE> 00560 stxxl::int64 new_blocks(BIDArray<BLK_SIZE> & bids); 00561 00562 template <unsigned BLK_SIZE> 00563 stxxl::int64 new_blocks(BID<BLK_SIZE> * begin, 00564 BID<BLK_SIZE> * end); 00565 #if 0 00566 template <unsigned BLK_SIZE> 00567 void delete_blocks(const BIDArray<BLK_SIZE> & bids); 00568 #endif 00569 template <unsigned BLK_SIZE> 00570 void delete_block(const BID<BLK_SIZE> & bid); 00571 }; 00572 00573 DiskAllocator::DiskAllocator(stxxl::int64 disk_size) : 00574 free_bytes(disk_size), 00575 disk_bytes(disk_size) 00576 { 00577 free_space[0] = disk_size; 00578 } 00579 00580 00581 template <unsigned BLK_SIZE> 00582 stxxl::int64 DiskAllocator::new_blocks(BIDArray<BLK_SIZE> & bids) 00583 { 00584 return new_blocks(bids.begin(), bids.end()); 00585 } 00586 00587 template <unsigned BLK_SIZE> 00588 stxxl::int64 DiskAllocator::new_blocks(BID<BLK_SIZE> * begin, 00589 BID<BLK_SIZE> * end) 00590 { 00591 scoped_mutex_lock lock(mutex); 00592 00593 STXXL_VERBOSE2("DiskAllocator::new_blocks<BLK_SIZE>, BLK_SIZE = " << BLK_SIZE << 00594 ", free:" << free_bytes << " total:" << disk_bytes << 00595 ", blocks: " << (end - begin) << 00596 " begin: " << ((void *)(begin)) << " end: " << ((void *)(end))); 00597 00598 stxxl::int64 requested_size = 0; 00599 00600 typename BIDArray<BLK_SIZE>::iterator cur = begin; 00601 for ( ; cur != end; ++cur) 00602 { 00603 STXXL_VERBOSE2("Asking for a block with size: " << (cur->size)); 00604 requested_size += cur->size; 00605 } 00606 00607 if (free_bytes < requested_size) 00608 { 00609 STXXL_ERRMSG("External memory block allocation error: " << requested_size << 00610 " bytes requested, " << free_bytes << 00611 " bytes free. Trying to extend the external memory space..."); 00612 00613 00614 begin->offset = disk_bytes; // allocate at the end 00615 for (++begin; begin != end; ++begin) 00616 { 00617 begin->offset = (begin - 1)->offset + (begin - 1)->size; 00618 } 00619 disk_bytes += requested_size; 00620 00621 return disk_bytes; 00622 } 00623 00624 // dump(); 00625 00626 sortseq::iterator space = 00627 std::find_if(free_space.begin(), free_space.end(), 00628 bind2nd(FirstFit(), requested_size)); 00629 00630 if (space != free_space.end()) 00631 { 00632 stxxl::int64 region_pos = (*space).first; 00633 stxxl::int64 region_size = (*space).second; 00634 free_space.erase(space); 00635 if (region_size > requested_size) 00636 free_space[region_pos + requested_size] = region_size - requested_size; 00637 00638 begin->offset = region_pos; 00639 for (++begin; begin != end; ++begin) 00640 { 00641 begin->offset = (begin - 1)->offset + (begin - 1)->size; 00642 } 00643 free_bytes -= requested_size; 00644 //dump(); 00645 00646 return disk_bytes; 00647 } 00648 00649 // no contiguous region found 00650 STXXL_VERBOSE1("Warning, when allocating an external memory space, no contiguous region found"); 00651 STXXL_VERBOSE1("It might harm the performance"); 00652 if (requested_size == BLK_SIZE) 00653 { 00654 assert(end - begin == 1); 00655 00656 STXXL_ERRMSG("Warning: Severe external memory space fragmentation!"); 00657 dump(); 00658 00659 STXXL_ERRMSG("External memory block allocation error: " << requested_size << 00660 " bytes requested, " << free_bytes << 00661 " bytes free. Trying to extend the external memory space..."); 00662 00663 begin->offset = disk_bytes; // allocate at the end 00664 disk_bytes += BLK_SIZE; 00665 00666 return disk_bytes; 00667 } 00668 00669 assert(requested_size > BLK_SIZE); 00670 assert(end - begin > 1); 00671 00672 lock.unlock(); 00673 00674 typename BIDArray<BLK_SIZE>::iterator middle = begin + ((end - begin) / 2); 00675 new_blocks(begin, middle); 00676 new_blocks(middle, end); 00677 00678 return disk_bytes; 00679 } 00680 00681 00682 template <unsigned BLK_SIZE> 00683 void DiskAllocator::delete_block(const BID<BLK_SIZE> & bid) 00684 { 00685 scoped_mutex_lock lock(mutex); 00686 00687 STXXL_VERBOSE2("DiskAllocator::delete_block<BLK_SIZE>, BLK_SIZE = " << BLK_SIZE 00688 << ", free:" << free_bytes << " total:" << disk_bytes); 00689 STXXL_VERBOSE2("Deallocating a block with size: " << bid.size); 00690 //assert(bid.size); 00691 00692 //dump(); 00693 stxxl::int64 region_pos = bid.offset; 00694 stxxl::int64 region_size = bid.size; 00695 STXXL_VERBOSE2("Deallocating a block with size: " << region_size << " position: " << region_pos); 00696 if (!free_space.empty()) 00697 { 00698 sortseq::iterator succ = free_space.upper_bound(region_pos); 00699 sortseq::iterator pred = succ; 00700 pred--; 00701 check_corruption(region_pos, region_size, pred, succ); 00702 if (succ == free_space.end()) 00703 { 00704 if (pred == free_space.end()) 00705 { 00706 STXXL_ERRMSG("Error deallocating block at " << bid.offset << " size " << bid.size); 00707 STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ")); 00708 STXXL_ERRMSG(((pred == free_space.begin()) ? "pred==free_space.begin()" : "pred!=free_space.begin()")); 00709 STXXL_ERRMSG(((pred == free_space.end()) ? "pred==free_space.end()" : "pred!=free_space.end()")); 00710 STXXL_ERRMSG(((succ == free_space.begin()) ? "succ==free_space.begin()" : "succ!=free_space.begin()")); 00711 STXXL_ERRMSG(((succ == free_space.end()) ? "succ==free_space.end()" : "succ!=free_space.end()")); 00712 dump(); 00713 assert(pred != free_space.end()); 00714 } 00715 if ((*pred).first + (*pred).second == region_pos) 00716 { 00717 // coalesce with predecessor 00718 region_size += (*pred).second; 00719 region_pos = (*pred).first; 00720 free_space.erase(pred); 00721 } 00722 } 00723 else 00724 { 00725 if (free_space.size() > 1) 00726 { 00727 #if 0 00728 if (pred == succ) 00729 { 00730 STXXL_ERRMSG("Error deallocating block at " << bid.offset << " size " << bid.size); 00731 STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ")); 00732 STXXL_ERRMSG(((pred == free_space.begin()) ? "pred==free_space.begin()" : "pred!=free_space.begin()")); 00733 STXXL_ERRMSG(((pred == free_space.end()) ? "pred==free_space.end()" : "pred!=free_space.end()")); 00734 STXXL_ERRMSG(((succ == free_space.begin()) ? "succ==free_space.begin()" : "succ!=free_space.begin()")); 00735 STXXL_ERRMSG(((succ == free_space.end()) ? "succ==free_space.end()" : "succ!=free_space.end()")); 00736 dump(); 00737 assert(pred != succ); 00738 } 00739 #endif 00740 bool succ_is_not_the_first = (succ != free_space.begin()); 00741 if ((*succ).first == region_pos + region_size) 00742 { 00743 // coalesce with successor 00744 region_size += (*succ).second; 00745 free_space.erase(succ); 00746 } 00747 if (succ_is_not_the_first) 00748 { 00749 if (pred == free_space.end()) 00750 { 00751 STXXL_ERRMSG("Error deallocating block at " << bid.offset << " size " << bid.size); 00752 STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ")); 00753 STXXL_ERRMSG(((pred == free_space.begin()) ? "pred==free_space.begin()" : "pred!=free_space.begin()")); 00754 STXXL_ERRMSG(((pred == free_space.end()) ? "pred==free_space.end()" : "pred!=free_space.end()")); 00755 STXXL_ERRMSG(((succ == free_space.begin()) ? "succ==free_space.begin()" : "succ!=free_space.begin()")); 00756 STXXL_ERRMSG(((succ == free_space.end()) ? "succ==free_space.end()" : "succ!=free_space.end()")); 00757 dump(); 00758 assert(pred != free_space.end()); 00759 } 00760 if ((*pred).first + (*pred).second == region_pos) 00761 { 00762 // coalesce with predecessor 00763 region_size += (*pred).second; 00764 region_pos = (*pred).first; 00765 free_space.erase(pred); 00766 } 00767 } 00768 } 00769 else 00770 { 00771 if ((*succ).first == region_pos + region_size) 00772 { 00773 // coalesce with successor 00774 region_size += (*succ).second; 00775 free_space.erase(succ); 00776 } 00777 } 00778 } 00779 } 00780 00781 free_space[region_pos] = region_size; 00782 free_bytes += stxxl::int64(bid.size); 00783 00784 //dump(); 00785 } 00786 00787 #if 0 00788 template <unsigned BLK_SIZE> 00789 void DiskAllocator::delete_blocks(const BIDArray<BLK_SIZE> & bids) 00790 { 00791 STXXL_VERBOSE2("DiskAllocator::delete_blocks<BLK_SIZE> BLK_SIZE=" << BLK_SIZE << 00792 ", free:" << free_bytes << " total:" << disk_bytes); 00793 00794 unsigned i = 0; 00795 for ( ; i < bids.size(); ++i) 00796 { 00797 stxxl::int64 region_pos = bids[i].offset; 00798 stxxl::int64 region_size = bids[i].size; 00799 STXXL_VERBOSE2("Deallocating a block with size: " << region_size); 00800 assert(bids[i].size); 00801 00802 if (!free_space.empty()) 00803 { 00804 sortseq::iterator succ = 00805 free_space.upper_bound(region_pos); 00806 sortseq::iterator pred = succ; 00807 pred--; 00808 00809 if (succ != free_space.end() 00810 && (*succ).first == region_pos + region_size) 00811 { 00812 // coalesce with successor 00813 00814 region_size += (*succ).second; 00815 free_space.erase(succ); 00816 } 00817 if (pred != free_space.end() 00818 && (*pred).first + (*pred).second == region_pos) 00819 { 00820 // coalesce with predecessor 00821 00822 region_size += (*pred).second; 00823 region_pos = (*pred).first; 00824 free_space.erase(pred); 00825 } 00826 } 00827 free_space[region_pos] = region_size; 00828 } 00829 for (i = 0; i < bids.size(); ++i) 00830 free_bytes += stxxl::int64(bids[i].size); 00831 } 00832 #endif 00833 00836 class config : public singleton<config> 00837 { 00838 friend class singleton<config>; 00839 00840 struct DiskEntry 00841 { 00842 std::string path; 00843 std::string io_impl; 00844 stxxl::int64 size; 00845 bool delete_on_exit; 00846 }; 00847 std::vector<DiskEntry> disks_props; 00848 00849 // in disks_props, flash devices come after all regular disks 00850 unsigned first_flash; 00851 00852 config() 00853 { 00854 const char * cfg_path = getenv("STXXLCFG"); 00855 if (cfg_path) 00856 init(cfg_path); 00857 else 00858 init(); 00859 } 00860 00861 ~config() 00862 { 00863 for (unsigned i = 0; i < disks_props.size(); ++i) { 00864 if (disks_props[i].delete_on_exit) { 00865 STXXL_ERRMSG("Removing disk file created from default configuration: " << disks_props[i].path); 00866 unlink(disks_props[i].path.c_str()); 00867 } 00868 } 00869 } 00870 00871 void init(const char * config_path = "./.stxxl"); 00872 00873 public: 00876 inline unsigned disks_number() const 00877 { 00878 return disks_props.size(); 00879 } 00880 00883 inline std::pair<unsigned, unsigned> regular_disk_range() const 00884 { 00885 return std::pair<unsigned, unsigned>(0, first_flash); 00886 } 00887 00890 inline std::pair<unsigned, unsigned> flash_range() const 00891 { 00892 return std::pair<unsigned, unsigned>(first_flash, disks_props.size()); 00893 } 00894 00898 inline const std::string & disk_path(int disk) const 00899 { 00900 return disks_props[disk].path; 00901 } 00905 inline stxxl::int64 disk_size(int disk) const 00906 { 00907 return disks_props[disk].size; 00908 } 00911 inline const std::string & disk_io_impl(int disk) const 00912 { 00913 return disks_props[disk].io_impl; 00914 } 00915 }; 00916 00917 00918 class FileCreator 00919 { 00920 public: 00921 virtual stxxl::file * create(const std::string & io_impl, 00922 const std::string & filename, 00923 int options, int disk); 00924 00925 virtual ~FileCreator() { } 00926 }; 00927 00931 00934 struct basic_allocation_strategy 00935 { 00936 basic_allocation_strategy(int disks_begin, int disks_end); 00937 basic_allocation_strategy(); 00938 int operator () (int i) const; 00939 static const char * name(); 00940 }; 00941 00944 struct striping 00945 { 00946 int begin, diff; 00947 striping(int b, int e) : begin(b), diff(e - b) 00948 { } 00949 striping() : begin(0) 00950 { 00951 diff = config::get_instance()->disks_number(); 00952 } 00953 int operator () (int i) const 00954 { 00955 return begin + i % diff; 00956 } 00957 static const char * name() 00958 { 00959 return "striping"; 00960 } 00961 // FIXME WHY? 00962 virtual ~striping() 00963 { } 00964 }; 00965 00968 struct FR : public striping 00969 { 00970 random_number<random_uniform_fast> rnd; 00971 FR(int b, int e) : striping(b, e) 00972 { } 00973 FR() : striping() 00974 { } 00975 int operator () (int /*i*/) const 00976 { 00977 return begin + rnd(diff); 00978 } 00979 static const char * name() 00980 { 00981 return "fully randomized striping"; 00982 } 00983 }; 00984 00987 struct SR : public striping 00988 { 00989 random_number<random_uniform_fast> rnd; 00990 int offset; 00991 SR(int b, int e) : striping(b, e) 00992 { 00993 offset = rnd(diff); 00994 } 00995 SR() : striping() 00996 { 00997 offset = rnd(diff); 00998 } 00999 int operator () (int i) const 01000 { 01001 return begin + (i + offset) % diff; 01002 } 01003 static const char * name() 01004 { 01005 return "simple randomized striping"; 01006 } 01007 }; 01008 01011 struct RC : public striping 01012 { 01013 std::vector<int> perm; 01014 01015 RC(int b, int e) : striping(b, e), perm(diff) 01016 { 01017 for (int i = 0; i < diff; i++) 01018 perm[i] = i; 01019 01020 stxxl::random_number<random_uniform_fast> rnd; 01021 std::random_shuffle(perm.begin(), perm.end(), rnd __STXXL_FORCE_SEQUENTIAL); 01022 } 01023 RC() : striping(), perm(diff) 01024 { 01025 for (int i = 0; i < diff; i++) 01026 perm[i] = i; 01027 01028 random_number<random_uniform_fast> rnd; 01029 std::random_shuffle(perm.begin(), perm.end(), rnd __STXXL_FORCE_SEQUENTIAL); 01030 } 01031 int operator () (int i) const 01032 { 01033 return begin + perm[i % diff]; 01034 } 01035 static const char * name() 01036 { 01037 return "randomized cycling striping"; 01038 } 01039 }; 01040 01041 struct RC_disk : public RC 01042 { 01043 RC_disk(int b, int e) : RC(b, e) 01044 { } 01045 RC_disk() : RC(config::get_instance()->regular_disk_range().first, config::get_instance()->regular_disk_range().second) 01046 { } 01047 static const char * name() 01048 { 01049 return "Randomized cycling striping on regular disks"; 01050 } 01051 }; 01052 01053 struct RC_flash : public RC 01054 { 01055 RC_flash(int b, int e) : RC(b, e) 01056 { } 01057 RC_flash() : RC(config::get_instance()->flash_range().first, config::get_instance()->flash_range().second) 01058 { } 01059 static const char * name() 01060 { 01061 return "Randomized cycling striping on flash devices"; 01062 } 01063 }; 01064 01067 struct single_disk 01068 { 01069 const int disk; 01070 single_disk(int d, int = 0) : disk(d) 01071 { } 01072 01073 single_disk() : disk(0) 01074 { } 01075 int operator () (int /*i*/) const 01076 { 01077 return disk; 01078 } 01079 static const char * name() 01080 { 01081 return "single disk"; 01082 } 01083 }; 01084 01086 01088 template <class BaseAllocator_> 01089 struct offset_allocator 01090 { 01091 BaseAllocator_ base; 01092 int_type offset; 01096 offset_allocator(int_type offset_) : base(), offset(offset_) { } 01101 offset_allocator(int_type offset_, BaseAllocator_ & base_) : base(base_), offset(offset_) { } 01102 int operator () (int_type i) const 01103 { 01104 return base(offset + i); 01105 } 01106 }; 01107 01109 01110 #if 0 // deprecated 01111 01113 template <class bid_it> 01114 struct bid_iterator_traits 01115 { 01116 bid_it * a; 01117 enum 01118 { 01119 block_size = bid_it::block_size 01120 }; 01121 }; 01122 01123 template <unsigned blk_sz> 01124 struct bid_iterator_traits<BID<blk_sz> *> 01125 { 01126 enum 01127 { 01128 block_size = blk_sz 01129 }; 01130 }; 01131 01132 01133 template <unsigned blk_sz, class X> 01134 struct bid_iterator_traits<__gnu_cxx::__normal_iterator<BID<blk_sz> *, X> > 01135 { 01136 enum 01137 { 01138 block_size = blk_sz 01139 }; 01140 }; 01141 01142 template <unsigned blk_sz, class X, class Y> 01143 struct bid_iterator_traits<std::_List_iterator<BID<blk_sz>, X, Y> > 01144 { 01145 enum 01146 { 01147 block_size = blk_sz 01148 }; 01149 }; 01150 01151 template <unsigned blk_sz, class X> 01152 struct bid_iterator_traits<typename std::vector<BID<blk_sz>, X>::iterator> 01153 { 01154 enum 01155 { 01156 block_size = blk_sz 01157 }; 01158 }; 01159 01160 #endif 01161 01163 01166 class block_manager : public singleton<block_manager> 01167 { 01168 friend class singleton<block_manager>; 01169 01170 DiskAllocator ** disk_allocators; 01171 file ** disk_files; 01172 01173 unsigned ndisks; 01174 block_manager(); 01175 01176 protected: 01177 template <class BIDType, class DiskAssgnFunctor, class BIDIteratorClass> 01178 void new_blocks_int( 01179 const unsigned_type nblocks, 01180 DiskAssgnFunctor functor, 01181 BIDIteratorClass out); 01182 01183 public: 01185 01192 template <class DiskAssgnFunctor, class BIDIteratorClass> 01193 void new_blocks( 01194 DiskAssgnFunctor functor, 01195 BIDIteratorClass bidbegin, 01196 BIDIteratorClass bidend); 01197 01206 template <class BlockType, class DiskAssgnFunctor, class BIDIteratorClass> 01207 void new_blocks( 01208 const unsigned_type nblocks, 01209 DiskAssgnFunctor functor, 01210 BIDIteratorClass out); 01211 01212 01214 01218 template <class BIDIteratorClass> 01219 void delete_blocks(const BIDIteratorClass & bidbegin, const BIDIteratorClass & bidend); 01220 01223 template <unsigned BLK_SIZE> 01224 void delete_block(const BID<BLK_SIZE> & bid); 01225 01226 ~block_manager(); 01227 }; 01228 01229 01230 template <class BIDType, class DiskAssgnFunctor, class OutputIterator> 01231 void block_manager::new_blocks_int( 01232 const unsigned_type nblocks, 01233 DiskAssgnFunctor functor, 01234 OutputIterator out) 01235 { 01236 typedef BIDType bid_type; 01237 typedef BIDArray<bid_type::t_size> bid_array_type; 01238 01239 // bid_type tmpbid; 01240 int_type * bl = new int_type[ndisks]; 01241 bid_array_type * disk_bids = new bid_array_type[ndisks]; 01242 file ** disk_ptrs = new file *[nblocks]; 01243 01244 memset(bl, 0, ndisks * sizeof(int_type)); 01245 01246 unsigned_type i = 0; 01247 //OutputIterator it = out; 01248 for ( ; i < nblocks; ++i /* , ++it*/) 01249 { 01250 const int disk = functor(i); 01251 disk_ptrs[i] = disk_files[disk]; 01252 //(*it).storage = disk_files[disk]; 01253 bl[disk]++; 01254 } 01255 01256 for (i = 0; i < ndisks; ++i) 01257 { 01258 if (bl[i]) 01259 { 01260 disk_bids[i].resize(bl[i]); 01261 const stxxl::int64 old_capacity = 01262 disk_allocators[i]->get_total_bytes(); 01263 const stxxl::int64 new_capacity = 01264 disk_allocators[i]->new_blocks(disk_bids[i]); 01265 if (old_capacity != new_capacity) 01266 { 01267 // resize the file 01268 disk_files[i]->set_size(new_capacity); 01269 if (new_capacity != disk_allocators[i]->get_total_bytes()) 01270 STXXL_ERRMSG("File resizing failed: actual size " << disk_allocators[i]->get_total_bytes() << " != requested size " << new_capacity); 01271 } 01272 } 01273 } 01274 01275 memset(bl, 0, ndisks * sizeof(int_type)); 01276 01277 OutputIterator it = out; 01278 for (i = 0 /*,it = out */; i != nblocks; ++it, ++i) 01279 { 01280 //int disk = (*it).storage->get_id(); 01281 //(*it).offset = disk_bids[disk][bl[disk]++].offset; 01282 const int disk = disk_ptrs[i]->get_id(); 01283 bid_type bid(disk_ptrs[i], disk_bids[disk][bl[disk]++].offset); 01284 *it = bid; 01285 STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:new " << FMT_BID(bid)); 01286 } 01287 01288 delete[] bl; 01289 delete[] disk_bids; 01290 delete[] disk_ptrs; 01291 } 01292 01293 template <class BlockType, class DiskAssgnFunctor, class OutputIterator> 01294 void block_manager::new_blocks( 01295 const unsigned_type nblocks, 01296 DiskAssgnFunctor functor, 01297 OutputIterator out) 01298 { 01299 typedef typename BlockType::bid_type bid_type; 01300 new_blocks_int<bid_type>(nblocks, functor, out); 01301 } 01302 01303 template <class DiskAssgnFunctor, class BIDIteratorClass> 01304 void block_manager::new_blocks( 01305 DiskAssgnFunctor functor, 01306 BIDIteratorClass bidbegin, 01307 BIDIteratorClass bidend) 01308 { 01309 typedef typename std::iterator_traits<BIDIteratorClass>::value_type bid_type; 01310 01311 unsigned_type nblocks = 0; 01312 01313 BIDIteratorClass bidbegin_copy(bidbegin); 01314 while (bidbegin_copy != bidend) 01315 { 01316 ++bidbegin_copy; 01317 ++nblocks; 01318 } 01319 01320 new_blocks_int<bid_type>(nblocks, functor, bidbegin); 01321 } 01322 01323 01324 template <unsigned BLK_SIZE> 01325 void block_manager::delete_block(const BID<BLK_SIZE> & bid) 01326 { 01327 STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:delete " << FMT_BID(bid)); 01328 // do not uncomment it 01329 //assert(bid.storage->get_id() < config::get_instance()->disks_number()); 01330 if (bid.storage->get_id() == -1) 01331 return; // self managed disk 01332 assert(bid.storage->get_id() >= 0); 01333 disk_allocators[bid.storage->get_id()]->delete_block(bid); 01334 disk_files[bid.storage->get_id()]->delete_region(bid.offset, bid.size); 01335 } 01336 01337 01338 template <class BIDIteratorClass> 01339 void block_manager::delete_blocks( 01340 const BIDIteratorClass & bidbegin, 01341 const BIDIteratorClass & bidend) 01342 { 01343 for (BIDIteratorClass it = bidbegin; it != bidend; it++) 01344 { 01345 delete_block(*it); 01346 } 01347 } 01348 01349 #ifndef STXXL_DEFAULT_ALLOC_STRATEGY 01350 #define STXXL_DEFAULT_ALLOC_STRATEGY stxxl::RC 01351 #endif 01352 01353 // in bytes 01354 #ifndef STXXL_DEFAULT_BLOCK_SIZE 01355 #define STXXL_DEFAULT_BLOCK_SIZE(type) (2 * 1024 * 1024) // use traits 01356 #endif 01357 01359 01360 __STXXL_END_NAMESPACE 01361 01362 01363 #endif // !STXXL_MNG_HEADER 01364 // vim: et:ts=4:sw=4