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