Check in gVisor.

PiperOrigin-RevId: 194583126
Change-Id: Ica1d8821a90f74e7e745962d71801c598c652463

4 files changed, 799 insertions, 0 deletions

diff --git a/pkg/sentry/memmap/BUILD b/pkg/sentry/memmap/BUILD
new file mode 100644
index 000000000..7525fea45
--- /dev/null
+++ b/pkg/sentry/memmap/BUILD
@@ -0,0 +1,71 @@
+package(licenses = ["notice"])  # Apache 2.0
+
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//tools/go_generics:defs.bzl", "go_template_instance")
+load("//tools/go_stateify:defs.bzl", "go_stateify")
+
+go_stateify(
+    name = "memmap_state",
+    srcs = [
+        "mappable_range.go",
+        "mapping_set.go",
+        "mapping_set_impl.go",
+    ],
+    out = "memmap_state.go",
+    package = "memmap",
+)
+
+go_template_instance(
+    name = "mappable_range",
+    out = "mappable_range.go",
+    package = "memmap",
+    prefix = "Mappable",
+    template = "//pkg/segment:generic_range",
+    types = {
+        "T": "uint64",
+    },
+)
+
+go_template_instance(
+    name = "mapping_set_impl",
+    out = "mapping_set_impl.go",
+    package = "memmap",
+    prefix = "Mapping",
+    template = "//pkg/segment:generic_set",
+    types = {
+        "Key": "uint64",
+        "Range": "MappableRange",
+        "Value": "MappingsOfRange",
+        "Functions": "mappingSetFunctions",
+    },
+)
+
+go_library(
+    name = "memmap",
+    srcs = [
+        "mappable_range.go",
+        "mapping_set.go",
+        "mapping_set_impl.go",
+        "memmap.go",
+        "memmap_state.go",
+    ],
+    importpath = "gvisor.googlesource.com/gvisor/pkg/sentry/memmap",
+    visibility = ["//pkg/sentry:internal"],
+    deps = [
+        "//pkg/log",
+        "//pkg/refs",
+        "//pkg/sentry/context",
+        "//pkg/sentry/platform",
+        "//pkg/sentry/usermem",
+        "//pkg/state",
+        "//pkg/syserror",
+    ],
+)
+
+go_test(
+    name = "memmap_test",
+    size = "small",
+    srcs = ["mapping_set_test.go"],
+    embed = [":memmap"],
+    deps = ["//pkg/sentry/usermem"],
+)
diff --git a/pkg/sentry/memmap/mapping_set.go b/pkg/sentry/memmap/mapping_set.go
new file mode 100644
index 000000000..0cd42ffbf
--- /dev/null
+++ b/pkg/sentry/memmap/mapping_set.go
@@ -0,0 +1,245 @@
+// Copyright 2018 Google Inc.
+//
+// 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.
+type MappingOfRange struct {
+	MappingSpace MappingSpace
+	AddrRange    usermem.AddrRange
+}
+
+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()),
+			},
+		}
+		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,
+			},
+		}] = 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,
+			},
+		}
+		m1[k1] = struct{}{}
+
+		k2 := MappingOfRange{
+			MappingSpace: k.MappingSpace,
+			AddrRange: usermem.AddrRange{
+				Start: k.AddrRange.Start + offset,
+				End:   k.AddrRange.End,
+			},
+		}
+		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) 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()),
+		},
+	}
+}
+
+// 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) []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)] = 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) []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))
+
+		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)
+			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_test.go b/pkg/sentry/memmap/mapping_set_test.go
new file mode 100644
index 000000000..10668d404
--- /dev/null
+++ b/pkg/sentry/memmap/mapping_set_test.go
@@ -0,0 +1,186 @@
+// Copyright 2018 Google Inc.
+//
+// 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 (
+	"reflect"
+	"testing"
+
+	"gvisor.googlesource.com/gvisor/pkg/sentry/usermem"
+)
+
+type testMappingSpace struct {
+	// Ideally we'd store the full ranges that were invalidated, rather
+	// than individual calls to Invalidate, as they are an implementation
+	// detail, but this is the simplest way for now.
+	inv []usermem.AddrRange
+}
+
+func (n *testMappingSpace) reset() {
+	n.inv = []usermem.AddrRange{}
+}
+
+func (n *testMappingSpace) Invalidate(ar usermem.AddrRange, opts InvalidateOpts) {
+	n.inv = append(n.inv, ar)
+}
+
+func TestAddRemoveMapping(t *testing.T) {
+	set := MappingSet{}
+	ms := &testMappingSpace{}
+
+	mapped := set.AddMapping(ms, usermem.AddrRange{0x10000, 0x12000}, 0x1000)
+	if got, want := mapped, []MappableRange{{0x1000, 0x3000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("AddMapping: got %+v, wanted %+v", got, want)
+	}
+
+	// Mappings (usermem.AddrRanges => memmap.MappableRange):
+	// [0x10000, 0x12000) => [0x1000, 0x3000)
+	t.Log(&set)
+
+	mapped = set.AddMapping(ms, usermem.AddrRange{0x20000, 0x21000}, 0x2000)
+	if len(mapped) != 0 {
+		t.Errorf("AddMapping: got %+v, wanted []", mapped)
+	}
+
+	// Mappings:
+	// [0x10000, 0x11000) => [0x1000, 0x2000)
+	// [0x11000, 0x12000) and [0x20000, 0x21000) => [0x2000, 0x3000)
+	t.Log(&set)
+
+	mapped = set.AddMapping(ms, usermem.AddrRange{0x30000, 0x31000}, 0x4000)
+	if got, want := mapped, []MappableRange{{0x4000, 0x5000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("AddMapping: got %+v, wanted %+v", got, want)
+	}
+
+	// Mappings:
+	// [0x10000, 0x11000) => [0x1000, 0x2000)
+	// [0x11000, 0x12000) and [0x20000, 0x21000) => [0x2000, 0x3000)
+	// [0x30000, 0x31000) => [0x4000, 0x5000)
+	t.Log(&set)
+
+	mapped = set.AddMapping(ms, usermem.AddrRange{0x12000, 0x15000}, 0x3000)
+	if got, want := mapped, []MappableRange{{0x3000, 0x4000}, {0x5000, 0x6000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("AddMapping: got %+v, wanted %+v", got, want)
+	}
+
+	// Mappings:
+	// [0x10000, 0x11000) => [0x1000, 0x2000)
+	// [0x11000, 0x12000) and [0x20000, 0x21000) => [0x2000, 0x3000)
+	// [0x12000, 0x13000) => [0x3000, 0x4000)
+	// [0x13000, 0x14000) and [0x30000, 0x31000) => [0x4000, 0x5000)
+	// [0x14000, 0x15000) => [0x5000, 0x6000)
+	t.Log(&set)
+
+	unmapped := set.RemoveMapping(ms, usermem.AddrRange{0x10000, 0x11000}, 0x1000)
+	if got, want := unmapped, []MappableRange{{0x1000, 0x2000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("RemoveMapping: got %+v, wanted %+v", got, want)
+	}
+
+	// Mappings:
+	// [0x11000, 0x12000) and [0x20000, 0x21000) => [0x2000, 0x3000)
+	// [0x12000, 0x13000) => [0x3000, 0x4000)
+	// [0x13000, 0x14000) and [0x30000, 0x31000) => [0x4000, 0x5000)
+	// [0x14000, 0x15000) => [0x5000, 0x6000)
+	t.Log(&set)
+
+	unmapped = set.RemoveMapping(ms, usermem.AddrRange{0x20000, 0x21000}, 0x2000)
+	if len(unmapped) != 0 {
+		t.Errorf("RemoveMapping: got %+v, wanted []", unmapped)
+	}
+
+	// Mappings:
+	// [0x11000, 0x13000) => [0x2000, 0x4000)
+	// [0x13000, 0x14000) and [0x30000, 0x31000) => [0x4000, 0x5000)
+	// [0x14000, 0x15000) => [0x5000, 0x6000)
+	t.Log(&set)
+
+	unmapped = set.RemoveMapping(ms, usermem.AddrRange{0x11000, 0x15000}, 0x2000)
+	if got, want := unmapped, []MappableRange{{0x2000, 0x4000}, {0x5000, 0x6000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("RemoveMapping: got %+v, wanted %+v", got, want)
+	}
+
+	// Mappings:
+	// [0x30000, 0x31000) => [0x4000, 0x5000)
+	t.Log(&set)
+
+	unmapped = set.RemoveMapping(ms, usermem.AddrRange{0x30000, 0x31000}, 0x4000)
+	if got, want := unmapped, []MappableRange{{0x4000, 0x5000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("RemoveMapping: got %+v, wanted %+v", got, want)
+	}
+}
+
+func TestInvalidateWholeMapping(t *testing.T) {
+	set := MappingSet{}
+	ms := &testMappingSpace{}
+
+	set.AddMapping(ms, usermem.AddrRange{0x10000, 0x11000}, 0)
+	// Mappings:
+	// [0x10000, 0x11000) => [0, 0x1000)
+	t.Log(&set)
+	set.Invalidate(MappableRange{0, 0x1000}, InvalidateOpts{})
+	if got, want := ms.inv, []usermem.AddrRange{{0x10000, 0x11000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("Invalidate: got %+v, wanted %+v", got, want)
+	}
+}
+
+func TestInvalidatePartialMapping(t *testing.T) {
+	set := MappingSet{}
+	ms := &testMappingSpace{}
+
+	set.AddMapping(ms, usermem.AddrRange{0x10000, 0x13000}, 0)
+	// Mappings:
+	// [0x10000, 0x13000) => [0, 0x3000)
+	t.Log(&set)
+	set.Invalidate(MappableRange{0x1000, 0x2000}, InvalidateOpts{})
+	if got, want := ms.inv, []usermem.AddrRange{{0x11000, 0x12000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("Invalidate: got %+v, wanted %+v", got, want)
+	}
+}
+
+func TestInvalidateMultipleMappings(t *testing.T) {
+	set := MappingSet{}
+	ms := &testMappingSpace{}
+
+	set.AddMapping(ms, usermem.AddrRange{0x10000, 0x11000}, 0)
+	set.AddMapping(ms, usermem.AddrRange{0x20000, 0x21000}, 0x2000)
+	// Mappings:
+	// [0x10000, 0x11000) => [0, 0x1000)
+	// [0x12000, 0x13000) => [0x2000, 0x3000)
+	t.Log(&set)
+	set.Invalidate(MappableRange{0, 0x3000}, InvalidateOpts{})
+	if got, want := ms.inv, []usermem.AddrRange{{0x10000, 0x11000}, {0x20000, 0x21000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("Invalidate: got %+v, wanted %+v", got, want)
+	}
+}
+
+func TestInvalidateOverlappingMappings(t *testing.T) {
+	set := MappingSet{}
+	ms1 := &testMappingSpace{}
+	ms2 := &testMappingSpace{}
+
+	set.AddMapping(ms1, usermem.AddrRange{0x10000, 0x12000}, 0)
+	set.AddMapping(ms2, usermem.AddrRange{0x20000, 0x22000}, 0x1000)
+	// Mappings:
+	// ms1:[0x10000, 0x12000) => [0, 0x2000)
+	// ms2:[0x11000, 0x13000) => [0x1000, 0x3000)
+	t.Log(&set)
+	set.Invalidate(MappableRange{0x1000, 0x2000}, InvalidateOpts{})
+	if got, want := ms1.inv, []usermem.AddrRange{{0x11000, 0x12000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("Invalidate: ms1: got %+v, wanted %+v", got, want)
+	}
+	if got, want := ms2.inv, []usermem.AddrRange{{0x20000, 0x21000}}; !reflect.DeepEqual(got, want) {
+		t.Errorf("Invalidate: ms1: got %+v, wanted %+v", got, want)
+	}
+}
diff --git a/pkg/sentry/memmap/memmap.go b/pkg/sentry/memmap/memmap.go
new file mode 100644
index 000000000..14fed55bc
--- /dev/null
+++ b/pkg/sentry/memmap/memmap.go
@@ -0,0 +1,297 @@
+// Copyright 2018 Google Inc.
+//
+// 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.
+	//
+	// Preconditions: offset+ar.Length() does not overflow.
+	AddMapping(ctx context.Context, ms MappingSpace, ar usermem.AddrRange, offset uint64) 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.
+	RemoveMapping(ctx context.Context, ms MappingSpace, ar usermem.AddrRange, offset uint64)
+
+	// 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.
+	//
+	// 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+dstAR.Length() does not overflow. The mapping at
+	// srcAR must exist.
+	CopyMapping(ctx context.Context, ms MappingSpace, srcAR, dstAR usermem.AddrRange, offset uint64) 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. Returned
+	// translations, and any mappings returned by platform.File.MapInternal for
+	// translated platform.Files, are valid until invalidated by a call back to
+	// MappingSpace.Invalidate or until the caller removes its mapping of the
+	// translated range.
+	//
+	// 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. When the Translation is invalidated, pages
+	// mapped by File.MapInto must be unmapped, and pages mapped by
+	// File.MapInternal become invalid.
+	File platform.File
+
+	// Offset is the offset into File at which this Translation begins.
+	Offset uint64
+}
+
+// CheckTranslateResult returns an error if (ts, terr) does not satisfy all
+// postconditions for Mappable.Translate(required, optional).
+//
+// Preconditions: As for Mappable.Translate.
+func CheckTranslateResult(required, optional MappableRange, 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)
+		}
+	}
+	// 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
+}
+
+// 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
+
+	// 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
+
+	// Hint is the name used for the mapping in /proc/[pid]/maps. If Hint is
+	// empty, MappingIdentity.MappedName() will be used instead.
+	//
+	// TODO: Replace entirely with MappingIdentity?
+	Hint string
+}