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