daemon/rib/fib-updater.cpp

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2014-2025,  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 "fib-updater.hpp"
#include "common/logger.hpp"

#include <ndn-cxx/mgmt/nfd/control-command.hpp>

namespace nfd::rib {

NFD_LOG_INIT(FibUpdater);

constexpr int MAX_NUM_TIMEOUTS = 10;
constexpr uint32_t ERROR_FACE_NOT_FOUND = 410;

FibUpdater::FibUpdater(Rib& rib, ndn::nfd::Controller& controller)
  : m_rib(rib)
  , m_controller(controller)
{
  rib.setFibUpdater(this);
}

void
FibUpdater::computeAndSendFibUpdates(const RibUpdateBatch& batch,
                                     const FibUpdateSuccessCallback& onSuccess,
                                     const FibUpdateFailureCallback& onFailure)
{
  m_batchFaceId = batch.getFaceId();

  // Erase previously calculated inherited routes
  m_inheritedRoutes.clear();

  // Erase previously calculated FIB updates
  m_updatesForBatchFaceId.clear();
  m_updatesForNonBatchFaceId.clear();

  computeUpdates(batch);

  sendUpdatesForBatchFaceId(onSuccess, onFailure);
}

void
FibUpdater::computeUpdates(const RibUpdateBatch& batch)
{
  NFD_LOG_TRACE("Computing updates for batch with faceid=" << batch.getFaceId());

  // Compute updates and add to m_fibUpdates
  for (const RibUpdate& update : batch) {
    switch (update.action) {
    case RibUpdate::REGISTER:
      computeUpdatesForRegistration(update);
      break;
    case RibUpdate::UNREGISTER:
      computeUpdatesForUnregistration(update);
      break;
    case RibUpdate::REMOVE_FACE:
      computeUpdatesForUnregistration(update);
      // Do not apply updates with the same face ID as the destroyed face
      // since they will be rejected by the FIB
      m_updatesForBatchFaceId.clear();
      break;
    }
  }
}

void
FibUpdater::computeUpdatesForRegistration(const RibUpdate& update)
{
  auto it = m_rib.find(update.name);

  // Name prefix exists
  if (it != m_rib.end()) {
    shared_ptr<const RibEntry> entry(it->second);
    auto existingRoute = entry->findRoute(update.route);

    // Route will be new
    if (existingRoute == entry->end()) {
      // Will the new route change the namespace's capture flag?
      bool willCaptureBeTurnedOn = (!entry->hasCapture() && update.route.isRibCapture());

      createFibUpdatesForNewRoute(*entry, update.route, willCaptureBeTurnedOn);
    }
    else {
      // Route already exists
      RibEntry entryCopy = *entry;

      Route& routeToUpdate = *entryCopy.findRoute(update.route);
      routeToUpdate.flags = update.route.flags;
      routeToUpdate.cost = update.route.cost;
      routeToUpdate.expires = update.route.expires;

      createFibUpdatesForUpdatedRoute(entryCopy, update.route, *existingRoute);
    }
  }
  else {
    // New name in RIB
    // Find prefix's parent
    shared_ptr<RibEntry> parent = m_rib.findParent(update.name);

    Rib::RibEntryList descendants = m_rib.findDescendantsForNonInsertedName(update.name);
    Rib::RibEntryList children;

    for (const auto& descendant : descendants) {
      // If the child has the same parent as the new entry,
      // the new entry must be the child's new parent
      if (descendant->getParent() == parent) {
        children.push_back(descendant);
      }
    }

    createFibUpdatesForNewRibEntry(update.name, update.route, children);
  }
}

void
FibUpdater::computeUpdatesForUnregistration(const RibUpdate& update)
{
  auto ribIt = m_rib.find(update.name);

  // Name prefix exists
  if (ribIt != m_rib.end()) {
    shared_ptr<const RibEntry> entry(ribIt->second);
    const bool hadCapture = entry->hasCapture();

    auto existing = entry->findRoute(update.route);
    if (existing != entry->end()) {
      RibEntry temp = *entry;

      // Erase route in temp entry
      temp.eraseRoute(update.route);

      bool captureWasTurnedOff = (hadCapture && !temp.hasCapture());
      createFibUpdatesForErasedRoute(temp, *existing, captureWasTurnedOff);

      // The RibEntry still has the face ID; need to update FIB
      // with lowest cost for the same face instead of removing the face from the FIB
      const Route* next = entry->getRouteWithSecondLowestCostByFaceId(update.route.faceId);

      if (next != nullptr) {
        createFibUpdatesForNewRoute(temp, *next, false);
      }

      // The RibEntry will be empty after this removal
      if (entry->getRoutes().size() == 1) {
        createFibUpdatesForErasedRibEntry(*entry);
      }
    }
  }
}

void
FibUpdater::sendUpdates(const FibUpdateList& updates,
                        const FibUpdateSuccessCallback& onSuccess,
                        const FibUpdateFailureCallback& onFailure)
{
  NFD_LOG_DEBUG("Applying " << updates.size() << " FIB update(s)");

  for (const FibUpdate& update : updates) {
    NFD_LOG_DEBUG("Sending " << update);

    if (update.action == FibUpdate::ADD_NEXTHOP) {
      sendAddNextHopUpdate(update, onSuccess, onFailure);
    }
    else if (update.action == FibUpdate::REMOVE_NEXTHOP) {
      sendRemoveNextHopUpdate(update, onSuccess, onFailure);
    }
  }
}

void
FibUpdater::sendUpdatesForBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
                                      const FibUpdateFailureCallback& onFailure)
{
  if (m_updatesForBatchFaceId.size() > 0) {
    sendUpdates(m_updatesForBatchFaceId, onSuccess, onFailure);
  }
  else {
    sendUpdatesForNonBatchFaceId(onSuccess, onFailure);
  }
}

