Sentry virtual filesystem, v2

Major differences from the current ("v1") sentry VFS:

- Path resolution is Filesystem-driven (FilesystemImpl methods call
vfs.ResolvingPath methods) rather than VFS-driven (fs package owns a
Dirent tree and calls fs.InodeOperations methods to populate it). This
drastically improves performance, primarily by reducing overhead from
inefficient synchronization and indirection. It also makes it possible
to implement remote filesystem protocols that translate FS system calls
into single RPCs, rather than having to make (at least) one RPC per path
component, significantly reducing the latency of remote filesystems
(especially during cold starts and for uncacheable shared filesystems).

- Mounts are correctly represented as a separate check based on
contextual state (current mount) rather than direct replacement in a
fs.Dirent tree. This makes it possible to support (non-recursive) bind
mounts and mount namespaces.

Included in this CL is fsimpl/memfs, an incomplete in-memory filesystem
that exists primarily to demonstrate intended filesystem implementation
patterns and for benchmarking:

BenchmarkVFS1TmpfsStat/1-6               3000000               497 ns/op
BenchmarkVFS1TmpfsStat/2-6               2000000               676 ns/op
BenchmarkVFS1TmpfsStat/3-6               2000000               904 ns/op
BenchmarkVFS1TmpfsStat/8-6               1000000              1944 ns/op
BenchmarkVFS1TmpfsStat/64-6               100000             14067 ns/op
BenchmarkVFS1TmpfsStat/100-6               50000             21700 ns/op
BenchmarkVFS2MemfsStat/1-6              10000000               197 ns/op
BenchmarkVFS2MemfsStat/2-6               5000000               233 ns/op
BenchmarkVFS2MemfsStat/3-6               5000000               268 ns/op
BenchmarkVFS2MemfsStat/8-6               3000000               477 ns/op
BenchmarkVFS2MemfsStat/64-6               500000              2592 ns/op
BenchmarkVFS2MemfsStat/100-6              300000              4045 ns/op
BenchmarkVFS1TmpfsMountStat/1-6          2000000               679 ns/op
BenchmarkVFS1TmpfsMountStat/2-6          2000000               912 ns/op
BenchmarkVFS1TmpfsMountStat/3-6          1000000              1113 ns/op
BenchmarkVFS1TmpfsMountStat/8-6          1000000              2118 ns/op
BenchmarkVFS1TmpfsMountStat/64-6                  100000             14251 ns/op
BenchmarkVFS1TmpfsMountStat/100-6                 100000             22397 ns/op
BenchmarkVFS2MemfsMountStat/1-6                  5000000               317 ns/op
BenchmarkVFS2MemfsMountStat/2-6                  5000000               361 ns/op
BenchmarkVFS2MemfsMountStat/3-6                  5000000               387 ns/op
BenchmarkVFS2MemfsMountStat/8-6                  3000000               582 ns/op
BenchmarkVFS2MemfsMountStat/64-6                  500000              2699 ns/op
BenchmarkVFS2MemfsMountStat/100-6                 300000              4133 ns/op

From this we can infer that, on this machine:

- Constant cost for tmpfs stat() is ~160ns in VFS2 and ~280ns in VFS1.

- Per-path-component cost is ~35ns in VFS2 and ~215ns in VFS1, a
difference of about 6x.

- The cost of crossing a mount boundary is about 80ns in VFS2
(MemfsMountStat/1 does approximately the same amount of work as
MemfsStat/2, except that it also crosses a mount boundary). This is an
inescapable cost of the separate mount lookup needed to support bind
mounts and mount namespaces.

PiperOrigin-RevId: 258853946

6 files changed, 542 insertions, 0 deletions

