Add an initial revision of an audio server.

services/media/audio/audio_output.h

+// 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.
+
+#ifndef SERVICES_MEDIA_AUDIO_AUDIO_OUTPUT_H_
+#define SERVICES_MEDIA_AUDIO_AUDIO_OUTPUT_H_
+
+#include <deque>
+#include <memory>
+#include <set>
+
+#include "base/callback.h"
+#include "base/synchronization/lock.h"
+#include "base/threading/sequenced_worker_pool.h"
+#include "mojo/services/media/common/cpp/local_time.h"
+#include "services/media/audio/audio_pipe.h"
+#include "services/media/audio/audio_track_impl.h"
+#include "services/media/audio/fwd_decls.h"
+
+namespace mojo {
+namespace media {
+namespace audio {
+
+class AudioOutput {
+ public:
+  virtual ~AudioOutput();
+
+  // AddTrack/RemoveTrack
+  //
+  // Adds or removes a track to/from the set of current set of tracks serviced
+  // by this outputs.  Called only from the main message loop.  Obtains the

[jeffbrown, 2015/11/04 23:43:32]

outputs -> output

[johngro, 2015/11/06 02:20:24]

Done.

+  // processing_lock and may block for the time it takes the derrived class to

[jeffbrown, 2015/11/04 23:43:33]

derrived -> derived

[johngro, 2015/11/06 02:20:24]

Done.

+  // run its processing task if the task is in progress when the method was
+  // called.

[jeffbrown, 2015/11/04 23:43:32]

In general it's safer to avoid immediately calling back into object here.  Are
there any downsides to simply scheduling the task to be run at the next
available opportunity?

[johngro, 2015/11/06 02:20:24]

I'm not sure that I understand the question.  As the comment mentions, things
which call these methods are always scheduled to run on the main message loop
thread; IOW - if an output want to shut itself down, for whatever reason, the
act of unlinking will be scheduled on the message loop thread, and "run at the
next available opportunity".

If an output is being added or removed because of an action taken on the server
side of thing, it is already in the context of the message loop thread, and this
is the "next available opportunity".

+  MediaResult AddTrackLink(AudioTrackToOutputLinkPtr link);
+  MediaResult RemoveTrackLink(const AudioTrackToOutputLinkPtr& link);
+
+ protected:
+  explicit AudioOutput(AudioOutputManager* manager);
+
+  //////////////////////////////////////////////////////////////////////////////
+  //
+  // Methods which may be implemented by derived classes to customize behavior.
+  //
+  //////////////////////////////////////////////////////////////////////////////
+
+  // Init
+  //
+  // Called during startup on the AudioServer's main message loop thread.  No
+  // locks are being held at this point.  Derived classes should allocate their
+  // hardware resources and initialize any internal state.  Return
+  // MediaResult::OK if everything is good and the output is ready to do work.
+  virtual MediaResult Init();

[jeffbrown, 2015/11/04 23:43:32]

Consider using a convention such as OnInit() to distinguish methods which are
intended to be overridden by implementors from others which are not.

[johngro, 2015/11/06 02:20:24]

If I had not intended for the method to be overridden, I would not have marked
it virtual, nor would I have added the helpful comment telling people that they
should override this method and do particular things here.

Furthermore, if this was a method which was meant to be overridden, and I was
overriding it in a derived class, and I didn't want subsequent derivations to
override the method, I would mark it "final" instead of marking it as
"override".

Finally, if I wanted to added a non-virtual method, and force the client to
never have a method with the same signature, I could also mark it as "final". 
This has the unfortunate side effect of forcing the method to become virtual,
and non-overridable.  I probably would not bother to do this because it..
1) costs something.
2) protects nothing.  Derived classes can always add methods with whatever name
they want, but someone with a base class pointer cannot accidentally call them
without first casting to the derived class.

+
+  // Cleanup
+  //
+  // Called at shutdown on the AudioServer's main message loop thread to allow
+  // derived classes to clean up any allocated resources.  All pending
+  // processing callbacks have either been nerfed or run till completion.  All
+  // AudioTrack tracks have been disconnected.  No locks are being held.
+  virtual void Cleanup();
+
+  // Process
+  //
+  // Called from within the context of the processing lock any time a scheduled

[jeffbrown, 2015/11/04 23:43:32]

Technically you don't need a lock to guarantee serialization.

Does this run on the main thread too or on a worker?  If it's on a worker, you
might want to make the subclass set the processing callback in some clearly
distinguishable way, such as by passing a closure to a function to register or
schedule it.

[johngro, 2015/11/06 02:20:24]

The lock is not being used to guarantee serialization.  Serialization is
guaranteed by the base::SequencedTaskRunner which acts as the thread pool and
imposes the message driven architecture encouraged by the mojo folks.

The lock is used for the following two purposes...
1) Protecting the client/link set.
2) Synchronizing with callbacks in-flight during shutdown.

