From 42e4512e5e9e3d125636332c1b3e0d8cb5f1e3e0 Mon Sep 17 00:00:00 2001 From: "Claudio D. Gasparini" Date: Thu, 4 Aug 2016 12:49:01 +0200 Subject: [PATCH] BUG-6237: Topology freezes or slows down due to java.util.concurrent.TimeoutException High consupmtion of memory is observed caused by high LoadingCache per OffsetMap instance. Fix by use -singleton empty constructor for LoadCache. -use null instead of optional Change-Id: Ia6edc0fc732ac286af4f3ef83d02add572fb5bf1 Signed-off-by: Claudio D. Gasparini --- .../impl/add/AddPathAbstractRouteEntry.java | 37 ++--- .../bgp/mode/impl/add/AddPathSelector.java | 2 +- .../bgp/mode/impl/{ => add}/OffsetMap.java | 79 +++++----- .../all/paths/AbstractAllPathsRouteEntry.java | 11 +- .../impl/add/all/paths/ComplexRouteEntry.java | 10 +- .../add/n/paths/AbstractNPathsRouteEntry.java | 7 +- .../impl/add/n/paths/ComplexRouteEntry.java | 10 +- .../impl/base/BaseAbstractRouteEntry.java | 32 ++-- .../mode/impl/base/BaseComplexRouteEntry.java | 9 +- .../bgp/mode/impl/base/OffsetMap.java | 139 ++++++++++++++++++ .../mode/impl/base/BaseRouteEntryTest.java | 2 +- 11 files changed, 236 insertions(+), 102 deletions(-) rename bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/{ => add}/OffsetMap.java (68%) create mode 100644 bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java index dd738f2a4c..0514ae23e6 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java @@ -7,15 +7,12 @@ */ package org.opendaylight.protocol.bgp.mode.impl.add; -import java.util.ArrayList; -import java.util.Collections; import java.util.List; import java.util.Map; import javax.annotation.concurrent.NotThreadSafe; import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType; import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction; import org.opendaylight.protocol.bgp.mode.api.BestPath; -import org.opendaylight.protocol.bgp.mode.impl.OffsetMap; import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry; import org.opendaylight.protocol.bgp.rib.spi.CacheDisconnectedPeers; import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker; @@ -46,9 +43,9 @@ import org.slf4j.LoggerFactory; public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry { private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class); - protected List bestPath = new ArrayList<>(); - protected List bestPathRemoved = new ArrayList<>(); - protected OffsetMap offsets = new OffsetMap<>(RouteKey.class); + protected List bestPath; + protected List bestPathRemoved; + protected OffsetMap offsets = OffsetMap.EMPTY; protected ContainerNode[] values = new ContainerNode[0]; protected Long[] pathsId = new Long[0]; private long pathIdCounter = 0L; @@ -56,7 +53,7 @@ public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry { private int addRoute(final RouteKey key, final ContainerNode attributes) { int offset = this.offsets.offsetOf(key); if (offset < 0) { - final OffsetMap newOffsets = this.offsets.with(key); + final OffsetMap newOffsets = this.offsets.with(key); offset = newOffsets.offsetOf(key); final ContainerNode[] newAttributes = newOffsets.expand(this.offsets, this.values, offset); final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset); @@ -93,12 +90,16 @@ public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry { @Override public void updateRoute(final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx, final PathArgument routeIdPA) { - this.bestPathRemoved.forEach(path -> removePathFromDataStore(path, isFirstBestPath(bestPathRemoved.indexOf(path)), routeIdPA, locRibTarget, ribSup, - peerPT, localTK, discPeers,tx)); - this.bestPathRemoved = Collections.emptyList(); + if(this.bestPathRemoved != null) { + this.bestPathRemoved.forEach(path -> removePathFromDataStore(path, isFirstBestPath(bestPathRemoved.indexOf(path)), routeIdPA, locRibTarget, ribSup, + peerPT, localTK, discPeers, tx)); + this.bestPathRemoved = null; + } - this.bestPath.forEach(path -> addPathToDataStore(path, isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA, locRibTarget, ribSup, - peerPT, localTK, discPeers,tx)); + if(this.bestPath != null) { + this.bestPath.forEach(path -> addPathToDataStore(path, isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA, locRibTarget, ribSup, + peerPT, localTK, discPeers, tx)); + } } @Override @@ -106,9 +107,11 @@ public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry { final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) { final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer); - this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers) && - peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath(this.bestPath.indexOf(path)))) - .forEach(path -> writeRoutePath(destPeer, routeId, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx)); + if(this.bestPath != null) { + this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers) && + peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath(this.bestPath.indexOf(path)))) + .forEach(path -> writeRoutePath(destPeer, routeId, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx)); + } } private void writeRoutePath(final PeerId destPeer, final PathArgument routeId, final PeerExportGroup peerGroup, final boolean destPeerSupAddPath, @@ -187,12 +190,12 @@ public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry { } } - protected final OffsetMap getOffsets() { + protected final OffsetMap getOffsets() { return this.offsets; } public final boolean isEmpty() { - return this.offsets.isEmty(); + return this.offsets.isEmpty(); } protected void selectBest(final RouteKey key, final AddPathSelector selector) { diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathSelector.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathSelector.java index 29e5b096d8..106c642cae 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathSelector.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathSelector.java @@ -27,7 +27,7 @@ public final class AddPathSelector extends AbstractBestPathSelector { super(ourAs); } - public void processPath(final ContainerNode attrs, final RouteKey key, final int offsetPosition, final Long pathId) { + void processPath(final ContainerNode attrs, final RouteKey key, final int offsetPosition, final Long pathId) { Preconditions.checkNotNull(key.getRouteId(), "Router ID may not be null"); // Consider only non-null attributes diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/OffsetMap.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java similarity index 68% rename from bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/OffsetMap.java rename to bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java index 9bb0ac6b95..28d2a6fda7 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/OffsetMap.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java @@ -5,7 +5,7 @@ * terms of the Eclipse Public License v1.0 which accompanies this distribution, * and is available at http://www.eclipse.org/legal/epl-v10.html */ -package org.opendaylight.protocol.bgp.mode.impl; +package org.opendaylight.protocol.bgp.mode.impl.add; import com.google.common.base.Preconditions; import com.google.common.cache.CacheBuilder; @@ -15,6 +15,7 @@ import com.google.common.collect.ImmutableSet; import com.google.common.collect.ImmutableSet.Builder; import java.lang.reflect.Array; import java.util.Arrays; +import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Set; @@ -30,73 +31,59 @@ import org.slf4j.LoggerFactory; * We also provide utility reformat methods, which provide access to * array members and array management features. */ -public final class OffsetMap> { +public final class OffsetMap { + static final OffsetMap EMPTY = new OffsetMap(Collections.emptySet()); private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class); private static final String NEGATIVEOFFSET = "Invalid negative offset %s"; private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs"; - private final Comparator ipv4Comparator = E::compareTo; - private final E[] routeKeys; - private final Class clazz; - private final LoadingCache, OffsetMap> keyCache = CacheBuilder.newBuilder().weakValues().build(new CacheLoader, OffsetMap>() { - @Override - public OffsetMap load(@Nonnull final Set key) throws Exception { - return new OffsetMap<>(key, clazz); - } - }); - - public OffsetMap(final Class clazz) { - this.clazz = clazz; - this.routeKeys = (E[]) Array.newInstance(clazz, 0); - } + private static final LoadingCache, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues().build( + new CacheLoader, OffsetMap>() { + @Override + public OffsetMap load(@Nonnull final Set key) throws Exception { + return new OffsetMap(key); + } + }); + private static final Comparator COMPARATOR = RouteKey::compareTo; + private final RouteKey[] routeKeys; - private OffsetMap(final Set keysSet, final Class clazz) { - this.clazz = clazz; - final E[] array = keysSet.toArray((E[]) Array.newInstance(this.clazz, keysSet.size())); - Arrays.sort(array, ipv4Comparator); + private OffsetMap(final Set routerIds) { + final RouteKey[] array = routerIds.toArray(new RouteKey[0]); + Arrays.sort(array, COMPARATOR); this.routeKeys = array; } - public List getRouteKeysList() { - return Arrays.stream(this.routeKeys).collect(Collectors.toList()); - } - - public E getRouterKey(final int offset) { - Preconditions.checkArgument(offset >= 0); - return this.routeKeys[offset]; - } - - public int offsetOf(final E key) { - return Arrays.binarySearch(this.routeKeys, key, ipv4Comparator); + public int offsetOf(final RouteKey key) { + return Arrays.binarySearch(this.routeKeys, key, COMPARATOR); } public int size() { return this.routeKeys.length; } - public OffsetMap with(final E key) { + public OffsetMap with(final RouteKey key) { // TODO: we could make this faster if we had an array-backed Set and requiring // the caller to give us the result of offsetOf() -- as that indicates // where to insert the new routerId while maintaining the sorted nature // of the array - final Builder b = ImmutableSet.builder(); - b.add(this.routeKeys); - b.add(key); + final Builder builder = ImmutableSet.builder(); + builder.add(this.routeKeys); + builder.add(key); - return keyCache.getUnchecked(b.build()); + return OFFSETMAPS.getUnchecked(builder.build()); } - public OffsetMap without(final E key) { - final Builder b = ImmutableSet.builder(); - int index = indexOfRouterId(key); + public OffsetMap without(final RouteKey key) { + final Builder builder = ImmutableSet.builder(); + final int index = indexOfRouterId(key); if (index < 0) { LOG.trace("Router key not found", key); } else { - b.add(removeValue(this.routeKeys, index)); + builder.add(removeValue(this.routeKeys, index)); } - return keyCache.getUnchecked(b.build()); + return OFFSETMAPS.getUnchecked(builder.build()); } - private int indexOfRouterId(final E key) { + private int indexOfRouterId(final RouteKey key) { for (int i = 0; i < this.routeKeys.length; i++) { if (key.equals(this.routeKeys[i])) { return i; @@ -142,7 +129,11 @@ public final class OffsetMap> { return ret; } - public boolean isEmty() { + boolean isEmpty() { return this.size() == 0; } -} + + public List getRouteKeysList() { + return Arrays.stream(this.routeKeys).collect(Collectors.toList()); + } +} \ No newline at end of file diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AbstractAllPathsRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AbstractAllPathsRouteEntry.java index 0378ff2430..cc815b1649 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AbstractAllPathsRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AbstractAllPathsRouteEntry.java @@ -34,7 +34,7 @@ abstract class AbstractAllPathsRouteEntry extends AddPathAbstractRouteEntry { newBestPathList.add(newBest); keyList.remove(newBest.getRouteKey()); /*we add the rest of path, regardless in what order they are, since this is all path case */ - for (RouteKey key : keyList) { + for (final RouteKey key : keyList) { final int offset = this.offsets.offsetOf(key); final ContainerNode attributes = this.offsets.getValue(this.values, offset); Preconditions.checkNotNull(key.getRouteId(), "Router ID may not be null"); @@ -46,14 +46,15 @@ abstract class AbstractAllPathsRouteEntry extends AddPathAbstractRouteEntry { } } - this.bestPathRemoved = new ArrayList<>(this.bestPath); - if (this.bestPathRemoved.removeAll(newBestPathList) && !this.bestPathRemoved.isEmpty() || !this.bestPath.equals(newBestPathList)) { + if(this.bestPath != null) { + this.bestPathRemoved = new ArrayList<>(this.bestPath); + } + + if (!newBestPathList.equals(this.bestPath) || this.bestPathRemoved != null && this.bestPathRemoved.removeAll(newBestPathList)) { this.bestPath = newBestPathList; LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved); return true; } return false; } - - } diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/ComplexRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/ComplexRouteEntry.java index e38bc8cff7..2ec4f43a90 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/ComplexRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/ComplexRouteEntry.java @@ -10,8 +10,8 @@ package org.opendaylight.protocol.bgp.mode.impl.add.all.paths; import com.google.common.primitives.UnsignedInteger; import org.opendaylight.protocol.bgp.mode.api.BestPath; -import org.opendaylight.protocol.bgp.mode.impl.OffsetMap; import org.opendaylight.protocol.bgp.mode.impl.add.AddPathBestPath; +import org.opendaylight.protocol.bgp.mode.impl.add.OffsetMap; import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey; import org.opendaylight.protocol.bgp.mode.spi.RouteEntryUtil; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; @@ -25,7 +25,7 @@ final class ComplexRouteEntry extends AbstractAllPathsRouteEntry { @Override public boolean removeRoute(final UnsignedInteger routerId, final Long remotePathId) { final RouteKey key = new RouteKey(routerId, remotePathId); - final OffsetMap map = getOffsets(); + final OffsetMap map = getOffsets(); final int offset = map.offsetOf(key); this.values = map.removeValue(this.values, offset); return removeRoute(key, offset); @@ -33,16 +33,16 @@ final class ComplexRouteEntry extends AbstractAllPathsRouteEntry { @Override public MapEntryNode createValue(final YangInstanceIdentifier.PathArgument routeId, final BestPath path) { - final OffsetMap map = getOffsets(); + final OffsetMap map = getOffsets(); final MapEntryNode mapValues = map.getValue(this.values, map.offsetOf(((AddPathBestPath) path).getRouteKey())); return RouteEntryUtil.createComplexRouteValue(routeId, path, mapValues); } @Override public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final YangInstanceIdentifier.NodeIdentifier attII, final NormalizedNode data) { - final OffsetMap oldMap = getOffsets(); + final OffsetMap oldMap = getOffsets(); final int offset = addRoute(new RouteKey(routerId, remotePathId), attII, data); - final OffsetMap newMap = getOffsets(); + final OffsetMap newMap = getOffsets(); if (!newMap.equals(oldMap)) { this.values = newMap.expand(oldMap, this.values, offset); diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AbstractNPathsRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AbstractNPathsRouteEntry.java index 05cd878d12..f95abcd586 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AbstractNPathsRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AbstractNPathsRouteEntry.java @@ -36,8 +36,11 @@ abstract class AbstractNPathsRouteEntry extends AddPathAbstractRouteEntry { keyList.remove(newBest.getRouteKey()); } - this.bestPathRemoved = new ArrayList<>(this.bestPath); - if (this.bestPathRemoved.removeAll(newBestPathList) && !this.bestPathRemoved.isEmpty() || !this.bestPath.equals(newBestPathList)) { + if(this.bestPath != null) { + this.bestPathRemoved = new ArrayList<>(this.bestPath); + } + if (!newBestPathList.equals(this.bestPath) || + this.bestPathRemoved != null && this.bestPathRemoved.removeAll(newBestPathList) && !this.bestPathRemoved.isEmpty()) { this.bestPath = newBestPathList; LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved); return true; diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/ComplexRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/ComplexRouteEntry.java index 9598a7de65..3d7b7abf4f 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/ComplexRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/ComplexRouteEntry.java @@ -9,8 +9,8 @@ package org.opendaylight.protocol.bgp.mode.impl.add.n.paths; import com.google.common.primitives.UnsignedInteger; import org.opendaylight.protocol.bgp.mode.api.BestPath; -import org.opendaylight.protocol.bgp.mode.impl.OffsetMap; import org.opendaylight.protocol.bgp.mode.impl.add.AddPathBestPath; +import org.opendaylight.protocol.bgp.mode.impl.add.OffsetMap; import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey; import org.opendaylight.protocol.bgp.mode.spi.RouteEntryUtil; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier; @@ -29,7 +29,7 @@ final class ComplexRouteEntry extends AbstractNPathsRouteEntry { @Override public boolean removeRoute(final UnsignedInteger routerId, final Long remotePathId) { final RouteKey key = new RouteKey(routerId, remotePathId); - final OffsetMap map = getOffsets(); + final OffsetMap map = getOffsets(); final int offset = map.offsetOf(key); this.values = map.removeValue(this.values, offset); return removeRoute(key, offset); @@ -37,16 +37,16 @@ final class ComplexRouteEntry extends AbstractNPathsRouteEntry { @Override public MapEntryNode createValue(final PathArgument routeId, final BestPath path) { - final OffsetMap map = getOffsets(); + final OffsetMap map = getOffsets(); final MapEntryNode mapValues = map.getValue(this.values, map.offsetOf(((AddPathBestPath) path).getRouteKey())); return RouteEntryUtil.createComplexRouteValue(routeId, path, mapValues); } @Override public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final NodeIdentifier attributesIdentifier, final NormalizedNode data) { - final OffsetMap oldMap = getOffsets(); + final OffsetMap oldMap = getOffsets(); final int offset = addRoute(new RouteKey(routerId, remotePathId), attributesIdentifier, data); - final OffsetMap newMap = getOffsets(); + final OffsetMap newMap = getOffsets(); if (!newMap.equals(oldMap)) { this.values = newMap.expand(oldMap, this.values, offset); diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseAbstractRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseAbstractRouteEntry.java index 18ee1ed3c4..f8fc1cc867 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseAbstractRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseAbstractRouteEntry.java @@ -14,7 +14,6 @@ import javax.annotation.concurrent.NotThreadSafe; import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType; import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction; import org.opendaylight.protocol.bgp.mode.api.BestPath; -import org.opendaylight.protocol.bgp.mode.impl.OffsetMap; import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry; import org.opendaylight.protocol.bgp.rib.spi.CacheDisconnectedPeers; import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker; @@ -34,18 +33,17 @@ import org.slf4j.LoggerFactory; @NotThreadSafe abstract class BaseAbstractRouteEntry extends AbstractRouteEntry { - private static final Logger LOG = LoggerFactory.getLogger(BaseAbstractRouteEntry.class); private static final ContainerNode[] EMPTY_ATTRIBUTES = new ContainerNode[0]; - private OffsetMap offsets = new OffsetMap<>(UnsignedInteger.class); + private OffsetMap offsets = OffsetMap.EMPTY; private ContainerNode[] values = EMPTY_ATTRIBUTES; - private Optional bestPath = Optional.empty(); - private Optional removedBestPath = Optional.empty(); + private BaseBestPath bestPath; + private BaseBestPath removedBestPath; private int addRoute(final UnsignedInteger routerId, final ContainerNode attributes) { int offset = this.offsets.offsetOf(routerId); if (offset < 0) { - final OffsetMap newOffsets = this.offsets.with(routerId); + final OffsetMap newOffsets = this.offsets.with(routerId); offset = newOffsets.offsetOf(routerId); this.values = newOffsets.expand(this.offsets, this.values, offset); @@ -67,7 +65,7 @@ abstract class BaseAbstractRouteEntry extends AbstractRouteEntry { protected final boolean removeRoute(final UnsignedInteger routerId, final int offset) { this.values = this.offsets.removeValue(this.values, offset); this.offsets = this.offsets.without(routerId); - return this.offsets.isEmty(); + return this.offsets.isEmpty(); } @Override @@ -86,8 +84,8 @@ abstract class BaseAbstractRouteEntry extends AbstractRouteEntry { } // Get the newly-selected best path. - final Optional newBestPath = Optional.ofNullable(selector.result()); - final boolean modified = !newBestPath.equals(this.bestPath); + final BaseBestPath newBestPath = selector.result(); + final boolean modified = newBestPath == null || !newBestPath.equals(this.bestPath); if (modified) { this.removedBestPath = this.bestPath; LOG.trace("Previous best {}, current best {}", this.bestPath, newBestPath); @@ -106,12 +104,12 @@ abstract class BaseAbstractRouteEntry extends AbstractRouteEntry { @Override public void updateRoute(final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx, final PathArgument routeIdPA) { - if (this.removedBestPath.isPresent()) { - removePathFromDataStore(this.removedBestPath.get(), routeIdPA, locRibTarget, peerPT, localTK, ribSup, discPeers, tx); - this.removedBestPath = Optional.empty(); + if (this.removedBestPath != null) { + removePathFromDataStore(this.removedBestPath, routeIdPA, locRibTarget, peerPT, localTK, ribSup, discPeers, tx); + this.removedBestPath = null; } - if (this.bestPath.isPresent()) { - addPathToDataStore(this.bestPath.get(), routeIdPA, locRibTarget, ribSup, peerPT, localTK, discPeers, tx); + if (this.bestPath != null) { + addPathToDataStore(this.bestPath, routeIdPA, locRibTarget, ribSup, peerPT, localTK, discPeers, tx); } } @@ -119,8 +117,8 @@ abstract class BaseAbstractRouteEntry extends AbstractRouteEntry { public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath, final PeerExportGroup peerGroup, final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) { - if (this.bestPath.isPresent()) { - final BaseBestPath path = this.bestPath.get(); + if (this.bestPath != null) { + final BaseBestPath path = this.bestPath; if (filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers)) { final ContainerNode effAttrib = peerGroup.effectiveAttributes(path.getPeerId(), path.getAttributes()); writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effAttrib, createValue(routeId, path), ribSup, tx); @@ -161,7 +159,7 @@ abstract class BaseAbstractRouteEntry extends AbstractRouteEntry { fillAdjRibsOut(path.getAttributes(), value, routeIdPA, path.getPeerId(), peerPT, localTK, ribSup, discPeers, tx); } - protected final OffsetMap getOffsets() { + final OffsetMap getOffsets() { return this.offsets; } diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseComplexRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseComplexRouteEntry.java index 9dd20a71a9..04c22444aa 100644 --- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseComplexRouteEntry.java +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseComplexRouteEntry.java @@ -9,7 +9,6 @@ package org.opendaylight.protocol.bgp.mode.impl.base; import com.google.common.primitives.UnsignedInteger; import org.opendaylight.protocol.bgp.mode.api.BestPath; -import org.opendaylight.protocol.bgp.mode.impl.OffsetMap; import org.opendaylight.protocol.bgp.mode.spi.RouteEntryUtil; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier; import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument; @@ -22,9 +21,9 @@ final class BaseComplexRouteEntry extends BaseAbstractRouteEntry { @Override public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final NodeIdentifier attrII, final NormalizedNode data) { - final OffsetMap oldMap = getOffsets(); + final OffsetMap oldMap = getOffsets(); final int offset = super.addRoute(routerId, remotePathId, attrII, data); - final OffsetMap newMap = getOffsets(); + final OffsetMap newMap = getOffsets(); if (!newMap.equals(oldMap)) { this.values = newMap.expand(oldMap, this.values, offset); @@ -36,7 +35,7 @@ final class BaseComplexRouteEntry extends BaseAbstractRouteEntry { @Override public boolean removeRoute(final UnsignedInteger routerId, final Long remotePathId) { - final OffsetMap map = getOffsets(); + final OffsetMap map = getOffsets(); final int offset = map.offsetOf(routerId); this.values = map.removeValue(this.values, offset); return removeRoute(routerId, offset); @@ -44,7 +43,7 @@ final class BaseComplexRouteEntry extends BaseAbstractRouteEntry { @Override public MapEntryNode createValue(final PathArgument routeId, final BestPath path) { - final OffsetMap map = getOffsets(); + final OffsetMap map = getOffsets(); final MapEntryNode mapValues = map.getValue(this.values, map.offsetOf(path.getRouterId())); return RouteEntryUtil.createComplexRouteValue(routeId, path, mapValues); } diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java new file mode 100644 index 0000000000..63e8b7cee2 --- /dev/null +++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/base/OffsetMap.java @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.protocol.bgp.mode.impl.base; + +import com.google.common.base.Preconditions; +import com.google.common.cache.CacheBuilder; +import com.google.common.cache.CacheLoader; +import com.google.common.cache.LoadingCache; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.ImmutableSet.Builder; +import com.google.common.primitives.UnsignedInteger; +import java.lang.reflect.Array; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; +import java.util.Set; +import javax.annotation.Nonnull; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * A map of Router identifier to an offset. Used to maintain a simple + * offset-based lookup across multiple RouteEntry objects, + * which share either contributors or consumers. + * We also provide utility reformat methods, which provide access to + * array members and array management features. + */ +final class OffsetMap { + static final OffsetMap EMPTY = new OffsetMap(Collections.emptySet()); + private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class); + private static final String NEGATIVEOFFSET = "Invalid negative offset %s"; + private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs"; + private static final LoadingCache, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues().build( + new CacheLoader, OffsetMap>() { + @Override + public OffsetMap load(@Nonnull final Set key) throws Exception { + return new OffsetMap(key); + } + }); + private static final Comparator COMPARATOR = UnsignedInteger::compareTo; + private final UnsignedInteger[] routeKeys; + + private OffsetMap(final Set routerIds) { + final UnsignedInteger[] array = routerIds.toArray(new UnsignedInteger[0]); + Arrays.sort(array, COMPARATOR); + this.routeKeys = array; + } + + UnsignedInteger getRouterKey(final int offset) { + Preconditions.checkArgument(offset >= 0); + return this.routeKeys[offset]; + } + + public int offsetOf(final UnsignedInteger key) { + return Arrays.binarySearch(this.routeKeys, key, COMPARATOR); + } + + public int size() { + return this.routeKeys.length; + } + + public OffsetMap with(final UnsignedInteger key) { + // TODO: we could make this faster if we had an array-backed Set and requiring + // the caller to give us the result of offsetOf() -- as that indicates + // where to insert the new routerId while maintaining the sorted nature + // of the array + final Builder builder = ImmutableSet.builder(); + builder.add(this.routeKeys); + builder.add(key); + + return OFFSETMAPS.getUnchecked(builder.build()); + } + + public OffsetMap without(final UnsignedInteger key) { + final Builder builder = ImmutableSet.builder(); + final int index = indexOfRouterId(key); + if (index < 0) { + LOG.trace("Router key not found", key); + } else { + builder.add(removeValue(this.routeKeys, index)); + } + return OFFSETMAPS.getUnchecked(builder.build()); + } + + private int indexOfRouterId(final UnsignedInteger key) { + for (int i = 0; i < this.routeKeys.length; i++) { + if (key.equals(this.routeKeys[i])) { + return i; + } + } + return -1; + } + + public T getValue(final T[] array, final int offset) { + Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset); + Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, routeKeys.length); + return array[offset]; + } + + public void setValue(final T[] array, final int offset, final T value) { + Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset); + Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, routeKeys.length); + array[offset] = value; + } + + T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) { + @SuppressWarnings("unchecked") + final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length); + final int oldSize = oldOffsets.routeKeys.length; + + System.arraycopy(oldArray, 0, ret, 0, offset); + System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset); + + return ret; + } + + public T[] removeValue(final T[] oldArray, final int offset) { + final int length = oldArray.length; + Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset); + Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, length); + + final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), length - 1); + System.arraycopy(oldArray, 0, ret, 0, offset); + if (offset < length - 1) { + System.arraycopy(oldArray, offset + 1, ret, offset, length - offset - 1); + } + + return ret; + } + + boolean isEmpty() { + return this.size() == 0; + } +} \ No newline at end of file diff --git a/bgp/path-selection-mode/src/test/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntryTest.java b/bgp/path-selection-mode/src/test/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntryTest.java index 63ffc2e16b..a297a4dc45 100644 --- a/bgp/path-selection-mode/src/test/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntryTest.java +++ b/bgp/path-selection-mode/src/test/java/org/opendaylight/protocol/bgp/mode/impl/base/BaseRouteEntryTest.java @@ -67,7 +67,7 @@ public class BaseRouteEntryTest extends AbstractRouteEntryTest { private void testAddRouteSelectBestAndWriteOnDS() { this.testBARE.addRoute(ROUTER_ID, REMOTE_PATH_ID, this.ribSupport.routeAttributesIdentifier(), this.attributes); - assertFalse(this.testBARE.getOffsets().isEmty()); + assertFalse(this.testBARE.getOffsets().isEmpty()); this.testBARE.selectBest(AS); this.testBARE.updateRoute(TABLES_KEY, this.peerPT, LOC_RIB_TARGET, this.ribSupport, this.discCache, this.tx, ROUTE_ID_PA); Map yiiCount = this.yIIChanges.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); -- 2.36.6