Bug 179690 - [MSE] Use correct range end checks in sourceBufferPrivateDidReceiveSample()
Summary: [MSE] Use correct range end checks in sourceBufferPrivateDidReceiveSample()
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Media (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2017-11-14 13:28 PST by Alicia Boya García
Modified: 2017-12-01 21:40 PST (History)
5 users (show)

See Also:


Attachments
Patch (15.66 KB, patch)
2017-11-14 13:35 PST, Alicia Boya García
no flags Details | Formatted Diff | Diff
Patch (17.90 KB, patch)
2017-12-01 09:26 PST, Alicia Boya García
no flags Details | Formatted Diff | Diff
Patch (18.91 KB, patch)
2017-12-01 16:21 PST, Alicia Boya García
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Alicia Boya García 2017-11-14 13:28:21 PST
The Coded Frame Processing algorithm as defined in
https://www.w3.org/TR/media-source/#sourcebuffer-coded-frame-processing states:

1.14. Remove existing coded frames in track buffer:
 -> If highest end timestamp for track buffer is not set:
       [...]
 -> If highest end timestamp for track buffer is set and less than or 
    equal to presentation timestamp:
       Remove all coded frames from track buffer that have a 
       presentation timestamp greater than or equal to highest end 
       timestamp and less than frame end timestamp.

Note the removal range is closed-open [a, b). WebKit is actually removing
frames using an open-closed range (a, b], which causes frames not to be removed
in situations where they should and frames to be removed in situations when
they should not.
Comment 1 Alicia Boya García 2017-11-14 13:35:20 PST
Created attachment 326918 [details]
Patch
Comment 2 Jer Noble 2017-11-14 14:02:38 PST
Thanks for writing these tests. But I'm curious what the behavior of this change is when faced with appends like:

// PTS, duration
[0, 2]
[2, 2]
[1, 2]

I would argue that the correct results would be:

buffered.length == 1
buffered.start(0) == 1
buffered.end(0) == 3

I'm not sure what this patch's results would be, as it stands.
Comment 3 Jer Noble 2017-11-14 14:13:28 PST
(In reply to Jer Noble from comment #2)
> Thanks for writing these tests. But I'm curious what the behavior of this
> change is when faced with appends like:
> 
> // PTS, duration
> [0, 2]
> [2, 2]
> [1, 2]
> 
> I would argue that the correct results would be:
> 
> buffered.length == 1
> buffered.start(0) == 1
> buffered.end(0) == 3
> 
> I'm not sure what this patch's results would be, as it stands.

I modified the test from your patch to issue appends in the order I specified above, and when run against ToT (i.e., without your fix), it gets:

{PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({1000/1000 = 1.000000}), DTS({1000/1000 = 1.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
EXPECTED (sourceBuffer.buffered.length == '1') OK
EXPECTED (sourceBuffer.buffered.start(0) == '0') OK
EXPECTED (sourceBuffer.buffered.end(0) == '3') OK

So it removes the second sample, but not the first, and leaves overlapping samples in the track buffer, which I think is incorrect.
Comment 4 Jer Noble 2017-11-14 14:28:44 PST
So I think I remember why we no longer seem to use the SampleIsLessThanMediaTimeComparator objects. We used to, when this was originally implemented, by using std::lower_bound(m_samples.begin(), m_samples.end(), SampleIsGreaterThanMediaTimeComparator).  But std::lower_bound doesn't actually do a binary search; it can't, because map::iterators aren't random access.  map::lower_bound does do a binary search, but it can't take a comparator, because it can't guarantee that the map is sorted in comparator order.  So we re-wrote all the algorithms to use the map::lower_bound (et. all.) algorithms, since those are O(log(n)) rather than the O(n) of the std::lower_bound functions.

I think we can still implement this using the map functions though, even accounting for duration.

Given a sample whose PTS is /pS/ and whose duration is /d/ and whose presentation end time is /pS/ + /d/ = /pE/, the end of the removal range is the first sample whose PTS > /pE/, and the start of the removal range is the first sample whose /pE'/ > /pS/.  Finding the end of the range is easy, it's map.upper_bound(/pE/). Finding the start is harder, because it requires a comparator.  But because our sample map is (supposed to be) non-overlapping, we can just find the first sample whose PTS > /ps/, and then look at the previous sample. If its PTS + duration > /pS/, the previous sample is the start, otherwise the current sample is.
Comment 5 Alicia Boya García 2017-11-14 15:00:52 PST
(In reply to Jer Noble from comment #2)
> Thanks for writing these tests. But I'm curious what the behavior of this
> change is when faced with appends like:
> 
> // PTS, duration
> [0, 2]
> [2, 2]
> [1, 2]
> 
> I would argue that the correct results would be:
> 
> buffered.length == 1
> buffered.start(0) == 1
> buffered.end(0) == 3
> 
> I'm not sure what this patch's results would be, as it stands.

It would produce the results the spec says, whether good or bad...

In this case it would depend on whether the DTSs are consecutive so the frames are considered part of the same Coded Frame Group.

If they are all part of the same Coded Frame Group, none of the conditions would evaluate true so no frames would be deleted:

1.13. If last decode timestamp for track buffer is unset (false) ...
1.14.a. If highest end timestamp for track buffer is not set (false).
1.14.b. If highest end timestamp for track buffer is set (true) and less than or equal to presentation timestamp (false).

{PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({2000/1000 = 2.000000}), DTS({1000/1000 = 1.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({1000/1000 = 1.000000}), DTS({2000/1000 = 2.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}

If at least the last frame starts a new Coded Frame Group (e.g. by having a lesser DTS than the previous one):

1.13. (enters in the condition but the frame is not removed because its PTS is not within the 1 microsecond window [PTS, PTS+1µs) ).
1.14.a. If highest end timestamp for track buffer is not set: (true)
  Remove all coded frames from track buffer that have a presentation timestamp greater than or equal to presentation timestamp and less than frame end timestamp. (removes the previous frame)
1.14.b. If highest end timestamp for track buffer is set (false) ...

{PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({1000/1000 = 1.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
Comment 6 Jer Noble 2017-11-14 16:48:22 PST
(In reply to Alicia Boya García from comment #5)
> (In reply to Jer Noble from comment #2)
> > Thanks for writing these tests. But I'm curious what the behavior of this
> > change is when faced with appends like:
> > 
> > // PTS, duration
> > [0, 2]
> > [2, 2]
> > [1, 2]
> > 
> > I would argue that the correct results would be:
> > 
> > buffered.length == 1
> > buffered.start(0) == 1
> > buffered.end(0) == 3
> > 
> > I'm not sure what this patch's results would be, as it stands.
> 
> It would produce the results the spec says, whether good or bad...
> 
> In this case it would depend on whether the DTSs are consecutive so the
> frames are considered part of the same Coded Frame Group.
> 
> If they are all part of the same Coded Frame Group, none of the conditions
> would evaluate true so no frames would be deleted:
> 
> 1.13. If last decode timestamp for track buffer is unset (false) ...
> 1.14.a. If highest end timestamp for track buffer is not set (false).
> 1.14.b. If highest end timestamp for track buffer is set (true) and less
> than or equal to presentation timestamp (false).
> 
> {PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 =
> 2.000000}), flags(1), generation(0)}
> {PTS({2000/1000 = 2.000000}), DTS({1000/1000 = 1.000000}),
> duration({2000/1000 = 2.000000}), flags(1), generation(0)}
> {PTS({1000/1000 = 1.000000}), DTS({2000/1000 = 2.000000}),
> duration({2000/1000 = 2.000000}), flags(1), generation(0)}
> 
> If at least the last frame starts a new Coded Frame Group (e.g. by having a
> lesser DTS than the previous one):
> 
> 1.13. (enters in the condition but the frame is not removed because its PTS
> is not within the 1 microsecond window [PTS, PTS+1µs) ).
> 1.14.a. If highest end timestamp for track buffer is not set: (true)
>   Remove all coded frames from track buffer that have a presentation
> timestamp greater than or equal to presentation timestamp and less than
> frame end timestamp. (removes the previous frame)
> 1.14.b. If highest end timestamp for track buffer is set (false) ...
> 
> {PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 =
> 2.000000}), flags(1), generation(0)}
> {PTS({1000/1000 = 1.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000
> = 2.000000}), flags(1), generation(0)}

Yuck. I really don't like the idea of having overlapping samples in this case. I would propose that we willfully violate the spec in this case in one of two ways:

Option 1: Remove the overlapping sample.  This obeys (I believe) the spirit of the specification and ensures that no samples can overlap inside the track buffer.

Option 2: Truncate the duration of the overlapping sample.  This solves the overlapping sample problem without actually removing the sample itself.  Has the possible benefit of matching GStreamer's behavior, where duration is ignored anyway.

Option 1 would be easier to implement; it's a cross platform change to the sample append code.

Option 2 would require changes to MediaSample and all its derived classes to add a new virtual "setDuration()" method.

WDYT?
Comment 7 Alicia Boya García 2017-11-14 18:04:02 PST
(In reply to Jer Noble from comment #6)

I'd argue for removing samples over modifying them, unless we have a convincing use case for doing otherwise.
Comment 8 Alicia Boya García 2017-11-14 18:45:46 PST
If we are going to diverge from spec-defined behavior, here is an idea: drop
all three removal steps (1.13, 1.14a and 1.14b) and replace them with this
single one:

Remove every existing frame in the track buffer whose presentation range
intersects with the range [PTS+1µs, PTS+DUR-1µs).

I think that is much simpler to understand and makes for more user-predictable
behavior yet still takes JS float conversion effects into account and
algorithmic complexity need not be affected... the most common case should be
still easy to keep O(1) and there should be no much problem in getting the
O(log(n)) search to work (just look at presentation end for the upper bound,
which should be no problem since the ordering of samples is the same whether we
consider PTS or presentation end because both values are monotonically
increasing...).

This simple rule should handle all the real cases that are handled by the
current approach just fine and fix those that are unspecified by the current
MSE spec.
Comment 9 Alicia Boya García 2017-12-01 09:26:32 PST
Created attachment 328100 [details]
Patch
Comment 10 Jer Noble 2017-12-01 12:12:58 PST
Comment on attachment 328100 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=328100&action=review

r=me with nit:

> Tools/TestWebKitAPI/Tests/WebCore/SampleMap.cpp:-232
> -TEST_F(SampleMapTest, findSamplesWithinPresentationRange)
> -{
> -    auto& presentationMap = map.presentationOrder();
> -    auto iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(0, 1), MediaTime(1, 1));
> -    EXPECT_EQ(MediaTime(1, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_EQ(MediaTime(2, 1), iterator_range.second->second->presentationTime());
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(1, 2), MediaTime(3, 2));
> -    EXPECT_EQ(MediaTime(1, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_EQ(MediaTime(2, 1), iterator_range.second->second->presentationTime());
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(9, 1), MediaTime(21, 1));
> -    EXPECT_EQ(MediaTime(11, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.second);
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(-1, 1), MediaTime(0, 1));
> -    EXPECT_EQ(MediaTime(0, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_EQ(MediaTime(1, 1), iterator_range.second->second->presentationTime());
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(10, 1), MediaTime(21, 2));
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.first);
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.second);
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(20, 1), MediaTime(21, 1));
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.first);
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.second);
> -}
> -

Please restore this test (with the new name and possibly new values) before landing.
Comment 11 Alicia Boya García 2017-12-01 13:05:14 PST
On an unrelated note...

Following the conversation from earlier, I've been experimenting with a new frame removal algorithm for some time, but I found it to be non-trivial because of unrelated bugs popping out from many parts of the code and the underlying libraries.

This patch is the same as before, with that test file fixed by removing the references to the deleted function.

Efforts to improve on the algorithm proposed by the W3C can be tracked in a different bugzilla issue.
Comment 12 Alicia Boya García 2017-12-01 16:21:52 PST
Created attachment 328182 [details]
Patch
Comment 13 WebKit Commit Bot 2017-12-01 21:39:34 PST
Comment on attachment 328182 [details]
Patch

Clearing flags on attachment: 328182

Committed r225442: <https://trac.webkit.org/changeset/225442>
Comment 14 WebKit Commit Bot 2017-12-01 21:39:36 PST
All reviewed patches have been landed.  Closing bug.
Comment 15 Radar WebKit Bug Importer 2017-12-01 21:40:19 PST
<rdar://problem/35812250>