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.dom.api.DOMDataWriteTransaction;
  19 import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry;
  20 import org.opendaylight.protocol.bgp.rib.spi.BGPPeerTracker;
  21 import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker;
  22 import org.opendaylight.protocol.bgp.rib.spi.Peer;
  23 import org.opendaylight.protocol.bgp.rib.spi.PeerExportGroup;
  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.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev171207.PeerId;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev171207.PeerRole;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev171207.rib.TablesKey;
  31 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  32 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
  33 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates;
  34 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  35 import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
  36 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  37 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  38 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
  39 import org.slf4j.Logger;
  40 import org.slf4j.LoggerFactory;
  41
  42 /**
  43  * A single route entry inside a route table. Maintains the attributes of
  44  * from all contributing peers. The information is stored in arrays with a
  45  * shared map of offsets for peers to allow lookups. This is needed to
  46  * maintain low memory overhead in face of large number of routes and peers,
  47  * where individual object overhead becomes the dominating factor.
  48  */
  49 @NotThreadSafe
  50 public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry<AddPathBestPath> {
  51
  52     private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
  53     private List<AddPathBestPath> bestPath;
  54     private List<AddPathBestPath> bestPathRemoved;
  55     protected OffsetMap offsets = OffsetMap.EMPTY;
  56     protected ContainerNode[] values = new ContainerNode[0];
  57     protected Long[] pathsId = new Long[0];
  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     private int addRoute(final RouteKey key, final ContainerNode 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 ContainerNode[] 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     protected int addRoute(final RouteKey key, final NodeIdentifier attributesIdentifier,
 103             final NormalizedNode<?, ?> data) {
 104         LOG.trace("Find {} in {}", attributesIdentifier, data);
 105         final ContainerNode advertisedAttrs
 106                 = (ContainerNode) NormalizedNodes.findNode(data, attributesIdentifier).orElse(null);
 107         return addRoute(key, advertisedAttrs);
 108     }
 109
 110     /**
 111      * Remove route.
 112      *
 113      * @param key RouteKey of removed route
 114      * @param offset Offset of removed route
 115      * @return true if it was the last route
 116      */
 117     protected final boolean removeRoute(final RouteKey key, final int offset) {
 118         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 119         this.values = this.offsets.removeValue(this.values, offset);
 120         this.pathsId = this.offsets.removeValue(this.pathsId, offset);
 121         this.offsets = this.offsets.without(key);
 122         if (this.removedPaths == null) {
 123             this.removedPaths = new ArrayList<>();
 124         }
 125         this.removedPaths.add(new RemovedPath(key, pathId));
 126         return isEmpty();
 127     }
 128
 129     @Override
 130     public void updateBestPaths(final RouteEntryDependenciesContainer entryDependencies,
 131             final NodeIdentifierWithPredicates routeIdPA, final DOMDataWriteTransaction tx) {
 132         final RIBSupport ribSupport = entryDependencies.getRibSupport();
 133         final ExportPolicyPeerTracker peerPT = entryDependencies.getExportPolicyPeerTracker();
 134         if (this.bestPathRemoved != null) {
 135             this.bestPathRemoved.forEach(path -> {
 136                 final PathArgument routeIdAddPath = ribSupport.getRouteIdAddPath(path.getPathId(), routeIdPA);
 137                 final YangInstanceIdentifier pathAddPathTarget = ribSupport
 138                         .routePath(entryDependencies.getLocRibTableTarget().node(ROUTES_IDENTIFIER), routeIdAddPath);
 139                 fillLocRib(pathAddPathTarget, null, tx);
 140             });
 141             this.bestPathRemoved = null;
 142         }
 143         if (this.removedPaths != null) {
 144             this.removedPaths.forEach(removedPath -> {
 145                 final PathArgument routeIdAddPath = ribSupport.getRouteIdAddPath(removedPath.getPathId(), routeIdPA);
 146                 final PathArgument routeIdAddPathDefault = ribSupport.getRouteIdAddPath(NON_PATH_ID_VALUE, routeIdPA);
 147                 fillAdjRibsOut(true, null, null, null,
 148                         routeIdAddPathDefault, routeIdAddPath,
 149                         RouterIds.createPeerId(removedPath.getRouteId()),
 150                         peerPT, entryDependencies.getLocalTablesKey(), ribSupport, tx);
 151             });
 152             this.removedPaths = null;
 153         }
 154
 155         if (this.newBestPathToBeAdvertised != null) {
 156             this.newBestPathToBeAdvertised.forEach(path -> addPathToDataStore(entryDependencies, path,
 157                     isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA,
 158                     peerPT, tx));
 159             this.newBestPathToBeAdvertised = null;
 160         }
 161     }
 162
 163     @Override
 164     public void initializeBestPaths(final RouteEntryDependenciesContainer entryDependencies,
 165             final RouteEntryInfo entryInfo, final PeerExportGroup peerGroup, final DOMDataWriteTransaction tx) {
 166         final PeerId toPeer = entryInfo.getToPeerId();
 167         final ExportPolicyPeerTracker peerPT = entryDependencies.getExportPolicyPeerTracker();
 168         final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(toPeer);
 169         if (this.bestPath != null) {
 170             final TablesKey localTk = entryDependencies.getLocalTablesKey();
 171             final RIBSupport ribSup = entryDependencies.getRibSupport();
 172             this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), toPeer, localTk)
 173                     && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath,
 174                     isFirstBestPath(this.bestPath.indexOf(path))))
 175                     .forEach(path -> writeRoutePath(entryInfo, peerGroup, destPeerSupAddPath,
 176                             path, localTk, ribSup, tx));
 177         }
 178     }
 179
 180     private void writeRoutePath(final RouteEntryInfo entryInfo, final PeerExportGroup peerGroup,
 181             final boolean destPeerSupAddPath, final AddPathBestPath path,
 182             final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 183         final NodeIdentifierWithPredicates routeId = entryInfo.getRouteId();
 184         final Peer fromPeer = this.peerTracker.getPeer(path.getPeerId());
 185         final ContainerNode effectiveAttributes
 186                 = peerGroup.effectiveAttributes(fromPeer.getRole(), path.getAttributes());
 187         final NodeIdentifierWithPredicates routeIdAddPath = ribSup
 188                 .getRouteIdAddPath(destPeerSupAddPath ? path.getPathId() : NON_PATH_ID_VALUE, routeId);
 189
 190         writeRoute(entryInfo.getToPeerId(), getAdjRibOutYII(ribSup, entryInfo.getRootPath(), routeIdAddPath, localTK),
 191                 effectiveAttributes, createValue(routeIdAddPath, path), ribSup, tx);
 192     }
 193
 194     private void addPathToDataStore(final RouteEntryDependenciesContainer entryDependencies, final AddPathBestPath path,
 195             final boolean isFirstBestPath, final NodeIdentifierWithPredicates routeIdPA,
 196             final ExportPolicyPeerTracker peerPT, final DOMDataWriteTransaction tx) {
 197         final RIBSupport ribSup = entryDependencies.getRibSupport();
 198         final NodeIdentifierWithPredicates routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 199         final NodeIdentifierWithPredicates routeIdAddPathDefault
 200                 = ribSup.getRouteIdAddPath(NON_PATH_ID_VALUE, routeIdPA);
 201         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(entryDependencies.getLocRibTableTarget()
 202                 .node(ROUTES_IDENTIFIER), routeIdAddPath);
 203         final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
 204         final MapEntryNode defaultValue = createValue(routeIdAddPathDefault, path);
 205         LOG.trace("Selected best value {}", addPathValue);
 206         fillLocRib(pathAddPathTarget, addPathValue, tx);
 207         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), defaultValue, addPathValue, routeIdAddPathDefault,
 208             routeIdAddPath, path.getPeerId(), peerPT, entryDependencies.getLocalTablesKey(), ribSup, tx);
 209     }
 210
 211     private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes,
 212             final MapEntryNode defaultValue, final MapEntryNode addPathValue,
 213             final PathArgument routeIdAddPathDefault,
 214             final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT,
 215             final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 216         /*
 217          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 218          * expose from which client a particular route was learned from in the local RIB, and have
 219          * the listener perform filtering.
 220          *
 221          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 222          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 223          * multiple times.
 224          */
 225         for (final PeerRole role : PeerRole.values()) {
 226             final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
 227             if (peerGroup != null) {
 228                 final Peer fromPeer = this.peerTracker.getPeer(routePeerId);
 229                 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(
 230                         fromPeer.getRole(), attributes);
 231                 peerGroup.forEach((destPeer, rootPath) -> {
 232                     final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 233                     if (filterRoutes(routePeerId, destPeer, localTK)
 234                             && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 235                         if (destPeerSupAddPath) {
 236                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK),
 237                                     effectiveAttributes, addPathValue, ribSup, tx);
 238                         } else if (!this.oldNonAddPathBestPathTheSame) {
 239                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPathDefault, localTK),
 240                                     effectiveAttributes, defaultValue, ribSup, tx);
 241                         }
 242                     }
 243                 });
 244             }
 245         }
 246     }
 247
 248
 249     protected final OffsetMap getOffsets() {
 250         return this.offsets;
 251     }
 252
 253     public final boolean isEmpty() {
 254         return this.offsets.isEmpty();
 255     }
 256
 257     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 258         final int offset = this.offsets.offsetOf(key);
 259         final ContainerNode attributes = this.offsets.getValue(this.values, offset);
 260         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 261         LOG.trace("Processing router key {} attributes {}", key, attributes);
 262         selector.processPath(attributes, key, offset, pathId);
 263     }
 264
 265     /**
 266      * Process best path selection.
 267      *
 268      * @param localAs The local autonomous system number
 269      * @param keyList List of RouteKey
 270      * @return the best path inside offset map passed
 271      */
 272     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 273         /*
 274          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 275          */
 276         final AddPathSelector selector = new AddPathSelector(localAs);
 277         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 278         LOG.trace("Best path selected {}", this.bestPath);
 279         return selector.result();
 280     }
 281
 282     private static boolean isFirstBestPath(final int bestPathPosition) {
 283         return bestPathPosition == 0;
 284     }
 285
 286     private static boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath,
 287             final boolean isFirstBestPath) {
 288         return !(!peerSupportsAddPath && !isFirstBestPath);
 289     }
 290
 291     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 292         this.oldNonAddPathBestPathTheSame = isNonAddPathBestPathTheSame(newBestPathList);
 293         filterRemovedPaths(newBestPathList);
 294         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
 295                 || newBestPathList != null
 296                 && !newBestPathList.equals(this.bestPath)) {
 297             this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 298             if (this.bestPath != null) {
 299                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 300             }
 301             this.bestPath = newBestPathList;
 302             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 303             return true;
 304         }
 305         return false;
 306     }
 307
 308     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 309         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 310                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 311     }
 312
 313     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 314         return pathList == null || pathList.isEmpty();
 315     }
 316
 317     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 318         if (this.bestPath == null) {
 319             return;
 320         }
 321         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 322         this.bestPath.forEach(oldBest -> {
 323             final Optional<AddPathBestPath> present = newBestPathList.stream()
 324                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 325                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 326             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 327         });
 328     }
 329 }