rib.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2024, Regents of the University of California,
4  * 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.
10  *
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 #ifndef NFD_DAEMON_RIB_RIB_HPP
27 #define NFD_DAEMON_RIB_RIB_HPP
28 
29 #include "rib-entry.hpp"
30 #include "rib-update-batch.hpp"
31 
32 #include <ndn-cxx/mgmt/nfd/control-parameters.hpp>
33 
34 #include <functional>
35 #include <map>
36 
37 namespace nfd::rib {
38 
39 using ndn::nfd::ControlParameters;
40 
41 class FibUpdater;
42 
47 {
48  shared_ptr<RibEntry> entry;
50 
51  friend bool
52  operator<(const RibRouteRef& lhs, const RibRouteRef& rhs) noexcept
53  {
54  return std::tie(lhs.entry->getName(), lhs.route->faceId, lhs.route->origin) <
55  std::tie(rhs.entry->getName(), rhs.route->faceId, rhs.route->origin);
56  }
57 };
58 
69 class Rib : noncopyable
70 {
71 public:
72  using RibEntryList = std::list<shared_ptr<RibEntry>>;
73  using RibTable = std::map<Name, shared_ptr<RibEntry>>;
74  using const_iterator = RibTable::const_iterator;
75 
76  void
77  setFibUpdater(FibUpdater* updater);
78 
80  find(const Name& prefix) const;
81 
82  Route*
83  find(const Name& prefix, const Route& route) const;
84 
85  Route*
86  findLongestPrefix(const Name& prefix, const Route& route) const;
87 
89  begin() const
90  {
91  return m_rib.begin();
92  }
93 
95  end() const
96  {
97  return m_rib.end();
98  }
99 
100  size_t
101  size() const noexcept
102  {
103  return m_nItems;
104  }
105 
106  [[nodiscard]] bool
107  empty() const noexcept
108  {
109  return m_rib.empty();
110  }
111 
112  shared_ptr<RibEntry>
113  findParent(const Name& prefix) const;
114 
115 public:
116  using UpdateSuccessCallback = std::function<void()>;
117  using UpdateFailureCallback = std::function<void(uint32_t code, const std::string& error)>;
118 
127  void
128  beginApplyUpdate(const RibUpdate& update,
129  const UpdateSuccessCallback& onSuccess,
130  const UpdateFailureCallback& onFailure);
131 
134  void
135  beginRemoveFace(uint64_t faceId);
136 
137  void
138  beginRemoveFailedFaces(const std::set<uint64_t>& activeFaceIds);
139 
140  void
141  onRouteExpiration(const Name& prefix, const Route& route);
142 
143  void
144  insert(const Name& prefix, const Route& route);
145 
146 private:
147  void
148  enqueueRemoveFace(const RibEntry& entry, uint64_t faceId);
149 
154  void
155  addUpdateToQueue(const RibUpdate& update,
156  const Rib::UpdateSuccessCallback& onSuccess,
157  const Rib::UpdateFailureCallback& onFailure);
158 
161  void
162  sendBatchFromQueue();
163 
164  void
165  onFibUpdateSuccess(const RibUpdateBatch& batch,
166  const RibUpdateList& inheritedRoutes,
167  const Rib::UpdateSuccessCallback& onSuccess);
168 
169  void
170  onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
171  uint32_t code, const std::string& error);
172 
174  void
175  erase(const Name& prefix, const Route& route);
176 
177 private:
178  using RouteComparePredicate = bool (*)(const Route&, const Route&);
179  using RouteSet = std::set<Route, RouteComparePredicate>;
180 
184  std::list<shared_ptr<RibEntry>>
185  findDescendants(const Name& prefix) const;
186 
190  std::list<shared_ptr<RibEntry>>
191  findDescendantsForNonInsertedName(const Name& prefix) const;
192 
193  RibTable::iterator
194  eraseEntry(RibTable::iterator it);
195 
196  void
197  updateRib(const RibUpdateBatch& batch);
198 
202  RouteSet
203  getAncestorRoutes(const RibEntry& entry) const;
204 
209  RouteSet
210  getAncestorRoutes(const Name& name) const;
211 
215  void
216  modifyInheritedRoutes(const RibUpdateList& inheritedRoutes);
217 
218 public:
224  signal::Signal<Rib, Name> afterInsertEntry;
225 
231  signal::Signal<Rib, Name> afterEraseEntry;
232 
235  signal::Signal<Rib, RibRouteRef> afterAddRoute;
236 
239  signal::Signal<Rib, RibRouteRef> beforeRemoveRoute;
240 
241 private:
242  RibTable m_rib;
243  // FaceId => Entry with Route on this face
244  std::multimap<uint64_t, shared_ptr<RibEntry>> m_faceEntries;
245  size_t m_nItems = 0;
246  FibUpdater* m_fibUpdater = nullptr;
247 
248  struct UpdateQueueItem
249  {
250  RibUpdateBatch batch;
251  const Rib::UpdateSuccessCallback managerSuccessCallback;
252  const Rib::UpdateFailureCallback managerFailureCallback;
253  };
254 
255  using UpdateQueue = std::list<UpdateQueueItem>;
256  UpdateQueue m_updateBatches;
257  bool m_isUpdateInProgress = false;
258 
259  friend FibUpdater;
260 };
261 
262 std::ostream&
263 operator<<(std::ostream& os, const Rib& rib);
264 
265 } // namespace nfd::rib
266 
267 #endif // NFD_DAEMON_RIB_RIB_HPP
Computes FibUpdates based on updates to the RIB and sends them to NFD.
Definition: fib-updater.hpp:42
Represents a RIB entry, which contains one or more Routes with the same prefix.
Definition: rib-entry.hpp:39
RouteList::const_iterator const_iterator
Definition: rib-entry.hpp:43
Represents the Routing Information Base.
Definition: rib.hpp:70
signal::Signal< Rib, Name > afterInsertEntry
Signals after a RIB entry is inserted.
Definition: rib.hpp:224
size_t size() const noexcept
Definition: rib.hpp:101
signal::Signal< Rib, RibRouteRef > afterAddRoute
Signals after a Route is added.
Definition: rib.hpp:235
void beginRemoveFailedFaces(const std::set< uint64_t > &activeFaceIds)
Definition: rib.cpp:355
const_iterator begin() const
Definition: rib.hpp:89
signal::Signal< Rib, RibRouteRef > beforeRemoveRoute
Signals before a route is removed.
Definition: rib.hpp:239
std::function< void()> UpdateSuccessCallback
Definition: rib.hpp:116
void setFibUpdater(FibUpdater *updater)
Definition: rib.cpp:41
void beginRemoveFace(uint64_t faceId)
Starts the FIB update process when a face has been destroyed.
Definition: rib.cpp:345
RibTable::const_iterator const_iterator
Definition: rib.hpp:74
Route * findLongestPrefix(const Name &prefix, const Route &route) const
Definition: rib.cpp:70
void insert(const Name &prefix, const Route &route)
Definition: rib.cpp:84
const_iterator end() const
Definition: rib.hpp:95
signal::Signal< Rib, Name > afterEraseEntry
Signals after a RIB entry is erased.
Definition: rib.hpp:231
std::list< shared_ptr< RibEntry > > RibEntryList
Definition: rib.hpp:72
void onRouteExpiration(const Name &prefix, const Route &route)
Definition: rib.cpp:189
bool empty() const noexcept
Definition: rib.hpp:107
std::map< Name, shared_ptr< RibEntry > > RibTable
Definition: rib.hpp:73
const_iterator find(const Name &prefix) const
Definition: rib.cpp:47
void beginApplyUpdate(const RibUpdate &update, const UpdateSuccessCallback &onSuccess, const UpdateFailureCallback &onFailure)
Passes the provided RibUpdateBatch to FibUpdater to calculate and send FibUpdates.
Definition: rib.cpp:335
std::function< void(uint32_t code, const std::string &error)> UpdateFailureCallback
Definition: rib.hpp:117
shared_ptr< RibEntry > findParent(const Name &prefix) const
Definition: rib.cpp:202
Represents a collection of RibUpdates to be applied to a single FaceId.
Represents a route that will be added to or removed from a namespace.
Definition: rib-update.hpp:39
Represents a route for a name prefix.
Definition: route.hpp:44
#define NFD_PUBLIC_WITH_TESTS_ELSE_PRIVATE
Definition: common.hpp:41
std::ostream & operator<<(std::ostream &os, const FibUpdate &update)
Definition: fib-update.cpp:52
std::list< RibUpdate > RibUpdateList
References a route.
Definition: rib.hpp:47
friend bool operator<(const RibRouteRef &lhs, const RibRouteRef &rhs) noexcept
Definition: rib.hpp:52
shared_ptr< RibEntry > entry
Definition: rib.hpp:48
RibEntry::const_iterator route
Definition: rib.hpp:49