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