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

Dridi · 2018-12-12T09:04:16Z

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

The text was updated successfully, but these errors were encountered:

fraenkel · 2018-12-12T21:35:56Z

@bradfitz FYI

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

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.
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 · 2018-12-13T09:40:49Z

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 · 2018-12-13T10:35:52Z

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 · 2018-12-13T10:40:30Z

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 · 2018-12-13T10:51:14Z

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 · 2018-12-13T10:56:17Z

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 · 2018-12-13T11:18:20Z

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 · 2018-12-13T11:53:00Z

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

dynamic table size updates must occur at the beginning of the first header block. The original fix, golang/go#25023, guaranteed it was at the beginning of the very first block. The Close method implicitly marked the end of the current header. We now document the Close behavior and can track when we are at the beginning of the first block. Updates golang/go#29187 Change-Id: I83ec39546527cb17d7de8a88ec417a46443d2baa Reviewed-on: https://go-review.googlesource.com/c/153978 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>

gopherbot · 2018-12-13T20:30:14Z

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

Updates to x/net git rev 891ebc4b82d6e74f468c533b06f983c7be918a96 for: http2/hpack: track the beginning of a header block https://go-review.googlesource.com/c/153978 Updates #29187 Change-Id: Ie2568b3f8d6aaa3f097a4ac25d3acdc794f5ff5c Reviewed-on: https://go-review.googlesource.com/c/154118 Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Matt Layher <mdlayher@gmail.com>

fraenkel · 2020-02-22T14:10:19Z

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

dynamic table size updates must occur at the beginning of the first header block. The original fix, golang/go#25023, guaranteed it was at the beginning of the very first block. The Close method implicitly marked the end of the current header. We now document the Close behavior and can track when we are at the beginning of the first block. Updates golang/go#29187 Change-Id: I83ec39546527cb17d7de8a88ec417a46443d2baa Reviewed-on: https://go-review.googlesource.com/c/153978 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>

Dridi · 2022-08-25T17:45:23Z

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.

gopherbot added this to the Unreleased milestone Dec 12, 2018

rsc mentioned this issue May 22, 2020

x/build/cmd/gopherbot: released things get marked Unreleased #39213

Open

seankhliao closed this as completed Aug 20, 2022

golang locked and limited conversation to collaborators Aug 25, 2023

gopherbot added the FrozenDueToAge label Aug 25, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

Dridi commented Dec 12, 2018

fraenkel commented Dec 12, 2018

Dridi commented Dec 13, 2018

fraenkel commented Dec 13, 2018

Dridi commented Dec 13, 2018

Dridi commented Dec 13, 2018

Dridi commented Dec 13, 2018

fraenkel commented Dec 13, 2018

gopherbot commented Dec 13, 2018

gopherbot commented Dec 13, 2018

fraenkel commented Feb 22, 2020

Dridi commented Aug 25, 2022

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

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

Comments

Dridi commented Dec 12, 2018

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

fraenkel commented Dec 12, 2018

Dridi commented Dec 13, 2018

fraenkel commented Dec 13, 2018

Dridi commented Dec 13, 2018

Dridi commented Dec 13, 2018

Dridi commented Dec 13, 2018

fraenkel commented Dec 13, 2018

gopherbot commented Dec 13, 2018

gopherbot commented Dec 13, 2018

fraenkel commented Feb 22, 2020

Dridi commented Aug 25, 2022

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

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