mappingservice/implementation/src/main/java/org/opendaylight/lispflowmapping/implementation/util/MappingMergeUtil.java

   1 /*
   2  * Copyright (c) 2016 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.util;
   9
  10 import com.google.common.base.Preconditions;
  11 import java.util.ArrayList;
  12 import java.util.Date;
  13 import java.util.HashMap;
  14 import java.util.LinkedHashMap;
  15 import java.util.List;
  16 import java.util.Map;
  17 import java.util.Set;
  18 import org.opendaylight.lispflowmapping.config.ConfigIni;
  19 import org.opendaylight.lispflowmapping.lisp.type.MappingData;
  20 import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil;
  21 import org.opendaylight.lispflowmapping.lisp.util.MaskUtil;
  22 import org.opendaylight.lispflowmapping.lisp.util.SourceDestKeyHelper;
  23 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IpPrefix;
  24 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv4Prefix;
  25 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.Ipv6Prefix;
  26 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.SimpleAddress;
  27 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.Address;
  28 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.source.dest.key.SourceDestKey;
  29 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.source.dest.key.SourceDestKeyBuilder;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.inet.binary.types.rev160303.IpAddressBinary;
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.XtrId;
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecord;
  33 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecordBuilder;
  34 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecord;
  35 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecordBuilder;
  36 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.rloc.container.Rloc;
  37 import org.slf4j.Logger;
  38 import org.slf4j.LoggerFactory;
  39
  40 /**
  41  * Utility class to implement merging of locator sets.
  42  *
  43  * @author Lorand Jakab
  44  *
  45  */
  46 public final class MappingMergeUtil {
  47     protected static final Logger LOG = LoggerFactory.getLogger(MappingMergeUtil.class);
  48
  49     // Utility class, should not be instantiated
  50     private MappingMergeUtil() {
  51     }
  52
  53     private static void mergeCommonMappingRecordFields(MappingRecordBuilder mrb, MappingRecord record) {
  54         // Set xTR-ID and site-ID from the current mapping, it help with determining the timestamp
  55         mrb.setXtrId(record.getXtrId());
  56         mrb.setSiteId(record.getSiteId());
  57         // For the TTL value we take the minimum of all records
  58         mrb.setRecordTtl(Math.min(mrb.getRecordTtl(), record.getRecordTtl()));
  59         if (!mrb.getAction().equals(record.getAction())) {
  60             LOG.warn("Mapping merge operation: actions are different, which one is used is undefined");
  61         }
  62         if (mrb.isAuthoritative() != record.isAuthoritative()) {
  63             LOG.warn("Mapping merge operation: authoritative status is different, which one is used is undefined");
  64         }
  65         if (!mrb.getEid().equals(record.getEid())) {
  66             LOG.warn("Mapping merge operation: EID records are different, which one is used is undefined");
  67         }
  68     }
  69
  70     private static LocatorRecord mergeLocators(LocatorRecord existingLocator, LocatorRecord newLocator) {
  71         if (existingLocator.isLocalLocator()) {
  72             return existingLocator;
  73         }
  74         return newLocator;
  75     }
  76
  77     private static int compareLocators(LocatorRecord one, LocatorRecord two) {
  78         byte[] oneIp = LispAddressUtil.ipAddressToByteArray(one.getRloc().getAddress());
  79         byte[] twoIp = LispAddressUtil.ipAddressToByteArray(two.getRloc().getAddress());
  80         return LispAddressUtil.compareIpAddressByteArrays(oneIp, twoIp);
  81     }
  82
  83     private static void mergeLocatorRecords(MappingRecordBuilder mrb, MappingRecord newRecord) {
  84         List<LocatorRecord> locators = mrb.getLocatorRecord();
  85
  86         // We assume locators are unique and sorted and don't show up several times (with different or identical
  87         // p/w/mp/mw), so we create a LinkedHashMap (which preserves order) of the locators from the existing merged
  88         // record, keyed by the Rloc
  89         Map<Rloc, LocatorRecord> locatorMap = new LinkedHashMap<Rloc, LocatorRecord>();
  90
  91         // All locators to be added to the merge set are first stored in this list
  92         List<LocatorRecord> newLocatorList = new ArrayList<LocatorRecord>();
  93
  94         for (LocatorRecord locator : locators) {
  95             locatorMap.put(locator.getRloc(), locator);
  96         }
  97         for (LocatorRecord newLocator : newRecord.getLocatorRecord()) {
  98             Rloc newRloc = newLocator.getRloc();
  99             if (locatorMap.containsKey(newRloc)) {
 100                 // overlapping locator
 101                 if (locatorMap.get(newRloc).equals(newLocator)) {
 102                     continue;
 103                 } else {
 104                     LocatorRecord mergedLocator = mergeLocators(locatorMap.get(newRloc), newLocator);
 105                     newLocatorList.add(mergedLocator);
 106                 }
 107             } else {
 108                 // new locator
 109                 newLocatorList.add(newLocator);
 110             }
 111         }
 112
 113         // Build new merged and sorted locator set if need be
 114         if (newLocatorList.size() != 0) {
 115             List<LocatorRecord> mergedLocators = new ArrayList<LocatorRecord>();
 116
 117             int mlocIt = 0;
 118             int locIt = 0;
 119             while (mlocIt < newLocatorList.size() && locIt < locators.size()) {
 120                 int cmp = compareLocators(locators.get(locIt), newLocatorList.get(mlocIt));
 121                 if (cmp < 0) {
 122                     mergedLocators.add(locators.get(locIt));
 123                     locIt++;
 124                 } else if (cmp > 0) {
 125                     mergedLocators.add(newLocatorList.get(mlocIt));
 126                     mlocIt++;
 127                 } else {
 128                     // when a locator appears in both lists, keep the new (merged) one and skip the old
 129                     mergedLocators.add(newLocatorList.get(mlocIt));
 130                     mlocIt++;
 131                     locIt++;
 132                 }
 133             }
 134             while (locIt < locators.size()) {
 135                 mergedLocators.add(locators.get(locIt));
 136                 locIt++;
 137             }
 138             while (mlocIt < newLocatorList.size()) {
 139                 mergedLocators.add(newLocatorList.get(mlocIt));
 140                 mlocIt++;
 141             }
 142             mrb.setLocatorRecord(mergedLocators);
 143         }
 144     }
 145
 146     public static MappingRecord mergeMappings(MappingRecord currentMergedMapping, MappingRecord newMapping,
 147             XtrId xtrId, Date regdate) {
 148         if (currentMergedMapping == null) {
 149             return newMapping;
 150         }
 151
 152         MappingRecordBuilder mrb = new MappingRecordBuilder(currentMergedMapping);
 153         mergeCommonMappingRecordFields(mrb, newMapping);
 154         mergeLocatorRecords(mrb, newMapping);
 155
 156         if (xtrId != null) {
 157             mrb.setXtrId(xtrId);
 158             mrb.setTimestamp(regdate.getTime());
 159         }
 160
 161         return mrb.build();
 162     }
 163
 164     public static MappingData mergeXtrIdMappings(List<Object> mappingDataList, List<XtrId> expiredMappings,
 165             Set<IpAddressBinary> sourceRlocs) {
 166         MappingRecordBuilder mrb = null;
 167         XtrId xtrId = null;
 168         Long timestamp = Long.MAX_VALUE;
 169
 170         for (int i = 0; i < mappingDataList.size(); i++) {
 171             MappingData mappingData = (MappingData) mappingDataList.get(i);
 172             MappingRecord record = mappingData.getRecord();
 173
 174             // Skip expired mappings and add them to a list to be returned to the caller
 175             if (timestampIsExpired(mappingData.getTimestamp())) {
 176                 expiredMappings.add(mappingData.getXtrId());
 177                 continue;
 178             }
 179
 180             if (mrb == null) {
 181                 mrb = new MappingRecordBuilder(record);
 182             }
 183
 184             // Save the oldest valid timestamp
 185             if (mappingData.getTimestamp().getTime() < timestamp) {
 186                 timestamp = mappingData.getTimestamp().getTime();
 187                 xtrId = mappingData.getXtrId();
 188             }
 189
 190             // Merge record fields and locators
 191             mergeCommonMappingRecordFields(mrb, record);
 192             mergeLocatorRecords(mrb, record);
 193
 194             // Save source locator for use in Map-Notify
 195             sourceRlocs.add(record.getSourceRloc());
 196         }
 197
 198         if (mrb == null) {
 199             LOG.warn("All mappings expired when merging! Unexpected!");
 200             return null;
 201         }
 202         mrb.setXtrId(xtrId);
 203
 204         return new MappingData(mrb.build(), new Date(timestamp));
 205     }
 206
 207     /*
 208      * The following three methods intentionally throw an exception when their argument is null, because they can't
 209      * decide based on that to return true or false, so the calling function should do that and only call these with
 210      * non-null arguments
 211      */
 212     public static boolean mappingIsExpired(MappingData mappingData) {
 213         Preconditions.checkNotNull(mappingData, "mapping should not be null!");
 214         if (mappingData.getTimestamp() != null) {
 215             return timestampIsExpired(mappingData.getTimestamp());
 216         }
 217         return false;
 218     }
 219
 220     public static boolean timestampIsExpired(Date timestamp) {
 221         Preconditions.checkNotNull(timestamp, "timestamp should not be null!");
 222         return timestampIsExpired(timestamp.getTime());
 223     }
 224
 225     public static boolean timestampIsExpired(Long timestamp) {
 226         Preconditions.checkNotNull(timestamp, "timestamp should not be null!");
 227         if ((System.currentTimeMillis() - timestamp) > ConfigIni.getInstance().getRegistrationValiditySb() ) {
 228             return true;
 229         }
 230         return false;
 231     }
 232
 233     public static MappingData computeNbSbIntersection(MappingData nbMappingData,
 234             MappingData sbMappingData) {
 235         return new MappingData(computeNbSbIntersection(nbMappingData.getRecord(), sbMappingData.getRecord()));
 236     }
 237
 238     private static MappingRecord computeNbSbIntersection(MappingRecord nbMapping, MappingRecord sbMapping) {
 239         // returns a MappingRecord which has the more specific EID, and intersection of locator records.
 240         // If locators intersection is empty, original NB mapping is returned.
 241         // The intersection is only computed for mappings with maskable EIDs.
 242         // Supports both maskable and non-maskable EIDs
 243
 244         MappingRecordBuilder mrb = new MappingRecordBuilder(nbMapping);
 245
 246         if (MaskUtil.isMaskable(sbMapping.getEid().getAddress())
 247                 && MaskUtil.isMaskable(nbMapping.getEid().getAddress())) {
 248
 249             short sbMask = MaskUtil.getMaskForAddress(sbMapping.getEid().getAddress());
 250             short nbMask = MaskUtil.getMaskForAddress(nbMapping.getEid().getAddress());
 251
 252             if (nbMapping.getEid().getAddress() instanceof org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang
 253                     .ietf.lisp.address.types.rev151105.lisp.address.address.SourceDestKey) {
 254                 nbMask = SourceDestKeyHelper.getDstMask(nbMapping.getEid());
 255                 if ( nbMask < sbMask) {
 256                     // We have to create a new SourceDest EID, where the source is same as the
 257                     // one in NB record, and dest EID is the more specific from SB mapping record.
 258
 259                     SourceDestKey srcDstKey = ((org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp
 260                             .address.types.rev151105.lisp.address.address.SourceDestKey) nbMapping.getEid()
 261                             .getAddress()).getSourceDestKey();
 262                     SourceDestKeyBuilder sdb = new SourceDestKeyBuilder(srcDstKey);
 263                     sdb.setDest(new SimpleAddress(getIpPrefix(sbMapping.getEid().getAddress())));
 264                     mrb.setEid(LispAddressUtil.asSrcDstEid(sdb.build(), nbMapping.getEid().getVirtualNetworkId()));
 265                 }
 266             } else if (nbMask < sbMask) {
 267                 // Both EIDs are IP prefixes. SB mapping is a subprefix so we have to update EID intersection
 268                 mrb.setEid(sbMapping.getEid());
 269             }
 270         }
 271         // find and update locators intersection if not empty
 272         List<LocatorRecord> commonLocators = getCommonLocatorRecords(nbMapping, sbMapping);
 273         if (commonLocators != null && !commonLocators.isEmpty()) {
 274             mrb.setLocatorRecord(commonLocators);
 275         }
 276
 277         return mrb.build();
 278     }
 279
 280     private static List<LocatorRecord> getCommonLocatorRecords(MappingRecord nbMapping, MappingRecord sbMapping) {
 281         // This method updates the MappingRecord builder with the intersection of the locator records
 282         // from the two mappings. NB mapping records fields have precedence, only Priority is updated
 283         // from SB mapping if p is 255.
 284
 285         // Return null when NB is a negative mapping
 286         if (nbMapping.getLocatorRecord() == null || nbMapping.getLocatorRecord().isEmpty()) {
 287             return null;
 288         }
 289
 290         List<LocatorRecord> sbLocators = sbMapping.getLocatorRecord();
 291
 292         // We assume locators are unique and don't show up several times (with different or identical p/w/mp/mw),
 293         // so we create a HashMap of the locators from the SB mapping record, keyed by the Rloc
 294         Map<Rloc, LocatorRecord> sbLocatorMap = new HashMap<Rloc, LocatorRecord>();
 295         for (LocatorRecord locator : sbLocators) {
 296             sbLocatorMap.put(locator.getRloc(), locator);
 297         }
 298
 299         // Gradually building final list of common locators, in order that they appear in NB Mapping
 300         List<LocatorRecord> commonLocators = new ArrayList<LocatorRecord>();
 301
 302         for (LocatorRecord nbLocator : nbMapping.getLocatorRecord()) {
 303             Rloc nbRloc = nbLocator.getRloc();
 304             if (sbLocatorMap.containsKey(nbRloc)) {
 305                 // common locator found. use the NB record as the common locator.
 306
 307                 if (sbLocatorMap.get(nbRloc).getPriority() == (short) 255) {
 308                     // if SB locator has p == 255 then common locator takes all NB fields except for p
 309                     // which must be set to 255
 310                     LocatorRecordBuilder lrb = new LocatorRecordBuilder(nbLocator);
 311                     lrb.setPriority((short) 255);
 312                     commonLocators.add(lrb.build());
 313                 } else {
 314                     commonLocators.add(nbLocator);
 315                 }
 316             }
 317         }
 318         return commonLocators;
 319     }
 320
 321     private static IpPrefix getIpPrefix(Address address) {
 322         IpPrefix ipPrefix = null;
 323
 324         if (address instanceof org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns
 325                 .yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv4Prefix) {
 326             org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp
 327                     .address.address.Ipv4Prefix lispPrefix = (org.opendaylight.yang.gen.v1.urn.ietf.params
 328                     .xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv4Prefix) address;
 329
 330             Ipv4Prefix inetPrefix = new Ipv4Prefix(lispPrefix.getIpv4Prefix());
 331             ipPrefix = new IpPrefix(inetPrefix);
 332         } else if (address instanceof org.opendaylight.yang.gen.v1.urn.ietf.params
 333                 .xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv6Prefix) {
 334             org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp
 335                     .address.address.Ipv6Prefix lispPrefix = (org.opendaylight.yang.gen.v1.urn.ietf.params
 336                     .xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.Ipv6Prefix) address;
 337
 338             Ipv6Prefix inetPrefix = new Ipv6Prefix(lispPrefix.getIpv6Prefix());
 339             ipPrefix = new IpPrefix(inetPrefix);
 340         } else {
 341             LOG.warn("Southbound mapping address is not an IpPrefix");
 342         }
 343         return ipPrefix;
 344     }
 345 }