FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
LRU2Q.h
1 #ifndef __2QLRU__
2 #define __2QLRU__
3 
4 /*
5  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of SAFSlib.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include <deque>
24 #include "cache.h"
25 #include "page_queue.h"
26 
27 #define RECLAIM_NPAGES 32
28 
29 namespace safs
30 {
31 
32 class LRU2Q_cache: public page_cache {
33  class linked_page: public frame {
34  public:
35  linked_page() {
36  }
37 
38  linked_page(off_t offset, char *data): frame(offset, data) {
39  }
40  };
41 
47  class indexed_page_queue: public linked_page_queue {
48  /*
49  * I need to hide this method so no one will be able to
50  * get the iterator.
51  */
52  iterator begin() {
53  return linked_page_queue::begin();
54  }
55 
56  /* This is to acclerate the deletion of any page. */
57  std::map<frame *, linked_obj *const> page_map;
58  public:
59  indexed_page_queue() {
60  }
61 
62  linked_obj *const push_back(frame *pg) {
63  linked_obj *const obj = linked_page_queue::push_back(pg);
64  page_map.insert(std::pair<frame *, linked_obj *const>(pg, obj));
65  return obj;
66  }
67 
68  void pop_front() {
69  if (size() <= 0)
70  return;
71  frame *pg = front();
72  remove(pg);
73  }
74 
75  void remove(frame *pg) {
76  std::map<frame *, linked_obj *const>::iterator it
77  = page_map.find(pg);
78  if (it == page_map.end()) {
79  fprintf(stderr, "page %p (offset %ld) doesn't exist in the queue\n",
80  pg, pg->get_offset());
81  return;
82  }
83  page_map.erase(pg);
84  linked_page_queue::remove(it->second);
85  }
86  };
87 
88  int npages;
89  linked_page *pages;
90  std::map<off_t, linked_page *> page_map;
91  indexed_page_queue free_pages;
92  indexed_page_queue active_queue;
93  indexed_page_queue inactive_queue;
94 
95  void evict_pages() {
96  /*
97  * if the inactive list is larger than active list,
98  * we need to start to move pages from the active
99  * list to the inactive list.
100  */
101  if (inactive_queue.size() < active_queue.size()) {
102  for (int i = 0; i < RECLAIM_NPAGES;) {
103  linked_page *pg = (linked_page *) active_queue.front();
104  active_queue.pop_front();
105  if (pg->referenced()) {
106  pg->set_referenced(false);
107  active_queue.push_back(pg);
108  }
109  else {
110  inactive_queue.push_back(pg);
111  pg->set_active(false);
112  i++;
113  }
114  }
115  }
116 
117  for (int i = 0; i < RECLAIM_NPAGES;) {
118  /* reclaim the oldest pages in the inactive queue. */
119  linked_page *pg = (linked_page *) inactive_queue.front();
120  inactive_queue.pop_front();
121  if (pg->referenced()) {
122  inactive_queue.push_back(pg);
123  pg->set_referenced(false);
124  }
125  else {
126  pg->set_referenced(false);
127  free_pages.push_back(pg);
128  i++;
129  page_map.erase(pg->get_offset());
130  }
131  }
132  }
133 
134  memory_manager *manager;
135 public:
136  LRU2Q_cache(long cache_size) {
137  printf("LRU2Q cache is used\n");
138  npages = cache_size / PAGE_SIZE;
139  pages = new linked_page[npages];
140  manager = memory_manager::create(cache_size, -1);
141  manager->register_cache(this);
142  for (int i = 0; i < npages; i++) {
143  char *page = NULL;
144  manager->get_free_pages(1, &page, this);
145  pages[i] = linked_page(-1, page);
146  free_pages.push_back(&pages[i]);
147  }
148  }
149 
150  page *search(off_t offset, off_t &old_off) {
151  std::map<off_t, linked_page *>::iterator it = page_map.find(offset);
152  if (!(it == page_map.end())) {
153  linked_page *pg = it->second;
154  /* if the page is in the inactive list */
155  if (!pg->active()) {
156  inactive_queue.remove(pg);
157  active_queue.push_back(pg);
158  pg->set_active(true);
159  pg->set_referenced(false);
160  }
161  else
162  pg->set_referenced(true);
163  pg->inc_ref();
164  return pg;
165  }
166 
167  /* we need to get a free page. */
168  if (free_pages.empty())
169  evict_pages();
170  linked_page *pg = (linked_page *) free_pages.front();
171  free_pages.pop_front();
172  page_map.insert(std::pair<off_t, linked_page *>(offset, pg));
173 
174  /* we need to add the page to the inactive queue */
175  inactive_queue.push_back(pg);
176  pg->set_referenced(true);
177  pg->set_active(false);
178  pg->reset_hits();
179  pg->set_data_ready(false);
180  old_off = pg->get_offset();
181  pg->set_offset(offset);
182  pg->inc_ref();
183  pg->hit();
184  return pg;
185  }
186 
187  long size() {
188  return ((long) npages) * PAGE_SIZE;
189  }
190 };
191 
192 }
193 
194 #endif