1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2018 Couchbase, Inc
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of the License at
8  *
9  *       http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *   Unless required by applicable law or agreed to in writing, software
12  *   distributed under the License is distributed on an "AS IS" BASIS,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17 
18 #include "item_eviction.h"
19 #include "item.h"
20 
21 #include <gsl/gsl>
22 
ItemEviction()23 ItemEviction::ItemEviction() {
24 }
25 
addFreqAndAgeToHistograms(uint8_t freq, uint64_t age)26 void ItemEviction::addFreqAndAgeToHistograms(uint8_t freq, uint64_t age) {
27     freqHistogram.addValue(freq);
28     ageHistogram.addValue(age);
29 }
30 
getFreqHistogramValueCount() const31 uint64_t ItemEviction::getFreqHistogramValueCount() const {
32     return freqHistogram.getValueCount();
33 }
34 
reset()35 void ItemEviction::reset() {
36     freqHistogram.reset();
37     ageHistogram.reset();
38     requiredToUpdateInterval = 1;
39 }
40 
getThresholds( double freqPercentage, double agePercentage) const41 std::pair<uint16_t, uint64_t> ItemEviction::getThresholds(
42         double freqPercentage, double agePercentage) const {
43     uint16_t freqThreshold = gsl::narrow<uint16_t>(
44             freqHistogram.getValueAtPercentile(freqPercentage));
45     uint64_t ageThreshold = ageHistogram.getValueAtPercentile(agePercentage);
46     return std::make_pair(freqThreshold, ageThreshold);
47 }
48 
convertFreqCountToNRUValue(uint8_t probCounter)49 uint8_t ItemEviction::convertFreqCountToNRUValue(uint8_t probCounter) {
50     /*
51      * The probabilistic counter has a range form 0 to 255, however the
52      * increments are not linear - it gets more difficult to increment the
53      * counter as its increases value.  Therefore incrementing from 0 to 1 is
54      * much easier than incrementing from 254 to 255.
55      *
56      * Therefore when mapping to the 4 NRU values we do not simply want to
57      * map 0-63 => 3, 64-127 => 2 etc.  Instead we want to reflect the bias
58      * in the 4 NRU states.  Therefore we map as follows:
59      * 0-3 => 3 (coldest), 4-31 => 2, 32->63 => 1, 64->255 => 0 (hottest),
60      */
61     if (probCounter >= 64) {
62         return MIN_NRU_VALUE; /* 0 - the hottest */
63     } else if (probCounter >= 32) {
64         return 1;
65     } else if (probCounter >= 4) {
66         return INITIAL_NRU_VALUE; /* 2 */
67     }
68     return MAX_NRU_VALUE; /* 3 - the coldest */
69 }
70 
copyFreqHistogram(HdrHistogram& hist)71 void ItemEviction::copyFreqHistogram(HdrHistogram& hist) {
72     HdrHistogram::Iterator iter{
73             freqHistogram.makeLinearIterator(valueUnitsPerBucket)};
74     while (auto result = freqHistogram.getNextValueAndCount(iter)) {
75         hist.addValueAndCount(result->first, result->second);
76     }
77 }
78