re #1
Right now, the client set is held static for the duration of a "process"
operation.  This scope can be tightened (by adding a specific lock to protect
the set), but would shift the burden of properly protecting the link set to the
derived classes which actually process their links during the processing
callback.

re #2
When final cleanup is happening in the context of the main message loop thread,
we need to reach a point in time where we have a strong guarantee that any
callbacks in flight have either been safely canceled, or run to completion.  A
classic pattern is implemented here... The guy doing the shutdown (main message
loop) begins by flagging the TaskRunner to shutdown an cancel all callbacks,
then sets a volatile flag in the output indicating that any callback which had
already launched should fast-abort.  Then, it attempts to enter the callback
lock.

On the other side of things, A callback in flight begins by promoting its weak
pointer to the output object, and then entering the processing lock and fast
aborting if the shutdown flag is set.  This flag is made available to derived
classes so that they may also abort their computation early if a shutdown has
been requested.

Back on the message loop thread, if an output process task has made it past all
of these checks, it will end up blocking until the output process task notices
the shutdown flag, or terminates normally.  After it has successfully entered
the lock, it has achieved its strong guarantee that all in-flight callbacks have
been effectively canceled, or run to completion.

A couple more small points.
+ Memory safety from the processing callback perspective is ensured by the weak
pointer.  If a callback is in flight, and the task runner shutdown does not
manage to cancel the task before a thread picks it up and is running, and the
message loop side of things gets all of the way to the point where it has
destroyed the object, the weak pointer promotion will fail and the callback will
do nothing.
+ OTOH, if the process callback successfully promotes the weak pointer, and then
the message loop runs to the point of releasing its reference before the
processing callback takes any other steps, the process callback will enter an
uncontested lock, notice the shutdown flag and immediately exit the lock having
done nothing.  When the promoted weak pointer goes out of scope, the output's
memory will be returned to the heap.  No complex interactions take place in the
destructor of an audio output, just freeing memory.  All freeing of driver
specific resources happened in the context of the message loop thread during the
shutdown process after the processing callbacks had been successfully
neutralized.

Re: thread context.  It runs strictly within the scope of on of the threads
which comes from the base::SequencedTaskManager thread pool.  This base:: object
ensures that for any given output, all scheduled callbacks are serialized
(although, not guaranteed to be the same thread between successive invocations).
 I will update the comment to attempt to make this more clear.

+  // processing callback fires.  One callback will be automatically scheduled at
+  // the end of initialization.  After that, derived classes are responsible for
+  // scheduling all subsequent callbacks to keep the engine running.
+  virtual void Process() = 0;
+
+  // InitializeLink
+  //
+  // Called on the AudioServer's main message loop any time a track is being
+  // added to this output.  Outputs should allocate and initialize any
+  // bookkeeping they will need to perform mixing on behalf of the newly added
+  // track.
+  //
+  // @return MediaResult::OK if initialization succeeded, or an appropriate
+  // error code otherwise.
+  virtual MediaResult InitializeLink(const AudioTrackToOutputLinkPtr& link);
+
+  //////////////////////////////////////////////////////////////////////////////
+  //
+  // Methods which may used by derived classes from within the context of a
+  // processing callback.  Note; since these methods are intended to be called
+  // from the within a processing callback, the processing_lock will always be

[jeffbrown, 2015/11/04 23:43:32]

This here suggests that these methods should be provided as part of a context
object to the processing callback rather than mixed in here alongside everything
else.

ie. The code could invoke the processing function and pass an object with the
relevant state and functions.

Process(ProcessingContext* context)

[johngro, 2015/11/06 02:20:24]

