7 files changed, 387 insertions, 1108 deletions

diff --git a/pkg/buffer/BUILD b/pkg/buffer/BUILD
deleted file mode 100644
index 19cd28a32..000000000
--- a/pkg/buffer/BUILD
+++ /dev/null
@@ -1,46 +0,0 @@
-load("//tools:defs.bzl", "go_library", "go_test")
-load("//tools/go_generics:defs.bzl", "go_template_instance")
-
-package(licenses = ["notice"])
-
-go_template_instance(
-    name = "buffer_list",
-    out = "buffer_list.go",
-    package = "buffer",
-    prefix = "buffer",
-    template = "//pkg/ilist:generic_list",
-    types = {
-        "Element": "*buffer",
-        "Linker": "*buffer",
-    },
-)
-
-go_library(
-    name = "buffer",
-    srcs = [
-        "buffer.go",
-        "buffer_list.go",
-        "pool.go",
-        "view.go",
-        "view_unsafe.go",
-    ],
-    visibility = ["//visibility:public"],
-    deps = [
-        "//pkg/context",
-        "//pkg/log",
-    ],
-)
-
-go_test(
-    name = "buffer_test",
-    size = "small",
-    srcs = [
-        "buffer_test.go",
-        "pool_test.go",
-        "view_test.go",
-    ],
-    library = ":buffer",
-    deps = [
-        "//pkg/state",
-    ],
-)
diff --git a/pkg/buffer/buffer_list.go b/pkg/buffer/buffer_list.go
new file mode 100644
index 000000000..6b5bea3fc
--- /dev/null
+++ b/pkg/buffer/buffer_list.go
@@ -0,0 +1,221 @@
+package buffer
+
+// ElementMapper provides an identity mapping by default.
+//
+// This can be replaced to provide a struct that maps elements to linker
+// objects, if they are not the same. An ElementMapper is not typically
+// required if: Linker is left as is, Element is left as is, or Linker and
+// Element are the same type.
+type bufferElementMapper struct{}
+
+// linkerFor maps an Element to a Linker.
+//
+// This default implementation should be inlined.
+//
+//go:nosplit
+func (bufferElementMapper) linkerFor(elem *buffer) *buffer { return elem }
+
+// List is an intrusive list. Entries can be added to or removed from the list
+// in O(1) time and with no additional memory allocations.
+//
+// The zero value for List is an empty list ready to use.
+//
+// To iterate over a list (where l is a List):
+//      for e := l.Front(); e != nil; e = e.Next() {
+// 		// do something with e.
+//      }
+//
+// +stateify savable
+type bufferList struct {
+	head *buffer
+	tail *buffer
+}
+
+// Reset resets list l to the empty state.
+func (l *bufferList) Reset() {
+	l.head = nil
+	l.tail = nil
+}
+
+// Empty returns true iff the list is empty.
+//
+//go:nosplit
+func (l *bufferList) Empty() bool {
+	return l.head == nil
+}
+
+// Front returns the first element of list l or nil.
+//
+//go:nosplit
+func (l *bufferList) Front() *buffer {
+	return l.head
+}
+
+// Back returns the last element of list l or nil.
+//
+//go:nosplit
+func (l *bufferList) Back() *buffer {
+	return l.tail
+}
+
+// Len returns the number of elements in the list.
+//
+// NOTE: This is an O(n) operation.
+//
+//go:nosplit
+func (l *bufferList) Len() (count int) {
+	for e := l.Front(); e != nil; e = (bufferElementMapper{}.linkerFor(e)).Next() {
+		count++
+	}
+	return count
+}
+
+// PushFront inserts the element e at the front of list l.
+//
+//go:nosplit
+func (l *bufferList) PushFront(e *buffer) {
+	linker := bufferElementMapper{}.linkerFor(e)
+	linker.SetNext(l.head)
+	linker.SetPrev(nil)
+	if l.head != nil {
+		bufferElementMapper{}.linkerFor(l.head).SetPrev(e)
+	} else {
+		l.tail = e
+	}
+
+	l.head = e
+}
+
+// PushBack inserts the element e at the back of list l.
+//
+//go:nosplit
+func (l *bufferList) PushBack(e *buffer) {
+	linker := bufferElementMapper{}.linkerFor(e)
+	linker.SetNext(nil)
+	linker.SetPrev(l.tail)
+	if l.tail != nil {
+		bufferElementMapper{}.linkerFor(l.tail).SetNext(e)
+	} else {
+		l.head = e
+	}
+
+	l.tail = e
+}
+
+// PushBackList inserts list m at the end of list l, emptying m.
+//
+//go:nosplit
+func (l *bufferList) PushBackList(m *bufferList) {
+	if l.head == nil {
+		l.head = m.head
+		l.tail = m.tail
+	} else if m.head != nil {
+		bufferElementMapper{}.linkerFor(l.tail).SetNext(m.head)
+		bufferElementMapper{}.linkerFor(m.head).SetPrev(l.tail)
+
+		l.tail = m.tail
+	}
+	m.head = nil
+	m.tail = nil
+}
+
+// InsertAfter inserts e after b.
+//
+//go:nosplit
+func (l *bufferList) InsertAfter(b, e *buffer) {
+	bLinker := bufferElementMapper{}.linkerFor(b)
+	eLinker := bufferElementMapper{}.linkerFor(e)
+
+	a := bLinker.Next()
+
+	eLinker.SetNext(a)
+	eLinker.SetPrev(b)
+	bLinker.SetNext(e)
+
+	if a != nil {
+		bufferElementMapper{}.linkerFor(a).SetPrev(e)
+	} else {
+		l.tail = e
+	}
+}
+
+// InsertBefore inserts e before a.
+//
+//go:nosplit
+func (l *bufferList) InsertBefore(a, e *buffer) {
+	aLinker := bufferElementMapper{}.linkerFor(a)
+	eLinker := bufferElementMapper{}.linkerFor(e)
+
+	b := aLinker.Prev()
+	eLinker.SetNext(a)
+	eLinker.SetPrev(b)
+	aLinker.SetPrev(e)
+
+	if b != nil {
+		bufferElementMapper{}.linkerFor(b).SetNext(e)
+	} else {
+		l.head = e
+	}
+}
+
+// Remove removes e from l.
+//
+//go:nosplit
+func (l *bufferList) Remove(e *buffer) {
+	linker := bufferElementMapper{}.linkerFor(e)
+	prev := linker.Prev()
+	next := linker.Next()
+
+	if prev != nil {
+		bufferElementMapper{}.linkerFor(prev).SetNext(next)
+	} else if l.head == e {
+		l.head = next
+	}
+
+	if next != nil {
+		bufferElementMapper{}.linkerFor(next).SetPrev(prev)
+	} else if l.tail == e {
+		l.tail = prev
+	}
+
+	linker.SetNext(nil)
+	linker.SetPrev(nil)
+}
+
+// Entry is a default implementation of Linker. Users can add anonymous fields
+// of this type to their structs to make them automatically implement the
+// methods needed by List.
+//
+// +stateify savable
+type bufferEntry struct {
+	next *buffer
+	prev *buffer
+}
+
+// Next returns the entry that follows e in the list.
+//
+//go:nosplit
+func (e *bufferEntry) Next() *buffer {
+	return e.next
+}
+
+// Prev returns the entry that precedes e in the list.
+//
+//go:nosplit
+func (e *bufferEntry) Prev() *buffer {
+	return e.prev
+}
+
+// SetNext assigns 'entry' as the entry that follows e in the list.
+//
+//go:nosplit
+func (e *bufferEntry) SetNext(elem *buffer) {
+	e.next = elem
+}
+
+// SetPrev assigns 'entry' as the entry that precedes e in the list.
+//
+//go:nosplit
+func (e *bufferEntry) SetPrev(elem *buffer) {
+	e.prev = elem
+}
diff --git a/pkg/buffer/buffer_state_autogen.go b/pkg/buffer/buffer_state_autogen.go
new file mode 100644
index 000000000..aaa72b723
--- /dev/null
+++ b/pkg/buffer/buffer_state_autogen.go
@@ -0,0 +1,163 @@
+// automatically generated by stateify.
+
+package buffer
+
+import (
+	"gvisor.dev/gvisor/pkg/state"
+)
+
+func (b *buffer) StateTypeName() string {
+	return "pkg/buffer.buffer"
+}
+
+func (b *buffer) StateFields() []string {
+	return []string{
+		"data",
+		"read",
+		"write",
+		"bufferEntry",
+	}
+}
+
+func (b *buffer) beforeSave() {}
+
+// +checklocksignore
+func (b *buffer) StateSave(stateSinkObject state.Sink) {
+	b.beforeSave()
+	stateSinkObject.Save(0, &b.data)
+	stateSinkObject.Save(1, &b.read)
+	stateSinkObject.Save(2, &b.write)
+	stateSinkObject.Save(3, &b.bufferEntry)
+}
+
+func (b *buffer) afterLoad() {}
+
+// +checklocksignore
+func (b *buffer) StateLoad(stateSourceObject state.Source) {
+	stateSourceObject.Load(0, &b.data)
+	stateSourceObject.Load(1, &b.read)
+	stateSourceObject.Load(2, &b.write)
+	stateSourceObject.Load(3, &b.bufferEntry)
+}
+
+func (l *bufferList) StateTypeName() string {
+	return "pkg/buffer.bufferList"
+}
+
+func (l *bufferList) StateFields() []string {
+	return []string{
+		"head",
+		"tail",
+	}
+}
+
+func (l *bufferList) beforeSave() {}
+
+// +checklocksignore
+func (l *bufferList) StateSave(stateSinkObject state.Sink) {
+	l.beforeSave()
+	stateSinkObject.Save(0, &l.head)
+	stateSinkObject.Save(1, &l.tail)
+}
+
+func (l *bufferList) afterLoad() {}
+
+// +checklocksignore
+func (l *bufferList) StateLoad(stateSourceObject state.Source) {
+	stateSourceObject.Load(0, &l.head)
+	stateSourceObject.Load(1, &l.tail)
+}
+
+func (e *bufferEntry) StateTypeName() string {
+	return "pkg/buffer.bufferEntry"
+}
+
+func (e *bufferEntry) StateFields() []string {
+	return []string{
+		"next",
+		"prev",
+	}
+}
+
+func (e *bufferEntry) beforeSave() {}
+
+// +checklocksignore
+func (e *bufferEntry) StateSave(stateSinkObject state.Sink) {
+	e.beforeSave()
+	stateSinkObject.Save(0, &e.next)
+	stateSinkObject.Save(1, &e.prev)
+}
+
+func (e *bufferEntry) afterLoad() {}
+
+// +checklocksignore
+func (e *bufferEntry) StateLoad(stateSourceObject state.Source) {
+	stateSourceObject.Load(0, &e.next)
+	stateSourceObject.Load(1, &e.prev)
+}
+
+func (p *pool) StateTypeName() string {
+	return "pkg/buffer.pool"
+}
+
+func (p *pool) StateFields() []string {
+	return []string{
+		"bufferSize",
+		"embeddedStorage",
+	}
+}
+
+func (p *pool) beforeSave() {}
+
+// +checklocksignore
+func (p *pool) StateSave(stateSinkObject state.Sink) {
+	p.beforeSave()
+	stateSinkObject.Save(0, &p.bufferSize)
+	stateSinkObject.Save(1, &p.embeddedStorage)
+}
+
+// +checklocksignore
+func (p *pool) StateLoad(stateSourceObject state.Source) {
+	stateSourceObject.Load(0, &p.bufferSize)
+	stateSourceObject.LoadWait(1, &p.embeddedStorage)
+	stateSourceObject.AfterLoad(p.afterLoad)
+}
+
+func (v *View) StateTypeName() string {
+	return "pkg/buffer.View"
+}
+
+func (v *View) StateFields() []string {
+	return []string{
+		"data",
+		"size",
+		"pool",
+	}
+}
+
+func (v *View) beforeSave() {}
+
+// +checklocksignore
+func (v *View) StateSave(stateSinkObject state.Sink) {
+	v.beforeSave()
+	stateSinkObject.Save(0, &v.data)
+	stateSinkObject.Save(1, &v.size)
+	stateSinkObject.Save(2, &v.pool)
+}
+
+func (v *View) afterLoad() {}
+
+// +checklocksignore
+func (v *View) StateLoad(stateSourceObject state.Source) {
+	stateSourceObject.Load(0, &v.data)
+	stateSourceObject.Load(1, &v.size)
+	stateSourceObject.Load(2, &v.pool)
+}
+
+func init() {
+	state.Register((*buffer)(nil))
+	state.Register((*bufferList)(nil))
+	state.Register((*bufferEntry)(nil))
+	state.Register((*pool)(nil))
+	state.Register((*View)(nil))
+}
diff --git a/pkg/buffer/buffer_test.go b/pkg/buffer/buffer_test.go
deleted file mode 100644
index 32db841e4..000000000
--- a/pkg/buffer/buffer_test.go
+++ /dev/null
@@ -1,111 +0,0 @@
-// Copyright 2021 The gVisor Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package buffer
-
-import (
-	"bytes"
-	"testing"
-)
-
-func TestBufferRemove(t *testing.T) {
-	sample := []byte("01234567")
-
-	// Success cases
-	for _, tc := range []struct {
-		desc string
-		data []byte
-		rng  Range
-		want []byte
-	}{
-		{
-			desc: "empty slice",
-		},
-		{
-			desc: "empty range",
-			data: sample,
-			want: sample,
-		},
-		{
-			desc: "empty range with positive begin",
-			data: sample,
-			rng:  Range{begin: 1, end: 1},
-			want: sample,
-		},
-		{
-			desc: "range at beginning",
-			data: sample,
-			rng:  Range{begin: 0, end: 1},
-			want: sample[1:],
-		},
-		{
-			desc: "range in middle",
-			data: sample,
-			rng:  Range{begin: 2, end: 4},
-			want: []byte("014567"),
-		},
-		{
-			desc: "range at end",
-			data: sample,
-			rng:  Range{begin: 7, end: 8},
-			want: sample[:7],
-		},
-		{
-			desc: "range all",
-			data: sample,
-			rng:  Range{begin: 0, end: 8},
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			var buf buffer
-			buf.initWithData(tc.data)
-			if ok := buf.Remove(tc.rng); !ok {
-				t.Errorf("buf.Remove(%#v) = false, want true", tc.rng)
-			} else if got := buf.ReadSlice(); !bytes.Equal(got, tc.want) {
-				t.Errorf("buf.ReadSlice() = %q, want %q", got, tc.want)
-			}
-		})
-	}
-
-	// Failure cases
-	for _, tc := range []struct {
-		desc string
-		data []byte
-		rng  Range
-	}{
-		{
-			desc: "begin out-of-range",
-			data: sample,
-			rng:  Range{begin: -1, end: 4},
-		},
-		{
-			desc: "end out-of-range",
-			data: sample,
-			rng:  Range{begin: 4, end: 9},
-		},
-		{
-			desc: "both out-of-range",
-			data: sample,
-			rng:  Range{begin: -100, end: 100},
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			var buf buffer
-			buf.initWithData(tc.data)
-			if ok := buf.Remove(tc.rng); ok {
-				t.Errorf("buf.Remove(%#v) = true, want false", tc.rng)
-			}
-		})
-	}
-}
diff --git a/pkg/buffer/buffer_unsafe_state_autogen.go b/pkg/buffer/buffer_unsafe_state_autogen.go
new file mode 100644
index 000000000..5a5c40722
--- /dev/null
+++ b/pkg/buffer/buffer_unsafe_state_autogen.go
@@ -0,0 +1,3 @@
+// automatically generated by stateify.
+
+package buffer
diff --git a/pkg/buffer/pool_test.go b/pkg/buffer/pool_test.go
deleted file mode 100644
index 8584bac89..000000000
--- a/pkg/buffer/pool_test.go
+++ /dev/null
@@ -1,51 +0,0 @@
-// Copyright 2020 The gVisor Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package buffer
-
-import (
-	"testing"
-)
-
-func TestGetDefaultBufferSize(t *testing.T) {
-	var p pool
-	for i := 0; i < embeddedCount*2; i++ {
-		buf := p.get()
-		if got, want := len(buf.data), defaultBufferSize; got != want {
-			t.Errorf("#%d len(buf.data) = %d, want %d", i, got, want)
-		}
-	}
-}
-
-func TestGetCustomBufferSize(t *testing.T) {
-	const size = 100
-
-	var p pool
-	p.setBufferSize(size)
-	for i := 0; i < embeddedCount*2; i++ {
-		buf := p.get()
-		if got, want := len(buf.data), size; got != want {
-			t.Errorf("#%d len(buf.data) = %d, want %d", i, got, want)
-		}
-	}
-}
-
-func TestPut(t *testing.T) {
-	var p pool
-	buf := p.get()
-	p.put(buf)
-	if buf.data != nil {
-		t.Errorf("buf.data = %x, want nil", buf.data)
-	}
-}
diff --git a/pkg/buffer/view_test.go b/pkg/buffer/view_test.go
deleted file mode 100644
index 796efa240..000000000
--- a/pkg/buffer/view_test.go
+++ /dev/null
@@ -1,900 +0,0 @@
-// Copyright 2020 The gVisor Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package buffer
-
-import (
-	"bytes"
-	"context"
-	"fmt"
-	"io"
-	"reflect"
-	"strings"
-	"testing"
-
-	"gvisor.dev/gvisor/pkg/state"
-)
-
-const bufferSize = defaultBufferSize
-
-func fillAppend(v *View, data []byte) {
-	v.Append(data)
-}
-
-func fillAppendEnd(v *View, data []byte) {
-	v.Grow(bufferSize-1, false)
-	v.Append(data)
-	v.TrimFront(bufferSize - 1)
-}
-
-func fillWriteFromReader(v *View, data []byte) {
-	b := bytes.NewBuffer(data)
-	v.WriteFromReader(b, int64(len(data)))
-}
-
-func fillWriteFromReaderEnd(v *View, data []byte) {
-	v.Grow(bufferSize-1, false)
-	b := bytes.NewBuffer(data)
-	v.WriteFromReader(b, int64(len(data)))
-	v.TrimFront(bufferSize - 1)
-}
-
-var fillFuncs = map[string]func(*View, []byte){
-	"append":             fillAppend,
-	"appendEnd":          fillAppendEnd,
-	"writeFromReader":    fillWriteFromReader,
-	"writeFromReaderEnd": fillWriteFromReaderEnd,
-}
-
-func BenchmarkReadAt(b *testing.B) {
-	b.ReportAllocs()
-	var v View
-	v.Append(make([]byte, 100))
-
-	buf := make([]byte, 10)
-	for i := 0; i < b.N; i++ {
-		v.ReadAt(buf, 0)
-	}
-}
-
-func BenchmarkWriteRead(b *testing.B) {
-	b.ReportAllocs()
-	var v View
-	sz := 1000
-	wbuf := make([]byte, sz)
-	rbuf := bytes.NewBuffer(make([]byte, sz))
-	for i := 0; i < b.N; i++ {
-		v.Append(wbuf)
-		rbuf.Reset()
-		v.ReadToWriter(rbuf, int64(sz))
-	}
-}
-
-func testReadAt(t *testing.T, v *View, offset int64, n int, wantStr string, wantErr error) {
-	t.Helper()
-	d := make([]byte, n)
-	n, err := v.ReadAt(d, offset)
-	if n != len(wantStr) {
-		t.Errorf("got %d, want %d", n, len(wantStr))
-	}
-	if err != wantErr {
-		t.Errorf("got err %v, want %v", err, wantErr)
-	}
-	if !bytes.Equal(d[:n], []byte(wantStr)) {
-		t.Errorf("got %q, want %q", string(d[:n]), wantStr)
-	}
-}
-
-func TestView(t *testing.T) {
-	testCases := []struct {
-		name   string
-		input  string
-		output string
-		op     func(*testing.T, *View)
-	}{
-		// Preconditions.
-		{
-			name:   "truncate-check",
-			input:  "hello",
-			output: "hello", // Not touched.
-			op: func(t *testing.T, v *View) {
-				defer func() {
-					if r := recover(); r == nil {
-						t.Errorf("Truncate(-1) did not panic")
-					}
-				}()
-				v.Truncate(-1)
-			},
-		},
-		{
-			name:   "grow-check",
-			input:  "hello",
-			output: "hello", // Not touched.
-			op: func(t *testing.T, v *View) {
-				defer func() {
-					if r := recover(); r == nil {
-						t.Errorf("Grow(-1) did not panic")
-					}
-				}()
-				v.Grow(-1, false)
-			},
-		},
-		{
-			name:   "advance-check",
-			input:  "hello",
-			output: "", // Consumed.
-			op: func(t *testing.T, v *View) {
-				defer func() {
-					if r := recover(); r == nil {
-						t.Errorf("advanceRead(Size()+1) did not panic")
-					}
-				}()
-				v.advanceRead(v.Size() + 1)
-			},
-		},
-
-		// Prepend.
-		{
-			name:   "prepend",
-			input:  "world",
-			output: "hello world",
-			op: func(t *testing.T, v *View) {
-				v.Prepend([]byte("hello "))
-			},
-		},
-		{
-			name:   "prepend-backfill-full",
-			input:  "hello world",
-			output: "jello world",
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(1)
-				v.Prepend([]byte("j"))
-			},
-		},
-		{
-			name:   "prepend-backfill-under",
-			input:  "hello world",
-			output: "hola world",
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(5)
-				v.Prepend([]byte("hola"))
-			},
-		},
-		{
-			name:   "prepend-backfill-over",
-			input:  "hello world",
-			output: "smello world",
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(1)
-				v.Prepend([]byte("sm"))
-			},
-		},
-		{
-			name:   "prepend-fill",
-			input:  strings.Repeat("1", bufferSize-1),
-			output: "0" + strings.Repeat("1", bufferSize-1),
-			op: func(t *testing.T, v *View) {
-				v.Prepend([]byte("0"))
-			},
-		},
-		{
-			name:   "prepend-overflow",
-			input:  strings.Repeat("1", bufferSize),
-			output: "0" + strings.Repeat("1", bufferSize),
-			op: func(t *testing.T, v *View) {
-				v.Prepend([]byte("0"))
-			},
-		},
-		{
-			name:   "prepend-multiple-buffers",
-			input:  strings.Repeat("1", bufferSize-1),
-			output: strings.Repeat("0", bufferSize*3) + strings.Repeat("1", bufferSize-1),
-			op: func(t *testing.T, v *View) {
-				v.Prepend([]byte(strings.Repeat("0", bufferSize*3)))
-			},
-		},
-
-		// Append and write.
-		{
-			name:   "append",
-			input:  "hello",
-			output: "hello world",
-			op: func(t *testing.T, v *View) {
-				v.Append([]byte(" world"))
-			},
-		},
-		{
-			name:   "append-fill",
-			input:  strings.Repeat("1", bufferSize-1),
-			output: strings.Repeat("1", bufferSize-1) + "0",
-			op: func(t *testing.T, v *View) {
-				v.Append([]byte("0"))
-			},
-		},
-		{
-			name:   "append-overflow",
-			input:  strings.Repeat("1", bufferSize),
-			output: strings.Repeat("1", bufferSize) + "0",
-			op: func(t *testing.T, v *View) {
-				v.Append([]byte("0"))
-			},
-		},
-		{
-			name:   "append-multiple-buffers",
-			input:  strings.Repeat("1", bufferSize-1),
-			output: strings.Repeat("1", bufferSize-1) + strings.Repeat("0", bufferSize*3),
-			op: func(t *testing.T, v *View) {
-				v.Append([]byte(strings.Repeat("0", bufferSize*3)))
-			},
-		},
-
-		// AppendOwned.
-		{
-			name:   "append-owned",
-			input:  "hello",
-			output: "hello world",
-			op: func(t *testing.T, v *View) {
-				b := []byte("Xworld")
-				v.AppendOwned(b)
-				b[0] = ' '
-			},
-		},
-
-		// Truncate.
-		{
-			name:   "truncate",
-			input:  "hello world",
-			output: "hello",
-			op: func(t *testing.T, v *View) {
-				v.Truncate(5)
-			},
-		},
-		{
-			name:   "truncate-noop",
-			input:  "hello world",
-			output: "hello world",
-			op: func(t *testing.T, v *View) {
-				v.Truncate(v.Size() + 1)
-			},
-		},
-		{
-			name:   "truncate-multiple-buffers",
-			input:  strings.Repeat("1", bufferSize*2),
-			output: strings.Repeat("1", bufferSize*2-1),
-			op: func(t *testing.T, v *View) {
-				v.Truncate(bufferSize*2 - 1)
-			},
-		},
-		{
-			name:   "truncate-multiple-buffers-to-one",
-			input:  strings.Repeat("1", bufferSize*2),
-			output: "11111",
-			op: func(t *testing.T, v *View) {
-				v.Truncate(5)
-			},
-		},
-
-		// TrimFront.
-		{
-			name:   "trim",
-			input:  "hello world",
-			output: "world",
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(6)
-			},
-		},
-		{
-			name:   "trim-too-large",
-			input:  "hello world",
-			output: "",
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(v.Size() + 1)
-			},
-		},
-		{
-			name:   "trim-multiple-buffers",
-			input:  strings.Repeat("1", bufferSize*2),
-			output: strings.Repeat("1", bufferSize*2-1),
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(1)
-			},
-		},
-		{
-			name:   "trim-multiple-buffers-to-one-buffer",
-			input:  strings.Repeat("1", bufferSize*2),
-			output: "1",
-			op: func(t *testing.T, v *View) {
-				v.TrimFront(bufferSize*2 - 1)
-			},
-		},
-
-		// Grow.
-		{
-			name:   "grow",
-			input:  "hello world",
-			output: "hello world",
-			op: func(t *testing.T, v *View) {
-				v.Grow(1, true)
-			},
-		},
-		{
-			name:   "grow-from-zero",
-			output: strings.Repeat("\x00", 1024),
-			op: func(t *testing.T, v *View) {
-				v.Grow(1024, true)
-			},
-		},
-		{
-			name:   "grow-from-non-zero",
-			input:  strings.Repeat("1", bufferSize),
-			output: strings.Repeat("1", bufferSize) + strings.Repeat("\x00", bufferSize),
-			op: func(t *testing.T, v *View) {
-				v.Grow(bufferSize*2, true)
-			},
-		},
-
-		// Copy.
-		{
-			name:   "copy",
-			input:  "hello",
-			output: "hello",
-			op: func(t *testing.T, v *View) {
-				other := v.Copy()
-				bs := other.Flatten()
-				want := []byte("hello")
-				if !bytes.Equal(bs, want) {
-					t.Errorf("expected %v, got %v", want, bs)
-				}
-			},
-		},
-		{
-			name:   "copy-large",
-			input:  strings.Repeat("1", bufferSize+1),
-			output: strings.Repeat("1", bufferSize+1),
-			op: func(t *testing.T, v *View) {
-				other := v.Copy()
-				bs := other.Flatten()
-				want := []byte(strings.Repeat("1", bufferSize+1))
-				if !bytes.Equal(bs, want) {
-					t.Errorf("expected %v, got %v", want, bs)
-				}
-			},
-		},
-
-		// Merge.
-		{
-			name:   "merge",
-			input:  "hello",
-			output: "hello world",
-			op: func(t *testing.T, v *View) {
-				var other View
-				other.Append([]byte(" world"))
-				v.Merge(&other)
-				if sz := other.Size(); sz != 0 {
-					t.Errorf("expected 0, got %d", sz)
-				}
-			},
-		},
-		{
-			name:   "merge-large",
-			input:  strings.Repeat("1", bufferSize+1),
-			output: strings.Repeat("1", bufferSize+1) + strings.Repeat("0", bufferSize+1),
-			op: func(t *testing.T, v *View) {
-				var other View
-				other.Append([]byte(strings.Repeat("0", bufferSize+1)))
-				v.Merge(&other)
-				if sz := other.Size(); sz != 0 {
-					t.Errorf("expected 0, got %d", sz)
-				}
-			},
-		},
-
-		// ReadAt.
-		{
-			name:   "readat",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, 0, 6, "hello", io.EOF) },
-		},
-		{
-			name:   "readat-long",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, 0, 8, "hello", io.EOF) },
-		},
-		{
-			name:   "readat-short",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, 0, 3, "hel", nil) },
-		},
-		{
-			name:   "readat-offset",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, 2, 3, "llo", io.EOF) },
-		},
-		{
-			name:   "readat-long-offset",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, 2, 8, "llo", io.EOF) },
-		},
-		{
-			name:   "readat-short-offset",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, 2, 2, "ll", nil) },
-		},
-		{
-			name:   "readat-skip-all",
-			input:  "hello",
-			output: "hello",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, bufferSize+1, 1, "", io.EOF) },
-		},
-		{
-			name:   "readat-second-buffer",
-			input:  strings.Repeat("0", bufferSize+1) + "12",
-			output: strings.Repeat("0", bufferSize+1) + "12",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, bufferSize+1, 1, "1", nil) },
-		},
-		{
-			name:   "readat-second-buffer-end",
-			input:  strings.Repeat("0", bufferSize+1) + "12",
-			output: strings.Repeat("0", bufferSize+1) + "12",
-			op:     func(t *testing.T, v *View) { testReadAt(t, v, bufferSize+1, 2, "12", io.EOF) },
-		},
-	}
-
-	for _, tc := range testCases {
-		for fillName, fn := range fillFuncs {
-			t.Run(fillName+"/"+tc.name, func(t *testing.T) {
-				// Construct & fill the view.
-				var view View
-				fn(&view, []byte(tc.input))
-
-				// Run the operation.
-				if tc.op != nil {
-					tc.op(t, &view)
-				}
-
-				// Flatten and validate.
-				out := view.Flatten()
-				if !bytes.Equal([]byte(tc.output), out) {
-					t.Errorf("expected %q, got %q", tc.output, string(out))
-				}
-
-				// Ensure the size is correct.
-				if len(out) != int(view.Size()) {
-					t.Errorf("size is wrong: expected %d, got %d", len(out), view.Size())
-				}
-
-				// Calculate contents via apply.
-				var appliedOut []byte
-				view.Apply(func(b []byte) {
-					appliedOut = append(appliedOut, b...)
-				})
-				if len(appliedOut) != len(out) {
-					t.Errorf("expected %d, got %d", len(out), len(appliedOut))
-				}
-				if !bytes.Equal(appliedOut, out) {
-					t.Errorf("expected %v, got %v", out, appliedOut)
-				}
-
-				// Calculate contents via ReadToWriter.
-				var b bytes.Buffer
-				n, err := view.ReadToWriter(&b, int64(len(out)))
-				if n != int64(len(out)) {
-					t.Errorf("expected %d, got %d", len(out), n)
-				}
-				if err != nil {
-					t.Errorf("expected nil, got %v", err)
-				}
-				if !bytes.Equal(b.Bytes(), out) {
-					t.Errorf("expected %v, got %v", out, b.Bytes())
-				}
-			})
-		}
-	}
-}
-
-func TestViewPullUp(t *testing.T) {
-	for _, tc := range []struct {
-		desc   string
-		inputs []string
-		offset int
-		length int
-		output string
-		failed bool
-		// lengths is the lengths of each buffer node after the pull up.
-		lengths []int
-	}{
-		{
-			desc: "whole empty view",
-		},
-		{
-			desc:    "zero pull",
-			inputs:  []string{"hello", " world"},
-			lengths: []int{5, 6},
-		},
-		{
-			desc:    "whole view",
-			inputs:  []string{"hello", " world"},
-			offset:  0,
-			length:  11,
-			output:  "hello world",
-			lengths: []int{11},
-		},
-		{
-			desc:    "middle to end aligned",
-			inputs:  []string{"0123", "45678", "9abcd"},
-			offset:  4,
-			length:  10,
-			output:  "456789abcd",
-			lengths: []int{4, 10},
-		},
-		{
-			desc:    "middle to end unaligned",
-			inputs:  []string{"0123", "45678", "9abcd"},
-			offset:  6,
-			length:  8,
-			output:  "6789abcd",
-			lengths: []int{4, 10},
-		},
-		{
-			desc:    "middle aligned",
-			inputs:  []string{"0123", "45678", "9abcd", "efgh"},
-			offset:  6,
-			length:  5,
-			output:  "6789a",
-			lengths: []int{4, 10, 4},
-		},
-
-		// Failed cases.
-		{
-			desc:   "empty view - length too long",
-			offset: 0,
-			length: 1,
-			failed: true,
-		},
-		{
-			desc:   "empty view - offset too large",
-			offset: 1,
-			length: 1,
-			failed: true,
-		},
-		{
-			desc:    "length too long",
-			inputs:  []string{"0123", "45678", "9abcd"},
-			offset:  4,
-			length:  100,
-			failed:  true,
-			lengths: []int{4, 5, 5},
-		},
-		{
-			desc:    "offset too large",
-			inputs:  []string{"0123", "45678", "9abcd"},
-			offset:  100,
-			length:  1,
-			failed:  true,
-			lengths: []int{4, 5, 5},
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			var v View
-			for _, s := range tc.inputs {
-				v.AppendOwned([]byte(s))
-			}
-
-			got, gotOk := v.PullUp(tc.offset, tc.length)
-			want, wantOk := []byte(tc.output), !tc.failed
-			if gotOk != wantOk || !bytes.Equal(got, want) {
-				t.Errorf("v.PullUp(%d, %d) = %q, %t; %q, %t", tc.offset, tc.length, got, gotOk, want, wantOk)
-			}
-
-			var gotLengths []int
-			for buf := v.data.Front(); buf != nil; buf = buf.Next() {
-				gotLengths = append(gotLengths, buf.ReadSize())
-			}
-			if !reflect.DeepEqual(gotLengths, tc.lengths) {
-				t.Errorf("lengths = %v; want %v", gotLengths, tc.lengths)
-			}
-		})
-	}
-}
-
-func TestViewRemove(t *testing.T) {
-	// Success cases
-	for _, tc := range []struct {
-		desc string
-		// before is the contents for each buffer node initially.
-		before []string
-		// after is the contents for each buffer node after removal.
-		after  []string
-		offset int
-		length int
-	}{
-		{
-			desc: "empty view",
-		},
-		{
-			desc:   "nothing removed",
-			before: []string{"hello", " world"},
-			after:  []string{"hello", " world"},
-		},
-		{
-			desc:   "whole view",
-			before: []string{"hello", " world"},
-			offset: 0,
-			length: 11,
-		},
-		{
-			desc:   "beginning to middle aligned",
-			before: []string{"0123", "45678", "9abcd"},
-			after:  []string{"9abcd"},
-			offset: 0,
-			length: 9,
-		},
-		{
-			desc:   "beginning to middle unaligned",
-			before: []string{"0123", "45678", "9abcd"},
-			after:  []string{"678", "9abcd"},
-			offset: 0,
-			length: 6,
-		},
-		{
-			desc:   "middle to end aligned",
-			before: []string{"0123", "45678", "9abcd"},
-			after:  []string{"0123"},
-			offset: 4,
-			length: 10,
-		},
-		{
-			desc:   "middle to end unaligned",
-			before: []string{"0123", "45678", "9abcd"},
-			after:  []string{"0123", "45"},
-			offset: 6,
-			length: 8,
-		},
-		{
-			desc:   "middle aligned",
-			before: []string{"0123", "45678", "9abcd"},
-			after:  []string{"0123", "9abcd"},
-			offset: 4,
-			length: 5,
-		},
-		{
-			desc:   "middle unaligned",
-			before: []string{"0123", "45678", "9abcd"},
-			after:  []string{"0123", "4578", "9abcd"},
-			offset: 6,
-			length: 1,
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			var v View
-			for _, s := range tc.before {
-				v.AppendOwned([]byte(s))
-			}
-
-			if ok := v.Remove(tc.offset, tc.length); !ok {
-				t.Errorf("v.Remove(%d, %d) = false, want true", tc.offset, tc.length)
-			}
-
-			var got []string
-			for buf := v.data.Front(); buf != nil; buf = buf.Next() {
-				got = append(got, string(buf.ReadSlice()))
-			}
-			if !reflect.DeepEqual(got, tc.after) {
-				t.Errorf("after = %v; want %v", got, tc.after)
-			}
-		})
-	}
-
-	// Failure cases
-	for _, tc := range []struct {
-		desc string
-		// before is the contents for each buffer node initially.
-		before []string
-		offset int
-		length int
-	}{
-		{
-			desc:   "offset out-of-range",
-			before: []string{"hello", " world"},
-			offset: -1,
-			length: 3,
-		},
-		{
-			desc:   "length too long",
-			before: []string{"hello", " world"},
-			offset: 0,
-			length: 12,
-		},
-		{
-			desc:   "length too long with positive offset",
-			before: []string{"hello", " world"},
-			offset: 3,
-			length: 9,
-		},
-		{
-			desc:   "length negative",
-			before: []string{"hello", " world"},
-			offset: 0,
-			length: -1,
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			var v View
-			for _, s := range tc.before {
-				v.AppendOwned([]byte(s))
-			}
-			if ok := v.Remove(tc.offset, tc.length); ok {
-				t.Errorf("v.Remove(%d, %d) = true, want false", tc.offset, tc.length)
-			}
-		})
-	}
-}
-
-func TestViewSubApply(t *testing.T) {
-	var v View
-	v.AppendOwned([]byte("0123"))
-	v.AppendOwned([]byte("45678"))
-	v.AppendOwned([]byte("9abcd"))
-
-	data := []byte("0123456789abcd")
-
-	for i := 0; i <= len(data); i++ {
-		for j := i; j <= len(data); j++ {
-			t.Run(fmt.Sprintf("SubApply(%d,%d)", i, j), func(t *testing.T) {
-				var got []byte
-				v.SubApply(i, j-i, func(b []byte) {
-					got = append(got, b...)
-				})
-				if want := data[i:j]; !bytes.Equal(got, want) {
-					t.Errorf("got = %q; want %q", got, want)
-				}
-			})
-		}
-	}
-}
-
-func doSaveAndLoad(t *testing.T, toSave, toLoad *View) {
-	t.Helper()
-	var buf bytes.Buffer
-	ctx := context.Background()
-	if _, err := state.Save(ctx, &buf, toSave); err != nil {
-		t.Fatal("state.Save:", err)
-	}
-	if _, err := state.Load(ctx, bytes.NewReader(buf.Bytes()), toLoad); err != nil {
-		t.Fatal("state.Load:", err)
-	}
-}
-
-func TestSaveRestoreViewEmpty(t *testing.T) {
-	var toSave View
-	var v View
-	doSaveAndLoad(t, &toSave, &v)
-
-	if got := v.pool.avail; got != nil {
-		t.Errorf("pool is not in zero state: v.pool.avail = %v, want nil", got)
-	}
-	if got := v.Flatten(); len(got) != 0 {
-		t.Errorf("v.Flatten() = %x, want []", got)
-	}
-}
-
-func TestSaveRestoreView(t *testing.T) {
-	// Create data that fits 2.5 slots.
-	data := bytes.Join([][]byte{
-		bytes.Repeat([]byte{1, 2}, defaultBufferSize),
-		bytes.Repeat([]byte{3}, defaultBufferSize/2),
-	}, nil)
-
-	var toSave View
-	toSave.Append(data)
-
-	var v View
-	doSaveAndLoad(t, &toSave, &v)
-
-	// Next available slot at index 3; 0-2 slot are used.
-	i := 3
-	if got, want := &v.pool.avail[0], &v.pool.embeddedStorage[i]; got != want {
-		t.Errorf("next available buffer points to %p, want %p (&v.pool.embeddedStorage[%d])", got, want, i)
-	}
-	if got := v.Flatten(); !bytes.Equal(got, data) {
-		t.Errorf("v.Flatten() = %x, want %x", got, data)
-	}
-}
-
-func TestRangeIntersect(t *testing.T) {
-	for _, tc := range []struct {
-		desc       string
-		x, y, want Range
-	}{
-		{
-			desc: "empty intersects empty",
-		},
-		{
-			desc: "empty intersection",
-			x:    Range{end: 10},
-			y:    Range{begin: 10, end: 20},
-		},
-		{
-			desc: "some intersection",
-			x:    Range{begin: 5, end: 20},
-			y:    Range{end: 10},
-			want: Range{begin: 5, end: 10},
-		},
-	} {
-		t.Run(tc.desc, func(t *testing.T) {
-			if got := tc.x.Intersect(tc.y); got != tc.want {
-				t.Errorf("(%#v).Intersect(%#v) = %#v; want %#v", tc.x, tc.y, got, tc.want)
-			}
-			if got := tc.y.Intersect(tc.x); got != tc.want {
-				t.Errorf("(%#v).Intersect(%#v) = %#v; want %#v", tc.y, tc.x, got, tc.want)
-			}
-		})
-	}
-}
-
-func TestRangeOffset(t *testing.T) {
-	for _, tc := range []struct {
-		input  Range
-		offset int
-		output Range
-	}{
-		{
-			input:  Range{},
-			offset: 0,
-			output: Range{},
-		},
-		{
-			input:  Range{},
-			offset: -1,
-			output: Range{begin: -1, end: -1},
-		},
-		{
-			input:  Range{begin: 10, end: 20},
-			offset: -1,
-			output: Range{begin: 9, end: 19},
-		},
-		{
-			input:  Range{begin: 10, end: 20},
-			offset: 2,
-			output: Range{begin: 12, end: 22},
-		},
-	} {
-		if got := tc.input.Offset(tc.offset); got != tc.output {
-			t.Errorf("(%#v).Offset(%d) = %#v, want %#v", tc.input, tc.offset, got, tc.output)
-		}
-	}
-}
-
-func TestRangeLen(t *testing.T) {
-	for _, tc := range []struct {
-		r    Range
-		want int
-	}{
-		{r: Range{}, want: 0},
-		{r: Range{begin: 1, end: 1}, want: 0},
-		{r: Range{begin: -1, end: -1}, want: 0},
-		{r: Range{end: 10}, want: 10},
-		{r: Range{begin: 5, end: 10}, want: 5},
-	} {
-		if got := tc.r.Len(); got != tc.want {
-			t.Errorf("(%#v).Len() = %d, want %d", tc.r, got, tc.want)
-		}
-	}
-}