Magnesium platform upgrade
[lispflowmapping.git] / mappingservice / implementation / src / main / java / org / opendaylight / lispflowmapping / implementation / MappingSystem.java
index b25e5986bb186b6bd1d1739f38111fcea1ec625b..1c9799d7cc2bdfa7ab979bd44cb97d599e80b2fb 100644 (file)
@@ -8,19 +8,23 @@
 
 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;
 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;
+import java.util.concurrent.ConcurrentHashMap;
 import org.opendaylight.lispflowmapping.config.ConfigIni;
 import org.opendaylight.lispflowmapping.dsbackend.DataStoreBackEnd;
 import org.opendaylight.lispflowmapping.implementation.timebucket.implementation.TimeBucketMappingTimeoutService;
 import org.opendaylight.lispflowmapping.implementation.timebucket.interfaces.ISouthBoundMappingTimeoutService;
 import org.opendaylight.lispflowmapping.implementation.util.DSBEInputUtil;
+import org.opendaylight.lispflowmapping.implementation.util.LoggingUtil;
 import org.opendaylight.lispflowmapping.implementation.util.MSNotificationInputUtil;
 import org.opendaylight.lispflowmapping.implementation.util.MappingMergeUtil;
 import org.opendaylight.lispflowmapping.interfaces.dao.ILispDAO;
@@ -35,11 +39,15 @@ import org.opendaylight.lispflowmapping.lisp.type.LispMessage;
 import org.opendaylight.lispflowmapping.lisp.type.MappingData;
 import org.opendaylight.lispflowmapping.lisp.util.LispAddressStringifier;
 import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil;
+import org.opendaylight.lispflowmapping.lisp.util.MappingRecordUtil;
 import org.opendaylight.lispflowmapping.lisp.util.MaskUtil;
 import org.opendaylight.lispflowmapping.lisp.util.SourceDestKeyHelper;
 import org.opendaylight.lispflowmapping.mapcache.AuthKeyDb;
 import org.opendaylight.lispflowmapping.mapcache.MultiTableMapCache;
 import org.opendaylight.lispflowmapping.mapcache.SimpleMapCache;
+import org.opendaylight.lispflowmapping.mapcache.lisp.LispMapCacheStringifier;
+import org.opendaylight.mdsal.binding.api.NotificationPublishService;
+import org.opendaylight.mdsal.common.api.LogicalDatastoreType;
 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.ExplicitLocatorPath;
 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv4;
