00001 // Filename: simpleLru.cxx 00002 // Created by: drose (11May07) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "simpleLru.h" 00016 #include "indent.h" 00017 00018 // We define this as a reference to an allocated object, instead of as 00019 // a concrete object, so that it won't get destructed when the program 00020 // exits. (If it did, there would be an ordering issue between it and 00021 // the various concrete SimpleLru objects which reference it.) 00022 LightMutex &SimpleLru::_global_lock = *new LightMutex; 00023 00024 //////////////////////////////////////////////////////////////////// 00025 // Function: SimpleLru::Constructor 00026 // Access: Published 00027 // Description: 00028 //////////////////////////////////////////////////////////////////// 00029 SimpleLru:: 00030 SimpleLru(const string &name, size_t max_size) : 00031 LinkedListNode(true), 00032 Namable(name) 00033 { 00034 _total_size = 0; 00035 _max_size = max_size; 00036 _active_marker = new SimpleLruPage(0); 00037 } 00038 00039 //////////////////////////////////////////////////////////////////// 00040 // Function: SimpleLru::Destructor 00041 // Access: Published, Virtual 00042 // Description: 00043 //////////////////////////////////////////////////////////////////// 00044 SimpleLru:: 00045 ~SimpleLru() { 00046 delete _active_marker; 00047 00048 #ifndef NDEBUG 00049 // We're shutting down. Force-remove everything remaining, but 00050 // don't explicitly evict it (that would force vertex buffers to 00051 // write themselves to disk unnecessarily). 00052 while (_next != (LinkedListNode *)this) { 00053 nassertv(_next != (LinkedListNode *)NULL); 00054 ((SimpleLruPage *)_next)->_lru = NULL; 00055 ((SimpleLruPage *)_next)->remove_from_list(); 00056 } 00057 #endif 00058 } 00059 00060 //////////////////////////////////////////////////////////////////// 00061 // Function: SimpleLruPage::enqueue_lru 00062 // Access: Published 00063 // Description: Adds the page to the LRU for the first time, or marks 00064 // it recently-accessed if it has already been added. 00065 // 00066 // If lru is NULL, it means to remove this page from its 00067 // LRU. 00068 //////////////////////////////////////////////////////////////////// 00069 void SimpleLruPage:: 00070 enqueue_lru(SimpleLru *lru) { 00071 LightMutexHolder holder(SimpleLru::_global_lock); 00072 00073 if (_lru == lru) { 00074 if (_lru != (SimpleLru *)NULL) { 00075 remove_from_list(); 00076 insert_before(_lru); 00077 } 00078 return; 00079 } 00080 00081 if (_lru != (SimpleLru *)NULL) { 00082 remove_from_list(); 00083 _lru->_total_size -= _lru_size; 00084 _lru = NULL; 00085 } 00086 00087 _lru = lru; 00088 00089 if (_lru != (SimpleLru *)NULL) { 00090 _lru->_total_size += _lru_size; 00091 insert_before(_lru); 00092 } 00093 00094 // Let's not automatically evict pages; instead, we'll evict only on 00095 // an explicit epoch test. 00096 // _lru->consider_evict(); 00097 } 00098 00099 //////////////////////////////////////////////////////////////////// 00100 // Function: SimpleLru::count_active_size 00101 // Access: Published 00102 // Description: Returns the total size of the pages that were 00103 // enqueued since the last call to begin_epoch(). 00104 //////////////////////////////////////////////////////////////////// 00105 size_t SimpleLru:: 00106 count_active_size() const { 00107 LightMutexHolder holder(_global_lock); 00108 size_t total = 0; 00109 00110 LinkedListNode *node = _prev; 00111 while (node != _active_marker && node != this) { 00112 total += ((SimpleLruPage *)node)->get_lru_size(); 00113 node = ((SimpleLruPage *)node)->_prev; 00114 } 00115 00116 return total; 00117 } 00118 00119 //////////////////////////////////////////////////////////////////// 00120 // Function: SimpleLru::output 00121 // Access: Published 00122 // Description: 00123 //////////////////////////////////////////////////////////////////// 00124 void SimpleLru:: 00125 output(ostream &out) const { 00126 LightMutexHolder holder(_global_lock); 00127 out << "SimpleLru " << get_name() 00128 << ", " << _total_size << " of " << _max_size; 00129 } 00130 00131 //////////////////////////////////////////////////////////////////// 00132 // Function: SimpleLru::write 00133 // Access: Published, Virtual 00134 // Description: 00135 //////////////////////////////////////////////////////////////////// 00136 void SimpleLru:: 00137 write(ostream &out, int indent_level) const { 00138 indent(out, indent_level) << *this << ":\n"; 00139 00140 // We write out the list backwards. Things we write out first are 00141 // the freshest in the LRU. Things at the end of the list will be 00142 // the next to be evicted. 00143 00144 LightMutexHolder holder(_global_lock); 00145 LinkedListNode *node = _prev; 00146 while (node != _active_marker && node != this) { 00147 SimpleLruPage *page = (SimpleLruPage *)node; 00148 indent(out, indent_level + 2) << *page << " (active)\n"; 00149 node = page->_prev; 00150 } 00151 if (node == _active_marker) { 00152 node = _active_marker->_prev; 00153 while (node != this) { 00154 SimpleLruPage *page = (SimpleLruPage *)node; 00155 indent(out, indent_level + 2) << *page << "\n"; 00156 node = page->_prev; 00157 } 00158 } 00159 00160 #ifndef NDEBUG 00161 ((SimpleLru *)this)->do_validate(); 00162 #endif 00163 } 00164 00165 //////////////////////////////////////////////////////////////////// 00166 // Function: SimpleLru::do_evict_to 00167 // Access: Private 00168 // Description: Evicts pages until the LRU is within the indicated 00169 // size. Assumes the lock is already held. If 00170 // hard_evict is false, does not evict "active" pages 00171 // that were added within this epoch. 00172 //////////////////////////////////////////////////////////////////// 00173 void SimpleLru:: 00174 do_evict_to(size_t target_size, bool hard_evict) { 00175 if (_next == this) { 00176 // Nothing in the queue. 00177 return; 00178 } 00179 00180 // Store the current end of the list. If pages re-enqueue 00181 // themselves during this traversal, we don't want to visit them 00182 // twice. 00183 SimpleLruPage *end = (SimpleLruPage *)_prev; 00184 00185 // Now walk through the list. 00186 SimpleLruPage *node = (SimpleLruPage *)_next; 00187 while (_total_size > target_size) { 00188 SimpleLruPage *next = (SimpleLruPage *)node->_next; 00189 00190 // We must release the lock while we call evict_lru(). 00191 _global_lock.release(); 00192 node->evict_lru(); 00193 _global_lock.acquire(); 00194 00195 if (node == end || node == _prev) { 00196 // If we reach the original tail of the list, stop. 00197 return; 00198 } 00199 if (!hard_evict && node == _active_marker) { 00200 // Also stop if we reach the active marker. Nodes beyond this 00201 // were added within this epoch. 00202 return; 00203 } 00204 node = next; 00205 } 00206 } 00207 00208 //////////////////////////////////////////////////////////////////// 00209 // Function: SimpleLru::do_validate 00210 // Access: Private 00211 // Description: Checks that the LRU is internally consistent. Assume 00212 // the lock is already held. 00213 //////////////////////////////////////////////////////////////////// 00214 bool SimpleLru:: 00215 do_validate() { 00216 size_t total = 0; 00217 00218 LinkedListNode *node = _next; 00219 while (node != this) { 00220 total += ((SimpleLruPage *)node)->get_lru_size(); 00221 node = ((SimpleLruPage *)node)->_next; 00222 } 00223 00224 return (total == _total_size); 00225 } 00226 00227 //////////////////////////////////////////////////////////////////// 00228 // Function: SimpleLruPage::Destructor 00229 // Access: Published, Virtual 00230 // Description: 00231 //////////////////////////////////////////////////////////////////// 00232 SimpleLruPage:: 00233 ~SimpleLruPage() { 00234 if (_lru != NULL) { 00235 dequeue_lru(); 00236 } 00237 } 00238 00239 //////////////////////////////////////////////////////////////////// 00240 // Function: SimpleLruPage::evict_lru 00241 // Access: Published, Virtual 00242 // Description: Evicts the page from the LRU. Called internally when 00243 // the LRU determines that it is full. May also be 00244 // called externally when necessary to explicitly evict 00245 // the page. 00246 // 00247 // It is legal for this method to either evict the page 00248 // as requested, do nothing (in which case the eviction 00249 // will be requested again at the next epoch), or 00250 // requeue itself on the tail of the queue (in which 00251 // case the eviction will be requested again much 00252 // later). 00253 //////////////////////////////////////////////////////////////////// 00254 void SimpleLruPage:: 00255 evict_lru() { 00256 dequeue_lru(); 00257 } 00258 00259 //////////////////////////////////////////////////////////////////// 00260 // Function: SimpleLruPage::output 00261 // Access: Published, Virtual 00262 // Description: 00263 //////////////////////////////////////////////////////////////////// 00264 void SimpleLruPage:: 00265 output(ostream &out) const { 00266 out << "page " << this << ", " << _lru_size; 00267 } 00268 00269 //////////////////////////////////////////////////////////////////// 00270 // Function: SimpleLruPage::write 00271 // Access: Published, Virtual 00272 // Description: 00273 //////////////////////////////////////////////////////////////////// 00274 void SimpleLruPage:: 00275 write(ostream &out, int indent_level) const { 00276 indent(out, indent_level) << *this << "\n"; 00277 }