Repository: netty/netty
Issue: DNS query ID space exhaustion
Labels: defect

In running big DNS resolution loads with very high parallellism and logging turned on I'm running into query ID space exhaustion (logged messages below).

As I've reviewed the Netty DNS code, I see there is a hard limit of 65536 queries max (in reality a lot less because there would be too many collisions to obtain an ID even with less concurrency).

Wouldn't it make sense to replace the AtomicReferenceArray that holds the promises with a ConcurrentHashMap that could grow as large as necessary? It could also be keyed by the original DnsQuestion, making it _much_ easier to troubleshoot the cases when the query fails and the original question gets lost somewhere. Note, even the current code seems to be doing something wrong, as I have also received warnings about DNS responses with an unknown ID (details below).

Perhaps the choice of the promise collection between AtomicReferenceArray vs. ConcurrentHashMap could be exposed as a configuration option to the user, if the original behavior is worth preserving 

```
2015-07-02 13:39:53,041 WARN  [epollEventLoopGroup-2-1] dns.DnsNameResolver: Received a DNS response with an unknown ID: 55787
```

```
2015-07-02 14:45:02,108 WARN  [epollEventLoopGroup-2-1] concurrent.DefaultPromise: An exception was thrown by com.test.XXXXXXXXXXXXXXXX
java.lang.IllegalStateException: query ID space exhausted: DefaultDnsQuestion(eske.net IN MX)
        at io.netty.resolver.dns.DnsQueryContext.allocateId(DnsQueryContext.java:92)
        at io.netty.resolver.dns.DnsQueryContext.<init>(DnsQueryContext.java:70)
        at io.netty.resolver.dns.DnsNameResolver.query0(DnsNameResolver.java:735)
        at io.netty.resolver.dns.DnsNameResolver.query(DnsNameResolver.java:694)
        at io.netty.resolver.dns.DnsNameResolver.query(DnsNameResolver.java:662)
...
2015-07-02 14:45:02,060 WARN  [epollEventLoopGroup-2-1] concurrent.DefaultPromise: An exception was thrown by com.test.XXXXXXXXXXXXXXXX
java.lang.IllegalStateException: query ID space exhausted: DefaultDnsQuestion(talkingrockcommunications.com IN MX)
        at io.netty.resolver.dns.DnsQueryContext.allocateId(DnsQueryContext.java:92)
        at io.netty.resolver.dns.DnsQueryContext.<init>(DnsQueryContext.java:70)
        at io.netty.resolver.dns.DnsNameResolver.query0(DnsNameResolver.java:735)
        at io.netty.resolver.dns.DnsNameResolver.query(DnsNameResolver.java:694)
        at io.netty.resolver.dns.DnsNameResolver.query(DnsNameResolver.java:662)
...
2015-07-02 14:45:01,529 WARN  [epollEventLoopGroup-2-1] concurrent.DefaultPromise: An exception was thrown by com.test.XXXXXXXXXXXXXXXX
java.lang.IllegalStateException: query ID space exhausted: DefaultDnsQuestion(mailin2.allsupinc.com IN A)
        at io.netty.resolver.dns.DnsQueryContext.allocateId(DnsQueryContext.java:92)
        at io.netty.resolver.dns.DnsQueryContext.<init>(DnsQueryContext.java:70)
        at io.netty.resolver.dns.DnsNameResolver.query0(DnsNameResolver.java:735)
        at io.netty.resolver.dns.DnsNameResolver.query(DnsNameResolver.java:694)
        at io.netty.resolver.dns.DnsNameResolver.query(DnsNameResolver.java:662)
```


Issue comments:
I didn't expect people to produce such amount of load obviously. Let me get the query ID allocation done on per-server basis rather than on per-resolver basis.

Thanks. If you want to keep an array structure, perhaps size could be a configurable setting? In either case it should be possible to get the originally submitted DnsQuestion in the listener.

I think this was fixed by @trustin ... @trustin WDYT ?

Not fixed yet

## 

https://twitter.com/trustin
https://twitter.com/trustin_ko
https://twitter.com/netty_project

On Wed, Sep 9, 2015, at 09:42 PM, Norman Maurer wrote:

> I think this was fixed by @trustin[1] ... @trustin[2] WDYT ?
> 
> —
> Reply to this email directly or view it on GitHub[3]. 

