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.rev130925.PeerId;
  24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerRole;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.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, final NormalizedNode<?, ?> data) {
  93         LOG.trace("Find {} in {}", attributesIdentifier, data);
  94         final ContainerNode advertisedAttrs = (ContainerNode) NormalizedNodes.findNode(data, attributesIdentifier).orNull();
  95         return addRoute(key, advertisedAttrs);
  96     }
  97
  98     /**
  99      * Remove route
 100      *
 101      * @param key RouteKey of removed route
 102      * @param offset Offset of removed route
 103      * @return true if it was the last route
 104      */
 105     protected final boolean removeRoute(final RouteKey key, final int offset) {
 106         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 107         this.values = this.offsets.removeValue(this.values, offset);
 108         this.pathsId = this.offsets.removeValue(this.pathsId, offset);
 109         this.offsets = this.offsets.without(key);
 110         if(this.removedPaths == null) {
 111             this.removedPaths = new ArrayList<>();
 112         }
 113         this.removedPaths.add(new RemovedPath(key, pathId));
 114         return isEmpty();
 115     }
 116
 117     @Override
 118     public void updateRoute(final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final YangInstanceIdentifier locRibTarget,
 119         final RIBSupport ribSupport, final DOMDataWriteTransaction tx, final PathArgument routeIdPA) {
 120         if(this.bestPathRemoved != null) {
 121             this.bestPathRemoved.forEach(path -> {
 122                 final PathArgument routeIdAddPath = ribSupport.getRouteIdAddPath(path.getPathId(), routeIdPA);
 123                 final YangInstanceIdentifier pathAddPathTarget = ribSupport.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 124                 fillLocRib(pathAddPathTarget, null, tx);
 125             });
 126             this.bestPathRemoved = null;
 127         }
 128         if(this.removedPaths != null) {
 129             this.removedPaths.forEach(removedPath -> {
 130                 final PathArgument routeIdAddPath = ribSupport.getRouteIdAddPath(removedPath.getPathId(), routeIdPA);
 131                 fillAdjRibsOut(true, null, null, null, routeIdPA, routeIdAddPath, RouterIds.createPeerId(removedPath.getRouteId()),
 132                     peerPT, localTK, ribSupport, tx);
 133             });
 134             this.removedPaths = null;
 135         }
 136
 137         if(this.newBestPathToBeAdvertised != null) {
 138             this.newBestPathToBeAdvertised.forEach(path -> addPathToDataStore(path, isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA,
 139                 locRibTarget, ribSupport, peerPT, localTK, tx));
 140             this.newBestPathToBeAdvertised = null;
 141         }
 142     }
 143
 144     @Override
 145     public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath, final PeerExportGroup peerGroup,
 146         final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 147         final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 148         if(this.bestPath != null) {
 149             final PeerRole destPeerRole = getRoutePeerIdRole(peerPT, destPeer);
 150             this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, destPeerRole) &&
 151                 peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath(this.bestPath.indexOf(path))))
 152                 .forEach(path -> writeRoutePath(destPeer, routeId, peerPT, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx));
 153         }
 154     }
 155
 156     private void writeRoutePath(final PeerId destPeer, final PathArgument routeId, final ExportPolicyPeerTracker peerPT,
 157         final PeerExportGroup peerGroup, final boolean destPeerSupAddPath,
 158         final BestPath path, final YangInstanceIdentifier rootPath, final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 159         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeId);
 160         final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(getRoutePeerIdRole(peerPT,path.getPeerId()), path.getAttributes());
 161         if (destPeerSupAddPath) {
 162             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK), effectiveAttributes, createValue(routeIdAddPath, path), ribSup, tx);
 163         } else {
 164             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes, createValue(routeId, path), ribSup, tx);
 165         }
 166     }
 167
 168     private void addPathToDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA, final YangInstanceIdentifier locRibTarget,
 169         final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK, final DOMDataWriteTransaction tx) {
 170         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 171         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 172         final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
 173         final MapEntryNode value = createValue(routeIdPA, path);
 174         LOG.trace("Selected best value {}", addPathValue);
 175         fillLocRib(pathAddPathTarget, addPathValue, tx);
 176         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), value, addPathValue, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK,
 177             ribSup, tx);
 178     }
 179
 180     private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes, final NormalizedNode<?, ?> value, final MapEntryNode addPathValue,
 181         final PathArgument routeId, final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT, final TablesKey
 182         localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 183         /*
 184          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 185          * expose from which client a particular route was learned from in the local RIB, and have
 186          * the listener perform filtering.
 187          *
 188          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 189          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 190          * multiple times.
 191          */
 192         for (final PeerRole role : PeerRole.values()) {
 193             final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
 194             if (peerGroup != null) {
 195                 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(getRoutePeerIdRole(peerPT, routePeerId), attributes);
 196                 peerGroup.forEach((destPeer, rootPath) -> {
 197                     final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 198                     if (filterRoutes(routePeerId, destPeer, peerPT, localTK, role) &&
 199                         peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 200                         if (destPeerSupAddPath) {
 201                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK), effectiveAttributes,
 202                                 addPathValue, ribSup, tx);
 203                         } else if(!this.oldNonAddPathBestPathTheSame){
 204                             update(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes, value, ribSup, tx);
 205                         }
 206                     }
 207                 });
 208             }
 209         }
 210     }
 211
 212
 213     protected final OffsetMap getOffsets() {
 214         return this.offsets;
 215     }
 216
 217     public final boolean isEmpty() {
 218         return this.offsets.isEmpty();
 219     }
 220
 221     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 222         final int offset = this.offsets.offsetOf(key);
 223         final ContainerNode attributes = this.offsets.getValue(this.values, offset);
 224         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 225         LOG.trace("Processing router key {} attributes {}", key, attributes);
 226         selector.processPath(attributes, key, offset, pathId);
 227     }
 228
 229     /**
 230      * Process best path selection
 231      *
 232      * @param localAs The local autonomous system number
 233      * @param keyList List of RouteKey
 234      * @return the best path inside offset map passed
 235      */
 236     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 237         /*
 238          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 239          */
 240         final AddPathSelector selector = new AddPathSelector(localAs);
 241         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 242         LOG.trace("Best path selected {}", this.bestPath);
 243         return selector.result();
 244     }
 245
 246     private boolean isFirstBestPath(final int bestPathPosition) {
 247         return bestPathPosition == 0;
 248     }
 249
 250     private boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath, final boolean isFirstBestPath) {
 251         return !(!peerSupportsAddPath && !isFirstBestPath);
 252     }
 253
 254     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 255         this.oldNonAddPathBestPathTheSame = isNonAddPathBestPathTheSame(newBestPathList);
 256         filterRemovedPaths(newBestPathList);
 257         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty() || newBestPathList != null && !newBestPathList.equals(this.bestPath)) {
 258             this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 259             if(this.bestPath != null) {
 260                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 261             }
 262             this.bestPath = newBestPathList;
 263             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 264             return true;
 265         }
 266         return false;
 267     }
 268
 269     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 270         return !(this.bestPath == null || newBestPathList == null || this.bestPath.isEmpty() || newBestPathList.isEmpty()) &&
 271             this.bestPath.get(0).equals(newBestPathList.get(0));
 272     }
 273
 274     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 275         if(this.bestPath == null) {
 276             return;
 277         }
 278         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 279         this.bestPath.forEach(oldBest -> {
 280             final Optional<AddPathBestPath> present = newBestPathList.stream()
 281                 .filter(newBest -> newBest.getPathId() == oldBest.getPathId() && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 282             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 283         });
 284     }
 285 }