diff options
Diffstat (limited to 'pkg/sentry/fs')
26 files changed, 71 insertions, 2348 deletions
diff --git a/pkg/sentry/fs/ashmem/area.go b/pkg/sentry/fs/ashmem/area.go deleted file mode 100644 index 3b8d6ca89..000000000 --- a/pkg/sentry/fs/ashmem/area.go +++ /dev/null @@ -1,308 +0,0 @@ -// Copyright 2018 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 ashmem - -import ( - "sync" - - "gvisor.dev/gvisor/pkg/abi/linux" - "gvisor.dev/gvisor/pkg/sentry/arch" - "gvisor.dev/gvisor/pkg/sentry/context" - "gvisor.dev/gvisor/pkg/sentry/fs" - "gvisor.dev/gvisor/pkg/sentry/fs/fsutil" - "gvisor.dev/gvisor/pkg/sentry/fs/tmpfs" - "gvisor.dev/gvisor/pkg/sentry/memmap" - "gvisor.dev/gvisor/pkg/sentry/usage" - "gvisor.dev/gvisor/pkg/sentry/usermem" - "gvisor.dev/gvisor/pkg/syserror" - "gvisor.dev/gvisor/pkg/waiter" -) - -const ( - // namePrefix is the name prefix assumed and forced by the Linux implementation. - namePrefix = "dev/ashmem" - - // nameLen is the maximum name length. - nameLen = 256 -) - -// Area implements fs.FileOperations. -// -// +stateify savable -type Area struct { - fsutil.FileNoFsync `state:"nosave"` - fsutil.FileNoSplice `state:"nosave"` - fsutil.FileNoopFlush `state:"nosave"` - fsutil.FileNotDirReaddir `state:"nosave"` - fsutil.FileUseInodeUnstableAttr `state:"nosave"` - waiter.AlwaysReady `state:"nosave"` - - ad *Device - - // mu protects fields below. - mu sync.Mutex `state:"nosave"` - tmpfsFile *fs.File - name string - size uint64 - perms usermem.AccessType - pb *PinBoard -} - -// Release implements fs.FileOperations.Release. -func (a *Area) Release() { - a.mu.Lock() - defer a.mu.Unlock() - if a.tmpfsFile != nil { - a.tmpfsFile.DecRef() - a.tmpfsFile = nil - } -} - -// Seek implements fs.FileOperations.Seek. -func (a *Area) Seek(ctx context.Context, file *fs.File, whence fs.SeekWhence, offset int64) (int64, error) { - a.mu.Lock() - defer a.mu.Unlock() - if a.size == 0 { - return 0, syserror.EINVAL - } - if a.tmpfsFile == nil { - return 0, syserror.EBADF - } - return a.tmpfsFile.FileOperations.Seek(ctx, file, whence, offset) -} - -// Read implements fs.FileOperations.Read. -func (a *Area) Read(ctx context.Context, file *fs.File, dst usermem.IOSequence, offset int64) (int64, error) { - a.mu.Lock() - defer a.mu.Unlock() - if a.size == 0 { - return 0, nil - } - if a.tmpfsFile == nil { - return 0, syserror.EBADF - } - return a.tmpfsFile.FileOperations.Read(ctx, file, dst, offset) -} - -// Write implements fs.FileOperations.Write. -func (a *Area) Write(ctx context.Context, file *fs.File, src usermem.IOSequence, offset int64) (int64, error) { - return 0, syserror.ENOSYS -} - -// ConfigureMMap implements fs.FileOperations.ConfigureMMap. -func (a *Area) ConfigureMMap(ctx context.Context, file *fs.File, opts *memmap.MMapOpts) error { - a.mu.Lock() - defer a.mu.Unlock() - if a.size == 0 { - return syserror.EINVAL - } - - if !a.perms.SupersetOf(opts.Perms) { - return syserror.EPERM - } - opts.MaxPerms = opts.MaxPerms.Intersect(a.perms) - - if a.tmpfsFile == nil { - tmpfsInodeOps := tmpfs.NewInMemoryFile(ctx, usage.Tmpfs, fs.UnstableAttr{}) - tmpfsInode := fs.NewInode(ctx, tmpfsInodeOps, fs.NewPseudoMountSource(ctx), fs.StableAttr{}) - dirent := fs.NewDirent(ctx, tmpfsInode, namePrefix+"/"+a.name) - tmpfsFile, err := tmpfsInode.GetFile(ctx, dirent, fs.FileFlags{Read: true, Write: true}) - // Drop the extra reference on the Dirent. - dirent.DecRef() - - if err != nil { - return err - } - - // Truncate to the size set by ASHMEM_SET_SIZE ioctl. - err = tmpfsInodeOps.Truncate(ctx, tmpfsInode, int64(a.size)) - if err != nil { - return err - } - a.tmpfsFile = tmpfsFile - a.pb = NewPinBoard() - } - - return a.tmpfsFile.ConfigureMMap(ctx, opts) -} - -// Ioctl implements fs.FileOperations.Ioctl. -func (a *Area) Ioctl(ctx context.Context, _ *fs.File, io usermem.IO, args arch.SyscallArguments) (uintptr, error) { - // Switch on ioctl request. - switch args[1].Uint() { - case linux.AshmemSetNameIoctl: - name, err := usermem.CopyStringIn(ctx, io, args[2].Pointer(), nameLen-1, usermem.IOOpts{ - AddressSpaceActive: true, - }) - if err != nil { - return 0, err - } - - a.mu.Lock() - defer a.mu.Unlock() - - // Cannot set name for already mapped ashmem. - if a.tmpfsFile != nil { - return 0, syserror.EINVAL - } - a.name = name - return 0, nil - - case linux.AshmemGetNameIoctl: - a.mu.Lock() - var local []byte - if a.name != "" { - nameLen := len([]byte(a.name)) - local = make([]byte, nameLen, nameLen+1) - copy(local, []byte(a.name)) - local = append(local, 0) - } else { - nameLen := len([]byte(namePrefix)) - local = make([]byte, nameLen, nameLen+1) - copy(local, []byte(namePrefix)) - local = append(local, 0) - } - a.mu.Unlock() - - if _, err := io.CopyOut(ctx, args[2].Pointer(), local, usermem.IOOpts{ - AddressSpaceActive: true, - }); err != nil { - return 0, syserror.EFAULT - } - return 0, nil - - case linux.AshmemSetSizeIoctl: - a.mu.Lock() - defer a.mu.Unlock() - - // Cannot set size for already mapped ashmem. - if a.tmpfsFile != nil { - return 0, syserror.EINVAL - } - a.size = uint64(args[2].SizeT()) - return 0, nil - - case linux.AshmemGetSizeIoctl: - return uintptr(a.size), nil - - case linux.AshmemPinIoctl, linux.AshmemUnpinIoctl, linux.AshmemGetPinStatusIoctl: - // Locking and unlocking is ok since once tmpfsFile is set, it won't be nil again - // even after unmapping! Unlocking is needed in order to avoid a deadlock on - // usermem.CopyObjectIn. - - // Cannot execute pin-related ioctls before mapping. - a.mu.Lock() - if a.tmpfsFile == nil { - a.mu.Unlock() - return 0, syserror.EINVAL - } - a.mu.Unlock() - - var pin linux.AshmemPin - _, err := usermem.CopyObjectIn(ctx, io, args[2].Pointer(), &pin, usermem.IOOpts{ - AddressSpaceActive: true, - }) - if err != nil { - return 0, syserror.EFAULT - } - - a.mu.Lock() - defer a.mu.Unlock() - return a.pinOperation(pin, args[1].Uint()) - - case linux.AshmemPurgeAllCachesIoctl: - return 0, nil - - case linux.AshmemSetProtMaskIoctl: - prot := uint64(args[2].ModeT()) - perms := usermem.AccessType{ - Read: prot&linux.PROT_READ != 0, - Write: prot&linux.PROT_WRITE != 0, - Execute: prot&linux.PROT_EXEC != 0, - } - - a.mu.Lock() - defer a.mu.Unlock() - - // Can only narrow prot mask. - if !a.perms.SupersetOf(perms) { - return 0, syserror.EINVAL - } - - // TODO(b/30946773,gvisor.dev/issue/153): If personality flag - // READ_IMPLIES_EXEC is set, set PROT_EXEC if PORT_READ is set. - - a.perms = perms - return 0, nil - - case linux.AshmemGetProtMaskIoctl: - return uintptr(a.perms.Prot()), nil - default: - // Ioctls irrelevant to Ashmem. - return 0, syserror.EINVAL - } -} - -// pinOperation should only be called while holding a.mu. -func (a *Area) pinOperation(pin linux.AshmemPin, op uint32) (uintptr, error) { - // Page-align a.size for checks. - pageAlignedSize, ok := usermem.Addr(a.size).RoundUp() - if !ok { - return 0, syserror.EINVAL - } - // Len 0 means everything onward. - if pin.Len == 0 { - pin.Len = uint32(pageAlignedSize) - pin.Offset - } - // Both Offset and Len have to be page-aligned. - if pin.Offset%uint32(usermem.PageSize) != 0 { - return 0, syserror.EINVAL - } - if pin.Len%uint32(usermem.PageSize) != 0 { - return 0, syserror.EINVAL - } - // Adding Offset and Len must not cause an uint32 overflow. - if end := pin.Offset + pin.Len; end < pin.Offset { - return 0, syserror.EINVAL - } - // Pin range must not exceed a's size. - if uint32(pageAlignedSize) < pin.Offset+pin.Len { - return 0, syserror.EINVAL - } - // Handle each operation. - r := RangeFromAshmemPin(pin) - switch op { - case linux.AshmemPinIoctl: - if a.pb.PinRange(r) { - return linux.AshmemWasPurged, nil - } - return linux.AshmemNotPurged, nil - - case linux.AshmemUnpinIoctl: - // TODO(b/30946773): Implement purge on unpin. - a.pb.UnpinRange(r) - return 0, nil - - case linux.AshmemGetPinStatusIoctl: - if a.pb.RangePinnedStatus(r) { - return linux.AshmemIsPinned, nil - } - return linux.AshmemIsUnpinned, nil - - default: - panic("unreachable") - } - -} diff --git a/pkg/sentry/fs/ashmem/ashmem_state_autogen.go b/pkg/sentry/fs/ashmem/ashmem_state_autogen.go deleted file mode 100755 index 13defb033..000000000 --- a/pkg/sentry/fs/ashmem/ashmem_state_autogen.go +++ /dev/null @@ -1,123 +0,0 @@ -// automatically generated by stateify. - -package ashmem - -import ( - "gvisor.dev/gvisor/pkg/state" -) - -func (x *Area) beforeSave() {} -func (x *Area) save(m state.Map) { - x.beforeSave() - m.Save("ad", &x.ad) - m.Save("tmpfsFile", &x.tmpfsFile) - m.Save("name", &x.name) - m.Save("size", &x.size) - m.Save("perms", &x.perms) - m.Save("pb", &x.pb) -} - -func (x *Area) afterLoad() {} -func (x *Area) load(m state.Map) { - m.Load("ad", &x.ad) - m.Load("tmpfsFile", &x.tmpfsFile) - m.Load("name", &x.name) - m.Load("size", &x.size) - m.Load("perms", &x.perms) - m.Load("pb", &x.pb) -} - -func (x *Device) beforeSave() {} -func (x *Device) save(m state.Map) { - x.beforeSave() - m.Save("InodeSimpleAttributes", &x.InodeSimpleAttributes) -} - -func (x *Device) afterLoad() {} -func (x *Device) load(m state.Map) { - m.Load("InodeSimpleAttributes", &x.InodeSimpleAttributes) -} - -func (x *PinBoard) beforeSave() {} -func (x *PinBoard) save(m state.Map) { - x.beforeSave() - m.Save("Set", &x.Set) -} - -func (x *PinBoard) afterLoad() {} -func (x *PinBoard) load(m state.Map) { - m.Load("Set", &x.Set) -} - -func (x *Range) beforeSave() {} -func (x *Range) save(m state.Map) { - x.beforeSave() - m.Save("Start", &x.Start) - m.Save("End", &x.End) -} - -func (x *Range) afterLoad() {} -func (x *Range) load(m state.Map) { - m.Load("Start", &x.Start) - m.Load("End", &x.End) -} - -func (x *Set) beforeSave() {} -func (x *Set) save(m state.Map) { - x.beforeSave() - var root *SegmentDataSlices = x.saveRoot() - m.SaveValue("root", root) -} - -func (x *Set) afterLoad() {} -func (x *Set) load(m state.Map) { - m.LoadValue("root", new(*SegmentDataSlices), func(y interface{}) { x.loadRoot(y.(*SegmentDataSlices)) }) -} - -func (x *node) beforeSave() {} -func (x *node) save(m state.Map) { - x.beforeSave() - m.Save("nrSegments", &x.nrSegments) - m.Save("parent", &x.parent) - m.Save("parentIndex", &x.parentIndex) - m.Save("hasChildren", &x.hasChildren) - m.Save("keys", &x.keys) - m.Save("values", &x.values) - m.Save("children", &x.children) -} - -func (x *node) afterLoad() {} -func (x *node) load(m state.Map) { - m.Load("nrSegments", &x.nrSegments) - m.Load("parent", &x.parent) - m.Load("parentIndex", &x.parentIndex) - m.Load("hasChildren", &x.hasChildren) - m.Load("keys", &x.keys) - m.Load("values", &x.values) - m.Load("children", &x.children) -} - -func (x *SegmentDataSlices) beforeSave() {} -func (x *SegmentDataSlices) save(m state.Map) { - x.beforeSave() - m.Save("Start", &x.Start) - m.Save("End", &x.End) - m.Save("Values", &x.Values) -} - -func (x *SegmentDataSlices) afterLoad() {} -func (x *SegmentDataSlices) load(m state.Map) { - m.Load("Start", &x.Start) - m.Load("End", &x.End) - m.Load("Values", &x.Values) -} - -func init() { - state.Register("ashmem.Area", (*Area)(nil), state.Fns{Save: (*Area).save, Load: (*Area).load}) - state.Register("ashmem.Device", (*Device)(nil), state.Fns{Save: (*Device).save, Load: (*Device).load}) - state.Register("ashmem.PinBoard", (*PinBoard)(nil), state.Fns{Save: (*PinBoard).save, Load: (*PinBoard).load}) - state.Register("ashmem.Range", (*Range)(nil), state.Fns{Save: (*Range).save, Load: (*Range).load}) - state.Register("ashmem.Set", (*Set)(nil), state.Fns{Save: (*Set).save, Load: (*Set).load}) - state.Register("ashmem.node", (*node)(nil), state.Fns{Save: (*node).save, Load: (*node).load}) - state.Register("ashmem.SegmentDataSlices", (*SegmentDataSlices)(nil), state.Fns{Save: (*SegmentDataSlices).save, Load: (*SegmentDataSlices).load}) -} diff --git a/pkg/sentry/fs/ashmem/device.go b/pkg/sentry/fs/ashmem/device.go deleted file mode 100644 index 776f54abe..000000000 --- a/pkg/sentry/fs/ashmem/device.go +++ /dev/null @@ -1,61 +0,0 @@ -// Copyright 2018 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 ashmem implements Android ashmem module (Anonymus Shared Memory). -package ashmem - -import ( - "gvisor.dev/gvisor/pkg/abi/linux" - "gvisor.dev/gvisor/pkg/sentry/context" - "gvisor.dev/gvisor/pkg/sentry/fs" - "gvisor.dev/gvisor/pkg/sentry/fs/fsutil" - "gvisor.dev/gvisor/pkg/sentry/usermem" -) - -// Device implements fs.InodeOperations. -// -// +stateify savable -type Device struct { - fsutil.InodeGenericChecker `state:"nosave"` - fsutil.InodeNoExtendedAttributes `state:"nosave"` - fsutil.InodeNoopAllocate `state:"nosave"` - fsutil.InodeNoopRelease `state:"nosave"` - fsutil.InodeNoopTruncate `state:"nosave"` - fsutil.InodeNoopWriteOut `state:"nosave"` - fsutil.InodeNotDirectory `state:"nosave"` - fsutil.InodeNotMappable `state:"nosave"` - fsutil.InodeNotSocket `state:"nosave"` - fsutil.InodeNotSymlink `state:"nosave"` - fsutil.InodeVirtual `state:"nosave"` - - fsutil.InodeSimpleAttributes -} - -var _ fs.InodeOperations = (*Device)(nil) - -// NewDevice creates and initializes a Device structure. -func NewDevice(ctx context.Context, owner fs.FileOwner, fp fs.FilePermissions) *Device { - return &Device{ - InodeSimpleAttributes: fsutil.NewInodeSimpleAttributes(ctx, owner, fp, linux.ANON_INODE_FS_MAGIC), - } -} - -// GetFile implements fs.InodeOperations.GetFile. -func (ad *Device) GetFile(ctx context.Context, d *fs.Dirent, flags fs.FileFlags) (*fs.File, error) { - return fs.NewFile(ctx, d, flags, &Area{ - ad: ad, - tmpfsFile: nil, - perms: usermem.AnyAccess, - }), nil -} diff --git a/pkg/sentry/fs/ashmem/pin_board.go b/pkg/sentry/fs/ashmem/pin_board.go deleted file mode 100644 index c5400dd94..000000000 --- a/pkg/sentry/fs/ashmem/pin_board.go +++ /dev/null @@ -1,127 +0,0 @@ -// Copyright 2018 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 ashmem - -import "gvisor.dev/gvisor/pkg/abi/linux" - -const maxUint64 = ^uint64(0) - -// setFunctions implements segment.Functions generated from segment.Functions for -// uint64 Key and noValue Value. For more information, see the build file and -// segment set implementation at pkg/segment/set.go. -type setFunctions struct{} - -// noValue is a type of range attached value, which is irrelevant here. -type noValue struct{} - -// MinKey implements segment.Functions.MinKey. -func (setFunctions) MinKey() uint64 { - return 0 -} - -// MaxKey implements segment.Functions.MaxKey. -func (setFunctions) MaxKey() uint64 { - return maxUint64 -} - -// ClearValue implements segment.Functions.ClearValue. -func (setFunctions) ClearValue(*noValue) { - return -} - -// Merge implements segment.Functions.Merge. -func (setFunctions) Merge(Range, noValue, Range, noValue) (noValue, bool) { - return noValue{}, true -} - -// Split implements segment.Functions.Split. -func (setFunctions) Split(Range, noValue, uint64) (noValue, noValue) { - return noValue{}, noValue{} -} - -// PinBoard represents a set of pinned ranges in ashmem. -// -// segment.Set is used for implementation where segments represent -// ranges of pinned bytes, while gaps represent ranges of unpinned -// bytes. All ranges are page-aligned. -// -// +stateify savable -type PinBoard struct { - Set -} - -// NewPinBoard creates a new pin board with all pages pinned. -func NewPinBoard() *PinBoard { - var pb PinBoard - pb.PinRange(Range{0, maxUint64}) - return &pb -} - -// PinRange pins all pages in the specified range and returns true -// if there are any newly pinned pages. -func (pb *PinBoard) PinRange(r Range) bool { - pinnedPages := false - for gap := pb.LowerBoundGap(r.Start); gap.Ok() && gap.Start() < r.End; { - common := gap.Range().Intersect(r) - if common.Length() == 0 { - gap = gap.NextGap() - continue - } - pinnedPages = true - gap = pb.Insert(gap, common, noValue{}).NextGap() - } - return pinnedPages -} - -// UnpinRange unpins all pages in the specified range. -func (pb *PinBoard) UnpinRange(r Range) { - for seg := pb.LowerBoundSegment(r.Start); seg.Ok() && seg.Start() < r.End; { - common := seg.Range().Intersect(r) - if common.Length() == 0 { - seg = seg.NextSegment() - continue - } - seg = pb.RemoveRange(common).NextSegment() - } -} - -// RangePinnedStatus returns false if there's at least one unpinned page in the -// specified range. -func (pb *PinBoard) RangePinnedStatus(r Range) bool { - for gap := pb.LowerBoundGap(r.Start); gap.Ok() && gap.Start() < r.End; { - common := gap.Range().Intersect(r) - if common.Length() == 0 { - gap = gap.NextGap() - continue - } - return false - } - return true -} - -// RangeFromAshmemPin converts ashmem's original pin structure -// to Range. -func RangeFromAshmemPin(ap linux.AshmemPin) Range { - if ap.Len == 0 { - return Range{ - uint64(ap.Offset), - maxUint64, - } - } - return Range{ - uint64(ap.Offset), - uint64(ap.Offset) + uint64(ap.Len), - } -} diff --git a/pkg/sentry/fs/ashmem/uint64_range.go b/pkg/sentry/fs/ashmem/uint64_range.go deleted file mode 100755 index d71a10b16..000000000 --- a/pkg/sentry/fs/ashmem/uint64_range.go +++ /dev/null @@ -1,62 +0,0 @@ -package ashmem - -// A Range represents a contiguous range of T. -// -// +stateify savable -type Range struct { - // Start is the inclusive start of the range. - Start uint64 - - // End is the exclusive end of the range. - End uint64 -} - -// WellFormed returns true if r.Start <= r.End. All other methods on a Range -// require that the Range is well-formed. -func (r Range) WellFormed() bool { - return r.Start <= r.End -} - -// Length returns the length of the range. -func (r Range) Length() uint64 { - return r.End - r.Start -} - -// Contains returns true if r contains x. -func (r Range) Contains(x uint64) bool { - return r.Start <= x && x < r.End -} - -// Overlaps returns true if r and r2 overlap. -func (r Range) Overlaps(r2 Range) bool { - return r.Start < r2.End && r2.Start < r.End -} - -// IsSupersetOf returns true if r is a superset of r2; that is, the range r2 is -// contained within r. -func (r Range) IsSupersetOf(r2 Range) bool { - return r.Start <= r2.Start && r.End >= r2.End -} - -// Intersect returns a range consisting of the intersection between r and r2. -// If r and r2 do not overlap, Intersect returns a range with unspecified -// bounds, but for which Length() == 0. -func (r Range) Intersect(r2 Range) Range { - if r.Start < r2.Start { - r.Start = r2.Start - } - if r.End > r2.End { - r.End = r2.End - } - if r.End < r.Start { - r.End = r.Start - } - return r -} - -// CanSplitAt returns true if it is legal to split a segment spanning the range -// r at x; that is, splitting at x would produce two ranges, both of which have -// non-zero length. -func (r Range) CanSplitAt(x uint64) bool { - return r.Contains(x) && r.Start < x -} diff --git a/pkg/sentry/fs/ashmem/uint64_set.go b/pkg/sentry/fs/ashmem/uint64_set.go deleted file mode 100755 index a4860175a..000000000 --- a/pkg/sentry/fs/ashmem/uint64_set.go +++ /dev/null @@ -1,1270 +0,0 @@ -package ashmem - -import ( - "bytes" - "fmt" -) - -const ( - // minDegree is the minimum degree of an internal node in a Set B-tree. - // - // - Any non-root node has at least minDegree-1 segments. - // - // - Any non-root internal (non-leaf) node has at least minDegree children. - // - // - The root node may have fewer than minDegree-1 segments, but it may - // only have 0 segments if the tree is empty. - // - // Our implementation requires minDegree >= 3. Higher values of minDegree - // usually improve performance, but increase memory usage for small sets. - minDegree = 3 - - maxDegree = 2 * minDegree -) - -// A Set is a mapping of segments with non-overlapping Range keys. The zero -// value for a Set is an empty set. Set values are not safely movable nor -// copyable. Set is thread-compatible. -// -// +stateify savable -type Set struct { - root node `state:".(*SegmentDataSlices)"` -} - -// IsEmpty returns true if the set contains no segments. -func (s *Set) IsEmpty() bool { - return s.root.nrSegments == 0 -} - -// IsEmptyRange returns true iff no segments in the set overlap the given -// range. This is semantically equivalent to s.SpanRange(r) == 0, but may be -// more efficient. -func (s *Set) IsEmptyRange(r Range) bool { - switch { - case r.Length() < 0: - panic(fmt.Sprintf("invalid range %v", r)) - case r.Length() == 0: - return true - } - _, gap := s.Find(r.Start) - if !gap.Ok() { - return false - } - return r.End <= gap.End() -} - -// Span returns the total size of all segments in the set. -func (s *Set) Span() uint64 { - var sz uint64 - for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { - sz += seg.Range().Length() - } - return sz -} - -// SpanRange returns the total size of the intersection of segments in the set -// with the given range. -func (s *Set) SpanRange(r Range) uint64 { - switch { - case r.Length() < 0: - panic(fmt.Sprintf("invalid range %v", r)) - case r.Length() == 0: - return 0 - } - var sz uint64 - for seg := s.LowerBoundSegment(r.Start); seg.Ok() && seg.Start() < r.End; seg = seg.NextSegment() { - sz += seg.Range().Intersect(r).Length() - } - return sz -} - -// FirstSegment returns the first segment in the set. If the set is empty, -// FirstSegment returns a terminal iterator. -func (s *Set) FirstSegment() Iterator { - if s.root.nrSegments == 0 { - return Iterator{} - } - return s.root.firstSegment() -} - -// LastSegment returns the last segment in the set. If the set is empty, -// LastSegment returns a terminal iterator. -func (s *Set) LastSegment() Iterator { - if s.root.nrSegments == 0 { - return Iterator{} - } - return s.root.lastSegment() -} - -// FirstGap returns the first gap in the set. -func (s *Set) FirstGap() GapIterator { - n := &s.root - for n.hasChildren { - n = n.children[0] - } - return GapIterator{n, 0} -} - -// LastGap returns the last gap in the set. -func (s *Set) LastGap() GapIterator { - n := &s.root - for n.hasChildren { - n = n.children[n.nrSegments] - } - return GapIterator{n, n.nrSegments} -} - -// Find returns the segment or gap whose range contains the given key. If a -// segment is found, the returned Iterator is non-terminal and the -// returned GapIterator is terminal. Otherwise, the returned Iterator is -// terminal and the returned GapIterator is non-terminal. -func (s *Set) Find(key uint64) (Iterator, GapIterator) { - n := &s.root - for { - - lower := 0 - upper := n.nrSegments - for lower < upper { - i := lower + (upper-lower)/2 - if r := n.keys[i]; key < r.End { - if key >= r.Start { - return Iterator{n, i}, GapIterator{} - } - upper = i - } else { - lower = i + 1 - } - } - i := lower - if !n.hasChildren { - return Iterator{}, GapIterator{n, i} - } - n = n.children[i] - } -} - -// FindSegment returns the segment whose range contains the given key. If no -// such segment exists, FindSegment returns a terminal iterator. -func (s *Set) FindSegment(key uint64) Iterator { - seg, _ := s.Find(key) - return seg -} - -// LowerBoundSegment returns the segment with the lowest range that contains a -// key greater than or equal to min. If no such segment exists, -// LowerBoundSegment returns a terminal iterator. -func (s *Set) LowerBoundSegment(min uint64) Iterator { - seg, gap := s.Find(min) - if seg.Ok() { - return seg - } - return gap.NextSegment() -} - -// UpperBoundSegment returns the segment with the highest range that contains a -// key less than or equal to max. If no such segment exists, UpperBoundSegment -// returns a terminal iterator. -func (s *Set) UpperBoundSegment(max uint64) Iterator { - seg, gap := s.Find(max) - if seg.Ok() { - return seg - } - return gap.PrevSegment() -} - -// FindGap returns the gap containing the given key. If no such gap exists -// (i.e. the set contains a segment containing that key), FindGap returns a -// terminal iterator. -func (s *Set) FindGap(key uint64) GapIterator { - _, gap := s.Find(key) - return gap -} - -// LowerBoundGap returns the gap with the lowest range that is greater than or -// equal to min. -func (s *Set) LowerBoundGap(min uint64) GapIterator { - seg, gap := s.Find(min) - if gap.Ok() { - return gap - } - return seg.NextGap() -} - -// UpperBoundGap returns the gap with the highest range that is less than or -// equal to max. -func (s *Set) UpperBoundGap(max uint64) GapIterator { - seg, gap := s.Find(max) - if gap.Ok() { - return gap - } - return seg.PrevGap() -} - -// Add inserts the given segment into the set and returns true. If the new -// segment can be merged with adjacent segments, Add will do so. If the new -// segment would overlap an existing segment, Add returns false. If Add -// succeeds, all existing iterators are invalidated. -func (s *Set) Add(r Range, val noValue) bool { - if r.Length() <= 0 { - panic(fmt.Sprintf("invalid segment range %v", r)) - } - gap := s.FindGap(r.Start) - if !gap.Ok() { - return false - } - if r.End > gap.End() { - return false - } - s.Insert(gap, r, val) - return true -} - -// AddWithoutMerging inserts the given segment into the set and returns true. -// If it would overlap an existing segment, AddWithoutMerging does nothing and -// returns false. If AddWithoutMerging succeeds, all existing iterators are -// invalidated. -func (s *Set) AddWithoutMerging(r Range, val noValue) bool { - if r.Length() <= 0 { - panic(fmt.Sprintf("invalid segment range %v", r)) - } - gap := s.FindGap(r.Start) - if !gap.Ok() { - return false - } - if r.End > gap.End() { - return false - } - s.InsertWithoutMergingUnchecked(gap, r, val) - return true -} - -// Insert inserts the given segment into the given gap. If the new segment can -// be merged with adjacent segments, Insert will do so. Insert returns an -// iterator to the segment containing the inserted value (which may have been -// merged with other values). All existing iterators (including gap, but not -// including the returned iterator) are invalidated. -// -// If the gap cannot accommodate the segment, or if r is invalid, Insert panics. -// -// Insert is semantically equivalent to a InsertWithoutMerging followed by a -// Merge, but may be more efficient. Note that there is no unchecked variant of -// Insert since Insert must retrieve and inspect gap's predecessor and -// successor segments regardless. -func (s *Set) Insert(gap GapIterator, r Range, val noValue) Iterator { - if r.Length() <= 0 { - panic(fmt.Sprintf("invalid segment range %v", r)) - } - prev, next := gap.PrevSegment(), gap.NextSegment() - if prev.Ok() && prev.End() > r.Start { - panic(fmt.Sprintf("new segment %v overlaps predecessor %v", r, prev.Range())) - } - if next.Ok() && next.Start() < r.End { - panic(fmt.Sprintf("new segment %v overlaps successor %v", r, next.Range())) - } - if prev.Ok() && prev.End() == r.Start { - if mval, ok := (setFunctions{}).Merge(prev.Range(), prev.Value(), r, val); ok { - prev.SetEndUnchecked(r.End) - prev.SetValue(mval) - if next.Ok() && next.Start() == r.End { - val = mval - if mval, ok := (setFunctions{}).Merge(prev.Range(), val, next.Range(), next.Value()); ok { - prev.SetEndUnchecked(next.End()) - prev.SetValue(mval) - return s.Remove(next).PrevSegment() - } - } - return prev - } - } - if next.Ok() && next.Start() == r.End { - if mval, ok := (setFunctions{}).Merge(r, val, next.Range(), next.Value()); ok { - next.SetStartUnchecked(r.Start) - next.SetValue(mval) - return next - } - } - return s.InsertWithoutMergingUnchecked(gap, r, val) -} - -// InsertWithoutMerging inserts the given segment into the given gap and -// returns an iterator to the inserted segment. All existing iterators -// (including gap, but not including the returned iterator) are invalidated. -// -// If the gap cannot accommodate the segment, or if r is invalid, -// InsertWithoutMerging panics. -func (s *Set) InsertWithoutMerging(gap GapIterator, r Range, val noValue) Iterator { - if r.Length() <= 0 { - panic(fmt.Sprintf("invalid segment range %v", r)) - } - if gr := gap.Range(); !gr.IsSupersetOf(r) { - panic(fmt.Sprintf("cannot insert segment range %v into gap range %v", r, gr)) - } - return s.InsertWithoutMergingUnchecked(gap, r, val) -} - -// InsertWithoutMergingUnchecked inserts the given segment into the given gap -// and returns an iterator to the inserted segment. All existing iterators -// (including gap, but not including the returned iterator) are invalidated. -// -// Preconditions: r.Start >= gap.Start(); r.End <= gap.End(). -func (s *Set) InsertWithoutMergingUnchecked(gap GapIterator, r Range, val noValue) Iterator { - gap = gap.node.rebalanceBeforeInsert(gap) - copy(gap.node.keys[gap.index+1:], gap.node.keys[gap.index:gap.node.nrSegments]) - copy(gap.node.values[gap.index+1:], gap.node.values[gap.index:gap.node.nrSegments]) - gap.node.keys[gap.index] = r - gap.node.values[gap.index] = val - gap.node.nrSegments++ - return Iterator{gap.node, gap.index} -} - -// Remove removes the given segment and returns an iterator to the vacated gap. -// All existing iterators (including seg, but not including the returned -// iterator) are invalidated. -func (s *Set) Remove(seg Iterator) GapIterator { - - if seg.node.hasChildren { - - victim := seg.PrevSegment() - - seg.SetRangeUnchecked(victim.Range()) - seg.SetValue(victim.Value()) - return s.Remove(victim).NextGap() - } - copy(seg.node.keys[seg.index:], seg.node.keys[seg.index+1:seg.node.nrSegments]) - copy(seg.node.values[seg.index:], seg.node.values[seg.index+1:seg.node.nrSegments]) - setFunctions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1]) - seg.node.nrSegments-- - return seg.node.rebalanceAfterRemove(GapIterator{seg.node, seg.index}) -} - -// RemoveAll removes all segments from the set. All existing iterators are -// invalidated. -func (s *Set) RemoveAll() { - s.root = node{} -} - -// RemoveRange removes all segments in the given range. An iterator to the -// newly formed gap is returned, and all existing iterators are invalidated. -func (s *Set) RemoveRange(r Range) GapIterator { - seg, gap := s.Find(r.Start) - if seg.Ok() { - seg = s.Isolate(seg, r) - gap = s.Remove(seg) - } - for seg = gap.NextSegment(); seg.Ok() && seg.Start() < r.End; seg = gap.NextSegment() { - seg = s.Isolate(seg, r) - gap = s.Remove(seg) - } - return gap -} - -// Merge attempts to merge two neighboring segments. If successful, Merge -// returns an iterator to the merged segment, and all existing iterators are -// invalidated. Otherwise, Merge returns a terminal iterator. -// -// If first is not the predecessor of second, Merge panics. -func (s *Set) Merge(first, second Iterator) Iterator { - if first.NextSegment() != second { - panic(fmt.Sprintf("attempt to merge non-neighboring segments %v, %v", first.Range(), second.Range())) - } - return s.MergeUnchecked(first, second) -} - -// MergeUnchecked attempts to merge two neighboring segments. If successful, -// MergeUnchecked returns an iterator to the merged segment, and all existing -// iterators are invalidated. Otherwise, MergeUnchecked returns a terminal -// iterator. -// -// Precondition: first is the predecessor of second: first.NextSegment() == -// second, first == second.PrevSegment(). -func (s *Set) MergeUnchecked(first, second Iterator) Iterator { - if first.End() == second.Start() { - if mval, ok := (setFunctions{}).Merge(first.Range(), first.Value(), second.Range(), second.Value()); ok { - - first.SetEndUnchecked(second.End()) - first.SetValue(mval) - return s.Remove(second).PrevSegment() - } - } - return Iterator{} -} - -// MergeAll attempts to merge all adjacent segments in the set. All existing -// iterators are invalidated. -func (s *Set) MergeAll() { - seg := s.FirstSegment() - if !seg.Ok() { - return - } - next := seg.NextSegment() - for next.Ok() { - if mseg := s.MergeUnchecked(seg, next); mseg.Ok() { - seg, next = mseg, mseg.NextSegment() - } else { - seg, next = next, next.NextSegment() - } - } -} - -// MergeRange attempts to merge all adjacent segments that contain a key in the -// specific range. All existing iterators are invalidated. -func (s *Set) MergeRange(r Range) { - seg := s.LowerBoundSegment(r.Start) - if !seg.Ok() { - return - } - next := seg.NextSegment() - for next.Ok() && next.Range().Start < r.End { - if mseg := s.MergeUnchecked(seg, next); mseg.Ok() { - seg, next = mseg, mseg.NextSegment() - } else { - seg, next = next, next.NextSegment() - } - } -} - -// MergeAdjacent attempts to merge the segment containing r.Start with its -// predecessor, and the segment containing r.End-1 with its successor. -func (s *Set) MergeAdjacent(r Range) { - first := s.FindSegment(r.Start) - if first.Ok() { - if prev := first.PrevSegment(); prev.Ok() { - s.Merge(prev, first) - } - } - last := s.FindSegment(r.End - 1) - if last.Ok() { - if next := last.NextSegment(); next.Ok() { - s.Merge(last, next) - } - } -} - -// Split splits the given segment at the given key and returns iterators to the -// two resulting segments. All existing iterators (including seg, but not -// including the returned iterators) are invalidated. -// -// If the segment cannot be split at split (because split is at the start or -// end of the segment's range, so splitting would produce a segment with zero -// length, or because split falls outside the segment's range altogether), -// Split panics. -func (s *Set) Split(seg Iterator, split uint64) (Iterator, Iterator) { - if !seg.Range().CanSplitAt(split) { - panic(fmt.Sprintf("can't split %v at %v", seg.Range(), split)) - } - return s.SplitUnchecked(seg, split) -} - -// SplitUnchecked splits the given segment at the given key and returns -// iterators to the two resulting segments. All existing iterators (including -// seg, but not including the returned iterators) are invalidated. -// -// Preconditions: seg.Start() < key < seg.End(). -func (s *Set) SplitUnchecked(seg Iterator, split uint64) (Iterator, Iterator) { - val1, val2 := (setFunctions{}).Split(seg.Range(), seg.Value(), split) - end2 := seg.End() - seg.SetEndUnchecked(split) - seg.SetValue(val1) - seg2 := s.InsertWithoutMergingUnchecked(seg.NextGap(), Range{split, end2}, val2) - - return seg2.PrevSegment(), seg2 -} - -// SplitAt splits the segment straddling split, if one exists. SplitAt returns -// true if a segment was split and false otherwise. If SplitAt splits a -// segment, all existing iterators are invalidated. -func (s *Set) SplitAt(split uint64) bool { - if seg := s.FindSegment(split); seg.Ok() && seg.Range().CanSplitAt(split) { - s.SplitUnchecked(seg, split) - return true - } - return false -} - -// Isolate ensures that the given segment's range does not escape r by -// splitting at r.Start and r.End if necessary, and returns an updated iterator -// to the bounded segment. All existing iterators (including seg, but not -// including the returned iterators) are invalidated. -func (s *Set) Isolate(seg Iterator, r Range) Iterator { - if seg.Range().CanSplitAt(r.Start) { - _, seg = s.SplitUnchecked(seg, r.Start) - } - if seg.Range().CanSplitAt(r.End) { - seg, _ = s.SplitUnchecked(seg, r.End) - } - return seg -} - -// ApplyContiguous applies a function to a contiguous range of segments, -// splitting if necessary. The function is applied until the first gap is -// encountered, at which point the gap is returned. If the function is applied -// across the entire range, a terminal gap is returned. All existing iterators -// are invalidated. -// -// N.B. The Iterator must not be invalidated by the function. -func (s *Set) ApplyContiguous(r Range, fn func(seg Iterator)) GapIterator { - seg, gap := s.Find(r.Start) - if !seg.Ok() { - return gap - } - for { - seg = s.Isolate(seg, r) - fn(seg) - if seg.End() >= r.End { - return GapIterator{} - } - gap = seg.NextGap() - if !gap.IsEmpty() { - return gap - } - seg = gap.NextSegment() - if !seg.Ok() { - - return GapIterator{} - } - } -} - -// +stateify savable -type node struct { - // An internal binary tree node looks like: - // - // K - // / \ - // Cl Cr - // - // where all keys in the subtree rooted by Cl (the left subtree) are less - // than K (the key of the parent node), and all keys in the subtree rooted - // by Cr (the right subtree) are greater than K. - // - // An internal B-tree node's indexes work out to look like: - // - // K0 K1 K2 ... Kn-1 - // / \/ \/ \ ... / \ - // C0 C1 C2 C3 ... Cn-1 Cn - // - // where n is nrSegments. - nrSegments int - - // parent is a pointer to this node's parent. If this node is root, parent - // is nil. - parent *node - - // parentIndex is the index of this node in parent.children. - parentIndex int - - // Flag for internal nodes that is technically redundant with "children[0] - // != nil", but is stored in the first cache line. "hasChildren" rather - // than "isLeaf" because false must be the correct value for an empty root. - hasChildren bool - - // Nodes store keys and values in separate arrays to maximize locality in - // the common case (scanning keys for lookup). - keys [maxDegree - 1]Range - values [maxDegree - 1]noValue - children [maxDegree]*node -} - -// firstSegment returns the first segment in the subtree rooted by n. -// -// Preconditions: n.nrSegments != 0. -func (n *node) firstSegment() Iterator { - for n.hasChildren { - n = n.children[0] - } - return Iterator{n, 0} -} - -// lastSegment returns the last segment in the subtree rooted by n. -// -// Preconditions: n.nrSegments != 0. -func (n *node) lastSegment() Iterator { - for n.hasChildren { - n = n.children[n.nrSegments] - } - return Iterator{n, n.nrSegments - 1} -} - -func (n *node) prevSibling() *node { - if n.parent == nil || n.parentIndex == 0 { - return nil - } - return n.parent.children[n.parentIndex-1] -} - -func (n *node) nextSibling() *node { - if n.parent == nil || n.parentIndex == n.parent.nrSegments { - return nil - } - return n.parent.children[n.parentIndex+1] -} - -// rebalanceBeforeInsert splits n and its ancestors if they are full, as -// required for insertion, and returns an updated iterator to the position -// represented by gap. -func (n *node) rebalanceBeforeInsert(gap GapIterator) GapIterator { - if n.parent != nil { - gap = n.parent.rebalanceBeforeInsert(gap) - } - if n.nrSegments < maxDegree-1 { - return gap - } - if n.parent == nil { - - left := &node{ - nrSegments: minDegree - 1, - parent: n, - parentIndex: 0, - hasChildren: n.hasChildren, - } - right := &node{ - nrSegments: minDegree - 1, - parent: n, - parentIndex: 1, - hasChildren: n.hasChildren, - } - copy(left.keys[:minDegree-1], n.keys[:minDegree-1]) - copy(left.values[:minDegree-1], n.values[:minDegree-1]) - copy(right.keys[:minDegree-1], n.keys[minDegree:]) - copy(right.values[:minDegree-1], n.values[minDegree:]) - n.keys[0], n.values[0] = n.keys[minDegree-1], n.values[minDegree-1] - zeroValueSlice(n.values[1:]) - if n.hasChildren { - copy(left.children[:minDegree], n.children[:minDegree]) - copy(right.children[:minDegree], n.children[minDegree:]) - zeroNodeSlice(n.children[2:]) - for i := 0; i < minDegree; i++ { - left.children[i].parent = left - left.children[i].parentIndex = i - right.children[i].parent = right - right.children[i].parentIndex = i - } - } - n.nrSegments = 1 - n.hasChildren = true - n.children[0] = left - n.children[1] = right - if gap.node != n { - return gap - } - if gap.index < minDegree { - return GapIterator{left, gap.index} - } - return GapIterator{right, gap.index - minDegree} - } - - copy(n.parent.keys[n.parentIndex+1:], n.parent.keys[n.parentIndex:n.parent.nrSegments]) - copy(n.parent.values[n.parentIndex+1:], n.parent.values[n.parentIndex:n.parent.nrSegments]) - n.parent.keys[n.parentIndex], n.parent.values[n.parentIndex] = n.keys[minDegree-1], n.values[minDegree-1] - copy(n.parent.children[n.parentIndex+2:], n.parent.children[n.parentIndex+1:n.parent.nrSegments+1]) - for i := n.parentIndex + 2; i < n.parent.nrSegments+2; i++ { - n.parent.children[i].parentIndex = i - } - sibling := &node{ - nrSegments: minDegree - 1, - parent: n.parent, - parentIndex: n.parentIndex + 1, - hasChildren: n.hasChildren, - } - n.parent.children[n.parentIndex+1] = sibling - n.parent.nrSegments++ - copy(sibling.keys[:minDegree-1], n.keys[minDegree:]) - copy(sibling.values[:minDegree-1], n.values[minDegree:]) - zeroValueSlice(n.values[minDegree-1:]) - if n.hasChildren { - copy(sibling.children[:minDegree], n.children[minDegree:]) - zeroNodeSlice(n.children[minDegree:]) - for i := 0; i < minDegree; i++ { - sibling.children[i].parent = sibling - sibling.children[i].parentIndex = i - } - } - n.nrSegments = minDegree - 1 - - if gap.node != n { - return gap - } - if gap.index < minDegree { - return gap - } - return GapIterator{sibling, gap.index - minDegree} -} - -// rebalanceAfterRemove "unsplits" n and its ancestors if they are deficient -// (contain fewer segments than required by B-tree invariants), as required for -// removal, and returns an updated iterator to the position represented by gap. -// -// Precondition: n is the only node in the tree that may currently violate a -// B-tree invariant. -func (n *node) rebalanceAfterRemove(gap GapIterator) GapIterator { - for { - if n.nrSegments >= minDegree-1 { - return gap - } - if n.parent == nil { - - return gap - } - - if sibling := n.prevSibling(); sibling != nil && sibling.nrSegments >= minDegree { - copy(n.keys[1:], n.keys[:n.nrSegments]) - copy(n.values[1:], n.values[:n.nrSegments]) - n.keys[0] = n.parent.keys[n.parentIndex-1] - n.values[0] = n.parent.values[n.parentIndex-1] - n.parent.keys[n.parentIndex-1] = sibling.keys[sibling.nrSegments-1] - n.parent.values[n.parentIndex-1] = sibling.values[sibling.nrSegments-1] - setFunctions{}.ClearValue(&sibling.values[sibling.nrSegments-1]) - if n.hasChildren { - copy(n.children[1:], n.children[:n.nrSegments+1]) - n.children[0] = sibling.children[sibling.nrSegments] - sibling.children[sibling.nrSegments] = nil - n.children[0].parent = n - n.children[0].parentIndex = 0 - for i := 1; i < n.nrSegments+2; i++ { - n.children[i].parentIndex = i - } - } - n.nrSegments++ - sibling.nrSegments-- - if gap.node == sibling && gap.index == sibling.nrSegments { - return GapIterator{n, 0} - } - if gap.node == n { - return GapIterator{n, gap.index + 1} - } - return gap - } - if sibling := n.nextSibling(); sibling != nil && sibling.nrSegments >= minDegree { - n.keys[n.nrSegments] = n.parent.keys[n.parentIndex] - n.values[n.nrSegments] = n.parent.values[n.parentIndex] - n.parent.keys[n.parentIndex] = sibling.keys[0] - n.parent.values[n.parentIndex] = sibling.values[0] - copy(sibling.keys[:sibling.nrSegments-1], sibling.keys[1:]) - copy(sibling.values[:sibling.nrSegments-1], sibling.values[1:]) - setFunctions{}.ClearValue(&sibling.values[sibling.nrSegments-1]) - if n.hasChildren { - n.children[n.nrSegments+1] = sibling.children[0] - copy(sibling.children[:sibling.nrSegments], sibling.children[1:]) - sibling.children[sibling.nrSegments] = nil - n.children[n.nrSegments+1].parent = n - n.children[n.nrSegments+1].parentIndex = n.nrSegments + 1 - for i := 0; i < sibling.nrSegments; i++ { - sibling.children[i].parentIndex = i - } - } - n.nrSegments++ - sibling.nrSegments-- - if gap.node == sibling { - if gap.index == 0 { - return GapIterator{n, n.nrSegments} - } - return GapIterator{sibling, gap.index - 1} - } - return gap - } - - p := n.parent - if p.nrSegments == 1 { - - left, right := p.children[0], p.children[1] - p.nrSegments = left.nrSegments + right.nrSegments + 1 - p.hasChildren = left.hasChildren - p.keys[left.nrSegments] = p.keys[0] - p.values[left.nrSegments] = p.values[0] - copy(p.keys[:left.nrSegments], left.keys[:left.nrSegments]) - copy(p.values[:left.nrSegments], left.values[:left.nrSegments]) - copy(p.keys[left.nrSegments+1:], right.keys[:right.nrSegments]) - copy(p.values[left.nrSegments+1:], right.values[:right.nrSegments]) - if left.hasChildren { - copy(p.children[:left.nrSegments+1], left.children[:left.nrSegments+1]) - copy(p.children[left.nrSegments+1:], right.children[:right.nrSegments+1]) - for i := 0; i < p.nrSegments+1; i++ { - p.children[i].parent = p - p.children[i].parentIndex = i - } - } else { - p.children[0] = nil - p.children[1] = nil - } - if gap.node == left { - return GapIterator{p, gap.index} - } - if gap.node == right { - return GapIterator{p, gap.index + left.nrSegments + 1} - } - return gap - } - // Merge n and either sibling, along with the segment separating the - // two, into whichever of the two nodes comes first. This is the - // reverse of the non-root splitting case in - // node.rebalanceBeforeInsert. - var left, right *node - if n.parentIndex > 0 { - left = n.prevSibling() - right = n - } else { - left = n - right = n.nextSibling() - } - - if gap.node == right { - gap = GapIterator{left, gap.index + left.nrSegments + 1} - } - left.keys[left.nrSegments] = p.keys[left.parentIndex] - left.values[left.nrSegments] = p.values[left.parentIndex] - copy(left.keys[left.nrSegments+1:], right.keys[:right.nrSegments]) - copy(left.values[left.nrSegments+1:], right.values[:right.nrSegments]) - if left.hasChildren { - copy(left.children[left.nrSegments+1:], right.children[:right.nrSegments+1]) - for i := left.nrSegments + 1; i < left.nrSegments+right.nrSegments+2; i++ { - left.children[i].parent = left - left.children[i].parentIndex = i - } - } - left.nrSegments += right.nrSegments + 1 - copy(p.keys[left.parentIndex:], p.keys[left.parentIndex+1:p.nrSegments]) - copy(p.values[left.parentIndex:], p.values[left.parentIndex+1:p.nrSegments]) - setFunctions{}.ClearValue(&p.values[p.nrSegments-1]) - copy(p.children[left.parentIndex+1:], p.children[left.parentIndex+2:p.nrSegments+1]) - for i := 0; i < p.nrSegments; i++ { - p.children[i].parentIndex = i - } - p.children[p.nrSegments] = nil - p.nrSegments-- - - n = p - } -} - -// A Iterator is conceptually one of: -// -// - A pointer to a segment in a set; or -// -// - A terminal iterator, which is a sentinel indicating that the end of -// iteration has been reached. -// -// Iterators are copyable values and are meaningfully equality-comparable. The -// zero value of Iterator is a terminal iterator. -// -// Unless otherwise specified, any mutation of a set invalidates all existing -// iterators into the set. -type Iterator struct { - // node is the node containing the iterated segment. If the iterator is - // terminal, node is nil. - node *node - - // index is the index of the segment in node.keys/values. - index int -} - -// Ok returns true if the iterator is not terminal. All other methods are only -// valid for non-terminal iterators. -func (seg Iterator) Ok() bool { - return seg.node != nil -} - -// Range returns the iterated segment's range key. -func (seg Iterator) Range() Range { - return seg.node.keys[seg.index] -} - -// Start is equivalent to Range().Start, but should be preferred if only the -// start of the range is needed. -func (seg Iterator) Start() uint64 { - return seg.node.keys[seg.index].Start -} - -// End is equivalent to Range().End, but should be preferred if only the end of -// the range is needed. -func (seg Iterator) End() uint64 { - return seg.node.keys[seg.index].End -} - -// SetRangeUnchecked mutates the iterated segment's range key. This operation -// does not invalidate any iterators. -// -// Preconditions: -// -// - r.Length() > 0. -// -// - The new range must not overlap an existing one: If seg.NextSegment().Ok(), -// then r.end <= seg.NextSegment().Start(); if seg.PrevSegment().Ok(), then -// r.start >= seg.PrevSegment().End(). -func (seg Iterator) SetRangeUnchecked(r Range) { - seg.node.keys[seg.index] = r -} - -// SetRange mutates the iterated segment's range key. If the new range would -// cause the iterated segment to overlap another segment, or if the new range -// is invalid, SetRange panics. This operation does not invalidate any -// iterators. -func (seg Iterator) SetRange(r Range) { - if r.Length() <= 0 { - panic(fmt.Sprintf("invalid segment range %v", r)) - } - if prev := seg.PrevSegment(); prev.Ok() && r.Start < prev.End() { - panic(fmt.Sprintf("new segment range %v overlaps segment range %v", r, prev.Range())) - } - if next := seg.NextSegment(); next.Ok() && r.End > next.Start() { - panic(fmt.Sprintf("new segment range %v overlaps segment range %v", r, next.Range())) - } - seg.SetRangeUnchecked(r) -} - -// SetStartUnchecked mutates the iterated segment's start. This operation does -// not invalidate any iterators. -// -// Preconditions: The new start must be valid: start < seg.End(); if -// seg.PrevSegment().Ok(), then start >= seg.PrevSegment().End(). -func (seg Iterator) SetStartUnchecked(start uint64) { - seg.node.keys[seg.index].Start = start -} - -// SetStart mutates the iterated segment's start. If the new start value would -// cause the iterated segment to overlap another segment, or would result in an -// invalid range, SetStart panics. This operation does not invalidate any -// iterators. -func (seg Iterator) SetStart(start uint64) { - if start >= seg.End() { - panic(fmt.Sprintf("new start %v would invalidate segment range %v", start, seg.Range())) - } - if prev := seg.PrevSegment(); prev.Ok() && start < prev.End() { - panic(fmt.Sprintf("new start %v would cause segment range %v to overlap segment range %v", start, seg.Range(), prev.Range())) - } - seg.SetStartUnchecked(start) -} - -// SetEndUnchecked mutates the iterated segment's end. This operation does not -// invalidate any iterators. -// -// Preconditions: The new end must be valid: end > seg.Start(); if -// seg.NextSegment().Ok(), then end <= seg.NextSegment().Start(). -func (seg Iterator) SetEndUnchecked(end uint64) { - seg.node.keys[seg.index].End = end -} - -// SetEnd mutates the iterated segment's end. If the new end value would cause -// the iterated segment to overlap another segment, or would result in an -// invalid range, SetEnd panics. This operation does not invalidate any -// iterators. -func (seg Iterator) SetEnd(end uint64) { - if end <= seg.Start() { - panic(fmt.Sprintf("new end %v would invalidate segment range %v", end, seg.Range())) - } - if next := seg.NextSegment(); next.Ok() && end > next.Start() { - panic(fmt.Sprintf("new end %v would cause segment range %v to overlap segment range %v", end, seg.Range(), next.Range())) - } - seg.SetEndUnchecked(end) -} - -// Value returns a copy of the iterated segment's value. -func (seg Iterator) Value() noValue { - return seg.node.values[seg.index] -} - -// ValuePtr returns a pointer to the iterated segment's value. The pointer is -// invalidated if the iterator is invalidated. This operation does not -// invalidate any iterators. -func (seg Iterator) ValuePtr() *noValue { - return &seg.node.values[seg.index] -} - -// SetValue mutates the iterated segment's value. This operation does not -// invalidate any iterators. -func (seg Iterator) SetValue(val noValue) { - seg.node.values[seg.index] = val -} - -// PrevSegment returns the iterated segment's predecessor. If there is no -// preceding segment, PrevSegment returns a terminal iterator. -func (seg Iterator) PrevSegment() Iterator { - if seg.node.hasChildren { - return seg.node.children[seg.index].lastSegment() - } - if seg.index > 0 { - return Iterator{seg.node, seg.index - 1} - } - if seg.node.parent == nil { - return Iterator{} - } - return segmentBeforePosition(seg.node.parent, seg.node.parentIndex) -} - -// NextSegment returns the iterated segment's successor. If there is no -// succeeding segment, NextSegment returns a terminal iterator. -func (seg Iterator) NextSegment() Iterator { - if seg.node.hasChildren { - return seg.node.children[seg.index+1].firstSegment() - } - if seg.index < seg.node.nrSegments-1 { - return Iterator{seg.node, seg.index + 1} - } - if seg.node.parent == nil { - return Iterator{} - } - return segmentAfterPosition(seg.node.parent, seg.node.parentIndex) -} - -// PrevGap returns the gap immediately before the iterated segment. -func (seg Iterator) PrevGap() GapIterator { - if seg.node.hasChildren { - - return seg.node.children[seg.index].lastSegment().NextGap() - } - return GapIterator{seg.node, seg.index} -} - -// NextGap returns the gap immediately after the iterated segment. -func (seg Iterator) NextGap() GapIterator { - if seg.node.hasChildren { - return seg.node.children[seg.index+1].firstSegment().PrevGap() - } - return GapIterator{seg.node, seg.index + 1} -} - -// PrevNonEmpty returns the iterated segment's predecessor if it is adjacent, -// or the gap before the iterated segment otherwise. If seg.Start() == -// Functions.MinKey(), PrevNonEmpty will return two terminal iterators. -// Otherwise, exactly one of the iterators returned by PrevNonEmpty will be -// non-terminal. -func (seg Iterator) PrevNonEmpty() (Iterator, GapIterator) { - gap := seg.PrevGap() - if gap.Range().Length() != 0 { - return Iterator{}, gap - } - return gap.PrevSegment(), GapIterator{} -} - -// NextNonEmpty returns the iterated segment's successor if it is adjacent, or -// the gap after the iterated segment otherwise. If seg.End() == -// Functions.MaxKey(), NextNonEmpty will return two terminal iterators. -// Otherwise, exactly one of the iterators returned by NextNonEmpty will be -// non-terminal. -func (seg Iterator) NextNonEmpty() (Iterator, GapIterator) { - gap := seg.NextGap() - if gap.Range().Length() != 0 { - return Iterator{}, gap - } - return gap.NextSegment(), GapIterator{} -} - -// A GapIterator is conceptually one of: -// -// - A pointer to a position between two segments, before the first segment, or -// after the last segment in a set, called a *gap*; or -// -// - A terminal iterator, which is a sentinel indicating that the end of -// iteration has been reached. -// -// Note that the gap between two adjacent segments exists (iterators to it are -// non-terminal), but has a length of zero. GapIterator.IsEmpty returns true -// for such gaps. An empty set contains a single gap, spanning the entire range -// of the set's keys. -// -// GapIterators are copyable values and are meaningfully equality-comparable. -// The zero value of GapIterator is a terminal iterator. -// -// Unless otherwise specified, any mutation of a set invalidates all existing -// iterators into the set. -type GapIterator struct { - // The representation of a GapIterator is identical to that of an Iterator, - // except that index corresponds to positions between segments in the same - // way as for node.children (see comment for node.nrSegments). - node *node - index int -} - -// Ok returns true if the iterator is not terminal. All other methods are only -// valid for non-terminal iterators. -func (gap GapIterator) Ok() bool { - return gap.node != nil -} - -// Range returns the range spanned by the iterated gap. -func (gap GapIterator) Range() Range { - return Range{gap.Start(), gap.End()} -} - -// Start is equivalent to Range().Start, but should be preferred if only the -// start of the range is needed. -func (gap GapIterator) Start() uint64 { - if ps := gap.PrevSegment(); ps.Ok() { - return ps.End() - } - return setFunctions{}.MinKey() -} - -// End is equivalent to Range().End, but should be preferred if only the end of -// the range is needed. -func (gap GapIterator) End() uint64 { - if ns := gap.NextSegment(); ns.Ok() { - return ns.Start() - } - return setFunctions{}.MaxKey() -} - -// IsEmpty returns true if the iterated gap is empty (that is, the "gap" is -// between two adjacent segments.) -func (gap GapIterator) IsEmpty() bool { - return gap.Range().Length() == 0 -} - -// PrevSegment returns the segment immediately before the iterated gap. If no -// such segment exists, PrevSegment returns a terminal iterator. -func (gap GapIterator) PrevSegment() Iterator { - return segmentBeforePosition(gap.node, gap.index) -} - -// NextSegment returns the segment immediately after the iterated gap. If no -// such segment exists, NextSegment returns a terminal iterator. -func (gap GapIterator) NextSegment() Iterator { - return segmentAfterPosition(gap.node, gap.index) -} - -// PrevGap returns the iterated gap's predecessor. If no such gap exists, -// PrevGap returns a terminal iterator. -func (gap GapIterator) PrevGap() GapIterator { - seg := gap.PrevSegment() - if !seg.Ok() { - return GapIterator{} - } - return seg.PrevGap() -} - -// NextGap returns the iterated gap's successor. If no such gap exists, NextGap -// returns a terminal iterator. -func (gap GapIterator) NextGap() GapIterator { - seg := gap.NextSegment() - if !seg.Ok() { - return GapIterator{} - } - return seg.NextGap() -} - -// segmentBeforePosition returns the predecessor segment of the position given -// by n.children[i], which may or may not contain a child. If no such segment -// exists, segmentBeforePosition returns a terminal iterator. -func segmentBeforePosition(n *node, i int) Iterator { - for i == 0 { - if n.parent == nil { - return Iterator{} - } - n, i = n.parent, n.parentIndex - } - return Iterator{n, i - 1} -} - -// segmentAfterPosition returns the successor segment of the position given by -// n.children[i], which may or may not contain a child. If no such segment -// exists, segmentAfterPosition returns a terminal iterator. -func segmentAfterPosition(n *node, i int) Iterator { - for i == n.nrSegments { - if n.parent == nil { - return Iterator{} - } - n, i = n.parent, n.parentIndex - } - return Iterator{n, i} -} - -func zeroValueSlice(slice []noValue) { - - for i := range slice { - setFunctions{}.ClearValue(&slice[i]) - } -} - -func zeroNodeSlice(slice []*node) { - for i := range slice { - slice[i] = nil - } -} - -// String stringifies a Set for debugging. -func (s *Set) String() string { - return s.root.String() -} - -// String stringifies a node (and all of its children) for debugging. -func (n *node) String() string { - var buf bytes.Buffer - n.writeDebugString(&buf, "") - return buf.String() -} - -func (n *node) writeDebugString(buf *bytes.Buffer, prefix string) { - if n.hasChildren != (n.nrSegments > 0 && n.children[0] != nil) { - buf.WriteString(prefix) - buf.WriteString(fmt.Sprintf("WARNING: inconsistent value of hasChildren: got %v, want %v\n", n.hasChildren, !n.hasChildren)) - } - for i := 0; i < n.nrSegments; i++ { - if child := n.children[i]; child != nil { - cprefix := fmt.Sprintf("%s- % 3d ", prefix, i) - if child.parent != n || child.parentIndex != i { - buf.WriteString(cprefix) - buf.WriteString(fmt.Sprintf("WARNING: inconsistent linkage to parent: got (%p, %d), want (%p, %d)\n", child.parent, child.parentIndex, n, i)) - } - child.writeDebugString(buf, fmt.Sprintf("%s- % 3d ", prefix, i)) - } - buf.WriteString(prefix) - buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i])) - } - if child := n.children[n.nrSegments]; child != nil { - child.writeDebugString(buf, fmt.Sprintf("%s- % 3d ", prefix, n.nrSegments)) - } -} - -// SegmentDataSlices represents segments from a set as slices of start, end, and -// values. SegmentDataSlices is primarily used as an intermediate representation -// for save/restore and the layout here is optimized for that. -// -// +stateify savable -type SegmentDataSlices struct { - Start []uint64 - End []uint64 - Values []noValue -} - -// ExportSortedSlice returns a copy of all segments in the given set, in ascending -// key order. -func (s *Set) ExportSortedSlices() *SegmentDataSlices { - var sds SegmentDataSlices - for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() { - sds.Start = append(sds.Start, seg.Start()) - sds.End = append(sds.End, seg.End()) - sds.Values = append(sds.Values, seg.Value()) - } - sds.Start = sds.Start[:len(sds.Start):len(sds.Start)] - sds.End = sds.End[:len(sds.End):len(sds.End)] - sds.Values = sds.Values[:len(sds.Values):len(sds.Values)] - return &sds -} - -// ImportSortedSlice initializes the given set from the given slice. -// -// Preconditions: s must be empty. sds must represent a valid set (the segments -// in sds must have valid lengths that do not overlap). The segments in sds -// must be sorted in ascending key order. -func (s *Set) ImportSortedSlices(sds *SegmentDataSlices) error { - if !s.IsEmpty() { - return fmt.Errorf("cannot import into non-empty set %v", s) - } - gap := s.FirstGap() - for i := range sds.Start { - r := Range{sds.Start[i], sds.End[i]} - if !gap.Range().IsSupersetOf(r) { - return fmt.Errorf("segment overlaps a preceding segment or is incorrectly sorted: [%d, %d) => %v", sds.Start[i], sds.End[i], sds.Values[i]) - } - gap = s.InsertWithoutMerging(gap, r, sds.Values[i]).NextGap() - } - return nil -} -func (s *Set) saveRoot() *SegmentDataSlices { - return s.ExportSortedSlices() -} - -func (s *Set) loadRoot(sds *SegmentDataSlices) { - if err := s.ImportSortedSlices(sds); err != nil { - panic(err) - } -} diff --git a/pkg/sentry/fs/binder/binder.go b/pkg/sentry/fs/binder/binder.go deleted file mode 100644 index eef54d787..000000000 --- a/pkg/sentry/fs/binder/binder.go +++ /dev/null @@ -1,260 +0,0 @@ -// Copyright 2018 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 binder implements Android Binder IPC module. -package binder - -import ( - "sync" - - "gvisor.dev/gvisor/pkg/abi/linux" - "gvisor.dev/gvisor/pkg/sentry/arch" - "gvisor.dev/gvisor/pkg/sentry/context" - "gvisor.dev/gvisor/pkg/sentry/fs" - "gvisor.dev/gvisor/pkg/sentry/fs/fsutil" - "gvisor.dev/gvisor/pkg/sentry/kernel" - "gvisor.dev/gvisor/pkg/sentry/memmap" - "gvisor.dev/gvisor/pkg/sentry/pgalloc" - "gvisor.dev/gvisor/pkg/sentry/platform" - "gvisor.dev/gvisor/pkg/sentry/usage" - "gvisor.dev/gvisor/pkg/sentry/usermem" - "gvisor.dev/gvisor/pkg/syserror" - "gvisor.dev/gvisor/pkg/waiter" -) - -const ( - currentProtocolVersion = 8 - - // mmapSizeLimit is the upper limit for mapped memory size in Binder. - mmapSizeLimit = 4 * 1024 * 1024 // 4MB -) - -// Device implements fs.InodeOperations. -// -// +stateify savable -type Device struct { - fsutil.InodeGenericChecker `state:"nosave"` - fsutil.InodeNoExtendedAttributes `state:"nosave"` - fsutil.InodeNoopAllocate `state:"nosave"` - fsutil.InodeNoopRelease `state:"nosave"` - fsutil.InodeNoopTruncate `state:"nosave"` - fsutil.InodeNoopWriteOut `state:"nosave"` - fsutil.InodeNotDirectory `state:"nosave"` - fsutil.InodeNotMappable `state:"nosave"` - fsutil.InodeNotSocket `state:"nosave"` - fsutil.InodeNotSymlink `state:"nosave"` - fsutil.InodeVirtual `state:"nosave"` - - fsutil.InodeSimpleAttributes -} - -var _ fs.InodeOperations = (*Device)(nil) - -// NewDevice creates and initializes a Device structure. -func NewDevice(ctx context.Context, owner fs.FileOwner, fp fs.FilePermissions) *Device { - return &Device{ - InodeSimpleAttributes: fsutil.NewInodeSimpleAttributes(ctx, owner, fp, 0), - } -} - -// GetFile implements fs.InodeOperations.GetFile. -// -// TODO(b/30946773): Add functionality to GetFile: Additional fields will be -// needed in the Device structure, initialize them here. Also, Device will need -// to keep track of the created Procs in order to implement BINDER_READ_WRITE -// ioctl. -func (bd *Device) GetFile(ctx context.Context, d *fs.Dirent, flags fs.FileFlags) (*fs.File, error) { - return fs.NewFile(ctx, d, flags, &Proc{ - bd: bd, - task: kernel.TaskFromContext(ctx), - mfp: pgalloc.MemoryFileProviderFromContext(ctx), - }), nil -} - -// Proc implements fs.FileOperations and fs.IoctlGetter. -// -// +stateify savable -type Proc struct { - fsutil.FileNoFsync `state:"nosave"` - fsutil.FileNoSplice `state:"nosave"` - fsutil.FileNotDirReaddir `state:"nosave"` - fsutil.FileUseInodeUnstableAttr `state:"nosave"` - waiter.AlwaysReady `state:"nosave"` - - bd *Device - task *kernel.Task - mfp pgalloc.MemoryFileProvider - - // mu protects fr. - mu sync.Mutex `state:"nosave"` - - // mapped is memory allocated from mfp.MemoryFile() by AddMapping. - mapped platform.FileRange -} - -// Release implements fs.FileOperations.Release. -func (bp *Proc) Release() { - bp.mu.Lock() - defer bp.mu.Unlock() - if bp.mapped.Length() != 0 { - bp.mfp.MemoryFile().DecRef(bp.mapped) - } -} - -// Seek implements fs.FileOperations.Seek. -// -// Binder doesn't support seek operation (unless in debug mode). -func (bp *Proc) Seek(ctx context.Context, file *fs.File, whence fs.SeekWhence, offset int64) (int64, error) { - return offset, syserror.EOPNOTSUPP -} - -// Read implements fs.FileOperations.Read. -// -// Binder doesn't support read operation (unless in debug mode). -func (bp *Proc) Read(ctx context.Context, file *fs.File, dst usermem.IOSequence, offset int64) (int64, error) { - return 0, syserror.EOPNOTSUPP -} - -// Write implements fs.FileOperations.Write. -// -// Binder doesn't support write operation. -func (bp *Proc) Write(ctx context.Context, file *fs.File, src usermem.IOSequence, offset int64) (int64, error) { - return 0, syserror.EOPNOTSUPP -} - -// Flush implements fs.FileOperations.Flush. -// -// TODO(b/30946773): Implement. -func (bp *Proc) Flush(ctx context.Context, file *fs.File) error { - return nil -} - -// ConfigureMMap implements fs.FileOperations.ConfigureMMap. -func (bp *Proc) ConfigureMMap(ctx context.Context, file *fs.File, opts *memmap.MMapOpts) error { - // Compare drivers/android/binder.c:binder_mmap(). - if caller := kernel.TaskFromContext(ctx); caller != bp.task { - return syserror.EINVAL - } - if opts.Length > mmapSizeLimit { - opts.Length = mmapSizeLimit - } - opts.MaxPerms.Write = false - - // TODO(b/30946773): Binder sets VM_DONTCOPY, preventing the created vma - // from being copied across fork(), but we don't support this yet. As - // a result, MMs containing a Binder mapping cannot be forked (MM.Fork will - // fail when AddMapping returns EBUSY). - - return fsutil.GenericConfigureMMap(file, bp, opts) -} - -// Ioctl implements fs.FileOperations.Ioctl. -// -// TODO(b/30946773): Implement. -func (bp *Proc) Ioctl(ctx context.Context, _ *fs.File, io usermem.IO, args arch.SyscallArguments) (uintptr, error) { - // Switch on ioctl request. - switch uint32(args[1].Int()) { - case linux.BinderVersionIoctl: - ver := &linux.BinderVersion{ - ProtocolVersion: currentProtocolVersion, - } - // Copy result to user-space. - _, err := usermem.CopyObjectOut(ctx, io, args[2].Pointer(), ver, usermem.IOOpts{ - AddressSpaceActive: true, - }) - return 0, err - case linux.BinderWriteReadIoctl: - // TODO(b/30946773): Implement. - fallthrough - case linux.BinderSetIdleTimeoutIoctl: - // TODO(b/30946773): Implement. - fallthrough - case linux.BinderSetMaxThreadsIoctl: - // TODO(b/30946773): Implement. - fallthrough - case linux.BinderSetIdlePriorityIoctl: - // TODO(b/30946773): Implement. - fallthrough - case linux.BinderSetContextMgrIoctl: - // TODO(b/30946773): Implement. - fallthrough - case linux.BinderThreadExitIoctl: - // TODO(b/30946773): Implement. - return 0, syserror.ENOSYS - default: - // Ioctls irrelevant to Binder. - return 0, syserror.EINVAL - } -} - -// AddMapping implements memmap.Mappable.AddMapping. -func (bp *Proc) AddMapping(ctx context.Context, ms memmap.MappingSpace, ar usermem.AddrRange, offset uint64, _ bool) error { - bp.mu.Lock() - defer bp.mu.Unlock() - if bp.mapped.Length() != 0 { - // mmap has been called before, which binder_mmap() doesn't like. - return syserror.EBUSY - } - // Binder only allocates and maps a single page up-front - // (drivers/android/binder.c:binder_mmap() => binder_update_page_range()). - fr, err := bp.mfp.MemoryFile().Allocate(usermem.PageSize, usage.Anonymous) - if err != nil { - return err - } - bp.mapped = fr - return nil -} - -// RemoveMapping implements memmap.Mappable.RemoveMapping. -func (*Proc) RemoveMapping(context.Context, memmap.MappingSpace, usermem.AddrRange, uint64, bool) { - // Nothing to do. Notably, we don't free bp.mapped to allow another mmap. -} - -// CopyMapping implements memmap.Mappable.CopyMapping. -func (bp *Proc) CopyMapping(ctx context.Context, ms memmap.MappingSpace, srcAR, dstAR usermem.AddrRange, offset uint64, _ bool) error { - // Nothing to do. Notably, this is one case where CopyMapping isn't - // equivalent to AddMapping, as AddMapping would return EBUSY. - return nil -} - -// Translate implements memmap.Mappable.Translate. -func (bp *Proc) Translate(ctx context.Context, required, optional memmap.MappableRange, at usermem.AccessType) ([]memmap.Translation, error) { - // TODO(b/30946773): In addition to the page initially allocated and mapped - // in AddMapping (Linux: binder_mmap), Binder allocates and maps pages for - // each transaction (Linux: binder_ioctl => binder_ioctl_write_read => - // binder_thread_write => binder_transaction => binder_alloc_buf => - // binder_update_page_range). Since we don't actually implement - // BinderWriteReadIoctl (Linux: BINDER_WRITE_READ), we only ever have the - // first page. - var err error - if required.End > usermem.PageSize { - err = &memmap.BusError{syserror.EFAULT} - } - if required.Start == 0 { - return []memmap.Translation{ - { - Source: memmap.MappableRange{0, usermem.PageSize}, - File: bp.mfp.MemoryFile(), - Offset: bp.mapped.Start, - Perms: usermem.AnyAccess, - }, - }, err - } - return nil, err -} - -// InvalidateUnsavable implements memmap.Mappable.InvalidateUnsavable. -func (bp *Proc) InvalidateUnsavable(ctx context.Context) error { - return nil -} diff --git a/pkg/sentry/fs/binder/binder_state_autogen.go b/pkg/sentry/fs/binder/binder_state_autogen.go deleted file mode 100755 index 1f321e3b6..000000000 --- a/pkg/sentry/fs/binder/binder_state_autogen.go +++ /dev/null @@ -1,40 +0,0 @@ -// automatically generated by stateify. - -package binder - -import ( - "gvisor.dev/gvisor/pkg/state" -) - -func (x *Device) beforeSave() {} -func (x *Device) save(m state.Map) { - x.beforeSave() - m.Save("InodeSimpleAttributes", &x.InodeSimpleAttributes) -} - -func (x *Device) afterLoad() {} -func (x *Device) load(m state.Map) { - m.Load("InodeSimpleAttributes", &x.InodeSimpleAttributes) -} - -func (x *Proc) beforeSave() {} -func (x *Proc) save(m state.Map) { - x.beforeSave() - m.Save("bd", &x.bd) - m.Save("task", &x.task) - m.Save("mfp", &x.mfp) - m.Save("mapped", &x.mapped) -} - -func (x *Proc) afterLoad() {} -func (x *Proc) load(m state.Map) { - m.Load("bd", &x.bd) - m.Load("task", &x.task) - m.Load("mfp", &x.mfp) - m.Load("mapped", &x.mapped) -} - -func init() { - state.Register("binder.Device", (*Device)(nil), state.Fns{Save: (*Device).save, Load: (*Device).load}) - state.Register("binder.Proc", (*Proc)(nil), state.Fns{Save: (*Proc).save, Load: (*Proc).load}) -} diff --git a/pkg/sentry/fs/dev/dev.go b/pkg/sentry/fs/dev/dev.go index fb6c30ff0..d4bbd9807 100644 --- a/pkg/sentry/fs/dev/dev.go +++ b/pkg/sentry/fs/dev/dev.go @@ -20,8 +20,6 @@ import ( "gvisor.dev/gvisor/pkg/sentry/context" "gvisor.dev/gvisor/pkg/sentry/fs" - "gvisor.dev/gvisor/pkg/sentry/fs/ashmem" - "gvisor.dev/gvisor/pkg/sentry/fs/binder" "gvisor.dev/gvisor/pkg/sentry/fs/ramfs" "gvisor.dev/gvisor/pkg/sentry/fs/tmpfs" "gvisor.dev/gvisor/pkg/sentry/usermem" @@ -81,7 +79,7 @@ func newSymlink(ctx context.Context, target string, msrc *fs.MountSource) *fs.In } // New returns the root node of a device filesystem. -func New(ctx context.Context, msrc *fs.MountSource, binderEnabled bool, ashmemEnabled bool) *fs.Inode { +func New(ctx context.Context, msrc *fs.MountSource) *fs.Inode { contents := map[string]*fs.Inode{ "fd": newSymlink(ctx, "/proc/self/fd", msrc), "stdin": newSymlink(ctx, "/proc/self/fd/0", msrc), @@ -118,16 +116,6 @@ func New(ctx context.Context, msrc *fs.MountSource, binderEnabled bool, ashmemEn "ptmx": newSymlink(ctx, "pts/ptmx", msrc), } - if binderEnabled { - binder := binder.NewDevice(ctx, fs.RootOwner, fs.FilePermsFromMode(0666)) - contents["binder"] = newCharacterDevice(ctx, binder, msrc) - } - - if ashmemEnabled { - ashmem := ashmem.NewDevice(ctx, fs.RootOwner, fs.FilePermsFromMode(0666)) - contents["ashmem"] = newCharacterDevice(ctx, ashmem, msrc) - } - iops := ramfs.NewDir(ctx, contents, fs.RootOwner, fs.FilePermsFromMode(0555)) return fs.NewInode(ctx, iops, msrc, fs.StableAttr{ DeviceID: devDevice.DeviceID(), diff --git a/pkg/sentry/fs/dev/fs.go b/pkg/sentry/fs/dev/fs.go index cbc2c2f9b..55f8af704 100644 --- a/pkg/sentry/fs/dev/fs.go +++ b/pkg/sentry/fs/dev/fs.go @@ -15,19 +15,10 @@ package dev import ( - "strconv" - "gvisor.dev/gvisor/pkg/sentry/context" "gvisor.dev/gvisor/pkg/sentry/fs" - "gvisor.dev/gvisor/pkg/syserror" ) -// Optional key containing boolean flag which specifies if Android Binder IPC should be enabled. -const binderEnabledKey = "binder_enabled" - -// Optional key containing boolean flag which specifies if Android ashmem should be enabled. -const ashmemEnabledKey = "ashmem_enabled" - // filesystem is a devtmpfs. // // +stateify savable @@ -67,33 +58,7 @@ func (*filesystem) Flags() fs.FilesystemFlags { // Mount returns a devtmpfs root that can be positioned in the vfs. func (f *filesystem) Mount(ctx context.Context, device string, flags fs.MountSourceFlags, data string, _ interface{}) (*fs.Inode, error) { - // device is always ignored. // devtmpfs backed by ramfs ignores bad options. See fs/ramfs/inode.c:ramfs_parse_options. // -> we should consider parsing the mode and backing devtmpfs by this. - - // Parse generic comma-separated key=value options. - options := fs.GenericMountSourceOptions(data) - - // binerEnabledKey is optional and binder is disabled by default. - binderEnabled := false - if beStr, exists := options[binderEnabledKey]; exists { - var err error - binderEnabled, err = strconv.ParseBool(beStr) - if err != nil { - return nil, syserror.EINVAL - } - } - - // ashmemEnabledKey is optional and ashmem is disabled by default. - ashmemEnabled := false - if aeStr, exists := options[ashmemEnabledKey]; exists { - var err error - ashmemEnabled, err = strconv.ParseBool(aeStr) - if err != nil { - return nil, syserror.EINVAL - } - } - - // Construct the devtmpfs root. - return New(ctx, fs.NewNonCachingMountSource(ctx, f, flags), binderEnabled, ashmemEnabled), nil + return New(ctx, fs.NewNonCachingMountSource(ctx, f, flags)), nil } diff --git a/pkg/sentry/fs/dirent.go b/pkg/sentry/fs/dirent.go index 28651e58b..fbca06761 100644 --- a/pkg/sentry/fs/dirent.go +++ b/pkg/sentry/fs/dirent.go @@ -229,11 +229,13 @@ func newDirent(inode *Inode, name string) *Dirent { if inode != nil { inode.MountSource.IncDirentRefs() } - return &Dirent{ + d := Dirent{ Inode: inode, name: name, children: make(map[string]*refs.WeakRef), } + d.EnableLeakCheck("fs.Dirent") + return &d } // NewNegativeDirent returns a new root negative Dirent. Otherwise same as NewDirent. diff --git a/pkg/sentry/fs/file.go b/pkg/sentry/fs/file.go index 8e1f5674d..bb8117f89 100644 --- a/pkg/sentry/fs/file.go +++ b/pkg/sentry/fs/file.go @@ -130,14 +130,15 @@ type File struct { // to false respectively. func NewFile(ctx context.Context, dirent *Dirent, flags FileFlags, fops FileOperations) *File { dirent.IncRef() - f := &File{ + f := File{ UniqueID: uniqueid.GlobalFromContext(ctx), Dirent: dirent, FileOperations: fops, flags: flags, } f.mu.Init() - return f + f.EnableLeakCheck("fs.File") + return &f } // DecRef destroys the File when it is no longer referenced. diff --git a/pkg/sentry/fs/file_overlay.go b/pkg/sentry/fs/file_overlay.go index c6cbd5631..9820f0b13 100644 --- a/pkg/sentry/fs/file_overlay.go +++ b/pkg/sentry/fs/file_overlay.go @@ -347,13 +347,14 @@ func (*overlayFileOperations) ConfigureMMap(ctx context.Context, file *File, opt // preventing us from saving a proper inode mapping for the // file. file.IncRef() - id := &overlayMappingIdentity{ + id := overlayMappingIdentity{ id: opts.MappingIdentity, overlayFile: file, } + id.EnableLeakCheck("fs.overlayMappingIdentity") // Swap out the old MappingIdentity for the wrapped one. - opts.MappingIdentity = id + opts.MappingIdentity = &id return nil } diff --git a/pkg/sentry/fs/gofer/handles.go b/pkg/sentry/fs/gofer/handles.go index b87c4f150..27eeae3d9 100644 --- a/pkg/sentry/fs/gofer/handles.go +++ b/pkg/sentry/fs/gofer/handles.go @@ -79,11 +79,12 @@ func newHandles(ctx context.Context, file contextFile, flags fs.FileFlags) (*han newFile.close(ctx) return nil, err } - h := &handles{ + h := handles{ File: newFile, Host: hostFile, } - return h, nil + h.EnableLeakCheck("gofer.handles") + return &h, nil } type handleReadWriter struct { diff --git a/pkg/sentry/fs/gofer/path.go b/pkg/sentry/fs/gofer/path.go index b91386909..8c17603f8 100644 --- a/pkg/sentry/fs/gofer/path.go +++ b/pkg/sentry/fs/gofer/path.go @@ -145,16 +145,17 @@ func (i *inodeOperations) Create(ctx context.Context, dir *fs.Inode, name string defer d.DecRef() // Construct the new file, caching the handles if allowed. - h := &handles{ + h := handles{ File: newFile, Host: hostFile, } + h.EnableLeakCheck("gofer.handles") if iops.fileState.canShareHandles() { iops.fileState.handlesMu.Lock() - iops.fileState.setSharedHandlesLocked(flags, h) + iops.fileState.setSharedHandlesLocked(flags, &h) iops.fileState.handlesMu.Unlock() } - return NewFile(ctx, d, name, flags, iops, h), nil + return NewFile(ctx, d, name, flags, iops, &h), nil } // CreateLink uses Create to create a symlink between oldname and newname. diff --git a/pkg/sentry/fs/gofer/session.go b/pkg/sentry/fs/gofer/session.go index 9f7660ed1..69d08a627 100644 --- a/pkg/sentry/fs/gofer/session.go +++ b/pkg/sentry/fs/gofer/session.go @@ -241,7 +241,7 @@ func Root(ctx context.Context, dev string, filesystem fs.Filesystem, superBlockF } // Construct the session. - s := &session{ + s := session{ connID: dev, msize: o.msize, version: o.version, @@ -250,13 +250,14 @@ func Root(ctx context.Context, dev string, filesystem fs.Filesystem, superBlockF superBlockFlags: superBlockFlags, mounter: mounter, } + s.EnableLeakCheck("gofer.session") if o.privateunixsocket { s.endpoints = newEndpointMaps() } // Construct the MountSource with the session and superBlockFlags. - m := fs.NewMountSource(ctx, s, filesystem, superBlockFlags) + m := fs.NewMountSource(ctx, &s, filesystem, superBlockFlags) // Given that gofer files can consume host FDs, restrict the number // of files that can be held by the cache. @@ -290,7 +291,7 @@ func Root(ctx context.Context, dev string, filesystem fs.Filesystem, superBlockF return nil, err } - sattr, iops := newInodeOperations(ctx, s, s.attach, qid, valid, attr, false) + sattr, iops := newInodeOperations(ctx, &s, s.attach, qid, valid, attr, false) return fs.NewInode(ctx, iops, m, sattr), nil } diff --git a/pkg/sentry/fs/gofer/session_state.go b/pkg/sentry/fs/gofer/session_state.go index 29a79441e..d045e04ff 100644 --- a/pkg/sentry/fs/gofer/session_state.go +++ b/pkg/sentry/fs/gofer/session_state.go @@ -111,5 +111,4 @@ func (s *session) afterLoad() { panic("failed to restore endpoint maps: " + err.Error()) } } - } diff --git a/pkg/sentry/fs/host/host_state_autogen.go b/pkg/sentry/fs/host/host_state_autogen.go index 9611da42a..f0e1c4b88 100755 --- a/pkg/sentry/fs/host/host_state_autogen.go +++ b/pkg/sentry/fs/host/host_state_autogen.go @@ -95,17 +95,17 @@ func (x *inodeFileState) load(m state.Map) { func (x *ConnectedEndpoint) save(m state.Map) { x.beforeSave() + m.Save("ref", &x.ref) m.Save("queue", &x.queue) m.Save("path", &x.path) - m.Save("ref", &x.ref) m.Save("srfd", &x.srfd) m.Save("stype", &x.stype) } func (x *ConnectedEndpoint) load(m state.Map) { + m.Load("ref", &x.ref) m.Load("queue", &x.queue) m.Load("path", &x.path) - m.Load("ref", &x.ref) m.LoadWait("srfd", &x.srfd) m.Load("stype", &x.stype) m.AfterLoad(x.afterLoad) diff --git a/pkg/sentry/fs/host/socket.go b/pkg/sentry/fs/host/socket.go index 7fedc88bc..44c4ee5f2 100644 --- a/pkg/sentry/fs/host/socket.go +++ b/pkg/sentry/fs/host/socket.go @@ -47,12 +47,12 @@ const maxSendBufferSize = 8 << 20 // // +stateify savable type ConnectedEndpoint struct { - queue *waiter.Queue - path string - // ref keeps track of references to a connectedEndpoint. ref refs.AtomicRefCount + queue *waiter.Queue + path string + // If srfd >= 0, it is the host FD that file was imported from. srfd int `state:"wait"` @@ -133,6 +133,8 @@ func NewConnectedEndpoint(ctx context.Context, file *fd.FD, queue *waiter.Queue, // AtomicRefCounters start off with a single reference. We need two. e.ref.IncRef() + e.ref.EnableLeakCheck("host.ConnectedEndpoint") + return &e, nil } diff --git a/pkg/sentry/fs/inode.go b/pkg/sentry/fs/inode.go index e4aae1135..f4ddfa406 100644 --- a/pkg/sentry/fs/inode.go +++ b/pkg/sentry/fs/inode.go @@ -86,12 +86,14 @@ type LockCtx struct { // NewInode takes a reference on msrc. func NewInode(ctx context.Context, iops InodeOperations, msrc *MountSource, sattr StableAttr) *Inode { msrc.IncRef() - return &Inode{ + i := Inode{ InodeOperations: iops, StableAttr: sattr, Watches: newWatches(), MountSource: msrc, } + i.EnableLeakCheck("fs.Inode") + return &i } // DecRef drops a reference on the Inode. diff --git a/pkg/sentry/fs/inode_overlay.go b/pkg/sentry/fs/inode_overlay.go index b247fa514..24b769cfc 100644 --- a/pkg/sentry/fs/inode_overlay.go +++ b/pkg/sentry/fs/inode_overlay.go @@ -567,6 +567,12 @@ func overlayCheck(ctx context.Context, o *overlayEntry, p PermMask) error { if o.upper != nil { err = o.upper.check(ctx, p) } else { + if p.Write { + // Since writes will be redirected to the upper filesystem, the lower + // filesystem need not be writable, but must be readable for copy-up. + p.Write = false + p.Read = true + } err = o.lower.check(ctx, p) } o.copyMu.RUnlock() diff --git a/pkg/sentry/fs/mount.go b/pkg/sentry/fs/mount.go index 912495528..7a9692800 100644 --- a/pkg/sentry/fs/mount.go +++ b/pkg/sentry/fs/mount.go @@ -138,12 +138,14 @@ func NewMountSource(ctx context.Context, mops MountSourceOperations, filesystem if filesystem != nil { fsType = filesystem.Name() } - return &MountSource{ + msrc := MountSource{ MountSourceOperations: mops, Flags: flags, FilesystemType: fsType, fscache: NewDirentCache(DefaultDirentCacheSize), } + msrc.EnableLeakCheck("fs.MountSource") + return &msrc } // DirentRefs returns the current mount direntRefs. diff --git a/pkg/sentry/fs/mounts.go b/pkg/sentry/fs/mounts.go index 281364dfc..693ffc760 100644 --- a/pkg/sentry/fs/mounts.go +++ b/pkg/sentry/fs/mounts.go @@ -181,12 +181,14 @@ func NewMountNamespace(ctx context.Context, root *Inode) (*MountNamespace, error d: newRootMount(1, d), } - return &MountNamespace{ + mns := MountNamespace{ userns: creds.UserNamespace, root: d, mounts: mnts, mountID: 2, - }, nil + } + mns.EnableLeakCheck("fs.MountNamespace") + return &mns, nil } // UserNamespace returns the user namespace associated with this mount manager. @@ -661,6 +663,11 @@ func (mns *MountNamespace) ResolveExecutablePath(ctx context.Context, wd, name s } defer d.DecRef() + // Check that it is a regular file. + if !IsRegular(d.Inode.StableAttr) { + continue + } + // Check whether we can read and execute the found file. if err := d.Inode.CheckPermission(ctx, PermMask{Read: true, Execute: true}); err != nil { log.Infof("Found executable at %q, but user cannot execute it: %v", binPath, err) diff --git a/pkg/sentry/fs/proc/fds.go b/pkg/sentry/fs/proc/fds.go index ea7aded9a..bee421d76 100644 --- a/pkg/sentry/fs/proc/fds.go +++ b/pkg/sentry/fs/proc/fds.go @@ -25,7 +25,6 @@ import ( "gvisor.dev/gvisor/pkg/sentry/fs/proc/device" "gvisor.dev/gvisor/pkg/sentry/fs/ramfs" "gvisor.dev/gvisor/pkg/sentry/kernel" - "gvisor.dev/gvisor/pkg/sentry/kernel/kdefs" "gvisor.dev/gvisor/pkg/syserror" ) @@ -42,8 +41,8 @@ func walkDescriptors(t *kernel.Task, p string, toInode func(*fs.File, kernel.FDF var file *fs.File var fdFlags kernel.FDFlags t.WithMuLocked(func(t *kernel.Task) { - if fdm := t.FDMap(); fdm != nil { - file, fdFlags = fdm.GetDescriptor(kdefs.FD(n)) + if fdTable := t.FDTable(); fdTable != nil { + file, fdFlags = fdTable.Get(int32(n)) } }) if file == nil { @@ -56,36 +55,31 @@ func walkDescriptors(t *kernel.Task, p string, toInode func(*fs.File, kernel.FDF // toDentAttr callback for each to get a DentAttr, which it then emits. This is // a helper for implementing fs.InodeOperations.Readdir. func readDescriptors(t *kernel.Task, c *fs.DirCtx, offset int64, toDentAttr func(int) fs.DentAttr) (int64, error) { - var fds kernel.FDs + var fds []int32 t.WithMuLocked(func(t *kernel.Task) { - if fdm := t.FDMap(); fdm != nil { - fds = fdm.GetFDs() + if fdTable := t.FDTable(); fdTable != nil { + fds = fdTable.GetFDs() } }) - fdInts := make([]int, 0, len(fds)) - for _, fd := range fds { - fdInts = append(fdInts, int(fd)) - } - - // Find the fd to start at. - idx := sort.SearchInts(fdInts, int(offset)) - if idx == len(fdInts) { + // Find the appropriate starting point. + idx := sort.Search(len(fds), func(i int) bool { return fds[i] >= int32(offset) }) + if idx == len(fds) { return offset, nil } - fdInts = fdInts[idx:] + fds = fds[idx:] - var fd int - for _, fd = range fdInts { + // Serialize all FDs. + for _, fd := range fds { name := strconv.FormatUint(uint64(fd), 10) - if err := c.DirEmit(name, toDentAttr(fd)); err != nil { + if err := c.DirEmit(name, toDentAttr(int(fd))); err != nil { // Returned offset is the next fd to serialize. return int64(fd), err } } // We serialized them all. Next offset should be higher than last // serialized fd. - return int64(fd + 1), nil + return int64(fds[len(fds)-1] + 1), nil } // fd implements fs.InodeOperations for a file in /proc/TID/fd/. @@ -154,9 +148,9 @@ func (f *fd) Close() error { type fdDir struct { ramfs.Dir - // We hold a reference on the task's fdmap but only keep an indirect - // task pointer to avoid Dirent loading circularity caused by fdmap's - // potential back pointers into the dirent tree. + // We hold a reference on the task's FDTable but only keep an indirect + // task pointer to avoid Dirent loading circularity caused by the + // table's back pointers into the dirent tree. t *kernel.Task } diff --git a/pkg/sentry/fs/proc/task.go b/pkg/sentry/fs/proc/task.go index b2e36aeee..ef0ca3301 100644 --- a/pkg/sentry/fs/proc/task.go +++ b/pkg/sentry/fs/proc/task.go @@ -580,8 +580,8 @@ func (s *statusData) ReadSeqFileData(ctx context.Context, h seqfile.SeqHandle) ( var fds int var vss, rss, data uint64 s.t.WithMuLocked(func(t *kernel.Task) { - if fdm := t.FDMap(); fdm != nil { - fds = fdm.Size() + if fdTable := t.FDTable(); fdTable != nil { + fds = fdTable.Size() } if mm := t.MemoryManager(); mm != nil { vss = mm.VirtualMemorySize() diff --git a/pkg/sentry/fs/tty/terminal.go b/pkg/sentry/fs/tty/terminal.go index 8290f2530..b7cecb2ed 100644 --- a/pkg/sentry/fs/tty/terminal.go +++ b/pkg/sentry/fs/tty/terminal.go @@ -38,9 +38,11 @@ type Terminal struct { func newTerminal(ctx context.Context, d *dirInodeOperations, n uint32) *Terminal { termios := linux.DefaultSlaveTermios - return &Terminal{ + t := Terminal{ d: d, n: n, ld: newLineDiscipline(termios), } + t.EnableLeakCheck("tty.Terminal") + return &t } |