resolve: add CURLOPT_DNS_SHUFFLE_ADDRESSES

This patch adds CURLOPT_DNS_SHUFFLE_ADDRESSES to explicitly request
shuffling of IP addresses returned for a hostname when there is more
than one. This is useful when the application knows that a round robin
approach is appropriate and is willing to accept the consequences of
potentially discarding some preference order returned by the system's
implementation.

Closes #1694

14 files changed, 270 insertions, 3 deletions

diff --git a/docs/libcurl/curl_easy_setopt.3 b/docs/libcurl/curl_easy_setopt.3
index b7d67f360..97883d85d 100644
--- a/docs/libcurl/curl_easy_setopt.3
+++ b/docs/libcurl/curl_easy_setopt.3
@@ -468,6 +468,8 @@ Bind name resolves to this IP4 address. See \fICURLOPT_DNS_LOCAL_IP4(3)\fP
 Bind name resolves to this IP6 address. See \fICURLOPT_DNS_LOCAL_IP6(3)\fP
 .IP CURLOPT_DNS_SERVERS
 Preferred DNS servers. See \fICURLOPT_DNS_SERVERS(3)\fP
+.IP CURLOPT_DNS_SHUFFLE_ADDRESSES
+Shuffle addresses before use. See \fICURLOPT_DNS_SHUFFLE_ADDRESSES(3)\fP
 .IP CURLOPT_ACCEPTTIMEOUT_MS
 Timeout for waiting for the server's connect back to be accepted. See \fICURLOPT_ACCEPTTIMEOUT_MS(3)\fP
 .IP CURLOPT_HAPPY_EYEBALLS_TIMEOUT_MS
diff --git a/docs/libcurl/opts/CURLOPT_DNS_SHUFFLE_ADDRESSES.3 b/docs/libcurl/opts/CURLOPT_DNS_SHUFFLE_ADDRESSES.3
new file mode 100644
index 000000000..8af2d0aa2
--- /dev/null
+++ b/docs/libcurl/opts/CURLOPT_DNS_SHUFFLE_ADDRESSES.3
@@ -0,0 +1,69 @@
+.\" **************************************************************************
+.\" *                                  _   _ ____  _
+.\" *  Project                     ___| | | |  _ \| |
+.\" *                             / __| | | | |_) | |
+.\" *                            | (__| |_| |  _ <| |___
+.\" *                             \___|\___/|_| \_\_____|
+.\" *
+.\" * Copyright (C) 1998 - 2018, Daniel Stenberg, <daniel@haxx.se>, et al.
+.\" *
+.\" * This software is licensed as described in the file COPYING, which
+.\" * you should have received as part of this distribution. The terms
+.\" * are also available at https://curl.haxx.se/docs/copyright.html.
+.\" *
+.\" * You may opt to use, copy, modify, merge, publish, distribute and/or sell
+.\" * copies of the Software, and permit persons to whom the Software is
+.\" * furnished to do so, under the terms of the COPYING file.
+.\" *
+.\" * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+.\" * KIND, either express or implied.
+.\" *
+.\" **************************************************************************
+.\"
+.TH CURLOPT_DNS_SHUFFLE_ADDRESSES 3 "3 March 2018" "libcurl 7.60.0" "curl_easy_setopt options"
+.SH NAME
+CURLOPT_DNS_SHUFFLE_ADDRESSES \- Shuffle addresses when a hostname returns more than one
+.SH SYNOPSIS
+.nf
+#include <curl/curl.h>
+
+CURLcode curl_easy_setopt(CURL *handle, CURLOPT_DNS_SHUFFLE_ADDRESSES, long onoff);
+.fi
+.SH DESCRIPTION
+When a name is resolved and more than one IP address is returned, shuffle the
+order of all returned addresses so that they will be used in a random order.
+This is similar to the ordering behavior of gethostbyname which is no longer
+used on most platforms.
+
+Addresses will not be reshuffled if a name resolution is completed using the
+DNS cache. \fICURLOPT_DNS_CACHE_TIMEOUT(3)\fP can be used together with this
+option to reduce DNS cache timeout or disable caching entirely if frequent
+reshuffling is needed.
+
+Since the addresses returned will be reordered randomly, their order will not
+be in accordance with RFC 3484 or any other deterministic order that may be
+generated by the system's name resolution implementation. This may have
+performance impacts and may cause IPv4 to be used before IPv6 or vice versa.
+.SH DEFAULT
+0 (disabled)
+.SH PROTOCOLS
+All
+.SH EXAMPLE
+.nf
+CURL *curl = curl_easy_init();
+if(curl) {
+  curl_easy_setopt(curl, CURLOPT_URL, "https://example.com");
+  curl_easy_setopt(curl, CURLOPT_DNS_SHUFFLE_ADDRESSES, 1L);
+
+  curl_easy_perform(curl);
+
+  /* always cleanup */
+  curl_easy_cleanup(curl);
+}
+.fi
+.SH AVAILABILITY
+Added in 7.60.0
+.SH RETURN VALUE
+CURLE_OK or an error such as CURLE_UNKNOWN_OPTION.
+.SH "SEE ALSO"
+.BR CURLOPT_DNS_CACHE_TIMEOUT "(3), " CURLOPT_IPRESOLVE "(3), "
diff --git a/docs/libcurl/opts/Makefile.inc b/docs/libcurl/opts/Makefile.inc
index b370082d6..80488bfa3 100644
--- a/docs/libcurl/opts/Makefile.inc
+++ b/docs/libcurl/opts/Makefile.inc
@@ -112,6 +112,7 @@ man_MANS =                                      \
   CURLOPT_DNS_LOCAL_IP4.3                       \
   CURLOPT_DNS_LOCAL_IP6.3                       \
   CURLOPT_DNS_SERVERS.3                         \
