diff options
Diffstat (limited to 'pkg/sentry/fsimpl/kernfs')
| -rw-r--r-- | pkg/sentry/fsimpl/kernfs/BUILD | 75 | ||||
| -rw-r--r-- | pkg/sentry/fsimpl/kernfs/fstree.go | 46 | ||||
| -rw-r--r-- | pkg/sentry/fsimpl/kernfs/kernfs_state_autogen.go | 178 | ||||
| -rw-r--r-- | pkg/sentry/fsimpl/kernfs/kernfs_test.go | 330 | ||||
| -rw-r--r-- | pkg/sentry/fsimpl/kernfs/slot_list.go | 193 |
5 files changed, 417 insertions, 405 deletions
diff --git a/pkg/sentry/fsimpl/kernfs/BUILD b/pkg/sentry/fsimpl/kernfs/BUILD deleted file mode 100644 index 179df6c1e..000000000 --- a/pkg/sentry/fsimpl/kernfs/BUILD +++ /dev/null @@ -1,75 +0,0 @@ -load("//tools:defs.bzl", "go_library", "go_test") -load("//tools/go_generics:defs.bzl", "go_template_instance") - -licenses(["notice"]) - -go_template_instance( - name = "fstree", - out = "fstree.go", - package = "kernfs", - prefix = "generic", - template = "//pkg/sentry/vfs/genericfstree:generic_fstree", - types = { - "Dentry": "Dentry", - }, -) - -go_template_instance( - name = "slot_list", - out = "slot_list.go", - package = "kernfs", - prefix = "slot", - template = "//pkg/ilist:generic_list", - types = { - "Element": "*slot", - "Linker": "*slot", - }, -) - -go_library( - name = "kernfs", - srcs = [ - "dynamic_bytes_file.go", - "fd_impl_util.go", - "filesystem.go", - "fstree.go", - "inode_impl_util.go", - "kernfs.go", - "slot_list.go", - "symlink.go", - ], - visibility = ["//pkg/sentry:internal"], - deps = [ - "//pkg/abi/linux", - "//pkg/context", - "//pkg/fspath", - "//pkg/log", - "//pkg/refs", - "//pkg/sentry/fs/lock", - "//pkg/sentry/kernel/auth", - "//pkg/sentry/memmap", - "//pkg/sentry/socket/unix/transport", - "//pkg/sentry/vfs", - "//pkg/sync", - "//pkg/syserror", - "//pkg/usermem", - ], -) - -go_test( - name = "kernfs_test", - size = "small", - srcs = ["kernfs_test.go"], - deps = [ - ":kernfs", - "//pkg/abi/linux", - "//pkg/context", - "//pkg/sentry/contexttest", - "//pkg/sentry/fsimpl/testutil", - "//pkg/sentry/kernel/auth", - "//pkg/sentry/vfs", - "//pkg/syserror", - "//pkg/usermem", - "@com_github_google_go-cmp//cmp:go_default_library", - ], -) diff --git a/pkg/sentry/fsimpl/kernfs/fstree.go b/pkg/sentry/fsimpl/kernfs/fstree.go new file mode 100644 index 000000000..ce86d7919 --- /dev/null +++ b/pkg/sentry/fsimpl/kernfs/fstree.go @@ -0,0 +1,46 @@ +package kernfs + +import ( + "gvisor.dev/gvisor/pkg/fspath" + "gvisor.dev/gvisor/pkg/sentry/vfs" +) + +// IsAncestorDentry returns true if d is an ancestor of d2; that is, d is +// either d2's parent or an ancestor of d2's parent. +func genericIsAncestorDentry(d, d2 *Dentry) bool { + for d2 != nil { + if d2.parent == d { + return true + } + if d2.parent == d2 { + return false + } + d2 = d2.parent + } + return false +} + +// ParentOrSelf returns d.parent. If d.parent is nil, ParentOrSelf returns d. +func genericParentOrSelf(d *Dentry) *Dentry { + if d.parent != nil { + return d.parent + } + return d +} + +// PrependPath is a generic implementation of FilesystemImpl.PrependPath(). +func genericPrependPath(vfsroot vfs.VirtualDentry, mnt *vfs.Mount, d *Dentry, b *fspath.Builder) error { + for { + if mnt == vfsroot.Mount() && &d.vfsd == vfsroot.Dentry() { + return vfs.PrependPathAtVFSRootError{} + } + if &d.vfsd == mnt.Root() { + return nil + } + if d.parent == nil { + return vfs.PrependPathAtNonMountRootError{} + } + b.PrependComponent(d.name) + d = d.parent + } +} diff --git a/pkg/sentry/fsimpl/kernfs/kernfs_state_autogen.go b/pkg/sentry/fsimpl/kernfs/kernfs_state_autogen.go new file mode 100644 index 000000000..371b1481c --- /dev/null +++ b/pkg/sentry/fsimpl/kernfs/kernfs_state_autogen.go @@ -0,0 +1,178 @@ +// automatically generated by stateify. + +package kernfs + +import ( + "gvisor.dev/gvisor/pkg/state" +) + +func (x *DynamicBytesFile) StateTypeName() string { + return "pkg/sentry/fsimpl/kernfs.DynamicBytesFile" +} + +func (x *DynamicBytesFile) StateFields() []string { + return []string{ + "InodeAttrs", + "InodeNoopRefCount", + "InodeNotDirectory", + "InodeNotSymlink", + "locks", + "data", + } +} + +func (x *DynamicBytesFile) beforeSave() {} + +func (x *DynamicBytesFile) StateSave(m state.Sink) { + x.beforeSave() + m.Save(0, &x.InodeAttrs) + m.Save(1, &x.InodeNoopRefCount) + m.Save(2, &x.InodeNotDirectory) + m.Save(3, &x.InodeNotSymlink) + m.Save(4, &x.locks) + m.Save(5, &x.data) +} + +func (x *DynamicBytesFile) afterLoad() {} + +func (x *DynamicBytesFile) StateLoad(m state.Source) { + m.Load(0, &x.InodeAttrs) + m.Load(1, &x.InodeNoopRefCount) + m.Load(2, &x.InodeNotDirectory) + m.Load(3, &x.InodeNotSymlink) + m.Load(4, &x.locks) + m.Load(5, &x.data) +} + +func (x *DynamicBytesFD) StateTypeName() string { + return "pkg/sentry/fsimpl/kernfs.DynamicBytesFD" +} + +func (x *DynamicBytesFD) StateFields() []string { + return []string{ + "FileDescriptionDefaultImpl", + "DynamicBytesFileDescriptionImpl", + "LockFD", + "vfsfd", + "inode", + } +} + +func (x *DynamicBytesFD) beforeSave() {} + +func (x *DynamicBytesFD) StateSave(m state.Sink) { + x.beforeSave() + m.Save(0, &x.FileDescriptionDefaultImpl) + m.Save(1, &x.DynamicBytesFileDescriptionImpl) + m.Save(2, &x.LockFD) + m.Save(3, &x.vfsfd) + m.Save(4, &x.inode) +} + +func (x *DynamicBytesFD) afterLoad() {} + +func (x *DynamicBytesFD) StateLoad(m state.Source) { + m.Load(0, &x.FileDescriptionDefaultImpl) + m.Load(1, &x.DynamicBytesFileDescriptionImpl) + m.Load(2, &x.LockFD) + m.Load(3, &x.vfsfd) + m.Load(4, &x.inode) +} + +func (x *StaticDirectory) StateTypeName() string { + return "pkg/sentry/fsimpl/kernfs.StaticDirectory" +} + +func (x *StaticDirectory) StateFields() []string { + return []string{ + "InodeNotSymlink", + "InodeDirectoryNoNewChildren", + "InodeAttrs", + "InodeNoDynamicLookup", + "OrderedChildren", + "locks", + } +} + +func (x *StaticDirectory) beforeSave() {} + +func (x *StaticDirectory) StateSave(m state.Sink) { + x.beforeSave() + m.Save(0, &x.InodeNotSymlink) + m.Save(1, &x.InodeDirectoryNoNewChildren) + m.Save(2, &x.InodeAttrs) + m.Save(3, &x.InodeNoDynamicLookup) + m.Save(4, &x.OrderedChildren) + m.Save(5, &x.locks) +} + +func (x *StaticDirectory) afterLoad() {} + +func (x *StaticDirectory) StateLoad(m state.Source) { + m.Load(0, &x.InodeNotSymlink) + m.Load(1, &x.InodeDirectoryNoNewChildren) + m.Load(2, &x.InodeAttrs) + m.Load(3, &x.InodeNoDynamicLookup) + m.Load(4, &x.OrderedChildren) + m.Load(5, &x.locks) +} + +func (x *slotList) StateTypeName() string { + return "pkg/sentry/fsimpl/kernfs.slotList" +} + +func (x *slotList) StateFields() []string { + return []string{ + "head", + "tail", + } +} + +func (x *slotList) beforeSave() {} + +func (x *slotList) StateSave(m state.Sink) { + x.beforeSave() + m.Save(0, &x.head) + m.Save(1, &x.tail) +} + +func (x *slotList) afterLoad() {} + +func (x *slotList) StateLoad(m state.Source) { + m.Load(0, &x.head) + m.Load(1, &x.tail) +} + +func (x *slotEntry) StateTypeName() string { + return "pkg/sentry/fsimpl/kernfs.slotEntry" +} + +func (x *slotEntry) StateFields() []string { + return []string{ + "next", + "prev", + } +} + +func (x *slotEntry) beforeSave() {} + +func (x *slotEntry) StateSave(m state.Sink) { + x.beforeSave() + m.Save(0, &x.next) + m.Save(1, &x.prev) +} + +func (x *slotEntry) afterLoad() {} + +func (x *slotEntry) StateLoad(m state.Source) { + m.Load(0, &x.next) + m.Load(1, &x.prev) +} + +func init() { + state.Register((*DynamicBytesFile)(nil)) + state.Register((*DynamicBytesFD)(nil)) + state.Register((*StaticDirectory)(nil)) + state.Register((*slotList)(nil)) + state.Register((*slotEntry)(nil)) +} diff --git a/pkg/sentry/fsimpl/kernfs/kernfs_test.go b/pkg/sentry/fsimpl/kernfs/kernfs_test.go deleted file mode 100644 index dc407eb1d..000000000 --- a/pkg/sentry/fsimpl/kernfs/kernfs_test.go +++ /dev/null @@ -1,330 +0,0 @@ -// 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 kernfs_test - -import ( - "bytes" - "fmt" - "testing" - - "github.com/google/go-cmp/cmp" - "gvisor.dev/gvisor/pkg/abi/linux" - "gvisor.dev/gvisor/pkg/context" - "gvisor.dev/gvisor/pkg/sentry/contexttest" - "gvisor.dev/gvisor/pkg/sentry/fsimpl/kernfs" - "gvisor.dev/gvisor/pkg/sentry/fsimpl/testutil" - "gvisor.dev/gvisor/pkg/sentry/kernel/auth" - "gvisor.dev/gvisor/pkg/sentry/vfs" - "gvisor.dev/gvisor/pkg/syserror" - "gvisor.dev/gvisor/pkg/usermem" -) - -const defaultMode linux.FileMode = 01777 -const staticFileContent = "This is sample content for a static test file." - -// RootDentryFn is a generator function for creating the root dentry of a test -// filesystem. See newTestSystem. -type RootDentryFn func(*auth.Credentials, *filesystem) *kernfs.Dentry - -// newTestSystem sets up a minimal environment for running a test, including an -// instance of a test filesystem. Tests can control the contents of the -// filesystem by providing an appropriate rootFn, which should return a -// pre-populated root dentry. -func newTestSystem(t *testing.T, rootFn RootDentryFn) *testutil.System { - ctx := contexttest.Context(t) - creds := auth.CredentialsFromContext(ctx) - v := &vfs.VirtualFilesystem{} - if err := v.Init(); err != nil { - t.Fatalf("VFS init: %v", err) - } - v.MustRegisterFilesystemType("testfs", &fsType{rootFn: rootFn}, &vfs.RegisterFilesystemTypeOptions{ - AllowUserMount: true, - }) - mns, err := v.NewMountNamespace(ctx, creds, "", "testfs", &vfs.GetFilesystemOptions{}) - if err != nil { - t.Fatalf("Failed to create testfs root mount: %v", err) - } - return testutil.NewSystem(ctx, t, v, mns) -} - -type fsType struct { - rootFn RootDentryFn -} - -type filesystem struct { - kernfs.Filesystem -} - -type file struct { - kernfs.DynamicBytesFile - content string -} - -func (fs *filesystem) newFile(creds *auth.Credentials, content string) *kernfs.Dentry { - f := &file{} - f.content = content - f.DynamicBytesFile.Init(creds, 0 /* devMajor */, 0 /* devMinor */, fs.NextIno(), f, 0777) - - d := &kernfs.Dentry{} - d.Init(f) - return d -} - -func (f *file) Generate(ctx context.Context, buf *bytes.Buffer) error { - fmt.Fprintf(buf, "%s", f.content) - return nil -} - -type attrs struct { - kernfs.InodeAttrs -} - -func (*attrs) SetStat(context.Context, *vfs.Filesystem, *auth.Credentials, vfs.SetStatOptions) error { - return syserror.EPERM -} - -type readonlyDir struct { - attrs - kernfs.InodeNotSymlink - kernfs.InodeNoDynamicLookup - kernfs.InodeDirectoryNoNewChildren - kernfs.OrderedChildren - - locks vfs.FileLocks - - dentry kernfs.Dentry -} - -func (fs *filesystem) newReadonlyDir(creds *auth.Credentials, mode linux.FileMode, contents map[string]*kernfs.Dentry) *kernfs.Dentry { - dir := &readonlyDir{} - dir.attrs.Init(creds, 0 /* devMajor */, 0 /* devMinor */, fs.NextIno(), linux.ModeDirectory|mode) - dir.OrderedChildren.Init(kernfs.OrderedChildrenOptions{}) - dir.dentry.Init(dir) - - dir.IncLinks(dir.OrderedChildren.Populate(&dir.dentry, contents)) - - return &dir.dentry -} - -func (d *readonlyDir) Open(ctx context.Context, rp *vfs.ResolvingPath, vfsd *vfs.Dentry, opts vfs.OpenOptions) (*vfs.FileDescription, error) { - fd, err := kernfs.NewGenericDirectoryFD(rp.Mount(), vfsd, &d.OrderedChildren, &d.locks, &opts) - if err != nil { - return nil, err - } - return fd.VFSFileDescription(), nil -} - -type dir struct { - attrs - kernfs.InodeNotSymlink - kernfs.InodeNoDynamicLookup - kernfs.OrderedChildren - - locks vfs.FileLocks - - fs *filesystem - dentry kernfs.Dentry -} - -func (fs *filesystem) newDir(creds *auth.Credentials, mode linux.FileMode, contents map[string]*kernfs.Dentry) *kernfs.Dentry { - dir := &dir{} - dir.fs = fs - dir.attrs.Init(creds, 0 /* devMajor */, 0 /* devMinor */, fs.NextIno(), linux.ModeDirectory|mode) - dir.OrderedChildren.Init(kernfs.OrderedChildrenOptions{Writable: true}) - dir.dentry.Init(dir) - - dir.IncLinks(dir.OrderedChildren.Populate(&dir.dentry, contents)) - - return &dir.dentry -} - -func (d *dir) Open(ctx context.Context, rp *vfs.ResolvingPath, vfsd *vfs.Dentry, opts vfs.OpenOptions) (*vfs.FileDescription, error) { - fd, err := kernfs.NewGenericDirectoryFD(rp.Mount(), vfsd, &d.OrderedChildren, &d.locks, &opts) - if err != nil { - return nil, err - } - return fd.VFSFileDescription(), nil -} - -func (d *dir) NewDir(ctx context.Context, name string, opts vfs.MkdirOptions) (*vfs.Dentry, error) { - creds := auth.CredentialsFromContext(ctx) - dir := d.fs.newDir(creds, opts.Mode, nil) - dirVFSD := dir.VFSDentry() - if err := d.OrderedChildren.Insert(name, dirVFSD); err != nil { - dir.DecRef() - return nil, err - } - d.IncLinks(1) - return dirVFSD, nil -} - -func (d *dir) NewFile(ctx context.Context, name string, opts vfs.OpenOptions) (*vfs.Dentry, error) { - creds := auth.CredentialsFromContext(ctx) - f := d.fs.newFile(creds, "") - fVFSD := f.VFSDentry() - if err := d.OrderedChildren.Insert(name, fVFSD); err != nil { - f.DecRef() - return nil, err - } - return fVFSD, nil -} - -func (*dir) NewLink(context.Context, string, kernfs.Inode) (*vfs.Dentry, error) { - return nil, syserror.EPERM -} - -func (*dir) NewSymlink(context.Context, string, string) (*vfs.Dentry, error) { - return nil, syserror.EPERM -} - -func (*dir) NewNode(context.Context, string, vfs.MknodOptions) (*vfs.Dentry, error) { - return nil, syserror.EPERM -} - -func (fsType) Name() string { - return "kernfs" -} - -func (fst fsType) GetFilesystem(ctx context.Context, vfsObj *vfs.VirtualFilesystem, creds *auth.Credentials, source string, opt vfs.GetFilesystemOptions) (*vfs.Filesystem, *vfs.Dentry, error) { - fs := &filesystem{} - fs.VFSFilesystem().Init(vfsObj, &fst, fs) - root := fst.rootFn(creds, fs) - return fs.VFSFilesystem(), root.VFSDentry(), nil -} - -// -------------------- Remainder of the file are test cases -------------------- - -func TestBasic(t *testing.T) { - sys := newTestSystem(t, func(creds *auth.Credentials, fs *filesystem) *kernfs.Dentry { - return fs.newReadonlyDir(creds, 0755, map[string]*kernfs.Dentry{ - "file1": fs.newFile(creds, staticFileContent), - }) - }) - defer sys.Destroy() - sys.GetDentryOrDie(sys.PathOpAtRoot("file1")).DecRef() -} - -func TestMkdirGetDentry(t *testing.T) { - sys := newTestSystem(t, func(creds *auth.Credentials, fs *filesystem) *kernfs.Dentry { - return fs.newReadonlyDir(creds, 0755, map[string]*kernfs.Dentry{ - "dir1": fs.newDir(creds, 0755, nil), - }) - }) - defer sys.Destroy() - - pop := sys.PathOpAtRoot("dir1/a new directory") - if err := sys.VFS.MkdirAt(sys.Ctx, sys.Creds, pop, &vfs.MkdirOptions{Mode: 0755}); err != nil { - t.Fatalf("MkdirAt for PathOperation %+v failed: %v", pop, err) - } - sys.GetDentryOrDie(pop).DecRef() -} - -func TestReadStaticFile(t *testing.T) { - sys := newTestSystem(t, func(creds *auth.Credentials, fs *filesystem) *kernfs.Dentry { - return fs.newReadonlyDir(creds, 0755, map[string]*kernfs.Dentry{ - "file1": fs.newFile(creds, staticFileContent), - }) - }) - defer sys.Destroy() - - pop := sys.PathOpAtRoot("file1") - fd, err := sys.VFS.OpenAt(sys.Ctx, sys.Creds, pop, &vfs.OpenOptions{ - Flags: linux.O_RDONLY, - }) - if err != nil { - t.Fatalf("OpenAt for PathOperation %+v failed: %v", pop, err) - } - defer fd.DecRef() - - content, err := sys.ReadToEnd(fd) - if err != nil { - t.Fatalf("Read failed: %v", err) - } - if diff := cmp.Diff(staticFileContent, content); diff != "" { - t.Fatalf("Read returned unexpected data:\n--- want\n+++ got\n%v", diff) - } -} - -func TestCreateNewFileInStaticDir(t *testing.T) { - sys := newTestSystem(t, func(creds *auth.Credentials, fs *filesystem) *kernfs.Dentry { - return fs.newReadonlyDir(creds, 0755, map[string]*kernfs.Dentry{ - "dir1": fs.newDir(creds, 0755, nil), - }) - }) - defer sys.Destroy() - - pop := sys.PathOpAtRoot("dir1/newfile") - opts := &vfs.OpenOptions{Flags: linux.O_CREAT | linux.O_EXCL, Mode: defaultMode} - fd, err := sys.VFS.OpenAt(sys.Ctx, sys.Creds, pop, opts) - if err != nil { - t.Fatalf("OpenAt(pop:%+v, opts:%+v) failed: %v", pop, opts, err) - } - - // Close the file. The file should persist. - fd.DecRef() - - fd, err = sys.VFS.OpenAt(sys.Ctx, sys.Creds, pop, &vfs.OpenOptions{ - Flags: linux.O_RDONLY, - }) - if err != nil { - t.Fatalf("OpenAt(pop:%+v) = %+v failed: %v", pop, fd, err) - } - fd.DecRef() -} - -func TestDirFDReadWrite(t *testing.T) { - sys := newTestSystem(t, func(creds *auth.Credentials, fs *filesystem) *kernfs.Dentry { - return fs.newReadonlyDir(creds, 0755, nil) - }) - defer sys.Destroy() - - pop := sys.PathOpAtRoot("/") - fd, err := sys.VFS.OpenAt(sys.Ctx, sys.Creds, pop, &vfs.OpenOptions{ - Flags: linux.O_RDONLY, - }) - if err != nil { - t.Fatalf("OpenAt for PathOperation %+v failed: %v", pop, err) - } - defer fd.DecRef() - - // Read/Write should fail for directory FDs. - if _, err := fd.Read(sys.Ctx, usermem.BytesIOSequence([]byte{}), vfs.ReadOptions{}); err != syserror.EISDIR { - t.Fatalf("Read for directory FD failed with unexpected error: %v", err) - } - if _, err := fd.Write(sys.Ctx, usermem.BytesIOSequence([]byte{}), vfs.WriteOptions{}); err != syserror.EBADF { - t.Fatalf("Write for directory FD failed with unexpected error: %v", err) - } -} - -func TestDirFDIterDirents(t *testing.T) { - sys := newTestSystem(t, func(creds *auth.Credentials, fs *filesystem) *kernfs.Dentry { - return fs.newReadonlyDir(creds, 0755, map[string]*kernfs.Dentry{ - // Fill root with nodes backed by various inode implementations. - "dir1": fs.newReadonlyDir(creds, 0755, nil), - "dir2": fs.newDir(creds, 0755, map[string]*kernfs.Dentry{ - "dir3": fs.newDir(creds, 0755, nil), - }), - "file1": fs.newFile(creds, staticFileContent), - }) - }) - defer sys.Destroy() - - pop := sys.PathOpAtRoot("/") - sys.AssertAllDirentTypes(sys.ListDirents(pop), map[string]testutil.DirentType{ - "dir1": linux.DT_DIR, - "dir2": linux.DT_DIR, - "file1": linux.DT_REG, - }) -} diff --git a/pkg/sentry/fsimpl/kernfs/slot_list.go b/pkg/sentry/fsimpl/kernfs/slot_list.go new file mode 100644 index 000000000..c6cd74660 --- /dev/null +++ b/pkg/sentry/fsimpl/kernfs/slot_list.go @@ -0,0 +1,193 @@ +package kernfs + +// 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 slotElementMapper struct{} + +// linkerFor maps an Element to a Linker. +// +// This default implementation should be inlined. +// +//go:nosplit +func (slotElementMapper) linkerFor(elem *slot) *slot { 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 slotList struct { + head *slot + tail *slot +} + +// Reset resets list l to the empty state. +func (l *slotList) Reset() { + l.head = nil + l.tail = nil +} + +// Empty returns true iff the list is empty. +func (l *slotList) Empty() bool { + return l.head == nil +} + +// Front returns the first element of list l or nil. +func (l *slotList) Front() *slot { + return l.head +} + +// Back returns the last element of list l or nil. +func (l *slotList) Back() *slot { + return l.tail +} + +// Len returns the number of elements in the list. +// +// NOTE: This is an O(n) operation. +func (l *slotList) Len() (count int) { + for e := l.Front(); e != nil; e = (slotElementMapper{}.linkerFor(e)).Next() { + count++ + } + return count +} + +// PushFront inserts the element e at the front of list l. +func (l *slotList) PushFront(e *slot) { + linker := slotElementMapper{}.linkerFor(e) + linker.SetNext(l.head) + linker.SetPrev(nil) + if l.head != nil { + slotElementMapper{}.linkerFor(l.head).SetPrev(e) + } else { + l.tail = e + } + + l.head = e +} + +// PushBack inserts the element e at the back of list l. +func (l *slotList) PushBack(e *slot) { + linker := slotElementMapper{}.linkerFor(e) + linker.SetNext(nil) + linker.SetPrev(l.tail) + if l.tail != nil { + slotElementMapper{}.linkerFor(l.tail).SetNext(e) + } else { + l.head = e + } + + l.tail = e +} + +// PushBackList inserts list m at the end of list l, emptying m. +func (l *slotList) PushBackList(m *slotList) { + if l.head == nil { + l.head = m.head + l.tail = m.tail + } else if m.head != nil { + slotElementMapper{}.linkerFor(l.tail).SetNext(m.head) + slotElementMapper{}.linkerFor(m.head).SetPrev(l.tail) + + l.tail = m.tail + } + m.head = nil + m.tail = nil +} + +// InsertAfter inserts e after b. +func (l *slotList) InsertAfter(b, e *slot) { + bLinker := slotElementMapper{}.linkerFor(b) + eLinker := slotElementMapper{}.linkerFor(e) + + a := bLinker.Next() + + eLinker.SetNext(a) + eLinker.SetPrev(b) + bLinker.SetNext(e) + + if a != nil { + slotElementMapper{}.linkerFor(a).SetPrev(e) + } else { + l.tail = e + } +} + +// InsertBefore inserts e before a. +func (l *slotList) InsertBefore(a, e *slot) { + aLinker := slotElementMapper{}.linkerFor(a) + eLinker := slotElementMapper{}.linkerFor(e) + + b := aLinker.Prev() + eLinker.SetNext(a) + eLinker.SetPrev(b) + aLinker.SetPrev(e) + + if b != nil { + slotElementMapper{}.linkerFor(b).SetNext(e) + } else { + l.head = e + } +} + +// Remove removes e from l. +func (l *slotList) Remove(e *slot) { + linker := slotElementMapper{}.linkerFor(e) + prev := linker.Prev() + next := linker.Next() + + if prev != nil { + slotElementMapper{}.linkerFor(prev).SetNext(next) + } else if l.head == e { + l.head = next + } + + if next != nil { + slotElementMapper{}.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 slotEntry struct { + next *slot + prev *slot +} + +// Next returns the entry that follows e in the list. +func (e *slotEntry) Next() *slot { + return e.next +} + +// Prev returns the entry that precedes e in the list. +func (e *slotEntry) Prev() *slot { + return e.prev +} + +// SetNext assigns 'entry' as the entry that follows e in the list. +func (e *slotEntry) SetNext(elem *slot) { + e.next = elem +} + +// SetPrev assigns 'entry' as the entry that precedes e in the list. +func (e *slotEntry) SetPrev(elem *slot) { + e.prev = elem +} |