Panda3D
|
00001 // Filename: lru.h 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 #ifndef LRU_H 00016 #define LRU_H 00017 00018 #define ENABLE_MUTEX 1 00019 00020 #if ENABLE_MUTEX 00021 #include "lightMutex.h" 00022 #include "lightMutexHolder.h" 00023 #define LruMutexHolder(mutex) MutexHolder(mutex) 00024 #else 00025 #define LruMutexHolder(mutex) 00026 #endif 00027 00028 00029 static const int MAXIMUM_LRU_PAGE_TYPES = 8; 00030 static const int FRAME_MAXIMUM_PRIORITY_CHANGES = 256; 00031 00032 00033 class Lru; 00034 class LruPage; 00035 00036 enum LruPagePriority 00037 { 00038 LPP_Highest = 0, 00039 LPP_High = 10, 00040 LPP_New = 20, 00041 LPP_Normal = 25, 00042 LPP_Intermediate = 30, 00043 LPP_Low = 40, 00044 LPP_TotalPriorities = 50, 00045 00046 LPP_PageOut = LPP_TotalPriorities - 1 00047 }; 00048 00049 typedef union _LruPageType 00050 { 00051 void *pointer; 00052 00053 } 00054 LruPageType; 00055 00056 typedef struct 00057 { 00058 int total_pages; 00059 int total_pages_in; 00060 int total_pages_out; 00061 int total_memory_in; 00062 int total_memory_out; 00063 } 00064 PageTypeStatistics; 00065 00066 typedef bool (*LruPageTypeFunction) (LruPage *lru_page); 00067 00068 class EXPCL_PANDA_DISPLAY LruPage 00069 { 00070 00071 protected: 00072 00073 LruPage ( ); 00074 ~LruPage ( ); 00075 void change_priority (int delta); 00076 00077 public: 00078 00079 typedef struct _LruPageVariables 00080 { 00081 LruPageType lru_page_type; // pointer to memory type 00082 00083 int size; 00084 LruPagePriority priority; 00085 int priority_change; 00086 00087 struct 00088 { 00089 unsigned int type : 8; 00090 unsigned int lock : 1; 00091 unsigned int in_cache : 1; 00092 unsigned int in_memory : 1; 00093 unsigned int on_disk : 1; 00094 unsigned int pre_allocated : 1; 00095 unsigned int allocated : 1; 00096 unsigned int in_lru : 1; 00097 } v; 00098 00099 int first_frame_identifier; // creation time 00100 int last_frame_identifier; // previous time page was used 00101 int current_frame_identifier; 00102 int update_frame_identifier; 00103 00104 int current_frame_usage; 00105 int last_frame_usage; 00106 00107 int total_frame_page_faults; 00108 int total_page_faults; 00109 00110 int total_usage; 00111 int update_total_usage; 00112 00113 int identifier; 00114 00115 PN_stdfloat average_frame_utilization; 00116 00117 LruPage *previous; 00118 LruPage *next; 00119 Lru *lru; 00120 00121 string name; 00122 } 00123 LruPageVariables; 00124 00125 LruPageVariables _m; 00126 00127 friend class Lru; 00128 }; 00129 00130 //////////////////////////////////////////////////////////////////// 00131 // Class : Lru 00132 // Description : Least Recently Used algorithm implementation: 00133 // In the Lru, each "memory page" has an associated class LruPage. 00134 // The Lru has a range of priorities from LPP_Highest to 00135 // LPP_PagedOut. Each priority has a doubly linked list of LruPages. 00136 // The algorithim uses an adaptive method based on the average 00137 // utilization of each page per frame (or time slice). The 00138 // average utilization is calculated with an exponetial moving 00139 // average. This is superior to a standard average since a standard 00140 // average becomes less and less adaptive the longer a page exists. 00141 // The average utilization is used to set the priority of each page. 00142 // A higher average utilization automatically raises the priority 00143 // of a page and a lower average utilization automatically lowers 00144 // the priority of a page. Therefore, pages with a higher average 00145 // utilization have a higher chance of being kept in memory or 00146 // cached and pages with a lower average utilization have a higher 00147 // chance of being paged out. When a page is paged in and there 00148 // is not enough memory available, then the lowest priority pages 00149 // will be paged out first until there is enough memory available. 00150 //////////////////////////////////////////////////////////////////// 00151 class EXPCL_PANDA_DISPLAY Lru 00152 { 00153 public: 00154 00155 Lru (int maximum_memory, int maximum_pages, int maximum_page_types); 00156 ~Lru ( ); 00157 00158 bool register_lru_page_type (int index, LruPageTypeFunction page_in_function, LruPageTypeFunction page_out_function); 00159 00160 LruPage *allocate_page (int size); 00161 void update_start_update_lru_page (LruPage *lru_page); 00162 00163 void free_page (LruPage *lru_page); 00164 00165 void add_page (LruPagePriority priority, LruPage *lru_page); 00166 void add_cached_page (LruPagePriority priority, LruPage *lru_page); 00167 void remove_page (LruPage *lru_page); 00168 00169 void lock_page (LruPage *lru_page); 00170 void unlock_page (LruPage *lru_page); 00171 00172 void access_page (LruPage *lru_page); 00173 00174 void set_maximum_frame_bandwidth_utilization (PN_stdfloat maximum_frame_bandwidth_utilization); 00175 00176 void begin_frame ( ); 00177 00178 void update_entire_lru ( ); 00179 void partial_lru_update (int maximum_updates); 00180 00181 // set maximum number of page updates per frame 00182 // pause/resume updates/current_frame_identifier 00183 00184 void unlock_all_pages (void); 00185 00186 void count_priority_level_pages (void); 00187 00188 void calculate_lru_statistics (void); 00189 00190 bool page_out_lru (int memory_required); 00191 00192 private: 00193 void update_page_priorities (void); 00194 void update_lru_page (LruPage *lru_page); 00195 void update_lru_page_old (LruPage *lru_page); 00196 00197 public: 00198 typedef struct _LruVariables 00199 { 00200 // LruPagePriority lists 00201 LruPage *lru_page_array [LPP_TotalPriorities]; 00202 00203 int total_pages; 00204 int available_memory; 00205 int current_frame_identifier; 00206 00207 int maximum_memory; 00208 int minimum_memory; // target amount of memory to keep free if possible 00209 int maximum_page_types; 00210 00211 int total_lifetime_page_ins; 00212 int total_lifetime_page_outs; 00213 00214 int total_page_ins_last_frame; 00215 int total_page_outs_last_frame; 00216 00217 int total_page_ins; 00218 int total_page_outs; 00219 00220 int total_page_access; 00221 double total_page_access_size; 00222 double total_page_all_access_size; 00223 00224 int start_priority_index; 00225 LruPage *start_update_lru_page; 00226 00227 int identifier; // the number of pages created during the lifetime of the LRU 00228 00229 PN_stdfloat weight; // used for exponential moving average 00230 PN_stdfloat maximum_frame_bandwidth_utilization; 00231 00232 PN_stdfloat frame_bandwidth_factor; 00233 00234 LruPageTypeFunction page_in_function_array [MAXIMUM_LRU_PAGE_TYPES]; 00235 LruPageTypeFunction page_out_function_array [MAXIMUM_LRU_PAGE_TYPES]; 00236 00237 int total_lru_page_priority_changes; 00238 LruPage *lru_page_priority_change_array [FRAME_MAXIMUM_PRIORITY_CHANGES]; 00239 00240 int maximum_pages; 00241 int total_lru_pages_in_pool; 00242 int total_lru_pages_in_free_pool; 00243 LruPage **lru_page_pool; 00244 LruPage **lru_page_free_pool; 00245 00246 int lru_page_count_array [LPP_TotalPriorities]; 00247 PageTypeStatistics *page_type_statistics_array; 00248 00249 void *context; // user specified data 00250 00251 #if ENABLE_MUTEX 00252 Mutex *mutex; 00253 #endif 00254 } 00255 LruVariables; 00256 00257 LruVariables _m; 00258 00259 friend class LruPage; 00260 }; 00261 00262 PN_stdfloat calculate_exponential_moving_average (PN_stdfloat value, PN_stdfloat weight, PN_stdfloat average); 00263 bool default_page_in_function (LruPage *lru_page); 00264 bool default_page_out_function (LruPage *lru_page); 00265 00266 void test_ema (void); 00267 void test_lru (void); 00268 00269 #endif