Repository: netty/netty
Issue: io.netty.resolver.dns.DnsNameResolver#doResolveCached race condition
Labels: defect

### Expected behavior

No exception.

### Actual behavior

```
2018-01-15 05:33:32,915 ERROR [Redisson-Epoll-1-15] (org.redisson.connection.DNSMonitor) Unable to resolve xxx.0001.use1.cache.amazonaws.com
java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
    at java.util.ArrayList.rangeCheck(ArrayList.java:653) ~[?:1.8.0_144]
    at java.util.ArrayList.get(ArrayList.java:429) ~[?:1.8.0_144]
    at io.netty.resolver.dns.DnsNameResolver.doResolveCached(DnsNameResolver.java:613) ~[netty-resolver-dns-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.dns.DnsNameResolver.doResolve(DnsNameResolver.java:593) ~[netty-resolver-dns-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.dns.DnsNameResolver.doResolve(DnsNameResolver.java:527) ~[netty-resolver-dns-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.SimpleNameResolver.resolve(SimpleNameResolver.java:63) ~[netty-resolver-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.dns.InflightNameResolver.resolve(InflightNameResolver.java:100) ~[netty-resolver-dns-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.dns.InflightNameResolver.resolve(InflightNameResolver.java:66) ~[netty-resolver-dns-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.dns.InflightNameResolver.resolve(InflightNameResolver.java:51) ~[netty-resolver-dns-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.InetSocketAddressResolver.doResolve(InetSocketAddressResolver.java:57) ~[netty-resolver-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.InetSocketAddressResolver.doResolve(InetSocketAddressResolver.java:32) ~[netty-resolver-4.1.19.Final.jar:4.1.19.Final]
    at io.netty.resolver.AbstractAddressResolver.resolve(AbstractAddressResolver.java:108) ~[netty-resolver-4.1.19.Final.jar:4.1.19.Final]
    at org.redisson.connection.DNSMonitor$1.run(DNSMonitor.java:89) ~[redisson-3.5.7.jar:?]
    at io.netty.util.concurrent.PromiseTask$RunnableAdapter.call(PromiseTask.java:38) ~[netty-common-4.1.19.Final.jar:4.1.19.Final]
```

### Steps to reproduce

No reproducer.

### Minimal yet complete reproducer code (or URL to code)

n/a

### Netty version

4.1.19.Final

### JVM version (e.g. `java -version`)

java version "1.8.0_131"
Java(TM) SE Runtime Environment (build 1.8.0_131-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.131-b11, mixed mode)

### OS version (e.g. `uname -a`)



Issue comments:
Some notes..

Might make more sense for io.netty.resolver.dns.DefaultDnsCache#get to return something like this to avoid concurrency issues with the list (in my experience exposing mutable data from a cache is a bad idea)..

```java
    @Override
    public List<? extends DnsCacheEntry> get(String hostname, DnsRecord[] additionals) {
        checkNotNull(hostname, "hostname");
        if (!emptyAdditionals(additionals)) {
            return null;
        }
        return Collections.unmodifiableList(new ArrayList<DnsCacheEntry>(resolveCache.get(hostname)));
    }
```
otherwise we probably need to add a double check in the sync block to  io.netty.resolver.dns.DnsNameResolver#doResolveAllCached and io.netty.resolver.dns.DnsNameResolver#doResolveCached..

```java
    private boolean doResolveCached(String hostname,
                                    DnsRecord[] additionals,
                                    Promise<InetAddress> promise,
                                    DnsCache resolveCache) {
        final List<? extends DnsCacheEntry> cachedEntries = resolveCache.get(hostname, additionals);
        if (cachedEntries == null || cachedEntries.isEmpty()) {
            return false;
        }

        InetAddress address = null;
        Throwable cause = null;
        synchronized (cachedEntries) {
            final int numEntries = cachedEntries.size();
            if (numEntries == 0) {
                return false;
            }
...
```
cc @mrniko
Fixed by https://github.com/netty/netty/pull/7584... return a new `ArrayList` will produce too much GC :(
@normanmaurer yeah figured as much, that's why I also mentioned the double check on the size in the sync block.
@normanmaurer thanks for the quick response!
That said I think we may want to do something smarter in the long run. But I think the fix is ok for now.
@johnou please check https://github.com/netty/netty/pull/7587 ... I think this is a more proper fix
@normanmaurer : We are still experiencing this issue in netty 4.1.20 version.


