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