src/route/name-prefix-table.cpp

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2014-2021,  The University of Memphis,
 *                           Regents of the University of California,
 *                           Arizona Board of Regents.
 *
 * This file is part of NLSR (Named-data Link State Routing).
 * See AUTHORS.md for complete list of NLSR authors and contributors.
 *
 * NLSR 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.
 *
 * NLSR 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
 * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "name-prefix-table.hpp"

#include "logger.hpp"
#include "nlsr.hpp"
#include "routing-table.hpp"

#include <algorithm>
#include <list>
#include <utility>

namespace nlsr {

INIT_LOGGER(route.NamePrefixTable);

NamePrefixTable::NamePrefixTable(const ndn::Name& ownRouterName, Fib& fib,
                                 RoutingTable& routingTable,
                                 AfterRoutingChange& afterRoutingChangeSignal,
                                 Lsdb::AfterLsdbModified& afterLsdbModifiedSignal)
  : m_ownRouterName(ownRouterName)
  , m_fib(fib)
  , m_routingTable(routingTable)
{
  m_afterRoutingChangeConnection = afterRoutingChangeSignal.connect(
    [this] (const std::list<RoutingTableEntry>& entries) {
      updateWithNewRoute(entries);
    });

  m_afterLsdbModified = afterLsdbModifiedSignal.connect(
    [this] (std::shared_ptr<Lsa> lsa, LsdbUpdate updateType,
            const auto& namesToAdd, const auto& namesToRemove) {
      updateFromLsdb(lsa, updateType, namesToAdd, namesToRemove);
    }
  );
}

NamePrefixTable::~NamePrefixTable()
{
  m_afterRoutingChangeConnection.disconnect();
  m_afterLsdbModified.disconnect();
}

void
NamePrefixTable::updateFromLsdb(std::shared_ptr<Lsa> lsa, LsdbUpdate updateType,
                                const std::list<ndn::Name>& namesToAdd,
                                const std::list<ndn::Name>& namesToRemove)
{
  if (m_ownRouterName == lsa->getOriginRouter()) {
    return;
  }
  NLSR_LOG_TRACE("Got update from Lsdb for router: " << lsa->getOriginRouter());

  if (updateType == LsdbUpdate::INSTALLED) {
    addEntry(lsa->getOriginRouter(), lsa->getOriginRouter());

    if (lsa->getType() == Lsa::Type::NAME) {
      auto nlsa = std::static_pointer_cast<NameLsa>(lsa);
      for (const auto& name : nlsa->getNpl().getNames()) {
        if (name != m_ownRouterName) {
          addEntry(name, lsa->getOriginRouter());
        }
      }
    }
  }
  else if (updateType == LsdbUpdate::UPDATED) {
    if (lsa->getType() != Lsa::Type::NAME) {
      return;
    }

    for (const auto& name : namesToAdd) {
      if (name != m_ownRouterName) {
        addEntry(name, lsa->getOriginRouter());
      }
    }

    for (const auto& name : namesToRemove) {
      if (name != m_ownRouterName) {
        removeEntry(name, lsa->getOriginRouter());
      }
    }
  }
  else {
    removeEntry(lsa->getOriginRouter(), lsa->getOriginRouter());
    if (lsa->getType() == Lsa::Type::NAME) {
      auto nlsa = std::static_pointer_cast<NameLsa>(lsa);
      for (const auto& name : nlsa->getNpl().getNames()) {
        if (name != m_ownRouterName) {
          removeEntry(name, lsa->getOriginRouter());
        }
      }
    }
  }
}

void
NamePrefixTable::addEntry(const ndn::Name& name, const ndn::Name& destRouter)
{
  // Check if the advertised name prefix is in the table already.
  NptEntryList::iterator nameItr =
    std::find_if(m_table.begin(),
                 m_table.end(),
                 [&] (const std::shared_ptr<NamePrefixTableEntry>& entry) {
                   return name == entry->getNamePrefix();
                 });

  // Attempt to find a routing table pool entry (RTPE) we can use.
  RoutingTableEntryPool::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_routingTable.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;
  }