@sindhuvaidy - This is expected. The fix is included in 4.1.21. Please upgrade.

Pull request review comments:
Little cleaner and less boiler plate code if we assign the locks to final fields as suggested in the javadocs https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

```java
private final Lock readLock = lock.readLock();
private final Lock writeLock = lock.writeLock();
```
is the read lock necessary?
Yes as we read the field... of we update it we use the write lock
done
since this class is trying to accommodate for concurrent access ... should this be in a loop until nothing is removed?
nit: this condition will be enforced by the map, consider removing the redundant null check. Also if the map allows null this will just be a no-op.
if this field is treated as copy on write ... can we just use a volatile and avoid the locking? this would make things much more clear because we let the list escape the lock above in `get()`.
the list escapes the lock here which may violate what ever locking/synchronization enforced by this class internally.
nit: share code with the previous method?
move this into the conditional block where it is actually used. If the assertion is not there `get(0)` will throw, and we already check for `isEmpty()` above.
move this into the conditional block where it is actually used. If the assertion is not there `get(0)` will throw, and we already check for `isEmpty()` above.
Yeah I think this would work...  Let me do this
I think I would keep it for now to make it clear we not support null at all.
not a blocker but the decision to "not support null" could be consolidated in a single place (where we add to `resolveCache`) instead of spread out throughout the code.
`set` -> `super`?
we haven't verified that `entry` is in the `entries` list and so do we need a special case for this condition here?
Can we clarify assumptions here? If it is not likely we will find the element then it seems beneficial to iterate first, and then only allocate/copy if we find the element. if it is likely we will find the element then the current approach (always allocate/copy) seems reasonable.
would it be better to handle this by checking `if (entries.size() == 1 && entry.get(0).equals(newEntry)) { swap with empty collection }`? or is it possible that `entries` may contain multiple elements which equal `entry`?
does it ever make sense to return an empty list, as opposed to just null? if we return empty lists then conditionals tend to get more complicated (e.g. `if not empty and not null`), and the tests should likely be updated to reflect this too.
@Scottmitch we should most likely find it. Thats why I choose the way I am doing it here.
@Scottmitch it may be possible to have multiple entries so I think the way its handled now it more safe.
@Scottmitch I was thinking about this and decided that it may be better to return an empty list mainly because we not state in the javadocs that we will ever return null from the `DnsCache` interface. 
I think if its empty its safe to return just `false`.
TIL: didn't know there is a constructor for this :)
Please include comment with this rational.
`DefaultDnsCacheEntry` doesn't implement `equals`, and on each `cache(..)` call a new element is created. Can you clarify under which conditions the `entries` array would contain the same element multiple times?
We have been returning `null` so perhaps it is best to update the javadocs. `null` is part of the language and there is no reliable way to express a java 6 API which won't return null, which means folks have to `null` check anyways at runtime.
the question was related to https://github.com/netty/netty/pull/7587#discussion_r162137171 below. I was wondering if this special case could be removed if we first search for an item and then allocate an entry / array copy around it. If we don't find the element we can bail without a special case for empty.
@Scottmitch actually scratch this... you are right it cant happen.
if it is "very likely" we will find the element should we create the `ArrayList` with `size - 1`?
if `size == 1` and `!entries.get(0).equals(entry)` then we don't need to go to the else condition (which will allocate/copy for no reason).
Now that we have a special check for `size == 1` before this conditional block executes ... is this ever possible?
honestly I don't care too much but at the end it ay be just good to be safe and not sorry... allocating an array which has one element more then needed is preferred over a memory copy because we need to resize imho.
no... let me remove it.
yep we can just return false
it looks like we should return `true` in an else condition? consider simplifying the code the control flow is easier to follow:

