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 static com.google.common.base.Verify.verifyNotNull;
  11 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID;
  12 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID_VALUE;
  13
  14 import com.google.common.collect.ImmutableList;
  15 import com.google.common.collect.Lists;
  16 import java.util.ArrayList;
  17 import java.util.Collections;
  18 import java.util.List;
  19 import java.util.Optional;
  20 import java.util.stream.Collectors;
  21 import javax.annotation.concurrent.NotThreadSafe;
  22 import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
  23 import org.opendaylight.protocol.bgp.mode.impl.BestPathStateImpl;
  24 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
  25 import org.opendaylight.protocol.bgp.rib.spi.RouterId;
  26 import org.opendaylight.protocol.bgp.rib.spi.entry.ActualBestPathRoutes;
  27 import org.opendaylight.protocol.bgp.rib.spi.entry.AdvertizedRoute;
  28 import org.opendaylight.protocol.bgp.rib.spi.entry.RouteEntryInfo;
  29 import org.opendaylight.protocol.bgp.rib.spi.entry.StaleBestPathRoute;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev180329.PathId;
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
  33 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.tables.Routes;
  34 import org.opendaylight.yangtools.yang.binding.ChildOf;
  35 import org.opendaylight.yangtools.yang.binding.ChoiceIn;
  36 import org.opendaylight.yangtools.yang.binding.DataObject;
  37 import org.opendaylight.yangtools.yang.binding.Identifiable;
  38 import org.opendaylight.yangtools.yang.binding.Identifier;
  39 import org.slf4j.Logger;
  40 import org.slf4j.LoggerFactory;
  41
  42 /**
  43  * A single route entry inside a route table. Maintains the attributes of
  44  * from all contributing peers. The information is stored in arrays with a
  45  * shared map of offsets for peers to allow lookups. This is needed to
  46  * maintain low memory overhead in face of large number of routes and peers,
  47  * where individual object overhead becomes the dominating factor.
  48  */
  49 @NotThreadSafe
  50 public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject & ChoiceIn<Tables>,
  51         S extends ChildOf<? super C>,
  52         R extends Route & ChildOf<? super S> & Identifiable<I>, I extends Identifier<R>>
  53         implements RouteEntry<C, S, R, I> {
  54
  55     private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
  56     private static final Long[] EMPTY_PATHS_ID = new Long[0];
  57     private static final Route[] EMPTY_VALUES = new Route[0];
  58
  59     private RouteKeyOffsets offsets = RouteKeyOffsets.EMPTY;
  60     private R[] values = (R[]) EMPTY_VALUES;
  61     private Long[] pathsId = EMPTY_PATHS_ID;
  62     private List<AddPathBestPath> bestPath;
  63     private List<AddPathBestPath> bestPathRemoved;
  64     private List<AddPathBestPath> newBestPathToBeAdvertised;
  65     private List<Long> removedPathsId;
  66
  67     private long pathIdCounter = 0L;
  68     private boolean isNonAddPathBestPathNew;
  69
  70     private R createRoute(final RIBSupport<C, S, R, I> ribSup, final String routeKey, final AddPathBestPath path) {
  71         final RouteKeyOffsets map = this.offsets;
  72         final R route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
  73         return ribSup.createRoute(route, ribSup.createRouteListKey(pathIdObj(path.getPathIdLong()), routeKey),
  74             path.getAttributes());
  75     }
  76
  77     @Override
  78     public final int addRoute(final RouterId routerId, final Long remotePathId, final R route) {
  79         final RouteKey key = new RouteKey(routerId, remotePathId);
  80         int offset = this.offsets.offsetOf(key);
  81         if (offset < 0) {
  82             final RouteKeyOffsets newOffsets = this.offsets.with(key);
  83             offset = newOffsets.offsetOf(key);
  84             final R[] newRoute = newOffsets.expand(this.offsets, this.values, offset);
  85             final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
  86             this.values = newRoute;
  87             this.offsets = newOffsets;
  88             this.pathsId = newPathsId;
  89             this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
  90         }
  91         this.offsets.setValue(this.values, offset, route);
  92         LOG.trace("Added route {} from {}", route, routerId);
  93         return offset;
  94     }
  95
  96     @Override
  97     public final boolean removeRoute(final RouterId routerId, final Long remotePathId) {
  98         final RouteKey key = new RouteKey(routerId, remotePathId);
  99         final int offset = this.offsets.offsetOf(key);
 100         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 101         this.values = this.offsets.removeValue(this.values, offset, (R[]) EMPTY_VALUES);
 102         this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
 103         this.offsets = this.offsets.without(key);
 104         if (this.removedPathsId == null) {
 105             this.removedPathsId = new ArrayList<>();
 106         }
 107         this.removedPathsId.add(pathId);
 108         return this.offsets.isEmpty();
 109     }
 110
 111     @Override
 112     public final Optional<StaleBestPathRoute<C, S, R, I>> removeStalePaths(final RIBSupport<C, S, R, I> ribSupport,
 113             final String routeKey) {
 114         final List<PathId> stalePaths;
 115         if (bestPathRemoved != null && !bestPathRemoved.isEmpty()) {
 116             stalePaths = bestPathRemoved.stream().map(AddPathBestPath::getPathId)
 117                     .map(AddPathAbstractRouteEntry::pathIdObj).collect(Collectors.toList());
 118             bestPathRemoved = null;
 119         } else {
 120             stalePaths = Collections.emptyList();
 121         }
 122
 123         List<PathId> removedPaths;
 124         if (removedPathsId != null) {
 125             removedPaths = Lists.transform(removedPathsId, AddPathAbstractRouteEntry::pathIdObj);
 126             this.removedPathsId = null;
 127         } else {
 128             removedPaths = Collections.emptyList();
 129         }
 130
 131         return stalePaths.isEmpty() && removedPaths.isEmpty() ? Optional.empty()
 132                 : Optional.of(new StaleBestPathRoute<>(ribSupport, routeKey, stalePaths,
 133                         removedPaths, this.isNonAddPathBestPathNew));
 134     }
 135
 136     @Override
 137     public final List<AdvertizedRoute<C, S, R, I>> newBestPaths(final RIBSupport<C, S, R, I> ribSupport,
 138             final String routeKey) {
 139         if (this.newBestPathToBeAdvertised == null || this.newBestPathToBeAdvertised.isEmpty()) {
 140             return Collections.emptyList();
 141         }
 142         final List<AdvertizedRoute<C, S, R, I>> advertized = new ArrayList<>(newBestPathToBeAdvertised.size());
 143         final AddPathBestPath firstBestPath = this.bestPath.isEmpty() ? null : this.bestPath.get(0);
 144         for (final AddPathBestPath path : this.newBestPathToBeAdvertised) {
 145             final R routeAddPath = createRoute(ribSupport, routeKey, path);
 146             // FIXME: can we use identity check here?
 147             final boolean isFirstBestPath = firstBestPath != null && firstBestPath.equals(path);
 148             final AdvertizedRoute<C, S, R, I> adv = new AdvertizedRoute<>(ribSupport, isFirstBestPath,
 149                     routeAddPath, path.getAttributes(), path.getPeerId(), path.isDepreferenced());
 150             advertized.add(adv);
 151         }
 152         this.newBestPathToBeAdvertised = null;
 153         return advertized;
 154     }
 155
 156     @Override
 157     public final List<ActualBestPathRoutes<C, S, R, I>> actualBestPaths(final RIBSupport<C, S, R, I> ribSupport,
 158             final RouteEntryInfo entryInfo) {
 159         if (this.bestPath == null || this.bestPath.isEmpty()) {
 160             return Collections.emptyList();
 161         }
 162         final List<ActualBestPathRoutes<C, S, R, I>> preexistentRoutes = new ArrayList<>();
 163         for (final AddPathBestPath path : this.bestPath) {
 164             final R route = createRoute(ribSupport, entryInfo.getRouteKey(), path);
 165             final ActualBestPathRoutes<C, S, R, I> adv = new ActualBestPathRoutes<>(ribSupport, route, path.getPeerId(),
 166                     path.getAttributes(), path.isDepreferenced());
 167             preexistentRoutes.add(adv);
 168         }
 169         return preexistentRoutes;
 170     }
 171
 172     @Override
 173     public final boolean selectBest(final long localAs) {
 174         final int size;
 175         return isBestPathNew((size = offsets.size()) == 0 ? ImmutableList.of() : selectBest(localAs, size));
 176     }
 177
 178     protected abstract ImmutableList<AddPathBestPath> selectBest(long localAs, int size);
 179
 180     /**
 181      * Process a specific route offset into specified selector.
 182      *
 183      * @param selector selector to update
 184      * @param offset offset to process
 185      */
 186     protected final void processOffset(final AddPathSelector selector, final int offset) {
 187         final RouteKey key = offsets.getKey(offset);
 188         final R route = offsets.getValue(values, offset);
 189         final Long pathId = offsets.getValue(pathsId, offset);
 190         LOG.trace("Processing router key {} route {}", key, route);
 191         selector.processPath(route.getAttributes(), key, offset, pathId);
 192     }
 193
 194     protected final AddPathBestPath bestPathAt(final int offset) {
 195         final Route route = verifyNotNull(offsets.getValue(values, offset));
 196         return new AddPathBestPath(new BestPathStateImpl(route.getAttributes()), offsets.getKey(offset),
 197             offsets.getValue(pathsId, offset), offset);
 198     }
 199
 200     private boolean isBestPathNew(final ImmutableList<AddPathBestPath> newBestPathList) {
 201         this.isNonAddPathBestPathNew = !isNonAddPathBestPathTheSame(newBestPathList);
 202         filterRemovedPaths(newBestPathList);
 203         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
 204                 || newBestPathList != null
 205                 && !newBestPathList.equals(this.bestPath)) {
 206             if (this.bestPath != null) {
 207                 this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
 208                 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
 209             } else {
 210                 this.newBestPathToBeAdvertised = newBestPathList;
 211             }
 212             this.bestPath = newBestPathList;
 213             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 214             return true;
 215         }
 216         return false;
 217     }
 218
 219     private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
 220         return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
 221                 && this.bestPath.get(0).equals(newBestPathList.get(0));
 222     }
 223
 224     private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
 225         return pathList == null || pathList.isEmpty();
 226     }
 227
 228     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 229         if (this.bestPath == null) {
 230             return;
 231         }
 232         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 233         this.bestPath.forEach(oldBest -> {
 234             final Optional<AddPathBestPath> present = newBestPathList.stream()
 235                     .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
 236                             && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 237             present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
 238         });
 239     }
 240
 241     private static PathId pathIdObj(final Long pathId) {
 242         return pathId == NON_PATH_ID_VALUE ? NON_PATH_ID : new PathId(pathId);
 243     }
 244 }