Check in gVisor.

PiperOrigin-RevId: 194583126
Change-Id: Ica1d8821a90f74e7e745962d71801c598c652463

4 files changed, 478 insertions, 0 deletions

diff --git a/pkg/tcpip/buffer/BUILD b/pkg/tcpip/buffer/BUILD
new file mode 100644
index 000000000..055e4b953
--- /dev/null
+++ b/pkg/tcpip/buffer/BUILD
@@ -0,0 +1,32 @@
+package(licenses = ["notice"])  # BSD
+
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//tools/go_stateify:defs.bzl", "go_stateify")
+
+go_stateify(
+    name = "buffer_state",
+    srcs = [
+        "view.go",
+    ],
+    out = "buffer_state.go",
+    package = "buffer",
+)
+
+go_library(
+    name = "buffer",
+    srcs = [
+        "buffer_state.go",
+        "prependable.go",
+        "view.go",
+    ],
+    importpath = "gvisor.googlesource.com/gvisor/pkg/tcpip/buffer",
+    visibility = ["//visibility:public"],
+    deps = ["//pkg/state"],
+)
+
+go_test(
+    name = "buffer_test",
+    size = "small",
+    srcs = ["view_test.go"],
+    embed = [":buffer"],
+)
diff --git a/pkg/tcpip/buffer/prependable.go b/pkg/tcpip/buffer/prependable.go
new file mode 100644
index 000000000..fd84585f9
--- /dev/null
+++ b/pkg/tcpip/buffer/prependable.go
@@ -0,0 +1,53 @@
+// 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 buffer
+
+// Prependable is a buffer that grows backwards, that is, more data can be
+// prepended to it. It is useful when building networking packets, where each
+// protocol adds its own headers to the front of the higher-level protocol
+// header and payload; for example, TCP would prepend its header to the payload,
+// then IP would prepend its own, then ethernet.
+type Prependable struct {
+	// Buf is the buffer backing the prependable buffer.
+	buf View
+
+	// usedIdx is the index where the used part of the buffer begins.
+	usedIdx int
+}
+
+// NewPrependable allocates a new prependable buffer with the given size.
+func NewPrependable(size int) Prependable {
+	return Prependable{buf: NewView(size), usedIdx: size}
+}
+
+// Prepend reserves the requested space in front of the buffer, returning a
+// slice that represents the reserved space.
+func (p *Prependable) Prepend(size int) []byte {
+	if size > p.usedIdx {
+		return nil
+	}
+
+	p.usedIdx -= size
+	return p.buf[p.usedIdx:][:size:size]
+}
+
+// View returns a View of the backing buffer that contains all prepended
+// data so far.
+func (p *Prependable) View() View {
+	v := p.buf
+	v.TrimFront(p.usedIdx)
+	return v
+}
+
+// UsedBytes returns a slice of the backing buffer that contains all prepended
+// data so far.
+func (p *Prependable) UsedBytes() []byte {
+	return p.buf[p.usedIdx:]
+}
+
+// UsedLength returns the number of bytes used so far.
+func (p *Prependable) UsedLength() int {
+	return len(p.buf) - p.usedIdx
+}
diff --git a/pkg/tcpip/buffer/view.go b/pkg/tcpip/buffer/view.go
new file mode 100644
index 000000000..241ccc7a8
--- /dev/null
+++ b/pkg/tcpip/buffer/view.go
@@ -0,0 +1,181 @@
+// 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 buffer provides the implementation of a buffer view.
+package buffer
+
+// View is a slice of a buffer, with convenience methods.
+type View []byte
+
+// NewView allocates a new buffer and returns an initialized view that covers
+// the whole buffer.
+func NewView(size int) View {
+	return make(View, size)
+}
+
+// NewViewFromBytes allocates a new buffer and copies in the given bytes.
+func NewViewFromBytes(b []byte) View {
+	return append(View(nil), b...)
+}
+
+// TrimFront removes the first "count" bytes from the visible section of the
+// buffer.
+func (v *View) TrimFront(count int) {
+	*v = (*v)[count:]
+}
+
+// CapLength irreversibly reduces the length of the visible section of the
+// buffer to the value specified.
+func (v *View) CapLength(length int) {
+	// We also set the slice cap because if we don't, one would be able to
+	// expand the view back to include the region just excluded. We want to
+	// prevent that to avoid potential data leak if we have uninitialized
+	// data in excluded region.
+	*v = (*v)[:length:length]
+}
+
+// ToVectorisedView transforms a View in a VectorisedView from an
+// already-allocated slice of View.
+func (v *View) ToVectorisedView(views [1]View) VectorisedView {
+	views[0] = *v
+	return NewVectorisedView(len(*v), views[:])
+}
+
+// VectorisedView is a vectorised version of View using non contigous memory.
+// It supports all the convenience methods supported by View.
+type VectorisedView struct {
+	views []View
+	size  int
+}
+
+// NewVectorisedView creates a new vectorised view from an already-allocated slice
+// of View and sets its size.
+func NewVectorisedView(size int, views []View) VectorisedView {
+	return VectorisedView{views: views, size: size}
+}
+
+// TrimFront removes the first "count" bytes of the vectorised view.
+func (vv *VectorisedView) TrimFront(count int) {
+	for count > 0 && len(vv.views) > 0 {
+		if count < len(vv.views[0]) {
+			vv.size -= count
+			vv.views[0].TrimFront(count)
+			return
+		}
+		count -= len(vv.views[0])
+		vv.RemoveFirst()
+	}
+}
+
+// CapLength irreversibly reduces the length of the vectorised view.
+func (vv *VectorisedView) CapLength(length int) {
+	if length < 0 {
+		length = 0
+	}
+	if vv.size < length {
+		return
+	}
+	vv.size = length
+	for i := range vv.views {
+		v := &vv.views[i]
+		if len(*v) >= length {
+			if length == 0 {
+				vv.views = vv.views[:i]
+			} else {
+				v.CapLength(length)
+				vv.views = vv.views[:i+1]
+			}
+			return
+		}
+		length -= len(*v)
+	}
+}
+
+// Clone returns a clone of this VectorisedView.
+// If the buffer argument is large enough to contain all the Views of this VectorisedView,
+// the method will avoid allocations and use the buffer to store the Views of the clone.
+func (vv *VectorisedView) Clone(buffer []View) VectorisedView {
+	var views []View
+	if len(buffer) >= len(vv.views) {
+		views = buffer[:len(vv.views)]
+	} else {
+		views = make([]View, len(vv.views))
+	}
+	for i, v := range vv.views {
+		views[i] = v
+	}
+	return VectorisedView{views: views, size: vv.size}
+}
+
+// First returns the first view of the vectorised view.
+// It panics if the vectorised view is empty.
+func (vv *VectorisedView) First() View {
+	if len(vv.views) == 0 {
+		return nil
+	}
+	return vv.views[0]
+}
+
+// RemoveFirst removes the first view of the vectorised view.
+func (vv *VectorisedView) RemoveFirst() {
+	if len(vv.views) == 0 {
+		return
+	}
+	vv.size -= len(vv.views[0])
+	vv.views = vv.views[1:]
+}
+
+// SetSize unsafely sets the size of the VectorisedView.
+func (vv *VectorisedView) SetSize(size int) {
+	vv.size = size
+}
+
+// SetViews unsafely sets the views of the VectorisedView.
+func (vv *VectorisedView) SetViews(views []View) {
+	vv.views = views
+}
+
+// Size returns the size in bytes of the entire content stored in the vectorised view.
+func (vv *VectorisedView) Size() int {
+	return vv.size
+}
+
+// ToView returns the a single view containing the content of the vectorised view.
+func (vv *VectorisedView) ToView() View {
+	v := make([]byte, vv.size)
+	u := v
+	for i := range vv.views {
+		n := copy(u, vv.views[i])
+		u = u[n:]
+	}
+	return v
+}
+
+// Views returns the slice containing the all views.
+func (vv *VectorisedView) Views() []View {
+	return vv.views
+}
+
+// ByteSlice returns a slice containing the all views as a []byte.
+func (vv *VectorisedView) ByteSlice() [][]byte {
+	s := make([][]byte, len(vv.views))
+	for i := range vv.views {
+		s[i] = []byte(vv.views[i])
+	}
+	return s
+}
+
+// copy returns a deep-copy of the vectorised view.
+// It is an expensive method that should be used only in tests.
+func (vv *VectorisedView) copy() *VectorisedView {
+	uu := &VectorisedView{
+		views: make([]View, len(vv.views)),
+		size:  vv.size,
+	}
+	for i, v := range vv.views {
+		uu.views[i] = make(View, len(v))
+		copy(uu.views[i], v)
+	}
+	return uu
+}
diff --git a/pkg/tcpip/buffer/view_test.go b/pkg/tcpip/buffer/view_test.go
new file mode 100644
index 000000000..ff8535ba5
--- /dev/null
+++ b/pkg/tcpip/buffer/view_test.go
@@ -0,0 +1,212 @@
+// 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 buffer_test contains tests for the VectorisedView type.
+package buffer
+
+import (
+	"reflect"
+	"testing"
+)
+
+// vv is an helper to build VectorisedView from different strings.
+func vv(size int, pieces ...string) *VectorisedView {
+	views := make([]View, len(pieces))
+	for i, p := range pieces {
+		views[i] = []byte(p)
+	}
+
+	vv := NewVectorisedView(size, views)
+	return &vv
+}
+
+var capLengthTestCases = []struct {
+	comment string
+	in      *VectorisedView
+	length  int
+	want    *VectorisedView
+}{
+	{
+		comment: "Simple case",
+		in:      vv(2, "12"),
+		length:  1,
+		want:    vv(1, "1"),
+	},
+	{
+		comment: "Case spanning across two Views",
+		in:      vv(4, "123", "4"),
+		length:  2,
+		want:    vv(2, "12"),
+	},
+	{
+		comment: "Corner case with negative length",
+		in:      vv(1, "1"),
+		length:  -1,
+		want:    vv(0),
+	},
+	{
+		comment: "Corner case with length = 0",
+		in:      vv(3, "12", "3"),
+		length:  0,
+		want:    vv(0),
+	},
+	{
+		comment: "Corner case with length = size",
+		in:      vv(1, "1"),
+		length:  1,
+		want:    vv(1, "1"),
+	},
+	{
+		comment: "Corner case with length > size",
+		in:      vv(1, "1"),
+		length:  2,
+		want:    vv(1, "1"),
+	},
+}
+
+func TestCapLength(t *testing.T) {
+	for _, c := range capLengthTestCases {
+		orig := c.in.copy()
+		c.in.CapLength(c.length)
+		if !reflect.DeepEqual(c.in, c.want) {
+			t.Errorf("Test \"%s\" failed when calling CapLength(%d) on %v. Got %v. Want %v",
+				c.comment, c.length, orig, c.in, c.want)
+		}
+	}
+}
+
+var trimFrontTestCases = []struct {
+	comment string
+	in      *VectorisedView
+	count   int
+	want    *VectorisedView
+}{
+	{
+		comment: "Simple case",
+		in:      vv(2, "12"),
+		count:   1,
+		want:    vv(1, "2"),
+	},
+	{
+		comment: "Case where we trim an entire View",
+		in:      vv(2, "1", "2"),
+		count:   1,
+		want:    vv(1, "2"),
+	},
+	{
+		comment: "Case spanning across two Views",
+		in:      vv(3, "1", "23"),
+		count:   2,
+		want:    vv(1, "3"),
+	},
+	{
+		comment: "Corner case with negative count",
+		in:      vv(1, "1"),
+		count:   -1,
+		want:    vv(1, "1"),
+	},
+	{
+		comment: " Corner case with count = 0",
+		in:      vv(1, "1"),
+		count:   0,
+		want:    vv(1, "1"),
+	},
+	{
+		comment: "Corner case with count = size",
+		in:      vv(1, "1"),
+		count:   1,
+		want:    vv(0),
+	},
+	{
+		comment: "Corner case with count > size",
+		in:      vv(1, "1"),
+		count:   2,
+		want:    vv(0),
+	},
+}
+
+func TestTrimFront(t *testing.T) {
+	for _, c := range trimFrontTestCases {
+		orig := c.in.copy()
+		c.in.TrimFront(c.count)
+		if !reflect.DeepEqual(c.in, c.want) {
+			t.Errorf("Test \"%s\" failed when calling TrimFront(%d) on %v. Got %v. Want %v",
+				c.comment, c.count, orig, c.in, c.want)
+		}
+	}
+}
+
+var toViewCases = []struct {
+	comment string
+	in      *VectorisedView
+	want    View
+}{
+	{
+		comment: "Simple case",
+		in:      vv(2, "12"),
+		want:    []byte("12"),
+	},
+	{
+		comment: "Case with multiple views",
+		in:      vv(2, "1", "2"),
+		want:    []byte("12"),
+	},
+	{
+		comment: "Empty case",
+		in:      vv(0),
+		want:    []byte(""),
+	},
+}
+
+func TestToView(t *testing.T) {
+	for _, c := range toViewCases {
+		got := c.in.ToView()
+		if !reflect.DeepEqual(got, c.want) {
+			t.Errorf("Test \"%s\" failed when calling ToView() on %v. Got %v. Want %v",
+				c.comment, c.in, got, c.want)
+		}
+	}
+}
+
+var toCloneCases = []struct {
+	comment  string
+	inView   *VectorisedView
+	inBuffer []View
+}{
+	{
+		comment:  "Simple case",
+		inView:   vv(1, "1"),
+		inBuffer: make([]View, 1),
+	},
+	{
+		comment:  "Case with multiple views",
+		inView:   vv(2, "1", "2"),
+		inBuffer: make([]View, 2),
+	},
+	{
+		comment:  "Case with buffer too small",
+		inView:   vv(2, "1", "2"),
+		inBuffer: make([]View, 1),
+	},
+	{
+		comment:  "Case with buffer larger than needed",
+		inView:   vv(1, "1"),
+		inBuffer: make([]View, 2),
+	},
+	{
+		comment:  "Case with nil buffer",
+		inView:   vv(1, "1"),
+		inBuffer: nil,
+	},
+}
+
+func TestToClone(t *testing.T) {
+	for _, c := range toCloneCases {
+		got := c.inView.Clone(c.inBuffer)
+		if !reflect.DeepEqual(&got, c.inView) {
+			t.Errorf("Test \"%s\" failed when calling Clone(%v) on %v. Got %v. Want %v",
+				c.comment, c.inBuffer, c.inView, got, c.inView)
+		}
+	}
+}