36 : m_lifetime(lifetime)
37 , m_capacity(INITIAL_CAPACITY)
38 , m_markInterval(m_lifetime / EXPECTED_MARK_COUNT)
39 , m_adjustCapacityInterval(m_lifetime)
42 NDN_THROW(std::invalid_argument(
"lifetime is less than MIN_LIFETIME"));
45 for (
size_t i = 0; i < EXPECTED_MARK_COUNT; ++i) {
46 m_queue.push_back(MARK);
49 m_markEvent =
getScheduler().schedule(m_markInterval, [
this] { mark(); });
50 m_adjustCapacityEvent =
getScheduler().schedule(m_adjustCapacityInterval, [
this] { adjustCapacity(); });
53 static_assert(INITIAL_CAPACITY >= MIN_CAPACITY);
54 static_assert(INITIAL_CAPACITY <= MAX_CAPACITY);
55 BOOST_ASSERT_MSG(
static_cast<size_t>(MIN_CAPACITY * CAPACITY_UP) > MIN_CAPACITY,
56 "CAPACITY_UP must be able to increase from MIN_CAPACITY");
57 BOOST_ASSERT_MSG(
static_cast<size_t>(MAX_CAPACITY * CAPACITY_DOWN) < MAX_CAPACITY,
58 "CAPACITY_DOWN must be able to decrease from MAX_CAPACITY");
59 BOOST_ASSERT_MSG(CAPACITY_UP > 1.0,
"CAPACITY_UP must adjust up");
60 BOOST_ASSERT_MSG(CAPACITY_DOWN < 1.0,
"CAPACITY_DOWN must adjust down");
61 static_assert(EVICT_LIMIT >= 1);
67 return m_queue.size() - countMarks();
73 Entry entry = DeadNonceList::makeEntry(name, nonce);
74 return m_ht.find(entry) != m_ht.end();
80 Entry entry = DeadNonceList::makeEntry(name, nonce);
81 const auto iter = m_ht.find(entry);
82 bool isDuplicate = iter != m_ht.end();
84 NFD_LOG_TRACE(
"adding " << (isDuplicate ?
"duplicate " :
"") << name <<
" nonce=" << nonce);
87 m_queue.relocate(m_queue.end(), m_index.project<
Queue>(iter));
90 m_queue.push_back(entry);
96 DeadNonceList::makeEntry(
const Name& name, Interest::Nonce nonce)
98 const auto& nameWire = name.wireEncode();
100 std::memcpy(&n, nonce.data(),
sizeof(n));
101 return CityHash64WithSeed(
reinterpret_cast<const char*
>(nameWire.data()), nameWire.size(), n);
105 DeadNonceList::countMarks()
const
107 return m_ht.count(MARK);
111 DeadNonceList::mark()
113 m_queue.push_back(MARK);
114 size_t nMarks = countMarks();
115 m_actualMarkCounts.insert(nMarks);
119 m_markEvent =
getScheduler().schedule(m_markInterval, [
this] { mark(); });
123 DeadNonceList::adjustCapacity()
125 auto oldCapacity = m_capacity;
126 auto equalRange = m_actualMarkCounts.equal_range(EXPECTED_MARK_COUNT);
127 if (equalRange.second == m_actualMarkCounts.begin()) {
129 m_capacity = std::max(MIN_CAPACITY,
static_cast<size_t>(m_capacity * CAPACITY_DOWN));
131 else if (equalRange.first == m_actualMarkCounts.end()) {
133 m_capacity = std::min(MAX_CAPACITY,
static_cast<size_t>(m_capacity * CAPACITY_UP));
136 if (m_capacity != oldCapacity) {
137 NFD_LOG_TRACE(
"adjusting capacity " << oldCapacity <<
" -> " << m_capacity);
140 m_actualMarkCounts.clear();
143 m_adjustCapacityEvent =
getScheduler().schedule(m_adjustCapacityInterval, [
this] { adjustCapacity(); });
147 DeadNonceList::evictEntries()
149 if (m_queue.size() <= m_capacity)
152 auto nEvict = std::min(m_queue.size() - m_capacity, EVICT_LIMIT);
153 for (
size_t i = 0; i < nEvict; i++) {
156 BOOST_ASSERT(m_queue.size() >= m_capacity);
158 NFD_LOG_TRACE(
"evicted=" << nEvict <<
" size=" <<
size() <<
" capacity=" << m_capacity);
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed)
static constexpr time::nanoseconds MIN_LIFETIME
Minimum entry lifetime.
static constexpr time::nanoseconds DEFAULT_LIFETIME
Default entry lifetime.
DeadNonceList(time::nanoseconds lifetime=DEFAULT_LIFETIME)
Constructs the Dead Nonce List.
size_t size() const
Returns the number of stored nonces.
void add(const Name &name, Interest::Nonce nonce)
Adds name+nonce to the list.
bool has(const Name &name, Interest::Nonce nonce) const
Determines if name+nonce is in the list.
#define NFD_LOG_INIT(name)
boost::multi_index_container< Policy::EntryRef, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::ordered_unique< boost::multi_index::identity< Policy::EntryRef > > > > Queue
ndn::Scheduler & getScheduler()
Returns the global Scheduler instance for the calling thread.