mirror of
https://github.com/refraction-networking/uquic.git
synced 2025-04-04 20:57:36 +03:00
1469 lines
41 KiB
Go
1469 lines
41 KiB
Go
package quic
|
|
|
|
import (
|
|
"fmt"
|
|
"math"
|
|
"testing"
|
|
|
|
"golang.org/x/exp/rand"
|
|
|
|
"github.com/refraction-networking/uquic/internal/protocol"
|
|
|
|
"github.com/stretchr/testify/require"
|
|
)
|
|
|
|
type callbackTracker struct {
|
|
called *bool
|
|
cb func()
|
|
}
|
|
|
|
func (t *callbackTracker) WasCalled() bool { return *t.called }
|
|
|
|
func getFrameSorterTestCallback(t *testing.T) (func(), callbackTracker) {
|
|
var called bool
|
|
cb := func() {
|
|
if called {
|
|
t.Fatal("double free")
|
|
}
|
|
called = true
|
|
}
|
|
return cb, callbackTracker{
|
|
cb: cb,
|
|
called: &called,
|
|
}
|
|
}
|
|
|
|
func TestFrameSorterSimpleCases(t *testing.T) {
|
|
s := newFrameSorter()
|
|
_, data, doneCb := s.Pop()
|
|
require.Nil(t, data)
|
|
require.Nil(t, doneCb)
|
|
|
|
// empty frames are ignored
|
|
require.NoError(t, s.Push(nil, 0, nil))
|
|
_, data, doneCb = s.Pop()
|
|
require.Nil(t, data)
|
|
require.Nil(t, doneCb)
|
|
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push([]byte("bar"), 3, cb2))
|
|
require.True(t, s.HasMoreData())
|
|
require.NoError(t, s.Push([]byte("foo"), 0, cb1))
|
|
|
|
offset, data, doneCb := s.Pop()
|
|
require.Equal(t, []byte("foo"), data)
|
|
require.Zero(t, offset)
|
|
require.NotNil(t, doneCb)
|
|
doneCb()
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, s.HasMoreData())
|
|
|
|
offset, data, doneCb = s.Pop()
|
|
require.Equal(t, []byte("bar"), data)
|
|
require.Equal(t, protocol.ByteCount(3), offset)
|
|
require.NotNil(t, doneCb)
|
|
doneCb()
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, s.HasMoreData())
|
|
|
|
// now receive a duplicate
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push([]byte("foo"), 0, cb3))
|
|
require.False(t, s.HasMoreData())
|
|
require.True(t, t3.WasCalled())
|
|
|
|
// now receive a later frame that overlaps with the ones we already consumed
|
|
cb4, _ := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push([]byte("barbaz"), 3, cb4))
|
|
require.True(t, s.HasMoreData())
|
|
|
|
offset, data, _ = s.Pop()
|
|
require.Equal(t, protocol.ByteCount(6), offset)
|
|
require.Equal(t, []byte("baz"), data)
|
|
require.False(t, s.HasMoreData())
|
|
}
|
|
|
|
// Usually, it's not a good idea to test the implementation details.
|
|
// However, we need to make sure that the frame sorter handles gaps correctly,
|
|
// in particular when overlapping stream data is received.
|
|
// This also includes returning buffers that are no longer needed.
|
|
func TestFrameSorterGapHandling(t *testing.T) {
|
|
getData := func(l protocol.ByteCount) []byte {
|
|
b := make([]byte, l)
|
|
rand.Read(b)
|
|
return b
|
|
}
|
|
|
|
checkQueue := func(t *testing.T, s *frameSorter, m map[protocol.ByteCount][]byte) {
|
|
require.Equal(t, len(m), len(s.queue))
|
|
for offset, data := range m {
|
|
require.Contains(t, s.queue, offset)
|
|
require.Equal(t, data, s.queue[offset].Data)
|
|
}
|
|
}
|
|
|
|
checkGaps := func(t *testing.T, s *frameSorter, expectedGaps []byteInterval) {
|
|
if s.gaps.Len() != len(expectedGaps) {
|
|
fmt.Println("Gaps:")
|
|
for gap := s.gaps.Front(); gap != nil; gap = gap.Next() {
|
|
fmt.Printf("\t%d - %d\n", gap.Value.Start, gap.Value.End)
|
|
}
|
|
require.Equal(t, len(expectedGaps), s.gaps.Len())
|
|
}
|
|
var i int
|
|
for gap := s.gaps.Front(); gap != nil; gap = gap.Next() {
|
|
require.Equal(t, expectedGaps[i], gap.Value)
|
|
i++
|
|
}
|
|
}
|
|
|
|
// ---xxx--------------
|
|
// ++++++
|
|
// =>
|
|
// ---xxx++++++--------
|
|
t.Run("case 1", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 11, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ---xxx-----------------
|
|
// +++++++
|
|
// =>
|
|
// ---xxx---+++++++--------
|
|
t.Run("case 2", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 10, cb2)) // 10 -15
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
10: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 6, End: 10},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ---xxx----xxxxxx-------
|
|
// ++++
|
|
// =>
|
|
// ---xxx++++xxxxx--------
|
|
t.Run("case 3", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f3, 10, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f2, 6, cb3)) // 6 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f2,
|
|
10: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ----xxxx-------
|
|
// ++++
|
|
// =>
|
|
// ----xxxx++-----
|
|
t.Run("case 4", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 7
|
|
require.NoError(t, s.Push(f2, 5, cb2)) // 5 - 9
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
7: f2[2:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 9, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
t.Run("case 4, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 2))
|
|
f1 := getData(4 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 7
|
|
require.NoError(t, s.Push(f2, 5*mult, cb2)) // 5 - 9
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f1,
|
|
7 * mult: f2[2*mult:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 9 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// xxxx-------
|
|
// ++++
|
|
// =>
|
|
// xxxx+++-----
|
|
t.Run("case 5", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 0, cb1)) // 0 - 4
|
|
require.NoError(t, s.Push(f2, 3, cb2)) // 3 - 7
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
0: f1,
|
|
4: f2[1:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 7, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
t.Run("case 5, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 2))
|
|
f1 := getData(4 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 0, cb1)) // 0 - 4
|
|
require.NoError(t, s.Push(f2, 3*mult, cb2)) // 3 - 7
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
0: f1,
|
|
4 * mult: f2[mult:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 7 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ----xxxx-------
|
|
// ++++
|
|
// =>
|
|
// --++xxxx-------
|
|
t.Run("case 6", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 9
|
|
require.NoError(t, s.Push(f2, 3, cb2)) // 3 - 7
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f2[:2],
|
|
5: f1,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 9, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
t.Run("case 6, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 2))
|
|
f1 := getData(4 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5*mult, cb1)) // 5 - 9
|
|
require.NoError(t, s.Push(f2, 3*mult, cb2)) // 3 - 7
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f2[:2*mult],
|
|
5 * mult: f1,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 9 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ---xxx----xxxxxx-------
|
|
// ++
|
|
// =>
|
|
// ---xxx++--xxxxx--------
|
|
t.Run("case 7", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(2)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f3, 10, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f2, 6, cb3)) // 6 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f2,
|
|
10: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 8, End: 10},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx---------xxxxxx--
|
|
// ++
|
|
// =>
|
|
// ---xxx---++----xxxxx--
|
|
t.Run("case 8", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(2)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f3, 15, cb2)) // 15 - 20
|
|
require.NoError(t, s.Push(f2, 10, cb3)) // 10 - 12
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
10: f2,
|
|
15: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 6, End: 10},
|
|
{Start: 12, End: 15},
|
|
{Start: 20, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx----xxxxxx-------
|
|
// ++
|
|
// =>
|
|
// ---xxx--++xxxxx--------
|
|
t.Run("case 9", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(2)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f3, 10, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f2, 8, cb3)) // 8 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
8: f2,
|
|
10: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 6, End: 8},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx----=====-------
|
|
// +++++++
|
|
// =>
|
|
// ---xxx++++=====--------
|
|
t.Run("case 10", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 10, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f3, 5, cb3)) // 5 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f3[1:5],
|
|
10: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 10, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 4))
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 10*mult, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f3, 5*mult, cb3)) // 5 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f1,
|
|
6 * mult: f3[mult : 5*mult],
|
|
10 * mult: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 15 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxxx----=====-------
|
|
// ++++++
|
|
// =>
|
|
// ---xxx++++=====--------
|
|
t.Run("case 11", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 7
|
|
require.NoError(t, s.Push(f2, 10, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f3, 5, cb3)) // 5 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
7: f3[2:],
|
|
10: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxxx----=====-------
|
|
// ++++++
|
|
// =>
|
|
// ---xxx++++=====--------
|
|
t.Run("case 11, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 3))
|
|
f1 := getData(4 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 7
|
|
require.NoError(t, s.Push(f2, 10*mult, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f3, 5*mult, cb3)) // 5 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f1,
|
|
7 * mult: f3[2*mult:],
|
|
10 * mult: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 15 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ----xxxx-------
|
|
// +++++++
|
|
// =>
|
|
// ----+++++++-----
|
|
t.Run("case 12", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(7)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 7
|
|
require.NoError(t, s.Push(f2, 3, cb2)) // 3 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ----xxx===-------
|
|
// +++++++
|
|
// =>
|
|
// ----+++++++-----
|
|
t.Run("case 13", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(7)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 9
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ----xxx====-------
|
|
// +++++
|
|
// =>
|
|
// ----+++====-----
|
|
t.Run("case 14", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 10
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f3[:3],
|
|
6: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 14, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 3))
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6*mult, cb2)) // 6 - 10
|
|
require.NoError(t, s.Push(f3, 3*mult, cb3)) // 3 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f3[:3*mult],
|
|
6 * mult: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 10 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ----xxx===-------
|
|
// ++++++
|
|
// =>
|
|
// ----++++++-----
|
|
t.Run("case 15", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 9
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 9
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 9, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxxx-------
|
|
// ++++
|
|
// =>
|
|
// ---xxxx-----
|
|
t.Run("case 16", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 9
|
|
require.NoError(t, s.Push(f2, 5, cb2)) // 5 - 9
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
5: f1,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 5},
|
|
{Start: 9, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
// ----xxx===-------
|
|
// +++
|
|
// =>
|
|
// ----xxx===-----
|
|
t.Run("case 17", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(3)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 9
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 6
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 9, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxxx-------
|
|
// ++
|
|
// =>
|
|
// ---xxxx-----
|
|
t.Run("case 18", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(4)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(2)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 9
|
|
require.NoError(t, s.Push(f2, 5, cb2)) // 5 - 7
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
5: f1,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 5},
|
|
{Start: 9, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
// ---xxxxx------
|
|
// ++
|
|
// =>
|
|
// ---xxxxx----
|
|
t.Run("case 19", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(5)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(2)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 10
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
5: f1,
|
|
})
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
5: f1,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 5},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
// xxxxx------
|
|
// ++
|
|
// =>
|
|
// xxxxx------
|
|
t.Run("case 20", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(10)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 0, cb1)) // 0 - 10
|
|
require.NoError(t, s.Push(f2, 5, cb2)) // 5 - 9
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
0: f1,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
// ---xxxxx---
|
|
// +++
|
|
// =>
|
|
// ---xxxxx---
|
|
t.Run("case 21", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(5)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 10
|
|
require.NoError(t, s.Push(f2, 7, cb2)) // 7 - 10
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 5},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
5: f1,
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
})
|
|
|
|
// ----xxx------
|
|
// +++++
|
|
// =>
|
|
// --+++++----
|
|
t.Run("case 22", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 8
|
|
require.NoError(t, s.Push(f2, 3, cb2)) // 3 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 8, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ----xxx===------
|
|
// ++++++++
|
|
// =>
|
|
// --++++++++----
|
|
t.Run("case 23", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(8)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 8
|
|
require.NoError(t, s.Push(f2, 8, cb2)) // 8 - 11
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 11, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// --xxx---===---
|
|
// ++++++
|
|
// =>
|
|
// --xxx++++++----
|
|
t.Run("case 24", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 6, cb3)) // 6 - 12
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 12, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// --xxx---===---###
|
|
// +++++++++
|
|
// =>
|
|
// --xxx+++++++++###
|
|
t.Run("case 25", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(3)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
f4 := getData(9)
|
|
cb4, t4 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 15, cb3)) // 15 - 18
|
|
require.NoError(t, s.Push(f4, 6, cb4)) // 6 - 15
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f4,
|
|
15: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 18, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
require.False(t, t4.WasCalled())
|
|
})
|
|
|
|
// ----xxx------
|
|
// +++++++
|
|
// =>
|
|
// --+++++++---
|
|
t.Run("case 26", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(10)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 8
|
|
require.NoError(t, s.Push(f2, 3, cb2)) // 3 - 13
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 13, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
})
|
|
|
|
// ---xxx====---
|
|
// ++++
|
|
// =>
|
|
// --+xxx====---
|
|
t.Run("case 27", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(4)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 10
|
|
require.NoError(t, s.Push(f3, 2, cb3)) // 2 - 6
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
2: f3[:1],
|
|
3: f1,
|
|
6: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 2},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 27, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
const mult = protocol.MinStreamFrameSize
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(4 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6*mult, cb2)) // 6 - 10
|
|
require.NoError(t, s.Push(f3, 2*mult, cb3)) // 2 - 6
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
2 * mult: f3[:mult],
|
|
3 * mult: f1,
|
|
6 * mult: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 2 * mult},
|
|
{Start: 10 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx====---
|
|
// ++++++
|
|
// =>
|
|
// --+xxx====---
|
|
t.Run("case 28", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 10
|
|
require.NoError(t, s.Push(f3, 2, cb3)) // 2 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
2: f3[:1],
|
|
3: f1,
|
|
6: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 2},
|
|
{Start: 10, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 28, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
const mult = protocol.MinStreamFrameSize
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6*mult, cb2)) // 6 - 10
|
|
require.NoError(t, s.Push(f3, 2*mult, cb3)) // 2 - 8
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
2 * mult: f3[:mult],
|
|
3 * mult: f1,
|
|
6 * mult: f2,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 2 * mult},
|
|
{Start: 10 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx===-----
|
|
// +++++
|
|
// =>
|
|
// ---xxx+++++---
|
|
t.Run("case 29", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(5)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 9
|
|
require.NoError(t, s.Push(f3, 6, cb3)) // 6 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 11, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx===----
|
|
// ++++++
|
|
// =>
|
|
// ---xxx===++--
|
|
t.Run("case 30", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6, cb2)) // 6 - 9
|
|
require.NoError(t, s.Push(f3, 5, cb3)) // 5 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f2,
|
|
9: f3[4:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 11, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 30, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 2))
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(6 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 6*mult, cb2)) // 6 - 9
|
|
require.NoError(t, s.Push(f3, 5*mult, cb3)) // 5 - 11
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f1,
|
|
6 * mult: f2,
|
|
9 * mult: f3[4*mult:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 11 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx---===-----
|
|
// ++++++++++
|
|
// =>
|
|
// ---xxx++++++++---
|
|
t.Run("case 31", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(10)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 5, cb3)) // 5 - 15
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f3[1:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 15, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 31, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 9))
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(10 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9*mult, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 5*mult, cb3)) // 5 - 15
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f1,
|
|
6 * mult: f3[mult:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 15 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx---===-----
|
|
// +++++++++
|
|
// =>
|
|
// ---+++++++++---
|
|
t.Run("case 32", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(9)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 12
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f3,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 12, End: protocol.MaxByteCount},
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
|
|
// ---xxx---===###-----
|
|
// ++++++++++++
|
|
// =>
|
|
// ---xxx++++++++++---
|
|
t.Run("case 33", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(3)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
f4 := getData(12)
|
|
cb4, t4 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 9, cb3)) // 12 - 15
|
|
require.NoError(t, s.Push(f4, 5, cb4)) // 5 - 17
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f1,
|
|
6: f4[1:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 17, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
require.True(t, t4.WasCalled())
|
|
})
|
|
|
|
t.Run("case 33, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 11))
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(3 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(3 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
f4 := getData(12 * mult)
|
|
cb4, t4 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9*mult, cb2)) // 9 - 12
|
|
require.NoError(t, s.Push(f3, 9*mult, cb3)) // 12 - 15
|
|
require.NoError(t, s.Push(f4, 5*mult, cb4)) // 5 - 17
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f1,
|
|
6 * mult: f4[mult:],
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 17 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
require.False(t, t4.WasCalled())
|
|
})
|
|
|
|
// ---xxx===---###
|
|
// ++++++
|
|
// =>
|
|
// ---xxx++++++###
|
|
t.Run("case 34", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(5)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(5)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(10)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
f4 := getData(5)
|
|
cb4, t4 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 5, cb1)) // 5 - 10
|
|
require.NoError(t, s.Push(f2, 10, cb2)) // 10 - 15
|
|
require.NoError(t, s.Push(f4, 20, cb3)) // 20 - 25
|
|
require.NoError(t, s.Push(f3, 10, cb4)) // 10 - 20
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
5: f1,
|
|
10: f3,
|
|
20: f4,
|
|
})
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 5},
|
|
{Start: 25, End: protocol.MaxByteCount},
|
|
})
|
|
require.False(t, t1.WasCalled())
|
|
require.True(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
require.False(t, t4.WasCalled())
|
|
})
|
|
|
|
// ---xxx---####---
|
|
// ++++++++
|
|
// =>
|
|
// ---++++++####---
|
|
t.Run("case 35", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
f1 := getData(3)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(8)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9, cb2)) // 9 - 13
|
|
require.NoError(t, s.Push(f3, 3, cb3)) // 3 - 11
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3},
|
|
{Start: 13, End: protocol.MaxByteCount},
|
|
})
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3: f3[:6],
|
|
9: f2,
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.True(t, t3.WasCalled())
|
|
})
|
|
|
|
t.Run("case 35, for long frames", func(t *testing.T) {
|
|
s := newFrameSorter()
|
|
mult := protocol.ByteCount(math.Ceil(float64(protocol.MinStreamFrameSize) / 6))
|
|
f1 := getData(3 * mult)
|
|
cb1, t1 := getFrameSorterTestCallback(t)
|
|
f2 := getData(4 * mult)
|
|
cb2, t2 := getFrameSorterTestCallback(t)
|
|
f3 := getData(8 * mult)
|
|
cb3, t3 := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f1, 3*mult, cb1)) // 3 - 6
|
|
require.NoError(t, s.Push(f2, 9*mult, cb2)) // 9 - 13
|
|
require.NoError(t, s.Push(f3, 3*mult, cb3)) // 3 - 11
|
|
checkGaps(t, s, []byteInterval{
|
|
{Start: 0, End: 3 * mult},
|
|
{Start: 13 * mult, End: protocol.MaxByteCount},
|
|
})
|
|
checkQueue(t, s, map[protocol.ByteCount][]byte{
|
|
3 * mult: f3[:6*mult],
|
|
9 * mult: f2,
|
|
})
|
|
require.True(t, t1.WasCalled())
|
|
require.False(t, t2.WasCalled())
|
|
require.False(t, t3.WasCalled())
|
|
})
|
|
}
|
|
|
|
func TestFrameSorterTooManyGaps(t *testing.T) {
|
|
s := newFrameSorter()
|
|
for i := 0; i < protocol.MaxStreamFrameSorterGaps; i++ {
|
|
require.NoError(t, s.Push([]byte("foobar"), protocol.ByteCount(i*7), nil))
|
|
}
|
|
require.Equal(t, protocol.MaxStreamFrameSorterGaps, s.gaps.Len())
|
|
err := s.Push([]byte("foobar"), protocol.ByteCount(protocol.MaxStreamFrameSorterGaps*7)+100, nil)
|
|
require.EqualError(t, err, "too many gaps in received data")
|
|
}
|
|
|
|
func TestFrameSorterRandomized(t *testing.T) {
|
|
t.Run("short", func(t *testing.T) {
|
|
testFrameSorterRandomized(t, 25, false, false)
|
|
})
|
|
t.Run("long", func(t *testing.T) {
|
|
testFrameSorterRandomized(t, 2*protocol.MinStreamFrameSize, false, false)
|
|
})
|
|
t.Run("short, with duplicates", func(t *testing.T) {
|
|
testFrameSorterRandomized(t, 25, true, false)
|
|
})
|
|
t.Run("long, with duplicates", func(t *testing.T) {
|
|
testFrameSorterRandomized(t, 2*protocol.MinStreamFrameSize, true, false)
|
|
})
|
|
t.Run("short, with overlaps", func(t *testing.T) {
|
|
testFrameSorterRandomized(t, 25, false, true)
|
|
})
|
|
t.Run("long, with overlaps", func(t *testing.T) {
|
|
testFrameSorterRandomized(t, 2*protocol.MinStreamFrameSize, false, true)
|
|
})
|
|
}
|
|
|
|
func testFrameSorterRandomized(t *testing.T, dataLen protocol.ByteCount, injectDuplicates, injectOverlaps bool) {
|
|
type frame struct {
|
|
offset protocol.ByteCount
|
|
data []byte
|
|
}
|
|
|
|
const num = 1000
|
|
|
|
data := make([]byte, num*int(dataLen))
|
|
rand.Read(data)
|
|
|
|
frames := make([]frame, num)
|
|
for i := 0; i < num; i++ {
|
|
b := make([]byte, dataLen)
|
|
offset := i * int(dataLen)
|
|
copy(b, data[offset:offset+int(dataLen)])
|
|
frames[i] = frame{
|
|
offset: protocol.ByteCount(i) * dataLen,
|
|
data: b,
|
|
}
|
|
}
|
|
rand.Shuffle(len(frames), func(i, j int) { frames[i], frames[j] = frames[j], frames[i] })
|
|
|
|
s := newFrameSorter()
|
|
|
|
var callbacks []callbackTracker
|
|
for _, f := range frames {
|
|
cb, tr := getFrameSorterTestCallback(t)
|
|
require.NoError(t, s.Push(f.data, f.offset, cb))
|
|
callbacks = append(callbacks, tr)
|
|
}
|
|
if injectDuplicates {
|
|
for i := 0; i < num/10; i++ {
|
|
cb, tr := getFrameSorterTestCallback(t)
|
|
df := frames[rand.Intn(len(frames))]
|
|
require.NoError(t, s.Push(df.data, df.offset, cb))
|
|
callbacks = append(callbacks, tr)
|
|
}
|
|
}
|
|
if injectOverlaps {
|
|
finalOffset := num * dataLen
|
|
for i := 0; i < num/3; i++ {
|
|
cb, tr := getFrameSorterTestCallback(t)
|
|
startOffset := protocol.ByteCount(rand.Intn(int(finalOffset)))
|
|
endOffset := startOffset + protocol.ByteCount(rand.Intn(int(finalOffset-startOffset)))
|
|
require.NoError(t, s.Push(data[startOffset:endOffset], startOffset, cb))
|
|
callbacks = append(callbacks, tr)
|
|
}
|
|
}
|
|
require.Equal(t, 1, s.gaps.Len())
|
|
require.Equal(t, byteInterval{Start: num * dataLen, End: protocol.MaxByteCount}, s.gaps.Front().Value)
|
|
|
|
// read all data
|
|
var read []byte
|
|
for {
|
|
offset, b, cb := s.Pop()
|
|
if b == nil {
|
|
break
|
|
}
|
|
require.Equal(t, offset, protocol.ByteCount(len(read)))
|
|
read = append(read, b...)
|
|
if cb != nil {
|
|
cb()
|
|
}
|
|
}
|
|
|
|
require.Equal(t, data, read)
|
|
require.False(t, s.HasMoreData())
|
|
for _, cb := range callbacks {
|
|
require.True(t, cb.WasCalled())
|
|
}
|
|
}
|