Panda3D
|
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