diff --git a/pkg/fspath/BUILD b/pkg/fspath/BUILD
new file mode 100644
index 000000000..11716af81
--- /dev/null
+++ b/pkg/fspath/BUILD
@@ -0,0 +1,28 @@
+load("//tools/go_stateify:defs.bzl", "go_library", "go_test")
+
+package(
+    default_visibility = ["//visibility:public"],
+    licenses = ["notice"],
+)
+
+go_library(
+    name = "fspath",
+    srcs = [
+        "builder.go",
+        "builder_unsafe.go",
+        "fspath.go",
+    ],
+    importpath = "gvisor.dev/gvisor/pkg/fspath",
+    deps = ["//pkg/syserror"],
+)
+
+go_test(
+    name = "fspath_test",
+    size = "small",
+    srcs = [
+        "builder_test.go",
+        "fspath_test.go",
+    ],
+    embed = [":fspath"],
+    deps = ["//pkg/syserror"],
+)
diff --git a/pkg/fspath/builder.go b/pkg/fspath/builder.go
new file mode 100644
index 000000000..7ddb36826
--- /dev/null
+++ b/pkg/fspath/builder.go
@@ -0,0 +1,104 @@
+// Copyright 2019 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 fspath
+
+import (
+	"fmt"
+)
+
+// Builder is similar to strings.Builder, but is used to produce pathnames
+// given path components in reverse order (from leaf to root). This is useful
+// in the common case where a filesystem is represented by a tree of named
+// nodes, and the path to a given node must be produced by walking upward from
+// that node to a given root.
+type Builder struct {
+	buf     []byte
+	start   int
+	needSep bool
+}
+
+// Reset resets the Builder to be empty.
+func (b *Builder) Reset() {
+	b.start = len(b.buf)
+	b.needSep = false
+}
+
+// Len returns the number of accumulated bytes.
+func (b *Builder) Len() int {
+	return len(b.buf) - b.start
+}
+
+func (b *Builder) needToGrow(n int) bool {
+	return b.start < n
+}
+
+func (b *Builder) grow(n int) {
+	newLen := b.Len() + n
+	var newCap int
+	if len(b.buf) == 0 {
+		newCap = 64 // arbitrary
+	} else {
+		newCap = 2 * len(b.buf)
+	}
+	for newCap < newLen {
+		newCap *= 2
+		if newCap == 0 {
+			panic(fmt.Sprintf("required length (%d) causes buffer size to overflow", newLen))
+		}
+	}
+	newBuf := make([]byte, newCap)
+	copy(newBuf[newCap-b.Len():], b.buf[b.start:])
+	b.start += newCap - len(b.buf)
+	b.buf = newBuf
+}
+
+// PrependComponent prepends the given path component to b's buffer. A path
+// separator is automatically inserted if appropriate.
+func (b *Builder) PrependComponent(pc string) {
+	if b.needSep {
+		b.PrependByte('/')
+	}
+	b.PrependString(pc)
+	b.needSep = true
+}
+
+// PrependString prepends the given string to b's buffer.
+func (b *Builder) PrependString(str string) {
+	if b.needToGrow(len(str)) {
+		b.grow(len(str))
+	}
+	b.start -= len(str)
+	copy(b.buf[b.start:], str)
+}
+
+// PrependByte prepends the given byte to b's buffer.
+func (b *Builder) PrependByte(c byte) {
+	if b.needToGrow(1) {
+		b.grow(1)
+	}
+	b.start--
+	b.buf[b.start] = c
+}
+
+// AppendString appends the given string to b's buffer.
+func (b *Builder) AppendString(str string) {
+	if b.needToGrow(len(str)) {
+		b.grow(len(str))
+	}
+	oldStart := b.start
+	b.start -= len(str)
+	copy(b.buf[b.start:], b.buf[oldStart:])
+	copy(b.buf[len(b.buf)-len(str):], str)
+}
diff --git a/pkg/fspath/builder_test.go b/pkg/fspath/builder_test.go
new file mode 100644
index 000000000..22f890273
--- /dev/null
+++ b/pkg/fspath/builder_test.go
@@ -0,0 +1,58 @@
+// Copyright 2019 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 fspath
+
+import (
+	"testing"
+)
+
+func TestBuilder(t *testing.T) {
+	type testCase struct {
+		pcs   []string // path components in reverse order
+		after string
+		want  string
+	}
+	tests := []testCase{
+		{
+			// Empty case.
+		},
+		{
+			pcs:  []string{"foo"},
+			want: "foo",
+		},
+		{
+			pcs:  []string{"foo", "bar", "baz"},
+			want: "baz/bar/foo",
+		},
+		{
+			pcs:   []string{"foo", "bar"},
+			after: " (deleted)",
+			want:  "bar/foo (deleted)",
+		},
+	}
+
+	for _, test := range tests {
+		t.Run(test.want, func(t *testing.T) {
+			var b Builder
+			for _, pc := range test.pcs {
+				b.PrependComponent(pc)
+			}
+			b.AppendString(test.after)
+			if got := b.String(); got != test.want {
+				t.Errorf("got %q, wanted %q", got, test.want)
+			}
+		})
+	}
+}
diff --git a/pkg/fspath/builder_unsafe.go b/pkg/fspath/builder_unsafe.go
new file mode 100644
index 000000000..75606808d
--- /dev/null
+++ b/pkg/fspath/builder_unsafe.go
@@ -0,0 +1,27 @@
+// Copyright 2019 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 fspath
+
+import (
+	"unsafe"
+)
+
+// String returns the accumulated string. No other methods should be called
+// after String.
+func (b *Builder) String() string {
+	bs := b.buf[b.start:]
+	// Compare strings.Builder.String().
+	return *(*string)(unsafe.Pointer(&bs))
+}
diff --git a/pkg/fspath/fspath.go b/pkg/fspath/fspath.go
new file mode 100644
index 000000000..f68752560
--- /dev/null
+++ b/pkg/fspath/fspath.go
@@ -0,0 +1,182 @@
+// Copyright 2019 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 fspath provides efficient tools for working with file paths in
+// Linux-compatible filesystem implementations.
+package fspath
+
+import (
+	"strings"
+
+	"gvisor.dev/gvisor/pkg/syserror"
+)
+
+const pathSep = '/'
+
+// Parse parses a pathname as described by path_resolution(7).
+func Parse(pathname string) (Path, error) {
+	if len(pathname) == 0 {
+		// "... POSIX decrees that an empty pathname must not be resolved
+		// successfully. Linux returns ENOENT in this case." -
+		// path_resolution(7)
+		return Path{}, syserror.ENOENT
+	}
+	// Skip leading path separators.
+	i := 0
+	for pathname[i] == pathSep {
+		i++
+		if i == len(pathname) {
+			// pathname consists entirely of path separators.
+			return Path{
+				Absolute: true,
+				Dir:      true,
+			}, nil
+		}
+	}
+	// Skip trailing path separators. This is required by Iterator.Next. This
+	// loop is guaranteed to terminate with j >= 0 because otherwise the
+	// pathname would consist entirely of path separators, so we would have
+	// returned above.
+	j := len(pathname) - 1
+	for pathname[j] == pathSep {
+		j--
+	}
+	// Find the end of the first path component.
+	firstEnd := i + 1
+	for firstEnd != len(pathname) && pathname[firstEnd] != pathSep {
+		firstEnd++
+	}
+	return Path{
+		Begin: Iterator{
+			partialPathname: pathname[i : j+1],
+			end:             firstEnd - i,
+		},
+		Absolute: i != 0,
+		Dir:      j != len(pathname)-1,
+	}, nil
+}
+
+// Path contains the information contained in a pathname string.
+//
+// Path is copyable by value.
+type Path struct {
+	// Begin is an iterator to the first path component in the relative part of
+	// the path.
+	//
+	// Path doesn't store information about path components after the first
+	// since this would require allocation.
+	Begin Iterator
+
+	// If true, the path is absolute, such that lookup should begin at the
+	// filesystem root. If false, the path is relative, such that where lookup
+	// begins is unspecified.
+	Absolute bool
+
+	// If true, the pathname contains trailing path separators, so the last
+	// path component must exist and resolve to a directory.
+	Dir bool
+}
+
+// String returns a pathname string equivalent to p. Note that the returned
+// string is not necessarily equal to the string p was parsed from; in
+// particular, redundant path separators will not be present.
+func (p Path) String() string {
+	var b strings.Builder
+	if p.Absolute {
+		b.WriteByte(pathSep)
+	}
+	sep := false
+	for pit := p.Begin; pit.Ok(); pit = pit.Next() {
+		if sep {
+			b.WriteByte(pathSep)
+		}
+		b.WriteString(pit.String())
+		sep = true
+	}
+	// Don't return "//" for Parse("/").
+	if p.Dir && p.Begin.Ok() {
+		b.WriteByte(pathSep)
+	}
+	return b.String()
+}
+
+// An Iterator represents either a path component in a Path or a terminal
+// iterator indicating that the end of the path has been reached.
+//
+// Iterator is immutable and copyable by value. The zero value of Iterator is
+// valid, and represents a terminal iterator.
+type Iterator struct {
+	// partialPathname is a substring of the original pathname beginning at the
+	// start of the represented path component and ending immediately after the
+	// end of the last path component in the pathname. If partialPathname is
+	// empty, the PathnameIterator is terminal.
+	//
+	// See TestParseIteratorPartialPathnames in fspath_test.go for a worked
+	// example.
+	partialPathname string
+
+	// end is the offset into partialPathname of the first byte after the end
+	// of the represented path component.
+	end int
+}
+
+// Ok returns true if it is not terminal.
+func (it Iterator) Ok() bool {
+	return len(it.partialPathname) != 0
+}
+
+// String returns the path component represented by it.
+//
+// Preconditions: it.Ok().
+func (it Iterator) String() string {
+	return it.partialPathname[:it.end]
+}
+
+// Next returns an iterator to the path component after it. If it is the last
+// component in the path, Next returns a terminal iterator.
+//
+// Preconditions: it.Ok().
+func (it Iterator) Next() Iterator {
+	if it.end == len(it.partialPathname) {
+		// End of the path.
+		return Iterator{}
+	}
+	// Skip path separators. Since Parse trims trailing path separators, if we
+	// aren't at the end of the path, there is definitely another path
+	// component.
+	i := it.end + 1
+	for {
+		if it.partialPathname[i] != pathSep {
+			break
+		}
+		i++
+	}
+	nextPartialPathname := it.partialPathname[i:]
+	// Find the end of this path component.
+	nextEnd := 1
+	for nextEnd < len(nextPartialPathname) && nextPartialPathname[nextEnd] != pathSep {
+		nextEnd++
+	}
+	return Iterator{
+		partialPathname: nextPartialPathname,
+		end:             nextEnd,
+	}
+}
+
+// NextOk is equivalent to it.Next().Ok(), but is faster.
+//
+// Preconditions: it.Ok().
+func (it Iterator) NextOk() bool {
+	return it.end != len(it.partialPathname)
+}
diff --git a/pkg/fspath/fspath_test.go b/pkg/fspath/fspath_test.go
new file mode 100644
index 000000000..215b35622
--- /dev/null
+++ b/pkg/fspath/fspath_test.go
@@ -0,0 +1,143 @@
+// Copyright 2019 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 fspath
+
+import (
+	"reflect"
+	"strings"
+	"testing"
+
+	"gvisor.dev/gvisor/pkg/syserror"
+)
+
+func TestParseIteratorPartialPathnames(t *testing.T) {
+	path, err := Parse("/foo//bar///baz////")
+	if err != nil {
+		t.Fatalf("Parse failed: %v", err)
+	}
+	// Parse strips leading slashes, and records their presence as
+	// Path.Absolute.
+	if !path.Absolute {
+		t.Errorf("Path.Absolute: got false, wanted true")
+	}
+	// Parse strips trailing slashes, and records their presence as Path.Dir.
+	if !path.Dir {
+		t.Errorf("Path.Dir: got false, wanted true")
+	}
+	// The first Iterator.partialPathname is the input pathname, with leading
+	// and trailing slashes stripped.
+	it := path.Begin
+	if want := "foo//bar///baz"; it.partialPathname != want {
+		t.Errorf("first Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want)
+	}
+	// Successive Iterator.partialPathnames remove the leading path component
+	// and following slashes, until we run out of path components and get a
+	// terminal Iterator.
+	it = it.Next()
+	if want := "bar///baz"; it.partialPathname != want {
+		t.Errorf("second Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want)
+	}
+	it = it.Next()
+	if want := "baz"; it.partialPathname != want {
+		t.Errorf("third Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want)
+	}
+	it = it.Next()
+	if want := ""; it.partialPathname != want {
+		t.Errorf("fourth Iterator.partialPathname: got %q, wanted %q", it.partialPathname, want)
+	}
+	if it.Ok() {
+		t.Errorf("fourth Iterator.Ok(): got true, wanted false")
+	}
+}
+
+func TestParse(t *testing.T) {
+	type testCase struct {
+		pathname string
+		relpath  []string
+		abs      bool
+		dir      bool
+	}
+	tests := []testCase{
+		{
+			pathname: "/",
+			relpath:  []string{},
+			abs:      true,
+			dir:      true,
+		},
+		{
+			pathname: "//",
+			relpath:  []string{},
+			abs:      true,
+			dir:      true,
+		},
+	}
+	for _, sep := range []string{"/", "//"} {
+		for _, abs := range []bool{false, true} {
+			for _, dir := range []bool{false, true} {
+				for _, pcs := range [][]string{
+					// single path component
+					{"foo"},
+					// multiple path components, including non-UTF-8
+					{".", "foo", "..", "\xe6", "bar"},
+				} {
+					prefix := ""
+					if abs {
+						prefix = sep
+					}
+					suffix := ""
+					if dir {
+						suffix = sep
+					}
+					tests = append(tests, testCase{
+						pathname: prefix + strings.Join(pcs, sep) + suffix,
+						relpath:  pcs,
+						abs:      abs,
+						dir:      dir,
+					})
+				}
+			}
+		}
+	}
+
+	for _, test := range tests {
+		t.Run(test.pathname, func(t *testing.T) {
+			p, err := Parse(test.pathname)
+			if err != nil {
+				t.Fatalf("failed to parse pathname %q: %v", test.pathname, err)
+			}
+			t.Logf("pathname %q => path %q", test.pathname, p)
+			if p.Absolute != test.abs {
+				t.Errorf("path absoluteness: got %v, wanted %v", p.Absolute, test.abs)
+			}
+			if p.Dir != test.dir {
+				t.Errorf("path must resolve to a directory: got %v, wanted %v", p.Dir, test.dir)
+			}
+			pcs := []string{}
+			for pit := p.Begin; pit.Ok(); pit = pit.Next() {
+				pcs = append(pcs, pit.String())
+			}
+			if !reflect.DeepEqual(pcs, test.relpath) {
+				t.Errorf("relative path: got %v, wanted %v", pcs, test.relpath)
+			}
+		})
+	}
+}
+
+func TestParseEmptyPathname(t *testing.T) {
+	p, err := Parse("")
+	if err != syserror.ENOENT {
+		t.Errorf("parsing empty pathname: got (%v, %v), wanted (<unspecified>, ENOENT)", p, err)
+	}
+}