STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
disk_allocator.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/mng/disk_allocator.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2004 Roman Dementiev <[email protected]>
7  * Copyright (C) 2007 Johannes Singler <[email protected]>
8  * Copyright (C) 2009, 2010 Andreas Beckmann <[email protected]>
9  * Copyright (C) 2013-2015 Timo Bingmann <[email protected]>
10  *
11  * Distributed under the Boost Software License, Version 1.0.
12  * (See accompanying file LICENSE_1_0.txt or copy at
13  * http://www.boost.org/LICENSE_1_0.txt)
14  **************************************************************************/
15 
16 #ifndef STXXL_MNG_DISK_ALLOCATOR_HEADER
17 #define STXXL_MNG_DISK_ALLOCATOR_HEADER
18 
23 #include <stxxl/bits/io/file.h>
24 #include <stxxl/bits/mng/bid.h>
25 #include <stxxl/bits/mng/config.h>
26 #include <stxxl/bits/namespace.h>
27 #include <stxxl/bits/noncopyable.h>
28 #include <stxxl/bits/parallel.h>
29 #include <stxxl/bits/verbose.h>
30 
31 #include <algorithm>
32 #include <cassert>
33 #include <functional>
34 #include <map>
35 #include <ostream>
36 #include <utility>
37 
39 
40 //! \ingroup mnglayer
41 //! \{
42 
43 class disk_allocator : private noncopyable
44 {
45  typedef std::pair<stxxl::int64, stxxl::int64> place;
46 
47  struct first_fit : public std::binary_function<place, stxxl::int64, bool>
48  {
49  bool operator () (
50  const place& entry,
51  const stxxl::int64 size) const
52  {
53  return (entry.second >= size);
54  }
55  };
56 
57  typedef std::map<stxxl::int64, stxxl::int64> sortseq;
58 
65  bool autogrow;
66 
67  void dump() const;
68 
69  void deallocation_error(
70  stxxl::int64 block_pos, stxxl::int64 block_size,
71  const sortseq::iterator& pred, const sortseq::iterator& succ) const;
72 
73  // expects the mutex to be locked to prevent concurrent access
74  void add_free_region(stxxl::int64 block_pos, stxxl::int64 block_size);
75 
76  // expects the mutex to be locked to prevent concurrent access
77  void grow_file(stxxl::int64 extend_bytes)
78  {
79  if (!extend_bytes)
80  return;
81 
82  storage->set_size(disk_bytes + extend_bytes);
83  add_free_region(disk_bytes, extend_bytes);
84  disk_bytes += extend_bytes;
85  }
86 
87 public:
88  disk_allocator(stxxl::file* storage, const disk_config& cfg)
89  : free_bytes(0),
90  disk_bytes(0),
91  cfg_bytes(cfg.size),
92  storage(storage),
93  autogrow(cfg.autogrow)
94  {
95  // initial growth to configured file size
96  grow_file(cfg.size);
97  }
98 
100  {
101  if (disk_bytes > cfg_bytes) { // reduce to original size
102  storage->set_size(cfg_bytes);
103  }
104  }
105 
106  inline int64 get_free_bytes() const
107  {
108  return free_bytes;
109  }
110 
111  inline int64 get_used_bytes() const
112  {
113  return disk_bytes - free_bytes;
114  }
115 
116  inline int64 get_total_bytes() const
117  {
118  return disk_bytes;
119  }
120 
121  template <unsigned BlockSize>
123  {
124  new_blocks(bids.begin(), bids.end());
125  }
126 
127  template <unsigned BlockSize>
128  void new_blocks(BID<BlockSize>* begin, BID<BlockSize>* end);
129 
130 #if 0
131  template <unsigned BlockSize>
132  void delete_blocks(const BIDArray<BlockSize>& bids)
133  {
134  for (unsigned i = 0; i < bids.size(); ++i)
135  delete_block(bids[i]);
136  }
137 #endif
138 
139  template <unsigned BlockSize>
140  void delete_block(const BID<BlockSize>& bid)
141  {
142  scoped_mutex_lock lock(mutex);
143 
144  STXXL_VERBOSE2("disk_allocator::delete_block<" << BlockSize <<
145  ">(pos=" << bid.offset << ", size=" << bid.size <<
146  "), free:" << free_bytes << " total:" << disk_bytes);
147 
148  add_free_region(bid.offset, bid.size);
149  }
150 };
151 
152 template <unsigned BlockSize>
153 void disk_allocator::new_blocks(BID<BlockSize>* begin, BID<BlockSize>* end)
154 {
155  stxxl::int64 requested_size = 0;
156 
157  for (typename BIDArray<BlockSize>::iterator cur = begin; cur != end; ++cur)
158  {
159  STXXL_VERBOSE2("Asking for a block with size: " << (cur->size));
160  requested_size += cur->size;
161  }
162 
163  scoped_mutex_lock lock(mutex);
164 
165  STXXL_VERBOSE2("disk_allocator::new_blocks<BlockSize>, BlockSize = " << BlockSize <<
166  ", free:" << free_bytes << " total:" << disk_bytes <<
167  ", blocks: " << (end - begin) <<
168  " begin: " << static_cast<void*>(begin) <<
169  " end: " << static_cast<void*>(end) <<
170  ", requested_size=" << requested_size);
171 
172  if (free_bytes < requested_size)
173  {
174  if (!autogrow) {
176  "Out of external memory error: " << requested_size <<
177  " requested, " << free_bytes << " bytes free. "
178  "Maybe enable autogrow flags?");
179  }
180 
181  STXXL_ERRMSG("External memory block allocation error: " << requested_size <<
182  " bytes requested, " << free_bytes <<
183  " bytes free. Trying to extend the external memory space...");
184 
185  grow_file(requested_size);
186  }
187 
188  // dump();
189 
190  sortseq::iterator space;
191  space = std::find_if(free_space.begin(), free_space.end(),
192  bind2nd(first_fit(), requested_size) _STXXL_FORCE_SEQUENTIAL);
193 
194  if (space == free_space.end() && requested_size == BlockSize)
195  {
196  assert(end - begin == 1);
197 
198  if (!autogrow) {
199  STXXL_ERRMSG("Warning: Severe external memory space fragmentation!");
200  dump();
201 
202  STXXL_ERRMSG("External memory block allocation error: " << requested_size <<
203  " bytes requested, " << free_bytes <<
204  " bytes free. Trying to extend the external memory space...");
205  }
206 
207  grow_file(BlockSize);
208 
209  space = std::find_if(free_space.begin(), free_space.end(),
210  bind2nd(first_fit(), requested_size) _STXXL_FORCE_SEQUENTIAL);
211  }
212 
213  if (space != free_space.end())
214  {
215  stxxl::int64 region_pos = (*space).first;
216  stxxl::int64 region_size = (*space).second;
217  free_space.erase(space);
218  if (region_size > requested_size)
219  free_space[region_pos + requested_size] = region_size - requested_size;
220 
221  for (stxxl::int64 pos = region_pos; begin != end; ++begin)
222  {
223  begin->offset = pos;
224  pos += begin->size;
225  }
226  free_bytes -= requested_size;
227  //dump();
228 
229  return;
230  }
231 
232  // no contiguous region found
233  STXXL_VERBOSE1("Warning, when allocating an external memory space, no contiguous region found");
234  STXXL_VERBOSE1("It might harm the performance");
235 
236  assert(requested_size > BlockSize);
237  assert(end - begin > 1);
238 
239  lock.unlock();
240 
241  BID<BlockSize>* middle = begin + ((end - begin) / 2);
242  new_blocks(begin, middle);
243  new_blocks(middle, end);
244 }
245 
246 //! \}
247 
249 
250 #endif // !STXXL_MNG_DISK_ALLOCATOR_HEADER
251 // vim: et:ts=4:sw=4
stxxl::int64 disk_bytes
long long int int64
Definition: types.h:38
void new_blocks(BIDArray< BlockSize > &bids)
stxxl::int64 cfg_bytes
stxxl::file * storage
Block size.
Definition: bid.h:45
stxxl::int64 free_bytes
void unlock()
unlock mutex hold prematurely
Definition: mutex.h:144
int64 get_used_bytes() const
#define STXXL_THROW(exception_type, error_message)
Throws exception_type with &quot;Error in [function] : [error_message]&quot;.
#define STXXL_VERBOSE2(x)
Definition: verbose.h:121
size_type size() const
return number of items in vector
iterator end()
return mutable iterator beyond last element
std::map< stxxl::int64, stxxl::int64 > sortseq
std::pair< stxxl::int64, stxxl::int64 > place
void grow_file(stxxl::int64 extend_bytes)
Defines interface of file.
Definition: file.h:56
Encapsulate the configuration of one &quot;disk&quot;. The disk is actually a file I/O object which block_manag...
Definition: config.h:34
iterator begin()
return mutable iterator to first element
Definition: simple_vector.h:94
Aquire a lock that&#39;s valid until the end of scope.
Definition: mutex.h:123
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
int64 get_total_bytes() const
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
int64 get_free_bytes() const
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
disk_allocator(stxxl::file *storage, const disk_config &cfg)
void delete_block(const BID< BlockSize > &bid)
#define _STXXL_FORCE_SEQUENTIAL
Definition: parallel.h:34
stxxl::int64 offset
offset within the file of the block
Definition: bid.h:50
uint64 size
file size to initially allocate
Definition: config.h:44
#define STXXL_END_NAMESPACE
Definition: namespace.h:17