00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
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
00025
00026
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
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
00052
00053
00054
00055 AdaptiveLru::
00056 ~AdaptiveLru() {
00057 #ifndef NDEBUG
00058
00059
00060
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
00075
00076
00077
00078
00079 void AdaptiveLru::
00080 do_partial_lru_update(int num_updates) {
00081
00082
00083
00084
00085
00086 AdaptiveLruPageStaticList *start_node = (AdaptiveLruPageStaticList *)_static_list._next;
00087 if (start_node == &_static_list) {
00088
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
00108
00109
00110
00111
00112
00113
00114
00115
00116
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
00174
00175
00176
00177
00178
00179
00180
00181 void AdaptiveLruPage::
00182 enqueue_lru(AdaptiveLru *lru) {
00183 if (lru != _lru && _lru != (AdaptiveLru *)NULL) {
00184
00185 _lru->do_remove_page(this);
00186 _lru = NULL;
00187 }
00188
00189 if (lru == _lru) {
00190 if (_lru != (AdaptiveLru *)NULL) {
00191
00192 _lru->do_access_page(this);
00193 }
00194 } else {
00195 nassertv(lru != (AdaptiveLru *)NULL);
00196
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
00208
00209
00210
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
00230
00231
00232
00233
00234
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
00249
00250
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
00261
00262
00263
00264 void AdaptiveLru::
00265 write(ostream &out, int indent_level) const {
00266 indent(out, indent_level) << *this << ":\n";
00267
00268
00269
00270
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
00300
00301
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
00315
00316
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
00330
00331
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
00340
00341 ++(page->_current_frame_usage);
00342
00343 } else {
00344
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
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
00359
00360
00361
00362
00363
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
00372 int index;
00373 for (index = LPP_TotalPriorities - 1; index >= 0; index--) {
00374
00375
00376
00377
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
00389
00390
00391 } else {
00392
00393 _lock.release();
00394 page->evict_lru();
00395 _lock.acquire();
00396
00397 if (_total_size <= target_size) {
00398
00399 return;
00400 }
00401 }
00402 if (node == end) {
00403
00404
00405 break;
00406 }
00407 node = next;
00408 }
00409 }
00410 attempts++;
00411 } while (hard_evict && attempts < 2);
00412 }
00413
00414
00415
00416
00417
00418
00419
00420 bool AdaptiveLru::
00421 do_validate() {
00422 bool okflag = true;
00423 pset<AdaptiveLruPage *> pages;
00424
00425
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
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
00479
00480
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
00500
00501
00502
00503 AdaptiveLruPage::
00504 AdaptiveLruPage(const AdaptiveLruPage ©) :
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
00521
00522
00523
00524 void AdaptiveLruPage::
00525 operator = (const AdaptiveLruPage ©) {
00526 set_lru_size(copy.get_lru_size());
00527 }
00528
00529
00530
00531
00532
00533
00534 AdaptiveLruPage::
00535 ~AdaptiveLruPage() {
00536 if (_lru != NULL) {
00537 dequeue_lru();
00538 }
00539 }
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556 void AdaptiveLruPage::
00557 evict_lru() {
00558 dequeue_lru();
00559 }
00560
00561
00562
00563
00564
00565
00566 void AdaptiveLruPage::
00567 output(ostream &out) const {
00568 out << "page " << this << ", " << _lru_size;
00569 }
00570
00571
00572
00573
00574
00575
00576 void AdaptiveLruPage::
00577 write(ostream &out, int indent_level) const {
00578 indent(out, indent_level) << *this << "\n";
00579 }
00580
00581
00582
00583
00584
00585
00586
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
00598
00599
00600
00601
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
00616
00617
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