Debian Codegraph @

networking_bagpipe/bagpipe_bgp/engine/tracker_worker.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 abc
16 import socket
17
18 from oslo_log import log as logging
19
20 from networking_bagpipe.bagpipe_bgp.common import log_decorator
21 from networking_bagpipe.bagpipe_bgp.common import looking_glass as lg
22 from networking_bagpipe.bagpipe_bgp.common import utils
23 from networking_bagpipe.bagpipe_bgp import engine
24 from networking_bagpipe.bagpipe_bgp.engine import exa
25 from networking_bagpipe.bagpipe_bgp.engine import worker
26
27
28 # Explanations on FilteredRoute
29
30 # We need to call self.best_route_removed for a route that was
31 # implicitly withdrawn, except if, in best_routes, there is
32 # a route that is the same with reference to what the
33 # best_route_removed callback will do:
34 # - if there is a route with same nexthop, same encap, same label
35 # (other attributes make the route different)
36 # => no call to best_route_removed
37 # - if there is a route with same nexthop, but a different label or
38 # a different encap
39 # => need to call best_route_removed
40 #
41 # Similarly, when multiple best routes exist for an entry
42 # (ECMP case), we don't want to call new_best_route multiple times
43 # uselessly for instance for two routes that would be 'same' wrt
44 # the actions done by the new_best_route callback. So we will do a
45 # call to self.new_best_route... *only* if the
46 # new_route is different from all current best routes.
47 #
48 # FilteredRoute is the class we use to identify a route
49 # that would be the 'same', based on the above. For instance
50 # FilteredRoute removes information on the .source and
51 # only BGP attributes that are used by callbacks.
52 keep_attributes_default = [exa.Attribute.CODE.NEXT_HOP,
53 exa.Attribute.CODE.PMSI_TUNNEL,
54 exa.Attribute.CODE.MED,
55 exa.Attribute.CODE.EXTENDED_COMMUNITY,
56 exa.Attribute.CODE.LOCAL_PREF]
57
58
59 class FilteredRoute(engine.RouteEntry):
60
61 def __init__(self, re, keep_attributes=None):
62 if keep_attributes is None:
63 keep_attributes = keep_attributes_default
64
65 attributes = exa.Attributes()
66 for (attribute_id, attribute) in re.attributes.items():
67 if attribute_id in keep_attributes:
68 attributes.add(attribute)
69
70 super().__init__(re.nlri, None, attributes)
71
72
73 def equivalent_route_in_routes(function, route, routes):
74 reference = function(route)
75 for r in routes:
76 if function(r) == reference:
77 return True
78 return False
79
80 # a compare_route callback has the following signature:
81 #
82 # def compare_route(self, route_a, route_b):
83 # """
84 # should return:
85 # - an int>0 if route_a is better than route_b
86 # - an int<0 if route_b is better than route_a
87 # - else 0
88 # """
89
90 # TODO(tmorin): both comparison should MAC Mobility if present
91
92
93 def compare_ecmp(worker, route_a, route_b):
94 # makes a comparison based on LOCAL_PREF
95 # if route has no LOCAL_PREF, use default value (100) as defined in exabgp
96 l_a = route_a.attributes.get(exa.Attribute.CODE.LOCAL_PREF)
97 l_a = l_a.localpref if l_a else 100
98 l_b = route_b.attributes.get(exa.Attribute.CODE.LOCAL_PREF)
99 l_b = l_b.localpref if l_b else 100
100 return (l_a > l_b) - (l_b > l_a)
101
102
103 def compare_no_ecmp(worker, route_a, route_b):
104 '''comparison operator without ECMP
105
106 This compares the two routes in a consistent fashion, but two routes
107 will never be considered of equal cost.
108 The comparison is 'salted' so that two distinct VRFs (e.g. on two distinct
109 bagpipe-bgp instances will not necessarily elect the same route as the
110 best one).
111 '''
112 worker.log.trace("compare_no_ecmp used")
113 base_comparison = compare_ecmp(worker, route_a, route_b)
114 if base_comparison:
115 return base_comparison
116
117 salt = socket.gethostname() + worker.name
118 hash_a = hash(salt + repr(route_a))
119 hash_b = hash(salt + repr(route_b))
120 cmp_hashes = (hash_a > hash_b) - (hash_b > hash_a)
121
122 if cmp_hashes:
123 return cmp_hashes
124
125 return (route_a > route_b) - (route_b > route_a)
126
127
128 class TrackerWorker(worker.Worker, lg.LookingGlassLocalLogger,
129 metaclass=abc.ABCMeta):
130
131 def __init__(self, bgp_manager, worker_name,
132 compare_routes=compare_no_ecmp):
133
134 worker.Worker.__init__(self, bgp_manager, worker_name)
135 lg.LookingGlassLocalLogger.__init__(self)
136
137 # dict: entry -> list of routes:
138 self.tracked_entry_2_routes = dict()
139 # dict: entry -> set of best_routes:
140 self.tracked_entry_2_best_routes = dict()
141
142 self._compare_routes = compare_routes
143
144 @log_decorator.log
145 def _on_event(self, event):
146 new_route = event.route_entry
147 filtered_new_route = FilteredRoute(new_route)
148
149 entry = self.route_to_tracked_entry(new_route)
150
151 if entry is None:
152 self.log.debug("Route not mapped to a tracked entry, ignoring: %s",
153 new_route)
154 return
155
156 self.log.trace("tracked_entry for this route: %s (type: %s)",
157 TrackerWorker._display_entry(entry), type(entry))
158
159 self._dump_state()
160
161 all_routes = self.tracked_entry_2_routes.setdefault(entry, [])
162
163 self.log.debug("We currently have %d route%s for this entry",
164 len(all_routes), utils.plural(all_routes))
165
166 if event.type == engine.RouteEvent.ADVERTISE:
167
168 withdrawn_best_routes = []
169
170 best_routes = self.tracked_entry_2_best_routes.get(entry)
171
172 if best_routes is None:
173 self.log.trace("We had no route for this entry (%s)")
174 self.tracked_entry_2_best_routes[entry] = {new_route}
175 best_routes = set()
176 self._call_new_best_route(entry, filtered_new_route)
177 else:
178 if event.replaced_route is not None:
179 self.log.trace("Will remove replaced route from all_routes"
180 " and best_routes: %s",
181 event.replaced_route)
182 try:
183 all_routes.remove(event.replaced_route)
184 except ValueError:
185 # we did not have any route for this entry
186 self.log.error("replaced_route is an entry for which "
187 "we had no route ??? (bug ?)")
188
189 if event.replaced_route in best_routes:
190 self.log.trace(
191 "Removing replaced_route from best_routes")
192 best_routes.remove(event.replaced_route)
193 withdrawn_best_routes.append(event.replaced_route)
194 else:
195 self.log.trace("replaced_route is not in best_routes")
196 self.log.trace("best_routes: %s", best_routes)
197 else:
198 self.log.trace("No replaced route to remove")
199
200 call_new_best_route_4_all = False
201 if len(best_routes) == 0:
202 self.log.trace("All best routes have been replaced")
203 self._recompute_best_routes(all_routes, best_routes)
204 if best_routes:
205 current_best = next(iter(best_routes))
206 self.log.trace("We'll need to call new_best_route for "
207 "all our new best routes")
208 call_new_best_route_4_all = True
209 else:
210 current_best = None
211 call_new_best_route_4_all = False
212 else:
213 # (if there is more than one route in the best routes, we
214 # take the first one)
215 current_best = next(iter(best_routes))
216
217 self.log.trace("Current best route: %s", current_best)
218
219 if new_route == current_best:
220 self.log.info("New route is a route we already had, "
221 "nothing to do.")
222 # nothing to do
223 return
224
225 # let's find if we need to update our best routes
226 if current_best:
227 route_comparison = self._compare_routes(self, new_route,
228 current_best)
229 else:
230 route_comparison = 1
231
232 self.log.trace("route_comparison: %d", route_comparison)
233
234 if route_comparison > 0:
235 # new_route is a strictly better route than any current
236 # one, discard all the current best routes
237 self.log.trace("Replacing all best routes with new one")
238 withdrawn_best_routes.extend(best_routes.copy())
239 best_routes.clear()
240 best_routes.add(new_route)
241 self._call_new_best_route(entry, filtered_new_route)
242 call_new_best_route_4_all = False
243 elif route_comparison == 0:
244 # new_route is as good as the current ones
245 self.log.trace("Adding new_route to best_routes...")
246
247 if call_new_best_route_4_all:
248 self._call_new_best_route_for_routes(entry,
249 best_routes)
250
251 if not equivalent_route_in_routes(FilteredRoute,
252 new_route,
253 best_routes):
254 best_routes.add(new_route)
255 self.log.trace("Calling self.new_best_route since we "
256 "yet had no such route in best routes")
257 self._call_new_best_route(entry, filtered_new_route)
258 else:
259 best_routes.add(new_route)
260 self.log.trace("Not calling new_best_route since we "
261 "had received a similar route already")
262 else:
263 self.log.trace("The route is no better than current "
264 "best ones")
265
266 if call_new_best_route_4_all:
267 self._call_new_best_route_for_routes(entry,
268 best_routes)
269
270 self.log.trace("Considering implicitly withdrawn best routes")
271 for r in withdrawn_best_routes:
272 self._selective_best_route_removed(entry,
273 r, best_routes,
274 False)
275
276 # add the route to the list of routes for this entry
277 self.log.trace("Adding route to all_routes for this entry")
278 all_routes.append(new_route)
279
280 else: # RouteEvent.WITHDRAW
281
282 withdrawn_route = new_route
283
284 self.log.trace("Removing route from all_routes for this entry")
285
286 # let's update known routes for this entry
287 try:
288 all_routes.remove(withdrawn_route)
289 except ValueError:
290 # we did not have any route for this entry
291 self.log.error("Withdraw received for an entry for which we "
292 "had no route ??? (not supposed to happen)")
293
294 # let's now update best routes
295 best_routes = self.tracked_entry_2_best_routes.get(entry)
296
297 if best_routes is None:
298 # we did not have any route for this entry
299 self.log.error("Withdraw received for an entry for which we "
300 "had no route: not supposed to happen!")
301 return
302
303 if withdrawn_route in best_routes:
304 self.log.trace("The event received is about a route which "
305 "is among the best routes for this entry")
306 # remove the route from best_routes
307 best_routes.remove(withdrawn_route)
308
309 withdrawn_route_is_last = False
310 if len(best_routes) == 0:
311 # we don't have any best route left...
312 self._recompute_best_routes(all_routes, best_routes)
313
314 if len(best_routes) > 0:
315 self._call_new_best_route_for_routes(entry,
316 best_routes)
317 else:
318 self.log.trace("Cleanup all_routes and best_routes")
319 withdrawn_route_is_last = True
320 del self.tracked_entry_2_best_routes[entry]
321 del self.tracked_entry_2_routes[entry]
322
323 self._selective_best_route_removed(entry,
324 withdrawn_route,
325 best_routes,
326 withdrawn_route_is_last)
327 else:
328 self.log.trace("The event received is not related to any "
329 "of the best routes for this entry")
330 # no need to update our best route list
331 pass
332
333 self.log.info("We now have %d route%s for this entry.",
334 len(all_routes), utils.plural(all_routes))
335
336 self._dump_state()
337
338 def _recompute_best_routes(self, all_routes, best_routes):
339 '''internal method to update best routes
340
341 update best_routes to contain the best routes from all_routes, based
342 on _compare_routes
343 '''
344
345 new_best_routes = []
346 for route in all_routes:
347 if len(new_best_routes) == 0:
348 new_best_routes = [route]
349 continue
350
351 comparison = self._compare_routes(self, route, new_best_routes[0])
352 if comparison > 0:
353 new_best_routes = [route]
354 elif comparison == 0:
355 new_best_routes.append(route)
356
357 best_routes.clear()
358 best_routes.update(new_best_routes)
359
360 self.log.trace("Recomputed new best routes: %s", best_routes)
361
362 @log_decorator.log
363 def _selective_best_route_removed(self, entry, withdrawn_route,
364 filtered_best_routes,
365 withdrawn_route_is_last):
366 if not equivalent_route_in_routes(FilteredRoute,
367 withdrawn_route,
368 filtered_best_routes):
369 self._call_best_route_removed(entry,
370 FilteredRoute(withdrawn_route),
371 withdrawn_route_is_last)
372 else:
373 self.log.trace("No need to call best_route_removed: %s",
374 FilteredRoute(withdrawn_route))
375
376 def equivalent_route_in_best_routes(self, route, function):
377 # This method checks if there is in the best routes for the same
378 # tracked entry as 'route', at least one route r for which function(r)
379 # is equal to function(route)
380 return equivalent_route_in_routes(
381 function,
382 route,
383 self.tracked_entry_2_best_routes.get(
384 self.route_to_tracked_entry(route),
385 []
386 )
387 )
388
389 def synthesize_withdraw_all(self, afi, safi):
390 for tracked_entry, routes in list(self.tracked_entry_2_routes.items()):
391 self.log.trace("Synthesizing withdraws for all routes of %s with "
392 "AFI(%s)/SAFI(%s)", tracked_entry, afi, safi)
393 for route in routes:
394 if (route.nlri.afi, route.nlri.safi) == (afi, safi):
395 self._on_event(
396 engine.RouteEvent(engine.RouteEvent.WITHDRAW, route)
397 )
398
399 @log_decorator.log
400 def _call_new_best_route_for_routes(self, entry, routes):
401 routes_no_dups = {FilteredRoute(r) for r in routes}
402 self.log.debug(" After filtering duplicates: %s", routes_no_dups)
403 for route in routes_no_dups:
404 self._call_new_best_route(entry, route)
405
406 @log_decorator.log
407 def _call_new_best_route(self, entry, new_route):
408 try:
409 self.new_best_route(entry, new_route)
410 except Exception as e:
411 self.log.error("Exception in <subclass>.new_best_route: %s", e)
412 if self.log.isEnabledFor(logging.WARNING):
413 self.log.exception("")
414
415 @log_decorator.log
416 def _call_best_route_removed(self, entry, old_route, last):
417 try:
418 self.best_route_removed(entry, old_route, last)
419 except Exception as e:
420 self.log.error("Exception in <subclass>.best_route_removed: %s",
421 e)
422 if self.log.isEnabledFor(logging.WARNING):
423 self.log.exception("")
424
425 # Callbacks for subclasses ########################
426
427 @abc.abstractmethod
428 def route_to_tracked_entry(self, route):
429 """Hook to control mapping from a route to a tracked entry
430
431 This method is how the subclass maps a BGP route into an object that
432 the TrackerWorker code will track.
433
434 For instance, a VPN VRF is expected to keep track of IP prefixes;
435 hence the route2tracked_entry code for a VRF could return the IP prefix
436 in the VPNv4 route.
437 The result will be that the TrackerWorker code will keep track, for a
438 each prefix, of all the routes and of the best routes.
439 """
440 pass
441
442 @abc.abstractmethod
443 def new_best_route(self, entry, new_route):
444 '''New Best Route hook
445
446 A new best route has been advertized for this tracked entry
447 '''
448 pass
449
450 @abc.abstractmethod
451 def best_route_removed(self, entry, old_route, last):
452 '''Best Route removed hook
453
454 A route that was a best route for this tracked entry has been
455 removed. The 'last' flag indicates if this was the last route
456 for this tracked entry.
457 '''
458 pass
459
460 # Debug support methods #########
461
462 def _dump_state(self):
463 if self.log.isEnabledFor(logging.TRACE):
464 self.log.trace("--- tracked_entry_2_routes ---")
465 for (entry, routes) in self.tracked_entry_2_routes.items():
466 self.log.trace(
467 " Entry: %s", TrackerWorker._display_entry(entry))
468 for route in routes:
469 self.log.trace(" Route: %s", route)
470
471 self.log.trace("--- tracked_entry_2_best_routes ---")
472 for (entry, best_routes) in \
473 self.tracked_entry_2_best_routes.items():
474 self.log.trace(" Entry: %s",
475 TrackerWorker._display_entry(entry))
476 for route in best_routes:
477 self.log.trace(" Route: %s", route)
478
479 self.log.trace("--- ---")
480
481 @staticmethod
482 def _display_entry(entry):
483 if (isinstance(entry, tuple) and len(entry) > 0 and
484 isinstance(entry[0], type)):
485 return repr(tuple([entry[0].__name__] + list(entry[1:])))
486 else:
487 return repr(entry)
488
489 # Looking glass ###########
490
491 def get_lg_map(self):
492 return {"received_routes": (lg.SUBTREE, self.get_lg_all_routes),
493 "best_routes": (lg.SUBTREE, self.get_lg_best_routes)}
494
495 def get_lg_all_routes(self, path_prefix):
496 return self._get_lg_routes(path_prefix,
497 self.tracked_entry_2_routes)
498
499 def get_lg_best_routes(self, path_prefix):
500 return self._get_lg_routes(path_prefix,
501 self.tracked_entry_2_best_routes)
502
503 def _get_lg_routes(self, path_prefix, route_dict):
504 routes = {}
505 for entry in route_dict.keys():
506 entry_repr = self._display_entry(entry)
507 routes[entry_repr] = [route.get_looking_glass_info(path_prefix)
508 for route in route_dict[entry]]
509 return routes