Panda3D
 All Classes Functions Variables Enumerations
adaptiveLru.cxx
00001 // Filename: adaptiveLru.cxx
00002 // Created by:  drose (03Sep08)
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 "adaptiveLru.h"
00016 #include "config_gobj.h"
00017 #include "clockObject.h"
00018 #include "indent.h"
00019 
00020 static const int HIGH_PRIORITY_SCALE = 4;
00021 static const int LOW_PRIORITY_RANGE = 25;
00022 
00023 ////////////////////////////////////////////////////////////////////
00024 //     Function: AdaptiveLru::Constructor
00025 //       Access: Published
00026 //  Description: 
00027 ////////////////////////////////////////////////////////////////////
00028 AdaptiveLru::
00029 AdaptiveLru(const string &name, size_t max_size) : 
00030   Namable(name)
00031 {
00032   _total_size = 0;
00033   _max_size = max_size;
00034 
00035   _current_frame_identifier = 0;
00036   _weight = adaptive_lru_weight;
00037   _max_updates_per_frame = adaptive_lru_max_updates_per_frame;
00038 
00039   // Initialize our list heads to empty.
00040   _static_list._next = &_static_list;
00041   _static_list._prev = &_static_list;
00042 
00043   int index;
00044   for (index = 0; index < LPP_TotalPriorities; ++index) {
00045     _page_array[index]._next = &_page_array[index];
00046     _page_array[index]._prev = &_page_array[index];
00047   }
00048 }
00049 
00050 ////////////////////////////////////////////////////////////////////
00051 //     Function: AdaptiveLru::Destructor
00052 //       Access: Published, Virtual
00053 //  Description: 
00054 ////////////////////////////////////////////////////////////////////
00055 AdaptiveLru::
00056 ~AdaptiveLru() {
00057 #ifndef NDEBUG
00058   // We're shutting down.  Force-remove everything remaining, but
00059   // don't explicitly evict it (that would force vertex buffers to
00060   // write themselves to disk unnecessarily).
00061 
00062   while (_static_list._next != &_static_list) {
00063     nassertv(_static_list._next != (LinkedListNode *)NULL);
00064     AdaptiveLruPage *page = (AdaptiveLruPage *)(AdaptiveLruPageStaticList *)_static_list._next;
00065 
00066     page->_lru = NULL;
00067     ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
00068     ((AdaptiveLruPageStaticList *)page)->remove_from_list();
00069   }
00070 #endif
00071 }
00072 
00073 ////////////////////////////////////////////////////////////////////
00074 //     Function: AdaptiveLru::do_partial_lru_update
00075 //       Access: Private
00076 //  Description: This only updates a number of pages up to the
00077 //               specified maximum_updates.  Assumes the lock is held.
00078 ////////////////////////////////////////////////////////////////////
00079 void AdaptiveLru::
00080 do_partial_lru_update(int num_updates) {
00081   // Iterate sequentially through the static list of pages.  As we
00082   // process each page, pop it and push it back on the tail.  Stop
00083   // when we have processed num_updates, or come back to the starting
00084   // one.
00085 
00086   AdaptiveLruPageStaticList *start_node = (AdaptiveLruPageStaticList *)_static_list._next;
00087   if (start_node == &_static_list) {
00088     // List is empty.
00089     return;
00090   }
00091 
00092   AdaptiveLruPageStaticList *node = start_node;
00093   do {
00094     AdaptiveLruPageStaticList *next = (AdaptiveLruPageStaticList *)node->_next;
00095     if (--num_updates <= 0) {
00096       return;
00097     }
00098 
00099     update_page((AdaptiveLruPage *)node);
00100     node->remove_from_list();
00101     node->insert_before(&_static_list);
00102     node = next;
00103   } while (node != start_node && node != &_static_list);
00104 }
00105 
00106 ////////////////////////////////////////////////////////////////////
00107 //     Function: AdaptiveLru::update_page
00108 //       Access: Private
00109 //  Description: This updates the page's average utilization.
00110 //               Priority LPP_New is considered to be average usage
00111 //               of 1.0 (which means the page is used once per frame
00112 //               on average).  Priorities < LPP_New are for pages
00113 //               used more than once per frame and Priorities >
00114 //               LPP_New are for pages used less than once per frame.
00115 //
00116 //               Assumes the lock is held.
00117 ////////////////////////////////////////////////////////////////////
00118 void AdaptiveLru::
00119 update_page(AdaptiveLruPage *page) {
00120   int target_priority = page->_priority;
00121   unsigned int lifetime_frames = _current_frame_identifier - page->_first_frame_identifier;
00122   if (lifetime_frames > 0) {
00123     if (page->_update_frame_identifier) {
00124       unsigned int update_frames;
00125       
00126       update_frames = (_current_frame_identifier - page->_update_frame_identifier);
00127       if (update_frames > 0) {
00128         PN_stdfloat update_average_frame_utilization =
00129           (PN_stdfloat) (page->_update_total_usage) / (PN_stdfloat)update_frames;
00130 
00131         page->_average_frame_utilization =
00132           calculate_exponential_moving_average(update_average_frame_utilization, 
00133                                                page->_average_frame_utilization);
00134 
00135         target_priority = page->_priority;
00136         if (page->_average_frame_utilization >= 1.0f) {
00137           int integer_average_frame_utilization;
00138           
00139           integer_average_frame_utilization =
00140             (int) ((page->_average_frame_utilization - 1.0f) *
00141                    (PN_stdfloat) HIGH_PRIORITY_SCALE);
00142           if (integer_average_frame_utilization >= LPP_New) {
00143             integer_average_frame_utilization = LPP_New;
00144           }
00145           integer_average_frame_utilization = LPP_New -
00146             integer_average_frame_utilization;
00147           target_priority = integer_average_frame_utilization;
00148         } else {
00149           int integer_average_frame_utilization;
00150           
00151           integer_average_frame_utilization = (int)
00152             (page->_average_frame_utilization *
00153              (PN_stdfloat) LOW_PRIORITY_RANGE);
00154           integer_average_frame_utilization = LOW_PRIORITY_RANGE -
00155             integer_average_frame_utilization;
00156           target_priority = LPP_New + integer_average_frame_utilization;
00157         }
00158       }
00159     }
00160 
00161     page->_update_frame_identifier = _current_frame_identifier;
00162     page->_update_total_usage = 0;
00163   }
00164 
00165   if (target_priority != page->_priority) {
00166     page->_priority = min(max(target_priority, 0), LPP_TotalPriorities - 1);
00167     ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
00168     ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]);
00169   }
00170 }
00171 
00172 ////////////////////////////////////////////////////////////////////
00173 //     Function: AdaptiveLruPage::enqueue_lru
00174 //       Access: Published
00175 //  Description: Adds the page to the LRU for the first time, or marks
00176 //               it recently-accessed if it has already been added.
00177 //
00178 //               If lru is NULL, it means to remove this page from its
00179 //               LRU.
00180 ////////////////////////////////////////////////////////////////////
00181 void AdaptiveLruPage::
00182 enqueue_lru(AdaptiveLru *lru) {
00183   if (lru != _lru && _lru != (AdaptiveLru *)NULL) {
00184     // It was previously on a different LRU.  Remove it first.
00185     _lru->do_remove_page(this);
00186     _lru = NULL;
00187   }
00188 
00189   if (lru == _lru) {
00190     if (_lru != (AdaptiveLru *)NULL) {
00191       // It's already on this LRU.  Access it.
00192       _lru->do_access_page(this);
00193     }
00194   } else {
00195     nassertv(lru != (AdaptiveLru *)NULL);
00196     // Add it to a new LRU.
00197     _lru = lru;
00198 
00199     _priority = AdaptiveLru::LPP_New;
00200     _first_frame_identifier = _lru->_current_frame_identifier;
00201     _current_frame_identifier = _lru->_current_frame_identifier;
00202     _lru->do_add_page(this);
00203   }
00204 }
00205 
00206 ////////////////////////////////////////////////////////////////////
00207 //     Function: AdaptiveLru::count_active_size
00208 //       Access: Published
00209 //  Description: Returns the total size of the pages that were
00210 //               enqueued since the last call to begin_epoch().
00211 ////////////////////////////////////////////////////////////////////
00212 size_t AdaptiveLru::
00213 count_active_size() const {
00214   size_t counted_size = 0;
00215 
00216   AdaptiveLruPageStaticList *node = (AdaptiveLruPageStaticList *)_static_list._next;
00217   while (node != &_static_list) {
00218     AdaptiveLruPage *page = (AdaptiveLruPage *)node;
00219     if (page->_current_frame_identifier + 1 >= _current_frame_identifier) {
00220       counted_size += page->_lru_size;
00221     }
00222     node = (AdaptiveLruPageStaticList *)node->_next;
00223   }
00224 
00225   return counted_size;
00226 }
00227 
00228 ////////////////////////////////////////////////////////////////////
00229 //     Function: AdaptiveLru::begin_epoch
00230 //       Access: Published
00231 //  Description: Marks the end of the previous epoch and the beginning
00232 //               of the next one.  This will evict any objects that
00233 //               are pending eviction, and also update any internal
00234 //               bookkeeping.
00235 ////////////////////////////////////////////////////////////////////
00236 void AdaptiveLru::
00237 begin_epoch() {
00238   LightMutexHolder holder(_lock);
00239   do_partial_lru_update(_max_updates_per_frame);
00240   if (_total_size > _max_size) {
00241     do_evict_to(_max_size, false);
00242   }
00243 
00244   _current_frame_identifier = ClockObject::get_global_clock()->get_frame_count();
00245 }
00246 
00247 ////////////////////////////////////////////////////////////////////
00248 //     Function: AdaptiveLru::output
00249 //       Access: Published
00250 //  Description: 
00251 ////////////////////////////////////////////////////////////////////
00252 void AdaptiveLru::
00253 output(ostream &out) const {
00254   LightMutexHolder holder(_lock);
00255   out << "AdaptiveLru " << get_name()
00256       << ", " << _total_size << " of " << _max_size;
00257 }
00258 
00259 ////////////////////////////////////////////////////////////////////
00260 //     Function: AdaptiveLru::write
00261 //       Access: Published, Virtual
00262 //  Description: 
00263 ////////////////////////////////////////////////////////////////////
00264 void AdaptiveLru::
00265 write(ostream &out, int indent_level) const {
00266   indent(out, indent_level) << *this << ":\n";
00267 
00268   // We write out the list backwards.  Things we write out first are
00269   // the freshest in the LRU.  Things at the end of the list will be
00270   // the next to be evicted.
00271 
00272   LightMutexHolder holder(_lock);
00273 
00274   int index;
00275   for (index = 0; index < LPP_TotalPriorities; ++index) {
00276     AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._prev;
00277     if (node != &_page_array[index]) {
00278       indent(out, indent_level + 2) << "Priority " << index << ":\n";
00279       while (node != &_page_array[index]) {
00280         AdaptiveLruPage *page = (AdaptiveLruPage *)node;
00281         indent(out, indent_level + 4) << *page;
00282 
00283         if (page->_current_frame_identifier + 1 >= _current_frame_identifier) {
00284           out << " (active)";
00285         }
00286         out << "\n";
00287 
00288         node = (AdaptiveLruPageDynamicList *)node->_prev;
00289       }
00290     }
00291   }
00292 
00293 #ifndef NDEBUG
00294   ((AdaptiveLru *)this)->do_validate();
00295 #endif
00296 }
00297 
00298 ////////////////////////////////////////////////////////////////////
00299 //     Function: AdaptiveLru::do_add_page
00300 //       Access: Private
00301 //  Description: Adds a new page the the LRU.
00302 ////////////////////////////////////////////////////////////////////
00303 void AdaptiveLru::
00304 do_add_page(AdaptiveLruPage *page) {
00305   nassertv(page != (AdaptiveLruPage *)NULL && page->_lru == this);
00306   LightMutexHolder holder(_lock);
00307 
00308   _total_size += page->_lru_size;
00309   ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]);
00310   ((AdaptiveLruPageStaticList *)page)->insert_before(&_static_list);
00311 }
00312 
00313 ////////////////////////////////////////////////////////////////////
00314 //     Function: AdaptiveLru::do_remove_page
00315 //       Access: Private
00316 //  Description: Removes a page from the LRU.
00317 ////////////////////////////////////////////////////////////////////
00318 void AdaptiveLru::
00319 do_remove_page(AdaptiveLruPage *page) {
00320   nassertv(page != (AdaptiveLruPage *)NULL && page->_lru == this);
00321   LightMutexHolder holder(_lock);
00322 
00323   _total_size -= page->_lru_size;
00324   ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
00325   ((AdaptiveLruPageStaticList *)page)->remove_from_list();
00326 }
00327 
00328 ////////////////////////////////////////////////////////////////////
00329 //     Function: AdaptiveLru::do_access_page
00330 //       Access: Private
00331 //  Description: Marks a page accessed.
00332 ////////////////////////////////////////////////////////////////////
00333 void AdaptiveLru::
00334 do_access_page(AdaptiveLruPage *page) {
00335   nassertv(page != (AdaptiveLruPage *)NULL && page->_lru == this);
00336   LightMutexHolder holder(_lock);
00337 
00338   if (page->_current_frame_identifier == _current_frame_identifier) {
00339     // This is the second or more time this page is accessed this
00340     // frame.
00341     ++(page->_current_frame_usage);
00342 
00343   } else {
00344     // This page has not yet been accessed this frame.  Update it.
00345     page->_current_frame_identifier = _current_frame_identifier;
00346     page->_last_frame_usage = page->_current_frame_usage;
00347     page->_current_frame_usage = 1;
00348   }
00349 
00350   // Move it to the tail of its priority list.
00351   ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
00352   ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]);
00353 
00354   ++(page->_update_total_usage);
00355 }
00356 
00357 ////////////////////////////////////////////////////////////////////
00358 //     Function: AdaptiveLru::do_evict_to
00359 //       Access: Private
00360 //  Description: Evicts pages until the LRU is within the indicated
00361 //               size.  Assumes the lock is already held.  If
00362 //               hard_evict is false, does not evict "active" pages
00363 //               that were added within this epoch.
00364 ////////////////////////////////////////////////////////////////////
00365 void AdaptiveLru::
00366 do_evict_to(size_t target_size, bool hard_evict) {
00367   int attempts;
00368 
00369   attempts = 0;
00370   do {
00371     // page out lower priority pages first
00372     int index;
00373     for (index = LPP_TotalPriorities - 1; index >= 0; index--) {
00374 
00375       // Store the current end of the list.  If pages re-enqueue
00376       // themselves during this traversal, we don't want to visit them
00377       // twice.
00378       AdaptiveLruPageDynamicList *end = (AdaptiveLruPageDynamicList *)_page_array[index]._prev;
00379 
00380       AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._next;
00381 
00382       while (node != &_page_array[index]) {
00383         AdaptiveLruPageDynamicList *next = (AdaptiveLruPageDynamicList *)node->_next;
00384         AdaptiveLruPage *page = (AdaptiveLruPage *)node;
00385 
00386         if (attempts == 0 && 
00387             (page->_current_frame_identifier + 1 >= _current_frame_identifier)) {
00388           // avoid swapping out pages used in the current and last
00389           // frame on the first attempt
00390 
00391         } else {
00392           // We must release the lock while we call evict_lru().
00393           _lock.release();
00394           page->evict_lru();
00395           _lock.acquire();
00396 
00397           if (_total_size <= target_size) {
00398             // We've evicted enough to satisfy our target.
00399             return;
00400           }
00401         }
00402         if (node == end) {
00403           // We've reached the former end of the list.  Stop here;
00404           // everything after has been re-queued.
00405           break;
00406         }
00407         node = next;
00408       }
00409     }
00410     attempts++;
00411   } while (hard_evict && attempts < 2);
00412 }
00413 
00414 ////////////////////////////////////////////////////////////////////
00415 //     Function: AdaptiveLru::do_validate
00416 //       Access: Private
00417 //  Description: Checks that the LRU is internally consistent.  Assume
00418 //               the lock is already held.
00419 ////////////////////////////////////////////////////////////////////
00420 bool AdaptiveLru::
00421 do_validate() {
00422   bool okflag = true;
00423   pset<AdaptiveLruPage *> pages;
00424 
00425   // First, walk through the dynamic pages.
00426   size_t counted_size = 0;
00427   int index;
00428   for (index = 0; index < LPP_TotalPriorities; ++index) {
00429     AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._next;
00430     while (node != &_page_array[index]) {
00431       AdaptiveLruPage *page = (AdaptiveLruPage *)node;
00432       counted_size += page->_lru_size;
00433       if (page->_priority != index) {
00434         nout << "page " << page << " has priority " << page->_priority
00435              << " but is in queue " << index << "\n";
00436         okflag = false;
00437       }
00438 
00439       bool inserted_ok = pages.insert(page).second;
00440       if (!inserted_ok) {
00441         nout << "page " << page << " appears more than once in the dynamic index\n";
00442         okflag = false;
00443       }
00444       node = (AdaptiveLruPageDynamicList *)node->_next;
00445     }
00446   }
00447 
00448   if (counted_size != _total_size) {
00449     nout << "count " << counted_size << " bytes in dynamic index, but have " << _total_size << " on record\n";
00450     okflag = false;
00451   }
00452 
00453   // Now, walk through the static pages.
00454   counted_size = 0;
00455   AdaptiveLruPageStaticList *node = (AdaptiveLruPageStaticList *)_static_list._next;
00456   while (node != &_static_list) {
00457     AdaptiveLruPage *page = (AdaptiveLruPage *)node;
00458     counted_size += page->_lru_size;
00459     
00460     if (pages.find(page) == pages.end()) {
00461       nout << "page " << page << " appears in dynamic index, but not in static index (or multiple times in static index)\n";
00462       okflag = false;
00463     } else {
00464       pages.erase(page);
00465     }
00466     node = (AdaptiveLruPageStaticList *)node->_next;
00467   }
00468 
00469   if (counted_size != _total_size) {
00470     nout << "count " << counted_size << " bytes in static index, but have " << _total_size << " on record\n";
00471     okflag = false;
00472   }
00473 
00474   return okflag;
00475 }
00476 
00477 ////////////////////////////////////////////////////////////////////
00478 //     Function: AdaptiveLruPage::Constructor
00479 //       Access: Protected
00480 //  Description: 
00481 ////////////////////////////////////////////////////////////////////
00482 AdaptiveLruPage::
00483 AdaptiveLruPage(size_t lru_size) :
00484   _lru(NULL),
00485   _lru_size(lru_size),
00486   _priority(0),
00487   _first_frame_identifier(0),
00488   _current_frame_identifier(0),
00489   _update_frame_identifier(0),
00490   _current_frame_usage(0),
00491   _last_frame_usage(0),
00492   _total_usage(0),
00493   _update_total_usage(0),
00494   _average_frame_utilization(1.0f)
00495 {
00496 }
00497 
00498 ////////////////////////////////////////////////////////////////////
00499 //     Function: AdaptiveLruPage::Copy Constructor
00500 //       Access: Protected
00501 //  Description: 
00502 ////////////////////////////////////////////////////////////////////
00503 AdaptiveLruPage::
00504 AdaptiveLruPage(const AdaptiveLruPage &copy) :
00505   _lru(NULL),
00506   _lru_size(copy._lru_size),
00507   _priority(0),
00508   _first_frame_identifier(0),
00509   _current_frame_identifier(0),
00510   _update_frame_identifier(0),
00511   _current_frame_usage(0),
00512   _last_frame_usage(0),
00513   _total_usage(0),
00514   _update_total_usage(0),
00515   _average_frame_utilization(1.0f)
00516 {
00517 }
00518 
00519 ////////////////////////////////////////////////////////////////////
00520 //     Function: AdaptiveLruPage::Copy Assignment Operator
00521 //       Access: Protected
00522 //  Description: 
00523 ////////////////////////////////////////////////////////////////////
00524 void AdaptiveLruPage::
00525 operator = (const AdaptiveLruPage &copy) {
00526   set_lru_size(copy.get_lru_size());
00527 }
00528 
00529 ////////////////////////////////////////////////////////////////////
00530 //     Function: AdaptiveLruPage::Destructor
00531 //       Access: Published, Virtual
00532 //  Description: 
00533 ////////////////////////////////////////////////////////////////////
00534 AdaptiveLruPage::
00535 ~AdaptiveLruPage() {
00536   if (_lru != NULL) {
00537     dequeue_lru();
00538   }
00539 }
00540 
00541 ////////////////////////////////////////////////////////////////////
00542 //     Function: AdaptiveLruPage::evict_lru
00543 //       Access: Published, Virtual
00544 //  Description: Evicts the page from the LRU.  Called internally when
00545 //               the LRU determines that it is full.  May also be
00546 //               called externally when necessary to explicitly evict
00547 //               the page.
00548 //
00549 //               It is legal for this method to either evict the page
00550 //               as requested, do nothing (in which case the eviction
00551 //               will be requested again at the next epoch), or
00552 //               requeue itself on the tail of the queue (in which
00553 //               case the eviction will be requested again much
00554 //               later).
00555 ////////////////////////////////////////////////////////////////////
00556 void AdaptiveLruPage::
00557 evict_lru() {
00558   dequeue_lru();
00559 }
00560 
00561 ////////////////////////////////////////////////////////////////////
00562 //     Function: AdaptiveLruPage::output
00563 //       Access: Published, Virtual
00564 //  Description: 
00565 ////////////////////////////////////////////////////////////////////
00566 void AdaptiveLruPage::
00567 output(ostream &out) const {
00568   out << "page " << this << ", " << _lru_size;
00569 }
00570 
00571 ////////////////////////////////////////////////////////////////////
00572 //     Function: AdaptiveLruPage::write
00573 //       Access: Published, Virtual
00574 //  Description: 
00575 ////////////////////////////////////////////////////////////////////
00576 void AdaptiveLruPage::
00577 write(ostream &out, int indent_level) const {
00578   indent(out, indent_level) << *this << "\n";
00579 }
00580 
00581 ////////////////////////////////////////////////////////////////////
00582 //     Function: AdaptiveLruPage::get_num_frames
00583 //       Access: Published
00584 //  Description: Returns the number of frames since the page was first
00585 //               added to its LRU.  Returns 0 if it does not have an
00586 //               LRU.
00587 ////////////////////////////////////////////////////////////////////
00588 unsigned int AdaptiveLruPage::
00589 get_num_frames() const {
00590   if (_lru == (AdaptiveLru *)NULL) {
00591     return 0;
00592   }
00593   return _lru->_current_frame_identifier - _first_frame_identifier;
00594 }
00595 
00596 ////////////////////////////////////////////////////////////////////
00597 //     Function: AdaptiveLruPage::get_num_inactive_frames
00598 //       Access: Published
00599 //  Description: Returns the number of frames since the page was last
00600 //               accessed on its LRU.  Returns 0 if it does not have
00601 //               an LRU.
00602 ////////////////////////////////////////////////////////////////////
00603 unsigned int AdaptiveLruPage::
00604 get_num_inactive_frames() const {
00605   if (_lru == (AdaptiveLru *)NULL) {
00606     return 0;
00607   }
00608   return _lru->_current_frame_identifier - _current_frame_identifier;
00609 }
00610 
00611 
00612 #if 0
00613 
00614 ////////////////////////////////////////////////////////////////////
00615 //     Function: test_adaptive_lru
00616 //       Access:
00617 //  Description: Unit test function for Lru.
00618 ////////////////////////////////////////////////////////////////////
00619 void
00620 test_adaptive_lru() {
00621   int maximum_memory = 3000000;
00622   AdaptiveLru *lru = new AdaptiveLru("test", maximum_memory);
00623 
00624   AdaptiveLruPage *lru_page_0;
00625   AdaptiveLruPage *lru_page_1;
00626   AdaptiveLruPage *lru_page_2;
00627   AdaptiveLruPage *lru_page_3;
00628   AdaptiveLruPage *lru_page_4;
00629   AdaptiveLruPage *lru_page_5;
00630   
00631   lru_page_0 = new AdaptiveLruPage(1000000);
00632   cerr << "created lru_page_0: " << lru_page_0 << "\n";
00633   lru_page_0->enqueue_lru(lru);
00634   
00635   lru_page_1 = new AdaptiveLruPage(1000000);
00636   cerr << "created lru_page_1: " << lru_page_1 << "\n";
00637   lru_page_1->enqueue_lru(lru);
00638   
00639   lru_page_2 = new AdaptiveLruPage(1000000);
00640   cerr << "created lru_page_2: " << lru_page_2 << "\n";
00641   lru_page_2->enqueue_lru(lru);
00642   
00643   lru_page_3 = new AdaptiveLruPage(1000000);
00644   cerr << "created lru_page_3: " << lru_page_3 << "\n";
00645   lru_page_3->enqueue_lru(lru);
00646   
00647   lru_page_4 = new AdaptiveLruPage(1000000);
00648   cerr << "created lru_page_4: " << lru_page_4 << "\n";
00649   lru_page_4->enqueue_lru(lru);
00650   
00651   lru_page_5 = new AdaptiveLruPage(1000000);
00652   cerr << "created lru_page_5: " << lru_page_5 << "\n";
00653   lru_page_5->enqueue_lru(lru);
00654 
00655   int total_frames = 300;
00656   int index;
00657   for (index = 0;  index < total_frames;  index++) {
00658     cerr << "FRAME " << index << "\n";
00659 
00660     lru->begin_epoch();
00661 
00662     if (index <= 5) {
00663       lru_page_0->mark_used_lru(lru);
00664     }
00665 
00666     lru_page_1->mark_used_lru(lru);
00667     lru_page_1->mark_used_lru(lru);
00668     
00669     if (index & 0x01) {
00670       lru_page_2->mark_used_lru(lru);
00671     }
00672 
00673     if ((index % 10) == 0) {
00674       lru_page_3->mark_used_lru(lru);
00675     }
00676 
00677     if (index >= 100) {
00678       lru_page_4->mark_used_lru(lru);
00679     }
00680 
00681     if (index >= 200) {
00682       lru_page_5->mark_used_lru(lru);
00683     }
00684 
00685     if (!lru->validate()) {
00686       cerr << "Failed validation\n";
00687       break;
00688     }
00689   }
00690   
00691   delete lru;
00692   delete lru_page_0;
00693   delete lru_page_1;
00694   delete lru_page_2;
00695   delete lru_page_3;
00696   delete lru_page_4;
00697   delete lru_page_5;
00698 }
00699 
00700 #endif  // test_adaptive_lru
 All Classes Functions Variables Enumerations