table: Fix segfault during Fib::removeNextHopFromAllEntries
Change-Id: I905a3c0da2f2a9197942cfeba7fd698b779e6e4a
Refs: #1816
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 3672b66..660ae72 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -144,8 +144,11 @@
Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
{
for (NameTree::const_iterator it = m_nameTree.fullEnumerate(
- &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); ++it) {
+ &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end();) {
shared_ptr<fib::Entry> entry = it->getFibEntry();
+
+ ++it; // need to be advance before `erase`, otherwise the iterator can be invalidated
+
entry->removeNextHop(face);
if (!entry->hasNextHops()) {
this->erase(*entry);
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 027f852..0832a31 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -86,6 +86,7 @@
~NameTree();
+public: // information
/**
* \brief Get the number of occupied entries in the Name Tree
*/
@@ -101,6 +102,13 @@
getNBuckets() const;
/**
+ * \brief Dump all the information stored in the Name Tree for debugging.
+ */
+ void
+ dump(std::ostream& output) const;
+
+public: // mutation
+ /**
* \brief Look for the Name Tree Entry that contains this name prefix.
* \details Starts from the shortest name prefix, and then increase the
* number of name components by one each time. All non-existing Name Tree
@@ -108,28 +116,48 @@
* \param prefix The querying name prefix.
* \return The pointer to the Name Tree Entry that contains this full name
* prefix.
+ * \note Existing iterators are unaffected.
*/
shared_ptr<name_tree::Entry>
lookup(const Name& prefix);
/**
- * \brief Exact match lookup for the given name prefix.
- * \return a null shared_ptr if this prefix is not found;
- * otherwise return the Name Tree Entry address
- */
- shared_ptr<name_tree::Entry>
- findExactMatch(const Name& prefix) const;
-
- /**
* \brief Delete a Name Tree Entry if this entry is empty.
* \param entry The entry to be deleted if empty.
* \note This function must be called after a table entry is detached from Name Tree
* entry. The function deletes a Name Tree entry if nothing is attached to it and
* it has no children, then repeats the same process on its ancestors.
+ * \note Existing iterators, except those pointing to deleted entries, are unaffected.
*/
bool
eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
+public: // shortcut access
+ /// get NameTree entry from attached FIB entry
+ shared_ptr<name_tree::Entry>
+ get(const fib::Entry& fibEntry) const;
+
+ /// get NameTree entry from attached PIT entry
+ shared_ptr<name_tree::Entry>
+ get(const pit::Entry& pitEntry) const;
+
+ /// get NameTree entry from attached Measurements entry
+ shared_ptr<name_tree::Entry>
+ get(const measurements::Entry& measurementsEntry) const;
+
+ /// get NameTree entry from attached StrategyChoice entry
+ shared_ptr<name_tree::Entry>
+ get(const strategy_choice::Entry& strategyChoiceEntry) const;
+
+public: // matching
+ /**
+ * \brief Exact match lookup for the given name prefix.
+ * \return a null shared_ptr if this prefix is not found;
+ * otherwise return the Name Tree Entry address
+ */
+ shared_ptr<name_tree::Entry>
+ findExactMatch(const Name& prefix) const;
+
/**
* \brief Longest prefix matching for the given name
* \details Starts from the full name string, reduce the number of name component
@@ -146,15 +174,13 @@
name_tree::AnyEntry()) const;
/**
- * \brief Resize the hash table size when its load factor reaches a threshold.
- * \details As we are currently using a hand-written hash table implementation
- * for the Name Tree, the hash table resize() function should be kept in the
- * name-tree.hpp file.
- * \param newNBuckets The number of buckets for the new hash table.
+ * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
*/
- void
- resize(size_t newNBuckets);
+ const_iterator
+ findAllMatches(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
+public: // enumeration
/**
* \brief Enumerate all the name prefixes stored in the Name Tree.
*/
@@ -169,39 +195,13 @@
const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
name_tree::AnyEntrySubTree()) const;
- /**
- * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
- */
- const_iterator
- findAllMatches(const Name& prefix,
- const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
-
- /**
- * \brief Dump all the information stored in the Name Tree for debugging.
- */
- void
- dump(std::ostream& output) const;
-
- shared_ptr<name_tree::Entry>
- get(const fib::Entry& fibEntry) const;
-
- shared_ptr<name_tree::Entry>
- get(const pit::Entry& pitEntry) const;
-
- shared_ptr<name_tree::Entry>
- get(const measurements::Entry& measurementsEntry) const;
-
- shared_ptr<name_tree::Entry>
- get(const strategy_choice::Entry& strategeChoiceEntry) const;
-
const_iterator
begin() const;
const_iterator
end() const;
- enum IteratorType
- {
+ enum IteratorType {
FULL_ENUMERATE_TYPE,
PARTIAL_ENUMERATE_TYPE,
FIND_ALL_MATCHES_TYPE
@@ -249,6 +249,17 @@
};
private:
+ /**
+ * \brief Resize the hash table size when its load factor reaches a threshold.
+ * \details As we are currently using a hand-written hash table implementation
+ * for the Name Tree, the hash table resize() function should be kept in the
+ * name-tree.hpp file.
+ * \param newNBuckets The number of buckets for the new hash table.
+ */
+ void
+ resize(size_t newNBuckets);
+
+private:
size_t m_nItems; // Number of items being stored
size_t m_nBuckets; // Number of hash buckets
size_t m_minNBuckets; // Minimum number of hash buckets
@@ -309,9 +320,9 @@
}
inline shared_ptr<name_tree::Entry>
-NameTree::get(const strategy_choice::Entry& strategeChoiceEntry) const
+NameTree::get(const strategy_choice::Entry& strategyChoiceEntry) const
{
- return strategeChoiceEntry.m_nameTreeEntry;
+ return strategyChoiceEntry.m_nameTreeEntry;
}
inline NameTree::const_iterator
diff --git a/tests/daemon/table/fib.cpp b/tests/daemon/table/fib.cpp
index d40f15d..35fcd3e 100644
--- a/tests/daemon/table/fib.cpp
+++ b/tests/daemon/table/fib.cpp
@@ -223,9 +223,36 @@
// {'/A':[1,2], '/B':[1]}
BOOST_CHECK_EQUAL(fib.size(), 2);
+ insertRes = fib.insert("/C");
+ insertRes.first->addNextHop(face2, 1);
+ // {'/A':[1,2], '/B':[1], '/C':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 3);
+
+ insertRes = fib.insert("/B/1");
+ insertRes.first->addNextHop(face1, 0);
+ // {'/A':[1,2], '/B':[1], '/B/1':[1], '/C':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 4);
+
+ insertRes = fib.insert("/B/1/2");
+ insertRes.first->addNextHop(face1, 0);
+ // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/C':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 5);
+
+ insertRes = fib.insert("/B/1/2/3");
+ insertRes.first->addNextHop(face1, 0);
+ // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/B/1/3':[1], '/C':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 6);
+
+ insertRes = fib.insert("/B/1/2/3/4");
+ insertRes.first->addNextHop(face1, 0);
+ // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/B/1/2/3':[1], '/B/1/2/3/4':[1], '/C':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 7);
+
+ /////////////
+
fib.removeNextHopFromAllEntries(face1);
- // {'/A':[2]}
- BOOST_CHECK_EQUAL(fib.size(), 1);
+ // {'/A':[2], '/C':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 2);
entry = fib.findLongestPrefixMatch(nameA);
BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
diff --git a/tests/daemon/table/name-tree.cpp b/tests/daemon/table/name-tree.cpp
index 0a6f986..cd1d894 100644
--- a/tests/daemon/table/name-tree.cpp
+++ b/tests/daemon/table/name-tree.cpp
@@ -109,7 +109,7 @@
BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 0);
}
-BOOST_AUTO_TEST_CASE(NameTreeBasic)
+BOOST_AUTO_TEST_CASE(Basic)
{
size_t nBuckets = 16;
NameTree nt(nBuckets);
@@ -239,7 +239,7 @@
BOOST_CHECK_EQUAL(nt.size(), 8);
}
-BOOST_AUTO_TEST_CASE(NameTreeIteratorFullEnumerate)
+BOOST_AUTO_TEST_CASE(IteratorFullEnumerate)
{
size_t nBuckets = 1024;
NameTree nt(nBuckets);
@@ -387,7 +387,7 @@
return std::make_pair(first, second);
}
-BOOST_AUTO_TEST_CASE(NameTreeIteratorPartialEnumerate)
+BOOST_AUTO_TEST_CASE(IteratorPartialEnumerate)
{
typedef NameTree::const_iterator const_iterator;
@@ -467,7 +467,8 @@
// No NameA
// No SubTree from NameAB
- const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
+ const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA,
+ &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
hasA = false;
hasAB = false;
hasAB1 = false;
@@ -516,7 +517,8 @@
// No NameA
// No SubTree from NameAC
- const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
+ const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA,
+ &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
hasA = false;
hasAB = false;
hasAB1 = false;
@@ -564,7 +566,8 @@
BOOST_CHECK_EQUAL(counter, 4);
// No Subtree from NameA
- const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoSubNameA);
+ const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA,
+ &predicate_NameTreeEntry_NoSubNameA);
hasA = false;
hasAB = false;
@@ -648,7 +651,8 @@
bool hasF = false;
counter = 0;
- const_iterator itExample = nameTreeExample.partialEnumerate(nameA, &predicate_NameTreeEntry_Example);
+ const_iterator itExample = nameTreeExample.partialEnumerate(nameA,
+ &predicate_NameTreeEntry_Example);
for (; itExample != nameTreeExample.end(); itExample++)
{
@@ -688,7 +692,7 @@
}
-BOOST_AUTO_TEST_CASE(NameTreeIteratorFindAllMatches)
+BOOST_AUTO_TEST_CASE(IteratorFindAllMatches)
{
size_t nBuckets = 16;
NameTree nt(nBuckets);
@@ -780,7 +784,7 @@
BOOST_CHECK_EQUAL(counter, 7);
}
-BOOST_AUTO_TEST_CASE(NameTreeHashTableResizeShrink)
+BOOST_AUTO_TEST_CASE(HashTableResizeShrink)
{
size_t nBuckets = 16;
NameTree nameTree(nBuckets);
@@ -796,6 +800,63 @@
BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 16);
}
+// .lookup should not invalidate iterator
+BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterLookup)
+{
+ NameTree nt;
+ nt.lookup("/A/B/C");
+ nt.lookup("/E");
+
+ Name nameB("/A/B");
+ std::set<Name> seenNames;
+ for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
+ BOOST_CHECK(seenNames.insert(it->getPrefix()).second);
+ if (it->getPrefix() == nameB) {
+ nt.lookup("/D");
+ }
+ }
+
+ BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/E"), 1);
+
+ seenNames.erase("/D"); // /D may or may not appear
+ BOOST_CHECK(seenNames.size() == 5);
+}
+
+// .eraseEntryIfEmpty should not invalidate iterator
+BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterErase)
+{
+ NameTree nt;
+ nt.lookup("/A/B/C");
+ nt.lookup("/A/D/E");
+ nt.lookup("/A/F/G");
+ nt.lookup("/H");
+
+ Name nameD("/A/D");
+ std::set<Name> seenNames;
+ for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
+ BOOST_CHECK(seenNames.insert(it->getPrefix()).second);
+ if (it->getPrefix() == nameD) {
+ nt.eraseEntryIfEmpty(nt.findExactMatch("/A/F/G")); // /A/F/G and /A/F are erased
+ }
+ }
+
+ BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A/D"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/A/D/E"), 1);
+ BOOST_CHECK_EQUAL(seenNames.count("/H"), 1);
+
+ seenNames.erase("/A/F"); // /A/F may or may not appear
+ seenNames.erase("/A/F/G"); // /A/F/G may or may not appear
+ BOOST_CHECK(seenNames.size() == 7);
+}
+
BOOST_AUTO_TEST_SUITE_END()
} // namespace tests