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(), key);
  53             } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
  54                 Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
  55                 ip6Trie.insert(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength(), 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());
  89         } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
  90             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
  91             return ip6Trie.lookupBest(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength());
  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());
 144                     break;
 145                 case PARENT:
 146                     node = ip4Trie.lookupParent(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength());
 147                     break;
 148                 case SIBLING:
 149                     node = ip4Trie.lookupSibling(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength());
 150                     break;
 151                 case VIRTUAL_PARENT_SIBLING:
 152                     node = ip4Trie.lookupVirtualParentSibling(prefix.getIpv4AddressBinary().getValue(),
 153                             prefix.getIpv4MaskLength());
 154                     break;
 155                 case WIDEST_NEGATIVE:
 156                     node = ip4Trie.lookupWidestNegative(prefix.getIpv4AddressBinary().getValue(),
 157                             prefix.getIpv4MaskLength());
 158                     break;
 159                 default:
 160                     node = null;
 161                     break;
 162             }
 163             if (node != null && node.prefix() != null) {
 164                 return LispAddressUtil.asIpv4PrefixBinaryEid(
 165                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
 166             }
 167         } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
 168             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
 169             switch (method) {
 170                 case COVERING:
 171                     node = ip6Trie.lookupCoveringLessSpecific(prefix.getIpv6AddressBinary().getValue(),
 172                             prefix.getIpv6MaskLength());
 173                     break;
 174                 case PARENT:
 175                     node = ip6Trie.lookupParent(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength());
 176                     break;
 177                 case SIBLING:
 178                     node = ip6Trie.lookupSibling(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength());
 179                     break;
 180                 case VIRTUAL_PARENT_SIBLING:
 181                     node = ip6Trie.lookupVirtualParentSibling(prefix.getIpv6AddressBinary().getValue(),
 182                             prefix.getIpv6MaskLength());
 183                     break;
 184                 case WIDEST_NEGATIVE:
 185                     node = ip6Trie.lookupWidestNegative(prefix.getIpv6AddressBinary().getValue(),
 186                             prefix.getIpv6MaskLength());
 187                     break;
 188                 default:
 189                     node = null;
 190                     break;
 191             }
 192             if (node != null && node.prefix() != null) {
 193                 return LispAddressUtil.asIpv6PrefixBinaryEid(
 194                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
 195             }
 196         }
 197         return null;
 198     }
 199
 200     @Override
 201     public Eid getCoveringLessSpecific(Eid key) {
 202         return getPrefix(key, GetPrefixMethods.COVERING);
 203     }
 204
 205     @Override
 206     public Eid getParentPrefix(Eid key) {
 207         return getPrefix(key, GetPrefixMethods.PARENT);
 208     }
 209
 210     @Override
 211     public Eid getSiblingPrefix(Eid key) {
 212         return getPrefix(key, GetPrefixMethods.SIBLING);
 213     }
 214
 215     @Override
 216     public Eid getVirtualParentSiblingPrefix(Eid key) {
 217         return getPrefix(key, GetPrefixMethods.VIRTUAL_PARENT_SIBLING);
 218     }
 219
 220     @Override
 221     public Eid getWidestNegativePrefix(Eid key) {
 222         return getPrefix(key, GetPrefixMethods.WIDEST_NEGATIVE);
 223     }
 224
 225     @Override
 226     public Set<Eid> getSubtree(Eid key) {
 227         Set<RadixTrie<Object>.TrieNode> nodes = null;
 228         if (key.getAddress() instanceof Ipv4PrefixBinary) {
 229             Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
 230             nodes = ip4Trie.lookupSubtree(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength());
 231         } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
 232             Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
 233             nodes = ip6Trie.lookupSubtree(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength());
 234         }
 235         return nodesToEids(key, nodes);
 236     }
 237
 238     private static Set<Eid> nodesToEids(Eid key, Set<RadixTrie<Object>.TrieNode> nodes) {
 239         if (nodes == null || nodes.isEmpty()) {
 240             return Collections.emptySet();
 241         }
 242
 243         Set<Eid> children = new HashSet<>();
 244         for (RadixTrie<Object>.TrieNode node : nodes) {
 245             if (key.getAddress() instanceof Ipv4PrefixBinary) {
 246                 children.add(LispAddressUtil.asIpv4PrefixBinaryEid(
 247                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
 248             } else if  (key.getAddress() instanceof Ipv6PrefixBinary) {
 249                 children.add(LispAddressUtil.asIpv6PrefixBinaryEid(
 250                         key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
 251             }
 252         }
 253         return children;
 254     }
 255
 256     private void tryRemoveFromTrie(Object key) {
 257         if (key instanceof Eid) {
 258             Eid eid = (Eid) key;
 259             if (eid.getAddress() instanceof Ipv4PrefixBinary) {
 260                 Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
 261                 ip4Trie.remove(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength());
 262             } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
 263                 Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
 264                 ip6Trie.remove(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength());
 265             }
 266         }
 267     }
 268
 269     @Override
 270     public void remove(Object key) {
 271         tryRemoveFromTrie(key);
 272         data.remove(key);
 273     }
 274
 275     @Override
 276     public void removeSpecific(Object key, String valueKey) {
 277         Map<String, Object> keyToValues = data.get(key);
 278         if (keyToValues == null) {
 279             return;
 280         }
 281
 282         synchronized (keyToValues) {
 283             if (keyToValues.containsKey(valueKey)) {
 284                 keyToValues.remove(valueKey);
 285                 if (keyToValues.isEmpty()) {
 286                     remove(key);
 287                 }
 288             }
 289         }
 290     }
 291
 292     @Override
 293     public void removeAll() {
 294         ip4Trie.removeAll();
 295         ip6Trie.removeAll();
 296         data.clear();
 297     }
 298
 299     public void close() throws Exception {
 300         data.clear();
 301     }
 302
 303     @Override
 304     public ILispDAO putNestedTable(Object key, String valueKey) {
 305         ILispDAO nestedTable = (ILispDAO) getSpecific(key, valueKey);
 306         if (nestedTable != null) {
 307             LOG.warn("Trying to add nested table that already exists. Aborting!");
 308             return nestedTable;
 309         }
 310         nestedTable = new HashMapDb();
 311         put(key, new MappingEntry<>(valueKey, nestedTable));
 312         return nestedTable;
 313     }
 314
 315     @Override
 316     public ILispDAO putTable(String key) {
 317         ILispDAO table = (ILispDAO) getSpecific(TABLES, key);
 318         if (table != null) {
 319             LOG.warn("Trying to add table that already exists. Aborting!");
 320             return table;
 321         }
 322         table = new HashMapDb();
 323         put(TABLES, new MappingEntry<>(key, table));
 324         return table;
 325     }
 326
 327     @Override
 328     public boolean isEmpty() {
 329         return data.isEmpty();
 330     }
 331 }