1 // Copyright (c) 2012 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 "sync/notifier/registration_manager.h"
6
7 #include <algorithm>
8 #include <cmath>
9 #include <cstddef>
10 #include <deque>
11 #include <vector>
12
13 #include "base/basictypes.h"
14 #include "base/message_loop/message_loop.h"
15 #include "base/stl_util.h"
16 #include "google/cacheinvalidation/include/invalidation-client.h"
17 #include "sync/notifier/invalidation_util.h"
18 #include "testing/gtest/include/gtest/gtest.h"
19
20 namespace syncer {
21 namespace {
22
23 // Fake registration manager that lets you override jitter.
24 class FakeRegistrationManager : public RegistrationManager {
25 public:
FakeRegistrationManager(invalidation::InvalidationClient * invalidation_client)26 explicit FakeRegistrationManager(
27 invalidation::InvalidationClient* invalidation_client)
28 : RegistrationManager(invalidation_client),
29 jitter_(0.0) {}
30
~FakeRegistrationManager()31 virtual ~FakeRegistrationManager() {}
32
SetJitter(double jitter)33 void SetJitter(double jitter) {
34 jitter_ = jitter;
35 }
36
37 protected:
GetJitter()38 virtual double GetJitter() OVERRIDE {
39 return jitter_;
40 }
41
42 private:
43 double jitter_;
44
45 DISALLOW_COPY_AND_ASSIGN(FakeRegistrationManager);
46 };
47
48 // Fake invalidation client that just stores the currently-registered
49 // object IDs.
50 class FakeInvalidationClient : public invalidation::InvalidationClient {
51 public:
FakeInvalidationClient()52 FakeInvalidationClient() {}
53
~FakeInvalidationClient()54 virtual ~FakeInvalidationClient() {}
55
LoseRegistration(const invalidation::ObjectId & oid)56 void LoseRegistration(const invalidation::ObjectId& oid) {
57 EXPECT_TRUE(ContainsKey(registered_ids_, oid));
58 registered_ids_.erase(oid);
59 }
60
LoseAllRegistrations()61 void LoseAllRegistrations() {
62 registered_ids_.clear();
63 }
64
65 // invalidation::InvalidationClient implementation.
66
Start()67 virtual void Start() OVERRIDE {}
Stop()68 virtual void Stop() OVERRIDE {}
Acknowledge(const invalidation::AckHandle & handle)69 virtual void Acknowledge(const invalidation::AckHandle& handle) OVERRIDE {}
70
Register(const invalidation::ObjectId & oid)71 virtual void Register(const invalidation::ObjectId& oid) OVERRIDE {
72 EXPECT_FALSE(ContainsKey(registered_ids_, oid));
73 registered_ids_.insert(oid);
74 }
75
Register(const std::vector<invalidation::ObjectId> & oids)76 virtual void Register(
77 const std::vector<invalidation::ObjectId>& oids) OVERRIDE {
78 // Unused for now.
79 }
80
Unregister(const invalidation::ObjectId & oid)81 virtual void Unregister(const invalidation::ObjectId& oid) OVERRIDE {
82 EXPECT_TRUE(ContainsKey(registered_ids_, oid));
83 registered_ids_.erase(oid);
84 }
85
Unregister(const std::vector<invalidation::ObjectId> & oids)86 virtual void Unregister(
87 const std::vector<invalidation::ObjectId>& oids) OVERRIDE {
88 // Unused for now.
89 }
90
GetRegisteredIdsForTest() const91 const ObjectIdSet& GetRegisteredIdsForTest() const {
92 return registered_ids_;
93 }
94
95 private:
96 ObjectIdSet registered_ids_;
97
98 DISALLOW_COPY_AND_ASSIGN(FakeInvalidationClient);
99 };
100
101 size_t kObjectIdsCount = 5;
102
GetIdForIndex(size_t index)103 invalidation::ObjectId GetIdForIndex(size_t index) {
104 char name[2] = "a";
105 name[0] += static_cast<char>(index);
106 return invalidation::ObjectId(1 + index, name);
107 }
108
GetSequenceOfIdsStartingAt(size_t start,size_t count)109 ObjectIdSet GetSequenceOfIdsStartingAt(size_t start, size_t count) {
110 ObjectIdSet ids;
111 for (size_t i = start; i < start + count; ++i)
112 ids.insert(GetIdForIndex(i));
113 return ids;
114 }
115
GetSequenceOfIds(size_t count)116 ObjectIdSet GetSequenceOfIds(size_t count) {
117 return GetSequenceOfIdsStartingAt(0, count);
118 }
119
ExpectPendingRegistrations(const ObjectIdSet & expected_pending_ids,double expected_delay_seconds,const RegistrationManager::PendingRegistrationMap & pending_registrations)120 void ExpectPendingRegistrations(
121 const ObjectIdSet& expected_pending_ids,
122 double expected_delay_seconds,
123 const RegistrationManager::PendingRegistrationMap& pending_registrations) {
124 ObjectIdSet pending_ids;
125 for (RegistrationManager::PendingRegistrationMap::const_iterator it =
126 pending_registrations.begin(); it != pending_registrations.end();
127 ++it) {
128 SCOPED_TRACE(ObjectIdToString(it->first));
129 pending_ids.insert(it->first);
130 base::TimeDelta offset =
131 it->second.last_registration_request -
132 it->second.registration_attempt;
133 base::TimeDelta expected_delay =
134 base::TimeDelta::FromSeconds(
135 static_cast<int64>(expected_delay_seconds)) + offset;
136 // TODO(akalin): Add base::PrintTo() for base::Time and
137 // base::TimeDeltas.
138 EXPECT_EQ(expected_delay, it->second.delay)
139 << expected_delay.InMicroseconds()
140 << ", " << it->second.delay.InMicroseconds();
141 if (it->second.delay <= base::TimeDelta()) {
142 EXPECT_EQ(base::TimeDelta(), it->second.actual_delay);
143 } else {
144 EXPECT_EQ(it->second.actual_delay, it->second.delay);
145 }
146 }
147 EXPECT_EQ(expected_pending_ids, pending_ids);
148 }
149
150 class RegistrationManagerTest : public testing::Test {
151 protected:
RegistrationManagerTest()152 RegistrationManagerTest()
153 : fake_registration_manager_(&fake_invalidation_client_) {}
154
~RegistrationManagerTest()155 virtual ~RegistrationManagerTest() {}
156
LoseRegistrations(const ObjectIdSet & oids)157 void LoseRegistrations(const ObjectIdSet& oids) {
158 for (ObjectIdSet::const_iterator it = oids.begin(); it != oids.end();
159 ++it) {
160 fake_invalidation_client_.LoseRegistration(*it);
161 fake_registration_manager_.MarkRegistrationLost(*it);
162 }
163 }
164
DisableIds(const ObjectIdSet & oids)165 void DisableIds(const ObjectIdSet& oids) {
166 for (ObjectIdSet::const_iterator it = oids.begin(); it != oids.end();
167 ++it) {
168 fake_invalidation_client_.LoseRegistration(*it);
169 fake_registration_manager_.DisableId(*it);
170 }
171 }
172
173 // Used by MarkRegistrationLostBackoff* tests.
RunBackoffTest(double jitter)174 void RunBackoffTest(double jitter) {
175 fake_registration_manager_.SetJitter(jitter);
176 ObjectIdSet ids = GetSequenceOfIds(kObjectIdsCount);
177 fake_registration_manager_.UpdateRegisteredIds(ids);
178
179 // Lose some ids.
180 ObjectIdSet lost_ids = GetSequenceOfIds(2);
181 LoseRegistrations(lost_ids);
182 ExpectPendingRegistrations(
183 lost_ids, 0.0,
184 fake_registration_manager_.GetPendingRegistrationsForTest());
185
186 // Trigger another failure to start delaying.
187 fake_registration_manager_.FirePendingRegistrationsForTest();
188 LoseRegistrations(lost_ids);
189
190 double scaled_jitter =
191 jitter * RegistrationManager::kRegistrationDelayMaxJitter;
192
193 double expected_delay =
194 RegistrationManager::kInitialRegistrationDelaySeconds *
195 (1.0 + scaled_jitter);
196 expected_delay = std::floor(expected_delay);
197 ExpectPendingRegistrations(
198 lost_ids, expected_delay,
199 fake_registration_manager_.GetPendingRegistrationsForTest());
200
201 // Trigger another failure.
202 fake_registration_manager_.FirePendingRegistrationsForTest();
203 LoseRegistrations(lost_ids);
204 expected_delay *=
205 RegistrationManager::kRegistrationDelayExponent + scaled_jitter;
206 expected_delay = std::floor(expected_delay);
207 ExpectPendingRegistrations(
208 lost_ids, expected_delay,
209 fake_registration_manager_.GetPendingRegistrationsForTest());
210
211 // Trigger enough failures to hit the ceiling.
212 while (expected_delay < RegistrationManager::kMaxRegistrationDelaySeconds) {
213 fake_registration_manager_.FirePendingRegistrationsForTest();
214 LoseRegistrations(lost_ids);
215 expected_delay *=
216 RegistrationManager::kRegistrationDelayExponent + scaled_jitter;
217 expected_delay = std::floor(expected_delay);
218 }
219 ExpectPendingRegistrations(
220 lost_ids,
221 RegistrationManager::kMaxRegistrationDelaySeconds,
222 fake_registration_manager_.GetPendingRegistrationsForTest());
223 }
224
225 FakeInvalidationClient fake_invalidation_client_;
226 FakeRegistrationManager fake_registration_manager_;
227
228 private:
229 // Needed by timers in RegistrationManager.
230 base::MessageLoop message_loop_;
231
232 DISALLOW_COPY_AND_ASSIGN(RegistrationManagerTest);
233 };
234
235 // Basic test of UpdateRegisteredIds to make sure we properly register
236 // new IDs and unregister any IDs no longer in the set.
TEST_F(RegistrationManagerTest,UpdateRegisteredIds)237 TEST_F(RegistrationManagerTest, UpdateRegisteredIds) {
238 ObjectIdSet ids = GetSequenceOfIds(kObjectIdsCount - 1);
239
240 EXPECT_TRUE(fake_registration_manager_.GetRegisteredIdsForTest().empty());
241 EXPECT_TRUE(fake_invalidation_client_.GetRegisteredIdsForTest().empty());
242
243 ObjectIdSet expected_unregistered_ids;
244
245 ObjectIdSet unregistered_ids =
246 fake_registration_manager_.UpdateRegisteredIds(ids);
247 EXPECT_EQ(expected_unregistered_ids, unregistered_ids);
248 EXPECT_EQ(ids, fake_registration_manager_.GetRegisteredIdsForTest());
249 EXPECT_EQ(ids, fake_invalidation_client_.GetRegisteredIdsForTest());
250
251 ids.insert(GetIdForIndex(kObjectIdsCount - 1));
252 ids.erase(GetIdForIndex(kObjectIdsCount - 2));
253 unregistered_ids = fake_registration_manager_.UpdateRegisteredIds(ids);
254 expected_unregistered_ids.insert(GetIdForIndex(kObjectIdsCount - 2));
255 EXPECT_EQ(expected_unregistered_ids, unregistered_ids);
256 EXPECT_EQ(ids, fake_registration_manager_.GetRegisteredIdsForTest());
257 EXPECT_EQ(ids, fake_invalidation_client_.GetRegisteredIdsForTest());
258 }
259
GetRoundedBackoff(double retry_interval,double jitter)260 int GetRoundedBackoff(double retry_interval, double jitter) {
261 const double kInitialRetryInterval = 3.0;
262 const double kMinRetryInterval = 2.0;
263 const double kMaxRetryInterval = 20.0;
264 const double kBackoffExponent = 2.0;
265 const double kMaxJitter = 0.5;
266
267 return static_cast<int>(
268 RegistrationManager::CalculateBackoff(retry_interval,
269 kInitialRetryInterval,
270 kMinRetryInterval,
271 kMaxRetryInterval,
272 kBackoffExponent,
273 jitter,
274 kMaxJitter));
275 }
276
TEST_F(RegistrationManagerTest,CalculateBackoff)277 TEST_F(RegistrationManagerTest, CalculateBackoff) {
278 // Test initial.
279 EXPECT_EQ(2, GetRoundedBackoff(0.0, -1.0));
280 EXPECT_EQ(3, GetRoundedBackoff(0.0, 0.0));
281 EXPECT_EQ(4, GetRoundedBackoff(0.0, +1.0));
282
283 // Test non-initial.
284 EXPECT_EQ(4, GetRoundedBackoff(3.0, -1.0));
285 EXPECT_EQ(6, GetRoundedBackoff(3.0, 0.0));
286 EXPECT_EQ(7, GetRoundedBackoff(3.0, +1.0));
287
288 EXPECT_EQ(7, GetRoundedBackoff(5.0, -1.0));
289 EXPECT_EQ(10, GetRoundedBackoff(5.0, 0.0));
290 EXPECT_EQ(12, GetRoundedBackoff(5.0, +1.0));
291
292 // Test ceiling.
293 EXPECT_EQ(19, GetRoundedBackoff(13.0, -1.0));
294 EXPECT_EQ(20, GetRoundedBackoff(13.0, 0.0));
295 EXPECT_EQ(20, GetRoundedBackoff(13.0, +1.0));
296 }
297
298 // Losing a registration should queue automatic re-registration.
TEST_F(RegistrationManagerTest,MarkRegistrationLost)299 TEST_F(RegistrationManagerTest, MarkRegistrationLost) {
300 ObjectIdSet ids = GetSequenceOfIds(kObjectIdsCount);
301
302 fake_registration_manager_.UpdateRegisteredIds(ids);
303 EXPECT_TRUE(
304 fake_registration_manager_.GetPendingRegistrationsForTest().empty());
305
306 // Lose some ids.
307 ObjectIdSet lost_ids = GetSequenceOfIds(3);
308 ObjectIdSet non_lost_ids = GetSequenceOfIdsStartingAt(3, kObjectIdsCount - 3);
309 LoseRegistrations(lost_ids);
310 ExpectPendingRegistrations(
311 lost_ids, 0.0,
312 fake_registration_manager_.GetPendingRegistrationsForTest());
313 EXPECT_EQ(non_lost_ids, fake_registration_manager_.GetRegisteredIdsForTest());
314 EXPECT_EQ(non_lost_ids, fake_invalidation_client_.GetRegisteredIdsForTest());
315
316 // Pretend we waited long enough to re-register.
317 fake_registration_manager_.FirePendingRegistrationsForTest();
318 EXPECT_EQ(ids, fake_registration_manager_.GetRegisteredIdsForTest());
319 EXPECT_EQ(ids, fake_invalidation_client_.GetRegisteredIdsForTest());
320 }
321
TEST_F(RegistrationManagerTest,MarkRegistrationLostBackoffLow)322 TEST_F(RegistrationManagerTest, MarkRegistrationLostBackoffLow) {
323 RunBackoffTest(-1.0);
324 }
325
TEST_F(RegistrationManagerTest,MarkRegistrationLostBackoffMid)326 TEST_F(RegistrationManagerTest, MarkRegistrationLostBackoffMid) {
327 RunBackoffTest(0.0);
328 }
329
TEST_F(RegistrationManagerTest,MarkRegistrationLostBackoffHigh)330 TEST_F(RegistrationManagerTest, MarkRegistrationLostBackoffHigh) {
331 RunBackoffTest(+1.0);
332 }
333
334 // Exponential backoff on lost registrations should be reset to zero if
335 // UpdateRegisteredIds is called.
TEST_F(RegistrationManagerTest,MarkRegistrationLostBackoffReset)336 TEST_F(RegistrationManagerTest, MarkRegistrationLostBackoffReset) {
337 ObjectIdSet ids = GetSequenceOfIds(kObjectIdsCount);
338
339 fake_registration_manager_.UpdateRegisteredIds(ids);
340
341 // Lose some ids.
342 ObjectIdSet lost_ids = GetSequenceOfIds(2);
343 LoseRegistrations(lost_ids);
344 ExpectPendingRegistrations(
345 lost_ids, 0.0,
346 fake_registration_manager_.GetPendingRegistrationsForTest());
347
348 // Trigger another failure to start delaying.
349 fake_registration_manager_.FirePendingRegistrationsForTest();
350 LoseRegistrations(lost_ids);
351 double expected_delay =
352 RegistrationManager::kInitialRegistrationDelaySeconds;
353 ExpectPendingRegistrations(
354 lost_ids, expected_delay,
355 fake_registration_manager_.GetPendingRegistrationsForTest());
356
357 // Set ids again.
358 fake_registration_manager_.UpdateRegisteredIds(ids);
359 ExpectPendingRegistrations(
360 ObjectIdSet(),
361 0.0,
362 fake_registration_manager_.GetPendingRegistrationsForTest());
363 }
364
TEST_F(RegistrationManagerTest,MarkAllRegistrationsLost)365 TEST_F(RegistrationManagerTest, MarkAllRegistrationsLost) {
366 ObjectIdSet ids = GetSequenceOfIds(kObjectIdsCount);
367
368 fake_registration_manager_.UpdateRegisteredIds(ids);
369
370 fake_invalidation_client_.LoseAllRegistrations();
371 fake_registration_manager_.MarkAllRegistrationsLost();
372
373 EXPECT_TRUE(fake_registration_manager_.GetRegisteredIdsForTest().empty());
374 EXPECT_TRUE(fake_invalidation_client_.GetRegisteredIdsForTest().empty());
375
376 ExpectPendingRegistrations(
377 ids, 0.0,
378 fake_registration_manager_.GetPendingRegistrationsForTest());
379
380 // Trigger another failure to start delaying.
381 fake_registration_manager_.FirePendingRegistrationsForTest();
382 fake_invalidation_client_.LoseAllRegistrations();
383 fake_registration_manager_.MarkAllRegistrationsLost();
384 double expected_delay =
385 RegistrationManager::kInitialRegistrationDelaySeconds;
386 ExpectPendingRegistrations(
387 ids, expected_delay,
388 fake_registration_manager_.GetPendingRegistrationsForTest());
389
390 // Pretend we waited long enough to re-register.
391 fake_registration_manager_.FirePendingRegistrationsForTest();
392 EXPECT_EQ(ids, fake_registration_manager_.GetRegisteredIdsForTest());
393 EXPECT_EQ(ids, fake_invalidation_client_.GetRegisteredIdsForTest());
394 }
395
396 // IDs that are disabled should not be re-registered by UpdateRegisteredIds or
397 // automatic re-registration if that registration is lost.
TEST_F(RegistrationManagerTest,DisableId)398 TEST_F(RegistrationManagerTest, DisableId) {
399 ObjectIdSet ids = GetSequenceOfIds(kObjectIdsCount);
400
401 fake_registration_manager_.UpdateRegisteredIds(ids);
402 EXPECT_TRUE(
403 fake_registration_manager_.GetPendingRegistrationsForTest().empty());
404
405 // Disable some ids.
406 ObjectIdSet disabled_ids = GetSequenceOfIds(3);
407 ObjectIdSet enabled_ids = GetSequenceOfIdsStartingAt(3, kObjectIdsCount - 3);
408 DisableIds(disabled_ids);
409 ExpectPendingRegistrations(
410 ObjectIdSet(),
411 0.0,
412 fake_registration_manager_.GetPendingRegistrationsForTest());
413 EXPECT_EQ(enabled_ids, fake_registration_manager_.GetRegisteredIdsForTest());
414 EXPECT_EQ(enabled_ids, fake_invalidation_client_.GetRegisteredIdsForTest());
415
416 fake_registration_manager_.UpdateRegisteredIds(ids);
417 EXPECT_EQ(enabled_ids, fake_registration_manager_.GetRegisteredIdsForTest());
418
419 fake_registration_manager_.MarkRegistrationLost(
420 *disabled_ids.begin());
421 ExpectPendingRegistrations(
422 ObjectIdSet(),
423 0.0,
424 fake_registration_manager_.GetPendingRegistrationsForTest());
425
426 fake_registration_manager_.MarkAllRegistrationsLost();
427 ExpectPendingRegistrations(
428 enabled_ids, 0.0,
429 fake_registration_manager_.GetPendingRegistrationsForTest());
430 }
431
432 } // namespace
433 } // namespace syncer
434