Create and use a seeded random number generator

(PortSuggester) to suggest what ephemeral source port
should be used when opening a UDP client socket in QUIC.

This should increase the likelihood of 0-RTT connections, even if a strike server is not used across a server cluster.

BUG=326545

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=239426

Review URL: https://codereview.chromium.org/107803002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@240782 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 229 insertions, 2 deletions

diff --git a/net/quic/port_suggester.cc b/net/quic/port_suggester.cc
new file mode 100644
index 0000000..6b7940e
--- /dev/null
+++ b/net/quic/port_suggester.cc
@@ -0,0 +1,49 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/quic/port_suggester.h"
+
+#include "base/logging.h"
+#include "net/base/host_port_pair.h"
+
+namespace net {
+
+PortSuggester::PortSuggester(const HostPortPair& server, uint64 seed)
+    : call_count_(0),
+      previous_suggestion_(-1) {
+  unsigned char hash_bytes[base::kSHA1Length];
+  base::SHA1HashBytes(
+      reinterpret_cast<const unsigned char*>(server.host().data()),
+      server.host().length(), hash_bytes);
+  COMPILE_ASSERT(sizeof(seed_) < sizeof(hash_bytes), seed_larger_than_hash);
+  memcpy(&seed_, hash_bytes, sizeof(seed_));
+  seed_ ^= seed ^ server.port();
+}
+
+int PortSuggester::SuggestPort(int min, int max) {
+  // Sometimes our suggestion can't be used, so we ensure that if additional
+  // calls are made, then each call (probably) provides a new suggestion.
+  if (++call_count_ > 1) {
+    // Evolve the seed.
+    unsigned char hash_bytes[base::kSHA1Length];
+    base::SHA1HashBytes(reinterpret_cast<const unsigned char *>(&seed_),
+                        sizeof(seed_), hash_bytes);
+    memcpy(&seed_, hash_bytes, sizeof(seed_));
+  }
+  DCHECK_LE(min, max);
+  DCHECK_GT(min, 0);
+  int range = max - min + 1;
+  // Ports (and hence the extent of the |range|) are generally under 2^16, so
+  // the tiny non-uniformity in the pseudo-random distribution is not
+  // significant.
+  previous_suggestion_ = static_cast<int>(seed_ % range) + min;
+  return previous_suggestion_;
+}
+
+int PortSuggester::previous_suggestion() const {
+  DCHECK_LT(0u, call_count_);
+  return previous_suggestion_;
+}
+
+}  // namespace net
diff --git a/net/quic/port_suggester.h b/net/quic/port_suggester.h
new file mode 100644
index 0000000..0074f7c
--- /dev/null
+++ b/net/quic/port_suggester.h
@@ -0,0 +1,50 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_QUIC_PORT_SUGGESTER_H_
+#define NET_QUIC_PORT_SUGGESTER_H_
+
+#include "base/basictypes.h"
+#include "base/memory/ref_counted.h"
+#include "base/sha1.h"
+#include "net/base/net_export.h"
+
+namespace net {
+
+class HostPortPair;
+
+// We provide a pseudo-random number generator that is always seeded the same
+// way for a given destination host-port pair.  The generator is used to
+// consistently suggest (for that host-port pair) an ephemeral source port,
+// and hence increase the likelihood that a server's load balancer will direct
+// a repeated connection to the same server (with QUIC, further increasing the
+// chance of connection establishment with 0-RTT).
+class NET_EXPORT_PRIVATE PortSuggester
+    : public base::RefCounted<PortSuggester> {
+ public:
+  PortSuggester(const HostPortPair& server, uint64 seed);
+
+  // Generate a pseudo-random int in the inclusive range from |min| to |max|.
+  // Will (probably) return different numbers when called repeatedly.
+  int SuggestPort(int min, int max);
+
+  uint32 call_count() const { return call_count_; }
+  int previous_suggestion() const;
+
+ private:
+  friend class base::RefCounted<PortSuggester>;
+
+  virtual ~PortSuggester() {}
+
+  // We maintain the first 8 bytes of a hash as our seed_ state.
+  uint64 seed_;
+  uint32 call_count_;  // Number of suggestions made.
+  int previous_suggestion_;
+
+  DISALLOW_COPY_AND_ASSIGN(PortSuggester);
+};
+
+}  // namespace net
+
+#endif  // NET_QUIC_PORT_SUGGESTER_H_
diff --git a/net/quic/port_suggester_unittest.cc b/net/quic/port_suggester_unittest.cc
new file mode 100644
index 0000000..add5258
--- /dev/null
+++ b/net/quic/port_suggester_unittest.cc
@@ -0,0 +1,112 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/quic/port_suggester.h"
+
+#include <set>
+
+#include "base/basictypes.h"
+#include "net/base/host_port_pair.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+namespace test {
+
+class PortSuggesterTest : public ::testing::Test {
+ protected:
+  PortSuggesterTest()
+      : entropy_(1345689),
+        min_ephemeral_port_(1025),
+        max_ephemeral_port_(65535) {
+  }
+
+  uint64 entropy_;
+  int min_ephemeral_port_;
+  int max_ephemeral_port_;
+};
+
+TEST_F(PortSuggesterTest, SmallRangeTest) {
+  // When the range is small (one wide), we always get that as our answer.
+  scoped_refptr<PortSuggester> port_suggester =
+      new PortSuggester(HostPortPair("www.example.com", 443), entropy_);
+  // Test this for a few different (small) ranges.
+  for (int port = 2000; port < 2010; ++port) {
+    // Use |port| for both |min| and |max| delimiting the suggestion range.
+    EXPECT_EQ(port, port_suggester->SuggestPort(port, port));
+    EXPECT_EQ(port, port_suggester->previous_suggestion());
+  }
+}
+
+TEST_F(PortSuggesterTest, SuggestAllPorts) {
+  // We should eventually fill out any range, but we'll just ensure that we
+  // fill out a small range of ports.
+  scoped_refptr<PortSuggester> port_suggester =
+      new PortSuggester(HostPortPair("www.example.com", 443), entropy_);
+  std::set<int> ports;
+  const uint32 port_range = 20;
+  const int insertion_limit = 200;  // We should be done by then.
+  for (int i = 0; i < insertion_limit; ++i) {
+    ports.insert(port_suggester->SuggestPort(min_ephemeral_port_,
+        min_ephemeral_port_ + port_range - 1));
+    if (ports.size() == port_range) {
+      break;
+    }
+  }
+  EXPECT_EQ(port_range, ports.size());
+}
+
+TEST_F(PortSuggesterTest, AvoidDuplication) {
+  // When the range is large, duplicates are rare, but we'll ask for a few
+  // suggestions and make sure they are unique.
+  scoped_refptr<PortSuggester> port_suggester =
+      new PortSuggester(HostPortPair("www.example.com", 80), entropy_);
+  std::set<int> ports;
+  const size_t port_count = 200;
+  for (size_t i = 0; i < port_count; ++i) {
+    ports.insert(port_suggester->SuggestPort(min_ephemeral_port_,
+                                             max_ephemeral_port_));
+  }
+  EXPECT_EQ(port_suggester->call_count(), port_count);
+  EXPECT_EQ(port_count, ports.size());
+}
+
+TEST_F(PortSuggesterTest, ConsistentPorts) {
+  // For given hostname, port, and entropy, we should always get the same
+  // suggestions.
+  scoped_refptr<PortSuggester> port_suggester1 =
+      new PortSuggester(HostPortPair("www.example.com", 443), entropy_);
+  scoped_refptr<PortSuggester> port_suggester2 =
+      new PortSuggester(HostPortPair("www.example.com", 443), entropy_);
+  for (int test_count = 20; test_count > 0; --test_count) {
+    EXPECT_EQ(port_suggester1->SuggestPort(min_ephemeral_port_,
+                                           min_ephemeral_port_),
+              port_suggester2->SuggestPort(min_ephemeral_port_,
+                                           min_ephemeral_port_));
+  }
+}
+
+TEST_F(PortSuggesterTest, DifferentHostPortEntropy) {
+  // When we have different hosts, port, or entropy, we probably won't collide.
+  scoped_refptr<PortSuggester> port_suggester[] = {
+      new PortSuggester(HostPortPair("www.example.com", 80), entropy_),
+      new PortSuggester(HostPortPair("www.example.ORG", 80), entropy_),
+      new PortSuggester(HostPortPair("www.example.com", 443), entropy_),
+      new PortSuggester(HostPortPair("www.example.com", 80), entropy_ + 123456),
+  };
+
+  std::set<int> ports;
+  const int port_count = 40;
+  size_t insertion_count = 0;
+  for (size_t j = 0; j < arraysize(port_suggester); ++j) {
+    for (int i = 0; i < port_count; ++i) {
+     ports.insert(port_suggester[j]->SuggestPort(min_ephemeral_port_,
+                                                 max_ephemeral_port_));
+     ++insertion_count;
+    }
+  }
+  EXPECT_EQ(insertion_count, ports.size());
+}
+
+}  // namespace test
+}  // namespace net
diff --git a/net/quic/quic_stream_factory.cc b/net/quic/quic_stream_factory.cc
index 0c5125b..d1c927b 100644
--- a/net/quic/quic_stream_factory.cc
+++ b/net/quic/quic_stream_factory.cc
@@ -9,6 +9,7 @@
 #include "base/logging.h"
 #include "base/message_loop/message_loop.h"
 #include "base/message_loop/message_loop_proxy.h"
