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