A new core playlist for VLC 4

The core playlist in VLC was started a long time ago. Since then, it has grown to handle too many different things, to the point it became a kind of god object.

In practice, the playlist was also controlling playback (start, stop, change volume…), configuring audio and video outputs, storing media detected by discovery…

For VLC 4, we wanted a new playlist API, containing a simple list of items (instead of a tree), acting as a media provider for a player, without unrelated responsibilities.

I wrote it several months ago (at Videolabs). Now that the old one has been removed, it’s time to give some technical details.

• Objectives
• Data structure
• Interaction with UI
  • Desynchronization
  • Synchronization
    • Core to UI
    • UI to core
• Random playback
  • Randomizer
• Sorting
• Interaction with the player
• Media source
• Conclusion

Objectives

One major design goal is to expose what UI frameworks need. Several user interfaces, like Qt, Mac OS and Android¹, will use this API to display and interact with the main VLC playlist.

The playlist must be performant for common use cases and usable from multiple threads.

Indeed, in VLC, user interfaces are implemented as modules loaded dynamically. In general, there is exactly one user interface, but there may be none or (in theory) several. Thus, the playlist may not be bound to the event loop of some specific user interface. Moreover, the playlist may be modified from a player thread; for example, playing a zip archive will replace the item by its content automatically.

As a consequence, the playlist will use a mutex; to avoid ToCToU issues, it will also expose public functions to lock and unlock it. But as we will see later, there will be other consequences.

Data structure

User interfaces need random access to the playlist items, so a vector is the most natural structure to store the items. A vector is provided by the standard library of many languages (vector in C++, Vec in Rust, ArrayList in Java…). But here, we’re in C, so there is nothing.

In the playlist, we only need a vector of pointers, so I first proposed improvements to an existing type, vlc_array_t, which only supports void * as items. But it was considered useless (1, 2) because it is too limited and not type-safe.

Therefore, I wrote vlc_vector. It is implemented using macros so that it’s generic over its item type. For example, we can use a vector of ints as follow:

// declare and initialize a vector of int
struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;

// append 0, 10, 20, 30 and 40
for (int i = 0; i < 5; ++i) {
    if (!vlc_vector_push(&vec, 10 * i)) {
        // allocation failure...
    }
}

// remove item at index 2
vlc_vector_remove(2);

// the vector now contains [0, 10, 30, 40]

int first = vec.data[0]; // 0
int last = vec.data[vec.size - 1]; // 40

// free resources
vlc_vector_destroy(&vec);

Internally, the playlist uses a vector of playlist items:

typedef struct VLC_VECTOR(struct vlc_playlist_item *) playlist_item_vector_t;

struct vlc_playlist {
    playlist_item_vector_t items;
    // ...
};

Interaction with UI

UI frameworks typically use list models to bind items to a list view component. A list model must provide:

• the total number of items,
• the item at a given index.

In addition, the model must notify its view when items are inserted, removed, moved or updated, and when the model is reset (the whole content should be invalidated).

For example, Qt list views use QAbstractItemModel/QAbstractListModel and the Android recycler view uses RecyclerView.Adapter.

The playlist API exposes the functions and callbacks providing these features.

Desynchronization

However, the core playlist may not be used as a direct data source for a list model. In other words, the functions of a list model must not delegate the calls to the core playlist.

To understand why, let’s consider a typical sequence of calls executed by a view on its model, from the UI thread:

model.count();
model.get(0);
model.get(1);
model.get(2);
model.get(3);
model.get(4);

If we implemented count() and get(index) by delegating to the playlist, we would have to lock each call individually:

// in some artificial UI framework in C++

int MyModel::count() {
    // don't do this
    vlc_playlist_Lock(playlist);
    int count = vlc_playlist_Count();
    vlc_playlist_Unlock(playlist);
    return count;
}

vlc_playlist_item_t *MyModel::get(int index) {
    // don't do this
    vlc_playlist_Lock(playlist);
    vlc_playlist_item_t *item = vlc_playlist_Get(playlist, index);
    vlc_playlist_Unlock(playlist);
    return item;
}

