From 3e875e5c4e77cc6f4d9689b9fd83dfb4ec954524 Mon Sep 17 00:00:00 2001 From: Lorand Jakab Date: Tue, 20 Jun 2017 14:54:10 +0300 Subject: [PATCH] Bug 9023: Fix merging of negative prefixes This happens after a positive mapping removal. Add integration test to keep from regressing. Change-Id: I32788e8af5b457bf895197ba11add34e8ae06c57 Signed-off-by: Lorand Jakab --- .../MappingServiceIntegrationTest.java | 58 +++++++++++++++++- .../implementation/MappingSystem.java | 59 ++++++++++++++----- 2 files changed, 102 insertions(+), 15 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 cb22fcf70..b98f77ee8 100644 --- a/integrationtest/src/test/java/org/opendaylight/lispflowmapping/integrationtest/MappingServiceIntegrationTest.java +++ b/integrationtest/src/test/java/org/opendaylight/lispflowmapping/integrationtest/MappingServiceIntegrationTest.java @@ -419,15 +419,21 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { } @Test - public void testNegativePrefix_gapIntersection() throws UnknownHostException { + public void testNbAndSbNegativePrefix() throws UnknownHostException { insertMappings(); testGapIntersection(); insertMappings(); testMultipleMappings(); + } + @Test + public void testExplicitSbNegativePrefixes() { // https://bugs.opendaylight.org/show_bug.cgi?id=8679 testNegativePrefix(); + + // https://bugs.opendaylight.org/show_bug.cgi?id=9023 + testPositiveMappingRemoval(); } private void testRepeatedSmr() throws SocketTimeoutException, UnknownHostException { @@ -620,6 +626,46 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { assertTrue(MappingRecordUtil.isNegativeMapping(mr)); } + private void testPositiveMappingRemoval() { + cleanUP(); + + insertNBMappings(1L, "192.167.0.0/16", "192.169.0.0/16"); + insertSBMappings(1L, "192.168.32.0/19"); + + MapReply mapReply = lms.handleMapRequest(newMapRequest(1L, "192.168.0.1/32")); + Eid expectedNegativePrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "192.168.0.0/19"); + MappingRecord mr = mapReply.getMappingRecordItem().get(0).getMappingRecord(); + assertEquals(expectedNegativePrefix, mr.getEid()); + assertTrue(MappingRecordUtil.isNegativeMapping(mr)); + + mapReply = lms.handleMapRequest(newMapRequest(1L, "192.168.64.1/32")); + expectedNegativePrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "192.168.64.0/18"); + mr = mapReply.getMappingRecordItem().get(0).getMappingRecord(); + assertEquals(expectedNegativePrefix, mr.getEid()); + assertTrue(MappingRecordUtil.isNegativeMapping(mr)); + + mapReply = lms.handleMapRequest(newMapRequest(1L, "192.168.128.1/32")); + expectedNegativePrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "192.168.128.0/17"); + mr = mapReply.getMappingRecordItem().get(0).getMappingRecord(); + assertEquals(expectedNegativePrefix, mr.getEid()); + assertTrue(MappingRecordUtil.isNegativeMapping(mr)); + + printMapCacheState(); + + mapService.removeMapping(MappingOrigin.Southbound, LispAddressUtil.asIpv4PrefixBinaryEid( + 1L, "192.168.32.0/19")); + + printMapCacheState(); + + mapReply = lms.handleMapRequest(newMapRequest(1L, "192.168.32.1/32")); + expectedNegativePrefix = LispAddressUtil.asIpv4PrefixBinaryEid(1L, "192.168.0.0/16"); + mr = mapReply.getMappingRecordItem().get(0).getMappingRecord(); + assertEquals(expectedNegativePrefix, mr.getEid()); + assertTrue(MappingRecordUtil.isNegativeMapping(mr)); + + printMapCacheState(); + } + private void insertMappings() { cleanUP(); mapService.setLookupPolicy(IMappingService.LookupPolicy.NB_AND_SB); @@ -632,15 +678,19 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { } private void insertNBMappings(long iid, String ... prefixes) { + LOG.debug("Adding Northbound mappings for prefixes: {}", prefixes); final InstanceIdType iiType = new InstanceIdType(iid); for (String prefix : prefixes) { MappingRecord record = newMappingRecord(prefix, iiType); mapService.addMapping(MappingOrigin.Northbound, record.getEid(), null, new MappingData(MappingOrigin.Northbound, record)); } + sleepForMilliseconds(25); + printMapCacheState(); } private void insertSBMappings(long iid, String ... prefixes) { + LOG.debug("Adding Southbound mappings for prefixes: {}", prefixes); final InstanceIdType iiType = new InstanceIdType(iid); Eid eid = LispAddressUtil.asIpv4PrefixBinaryEid("0.0.0.0/0", iiType); mapService.addAuthenticationKey(eid, NULL_AUTH_KEY); @@ -650,6 +700,11 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { mapService.addMapping(MappingOrigin.Southbound, record.getEid(), null, new MappingData(MappingOrigin.Southbound, record, System.currentTimeMillis())); } + printMapCacheState(); + } + + private void printMapCacheState() { + LOG.debug("Map-cache state:\n{}", mapService.prettyPrintMappings()); } /** @@ -666,6 +721,7 @@ public class MappingServiceIntegrationTest extends AbstractMdsalTestBase { .setLocatorRecord(Lists.newArrayList(new LocatorRecordBuilder() .setRloc(LispAddressUtil.asIpv4Rloc("2.2.2.2")) .setLocatorId("loc_id") + .setRouted(true) .setPriority((short) 1) .setWeight((short) 1).build())) .setTimestamp(System.currentTimeMillis()) 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 e1f38471e..ab19666b2 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 @@ -11,8 +11,10 @@ package org.opendaylight.lispflowmapping.implementation; import java.util.ArrayList; import java.util.Date; import java.util.EnumMap; +import java.util.HashMap; import java.util.HashSet; import java.util.List; +import java.util.Map; import java.util.Set; import org.opendaylight.controller.md.sal.binding.api.NotificationPublishService; import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType; @@ -202,6 +204,8 @@ public class MappingSystem implements IMappingSystem { public MappingData addNegativeMapping(Eid key) { MappingRecord mapping = buildNegativeMapping(key); MappingData mappingData = new MappingData(MappingOrigin.Southbound, mapping); + LOG.debug("Adding negative mapping for EID {}", LispAddressStringifier.getString(key)); + LOG.trace(mappingData.getString()); smc.addMapping(mapping.getEid(), mappingData); dsbe.addMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, mapping.getEid(), null, mappingData)); return mappingData; @@ -478,8 +482,17 @@ public class MappingSystem implements IMappingSystem { Set dstSubscribers = null; MappingData mapping = (MappingData) tableMap.get(origin).getMapping(null, key); + if (LOG.isDebugEnabled()) { + LOG.debug("Removing mapping for EID {} from {}", + LispAddressStringifier.getString(key), origin); + } + if (LOG.isTraceEnabled()) { + LOG.trace(mapping.getString()); + } + + MappingData notificationMapping = mapping; + if (mapping != null) { - MappingData notificationMapping = mapping; subscribers = (Set) getData(MappingOrigin.Southbound, key, SubKeys.SUBSCRIBERS); // For SrcDst LCAF also send SMRs to Dst prefix if (key.getAddress() instanceof SourceDestKey) { @@ -490,7 +503,6 @@ public class MappingSystem implements IMappingSystem { new MappingRecordBuilder().setEid(key).build()); } } - notifyChange(notificationMapping, subscribers, dstSubscribers, MappingChange.Removed); } if (origin == MappingOrigin.Northbound) { @@ -499,11 +511,18 @@ public class MappingSystem implements IMappingSystem { if (origin == MappingOrigin.Southbound) { removeFromSbTimeoutService(key); - if (mapping != null && mapping.isPositive().or(false)) { - mergeNegativePrefixes(key); - } } - tableMap.get(origin).removeMapping(key); + + if (origin == MappingOrigin.Southbound && mapping != null && mapping.isPositive().or(false)) { + mergeNegativePrefixes(key); + } else { + // mergeNegativePrefixes() above removes the mapping, so addNegativeMapping() will work correctly + tableMap.get(origin).removeMapping(key); + } + + if (notificationMapping != null) { + notifyChange(notificationMapping, subscribers, dstSubscribers, MappingChange.Removed); + } } private void notifyChange(MappingData mapping, Set subscribers, Set dstSubscribers, @@ -522,26 +541,38 @@ public class MappingSystem implements IMappingSystem { * Merges adjacent negative prefixes and notifies their subscribers. */ private void mergeNegativePrefixes(Eid eid) { - // If prefix sibling has a negative mapping, save its subscribers - Eid sibling = smc.getSiblingPrefix(eid); - MappingData mapping = (MappingData) smc.getMapping(null, sibling); + LOG.debug("Merging negative prefixes starting from EID {}", LispAddressStringifier.getString(eid)); + + // If we delete nodes while we walk up the radix trie the algorithm will give incorrect results, because + // removals rearrange relationships in the trie. So we save prefixes to be removed into a HashMap. + Map mergedMappings = new HashMap<>(); + + Eid currentNode = smc.getSiblingPrefix(eid); + MappingData mapping = (MappingData) smc.getMapping(null, currentNode); if (mapping != null && mapping.isNegative().or(false)) { - removeSbMapping(sibling, mapping); + mergedMappings.put(currentNode, mapping); } else { return; } - Eid currentNode = sibling; - Eid previousNode = sibling; - while ((currentNode = smc.getVirtualParentSiblingPrefix(currentNode)) != null) { + Eid previousNode = currentNode; + currentNode = smc.getVirtualParentSiblingPrefix(currentNode); + while (currentNode != null) { mapping = (MappingData) smc.getMapping(null, currentNode); if (mapping != null && mapping.isNegative().or(false)) { - removeSbMapping(currentNode, mapping); + mergedMappings.put(currentNode, mapping); } else { break; } previousNode = currentNode; + currentNode = smc.getVirtualParentSiblingPrefix(previousNode); + } + + for (Eid key : mergedMappings.keySet()) { + removeSbMapping(key, mergedMappings.get(key)); } + smc.removeMapping(eid); + addNegativeMapping(getVirtualParent(previousNode)); } -- 2.36.6