STXXL  1.4.1
 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 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 
21 #include <stxxl/bits/io/file.h>
22 #include <stxxl/bits/mng/bid.h>
23 #include <stxxl/bits/mng/config.h>
24 #include <stxxl/bits/namespace.h>
25 #include <stxxl/bits/noncopyable.h>
26 #include <stxxl/bits/parallel.h>
27 #include <stxxl/bits/verbose.h>
28 
29 #include <algorithm>
30 #include <cassert>
31 #include <functional>
32 #include <map>
33 #include <ostream>
34 #include <utility>
35 
37 
38 //! \ingroup mnglayer
39 //! \{
40 
41 class disk_allocator : private noncopyable
42 {
43  typedef std::pair<stxxl::int64, stxxl::int64> place;
44 
45  struct first_fit : public std::binary_function<place, stxxl::int64, bool>
46  {
47  bool operator () (
48  const place& entry,
49  const stxxl::int64 size) const
50  {
51  return (entry.second >= size);
52  }
53  };
54 
55  typedef std::map<stxxl::int64, stxxl::int64> sortseq;
56 
63  bool autogrow;
64 
65  void dump() const;
66 
67  void deallocation_error(
68  stxxl::int64 block_pos, stxxl::int64 block_size,
69  const sortseq::iterator& pred, const sortseq::iterator& succ) const;
70 
71  // expects the mutex to be locked to prevent concurrent access
72  void add_free_region(stxxl::int64 block_pos, stxxl::int64 block_size);
73 
74  // expects the mutex to be locked to prevent concurrent access
75  void grow_file(stxxl::int64 extend_bytes)
76  {
77  if (!extend_bytes)
78  return;
79 
80  storage->set_size(disk_bytes + extend_bytes);
81  add_free_region(disk_bytes, extend_bytes);
82  disk_bytes += extend_bytes;
83  }
84 
85 public:
86  disk_allocator(stxxl::file* storage, const disk_config& cfg)
87  : free_bytes(0),
88  disk_bytes(0),
89  cfg_bytes(cfg.size),
90  storage(storage),
91  autogrow(cfg.autogrow)
92  {
93  // initial growth to configured file size
94  grow_file(cfg.size);
95  }
96 
98  {
99  if (disk_bytes > cfg_bytes) { // reduce to original size
100  storage->set_size(cfg_bytes);
101  }
102  }
103 
104  inline int64 get_free_bytes() const
105  {
106  return free_bytes;
107  }
108 
109  inline int64 get_used_bytes() const
110  {
111  return disk_bytes - free_bytes;
112  }
113 
114  inline int64 get_total_bytes() const
115  {
116  return disk_bytes;
117  }
118 
119  template <unsigned BlockSize>
121  {
122  new_blocks(bids.begin(), bids.end());
123  }
124 
125  template <unsigned BlockSize>
126  void new_blocks(BID<BlockSize>* begin, BID<BlockSize>* end);
127 
128 #if 0
129  template <unsigned BlockSize>
130  void delete_blocks(const BIDArray<BlockSize>& bids)
131  {
132  for (unsigned i = 0; i < bids.size(); ++i)
133  delete_block(bids[i]);
134  }
135 #endif
136 
137  template <unsigned BlockSize>
138  void delete_block(const BID<BlockSize>& bid)
139  {
140  scoped_mutex_lock lock(mutex);
141 
142  STXXL_VERBOSE2("disk_allocator::delete_block<" << BlockSize <<
143  ">(pos=" << bid.offset << ", size=" << bid.size <<
144  "), free:" << free_bytes << " total:" << disk_bytes);
145 
146  add_free_region(bid.offset, bid.size);
147  }
148 };
149 
150 template <unsigned BlockSize>
151 void disk_allocator::new_blocks(BID<BlockSize>* begin, BID<BlockSize>* end)
152 {
153  stxxl::int64 requested_size = 0;
154 
155  for (typename BIDArray<BlockSize>::iterator cur = begin; cur != end; ++cur)
156  {
157  STXXL_VERBOSE2("Asking for a block with size: " << (cur->size));
158  requested_size += cur->size;
159  }
160 
161  scoped_mutex_lock lock(mutex);
162 
163  STXXL_VERBOSE2("disk_allocator::new_blocks<BlockSize>, BlockSize = " << BlockSize <<
164  ", free:" << free_bytes << " total:" << disk_bytes <<
165  ", blocks: " << (end - begin) <<
166  " begin: " << static_cast<void*>(begin) <<
167  " end: " << static_cast<void*>(end) <<
168  ", requested_size=" << requested_size);
169 
170  if (free_bytes < requested_size)
171  {
172  if (!autogrow) {
173  STXXL_ERRMSG("External memory block allocation error: " << requested_size <<
174  " bytes requested, " << free_bytes <<
175  " bytes free. Trying to extend the external memory space...");
176  }
177 
178  grow_file(requested_size);
179  }
180 
181  // dump();
182 
183  sortseq::iterator space;
184  space = std::find_if(free_space.begin(), free_space.end(),
185  bind2nd(first_fit(), requested_size) _STXXL_FORCE_SEQUENTIAL);
186 
187  if (space == free_space.end() && requested_size == BlockSize)
188  {
189  assert(end - begin == 1);
190 
191  if (!autogrow) {
192  STXXL_ERRMSG("Warning: Severe external memory space fragmentation!");
193  dump();
194 
195  STXXL_ERRMSG("External memory block allocation error: " << requested_size <<
196  " bytes requested, " << free_bytes <<
197  " bytes free. Trying to extend the external memory space...");
198  }
199 
200  grow_file(BlockSize);
201 
202  space = std::find_if(free_space.begin(), free_space.end(),
203  bind2nd(first_fit(), requested_size) _STXXL_FORCE_SEQUENTIAL);
204  }
205 
206  if (space != free_space.end())
207  {
208  stxxl::int64 region_pos = (*space).first;
209  stxxl::int64 region_size = (*space).second;
210  free_space.erase(space);
211  if (region_size > requested_size)
212  free_space[region_pos + requested_size] = region_size - requested_size;
213 
214  for (stxxl::int64 pos = region_pos; begin != end; ++begin)
215  {
216  begin->offset = pos;
217  pos += begin->size;
218  }
219  free_bytes -= requested_size;
220  //dump();
221 
222  return;
223  }
224 
225  // no contiguous region found
226  STXXL_VERBOSE1("Warning, when allocating an external memory space, no contiguous region found");
227  STXXL_VERBOSE1("It might harm the performance");
228 
229  assert(requested_size > BlockSize);
230  assert(end - begin > 1);
231 
232  lock.unlock();
233 
234  BID<BlockSize>* middle = begin + ((end - begin) / 2);
235  new_blocks(begin, middle);
236  new_blocks(middle, end);
237 }
238 
239 //! \}
240 
242 
243 #endif // !STXXL_MNG_DISK_ALLOCATOR_HEADER
244 // 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:126
int64 get_used_bytes() const
#define STXXL_VERBOSE2(x)
Definition: verbose.h:107
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
Block identifier class.
Definition: bid.h:41
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:105
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
int64 get_total_bytes() const
#define STXXL_VERBOSE1(x)
Definition: verbose.h:99
int64 get_free_bytes() const
#define STXXL_ERRMSG(x)
Definition: verbose.h:80
disk_allocator(stxxl::file *storage, const disk_config &cfg)
void delete_block(const BID< BlockSize > &bid)
#define _STXXL_FORCE_SEQUENTIAL
Definition: parallel.h:50
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