36 const size_t DeadNonceList::INITIAL_CAPACITY = (1 << 7);
37 const size_t DeadNonceList::MIN_CAPACITY = (1 << 3);
38 const size_t DeadNonceList::MAX_CAPACITY = (1 << 24);
39 const DeadNonceList::Entry DeadNonceList::MARK = 0;
40 const size_t DeadNonceList::EXPECTED_MARK_COUNT = 5;
41 const double DeadNonceList::CAPACITY_UP = 1.2;
42 const double DeadNonceList::CAPACITY_DOWN = 0.9;
43 const size_t DeadNonceList::EVICT_LIMIT = (1 << 6);
46 : m_lifetime(lifetime)
47 , m_queue(m_index.get<0>())
48 , m_ht(m_index.get<1>())
49 , m_capacity(INITIAL_CAPACITY)
50 , m_markInterval(m_lifetime / EXPECTED_MARK_COUNT)
51 , m_adjustCapacityInterval(m_lifetime)
54 BOOST_THROW_EXCEPTION(std::invalid_argument(
"lifetime is less than MIN_LIFETIME"));
57 for (
size_t i = 0; i < EXPECTED_MARK_COUNT; ++i) {
58 m_queue.push_back(MARK);
63 bind(&DeadNonceList::adjustCapacity,
this));
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);
132 DeadNonceList::adjustCapacity()
135 m_actualMarkCounts.equal_range(EXPECTED_MARK_COUNT);
137 if (equalRange.second == m_actualMarkCounts.begin()) {
139 m_capacity = std::max(MIN_CAPACITY,
140 static_cast<size_t>(m_capacity * CAPACITY_DOWN));
141 NFD_LOG_TRACE(
"adjustCapacity DOWN capacity=" << m_capacity);
143 else if (equalRange.first == m_actualMarkCounts.end()) {
145 m_capacity = std::min(MAX_CAPACITY,
146 static_cast<size_t>(m_capacity * CAPACITY_UP));
150 m_actualMarkCounts.clear();
152 this->evictEntries();
155 bind(&DeadNonceList::adjustCapacity,
this));
159 DeadNonceList::evictEntries()
161 ssize_t nOverCapacity = m_queue.size() - m_capacity;
162 if (nOverCapacity <= 0)
165 for (ssize_t nEvict = std::min<ssize_t>(nOverCapacity, EVICT_LIMIT); nEvict > 0; --nEvict) {
166 m_queue.erase(m_queue.begin());
168 BOOST_ASSERT(m_queue.size() >= m_capacity);
static const time::nanoseconds MIN_LIFETIME
minimum entry lifetime
void cancel(const EventId &eventId)
cancel a scheduled event
const uint8_t * wire() const
Get pointer to encoded wire.
Represents a TLV element of NDN packet format.
void add(const Name &name, uint32_t nonce)
records name+nonce
Table::const_iterator iterator
#define NFD_LOG_TRACE(expression)
size_t size() const
Get size of encoded wire, including Type-Length-Value.
Copyright (c) 2011-2015 Regents of the University of California.
static const time::nanoseconds DEFAULT_LIFETIME
default entry lifetime
DeadNonceList(const time::nanoseconds &lifetime=DEFAULT_LIFETIME)
constructs the Dead Nonce List
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed)
Represents an absolute name.
bool has(const Name &name, uint32_t nonce) const
determines if name+nonce exists
EventId schedule(time::nanoseconds after, const EventCallback &event)
schedule an event
#define NFD_LOG_INIT(name)