Note that locking and unlocking from the UI thread for every playlist item is not a good idea for responsiveness, but this is a minor issue here.

The real problem is that locking is not sufficient to guarantee correctness: the list view expects its model to return consistent values. Our implementation can break this assumption, because the playlist content could change asynchronously between calls. Here is an example:

// the playlist initially contains 5 items: [A, B, C, D, E]
model.count(); // 5
model.get(0);  // A
model.get(1);  // B
                    // the first playlist item is removed from another thread:
                    //     vlc_playlist_RemoveOne(playlist, 0);
                    // the playlist now contains [B, C, D, E]
model.get(2);  // D
model.get(3);  // E
model.get(4);  // out-of-range, undefined behavior (probably segfault)

The view could not process any notification of the item removal before the end of the current execution in its event loop… that is, at least after model.get(4). To avoid this problem, the data provided by view models must always live in the UI thread.

This implies that the UI has to manage a copy of the playlist content. The UI playlist should be considered as a remote out-of-sync view of the core playlist.

Note that the copy must not be limited to the list of pointers to playlist items: the content which is displayed and susceptible to change asynchronously (media metadata, like title or duration) must also be copied. The UI needs a deep copy; otherwise, the content could change (and be exposed) before the list view was notified… which, again, would break assumptions about the model.

Synchronization

The core playlist and the UI playlist are out-of-sync. So we need to “synchronize” them:

• the changes on the core playlist must be reflected to the UI views,
• the user, via the UI, may request changes to the core playlist (to add, move or remove items for example).

Core to UI

The core playlist is the source of truth.

Every change to the UI playlist must occur in the UI thread, yet the core playlist notification handlers are executed from any thread. Therefore, playlist callback handlers must retrieve appropriate data from the playlist, then post an event to the UI event loop², which will be handled from the UI thread. From there, the core playlist will be out-of-sync, so it would be incorrect to access it.

The order of events forwarded to the UI thread must be preserved. That way, the indices notified by the core playlist are necessarily valid within the context of the list model in the UI thread. The core playlist events can be understood as a sequence of “patches” that the UI playlist must apply to its own copy.

This only works if only the core playlist callbacks modify the list model content.

UI to core

Since the list model can only be modified by the core playlist callbacks, it is incorrect to modify it on user actions. As a consequence, the changes must be requested to the core playlist, which will, in turn, notify the actual changes.

The synchronization is more tricky in that direction.

To understand why, suppose the user selects items 10 to 20, then drag & drop to move them to index 42. Once the user releases the mouse button to “drop” the items, we need to lock the core playlist to apply the changes.

The problem is that, before we successfully acquired the lock, another client may have modified the playlist: it may have cleared it, or shuffled it, or removed items 5 to 15… As a consequence, we cannot apply the “move” request as is, because it was created from a previous playlist state.

To solve the issue, we need to adapt the request to make it fit the current playlist state. In other words, resolve conflicts: find the items if they had been moved, ignore the items not found for removal…

For that purpose, in addition to functions modifying the content directly, the playlist exposes functions to request “desynchronized” changes, which automatically resolve conflicts and generate an appropriate sequence of events to notify the clients of the actual changes.

Let’s take an example. Initially, our playlist contains 10 items:

[A, B, C, D, E, F, G, H, I, J]

The user selects [C, D, E, F, G] and press the Del key to remove the items. To apply the change, we need to lock the core playlist.

But at that time, another thread was holding the lock to apply some other changes. It removed F and I, and shuffled the playlist:

[E, B, D, J, C, G, H, A]

Once the other thread unlocks the playlist, our lock finally succeeds. Then, we call request_remove([C, D, E, F, G]) (this is pseudo-code, the real function is vlc_playlist_RequestRemove).

Internally, it triggers several calls:

// [E, B, D, J, C, G, H, A]
remove(index = 4, count = 2)   // remove [C, G]
// [E, B, D, J, H, A]
remove(index = 2, count = 1)   // remove [D]
// [E, B, J, H, A]
remove(index = 0, count = 1)   // remove [E]
// [B, J, H, A]

