Stxxl  1.2.1
mng.h
1 /***************************************************************************
2  * include/stxxl/bits/mng/mng.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2004 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7  * Copyright (C) 2007 Johannes Singler <singler@ira.uka.de>
8  * Copyright (C) 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_MNG_HEADER
16 #define STXXL_MNG_HEADER
17 
18 #include <memory>
19 #include <iostream>
20 #include <iomanip>
21 #include <fstream>
22 #include <vector>
23 #include <list>
24 #include <map>
25 #include <algorithm>
26 #include <string>
27 #include <cstdlib>
28 
29 #ifdef STXXL_BOOST_CONFIG
30  #include <boost/config.hpp>
31 #endif
32 
33 #ifdef BOOST_MSVC
34 #include <memory.h>
35 #endif
36 
37 #include <stxxl/bits/io/iobase.h>
38 #include <stxxl/bits/noncopyable.h>
39 #include <stxxl/bits/common/rand.h>
40 #include <stxxl/bits/common/aligned_alloc.h>
41 #include <stxxl/bits/common/debug.h>
42 #include <stxxl/bits/parallel.h>
43 #include <stxxl/bits/singleton.h>
44 
45 #ifndef STXXL_VERBOSE_BLOCK_LIFE_CYCLE
46 #define STXXL_VERBOSE_BLOCK_LIFE_CYCLE STXXL_VERBOSE2
47 #endif
48 #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
49 
50 
51 __STXXL_BEGIN_NAMESPACE
52 
57 
59 
61 template <unsigned SIZE>
62 struct BID
63 {
64  enum
65  {
66  size = SIZE,
67  t_size = SIZE
68  };
70  stxxl::int64 offset;
71  BID() : storage(NULL), offset(0) { }
72  bool valid() const
73  {
74  return storage;
75  }
76  BID(file * s, stxxl::int64 o) : storage(s), offset(o) { }
77  BID(const BID & obj) : storage(obj.storage), offset(obj.offset) { }
78  template <unsigned BlockSize>
79  explicit BID(const BID<BlockSize> & obj) : storage(obj.storage), offset(obj.offset) { }
80 };
81 
82 
84 
86 template <>
87 struct BID<0>
88 {
90  stxxl::int64 offset;
91  unsigned size;
92  enum
93  {
94  t_size = 0
95  };
96  BID() : storage(NULL), offset(0), size(0) { }
97  BID(file * f, stxxl::int64 o, unsigned s) : storage(f), offset(o), size(s) { }
98  bool valid() const
99  {
100  return storage;
101  }
102 };
103 
104 template <unsigned blk_sz>
105 bool operator == (const BID<blk_sz> & a, const BID<blk_sz> & b)
106 {
107  return (a.storage == b.storage) && (a.offset == b.offset) && (a.size == b.size);
108 }
109 
110 template <unsigned blk_sz>
111 bool operator != (const BID<blk_sz> & a, const BID<blk_sz> & b)
112 {
113  return (a.storage != b.storage) || (a.offset != b.offset) || (a.size != b.size);
114 }
115 
116 
117 template <unsigned blk_sz>
118 std::ostream & operator << (std::ostream & s, const BID<blk_sz> & bid)
119 {
120  s << " storage file addr: " << bid.storage;
121  s << " offset: " << bid.offset;
122  s << " size: " << bid.size;
123  return s;
124 }
125 
126 
127 template <unsigned bytes>
128 class filler_struct__
129 {
130  typedef unsigned char byte_type;
131  byte_type filler_array_[bytes];
132 
133 public:
134  filler_struct__() { STXXL_VERBOSE2("filler_struct__ is allocated"); }
135 };
136 
137 template <>
138 class filler_struct__<0>
139 {
140  typedef unsigned char byte_type;
141 
142 public:
143  filler_struct__() { STXXL_VERBOSE2("filler_struct__ is allocated"); }
144 };
145 
147 template <class T, unsigned Size_>
149 {
150 public:
151  typedef T type;
152  typedef T value_type;
153  typedef T & reference;
154  typedef const T & const_reference;
155  typedef type * pointer;
156  typedef pointer iterator;
157  typedef const type * const_iterator;
158 
159  enum
160  {
161  size = Size_
162  };
163 
165  T elem[size];
166 
167  element_block() { STXXL_VERBOSE2("element_block is allocated"); }
168 
170  reference operator [] (int i)
171  {
172  return elem[i];
173  }
174 
176  iterator begin()
177  {
178  return elem;
179  }
181  const_iterator begin() const
182  {
183  return elem;
184  }
186  const_iterator cbegin() const
187  {
188  return begin();
189  }
191  iterator end()
192  {
193  return elem + size;
194  }
196  const_iterator end() const
197  {
198  return elem + size;
199  }
201  const_iterator cend() const
202  {
203  return end();
204  }
205 };
206 
208 template <class T, unsigned Size_, unsigned RawSize_, unsigned NBids_ = 0>
209 class block_w_bids : public element_block<T, Size_>
210 {
211 public:
212  enum
213  {
214  raw_size = RawSize_,
215  nbids = NBids_
216  };
217  typedef BID<raw_size> bid_type;
218 
220  bid_type ref[nbids];
221 
224  {
225  return ref[i];
226  }
227 
228  block_w_bids() { STXXL_VERBOSE2("block_w_bids is allocated"); }
229 };
230 
231 template <class T, unsigned Size_, unsigned RawSize_>
232 class block_w_bids<T, Size_, RawSize_, 0>: public element_block<T, Size_>
233 {
234 public:
235  enum
236  {
237  raw_size = RawSize_,
238  nbids = 0
239  };
240  typedef BID<raw_size> bid_type;
241 
242  block_w_bids() { STXXL_VERBOSE2("block_w_bids is allocated"); }
243 };
244 
246 template <class T_, unsigned RawSize_, unsigned NBids_, class InfoType_ = void>
248  public block_w_bids<T_, ((RawSize_ - sizeof(BID<RawSize_>) * NBids_ - sizeof(InfoType_)) / sizeof(T_)), RawSize_, NBids_>
249 {
250 public:
252  typedef InfoType_ info_type;
253 
256 
257  enum { size = ((RawSize_ - sizeof(BID<RawSize_>) * NBids_ - sizeof(InfoType_)) / sizeof(T_)) };
258 
259 public:
260  block_w_info() { STXXL_VERBOSE2("block_w_info is allocated"); }
261 };
262 
263 template <class T_, unsigned RawSize_, unsigned NBids_>
264 class block_w_info<T_, RawSize_, NBids_, void>:
265  public block_w_bids<T_, ((RawSize_ - sizeof(BID<RawSize_>) * NBids_) / sizeof(T_)), RawSize_, NBids_>
266 {
267 public:
268  typedef void info_type;
269  enum { size = ((RawSize_ - sizeof(BID<RawSize_>) * NBids_) / sizeof(T_)) };
270 
271 public:
272  block_w_info() { STXXL_VERBOSE2("block_w_info is allocated"); }
273 };
274 
276 
289 template <unsigned RawSize_, class T_, unsigned NRef_ = 0, class InfoType_ = void>
290 class typed_block :
291  public block_w_info<T_, RawSize_, NRef_, InfoType_>,
292  public filler_struct__<(RawSize_ - sizeof(block_w_info<T_, RawSize_, NRef_, InfoType_>))>
293 {
294 public:
295  typedef T_ type;
296  typedef T_ value_type;
297  typedef T_ & reference;
298  typedef const T_ & const_reference;
299  typedef type * pointer;
300  typedef pointer iterator;
301  typedef type const * const_iterator;
302 
303  enum { has_filler = (RawSize_ != sizeof(block_w_info<T_, RawSize_, NRef_, InfoType_>)) };
304 
305  typedef BID<RawSize_> bid_type;
306 
307  typed_block()
308  {
309  STXXL_VERBOSE2("typed_block is allocated");
310  }
311 
312  enum
313  {
314  raw_size = RawSize_,
316  };
317 
323  request_ptr write(const BID<raw_size> & bid,
325  {
326  STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:write " << FMT_BID(bid));
327  return bid.storage->awrite(
328  this,
329  bid.offset,
330  raw_size,
331  on_cmpl);
332  }
333 
339  request_ptr read(const BID<raw_size> & bid,
341  {
342  STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:read " << FMT_BID(bid));
343  return bid.storage->aread(this, bid.offset, raw_size, on_cmpl);
344  }
345 
346  static void * operator new[] (size_t bytes)
347  {
348  unsigned_type meta_info_size = bytes % raw_size;
349  STXXL_VERBOSE1("typed::block operator new[]: Meta info size: " << meta_info_size);
350 
351  void * result = aligned_alloc<BLOCK_ALIGN>(bytes, meta_info_size);
352  #ifdef STXXL_VALGRIND_TYPED_BLOCK_INITIALIZE_ZERO
353  memset(result, 0, bytes);
354  #endif
355  char * tmp = (char *)result;
356  STXXL_DEBUGMON_DO(block_allocated(tmp, tmp + bytes, RawSize_));
357  tmp += RawSize_;
358  while (tmp < ((char *)result) + bytes)
359  {
360  STXXL_DEBUGMON_DO(block_allocated(tmp, ((char *)result) + bytes, RawSize_));
361  tmp += RawSize_;
362  }
363  return result;
364  }
365 
366  static void * operator new (size_t bytes)
367  {
368  unsigned_type meta_info_size = bytes % raw_size;
369  STXXL_VERBOSE1("typed::block operator new: Meta info size: " << meta_info_size);
370 
371  void * result = aligned_alloc<BLOCK_ALIGN>(bytes, meta_info_size);
372  #ifdef STXXL_VALGRIND_TYPED_BLOCK_INITIALIZE_ZERO
373  memset(result, 0, bytes);
374  #endif
375  char * tmp = (char *)result;
376  STXXL_DEBUGMON_DO(block_allocated(tmp, tmp + bytes, RawSize_));
377  tmp += RawSize_;
378  while (tmp < ((char *)result) + bytes)
379  {
380  STXXL_DEBUGMON_DO(block_allocated(tmp, ((char *)result) + bytes, RawSize_));
381  tmp += RawSize_;
382  }
383  return result;
384  }
385 
386  static void * operator new (size_t /*bytes*/, void * ptr) // construct object in existing memory
387  {
388  return ptr;
389  }
390 
391  static void operator delete[] (void * ptr)
392  {
393  STXXL_DEBUGMON_DO(block_deallocated((char *)ptr));
394  aligned_dealloc<BLOCK_ALIGN>(ptr);
395  }
396 
397  static void operator delete (void * ptr)
398  {
399  STXXL_DEBUGMON_DO(block_deallocated((char *)ptr));
400  aligned_dealloc<BLOCK_ALIGN>(ptr);
401  }
402 
403  static void operator delete (void *, void *)
404  { }
405 
406  // STRANGE: implementing destructor makes g++ allocate
407  // additional 4 bytes in the beginning of every array
408  // of this type !? makes aligning to 4K boundaries difficult
409  //
410  // http://www.cc.gatech.edu/grads/j/Seung.Won.Jun/tips/pl/node4.html :
411  // "One interesting thing is the array allocator requires more memory
412  // than the array size multiplied by the size of an element, by a
413  // difference of delta for metadata a compiler needs. It happens to
414  // be 8 bytes long in g++."
415  // ~typed_block() { }
416 };
417 
418 
419 #if 0
420 template <unsigned BLK_SIZE>
421 class BIDArray : public std::vector<BID<BLK_SIZE> >
422 {
423 public:
424  BIDArray(std::vector<BID<BLK_SIZE> >::size_type size = 0) : std::vector<BID<BLK_SIZE> >(size) { }
425 };
426 #endif
427 
428 template <unsigned BLK_SIZE>
429 class BIDArray : private noncopyable
430 {
431 protected:
432  unsigned_type _size;
433  BID<BLK_SIZE> * array;
434 
435 public:
436  typedef BID<BLK_SIZE> & reference;
437  typedef BID<BLK_SIZE> * iterator;
438  typedef const BID<BLK_SIZE> * const_iterator;
439  BIDArray() : _size(0), array(NULL)
440  { }
441  iterator begin()
442  {
443  return array;
444  }
445  iterator end()
446  {
447  return array + _size;
448  }
449 
450  BIDArray(unsigned_type size) : _size(size)
451  {
452  array = new BID<BLK_SIZE>[size];
453  }
454  unsigned_type size() const
455  {
456  return _size;
457  }
458  reference operator [] (int_type i)
459  {
460  return array[i];
461  }
462  void resize(unsigned_type newsize)
463  {
464  if (array)
465  {
466  STXXL_MSG("Warning: resizing nonempty BIDArray");
467  BID<BLK_SIZE> * tmp = array;
468  array = new BID<BLK_SIZE>[newsize];
469  memcpy((void *)array, (void *)tmp,
470  sizeof(BID<BLK_SIZE>) * (STXXL_MIN(_size, newsize)));
471  delete[] tmp;
472  _size = newsize;
473  }
474  else
475  {
476  array = new BID<BLK_SIZE>[newsize];
477  _size = newsize;
478  }
479  }
480  ~BIDArray()
481  {
482  if (array)
483  delete[] array;
484  }
485 };
486 
487 
488 class DiskAllocator : private noncopyable
489 {
490  stxxl::mutex mutex;
491 
492  typedef std::pair<stxxl::int64, stxxl::int64> place;
493  struct FirstFit : public std::binary_function<place, stxxl::int64, bool>
494  {
495  bool operator () (
496  const place & entry,
497  const stxxl::int64 size) const
498  {
499  return (entry.second >= size);
500  }
501  };
502  struct OffCmp
503  {
504  bool operator () (const stxxl::int64 & off1, const stxxl::int64 & off2)
505  {
506  return off1 < off2;
507  }
508  };
509 
510  DiskAllocator()
511  { }
512 
513 protected:
514  typedef std::map<stxxl::int64, stxxl::int64> sortseq;
515  sortseq free_space;
516  // sortseq used_space;
517  stxxl::int64 free_bytes;
518  stxxl::int64 disk_bytes;
519 
520  void dump();
521 
522  void check_corruption(stxxl::int64 region_pos, stxxl::int64 region_size,
523  sortseq::iterator pred, sortseq::iterator succ)
524  {
525  if (pred != free_space.end())
526  {
527  if (pred->first <= region_pos && pred->first + pred->second > region_pos)
528  {
529  STXXL_THROW(bad_ext_alloc, "DiskAllocator::check_corruption", "Error: double deallocation of external memory " <<
530  "System info: P " << pred->first << " " << pred->second << " " << region_pos);
531  }
532  }
533  if (succ != free_space.end())
534  {
535  if (region_pos <= succ->first && region_pos + region_size > succ->first)
536  {
537  STXXL_THROW(bad_ext_alloc, "DiskAllocator::check_corruption", "Error: double deallocation of external memory "
538  << "System info: S " << region_pos << " " << region_size << " " << succ->first);
539  }
540  }
541  }
542 
543 public:
544  inline DiskAllocator(stxxl::int64 disk_size);
545 
546  inline stxxl::int64 get_free_bytes() const
547  {
548  return free_bytes;
549  }
550  inline stxxl::int64 get_used_bytes() const
551  {
552  return disk_bytes - free_bytes;
553  }
554  inline stxxl::int64 get_total_bytes() const
555  {
556  return disk_bytes;
557  }
558 
559  template <unsigned BLK_SIZE>
560  stxxl::int64 new_blocks(BIDArray<BLK_SIZE> & bids);
561 
562  template <unsigned BLK_SIZE>
563  stxxl::int64 new_blocks(BID<BLK_SIZE> * begin,
564  BID<BLK_SIZE> * end);
565 #if 0
566  template <unsigned BLK_SIZE>
567  void delete_blocks(const BIDArray<BLK_SIZE> & bids);
568 #endif
569  template <unsigned BLK_SIZE>
570  void delete_block(const BID<BLK_SIZE> & bid);
571 };
572 
573 DiskAllocator::DiskAllocator(stxxl::int64 disk_size) :
574  free_bytes(disk_size),
575  disk_bytes(disk_size)
576 {
577  free_space[0] = disk_size;
578 }
579 
580 
581 template <unsigned BLK_SIZE>
582 stxxl::int64 DiskAllocator::new_blocks(BIDArray<BLK_SIZE> & bids)
583 {
584  return new_blocks(bids.begin(), bids.end());
585 }
586 
587 template <unsigned BLK_SIZE>
588 stxxl::int64 DiskAllocator::new_blocks(BID<BLK_SIZE> * begin,
589  BID<BLK_SIZE> * end)
590 {
591  scoped_mutex_lock lock(mutex);
592 
593  STXXL_VERBOSE2("DiskAllocator::new_blocks<BLK_SIZE>, BLK_SIZE = " << BLK_SIZE <<
594  ", free:" << free_bytes << " total:" << disk_bytes <<
595  ", blocks: " << (end - begin) <<
596  " begin: " << ((void *)(begin)) << " end: " << ((void *)(end)));
597 
598  stxxl::int64 requested_size = 0;
599 
600  typename BIDArray<BLK_SIZE>::iterator cur = begin;
601  for ( ; cur != end; ++cur)
602  {
603  STXXL_VERBOSE2("Asking for a block with size: " << (cur->size));
604  requested_size += cur->size;
605  }
606 
607  if (free_bytes < requested_size)
608  {
609  STXXL_ERRMSG("External memory block allocation error: " << requested_size <<
610  " bytes requested, " << free_bytes <<
611  " bytes free. Trying to extend the external memory space...");
612 
613 
614  begin->offset = disk_bytes; // allocate at the end
615  for (++begin; begin != end; ++begin)
616  {
617  begin->offset = (begin - 1)->offset + (begin - 1)->size;
618  }
619  disk_bytes += requested_size;
620 
621  return disk_bytes;
622  }
623 
624  // dump();
625 
626  sortseq::iterator space =
627  std::find_if(free_space.begin(), free_space.end(),
628  bind2nd(FirstFit(), requested_size));
629 
630  if (space != free_space.end())
631  {
632  stxxl::int64 region_pos = (*space).first;
633  stxxl::int64 region_size = (*space).second;
634  free_space.erase(space);
635  if (region_size > requested_size)
636  free_space[region_pos + requested_size] = region_size - requested_size;
637 
638  begin->offset = region_pos;
639  for (++begin; begin != end; ++begin)
640  {
641  begin->offset = (begin - 1)->offset + (begin - 1)->size;
642  }
643  free_bytes -= requested_size;
644  //dump();
645 
646  return disk_bytes;
647  }
648 
649  // no contiguous region found
650  STXXL_VERBOSE1("Warning, when allocating an external memory space, no contiguous region found");
651  STXXL_VERBOSE1("It might harm the performance");
652  if (requested_size == BLK_SIZE)
653  {
654  assert(end - begin == 1);
655 
656  STXXL_ERRMSG("Warning: Severe external memory space fragmentation!");
657  dump();
658 
659  STXXL_ERRMSG("External memory block allocation error: " << requested_size <<
660  " bytes requested, " << free_bytes <<
661  " bytes free. Trying to extend the external memory space...");
662 
663  begin->offset = disk_bytes; // allocate at the end
664  disk_bytes += BLK_SIZE;
665 
666  return disk_bytes;
667  }
668 
669  assert(requested_size > BLK_SIZE);
670  assert(end - begin > 1);
671 
672  lock.unlock();
673 
674  typename BIDArray<BLK_SIZE>::iterator middle = begin + ((end - begin) / 2);
675  new_blocks(begin, middle);
676  new_blocks(middle, end);
677 
678  return disk_bytes;
679 }
680 
681 
682 template <unsigned BLK_SIZE>
683 void DiskAllocator::delete_block(const BID<BLK_SIZE> & bid)
684 {
685  scoped_mutex_lock lock(mutex);
686 
687  STXXL_VERBOSE2("DiskAllocator::delete_block<BLK_SIZE>, BLK_SIZE = " << BLK_SIZE
688  << ", free:" << free_bytes << " total:" << disk_bytes);
689  STXXL_VERBOSE2("Deallocating a block with size: " << bid.size);
690  //assert(bid.size);
691 
692  //dump();
693  stxxl::int64 region_pos = bid.offset;
694  stxxl::int64 region_size = bid.size;
695  STXXL_VERBOSE2("Deallocating a block with size: " << region_size << " position: " << region_pos);
696  if (!free_space.empty())
697  {
698  sortseq::iterator succ = free_space.upper_bound(region_pos);
699  sortseq::iterator pred = succ;
700  pred--;
701  check_corruption(region_pos, region_size, pred, succ);
702  if (succ == free_space.end())
703  {
704  if (pred == free_space.end())
705  {
706  STXXL_ERRMSG("Error deallocating block at " << bid.offset << " size " << bid.size);
707  STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ"));
708  STXXL_ERRMSG(((pred == free_space.begin()) ? "pred==free_space.begin()" : "pred!=free_space.begin()"));
709  STXXL_ERRMSG(((pred == free_space.end()) ? "pred==free_space.end()" : "pred!=free_space.end()"));
710  STXXL_ERRMSG(((succ == free_space.begin()) ? "succ==free_space.begin()" : "succ!=free_space.begin()"));
711  STXXL_ERRMSG(((succ == free_space.end()) ? "succ==free_space.end()" : "succ!=free_space.end()"));
712  dump();
713  assert(pred != free_space.end());
714  }
715  if ((*pred).first + (*pred).second == region_pos)
716  {
717  // coalesce with predecessor
718  region_size += (*pred).second;
719  region_pos = (*pred).first;
720  free_space.erase(pred);
721  }
722  }
723  else
724  {
725  if (free_space.size() > 1)
726  {
727 #if 0
728  if (pred == succ)
729  {
730  STXXL_ERRMSG("Error deallocating block at " << bid.offset << " size " << bid.size);
731  STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ"));
732  STXXL_ERRMSG(((pred == free_space.begin()) ? "pred==free_space.begin()" : "pred!=free_space.begin()"));
733  STXXL_ERRMSG(((pred == free_space.end()) ? "pred==free_space.end()" : "pred!=free_space.end()"));
734  STXXL_ERRMSG(((succ == free_space.begin()) ? "succ==free_space.begin()" : "succ!=free_space.begin()"));
735  STXXL_ERRMSG(((succ == free_space.end()) ? "succ==free_space.end()" : "succ!=free_space.end()"));
736  dump();
737  assert(pred != succ);
738  }
739 #endif
740  bool succ_is_not_the_first = (succ != free_space.begin());
741  if ((*succ).first == region_pos + region_size)
742  {
743  // coalesce with successor
744  region_size += (*succ).second;
745  free_space.erase(succ);
746  }
747  if (succ_is_not_the_first)
748  {
749  if (pred == free_space.end())
750  {
751  STXXL_ERRMSG("Error deallocating block at " << bid.offset << " size " << bid.size);
752  STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ"));
753  STXXL_ERRMSG(((pred == free_space.begin()) ? "pred==free_space.begin()" : "pred!=free_space.begin()"));
754  STXXL_ERRMSG(((pred == free_space.end()) ? "pred==free_space.end()" : "pred!=free_space.end()"));
755  STXXL_ERRMSG(((succ == free_space.begin()) ? "succ==free_space.begin()" : "succ!=free_space.begin()"));
756  STXXL_ERRMSG(((succ == free_space.end()) ? "succ==free_space.end()" : "succ!=free_space.end()"));
757  dump();
758  assert(pred != free_space.end());
759  }
760  if ((*pred).first + (*pred).second == region_pos)
761  {
762  // coalesce with predecessor
763  region_size += (*pred).second;
764  region_pos = (*pred).first;
765  free_space.erase(pred);
766  }
767  }
768  }
769  else
770  {
771  if ((*succ).first == region_pos + region_size)
772  {
773  // coalesce with successor
774  region_size += (*succ).second;
775  free_space.erase(succ);
776  }
777  }
778  }
779  }
780 
781  free_space[region_pos] = region_size;
782  free_bytes += stxxl::int64(bid.size);
783 
784  //dump();
785 }
786 
787 #if 0
788 template <unsigned BLK_SIZE>
789 void DiskAllocator::delete_blocks(const BIDArray<BLK_SIZE> & bids)
790 {
791  STXXL_VERBOSE2("DiskAllocator::delete_blocks<BLK_SIZE> BLK_SIZE=" << BLK_SIZE <<
792  ", free:" << free_bytes << " total:" << disk_bytes);
793 
794  unsigned i = 0;
795  for ( ; i < bids.size(); ++i)
796  {
797  stxxl::int64 region_pos = bids[i].offset;
798  stxxl::int64 region_size = bids[i].size;
799  STXXL_VERBOSE2("Deallocating a block with size: " << region_size);
800  assert(bids[i].size);
801 
802  if (!free_space.empty())
803  {
804  sortseq::iterator succ =
805  free_space.upper_bound(region_pos);
806  sortseq::iterator pred = succ;
807  pred--;
808 
809  if (succ != free_space.end()
810  && (*succ).first == region_pos + region_size)
811  {
812  // coalesce with successor
813 
814  region_size += (*succ).second;
815  free_space.erase(succ);
816  }
817  if (pred != free_space.end()
818  && (*pred).first + (*pred).second == region_pos)
819  {
820  // coalesce with predecessor
821 
822  region_size += (*pred).second;
823  region_pos = (*pred).first;
824  free_space.erase(pred);
825  }
826  }
827  free_space[region_pos] = region_size;
828  }
829  for (i = 0; i < bids.size(); ++i)
830  free_bytes += stxxl::int64(bids[i].size);
831 }
832 #endif
833 
836 class config : public singleton<config>
837 {
838  friend class singleton<config>;
839 
840  struct DiskEntry
841  {
842  std::string path;
843  std::string io_impl;
844  stxxl::int64 size;
845  bool delete_on_exit;
846  };
847  std::vector<DiskEntry> disks_props;
848 
849  // in disks_props, flash devices come after all regular disks
850  unsigned first_flash;
851 
852  config()
853  {
854  const char * cfg_path = getenv("STXXLCFG");
855  if (cfg_path)
856  init(cfg_path);
857  else
858  init();
859  }
860 
861  ~config()
862  {
863  for (unsigned i = 0; i < disks_props.size(); ++i) {
864  if (disks_props[i].delete_on_exit) {
865  STXXL_ERRMSG("Removing disk file created from default configuration: " << disks_props[i].path);
866  unlink(disks_props[i].path.c_str());
867  }
868  }
869  }
870 
871  void init(const char * config_path = "./.stxxl");
872 
873 public:
876  inline unsigned disks_number() const
877  {
878  return disks_props.size();
879  }
880 
883  inline std::pair<unsigned, unsigned> regular_disk_range() const
884  {
885  return std::pair<unsigned, unsigned>(0, first_flash);
886  }
887 
890  inline std::pair<unsigned, unsigned> flash_range() const
891  {
892  return std::pair<unsigned, unsigned>(first_flash, disks_props.size());
893  }
894 
898  inline const std::string & disk_path(int disk) const
899  {
900  return disks_props[disk].path;
901  }
905  inline stxxl::int64 disk_size(int disk) const
906  {
907  return disks_props[disk].size;
908  }
911  inline const std::string & disk_io_impl(int disk) const
912  {
913  return disks_props[disk].io_impl;
914  }
915 };
916 
917 
918 class FileCreator
919 {
920 public:
921  virtual stxxl::file * create(const std::string & io_impl,
922  const std::string & filename,
923  int options, int disk);
924 
925  virtual ~FileCreator() { }
926 };
927 
931 
935 {
936  basic_allocation_strategy(int disks_begin, int disks_end);
938  int operator () (int i) const;
939  static const char * name();
940 };
941 
944 struct striping
945 {
946  int begin, diff;
947  striping(int b, int e) : begin(b), diff(e - b)
948  { }
949  striping() : begin(0)
950  {
951  diff = config::get_instance()->disks_number();
952  }
953  int operator () (int i) const
954  {
955  return begin + i % diff;
956  }
957  static const char * name()
958  {
959  return "striping";
960  }
961  // FIXME WHY?
962  virtual ~striping()
963  { }
964 };
965 
968 struct FR : public striping
969 {
971  FR(int b, int e) : striping(b, e)
972  { }
973  FR() : striping()
974  { }
975  int operator () (int /*i*/) const
976  {
977  return begin + rnd(diff);
978  }
979  static const char * name()
980  {
981  return "fully randomized striping";
982  }
983 };
984 
987 struct SR : public striping
988 {
990  int offset;
991  SR(int b, int e) : striping(b, e)
992  {
993  offset = rnd(diff);
994  }
995  SR() : striping()
996  {
997  offset = rnd(diff);
998  }
999  int operator () (int i) const
1000  {
1001  return begin + (i + offset) % diff;
1002  }
1003  static const char * name()
1004  {
1005  return "simple randomized striping";
1006  }
1007 };
1008 
1011 struct RC : public striping
1012 {
1013  std::vector<int> perm;
1014 
1015  RC(int b, int e) : striping(b, e), perm(diff)
1016  {
1017  for (int i = 0; i < diff; i++)
1018  perm[i] = i;
1019 
1020  stxxl::random_number<random_uniform_fast> rnd;
1021  std::random_shuffle(perm.begin(), perm.end(), rnd __STXXL_FORCE_SEQUENTIAL);
1022  }
1023  RC() : striping(), perm(diff)
1024  {
1025  for (int i = 0; i < diff; i++)
1026  perm[i] = i;
1027 
1029  std::random_shuffle(perm.begin(), perm.end(), rnd __STXXL_FORCE_SEQUENTIAL);
1030  }
1031  int operator () (int i) const
1032  {
1033  return begin + perm[i % diff];
1034  }
1035  static const char * name()
1036  {
1037  return "randomized cycling striping";
1038  }
1039 };
1040 
1041 struct RC_disk : public RC
1042 {
1043  RC_disk(int b, int e) : RC(b, e)
1044  { }
1045  RC_disk() : RC(config::get_instance()->regular_disk_range().first, config::get_instance()->regular_disk_range().second)
1046  { }
1047  static const char * name()
1048  {
1049  return "Randomized cycling striping on regular disks";
1050  }
1051 };
1052 
1053 struct RC_flash : public RC
1054 {
1055  RC_flash(int b, int e) : RC(b, e)
1056  { }
1057  RC_flash() : RC(config::get_instance()->flash_range().first, config::get_instance()->flash_range().second)
1058  { }
1059  static const char * name()
1060  {
1061  return "Randomized cycling striping on flash devices";
1062  }
1063 };
1064 
1068 {
1069  const int disk;
1070  single_disk(int d, int = 0) : disk(d)
1071  { }
1072 
1073  single_disk() : disk(0)
1074  { }
1075  int operator () (int /*i*/) const
1076  {
1077  return disk;
1078  }
1079  static const char * name()
1080  {
1081  return "single disk";
1082  }
1083 };
1084 
1086 
1088 template <class BaseAllocator_>
1090 {
1091  BaseAllocator_ base;
1092  int_type offset;
1096  offset_allocator(int_type offset_) : base(), offset(offset_) { }
1101  offset_allocator(int_type offset_, BaseAllocator_ & base_) : base(base_), offset(offset_) { }
1102  int operator () (int_type i) const
1103  {
1104  return base(offset + i);
1105  }
1106 };
1107 
1109 
1110 #if 0 // deprecated
1111 
1113 template <class bid_it>
1114 struct bid_iterator_traits
1115 {
1116  bid_it * a;
1117  enum
1118  {
1119  block_size = bid_it::block_size
1120  };
1121 };
1122 
1123 template <unsigned blk_sz>
1124 struct bid_iterator_traits<BID<blk_sz> *>
1125 {
1126  enum
1127  {
1128  block_size = blk_sz
1129  };
1130 };
1131 
1132 
1133 template <unsigned blk_sz, class X>
1134 struct bid_iterator_traits<__gnu_cxx::__normal_iterator<BID<blk_sz> *, X> >
1135 {
1136  enum
1137  {
1138  block_size = blk_sz
1139  };
1140 };
1141 
1142 template <unsigned blk_sz, class X, class Y>
1143 struct bid_iterator_traits<std::_List_iterator<BID<blk_sz>, X, Y> >
1144 {
1145  enum
1146  {
1147  block_size = blk_sz
1148  };
1149 };
1150 
1151 template <unsigned blk_sz, class X>
1152 struct bid_iterator_traits<typename std::vector<BID<blk_sz>, X>::iterator>
1153 {
1154  enum
1155  {
1156  block_size = blk_sz
1157  };
1158 };
1159 
1160 #endif
1161 
1163 
1166 class block_manager : public singleton<block_manager>
1167 {
1168  friend class singleton<block_manager>;
1169 
1170  DiskAllocator ** disk_allocators;
1171  file ** disk_files;
1172 
1173  unsigned ndisks;
1174  block_manager();
1175 
1176 protected:
1177  template <class BIDType, class DiskAssgnFunctor, class BIDIteratorClass>
1178  void new_blocks_int(
1179  const unsigned_type nblocks,
1180  DiskAssgnFunctor functor,
1181  BIDIteratorClass out);
1182 
1183 public:
1185 
1192  template <class DiskAssgnFunctor, class BIDIteratorClass>
1193  void new_blocks(
1194  DiskAssgnFunctor functor,
1195  BIDIteratorClass bidbegin,
1196  BIDIteratorClass bidend);
1197 
1206  template <class BlockType, class DiskAssgnFunctor, class BIDIteratorClass>
1207  void new_blocks(
1208  const unsigned_type nblocks,
1209  DiskAssgnFunctor functor,
1210  BIDIteratorClass out);
1211 
1212 
1214 
1218  template <class BIDIteratorClass>
1219  void delete_blocks(const BIDIteratorClass & bidbegin, const BIDIteratorClass & bidend);
1220 
1223  template <unsigned BLK_SIZE>
1224  void delete_block(const BID<BLK_SIZE> & bid);
1225 
1226  ~block_manager();
1227 };
1228 
1229 
1230 template <class BIDType, class DiskAssgnFunctor, class OutputIterator>
1231 void block_manager::new_blocks_int(
1232  const unsigned_type nblocks,
1233  DiskAssgnFunctor functor,
1234  OutputIterator out)
1235 {
1236  typedef BIDType bid_type;
1237  typedef BIDArray<bid_type::t_size> bid_array_type;
1238 
1239  // bid_type tmpbid;
1240  int_type * bl = new int_type[ndisks];
1241  bid_array_type * disk_bids = new bid_array_type[ndisks];
1242  file ** disk_ptrs = new file *[nblocks];
1243 
1244  memset(bl, 0, ndisks * sizeof(int_type));
1245 
1246  unsigned_type i = 0;
1247  //OutputIterator it = out;
1248  for ( ; i < nblocks; ++i /* , ++it*/)
1249  {
1250  const int disk = functor(i);
1251  disk_ptrs[i] = disk_files[disk];
1252  //(*it).storage = disk_files[disk];
1253  bl[disk]++;
1254  }
1255 
1256  for (i = 0; i < ndisks; ++i)
1257  {
1258  if (bl[i])
1259  {
1260  disk_bids[i].resize(bl[i]);
1261  const stxxl::int64 old_capacity =
1262  disk_allocators[i]->get_total_bytes();
1263  const stxxl::int64 new_capacity =
1264  disk_allocators[i]->new_blocks(disk_bids[i]);
1265  if (old_capacity != new_capacity)
1266  {
1267  // resize the file
1268  disk_files[i]->set_size(new_capacity);
1269  if (new_capacity != disk_allocators[i]->get_total_bytes())
1270  STXXL_ERRMSG("File resizing failed: actual size " << disk_allocators[i]->get_total_bytes() << " != requested size " << new_capacity);
1271  }
1272  }
1273  }
1274 
1275  memset(bl, 0, ndisks * sizeof(int_type));
1276 
1277  OutputIterator it = out;
1278  for (i = 0 /*,it = out */; i != nblocks; ++it, ++i)
1279  {
1280  //int disk = (*it).storage->get_id();
1281  //(*it).offset = disk_bids[disk][bl[disk]++].offset;
1282  const int disk = disk_ptrs[i]->get_id();
1283  bid_type bid(disk_ptrs[i], disk_bids[disk][bl[disk]++].offset);
1284  *it = bid;
1285  STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:new " << FMT_BID(bid));
1286  }
1287 
1288  delete[] bl;
1289  delete[] disk_bids;
1290  delete[] disk_ptrs;
1291 }
1292 
1293 template <class BlockType, class DiskAssgnFunctor, class OutputIterator>
1295  const unsigned_type nblocks,
1296  DiskAssgnFunctor functor,
1297  OutputIterator out)
1298 {
1299  typedef typename BlockType::bid_type bid_type;
1300  new_blocks_int<bid_type>(nblocks, functor, out);
1301 }
1302 
1303 template <class DiskAssgnFunctor, class BIDIteratorClass>
1305  DiskAssgnFunctor functor,
1306  BIDIteratorClass bidbegin,
1307  BIDIteratorClass bidend)
1308 {
1309  typedef typename std::iterator_traits<BIDIteratorClass>::value_type bid_type;
1310 
1311  unsigned_type nblocks = 0;
1312 
1313  BIDIteratorClass bidbegin_copy(bidbegin);
1314  while (bidbegin_copy != bidend)
1315  {
1316  ++bidbegin_copy;
1317  ++nblocks;
1318  }
1319 
1320  new_blocks_int<bid_type>(nblocks, functor, bidbegin);
1321 }
1322 
1323 
1324 template <unsigned BLK_SIZE>
1326 {
1327  STXXL_VERBOSE_BLOCK_LIFE_CYCLE("BLC:delete " << FMT_BID(bid));
1328  // do not uncomment it
1329  //assert(bid.storage->get_id() < config::get_instance()->disks_number());
1330  if (bid.storage->get_id() == -1)
1331  return; // self managed disk
1332  assert(bid.storage->get_id() >= 0);
1333  disk_allocators[bid.storage->get_id()]->delete_block(bid);
1334  disk_files[bid.storage->get_id()]->delete_region(bid.offset, bid.size);
1335 }
1336 
1337 
1338 template <class BIDIteratorClass>
1340  const BIDIteratorClass & bidbegin,
1341  const BIDIteratorClass & bidend)
1342 {
1343  for (BIDIteratorClass it = bidbegin; it != bidend; it++)
1344  {
1345  delete_block(*it);
1346  }
1347 }
1348 
1349 #ifndef STXXL_DEFAULT_ALLOC_STRATEGY
1350  #define STXXL_DEFAULT_ALLOC_STRATEGY stxxl::RC
1351 #endif
1352 
1353 // in bytes
1354 #ifndef STXXL_DEFAULT_BLOCK_SIZE
1355  #define STXXL_DEFAULT_BLOCK_SIZE(type) (2 * 1024 * 1024) // use traits
1356 #endif
1357 
1359 
1360 __STXXL_END_NAMESPACE
1361 
1362 
1363 #endif // !STXXL_MNG_HEADER
1364 // vim: et:ts=4:sw=4