memmap

package
v0.0.0-...-4bf4b70 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 24, 2021 License: Apache-2.0, MIT Imports: 7 Imported by: 0

Documentation

Overview

Package memmap defines semantics for memory mappings.

Index

Constants

View Source 
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.
	MappingminDegree = 3

	MappingmaxDegree = 2 * MappingminDegree
)
View Source 
const MappingtrackGaps = 0

trackGaps is an optional parameter.

If trackGaps is 1, the Set will track maximum gap size recursively, enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this case, Key must be an unsigned integer.

trackGaps must be 0 or 1.

Variables

This section is empty.

Functions

func CheckTranslateResult 

func CheckTranslateResult(required, optional MappableRange, at usermem.AccessType, ts []Translation, terr error) error

CheckTranslateResult returns an error if (ts, terr) does not satisfy all postconditions for Mappable.Translate(required, optional, at).

Preconditions: Same as Mappable.Translate.

func MappingzeroNodeSlice 

func MappingzeroNodeSlice(slice []*Mappingnode)

func MappingzeroValueSlice 

func MappingzeroValueSlice(slice []MappingsOfRange)

Types

type BusError 

type BusError struct {
	// Err is the original error.
	Err error
}

BusError may be returned by implementations of Mappable.Translate for errors that should result in SIGBUS delivery if they cause application page fault handling to fail.

func (*BusError) Error 

func (b *BusError) Error() string

Error implements error.Error.

type File 

type File interface {

	// IncRef increments the reference count on all pages in fr.
	//
	// Preconditions:
	// * fr.Start and fr.End must be page-aligned.
	// * fr.Length() > 0.
	// * At least one reference must be held on all pages in fr. (The File
	//   interface does not provide a way to acquire an initial reference;
	//   implementors may define mechanisms for doing so.)
	IncRef(fr FileRange)

	// DecRef decrements the reference count on all pages in fr.
	//
	// Preconditions:
	// * fr.Start and fr.End must be page-aligned.
	// * fr.Length() > 0.
	// * At least one reference must be held on all pages in fr.
	DecRef(fr FileRange)

	// MapInternal returns a mapping of the given file offsets in the invoking
	// process' address space for reading and writing.
	//
	// Note that fr.Start and fr.End need not be page-aligned.
	//
	// Preconditions:
	// * fr.Length() > 0.
	// * At least one reference must be held on all pages in fr.
	//
	// Postconditions: The returned mapping is valid as long as at least one
	// reference is held on the mapped pages.
	MapInternal(fr FileRange, at usermem.AccessType) (safemem.BlockSeq, error)

	// FD returns the file descriptor represented by the File.
	//
	// The only permitted operation on the returned file descriptor is to map
	// pages from it consistent with the requirements of AddressSpace.MapFile.
	FD() int
}

File represents a host file that may be mapped into an platform.AddressSpace.

type FileRange 

type FileRange struct {
	// Start is the inclusive start of the range.
	Start uint64

	// End is the exclusive end of the range.
	End uint64
}

A Range represents a contiguous range of T.

+stateify savable

func (FileRange) CanSplitAt 

func (r FileRange) CanSplitAt(x uint64) bool

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 (FileRange) Contains 

func (r FileRange) Contains(x uint64) bool

Contains returns true if r contains x.

func (FileRange) Intersect 

func (r FileRange) Intersect(r2 FileRange) FileRange

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 (FileRange) IsSupersetOf 

func (r FileRange) IsSupersetOf(r2 FileRange) bool

IsSupersetOf returns true if r is a superset of r2; that is, the range r2 is contained within r.

func (FileRange) Length 

func (r FileRange) Length() uint64

Length returns the length of the range.

func (FileRange) Overlaps 

func (r FileRange) Overlaps(r2 FileRange) bool

Overlaps returns true if r and r2 overlap.

func (*FileRange) StateFields 

func (fr *FileRange) StateFields() []string

func (*FileRange) StateLoad 

func (fr *FileRange) StateLoad(stateSourceObject state.Source)

func (*FileRange) StateSave 

