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