Line data Source code
1 : /*
2 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
3 : * Copyright Contributors to the OpenSDN project
4 : */
5 :
6 : #include "bgp/bgp_multicast.h"
7 :
8 : #include <boost/bind/bind.hpp>
9 : #include <boost/foreach.hpp>
10 :
11 : #include "base/string_util.h"
12 : #include "base/task_annotations.h"
13 : #include "bgp/bgp_log.h"
14 : #include "bgp/bgp_mvpn.h"
15 : #include "bgp/bgp_server.h"
16 : #include "bgp/bgp_update.h"
17 : #include "bgp/ermvpn/ermvpn_table.h"
18 : #include "bgp/mvpn/mvpn_route.h"
19 : #include "bgp/routing-instance/routing_instance.h"
20 : #include "bgp/routing-instance/routing_instance_analytics_types.h"
21 : #include "bgp/routing-instance/routing_instance_log.h"
22 : #include "bgp/tunnel_encap/tunnel_encap.h"
23 :
24 : using std::string;
25 : using std::vector;
26 : using namespace boost::placeholders;
27 :
28 : class McastTreeManager::DeleteActor : public LifetimeActor {
29 : public:
30 42908 : explicit DeleteActor(McastTreeManager *tree_manager)
31 42908 : : LifetimeActor(tree_manager->table_->routing_instance()->server()->
32 : lifetime_manager()),
33 42908 : tree_manager_(tree_manager) {
34 42909 : }
35 85818 : virtual ~DeleteActor() {
36 85818 : }
37 :
38 42910 : virtual bool MayDelete() const {
39 42910 : return tree_manager_->MayDelete();
40 : }
41 :
42 42909 : virtual void Shutdown() {
43 42909 : tree_manager_->Shutdown();
44 42909 : }
45 :
46 42909 : virtual void Destroy() {
47 42909 : tree_manager_->table_->DestroyTreeManager();
48 42909 : }
49 :
50 : private:
51 : McastTreeManager *tree_manager_;
52 : };
53 :
54 : //
55 : // Constructor for McastForwarder. The level is determined by the route type.
56 : // We get the address of the forwarder and the label_block from the attributes
57 : // of the active path. The LabelBLockPtr needs to be copied so that we can
58 : // release the label when processing a delete notification - we won't have the
59 : // path at that point.
60 : //
61 : // The RD will be zero for BGP learnt routes and the RouterId will be zero for
62 : // XMPP learnt routes.
63 : //
64 9805 : McastForwarder::McastForwarder(McastSGEntry *sg_entry, ErmVpnRoute *route)
65 9805 : : sg_entry_(sg_entry),
66 9805 : route_(route),
67 9805 : global_tree_route_(NULL),
68 9805 : label_(0),
69 9805 : address_(0),
70 9805 : rd_(route->GetPrefix().route_distinguisher()),
71 19610 : router_id_(route->GetPrefix().router_id()) {
72 9805 : const BgpPath *path = route->BestPath();
73 9805 : const BgpAttr *attr = path->GetAttr();
74 :
75 9805 : if (route_->GetPrefix().type() == ErmVpnPrefix::NativeRoute) {
76 4801 : level_ = McastTreeManager::LevelNative;
77 4801 : address_ = attr->nexthop().to_v4();
78 4801 : label_block_ = attr->label_block();
79 : } else {
80 5004 : level_ = McastTreeManager::LevelLocal;
81 5004 : const EdgeDiscovery::Edge *edge = attr->edge_discovery()->edge_list[0];
82 5004 : address_ = edge->address;
83 5004 : label_block_ = edge->label_block;
84 : }
85 :
86 9805 : if (path->GetAttr()->ext_community())
87 4846 : encap_ = path->GetAttr()->ext_community()->GetTunnelEncap();
88 9805 : }
89 :
90 : //
91 : // Destructor for McastForwarder. Flushes forward and reverse links to and
92 : // from other McastForwarders.
93 : //
94 11728 : McastForwarder::~McastForwarder() {
95 9805 : DeleteGlobalTreeRoute();
96 9805 : FlushLinks();
97 9805 : ReleaseLabel();
98 11728 : }
99 :
100 : //
101 : // Update the McastForwarder based on information in the ErmVpnRoute.
102 : // Return true if something changed.
103 : //
104 7882 : bool McastForwarder::Update(ErmVpnRoute *route) {
105 7882 : McastForwarder forwarder(sg_entry_, route);
106 :
107 7882 : bool changed = false;
108 7882 : if (label_block_ != forwarder.label_block_) {
109 1031 : ReleaseLabel();
110 1031 : label_block_ = forwarder.label_block_;
111 1031 : changed = true;
112 : }
113 7882 : if (address_ != forwarder.address_) {
114 448 : address_ = forwarder.address_;
115 448 : changed = true;
116 : }
117 7882 : if (encap_ != forwarder.encap_) {
118 14 : encap_ = forwarder.encap_;
119 14 : changed = true;
120 : }
121 :
122 7882 : return changed;
123 7882 : }
124 :
125 : //
126 : // Printable string for McastForwarder.
127 : //
128 2792 : std::string McastForwarder::ToString() const {
129 2792 : if (level_ == McastTreeManager::LevelNative) {
130 5584 : return rd_.ToString() + " -> " + integerToString(label_);
131 : } else {
132 0 : return router_id_.to_string() + " -> " + integerToString(label_);
133 : }
134 : }
135 :
136 : //
137 : // Find a link to the given McastForwarder.
138 : //
139 3668 : McastForwarder *McastForwarder::FindLink(McastForwarder *forwarder) {
140 3668 : for (McastForwarderList::iterator it = tree_links_.begin();
141 5874 : it != tree_links_.end(); ++it) {
142 2206 : if (*it == forwarder) return forwarder;
143 : }
144 3668 : return NULL;
145 : }
146 :
147 : //
148 : // Add a link to the given McastForwarder.
149 : //
150 3668 : void McastForwarder::AddLink(McastForwarder *forwarder) {
151 3668 : assert(!FindLink(forwarder));
152 3668 : tree_links_.push_back(forwarder);
153 3668 : }
154 :
155 : //
156 : // Remove a link to the given McastForwarder.
157 : //
158 1834 : void McastForwarder::RemoveLink(McastForwarder *forwarder) {
159 1834 : for (McastForwarderList::iterator it = tree_links_.begin();
160 1949 : it != tree_links_.end(); ++it) {
161 1949 : if (*it == forwarder) {
162 1834 : tree_links_.erase(it);
163 1834 : return;
164 : }
165 : }
166 : }
167 :
168 : //
169 : // Flush all links from this McastForwarder. Takes care of removing the
170 : // reverse links as well.
171 : //
172 15318 : void McastForwarder::FlushLinks() {
173 15318 : for (McastForwarderList::iterator it = tree_links_.begin();
174 17152 : it != tree_links_.end(); ++it) {
175 1834 : (*it)->RemoveLink(this);
176 : }
177 15318 : tree_links_.clear();
178 15318 : }
179 :
180 : //
181 : // Allocate a label for this McastForwarder. The label gets allocated from
182 : // the LabelBlock corresponding to the label range advertised by the peer.
183 : // This is used when updating the distribution tree for the McastSGEntry to
184 : // this McastForwarder belongs.
185 : //
186 3513 : void McastForwarder::AllocateLabel() {
187 3513 : label_ = label_block_->AllocateLabel();
188 3513 : }
189 :
190 : //
191 : // Release the label, if any, for this McastForwarder. This is required when
192 : // updating the distribution tree for the McastSGEntry to which we belong.
193 : //
194 16349 : void McastForwarder::ReleaseLabel() {
195 16349 : if (label_ != 0) {
196 3505 : label_block_->ReleaseLabel(label_);
197 3505 : label_ = 0;
198 : }
199 16349 : }
200 :
201 : //
202 : // Add the GlobalTreeRoute for this McastForwarder. The GlobalTreeRoute is
203 : // used by the tree builder to tell the associated control-node about the
204 : // forwarding edges for Native McastForwarders attached it.
205 : //
206 3356 : void McastForwarder::AddGlobalTreeRoute() {
207 3356 : assert(level_ == McastTreeManager::LevelLocal);
208 3356 : assert(!global_tree_route_);
209 :
210 : // Bail if there's no label allocated.
211 3356 : if (label_ == 0)
212 2099 : return;
213 :
214 : // Bail if we can't build a source RD.
215 1356 : if (sg_entry_->GetSourceRd().IsZero())
216 99 : return;
217 :
218 : // Construct the prefix and route key.
219 1257 : BgpTable *table = static_cast<BgpTable *>(route_->get_table());
220 : ErmVpnPrefix prefix(ErmVpnPrefix::GlobalTreeRoute,
221 1257 : RouteDistinguisher::kZeroRd, router_id_,
222 1257 : sg_entry_->group(), sg_entry_->source());
223 1257 : ErmVpnRoute rt_key(prefix);
224 :
225 : // Find or create the route.
226 1257 : McastManagerPartition *partition = sg_entry_->partition();
227 : DBTablePartition *tbl_partition =
228 1257 : static_cast<DBTablePartition *>(partition->GetTablePartition());
229 : ErmVpnRoute *route =
230 1257 : static_cast<ErmVpnRoute *>(tbl_partition->Find(&rt_key));
231 1257 : if (!route) {
232 411 : route = new ErmVpnRoute(prefix);
233 411 : tbl_partition->Add(route);
234 : } else {
235 846 : route->ClearDelete();
236 : }
237 :
238 : // Build the attributes. Need to go through the tree links to build the
239 : // EdgeForwardingSpec.
240 1257 : BgpServer *server = table->routing_instance()->server();
241 1257 : BgpAttrSpec attr_spec;
242 1257 : BgpAttrNextHop nexthop(server->bgp_identifier());
243 1257 : attr_spec.push_back(&nexthop);
244 1257 : BgpAttrSourceRd source_rd(sg_entry_->GetSourceRd());
245 1257 : attr_spec.push_back(&source_rd);
246 1257 : EdgeForwardingSpec efspec;
247 1257 : for (McastForwarderList::const_iterator it = tree_links_.begin();
248 2201 : it != tree_links_.end(); ++it) {
249 944 : EdgeForwardingSpec::Edge *edge = new EdgeForwardingSpec::Edge;
250 944 : edge->SetInboundIp4Address(address_);
251 944 : edge->inbound_label = label_;
252 944 : edge->SetOutboundIp4Address((*it)->address());
253 944 : edge->outbound_label = (*it)->label();
254 944 : efspec.edge_list.push_back(edge);
255 : }
256 1257 : attr_spec.push_back(&efspec);
257 : // Add tunnel encaps for remote nodes
258 1257 : ExtCommunitySpec ext;
259 1257 : ext.AddTunnelEncaps(encap_);
260 1257 : if (!ext.communities.empty())
261 75 : attr_spec.push_back(&ext);
262 1257 : BgpAttrPtr attr = server->attr_db()->Locate(attr_spec);
263 :
264 : // Add a path with source BgpPath::Local.
265 1257 : BgpPath *path = new BgpPath(0, BgpPath::Local, attr);
266 1257 : route->InsertPath(path);
267 1257 : tbl_partition->Notify(route);
268 1257 : global_tree_route_ = route;
269 1257 : }
270 :
271 : //
272 : // Delete the GlobalTreeRoute for this McastForwarder.
273 : //
274 13161 : void McastForwarder::DeleteGlobalTreeRoute() {
275 13161 : if (!global_tree_route_)
276 11904 : return;
277 :
278 1257 : McastManagerPartition *partition = sg_entry_->partition();
279 : DBTablePartition *tbl_partition =
280 1257 : static_cast<DBTablePartition *>(partition->GetTablePartition());
281 1257 : global_tree_route_->RemovePath(BgpPath::Local);
282 :
283 1257 : if (!global_tree_route_->HasPaths()) {
284 1206 : tbl_partition->Delete(global_tree_route_);
285 : } else {
286 51 : tbl_partition->Notify(global_tree_route_);
287 : }
288 1257 : global_tree_route_ = NULL;
289 : }
290 :
291 : //
292 : // Append list of BgpOListElems from the Local tree to the BgpOListSpec. The
293 : // list is built based on the tree links in this McastForwarder.
294 : //
295 4113 : void McastForwarder::AddLocalOListElems(BgpOListSpec *olist_spec) {
296 4113 : assert(level_ == McastTreeManager::LevelNative);
297 :
298 4113 : for (McastForwarderList::const_iterator it = tree_links_.begin();
299 7685 : it != tree_links_.end(); ++it) {
300 3572 : BgpOListElem elem((*it)->address(), (*it)->label(), (*it)->encap());
301 3572 : olist_spec->elements.push_back(elem);
302 3572 : }
303 4113 : }
304 :
305 : //
306 : // Append list of BgpOListElems from the Global tree to the BgpOListSpec. The
307 : // list is built based on EdgeForwarding attribute in the GlobalTreeRoute.
308 : //
309 4113 : void McastForwarder::AddGlobalOListElems(BgpOListSpec *olist_spec) {
310 4113 : assert(level_ == McastTreeManager::LevelNative);
311 :
312 : // Bail if this is not the forest node for the Local tree.
313 4113 : if (!sg_entry_->IsForestNode(this))
314 2445 : return;
315 :
316 2141 : const ErmVpnRoute *route = sg_entry_->tree_result_route();
317 2141 : if (!route)
318 473 : return;
319 :
320 1668 : const BgpPath *path = route->BestPath();
321 1668 : if (!path)
322 0 : return;
323 1668 : const BgpAttr *attr = path->GetAttr();
324 1668 : vector<string> encaps;
325 1668 : if (attr && attr->ext_community())
326 544 : encaps = attr->ext_community()->GetTunnelEncap();
327 :
328 : // Go through each forwarding edge and add it to the list.
329 1668 : const EdgeForwarding *eforwarding = path->GetAttr()->edge_forwarding();
330 1668 : for (EdgeForwarding::EdgeList::const_iterator it =
331 4440 : eforwarding->edge_list.begin(); it != eforwarding->edge_list.end();
332 1104 : ++it) {
333 1104 : const EdgeForwarding::Edge *edge = *it;
334 1104 : if (edge->inbound_address == address_) {
335 956 : BgpOListElem elem(edge->outbound_address, edge->outbound_label,
336 956 : encaps);
337 956 : olist_spec->elements.push_back(elem);
338 956 : }
339 : }
340 1668 : }
341 :
342 : //
343 : // Construct an UpdateInfo with the RibOutAttr that needs to be advertised to
344 : // the IPeer for the ErmVpnRoute associated with this McastForwarder. This is
345 : // used as Export method of the ErmVpnTable. It is expected that the caller
346 : // fills in the target RibPeerSet in the UpdateInfo.
347 : //
348 : // The main functionality here is to transform the McastForwarderList for the
349 : // distribution tree and the EdgeForwarding attribute from the GlobalTreeRoute
350 : // into a BgpOList.
351 : //
352 4113 : UpdateInfo *McastForwarder::GetUpdateInfo(ErmVpnTable *table) {
353 4113 : CHECK_CONCURRENCY("db::DBTable");
354 :
355 4113 : assert(level_ == McastTreeManager::LevelNative);
356 :
357 4113 : BgpOListSpec olist_spec(BgpAttribute::OList);
358 4113 : AddLocalOListElems(&olist_spec);
359 4113 : AddGlobalOListElems(&olist_spec);
360 :
361 : // Bail if there is no label allocated.
362 4113 : if (label_ == 0)
363 644 : return NULL;
364 :
365 3469 : BgpAttrSpec attr_spec;
366 3469 : attr_spec.push_back(&olist_spec);
367 3469 : BgpAttrPtr attr = table->server()->attr_db()->Locate(attr_spec);
368 :
369 3469 : UpdateInfo *uinfo = new UpdateInfo;
370 3469 : uinfo->roattr = RibOutAttr(table, route_, attr.get(), label_, true, true);
371 5587 : if (route_ && sg_entry_->IsForestNode(this) &&
372 2118 : sg_entry_->IsTreeBuilder(McastTreeManager::LevelLocal)) {
373 1263 : table->GetMvpnSourceAddress(route_, uinfo->roattr.source_address());
374 : }
375 3469 : return uinfo;
376 4113 : }
377 :
378 : //
379 : // Constructor for McastSGEntry.
380 : //
381 23968 : McastSGEntry::McastSGEntry(McastManagerPartition *partition,
382 23968 : Ip4Address group, Ip4Address source)
383 23968 : : partition_(partition),
384 23968 : group_(group),
385 23968 : source_(source),
386 23968 : forest_node_(NULL),
387 23968 : local_tree_route_(NULL),
388 23968 : tree_result_route_(NULL),
389 47936 : on_work_queue_(false) {
390 71904 : for (int level = McastTreeManager::LevelFirst;
391 71904 : level < McastTreeManager::LevelCount; ++level) {
392 47936 : ForwarderSet *forwarders = new ForwarderSet;
393 47936 : forwarder_sets_.push_back(forwarders);
394 47936 : update_needed_.push_back(false);
395 : }
396 23968 : }
397 :
398 : //
399 : // Destructor for McastSGEntry.
400 : //
401 24375 : McastSGEntry::~McastSGEntry() {
402 23968 : STLDeleteValues(&forwarder_sets_);
403 24375 : }
404 :
405 : //
406 : // Printable string for McastSGEntry.
407 : //
408 56 : std::string McastSGEntry::ToString() const {
409 112 : return group_.to_string() + "," + source_.to_string();
410 : }
411 :
412 : //
413 : // Add the given McastForwarder under this McastSGEntry and trigger update
414 : // of the distribution tree.
415 : //
416 1923 : void McastSGEntry::AddForwarder(McastForwarder *forwarder) {
417 1923 : uint8_t level = forwarder->level();
418 1923 : forwarder_sets_[level]->insert(forwarder);
419 1923 : update_needed_[level] = true;
420 1923 : partition_->EnqueueSGEntry(this);
421 1923 : }
422 :
423 : //
424 : // Handle change for the given McastForwarder under this McastSGEntry. Trigger
425 : // update of the distribution tree.
426 : //
427 : // Note that this method only handles the change = the caller determines that
428 : // there has been a change.
429 : //
430 1085 : void McastSGEntry::ChangeForwarder(McastForwarder *forwarder) {
431 1085 : uint8_t level = forwarder->level();
432 1085 : update_needed_[level] = true;
433 1085 : partition_->EnqueueSGEntry(this);
434 1085 : }
435 :
436 : //
437 : // Delete the given McastForwarder from this McastSGEntry and trigger update
438 : // of the distribution tree.
439 : //
440 1923 : void McastSGEntry::DeleteForwarder(McastForwarder *forwarder) {
441 1923 : if (forwarder == forest_node_)
442 396 : forest_node_ = NULL;
443 1923 : uint8_t level = forwarder->level();
444 1923 : forwarder_sets_[level]->erase(forwarder);
445 1923 : update_needed_[level] = true;
446 1923 : partition_->EnqueueSGEntry(this);
447 1923 : }
448 :
449 : //
450 : // Get the SourceRD to be used when adding [Local|Global]TreeRoutes. This
451 : // SourceRD gets used as the RD when the ErmVpnRoute is replicated from the
452 : // VRF table to the VPN table.
453 : //
454 : // We simply use the RD for the forest node.
455 : //
456 3435 : const RouteDistinguisher &McastSGEntry::GetSourceRd() const {
457 3435 : if (!forest_node_)
458 99 : return RouteDistinguisher::kZeroRd;
459 3336 : return forest_node_->route()->GetPrefix().route_distinguisher();
460 : }
461 :
462 : //
463 : // Add the LocalTreeRoute for this McastSGEntry. This route advertises a set
464 : // of candidate edges from McastForwarders attached to this control-node that
465 : // can be used by the tree builder to build the higher level tree. We simply
466 : // advertise edges McastTreeManager::kDegree - 1 edges from the forest node.
467 : //
468 : // We advertise kDegree-1 candidate edges via the EdgeDiscovery attribute. All
469 : // the edges are for the forest node for the tree of native McastForwarders.
470 : // The label block for each edge in the EdgeDiscovery attribute is of size 1 -
471 : // this is label that has been allocated for the forest node. Using a single
472 : // label is acceptable because the tree builder algorithm does not change the
473 : // relative order of nodes in the tree.
474 : //
475 1170 : void McastSGEntry::AddLocalTreeRoute() {
476 1170 : assert(!forest_node_);
477 1170 : assert(!local_tree_route_);
478 :
479 : // Select last usable leaf in the distribution tree as the forest node.
480 : // A leaf is considered usable if it has a valid label i.e. it has not
481 : // run out of labels.
482 1170 : uint8_t level = McastTreeManager::LevelNative;
483 1170 : ForwarderSet *forwarders = forwarder_sets_[level];
484 1170 : for (ForwarderSet::reverse_iterator rit = forwarders->rbegin();
485 1177 : rit != forwarders->rend(); ++rit) {
486 829 : McastForwarder *forwarder = *rit;
487 829 : if (forwarder->label()) {
488 822 : forest_node_ = forwarder;
489 822 : break;
490 : }
491 : }
492 :
493 : // Bail if we couldn't designate a forest node.
494 1170 : if (!forest_node_)
495 348 : return;
496 :
497 : // Construct the prefix and route key.
498 822 : BgpServer *server = partition_->server();
499 822 : Ip4Address router_id(server->bgp_identifier());
500 : ErmVpnPrefix prefix(ErmVpnPrefix::LocalTreeRoute,
501 822 : RouteDistinguisher::kZeroRd, router_id, group_, source_);
502 822 : ErmVpnRoute rt_key(prefix);
503 :
504 : // Find or create the route.
505 : DBTablePartition *tbl_partition =
506 822 : static_cast<DBTablePartition *>(partition_->GetTablePartition());
507 : ErmVpnRoute *route =
508 822 : static_cast<ErmVpnRoute *>(tbl_partition->Find(&rt_key));
509 822 : if (!route) {
510 348 : route = new ErmVpnRoute(prefix);
511 348 : tbl_partition->Add(route);
512 : } else {
513 474 : route->ClearDelete();
514 : }
515 :
516 : // Build the attributes.
517 822 : BgpAttrSpec attr_spec;
518 822 : BgpAttrNextHop nexthop(server->bgp_identifier());
519 822 : attr_spec.push_back(&nexthop);
520 822 : BgpAttrSourceRd source_rd(GetSourceRd());
521 822 : attr_spec.push_back(&source_rd);
522 822 : EdgeDiscoverySpec edspec;
523 3288 : for (int idx = 1; idx <= McastTreeManager::kDegree - 1; ++idx) {
524 2466 : EdgeDiscoverySpec::Edge *edge = new EdgeDiscoverySpec::Edge;
525 2466 : edge->SetIp4Address(forest_node_->address());
526 2466 : edge->SetLabels(forest_node_->label(), forest_node_->label());
527 2466 : edspec.edge_list.push_back(edge);
528 : }
529 822 : attr_spec.push_back(&edspec);
530 : // Add tunnel encaps for remote nodes
531 822 : ExtCommunitySpec ext;
532 822 : ext.AddTunnelEncaps(forest_node_->encap());
533 822 : if (!ext.communities.empty())
534 78 : attr_spec.push_back(&ext);
535 822 : BgpAttrPtr attr = server->attr_db()->Locate(attr_spec);
536 :
537 : // Add a path with source BgpPath::Local.
538 822 : BgpPath *path = new BgpPath(0, BgpPath::Local, attr);
539 822 : route->InsertPath(path);
540 822 : tbl_partition->Notify(route);
541 822 : local_tree_route_ = route;
542 822 : }
543 :
544 : //
545 : // Delete the LocalTreeRoute for this McastSGEntry.
546 : //
547 1170 : void McastSGEntry::DeleteLocalTreeRoute() {
548 1170 : if (!local_tree_route_)
549 348 : return;
550 :
551 822 : forest_node_ = NULL;
552 : DBTablePartition *tbl_partition =
553 822 : static_cast<DBTablePartition *>(partition_->GetTablePartition());
554 822 : local_tree_route_->RemovePath(BgpPath::Local);
555 822 : if (!local_tree_route_->HasPaths()) {
556 822 : tbl_partition->Delete(local_tree_route_);
557 : } else {
558 0 : tbl_partition->Notify(local_tree_route_);
559 : }
560 822 : local_tree_route_ = NULL;
561 : }
562 :
563 : //
564 : // Update the LocalTreeRoute for this McastSGEntry if RouterId has changed.
565 : //
566 723 : void McastSGEntry::UpdateLocalTreeRoute() {
567 723 : if (!local_tree_route_)
568 723 : return;
569 :
570 : // Bail if the RouterId hasn't changed.
571 607 : const BgpServer *server = partition_->server();
572 607 : Ip4Address router_id = local_tree_route_->GetPrefix().router_id();
573 607 : if (router_id.to_ulong() == server->bgp_identifier())
574 607 : return;
575 :
576 : // Add and delete the route.
577 0 : DeleteLocalTreeRoute();
578 0 : AddLocalTreeRoute();
579 : }
580 :
581 : //
582 : // Update relevant [Local|Global]TreeRoutes for the McastSGEntry.
583 : //
584 3387 : void McastSGEntry::UpdateRoutes(uint8_t level) {
585 3387 : if (level == McastTreeManager::LevelNative) {
586 1170 : DeleteLocalTreeRoute();
587 1170 : AddLocalTreeRoute();
588 : } else {
589 2217 : ForwarderSet *forwarders = forwarder_sets_[level];
590 2217 : for (ForwarderSet::iterator it = forwarders->begin();
591 5573 : it != forwarders->end(); ++it) {
592 3356 : (*it)->DeleteGlobalTreeRoute();
593 3356 : (*it)->AddGlobalTreeRoute();
594 : }
595 : }
596 3387 : }
597 :
598 3172 : ErmVpnRoute *McastSGEntry::GetGlobalTreeRootRoute() const {
599 3172 : if (!IsTreeBuilder(McastTreeManager::LevelLocal))
600 1586 : return NULL;
601 1586 : ForwarderSet *forwarders = forwarder_sets_[McastTreeManager::LevelLocal];
602 1586 : assert(!forwarders->empty());
603 1586 : ForwarderSet::const_iterator it = forwarders->begin();
604 1586 : return (*it)->global_tree_route();
605 : }
606 :
607 : //
608 : // Implement tree builder election.
609 : //
610 8681 : bool McastSGEntry::IsTreeBuilder(uint8_t level) const {
611 8681 : if (level == McastTreeManager::LevelNative)
612 1172 : return true;
613 :
614 7509 : const ForwarderSet *forwarders = forwarder_sets_[level];
615 7509 : ForwarderSet::const_iterator it = forwarders->begin();
616 7509 : if (it == forwarders->end())
617 680 : return false;
618 :
619 6829 : Ip4Address router_id(partition_->server()->bgp_identifier());
620 6829 : if ((*it)->router_id() != router_id)
621 3129 : return false;
622 :
623 3700 : return true;
624 : }
625 :
626 : //
627 : //
628 : // Update specified distribution tree for the McastSGEntry. We traverse all
629 : // McastForwarders in sorted order and arrange them in breadth first fashion
630 : // in a k-ary tree. Building the tree in this manner guarantees that we get
631 : // the same tree for a given set of forwarders, independent of the order in
632 : // in which they joined. This predictability is deemed to be more important
633 : // than other criteria such as minimizing disruption of traffic, minimizing
634 : // the cost/weight of the tree etc.
635 : //
636 6536 : void McastSGEntry::UpdateTree(uint8_t level) {
637 6536 : CHECK_CONCURRENCY("db::DBTable");
638 :
639 6536 : if (!update_needed_[level])
640 4517 : return;
641 3387 : update_needed_[level] = false;
642 :
643 : int degree;
644 3387 : if (level == McastTreeManager::LevelNative) {
645 1170 : degree = McastTreeManager::kDegree;
646 : } else {
647 2217 : degree = McastTreeManager::kDegree - 1;
648 : }
649 :
650 : // First get rid of the previous distribution tree and enqueue all the
651 : // associated ErmVpnRoutes for notification. Note that DBListeners will
652 : // not get invoked until after this routine is done.
653 3387 : ForwarderSet *forwarders = forwarder_sets_[level];
654 3387 : for (ForwarderSet::iterator it = forwarders->begin();
655 8900 : it != forwarders->end(); ++it) {
656 5513 : (*it)->FlushLinks();
657 5513 : (*it)->ReleaseLabel();
658 5513 : partition_->GetTablePartition()->Notify((*it)->route());
659 : }
660 :
661 : // Bail if we're not the tree builder.
662 3387 : if (!IsTreeBuilder(level)) {
663 1368 : UpdateRoutes(level);
664 1368 : return;
665 : }
666 :
667 : // Create a vector of pointers to the McastForwarders in sorted order.
668 : // We do this because std::set doesn't support random access iterators.
669 : // Skip if we can't allocate a label for the McastForwarder.
670 2019 : McastForwarderList vec;
671 2019 : vec.reserve(forwarders->size());
672 2019 : for (ForwarderSet::iterator it = forwarders->begin();
673 5532 : it != forwarders->end(); ++it) {
674 3513 : McastForwarder *forwarder = *it;
675 3513 : forwarder->AllocateLabel();
676 3513 : if (!forwarder->label())
677 8 : continue;
678 3505 : vec.push_back(forwarder);
679 : }
680 :
681 : // Go through each McastForwarder in the vector and link it to it's parent
682 : // McastForwarder in the k-ary tree. We also add a link from the parent to
683 : // the entry in question.
684 5524 : for (McastForwarderList::iterator it = vec.begin(); it != vec.end(); ++it) {
685 3505 : int idx = it - vec.begin();
686 3505 : if (idx == 0)
687 1671 : continue;
688 :
689 1834 : int parent_idx = (idx - 1) / degree;
690 1834 : McastForwarderList::iterator parent_it = vec.begin() + parent_idx;
691 1834 : assert(parent_it != vec.end());
692 1834 : McastForwarder *forwarder = *it;
693 1834 : McastForwarder *parent_forwarder = *parent_it;
694 1834 : forwarder->AddLink(parent_forwarder);
695 1834 : parent_forwarder->AddLink(forwarder);
696 : }
697 :
698 : // Update [Local|Global]TreeRoutes.
699 2019 : UpdateRoutes(level);
700 2019 : }
701 :
702 : //
703 : // Update distribution trees for both levels.
704 : //
705 3268 : void McastSGEntry::UpdateTree() {
706 9804 : for (uint8_t level = McastTreeManager::LevelFirst;
707 9804 : level < McastTreeManager::LevelCount; ++level) {
708 6536 : UpdateTree(level);
709 : }
710 3268 : }
711 :
712 : //
713 : // Trigger notification of the ErmVpnRoute associated with the McastForwarder
714 : // that is the forest node. This is used to trigger a rebuild of the BgpOlist
715 : // when the GlobalTreeRoute is updated.
716 : //
717 1954 : void McastSGEntry::NotifyForestNode() {
718 1954 : if (!forest_node_)
719 431 : return;
720 1523 : partition_->GetTablePartition()->Notify(forest_node_->route());
721 : }
722 :
723 177 : bool McastSGEntry::GetForestNodePMSI(uint32_t *label, Ip4Address *address,
724 : vector<string> *tunnel_encap) const {
725 177 : if (!forest_node_)
726 0 : return false;
727 177 : *label = forest_node_->label();
728 177 : *address = forest_node_->address();
729 177 : *tunnel_encap = forest_node_->encap();
730 177 : return true;
731 : }
732 :
733 7582 : bool McastSGEntry::IsForestNode(McastForwarder *forwarder) {
734 7582 : return (forwarder == forest_node_);
735 : }
736 :
737 3268 : bool McastSGEntry::empty() const {
738 3268 : if (local_tree_route_ || tree_result_route_)
739 2559 : return false;
740 709 : if (!forwarder_sets_[McastTreeManager::LevelNative]->empty())
741 3 : return false;
742 706 : if (!forwarder_sets_[McastTreeManager::LevelLocal]->empty())
743 299 : return false;
744 407 : return true;
745 : }
746 :
747 : //
748 : // Constructor for McastManagerPartition.
749 : //
750 42875 : McastManagerPartition::McastManagerPartition(McastTreeManager *tree_manager,
751 42875 : size_t part_id)
752 42875 : : tree_manager_(tree_manager),
753 42875 : part_id_(part_id),
754 42876 : update_count_(0),
755 85749 : work_queue_(TaskScheduler::GetInstance()->GetTaskId("db::DBTable"),
756 42873 : part_id_,
757 42875 : boost::bind(&McastManagerPartition::ProcessSGEntry, this, _1)) {
758 42876 : }
759 :
760 : //
761 : // Destructor for McastManagerPartition.
762 : //
763 42876 : McastManagerPartition::~McastManagerPartition() {
764 42876 : work_queue_.Shutdown();
765 42876 : }
766 :
767 : // Find the McastSGEntry for the given group and source.
768 20212 : McastSGEntry *McastManagerPartition::FindSGEntry(
769 : const Ip4Address &group, const Ip4Address &source) {
770 : return const_cast<McastSGEntry *>(
771 20212 : static_cast<const McastManagerPartition *>(this)->FindSGEntry(group,
772 20212 : source));
773 : }
774 :
775 : //
776 : // Find the McastSGEntry for the given group and source.
777 : //
778 23561 : const McastSGEntry *McastManagerPartition::FindSGEntry(
779 : const Ip4Address &group, const Ip4Address &source) const {
780 : McastSGEntry temp_sg_entry(const_cast<McastManagerPartition *>(this),
781 23561 : group, source);
782 23561 : SGList::const_iterator it = sg_list_.find(&temp_sg_entry);
783 47122 : return (it != sg_list_.end() ? *it : NULL);
784 23561 : }
785 :
786 : //
787 : // Find or create the McastSGEntry for the given group and source.
788 : //
789 2348 : McastSGEntry *McastManagerPartition::LocateSGEntry(
790 : Ip4Address group, Ip4Address source) {
791 2348 : McastSGEntry *sg_entry = FindSGEntry(group, source);
792 2348 : if (!sg_entry) {
793 407 : sg_entry = new McastSGEntry(this, group, source);
794 407 : sg_list_.insert(sg_entry);
795 : }
796 2348 : return sg_entry;
797 : }
798 :
799 3172 : ErmVpnRoute *McastManagerPartition::GetGlobalTreeRootRoute(
800 : const Ip4Address &source, const Ip4Address &group) const {
801 3172 : const McastSGEntry *sg = FindSGEntry(group, source);
802 3172 : return sg ? sg->GetGlobalTreeRootRoute() : NULL;
803 : }
804 :
805 7976 : void McastManagerPartition::NotifyForestNode(
806 : const Ip4Address &source, const Ip4Address &group) {
807 7976 : McastSGEntry *sg = FindSGEntry(group, source);
808 7976 : if (sg)
809 310 : sg->NotifyForestNode();
810 7976 : }
811 :
812 177 : bool McastManagerPartition::GetForestNodePMSI(ErmVpnRoute *rt, uint32_t *label,
813 : Ip4Address *address, vector<string> *encap) const {
814 177 : const McastSGEntry *sg = FindSGEntry(rt->GetPrefix().group(),
815 177 : rt->GetPrefix().source());
816 177 : return sg ? sg->GetForestNodePMSI(label, address, encap) : false;
817 : }
818 :
819 : //
820 : // Enqueue the given McastSGEntry on the WorkQueue if it's not already on it.
821 : //
822 5356 : void McastManagerPartition::EnqueueSGEntry(McastSGEntry *sg_entry) {
823 5356 : if (sg_entry->on_work_queue())
824 2088 : return;
825 3268 : work_queue_.Enqueue(sg_entry);
826 3268 : sg_entry->set_on_work_queue();
827 : }
828 :
829 : //
830 : // Callback for the WorkQueue. Updates distribution trees for the McastSGEntry.
831 : // Also gets rid of the McastSGEntry if it is eligible to be deleted.
832 : //
833 3268 : bool McastManagerPartition::ProcessSGEntry(McastSGEntry *sg_entry) {
834 3268 : CHECK_CONCURRENCY("db::DBTable");
835 :
836 3268 : sg_entry->clear_on_work_queue();
837 3268 : sg_entry->UpdateTree();
838 3268 : update_count_++;
839 :
840 3268 : if (sg_entry->empty()) {
841 407 : sg_list_.erase(sg_entry);
842 407 : delete sg_entry;
843 : }
844 :
845 3268 : if (sg_list_.empty())
846 292 : tree_manager_->RetryDelete();
847 :
848 3268 : return true;
849 : }
850 :
851 : //
852 : // Get the DBTablePartBase for the ErmVpnTable for our partition id.
853 : //
854 11194 : DBTablePartBase *McastManagerPartition::GetTablePartition() {
855 11194 : return tree_manager_->GetTablePartition(part_id_);
856 : }
857 :
858 0 : const RoutingInstance *McastManagerPartition::routing_instance() const {
859 0 : return tree_manager_->table()->routing_instance();
860 : }
861 :
862 8258 : BgpServer *McastManagerPartition::server() {
863 8258 : return tree_manager_->table()->server();
864 : }
865 :
866 0 : const BgpServer *McastManagerPartition::server() const {
867 0 : return tree_manager_->table()->server();
868 : }
869 :
870 : //
871 : // Constructor for McastTreeManager.
872 : //
873 42904 : McastTreeManager::McastTreeManager(ErmVpnTable *table)
874 42904 : : table_(table),
875 42904 : listener_id_(DBTable::kInvalidId),
876 42904 : table_delete_ref_(this, table->deleter()) {
877 42908 : deleter_.reset(new DeleteActor(this));
878 42909 : }
879 :
880 : //
881 : // Destructor for McastTreeManager.
882 : //
883 66867 : McastTreeManager::~McastTreeManager() {
884 66867 : }
885 :
886 : //
887 : // Initialize the McastTreeManager. We allocate the McastManagerPartitions
888 : // and register a DBListener for the ErmVpnTable.
889 : //
890 42871 : void McastTreeManager::Initialize() {
891 42871 : AllocPartitions();
892 42875 : listener_id_ = table_->Register(
893 : boost::bind(&McastTreeManager::RouteListener, this, _1, _2),
894 : "McastTreeManager");
895 42876 : }
896 :
897 : //
898 : // Terminate the McastTreeManager. We free the McastManagerPartitions
899 : // and unregister from the ErmVpnTable.
900 : //
901 42876 : void McastTreeManager::Terminate() {
902 42876 : table_->Unregister(listener_id_);
903 42876 : FreePartitions();
904 42876 : }
905 :
906 : //
907 : // Allocate the McastManagerPartitions.
908 : //
909 42876 : void McastTreeManager::AllocPartitions() {
910 85751 : for (int part_id = 0; part_id < table_->PartitionCount(); part_id++) {
911 42876 : partitions_.push_back(new McastManagerPartition(this, part_id));
912 : }
913 42875 : }
914 :
915 : //
916 : // Free the McastManagerPartitions.
917 : //
918 42876 : void McastTreeManager::FreePartitions() {
919 85752 : for (size_t part_id = 0; part_id < partitions_.size(); part_id++) {
920 42876 : delete partitions_[part_id];
921 : }
922 42876 : partitions_.clear();
923 42876 : }
924 :
925 7978 : McastManagerPartition *McastTreeManager::GetPartition(int part_id) {
926 7978 : return partitions_[part_id];
927 : }
928 :
929 3349 : const McastManagerPartition *McastTreeManager::GetPartition(int part_id) const {
930 3349 : return partitions_[part_id];
931 : }
932 :
933 : //
934 : // Get the DBTablePartBase for the ErmVpnTable for given partition id.
935 : //
936 11194 : DBTablePartBase *McastTreeManager::GetTablePartition(size_t part_id) {
937 11194 : return table_->GetTablePartition(part_id);
938 : }
939 :
940 : //
941 : // Construct export state for the given ErmVpnRoute. Note that the route
942 : // only needs to be exported to the IPeer from which it was learnt.
943 : //
944 3143 : UpdateInfo *McastTreeManager::GetUpdateInfo(ErmVpnRoute *route) {
945 3143 : CHECK_CONCURRENCY("db::DBTable");
946 :
947 3143 : DBState *dbstate = route->GetState(table_, listener_id_);
948 3143 : McastForwarder *forwarder = dynamic_cast<McastForwarder *>(dbstate);
949 :
950 3143 : if (!forwarder)
951 0 : return NULL;
952 :
953 3143 : return forwarder->GetUpdateInfo(table_);
954 : }
955 :
956 : //
957 : // DBListener callback handler for Native and Local routes in the ErmVpnTable.
958 : // It creates, updates or deletes the associated McastForwarder as appropriate.
959 : //
960 : // Creates a McastSGEntry if one doesn't already exist. However, McastSGEntrys
961 : // don't get deleted from here. They only get deleted from WorkQueue callback
962 : // routine i.e. McastManagerPartition::ProcessSGEntry.
963 : //
964 11749 : void McastTreeManager::TreeNodeListener(McastManagerPartition *partition,
965 : ErmVpnRoute *route) {
966 11749 : CHECK_CONCURRENCY("db::DBTable");
967 :
968 11749 : DBState *dbstate = route->GetState(table_, listener_id_);
969 11749 : if (!dbstate) {
970 : // We have no previous DBState for this route.
971 : // Bail if the route is not valid.
972 1944 : if (!route->IsValid())
973 21 : return;
974 :
975 : // Create a new McastForwarder and associate it with the route.
976 1923 : McastSGEntry *sg_entry = partition->LocateSGEntry(
977 1923 : route->GetPrefix().group(), route->GetPrefix().source());
978 1923 : McastForwarder *forwarder = new McastForwarder(sg_entry, route);
979 1923 : sg_entry->AddForwarder(forwarder);
980 1923 : route->SetState(table_, listener_id_, forwarder);
981 :
982 : // Update local tree route if our RouterId has changed. Ideally,
983 : // we should trigger an update of all local trees routes when we
984 : // detect a change in RouterId. Instead, we currently check and
985 : // update the local route when we detect a new local route from
986 : // another node.
987 1923 : if (route->GetPrefix().type() == ErmVpnPrefix::LocalTreeRoute)
988 723 : sg_entry->UpdateLocalTreeRoute();
989 : } else {
990 9805 : McastSGEntry *sg_entry = partition->FindSGEntry(
991 9805 : route->GetPrefix().group(), route->GetPrefix().source());
992 9805 : assert(sg_entry);
993 9805 : McastForwarder *forwarder = dynamic_cast<McastForwarder *>(dbstate);
994 9805 : assert(forwarder);
995 :
996 9805 : if (!route->IsValid()) {
997 : // Delete the McastForwarder associated with the route.
998 1923 : route->ClearState(table_, listener_id_);
999 1923 : sg_entry->DeleteForwarder(forwarder);
1000 1923 : delete forwarder;
1001 7882 : } else if (forwarder->Update(route)) {
1002 : // Trigger update of the distribution tree.
1003 1085 : sg_entry->ChangeForwarder(forwarder);
1004 : }
1005 : }
1006 : }
1007 :
1008 : //
1009 : // DBListener callback handler for GlobalTreeRoutes in the ErmVpnTable. It
1010 : // updates the tree_result_route_ and triggers re-evaluation of the forest
1011 : // node McastForwarder's BgpOlist.
1012 : //
1013 9344 : void McastTreeManager::TreeResultListener(McastManagerPartition *partition,
1014 : ErmVpnRoute *route) {
1015 9344 : CHECK_CONCURRENCY("db::DBTable");
1016 :
1017 9344 : DBState *dbstate = route->GetState(table_, listener_id_);
1018 9344 : if (!dbstate) {
1019 : // We have no previous DBState for this route.
1020 : // Bail if the route is not valid.
1021 8125 : if (!route->IsValid())
1022 5997 : return;
1023 :
1024 : // Ignore GlobalTreeRoute if it's not applicable to this control-node.
1025 2128 : BgpServer *server = table_->routing_instance()->server();
1026 2128 : if (route->GetPrefix().router_id().to_ulong() !=
1027 2128 : server->bgp_identifier())
1028 1703 : return;
1029 :
1030 425 : McastSGEntry *sg_entry = partition->LocateSGEntry(
1031 425 : route->GetPrefix().group(), route->GetPrefix().source());
1032 425 : route->SetState(table_, listener_id_, sg_entry);
1033 425 : sg_entry->set_tree_result_route(route);
1034 425 : sg_entry->NotifyForestNode();
1035 : } else {
1036 1219 : McastSGEntry *sg_entry = dynamic_cast<McastSGEntry *>(dbstate);
1037 1219 : assert(sg_entry);
1038 :
1039 1219 : if (!route->IsValid()) {
1040 425 : sg_entry->clear_tree_result_route();
1041 425 : route->ClearState(table_, listener_id_);
1042 425 : partition->EnqueueSGEntry(sg_entry);
1043 : }
1044 1219 : sg_entry->NotifyForestNode();
1045 : }
1046 : }
1047 :
1048 : //
1049 : // DBListener callback handler for the ErmVpnTable. GlobalTreeRoutes provide
1050 : // result information and hence are handled differently than Native and Local
1051 : // routes, which result in update of a McastForwarder.
1052 : //
1053 21093 : void McastTreeManager::RouteListener(
1054 : DBTablePartBase *tpart, DBEntryBase *db_entry) {
1055 21093 : CHECK_CONCURRENCY("db::DBTable");
1056 :
1057 21093 : McastManagerPartition *partition = partitions_[tpart->index()];
1058 21093 : ErmVpnRoute *route = dynamic_cast<ErmVpnRoute *>(db_entry);
1059 21093 : if (route->GetPrefix().type() == ErmVpnPrefix::GlobalTreeRoute) {
1060 9344 : TreeResultListener(partition, route);
1061 : } else {
1062 11749 : TreeNodeListener(partition, route);
1063 : }
1064 21093 : }
1065 :
1066 :
1067 : //
1068 : // Check if the McastTreeManager can be deleted. This can happen only if all
1069 : // the McastManagerPartitions are empty.
1070 : //
1071 42910 : bool McastTreeManager::MayDelete() const {
1072 42910 : CHECK_CONCURRENCY("bgp::Config");
1073 :
1074 42910 : for (PartitionList::const_iterator it = partitions_.begin();
1075 85786 : it != partitions_.end(); ++it) {
1076 42877 : if (!(*it)->empty())
1077 1 : return false;
1078 : }
1079 :
1080 42909 : return true;
1081 : }
1082 :
1083 : //
1084 : // Initiate shutdown for the McastTreeManager.
1085 : //
1086 42909 : void McastTreeManager::Shutdown() {
1087 42909 : CHECK_CONCURRENCY("bgp::Config");
1088 42909 : }
1089 :
1090 : //
1091 : // Trigger deletion of the McastTreeManager and propagate the delete to any
1092 : // dependents.
1093 : //
1094 42909 : void McastTreeManager::ManagedDelete() {
1095 42909 : deleter_->Delete();
1096 42909 : }
1097 :
1098 : //
1099 : // Attempt to enqueue a delete for the McastTreeManager.
1100 : //
1101 292 : void McastTreeManager::RetryDelete() {
1102 292 : if (!deleter()->IsDeleted())
1103 291 : return;
1104 1 : deleter()->RetryDelete();
1105 : }
1106 :
1107 : //
1108 : // Return the LifetimeActor for the McastTreeManager.
1109 : //
1110 6472 : LifetimeActor *McastTreeManager::deleter() {
1111 6472 : return deleter_.get();
1112 : }
1113 :
1114 : //
1115 : // Return the LifetimeActor for the McastTreeManager.
1116 : // Const version.
1117 : //
1118 190 : const LifetimeActor *McastTreeManager::deleter() const {
1119 190 : return deleter_.get();
1120 : }
1121 :
1122 : //
1123 : // Return true if the McastTreeManager is deleted.
1124 : //
1125 190 : bool McastTreeManager::deleted() const {
1126 190 : return deleter_->IsDeleted();
1127 : }
1128 :
1129 3172 : ErmVpnRoute *McastTreeManager::GetGlobalTreeRootRoute(
1130 : const Ip4Address &source, const Ip4Address &group) const {
1131 3172 : const McastManagerPartition *partition = GetPartition(table_->Hash(group));
1132 3172 : return partition->GetGlobalTreeRootRoute(source, group);
1133 : }
1134 :
1135 7976 : void McastTreeManager::NotifyForestNode(int part_id, const Ip4Address &source,
1136 : const Ip4Address &group) {
1137 7976 : McastManagerPartition *partition = GetPartition(part_id);
1138 7976 : partition->NotifyForestNode(source, group);
1139 7976 : }
1140 :
1141 247 : bool McastTreeManager::GetForestNodePMSI(ErmVpnRoute *rt, uint32_t *label,
1142 : Ip4Address *address, vector<string> *encap) const {
1143 247 : if (!rt || !rt->IsUsable())
1144 70 : return false;
1145 : const McastManagerPartition *partition =
1146 177 : GetPartition(rt->get_table_partition()->index());
1147 177 : return partition->GetForestNodePMSI(rt, label, address, encap);
1148 : }
|
