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