mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java

   1 /*
   2  * Copyright (c) 2015 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.inmemorydb;
   9
  10 import java.util.AbstractMap.SimpleImmutableEntry;
  11 import java.util.HashSet;
  12 import java.util.Map;
  13 import java.util.Set;
  14 import java.util.concurrent.ConcurrentHashMap;
  15 import java.util.concurrent.ConcurrentMap;
  16 import javax.annotation.PreDestroy;
  17 import javax.inject.Inject;
  18 import javax.inject.Singleton;
  19 import org.opendaylight.lispflowmapping.inmemorydb.radixtrie.RadixTrie;
  20 import org.opendaylight.lispflowmapping.interfaces.dao.ILispDAO;
  21 import org.opendaylight.lispflowmapping.interfaces.dao.IRowVisitor;
  22 import org.opendaylight.lispflowmapping.interfaces.dao.MappingEntry;
  23 import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil;
  24 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv4PrefixBinary;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv6PrefixBinary;
  26 import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.eid.container.Eid;
  27 import org.osgi.service.component.annotations.Activate;
  28 import org.osgi.service.component.annotations.Component;
  29 import org.osgi.service.component.annotations.Deactivate;
  30 import org.slf4j.Logger;
  31 import org.slf4j.LoggerFactory;
  32
  33 @Singleton
  34 @Component(service = ILispDAO.class, immediate = true, property = "type=default")
  35 public class HashMapDb implements ILispDAO, AutoCloseable {
  36     private static final Logger LOG = LoggerFactory.getLogger(HashMapDb.class);
  37     private static final Object TABLES = "tables";
  38
  39     private final ConcurrentMap<Object, ConcurrentMap<String, Object>> data = new ConcurrentHashMap<>();
  40
  41     // IPv4 and IPv6 radix tries used for longest prefix matching
  42     private final RadixTrie<Object> ip4Trie = new RadixTrie<>(32, true);
  43     private final RadixTrie<Object> ip6Trie = new RadixTrie<>(128, true);
  44
  45     private enum GetPrefixMethods {
  46         PARENT,
  47         SIBLING,
  48         VIRTUAL_PARENT_SIBLING,
  49         WIDEST_NEGATIVE,
  50         COVERING
  51     }
  52
  53     @Inject
  54     @Activate
  55     public HashMapDb() {
  56
  57     }
  58
  59     @PreDestroy
  60     @Deactivate
  61     @Override
  62     public void close() {
  63         data.clear();
  64     }
  65
  66     public void tryAddToIpTrie(Object key) {
  67         if (key instanceof Eid) {
  68             Eid eid = (Eid) key;
  69             if (eid.getAddress() instanceof Ipv4PrefixBinary) {
  70                 Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
  71                 ip4Trie.insert(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava(), key);
  72             } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
  73                 Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
  74                 ip6Trie.insert(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava(), key);
  75             }
  76         }
  77     }
  78
  79     @Override
  80     public void put(Object key, MappingEntry<?>... values) {
  81         if (!data.containsKey(key)) {
  82             data.put(key, new ConcurrentHashMap<String, Object>());
  83         }
  84         for (MappingEntry<?> entry : values) {
  85             tryAddToIpTrie(key);
  86             data.get(key).put(entry.getKey(), entry.getValue());
  87         }
  88     }
  89
  90     @Override
  91     public Object getSpecific(Object key, String valueKey) {
  92         Map<String, Object> keyToValues = data.get(key);
  93         if (keyToValues == null) {
  94             return null;
  95         }
  96         return keyToValues.get(valueKey);
  97     }
  98
  99     @Override
 100     public Map<String, Object> get(Object key) {
 101         return data.get(key);
 102     }
 103
 104     private RadixTrie<Object>.TrieNode lookupBestNode(Eid eid) {
 105         if (eid.getAddress() instanceof Ipv4PrefixBinary) {
 106             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
 107             return ip4Trie.lookupBest(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava());
 108         } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
 109             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
 110             return ip6Trie.lookupBest(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava());
 111         }
 112         return null;
 113     }
 114
 115     @Override
 116     public Map<String, Object> getBest(Object key) {
 117         if (key instanceof Eid) {
 118             Eid eid = (Eid) key;
 119             RadixTrie<Object>.TrieNode node = lookupBestNode(eid);
 120             if (node == null) {
 121                 return get(key);
 122             }
 123             return get(node.data());
 124         }
 125         return null;
 126     }
 127
 128     @Override
 129     public SimpleImmutableEntry<Eid, Map<String, ?>> getBestPair(Object key) {
 130         Map<String, ?> result = null;
 131
 132         if (key instanceof Eid) {
 133             Eid eid = (Eid) key;
 134             RadixTrie<Object>.TrieNode node = lookupBestNode(eid);
 135             if (node == null) {
 136                 result = get(key);
 137                 return (result == null) ? null : new SimpleImmutableEntry<>((Eid)key, result);
 138             }
 139             result = get(node.data());
 140             return (result == null) ? null : new SimpleImmutableEntry<>((Eid)node.data(), result);
 141         }
 142         return null;
 143     }
 144
 145     @Override
 146     public void getAll(IRowVisitor visitor) {
 147         for (ConcurrentMap.Entry<Object, ConcurrentMap<String, Object>> keyEntry : data.entrySet()) {
 148             for (Map.Entry<String, Object> valueEntry : keyEntry.getValue().entrySet()) {
 149                 visitor.visitRow(keyEntry.getKey(), valueEntry.getKey(), valueEntry.getValue());
 150             }
 151         }
 152     }
 153
 154     private Eid getPrefix(Eid key, GetPrefixMethods method) {
 155         RadixTrie<Object>.TrieNode node = null;
 156
 157         if (key.getAddress() instanceof Ipv4PrefixBinary) {
 158             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
 159             switch (method) {
 160                 case COVERING:
 161                     node = ip4Trie.lookupCoveringLessSpecific(prefix.getIpv4AddressBinary().getValue(),
 162                             prefix.getIpv4MaskLength().toJava());
 163                     break;
 164                 case PARENT:
 165                     node = ip4Trie.lookupParent(prefix.getIpv4AddressBinary().getValue(),
 166                             prefix.getIpv4MaskLength().toJava());
 167                     break;
 168                 case SIBLING:
 169                     node = ip4Trie.lookupSibling(prefix.getIpv4AddressBinary().getValue(),
 170                             prefix.getIpv4MaskLength().toJava());
 171                     break;
 172                 case VIRTUAL_PARENT_SIBLING:
 173                     node = ip4Trie.lookupVirtualParentSibling(prefix.getIpv4AddressBinary().getValue(),
 174                             prefix.getIpv4MaskLength().toJava());
 175                     break;
 176                 case WIDEST_NEGATIVE:
 177                     node = ip4Trie.lookupWidestNegative(prefix.getIpv4AddressBinary().getValue(),
 178                             prefix.getIpv4MaskLength().toJava());
 179                     break;
 180                 default:
 181                     node = null;
 182                     break;
 183             }
 184             if (node != null && node.prefix() != null) {
 185                 return LispAddressUtil.asIpv4PrefixBinaryEid(
 186                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
 187             }
 188         } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
 189             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
 190             switch (method) {
 191                 case COVERING:
 192                     node = ip6Trie.lookupCoveringLessSpecific(prefix.getIpv6AddressBinary().getValue(),
 193                             prefix.getIpv6MaskLength().toJava());
 194                     break;
 195                 case PARENT:
 196                     node = ip6Trie.lookupParent(prefix.getIpv6AddressBinary().getValue(),
 197                             prefix.getIpv6MaskLength().toJava());
 198                     break;
 199                 case SIBLING:
 200                     node = ip6Trie.lookupSibling(prefix.getIpv6AddressBinary().getValue(),
 201                             prefix.getIpv6MaskLength().toJava());
 202                     break;
 203                 case VIRTUAL_PARENT_SIBLING:
 204                     node = ip6Trie.lookupVirtualParentSibling(prefix.getIpv6AddressBinary().getValue(),
 205                             prefix.getIpv6MaskLength().toJava());
 206                     break;
 207                 case WIDEST_NEGATIVE:
 208                     node = ip6Trie.lookupWidestNegative(prefix.getIpv6AddressBinary().getValue(),
 209                             prefix.getIpv6MaskLength().toJava());
 210                     break;
 211                 default:
 212                     node = null;
 213                     break;
 214             }
 215             if (node != null && node.prefix() != null) {
 216                 return LispAddressUtil.asIpv6PrefixBinaryEid(
 217                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
 218             }
 219         }
 220         return null;
 221     }
 222
 223     @Override
 224     public Eid getCoveringLessSpecific(Eid key) {
 225         return getPrefix(key, GetPrefixMethods.COVERING);
 226     }
 227
 228     @Override
 229     public Eid getParentPrefix(Eid key) {
 230         return getPrefix(key, GetPrefixMethods.PARENT);
 231     }
 232
 233     @Override
 234     public Eid getSiblingPrefix(Eid key) {
 235         return getPrefix(key, GetPrefixMethods.SIBLING);
 236     }
 237
 238     @Override
 239     public Eid getVirtualParentSiblingPrefix(Eid key) {
 240         return getPrefix(key, GetPrefixMethods.VIRTUAL_PARENT_SIBLING);
 241     }
 242
 243     @Override
 244     public Eid getWidestNegativePrefix(Eid key) {
 245         return getPrefix(key, GetPrefixMethods.WIDEST_NEGATIVE);
 246     }
 247
 248     @Override
 249     public Set<Eid> getSubtree(Eid key) {
 250         Set<RadixTrie<Object>.TrieNode> nodes = null;
 251         if (key.getAddress() instanceof Ipv4PrefixBinary) {
 252             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
 253             nodes = ip4Trie.lookupSubtree(prefix.getIpv4AddressBinary().getValue(),
 254                     prefix.getIpv4MaskLength().toJava());
 255         } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
 256             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
 257             nodes = ip6Trie.lookupSubtree(prefix.getIpv6AddressBinary().getValue(),
 258                     prefix.getIpv6MaskLength().toJava());
 259         }
 260         return nodesToEids(key, nodes);
 261     }
 262
 263     private static Set<Eid> nodesToEids(Eid key, Set<RadixTrie<Object>.TrieNode> nodes) {
 264         if (nodes == null || nodes.isEmpty()) {
 265             return Set.of();
 266         }
 267
 268         Set<Eid> children = new HashSet<>();
 269         for (RadixTrie<Object>.TrieNode node : nodes) {
 270             if (key.getAddress() instanceof Ipv4PrefixBinary) {
 271                 children.add(LispAddressUtil.asIpv4PrefixBinaryEid(
 272                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
 273             } else if  (key.getAddress() instanceof Ipv6PrefixBinary) {
 274                 children.add(LispAddressUtil.asIpv6PrefixBinaryEid(
 275                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
 276             }
 277         }
 278         return children;
 279     }
 280
 281     private void tryRemoveFromTrie(Object key) {
 282         if (key instanceof Eid) {
 283             Eid eid = (Eid) key;
 284             if (eid.getAddress() instanceof Ipv4PrefixBinary) {
 285                 Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
 286                 ip4Trie.remove(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava());
 287             } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
 288                 Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
 289                 ip6Trie.remove(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava());
 290             }
 291         }
 292     }
 293
 294     @Override
 295     public void remove(Object key) {
 296         tryRemoveFromTrie(key);
 297         data.remove(key);
 298     }
 299
 300     @Override
 301     public void removeSpecific(Object key, String valueKey) {
 302         Map<String, Object> keyToValues = data.get(key);
 303         if (keyToValues == null) {
 304             return;
 305         }
 306
 307         synchronized (keyToValues) {
 308             if (keyToValues.containsKey(valueKey)) {
 309                 keyToValues.remove(valueKey);
 310                 if (keyToValues.isEmpty()) {
 311                     remove(key);
 312                 }
 313             }
 314         }
 315     }
 316
 317     @Override
 318     public void removeAll() {
 319         ip4Trie.removeAll();
 320         ip6Trie.removeAll();
 321         data.clear();
 322     }
 323
 324     @Override
 325     public ILispDAO putNestedTable(Object key, String valueKey) {
 326         ILispDAO nestedTable = (ILispDAO) getSpecific(key, valueKey);
 327         if (nestedTable != null) {
 328             LOG.warn("Trying to add nested table that already exists. Aborting!");
 329             return nestedTable;
 330         }
 331         nestedTable = new HashMapDb();
 332         put(key, new MappingEntry<>(valueKey, nestedTable));
 333         return nestedTable;
 334     }
 335
 336     @Override
 337     public ILispDAO putTable(String key) {
 338         ILispDAO table = (ILispDAO) getSpecific(TABLES, key);
 339         if (table != null) {
 340             LOG.warn("Trying to add table that already exists. Aborting!");
 341             return table;
 342         }
 343         table = new HashMapDb();
 344         put(TABLES, new MappingEntry<>(key, table));
 345         return table;
 346     }
 347
 348     @Override
 349     public boolean isEmpty() {
 350         return data.isEmpty();
 351     }
 352 }