func (fr *FileRange) StateSave(stateSinkObject state.Sink)

func (*FileRange) StateTypeName 

func (fr *FileRange) StateTypeName() string

func (FileRange) String 

func (fr FileRange) String() string

String implements fmt.Stringer.String.

func (FileRange) WellFormed 

func (r FileRange) WellFormed() bool

WellFormed returns true if r.Start <= r.End. All other methods on a Range require that the Range is well-formed.

type InvalidateOpts 

type InvalidateOpts struct {
	// InvalidatePrivate is true if private pages in the invalidated region
	// should also be discarded, causing their data to be lost.
	InvalidatePrivate bool
}

InvalidateOpts holds options to MappingSpace.Invalidate.

type MLockMode 

type MLockMode int

MLockMode specifies the memory locking behavior of a memory mapping. 

const (
	// MLockNone specifies that a mapping has no memory locking behavior.
	//
	// This must be the zero value for MLockMode.
	MLockNone MLockMode = iota

	// MLockEager specifies that a mapping is memory-locked, as by mlock() or
	// similar. Pages in the mapping should be made, and kept, resident in
	// physical memory as soon as possible.
	//
	// As of this writing, MLockEager does not cause memory-locking to be
	// requested from the host; it only affects the sentry's memory management
	// behavior.
	//
	// MLockEager is analogous to Linux's VM_LOCKED.
	MLockEager

	// MLockLazy specifies that a mapping is memory-locked, as by mlock() or
	// similar. Pages in the mapping should be kept resident in physical memory
	// once they have been made resident due to e.g. a page fault.
	//
	// As of this writing, MLockLazy does not cause memory-locking to be
	// requested from the host; in fact, it has virtually no effect, except for
	// interactions between mlocked pages and other syscalls.
	//
	// MLockLazy is analogous to Linux's VM_LOCKED | VM_LOCKONFAULT.
	MLockLazy
)

Note that the ordering of MLockModes is significant; see mm.MemoryManager.defMLockMode.

type MMapOpts 

type MMapOpts struct {
	// Length is the length of the mapping.
	Length uint64

	// MappingIdentity controls the lifetime of Mappable, and provides
	// properties of the mapping shown in /proc/[pid]/maps. If MMapOpts is used
	// to successfully create a memory mapping, a reference is taken on
	// MappingIdentity.
	MappingIdentity MappingIdentity

	// Mappable is the Mappable to be mapped. If Mappable is nil, the mapping
	// is anonymous. If Mappable is not nil, it must remain valid as long as a
	// reference is held on MappingIdentity.
	Mappable Mappable

	// Offset is the offset into Mappable to map. If Mappable is nil, Offset is
	// ignored.
	Offset uint64

	// Addr is the suggested address for the mapping.
	Addr usermem.Addr

	// Fixed specifies whether this is a fixed mapping (it must be located at
	// Addr).
	Fixed bool

	// Unmap specifies whether existing mappings in the range being mapped may
	// be replaced. If Unmap is true, Fixed must be true.
	Unmap bool

	// If Map32Bit is true, all addresses in the created mapping must fit in a
	// 32-bit integer. (Note that the "end address" of the mapping, i.e. the
	// address of the first byte *after* the mapping, need not fit in a 32-bit
	// integer.) Map32Bit is ignored if Fixed is true.
	Map32Bit bool

	// Perms is the set of permissions to the applied to this mapping.
	Perms usermem.AccessType

	// MaxPerms limits the set of permissions that may ever apply to this
	// mapping. If Mappable is not nil, all memmap.Translations returned by
	// Mappable.Translate must support all accesses in MaxPerms.
	//
	// Preconditions: MaxAccessType should be an effective AccessType, as
	// access cannot be limited beyond effective AccessTypes.
	MaxPerms usermem.AccessType

	// Private is true if writes to the mapping should be propagated to a copy
	// that is exclusive to the MemoryManager.
	Private bool

	// GrowsDown is true if the mapping should be automatically expanded
	// downward on guard page faults.
	GrowsDown bool

	// Precommit is true if the platform should eagerly commit resources to the
	// mapping (see platform.AddressSpace.MapFile).
	Precommit bool

	// MLockMode specifies the memory locking behavior of the mapping.
	MLockMode MLockMode

	// Hint is the name used for the mapping in /proc/[pid]/maps. If Hint is
	// empty, MappingIdentity.MappedName() will be used instead.
	//
	// TODO(jamieliu): Replace entirely with MappingIdentity?
	Hint string

	// Force means to skip validation checks of Addr and Length. It can be
	// used to create special mappings below mm.layout.MinAddr and
	// mm.layout.MaxAddr. It has to be used with caution.
	//
	// If Force is true, Unmap and Fixed must be true.
	Force bool
}

