1 // Copyright (c) 2009 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 "base/stl_util-inl.h" 6 #include "base/string_util.h" 7 #include "chrome/browser/extensions/extension_function.h" 8 #include "chrome/browser/extensions/extensions_quota_service.h" 9 #include "testing/gtest/include/gtest/gtest.h" 10 11 using base::TimeDelta; 12 using base::TimeTicks; 13 14 typedef QuotaLimitHeuristic::Bucket Bucket; 15 typedef QuotaLimitHeuristic::Config Config; 16 typedef QuotaLimitHeuristic::BucketList BucketList; 17 typedef ExtensionsQuotaService::TimedLimit TimedLimit; 18 typedef ExtensionsQuotaService::SustainedLimit SustainedLimit; 19 20 static const Config kFrozenConfig = { 0, TimeDelta::FromDays(0) }; 21 static const Config k2PerMinute = { 2, TimeDelta::FromMinutes(1) }; 22 static const Config k20PerHour = { 20, TimeDelta::FromHours(1) }; 23 static const TimeTicks kStartTime = TimeTicks(); 24 static const TimeTicks k1MinuteAfterStart = 25 kStartTime + TimeDelta::FromMinutes(1); 26 27 namespace { 28 class Mapper : public QuotaLimitHeuristic::BucketMapper { 29 public: 30 Mapper() {} 31 virtual ~Mapper() { STLDeleteValues(&buckets_); } 32 virtual void GetBucketsForArgs(const ListValue* args, BucketList* buckets) { 33 for (size_t i = 0; i < args->GetSize(); i++) { 34 int id; 35 ASSERT_TRUE(args->GetInteger(i, &id)); 36 if (buckets_.find(id) == buckets_.end()) 37 buckets_[id] = new Bucket(); 38 buckets->push_back(buckets_[id]); 39 } 40 } 41 private: 42 typedef std::map<int, Bucket*> BucketMap; 43 BucketMap buckets_; 44 DISALLOW_COPY_AND_ASSIGN(Mapper); 45 }; 46 47 class MockMapper : public QuotaLimitHeuristic::BucketMapper { 48 public: 49 virtual void GetBucketsForArgs(const ListValue* args, BucketList* buckets) {} 50 }; 51 52 class MockFunction : public ExtensionFunction { 53 public: 54 explicit MockFunction(const std::string& name) { set_name(name); } 55 virtual void SetArgs(const ListValue* args) {} 56 virtual const std::string GetError() { return std::string(); } 57 virtual const std::string GetResult() { return std::string(); } 58 virtual void Run() {} 59 }; 60 61 class TimedLimitMockFunction : public MockFunction { 62 public: 63 explicit TimedLimitMockFunction(const std::string& name) 64 : MockFunction(name) {} 65 virtual void GetQuotaLimitHeuristics( 66 QuotaLimitHeuristics* heuristics) const { 67 heuristics->push_back(new TimedLimit(k2PerMinute, new Mapper())); 68 } 69 }; 70 71 class ChainedLimitsMockFunction : public MockFunction { 72 public: 73 explicit ChainedLimitsMockFunction(const std::string& name) 74 : MockFunction(name) {} 75 virtual void GetQuotaLimitHeuristics( 76 QuotaLimitHeuristics* heuristics) const { 77 // No more than 2 per minute sustained over 5 minutes. 78 heuristics->push_back(new SustainedLimit(TimeDelta::FromMinutes(5), 79 k2PerMinute, new Mapper())); 80 // No more than 20 per hour. 81 heuristics->push_back(new TimedLimit(k20PerHour, new Mapper())); 82 } 83 }; 84 85 class FrozenMockFunction : public MockFunction { 86 public: 87 explicit FrozenMockFunction(const std::string& name) : MockFunction(name) {} 88 virtual void GetQuotaLimitHeuristics( 89 QuotaLimitHeuristics* heuristics) const { 90 heuristics->push_back(new TimedLimit(kFrozenConfig, new Mapper())); 91 } 92 }; 93 } // namespace 94 95 class ExtensionsQuotaServiceTest : public testing::Test { 96 public: 97 ExtensionsQuotaServiceTest() 98 : extension_a_("a"), extension_b_("b"), extension_c_("c") {} 99 virtual void SetUp() { 100 service_.reset(new ExtensionsQuotaService()); 101 } 102 virtual void TearDown() { 103 service_.reset(); 104 } 105 protected: 106 std::string extension_a_; 107 std::string extension_b_; 108 std::string extension_c_; 109 scoped_ptr<ExtensionsQuotaService> service_; 110 }; 111 112 class QuotaLimitHeuristicTest : public testing::Test { 113 public: 114 static void DoMoreThan2PerMinuteFor5Minutes(const TimeTicks& start_time, 115 QuotaLimitHeuristic* lim, 116 Bucket* b, 117 int an_unexhausted_minute) { 118 for (int i = 0; i < 5; i++) { 119 // Perform one operation in each minute. 120 int m = i * 60; 121 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(10 + m))); 122 EXPECT_TRUE(b->has_tokens()); 123 124 if (i == an_unexhausted_minute) 125 continue; // Don't exhaust all tokens this minute. 126 127 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(15 + m))); 128 EXPECT_FALSE(b->has_tokens()); 129 130 // These are OK because we haven't exhausted all buckets. 131 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(20 + m))); 132 EXPECT_FALSE(b->has_tokens()); 133 EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(50 + m))); 134 EXPECT_FALSE(b->has_tokens()); 135 } 136 } 137 }; 138 139 TEST_F(QuotaLimitHeuristicTest, Timed) { 140 TimedLimit lim(k2PerMinute, new MockMapper()); 141 Bucket b; 142 143 b.Reset(k2PerMinute, kStartTime); 144 EXPECT_TRUE(lim.Apply(&b, kStartTime)); 145 EXPECT_TRUE(b.has_tokens()); 146 EXPECT_TRUE(lim.Apply(&b, kStartTime + TimeDelta::FromSeconds(30))); 147 EXPECT_FALSE(b.has_tokens()); 148 EXPECT_FALSE(lim.Apply(&b, k1MinuteAfterStart)); 149 150 b.Reset(k2PerMinute, kStartTime); 151 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart - TimeDelta::FromSeconds(1))); 152 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart)); 153 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(1))); 154 EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(2))); 155 EXPECT_FALSE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(3))); 156 } 157 158 TEST_F(QuotaLimitHeuristicTest, Sustained) { 159 SustainedLimit lim(TimeDelta::FromMinutes(5), k2PerMinute, new MockMapper()); 160 Bucket bucket; 161 162 bucket.Reset(k2PerMinute, kStartTime); 163 DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, -1); 164 // This straw breaks the camel's back. 165 EXPECT_FALSE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(6))); 166 167 // The heuristic resets itself on a safe request. 168 EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromDays(1))); 169 170 // Do the same as above except don't exhaust final bucket. 171 bucket.Reset(k2PerMinute, kStartTime); 172 DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, -1); 173 EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(7))); 174 175 // Do the same as above except don't exhaust the 3rd (w.l.o.g) bucket. 176 bucket.Reset(k2PerMinute, kStartTime); 177 DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, 3); 178 // If the 3rd bucket were exhausted, this would fail (see first test). 179 EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(6))); 180 } 181 182 TEST_F(ExtensionsQuotaServiceTest, NoHeuristic) { 183 scoped_refptr<MockFunction> f(new MockFunction("foo")); 184 ListValue args; 185 EXPECT_TRUE(service_->Assess(extension_a_, f, &args, kStartTime)); 186 } 187 188 TEST_F(ExtensionsQuotaServiceTest, FrozenHeuristic) { 189 scoped_refptr<MockFunction> f(new FrozenMockFunction("foo")); 190 ListValue args; 191 args.Append(new FundamentalValue(1)); 192 EXPECT_FALSE(service_->Assess(extension_a_, f, &args, kStartTime)); 193 } 194 195 TEST_F(ExtensionsQuotaServiceTest, SingleHeuristic) { 196 scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo")); 197 ListValue args; 198 args.Append(new FundamentalValue(1)); 199 EXPECT_TRUE(service_->Assess(extension_a_, f, &args, kStartTime)); 200 EXPECT_TRUE(service_->Assess(extension_a_, f, &args, 201 kStartTime + TimeDelta::FromSeconds(10))); 202 EXPECT_FALSE(service_->Assess(extension_a_, f, &args, 203 kStartTime + TimeDelta::FromSeconds(15))); 204 205 ListValue args2; 206 args2.Append(new FundamentalValue(1)); 207 args2.Append(new FundamentalValue(2)); 208 EXPECT_TRUE(service_->Assess(extension_b_, f, &args2, kStartTime)); 209 EXPECT_TRUE(service_->Assess(extension_b_, f, &args2, 210 kStartTime + TimeDelta::FromSeconds(10))); 211 212 TimeDelta peace = TimeDelta::FromMinutes(30); 213 EXPECT_TRUE(service_->Assess(extension_b_, f, &args, kStartTime + peace)); 214 EXPECT_TRUE(service_->Assess(extension_b_, f, &args, 215 kStartTime + peace + TimeDelta::FromSeconds(10))); 216 EXPECT_FALSE(service_->Assess(extension_b_, f, &args2, 217 kStartTime + peace + TimeDelta::FromSeconds(15))); 218 219 // Test that items are independent. 220 ListValue args3; 221 args3.Append(new FundamentalValue(3)); 222 EXPECT_TRUE(service_->Assess(extension_c_, f, &args, kStartTime)); 223 EXPECT_TRUE(service_->Assess(extension_c_, f, &args3, 224 kStartTime + TimeDelta::FromSeconds(10))); 225 EXPECT_TRUE(service_->Assess(extension_c_, f, &args, 226 kStartTime + TimeDelta::FromSeconds(15))); 227 EXPECT_TRUE(service_->Assess(extension_c_, f, &args3, 228 kStartTime + TimeDelta::FromSeconds(20))); 229 EXPECT_FALSE(service_->Assess(extension_c_, f, &args, 230 kStartTime + TimeDelta::FromSeconds(25))); 231 EXPECT_FALSE(service_->Assess(extension_c_, f, &args3, 232 kStartTime + TimeDelta::FromSeconds(30))); 233 } 234 235 TEST_F(ExtensionsQuotaServiceTest, ChainedHeuristics) { 236 scoped_refptr<MockFunction> f(new ChainedLimitsMockFunction("foo")); 237 ListValue args; 238 args.Append(new FundamentalValue(1)); 239 240 // First, test that the low limit can be avoided but the higher one is hit. 241 // One event per minute for 20 minutes comes in under the sustained limit, 242 // but is equal to the timed limit. 243 for (int i = 0; i < 20; i++) { 244 EXPECT_TRUE(service_->Assess(extension_a_, f, &args, 245 kStartTime + TimeDelta::FromSeconds(10 + i * 60))); 246 } 247 248 // This will bring us to 21 events in an hour, which is a violation. 249 EXPECT_FALSE(service_->Assess(extension_a_, f, &args, 250 kStartTime + TimeDelta::FromMinutes(30))); 251 252 // Now, check that we can still hit the lower limit. 253 for (int i = 0; i < 5; i++) { 254 EXPECT_TRUE(service_->Assess(extension_b_, f, &args, 255 kStartTime + TimeDelta::FromSeconds(10 + i * 60))); 256 EXPECT_TRUE(service_->Assess(extension_b_, f, &args, 257 kStartTime + TimeDelta::FromSeconds(15 + i * 60))); 258 EXPECT_TRUE(service_->Assess(extension_b_, f, &args, 259 kStartTime + TimeDelta::FromSeconds(20 + i * 60))); 260 } 261 262 EXPECT_FALSE(service_->Assess(extension_b_, f, &args, 263 kStartTime + TimeDelta::FromMinutes(6))); 264 } 265 266 TEST_F(ExtensionsQuotaServiceTest, MultipleFunctionsDontInterfere) { 267 scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo")); 268 scoped_refptr<MockFunction> g(new TimedLimitMockFunction("bar")); 269 270 ListValue args_f; 271 ListValue args_g; 272 args_f.Append(new FundamentalValue(1)); 273 args_g.Append(new FundamentalValue(2)); 274 275 EXPECT_TRUE(service_->Assess(extension_a_, f, &args_f, kStartTime)); 276 EXPECT_TRUE(service_->Assess(extension_a_, g, &args_g, kStartTime)); 277 EXPECT_TRUE(service_->Assess(extension_a_, f, &args_f, 278 kStartTime + TimeDelta::FromSeconds(10))); 279 EXPECT_TRUE(service_->Assess(extension_a_, g, &args_g, 280 kStartTime + TimeDelta::FromSeconds(10))); 281 EXPECT_FALSE(service_->Assess(extension_a_, f, &args_f, 282 kStartTime + TimeDelta::FromSeconds(15))); 283 EXPECT_FALSE(service_->Assess(extension_a_, g, &args_g, 284 kStartTime + TimeDelta::FromSeconds(15))); 285 } 286 287 TEST_F(ExtensionsQuotaServiceTest, ViolatorsWillBeViolators) { 288 scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo")); 289 scoped_refptr<MockFunction> g(new TimedLimitMockFunction("bar")); 290 ListValue arg; 291 arg.Append(new FundamentalValue(1)); 292 EXPECT_TRUE(service_->Assess(extension_a_, f, &arg, kStartTime)); 293 EXPECT_TRUE(service_->Assess(extension_a_, f, &arg, 294 kStartTime + TimeDelta::FromSeconds(10))); 295 EXPECT_FALSE(service_->Assess(extension_a_, f, &arg, 296 kStartTime + TimeDelta::FromSeconds(15))); 297 298 // We don't allow this extension to use quota limited functions even if they 299 // wait a while. 300 EXPECT_FALSE(service_->Assess(extension_a_, f, &arg, 301 kStartTime + TimeDelta::FromDays(1))); 302 EXPECT_FALSE(service_->Assess(extension_a_, g, &arg, 303 kStartTime + TimeDelta::FromDays(1))); 304 } 305
