Merge 216da0b7 (automated)

5 files changed, 2039 insertions, 0 deletions

diff --git a/pkg/sentry/memmap/mappable_range.go b/pkg/sentry/memmap/mappable_range.go
new file mode 100755
index 000000000..6b6c2c685
--- /dev/null
+++ b/pkg/sentry/memmap/mappable_range.go
@@ -0,0 +1,62 @@
+package memmap
+
+// A Range represents a contiguous range of T.
+//
+// +stateify savable
+type MappableRange 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 MappableRange) WellFormed() bool {
+	return r.Start <= r.End
+}
+
+// Length returns the length of the range.
+func (r MappableRange) Length() uint64 {
+	return r.End - r.Start
+}
+
+// Contains returns true if r contains x.
+func (r MappableRange) Contains(x uint64) bool {
+	return r.Start <= x && x < r.End
+}
+
+// Overlaps returns true if r and r2 overlap.
+func (r MappableRange) Overlaps(r2 MappableRange) 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 MappableRange) IsSupersetOf(r2 MappableRange) 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 MappableRange) Intersect(r2 MappableRange) MappableRange {
+	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 MappableRange) CanSplitAt(x uint64) bool {
+	return r.Contains(x) && r.Start < x
+}
diff --git a/pkg/sentry/memmap/mapping_set.go b/pkg/sentry/memmap/mapping_set.go
new file mode 100644
index 000000000..3cf2b338f
--- /dev/null
+++ b/pkg/sentry/memmap/mapping_set.go
@@ -0,0 +1,253 @@
+// 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 memmap
+
+import (
+	"fmt"
+	"math"
+
+	"gvisor.googlesource.com/gvisor/pkg/sentry/usermem"
+)
+
+// MappingSet maps offsets into a Mappable to mappings of those offsets. It is
+// used to implement Mappable.AddMapping and RemoveMapping for Mappables that
+// may need to call MappingSpace.Invalidate.
+//
+// type MappingSet <generated by go_generics>
+
+// 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 MappingsOfRange map[MappingOfRange]struct{}
+
+// MappingOfRange represents a mapping of a MappableRange.
+//
+// +stateify savable
+type MappingOfRange struct {
+	MappingSpace MappingSpace
+	AddrRange    usermem.AddrRange
+	Writable     bool
+}
+
+func (r MappingOfRange) invalidate(opts InvalidateOpts) {
+	r.MappingSpace.Invalidate(r.AddrRange, opts)
+}
+
+// String implements fmt.Stringer.String.
+func (r MappingOfRange) String() string {
+	return fmt.Sprintf("%#v", r.AddrRange)
+}
+
+// mappingSetFunctions implements segment.Functions for MappingSet.
+type mappingSetFunctions struct{}
+
+// MinKey implements segment.Functions.MinKey.
+func (mappingSetFunctions) MinKey() uint64 {
+	return 0
+}
+
+// MaxKey implements segment.Functions.MaxKey.
+func (mappingSetFunctions) MaxKey() uint64 {
+	return math.MaxUint64
+}
+
+// ClearValue implements segment.Functions.ClearValue.
+func (mappingSetFunctions) ClearValue(v *MappingsOfRange) {
+	*v = MappingsOfRange{}
+}
+
+// Merge implements segment.Functions.Merge.
+//
+// Since each value is a map of MappingOfRanges, values can only be merged if
+// all MappingOfRanges in each map have an exact pair in the other map, forming
+// one contiguous region.
+func (mappingSetFunctions) Merge(r1 MappableRange, val1 MappingsOfRange, r2 MappableRange, val2 MappingsOfRange) (MappingsOfRange, bool) {
+	if len(val1) != len(val2) {
+		return nil, false
+	}
+
+	merged := make(MappingsOfRange, len(val1))
+
+	// Each MappingOfRange in val1 must have a matching region in val2, forming
+	// one contiguous region.
+	for k1 := range val1 {
+		// We expect val2 to to contain a key that forms a contiguous
+		// region with k1.
+		k2 := MappingOfRange{
+			MappingSpace: k1.MappingSpace,
+			AddrRange: usermem.AddrRange{
+				Start: k1.AddrRange.End,
+				End:   k1.AddrRange.End + usermem.Addr(r2.Length()),
+			},
+			Writable: k1.Writable,
+		}
+		if _, ok := val2[k2]; !ok {
+			return nil, false
+		}
+
+		// OK. Add it to the merged map.
+		merged[MappingOfRange{
+			MappingSpace: k1.MappingSpace,
+			AddrRange: usermem.AddrRange{
+				Start: k1.AddrRange.Start,
+				End:   k2.AddrRange.End,
+			},
+			Writable: k1.Writable,
+		}] = struct{}{}
+	}
+
+	return merged, true
+}
+
+// Split implements segment.Functions.Split.
+func (mappingSetFunctions) Split(r MappableRange, val MappingsOfRange, split uint64) (MappingsOfRange, MappingsOfRange) {
+	if split <= r.Start || split >= r.End {
+		panic(fmt.Sprintf("split is not within range %v", r))
+	}
+
+	m1 := make(MappingsOfRange, len(val))
+	m2 := make(MappingsOfRange, len(val))
+
+	// split is a value in MappableRange, we need the offset into the
+	// corresponding MappingsOfRange.
+	offset := usermem.Addr(split - r.Start)
+	for k := range val {
+		k1 := MappingOfRange{
+			MappingSpace: k.MappingSpace,
+			AddrRange: usermem.AddrRange{
+				Start: k.AddrRange.Start,
+				End:   k.AddrRange.Start + offset,
+			},
+			Writable: k.Writable,
+		}
+		m1[k1] = struct{}{}
+
+		k2 := MappingOfRange{
+			MappingSpace: k.MappingSpace,
+			AddrRange: usermem.AddrRange{
+				Start: k.AddrRange.Start + offset,
+				End:   k.AddrRange.End,
+			},
+			Writable: k.Writable,
+		}
+		m2[k2] = struct{}{}
+	}
+
+	return m1, m2
+}
+
+// subsetMapping returns the MappingOfRange that maps subsetRange, given that
+// ms maps wholeRange beginning at addr.
+//
+// For instance, suppose wholeRange = [0x0, 0x2000) and addr = 0x4000,
+// indicating that ms maps addresses [0x4000, 0x6000) to MappableRange [0x0,
+// 0x2000). Then for subsetRange = [0x1000, 0x2000), subsetMapping returns a
+// MappingOfRange for which AddrRange = [0x5000, 0x6000).
+func subsetMapping(wholeRange, subsetRange MappableRange, ms MappingSpace, addr usermem.Addr, writable bool) MappingOfRange {
+	if !wholeRange.IsSupersetOf(subsetRange) {
+		panic(fmt.Sprintf("%v is not a superset of %v", wholeRange, subsetRange))
+	}
+
+	offset := subsetRange.Start - wholeRange.Start
+	start := addr + usermem.Addr(offset)
+	return MappingOfRange{
+		MappingSpace: ms,
+		AddrRange: usermem.AddrRange{
+			Start: start,
+			End:   start + usermem.Addr(subsetRange.Length()),
+		},
+		Writable: writable,
+	}
+}
+
+// AddMapping adds the given mapping and returns the set of MappableRanges that
+// previously had no mappings.
+//
+// Preconditions: As for Mappable.AddMapping.
+func (s *MappingSet) AddMapping(ms MappingSpace, ar usermem.AddrRange, offset uint64, writable bool) []MappableRange {
+	mr := MappableRange{offset, offset + uint64(ar.Length())}
+	var mapped []MappableRange
+	seg, gap := s.Find(mr.Start)
+	for {
+		switch {
+		case seg.Ok() && seg.Start() < mr.End:
+			seg = s.Isolate(seg, mr)
+			seg.Value()[subsetMapping(mr, seg.Range(), ms, ar.Start, writable)] = struct{}{}
+			seg, gap = seg.NextNonEmpty()
+
+		case gap.Ok() && gap.Start() < mr.End:
+			gapMR := gap.Range().Intersect(mr)
+			mapped = append(mapped, gapMR)
+			// Insert a set and continue from the above case.
+			seg, gap = s.Insert(gap, gapMR, make(MappingsOfRange)), MappingGapIterator{}
+
+		default:
+			return mapped
+		}
+	}
+}
+
+// RemoveMapping removes the given mapping and returns the set of
+// MappableRanges that now have no mappings.
+//
+// Preconditions: As for Mappable.RemoveMapping.
+func (s *MappingSet) RemoveMapping(ms MappingSpace, ar usermem.AddrRange, offset uint64, writable bool) []MappableRange {
+	mr := MappableRange{offset, offset + uint64(ar.Length())}
+	var unmapped []MappableRange
+
+	seg := s.FindSegment(mr.Start)
+	if !seg.Ok() {
+		panic(fmt.Sprintf("MappingSet.RemoveMapping(%v): no segment containing %#x: %v", mr, mr.Start, s))
+	}
+	for seg.Ok() && seg.Start() < mr.End {
+		// Ensure this segment is limited to our range.
+		seg = s.Isolate(seg, mr)
+
+		// Remove this part of the mapping.
+		mappings := seg.Value()
+		delete(mappings, subsetMapping(mr, seg.Range(), ms, ar.Start, writable))
+
+		if len(mappings) == 0 {
+			unmapped = append(unmapped, seg.Range())
+			seg = s.Remove(seg).NextSegment()
+		} else {
+			seg = seg.NextSegment()
+		}
+	}
+	s.MergeAdjacent(mr)
+	return unmapped
+}
+
+// Invalidate calls MappingSpace.Invalidate for all mappings of offsets in mr.
+func (s *MappingSet) Invalidate(mr MappableRange, opts InvalidateOpts) {
+	for seg := s.LowerBoundSegment(mr.Start); seg.Ok() && seg.Start() < mr.End; seg = seg.NextSegment() {
+		segMR := seg.Range()
+		for m := range seg.Value() {
+			region := subsetMapping(segMR, segMR.Intersect(mr), m.MappingSpace, m.AddrRange.Start, m.Writable)
+			region.invalidate(opts)
+		}
+	}
+}
+
+// InvalidateAll calls MappingSpace.Invalidate for all mappings of s.
+func (s *MappingSet) InvalidateAll(opts InvalidateOpts) {
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		for m := range seg.Value() {
+			m.invalidate(opts)
+		}
+	}
+}
diff --git a/pkg/sentry/memmap/mapping_set_impl.go b/pkg/sentry/memmap/mapping_set_impl.go
new file mode 100755
index 000000000..eb3071e89
--- /dev/null
+++ b/pkg/sentry/memmap/mapping_set_impl.go
@@ -0,0 +1,1270 @@
+package memmap
+
+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.
+	MappingminDegree = 3
+
+	MappingmaxDegree = 2 * MappingminDegree
+)
+
+// 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 MappingSet struct {
+	root Mappingnode `state:".(*MappingSegmentDataSlices)"`
+}
+
+// IsEmpty returns true if the set contains no segments.
+func (s *MappingSet) 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 *MappingSet) IsEmptyRange(r MappableRange) 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 *MappingSet) 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 *MappingSet) SpanRange(r MappableRange) 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 *MappingSet) FirstSegment() MappingIterator {
+	if s.root.nrSegments == 0 {
+		return MappingIterator{}
+	}
+	return s.root.firstSegment()
+}
+
+// LastSegment returns the last segment in the set. If the set is empty,
+// LastSegment returns a terminal iterator.
+func (s *MappingSet) LastSegment() MappingIterator {
+	if s.root.nrSegments == 0 {
+		return MappingIterator{}
+	}
+	return s.root.lastSegment()
+}
+
+// FirstGap returns the first gap in the set.
+func (s *MappingSet) FirstGap() MappingGapIterator {
+	n := &s.root
+	for n.hasChildren {
+		n = n.children[0]
+	}
+	return MappingGapIterator{n, 0}
+}
+
+// LastGap returns the last gap in the set.
+func (s *MappingSet) LastGap() MappingGapIterator {
+	n := &s.root
+	for n.hasChildren {
+		n = n.children[n.nrSegments]
+	}
+	return MappingGapIterator{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 *MappingSet) Find(key uint64) (MappingIterator, MappingGapIterator) {
+	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 MappingIterator{n, i}, MappingGapIterator{}
+				}
+				upper = i
+			} else {
+				lower = i + 1
+			}
+		}
+		i := lower
+		if !n.hasChildren {
+			return MappingIterator{}, MappingGapIterator{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 *MappingSet) FindSegment(key uint64) MappingIterator {
+	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 *MappingSet) LowerBoundSegment(min uint64) MappingIterator {
+	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 *MappingSet) UpperBoundSegment(max uint64) MappingIterator {
+	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 *MappingSet) FindGap(key uint64) MappingGapIterator {
+	_, gap := s.Find(key)
+	return gap
+}
+
+// LowerBoundGap returns the gap with the lowest range that is greater than or
+// equal to min.
+func (s *MappingSet) LowerBoundGap(min uint64) MappingGapIterator {
+	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 *MappingSet) UpperBoundGap(max uint64) MappingGapIterator {
+	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 *MappingSet) Add(r MappableRange, val MappingsOfRange) 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 *MappingSet) AddWithoutMerging(r MappableRange, val MappingsOfRange) 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 *MappingSet) Insert(gap MappingGapIterator, r MappableRange, val MappingsOfRange) MappingIterator {
+	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 := (mappingSetFunctions{}).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 := (mappingSetFunctions{}).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 := (mappingSetFunctions{}).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 *MappingSet) InsertWithoutMerging(gap MappingGapIterator, r MappableRange, val MappingsOfRange) MappingIterator {
+	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 *MappingSet) InsertWithoutMergingUnchecked(gap MappingGapIterator, r MappableRange, val MappingsOfRange) MappingIterator {
+	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 MappingIterator{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 *MappingSet) Remove(seg MappingIterator) MappingGapIterator {
+
+	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])
+	mappingSetFunctions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1])
+	seg.node.nrSegments--
+	return seg.node.rebalanceAfterRemove(MappingGapIterator{seg.node, seg.index})
+}
+
+// RemoveAll removes all segments from the set. All existing iterators are
+// invalidated.
+func (s *MappingSet) RemoveAll() {
+	s.root = Mappingnode{}
+}
+
+// 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 *MappingSet) RemoveRange(r MappableRange) MappingGapIterator {
+	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 *MappingSet) Merge(first, second MappingIterator) MappingIterator {
+	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 *MappingSet) MergeUnchecked(first, second MappingIterator) MappingIterator {
+	if first.End() == second.Start() {
+		if mval, ok := (mappingSetFunctions{}).Merge(first.Range(), first.Value(), second.Range(), second.Value()); ok {
+
+			first.SetEndUnchecked(second.End())
+			first.SetValue(mval)
+			return s.Remove(second).PrevSegment()
+		}
+	}
+	return MappingIterator{}
+}
+
+// MergeAll attempts to merge all adjacent segments in the set. All existing
+// iterators are invalidated.
+func (s *MappingSet) 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 *MappingSet) MergeRange(r MappableRange) {
+	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 *MappingSet) MergeAdjacent(r MappableRange) {
+	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 *MappingSet) Split(seg MappingIterator, split uint64) (MappingIterator, MappingIterator) {
+	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 *MappingSet) SplitUnchecked(seg MappingIterator, split uint64) (MappingIterator, MappingIterator) {
+	val1, val2 := (mappingSetFunctions{}).Split(seg.Range(), seg.Value(), split)
+	end2 := seg.End()
+	seg.SetEndUnchecked(split)
+	seg.SetValue(val1)
+	seg2 := s.InsertWithoutMergingUnchecked(seg.NextGap(), MappableRange{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 *MappingSet) 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 *MappingSet) Isolate(seg MappingIterator, r MappableRange) MappingIterator {
+	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 *MappingSet) ApplyContiguous(r MappableRange, fn func(seg MappingIterator)) MappingGapIterator {
+	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 MappingGapIterator{}
+		}
+		gap = seg.NextGap()
+		if !gap.IsEmpty() {
+			return gap
+		}
+		seg = gap.NextSegment()
+		if !seg.Ok() {
+
+			return MappingGapIterator{}
+		}
+	}
+}
+
+// +stateify savable
+type Mappingnode 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 *Mappingnode
+
+	// 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     [MappingmaxDegree - 1]MappableRange
+	values   [MappingmaxDegree - 1]MappingsOfRange
+	children [MappingmaxDegree]*Mappingnode
+}
+
+// firstSegment returns the first segment in the subtree rooted by n.
+//
+// Preconditions: n.nrSegments != 0.
+func (n *Mappingnode) firstSegment() MappingIterator {
+	for n.hasChildren {
+		n = n.children[0]
+	}
+	return MappingIterator{n, 0}
+}
+
+// lastSegment returns the last segment in the subtree rooted by n.
+//
+// Preconditions: n.nrSegments != 0.
+func (n *Mappingnode) lastSegment() MappingIterator {
+	for n.hasChildren {
+		n = n.children[n.nrSegments]
+	}
+	return MappingIterator{n, n.nrSegments - 1}
+}
+
+func (n *Mappingnode) prevSibling() *Mappingnode {
+	if n.parent == nil || n.parentIndex == 0 {
+		return nil
+	}
+	return n.parent.children[n.parentIndex-1]
+}
+
+func (n *Mappingnode) nextSibling() *Mappingnode {
+	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 *Mappingnode) rebalanceBeforeInsert(gap MappingGapIterator) MappingGapIterator {
+	if n.parent != nil {
+		gap = n.parent.rebalanceBeforeInsert(gap)
+	}
+	if n.nrSegments < MappingmaxDegree-1 {
+		return gap
+	}
+	if n.parent == nil {
+
+		left := &Mappingnode{
+			nrSegments:  MappingminDegree - 1,
+			parent:      n,
+			parentIndex: 0,
+			hasChildren: n.hasChildren,
+		}
+		right := &Mappingnode{
+			nrSegments:  MappingminDegree - 1,
+			parent:      n,
+			parentIndex: 1,
+			hasChildren: n.hasChildren,
+		}
+		copy(left.keys[:MappingminDegree-1], n.keys[:MappingminDegree-1])
+		copy(left.values[:MappingminDegree-1], n.values[:MappingminDegree-1])
+		copy(right.keys[:MappingminDegree-1], n.keys[MappingminDegree:])
+		copy(right.values[:MappingminDegree-1], n.values[MappingminDegree:])
+		n.keys[0], n.values[0] = n.keys[MappingminDegree-1], n.values[MappingminDegree-1]
+		MappingzeroValueSlice(n.values[1:])
+		if n.hasChildren {
+			copy(left.children[:MappingminDegree], n.children[:MappingminDegree])
+			copy(right.children[:MappingminDegree], n.children[MappingminDegree:])
+			MappingzeroNodeSlice(n.children[2:])
+			for i := 0; i < MappingminDegree; 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 < MappingminDegree {
+			return MappingGapIterator{left, gap.index}
+		}
+		return MappingGapIterator{right, gap.index - MappingminDegree}
+	}
+
+	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[MappingminDegree-1], n.values[MappingminDegree-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 := &Mappingnode{
+		nrSegments:  MappingminDegree - 1,
+		parent:      n.parent,
+		parentIndex: n.parentIndex + 1,
+		hasChildren: n.hasChildren,
+	}
+	n.parent.children[n.parentIndex+1] = sibling
+	n.parent.nrSegments++
+	copy(sibling.keys[:MappingminDegree-1], n.keys[MappingminDegree:])
+	copy(sibling.values[:MappingminDegree-1], n.values[MappingminDegree:])
+	MappingzeroValueSlice(n.values[MappingminDegree-1:])
+	if n.hasChildren {
+		copy(sibling.children[:MappingminDegree], n.children[MappingminDegree:])
+		MappingzeroNodeSlice(n.children[MappingminDegree:])
+		for i := 0; i < MappingminDegree; i++ {
+			sibling.children[i].parent = sibling
+			sibling.children[i].parentIndex = i
+		}
+	}
+	n.nrSegments = MappingminDegree - 1
+
+	if gap.node != n {
+		return gap
+	}
+	if gap.index < MappingminDegree {
+		return gap
+	}
+	return MappingGapIterator{sibling, gap.index - MappingminDegree}
+}
+
+// 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 *Mappingnode) rebalanceAfterRemove(gap MappingGapIterator) MappingGapIterator {
+	for {
+		if n.nrSegments >= MappingminDegree-1 {
+			return gap
+		}
+		if n.parent == nil {
+
+			return gap
+		}
+
+		if sibling := n.prevSibling(); sibling != nil && sibling.nrSegments >= MappingminDegree {
+			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]
+			mappingSetFunctions{}.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 MappingGapIterator{n, 0}
+			}
+			if gap.node == n {
+				return MappingGapIterator{n, gap.index + 1}
+			}
+			return gap
+		}
+		if sibling := n.nextSibling(); sibling != nil && sibling.nrSegments >= MappingminDegree {
+			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:])
+			mappingSetFunctions{}.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 MappingGapIterator{n, n.nrSegments}
+				}
+				return MappingGapIterator{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 MappingGapIterator{p, gap.index}
+			}
+			if gap.node == right {
+				return MappingGapIterator{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 *Mappingnode
+		if n.parentIndex > 0 {
+			left = n.prevSibling()
+			right = n
+		} else {
+			left = n
+			right = n.nextSibling()
+		}
+
+		if gap.node == right {
+			gap = MappingGapIterator{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])
+		mappingSetFunctions{}.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 MappingIterator struct {
+	// node is the node containing the iterated segment. If the iterator is
+	// terminal, node is nil.
+	node *Mappingnode
+
+	// 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 MappingIterator) Ok() bool {
+	return seg.node != nil
+}
+
+// Range returns the iterated segment's range key.
+func (seg MappingIterator) Range() MappableRange {
+	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 MappingIterator) 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 MappingIterator) 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 MappingIterator) SetRangeUnchecked(r MappableRange) {
+	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 MappingIterator) SetRange(r MappableRange) {
+	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 MappingIterator) 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 MappingIterator) 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 MappingIterator) 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 MappingIterator) 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 MappingIterator) Value() MappingsOfRange {
+	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 MappingIterator) ValuePtr() *MappingsOfRange {
+	return &seg.node.values[seg.index]
+}
+
+// SetValue mutates the iterated segment's value. This operation does not
+// invalidate any iterators.
+func (seg MappingIterator) SetValue(val MappingsOfRange) {
+	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 MappingIterator) PrevSegment() MappingIterator {
+	if seg.node.hasChildren {
+		return seg.node.children[seg.index].lastSegment()
+	}
+	if seg.index > 0 {
+		return MappingIterator{seg.node, seg.index - 1}
+	}
+	if seg.node.parent == nil {
+		return MappingIterator{}
+	}
+	return MappingsegmentBeforePosition(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 MappingIterator) NextSegment() MappingIterator {
+	if seg.node.hasChildren {
+		return seg.node.children[seg.index+1].firstSegment()
+	}
+	if seg.index < seg.node.nrSegments-1 {
+		return MappingIterator{seg.node, seg.index + 1}
+	}
+	if seg.node.parent == nil {
+		return MappingIterator{}
+	}
+	return MappingsegmentAfterPosition(seg.node.parent, seg.node.parentIndex)
+}
+
+// PrevGap returns the gap immediately before the iterated segment.
+func (seg MappingIterator) PrevGap() MappingGapIterator {
+	if seg.node.hasChildren {
+
+		return seg.node.children[seg.index].lastSegment().NextGap()
+	}
+	return MappingGapIterator{seg.node, seg.index}
+}
+
+// NextGap returns the gap immediately after the iterated segment.
+func (seg MappingIterator) NextGap() MappingGapIterator {
+	if seg.node.hasChildren {
+		return seg.node.children[seg.index+1].firstSegment().PrevGap()
+	}
+	return MappingGapIterator{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 MappingIterator) PrevNonEmpty() (MappingIterator, MappingGapIterator) {
+	gap := seg.PrevGap()
+	if gap.Range().Length() != 0 {
+		return MappingIterator{}, gap
+	}
+	return gap.PrevSegment(), 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 (seg MappingIterator) NextNonEmpty() (MappingIterator, MappingGapIterator) {
+	gap := seg.NextGap()
+	if gap.Range().Length() != 0 {
+		return MappingIterator{}, gap
+	}
+	return gap.NextSegment(), MappingGapIterator{}
+}
+
+// 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 MappingGapIterator 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  *Mappingnode
+	index int
+}
+
+// Ok returns true if the iterator is not terminal. All other methods are only
+// valid for non-terminal iterators.
+func (gap MappingGapIterator) Ok() bool {
+	return gap.node != nil
+}
+
+// Range returns the range spanned by the iterated gap.
+func (gap MappingGapIterator) Range() MappableRange {
+	return MappableRange{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 MappingGapIterator) Start() uint64 {
+	if ps := gap.PrevSegment(); ps.Ok() {
+		return ps.End()
+	}
+	return mappingSetFunctions{}.MinKey()
+}
+
+// End is equivalent to Range().End, but should be preferred if only the end of
+// the range is needed.
+func (gap MappingGapIterator) End() uint64 {
+	if ns := gap.NextSegment(); ns.Ok() {
+		return ns.Start()
+	}
+	return mappingSetFunctions{}.MaxKey()
+}
+
+// IsEmpty returns true if the iterated gap is empty (that is, the "gap" is
+// between two adjacent segments.)
+func (gap MappingGapIterator) 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 MappingGapIterator) PrevSegment() MappingIterator {
+	return MappingsegmentBeforePosition(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 MappingGapIterator) NextSegment() MappingIterator {
+	return MappingsegmentAfterPosition(gap.node, gap.index)
+}
+
+// PrevGap returns the iterated gap's predecessor. If no such gap exists,
+// PrevGap returns a terminal iterator.
+func (gap MappingGapIterator) PrevGap() MappingGapIterator {
+	seg := gap.PrevSegment()
+	if !seg.Ok() {
+		return MappingGapIterator{}
+	}
+	return seg.PrevGap()
+}
+
+// NextGap returns the iterated gap's successor. If no such gap exists, NextGap
+// returns a terminal iterator.
+func (gap MappingGapIterator) NextGap() MappingGapIterator {
+	seg := gap.NextSegment()
+	if !seg.Ok() {
+		return MappingGapIterator{}
+	}
+	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 MappingsegmentBeforePosition(n *Mappingnode, i int) MappingIterator {
+	for i == 0 {
+		if n.parent == nil {
+			return MappingIterator{}
+		}
+		n, i = n.parent, n.parentIndex
+	}
+	return MappingIterator{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 MappingsegmentAfterPosition(n *Mappingnode, i int) MappingIterator {
+	for i == n.nrSegments {
+		if n.parent == nil {
+			return MappingIterator{}
+		}
+		n, i = n.parent, n.parentIndex
+	}
+	return MappingIterator{n, i}
+}
+
+func MappingzeroValueSlice(slice []MappingsOfRange) {
+
+	for i := range slice {
+		mappingSetFunctions{}.ClearValue(&slice[i])
+	}
+}
+
+func MappingzeroNodeSlice(slice []*Mappingnode) {
+	for i := range slice {
+		slice[i] = nil
+	}
+}
+
+// String stringifies a Set for debugging.
+func (s *MappingSet) String() string {
+	return s.root.String()
+}
+
+// String stringifes a node (and all of its children) for debugging.
+func (n *Mappingnode) String() string {
+	var buf bytes.Buffer
+	n.writeDebugString(&buf, "")
+	return buf.String()
+}
+
+func (n *Mappingnode) 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 MappingSegmentDataSlices struct {
+	Start  []uint64
+	End    []uint64
+	Values []MappingsOfRange
+}
+
+// ExportSortedSlice returns a copy of all segments in the given set, in ascending
+// key order.
+func (s *MappingSet) ExportSortedSlices() *MappingSegmentDataSlices {
+	var sds MappingSegmentDataSlices
+	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 *MappingSet) ImportSortedSlices(sds *MappingSegmentDataSlices) error {
+	if !s.IsEmpty() {
+		return fmt.Errorf("cannot import into non-empty set %v", s)
+	}
+	gap := s.FirstGap()
+	for i := range sds.Start {
+		r := MappableRange{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 *MappingSet) saveRoot() *MappingSegmentDataSlices {
+	return s.ExportSortedSlices()
+}
+
+func (s *MappingSet) loadRoot(sds *MappingSegmentDataSlices) {
+	if err := s.ImportSortedSlices(sds); err != nil {
+		panic(err)
+	}
+}
diff --git a/pkg/sentry/memmap/memmap.go b/pkg/sentry/memmap/memmap.go
new file mode 100644
index 000000000..0106c857d
--- /dev/null
+++ b/pkg/sentry/memmap/memmap.go
@@ -0,0 +1,361 @@
+// 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 memmap defines semantics for memory mappings.
+package memmap
+
+import (
+	"fmt"
+
+	"gvisor.googlesource.com/gvisor/pkg/refs"
+	"gvisor.googlesource.com/gvisor/pkg/sentry/context"
+	"gvisor.googlesource.com/gvisor/pkg/sentry/platform"
+	"gvisor.googlesource.com/gvisor/pkg/sentry/usermem"
+)
+
+// Mappable represents a memory-mappable object, a mutable mapping from uint64
+// offsets to (platform.File, uint64 File offset) pairs.
+//
+// See mm/mm.go for Mappable's place in the lock order.
+//
+// Preconditions: For all Mappable methods, usermem.AddrRanges and
+// MappableRanges must be non-empty (Length() != 0), and usermem.Addrs and
+// Mappable offsets must be page-aligned.
+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 platform.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
+}
+
+// Translations are returned by Mappable.Translate.
+type Translation struct {
+	// Source is the translated range in the Mappable.
+	Source MappableRange
+
+	// File is the mapped file.
+	File platform.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
+}
+
+// FileRange returns the platform.FileRange represented by t.
+func (t Translation) FileRange() platform.FileRange {
+	return platform.FileRange{t.Offset, t.Offset + t.Source.Length()}
+}
+
+// CheckTranslateResult returns an error if (ts, terr) does not satisfy all
+// postconditions for Mappable.Translate(required, optional, at).
+//
+// Preconditions: As for Mappable.Translate.
+func CheckTranslateResult(required, optional MappableRange, at usermem.AccessType, ts []Translation, terr error) error {
+	// Verify that the inputs to Mappable.Translate were valid.
+	if !required.WellFormed() || required.Length() <= 0 {
+		panic(fmt.Sprintf("invalid required range: %v", required))
+	}
+	if !usermem.Addr(required.Start).IsPageAligned() || !usermem.Addr(required.End).IsPageAligned() {
+		panic(fmt.Sprintf("unaligned required range: %v", required))
+	}
+	if !optional.IsSupersetOf(required) {
+		panic(fmt.Sprintf("optional range %v is not a superset of required range %v", optional, required))
+	}
+	if !usermem.Addr(optional.Start).IsPageAligned() || !usermem.Addr(optional.End).IsPageAligned() {
+		panic(fmt.Sprintf("unaligned optional range: %v", optional))
+	}
+
+	// The first Translation must include required.Start.
+	if len(ts) != 0 && !ts[0].Source.Contains(required.Start) {
+		return fmt.Errorf("first Translation %+v does not cover start of required range %v", ts[0], required)
+	}
+	for i, t := range ts {
+		if !t.Source.WellFormed() || t.Source.Length() <= 0 {
+			return fmt.Errorf("Translation %+v has invalid Source", t)
+		}
+		if !usermem.Addr(t.Source.Start).IsPageAligned() || !usermem.Addr(t.Source.End).IsPageAligned() {
+			return fmt.Errorf("Translation %+v has unaligned Source", t)
+		}
+		if t.File == nil {
+			return fmt.Errorf("Translation %+v has nil File", t)
+		}
+		if !usermem.Addr(t.Offset).IsPageAligned() {
+			return fmt.Errorf("Translation %+v has unaligned Offset", t)
+		}
+		// Translations must be contiguous and in increasing order of
+		// Translation.Source.
+		if i > 0 && ts[i-1].Source.End != t.Source.Start {
+			return fmt.Errorf("Translations %+v and %+v are not contiguous", ts[i-1], t)
+		}
+		// At least part of each Translation must be required.
+		if t.Source.Intersect(required).Length() == 0 {
+			return fmt.Errorf("Translation %+v lies entirely outside required range %v", t, required)
+		}
+		// Translations must be constrained to the optional range.
+		if !optional.IsSupersetOf(t.Source) {
+			return fmt.Errorf("Translation %+v lies outside optional range %v", t, optional)
+		}
+		// Each Translation must permit a superset of requested accesses.
+		if !t.Perms.SupersetOf(at) {
+			return fmt.Errorf("Translation %+v does not permit all requested access types %v", t, at)
+		}
+	}
+	// If the set of Translations does not cover the entire required range,
+	// Translate must return a non-nil error explaining why.
+	if terr == nil {
+		if len(ts) == 0 {
+			return fmt.Errorf("no Translations and no error")
+		}
+		if t := ts[len(ts)-1]; !t.Source.Contains(required.End - 1) {
+			return fmt.Errorf("last Translation %+v does not reach end of required range %v, but Translate returned no error", t, required)
+		}
+	}
+	return nil
+}
+
+// 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.
+type BusError struct {
+	// Err is the original error.
+	Err error
+}
+
+// Error implements error.Error.
+func (b *BusError) Error() string {
+	return fmt.Sprintf("BusError: %v", b.Err.Error())
+}
+
+// MappableRange represents a range of uint64 offsets into a Mappable.
+//
+// type MappableRange <generated using go_generics>
+
+// String implements fmt.Stringer.String.
+func (mr MappableRange) String() string {
+	return fmt.Sprintf("[%#x, %#x)", mr.Start, mr.End)
+}
+
+// MappingSpace represents a mutable mapping from usermem.Addrs to (Mappable,
+// uint64 offset) pairs.
+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)
+}
+
+// InvalidateOpts holds options to MappingSpace.Invalidate.
+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
+}
+
+// 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 MappingIdentity interface {
+	// MappingIdentity is reference-counted.
+	refs.RefCounter
+
+	// 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
+}
+
+// MLockMode specifies the memory locking behavior of a memory mapping.
+type MLockMode int
+
+// Note that the ordering of MLockModes is significant; see
+// mm.MemoryManager.defMLockMode.
+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
+)
+
+// MMapOpts specifies a request to create a memory mapping.
+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
+}
diff --git a/pkg/sentry/memmap/memmap_state_autogen.go b/pkg/sentry/memmap/memmap_state_autogen.go
new file mode 100755
index 000000000..42009f82a
--- /dev/null
+++ b/pkg/sentry/memmap/memmap_state_autogen.go
@@ -0,0 +1,93 @@
+// automatically generated by stateify.
+
+package memmap
+
+import (
+	"gvisor.googlesource.com/gvisor/pkg/state"
+)
+
+func (x *MappableRange) beforeSave() {}
+func (x *MappableRange) save(m state.Map) {
+	x.beforeSave()
+	m.Save("Start", &x.Start)
+	m.Save("End", &x.End)
+}
+
+func (x *MappableRange) afterLoad() {}
+func (x *MappableRange) load(m state.Map) {
+	m.Load("Start", &x.Start)
+	m.Load("End", &x.End)
+}
+
+func (x *MappingOfRange) beforeSave() {}
+func (x *MappingOfRange) save(m state.Map) {
+	x.beforeSave()
+	m.Save("MappingSpace", &x.MappingSpace)
+	m.Save("AddrRange", &x.AddrRange)
+	m.Save("Writable", &x.Writable)
+}
+
+func (x *MappingOfRange) afterLoad() {}
+func (x *MappingOfRange) load(m state.Map) {
+	m.Load("MappingSpace", &x.MappingSpace)
+	m.Load("AddrRange", &x.AddrRange)
+	m.Load("Writable", &x.Writable)
+}
+
+func (x *MappingSet) beforeSave() {}
+func (x *MappingSet) save(m state.Map) {
+	x.beforeSave()
+	var root *MappingSegmentDataSlices = x.saveRoot()
+	m.SaveValue("root", root)
+}
+
+func (x *MappingSet) afterLoad() {}
+func (x *MappingSet) load(m state.Map) {
+	m.LoadValue("root", new(*MappingSegmentDataSlices), func(y interface{}) { x.loadRoot(y.(*MappingSegmentDataSlices)) })
+}
+
+func (x *Mappingnode) beforeSave() {}
+func (x *Mappingnode) 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 *Mappingnode) afterLoad() {}
+func (x *Mappingnode) 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 *MappingSegmentDataSlices) beforeSave() {}
+func (x *MappingSegmentDataSlices) save(m state.Map) {
+	x.beforeSave()
+	m.Save("Start", &x.Start)
+	m.Save("End", &x.End)
+	m.Save("Values", &x.Values)
+}
+
+func (x *MappingSegmentDataSlices) afterLoad() {}
+func (x *MappingSegmentDataSlices) load(m state.Map) {
+	m.Load("Start", &x.Start)
+	m.Load("End", &x.End)
+	m.Load("Values", &x.Values)
+}
+
+func init() {
+	state.Register("memmap.MappableRange", (*MappableRange)(nil), state.Fns{Save: (*MappableRange).save, Load: (*MappableRange).load})
+	state.Register("memmap.MappingOfRange", (*MappingOfRange)(nil), state.Fns{Save: (*MappingOfRange).save, Load: (*MappingOfRange).load})
+	state.Register("memmap.MappingSet", (*MappingSet)(nil), state.Fns{Save: (*MappingSet).save, Load: (*MappingSet).load})
+	state.Register("memmap.Mappingnode", (*Mappingnode)(nil), state.Fns{Save: (*Mappingnode).save, Load: (*Mappingnode).load})
+	state.Register("memmap.MappingSegmentDataSlices", (*MappingSegmentDataSlices)(nil), state.Fns{Save: (*MappingSegmentDataSlices).save, Load: (*MappingSegmentDataSlices).load})
+}