MMapOpts specifies a request to create a memory mapping.

type Mappable 

type Mappable interface {
	// AddMapping notifies the Mappable of a mapping from addresses ar in ms to
	// offsets [offset, offset+ar.Length()) in this Mappable.
	//
	// The writable flag indicates whether the backing data for a Mappable can
	// be modified through the mapping. Effectively, this means a shared mapping
	// where Translate may be called with at.Write == true. This is a property
	// established at mapping creation and must remain constant throughout the
	// lifetime of the mapping.
	//
	// Preconditions: offset+ar.Length() does not overflow.
	AddMapping(ctx context.Context, ms MappingSpace, ar usermem.AddrRange, offset uint64, writable bool) error

	// RemoveMapping notifies the Mappable of the removal of a mapping from
	// addresses ar in ms to offsets [offset, offset+ar.Length()) in this
	// Mappable.
	//
	// Preconditions:
	// * offset+ar.Length() does not overflow.
	// * The removed mapping must exist. writable must match the
	//   corresponding call to AddMapping.
	RemoveMapping(ctx context.Context, ms MappingSpace, ar usermem.AddrRange, offset uint64, writable bool)

	// CopyMapping notifies the Mappable of an attempt to copy a mapping in ms
	// from srcAR to dstAR. For most Mappables, this is equivalent to
	// AddMapping. Note that it is possible that srcAR.Length() != dstAR.Length(),
	// and also that srcAR.Length() == 0.
	//
	// CopyMapping is only called when a mapping is copied within a given
	// MappingSpace; it is analogous to Linux's vm_operations_struct::mremap.
	//
	// Preconditions:
	// * offset+srcAR.Length() and offset+dstAR.Length() do not overflow.
	// * The mapping at srcAR must exist. writable must match the
	//   corresponding call to AddMapping.
	CopyMapping(ctx context.Context, ms MappingSpace, srcAR, dstAR usermem.AddrRange, offset uint64, writable bool) error

	// Translate returns the Mappable's current mappings for at least the range
	// of offsets specified by required, and at most the range of offsets
	// specified by optional. at is the set of access types that may be
	// performed using the returned Translations. If not all required offsets
	// are translated, it returns a non-nil error explaining why.
	//
	// Translations are valid until invalidated by a callback to
	// MappingSpace.Invalidate or until the caller removes its mapping of the
	// translated range. Mappable implementations must ensure that at least one
	// reference is held on all pages in a File that may be the result
	// of a valid Translation.
	//
	// Preconditions:
	// * required.Length() > 0.
	// * optional.IsSupersetOf(required).
	// * required and optional must be page-aligned.
	// * The caller must have established a mapping for all of the queried
	//   offsets via a previous call to AddMapping.
	// * The caller is responsible for ensuring that calls to Translate
	//   synchronize with invalidation.
	//
	// Postconditions: See CheckTranslateResult.
	Translate(ctx context.Context, required, optional MappableRange, at usermem.AccessType) ([]Translation, error)

	// InvalidateUnsavable requests that the Mappable invalidate Translations
	// that cannot be preserved across save/restore.
	//
	// Invariant: InvalidateUnsavable never races with concurrent calls to any
	// other Mappable methods.
	InvalidateUnsavable(ctx context.Context) error
}

Mappable represents a memory-mappable object, a mutable mapping from uint64 offsets to (File, uint64 File offset) pairs.

See mm/mm.go for Mappable's place in the lock order.

