STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
node_cache.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/btree/node_cache.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <[email protected]>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_CONTAINERS_BTREE_NODE_CACHE_HEADER
14 #define STXXL_CONTAINERS_BTREE_NODE_CACHE_HEADER
15 
16 #include <stxxl/bits/config.h>
18 #include <stxxl/bits/io/request.h>
23 
25 
26 #define STXXL_BTREE_CACHE_VERBOSE STXXL_VERBOSE2
27 
28 // TODO: speedup BID2node_ access using search result iterator in the methods
29 
30 namespace btree {
31 
32 template <class NodeType, class BTreeType>
33 class node_cache : private noncopyable
34 {
35 public:
36  typedef BTreeType btree_type;
37  typedef NodeType node_type;
38  typedef typename node_type::block_type block_type;
39  typedef typename node_type::bid_type bid_type;
40  typedef typename btree_type::key_compare key_compare;
41 
42  typedef typename btree_type::alloc_strategy_type alloc_strategy_type;
44 
45 private:
48 
49 /*
50  struct bid_comp
51  {
52  bool operator () (const bid_type & a, const bid_type & b) const
53  {
54  return (a.storage < b.storage) || ( a.storage == b.storage && a.offset < b.offset);
55  }
56  };
57 */
58 
59  struct bid_hash
60  {
61  size_t operator () (const bid_type& bid) const
62  {
63  size_t result =
64  longhash1(bid.offset + reinterpret_cast<uint64>(bid.storage));
65  return result;
66  }
67 #if STXXL_MSVC
68  bool operator () (const bid_type& a, const bid_type& b) const
69  {
70  return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
71  }
72  enum
73  { // parameters for hash table
74  bucket_size = 4, // 0 < bucket_size
75  min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
76  };
77 #endif
78  };
79 
80  std::vector<node_type*> m_nodes;
81  std::vector<request_ptr> m_reqs;
82  std::vector<bool> m_fixed;
83  std::vector<bool> m_dirty;
84  std::vector<int_type> m_free_nodes;
86 
87  //typedef std::map<bid_type,int_type,bid_comp> BID2node_type;
89 
94 
102 
103  // changes btree pointer in all contained iterators
105  {
106  for (typename std::vector<node_type*>::const_iterator it = m_nodes.begin();
107  it != m_nodes.end(); ++it)
108  {
109  (*it)->m_btree = b;
110  }
111  }
112 
113 public:
114  node_cache(unsigned_type cache_size_in_bytes,
115  btree_type* btree,
116  key_compare cmp)
117  : m_btree(btree),
118  m_cmp(cmp),
119  m_bm(block_manager::get_instance()),
120  n_found(0),
121  n_not_found(0),
122  n_created(0),
123  n_deleted(0),
124  n_read(0),
125  n_written(0),
126  n_clean_forced(0)
127  {
128  const unsigned_type nnodes = cache_size_in_bytes / block_type::raw_size;
129  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache constructor nodes=" << nnodes);
130  if (nnodes < 3)
131  {
132  STXXL_THROW2(std::runtime_error, "btree::node_cache::node_cache", "Too few memory for a node cache (<3)");
133  }
134  m_nodes.reserve(nnodes);
135  m_reqs.resize(nnodes);
136  m_free_nodes.reserve(nnodes);
137  m_fixed.resize(nnodes, false);
138  m_dirty.resize(nnodes, true);
139  for (unsigned_type i = 0; i < nnodes; ++i)
140  {
141  m_nodes.push_back(new node_type(m_btree, m_cmp));
142  m_free_nodes.push_back(i);
143  }
144 
145  pager_type tmp_pager(nnodes);
146  std::swap(m_pager, tmp_pager);
147  }
148 
150  {
151  return m_nodes.size();
152  }
153 
154  // returns the number of fixed pages
156  {
157  typename bid2node_type::const_iterator i = m_bid2node.begin();
158  typename bid2node_type::const_iterator end = m_bid2node.end();
159  unsigned_type cnt = 0;
160  for ( ; i != end; ++i)
161  {
162  if (m_fixed[(*i).second])
163  ++cnt;
164  }
165  return cnt;
166  }
167 
169  {
170  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache destructor addr=" << this);
171  typename bid2node_type::const_iterator i = m_bid2node.begin();
172  typename bid2node_type::const_iterator end = m_bid2node.end();
173  for ( ; i != end; ++i)
174  {
175  const unsigned_type p = (*i).second;
176  if (m_reqs[p].valid())
177  m_reqs[p]->wait();
178 
179  if (m_dirty[p])
180  m_nodes[p]->save();
181  }
182  for (unsigned_type i = 0; i < size(); ++i)
183  delete m_nodes[i];
184  }
185 
187  {
188  ++n_created;
189 
190  if (m_free_nodes.empty())
191  {
192  // need to kick a node
193  int_type node2kick;
194  unsigned_type i = 0;
195  const unsigned_type max_tries = size() + 1;
196  do
197  {
198  ++i;
199  node2kick = m_pager.kick();
200  if (i == max_tries)
201  {
202  STXXL_ERRMSG(
203  "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
204  STXXL_ERRMSG("Returning NULL node.");
205  return NULL;
206  }
207  m_pager.hit(node2kick);
208  } while (m_fixed[node2kick]);
209 
210  if (m_reqs[node2kick].valid())
211  m_reqs[node2kick]->wait();
212 
213  node_type& node = *(m_nodes[node2kick]);
214 
215  if (m_dirty[node2kick])
216  {
217  node.save();
218  ++n_written;
219  }
220  else
221  ++n_clean_forced;
222 
223  //reqs_[node2kick] = request_ptr(); // reset request
224 
225  assert(m_bid2node.find(node.my_bid()) != m_bid2node.end());
226  m_bid2node.erase(node.my_bid());
227  m_bm->new_block(m_alloc_strategy, new_bid);
228 
229  m_bid2node[new_bid] = node2kick;
230 
231  node.init(new_bid);
232 
233  m_dirty[node2kick] = true;
234 
235  assert(size() == m_bid2node.size() + m_free_nodes.size());
236 
237  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_new_node, need to kick node " << node2kick);
238 
239  return &node;
240  }
241 
242  int_type free_node = m_free_nodes.back();
243  m_free_nodes.pop_back();
244  assert(m_fixed[free_node] == false);
245 
246  m_bm->new_block(m_alloc_strategy, new_bid);
247  m_bid2node[new_bid] = free_node;
248  node_type& node = *(m_nodes[free_node]);
249  node.init(new_bid);
250 
251  // assert(!(reqs_[free_node].valid()));
252 
253  m_pager.hit(free_node);
254 
255  m_dirty[free_node] = true;
256 
257  assert(size() == m_bid2node.size() + m_free_nodes.size());
258 
259  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_new_node, free node " << free_node << "available");
260 
261  return &node;
262  }
263 
264  node_type * get_node(const bid_type& bid, bool fix = false)
265  {
266  typename bid2node_type::const_iterator it = m_bid2node.find(bid);
267  ++n_read;
268 
269  if (it != m_bid2node.end())
270  {
271  // the node is in cache
272  const int_type nodeindex = it->second;
273  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_node, the node " << nodeindex << "is in cache , fix=" << fix);
274  m_fixed[nodeindex] = fix;
275  m_pager.hit(nodeindex);
276  m_dirty[nodeindex] = true;
277 
278  if (m_reqs[nodeindex].valid() && !m_reqs[nodeindex]->poll())
279  m_reqs[nodeindex]->wait();
280 
281  ++n_found;
282  return m_nodes[nodeindex];
283  }
284 
285  ++n_not_found;
286 
287  // the node is not in cache
288  if (m_free_nodes.empty())
289  {
290  // need to kick a node
291  int_type node2kick;
292  unsigned_type i = 0;
293  const unsigned_type max_tries = size() + 1;
294  do
295  {
296  ++i;
297  node2kick = m_pager.kick();
298  if (i == max_tries)
299  {
300  STXXL_ERRMSG(
301  "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
302  STXXL_ERRMSG("Returning NULL node.");
303  return NULL;
304  }
305  m_pager.hit(node2kick);
306  } while (m_fixed[node2kick]);
307 
308  if (m_reqs[node2kick].valid())
309  m_reqs[node2kick]->wait();
310 
311  node_type& node = *(m_nodes[node2kick]);
312 
313  if (m_dirty[node2kick])
314  {
315  node.save();
316  ++n_written;
317  }
318  else
319  ++n_clean_forced;
320 
321  m_bid2node.erase(node.my_bid());
322 
323  m_reqs[node2kick] = node.load(bid);
324  m_bid2node[bid] = node2kick;
325 
326  m_fixed[node2kick] = fix;
327 
328  m_dirty[node2kick] = true;
329 
330  assert(size() == m_bid2node.size() + m_free_nodes.size());
331 
332  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_node, need to kick node" << node2kick << " fix=" << fix);
333 
334  return &node;
335  }
336 
337  int_type free_node = m_free_nodes.back();
338  m_free_nodes.pop_back();
339  assert(m_fixed[free_node] == false);
340 
341  node_type& node = *(m_nodes[free_node]);
342  m_reqs[free_node] = node.load(bid);
343  m_bid2node[bid] = free_node;
344 
345  m_pager.hit(free_node);
346 
347  m_fixed[free_node] = fix;
348 
349  m_dirty[free_node] = true;
350 
351  assert(size() == m_bid2node.size() + m_free_nodes.size());
352 
353  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_node, free node " << free_node << "available, fix=" << fix);
354 
355  return &node;
356  }
357 
358  node_type const * get_const_node(const bid_type& bid, bool fix = false)
359  {
360  typename bid2node_type::const_iterator it = m_bid2node.find(bid);
361  ++n_read;
362 
363  if (it != m_bid2node.end())
364  {
365  // the node is in cache
366  const int_type nodeindex = it->second;
367  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_node, the node " << nodeindex << "is in cache , fix=" << fix);
368  m_fixed[nodeindex] = fix;
369  m_pager.hit(nodeindex);
370 
371  if (m_reqs[nodeindex].valid() && !m_reqs[nodeindex]->poll())
372  m_reqs[nodeindex]->wait();
373 
374  ++n_found;
375  return m_nodes[nodeindex];
376  }
377 
378  ++n_not_found;
379 
380  // the node is not in cache
381  if (m_free_nodes.empty())
382  {
383  // need to kick a node
384  int_type node2kick;
385  unsigned_type i = 0;
386  const unsigned_type max_tries = size() + 1;
387  do
388  {
389  ++i;
390  node2kick = m_pager.kick();
391  if (i == max_tries)
392  {
393  STXXL_ERRMSG(
394  "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
395  STXXL_ERRMSG("Returning NULL node.");
396  return NULL;
397  }
398  m_pager.hit(node2kick);
399  } while (m_fixed[node2kick]);
400 
401  if (m_reqs[node2kick].valid())
402  m_reqs[node2kick]->wait();
403 
404  node_type& node = *(m_nodes[node2kick]);
405  if (m_dirty[node2kick])
406  {
407  node.save();
408  ++n_written;
409  }
410  else
411  ++n_clean_forced;
412 
413  m_bid2node.erase(node.my_bid());
414 
415  m_reqs[node2kick] = node.load(bid);
416  m_bid2node[bid] = node2kick;
417 
418  m_fixed[node2kick] = fix;
419 
420  m_dirty[node2kick] = false;
421 
422  assert(size() == m_bid2node.size() + m_free_nodes.size());
423 
424  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_node, need to kick node" << node2kick << " fix=" << fix);
425 
426  return &node;
427  }
428 
429  int_type free_node = m_free_nodes.back();
430  m_free_nodes.pop_back();
431  assert(m_fixed[free_node] == false);
432 
433  node_type& node = *(m_nodes[free_node]);
434  m_reqs[free_node] = node.load(bid);
435  m_bid2node[bid] = free_node;
436 
437  m_pager.hit(free_node);
438 
439  m_fixed[free_node] = fix;
440 
441  m_dirty[free_node] = false;
442 
443  assert(size() == m_bid2node.size() + m_free_nodes.size());
444 
445  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache get_node, free node " << free_node << "available, fix=" << fix);
446 
447  return &node;
448  }
449 
450  void delete_node(const bid_type& bid)
451  {
452  typename bid2node_type::const_iterator it = m_bid2node.find(bid);
453  try
454  {
455  if (it != m_bid2node.end())
456  {
457  // the node is in the cache
458  const int_type nodeindex = it->second;
459  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache delete_node " << nodeindex << " from cache.");
460  if (m_reqs[nodeindex].valid())
461  m_reqs[nodeindex]->wait();
462 
463  //reqs_[nodeindex] = request_ptr(); // reset request
464  m_free_nodes.push_back(nodeindex);
465  m_bid2node.erase(bid);
466  m_fixed[nodeindex] = false;
467  }
468  ++n_deleted;
469  } catch (const io_error& ex)
470  {
471  m_bm->delete_block(bid);
472  throw io_error(ex.what());
473  }
474  m_bm->delete_block(bid);
475  }
476 
477  void prefetch_node(const bid_type& bid)
478  {
479  if (m_bid2node.find(bid) != m_bid2node.end())
480  return;
481 
482  // the node is not in cache
483  if (m_free_nodes.empty())
484  {
485  // need to kick a node
486  int_type node2kick;
487  unsigned_type i = 0;
488  const unsigned_type max_tries = size() + 1;
489  do
490  {
491  ++i;
492  node2kick = m_pager.kick();
493  if (i == max_tries)
494  {
495  STXXL_ERRMSG(
496  "The node cache is too small, no node can be kicked out (all nodes are fixed) !");
497  STXXL_ERRMSG("Returning NULL node.");
498  return;
499  }
500  m_pager.hit(node2kick);
501  } while (m_fixed[node2kick]);
502 
503  if (m_reqs[node2kick].valid())
504  m_reqs[node2kick]->wait();
505 
506  node_type& node = *(m_nodes[node2kick]);
507 
508  if (m_dirty[node2kick])
509  {
510  node.save();
511  ++n_written;
512  }
513  else
514  ++n_clean_forced;
515 
516  m_bid2node.erase(node.my_bid());
517 
518  m_reqs[node2kick] = node.prefetch(bid);
519  m_bid2node[bid] = node2kick;
520 
521  m_fixed[node2kick] = false;
522 
523  m_dirty[node2kick] = false;
524 
525  assert(size() == m_bid2node.size() + m_free_nodes.size());
526 
527  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache prefetch_node, need to kick node" << node2kick << " ");
528 
529  return;
530  }
531 
532  int_type free_node = m_free_nodes.back();
533  m_free_nodes.pop_back();
534  assert(m_fixed[free_node] == false);
535 
536  node_type& node = *(m_nodes[free_node]);
537  m_reqs[free_node] = node.prefetch(bid);
538  m_bid2node[bid] = free_node;
539 
540  m_pager.hit(free_node);
541 
542  m_fixed[free_node] = false;
543 
544  m_dirty[free_node] = false;
545 
546  assert(size() == m_bid2node.size() + m_free_nodes.size());
547 
548  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache prefetch_node, free node " << free_node << "available");
549 
550  return;
551  }
552 
553  void unfix_node(const bid_type& bid)
554  {
555  assert(m_bid2node.find(bid) != m_bid2node.end());
556  m_fixed[m_bid2node[bid]] = false;
557  STXXL_BTREE_CACHE_VERBOSE("btree::node_cache unfix_node, node " << m_bid2node[bid]);
558  }
559 
560  void swap(node_cache& obj)
561  {
562  std::swap(m_cmp, obj.m_cmp);
563  std::swap(m_nodes, obj.m_nodes);
564  std::swap(m_reqs, obj.m_reqs);
565  change_btree_pointers(m_btree);
566  obj.change_btree_pointers(obj.m_btree);
567  std::swap(m_fixed, obj.m_fixed);
568  std::swap(m_free_nodes, obj.m_free_nodes);
569  std::swap(m_bid2node, obj.m_bid2node);
570  std::swap(m_pager, obj.m_pager);
571  std::swap(m_alloc_strategy, obj.m_alloc_strategy);
572  std::swap(n_found, obj.n_found);
573  std::swap(n_not_found, obj.n_found);
574  std::swap(n_created, obj.n_created);
575  std::swap(n_deleted, obj.n_deleted);
576  std::swap(n_read, obj.n_read);
577  std::swap(n_written, obj.n_written);
578  std::swap(n_clean_forced, obj.n_clean_forced);
579  }
580 
581  void print_statistics(std::ostream& o) const
582  {
583  if (n_read)
584  o << "Found blocks : " << n_found << " (" <<
585  100. * double(n_found) / double(n_read) << "%)" << std::endl;
586  else
587  o << "Found blocks : " << n_found << " (" <<
588  100 << "%)" << std::endl;
589 
590  o << "Not found blocks : " << n_not_found << std::endl;
591  o << "Created in the cache blocks : " << n_created << std::endl;
592  o << "Deleted blocks : " << n_deleted << std::endl;
593  o << "Read blocks : " << n_read << std::endl;
594  o << "Written blocks : " << n_written << std::endl;
595  o << "Clean blocks forced from the cache: " << n_clean_forced << std::endl;
596  }
598  {
599  n_found = 0;
600  n_not_found = 0;
601  n_created = 0;
602  n_deleted = 0;
603  n_read = 0;
604  n_written = 0;
605  n_clean_forced = 0;
606  }
607 };
608 
609 } // namespace btree
610 
612 
613 namespace std {
614 
615 template <class NodeType, class BTreeType>
618 {
619  a.swap(b);
620 }
621 
622 } // namespace std
623 
624 #endif // !STXXL_CONTAINERS_BTREE_NODE_CACHE_HEADER
stxxl::lru_pager pager_type
Definition: node_cache.h:43
__gnu_cxx::hash_map< KeyType, MappedType, HashType > result
Definition: hash_map.h:61
Block manager class.
Definition: block_manager.h:61
long long int int64
Definition: types.h:38
size_t longhash1(uint64 key_)
Definition: utils.h:230
node_type const * get_const_node(const bid_type &bid, bool fix=false)
Definition: node_cache.h:358
bid2node_type m_bid2node
Definition: node_cache.h:90
void change_btree_pointers(btree_type *b)
Definition: node_cache.h:104
void swap(node_cache &obj)
Definition: node_cache.h:560
node_type::block_type block_type
Definition: node_cache.h:38
std::vector< node_type * > m_nodes
Definition: node_cache.h:80
void prefetch_node(const bid_type &bid)
Definition: node_cache.h:477
void print_statistics(std::ostream &o) const
Definition: node_cache.h:581
btree_type::alloc_strategy_type alloc_strategy_type
Definition: node_cache.h:42
void unfix_node(const bid_type &bid)
Definition: node_cache.h:553
std::vector< bool > m_dirty
Definition: node_cache.h:83
btree_type::key_compare key_compare
Definition: node_cache.h:40
std::vector< bool > m_fixed
Definition: node_cache.h:82
std::vector< int_type > m_free_nodes
Definition: node_cache.h:84
hash_map_type bid2node_type
Definition: node_cache.h:88
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
unsigned_type nfixed() const
Definition: node_cache.h:155
node_cache(unsigned_type cache_size_in_bytes, btree_type *btree, key_compare cmp)
Definition: node_cache.h:114
compat_hash_map< bid_type, int_type, bid_hash >::result hash_map_type
Definition: node_cache.h:85
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
#define STXXL_THROW2(exception_type, location, error_message)
Throws exception_type with &quot;Error in [location] : [error_message]&quot;.
block_manager * m_bm
Definition: node_cache.h:92
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
std::vector< request_ptr > m_reqs
Definition: node_cache.h:81
Pager with LRU replacement strategy.
Definition: pager.h:66
void delete_node(const bid_type &bid)
Definition: node_cache.h:450
node_type * get_new_node(bid_type &new_bid)
Definition: node_cache.h:186
#define STXXL_BTREE_CACHE_VERBOSE
Definition: node_cache.h:26
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
alloc_strategy_type m_alloc_strategy
Definition: node_cache.h:93
node_type::bid_type bid_type
Definition: node_cache.h:39
unsigned_type size() const
Definition: node_cache.h:149
btree_type * m_btree
Definition: node_cache.h:46
node_type * get_node(const bid_type &bid, bool fix=false)
Definition: node_cache.h:264
#define STXXL_END_NAMESPACE
Definition: namespace.h:17