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