37 const size_t DeadNonceList::INITIAL_CAPACITY = 1 << 7;
38 const size_t DeadNonceList::MIN_CAPACITY = 1 << 3;
39 const size_t DeadNonceList::MAX_CAPACITY = 1 << 24;
40 const DeadNonceList::Entry DeadNonceList::MARK = 0;
41 const size_t DeadNonceList::EXPECTED_MARK_COUNT = 5;
42 const double DeadNonceList::CAPACITY_UP = 1.2;
43 const double DeadNonceList::CAPACITY_DOWN = 0.9;
44 const size_t DeadNonceList::EVICT_LIMIT = 1 << 6;
47 : m_lifetime(lifetime)
48 , m_queue(m_index.
get<0>())
49 , m_ht(m_index.
get<1>())
50 , m_capacity(INITIAL_CAPACITY)
51 , m_markInterval(m_lifetime / EXPECTED_MARK_COUNT)
52 , m_adjustCapacityInterval(m_lifetime)
55 NDN_THROW(std::invalid_argument(
"lifetime is less than MIN_LIFETIME"));
58 for (
size_t i = 0; i < EXPECTED_MARK_COUNT; ++i) {
59 m_queue.push_back(MARK);
62 m_markEvent =
getScheduler().schedule(m_markInterval, [
this] { mark(); });
63 m_adjustCapacityEvent =
getScheduler().schedule(m_adjustCapacityInterval, [
this] { adjustCapacity(); });
69 m_adjustCapacityEvent.
cancel();
72 static_assert(INITIAL_CAPACITY >= MIN_CAPACITY,
"INITIAL_CAPACITY is too small");
73 static_assert(INITIAL_CAPACITY <= MAX_CAPACITY,
"INITIAL_CAPACITY is too large");
74 BOOST_ASSERT_MSG(
static_cast<size_t>(MIN_CAPACITY * CAPACITY_UP) > MIN_CAPACITY,
75 "CAPACITY_UP must be able to increase from MIN_CAPACITY");
76 BOOST_ASSERT_MSG(
static_cast<size_t>(MAX_CAPACITY * CAPACITY_DOWN) < MAX_CAPACITY,
77 "CAPACITY_DOWN must be able to decrease from MAX_CAPACITY");
78 BOOST_ASSERT_MSG(CAPACITY_UP > 1.0,
"CAPACITY_UP must adjust up");
79 BOOST_ASSERT_MSG(CAPACITY_DOWN < 1.0,
"CAPACITY_DOWN must adjust down");
80 static_assert(EVICT_LIMIT >= 1,
"EVICT_LIMIT must be at least 1");
86 return m_queue.size() - this->countMarks();
92 Entry entry = DeadNonceList::makeEntry(
name, nonce);
93 return m_ht.find(entry) != m_ht.end();
99 Entry entry = DeadNonceList::makeEntry(
name, nonce);
100 m_queue.push_back(entry);
102 this->evictEntries();
106 DeadNonceList::makeEntry(
const Name&
name, uint32_t nonce)
110 static_cast<uint64_t
>(nonce));
114 DeadNonceList::countMarks()
const
116 return m_ht.count(MARK);
120 DeadNonceList::mark()
122 m_queue.push_back(MARK);
123 size_t nMarks = this->countMarks();
124 m_actualMarkCounts.insert(nMarks);
128 m_markEvent =
getScheduler().schedule(m_markInterval, [
this] { mark(); });
132 DeadNonceList::adjustCapacity()
134 auto equalRange = m_actualMarkCounts.equal_range(EXPECTED_MARK_COUNT);
135 if (equalRange.second == m_actualMarkCounts.begin()) {
137 m_capacity = std::max(MIN_CAPACITY,
static_cast<size_t>(m_capacity * CAPACITY_DOWN));
138 NFD_LOG_TRACE(
"adjustCapacity DOWN capacity=" << m_capacity);
140 else if (equalRange.first == m_actualMarkCounts.end()) {
142 m_capacity = std::min(MAX_CAPACITY,
static_cast<size_t>(m_capacity * CAPACITY_UP));
146 m_actualMarkCounts.clear();
147 this->evictEntries();
149 m_adjustCapacityEvent =
getScheduler().schedule(m_adjustCapacityInterval, [
this] { adjustCapacity(); });
153 DeadNonceList::evictEntries()
155 ssize_t nOverCapacity = m_queue.size() - m_capacity;
156 if (nOverCapacity <= 0)
159 for (ssize_t nEvict = std::min<ssize_t>(nOverCapacity, EVICT_LIMIT); nEvict > 0; --nEvict) {
160 m_queue.erase(m_queue.begin());
162 BOOST_ASSERT(m_queue.size() >= m_capacity);