fw: use dead Nonce list in pipelines

refs #1953

Change-Id: I0faef2a985b03fe96387c2e0181588713550b9ce
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 1b677be..d8bc19f 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -74,9 +74,11 @@
   // PIT insert
   shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
 
-  // detect loop and record Nonce
-  bool isLoop = ! pitEntry->addNonce(interest.getNonce());
-  if (isLoop) {
+  // detect duplicate Nonce
+  int dnw = pitEntry->findNonce(interest.getNonce(), inFace);
+  bool hasDuplicateNonce = (dnw != pit::DUPLICATE_NONCE_NONE) ||
+                           m_deadNonceList.has(interest.getName(), interest.getNonce());
+  if (hasDuplicateNonce) {
     // goto Interest loop pipeline
     this->onInterestLoop(inFace, interest, pitEntry);
     return;
@@ -96,7 +98,7 @@
       // XXX should we lookup PIT for other Interests that also match csMatch?
 
       // set PIT straggler timer
-      this->setStragglerTimer(pitEntry);
+      this->setStragglerTimer(pitEntry, true, csMatch->getFreshnessPeriod());
 
       // goto outgoing Data pipeline
       this->onOutgoingData(*csMatch, inFace);
@@ -208,7 +210,7 @@
   this->cancelUnsatisfyAndStragglerTimer(pitEntry);
 
   // set PIT straggler timer
-  this->setStragglerTimer(pitEntry);
+  this->setStragglerTimer(pitEntry, false);
 }
 
 void
@@ -220,6 +222,20 @@
   this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeExpirePendingInterest, _1,
                                           pitEntry));
 
+  // goto Interest Finalize pipeline
+  this->onInterestFinalize(pitEntry, false);
+}
+
+void
+Forwarder::onInterestFinalize(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+                              const time::milliseconds& dataFreshnessPeriod)
+{
+  NFD_LOG_DEBUG("onInterestFinalize interest=" << pitEntry->getName() <<
+                (isSatisfied ? " satisfied" : " unsatisfied"));
+
+  // Dead Nonce List insert if necessary
+  this->insertDeadNonceList(*pitEntry, isSatisfied, dataFreshnessPeriod, 0);
+
   // PIT delete
   this->cancelUnsatisfyAndStragglerTimer(pitEntry);
   m_pit.erase(pitEntry);
@@ -277,12 +293,15 @@
     this->dispatchToStrategy(pitEntry, bind(&Strategy::beforeSatisfyInterest, _1,
                                             pitEntry, cref(inFace), cref(data)));
 
+    // Dead Nonce List insert if necessary (for OutRecord of inFace)
+    this->insertDeadNonceList(*pitEntry, true, data.getFreshnessPeriod(), &inFace);
+
     // mark PIT satisfied
     pitEntry->deleteInRecords();
     pitEntry->deleteOutRecord(inFace.shared_from_this());
 
     // set PIT straggler timer
-    this->setStragglerTimer(pitEntry);
+    this->setStragglerTimer(pitEntry, true, data.getFreshnessPeriod());
   }
 
   // foreach pending downstream
@@ -364,13 +383,14 @@
 }
 
 void
-Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry)
+Forwarder::setStragglerTimer(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+                             const time::milliseconds& dataFreshnessPeriod)
 {
   time::nanoseconds stragglerTime = time::milliseconds(100);
 
   scheduler::cancel(pitEntry->m_stragglerTimer);
   pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
-    bind(&Pit::erase, &m_pit, pitEntry));
+    bind(&Forwarder::onInterestFinalize, this, pitEntry, isSatisfied, dataFreshnessPeriod));
 }
 
 void
@@ -380,4 +400,49 @@
   scheduler::cancel(pitEntry->m_stragglerTimer);
 }
 
