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.ImmutableList;
  11 import com.google.common.collect.Lists;
  12 import com.google.common.primitives.UnsignedInteger;
  13 import java.util.ArrayList;
  14 import java.util.Collections;
  15 import java.util.List;
  16 import java.util.Optional;
  17 import java.util.stream.Collectors;
  18 import javax.annotation.concurrent.NotThreadSafe;
  19 import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
  20 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
  21 import org.opendaylight.protocol.bgp.rib.spi.entry.ActualBestPathRoutes;
  22 import org.opendaylight.protocol.bgp.rib.spi.entry.AdvertizedRoute;
  23 import org.opendaylight.protocol.bgp.rib.spi.entry.RouteEntryInfo;
  24 import org.opendaylight.protocol.bgp.rib.spi.entry.StaleBestPathRoute;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
  26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
  27 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.tables.Routes;
  28 import org.opendaylight.yangtools.yang.binding.ChildOf;
  29 import org.opendaylight.yangtools.yang.binding.ChoiceIn;
  30 import org.opendaylight.yangtools.yang.binding.DataObject;
  31 import org.opendaylight.yangtools.yang.binding.Identifiable;
  32 import org.opendaylight.yangtools.yang.binding.Identifier;
  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<C extends Routes & DataObject & ChoiceIn<Tables>,
  45         S extends ChildOf<? super C>,
  46         R extends Route & ChildOf<? super S> & Identifiable<I>, I extends Identifier<R>>
  47         implements RouteEntry<C, S, R, I> {
  48
  49     private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
  50     private static final Long[] EMPTY_PATHS_ID = new Long[0];
  51     private static final Route[] EMPTY_VALUES = new Route[0];
  52
  53     protected OffsetMap offsets = OffsetMap.EMPTY;
  54     protected R[] values = (R[]) EMPTY_VALUES;
  55     protected Long[] pathsId = EMPTY_PATHS_ID;
  56     private List<AddPathBestPath> bestPath;
  57     private List<AddPathBestPath> bestPathRemoved;
  58     private long pathIdCounter = 0L;
  59     private boolean isNonAddPathBestPathNew;
  60     private List<AddPathBestPath> newBestPathToBeAdvertised;
  61     private List<Long> removedPathsId;
  62
  63     private R createRoute(final RIBSupport<C, S, R, I> ribSup, final String routeKey,
  64             final long pathId, final AddPathBestPath path) {
  65         final OffsetMap map = getOffsets();
  66         final R route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
  67         return ribSup.createRoute(route, routeKey, pathId, path.getAttributes());
  68     }
  69
  70     @Override
  71     public final int addRoute(final UnsignedInteger routerId, final long remotePathId, final R route) {
  72         final RouteKey key = new RouteKey(routerId, remotePathId);
  73         int offset = this.offsets.offsetOf(key);
  74         if (offset < 0) {
  75             final OffsetMap newOffsets = this.offsets.with(key);
  76             offset = newOffsets.offsetOf(key);
  77             final R[] newRoute = newOffsets.expand(this.offsets, this.values, offset);
  78             final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
  79             this.values = newRoute;
  80             this.offsets = newOffsets;
  81             this.pathsId = newPathsId;
  82             this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
  83         }
  84         this.offsets.setValue(this.values, offset, route);
  85         LOG.trace("Added route {} from {}", route, key.getRouteId());
  86         return offset;
  87     }
  88
  89     @Override
  90     public final boolean removeRoute(final UnsignedInteger routerId, final long remotePathId) {
  91         final RouteKey key = new RouteKey(routerId, remotePathId);
  92         final int offset = getOffsets().offsetOf(key);
  93         final long pathId = this.offsets.getValue(this.pathsId, offset);
  94         this.values = this.offsets.removeValue(this.values, offset, (R[]) EMPTY_VALUES);
  95         this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
  96         this.offsets = this.offsets.without(key);
  97         if (this.removedPathsId == null) {
  98             this.removedPathsId = new ArrayList<>();
  99         }
 100         this.removedPathsId.add(pathId);
 101         return isEmpty();
 102     }
 103
 104     @Override
 105     public final Optional<StaleBestPathRoute<C, S, R, I>> removeStalePaths(final RIBSupport<C, S, R, I> ribSupport,
 106             final String routeKey) {
 107         if ((this.bestPathRemoved == null || this.bestPathRemoved.isEmpty()) && this.removedPathsId == null) {
 108             return Optional.empty();
 109         }
 110         List<Long> stalePaths = Collections.emptyList();
 111         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()) {
 112             stalePaths = this.bestPathRemoved.stream().map(AddPathBestPath::getPathId).collect(Collectors.toList());
 113             this.bestPathRemoved = null;
 114         }
 115         final StaleBestPathRoute<C, S, R, I> stale = new StaleBestPathRoute<>(ribSupport, routeKey, stalePaths,
 116                 this.removedPathsId, this.isNonAddPathBestPathNew);
 117         this.removedPathsId = null;
 118         return Optional.of(stale);
 119     }
 120
 121     @Override
 122     public final List<AdvertizedRoute<C, S, R, I>> newBestPaths(final RIBSupport<C, S, R, I> ribSupport,
 123             final String routeKey) {
 124         if (this.newBestPathToBeAdvertised == null || this.newBestPathToBeAdvertised.isEmpty()) {
 125             return Collections.emptyList();
 126         }
 127         final List<AdvertizedRoute<C, S, R, I>> advertized = new ArrayList<>(newBestPathToBeAdvertised.size());
 128         final AddPathBestPath firstBestPath = this.bestPath.isEmpty() ? null : this.bestPath.get(0);
 129         for (final AddPathBestPath path : this.newBestPathToBeAdvertised) {
 130             final R routeAddPath = createRoute(ribSupport, routeKey, path.getPathId(), path);
 131             // FIXME: can we use identity check here?
 132             final boolean isFirstBestPath = firstBestPath != null && firstBestPath.equals(path);
 133             final AdvertizedRoute<C, S, R, I> adv = new AdvertizedRoute<>(ribSupport, isFirstBestPath,
 134                     routeAddPath, path.getAttributes(), path.getPeerId());
 135             advertized.add(adv);
 136         }
 137         this.newBestPathToBeAdvertised = null;
 138         return advertized;
 139     }
 140
 141     @Override
 142     public final List<ActualBestPathRoutes<C, S, R, I>> actualBestPaths(final RIBSupport<C, S, R, I> ribSupport,
 143             final RouteEntryInfo entryInfo) {
 144         if (this.bestPath == null || this.bestPath.isEmpty()) {
 145             return Collections.emptyList();
 146         }
 147         final List<ActualBestPathRoutes<C, S, R, I>> preexistentRoutes = new ArrayList<>();
 148         for (final AddPathBestPath path : this.bestPath) {
 149             final R route = createRoute(ribSupport, entryInfo.getRouteKey(), path.getPathId(), path);
 150             final ActualBestPathRoutes<C, S, R, I> adv = new ActualBestPathRoutes<>(ribSupport, route, path.getPeerId(),
 151                     path.getAttributes());
 152             preexistentRoutes.add(adv);
 153         }
 154         return preexistentRoutes;
 155     }
 156
 157     private OffsetMap getOffsets() {
 158         return this.offsets;
 159     }
 160
 161     public final boolean isEmpty() {
 162         return this.offsets.isEmpty();
 163     }
 164
 165     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 166         final int offset = this.offsets.offsetOf(key);
 167         final R route = this.offsets.getValue(this.values, offset);
 168         final long pathId = this.offsets.getValue(this.pathsId, offset);
 169         LOG.trace("Processing router key {} route {}", key, route);
 170         selector.processPath(route.getAttributes(), key, offset, pathId);
 171     }
 172
 173     /**
 174      * Process best path selection.
 175      *
 176      * @param localAs The local autonomous system number
 177      * @param keyList List of RouteKey
 178      * @return the best path inside offset map passed
 179      */
 180     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 181         /*
 182          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 183          */
 184         final AddPathSelector selector = new AddPathSelector(localAs);
 185         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 186         LOG.trace("Best path selected {}", this.bestPath);
 187         return selector.result();
 188     }
 189
 190     protected boolean isBestPathNew(final ImmutableList<AddPathBestPath> newBestPathList) {
 191         this.isNonAddPathBestPathNew = !isNonAddPathBestPathTheSame(newBestPathList);
 192         filterRemovedPaths(newBestPathList);
 193         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
 194                 || newBestPathList != null
 195                 && !newBestPathList.equals(this.bestPath)) {
 196             if (this.bestPath != null) {
 197                 this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 198                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 199             } else {
 200                 this.newBestPathToBeAdvertised = newBestPathList;
 201             }
 202             this.bestPath = newBestPathList;
 203             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 204             return true;
 205         }
 206         return false;
 207     }
 208
 209     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 210         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 211                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 212     }
 213
 214     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 215         return pathList == null || pathList.isEmpty();
 216     }
 217
 218     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 219         if (this.bestPath == null) {
 220             return;
 221         }
 222         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 223         this.bestPath.forEach(oldBest -> {
 224             final Optional<AddPathBestPath> present = newBestPathList.stream()
 225                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 226                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 227             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 228         });
 229     }
 230 }