@@ -61,7 +69,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;
@@ -81,18 +88,19 @@ public class MappingSystem implements IMappingSystem {
     private static final String AUTH_KEY_TABLE = "authentication";
     //private static final int TTL_RLOC_TIMED_OUT = 1;
     private static final int TTL_NO_RLOC_KNOWN = ConfigIni.getInstance().getNegativeMappingTTL();
-    private NotificationPublishService notificationPublishService;
+    private final NotificationPublishService notificationPublishService;
     private boolean mappingMerge;
-    private ILispDAO dao;
+    private final ILispDAO dao;
     private ILispDAO sdao;
     private ILispMapCache smc;
     private IMapCache pmc;
+    private final ConcurrentHashMap<Eid, Set<Subscriber>> subscriberdb = new ConcurrentHashMap<>();
     private IAuthKeyDb akdb;
     private final EnumMap<MappingOrigin, IMapCache> tableMap = new EnumMap<>(MappingOrigin.class);
     private DataStoreBackEnd dsbe;
     private boolean isMaster = false;
 
-    private ISouthBoundMappingTimeoutService sbMappingTimeoutService;
+    private final ISouthBoundMappingTimeoutService sbMappingTimeoutService;
 
     public MappingSystem(ILispDAO dao, boolean iterateMask, NotificationPublishService nps, boolean mappingMerge) {
         this.dao = dao;
@@ -105,8 +113,8 @@ public class MappingSystem implements IMappingSystem {
                 this);
     }
 
-    public void setDataStoreBackEnd(DataStoreBackEnd dsbe) {
-        this.dsbe = dsbe;
+    public void setDataStoreBackEnd(DataStoreBackEnd dataStoreBackEnd) {
+        this.dsbe = dataStoreBackEnd;
     }
 
     @Override
@@ -140,7 +148,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();
 
@@ -149,6 +167,17 @@ public class MappingSystem implements IMappingSystem {
             return;
         }
 
+        if (LOG.isDebugEnabled()) {
+            LOG.debug("DAO: Adding {} mapping for EID {}", origin, LispAddressStringifier.getString(key));
+        }
+
+        if (LOG.isTraceEnabled()) {
+            LOG.trace("mappingData = {}", mappingData.getString());
+        }
+
+        // Save the old mapping for the key before we modify anything, so that we can detect changes later
+        final MappingRecord oldMapping = getMappingRecord(getMapping(key));
+
         if (origin == MappingOrigin.Southbound) {
             XtrId xtrId = mappingData.getXtrId();
             if (xtrId == null && mappingMerge && mappingData.isMergeEnabled()) {
@@ -169,6 +198,19 @@ public class MappingSystem implements IMappingSystem {
         }
 
         tableMap.get(origin).addMapping(key, mappingData);
+
+        // We need to check if the newly added mapping is covering negatives in SB, and remove those (with notification)
+        if (mappingData.isPositive().or(true)) {
+            handleSbNegativeMappings(key);
+        }
+
+        MappingRecord newMapping = getMappingRecord(getMapping(key));
+
+        handleAddMappingNotifications(origin, key, mappingData, oldMapping, newMapping, changeType);
+    }
+
+    private static MappingRecord getMappingRecord(MappingData mappingData) {
+        return mappingData != null ? mappingData.getRecord() : null;
     }
 
     @SuppressWarnings("unchecked")
@@ -198,10 +240,65 @@ public class MappingSystem implements IMappingSystem {
         smc.addData(key, SubKeys.TIME_BUCKET_ID, updatedBucketId);
     }
 
+    private void handleSbNegativeMappings(Eid key) {
+        Set<Eid> childPrefixes = getSubtree(MappingOrigin.Southbound, key);
+
+        LOG.trace("handleSbNegativeMappings(): subtree prefix set for EID {}: {}",
+                LispAddressStringifier.getString(key),
+                LispAddressStringifier.getString(childPrefixes));
+
+        for (Eid prefix : childPrefixes) {
+            handleSbNegativeMapping(prefix);
+        }
+
+        Eid parentPrefix = smc.getCoveringLessSpecific(key);
+        LOG.trace("handleSbNegativeMappings(): parent prefix for EID {}: {}",
+                LispAddressStringifier.getString(key),
+                LispAddressStringifier.getString(parentPrefix));
+        handleSbNegativeMapping(parentPrefix);
+    }
+
+    private void handleSbNegativeMapping(Eid key) {
+        MappingData mappingData = getSbMappingWithExpiration(null, key, null);
+        if (mappingData != null && mappingData.isNegative().or(false)) {
+            removeSbMapping(mappingData.getRecord().getEid(), mappingData);
+        }
+    }
+
+    private void handleAddMappingNotifications(MappingOrigin origin, Eid key, MappingData mappingData,
+                                               MappingRecord oldMapping, MappingRecord newMapping,
+                                               MappingChange changeType) {
+        // Non-southbound origins are MD-SAL first, so they only get to call addMapping() if there is a change
+        // Southbound is different, so we need to check if there is a change in the mapping. This check takes into
+        // account policy as well
+        if (origin != MappingOrigin.Southbound || MappingRecordUtil.mappingChanged(oldMapping, newMapping)) {
+            notifyChange(key, mappingData.getRecord(), changeType);
+
+            Eid dstKey = key;
+            // Since the above notifyChange() already notifies the dest part of source/dest addresses, we save the dest
+            // for the checks that we do afterwards
+            if (key.getAddress() instanceof SourceDestKey) {
+                dstKey = SourceDestKeyHelper.getDstBinary(key);
+            }
+            // If the old mapping had a different EID than what was just added, notify those subscribers too
+            if (oldMapping != null && !oldMapping.getEid().equals(key) && !oldMapping.getEid().equals(dstKey)) {
+                notifyChange(oldMapping.getEid(), oldMapping, changeType);
+            }
+            // If the new mapping has a different EID than what was just added (e.g., due to NB_AND_SB), notify those
+            // subscribers too
+            if (newMapping != null && !newMapping.getEid().equals(key) && !newMapping.getEid().equals(dstKey)) {
+                notifyChange(newMapping.getEid(), newMapping, changeType);
+            }
+        }
+
+    }
+
     @Override
     public MappingData addNegativeMapping(Eid key) {
         MappingRecord mapping = buildNegativeMapping(key);
         MappingData mappingData = new MappingData(mapping);
+        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));
         return mappingData;
@@ -232,6 +329,7 @@ public class MappingSystem implements IMappingSystem {
      * Since this method is only called when there is a hit in the southbound Map-Register cache, and that cache is
      * not used when merge is on, it's OK to ignore the effects of timestamp changes on merging for now.
      */
+    @Override
     public void refreshMappingRegistration(Eid key, XtrId xtrId, Long timestamp) {
 
         sbMappingTimeoutService.removeExpiredMappings();
@@ -269,7 +367,7 @@ public class MappingSystem implements IMappingSystem {
         }
 
         LocatorRecord locatorRecord = mappingData.getRecord().getLocatorRecord().get(0);
-        long serviceIndex = ((ServicePath) eid.getAddress()).getServicePath().getServiceIndex();
+        long serviceIndex = ((ServicePath) eid.getAddress()).getServicePath().getServiceIndex().toJava();
         int index = LispAddressUtil.STARTING_SERVICE_INDEX - (int) serviceIndex;
         Rloc rloc = locatorRecord.getRloc();
         if (rloc.getAddress() instanceof Ipv4 || rloc.getAddress() instanceof Ipv6) {
@@ -298,6 +396,7 @@ public class MappingSystem implements IMappingSystem {
     }
 
     private MappingData handleMergedMapping(Eid key) {
+        LOG.trace("Merging mappings for EID {}", LispAddressStringifier.getString(key));
         List<MappingData> expiredMappingDataList = new ArrayList<>();
         Set<IpAddressBinary> sourceRlocs = new HashSet<>();
 
@@ -321,8 +420,13 @@ public class MappingSystem implements IMappingSystem {
     @Override
     public MappingData getMapping(Eid src, Eid dst) {
         // NOTE: Currently we have two lookup algorithms implemented, which are configurable
+        IMappingService.LookupPolicy policy = ConfigIni.getInstance().getLookupPolicy();
+        LOG.debug("DAO: Looking up mapping for {}, source EID {} with policy {}",
+                LispAddressStringifier.getString(dst),
+                LispAddressStringifier.getString(src),
+                policy);
 
-        if (ConfigIni.getInstance().getLookupPolicy() == IMappingService.LookupPolicy.NB_AND_SB) {
+        if (policy == IMappingService.LookupPolicy.NB_AND_SB) {
             return getMappingNbSbIntersection(src, dst);
         } else {
             return getMappingNbFirst(src, dst);
@@ -391,11 +495,17 @@ public class MappingSystem implements IMappingSystem {
 
     private MappingData getSbMappingWithExpiration(Eid src, Eid dst, XtrId xtrId) {
         MappingData mappingData = (MappingData) smc.getMapping(dst, xtrId);
-        if (mappingData != null && MappingMergeUtil.mappingIsExpired(mappingData)) {
-            return handleSbExpiredMapping(dst, xtrId, mappingData);
-        } else {
-            return mappingData;
+        while (mappingData != null && MappingMergeUtil.mappingIsExpired(mappingData)) {
+            // If the mappingData is expired, handleSbExpiredMapping() will run merge for it if merge is enabled,
+            // otherwise it will remove the expired mapping, returning null.
+            MappingData mergedMappingData = handleSbExpiredMapping(dst, xtrId, mappingData);
+            if (mergedMappingData != null) {
+                return mergedMappingData;
+            }
+            // If the expired mapping was removed, we look up the original query again
+            mappingData = (MappingData) smc.getMapping(dst, xtrId);
         }
+        return mappingData;
     }
 
     public MappingData handleSbExpiredMapping(Eid key, XtrId xtrId, MappingData mappingData) {
@@ -412,21 +522,29 @@ public class MappingSystem implements IMappingSystem {
     }
 
     private void removeSbXtrIdSpecificMapping(Eid key, XtrId xtrId, MappingData mappingData) {
+        if (LOG.isDebugEnabled()) {
+            LOG.debug("DAO: Removing southbound mapping for EID {}, xTR-ID {}",
+                    LispAddressStringifier.getString(key),
+                    LispAddressStringifier.getString(xtrId));
+        }
         smc.removeMapping(key, xtrId);
         dsbe.removeXtrIdMapping(DSBEInputUtil.toXtrIdMapping(mappingData));
     }
 
-    @SuppressWarnings("unchecked")
     private void removeSbMapping(Eid key, MappingData mappingData) {
         if (mappingData != null && mappingData.getXtrId() != null) {
             removeSbXtrIdSpecificMapping(key, mappingData.getXtrId(), mappingData);
         }
 
         removeFromSbTimeoutService(key);
-        Set<Subscriber> subscribers = (Set<Subscriber>) getData(MappingOrigin.Southbound, key, SubKeys.SUBSCRIBERS);
+        final Set<Subscriber> subscribers = getSubscribers(key);
+        if (LOG.isDebugEnabled()) {
+            LOG.debug("DAO: Removing southbound mapping for EID {}", LispAddressStringifier.getString(key));
+        }
         smc.removeMapping(key);
         dsbe.removeMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, key, mappingData));
-        notifyChange(mappingData, subscribers, null, MappingChange.Removed);
+        publishNotification(mappingData.getRecord(), null, subscribers, null, MappingChange.Removed);
+        removeSubscribersConditionally(MappingOrigin.Southbound, key);
     }
 
     private void removeFromSbTimeoutService(Eid key) {
@@ -472,88 +590,165 @@ public class MappingSystem implements IMappingSystem {
     }
 
     @Override
-    @SuppressWarnings("unchecked")
+    public Set<Eid> 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<Subscriber> subscribers = null;
         Set<Subscriber> 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() && mapping != null) {
+            LOG.trace(mapping.getString());
+        }
+
+        MappingRecord notificationMapping = null;
+
         if (mapping != null) {
-            MappingData notificationMapping = mapping;
-            subscribers = (Set<Subscriber>) getData(MappingOrigin.Southbound, key, SubKeys.SUBSCRIBERS);
+            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);
-                dstSubscribers = (Set<Subscriber>) getData(MappingOrigin.Southbound, dstAddr, SubKeys.SUBSCRIBERS);
-                if (!(mapping.getRecord().getEid().getAddress() instanceof SourceDestKey)) {
-                    notificationMapping = new MappingData(new MappingRecordBuilder().setEid(key).build());
-                }
+                dstAddr = SourceDestKeyHelper.getDstBinary(key);
+                dstSubscribers = getSubscribers(dstAddr);
             }
-            notifyChange(notificationMapping, subscribers, dstSubscribers, MappingChange.Removed);
         }
 
-        if (origin == MappingOrigin.Northbound) {
-            removeData(MappingOrigin.Southbound, key, SubKeys.SUBSCRIBERS);
-        }
+        removeSubscribersConditionally(origin, key);
 
         if (origin == MappingOrigin.Southbound) {
             removeFromSbTimeoutService(key);
-            if (mapping != null && mapping.isPositive().or(false)) {
-                mergeNegativePrefixes(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) {
+            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<Subscriber> subscribers = getSubscribers(eid);
+
+        Set<Subscriber> 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);
+        }
+
+        // No reason to send a notification when no subscribers exist
+        if (subscribers != null || dstSubscribers != null) {
+            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<Eid> childPrefixes = getSubtree(MappingOrigin.Southbound, eid);
+        if (childPrefixes == null || childPrefixes.isEmpty()) {
+            return;
+        }
+
+        childPrefixes.remove(eid);
+        for (Eid prefix : childPrefixes) {
+            Set<Subscriber> subscribers = getSubscribers(prefix);
+            // No reason to send a notification when no subscribers exist
+            if (subscribers != null) {
+                publishNotification(mapping, prefix, subscribers, null, mappingChange);
             }
         }
-        tableMap.get(origin).removeMapping(key);
     }
 
-    private void notifyChange(MappingData mapping, Set<Subscriber> subscribers, Set<Subscriber> dstSubscribers,
-            MappingChange mappingChange) {
-        MappingChanged notification = MSNotificationInputUtil.toMappingChanged(mapping, subscribers, dstSubscribers,
-                mappingChange);
+    private void publishNotification(MappingRecord mapping, Eid eid, Set<Subscriber> subscribers,
+                                     Set<Subscriber> 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.
      */
     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<Eid, MappingData> 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));
     }
 
     private static Eid getVirtualParent(Eid eid) {
         if (eid.getAddress() instanceof Ipv4PrefixBinary) {
             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
-            short parentPrefixLength = (short) (prefix.getIpv4MaskLength() - 1);
+            short parentPrefixLength = (short) (prefix.getIpv4MaskLength().toJava() - 1);
             byte[] parentPrefix = MaskUtil.normalizeByteArray(prefix.getIpv4AddressBinary().getValue(),
                     parentPrefixLength);
             return LispAddressUtil.asIpv4PrefixBinaryEid(eid, parentPrefix, parentPrefixLength);
         } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
-            short parentPrefixLength = (short) (prefix.getIpv6MaskLength() - 1);
+            short parentPrefixLength = (short) (prefix.getIpv6MaskLength().toJava() - 1);
             byte[] parentPrefix = MaskUtil.normalizeByteArray(prefix.getIpv6AddressBinary().getValue(),
                     parentPrefixLength);
             return LispAddressUtil.asIpv6PrefixBinaryEid(eid, parentPrefix, parentPrefixLength);
@@ -561,6 +756,63 @@ public class MappingSystem implements IMappingSystem {
         return null;
     }
 
+    @Override
+    public synchronized void subscribe(Subscriber subscriber, Eid subscribedEid) {
+        Set<Subscriber> subscribers = getSubscribers(subscribedEid);
+        if (subscribers == null) {
+            subscribers = Sets.newConcurrentHashSet();
+        } else if (subscribers.contains(subscriber)) {
+            // If there is an entry already for this subscriber, remove it, so that it gets the new timestamp
+            subscribers.remove(subscriber);
+        }
+        if (LOG.isDebugEnabled()) {
+            LOG.debug("Adding new subscriber {} for EID {}", subscriber.getString(),
+                    LispAddressStringifier.getString(subscribedEid));
+        }
+        subscribers.add(subscriber);
+        addSubscribers(subscribedEid, subscribers);
+    }
+
+    private void addSubscribers(Eid address, Set<Subscriber> subscribers) {
+        LoggingUtil.logSubscribers(LOG, address, subscribers);
+        subscriberdb.put(address, subscribers);
+    }
+
+    @Override
+    public Set<Subscriber> getSubscribers(Eid address) {
+        if (LOG.isDebugEnabled()) {
+            LOG.debug("Retrieving subscribers for EID {}", LispAddressStringifier.getString(address));
+        }
+
+        Set<Subscriber> subscribers = subscriberdb.get(address);
+        LoggingUtil.logSubscribers(LOG, address, subscribers);
+        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));
+        }
+        subscriberdb.remove(address);
+    }
+
     @Override
     public void addAuthenticationKey(Eid key, MappingAuthkey authKey) {
         LOG.debug("Adding authentication key '{}' with key-ID {} for {}", authKey.getKeyString(), authKey.getKeyType(),
@@ -658,7 +910,9 @@ public class MappingSystem implements IMappingSystem {
 
     @Override
     public String printMappings() {
-        final StringBuffer sb = new StringBuffer();
+        sbMappingTimeoutService.removeExpiredMappings();
+
+        final StringBuilder sb = new StringBuilder();
         sb.append("Policy map-cache\n----------------\n");
         sb.append(pmc.printMappings());
         sb.append("\nSouthbound map-cache\n--------------------\n");
@@ -668,11 +922,27 @@ public class MappingSystem implements IMappingSystem {
 
     @Override
     public String prettyPrintMappings() {
-        final StringBuffer sb = new StringBuffer();
+        sbMappingTimeoutService.removeExpiredMappings();
+
+        final StringBuilder sb = new StringBuilder();
         sb.append("Policy map-cache\n----------------\n");
         sb.append(pmc.prettyPrintMappings());
         sb.append("\nSouthbound map-cache\n--------------------\n");
         sb.append(smc.prettyPrintMappings());
+        sb.append("\nSubscribers\n-----------\n");
+        sb.append(prettyPrintSubscribers(subscriberdb));
+        return sb.toString();
+    }
+
+    private static String prettyPrintSubscribers(Map<Eid, Set<Subscriber>> subscribers) {
+        final StringBuilder sb = new StringBuilder();
+        for (Eid eid: subscribers.keySet()) {
+            sb.append("\n  ");
+            sb.append(LispAddressStringifier.getString(eid));
+            sb.append("\n");
+            sb.append(LispMapCacheStringifier.prettyPrintSubscriberSet(subscribers.get(eid), 4));
+            sb.append("\n");
+        }
         return sb.toString();
     }
 
@@ -688,6 +958,7 @@ public class MappingSystem implements IMappingSystem {
 
     public void cleanCaches() {
         dao.removeAll();
+        subscriberdb.clear();
         buildMapCaches();
     }