Panda3D
 All Classes Functions Variables Enumerations
simpleLru.cxx
1 // Filename: simpleLru.cxx
2 // Created by: drose (11May07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "simpleLru.h"
16 #include "indent.h"
17 
18 // We define this as a reference to an allocated object, instead of as
19 // a concrete object, so that it won't get destructed when the program
20 // exits. (If it did, there would be an ordering issue between it and
21 // the various concrete SimpleLru objects which reference it.)
22 LightMutex &SimpleLru::_global_lock = *new LightMutex;
23 
24 ////////////////////////////////////////////////////////////////////
25 // Function: SimpleLru::Constructor
26 // Access: Published
27 // Description:
28 ////////////////////////////////////////////////////////////////////
29 SimpleLru::
30 SimpleLru(const string &name, size_t max_size) :
31  LinkedListNode(true),
32  Namable(name)
33 {
34  _total_size = 0;
35  _max_size = max_size;
36  _active_marker = new SimpleLruPage(0);
37 }
38 
39 ////////////////////////////////////////////////////////////////////
40 // Function: SimpleLru::Destructor
41 // Access: Published, Virtual
42 // Description:
43 ////////////////////////////////////////////////////////////////////
44 SimpleLru::
45 ~SimpleLru() {
46  delete _active_marker;
47 
48 #ifndef NDEBUG
49  // We're shutting down. Force-remove everything remaining, but
50  // don't explicitly evict it (that would force vertex buffers to
51  // write themselves to disk unnecessarily).
52  while (_next != (LinkedListNode *)this) {
53  nassertv(_next != (LinkedListNode *)NULL);
54  ((SimpleLruPage *)_next)->_lru = NULL;
55  ((SimpleLruPage *)_next)->remove_from_list();
56  }
57 #endif
58 }
59 
60 ////////////////////////////////////////////////////////////////////
61 // Function: SimpleLruPage::enqueue_lru
62 // Access: Published
63 // Description: Adds the page to the LRU for the first time, or marks
64 // it recently-accessed if it has already been added.
65 //
66 // If lru is NULL, it means to remove this page from its
67 // LRU.
68 ////////////////////////////////////////////////////////////////////
69 void SimpleLruPage::
71  LightMutexHolder holder(SimpleLru::_global_lock);
72 
73  if (_lru == lru) {
74  if (_lru != (SimpleLru *)NULL) {
75  remove_from_list();
76  insert_before(_lru);
77  }
78  return;
79  }
80 
81  if (_lru != (SimpleLru *)NULL) {
82  remove_from_list();
83  _lru->_total_size -= _lru_size;
84  _lru = NULL;
85  }
86 
87  _lru = lru;
88 
89  if (_lru != (SimpleLru *)NULL) {
90  _lru->_total_size += _lru_size;
91  insert_before(_lru);
92  }
93 
94  // Let's not automatically evict pages; instead, we'll evict only on
95  // an explicit epoch test.
96  // _lru->consider_evict();
97 }
98 
99 ////////////////////////////////////////////////////////////////////
100 // Function: SimpleLru::count_active_size
101 // Access: Published
102 // Description: Returns the total size of the pages that were
103 // enqueued since the last call to begin_epoch().
104 ////////////////////////////////////////////////////////////////////
105 size_t SimpleLru::
107  LightMutexHolder holder(_global_lock);
108  size_t total = 0;
109 
110  LinkedListNode *node = _prev;
111  while (node != _active_marker && node != this) {
112  total += ((SimpleLruPage *)node)->get_lru_size();
113  node = ((SimpleLruPage *)node)->_prev;
114  }
115 
116  return total;
117 }
118 
119 ////////////////////////////////////////////////////////////////////
120 // Function: SimpleLru::output
121 // Access: Published
122 // Description:
123 ////////////////////////////////////////////////////////////////////
124 void SimpleLru::
125 output(ostream &out) const {
126  LightMutexHolder holder(_global_lock);
127  out << "SimpleLru " << get_name()
128  << ", " << _total_size << " of " << _max_size;
129 }
130 
131 ////////////////////////////////////////////////////////////////////
132 // Function: SimpleLru::write
133 // Access: Published, Virtual
134 // Description:
135 ////////////////////////////////////////////////////////////////////
136 void SimpleLru::
137 write(ostream &out, int indent_level) const {
138  indent(out, indent_level) << *this << ":\n";
139 
140  // We write out the list backwards. Things we write out first are
141  // the freshest in the LRU. Things at the end of the list will be
142  // the next to be evicted.
143 
144  LightMutexHolder holder(_global_lock);
145  LinkedListNode *node = _prev;
146  while (node != _active_marker && node != this) {
147  SimpleLruPage *page = (SimpleLruPage *)node;
148  indent(out, indent_level + 2) << *page << " (active)\n";
149  node = page->_prev;
150  }
151  if (node == _active_marker) {
152  node = _active_marker->_prev;
153  while (node != this) {
154  SimpleLruPage *page = (SimpleLruPage *)node;
155  indent(out, indent_level + 2) << *page << "\n";
156  node = page->_prev;
157  }
158  }
159 
160 #ifndef NDEBUG
161  ((SimpleLru *)this)->do_validate();
162 #endif
163 }
164 
165 ////////////////////////////////////////////////////////////////////
166 // Function: SimpleLru::do_evict_to
167 // Access: Private
168 // Description: Evicts pages until the LRU is within the indicated
169 // size. Assumes the lock is already held. If
170 // hard_evict is false, does not evict "active" pages
171 // that were added within this epoch.
172 ////////////////////////////////////////////////////////////////////
173 void SimpleLru::
174 do_evict_to(size_t target_size, bool hard_evict) {
175  if (_next == this) {
176  // Nothing in the queue.
177  return;
178  }
179 
180  // Store the current end of the list. If pages re-enqueue
181  // themselves during this traversal, we don't want to visit them
182  // twice.
183  SimpleLruPage *end = (SimpleLruPage *)_prev;
184 
185  // Now walk through the list.
186  SimpleLruPage *node = (SimpleLruPage *)_next;
187  while (_total_size > target_size) {
188  SimpleLruPage *next = (SimpleLruPage *)node->_next;
189 
190  // We must release the lock while we call evict_lru().
191  _global_lock.release();
192  node->evict_lru();
193  _global_lock.acquire();
194 
195  if (node == end || node == _prev) {
196  // If we reach the original tail of the list, stop.
197  return;
198  }
199  if (!hard_evict && node == _active_marker) {
200  // Also stop if we reach the active marker. Nodes beyond this
201  // were added within this epoch.
202  return;
203  }
204  node = next;
205  }
206 }
207 
208 ////////////////////////////////////////////////////////////////////
209 // Function: SimpleLru::do_validate
210 // Access: Private
211 // Description: Checks that the LRU is internally consistent. Assume
212 // the lock is already held.
213 ////////////////////////////////////////////////////////////////////
214 bool SimpleLru::
215 do_validate() {
216  size_t total = 0;
217 
218  LinkedListNode *node = _next;
219  while (node != this) {
220  total += ((SimpleLruPage *)node)->get_lru_size();
221  node = ((SimpleLruPage *)node)->_next;
222  }
223 
224  return (total == _total_size);
225 }
226 
227 ////////////////////////////////////////////////////////////////////
228 // Function: SimpleLruPage::Destructor
229 // Access: Published, Virtual
230 // Description:
231 ////////////////////////////////////////////////////////////////////
232 SimpleLruPage::
233 ~SimpleLruPage() {
234  if (_lru != NULL) {
235  dequeue_lru();
236  }
237 }
238 
239 ////////////////////////////////////////////////////////////////////
240 // Function: SimpleLruPage::evict_lru
241 // Access: Published, Virtual
242 // Description: Evicts the page from the LRU. Called internally when
243 // the LRU determines that it is full. May also be
244 // called externally when necessary to explicitly evict
245 // the page.
246 //
247 // It is legal for this method to either evict the page
248 // as requested, do nothing (in which case the eviction
249 // will be requested again at the next epoch), or
250 // requeue itself on the tail of the queue (in which
251 // case the eviction will be requested again much
252 // later).
253 ////////////////////////////////////////////////////////////////////
254 void SimpleLruPage::
256  dequeue_lru();
257 }
258 
259 ////////////////////////////////////////////////////////////////////
260 // Function: SimpleLruPage::output
261 // Access: Published, Virtual
262 // Description:
263 ////////////////////////////////////////////////////////////////////
264 void SimpleLruPage::
265 output(ostream &out) const {
266  out << "page " << this << ", " << _lru_size;
267 }
268 
269 ////////////////////////////////////////////////////////////////////
270 // Function: SimpleLruPage::write
271 // Access: Published, Virtual
272 // Description:
273 ////////////////////////////////////////////////////////////////////
274 void SimpleLruPage::
275 write(ostream &out, int indent_level) const {
276  indent(out, indent_level) << *this << "\n";
277 }
An implementation of a very simple LRU algorithm.
Definition: simpleLru.h:31
void release() const
Releases the lightMutex.
void acquire() const
Grabs the lightMutex if it is available.
void enqueue_lru(SimpleLru *lru)
Adds the page to the LRU for the first time, or marks it recently-accessed if it has already been add...
Definition: simpleLru.cxx:70
void dequeue_lru()
Removes the page from its SimpleLru.
Definition: simpleLru.I:164
This just stores the pointers to implement a doubly-linked list of some kind of object.
A base class for all things which can have a name.
Definition: namable.h:29
Similar to MutexHolder, but for a light mutex.
virtual void evict_lru()
Evicts the page from the LRU.
Definition: simpleLru.cxx:255
One atomic piece that may be managed by a SimpleLru chain.
Definition: simpleLru.h:70
size_t count_active_size() const
Returns the total size of the pages that were enqueued since the last call to begin_epoch().
Definition: simpleLru.cxx:106
size_t get_lru_size() const
Returns the size of this page as reported to the LRU, presumably in bytes.
Definition: simpleLru.I:208
This is a standard, non-reentrant mutex, similar to the Mutex class.
Definition: lightMutex.h:45