All Mappable methods have the following preconditions: * usermem.AddrRanges and MappableRanges must be non-empty (Length() != 0). * usermem.Addrs and Mappable offsets must be page-aligned.

type MappableRange 

type MappableRange struct {
	// Start is the inclusive start of the range.
	Start uint64

	// End is the exclusive end of the range.
	End uint64
}

A Range represents a contiguous range of T.

+stateify savable

func (MappableRange) CanSplitAt 

func (r MappableRange) CanSplitAt(x uint64) bool

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 (MappableRange) Contains 

func (r MappableRange) Contains(x uint64) bool

Contains returns true if r contains x.

func (MappableRange) Intersect 

func (r MappableRange) Intersect(r2 MappableRange) MappableRange

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 (MappableRange) IsSupersetOf 

func (r MappableRange) IsSupersetOf(r2 MappableRange) bool

IsSupersetOf returns true if r is a superset of r2; that is, the range r2 is contained within r.

func (MappableRange) Length 

func (r MappableRange) Length() uint64

Length returns the length of the range.

func (MappableRange) Overlaps 

func (r MappableRange) Overlaps(r2 MappableRange) bool

Overlaps returns true if r and r2 overlap.

func (*MappableRange) StateFields 

func (mr *MappableRange) StateFields() []string

func (*MappableRange) StateLoad 

func (mr *MappableRange) StateLoad(stateSourceObject state.Source)

func (*MappableRange) StateSave 

func (mr *MappableRange) StateSave(stateSinkObject state.Sink)

func (*MappableRange) StateTypeName 

func (mr *MappableRange) StateTypeName() string

func (MappableRange) String 

func (mr MappableRange) String() string

String implements fmt.Stringer.String.

func (MappableRange) WellFormed 

func (r MappableRange) WellFormed() bool

WellFormed returns true if r.Start <= r.End. All other methods on a Range require that the Range is well-formed.

type MappingGapIterator 

type MappingGapIterator struct {
	// contains filtered or unexported fields
}

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.

func (MappingGapIterator) End 

func (gap MappingGapIterator) End() uint64

End is equivalent to Range().End, but should be preferred if only the end of the range is needed.

func (MappingGapIterator) IsEmpty 

func (gap MappingGapIterator) IsEmpty() bool

IsEmpty returns true if the iterated gap is empty (that is, the "gap" is between two adjacent segments.)

func (MappingGapIterator) NextGap 

func (gap MappingGapIterator) NextGap() MappingGapIterator

NextGap returns the iterated gap's successor. If no such gap exists, NextGap returns a terminal iterator.

func (MappingGapIterator) NextLargeEnoughGap 

func (gap MappingGapIterator) NextLargeEnoughGap(minSize uint64) MappingGapIterator

NextLargeEnoughGap returns the iterated gap's first next gap with larger length than minSize. If not found, return a terminal gap iterator (does NOT include this gap itself).

Precondition: trackGaps must be 1.

func (MappingGapIterator) NextSegment 

func (gap MappingGapIterator) NextSegment() MappingIterator

NextSegment returns the segment immediately after the iterated gap. If no such segment exists, NextSegment returns a terminal iterator.

func (MappingGapIterator) Ok 

func (gap MappingGapIterator) Ok() bool

Ok returns true if the iterator is not terminal. All other methods are only valid for non-terminal iterators.

func (MappingGapIterator) PrevGap 

func (gap MappingGapIterator) PrevGap() MappingGapIterator

PrevGap returns the iterated gap's predecessor. If no such gap exists, PrevGap returns a terminal iterator.

func (MappingGapIterator) PrevLargeEnoughGap 

func (gap MappingGapIterator) PrevLargeEnoughGap(minSize uint64) MappingGapIterator

PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or equal length than minSize. If not found, return a terminal gap iterator (does NOT include this gap itself).

Precondition: trackGaps must be 1.

func (MappingGapIterator) PrevSegment 

func (gap MappingGapIterator) PrevSegment() MappingIterator

PrevSegment returns the segment immediately before the iterated gap. If no such segment exists, PrevSegment returns a terminal iterator.

func (MappingGapIterator) Range 

func (gap MappingGapIterator) Range() MappableRange

Range returns the range spanned by the iterated gap.

func (MappingGapIterator) Start 

func (gap MappingGapIterator) Start() uint64

Start is equivalent to Range().Start, but should be preferred if only the start of the range is needed.

type MappingIdentity 

type MappingIdentity interface {
	// IncRef increments the MappingIdentity's reference count.
	IncRef()

	// DecRef decrements the MappingIdentity's reference count.
	DecRef(ctx context.Context)

	// MappedName returns the application-visible name shown in
	// /proc/[pid]/maps.
	MappedName(ctx context.Context) string

	// DeviceID returns the device number shown in /proc/[pid]/maps.
	DeviceID() uint64

	// InodeID returns the inode number shown in /proc/[pid]/maps.
	InodeID() uint64

	// Msync has the same semantics as fs.FileOperations.Fsync(ctx,
	// int64(mr.Start), int64(mr.End-1), fs.SyncData).
	// (fs.FileOperations.Fsync() takes an inclusive end, but mr.End is
	// exclusive, hence mr.End-1.) It is defined rather than Fsync so that
	// implementors don't need to depend on the fs package for fs.SyncType.
	Msync(ctx context.Context, mr MappableRange) error
}

MappingIdentity controls the lifetime of a Mappable, and provides information about the Mappable for /proc/[pid]/maps. It is distinct from Mappable because all Mappables that are coherent must compare equal to support the implementation of shared futexes, but different MappingIdentities may represent the same Mappable, in the same way that multiple fs.Files may represent the same fs.Inode. (This similarity is not coincidental; fs.File implements MappingIdentity, and some fs.InodeOperations implement Mappable.)

type MappingIterator 

type MappingIterator struct {
	// contains filtered or unexported fields
}

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.

func MappingsegmentAfterPosition 

func MappingsegmentAfterPosition(n *Mappingnode, i int) MappingIterator

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 MappingsegmentBeforePosition 

func MappingsegmentBeforePosition(n *Mappingnode, i int) MappingIterator

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 (MappingIterator) End 

func (seg MappingIterator) End() uint64

End is equivalent to Range().End, but should be preferred if only the end of the range is needed.

func (MappingIterator) NextGap 

func (seg MappingIterator) NextGap() MappingGapIterator

NextGap returns the gap immediately after the iterated segment.

func (MappingIterator) NextNonEmpty 

func (seg MappingIterator) NextNonEmpty() (MappingIterator, MappingGapIterator)

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 (MappingIterator) NextSegment 

func (seg MappingIterator) NextSegment() MappingIterator

NextSegment returns the iterated segment's successor. If there is no succeeding segment, NextSegment returns a terminal iterator.

func (MappingIterator) Ok 

func (seg MappingIterator) Ok() bool

Ok returns true if the iterator is not terminal. All other methods are only valid for non-terminal iterators.

func (MappingIterator) PrevGap 

func (seg MappingIterator) PrevGap() MappingGapIterator

PrevGap returns the gap immediately before the iterated segment.

func (MappingIterator) PrevNonEmpty 

func (seg MappingIterator) PrevNonEmpty() (MappingIterator, MappingGapIterator)

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 (MappingIterator) PrevSegment 

func (seg MappingIterator) PrevSegment() MappingIterator

PrevSegment returns the iterated segment's predecessor. If there is no preceding segment, PrevSegment returns a terminal iterator.

func (MappingIterator) Range 

func (seg MappingIterator) Range() MappableRange

Range returns the iterated segment's range key.

func (MappingIterator) SetEnd 

func (seg MappingIterator) SetEnd(end uint64)

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 (MappingIterator) SetEndUnchecked 

func (seg MappingIterator) SetEndUnchecked(end uint64)

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 (MappingIterator) SetRange 

func (seg MappingIterator) SetRange(r MappableRange)

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 (MappingIterator) SetRangeUnchecked 

func (seg MappingIterator) SetRangeUnchecked(r MappableRange)

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 (MappingIterator) SetStart 