```java
return entries.get(0).equals(entry) && compareAndSet(entries, Collections.<DefaultDnsCacheEntry>emptyList());
```
fine with me ... just may be able to save some memory if its "very likely".
doh! Yeah... let me do what you suggested. 
Actually no... there was something else wrong.

This is correct:

```java
                    if (entries.get(0).equals(entry)) {
                        // If the list is empty we just return early and so not allocate a new ArrayList.
                        if (compareAndSet(entries, Collections.<DefaultDnsCacheEntry>emptyList())) {
                            return false;
                        } else {
                            // try again as the CAS failed
                            continue;
                        }
                    }
                    return false;
```

@Scottmitch WDYT ?
sorry this was not correct as well. Pushed a new version which should be correct
Is NoSuchElementException possible here?

Patch that resolved the issue:
diff --git a/resolver-dns/src/main/java/io/netty/resolver/dns/DefaultDnsCache.java b/resolver-dns/src/main/java/io/netty/resolver/dns/DefaultDnsCache.java
index f2acd3fac76..2b3477bd381 100644
--- a/resolver-dns/src/main/java/io/netty/resolver/dns/DefaultDnsCache.java
+++ b/resolver-dns/src/main/java/io/netty/resolver/dns/DefaultDnsCache.java
@@ -23,11 +23,13 @@
 
 import java.net.InetAddress;
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicReference;
 
 import static io.netty.util.internal.ObjectUtil.checkNotNull;
 import static io.netty.util.internal.ObjectUtil.checkPositiveOrZero;
