Amortize data usage using TrafficStats on Android.

components/data_usage/android/traffic_stats_amortizer.cc

Index: components/data_usage/android/traffic_stats_amortizer.cc
diff --git a/components/data_usage/android/traffic_stats_amortizer.cc b/components/data_usage/android/traffic_stats_amortizer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..10982ae6cc47ce8f21afc18aa11d613b26495a6c
--- /dev/null
+++ b/components/data_usage/android/traffic_stats_amortizer.cc
@@ -0,0 +1,252 @@
+// Copyright 2015 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 "components/data_usage/android/traffic_stats_amortizer.h"
+
+#include <algorithm>  // For std::min.

[tbansal1, 2015/11/10 18:53:55]

Is algorithm not banned in Chromium?

[sclittle, 2015/11/11 02:10:07]

I don't think it's banned, lots of stuff uses it, e.g.
https://code.google.com/p/chromium/codesearch#search/&q=%22include%20%3Calgor...

+#include <cmath>      // For std::modf.
+
+#include "base/location.h"
+#include "base/time/default_tick_clock.h"
+#include "base/timer/timer.h"
+#include "components/data_usage/core/data_use.h"
+#include "net/android/traffic_stats.h"
+
+namespace data_usage {
+namespace android {
+
+namespace {
+
+// Convenience typedef.
+typedef std::vector<
+    std::pair<linked_ptr<DataUse>, DataUseAmortizer::DataUseConsumerCallback>>
+    DataUseBuffer;
+
+// The delay between receiving DataUse and querying TrafficStats byte counts for
+// amortization.
+// TODO(sclittle): Control this with a field trial parameter.
+const int64_t kDefaultTrafficStatsQueryDelayMs = 50;
+
+// The longest amount of time that an amortization run can be delayed for.
+// TODO(sclittle): Control this with a field trial parameter.
+const int64_t kDefaultMaxAmortizationDelayMs = 500;
+
+// The maximum allowed size of the DataUse buffer. If the buffer ever exceeds
+// this size, then DataUse will be amortized immediately and the buffer will be
+// flushed.
+// TODO(sclittle): Control this with a field trial parameter.
+const size_t kDefaultMaxDataUseBufferSize = 128;

[bengr, 2015/11/10 18:12:50]

So does this mean we will lose accuracy whenever there are more than 128 reads
in a half second?

[sclittle, 2015/11/11 02:10:07]

Yes, this is true. I doubt it will be a problem in practice though, especially
if we combine reads for the same request with the same callback.

+
+// Scales |bytes| by |ratio|, using |remainder| to hold the running rounding
+// error.
+int64_t ScaleByteCount(int64_t bytes, double ratio, double* remainder) {
+  double intpart;
+  *remainder =
+      std::modf(static_cast<double>(bytes) * ratio + (*remainder), &intpart);

[bengr, 2015/11/10 18:12:50]

Are there any assumptions about ratio? E.g., >= 1.0? What happens when bytes is
INT64_MAX? Or when bytes * ratio overflows double?

[sclittle, 2015/11/11 02:10:07]

Added DCHECKs and comments. |ratio| can be any double, so long as the final
scaled and truncated result is between [0, INT64_MAX].

It's impossible for those overflows to happen, since |ratio| is the quotient of
two other non-negative int64_t numbers, and even if |remainder| is non-zero in
this case, then |remainder| would still be truncated anyways.

+
+  DCHECK_GE(intpart, 0.0);
+  DCHECK_LE(intpart, static_cast<double>(INT64_MAX));
+  DCHECK_GE(*remainder, 0.0);
+  DCHECK_LT(*remainder, 1.0);
+  return static_cast<int64_t>(intpart);
+}
+
+// Amortize the difference between |desired_post_amortization_total_tx_bytes|
+// and |pre_amortization_total_tx_bytes| into each of the DataUse objects in
+// |data_use_sequence| by scaling the DataUse's |tx_bytes| appropriately. Does
+// the same with the |rx_bytes| using those respective parameters.
+void AmortizeDataUseSequence(DataUseBuffer* data_use_sequence,
+                             int64_t pre_amortization_total_tx_bytes,
+                             int64_t desired_post_amortization_total_tx_bytes,
+                             int64_t pre_amortization_total_rx_bytes,
+                             int64_t desired_post_amortization_total_rx_bytes) {
+  DCHECK(data_use_sequence);
+  DCHECK(!data_use_sequence->empty());
+
+  if (pre_amortization_total_tx_bytes != 0) {

[tbansal1, 2015/11/10 18:53:55]

if |pre_amortization_total_tx_bytes| is 0 but
|desired_post_amortization_total_tx_bytes| != 0, then I would simply distribute
|desired_post_amortization_total_tx_bytes| equally among all data_use objects.
WDYT?

Same for rx case.

[sclittle, 2015/11/11 02:10:07]

Added a TODO to handle this case gracefully.

I see what you mean, but I don't think it really makes sense to do that. Not all
DataUse objects are equal (there could be multiple tiny DataUse objects for the
same request, and one big DataUse for a different request), and how would we
distribute them among reported extra bytes (e.g. off-the-record)?

It seems easier in these cases to just give up on the TrafficStats values and
fall back to just using the byte counts from the net stack, since those are at
least a decent guess of the data usage.

+    const double ratio =
+        static_cast<double>(desired_post_amortization_total_tx_bytes) /
+        static_cast<double>(pre_amortization_total_tx_bytes);
+    double remainder = 0.0;
+    for (auto& data_use_buffer_pair : *data_use_sequence) {
+      data_use_buffer_pair.first->tx_bytes = ScaleByteCount(
+          data_use_buffer_pair.first->tx_bytes, ratio, &remainder);
+      // TODO(sclittle): Record UMA about values before vs. after amortization.
+    }
+  }
+
+  if (pre_amortization_total_rx_bytes != 0) {
+    const double ratio =
+        static_cast<double>(desired_post_amortization_total_rx_bytes) /
+        static_cast<double>(pre_amortization_total_rx_bytes);
+    double remainder = 0.0;
+    for (auto& data_use_buffer_pair : *data_use_sequence) {
+      data_use_buffer_pair.first->rx_bytes = ScaleByteCount(
+          data_use_buffer_pair.first->rx_bytes, ratio, &remainder);
+      // TODO(sclittle): Record UMA about values before vs. after amortization.
+    }
+  }
+}
+
+}  // namespace
+
+TrafficStatsAmortizer::TrafficStatsAmortizer()
+    : TrafficStatsAmortizer(
+          scoped_ptr<base::TickClock>(new base::DefaultTickClock()),
+          scoped_ptr<base::Timer>(new base::Timer(false, false)),
+          base::TimeDelta::FromMilliseconds(kDefaultTrafficStatsQueryDelayMs),
+          base::TimeDelta::FromMilliseconds(kDefaultMaxAmortizationDelayMs),
+          kDefaultMaxDataUseBufferSize) {}

[bengr, 2015/11/10 18:12:50]

Since there should only be one instance, would it make sense to set a static
bool?

[sclittle, 2015/11/11 02:10:07]

On second thought, that's not exactly true, I've reworded that comment on the
TrafficStatsAmortizer class. It's OK for multiple TrafficStatsAmortizers to
exist, so long as every amortizer is notified of every byte, e.g. the same
DataUse object or a corresponding number of extra bytes must be reported to all
the amortizers.

+
+TrafficStatsAmortizer::~TrafficStatsAmortizer() {}
+
+void TrafficStatsAmortizer::AmortizeDataUse(
+    scoped_ptr<DataUse> data_use,
+    const DataUseConsumerCallback& callback) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK(!callback.is_null());
+  int64_t tx_bytes = data_use->tx_bytes, rx_bytes = data_use->rx_bytes;
+
+  // TODO(sclittle): Combine consecutive buffered DataUse objects that are
+  // identical except for byte counts and have the same callback.
+  buffered_data_use_.push_back(
+      std::make_pair(linked_ptr<DataUse>(data_use.release()), callback));
+
+  AddPreAmortizationBytes(tx_bytes, rx_bytes);
+}
+
+void TrafficStatsAmortizer::OnExtraBytes(int64_t extra_tx_bytes,
+                                         int64_t extra_rx_bytes) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  AddPreAmortizationBytes(extra_tx_bytes, extra_rx_bytes);
+}
+
+base::WeakPtr<TrafficStatsAmortizer> TrafficStatsAmortizer::GetWeakPtr() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return weak_ptr_factory_.GetWeakPtr();
+}
+
+TrafficStatsAmortizer::TrafficStatsAmortizer(
+    scoped_ptr<base::TickClock> tick_clock,
+    scoped_ptr<base::Timer> traffic_stats_query_timer,
+    const base::TimeDelta& traffic_stats_query_delay,
+    const base::TimeDelta& max_amortization_delay,
+    size_t max_data_use_buffer_size)
+    : tick_clock_(tick_clock.Pass()),
+      traffic_stats_query_timer_(traffic_stats_query_timer.Pass()),
+      traffic_stats_query_delay_(traffic_stats_query_delay),
+      max_amortization_delay_(max_amortization_delay),
+      max_data_use_buffer_size_(max_data_use_buffer_size),
+      is_amortization_run_in_progress_(false),

