x/net/http2: Priorities graph corruption

[elindsey]

Go version

go1.22.1

Output of go env in your module/workspace:

$ go env
GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/elilindsey/Library/Caches/go-build'
GOENV='/Users/elilindsey/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/elilindsey/code/go/pkg/mod'
GONOPROXY='stash.corp.netflix.com'
GONOSUMDB='stash.corp.netflix.com'
GOOS='darwin'
GOPATH='/Users/elilindsey/code/go'
GOPRIVATE='stash.corp.netflix.com'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/opt/homebrew/Cellar/go/1.22.1/libexec'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/opt/homebrew/Cellar/go/1.22.1/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.22.1'
GCCGO='gccgo'
AR='ar'
CC='cc'
CXX='c++'
CGO_ENABLED='1'
GOMOD='/Users/elilindsey/code/scratchgo/bindl4/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/9v/g2961bl15zv1bx2qk1sclrtr0000gn/T/go-build4121450534=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

When a stream with multiple children is deleted, not all streams will end up parented at the priority graph's root.

Here is a failing test case:

package http2

import (
	"testing"
)

func addDep(ws *priorityWriteScheduler, child uint32, parent uint32) {
	ws.AdjustStream(child, PriorityParam{
		StreamDep: parent,
		Exclusive: false,
		Weight:    16,
	})
}

func validateDepTree(ws *priorityWriteScheduler, id uint32, t *testing.T) {
	for n := ws.nodes[id]; n != nil; n = n.parent {
		if n.parent == nil {
			if n.id != uint32(0) {
				t.Errorf("detected nodes not parented to 0")
			}
		}
	}
}

func TestPrioritiesGraphCorruption(t *testing.T) {
	ws := NewPriorityWriteScheduler(nil).(*priorityWriteScheduler)

	// Root entry
	addDep(ws, uint32(1), uint32(0))
	addDep(ws, uint32(3), uint32(1))
	addDep(ws, uint32(5), uint32(1))

	for id := uint32(7); id < uint32(100); id += uint32(4) {
		addDep(ws, id, id-uint32(4))
		addDep(ws, id+uint32(2), id-uint32(4))
		validateDepTree(ws, id, t)
	}
}

Here is a patch to fix this test case:

diff --git a/vendor/golang.org/x/net/http2/writesched_priority.go b/vendor/golang.org/x/net/http2/writesched_priority.go
index 0a242c6..f678333 100644
--- a/vendor/golang.org/x/net/http2/writesched_priority.go
+++ b/vendor/golang.org/x/net/http2/writesched_priority.go
@@ -443,8 +443,8 @@ func (ws *priorityWriteScheduler) addClosedOrIdleNode(list *[]*priorityNode, max
 }
 
 func (ws *priorityWriteScheduler) removeNode(n *priorityNode) {
-       for k := n.kids; k != nil; k = k.next {
-               k.setParent(n.parent)
+       for n.kids != nil {
+               n.kids.setParent(n.parent)
        }
        n.setParent(nil)
        delete(ws.nodes, n.id)

What did you see happen?

Some nodes in the priority graph do not have node 0 as an ancestor.

What did you expect to see?

All nodes should have node 0 as an ancestor.

[thanm]

@neild per owners.

[neild]

Good catch. Thanks for the very nice reproduction case and fix.

[gopherbot]

Change https://go.dev/cl/589255 mentions this issue: http2: avoid corruption in priority write scheduler