FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
shadow_cell.h
1 #ifndef __SHADOW_CELL_H__
2 #define __SHADOW_CELL_H__
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 "cache.h"
24 
25 /* 36 shadow pages makes exactly 4 cache lines. */
26 #define NUM_SHADOW_PAGES 36
27 
28 namespace safs
29 {
30 
31 class shadow_page
32 {
33  int offset;
34  unsigned char hits;
35  char flags;
36 public:
37  shadow_page() {
38  offset = -1;
39  hits = 0;
40  flags = 0;
41  }
42  shadow_page(page &pg) {
43  offset = pg.get_offset() >> LOG_PAGE_SIZE;
44  hits = pg.get_hits();
45  flags = 0;
46  }
47 
48  void set_referenced(bool referenced) {
49  if (referenced)
50  flags |= 0x1 << REFERENCED_BIT;
51  else
52  flags &= ~(0x1 << REFERENCED_BIT);
53  }
54  bool referenced() {
55  return flags & (0x1 << REFERENCED_BIT);
56  }
57 
58  off_t get_offset() const {
59  return ((off_t) offset) << LOG_PAGE_SIZE;
60  }
61 
62  int get_hits() {
63  return hits;
64  }
65 
66  void set_hits(int hits) {
67  assert (hits <= 0xff);
68  this->hits = hits;
69  }
70 
71  bool is_valid() {
72  return offset != -1;
73  }
74 };
75 
76 #ifdef USE_SHADOW_PAGE
77 
78 class shadow_cell
79 {
80 public:
81  virtual void add(shadow_page pg) = 0;
82  virtual shadow_page search(off_t off) = 0;
83  virtual void scale_down_hits() = 0;
84 };
85 
91 template<class T, int SIZE>
92 class embedded_queue
93 {
94  unsigned short start;
95  unsigned short num;
96  /* the size of the buffer is specified by SIZE. */
97  T buf[SIZE];
98 public:
99  embedded_queue() {
100  assert(SIZE < 0xffff);
101  start = 0;
102  num = 0;
103  }
104 
105  void push_back(T v) {
106  assert(num < SIZE);
107  buf[(start + num) % SIZE] = v;
108  num++;
109  }
110 
111  void pop_front() {
112  assert(num > 0);
113  start = (start + 1) % SIZE;
114  num--;
115  }
116 
117  void remove(int idx);
118 
119  bool is_empty() {
120  return num == 0;
121  }
122 
123  bool is_full() {
124  return num == SIZE;
125  }
126 
127  int size() {
128  return num;
129  }
130 
131  T &back() {
132  assert(num > 0);
133  return buf[(start + num - 1) % SIZE];
134  }
135 
136  T &front() {
137  assert(num > 0);
138  return buf[start];
139  }
140 
141  T &get(int idx) {
142  assert(num > 0);
143  return buf[(start + idx) % SIZE];
144  }
145 
146  void set(T &v, int idx) {
147  buf[(start + idx) % SIZE] = v;
148  }
149 
150  void print_state() {
151  printf("start: %d, num: %d\n", start, num);
152  for (int i = 0; i < this->size(); i++)
153  printf("%ld\t", this->get(i));
154  printf("\n");
155  }
156 };
157 
158 class clock_shadow_cell: public shadow_cell
159 {
160  int last_idx;
161  // TODO adjust to make it fit in cache lines.
162  embedded_queue<shadow_page, NUM_SHADOW_PAGES> queue;
163 public:
164  clock_shadow_cell() {
165  last_idx = 0;
166  }
167 
168  void add(shadow_page pg);
169 
170  shadow_page search(off_t off);
171 
172  void scale_down_hits();
173 };
174 
175 class LRU_shadow_cell: public shadow_cell
176 {
177  embedded_queue<shadow_page, NUM_SHADOW_PAGES> queue;
178 public:
179  LRU_shadow_cell() {
180  }
181 
182  /*
183  * add a page to the cell, which is evicted from hash_cell.
184  * the only thing we need to record is the number of hits
185  * of this page.
186  */
187  void add(shadow_page pg) {
188  if (queue.is_full())
189  queue.pop_front();
190  queue.push_back(pg);
191  }
192 
193  shadow_page search(off_t off);
194 
195  void scale_down_hits();
196 };
197 
198 #endif
199 
200 }
201 
202 #endif