Debian Codegraph @

networking_bagpipe/bagpipe_bgp/engine/route_table_manager.py

raw
1 # Copyright 2014 Orange
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
6 #
7 # http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
14
15 import collections
16 from functools import reduce
17 import queue
18 import threading
19
20 from oslo_log import log as logging
21
22 from networking_bagpipe._i18n import _
23 from networking_bagpipe.bagpipe_bgp.common import log_decorator
24 from networking_bagpipe.bagpipe_bgp.common import looking_glass as lg
25 from networking_bagpipe.bagpipe_bgp.common import utils
26 from networking_bagpipe.bagpipe_bgp import engine
27 from networking_bagpipe.bagpipe_bgp.engine import bgp_peer_worker
28 from networking_bagpipe.bagpipe_bgp.engine import exa
29 from networking_bagpipe.bagpipe_bgp.engine import worker as worker_m
30
31
32 LOG = logging.getLogger(__name__)
33
34
35 def cmp(a, b):
36 return (a > b) - (b > a)
37
38
39 class Match:
40
41 def __init__(self, afi, safi, route_target):
42 assert route_target is None or isinstance(route_target,
43 exa.RouteTarget)
44 self.afi = afi
45 self.safi = safi
46 self.route_target = route_target
47
48 def __hash__(self):
49 # FIXME, could use a tuple, but RT not yet hashable
50 # return hash((self.afi, self.safi, self.route_target))
51 return hash(str(self))
52
53 def __repr__(self):
54 return "match:%s" % str(self)
55
56 def __str__(self):
57 return "{}/{},{}".format(self.afi or "*", self.safi or "*",
58 self.route_target or "*")
59
60 def __cmp__(self, other):
61 assert isinstance(other, Match)
62
63 self_afi = self.afi or engine.Subscription.ANY_AFI
64 self_safi = self.safi or engine.Subscription.ANY_SAFI
65 self_rt = self.route_target or exa.RouteTarget(0, 0)
66
67 other_afi = other.afi or engine.Subscription.ANY_AFI
68 other_safi = other.safi or engine.Subscription.ANY_SAFI
69 other_rt = other.route_target or exa.RouteTarget(0, 0)
70
71 val = cmp((self_afi, self_safi, str(self_rt)),
72 (other_afi, other_safi, str(other_rt)))
73
74 return val
75
76 def __lt__(self, other):
77 return self.__cmp__(other) == -1
78
79 def __eq__(self, other):
80 return self.__cmp__(other) == 0
81
82
83 MATCH_ANY = Match(engine.Subscription.ANY_AFI,
84 engine.Subscription.ANY_SAFI,
85 engine.Subscription.ANY_RT)
86
87
88 def matches_for(afi, safi, route_targets):
89 # generate all possible match entries for this afi/safi
90 # and these routetargets, with all possible wildcards
91 #
92 # There are 4*(n+1) possible Match object (for n route_targets)
93 for _afi in (engine.Subscription.ANY_AFI, afi):
94 for _safi in (engine.Subscription.ANY_SAFI, safi):
95 yield Match(_afi, _safi, None)
96 if route_targets is not None:
97 for rt in route_targets:
98 yield Match(_afi, _safi, rt)
99
100
101 class WorkersAndEntries:
102
103 def __init__(self):
104 self.workers = set()
105 self.entries = set()
106 self.n_local_workers = 0
107
108 def __repr__(self):
109 return "workers: {}\nentries: {}".format(self.workers,
110 self.entries)
111
112 def add_worker(self, worker):
113 '''returns True iif first local worker'''
114 self.workers.add(worker)
115 if not isinstance(worker, bgp_peer_worker.BGPPeerWorker):
116 self.n_local_workers += 1
117 return self.n_local_workers == 1
118
119 def del_worker(self, worker):
120 '''returns True iif last local worker'''
121 self.workers.remove(worker)
122 if not isinstance(worker, bgp_peer_worker.BGPPeerWorker):
123 self.n_local_workers -= 1
124 return self.n_local_workers == 0
125
126 def is_empty(self):
127 return (len(self.workers) == 0 and
128 len(self.entries) == 0)
129
130
131 STOP_EVENT = "STOP_EVENT"
132
133
134 def test_should_dispatch(route_event, target_worker):
135 '''tests if route should be dispatched to a worker
136
137 returns a (boolean,string) tuple
138 the string contains the reason why the route_event should not be
139 dispatched to target_worker
140 '''
141 if route_event.source == target_worker:
142 return (False, "not dispatching an update back to its source")
143 elif (isinstance(route_event.source, bgp_peer_worker.BGPPeerWorker) and
144 isinstance(target_worker, bgp_peer_worker.BGPPeerWorker)):
145 return (False, "do not dispatch a route between BGP peers")
146 else:
147 return (True, "")
148
149
150 class RouteTableManager(threading.Thread, lg.LookingGlassMixin,
151 utils.ClassReprMixin):
152 """Singleton class dispatching route events between workers
153
154 Events relates to BGP routes that are announced or withdrawn by workers.
155 Workers subscribe to events by indicating AFI, SAFI, Route Targets in which
156 they are interested.
157 There can be workers responsible for handling services locally (e.g. a VPN
158 instance) and workers that are BGP peers.
159
160 Though sources of routes are typically Workers, they don't need to be; any
161 class can source a route.
162 """
163
164 def __init__(self, first_local_subscriber_cb, last_local_subscriber_cb):
165 threading.Thread.__init__(self, name="RouteTableManager")
166 self.setDaemon(True)
167
168 # keys are Matches, values are WorkersAndEntries objects:
169 self._match_2_workers_entries = (
170 collections.defaultdict(WorkersAndEntries))
171
172 # workers known to us
173 # name -> worker dict
174 self._workers = {}
175
176 # keys are (source,nlri) tuples, values are Entry objects:
177 self._source_nlri_2_entry = {}
178
179 self.first_local_subscriber_callback = first_local_subscriber_cb
180 self.last_local_subscriber_callback = last_local_subscriber_cb
181
182 self._queue = queue.Queue()
183
184 @log_decorator.log_info
185 def stop(self):
186 self.enqueue(STOP_EVENT)
187
188 def run(self):
189 while True:
190 LOG.debug("RouteTableManager waiting on queue")
191 event = self._queue.get()
192 if event == STOP_EVENT:
193 LOG.info("STOP_EVENT => breaking main loop")
194 break
195 else:
196 self._on_event(event)
197 LOG.debug("RouteTableManager queue size: %d", self._queue.qsize())
198
199 LOG.info("Out of main loop")
200
201 @log_decorator.log_info
202 def _on_event(self, event):
203 try:
204 if event.__class__ == engine.RouteEvent:
205 self._receive_route_event(event)
206 elif event.__class__ == engine.Subscription:
207 self._worker_subscribes(event)
208 elif event.__class__ == engine.Unsubscription:
209 self._worker_unsubscribes(event)
210 elif event.__class__ == engine.WorkerCleanupEvent:
211 self._worker_cleanup(event.worker)
212 else:
213 raise Exception(_("unknown event: %s" % event))
214 except Exception:
215 LOG.exception("Exception during processing of event %s", event)
216
217 def enqueue(self, event):
218 self._queue.put(event)
219
220 def _check_match_2_workers_and_entries_cleanup(self, match):
221 wa = self._match_2_workers_entries.get(match)
222 if wa is None:
223 LOG.warning("why are we here ?")
224 # nothing to cleanup
225 return
226 else:
227 if wa.is_empty():
228 del self._match_2_workers_entries[match]
229
230 def callback_first_local_subscriber(self, sub):
231 if self.first_local_subscriber_callback:
232 LOG.debug("first local subscriber callback for %s ...", sub)
233 self.first_local_subscriber_callback(sub)
234
235 def callback_last_local_subscriber(self, sub):
236 if self.last_local_subscriber_callback:
237 LOG.debug("last local subscriber callback for %s ...", sub)
238 self.last_local_subscriber_callback(sub)
239
240 @log_decorator.log_info
241 def _worker_subscribes(self, sub):
242 assert isinstance(sub.worker, worker_m.Worker)
243
244 worker = sub.worker
245
246 self._workers[worker.name] = worker
247
248 match = Match(sub.afi, sub.safi, sub.route_target)
249
250 wa = self._match_2_workers_entries[match]
251
252 # update match2worker
253 if wa.add_worker(worker):
254 self.callback_first_local_subscriber(sub)
255
256 LOG.debug("match2workers: %s", wa.workers)
257
258 # re-synthesize events
259 for entry in wa.entries:
260 LOG.debug("Found an entry for this match: %s", entry)
261 event = engine.RouteEvent(engine.RouteEvent.ADVERTISE, entry)
262 (dispatch, reason) = test_should_dispatch(event, worker)
263
264 if dispatch:
265 # check if the entry carries a route_target to which the worker
266 # was already subscribed
267 for rt in entry.route_targets:
268 if Match(entry.afi,
269 entry.safi,
270 rt) in worker._rtm_matches:
271 (dispatch, reason) = (
272 False,
273 "worker already had a subscription for this route")
274 break
275
276 if dispatch:
277 LOG.info("Dispatching re-synthesized event for %s", entry)
278 worker.enqueue(event)
279 else:
280 LOG.info("%s => not dispatching re-synthesized event for %s",
281 reason, entry)
282
283 # update worker matches
284 worker._rtm_matches.add(match)
285
286 # self._dump_state()
287
288 def _worker_unsubscribes(self, sub):
289 assert isinstance(sub.worker, worker_m.Worker)
290
291 worker = sub.worker
292
293 # self._dump_state()
294
295 match = Match(sub.afi, sub.safi, sub.route_target)
296
297 # update worker matches
298 try:
299 worker._rtm_matches.remove(match)
300 except KeyError:
301 LOG.warning("worker %s unsubs' from %s but this match was"
302 " not tracked for this worker (should not happen,"
303 " this is a bug)", worker, match)
304
305 # synthesize withdraw events
306 wa = self._match_2_workers_entries.get(match)
307 if wa:
308 for entry in wa.entries:
309 intersect = set(matches_for(entry.afi,
310 entry.safi,
311 entry.route_targets)
312 ).intersection(worker._rtm_matches)
313 if len(intersect) > 0:
314 LOG.debug("Will not synthesize withdraw event for %s, "
315 "because worker subscribed to %s", entry,
316 intersect)
317 else:
318 LOG.debug("Found an entry for this match: %s", entry)
319 event = engine.RouteEvent(engine.RouteEvent.WITHDRAW,
320 entry)
321 (dispatch, reason) = test_should_dispatch(event, worker)
322 if dispatch:
323 LOG.info("Dispatching re-synthesized event for %s",
324 entry)
325 worker.enqueue(event)
326 else:
327 LOG.info("%s => not dispatching re-synthesized event"
328 " for %s", reason, entry)
329
330 # update _match_2_workers_entries
331 try:
332 if wa.del_worker(worker):
333 LOG.debug("see if need to callback on last local worker")
334 self.callback_last_local_subscriber(sub)
335 self._check_match_2_workers_and_entries_cleanup(match)
336 except KeyError:
337 LOG.warning("worker %s unsubscribed from %s but was not"
338 " subscribed yet", worker, match)
339 else: # wa is None
340 LOG.warning("worker %s unsubscribed from %s but we had no such"
341 " subscription yet", worker, match)
342
343 if len(worker._rtm_matches) == 0:
344 self._workers.pop(worker.name, None)
345
346 # self._dump_state()
347
348 @log_decorator.log
349 def _propagate_route_event(self, route_event, except_workers=None):
350 '''Propagate route_event to workers subscribed to the route
351
352 based on subscribed RTs/wildcards, and excluding the workers in
353 except_workers.
354
355 Returns the list of workers to which the event was propagated.
356 '''
357
358 re = route_event.route_entry
359
360 if except_workers is None:
361 except_workers = []
362
363 target_workers = set()
364 for match in matches_for(re.afi, re.safi, re.route_targets):
365 LOG.debug("Finding interested workers for match %s", match)
366
367 interested_workers = self._match_2_workers_entries[match].workers
368
369 LOG.debug(" Workers interested in this match: %s",
370 interested_workers)
371
372 for worker in interested_workers:
373 (dispatch, reason) = test_should_dispatch(route_event, worker)
374 if dispatch:
375 if worker not in except_workers:
376 LOG.debug("Will dispatch event to %s: %s",
377 worker, route_event)
378 target_workers.add(worker)
379 else:
380 LOG.debug("Decided not to dispatch to %s, based on"
381 " except_workers: %s", worker, route_event)
382 else:
383 LOG.debug("Decided not to dispatch to %s: %s (%s)",
384 worker, reason, route_event)
385
386 for worker in target_workers:
387 LOG.info("Dispatching event to %s: %s", worker, route_event)
388 worker.enqueue(route_event)
389
390 return target_workers
391
392 @log_decorator.log_info
393 def _receive_route_event(self, route_event):
394 entry = route_event.route_entry
395
396 LOG.debug("Try to find an entry from same worker with same nlri")
397 replaced_entry = self._source_nlri_2_entry.get((entry.source,
398 entry.nlri))
399
400 LOG.debug(" Result: %s", replaced_entry)
401
402 # replaced_entry should be non-empty for a withdraw
403 if (replaced_entry is None and
404 route_event.type == engine.RouteEvent.WITHDRAW):
405 LOG.warning("WITHDRAW but found no route that we could remove: %s",
406 route_event.route_entry)
407 return
408
409 # Propagate events to interested workers...
410 if route_event.type == engine.RouteEvent.ADVERTISE:
411
412 if replaced_entry == route_event.route_entry:
413 LOG.warning("Ignoring, the route advertized is the same as the"
414 " one previously advertized by the source %s: %s",
415 route_event.source, route_event.route_entry)
416 return
417
418 # propagate event to interested worker
419 # and include the info on the route are replaced by this
420 # route, if any
421 route_event.set_replaced_route(replaced_entry)
422
423 workers_already_notified = self._propagate_route_event(route_event)
424 else: # WITHDRAW
425 workers_already_notified = None
426
427 # Synthesize and dispatch a withdraw event for the route entry that
428 # was withdrawn or replaced, except, in the case of a replaced route,
429 # to workers that had the ADVERTISE event
430 if replaced_entry is not None:
431 LOG.debug("Synthesizing a withdraw event for replaced route %s",
432 replaced_entry)
433 removal_event = engine.RouteEvent(engine.RouteEvent.WITHDRAW,
434 replaced_entry,
435 route_event.source)
436
437 self._propagate_route_event(removal_event,
438 workers_already_notified)
439
440 # Update match2entries for the replaced_route
441 for match in matches_for(replaced_entry.afi,
442 replaced_entry.safi,
443 replaced_entry.route_targets):
444 wa = self._match_2_workers_entries.get(match, None)
445 if wa is None:
446 LOG.error("Trying to remove a route from a match, but"
447 " match %s not found - not supposed to happen"
448 " (route: %s)", match, replaced_entry)
449 else:
450 wa.entries.discard(replaced_entry)
451 self._check_match_2_workers_and_entries_cleanup(match)
452
453 # update the route entries for this source
454 replaced_entry.source._rtm_route_entries.discard(replaced_entry)
455
456 if route_event.type == engine.RouteEvent.ADVERTISE:
457 # Update match2entries and source2entries for the newly
458 # advertized route
459 for match in matches_for(entry.afi,
460 entry.safi,
461 entry.route_targets):
462 self._match_2_workers_entries[match].entries.add(entry)
463
464 entry.source._rtm_route_entries.add(entry)
465
466 # Update _source_nlri_2_entry
467 self._source_nlri_2_entry[(entry.source, entry.nlri)] = entry
468 else: # WITHDRAW
469 # Update source2entries
470 entry.source._rtm_route_entries.discard(entry)
471
472 # Update _source_nlri_2_entry
473 try:
474 del self._source_nlri_2_entry[(entry.source, entry.nlri)]
475 except KeyError:
476 LOG.error("BUG: withdraw, but nothing could be removed in "
477 "_source_nlri_2_entry")
478
479 # self._dump_state()
480
481 @log_decorator.log_info
482 def _worker_cleanup(self, worker):
483 '''Cleanup the subscriptions and routes advertised by a worker
484
485 Consider all routes announced by this worker as withdrawn.
486 Consider this worker unsubscribed from all of its current
487 subscriptions.
488 '''
489 assert isinstance(worker, worker_m.Worker)
490 # synthesize withdraw events for all routes from this worker
491 LOG.info(" Preparing to withdraw %d routes that were advertised "
492 "by worker", len(worker._rtm_route_entries))
493 for entry in worker._rtm_route_entries:
494 LOG.info(" Enqueue event to Withdraw route %s", entry)
495 self.enqueue(engine.RouteEvent(engine.RouteEvent.WITHDRAW, entry))
496
497 # remove worker from all of its subscriptions
498 for match in worker._rtm_matches:
499 wa = self._match_2_workers_entries[match]
500 if wa.del_worker(worker):
501 self.callback_last_local_subscriber(
502 engine.Subscription(match.afi, match.safi,
503 match.route_target, worker))
504 self._check_match_2_workers_and_entries_cleanup(match)
505
506 worker._rtm_matches.clear()
507
508 # self._dump_state()
509
510 def _dump_state(self):
511 if not LOG.isEnabledFor(logging.DEBUG):
512 return
513
514 dump = []
515
516 dump.append("~~~ Worker -> Matches ~~~")
517 for worker in self._workers.values():
518 dump.append(" %s" % worker)
519 matches = list(worker._rtm_matches)
520 matches.sort()
521 for match in matches:
522 dump.append(" %s" % match)
523
524 match_2_worker_dump = []
525 match_2_entries_dump = []
526
527 matches = list(self._match_2_workers_entries.keys())
528 matches.sort()
529 for match in matches:
530 match_2_worker_dump.append(" %s" % match)
531 match_2_entries_dump.append(" %s" % match)
532 wa = self._match_2_workers_entries.get(match)
533 if wa:
534 for worker in wa.workers:
535 match_2_worker_dump.append(" %s" % worker)
536 for re in wa.entries:
537 match_2_entries_dump.append(" %s" % re)
538
539 dump.append("\n~~~ Match -> Workers ~~~\n%s\n" %
540 "\n".join(match_2_worker_dump))
541
542 dump.append("~~~ Match -> Entries ~~~\n%s\n" %
543 "\n".join(match_2_entries_dump))
544
545 dump.append("~~~ (source,nlri) -> entries ~~~")
546 for ((source, nlri), entry) in self._source_nlri_2_entry.items():
547 dump.append(" ({}, {}): {}".format(source, nlri, entry))
548
549 LOG.debug("RouteTableManager data dump:\n\n%s\n", "\n".join(dump))
550
551 # Looking Glass #####
552
553 def get_lg_map(self):
554 return {"workers": (lg.COLLECTION, (self.get_lg_worker_list,
555 self.get_lg_worker_from_path_item)
556 ),
557 "routes": (lg.SUBTREE, self.get_lg_routes)}
558
559 def get_lg_routes(self, path_prefix):
560 result = {}
561
562 match_IPVPN = Match(exa.AFI.ipv4, exa.SAFI.mpls_vpn,
563 engine.Subscription.ANY_RT)
564 match_EVPN = Match(exa.AFI.l2vpn, exa.SAFI.evpn,
565 engine.Subscription.ANY_RT)
566 match_RTC = Match(exa.AFI.ipv4, exa.SAFI.rtc,
567 engine.Subscription.ANY_RT)
568 match_FlowSpecVPN = Match(exa.AFI.ipv4, exa.SAFI.flow_vpn,
569 engine.Subscription.ANY_RT)
570 for match in [match_IPVPN, match_EVPN, match_RTC, match_FlowSpecVPN]:
571 match_result = []
572 wa = self._match_2_workers_entries.get(match)
573 if wa is not None:
574 for entry in wa.entries:
575 match_result.append(
576 entry.get_looking_glass_info(path_prefix))
577 result[str(match)] = match_result
578 return result
579
580 def get_lg_worker_list(self):
581 return [{"id": worker.name}
582 for worker in self._workers.values()]
583
584 def get_lg_worker_from_path_item(self, path_item):
585 return self._workers.get(path_item, None)
586
587 def get_all_routes_but_rtc(self):
588 return [re for re in self._match_2_workers_entries[MATCH_ANY].entries
589 if (re.afi, re.safi) != (exa.AFI.ipv4, exa.SAFI.rtc)
590 ]
591
592 def get_local_routes_count(self):
593 return reduce(
594 lambda count, entry:
595 count + (not isinstance(entry.source,
596 bgp_peer_worker.BGPPeerWorker)),
597 self.get_all_routes_but_rtc(),
598 0)
599
600 def get_received_routes_count(self):
601 return reduce(
602 lambda count, entry:
603 count + isinstance(entry.source, bgp_peer_worker.BGPPeerWorker),
604 self.get_all_routes_but_rtc(),
605 0)