I don't understand.  The context, in this case, is the base object itself. 
Actions need to be taken to schedule the next callback, and to begin the process
of deferring shutdown to the message loop thread which require the private state
of the base object itself.  Why would it be advantageous to add a layer of
indirection between the derived object and its base class?

+  // held when they are called.
+  //
+
+  // ScheduleCallback
+  //
+  // Schedule a processing callback at the specified absolute time on the local
+  // clock.
+  void ScheduleCallback(LocalTime when);
+
+  // ShutdownSelf
+  //
+  // Kick off the process of shooting ourselves in the head.  Note, after this
+  // method has been called, no new callbacks may be scheduled.  As soon as the
+  // main message loop finds out about our shutdown request, it will complete
+  // the process of shutting us down, unlinking us from our tracks and calling
+  // the Cleanup method.
+  void ShutdownSelf();
+
+  // shutting_down
+  //
+  // Check the shutting down flag.  Only the base class may modify the flag, but
+  // derived classes are free to check it at any time.
+  inline bool shutting_down() const { return shutting_down_; }
+
+  // TODO(johngro): Order this by priority.  Figure out how we are going to be
+  // able to quickly find a track with a specific priority in order to optimize
+  // changes of priority.  Perhaps uniquify the priorities by assigning a
+  // sequence number to the lower bits (avoiding collisions when assigning new
+  // priorities will be the trick).

[jeffbrown, 2015/11/04 23:43:33]

Could just use a heap.

[johngro, 2015/11/06 02:20:24]

sure, I pretty much already am; right now I am using a std::set which is
probably a red/black tree internally.  I could either overload the less operator
used to sort the set, or I could just use a std::map (I would prefer the former,
but need to think about it some).

What I am really concerned about here (and expressed in previous versions of
this comment, but somehow lost by the time it got here) is optimizing for
indexing this set two ways.  There is a short list of operations which need to
be optimized here, IMO.

1) Traversing the list in priority order.
2) Adding a track/link to the set.
3) Removing a track/link from the set.
4) Altering the priority of a track which is in the set.

re #1: This is the primary operation as it will happen far more often than other
ops.  It must be O(k).  Indexing the set based on priority is the obvious
solution.

re #2: This is an insertion operation based on the priority index.  As the
insertion into the underlying std::set/std::map is guaranteed to be O(log2), we
should be good here simply by indexing by priority.  (most implementations I
have every looked at of set/map use a red-black tree under the hood, so are
guaranteed to be 2*log(N) at worst)

re #3: Removing a track from the set involves looking it up by
id/pointer/handle/whatever.  Right now, this is O(log2) because my current set
is indexed by pointer.  If I change that to be indexed by link priority, then
removal becomes O(N).  This is undesirable, not because I am overly concerned
with the client (it is probably shutting down) but because it need to hold the
link set static for the duration of the lookup and removal operation which means
that if we want to perform a mix operation, we may have to wait for the O(N)
operation to complete.

re #4: This is basically an atomic remove-then-insert operation.  In the outline
above this would be O(N).  If #3 can be optimized, it becomes O(log2)

So; there are a few different ways I could optimize #3.  One way would be to
index the set two different ways.  Given that std::set/map do not support this,
you would need to accomplish this by making the object a member of two different
set-like objects.  In order to make this an improvement over what is described
here, you need to be able to get to the object in Index #2 after looking it up
in Index #1 in O(k) time (and vice-versa).  The best way I know to do this is to
use intrusive containers, and make the set bookkeeping for the indices part of
the object itself.  std:: containers do not support intrusive semantics.  boost
containers do, but are clearly not allowed here.  Rolling my own is unappealing,
but if I had to resort to such a thing, I would want to make it part of the
overall project, not just this.

Another option is what I am attempting to describe above.  If I can guarantee
uniqueness of priority, the set could be indexed based on priority alone and we
could leave it at that.  How the uniqueness is determined is the tricky part. 
One option would be to build a key which is made of the priority in the high
order bits, and the this pointer of the link in the low order bits.  This would
end up being a 96 bit object and would suffer some lookup performance hit as a
result.  Another way to do it would be to use the sequence number I mention
above.  Instead of the pointer, use a 32 bit sequence number generated at link
instantiate time appended to the priority in order to uniquify the key.  This
has the advantage to keeping our key to 64 bits, but has the disadvantage of
making sequence number generation complex.  Sequence numbers must either be
assumed to be unique (likely to be OK, but strictly speaking not OK), or they
need to be tested for uniqueness.  Testing them using this container alone is
technically O(N); a separate set of active sequence numbers would need to be
introduced to guarantee no collisions in O(log2) during generation.  Additional
complexity, but performed entirely on the message loop thread, so no locks are
required.  If the message loop ever becomes multi-threaded, the scope of lock
contention is limited to the input domain and does not affect the output domain.

