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 com.google.common.collect.Lists;
  11 import com.google.common.primitives.UnsignedInteger;
  12 import java.util.ArrayList;
  13 import java.util.List;
  14 import java.util.Optional;
  15 import javax.annotation.concurrent.NotThreadSafe;
  16 import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
  17 import org.opendaylight.protocol.bgp.mode.api.BestPath;
  18 import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry;
  19 import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker;
  20 import org.opendaylight.protocol.bgp.rib.spi.PeerExportGroup;
  21 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
  22 import org.opendaylight.protocol.bgp.rib.spi.RouterIds;
  23 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev171207.PeerId;
  24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev171207.PeerRole;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev171207.rib.TablesKey;
  26 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  27 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
  28 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  29 import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
  30 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  31 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  32 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
  33 import org.slf4j.Logger;
  34 import org.slf4j.LoggerFactory;
  35
  36 /**
  37  * A single route entry inside a route table. Maintains the attributes of
  38  * from all contributing peers. The information is stored in arrays with a
  39  * shared map of offsets for peers to allow lookups. This is needed to
  40  * maintain low memory overhead in face of large number of routes and peers,
  41  * where individual object overhead becomes the dominating factor.
  42  */
  43 @NotThreadSafe
  44 public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry {
  45
  46     private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
  47     private List<AddPathBestPath> bestPath;
  48     private List<AddPathBestPath> bestPathRemoved;
  49     protected OffsetMap offsets = OffsetMap.EMPTY;
  50     protected ContainerNode[] values = new ContainerNode[0];
  51     protected Long[] pathsId = new Long[0];
  52     private long pathIdCounter = 0L;
  53     private boolean oldNonAddPathBestPathTheSame;
  54     private List<AddPathBestPath> newBestPathToBeAdvertised;
  55     private List<RemovedPath> removedPaths;
  56
  57     private static final class RemovedPath {
  58         private final RouteKey key;
  59         private final Long pathId;
  60
  61         RemovedPath(final RouteKey key, final Long pathId) {
  62             this.key = key;
  63             this.pathId = pathId;
  64         }
  65
  66         Long getPathId() {
  67             return this.pathId;
  68         }
  69
  70         UnsignedInteger getRouteId() {
  71             return this.key.getRouteId();
  72         }
  73     }
  74
  75     private int addRoute(final RouteKey key, final ContainerNode attributes) {
  76         int offset = this.offsets.offsetOf(key);
  77         if (offset < 0) {
  78             final OffsetMap newOffsets = this.offsets.with(key);
  79             offset = newOffsets.offsetOf(key);
  80             final ContainerNode[] newAttributes = newOffsets.expand(this.offsets, this.values, offset);
  81             final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
  82             this.values = newAttributes;
  83             this.offsets = newOffsets;
  84             this.pathsId = newPathsId;
  85             this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
  86         }
  87         this.offsets.setValue(this.values, offset, attributes);
  88         LOG.trace("Added route from {} attributes {}", key.getRouteId(), attributes);
  89         return offset;
  90     }
  91
  92     protected int addRoute(final RouteKey key, final NodeIdentifier attributesIdentifier,
  93             final NormalizedNode<?, ?> data) {
  94         LOG.trace("Find {} in {}", attributesIdentifier, data);
  95         final ContainerNode advertisedAttrs
  96                 = (ContainerNode) NormalizedNodes.findNode(data, attributesIdentifier).orElse(null);
  97         return addRoute(key, advertisedAttrs);
  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 updateRoute(final TablesKey localTK, final ExportPolicyPeerTracker peerPT,
 121             final YangInstanceIdentifier locRibTarget, final RIBSupport ribSupport, final DOMDataWriteTransaction tx,
 122             final PathArgument routeIdPA) {
 123         if (this.bestPathRemoved != null) {
 124             this.bestPathRemoved.forEach(path -> {
 125                 final PathArgument routeIdAddPath = ribSupport.getRouteIdAddPath(path.getPathId(), routeIdPA);
 126                 final YangInstanceIdentifier pathAddPathTarget = ribSupport
 127                         .routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 128                 fillLocRib(pathAddPathTarget, null, tx);
 129             });
 130             this.bestPathRemoved = null;
 131         }
 132         if (this.removedPaths != null) {
 133             this.removedPaths.forEach(removedPath -> {
 134                 final PathArgument routeIdAddPath = ribSupport.getRouteIdAddPath(removedPath.getPathId(), routeIdPA);
 135                 fillAdjRibsOut(true, null, null, null, routeIdPA, routeIdAddPath,
 136                         RouterIds.createPeerId(removedPath.getRouteId()), peerPT, localTK, ribSupport, tx);
 137             });
 138             this.removedPaths = null;
 139         }
 140
 141         if (this.newBestPathToBeAdvertised != null) {
 142             this.newBestPathToBeAdvertised.forEach(path -> addPathToDataStore(path,
 143                     isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA, locRibTarget, ribSupport, peerPT,
 144                     localTK, tx));
 145             this.newBestPathToBeAdvertised = null;
 146         }
 147     }
 148
 149     @Override
 150     public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath,
 151             final PeerExportGroup peerGroup, final TablesKey localTK, final ExportPolicyPeerTracker peerPT,
 152             final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 153         final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 154         if (this.bestPath != null) {
 155             final PeerRole destPeerRole = getRoutePeerIdRole(peerPT, destPeer);
 156             this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK,
 157                     destPeerRole) && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath,
 158                     isFirstBestPath(this.bestPath.indexOf(path)))).forEach(path -> writeRoutePath(destPeer, routeId,
 159                     peerPT, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx));
 160         }
 161     }
 162
 163     private void writeRoutePath(final PeerId destPeer, final PathArgument routeId, final ExportPolicyPeerTracker peerPT,
 164         final PeerExportGroup peerGroup, final boolean destPeerSupAddPath, final BestPath path,
 165             final YangInstanceIdentifier rootPath, final TablesKey localTK, final RIBSupport ribSup,
 166             final DOMDataWriteTransaction tx) {
 167         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeId);
 168         final ContainerNode effectiveAttributes = peerGroup
 169                 .effectiveAttributes(getRoutePeerIdRole(peerPT,path.getPeerId()), path.getAttributes());
 170         if (destPeerSupAddPath) {
 171             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK), effectiveAttributes,
 172                     createValue(routeIdAddPath, path), ribSup, tx);
 173         } else {
 174             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes,
 175                     createValue(routeId, path), ribSup, tx);
 176         }
 177     }
 178
 179     private void addPathToDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA,
 180             final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT,
 181             final TablesKey localTK, final DOMDataWriteTransaction tx) {
 182         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 183         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER),
 184                 routeIdAddPath);
 185         final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
 186         final MapEntryNode value = createValue(routeIdPA, path);
 187         LOG.trace("Selected best value {}", addPathValue);
 188         fillLocRib(pathAddPathTarget, addPathValue, tx);
 189         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), value, addPathValue, routeIdPA, routeIdAddPath,
 190                 path.getPeerId(), peerPT, localTK,
 191             ribSup, tx);
 192     }
 193
 194     private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes,
 195             final NormalizedNode<?, ?> value, final MapEntryNode addPathValue, final PathArgument routeId,
 196             final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT,
 197             final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 198         /*
 199          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 200          * expose from which client a particular route was learned from in the local RIB, and have
 201          * the listener perform filtering.
 202          *
 203          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 204          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 205          * multiple times.
 206          */
 207         for (final PeerRole role : PeerRole.values()) {
 208             final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
 209             if (peerGroup != null) {
 210                 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(getRoutePeerIdRole(peerPT,
 211                         routePeerId), attributes);
 212                 peerGroup.forEach((destPeer, rootPath) -> {
 213                     final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 214                     if (filterRoutes(routePeerId, destPeer, peerPT, localTK, role)
 215                             && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 216                         if (destPeerSupAddPath) {
 217                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK),
 218                                     effectiveAttributes, addPathValue, ribSup, tx);
 219                         } else if (!this.oldNonAddPathBestPathTheSame) {
 220                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK),
 221                                     effectiveAttributes, value, ribSup, tx);
 222                         }
 223                     }
 224                 });
 225             }
 226         }
 227     }
 228
 229
 230     protected final OffsetMap getOffsets() {
 231         return this.offsets;
 232     }
 233
 234     public final boolean isEmpty() {
 235         return this.offsets.isEmpty();
 236     }
 237
 238     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 239         final int offset = this.offsets.offsetOf(key);
 240         final ContainerNode attributes = this.offsets.getValue(this.values, offset);
 241         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 242         LOG.trace("Processing router key {} attributes {}", key, attributes);
 243         selector.processPath(attributes, key, offset, pathId);
 244     }
 245
 246     /**
 247      * Process best path selection.
 248      *
 249      * @param localAs The local autonomous system number
 250      * @param keyList List of RouteKey
 251      * @return the best path inside offset map passed
 252      */
 253     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 254         /*
 255          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 256          */
 257         final AddPathSelector selector = new AddPathSelector(localAs);
 258         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 259         LOG.trace("Best path selected {}", this.bestPath);
 260         return selector.result();
 261     }
 262
 263     private static boolean isFirstBestPath(final int bestPathPosition) {
 264         return bestPathPosition == 0;
 265     }
 266
 267     private static boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath,
 268             final boolean isFirstBestPath) {
 269         return !(!peerSupportsAddPath && !isFirstBestPath);
 270     }
 271
 272     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 273         this.oldNonAddPathBestPathTheSame = isNonAddPathBestPathTheSame(newBestPathList);
 274         filterRemovedPaths(newBestPathList);
 275         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty() || newBestPathList != null
 276                 && !newBestPathList.equals(this.bestPath)) {
 277             this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 278             if (this.bestPath != null) {
 279                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 280             }
 281             this.bestPath = newBestPathList;
 282             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 283             return true;
 284         }
 285         return false;
 286     }
 287
 288     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 289         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 290                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 291     }
 292
 293     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 294         return pathList == null || pathList.isEmpty();
 295     }
 296
 297     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 298         if (this.bestPath == null) {
 299             return;
 300         }
 301         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 302         this.bestPath.forEach(oldBest -> {
 303             final Optional<AddPathBestPath> present = newBestPathList.stream()
 304                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 305                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 306             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 307         });
 308     }
 309 }