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