Panda3D
 All Classes Functions Variables Enumerations
simpleLru.cxx
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 }
 All Classes Functions Variables Enumerations