Page History

Work Queue Deadlocks

Use of Work Queues

Most network drivers use a work queue to handle network events. This is done for two reason: (1) Most of the example code to leverage from does it that way, and (2) it is easier and is a more efficient use memory resources to use the work queue rather than creating a dedicated task/thread to service the network.

High and Low Priority Work Queues

There are two work queues: A single, high priority work queue that is intended only to service the back end interrupt processing in a semi-normal, tasking context. And low priority work queue(s) that are similar but as then name implies are lower in priority and not dedicated for time-critical back end interrupt processing.

Downsides of Work Queues

There are two important downsides to the use of work queues. First, the work queues are inherently non-deterministic. The time delay from the point at which you schedule work and the time at which the work is performed in highly random and that delay is due not only to the strict priority scheduling but also to what work as been queued ahead of you.

...

A second problem is related: Only one work queue job can be performed at a time. That job should be brief so that it can make the work queue available again for the next work queue job as soon as possible. And that job should never block waiting for resources! If the job blocks, then it blocks the entire work queue and makes the whole work queue unavailable for the duration of the wait.

Networking on Work Queues

As mentioned, most network drivers use a work queue to handle network events. (some are even configurable to use high priority work queue... YIKES!). Most network operations are not really suited for execution on a work queue: The networking operations can be quite extended and also can block waiting for for the availability of resources. So, at a minimum, networking should never use the high priority work queue.

Work Queue Deadlocks

If there is only a single instance of a work queue, then it is easy to create a deadlock on the work queue if a work job blocks on the work queue. Here is the generic work queue deadlock scenario:

• A job runs on a work queue and waits for the availability of a resource.
• The operation that provides that resource also runs on the same work queue.
• But since the work queue is blocked waiting for the resource, the job that provides the resource cannot run and a deadlock results.

IOBs

IOBs (I/O Blocks) are small I/O buffers that can be linked together in chains to efficiently buffer variable sized network packet data. This is a much more efficient use of buffering space than full packet buffers since the packets content is often much smaller than the full packet size (the MSS).

...

• Some logic in the OS runs on a work queue and blocks waiting for an IOB to become available,
• The logic that releases the IOB also runs on the same work queue, but
• That logic that provides the IOB cannot execute, however, because the other job is blocked waiting for the IOB on the same work queue.

Alternatives to Work Queues

To avoid network deadlocks here is the rule: Never run the network on a singleton work queue!

Most network implementation do just that! Here are a couple of alternatives:

Use Multiple Low Priority Work Queues

Unlike the high priority work queues, the low priority work queues utilize a thread pool. The number of threads in the pool is controlled by the CONFIG_SCHED_LPNTHREADS. If CONFIG_SCHED_LPNTHREADS is greater than one, then such deadlocks should not be possible: In that case, if a thread is busy with some other job (even if it is only waiting for a resource), then the job will be assigned to a different thread and the deadlock will be broken. The cost of the additional low priority work queue thread is primarily the memory set aside for the thread's stack.

Use a Dedicated Network Thread

The best solution would be to write a custom kernel thread to handle driver network operations. This would be the highest performing and the most manageable. It would also, however, but substantially more work.

Interactions with Network Locks

The network lock is a re-entrant mutex that enforces mutually exclusive access to the network. The network lock can also cause deadlocks and can also interact with the work queues to degrade performance. Consider this scenario:

...