  std::shared_ptr<NamePrefixTableEntry> npte;
  // Either we have to make a new NPT entry or there already was one.
  if (nameItr == m_table.end()) {
    NLSR_LOG_DEBUG("Adding origin: " << rtpePtr->getDestination()
                   << " to a new name prefix: " << name);
    npte = std::make_shared<NamePrefixTableEntry>(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().size() > 0) {
      NLSR_LOG_TRACE("Updating FIB with next hops for " << npte->getNamePrefix());
      m_fib.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 {
      NLSR_LOG_TRACE(npte->getNamePrefix() << " has no next hops; removing from FIB");
      m_fib.remove(name);
    }
  }
  else {
    npte = *nameItr;
    NLSR_LOG_TRACE("Adding origin: " << rtpePtr->getDestination() <<
                   " to existing prefix: " << **nameItr);
    (*nameItr)->addRoutingTableEntry(rtpePtr);
    (*nameItr)->generateNhlfromRteList();

    if ((*nameItr)->getNexthopList().size() > 0) {
      NLSR_LOG_TRACE("Updating FIB with next hops for " << (**nameItr));
      m_fib.update(name, (*nameItr)->getNexthopList());
    }
    else {
      NLSR_LOG_TRACE(npte->getNamePrefix() << " has no next hops; removing from FIB");
      m_fib.remove(name);
    }
  }

  // Add the reference to this NPT to the RTPE.
  rtpePtr->namePrefixTableEntries.emplace(
    std::make_pair(npte->getNamePrefix(), std::weak_ptr<NamePrefixTableEntry>(npte)));
}

void
NamePrefixTable::removeEntry(const ndn::Name& name, const ndn::Name& destRouter)
{
  NLSR_LOG_DEBUG("Removing origin: " << destRouter << " from " << name);

  // Fetch an iterator to the appropriate pair object in the pool.
  RoutingTableEntryPool::iterator rtpeItr = m_rtpool.find(destRouter);

  // 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()) {
    NLSR_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(),
                 [&] (const std::shared_ptr<NamePrefixTableEntry>& entry) {
                   return entry->getNamePrefix() == name;
                 });
  if (nameItr != m_table.end()) {
    NLSR_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) {
      NLSR_LOG_TRACE(**nameItr << " has no routing table entries;"
                 << " removing from table and FIB");
      m_table.erase(nameItr);
      m_fib.remove(name);
    }
    else {
      NLSR_LOG_TRACE(**nameItr << " has other routing table entries;"
                 << " updating FIB with next hops");
      (*nameItr)->generateNhlfromRteList();
      m_fib.update(name, (*nameItr)->getNexthopList());
    }
  }
  else {
    NLSR_LOG_DEBUG("Attempted to remove origin: " << rtpePtr->getDestination()
               << " from non-existent prefix: " << name);
  }
}

void
NamePrefixTable::updateWithNewRoute(const std::list<RoutingTableEntry>& entries)
{
  NLSR_LOG_DEBUG("Updating table with newly calculated routes");

  // Iterate over each pool entry we have
  for (auto&& poolEntryPair : m_rtpool) {
    auto&& poolEntry = poolEntryPair.second;
    auto sourceEntry = std::find_if(entries.begin(), entries.end(),
                                    [&poolEntry] (const RoutingTableEntry& entry) {
                                      return poolEntry->getDestination() == entry.getDestination();
                                    });
    // If this pool entry has a corresponding entry in the routing table now
    if (sourceEntry != entries.end()
        && poolEntry->getNexthopList() != sourceEntry->getNexthopList()) {
      NLSR_LOG_DEBUG("Routing entry: " << poolEntry->getDestination() << " has changed next-hops.");
      poolEntry->setNexthopList(sourceEntry->getNexthopList());
      for (const auto& nameEntry : poolEntry->namePrefixTableEntries) {
        auto nameEntryFullPtr = nameEntry.second.lock();
        addEntry(nameEntryFullPtr->getNamePrefix(), poolEntry->getDestination());
      }
    }
    else if (sourceEntry == entries.end()) {
      NLSR_LOG_DEBUG("Routing entry: " << poolEntry->getDestination() << " now has no next-hops.");
      poolEntry->getNexthopList().clear();
      for (const auto& nameEntry : poolEntry->namePrefixTableEntries) {
        auto nameEntryFullPtr = nameEntry.second.lock();
        addEntry(nameEntryFullPtr->getNamePrefix(), poolEntry->getDestination());
      }
    }
    else {
      NLSR_LOG_TRACE("No change in routing entry:" << poolEntry->getDestination()
                 << ", no action necessary.");
    }
  }
}

  // 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)
{
  RoutingTableEntryPool::iterator poolItr =
    m_rtpool.insert(std::make_pair(rtpe.getDestination(),
                                   std::make_shared<RoutingTablePoolEntry>
                                   (rtpe)))
    .first;
  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) {
    NLSR_LOG_DEBUG("Attempted to delete non-existent origin: "
               << rtpePtr->getDestination()
               << " from NPT routing table entry storage pool.");
  }
}

void
NamePrefixTable::writeLog()
{
  NLSR_LOG_DEBUG(*this);
}

std::ostream&
operator<<(std::ostream& os, const NamePrefixTable& table)
{
  os << "----------------NPT----------------------\n";

  for (const auto& entryPtr : table) {
    os << *entryPtr << std::endl;
  }

  return os;
}

} // namespace nlsr