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