View Issue Details

IDProjectCategoryView StatusLast Update
0001146OpenMPTPlayback Compatibilitypublic2020-11-15 21:32
Reportermanx Assigned ToSaga Musix  
PriorityhighSeverityblockReproducibilityalways
Status assignedResolutionopen 
Product VersionOpenMPT 1.28.00.* (old testing) 
Target VersionOpenMPT 1.30 / libopenmpt 0.6 (goals) 
Summary0001146: Handle infinite loops
Description

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.

TagsNo tags attached.
Has the bug occurred in previous versions?
Tested code revision (in case you know it)

Relationships

related to 0001206 resolvedSaga Musix Odd behavior when seeking through this module in libopenmpt 
related to 0000959 assignedSaga Musix Incorrect handling of simultaneous pattern loop and position jump/pattern break/pattern delay commands 
related to 0001387 closed Infinite song loop at the end of module gom_jabbar_end 

Activities

manx

manx

2019-01-24 12:07

administrator   ~0003825

Last edited: 2019-03-01 14:12

View 2 revisions

rough sketch of a possible algorithm/implementation

in playstate:

  1. store a counter per row per channel, initialized with the loop count of the loop command, invalid if none. (i.e. store [order,row,chn,loopcount] for all loop/backwardpositionjump

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))

  1. reset loop counts for patternloops on pattern change if not position jumping
  2. when looping, decrease that counter and reset all counters that are jumped-over-backwards to their original loop count value.
  3. done. this implements a proper (implicit) stack for all loopcounters. song will terminate, always. getlength does not need to estimate loops anymore but can calculate them precisely.

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.

assumptions:

  • algorithm is compatible with weird format quirks (i do not see why it shouldnt be, though)
  • a backwards position jump in a particular order/row position always targets the same row in the jumped-to pattern (which as far as i can see is true, even for FT2). things will not

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.

memory requirements:

  • rowvisior: O(num_orders * max(rows_per_pattern) * sizeof(bool))
  • loopcountstacks: O(num_orders * max(num_loopjumpcommands_per_pattern) * sizeof(int))

runtime complexity:

  • rowvisitor: O(num_looped_rows) per loop, amortized O(1)
  • loopcountstacks: O(max(num_loopjumpcommands_per_pattern)+log(num_loops_per_song)) per loop, amortized O(log(num_loops_per_song))

it can even support a mode with current infinite loop behaviour:

  • on loop, reset not only the jumped-over loop counts, but instead reset all but the one currently executing, even the ones later in the pattern.

i think we can even completely remove all traces of rowvisitor.

manx

manx

2020-05-28 11:02

administrator   ~0004352

https://forum.openmpt.org/index.php?topic=6367.0

Saga Musix

Saga Musix

2020-10-17 19:40

administrator   ~0004472

Last edited: 2020-10-17 19:47

View 2 revisions

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.

Saga Musix

Saga Musix

2020-10-17 22:32

administrator   ~0004473

Last edited: 2020-10-17 22:36

View 3 revisions

This implementation avoids memory allocations for every row on which no pattern loop is played by using variant<bool, set>: bool=false equals empty set, bool=true equals set with one trivial entry: all loop counts are zero.

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 std::variant we still pay the space of a std::set on each row.

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).
Given a 64-bit build, any pattern without loops that is smaller than 256 rows would consume only 36 bytes in total instead of 32 bytes per row. For a module like Beyond The Network this would mean the memory usage is around 25KB instead of 800KB.

Saga Musix

Saga Musix

2020-10-20 20:44

administrator   ~0004483

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.

Saga Musix

Saga Musix

2020-10-20 21:15

administrator   ~0004484

Proposed workaround and some evil files that are disproportionally long compared to their byte size due to nested loops.

evil-loops.7z (393 bytes)
Saga Musix

Saga Musix

2020-10-23 16:45

administrator   ~0004485

More tweaking and optimizations; now the RowVisitor also handles the ProTracker Row Delay + Pattern Break quirk consistently for both regular playback and GetLength.

Saga Musix

Saga Musix

2020-10-23 22:53

administrator   ~0004486

Previous patch accidentally inverted a min/max, breaking pre-allocation

Saga Musix

Saga Musix

2020-10-23 23:38

administrator   ~0004487

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:

  • It would require knowledge about pattern break and pattern loop handling (such as per-format command precedence etc.) to be duplicated into yet another place (the pre-allocation step)
  • Other format quirks might also have to be added
  • Pattern loops can actually be carried on between patterns in some tricky situations

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.

Saga Musix

Saga Musix

2020-10-25 15:43

administrator   ~0004489

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.

Saga Musix

Saga Musix

2020-11-07 14:56

administrator   ~0004505

Last edited: 2020-11-07 15:09

View 2 revisions

Updated against current trunk and minor refactoring (consolidating more code between GetLength() and ProcessRow() to avoid duplicate logic - in fact, some logic between the two functions was not identical, leading to incorrect time calculation for a loop-related S3M quirk)

Issue History

Date Modified Username Field Change
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
2020-11-07 14:56 Saga Musix Note Added: 0004505
2020-11-07 14:56 Saga Musix File Added: handle-infinite-loops-v8.7z
2020-11-07 15:09 Saga Musix Note Edited: 0004505 View Revisions
2020-11-15 21:32 Saga Musix Relationship added related to 0001387