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