strengthen priority tree code and add tests
The priority tree codes has been strengthened to handle some new
corner cases.
- Handle setting the parent to itself.
- Handle exclusive reprioritization to the root stream.
- Handle reprioritization to stream dependent of stream being
reprioritized.
In addition, split out the adjustment function so that it can be
tested independently of the serverConn and add tests.
diff --git a/priority_test.go b/priority_test.go
new file mode 100644
index 0000000..d9648fd
--- /dev/null
+++ b/priority_test.go
@@ -0,0 +1,121 @@
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+// See https://code.google.com/p/go/source/browse/CONTRIBUTORS
+// Licensed under the same terms as Go itself:
+// https://code.google.com/p/go/source/browse/LICENSE
+
+package http2
+
+import (
+ "testing"
+)
+
+func TestPriority(t *testing.T) {
+ // A -> B
+ // move A's parent to B
+ streams := make(map[uint32]*stream)
+ a := &stream{
+ parent: nil,
+ weight: 16,
+ }
+ streams[1] = a
+ b := &stream{
+ parent: a,
+ weight: 16,
+ }
+ streams[2] = b
+ adjustStreamPriority(streams, 1, PriorityParam{
+ Weight: 20,
+ StreamDep: 2,
+ })
+ if a.parent != b {
+ t.Errorf("Expected A's parent to be B")
+ }
+ if a.weight != 20 {
+ t.Errorf("Expected A's weight to be 20; got %d", a.weight)
+ }
+ if b.parent != nil {
+ t.Errorf("Expected B to have no parent")
+ }
+ if b.weight != 16 {
+ t.Errorf("Expected B's weight to be 16; got %d", b.weight)
+ }
+}
+
+func TestPriorityExclusiveZero(t *testing.T) {
+ // A B and C are all children of the 0 stream.
+ // Exclusive reprioritization to any of the streams
+ // should bring the rest of the streams under the
+ // reprioritized stream
+ streams := make(map[uint32]*stream)
+ a := &stream{
+ parent: nil,
+ weight: 16,
+ }
+ streams[1] = a
+ b := &stream{
+ parent: nil,
+ weight: 16,
+ }
+ streams[2] = b
+ c := &stream{
+ parent: nil,
+ weight: 16,
+ }
+ streams[3] = c
+ adjustStreamPriority(streams, 3, PriorityParam{
+ Weight: 20,
+ StreamDep: 0,
+ Exclusive: true,
+ })
+ if a.parent != c {
+ t.Errorf("Expected A's parent to be C")
+ }
+ if a.weight != 16 {
+ t.Errorf("Expected A's weight to be 16; got %d", a.weight)
+ }
+ if b.parent != c {
+ t.Errorf("Expected B's parent to be C")
+ }
+ if b.weight != 16 {
+ t.Errorf("Expected B's weight to be 16; got %d", b.weight)
+ }
+ if c.parent != nil {
+ t.Errorf("Expected C to have no parent")
+ }
+ if c.weight != 20 {
+ t.Errorf("Expected C's weight to be 20; got %d", b.weight)
+ }
+}
+
+func TestPriorityOwnParent(t *testing.T) {
+ streams := make(map[uint32]*stream)
+ a := &stream{
+ parent: nil,
+ weight: 16,
+ }
+ streams[1] = a
+ b := &stream{
+ parent: a,
+ weight: 16,
+ }
+ streams[2] = b
+ adjustStreamPriority(streams, 1, PriorityParam{
+ Weight: 20,
+ StreamDep: 1,
+ })
+ if a.parent != nil {
+ t.Errorf("Expected A's parent to be nil")
+ }
+ if a.weight != 20 {
+ t.Errorf("Expected A's weight to be 20; got %d", a.weight)
+ }
+ if b.parent != a {
+ t.Errorf("Expected B's parent to be A")
+ }
+ if b.weight != 16 {
+ t.Errorf("Expected B's weight to be 16; got %d", b.weight)
+ }
+
+}
diff --git a/server.go b/server.go
index aba029a..7ab54f8 100644
--- a/server.go
+++ b/server.go
@@ -1213,7 +1213,7 @@
sc.streams[id] = st
if f.HasPriority() {
- sc.adjustStreamPriority(st.id, f.Priority)
+ adjustStreamPriority(sc.streams, st.id, f.Priority)
}
sc.curOpenStreams++
sc.req = requestParam{
@@ -1276,13 +1276,12 @@
}
func (sc *serverConn) processPriority(f *PriorityFrame) error {
- sc.adjustStreamPriority(f.StreamID, f.PriorityParam)
+ adjustStreamPriority(sc.streams, f.StreamID, f.PriorityParam)
return nil
}
-func (sc *serverConn) adjustStreamPriority(streamID uint32, priority PriorityParam) {
- // TODO: untested
- st, ok := sc.streams[streamID]
+func adjustStreamPriority(streams map[uint32]*stream, streamID uint32, priority PriorityParam) {
+ st, ok := streams[streamID]
if !ok {
// TODO: not quite correct (this streamID might
// already exist in the dep tree, but be closed), but
@@ -1290,10 +1289,27 @@
return
}
st.weight = priority.Weight
- st.parent = sc.streams[priority.StreamDep] // might be nil
- if priority.Exclusive && st.parent != nil {
- for _, openStream := range sc.streams {
- if openStream.parent == st.parent {
+ parent := streams[priority.StreamDep] // might be nil
+ if parent == st {
+ // if client tries to set this stream to be the parent of itself
+ // ignore and keep going
+ return
+ }
+
+ // section 5.3.3: If a stream is made dependent on one of its
+ // own dependencies, the formerly dependent stream is first
+ // moved to be dependent on the reprioritized stream's previous
+ // parent. The moved dependency retains its weight.
+ for piter := parent; piter != nil; piter = piter.parent {
+ if piter == st {
+ parent.parent = st.parent
+ break
+ }
+ }
+ st.parent = parent
+ if priority.Exclusive && (st.parent != nil || priority.StreamDep == 0) {
+ for _, openStream := range streams {
+ if openStream != st && openStream.parent == st.parent {
openStream.parent = st
}
}
