ryu/build/lib.linux-armv7l-2.7/ryu/services/protocols/bgp/info_base/base.py

   1 # Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
   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
  12 # implied.
  13 # See the License for the specific language governing permissions and
  14 # limitations under the License.
  15 """
  16  Defines some model classes related BGP.
  17
  18  These class include types used in saving information sent/received over BGP
  19  sessions.
  20 """
  21 import abc
  22 from abc import ABCMeta
  23 from abc import abstractmethod
  24 from copy import copy
  25 import logging
  26 import functools
  27 import netaddr
  28 import six
  29
  30 from ryu.lib.packet.bgp import RF_IPv4_UC
  31 from ryu.lib.packet.bgp import RouteTargetMembershipNLRI
  32 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_EXTENDED_COMMUNITIES
  33 from ryu.lib.packet.bgp import BGPPathAttributeLocalPref
  34 from ryu.lib.packet.bgp import BGP_ATTR_TYPE_AS_PATH
  35
  36 from ryu.services.protocols.bgp.base import OrderedDict
  37 from ryu.services.protocols.bgp.constants import VPN_TABLE
  38 from ryu.services.protocols.bgp.constants import VRF_TABLE
  39 from ryu.services.protocols.bgp.model import OutgoingRoute
  40 from ryu.services.protocols.bgp.processor import BPR_ONLY_PATH
  41 from ryu.services.protocols.bgp.processor import BPR_UNKNOWN
  42
  43
  44 LOG = logging.getLogger('bgpspeaker.info_base.base')
  45
  46
  47 @six.add_metaclass(ABCMeta)
  48 class Table(object):
  49     """A container for holding information about destination/prefixes.
  50
  51     Routing information base for a particular afi/safi.
  52     This is a base class which should be sub-classed for different route
  53     family. A table can be uniquely identified by (Route Family, Scope Id).
  54     """
  55     ROUTE_FAMILY = RF_IPv4_UC
  56
  57     def __init__(self, scope_id, core_service, signal_bus):
  58         self._destinations = dict()
  59         # Scope in which this table exists.
  60         # If this table represents the VRF, then this could be a VPN ID.
  61         # For global/VPN tables this should be None
  62         self._scope_id = scope_id
  63         self._signal_bus = signal_bus
  64         self._core_service = core_service
  65
  66     @property
  67     def route_family(self):
  68         return self.__class__.ROUTE_FAMILY
  69
  70     @property
  71     def core_service(self):
  72         return self._core_service
  73
  74     @property
  75     def scope_id(self):
  76         return self._scope_id
  77
  78     @abstractmethod
  79     def _create_dest(self, nlri):
  80         """Creates destination specific for this table.
  81         Returns destination that stores information of paths to *nlri*.
  82         """
  83         raise NotImplementedError()
  84
  85     def values(self):
  86         return iter(self._destinations.values())
  87
  88     def insert(self, path):
  89         self._validate_path(path)
  90         self._validate_nlri(path.nlri)
  91         if path.is_withdraw:
  92             updated_dest = self._insert_withdraw(path)
  93         else:
  94             updated_dest = self._insert_path(path)
  95         return updated_dest
  96
  97     def insert_sent_route(self, sent_route):
  98         self._validate_path(sent_route.path)
  99         dest = self._get_or_create_dest(sent_route.path.nlri)
 100         dest.add_sent_route(sent_route)
 101
 102     def _insert_path(self, path):
 103         """Add new path to destination identified by given prefix.
 104         """
 105         assert path.is_withdraw is False
 106         dest = self._get_or_create_dest(path.nlri)
 107         # Add given path to matching Dest.
 108         dest.add_new_path(path)
 109         # Return updated destination.
 110         return dest
 111
 112     def _insert_withdraw(self, path):
 113         """Appends given path to withdraw list of Destination for given prefix.
 114         """
 115         assert path.is_withdraw is True
 116         dest = self._get_or_create_dest(path.nlri)
 117         # Add given path to matching destination.
 118         dest.add_withdraw(path)
 119         # Return updated destination.
 120         return dest
 121
 122     def cleanup_paths_for_peer(self, peer):
 123         """Remove old paths from whose source is `peer`
 124
 125         Old paths have source version number that is less than current peer
 126         version number. Also removes sent paths to this peer.
 127         """
 128         LOG.debug('Cleaning paths from table %s for peer %s', self, peer)
 129         for dest in self.values():
 130             # Remove paths learned from this source
 131             paths_deleted = dest.remove_old_paths_from_source(peer)
 132             # Remove sent paths to this peer
 133             had_sent = dest.remove_sent_route(peer)
 134             if had_sent:
 135                 LOG.debug('Removed sent route %s for %s', dest.nlri, peer)
 136             # If any paths are removed we enqueue respective destination for
 137             # future processing.
 138             if paths_deleted:
 139                 self._signal_bus.dest_changed(dest)
 140
 141     def clean_uninteresting_paths(self, interested_rts):
 142         """Cleans table of any path that do not have any RT in common
 143          with `interested_rts`.
 144          Parameters:
 145              - `interested_rts`: (set) of RT that are of interest/that need to
 146              be preserved
 147         """
 148         LOG.debug('Cleaning table %s for given interested RTs %s',
 149                   self, interested_rts)
 150         uninteresting_dest_count = 0
 151         for dest in self.values():
 152             added_withdraw = \
 153                 dest.withdraw_uninteresting_paths(interested_rts)
 154             if added_withdraw:
 155                 self._signal_bus.dest_changed(dest)
 156                 uninteresting_dest_count += 1
 157         return uninteresting_dest_count
 158
 159     def delete_dest_by_nlri(self, nlri):
 160         """Deletes the destination identified by given prefix.
 161
 162         Returns the deleted destination if a match is found. If not match is
 163         found return None.
 164         """
 165         self._validate_nlri(nlri)
 166         dest = self._get_dest(nlri)
 167         if dest:
 168             self._destinations.pop(dest)
 169         return dest
 170
 171     def delete_dest(self, dest):
 172         del self._destinations[self._table_key(dest.nlri)]
 173
 174     def _validate_nlri(self, nlri):
 175         """Validated *nlri* is the type that this table stores/supports.
 176         """
 177         if not nlri or not (nlri.ROUTE_FAMILY == self.route_family):
 178             raise ValueError('Invalid Vpnv4 prefix given.')
 179
 180     def _validate_path(self, path):
 181         """Check if given path is an instance of *Path*.
 182
 183         Raises ValueError if given is not a instance of *Path*.
 184         """
 185         if not path or not (path.route_family == self.route_family):
 186             raise ValueError('Invalid path. Expected instance of'
 187                              ' Vpnv4 route family path, got %s.' % path)
 188
 189     def _get_or_create_dest(self, nlri):
 190         table_key = self._table_key(nlri)
 191         dest = self._destinations.get(table_key)
 192         # If destination for given prefix does not exist we create it.
 193         if dest is None:
 194             dest = self._create_dest(nlri)
 195             self._destinations[table_key] = dest
 196         return dest
 197
 198     def _get_dest(self, nlri):
 199         table_key = self._table_key(nlri)
 200         dest = self._destinations.get(table_key)
 201         return dest
 202
 203     def is_for_vrf(self):
 204         """Returns true if this table instance represents a VRF.
 205         """
 206         return self.scope_id is not None
 207
 208     def __str__(self):
 209         return 'Table(scope_id: %s, rf: %s)' % (self.scope_id,
 210                                                 self.route_family)
 211
 212     @abstractmethod
 213     def _table_key(self, nlri):
 214         """Return a key that will uniquely identify this NLRI inside
 215         this table.
 216         """
 217         raise NotImplementedError()
 218
 219
 220 class NonVrfPathProcessingMixin(object):
 221     """Mixin reacting to best-path selection algorithm on main table
 222     level. Intended to use with "Destination" subclasses.
 223     Applies to most of Destinations except for VrfDest
 224     because they are processed at VRF level, so different logic applies.
 225     """
 226
 227     def __init__(self):
 228         self._core_service = None  # not assigned yet
 229         self._known_path_list = []
 230
 231     def _best_path_lost(self):
 232         self._best_path = None
 233
 234         if self._sent_routes:
 235             # We have to send update-withdraw to all peers to whom old best
 236             # path was sent.
 237             for sent_route in self._sent_routes.values():
 238                 sent_path = sent_route.path
 239                 withdraw_clone = sent_path.clone(for_withdrawal=True)
 240                 outgoing_route = OutgoingRoute(withdraw_clone)
 241                 sent_route.sent_peer.enque_outgoing_msg(outgoing_route)
 242                 LOG.debug('Sending withdrawal to %s for %s',
 243                           sent_route.sent_peer, outgoing_route)
 244
 245             # Have to clear sent_route list for this destination as
 246             # best path is removed.
 247             self._sent_routes = {}
 248
 249     def _new_best_path(self, new_best_path):
 250         old_best_path = self._best_path
 251         self._best_path = new_best_path
 252         LOG.debug('New best path selected for destination %s', self)
 253
 254         # If old best path was withdrawn
 255         if (old_best_path and
 256                 old_best_path not in self._known_path_list and
 257                 self._sent_routes):
 258             # Have to clear sent_route list for this destination as
 259             # best path is removed.
 260             self._sent_routes = {}
 261
 262         # Communicate that we have new best path to all qualifying
 263         # bgp-peers.
 264         pm = self._core_service.peer_manager
 265         pm.comm_new_best_to_bgp_peers(new_best_path)
 266
 267         # withdraw old best path
 268         if old_best_path and self._sent_routes:
 269             for sent_route in self._sent_routes.values():
 270                 sent_path = sent_route.path
 271                 withdraw_clone = sent_path.clone(for_withdrawal=True)
 272                 outgoing_route = OutgoingRoute(withdraw_clone)
 273                 sent_route.sent_peer.enque_outgoing_msg(outgoing_route)
 274                 LOG.debug('Sending withdrawal to %s for %s',
 275                           sent_route.sent_peer, outgoing_route)
 276                 self._sent_routes = {}
 277
 278
 279 @six.add_metaclass(ABCMeta)
 280 class Destination(object):
 281     """State about a particular destination.
 282
 283     For example, an IP prefix. This is the data-structure that is hung of the
 284     a routing information base table *Table*.
 285     """
 286
 287     ROUTE_FAMILY = RF_IPv4_UC
 288
 289     def __init__(self, table, nlri):
 290         # Validate arguments.
 291         if table.route_family != self.__class__.ROUTE_FAMILY:
 292             raise ValueError('Table and destination route family '
 293                              'do not match.')
 294
 295         # Back-pointer to the table that contains this destination.
 296         self._table = table
 297
 298         self._core_service = table.core_service
 299
 300         self._nlri = nlri
 301
 302         # List of all known processed paths,
 303         self._known_path_list = []
 304
 305         # List of new un-processed paths.
 306         self._new_path_list = []
 307
 308         # Pointer to best-path. One from the the known paths.
 309         self._best_path = None
 310
 311         # Reason current best path was chosen as best path.
 312         self._best_path_reason = None
 313
 314         # List of withdrawn paths.
 315         self._withdraw_list = []
 316
 317         # List of SentRoute objects. This is the Adj-Rib-Out for this
 318         # destination. (key/value: peer/sent_route)
 319         self._sent_routes = {}
 320
 321         # This is an (optional) list of paths that were created as a
 322         # result of exporting this route to other tables.
 323         # self.exported_paths = None
 324
 325         # Automatically generated
 326         #
 327         # On work queue for BGP processor.
 328         # self.next_dest_to_process
 329         # self.prev_dest_to_process
 330
 331     @property
 332     def route_family(self):
 333         return self.__class__.ROUTE_FAMILY
 334
 335     @property
 336     def nlri(self):
 337         return self._nlri
 338
 339     @property
 340     def nlri_str(self):
 341         return self._nlri.formatted_nlri_str
 342
 343     @property
 344     def best_path(self):
 345         return self._best_path
 346
 347     @property
 348     def best_path_reason(self):
 349         return self._best_path_reason
 350
 351     @property
 352     def known_path_list(self):
 353         return self._known_path_list[:]
 354
 355     @property
 356     def sent_routes(self):
 357         return list(self._sent_routes.values())
 358
 359     def add_new_path(self, new_path):
 360         self._validate_path(new_path)
 361         self._new_path_list.append(new_path)
 362
 363     def add_withdraw(self, withdraw):
 364         self._validate_path(withdraw)
 365         self._withdraw_list.append(withdraw)
 366
 367     def add_sent_route(self, sent_route):
 368         self._sent_routes[sent_route.sent_peer] = sent_route
 369
 370     def remove_sent_route(self, peer):
 371         if self.was_sent_to(peer):
 372             del self._sent_routes[peer]
 373             return True
 374         return False
 375
 376     def was_sent_to(self, peer):
 377         if peer in self._sent_routes.keys():
 378             return True
 379         return False
 380
 381     def _process(self):
 382         """Calculate best path for this destination.
 383
 384         A destination is processed when known paths to this destination has
 385         changed. We might have new paths or withdrawals of last known paths.
 386         Removes withdrawals and adds new learned paths from known path list.
 387         Uses bgp best-path calculation algorithm on new list of known paths to
 388         choose new best-path. Communicates best-path to core service.
 389         """
 390         LOG.debug('Processing destination: %s', self)
 391         new_best_path, reason = self._process_paths()
 392         self._best_path_reason = reason
 393
 394         if self._best_path == new_best_path:
 395             return
 396
 397         if new_best_path is None:
 398             # we lost best path
 399             assert not self._known_path_list, repr(self._known_path_list)
 400             return self._best_path_lost()
 401         else:
 402             return self._new_best_path(new_best_path)
 403
 404     @abstractmethod
 405     def _best_path_lost(self):
 406         raise NotImplementedError()
 407
 408     @abstractmethod
 409     def _new_best_path(self, new_best_path):
 410         raise NotImplementedError()
 411
 412     @classmethod
 413     def _validate_path(cls, path):
 414         if not path or path.route_family != cls.ROUTE_FAMILY:
 415             raise ValueError(
 416                 'Invalid path. Expected %s path got %s' %
 417                 (cls.ROUTE_FAMILY, path)
 418             )
 419
 420     def process(self):
 421         self._process()
 422         if not self._known_path_list and not self._best_path:
 423             self._remove_dest_from_table()
 424
 425     def _remove_dest_from_table(self):
 426         self._table.delete_dest(self)
 427
 428     def remove_old_paths_from_source(self, source):
 429         """Removes known old paths from *source*.
 430
 431         Returns *True* if any of the known paths were found to be old and
 432         removed/deleted.
 433         """
 434         assert(source and hasattr(source, 'version_num'))
 435         removed_paths = []
 436         # Iterate over the paths in reverse order as we want to delete paths
 437         # whose source is this peer.
 438         source_ver_num = source.version_num
 439         for path_idx in range(len(self._known_path_list) - 1, -1, -1):
 440             path = self._known_path_list[path_idx]
 441             if (path.source == source and
 442                     path.source_version_num < source_ver_num):
 443                 # If this peer is source of any paths, remove those path.
 444                 del(self._known_path_list[path_idx])
 445                 removed_paths.append(path)
 446         return removed_paths
 447
 448     def withdraw_if_sent_to(self, peer):
 449         """Sends a withdraw for this destination to given `peer`.
 450
 451         Check the records if we indeed advertise this destination to given peer
 452         and if so, creates a withdraw for advertised route and sends it to the
 453         peer.
 454         Parameter:
 455             - `peer`: (Peer) peer to send withdraw to
 456         """
 457         from ryu.services.protocols.bgp.peer import Peer
 458         if not isinstance(peer, Peer):
 459             raise TypeError('Currently we only support sending withdrawal'
 460                             ' to instance of peer')
 461         sent_route = self._sent_routes.pop(peer, None)
 462         if not sent_route:
 463             return False
 464
 465         sent_path = sent_route.path
 466         withdraw_clone = sent_path.clone(for_withdrawal=True)
 467         outgoing_route = OutgoingRoute(withdraw_clone)
 468         sent_route.sent_peer.enque_outgoing_msg(outgoing_route)
 469         return True
 470
 471     def _process_paths(self):
 472         """Calculates best-path among known paths for this destination.
 473
 474         Returns:
 475          - Best path
 476
 477         Modifies destination's state related to stored paths. Removes withdrawn
 478         paths from known paths. Also, adds new paths to known paths.
 479         """
 480         # First remove the withdrawn paths.
 481         # Note: If we want to support multiple paths per destination we may
 482         # have to maintain sent-routes per path.
 483         self._remove_withdrawals()
 484
 485         # Have to select best-path from available paths and new paths.
 486         # If we do not have any paths, then we no longer have best path.
 487         if not self._known_path_list and len(self._new_path_list) == 1:
 488             # If we do not have any old but one new path
 489             # it becomes best path.
 490             self._known_path_list.append(self._new_path_list[0])
 491             del(self._new_path_list[0])
 492             return self._known_path_list[0], BPR_ONLY_PATH
 493
 494         # If we have a new version of old/known path we use it and delete old
 495         # one.
 496         self._remove_old_paths()
 497
 498         # Collect all new paths into known paths.
 499         self._known_path_list.extend(self._new_path_list)
 500
 501         # Clear new paths as we copied them.
 502         del(self._new_path_list[:])
 503
 504         # If we do not have any paths to this destination, then we do not have
 505         # new best path.
 506         if not self._known_path_list:
 507             return None, BPR_UNKNOWN
 508
 509         # Compute new best path
 510         current_best_path, reason = self._compute_best_known_path()
 511         return current_best_path, reason
 512
 513     def _remove_withdrawals(self):
 514         """Removes withdrawn paths.
 515
 516         Note:
 517         We may have disproportionate number of withdraws compared to know paths
 518         since not all paths get installed into the table due to bgp policy and
 519         we can receive withdraws for such paths and withdrawals may not be
 520         stopped by the same policies.
 521         """
 522
 523         LOG.debug('Removing %s withdrawals', len(self._withdraw_list))
 524
 525         # If we have no withdrawals, we have nothing to do.
 526         if not self._withdraw_list:
 527             return
 528
 529         # If we have some withdrawals and no know-paths, it means it is safe to
 530         # delete these withdraws.
 531         if not self._known_path_list:
 532             LOG.debug('Found %s withdrawals for path(s) that did not get'
 533                       ' installed.', len(self._withdraw_list))
 534             del(self._withdraw_list[:])
 535             return
 536
 537         # If we have some known paths and some withdrawals, we find matches and
 538         # delete them first.
 539         matches = set()
 540         w_matches = set()
 541         # Match all withdrawals from destination paths.
 542         for withdraw in self._withdraw_list:
 543             match = None
 544             for path in self._known_path_list:
 545                 # We have a match if the source are same.
 546                 if path.source == withdraw.source:
 547                     match = path
 548                     matches.add(path)
 549                     w_matches.add(withdraw)
 550                     # One withdraw can remove only one path.
 551                     break
 552             # We do no have any match for this withdraw.
 553             if not match:
 554                 LOG.debug('No matching path for withdraw found, may be path '
 555                           'was not installed into table: %s',
 556                           withdraw)
 557         # If we have partial match.
 558         if len(matches) != len(self._withdraw_list):
 559             LOG.debug('Did not find match for some withdrawals. Number of '
 560                       'matches(%s), number of withdrawals (%s)',
 561                       len(matches), len(self._withdraw_list))
 562
 563         # Clear matching paths and withdrawals.
 564         for match in matches:
 565             self._known_path_list.remove(match)
 566         for w_match in w_matches:
 567             self._withdraw_list.remove(w_match)
 568
 569     def _remove_old_paths(self):
 570         """Identifies which of known paths are old and removes them.
 571
 572         Known paths will no longer have paths whose new version is present in
 573         new paths.
 574         """
 575         new_paths = self._new_path_list
 576         known_paths = self._known_path_list
 577         for new_path in new_paths:
 578             old_paths = []
 579             for path in known_paths:
 580                 # Here we just check if source is same and not check if path
 581                 # version num. as new_paths are implicit withdrawal of old
 582                 # paths and when doing RouteRefresh (not EnhancedRouteRefresh)
 583                 # we get same paths again.
 584                 if new_path.source == path.source:
 585                     old_paths.append(path)
 586                     break
 587
 588             for old_path in old_paths:
 589                 known_paths.remove(old_path)
 590                 LOG.debug('Implicit withdrawal of old path, since we have'
 591                           ' learned new path from same source: %s', old_path)
 592
 593     def _compute_best_known_path(self):
 594         """Computes the best path among known paths.
 595
 596         Returns current best path among `known_paths`.
 597         """
 598         if not self._known_path_list:
 599             from ryu.services.protocols.bgp.processor import BgpProcessorError
 600             raise BgpProcessorError(desc='Need at-least one known path to'
 601                                     ' compute best path')
 602
 603         # We pick the first path as current best path. This helps in breaking
 604         # tie between two new paths learned in one cycle for which best-path
 605         # calculation steps lead to tie.
 606         current_best_path = self._known_path_list[0]
 607         best_path_reason = BPR_ONLY_PATH
 608         for next_path in self._known_path_list[1:]:
 609             from ryu.services.protocols.bgp.processor import compute_best_path
 610             # Compare next path with current best path.
 611             new_best_path, reason = \
 612                 compute_best_path(self._core_service.asn, current_best_path,
 613                                   next_path)
 614             best_path_reason = reason
 615             if new_best_path is not None:
 616                 current_best_path = new_best_path
 617
 618         return current_best_path, best_path_reason
 619
 620     def withdraw_uninteresting_paths(self, interested_rts):
 621         """Withdraws paths that are no longer interesting.
 622
 623         For all known paths that do not have any route target in common with
 624         given `interested_rts` we add a corresponding withdraw.
 625
 626         Returns True if we added any withdraws.
 627         """
 628         add_withdraws = False
 629         for path in self._known_path_list:
 630             if not path.has_rts_in(interested_rts):
 631                 self.withdraw_path(path)
 632                 add_withdraws = True
 633         return add_withdraws
 634
 635     def withdraw_path(self, path):
 636         if path not in self.known_path_list:
 637             raise ValueError("Path not known, no need to withdraw")
 638         withdraw = path.clone(for_withdrawal=True)
 639         self._withdraw_list.append(withdraw)
 640
 641     def to_dict(self):
 642         return {'table': str(self._table),
 643                 'nlri': str(self._nlri),
 644                 'paths': self._known_path_list[:],
 645                 'withdraws': self._get_num_withdraws()}
 646
 647     def __str__(self):
 648         return ('Destination(table: %s, nlri: %s, paths: %s, withdraws: %s,'
 649                 ' new paths: %s)' % (self._table, str(self._nlri),
 650                                      len(self._known_path_list),
 651                                      len(self._withdraw_list),
 652                                      len(self._new_path_list)))
 653
 654     def _get_num_valid_paths(self):
 655         return len(self._known_path_list)
 656
 657     def _get_num_withdraws(self):
 658         return len(self._withdraw_list)
 659
 660     def sent_routes_by_peer(self, peer):
 661         """get sent routes corresponding to specified peer.
 662
 663         Returns SentRoute list.
 664         """
 665         result = []
 666         for route in self._sent_routes.values():
 667             if route.sent_peer == peer:
 668                 result.append(route)
 669
 670         return result
 671
 672     def __lt__(self, other):
 673         return str(self) < str(other)
 674
 675     def __le__(self, other):
 676         return str(self) <= str(other)
 677
 678     def __eq__(self, other):
 679         return str(self) == str(other)
 680
 681     def __ne__(self, other):
 682         return str(self) != str(other)
 683
 684     def __gt__(self, other):
 685         return str(self) > str(other)
 686
 687     def __ge__(self, other):
 688         return str(self) >= str(other)
 689
 690
 691 @six.add_metaclass(ABCMeta)
 692 class Path(object):
 693     """Represents a way of reaching an IP destination.
 694
 695     Also contains other meta-data given to us by a specific source (such as a
 696     peer).
 697     """
 698     __slots__ = ('_source', '_path_attr_map', '_nlri', '_source_version_num',
 699                  '_exported_from', '_nexthop', 'next_path', 'prev_path',
 700                  '_is_withdraw', 'med_set_by_target_neighbor')
 701     ROUTE_FAMILY = RF_IPv4_UC
 702
 703     def __init__(self, source, nlri, src_ver_num, pattrs=None, nexthop=None,
 704                  is_withdraw=False, med_set_by_target_neighbor=False):
 705         """Initializes Ipv4 path.
 706
 707         If this path is not a withdraw, then path attribute and nexthop both
 708         should be provided.
 709         Parameters:
 710             - `source`: (Peer/str) source of this path.
 711             - `nlri`: (Vpnv4) Nlri instance for Vpnv4 route family.
 712             - `src_ver_num`: (int) version number of *source* when this path
 713             was learned.
 714             - `pattrs`: (OrderedDict) various path attributes for this path.
 715             - `nexthop`: (str) nexthop advertised for this path.
 716             - `is_withdraw`: (bool) True if this represents a withdrawal.
 717         """
 718         self.med_set_by_target_neighbor = med_set_by_target_neighbor
 719         if nlri.ROUTE_FAMILY != self.__class__.ROUTE_FAMILY:
 720             raise ValueError('NLRI and Path route families do not'
 721                              ' match (%s, %s).' %
 722                              (nlri.ROUTE_FAMILY, self.__class__.ROUTE_FAMILY))
 723
 724         # Currently paths injected directly into VRF has only one source
 725         # src_peer can be None to denote NC else has to be instance of Peer.
 726         # Paths can be exported from one VRF and then imported into another
 727         # VRF, in such cases it source is denoted as string VPN_TABLE.
 728         if not (source is None or
 729                 hasattr(source, 'version_num') or
 730                 source in (VRF_TABLE, VPN_TABLE)):
 731             raise ValueError('Invalid or Unsupported source for path: %s' %
 732                              source)
 733
 734         # If this path is not a withdraw path, than it should have path-
 735         # attributes and nexthop.
 736         if not is_withdraw and not (pattrs and nexthop):
 737             raise ValueError('Need to provide nexthop and patattrs '
 738                              'for path that is not a withdraw.')
 739
 740         # The entity (peer) that gave us this path.
 741         self._source = source
 742
 743         # Path attribute of this path.
 744         if pattrs:
 745             self._path_attr_map = copy(pattrs)
 746         else:
 747             self._path_attr_map = OrderedDict()
 748
 749         # NLRI that this path represents.
 750         self._nlri = nlri
 751
 752         # If given nlri is withdrawn.
 753         self._is_withdraw = is_withdraw
 754
 755         # @see Source.version_num
 756         self._source_version_num = src_ver_num
 757
 758         self._nexthop = nexthop
 759
 760         # Automatically generated.
 761         #
 762         # self.next_path
 763         # self.prev_path
 764
 765         # The Destination from which this path was exported, if any.
 766         self._exported_from = None
 767
 768     @property
 769     def source_version_num(self):
 770         return self._source_version_num
 771
 772     @property
 773     def source(self):
 774         return self._source
 775
 776     @property
 777     def route_family(self):
 778         return self.__class__.ROUTE_FAMILY
 779
 780     @property
 781     def nlri(self):
 782         return self._nlri
 783
 784     @property
 785     def nlri_str(self):
 786         return self._nlri.formatted_nlri_str
 787
 788     @property
 789     def is_withdraw(self):
 790         return self._is_withdraw
 791
 792     @property
 793     def pathattr_map(self):
 794         return copy(self._path_attr_map)
 795
 796     @property
 797     def nexthop(self):
 798         return self._nexthop
 799
 800     def get_pattr(self, pattr_type, default=None):
 801         """Returns path attribute of given type.
 802
 803         Returns None if we do not attribute of type *pattr_type*.
 804         """
 805         return self._path_attr_map.get(pattr_type, default)
 806
 807     def clone(self, for_withdrawal=False):
 808         pathattrs = None
 809         if not for_withdrawal:
 810             pathattrs = self.pathattr_map
 811         clone = self.__class__(
 812             self.source,
 813             self.nlri,
 814             self.source_version_num,
 815             pattrs=pathattrs,
 816             nexthop=self.nexthop,
 817             is_withdraw=for_withdrawal
 818         )
 819         return clone
 820
 821     def get_rts(self):
 822         extcomm_attr = self._path_attr_map.get(
 823             BGP_ATTR_TYPE_EXTENDED_COMMUNITIES)
 824         if extcomm_attr is None:
 825             rts = []
 826         else:
 827             rts = extcomm_attr.rt_list
 828         return rts
 829
 830     def has_rts_in(self, interested_rts):
 831         """Returns True if this `Path` has any `ExtCommunity` attribute
 832         route target common with `interested_rts`.
 833         """
 834         assert isinstance(interested_rts, set)
 835         curr_rts = self.get_rts()
 836         # Add default RT to path RTs so that we match interest for peers who
 837         # advertised default RT
 838         curr_rts.append(RouteTargetMembershipNLRI.DEFAULT_RT)
 839
 840         return not interested_rts.isdisjoint(curr_rts)
 841
 842     def is_local(self):
 843         return self._source is None
 844
 845     def has_nexthop(self):
 846         return self._nexthop and self._nexthop not in ('0.0.0.0', '::')
 847
 848     def __str__(self):
 849         return (
 850             'Path(source: %s, nlri: %s, source ver#: %s, '
 851             'path attrs.: %s, nexthop: %s, is_withdraw: %s)' %
 852             (
 853                 self._source, self._nlri, self._source_version_num,
 854                 self._path_attr_map, self._nexthop, self._is_withdraw
 855             )
 856         )
 857
 858     def __repr__(self):
 859         return ('Path(%s, %s, %s, %s, %s, %s)' % (
 860             self._source, self._nlri, self._source_version_num,
 861             self._path_attr_map, self._nexthop, self._is_withdraw))
 862
 863
 864 @six.add_metaclass(ABCMeta)
 865 class Filter(object):
 866     """Represents a general filter for in-bound and out-bound filter
 867
 868     ================ ==================================================
 869     Attribute        Description
 870     ================ ==================================================
 871     policy           Filter.POLICY_PERMIT or Filter.POLICY_DENY
 872     ================ ==================================================
 873     """
 874
 875     ROUTE_FAMILY = RF_IPv4_UC
 876
 877     POLICY_DENY = 0
 878     POLICY_PERMIT = 1
 879
 880     def __init__(self, policy=POLICY_DENY):
 881         self._policy = policy
 882
 883     @property
 884     def policy(self):
 885         return self._policy
 886
 887     @abstractmethod
 888     def evaluate(self, path):
 889         """ This method evaluates the path.
 890
 891         Returns this object's policy and the result of matching.
 892         If the specified prefix matches this object's prefix and
 893         ge and le condition,
 894         this method returns True as the matching result.
 895
 896         ``path`` specifies the path. prefix must be string.
 897         """
 898         raise NotImplementedError()
 899
 900     @abstractmethod
 901     def clone(self):
 902         """ This method clones Filter object.
 903
 904         Returns Filter object that has the same values with the original one.
 905         """
 906         raise NotImplementedError()
 907
 908
 909 @functools.total_ordering
 910 class PrefixFilter(Filter):
 911     """
 912     Used to specify a prefix for filter.
 913
 914     We can create PrefixFilter object as follows::
 915
 916         prefix_filter = PrefixFilter('10.5.111.0/24',
 917                                      policy=PrefixFilter.POLICY_PERMIT)
 918
 919     ================ ==================================================
 920     Attribute        Description
 921     ================ ==================================================
 922     prefix           A prefix used for this filter
 923     policy           One of the following values.
 924
 925                      | PrefixFilter.POLICY.PERMIT
 926                      | PrefixFilter.POLICY_DENY
 927     ge               Prefix length that will be applied to this filter.
 928                      ge means greater than or equal.
 929     le               Prefix length that will be applied to this filter.
 930                      le means less than or equal.
 931     ================ ==================================================
 932
 933     For example, when PrefixFilter object is created as follows::
 934
 935         p = PrefixFilter('10.5.111.0/24',
 936                          policy=PrefixFilter.POLICY_DENY,
 937                          ge=26, le=28)
 938
 939     Prefixes which match 10.5.111.0/24 and its length matches
 940     from 26 to 28 will be filtered.
 941     When this filter is used as an out-filter, it will stop sending
 942     the path to neighbor because of POLICY_DENY.
 943     When this filter is used as in-filter, it will stop importing the path
 944     to the global rib because of POLICY_DENY.
 945     If you specify POLICY_PERMIT, the path is sent to neighbor or imported to
 946     the global rib.
 947
 948     If you don't want to send prefixes 10.5.111.64/26 and 10.5.111.32/27
 949     and 10.5.111.16/28, and allow to send other 10.5.111.0's prefixes,
 950     you can do it by specifying as follows::
 951
 952         p = PrefixFilter('10.5.111.0/24',
 953                          policy=PrefixFilter.POLICY_DENY,
 954                          ge=26, le=28).
 955     """
 956
 957     def __init__(self, prefix, policy, ge=None, le=None):
 958         super(PrefixFilter, self).__init__(policy)
 959         self._prefix = prefix
 960         self._network = netaddr.IPNetwork(prefix)
 961         self._ge = ge
 962         self._le = le
 963
 964     def __lt__(self, other):
 965         return self._network < other._network
 966
 967     def __eq__(self, other):
 968         return self._network == other._network
 969
 970     def __repr__(self):
 971         policy = 'PERMIT' \
 972             if self._policy == self.POLICY_PERMIT else 'DENY'
 973
 974         return 'PrefixFilter(prefix=%s,policy=%s,ge=%s,le=%s)'\
 975                % (self._prefix, policy, self._ge, self._le)
 976
 977     @property
 978     def prefix(self):
 979         return self._prefix
 980
 981     @property
 982     def policy(self):
 983         return self._policy
 984
 985     @property
 986     def ge(self):
 987         return self._ge
 988
 989     @property
 990     def le(self):
 991         return self._le
 992
 993     def evaluate(self, path):
 994         """ This method evaluates the prefix.
 995
 996         Returns this object's policy and the result of matching.
 997         If the specified prefix matches this object's prefix and
 998         ge and le condition,
 999         this method returns True as the matching result.
1000
1001         ``path`` specifies the path that has prefix.
1002         """
1003         nlri = path.nlri
1004
1005         result = False
1006         length = nlri.length
1007         net = netaddr.IPNetwork(nlri.prefix)
1008
1009         if net in self._network:
1010             if self._ge is None and self._le is None:
1011                 result = True
1012
1013             elif self._ge is None and self._le:
1014                 if length <= self._le:
1015                     result = True
1016
1017             elif self._ge and self._le is None:
1018                 if self._ge <= length:
1019                     result = True
1020
1021             elif self._ge and self._le:
1022                 if self._ge <= length <= self._le:
1023                     result = True
1024
1025         return self.policy, result
1026
1027     def clone(self):
1028         """ This method clones PrefixFilter object.
1029
1030         Returns PrefixFilter object that has the same values with the
1031         original one.
1032         """
1033
1034         return self.__class__(self.prefix,
1035                               policy=self._policy,
1036                               ge=self._ge,
1037                               le=self._le)
1038
1039
1040 @functools.total_ordering
1041 class ASPathFilter(Filter):
1042     """
1043     Used to specify a prefix for AS_PATH attribute.
1044
1045     We can create ASPathFilter object as follows::
1046
1047         as_path_filter = ASPathFilter(65000,policy=ASPathFilter.TOP)
1048
1049     ================ ==================================================
1050     Attribute        Description
1051     ================ ==================================================
1052     as_number        A AS number used for this filter
1053     policy           One of the following values.
1054
1055                      | ASPathFilter.POLICY_TOP
1056                      | ASPathFilter.POLICY_END
1057                      | ASPathFilter.POLICY_INCLUDE
1058                      | ASPathFilter.POLICY_NOT_INCLUDE
1059     ================ ==================================================
1060
1061     Meaning of each policy is as follows:
1062
1063     ================== ==================================================
1064     Policy             Description
1065     ================== ==================================================
1066     POLICY_TOP         Filter checks if the specified AS number
1067                        is at the top of AS_PATH attribute.
1068     POLICY_END         Filter checks is the specified AS number
1069                        is at the last of AS_PATH attribute.
1070     POLICY_INCLUDE     Filter checks if specified AS number exists
1071                        in AS_PATH attribute.
1072     POLICY_NOT_INCLUDE Opposite to POLICY_INCLUDE.
1073     ================== ==================================================
1074     """
1075
1076     POLICY_TOP = 2
1077     POLICY_END = 3
1078     POLICY_INCLUDE = 4
1079     POLICY_NOT_INCLUDE = 5
1080
1081     def __init__(self, as_number, policy):
1082         super(ASPathFilter, self).__init__(policy)
1083         self._as_number = as_number
1084
1085     def __lt__(self, other):
1086         return self.as_number < other.as_number
1087
1088     def __eq__(self, other):
1089         return self.as_number == other.as_number
1090
1091     def __repr__(self):
1092         policy = 'TOP'
1093         if self._policy == self.POLICY_INCLUDE:
1094             policy = 'INCLUDE'
1095         elif self._policy == self.POLICY_NOT_INCLUDE:
1096             policy = 'NOT_INCLUDE'
1097         elif self._policy == self.POLICY_END:
1098             policy = 'END'
1099
1100         return 'ASPathFilter(as_number=%s,policy=%s)'\
1101                % (self._as_number, policy)
1102
1103     @property
1104     def as_number(self):
1105         return self._as_number
1106
1107     @property
1108     def policy(self):
1109         return self._policy
1110
1111     def evaluate(self, path):
1112         """ This method evaluates as_path list.
1113
1114         Returns this object's policy and the result of matching.
1115         If the specified AS number matches this object's AS number
1116         according to the policy,
1117         this method returns True as the matching result.
1118
1119         ``path`` specifies the path.
1120         """
1121
1122         path_aspath = path.pathattr_map.get(BGP_ATTR_TYPE_AS_PATH)
1123         path_seg_list = path_aspath.path_seg_list
1124         if path_seg_list:
1125             path_seg = path_seg_list[0]
1126         else:
1127             path_seg = []
1128         result = False
1129
1130         LOG.debug("path_seg : %s", path_seg)
1131         if self.policy == ASPathFilter.POLICY_TOP:
1132
1133             if len(path_seg) > 0 and path_seg[0] == self._as_number:
1134                 result = True
1135
1136         elif self.policy == ASPathFilter.POLICY_INCLUDE:
1137             for aspath in path_seg:
1138                 LOG.debug("POLICY_INCLUDE as_number : %s", aspath)
1139                 if aspath == self._as_number:
1140                     result = True
1141                     break
1142
1143         elif self.policy == ASPathFilter.POLICY_END:
1144
1145             if len(path_seg) > 0 and path_seg[-1] == self._as_number:
1146                 result = True
1147
1148         elif self.policy == ASPathFilter.POLICY_NOT_INCLUDE:
1149
1150             if self._as_number not in path_seg:
1151                 result = True
1152
1153         return self.policy, result
1154
1155     def clone(self):
1156         """ This method clones ASPathFilter object.
1157
1158         Returns ASPathFilter object that has the same values with the
1159         original one.
1160         """
1161
1162         return self.__class__(self._as_number,
1163                               policy=self._policy)
1164
1165
1166 class AttributeMap(object):
1167     """
1168     This class is used to specify an attribute to add if the path matches
1169     filters.
1170     We can create AttributeMap object as follows::
1171
1172         pref_filter = PrefixFilter('192.168.103.0/30',
1173                                    PrefixFilter.POLICY_PERMIT)
1174
1175         attribute_map = AttributeMap([pref_filter],
1176                                      AttributeMap.ATTR_LOCAL_PREF, 250)
1177
1178         speaker.attribute_map_set('192.168.50.102', [attribute_map])
1179
1180     AttributeMap.ATTR_LOCAL_PREF means that 250 is set as a
1181     local preference value if nlri in the path matches pref_filter.
1182
1183     ASPathFilter is also available as a filter. ASPathFilter checks if AS_PATH
1184     attribute in the path matches AS number in the filter.
1185
1186     =================== ==================================================
1187     Attribute           Description
1188     =================== ==================================================
1189     filters             A list of filter.
1190                         Each object should be a Filter class or its sub-class
1191     attr_type           A type of attribute to map on filters. Currently
1192                         AttributeMap.ATTR_LOCAL_PREF is available.
1193     attr_value          A attribute value
1194     =================== ==================================================
1195     """
1196
1197     ATTR_LOCAL_PREF = '_local_pref'
1198
1199     def __init__(self, filters, attr_type, attr_value):
1200
1201         assert all(isinstance(f, Filter) for f in filters),\
1202             'all the items in filters must be an instance of Filter sub-class'
1203         self.filters = filters
1204         self.attr_type = attr_type
1205         self.attr_value = attr_value
1206
1207     def evaluate(self, path):
1208         """ This method evaluates attributes of the path.
1209
1210         Returns the cause and result of matching.
1211         Both cause and result are returned from filters
1212         that this object contains.
1213
1214         ``path`` specifies the path.
1215         """
1216         result = False
1217         cause = None
1218
1219         for f in self.filters:
1220
1221             cause, result = f.evaluate(path)
1222             if not result:
1223                 break
1224
1225         return cause, result
1226
1227     def get_attribute(self):
1228         func = getattr(self, 'get' + self.attr_type)
1229         return func()
1230
1231     def get_local_pref(self):
1232         local_pref_attr = BGPPathAttributeLocalPref(value=self.attr_value)
1233         return local_pref_attr
1234
1235     def clone(self):
1236         """ This method clones AttributeMap object.
1237
1238         Returns AttributeMap object that has the same values with the
1239         original one.
1240         """
1241
1242         cloned_filters = [f.clone() for f in self.filters]
1243         return self.__class__(cloned_filters, self.attr_type, self.attr_value)
1244
1245     def __repr__(self):
1246
1247         attr_type = 'LOCAL_PREF'\
1248             if self.attr_type == self.ATTR_LOCAL_PREF else None
1249
1250         filter_string = ','.join(repr(f) for f in self.filters)
1251         return ('AttributeMap(filters=[%s],'
1252                 'attribute_type=%s,'
1253                 'attribute_value=%s)' % (filter_string,
1254                                          attr_type,
1255                                          self.attr_value))