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;
  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, 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, 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 = ribSup.getRouteIdAddPath(NON_PATH_ID, routeIdPA);
 200         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(entryDependencies.getLocRibTableTarget()
 201                 .node(ROUTES_IDENTIFIER), routeIdAddPath);
 202         final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
 203         final MapEntryNode defaultValue = createValue(routeIdAddPathDefault, path);
 204         LOG.trace("Selected best value {}", addPathValue);
 205         fillLocRib(pathAddPathTarget, addPathValue, tx);
 206         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), defaultValue, addPathValue, routeIdAddPathDefault,
 207             routeIdAddPath, path.getPeerId(), peerPT, entryDependencies.getLocalTablesKey(), ribSup, tx);
 208     }
 209
 210     private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes,
 211             final MapEntryNode defaultValue, final MapEntryNode addPathValue,
 212             final PathArgument routeIdAddPathDefault,
 213             final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT,
 214             final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 215         /*
 216          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 217          * expose from which client a particular route was learned from in the local RIB, and have
 218          * the listener perform filtering.
 219          *
 220          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 221          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 222          * multiple times.
 223          */
 224         for (final PeerRole role : PeerRole.values()) {
 225             final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
 226             if (peerGroup != null) {
 227                 final Peer fromPeer = this.peerTracker.getPeer(routePeerId);
 228                 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(
 229                         fromPeer.getRole(), attributes);
 230                 peerGroup.forEach((destPeer, rootPath) -> {
 231                     final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 232                     if (filterRoutes(routePeerId, destPeer, localTK)
 233                             && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 234                         if (destPeerSupAddPath) {
 235                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK),
 236                                     effectiveAttributes, addPathValue, ribSup, tx);
 237                         } else if (!this.oldNonAddPathBestPathTheSame) {
 238                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPathDefault, localTK),
 239                                     effectiveAttributes, defaultValue, ribSup, tx);
 240                         }
 241                     }
 242                 });
 243             }
 244         }
 245     }
 246
 247
 248     protected final OffsetMap getOffsets() {
 249         return this.offsets;
 250     }
 251
 252     public final boolean isEmpty() {
 253         return this.offsets.isEmpty();
 254     }
 255
 256     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 257         final int offset = this.offsets.offsetOf(key);
 258         final ContainerNode attributes = this.offsets.getValue(this.values, offset);
 259         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 260         LOG.trace("Processing router key {} attributes {}", key, attributes);
 261         selector.processPath(attributes, key, offset, pathId);
 262     }
 263
 264     /**
 265      * Process best path selection.
 266      *
 267      * @param localAs The local autonomous system number
 268      * @param keyList List of RouteKey
 269      * @return the best path inside offset map passed
 270      */
 271     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 272         /*
 273          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 274          */
 275         final AddPathSelector selector = new AddPathSelector(localAs);
 276         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 277         LOG.trace("Best path selected {}", this.bestPath);
 278         return selector.result();
 279     }
 280
 281     private static boolean isFirstBestPath(final int bestPathPosition) {
 282         return bestPathPosition == 0;
 283     }
 284
 285     private static boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath,
 286             final boolean isFirstBestPath) {
 287         return !(!peerSupportsAddPath && !isFirstBestPath);
 288     }
 289
 290     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 291         this.oldNonAddPathBestPathTheSame = isNonAddPathBestPathTheSame(newBestPathList);
 292         filterRemovedPaths(newBestPathList);
 293         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
 294                 || newBestPathList != null
 295                 && !newBestPathList.equals(this.bestPath)) {
 296             this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 297             if (this.bestPath != null) {
 298                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 299             }
 300             this.bestPath = newBestPathList;
 301             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 302             return true;
 303         }
 304         return false;
 305     }
 306
 307     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 308         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 309                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 310     }
 311
 312     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 313         return pathList == null || pathList.isEmpty();
 314     }
 315
 316     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 317         if (this.bestPath == null) {
 318             return;
 319         }
 320         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 321         this.bestPath.forEach(oldBest -> {
 322             final Optional<AddPathBestPath> present = newBestPathList.stream()
 323                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 324                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 325             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 326         });
 327     }
 328 }