net/http/http_auth_cache.cc

   1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/http/http_auth_cache.h"
   6
   7 #include "base/logging.h"
   8 #include "base/metrics/histogram_macros.h"
   9 #include "base/strings/string_util.h"
  10
  11 namespace {
  12
  13 // Helper to find the containing directory of path. In RFC 2617 this is what
  14 // they call the "last symbolic element in the absolute path".
  15 // Examples:
  16 //   "/foo/bar.txt" --> "/foo/"
  17 //   "/foo/" --> "/foo/"
  18 std::string GetParentDirectory(const std::string& path) {
  19   std::string::size_type last_slash = path.rfind("/");
  20   if (last_slash == std::string::npos) {
  21     // No slash (absolute paths always start with slash, so this must be
  22     // the proxy case which uses empty string).
  23     DCHECK(path.empty());
  24     return path;
  25   }
  26   return path.substr(0, last_slash + 1);
  27 }
  28
  29 // Debug helper to check that |path| arguments are properly formed.
  30 // (should be absolute path, or empty string).
  31 void CheckPathIsValid(const std::string& path) {
  32   DCHECK(path.empty() || path[0] == '/');
  33 }
  34
  35 // Return true if |path| is a subpath of |container|. In other words, is
  36 // |container| an ancestor of |path|?
  37 bool IsEnclosingPath(const std::string& container, const std::string& path) {
  38   DCHECK(container.empty() || *(container.end() - 1) == '/');
  39   return ((container.empty() && path.empty()) ||
  40           (!container.empty() &&
  41            base::StartsWith(path, container, base::CompareCase::SENSITIVE)));
  42 }
  43
  44 // Debug helper to check that |origin| arguments are properly formed.
  45 void CheckOriginIsValid(const GURL& origin) {
  46   DCHECK(origin.is_valid());
  47   // Note that the scheme may be FTP when we're using a HTTP proxy.
  48   DCHECK(origin.SchemeIsHTTPOrHTTPS() || origin.SchemeIs("ftp") ||
  49          origin.SchemeIsWSOrWSS());
  50   DCHECK(origin.GetOrigin() == origin);
  51 }
  52
  53 // Functor used by remove_if.
  54 struct IsEnclosedBy {
  55   explicit IsEnclosedBy(const std::string& path) : path(path) { }
  56   bool operator() (const std::string& x) const {
  57     return IsEnclosingPath(path, x);
  58   }
  59   const std::string& path;
  60 };
  61
  62 void RecordLookupPosition(int position) {
  63   UMA_HISTOGRAM_COUNTS_100("Net.HttpAuthCacheLookupPosition", position);
  64 }
  65
  66 void RecordLookupByPathPosition(int position) {
  67   UMA_HISTOGRAM_COUNTS_100("Net.HttpAuthCacheLookupByPathPosition", position);
  68 }
  69
  70 }  // namespace
  71
  72 namespace net {
  73
  74 HttpAuthCache::HttpAuthCache() {
  75 }
  76
  77 HttpAuthCache::~HttpAuthCache() {
  78 }
  79
  80 // Performance: O(n), where n is the number of realm entries.
  81 HttpAuthCache::Entry* HttpAuthCache::Lookup(const GURL& origin,
  82                                             const std::string& realm,
  83                                             HttpAuth::Scheme scheme) {
  84   CheckOriginIsValid(origin);
  85
  86   int entries_examined = 0;
  87   // Linear scan through the realm entries.
  88   for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
  89     ++entries_examined;
  90     if (it->origin() == origin && it->realm() == realm &&
  91         it->scheme() == scheme) {
  92       it->last_use_time_ = base::TimeTicks::Now();
  93       RecordLookupPosition(entries_examined);
  94       return &(*it);
  95     }
  96   }
  97   RecordLookupPosition(0);
  98   return NULL;  // No realm entry found.
  99 }
 100
 101 // Performance: O(n*m), where n is the number of realm entries, m is the number
 102 // of path entries per realm. Both n amd m are expected to be small; m is
 103 // kept small because AddPath() only keeps the shallowest entry.
 104 HttpAuthCache::Entry* HttpAuthCache::LookupByPath(const GURL& origin,
 105                                                   const std::string& path) {
 106   HttpAuthCache::Entry* best_match = NULL;
 107   size_t best_match_length = 0;
 108   int best_match_position = 0;
 109   CheckOriginIsValid(origin);
 110   CheckPathIsValid(path);
 111
 112   // RFC 2617 section 2:
 113   // A client SHOULD assume that all paths at or deeper than the depth of
 114   // the last symbolic element in the path field of the Request-URI also are
 115   // within the protection space ...
 116   std::string parent_dir = GetParentDirectory(path);
 117
 118   int entries_examined = 0;
 119   // Linear scan through the realm entries.
 120   for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
 121     ++entries_examined;
 122     size_t len = 0;
 123     if (it->origin() == origin && it->HasEnclosingPath(parent_dir, &len) &&
 124         (!best_match || len > best_match_length)) {
 125       best_match = &(*it);
 126       best_match_length = len;
 127       best_match_position = entries_examined;
 128     }
 129   }
 130   if (best_match)
 131     best_match->last_use_time_ = base::TimeTicks::Now();
 132   RecordLookupByPathPosition(best_match_position);
 133   return best_match;
 134 }
 135
 136 HttpAuthCache::Entry* HttpAuthCache::Add(const GURL& origin,
 137                                          const std::string& realm,
 138                                          HttpAuth::Scheme scheme,
 139                                          const std::string& auth_challenge,
 140                                          const AuthCredentials& credentials,
 141                                          const std::string& path) {
 142   CheckOriginIsValid(origin);
 143   CheckPathIsValid(path);
 144
 145   base::TimeTicks now = base::TimeTicks::Now();
 146
 147   // Check for existing entry (we will re-use it if present).
 148   HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme);
 149   if (!entry) {
 150     bool evicted = false;
 151     // Failsafe to prevent unbounded memory growth of the cache.
 152     if (entries_.size() >= kMaxNumRealmEntries) {
 153       LOG(WARNING) << "Num auth cache entries reached limit -- evicting";
 154       UMA_HISTOGRAM_LONG_TIMES("Net.HttpAuthCacheAddEvictedCreation",
 155           now - entries_.back().creation_time_);
 156       UMA_HISTOGRAM_LONG_TIMES("Net.HttpAuthCacheAddEvictedLastUse",
 157           now - entries_.back().last_use_time_);
 158       entries_.pop_back();
 159       evicted = true;
 160     }
 161     UMA_HISTOGRAM_BOOLEAN("Net.HttpAuthCacheAddEvicted", evicted);
 162
 163     entries_.push_front(Entry());
 164     entry = &entries_.front();
 165     entry->origin_ = origin;
 166     entry->realm_ = realm;
 167     entry->scheme_ = scheme;
 168     entry->creation_time_ = now;
 169   }
 170   DCHECK_EQ(origin, entry->origin_);
 171   DCHECK_EQ(realm, entry->realm_);
 172   DCHECK_EQ(scheme, entry->scheme_);
 173
 174   entry->auth_challenge_ = auth_challenge;
 175   entry->credentials_ = credentials;
 176   entry->nonce_count_ = 1;
 177   entry->AddPath(path);
 178   entry->last_use_time_ = now;
 179
 180   return entry;
 181 }
 182
 183 HttpAuthCache::Entry::~Entry() {
 184 }
 185
 186 void HttpAuthCache::Entry::UpdateStaleChallenge(
 187     const std::string& auth_challenge) {
 188   auth_challenge_ = auth_challenge;
 189   nonce_count_ = 1;
 190 }
 191
 192 HttpAuthCache::Entry::Entry()
 193     : scheme_(HttpAuth::AUTH_SCHEME_MAX),
 194       nonce_count_(0) {
 195 }
 196
 197 void HttpAuthCache::Entry::AddPath(const std::string& path) {
 198   std::string parent_dir = GetParentDirectory(path);
 199   if (!HasEnclosingPath(parent_dir, NULL)) {
 200     // Remove any entries that have been subsumed by the new entry.
 201     paths_.remove_if(IsEnclosedBy(parent_dir));
 202
 203     bool evicted = false;
 204     // Failsafe to prevent unbounded memory growth of the cache.
 205     if (paths_.size() >= kMaxNumPathsPerRealmEntry) {
 206       LOG(WARNING) << "Num path entries for " << origin()
 207                    << " has grown too large -- evicting";
 208       paths_.pop_back();
 209       evicted = true;
 210     }
 211     UMA_HISTOGRAM_BOOLEAN("Net.HttpAuthCacheAddPathEvicted", evicted);
 212
 213     // Add new path.
 214     paths_.push_front(parent_dir);
 215   }
 216 }
 217
 218 bool HttpAuthCache::Entry::HasEnclosingPath(const std::string& dir,
 219                                             size_t* path_len) {
 220   DCHECK(GetParentDirectory(dir) == dir);
 221   for (PathList::const_iterator it = paths_.begin(); it != paths_.end();
 222        ++it) {
 223     if (IsEnclosingPath(*it, dir)) {
 224       // No element of paths_ may enclose any other element.
 225       // Therefore this path is the tightest bound.  Important because
 226       // the length returned is used to determine the cache entry that
 227       // has the closest enclosing path in LookupByPath().
 228       if (path_len)
 229         *path_len = it->length();
 230       return true;
 231     }
 232   }
 233   return false;
 234 }
 235
 236 bool HttpAuthCache::Remove(const GURL& origin,
 237                            const std::string& realm,
 238                            HttpAuth::Scheme scheme,
 239                            const AuthCredentials& credentials) {
 240   for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
 241     if (it->origin() == origin && it->realm() == realm &&
 242         it->scheme() == scheme) {
 243       if (credentials.Equals(it->credentials())) {
 244         entries_.erase(it);
 245         return true;
 246       }
 247       return false;
 248     }
 249   }
 250   return false;
 251 }
 252
 253 void HttpAuthCache::Clear() {
 254   entries_.clear();
 255 }
 256
 257 bool HttpAuthCache::UpdateStaleChallenge(const GURL& origin,
 258                                          const std::string& realm,
 259                                          HttpAuth::Scheme scheme,
 260                                          const std::string& auth_challenge) {
 261   HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme);
 262   if (!entry)
 263     return false;
 264   entry->UpdateStaleChallenge(auth_challenge);
 265   entry->last_use_time_ = base::TimeTicks::Now();
 266   return true;
 267 }
 268
 269 void HttpAuthCache::UpdateAllFrom(const HttpAuthCache& other) {
 270   for (EntryList::const_iterator it = other.entries_.begin();
 271        it != other.entries_.end(); ++it) {
 272     // Add an Entry with one of the original entry's paths.
 273     DCHECK(it->paths_.size() > 0);
 274     Entry* entry = Add(it->origin(), it->realm(), it->scheme(),
 275                        it->auth_challenge(), it->credentials(),
 276                        it->paths_.back());
 277     // Copy all other paths.
 278     for (Entry::PathList::const_reverse_iterator it2 = ++it->paths_.rbegin();
 279          it2 != it->paths_.rend(); ++it2)
 280       entry->AddPath(*it2);
 281     // Copy nonce count (for digest authentication).
 282     entry->nonce_count_ = it->nonce_count_;
 283   }
 284 }
 285
 286 }  // namespace net