fw: use dead Nonce list in pipelines
refs #1953
Change-Id: I0faef2a985b03fe96387c2e0181588713550b9ce
diff --git a/daemon/table/dead-nonce-list.hpp b/daemon/table/dead-nonce-list.hpp
index ad2e0ad..1c7f7cc 100644
--- a/daemon/table/dead-nonce-list.hpp
+++ b/daemon/table/dead-nonce-list.hpp
@@ -83,6 +83,11 @@
size_t
size() const;
+ /** \return expected lifetime
+ */
+ const time::nanoseconds&
+ getLifetime() const;
+
private: // Entry and Index
typedef uint64_t Entry;
@@ -206,6 +211,12 @@
static const size_t EVICT_LIMIT;
};
+inline const time::nanoseconds&
+DeadNonceList::getLifetime() const
+{
+ return m_lifetime;
+}
+
} // namespace nfd
#endif // NFD_DAEMON_TABLE_DEAD_NONCE_LIST_HPP
diff --git a/daemon/table/pit-entry.cpp b/daemon/table/pit-entry.cpp
index e089a09..35cc2e0 100644
--- a/daemon/table/pit-entry.cpp
+++ b/daemon/table/pit-entry.cpp
@@ -126,10 +126,38 @@
return false;
}
-bool
-Entry::addNonce(uint32_t nonce)
+int
+Entry::findNonce(uint32_t nonce, const Face& face) const
{
- return m_nonceList.add(nonce);
+ // TODO should we ignore expired in/out records?
+
+ int dnw = DUPLICATE_NONCE_NONE;
+
+ for (InRecordCollection::const_iterator it = m_inRecords.begin();
+ it != m_inRecords.end(); ++it) {
+ if (it->getLastNonce() == nonce) {
+ if (it->getFace().get() == &face) {
+ dnw |= DUPLICATE_NONCE_IN_SAME;
+ }
+ else {
+ dnw |= DUPLICATE_NONCE_IN_OTHER;
+ }
+ }
+ }
+
+ for (OutRecordCollection::const_iterator it = m_outRecords.begin();
+ it != m_outRecords.end(); ++it) {
+ if (it->getLastNonce() == nonce) {
+ if (it->getFace().get() == &face) {
+ dnw |= DUPLICATE_NONCE_OUT_SAME;
+ }
+ else {
+ dnw |= DUPLICATE_NONCE_OUT_OTHER;
+ }
+ }
+ }
+
+ return dnw;
}
InRecordCollection::iterator
@@ -170,7 +198,6 @@
}
it->update(interest);
- m_nonceList.add(interest.getNonce());
return it;
}
diff --git a/daemon/table/pit-entry.hpp b/daemon/table/pit-entry.hpp
index 420bb29..5a691de 100644
--- a/daemon/table/pit-entry.hpp
+++ b/daemon/table/pit-entry.hpp
@@ -26,7 +26,6 @@
#ifndef NFD_DAEMON_TABLE_PIT_ENTRY_HPP
#define NFD_DAEMON_TABLE_PIT_ENTRY_HPP
-#include "pit-nonce-list.hpp"
#include "pit-in-record.hpp"
#include "pit-out-record.hpp"
#include "core/scheduler.hpp"
@@ -49,6 +48,20 @@
*/
typedef std::list<OutRecord> OutRecordCollection;
+/** \brief indicates where duplicate Nonces are found
+ */
+enum DuplicateNonceWhere {
+ DUPLICATE_NONCE_NONE = 0,
+ /// in-record of same face
+ DUPLICATE_NONCE_IN_SAME = (1 << 0),
+ /// in-record of other face
+ DUPLICATE_NONCE_IN_OTHER = (1 << 1),
+ /// out-record of same face
+ DUPLICATE_NONCE_OUT_SAME = (1 << 2),
+ /// out-record of other face
+ DUPLICATE_NONCE_OUT_OTHER = (1 << 3)
+};
+
/** \brief represents a PIT entry
*/
class Entry : public StrategyInfoHost, noncopyable
@@ -86,12 +99,11 @@
bool
violatesScope(const Face& face) const;
- /** \brief records a nonce
- *
- * \return true if nonce is new; false if nonce is seen before
+ /** \brief finds where a duplicate Nonce appears
+ * \return OR'ed DuplicateNonceWhere
*/
- bool
- addNonce(uint32_t nonce);
+ int
+ findNonce(uint32_t nonce, const Face& face) const;
public: // InRecord
const InRecordCollection&
@@ -156,7 +168,6 @@
EventId m_stragglerTimer;
private:
- pit::NonceList m_nonceList;
shared_ptr<const Interest> m_interest;
InRecordCollection m_inRecords;
OutRecordCollection m_outRecords;
diff --git a/daemon/table/pit-nonce-list.cpp b/daemon/table/pit-nonce-list.cpp
deleted file mode 100644
index 02502ab..0000000
--- a/daemon/table/pit-nonce-list.cpp
+++ /dev/null
@@ -1,66 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis
- *
- * This file is part of NFD (Named Data Networking Forwarding Daemon).
- * See AUTHORS.md for complete list of NFD authors and contributors.
- *
- * NFD is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE. See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#include "pit-nonce-list.hpp"
-
-namespace nfd {
-namespace pit {
-
-// The NonceList has limited capacity to avoid memory explosion
-// if PIT entry is constantly refreshed (NFD Bug #1770).
-// Current implementation keeps nonces in a set to detect duplicates,
-// and a queue to evict the oldest nonce when capacity limit is reached.
-// A limitation is that a nonce first appeared at time 0 and duplicated at time 10
-// could be evicted before a nonce appeared only once at time 5;
-// this limitation should not affect normal operation.
-
-const size_t NonceList::CAPACITY = 256;
-
-NonceList::NonceList()
-{
-}
-
-bool
-NonceList::add(uint32_t nonce)
-{
- bool isNew = m_nonceSet.insert(nonce).second;
- if (!isNew)
- return false;
-
- m_nonceQueue.push(nonce);
- BOOST_ASSERT(m_nonceSet.size() == m_nonceQueue.size());
-
- if (m_nonceSet.size() > CAPACITY) {
- size_t nErased = m_nonceSet.erase(m_nonceQueue.front());
- BOOST_ASSERT(nErased == 1);
- m_nonceQueue.pop();
- BOOST_ASSERT(m_nonceSet.size() == m_nonceQueue.size());
- BOOST_ASSERT(m_nonceSet.size() <= CAPACITY);
- }
- return true;
-}
-
-} // namespace pit
-} // namespace nfd
diff --git a/daemon/table/pit-nonce-list.hpp b/daemon/table/pit-nonce-list.hpp
deleted file mode 100644
index 393ae34..0000000
--- a/daemon/table/pit-nonce-list.hpp
+++ /dev/null
@@ -1,64 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014, Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology,
- * The University of Memphis
- *
- * This file is part of NFD (Named Data Networking Forwarding Daemon).
- * See AUTHORS.md for complete list of NFD authors and contributors.
- *
- * NFD is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE. See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef NFD_DAEMON_TABLE_PIT_NONCE_LIST_HPP
-#define NFD_DAEMON_TABLE_PIT_NONCE_LIST_HPP
-
-#include "common.hpp"
-
-namespace nfd {
-namespace pit {
-
-/** \brief represents a Nonce list
- */
-class NonceList : noncopyable
-{
-public:
- NonceList();
-
- /** \brief records a nonce
- * \return true if nonce is new; false if nonce is seen before
- */
- bool
- add(uint32_t nonce);
-
- size_t
- size() const
- {
- return m_nonceSet.size();
- }
-
-public:
- static const size_t CAPACITY;
-
-private:
- std::set<uint32_t> m_nonceSet;
- std::queue<uint32_t> m_nonceQueue;
-};
-
-} // namespace pit
-} // namespace nfd
-
-#endif // NFD_DAEMON_TABLE_PIT_NONCE_LIST_HPP