[tbansal1, 2015/11/10 18:53:55]

Is it possible to get rid of is_amortization_run_in_progress_?
Seems like is_amortization_run_in_progress_ is false iff
current_amortization_run_start_time_ is null?

[sclittle, 2015/11/11 02:10:07]

The null TimeTicks (i.e. base::TimeTicks()) is actually a valid time that could
come up for real, so I don't want to have special casing for that.

+      are_last_amortization_traffic_stats_available_(false),
+      last_amortization_traffic_stats_tx_bytes_(-1),
+      last_amortization_traffic_stats_rx_bytes_(-1),
+      pre_amortization_tx_bytes_(0),
+      pre_amortization_rx_bytes_(0),
+      weak_ptr_factory_(this) {}
+
+bool TrafficStatsAmortizer::QueryTrafficStats(int64_t* tx_bytes,
+                                              int64_t* rx_bytes) const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return net::android::traffic_stats::GetCurrentUidTxBytes(tx_bytes) &&
+         net::android::traffic_stats::GetCurrentUidRxBytes(rx_bytes);
+}
+
+void TrafficStatsAmortizer::AddPreAmortizationBytes(int64_t tx_bytes,
+                                                    int64_t rx_bytes) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK_GE(tx_bytes, 0);
+  DCHECK_GE(rx_bytes, 0);
+  base::TimeTicks now_ticks = tick_clock_->NowTicks();
+
+  if (!is_amortization_run_in_progress_) {

[bengr, 2015/11/10 18:12:50]

I'd just call this is_amortization_in_progress_.

[sclittle, 2015/11/11 02:10:07]

Done.

+    is_amortization_run_in_progress_ = true;
+    current_amortization_run_start_time_ = now_ticks;
+  }
+
+  pre_amortization_tx_bytes_ += tx_bytes;
+  pre_amortization_rx_bytes_ += rx_bytes;
+
+  if (buffered_data_use_.size() > max_data_use_buffer_size_) {
+    // Enforce a maximum limit on the size of |buffered_data_use_| to avoid
+    // hogging memory. Note that this will likely cause the post-amortization
+    // byte counts calculated here to be less accurate than if the amortizer
+    // waited to perform amortization.
+    traffic_stats_query_timer_->Stop();

[bengr, 2015/11/10 18:12:50]

Add UMA (or a TODO for UMA).

[sclittle, 2015/11/11 02:10:07]

Done.

+    AmortizeNow();
+    return;
+  }
+
+  // Cap any amortization delay to |max_amortization_delay_|. Note that if
+  // |max_amortization_delay_| comes earlier, then this will likely cause the
+  // post-amortization byte counts calculated here to be less accurate than if
+  // the amortizer waited to perform amortization.
+  base::TimeDelta query_delay = std::min(
+      traffic_stats_query_delay_, current_amortization_run_start_time_ +
+                                      max_amortization_delay_ - now_ticks);
+
+  // Set the timer to query TrafficStats and amortize after a delay. If the
+  // timer was already set, then this overrides the previous delay.

