Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
Davide Pesavento | 87fc0f8 | 2018-04-11 23:43:51 -0400 | [diff] [blame] | 2 | /* |
| 3 | * Copyright (c) 2014-2018, Regents of the University of California, |
Alexander Afanasyev | 7c10b3b | 2015-01-20 12:24:27 -0800 | [diff] [blame] | 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 Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 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/>. |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 24 | */ |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 25 | |
| 26 | #ifndef NFD_RIB_RIB_HPP |
| 27 | #define NFD_RIB_RIB_HPP |
| 28 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 29 | #include "rib-entry.hpp" |
| 30 | #include "rib-update-batch.hpp" |
| 31 | |
Junxiao Shi | 25c6ce4 | 2016-09-09 13:49:59 +0000 | [diff] [blame] | 32 | #include <ndn-cxx/mgmt/nfd/control-parameters.hpp> |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 33 | |
| 34 | namespace nfd { |
| 35 | namespace rib { |
| 36 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 37 | using ndn::nfd::ControlParameters; |
| 38 | |
| 39 | class FibUpdater; |
| 40 | |
Nick Gordon | 89c4cca | 2016-11-02 15:42:32 +0000 | [diff] [blame] | 41 | /** \brief references a route |
| 42 | */ |
| 43 | struct RibRouteRef |
| 44 | { |
| 45 | shared_ptr<RibEntry> entry; |
| 46 | RibEntry::const_iterator route; |
| 47 | }; |
| 48 | |
Junxiao Shi | 89c0ea0 | 2017-03-06 19:52:05 +0000 | [diff] [blame] | 49 | bool |
| 50 | operator<(const RibRouteRef& lhs, const RibRouteRef& rhs); |
| 51 | |
Nick Gordon | 89c4cca | 2016-11-02 15:42:32 +0000 | [diff] [blame] | 52 | /** \brief represents the Routing Information Base |
| 53 | |
| 54 | The Routing Information Base contains a collection of Routes, each |
| 55 | represents a piece of static or dynamic routing information |
| 56 | registered by applications, operators, or NFD itself. Routes |
| 57 | associated with the same namespace are collected into a RIB entry. |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 58 | */ |
Alexander Afanasyev | 20d3144 | 2014-04-19 17:00:53 -0700 | [diff] [blame] | 59 | class Rib : noncopyable |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 60 | { |
| 61 | public: |
Vince Lehman | 218be0a | 2015-01-15 17:25:20 -0600 | [diff] [blame] | 62 | typedef std::list<shared_ptr<RibEntry>> RibEntryList; |
| 63 | typedef std::map<Name, shared_ptr<RibEntry>> RibTable; |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 64 | typedef RibTable::const_iterator const_iterator; |
Vince Lehman | 218be0a | 2015-01-15 17:25:20 -0600 | [diff] [blame] | 65 | typedef std::map<uint64_t, std::list<shared_ptr<RibEntry>>> FaceLookupTable; |
| 66 | typedef bool (*RouteComparePredicate)(const Route&, const Route&); |
| 67 | typedef std::set<Route, RouteComparePredicate> RouteSet; |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 68 | |
| 69 | Rib(); |
| 70 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 71 | ~Rib(); |
| 72 | |
| 73 | void |
| 74 | setFibUpdater(FibUpdater* updater); |
| 75 | |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 76 | const_iterator |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 77 | find(const Name& prefix) const; |
| 78 | |
Vince Lehman | 218be0a | 2015-01-15 17:25:20 -0600 | [diff] [blame] | 79 | Route* |
| 80 | find(const Name& prefix, const Route& route) const; |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 81 | |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 82 | const_iterator |
| 83 | begin() const; |
| 84 | |
| 85 | const_iterator |
| 86 | end() const; |
| 87 | |
| 88 | size_t |
| 89 | size() const; |
| 90 | |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 91 | bool |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 92 | empty() const; |
| 93 | |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 94 | shared_ptr<RibEntry> |
| 95 | findParent(const Name& prefix) const; |
| 96 | |
| 97 | /** \brief finds namespaces under the passed prefix |
| 98 | * \return{ a list of entries which are under the passed prefix } |
| 99 | */ |
Vince Lehman | 218be0a | 2015-01-15 17:25:20 -0600 | [diff] [blame] | 100 | std::list<shared_ptr<RibEntry>> |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 101 | findDescendants(const Name& prefix) const; |
| 102 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 103 | /** \brief finds namespaces under the passed prefix |
| 104 | * |
| 105 | * \note Unlike findDescendants, needs to find where prefix would fit in tree |
| 106 | * before collecting list of descendant prefixes |
| 107 | * |
| 108 | * \return{ a list of entries which would be under the passed prefix if the prefix |
| 109 | * existed in the RIB } |
| 110 | */ |
| 111 | std::list<shared_ptr<RibEntry>> |
| 112 | findDescendantsForNonInsertedName(const Name& prefix) const; |
| 113 | |
| 114 | public: |
Davide Pesavento | 87fc0f8 | 2018-04-11 23:43:51 -0400 | [diff] [blame] | 115 | using UpdateSuccessCallback = std::function<void()>; |
| 116 | using UpdateFailureCallback = std::function<void(uint32_t code, const std::string& error)>; |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 117 | |
| 118 | /** \brief passes the provided RibUpdateBatch to FibUpdater to calculate and send FibUpdates. |
| 119 | * |
| 120 | * If the FIB is updated successfully, onFibUpdateSuccess() will be called, and the |
| 121 | * RIB will be updated |
| 122 | * |
| 123 | * If the FIB update fails, onFibUpdateFailure() will be called, and the RIB will not |
| 124 | * be updated. |
| 125 | */ |
| 126 | void |
| 127 | beginApplyUpdate(const RibUpdate& update, |
| 128 | const UpdateSuccessCallback& onSuccess, |
| 129 | const UpdateFailureCallback& onFailure); |
| 130 | |
| 131 | /** \brief starts the FIB update process when a face has been destroyed |
| 132 | */ |
| 133 | void |
| 134 | beginRemoveFace(uint64_t faceId); |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 135 | |
| 136 | void |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 137 | onFibUpdateSuccess(const RibUpdateBatch& batch, |
| 138 | const RibUpdateList& inheritedRoutes, |
| 139 | const Rib::UpdateSuccessCallback& onSuccess); |
| 140 | |
| 141 | void |
| 142 | onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure, |
| 143 | uint32_t code, const std::string& error); |
| 144 | |
| 145 | void |
| 146 | onRouteExpiration(const Name& prefix, const Route& route); |
| 147 | |
Junxiao Shi | 9f5b01d | 2016-08-05 03:54:28 +0000 | [diff] [blame] | 148 | void |
| 149 | insert(const Name& prefix, const Route& route); |
| 150 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 151 | private: |
| 152 | /** \brief adds the passed update to a RibUpdateBatch and adds the batch to |
| 153 | * the end of the update queue. |
| 154 | * |
| 155 | * If an update is not in progress, the front update batch in the queue will be |
| 156 | * processed by the RIB. |
| 157 | * |
| 158 | * If an update is in progress, the added update will eventually be processed |
| 159 | * when it reaches the front of the queue; after other update batches are |
| 160 | * processed, the queue is advanced. |
| 161 | */ |
| 162 | void |
| 163 | addUpdateToQueue(const RibUpdate& update, |
| 164 | const Rib::UpdateSuccessCallback& onSuccess, |
| 165 | const Rib::UpdateFailureCallback& onFailure); |
| 166 | |
| 167 | /** \brief Attempts to send the front update batch in the queue. |
| 168 | * |
| 169 | * If an update is not in progress, the front update batch in the queue will be |
| 170 | * sent to the RIB for processing. |
| 171 | * |
| 172 | * If an update is in progress, nothing will be done. |
| 173 | */ |
| 174 | void |
| 175 | sendBatchFromQueue(); |
| 176 | |
| 177 | PUBLIC_WITH_TESTS_ELSE_PRIVATE: |
| 178 | // Used by RibManager unit-tests to get sent batch to simulate successful FIB update |
Davide Pesavento | 87fc0f8 | 2018-04-11 23:43:51 -0400 | [diff] [blame] | 179 | std::function<void(RibUpdateBatch)> m_onSendBatchFromQueue; |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 180 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 181 | void |
| 182 | erase(const Name& prefix, const Route& route); |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 183 | |
| 184 | private: |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 185 | RibTable::iterator |
| 186 | eraseEntry(RibTable::iterator it); |
| 187 | |
| 188 | void |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 189 | updateRib(const RibUpdateBatch& batch); |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 190 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 191 | /** \brief returns routes inherited from the entry's ancestors |
| 192 | * |
| 193 | * \return{ a list of inherited routes } |
| 194 | */ |
Vince Lehman | 218be0a | 2015-01-15 17:25:20 -0600 | [diff] [blame] | 195 | RouteSet |
| 196 | getAncestorRoutes(const RibEntry& entry) const; |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 197 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 198 | /** \brief returns routes inherited from the parent of the name and the parent's ancestors |
| 199 | * |
| 200 | * \note A parent is first found for the passed name before inherited routes are collected |
| 201 | * |
| 202 | * \return{ a list of inherited routes } |
| 203 | */ |
| 204 | RouteSet |
| 205 | getAncestorRoutes(const Name& name) const; |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 206 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 207 | /** \brief applies the passed inheritedRoutes and their actions to the corresponding RibEntries' |
| 208 | * inheritedRoutes lists |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 209 | */ |
| 210 | void |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 211 | modifyInheritedRoutes(const RibUpdateList& inheritedRoutes); |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 212 | |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 213 | PUBLIC_WITH_TESTS_ELSE_PRIVATE: |
| 214 | typedef std::pair<const Name&,const Route&> NameAndRoute; |
| 215 | |
| 216 | std::list<NameAndRoute> |
| 217 | findRoutesWithFaceId(uint64_t faceId); |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 218 | |
Yanbiao Li | c17de83 | 2014-11-21 17:51:45 -0800 | [diff] [blame] | 219 | public: |
Nick Gordon | 89c4cca | 2016-11-02 15:42:32 +0000 | [diff] [blame] | 220 | /** \brief signals after a RIB entry is inserted |
| 221 | * |
| 222 | * A RIB entry is inserted when the first route associated with a |
| 223 | * certain namespace is added. |
| 224 | */ |
Yanbiao Li | b9d439d | 2014-12-11 16:12:32 -0800 | [diff] [blame] | 225 | ndn::util::signal::Signal<Rib, Name> afterInsertEntry; |
Nick Gordon | 89c4cca | 2016-11-02 15:42:32 +0000 | [diff] [blame] | 226 | |
| 227 | /** \brief signals after a RIB entry is erased |
| 228 | * |
| 229 | * A RIB entry is erased when the last route associated with a |
| 230 | * certain namespace is removed. |
| 231 | */ |
| 232 | |
Yanbiao Li | b9d439d | 2014-12-11 16:12:32 -0800 | [diff] [blame] | 233 | ndn::util::signal::Signal<Rib, Name> afterEraseEntry; |
Yanbiao Li | c17de83 | 2014-11-21 17:51:45 -0800 | [diff] [blame] | 234 | |
Nick Gordon | 89c4cca | 2016-11-02 15:42:32 +0000 | [diff] [blame] | 235 | /** \brief signals after a Route is added |
| 236 | */ |
| 237 | ndn::util::signal::Signal<Rib, RibRouteRef> afterAddRoute; |
| 238 | |
| 239 | /** \brief signals before a route is removed |
| 240 | */ |
| 241 | ndn::util::signal::Signal<Rib, RibRouteRef> beforeRemoveRoute; |
| 242 | |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 243 | private: |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 244 | RibTable m_rib; |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 245 | FaceLookupTable m_faceMap; |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 246 | FibUpdater* m_fibUpdater; |
Vince Lehman | 4387e78 | 2014-06-19 16:57:45 -0500 | [diff] [blame] | 247 | |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 248 | size_t m_nItems; |
Vince Lehman | 76c751c | 2014-11-18 17:36:38 -0600 | [diff] [blame] | 249 | |
| 250 | friend class FibUpdater; |
| 251 | |
| 252 | private: |
| 253 | struct UpdateQueueItem |
| 254 | { |
| 255 | RibUpdateBatch batch; |
| 256 | const Rib::UpdateSuccessCallback managerSuccessCallback; |
| 257 | const Rib::UpdateFailureCallback managerFailureCallback; |
| 258 | }; |
| 259 | |
| 260 | PUBLIC_WITH_TESTS_ELSE_PRIVATE: |
| 261 | typedef std::list<UpdateQueueItem> UpdateQueue; |
| 262 | UpdateQueue m_updateBatches; |
| 263 | |
| 264 | private: |
| 265 | bool m_isUpdateInProgress; |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 266 | }; |
| 267 | |
| 268 | inline Rib::const_iterator |
| 269 | Rib::begin() const |
| 270 | { |
| 271 | return m_rib.begin(); |
| 272 | } |
| 273 | |
| 274 | inline Rib::const_iterator |
| 275 | Rib::end() const |
| 276 | { |
| 277 | return m_rib.end(); |
| 278 | } |
| 279 | |
| 280 | inline size_t |
| 281 | Rib::size() const |
| 282 | { |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 283 | return m_nItems; |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 284 | } |
| 285 | |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 286 | inline bool |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 287 | Rib::empty() const |
| 288 | { |
| 289 | return m_rib.empty(); |
| 290 | } |
| 291 | |
Vince | 12e4946 | 2014-06-09 13:29:32 -0500 | [diff] [blame] | 292 | std::ostream& |
| 293 | operator<<(std::ostream& os, const Rib& rib); |
| 294 | |
Alexander Afanasyev | 3ecec50 | 2014-04-16 13:42:44 -0700 | [diff] [blame] | 295 | } // namespace rib |
| 296 | } // namespace nfd |
| 297 | |
| 298 | #endif // NFD_RIB_RIB_HPP |