+static inline void
+insertNonceToDnl(DeadNonceList& dnl, const pit::Entry& pitEntry,
+                 const pit::OutRecord& outRecord)
+{
+  dnl.add(pitEntry.getName(), outRecord.getLastNonce());
+}
+
+void
+Forwarder::insertDeadNonceList(pit::Entry& pitEntry, bool isSatisfied,
+                               const time::milliseconds& dataFreshnessPeriod,
+                               Face* upstream)
+{
+  // need Dead Nonce List insert?
+  bool needDnl = false;
+  if (isSatisfied) {
+    bool hasFreshnessPeriod = dataFreshnessPeriod >= time::milliseconds::zero();
+    // Data never becomes stale if it doesn't have FreshnessPeriod field
+    needDnl = static_cast<bool>(pitEntry.getInterest().getMustBeFresh()) &&
+              (hasFreshnessPeriod && dataFreshnessPeriod < m_deadNonceList.getLifetime());
+  }
+  else {
+    needDnl = true;
+  }
+
+  if (!needDnl) {
+    return;
+  }
+
+  // Dead Nonce List insert
+  if (upstream == 0) {
+    // insert all outgoing Nonces
+    const pit::OutRecordCollection& outRecords = pitEntry.getOutRecords();
+    std::for_each(outRecords.begin(), outRecords.end(),
+                  bind(&insertNonceToDnl, ref(m_deadNonceList), cref(pitEntry), _1));
+  }
+  else {
+    // insert outgoing Nonce of a specific face
+    pit::OutRecordCollection::const_iterator outRecord =
+      pitEntry.getOutRecord(upstream->shared_from_this());
+    if (outRecord != pitEntry.getOutRecords().end()) {
+      m_deadNonceList.add(pitEntry.getName(), outRecord->getLastNonce());
+    }
+  }
+}
+
 } // namespace nfd
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 8c5ed79..a753f15 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -1,11 +1,12 @@
 /* -*- 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
+ * 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.
@@ -20,7 +21,7 @@
  *
  * 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_FW_FORWARDER_HPP
 #define NFD_DAEMON_FW_FORWARDER_HPP
@@ -34,6 +35,7 @@
 #include "table/cs.hpp"
 #include "table/measurements.hpp"
 #include "table/strategy-choice.hpp"
+#include "table/dead-nonce-list.hpp"
 
 namespace nfd {
 
@@ -99,6 +101,9 @@
   StrategyChoice&
   getStrategyChoice();
 
+  DeadNonceList&
+  getDeadNonceList();
+
 PUBLIC_WITH_TESTS_ELSE_PRIVATE: // pipelines
   /** \brief incoming Interest pipeline
    */
@@ -127,6 +132,14 @@
   VIRTUAL_WITH_TESTS void
   onInterestUnsatisfied(shared_ptr<pit::Entry> pitEntry);
 
+  /** \brief Interest finalize pipeline
+   *  \param isSatisfied whether the Interest has been satisfied
+   *  \param dataFreshnessPeriod FreshnessPeriod of satisfying Data
+   */
+  VIRTUAL_WITH_TESTS void
+  onInterestFinalize(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+                     const time::milliseconds& dataFreshnessPeriod = time::milliseconds(-1));
+
   /** \brief incoming Data pipeline
    */
   VIRTUAL_WITH_TESTS void
@@ -147,11 +160,21 @@
   setUnsatisfyTimer(shared_ptr<pit::Entry> pitEntry);
 
   VIRTUAL_WITH_TESTS void
-  setStragglerTimer(shared_ptr<pit::Entry> pitEntry);
+  setStragglerTimer(shared_ptr<pit::Entry> pitEntry, bool isSatisfied,
+                    const time::milliseconds& dataFreshnessPeriod = time::milliseconds(-1));
 
   VIRTUAL_WITH_TESTS void
   cancelUnsatisfyAndStragglerTimer(shared_ptr<pit::Entry> pitEntry);
 
