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         COVERING
  45     }
  46
  47     public void tryAddToIpTrie(Object key) {
  48         if (key instanceof Eid) {
  49             Eid eid = (Eid) key;
  50             if (eid.getAddress() instanceof Ipv4PrefixBinary) {
  51                 Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
  52                 ip4Trie.insert(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava(), key);
  53             } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
  54                 Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
  55                 ip6Trie.insert(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava(), key);
  56             }
  57         }
  58     }
  59
  60     @Override
  61     public void put(Object key, MappingEntry<?>... values) {
  62         if (!data.containsKey(key)) {
  63             data.put(key, new ConcurrentHashMap<String, Object>());
  64         }
  65         for (MappingEntry<?> entry : values) {
  66             tryAddToIpTrie(key);
  67             data.get(key).put(entry.getKey(), entry.getValue());
  68         }
  69     }
  70
  71     @Override
  72     public Object getSpecific(Object key, String valueKey) {
  73         Map<String, Object> keyToValues = data.get(key);
  74         if (keyToValues == null) {
  75             return null;
  76         }
  77         return keyToValues.get(valueKey);
  78     }
  79
  80     @Override
  81     public Map<String, Object> get(Object key) {
  82         return data.get(key);
  83     }
  84
  85     private RadixTrie<Object>.TrieNode lookupBestNode(Eid eid) {
  86         if (eid.getAddress() instanceof Ipv4PrefixBinary) {
  87             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
  88             return ip4Trie.lookupBest(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava());
  89         } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
  90             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
  91             return ip6Trie.lookupBest(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava());
  92         }
  93         return null;
  94     }
  95
  96     @Override
  97     public Map<String, Object> getBest(Object key) {
  98         if (key instanceof Eid) {
  99             Eid eid = (Eid) key;
 100             RadixTrie<Object>.TrieNode node = lookupBestNode(eid);
 101             if (node == null) {
 102                 return get(key);
 103             }
 104             return get(node.data());
 105         }
 106         return null;
 107     }
 108
 109     @Override
 110     public SimpleImmutableEntry<Eid, Map<String, ?>> getBestPair(Object key) {
 111         Map<String, ?> result = null;
 112
 113         if (key instanceof Eid) {
 114             Eid eid = (Eid) key;
 115             RadixTrie<Object>.TrieNode node = lookupBestNode(eid);
 116             if (node == null) {
 117                 result = get(key);
 118                 return (result == null) ? null : new SimpleImmutableEntry<>((Eid)key, result);
 119             }
 120             result = get(node.data());
 121             return (result == null) ? null : new SimpleImmutableEntry<>((Eid)node.data(), result);
 122         }
 123         return null;
 124     }
 125
 126     @Override
 127     public void getAll(IRowVisitor visitor) {
 128         for (ConcurrentMap.Entry<Object, ConcurrentMap<String, Object>> keyEntry : data.entrySet()) {
 129             for (Map.Entry<String, Object> valueEntry : keyEntry.getValue().entrySet()) {
 130                 visitor.visitRow(keyEntry.getKey(), valueEntry.getKey(), valueEntry.getValue());
 131             }
 132         }
 133     }
 134
 135     private Eid getPrefix(Eid key, GetPrefixMethods method) {
 136         RadixTrie<Object>.TrieNode node = null;
 137
 138         if (key.getAddress() instanceof Ipv4PrefixBinary) {
 139             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
 140             switch (method) {
 141                 case COVERING:
 142                     node = ip4Trie.lookupCoveringLessSpecific(prefix.getIpv4AddressBinary().getValue(),
 143                             prefix.getIpv4MaskLength().toJava());
 144                     break;
 145                 case PARENT:
 146                     node = ip4Trie.lookupParent(prefix.getIpv4AddressBinary().getValue(),
 147                             prefix.getIpv4MaskLength().toJava());
 148                     break;
 149                 case SIBLING:
 150                     node = ip4Trie.lookupSibling(prefix.getIpv4AddressBinary().getValue(),
 151                             prefix.getIpv4MaskLength().toJava());
 152                     break;
 153                 case VIRTUAL_PARENT_SIBLING:
 154                     node = ip4Trie.lookupVirtualParentSibling(prefix.getIpv4AddressBinary().getValue(),
 155                             prefix.getIpv4MaskLength().toJava());
 156                     break;
 157                 case WIDEST_NEGATIVE:
 158                     node = ip4Trie.lookupWidestNegative(prefix.getIpv4AddressBinary().getValue(),
 159                             prefix.getIpv4MaskLength().toJava());
 160                     break;
 161                 default:
 162                     node = null;
 163                     break;
 164             }
 165             if (node != null && node.prefix() != null) {
 166                 return LispAddressUtil.asIpv4PrefixBinaryEid(
 167                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
 168             }
 169         } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
 170             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
 171             switch (method) {
 172                 case COVERING:
 173                     node = ip6Trie.lookupCoveringLessSpecific(prefix.getIpv6AddressBinary().getValue(),
 174                             prefix.getIpv6MaskLength().toJava());
 175                     break;
 176                 case PARENT:
 177                     node = ip6Trie.lookupParent(prefix.getIpv6AddressBinary().getValue(),
 178                             prefix.getIpv6MaskLength().toJava());
 179                     break;
 180                 case SIBLING:
 181                     node = ip6Trie.lookupSibling(prefix.getIpv6AddressBinary().getValue(),
 182                             prefix.getIpv6MaskLength().toJava());
 183                     break;
 184                 case VIRTUAL_PARENT_SIBLING:
 185                     node = ip6Trie.lookupVirtualParentSibling(prefix.getIpv6AddressBinary().getValue(),
 186                             prefix.getIpv6MaskLength().toJava());
 187                     break;
 188                 case WIDEST_NEGATIVE:
 189                     node = ip6Trie.lookupWidestNegative(prefix.getIpv6AddressBinary().getValue(),
 190                             prefix.getIpv6MaskLength().toJava());
 191                     break;
 192                 default:
 193                     node = null;
 194                     break;
 195             }
 196             if (node != null && node.prefix() != null) {
 197                 return LispAddressUtil.asIpv6PrefixBinaryEid(
 198                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
 199             }
 200         }
 201         return null;
 202     }
 203
 204     @Override
 205     public Eid getCoveringLessSpecific(Eid key) {
 206         return getPrefix(key, GetPrefixMethods.COVERING);
 207     }
 208
 209     @Override
 210     public Eid getParentPrefix(Eid key) {
 211         return getPrefix(key, GetPrefixMethods.PARENT);
 212     }
 213
 214     @Override
 215     public Eid getSiblingPrefix(Eid key) {
 216         return getPrefix(key, GetPrefixMethods.SIBLING);
 217     }
 218
 219     @Override
 220     public Eid getVirtualParentSiblingPrefix(Eid key) {
 221         return getPrefix(key, GetPrefixMethods.VIRTUAL_PARENT_SIBLING);
 222     }
 223
 224     @Override
 225     public Eid getWidestNegativePrefix(Eid key) {
 226         return getPrefix(key, GetPrefixMethods.WIDEST_NEGATIVE);
 227     }
 228
 229     @Override
 230     public Set<Eid> getSubtree(Eid key) {
 231         Set<RadixTrie<Object>.TrieNode> nodes = null;
 232         if (key.getAddress() instanceof Ipv4PrefixBinary) {
 233             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
 234             nodes = ip4Trie.lookupSubtree(prefix.getIpv4AddressBinary().getValue(),
 235                     prefix.getIpv4MaskLength().toJava());
 236         } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
 237             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
 238             nodes = ip6Trie.lookupSubtree(prefix.getIpv6AddressBinary().getValue(),
 239                     prefix.getIpv6MaskLength().toJava());
 240         }
 241         return nodesToEids(key, nodes);
 242     }
 243
 244     private static Set<Eid> nodesToEids(Eid key, Set<RadixTrie<Object>.TrieNode> nodes) {
 245         if (nodes == null || nodes.isEmpty()) {
 246             return Collections.emptySet();
 247         }
 248
 249         Set<Eid> children = new HashSet<>();
 250         for (RadixTrie<Object>.TrieNode node : nodes) {
 251             if (key.getAddress() instanceof Ipv4PrefixBinary) {
 252                 children.add(LispAddressUtil.asIpv4PrefixBinaryEid(
 253                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
 254             } else if  (key.getAddress() instanceof Ipv6PrefixBinary) {
 255                 children.add(LispAddressUtil.asIpv6PrefixBinaryEid(
 256                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
 257             }
 258         }
 259         return children;
 260     }
 261
 262     private void tryRemoveFromTrie(Object key) {
 263         if (key instanceof Eid) {
 264             Eid eid = (Eid) key;
 265             if (eid.getAddress() instanceof Ipv4PrefixBinary) {
 266                 Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
 267                 ip4Trie.remove(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava());
 268             } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
 269                 Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
 270                 ip6Trie.remove(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava());
 271             }
 272         }
 273     }
 274
 275     @Override
 276     public void remove(Object key) {
 277         tryRemoveFromTrie(key);
 278         data.remove(key);
 279     }
 280
 281     @Override
 282     public void removeSpecific(Object key, String valueKey) {
 283         Map<String, Object> keyToValues = data.get(key);
 284         if (keyToValues == null) {
 285             return;
 286         }
 287
 288         synchronized (keyToValues) {
 289             if (keyToValues.containsKey(valueKey)) {
 290                 keyToValues.remove(valueKey);
 291                 if (keyToValues.isEmpty()) {
 292                     remove(key);
 293                 }
 294             }
 295         }
 296     }
 297
 298     @Override
 299     public void removeAll() {
 300         ip4Trie.removeAll();
 301         ip6Trie.removeAll();
 302         data.clear();
 303     }
 304
 305     public void close() throws Exception {
 306         data.clear();
 307     }
 308
 309     @Override
 310     public ILispDAO putNestedTable(Object key, String valueKey) {
 311         ILispDAO nestedTable = (ILispDAO) getSpecific(key, valueKey);
 312         if (nestedTable != null) {
 313             LOG.warn("Trying to add nested table that already exists. Aborting!");
 314             return nestedTable;
 315         }
 316         nestedTable = new HashMapDb();
 317         put(key, new MappingEntry<>(valueKey, nestedTable));
 318         return nestedTable;
 319     }
 320
 321     @Override
 322     public ILispDAO putTable(String key) {
 323         ILispDAO table = (ILispDAO) getSpecific(TABLES, key);
 324         if (table != null) {
 325             LOG.warn("Trying to add table that already exists. Aborting!");
 326             return table;
 327         }
 328         table = new HashMapDb();
 329         put(TABLES, new MappingEntry<>(key, table));
 330         return table;
 331     }
 332
 333     @Override
 334     public boolean isEmpty() {
 335         return data.isEmpty();
 336     }
 337 }