Tracked objects: Bump cumulative byte count storage to 64 bits to avoid saturation

base/tracked_objects.cc

 // Copyright (c) 2012 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 "base/tracked_objects.h"
 
 #include <ctype.h>
 #include <limits.h>
 #include <stdlib.h>
 
+#include <limits>
+
 #include "base/atomicops.h"
 #include "base/base_switches.h"
 #include "base/command_line.h"
 #include "base/compiler_specific.h"
 #include "base/debug/leak_annotations.h"
 #include "base/logging.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/numerics/safe_conversions.h"
 #include "base/numerics/safe_math.h"
 #include "base/process/process_handle.h"
 #include "base/third_party/valgrind/memcheck.h"
+#include "base/threading/platform_thread.h"
 #include "base/threading/worker_pool.h"
 #include "base/tracking_info.h"
 #include "build/build_config.h"
 
 using base::TimeDelta;
 
 namespace base {
 class TimeDelta;
 }
 
@@ skipping 71 matching lines @@
 
 DeathData::DeathData()
     : count_(0),
       sample_probability_count_(0),
       run_duration_sum_(0),
       queue_duration_sum_(0),
       run_duration_max_(0),
       queue_duration_max_(0),
       alloc_ops_(0),
       free_ops_(0),
-      allocated_bytes_(0),
-      freed_bytes_(0),
-      alloc_overhead_bytes_(0),
+#if !defined(ARCH_CPU_64_BITS)
+      byte_update_counter_(0),
+#endif
+      allocated_bytes_(),
+      freed_bytes_(),
+      alloc_overhead_bytes_(),
       max_allocated_bytes_(0),
       run_duration_sample_(0),
       queue_duration_sample_(0),
-      last_phase_snapshot_(nullptr) {}
+      last_phase_snapshot_(nullptr) {
+}
 
 DeathData::DeathData(const DeathData& other)
     : count_(other.count_),
       sample_probability_count_(other.sample_probability_count_),
       run_duration_sum_(other.run_duration_sum_),
       queue_duration_sum_(other.queue_duration_sum_),
       run_duration_max_(other.run_duration_max_),
       queue_duration_max_(other.queue_duration_max_),
       alloc_ops_(other.alloc_ops_),
       free_ops_(other.free_ops_),
+#if !defined(ARCH_CPU_64_BITS)
+      byte_update_counter_(0),
+#endif
       allocated_bytes_(other.allocated_bytes_),
       freed_bytes_(other.freed_bytes_),
       alloc_overhead_bytes_(other.alloc_overhead_bytes_),
       max_allocated_bytes_(other.max_allocated_bytes_),
       run_duration_sample_(other.run_duration_sample_),
       queue_duration_sample_(other.queue_duration_sample_),
       last_phase_snapshot_(nullptr) {
   // This constructor will be used by std::map when adding new DeathData values
   // to the map.  At that point, last_phase_snapshot_ is still NULL, so we don't
   // need to worry about ownership transfer.
@@ skipping 56 matching lines @@
     base::subtle::NoBarrier_Store(&run_duration_sample_, run_duration);
   }
 }
 
 void DeathData::RecordAllocations(const uint32_t alloc_ops,
                                   const uint32_t free_ops,
                                   const uint32_t allocated_bytes,
                                   const uint32_t freed_bytes,
                                   const uint32_t alloc_overhead_bytes,
                                   const uint32_t max_allocated_bytes) {
+#if !defined(ARCH_CPU_64_BITS)
+  // On 32 bit systems, we use an even/odd locking scheme to make possible to
+  // read 64 bit sums consistently. Note that since writes are bound to the
+  // thread owning this DeathData, there's no race on these writes.
+  int32_t counter_val =
+      base::subtle::Barrier_AtomicIncrement(&byte_update_counter_, 1);
+  // The counter must be odd.
+  DCHECK_EQ(1, counter_val & 1);
+#endif
+
   // Use saturating arithmetic.
   SaturatingMemberAdd(alloc_ops, &alloc_ops_);
   SaturatingMemberAdd(free_ops, &free_ops_);
-  SaturatingMemberAdd(allocated_bytes, &allocated_bytes_);
-  SaturatingMemberAdd(freed_bytes, &freed_bytes_);
-  SaturatingMemberAdd(alloc_overhead_bytes, &alloc_overhead_bytes_);
+  SaturatingByteCountMemberAdd(allocated_bytes, &allocated_bytes_);
+  SaturatingByteCountMemberAdd(freed_bytes, &freed_bytes_);
+  SaturatingByteCountMemberAdd(alloc_overhead_bytes, &alloc_overhead_bytes_);
 
   int32_t max = base::saturated_cast<int32_t>(max_allocated_bytes);
   if (max > max_allocated_bytes_)
     base::subtle::NoBarrier_Store(&max_allocated_bytes_, max);
+
+#if !defined(ARCH_CPU_64_BITS)
+  // Now release the value while rolling to even.
+  counter_val = base::subtle::Barrier_AtomicIncrement(&byte_update_counter_, 1);
+  DCHECK_EQ(0, counter_val & 1);
+#endif
 }
 
 void DeathData::OnProfilingPhaseCompleted(int profiling_phase) {
   // Snapshotting and storing current state.
   last_phase_snapshot_ =
       new DeathDataPhaseSnapshot(profiling_phase, *this, last_phase_snapshot_);
 
   // Not touching fields for which a delta can be computed by comparing with a
   // snapshot from the previous phase. Resetting other fields.  Sample values
   // will be reset upon next death recording because sample_probability_count_
@@ skipping 17 matching lines @@
   // The damage is limited to selecting a wrong sample, which is not something
   // that can cause accumulating or cascading effects.
   // If there were no inconsistencies caused by race conditions, we never send a
   // sample for the previous phase in the next phase's snapshot because
   // ThreadData::SnapshotExecutedTasks doesn't send deltas with 0 count.
   base::subtle::NoBarrier_Store(&sample_probability_count_, 0);
   base::subtle::NoBarrier_Store(&run_duration_max_, 0);
   base::subtle::NoBarrier_Store(&queue_duration_max_, 0);
 }
 
