From 5d0eed4dade2350534ad190244baf0ed7bafedbc Mon Sep 17 00:00:00 2001 From: Lorand Jakab Date: Tue, 12 Sep 2017 20:41:01 +0300 Subject: [PATCH] Bug 9116: SMR children of a prefix too JIRA: LISPMAP-165 Change-Id: I99800a800cef37a5d9cd1b33fe2e13a6d1ca1f5d Signed-off-by: Lorand Jakab --- .../MappingServiceIntegrationTest.java | 48 ++++++- .../interfaces/dao/ILispDAO.java | 10 ++ .../interfaces/mapcache/ILispMapCache.java | 10 ++ .../interfaces/mapcache/IMappingSystem.java | 23 +++ .../mappingservice/IMappingService.java | 11 ++ .../api/src/main/yang/odl-mappingservice.yang | 1 + .../implementation/MappingService.java | 5 + .../implementation/MappingSystem.java | 136 +++++++++++++++--- .../implementation/lisp/MapServer.java | 5 +- .../mdsal/MappingDataListener.java | 44 ++---- .../util/MSNotificationInputUtil.java | 20 +-- .../mdsal/MappingDataListenerTest.java | 16 +-- .../lispflowmapping/inmemorydb/HashMapDb.java | 20 ++- .../inmemorydb/radixtrie/RadixTrie.java | 134 ++++++++++------- .../lisp/util/LispAddressStringifier.java | 28 +++- .../mapcache/SimpleMapCache.java | 9 ++ 16 files changed, 384 insertions(+), 136 deletions(-) diff --git a/integrationtest/src/test/java/org/opendaylight/lispflowmapping/integrationtest/MappingServiceIntegrationTest.java b/integrationtest/src/test/java/org/opendaylight/lispflowmapping/integrationtest/MappingServiceIntegrationTest.java index 2c1c8d806..629a4299c 100644 --- a/integrationtest/src/test/java/org/opendaylight/lispflowmapping/integrationtest/MappingServiceIntegrationTest.java +++ b/integrationtest/src/test/java/org/opendaylight/lispflowmapping/integrationtest/MappingServiceIntegrationTest.java @@ -43,6 +43,7 @@ import java.net.UnknownHostException; import java.nio.ByteBuffer; import java.util.ArrayList; import java.util.Arrays; +import java.util.HashSet; import java.util.List; import java.util.Set; import javax.inject.Inject; @@ -425,7 +426,15 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { testPositiveMappingRemoval(); // https://bugs.opendaylight.org/show_bug.cgi?id=9037 - testPositivePrefixOverlappingNegativePrefix(); + testPositivePrefixOverlappingNegativePrefix_moreSpecific(); + + // https://bugs.opendaylight.org/show_bug.cgi?id=9116 + testPositivePrefixOverlappingNegativePrefix_lessSpecific(); + } + + @Test + public void testMappingChangeCases() { + testSubtree(); } private void testRepeatedSmr() throws SocketTimeoutException, UnknownHostException { @@ -660,7 +669,7 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { printMapCacheState(); } - private void testPositivePrefixOverlappingNegativePrefix() { + private void testPositivePrefixOverlappingNegativePrefix_moreSpecific() { cleanUP(); insertNBMappings(1L, "192.167.0.0/16", "192.169.0.0/16"); @@ -680,6 +689,41 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { assertTrue(MappingRecordUtil.isNegativeMapping(mr)); } + private void testPositivePrefixOverlappingNegativePrefix_lessSpecific() { + cleanUP(); + + insertNBMappings(1L, "192.167.0.0/16", "192.169.0.0/16"); + + MapReply mapReply = lms.handleMapRequest(newMapRequest(1L, "192.168.0.1/32")); + Eid expectedNegativePrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "192.168.0.0/16"); + MappingRecord mr = mapReply.getMappingRecordItem().get(0).getMappingRecord(); + assertEquals(expectedNegativePrefix, mr.getEid()); + assertTrue(MappingRecordUtil.isNegativeMapping(mr)); + + insertNBMappings(1L, "192.0.0.0/8"); + + mapReply = lms.handleMapRequest(newMapRequest(1L, "192.168.0.1/32")); + Eid expectedPositivePrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "192.0.0.0/8"); + mr = mapReply.getMappingRecordItem().get(0).getMappingRecord(); + assertEquals(expectedPositivePrefix, mr.getEid()); + assertTrue(MappingRecordUtil.isPositiveMapping(mr)); + } + + private void testSubtree() { + cleanUP(); + + insertSBMappings(1L, "10.0.0.0/8", + "10.0.0.0/16", "10.2.0.0/16", "10.255.0.0/16"); + Eid queryPrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "10.0.0.0/9"); + Set subtreePrefixes = mapService.getSubtree(MappingOrigin.Southbound, queryPrefix); + LOG.debug("Subtree prefix set for EID {}: {}", LispAddressStringifier.getString(queryPrefix), + LispAddressStringifier.getString(subtreePrefixes)); + Set expectedSubtreePrefixes = new HashSet<>(); + expectedSubtreePrefixes.add(LispAddressUtil.asIpv4PrefixBinaryEid(1L, "10.0.0.0/16")); + expectedSubtreePrefixes.add(LispAddressUtil.asIpv4PrefixBinaryEid(1L, "10.2.0.0/16")); + assertEquals(expectedSubtreePrefixes, subtreePrefixes); + } + private void insertMappings() { cleanUP(); mapService.setLookupPolicy(IMappingService.LookupPolicy.NB_AND_SB); diff --git a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/dao/ILispDAO.java b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/dao/ILispDAO.java index 65a4e748b..203d6ab05 100644 --- a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/dao/ILispDAO.java +++ b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/dao/ILispDAO.java @@ -64,6 +64,16 @@ public interface ILispDAO { */ SimpleImmutableEntry> getBestPair(Object key); + /** + * Look up the covering prefix for the argument, but exclude the argument itself, so the result is always less + * specific than the lookup key. + * + * @param key + * The eid prefix, IPv4 or IPv6, to be looked up. Key must be normalized. + * @return The covering prefix. + */ + Eid getCoveringLessSpecific(Eid key); + /** * Get parent prefix. * diff --git a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/ILispMapCache.java b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/ILispMapCache.java index 0a745dfeb..68e5c003f 100644 --- a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/ILispMapCache.java +++ b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/ILispMapCache.java @@ -89,6 +89,16 @@ public interface ILispMapCache extends IMapCache { */ void removeXtrIdMappings(Eid key, List xtrIds); + /** + * Look up the covering prefix for the argument, but exclude the argument itself, so the result is always less + * specific than the lookup key. + * + * @param key + * The eid prefix, IPv4 or IPv6, to be looked up. Key must be normalized. + * @return The covering prefix. + */ + Eid getCoveringLessSpecific(Eid key); + /** * Returns the parent prefix for given key. * diff --git a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/IMappingSystem.java b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/IMappingSystem.java index db7a9809b..613b75fb3 100644 --- a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/IMappingSystem.java +++ b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mapcache/IMappingSystem.java @@ -45,6 +45,18 @@ public interface IMappingSystem { */ MappingData addNegativeMapping(Eid key); + /** + * Update mapping. + * + * @param origin + * Table where mapping should be added + * @param key + * Key of the mapping + * @param mapping + * Mapping to be stored + */ + void updateMapping(MappingOrigin origin, Eid key, MappingData mapping); + /** * Retrieves mapping for the provided src and dst key. * @@ -98,6 +110,17 @@ public interface IMappingSystem { */ Eid getWidestNegativePrefix(Eid key); + /** + * Retrieves the subtree of a maskable prefix from the given map-cache. + * + * @param origin + * Table where the key should be looked up + * @param key + * Key to be looked up + * @return The child prefixes of the prefix, including the prefix itself if present + */ + Set getSubtree(MappingOrigin origin, Eid key); + /** * Refresh southbound mapping registration timestamp. * diff --git a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mappingservice/IMappingService.java b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mappingservice/IMappingService.java index e3bf81e4c..7891d6e70 100644 --- a/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mappingservice/IMappingService.java +++ b/mappingservice/api/src/main/java/org/opendaylight/lispflowmapping/interfaces/mappingservice/IMappingService.java @@ -94,6 +94,17 @@ public interface IMappingService { */ Eid getWidestNegativePrefix(Eid key); + /** + * Retrieves the subtree of a maskable prefix from the given map-cache. + * + * @param origin + * Table where the key should be looked up + * @param key + * Key to be looked up + * @return The child prefixes of the prefix, including the prefix itself if present + */ + Set getSubtree(MappingOrigin origin, Eid key); + /** * Refresh southbound mapping registration timestamp. * diff --git a/mappingservice/api/src/main/yang/odl-mappingservice.yang b/mappingservice/api/src/main/yang/odl-mappingservice.yang index ced643a45..9c70b0dc2 100644 --- a/mappingservice/api/src/main/yang/odl-mappingservice.yang +++ b/mappingservice/api/src/main/yang/odl-mappingservice.yang @@ -294,6 +294,7 @@ module odl-mappingservice { type mapping-change; } uses lisp-proto:mapping-record-container; + uses lisp-proto:eid-container; list subscriber-item { description "The list of subscribers to be notified of this change."; uses lisp-proto:subscriber-data-grouping; diff --git a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingService.java b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingService.java index 4bcbcd4e0..e7493eea6 100644 --- a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingService.java +++ b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingService.java @@ -456,6 +456,11 @@ public class MappingService implements OdlMappingserviceService, IMappingService return mappingSystem.getWidestNegativePrefix(key); } + @Override + public Set getSubtree(MappingOrigin origin, Eid key) { + return mappingSystem.getSubtree(origin, key); + } + @Override public void addAuthenticationKey(Eid key, MappingAuthkey authKey) { dsbe.addAuthenticationKey(DSBEInputUtil.toAuthenticationKey(key, authKey)); diff --git a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingSystem.java b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingSystem.java index ba2e12517..14762a0e2 100644 --- a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingSystem.java +++ b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingSystem.java @@ -10,6 +10,7 @@ package org.opendaylight.lispflowmapping.implementation; import com.google.common.collect.Sets; import java.util.ArrayList; +import java.util.Collections; import java.util.Date; import java.util.EnumMap; import java.util.HashMap; @@ -67,7 +68,6 @@ import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.ma import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecordBuilder; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.rloc.container.Rloc; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChange; -import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChanged; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingOrigin; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.db.instance.AuthenticationKey; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.db.instance.Mapping; @@ -147,7 +147,17 @@ public class MappingSystem implements IMappingSystem { tableMap.put(MappingOrigin.Southbound, smc); } + @Override + public void updateMapping(MappingOrigin origin, Eid key, MappingData mappingData) { + addMapping(origin, key, mappingData, MappingChange.Updated); + } + + @Override public void addMapping(MappingOrigin origin, Eid key, MappingData mappingData) { + addMapping(origin, key, mappingData, MappingChange.Created); + } + + private void addMapping(MappingOrigin origin, Eid key, MappingData mappingData, MappingChange changeType) { sbMappingTimeoutService.removeExpiredMappings(); @@ -177,9 +187,11 @@ public class MappingSystem implements IMappingSystem { tableMap.get(origin).addMapping(key, mappingData); - // We store explicit negative mappings in SB. That may cause issues, see bug 9037 for details if (origin != MappingOrigin.Southbound) { + // If a NB mapping is added, we need to check if it's covering negative mappings in SB, and remove those handleSbNegativeMappings(key); + // Notifications for SB changes are sent in the SB code itself, so this is called for non-SB additions only + notifyChange(key, mappingData.getRecord(), changeType); } } @@ -211,6 +223,31 @@ public class MappingSystem implements IMappingSystem { } private void handleSbNegativeMappings(Eid key) { + Set childPrefixes = getSubtree(MappingOrigin.Southbound, key); + + // We don't want to remove a newly added negative mapping, so remove it from the child set + childPrefixes.remove(key); + + LOG.trace("handleSbNegativeMappings(): subtree prefix set for EID {} (excluding the EID itself): {}", + LispAddressStringifier.getString(key), + LispAddressStringifier.getString(childPrefixes)); + if (childPrefixes == null || childPrefixes.isEmpty()) { + // The assumption here is that negative prefixes are well maintained and never overlapping. + // If we have children for the EID, no parent lookup should thus be necessary. + Eid parentPrefix = smc.getCoveringLessSpecific(key); + LOG.trace("handleSbNegativeMappings(): parent prefix for EID {}: {}", + LispAddressStringifier.getString(key), + LispAddressStringifier.getString(parentPrefix)); + handleSbNegativeMapping(parentPrefix); + return; + } + + for (Eid prefix : childPrefixes) { + handleSbNegativeMapping(prefix); + } + } + + private void handleSbNegativeMapping(Eid key) { MappingData mappingData = getSbMappingWithExpiration(null, key, null); if (mappingData != null && mappingData.isNegative().or(false)) { removeSbMapping(mappingData.getRecord().getEid(), mappingData); @@ -221,7 +258,7 @@ public class MappingSystem implements IMappingSystem { public MappingData addNegativeMapping(Eid key) { MappingRecord mapping = buildNegativeMapping(key); MappingData mappingData = new MappingData(mapping); - LOG.debug("Adding negative mapping for EID {}", LispAddressStringifier.getString(key)); + LOG.debug("Adding negative mapping for EID {}", LispAddressStringifier.getString(mapping.getEid())); LOG.trace(mappingData.getString()); smc.addMapping(mapping.getEid(), mappingData); dsbe.addMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, mapping.getEid(), null, mappingData)); @@ -446,8 +483,8 @@ public class MappingSystem implements IMappingSystem { Set subscribers = getSubscribers(key); smc.removeMapping(key); dsbe.removeMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, key, mappingData)); - notifyChange(mappingData, subscribers, null, MappingChange.Removed); - removeSubscribers(key); + publishNotification(mappingData.getRecord(), null, subscribers, null, MappingChange.Removed); + removeSubscribersConditionally(MappingOrigin.Southbound, key); } private void removeFromSbTimeoutService(Eid key) { @@ -492,8 +529,19 @@ public class MappingSystem implements IMappingSystem { } } + @Override + public Set getSubtree(MappingOrigin origin, Eid key) { + if (!MaskUtil.isMaskable(key.getAddress())) { + LOG.warn("Child prefixes only make sense for maskable addresses!"); + return Collections.emptySet(); + } + + return tableMap.get(origin).getSubtree(key); + } + @Override public void removeMapping(MappingOrigin origin, Eid key) { + Eid dstAddr = null; Set subscribers = null; Set dstSubscribers = null; MappingData mapping = (MappingData) tableMap.get(origin).getMapping(null, key); @@ -506,21 +554,19 @@ public class MappingSystem implements IMappingSystem { LOG.trace(mapping.getString()); } - MappingData notificationMapping = mapping; + MappingRecord notificationMapping = null; if (mapping != null) { + notificationMapping = mapping.getRecord(); subscribers = getSubscribers(key); // For SrcDst LCAF also send SMRs to Dst prefix if (key.getAddress() instanceof SourceDestKey) { - Eid dstAddr = SourceDestKeyHelper.getDstBinary(key); + dstAddr = SourceDestKeyHelper.getDstBinary(key); dstSubscribers = getSubscribers(dstAddr); - if (!(mapping.getRecord().getEid().getAddress() instanceof SourceDestKey)) { - notificationMapping = new MappingData(new MappingRecordBuilder().setEid(key).build()); - } } } - removeSubscribers(key); + removeSubscribersConditionally(origin, key); if (origin == MappingOrigin.Southbound) { removeFromSbTimeoutService(key); @@ -534,22 +580,59 @@ public class MappingSystem implements IMappingSystem { } if (notificationMapping != null) { - notifyChange(notificationMapping, subscribers, dstSubscribers, MappingChange.Removed); + publishNotification(notificationMapping, key, subscribers, dstSubscribers, MappingChange.Removed); + notifyChildren(key, notificationMapping, MappingChange.Removed); + if (dstAddr != null) { + notifyChildren(dstAddr, notificationMapping, MappingChange.Removed); + } + } + } + + public void notifyChange(Eid eid, MappingRecord mapping, MappingChange mappingChange) { + Set subscribers = getSubscribers(eid); + + Set dstSubscribers = null; + // For SrcDst LCAF also send SMRs to Dst prefix + if (eid.getAddress() instanceof SourceDestKey) { + Eid dstAddr = SourceDestKeyHelper.getDstBinary(eid); + dstSubscribers = getSubscribers(dstAddr); + notifyChildren(dstAddr, mapping, mappingChange); + } + publishNotification(mapping, eid, subscribers, dstSubscribers, mappingChange); + + notifyChildren(eid, mapping, mappingChange); + } + + private void notifyChildren(Eid eid, MappingRecord mapping, MappingChange mappingChange) { + // Update/created only happens for NB mappings. We assume no overlapping prefix support for NB mappings - so + // this NB mapping should not have any children. Both for NB first and NB&SB cases all subscribers for SB + // prefixes that are equal or more specific to this NB prefix have to be notified of the potential change. + // Each subscriber is notified for the prefix that it is currently subscribed to, and MS should return to them + // a Map-Reply with the same prefix and update mapping in cases of EID_INTERSECTION_RLOC_NB_FIRST which is a + // new option we are creating TODO + Set childPrefixes = getSubtree(MappingOrigin.Southbound, eid); + if (childPrefixes == null || childPrefixes.isEmpty()) { + return; + } + + childPrefixes.remove(eid); + for (Eid prefix : childPrefixes) { + Set subscribers = getSubscribers(prefix); + publishNotification(mapping, prefix, subscribers, null, mappingChange); } } - private void notifyChange(MappingData mapping, Set subscribers, Set dstSubscribers, - MappingChange mappingChange) { - MappingChanged notification = MSNotificationInputUtil.toMappingChanged(mapping, subscribers, dstSubscribers, - mappingChange); + private void publishNotification(MappingRecord mapping, Eid eid, Set subscribers, + Set dstSubscribers, MappingChange mappingChange) { try { - notificationPublishService.putNotification(notification); + // The notifications are used for sending SMR. + notificationPublishService.putNotification(MSNotificationInputUtil.toMappingChanged( + mapping, eid, subscribers, dstSubscribers, mappingChange)); } catch (InterruptedException e) { LOG.warn("Notification publication interrupted!"); } } - /* * Merges adjacent negative prefixes and notifies their subscribers. */ @@ -639,6 +722,23 @@ public class MappingSystem implements IMappingSystem { return subscribers; } + /* + * Only remove subscribers if there is no exact match mapping in the map-cache other than the one specified by + * origin. Right now we only have two origins, but in case we will have more, we only need to update this method, + * not the callers. We use getData() instead of getMapping to do exact match instead of longest prefix match. + */ + private void removeSubscribersConditionally(MappingOrigin origin, Eid address) { + if (origin == MappingOrigin.Southbound) { + if (pmc.getData(address, SubKeys.RECORD) == null) { + removeSubscribers(address); + } + } else if (origin == MappingOrigin.Northbound) { + if (smc.getData(address, SubKeys.RECORD) == null) { + removeSubscribers(address); + } + } + } + private void removeSubscribers(Eid address) { if (LOG.isDebugEnabled()) { LOG.debug("Removing subscribers for EID {}", LispAddressStringifier.getString(address)); diff --git a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/lisp/MapServer.java b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/lisp/MapServer.java index 65e659ccc..7295bfeaa 100644 --- a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/lisp/MapServer.java +++ b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/lisp/MapServer.java @@ -235,7 +235,10 @@ public class MapServer implements IMapServerAsync, OdlMappingserviceListener, IS public void onMappingChanged(MappingChanged notification) { LOG.trace("MappingChanged event of type: `{}'", notification.getChangeType()); if (subscriptionService) { - Eid eid = notification.getMappingRecord().getEid(); + Eid eid = notification.getEid(); + if (eid == null) { + eid = notification.getMappingRecord().getEid(); + } Set subscribers = MSNotificationInputUtil.toSubscriberSet(notification.getSubscriberItem()); LoggingUtil.logSubscribers(LOG, eid, subscribers); if (mapService.isMaster()) { diff --git a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListener.java b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListener.java index 037dcc0e2..04453fa50 100644 --- a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListener.java +++ b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListener.java @@ -10,25 +10,19 @@ package org.opendaylight.lispflowmapping.implementation.mdsal; import java.util.ArrayList; import java.util.Collection; import java.util.List; -import java.util.Set; import org.opendaylight.controller.md.sal.binding.api.DataBroker; import org.opendaylight.controller.md.sal.binding.api.DataObjectModification; import org.opendaylight.controller.md.sal.binding.api.DataObjectModification.ModificationType; import org.opendaylight.controller.md.sal.binding.api.DataTreeModification; import org.opendaylight.controller.md.sal.binding.api.NotificationPublishService; -import org.opendaylight.lispflowmapping.implementation.util.MSNotificationInputUtil; -import org.opendaylight.lispflowmapping.interfaces.dao.Subscriber; import org.opendaylight.lispflowmapping.interfaces.mapcache.IMappingSystem; import org.opendaylight.lispflowmapping.lisp.type.MappingData; import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil; -import org.opendaylight.lispflowmapping.lisp.util.SourceDestKeyHelper; -import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.SourceDestKey; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.eid.container.Eid; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecord; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecordBuilder; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecord; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecordBuilder; -import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChange; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingDatabase; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingOrigin; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.db.instance.Mapping; @@ -104,40 +98,22 @@ public class MappingDataListener extends AbstractDataListener { continue; } - MappingChange mappingChange; + final Mapping convertedMapping = convertToBinaryIfNecessary(mapping); + Eid convertedEid = convertedMapping.getMappingRecord().getEid(); if (ModificationType.SUBTREE_MODIFIED == mod.getModificationType()) { LOG.trace("Received update data"); - mappingChange = MappingChange.Updated; + LOG.trace("Key: {}", change.getRootPath().getRootIdentifier()); + LOG.trace("Value: {}", mapping); + mapSystem.updateMapping(convertedMapping.getOrigin(), convertedEid, + new MappingData(convertedMapping.getMappingRecord())); } else { LOG.trace("Received write data"); - mappingChange = MappingChange.Created; + LOG.trace("Key: {}", change.getRootPath().getRootIdentifier()); + LOG.trace("Value: {}", mapping); + mapSystem.addMapping(convertedMapping.getOrigin(), convertedEid, + new MappingData(convertedMapping.getMappingRecord())); } - LOG.trace("Key: {}", change.getRootPath().getRootIdentifier()); - LOG.trace("Value: {}", mapping); - - final Mapping convertedMapping = convertToBinaryIfNecessary(mapping); - Eid convertedEid = convertedMapping.getMappingRecord().getEid(); - - mapSystem.addMapping(convertedMapping.getOrigin(), convertedEid, - new MappingData(convertedMapping.getMappingRecord())); - Set subscribers = mapSystem.getSubscribers(convertedEid); - - Set dstSubscribers = null; - // For SrcDst LCAF also send SMRs to Dst prefix - if (convertedEid.getAddress() instanceof SourceDestKey) { - Eid dstAddr = SourceDestKeyHelper.getDstBinary(convertedEid); - dstSubscribers = mapSystem.getSubscribers(dstAddr); - } - - try { - // The notifications are used for sending SMR. - notificationPublishService.putNotification(MSNotificationInputUtil.toMappingChanged( - convertedMapping, subscribers, dstSubscribers, mappingChange)); - } catch (InterruptedException e) { - LOG.warn("Notification publication interrupted!"); - } - } else { LOG.warn("Ignoring unhandled modification type {}", mod.getModificationType()); } diff --git a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/util/MSNotificationInputUtil.java b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/util/MSNotificationInputUtil.java index 7aa820630..50b88b732 100644 --- a/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/util/MSNotificationInputUtil.java +++ b/mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/util/MSNotificationInputUtil.java @@ -13,11 +13,11 @@ import java.util.ArrayList; import java.util.List; import java.util.Set; import org.opendaylight.lispflowmapping.interfaces.dao.Subscriber; -import org.opendaylight.lispflowmapping.lisp.type.MappingData; +import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.eid.container.Eid; +import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecord; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChange; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChanged; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChangedBuilder; -import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.db.instance.Mapping; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.mapping.changed.DstSubscriberItem; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.mapping.changed.DstSubscriberItemBuilder; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.mapping.changed.SubscriberItem; @@ -35,19 +35,11 @@ public final class MSNotificationInputUtil { private MSNotificationInputUtil() { } - public static MappingChanged toMappingChanged(Mapping input, Set subscribers, - Set dstSubscribers, MappingChange change) { + public static MappingChanged toMappingChanged(MappingRecord mapping, Eid eid, Set subscribers, + Set dstSubscribers, MappingChange change) { return new MappingChangedBuilder() - .setMappingRecord(input.getMappingRecord()) - .setSubscriberItem(toSubscriberList(subscribers)) - .setDstSubscriberItem(toDstSubscriberList(dstSubscribers)) - .setChangeType(change).build(); - } - - public static MappingChanged toMappingChanged(MappingData mapping, Set subscribers, - Set dstSubscribers, MappingChange change) { - return new MappingChangedBuilder() - .setMappingRecord(mapping.getRecord()) + .setMappingRecord(mapping) + .setEid(eid) .setSubscriberItem(toSubscriberList(subscribers)) .setDstSubscriberItem(toDstSubscriberList(dstSubscribers)) .setChangeType(change).build(); diff --git a/mappingservice/implementation/src/test/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListenerTest.java b/mappingservice/implementation/src/test/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListenerTest.java index 3f89c1bb4..d4f96f4c7 100644 --- a/mappingservice/implementation/src/test/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListenerTest.java +++ b/mappingservice/implementation/src/test/java/org/opendaylight/lispflowmapping/implementation/mdsal/MappingDataListenerTest.java @@ -104,8 +104,6 @@ public class MappingDataListenerTest { @SuppressWarnings("unchecked") public void onDataTreeChangedTest_delete_NB() throws InterruptedException { final List> changes = Lists.newArrayList(change_del); - final MappingChanged mapChanged = MSNotificationInputUtil - .toMappingChanged(MAPPING_EID_1_NB, null, null, MappingChange.Removed); Mockito.when(mod_del.getDataBefore()).thenReturn(MAPPING_EID_1_NB); mappingDataListener.onDataTreeChanged(changes); @@ -135,8 +133,8 @@ public class MappingDataListenerTest { @SuppressWarnings("unchecked") public void onDataTreeChangedTest_subtreeModified_NB() throws InterruptedException { final List> changes = Lists.newArrayList(change_subtreeModified); - final MappingChanged mapChanged = MSNotificationInputUtil - .toMappingChanged(MAPPING_EID_2_NB, null, null, MappingChange.Updated); + final MappingChanged mapChanged = MSNotificationInputUtil.toMappingChanged( + MAPPING_EID_2_NB.getMappingRecord(), null, null, null, MappingChange.Updated); Mockito.when(mod_subtreeModified.getDataAfter()).thenReturn(MAPPING_EID_2_NB); mappingDataListener.onDataTreeChanged(changes); @@ -170,8 +168,8 @@ public class MappingDataListenerTest { @SuppressWarnings("unchecked") public void onDataTreeChangedTest_write_NB() throws InterruptedException { final List> changes = Lists.newArrayList(change_write); - final MappingChanged mapChanged = MSNotificationInputUtil - .toMappingChanged(MAPPING_EID_3_NB, null, null, MappingChange.Created); + final MappingChanged mapChanged = MSNotificationInputUtil.toMappingChanged( + MAPPING_EID_3_NB.getMappingRecord(), null, null, null, MappingChange.Created); Mockito.when(mod_write.getDataAfter()).thenReturn(MAPPING_EID_3_NB); mappingDataListener.onDataTreeChanged(changes); @@ -205,10 +203,8 @@ public class MappingDataListenerTest { public void onDataTreeChangedTest_multipleChanges() throws InterruptedException { final List> changes = Lists.newArrayList(change_del, change_subtreeModified, change_write); - final MappingChanged mapChangedDel = MSNotificationInputUtil - .toMappingChanged(MAPPING_EID_1_NB, null, null, MappingChange.Removed); - final MappingChanged mapChangedSubtreeMod = MSNotificationInputUtil - .toMappingChanged(MAPPING_EID_2_NB, null, null, MappingChange.Updated); + final MappingChanged mapChangedSubtreeMod = MSNotificationInputUtil.toMappingChanged( + MAPPING_EID_2_NB.getMappingRecord(), null, null, null, MappingChange.Updated); Mockito.when(mod_del.getDataBefore()).thenReturn(MAPPING_EID_1_NB); Mockito.when(mod_subtreeModified.getDataAfter()).thenReturn(MAPPING_EID_2_NB); diff --git a/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java b/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java index df27cd8f9..93f2b377b 100644 --- a/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java +++ b/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java @@ -40,7 +40,8 @@ public class HashMapDb implements ILispDAO, AutoCloseable { PARENT, SIBLING, VIRTUAL_PARENT_SIBLING, - WIDEST_NEGATIVE + WIDEST_NEGATIVE, + COVERING } public void tryAddToIpTrie(Object key) { @@ -137,6 +138,10 @@ public class HashMapDb implements ILispDAO, AutoCloseable { if (key.getAddress() instanceof Ipv4PrefixBinary) { Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress(); switch (method) { + case COVERING: + node = ip4Trie.lookupCoveringLessSpecific(prefix.getIpv4AddressBinary().getValue(), + prefix.getIpv4MaskLength()); + break; case PARENT: node = ip4Trie.lookupParent(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength()); break; @@ -155,13 +160,17 @@ public class HashMapDb implements ILispDAO, AutoCloseable { node = null; break; } - if (node != null) { + if (node != null && node.prefix() != null) { return LispAddressUtil.asIpv4PrefixBinaryEid( key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()); } } else if (key.getAddress() instanceof Ipv6PrefixBinary) { Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress(); switch (method) { + case COVERING: + node = ip6Trie.lookupCoveringLessSpecific(prefix.getIpv6AddressBinary().getValue(), + prefix.getIpv6MaskLength()); + break; case PARENT: node = ip6Trie.lookupParent(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength()); break; @@ -180,7 +189,7 @@ public class HashMapDb implements ILispDAO, AutoCloseable { node = null; break; } - if (node != null) { + if (node != null && node.prefix() != null) { return LispAddressUtil.asIpv6PrefixBinaryEid( key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()); } @@ -188,6 +197,11 @@ public class HashMapDb implements ILispDAO, AutoCloseable { return null; } + @Override + public Eid getCoveringLessSpecific(Eid key) { + return getPrefix(key, GetPrefixMethods.COVERING); + } + @Override public Eid getParentPrefix(Eid key) { return getPrefix(key, GetPrefixMethods.PARENT); diff --git a/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrie.java b/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrie.java index ef14492fe..81f6bfe19 100644 --- a/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrie.java +++ b/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrie.java @@ -125,7 +125,7 @@ public class RadixTrie { } // find closest prefix starting at ROOT - TrieNode closest = root.findClosest(prefix, preflen); + TrieNode closest = root.findClosest(prefix, preflen, false); // find first different bit <= min(closestNode.preflen, preflen) int diffbit = closest.firstDifferentBit(prefix, preflen); @@ -179,6 +179,38 @@ public class RadixTrie { return null; } + /** + * Look up the covering prefix for the argument, but exclude the argument itself, so the result is always less + * specific than the lookup key. + * + * @param prefix Big endian byte array representation of the prefix argument + * @param preflen Prefix length + * @return Covering node + */ + public TrieNode lookupCoveringLessSpecific(byte[] prefix, int preflen) { + if (root == null || preflen > maxBits) { + return null; + } + + TrieNode node = root.findClosest(prefix, preflen, true); + + if (node == null) { + return null; + } else if (node.bit < preflen && node.prefix != null) { + // If the current node is not virtual and is less specific than the query, we can return it directly + return node; + } + + // Else, we need to find a non-virtual parent + node = node.up; + + while (node != null && node.prefix == null) { + node = node.up; + } + + return node; + } + /** * Given an EID, lookup the longest prefix match, then return its parent node. * @@ -191,10 +223,10 @@ public class RadixTrie { if (node == null) { return null; - } else { - node = node.up; } + node = node.up; + while (node != null && node.prefix == null) { node = node.up; } @@ -255,7 +287,7 @@ public class RadixTrie { return null; } - TrieNode node = root.findClosest(prefix, preflen); + TrieNode node = root.findClosest(prefix, preflen, false); // not a negative match if (node.prefix != null && node.prefixLength() <= preflen && node.comparePrefix(prefix)) { @@ -277,7 +309,7 @@ public class RadixTrie { return null; } - TrieNode node = root.findClosest(prefix, preflen); + TrieNode node = root.findClosest(prefix, preflen, false); // if no node is found or if node not a prefix or if mask is not the same if (node == null || node.prefix == null || node.bit != preflen) { @@ -304,19 +336,16 @@ public class RadixTrie { return Collections.emptySet(); } - TrieNode node = root.findClosest(prefix, preflen); - - // if no node is found or if node not a prefix - if (node == null || node.prefix == null) { - return Collections.emptySet(); - } + TrieNode node = root.findClosest(prefix, preflen, true); Set children = new HashSet<>(); - children.add(node); + if (node.prefix != null && node.bit >= preflen) { + children.add(node); + } Iterator it = node.iterator(); while (it.hasNext()) { node = it.next(); - if (node.prefix != null) { + if (node.prefix != null && node.bit >= preflen) { children.add(node); } } @@ -337,42 +366,6 @@ public class RadixTrie { } } - /** - * Remove node's subtree. - * - * @param node Node who's subtree is to be removed - */ - public void removeSubtree(TrieNode node) { - TrieNode itNode; - Iterator it = node.iterator(); - - while (it.hasNext()) { - itNode = it.next(); - itNode.erase(); - } - } - - /** - * Remove subtree for longest match. - * - * @param prefix Prefix to be looked up - * @param preflen Prefix length - */ - public void removeSubtree(byte[] prefix, int preflen) { - TrieNode itNode = lookupBest(prefix, preflen); - - if (itNode == null) { - return; - } - - Iterator it = itNode.iterator(); - - while (it.hasNext()) { - itNode = it.next(); - itNode.erase(); - } - } - /** * Remove all entries in the trie. */ @@ -421,12 +414,13 @@ public class RadixTrie { * * @param pref Searched prefix * @param preflen Searched prefix length + * @param virtual Include virtual nodes in search * @return The node found */ - public TrieNode findClosest(byte[] pref, int preflen) { + public TrieNode findClosest(byte[] pref, int preflen, boolean virtual) { TrieNode node = this; - while (node.prefix == null || node.bit < preflen) { + while ((!virtual && node.prefix == null) || node.bit < preflen) { if (testBitInPrefixByte(pref, node.bit)) { if (node.right == null) { break; @@ -692,6 +686,44 @@ public class RadixTrie { return new TriePostOrderIterator(this); } + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + sb.append(printPrefixAndMask()); + if (up != null) { + sb.append(", parent: "); + sb.append(up.printPrefixAndMask()); + } + if (left != null) { + sb.append(", left child: "); + sb.append(left.printPrefixAndMask()); + } + if (right != null) { + sb.append(", right child: "); + sb.append(right.printPrefixAndMask()); + } + if (data != null) { + sb.append(", data: "); + sb.append(data); + } + return sb.toString(); + } + + private String printPrefixAndMask() { + if (prefix == null) { + return "Virtual @ bit " + bit; + } + StringBuilder sb = new StringBuilder(); + try { + sb.append(InetAddress.getByAddress(prefix)); + sb.append("/"); + sb.append(bit); + } catch (UnknownHostException e) { + return "NaP"; + } + return sb.toString(); + } + /** * Post order iterator implementation for prefix trie. It's safe to use it to remove nodes. */ diff --git a/mappingservice/lisp-proto/src/main/java/org/opendaylight/lispflowmapping/lisp/util/LispAddressStringifier.java b/mappingservice/lisp-proto/src/main/java/org/opendaylight/lispflowmapping/lisp/util/LispAddressStringifier.java index 15e72e061..3fff6d619 100644 --- a/mappingservice/lisp-proto/src/main/java/org/opendaylight/lispflowmapping/lisp/util/LispAddressStringifier.java +++ b/mappingservice/lisp-proto/src/main/java/org/opendaylight/lispflowmapping/lisp/util/LispAddressStringifier.java @@ -7,13 +7,13 @@ */ package org.opendaylight.lispflowmapping.lisp.util; -import com.google.common.base.Preconditions; import com.google.common.io.BaseEncoding; import com.google.common.net.InetAddresses; import java.net.Inet4Address; import java.net.Inet6Address; import java.net.UnknownHostException; import java.util.List; +import java.util.Set; import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.LispAddress; import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.SimpleAddress; import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.Address; @@ -39,6 +39,7 @@ import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.typ import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv6Binary; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv6PrefixBinary; import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.XtrId; +import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.eid.container.Eid; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -50,7 +51,7 @@ import org.slf4j.LoggerFactory; * @author Lorand Jakab * */ -public class LispAddressStringifier { +public final class LispAddressStringifier { protected static final Logger LOG = LoggerFactory.getLogger(LispAddressStringifier.class); private static final String PREFIX_SEPARATOR = ":"; @@ -78,10 +79,28 @@ public class LispAddressStringifier { URL; } + // Utility class, should not be instantiated + private LispAddressStringifier() { + } + public static String getString(LispAddress lispAddress) { return getAddrString(Destination.USER, lispAddress); } + public static String getString(Set eids) { + StringBuilder sb = new StringBuilder("{"); + boolean first = true; + for (Eid eid : eids) { + if (!first) { + sb.append(", "); + } + sb.append(getString(eid)); + first = false; + } + sb.append("}"); + return sb.toString(); + } + public static String getString(Address address) { return getAddrString(Destination.USER, address, null); } @@ -111,7 +130,10 @@ public class LispAddressStringifier { } private static String getAddrString(Destination dst, LispAddress lispAddress) { - Preconditions.checkNotNull(lispAddress, "lispAddress should not be null"); + if (lispAddress == null) { + return "null"; + } + Address addr = lispAddress.getAddress(); Long vni = null; diff --git a/mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/SimpleMapCache.java b/mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/SimpleMapCache.java index e7a5753d0..4310e35cb 100644 --- a/mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/SimpleMapCache.java +++ b/mappingservice/mapcache/src/main/java/org/opendaylight/lispflowmapping/mapcache/SimpleMapCache.java @@ -175,6 +175,15 @@ public class SimpleMapCache implements ILispMapCache { return table.getWidestNegativePrefix(MaskUtil.normalize(eid)); } + @Override + public Eid getCoveringLessSpecific(Eid eid) { + ILispDAO table = getVniTable(eid); + if (table == null) { + return null; + } + return table.getCoveringLessSpecific(MaskUtil.normalize(eid)); + } + @Override public Eid getParentPrefix(Eid eid) { ILispDAO table = getVniTable(eid); -- 2.36.6