Web Audio API delay node distortion

RESOLVED FIXED in mozilla33

Status

()

defect
P1
normal
RESOLVED FIXED
6 years ago
5 years ago

People

(Reporter: ashley, Assigned: karlt)

Tracking

(Blocks 1 bug)

28 Branch
mozilla33
x86_64
All
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

()

Attachments

(13 attachments, 3 obsolete attachments)

1.64 KB, text/html
Details
16.78 KB, patch
Details | Diff | Splinter Review
1.42 KB, patch
Details | Diff | Splinter Review
109.56 KB, text/html
Details
1.32 KB, text/html
Details
1.57 KB, text/html
Details
6.62 KB, patch
padenot
: review+
karlt
: checkin+
Details | Diff | Splinter Review
10.71 KB, patch
roc
: review+
karlt
: checkin+
Details | Diff | Splinter Review
23.10 KB, patch
padenot
: review+
karlt
: checkin+
Details | Diff | Splinter Review
6.20 KB, patch
roc
: review+
Details | Diff | Splinter Review
29.57 KB, patch
roc
: review+
Details | Diff | Splinter Review
5.61 KB, patch
padenot
: review+
Details | Diff | Splinter Review
4.31 KB, patch
roc
: review+
Details | Diff | Splinter Review
User Agent: Mozilla/5.0 (Windows NT 6.3; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/31.0.1650.34 Safari/537.36

Steps to reproduce:

1. Visit http://www.scirra.com/labs/audioeffects/
2. Click 'Play SFX1', then SFX2, SFX3, SFX4 in turn. Then click 'Play music'.
3. When the music starts playing, click 'Add delay effect'


Actual results:

The audio plays back with lots of distortion (it sounds kind of fuzzy, like static playing over the top).

Also, following these steps, after closing the browser I get a ghost Nightly.exe process which is not using CPU but needs to be ended from task manager before it lets you open a new instance of the browser. This is reproducible every time on my system.


Expected results:

The audio should not be distorted and the process should exit correctly after closing the browser. All effects should sound like they do in Chrome.
I would add in my opinion you were over-optimistic to ship this in release with Firefox 25. This bug report is using Firefox 28 Nightly; in Firefox 25, it's far more unstable. The ghost process issue is also reproducible there, and audio also completely cuts out following these steps, or (non-reproducibly) degrades in to stuttering distortion after playing with a few different effects.

Additionally according to https://wiki.mozilla.org/WebAudio_API_Rollout_Status there is still no support for OscillatorNode (used to control the phaser and flanger effects, so they sound different in Firefox as they do to Chrome) or WaveTable (used for the distortion effect so it does not work in Firefox).

Construct 2, a major HTML5 game engine, supports all these features in its audio engine. We were forwards-thinking enough to feature detect the unprefixed AudioContext and have kept up to date with API changes, but this in turn means all existing web content using our engine is affected by the above issues.
I think the problems stem from context.createMediaElementSource(). This is the only sensible way to play music with the Web Audio API, and all Construct 2-made games have been using it for a long time. However Firefox 25 seems unable to emit any audio at all for this type of node, or only brief clips which cut out or reduce to distortion. Real-world example: http://www.scirra.com/labs/sbwebapp2/ (the title screen music and in-game music are played with HTML5 audio going through createMediaElementSource()).

The impact of this bug appears to be: Firefox can no longer play music in any game made using the Construct 2 engine.

We feature-detect the presence of createMediaElementSource before using it. If it does not exist, we simply play HTML5 audio separately without connecting it in to the Web Audio API. A possible workaround would be to remove the createMediaElementSource function until it is working. I would favour a patch to the stable branch for this.
Component: Untriaged → Web Audio
Product: Firefox → Core
(In reply to ashley from comment #0)
> Also, following these steps, after closing the browser I get a ghost
> Nightly.exe process which is not using CPU but needs to be ended from task
> manager before it lets you open a new instance of the browser. This is
> reproducible every time on my system.

This seems to be the same issue as bug 926522.  The process can continue for up to a minute.  I've verified that patches in that bug and its dependency fix this.

We can use this bug to track fixing the delay distortion.
Status: UNCONFIRMED → NEW
Ever confirmed: true
Summary: Web Audio API delay node distortion/ghost process → Web Audio API delay node distortion
(In reply to ashley from comment #1)
> Additionally according to
> https://wiki.mozilla.org/WebAudio_API_Rollout_Status there is still no
> support for OscillatorNode (used to control the phaser and flanger effects,
> so they sound different in Firefox as they do to Chrome) or WaveTable (used
> for the distortion effect so it does not work in Firefox).

I've updated that page as OscillatorNode and PeriodicWave were implemented in
Firefox 25.  In Firefox 25 Beta 7, on Linux, the distortion, phaser, flanger
effects sound similar to Chromium Version 30.0.1599.37.

(In reply to ashley from comment #2)
> I think the problems stem from context.createMediaElementSource(). This is
> the only sensible way to play music with the Web Audio API, and all
> Construct 2-made games have been using it for a long time. However Firefox
> 25 seems unable to emit any audio at all for this type of node, or only
> brief clips which cut out or reduce to distortion. Real-world example:
> http://www.scirra.com/labs/sbwebapp2/ (the title screen music and in-game
> music are played with HTML5 audio going through createMediaElementSource()).

I'm not aware of differences in MediaElementAudioSourceNode between Nightly
and Firefox 25, but on Win 7 I see these problems on
http://www.scirra.com/labs/audioeffects/ even without adding effects.

On Linux, I'm not really able to reproduce this issue.  I'm hearing the music
without problems on http://www.scirra.com/labs/sbwebapp2/ in Firefox 25 Beta
7.  I can reproduce at least one situation on Linux where the effects are not
good on Firefox 25 Beta 7 but OK on Nightly:

1. Visit http://www.scirra.com/labs/audioeffects/
2. Click 'Add distortion effect' twice
3. Click 'Play music' and then 'SFX4' immediately after.

I can also reproduce the delay effect problem even on Win 7 and Linux Nightly
with:

1. Visit http://www.scirra.com/labs/audioeffects/
2. Click 'Add delay effect' once.
3. Click 'Play music'.

Changing OS to all, at least for the delay effect issue reported in comment 0, though perhaps there may be something specific to MediaElementAudioSourceNode (?decoders) on WINNT.

A testcase in human-readable javascript may be necessary for diagnosis.
OS: Windows 8.1 → All
(In reply to Karl Tomlinson (:karlt) from comment #4)
> I can reproduce at least one situation on Linux where the effects are not
> good on Firefox 25 Beta 7 but OK on Nightly:
> 
> 1. Visit http://www.scirra.com/labs/audioeffects/
> 2. Click 'Add distortion effect' twice
> 3. Click 'Play music' and then 'SFX4' immediately after.

In fact, step 2 is not necessary.  This is best reproduced soon after page load.
This changed from an awful buzz to something believable on Nightly in this range.
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=ab5f29823236&tochange=3697f962bb7b

Even on a recent Nightly, however, with no effects applied, the music gets louder and more distorted each time "Play music" is clicked:

1. Visit http://www.scirra.com/labs/audioeffects/
2. Click 'Play music' repeatedly.
(In reply to Karl Tomlinson (:karlt) from comment #5)
> > 1. Visit http://www.scirra.com/labs/audioeffects/

> > 3. Click 'Play music' and then 'SFX4' immediately after.

> This changed from an awful buzz to something believable on Nightly in this
> range.
> http://hg.mozilla.org/mozilla-central/
> pushloghtml?fromchange=ab5f29823236&tochange=3697f962bb7b

The changeset that fixed that is http://hg.mozilla.org/mozilla-central/rev/b0f89cf3ede6, a follow-up in bug 752796, which is now in Firefox 26 beta.
https://hg.mozilla.org/releases/mozilla-beta/rev/b0f89cf3ede6
Filed bug 937962 on the distortion with createMediaElementSource, because that is still happening.
Priority: -- → P1
Assignee: nobody → paul
Posted file minimal test case
Someone gave me a nicer test case on twitter, attached here for posterity.

The problem seem to be about feedback loops:

source.connect(delay);
delay.delatTime.value = 0.5;
delay.connect(gain);
gain.gain.value = 0.4;
delay.connect(context.destination);
gain.connect(delay);
Here is a tentative diagnostic patch. Running the test case, we can see that the
stream ordering is not the same each time:

> Cycle detected, starting at 0x7f41826e0280
> -- 0x7f41826e00c0
> Cycle end
> Stream ordering: 
> -- DelayNodeEngine
> -- GainNodeEngine
> -- DestinationNodeEngine
> -- ScriptProcessorNodeEngine
> -- OscillatorNodeEngine
> End.
> Cycle detected, starting at 0x7f41826e00c0
> -- 0x7f41826e0280
> Cycle end
> Stream ordering: 
> -- GainNodeEngine
> -- DelayNodeEngine
> -- DestinationNodeEngine
> -- ScriptProcessorNodeEngine
> -- OscillatorNodeEngine
> End.
> Cycle detected, starting at 0x7f41826e0280
> -- 0x7f41826e00c0
> Cycle end
> Stream ordering: 
> -- DelayNodeEngine
> -- GainNodeEngine
> -- DestinationNodeEngine
> -- ScriptProcessorNodeEngine
> -- OscillatorNodeEngine
> End.

This could be an issue, I guess.
So, I applied ehsan's patch from bug 883010 (the one that could not be checked in because of failures), that makes us cache the stream order (so it's not recomputed every time, with the order change weirness), to quickly check my theory, and the distortion goes away.
(In reply to comment #10)
> So, I applied ehsan's patch from bug 883010 (the one that could not be checked
> in because of failures), that makes us cache the stream order (so it's not
> recomputed every time, with the order change weirness), to quickly check my
> theory, and the distortion goes away.

Perhaps that also explains the test failures?
(In reply to :Ehsan Akhgari (needinfo? me!) from comment #11)
> (In reply to comment #10)
> > So, I applied ehsan's patch from bug 883010 (the one that could not be checked
> > in because of failures), that makes us cache the stream order (so it's not
> > recomputed every time, with the order change weirness), to quickly check my
> > theory, and the distortion goes away.
> 
> Perhaps that also explains the test failures?

Maybe. I've picked up your patch again and I'm trying to make it green, but I hit a jit crash so it slowed me down a bit. It seems promising, although the real fix for this bug would be to make the ordering of the stream the same regardless of the order in which they are before ordering.
The stream order should be cached where possible, but that is not the solution to this bug.  (Consider for example, the cycle / feedback loop running while changes are made elsewhere in the graph.  Those changes will disable the caching, but should not affect the output of the cycle.)

Each stream order satisfying the requirements in the calculation should produce the same output.  If different stream orders are producing different output then there is a problem with our model or the requirements.

To make cycles work correctly we need a means to get output from the delay node before input (for this block in time) is provided.
(In reply to Karl Tomlinson (back Jan 28 :karlt) from comment #13)
> The stream order should be cached where possible, but that is not the
> solution to this bug.  (Consider for example, the cycle / feedback loop
> running while changes are made elsewhere in the graph.  Those changes will
> disable the caching, but should not affect the output of the cycle.)

Agreed, I picked up the patch again to check my theory, and seeing it was close to being landable, I fixed a couple things.
 
> Each stream order satisfying the requirements in the calculation should
> produce the same output.  If different stream orders are producing different
> output then there is a problem with our model or the requirements.

I think we have some weirdness in the algorithm, that makes it dependent on the input order.

> To make cycles work correctly we need a means to get output from the delay
> node before input (for this block in time) is provided.

Yes, I think that's taken care of already [1].

http://dxr.mozilla.org/mozilla-central/source/content/media/AudioNodeStream.cpp?from=audionodestream#285
This works, but feels hacky.

Basically, it justs puts the "sinks" (MediaStreamDestinationNode,
AudioDestinationNode, etc.) at beginning of the array, so that the recursive
ordering algorithm works in "pull" mode, and the ordering is the same each time.

But this is just a sketch I think.
(In reply to Paul Adenot (:padenot) from comment #14)
> > To make cycles work correctly we need a means to get output from the delay
> > node before input (for this block in time) is provided.
> 
> Yes, I think that's taken care of already [1].
> 
> http://dxr.mozilla.org/mozilla-central/source/content/media/AudioNodeStream.
> cpp?from=audionodestream#285

That's not quite what I meant.
Consider processing for block n at time t with a cycle with a DelayNode:

Attempt 1: Process the DelayNode *before* other nodes in the cycle:

* The output from the DelayNode is now available to all nodes connected to its
  output, including those in the cycle.

* DelayNode input from nodes outside the cycle will already be available.

* However, DelayNode input from nodes within the cycle will be from nodes that
  have not yet processed block n.  Input from those nodes will be for block n-1.

Attempt 2: Process the DelayNode *after* other nodes in the cycles:

* The input to the DelayNode is now available from all nodes connected to its
  input, including those in the cycle.

* DelayNode output will be available to downstream nodes outside the cycle.

* However, DelayNode output for block n was not available for nodes in the
  cycle.  Those nodes received data from block n-1 instead of block n.

I think we need to set mLastChunks for the DelayNode *before* processing for other nodes in the cycle (or provide a different means of getting the output).  We then need to feed input into the delay node *after* processing for the other nodes in the cycle.
There is actually two issues in this bug:
- The topological sort we use to decide in which order we should process the streams should find a better ordering, independant on input order. Simply starting the algorithms from the sinks fixes that.
- We should then make sure the nodes get the right block. Attached is a stand alone web page that can help us do that (just change the content of the "dirac" function). It seems kind of okay, from my testing (with the patch applied), but I haven't thought about it enough.
(In reply to Paul Adenot (:padenot) from comment #17)
> There is actually two issues in this bug:
> - The topological sort we use to decide in which order we should process the
> streams should find a better ordering, independant on input order. Simply
> starting the algorithms from the sinks fixes that.

If the nodes receive and send the correct blocks, then is there a problem with the ordering?

Ordering is observable through ScriptProcessorNode, AnalyserNode, and other nodes that send events, but ordering is not specified.
(In reply to Karl Tomlinson (back Jan 28 :karlt) from comment #19)
> (In reply to Paul Adenot (:padenot) from comment #17)
> > There is actually two issues in this bug:
> > - The topological sort we use to decide in which order we should process the
> > streams should find a better ordering, independant on input order. Simply
> > starting the algorithms from the sinks fixes that.
> 
> If the nodes receive and send the correct blocks, then is there a problem
> with the ordering?
> 
> Ordering is observable through ScriptProcessorNode, AnalyserNode, and other
> nodes that send events, but ordering is not specified.

Well, that's the whole problem: the stream order, currently, depends on the stream order for the previous MSG run, (comment 9). This is a bug: the nodes _don't_ receive and send the correct blocks.
Blocks: 962548
I've written a test case for the Web Audio mochitest suite to test for distortion in feedback loops -- this bug seems to occur even when gain/delay are 0, so a feedback loop is set up with a gain and delay of 0 and the output is checked against a pure sine wave.
This allow the MSG to order the stream in a true "pull" fashion, as needed for
proper rendering of cycles. The distortion goes away, with this.
Attachment #8379793 - Flags: review?(roc)
This is similar to attachment 8366761 [details] but swaps the delay and gain nodes.

The black line is the actual output while the red line is expected - actual.

The patch of attachment 8379793 [details] [diff] [review] makes the loop delay consistent, but now always one block too long.

I have some WIP patches to separate delay buffer write and read so that read can happen before write (when delay > 1 block), if you are happy for me to take over.
(In reply to Paul Adenot (:padenot) from comment #22)
> This allow the MSG to order the stream in a true "pull" fashion, as needed
> for proper rendering of cycles. The distortion goes away, with this.

I don't understand the problem. UpdateStreamOrder should already ensure that a stream with no outputs is ordered after all of its input streams. Why is that not enough?
(In reply to Karl Tomlinson (:karlt) from comment #16)
> I think we need to set mLastChunks for the DelayNode *before* processing for
> other nodes in the cycle (or provide a different means of getting the
> output).  We then need to feed input into the delay node *after* processing
> for the other nodes in the cycle.

I agree with this.
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #24)
> (In reply to Paul Adenot (:padenot) from comment #22)
> > This allow the MSG to order the stream in a true "pull" fashion, as needed
> > for proper rendering of cycles. The distortion goes away, with this.
> 
> I don't understand the problem. UpdateStreamOrder should already ensure that
> a stream with no outputs is ordered after all of its input streams. Why is
> that not enough?

Because when you have a loop, nodes part of the loop are swapped (in the final ordering) when running the algorithm twice in a row. Since we (used to) reorder the streams each iteration, we would grab the wrong input chunk, and this provoked the distortion. We don't do that anymore, but the problem can still be triggered (if authors change the graph topology often enough to trigger enough reordering).

Karl, I'm happy for you to take over this. I'd rather have a fixed ordering that does not glitch for now, and then write a proper solution (or maybe your WIP in progress patches can make it soon?). I fully agree that comment 16 is the proper way to fix this. I'm just concerned by the fact that this problem is being reported to me over and over.
I have something working at
https://tbpl.mozilla.org/?tree=Try&rev=1316a1837bac
https://tbpl.mozilla.org/?tree=Try&rev=76b70b699a7d

but properly determining the number of output channels before knowing the number of input channels is really bug 857610.  I'll have a solution for that soon.
Assignee: paul → karlt
Depends on: 857610
Thank you, roc, for the suggestion to use two passes.
Perhaps it might be possible to do two different analyses during one traversal, but this is simpler.

If two cycles share a common path, they will now *both* be treated as cycles,
either by muting or by enforcing minimum delay.  Previously, marking one cycle
mHasBeenOrdered first could prevent detection of other cycles.
Attachment #8382713 - Flags: review?(roc)
Now that ProduceOutput doesn't necessarily produce output, ProcessInput might be a better name.
Attachment #8382714 - Flags: review?(roc)
Similarly for the AudioNodeEngine methods.
Attachment #8382715 - Flags: review?(paul)
Comment on attachment 8382713 [details] [diff] [review]
change stream ordering to get DelayNode echo output before supplying input

Review of attachment 8382713 [details] [diff] [review]:
-----------------------------------------------------------------

Basically, it's difficult to tell how this works, so some more precise documentation is needed.

::: content/media/MediaStreamGraph.cpp
@@ +531,5 @@
> +  OrderingState(int aFirstOrderingIndex) :
> +    stackPosition(UINT_MAX), orderingIndex(aFirstOrderingIndex) {};
> +  // Descending counter used to determine which streams on the stack are
> +  // included in cycles.
> +  unsigned stackPosition;

uint32_t

@@ +533,5 @@
> +  // Descending counter used to determine which streams on the stack are
> +  // included in cycles.
> +  unsigned stackPosition;
> +  // Ascending counter used to mark the order of streams.
> +  int orderingIndex;

int32_t. Also, use "m" prefix. Also, please give a precise description of the invariants here.

@@ +537,5 @@
> +  int orderingIndex;
> +};
> +
> +// Search depth-first upstream, marking the stream order for dependencies and
> +// this stream.

This comment is hard to understand. Please specify exactly what this does, I think that will really help make this code understandable.

@@ +677,5 @@
> +
> +  // Reference count changes on streams are atomic operations, so avoid
> +  // unnecessary changes.
> +  for (uint32_t i = sourceStreamCount; i < mFirstCycleBreaker; ++i) {
> +    while (1) {

while (true)

::: content/media/MediaStreamGraph.h
@@ +992,5 @@
>  
>    // The list of all inputs that are currently enabled or waiting to be enabled.
>    nsTArray<MediaInputPort*> mInputs;
>    bool mAutofinish;
> +  unsigned mCycleMarker;

uint32_t
Attachment #8382713 - Flags: review?(roc) → review-
Comment on attachment 8382712 [details] [diff] [review]
part 1: allow DelayNodeEngine to produce output before input

Review of attachment 8382712 [details] [diff] [review]:
-----------------------------------------------------------------

::: content/media/AudioNodeEngine.h
@@ +265,5 @@
>    }
> +  /**
> +   * Produce the next block of audio samples, before input is provided.
> +   * ProduceAudioBlock() will be called later, and it then should not change
> +   * aOutput.  This is used only for DelayNodeEngine in an echo loop.

s/echo/feedback/ to be more generic.
Attachment #8382712 - Flags: review?(paul) → review+
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #32)
> Comment on attachment 8382713 [details] [diff] [review]

> Basically, it's difficult to tell how this works, so some more precise
> documentation is needed.

Fair enough.  This was helpful in ironing out a bug with intersecting cycles.
It should make more sense now.

> ::: content/media/MediaStreamGraph.cpp
> @@ +531,5 @@
> > +  OrderingState(int aFirstOrderingIndex) :
> > +    stackPosition(UINT_MAX), orderingIndex(aFirstOrderingIndex) {};
> > +  // Descending counter used to determine which streams on the stack are
> > +  // included in cycles.
> > +  unsigned stackPosition;
> 
> uint32_t

> > +  // Ascending counter used to mark the order of streams.
> > +  int orderingIndex;
> 
> int32_t. Also, use "m" prefix. Also, please give a precise description of
> the invariants here.

I've added documentation to these members, particularly the former as there
are not many invariants directly involving the ordering index.  I've also
changed the names a little to highlight differences from the corresponding
processed stream variables.

The 'm' prefix is useful in classes with methods, so as to distinguish from
local (automatic) variables.  If there are no methods in the class, then all
uses of the members involve pointer-to-member operators and so the members
never look like locals.

https://groups.google.com/forum/#!searchin/mozilla.dev.platform/style$20pod$20m/mozilla.dev.platform/EYCylYteP-I/whbDMW72TC8J
almost said something similar, and I don't remember any disagreement about
this point.  However, 'm' does at least make it clear that these are not class
static variables.

> ::: content/media/MediaStreamGraph.h

> > +  unsigned mCycleMarker;
> 
> uint32_t

You've requested some changes to integer types, but I don't know why.

orderingIndex is used with nsTArray<>::index_type, so I've changed it and
ProcessedMediaStream::mOrderingIndex to uint32_t to match that.

stackPosition and mCycleMarker, however, are not used as nsTArray indices, and
so are free from the quirks of nsTArray.  I assume you are not requesting the
special-length type because you are concerned about future memory usage or
packing of member variables in ProcessedMediaStream.

Usually I prefer the regular unsigned int for unsigned variables when nothing
larger is required because then we know that integral promotion won't convert
it to a signed type, possibly leading to unexpected results (cf. bug 651309).
However, that shouldn't be a problem here, so I don't think there is much harm
in using uint32_t.
Attachment #8382713 - Attachment is obsolete: true
Attachment #8384317 - Flags: review?(roc)
Attachment #8384317 - Attachment description: part 3 v2: change stream ordering to get DelayNode echo output before supplying input → part 2 v2: change stream ordering to get DelayNode echo output before supplying input
(In reply to Karl Tomlinson (:karlt) from comment #34)
> The 'm' prefix is useful in classes with methods, so as to distinguish from
> local (automatic) variables.  If there are no methods in the class, then all
> uses of the members involve pointer-to-member operators and so the members
> never look like locals.

I don't think this distinction is worth making. It means that as soon as you add a single member function to the class you should rename all the members, which would be a real pain, so it just seems like trouble.

> > ::: content/media/MediaStreamGraph.h
> 
> > > +  unsigned mCycleMarker;
> > 
> > uint32_t
> 
> You've requested some changes to integer types, but I don't know why.
> 
> orderingIndex is used with nsTArray<>::index_type, so I've changed it and
> ProcessedMediaStream::mOrderingIndex to uint32_t to match that.
> 
> stackPosition and mCycleMarker, however, are not used as nsTArray indices,
> and
> so are free from the quirks of nsTArray.  I assume you are not requesting the
> special-length type because you are concerned about future memory usage or
> packing of member variables in ProcessedMediaStream.
> 
> Usually I prefer the regular unsigned int for unsigned variables when nothing
> larger is required because then we know that integral promotion won't convert
> it to a signed type, possibly leading to unexpected results (cf. bug 651309).
> However, that shouldn't be a problem here, so I don't think there is much
> harm
> in using uint32_t.

I prefer to use fixed-length types in most situations since it ensures overflow will happen under the same conditions for 32bit and 64bit platforms.
Comment on attachment 8384317 [details] [diff] [review]
part 2 v2: change stream ordering to get DelayNode echo output before supplying input

Review of attachment 8384317 [details] [diff] [review]:
-----------------------------------------------------------------

::: content/media/MediaStreamGraph.cpp
@@ +682,5 @@
> +  // not in cycles, and there may be more than one DelayNode in a cycle, so we
> +  // must detect all DelayNodes in cycles before breaking the cycles.  We
> +  // don't want to analyse every cycle to see whether it contains a delay
> +  // node, so first find delay nodes in cycles, then break at DelayNodes, and
> +  // reorder again.

Your comments are good, but the code is still more complex than I was hoping for.

How about we implement this by explicitly using Tarjan's algorithm?
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

A node is in a cycle iff it is in a strongly-connected component of size > 1. Tarjan's algorithm topologically orders the SCCs for us so in the absence of cycles it computes a valid order.

When we identify an SCC of size > 1, we can check it for DelayNodes and make them cycle-breakers. Then, we can do a DFS within the SCC to see if we've broken all cycles, giving the correct order for those nodes if we have.

It's still going to be a bit complicated but I think being explicit about the algorithms we're using will make this more maintainable.

::: content/media/MediaStreamGraph.h
@@ +988,5 @@
> +  struct OrderingState;
> +  uint32_t SetOrderUpstream(OrderingState *orderingState);
> +  bool HasBeenOrdered() { return mOrderingIndex != uint32_t(-1); }
> +  // Returns true if this stream receives input, directly or indirectly, from
> +  // any streams on the stack.

Add "See MediaStreamGraphImpl::UpdateStreamOrder".
Attachment #8384317 - Flags: review?(roc) → review-
Attachment #8382715 - Flags: review?(paul) → review+
Landed the method renames and DelayNodeEngine refactoring to minimize conflicts with other developments while investigating roc's proposal.

https://hg.mozilla.org/integration/mozilla-inbound/rev/5678323e54ad
https://hg.mozilla.org/integration/mozilla-inbound/rev/597c9e0f6c7e
https://hg.mozilla.org/integration/mozilla-inbound/rev/aa3c47aed9e9
Keywords: leave-open
Attachment #8382712 - Flags: checkin+
Attachment #8382714 - Flags: checkin+
Attachment #8382715 - Flags: checkin+
Blocks: 991251
Original report still reproduces in Firefox 32.0a1 nightly. Is this still being worked on? It's holding back enabling createMediaElementSource() in Firefox in Construct 2, a major HTML5 game engine.
The issue being addressed here is the distortion from a feedback loop.
That is unrelated to createMediaElementSource().

I filed bug 937962 on an issue related to createMediaElementSource(), but the main issue in the testcase there has been addressed.

If there is still distortion from createMediaElementSource(), then would you be able to file a new bug with steps to reproduce, please?
Any news on this? Delay node still causes distortion.
The current ordering algorithm sometimes adds and removes thread-safe
references unnecessarily.  We could jump through hoops to swap array elements or use forget() and alreadyAddRefed() in order to avoid refcount manipulation, but this is more complicated than the benefits from provided by the RAII class.  The RAII is already complicated by the fact that I happens after and on a different thread to RA.

Eventually we should probably replace mStreams with a linked list to reduce
the cost of destroying the graph from n^2 to n, so this is a step in that
direction.
Attachment #8452103 - Flags: review?(roc)
See http://www.timl.id.au/?p=327 for a nice description of how this
cycle detection algorithm works.

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #36)
> Comment on attachment 8384317 [details] [diff] [review]
> How about we implement this by explicitly using Tarjan's algorithm?
> http://en.wikipedia.org/wiki/
> Tarjan%27s_strongly_connected_components_algorithm

Thanks for the link.  I didn't know this was called Tarjan's algorithm.

The previous patch differed from Tarjan's algorithm in that it used a sub-tree
DFS search to find the SCC when its root was popped from the DFS stack.  This
version tracks these in an explicit stack, as in Pearce's algorithm, which
removes some of the complexity.

The previous version followed the recursive nature of Tarjan's algorithm but
an iterative implementation is better for potentially large graphs on child
threads.  Using linked lists makes the input iteration for iterative DFS simple, and will be useful for addressing n^2 destruction.

> A node is in a cycle iff it is in a strongly-connected component of size >
> 1.

A node in an SCC of size 1 may either be in a cycle or not, and so Tarjan's
algorithm doesn't distinguish.  Both are SCCs of size 1, but a small
variation, retained from the previous patch, handles that case.

> When we identify an SCC of size > 1, we can check it for DelayNodes and make
> them cycle-breakers. Then, we can do a DFS within the SCC to see if we've
> broken all cycles, giving the correct order for those nodes if we have.

This was a nice improvement, thanks.
Attachment #8384317 - Attachment is obsolete: true
Attachment #8452108 - Flags: review?(roc)
Comment on attachment 8452108 [details] [diff] [review]
part 6 (part 2 v3): change stream ordering to get DelayNode echo output before supplying input

Review of attachment 8452108 [details] [diff] [review]:
-----------------------------------------------------------------

Gnarly!

::: content/media/AudioNodeStream.cpp
@@ +490,5 @@
> +{
> +  MOZ_ASSERT(mEngine->OutputCount() == 1,
> +             "DelayNodeEngine output count should be 1");
> +  MOZ_ASSERT(!InMutedCycle(), "DelayNodes should break cycles");
> +  mLastChunks.SetLength(1);

We should assert around here that this is actually for a DelayNode.

::: content/media/MediaStreamGraph.cpp
@@ +577,5 @@
> +  // whether streams in SCCs of size 1 are in a cycle and (b) to re-run the
> +  // algorithm over SCCs with breaks at DelayNodes.
> +  //
> +  // [1] https://github.com/scipy/scipy/blob/e2c502fca/scipy/sparse/csgraph/_traversal.pyx#L582
> +  // [2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1707

Might want to link to the blog here too.

@@ +713,5 @@
> +        mStreams[mFirstCycleBreaker] = ns;
> +      }
> +    }
> +    auto after_scc = next;
> +    while((next = static_cast<ProcessedMediaStream*>(sccStack.popFirst()))

space after 'while'
Attachment #8452108 - Flags: review?(roc) → review+
Without this, UpdateOutputBlock() would be called from ProcessBlock(),
giving the wrong minimum delay.
Attachment #8457704 - Flags: review?(roc)
Attachment #8457703 - Flags: review?(paul) → review+
https://hg.mozilla.org/mozilla-central/rev/04019eb4d1b5
https://hg.mozilla.org/mozilla-central/rev/013907ce316a
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla33
Depends on: 1041466
Verified fixed in nightly 34. Thanks for the good work.
Blocks: 1057073
Depends on: CVE-2014-8640
You need to log in before you can comment on or make changes to this bug.