+int64_t DeathData::CumulativeByteCountRead(const CumulativeByteCount* count) {
+#if defined(ARCH_CPU_64_BITS)
+  return *count;
+#else
+  return static_cast<int64_t>(count->hi_word) << 32 |
+         static_cast<uint32_t>(count->lo_word);
+#endif
+}
+
+int64_t DeathData::ConsistentCumulativeByteCountRead(
+    const CumulativeByteCount* count) const {
+#if defined(ARCH_CPU_64_BITS)
+  return base::subtle::NoBarrier_Load(count);
+#else
+  // We're on a 32 bit system, this is going to be complicated.
+  while (true) {
+    int32_t update_counter = 0;
+    // Acquire the starting count, spin until it's even.
+
+    // The value of |kYieldProcessorTries| is cargo culted from the page
+    // allocator, TCMalloc, Window critical section defaults, and various other
+    // recommendations.
+    // This is not performance critical here, as the reads are vanishingly rare
+    // and only happen under the --enable-heap-profiling=task-profiler flag.
+    constexpr size_t kYieldProcessorTries = 10000;

[gab, 2017/05/03 17:25:37]

spin_lock.cc uses 1000 not 10000

spin_lock.cc also uses YieldProcessor() to inform the processor that this code
is in a busy loop (e.g. yielding resources to other threads without giving up
this thread's quantum on hyperthreaded CPUs)

Short of bringing YieldProcessor() here, I'm not sure what's worse... spinning
to 1000 and yielding thread less often or yielding thread every cycle but first?

FWIW, one_writer_seqlock.cc does the latter.

[Sigurður Ásgeirsson, 2017/05/03 17:44:04]

Ugh, typo alert!

Lemme try it this way - like you say, I'll be the first to feel the pain :).

+    size_t lock_attempts = 0;
+    do {
+      ++lock_attempts;
+      if (lock_attempts == kYieldProcessorTries) {
+        // Yield the current thread periodically to avoid writer starvation.
+        base::PlatformThread::YieldCurrentThread();
+        lock_attempts = 0;
+      }
+
+      update_counter = base::subtle::Acquire_Load(&byte_update_counter_);

[gab, 2017/05/03 17:25:37]

optional:

After reading http://preshing.com/20130922/acquire-and-release-fences/ (in
particular example around std::atomic_thread_fence(std::memory_order_acquire))

I think you could avoid the Acquire here if you add a
base::subtle::MemoryBarrier() right after exiting the loop.

That barrier would guarantee that you see everything that was written prior to
the value of |byte_update_counter_| you just saw (i.e. same property as
Acquire_Load().

base::subtle::MemoryBarrier() is a full-on barrier whereas you just need acquire
semantics, but maybe a full barrier outside the loop is better than an acquire
barrier inside the loop..?

[Sigurður Ásgeirsson, 2017/05/03 17:44:04]

Done.

+    } while (update_counter & 1);
+
+    DCHECK_EQ(update_counter & 1, 0);
+
+    int64_t value =
+        static_cast<int64_t>(base::subtle::NoBarrier_Load(&count->hi_word))
+            << 32 |
+        static_cast<uint32_t>(base::subtle::NoBarrier_Load(&count->lo_word));
+
+    // If the count has not changed, the read is consistent.
+    // Otherwise go around and try again.
+    if (update_counter == base::subtle::Acquire_Load(&byte_update_counter_))

[gab, 2017/05/03 17:25:37]

Acquire semantics at the end of the method do nothing (they only guarantee that
reads coming after are consistent which is irrelevant). 

I think you want Release_Load() -- which is implemented as MemoryBarrier() +
NoBarrier_Load() @
https://cs.chromium.org/chromium/src/base/atomicops_internals_portable.h?rcl=...
so that would make sense as it would fence the above reads.

Looking in the codebase for existing usage of Release_Load() I found
one_writer_seqlock.h which seems very similar to what you're trying to do.

[Sigurður Ásgeirsson, 2017/05/03 17:44:04]

Ah, cool, that makes sense.

+      return value;
+  }
+#endif
+}
+
 void DeathData::SaturatingMemberAdd(const uint32_t addend,
                                     base::subtle::Atomic32* sum) {
+  constexpr int32_t kInt32Max = std::numeric_limits<int32_t>::max();
   // Bail quick if no work or already saturated.
-  if (addend == 0U || *sum == INT_MAX)
+  if (addend == 0U || *sum == kInt32Max)
     return;
 
   base::CheckedNumeric<int32_t> new_sum = *sum;
   new_sum += addend;
-  base::subtle::NoBarrier_Store(sum, new_sum.ValueOrDefault(INT_MAX));
+  base::subtle::NoBarrier_Store(sum, new_sum.ValueOrDefault(kInt32Max));
+}
+
+void DeathData::SaturatingByteCountMemberAdd(const uint32_t addend,
+                                             CumulativeByteCount* sum) {
+  constexpr int64_t kInt64Max = std::numeric_limits<int64_t>::max();
+  // Bail quick if no work or already saturated.
+  if (addend == 0U || CumulativeByteCountRead(sum) == kInt64Max)
+    return;
+
+  base::CheckedNumeric<int64_t> new_sum = CumulativeByteCountRead(sum);
+  new_sum += addend;
+  int64_t new_value = new_sum.ValueOrDefault(kInt64Max);
+// Update our value.
+#if defined(ARCH_CPU_64_BITS)
+  base::subtle::NoBarrier_Store(sum, new_value);
+#else
+  base::subtle::NoBarrier_Store(&sum->hi_word,
+                                static_cast<int32_t>(new_value >> 32));
+  base::subtle::NoBarrier_Store(&sum->lo_word,
+                                static_cast<int32_t>(new_value & 0xFFFFFFFF));
+#endif
 }
 
 //------------------------------------------------------------------------------
 DeathDataSnapshot::DeathDataSnapshot()
     : count(-1),
       run_duration_sum(-1),
       run_duration_max(-1),
       run_duration_sample(-1),
       queue_duration_sum(-1),
       queue_duration_max(-1),
       queue_duration_sample(-1),
       alloc_ops(-1),
       free_ops(-1),
       allocated_bytes(-1),
       freed_bytes(-1),
       alloc_overhead_bytes(-1),
       max_allocated_bytes(-1) {}
 
 DeathDataSnapshot::DeathDataSnapshot(int count,
                                      int32_t run_duration_sum,
                                      int32_t run_duration_max,
                                      int32_t run_duration_sample,
                                      int32_t queue_duration_sum,
                                      int32_t queue_duration_max,
                                      int32_t queue_duration_sample,
                                      int32_t alloc_ops,
                                      int32_t free_ops,
-                                     int32_t allocated_bytes,
-                                     int32_t freed_bytes,
-                                     int32_t alloc_overhead_bytes,
+                                     int64_t allocated_bytes,
+                                     int64_t freed_bytes,
+                                     int64_t alloc_overhead_bytes,
                                      int32_t max_allocated_bytes)
     : count(count),
       run_duration_sum(run_duration_sum),
       run_duration_max(run_duration_max),
       run_duration_sample(run_duration_sample),
       queue_duration_sum(queue_duration_sum),
       queue_duration_max(queue_duration_max),
       queue_duration_sample(queue_duration_sample),
       alloc_ops(alloc_ops),
       free_ops(free_ops),
@@ skipping 774 matching lines @@
 #endif
 }
 
 ProcessDataSnapshot::ProcessDataSnapshot(const ProcessDataSnapshot& other) =
     default;
 
 ProcessDataSnapshot::~ProcessDataSnapshot() {
 }
 
 }  // namespace tracked_objects