bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.protocol.bgp.mode.impl.add;
   9
  10 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID_VALUE;
  11
  12 import com.google.common.collect.Lists;
  13 import com.google.common.primitives.UnsignedInteger;
  14 import java.util.ArrayList;
  15 import java.util.List;
  16 import java.util.Optional;
  17 import javax.annotation.concurrent.NotThreadSafe;
  18 import org.opendaylight.controller.md.sal.binding.api.WriteTransaction;
  19 import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
  20 import org.opendaylight.protocol.bgp.mode.impl.BGPRouteEntryExportParametersImpl;
  21 import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry;
  22 import org.opendaylight.protocol.bgp.rib.spi.BGPPeerTracker;
  23 import org.opendaylight.protocol.bgp.rib.spi.Peer;
  24 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
  25 import org.opendaylight.protocol.bgp.rib.spi.RouterIds;
  26 import org.opendaylight.protocol.bgp.rib.spi.entry.RouteEntryDependenciesContainer;
  27 import org.opendaylight.protocol.bgp.rib.spi.entry.RouteEntryInfo;
  28 import org.opendaylight.protocol.bgp.rib.spi.policy.BGPRouteEntryExportParameters;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev180329.path.attributes.Attributes;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.PeerId;
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
  33 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.TablesKey;
  34 import org.opendaylight.yangtools.yang.binding.Identifier;
  35 import org.opendaylight.yangtools.yang.binding.InstanceIdentifier;
  36 import org.opendaylight.yangtools.yang.binding.KeyedInstanceIdentifier;
  37 import org.slf4j.Logger;
  38 import org.slf4j.LoggerFactory;
  39
  40 /**
  41  * A single route entry inside a route table. Maintains the attributes of
  42  * from all contributing peers. The information is stored in arrays with a
  43  * shared map of offsets for peers to allow lookups. This is needed to
  44  * maintain low memory overhead in face of large number of routes and peers,
  45  * where individual object overhead becomes the dominating factor.
  46  */
  47 @NotThreadSafe
  48 public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry<AddPathBestPath> {
  49
  50     private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
  51     private static final Long[] EMPTY_PATHS_ID = new Long[0];
  52
  53     private List<AddPathBestPath> bestPath;
  54     private List<AddPathBestPath> bestPathRemoved;
  55     protected OffsetMap offsets = OffsetMap.EMPTY;
  56     protected Route[] values = EMPTY_VALUES;
  57     protected Long[] pathsId =  EMPTY_PATHS_ID;
  58     private long pathIdCounter = 0L;
  59     private boolean oldNonAddPathBestPathTheSame;
  60     private List<AddPathBestPath> newBestPathToBeAdvertised;
  61     private List<RemovedPath> removedPaths;
  62
  63     public AddPathAbstractRouteEntry(final BGPPeerTracker peerTracker) {
  64         super(peerTracker);
  65     }
  66
  67     private static final class RemovedPath {
  68         private final RouteKey key;
  69         private final long pathId;
  70
  71         RemovedPath(final RouteKey key, final long pathId) {
  72             this.key = key;
  73             this.pathId = pathId;
  74         }
  75
  76         long getPathId() {
  77             return this.pathId;
  78         }
  79
  80         UnsignedInteger getRouteId() {
  81             return this.key.getRouteId();
  82         }
  83     }
  84
  85     @Override
  86     public final Route createRoute(final RIBSupport ribSup, final String routeKey, final long pathId,
  87             final AddPathBestPath path) {
  88         final OffsetMap map = getOffsets();
  89         final Route route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
  90         return ribSup.createRoute(route, routeKey, pathId, path.getAttributes());
  91     }
  92
  93     @Override
  94     public final int addRoute(final UnsignedInteger routerId, final long remotePathId, final Route route) {
  95         final RouteKey key = new RouteKey(routerId, remotePathId);
  96         int offset = this.offsets.offsetOf(key);
  97         if (offset < 0) {
  98             final OffsetMap newOffsets = this.offsets.with(key);
  99             offset = newOffsets.offsetOf(key);
 100             final Route[] newRoute = newOffsets.expand(this.offsets, this.values, offset);
 101             final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
 102             this.values = newRoute;
 103             this.offsets = newOffsets;
 104             this.pathsId = newPathsId;
 105             this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
 106         }
 107         this.offsets.setValue(this.values, offset, route);
 108         LOG.trace("Added route {} from {}", route, key.getRouteId());
 109         return offset;
 110     }
 111
 112     @Override
 113     public final boolean removeRoute(final UnsignedInteger routerId, final long remotePathId) {
 114         final RouteKey key = new RouteKey(routerId, remotePathId);
 115         final int offset = getOffsets().offsetOf(key);
 116         final long pathId = this.offsets.getValue(this.pathsId, offset);
 117         this.values = this.offsets.removeValue(this.values, offset, EMPTY_VALUES);
 118         this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
 119         this.offsets = this.offsets.without(key);
 120         if (this.removedPaths == null) {
 121             this.removedPaths = new ArrayList<>();
 122         }
 123         this.removedPaths.add(new RemovedPath(key, pathId));
 124         return isEmpty();
 125     }
 126
 127     @Override
 128     public void updateBestPaths(
 129             final RouteEntryDependenciesContainer entryDependencies,
 130             final String routeKey,
 131             final WriteTransaction tx) {
 132
 133         final RIBSupport ribSupport = entryDependencies.getRibSupport();
 134         final KeyedInstanceIdentifier<Tables, TablesKey> locRibTarget = entryDependencies.getLocRibTableTarget();
 135         if (this.bestPathRemoved != null) {
 136             this.bestPathRemoved.forEach(path -> {
 137                 final Identifier newRouteKey = ribSupport.createRouteListKey(path.getPathId(), routeKey);
 138                 final InstanceIdentifier routeTarget = ribSupport.createRouteIdentifier(locRibTarget, newRouteKey);
 139                 LOG.debug("Delete route from LocRib {}", routeTarget);
 140                 tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
 141             });
 142             this.bestPathRemoved = null;
 143         }
 144         if (this.removedPaths != null) {
 145             this.removedPaths.forEach(removedPath -> {
 146                 final Identifier routeKeyAddPath
 147                         = ribSupport.createRouteListKey(removedPath.getPathId(), routeKey);
 148                 final Identifier routeKeyNonAddPath = ribSupport.createRouteListKey(NON_PATH_ID_VALUE, routeKey);
 149                 fillAdjRibsOut(true, null, null, null,
 150                         routeKeyNonAddPath, routeKeyAddPath,
 151                         RouterIds.createPeerId(removedPath.getRouteId()),
 152                         entryDependencies.getLocalTablesKey(), entryDependencies, tx);
 153             });
 154             this.removedPaths = null;
 155         }
 156
 157         if (this.newBestPathToBeAdvertised != null) {
 158             this.newBestPathToBeAdvertised.forEach(path -> addPathToDataStore(entryDependencies, path,
 159                     isFirstBestPath(this.bestPath.indexOf(path)), routeKey, tx));
 160             this.newBestPathToBeAdvertised = null;
 161         }
 162     }
 163
 164     @Override
 165     public void initializeBestPaths(final RouteEntryDependenciesContainer routeEntryDep,
 166             final RouteEntryInfo entryInfo, final WriteTransaction tx) {
 167         if (this.bestPath != null) {
 168             final Peer toPeer = entryInfo.getToPeer();
 169             final TablesKey localTk = routeEntryDep.getLocalTablesKey();
 170             final boolean destPeerSupAddPath = toPeer.supportsAddPathSupported(localTk);
 171             for (final AddPathBestPath path : this.bestPath) {
 172                 if (!filterRoutes(path.getPeerId(), toPeer, localTk)) {
 173                     continue;
 174                 }
 175                 final String routeKey = entryInfo.getRouteKey();
 176                 final RIBSupport ribSupport = routeEntryDep.getRibSupport();
 177                 final BGPRouteEntryExportParameters baseExp = new BGPRouteEntryExportParametersImpl(
 178                         this.peerTracker.getPeer(path.getPeerId()), toPeer);
 179                 final Optional<Attributes> effAttrib = routeEntryDep.getRoutingPolicies()
 180                         .applyExportPolicies(baseExp, path.getAttributes());
 181                 if (effAttrib.isPresent()) {
 182                     Identifier routeIdentifier = ribSupport.createRouteListKey(destPeerSupAddPath
 183                             ? path.getPathId() : NON_PATH_ID_VALUE, routeKey);
 184                     final Route route = createRoute(ribSupport, routeKey, destPeerSupAddPath
 185                             ? path.getPathId() : NON_PATH_ID_VALUE, path);
 186                     InstanceIdentifier ribOutIId
 187                             = ribSupport.createRouteIdentifier(toPeer.getRibOutIId(localTk), routeIdentifier);
 188
 189                     LOG.debug("Write route {} to peer AdjRibsOut {}", route, toPeer.getPeerId());
 190                     tx.put(LogicalDatastoreType.OPERATIONAL, ribOutIId, route);
 191                     tx.put(LogicalDatastoreType.OPERATIONAL, ribOutIId.child(Attributes.class), effAttrib.get());
 192                 }
 193             }
 194         }
 195     }
 196
 197     private void addPathToDataStore(
 198             final RouteEntryDependenciesContainer entryDep,
 199             final AddPathBestPath path,
 200             final boolean isFirstBestPath,
 201             final String routeKey,
 202             final WriteTransaction tx) {
 203         final RIBSupport ribSup = entryDep.getRibSupport();
 204         final Identifier routeIdAddPath = ribSup.createRouteListKey(path.getPathId(), routeKey);
 205         final Identifier routeIdAddNonPath = ribSup.createRouteListKey(NON_PATH_ID_VALUE, routeKey);
 206         final Route routeAddPath = createRoute(ribSup, routeKey, path.getPathId(), path);
 207         final Route routeNonAddPath = createRoute(ribSup, routeKey, NON_PATH_ID_VALUE, path);
 208
 209         final KeyedInstanceIdentifier<Tables, TablesKey> locRibTarget = entryDep.getLocRibTableTarget();
 210         final InstanceIdentifier routeTarget = ribSup.createRouteIdentifier(locRibTarget, routeIdAddPath);
 211         LOG.debug("Write route to LocRib {}", routeAddPath);
 212         tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget, routeAddPath);
 213
 214         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), routeNonAddPath, routeAddPath, routeIdAddNonPath,
 215             routeIdAddPath, path.getPeerId(), entryDep.getLocalTablesKey(), entryDep, tx);
 216     }
 217
 218     @SuppressWarnings("unchecked")
 219     private void fillAdjRibsOut(
 220             final boolean isFirstBestPath,
 221             final Attributes attributes,
 222             final Route routeNonAddPath,
 223             final Route routeAddPath,
 224             final Identifier routeKeyAddNonPath,
 225             final Identifier routeKeyAddPath,
 226             final PeerId fromPeerId,
 227             final TablesKey localTK,
 228             final RouteEntryDependenciesContainer routeEntryDep,
 229             final WriteTransaction tx) {
 230         /*
 231          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 232          * expose from which client a particular route was learned from in the local RIB, and have
 233          * the listener perform filtering.
 234          *
 235          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 236          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 237          * multiple times.
 238          */
 239         final RIBSupport ribSupport = routeEntryDep.getRibSupport();
 240         for (final Peer toPeer : this.peerTracker.getPeers()) {
 241             if (!filterRoutes(fromPeerId, toPeer, localTK)) {
 242                 continue;
 243             }
 244             final boolean destPeerSupAddPath = toPeer.supportsAddPathSupported(localTK);
 245
 246             if (toPeer.getPeerId().getValue().equals("bgp://127.0.0.5")) {
 247                 LOG.debug("Write route {} to peer AdjRibsOut {}", toPeer.getPeerId());
 248             }
 249             if (peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 250
 251                 Optional<Attributes> effAttrib = Optional.empty();
 252                 final Peer fromPeer = this.peerTracker.getPeer(fromPeerId);
 253
 254                 if (fromPeer != null && attributes != null) {
 255                     final BGPRouteEntryExportParameters baseExp
 256                             = new BGPRouteEntryExportParametersImpl(fromPeer, toPeer);
 257                     effAttrib = routeEntryDep.getRoutingPolicies()
 258                             .applyExportPolicies(baseExp, attributes);
 259                 }
 260                 Route newRoute = null;
 261                 InstanceIdentifier ribOutRoute = null;
 262                 if (destPeerSupAddPath) {
 263                     newRoute = routeAddPath;
 264                     ribOutRoute
 265                             = ribSupport.createRouteIdentifier(toPeer.getRibOutIId(localTK), routeKeyAddPath);
 266                 } else if (!this.oldNonAddPathBestPathTheSame) {
 267                     ribOutRoute
 268                             = ribSupport.createRouteIdentifier(toPeer.getRibOutIId(localTK), routeKeyAddNonPath);
 269                     newRoute = routeNonAddPath;
 270                 }
 271
 272                 if (effAttrib.isPresent() && newRoute != null) {
 273                     LOG.debug("Write route {} to peer AdjRibsOut {}", newRoute, toPeer.getPeerId());
 274                     tx.put(LogicalDatastoreType.OPERATIONAL, ribOutRoute, newRoute);
 275                     tx.put(LogicalDatastoreType.OPERATIONAL, ribOutRoute.child(Attributes.class), effAttrib.get());
 276                 } else if (ribOutRoute != null) {
 277                     LOG.trace("Removing {} from transaction for peer {}", ribOutRoute, toPeer.getPeerId());
 278                     tx.delete(LogicalDatastoreType.OPERATIONAL, ribOutRoute);
 279                 }
 280             }
 281         }
 282     }
 283
 284
 285     protected final OffsetMap getOffsets() {
 286         return this.offsets;
 287     }
 288
 289     public final boolean isEmpty() {
 290         return this.offsets.isEmpty();
 291     }
 292
 293     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 294         final int offset = this.offsets.offsetOf(key);
 295         final Route route = this.offsets.getValue(this.values, offset);
 296         final long pathId = this.offsets.getValue(this.pathsId, offset);
 297         LOG.trace("Processing router key {} route {}", key, route);
 298         selector.processPath(route.getAttributes(), key, offset, pathId);
 299     }
 300
 301     /**
 302      * Process best path selection.
 303      *
 304      * @param localAs The local autonomous system number
 305      * @param keyList List of RouteKey
 306      * @return the best path inside offset map passed
 307      */
 308     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 309         /*
 310          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 311          */
 312         final AddPathSelector selector = new AddPathSelector(localAs);
 313         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 314         LOG.trace("Best path selected {}", this.bestPath);
 315         return selector.result();
 316     }
 317
 318     private static boolean isFirstBestPath(final int bestPathPosition) {
 319         return bestPathPosition == 0;
 320     }
 321
 322     private static boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath,
 323             final boolean isFirstBestPath) {
 324         return !(!peerSupportsAddPath && !isFirstBestPath);
 325     }
 326
 327     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 328         this.oldNonAddPathBestPathTheSame = isNonAddPathBestPathTheSame(newBestPathList);
 329         filterRemovedPaths(newBestPathList);
 330         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
 331                 || newBestPathList != null
 332                 && !newBestPathList.equals(this.bestPath)) {
 333             this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 334             if (this.bestPath != null) {
 335                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 336             }
 337             this.bestPath = newBestPathList;
 338             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 339             return true;
 340         }
 341         return false;
 342     }
 343
 344     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 345         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 346                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 347     }
 348
 349     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 350         return pathList == null || pathList.isEmpty();
 351     }
 352
 353     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 354         if (this.bestPath == null) {
 355             return;
 356         }
 357         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 358         this.bestPath.forEach(oldBest -> {
 359             final Optional<AddPathBestPath> present = newBestPathList.stream()
 360                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 361                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 362             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 363         });
 364     }
 365 }