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