BUG-7464: Fix StackOverflowError on hash collisions

If LNodes get saturated due to poor key hash function, the ListMap
chain can grow large. Since ListMap.get() was implemented using recursion
this can easily trigger StackOverflowError. The same problem impacts
ListMap.contains(), which is triggered in the add() path.

Turn recursion into a loop, which provides defence against the error,
while not alleviating the performance impact.

Change-Id: Id04d30b9cb4d75dc4535ff20bd11a16ed96ab0ff
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
index 1522b6611fa72df49272e431b8436408e1f73b80..9978b5f627168ae57159e4c5789bbe01f6968587 100644 (file)
--- a/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
+++ b/third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/ListMap.java
@@ -49,14 +49,26 @@ final class ListMap<K, V> {
     }
 
     int size() {
-        return next == null ? 1 : next.size() + 1;
+        int sz = 1;
+        for (ListMap<?, ?> wlk = next; wlk != null; wlk = wlk.next) {
+            sz++;
+        }
+        return sz;
     }
 
     Option<V> get(final K key) {
         if (key.equals(k)) {
             return Option.makeOption(v);
         }
-        return next == null ? Option.makeOption() : next.get(key);
+
+        // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+        for (ListMap<K, V> m = next; m != null; m = m.next) {
+            if (key.equals(m.k)) {
+                return Option.makeOption(m.v);
+            }
+        }
+
+        return Option.makeOption();
     }
 
     ListMap<K,V> add(final K key, final V value) {
@@ -72,11 +84,18 @@ final class ListMap<K, V> {
     }
 
     private boolean contains(final K key) {
-        if (key.equals(this.k)) {
+        if (key.equals(k)) {
             return true;
         }
 
-        return next != null && next.contains(key);
+        // We do not perform recursion on purpose here, so we do not run out of stack if the key hashing fails.
+        for (ListMap<K, V> m = next; m != null; m = m.next) {
+            if (key.equals(m.k)) {
+                return true;
+            }
+        }
+
+        return false;
     }
 
     private ListMap<K, V> remove0(final K key) {

diff --git a/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java
new file mode 100644 (file)
index 0000000..f6afabf
--- /dev/null
+++ b/third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java
@@ -0,0 +1,40 @@
+/*
+ * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.opendaylight.yangtools.triemap;
+
+import static org.junit.Assert.assertFalse;
+
+import org.junit.Test;
+
+public class ListMapTest {
+
+    /**
+     * Test if Listmap.get() does not cause stack overflow.
+     */
+    @Test
+    public void testGetOverflow() {
+        ListMap<Integer, Boolean> map = ListMap.map(1, Boolean.TRUE, 2, Boolean.TRUE);
+
+        // 30K seems to be enough to trigger the problem locally
+        for (int i = 3; i < 30000; ++i) {
+            map = map.add(i, Boolean.TRUE);
+        }
+
+        final Option<Boolean> ret = map.get(0);
+        assertFalse(ret.nonEmpty());
+    }
+
+}