+  /** \brief insert Nonce to Dead Nonce List if necessary
+   *  \param upstream if null, insert Nonces from all OutRecords;
+   *                  if not null, insert Nonce only on the OutRecord of this face
+   */
+  VIRTUAL_WITH_TESTS void
+  insertDeadNonceList(pit::Entry& pitEntry, bool isSatisfied,
+                      const time::milliseconds& dataFreshnessPeriod,
+                      Face* upstream);
+
   /// call trigger (method) on the effective strategy of pitEntry
 #ifdef WITH_TESTS
   virtual void
@@ -174,6 +197,7 @@
   Cs             m_cs;
   Measurements   m_measurements;
   StrategyChoice m_strategyChoice;
+  DeadNonceList  m_deadNonceList;
 
   static const Name LOCALHOST_NAME;
 
@@ -253,6 +277,12 @@
   return m_strategyChoice;
 }
 
+inline DeadNonceList&
+Forwarder::getDeadNonceList()
+{
+  return m_deadNonceList;
+}
+
 #ifdef WITH_TESTS
 inline void
 Forwarder::dispatchToStrategy(shared_ptr<pit::Entry> pitEntry, function<void(fw::Strategy*)> trigger)
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
diff --git a/tests/daemon/fw/forwarder.cpp b/tests/daemon/fw/forwarder.cpp
index 6856d8f..930de00 100644
--- a/tests/daemon/fw/forwarder.cpp
+++ b/tests/daemon/fw/forwarder.cpp
@@ -424,6 +424,38 @@
   BOOST_CHECK_EQUAL(face4->m_sentDatas.size(), 1);
 }
 
+static inline void
+delayedInterestLoop(const time::nanoseconds& delay, DummyFace& face, const Interest& interest)
+{
+  scheduler::schedule(delay, bind(&DummyFace::receiveInterest, &face, cref(interest)));
+}
+
+BOOST_AUTO_TEST_CASE(Bug1953) // persistent loop with short InterestLifetime
+{
+  LimitedIo limitedIo;
+  Forwarder forwarder;
+  shared_ptr<DummyFace> face1 = make_shared<DummyFace>();
+  shared_ptr<DummyFace> face2 = make_shared<DummyFace>();
+  forwarder.addFace(face1);
+  forwarder.addFace(face2);
+
+  // cause an Interest sent out of face2 to loop back into face1 after a delay
+  face2->onSendInterest += bind(&delayedInterestLoop, time::milliseconds(170), ref(*face1), _1);
+
+  Fib& fib = forwarder.getFib();
+  shared_ptr<fib::Entry> fibEntry = fib.insert(Name("ndn:/A")).first;
+  fibEntry->addNextHop(face2, 0);
+
+  shared_ptr<Interest> interest = makeInterest("ndn:/A/1");
+  interest->setNonce(82101183);
+  interest->setInterestLifetime(time::milliseconds(50));
+  face1->receiveInterest(*interest);
+
+  limitedIo.defer(time::milliseconds(1000));
+
+  BOOST_CHECK_EQUAL(face2->m_sentInterests.size(), 1);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } // namespace tests
diff --git a/tests/daemon/table/dead-nonce-list.cpp b/tests/daemon/table/dead-nonce-list.cpp
index c8a59bb..970d537 100644
--- a/tests/daemon/table/dead-nonce-list.cpp
+++ b/tests/daemon/table/dead-nonce-list.cpp
@@ -41,14 +41,21 @@
   const uint32_t nonce2 = 0x1f46372b;
 
   DeadNonceList dnl;
-
+  BOOST_CHECK_EQUAL(dnl.size(), 0);
   BOOST_CHECK_EQUAL(dnl.has(nameA, nonce1), false);
+
   dnl.add(nameA, nonce1);
+  BOOST_CHECK_EQUAL(dnl.size(), 1);
   BOOST_CHECK_EQUAL(dnl.has(nameA, nonce1), true);
   BOOST_CHECK_EQUAL(dnl.has(nameA, nonce2), false);
   BOOST_CHECK_EQUAL(dnl.has(nameB, nonce1), false);
 }
 