Links:
1. https://github.com/trustin
2. https://github.com/trustin
3. https://github.com/netty/netty/issues/3972#issuecomment-138896842

DNS txid space is limited to 0-65535, like @trustin suggested we can use a txid pool per server, but maybe we could do a txid pool per source port ?

I think a dns query identifier is `source port` + `transaction id` we can send the same transaction id to a same server, but using a different source port. This way we have a far bigger query id space.

I'd support any solution that would extend the query ID space...

Busy at work - will fix when I have time. PR welcome.

Fixed by #4455


Pull request review comments:
We should not do this as this allows this to escape from the constructor and so we may see not fully initialise instances .

can't we use a ConcurrentMap here ?

We can't because we insert multiple entries.

I guess that's not gonna happen because `DnsQueryContext` is only accessed later when a matching DNS response is received.


Patch that resolved the issue:
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 9c3b7a1d2bc..dce3e66d59b 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
@@ -37,7 +37,6 @@
 import io.netty.resolver.SimpleNameResolver;
 import io.netty.util.NetUtil;
 import io.netty.util.ReferenceCountUtil;
-import io.netty.util.collection.IntObjectHashMap;
 import io.netty.util.concurrent.FastThreadLocal;
 import io.netty.util.concurrent.Future;
 import io.netty.util.concurrent.Promise;
@@ -59,9 +58,8 @@
 import java.util.Map.Entry;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.TimeUnit;
-import java.util.concurrent.atomic.AtomicReferenceArray;
 
-import static io.netty.util.internal.ObjectUtil.*;
+import static io.netty.util.internal.ObjectUtil.checkNotNull;
 
 /**
  * A DNS-based {@link NameResolver}.
@@ -95,11 +93,9 @@ public class DnsNameResolver extends SimpleNameResolver<InetSocketAddress> {
     final DatagramChannel ch;
 
     /**
-     * An array whose index is the ID of a DNS query and whose value is the promise of the corresponsing response. We
-     * don't use {@link IntObjectHashMap} or map-like data structure here because 64k elements are fairly small, which
-     * is only about 512KB.
+     * Manages the {@link DnsQueryContext}s in progress and their query IDs.
      */
