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 : #ifndef SRC_BGP_BGP_MULTICAST_H_
7 : #define SRC_BGP_BGP_MULTICAST_H_
8 :
9 : #include <boost/scoped_ptr.hpp>
10 :
11 : #include <set>
12 : #include <string>
13 : #include <vector>
14 :
15 : #include "base/label_block.h"
16 : #include "base/lifetime.h"
17 : #include "base/queue_task.h"
18 : #include "base/address.h"
19 : #include "bgp/bgp_ribout.h"
20 : #include "db/db_entry.h"
21 : #include "net/rd.h"
22 :
23 : class BgpOListSpec;
24 : class BgpServer;
25 : class DBTablePartBase;
26 : class ErmVpnRoute;
27 : class ErmVpnTable;
28 : class McastForwarder;
29 : class McastManagerPartition;
30 : class McastSGEntry;
31 : class McastTreeManager;
32 : class RoutingInstance;
33 : struct UpdateInfo;
34 :
35 : typedef std::vector<McastForwarder *> McastForwarderList;
36 :
37 : //
38 : // This class represents membership of a vRouter or a control-node in a (G,S)
39 : // within a multicast table.
40 : //
41 : // A vRouter is considered a member if it has advertised a route for (G,S) via
42 : // XMPP. The level_ field in McastForwarder is set to LevelNative in this case.
43 : //
44 : // A control-node is considered to be a member if it has advertised (via BGP)
45 : // an ErmVpnRoute of type LocalRoute for (G,S). The level_ field gets set to
46 : // LevelLocal in this case.
47 :
48 : // There's a 1:1 correspondence between an ErmVpnRoute of type NativeRoute or
49 : // LocalRoute and a McastForwarder. Routes in the ErmVpnTable are keyed by RD,
50 : // RouterId, Group and Source. When these routes are processed, we invert the
51 : // information and create a McastSGEntry for each unique (G,S). Information
52 : // from the RD and the IPeer from which we learnt the route is used to create
53 : // a McastForwarder. The McastForwarder is part of a set in the McastSGEntry
54 : // for the (G,S).
55 : //
56 : // A McastForwarder gets created when the DBListener for the McastTreeManager
57 : // sees a new ErmVpnRoute of type NativeRoute or LocalRoute. It's deleted when
58 : // the DBListener detects that the route in question has been deleted.
59 : //
60 : // A McastForwarder is associated with the ErmVpnRoute by setting it to be the
61 : // DBState for the McastTreeManager's listener id. The McastForwarder keeps a
62 : // back pointer to the ErmVpnRoute.
63 : //
64 : // The LabelBlockPtr is obtained from the attributes of the best path for the
65 : // ErmVpnRoute. It's used to allocate labels for the McastForwarder without
66 : // needing to reach into the route. More importantly, it's required to release
67 : // the currently allocated label when the route gets marked for deletion, at
68 : // which time there's no active path for the route.
69 : //
70 : // A McastForwarder contains a vector of pointers to other McastForwarders at
71 : // the same NodeLevel within the McastSGEntry. The collection of these links
72 : // constitutes the distribution tree for the McastSGEntry at that NodeLevel.
73 : // Note that only a single MPLS label is used for a McastForwarder in a given
74 : // distribution tree. Thus the label can be stored in the McastForwarder itself
75 : // and does not need to be part of the link information.
76 : //
77 : // If this control-node is elected as the tree builder for the (G,S), a global
78 : // distribution tree of all Local McastForwarders is built. Relevant edges of
79 : // this global distribution tree are advertised to each control-node by adding
80 : // a GlobalTreeRoute for each Local McastForwarder. The global_tree_route_ is
81 : // used to keep track of this ErmVpnRoute and [Add|Delete]GlobalTreeRoute are
82 : // used to add or delete the route.
83 : //
84 : class McastForwarder : public DBState {
85 : public:
86 : McastForwarder(McastSGEntry *sg_entry, ErmVpnRoute *route);
87 : ~McastForwarder();
88 :
89 : bool Update(ErmVpnRoute *route);
90 : std::string ToString() const;
91 : uint8_t GetLevel() const;
92 :
93 : McastForwarder *FindLink(McastForwarder *forwarder);
94 : void AddLink(McastForwarder *forwarder);
95 : void RemoveLink(McastForwarder *forwarder);
96 : void FlushLinks();
97 :
98 : void AllocateLabel();
99 : void ReleaseLabel();
100 :
101 : void AddGlobalTreeRoute();
102 : void DeleteGlobalTreeRoute();
103 : UpdateInfo *GetUpdateInfo(ErmVpnTable *table);
104 :
105 4931 : uint8_t level() const { return level_; }
106 15921 : uint32_t label() const { return label_; }
107 8 : const LabelBlock *label_block() const { return label_block_.get(); }
108 7175 : Ip4Address address() const { return address_; }
109 4571 : std::vector<std::string> encap() const { return encap_; }
110 12312 : ErmVpnRoute *route() { return route_; }
111 43086 : const RouteDistinguisher &route_distinguisher() const { return rd_; }
112 25865 : Ip4Address router_id() const { return router_id_; }
113 :
114 : bool empty() { return tree_links_.empty(); }
115 1586 : ErmVpnRoute *global_tree_route() const { return global_tree_route_; }
116 :
117 : private:
118 : friend class BgpMulticastTest;
119 : friend class ShowMulticastManagerDetailHandler;
120 :
121 : void AddLocalOListElems(BgpOListSpec *olist_spec);
122 : void AddGlobalOListElems(BgpOListSpec *olist_spec);
123 :
124 : McastSGEntry *sg_entry_;
125 : ErmVpnRoute *route_;
126 : ErmVpnRoute *global_tree_route_;
127 : uint8_t level_;
128 : LabelBlockPtr label_block_;
129 : uint32_t label_;
130 : Ip4Address address_;
131 : RouteDistinguisher rd_;
132 : Ip4Address router_id_;
133 : std::vector<std::string> encap_;
134 : McastForwarderList tree_links_;
135 :
136 : DISALLOW_COPY_AND_ASSIGN(McastForwarder);
137 : };
138 :
139 : //
140 : // Key comparison class for McastForwarder.
141 : //
142 : struct McastForwarderCompare {
143 12343 : bool operator()(const McastForwarder *lhs,
144 : const McastForwarder *rhs) const {
145 12343 : if (lhs->route_distinguisher() < rhs->route_distinguisher())
146 3143 : return true;
147 9200 : if (lhs->route_distinguisher() > rhs->route_distinguisher())
148 4022 : return false;
149 5178 : if (lhs->router_id() < rhs->router_id())
150 842 : return true;
151 4336 : if (lhs->router_id() > rhs->router_id())
152 490 : return false;
153 :
154 3846 : return false;
155 : }
156 : };
157 :
158 : //
159 : // This class represents a (G,S) entry within a McastManagerPartition. The
160 : // routes in the ErmVpnTable are keyed by RD, RouterId, Group and Source.
161 : // When these routes are processed, we rearrange the information and create a
162 : // McastSGEntry for each unique (G,S). The RD and RouterId in the ErmVpnRoute
163 : // represent a McastForwarder.
164 : //
165 : // A McastSGEntry is part of a set in the McastManagerPartition. In addition
166 : // is may also temporarily be on the WorkQueue in the McastManagerPartition
167 : // if the distribution tree needs to be updated.
168 : //
169 : // A McastSGEntry is created when the DBListener for the ErmVpnTable sees the
170 : // first ErmVpnRoute containing the (G,S) and needs to create a McastForwarder.
171 : // It is destroyed when all McastForwarders under it are gone. The delete is
172 : // done from the McastManagerPartition's WorkQueue callback routine to ensure
173 : // that there are no stale references to it on the WorkQueue. Note that the
174 : // WorkQueue cannot contain more than one reference to a given McastSGEntry.
175 : //
176 : // Two sets of pointers to McastForwarders are maintained in a McastSGEntry -
177 : // for Native and Local tree levels. The McastForwarders at the Native level
178 : // correspond to vRouters that have subscribed to the (G,S). McastForwarders
179 : // at the Local level correspond to control-nodes (including this one) that
180 : // are advertising their local subtree's candidate edges via a LocalTreeRoute.
181 : // The sets are keyed by the RD and RouterId of the McastForwarders.
182 : //
183 : // A local distribution tree of all Native McastForwarders is built and the
184 : // last leaf in the tree is designated as the forest node. The forest_node_
185 : // is used to keep track of this McastForwarder. A LocalTreeRoute is added to
186 : // the ErmVpnTable and the forest node's candidate edges are advertised using
187 : // the EdgeDiscovery attribute. The local_tree_route_ keeps track of the route.
188 : //
189 : // If this control-node is elected to be the tree builder for this (G,S), a
190 : // global distribution tree of all Local McastForwarders is built. Relevant
191 : // edges of this global distribution tree are advertised to each control-node
192 : // by adding a GlobalTreeRoute for each Local McastForwarder. The forwarding
193 : // edges are encoded using the EdgeForwarding attribute.
194 : //
195 : // Whether the tree builder is this control-node or another control-node, the
196 : // tree_result_route_ member keeps track of the GlobalTreeRoute that contains
197 : // the forwarding edges relevant to this control-node. The RouterId in the
198 : // GlobalTreeRoute is used to decide if it's for this control-node. We set
199 : // our DBState on this ErmVpnRoute to be the McastSGEntry.
200 : //
201 : // The McastSGEntry is enqueued on the WorkQueue in the McastManagerPartition
202 : // when a McastForwarder is added, changed or deleted so that the distribution
203 : // tree and the necessary LocalTreeRoute or GlobalTreeRoutes can be updated.
204 : //
205 : class McastSGEntry : public DBState {
206 : public:
207 : McastSGEntry(McastManagerPartition *partition,
208 : Ip4Address group, Ip4Address source);
209 : ~McastSGEntry();
210 :
211 : std::string ToString() const;
212 :
213 : void AddForwarder(McastForwarder *forwarder);
214 : void ChangeForwarder(McastForwarder *forwarder);
215 : void DeleteForwarder(McastForwarder *forwarder);
216 :
217 : const RouteDistinguisher &GetSourceRd() const;
218 : void AddLocalTreeRoute();
219 : void DeleteLocalTreeRoute();
220 : void UpdateLocalTreeRoute();
221 : void UpdateTree();
222 : void NotifyForestNode();
223 : bool IsForestNode(McastForwarder *forwarder);
224 :
225 138657 : Ip4Address group() const { return group_; }
226 129285 : Ip4Address source() const { return source_; }
227 2514 : McastManagerPartition *partition() { return partition_; }
228 2141 : const ErmVpnRoute *tree_result_route() const { return tree_result_route_; }
229 425 : void set_tree_result_route(ErmVpnRoute *route) {
230 425 : tree_result_route_ = route;
231 425 : }
232 425 : void clear_tree_result_route() { tree_result_route_ = NULL; }
233 :
234 5356 : bool on_work_queue() { return on_work_queue_; }
235 3268 : void set_on_work_queue() { on_work_queue_ = true; }
236 3268 : void clear_on_work_queue() { on_work_queue_ = false; }
237 :
238 : bool empty() const;
239 : ErmVpnRoute *GetGlobalTreeRootRoute() const;
240 : bool GetForestNodePMSI(uint32_t *label, Ip4Address *address,
241 : std::vector<std::string> *encap) const;
242 : bool IsTreeBuilder(uint8_t level) const;
243 :
244 : private:
245 : friend class BgpMulticastTest;
246 : friend class ShowMulticastManagerDetailHandler;
247 :
248 : typedef std::set<McastForwarder *, McastForwarderCompare> ForwarderSet;
249 :
250 : void UpdateTree(uint8_t level);
251 : void UpdateRoutes(uint8_t level);
252 :
253 : McastManagerPartition *partition_;
254 : Ip4Address group_, source_;
255 : McastForwarder *forest_node_;
256 : ErmVpnRoute *local_tree_route_;
257 : ErmVpnRoute *tree_result_route_;
258 : std::vector<ForwarderSet *> forwarder_sets_;
259 : std::vector<bool> update_needed_;
260 : bool on_work_queue_;
261 :
262 : DISALLOW_COPY_AND_ASSIGN(McastSGEntry);
263 : };
264 :
265 : //
266 : // Key comparison class for McastSGEntry.
267 : //
268 : struct McastSGEntryCompare {
269 35788 : bool operator()(const McastSGEntry *lhs, const McastSGEntry *rhs) const {
270 35788 : if (lhs->group().to_ulong() < rhs->group().to_ulong()) {
271 2877 : return true;
272 : }
273 32911 : if (lhs->group().to_ulong() > rhs->group().to_ulong()) {
274 732 : return false;
275 : }
276 32179 : if (lhs->source().to_ulong() < rhs->source().to_ulong()) {
277 345 : return true;
278 : }
279 31834 : if (lhs->source().to_ulong() > rhs->source().to_ulong()) {
280 94 : return false;
281 : }
282 31740 : return false;
283 : }
284 : };
285 :
286 : //
287 : // This class represents a partition in the McastTreeManager. It is used to
288 : // maintain membership information for a subset of the (G,S) entries in the
289 : // associated ErmVpnTable and to calculate and store distribution trees for
290 : // each of those (G,S) entries.
291 : //
292 : // The partition for a (G,S) is determined by a hash function. Consequently,
293 : // information about all McastForwarders that have sent joins for a (G,S) is
294 : // always under a single partition.
295 : //
296 : // A McastManagerPartition keeps a set of pointers to McastSGEntrys for the
297 : // (G,S) states that fall under the partition. The set is keyed by the group
298 : // and source addresses.
299 : //
300 : // A WorkQueue of pointers to McastSGEntrys is used to keep track of entries
301 : // that need their distribution tree to be updated. The use of the WorkQueue
302 : // also allows us to combine multiple McastForwarder join/leave events into
303 : // a smaller number of updates to the distribution tree.
304 : //
305 : // All McastManagerPartitions are allocated when the McastTreeManager gets
306 : // initialized and are freed when the McastTreeManager is terminated.
307 : //
308 : class McastManagerPartition {
309 : public:
310 : McastManagerPartition(McastTreeManager *tree_manager, size_t part_id);
311 : ~McastManagerPartition();
312 :
313 : McastSGEntry *FindSGEntry(const Ip4Address &group,
314 : const Ip4Address &source);
315 : const McastSGEntry *FindSGEntry(const Ip4Address &group,
316 : const Ip4Address &source) const;
317 : McastSGEntry *LocateSGEntry(Ip4Address group, Ip4Address source);
318 : void EnqueueSGEntry(McastSGEntry *sg_entry);
319 :
320 : DBTablePartBase *GetTablePartition();
321 : const RoutingInstance *routing_instance() const;
322 : BgpServer *server();
323 : const BgpServer *server() const;
324 : McastTreeManager *tree_manager() const { return tree_manager_; }
325 42877 : bool empty() const { return sg_list_.empty(); }
326 190 : size_t size() const { return sg_list_.size(); }
327 : ErmVpnRoute *GetGlobalTreeRootRoute(const Ip4Address &source,
328 : const Ip4Address &group) const;
329 : void NotifyForestNode(const Ip4Address &source, const Ip4Address &group);
330 : bool GetForestNodePMSI(ErmVpnRoute *rt, uint32_t *label,
331 : Ip4Address *address,
332 : std::vector<std::string> *encap) const;
333 :
334 : private:
335 : friend class BgpMulticastTest;
336 : friend class ShowMulticastManagerDetailHandler;
337 :
338 : typedef std::set<McastSGEntry *, McastSGEntryCompare> SGList;
339 :
340 : bool ProcessSGEntry(McastSGEntry *sg_entry);
341 :
342 : McastTreeManager *tree_manager_;
343 : size_t part_id_;
344 : SGList sg_list_;
345 : int update_count_;
346 : WorkQueue<McastSGEntry *> work_queue_;
347 :
348 : DISALLOW_COPY_AND_ASSIGN(McastManagerPartition);
349 : };
350 :
351 : //
352 : // This class represents the multicast tree manager for an ErmVpnTable.
353 : //
354 : // It is responsible for listening to route notifications on the associated
355 : // ErmVpnTable and building distribution trees for edge replicated multicast.
356 : // A local distribution tree consisting of all the vRouters that subscribed
357 : // to this control-node is built for each (G,S). Further, if this control
358 : // node is elected to be the tree builder for a (G,S) a global distribution
359 : // is also built. The global tree is built by selecting edges from the set
360 : // of candidate edges advertised by each control-node.
361 : //
362 : // It also provides the ErmVpnTable class with an API to get the UpdateInfo
363 : // for a route in the ErmVpnTable. This is used by the table's Export method
364 : // to construct the RibOutAttr for the multicast routes. This is how we send
365 : // the label and OList information for a (G,S) to the XMPP peers.
366 : //
367 : // A McastTableManager keeps a vector of pointers to McastManagerPartitions.
368 : // The number of partitions is the same as the DB partition count. Each such
369 : // partition contains a subset of (G,S) entries learnt from the route table.
370 : // The concurrency model is that each McastManagerPartition can be updated
371 : // with membership information and can build distribution trees independently
372 : // of the other partitions.
373 : //
374 : // There's a 1:1 relationship between the McastTreeManager a ErmVpnTable with
375 : // the McastTreeManager being dependent of the ErmVpnTable via LifetimeManager
376 : // infrastructure. The McastTreeManager is created when the ErmVpnTable gets
377 : // associated with a RoutingInstance. A McastTreeManager can be destroyed when
378 : // all McastManagerPartitions are empty i.e. when all McastSGEntrys in all the
379 : // partition have been cleaned up. Actual deletion happens via LifetimeManager
380 : // infrastructure.
381 : //
382 : // Note that we do not create a McastTreeManager for the ErmVpnTable in the
383 : // default routing instance i.e. bgp.ermvpn.0.
384 : //
385 : class McastTreeManager {
386 : public:
387 : static const int kDegree = 4;
388 :
389 : typedef std::vector<McastManagerPartition *> PartitionList;
390 : typedef PartitionList::const_iterator const_iterator;
391 :
392 : enum NodeLevel {
393 : LevelFirst = 0,
394 : LevelNative = 0,
395 : LevelLocal = 1,
396 : LevelCount = 2,
397 : };
398 :
399 : explicit McastTreeManager(ErmVpnTable *table);
400 : virtual ~McastTreeManager();
401 :
402 6667 : const_iterator begin() const { return partitions_.begin(); }
403 6857 : const_iterator end() const { return partitions_.end(); }
404 :
405 : virtual void Initialize();
406 : virtual void Terminate();
407 :
408 : McastManagerPartition *GetPartition(int part_id);
409 : const McastManagerPartition *GetPartition(int part_id) const;
410 :
411 : virtual UpdateInfo *GetUpdateInfo(ErmVpnRoute *route);
412 : DBTablePartBase *GetTablePartition(size_t part_id);
413 8258 : ErmVpnTable *table() { return table_; }
414 10287 : const ErmVpnTable *table() const { return table_; }
415 :
416 : void ManagedDelete();
417 : void Shutdown();
418 : bool MayDelete() const;
419 : void RetryDelete();
420 :
421 : LifetimeActor *deleter();
422 : const LifetimeActor *deleter() const;
423 : bool deleted() const;
424 : const ErmVpnRoute *GetGlobalErmVpnTreeMvpnRoute() const;
425 : virtual ErmVpnRoute *GetGlobalTreeRootRoute(const Ip4Address &source,
426 : const Ip4Address &group) const;
427 : void NotifyForestNode(int part_id, const Ip4Address &source,
428 : const Ip4Address &group);
429 : virtual bool GetForestNodePMSI(ErmVpnRoute *rt, uint32_t *label,
430 : Ip4Address *address, std::vector<std::string> *encap) const;
431 :
432 : private:
433 : friend class BgpMulticastTest;
434 : friend class ShowMulticastManagerDetailHandler;
435 :
436 : class DeleteActor;
437 :
438 : void AllocPartitions();
439 : void FreePartitions();
440 : void TreeNodeListener(McastManagerPartition *partition,
441 : ErmVpnRoute *route);
442 : void TreeResultListener(McastManagerPartition *partition,
443 : ErmVpnRoute *route);
444 : void RouteListener(DBTablePartBase *tpart, DBEntryBase *db_entry);
445 :
446 : ErmVpnTable *table_;
447 : int listener_id_;
448 : PartitionList partitions_;
449 :
450 : boost::scoped_ptr<DeleteActor> deleter_;
451 : LifetimeRef<McastTreeManager> table_delete_ref_;
452 :
453 : DISALLOW_COPY_AND_ASSIGN(McastTreeManager);
454 : };
455 :
456 : #endif // SRC_BGP_BGP_MULTICAST_H_
|
