blob: 29c9eb726d48fa027189a6d8d5277fc67b90d1a4 [file] [log] [blame]
Vince12e49462014-06-09 13:29:32 -05001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Davide Pesaventoa3148082018-04-12 18:21:54 -04002/*
Davide Pesaventoc2442be2025-01-11 17:25:40 -05003 * Copyright (c) 2014-2025, Regents of the University of California,
Alexander Afanasyev7c10b3b2015-01-20 12:24:27 -08004 * Arizona Board of Regents,
5 * Colorado State University,
6 * University Pierre & Marie Curie, Sorbonne University,
7 * Washington University in St. Louis,
8 * Beijing Institute of Technology,
9 * The University of Memphis.
Vince12e49462014-06-09 13:29:32 -050010 *
11 * This file is part of NFD (Named Data Networking Forwarding Daemon).
12 * See AUTHORS.md for complete list of NFD authors and contributors.
13 *
14 * NFD is free software: you can redistribute it and/or modify it under the terms
15 * of the GNU General Public License as published by the Free Software Foundation,
16 * either version 3 of the License, or (at your option) any later version.
17 *
18 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20 * PURPOSE. See the GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License along with
23 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24 */
25
26#include "rib-entry.hpp"
Davide Pesavento2cae8ca2019-04-18 20:48:05 -040027#include "common/logger.hpp"
Vince Lehman281ded72014-08-21 12:17:08 -050028
Junxiao Shi25c6ce42016-09-09 13:49:59 +000029#include <ndn-cxx/mgmt/nfd/control-command.hpp>
Vince12e49462014-06-09 13:29:32 -050030
Davide Pesaventoe422f9e2022-06-03 01:30:23 -040031namespace nfd::rib {
Vince12e49462014-06-09 13:29:32 -050032
Davide Pesaventoa3148082018-04-12 18:21:54 -040033NFD_LOG_INIT(RibEntry);
34
Davide Pesavento412c9822021-07-02 00:21:05 -040035static bool
36compareFaceIdAndOrigin(const Route& lhs, const Route& rhs)
37{
38 return lhs.faceId == rhs.faceId && lhs.origin == rhs.origin;
39}
40
Vince Lehman218be0a2015-01-15 17:25:20 -060041RibEntry::RouteList::iterator
42RibEntry::findRoute(const Route& route)
Vince12e49462014-06-09 13:29:32 -050043{
Davide Pesavento412c9822021-07-02 00:21:05 -040044 return std::find_if(begin(), end(),
45 [&] (const auto& r) { return compareFaceIdAndOrigin(r, route); });
Vince12e49462014-06-09 13:29:32 -050046}
47
Vince Lehman76c751c2014-11-18 17:36:38 -060048RibEntry::RouteList::const_iterator
49RibEntry::findRoute(const Route& route) const
50{
Davide Pesavento412c9822021-07-02 00:21:05 -040051 return std::find_if(begin(), end(),
52 [&] (const auto& r) { return compareFaceIdAndOrigin(r, route); });
Vince Lehman76c751c2014-11-18 17:36:38 -060053}
54
Nick Gordon89c4cca2016-11-02 15:42:32 +000055std::pair<RibEntry::iterator, bool>
Vince Lehman218be0a2015-01-15 17:25:20 -060056RibEntry::insertRoute(const Route& route)
Vince12e49462014-06-09 13:29:32 -050057{
Davide Pesavento412c9822021-07-02 00:21:05 -040058 auto it = findRoute(route);
Vince12e49462014-06-09 13:29:32 -050059
Vince Lehman76c751c2014-11-18 17:36:38 -060060 if (it == end()) {
61 if (route.flags & ndn::nfd::ROUTE_FLAG_CAPTURE) {
62 m_nRoutesWithCaptureSet++;
63 }
Vince Lehman4387e782014-06-19 16:57:45 -050064
Vince Lehman76c751c2014-11-18 17:36:38 -060065 m_routes.push_back(route);
Davide Pesaventoe4b22382018-06-10 14:37:24 -040066 return {std::prev(m_routes.end()), true};
67 }
Vince Lehman76c751c2014-11-18 17:36:38 -060068
Davide Pesaventoe4b22382018-06-10 14:37:24 -040069 return {it, false};
Vince12e49462014-06-09 13:29:32 -050070}
71
Vince Lehman281ded72014-08-21 12:17:08 -050072void
Vince Lehman218be0a2015-01-15 17:25:20 -060073RibEntry::eraseRoute(const Route& route)
Vince12e49462014-06-09 13:29:32 -050074{
Davide Pesaventoc2442be2025-01-11 17:25:40 -050075 eraseRoute(findRoute(route));
Vince Lehman4387e782014-06-19 16:57:45 -050076}
77
78bool
Davide Pesavento412c9822021-07-02 00:21:05 -040079RibEntry::hasFaceId(uint64_t faceId) const
Vince12e49462014-06-09 13:29:32 -050080{
Davide Pesaventoc2442be2025-01-11 17:25:40 -050081 return std::find_if(begin(), end(), [=] (const auto& r) { return r.faceId == faceId; }) != end();
Vince Lehman76c751c2014-11-18 17:36:38 -060082}
83
Vince12e49462014-06-09 13:29:32 -050084void
85RibEntry::addChild(shared_ptr<RibEntry> child)
86{
Davide Pesaventoe4b22382018-06-10 14:37:24 -040087 BOOST_ASSERT(!child->getParent());
Davide Pesaventoc2442be2025-01-11 17:25:40 -050088 child->m_parent = shared_from_this();
Davide Pesaventoe4b22382018-06-10 14:37:24 -040089 m_children.push_back(std::move(child));
Vince12e49462014-06-09 13:29:32 -050090}
91
92void
93RibEntry::removeChild(shared_ptr<RibEntry> child)
94{
95 BOOST_ASSERT(child->getParent().get() == this);
Davide Pesaventoc2442be2025-01-11 17:25:40 -050096 child->m_parent = nullptr;
Vince12e49462014-06-09 13:29:32 -050097 m_children.remove(child);
98}
99
Vince Lehman218be0a2015-01-15 17:25:20 -0600100RibEntry::RouteList::iterator
101RibEntry::eraseRoute(RouteList::iterator route)
Vince12e49462014-06-09 13:29:32 -0500102{
Vince Lehman76c751c2014-11-18 17:36:38 -0600103 if (route != m_routes.end()) {
104 if (route->flags & ndn::nfd::ROUTE_FLAG_CAPTURE) {
105 m_nRoutesWithCaptureSet--;
Vince Lehman4387e782014-06-19 16:57:45 -0500106 }
107
Vince Lehman76c751c2014-11-18 17:36:38 -0600108 // Cancel any scheduled event
Davide Pesaventoe1bdc082018-10-11 21:20:23 -0400109 NFD_LOG_TRACE("Cancelling expiration event: " << route->getExpirationEvent());
110 route->cancelExpirationEvent();
Vince Lehman76c751c2014-11-18 17:36:38 -0600111
112 return m_routes.erase(route);
113 }
114
Vince Lehman218be0a2015-01-15 17:25:20 -0600115 return m_routes.end();
Vince Lehman4387e782014-06-19 16:57:45 -0500116}
117
118void
Vince Lehman218be0a2015-01-15 17:25:20 -0600119RibEntry::addInheritedRoute(const Route& route)
Vince Lehman4387e782014-06-19 16:57:45 -0500120{
Vince Lehman218be0a2015-01-15 17:25:20 -0600121 m_inheritedRoutes.push_back(route);
Vince Lehman4387e782014-06-19 16:57:45 -0500122}
123
124void
Vince Lehman218be0a2015-01-15 17:25:20 -0600125RibEntry::removeInheritedRoute(const Route& route)
Vince Lehman4387e782014-06-19 16:57:45 -0500126{
Davide Pesavento412c9822021-07-02 00:21:05 -0400127 m_inheritedRoutes.remove_if([id = route.faceId] (const auto& r) { return r.faceId == id; });
Vince Lehman4387e782014-06-19 16:57:45 -0500128}
129
Vince Lehman76c751c2014-11-18 17:36:38 -0600130RibEntry::RouteList::const_iterator
131RibEntry::findInheritedRoute(const Route& route) const
Vince Lehman4387e782014-06-19 16:57:45 -0500132{
Vince Lehman218be0a2015-01-15 17:25:20 -0600133 return std::find_if(m_inheritedRoutes.begin(), m_inheritedRoutes.end(),
Davide Pesavento412c9822021-07-02 00:21:05 -0400134 [id = route.faceId] (const auto& r) { return r.faceId == id; });
Vince Lehman4387e782014-06-19 16:57:45 -0500135}
136
137bool
Vince Lehman76c751c2014-11-18 17:36:38 -0600138RibEntry::hasInheritedRoute(const Route& route) const
Vince Lehman4387e782014-06-19 16:57:45 -0500139{
Davide Pesaventoe4b22382018-06-10 14:37:24 -0400140 return findInheritedRoute(route) != m_inheritedRoutes.end();
Vince Lehman4387e782014-06-19 16:57:45 -0500141}
142
143bool
Vince Lehman4387e782014-06-19 16:57:45 -0500144RibEntry::hasChildInheritOnFaceId(uint64_t faceId) const
145{
Vince Lehman76c751c2014-11-18 17:36:38 -0600146 for (const Route& route : m_routes) {
147 if (route.faceId == faceId && (route.flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)) {
148 return true;
Vince Lehman4387e782014-06-19 16:57:45 -0500149 }
Vince Lehman76c751c2014-11-18 17:36:38 -0600150 }
Vince Lehman4387e782014-06-19 16:57:45 -0500151
152 return false;
153}
154
Vince Lehman9dcfc402015-03-26 03:18:54 -0500155const Route*
Vince Lehman76c751c2014-11-18 17:36:38 -0600156RibEntry::getRouteWithLowestCostByFaceId(uint64_t faceId) const
Vince Lehman4387e782014-06-19 16:57:45 -0500157{
Vince Lehman9dcfc402015-03-26 03:18:54 -0500158 const Route* candidate = nullptr;
Vince Lehman4387e782014-06-19 16:57:45 -0500159
Vince Lehman76c751c2014-11-18 17:36:38 -0600160 for (const Route& route : m_routes) {
161 // Matching face ID
162 if (route.faceId == faceId) {
163 // If this is the first route with this Face ID found
164 if (candidate == nullptr) {
Vince Lehman9dcfc402015-03-26 03:18:54 -0500165 candidate = &route;
Vince Lehman76c751c2014-11-18 17:36:38 -0600166 }
167 else if (route.cost < candidate->cost) {
168 // Found a route with a lower cost
Vince Lehman9dcfc402015-03-26 03:18:54 -0500169 candidate = &route;
Vince Lehman76c751c2014-11-18 17:36:38 -0600170 }
Vince Lehman4387e782014-06-19 16:57:45 -0500171 }
Vince Lehman76c751c2014-11-18 17:36:38 -0600172 }
Vince Lehman4387e782014-06-19 16:57:45 -0500173
Vince Lehman218be0a2015-01-15 17:25:20 -0600174 return candidate;
Vince Lehman4387e782014-06-19 16:57:45 -0500175}
176
Vince Lehman76c751c2014-11-18 17:36:38 -0600177const Route*
178RibEntry::getRouteWithSecondLowestCostByFaceId(uint64_t faceId) const
179{
Vince Lehman4310d502016-03-04 11:58:59 -0600180 std::vector<const Route*> matches;
Vince Lehman76c751c2014-11-18 17:36:38 -0600181
182 // Copy routes which have faceId
Vince Lehman4310d502016-03-04 11:58:59 -0600183 for (const Route& route : m_routes) {
184 if (route.faceId == faceId) {
185 matches.push_back(&route);
186 }
187 }
Vince Lehman76c751c2014-11-18 17:36:38 -0600188
Vince Lehman4310d502016-03-04 11:58:59 -0600189 // If there are less than 2 routes, there is no second lowest
Vince Lehman76c751c2014-11-18 17:36:38 -0600190 if (matches.size() < 2) {
191 return nullptr;
192 }
193
194 // Get second lowest cost
195 std::nth_element(matches.begin(), matches.begin() + 1, matches.end(),
Vince Lehman4310d502016-03-04 11:58:59 -0600196 [] (const Route* lhs, const Route* rhs) { return lhs->cost < rhs->cost; });
Vince Lehman76c751c2014-11-18 17:36:38 -0600197
Vince Lehman4310d502016-03-04 11:58:59 -0600198 return matches.at(1);
Vince Lehman76c751c2014-11-18 17:36:38 -0600199}
200
Vince Lehman9dcfc402015-03-26 03:18:54 -0500201const Route*
Vince Lehman76c751c2014-11-18 17:36:38 -0600202RibEntry::getRouteWithLowestCostAndChildInheritByFaceId(uint64_t faceId) const
Vince Lehman4387e782014-06-19 16:57:45 -0500203{
Vince Lehman9dcfc402015-03-26 03:18:54 -0500204 const Route* candidate = nullptr;
Vince Lehman4387e782014-06-19 16:57:45 -0500205
Vince Lehman76c751c2014-11-18 17:36:38 -0600206 for (const Route& route : m_routes) {
207 // Correct face ID and Child Inherit flag set
208 if (route.faceId == faceId &&
209 (route.flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT) == ndn::nfd::ROUTE_FLAG_CHILD_INHERIT)
Vince Lehman4387e782014-06-19 16:57:45 -0500210 {
Vince Lehman76c751c2014-11-18 17:36:38 -0600211 // If this is the first route with this Face ID found
212 if (candidate == nullptr) {
Vince Lehman9dcfc402015-03-26 03:18:54 -0500213 candidate = &route;
Vince Lehman76c751c2014-11-18 17:36:38 -0600214 }
215 else if (route.cost < candidate->cost) {
216 // Found a route with a lower cost
Vince Lehman9dcfc402015-03-26 03:18:54 -0500217 candidate = &route;
Vince Lehman76c751c2014-11-18 17:36:38 -0600218 }
Vince Lehman4387e782014-06-19 16:57:45 -0500219 }
Vince Lehman76c751c2014-11-18 17:36:38 -0600220 }
Vince Lehman4387e782014-06-19 16:57:45 -0500221
Vince Lehman218be0a2015-01-15 17:25:20 -0600222 return candidate;
Vince12e49462014-06-09 13:29:32 -0500223}
224
Junxiao Shid47cd632018-09-11 03:10:00 +0000225ndn::PrefixAnnouncement
226RibEntry::getPrefixAnnouncement(time::milliseconds minExpiration,
227 time::milliseconds maxExpiration) const
228{
229 const Route* bestAnnRoute = nullptr;
Davide Pesavento412c9822021-07-02 00:21:05 -0400230 auto entryExpiry = time::steady_clock::time_point::min();
Junxiao Shid47cd632018-09-11 03:10:00 +0000231
232 for (const Route& route : *this) {
233 if (route.expires) {
234 entryExpiry = std::max(entryExpiry, *route.expires);
235 if (route.announcement) {
236 if (bestAnnRoute == nullptr || *route.expires > *bestAnnRoute->expires) {
237 bestAnnRoute = &route;
238 }
239 }
240 }
241 else {
Davide Pesavento412c9822021-07-02 00:21:05 -0400242 entryExpiry = time::steady_clock::time_point::max();
Junxiao Shid47cd632018-09-11 03:10:00 +0000243 }
244 }
245
246 if (bestAnnRoute != nullptr) {
247 return *bestAnnRoute->announcement;
248 }
249
250 ndn::PrefixAnnouncement ann;
251 ann.setAnnouncedName(m_name);
Davide Pesaventoa3a7a4e2022-05-29 16:06:22 -0400252 ann.setExpiration(std::clamp(
Junxiao Shid47cd632018-09-11 03:10:00 +0000253 time::duration_cast<time::milliseconds>(entryExpiry - time::steady_clock::now()),
254 minExpiration, maxExpiration));
255 return ann;
256}
257
Vince12e49462014-06-09 13:29:32 -0500258std::ostream&
Vince12e49462014-06-09 13:29:32 -0500259operator<<(std::ostream& os, const RibEntry& entry)
260{
Davide Pesaventoa3a7a4e2022-05-29 16:06:22 -0400261 os << "RibEntry {\n"
262 << " Name: " << entry.getName() << "\n";
Vince Lehman76c751c2014-11-18 17:36:38 -0600263 for (const Route& route : entry) {
Junxiao Shi3f21e582017-05-29 15:26:32 +0000264 os << " " << route << "\n";
Vince Lehman76c751c2014-11-18 17:36:38 -0600265 }
Davide Pesaventoa3a7a4e2022-05-29 16:06:22 -0400266 return os << "}";
Vince12e49462014-06-09 13:29:32 -0500267}
268
Davide Pesaventoe422f9e2022-06-03 01:30:23 -0400269} // namespace nfd::rib