+  CURLOPT_DNS_SHUFFLE_ADDRESSES.3               \
   CURLOPT_DNS_USE_GLOBAL_CACHE.3                \
   CURLOPT_EGDSOCKET.3                           \
   CURLOPT_ERRORBUFFER.3                         \
diff --git a/docs/libcurl/symbols-in-versions b/docs/libcurl/symbols-in-versions
index 2877de7f1..52e8407dd 100644
--- a/docs/libcurl/symbols-in-versions
+++ b/docs/libcurl/symbols-in-versions
@@ -373,6 +373,7 @@ CURLOPT_DNS_INTERFACE           7.33.0
 CURLOPT_DNS_LOCAL_IP4           7.33.0
 CURLOPT_DNS_LOCAL_IP6           7.33.0
 CURLOPT_DNS_SERVERS             7.24.0
+CURLOPT_DNS_SHUFFLE_ADDRESSES   7.60.0
 CURLOPT_DNS_USE_GLOBAL_CACHE    7.9.3         7.11.1
 CURLOPT_EGDSOCKET               7.7
 CURLOPT_ENCODING                7.10
diff --git a/include/curl/curl.h b/include/curl/curl.h
index 43d5e031f..3fd4ca87d 100644
--- a/include/curl/curl.h
+++ b/include/curl/curl.h
@@ -1844,6 +1844,9 @@ typedef enum {
   /* send HAProxy PROXY protocol header? */
   CINIT(HAPROXYPROTOCOL, LONG, 274),
 
+  /* shuffle addresses before use when DNS returns multiple */
+  CINIT(DNS_SHUFFLE_ADDRESSES, LONG, 275),
+
   CURLOPT_LASTENTRY /* the last unused */
 } CURLoption;
 