func (seg MappingIterator) SetStart(start uint64)

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 (MappingIterator) SetStartUnchecked 

func (seg MappingIterator) SetStartUnchecked(start uint64)

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 (MappingIterator) SetValue 

func (seg MappingIterator) SetValue(val MappingsOfRange)

SetValue mutates the iterated segment's value. This operation does not invalidate any iterators.

func (MappingIterator) Start 

func (seg MappingIterator) Start() uint64

Start is equivalent to Range().Start, but should be preferred if only the start of the range is needed.

func (MappingIterator) Value 

func (seg MappingIterator) Value() MappingsOfRange

Value returns a copy of the iterated segment's value.

func (MappingIterator) ValuePtr 

func (seg MappingIterator) ValuePtr() *MappingsOfRange

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.

type MappingOfRange 

type MappingOfRange struct {
	MappingSpace MappingSpace
	AddrRange    usermem.AddrRange
	Writable     bool
}

MappingOfRange represents a mapping of a MappableRange.

+stateify savable

func (*MappingOfRange) StateFields 

func (r *MappingOfRange) StateFields() []string

func (*MappingOfRange) StateLoad 

func (r *MappingOfRange) StateLoad(stateSourceObject state.Source)

func (*MappingOfRange) StateSave 

func (r *MappingOfRange) StateSave(stateSinkObject state.Sink)

func (*MappingOfRange) StateTypeName 

func (r *MappingOfRange) StateTypeName() string

func (MappingOfRange) String 

func (r MappingOfRange) String() string

String implements fmt.Stringer.String.

type MappingSegmentDataSlices 

type MappingSegmentDataSlices struct {
	Start  []uint64
	End    []uint64
	Values []MappingsOfRange
}

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

func (*MappingSegmentDataSlices) StateFields 

func (m *MappingSegmentDataSlices) StateFields() []string

func (*MappingSegmentDataSlices) StateLoad 

func (m *MappingSegmentDataSlices) StateLoad(stateSourceObject state.Source)

func (*MappingSegmentDataSlices) StateSave 

func (m *MappingSegmentDataSlices) StateSave(stateSinkObject state.Sink)

func (*MappingSegmentDataSlices) StateTypeName 

func (m *MappingSegmentDataSlices) StateTypeName() string

type MappingSet 

type MappingSet struct {
	// contains filtered or unexported fields
}

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

func (*MappingSet) Add 

func (s *MappingSet) Add(r MappableRange, val MappingsOfRange) bool

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 (*MappingSet) AddMapping 

func (s *MappingSet) AddMapping(ms MappingSpace, ar usermem.AddrRange, offset uint64, writable bool) []MappableRange

AddMapping adds the given mapping and returns the set of MappableRanges that previously had no mappings.

Preconditions: Same as Mappable.AddMapping.

func (*MappingSet) AddWithoutMerging 

func (s *MappingSet) AddWithoutMerging(r MappableRange, val MappingsOfRange) bool

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 (*MappingSet) ApplyContiguous 

func (s *MappingSet) ApplyContiguous(r MappableRange, fn func(seg MappingIterator)) MappingGapIterator

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 (*MappingSet) ExportSortedSlices 

func (s *MappingSet) ExportSortedSlices() *MappingSegmentDataSlices

ExportSortedSlices returns a copy of all segments in the given set, in ascending key order.

func (*MappingSet) Find 

func (s *MappingSet) Find(key uint64) (MappingIterator, MappingGapIterator)

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 (*MappingSet) FindGap 

func (s *MappingSet) FindGap(key uint64) MappingGapIterator

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 (*MappingSet) FindSegment 

func (s *MappingSet) FindSegment(key uint64) MappingIterator

FindSegment returns the segment whose range contains the given key. If no such segment exists, FindSegment returns a terminal iterator.

func (*MappingSet) FirstGap 

func (s *MappingSet) FirstGap() MappingGapIterator

FirstGap returns the first gap in the set.

func (*MappingSet) FirstSegment 

func (s *MappingSet) FirstSegment() MappingIterator

FirstSegment returns the first segment in the set. If the set is empty, FirstSegment returns a terminal iterator.

