fw: fix and simplify enumeration logic in Forwarder::onNewNextHop()
Also remove Strategy::enableNewNextHopTrigger(). Strategies can already
opt-in by overriding afterNewNextHop(), there is no need for a separate
enablement flag.
Refs: #4931
Change-Id: Ifcbdbc7e954bd20d9969fd99882a2a9aebbc8fcc
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 671c536..8301014 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.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,
@@ -76,8 +76,8 @@
cleanupOnFaceRemoval(m_nameTree, m_fib, m_pit, face);
});
- m_fib.afterNewNextHop.connect([&] (const Name& prefix, const fib::NextHop& nextHop) {
- this->startProcessNewNextHop(prefix, nextHop);
+ m_fib.afterNewNextHop.connect([this] (const Name& prefix, const fib::NextHop& nextHop) {
+ this->onNewNextHop(prefix, nextHop);
});
m_strategyChoice.setDefaultStrategy(getDefaultStrategyName());
@@ -213,7 +213,7 @@
// dispatch to strategy: after incoming Interest
this->dispatchToStrategy(*pitEntry,
- [&] (fw::Strategy& strategy) {
+ [&] (auto& strategy) {
strategy.afterReceiveInterest(FaceEndpoint(ingress.face, 0), interest, pitEntry);
});
}
@@ -237,7 +237,7 @@
// dispatch to strategy: after Content Store hit
this->dispatchToStrategy(*pitEntry,
- [&] (fw::Strategy& strategy) { strategy.afterContentStoreHit(pitEntry, ingress, data); });
+ [&] (auto& strategy) { strategy.afterContentStoreHit(pitEntry, ingress, data); });
}
pit::OutRecord*
@@ -325,7 +325,7 @@
// trigger strategy: after receive Data
this->dispatchToStrategy(*pitEntry,
- [&] (fw::Strategy& strategy) { strategy.afterReceiveData(pitEntry, ingress, data); });
+ [&] (auto& strategy) { strategy.afterReceiveData(pitEntry, ingress, data); });
// mark PIT satisfied
pitEntry->isSatisfied = true;
@@ -358,7 +358,7 @@
// invoke PIT satisfy callback
this->dispatchToStrategy(*pitEntry,
- [&] (fw::Strategy& strategy) { strategy.beforeSatisfyInterest(pitEntry, ingress, data); });
+ [&] (auto& strategy) { strategy.beforeSatisfyInterest(pitEntry, ingress, data); });
// mark PIT satisfied
pitEntry->isSatisfied = true;
@@ -481,7 +481,7 @@
// trigger strategy: after receive NACK
this->dispatchToStrategy(*pitEntry,
- [&] (fw::Strategy& strategy) { strategy.afterReceiveNack(ingress, nack, pitEntry); });
+ [&] (auto& strategy) { strategy.afterReceiveNack(ingress, nack, pitEntry); });
}
bool
@@ -542,37 +542,21 @@
{
const auto affectedEntries = this->getNameTree().partialEnumerate(prefix,
[&] (const name_tree::Entry& nte) -> std::pair<bool, bool> {
- const fib::Entry* fibEntry = nte.getFibEntry();
- const fw::Strategy* strategy = nullptr;
- if (nte.getStrategyChoiceEntry() != nullptr) {
- strategy = &nte.getStrategyChoiceEntry()->getStrategy();
- }
- // current nte has buffered Interests but no fibEntry (except for the root nte) and the strategy
- // enables new nexthop behavior, we enumerate the current nte and keep visiting its children.
- if (nte.getName().size() == 0 ||
- (strategy != nullptr && strategy->wantNewNextHopTrigger() &&
- fibEntry == nullptr && nte.hasPitEntries())) {
- return {true, true};
- }
- // we don't need the current nte (no pitEntry or strategy doesn't support new nexthop), but
- // if the current nte has no fibEntry, it's still possible that its children are affected by
- // the new nexthop.
- else if (fibEntry == nullptr) {
- return {false, true};
- }
- // if the current nte has a fibEntry, we ignore the current nte and don't visit its
- // children because they are already covered by the current nte's fibEntry.
- else {
+ // we ignore an NTE and skip visiting its descendants if that NTE has an
+ // associated FIB entry (1st condition), since in that case the new nexthop
+ // won't affect any PIT entries anywhere in that subtree, *unless* this is
+ // the initial NTE from which the enumeration started (2nd condition), which
+ // must always be considered
+ if (nte.getFibEntry() != nullptr && nte.getName().size() > prefix.size()) {
return {false, false};
}
+ return {nte.hasPitEntries(), true};
});
for (const auto& nte : affectedEntries) {
for (const auto& pitEntry : nte.getPitEntries()) {
this->dispatchToStrategy(*pitEntry,
- [&] (fw::Strategy& strategy) {
- strategy.afterNewNextHop(nextHop, pitEntry);
- });
+ [&] (auto& strategy) { strategy.afterNewNextHop(nextHop, pitEntry); });
}
}
}
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 4bdd42a..aaef44c 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -107,16 +107,6 @@
this->onIncomingNack(ingress, nack);
}
- /** \brief start new nexthop processing
- * \param prefix the prefix of the FibEntry containing the new nexthop
- * \param nextHop the new NextHop
- */
- void
- startProcessNewNextHop(const Name& prefix, const fib::NextHop& nextHop)
- {
- this->onNewNextHop(prefix, nextHop);
- }
-
NameTree&
getNameTree()
{
diff --git a/daemon/fw/strategy.hpp b/daemon/fw/strategy.hpp
index 571d7d1..3c6536e 100644
--- a/daemon/fw/strategy.hpp
+++ b/daemon/fw/strategy.hpp
@@ -114,14 +114,6 @@
return m_name;
}
- /** \return Whether the afterNewNextHop trigger should be invoked for this strategy.
- */
- bool
- wantNewNextHopTrigger() const
- {
- return m_wantNewNextHopTrigger;
- }
-
public: // triggers
/** \brief Trigger after Interest is received
*
@@ -388,15 +380,6 @@
m_name = name;
}
-NFD_PUBLIC_WITH_TESTS_ELSE_PROTECTED: // setter
- /** \brief Set whether the afterNewNextHop trigger should be invoked for this strategy
- */
- void
- enableNewNextHopTrigger(bool enabled)
- {
- m_wantNewNextHopTrigger = enabled;
- }
-
private: // registry
typedef std::function<unique_ptr<Strategy>(Forwarder& forwarder, const Name& strategyName)> CreateFunc;
typedef std::map<Name, CreateFunc> Registry; // indexed by strategy name
@@ -421,8 +404,6 @@
Forwarder& m_forwarder;
MeasurementsAccessor m_measurements;
-
- bool m_wantNewNextHopTrigger = false;
};
} // namespace fw
diff --git a/tests/daemon/fw/forwarder.t.cpp b/tests/daemon/fw/forwarder.t.cpp
index 77db2c8..f3f7c63 100644
--- a/tests/daemon/fw/forwarder.t.cpp
+++ b/tests/daemon/fw/forwarder.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,
@@ -698,6 +698,96 @@
BOOST_CHECK_EQUAL(forwarder.getCounters().nUnsolicitedData, 1);
}
+BOOST_AUTO_TEST_CASE(NewNextHop)
+{
+ auto face1 = addFace();
+ auto face2 = addFace();
+ auto face3 = addFace();
+ auto face4 = addFace();
+
+ auto& strategy = choose<DummyStrategy>(forwarder, "/A", DummyStrategy::getStrategyName());
+
+ Fib& fib = forwarder.getFib();
+ Pit& pit = forwarder.getPit();
+
+ // fib: "/", "/A/B", "/A/B/C/D/E"
+ fib::Entry* entry = fib.insert("/").first;
+ fib.addOrUpdateNextHop(*entry, *face1, 100);
+ entry = fib.insert("/A/B").first;
+ fib.addOrUpdateNextHop(*entry, *face2, 0);
+ entry = fib.insert("/A/B/C/D/E").first;
+ fib.addOrUpdateNextHop(*entry, *face3, 0);
+
+ // pit: "/A", "/A/B/C", "/A/B/Z"
+ auto interest1 = makeInterest("/A");
+ auto pit1 = pit.insert(*interest1).first;
+ pit1->insertOrUpdateInRecord(*face3, *interest1);
+ auto interest2 = makeInterest("/A/B/C");
+ auto pit2 = pit.insert(*interest2).first;
+ pit2->insertOrUpdateInRecord(*face3, *interest2);
+ auto interest3 = makeInterest("/A/B/Z");
+ auto pit3 = pit.insert(*interest3).first;
+ pit3->insertOrUpdateInRecord(*face3, *interest3);
+
+ // new nexthop for "/"
+ entry = fib.insert("/").first;
+ fib.addOrUpdateNextHop(*entry, *face2, 50);
+
+ // /A --> triggered
+ // /A/B/C --> not triggered
+ // /A/B/Z --> not triggered
+ BOOST_TEST_REQUIRE(strategy.afterNewNextHopCalls.size() == 1);
+ BOOST_TEST(strategy.afterNewNextHopCalls[0] == "/A");
+ strategy.afterNewNextHopCalls.clear();
+
+ // new nexthop for "/A"
+ entry = fib.insert("/A").first;
+ fib.addOrUpdateNextHop(*entry, *face4, 50);
+
+ // /A --> triggered
+ // /A/B/C --> not triggered
+ // /A/B/Z --> not triggered
+ BOOST_TEST_REQUIRE(strategy.afterNewNextHopCalls.size() == 1);
+ BOOST_TEST(strategy.afterNewNextHopCalls[0] == "/A");
+ strategy.afterNewNextHopCalls.clear();
+
+ // new nexthop for "/A/B"
+ entry = fib.insert("/A/B").first;
+ fib.addOrUpdateNextHop(*entry, *face4, 0);
+
+ // /A --> not triggered
+ // /A/B/C --> triggered
+ // /A/B/Z --> triggered
+ BOOST_TEST_REQUIRE(strategy.afterNewNextHopCalls.size() == 2);
+ BOOST_TEST(strategy.afterNewNextHopCalls[0] == "/A/B/C");
+ BOOST_TEST(strategy.afterNewNextHopCalls[1] == "/A/B/Z");
+ strategy.afterNewNextHopCalls.clear();
+
+ // new nexthop for "/A/B/C/D"
+ entry = fib.insert("/A/B/C/D").first;
+ fib.addOrUpdateNextHop(*entry, *face1, 0);
+
+ // nothing triggered
+ BOOST_TEST(strategy.afterNewNextHopCalls.size() == 0);
+
+ // create a second pit entry for /A
+ auto interest4 = makeInterest("/A");
+ interest4->setMustBeFresh(true);
+ auto pit4 = pit.insert(*interest4).first;
+ pit4->insertOrUpdateInRecord(*face3, *interest4);
+
+ // new nexthop for "/A"
+ entry = fib.insert("/A").first;
+ fib.addOrUpdateNextHop(*entry, *face1, 0);
+
+ // /A --> triggered twice
+ // /A/B/C --> not triggered
+ // /A/B/Z --> not triggered
+ BOOST_TEST_REQUIRE(strategy.afterNewNextHopCalls.size() == 2);
+ BOOST_TEST(strategy.afterNewNextHopCalls[0] == "/A");
+ BOOST_TEST(strategy.afterNewNextHopCalls[1] == "/A");
+}
+
BOOST_AUTO_TEST_SUITE_END() // TestForwarder
BOOST_AUTO_TEST_SUITE_END() // Fw
diff --git a/tests/daemon/fw/strategy-newnexthop.t.cpp b/tests/daemon/fw/strategy-newnexthop.t.cpp
deleted file mode 100644
index 282e74f..0000000
--- a/tests/daemon/fw/strategy-newnexthop.t.cpp
+++ /dev/null
@@ -1,163 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2019, 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 "fw/forwarder.hpp"
-#include "common/global.hpp"
-
-#include "tests/test-common.hpp"
-#include "tests/daemon/global-io-fixture.hpp"
-#include "tests/daemon/face/dummy-face.hpp"
-#include "choose-strategy.hpp"
-#include "dummy-strategy.hpp"
-
-namespace nfd {
-namespace tests {
-
-class StrategyNewNextHopFixture : public GlobalIoTimeFixture
-{
-protected:
- template<typename ...Args>
- shared_ptr<DummyFace>
- addFace(Args&&... args)
- {
- auto face = make_shared<DummyFace>(std::forward<Args>(args)...);
- faceTable.add(face);
- return face;
- }
-
-protected:
- FaceTable faceTable;
- Forwarder forwarder{faceTable};
-};
-
-BOOST_AUTO_TEST_SUITE(Fw)
-BOOST_FIXTURE_TEST_SUITE(TestStrategyNewNextHop, StrategyNewNextHopFixture)
-
-BOOST_AUTO_TEST_CASE(AfterNewNextHop1)
-{
- auto face1 = addFace();
- auto face2 = addFace();
- auto face3 = addFace();
-
- DummyStrategy& strategy = choose<DummyStrategy>(forwarder, "/A", DummyStrategy::getStrategyName());
- StrategyChoice& sc = forwarder.getStrategyChoice();
- sc.insert(Name("/A/B"), strategy.getStrategyName());
- sc.insert(Name("/A/B/C"), strategy.getStrategyName());
-
- strategy.enableNewNextHopTrigger(true);
-
- Fib& fib = forwarder.getFib();
- Pit& pit = forwarder.getPit();
-
- // fib: "/", "/A/B"
- fib::Entry* entry = fib.insert("/").first;
- fib.addOrUpdateNextHop(*entry, *face1, 0);
- entry = fib.insert("/A/B").first;
- fib.addOrUpdateNextHop(*entry, *face1, 0);
-
- // pit: "/A", "/A/B/C"
- auto interest1 = makeInterest("/A");
- shared_ptr<pit::Entry> pit1 = pit.insert(*interest1).first;
- pit1->insertOrUpdateInRecord(*face3, *interest1);
- auto interest2 = makeInterest("/A/B/C");
- shared_ptr<pit::Entry> pit2 = pit.insert(*interest2).first;
- pit2->insertOrUpdateInRecord(*face3, *interest2);
- // new nexthop for "/"
- entry = fib.insert("/").first;
- fib.addOrUpdateNextHop(*entry, *face2, 0);
-
- // /A --> triggered, /A/B --> not triggered, /A/B/C --> not triggered
- BOOST_REQUIRE_EQUAL(strategy.afterNewNextHopCalls.size(), 1);
- BOOST_CHECK_EQUAL(strategy.afterNewNextHopCalls[0], Name("/A"));
-}
-
-BOOST_AUTO_TEST_CASE(AfterNewNextHop2)
-{
- auto face1 = addFace();
- auto face2 = addFace();
- auto face3 = addFace();
-
- DummyStrategy& strategy = choose<DummyStrategy>(forwarder, "/A", DummyStrategy::getStrategyName());
- StrategyChoice& sc = forwarder.getStrategyChoice();
- sc.insert(Name("/A/B"), strategy.getStrategyName());
- sc.insert(Name("/A/B/C"), strategy.getStrategyName());
-
- strategy.enableNewNextHopTrigger(true);
-
- Fib& fib = forwarder.getFib();
- Pit& pit = forwarder.getPit();
-
- // fib: "/", "/A/B"
- fib::Entry* entry = fib.insert("/").first;
- fib.addOrUpdateNextHop(*entry, *face1, 0);
- entry = fib.insert("/A/B").first;
- fib.addOrUpdateNextHop(*entry, *face1, 0);
-
- // pit: "/A", "/A/B/C"
- auto interest1 = makeInterest("/A");
- shared_ptr<pit::Entry> pit1 = pit.insert(*interest1).first;
- pit1->insertOrUpdateInRecord(*face3, *interest1);
- auto interest2 = makeInterest("/A/B");
- shared_ptr<pit::Entry> pit2 = pit.insert(*interest2).first;
- pit2->insertOrUpdateInRecord(*face3, *interest2);
- // new nexthop for "/"
- entry = fib.insert("/").first;
- fib.addOrUpdateNextHop(*entry, *face2, 0);
-
- // /A --> triggered, /A/B --> not triggered, /A/B/C --> not triggered
- BOOST_REQUIRE_EQUAL(strategy.afterNewNextHopCalls.size(), 1);
- BOOST_CHECK_EQUAL(strategy.afterNewNextHopCalls[0], Name("/A"));
-}
-
-BOOST_AUTO_TEST_CASE(DisableTrigger)
-{
- auto face1 = addFace();
- auto face2 = addFace();
- auto face3 = addFace();
-
- DummyStrategy& strategy = choose<DummyStrategy>(forwarder, "/A", DummyStrategy::getStrategyName());
- strategy.enableNewNextHopTrigger(false);
-
- Fib& fib = forwarder.getFib();
- Pit& pit = forwarder.getPit();
-
- fib::Entry* entry = fib.insert("/").first;
- fib.addOrUpdateNextHop(*entry, *face1, 0);
-
- auto interest1 = makeInterest("/A");
- shared_ptr<pit::Entry> pit1 = pit.insert(*interest1).first;
- pit1->insertOrUpdateInRecord(*face3, *interest1);
- // new nexthop for "/A"
- entry = fib.insert("/A").first;
- fib.addOrUpdateNextHop(*entry, *face2, 0);
-
- BOOST_CHECK_EQUAL(strategy.afterNewNextHopCalls.size(), 0);
-}
-
-BOOST_AUTO_TEST_SUITE_END() // TestStrategyNewNextHop
-BOOST_AUTO_TEST_SUITE_END() // Fw
-
-} // namespace tests
-} // namespace nfd