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 Attributes[] values = EMPTY_ATTRIBUTES;
  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     protected int addRoute(final RouteKey key, final Attributes attributes) {
  86         int offset = this.offsets.offsetOf(key);
  87         if (offset < 0) {
  88             final OffsetMap newOffsets = this.offsets.with(key);
  89             offset = newOffsets.offsetOf(key);
  90             final Attributes[] newAttributes = newOffsets.expand(this.offsets, this.values, offset);
  91             final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
  92             this.values = newAttributes;
  93             this.offsets = newOffsets;
  94             this.pathsId = newPathsId;
  95             this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
  96         }
  97         this.offsets.setValue(this.values, offset, attributes);
  98         LOG.trace("Added route from {} attributes {}", key.getRouteId(), attributes);
  99         return offset;
 100     }
 101
 102     /**
 103      * Remove route.
 104      *
 105      * @param key RouteKey of removed route
 106      * @param offset Offset of removed route
 107      * @return true if it was the last route
 108      */
 109     protected final boolean removeRoute(final RouteKey key, final int offset) {
 110         final long pathId = this.offsets.getValue(this.pathsId, offset);
 111         this.values = this.offsets.removeValue(this.values, offset, EMPTY_ATTRIBUTES);
 112         this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
 113         this.offsets = this.offsets.without(key);
 114         if (this.removedPaths == null) {
 115             this.removedPaths = new ArrayList<>();
 116         }
 117         this.removedPaths.add(new RemovedPath(key, pathId));
 118         return isEmpty();
 119     }
 120
 121     @Override
 122     public void updateBestPaths(
 123             final RouteEntryDependenciesContainer entryDependencies,
 124             final String routeKey,
 125             final WriteTransaction tx) {
 126
 127         final RIBSupport ribSupport = entryDependencies.getRibSupport();
 128         final KeyedInstanceIdentifier<Tables, TablesKey> locRibTarget = entryDependencies.getLocRibTableTarget();
 129         if (this.bestPathRemoved != null) {
 130             this.bestPathRemoved.forEach(path -> {
 131                 final Identifier newRouteKey = ribSupport.createRouteListKey(path.getPathId(), routeKey);
 132                 final InstanceIdentifier routeTarget = ribSupport.createRouteIdentifier(locRibTarget, newRouteKey);
 133                 LOG.debug("Delete route from LocRib {}", routeTarget);
 134                 tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
 135             });
 136             this.bestPathRemoved = null;
 137         }
 138         if (this.removedPaths != null) {
 139             this.removedPaths.forEach(removedPath -> {
 140                 final Identifier routeKeyAddPath
 141                         = ribSupport.createRouteListKey(removedPath.getPathId(), routeKey);
 142                 final Identifier routeKeyNonAddPath = ribSupport.createRouteListKey(NON_PATH_ID_VALUE, routeKey);
 143                 fillAdjRibsOut(true, null, null, null,
 144                         routeKeyNonAddPath, routeKeyAddPath,
 145                         RouterIds.createPeerId(removedPath.getRouteId()),
 146                         entryDependencies.getLocalTablesKey(), entryDependencies, tx);
 147             });
 148             this.removedPaths = null;
 149         }
 150
 151         if (this.newBestPathToBeAdvertised != null) {
 152             this.newBestPathToBeAdvertised.forEach(path -> addPathToDataStore(entryDependencies, path,
 153                     isFirstBestPath(this.bestPath.indexOf(path)), routeKey, tx));
 154             this.newBestPathToBeAdvertised = null;
 155         }
 156     }
 157
 158     @Override
 159     public void initializeBestPaths(final RouteEntryDependenciesContainer entryDependencies,
 160             final RouteEntryInfo entryInfo, final WriteTransaction tx) {
 161         if (this.bestPath != null) {
 162             final Peer toPeer = entryInfo.getToPeer();
 163             final TablesKey localTk = entryDependencies.getLocalTablesKey();
 164             final boolean destPeerSupAddPath = toPeer.supportsAddPathSupported(localTk);
 165             for (final AddPathBestPath path : this.bestPath) {
 166                 if (!filterRoutes(path.getPeerId(), toPeer, localTk)) {
 167                     continue;
 168                 }
 169                 writeRoutePath(entryInfo, destPeerSupAddPath, path, localTk, entryDependencies, tx);
 170             }
 171         }
 172     }
 173
 174     @SuppressWarnings("unchecked")
 175     private void writeRoutePath(final RouteEntryInfo entryInfo,
 176             final boolean destPeerSupAddPath, final AddPathBestPath path,
 177             final TablesKey localTK, final RouteEntryDependenciesContainer routeEntryDep, final WriteTransaction tx) {
 178         final String routeKey = entryInfo.getRouteKey();
 179         final RIBSupport ribSupport = routeEntryDep.getRibSupport();
 180         final BGPRouteEntryExportParameters baseExp = new BGPRouteEntryExportParametersImpl(
 181                 this.peerTracker.getPeer(path.getPeerId()), entryInfo.getToPeer());
 182         final Optional<Attributes> effAttrib = routeEntryDep.getRoutingPolicies()
 183                 .applyExportPolicies(baseExp, path.getAttributes());
 184
 185         Identifier routeIdentifier = ribSupport.createRouteListKey(destPeerSupAddPath
 186                 ? path.getPathId() : NON_PATH_ID_VALUE, routeKey);
 187         final Peer toPeer = entryInfo.getToPeer();
 188         final Route route = createRoute(ribSupport, routeKey, destPeerSupAddPath
 189                 ? path.getPathId() : NON_PATH_ID_VALUE, path);
 190         InstanceIdentifier ribOutIId = ribSupport.createRouteIdentifier(toPeer.getRibOutIId(localTK), routeIdentifier);
 191         if (effAttrib.isPresent() && route != null) {
 192             LOG.debug("Write route {} to peer AdjRibsOut {}", route, toPeer.getPeerId());
 193             tx.put(LogicalDatastoreType.OPERATIONAL, ribOutIId, route);
 194             tx.put(LogicalDatastoreType.OPERATIONAL, ribOutIId.child(Attributes.class), effAttrib.get());
 195         }
 196     }
 197
 198     private void addPathToDataStore(
 199             final RouteEntryDependenciesContainer entryDep,
 200             final AddPathBestPath path,
 201             final boolean isFirstBestPath,
 202             final String routeKey,
 203             final WriteTransaction tx) {
 204         final RIBSupport ribSup = entryDep.getRibSupport();
 205         final Identifier routeIdAddPath = ribSup.createRouteListKey(path.getPathId(), routeKey);
 206         final Identifier routeIdAddNonPath = ribSup.createRouteListKey(NON_PATH_ID_VALUE, routeKey);
 207         final Route routeAddPath = createRoute(ribSup, routeKey, path.getPathId(), path);
 208         final Route routeNonAddPath = createRoute(ribSup, routeKey, NON_PATH_ID_VALUE, path);
 209
 210         final KeyedInstanceIdentifier<Tables, TablesKey> locRibTarget = entryDep.getLocRibTableTarget();
 211         final InstanceIdentifier routeTarget = ribSup.createRouteIdentifier(locRibTarget, routeIdAddPath);
 212         LOG.debug("Write route to LocRib {}", routeAddPath);
 213         tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget, routeAddPath);
 214
 215         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), routeNonAddPath, routeAddPath, routeIdAddNonPath,
 216             routeIdAddPath, path.getPeerId(), entryDep.getLocalTablesKey(), entryDep, tx);
 217     }
 218
 219     @SuppressWarnings("unchecked")
 220     private void fillAdjRibsOut(
 221             final boolean isFirstBestPath,
 222             final Attributes attributes,
 223             final Route routeNonAddPath,
 224             final Route routeAddPath,
 225             final Identifier routeKeyAddNonPath,
 226             final Identifier routeKeyAddPath,
 227             final PeerId fromPeerId,
 228             final TablesKey localTK,
 229             final RouteEntryDependenciesContainer routeEntryDep,
 230             final WriteTransaction tx) {
 231         /*
 232          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 233          * expose from which client a particular route was learned from in the local RIB, and have
 234          * the listener perform filtering.
 235          *
 236          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 237          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 238          * multiple times.
 239          */
 240         final RIBSupport ribSupport = routeEntryDep.getRibSupport();
 241         for (final Peer toPeer : this.peerTracker.getPeers()) {
 242             if (!filterRoutes(fromPeerId, toPeer, localTK)) {
 243                 continue;
 244             }
 245             final boolean destPeerSupAddPath = toPeer.supportsAddPathSupported(localTK);
 246
 247             if (toPeer.getPeerId().getValue().equals("bgp://127.0.0.5")) {
 248                 LOG.debug("Write route {} to peer AdjRibsOut {}", toPeer.getPeerId());
 249             }
 250             if (peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 251
 252                 Optional<Attributes> effAttrib = Optional.empty();
 253                 final Peer fromPeer = this.peerTracker.getPeer(fromPeerId);
 254
 255                 if (fromPeer != null && attributes != null) {
 256                     final BGPRouteEntryExportParameters baseExp
 257                             = new BGPRouteEntryExportParametersImpl(fromPeer, toPeer);
 258                     effAttrib = routeEntryDep.getRoutingPolicies()
 259                             .applyExportPolicies(baseExp, attributes);
 260                 }
 261                 Route newRoute = null;
 262                 InstanceIdentifier ribOutRoute = null;
 263                 if (destPeerSupAddPath) {
 264                     newRoute = routeAddPath;
 265                     ribOutRoute
 266                             = ribSupport.createRouteIdentifier(toPeer.getRibOutIId(localTK), routeKeyAddPath);
 267                 } else if (!this.oldNonAddPathBestPathTheSame) {
 268                     ribOutRoute
 269                             = ribSupport.createRouteIdentifier(toPeer.getRibOutIId(localTK), routeKeyAddNonPath);
 270                     newRoute = routeNonAddPath;
 271                 }
 272
 273                 if (effAttrib.isPresent() && newRoute != null) {
 274                     LOG.debug("Write route {} to peer AdjRibsOut {}", newRoute, toPeer.getPeerId());
 275                     tx.put(LogicalDatastoreType.OPERATIONAL, ribOutRoute, newRoute);
 276                     tx.put(LogicalDatastoreType.OPERATIONAL, ribOutRoute.child(Attributes.class), effAttrib.get());
 277                 } else if (ribOutRoute != null) {
 278                     LOG.trace("Removing {} from transaction for peer {}", ribOutRoute, toPeer.getPeerId());
 279                     tx.delete(LogicalDatastoreType.OPERATIONAL, ribOutRoute);
 280                 }
 281             }
 282         }
 283     }
 284
 285
 286     protected final OffsetMap getOffsets() {
 287         return this.offsets;
 288     }
 289
 290     public final boolean isEmpty() {
 291         return this.offsets.isEmpty();
 292     }
 293
 294     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 295         final int offset = this.offsets.offsetOf(key);
 296         final Attributes attributes = this.offsets.getValue(this.values, offset);
 297         final long pathId = this.offsets.getValue(this.pathsId, offset);
 298         LOG.trace("Processing router key {} attributes {}", key, attributes);
 299         selector.processPath(attributes, key, offset, pathId);
 300     }
 301
 302     /**
 303      * Process best path selection.
 304      *
 305      * @param localAs The local autonomous system number
 306      * @param keyList List of RouteKey
 307      * @return the best path inside offset map passed
 308      */
 309     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 310         /*
 311          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 312          */
 313         final AddPathSelector selector = new AddPathSelector(localAs);
 314         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 315         LOG.trace("Best path selected {}", this.bestPath);
 316         return selector.result();
 317     }
 318
 319     private static boolean isFirstBestPath(final int bestPathPosition) {
 320         return bestPathPosition == 0;
 321     }
 322
 323     private static boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath,
 324             final boolean isFirstBestPath) {
 325         return !(!peerSupportsAddPath && !isFirstBestPath);
 326     }
 327
 328     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 329         this.oldNonAddPathBestPathTheSame = isNonAddPathBestPathTheSame(newBestPathList);
 330         filterRemovedPaths(newBestPathList);
 331         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
 332                 || newBestPathList != null
 333                 && !newBestPathList.equals(this.bestPath)) {
 334             this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 335             if (this.bestPath != null) {
 336                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 337             }
 338             this.bestPath = newBestPathList;
 339             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 340             return true;
 341         }
 342         return false;
 343     }
 344
 345     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 346         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 347                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 348     }
 349
 350     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 351         return pathList == null || pathList.isEmpty();
 352     }
 353
 354     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 355         if (this.bestPath == null) {
 356             return;
 357         }
 358         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 359         this.bestPath.forEach(oldBest -> {
 360             final Optional<AddPathBestPath> present = newBestPathList.stream()
 361                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 362                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 363             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 364         });
 365     }
 366 }