+BOOST_AUTO_TEST_CASE(MinLifetime)
+{
+  BOOST_CHECK_THROW(DeadNonceList dnl(time::milliseconds::zero()), std::invalid_argument);
+}
+
 /// A Fixture that periodically inserts Nonces
 class PeriodicalInsertionFixture : public BaseFixture
 {
@@ -100,6 +107,8 @@
 
 BOOST_FIXTURE_TEST_CASE(Lifetime, PeriodicalInsertionFixture)
 {
+  BOOST_CHECK_EQUAL(dnl.getLifetime(), LIFETIME);
+
   LimitedIo limitedIo;
 
   const int RATE = DeadNonceList::INITIAL_CAPACITY / 2;
diff --git a/tests/daemon/table/pit.cpp b/tests/daemon/table/pit.cpp
index 566421f..8e73a12 100644
--- a/tests/daemon/table/pit.cpp
+++ b/tests/daemon/table/pit.cpp
@@ -33,27 +33,6 @@
 
 BOOST_FIXTURE_TEST_SUITE(TablePit, BaseFixture)
 
-BOOST_AUTO_TEST_CASE(NonceList)
-{
-  BOOST_REQUIRE_GE(pit::NonceList::CAPACITY, 32);
-  BOOST_REQUIRE_LE(pit::NonceList::CAPACITY, 4096);
-
-  pit::NonceList nl;
-  for (uint32_t nonce = 0; nonce < static_cast<uint32_t>(pit::NonceList::CAPACITY); ++nonce) {
-    BOOST_CHECK_EQUAL(nl.add(nonce), true);
-  }
-  BOOST_CHECK_EQUAL(nl.size(), pit::NonceList::CAPACITY);
-
-  BOOST_CHECK_EQUAL(nl.add(32), false);
-  BOOST_CHECK_EQUAL(nl.size(), pit::NonceList::CAPACITY);
-
-  BOOST_CHECK_EQUAL(nl.add(4096), true);
-  BOOST_CHECK_EQUAL(nl.size(), pit::NonceList::CAPACITY);
-
-  BOOST_CHECK_EQUAL(nl.add(0), true);// 0 is evicted
-  BOOST_CHECK_EQUAL(nl.size(), pit::NonceList::CAPACITY);
-}
-
 BOOST_AUTO_TEST_CASE(EntryInOutRecords)
 {
   shared_ptr<Face> face1 = make_shared<DummyFace>();
@@ -171,20 +150,68 @@
 
 BOOST_AUTO_TEST_CASE(EntryNonce)
 {
+  shared_ptr<Face> face1 = make_shared<DummyFace>();
+  shared_ptr<Face> face2 = make_shared<DummyFace>();
+
   shared_ptr<Interest> interest = makeInterest("ndn:/qtCQ7I1c");
+  interest->setNonce(25559);
 
-  pit::Entry entry(*interest);
+  pit::Entry entry0(*interest);
+  BOOST_CHECK_EQUAL(entry0.findNonce(25559, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry0.findNonce(25559, *face2), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry0.findNonce(19004, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry0.findNonce(19004, *face2), pit::DUPLICATE_NONCE_NONE);
 
-  BOOST_CHECK_EQUAL(entry.addNonce(25559), true);
-  BOOST_CHECK_EQUAL(entry.addNonce(25559), false);
-  BOOST_CHECK_EQUAL(entry.addNonce(19004), true);
-  BOOST_CHECK_EQUAL(entry.addNonce(19004), false);
+  pit::Entry entry1(*interest);
+  entry1.insertOrUpdateInRecord(face1, *interest);
+  BOOST_CHECK_EQUAL(entry1.findNonce(25559, *face1), pit::DUPLICATE_NONCE_IN_SAME);
+  BOOST_CHECK_EQUAL(entry1.findNonce(25559, *face2), pit::DUPLICATE_NONCE_IN_OTHER);
+  BOOST_CHECK_EQUAL(entry1.findNonce(19004, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry1.findNonce(19004, *face2), pit::DUPLICATE_NONCE_NONE);
+
+  pit::Entry entry2(*interest);
+  entry2.insertOrUpdateOutRecord(face1, *interest);
+  BOOST_CHECK_EQUAL(entry2.findNonce(25559, *face1), pit::DUPLICATE_NONCE_OUT_SAME);
+  BOOST_CHECK_EQUAL(entry2.findNonce(25559, *face2), pit::DUPLICATE_NONCE_OUT_OTHER);
+  BOOST_CHECK_EQUAL(entry2.findNonce(19004, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry2.findNonce(19004, *face2), pit::DUPLICATE_NONCE_NONE);
+
+  pit::Entry entry3(*interest);
+  entry3.insertOrUpdateInRecord(face1, *interest);
+  entry3.insertOrUpdateOutRecord(face1, *interest);
+  BOOST_CHECK_EQUAL(entry3.findNonce(25559, *face1),
+                    pit::DUPLICATE_NONCE_IN_SAME | pit::DUPLICATE_NONCE_OUT_SAME);
+  BOOST_CHECK_EQUAL(entry3.findNonce(25559, *face2),
+                    pit::DUPLICATE_NONCE_IN_OTHER | pit::DUPLICATE_NONCE_OUT_OTHER);
+  BOOST_CHECK_EQUAL(entry3.findNonce(19004, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry3.findNonce(19004, *face2), pit::DUPLICATE_NONCE_NONE);
+
+  pit::Entry entry4(*interest);
+  entry4.insertOrUpdateInRecord(face1, *interest);
+  entry4.insertOrUpdateInRecord(face2, *interest);
+  BOOST_CHECK_EQUAL(entry4.findNonce(25559, *face1),
+                    pit::DUPLICATE_NONCE_IN_SAME | pit::DUPLICATE_NONCE_IN_OTHER);
+  BOOST_CHECK_EQUAL(entry4.findNonce(25559, *face2),
+                    pit::DUPLICATE_NONCE_IN_SAME | pit::DUPLICATE_NONCE_IN_OTHER);
+  BOOST_CHECK_EQUAL(entry4.findNonce(19004, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry4.findNonce(19004, *face2), pit::DUPLICATE_NONCE_NONE);
+
+  pit::Entry entry5(*interest);
+  entry5.insertOrUpdateOutRecord(face1, *interest);
+  entry5.insertOrUpdateOutRecord(face2, *interest);
+  BOOST_CHECK_EQUAL(entry5.findNonce(25559, *face1),
+                    pit::DUPLICATE_NONCE_OUT_SAME | pit::DUPLICATE_NONCE_OUT_OTHER);
+  BOOST_CHECK_EQUAL(entry5.findNonce(25559, *face2),
+                    pit::DUPLICATE_NONCE_OUT_SAME | pit::DUPLICATE_NONCE_OUT_OTHER);
+  BOOST_CHECK_EQUAL(entry5.findNonce(19004, *face1), pit::DUPLICATE_NONCE_NONE);
+  BOOST_CHECK_EQUAL(entry5.findNonce(19004, *face2), pit::DUPLICATE_NONCE_NONE);
 }
 
 BOOST_AUTO_TEST_CASE(EntryLifetime)
 {
   shared_ptr<Interest> interest = makeInterest("ndn:/7oIEurbgy6");
-  BOOST_ASSERT(interest->getInterestLifetime() < time::milliseconds::zero()); // library uses -1 to indicate unset lifetime
+  // library uses -1 to indicate unset lifetime
+  BOOST_ASSERT(interest->getInterestLifetime() < time::milliseconds::zero());
 
   shared_ptr<Face> face = make_shared<DummyFace>();
   pit::Entry entry(*interest);