-    final AtomicReferenceArray<DnsQueryContext> promises = new AtomicReferenceArray<DnsQueryContext>(65536);
+    final DnsQueryContextManager queryContextManager = new DnsQueryContextManager();
 
     /**
      * Cache for {@link #doResolve(InetSocketAddress, Promise)} and {@link #doResolveAll(InetSocketAddress, Promise)}.
@@ -937,7 +933,7 @@ public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception
                     logger.debug("{} RECEIVED: [{}: {}], {}", ch, queryId, res.sender(), res);
                 }
 
-                final DnsQueryContext qCtx = promises.get(queryId);
+                final DnsQueryContext qCtx = queryContextManager.get(res.sender(), queryId);
                 if (qCtx == null) {
                     if (logger.isWarnEnabled()) {
                         logger.warn("{} Received a DNS response with an unknown ID: {}", ch, queryId);
diff --git a/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContext.java b/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContext.java
index 1d1d96c35c1..8217c82ea62 100644
--- a/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContext.java
+++ b/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContext.java
@@ -31,7 +31,6 @@
 import io.netty.util.concurrent.ScheduledFuture;
 import io.netty.util.internal.OneTimeTask;
 import io.netty.util.internal.StringUtil;
-import io.netty.util.internal.ThreadLocalRandom;
 import io.netty.util.internal.logging.InternalLogger;
 import io.netty.util.internal.logging.InternalLoggerFactory;
 
@@ -60,9 +59,9 @@ final class DnsQueryContext {
         this.nameServerAddr = nameServerAddr;
         this.question = question;
         this.promise = promise;
-
-        id = allocateId();
         recursionDesired = parent.isRecursionDesired();
+        id = parent.queryContextManager.add(this);
+
         if (parent.isOptResourceEnabled()) {
             optResource = new DefaultDnsRawRecord(
                     StringUtil.EMPTY_STRING, DnsRecordType.OPT, parent.maxPayloadSize(), 0, Unpooled.EMPTY_BUFFER);
@@ -71,25 +70,17 @@ final class DnsQueryContext {
         }
     }
 
-    private int allocateId() {
-        int id = ThreadLocalRandom.current().nextInt(parent.promises.length());
-        final int maxTries = parent.promises.length() << 1;
-        int tries = 0;
-        for (;;) {
-            if (parent.promises.compareAndSet(id, null, this)) {
-                return id;
-            }
-
-            id = id + 1 & 0xFFFF;
+    InetSocketAddress nameServerAddr() {
+        return nameServerAddr;
+    }
 
-            if (++ tries >= maxTries) {
-                throw new IllegalStateException("query ID space exhausted: " + question);
-            }
-        }
+    DnsQuestion question() {
+        return question;
     }
 
     void query() {
-        final DnsQuestion question = this.question;
+        final DnsQuestion question = question();
+        final InetSocketAddress nameServerAddr = nameServerAddr();
         final DatagramDnsQuery query = new DatagramDnsQuery(null, nameServerAddr, id);
         query.setRecursionDesired(recursionDesired);
         query.setRecord(DnsSection.QUESTION, question);
@@ -159,13 +150,13 @@ public void run() {
     }
 
     void finish(AddressedEnvelope<? extends DnsResponse, InetSocketAddress> envelope) {
-        DnsResponse res = envelope.content();
+        final DnsResponse res = envelope.content();
         if (res.count(DnsSection.QUESTION) != 1) {
             logger.warn("Received a DNS response with invalid number of questions: {}", envelope);
             return;
         }
 
-        if (!question.equals(res.recordAt(DnsSection.QUESTION))) {
+        if (!question().equals(res.recordAt(DnsSection.QUESTION))) {
             logger.warn("Received a mismatching DNS response: {}", envelope);
             return;
         }
@@ -174,7 +165,7 @@ void finish(AddressedEnvelope<? extends DnsResponse, InetSocketAddress> envelope
     }
 
     private void setSuccess(AddressedEnvelope<? extends DnsResponse, InetSocketAddress> envelope) {
-        parent.promises.set(id, null);
+        parent.queryContextManager.remove(nameServerAddr(), id);
 
         // Cancel the timeout task.
         final ScheduledFuture<?> timeoutFuture = this.timeoutFuture;
@@ -192,7 +183,8 @@ private void setSuccess(AddressedEnvelope<? extends DnsResponse, InetSocketAddre
     }
 
     private void setFailure(String message, Throwable cause) {
-        parent.promises.set(id, null);
+        final InetSocketAddress nameServerAddr = nameServerAddr();
+        parent.queryContextManager.remove(nameServerAddr, id);
 
         final StringBuilder buf = new StringBuilder(message.length() + 64);
         buf.append('[')
@@ -203,9 +195,9 @@ private void setFailure(String message, Throwable cause) {
 
         final DnsNameResolverException e;
         if (cause != null) {
-            e = new DnsNameResolverException(nameServerAddr, question, buf.toString(), cause);
+            e = new DnsNameResolverException(nameServerAddr, question(), buf.toString(), cause);
         } else {
-            e = new DnsNameResolverException(nameServerAddr, question, buf.toString());
+            e = new DnsNameResolverException(nameServerAddr, question(), buf.toString());
         }
 
         promise.tryFailure(e);
diff --git a/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContextManager.java b/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContextManager.java
new file mode 100644
index 00000000000..9c3946c72fb
--- /dev/null
+++ b/resolver-dns/src/main/java/io/netty/resolver/dns/DnsQueryContextManager.java
@@ -0,0 +1,148 @@
+/*
+ * Copyright 2015 The Netty Project
+ *
+ * The Netty Project licenses this file to you 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 io.netty.resolver.dns;
+
+import io.netty.util.NetUtil;
+import io.netty.util.collection.IntObjectHashMap;
+import io.netty.util.collection.IntObjectMap;
+import io.netty.util.internal.ThreadLocalRandom;
+
+import java.net.Inet4Address;
+import java.net.Inet6Address;
+import java.net.InetAddress;
+import java.net.InetSocketAddress;
+import java.net.UnknownHostException;
+import java.util.HashMap;
+import java.util.Map;
+
+final class DnsQueryContextManager {
+
+    /**
+     * A map whose key is the DNS server address and value is the map of the DNS query ID and its corresponding
+     * {@link DnsQueryContext}.
+     */
+    final Map<InetSocketAddress, IntObjectMap<DnsQueryContext>> map =
+            new HashMap<InetSocketAddress, IntObjectMap<DnsQueryContext>>();
+
+    int add(DnsQueryContext qCtx) {
+        final IntObjectMap<DnsQueryContext> contexts = getOrCreateContextMap(qCtx.nameServerAddr());
+
+        int id = ThreadLocalRandom.current().nextInt(1, 65536);
+        final int maxTries = 65535 << 1;
+        int tries = 0;
+
+        synchronized (contexts) {
+            for (;;) {
+                if (!contexts.containsKey(id)) {
+                    contexts.put(id, qCtx);
+                    return id;
+                }
+
+                id = id + 1 & 0xFFFF;
+
+                if (++tries >= maxTries) {
+                    throw new IllegalStateException("query ID space exhausted: " + qCtx.question());
+                }
+            }
+        }
+    }
+
+    DnsQueryContext get(InetSocketAddress nameServerAddr, int id) {
+        final IntObjectMap<DnsQueryContext> contexts = getContextMap(nameServerAddr);
+        final DnsQueryContext qCtx;
+        if (contexts != null) {
+            synchronized (contexts) {
+                qCtx = contexts.get(id);
+            }
+        } else {
+            qCtx = null;
+        }
+
+        return qCtx;
+    }
+
+    DnsQueryContext remove(InetSocketAddress nameServerAddr, int id) {
+        final IntObjectMap<DnsQueryContext> contexts = getContextMap(nameServerAddr);
+        if (contexts == null) {
+            return null;
+        }
+
+        synchronized (contexts) {
+            return  contexts.remove(id);
+        }
+    }
+
+    private IntObjectMap<DnsQueryContext> getContextMap(InetSocketAddress nameServerAddr) {
+        synchronized (map) {
+            return map.get(nameServerAddr);
+        }
+    }
+
+    private IntObjectMap<DnsQueryContext> getOrCreateContextMap(InetSocketAddress nameServerAddr) {
+        synchronized (map) {
+            final IntObjectMap<DnsQueryContext> contexts = map.get(nameServerAddr);
+            if (contexts != null) {
+                return contexts;
+            }
+
+            final IntObjectMap<DnsQueryContext> newContexts = new IntObjectHashMap<DnsQueryContext>();
+            final InetAddress a = nameServerAddr.getAddress();
+            final int port = nameServerAddr.getPort();
+            map.put(nameServerAddr, newContexts);
+
+            if (a instanceof Inet4Address) {
+                // Also add the mapping for the IPv4-compatible IPv6 address.
+                final Inet4Address a4 = (Inet4Address) a;
+                if (a4.isLoopbackAddress()) {
+                    map.put(new InetSocketAddress(NetUtil.LOCALHOST6, port), newContexts);
+                } else {
+                    map.put(new InetSocketAddress(toCompatAddress(a4), port), newContexts);
+                }
+            } else if (a instanceof Inet6Address) {
+                // Also add the mapping for the IPv4 address if this IPv6 address is compatible.
+                final Inet6Address a6 = (Inet6Address) a;
+                if (a6.isLoopbackAddress()) {
+                    map.put(new InetSocketAddress(NetUtil.LOCALHOST4, port), newContexts);
+                } else if (a6.isIPv4CompatibleAddress()) {
+                    map.put(new InetSocketAddress(toIPv4Address(a6), port), newContexts);
+                }
+            }
+
+            return newContexts;
+        }
+    }
+
+    private static Inet6Address toCompatAddress(Inet4Address a4) {
+        byte[] b4 = a4.getAddress();
+        byte[] b6 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, b4[0], b4[1], b4[2], b4[3] };
+        try {
+            return (Inet6Address) InetAddress.getByAddress(b6);
+        } catch (UnknownHostException e) {
+            throw new Error(e);
+        }
+    }
+
+    private static Inet4Address toIPv4Address(Inet6Address a6) {
+        byte[] b6 = a6.getAddress();
+        byte[] b4 = { b6[12], b6[13], b6[14], b6[15] };
+        try {
+            return (Inet4Address) InetAddress.getByAddress(b4);
+        } catch (UnknownHostException e) {
+            throw new Error(e);
+        }
+    }
+}


Test patch: