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