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