blob: c76940b7dd1b3a1a0ae995e7dbb07ce2f0698d1c [file] [log] [blame]
Alexander Afanasyev3ecec502014-04-16 13:42:44 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Vince12e49462014-06-09 13:29:32 -05003 * Copyright (c) 2014, 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
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070010 *
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/>.
Vince12e49462014-06-09 13:29:32 -050024 */
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070025
26#include "rib.hpp"
27
Vince Lehman281ded72014-08-21 12:17:08 -050028#include "core/logger.hpp"
29
30NFD_LOG_INIT("Rib");
31
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070032namespace nfd {
33namespace rib {
34
Vince Lehman4387e782014-06-19 16:57:45 -050035static inline bool
36sortFace(const FaceEntry& entry1, const FaceEntry& entry2)
37{
38 return entry1.faceId < entry2.faceId;
39}
40
41static inline bool
42isChildInheritFlagSet(uint64_t flags)
43{
44 return flags & ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
45}
46
47static inline bool
48isCaptureFlagSet(uint64_t flags)
49{
50 return flags & ndn::nfd::ROUTE_FLAG_CAPTURE;
51}
52
53static inline bool
54isAnyFlagSet(uint64_t flags)
55{
56 return isChildInheritFlagSet(flags) || isCaptureFlagSet(flags);
57}
58
59static inline bool
60areBothFlagsSet(uint64_t flags)
61{
62 return isChildInheritFlagSet(flags) && isCaptureFlagSet(flags);
63}
64
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070065Rib::Rib()
Vince12e49462014-06-09 13:29:32 -050066 : m_nItems(0)
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070067{
68}
69
70
71Rib::~Rib()
72{
73}
74
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070075Rib::const_iterator
Vince12e49462014-06-09 13:29:32 -050076Rib::find(const Name& prefix) const
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070077{
Vince12e49462014-06-09 13:29:32 -050078 return m_rib.find(prefix);
79}
80
Syed Obaid3313a372014-07-01 01:31:33 -050081FaceEntry*
Vince12e49462014-06-09 13:29:32 -050082Rib::find(const Name& prefix, const FaceEntry& face) const
83{
84 RibTable::const_iterator ribIt = m_rib.find(prefix);
85
86 // Name prefix exists
87 if (ribIt != m_rib.end())
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070088 {
Vince12e49462014-06-09 13:29:32 -050089 shared_ptr<RibEntry> entry(ribIt->second);
90
Syed Obaid3313a372014-07-01 01:31:33 -050091 RibEntry::iterator faceIt = std::find_if(entry->begin(), entry->end(),
Vince12e49462014-06-09 13:29:32 -050092 bind(&compareFaceIdAndOrigin, _1, face));
93
94 if (faceIt != entry->end())
95 {
Syed Obaid3313a372014-07-01 01:31:33 -050096 return &((*faceIt));
Vince12e49462014-06-09 13:29:32 -050097 }
Alexander Afanasyev3ecec502014-04-16 13:42:44 -070098 }
Syed Obaid3313a372014-07-01 01:31:33 -050099 return 0;
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700100}
101
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700102void
Vince12e49462014-06-09 13:29:32 -0500103Rib::insert(const Name& prefix, const FaceEntry& face)
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700104{
Vince12e49462014-06-09 13:29:32 -0500105 RibTable::iterator ribIt = m_rib.find(prefix);
106
107 // Name prefix exists
108 if (ribIt != m_rib.end())
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700109 {
Vince12e49462014-06-09 13:29:32 -0500110 shared_ptr<RibEntry> entry(ribIt->second);
111
112 RibEntry::iterator faceIt = std::find_if(entry->getFaces().begin(),
113 entry->getFaces().end(),
114 bind(&compareFaceIdAndOrigin, _1, face));
115
116 if (faceIt == entry->end())
117 {
Vince Lehman4387e782014-06-19 16:57:45 -0500118 // Will the new face change the namespace's capture flag?
119 bool captureWasTurnedOn = (entry->hasCapture() == false && isCaptureFlagSet(face.flags));
120
Vince12e49462014-06-09 13:29:32 -0500121 // New face
122 entry->insertFace(face);
123 m_nItems++;
124
125 // Register with face lookup table
126 m_faceMap[face.faceId].push_back(entry);
Vince Lehman4387e782014-06-19 16:57:45 -0500127
128 createFibUpdatesForNewFaceEntry(*entry, face, captureWasTurnedOn);
Vince12e49462014-06-09 13:29:32 -0500129 }
Vince Lehman4387e782014-06-19 16:57:45 -0500130 else // Entry exists, update fields
Vince12e49462014-06-09 13:29:32 -0500131 {
Syed Obaid3313a372014-07-01 01:31:33 -0500132 // First cancel old scheduled event, if any, then set the EventId to new one
133 if (static_cast<bool>(faceIt->getExpirationEvent()))
Vince Lehman281ded72014-08-21 12:17:08 -0500134 {
135 NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " "
136 << *faceIt);
Syed Obaid3313a372014-07-01 01:31:33 -0500137 scheduler::cancel(faceIt->getExpirationEvent());
Vince Lehman281ded72014-08-21 12:17:08 -0500138 }
Syed Obaid3313a372014-07-01 01:31:33 -0500139
140 // No checks are required here as the iterator needs to be updated in all cases.
141 faceIt->setExpirationEvent(face.getExpirationEvent());
142
Vince Lehman4387e782014-06-19 16:57:45 -0500143 // Save flags for update processing
144 uint64_t previousFlags = faceIt->flags;
145
146 // If the entry's cost didn't change and child inherit is not set,
147 // no need to traverse subtree.
148 uint64_t previousCost = faceIt->cost;
149
Vince12e49462014-06-09 13:29:32 -0500150 faceIt->flags = face.flags;
151 faceIt->cost = face.cost;
152 faceIt->expires = face.expires;
Vince Lehman4387e782014-06-19 16:57:45 -0500153
154 createFibUpdatesForUpdatedEntry(*entry, face, previousFlags, previousCost);
Vince12e49462014-06-09 13:29:32 -0500155 }
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700156 }
Vince12e49462014-06-09 13:29:32 -0500157 else // New name prefix
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700158 {
Vince12e49462014-06-09 13:29:32 -0500159 shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));
160
161 m_rib[prefix] = entry;
162 m_nItems++;
163
164 entry->setName(prefix);
165 entry->insertFace(face);
166
167 // Find prefix's parent
168 shared_ptr<RibEntry> parent = findParent(prefix);
169
170 // Add self to parent's children
171 if (static_cast<bool>(parent))
172 {
173 parent->addChild(entry);
174 }
175
176 RibEntryList children = findDescendants(prefix);
177
178 for (std::list<shared_ptr<RibEntry> >::iterator child = children.begin();
179 child != children.end(); ++child)
180 {
181 if ((*child)->getParent() == parent)
182 {
183 // Remove child from parent and inherit parent's child
184 if (static_cast<bool>(parent))
185 {
186 parent->removeChild((*child));
187 }
Vince12e49462014-06-09 13:29:32 -0500188 entry->addChild((*child));
189 }
190 }
191
192 // Register with face lookup table
193 m_faceMap[face.faceId].push_back(entry);
Vince Lehman4387e782014-06-19 16:57:45 -0500194
195 createFibUpdatesForNewRibEntry(*entry, face);
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700196 }
197}
198
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700199void
Vince12e49462014-06-09 13:29:32 -0500200Rib::erase(const Name& prefix, const FaceEntry& face)
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700201{
Vince12e49462014-06-09 13:29:32 -0500202 RibTable::iterator ribIt = m_rib.find(prefix);
203
204 // Name prefix exists
205 if (ribIt != m_rib.end())
206 {
207 shared_ptr<RibEntry> entry(ribIt->second);
208
Vince Lehman4387e782014-06-19 16:57:45 -0500209 const bool hadCapture = entry->hasCapture();
210
211 // Need to copy face to do FIB updates with correct cost and flags since nfdc does not
212 // pass flags or cost
213 RibEntry::iterator faceIt = entry->findFace(face);
Vince Lehman4387e782014-06-19 16:57:45 -0500214
215 if (faceIt != entry->end())
Vince12e49462014-06-09 13:29:32 -0500216 {
Syed Obaid3313a372014-07-01 01:31:33 -0500217 FaceEntry faceToErase = *faceIt;
218 faceToErase.flags = faceIt->flags;
219 faceToErase.cost = faceIt->cost;
220
Vince Lehman4387e782014-06-19 16:57:45 -0500221 entry->eraseFace(faceIt);
Vince Lehman281ded72014-08-21 12:17:08 -0500222
Vince12e49462014-06-09 13:29:32 -0500223 m_nItems--;
224
Vince Lehman4387e782014-06-19 16:57:45 -0500225 const bool captureWasTurnedOff = (hadCapture && !entry->hasCapture());
226
227 createFibUpdatesForErasedFaceEntry(*entry, faceToErase, captureWasTurnedOff);
228
Vince12e49462014-06-09 13:29:32 -0500229 // If this RibEntry no longer has this faceId, unregister from face lookup table
230 if (!entry->hasFaceId(face.faceId))
231 {
232 m_faceMap[face.faceId].remove(entry);
233 }
Vince Lehman4387e782014-06-19 16:57:45 -0500234 else
235 {
236 // The RibEntry still has the face ID; need to update FIB
237 // with lowest cost for the same face instead of removing the face from the FIB
238 shared_ptr<FaceEntry> lowCostFace = entry->getFaceWithLowestCostByFaceId(face.faceId);
239
240 BOOST_ASSERT(static_cast<bool>(lowCostFace));
241
242 createFibUpdatesForNewFaceEntry(*entry, *lowCostFace, false);
243 }
Vince12e49462014-06-09 13:29:32 -0500244
245 // If a RibEntry's facelist is empty, remove it from the tree
246 if (entry->getFaces().size() == 0)
247 {
248 eraseEntry(ribIt);
249 }
250 }
251 }
252}
253
254void
255Rib::erase(const uint64_t faceId)
256{
257 FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);
258
259 // No RIB entries have this face
260 if (lookupIt == m_faceMap.end())
261 {
262 return;
263 }
264
265 RibEntryList& ribEntries = lookupIt->second;
266
267 // For each RIB entry that has faceId, remove the face from the entry
268 for (RibEntryList::iterator entryIt = ribEntries.begin(); entryIt != ribEntries.end(); ++entryIt)
269 {
270 shared_ptr<RibEntry> entry = *entryIt;
271
Vince Lehman4387e782014-06-19 16:57:45 -0500272 const bool hadCapture = entry->hasCapture();
273
Vince12e49462014-06-09 13:29:32 -0500274 // Find the faces in the entry
275 for (RibEntry::iterator faceIt = entry->begin(); faceIt != entry->end(); ++faceIt)
276 {
277 if (faceIt->faceId == faceId)
278 {
Vince Lehman4387e782014-06-19 16:57:45 -0500279 FaceEntry copy = *faceIt;
280
Vince12e49462014-06-09 13:29:32 -0500281 faceIt = entry->eraseFace(faceIt);
Vince Lehman4387e782014-06-19 16:57:45 -0500282
283 const bool captureWasTurnedOff = (hadCapture && !entry->hasCapture());
284 createFibUpdatesForErasedFaceEntry(*entry, copy, captureWasTurnedOff);
Vince12e49462014-06-09 13:29:32 -0500285 }
286 }
287
288 // If a RibEntry's facelist is empty, remove it from the tree
289 if (entry->getFaces().size() == 0)
290 {
291 eraseEntry(m_rib.find(entry->getName()));
292 }
293 }
294
295 // Face no longer exists, remove from face lookup table
296 FaceLookupTable::iterator entryToDelete = m_faceMap.find(faceId);
297
298 if (entryToDelete != m_faceMap.end())
299 {
300 m_faceMap.erase(entryToDelete);
301 }
302}
303
304shared_ptr<RibEntry>
305Rib::findParent(const Name& prefix) const
306{
307 for (int i = prefix.size() - 1; i >= 0; i--)
308 {
309 RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));
310 if (it != m_rib.end())
311 {
312 return (it->second);
313 }
314 }
315
316 return shared_ptr<RibEntry>();
317}
318
319std::list<shared_ptr<RibEntry> >
320Rib::findDescendants(const Name& prefix) const
321{
322 std::list<shared_ptr<RibEntry> > children;
323
324 RibTable::const_iterator it = m_rib.find(prefix);
325
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700326 if (it != m_rib.end())
327 {
Vince12e49462014-06-09 13:29:32 -0500328 ++it;
329 for (; it != m_rib.end(); ++it)
330 {
331 if (prefix.isPrefixOf(it->first))
332 {
333 children.push_back((it->second));
334 }
335 else
336 {
337 break;
338 }
339 }
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700340 }
Vince12e49462014-06-09 13:29:32 -0500341
342 return children;
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700343}
344
Vince12e49462014-06-09 13:29:32 -0500345Rib::RibTable::iterator
346Rib::eraseEntry(RibTable::iterator it)
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700347{
Vince12e49462014-06-09 13:29:32 -0500348 // Entry does not exist
349 if (it == m_rib.end())
350 {
351 return m_rib.end();
352 }
353
354 shared_ptr<RibEntry> entry(it->second);
355
Vince Lehman4387e782014-06-19 16:57:45 -0500356 // Remove inherited routes from namespace
357 createFibUpdatesForErasedRibEntry(*entry);
358
Vince12e49462014-06-09 13:29:32 -0500359 shared_ptr<RibEntry> parent = entry->getParent();
360
361 // Remove self from parent's children
362 if (static_cast<bool>(parent))
363 {
364 parent->removeChild(entry);
365 }
366
367 std::list<shared_ptr<RibEntry> > children = entry->getChildren();
368
369 for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
370 {
371 // Remove children from self
372 entry->removeChild(*child);
373
374 // Update parent's children
375 if (static_cast<bool>(parent))
376 {
377 parent->addChild(*child);
378 }
379 }
380
381 // Must save and advance iterator to return a valid iterator
382 RibTable::iterator nextIt = it;
383 nextIt++;
384
385 m_rib.erase(it);
386
387 return nextIt;
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700388}
389
Vince Lehman4387e782014-06-19 16:57:45 -0500390bool
391compareFibUpdates(const shared_ptr<const FibUpdate> lhs, const shared_ptr<const FibUpdate> rhs)
392{
393 return ((lhs->name == rhs->name) &&
394 (lhs->faceId == rhs->faceId));
395}
396
397void
398Rib::insertFibUpdate(shared_ptr<FibUpdate> update)
399{
400 // If an update with the same name and face already exists,
401 // replace it
402 FibUpdateList::iterator it = std::find_if(m_fibUpdateList.begin(), m_fibUpdateList.end(),
403 bind(&compareFibUpdates, _1, update));
404
405 if (it != m_fibUpdateList.end())
406 {
407 // Get rid of the const to alter the action, prevents copying or removal and
408 // insertion
409 FibUpdate& entry = const_cast<FibUpdate&>(*(*it));
410 entry.action = update->action;
411 entry.cost = update->cost;
412 }
413 else
414 {
415 m_fibUpdateList.push_back(update);
416 }
417}
418
419void
420Rib::createFibUpdatesForNewRibEntry(RibEntry& entry, const FaceEntry& face)
421{
422 // Create FIB update for new entry
423 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), face.faceId, face.cost));
424
425 // No flags are set
426 if (!isAnyFlagSet(face.flags))
427 {
428 // Add ancestor faces to self
429 addInheritedFacesToEntry(entry, getAncestorFaces(entry));
430 }
431 else if (areBothFlagsSet(face.flags))
432 {
433 // Add face to children
434 FaceSet facesToAdd;
435 facesToAdd.insert(face);
436
437 // Remove faces blocked by capture and add self to children
438 modifyChildrensInheritedFaces(entry, facesToAdd, getAncestorFaces(entry));
439 }
440 else if (isChildInheritFlagSet(face.flags))
441 {
442 FaceSet ancestorFaces = getAncestorFaces(entry);
443
444 // Add ancestor faces to self
445 addInheritedFacesToEntry(entry, ancestorFaces);
446
447 // If there is an ancestor face which is the same as the new face, replace it
448 // with the new face
449 FaceSet::iterator it = ancestorFaces.find(face);
450
451 // There is a face that needs to be overwritten, erase and then replace
452 if (it != ancestorFaces.end())
453 {
454 ancestorFaces.erase(it);
455 }
456
457 // Add new face to ancestor list so it can be added to children
458 ancestorFaces.insert(face);
459
460 // Add ancestor faces to children
461 modifyChildrensInheritedFaces(entry, ancestorFaces, FaceSet());
462 }
463 else if (isCaptureFlagSet(face.flags))
464 {
465 // Remove faces blocked by capture
466 modifyChildrensInheritedFaces(entry, FaceSet(), getAncestorFaces(entry));
467 }
468}
469
470void
471Rib::createFibUpdatesForNewFaceEntry(RibEntry& entry, const FaceEntry& face,
472 bool captureWasTurnedOn)
473{
474 // Only update if the new face has a lower cost than a previously installed face
475 shared_ptr<FaceEntry> prevFace = entry.getFaceWithLowestCostAndChildInheritByFaceId(face.faceId);
476
477 FaceSet facesToAdd;
478 if (isChildInheritFlagSet(face.flags))
479 {
480 // Add to children if this new face doesn't override a previous lower cost, or
481 // add to children if this new is lower cost than a previous face.
482 // Less than equal, since entry may find this face
483 if (!static_cast<bool>(prevFace) || face.cost <= prevFace->cost)
484 {
485 // Add self to children
486 facesToAdd.insert(face);
487 }
488 }
489
490 FaceSet facesToRemove;
491 if (captureWasTurnedOn)
492 {
493 // Capture flag on
494 facesToRemove = getAncestorFaces(entry);
495
496 // Remove ancestor faces from self
497 removeInheritedFacesFromEntry(entry, facesToRemove);
498 }
499
500 modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
501
502 // If another face with same faceId and lower cost, don't update.
503 // Must be done last so that add updates replace removal updates
504 // Create FIB update for new entry
505 if (face.cost <= entry.getFaceWithLowestCostByFaceId(face.faceId)->cost)
506 {
507 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), face.faceId, face.cost));
508 }
509}
510
511void
512Rib::createFibUpdatesForUpdatedEntry(RibEntry& entry, const FaceEntry& face,
513 const uint64_t previousFlags, const uint64_t previousCost)
514{
515 const bool costDidChange = (face.cost != previousCost);
516
517 // Look for an installed face with the lowest cost and child inherit set
518 shared_ptr<FaceEntry> prevFace = entry.getFaceWithLowestCostAndChildInheritByFaceId(face.faceId);
519
520 // No flags changed and cost didn't change, no change in FIB
521 if (face.flags == previousFlags && !costDidChange)
522 {
523 return;
524 }
525
526 // Cost changed so create update for the entry itself
527 if (costDidChange)
528 {
529 // Create update if this face's cost is lower than other faces
530 if (face.cost <= entry.getFaceWithLowestCostByFaceId(face.faceId)->cost)
531 {
532 // Create FIB update for the updated entry
533 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), face.faceId, face.cost));
534 }
535 else if (previousCost < entry.getFaceWithLowestCostByFaceId(face.faceId)->cost)
536 {
537 // Create update if this face used to be the lowest face but is no longer
538 // the lowest cost face.
539 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), prevFace->faceId,
540 prevFace->cost));
541 }
542
543 // If another face with same faceId and lower cost and ChildInherit exists,
544 // don't update children.
545 if (!static_cast<bool>(prevFace) || face.cost <= prevFace->cost)
546 {
547 // If no flags changed but child inheritance is set, need to update children
548 // with new cost
549 if ((face.flags == previousFlags) && isChildInheritFlagSet(face.flags))
550 {
551 // Add self to children
552 FaceSet facesToAdd;
553 facesToAdd.insert(face);
554 modifyChildrensInheritedFaces(entry, facesToAdd, FaceSet());
555
556 return;
557 }
558 }
559 }
560
561 // Child inherit was turned on
562 if (!isChildInheritFlagSet(previousFlags) && isChildInheritFlagSet(face.flags))
563 {
564 // If another face with same faceId and lower cost and ChildInherit exists,
565 // don't update children.
566 if (!static_cast<bool>(prevFace) || face.cost <= prevFace->cost)
567 {
568 // Add self to children
569 FaceSet facesToAdd;
570 facesToAdd.insert(face);
571 modifyChildrensInheritedFaces(entry, facesToAdd, FaceSet());
572 }
573
574 } // Child inherit was turned off
575 else if (isChildInheritFlagSet(previousFlags) && !isChildInheritFlagSet(face.flags))
576 {
577 // Remove self from children
578 FaceSet facesToRemove;
579 facesToRemove.insert(face);
580
581 FaceSet facesToAdd;
582 // If another face with same faceId and ChildInherit exists, update children with this face.
583 if (static_cast<bool>(prevFace))
584 {
585 facesToAdd.insert(*prevFace);
586 }
587 else
588 {
589 // Look for an ancestor that was blocked previously
590 const FaceSet ancestorFaces = getAncestorFaces(entry);
591 FaceSet::iterator it = ancestorFaces.find(face);
592
593 // If an ancestor is found, add it to children
594 if (it != ancestorFaces.end())
595 {
596 facesToAdd.insert(*it);
597 }
598 }
599
600 modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
601 }
602
603 // Capture was turned on
604 if (!isCaptureFlagSet(previousFlags) && isCaptureFlagSet(face.flags))
605 {
606 FaceSet ancestorFaces = getAncestorFaces(entry);
607
608 // Remove ancestor faces from self
609 removeInheritedFacesFromEntry(entry, ancestorFaces);
610
611 // Remove ancestor faces from children
612 modifyChildrensInheritedFaces(entry, FaceSet(), ancestorFaces);
613 } // Capture was turned off
614 else if (isCaptureFlagSet(previousFlags) && !isCaptureFlagSet(face.flags))
615 {
616 FaceSet ancestorFaces = getAncestorFaces(entry);
617
618 // Add ancestor faces to self
619 addInheritedFacesToEntry(entry, ancestorFaces);
620
621 // Add ancestor faces to children
622 modifyChildrensInheritedFaces(entry, ancestorFaces, FaceSet());
623 }
624}
625
626void
627Rib::createFibUpdatesForErasedFaceEntry(RibEntry& entry, const FaceEntry& face,
628 const bool captureWasTurnedOff)
629{
630 insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), face.faceId));
631
632 if (areBothFlagsSet(face.flags))
633 {
634 // Remove self from children
635 FaceSet facesToRemove;
636 facesToRemove.insert(face);
637
638 // If capture is turned off for the route, need to add ancestors
639 // to self and children
640 FaceSet facesToAdd;
641 if (captureWasTurnedOff)
642 {
643 // Look for an ancestors that were blocked previously
644 facesToAdd = getAncestorFaces(entry);
645
646 // Add ancestor faces to self
647 addInheritedFacesToEntry(entry, facesToAdd);
648 }
649
650 modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
651 }
652 else if (isChildInheritFlagSet(face.flags))
653 {
654 // If not blocked by capture, add inherited routes to children
655 FaceSet facesToAdd;
656 if (!entry.hasCapture())
657 {
658 facesToAdd = getAncestorFaces(entry);
659 }
660
661 FaceSet facesToRemove;
662 facesToRemove.insert(face);
663
664 // Add ancestor faces to children
665 modifyChildrensInheritedFaces(entry, facesToAdd, facesToRemove);
666 }
667 else if (isCaptureFlagSet(face.flags))
668 {
669 // If capture is turned off for the route, need to add ancestors
670 // to self and children
671 FaceSet facesToAdd;
672 if (captureWasTurnedOff)
673 {
674 // Look for an ancestors that were blocked previously
675 facesToAdd = getAncestorFaces(entry);
676
677 // Add ancestor faces to self
678 addInheritedFacesToEntry(entry, facesToAdd);
679 }
680
681 modifyChildrensInheritedFaces(entry, facesToAdd, FaceSet());
682 }
683
684 // Need to check if the removed face was blocking an inherited route
685 FaceSet ancestorFaces = getAncestorFaces(entry);
686
687 if (!entry.hasCapture())
688 {
689 // If there is an ancestor face which is the same as the erased face, add that face
690 // to the current entry
691 FaceSet::iterator it = ancestorFaces.find(face);
692
693 if (it != ancestorFaces.end())
694 {
695 entry.addInheritedFace(*it);
696 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
697 }
698 }
699}
700
701void
702Rib::createFibUpdatesForErasedRibEntry(RibEntry& entry)
703{
704 for (RibEntry::FaceList::iterator it = entry.getInheritedFaces().begin();
705 it != entry.getInheritedFaces().end(); ++it)
706 {
707 insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), it->faceId));
708 }
709}
710
711Rib::FaceSet
712Rib::getAncestorFaces(const RibEntry& entry) const
713{
714 FaceSet ancestorFaces(&sortFace);
715
716 shared_ptr<RibEntry> parent = entry.getParent();
717
718 while (static_cast<bool>(parent))
719 {
720 for (RibEntry::iterator it = parent->getFaces().begin();
721 it != parent->getFaces().end(); ++it)
722 {
723 if (isChildInheritFlagSet(it->flags))
724 {
725 ancestorFaces.insert(*it);
726 }
727 }
728
729 if (parent->hasCapture())
730 {
731 break;
732 }
733
734 parent = parent->getParent();
735 }
736
737 return ancestorFaces;
738}
739
740void
741Rib::addInheritedFacesToEntry(RibEntry& entry, const Rib::FaceSet& facesToAdd)
742{
743 for (FaceSet::const_iterator it = facesToAdd.begin(); it != facesToAdd.end(); ++it)
744 {
745 // Don't add an ancestor faceId if the namespace has an entry for that faceId
746 if (!entry.hasFaceId(it->faceId))
747 {
748 entry.addInheritedFace(*it);
749 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), it->faceId, it->cost));
750 }
751 }
752}
753
754void
755Rib::removeInheritedFacesFromEntry(RibEntry& entry, const Rib::FaceSet& facesToRemove)
756{
757 for (FaceSet::const_iterator it = facesToRemove.begin(); it != facesToRemove.end(); ++it)
758 {
759 // Only remove if the face has been inherited
760 if (entry.hasInheritedFace(*it))
761 {
762 entry.removeInheritedFace(*it);
763 insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), it->faceId));
764 }
765 }
766}
767
768void
769Rib::modifyChildrensInheritedFaces(RibEntry& entry, const Rib::FaceSet& facesToAdd,
770 const Rib::FaceSet& facesToRemove)
771{
772 RibEntryList children = entry.getChildren();
773
774 for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
775 {
776 traverseSubTree(*(*child), facesToAdd, facesToRemove);
777 }
778}
779
780void
781Rib::traverseSubTree(RibEntry& entry, Rib::FaceSet facesToAdd,
782 Rib::FaceSet facesToRemove)
783{
784 // If a route on the namespace has the capture flag set, ignore self and children
785 if (entry.hasCapture())
786 {
787 return;
788 }
789
790 // Remove inherited faces from current namespace
791 for (Rib::FaceSet::const_iterator removeIt = facesToRemove.begin();
792 removeIt != facesToRemove.end(); )
793 {
794 // If a route on the namespace has the same face and child inheritance set, ignore this face
795 if (entry.hasChildInheritOnFaceId(removeIt->faceId))
796 {
797 facesToRemove.erase(removeIt++);
798 continue;
799 }
800
801 // Only remove face if it removes an existing inherited route
802 if (entry.hasInheritedFace(*removeIt))
803 {
804 entry.removeInheritedFace(*removeIt);
805 insertFibUpdate(FibUpdate::createRemoveUpdate(entry.getName(), removeIt->faceId));
806 }
807
808 ++removeIt;
809 }
810
811 // Add inherited faces to current namespace
812 for (Rib::FaceSet::const_iterator addIt = facesToAdd.begin();
813 addIt != facesToAdd.end(); )
814 {
815 // If a route on the namespace has the same face and child inherit set, ignore this face
816 if (entry.hasChildInheritOnFaceId(addIt->faceId))
817 {
818 facesToAdd.erase(addIt++);
819 continue;
820 }
821
822 // Only add face if it does not override an existing route
823 if (!entry.hasFaceId(addIt->faceId))
824 {
825 RibEntry::FaceList::iterator faceIt = entry.findInheritedFace(*addIt);
826
827 // If the entry already has the inherited face, just update the face
828 if (faceIt != entry.getInheritedFaces().end())
829 {
830 faceIt->cost = addIt->cost;
831 }
832 else // Otherwise, this is a newly inherited face
833 {
834 entry.addInheritedFace(*addIt);
835 }
836
837 insertFibUpdate(FibUpdate::createAddUpdate(entry.getName(), addIt->faceId, addIt->cost));
838 }
839
840 ++addIt;
841 }
842
843 Rib::RibEntryList children = entry.getChildren();
844
845 // Apply face operations to current namespace's children
846 for (Rib::RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
847 {
848 traverseSubTree(*(*child), facesToAdd, facesToRemove);
849 }
850}
851
Alexander Afanasyev20d31442014-04-19 17:00:53 -0700852std::ostream&
Vince12e49462014-06-09 13:29:32 -0500853operator<<(std::ostream& os, const Rib& rib)
Alexander Afanasyev20d31442014-04-19 17:00:53 -0700854{
Vince12e49462014-06-09 13:29:32 -0500855 for (Rib::RibTable::const_iterator it = rib.begin(); it != rib.end(); ++it)
856 {
857 os << *(it->second) << "\n";
858 }
Alexander Afanasyev20d31442014-04-19 17:00:53 -0700859
860 return os;
861}
862
Alexander Afanasyev3ecec502014-04-16 13:42:44 -0700863} // namespace rib
864} // namespace nfd