rib.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2019, 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 #include "rib.hpp"
27 #include "fib-updater.hpp"
28 #include "common/logger.hpp"
29 
30 namespace nfd {
31 namespace rib {
32 
33 NFD_LOG_INIT(Rib);
34 
35 bool
36 operator<(const RibRouteRef& lhs, const RibRouteRef& rhs)
37 {
38  return std::tie(lhs.entry->getName(), lhs.route->faceId, lhs.route->origin) <
39  std::tie(rhs.entry->getName(), rhs.route->faceId, rhs.route->origin);
40 }
41 
42 static inline bool
43 sortRoutes(const Route& lhs, const Route& rhs)
44 {
45  return lhs.faceId < rhs.faceId;
46 }
47 
48 void
50 {
51  m_fibUpdater = updater;
52 }
53 
55 Rib::find(const Name& prefix) const
56 {
57  return m_rib.find(prefix);
58 }
59 
60 Route*
61 Rib::find(const Name& prefix, const Route& route) const
62 {
63  auto ribIt = m_rib.find(prefix);
64 
65  // Name prefix exists
66  if (ribIt != m_rib.end()) {
67  shared_ptr<RibEntry> entry = ribIt->second;
68  auto routeIt = entry->findRoute(route);
69  if (routeIt != entry->end()) {
70  return &*routeIt;
71  }
72  }
73 
74  return nullptr;
75 }
76 
77 Route*
78 Rib::findLongestPrefix(const Name& prefix, const Route& route) const
79 {
80  Route* existingRoute = find(prefix, route);
81  if (existingRoute == nullptr) {
82  auto parent = findParent(prefix);
83  if (parent) {
84  existingRoute = find(parent->getName(), route);
85  }
86  }
87 
88  return existingRoute;
89 }
90 
91 void
92 Rib::insert(const Name& prefix, const Route& route)
93 {
94  auto ribIt = m_rib.find(prefix);
95 
96  // Name prefix exists
97  if (ribIt != m_rib.end()) {
98  shared_ptr<RibEntry> entry(ribIt->second);
99 
100  RibEntry::iterator entryIt;
101  bool didInsert = false;
102  std::tie(entryIt, didInsert) = entry->insertRoute(route);
103 
104  if (didInsert) {
105  // The route was new and we successfully inserted it.
106  m_nItems++;
107 
108  afterAddRoute(RibRouteRef{entry, entryIt});
109 
110  // Register with face lookup table
111  m_faceEntries.emplace(route.faceId, entry);
112  }
113  else {
114  // Route exists, update fields
115  // First cancel old scheduled event, if any, then set the EventId to new one
116  if (entryIt->getExpirationEvent()) {
117  NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " " << *entryIt);
118  entryIt->cancelExpirationEvent();
119  }
120 
121  *entryIt = route;
122  }
123  }
124  else {
125  // New name prefix
126  auto entry = make_shared<RibEntry>();
127 
128  m_rib[prefix] = entry;
129  m_nItems++;
130 
131  entry->setName(prefix);
132  auto routeIt = entry->insertRoute(route).first;
133 
134  // Find prefix's parent
135  shared_ptr<RibEntry> parent = findParent(prefix);
136 
137  // Add self to parent's children
138  if (parent != nullptr) {
139  parent->addChild(entry);
140  }
141 
142  RibEntryList children = findDescendants(prefix);
143 
144  for (const auto& child : children) {
145  if (child->getParent() == parent) {
146  // Remove child from parent and inherit parent's child
147  if (parent != nullptr) {
148  parent->removeChild(child);
149  }
150 
151  entry->addChild(child);
152  }
153  }
154 
155  // Register with face lookup table
156  m_faceEntries.emplace(route.faceId, entry);
157 
158  // do something after inserting an entry
159  afterInsertEntry(prefix);
160  afterAddRoute(RibRouteRef{entry, routeIt});
161  }
162 }
163 
164 void
165 Rib::erase(const Name& prefix, const Route& route)
166 {
167  auto ribIt = m_rib.find(prefix);
168  if (ribIt == m_rib.end()) {
169  // Name prefix does not exist
170  return;
171  }
172 
173  shared_ptr<RibEntry> entry = ribIt->second;
174  auto routeIt = entry->findRoute(route);
175 
176  if (routeIt != entry->end()) {
177  beforeRemoveRoute(RibRouteRef{entry, routeIt});
178 
179  auto faceId = route.faceId;
180  entry->eraseRoute(routeIt);
181  m_nItems--;
182 
183  // If this RibEntry no longer has this faceId, unregister from face lookup table
184  if (!entry->hasFaceId(faceId)) {
185  auto range = m_faceEntries.equal_range(faceId);
186  for (auto it = range.first; it != range.second; ++it) {
187  if (it->second == entry) {
188  m_faceEntries.erase(it);
189  break;
190  }
191  }
192  }
193 
194  // If a RibEntry's route list is empty, remove it from the tree
195  if (entry->getRoutes().empty()) {
196  eraseEntry(ribIt);
197  }
198  }
199 }
200 
201 void
202 Rib::onRouteExpiration(const Name& prefix, const Route& route)
203 {
204  NFD_LOG_DEBUG(route << " for " << prefix << " has expired");
205 
206  RibUpdate update;
208  .setName(prefix)
209  .setRoute(route);
210 
211  beginApplyUpdate(update, nullptr, nullptr);
212 }
213 
214 shared_ptr<RibEntry>
215 Rib::findParent(const Name& prefix) const
216 {
217  for (int i = prefix.size() - 1; i >= 0; i--) {
218  auto it = m_rib.find(prefix.getPrefix(i));
219  if (it != m_rib.end()) {
220  return it->second;
221  }
222  }
223 
224  return nullptr;
225 }
226 
227 std::list<shared_ptr<RibEntry>>
228 Rib::findDescendants(const Name& prefix) const
229 {
230  std::list<shared_ptr<RibEntry>> children;
231 
232  RibTable::const_iterator it = m_rib.find(prefix);
233  if (it != m_rib.end()) {
234  ++it;
235  for (; it != m_rib.end(); ++it) {
236  if (prefix.isPrefixOf(it->first)) {
237  children.push_back((it->second));
238  }
239  else {
240  break;
241  }
242  }
243  }
244 
245  return children;
246 }
247 
248 std::list<shared_ptr<RibEntry>>
249 Rib::findDescendantsForNonInsertedName(const Name& prefix) const
250 {
251  std::list<shared_ptr<RibEntry>> children;
252 
253  for (const auto& pair : m_rib) {
254  if (prefix.isPrefixOf(pair.first)) {
255  children.push_back(pair.second);
256  }
257  }
258 
259  return children;
260 }
261 
262 Rib::RibTable::iterator
263 Rib::eraseEntry(RibTable::iterator it)
264 {
265  // Entry does not exist
266  if (it == m_rib.end()) {
267  return m_rib.end();
268  }
269 
270  shared_ptr<RibEntry> entry(it->second);
271 
272  shared_ptr<RibEntry> parent = entry->getParent();
273 
274  // Remove self from parent's children
275  if (parent != nullptr) {
276  parent->removeChild(entry);
277  }
278 
279  for (auto childIt = entry->getChildren().begin(); childIt != entry->getChildren().end(); ) {
280  shared_ptr<RibEntry> child = *childIt;
281 
282  // Advance iterator so it is not invalidated by removal
283  ++childIt;
284 
285  // Remove children from self
286  entry->removeChild(child);
287 
288  // Update parent's children
289  if (parent != nullptr) {
290  parent->addChild(child);
291  }
292  }
293 
294  auto nextIt = m_rib.erase(it);
295 
296  // do something after erasing an entry.
297  afterEraseEntry(entry->getName());
298 
299  return nextIt;
300 }
301 
302 Rib::RouteSet
303 Rib::getAncestorRoutes(const RibEntry& entry) const
304 {
305  RouteSet ancestorRoutes(&sortRoutes);
306 
307  shared_ptr<RibEntry> parent = entry.getParent();
308 
309  while (parent != nullptr) {
310  for (const Route& route : parent->getRoutes()) {
311  if (route.isChildInherit()) {
312  ancestorRoutes.insert(route);
313  }
314  }
315 
316  if (parent->hasCapture()) {
317  break;
318  }
319 
320  parent = parent->getParent();
321  }
322 
323  return ancestorRoutes;
324 }
325 
326 Rib::RouteSet
327 Rib::getAncestorRoutes(const Name& name) const
328 {
329  RouteSet ancestorRoutes(&sortRoutes);
330 
331  shared_ptr<RibEntry> parent = findParent(name);
332 
333  while (parent != nullptr) {
334  for (const Route& route : parent->getRoutes()) {
335  if (route.isChildInherit()) {
336  ancestorRoutes.insert(route);
337  }
338  }
339 
340  if (parent->hasCapture()) {
341  break;
342  }
343 
344  parent = parent->getParent();
345  }
346 
347  return ancestorRoutes;
348 }
349 
350 void
352  const Rib::UpdateSuccessCallback& onSuccess,
353  const Rib::UpdateFailureCallback& onFailure)
354 {
355  BOOST_ASSERT(m_fibUpdater != nullptr);
356 
357  addUpdateToQueue(update, onSuccess, onFailure);
358 
359  sendBatchFromQueue();
360 }
361 
362 void
363 Rib::beginRemoveFace(uint64_t faceId)
364 {
365  auto range = m_faceEntries.equal_range(faceId);
366  for (auto it = range.first; it != range.second; ++it) {
367  enqueueRemoveFace(*it->second, faceId);
368  }
369  sendBatchFromQueue();
370 }
371 
372 void
373 Rib::beginRemoveFailedFaces(const std::set<uint64_t>& activeFaceIds)
374 {
375  for (auto it = m_faceEntries.begin(); it != m_faceEntries.end(); ++it) {
376  if (activeFaceIds.count(it->first) > 0) {
377  continue;
378  }
379  enqueueRemoveFace(*it->second, it->first);
380  }
381  sendBatchFromQueue();
382 }
383 
384 void
385 Rib::enqueueRemoveFace(const RibEntry& entry, uint64_t faceId)
386 {
387  for (const Route& route : entry) {
388  if (route.faceId != faceId) {
389  continue;
390  }
391 
392  RibUpdate update;
394  .setName(entry.getName())
395  .setRoute(route);
396  addUpdateToQueue(update, nullptr, nullptr);
397  }
398 }
399 
400 void
401 Rib::addUpdateToQueue(const RibUpdate& update,
402  const Rib::UpdateSuccessCallback& onSuccess,
403  const Rib::UpdateFailureCallback& onFailure)
404 {
405  RibUpdateBatch batch(update.getRoute().faceId);
406  batch.add(update);
407 
408  UpdateQueueItem item{batch, onSuccess, onFailure};
409  m_updateBatches.push_back(std::move(item));
410 }
411 
412 void
413 Rib::sendBatchFromQueue()
414 {
415  if (m_updateBatches.empty() || m_isUpdateInProgress) {
416  return;
417  }
418 
419  m_isUpdateInProgress = true;
420 
421  UpdateQueueItem item = std::move(m_updateBatches.front());
422  m_updateBatches.pop_front();
423 
424  RibUpdateBatch& batch = item.batch;
425 
426  // Until task #1698, each RibUpdateBatch contains exactly one RIB update
427  BOOST_ASSERT(batch.size() == 1);
428 
429  auto fibSuccessCb = bind(&Rib::onFibUpdateSuccess, this, batch, _1, item.managerSuccessCallback);
430  auto fibFailureCb = bind(&Rib::onFibUpdateFailure, this, item.managerFailureCallback, _1, _2);
431 
432  m_fibUpdater->computeAndSendFibUpdates(batch, fibSuccessCb, fibFailureCb);
433 }
434 
435 void
436 Rib::onFibUpdateSuccess(const RibUpdateBatch& batch,
437  const RibUpdateList& inheritedRoutes,
438  const Rib::UpdateSuccessCallback& onSuccess)
439 {
440  for (const RibUpdate& update : batch) {
441  switch (update.getAction()) {
442  case RibUpdate::REGISTER:
443  insert(update.getName(), update.getRoute());
444  break;
447  erase(update.getName(), update.getRoute());
448  break;
449  }
450  }
451 
452  // Add and remove precalculated inherited routes to RibEntries
453  modifyInheritedRoutes(inheritedRoutes);
454 
455  m_isUpdateInProgress = false;
456 
457  if (onSuccess != nullptr) {
458  onSuccess();
459  }
460 
461  // Try to advance the batch queue
462  sendBatchFromQueue();
463 }
464 
465 void
466 Rib::onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
467  uint32_t code, const std::string& error)
468 {
469  m_isUpdateInProgress = false;
470 
471  if (onFailure != nullptr) {
472  onFailure(code, error);
473  }
474 
475  // Try to advance the batch queue
476  sendBatchFromQueue();
477 }
478 
479 void
480 Rib::modifyInheritedRoutes(const RibUpdateList& inheritedRoutes)
481 {
482  for (const RibUpdate& update : inheritedRoutes) {
483  auto ribIt = m_rib.find(update.getName());
484  BOOST_ASSERT(ribIt != m_rib.end());
485  shared_ptr<RibEntry> entry(ribIt->second);
486 
487  switch (update.getAction()) {
488  case RibUpdate::REGISTER:
489  entry->addInheritedRoute(update.getRoute());
490  break;
492  entry->removeInheritedRoute(update.getRoute());
493  break;
495  break;
496  }
497  }
498 }
499 
500 std::ostream&
501 operator<<(std::ostream& os, const Rib& rib)
502 {
503  for (const auto& item : rib) {
504  os << *item.second << "\n";
505  }
506 
507  return os;
508 }
509 
510 } // namespace rib
511 } // namespace nfd
references a route
Definition: rib.hpp:43
uint64_t faceId
Definition: route.hpp:81
RibUpdate & setRoute(const Route &route)
Definition: rib-update.hpp:107
represents the Routing Information Base
Definition: rib.hpp:59
shared_ptr< RibEntry > findParent(const Name &prefix) const
Definition: rib.cpp:215
signal::Signal< Rib, Name > afterEraseEntry
signals after a RIB entry is erased
Definition: rib.hpp:224
const Name & getName() const
Definition: rib-update.hpp:101
computes FibUpdates based on updates to the RIB and sends them to NFD
Definition: fib-updater.hpp:41
static bool sortRoutes(const Route &lhs, const Route &rhs)
Definition: rib.cpp:43
signal::Signal< Rib, Name > afterInsertEntry
signals after a RIB entry is inserted
Definition: rib.hpp:217
std::ostream & operator<<(std::ostream &os, const FibUpdate &update)
Definition: fib-update.hpp:74
RibTable::const_iterator const_iterator
Definition: rib.hpp:64
RibUpdate & setAction(Action action)
Definition: rib-update.hpp:81
Route * findLongestPrefix(const Name &prefix, const Route &route) const
Definition: rib.cpp:78
#define NFD_LOG_TRACE
Definition: logger.hpp:37
An update triggered by a face destruction notification.
Definition: rib-update.hpp:51
std::function< void(uint32_t code, const std::string &error)> UpdateFailureCallback
Definition: rib.hpp:107
Represents a collection of RibUpdates to be applied to a single FaceId.
signal::Signal< Rib, RibRouteRef > afterAddRoute
signals after a Route is added
Definition: rib.hpp:228
void setFibUpdater(FibUpdater *updater)
Definition: rib.cpp:49
std::list< shared_ptr< RibEntry > > RibEntryList
Definition: rib.hpp:62
Action getAction() const
Definition: rib-update.hpp:88
void add(const RibUpdate &update)
void computeAndSendFibUpdates(const RibUpdateBatch &batch, const FibUpdateSuccessCallback &onSuccess, const FibUpdateFailureCallback &onFailure)
computes FibUpdates using the provided RibUpdateBatch and then sends the updates to NFD&#39;s FIB ...
Definition: fib-updater.cpp:49
RibUpdate & setName(const Name &name)
Definition: rib-update.hpp:94
std::list< RibUpdate > RibUpdateList
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
void insert(const Name &prefix, const Route &route)
Definition: rib.cpp:92
RouteList::iterator iterator
Definition: rib-entry.hpp:42
represents a route for a name prefix
Definition: route.hpp:43
RibEntry::const_iterator route
Definition: rib.hpp:46
shared_ptr< RibEntry > entry
Definition: rib.hpp:45
signal::Signal< Rib, RibRouteRef > beforeRemoveRoute
signals before a route is removed
Definition: rib.hpp:232
#define NFD_LOG_DEBUG
Definition: logger.hpp:38
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
shared_ptr< RibEntry > getParent() const
Definition: rib-entry.hpp:235
Represents a RIB entry, which contains one or more Routes with the same prefix.
Definition: rib-entry.hpp:38
void beginRemoveFace(uint64_t faceId)
starts the FIB update process when a face has been destroyed
Definition: rib.cpp:363
void onRouteExpiration(const Name &prefix, const Route &route)
Definition: rib.cpp:202
const_iterator find(const Name &prefix) const
Definition: rib.cpp:55
bool operator<(const ReadvertisedRoute &lhs, const ReadvertisedRoute &rhs)
void beginRemoveFailedFaces(const std::set< uint64_t > &activeFaceIds)
Definition: rib.cpp:373
std::function< void()> UpdateSuccessCallback
Definition: rib.hpp:106
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:351
const Route & getRoute() const
Definition: rib-update.hpp:114