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.IpAddress;
  20 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev100924.IpPrefix;
  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.source.dest.key.SourceDestKey;
  23 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.lisp.address.types.rev151105.lisp.address.address.source.dest.key.SourceDestKeyBuilder;
  24 import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil;
  25 import org.opendaylight.lispflowmapping.lisp.util.MaskUtil;
  26 import org.opendaylight.lispflowmapping.lisp.util.SourceDestKeyHelper;
  27 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.XtrId;
  28 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecord;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.locatorrecords.LocatorRecordBuilder;
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecord;
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.mapping.record.container.MappingRecordBuilder;
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.rloc.container.Rloc;
  33 import org.slf4j.Logger;
  34 import org.slf4j.LoggerFactory;
  35
  36 import com.google.common.base.Preconditions;
  37
  38 /**
  39  * Utility class to implement merging of locator sets
  40  *
  41  * @author Lorand Jakab
  42  *
  43  */
  44 public final class MappingMergeUtil {
  45     protected static final Logger LOG = LoggerFactory.getLogger(MappingMergeUtil.class);
  46     // A mapping registration is valid for this many milliseconds
  47     private static final long REGISTRATION_VALIDITY = 200000L;
  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 a, LocatorRecord b) {
  78         InetAddress aInet = LispAddressUtil.ipAddressToInet(a.getRloc().getAddress());
  79         InetAddress bInet = LispAddressUtil.ipAddressToInet(b.getRloc().getAddress());
  80         return LispAddressUtil.compareInetAddresses(aInet, bInet);
  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 mlIt = 0, lIt = 0;
 118             while (mlIt < newLocatorList.size() && lIt < locators.size()) {
 119                 int cmp = compareLocators(locators.get(lIt), newLocatorList.get(mlIt));
 120                 if (cmp < 0) {
 121                     mergedLocators.add(locators.get(lIt));
 122                     lIt++;
 123                 } else if (cmp > 0) {
 124                     mergedLocators.add(newLocatorList.get(mlIt));
 125                     mlIt++;
 126                 } else {
 127                     // when a locator appears in both lists, keep the new (merged) one and skip the old
 128                     mergedLocators.add(newLocatorList.get(mlIt));
 129                     mlIt++;
 130                     lIt++;
 131                 }
 132             }
 133             while (lIt < locators.size()) {
 134                 mergedLocators.add(locators.get(lIt));
 135                 lIt++;
 136             }
 137             while (mlIt < newLocatorList.size()) {
 138                 mergedLocators.add(newLocatorList.get(mlIt));
 139                 mlIt++;
 140             }
 141             mrb.setLocatorRecord(mergedLocators);
 142         }
 143     }
 144
 145     public static MappingRecord mergeMappings(MappingRecord currentMergedMapping, MappingRecord newMapping,
 146             XtrId xtrId, Date regdate) {
 147         if (currentMergedMapping == null) {
 148             return newMapping;
 149         }
 150
 151         MappingRecordBuilder mrb = new MappingRecordBuilder(currentMergedMapping);
 152         mergeCommonMappingRecordFields(mrb, newMapping);
 153         mergeLocatorRecords(mrb, newMapping);
 154
 155         if (xtrId != null) {
 156             mrb.setXtrId(xtrId);
 157             mrb.setTimestamp(regdate.getTime());
 158         }
 159
 160         return mrb.build();
 161     }
 162
 163     public static MappingRecord mergeXtrIdMappings(List<Object> records, List<XtrId> expiredMappings,
 164             Set<IpAddress> sourceRlocs) {
 165         MappingRecordBuilder mrb = null;
 166         XtrId xtrId = null;
 167         Long timestamp = Long.MAX_VALUE;
 168
 169         for (int i = 0; i < records.size(); i++) {
 170             MappingRecord record = (MappingRecord) records.get(i);
 171
 172             // Skip expired mappings and add them to a list to be returned to the caller
 173             if (timestampIsExpired(record.getTimestamp())) {
 174                 expiredMappings.add(record.getXtrId());
 175                 continue;
 176             }
 177
 178             if (mrb == null) {
 179                 mrb = new MappingRecordBuilder((MappingRecord) records.get(i));
 180             }
 181
 182             // Save the oldest valid timestamp
 183             if (record.getTimestamp() < timestamp) {
 184                 timestamp = record.getTimestamp();
 185                 xtrId = record.getXtrId();
 186             }
 187
 188             // Merge record fields and locators
 189             mergeCommonMappingRecordFields(mrb, record);
 190             mergeLocatorRecords(mrb, record);
 191
 192             // Save source locator for use in Map-Notify
 193             sourceRlocs.add(record.getSourceRloc());
 194         }
 195
 196         if (mrb == null) {
 197             LOG.warn("All mappings expired when merging! Unexpected!");
 198             return null;
 199         }
 200         mrb.setXtrId(xtrId);
 201         mrb.setTimestamp(timestamp);
 202
 203         return mrb.build();
 204     }
 205
 206     public static boolean mappingIsExpired(MappingRecord mapping) {
 207         Preconditions.checkNotNull(mapping, "mapping should not be null!");
 208         if (mapping.getTimestamp() != null) {
 209             return timestampIsExpired(mapping.getTimestamp());
 210         }
 211         return false;
 212     }
 213
 214     public static boolean timestampIsExpired(Date timestamp) {
 215         Preconditions.checkNotNull(timestamp, "timestamp should not be null!");
 216         return timestampIsExpired(timestamp.getTime());
 217     }
 218
 219     public static boolean timestampIsExpired(Long timestamp) {
 220         Preconditions.checkNotNull(timestamp, "timestamp should not be null!");
 221         if ((System.currentTimeMillis() - timestamp) > REGISTRATION_VALIDITY) {
 222             return true;
 223         }
 224         return false;
 225     }
 226
 227     public static Object computeNbSbIntersection(MappingRecord nbMapping, MappingRecord sbMapping) {
 228         // returns a MappingRecord which has the more specific EID, and intersection of locator records.
 229         // If locators intersection is empty, original NB mapping is returned.
 230         // The intersection is only computed for mappings with maskable EIDs.
 231         // Supports both maskable and non-maskable EIDs
 232
 233         MappingRecordBuilder mrb = new MappingRecordBuilder(nbMapping);
 234
 235         if (MaskUtil.isMaskable(sbMapping.getEid().getAddress())
 236                 && MaskUtil.isMaskable(nbMapping.getEid().getAddress())) {
 237
 238             short sbMask = MaskUtil.getMaskForAddress(sbMapping.getEid().getAddress());
 239             short nbMask = MaskUtil.getMaskForAddress(nbMapping.getEid().getAddress());
 240
 241             if (nbMapping.getEid().getAddress() instanceof SourceDestKey) {
 242                 nbMask = SourceDestKeyHelper.getDstMask(nbMapping.getEid());
 243                 if ( nbMask < sbMask) {
 244                     // We have to create a new SourceDest EID, where the source is same as the
 245                     // one in NB record, and dest EID is the more specific from SB mapping record.
 246
 247                     SourceDestKeyBuilder sdb = new SourceDestKeyBuilder(
 248                             ((SourceDestKey) nbMapping.getEid().getAddress()));
 249                     sdb.setDest(new SimpleAddress ((IpPrefix) sbMapping.getEid().getAddress()));
 250                     mrb.setEid(LispAddressUtil.asSrcDstEid(sdb.build(), nbMapping.getEid().getVirtualNetworkId()));
 251                 }
 252             } else if (nbMask < sbMask) {
 253                 // Both EIDs are IP prefixes. SB mapping is a subprefix so we have to update EID intersection
 254                 mrb.setEid(sbMapping.getEid());
 255                 mrb.setMaskLength(sbMask);
 256             }
 257         }
 258         // find and update locators intersection if not empty
 259         List<LocatorRecord> commonLocators = getCommonLocatorRecords(nbMapping, sbMapping);
 260         if (commonLocators != null && !commonLocators.isEmpty()) {
 261             mrb.setLocatorRecord(commonLocators);
 262         }
 263
 264         return mrb.build();
 265     }
 266
 267     private static List<LocatorRecord> getCommonLocatorRecords(MappingRecord nbMapping, MappingRecord sbMapping) {
 268         // This method updates the MappingRecord builder with the intersection of the locator records
 269         // from the two mappings. NB mapping records fields have precedence, only Priority is updated
 270         // from SB mapping if p is 255.
 271
 272         // Return null when NB is a negative mapping
 273         if (nbMapping.getLocatorRecord() == null || nbMapping.getLocatorRecord().isEmpty()) {
 274             return null;
 275         }
 276
 277         List<LocatorRecord> sbLocators = sbMapping.getLocatorRecord();
 278
 279         // We assume locators are unique and don't show up several times (with different or identical p/w/mp/mw),
 280         // so we create a HashMap of the locators from the SB mapping record, keyed by the Rloc
 281         Map<Rloc, LocatorRecord> sbLocatorMap = new HashMap<Rloc, LocatorRecord>();
 282         for (LocatorRecord locator : sbLocators) {
 283             sbLocatorMap.put(locator.getRloc(), locator);
 284         }
 285
 286         // Gradually building final list of common locators, in order that they appear in NB Mapping
 287         List<LocatorRecord> commonLocators = new ArrayList<LocatorRecord>();
 288
 289         for (LocatorRecord nbLocator : nbMapping.getLocatorRecord()) {
 290             Rloc nbRloc = nbLocator.getRloc();
 291             if (sbLocatorMap.containsKey(nbRloc)) {
 292                 // common locator found. use the NB record as the common locator.
 293
 294                 if (sbLocatorMap.get(nbRloc).getPriority() == (short) 255) {
 295                     // if SB locator has p == 255 then common locator takes all NB fields except for p
 296                     // which must be set to 255
 297                     LocatorRecordBuilder lrb = new LocatorRecordBuilder(nbLocator);
 298                     lrb.setPriority((short) 255);
 299                     commonLocators.add(lrb.build());
 300                 } else {
 301                     commonLocators.add(nbLocator);
 302                 }
 303             }
 304         }
 305         return commonLocators;
 306     }
 307
 308 }