Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
disk_block_allocator.hpp
Go to the documentation of this file.
1 /***************************************************************************
2  * foxxll/mng/disk_block_allocator.hpp
3  *
4  * Part of FOXXLL. See http://foxxll.org
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 FOXXLL_MNG_DISK_BLOCK_ALLOCATOR_HEADER
17 #define FOXXLL_MNG_DISK_BLOCK_ALLOCATOR_HEADER
18 
19 #include <algorithm>
20 #include <cassert>
21 #include <map>
22 #include <mutex>
23 #include <ostream>
24 #include <utility>
25 
26 #include <tlx/logger.hpp>
27 
30 #include <foxxll/common/types.hpp>
31 #include <foxxll/io/file.hpp>
32 #include <foxxll/mng/bid.hpp>
33 #include <foxxll/mng/config.hpp>
34 
35 namespace foxxll {
36 
37 //! \ingroup foxxll_mnglayer
38 //! \{
39 
40 /*!
41  * This class manages allocation of blocks onto a single disk. It contains a map
42  * of all currently allocated blocks. The block_manager selects which of the
43  * disk_block_allocator objects blocks are drawn from.
44  */
46 {
47  constexpr static bool debug = false;
48 
49 public:
50  disk_block_allocator(file* storage, const disk_config& cfg)
51  : cfg_bytes_(cfg.size),
52  storage_(storage),
53  autogrow_(cfg.autogrow)
54  {
55  // initial growth to configured file size
56  grow_file(cfg.size);
57  }
58 
59  //! non-copyable: delete copy-constructor
61  //! non-copyable: delete assignment operator
63 
65  {
66  if (disk_bytes_ > cfg_bytes_) { // reduce to original size
68  }
69  }
70 
71  //! Returns autogrow
72  bool autogrow() const { return autogrow_; }
73 
74  bool has_available_space(uint64_t bytes) const
75  {
76  return autogrow_ || free_bytes_ >= bytes;
77  }
78 
79  uint64_t free_bytes() const
80  {
81  return free_bytes_;
82  }
83 
84  uint64_t used_bytes() const
85  {
86  return disk_bytes_ - free_bytes_;
87  }
88 
89  uint64_t total_bytes() const
90  {
91  return disk_bytes_;
92  }
93 
94  template <size_t BlockSize>
96  {
97  new_blocks(bids.begin(), bids.end());
98  }
99 
100  template <typename BIDIterator>
101  void new_blocks(BIDIterator begin, BIDIterator end);
102 
103  template <size_t BlockSize>
105  {
106  for (size_t i = 0; i < bids.size(); ++i)
107  delete_block(bids[i]);
108  }
109 
110  template <size_t BlockSize>
111  void delete_block(const BID<BlockSize>& bid)
112  {
113  std::unique_lock<std::mutex> lock(mutex_);
114 
115  LOG << "disk_block_allocator::delete_block<" << BlockSize <<
116  ">(pos=" << bid.offset << ", size=" << bid.size <<
117  "), free:" << free_bytes_ << " total:" << disk_bytes_;
118 
119  add_free_region(bid.offset, bid.size);
120  }
121 
122 private:
123  //! pair (offset, size) used for free space calculation
124  using place = std::pair<uint64_t, uint64_t>;
125  using space_map_type = std::map<uint64_t, uint64_t>;
126 
127  std::mutex mutex_;
128  //! map of free space as places
130  uint64_t free_bytes_ = 0;
131  uint64_t disk_bytes_ = 0;
132  uint64_t cfg_bytes_;
134  bool autogrow_;
135 
136  void dump() const;
137 
138  void deallocation_error(
139  uint64_t block_pos, uint64_t block_size,
140  const space_map_type::iterator& pred,
141  const space_map_type::iterator& succ) const;
142 
143  // expects the mutex_ to be locked to prevent concurrent access
144  void add_free_region(uint64_t block_pos, uint64_t block_size);
145 
146  // expects the mutex_ to be locked to prevent concurrent access
147  void grow_file(uint64_t extend_bytes)
148  {
149  if (extend_bytes == 0)
150  return;
151 
152  storage_->set_size(disk_bytes_ + extend_bytes);
153  add_free_region(disk_bytes_, extend_bytes);
154  disk_bytes_ += extend_bytes;
155  }
156 };
157 
158 template <typename BIDIterator>
159 void disk_block_allocator::new_blocks(BIDIterator begin, BIDIterator end)
160 {
161  uint64_t requested_size = 0;
162 
163  for (BIDIterator cur = begin; cur != end; ++cur)
164  {
165  LOG << "Asking for a block with size: " << cur->size;
166  requested_size += cur->size;
167  }
168 
169  std::unique_lock<std::mutex> lock(mutex_);
170 
171  LOG << "disk_block_allocator::new_blocks<BlockSize>"
172  ", BlockSize = " << begin->size <<
173  ", free:" << free_bytes_ << " total:" << disk_bytes_ <<
174  ", blocks: " << (end - begin) <<
175  ", requested_size=" << requested_size;
176 
177  if (free_bytes_ < requested_size)
178  {
179  if (!autogrow_) {
180  FOXXLL_THROW(
182  "Out of external memory error: " << requested_size <<
183  " requested, " << free_bytes_ << " bytes free. "
184  "Maybe enable autogrow_ flags?"
185  );
186  }
187 
188  LOG1 << "External memory block allocation error: " << requested_size <<
189  " bytes requested, " << free_bytes_ <<
190  " bytes free. Trying to extend the external memory space...";
191 
192  grow_file(requested_size);
193  }
194 
195  // dump();
196 
197  space_map_type::iterator space =
198  std::find_if(
199  free_space_.begin(), free_space_.end(),
200  [requested_size](const place& entry) {
201  return (entry.second >= requested_size);
202  }
203  );
204 
205  if (space == free_space_.end() && begin + 1 == end)
206  {
207  if (!autogrow_) {
208  LOG1 << "Warning: Severe external memory space fragmentation!";
209  dump();
210 
211  LOG1 << "External memory block allocation error: " << requested_size <<
212  " bytes requested, " << free_bytes_ <<
213  " bytes free. Trying to extend the external memory space...";
214  }
215 
216  grow_file(begin->size);
217 
218  space = std::find_if(
219  free_space_.begin(), free_space_.end(),
220  [requested_size](const place& entry) {
221  return (entry.second >= requested_size);
222  }
223  );
224  }
225 
226  if (space != free_space_.end())
227  {
228  uint64_t region_pos = (*space).first;
229  uint64_t region_size = (*space).second;
230  free_space_.erase(space);
231 
232  if (region_size > requested_size)
233  free_space_[region_pos + requested_size] = region_size - requested_size;
234 
235  for (uint64_t pos = region_pos; begin != end; ++begin)
236  {
237  begin->offset = pos;
238  pos += begin->size;
239  }
240 
241  assert(free_bytes_ >= requested_size);
242  free_bytes_ -= requested_size;
243  //dump();
244 
245  return;
246  }
247 
248  // no contiguous region found
249  LOG << "Warning, when allocating an external memory space, no"
250  "contiguous region found. It might harm the performance";
251 
252  assert(end - begin > 1);
253 
254  lock.unlock();
255 
256  BIDIterator middle = begin + ((end - begin) / 2);
257  new_blocks(begin, middle);
258  new_blocks(middle, end);
259 }
260 
261 //! \}
262 
263 } // namespace foxxll
264 
265 #endif // !FOXXLL_MNG_DISK_BLOCK_ALLOCATOR_HEADER
266 
267 /**************************************************************************/
external_size_type size
file size to initially allocate
Definition: config.hpp:46
virtual void set_size(offset_type newsize)=0
iterator end() noexcept
return mutable iterator beyond last element
void add_free_region(uint64_t block_pos, uint64_t block_size)
#define LOG1
Definition: logger.hpp:145
#define FOXXLL_THROW(exception_type, error_message)
Throws exception_type with "Error in [function] : [error_message]".
Simpler non-growing vector without initialization.
external_size_type offset
offset within the file of the block (uint64_t)
Definition: bid.hpp:50
disk_block_allocator(file *storage, const disk_config &cfg)
std::map< uint64_t, uint64_t > space_map_type
iterator begin() noexcept
return mutable iterator to first element
void delete_blocks(const BIDArray< BlockSize > &bids)
size_type size() const noexcept
return number of items in vector
void new_blocks(BIDArray< BlockSize > &bids)
disk_block_allocator & operator=(const disk_block_allocator &)=delete
non-copyable: delete assignment operator
static const size_t bytes
number of bytes in uint_pair
Definition: uint_types.hpp:75
space_map_type free_space_
map of free space as places
void grow_file(uint64_t extend_bytes)
void deallocation_error(uint64_t block_pos, uint64_t block_size, const space_map_type::iterator &pred, const space_map_type::iterator &succ) const
bool has_available_space(uint64_t bytes) const
void delete_block(const BID< BlockSize > &bid)
bool autogrow() const
Returns autogrow.
std::pair< uint64_t, uint64_t > place
pair (offset, size) used for free space calculation
#define LOG
Default logging method: output if the local debug variable is true.
Definition: logger.hpp:141
static constexpr size_t size
Block size.
Definition: bid.hpp:43
This class manages allocation of blocks onto a single disk.