View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0001146||OpenMPT||Playback Compatibility||public||2018-09-22 06:28||2020-10-25 15:43|
|Reporter||manx||Assigned To||Saga Musix|
|Product Version||OpenMPT 1.28.00.* (old testing)|
|Target Version||OpenMPT 1.30 / libopenmpt 0.6 (goals)|
|Summary||0001146: Handle infinite loops|
libopenmpt, by default, should never enter an infinite playback loop, even if the module itself contains an infinite loop using pattern loops or pattern position jumps and pattern break to row.
|Tags||No tags attached.|
|Has the bug occurred in previous versions?|
|Tested code revision (in case you know it)|
rough sketch of a possible algorithm/implementation
commands (position jumps have implicit loop count 1, unless song has repeat-forever set, in which case they have infinite loop count), sorted in a vector for space and lookup efficiency,
memory should be pre-allocated when loading the file (or when editing in the tracker))
the algorithm guarantees termination by the following principle: the loop count for the latest (latest in song order-list + row ordering) backwards loop/jump is always strictly
monotonically descreasing, and earlier loop counts are only ever reset to their original (thus maximum) value. ordering loop counts in this order from song end to song start, interpreting
every loopcount as a digit and interpreting the concatenated number as an integer ALWAYS decreases the integer towards zero on every backward loop/jump. when it reaches 0, no further
backward loop/jump will ever be exectuted. termination is guaranteed by construction.
violate invariants even if this assumption does not hold. the worst case outcome is too short playback in truely extremely weird situations (because the loop count is decreased even if in
theory it might be possible that the target on the next occasion might be something entirely different, which would be desirable to execute).
in default libopenmpt playback mode (i.e. not allowing any infinite loops at all), this algorithm must be followed without exceptions. in repeat-song-n-times mode, backwardpositionjump
commands are initialized with n+1.
it can even support a mode with current infinite loop behaviour:
i think we can even completely remove all traces of rowvisitor.
Here's an initial implementation following the existing RowVisitor approach. It's far from optimal with regards to memory allocations, it's just a first try to check the feasibility of this idea.
The advantage of this approach is that it is completely independent of any pattern break / jump / loop handling and can thus be agnostic of those events and as a consequence of any compatibility quicks.
handle-infinite-loops.7z (8,500 bytes)
This implementation avoids memory allocations for every row on which no pattern loop is played by using
This means that in the most common case (no pattern loops in module), there won't be any extra allocations, but as this uses a
The next step could be to further optimize the common case from "variant<bool, set> inside vector inside vector" to "variant<bitset, set inside vector> inside vector". This would allow for the most common case (no pattern loops in a pattern) to consume much less memory and not even require an extra allocation outside of the order vector, for each pattern where the bitset is large enough (e.g. 256 entries would be enough for most modules).
handle-infinite-loops-v2.7z (10,976 bytes)
New tweaked version that is allocation-free during playback for most modules - unanticipated pattern loop quirks may still force some memory allocation, but that was the case with the original RowVisitor too.
Note that all new implementations have one common issue: While the accurate estimation of pattern loops is very desirable, it also opens an easy Denial of Service possibility: Even a sub-kilobyte IT file may contain nested pattern loops that would cause 16^64 pattern loop executions, which is obviously an infinity. libopenmpt will by default scan the length of all modules for subsong detection, so it will effectively lock up that thread forever.
I think it is required to put some arbitrary (maybe even configurable) limit on pattern loop evaluation in the context of length calculation. For example, this limit could be a number of rows since the player has been inside any sort of pattern loop. The limit should be a couple thousand of rows to be sure that no real-world module will ever be hit by this. If the limit is hit, libopenmpt could return infinity for song duration.
handle-infinite-loops-v3.7z (11,695 bytes)
Proposed workaround and some evil files that are disproportionally long compared to their byte size due to nested loops.
handle-infinite-loops-v4.7z (12,006 bytes)
evil-loops.7z (393 bytes)
More tweaking and optimizations; now the RowVisitor also handles the ProTracker Row Delay + Pattern Break quirk consistently for both regular playback and GetLength.
handle-infinite-loops-v5.7z (13,134 bytes)
Previous patch accidentally inverted a min/max, breaking pre-allocation
handle-infinite-loops-v6.7z (13,419 bytes)
While a variant closer to what is described in the first comment might be possible, I think it comes with a set of disadvantages that RowVisitor doesn have:
On the other hand, extending RowVisitor with the loop state logic makes integration in the existing code very easy, and it can also be reasoned similarly easily that it will always terminate.
This is the state against current trunk with some minor updates here and there. I think this is now in a pretty much optimal state and I suggest to apply it as soon as possible to give it some thorough testing. For modules that have no pattern loops at all, memory consumption and allocation behaviour will be pretty much identical (in fact, a bit less memory will be consumed because the list of last visited rows no longer exists). For "normal" pattern loops as they will be found in most modules (trivial nesting that doesn't exploit any quirks), the code is allocation-free during playback. Only for complex modules that really try to exploit pattern loops (such as Black Queen) there will be some allocations during playback, but that was already the case with the old implementation, so this is not a new issue.
While some of those allocations could be avoided, it would make the implementation much more complex and error-prone because format-specific playback logic would have to be added to the pre-allocation code. The same would be true for an implementation that only looks at the jumps themselves, with the difference that it wouldn't work at all without this format-specific knowledge.
handle-infinite-loops-v7.7z (13,772 bytes)
|2018-09-22 06:28||manx||New Issue|
|2018-09-23 09:56||manx||Priority||normal => urgent|
|2018-09-23 09:56||manx||Severity||major => block|
|2018-09-23 09:56||manx||Target Version||OpenMPT 1.29.01.00 / libopenmpt 0.5.0 (upgrade first) => libopenmpt 0.4 (goals)|
|2018-09-24 11:25||manx||Target Version||libopenmpt 0.4 (goals) => OpenMPT 1.29.01.00 / libopenmpt 0.5.0 (upgrade first)|
|2019-01-24 12:07||manx||Note Added: 0003825|
|2019-02-28 20:40||Saga Musix||Relationship added||related to 0001206|
|2019-03-01 14:12||manx||Note Edited: 0003825||View Revisions|
|2019-05-27 06:54||manx||Relationship added||related to 0000959|
|2020-01-05 10:43||manx||Target Version||OpenMPT 1.29.01.00 / libopenmpt 0.5.0 (upgrade first) => OpenMPT 1.30 / libopenmpt 0.6 (goals)|
|2020-05-10 09:04||manx||Priority||urgent => high|
|2020-05-28 11:02||manx||Note Added: 0004352|
|2020-10-17 19:40||Saga Musix||Note Added: 0004472|
|2020-10-17 19:40||Saga Musix||File Added: handle-infinite-loops.7z|
|2020-10-17 19:47||Saga Musix||Note Edited: 0004472||View Revisions|
|2020-10-17 22:32||Saga Musix||Note Added: 0004473|
|2020-10-17 22:32||Saga Musix||File Added: handle-infinite-loops-v2.7z|
|2020-10-17 22:36||Saga Musix||Note Edited: 0004473||View Revisions|
|2020-10-17 22:36||Saga Musix||Note Edited: 0004473||View Revisions|
|2020-10-19 21:35||Saga Musix||Assigned To||=> Saga Musix|
|2020-10-19 21:35||Saga Musix||Status||new => assigned|
|2020-10-20 20:44||Saga Musix||Note Added: 0004483|
|2020-10-20 20:44||Saga Musix||File Added: handle-infinite-loops-v3.7z|
|2020-10-20 21:15||Saga Musix||Note Added: 0004484|
|2020-10-20 21:15||Saga Musix||File Added: handle-infinite-loops-v4.7z|
|2020-10-20 21:15||Saga Musix||File Added: evil-loops.7z|
|2020-10-23 16:45||Saga Musix||Note Added: 0004485|
|2020-10-23 16:45||Saga Musix||File Added: handle-infinite-loops-v5.7z|
|2020-10-23 22:53||Saga Musix||Note Added: 0004486|
|2020-10-23 22:53||Saga Musix||File Added: handle-infinite-loops-v6.7z|
|2020-10-23 23:38||Saga Musix||Note Added: 0004487|
|2020-10-25 15:43||Saga Musix||Note Added: 0004489|
|2020-10-25 15:43||Saga Musix||File Added: handle-infinite-loops-v7.7z|