Avoid multiple dns lookups for the same query

If two or more rapid dns requests for the same server are done
from different threads it turns into separate dns reques, if
the response of the request isn't found in the cache.

This patch avoid multiple request for the same server by
letting subsequents request wait until the first request
has finished.

Change-Id: Ic72ea0e7d3964a4164eddf866feb4357ec4dfe54

3 files changed, 135 insertions, 1 deletions

diff --git a/libc/netbsd/resolv/res_cache.c b/libc/netbsd/resolv/res_cache.c
index 284ca2f..2dcb164 100644
--- a/libc/netbsd/resolv/res_cache.c
+++ b/libc/netbsd/resolv/res_cache.c
@@ -1159,6 +1159,15 @@ entry_equals( const Entry*  e1, const Entry*  e2 )
  * inlined in the Entry structure.
  */
 
+/* Maximum time for a thread to wait for an pending request */
+#define PENDING_REQUEST_TIMEOUT 20;
+
+typedef struct pending_req_info {
+    unsigned int                hash;
+    pthread_cond_t              cond;
+    struct pending_req_info*    next;
+} PendingReqInfo;
+
 typedef struct resolv_cache {
     int              max_entries;
     int              num_entries;
@@ -1167,6 +1176,7 @@ typedef struct resolv_cache {
     unsigned         generation;
     int              last_id;
     Entry*           entries;
+    PendingReqInfo   pending_requests;
 } Cache;
 
 typedef struct resolv_cache_info {
@@ -1181,6 +1191,107 @@ typedef struct resolv_cache_info {
 #define  HTABLE_VALID(x)  ((x) != NULL && (x) != HTABLE_DELETED)
 
 static void
+_cache_flush_pending_requests_locked( struct resolv_cache* cache )
+{
+    struct pending_req_info *ri, *tmp;
+    if (cache) {
+        ri = cache->pending_requests.next;
+
+        while (ri) {
+            tmp = ri;
+            ri = ri->next;
+            pthread_cond_broadcast(&tmp->cond);
+
+            pthread_cond_destroy(&tmp->cond);
+            free(tmp);
+        }
+
+        cache->pending_requests.next = NULL;
+    }
+}
+
+/* return 0 if no pending request is found matching the key
+ * if a matching request is found the calling thread will wait
+ * and return 1 when released */
+static int
+_cache_check_pending_request_locked( struct resolv_cache* cache, Entry* key )
+{
+    struct pending_req_info *ri, *prev;
+    int exist = 0;
+
+    if (cache && key) {
+        ri = cache->pending_requests.next;
+        prev = &cache->pending_requests;
+        while (ri) {
+            if (ri->hash == key->hash) {
+                exist = 1;
+                break;
+            }
+            prev = ri;
+            ri = ri->next;
+        }
+
+        if (!exist) {
+            ri = calloc(1, sizeof(struct pending_req_info));
+            if (ri) {
+                ri->hash = key->hash;
+                pthread_cond_init(&ri->cond, NULL);
+                prev->next = ri;
+            }
+        } else {
+            struct timespec ts = {0,0};
+            ts.tv_sec = _time_now() + PENDING_REQUEST_TIMEOUT;
+            int rv = pthread_cond_timedwait(&ri->cond, &cache->lock, &ts);
+        }
+    }
+
+    return exist;
+}
+
+/* notify any waiting thread that waiting on a request
+ * matching the key has been added to the cache */
+static void
+_cache_notify_waiting_tid_locked( struct resolv_cache* cache, Entry* key )
+{
+    struct pending_req_info *ri, *prev;
+
+    if (cache && key) {
+        ri = cache->pending_requests.next;
+        prev = &cache->pending_requests;
+        while (ri) {
+            if (ri->hash == key->hash) {
+                pthread_cond_broadcast(&ri->cond);
+                break;
+            }
+            prev = ri;
+            ri = ri->next;
+        }
+
+        // remove item from list and destroy
+        if (ri) {
+            prev->next = ri->next;
+            pthread_cond_destroy(&ri->cond);
+            free(ri);
+        }
+    }
+}
+
+/* notify the cache that the query failed */
+void
+_resolv_cache_query_failed( struct resolv_cache* cache,
+                   const void* query,
+                   int         querylen)
+{
+    Entry    key[1];
+
+    if (cache && entry_init_key(key, query, querylen)) {
+        pthread_mutex_lock(&cache->lock);
+        _cache_notify_waiting_tid_locked(cache, key);
+        pthread_mutex_unlock(&cache->lock);
+    }
+}
+
+static void
 _cache_flush_locked( Cache*  cache )
 {
     int     nn;
@@ -1197,6 +1308,9 @@ _cache_flush_locked( Cache*  cache )
         }
     }
 
+    // flush pending request
+    _cache_flush_pending_requests_locked(cache);
+
     cache->mru_list.mru_next = cache->mru_list.mru_prev = &cache->mru_list;
     cache->num_entries       = 0;
     cache->last_id           = 0;
@@ -1470,7 +1584,17 @@ _resolv_cache_lookup( struct resolv_cache*  cache,
 
     if (e == NULL) {
         XLOG( "NOT IN CACHE");
-        goto Exit;
+        // calling thread will wait if an outstanding request is found
+        // that matching this query
+        if (!_cache_check_pending_request_locked(cache, key)) {
+            goto Exit;
+        } else {
+            lookup = _cache_lookup_p(cache, key);
+            e = *lookup;
+            if (e == NULL) {
+                goto Exit;
+            }
+        }
     }
 
     now = _time_now();
@@ -1573,6 +1697,7 @@ _resolv_cache_add( struct resolv_cache*  cache,
     _cache_dump_mru(cache);
 #endif
 Exit:
+    _cache_notify_waiting_tid_locked(cache, key);
     pthread_mutex_unlock( &cache->lock );
 }
 
diff --git a/libc/netbsd/resolv/res_send.c b/libc/netbsd/resolv/res_send.c
index dbad6dd..2f131f1 100644
--- a/libc/netbsd/resolv/res_send.c
+++ b/libc/netbsd/resolv/res_send.c
@@ -646,6 +646,9 @@ res_nsend(res_state statp,
 		errno = terrno;
 	return (-1);
  fail:
+#if USE_RESOLV_CACHE
+	_resolv_cache_query_failed(cache, buf, buflen);
+#endif
 	res_nclose(statp);
 	return (-1);
 }
diff --git a/libc/private/resolv_cache.h b/libc/private/resolv_cache.h
index 2a54453..1dcc53f 100644
--- a/libc/private/resolv_cache.h
+++ b/libc/private/resolv_cache.h
@@ -95,4 +95,10 @@ _resolv_cache_add( struct resolv_cache*  cache,
                    const void*           answer,
                    int                   answerlen );
 
+/* Notify the cache a request failed */
+extern void
+_resolv_cache_query_failed( struct resolv_cache* cache,
+                   const void* query,
+                   int         querylen);
+
 #endif /* _RESOLV_CACHE_H_ */