void
FibUpdater::sendUpdatesForNonBatchFaceId(const FibUpdateSuccessCallback& onSuccess,
                                         const FibUpdateFailureCallback& onFailure)
{
  if (m_updatesForNonBatchFaceId.size() > 0) {
    sendUpdates(m_updatesForNonBatchFaceId, onSuccess, onFailure);
  }
  else {
    onSuccess(m_inheritedRoutes);
  }
}

void
FibUpdater::sendAddNextHopUpdate(const FibUpdate& update,
                                 const FibUpdateSuccessCallback& onSuccess,
                                 const FibUpdateFailureCallback& onFailure,
                                 uint32_t nTimeouts)
{
  m_controller.start<ndn::nfd::FibAddNextHopCommand>(
    ControlParameters()
      .setName(update.name)
      .setFaceId(update.faceId)
      .setCost(update.cost),
    [=] (const auto&) { onUpdateSuccess(update, onSuccess, onFailure); },
    [=] (const auto& resp) { onUpdateError(update, onSuccess, onFailure, resp, nTimeouts); });
}

void
FibUpdater::sendRemoveNextHopUpdate(const FibUpdate& update,
                                    const FibUpdateSuccessCallback& onSuccess,
                                    const FibUpdateFailureCallback& onFailure,
                                    uint32_t nTimeouts)
{
  m_controller.start<ndn::nfd::FibRemoveNextHopCommand>(
    ControlParameters()
      .setName(update.name)
      .setFaceId(update.faceId),
    [=] (const auto&) { onUpdateSuccess(update, onSuccess, onFailure); },
    [=] (const auto& resp) { onUpdateError(update, onSuccess, onFailure, resp, nTimeouts); });
}

void
FibUpdater::onUpdateSuccess(const FibUpdate& update,
                            const FibUpdateSuccessCallback& onSuccess,
                            const FibUpdateFailureCallback& onFailure)
{
  if (update.faceId == m_batchFaceId) {
    m_updatesForBatchFaceId.remove(update);

    if (m_updatesForBatchFaceId.size() == 0) {
      sendUpdatesForNonBatchFaceId(onSuccess, onFailure);
    }
  }
  else {
    m_updatesForNonBatchFaceId.remove(update);

    if (m_updatesForNonBatchFaceId.size() == 0) {
      onSuccess(m_inheritedRoutes);
    }
  }
}

void
FibUpdater::onUpdateError(const FibUpdate& update,
                          const FibUpdateSuccessCallback& onSuccess,
                          const FibUpdateFailureCallback& onFailure,
                          const ndn::nfd::ControlResponse& response, uint32_t nTimeouts)
{
  uint32_t code = response.getCode();
  NFD_LOG_DEBUG("Failed to apply " << update <<
                " [code: " << code << ", error: " << response.getText() << "]");

  if (code == ndn::nfd::Controller::ERROR_TIMEOUT && nTimeouts < MAX_NUM_TIMEOUTS) {
    sendAddNextHopUpdate(update, onSuccess, onFailure, ++nTimeouts);
  }
  else if (code == ERROR_FACE_NOT_FOUND) {
    if (update.faceId == m_batchFaceId) {
      onFailure(code, response.getText());
    }
    else {
      m_updatesForNonBatchFaceId.remove(update);

      if (m_updatesForNonBatchFaceId.size() == 0) {
        onSuccess(m_inheritedRoutes);
      }
    }
  }
  else {
    NDN_THROW(Error("Non-recoverable error " + std::to_string(code) + ": " + response.getText()));
  }
}

void
FibUpdater::addFibUpdate(const FibUpdate& update)
{
  FibUpdateList& updates = (update.faceId == m_batchFaceId) ? m_updatesForBatchFaceId :
                                                              m_updatesForNonBatchFaceId;

  // If an update with the same name and route already exists, replace it
  auto it = std::find_if(updates.begin(), updates.end(),
    [&update] (const FibUpdate& other) {
      return update.name == other.name && update.faceId == other.faceId;
    });

  if (it != updates.end()) {
    FibUpdate& existingUpdate = *it;
    existingUpdate.action = update.action;
    existingUpdate.cost = update.cost;
  }
  else {
    updates.push_back(update);
  }
}

void
FibUpdater::addInheritedRoutes(const RibEntry& entry, const Rib::RouteSet& routesToAdd)
{
  for (const Route& route : routesToAdd) {
    // Don't add an ancestor faceId if the namespace has an entry for that faceId
    if (!entry.hasFaceId(route.faceId)) {
      // Create a record of the inherited route so it can be added to the RIB later
      addInheritedRoute(entry.getName(), route);

      addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
    }
  }
}

void
FibUpdater::addInheritedRoutes(const Name& name, const Rib::RouteSet& routesToAdd,
                               const Route& ignore)
{
  for (const Route& route : routesToAdd) {
    if (route.faceId != ignore.faceId) {
      // Create a record of the inherited route so it can be added to the RIB later
      addInheritedRoute(name, route);

      addFibUpdate(FibUpdate::createAddUpdate(name, route.faceId, route.cost));
    }
  }
}

void
FibUpdater::removeInheritedRoutes(const RibEntry& entry, const Rib::Rib::RouteSet& routesToRemove)
{
  for (const Route& route : routesToRemove) {
    // Only remove if the route has been inherited
    if (entry.hasInheritedRoute(route)) {
      removeInheritedRoute(entry.getName(), route);
      addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
    }
  }
}

void
FibUpdater::createFibUpdatesForNewRibEntry(const Name& name, const Route& route,
                                           const Rib::RibEntryList& children)
{
  // Create FIB update for new entry
  addFibUpdate(FibUpdate::createAddUpdate(name, route.faceId, route.cost));

  // No flags are set
  if (!route.isChildInherit() && !route.isRibCapture()) {
    // Add ancestor routes to self
    addInheritedRoutes(name, m_rib.getAncestorRoutes(name), route);
  }
  else if (route.isChildInherit() && route.isRibCapture()) {
    // Add route to children
    Rib::RouteSet routesToAdd;
    routesToAdd.insert(route);

    // Remove routes blocked by capture and add self to children
    modifyChildrensInheritedRoutes(children, routesToAdd, m_rib.getAncestorRoutes(name));
  }
  else if (route.isChildInherit()) {
    Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(name);

    // Add ancestor routes to self
    addInheritedRoutes(name, ancestorRoutes, route);

    // If there is an ancestor route which is the same as the new route, replace it
    // with the new route
    auto it = ancestorRoutes.find(route);

    // There is a route that needs to be overwritten, erase and then replace
    if (it != ancestorRoutes.end()) {
      ancestorRoutes.erase(it);
    }

    // Add new route to ancestor list so it can be added to children
    ancestorRoutes.insert(route);

    // Add ancestor routes to children
    modifyChildrensInheritedRoutes(children, ancestorRoutes, Rib::RouteSet());
  }
  else if (route.isRibCapture()) {
    // Remove routes blocked by capture
    modifyChildrensInheritedRoutes(children, Rib::RouteSet(), m_rib.getAncestorRoutes(name));
  }
}

void
FibUpdater::createFibUpdatesForNewRoute(const RibEntry& entry, const Route& route,
                                        bool captureWasTurnedOn)
{
  // Only update if the new route has a lower cost than a previously installed route
  const Route* prevRoute = entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);

  Rib::RouteSet routesToAdd;
  if (route.isChildInherit()) {
    // Add to children if this new route doesn't override a previous lower cost, or
    // add to children if this new route is lower cost than a previous route.
    // Less than equal, since entry may find this route
    if (prevRoute == nullptr || route.cost <= prevRoute->cost) {
      // Add self to children
      routesToAdd.insert(route);
    }
  }

  Rib::RouteSet routesToRemove;
  if (captureWasTurnedOn) {
    // Capture flag on
    routesToRemove = m_rib.getAncestorRoutes(entry);

    // Remove ancestor routes from self
    removeInheritedRoutes(entry, routesToRemove);
  }

  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);

  // If another route with same faceId and lower cost exists, don't update.
  // Must be done last so that add updates replace removal updates
  // Create FIB update for new entry
  const Route* other = entry.getRouteWithLowestCostByFaceId(route.faceId);

  if (other == nullptr || route.cost <= other->cost) {
    addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
  }
}

void
FibUpdater::createFibUpdatesForUpdatedRoute(const RibEntry& entry, const Route& route,
                                            const Route& existingRoute)
{
  const bool costDidChange = (route.cost != existingRoute.cost);

  // Look for an installed route with the lowest cost and child inherit set
  const Route* prevRoute = entry.getRouteWithLowestCostAndChildInheritByFaceId(route.faceId);

  // No flags changed and cost didn't change, no change in FIB
  if (route.flags == existingRoute.flags && !costDidChange) {
    return;
  }

  // Cost changed so create update for the entry itself
  if (costDidChange) {
    // Create update if this route's cost is lower than other routes
    if (route.cost <= entry.getRouteWithLowestCostByFaceId(route.faceId)->cost) {
      // Create FIB update for the updated entry
      addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), route.faceId, route.cost));
    }
    else if (existingRoute.cost < entry.getRouteWithLowestCostByFaceId(route.faceId)->cost) {
      // Create update if this route used to be the lowest route but is no longer
      // the lowest cost route.
      addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), prevRoute->faceId, prevRoute->cost));
    }

    // If another route with same faceId and lower cost and ChildInherit exists,
    // don't update children.
    if (prevRoute == nullptr || route.cost <= prevRoute->cost) {
      // If no flags changed but child inheritance is set, need to update children
      // with new cost
      if ((route.flags == existingRoute.flags) && route.isChildInherit()) {
        // Add self to children
        Rib::RouteSet routesToAdd;
        routesToAdd.insert(route);
        modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());

        return;
      }
    }
  }

  // Child inherit was turned on
  if (!existingRoute.isChildInherit() && route.isChildInherit()) {
    // If another route with same faceId and lower cost and ChildInherit exists,
    // don't update children.
    if (prevRoute == nullptr || route.cost <= prevRoute->cost) {
      // Add self to children
      Rib::RouteSet routesToAdd;
      routesToAdd.insert(route);
      modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
    }
  } // Child inherit was turned off
  else if (existingRoute.isChildInherit() && !route.isChildInherit()) {
    // Remove self from children
    Rib::RouteSet routesToRemove;
    routesToRemove.insert(route);

    Rib::RouteSet routesToAdd;
    // If another route with same faceId and ChildInherit exists, update children with this route.
    if (prevRoute != nullptr) {
      routesToAdd.insert(*prevRoute);
    }
    else {
      // Look for an ancestor that was blocked previously
      const Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);
      auto it = ancestorRoutes.find(route);

      // If an ancestor is found, add it to children
      if (it != ancestorRoutes.end()) {
        routesToAdd.insert(*it);
      }
    }

    modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
  }

  // Capture was turned on
  if (!existingRoute.isRibCapture() && route.isRibCapture()) {
    Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);

    // Remove ancestor routes from self
    removeInheritedRoutes(entry, ancestorRoutes);

    // Remove ancestor routes from children
    modifyChildrensInheritedRoutes(entry.getChildren(), Rib::RouteSet(), ancestorRoutes);
  }  // Capture was turned off
  else if (existingRoute.isRibCapture() && !route.isRibCapture()) {
    Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);

    // Add ancestor routes to self
    addInheritedRoutes(entry, ancestorRoutes);

    // Add ancestor routes to children
    modifyChildrensInheritedRoutes(entry.getChildren(), ancestorRoutes, Rib::RouteSet());
  }
}

void
FibUpdater::createFibUpdatesForErasedRoute(const RibEntry& entry, const Route& route,
                                           bool captureWasTurnedOff)
{
  addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));

  if (route.isChildInherit() && route.isRibCapture()) {
    // Remove self from children
    Rib::RouteSet routesToRemove;
    routesToRemove.insert(route);

    // If capture is turned off for the route and another route is installed in the RibEntry,
    // add ancestors to self
    Rib::RouteSet routesToAdd;
    if (captureWasTurnedOff && !entry.empty()) {
      // Look for an ancestors that were blocked previously
      routesToAdd = m_rib.getAncestorRoutes(entry);

      // Add ancestor routes to self
      addInheritedRoutes(entry, routesToAdd);
    }

    modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
  }
  else if (route.isChildInherit()) {
    // If not blocked by capture, add inherited routes to children
    Rib::RouteSet routesToAdd;
    if (!entry.hasCapture()) {
      routesToAdd = m_rib.getAncestorRoutes(entry);
    }

    Rib::RouteSet routesToRemove;
    routesToRemove.insert(route);

    // Add ancestor routes to children
    modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
  }
  else if (route.isRibCapture()) {
    // If capture is turned off for the route and another route is installed in the RibEntry,
    // add ancestors to self
    Rib::RouteSet routesToAdd;
    if (captureWasTurnedOff && !entry.empty()) {
      // Look for an ancestors that were blocked previously
      routesToAdd = m_rib.getAncestorRoutes(entry);

      // Add ancestor routes to self
      addInheritedRoutes(entry, routesToAdd);
    }

    modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, Rib::RouteSet());
  }

  // Need to check if the removed route was blocking an inherited route
  Rib::RouteSet ancestorRoutes = m_rib.getAncestorRoutes(entry);

  // If the current entry has capture set or is pending removal, don't add inherited route
  if (!entry.hasCapture() && !entry.empty()) {
    // If there is an ancestor route which is the same as the erased route, add that route
    // to the current entry
    auto it = ancestorRoutes.find(route);
    if (it != ancestorRoutes.end()) {
      addInheritedRoute(entry.getName(), *it);
      addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
    }
  }
}

void
FibUpdater::createFibUpdatesForErasedRibEntry(const RibEntry& entry)
{
  for (const Route& route : entry.getInheritedRoutes()) {
    addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), route.faceId));
  }
}

void
FibUpdater::modifyChildrensInheritedRoutes(const Rib::RibEntryList& children,
                                           const Rib::RouteSet& routesToAdd,
                                           const Rib::RouteSet& routesToRemove)
{
  for (const auto& child : children) {
    traverseSubTree(*child, routesToAdd, routesToRemove);
  }
}

void
FibUpdater::traverseSubTree(const RibEntry& entry, Rib::Rib::RouteSet routesToAdd,
                            Rib::Rib::RouteSet routesToRemove)
{
  // If a route on the namespace has the capture flag set, ignore self and children
  if (entry.hasCapture()) {
    return;
  }

  // Remove inherited routes from current namespace
  for (auto removeIt = routesToRemove.begin(); removeIt != routesToRemove.end(); ) {
    // If a route on the namespace has the same face ID and child inheritance set,
    // ignore this route
    if (entry.hasChildInheritOnFaceId(removeIt->faceId)) {
      removeIt = routesToRemove.erase(removeIt);
      continue;
    }

    // Only remove route if it removes an existing inherited route
    if (entry.hasInheritedRoute(*removeIt)) {
      removeInheritedRoute(entry.getName(), *removeIt);
      addFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), removeIt->faceId));
    }

    ++removeIt;
  }

  // Add inherited routes to current namespace
  for (auto addIt = routesToAdd.begin(); addIt != routesToAdd.end(); ) {
    // If a route on the namespace has the same face ID and child inherit set, ignore this face
    if (entry.hasChildInheritOnFaceId(addIt->faceId)) {
      addIt = routesToAdd.erase(addIt);
      continue;
    }

    // Only add route if it does not override an existing route
    if (!entry.hasFaceId(addIt->faceId)) {
      addInheritedRoute(entry.getName(), *addIt);
      addFibUpdate(FibUpdate::createAddUpdate(entry.getName(), addIt->faceId, addIt->cost));
    }

    ++addIt;
  }

  modifyChildrensInheritedRoutes(entry.getChildren(), routesToAdd, routesToRemove);
}

void
FibUpdater::addInheritedRoute(const Name& name, const Route& route)
{
  m_inheritedRoutes.push_back({RibUpdate::REGISTER, name, route});
}

void
FibUpdater::removeInheritedRoute(const Name& name, const Route& route)
{
  m_inheritedRoutes.push_back({RibUpdate::UNREGISTER, name, route});
}

} // namespace nfd::rib