STXXL  1.4.1
 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) + size_t(bid.offset >> 32);
42  return result;
43  }
44 #if STXXL_MSVC
45  bool operator () (const bid_type& a, const bid_type& b) const
46  {
47  return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
48  }
49  enum
50  { // parameters for hash table
51  bucket_size = 4, // 0 < bucket_size
52  min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
53  };
54 #endif
55  };
56  typedef std::pair<block_type*, request_ptr> busy_entry;
58  typedef typename std::list<block_type*>::iterator free_blocks_iterator;
59  typedef typename hash_map_type::iterator busy_blocks_iterator;
60 
61  // contains free prefetch blocks
62  std::list<block_type*> free_blocks;
63  // blocks that are in reading or already read but not retrieved by user
65 
67 
68 public:
69  //! Constructs pool.
70  //! \param init_size initial number of blocks in the pool
71  explicit prefetch_pool(unsigned_type init_size = 1) : free_blocks_size(init_size)
72  {
73  unsigned_type i = 0;
74  for ( ; i < init_size; ++i)
75  free_blocks.push_back(new block_type);
76  }
77 
78  void swap(prefetch_pool& obj)
79  {
80  std::swap(free_blocks, obj.free_blocks);
81  std::swap(busy_blocks, obj.busy_blocks);
82  std::swap(free_blocks_size, obj.free_blocks_size);
83  }
84 
85  //! Waits for completion of all ongoing read requests and frees memory.
86  virtual ~prefetch_pool()
87  {
88  while (!free_blocks.empty())
89  {
90  delete free_blocks.back();
91  free_blocks.pop_back();
92  }
93 
94  try
95  {
96  busy_blocks_iterator i2 = busy_blocks.begin();
97  for ( ; i2 != busy_blocks.end(); ++i2)
98  {
99  i2->second.second->wait();
100  delete i2->second.first;
101  }
102  }
103  catch (...)
104  { }
105  }
106 
107  //! Returns number of owned blocks.
109  { return free_blocks_size + busy_blocks.size(); }
110 
111  //! Gives a hint for prefetching a block.
112  //! \param bid address of a block to be prefetched
113  //! \return \c true if there was a free block to do prefetch and prefetching
114  //! was scheduled, \c false otherwise
115  //! \note If there are no free blocks available (all blocks
116  //! are already in reading or read but not retrieved by user calling \c read
117  //! method) calling \c hint function has no effect
118  bool hint(bid_type bid)
119  {
120  // if block is already hinted, no need to hint it again
121  if (in_prefetching(bid)) {
122  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
123  return true;
124  }
125 
126  if (free_blocks_size) // only if we have a free block
127  {
128  --free_blocks_size;
129  block_type* block = free_blocks.back();
130  free_blocks.pop_back();
131  STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => prefetching");
132  request_ptr req = block->read(bid);
133  busy_blocks[bid] = busy_entry(block, req);
134  return true;
135  }
136  STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => no free blocks for prefetching");
137  return false;
138  }
139 
141  {
142  // if block is already hinted, no need to hint it again
143  if (in_prefetching(bid)) {
144  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
145  return true;
146  }
147 
148  if (free_blocks_size) // only if we have a free block
149  {
150  --free_blocks_size;
151  block_type* block = free_blocks.back();
152  free_blocks.pop_back();
153  if (w_pool.has_request(bid))
154  {
155  busy_entry wp_request = w_pool.steal_request(bid);
156  STXXL_VERBOSE1("prefetch_pool::hint2 bid=" << bid << " was in write cache at " << wp_request.first);
157  assert(wp_request.first != 0);
158  w_pool.add(block); //in exchange
159  busy_blocks[bid] = wp_request;
160  return true;
161  }
162  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => prefetching");
163  request_ptr req = block->read(bid);
164  busy_blocks[bid] = busy_entry(block, req);
165  return true;
166  }
167  STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => no free blocks for prefetching");
168  return false;
169  }
170 
172  {
173  busy_blocks_iterator cache_el = busy_blocks.find(bid);
174  if (cache_el == busy_blocks.end())
175  return false;
176 
177  // cancel request if it is a read request, there might be
178  // write requests 'stolen' from a write_pool that may not be canceled
179  if (cache_el->second.second->get_type() == request::READ)
180  cache_el->second.second->cancel();
181  // finish the request
182  cache_el->second.second->wait();
183  ++free_blocks_size;
184  free_blocks.push_back(cache_el->second.first);
185  busy_blocks.erase(cache_el);
186  return true;
187  }
188 
190  {
191  return (busy_blocks.find(bid) != busy_blocks.end());
192  }
193 
194  //! Reads block. If this block is cached block is not read but passed from the cache.
195  //! \param block block object, where data to be read to. If block was cached \c block 's
196  //! ownership goes to the pool and block from cache is returned in \c block value.
197  //! \param bid address of the block
198  //! \warning \c block parameter must be allocated dynamically using \c new .
199  //! \return request pointer object of read operation
201  {
202  busy_blocks_iterator cache_el = busy_blocks.find(bid);
203  if (cache_el == busy_blocks.end())
204  {
205  // not cached
206  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
207  return block->read(bid);
208  }
209 
210  // cached
211  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
212  ++free_blocks_size;
213  free_blocks.push_back(block);
214  block = cache_el->second.first;
215  request_ptr result = cache_el->second.second;
216  busy_blocks.erase(cache_el);
217  return result;
218  }
219 
221  {
222  // try cache
223  busy_blocks_iterator cache_el = busy_blocks.find(bid);
224  if (cache_el != busy_blocks.end())
225  {
226  // cached
227  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
228  ++free_blocks_size;
229  free_blocks.push_back(block);
230  block = cache_el->second.first;
231  request_ptr result = cache_el->second.second;
232  busy_blocks.erase(cache_el);
233  return result;
234  }
235 
236  // try w_pool cache
237  if (w_pool.has_request(bid))
238  {
239  busy_entry wp_request = w_pool.steal_request(bid);
240  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " was in write cache at " << wp_request.first);
241  assert(wp_request.first != 0);
242  w_pool.add(block); //in exchange
243  block = wp_request.first;
244  return wp_request.second;
245  }
246 
247  // not cached
248  STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
249  return block->read(bid);
250  }
251 
252  //! Resizes size of the pool.
253  //! \param new_size desired size of the pool. If some
254  //! blocks are used for prefetching, these blocks can't be freed.
255  //! Only free blocks (not in prefetching) can be freed by reducing
256  //! the size of the pool calling this method.
257  //! \return new size of the pool
259  {
260  int_type diff = int_type(new_size) - int_type(size());
261  if (diff > 0)
262  {
263  free_blocks_size += diff;
264  while (--diff >= 0)
265  free_blocks.push_back(new block_type);
266 
267  return size();
268  }
269 
270  while (diff < 0 && free_blocks_size > 0)
271  {
272  ++diff;
273  --free_blocks_size;
274  delete free_blocks.back();
275  free_blocks.pop_back();
276  }
277  return size();
278  }
279 };
280 
281 //! \}
282 
284 
285 namespace std {
286 
287 template <class BlockType>
290 {
291  a.swap(b);
292 }
293 
294 } // namespace std
295 
296 #endif // !STXXL_MNG_PREFETCH_POOL_HEADER
297 // vim: et:ts=4:sw=4
bool has_request(bid_type bid)
Definition: write_pool.h:197
hash_map_type busy_blocks
Definition: prefetch_pool.h:64
bool hint(bid_type bid, write_pool< block_type > &w_pool)
request_ptr read(block_type *&block, bid_type bid, write_pool< block_type > &w_pool)
void swap(prefetch_pool &obj)
Definition: prefetch_pool.h:78
bool in_prefetching(bid_type bid)
void add(block_type *&block)
Definition: write_pool.h:245
std::list< block_type * > free_blocks
Definition: prefetch_pool.h:62
block_type::bid_type bid_type
Definition: prefetch_pool.h:33
bool invalidate(bid_type bid)
virtual ~prefetch_pool()
Waits for completion of all ongoing read requests and frees memory.
Definition: prefetch_pool.h:86
hash_map_type::iterator busy_blocks_iterator
Definition: prefetch_pool.h:59
bool hint(bid_type bid)
Gives a hint for prefetching a block.
#define STXXL_VERBOSE2(x)
Definition: verbose.h:107
std::pair< block_type *, request_ptr > steal_request(bid_type bid)
Definition: write_pool.h:224
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:32
unsigned_type free_blocks_size
Definition: prefetch_pool.h:66
Implements dynamically resizable prefetching pool.
Definition: prefetch_pool.h:29
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:99
std::list< block_type * >::iterator free_blocks_iterator
Definition: prefetch_pool.h:58
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 resize(unsigned_type new_size)
Resizes size of the pool.
std::pair< block_type *, request_ptr > busy_entry
Definition: prefetch_pool.h:56
request_ptr read(block_type *&block, bid_type bid)
Reads block. If this block is cached block is not read but passed from the cache. ...
prefetch_pool(unsigned_type init_size=1)
Constructs pool.
Definition: prefetch_pool.h:71
#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:57