x/net/http2/hpack: Regression in dynamic table size updates

[dridi]

What version of Go are you using (go version)?

$ go version
go version go1.11.2 linux/amd64

Does this issue reproduce with the latest release?

I'm not sure, I install go from fedora repositories:

$ rpm -qa golang golang-src
golang-1.11.2-1.fc29.x86_64
golang-src-1.11.2-1.fc29.noarch

But the code from the master looks very similar if not identical, so probably a yes. I only browsed the pieces of code I discuss below.

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/dridi/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/dridi/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/lib/golang"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/golang/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build448483994=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Before we added support for HTTP/2 to Varnish Cache I wrote a single-allocation HPACK implementation called cashpack (it does not amortize dynamic tables across concurrent h2 sessions). Once I had a 100% coverage of the spec I added partial support for nghttp2 decoding with the same test suite and partial support for go's hpack implementation. The support is partial because when I baked in golang support there was no way to probe the dynamic table and check its contents.

The goal was to get some confidence in terms of interoperability with other implementations, in addition to prototyping an HPACK implementation that would work under Varnish's memory constraints.

The code is here:

https://github.com/Dridi/cashpack

The test suite is explained in great details here:

https://github.com/Dridi/cashpack/blob/master/tst/README.rst

Including a word on interop checks:

https://github.com/Dridi/cashpack/blob/master/tst/README.rst#interoperability-checks

What did you expect to see?

When I worked on cashpack for the first time since I upgraded to Fedora 29 I ran into two test failures only for the go implementation. Ever since go 1.6 I have been used to seeing the test suite pass and was surprised to see it fail!

What did you see instead?

The error log from the test suite looks like this:

FAIL: rfc7541_4_2
=================

---------------------------------------------
TEST: Encoder can choose to use less capacity
---------------------------------------------
hpack_decode: ./hdecode
hpack_decode: ./fdecode
hpack_decode: ./godecode
hpack_encode: ./hencode
----------------------------------
TEST: Resize followed by an update
----------------------------------
hpack_decode: ./hdecode --decoding-spec d12,r20,
hpack_decode: ./fdecode --decoding-spec d12,r20,
hpack_decode: ./godecode --decoding-spec d12,r20,
2018/12/12 09:27:29 decode: decoding error: dynamic table size update MUST occur at the beginning of a header block
FAIL rfc7541_4_2 (exit status: 1)

FAIL: rfc7541_4_3
=================

--------------------------------------------
TEST: Downsizing the dynamic table may evict
--------------------------------------------
hpack_decode: ./hdecode --decoding-spec d25,r42,
hpack_decode: ./fdecode --decoding-spec d25,r42,
hpack_decode: ./godecode --decoding-spec d25,r42,
2018/12/12 09:27:29 decode: decoding error: dynamic table size update MUST occur at the beginning of a header block
FAIL rfc7541_4_3 (exit status: 1)

I checked the code from the golang-src package on Fedora and came to the conclusion that the logic is broken if my reading of the RFC is correct.

go/src/internal/x/net/http2/hpack/hpack.go

Lines 392 to 396 in 2012227

	// RFC 7541, sec 4.2: This dynamic table size update MUST occur at the
	// beginning of the first header block following the change to the dynamic table size.
	if d.dynTab.size > 0 {
	return DecodingError{errors.New("dynamic table size update MUST occur at the beginning of a header block")}
	}

Here the code is looking at the size of the dynamic table to figure whether we are at the beginning of a block, but the dynamic table is completely orthogonal to the organization of blocks. The block from stream 1 may insert fields into the table, and the block from stream 3 may wish to enlarge the table to make room for cookies.

There is also a convoluted use case to help clear the dynamic table without changing its size:

• dynamic table has a size $size
• out of band resize to zero
• out of band resize to $size
• next block needs a size update of $size
• once the update is performed the table should be empty
• parse fields from the rest of the block

