| 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 |