Thus, every client (including the UI from which the user requested to remove the items), will receive a sequence of 3 events on_items_removed, corresponding to each removed slice.

The slices are removed in descending order for both optimization (it minimizes the number of shifts) and simplicity (the index of a removal does not depend on previous removals).

In practice, it is very likely that the request will apply exactly to the current state of the playlist. To avoid unnecessary linear searches to find the items, these functions accept an additional index_hint parameter, giving the index of the items when the request was created. It should (hopefully) almost always be the same as the index in the current playlist state.

Random playback

Contrary to shuffle, random playback does not move the items within the playlist; instead, it does not play them sequentially.

To select the next item to play, we could just pick one at random.

But this is not ideal: some items will be selected several times (possibly in a row) while some others will not be selected at all. And if loop is disabled, when should we stop? After all n items have been selected at least once or after n playbacks?

Instead, we would like some desirable properties that work both with loop enabled and disabled:

• an item must never be selected twice (within a cycle, if loop is enabled),
• we should be able to navigate back to the previously selected items,
• we must able to force the selection of a specific item (typically when the user double-clicks on an item in the playlist),
• insertions and removals must be taken into account at any time,

In addition, if loop is enabled:

• the random order must be recomputed for very cycle (we don’t always want the same random order),
• it should be possible to navigate back to previous items from the previous cycle,
• an item must never be selected twice in a row (in particular, it may not be the last item of one cycle and the first item of the next cycle).

Randomizer

I wrote a randomizer to select items “randomly” within all these constraints.

To get an idea of the results, here is a sequence produced for a playlist containing 5 items (A, B, C, D and E), with loop enabled (so that it continues indefinitely):

E D A B C E B C A D C B E D A C E A D B A D C E B A B D E C B C A E D E D B C A
E C B D A C A E B D C D E A B E D B A C D C B A E D A B C E B D C A E D C A B E
B A E C D C E D A B C E B A D E C B D A D B A C E C E B A D B C E D A E A C B D
A D E B C D C A E B E A D C B C D B A E C E A B D C D E A B D A E C B C A D B E
A B E C D A C B E D E D A B C D E C A B C A E B D E B D C A C A E D B D B E C A

Here is how it works.

The randomizer stores a single vector containing all the items of the playlist. This vector is not shuffled at once. Instead, steps of the Fisher-Yates algorithm are executed one-by-one on demand. This has several advantages:

• on insertions and removals, there is no need to reshuffle or shift the whole array;
• if loop is enabled, the history of the last cycle can be kept in place.

It also maintains 3 indexes:

• head indicates the end of the items already determinated for the current cycle (if loop is disabled, there is only one cycle),
• next points to the item after the current one³,
• history points to the first item of ordered history from the last cycle.

0              next  head          history       size
|---------------|-----|.............|-------------|
 <------------------->               <----------->
  determinated range                 history range

Let’s reuse the example I wrote in the documentation.

Here is the initial state with our 5 items:

                                         history
                next                     |
                head                     |
                |                        |
                A    B    C    D    E

The playlist calls Next() to retrieve the next random item. The randomizer picks one item (say, D), and swaps it with the current head (A). Next() returns D.

                                         history
                     next                |
                     head                |
                     |                   |
                D    B    C    A    E
              <--->
           determinated range

The playlist calls Next() one more time. The randomizer selects one item outside the determinated range (say, E). Next() returns E.

                                         history
                          next           |
                          head           |
                          |              |
                D    E    C    A    B
              <-------->
           determinated range

The playlist calls Next() one more time. The randomizer selects C (already in place). Next() returns C.

                                         history
                               next      |
                               head      |
                               |         |
                D    E    C    A    B
              <------------->
            determinated range

The playlist then calls Prev(). Since the “current” item is C, the previous one is E, so Prev() returns E, and next moves back.

                                         history
                          next           |
                          |    head      |
                          |    |         |
                D    E    C    A    B
              <------------->
            determinated range

