Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
block_manager.hpp
Go to the documentation of this file.
1 /***************************************************************************
2  * foxxll/mng/block_manager.hpp
3  *
4  * Part of FOXXLL. See http://foxxll.org
5  *
6  * Copyright (C) 2002-2007 Roman Dementiev <[email protected]>
7  * Copyright (C) 2007, 2009 Johannes Singler <[email protected]>
8  * Copyright (C) 2008-2010 Andreas Beckmann <[email protected]>
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 FOXXLL_MNG_BLOCK_MANAGER_HEADER
16 #define FOXXLL_MNG_BLOCK_MANAGER_HEADER
17 
18 #include <algorithm>
19 #include <cstdlib>
20 #include <iterator>
21 #include <memory>
22 #include <mutex>
23 #include <string>
24 #include <vector>
25 
26 #include <foxxll/common/utils.hpp>
27 #include <foxxll/config.hpp>
28 #include <foxxll/defines.hpp>
30 #include <foxxll/io/file.hpp>
31 #include <foxxll/io/request.hpp>
32 #include <foxxll/mng/bid.hpp>
34 #include <foxxll/mng/config.hpp>
36 #include <foxxll/singleton.hpp>
37 #include <tlx/simple_vector.hpp>
38 
39 #if FOXXLL_MSVC
40 #include <memory.h>
41 #endif
42 
43 namespace foxxll {
44 
45 //! \addtogroup foxxll_mnglayer
46 //! \{
47 
48 /*!
49  * Block manager class.
50  *
51  * Manages allocation and deallocation of blocks in multiple/single disk setting
52  * \remarks is a singleton
53  */
54 class block_manager : public singleton<block_manager>
55 {
56  constexpr static bool debug = false;
57 
58 public:
59  /*!
60  * Allocates new blocks.
61  *
62  * Allocates new blocks according to the strategy given by \b functor and
63  * stores block identifiers to the range [ \b bid_begin, \b bid_end)
64  * Allocation will be lined up with previous partial allocations of \b
65  * alloc_offset blocks. For BID<0> allocations, the objects' size field must
66  * be initialized.
67  *
68  * \param functor object of model of \b allocation_strategy concept
69  * \param bid_begin bidirectional BID iterator object
70  * \param bid_end bidirectional BID iterator object
71  * \param alloc_offset advance for \b functor to line up partial allocations
72  */
73  template <typename DiskAssignFunctor, typename BIDIterator>
74  void new_blocks(
75  const DiskAssignFunctor& functor,
76  BIDIterator bid_begin, BIDIterator bid_end,
77  size_t alloc_offset = 0);
78 
79  /*!
80  * Allocates a new block according to the strategy given by \b functor and
81  * stores the block identifier to bid.
82  *
83  * Allocation will be lined up with previous partial allocations of \b
84  * alloc_offset blocks.
85  *
86  * \param functor object of model of \b allocation_strategy concept
87  * \param bid BID to store the block identifier
88  * \param alloc_offset advance for \b functor to line up partial allocations
89  */
90  template <typename DiskAssignFunctor, size_t BlockSize>
91  void new_block(const DiskAssignFunctor& functor,
92  BID<BlockSize>& bid, size_t alloc_offset = 0)
93  {
94  new_blocks(functor, &bid, std::next(&bid, 1), alloc_offset);
95  }
96 
97  //! Deallocates blocks.
98  //!
99  //! Deallocates blocks in the range [ \b bid_begin, \b bid_end)
100  //! \param bid_begin iterator object of \b bid_iterator concept
101  //! \param bid_end iterator object of \b bid_iterator concept
102  template <typename BIDIterator>
103  void delete_blocks(const BIDIterator& bid_begin,
104  const BIDIterator& bid_end);
105 
106  //! Deallocates a block.
107  //! \param bid block identifier
108  template <size_t BlockSize>
109  void delete_block(const BID<BlockSize>& bid);
110 
111  //! \name Statistics
112  //! \{
113 
114  //! return total number of bytes available in all disks
115  uint64_t total_bytes() const;
116 
117  //! Return total number of free bytes
118  uint64_t free_bytes() const;
119 
120  //! return total requested allocation in bytes
121  uint64_t total_allocation() const;
122 
123  //! return currently allocated bytes
124  uint64_t current_allocation() const;
125 
126  //! return maximum number of bytes allocated during program run.
127  uint64_t maximum_allocation() const;
128 
129  //! \}
130 
131  ~block_manager();
132 
133 private:
134  friend class singleton<block_manager>;
135 
136  //! number of managed disks
137  size_t ndisks_;
138 
139  //! vector of opened disk files
141 
142  //! one block allocator per disk
144 
145  //! total requested allocation in bytes
146  uint64_t total_allocation_ = 0;
147 
148  //! currently allocated bytes
149  uint64_t current_allocation_ = 0;
150 
151  //! maximum number of bytes allocated during program run.
152  uint64_t maximum_allocation_ = 0;
153 
154  //! private construction from singleton
155  block_manager();
156 
157  //! protect internal data structures
158  mutable std::mutex mutex_;
159 
160  //! log creation and destruction of blocks
161  static constexpr bool verbose_block_life_cycle = false;
162 };
163 
164 template <typename DiskAssignFunctor, typename BIDIterator>
166  const DiskAssignFunctor& functor,
167  BIDIterator bid_begin, BIDIterator bid_end,
168  size_t alloc_offset)
169 {
170  std::unique_lock<std::mutex> lock(mutex_);
171 
172  using BIDType = typename std::iterator_traits<BIDIterator>::value_type;
173 
174  // choose disks for each block, sum up bytes allocated on a disk
175 
176  tlx::simple_vector<size_t> disk_blocks(ndisks_);
178  std::vector<std::vector<size_t> > disk_out(ndisks_);
179 
180  disk_blocks.fill(0);
181  disk_bytes.fill(0);
182 
183  size_t bid_size = static_cast<size_t>(bid_end - bid_begin);
184 
185  BIDIterator bid = bid_begin;
186  for (size_t i = 0; i < bid_size; ++i, ++bid)
187  {
188  size_t disk_id = functor(alloc_offset + i);
189 
190  if (!block_allocators_[disk_id]->has_available_space(
191  disk_bytes[disk_id] + bid->size
192  ))
193  {
194  // find disk (cyclically) that has enough free space for block
195 
196  for (size_t adv = 1; adv < ndisks_; ++adv)
197  {
198  size_t try_disk_id = (disk_id + adv) % ndisks_;
199  if (block_allocators_[try_disk_id]->has_available_space(
200  disk_bytes[try_disk_id] + bid->size
201  ))
202  {
203  disk_id = try_disk_id;
204  break;
205  }
206  }
207 
208  // if no disk has free space, pick first selected by functor
209  }
210 
211  // assign block to disk
212  disk_blocks[disk_id]++;
213  disk_bytes[disk_id] += bid->size;
214  disk_out[disk_id].push_back(i);
215  }
216 
217  // allocate blocks on disks in sequence, then scatter blocks into output
218 
220 
221  for (size_t d = 0; d < ndisks_; ++d)
222  {
223  if (disk_blocks[d] == 0) continue;
224  bids.resize(disk_blocks[d]);
225 
226  std::vector<size_t>& bid_perm = disk_out[d];
227 
228  // collect bids from output (due to size field for BID<0>)
229  for (size_t i = 0; i < disk_blocks[d]; ++i)
230  bids[i] = bid_begin[bid_perm[i]];
231 
232  // let block_allocator fill in offset fields
233  block_allocators_[d]->new_blocks(bids);
234 
235  // distributed bids back to output
236  for (size_t i = 0; i < disk_blocks[d]; ++i) {
237  bids[i].storage = disk_files_[d].get();
238 
239  LOGC(verbose_block_life_cycle) << "BLC:new " << bids[i];
240  bid_begin[bid_perm[i]] = bids[i];
241 
242  total_allocation_ += bids[i].size;
243  current_allocation_ += bids[i].size;
244  }
245  }
246 
248 }
249 
250 template <size_t BlockSize>
252 {
253  std::unique_lock<std::mutex> lock(mutex_);
254 
255  if (!bid.valid()) {
256  LOG << "Warning: invalid block to be deleted.";
257  return;
258  }
259  if (!bid.is_managed())
260  return; // self managed disk
261 
262  LOGC(verbose_block_life_cycle) << "BLC:delete " << bid;
263  assert(bid.storage->get_allocator_id() >= 0);
264  block_allocators_[bid.storage->get_allocator_id()]->delete_block(bid);
265  disk_files_[bid.storage->get_allocator_id()]->discard(bid.offset, bid.size);
266 
267  current_allocation_ -= BlockSize;
268 }
269 
270 template <typename BIDIterator>
272  const BIDIterator& bid_begin, const BIDIterator& bid_end)
273 {
274  for (BIDIterator it = bid_begin; it != bid_end; ++it)
275  delete_block(*it);
276 }
277 
278 //! \}
279 
280 } // namespace foxxll
281 
282 #endif // !FOXXLL_MNG_BLOCK_MANAGER_HEADER
283 
284 /**************************************************************************/
void new_blocks(const DiskAssignFunctor &functor, BIDIterator bid_begin, BIDIterator bid_end, size_t alloc_offset=0)
Allocates new blocks.
std::mutex mutex_
protect internal data structures
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.hpp:226
uint64_t current_allocation() const
return currently allocated bytes
void resize(size_type new_size)
resize the array to contain exactly new_size items
uint64_t current_allocation_
currently allocated bytes
uint64_t total_bytes() const
return total number of bytes available in all disks
void delete_blocks(const BIDIterator &bid_begin, const BIDIterator &bid_end)
Simpler non-growing vector without initialization.
external_size_type offset
offset within the file of the block (uint64_t)
Definition: bid.hpp:50
void delete_block(const BID< BlockSize > &bid)
static constexpr bool debug
bool valid() const
Definition: bid.hpp:70
uint64_t total_allocation() const
return total requested allocation in bytes
tlx::simple_vector< disk_block_allocator * > block_allocators_
one block allocator per disk
uint64_t total_allocation_
total requested allocation in bytes
void fill(const value_type &v=value_type()) noexcept
Zero the whole array content.
size_type size() const noexcept
return number of items in vector
size_t ndisks_
number of managed disks
block_manager()
private construction from singleton
Block manager class.
uint64_t free_bytes() const
Return total number of free bytes.
bool is_managed() const
Definition: bid.hpp:75
void new_block(const DiskAssignFunctor &functor, BID< BlockSize > &bid, size_t alloc_offset=0)
Allocates a new block according to the strategy given by functor and stores the block identifier to b...
tlx::simple_vector< file_ptr > disk_files_
vector of opened disk files
uint64_t maximum_allocation() const
return maximum number of bytes allocated during program run.
file * storage
pointer to the file of the block
Definition: bid.hpp:48
#define LOG
Default logging method: output if the local debug variable is true.
Definition: logger.hpp:141
uint64_t maximum_allocation_
maximum number of bytes allocated during program run.
static constexpr bool verbose_block_life_cycle
log creation and destruction of blocks
static constexpr size_t size
Block size.
Definition: bid.hpp:43
#define LOGC(cond)
Explicitly specify the condition for logging.
Definition: logger.hpp:137