Programming Servo: the makings of a task-queue

The HTML Living Standard tells us the following with regards to task-queues:

And further explaining the concept of task-sources and tasks:


Task-sources in Servo

In Servo, task-sources are implemented via a channel, whose sender is cloned for each specific task-source, and where tasks are messages sent on the channel and containing a closure representing the actual task.

An example of a task-source, here the “networking” task-source: https://github.com/servo/servo/blob/master/components/script/task_source/networking.rs

Those ‘task messages’ are handled by the event-loop of the responsible webpage or worker.

https://github.com/servo/servo/blob/9e1ec1d5bbc22842c10633ce51ff07fd9d06e9ad/components/script/script_thread.rs#L1377

And the run_box is from the below trait:

So essentially, the entire concept of task-sources, tasks, and task-queues was represented as a single channel in Servo. Each clone of the Sender was a given task-source, a message sent by it was a task, and one could say the single receiver, or it’s internal buffer, represented the single task-queue used for all task-sources.


Some proposed changes

https://github.com/servo/servo/issues/19997

And so we set about to introduce throttling capacity to our task-queue…

Another way to look at this is that we simply wanted to have an actual task-queue, as opposed to having our Receiver double as one.

So one could say, the essential change was the following:

https://github.com/servo/servo/pull/21388/files

Where this TaskQueue would then also have to replace the role of the receiver inside the event-loop of the “script-thread

https://github.com/servo/servo/pull/21388/files

A generic task-queue

It’s also worth noting that besides the above “main script-thread”, which represents that event-loop of one, or several same-origin, browsing-context, Servo also has other event-loops, for the various types of web workers, and we needed to use the TaskQueue there as well:

The main difference is the type of message that a given task-queue is supposed to handle in the various event-loops. The task queue only cares about messages containing an actual task, however those are part of different broader messaging structures, as can be seen below:

So you see, the task-queue is actually only interested in the contents of CommonScriptMsg::Task , yet those are wrapped in different “structures of messaging” for the various event-loops.

How can we allow the task-queue to handle these different message type in a generic way?


Let the messages do the work themselves

First of all, we haven’t really looked at what the task-queue does internally.

At a high-level, the task-queue will sort incoming messages per task-source, make “normal” priority ones immediately available for the event-loop to drain and handle, while counting the tasks that are handled, and holding back “low-priority” tasks once a “high-watermark” of handled tasks has been reached for a given iteration of the event-loop.

At the next iteration of the event-loop, the ‘business counter’ is reset, and priority tasks are made available for the event-loop to handle. Any previously throttled non-priority task could be handled as well, since it’s a new iteration of the event-loop, but once the “high-watermark” is reached once more, such tasks will be held-back for a subsequent “less-busy” iteration of the event-loop.

Internally, the task-queue stores tasks in their most basic format, represented by a QueuedTask

So basically, in order to “sort tasks per task-source”, store them, and later make them available to the event-loop in less-busy times, the task-queue is going to have to go from the various message type to a QueuedTask, and then back.

Since the messages themselves are intimately familiar with their own structure, an “easy” way to do the above, is by letting the messages do it themselves. This can be achieved through a trait:

Here is an example of an implementation:

Essentially, it’s the message itself that will unwrap and re-construct itself. So the task-queue can simply do something like:

The result of these conversions is that as far as the event-loop’s go, nothing has changed. It’s still the same messages/events that are handled at each iteration. Yet some of these messages could be throttled for one or several iteration by the task-queue. By using a trait for the conversions from and to event-loop specific messages, the task-queue is able to focus on the throttling and other queuing logic, using the common denominator among all event-loop messages, represented by a QueuedTask.


How to wake-up an event-loop

You might have noticed the wake_up_msg and is_wake_up_msg methods on the trait above. What are those useful for?

Think about the following situation:

  1. You have throttled tasks in the queue, which are basically messages that came in during a previous iteration of the event-loop and were held back by the task-queue.
  2. You are now in a new iteration of the event-loop, which always starts with a select over the various message ports whose communication relate to running the event-loop, and the task-queue is essentially one such port.
  3. There a no new messages coming in.

At this point, your event-loop is essentially stuck waiting for events/messages to come in, while the task-queue still has some message in one of it’s non-priority queues.

We’re definitely not busy, yet we’re not handling the throttled tasks either!

First, let’s look at how the task-queue is plugged into the select of the event-loop:

So essentially, the task-queue makes the original receiver of the channel available to the select, and when the receiver is “ready to receive”, the task-queue will “take tasks” from it, and make available a “receiver-like” interface for the event-loop to “receive” tasks from the queue, as opposed to directly from the channel receiver.

So here’s the catch: if no new messages comes in, while the task-queue actually has throttled tasks ready to be handled, the event-loop would be stuck waiting on the select.

We need a way to wake-up the select when the task-queue contains throttled tasks. The task-queue does this by sending a dedicated “wake-up” message on the original “task sender”, corresponding to the “port/receiver” on which the event-loop messages are received.

Again, since the “wake-up message” will differ per event-loop, we’re just going to ask the message type to provide us with such a message.

Since this “wake-up call” is going to come-in like a regular message, we also need a way for the task-queue to discard those as part of it’s processing of incoming messages.

Again, since the message type itself is the most familiar with it’s own structure and message variants, we’re just going to let it do the job!

And that’s it folks, we won’t be blocking on our select as part of an event-loop when no new messages come in while there are throttled tasks waiting to be handled…


An high-level overview

So far I haven’t discussed the internals of the task-queue that much, let’s just say that for now we only throttle the non-priority “performance timeline” task source, and that you are welcome to take a closer look at https://github.com/servo/servo/pull/21388

I think that’s enough for today…


Want to help?

If you’re interested, there is actually one TODO left as part of the above:

Remember this CommonScriptMsg::Task ? It currently contains a ScriptThreadEventCategory , while what it really could use in addition to that would be a TaskSourceName .

Your help is much wanted and all skill-levels are welcome! https://github.com/servo/servo/issues/21527