Name prefix table entries keep pointers instead of keeping a copy of the object for routing table entries.
refs: #2863
Change-Id: I3271c9f96dfc8721a0ca7c900542c6ddb0b321ac
diff --git a/src/route/name-prefix-table.cpp b/src/route/name-prefix-table.cpp
index 5c18b77..e743276 100644
--- a/src/route/name-prefix-table.cpp
+++ b/src/route/name-prefix-table.cpp
@@ -33,112 +33,90 @@
INIT_LOGGER("NamePrefixTable");
-static bool
+bool
npteCompare(NamePrefixTableEntry& npte, const ndn::Name& name)
{
return npte.getNamePrefix() == name;
}
void
-NamePrefixTable::addEntry(const ndn::Name& name, RoutingTableEntry& rte)
-{
- // Check if the advertised name prefix is in the table already.
- NptEntryList::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- bind(&npteCompare, _1, name));
- // If not, create a new entry and add it.
- if (it == m_table.end()) {
- _LOG_TRACE("Adding origin: " << rte.getDestination() << " to new name prefix: " << name);
-
- NamePrefixTableEntry entry(name);
- entry.addRoutingTableEntry(rte); // Add this RTE to this new NPT entry.
- entry.generateNhlfromRteList(); // Generate a list of next-hops from the RTE.
-
- m_table.push_back(entry); // Add the new, completed entry into the main table.
-
- // If the RTE we added has any next hops, we inform the FIB of this.
- if (rte.getNexthopList().getSize() > 0) {
- _LOG_TRACE("Updating FIB with next hops for " << entry);
- m_nlsr.getFib().update(name, entry.getNexthopList());
- }
- }
- else {
- _LOG_TRACE("Adding origin: " << rte.getDestination() << " to existing prefix: " << *it);
- // Update the existing entry with the new RTE.
- it->addRoutingTableEntry(rte);
-
- it->generateNhlfromRteList();
-
- // As above, inform the FIB of this fact.
- // We may possibly have a new best next-hop for this name prefix
- // So this is a necessary step.
- if (it->getNexthopList().getSize() > 0) {
- _LOG_TRACE("Updating FIB with next hops for " << *it);
- m_nlsr.getFib().update(name, it->getNexthopList());
- }
- else {
- // The routing table may recalculate and add a routing table
- // entry with no next hops to replace an existing routing table
- // entry. In this case, the name prefix is no longer reachable
- // through a next hop and should be removed from the FIB. But,
- // the prefix should remain in the Name Prefix Table as a future
- // routing table calculation may add next hops.
- _LOG_TRACE(*it << " has no next hops; removing from FIB");
- m_nlsr.getFib().remove(name);
- }
- }
-}
-
-void
-NamePrefixTable::removeEntry(const ndn::Name& name, RoutingTableEntry& rte)
-{
- NptEntryList::iterator it = std::find_if(m_table.begin(),
- m_table.end(),
- bind(&npteCompare, _1, name));
- if (it != m_table.end()) {
- _LOG_TRACE("Removing origin: " << rte.getDestination() << " from prefix: " << *it);
-
- it->removeRoutingTableEntry(rte);
-
- // If the prefix is a router prefix and it does not have any other routing table entries,
- // the Adjacency/Coordinate LSA associated with that origin router has been removed from
- // the LSDB and so the router prefix should be removed from the Name Prefix Table.
- //
- // If the prefix is an advertised name prefix:
- // If another router advertises this name prefix, the RteList should have another entry
- // for that router; the next hops should be recalculated and installed in the FIB.
- //
- // If no other router advertises this name prefix, the RteList should be empty and the
- // prefix can be removed from the Name Prefix Table. Once a new Name LSA advertises this
- // prefix, a new entry for the prefix will be created.
- //
- if (it->getRteListSize() == 0) {
- _LOG_TRACE(*it << " has no routing table entries; removing from table and FIB");
- m_table.erase(it);
- m_nlsr.getFib().remove(name);
- }
- else {
- _LOG_TRACE(*it << " has other routing table entries; updating FIB with next hops");
- it->generateNhlfromRteList();
-
- m_nlsr.getFib().update(name, it->getNexthopList());
- }
- }
-}
-
-void
NamePrefixTable::addEntry(const ndn::Name& name, const ndn::Name& destRouter)
{
- _LOG_DEBUG("Adding origin: " << destRouter << " to " << name);
- RoutingTableEntry* rteCheck = m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
+ // Check if the advertised name prefix is in the table already.
+ NptEntryList::iterator nameItr = std::find(m_table.begin(),
+ m_table.end(),
+ name);
- if (rteCheck != nullptr) {
- addEntry(name, *rteCheck);
+ // Attempt to find a routing table pool entry (RTPE) we can use.
+ RtpEntryMap::iterator rtpeItr = m_rtpool.find(destRouter);
+
+ // These declarations just to make the compiler happy...
+ RoutingTablePoolEntry rtpe;
+ std::shared_ptr<RoutingTablePoolEntry> rtpePtr(nullptr);
+
+ // There isn't currently a routing table entry in the pool for this name
+ if (rtpeItr == m_rtpool.end()) {
+ // See if there is a routing table entry available we could use
+ RoutingTableEntry* routeEntryPtr = m_nlsr.getRoutingTable()
+ .findRoutingTableEntry(destRouter);
+
+ // We have to create a new routing table entry
+ if (routeEntryPtr == nullptr) {
+ rtpe = RoutingTablePoolEntry(destRouter, 0);
+ }
+ // There was already a usable one in the routing table
+ else {
+ rtpe = RoutingTablePoolEntry(*routeEntryPtr, 0);
+ }
+
+ // Add the new pool object to the pool.
+ rtpePtr = addRtpeToPool(rtpe);
+ }
+ // There was one already, so just fetch that one.
+ else {
+ rtpePtr = (*rtpeItr).second;
+ }
+
+ // Either we have to make a new NPT entry or there already was one.
+ if (nameItr == m_table.end()) {
+ _LOG_DEBUG("Adding origin: " << rtpePtr->getDestination()
+ << " to a new name prefix: " << name);
+ NamePrefixTableEntry npte(name);
+ npte.addRoutingTableEntry(rtpePtr);
+ npte.generateNhlfromRteList();
+ m_table.push_back(npte);
+
+ // If this entry has next hops, we need to inform the FIB
+ if (npte.getNexthopList().getSize() > 0) {
+ _LOG_TRACE("Updating FIB with next hops for " << npte);
+ m_nlsr.getFib().update(name, npte.getNexthopList());
+ }
+ // The routing table may recalculate and add a routing table entry
+ // with no next hops to replace an existing routing table entry. In
+ // this case, the name prefix is no longer reachable through a next
+ // hop and should be removed from the FIB. But, the prefix should
+ // remain in the Name Prefix Table as a future routing table
+ // calculation may add next hops.
+ else {
+ _LOG_TRACE(npte << " has no next hops; removing from FIB");
+ m_nlsr.getFib().remove(name);
+ }
}
else {
- RoutingTableEntry rte(destRouter);
- addEntry(name, rte);
+ _LOG_TRACE("Adding origin: " << rtpePtr->getDestination()
+ << " to existing prefix: " << *nameItr);
+ nameItr->addRoutingTableEntry(rtpePtr);
+ nameItr->generateNhlfromRteList();
+
+ if (nameItr->getNexthopList().getSize() > 0) {
+ _LOG_TRACE("Updating FIB with next hops for " << (*nameItr));
+ m_nlsr.getFib().update(name, nameItr->getNexthopList());
+ }
+ else {
+ _LOG_TRACE((*nameItr) << " has no next hops; removing from FIB");
+ m_nlsr.getFib().remove(name);
+ }
}
}
@@ -147,14 +125,64 @@
{
_LOG_DEBUG("Removing origin: " << destRouter << " from " << name);
- RoutingTableEntry* rteCheck = m_nlsr.getRoutingTable().findRoutingTableEntry(destRouter);
+ // Fetch an iterator to the appropriate pair object in the pool.
+ RtpEntryMap::iterator rtpeItr = m_rtpool.find(destRouter);
- if (rteCheck != nullptr) {
- removeEntry(name, *rteCheck);
+ // Simple error checking to prevent any unusual behavior in the case
+ // that we try to remove an entry that isn't there.
+ if (rtpeItr == m_rtpool.end()) {
+ _LOG_DEBUG("No entry for origin: " << destRouter
+ << " found, so it cannot be removed from prefix: "
+ << name);
+ return;
+ }
+ std::shared_ptr<RoutingTablePoolEntry> rtpePtr = rtpeItr->second;
+
+ // Ensure that the entry exists
+ NptEntryList::iterator nameItr = std::find_if(m_table.begin(),
+ m_table.end(),
+ bind(&npteCompare, _1, name));
+ if (nameItr != m_table.end()) {
+ _LOG_TRACE("Removing origin: " << rtpePtr->getDestination()
+ << " from prefix: " << *nameItr);
+
+ // Rather than iterating through the whole list periodically, just
+ // delete them here if they have no references.
+ if ((*nameItr).removeRoutingTableEntry(rtpePtr) == 0) {
+ deleteRtpeFromPool(rtpePtr);
+ }
+
+ // If the prefix is a router prefix and it does not have any other
+ // routing table entries, the Adjacency/Coordinate LSA associated
+ // with that origin router has been removed from the LSDB and so
+ // the router prefix should be removed from the Name Prefix Table.
+ //
+ // If the prefix is an advertised name prefix: If another router
+ // advertises this name prefix, the RteList should have another
+ // entry for that router; the next hops should be recalculated
+ // and installed in the FIB.
+ //
+ // If no other router advertises this name prefix, the RteList
+ // should be empty and the prefix can be removed from the Name
+ // Prefix Table. Once a new Name LSA advertises this prefix, a
+ // new entry for the prefix will be created.
+ //
+ if ((*nameItr).getRteListSize() == 0) {
+ _LOG_TRACE(*nameItr << " has no routing table entries;"
+ << " removing from table and FIB");
+ m_table.erase(nameItr);
+ m_nlsr.getFib().remove(name);
+ }
+ else {
+ _LOG_TRACE(*nameItr << " has other routing table entries;"
+ << " updating FIB with next hops");
+ (*nameItr).generateNhlfromRteList();
+ m_nlsr.getFib().update(name, (*nameItr).getNexthopList());
+ }
}
else {
- RoutingTableEntry rte(destRouter);
- removeEntry(name, rte);
+ _LOG_DEBUG("Attempted to remove origin: " << rtpePtr->getDestination()
+ << " from non-existant prefix: " << name);
}
}
@@ -163,29 +191,60 @@
{
_LOG_DEBUG("Updating table with newly calculated routes");
- // Update each name prefix entry in the Name Prefix Table with newly calculated next hops
- // For each entry in the NPT
- for (const NamePrefixTableEntry& prefixEntry : m_table) {
- // For each routing table entry
- for (const RoutingTableEntry& routingEntry : prefixEntry.getRteList()) {
- _LOG_TRACE("Updating next hops to origin: " << routingEntry.getDestination()
- << " for prefix: " << prefixEntry);
-
+ // Update each name prefix table entry in the NPT with the
+ // newly calculated next hops.
+ for (auto&& npte : m_table) {
+ // For each routing table pool entry in this NPT entry.
+ for (auto&& rtpe : npte.getRteList()) {
+ _LOG_TRACE("Updating next hops to origin: " << rtpe->getDestination()
+ << " for prefix: " << npte);
RoutingTableEntry* rteCheck =
- m_nlsr.getRoutingTable().findRoutingTableEntry(routingEntry.getDestination());
+ m_nlsr.getRoutingTable().findRoutingTableEntry(rtpe->getDestination());
// If there is a routing table entry for this prefix, update the NPT with it.
if (rteCheck != nullptr) {
- addEntry(prefixEntry.getNamePrefix(), *rteCheck);
+ rtpe->setNexthopList(rteCheck->getNexthopList());
}
else {
- RoutingTableEntry rte(routingEntry.getDestination());
- addEntry(prefixEntry.getNamePrefix(), rte);
+ rtpe->getNexthopList().reset();
}
+ addEntry(npte.getNamePrefix(), rtpe->getDestination());
}
}
}
+ // Inserts the routing table pool entry into the NPT's RTE storage
+ // pool. This cannot fail, so the pool is guaranteed to contain the
+ // item after this occurs.
+std::shared_ptr<RoutingTablePoolEntry>
+NamePrefixTable::addRtpeToPool(RoutingTablePoolEntry& rtpe)
+{
+ RtpEntryMap::iterator poolItr =
+ m_rtpool.insert(std::make_pair(rtpe.getDestination(),
+ std::make_shared<RoutingTablePoolEntry>
+ (rtpe)))
+ .first;
+ //| There's gotta be a more efficient way to do this
+ //std::shared_ptr<RoutingTablePoolEntry> poolPtr = &(poolItr->second);
+ return poolItr->second;
+}
+
+ // Removes the routing table pool entry from the storage pool. The
+ // postconditions of this function are guaranteed to include that
+ // the storage pool does not contain such an item. Additionally,
+ // this function cannot fail, but nonetheless debug information is
+ // given in the case that this function is called with an entry that
+ // isn't in the pool.
+void
+NamePrefixTable::deleteRtpeFromPool(std::shared_ptr<RoutingTablePoolEntry> rtpePtr)
+{
+ if (m_rtpool.erase(rtpePtr->getDestination()) != 1) {
+ _LOG_DEBUG("Attempted to delete non-existant origin: "
+ << rtpePtr->getDestination()
+ << " from NPT routing table entry storage pool.");
+ }
+}
+
void
NamePrefixTable::writeLog()
{