table: DeadNonceList code cleanup/modernization
Change-Id: I7d2bb8982b60b138c979470406b0a607301f2768
diff --git a/daemon/table/dead-nonce-list.cpp b/daemon/table/dead-nonce-list.cpp
index 142ddea..c89e9cc 100644
--- a/daemon/table/dead-nonce-list.cpp
+++ b/daemon/table/dead-nonce-list.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2020, Regents of the University of California,
+ * Copyright (c) 2014-2021, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -32,16 +32,16 @@
NFD_LOG_INIT(DeadNonceList);
-const time::nanoseconds DeadNonceList::DEFAULT_LIFETIME = 6_s;
-const time::nanoseconds DeadNonceList::MIN_LIFETIME = 1_ms;
-const size_t DeadNonceList::INITIAL_CAPACITY = 1 << 7;
-const size_t DeadNonceList::MIN_CAPACITY = 1 << 3;
-const size_t DeadNonceList::MAX_CAPACITY = 1 << 24;
-const DeadNonceList::Entry DeadNonceList::MARK = 0;
-const size_t DeadNonceList::EXPECTED_MARK_COUNT = 5;
-const double DeadNonceList::CAPACITY_UP = 1.2;
-const double DeadNonceList::CAPACITY_DOWN = 0.9;
-const size_t DeadNonceList::EVICT_LIMIT = 1 << 6;
+const time::nanoseconds DeadNonceList::DEFAULT_LIFETIME;
+const time::nanoseconds DeadNonceList::MIN_LIFETIME;
+const size_t DeadNonceList::INITIAL_CAPACITY;
+const size_t DeadNonceList::MIN_CAPACITY;
+const size_t DeadNonceList::MAX_CAPACITY;
+const DeadNonceList::Entry DeadNonceList::MARK;
+const size_t DeadNonceList::EXPECTED_MARK_COUNT;
+const double DeadNonceList::CAPACITY_UP;
+const double DeadNonceList::CAPACITY_DOWN;
+const size_t DeadNonceList::EVICT_LIMIT;
DeadNonceList::DeadNonceList(time::nanoseconds lifetime)
: m_lifetime(lifetime)
@@ -61,12 +61,6 @@
m_markEvent = getScheduler().schedule(m_markInterval, [this] { mark(); });
m_adjustCapacityEvent = getScheduler().schedule(m_adjustCapacityInterval, [this] { adjustCapacity(); });
-}
-
-DeadNonceList::~DeadNonceList()
-{
- m_markEvent.cancel();
- m_adjustCapacityEvent.cancel();
BOOST_ASSERT_MSG(DEFAULT_LIFETIME >= MIN_LIFETIME, "DEFAULT_LIFETIME is too small");
static_assert(INITIAL_CAPACITY >= MIN_CAPACITY, "INITIAL_CAPACITY is too small");
@@ -83,7 +77,7 @@
size_t
DeadNonceList::size() const
{
- return m_queue.size() - this->countMarks();
+ return m_queue.size() - countMarks();
}
bool
@@ -99,13 +93,13 @@
Entry entry = DeadNonceList::makeEntry(name, nonce);
m_queue.push_back(entry);
- this->evictEntries();
+ evictEntries();
}
DeadNonceList::Entry
DeadNonceList::makeEntry(const Name& name, Interest::Nonce nonce)
{
- Block nameWire = name.wireEncode();
+ const auto& nameWire = name.wireEncode();
uint32_t n;
std::memcpy(&n, nonce.data(), sizeof(n));
return CityHash64WithSeed(reinterpret_cast<const char*>(nameWire.wire()), nameWire.size(), n);
@@ -121,7 +115,7 @@
DeadNonceList::mark()
{
m_queue.push_back(MARK);
- size_t nMarks = this->countMarks();
+ size_t nMarks = countMarks();
m_actualMarkCounts.insert(nMarks);
NFD_LOG_TRACE("mark nMarks=" << nMarks);
@@ -145,7 +139,7 @@
}
m_actualMarkCounts.clear();
- this->evictEntries();
+ evictEntries();
m_adjustCapacityEvent = getScheduler().schedule(m_adjustCapacityInterval, [this] { adjustCapacity(); });
}
@@ -153,11 +147,11 @@
void
DeadNonceList::evictEntries()
{
- ssize_t nOverCapacity = m_queue.size() - m_capacity;
- if (nOverCapacity <= 0) // not over capacity
+ if (m_queue.size() <= m_capacity) // not over capacity
return;
- for (ssize_t nEvict = std::min<ssize_t>(nOverCapacity, EVICT_LIMIT); nEvict > 0; --nEvict) {
+ auto nEvict = std::min(m_queue.size() - m_capacity, EVICT_LIMIT);
+ for (; nEvict > 0; --nEvict) {
m_queue.erase(m_queue.begin());
}
BOOST_ASSERT(m_queue.size() >= m_capacity);
diff --git a/daemon/table/dead-nonce-list.hpp b/daemon/table/dead-nonce-list.hpp
index 5322dd4..ff9dfcd 100644
--- a/daemon/table/dead-nonce-list.hpp
+++ b/daemon/table/dead-nonce-list.hpp
@@ -34,56 +34,58 @@
namespace nfd {
-/** \brief Represents the Dead Nonce List
+/**
+ * \brief Represents the Dead Nonce List.
*
- * The Dead Nonce List is a global table that supplements PIT for loop detection.
- * When a Nonce is erased (dead) from PIT entry, the Nonce and the Interest Name is added to
- * Dead Nonce List, and kept for a duration in which most loops are expected to have occured.
+ * The Dead Nonce List is a global table that supplements the PIT for loop detection.
+ * When a Nonce is erased (dead) from a PIT entry, the Nonce and the Interest Name are added to
+ * the Dead Nonce List and kept for a duration in which most loops are expected to have occured.
*
- * To reduce memory usage, the Interest Name and Nonce are stored as a 64-bit hash.
- * There could be false positives (non-looping Interest could be considered looping),
- * but the probability is small, and the error is recoverable when consumer retransmits
- * with a different Nonce.
+ * To reduce memory usage, the Interest Name and Nonce are stored as a 64-bit hash.
+ * The probability of false positives (a non-looping Interest considered as looping) is small
+ * and a collision is recoverable when the consumer retransmits with a different Nonce.
*
- * To reduce memory usage, entries do not have associated timestamps. Instead,
- * lifetime of entries is controlled by dynamically adjusting the capacity of the container.
- * At fixed intervals, the MARK, an entry with a special value, is inserted into the container.
- * The number of MARKs stored in the container reflects the lifetime of entries,
- * because MARKs are inserted at fixed intervals.
+ * To reduce memory usage, entries do not have associated timestamps. Instead, the lifetime
+ * of the entries is controlled by dynamically adjusting the capacity of the container.
+ * At fixed intervals, a MARK (an entry with a special value) is inserted into the container.
+ * The number of MARKs stored in the container reflects the lifetime of the entries,
+ * because MARKs are inserted at fixed intervals.
*/
class DeadNonceList : noncopyable
{
public:
- /** \brief Constructs the Dead Nonce List
- * \param lifetime duration of the expected lifetime of each nonce,
- * must be no less than MIN_LIFETIME.
- * This should be set to the duration in which most loops would have occured.
- * A loop cannot be detected if delay of the cycle is greater than lifetime.
- * \throw std::invalid_argument if lifetime is less than MIN_LIFETIME
+ /**
+ * \brief Constructs the Dead Nonce List
+ * \param lifetime expected lifetime of each nonce, must be no less than #MIN_LIFETIME.
+ * This should be set to a duration over which most loops would have occured.
+ * A loop cannot be detected if the total delay of the cycle is greater than lifetime.
+ * \throw std::invalid_argument if lifetime is less than #MIN_LIFETIME
*/
explicit
DeadNonceList(time::nanoseconds lifetime = DEFAULT_LIFETIME);
- ~DeadNonceList();
-
- /** \brief Determines if name+nonce exists
- * \return true if name+nonce exists, false otherwise
+ /**
+ * \brief Determines if name+nonce is in the list
+ * \return true if name+nonce exists, false otherwise
*/
bool
has(const Name& name, Interest::Nonce nonce) const;
- /** \brief Records name+nonce
+ /**
+ * \brief Adds name+nonce to the list
*/
void
add(const Name& name, Interest::Nonce nonce);
- /** \return number of stored Nonces
- * \note The return value does not contain non-Nonce entries in the index, if any.
+ /**
+ * \brief Returns the number of stored nonces
+ * \note The return value does not contain non-Nonce entries in the index, if any.
*/
size_t
size() const;
- /** \return expected lifetime
+ /**
+ * \brief Returns the expected nonce lifetime
*/
time::nanoseconds
getLifetime() const
@@ -91,26 +93,12 @@
return m_lifetime;
}
-private: // Entry and Index
- typedef uint64_t Entry;
+private:
+ using Entry = uint64_t;
static Entry
makeEntry(const Name& name, Interest::Nonce nonce);
- typedef boost::multi_index_container<
- Entry,
- boost::multi_index::indexed_by<
- boost::multi_index::sequenced<>,
- boost::multi_index::hashed_non_unique<
- boost::multi_index::identity<Entry>
- >
- >
- > Index;
-
- typedef Index::nth_index<0>::type Queue;
- typedef Index::nth_index<1>::type Hashtable;
-
-private: // actual lifetime estimation and capacity control
/** \brief Return the number of MARKs in the index
*/
size_t
@@ -136,17 +124,28 @@
public:
/// Default entry lifetime
- static const time::nanoseconds DEFAULT_LIFETIME;
+ static constexpr time::nanoseconds DEFAULT_LIFETIME = 6_s;
/// Minimum entry lifetime
- static const time::nanoseconds MIN_LIFETIME;
+ static constexpr time::nanoseconds MIN_LIFETIME = 1_ms;
private:
- time::nanoseconds m_lifetime;
+ const time::nanoseconds m_lifetime;
+
+ using Index = boost::multi_index_container<
+ Entry,
+ boost::multi_index::indexed_by<
+ boost::multi_index::sequenced<>,
+ boost::multi_index::hashed_non_unique<boost::multi_index::identity<Entry>>
+ >
+ >;
+ using Queue = Index::nth_index<0>::type;
+ using Hashtable = Index::nth_index<1>::type;
+
Index m_index;
Queue& m_queue;
Hashtable& m_ht;
-NFD_PUBLIC_WITH_TESTS_ELSE_PRIVATE: // actual lifetime estimation and capacity control
+NFD_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
// ---- current capacity and hard limits
@@ -159,33 +158,32 @@
*/
size_t m_capacity;
- static const size_t INITIAL_CAPACITY;
+ static constexpr size_t INITIAL_CAPACITY = 1 << 7;
/** \brief Minimum capacity
*
* This is to ensure correct algorithm operations.
*/
- static const size_t MIN_CAPACITY;
+ static constexpr size_t MIN_CAPACITY = 1 << 3;
/** \brief Maximum capacity
*
* This is to limit memory usage.
*/
- static const size_t MAX_CAPACITY;
+ static constexpr size_t MAX_CAPACITY = 1 << 24;
// ---- actual entry lifetime estimation
/** \brief The MARK for capacity
*
* The MARK doesn't have a distinct type.
- * Entry is a hash. The hash function should have non-invertible property,
- * so it's unlikely for a usual Entry to have collision with the MARK.
+ * Entry is a hash. The hash function should be non-invertible, so that
+ * it's infeasible to craft a "normal" Entry that collides with the MARK.
*/
- static const Entry MARK;
+ static constexpr Entry MARK = 0;
- /** \brief Expected number of MARKs in the index
- */
- static const size_t EXPECTED_MARK_COUNT;
+ /// Expected number of MARKs in the index
+ static constexpr size_t EXPECTED_MARK_COUNT = 5;
/** \brief Number of MARKs in the index after each MARK insertion
*
@@ -194,18 +192,18 @@
*/
std::multiset<size_t> m_actualMarkCounts;
- time::nanoseconds m_markInterval;
- scheduler::EventId m_markEvent;
+ const time::nanoseconds m_markInterval;
+ scheduler::ScopedEventId m_markEvent;
// ---- capacity adjustments
- static const double CAPACITY_UP;
- static const double CAPACITY_DOWN;
- time::nanoseconds m_adjustCapacityInterval;
- scheduler::EventId m_adjustCapacityEvent;
+ static constexpr double CAPACITY_UP = 1.2;
+ static constexpr double CAPACITY_DOWN = 0.9;
+ const time::nanoseconds m_adjustCapacityInterval;
+ scheduler::ScopedEventId m_adjustCapacityEvent;
- /// Maximum number of entries to evict at each operation if index is over capacity
- static const size_t EVICT_LIMIT;
+ /// Maximum number of entries to evict at each operation if the index is over capacity
+ static constexpr size_t EVICT_LIMIT = 64;
};
} // namespace nfd
diff --git a/docs/doxygen.conf.in b/docs/doxygen.conf.in
index d68d7c6..edc9da7 100644
--- a/docs/doxygen.conf.in
+++ b/docs/doxygen.conf.in
@@ -1041,13 +1041,6 @@
ALPHABETICAL_INDEX = YES
-# The COLS_IN_ALPHA_INDEX tag can be used to specify the number of columns in
-# which the alphabetical index list will be split.
-# Minimum value: 1, maximum value: 20, default value: 5.
-# This tag requires that the tag ALPHABETICAL_INDEX is set to YES.
-
-COLS_IN_ALPHA_INDEX = 5
-
# In case all classes in a project start with a common prefix, all classes will
# be put under the same header in the alphabetical index. The IGNORE_PREFIX tag
# can be used to specify a prefix (or a list of prefixes) that should be ignored
diff --git a/tests/daemon/table/dead-nonce-list.t.cpp b/tests/daemon/table/dead-nonce-list.t.cpp
index a5a537e..fb3ab90 100644
--- a/tests/daemon/table/dead-nonce-list.t.cpp
+++ b/tests/daemon/table/dead-nonce-list.t.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2020, Regents of the University of California,
+ * Copyright (c) 2014-2021, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -55,15 +55,14 @@
BOOST_AUTO_TEST_CASE(MinLifetime)
{
- BOOST_CHECK_THROW(DeadNonceList dnl(time::milliseconds::zero()), std::invalid_argument);
+ BOOST_CHECK_THROW(DeadNonceList(0_ms), std::invalid_argument);
}
-/// A Fixture that periodically inserts Nonces
+/// A fixture that periodically inserts Nonces
class PeriodicalInsertionFixture : public GlobalIoTimeFixture
{
protected:
PeriodicalInsertionFixture()
- : dnl(LIFETIME)
{
addNonce();
}
@@ -81,31 +80,30 @@
dnl.add(name, ++lastNonce);
}
- if (addNonceInterval > 0_ns) {
- addNonceEvent = getScheduler().schedule(addNonceInterval, [this] { addNonce(); });
- }
+ addNonceEvent = getScheduler().schedule(ADD_INTERVAL, [this] { addNonce(); });
}
/** \brief advance clocks by LIFETIME*t
*/
void
- advanceClocksByLifetime(float t)
+ advanceClocksByLifetime(double t)
{
- advanceClocks(timeUnit, time::duration_cast<time::nanoseconds>(LIFETIME * t));
+ advanceClocks(ADD_INTERVAL / 2, time::duration_cast<time::nanoseconds>(LIFETIME * t));
}
protected:
- static const time::nanoseconds LIFETIME;
- DeadNonceList dnl;
+ static constexpr time::nanoseconds LIFETIME = 200_ms;
+ static constexpr time::nanoseconds ADD_INTERVAL = LIFETIME / DeadNonceList::EXPECTED_MARK_COUNT;
+
+ DeadNonceList dnl{LIFETIME};
Name name = "/N";
uint32_t lastNonce = 0;
size_t addNonceBatch = 0;
- const time::nanoseconds addNonceInterval = LIFETIME / DeadNonceList::EXPECTED_MARK_COUNT;
- const time::nanoseconds timeUnit = addNonceInterval / 2;
scheduler::ScopedEventId addNonceEvent;
};
-const time::nanoseconds PeriodicalInsertionFixture::LIFETIME = 200_ms;
+const time::nanoseconds PeriodicalInsertionFixture::LIFETIME;
+const time::nanoseconds PeriodicalInsertionFixture::ADD_INTERVAL;
BOOST_FIXTURE_TEST_CASE(Lifetime, PeriodicalInsertionFixture)
{