X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=mappingservice%2Finmemorydb%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Flispflowmapping%2Finmemorydb%2FHashMapDb.java;h=8048cf807a556019f4d492360122ce098d9fb9a7;hb=4a99f1d24037d5b7947658b7360a8c53baeedbf6;hp=1fa6b2ce42a75e6d8ab080ccad0c87e7960b3221;hpb=c3571cac0b746ac1c554b220959a3205c4a84e20;p=lispflowmapping.git diff --git a/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java b/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java index 1fa6b2ce4..8048cf807 100644 --- a/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java +++ b/mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/HashMapDb.java @@ -8,24 +8,54 @@ package org.opendaylight.lispflowmapping.inmemorydb; +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.RLOCGroup; +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> data = new ConcurrentHashMap>(); - private TimeUnit timeUnit = TimeUnit.SECONDS; - private int recordTimeOut = 240; + private static final Object TABLES = (Object) "tables"; + private ConcurrentMap> data = new ConcurrentHashMap<>(); + + // IPv4 and IPv6 radix tries used for longest prefix matching + private RadixTrie ip4Trie = new RadixTrie<>(32, true); + private RadixTrie 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) { @@ -33,6 +63,7 @@ public class HashMapDb implements ILispDAO, AutoCloseable { data.put(key, new ConcurrentHashMap()); } for (MappingEntry entry : values) { + tryAddToIpTrie(key); data.get(key).put(entry.getKey(), entry.getValue()); } } @@ -51,6 +82,47 @@ public class HashMapDb implements ILispDAO, AutoCloseable { return data.get(key); } + private RadixTrie.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 getBest(Object key) { + if (key instanceof Eid) { + Eid eid = (Eid) key; + RadixTrie.TrieNode node = lookupBestNode(eid); + if (node == null) { + return get(key); + } + return get(node.data()); + } + return null; + } + + @Override + public SimpleImmutableEntry> getBestPair(Object key) { + Map result = null; + + if (key instanceof Eid) { + Eid eid = (Eid) key; + RadixTrie.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> keyEntry : data.entrySet()) { @@ -60,58 +132,206 @@ public class HashMapDb implements ILispDAO, AutoCloseable { } } + private Eid getPrefix(Eid key, GetPrefixMethods method) { + RadixTrie.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); } - public void cleanOld() { - getAll(new IRowVisitor() { - public void visitRow(Object keyId, String valueKey, Object value) { - if (value instanceof RLOCGroup) { - RLOCGroup rloc = (RLOCGroup) value; - if (isExpired(rloc)) { - removeSpecific(keyId, valueKey); - } - } - } + @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 getSubtree(Eid key) { + Set.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 nodesToEids(Eid key, Set.TrieNode> nodes) { + if (nodes == null || nodes.isEmpty()) { + return Collections.emptySet(); + } - private boolean isExpired(RLOCGroup rloc) { - return System.currentTimeMillis() - rloc.getRegisterdDate().getTime() > TimeUnit.MILLISECONDS.convert(recordTimeOut, timeUnit); + Set children = new HashSet<>(); + for (RadixTrie.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 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 { data.clear(); } + @Override + public ILispDAO putNestedTable(Object key, String valueKey) { + ILispDAO nestedTable = (ILispDAO) getSpecific(key, valueKey); + if (nestedTable != null) { + LOG.warn("Trying to add nested table that already exists. Aborting!"); + return nestedTable; + } + nestedTable = new HashMapDb(); + put(key, new MappingEntry<>(valueKey, nestedTable)); + return nestedTable; + } + + @Override + public ILispDAO putTable(String key) { + ILispDAO table = (ILispDAO) getSpecific(TABLES, key); + if (table != null) { + LOG.warn("Trying to add table that already exists. Aborting!"); + return table; + } + table = new HashMapDb(); + put(TABLES, new MappingEntry<>(key, table)); + return table; + } + + @Override + public boolean isEmpty() { + return data.isEmpty(); + } }