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/strings/string_util.h" 9 10 namespace { 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/" 17 std::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). 30 void 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|? 36 bool 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. 43 void CheckOriginIsValid(const GURL& origin) { 44 DCHECK(origin.is_valid()); 45 // Note that the scheme may be FTP when we're using a HTTP proxy. 46 DCHECK(origin.SchemeIsHTTPOrHTTPS() || origin.SchemeIs("ftp") || 47 origin.SchemeIsWSOrWSS()); 48 DCHECK(origin.GetOrigin() == origin); 49 } 50 51 // Functor used by remove_if. 52 struct IsEnclosedBy { 53 explicit IsEnclosedBy(const std::string& path) : path(path) { } 54 bool operator() (const std::string& x) const { 55 return IsEnclosingPath(path, x); 56 } 57 const std::string& path; 58 }; 59 60 } // namespace 61 62 namespace net { 63 64 HttpAuthCache::HttpAuthCache() { 65 } 66 67 HttpAuthCache::~HttpAuthCache() { 68 } 69 70 // Performance: O(n), where n is the number of realm entries. 71 HttpAuthCache::Entry* HttpAuthCache::Lookup(const GURL& origin, 72 const std::string& realm, 73 HttpAuth::Scheme scheme) { 74 CheckOriginIsValid(origin); 75 76 // Linear scan through the realm entries. 77 for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) { 78 if (it->origin() == origin && it->realm() == realm && 79 it->scheme() == scheme) 80 return &(*it); 81 } 82 return NULL; // No realm entry found. 83 } 84 85 // Performance: O(n*m), where n is the number of realm entries, m is the number 86 // of path entries per realm. Both n amd m are expected to be small; m is 87 // kept small because AddPath() only keeps the shallowest entry. 88 HttpAuthCache::Entry* HttpAuthCache::LookupByPath(const GURL& origin, 89 const std::string& path) { 90 HttpAuthCache::Entry* best_match = NULL; 91 size_t best_match_length = 0; 92 CheckOriginIsValid(origin); 93 CheckPathIsValid(path); 94 95 // RFC 2617 section 2: 96 // A client SHOULD assume that all paths at or deeper than the depth of 97 // the last symbolic element in the path field of the Request-URI also are 98 // within the protection space ... 99 std::string parent_dir = GetParentDirectory(path); 100 101 // Linear scan through the realm entries. 102 for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) { 103 size_t len = 0; 104 if (it->origin() == origin && it->HasEnclosingPath(parent_dir, &len) && 105 (!best_match || len > best_match_length)) { 106 best_match_length = len; 107 best_match = &(*it); 108 } 109 } 110 return best_match; 111 } 112 113 HttpAuthCache::Entry* HttpAuthCache::Add(const GURL& origin, 114 const std::string& realm, 115 HttpAuth::Scheme scheme, 116 const std::string& auth_challenge, 117 const AuthCredentials& credentials, 118 const std::string& path) { 119 CheckOriginIsValid(origin); 120 CheckPathIsValid(path); 121 122 // Check for existing entry (we will re-use it if present). 123 HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme); 124 if (!entry) { 125 // Failsafe to prevent unbounded memory growth of the cache. 126 if (entries_.size() >= kMaxNumRealmEntries) { 127 LOG(WARNING) << "Num auth cache entries reached limit -- evicting"; 128 entries_.pop_back(); 129 } 130 131 entries_.push_front(Entry()); 132 entry = &entries_.front(); 133 entry->origin_ = origin; 134 entry->realm_ = realm; 135 entry->scheme_ = scheme; 136 } 137 DCHECK_EQ(origin, entry->origin_); 138 DCHECK_EQ(realm, entry->realm_); 139 DCHECK_EQ(scheme, entry->scheme_); 140 141 entry->auth_challenge_ = auth_challenge; 142 entry->credentials_ = credentials; 143 entry->nonce_count_ = 1; 144 entry->AddPath(path); 145 146 return entry; 147 } 148 149 HttpAuthCache::Entry::~Entry() { 150 } 151 152 void HttpAuthCache::Entry::UpdateStaleChallenge( 153 const std::string& auth_challenge) { 154 auth_challenge_ = auth_challenge; 155 nonce_count_ = 1; 156 } 157 158 HttpAuthCache::Entry::Entry() 159 : scheme_(HttpAuth::AUTH_SCHEME_MAX), 160 nonce_count_(0) { 161 } 162 163 void 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 181 bool 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 199 bool HttpAuthCache::Remove(const GURL& origin, 200 const std::string& realm, 201 HttpAuth::Scheme scheme, 202 const AuthCredentials& credentials) { 203 for (EntryList::iterator it = entries_.begin(); it != entries_.end(); ++it) { 204 if (it->origin() == origin && it->realm() == realm && 205 it->scheme() == scheme) { 206 if (credentials.Equals(it->credentials())) { 207 entries_.erase(it); 208 return true; 209 } 210 return false; 211 } 212 } 213 return false; 214 } 215 216 bool HttpAuthCache::UpdateStaleChallenge(const GURL& origin, 217 const std::string& realm, 218 HttpAuth::Scheme scheme, 219 const std::string& auth_challenge) { 220 HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme); 221 if (!entry) 222 return false; 223 entry->UpdateStaleChallenge(auth_challenge); 224 return true; 225 } 226 227 void HttpAuthCache::UpdateAllFrom(const HttpAuthCache& other) { 228 for (EntryList::const_iterator it = other.entries_.begin(); 229 it != other.entries_.end(); ++it) { 230 // Add an Entry with one of the original entry's paths. 231 DCHECK(it->paths_.size() > 0); 232 Entry* entry = Add(it->origin(), it->realm(), it->scheme(), 233 it->auth_challenge(), it->credentials(), 234 it->paths_.back()); 235 // Copy all other paths. 236 for (Entry::PathList::const_reverse_iterator it2 = ++it->paths_.rbegin(); 237 it2 != it->paths_.rend(); ++it2) 238 entry->AddPath(*it2); 239 // Copy nonce count (for digest authentication). 240 entry->nonce_count_ = it->nonce_count_; 241 } 242 } 243 244 } // namespace net 245