TL;DR?
Yeah, I have thought about this some and there are some fine points which
deserve consideration.  I'm going to wait until we implement the priority
feature before implementing a solution.

+  //
+  // Right now, we have no priorities, so this is just a set of track/output
+  // links.
+  AudioTrackToOutputLinkSet links_;
+  AudioOutputManager* manager_;
+
+ private:
+  // It's always nice when you manager is also your friend.  Seriously though,
+  // the AudioOutputManager gets to call Init and Shutown, no one else
+  // (including derived classes) should be able to.
+  friend class AudioOutputManager;
+
+  // Thunk used to schedule delayed processing tasks on our task_runner.
+  static void ProcessThunk(AudioOutputWeakPtr weak_output);
+
+  // Called from the AudioOutputManager after an output has been created.
+  // Gives derived classes a chance to set up hardware, then sets up the
+  // machinery needed for scheduling processing tasks and schedules the first
+  // processing callback immediately in order to get the process running.
+  MediaResult Init(const AudioOutputPtr& self,
+                   scoped_refptr<base::SequencedTaskRunner> task_runner);
+
+  // Called from Shutdown (main message loop) and ShutdowSelf (processing

[jeffbrown, 2015/11/04 23:43:32]

I think it's a little weird for there to be two different sources of shutdown
events (the processing callback and the output manager).  It runs the risk of
the output getting into states that the output manager doesn't expect.

Consider providing some kind of callback for the output to tell the output
manager that it's in a bad state and needs to be shut down so that the output
manager is always the one driving the shutdown and can stay in sync with
everything.

[johngro, 2015/11/06 02:20:24]

That is how things handled now.  Shutdown self posts a message to the main
message loop (executed by the output manager) which actually performs the
shutdown through the central Shutdown choke-point.

+  // context).  Starts the process of shutdown, preventing new processing tasks
+  // from being scheduled, and nerfing any tasks in flight.
+  //
+  // @return true if this call just kicked off the process of shutting down,
+  // false otherwise.
+  bool BeginShutdown();
+
+  // Called from the AudioOutputManager on the main message loop
+  // thread.  Makes certain that the process of shutdown has started,
+  // synchronizes with any processing tasks which were executing at the time,
+  // then finishes the shutdown process by unlinking from all tracks and
+  // cleaning up all resources.
+  void Shutdown();
+
+  base::Lock processing_lock_;

[jeffbrown, 2015/11/04 23:43:33]

We won't need this lock if the processing state is encapsulated elsewhere.

[johngro, 2015/11/06 02:20:24]

I disagree.  See my comments regarding synchronization above.

+  base::Lock shutdown_lock_;

[jeffbrown, 2015/11/04 23:43:32]

We won't need this lock is shutdown is always initiated by the output manager on
the main thread.

[johngro, 2015/11/06 02:20:24]

Unfortunately, I think it is an important requirement that shutdown be initiated
from either side of the threading-fence.  There are many very good reasons that
an output may need to shut down in a timely fashion due to some unrecoverable
error situation.

Note: shutdown is not executed in the context of the thread-pool thread, it is
simply scheduled to execute on the main message loop thread via BeginShutdown. 
The shutdown_lock_ is used to make this operation thread safe in the unlikely
case that both side of the system decide that they want to shut down an output
at the same time.

+  scoped_refptr<base::SequencedTaskRunner> task_runner_;
+  AudioOutputWeakPtr weak_self_;
+
+  // TODO(johngro): Eliminate the shutting down flag and just use the
+  // task_runner_'s nullness for this test?
+  volatile bool shutting_down_ = false;
+  volatile bool shut_down_ = false;
+};
+
+}  // namespace audio
+}  // namespace media
+}  // namespace mojo
+
+#endif  // SERVICES_MEDIA_AUDIO_AUDIO_OUTPUT_H_
+