The playlist calls Next(), which returns C, as expected.

                                         history
                               next      |
                               head      |
                               |         |
                D    E    C    A    B
              <------------->
            determinated range

The playlist calls Next(), the randomizer selects B, and returns it.

                                         history
                                    next |
                                    head |
                                    |    |
                D    E    C    B    A
              <------------------>
               determinated range

The playlist calls Next(), the randomizer selects the last item (it has no choice). next and head now point one item past the end (their value is the vector size).

                                         history
                                         next
                                         head
                                         |
                D    E    C    B    A
              <----------------------->
                 determinated range

At this point, if loop is disabled, it is not possible to call Next() anymore (HasNext() returns false). So let’s enable it by calling SetLoop(), then let’s call Next() again.

This will start a new loop cycle. Firstly, next and head are reset, and the whole vector belongs to the last cycle history.

                 history
                 next
                 head
                 |
                 D    E    C    B    A
              <------------------------>
                    history range

Secondly, to avoid selecting A twice in a row (as the last item of the previous cycle and the first item of the new one), the randomizer will immediately determine another item in the vector (say C) to be the first of the new cycle. The items that belong to the history are kept in order. head and history move forward.

                     history
                next |
                |    head
                |    |
                C    D    E    B    A
              <---><------------------>
      determinated     history range
             range

Finally, it will actually select and return the first item (C).

                     history
                     next
                     head
                     |
                C    D    E    B    A
              <---><------------------>
      determinated     history range
             range

Then, the user adds an item to the playlist (F). This item is added in front of history.

                          history
                     next |
                     head |
                     |    |
                C    F    D    E    B    A
              <--->     <------------------>
      determinated          history range
             range

The playlist calls Next(), the randomizer randomly selects E. E “disappears” from the history of the last cycle. This is a general property: each item may not appear more than once in the “history” (both from the last and the new cycle). The history order is preserved.

                               history
                          next |
                          head |
                          |    |
                C    E    F    D    B    A
              <-------->     <-------------->
             determinated     history range
                range

The playlist then calls Prev() 3 times, that yields C, then A, then B. next is decremented (modulo size) on each call.

                               history
                               |    next
                          head |    |
                          |    |    |
                C    E    F    D    B    A
              <-------->     <-------------->
             determinated     history range
                range

Hopefully, the resulting randomness will match what people expect in practice.

Sorting

The playlist can be sorted by an ordered list of criteria (a key and a order).

The implementation is complicated by the fact that items metadata can change asynchronously (for example if the player is parsing it), making the comparison function inconsistent.

To avoid the problem, a first pass builds a list of metadata for all items, then this list is sorted, and finally the resulting order is applied back to the playlist.

As a benefit, the items are locked only once to retrieved their metadata.

Interaction with the player

For VLC 4, Thomas wrote a new player API.

A player can be used without a playlist: we can set its current media and the player can request, when necessary, the next media to play from a media provider.

A playlist, on the other hand, needs a player, and registers itself as its media provider. They are tightly coupled:

• the playlist controls the player on user actions;
• the player events may update the playlist state.

To keep them synchronized:

• on user actions, we need to lock the playlist, then the player;
• on player events, we need to lock the player, then the playlist.

This poses a lock-order inversion problem: for example, if thread A locks the playlist then waits for the player lock, while thread B locks the player then waits for the playlist lock, then thread A and B are deadlocked.

To avoid the problem, the player and the playlist share the same lock. Concretely, vlc_playlist_Lock() delegates to vlc_player_Lock(). In practice, the lock should be held only for short periods of time.

Media source

A separate API (media source and media tree) was necessary to expose what is called services discovery (used to detect media from various sources like Samba or MTP), which were previously managed by the old playlist.

Thus, we could kill the old playlist.

Conclusion

The new playlist and player API should help to implement UI properly (spoiler: a new modern UI is being developed), to avoid racy bugs and to implement new features (spoiler: gapless).

Discuss on reddit and Hacker News.