@@ -39,8 +41,8 @@
 @UnstableApi
 public class DefaultDnsCache implements DnsCache {
 
-    private final ConcurrentMap<String, List<DefaultDnsCacheEntry>> resolveCache =
-                                                            PlatformDependent.newConcurrentHashMap();
+    private final ConcurrentMap<String, Entries> resolveCache = PlatformDependent.newConcurrentHashMap();
+
     private final int minTtl;
     private final int maxTtl;
     private final int negativeTtl;
@@ -97,28 +99,21 @@ public int negativeTtl() {
 
     @Override
     public void clear() {
-        for (Iterator<Map.Entry<String, List<DefaultDnsCacheEntry>>> i = resolveCache.entrySet().iterator();
-             i.hasNext();) {
-            final Map.Entry<String, List<DefaultDnsCacheEntry>> e = i.next();
-            i.remove();
-            cancelExpiration(e.getValue());
+        while (!resolveCache.isEmpty()) {
+            for (Iterator<Map.Entry<String, Entries>> i = resolveCache.entrySet().iterator(); i.hasNext();) {
+                Map.Entry<String, Entries> e = i.next();
+                i.remove();
+
+                e.getValue().cancelExpiration();
+            }
         }
     }
 
     @Override
     public boolean clear(String hostname) {
         checkNotNull(hostname, "hostname");
-        boolean removed = false;
-        for (Iterator<Map.Entry<String, List<DefaultDnsCacheEntry>>> i = resolveCache.entrySet().iterator();
-             i.hasNext();) {
-            final Map.Entry<String, List<DefaultDnsCacheEntry>> e = i.next();
-            if (e.getKey().equals(hostname)) {
-                i.remove();
-                cancelExpiration(e.getValue());
-                removed = true;
-            }
-        }
-        return removed;
+        Entries entries = resolveCache.remove(hostname);
+        return entries != null && entries.cancelExpiration();
     }
 
     private static boolean emptyAdditionals(DnsRecord[] additionals) {
@@ -129,22 +124,11 @@ private static boolean emptyAdditionals(DnsRecord[] additionals) {
     public List<? extends DnsCacheEntry> get(String hostname, DnsRecord[] additionals) {
         checkNotNull(hostname, "hostname");
         if (!emptyAdditionals(additionals)) {
-            return null;
+            return Collections.<DnsCacheEntry>emptyList();
         }
-        return resolveCache.get(hostname);
-    }
 
-    private List<DefaultDnsCacheEntry> cachedEntries(String hostname) {
-        List<DefaultDnsCacheEntry> oldEntries = resolveCache.get(hostname);
-        final List<DefaultDnsCacheEntry> entries;
-        if (oldEntries == null) {
-            List<DefaultDnsCacheEntry> newEntries = new ArrayList<DefaultDnsCacheEntry>(8);
-            oldEntries = resolveCache.putIfAbsent(hostname, newEntries);
-            entries = oldEntries != null? oldEntries : newEntries;
-        } else {
-            entries = oldEntries;
-        }
-        return entries;
+        Entries entries = resolveCache.get(hostname);
+        return entries == null ? null : entries.get();
     }
 
     @Override
@@ -157,22 +141,7 @@ public DnsCacheEntry cache(String hostname, DnsRecord[] additionals,
         if (maxTtl == 0 || !emptyAdditionals(additionals)) {
             return e;
         }
-        final int ttl = Math.max(minTtl, (int) Math.min(maxTtl, originalTtl));
-        final List<DefaultDnsCacheEntry> entries = cachedEntries(hostname);
-
-        synchronized (entries) {
-            if (!entries.isEmpty()) {
-                final DefaultDnsCacheEntry firstEntry = entries.get(0);
-                if (firstEntry.cause() != null) {
-                    assert entries.size() == 1;
-                    firstEntry.cancelExpiration();
-                    entries.clear();
-                }
-            }
-            entries.add(e);
-        }
-
-        scheduleCacheExpiration(entries, e, ttl, loop);
+        cache0(e, Math.max(minTtl, (int) Math.min(maxTtl, originalTtl)), loop);
         return e;
     }
 
@@ -186,40 +155,34 @@ public DnsCacheEntry cache(String hostname, DnsRecord[] additionals, Throwable c
         if (negativeTtl == 0 || !emptyAdditionals(additionals)) {
             return e;
         }
-        final List<DefaultDnsCacheEntry> entries = cachedEntries(hostname);
-
-        synchronized (entries) {
-            final int numEntries = entries.size();
-            for (int i = 0; i < numEntries; i ++) {
-                entries.get(i).cancelExpiration();
-            }
-            entries.clear();
-            entries.add(e);
-        }
 
-        scheduleCacheExpiration(entries, e, negativeTtl, loop);
+        cache0(e, negativeTtl, loop);
         return e;
     }
 
-    private static void cancelExpiration(List<DefaultDnsCacheEntry> entries) {
-        final int numEntries = entries.size();
-        for (int i = 0; i < numEntries; i++) {
-            entries.get(i).cancelExpiration();
+    private void cache0(DefaultDnsCacheEntry e, int ttl, EventLoop loop) {
+        Entries entries = resolveCache.get(e.hostname());
+        if (entries == null) {
+            entries = new Entries(e);
+            Entries oldEntries = resolveCache.putIfAbsent(e.hostname(), entries);
+            if (oldEntries != null) {
+                entries = oldEntries;
+                entries.add(e);
+            }
         }
+
+        scheduleCacheExpiration(entries, e, ttl, loop);
     }
 
-    private void scheduleCacheExpiration(final List<DefaultDnsCacheEntry> entries,
+    private void scheduleCacheExpiration(final Entries entries,
                                          final DefaultDnsCacheEntry e,
                                          int ttl,
                                          EventLoop loop) {
         e.scheduleExpiration(loop, new Runnable() {
                     @Override
                     public void run() {
-                        synchronized (entries) {
-                            entries.remove(e);
-                            if (entries.isEmpty()) {
-                                resolveCache.remove(e.hostname());
-                            }
+                        if (entries.remove(e)) {
+                            resolveCache.remove(e.hostname);
                         }
                     }
                 }, ttl, TimeUnit.SECONDS);
@@ -289,4 +252,98 @@ public String toString() {
             }
         }
     }
+
+    // Directly extend AtomicReference for intrinsics and also to keep memory overhead low.
+    private static final class Entries extends AtomicReference<List<DefaultDnsCacheEntry>> {
+
+        Entries(DefaultDnsCacheEntry entry) {
+            super(Collections.singletonList(entry));
+        }
+
+        void add(DefaultDnsCacheEntry e) {
+            if (e.cause() == null) {
+                for (;;) {
+                    List<DefaultDnsCacheEntry> entries = get();
+                    if (!entries.isEmpty()) {
+                        final DefaultDnsCacheEntry firstEntry = entries.get(0);
+                        if (firstEntry.cause() != null) {
+                            assert entries.size() == 1;
+                            if (compareAndSet(entries, Collections.singletonList(e))) {
+                                firstEntry.cancelExpiration();
+                                return;
+                            } else {
+                                // Need to try again as CAS failed
+                                continue;
+                            }
+                        }
+                        // Create a new List for COW semantics
+                        List<DefaultDnsCacheEntry> newEntries = new ArrayList<DefaultDnsCacheEntry>(entries.size() + 1);
+                        newEntries.addAll(entries);
+                        newEntries.add(e);
+                        if (compareAndSet(entries, newEntries)) {
+                            return;
+                        }
+                    } else if (compareAndSet(entries, Collections.singletonList(e))) {
+                        return;
+                    }
+                }
+            } else {
+                List<DefaultDnsCacheEntry> entries = getAndSet(Collections.singletonList(e));
+                cancelExpiration(entries);
+            }
+        }
+
+        boolean remove(DefaultDnsCacheEntry entry) {
+            for (;;) {
+                List<DefaultDnsCacheEntry> entries = get();
+                int size = entries.size();
+                if (size == 0) {
+                    return false;
+                } else if (size == 1) {
+                    if (entries.get(0).equals(entry)) {
+                        // If the list is empty we just return early and so not allocate a new ArrayList.
+                        if (compareAndSet(entries, Collections.<DefaultDnsCacheEntry>emptyList())) {
+                            return true;
+                        }
+                    } else {
+                        return false;
+                    }
+                } else {
+                    // Just size the new ArrayList as before as we may not find the entry we are looking for and not
+                    // want to cause an extra allocation / memory copy in this case.
+                    //
+                    // Its very likely we find the entry we are looking for so we directly create a new ArrayList
+                    // and fill it.
+                    List<DefaultDnsCacheEntry> newEntries = new ArrayList<DefaultDnsCacheEntry>(size);
+                    for (int i = 0; i < size; i++) {
+                        DefaultDnsCacheEntry e = entries.get(i);
+                        if (!e.equals(entry)) {
+                            newEntries.add(e);
+                        }
+                    }
+                    if (compareAndSet(entries, Collections.unmodifiableList(newEntries))) {
+                        // This will return true if an entry was removed.
+                        return newEntries.size() != size;
+                    }
+                }
+            }
+        }
+
+        boolean cancelExpiration() {
+            List<DefaultDnsCacheEntry> entries = getAndSet(Collections.<DefaultDnsCacheEntry>emptyList());
+            if (entries.isEmpty()) {
+                return false;
+            }
+
+            cancelExpiration(entries);
+            return true;
+        }
+
+        private static void cancelExpiration(List<DefaultDnsCacheEntry> entryList) {
+            final int numEntries = entryList.size();
+            for (int i = 0; i < numEntries; i++) {
+                entryList.get(i).cancelExpiration();
+            }
+        }
+    }
 }
diff --git a/resolver-dns/src/main/java/io/netty/resolver/dns/DnsNameResolver.java b/resolver-dns/src/main/java/io/netty/resolver/dns/DnsNameResolver.java
index 1a928f8c23b..eaa714026d2 100644
--- a/resolver-dns/src/main/java/io/netty/resolver/dns/DnsNameResolver.java
+++ b/resolver-dns/src/main/java/io/netty/resolver/dns/DnsNameResolver.java
@@ -600,43 +600,28 @@ private boolean doResolveCached(String hostname,
                                     Promise<InetAddress> promise,
                                     DnsCache resolveCache) {
         final List<? extends DnsCacheEntry> cachedEntries = resolveCache.get(hostname, additionals);
-        if (cachedEntries == null) {
+        if (cachedEntries == null || cachedEntries.isEmpty()) {
             return false;
         }
 
-        InetAddress address = null;
-        Throwable cause = null;
-        synchronized (cachedEntries) {
+        Throwable cause = cachedEntries.get(0).cause();
+        if (cause == null) {
             final int numEntries = cachedEntries.size();
-            if (numEntries == 0) {
-                return false;
-            }
-
-            if (cachedEntries.get(0).cause() != null) {
-                cause = cachedEntries.get(0).cause();
-            } else {
-                // Find the first entry with the preferred address type.
-                for (InternetProtocolFamily f : resolvedInternetProtocolFamilies) {
-                    for (int i = 0; i < numEntries; i++) {
-                        final DnsCacheEntry e = cachedEntries.get(i);
-                        if (f.addressType().isInstance(e.address())) {
-                            address = e.address();
-                            break;
-                        }
+            // Find the first entry with the preferred address type.
+            for (InternetProtocolFamily f : resolvedInternetProtocolFamilies) {
+                for (int i = 0; i < numEntries; i++) {
+                    final DnsCacheEntry e = cachedEntries.get(i);
+                    if (f.addressType().isInstance(e.address())) {
+                        trySuccess(promise, e.address());
+                        return true;
                     }
                 }
             }
-        }
-
-        if (address != null) {
-            trySuccess(promise, address);
-            return true;
-        }
-        if (cause != null) {
+            return false;
+        } else {
             tryFailure(promise, cause);
             return true;
         }
-        return false;
     }
 
     private static <T> void trySuccess(Promise<T> promise, T result) {
@@ -732,44 +717,34 @@ private boolean doResolveAllCached(String hostname,
                                        Promise<List<InetAddress>> promise,
                                        DnsCache resolveCache) {
         final List<? extends DnsCacheEntry> cachedEntries = resolveCache.get(hostname, additionals);
-        if (cachedEntries == null) {
+        if (cachedEntries == null || cachedEntries.isEmpty()) {
             return false;
         }
 
-        List<InetAddress> result = null;
-        Throwable cause = null;
-        synchronized (cachedEntries) {
+        Throwable cause = cachedEntries.get(0).cause();
+        if (cause == null) {
+            List<InetAddress> result = null;
             final int numEntries = cachedEntries.size();
-            if (numEntries == 0) {
-                return false;
-            }
-
-            if (cachedEntries.get(0).cause() != null) {
-                cause = cachedEntries.get(0).cause();
-            } else {
-                for (InternetProtocolFamily f : resolvedInternetProtocolFamilies) {
-                    for (int i = 0; i < numEntries; i++) {
-                        final DnsCacheEntry e = cachedEntries.get(i);
-                        if (f.addressType().isInstance(e.address())) {
-                            if (result == null) {
-                                result = new ArrayList<InetAddress>(numEntries);
-                            }
-                            result.add(e.address());
+            for (InternetProtocolFamily f : resolvedInternetProtocolFamilies) {
+                for (int i = 0; i < numEntries; i++) {
+                    final DnsCacheEntry e = cachedEntries.get(i);
+                    if (f.addressType().isInstance(e.address())) {
+                        if (result == null) {
+                            result = new ArrayList<InetAddress>(numEntries);
                         }
+                        result.add(e.address());
                     }
                 }
             }
-        }
-
-        if (result != null) {
-            trySuccess(promise, result);
-            return true;
-        }
-        if (cause != null) {
+            if (result != null) {
+                trySuccess(promise, result);
+                return true;
+            }
+            return false;
+        } else {
             tryFailure(promise, cause);
             return true;
         }
-        return false;
     }
 
     static final class ListResolverContext extends DnsNameResolverContext<List<InetAddress>> {


Test patch: