table: delete PIT in-record and out-record when face is destroyed
refs #3685
Change-Id: I3c20417c9a30db69c90c9d59a30af1529bc1f98e
diff --git a/daemon/table/cleanup.cpp b/daemon/table/cleanup.cpp
new file mode 100644
index 0000000..0ba0725
--- /dev/null
+++ b/daemon/table/cleanup.cpp
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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 "cleanup.hpp"
+
+namespace nfd {
+
+void
+cleanupOnFaceRemoval(NameTree& nt, Fib& fib, Pit& pit, const Face& face)
+{
+ std::multimap<size_t, weak_ptr<name_tree::Entry>> maybeEmptyNtes;
+
+ // visit FIB and PIT entries in one pass of NameTree enumeration
+ for (const name_tree::Entry& nte : nt) {
+ fib::Entry* fibEntry = nte.getFibEntry();
+ if (fibEntry != nullptr) {
+ fib.removeNextHop(*fibEntry, face);
+ }
+
+ for (const auto& pitEntry : nte.getPitEntries()) {
+ pit.deleteInOutRecords(pitEntry, face);
+ }
+
+ if (nte.getFibEntry() == nullptr && !nte.hasPitEntries()) {
+ maybeEmptyNtes.emplace(nte.getPrefix().size(), const_pointer_cast<name_tree::Entry>(nte.shared_from_this()));
+ }
+ }
+
+ // try to erase longer names first, so that children are erased before parent is checked
+ for (auto i = maybeEmptyNtes.rbegin(); i != maybeEmptyNtes.rend(); ++i) {
+ shared_ptr<name_tree::Entry> nte = i->second.lock();
+ // nte may have been erased when its last child is erased
+ if (nte != nullptr) {
+ nt.eraseEntryIfEmpty(nte);
+ }
+ }
+}
+
+} // namespace nfd
diff --git a/daemon/table/cleanup.hpp b/daemon/table/cleanup.hpp
new file mode 100644
index 0000000..3c84482
--- /dev/null
+++ b/daemon/table/cleanup.hpp
@@ -0,0 +1,52 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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_CLEANUP_HPP
+#define NFD_DAEMON_TABLE_CLEANUP_HPP
+
+#include "name-tree.hpp"
+#include "fib.hpp"
+#include "pit.hpp"
+
+namespace nfd {
+
+/** \brief cleanup tables when a face is destroyed
+ *
+ * This function enumerates the NameTree, calls Fib::removeNextHop for each FIB entry,
+ * calls Pit::deleteInOutRecords for each PIT entry, and finally
+ * deletes any name tree entries that have become empty.
+ *
+ * \note It's a design choice to let Fib and Pit classes decide what to do with each entry.
+ * This function is only responsible for implementing the enumeration procedure.
+ * The benefit of having this function instead of doing the enumeration in Fib and Pit
+ * classes is to perform both FIB and PIT cleanups in one pass of NameTree enumeration,
+ * so as to reduce performance overhead.
+ */
+void
+cleanupOnFaceRemoval(NameTree& nt, Fib& fib, Pit& pit, const Face& face);
+
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CLEANUP_HPP
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 2df3122..890bbbe 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -130,10 +130,14 @@
}
void
-Fib::erase(shared_ptr<name_tree::Entry> nte)
+Fib::erase(shared_ptr<name_tree::Entry> nte, bool canDeleteNte)
{
+ BOOST_ASSERT(nte != nullptr);
+
nte->setFibEntry(nullptr);
- m_nameTree.eraseEntryIfEmpty(nte);
+ if (canDeleteNte) {
+ m_nameTree.eraseEntryIfEmpty(nte);
+ }
--m_nItems;
}
@@ -151,28 +155,19 @@
{
shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
if (nte != nullptr) {
+ // don't try to erase s_emptyEntry
this->erase(nte);
}
}
void
-Fib::removeNextHopFromAllEntries(const Face& face)
+Fib::removeNextHop(Entry& entry, const Face& face)
{
- std::list<Entry*> toErase;
+ entry.removeNextHop(face);
- auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
- for (const name_tree::Entry& nte : enumerable) {
- Entry* entry = nte.getFibEntry();
- entry->removeNextHop(face);
- if (!entry->hasNextHops()) {
- toErase.push_back(entry);
- // entry needs to be erased, but we must wait until the enumeration ends,
- // because otherwise NameTree iterator would be invalidated
- }
- }
-
- for (Entry* entry : toErase) {
- this->erase(*entry);
+ if (!entry.hasNextHops()) {
+ shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
+ this->erase(nte, false);
}
}
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index bfe6684..df2bfeb 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -93,15 +93,10 @@
void
erase(const Entry& entry);
- /** \brief removes the NextHop record for face in all entries
- *
- * This is usually invoked when face is destroyed.
- * Removing the last NextHop in a FIB entry will erase the FIB entry.
- *
- * \todo change parameter type to Face&
+ /** \brief removes the NextHop record for face
*/
void
- removeNextHopFromAllEntries(const Face& face);
+ removeNextHop(Entry& entry, const Face& face);
public: // enumeration
class const_iterator;
@@ -158,7 +153,7 @@
findLongestPrefixMatch(shared_ptr<name_tree::Entry> nte) const;
void
- erase(shared_ptr<name_tree::Entry> nameTreeEntry);
+ erase(shared_ptr<name_tree::Entry> nte, bool canDeleteNte = true);
private:
NameTree& m_nameTree;
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 5db1ce2..57cbf53 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -124,17 +124,35 @@
}
void
-Pit::erase(shared_ptr<pit::Entry> pitEntry)
+Pit::erase(shared_ptr<pit::Entry> entry)
{
- shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.getEntry(*pitEntry);
- BOOST_ASSERT(nameTreeEntry != nullptr);
+ this->erase(entry, true);
+}
- nameTreeEntry->erasePitEntry(pitEntry);
- m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
+void
+Pit::erase(shared_ptr<pit::Entry> entry, bool canDeleteNte)
+{
+ shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(*entry);
+ BOOST_ASSERT(nte != nullptr);
+ nte->erasePitEntry(entry);
+ if (canDeleteNte) {
+ m_nameTree.eraseEntryIfEmpty(nte);
+ }
--m_nItems;
}
+void
+Pit::deleteInOutRecords(shared_ptr<pit::Entry> entry, const Face& face)
+{
+ BOOST_ASSERT(entry != nullptr);
+
+ entry->deleteInRecord(face);
+ entry->deleteOutRecord(face);
+
+ /// \todo decide whether to delete PIT entry if there's no more in/out-record left
+}
+
Pit::const_iterator
Pit::begin() const
{
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index cea528f..cbfac86 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -81,7 +81,12 @@
* \brief erases a PIT Entry
*/
void
- erase(shared_ptr<pit::Entry> pitEntry);
+ erase(shared_ptr<pit::Entry> entry);
+
+ /** \brief deletes in-record and out-record for face
+ */
+ void
+ deleteInOutRecords(shared_ptr<pit::Entry> entry, const Face& face);
public: // enumeration
class const_iterator;
@@ -140,6 +145,12 @@
};
private:
+ /**
+ * \brief erases a PIT Entry
+ */
+ void
+ erase(shared_ptr<pit::Entry> pitEntry, bool canDeleteNte);
+
/** \brief finds or inserts a PIT entry for Interest
* \param interest the Interest; must be created with make_shared if allowInsert
* \param allowInsert whether inserting new entry is allowed.