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