src/sync/notifier/ack_tracker.cc

   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/ack_tracker.h"
   6
   7 #include <algorithm>
   8 #include <iterator>
   9 #include <utility>
  10
  11 #include "base/callback.h"
  12 #include "base/stl_util.h"
  13 #include "base/time/tick_clock.h"
  14 #include "google/cacheinvalidation/include/types.h"
  15
  16 namespace syncer {
  17
  18 namespace {
  19
  20 // All times are in milliseconds.
  21 const net::BackoffEntry::Policy kDefaultBackoffPolicy = {
  22   // Number of initial errors (in sequence) to ignore before applying
  23   // exponential back-off rules.
  24   // Note this value is set to 1 to work in conjunction with a hack in
  25   // AckTracker::Track.
  26   1,
  27
  28   // Initial delay.  The interpretation of this value depends on
  29   // always_use_initial_delay.  It's either how long we wait between
  30   // requests before backoff starts, or how much we delay the first request
  31   // after backoff starts.
  32   60 * 1000,
  33
  34   // Factor by which the waiting time will be multiplied.
  35   2,
  36
  37   // Fuzzing percentage. ex: 10% will spread requests randomly
  38   // between 90%-100% of the calculated time.
  39   0,
  40
  41   // Maximum amount of time we are willing to delay our request, -1
  42   // for no maximum.
  43   60 * 10 * 1000,
  44
  45   // Time to keep an entry from being discarded even when it
  46   // has no significant state, -1 to never discard.
  47   -1,
  48
  49   // If true, we always use a delay of initial_delay_ms, even before
  50   // we've seen num_errors_to_ignore errors.  Otherwise, initial_delay_ms
  51   // is the first delay once we start exponential backoff.
  52   //
  53   // So if we're ignoring 1 error, we'll see (N, N, Nm, Nm^2, ...) if true,
  54   // and (0, 0, N, Nm, ...) when false, where N is initial_backoff_ms and
  55   // m is multiply_factor, assuming we've already seen one success.
  56   true,
  57 };
  58
  59 scoped_ptr<net::BackoffEntry> CreateDefaultBackoffEntry(
  60     const net::BackoffEntry::Policy* const policy) {
  61   return scoped_ptr<net::BackoffEntry>(new net::BackoffEntry(policy));
  62 }
  63
  64 }  // namespace
  65
  66 AckTracker::Delegate::~Delegate() {
  67 }
  68
  69 AckTracker::Entry::Entry(scoped_ptr<net::BackoffEntry> backoff,
  70                          const ObjectIdSet& ids)
  71     : backoff(backoff.Pass()), ids(ids) {
  72 }
  73
  74 AckTracker::Entry::~Entry() {
  75 }
  76
  77 AckTracker::AckTracker(base::TickClock* tick_clock, Delegate* delegate)
  78     : create_backoff_entry_callback_(base::Bind(&CreateDefaultBackoffEntry)),
  79       tick_clock_(tick_clock),
  80       delegate_(delegate) {
  81   DCHECK(tick_clock_);
  82   DCHECK(delegate_);
  83 }
  84
  85 AckTracker::~AckTracker() {
  86   DCHECK(thread_checker_.CalledOnValidThread());
  87
  88   Clear();
  89 }
  90
  91 void AckTracker::Clear() {
  92   DCHECK(thread_checker_.CalledOnValidThread());
  93
  94   timer_.Stop();
  95   STLDeleteValues(&queue_);
  96 }
  97
  98 void AckTracker::Track(const ObjectIdSet& ids) {
  99   DCHECK(thread_checker_.CalledOnValidThread());
 100   DCHECK(!ids.empty());
 101
 102   scoped_ptr<Entry> entry(new Entry(
 103       create_backoff_entry_callback_.Run(&kDefaultBackoffPolicy), ids));
 104   // This is a small hack. When net::BackoffRequest is first created,
 105   // GetReleaseTime() always returns the default base::TimeTicks value: 0.
 106   // In order to work around that, we mark it as failed right away.
 107   entry->backoff->InformOfRequest(false /* succeeded */);
 108   const base::TimeTicks release_time = entry->backoff->GetReleaseTime();
 109   queue_.insert(std::make_pair(release_time, entry.release()));
 110   NudgeTimer();
 111 }
 112
 113 void AckTracker::Ack(const ObjectIdSet& ids) {
 114   DCHECK(thread_checker_.CalledOnValidThread());
 115
 116   // We could be clever and maintain a mapping of object IDs to their position
 117   // in the multimap, but that makes things a lot more complicated.
 118   for (std::multimap<base::TimeTicks, Entry*>::iterator it = queue_.begin();
 119        it != queue_.end(); ) {
 120     ObjectIdSet remaining_ids;
 121     std::set_difference(it->second->ids.begin(), it->second->ids.end(),
 122                         ids.begin(), ids.end(),
 123                         std::inserter(remaining_ids, remaining_ids.begin()),
 124                         ids.value_comp());
 125     it->second->ids.swap(remaining_ids);
 126     if (it->second->ids.empty()) {
 127       std::multimap<base::TimeTicks, Entry*>::iterator erase_it = it;
 128       ++it;
 129       delete erase_it->second;
 130       queue_.erase(erase_it);
 131     } else {
 132       ++it;
 133     }
 134   }
 135   NudgeTimer();
 136 }
 137
 138 void AckTracker::NudgeTimer() {
 139   DCHECK(thread_checker_.CalledOnValidThread());
 140
 141   if (queue_.empty()) {
 142     return;
 143   }
 144
 145   const base::TimeTicks now = tick_clock_->NowTicks();
 146   // There are two cases when the timer needs to be started:
 147   // 1. |desired_run_time_| is in the past. By definition, the timer has already
 148   //    fired at this point. Since the queue is non-empty, we need to set the
 149   //    timer to fire again.
 150   // 2. The timer is already running but we need it to fire sooner if the first
 151   //    entry's timeout occurs before |desired_run_time_|.
 152   if (desired_run_time_ <= now || queue_.begin()->first < desired_run_time_) {
 153     base::TimeDelta delay = queue_.begin()->first - now;
 154     if (delay < base::TimeDelta()) {
 155       delay = base::TimeDelta();
 156     }
 157     timer_.Start(FROM_HERE, delay, this, &AckTracker::OnTimeout);
 158     desired_run_time_ = queue_.begin()->first;
 159   }
 160 }
 161
 162 void AckTracker::OnTimeout() {
 163   DCHECK(thread_checker_.CalledOnValidThread());
 164
 165   OnTimeoutAt(tick_clock_->NowTicks());
 166 }
 167
 168 void AckTracker::OnTimeoutAt(base::TimeTicks now) {
 169   DCHECK(thread_checker_.CalledOnValidThread());
 170
 171   if (queue_.empty())
 172     return;
 173
 174   ObjectIdSet expired_ids;
 175   std::multimap<base::TimeTicks, Entry*>::iterator end =
 176       queue_.upper_bound(now);
 177   std::vector<Entry*> expired_entries;
 178   for (std::multimap<base::TimeTicks, Entry*>::iterator it = queue_.begin();
 179        it != end; ++it) {
 180     expired_ids.insert(it->second->ids.begin(), it->second->ids.end());
 181     it->second->backoff->InformOfRequest(false /* succeeded */);
 182     expired_entries.push_back(it->second);
 183   }
 184   queue_.erase(queue_.begin(), end);
 185   for (std::vector<Entry*>::const_iterator it = expired_entries.begin();
 186        it != expired_entries.end(); ++it) {
 187     queue_.insert(std::make_pair((*it)->backoff->GetReleaseTime(), *it));
 188   }
 189   delegate_->OnTimeout(expired_ids);
 190   NudgeTimer();
 191 }
 192
 193 // Testing helpers.
 194 void AckTracker::SetCreateBackoffEntryCallbackForTest(
 195     const CreateBackoffEntryCallback& create_backoff_entry_callback) {
 196   DCHECK(thread_checker_.CalledOnValidThread());
 197
 198   create_backoff_entry_callback_ = create_backoff_entry_callback;
 199 }
 200
 201 bool AckTracker::TriggerTimeoutAtForTest(base::TimeTicks now) {
 202   DCHECK(thread_checker_.CalledOnValidThread());
 203
 204   bool no_timeouts_before_now = (queue_.lower_bound(now) == queue_.begin());
 205   OnTimeoutAt(now);
 206   return no_timeouts_before_now;
 207 }
 208
 209 bool AckTracker::IsQueueEmptyForTest() const {
 210   DCHECK(thread_checker_.CalledOnValidThread());
 211
 212   return queue_.empty();
 213 }
 214
 215 const base::Timer& AckTracker::GetTimerForTest() const {
 216   DCHECK(thread_checker_.CalledOnValidThread());
 217
 218   return timer_;
 219 }
 220
 221 }  // namespace syncer