mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/MappingSystem.java

   1 /*
   2  * Copyright (c) 2015, 2017 Cisco Systems, Inc.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8
   9 package org.opendaylight.lispflowmapping.implementation;
  10
  11 import com.google.common.collect.Sets;
  12 import java.util.ArrayList;
  13 import java.util.Collections;
  14 import java.util.Date;
  15 import java.util.EnumMap;
  16 import java.util.HashMap;
  17 import java.util.HashSet;
  18 import java.util.List;
  19 import java.util.Map;
  20 import java.util.Set;
  21 import java.util.concurrent.ConcurrentHashMap;
  22 import org.opendaylight.controller.md.sal.binding.api.NotificationPublishService;
  23 import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
  24 import org.opendaylight.lispflowmapping.config.ConfigIni;
  25 import org.opendaylight.lispflowmapping.dsbackend.DataStoreBackEnd;
  26 import org.opendaylight.lispflowmapping.implementation.timebucket.implementation.TimeBucketMappingTimeoutService;
  27 import org.opendaylight.lispflowmapping.implementation.timebucket.interfaces.ISouthBoundMappingTimeoutService;
  28 import org.opendaylight.lispflowmapping.implementation.util.DSBEInputUtil;
  29 import org.opendaylight.lispflowmapping.implementation.util.LoggingUtil;
  30 import org.opendaylight.lispflowmapping.implementation.util.MSNotificationInputUtil;
  31 import org.opendaylight.lispflowmapping.implementation.util.MappingMergeUtil;
  32 import org.opendaylight.lispflowmapping.interfaces.dao.ILispDAO;
  33 import org.opendaylight.lispflowmapping.interfaces.dao.SubKeys;
  34 import org.opendaylight.lispflowmapping.interfaces.dao.Subscriber;
  35 import org.opendaylight.lispflowmapping.interfaces.mapcache.IAuthKeyDb;
  36 import org.opendaylight.lispflowmapping.interfaces.mapcache.ILispMapCache;
  37 import org.opendaylight.lispflowmapping.interfaces.mapcache.IMapCache;
  38 import org.opendaylight.lispflowmapping.interfaces.mapcache.IMappingSystem;
  39 import org.opendaylight.lispflowmapping.interfaces.mappingservice.IMappingService;
  40 import org.opendaylight.lispflowmapping.lisp.type.LispMessage;
  41 import org.opendaylight.lispflowmapping.lisp.type.MappingData;
  42 import org.opendaylight.lispflowmapping.lisp.util.LispAddressStringifier;
  43 import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil;
  44 import org.opendaylight.lispflowmapping.lisp.util.MaskUtil;
  45 import org.opendaylight.lispflowmapping.lisp.util.SourceDestKeyHelper;
  46 import org.opendaylight.lispflowmapping.mapcache.AuthKeyDb;
  47 import org.opendaylight.lispflowmapping.mapcache.MultiTableMapCache;
  48 import org.opendaylight.lispflowmapping.mapcache.SimpleMapCache;
  49 import org.opendaylight.lispflowmapping.mapcache.lisp.LispMapCacheStringifier;
  50 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.SimpleAddress;
  51 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.ExplicitLocatorPath;
  52 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv4;
  53 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv6;
  54 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.ServicePath;
  55 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.SourceDestKey;
  56 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.explicit.locator.path.explicit.locator.path.Hop;
  57 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.inet.binary.types.rev160303.IpAddressBinary;
  58 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.Ipv4PrefixBinaryAfi;
  59 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.Ipv6PrefixBinaryAfi;
  60 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv4PrefixBinary;
  61 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv6PrefixBinary;
  62 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.XtrId;
  63 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.eid.container.Eid;
  64 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecord;
  65 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecordBuilder;
  66 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.authkey.container.MappingAuthkey;
  67 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecord;
  68 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecordBuilder;
  69 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.rloc.container.Rloc;
  70 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingChange;
  71 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.MappingOrigin;
  72 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.db.instance.AuthenticationKey;
  73 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.mappingservice.rev150906.db.instance.Mapping;
  74 import org.slf4j.Logger;
  75 import org.slf4j.LoggerFactory;
  76
  77 /**
  78  * The Mapping System coordinates caching of md-sal stored mappings and if so configured enables longest prefix match
  79  * mapping lookups.
  80  *
  81  * @author Florin Coras
  82  * @author Lorand Jakab
  83  *
  84  */
  85 public class MappingSystem implements IMappingSystem {
  86     private static final Logger LOG = LoggerFactory.getLogger(MappingSystem.class);
  87     private static final String AUTH_KEY_TABLE = "authentication";
  88     //private static final int TTL_RLOC_TIMED_OUT = 1;
  89     private static final int TTL_NO_RLOC_KNOWN = ConfigIni.getInstance().getNegativeMappingTTL();
  90     private NotificationPublishService notificationPublishService;
  91     private boolean mappingMerge;
  92     private ILispDAO dao;
  93     private ILispDAO sdao;
  94     private ILispMapCache smc;
  95     private IMapCache pmc;
  96     private ConcurrentHashMap<Eid, Set<Subscriber>> subscriberdb = new ConcurrentHashMap<>();
  97     private IAuthKeyDb akdb;
  98     private final EnumMap<MappingOrigin, IMapCache> tableMap = new EnumMap<>(MappingOrigin.class);
  99     private DataStoreBackEnd dsbe;
 100     private boolean isMaster = false;
 101
 102     private ISouthBoundMappingTimeoutService sbMappingTimeoutService;
 103
 104     public MappingSystem(ILispDAO dao, boolean iterateMask, NotificationPublishService nps, boolean mappingMerge) {
 105         this.dao = dao;
 106         this.notificationPublishService = nps;
 107         this.mappingMerge = mappingMerge;
 108         buildMapCaches();
 109
 110         sbMappingTimeoutService = new TimeBucketMappingTimeoutService(ConfigIni.getInstance()
 111                 .getNumberOfBucketsInTimeBucketWheel(), ConfigIni.getInstance().getRegistrationValiditySb(),
 112                 this);
 113     }
 114
 115     public void setDataStoreBackEnd(DataStoreBackEnd dataStoreBackEnd) {
 116         this.dsbe = dataStoreBackEnd;
 117     }
 118
 119     @Override
 120     public void setMappingMerge(boolean mappingMerge) {
 121         this.mappingMerge = mappingMerge;
 122     }
 123
 124     @Override
 125     public void setIterateMask(boolean iterate) {
 126         LOG.error("Non-longest prefix match lookups are not properly supported, variable is set to true");
 127     }
 128
 129     public void initialize() {
 130         restoreDaoFromDatastore();
 131     }
 132
 133     private void buildMapCaches() {
 134         /*
 135          * There exists a direct relationship between MappingOrigins and the tables that are part of the MappingSystem.
 136          * Therefore, if a new origin is added, probably a new table should be instantiated here as well. Here we
 137          * instantiate a SimpleMapCache for southbound originated LISP mappings and a MultiTableMapCache for northbound
 138          * originated mappings. Use of FlatMapCache would be possible when no longest prefix match is needed at all,
 139          * but that option is no longer supported in the code, since it was never tested and may lead to unexpected
 140          * results.
 141          */
 142         sdao = dao.putTable(MappingOrigin.Southbound.toString());
 143         pmc = new MultiTableMapCache(dao.putTable(MappingOrigin.Northbound.toString()));
 144         smc = new SimpleMapCache(sdao);
 145         akdb = new AuthKeyDb(dao.putTable(AUTH_KEY_TABLE));
 146         tableMap.put(MappingOrigin.Northbound, pmc);
 147         tableMap.put(MappingOrigin.Southbound, smc);
 148     }
 149
 150     @Override
 151     public void updateMapping(MappingOrigin origin, Eid key, MappingData mappingData) {
 152         addMapping(origin, key, mappingData, MappingChange.Updated);
 153     }
 154
 155     @Override
 156     public void addMapping(MappingOrigin origin, Eid key, MappingData mappingData) {
 157         addMapping(origin, key, mappingData, MappingChange.Created);
 158     }
 159
 160     private void addMapping(MappingOrigin origin, Eid key, MappingData mappingData, MappingChange changeType) {
 161
 162         sbMappingTimeoutService.removeExpiredMappings();
 163
 164         if (mappingData == null) {
 165             LOG.warn("addMapping() called with null mapping, ignoring");
 166             return;
 167         }
 168
 169         if (origin == MappingOrigin.Southbound) {
 170             XtrId xtrId = mappingData.getXtrId();
 171             if (xtrId == null && mappingMerge && mappingData.isMergeEnabled()) {
 172                 LOG.warn("addMapping() called will null xTR-ID in MappingRecord, while merge is set, ignoring");
 173                 return;
 174             }
 175             if (xtrId != null && mappingMerge) {
 176                 if (mappingData.isMergeEnabled()) {
 177                     smc.addMapping(key, xtrId, mappingData);
 178                     handleMergedMapping(key);
 179                     return;
 180                 } else {
 181                     clearPresentXtrIdMappings(key);
 182                     smc.addMapping(key, xtrId, mappingData);
 183                 }
 184             }
 185             addOrRefreshMappingInTimeoutService(key, mappingData);
 186         }
 187
 188         tableMap.get(origin).addMapping(key, mappingData);
 189
 190         if (origin != MappingOrigin.Southbound) {
 191             // If a NB mapping is added, we need to check if it's covering negative mappings in SB, and remove those
 192             handleSbNegativeMappings(key);
 193             // Notifications for SB changes are sent in the SB code itself, so this is called for non-SB additions only
 194             notifyChange(key, mappingData.getRecord(), changeType);
 195         }
 196     }
 197
 198     @SuppressWarnings("unchecked")
 199     private void clearPresentXtrIdMappings(Eid key) {
 200         List<MappingData> allXtrMappingList = (List<MappingData>) (List<?>) smc.getAllXtrIdMappings(key);
 201
 202         if (((MappingData) smc.getMapping(key, (XtrId) null)).isMergeEnabled()) {
 203             LOG.trace("Different xTRs have different merge configuration!");
 204         }
 205
 206         for (MappingData mappingData : allXtrMappingList) {
 207             removeSbXtrIdSpecificMapping(key, mappingData.getXtrId(), mappingData);
 208         }
 209     }
 210
 211     private void addOrRefreshMappingInTimeoutService(Eid key, MappingData mappingData) {
 212         Integer oldBucketId = (Integer) smc.getData(key, SubKeys.TIME_BUCKET_ID);
 213         Integer updatedBucketId;
 214
 215         if (oldBucketId != null) {
 216             //refresh mapping
 217             updatedBucketId = sbMappingTimeoutService.refreshMapping(key, mappingData, oldBucketId);
 218         } else {
 219             updatedBucketId = sbMappingTimeoutService.addMapping(key, mappingData);
 220         }
 221
 222         smc.addData(key, SubKeys.TIME_BUCKET_ID, updatedBucketId);
 223     }
 224
 225     private void handleSbNegativeMappings(Eid key) {
 226         Set<Eid> childPrefixes = getSubtree(MappingOrigin.Southbound, key);
 227
 228         // We don't want to remove a newly added negative mapping, so remove it from the child set
 229         childPrefixes.remove(key);
 230
 231         LOG.trace("handleSbNegativeMappings(): subtree prefix set for EID {} (excluding the EID itself): {}",
 232                 LispAddressStringifier.getString(key),
 233                 LispAddressStringifier.getString(childPrefixes));
 234         if (childPrefixes == null || childPrefixes.isEmpty()) {
 235             // The assumption here is that negative prefixes are well maintained and never overlapping.
 236             // If we have children for the EID, no parent lookup should thus be necessary.
 237             Eid parentPrefix = smc.getCoveringLessSpecific(key);
 238             LOG.trace("handleSbNegativeMappings(): parent prefix for EID {}: {}",
 239                     LispAddressStringifier.getString(key),
 240                     LispAddressStringifier.getString(parentPrefix));
 241             handleSbNegativeMapping(parentPrefix);
 242             return;
 243         }
 244
 245         for (Eid prefix : childPrefixes) {
 246             handleSbNegativeMapping(prefix);
 247         }
 248     }
 249
 250     private void handleSbNegativeMapping(Eid key) {
 251         MappingData mappingData = getSbMappingWithExpiration(null, key, null);
 252         if (mappingData != null && mappingData.isNegative().or(false)) {
 253             removeSbMapping(mappingData.getRecord().getEid(), mappingData);
 254         }
 255     }
 256
 257     @Override
 258     public MappingData addNegativeMapping(Eid key) {
 259         MappingRecord mapping = buildNegativeMapping(key);
 260         MappingData mappingData = new MappingData(mapping);
 261         LOG.debug("Adding negative mapping for EID {}", LispAddressStringifier.getString(mapping.getEid()));
 262         LOG.trace(mappingData.getString());
 263         smc.addMapping(mapping.getEid(), mappingData);
 264         dsbe.addMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, mapping.getEid(), null, mappingData));
 265         return mappingData;
 266     }
 267
 268     private MappingRecord buildNegativeMapping(Eid eid) {
 269         MappingRecordBuilder recordBuilder = new MappingRecordBuilder();
 270         recordBuilder.setAuthoritative(false);
 271         recordBuilder.setMapVersion((short) 0);
 272         recordBuilder.setEid(eid);
 273         if (eid.getAddressType().equals(Ipv4PrefixBinaryAfi.class)
 274                 || eid.getAddressType().equals(Ipv6PrefixBinaryAfi.class)) {
 275             Eid widestNegativePrefix = getWidestNegativePrefix(eid);
 276             if (widestNegativePrefix != null) {
 277                 recordBuilder.setEid(widestNegativePrefix);
 278             }
 279         }
 280         recordBuilder.setAction(LispMessage.NEGATIVE_MAPPING_ACTION);
 281         //if (getAuthenticationKey(eid) != null) {
 282         //    recordBuilder.setRecordTtl(TTL_RLOC_TIMED_OUT);
 283         //} else {
 284         recordBuilder.setRecordTtl(TTL_NO_RLOC_KNOWN);
 285         //}
 286         return recordBuilder.build();
 287     }
 288
 289     /*
 290      * Since this method is only called when there is a hit in the southbound Map-Register cache, and that cache is
 291      * not used when merge is on, it's OK to ignore the effects of timestamp changes on merging for now.
 292      */
 293     public void refreshMappingRegistration(Eid key, XtrId xtrId, Long timestamp) {
 294
 295         sbMappingTimeoutService.removeExpiredMappings();
 296
 297         if (timestamp == null) {
 298             timestamp = System.currentTimeMillis();
 299         }
 300         MappingData mappingData = (MappingData) smc.getMapping(null, key);
 301         if (mappingData != null) {
 302             mappingData.setTimestamp(new Date(timestamp));
 303             addOrRefreshMappingInTimeoutService(key, mappingData);
 304         } else {
 305             LOG.warn("Could not update timestamp for EID {}, no mapping found", LispAddressStringifier.getString(key));
 306         }
 307         if (mappingMerge && xtrId != null) {
 308             MappingData xtrIdMappingData = (MappingData) smc.getMapping(key, xtrId);
 309             if (xtrIdMappingData != null) {
 310                 xtrIdMappingData.setTimestamp(new Date(timestamp));
 311             } else {
 312                 LOG.warn("Could not update timestamp for EID {} xTR-ID {}, no mapping found",
 313                         LispAddressStringifier.getString(key), LispAddressStringifier.getString(xtrId));
 314             }
 315         }
 316     }
 317
 318     private MappingData updateServicePathMappingRecord(MappingData mappingData, Eid eid) {
 319         // keep properties of original record
 320         MappingRecordBuilder recordBuilder = new MappingRecordBuilder(mappingData.getRecord());
 321         recordBuilder.setLocatorRecord(new ArrayList<LocatorRecord>());
 322
 323         // there should only be one locator record
 324         if (mappingData.getRecord().getLocatorRecord().size() != 1) {
 325             LOG.warn("MappingRecord associated to ServicePath EID has more than one locator!");
 326             return mappingData;
 327         }
 328
 329         LocatorRecord locatorRecord = mappingData.getRecord().getLocatorRecord().get(0);
 330         long serviceIndex = ((ServicePath) eid.getAddress()).getServicePath().getServiceIndex();
 331         int index = LispAddressUtil.STARTING_SERVICE_INDEX - (int) serviceIndex;
 332         Rloc rloc = locatorRecord.getRloc();
 333         if (rloc.getAddress() instanceof Ipv4 || rloc.getAddress() instanceof Ipv6) {
 334             if (index != 0) {
 335                 LOG.warn("Service Index should be 255 for simple IP RLOCs!");
 336             }
 337             return mappingData;
 338         } else if (rloc.getAddress() instanceof ExplicitLocatorPath) {
 339             ExplicitLocatorPath elp = (ExplicitLocatorPath) rloc.getAddress();
 340             List<Hop> hops = elp.getExplicitLocatorPath().getHop();
 341
 342             if (index < 0 || index > hops.size())  {
 343                 LOG.warn("Service Index out of bounds!");
 344                 return mappingData;
 345             }
 346
 347             SimpleAddress nextHop = hops.get(index).getAddress();
 348             LocatorRecordBuilder lrb = new LocatorRecordBuilder(locatorRecord);
 349             lrb.setRloc(LispAddressUtil.toRloc(nextHop));
 350             recordBuilder.getLocatorRecord().add(lrb.build());
 351             return new MappingData(recordBuilder.build());
 352         } else {
 353             LOG.warn("Nothing to do with ServicePath mapping record");
 354             return mappingData;
 355         }
 356     }
 357
 358     private MappingData handleMergedMapping(Eid key) {
 359         List<MappingData> expiredMappingDataList = new ArrayList<>();
 360         Set<IpAddressBinary> sourceRlocs = new HashSet<>();
 361
 362         MappingData mergedMappingData = MappingMergeUtil.mergeXtrIdMappings(smc.getAllXtrIdMappings(key),
 363                 expiredMappingDataList, sourceRlocs);
 364
 365         for (MappingData mappingData : expiredMappingDataList) {
 366             removeSbXtrIdSpecificMapping(key, mappingData.getXtrId(), mappingData);
 367         }
 368
 369         if (mergedMappingData != null) {
 370             smc.addMapping(key, mergedMappingData, sourceRlocs);
 371             dsbe.addMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, key, mergedMappingData));
 372             addOrRefreshMappingInTimeoutService(key, mergedMappingData);
 373         } else {
 374             removeSbMapping(key, mergedMappingData);
 375         }
 376         return mergedMappingData;
 377     }
 378
 379     @Override
 380     public MappingData getMapping(Eid src, Eid dst) {
 381         // NOTE: Currently we have two lookup algorithms implemented, which are configurable
 382
 383         if (ConfigIni.getInstance().getLookupPolicy() == IMappingService.LookupPolicy.NB_AND_SB) {
 384             return getMappingNbSbIntersection(src, dst);
 385         } else {
 386             return getMappingNbFirst(src, dst);
 387         }
 388     }
 389
 390     @Override
 391     public MappingData getMapping(Eid dst) {
 392         return getMapping((Eid) null, dst);
 393     }
 394
 395     @Override
 396     public MappingData getMapping(Eid src, Eid dst, XtrId xtrId) {
 397         // Note: If xtrId is null, we need to go through regular policy checking else Policy doesn't matter
 398
 399         if (xtrId == null) {
 400             return getMapping(src, dst);
 401         }
 402
 403         return getSbMappingWithExpiration(src, dst, xtrId);
 404     }
 405
 406     @Override
 407     public MappingData getMapping(MappingOrigin origin, Eid key) {
 408         if (origin.equals(MappingOrigin.Southbound)) {
 409             return getSbMappingWithExpiration(null, key, null);
 410         }
 411         return (MappingData) tableMap.get(origin).getMapping(null, key);
 412     }
 413
 414     private MappingData getMappingNbFirst(Eid src, Eid dst) {
 415
 416         // Default lookup policy is northboundFirst
 417         //lookupPolicy == NB_FIRST
 418
 419         MappingData nbMappingData = (MappingData) pmc.getMapping(src, dst);
 420
 421         if (nbMappingData == null) {
 422             return getSbMappingWithExpiration(src, dst, null);
 423         }
 424         if (dst.getAddress() instanceof ServicePath) {
 425             return updateServicePathMappingRecord(nbMappingData, dst);
 426         }
 427         return nbMappingData;
 428     }
 429
 430     private MappingData getMappingNbSbIntersection(Eid src, Eid dst) {
 431         //lookupPolicy == NB_AND_SB, we return intersection
 432         //of NB and SB mappings, or NB mapping if intersection is empty.
 433
 434         MappingData nbMappingData = (MappingData) pmc.getMapping(src, dst);
 435         if (nbMappingData == null) {
 436             return nbMappingData;
 437         }
 438         // no intersection for Service Path mappings
 439         if (dst.getAddress() instanceof ServicePath) {
 440             return updateServicePathMappingRecord(nbMappingData, dst);
 441         }
 442         MappingData sbMappingData = getSbMappingWithExpiration(src, dst, null);
 443         if (sbMappingData == null) {
 444             return nbMappingData;
 445         }
 446         // both NB and SB mappings exist. Compute intersection of the mappings
 447         return MappingMergeUtil.computeNbSbIntersection(nbMappingData, sbMappingData);
 448     }
 449
 450     private MappingData getSbMappingWithExpiration(Eid src, Eid dst, XtrId xtrId) {
 451         MappingData mappingData = (MappingData) smc.getMapping(dst, xtrId);
 452         if (mappingData != null && MappingMergeUtil.mappingIsExpired(mappingData)) {
 453             return handleSbExpiredMapping(dst, xtrId, mappingData);
 454         } else {
 455             return mappingData;
 456         }
 457     }
 458
 459     public MappingData handleSbExpiredMapping(Eid key, XtrId xtrId, MappingData mappingData) {
 460         if (mappingMerge && mappingData.isMergeEnabled()) {
 461             return handleMergedMapping(key);
 462         }
 463
 464         if (xtrId != null) {
 465             removeSbXtrIdSpecificMapping(key, xtrId, mappingData);
 466         } else {
 467             removeSbMapping(key, mappingData);
 468         }
 469         return null;
 470     }
 471
 472     private void removeSbXtrIdSpecificMapping(Eid key, XtrId xtrId, MappingData mappingData) {
 473         smc.removeMapping(key, xtrId);
 474         dsbe.removeXtrIdMapping(DSBEInputUtil.toXtrIdMapping(mappingData));
 475     }
 476
 477     private void removeSbMapping(Eid key, MappingData mappingData) {
 478         if (mappingData != null && mappingData.getXtrId() != null) {
 479             removeSbXtrIdSpecificMapping(key, mappingData.getXtrId(), mappingData);
 480         }
 481
 482         removeFromSbTimeoutService(key);
 483         Set<Subscriber> subscribers = getSubscribers(key);
 484         smc.removeMapping(key);
 485         dsbe.removeMapping(DSBEInputUtil.toMapping(MappingOrigin.Southbound, key, mappingData));
 486         publishNotification(mappingData.getRecord(), null, subscribers, null, MappingChange.Removed);
 487         removeSubscribersConditionally(MappingOrigin.Southbound, key);
 488     }
 489
 490     private void removeFromSbTimeoutService(Eid key) {
 491         Integer bucketId = (Integer) smc.getData(key, SubKeys.TIME_BUCKET_ID);
 492         if (bucketId != null) {
 493             sbMappingTimeoutService.removeMappingFromTimeoutService(key, bucketId);
 494         }
 495     }
 496
 497     @Override
 498     public Eid getWidestNegativePrefix(Eid key) {
 499         if (!MaskUtil.isMaskable(key.getAddress())) {
 500             LOG.warn("Widest negative prefix only makes sense for maskable addresses!");
 501             return null;
 502         }
 503
 504         // We assume that ILispMapCache#getWidestNegativeMapping() returns null for positive mappings, and 0/0
 505         // for empty cache.
 506         Eid nbPrefix = pmc.getWidestNegativeMapping(key);
 507         if (nbPrefix == null) {
 508             LOG.trace("getWidestNegativePrefix NB: positive mapping, returning null");
 509             return null;
 510         }
 511         if (LOG.isTraceEnabled()) {
 512             LOG.trace("getWidestNegativePrefix NB: {}", LispAddressStringifier.getString(nbPrefix));
 513         }
 514
 515         Eid sbPrefix = smc.getWidestNegativeMapping(key);
 516         if (sbPrefix == null) {
 517             LOG.trace("getWidestNegativePrefix SB: positive mapping, returning null");
 518             return null;
 519         }
 520         if (LOG.isTraceEnabled()) {
 521             LOG.trace("getWidestNegativePrefix SB: {}", LispAddressStringifier.getString(sbPrefix));
 522         }
 523
 524         // since prefixes overlap, just return the more specific (larger mask)
 525         if (LispAddressUtil.getIpPrefixMask(nbPrefix) < LispAddressUtil.getIpPrefixMask(sbPrefix)) {
 526             return sbPrefix;
 527         } else {
 528             return nbPrefix;
 529         }
 530     }
 531
 532     @Override
 533     public Set<Eid> getSubtree(MappingOrigin origin, Eid key) {
 534         if (!MaskUtil.isMaskable(key.getAddress())) {
 535             LOG.warn("Child prefixes only make sense for maskable addresses!");
 536             return Collections.emptySet();
 537         }
 538
 539         return tableMap.get(origin).getSubtree(key);
 540     }
 541
 542     @Override
 543     public void removeMapping(MappingOrigin origin, Eid key) {
 544         Eid dstAddr = null;
 545         Set<Subscriber> subscribers = null;
 546         Set<Subscriber> dstSubscribers = null;
 547         MappingData mapping = (MappingData) tableMap.get(origin).getMapping(null, key);
 548
 549         if (LOG.isDebugEnabled()) {
 550             LOG.debug("Removing mapping for EID {} from {}",
 551                     LispAddressStringifier.getString(key), origin);
 552         }
 553         if (LOG.isTraceEnabled() && mapping != null) {
 554             LOG.trace(mapping.getString());
 555         }
 556
 557         MappingRecord notificationMapping = null;
 558
 559         if (mapping != null) {
 560             notificationMapping = mapping.getRecord();
 561             subscribers = getSubscribers(key);
 562             // For SrcDst LCAF also send SMRs to Dst prefix
 563             if (key.getAddress() instanceof SourceDestKey) {
 564                 dstAddr = SourceDestKeyHelper.getDstBinary(key);
 565                 dstSubscribers = getSubscribers(dstAddr);
 566             }
 567         }
 568
 569         removeSubscribersConditionally(origin, key);
 570
 571         if (origin == MappingOrigin.Southbound) {
 572             removeFromSbTimeoutService(key);
 573         }
 574
 575         if (origin == MappingOrigin.Southbound && mapping != null && mapping.isPositive().or(false)) {
 576             mergeNegativePrefixes(key);
 577         } else {
 578             // mergeNegativePrefixes() above removes the mapping, so addNegativeMapping() will work correctly
 579             tableMap.get(origin).removeMapping(key);
 580         }
 581
 582         if (notificationMapping != null) {
 583             publishNotification(notificationMapping, key, subscribers, dstSubscribers, MappingChange.Removed);
 584             notifyChildren(key, notificationMapping, MappingChange.Removed);
 585             if (dstAddr != null) {
 586                 notifyChildren(dstAddr, notificationMapping, MappingChange.Removed);
 587             }
 588         }
 589     }
 590
 591     public void notifyChange(Eid eid, MappingRecord mapping, MappingChange mappingChange) {
 592         Set<Subscriber> subscribers = getSubscribers(eid);
 593
 594         Set<Subscriber> dstSubscribers = null;
 595         // For SrcDst LCAF also send SMRs to Dst prefix
 596         if (eid.getAddress() instanceof SourceDestKey) {
 597             Eid dstAddr = SourceDestKeyHelper.getDstBinary(eid);
 598             dstSubscribers = getSubscribers(dstAddr);
 599             notifyChildren(dstAddr, mapping, mappingChange);
 600         }
 601         publishNotification(mapping, eid, subscribers, dstSubscribers, mappingChange);
 602
 603         notifyChildren(eid, mapping, mappingChange);
 604     }
 605
 606     private void notifyChildren(Eid eid, MappingRecord mapping, MappingChange mappingChange) {
 607         // Update/created only happens for NB mappings. We assume no overlapping prefix support for NB mappings - so
 608         // this NB mapping should not have any children. Both for NB first and NB&SB cases all subscribers for SB
 609         // prefixes that are equal or more specific to this NB prefix have to be notified of the potential change.
 610         // Each subscriber is notified for the prefix that it is currently subscribed to, and MS should return to them
 611         // a Map-Reply with the same prefix and update mapping in cases of EID_INTERSECTION_RLOC_NB_FIRST which is a
 612         // new option we are creating TODO
 613         Set<Eid> childPrefixes = getSubtree(MappingOrigin.Southbound, eid);
 614         if (childPrefixes == null || childPrefixes.isEmpty()) {
 615             return;
 616         }
 617
 618         childPrefixes.remove(eid);
 619         for (Eid prefix : childPrefixes) {
 620             Set<Subscriber> subscribers = getSubscribers(prefix);
 621             publishNotification(mapping, prefix, subscribers, null, mappingChange);
 622         }
 623     }
 624
 625     private void publishNotification(MappingRecord mapping, Eid eid, Set<Subscriber> subscribers,
 626                                      Set<Subscriber> dstSubscribers, MappingChange mappingChange) {
 627         try {
 628             // The notifications are used for sending SMR.
 629             notificationPublishService.putNotification(MSNotificationInputUtil.toMappingChanged(
 630                     mapping, eid, subscribers, dstSubscribers, mappingChange));
 631         } catch (InterruptedException e) {
 632             LOG.warn("Notification publication interrupted!");
 633         }
 634     }
 635
 636     /*
 637      * Merges adjacent negative prefixes and notifies their subscribers.
 638      */
 639     private void mergeNegativePrefixes(Eid eid) {
 640         LOG.debug("Merging negative prefixes starting from EID {}", LispAddressStringifier.getString(eid));
 641
 642         // If we delete nodes while we walk up the radix trie the algorithm will give incorrect results, because
 643         // removals rearrange relationships in the trie. So we save prefixes to be removed into a HashMap.
 644         Map<Eid, MappingData> mergedMappings = new HashMap<>();
 645
 646         Eid currentNode = smc.getSiblingPrefix(eid);
 647         MappingData mapping = (MappingData) smc.getMapping(null, currentNode);
 648         if (mapping != null && mapping.isNegative().or(false)) {
 649             mergedMappings.put(currentNode, mapping);
 650         } else {
 651             return;
 652         }
 653
 654         Eid previousNode = currentNode;
 655         currentNode = smc.getVirtualParentSiblingPrefix(currentNode);
 656         while (currentNode != null) {
 657             mapping = (MappingData) smc.getMapping(null, currentNode);
 658             if (mapping != null && mapping.isNegative().or(false)) {
 659                 mergedMappings.put(currentNode, mapping);
 660             } else {
 661                 break;
 662             }
 663             previousNode = currentNode;
 664             currentNode = smc.getVirtualParentSiblingPrefix(previousNode);
 665         }
 666
 667         for (Eid key : mergedMappings.keySet()) {
 668             removeSbMapping(key, mergedMappings.get(key));
 669         }
 670         smc.removeMapping(eid);
 671
 672         addNegativeMapping(getVirtualParent(previousNode));
 673     }
 674
 675     private static Eid getVirtualParent(Eid eid) {
 676         if (eid.getAddress() instanceof Ipv4PrefixBinary) {
 677             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
 678             short parentPrefixLength = (short) (prefix.getIpv4MaskLength() - 1);
 679             byte[] parentPrefix = MaskUtil.normalizeByteArray(prefix.getIpv4AddressBinary().getValue(),
 680                     parentPrefixLength);
 681             return LispAddressUtil.asIpv4PrefixBinaryEid(eid, parentPrefix, parentPrefixLength);
 682         } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
 683             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
 684             short parentPrefixLength = (short) (prefix.getIpv6MaskLength() - 1);
 685             byte[] parentPrefix = MaskUtil.normalizeByteArray(prefix.getIpv6AddressBinary().getValue(),
 686                     parentPrefixLength);
 687             return LispAddressUtil.asIpv6PrefixBinaryEid(eid, parentPrefix, parentPrefixLength);
 688         }
 689         return null;
 690     }
 691
 692     @Override
 693     public synchronized void subscribe(Subscriber subscriber, Eid subscribedEid) {
 694         Set<Subscriber> subscribers = getSubscribers(subscribedEid);
 695         if (subscribers == null) {
 696             subscribers = Sets.newConcurrentHashSet();
 697         } else if (subscribers.contains(subscriber)) {
 698             // If there is an entry already for this subscriber, remove it, so that it gets the new timestamp
 699             subscribers.remove(subscriber);
 700         }
 701         if (LOG.isDebugEnabled()) {
 702             LOG.debug("Adding new subscriber {} for EID {}", subscriber.getString(),
 703                     LispAddressStringifier.getString(subscribedEid));
 704         }
 705         subscribers.add(subscriber);
 706         addSubscribers(subscribedEid, subscribers);
 707     }
 708
 709     private void addSubscribers(Eid address, Set<Subscriber> subscribers) {
 710         LoggingUtil.logSubscribers(LOG, address, subscribers);
 711         subscriberdb.put(address, subscribers);
 712     }
 713
 714     @Override
 715     public Set<Subscriber> getSubscribers(Eid address) {
 716         if (LOG.isDebugEnabled()) {
 717             LOG.debug("Retrieving subscribers for EID {}", LispAddressStringifier.getString(address));
 718         }
 719
 720         Set<Subscriber> subscribers = subscriberdb.get(address);
 721         LoggingUtil.logSubscribers(LOG, address, subscribers);
 722         return subscribers;
 723     }
 724
 725     /*
 726      * Only remove subscribers if there is no exact match mapping in the map-cache other than the one specified by
 727      * origin. Right now we only have two origins, but in case we will have more, we only need to update this method,
 728      * not the callers. We use getData() instead of getMapping to do exact match instead of longest prefix match.
 729      */
 730     private void removeSubscribersConditionally(MappingOrigin origin, Eid address) {
 731         if (origin == MappingOrigin.Southbound) {
 732             if (pmc.getData(address, SubKeys.RECORD) == null) {
 733                 removeSubscribers(address);
 734             }
 735         } else if (origin == MappingOrigin.Northbound) {
 736             if (smc.getData(address, SubKeys.RECORD) == null) {
 737                 removeSubscribers(address);
 738             }
 739         }
 740     }
 741
 742     private void removeSubscribers(Eid address) {
 743         if (LOG.isDebugEnabled()) {
 744             LOG.debug("Removing subscribers for EID {}", LispAddressStringifier.getString(address));
 745         }
 746         subscriberdb.remove(address);
 747     }
 748
 749     @Override
 750     public void addAuthenticationKey(Eid key, MappingAuthkey authKey) {
 751         LOG.debug("Adding authentication key '{}' with key-ID {} for {}", authKey.getKeyString(), authKey.getKeyType(),
 752                 LispAddressStringifier.getString(key));
 753         akdb.addAuthenticationKey(key, authKey);
 754     }
 755
 756     @Override
 757     public MappingAuthkey getAuthenticationKey(Eid key) {
 758         if (LOG.isDebugEnabled()) {
 759             LOG.debug("Retrieving authentication key for {}", LispAddressStringifier.getString(key));
 760         }
 761         return akdb.getAuthenticationKey(key);
 762     }
 763
 764     @Override
 765     public void removeAuthenticationKey(Eid key) {
 766         if (LOG.isDebugEnabled()) {
 767             LOG.debug("Removing authentication key for {}", LispAddressStringifier.getString(key));
 768         }
 769         akdb.removeAuthenticationKey(key);
 770     }
 771
 772     @Override
 773     public void addData(MappingOrigin origin, Eid key, String subKey, Object data) {
 774         if (LOG.isDebugEnabled()) {
 775             LOG.debug("Add data of {} for key {} and subkey {}", data.getClass(),
 776                     LispAddressStringifier.getString(key), subKey);
 777         }
 778         tableMap.get(origin).addData(key, subKey, data);
 779     }
 780
 781     @Override
 782     public Object getData(MappingOrigin origin, Eid key, String subKey) {
 783         if (LOG.isDebugEnabled()) {
 784             LOG.debug("Retrieving data for key {} and subkey {}", LispAddressStringifier.getString(key), subKey);
 785         }
 786         return tableMap.get(origin).getData(key, subKey);
 787     }
 788
 789     @Override
 790     public void removeData(MappingOrigin origin, Eid key, String subKey) {
 791         if (LOG.isDebugEnabled()) {
 792             LOG.debug("Removing data for key {} and subkey {}", LispAddressStringifier.getString(key), subKey);
 793         }
 794         tableMap.get(origin).removeData(key, subKey);
 795     }
 796
 797     @Override
 798     public Eid getParentPrefix(Eid key) {
 799         return smc.getParentPrefix(key);
 800     }
 801
 802
 803     /**
 804      * Restore all mappings and keys from mdsal datastore.
 805      */
 806     private void restoreDaoFromDatastore() {
 807         List<AuthenticationKey> authKeys = dsbe.getAllAuthenticationKeys();
 808         List<Mapping> mappings = dsbe.getAllMappings(LogicalDatastoreType.CONFIGURATION);
 809
 810         /*
 811          * XXX By default, the operational datastore is not persisted to disk, either at run-time, or on shutdown,
 812          * so the following will have no effect (getLastUpdateTimestamp() will fail, since it's reading from
 813          * the operational datastore, and even if it didn't getAllMappings() will fail anyway). According to rovarga it
 814          * should be possible to turn on persistence for the operational datastore editing
 815          * etc/opendaylight/karaf/05-clustering.xml, by setting <persistence>true</persistence>. At the time of writing
 816          * the below code block that didn't seem to work though.
 817          */
 818         Long lastUpdateTimestamp = dsbe.getLastUpdateTimestamp();
 819         if (lastUpdateTimestamp != null && System.currentTimeMillis() - lastUpdateTimestamp
 820                 > ConfigIni.getInstance().getRegistrationValiditySb()) {
 821             LOG.warn("Restore threshold passed, not restoring operational datastore into DAO");
 822         } else {
 823             mappings.addAll(dsbe.getAllMappings(LogicalDatastoreType.OPERATIONAL));
 824         }
 825         dsbe.removeLastUpdateTimestamp();
 826
 827         LOG.info("Restoring {} mappings and {} keys from datastore into DAO", mappings.size(), authKeys.size());
 828
 829         for (Mapping mapping : mappings) {
 830             addMapping(mapping.getOrigin(), mapping.getMappingRecord().getEid(),
 831                     new MappingData(mapping.getMappingRecord()));
 832         }
 833
 834         for (AuthenticationKey authKey : authKeys) {
 835             addAuthenticationKey(authKey.getEid(), authKey.getMappingAuthkey());
 836         }
 837     }
 838
 839     public void destroy() {
 840         LOG.info("Mapping System is being destroyed!");
 841         dsbe.saveLastUpdateTimestamp();
 842     }
 843
 844     @Override
 845     public String printMappings() {
 846         sbMappingTimeoutService.removeExpiredMappings();
 847
 848         final StringBuilder sb = new StringBuilder();
 849         sb.append("Policy map-cache\n----------------\n");
 850         sb.append(pmc.printMappings());
 851         sb.append("\nSouthbound map-cache\n--------------------\n");
 852         sb.append(smc.printMappings());
 853         return sb.toString();
 854     }
 855
 856     @Override
 857     public String prettyPrintMappings() {
 858         sbMappingTimeoutService.removeExpiredMappings();
 859
 860         final StringBuilder sb = new StringBuilder();
 861         sb.append("Policy map-cache\n----------------\n");
 862         sb.append(pmc.prettyPrintMappings());
 863         sb.append("\nSouthbound map-cache\n--------------------\n");
 864         sb.append(smc.prettyPrintMappings());
 865         sb.append("\nSubscribers\n-----------\n");
 866         sb.append(prettyPrintSubscribers(subscriberdb));
 867         return sb.toString();
 868     }
 869
 870     private static String prettyPrintSubscribers(Map<Eid, Set<Subscriber>> subscribers) {
 871         final StringBuilder sb = new StringBuilder();
 872         for (Eid eid: subscribers.keySet()) {
 873             sb.append("\n  ");
 874             sb.append(LispAddressStringifier.getString(eid));
 875             sb.append("\n");
 876             sb.append(LispMapCacheStringifier.prettyPrintSubscriberSet(subscribers.get(eid), 4));
 877             sb.append("\n");
 878         }
 879         return sb.toString();
 880     }
 881
 882     @Override
 883     public String printKeys() {
 884         return akdb.printKeys();
 885     }
 886
 887     @Override
 888     public String prettyPrintKeys() {
 889         return akdb.prettyPrintKeys();
 890     }
 891
 892     public void cleanCaches() {
 893         dao.removeAll();
 894         subscriberdb.clear();
 895         buildMapCaches();
 896     }
 897
 898     public void cleanSBMappings() {
 899         smc = new SimpleMapCache(sdao);
 900     }
 901
 902     @Override
 903     public void setIsMaster(boolean isMaster) {
 904         this.isMaster = isMaster;
 905     }
 906
 907     @Override
 908     public boolean isMaster() {
 909         return isMaster;
 910     }
 911 }