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