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