func (*MappingSet) ImportSortedSlices 

func (s *MappingSet) ImportSortedSlices(sds *MappingSegmentDataSlices) error

ImportSortedSlices 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 (*MappingSet) Insert 

func (s *MappingSet) Insert(gap MappingGapIterator, r MappableRange, val MappingsOfRange) MappingIterator

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 (*MappingSet) InsertWithoutMerging 

func (s *MappingSet) InsertWithoutMerging(gap MappingGapIterator, r MappableRange, val MappingsOfRange) MappingIterator

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 (*MappingSet) InsertWithoutMergingUnchecked 

func (s *MappingSet) InsertWithoutMergingUnchecked(gap MappingGapIterator, r MappableRange, val MappingsOfRange) MappingIterator

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 (*MappingSet) Invalidate 

func (s *MappingSet) Invalidate(mr MappableRange, opts InvalidateOpts)

Invalidate calls MappingSpace.Invalidate for all mappings of offsets in mr.

func (*MappingSet) InvalidateAll 

func (s *MappingSet) InvalidateAll(opts InvalidateOpts)

InvalidateAll calls MappingSpace.Invalidate for all mappings of s.

func (*MappingSet) IsEmpty 

func (s *MappingSet) IsEmpty() bool

IsEmpty returns true if the set contains no segments.

func (*MappingSet) IsEmptyRange 

func (s *MappingSet) IsEmptyRange(r MappableRange) bool

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 (*MappingSet) Isolate 

func (s *MappingSet) Isolate(seg MappingIterator, r MappableRange) MappingIterator

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 (*MappingSet) LastGap 

func (s *MappingSet) LastGap() MappingGapIterator

LastGap returns the last gap in the set.

func (*MappingSet) LastSegment 

func (s *MappingSet) LastSegment() MappingIterator

LastSegment returns the last segment in the set. If the set is empty, LastSegment returns a terminal iterator.

func (*MappingSet) LowerBoundGap 

func (s *MappingSet) LowerBoundGap(min uint64) MappingGapIterator

LowerBoundGap returns the gap with the lowest range that is greater than or equal to min.

func (*MappingSet) LowerBoundSegment 

func (s *MappingSet) LowerBoundSegment(min uint64) MappingIterator

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 (*MappingSet) Merge 

func (s *MappingSet) Merge(first, second MappingIterator) MappingIterator

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 (*MappingSet) MergeAdjacent 

func (s *MappingSet) MergeAdjacent(r MappableRange)

MergeAdjacent attempts to merge the segment containing r.Start with its predecessor, and the segment containing r.End-1 with its successor.

func (*MappingSet) MergeAll 

func (s *MappingSet) MergeAll()

MergeAll attempts to merge all adjacent segments in the set. All existing iterators are invalidated.

func (*MappingSet) MergeRange 

func (s *MappingSet) MergeRange(r MappableRange)

MergeRange attempts to merge all adjacent segments that contain a key in the specific range. All existing iterators are invalidated.

func (*MappingSet) MergeUnchecked 

func (s *MappingSet) MergeUnchecked(first, second MappingIterator) MappingIterator

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 (*MappingSet) Remove 

func (s *MappingSet) Remove(seg MappingIterator) MappingGapIterator

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 (*MappingSet) RemoveAll 

func (s *MappingSet) RemoveAll()

RemoveAll removes all segments from the set. All existing iterators are invalidated.

func (*MappingSet) RemoveMapping 

func (s *MappingSet) RemoveMapping(ms MappingSpace, ar usermem.AddrRange, offset uint64, writable bool) []MappableRange

RemoveMapping removes the given mapping and returns the set of MappableRanges that now have no mappings.

Preconditions: Same as Mappable.RemoveMapping.

func (*MappingSet) RemoveRange 

func (s *MappingSet) RemoveRange(r MappableRange) MappingGapIterator

RemoveRange removes all segments in the given range. An iterator to the newly formed gap is returned, and all existing iterators are invalidated.

func (*MappingSet) Span 

func (s *MappingSet) Span() uint64

