package org.opendaylight.lispflowmapping.inmemorydb;
-import java.util.Date;
+import java.util.AbstractMap.SimpleImmutableEntry;
+import java.util.Collections;
+import java.util.HashSet;
import java.util.Map;
+import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.TimeUnit;
-
+import org.opendaylight.lispflowmapping.inmemorydb.radixtrie.RadixTrie;
import org.opendaylight.lispflowmapping.interfaces.dao.ILispDAO;
import org.opendaylight.lispflowmapping.interfaces.dao.IRowVisitor;
import org.opendaylight.lispflowmapping.interfaces.dao.MappingEntry;
-import org.opendaylight.lispflowmapping.interfaces.dao.SubKeys;
+import org.opendaylight.lispflowmapping.lisp.util.LispAddressUtil;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv4PrefixBinary;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.binary.address.types.rev160504.augmented.lisp.address.address.Ipv6PrefixBinary;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.lfm.lisp.proto.rev151105.eid.container.Eid;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
public class HashMapDb implements ILispDAO, AutoCloseable {
protected static final Logger LOG = LoggerFactory.getLogger(HashMapDb.class);
- private ConcurrentMap<Object, ConcurrentMap<String, Object>> data = new ConcurrentHashMap<Object, ConcurrentMap<String, Object>>();
- private TimeUnit timeUnit = TimeUnit.SECONDS;
- private int recordTimeOut = 240;
- private final Object TABLES = (Object) "tables";
+ private static final Object TABLES = (Object) "tables";
+ private ConcurrentMap<Object, ConcurrentMap<String, Object>> data = new ConcurrentHashMap<>();
+
+ // IPv4 and IPv6 radix tries used for longest prefix matching
+ private RadixTrie<Object> ip4Trie = new RadixTrie<>(32, true);
+ private RadixTrie<Object> ip6Trie = new RadixTrie<>(128, true);
+
+ private enum GetPrefixMethods {
+ PARENT,
+ SIBLING,
+ VIRTUAL_PARENT_SIBLING,
+ WIDEST_NEGATIVE,
+ COVERING
+ }
+
+ public void tryAddToIpTrie(Object key) {
+ if (key instanceof Eid) {
+ Eid eid = (Eid) key;
+ if (eid.getAddress() instanceof Ipv4PrefixBinary) {
+ Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
+ ip4Trie.insert(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava(), key);
+ } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
+ Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
+ ip6Trie.insert(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava(), key);
+ }
+ }
+ }
@Override
public void put(Object key, MappingEntry<?>... values) {
data.put(key, new ConcurrentHashMap<String, Object>());
}
for (MappingEntry<?> entry : values) {
+ tryAddToIpTrie(key);
data.get(key).put(entry.getKey(), entry.getValue());
}
}
return data.get(key);
}
+ private RadixTrie<Object>.TrieNode lookupBestNode(Eid eid) {
+ if (eid.getAddress() instanceof Ipv4PrefixBinary) {
+ Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
+ return ip4Trie.lookupBest(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava());
+ } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
+ Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
+ return ip6Trie.lookupBest(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava());
+ }
+ return null;
+ }
+
+ @Override
+ public Map<String, Object> getBest(Object key) {
+ if (key instanceof Eid) {
+ Eid eid = (Eid) key;
+ RadixTrie<Object>.TrieNode node = lookupBestNode(eid);
+ if (node == null) {
+ return get(key);
+ }
+ return get(node.data());
+ }
+ return null;
+ }
+
+ @Override
+ public SimpleImmutableEntry<Eid, Map<String, ?>> getBestPair(Object key) {
+ Map<String, ?> result = null;
+
+ if (key instanceof Eid) {
+ Eid eid = (Eid) key;
+ RadixTrie<Object>.TrieNode node = lookupBestNode(eid);
+ if (node == null) {
+ result = get(key);
+ return (result == null) ? null : new SimpleImmutableEntry<>((Eid)key, result);
+ }
+ result = get(node.data());
+ return (result == null) ? null : new SimpleImmutableEntry<>((Eid)node.data(), result);
+ }
+ return null;
+ }
+
@Override
public void getAll(IRowVisitor visitor) {
for (ConcurrentMap.Entry<Object, ConcurrentMap<String, Object>> keyEntry : data.entrySet()) {
}
}
+ private Eid getPrefix(Eid key, GetPrefixMethods method) {
+ RadixTrie<Object>.TrieNode node = null;
+
+ if (key.getAddress() instanceof Ipv4PrefixBinary) {
+ Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
+ switch (method) {
+ case COVERING:
+ node = ip4Trie.lookupCoveringLessSpecific(prefix.getIpv4AddressBinary().getValue(),
+ prefix.getIpv4MaskLength().toJava());
+ break;
+ case PARENT:
+ node = ip4Trie.lookupParent(prefix.getIpv4AddressBinary().getValue(),
+ prefix.getIpv4MaskLength().toJava());
+ break;
+ case SIBLING:
+ node = ip4Trie.lookupSibling(prefix.getIpv4AddressBinary().getValue(),
+ prefix.getIpv4MaskLength().toJava());
+ break;
+ case VIRTUAL_PARENT_SIBLING:
+ node = ip4Trie.lookupVirtualParentSibling(prefix.getIpv4AddressBinary().getValue(),
+ prefix.getIpv4MaskLength().toJava());
+ break;
+ case WIDEST_NEGATIVE:
+ node = ip4Trie.lookupWidestNegative(prefix.getIpv4AddressBinary().getValue(),
+ prefix.getIpv4MaskLength().toJava());
+ break;
+ default:
+ node = null;
+ break;
+ }
+ if (node != null && node.prefix() != null) {
+ return LispAddressUtil.asIpv4PrefixBinaryEid(
+ key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
+ }
+ } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
+ Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
+ switch (method) {
+ case COVERING:
+ node = ip6Trie.lookupCoveringLessSpecific(prefix.getIpv6AddressBinary().getValue(),
+ prefix.getIpv6MaskLength().toJava());
+ break;
+ case PARENT:
+ node = ip6Trie.lookupParent(prefix.getIpv6AddressBinary().getValue(),
+ prefix.getIpv6MaskLength().toJava());
+ break;
+ case SIBLING:
+ node = ip6Trie.lookupSibling(prefix.getIpv6AddressBinary().getValue(),
+ prefix.getIpv6MaskLength().toJava());
+ break;
+ case VIRTUAL_PARENT_SIBLING:
+ node = ip6Trie.lookupVirtualParentSibling(prefix.getIpv6AddressBinary().getValue(),
+ prefix.getIpv6MaskLength().toJava());
+ break;
+ case WIDEST_NEGATIVE:
+ node = ip6Trie.lookupWidestNegative(prefix.getIpv6AddressBinary().getValue(),
+ prefix.getIpv6MaskLength().toJava());
+ break;
+ default:
+ node = null;
+ break;
+ }
+ if (node != null && node.prefix() != null) {
+ return LispAddressUtil.asIpv6PrefixBinaryEid(
+ key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength());
+ }
+ }
+ return null;
+ }
+
@Override
- public void remove(Object key) {
- data.remove(key);
+ public Eid getCoveringLessSpecific(Eid key) {
+ return getPrefix(key, GetPrefixMethods.COVERING);
}
@Override
- public void removeSpecific(Object key, String valueKey) {
- if (data.containsKey(key) && data.get(key).containsKey(valueKey)) {
- data.get(key).remove(valueKey);
- }
+ public Eid getParentPrefix(Eid key) {
+ return getPrefix(key, GetPrefixMethods.PARENT);
}
@Override
- public void removeAll() {
- data.clear();
+ public Eid getSiblingPrefix(Eid key) {
+ return getPrefix(key, GetPrefixMethods.SIBLING);
}
- // TODO: this should be moved outside of DAO implementation
- public void cleanOld() {
- getAll(new IRowVisitor() {
- public void visitRow(Object keyId, String valueKey, Object value) {
- if (value != null && valueKey instanceof String && ((String) valueKey).equals(SubKeys.REGDATE)) {
- Date date = (Date) value;
- if (isExpired(date)) {
- removeSpecific(keyId, SubKeys.RECORD);
- }
- }
- }
+ @Override
+ public Eid getVirtualParentSiblingPrefix(Eid key) {
+ return getPrefix(key, GetPrefixMethods.VIRTUAL_PARENT_SIBLING);
+ }
+
+ @Override
+ public Eid getWidestNegativePrefix(Eid key) {
+ return getPrefix(key, GetPrefixMethods.WIDEST_NEGATIVE);
+ }
+
+ @Override
+ public Set<Eid> getSubtree(Eid key) {
+ Set<RadixTrie<Object>.TrieNode> nodes = null;
+ if (key.getAddress() instanceof Ipv4PrefixBinary) {
+ Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) key.getAddress();
+ nodes = ip4Trie.lookupSubtree(prefix.getIpv4AddressBinary().getValue(),
+ prefix.getIpv4MaskLength().toJava());
+ } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
+ Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) key.getAddress();
+ nodes = ip6Trie.lookupSubtree(prefix.getIpv6AddressBinary().getValue(),
+ prefix.getIpv6MaskLength().toJava());
+ }
+ return nodesToEids(key, nodes);
+ }
+
+ private static Set<Eid> nodesToEids(Eid key, Set<RadixTrie<Object>.TrieNode> nodes) {
+ if (nodes == null || nodes.isEmpty()) {
+ return Collections.emptySet();
+ }
- private boolean isExpired(Date date) {
- return System.currentTimeMillis() - date.getTime() > TimeUnit.MILLISECONDS.convert(recordTimeOut, timeUnit);
+ Set<Eid> children = new HashSet<>();
+ for (RadixTrie<Object>.TrieNode node : nodes) {
+ if (key.getAddress() instanceof Ipv4PrefixBinary) {
+ children.add(LispAddressUtil.asIpv4PrefixBinaryEid(
+ key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
+ } else if (key.getAddress() instanceof Ipv6PrefixBinary) {
+ children.add(LispAddressUtil.asIpv6PrefixBinaryEid(
+ key.getVirtualNetworkId(), node.prefix(), (short) node.prefixLength()));
}
- });
+ }
+ return children;
}
- public TimeUnit getTimeUnit() {
- return timeUnit;
+ private void tryRemoveFromTrie(Object key) {
+ if (key instanceof Eid) {
+ Eid eid = (Eid) key;
+ if (eid.getAddress() instanceof Ipv4PrefixBinary) {
+ Ipv4PrefixBinary prefix = (Ipv4PrefixBinary) eid.getAddress();
+ ip4Trie.remove(prefix.getIpv4AddressBinary().getValue(), prefix.getIpv4MaskLength().toJava());
+ } else if (eid.getAddress() instanceof Ipv6PrefixBinary) {
+ Ipv6PrefixBinary prefix = (Ipv6PrefixBinary) eid.getAddress();
+ ip6Trie.remove(prefix.getIpv6AddressBinary().getValue(), prefix.getIpv6MaskLength().toJava());
+ }
+ }
}
- public void setRecordTimeOut(int recordTimeOut) {
- this.recordTimeOut = recordTimeOut;
+ @Override
+ public void remove(Object key) {
+ tryRemoveFromTrie(key);
+ data.remove(key);
}
- public int getRecordTimeOut() {
- return recordTimeOut;
+ @Override
+ public void removeSpecific(Object key, String valueKey) {
+ Map<String, Object> keyToValues = data.get(key);
+ if (keyToValues == null) {
+ return;
+ }
+
+ synchronized (keyToValues) {
+ if (keyToValues.containsKey(valueKey)) {
+ keyToValues.remove(valueKey);
+ if (keyToValues.isEmpty()) {
+ remove(key);
+ }
+ }
+ }
}
- public void setTimeUnit(TimeUnit timeUnit) {
- this.timeUnit = timeUnit;
+ @Override
+ public void removeAll() {
+ ip4Trie.removeAll();
+ ip6Trie.removeAll();
+ data.clear();
}
public void close() throws Exception {
put(TABLES, new MappingEntry<>(key, table));
return table;
}
+
+ @Override
+ public boolean isEmpty() {
+ return data.isEmpty();
+ }
}
Code Review / lispflowmapping.git / blobdiff