| 143 | * right. */ |
| 144 | |
| 145 | void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) { |
| 146 | int j, k, count; |
| 147 | dictEntry *samples[server.maxmemory_samples]; |
| 148 | |
| 149 | count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples); |
| 150 | for (j = 0; j < count; j++) { |
| 151 | unsigned long long idle; |
| 152 | sds key; |
| 153 | robj *o; |
| 154 | dictEntry *de; |
| 155 | |
| 156 | de = samples[j]; |
| 157 | key = dictGetKey(de); |
| 158 | |
| 159 | /* If the dictionary we are sampling from is not the main |
| 160 | * dictionary (but the expires one) we need to lookup the key |
| 161 | * again in the key dictionary to obtain the value object. */ |
| 162 | if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) { |
| 163 | if (sampledict != keydict) de = dictFind(keydict, key); |
| 164 | o = dictGetVal(de); |
| 165 | } |
| 166 | |
| 167 | /* Calculate the idle time according to the policy. This is called |
| 168 | * idle just because the code initially handled LRU, but is in fact |
| 169 | * just a score where an higher score means better candidate. */ |
| 170 | if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) { |
| 171 | idle = estimateObjectIdleTime(o); |
| 172 | } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { |
| 173 | /* When we use an LRU policy, we sort the keys by idle time |
| 174 | * so that we expire keys starting from greater idle time. |
| 175 | * However when the policy is an LFU one, we have a frequency |
| 176 | * estimation, and we want to evict keys with lower frequency |
| 177 | * first. So inside the pool we put objects using the inverted |
| 178 | * frequency subtracting the actual frequency to the maximum |
| 179 | * frequency of 255. */ |
| 180 | idle = 255-LFUDecrAndReturn(o); |
| 181 | } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) { |
| 182 | /* In this case the sooner the expire the better. */ |
| 183 | idle = ULLONG_MAX - (long)dictGetVal(de); |
| 184 | } else { |
| 185 | serverPanic("Unknown eviction policy in evictionPoolPopulate()"); |
| 186 | } |
| 187 | |
| 188 | /* Insert the element inside the pool. |
| 189 | * First, find the first empty bucket or the first populated |
| 190 | * bucket that has an idle time smaller than our idle time. */ |
| 191 | k = 0; |
| 192 | while (k < EVPOOL_SIZE && |
| 193 | pool[k].key && |
| 194 | pool[k].idle < idle) k++; |
| 195 | if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) { |
| 196 | /* Can't insert if the element is < the worst element we have |
| 197 | * and there are no empty buckets. */ |
| 198 | continue; |
| 199 | } else if (k < EVPOOL_SIZE && pool[k].key == NULL) { |
| 200 | /* Inserting into empty position. No setup needed before insert. */ |
| 201 | } else { |
| 202 | /* Inserting in the middle. Now k points to the first element |
no test coverage detected