Support parallel captures from the StackSamplingProfiler.

base/profiler/stack_sampling_profiler.cc

Index: base/profiler/stack_sampling_profiler.cc
diff --git a/base/profiler/stack_sampling_profiler.cc b/base/profiler/stack_sampling_profiler.cc
index f294251cd32b6dff9d3b3b4bee1bbf8134e66ba7..7497c7639a45caf1c84a8f2019fdec3f4790a823 100644
--- a/base/profiler/stack_sampling_profiler.cc
+++ b/base/profiler/stack_sampling_profiler.cc
@@ -5,16 +5,22 @@
 #include "base/profiler/stack_sampling_profiler.h"
 
 #include <algorithm>
+#include <map>
 #include <utility>
 
+#include "base/atomic_sequence_num.h"
+#include "base/atomicops.h"
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/callback.h"
 #include "base/lazy_instance.h"
 #include "base/location.h"
 #include "base/macros.h"
+#include "base/memory/ptr_util.h"
+#include "base/memory/singleton.h"
 #include "base/profiler/native_stack_sampler.h"
 #include "base/synchronization/lock.h"
+#include "base/threading/thread.h"
 #include "base/threading/thread_task_runner_handle.h"
 #include "base/timer/elapsed_timer.h"
 
@@ -22,9 +28,6 @@ namespace base {
 
 namespace {
 
-// Used to ensure only one profiler is running at a time.
-LazyInstance<Lock>::Leaky concurrent_profiling_lock = LAZY_INSTANCE_INITIALIZER;
-
 // AsyncRunner ----------------------------------------------------------------
 
 // Helper class to allow a profiler to be run completely asynchronously from the
@@ -160,102 +163,468 @@ StackSamplingProfiler::CallStackProfile::CallStackProfile(
 
 // StackSamplingProfiler::SamplingThread --------------------------------------
 
-StackSamplingProfiler::SamplingThread::SamplingThread(
-    std::unique_ptr<NativeStackSampler> native_sampler,
-    const SamplingParams& params,
-    const CompletedCallback& completed_callback)
-    : native_sampler_(std::move(native_sampler)),
-      params_(params),
-      stop_event_(WaitableEvent::ResetPolicy::AUTOMATIC,
-                  WaitableEvent::InitialState::NOT_SIGNALED),
-      completed_callback_(completed_callback) {}
+class StackSamplingProfiler::SamplingThread : public Thread {
+ public:
+  struct CollectionContext {
+    CollectionContext(PlatformThreadId target,
+                      const SamplingParams& params,
+                      const CompletedCallback& callback,
+                      std::unique_ptr<NativeStackSampler> sampler)
+        : collection_id(next_collection_id_.GetNext()),
+          target(target),
+          params(params),
+          callback(callback),
+          native_sampler(std::move(sampler)) {}
+    ~CollectionContext() {}
+
+    // An identifier for this collection, used to uniquely identify it to
+    // outside interests.
+    const int collection_id;
+
+    Time next_sample_time;
+
+    PlatformThreadId target;
+    SamplingParams params;
+    CompletedCallback callback;
+
+    std::unique_ptr<NativeStackSampler> native_sampler;
+
+    // Counters that indicate the current position along the acquisition.
+    int burst = 0;
+    int sample = 0;
+
+    // The time that a profile was started, for calculating the total duration.
+    Time profile_start_time;
+
+    // The collected stack samples. The active profile is always at the back().
+    CallStackProfiles profiles;
+
+   private:
+    static StaticAtomicSequenceNumber next_collection_id_;
+  };
+
+  // Gets the single instance of this class.
+  static SamplingThread* GetInstance();
+
+  // Starts the thread.
+  void Start();
+
+  // Adds a new CollectionContext to the thread. This can be called externally
+  // from any thread. This returns an ID that can later be used to stop
+  // the sampling.
+  int Add(std::unique_ptr<CollectionContext> collection);
 
-StackSamplingProfiler::SamplingThread::~SamplingThread() {}
+  // Removes an active collection based on its ID, forcing it to run its
+  // callback if any data has been collected. This can be called externally
+  // from any thread.
+  void Remove(int id);
 
-void StackSamplingProfiler::SamplingThread::ThreadMain() {
-  PlatformThread::SetName("Chrome_SamplingProfilerThread");
+  // Removes all active collections and stops the underlying thread.
+  void Shutdown();
+
+  // Begins an idle shutdown as if the idle-timer had expired.
+  void ShutdownIfIdle();
+
+  // Undoes the "permanent" effect of Shutdown() so the thread can restart.
+  void UndoShutdown();
+
+  // Sets the number of ms to wait after becoming idle before shutting down.
+  // Set to zero to disable.
+  void SetIdleShutdownTime(int shutdown_ms);
+
+ private:
+  SamplingThread();
+  ~SamplingThread() override;
+  friend struct DefaultSingletonTraits<SamplingThread>;
+
+  // Get task runner that is usable from the outside.
+  scoped_refptr<SingleThreadTaskRunner> GetOrCreateTaskRunner();
+  scoped_refptr<SingleThreadTaskRunner> GetTaskRunner();
+
+  // Get task runner that is usable from the sampling thread itself.
+  scoped_refptr<SingleThreadTaskRunner> GetTaskRunnerOnSamplingThread();
+
+  // Finishes a collection and reports collected data via callback.
+  void FinishCollection(CollectionContext* collection);
+
+  // Records a single sample of a collection.
+  void RecordSample(CollectionContext* collection);
+
+  // Check if the sampling thread is idle.
+  void CheckForIdle();
+
+  // These methods are tasks that get posted to the internal message queue.
+  void AddCollectionTask(std::unique_ptr<CollectionContext> collection_ptr);
+  void RemoveCollectionTask(int id);
+  void PerformCollectionTask(int id);
+  void ShutdownTask();
+
+  // Updates the |next_sample_time| time based on configured parameters.
+  bool UpdateNextSampleTime(CollectionContext* collection);
+
+  // Thread:
+  void CleanUp() override;
+
+  // The task-runner for the sampling thread and some information about it.
+  // This must always be accessed while holding the lock. The saved task-runner
+  // can be freely used by any calling thread.
+  scoped_refptr<SingleThreadTaskRunner> task_runner_;
+  bool task_runner_forced_shutdown_ = false;
+  int task_runner_create_requests_ = 0;
+  TimeDelta task_runner_idle_shutdown_time_ = TimeDelta::FromSeconds(5);
+  Lock task_runner_lock_;
+
+  // A map of IDs to collection contexts. Because this class is a singleton
+  // that is never destroyed, context objects will never be destructed except
+  // by explicit action. Thus, it's acceptable to pass unretained pointers
+  // to these objects when posting tasks.
+  std::map<int, std::unique_ptr<CollectionContext>> active_collections_;
+
+  DISALLOW_COPY_AND_ASSIGN(SamplingThread);
+};
+
+StaticAtomicSequenceNumber StackSamplingProfiler::SamplingThread::
+    CollectionContext::next_collection_id_;
+
+StackSamplingProfiler::SamplingThread::SamplingThread()
+    : Thread("Chrome_SamplingProfilerThread") {}
+
+StackSamplingProfiler::SamplingThread::~SamplingThread() {
+  Thread::Stop();
+}
+
+StackSamplingProfiler::SamplingThread*
+StackSamplingProfiler::SamplingThread::GetInstance() {
+  return Singleton<SamplingThread, LeakySingletonTraits<SamplingThread>>::get();
+}
+
+void StackSamplingProfiler::SamplingThread::Start() {
+  Thread::Options options;
+  // Use a higher priority for a more accurate sampling interval.
+  options.priority = ThreadPriority::DISPLAY;
+  Thread::StartWithOptions(options);
+}
 
-  // For now, just ignore any requests to profile while another profiler is
-  // working.
-  if (!concurrent_profiling_lock.Get().Try())
+int StackSamplingProfiler::SamplingThread::Add(
+    std::unique_ptr<CollectionContext> collection) {
+  int id = collection->collection_id;
+  scoped_refptr<SingleThreadTaskRunner> task_runner = GetOrCreateTaskRunner();
+
+  // There may be no task-runner if the sampling thread has been permanently
+  // shut down.
+  if (task_runner) {
+    task_runner->PostTask(
+        FROM_HERE, Bind(&SamplingThread::AddCollectionTask, Unretained(this),
+                        Passed(&collection)));
+  }
+  return id;
+}
+
+void StackSamplingProfiler::SamplingThread::Remove(int id) {
+  scoped_refptr<SingleThreadTaskRunner> task_runner = GetTaskRunner();
+  if (!task_runner)
+    return;  // Everything has already stopped.
+
+  // This can fail if the thread were to exit between acquisition of the task
+  // runner above and the call below. In that case, however, everything has
+  // stopped so there's no need to try to stop it.
+  task_runner->PostTask(FROM_HERE, Bind(&SamplingThread::RemoveCollectionTask,
+                                        Unretained(this), id));
+}
+
+void StackSamplingProfiler::SamplingThread::Shutdown() {
+  // Record that a shutdown has been requested so nothing can cause it to
+  // start up again.
+  {
+    AutoLock lock(task_runner_lock_);
+    task_runner_forced_shutdown_ = true;
+  }
+
+  scoped_refptr<SingleThreadTaskRunner> task_runner = GetTaskRunner();
+  if (!task_runner)
+    return;  // Everything has already stopped.
+
+  // This can fail if the thread were to exit between acquisition of the task
+  // runner above and the call below. In that case, however, everything has
+  // stopped so there's no need to do anything.
+  task_runner->PostTask(FROM_HERE,
+                        Bind(&SamplingThread::ShutdownTask, Unretained(this)));
+
+  // Now that a task has been posted, calling Stop() will block until that task
+  // has been executed.
+  Stop();
+}
+
+void StackSamplingProfiler::SamplingThread::ShutdownIfIdle() {
+  scoped_refptr<SingleThreadTaskRunner> task_runner = GetTaskRunner();
+  if (!task_runner)
+    return;  // Everything has already stopped.
+
+  // ShutdownTask will check if the thread is idle and skip the shutdown if not.
+  task_runner->PostTask(FROM_HERE,
+                        Bind(&SamplingThread::ShutdownTask, Unretained(this)));
+}
+
+void StackSamplingProfiler::SamplingThread::UndoShutdown() {
+  {
+    AutoLock lock(task_runner_lock_);
+    task_runner_forced_shutdown_ = false;
+  }
+}
+
+void StackSamplingProfiler::SamplingThread::SetIdleShutdownTime(
+    int shutdown_ms) {
+  AutoLock lock(task_runner_lock_);
+  task_runner_idle_shutdown_time_ = TimeDelta::FromMilliseconds(shutdown_ms);
+}
+
+scoped_refptr<SingleThreadTaskRunner>
+StackSamplingProfiler::SamplingThread::GetOrCreateTaskRunner() {
+  AutoLock lock(task_runner_lock_);
+  ++task_runner_create_requests_;
+  if (!task_runner_) {
+    // If a forced shutdown has been done, don't let it restart.
+    if (task_runner_forced_shutdown_)
+      return nullptr;
+    // If this is not the first time the sampling thread has been launched, the
+    // previous instance has only been partially cleaned up. It is necessary
+    // to call Stop() before Start(). This is safe even the thread has never
+    // been started.
+    Stop();
+    // The thread is not running. Start it and get associated runner. The task-
+    // runner has to be saved for future use because though it can be used from
+    // any thread, it can be acquired via task_runner() only on the created
+    // thread and the thread that creates it (i.e. this thread).
+    Start();
+    task_runner_ = Thread::task_runner();
+    // Detach the sampling thread from the "sequence" (i.e. thread) that
+    // started it so that it can be self-managed or stopped on by another
+    // thread.
+    DetachFromSequence();
+  } else {
+    // This shouldn't be called from the sampling thread as it's inefficient.
+    // Use GetTaskRunnerOnSamplingThread() instead.
+    DCHECK_NE(GetThreadId(), PlatformThread::CurrentId());
+  }
+
+  return task_runner_;
+}
+
+scoped_refptr<SingleThreadTaskRunner>
+StackSamplingProfiler::SamplingThread::GetTaskRunner() {
+  // This shouldn't be called from the sampling thread as it's inefficient. Use
+  // GetTaskRunnerOnSamplingThread() instead.
+  DCHECK_NE(GetThreadId(), PlatformThread::CurrentId());
+
+  AutoLock lock(task_runner_lock_);
+  return task_runner_;
+}
+
+scoped_refptr<SingleThreadTaskRunner>
+StackSamplingProfiler::SamplingThread::GetTaskRunnerOnSamplingThread() {
+  // This should be called only from the sampling thread as it has limited
+  // accessibility.
+  DCHECK_EQ(GetThreadId(), PlatformThread::CurrentId());
+
+  return Thread::task_runner();
+}
+
+void StackSamplingProfiler::SamplingThread::FinishCollection(
+    CollectionContext* collection) {
+  // If there is no duration for the final profile (because it was stopped),
+  // calculated it now.
+  if (!collection->profiles.empty() &&
+      collection->profiles.back().profile_duration == TimeDelta()) {
+    collection->profiles.back().profile_duration =
+        Time::Now() - collection->profile_start_time;
+  }
+
+  // Run the associated callback, passing the collected profiles. It's okay to
+  // move them because this collection is about to be deleted.
+  collection->callback.Run(std::move(collection->profiles));
+
+  // Remove this collection from the map of known ones.  This must be done
+  // last as the |collection| parameter is invalid after this point.
+  size_t count = active_collections_.erase(collection->collection_id);
+  DCHECK_EQ(1U, count);
+}
+
+void StackSamplingProfiler::SamplingThread::RecordSample(
+    CollectionContext* collection) {
+  DCHECK(collection->native_sampler);
+
+  // If this is the first sample of a burst, a new Profile needs to be created
+  // and filled.
+  if (collection->sample == 0) {
+    collection->profiles.push_back(CallStackProfile());
+    CallStackProfile& profile = collection->profiles.back();
+    profile.sampling_period = collection->params.sampling_interval;
+    collection->profile_start_time = Time::Now();
+    collection->native_sampler->ProfileRecordingStarting(&profile.modules);
+  }
+
+  // The currently active profile being acptured.
+  CallStackProfile& profile = collection->profiles.back();
+
+  // Record a single sample.
+  profile.samples.push_back(Sample());
+  Sample& sample = profile.samples.back();
+  collection->native_sampler->RecordStackSample(&sample);
+
+  // An empty result indicates that the thread under test is gone.

[Mike Wittman, 2017/01/31 22:14:27]

I don't think relying on SuspendThread to error out on terminated threads is a
viable mechanism for handling thread exit. Thread ids are reused on Windows so
there's no guarantee that another thread won't have been started with the same
id. I suspect we'll need some kind of formal synchronization between the target
threads and the profiler thread to coordinate thread exit.

Also, independent of that, an empty result here could happen for many other
reasons -- the stack pointer pointing to a guard page for example.

[bcwhite, 2017/02/01 14:47:29]

While reuse of thread-ids is possible, I don't think it's a concern:

1) The thread has to exit and the ID reused relatively quickly.
2) The presence of a foreign stack-frame in the data would be obvious and easily
dismissed.
3) It's non-trivial (at best) to have an outside, independent watcher learn when
a thread exits.

I believe it's not worth addressing this until it proves to be a real problem.
Makes sense.  I'll make the native sampler record information from the last
sample attempt.

[Mike Wittman, 2017/02/01 17:59:53]

I think this is a serious concern, and requires a solution that we have
confidence in up front. Since the profiler effectively controls the execution of
the entire rest of Chrome, it's imperative that it be as bulletproof as
possible. Avoiding non-deterministic failure modes is absolutely essential
because the resulting failures will be difficult to notice and next to
impossible to investigate effectively.

100ms is a pretty huge window in system execution terms. If the profiled thread
exits, hundreds if not thousands of thread creations could occur before the next
attempted sample, any of which could reuse the id.

If a thread in another process claims the id, then it's not clear what will
happen. Worst case scenario would be that we succeed in suspending the thread,
only to crash while trying to copy the stack. That would likely deadlock some
random innocent process on the system, a nasty scenario that we should be
avoiding at all costs.

If a thread in Chrome claims the id, then the profiler will happily continue
profiling the other thread, silently generating wrong data. There would be no
way to reliably detect this scenario in the data processing.

I don't think we need an independent thread watcher, since we can rely on the
StackSamplingProfiler's destructor being called before thread exit.

Straw man proposal: put a WaitableEvent "profiling_stopped" in the
CollectionContext. Thread a "profiler_destroying" flag through to the
RemoveCollectionTask from the StackSamplingProfiler destructor. After posting
the RemoveCollectionTask in the target thread, wait on the profiling_stopped
event. When executing the RemoveCollectionTask in the profiler thread, signal
the profiling_stopped event if the profiler_destroying flag is present.

I believe this would ensure the target thread has not exited until the profiler
is finished with it.

[bcwhite, 2017/02/01 19:11:16]

I don't understand.  The StackSamplingProfiler lifetime is completely
independent of any thread it might be sampling.
I'm confused.  An independent thread can exit at any time, right?


How about this for a simpler technique:  When the native sampler is created, use
GetThreadTimes() to get lpCreationTime.  Before each sample, do the same.  If
the creation-time changes, it must be a different thread.  In addition, there is
an lpExitTime that would determine if the thread has exited (but not yet been
reaped).

[Mike Wittman, 2017/02/01 20:26:51]

That's true, the current interface allows an arbitrary thread id to be supplied
for profiling. We'd need restrict the profiler to working on the thread where
it's created to rely on this behavior.

This is probably a reasonable trade off to make though, considering the
anticipated use cases in the new thread scheduler world. I think the profiler
will be used either for self profiling, or for profiling directed by the thread
scheduler. In the former case the StackSamplingProfiler would be allocated on
the thread's stack. In the latter case, the thread scheduler will know when
threads exit and can coordinate with the profiler internals via some
to-be-defined mechanism.
Chrome threads can exit by quitting the message loop. I believe directly exiting
threads is not supported in Chrome because it doesn't run destructors or do
other necessary cleanup. In the case of threads managed by the thread scheduler,
the scheduler itself will be responsible for thread exit.
This would dramatically reduce the window of vulnerability, but I don't think it
could prevent this situation from occurring. GetThreadTimes() is an inherently
racy API; there will always be some window between the time that
GetThreadTimes() is invoked and the actions taken as a result, during which time
threads could be destroyed or created.

[bcwhite, 2017/02/01 20:37:59]

If the call were made while the thread was suspended, there wouldn't be any
race.

But to avoid being suspended any longer than necessary, the check could be done
after the acquisition.  On the incredibly slim chance that the thread died and
was replaced with an identical ID in those few ns, the worst that would happen
is that the last sample would get discarded unnecessarily.

[Mike Wittman, 2017/02/01 21:19:04]

There would still be a race between the time the thread id was provided to the
profiler and the first time the thread was suspended. (At least that one, there
may be others too.)

It's really difficult to be sure that all relevant thread interleaving scenarios
have been considered with an API like this. And even if they have, it will be
significantly difficult for other developers to validate the correctness of the
resulting code. If and when some future developer makes changes here, there's a
small chance they will understand the subtleties sufficiently to avoid
introducing races.

I'm generally not comfortable with a solution here that requires either
analyzing races away or winning them at runtime, if there is a viable non-racy
alternative.

[bcwhite, 2017/02/01 22:01:47]

The thread creation time would be captured during the ctor of the
StackSamplingProfiler so at a known time and from a known thread.

The thread under test could still die and be replaced in that time but that's a
race outside of this module.  It's up to the caller to ensure that the thread it
wants to profile is still alive when the ctor returns, before Start is called,
something it has the chance of doing because it has more knowledge.

It'll be possible to verify the thread even on the very first sampling attempt.
Any solution is going to have potential race conditions to verify but this at
least is simple and easy to follow.

[Mike Wittman, 2017/02/02 02:48:05]

I am not convinced that we've enumerated and addressed all the possible races
here, and I am skeptical that this is realistically possible given the
dependence on Win32 implementation details. Take GetThreadTime() for example:
your analysis assumes that this executes in a short time and that the values it
returns reflect some relatively current state of reality. Neither of these is
guaranteed to be true, and even if they are now the behavior could change in the
future. There are probably other assumptions we're both making about how this
call and SuspendThread work that may be invalid. Depending on undocumented
behavior is risky and should be avoided where possible.

An entirely separate can of worms is cross-platform support. GetThreadTimes() is
a Win32 API. Even if there are equivalent APIs on OS X, iOS, Linux, and Android,
there's basically zero chance we can depend on winning the same races,
consistently, on every one of those platforms now and in the future. It's also
unknown if the SuspendThread-equivalent will reliably tell us if the thread was
terminated (this is true for Windows too for that matter).

If GetThreadTimes() and its other-platform equivalents take locks then they
cannot be called while the thread is suspended, making races unavoidable. 
As far as I'm aware the strawman proposal I mentioned has no race conditions due
to the use of established synchronization primitives. It also depends solely on
cross-platform interfaces.

Given all the issues with the SuspendThread/GetThreadTimes approach I'm not OK
moving forward with it for handling thread exit. We need a solution that
guarantees correct behavior in all cases.

[bcwhite, 2017/02/02 14:24:25]

Undocumented?  GetThreadTimes is a published and supported API of which the only
behavior we're looking at is the reported creation time.
https://msdn.microsoft.com/en-us/library/windows/desktop/ms683237(v=vs.85).aspx

We can't guarantee the time and operation of future Chrome changes, either, but
since GetThreadTime() is a published API upon which thousands of applications
likely depend, I don't see it changing in any significant way.  And it really
doesn't matter if it's not exceptionally quick (though it likely is) since it'll
be running on the sampling thread after the sampled thread has been resumed.  As
you've said, 100s of ms is a lot of time.  Even if there were many concurrent
profiles being collected, it's not going be significant compared to the existing
activities of stopping a thread, copying its stack, and decoding it.
Cross-platform is already a can of worms.  Recording and checking the thread-ID
would live in the platform-specific NativeStackSamplerWin class.  When (if?)
other platform support gets added, those classes can use whatever is appropriate
for them.  Or if nothing works, then a more complex solution can be
investigated.  There's no benefit in trying to code specifically for them in
advance.
I wouldn't do it while suspended anyway for reasons I mentioned previously.
It does.  I don't know what they are, but I'm sure they're there.  Managing the
start/stop of a thread proved to be insanely difficult.  But even if I'm wrong,
the proposal is far more complex and difficult to understand than this simple,
self-contained solution.  The proposal also makes assumptions about the threads
under test, something that may prove limiting in the future.  Somebody is bound
to want to trace a PlatformThread without a message-loop at some point.
No, you don't.  You need to be sure it won't crash but other than that, you just
need a solution that has a signal-to-noise ratio sufficient to analyze the data;
I see very little, if any, noise coming from this.  We can't let "perfect" be
the enemy of the "good".

This is a simple solution and can be implemented quickly and cleanly.  We should
do it.  If it proves to be untenable in the field, then we can investigate more
complicated methods.

[Mike Wittman, 2017/02/02 19:22:31]

Several points:

1. Running the check after the sampling has already happened still leaves a
100ms race window, and still allows the failure scenarios I mentioned in comment
#139.

2. The point I was trying, inelegantly, to make above is that Win32
implementation details affect the length of the race window in ways which are
difficult to predict.

3. All it takes for this approach to go sideways, due to SuspendThread operating
on a different thread than GetThreadTimes, is one ill-timed context switch on
the profiler thread within the race window. The length of the window just makes
the probability of hitting this case more or less likely.

4. Given the number of Chrome users and the number of times this code is run,
events with even a vanishingly small probability of occurring will occur
reliably over the population. A one-in-a-million event during profiling will
occur hundreds of times per day, just over the population of canary and dev
users. The guard page check in the code is there to handle a case that occurs
with a probability of around 1 in 10,000,000, and was generating a
non-negligible number of crash reports.
The OS X implementation is in progress; one of the Mac developers has already
started working on it.
The strawman proposal uses standard Chrome synchronization primitives and would
be significantly easier to understand by the average Chrome developer than the
use of Win32 APIs. Effectively the only restrictions it places on the profiled
threads is that, if they are being profiled from a thread other than themselves,
that thread must be responsible for ensuring the profiled thread outlives the
profiling. There's no need for the profiled thread to have a message loop.
I am not sure it won't crash and I haven't seen sufficient justification in this
thread for why it won't crash. I've even outlined a possible scenario where not
only will it crash, but it will deadlock other processes on the system. This
would not only be incredibly poor behavior, but potentially a huge PR black eye
("Chrome is so unstable it crashes my other applications too!").

Summarizing my objections to this approach:
- it's platform-specific, and it's highly uncertain whether it can even be
applied to other platforms
- it's racy, probably unavoidably so
- we don't understand all the consequences of losing the race, but there's good
reason to believe that at least one consequence is crashes and system
instability
- losing the race will happen with non-negligible frequency over the user
population
- there's good reason to believe that an alternate implementation is possible
that doesn't have these drawbacks

This is the best I can do to explain why I can't approve this approach to
handling thread exit. If you want to continue pursuing it, you'll need to
escalate to danakj or another Chrome threading/synchronization guru.

[bcwhite, 2017/02/02 20:46:16]

100ms?  If the check happens immediately after the sampling, it is checked as
soon as the sample is converted.  That's us.

And the failure case is that the last sample gets dropped unnecessarily.  That's
not a serious problem.
But it's not.  The GetThreadTimes is done on the same thread, just after it is
resumed, all within the NativeStackSampler.
Crashes are serious things, and one-in-ten-million crashes would be a
significant addition to the current number of crashes.

But one-in-a-million bad samples is in no way significant, an error of 0.0001%
which is minuscule and certainly less than the normal variation seen when
aggregating samples.
And do they claim that there is no platform-specific way to detect if a thread
has exited?
It also requires modification of every thread that needs to be sampled,
something that will limit the ease of using this tool.  Plus, those
modifications may have far-reaching effects since they will change the
characteristics of how the thread exits, possibly affecting other threads
waiting on it.  There's no way to predict how far those effects will propagate.
If it won't work or risks other processes then I agree with you and a more
complicated solution needs to be used.

What I'm trying to determine at the moment is if a thread-ID can be reused while
a win::ScopedHandle to it is still open to that thread.  Seems to me something
the OS would prevent...

From this article on SO...
http://stackoverflow.com/questions/14863919/does-a-thread-id-stay-unique-vali...
... it seems to be the case that the thread-ID CANNOT be reused until the
ScopedHandle used by the NativeStackSampler releases it.

If that is the case then there is no need to worry about the thread being
replaced with one of an identical ID while it is being sampled and all this can
be simplified.

Is there something I'm missing about this?

[Mike Wittman, 2017/02/02 22:29:15]

Are you presuming the GetThreadTimes call is made both before and after the
thread suspension? Otherwise the race window is the interval between the
GetThreadTimes call and the next SuspendThread call, which is the 100ms between
the end of one sample and the start of the next. If the thread gets replaced
during that window, SuspendThread will operate on the wrong thread.
The failure I've mentioned results in a crash and deadlock and works like this:

1. GetThreadTimes call is made. Thread id and creation time match what was seen
previously.
2. Time goes by...
3. The thread is replaced by a thread in another process.
4. SuspendThread is called on the new thread and succeeds.
5. The NativeStackSampler attempts to copy the thread's stack, but generates an
access violation because the thread's stack lives in another process' address
space.
6. Chrome crashes. The thread in the other process remains permanently
suspended.
What do you mean by "it's not"? The context switch won't happen in this case?
The issue I see with this affecting the data is that it's turning what is
currently a retryable failure (SuspendThread failed) into a permanent failure.
To the extent that SuspendThread fails due reasons other than the thread has
exited, we will miss out collecting all the rest of the collection's samples.
It's unclear how often this will happen. There's one case described in the
documentation, but it's unclear what other scenarios will cause this behavior.
I looked at the initial OS X implementation and the SuspendThread equivalent
effectively operates on pid_t's, which are reused by the OS. So it's very likely
subject to the same race conditions.
It doesn't require modification of every thread that needs to be sampled, it
just requires allocation of a StackSamplingProfiler on the stack for any thread
that wants to sample itself. The other main use case of threads sampled on
behalf of the thread scheduler require no changes. The only effect on thread
exit is that the profiled thread might need to wait for the profiler thread to
finish its current sample, and there may still be ways to mitigate that if it
proves burdensome.
I don't know if a thread id can be reused while holding a handle. But even if
this works on Windows, it's unlikely to work on OS X since there's no
corresponding handle concept. On that platform we'll probably have to implement
a synchronization-based solution similar what I've proposed. At that point,
given a cross-platform implementation, there would be no reason not to replace
the Windows implementation with that solution to minimize code complexity. I
don't see why we shouldn't just avoid the intermediate step.

[bcwhite, 2017/02/03 13:28:38]

Okay, you've convinced me: If a thread were to exit and its ID be reused,
whether it be another Chrome thread or in some outside process, then Bad
Things(tm) may happen if any attempt to suspend that thread is made.  There is
no way, in the NativeStackSampler alone, to fully eliminate such a possibility.

I also agree with you completely that any solution should be implemented, if
practical, in a generic manner that applies to all architectures and even,
ideally, is reusable for other purposes.  That's just a general principal and
good idea.

However, documentation states that a thread-ID cannot be reused under Windows as
long as there are any open handles to that thread.  Since the
NativeStackSamplerWin object holds an open handle, the thread-ID cannot be
reused and thus no other solution is necessary. Additional protection should not
be implemented speculatively based on what may be needed in the future.

If the implementation of stack-sampling for another OS does need a more
elaborate solution, then one should be implemented at that time as part of that
effort.

Do you agree?

[Mike Wittman, 2017/02/03 17:24:15]

No, sorry, I don't agree.

Support for other OS's is not a future concern. Mac support is being worked on
right now by an engineer the team has committed for the project.

I don't see how this approach could work on Mac. Going with it would not only
shift the burden for implementing cross-platform support onto the Mac developer
but would make their job much harder by forcing them to deal with a bunch of
complexity that doesn't apply to them. They're not going to be comfortable
changing the Windows-specific implementation, so the end result will be two
different implementations doing the same thing. Then, someone with Windows
experience will have to come in and clean this up just to get back to the state
we would have been if we'd implemented the cross-platform interface in the first
place.

That's a ton of unnecessary work and code churn.

[bcwhite, 2017/02/03 18:47:58]

Correct.  Or at least to a different CL.
There is no other complexity.  There is absolutely nothing that needs to be done
here.  The native sampler will work exactly as it did before.  There is no need
to try to handle the "thread under test dies" case as it is already safe.

It's safe exactly as it was.  For me to write something that isn't necessary on
the hope that it will fulfill someone else need would not be in line with
standard Chrome development and could easily result in more churn trying to do
so.

[Mike Wittman, 2017/02/04 01:09:29]

The complexity is inherent in this change: it adds functions and state to the
cross-platform NativeStackSampler interface that only apply to Windows. The Mac
developer will have to understand and keep straight what parts of this interface
apply to them, what parts don't, how both of those parts interact each other and
with the cross-platform support that they will need to implement, and how to
make the StackSamplingProfiler work with both systems at the same time.

I've been here -- working on a cross-platform interface with inconsistent
platform-specific implementations -- and it increases the level of difficulty
and complexity substantially, well beyond what it would take to just implement
the cross-platform support from scratch.
Why do you say this will work as it did before? The profiler thread join in the
StackSamplingProfiler destructor, which prevented profiling past thread exit in
the single-thread-profiling implementation, has gone away with the
multi-threading changes. It hasn't been replaced with something that works
consistently across platforms.

It's particularly ill-timed to be regressing this behavior now, right when we're
trying to bring up the profiler on Mac.
Chrome is a cross-platform product. Implementing platform-specific functionality
that not only does not generalize across platforms, but makes it harder to do so
is counterproductive. Especially if there is a known need for the functionality
on other platforms at time of implementation and a likely viable
platform-independent alternative.

I appreciate the effort that has gone into this thread exit implementation. But
the bottom line is that, even if it works on Windows, it would move the project
further from where it needs to be rather than closer.

The suggestion I made for a cross platform approach is conceptually similar to
the single-thread-profiling join-on-destruction implementation, so there's good
reason to believe it will work without a huge amount of effort.

[bcwhite, 2017/02/04 02:07:01]

Not true.  I can remove completely everything I added to the NativeSampler and
it will continue to work.  I left them in place because it helps the *test*.

In fact, the only addition is recording the state of the thread under test in
detail.  The detail could be easily reduced or removed completely.
It continues to sample but gets only empty frames because the SuspendThread call
will fail.  When there are no more samples to take, it executes the callback. 
If the object of that callback has gone away (it should be a weak-pointer), then
the callback will do nothing.

Dealing the the sampling of the thread that owns the Profiler isn't sufficient
anyway.  Thread A could start sampling on thread B but then B could exit without
A's knowledge or destruction of the profiler doing the sampling.  Handling this
general case also handles the A-samples-A special case and the Windows
NativeStackSampler handles the generic case by returning empty stack frames
after the thread exit.

Yes, it would be nice to be able to tell if the thread has actually exited and
stop the sampling immediately but I haven't found any way to do that reliably.
When it was only the main thread sampling the main thread during startup, there
was only the special case but now that we want to be able to sample any thread
at any time, the general case has to be addressed and thus will have to be
addressed on the Mac, too.  And in addressing that, it'll address the special
case as well.


I've asked Alexei to weigh in on this discussion because it seems we're coming
at this from different directions and a new voice may help clear things up.

[Mike Wittman, 2017/02/06 20:54:06]

Even if the interface is updated to be the same across platforms, the behavior
will still be different and the StackSamplingProfiler/SamplingThread will need
to operate differently depending on whether it is running on Windows or Mac. The
code will have to operate against two different sets of invariants.
How can this work on Mac? It's still subject to all the problems I outlined at
the end of comment #154.
General A-samples-B is a relatively unimportant use case within Chrome, and
should not be driving the implementation. The two main use cases that need to be
supported now and in the future, respectively, are A-samples-A and thread
scheduler-samples-thread scheduler-managed thread.

A-samples-A can be handled in a cross-platform manner by having the
StackSamplingProfiler coordinate with SamplingThread to ensure the
SamplingThread is done with the profiled thread before the profiled thread
exits.

Thread scheduler-directed sampling can be handled by the thread scheduler
notifying the SamplingThread before it shuts down threads.

In a thread scheduler world, general A-samples-B is at best a niche use case. If
someone wants this, it still can be supported the same way as A-samples-A by
delegating the responsibility for ensuring that the thread outlives the
StackSamplingProfiler onto the StackSamplingProfiler user. In pretty much any
non-thread-scheduler case where A-samples-B would be useful, A will already have
some relationship with B that it can leverage to be notified prior to B exiting.
Thanks, I think this is a good idea.

+  if (sample.frames.empty()) {
+    // Indicate that collection is complete so it stops below and finishes.
+    // The empty frame remains as an indicator during analysis that the
+    // thread exited.
+    collection->sample = collection->params.samples_per_burst - 1;
+    collection->burst = collection->params.bursts - 1;
+  }
+
+  // If this is the last sample of a burst, record the total time.
+  if (collection->sample == collection->params.samples_per_burst - 1) {
+    profile.profile_duration = Time::Now() - collection->profile_start_time;
+    collection->native_sampler->ProfileRecordingStopped();
+  }
+}
+
+void StackSamplingProfiler::SamplingThread::CheckForIdle() {
+  if (!active_collections_.empty())
     return;
 
-  CallStackProfiles profiles;
-  CollectProfiles(&profiles);
-  concurrent_profiling_lock.Get().Release();
-  completed_callback_.Run(std::move(profiles));
-}
-
-// Depending on how long the sampling takes and the length of the sampling
-// interval, a burst of samples could take arbitrarily longer than
-// samples_per_burst * sampling_interval. In this case, we (somewhat
-// arbitrarily) honor the number of samples requested rather than strictly
-// adhering to the sampling intervals. Once we have established users for the
-// StackSamplingProfiler and the collected data to judge, we may go the other
-// way or make this behavior configurable.
-void StackSamplingProfiler::SamplingThread::CollectProfile(
-    CallStackProfile* profile,
-    TimeDelta* elapsed_time,
-    bool* was_stopped) {
-  ElapsedTimer profile_timer;
-  native_sampler_->ProfileRecordingStarting(&profile->modules);
-  profile->sampling_period = params_.sampling_interval;
-  *was_stopped = false;
-  TimeDelta previous_elapsed_sample_time;
-  for (int i = 0; i < params_.samples_per_burst; ++i) {
-    if (i != 0) {
-      // Always wait, even if for 0 seconds, so we can observe a signal on
-      // stop_event_.
-      if (stop_event_.TimedWait(
-              std::max(params_.sampling_interval - previous_elapsed_sample_time,
-                       TimeDelta()))) {
-        *was_stopped = true;
-        break;
-      }
-    }
-    ElapsedTimer sample_timer;
-    profile->samples.push_back(Sample());
-    native_sampler_->RecordStackSample(&profile->samples.back());
-    previous_elapsed_sample_time = sample_timer.Elapsed();
+  AutoLock lock(task_runner_lock_);
+  if (!task_runner_idle_shutdown_time_.is_zero()) {
+    GetTaskRunnerOnSamplingThread()->PostDelayedTask(
+        FROM_HERE, Bind(&SamplingThread::ShutdownTask, Unretained(this)),
+        task_runner_idle_shutdown_time_);
   }
+}
 
-  *elapsed_time = profile_timer.Elapsed();
-  profile->profile_duration = *elapsed_time;
-  native_sampler_->ProfileRecordingStopped();
+void StackSamplingProfiler::SamplingThread::AddCollectionTask(
+    std::unique_ptr<CollectionContext> collection_ptr) {
+  // Ownership of the collection is going to be given to a map but a pointer
+  // to it will be needed later.
+  CollectionContext* collection = collection_ptr.get();
+  active_collections_.insert(
+      std::make_pair(collection->collection_id, std::move(collection_ptr)));
+
+  GetTaskRunnerOnSamplingThread()->PostDelayedTask(
+      FROM_HERE, Bind(&SamplingThread::PerformCollectionTask, Unretained(this),
+                      collection->collection_id),
+      collection->params.initial_delay);
 }
 
-// In an analogous manner to CollectProfile() and samples exceeding the expected
-// total sampling time, bursts may also exceed the burst_interval. We adopt the
-// same wait-and-see approach here.
-void StackSamplingProfiler::SamplingThread::CollectProfiles(
-    CallStackProfiles* profiles) {
-  if (stop_event_.TimedWait(params_.initial_delay))
+void StackSamplingProfiler::SamplingThread::RemoveCollectionTask(int id) {
+  auto found = active_collections_.find(id);
+  if (found == active_collections_.end())
     return;
 
-  TimeDelta previous_elapsed_profile_time;
-  for (int i = 0; i < params_.bursts; ++i) {
-    if (i != 0) {
-      // Always wait, even if for 0 seconds, so we can observe a signal on
-      // stop_event_.
-      if (stop_event_.TimedWait(
-              std::max(params_.burst_interval - previous_elapsed_profile_time,
-                       TimeDelta())))
-        return;
-    }
+  FinishCollection(found->second.get());
+  CheckForIdle();
+}
 
-    CallStackProfile profile;
-    bool was_stopped = false;
-    CollectProfile(&profile, &previous_elapsed_profile_time, &was_stopped);
-    if (!profile.samples.empty())
-      profiles->push_back(std::move(profile));
+void StackSamplingProfiler::SamplingThread::PerformCollectionTask(int id) {
+  auto found = active_collections_.find(id);
 
-    if (was_stopped)
+  // The task won't be found if it has been stopped.
+  if (found == active_collections_.end())
+    return;
+
+  CollectionContext* collection = found->second.get();
+
+  // Handle first-run with no "next time".
+  if (collection->next_sample_time == Time())
+    collection->next_sample_time = Time::Now();
+
+  // Do the collection of a single sample.
+  RecordSample(collection);
+
+  // Update the time of the next sample recording.
+  if (UpdateNextSampleTime(collection)) {
+    bool success = GetTaskRunnerOnSamplingThread()->PostDelayedTask(
+        FROM_HERE,
+        Bind(&SamplingThread::PerformCollectionTask, Unretained(this), id),
+        std::max(collection->next_sample_time - Time::Now(), TimeDelta()));
+    DCHECK(success);
+  } else {
+    // All capturing has completed so finish the collection. Let object expire.
+    // The |collection| variable will be invalid after this call.
+    FinishCollection(collection);
+    CheckForIdle();
+  }
+}
+
+void StackSamplingProfiler::SamplingThread::ShutdownTask() {
+  // Holding this lock ensures that any attempt to start another job will
+  // get postponed until StopSoon can run thus eliminating the race.
+  AutoLock lock(task_runner_lock_);
+
+  // If this is a forced, permanent shutdown, stop all active collections.
+  if (task_runner_forced_shutdown_) {
+    // FinishCollection will remove the entry thus invalidating any iterator.
+    while (!active_collections_.empty())
+      FinishCollection(active_collections_.begin()->second.get());
+  } else {
+    // If active_collections_ is not empty, something new has arrived since
+    // this task got posted. Abort the shutdown so it can be processed.
+    if (!active_collections_.empty())
+      return;
+    // It's possible that a new AddCollectionTask has been posted after this
+    // task. Reset the "create requests" counter and try again after any other
+    // pending tasks.
+    if (task_runner_create_requests_ > 0 && task_runner_) {
+      task_runner_create_requests_ = 0;
+      task_runner_->PostTask(
+          FROM_HERE, Bind(&SamplingThread::ShutdownTask, Unretained(this)));
       return;
+    }
+    // There can be no new AddCollectionTasks at this point because creating
+    // those always increments "create requests". There may be other requests,
+    // like Remove, but it's okay to schedule the thread to stop once they've
+    // been executed (i.e. "soon").
   }
+
+  // Stop the underlying thread as soon as all immediate tasks are complete.
+  // Calling Stop() directly would result in deadlock.
+  StopSoon();
+
+  // StopSoon will have set the owning sequence (again) so it must be detached
+  // (again) in order for Stop/Start to be called (again) should more work
+  // come in. Holding the |task_runner_lock_| ensures the necessary happens-
+  // after with regard to this detach and future Thread API calls.
+  DetachFromSequence();
+
+  // Clear the task_runner_ variable so the thread will be restarted when
+  // new work comes in.
+  task_runner_ = nullptr;
+}
+
+bool StackSamplingProfiler::SamplingThread::UpdateNextSampleTime(
+    CollectionContext* collection) {
+  if (++collection->sample < collection->params.samples_per_burst) {
+    collection->next_sample_time += collection->params.sampling_interval;
+    return true;
+  }
+
+  // This will keep a consistent average interval between samples but will
+  // result in constant series of acquisitions, thus nearly locking out the
+  // target thread, if the interval is smaller than the time it takes to
+  // actually acquire the sample. Anything sampling that quickly is going
+  // to be a problem anyway so don't worry about it.
+  if (++collection->burst < collection->params.bursts) {
+    collection->sample = 0;
+    collection->next_sample_time += collection->params.burst_interval;
+    return true;
+  }
+
+  return false;
 }
 
-void StackSamplingProfiler::SamplingThread::Stop() {
-  stop_event_.Signal();
+void StackSamplingProfiler::SamplingThread::CleanUp() {
+  // There should be no collections remaining when the thread stops.
+  DCHECK(active_collections_.empty());
+
+  // Let the parent clean up.
+  Thread::CleanUp();
 }
 
 // StackSamplingProfiler ------------------------------------------------------
@@ -287,8 +656,6 @@ StackSamplingProfiler::StackSamplingProfiler(
 
 StackSamplingProfiler::~StackSamplingProfiler() {
   Stop();
-  if (!sampling_thread_handle_.is_null())
-    PlatformThread::Join(sampling_thread_handle_);
 }
 
 // static
@@ -310,16 +677,39 @@ void StackSamplingProfiler::Start() {
   if (!native_sampler)
     return;
 
-  sampling_thread_.reset(new SamplingThread(std::move(native_sampler), params_,
-                                            completed_callback_));
-  if (!PlatformThread::Create(0, sampling_thread_.get(),
-                              &sampling_thread_handle_))
-    sampling_thread_.reset();
+  collection_id_ = SamplingThread::GetInstance()->Add(
+      MakeUnique<SamplingThread::CollectionContext>(
+          thread_id_, params_, completed_callback_, std::move(native_sampler)));
 }
 
 void StackSamplingProfiler::Stop() {
-  if (sampling_thread_)
-    sampling_thread_->Stop();
+  SamplingThread::GetInstance()->Remove(collection_id_);
+}
+
+// static
+void StackSamplingProfiler::Shutdown() {
+  SamplingThread::GetInstance()->Shutdown();
+}
+
+// static
+void StackSamplingProfiler::UndoShutdownForTesting() {
+  SamplingThread::GetInstance()->UndoShutdown();
+}
+
+// static
+bool StackSamplingProfiler::IsSamplingThreadRunningForTesting() {
+  return SamplingThread::GetInstance()->IsRunning();
+}
+
+// static
+void StackSamplingProfiler::SetSamplingThreadIdleShutdownTimeForTesting(
+    int shutdown_ms) {
+  SamplingThread::GetInstance()->SetIdleShutdownTime(shutdown_ms);
+}
+
+// static
+void StackSamplingProfiler::InitiateSamplingThreadIdleShutdownForTesting() {
+  SamplingThread::GetInstance()->ShutdownIfIdle();
 }
 
 // static