Speed up sanitizing headers received from HTTP proxies.

net/http/proxy_client_socket.cc

 // Copyright (c) 2012 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/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"
 #include "net/http/http_auth_controller.h"
 #include "net/http/http_request_info.h"
 #include "net/http/http_response_headers.h"
 #include "net/http/http_response_info.h"
 #include "url/gurl.h"
 
 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,
     const HttpRequestHeaders& auth_headers,
     const std::string& user_agent,
     std::string* request_line,
     HttpRequestHeaders* request_headers) {
   // RFC 7230 Section 5.4 says a client MUST send a Host header field in all
   // HTTP/1.1 request messages, and Host SHOULD be the first header field
   // following the request-line.  Add "Proxy-Connection: keep-alive" for compat
@@ skipping 37 matching lines @@
         "Net.BlockedTunnelResponse.HttpProxy",
         HttpUtil::MapStatusCodeForHistogram(http_status_code),
         HttpUtil::GetStatusCodesForHistogram());
   }
 }
 
 // static
 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",
 
-  CopyHeaderValues(old_headers, new_headers, "content-length");
+      "content-length",
 
-  CopyHeaderValues(old_headers, new_headers, "proxy-authenticate");
+      "proxy-authenticate",
+  };
 
-  response->headers = new_headers;
+  // 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);
+  }
+
+  response->headers->RemoveHeaders(headers_to_remove);
+
   return true;
 }
 
 // static
 bool ProxyClientSocket::SanitizeProxyRedirect(HttpResponseInfo* response) {
   DCHECK(response && response->headers.get());
 
   std::string location;
   if (!response->headers->IsRedirect(&location))
     return false;
 
   // Return minimal headers; set "Content-Length: 0" to ignore response body.
   std::string fake_response_headers = base::StringPrintf(
       "HTTP/1.0 302 Found\n"
       "Location: %s\n"
       "Content-Length: 0\n"
       "Connection: close\n"
       "\n",
       location.c_str());
   std::string raw_headers =
       HttpUtil::AssembleRawHeaders(fake_response_headers.data(),
                                    fake_response_headers.length());
   response->headers = new HttpResponseHeaders(raw_headers);
 
   return true;
 }
 
 }  // namespace net