Add chrome to the repository.

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

6 files changed, 957 insertions, 0 deletions

diff --git a/chrome/renderer/net/render_dns_master.cc b/chrome/renderer/net/render_dns_master.cc
new file mode 100644
index 0000000..01f8c78
--- /dev/null
+++ b/chrome/renderer/net/render_dns_master.cc
@@ -0,0 +1,189 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// See header file for description of RenderDnsMaster class
+
+
+#include "chrome/renderer/net/render_dns_master.h"
+
+#include <ctype.h>
+
+#include "base/logging.h"
+#include "chrome/common/net/dns.h"
+#include "chrome/common/render_messages.h"
+#include "chrome/renderer/net/render_dns_queue.h"
+#include "chrome/renderer/render_thread.h"
+
+// This API is used in the render process by renderer_glue.cc.
+// IF you are in the render process, you MUST be on the renderer thread to call.
+void DnsPrefetchCString(const char* hostname, size_t length) {
+  RenderThread::current()->Resolve(hostname, length);
+}
+
+// The number of hostnames submitted to Browser DNS resolver per call to
+// SubmitHostsnames() (which reads names from our queue).
+static const size_t kMAX_SUBMISSION_PER_TASK = 30;
+
+RenderDnsMaster::RenderDnsMaster()
+    : c_string_queue_(1000),
+#pragma warning(push)
+#pragma warning(suppress: 4355)  // Okay to pass "this" here.
+    render_dns_factory_(this) {
+#pragma warning(pop)
+  Reset();
+}
+
+void RenderDnsMaster::Reset() {
+  domain_map_.clear();
+  c_string_queue_.Clear();
+  buffer_full_discard_count_ = 0;
+  numeric_ip_discard_count_ = 0;
+  new_name_count_ = 0;
+}
+
+// Push names into queue quickly!
+void RenderDnsMaster::Resolve(const char* name, size_t length) {
+  if (!length)
+    return;  // Don't store empty strings in buffer.
+  if (is_numeric_ip(name, length))
+    return;  // Numeric IPs have no DNS lookup significance.
+
+  size_t old_size =  c_string_queue_.Size();
+  DnsQueue::PushResult result = c_string_queue_.Push(name, length);
+  if (DnsQueue::SUCCESSFUL_PUSH == result) {
+    if (1 == c_string_queue_.Size()) {
+      DCHECK(0 == old_size);
+      if (0 != old_size)
+        return;  // Overkill safety net: Don't send too many InvokeLater's.
+      render_dns_factory_.RevokeAll();
+      RenderThread::current()->message_loop()->PostDelayedTask(FROM_HERE,
+          render_dns_factory_.NewRunnableMethod(
+              &RenderDnsMaster::SubmitHostnames), 10);
+    }
+    return;
+  }
+  if (DnsQueue::OVERFLOW_PUSH == result) {
+    buffer_full_discard_count_++;
+    return;
+  }
+  DCHECK(DnsQueue::REDUNDANT_PUSH == result);
+}
+
+// Extract data from the Queue, and then send it off the the Browser process
+// to be resolved.
+void RenderDnsMaster::SubmitHostnames() {
+  // Get all names out of the C_string_queue (into our map)
+  ExtractBufferedNames();
+  // TBD: IT could be that we should only extract about as many names as we are
+  // going to send to the browser.  That would cause a "silly" page with a TON
+  // of URLs to start to overrun the DnsQueue, which will cause the names to
+  // be dropped (not stored in the queue).  By fetching ALL names, we are
+  // taking on a lot of work, which may take a long time to process... perhaps
+  // longer than the page may be visible!?!?!  If we implement a better
+  // mechanism for doing domain_map.clear() (see end of this method), then
+  // we'd automatically flush such pending work from a ridiculously link-filled
+  // page.
+
+  // Don't overload the browser DNS lookup facility, or take too long here,
+  // by only sending off kMAX_SUBMISSION_PER_TASK names to the Browser.
+  // This will help to avoid overloads when a page has a TON of links.
+  DnsPrefetchNames(kMAX_SUBMISSION_PER_TASK);
+  if (new_name_count_ > 0 || 0 < c_string_queue_.Size()) {
+    render_dns_factory_.RevokeAll();
+    RenderThread::current()->message_loop()->PostDelayedTask(FROM_HERE,
+        render_dns_factory_.NewRunnableMethod(
+            &RenderDnsMaster::SubmitHostnames), 10);
+  } else {
+    // TODO(JAR): Should we only clear the map when we navigate, or reload?
+    domain_map_.clear();
+  }
+}
+
+// Pull some hostnames from the queue, and add them to our map.
+void RenderDnsMaster::ExtractBufferedNames(size_t size_goal) {
+  size_t count(0);  // Number of entries to find (0 means find all).
+  if (size_goal > 0) {
+    if (size_goal <= domain_map_.size())
+      return;  // Size goal was met.
+    count = size_goal - domain_map_.size();
+  }
+
+  std::string name;
+  while (c_string_queue_.Pop(&name)) {
+    DCHECK(0 != name.size());
+    // We don't put numeric IP names into buffer.
+    DCHECK(!is_numeric_ip(name.c_str(), name.size()));
+    DomainUseMap::iterator it;
+    it = domain_map_.find(name);
+    if (domain_map_.end() == it) {
+      domain_map_[name] = kPending;
+      new_name_count_++;
+      if (0 == count) continue;  // Until buffer is empty.
+      if (1 == count) break;  // We found size_goal.
+      DCHECK(1 < count);
+      count--;
+    } else {
+      DCHECK(kPending == it->second || kLookupRequested == it->second);
+    }
+  }
+}
+
+void RenderDnsMaster::DnsPrefetchNames(size_t max_count) {
+  // We are on the renderer thread, and just need to send things to the browser.
+  chrome_common_net::NameList names;
+  for (DomainUseMap::iterator it = domain_map_.begin();
+    it != domain_map_.end();
+    it++) {
+    if (0 == (it->second & kLookupRequested)) {
+      it->second |= kLookupRequested;
+      names.push_back(it->first);
+      if (0 == max_count) continue;  // Get all, independent of count.
+      if (1 == max_count) break;
+      max_count--;
+      DCHECK(1 <= max_count);
+    }
+  }
+  new_name_count_ -= names.size();
+  DCHECK(new_name_count_ >= 0);
+
+  RenderThread::current()->Send(new ViewHostMsg_DnsPrefetch(names));
+}
+
+// is_numeric_ip() checks to see if all characters in name are either numeric,
+// or dots.  Such a name will not actually be passed to DNS, as it is an IP
+// address.
+bool RenderDnsMaster::is_numeric_ip(const char* name, size_t length) {
+  // Scan for a character outside our lookup list.
+  while (length-- > 0) {
+    if (!isdigit(*name) && '.' != *name)
+      return false;
+    name++;
+  }
+  return true;
+}
diff --git a/chrome/renderer/net/render_dns_master.h b/chrome/renderer/net/render_dns_master.h
new file mode 100644
index 0000000..31f26fe
--- /dev/null
+++ b/chrome/renderer/net/render_dns_master.h
@@ -0,0 +1,134 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// A RenderDnsMaster instance is maintained for each RenderThread.
+// Hostnames are typically added to the embedded queue during rendering.
+// The first addition to the queue (transitioning from empty to having
+// some names) causes a processing task to be added to the Renderer Thread.
+// The processing task gathers all buffered names, and send them via IPC
+// to the browser, so that DNS lookups can be performed before the user attempts
+// to traverse a link.
+// This class removed some duplicates, and discards numeric IP addresss
+// (which wouldn't looked up in DNS anyway).
+// To limit the time during the processing task (and avoid stalling the Render
+// thread), several limits are placed on how much of the queue to process.
+// If the processing task is not able to completely empty the queue, it
+// schedules a future continuation of the task, and keeps the map of already
+// sent names.  If the entire queue is processed, then the list of "sent names"
+// is cleared so that future gatherings may again pass along the same names.
+
+#ifndef CHROME_RENDERER_RENDER_NET_DNS_MASTER_H__
+#define CHROME_RENDERER_RENDER_NET_DNS_MASTER_H__
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/task.h"
+#include "chrome/renderer/net/render_dns_queue.h"
+
+// Global API consists to do Prefetching in renderer.  This uses IPC to reach
+// the Browser's global functions.
+void DnsPrefetchCString(const char* hostname, size_t length);
+
+class RenderDnsMaster {
+ public:
+  RenderDnsMaster();
+
+  ~RenderDnsMaster() {}
+
+  // Push a name into the queue to be resolved.
+  void Resolve(const char* name, size_t length);
+
+  // SubmitHosts processes the buffered names, and submits them for DNS
+  // prefetching.
+  // Note that browser process may decide which names should be looked up (to
+  // pre-warm the cache) based on what has been (or not been) looked up
+  // recently.
+  // If sending for DNS lookup is incomplete (queue is not empty, or not all
+  // names in map are sent, or ...) then a task to continue processing is
+  // sent to our thread loop.
+  void SubmitHostnames();
+
+  // The following is private, but exposed for testing purposes only.
+  static bool RenderDnsMaster::is_numeric_ip(const char* name, size_t length);
+
+ private:
+  // ExtractBufferedNames pulls names from queue into the map, reducing or
+  // eliminating a waiting queue.
+  // The size_goal argument can be used to reduce the amount of
+  // processing done in this method, and can leave some data
+  // in the buffer under some circumstances.
+  // If size_goal is zero, then extraction proceeds until
+  // the queue is empty.  If size goal is positive, then
+  // extraction continues until the domain_map_ contains
+  // at least the specified number of names, or the buffer is empty.
+  void ExtractBufferedNames(size_t size_goal = 0);
+
+  // DnsPrefetchNames does not check the buffer, and just sends names
+  // that are already collected in the domain_map_ for DNS lookup.
+  // If max_count is zero, then all available names are sent; and
+  // if positive, then at most max_count names will be sent.
+  void DnsPrefetchNames(size_t max_count = 0);
+
+  // Reset() restores initial state provided after construction.
+  // This discards ALL queue entries, and map entries.
+  void Reset();
+
+  // We use c_string_queue_ to hold lists of names supplied typically) by the
+  // renderer.  It queues the names, at minimal cost to the renderer's thread,
+  // and allows this class to process them when time permits (in a later task).
+  DnsQueue c_string_queue_;
+
+
+  // domain_map_ contains (for each domain) one of the next two constants,
+  // depending on whether we have asked the browser process to do the actual
+  // DNS lookup.
+  static const int kLookupRequested = 0x1;
+  static const int kPending = 0x0;
+  typedef std::map<std::string, int> DomainUseMap;
+  DomainUseMap domain_map_;
+
+  // Cache a tally of the count of names that haven't yet been sent
+  // for DNS pre-fetching.  Note that we *could* recalculate this
+  // count by iterating over domain_map_, looking for even values.
+  size_t new_name_count_;
+
+  // We have some metrics to examine performance.  We might use
+  // these metrics to modify buffer counts etc. some day.
+  int buffer_full_discard_count_;
+  int numeric_ip_discard_count_;
+
+  ScopedRunnableMethodFactory<RenderDnsMaster> render_dns_factory_;
+
+  DISALLOW_EVIL_CONSTRUCTORS(RenderDnsMaster);
+};  // class RenderDnsMaster
+
+#endif  // CHROME_RENDERER_RENDER_NET_DNS_MASTER_H__
diff --git a/chrome/renderer/net/render_dns_master_unittest.cc b/chrome/renderer/net/render_dns_master_unittest.cc
new file mode 100644
index 0000000..beaddf7
--- /dev/null
+++ b/chrome/renderer/net/render_dns_master_unittest.cc
@@ -0,0 +1,61 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Single threaded tests of RenderDnsMaster functionality.
+
+#include "chrome/renderer/net/render_dns_master.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+#include <algorithm>
+
+namespace {
+
+class RenderDnsMasterTest : public testing::Test {
+};
+
+TEST(RenderDnsMasterTest, NumericIpDiscardCheck) {
+  // Regular names.
+  const std::string A("a.com"), B("b.net"), C("www.other.uk");
+  // Combination of digits plus dots.
+  const std::string N1("1.3."), N2("5.5.7.12");
+
+#define TESTNAME(string) RenderDnsMaster::is_numeric_ip((string.data()), \
+                                                        (string).size())
+
+  EXPECT_TRUE(TESTNAME(N1));
+  EXPECT_TRUE(TESTNAME(N2));
+
+  EXPECT_FALSE(TESTNAME(A));
+  EXPECT_FALSE(TESTNAME(B));
+  EXPECT_FALSE(TESTNAME(C));
+
+#undef TESTNAME
+}
+
+}  // namespace anonymous
\ No newline at end of file
diff --git a/chrome/renderer/net/render_dns_queue.cc b/chrome/renderer/net/render_dns_queue.cc
new file mode 100644
index 0000000..6a1661c
--- /dev/null
+++ b/chrome/renderer/net/render_dns_queue.cc
@@ -0,0 +1,169 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// See header file for description of DnsQueue class
+
+#include "chrome/renderer/net/render_dns_queue.h"
+
+#include "base/logging.h"
+#include "base/stats_counters.h"
+
+DnsQueue::DnsQueue(BufferSize size)
+    : buffer_(new char[size + 2]),
+      buffer_size_(size + 1),
+      buffer_sentinel_(size + 1),
+      size_(0) {
+  CHECK(0 < static_cast<BufferSize>(size + 3));  // Avoid overflow worries.
+  buffer_[buffer_sentinel_] = '\0';  // Guard byte to help reading data.
+  readable_ = writeable_ = 0;  // Buffer starts empty.
+}
+
+DnsQueue::~DnsQueue(void) {
+}
+
+// Push takes an unterminated string plus its length.
+// The string must not contain a null terminator.
+// Exactly length chars are written, or nothing is written.
+// Returns true for success, false there was no room to push.
+DnsQueue::PushResult DnsQueue::Push(const char* source,
+                                    const size_t unsigned_length) {
+  BufferSize length = static_cast<BufferSize>(unsigned_length);
+  if (0 > length+1)  // Avoid overflows in conversion to signed.
+    return OVERFLOW_PUSH;
+
+  // To save on sites with a LOT of links to the SAME domain, we have a
+  // a compaction hack that removes duplicates when we try to push() a
+  // match with the last push.
+  if (0 < size_ && readable_ + length < buffer_sentinel_ &&
+    0 == strncmp(source, &buffer_[readable_], unsigned_length) &&
+    '\0' == buffer_[readable_ + unsigned_length]) {
+    SIMPLE_STATS_COUNTER(L"DNS.PrefetchDnsRedundantPush");
+
+    // We already wrote this name to the queue, so we'll skip this repeat.
+    return REDUNDANT_PUSH;
+  }
+
+  // Calling convention precludes nulls.
+  DCHECK(!length || '\0' != source[length - 1]);
+
+  DCHECK(Validate());
+
+  BufferSize available_space = readable_ - writeable_;
+
+  if (0 >= available_space) {
+    available_space += buffer_size_;
+  }
+
+  if (length + 1 >= available_space) {
+    SIMPLE_STATS_COUNTER(L"DNS.PrefetchDnsQueueFull");
+    return OVERFLOW_PUSH;  // Not enough space to push.
+  }
+
+  BufferSize dest = writeable_;
+  BufferSize space_till_wrap = buffer_sentinel_ - dest;
+  if (space_till_wrap < length + 1) {
+    // Copy until we run out of room at end of buffer.
+    std::memcpy(&buffer_[dest], source, space_till_wrap);
+    // Ensure caller didn't have embedded '\0' and also
+    // ensure trailing sentinel was in place.
+    DCHECK(space_till_wrap == strlen(&buffer_[dest]));  // Relies on sentinel.
+
+    length -= space_till_wrap;
+    source += space_till_wrap;
+    dest = 0;  // Continue writing at start of buffer.
+  }
+
+  // Copy any remaining portion of source.
+  std::memcpy(&buffer_[dest], source, length);
+  DCHECK(dest + length < buffer_sentinel_);
+  buffer_[dest + length] = '\0';  // We need termination in our buffer.
+  DCHECK(length == strlen(&buffer_[dest]));  // Preclude embedded '\0'.
+
+  dest += length + 1;
+  if (dest == buffer_sentinel_)
+    dest = 0;
+
+  writeable_ = dest;
+  size_++;
+  DCHECK(Validate());
+  return SUCCESSFUL_PUSH;
+}
+
+// Extracts the next available string from the buffer.
+// The returned string is null terminated, and hence has length
+// that is exactly one greater than the written string.
+// If the buffer is empty, then the Pop and returns false.
+bool DnsQueue::Pop(std::string* out_string) {
+  DCHECK(Validate());
+  // Sentinel will preclude memory reads beyond buffer's end.
+  DCHECK('\0' == buffer_[buffer_sentinel_]);
+
+  if (readable_ == writeable_) {
+    return false;  // buffer was empty
+  }
+
+  // Constructor *may* rely on sentinel for null termination.
+  (*out_string) = &buffer_[readable_];
+  // Our sentinel_ at end of buffer precludes an overflow in cast.
+  BufferSize first_fragment_size = static_cast<BufferSize> (out_string->size());
+
+  BufferSize terminal_null;
+  if (readable_ + first_fragment_size >= buffer_sentinel_) {
+    // Sentinel was used, so we need the portion after the wrap.
+    out_string->append(&buffer_[0]);  // Fragment at start of buffer.
+    // Sentinel precludes overflow in cast to signed type.
+    terminal_null = static_cast<BufferSize>(out_string->size())
+                    - first_fragment_size;
+  } else {
+    terminal_null = readable_ + first_fragment_size;
+  }
+  DCHECK('\0' == buffer_[terminal_null]);
+
+  BufferSize new_readable = terminal_null + 1;
+  if (buffer_sentinel_ == new_readable)
+    new_readable = 0;
+
+  readable_ = new_readable;
+  size_--;
+  if (readable_ == writeable_ || 0 == size_) {
+    // Queue is empty, so reset to start of buffer to help with peeking.
+    readable_ = writeable_ = 0;
+  }
+  DCHECK(Validate());
+  return true;
+}
+
+bool DnsQueue::Validate() {
+  return (readable_ >= 0) &&
+          readable_ < buffer_sentinel_ &&
+          writeable_ >= 0 &&
+          writeable_ < buffer_sentinel_ &&
+          '\0' == buffer_[buffer_sentinel_] &&
+          ((0 == size_) == (readable_ == writeable_));
+}
diff --git a/chrome/renderer/net/render_dns_queue.h b/chrome/renderer/net/render_dns_queue.h
new file mode 100644
index 0000000..0a180f6
--- /dev/null
+++ b/chrome/renderer/net/render_dns_queue.h
@@ -0,0 +1,117 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// DnsQueue is implemented as an almost FIFO circular buffer for text
+// strings that don't have embedded nulls ('\0').  The "almost" element is that
+// some duplicate strings may be removed (i.e., the string won't really be
+// pushed *if* the class happens to notice that a duplicate is already in the
+// queue).
+// The buffers internal format is null terminated character strings
+// (a.k.a., c_strings).
+// It is written to be as fast as possible during push() operations, so
+// that there will be minimal performance impact on a supplier thread.
+// The push() operation will not block, and no memory allocation is involved
+// (internally) during the push operations.
+// The one caveat is that if there is insufficient space in the buffer to
+// accept additional string via a push(), then the push() will fail, and
+// the buffer will be unmodified.
+
+// This class was designed for use in DNS prefetch operations.  During
+// rendering, the supplier is the renderer (typically), and the consumer
+// is a thread that sends messages to an async DNS resolver.
+
+#ifndef CHROME_RENDERER_NET_RENDER_DNS_QUEUE_H__
+#define CHROME_RENDERER_NET_RENDER_DNS_QUEUE_H__
+
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/lock.h"
+#include "base/scoped_ptr.h"
+
+class DnsQueue {
+ public:
+  // BufferSize is a signed type used for indexing into a buffer.
+  typedef int32 BufferSize;
+
+  enum PushResult { SUCCESSFUL_PUSH, OVERFLOW_PUSH, REDUNDANT_PUSH };
+
+  // The size specified in the constructor creates a buffer large enough
+  // to hold at most one string of that length, or "many"
+  // strings of considerably shorter length.  Note that strings
+  // are padded internally with a terminal '\0" while stored,
+  // so if you are trying to be precise and get N strings of
+  // length K to fit, you should actually construct a buffer with
+  // an internal size of N*(K+1).
+  explicit DnsQueue(BufferSize size);
+  ~DnsQueue(void);
+
+  size_t Size() const { return size_; }
+  void Clear() {
+    size_ = 0;
+    readable_ = writeable_;
+    Validate();
+  }
+
+  // Push takes an unterminated string of the given length
+  // and inserts it into the queue for later
+  // extraction by read.  For each successful push(), there
+  // can later be a corresponding read() to extracted the text.
+  // The string must not contain an embedded null terminator
+  // Exactly length chars are written, or the push fails (where
+  // "fails" means nothing is written).
+  // Returns true for success, false for failure (nothing written).
+  PushResult Push(const char* source, const size_t length);
+
+  PushResult Push(std::string source) {
+    return Push(source.c_str(), source.length());
+  }
+
+  // Extract the next available string from the buffer.
+  // If the buffer is empty, then return false.
+  bool Pop(std::string* out_string);
+
+ private:
+  bool Validate();  // Checks that all internal data is valid.
+
+  const BufferSize buffer_size_;  // Size one smaller than allocated space.
+  const scoped_array<char> buffer_;  // Circular buffer, plus extra char ('\0').
+  const BufferSize buffer_sentinel_;  // Index of extra '\0' at end of buffer_.
+
+  // If writable_ == readable_, then the buffer is empty.
+  BufferSize readable_;  // Next readable char in buffer_.
+  BufferSize writeable_;  // The next space in buffer_ to push.
+
+  // Number of queued strings
+  size_t size_;
+
+  DISALLOW_EVIL_CONSTRUCTORS(DnsQueue);
+};  // class DnsQueue
+
+#endif  // CHROME_RENDERER_NET_RENDER_DNS_QUEUE_H__
diff --git a/chrome/renderer/net/render_dns_queue_unittest.cc b/chrome/renderer/net/render_dns_queue_unittest.cc
new file mode 100644
index 0000000..2829264
--- /dev/null
+++ b/chrome/renderer/net/render_dns_queue_unittest.cc
@@ -0,0 +1,287 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include <sstream>
+
+#include "chrome/renderer/net/render_dns_queue.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// Single threaded tests of DnsQueue functionality.
+
+namespace {
+
+class DnsQueueTest : public testing::Test {
+};
+
+// Define a helper class that does Push'es and Pop's of numbers.
+// This makes it easy to test a LOT of reads, and keep the expected Pop
+// value in sync with the Push value.
+class DnsQueueSequentialTester {
+ public:
+  DnsQueueSequentialTester::DnsQueueSequentialTester(
+    DnsQueue& buffer, int32 read_counter = 0, int32 write_counter = 0);
+
+  // Return of false means buffer was full, or would not take entry.
+  bool Push(void);  // Push the string value of next number.
+
+  // Return of false means buffer returned wrong value.
+  bool Pop(void);  // Validate string value of next read.
+
+ private:
+  DnsQueue* buffer_;
+  int32 read_counter_;  // expected value of next read string.
+  int32 write_counter_;  // Numerical value to write next string.
+  DISALLOW_EVIL_CONSTRUCTORS(DnsQueueSequentialTester);
+};
+
+
+DnsQueueSequentialTester::DnsQueueSequentialTester(
+  DnsQueue& buffer, int32 read_counter, int32 write_counter)
+    : buffer_(&buffer),
+      read_counter_(read_counter),
+      write_counter_(write_counter) {
+}
+
+bool DnsQueueSequentialTester::Push(void) {
+  std::ostringstream value;
+  value << write_counter_;
+
+  // Exercise both write methods intermittently.
+  DnsQueue::PushResult result = (write_counter_ % 2) ?
+       buffer_->Push(value.str().c_str(), value.str().size()) :
+       buffer_->Push(value.str());
+  if (DnsQueue::SUCCESSFUL_PUSH == result)
+    write_counter_++;
+  return DnsQueue::OVERFLOW_PUSH != result;
+}
+
+bool DnsQueueSequentialTester::Pop(void) {
+  std::string string;
+  if (buffer_->Pop(&string)) {
+    std::ostringstream expected_value;
+    expected_value << read_counter_++;
+    EXPECT_STREQ(expected_value.str().c_str(), string.c_str())
+        << "Pop did not match write for value " << read_counter_;
+    return true;
+  }
+  return false;
+}
+
+
+TEST(DnsQueueTest, BufferUseCheck) {
+  // Use a small buffer so we can see that we can't write a string as soon as it
+  // gets longer than one less than the buffer size.  The extra empty character
+  // is used to keep read and write pointers from overlapping when buffer is
+  // full.  This shows the buffer size can constrain writes (and we're not
+  // scribbling all over memory).
+  const int buffer_size = 3;  // Just room for 2 digts plus '\0' plus blank.
+  std::string string;
+  DnsQueue buffer(buffer_size);
+  DnsQueueSequentialTester tester(buffer);
+
+  EXPECT_FALSE(tester.Pop()) << "Pop from empty buffer succeeded";
+
+  int i;
+  for (i = 0; i < 102; i++) {
+    if (!tester.Push())
+      break;  // String was too large.
+    EXPECT_TRUE(tester.Pop()) << "Unable to read back data " << i;
+    EXPECT_FALSE(buffer.Pop(&string))
+                << "read from empty buffer not flagged";
+  }
+
+  EXPECT_GE(i, 100) << "Can't write 2 digit strings in 4 character buffer";
+  EXPECT_LT(i, 101) << "We wrote 3 digit strings into a 4 character buffer";
+}
+
+TEST(DnsQueueTest, SubstringUseCheck) {
+  // Verify that only substring is written/read.
+  const int buffer_size = 100;
+  const char big_string[] = "123456789";
+  std::string string;
+  DnsQueue buffer(buffer_size);
+
+  EXPECT_FALSE(buffer.Pop(&string)) << "Initial buffer not empty";
+
+  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(big_string, 3))
+      << "Can't write string";
+  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(big_string, 0))
+      << "Can't write null string";
+  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(big_string, 5))
+      << "Can't write string";
+
+  EXPECT_TRUE(buffer.Pop(&string)) << "Filled buffer marked as empty";
+  EXPECT_STREQ(string.c_str(), "123") << "Can't read actual data";
+  EXPECT_TRUE(buffer.Pop(&string)) << "Filled buffer marked as empty";
+  EXPECT_STREQ(string.c_str(), "") << "Can't read null string";
+  EXPECT_TRUE(buffer.Pop(&string)) << "Filled buffer marked as empty";
+  EXPECT_STREQ(string.c_str(), "12345") << "Can't read actual data";
+
+  EXPECT_FALSE(buffer.Pop(&string))
+              << "read from empty buffer not flagged";
+}
+
+TEST(DnsQueueTest, SizeCheck) {
+  // Verify that size is correctly accounted for in buffer.
+  const int buffer_size = 100;
+  std::string input_string = "Hello";
+  std::string string;
+  DnsQueue buffer(buffer_size);
+
+  EXPECT_EQ(0, buffer.Size());
+  EXPECT_FALSE(buffer.Pop(&string));
+  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(input_string));
+  EXPECT_EQ(1, buffer.Size());
+  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push("Hi There"));
+  EXPECT_EQ(2, buffer.Size());
+  EXPECT_TRUE(buffer.Pop(&string));
+  EXPECT_EQ(1, buffer.Size());
+  EXPECT_TRUE(buffer.Pop(&string));
+  EXPECT_EQ(0, buffer.Size());
+  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(input_string));
+  EXPECT_EQ(1, buffer.Size());
+
+  // Check to see that the first string, if repeated, is discarded.
+  EXPECT_EQ(DnsQueue::REDUNDANT_PUSH, buffer.Push(input_string));
+  EXPECT_EQ(1, buffer.Size());
+}
+
+TEST(DnsQueueTest, FillThenEmptyCheck) {
+  // Use a big buffer so we'll get a bunch of writes in.
+  // This tests to be sure the buffer holds many strings.
+  // We also make sure they all come out intact.
+  const int buffer_size = 1000;
+  int byte_usage_counter = 1;  // Separation character between pointer.
+  DnsQueue buffer(buffer_size);
+  DnsQueueSequentialTester tester(buffer);
+
+  int write_success;
+  for (write_success = 0; write_success < buffer_size; write_success++) {
+    if (!tester.Push())
+      break;
+    EXPECT_EQ(buffer.Size(), write_success + 1);
+    if (write_success > 99)
+      byte_usage_counter += 4;  // 3 digit plus '\0'.
+    else if (write_success > 9)
+      byte_usage_counter += 3;  // 2 digits plus '\0'.
+    else
+      byte_usage_counter += 2;  // Digit plus '\0'.
+  }
+  EXPECT_LE(byte_usage_counter, buffer_size)
+      << "Written data exceeded buffer size";
+  EXPECT_GE(byte_usage_counter, buffer_size - 4)
+      << "Buffer does not appear to have filled";
+
+  EXPECT_GE(write_success, 10) << "Couldn't even write 10 one digit strings "
+      "in " << buffer_size << " byte buffer";
+
+
+  while (1) {
+    if (!tester.Pop())
+      break;
+    write_success--;
+  }
+  EXPECT_EQ(write_success, 0) << "Push and Pop count were different";
+
+  EXPECT_FALSE(tester.Pop()) << "Read from empty buffer succeeded";
+}
+
+TEST(DnsQueueTest, ClearCheck) {
+  // Use a big buffer so we'll get a bunch of writes in.
+  const int buffer_size = 1000;
+  DnsQueue buffer(buffer_size);
+  std::string string("ABC");
+  DnsQueueSequentialTester tester(buffer);
+
+  int write_success;
+  for (write_success = 0; write_success < buffer_size; write_success++) {
+    if (!tester.Push())
+      break;
+    EXPECT_EQ(buffer.Size(), write_success + 1);
+  }
+
+  buffer.Clear();
+  EXPECT_EQ(buffer.Size(), 0);
+
+  int write_success2;
+  for (write_success2 = 0; write_success2 < buffer_size; write_success2++) {
+    if (!tester.Push())
+      break;
+    EXPECT_EQ(buffer.Size(), write_success2 + 1);
+  }
+
+  for (; write_success2 > 0; write_success2--) {
+    EXPECT_EQ(buffer.Size(), write_success2);
+    EXPECT_TRUE(buffer.Pop(&string));
+  }
+
+  EXPECT_EQ(buffer.Size(), 0);
+  buffer.Clear();
+  EXPECT_EQ(buffer.Size(), 0);
+}
+
+TEST(DnsQueueTest, WrapOnVariousSubstrings) {
+  // Use a prime number for the allocated buffer size so that we tend
+  // to exercise all possible edge conditions (in circular text buffer).
+  // Once we're over 10 writes, all our strings are 2 digits long,
+  // with a '\0' terminator added making 3 characters per write.
+  // Since 3 is relatively prime to 23, we'll soon wrap (about
+  // every 6 writes).  Hence after 18 writes, we'll have tested all
+  // edge conditions.  We'll first do this where we empty the buffer
+  // after each write, and then again where there are some strings
+  // still in the buffer after each write.
+  const int prime_number = 23;
+  // Circular buffer needs an extra extra space to distinguish full from empty.
+  const int buffer_size = prime_number - 1;
+  DnsQueue buffer(buffer_size);
+  DnsQueueSequentialTester tester(buffer);
+
+  // First test empties between each write. Second loop
+  // has writes for each pop.  Third has three pushes per pop.
+  // Third has two items pending during each write.
+  for (int j = 0; j < 3; j++) {
+    // Each group does 30 tests, which is more than 10+18
+    // which was needed to get into the thorough testing zone
+    // mentioned above.
+    for (int i = 0; i < 30; i++) {
+      EXPECT_TRUE(tester.Push()) << "write failed with only " << j
+                                    << " blocks in buffer";
+      EXPECT_TRUE(tester.Pop()) << "Unable to read back data ";
+    }
+    EXPECT_TRUE(tester.Push());
+  }
+
+  // Read back the accumulated 3 extra blocks.
+  EXPECT_TRUE(tester.Pop());
+  EXPECT_TRUE(tester.Pop());
+  EXPECT_TRUE(tester.Pop());
+  EXPECT_FALSE(tester.Pop());
+}
+
+};  // namespace