Closed Bug 766331 Opened 9 years ago Closed 9 years ago

nsOggReader::EndRangeTime O(N^2) on invalid data


(Core :: Audio/Video, defect)

Not set





(Reporter: rillian, Assigned: rillian)



(2 files, 2 obsolete files)

Poorly constructed files can result in nsOggReader scanning most of the file looking for a valid granulepos. This results in playback hanging for a significant time on long files, with Firefox using 100% cpu.
Attached file problem file generator
Problem file generator by Greg Maxwell. To make an example, comment out the ogg_page_checksum call on line 92 and run the output for a few cycles. This will generate a file with valid ogg data at the beginning, but append copies with invalid crc values which libogg with reject.

Example problem files produced this way by Greg Maxwell:

The same issue occurs with both Vorbis and Opus; likely all Ogg-container files are affected. The long-running scan happens inside RangeEndTime. Likely we should limit how far that function is willing to hunt for a seek point.
The problem here is that we rely on crc values from valid pages to know when we're hit data we've seen before. Since these files end with no value pages, we scan them for a sync point, back off 5k, and scan them all again, using quadratic time to find the end of the valid data.

Switching to exponential rather than linear backup allows playback to start instantly, for example.
Summary: nsOggReader will scan entire file for granulepos values → nsOggReader::EndRangeTime O(N^2) on invalid data
(In reply to Ralph Giles (:rillian) from comment #2)
> Switching to exponential rather than linear backup allows playback to start
> instantly, for example.

You're talking about changing the mustBackOff loop in EndRangeTime? If you backed off this way you'd want to do a linear scan after the sync to ensure you get the last page with a granulepos in the range, else you won't be getting the last granulepos in the range.

I don't think this is worth spending much (perhaps any) time fixing this, given that Ogg isn't our focus moving forward, and this is only an issue for invalid files.
Attached patch proposed fix (obsolete) — Splinter Review
Proposed fix. This restores O(N) when scanning backward from the end. There's still a pause, but it's much better. Does this look like a useful direction?
Attachment #634672 - Flags: feedback?(cpearce)
Comment on attachment 634672 [details] [diff] [review]
proposed fix

Review of attachment 634672 [details] [diff] [review]:

I think that approach is fine.
Attachment #634672 - Flags: feedback?(cpearce) → feedback+
Attached patch cleaned up patch (obsolete) — Splinter Review
Updated patch. This is less aggressive, but won't fail to read long pages at the end of the file.

There are still some problems with the invalid files after applying this patch, but it addresses the quadratic time issue, reducing the time after seek from minutes to seconds.

With the opus example there's a several second delay after any seek while it searches the file again, and playback can become completely stuck with the vorbis example. Nevertheless I'm happy with the mitigation it provides. There are no great solutions here; we can't bisection-search to find the last valid page in a sea of garbage data, so we have to either scan or give up.
Attachment #634672 - Attachment is obsolete: true
Media tests are green. Requesting review for landing.
Assignee: nobody → giles
Attachment #635516 - Flags: review?(cpearce)
Attached patch cleaned up patchSplinter Review
Sorry, forgot to update with the latest version of the patch. This is like the previous one, but only reads on maxOggPageLength, not two. We would need two if we were doing random access, in case we land in the middle of the first of two long pages, but since we're scanning backward, one page length is sufficient.

This one is
Attachment #635516 - Attachment is obsolete: true
Attachment #635516 - Flags: review?(cpearce)
Attachment #636353 - Flags: review?(cpearce)
Attachment #636353 - Flags: review?(cpearce) → review+
Thanks, Chris. Ready to land.

I've not added a test for this; the issue is with corrupt files and must be several MB to make the hang obvious.
Keywords: checkin-needed
Media tests on the try push are green.
Pushed to mozilla-inbound:
Flags: in-testsuite-
Keywords: checkin-needed
Target Milestone: --- → mozilla16
Closed: 9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.