00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
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 , void * ptr)
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
00407
00408
00409
00410
00411
00412
00413
00414
00415
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
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;
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
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
00645
00646 return disk_bytes;
00647 }
00648
00649
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;
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
00691
00692
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
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
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
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
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
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
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
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
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
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 ) 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 ) 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
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
01248 for ( ; i < nblocks; ++i )
01249 {
01250 const int disk = functor(i);
01251 disk_ptrs[i] = disk_files[disk];
01252
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
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 ; i != nblocks; ++it, ++i)
01279 {
01280
01281
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
01329
01330 if (bid.storage->get_id() == -1)
01331 return;
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
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