Speed up sanitizing headers received from HTTP proxies.

net/http/proxy_client_socket.cc

Index: net/http/proxy_client_socket.cc
diff --git a/net/http/proxy_client_socket.cc b/net/http/proxy_client_socket.cc
index 453b6d94d42a223f5d8d8d622b4c68970b126020..1cfa0c3a194a70c7d716083e46c427a293f7dcc6 100644
--- a/net/http/proxy_client_socket.cc
+++ b/net/http/proxy_client_socket.cc
@@ -4,7 +4,10 @@
 
 #include "net/http/proxy_client_socket.h"
 
+#include <unordered_set>
+
 #include "base/metrics/histogram_macros.h"
+#include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "net/base/host_port_pair.h"
 #include "net/base/net_errors.h"
@@ -16,20 +19,6 @@
 
 namespace net {
 
-namespace {
-
-void CopyHeaderValues(scoped_refptr<HttpResponseHeaders> source,
-                      scoped_refptr<HttpResponseHeaders> dest,
-                      const std::string& header_name) {
-  size_t iter = 0;
-  std::string header_value;
-
-  while (source->EnumerateHeader(&iter, header_name, &header_value))
-    dest->AddHeader(header_name + ": " + header_value);
-}
-
-}  // namespace
-
 // static
 void ProxyClientSocket::BuildTunnelRequest(
     const HostPortPair& endpoint,
@@ -87,27 +76,38 @@ void ProxyClientSocket::LogBlockedTunnelResponse(int http_status_code,
 bool ProxyClientSocket::SanitizeProxyAuth(HttpResponseInfo* response) {
   DCHECK(response && response->headers.get());
 
-  scoped_refptr<HttpResponseHeaders> old_headers = response->headers;
-
-  const char kHeaders[] = "HTTP/1.1 407 Proxy Authentication Required\n\n";
-  scoped_refptr<HttpResponseHeaders> new_headers = new HttpResponseHeaders(
-      HttpUtil::AssembleRawHeaders(kHeaders, arraysize(kHeaders)));
-
   // Copy status line and all hop-by-hop headers to preserve keep-alive
   // behavior.
-  new_headers->ReplaceStatusLine(old_headers->GetStatusLine());
-  CopyHeaderValues(old_headers, new_headers, "connection");
-  CopyHeaderValues(old_headers, new_headers, "proxy-connection");
-  CopyHeaderValues(old_headers, new_headers, "keep-alive");
-  CopyHeaderValues(old_headers, new_headers, "trailer");
-  CopyHeaderValues(old_headers, new_headers, "transfer-encoding");
-  CopyHeaderValues(old_headers, new_headers, "upgrade");
+  const char* kHeadersToKeep[] = {
+      "connection",         "proxy-connection", "keep-alive", "trailer",
+      "transfer-encoding",  "upgrade",
+
+      "content-length",
+
+      "proxy-authenticate",
+  };
 
-  CopyHeaderValues(old_headers, new_headers, "content-length");
+  // Create a list of all present header not in |kHeadersToKeep|, and then
+  // remove them.
+  size_t iter = 0;
+  std::string header_name;
+  std::string header_value;
+  std::unordered_set<std::string> headers_to_remove;
+  while (response->headers->EnumerateHeaderLines(&iter, &header_name,
+                                                 &header_value)) {
+    bool remove = true;
+    for (const char* header : kHeadersToKeep) {

[Julia Tuttle, 2017/01/19 22:26:40]

Might be faster to just unconditionally remove the headers to keep after adding
all the current headers?

[mmenke, 2017/01/23 17:28:14]

The problem with that is the same reason adding header lines one-at-a-time is
slow.  Each time we add/remove a header/all instances of a header, we re-parse
the headers from scratch, which is slow.

i.e., the new bad case would be:

a:a
b:a
c:a
d:a
....

Each remove call would require a few more bytes than each add call requires now,
but we'd still have O(n^2) time for an O(n log n) length input (log n is because
keys have to grow in length to be unique).

This approach instead only parses the output string once, so I think should be
more robust against bad inputs.

+      if (base::EqualsCaseInsensitiveASCII(header, header_name)) {
+        remove = false;
+        break;
+      }
+    }
+    if (remove)
+      headers_to_remove.insert(header_name);
+  }
 
-  CopyHeaderValues(old_headers, new_headers, "proxy-authenticate");
+  response->headers->RemoveHeaders(headers_to_remove);
 
-  response->headers = new_headers;
   return true;
 }