Developer’s Corner: HoL Blocking and the Deadlock Hazard

SMITH: Doctor, it hurts when I do this.
DALE: Don’t do that.

– Smith and Dale

This is the third article in the QUIC Header Compression Design Team series.

Introduction

To achieve the best header compression performance, it is tempting to have the compression protocol allow potential head-of-line blocking (HoLB). The idea is that HoLB will not occur most of the time, while the compression gain is significant. The first article of this series exposes priority inversion caused by HoLB and challenges the assertion that HoLB is rare. The second problem is that HoLB is a potential attack vector, wherein the decoder is tricked into using a lot of memory. One way to prevent such attack is to not read from the stream until the decoder can process the stream immediately. This approach creates a deadlock hazard. This problem is examined in this article.

Note on Terminology

If a header block B depends on an entry inserted by header block A, we say that B depends on A. Together, they are dependent header blocks.

Problem Statement

Writing dependent header blocks to stream out of order introduces the risk of a deadlock. There are two types of a deadlock.

Single-stream Deadlock

When dependent header blocks are written out of order to the same stream, the first header block cannot be parsed because it depends on the block that follows it.

Multiple-stream Deadlock

This type of deadlock happens when the out-of-order header block prevents the receiver from reading stream data that follows the header block. What makes it different from the regular HoLB case is that the sender cannot put the resolving header block onto the stream due to the limits imposed by the QUIC connection flow control.

Scenario 1: Resend After a Reset

One way a multi-stream deadlock can occur is when a header block must be resent after a stream reset. By the time the sender figures out that it needs to resend a header block, it may have filled all existing streams to the brim — which the receiver cannot drain — and is not allowed to stream more data.

Possible Mitigation: Don’t Fill Flow Control Window

One potential solution is always to leave some room in the connection flow control window. That is, leave at least the number of bytes required to resend all unacknowledged header blocks.

There are downsides to this approach:

1. It is not clear that the connection flow control window information is available at HTTP/QUIC level.
2. The code complexity of the HTTP/QUIC layer increases — the user code can no longer write directly to the stream. These calls must be intercepted at HTTP/QUIC layer to ensure that the threshold is not exceeded.
3. Most of the time, these are just wasted bytes that could otherwise be used. In other words, throughput suffers.
4. Not filling the connection window may prevent the peer from sending WINDOW_UPDATE, resulting in a stall.

Scenario 2: Out-of-order Write

In general, a multi-stream deadlock can occur any time dependent header blocks are written to different streams — consuming flow control credits — out of order. If header block B depends on header block A, but is written to stream first, it may happen that header block A can never be written: If the receiver does not process stream B because of its application protocol rules (in our case, the receiver is avoiding memory exhaustion attacks), it is possible that the connection flow control prevents the sender from sending more data.

Possible Mitigation: Don’t Do That

“Well, don’t do that, then!” – might one say. This is a sound point of view: since the problem is of the application’s own making, it is up to the application to solve it. Nevertheless, the deadlock risk bears being pointed out, as it affects how a QUIC/HTTP implementation may be designed. For example, if the stream interface offered by a QUIC implementation performs internal buffering, can the application make sure that data on one stream gets sent before dependent data on another stream?

Possible Mitigation: Make the Transport Do It

My initial report to the Design Team prompted Martin Thomson to share the finding on the common IETF QUIC WG Mailing list. The resulting thread is large and makes for an interesting read. It contains several ideas on how such deadlock could be prevented by the transport, either by making the current priority implications stricter; or by introducing extra transport rules, exceptions, or overrides of various sorts.

Summary

It is natural to write dependent header blocks to streams in order. Not doing so may result in a deadlock. In particular, resetting streams forces the encoder to write header blocks out of order. Hence, the encoder must address the possibility of a deadlock in some fashion.

P. S.

The “don’t do that” versus “let the transport solve it” discussion is likely to resume at the upcoming Interim Meeting (Jan 23 – 25) in Melbourne, Australia. Watch this space for updates.