1// Copyright (c) 2010 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/string_util.h"
9
10namespace {
11
12// Helper to find the containing directory of path. In RFC 2617 this is what
13// they call the "last symbolic element in the absolute path".
14// Examples:
15//   "/foo/bar.txt" --> "/foo/"
16//   "/foo/" --> "/foo/"
17std::string GetParentDirectory(const std::string& path) {
18  std::string::size_type last_slash = path.rfind("/");
19  if (last_slash == std::string::npos) {
20    // No slash (absolute paths always start with slash, so this must be
21    // the proxy case which uses empty string).
22    DCHECK(path.empty());
23    return path;
24  }
25  return path.substr(0, last_slash + 1);
26}
27
28// Debug helper to check that |path| arguments are properly formed.
29// (should be absolute path, or empty string).
30void CheckPathIsValid(const std::string& path) {
31  DCHECK(path.empty() || path[0] == '/');
32}
33
34// Return true if |path| is a subpath of |container|. In other words, is
35// |container| an ancestor of |path|?
36bool IsEnclosingPath(const std::string& container, const std::string& path) {
37  DCHECK(container.empty() || *(container.end() - 1) == '/');
38  return ((container.empty() && path.empty()) ||
39          (!container.empty() && StartsWithASCII(path, container, true)));
40}
41
42// Debug helper to check that |origin| arguments are properly formed.
43void CheckOriginIsValid(const GURL& origin) {
44  DCHECK(origin.is_valid());
45  DCHECK(origin.SchemeIs("http") || origin.SchemeIs("https"));
46  DCHECK(origin.GetOrigin() == origin);
47}
48
49// Functor used by remove_if.
50struct IsEnclosedBy {
51  explicit IsEnclosedBy(const std::string& path) : path(path) { }
52  bool operator() (const std::string& x) {
53    return IsEnclosingPath(path, x);
54  }
55  const std::string& path;
56};
57
58}  // namespace
59
60namespace net {
61
62HttpAuthCache::HttpAuthCache() {
63}
64
65HttpAuthCache::~HttpAuthCache() {
66}
67
68// Performance: O(n), where n is the number of realm entries.
69HttpAuthCache::Entry* HttpAuthCache::Lookup(const GURL& origin,
70                                            const std::string& realm,
71                                            HttpAuth::Scheme scheme) {
72  CheckOriginIsValid(origin);
73
74  // Linear scan through the realm entries.
75  for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
76    if (it->origin() == origin && it->realm() == realm &&
77        it->scheme() == scheme)
78      return &(*it);
79  }
80  return NULL;  // No realm entry found.
81}
82
83// Performance: O(n*m), where n is the number of realm entries, m is the number
84// of path entries per realm. Both n amd m are expected to be small; m is
85// kept small because AddPath() only keeps the shallowest entry.
86HttpAuthCache::Entry* HttpAuthCache::LookupByPath(const GURL& origin,
87                                                  const std::string& path) {
88  HttpAuthCache::Entry* best_match = NULL;
89  size_t best_match_length = 0;
90  CheckOriginIsValid(origin);
91  CheckPathIsValid(path);
92
93  // RFC 2617 section 2:
94  // A client SHOULD assume that all paths at or deeper than the depth of
95  // the last symbolic element in the path field of the Request-URI also are
96  // within the protection space ...
97  std::string parent_dir = GetParentDirectory(path);
98
99  // Linear scan through the realm entries.
100  for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
101    size_t len = 0;
102    if (it->origin() == origin && it->HasEnclosingPath(parent_dir, &len) &&
103        (!best_match || len > best_match_length)) {
104      best_match_length = len;
105      best_match = &(*it);
106    }
107  }
108  return best_match;
109}
110
111HttpAuthCache::Entry* HttpAuthCache::Add(const GURL& origin,
112                                         const std::string& realm,
113                                         HttpAuth::Scheme scheme,
114                                         const std::string& auth_challenge,
115                                         const string16& username,
116                                         const string16& password,
117                                         const std::string& path) {
118  CheckOriginIsValid(origin);
119  CheckPathIsValid(path);
120
121  // Check for existing entry (we will re-use it if present).
122  HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme);
123  if (!entry) {
124    // Failsafe to prevent unbounded memory growth of the cache.
125    if (entries_.size() >= kMaxNumRealmEntries) {
126      LOG(WARNING) << "Num auth cache entries reached limit -- evicting";
127      entries_.pop_back();
128    }
129
130    entries_.push_front(Entry());
131    entry = &entries_.front();
132    entry->origin_ = origin;
133    entry->realm_ = realm;
134    entry->scheme_ = scheme;
135  }
136  DCHECK_EQ(origin, entry->origin_);
137  DCHECK_EQ(realm, entry->realm_);
138  DCHECK_EQ(scheme, entry->scheme_);
139
140  entry->auth_challenge_ = auth_challenge;
141  entry->username_ = username;
142  entry->password_ = password;
143  entry->nonce_count_ = 1;
144  entry->AddPath(path);
145
146  return entry;
147}
148
149HttpAuthCache::Entry::~Entry() {
150}
151
152void HttpAuthCache::Entry::UpdateStaleChallenge(
153    const std::string& auth_challenge) {
154  auth_challenge_ = auth_challenge;
155  nonce_count_ = 1;
156}
157
158HttpAuthCache::Entry::Entry()
159    : scheme_(HttpAuth::AUTH_SCHEME_MAX),
160      nonce_count_(0) {
161}
162
163void HttpAuthCache::Entry::AddPath(const std::string& path) {
164  std::string parent_dir = GetParentDirectory(path);
165  if (!HasEnclosingPath(parent_dir, NULL)) {
166    // Remove any entries that have been subsumed by the new entry.
167    paths_.remove_if(IsEnclosedBy(parent_dir));
168
169    // Failsafe to prevent unbounded memory growth of the cache.
170    if (paths_.size() >= kMaxNumPathsPerRealmEntry) {
171      LOG(WARNING) << "Num path entries for " << origin()
172                   << " has grown too large -- evicting";
173      paths_.pop_back();
174    }
175
176    // Add new path.
177    paths_.push_front(parent_dir);
178  }
179}
180
181bool HttpAuthCache::Entry::HasEnclosingPath(const std::string& dir,
182                                            size_t* path_len) {
183  DCHECK(GetParentDirectory(dir) == dir);
184  for (PathList::const_iterator it = paths_.begin(); it != paths_.end();
185       ++it) {
186    if (IsEnclosingPath(*it, dir)) {
187      // No element of paths_ may enclose any other element.
188      // Therefore this path is the tightest bound.  Important because
189      // the length returned is used to determine the cache entry that
190      // has the closest enclosing path in LookupByPath().
191      if (path_len)
192        *path_len = it->length();
193      return true;
194    }
195  }
196  return false;
197}
198
199bool HttpAuthCache::Remove(const GURL& origin,
200                           const std::string& realm,
201                           HttpAuth::Scheme scheme,
202                           const string16& username,
203                           const string16& password) {
204  for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) {
205    if (it->origin() == origin && it->realm() == realm &&
206        it->scheme() == scheme) {
207      if (username == it->username() && password == it->password()) {
208        entries_.erase(it);
209        return true;
210      }
211      return false;
212    }
213  }
214  return false;
215}
216
217bool HttpAuthCache::UpdateStaleChallenge(const GURL& origin,
218                                         const std::string& realm,
219                                         HttpAuth::Scheme scheme,
220                                         const std::string& auth_challenge) {
221  HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme);
222  if (!entry)
223    return false;
224  entry->UpdateStaleChallenge(auth_challenge);
225  return true;
226}
227
228}  // namespace net
229