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