diff --git a/lib/hostip.c b/lib/hostip.c
index 8554d39d1..c2f9defd9 100644
--- a/lib/hostip.c
+++ b/lib/hostip.c
@@ -5,7 +5,7 @@
  *                            | (__| |_| |  _ <| |___
  *                             \___|\___/|_| \_\_____|
  *
- * Copyright (C) 1998 - 2017, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1998 - 2018, Daniel Stenberg, <daniel@haxx.se>, et al.
  *
  * This software is licensed as described in the file COPYING, which
  * you should have received as part of this distribution. The terms
@@ -54,6 +54,7 @@
 #include "sendf.h"
 #include "hostip.h"
 #include "hash.h"
+#include "rand.h"
 #include "share.h"
 #include "strerror.h"
 #include "url.h"
@@ -367,6 +368,70 @@ Curl_fetch_addr(struct connectdata *conn,
 }
 
 /*
+ * Curl_shuffle_addr() shuffles the order of addresses in a 'Curl_addrinfo'
+ * struct by re-linking its linked list.
+ *
+ * The addr argument should be the address of a pointer to the head node of a
+ * `Curl_addrinfo` list and it will be modified to point to the new head after
+ * shuffling.
+ *
+ * Not declared static only to make it easy to use in a unit test!
+ *
+ * @unittest: 1608
+ */
+CURLcode Curl_shuffle_addr(struct Curl_easy *data, Curl_addrinfo **addr)
+{
+  CURLcode result = CURLE_OK;
+  const int num_addrs = Curl_num_addresses(*addr);
+
+  if(num_addrs > 1) {
+    Curl_addrinfo **nodes;
+    infof(data, "Shuffling %i addresses", num_addrs);
+
+    nodes = malloc(num_addrs*sizeof(*nodes));
+    if(nodes) {
+      int i;
+      unsigned int *rnd;
+      const size_t rnd_size = num_addrs * sizeof(*rnd);
+
+      /* build a plain array of Curl_addrinfo pointers */
+      nodes[0] = *addr;
+      for(i = 1; i < num_addrs; i++) {
+        nodes[i] = nodes[i-1]->ai_next;
+      }
+
+      rnd = malloc(rnd_size);
+      if(rnd) {
+        /* Fisher-Yates shuffle */
+        if(Curl_rand(data, (unsigned char *)rnd, rnd_size) == CURLE_OK) {
+          Curl_addrinfo *swap_tmp;
+          for(i = num_addrs - 1; i > 0; i--) {
+            swap_tmp = nodes[rnd[i] % (i + 1)];
+            nodes[rnd[i] % (i + 1)] = nodes[i];
+            nodes[i] = swap_tmp;
+          }
+
+          /* relink list in the new order */
+          for(i = 1; i < num_addrs; i++) {
+            nodes[i-1]->ai_next = nodes[i];
+          }
+
+          nodes[num_addrs-1]->ai_next = NULL;
+          *addr = nodes[0];
+        }
+        free(rnd);
+      }
+      else
+        result = CURLE_OUT_OF_MEMORY;
+      free(nodes);
+    }
+    else
+      result = CURLE_OUT_OF_MEMORY;
+  }
+  return result;
+}
+
+/*
  * Curl_cache_addr() stores a 'Curl_addrinfo' struct in the DNS cache.
  *
  * When calling Curl_resolv() has resulted in a response with a returned
@@ -386,6 +451,13 @@ Curl_cache_addr(struct Curl_easy *data,
   struct Curl_dns_entry *dns;
   struct Curl_dns_entry *dns2;
 
+  /* shuffle addresses if requested */
+  if(data->set.dns_shuffle_addresses) {
+    CURLcode result = Curl_shuffle_addr(data, &addr);
+    if(!result)
+      return NULL;
+  }
+
   /* Create an entry id, based upon the hostname and port */
   entry_id = create_hostcache_id(hostname, port);
   /* If we can't create the entry id, fail */
diff --git a/lib/hostip.h b/lib/hostip.h
index 298eeeee3..1de4bee8d 100644
--- a/lib/hostip.h
+++ b/lib/hostip.h
@@ -7,7 +7,7 @@
  *                            | (__| |_| |  _ <| |___
  *                             \___|\___/|_| \_\_____|
  *
- * Copyright (C) 1998 - 2017, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1998 - 2018, Daniel Stenberg, <daniel@haxx.se>, et al.
  *
  * This software is licensed as described in the file COPYING, which
  * you should have received as part of this distribution. The terms
@@ -182,6 +182,17 @@ struct Curl_dns_entry *
 Curl_fetch_addr(struct connectdata *conn,
                 const char *hostname,
                 int port);
+
+/*
+ * Curl_shuffle_addr() shuffles the order of addresses in a 'Curl_addrinfo'
+ * struct by re-linking its linked list.
+ *
+ * The addr argument should be the address of a pointer to the head node of a
+ * `Curl_addrinfo` list and it will be modified to point to the new head after
+ * shuffling.
+ */
+CURLcode Curl_shuffle_addr(struct Curl_easy *data, Curl_addrinfo **addr);
+
 /*
  * Curl_cache_addr() stores a 'Curl_addrinfo' struct in the DNS cache.
  *
diff --git a/lib/setopt.c b/lib/setopt.c
index 737a60f85..da364fa81 100644
--- a/lib/setopt.c
+++ b/lib/setopt.c
@@ -2561,6 +2561,9 @@ CURLcode Curl_vsetopt(struct Curl_easy *data, CURLoption option,
       return CURLE_BAD_FUNCTION_ARGUMENT;
     data->set.happy_eyeballs_timeout = arg;
     break;
+  case CURLOPT_DNS_SHUFFLE_ADDRESSES:
+    data->set.dns_shuffle_addresses = (0 != va_arg(param, long)) ? TRUE:FALSE;
+    break;
   default:
     /* unknown tag and its companion, just ignore: */
     result = CURLE_UNKNOWN_OPTION;
diff --git a/lib/urldata.h b/lib/urldata.h
index dad31cd4e..35bbb8590 100644
--- a/lib/urldata.h
+++ b/lib/urldata.h
@@ -1674,6 +1674,8 @@ struct UserDefined {
   bool suppress_connect_headers;  /* suppress proxy CONNECT response headers
                                      from user callbacks */
 
+  bool dns_shuffle_addresses; /* whether to shuffle addresses before use */
+
   struct Curl_easy *stream_depends_on;
   bool stream_depends_e; /* set or don't set the Exclusive bit */
   int stream_weight;
diff --git a/packages/OS400/curl.inc.in b/packages/OS400/curl.inc.in
index a21ee9bba..ac302967f 100644
--- a/packages/OS400/curl.inc.in
+++ b/packages/OS400/curl.inc.in
@@ -1330,6 +1330,8 @@
      d                 c                   20272
      d  CURLOPT_RESOLVER_START_DATA...
      d                 c                   10273
+     d  CURLOPT_DNS_SHUFFLE_ADDRESSES...
+     d                 c                   00274
       *
       /if not defined(CURL_NO_OLDIES)
      d  CURLOPT_FILE   c                   10001
diff --git a/tests/data/Makefile.inc b/tests/data/Makefile.inc
index ca0c7edd1..2f5721318 100644
--- a/tests/data/Makefile.inc
+++ b/tests/data/Makefile.inc
@@ -177,6 +177,7 @@ test1533 test1534 test1535 test1536 test1537 test1538 \
 test1540 \
 test1550 test1551 test1552 test1553 test1554 test1555 test1556 \
 test1600 test1601 test1602 test1603 test1604 test1605 test1606 test1607 \
+test1608 \
 \
 test1700 test1701 test1702 \
 \
diff --git a/tests/data/test1608 b/tests/data/test1608
new file mode 100644
index 000000000..702310757
--- /dev/null
+++ b/tests/data/test1608
@@ -0,0 +1,26 @@
+<testcase>
+<info>
+<keywords>
+unittest
+curlopt_dns_shuffle_addresses
+</keywords>
+</info>
+
+#
+# Client-side
+<client>
+<server>
+none
+</server>
+<features>
+unittest
+</features>
+ <name>
+verify DNS shuffling
+ </name>
+<tool>
+unit1608
+</tool>
+</client>
+
+</testcase>
diff --git a/tests/unit/Makefile.inc b/tests/unit/Makefile.inc
index 9a19f51d1..f77da7588 100644
--- a/tests/unit/Makefile.inc
+++ b/tests/unit/Makefile.inc
@@ -9,7 +9,8 @@ UNITPROGS = unit1300 unit1301 unit1302 unit1303 unit1304 unit1305 unit1307	\
  unit1308 unit1309 unit1323 \
  unit1330 unit1394 unit1395 unit1396 unit1397 unit1398	\
  unit1399	\
- unit1600 unit1601 unit1602 unit1603 unit1604 unit1605 unit1606 unit1607
+ unit1600 unit1601 unit1602 unit1603 unit1604 unit1605 unit1606 unit1607 \
+ unit1608
 
 unit1300_SOURCES = unit1300.c $(UNITFILES)
 unit1300_CPPFLAGS = $(AM_CPPFLAGS)
@@ -88,3 +89,6 @@ unit1606_CPPFLAGS = $(AM_CPPFLAGS)
 
 unit1607_SOURCES = unit1607.c $(UNITFILES)
 unit1607_CPPFLAGS = $(AM_CPPFLAGS)
+
+unit1608_SOURCES = unit1608.c $(UNITFILES)
+unit1608_CPPFLAGS = $(AM_CPPFLAGS)
diff --git a/tests/unit/unit1608.c b/tests/unit/unit1608.c
new file mode 100644
index 000000000..9ae474ba9
--- /dev/null
+++ b/tests/unit/unit1608.c
@@ -0,0 +1,70 @@
+/***************************************************************************
+ *                                  _   _ ____  _
+ *  Project                     ___| | | |  _ \| |
+ *                             / __| | | | |_) | |
+ *                            | (__| |_| |  _ <| |___
+ *                             \___|\___/|_| \_\_____|
+ *
+ * Copyright (C) 1998 - 2018, Daniel Stenberg, <daniel@haxx.se>, et al.
+ *
+ * This software is licensed as described in the file COPYING, which
+ * you should have received as part of this distribution. The terms
+ * are also available at https://curl.haxx.se/docs/copyright.html.
+ *
+ * You may opt to use, copy, modify, merge, publish, distribute and/or sell
+ * copies of the Software, and permit persons to whom the Software is
+ * furnished to do so, under the terms of the COPYING file.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ***************************************************************************/
+#include "curlcheck.h"
+
+#include "hostip.h"
+
+#define NUM_ADDRS 8
+static struct Curl_addrinfo addrs[NUM_ADDRS];
+
+static CURLcode unit_setup(void)
+{
+  int i;
+  for(i = 0; i < NUM_ADDRS - 1; i++) {
+    addrs[i].ai_next = &addrs[i + 1];
+  }
+
+  return CURLE_OK;
+}
+
+static void unit_stop(void)
+{
+
+}
+
+UNITTEST_START
+{
+  int i;
+  CURLcode code;
+  struct Curl_addrinfo* addrhead = addrs;
+
+  struct Curl_easy *easy = curl_easy_init();
+  abort_unless(easy, "out of memory");
+
+  code = curl_easy_setopt(easy, CURLOPT_DNS_SHUFFLE_ADDRESSES, 1L);
+  abort_unless(code == CURLE_OK, "curl_easy_setopt failed");
+
+  /* Shuffle repeatedly and make sure that the list changes */
+  for(i = 0; i < 10; i++) {
+    if(CURLE_OK != Curl_shuffle_addr(easy, &addrhead))
+      break;
+    if(addrhead != addrs)
+      break;
+  }
+
+  curl_easy_cleanup(easy);
+
+  abort_unless(addrhead != addrs, "addresses are not being reordered");
+
+  return 0;
+}
+UNITTEST_STOP