Changing response caching logic to use less data and avoid use of static non POD vars.

This should also reduce number of calls to CalculateIdleState.

BUG=NONE
TEST=unit test ExtensionIdleApiTest.CacheTest


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

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

4 files changed, 274 insertions, 62 deletions

diff --git a/chrome/browser/extensions/extension_idle_api.cc b/chrome/browser/extensions/extension_idle_api.cc
index f648410..ffdf9a7 100644
--- a/chrome/browser/extensions/extension_idle_api.cc
+++ b/chrome/browser/extensions/extension_idle_api.cc
@@ -4,6 +4,7 @@
 
 #include "chrome/browser/extensions/extension_idle_api.h"
 
+#include <algorithm>
 #include <string>
 #include <map>
 
@@ -25,6 +26,7 @@
 namespace keys = extension_idle_api_constants;
 
 namespace {
+
 const int kIdlePollInterval = 1;  // Number of seconds between status checks
                                   // when polling for active.
 const int kThrottleInterval = 1;  // Number of seconds to throttle idle checks
@@ -35,63 +37,15 @@ const int kMaxThreshold = 4*60*60;  // Four hours, in seconds. Not set
                                     // arbitrarily high for security concerns.
 const unsigned int kMaxCacheSize = 100;  // Number of state queries to cache.
 
-struct TimeStampedIdleState {
-  IdleState idle_state;
-  double timestamp;
-  TimeStampedIdleState() : idle_state(IDLE_STATE_UNKNOWN), timestamp(0) {
-  }
-  TimeStampedIdleState(IdleState state, double time) : idle_state(state),
-                                                       timestamp(time) {
-  }
-};
-
-typedef std::map<int, TimeStampedIdleState> CachedStateMap;
-
-class ExtensionIdlePollingData {
- public:
-  ExtensionIdlePollingData() {
-  }
-
-  void Update(int threshold, IdleState new_state) {
-    CleanUp();
-    cached_answer_[threshold] = TimeStampedIdleState(new_state,
-        base::Time::Now().ToDoubleT());
-  }
-
-  bool ShouldThrottle(int threshold) {
-    if (cached_answer_[threshold].idle_state == IDLE_STATE_UNKNOWN)
-      return false;
-    double delta = base::Time::Now().ToDoubleT() -
-        cached_answer_[threshold].timestamp;
-    if (delta < kThrottleInterval)
-      return true;
-    else
-      return false;
-  }
-
-  IdleState GetCachedAnswer(int threshold) {
-    return cached_answer_[threshold].idle_state;
-  }
- private:
-  void CleanUp() {
-    if (cached_answer_.size() > kMaxCacheSize) {
-      double now = base::Time::Now().ToDoubleT();
-      for (CachedStateMap::iterator it = cached_answer_.begin();
-             it != cached_answer_.end(); ++it) {
-          if (now - it->second.timestamp > kThrottleInterval)
-            cached_answer_.erase(it);
-      }
-    }
-    if (cached_answer_.size() > kMaxCacheSize) {
-      cached_answer_.clear();
-    }
-  }
-
-  CachedStateMap cached_answer_;
-};
-
-// Used to throttle excessive calls to query for idle state
-ExtensionIdlePollingData polling_data;
+// Calculates the error query interval has in respect to idle interval.
+// The error is defined as amount of the query interval that is not part of the
+// idle interval.
+double QueryErrorFromIdle(double idle_start,
+                          double idle_end,
+                          double query_start,
+                          double query_end) {
+  return query_end - idle_end + std::max(0., idle_start - query_start);
+}
 
 // Internal class which is used to poll for changes in the system idle state.
 class ExtensionIdlePollingTask {
@@ -129,7 +83,7 @@ void ExtensionIdlePollingTask::IdleStateCallback(IdleState current_state) {
 
   ExtensionIdlePollingTask::poll_task_running_ = false;
 
-  polling_data.Update(threshold_, current_state);
+  ExtensionIdleCache::UpdateCache(threshold_, current_state);
 
   // Startup another polling task as we exit.
   if (current_state != IDLE_STATE_ACTIVE)
@@ -191,7 +145,9 @@ void ExtensionIdleQueryStateFunction::IdleStateCallback(int threshold,
   }
 
   result_.reset(CreateIdleValue(state));
-  polling_data.Update(threshold, state);
+
+  ExtensionIdleCache::UpdateCache(threshold, state);
+
   SendResponse(true);
 }
 
@@ -200,8 +156,9 @@ bool ExtensionIdleQueryStateFunction::RunImpl() {
   EXTENSION_FUNCTION_VALIDATE(args_->GetInteger(0, &threshold));
   threshold = CheckThresholdBounds(threshold);
 
-  if (polling_data.ShouldThrottle(threshold)) {
-    result_.reset(CreateIdleValue(polling_data.GetCachedAnswer(threshold)));
+  IdleState state = ExtensionIdleCache::CalculateIdleState(threshold);
+  if (state != IDLE_STATE_UNKNOWN) {
+    result_.reset(CreateIdleValue(state));
     SendResponse(true);
     return true;
   }
@@ -224,3 +181,91 @@ void ExtensionIdleEventRouter::OnIdleStateChange(Profile* profile,
   profile->GetExtensionEventRouter()->DispatchEventToRenderers(
       keys::kOnStateChanged, json_args, profile, GURL());
 }
+
+ExtensionIdleCache::CacheData ExtensionIdleCache::cached_data =
+    {-1, -1, -1, -1};
+
+IdleState ExtensionIdleCache::CalculateIdleState(int threshold) {
+  return CalculateState(threshold, base::Time::Now().ToDoubleT());
+}
+
+IdleState ExtensionIdleCache::CalculateState(int threshold, double now) {
+  if (threshold < kMinThreshold)
+    return IDLE_STATE_UNKNOWN;
+  double threshold_moment = now - static_cast<double>(threshold);
+  double throttle_interval = static_cast<double>(kThrottleInterval);
+
+  // We test for IDEL_STATE_LOCKED first, because the result should be
+  // independent of the data for idle and active state. If last state was
+  // LOCKED and test for LOCKED is satisfied we should always return LOCKED.
+  if (cached_data.latest_locked > 0 &&
+      now - cached_data.latest_locked < throttle_interval)
+    return IDLE_STATE_LOCKED;
+
+  // If thershold moment is beyond the moment after whih we are certain we have
+  // been active, return active state. We allow kThrottleInterval error.
+  if (cached_data.latest_known_active > 0 &&
+      threshold_moment - cached_data.latest_known_active < throttle_interval)
+    return IDLE_STATE_ACTIVE;
+
+  // If total error that query interval has in respect to last recorded idle
+  // interval is less than kThrottleInterval, return IDLE state.
+  // query interval is the interval [now, now - threshold] and the error is
+  // defined as amount of query interval that is outside of idle interval.
+  double error_from_idle =
+      QueryErrorFromIdle(cached_data.idle_interval_start,
+          cached_data.idle_interval_end, threshold_moment, now);
+  if (cached_data.idle_interval_end > 0 &&
+      error_from_idle < throttle_interval)
+    return IDLE_STATE_IDLE;
+
+  return IDLE_STATE_UNKNOWN;
+}
+
+void ExtensionIdleCache::UpdateCache(int threshold, IdleState state) {
+  Update(threshold, state, base::Time::Now().ToDoubleT());
+}
+
+void ExtensionIdleCache::Update(int threshold, IdleState state, double now) {
+  if (threshold < kMinThreshold)
+    return;
+  double threshold_moment = now - static_cast<double>(threshold);
+  switch (state) {
+    case IDLE_STATE_IDLE:
+      if (threshold_moment > cached_data.idle_interval_end) {
+        // Cached and new interval don't overlap. We disregard the cached one.
+        cached_data.idle_interval_start = threshold_moment;
+      } else {
+        // Cached and new interval overlap, so we can combine them. We set
+        // the cached interval begining to less recent one.
+        cached_data.idle_interval_start =
+            std::min(cached_data.idle_interval_start, threshold_moment);
+      }
+      cached_data.idle_interval_end = now;
+      // Reset data for LOCKED state, since the last query result is not
+      // LOCKED.
+      cached_data.latest_locked = -1;
+      break;
+    case IDLE_STATE_ACTIVE:
+      if (threshold_moment > cached_data.latest_known_active)
+        cached_data.latest_known_active = threshold_moment;
+      // Reset data for LOCKED state, since the last query result is not
+      // LOCKED.
+      cached_data.latest_locked = -1;
+      break;
+    case IDLE_STATE_LOCKED:
+      if (threshold_moment > cached_data.latest_locked)
+        cached_data.latest_locked = now;
+      break;
+    default:
+      return;
+  }
+}
+
+int ExtensionIdleCache::get_min_threshold() {
+  return kMinThreshold;
+}
+
+double ExtensionIdleCache::get_throttle_interval() {
+  return static_cast<double>(kThrottleInterval);
+}
diff --git a/chrome/browser/extensions/extension_idle_api.h b/chrome/browser/extensions/extension_idle_api.h
index 927c68c..c6c3b52 100644
--- a/chrome/browser/extensions/extension_idle_api.h
+++ b/chrome/browser/extensions/extension_idle_api.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -30,4 +30,49 @@ class ExtensionIdleQueryStateFunction : public AsyncExtensionFunction {
   void IdleStateCallback(int threshold, IdleState state);
 };
 
+// Class used for caching answers from CalculateIdleState.
+class ExtensionIdleCache {
+ public:
+  static IdleState CalculateIdleState(int threshold);
+  static void UpdateCache(int threshold, IdleState state);
+
+ private:
+  FRIEND_TEST_ALL_PREFIXES(ExtensionIdleApiTest, CacheTest);
+
+  struct CacheData {
+    // Latest moment in history after which we are certain that there was some
+    // activity. If we are querying for a  threshold beyond this moment, we know
+    // the result will be active.
+    double latest_known_active;
+    // [idle_interval_start, idle_interval_end] is the latest interval in
+    // history for which we are certain there was no activity.
+    double idle_interval_start;
+    double idle_interval_end;
+    // Set iff the last recored query result was IDLE_STATE_LOCKED. Equals the
+    // moment the result was recorded in cache.
+    double latest_locked;
+  };
+
+  // We assume moment is increasing with every call to one of these two methods.
+
+  // Tries to determine the idle state based on results of previous queries.
+  // |threshold| is time span in seconds from now we consider in calculating
+  // state.
+  // |moment| is the moment in time this method was called (should be equal to
+  // now, except in tests).
+  // Returns calculated state, or IDLE_STATE_UNKNOWN if the state could not be
+  // determined.
+  static IdleState CalculateState(int threshold, double moment);
+
+  // Updates cached data with the latest query result.
+  // |threshold| is threshold parameter of the query.
+  // |state| is result of the query.
+  // |moment| is moment in time this method is called.
+  static void Update(int threshold, IdleState state, double moment);
+
+  static int get_min_threshold();
+  static double get_throttle_interval();
+
+  static CacheData cached_data;
+};
 #endif  // CHROME_BROWSER_EXTENSIONS_EXTENSION_IDLE_API_H_
diff --git a/chrome/browser/extensions/extension_idle_api_unittest.cc b/chrome/browser/extensions/extension_idle_api_unittest.cc
new file mode 100644
index 0000000..7196c93
--- /dev/null
+++ b/chrome/browser/extensions/extension_idle_api_unittest.cc
@@ -0,0 +1,121 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <gtest/gtest.h>
+
+#include "chrome/browser/extensions/extension_idle_api.h"
+
+TEST(ExtensionIdleApiTest, CacheTest) {
+  double throttle_interval = ExtensionIdleCache::get_throttle_interval();
+  int min_threshold = ExtensionIdleCache::get_min_threshold();
+  double now = 10 * min_threshold;
+
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+            ExtensionIdleCache::CalculateState(min_threshold, now));
+
+  ExtensionIdleCache::Update(2 * min_threshold, IDLE_STATE_IDLE, now);
+
+  EXPECT_EQ(IDLE_STATE_IDLE,
+            ExtensionIdleCache::CalculateState(2 * min_threshold, now));
+  EXPECT_EQ(IDLE_STATE_IDLE,
+      ExtensionIdleCache::CalculateState(2 * min_threshold,
+                                         now + 0.9 * throttle_interval));
+  EXPECT_EQ(IDLE_STATE_IDLE,
+      ExtensionIdleCache::CalculateState(min_threshold,
+                                         now + 0.1 * throttle_interval));
+  // Threshold exeeds idle interval boundries.
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+      ExtensionIdleCache::CalculateState(2 * min_threshold + 1,
+                                         now + 0.1 * throttle_interval));
+  // It has been more than throttle interval since last query.
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+      ExtensionIdleCache::CalculateState(min_threshold,
+                                         now + 1.1 * throttle_interval));
+
+  now += 10 * min_threshold;
+  // Idle interval does not overlap with previous one.
+  ExtensionIdleCache::Update(5 * min_threshold, IDLE_STATE_IDLE, now);
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+            ExtensionIdleCache::CalculateState(7 * min_threshold, now));
+
+  now += min_threshold;
+  // Idle interval overlaps with previous one.
+  ExtensionIdleCache::Update(2 * min_threshold, IDLE_STATE_IDLE, now);
+  // Threshold exeeds last idle interval boundaries, but does not exeed union of
+  // two last (overlaping) idle intervals.
+  EXPECT_EQ(IDLE_STATE_IDLE,
+            ExtensionIdleCache::CalculateState(4 * min_threshold, now));
+
+  now += 0.2 * throttle_interval;
+  ExtensionIdleCache::Update(8 * min_threshold, IDLE_STATE_ACTIVE, now);
+  EXPECT_EQ(IDLE_STATE_IDLE,
+      ExtensionIdleCache::CalculateState(4 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+
+  // If both idle and active conditions are satisfied, return ACTIVE (because
+  // obviously ACTIVE was reported after last idle interval).
+  ExtensionIdleCache::Update(3 * min_threshold, IDLE_STATE_ACTIVE, now);
+  EXPECT_EQ(IDLE_STATE_ACTIVE,
+      ExtensionIdleCache::CalculateState(4 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+
+  now += 10 * min_threshold;
+  ExtensionIdleCache::Update(8 * min_threshold, IDLE_STATE_ACTIVE, now);
+  // Threshold does not exeed last active state, but the error is within
+  // throttle interval.
+  EXPECT_EQ(IDLE_STATE_ACTIVE,
+      ExtensionIdleCache::CalculateState(8 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+  // The error is not within throttle interval.
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+      ExtensionIdleCache::CalculateState(8 * min_threshold,
+                                         now + 1.1 * throttle_interval));
+
+  // We report LOCKED iff it was last reported state was LOCKED and  it has
+  // been less than throttle_interval since last query.
+  now += 10 * min_threshold;
+  ExtensionIdleCache::Update(4 * min_threshold, IDLE_STATE_LOCKED, now);
+  EXPECT_EQ(IDLE_STATE_LOCKED,
+      ExtensionIdleCache::CalculateState(2 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+  // More than throttle_interval since last query.
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+      ExtensionIdleCache::CalculateState(2 * min_threshold,
+                                         now + 1.1 * throttle_interval));
+
+  now += 0.2 * throttle_interval;
+  ExtensionIdleCache::Update(4 * min_threshold, IDLE_STATE_ACTIVE, now);
+  // Last reported query was ACTIVE.
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+      ExtensionIdleCache::CalculateState(2 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+
+  now += 0.2 * throttle_interval;
+  ExtensionIdleCache::Update(2 * min_threshold, IDLE_STATE_LOCKED, now);
+  EXPECT_EQ(IDLE_STATE_LOCKED,
+      ExtensionIdleCache::CalculateState(5 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+
+  now += 10 * min_threshold;
+  ExtensionIdleCache::Update(4 * min_threshold, IDLE_STATE_LOCKED, now);
+
+  now += 0.2 * throttle_interval;
+  ExtensionIdleCache::Update(2 * min_threshold, IDLE_STATE_IDLE, now);
+
+  // Last reported state was IDLE.
+  EXPECT_EQ(IDLE_STATE_UNKNOWN,
+      ExtensionIdleCache::CalculateState(3 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+
+  now += min_threshold;
+  ExtensionIdleCache::Update(2 * min_threshold, IDLE_STATE_LOCKED, now);
+
+  now += 0.2 * throttle_interval;
+  ExtensionIdleCache::Update(4 * min_threshold, IDLE_STATE_ACTIVE, now);
+
+  // Last reported state was ACTIVE.
+  EXPECT_EQ(IDLE_STATE_ACTIVE,
+      ExtensionIdleCache::CalculateState(6 * min_threshold,
+                                         now + 0.3 * throttle_interval));
+}
diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi
index 3f660d2..6003059 100644
--- a/chrome/chrome_tests.gypi
+++ b/chrome/chrome_tests.gypi
@@ -1276,6 +1276,7 @@
         'browser/extensions/extension_creator_filter_unittest.cc',
         'browser/extensions/extension_event_router_forwarder_unittest.cc',
         'browser/extensions/extension_icon_manager_unittest.cc',
+        'browser/extensions/extension_idle_api_unittest.cc',
         'browser/extensions/extension_info_map_unittest.cc',
         'browser/extensions/extension_menu_manager_unittest.cc',
         'browser/extensions/extension_omnibox_unittest.cc',