[bengr, 2015/11/10 18:12:50]

So the point of this is that we will hopefully amortize when the network is
idle?

[sclittle, 2015/11/11 02:10:07]

Yes, added comment.

+  traffic_stats_query_timer_->Start(

[tbansal1, 2015/11/10 18:53:55]

does this post immediately if the delay is negative?

[sclittle, 2015/11/11 02:10:07]

Yes, see
https://code.google.com/p/chromium/codesearch#chromium/src/base/timer/timer.c...

+      FROM_HERE, query_delay,
+      base::Bind(&TrafficStatsAmortizer::AmortizeNow, GetWeakPtr()));
+}
+
+void TrafficStatsAmortizer::AmortizeNow() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  int64_t current_traffic_stats_tx_bytes = -1;

[bengr, 2015/11/10 18:12:50]

What's the significance of -1?

[sclittle, 2015/11/11 02:10:07]

It's just for debug purposes. If something goes wrong somehow, then it's easier
to recognize a -1 here then some arbitrary uninitialized memory value.

[bengr, 2015/11/11 15:41:37]

Please add a comment.

+  int64_t current_traffic_stats_rx_bytes = -1;
+  bool are_current_traffic_stats_available = QueryTrafficStats(
+      &current_traffic_stats_tx_bytes, &current_traffic_stats_rx_bytes);
+
+  if (are_current_traffic_stats_available &&
+      are_last_amortization_traffic_stats_available_ &&
+      !buffered_data_use_.empty()) {
+    // These TrafficStats byte counts are guaranteed to increase monotonically
+    // since device boot.
+    DCHECK_GE(current_traffic_stats_tx_bytes,
+              last_amortization_traffic_stats_tx_bytes_);
+    DCHECK_GE(current_traffic_stats_rx_bytes,
+              last_amortization_traffic_stats_rx_bytes_);
+
+    int64_t desired_post_amortization_total_tx_bytes =
+        current_traffic_stats_tx_bytes -
+        last_amortization_traffic_stats_tx_bytes_;
+    int64_t desired_post_amortization_total_rx_bytes =
+        current_traffic_stats_rx_bytes -
+        last_amortization_traffic_stats_rx_bytes_;
+
+    AmortizeDataUseSequence(&buffered_data_use_, pre_amortization_tx_bytes_,
+                            desired_post_amortization_total_tx_bytes,
+                            pre_amortization_rx_bytes_,
+                            desired_post_amortization_total_rx_bytes);
+  }
+
+  // TODO(sclittle): Record some UMA about the delay before amortizing and how
+  // big the buffer was before amortizing.
+
+  // Reset state now that the amortization run has finished.
+  is_amortization_run_in_progress_ = false;
+  current_amortization_run_start_time_ = base::TimeTicks();
+
+  are_last_amortization_traffic_stats_available_ =
+      are_current_traffic_stats_available;
+  last_amortization_traffic_stats_tx_bytes_ = current_traffic_stats_tx_bytes;
+  last_amortization_traffic_stats_rx_bytes_ = current_traffic_stats_rx_bytes;
+
+  pre_amortization_tx_bytes_ = 0;
+  pre_amortization_rx_bytes_ = 0;
+
+  // Pass post-amortization DataUse to their respective callbacks.

[bengr, 2015/11/10 18:12:50]

DataUse -> DataUse objects

[sclittle, 2015/11/11 02:10:07]

Done.

+  DataUseBuffer data_use_sequence;
+  data_use_sequence.swap(buffered_data_use_);
+  for (auto& data_use_buffer_pair : data_use_sequence) {
+    scoped_ptr<DataUse> data_use(data_use_buffer_pair.first.release());
+    data_use_buffer_pair.second.Run(data_use.Pass());
+  }
+}
+
+}  // namespace android
+}  // namespace data_usage