Home | History | Annotate | Download | only in http
      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 
     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() && StartsWithASCII(path, container, true)));
     41 }
     42 
     43 // Debug helper to check that |origin| arguments are properly formed.
     44 void 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.
     53 struct 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 
     61 void RecordLookupPosition(int position) {
     62   UMA_HISTOGRAM_COUNTS_100("Net.HttpAuthCacheLookupPosition", position);
     63 }
     64 
     65 void RecordLookupByPathPosition(int position) {
     66   UMA_HISTOGRAM_COUNTS_100("Net.HttpAuthCacheLookupByPathPosition", position);
     67 }
     68 
     69 }  // namespace
     70 
     71 namespace net {
     72 
     73 HttpAuthCache::HttpAuthCache() {
     74 }
     75 
     76 HttpAuthCache::~HttpAuthCache() {
     77 }
     78 
     79 // Performance: O(n), where n is the number of realm entries.
     80 HttpAuthCache::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.
    103 HttpAuthCache::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 
    135 HttpAuthCache::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 
    182 HttpAuthCache::Entry::~Entry() {
    183 }
    184 
    185 void HttpAuthCache::Entry::UpdateStaleChallenge(
    186     const std::string& auth_challenge) {
    187   auth_challenge_ = auth_challenge;
    188   nonce_count_ = 1;
    189 }
    190 
    191 HttpAuthCache::Entry::Entry()
    192     : scheme_(HttpAuth::AUTH_SCHEME_MAX),
    193       nonce_count_(0) {
    194 }
    195 
    196 void 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 
    217 bool 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 
    235 bool 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 
    252 bool HttpAuthCache::UpdateStaleChallenge(const GURL& origin,
    253                                          const std::string& realm,
    254                                          HttpAuth::Scheme scheme,
    255                                          const std::string& auth_challenge) {
    256   HttpAuthCache::Entry* entry = Lookup(origin, realm, scheme);
    257   if (!entry)
    258     return false;
    259   entry->UpdateStaleChallenge(auth_challenge);
    260   entry->last_use_time_ = base::TimeTicks::Now();
    261   return true;
    262 }
    263 
    264 void HttpAuthCache::UpdateAllFrom(const HttpAuthCache& other) {
    265   for (EntryList::const_iterator it = other.entries_.begin();
    266        it != other.entries_.end(); ++it) {
    267     // Add an Entry with one of the original entry's paths.
    268     DCHECK(it->paths_.size() > 0);
    269     Entry* entry = Add(it->origin(), it->realm(), it->scheme(),
    270                        it->auth_challenge(), it->credentials(),
    271                        it->paths_.back());
    272     // Copy all other paths.
    273     for (Entry::PathList::const_reverse_iterator it2 = ++it->paths_.rbegin();
    274          it2 != it->paths_.rend(); ++it2)
    275       entry->AddPath(*it2);
    276     // Copy nonce count (for digest authentication).
    277     entry->nonce_count_ = it->nonce_count_;
    278   }
    279 }
    280 
    281 }  // namespace net
    282