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