Check in gVisor.

PiperOrigin-RevId: 194583126
Change-Id: Ica1d8821a90f74e7e745962d71801c598c652463

7 files changed, 734 insertions, 0 deletions

diff --git a/pkg/tcpip/network/fragmentation/BUILD b/pkg/tcpip/network/fragmentation/BUILD
new file mode 100644
index 000000000..78fe878ec
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/BUILD
@@ -0,0 +1,61 @@
+package(licenses = ["notice"])  # BSD
+
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//tools/go_generics:defs.bzl", "go_template_instance")
+load("//tools/go_stateify:defs.bzl", "go_stateify")
+
+go_stateify(
+    name = "fragmentation_state",
+    srcs = ["reassembler_list.go"],
+    out = "fragmentation_state.go",
+    package = "fragmentation",
+)
+
+go_template_instance(
+    name = "reassembler_list",
+    out = "reassembler_list.go",
+    package = "fragmentation",
+    prefix = "reassembler",
+    template = "//pkg/ilist:generic_list",
+    types = {
+        "Linker": "*reassembler",
+    },
+)
+
+go_library(
+    name = "fragmentation",
+    srcs = [
+        "frag_heap.go",
+        "fragmentation.go",
+        "fragmentation_state.go",
+        "reassembler.go",
+        "reassembler_list.go",
+    ],
+    importpath = "gvisor.googlesource.com/gvisor/pkg/tcpip/network/fragmentation",
+    visibility = ["//:sandbox"],
+    deps = [
+        "//pkg/log",
+        "//pkg/state",
+        "//pkg/tcpip/buffer",
+    ],
+)
+
+go_test(
+    name = "fragmentation_test",
+    size = "small",
+    srcs = [
+        "frag_heap_test.go",
+        "fragmentation_test.go",
+        "reassembler_test.go",
+    ],
+    embed = [":fragmentation"],
+    deps = ["//pkg/tcpip/buffer"],
+)
+
+filegroup(
+    name = "autogen",
+    srcs = [
+        "reassembler_list.go",
+    ],
+    visibility = ["//:sandbox"],
+)
diff --git a/pkg/tcpip/network/fragmentation/frag_heap.go b/pkg/tcpip/network/fragmentation/frag_heap.go
new file mode 100644
index 000000000..2e8512909
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/frag_heap.go
@@ -0,0 +1,67 @@
+// Copyright 2016 The Netstack Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fragmentation
+
+import (
+	"container/heap"
+	"fmt"
+
+	"gvisor.googlesource.com/gvisor/pkg/tcpip/buffer"
+)
+
+type fragment struct {
+	offset uint16
+	vv     *buffer.VectorisedView
+}
+
+type fragHeap []fragment
+
+func (h *fragHeap) Len() int {
+	return len(*h)
+}
+
+func (h *fragHeap) Less(i, j int) bool {
+	return (*h)[i].offset < (*h)[j].offset
+}
+
+func (h *fragHeap) Swap(i, j int) {
+	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
+}
+
+func (h *fragHeap) Push(x interface{}) {
+	*h = append(*h, x.(fragment))
+}
+
+func (h *fragHeap) Pop() interface{} {
+	old := *h
+	n := len(old)
+	x := old[n-1]
+	*h = old[:n-1]
+	return x
+}
+
+// reassamble empties the heap and returns a VectorisedView
+// containing a reassambled version of the fragments inside the heap.
+func (h *fragHeap) reassemble() (buffer.VectorisedView, error) {
+	curr := heap.Pop(h).(fragment)
+	views := curr.vv.Views()
+	size := curr.vv.Size()
+
+	if curr.offset != 0 {
+		return buffer.NewVectorisedView(0, nil), fmt.Errorf("offset of the first packet is != 0 (%d)", curr.offset)
+	}
+
+	for h.Len() > 0 {
+		curr := heap.Pop(h).(fragment)
+		if int(curr.offset) < size {
+			curr.vv.TrimFront(size - int(curr.offset))
+		} else if int(curr.offset) > size {
+			return buffer.NewVectorisedView(0, nil), fmt.Errorf("packet has a hole, expected offset %d, got %d", size, curr.offset)
+		}
+		size += curr.vv.Size()
+		views = append(views, curr.vv.Views()...)
+	}
+	return buffer.NewVectorisedView(size, views), nil
+}
diff --git a/pkg/tcpip/network/fragmentation/frag_heap_test.go b/pkg/tcpip/network/fragmentation/frag_heap_test.go
new file mode 100644
index 000000000..218a24d7b
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/frag_heap_test.go
@@ -0,0 +1,112 @@
+// Copyright 2016 The Netstack Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fragmentation
+
+import (
+	"container/heap"
+	"reflect"
+	"testing"
+
+	"gvisor.googlesource.com/gvisor/pkg/tcpip/buffer"
+)
+
+var reassambleTestCases = []struct {
+	comment string
+	in      []fragment
+	want    *buffer.VectorisedView
+}{
+	{
+		comment: "Non-overlapping in-order",
+		in: []fragment{
+			{offset: 0, vv: vv(1, "0")},
+			{offset: 1, vv: vv(1, "1")},
+		},
+		want: vv(2, "0", "1"),
+	},
+	{
+		comment: "Non-overlapping out-of-order",
+		in: []fragment{
+			{offset: 1, vv: vv(1, "1")},
+			{offset: 0, vv: vv(1, "0")},
+		},
+		want: vv(2, "0", "1"),
+	},
+	{
+		comment: "Duplicated packets",
+		in: []fragment{
+			{offset: 0, vv: vv(1, "0")},
+			{offset: 0, vv: vv(1, "0")},
+		},
+		want: vv(1, "0"),
+	},
+	{
+		comment: "Overlapping in-order",
+		in: []fragment{
+			{offset: 0, vv: vv(2, "01")},
+			{offset: 1, vv: vv(2, "12")},
+		},
+		want: vv(3, "01", "2"),
+	},
+	{
+		comment: "Overlapping out-of-order",
+		in: []fragment{
+			{offset: 1, vv: vv(2, "12")},
+			{offset: 0, vv: vv(2, "01")},
+		},
+		want: vv(3, "01", "2"),
+	},
+	{
+		comment: "Overlapping subset in-order",
+		in: []fragment{
+			{offset: 0, vv: vv(3, "012")},
+			{offset: 1, vv: vv(1, "1")},
+		},
+		want: vv(3, "012"),
+	},
+	{
+		comment: "Overlapping subset out-of-order",
+		in: []fragment{
+			{offset: 1, vv: vv(1, "1")},
+			{offset: 0, vv: vv(3, "012")},
+		},
+		want: vv(3, "012"),
+	},
+}
+
+func TestReassamble(t *testing.T) {
+	for _, c := range reassambleTestCases {
+		h := (fragHeap)(make([]fragment, 0, 8))
+		heap.Init(&h)
+		for _, f := range c.in {
+			heap.Push(&h, f)
+		}
+		got, _ := h.reassemble()
+
+		if !reflect.DeepEqual(got, *c.want) {
+			t.Errorf("Test \"%s\" reassembling failed. Got %v. Want %v", c.comment, got, *c.want)
+		}
+	}
+}
+
+func TestReassambleFailsForNonZeroOffset(t *testing.T) {
+	h := (fragHeap)(make([]fragment, 0, 8))
+	heap.Init(&h)
+	heap.Push(&h, fragment{offset: 1, vv: vv(1, "0")})
+	_, err := h.reassemble()
+	if err == nil {
+		t.Errorf("reassemble() did not fail when the first packet had offset != 0")
+	}
+}
+
+func TestReassambleFailsForHoles(t *testing.T) {
+	h := (fragHeap)(make([]fragment, 0, 8))
+	heap.Init(&h)
+	heap.Push(&h, fragment{offset: 0, vv: vv(1, "0")})
+	heap.Push(&h, fragment{offset: 2, vv: vv(1, "1")})
+	_, err := h.reassemble()
+	if err == nil {
+		t.Errorf("reassemble() did not fail when there was a hole in the packet")
+	}
+}
diff --git a/pkg/tcpip/network/fragmentation/fragmentation.go b/pkg/tcpip/network/fragmentation/fragmentation.go
new file mode 100644
index 000000000..a309a24c5
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/fragmentation.go
@@ -0,0 +1,124 @@
+// Copyright 2016 The Netstack Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package fragmentation contains the implementation of IP fragmentation.
+// It is based on RFC 791 and RFC 815.
+package fragmentation
+
+import (
+	"log"
+	"sync"
+	"time"
+
+	"gvisor.googlesource.com/gvisor/pkg/tcpip/buffer"
+)
+
+// DefaultReassembleTimeout is based on the linux stack: net.ipv4.ipfrag_time.
+const DefaultReassembleTimeout = 30 * time.Second
+
+// HighFragThreshold is the threshold at which we start trimming old
+// fragmented packets. Linux uses a default value of 4 MB. See
+// net.ipv4.ipfrag_high_thresh for more information.
+const HighFragThreshold = 4 << 20 // 4MB
+
+// LowFragThreshold is the threshold we reach to when we start dropping
+// older fragmented packets. It's important that we keep enough room for newer
+// packets to be re-assembled. Hence, this needs to be lower than
+// HighFragThreshold enough. Linux uses a default value of 3 MB. See
+// net.ipv4.ipfrag_low_thresh for more information.
+const LowFragThreshold = 3 << 20 // 3MB
+
+// Fragmentation is the main structure that other modules
+// of the stack should use to implement IP Fragmentation.
+type Fragmentation struct {
+	mu           sync.Mutex
+	highLimit    int
+	lowLimit     int
+	reassemblers map[uint32]*reassembler
+	rList        reassemblerList
+	size         int
+	timeout      time.Duration
+}
+
+// NewFragmentation creates a new Fragmentation.
+//
+// highMemoryLimit specifies the limit on the memory consumed
+// by the fragments stored by Fragmentation (overhead of internal data-structures
+// is not accounted). Fragments are dropped when the limit is reached.
+//
+// lowMemoryLimit specifies the limit on which we will reach by dropping
+// fragments after reaching highMemoryLimit.
+//
+// reassemblingTimeout specifes the maximum time allowed to reassemble a packet.
+// Fragments are lazily evicted only when a new a packet with an
+// already existing fragmentation-id arrives after the timeout.
+func NewFragmentation(highMemoryLimit, lowMemoryLimit int, reassemblingTimeout time.Duration) *Fragmentation {
+	if lowMemoryLimit >= highMemoryLimit {
+		lowMemoryLimit = highMemoryLimit
+	}
+
+	if lowMemoryLimit < 0 {
+		lowMemoryLimit = 0
+	}
+
+	return &Fragmentation{
+		reassemblers: make(map[uint32]*reassembler),
+		highLimit:    highMemoryLimit,
+		lowLimit:     lowMemoryLimit,
+		timeout:      reassemblingTimeout,
+	}
+}
+
+// Process processes an incoming fragment beloning to an ID
+// and returns a complete packet when all the packets belonging to that ID have been received.
+func (f *Fragmentation) Process(id uint32, first, last uint16, more bool, vv *buffer.VectorisedView) (buffer.VectorisedView, bool) {
+	f.mu.Lock()
+	r, ok := f.reassemblers[id]
+	if ok && r.tooOld(f.timeout) {
+		// This is very likely to be an id-collision or someone performing a slow-rate attack.
+		f.release(r)
+		ok = false
+	}
+	if !ok {
+		r = newReassembler(id)
+		f.reassemblers[id] = r
+		f.rList.PushFront(r)
+	}
+	f.mu.Unlock()
+
+	res, done, consumed := r.process(first, last, more, vv)
+
+	f.mu.Lock()
+	f.size += consumed
+	if done {
+		f.release(r)
+	}
+	// Evict reassemblers if we are consuming more memory than highLimit until
+	// we reach lowLimit.
+	if f.size > f.highLimit {
+		tail := f.rList.Back()
+		for f.size > f.lowLimit && tail != nil {
+			f.release(tail)
+			tail = tail.Prev()
+		}
+	}
+	f.mu.Unlock()
+	return res, done
+}
+
+func (f *Fragmentation) release(r *reassembler) {
+	// Before releasing a fragment we need to check if r is already marked as done.
+	// Otherwise, we would delete it twice.
+	if r.checkDoneOrMark() {
+		return
+	}
+
+	delete(f.reassemblers, r.id)
+	f.rList.Remove(r)
+	f.size -= r.size
+	if f.size < 0 {
+		log.Printf("memory counter < 0 (%d), this is an accounting bug that requires investigation", f.size)
+		f.size = 0
+	}
+}
diff --git a/pkg/tcpip/network/fragmentation/fragmentation_test.go b/pkg/tcpip/network/fragmentation/fragmentation_test.go
new file mode 100644
index 000000000..2f0200d26
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/fragmentation_test.go
@@ -0,0 +1,166 @@
+// Copyright 2016 The Netstack Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fragmentation
+
+import (
+	"reflect"
+	"testing"
+	"time"
+
+	"gvisor.googlesource.com/gvisor/pkg/tcpip/buffer"
+)
+
+// vv is a helper to build VectorisedView from different strings.
+func vv(size int, pieces ...string) *buffer.VectorisedView {
+	views := make([]buffer.View, len(pieces))
+	for i, p := range pieces {
+		views[i] = []byte(p)
+	}
+
+	vv := buffer.NewVectorisedView(size, views)
+	return &vv
+}
+
+func emptyVv() *buffer.VectorisedView {
+	vv := buffer.NewVectorisedView(0, nil)
+	return &vv
+}
+
+type processInput struct {
+	id    uint32
+	first uint16
+	last  uint16
+	more  bool
+	vv    *buffer.VectorisedView
+}
+
+type processOutput struct {
+	vv   *buffer.VectorisedView
+	done bool
+}
+
+var processTestCases = []struct {
+	comment string
+	in      []processInput
+	out     []processOutput
+}{
+	{
+		comment: "One ID",
+		in: []processInput{
+			{id: 0, first: 0, last: 1, more: true, vv: vv(2, "01")},
+			{id: 0, first: 2, last: 3, more: false, vv: vv(2, "23")},
+		},
+		out: []processOutput{
+			{vv: emptyVv(), done: false},
+			{vv: vv(4, "01", "23"), done: true},
+		},
+	},
+	{
+		comment: "Two IDs",
+		in: []processInput{
+			{id: 0, first: 0, last: 1, more: true, vv: vv(2, "01")},
+			{id: 1, first: 0, last: 1, more: true, vv: vv(2, "ab")},
+			{id: 1, first: 2, last: 3, more: false, vv: vv(2, "cd")},
+			{id: 0, first: 2, last: 3, more: false, vv: vv(2, "23")},
+		},
+		out: []processOutput{
+			{vv: emptyVv(), done: false},
+			{vv: emptyVv(), done: false},
+			{vv: vv(4, "ab", "cd"), done: true},
+			{vv: vv(4, "01", "23"), done: true},
+		},
+	},
+}
+
+func TestFragmentationProcess(t *testing.T) {
+	for _, c := range processTestCases {
+		f := NewFragmentation(1024, 512, DefaultReassembleTimeout)
+		for i, in := range c.in {
+			vv, done := f.Process(in.id, in.first, in.last, in.more, in.vv)
+			if !reflect.DeepEqual(vv, *(c.out[i].vv)) {
+				t.Errorf("Test \"%s\" Process() returned a wrong vv. Got %v. Want %v", c.comment, vv, *(c.out[i].vv))
+			}
+			if done != c.out[i].done {
+				t.Errorf("Test \"%s\" Process() returned a wrong done. Got %t. Want %t", c.comment, done, c.out[i].done)
+			}
+			if c.out[i].done {
+				if _, ok := f.reassemblers[in.id]; ok {
+					t.Errorf("Test \"%s\" Process() didn't remove buffer from reassemblers.", c.comment)
+				}
+				for n := f.rList.Front(); n != nil; n = n.Next() {
+					if n.id == in.id {
+						t.Errorf("Test \"%s\" Process() didn't remove buffer from rList.", c.comment)
+					}
+				}
+			}
+		}
+	}
+}
+
+func TestReassemblingTimeout(t *testing.T) {
+	timeout := time.Millisecond
+	f := NewFragmentation(1024, 512, timeout)
+	// Send first fragment with id = 0, first = 0, last = 0, and more = true.
+	f.Process(0, 0, 0, true, vv(1, "0"))
+	// Sleep more than the timeout.
+	time.Sleep(2 * timeout)
+	// Send another fragment that completes a packet.
+	// However, no packet should be reassembled because the fragment arrived after the timeout.
+	_, done := f.Process(0, 1, 1, false, vv(1, "1"))
+	if done {
+		t.Errorf("Fragmentation does not respect the reassembling timeout.")
+	}
+}
+
+func TestMemoryLimits(t *testing.T) {
+	f := NewFragmentation(3, 1, DefaultReassembleTimeout)
+	// Send first fragment with id = 0.
+	f.Process(0, 0, 0, true, vv(1, "0"))
+	// Send first fragment with id = 1.
+	f.Process(1, 0, 0, true, vv(1, "1"))
+	// Send first fragment with id = 2.
+	f.Process(2, 0, 0, true, vv(1, "2"))
+
+	// Send first fragment with id = 3. This should caused id = 0 and id = 1 to be
+	// evicted.
+	f.Process(3, 0, 0, true, vv(1, "3"))
+
+	if _, ok := f.reassemblers[0]; ok {
+		t.Errorf("Memory limits are not respected: id=0 has not been evicted.")
+	}
+	if _, ok := f.reassemblers[1]; ok {
+		t.Errorf("Memory limits are not respected: id=1 has not been evicted.")
+	}
+	if _, ok := f.reassemblers[3]; !ok {
+		t.Errorf("Implementation of memory limits is wrong: id=3 is not present.")
+	}
+}
+
+func TestMemoryLimitsIgnoresDuplicates(t *testing.T) {
+	f := NewFragmentation(1, 0, DefaultReassembleTimeout)
+	// Send first fragment with id = 0.
+	f.Process(0, 0, 0, true, vv(1, "0"))
+	// Send the same packet again.
+	f.Process(0, 0, 0, true, vv(1, "0"))
+
+	got := f.size
+	want := 1
+	if got != want {
+		t.Errorf("Wrong size, duplicates are not handled correctly: got=%d, want=%d.", got, want)
+	}
+}
+
+func TestFragmentationViewsDoNotEscape(t *testing.T) {
+	f := NewFragmentation(1024, 512, DefaultReassembleTimeout)
+	in := vv(2, "0", "1")
+	f.Process(0, 0, 1, true, in)
+	// Modify input view.
+	in.RemoveFirst()
+	got, _ := f.Process(0, 2, 2, false, vv(1, "2"))
+	want := vv(3, "0", "1", "2")
+	if !reflect.DeepEqual(got, *want) {
+		t.Errorf("Process() returned a wrong vv. Got %v. Want %v", got, *want)
+	}
+}
diff --git a/pkg/tcpip/network/fragmentation/reassembler.go b/pkg/tcpip/network/fragmentation/reassembler.go
new file mode 100644
index 000000000..0267a575d
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/reassembler.go
@@ -0,0 +1,109 @@
+// Copyright 2016 The Netstack Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fragmentation
+
+import (
+	"container/heap"
+	"fmt"
+	"math"
+	"sync"
+	"time"
+
+	"gvisor.googlesource.com/gvisor/pkg/tcpip/buffer"
+)
+
+type hole struct {
+	first   uint16
+	last    uint16
+	deleted bool
+}
+
+type reassembler struct {
+	reassemblerEntry
+	id           uint32
+	size         int
+	mu           sync.Mutex
+	holes        []hole
+	deleted      int
+	heap         fragHeap
+	done         bool
+	creationTime time.Time
+}
+
+func newReassembler(id uint32) *reassembler {
+	r := &reassembler{
+		id:           id,
+		holes:        make([]hole, 0, 16),
+		deleted:      0,
+		heap:         make(fragHeap, 0, 8),
+		creationTime: time.Now(),
+	}
+	r.holes = append(r.holes, hole{
+		first:   0,
+		last:    math.MaxUint16,
+		deleted: false})
+	return r
+}
+
+// updateHoles updates the list of holes for an incoming fragment and
+// returns true iff the fragment filled at least part of an existing hole.
+func (r *reassembler) updateHoles(first, last uint16, more bool) bool {
+	used := false
+	for i := range r.holes {
+		if r.holes[i].deleted || first > r.holes[i].last || last < r.holes[i].first {
+			continue
+		}
+		used = true
+		r.deleted++
+		r.holes[i].deleted = true
+		if first > r.holes[i].first {
+			r.holes = append(r.holes, hole{r.holes[i].first, first - 1, false})
+		}
+		if last < r.holes[i].last && more {
+			r.holes = append(r.holes, hole{last + 1, r.holes[i].last, false})
+		}
+	}
+	return used
+}
+
+func (r *reassembler) process(first, last uint16, more bool, vv *buffer.VectorisedView) (buffer.VectorisedView, bool, int) {
+	r.mu.Lock()
+	defer r.mu.Unlock()
+	consumed := 0
+	if r.done {
+		// A concurrent goroutine might have already reassembled
+		// the packet and emptied the heap while this goroutine
+		// was waiting on the mutex. We don't have to do anything in this case.
+		return buffer.NewVectorisedView(0, nil), false, consumed
+	}
+	if r.updateHoles(first, last, more) {
+		// We store the incoming packet only if it filled some holes.
+		uu := vv.Clone(nil)
+		heap.Push(&r.heap, fragment{offset: first, vv: &uu})
+		consumed = vv.Size()
+		r.size += consumed
+	}
+	// Check if all the holes have been deleted and we are ready to reassamble.
+	if r.deleted < len(r.holes) {
+		return buffer.NewVectorisedView(0, nil), false, consumed
+	}
+	res, err := r.heap.reassemble()
+	if err != nil {
+		panic(fmt.Sprintf("reassemble failed with: %v. There is probably a bug in the code handling the holes.", err))
+	}
+	return res, true, consumed
+}
+
+func (r *reassembler) tooOld(timeout time.Duration) bool {
+	return time.Now().Sub(r.creationTime) > timeout
+}
+
+func (r *reassembler) checkDoneOrMark() bool {
+	r.mu.Lock()
+	prev := r.done
+	r.done = true
+	r.mu.Unlock()
+	return prev
+}
diff --git a/pkg/tcpip/network/fragmentation/reassembler_test.go b/pkg/tcpip/network/fragmentation/reassembler_test.go
new file mode 100644
index 000000000..b64604383
--- /dev/null
+++ b/pkg/tcpip/network/fragmentation/reassembler_test.go
@@ -0,0 +1,95 @@
+// Copyright 2016 The Netstack Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fragmentation
+
+import (
+	"math"
+	"reflect"
+	"testing"
+)
+
+type updateHolesInput struct {
+	first uint16
+	last  uint16
+	more  bool
+}
+
+var holesTestCases = []struct {
+	comment string
+	in      []updateHolesInput
+	want    []hole
+}{
+	{
+		comment: "No fragments. Expected holes: {[0 -> inf]}.",
+		in:      []updateHolesInput{},
+		want:    []hole{{first: 0, last: math.MaxUint16, deleted: false}},
+	},
+	{
+		comment: "One fragment at beginning. Expected holes: {[2, inf]}.",
+		in:      []updateHolesInput{{first: 0, last: 1, more: true}},
+		want: []hole{
+			{first: 0, last: math.MaxUint16, deleted: true},
+			{first: 2, last: math.MaxUint16, deleted: false},
+		},
+	},
+	{
+		comment: "One fragment in the middle. Expected holes: {[0, 0], [3, inf]}.",
+		in:      []updateHolesInput{{first: 1, last: 2, more: true}},
+		want: []hole{
+			{first: 0, last: math.MaxUint16, deleted: true},
+			{first: 0, last: 0, deleted: false},
+			{first: 3, last: math.MaxUint16, deleted: false},
+		},
+	},
+	{
+		comment: "One fragment at the end. Expected holes: {[0, 0]}.",
+		in:      []updateHolesInput{{first: 1, last: 2, more: false}},
+		want: []hole{
+			{first: 0, last: math.MaxUint16, deleted: true},
+			{first: 0, last: 0, deleted: false},
+		},
+	},
+	{
+		comment: "One fragment completing a packet. Expected holes: {}.",
+		in:      []updateHolesInput{{first: 0, last: 1, more: false}},
+		want: []hole{
+			{first: 0, last: math.MaxUint16, deleted: true},
+		},
+	},
+	{
+		comment: "Two non-overlapping fragments completing a packet. Expected holes: {}.",
+		in: []updateHolesInput{
+			{first: 0, last: 1, more: true},
+			{first: 2, last: 3, more: false},
+		},
+		want: []hole{
+			{first: 0, last: math.MaxUint16, deleted: true},
+			{first: 2, last: math.MaxUint16, deleted: true},
+		},
+	},
+	{
+		comment: "Two overlapping fragments completing a packet. Expected holes: {}.",
+		in: []updateHolesInput{
+			{first: 0, last: 2, more: true},
+			{first: 2, last: 3, more: false},
+		},
+		want: []hole{
+			{first: 0, last: math.MaxUint16, deleted: true},
+			{first: 3, last: math.MaxUint16, deleted: true},
+		},
+	},
+}
+
+func TestUpdateHoles(t *testing.T) {
+	for _, c := range holesTestCases {
+		r := newReassembler(0)
+		for _, i := range c.in {
+			r.updateHoles(i.first, i.last, i.more)
+		}
+		if !reflect.DeepEqual(r.holes, c.want) {
+			t.Errorf("Test \"%s\" produced unexepetced holes. Got %v. Want %v", c.comment, r.holes, c.want)
+		}
+	}
+}