Panda3D

lru.cxx

00001 // Filename: lru.cxx
00002 // Created by: aignacio (12Dec05)
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 "stdafx.h"
00016 
00017 #define LRU_UNIT_TEST 0
00018 
00019 #include <stdio.h>
00020 #include <stdlib.h>
00021 //#include <windows.h>
00022 
00023 #include "lru.h"
00024 
00025 
00026 static const int HIGH_PRIORITY_SCALE = 4;
00027 static const int LOW_PRIORITY_RANGE = 25;
00028 
00029 ////////////////////////////////////////////////////////////////////
00030 //     Function: Lru::Constructor
00031 //       Access: Public
00032 //  Description:
00033 ////////////////////////////////////////////////////////////////////
00034 Lru::Lru (int maximum_memory, int maximum_pages, int maximum_page_types)
00035 {
00036   if(this) {
00037     int  index;
00038 
00039     memset(&this->_m, 0, sizeof (LruVariables));
00040 
00041     this->_m.maximum_memory = maximum_memory;
00042     this->_m.maximum_pages  = maximum_pages;
00043     this->_m.maximum_page_types = maximum_page_types;
00044     this->_m.available_memory = maximum_memory;
00045     this->_m.current_frame_identifier = 1;
00046     this->_m.weight = 0.20f;
00047 
00048     this->set_maximum_frame_bandwidth_utilization(2000000.0f);
00049 
00050     for(index = 0; index < MAXIMUM_LRU_PAGE_TYPES; index++) {
00051       this->_m.page_in_function_array[index] = default_page_in_function;
00052       this->_m.page_out_function_array[index] = default_page_out_function;
00053     }
00054 
00055     if(maximum_pages > 0) {
00056       this -> _m.lru_page_pool = new LruPage * [maximum_pages];
00057       this -> _m.lru_page_free_pool = new LruPage * [maximum_pages];
00058       for(index = 0; index < maximum_pages; index++) {
00059         LruPage  * lru_page;
00060 
00061         lru_page = new LruPage ( );
00062         if(lru_page) {
00063           lru_page->_m.v.pre_allocated = true;
00064           this->_m.lru_page_pool[index] = lru_page;
00065         }
00066         else {
00067 // ERROR
00068         }
00069       }
00070     }
00071 
00072     if(maximum_page_types > 0) {
00073       this -> _m.page_type_statistics_array =
00074         new PageTypeStatistics [maximum_page_types];
00075     }
00076 
00077 #if ENABLE_MUTEX
00078     this -> _m.mutex = new Mutex ("lru");
00079 #endif
00080 
00081   }
00082 }
00083 
00084 ////////////////////////////////////////////////////////////////////
00085 //     Function: Lru::Destructor
00086 //       Access: Public
00087 //  Description:
00088 ////////////////////////////////////////////////////////////////////
00089 Lru::~Lru ( )
00090 {
00091   int        index;
00092   LruPage  * lru_page;
00093 
00094   // free pre-allocated LruPages
00095   if(this->_m.maximum_pages > 0) {
00096     if(this->_m.lru_page_free_pool) {
00097       for(index = 0; index < this->_m.maximum_pages; index++) {
00098         lru_page = this->_m.lru_page_pool[index];
00099         if(lru_page->_m.v.in_lru) {
00100           this->remove_page(lru_page);
00101         }
00102 
00103         delete lru_page;
00104       }
00105 
00106       delete this -> _m.lru_page_free_pool;
00107     }
00108     if(this->_m.lru_page_pool) {
00109       delete this -> _m.lru_page_pool;
00110     }
00111   }
00112 
00113   // free dynamically allocated LruPages
00114   for(index = 0; index < LPP_TotalPriorities; index++) {
00115     LruPage  * next_lru_page;
00116 
00117     lru_page = this->_m.lru_page_array[index];
00118     while(lru_page) {
00119       next_lru_page = lru_page->_m.next;
00120 
00121       delete  lru_page;
00122 
00123       lru_page = next_lru_page;
00124     }
00125   }
00126 
00127   if(this->_m.page_type_statistics_array) {
00128     delete this -> _m.page_type_statistics_array;
00129   }
00130 
00131 #if ENABLE_MUTEX
00132   if(this->_m.mutex) {
00133     delete this -> _m.mutex;
00134   }
00135 #endif
00136 
00137 }
00138 
00139 ////////////////////////////////////////////////////////////////////
00140 //     Function: LruPage::Constructor
00141 //       Access: Protected
00142 //  Description: Internal function only.
00143 //               Call  Lru::allocate_page instead.
00144 ////////////////////////////////////////////////////////////////////
00145 LruPage::LruPage ( )
00146 {
00147   if(this) {
00148     memset(&this->_m, 0, sizeof (LruPageVariables));
00149     _m.name = "";   
00150   }
00151 }
00152 
00153 ////////////////////////////////////////////////////////////////////
00154 //     Function: LruPage::Destructor
00155 //       Access: Protected
00156 //  Description: Internal function only.
00157 //               Call  Lru::free_page instead.
00158 ////////////////////////////////////////////////////////////////////
00159 LruPage::~LruPage ( )
00160 {
00161 
00162 }
00163 
00164 ////////////////////////////////////////////////////////////////////
00165 //     Function: LruPage::change_priority
00166 //       Access: Protected
00167 //  Description:
00168 ////////////////////////////////////////////////////////////////////
00169 void LruPage::change_priority (int delta)
00170 {
00171   this->_m.priority_change += delta;
00172 }
00173 
00174 ////////////////////////////////////////////////////////////////////
00175 //     Function: Lru::register_lru_page_type
00176 //       Access: Public
00177 //  Description: Registers a specific type of page and its
00178 //               required page in and out functions.
00179 ////////////////////////////////////////////////////////////////////
00180 bool Lru::register_lru_page_type (int index,
00181   LruPageTypeFunction page_in_function,
00182   LruPageTypeFunction page_out_function)
00183 {
00184   bool  state;
00185 
00186   state = false;
00187   if(index >= 0 && index < MAXIMUM_LRU_PAGE_TYPES) {
00188     this->_m.page_in_function_array[index] = page_in_function;
00189     this->_m.page_out_function_array[index] = page_out_function;
00190     state = true;
00191   }
00192 
00193   return state;
00194 }
00195 
00196 ////////////////////////////////////////////////////////////////////
00197 //     Function: Lru::allocate_page
00198 //       Access: Public
00199 //  Description:
00200 ////////////////////////////////////////////////////////////////////
00201 LruPage *Lru::allocate_page (int size)
00202 {
00203   LruPage  * lru_page;
00204 
00205   lru_page = 0;
00206   if(size <= this->_m.maximum_memory) {
00207     if(this->_m.maximum_pages) {
00208       if(this->_m.total_lru_pages_in_free_pool > 0) {
00209         lru_page =
00210           this->_m.lru_page_free_pool [this->_m.total_lru_pages_in_free_pool - 1];
00211         this->_m.total_lru_pages_in_free_pool--;
00212 
00213         memset (&lru_page -> _m, 0, sizeof (LruPage::LruPageVariables));
00214         lru_page->_m.v.pre_allocated = true;
00215       }
00216       else {
00217         if(this->_m.total_lru_pages_in_pool < this->_m.maximum_pages) {
00218           lru_page = this->_m.lru_page_pool[this->_m.total_lru_pages_in_pool];
00219           this->_m.total_lru_pages_in_pool++;
00220         }
00221         else {
00222           // out of pre-allocated LruPages so dynamically allocate a page
00223           lru_page = new LruPage ( );
00224         }
00225       }
00226     }
00227     else {
00228       lru_page = new LruPage;
00229     }
00230     if(lru_page) {
00231       lru_page->_m.lru = this;
00232       lru_page->_m.size = size;
00233       lru_page->_m.first_frame_identifier = this->_m.current_frame_identifier;
00234       lru_page->_m.last_frame_identifier = this->_m.current_frame_identifier;
00235 
00236       lru_page->_m.v.allocated = true;
00237       lru_page->_m.identifier = this->_m.identifier;
00238 
00239       lru_page->_m.average_frame_utilization = 1.0f;
00240 
00241       this->_m.total_pages++;
00242       this->_m.identifier++;
00243     }
00244     else {
00245 
00246 // ERROR: could not allocate LruPage
00247 
00248     }
00249   }
00250   else {
00251 
00252 // ERROR: requested page size is larger than maximum memory size
00253 
00254   }
00255 
00256   return lru_page;
00257 }
00258 
00259 ////////////////////////////////////////////////////////////////////
00260 //     Function: Lru::update_start_update_lru_page
00261 //       Access: Public
00262 //  Description:
00263 ////////////////////////////////////////////////////////////////////
00264 void Lru::update_start_update_lru_page (LruPage *lru_page)
00265 {
00266   if(lru_page) {
00267     if(this->_m.start_update_lru_page == lru_page) {
00268       if(lru_page->_m.next) {
00269         this->_m.start_update_lru_page = lru_page->_m.next;
00270       }
00271       else {
00272         if((this->_m.start_priority_index + 1) >= LPP_TotalPriorities) {
00273           this->_m.start_priority_index = 0;
00274         }
00275         else {
00276           this->_m.start_priority_index = this->_m.start_priority_index + 1;
00277         }
00278 
00279         this->_m.start_update_lru_page = 0;
00280       }
00281     }
00282   }
00283 }
00284 
00285 ////////////////////////////////////////////////////////////////////
00286 //     Function: Lru::free_page
00287 //       Access: Public
00288 //  Description:
00289 ////////////////////////////////////////////////////////////////////
00290 void Lru::free_page (LruPage *lru_page)
00291 {
00292   if(this->_m.total_pages > 0) {
00293     if(lru_page) {
00294       LruMutexHolder(this->_m.mutex);
00295 
00296       this->update_start_update_lru_page(lru_page);
00297 
00298       if(lru_page->_m.v.in_cache) {
00299         this->_m.available_memory += lru_page->_m.size;
00300       }
00301 
00302       if(lru_page->_m.v.pre_allocated) {
00303         if(this->_m.maximum_pages) {
00304           lru_page->_m.v.allocated = false;
00305           this->_m.lru_page_free_pool [this->_m.total_lru_pages_in_free_pool] =
00306             lru_page;
00307           this->_m.total_lru_pages_in_free_pool++;
00308         }
00309         else {
00310 // ERROR: this case should not happen
00311         }
00312       }
00313       else {
00314         delete lru_page;
00315       }
00316 
00317       this->_m.total_pages--;
00318     }
00319   }
00320   else {
00321 
00322 // ERROR: tried to free a page when 0 pages allocated
00323 
00324   }
00325 }
00326 
00327 ////////////////////////////////////////////////////////////////////
00328 //     Function: Lru::add_page
00329 //       Access: Public
00330 //  Description: Adds a page to the LRU based on the given priority.
00331 ////////////////////////////////////////////////////////////////////
00332 void Lru::add_page (LruPagePriority priority, LruPage *lru_page)
00333 {
00334   if(lru_page) {
00335     LruMutexHolder(this->_m.mutex);
00336 
00337     LruPage * first_lru_page;
00338 
00339     lru_page->_m.priority = priority;
00340 
00341     first_lru_page = this->_m.lru_page_array[lru_page->_m.priority];
00342     if(first_lru_page) {
00343       first_lru_page->_m.previous = lru_page;
00344       lru_page->_m.next = first_lru_page;
00345     }
00346 
00347     this->_m.lru_page_array[lru_page->_m.priority] = lru_page;
00348 
00349     lru_page->_m.v.in_lru = true;
00350   }
00351 }
00352 
00353 ////////////////////////////////////////////////////////////////////
00354 //     Function: Lru::add_cached_page
00355 //       Access: Public
00356 //  Description: Adds a page that is already paged in to the LRU
00357 //               based on the given priority.
00358 ////////////////////////////////////////////////////////////////////
00359 void Lru::add_cached_page (LruPagePriority priority, LruPage *lru_page)
00360 {
00361   if(lru_page) {
00362     LruMutexHolder(this->_m.mutex);
00363 
00364     lru_page->_m.v.in_cache = true;
00365 
00366     if(lru_page->_m.size > this->_m.available_memory) {
00367       int  memory_required;
00368 
00369       memory_required = lru_page->_m.size - this->_m.available_memory;
00370 
00371       // unload page(s)
00372       this->page_out_lru(memory_required);
00373     }
00374 
00375     this->_m.available_memory -= lru_page->_m.size;
00376 
00377     this->add_page(priority, lru_page);
00378   }
00379 }
00380 
00381 ////////////////////////////////////////////////////////////////////
00382 //     Function: Lru::remove_page
00383 //       Access: Public
00384 //  Description: Removes a page from the LRU.
00385 ////////////////////////////////////////////////////////////////////
00386 void Lru::remove_page (LruPage *lru_page)
00387 {
00388   if(this) {
00389     if(this->_m.total_pages > 0) {
00390       if(lru_page) {
00391         LruMutexHolder(this->_m.mutex);
00392 
00393         this->update_start_update_lru_page(lru_page);
00394 
00395         if(lru_page->_m.previous) {
00396           lru_page->_m.previous->_m.next = lru_page->_m.next;
00397           if(lru_page->_m.next) {
00398             lru_page->_m.next->_m.previous = lru_page->_m.previous;
00399           }
00400         }
00401         else {
00402           this->_m.lru_page_array[lru_page->_m.priority] =
00403             lru_page->_m.next;
00404           if(lru_page->_m.next) {
00405             lru_page->_m.next->_m.previous = 0;
00406           }
00407         }
00408 
00409         lru_page->_m.next = 0;
00410         lru_page->_m.previous = 0;
00411 
00412         lru_page->_m.v.in_lru = false;
00413       }
00414     }
00415     else {
00416 
00417 // ERROR: tried to remove a page when 0 pages are allocated
00418 
00419     }
00420   }
00421   else {
00422 
00423 // ERROR: Lru == 0, this should not happen
00424 
00425   }
00426 }
00427 
00428 ////////////////////////////////////////////////////////////////////
00429 //     Function: Lru::lock_page
00430 //       Access: Public
00431 //  Description:
00432 ////////////////////////////////////////////////////////////////////
00433 void Lru::lock_page (LruPage *lru_page)
00434 {
00435   lru_page->_m.v.lock = true;
00436 }
00437 
00438 ////////////////////////////////////////////////////////////////////
00439 //     Function: Lru::unlock_page
00440 //       Access: Public
00441 //  Description:
00442 ////////////////////////////////////////////////////////////////////
00443 void Lru::unlock_page (LruPage *lru_page)
00444 {
00445   lru_page->_m.v.lock = false;
00446 }
00447 
00448 ////////////////////////////////////////////////////////////////////
00449 //     Function: Lru::access_page
00450 //       Access: Public
00451 //  Description: This must always be called before accessing or
00452 //               using a page's memory since it pages in the page
00453 //               if it is currently paged out.
00454 ////////////////////////////////////////////////////////////////////
00455 void Lru::access_page (LruPage *lru_page)
00456 {
00457   if(lru_page) {
00458     if(lru_page->_m.current_frame_identifier
00459        == this->_m.current_frame_identifier) {
00460       lru_page->_m.current_frame_usage++;
00461       this->_m.total_page_all_access_size += lru_page->_m.size;
00462     }
00463     else {
00464       // first update this frame
00465       lru_page->_m.last_frame_identifier = lru_page->_m.current_frame_identifier;
00466       lru_page->_m.current_frame_identifier = this->_m.current_frame_identifier;
00467       lru_page->_m.last_frame_usage = lru_page->_m.current_frame_usage;
00468       lru_page->_m.current_frame_usage = 1;
00469       lru_page->_m.total_frame_page_faults = 0;
00470 
00471       this->_m.total_page_access_size += lru_page->_m.size;
00472     }
00473 
00474     // check if the page is out
00475     if(lru_page->_m.v.in_cache == false) {
00476       bool  state;
00477 
00478       state = true;
00479 
00480       LruMutexHolder(this->_m.mutex);
00481 
00482       // check memory usage
00483       if(lru_page->_m.size > this->_m.available_memory) {
00484         int  memory_required;
00485 
00486         memory_required = lru_page->_m.size - this->_m.available_memory;
00487 
00488         // unload page(s)
00489         state = this->page_out_lru(memory_required);
00490       }
00491 
00492       // load the page in
00493       if(state) {
00494         // PAGE IN CALLBACK
00495         if(this->_m.page_in_function_array[lru_page->_m.v.type](lru_page)) {
00496           this->_m.available_memory -= lru_page->_m.size;
00497           lru_page->_m.v.in_cache = true;
00498 
00499           // CHANGE THE PAGE PRIORITY FROM LPP_PageOut TO LPP_New
00500           this->remove_page(lru_page);
00501           this->add_page(LPP_New, lru_page);
00502 
00503           this->_m.total_lifetime_page_ins++;
00504         }
00505       }
00506 
00507       lru_page->_m.total_frame_page_faults++;
00508       lru_page->_m.total_page_faults++;
00509     }
00510 
00511     lru_page->_m.total_usage++;
00512     lru_page->_m.update_total_usage++;
00513 
00514     this->_m.total_page_access++;
00515   }
00516 }
00517 
00518 ////////////////////////////////////////////////////////////////////
00519 //     Function: Lru::set_maximum_frame_bandwidth_utilization
00520 //       Access: Public
00521 //  Description:
00522 ////////////////////////////////////////////////////////////////////
00523 void Lru::set_maximum_frame_bandwidth_utilization
00524   (PN_stdfloat maximum_frame_bandwidth_utilization)
00525 {
00526   this->_m.maximum_frame_bandwidth_utilization =
00527     maximum_frame_bandwidth_utilization;
00528 
00529   this->_m.frame_bandwidth_factor = (PN_stdfloat) LPP_TotalPriorities
00530     / this->_m.maximum_frame_bandwidth_utilization;
00531 }
00532 
00533 ////////////////////////////////////////////////////////////////////
00534 //     Function: Lru::begin_frame
00535 //       Access: Public
00536 //  Description: This must be called before each frame.
00537 ////////////////////////////////////////////////////////////////////
00538 void Lru::begin_frame ( )
00539 {
00540   this->_m.current_frame_identifier++;
00541 
00542   this->_m.total_page_ins_last_frame = this->_m.total_page_ins;
00543   this->_m.total_page_outs = this->_m.total_page_outs;
00544 
00545   this->_m.total_page_ins = 0;
00546   this->_m.total_page_outs = 0;
00547 }
00548 
00549 ////////////////////////////////////////////////////////////////////
00550 //     Function: Lru::update_page_priorities
00551 //       Access: Public
00552 //  Description: This updates the priority of a page that has a
00553 //               change in priority.
00554 ////////////////////////////////////////////////////////////////////
00555 void Lru::update_page_priorities (void)
00556 {
00557   int index;
00558   LruPage *lru_page;
00559 
00560   for(index = 0; index < this->_m.total_lru_page_priority_changes; index++) {
00561     int priority;
00562 
00563     lru_page = this->_m.lru_page_priority_change_array[index];
00564 
00565     this->remove_page(lru_page);
00566 
00567     priority = (( int ) lru_page->_m.priority + lru_page->_m.priority_change);
00568     if(priority < 0) {
00569       priority = 0;
00570     }
00571     if(priority >= LPP_TotalPriorities) {
00572       priority = LPP_TotalPriorities - 1;
00573     }
00574 
00575     this->add_page((LruPagePriority) priority, lru_page);
00576     lru_page->_m.priority_change = 0;
00577   }
00578   this->_m.total_lru_page_priority_changes = 0;
00579 }
00580 
00581 ////////////////////////////////////////////////////////////////////
00582 //     Function: Lru::update_lru_page
00583 //       Access: Public
00584 //  Description: This updates the page's average utilization.
00585 //               Priority LPP_New is considered to be average usage
00586 //               of 1.0 (which means the page is used once per frame
00587 //               on average).  Priorities < LPP_New are for pages
00588 //               used more than once per frame and Priorities >
00589 //               LPP_New are for pages used less than once per frame.
00590 //               If there was a change in priority, then adds it to
00591 //               the array of lru pages with changed priorities
00592 //               which will be updated later.
00593 ////////////////////////////////////////////////////////////////////
00594 void Lru::update_lru_page (LruPage *lru_page)
00595 {
00596 
00597 #if LRU_UNIT_TEST
00598   if(false) {
00599     char  string[256];
00600 
00601     sprintf(string, "  UPDATE %d\n", lru_page->_m.identifier);
00602     OutputDebugString(string);
00603   }
00604 #endif
00605 
00606   if(lru_page->_m.v.lock == false && lru_page->_m.v.in_cache) {
00607     int delta_priority;
00608     int lifetime_frames;
00609 
00610     delta_priority = 0;
00611 
00612     lifetime_frames = this->_m.current_frame_identifier -
00613       lru_page->_m.first_frame_identifier;
00614     if(lifetime_frames >= 1) {
00615       if(lru_page->_m.update_frame_identifier) {
00616         int target_priority;
00617         int integer_update_frames;
00618         PN_stdfloat update_frames;
00619         PN_stdfloat one_over_update_frames;
00620         PN_stdfloat update_average_frame_utilization;
00621 
00622         integer_update_frames = (this->_m.current_frame_identifier -
00623           lru_page->_m.update_frame_identifier);
00624         if(integer_update_frames > 0) {
00625           update_frames = ( PN_stdfloat ) integer_update_frames;
00626           one_over_update_frames = 1.0f / update_frames;
00627 
00628           update_average_frame_utilization =
00629             (PN_stdfloat) (lru_page->_m.update_total_usage)* one_over_update_frames;
00630 
00631           lru_page->_m.average_frame_utilization =
00632             calculate_exponential_moving_average(
00633                update_average_frame_utilization, this->_m.weight,
00634                lru_page->_m.average_frame_utilization);
00635 
00636           target_priority = lru_page->_m.priority;
00637           if(lru_page->_m.average_frame_utilization >= 1.0f) {
00638             int integer_average_frame_utilization;
00639 
00640             integer_average_frame_utilization =
00641               (int) ((lru_page->_m.average_frame_utilization - 1.0f) *
00642               (PN_stdfloat) HIGH_PRIORITY_SCALE);
00643             if(integer_average_frame_utilization >= LPP_New) {
00644               integer_average_frame_utilization = LPP_New;
00645             }
00646             integer_average_frame_utilization = LPP_New -
00647               integer_average_frame_utilization;
00648             target_priority = integer_average_frame_utilization;
00649           }
00650           else {
00651             int integer_average_frame_utilization;
00652 
00653             integer_average_frame_utilization = (int)
00654                (lru_page->_m.average_frame_utilization *
00655                (PN_stdfloat) LOW_PRIORITY_RANGE);
00656             integer_average_frame_utilization = LOW_PRIORITY_RANGE -
00657               integer_average_frame_utilization;
00658             target_priority = LPP_New + integer_average_frame_utilization;
00659           }
00660 
00661           delta_priority = target_priority - lru_page->_m.priority;
00662           lru_page->change_priority(delta_priority);
00663         }
00664       }
00665 
00666       lru_page->_m.update_frame_identifier = this->_m.current_frame_identifier;
00667       lru_page->_m.update_total_usage = 0;
00668     }
00669 
00670     if(lru_page->_m.priority_change) {
00671       if(this->_m.total_lru_page_priority_changes
00672          < FRAME_MAXIMUM_PRIORITY_CHANGES)
00673       {
00674         this->_m.lru_page_priority_change_array
00675           [this->_m.total_lru_page_priority_changes] = lru_page;
00676         this->_m.total_lru_page_priority_changes++;
00677       }
00678     }
00679   }
00680 }
00681 
00682 ////////////////////////////////////////////////////////////////////
00683 //     Function: Lru::update_lru_page_old
00684 //       Access: Public
00685 //  Description: This updates the page's average utilization and
00686 //               adds it to the array of pages with changed
00687 //               priorities if there was a change in priority.
00688 //               Old method.
00689 ////////////////////////////////////////////////////////////////////
00690 void Lru::update_lru_page_old (LruPage *lru_page)
00691 {
00692 }
00693 
00694 ////////////////////////////////////////////////////////////////////
00695 //     Function: Lru::update_entire_lru
00696 //       Access: Public
00697 //  Description: This updates all the pages in the Lru.
00698 //               Lru::partial_lru_update should be called instead
00699 //               due to performance reasons.
00700 ////////////////////////////////////////////////////////////////////
00701 void Lru::update_entire_lru ( )
00702 {
00703   if(this->_m.total_pages > 0) {
00704     int index;
00705     LruPage *lru_page;
00706 
00707     LruMutexHolder(this->_m.mutex);
00708 
00709     for(index = 0; index < LPP_TotalPriorities; index++) {
00710 
00711       LruPage  * next_lru_page;
00712 
00713       lru_page = this->_m.lru_page_array[index];
00714       while(lru_page) {
00715         next_lru_page = lru_page->_m.next;
00716 
00717         this->update_lru_page(lru_page);
00718 
00719         lru_page = next_lru_page;
00720       }
00721     }
00722 
00723     this->update_page_priorities( );
00724   }
00725 }
00726 
00727 ////////////////////////////////////////////////////////////////////
00728 //     Function: Lru::partial_lru_update
00729 //       Access: Public
00730 //  Description: This only updates a number of pages up to the
00731 //               specified maximum_updates.
00732 ////////////////////////////////////////////////////////////////////
00733 void Lru::partial_lru_update (int maximum_updates)
00734 {
00735   int total_page_updates;
00736 
00737   if (maximum_updates <= 0) {
00738     // enforce a minimum number of updates
00739     maximum_updates = 1;
00740   }
00741 
00742   total_page_updates = 0;
00743   if(this->_m.total_pages > 0) {
00744     int index;
00745     int start_priority;
00746     LruPage *lru_page;
00747 
00748     LruMutexHolder(this->_m.mutex);
00749 
00750     start_priority = this->_m.start_priority_index;
00751 
00752     {
00753       for(index = start_priority;  index < LPP_TotalPriorities; index++) {
00754 
00755         LruPage *next_lru_page;
00756 
00757         if(index == start_priority) {
00758           if(this->_m.start_update_lru_page) {
00759             lru_page = this->_m.start_update_lru_page;
00760           }
00761           else {
00762             lru_page = this->_m.lru_page_array[index];
00763           }
00764         }
00765         else {
00766           lru_page = this->_m.lru_page_array[index];
00767         }
00768         while(lru_page) {
00769           next_lru_page = lru_page->_m.next;
00770 
00771           this->update_lru_page(lru_page);
00772 
00773           total_page_updates++;
00774           if(total_page_updates >= maximum_updates) {
00775             if(next_lru_page) {
00776               this->_m.start_priority_index = index;
00777               this->_m.start_update_lru_page = next_lru_page;
00778             }
00779             else {
00780               if((index + 1) >= LPP_TotalPriorities) {
00781                 this->_m.start_priority_index = 0;
00782               }
00783               else {
00784                 this->_m.start_priority_index = index + 1;
00785               }
00786 
00787               this->_m.start_update_lru_page = 0;
00788             }
00789 
00790             break;
00791           }
00792 
00793           lru_page = next_lru_page;
00794         }
00795 
00796         if(total_page_updates >= maximum_updates) {
00797           break;
00798         }
00799       }
00800     }
00801 
00802     if(total_page_updates < maximum_updates) {
00803       for(index = 0;  index <= start_priority;  index++) {
00804         LruPage *next_lru_page;
00805 
00806         lru_page = this->_m.lru_page_array[index];
00807         while(lru_page) {
00808           next_lru_page = lru_page->_m.next;
00809 
00810           this->update_lru_page(lru_page);
00811 
00812           total_page_updates++;
00813           if(total_page_updates >= maximum_updates) {
00814             if(next_lru_page) {
00815               this->_m.start_priority_index = index;
00816               this->_m.start_update_lru_page = next_lru_page;
00817             }
00818             else {
00819               if((index + 1) >= LPP_TotalPriorities) {
00820                 this->_m.start_priority_index = 0;
00821               }
00822               else {
00823                 this->_m.start_priority_index = index + 1;
00824               }
00825 
00826               this->_m.start_update_lru_page = 0;
00827             }
00828 
00829             break;
00830           }
00831 
00832           lru_page = next_lru_page;
00833         }
00834 
00835         if(total_page_updates >= maximum_updates) {
00836           break;
00837         }
00838       }
00839     }
00840 
00841     if(total_page_updates < maximum_updates) {
00842       this->_m.start_priority_index  = 0;
00843       this->_m.start_update_lru_page = 0;
00844     }
00845 
00846     this->update_page_priorities( );
00847   }
00848 }
00849 
00850 ////////////////////////////////////////////////////////////////////
00851 //     Function: Lru::unlock_all_pages
00852 //       Access: Public
00853 //  Description:
00854 ////////////////////////////////////////////////////////////////////
00855 void Lru::unlock_all_pages (void)
00856 {
00857   if(this->_m.total_pages > 0) {
00858     int  index;
00859 
00860     for(index = 0;  index < LPP_TotalPriorities; index++) {
00861       LruPage *lru_page;
00862       LruPage *next_lru_page;
00863 
00864       lru_page = this->_m.lru_page_array[index];
00865       while(lru_page) {
00866         next_lru_page = lru_page->_m.next;
00867 
00868         lru_page->_m.v.lock = false;
00869 
00870         lru_page = next_lru_page;
00871       }
00872     }
00873   }
00874 }
00875 
00876 ////////////////////////////////////////////////////////////////////
00877 //     Function: Lru::page_out_lru
00878 //       Access: Public
00879 //  Description: Pages out the lowest priority pages until the
00880 //               memory_required is satisfied.  This will unlock
00881 //               all pages if needed.
00882 ////////////////////////////////////////////////////////////////////
00883 bool Lru::page_out_lru (int memory_required)
00884 {
00885   bool state;
00886   int attempts;
00887 
00888   state = false;
00889   attempts = 0;
00890   if(this->_m.total_pages > 0) {
00891     LruMutexHolder(this->_m.mutex);
00892 
00893     do {
00894       int index;
00895       int minimum_frame_identifier;
00896       
00897       minimum_frame_identifier = this->_m.current_frame_identifier - 1;
00898 
00899       // page out lower priority pages first
00900       for(index = LPP_PageOut - 1; index >= 0; index--) {
00901         LruPage *lru_page;
00902         LruPage *next_lru_page;
00903 
00904         lru_page = this->_m.lru_page_array[index];
00905         while(lru_page) {
00906           next_lru_page = lru_page->_m.next;
00907 
00908           if(attempts == 0 && (lru_page->_m.current_frame_identifier >= minimum_frame_identifier)) {
00909             // avoid swapping out pages used in the current and last frame on the first attempt
00910           }
00911           else {
00912             if(lru_page->_m.v.lock == false && lru_page->_m.v.in_cache) {
00913               memory_required -= lru_page->_m.size;
00914               this->_m.available_memory += lru_page->_m.size;
00915               lru_page->_m.v.in_cache = false;
00916 
00917               // PAGE OUT CALLBACK
00918               this->_m.page_out_function_array[lru_page->_m.v.type](lru_page);
00919               this->_m.total_lifetime_page_outs++;
00920 
00921               // MOVE THE PAGE TO THE LPP_PageOut PRIORITY
00922               this->remove_page(lru_page);
00923               this->add_page(LPP_PageOut, lru_page);
00924 
00925               if(memory_required <= 0) {
00926                 break;
00927               }
00928             }
00929           }
00930           
00931           lru_page = next_lru_page;
00932         }
00933 
00934         if(memory_required <= 0) {
00935           break;
00936         }
00937       }
00938 
00939       if(memory_required > 0) {
00940         state = false;
00941       }
00942       else {
00943         state = true;
00944       }
00945 
00946       attempts++;
00947     } while(state == false && attempts < 2);
00948   }
00949 
00950   return state;
00951 }
00952 
00953 ////////////////////////////////////////////////////////////////////
00954 //     Function: Lru::count_priority_level_pages
00955 //       Access: Public
00956 //  Description: Debug function. Counts the number of pages for each
00957 //               priority level.
00958 ////////////////////////////////////////////////////////////////////
00959 void Lru::count_priority_level_pages (void)
00960 {
00961   int  index;
00962 
00963   LruMutexHolder(this->_m.mutex);
00964 
00965   for(index = 0; index < LPP_TotalPriorities; index++) {
00966     int total_pages;
00967     LruPage *lru_page;
00968     LruPage *next_lru_page;
00969 
00970     total_pages = 0;
00971     lru_page = this->_m.lru_page_array[index];
00972     while(lru_page) {
00973       next_lru_page = lru_page->_m.next;
00974 
00975       total_pages++;
00976 
00977       lru_page = next_lru_page;
00978     }
00979 
00980     this->_m.lru_page_count_array[index] = total_pages;
00981   }
00982 }
00983 
00984 ////////////////////////////////////////////////////////////////////
00985 //     Function: Lru::calculate_lru_statistics
00986 //       Access: Public
00987 //  Description: Debug function.
00988 ////////////////////////////////////////////////////////////////////
00989 void Lru::calculate_lru_statistics (void)
00990 {
00991   LruMutexHolder(this->_m.mutex);
00992 
00993   if(this->_m.maximum_page_types > 0) {
00994     int  index;
00995 
00996     memset(this->_m.page_type_statistics_array, 0,
00997            sizeof (PageTypeStatistics) * this->_m.maximum_page_types);
00998     for(index = 0;  index < LPP_TotalPriorities;  index++) {
00999       LruPage *lru_page;
01000       LruPage *next_lru_page;
01001       PageTypeStatistics *page_type_statistics;
01002 
01003       lru_page = this->_m.lru_page_array[index];
01004       while(lru_page) {
01005         int  type;
01006 
01007         next_lru_page = lru_page->_m.next;
01008 
01009         type = lru_page->_m.v.type;
01010         page_type_statistics = &this->_m.page_type_statistics_array[type];
01011         page_type_statistics->total_pages++;
01012 
01013         if(lru_page->_m.v.in_cache) {
01014           page_type_statistics->total_pages_in++;
01015           page_type_statistics->total_memory_in += lru_page->_m.size;
01016         }
01017         else {
01018           page_type_statistics->total_pages_out++;
01019           page_type_statistics->total_memory_out += lru_page->_m.size;
01020         }
01021 
01022         lru_page = next_lru_page;
01023       }
01024     }
01025   }
01026 }
01027 
01028 ////////////////////////////////////////////////////////////////////
01029 //     Function: calculate_exponential_moving_average
01030 //       Access: Public
01031 //  Description:
01032 ////////////////////////////////////////////////////////////////////
01033 PN_stdfloat calculate_exponential_moving_average(PN_stdfloat value,
01034   PN_stdfloat weight, PN_stdfloat average)
01035 {
01036   return ((value - average) * weight) + average;
01037 }
01038 
01039 ////////////////////////////////////////////////////////////////////
01040 //     Function: default_page_in_function
01041 //       Access: Public
01042 //  Description:
01043 ////////////////////////////////////////////////////////////////////
01044 bool default_page_in_function(LruPage *lru_page)
01045 {
01046 
01047 #if LRU_UNIT_TEST
01048   char  string[256];
01049 
01050   sprintf(string, "  PAGE IN %d\n", lru_page->_m.identifier);
01051   OutputDebugString(string);
01052 #endif
01053 
01054   return true;
01055 }
01056 
01057 ////////////////////////////////////////////////////////////////////
01058 //     Function: default_page_out_function
01059 //       Access: Public
01060 //  Description:
01061 ////////////////////////////////////////////////////////////////////
01062 bool default_page_out_function(LruPage *lru_page)
01063 {
01064 
01065 #if LRU_UNIT_TEST
01066   char  string[256];
01067 
01068   sprintf(string, "  PAGE OUT %d\n", lru_page->_m.identifier);
01069   OutputDebugString(string);
01070 #endif
01071 
01072   return true;
01073 }
01074 
01075 #if LRU_UNIT_TEST
01076 
01077 ////////////////////////////////////////////////////////////////////
01078 //     Function: test_ema
01079 //       Access:
01080 //  Description: Unit test function for ema.
01081 ////////////////////////////////////////////////////////////////////
01082 void test_ema(void)
01083 {
01084   int    index;
01085   PN_stdfloat  usage;
01086   PN_stdfloat  weight;
01087   PN_stdfloat  average;
01088 
01089   weight  = 0.2;
01090   average = 1.0f;
01091   for(index = 0; index < 50; index++) {
01092     if(index < 25) {
01093       usage = (PN_stdfloat) (index & 0x01);
01094     }
01095     else {
01096       usage = 0.0f;
01097     }
01098     average =
01099       calculate_exponential_moving_average(usage, weight, average);
01100 
01101     char  string[256];
01102     sprintf(string, "%d  %f\n", index, average);
01103     OutputDebugString(string);
01104   }
01105 }
01106 
01107 ////////////////////////////////////////////////////////////////////
01108 //     Function: test_lru
01109 //       Access:
01110 //  Description: Unit test function for Lru.
01111 ////////////////////////////////////////////////////////////////////
01112 void test_lru(void)
01113 {
01114   int maximum_memory;
01115   int maximum_pages;
01116   int maximum_page_types;
01117   Lru *lru;
01118 
01119   test_ema( );
01120 
01121   maximum_memory = 3000000;
01122   maximum_pages = 3;
01123   maximum_page_types = 4;
01124   lru = new Lru (maximum_memory, maximum_pages, maximum_page_types);
01125   if(lru) {
01126     lru->_m.minimum_memory = 1000000;
01127 
01128     LruPage *lru_page_0;
01129     LruPage *lru_page_1;
01130     LruPage *lru_page_2;
01131     LruPage *lru_page_3;
01132     LruPage *lru_page_4;
01133     LruPage *lru_page_5;
01134 
01135     lru_page_0 = lru->allocate_page(1000000);
01136     if(lru_page_0) {
01137       lru->add_page(LPP_PageOut, lru_page_0);
01138     }
01139 
01140     lru_page_1 = lru->allocate_page(1000000);
01141     if(lru_page_1) {
01142       lru->add_page(LPP_PageOut, lru_page_1);
01143     }
01144 
01145     lru_page_2 = lru->allocate_page(1000000);
01146     if(lru_page_2) {
01147       lru->add_page(LPP_PageOut, lru_page_2);
01148     }
01149 
01150     lru_page_3 = lru->allocate_page(1000000);
01151     if(lru_page_3) {
01152       lru->add_page(LPP_PageOut, lru_page_3);
01153     }
01154 
01155     lru_page_4 = lru->allocate_page(1000000);
01156     if(lru_page_4) {
01157       lru->add_page(LPP_PageOut, lru_page_4);
01158     }
01159 
01160     lru_page_5 = lru->allocate_page(1000000);
01161     if(lru_page_5) {
01162       lru->add_page(LPP_PageOut, lru_page_5);
01163     }
01164 
01165     int index;
01166     int total_frames;
01167 
01168     total_frames = 300;
01169     for(index = 0;  index < total_frames;  index++) {
01170       char  string[256];
01171 
01172       sprintf(string, "FRAME %d\n", index);
01173       OutputDebugString(string);
01174 
01175       lru->begin_frame( );
01176 
01177       if(index <= 5) {
01178         lru->access_page(lru_page_0);
01179       }
01180 
01181       lru->access_page(lru_page_1);
01182       lru->access_page(lru_page_1);
01183 
01184       if(index & 0x01) {
01185         lru->access_page(lru_page_2);
01186       }
01187 
01188       if((index % 10) == 0) {
01189         lru->access_page(lru_page_3);
01190       }
01191 
01192       if(index >= 100) {
01193         lru->access_page(lru_page_4);
01194       }
01195 
01196       if(index >= 200) {
01197         lru->access_page(lru_page_5);
01198       }
01199 
01200       if(false) {
01201         lru->update_entire_lru( );
01202       }
01203       else {
01204         int  maximum_updates;
01205 
01206         maximum_updates = 3;
01207         lru->partial_lru_update(maximum_updates);
01208       }
01209     }
01210 
01211     if(!true) {
01212       lru->remove_page(lru_page_2);
01213       lru->free_page(lru_page_2);
01214 
01215       lru->remove_page(lru_page_3);
01216       lru->free_page(lru_page_3);
01217 
01218       lru->remove_page(lru_page_1);
01219       lru->free_page(lru_page_1);
01220     }
01221 
01222     delete lru;
01223   }
01224 }
01225 
01226 #endif
 All Classes Functions Variables Enumerations