It looks like in hpack.go the out of band resize takes effect immediately instead of being deferred to the next HPACK block (which in practice shouldn't make any difference). The actionable bug is that assuming that a table update that must happen at the beginning of a block is correlated to the dynamic table being empty.

If I understand the purpose correctly of hpack.Decode.Close() (the only function I used that is not documented) it is meant to signal the end of an HPACK block, however there is no state tracking of that fact, only a check that there is no further data left to be parsed:

go/src/vendor/golang_org/x/net/http2/hpack/hpack.go

Lines 229 to 234 in 1ae7397

	func (d *Decoder) Close() error {
	if d.saveBuf.Len() > 0 {
	d.saveBuf.Reset()
	return DecodingError{errors.New("truncated headers")}
	}
	return nil

Test cases for RFC coverage include a copy of the section they cover, for example the double-resize single-update case:

https://github.com/Dridi/cashpack/blob/master/tst/rfc7541_4_2#L24-L35

If you wish to look closer at the test suite, you will sometimes see that some interop checks are ignored because either the HPACK implementation leaves some checks to its h2 stack or we run into undefined behavior like for example the limits of packed integers. This is done with the tst_ignore fixture to leave out the go or nghttp2 implementation.

I'm not a go developer so I don't feel confident enough to attempt a patch. godecode was my very first go program, please be gentle :)

https://github.com/Dridi/cashpack/blob/master/tst/godecode.go

[fraenkel]

@bradfitz FYI

You are correct. The fix isn't quite right since the Decoder is missing a bit of state.
Our choices are to

1. Fix it properly, which requires an additional API and knowledge when to use it appropriately. The decode needs to know when it is processing the first frame, and internally we can easily determine if its the first representation of the first frame.
2. Revert

I did investigate other hpack implementations to see how they handled this spec issue. Most do not. Lua actually documented it as a TODO, and another handled it appropriately because they decoded the entire header as one big blob.

[dridi]

I'm not sure you need to change the API to fix this, but my review of your implementation was rather superficial.

You definitely need more state tracking, but as long as this remains as an internal/vendor package you probably don't need more documentation, only references to the RFC like the mention of section 4.2 above. Any reason why it's not part of the public go API? I'm asking for a friend :-p

[fraenkel]

There is no need to change the API, but a new API needs to be added.
The issue is that hpack isn't internal which is why we just can't hide it. We can offer both behaviors to check or not based on using the new API.
The sticky point with the new API is that it adds state to the Decoder which is not there today. One will need to mark when the first header is being written and constantly mark it. This is only known from within the Framer, https://github.com/golang/net/blob/master/http2/frame.go#L1534. The rest can be handled within the Decoder.

On the flip side, the Encoder doesn't guarantee that it would generate the update as the beginning of the first block since it too lacks state but it's less of an issue there.

[dridi]

You already have the Close() method to signal the end of block according to how the h2 stack uses it, so you can know when it's called that the next write starts a new block.

Regarding the out of band resize (done via h2 settings) you need to keep track up to two of them and remember the lowest and the latest.

I think the decoder can grow new internal state for both without the need for a new API.

[dridi]

IMO the first thing to do is to godoc the Close() method because I had to see how it was used in DecodeFull() to wildguess its purpose and in the h2 code to confirm it:

go/src/internal/x/net/http2/hpack/hpack.go

Lines 215 to 227 in 944a9c7

	func (d *Decoder) DecodeFull(p []byte) ([]HeaderField, error) {
	var hf []HeaderField
	saveFunc := d.emit
	defer func() { d.emit = saveFunc }()
	d.emit = func(f HeaderField) { hf = append(hf, f) }
	if _, err := d.Write(p); err != nil {
	return nil, err
	}
	if err := d.Close(); err != nil {
	return nil, err
	}
	return hf, nil
	}

go/src/net/http/h2_bundle.go

Lines 2775 to 2797 in 944a9c7

	var hc http2headersOrContinuation = hf
	for {
	frag := hc.HeaderBlockFragment()
	if _, err := hdec.Write(frag); err != nil {
	return nil, http2ConnectionError(http2ErrCodeCompression)
	}
	if hc.HeadersEnded() {
	break
	}
	if f, err := fr.ReadFrame(); err != nil {
	return nil, err
	} else {
	hc = f.(*http2ContinuationFrame) // guaranteed by checkFrameOrder
	}
	}
	mh.http2HeadersFrame.headerFragBuf = nil
	mh.http2HeadersFrame.invalidate()
	if err := hdec.Close(); err != nil {
	return nil, http2ConnectionError(http2ErrCodeCompression)
	}

I must admit I found the name surprising initially :)

[dridi]

On the flip side, the Encoder doesn't guarantee that it would generate the update as the beginning of the first block since it too lacks state but it's less of an issue there.

I had my eyes on the Encoder when I added go to the cashpack test suite but it didn't seem flexible enough to meet the needs of the test suite. So my review there was even more superficial and I didn't revisit it on Monday while I was hunting this bug.

[fraenkel]

Good catch on using Close(). I think I can get something to work quickly.
As far as the second issue regarding out of band resize, that needs to go into a separate issue since that is just missing.

[gopherbot]

Change https://golang.org/cl/153978 mentions this issue: http2/hpack: track the beginning of a header block

[gopherbot]

Change https://golang.org/cl/154118 mentions this issue: internal/x/net/http2/hpack: update from upstream

[fraenkel]

I believe this can be closed now since the changes have been merged.

[dridi]

I had forgotten about this one and indeed, closing it was long overdue.

I was able to test the net/http2/hpack package from go1.18.5 (current version on Fedora 36) with my test suite and it passed with flying colors.