From c168c28f4027aa972940d32450eb9c9ee1cdfacf Mon Sep 17 00:00:00 2001
From: Robert Varga <rovarga@cisco.com>
Date: Sat, 31 Dec 2016 17:52:12 +0100
Subject: [PATCH] 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>
---
 .../yangtools/triemap/ListMap.java            | 27 +++++++++++--
 .../yangtools/triemap/ListMapTest.java        | 40 +++++++++++++++++++
 2 files changed, 63 insertions(+), 4 deletions(-)
 create mode 100644 third-party/triemap/src/test/java/org/opendaylight/yangtools/triemap/ListMapTest.java

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 1522b6611f..9978b5f627 100644
--- 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
index 0000000000..f6afabf30c
--- /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());
+    }
+
+}
-- 
2.36.6