Fix bug 59917 - Network position cache can get time clashes

Now use a lru list for cache eviction.
Also adds a test for the cache, and makes the cache public for testing.

BUG=59917
TEST=GeolocationNetworkProviderTest.NetworkPositionCache

Review URL: http://codereview.chromium.org/3954001

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@63351 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 164 insertions, 99 deletions

diff --git a/chrome/browser/geolocation/network_location_provider.cc b/chrome/browser/geolocation/network_location_provider.cc
index 1f77fbc..cb3fbf5 100644
--- a/chrome/browser/geolocation/network_location_provider.cc
+++ b/chrome/browser/geolocation/network_location_provider.cc
@@ -12,103 +12,92 @@ namespace {
 // The maximum period of time we'll wait for a complete set of device data
 // before sending the request.
 const int kDataCompleteWaitPeriod = 1000 * 2;  // 2 seconds
-
-// The maximum size of the cache of positions for previously requested device
-// data.
-const size_t kMaximumCacheSize = 10;
 }  // namespace
 
-// The PositionCache handles caching and retrieving a position returned by a
-// network location provider. It is not thread safe. It's methods are called on
-// multiple threads by NetworkLocationProvider, but the timing is such that
-// thread safety is not required.
-class NetworkLocationProvider::PositionCache {
- public:
-  // Caches the current position response for the current set of cell ID and
-  // WiFi data. Returns true on success, false otherwise.
-  bool CachePosition(const GatewayData& gateway_data,
-                     const RadioData& radio_data,
-                     const WifiData& wifi_data,
-                     const Geoposition& position) {
-    // Check that we can generate a valid key for the device data.
-    string16 key;
-    if (!MakeKey(gateway_data, radio_data, wifi_data, &key)) {
-      return false;
-    }
-    // If the cache is full, remove the oldest entry.
-    if (cache_.size() == kMaximumCacheSize) {
-      DCHECK(cache_times_.size() == kMaximumCacheSize);
-      CacheTimesMap::iterator oldest_entry = cache_times_.begin();
-      DCHECK(oldest_entry != cache_times_.end());
-      cache_.erase(oldest_entry->second);
-      cache_times_.erase(oldest_entry);
-    }
-    // Insert the position into the cache.
-    std::pair<CacheMap::iterator, bool> result =
-        cache_.insert(std::make_pair(key, position));
-    DCHECK(result.second);
-    cache_times_[position.timestamp] = result.first;
-    DCHECK(cache_.size() == cache_times_.size());
-    return true;
-  }
+// static
+const size_t NetworkLocationProvider::PositionCache::kMaximumSize = 10;
 
-  // Searches for a cached position response for the current set of cell ID and
-  // WiFi data. Returns the cached position if available, NULL otherwise.
-  const Geoposition *FindPosition(const GatewayData &gateway_data,
-                                  const RadioData &radio_data,
-                                  const WifiData &wifi_data) {
-    string16 key;
-    if (!MakeKey(gateway_data, radio_data, wifi_data, &key)) {
-      return NULL;
-    }
-    CacheMap::const_iterator iter = cache_.find(key);
-    return iter == cache_.end() ? NULL : &iter->second;
+bool NetworkLocationProvider::PositionCache::CachePosition(
+    const GatewayData& gateway_data,
+    const WifiData& wifi_data,
+    const Geoposition& position) {
+  // Check that we can generate a valid key for the device data.
+  string16 key;
+  if (!MakeKey(gateway_data, wifi_data, &key)) {
+    return false;
   }
+  // If the cache is full, remove the oldest entry.
+  if (cache_.size() == kMaximumSize) {
+    DCHECK(cache_age_list_.size() == kMaximumSize);
+    CacheAgeList::iterator oldest_entry = cache_age_list_.begin();
+    DCHECK(oldest_entry != cache_age_list_.end());
+    cache_.erase(*oldest_entry);
+    cache_age_list_.erase(oldest_entry);
+  }
+  DCHECK_LT(cache_.size(), kMaximumSize);
+  // Insert the position into the cache.
+  std::pair<CacheMap::iterator, bool> result =
+      cache_.insert(std::make_pair(key, position));
+  if (!result.second) {
+    NOTREACHED();  // We never try to add the same key twice.
+    CHECK_EQ(cache_.size(), cache_age_list_.size());
+    return false;
+  }
+  cache_age_list_.push_back(result.first);
+  DCHECK_EQ(cache_.size(), cache_age_list_.size());
+  return true;
+}
 
-  // Makes the key for the map of cached positions, using a set of
-  // device data. Returns true if a good key was generated, false otherwise.
-  static bool MakeKey(const GatewayData& gateway_data,
-                      const RadioData& /*radio_data*/,
-                      const WifiData& wifi_data,
-                      string16* key) {
-    // Currently we use only the WiFi data and gateway data, and base the
-    // key only on the MAC addresses.
-    // TODO(steveblock): Make use of radio_data.
-    DCHECK(key);
-    key->clear();
-    key->reserve(wifi_data.access_point_data.size() * 19 +
-        gateway_data.router_data.size() * 19);
-    const string16 separator(ASCIIToUTF16("|"));
-    for (GatewayData::RouterDataSet::const_iterator iter =
-         gateway_data.router_data.begin();
-         iter != gateway_data.router_data.end();
-         iter++) {
-      *key += separator;
-      *key += iter->mac_address;
-      *key += separator;
-    }
-    for (WifiData::AccessPointDataSet::const_iterator iter =
-         wifi_data.access_point_data.begin();
-         iter != wifi_data.access_point_data.end();
-         iter++) {
-      *key += separator;
-      *key += iter->mac_address;
-      *key += separator;
-    }
-    // If the key is the empty string, return false, as we don't want to cache a
-    // position for such a set of device data.
-    return !key->empty();
+// Searches for a cached position response for the current set of cell ID and
+// WiFi data. Returns the cached position if available, NULL otherwise.
+const Geoposition* NetworkLocationProvider::PositionCache::FindPosition(
+    const GatewayData& gateway_data,
+    const WifiData& wifi_data) {
+  string16 key;
+  if (!MakeKey(gateway_data, wifi_data, &key)) {
+    return NULL;
   }
+  CacheMap::const_iterator iter = cache_.find(key);
+  return iter == cache_.end() ? NULL : &iter->second;
+}
 
- private:
-  // The cache of positions. This is stored using two maps. One map is keyed on
-  // a string that represents a set of device data, the other is keyed on the
-  // timestamp of the position.
-  typedef std::map<string16, Geoposition> CacheMap;
-  CacheMap cache_;
-  typedef std::map<base::Time, CacheMap::iterator> CacheTimesMap;
-  CacheTimesMap cache_times_;
-};
+// Makes the key for the map of cached positions, using a set of
+// device data. Returns true if a good key was generated, false otherwise.
+//
+// static
+bool NetworkLocationProvider::PositionCache::MakeKey(
+    const GatewayData& gateway_data,
+    const WifiData& wifi_data,
+    string16* key) {
+  // Currently we use only the WiFi data and gateway data, and base the
+  // key only on the MAC addresses.
+  // TODO(joth): Make use of radio_data.
+  DCHECK(key);
+  key->clear();
+  const size_t kCharsPerMacAddress = 6 * 3 + 1;  // e.g. "11:22:33:44:55:66|"
+  key->reserve(wifi_data.access_point_data.size() * kCharsPerMacAddress
+               + gateway_data.router_data.size() * kCharsPerMacAddress);
+  const string16 separator(ASCIIToUTF16("|"));
+  for (GatewayData::RouterDataSet::const_iterator iter =
+       gateway_data.router_data.begin();
+       iter != gateway_data.router_data.end();
+       iter++) {
+    *key += separator;
+    *key += iter->mac_address;
+    *key += separator;
+  }
+  for (WifiData::AccessPointDataSet::const_iterator iter =
+       wifi_data.access_point_data.begin();
+       iter != wifi_data.access_point_data.end();
+       iter++) {
+    *key += separator;
+    *key += iter->mac_address;
+    *key += separator;
+  }
+  // If the key is the empty string, return false, as we don't want to cache a
+  // position for such a set of device data.
+  return !key->empty();
+}
 
 // NetworkLocationProvider factory function
 LocationProviderBase* NewNetworkLocationProvider(
@@ -207,8 +196,7 @@ void NetworkLocationProvider::LocationResponseAvailable(
   // Record the position and update our cache.
   position_ = position;
   if (position.IsValidFix()) {
-    position_cache_->CachePosition(gateway_data, radio_data,
-                                   wifi_data, position);
+    position_cache_->CachePosition(gateway_data, wifi_data, position);
   }
 
   // Record access_token if it's set.
@@ -273,7 +261,7 @@ void NetworkLocationProvider::RequestPosition() {
     return;
 
   const Geoposition* cached_position =
-      position_cache_->FindPosition(gateway_data_, radio_data_, wifi_data_);
+      position_cache_->FindPosition(gateway_data_, wifi_data_);
   DCHECK(!device_data_updated_timestamp_.is_null()) <<
       "Timestamp must be set before looking up position";
   if (cached_position) {
diff --git a/chrome/browser/geolocation/network_location_provider.h b/chrome/browser/geolocation/network_location_provider.h
index e86f93c..47267f2 100644
--- a/chrome/browser/geolocation/network_location_provider.h
+++ b/chrome/browser/geolocation/network_location_provider.h
@@ -6,6 +6,7 @@
 #define CHROME_BROWSER_GEOLOCATION_NETWORK_LOCATION_PROVIDER_H_
 #pragma once
 
+#include <list>
 #include <string>
 
 #include "base/basictypes.h"
@@ -27,6 +28,43 @@ class NetworkLocationProvider
       public WifiDataProvider::ListenerInterface,
       public NetworkLocationRequest::ListenerInterface {
  public:
+  // Cache of recently resolved locations. Public for tests.
+  class PositionCache {
+   public:
+    // The maximum size of the cache of positions for previously requested
+    // device data.
+    static const size_t kMaximumSize;
+
+    // Caches the current position response for the current set of cell ID and
+    // WiFi data. In the case of the cache exceeding kMaximumSize this will
+    // evict old entries in FIFO orderer of being added.
+    // Returns true on success, false otherwise.
+    bool CachePosition(const GatewayData& gateway_data,
+                       const WifiData& wifi_data,
+                       const Geoposition& position);
+
+    // Searches for a cached position response for the current set of device
+    // data. Returns NULL if the position is not in the cache, or the cached
+    // position if available. Ownership remains with the cache.
+    const Geoposition* FindPosition(const GatewayData& gateway_data,
+                                    const WifiData& wifi_data);
+
+   private:
+    // Makes the key for the map of cached positions, using a set of
+    // device data. Returns true if a good key was generated, false otherwise.
+    static bool MakeKey(const GatewayData& gateway_data,
+                        const WifiData& wifi_data,
+                        string16* key);
+
+    // The cache of positions. This is stored as a map keyed on a string that
+    // represents a set of device data, and a list to provide
+    // least-recently-added eviction.
+    typedef std::map<string16, Geoposition> CacheMap;
+    CacheMap cache_;
+    typedef std::list<CacheMap::iterator> CacheAgeList;
+    CacheAgeList cache_age_list_;  // Oldest first.
+  };
+
   NetworkLocationProvider(AccessTokenStore* access_token_store,
                           URLRequestContextGetter* context,
                           const GURL& url,
@@ -41,9 +79,6 @@ class NetworkLocationProvider
   virtual void OnPermissionGranted(const GURL& requesting_frame);
 
  private:
-  // PositionCache is an implementation detail of NetworkLocationProvider.
-  class PositionCache;
-
   // Satisfies a position request from cache or network.
   void RequestPosition();
 
diff --git a/chrome/browser/geolocation/network_location_provider_unittest.cc b/chrome/browser/geolocation/network_location_provider_unittest.cc
index c0e2023..9bef39c 100644
--- a/chrome/browser/geolocation/network_location_provider_unittest.cc
+++ b/chrome/browser/geolocation/network_location_provider_unittest.cc
@@ -14,9 +14,13 @@
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace {
+// Constants used in multiple tests.
 const char kTestServerUrl[] = "https://www.geolocation.test/service";
 const char kTestHost[] = "myclienthost.test";
 const char kTestHostUrl[] = "http://myclienthost.test/some/path";
+// Using #define so we can easily paste this into various other strings.
+#define REFERENCE_ACCESS_TOKEN "2:k7j3G6LaL6u_lafw:4iXOeOpTh1glSXe"
+
 }  // namespace
 
 // Stops the specified (nested) message loop when the listener is called back.
@@ -125,6 +129,7 @@ class GeolocationNetworkProviderTest : public testing::Test {
   virtual void TearDown() {
     WifiDataProvider::ResetFactory();
     RadioDataProvider::ResetFactory();
+    GatewayDataProvider::ResetFactory();
     URLFetcher::set_factory(NULL);
   }
 
@@ -192,6 +197,15 @@ class GeolocationNetworkProviderTest : public testing::Test {
     return data;
   }
 
+  static Geoposition CreateReferencePosition(int id) {
+    Geoposition pos;
+    pos.latitude = id;
+    pos.longitude = -(id + 1);
+    pos.altitude = 2 * id;
+    pos.timestamp = base::Time::Now();
+    return pos;
+  }
+
   static void ParseGatewayRequest(const std::string& request_data,
                                   GatewayData* gateway_data_out) {
     scoped_ptr<Value> value(base::JSONReader::Read(request_data, false));
@@ -412,9 +426,7 @@ TEST_F(GeolocationNetworkProviderTest, MultipleWifiScansComplete) {
   TestURLFetcher* fetcher = get_url_fetcher_and_advance_id();
   ASSERT_TRUE(fetcher != NULL);
   CheckEmptyRequestIsValid(fetcher->upload_data());
-  // Complete the network request with bad position fix (using #define so we
-  // can paste this into various other strings below)
-  #define REFERENCE_ACCESS_TOKEN "2:k7j3G6LaL6u_lafw:4iXOeOpTh1glSXe"
+  // Complete the network request with bad position fix.
   const char* kNoFixNetworkResponse =
       "{"
       "  \"location\": null,"
@@ -737,3 +749,33 @@ TEST_F(GeolocationNetworkProviderTest,
   CheckRequestIsValid(fetcher->upload_data(), 0,
                       kScanCount, REFERENCE_ACCESS_TOKEN);
 }
+
+TEST_F(GeolocationNetworkProviderTest, NetworkPositionCache) {
+  NetworkLocationProvider::PositionCache cache;
+
+  const int kCacheSize = NetworkLocationProvider::PositionCache::kMaximumSize;
+  for (int i = 0; i < kCacheSize * 2 + 1; ++i) {
+    Geoposition pos = CreateReferencePosition(i);
+    bool ret = cache.CachePosition(CreateReferenceRouterData(2),
+                                   CreateReferenceWifiScanData(i), pos);
+    EXPECT_TRUE(ret)  << i;
+    const Geoposition* item = cache.FindPosition(
+        CreateReferenceRouterData(2),
+        CreateReferenceWifiScanData(i));
+    ASSERT_TRUE(item) << i;
+    EXPECT_EQ(pos.latitude, item->latitude)  << i;
+    EXPECT_EQ(pos.longitude, item->longitude)  << i;
+    if (i < kCacheSize) {
+      // Nothing should have spilled yet; check oldest item is still there.
+      EXPECT_TRUE(cache.FindPosition(CreateReferenceRouterData(2),
+                                     CreateReferenceWifiScanData(0)));
+    } else {
+      const int evicted = i - kCacheSize;
+      EXPECT_FALSE(cache.FindPosition(CreateReferenceRouterData(2),
+                                      CreateReferenceWifiScanData(evicted)));
+      EXPECT_TRUE(cache.FindPosition(CreateReferenceRouterData(2),
+                                     CreateReferenceWifiScanData(evicted + 1)));
+    }
+  }
+}
+