+#include "base/metrics/histogram.h"
 #include "base/rand_util.h"
 #include "base/stl_util.h"
 #include "base/strings/string_util.h"
@@ -21,6 +22,7 @@
 #include "net/quic/congestion_control/tcp_receiver.h"
 #include "net/quic/crypto/proof_verifier_chromium.h"
 #include "net/quic/crypto/quic_random.h"
+#include "net/quic/port_suggester.h"
 #include "net/quic/quic_client_session.h"
 #include "net/quic/quic_clock.h"
 #include "net/quic/quic_connection.h"
@@ -263,7 +265,8 @@ QuicStreamFactory::QuicStreamFactory(
       random_generator_(random_generator),
       clock_(clock),
       max_packet_length_(max_packet_length),
-      weak_factory_(this) {
+      weak_factory_(this),
+      port_entropy_(random_generator_->RandUint64()) {
   config_.SetDefaults();
   config_.set_idle_connection_state_lifetime(
       QuicTime::Delta::FromSeconds(30),
@@ -456,13 +459,18 @@ int QuicStreamFactory::CreateSession(
     QuicClientSession** session) {
   QuicGuid guid = random_generator_->RandUint64();
   IPEndPoint addr = *address_list.begin();
+  scoped_refptr<PortSuggester> port_suggester =
+      new PortSuggester(host_port_proxy_pair.first, port_entropy_);
   scoped_ptr<DatagramClientSocket> socket(
       client_socket_factory_->CreateDatagramClientSocket(
-          DatagramSocket::RANDOM_BIND, base::Bind(&base::RandInt),
+          DatagramSocket::RANDOM_BIND,
+          base::Bind(&PortSuggester::SuggestPort, port_suggester),
           net_log.net_log(), net_log.source()));
   int rv = socket->Connect(addr);
   if (rv != OK)
     return rv;
+  UMA_HISTOGRAM_COUNTS("Net.QuicEphemeralPortsSuggested",
+                       port_suggester->call_count());
 
   // We should adaptively set this buffer size, but for now, we'll use a size
   // that is more than large enough for a full receive window, and yet
diff --git a/net/quic/quic_stream_factory.h b/net/quic/quic_stream_factory.h
index ae0add0..6d4d413 100644
--- a/net/quic/quic_stream_factory.h
+++ b/net/quic/quic_stream_factory.h
@@ -230,6 +230,14 @@ class NET_EXPORT_PRIVATE QuicStreamFactory
 
   base::WeakPtrFactory<QuicStreamFactory> weak_factory_;
 
+  // Each profile will (probably) have a unique port_entropy_ value.  This value
+  // is used to help seed a pseudo-random number generator (PortSuggester) so
+  // that we consistently (within this profile) suggest the same ephemeral port
+  // when we re-connect to any given server/port.  The differences between
+  // profiles (probablistically) prevent two profiles from colliding in their
+  // ephemeral port requests.
+  uint64 port_entropy_;
+
   DISALLOW_COPY_AND_ASSIGN(QuicStreamFactory);
 };