STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
prefetch_pool.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/mng/prefetch_pool.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2003-2004 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009 Andreas Beckmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_MNG_PREFETCH_POOL_HEADER
15 #define STXXL_MNG_PREFETCH_POOL_HEADER
16 
17 #include <list>
18 #include <stxxl/bits/config.h>
21 
23 
24 //! \addtogroup schedlayer
25 //! \{
26 
27 //! Implements dynamically resizable prefetching pool.
28 template <class BlockType>
29 class prefetch_pool : private noncopyable
30 {
31 public:
32  typedef BlockType block_type;
33  typedef typename block_type::bid_type bid_type;
34 
35 protected:
36  struct bid_hash
37  {
38  size_t operator () (const bid_type& bid) const
39  {
40  size_t result = size_t(bid.storage) +
41  size_t(bid.offset & 0xffffffff) +
42  size_t(bid.offset >> 32);
43  return result;
44  }
45 #if STXXL_MSVC
46  bool operator () (const bid_type& a, const bid_type& b) const
47  {
48  return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
49  }
50  enum
51  { // parameters for hash table
52  bucket_size = 4, // 0 < bucket_size
53  min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
54  };
55 #endif
56  };
57  typedef std::pair<block_type*, request_ptr> busy_entry;
59  typedef typename std::list<block_type*>::iterator free_blocks_iterator;
60  typedef typename hash_map_type::iterator busy_blocks_iterator;
61 
62  //! contains free prefetch blocks
63  std::list<block_type*> free_blocks;
64 
65  //! blocks that are in reading or already read but not retrieved by user
67 
68  //! count number of free blocks, since traversing the std::list is slow.
70 
71 public:
72  //! Constructs pool.
73  //! \param init_size initial number of blocks in the pool
74  explicit prefetch_pool(unsigned_type init_size = 1)
75  : free_blocks_size(init_size)
76  {
77  unsigned_type i = 0;
78  for ( ; i < init_size; ++i)
79  free_blocks.push_back(new block_type);
80  }
81 
82  void swap(prefetch_pool& obj)
83  {
84  std::swap(free_blocks, obj.free_blocks);
85  std::swap(busy_blocks, obj.busy_blocks);
86  std::swap(free_blocks_size, obj.free_blocks_size);
87  }
88 
89  //! Waits for completion of all ongoing read requests and frees memory.
90  virtual ~prefetch_pool()
91  {
92  while (!free_blocks.empty())
93  {
94  delete free_blocks.back();
95  free_blocks.pop_back();
96  }
97 
98  try
99  {
100  busy_blocks_iterator i2 = busy_blocks.begin();
101  for ( ; i2 != busy_blocks.end(); ++i2)
102  {
103  i2->second.second->wait();
104  delete i2->second.first;
105  }
106  }
107  catch (...)
108  { }
109  }
110 
111  //! Returns number of owned blocks.
113  {
114  return free_blocks_size + busy_blocks.size();
115  }
116 
117  //! Returns the number of free prefetching blocks.
119  {
120  return free_blocks_size;
121  }
122 
123  //! Returns the number of busy prefetching blocks.
125  {
126  return busy_blocks.size();
127  }
128 
129  //! Add a new block to prefetch pool, enlarges size of pool.
130  void add(block_type*& block)
131  {
132  free_blocks.push_back(block);
133  ++free_blocks_size;
134  block = NULL; // prevent caller from using the block any further
135  }
136 
137  //! Take out a block from the pool, one unhinted free block must be
138  //! available.
139  //! \return pointer to the block. Ownership of the block goes to the caller.
141  {
142  STXXL_CHECK(!free_blocks.empty());
143 
144  block_type* p = free_blocks.back();
145  free_blocks.pop_back();
146  --free_blocks_size;
147  return p;
148  }
149 
150  /*!
151  * Gives a hint for prefetching a block, the block may or may not be read
152  * into a prefetch buffer.
153  *
154  * \param bid address of a block to be prefetched
155  * \return \c true if there was a free block to do prefetch and
156  * prefetching was scheduled, \c false otherwise
157  *
158  * \note If there are no free blocks available (all blocks are already in
159  * reading or read but not retrieved by user calling \c read method)
160  * calling \c hint function has no effect
161  */
162  bool hint(bid_type bid)
163  {
164  // if block is already hinted, no need to hint it again
165  if (in_prefetching(bid)) {
166  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
167  return true;
168  }
169 
170  if (free_blocks_size) // only if we have a free block
171  {
172  --free_blocks_size;
173  block_type* block = free_blocks.back();
174  free_blocks.pop_back();
175  STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => prefetching");
176  request_ptr req = block->read(bid);
177  busy_blocks[bid] = busy_entry(block, req);
178  return true;
179  }
180  STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => no free blocks for prefetching");
181  return false;
182  }
183 
184  /*!
185  * Gives a hint for prefetching a block, the block may or may not be read
186  * into a prefetch buffer. This variant checks if the write pool is
187  * currently writing said block.
188  *
189  * \param bid address of a block to be prefetched
190  * \return \c true if there was a free block to do prefetch and
191  * prefetching was scheduled, \c false otherwise
192  *
193  * \note If there are no free blocks available (all blocks are already in
194  * reading or read but not retrieved by user calling \c read method)
195  * calling \c hint function has no effect
196  */
198  {
199  // if block is already hinted, no need to hint it again
200  if (in_prefetching(bid)) {
201  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
202  return true;
203  }
204 
205  if (free_blocks_size) // only if we have a free block
206  {
207  --free_blocks_size;
208  block_type* block = free_blocks.back();
209  free_blocks.pop_back();
210  if (w_pool.has_request(bid))
211  {
212  busy_entry wp_request = w_pool.steal_request(bid);
213  STXXL_VERBOSE1("prefetch_pool::hint2 bid=" << bid << " was in write cache at " << wp_request.first);
214  assert(wp_request.first != 0);
215  w_pool.add(block); //in exchange
216  busy_blocks[bid] = wp_request;
217  return true;
218  }
219  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => prefetching");
220  request_ptr req = block->read(bid);
221  busy_blocks[bid] = busy_entry(block, req);
222  return true;
223  }
224  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => no free blocks for prefetching");
225  return false;
226  }
227 
228  //! Cancel a hint request in case the block is no longer desired.
230  {
231  busy_blocks_iterator cache_el = busy_blocks.find(bid);
232  if (cache_el == busy_blocks.end())
233  return false;
234 
235  // cancel request if it is a read request, there might be
236  // write requests 'stolen' from a write_pool that may not be canceled
237  if (cache_el->second.second->get_type() == request::READ)
238  cache_el->second.second->cancel();
239  // finish the request
240  cache_el->second.second->wait();
241  ++free_blocks_size;
242  free_blocks.push_back(cache_el->second.first);
243  busy_blocks.erase(cache_el);
244  return true;
245  }
246 
247  //! Checks if a block is in the hinted block set.
249  {
250  return (busy_blocks.find(bid) != busy_blocks.end());
251  }
252 
253  //! Returns the request pointer for a hinted block, or an invalid NULL
254  //! request in case it was not requested due to lack of prefetch buffers.
256  {
257  busy_blocks_iterator cache_el = busy_blocks.find(bid);
258 
259  if (cache_el == busy_blocks.end())
260  return request_ptr(); // invalid pointer
261  else
262  return cache_el->second.second;
263  }
264 
265  //! Returns true if the blocks was hinted and the request is finished.
266  bool poll(bid_type bid)
267  {
268  request_ptr req = find(bid);
269  return req.valid() ? req->poll() : false;
270  }
271 
272  /*!
273  * Reads block. If this block is cached block is not read but passed from
274  * the cache.
275  *
276  * \param block block object, where data to be read to. If block was cached
277  * \c block 's ownership goes to the pool and block from cache is returned
278  * in \c block value.
279  *
280  * \param bid address of the block
281  *
282  * \warning \c block parameter must be allocated dynamically using \c new .
283  *
284  * \return request pointer object of read operation
285  */
287  {
288  busy_blocks_iterator cache_el = busy_blocks.find(bid);
289  if (cache_el == busy_blocks.end())
290  {
291  // not cached
292  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
293  return block->read(bid);
294  }
295 
296  // cached
297  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
298  ++free_blocks_size;
299  free_blocks.push_back(block);
300  block = cache_el->second.first;
301  request_ptr result = cache_el->second.second;
302  busy_blocks.erase(cache_el);
303  return result;
304  }
305 
307  {
308  // try cache
309  busy_blocks_iterator cache_el = busy_blocks.find(bid);
310  if (cache_el != busy_blocks.end())
311  {
312  // cached
313  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
314  ++free_blocks_size;
315  free_blocks.push_back(block);
316  block = cache_el->second.first;
317  request_ptr result = cache_el->second.second;
318  busy_blocks.erase(cache_el);
319  return result;
320  }
321 
322  // try w_pool cache
323  if (w_pool.has_request(bid))
324  {
325  busy_entry wp_request = w_pool.steal_request(bid);
326  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " was in write cache at " << wp_request.first);
327  assert(wp_request.first != 0);
328  w_pool.add(block); //in exchange
329  block = wp_request.first;
330  return wp_request.second;
331  }
332 
333  // not cached
334  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
335  return block->read(bid);
336  }
337 
338  //! Resizes size of the pool.
339  //! \param new_size desired size of the pool. If some
340  //! blocks are used for prefetching, these blocks can't be freed.
341  //! Only free blocks (not in prefetching) can be freed by reducing
342  //! the size of the pool calling this method.
343  //! \return new size of the pool
345  {
346  int_type diff = int_type(new_size) - int_type(size());
347  if (diff > 0)
348  {
349  free_blocks_size += diff;
350  while (--diff >= 0)
351  free_blocks.push_back(new block_type);
352 
353  return size();
354  }
355 
356  while (diff < 0 && free_blocks_size > 0)
357  {
358  ++diff;
359  --free_blocks_size;
360  delete free_blocks.back();
361  free_blocks.pop_back();
362  }
363  return size();
364  }
365 };
366 
367 //! \}
368 
370 
371 namespace std {
372 
373 template <class BlockType>
376 {
377  a.swap(b);
378 }
379 
380 } // namespace std
381 
382 #endif // !STXXL_MNG_PREFETCH_POOL_HEADER
383 // vim: et:ts=4:sw=4
bool has_request(bid_type bid)
Definition: write_pool.h:197
hash_map_type busy_blocks
blocks that are in reading or already read but not retrieved by user
Definition: prefetch_pool.h:66
bool hint(bid_type bid, write_pool< block_type > &w_pool)
Gives a hint for prefetching a block, the block may or may not be read into a prefetch buffer...
request_ptr read(block_type *&block, bid_type bid, write_pool< block_type > &w_pool)
void swap(prefetch_pool &obj)
Definition: prefetch_pool.h:82
bool in_prefetching(bid_type bid)
Checks if a block is in the hinted block set.
void add(block_type *&block)
Definition: write_pool.h:245
std::list< block_type * > free_blocks
contains free prefetch blocks
Definition: prefetch_pool.h:63
request_ptr find(bid_type bid)
Returns the request pointer for a hinted block, or an invalid NULL request in case it was not request...
void add(block_type *&block)
Add a new block to prefetch pool, enlarges size of pool.
block_type::bid_type bid_type
Definition: prefetch_pool.h:33
bool invalidate(bid_type bid)
Cancel a hint request in case the block is no longer desired.
virtual ~prefetch_pool()
Waits for completion of all ongoing read requests and frees memory.
Definition: prefetch_pool.h:90
hash_map_type::iterator busy_blocks_iterator
Definition: prefetch_pool.h:60
bool hint(bid_type bid)
Gives a hint for prefetching a block, the block may or may not be read into a prefetch buffer...
#define STXXL_VERBOSE2(x)
Definition: verbose.h:121
bool valid() const
test for a non-NULL pointer
Definition: counting_ptr.h:138
std::pair< block_type *, request_ptr > steal_request(bid_type bid)
Definition: write_pool.h:224
#define STXXL_CHECK(condition)
STXXL_CHECK is an assertion macro for unit tests, which contrarily to assert() also works in release ...
Definition: verbose.h:170
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:32
unsigned_type free_blocks_size
count number of free blocks, since traversing the std::list is slow.
Definition: prefetch_pool.h:69
Implements dynamically resizable prefetching pool.
Definition: prefetch_pool.h:29
counting_ptr< request > request_ptr
A reference counting pointer for request.
Definition: request.h:113
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
unsigned_type free_size() const
Returns the number of free prefetching blocks.
std::list< block_type * >::iterator free_blocks_iterator
Definition: prefetch_pool.h:59
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
unsigned_type size() const
Returns number of owned blocks.
unsigned_type busy_size() const
Returns the number of busy prefetching blocks.
block_type * steal()
Take out a block from the pool, one unhinted free block must be available.
unsigned_type resize(unsigned_type new_size)
Resizes size of the pool.
bool poll(bid_type bid)
Returns true if the blocks was hinted and the request is finished.
virtual bool poll()=0
Polls the status of the request.
std::pair< block_type *, request_ptr > busy_entry
Definition: prefetch_pool.h:57
request_ptr read(block_type *&block, bid_type bid)
Reads block.
ExtIterator find(ExtIterator begin, ExtIterator end, const EqualityComparable &value, int_type nbuffers=0)
External equivalent of std::find, see stxxl::find.
Definition: scan.h:289
prefetch_pool(unsigned_type init_size=1)
Constructs pool.
Definition: prefetch_pool.h:74
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
compat_hash_map< bid_type, busy_entry, bid_hash >::result hash_map_type
Definition: prefetch_pool.h:58