Span returns the total size of all segments in the set.

func (*MappingSet) SpanRange 

func (s *MappingSet) SpanRange(r MappableRange) uint64

SpanRange returns the total size of the intersection of segments in the set with the given range.

func (*MappingSet) Split 

func (s *MappingSet) Split(seg MappingIterator, split uint64) (MappingIterator, MappingIterator)

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 (*MappingSet) SplitAt 

func (s *MappingSet) SplitAt(split uint64) bool

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 (*MappingSet) SplitUnchecked 

func (s *MappingSet) SplitUnchecked(seg MappingIterator, split uint64) (MappingIterator, MappingIterator)

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 (*MappingSet) StateFields 

func (s *MappingSet) StateFields() []string

func (*MappingSet) StateLoad 

func (s *MappingSet) StateLoad(stateSourceObject state.Source)

func (*MappingSet) StateSave 

func (s *MappingSet) StateSave(stateSinkObject state.Sink)

func (*MappingSet) StateTypeName 

func (s *MappingSet) StateTypeName() string

func (*MappingSet) String 

func (s *MappingSet) String() string

String stringifies a Set for debugging.

func (*MappingSet) UpperBoundGap 

func (s *MappingSet) UpperBoundGap(max uint64) MappingGapIterator

UpperBoundGap returns the gap with the highest range that is less than or equal to max.

func (*MappingSet) UpperBoundSegment 

func (s *MappingSet) UpperBoundSegment(max uint64) MappingIterator

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.

type MappingSpace 

type MappingSpace interface {
	// Invalidate is called to notify the MappingSpace that values returned by
	// previous calls to Mappable.Translate for offsets mapped by addresses in
	// ar are no longer valid.
	//
	// Invalidate must not take any locks preceding mm.MemoryManager.activeMu
	// in the lock order.
	//
	// Preconditions:
	// * ar.Length() != 0.
	// * ar must be page-aligned.
	Invalidate(ar usermem.AddrRange, opts InvalidateOpts)
}

MappingSpace represents a mutable mapping from usermem.Addrs to (Mappable, uint64 offset) pairs.

type MappingdynamicGap 

type MappingdynamicGap [MappingtrackGaps]uint64

dynamicGap is a type that disappears if trackGaps is 0.

func (*MappingdynamicGap) Get 

func (d *MappingdynamicGap) Get() uint64

Get returns the value of the gap.

Precondition: trackGaps must be non-zero.

func (*MappingdynamicGap) Set 

func (d *MappingdynamicGap) Set(v uint64)

Set sets the value of the gap.

Precondition: trackGaps must be non-zero.

type Mappingnode 

type Mappingnode struct {
	// contains filtered or unexported fields
}

+stateify savable

func (*Mappingnode) StateFields 

func (n *Mappingnode) StateFields() []string

func (*Mappingnode) StateLoad 

func (n *Mappingnode) StateLoad(stateSourceObject state.Source)

func (*Mappingnode) StateSave 

func (n *Mappingnode) StateSave(stateSinkObject state.Sink)

func (*Mappingnode) StateTypeName 

func (n *Mappingnode) StateTypeName() string

func (*Mappingnode) String 

func (n *Mappingnode) String() string

String stringifies a node (and all of its children) for debugging.

type MappingsOfRange 

type MappingsOfRange map[MappingOfRange]struct{}

MappingsOfRange is the value type of MappingSet, and represents the set of all mappings of the corresponding MappableRange.

Using a map offers O(1) lookups in RemoveMapping and mappingSetFunctions.Merge.

type Translation 

type Translation struct {
	// Source is the translated range in the Mappable.
	Source MappableRange

	// File is the mapped file.
	File File

	// Offset is the offset into File at which this Translation begins.
	Offset uint64

	// Perms is the set of permissions for which platform.AddressSpace.MapFile
	// and platform.AddressSpace.MapInternal on this Translation is permitted.
	Perms usermem.AccessType
}

Translations are returned by Mappable.Translate.

func (Translation) FileRange 

func (t Translation) FileRange() FileRange

FileRange returns the FileRange represented by t.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.