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