Merge release-20200518.0-45-g0bc022b7 (automated)

7 files changed, 1165 insertions, 12 deletions

diff --git a/pkg/sentry/fs/fsutil/dirty_set_impl.go b/pkg/sentry/fs/fsutil/dirty_set_impl.go
index 2510b81b3..8d462c412 100755..100644
--- a/pkg/sentry/fs/fsutil/dirty_set_impl.go
+++ b/pkg/sentry/fs/fsutil/dirty_set_impl.go
@@ -9,6 +9,34 @@ import (
 	"fmt"
 )
 
+// trackGaps is an optional parameter.
+//
+// If trackGaps is 1, the Set will track maximum gap size recursively,
+// enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this
+// case, Key must be an unsigned integer.
+//
+// trackGaps must be 0 or 1.
+const DirtytrackGaps = 0
+
+var _ = uint8(DirtytrackGaps << 7) // Will fail if not zero or one.
+
+// dynamicGap is a type that disappears if trackGaps is 0.
+type DirtydynamicGap [DirtytrackGaps]uint64
+
+// Get returns the value of the gap.
+//
+// Precondition: trackGaps must be non-zero.
+func (d *DirtydynamicGap) Get() uint64 {
+	return d[:][0]
+}
+
+// Set sets the value of the gap.
+//
+// Precondition: trackGaps must be non-zero.
+func (d *DirtydynamicGap) Set(v uint64) {
+	d[:][0] = v
+}
+
 const (
 	// minDegree is the minimum degree of an internal node in a Set B-tree.
 	//
@@ -267,8 +295,12 @@ func (s *DirtySet) Insert(gap DirtyGapIterator, r __generics_imported0.MappableR
 	}
 	if prev.Ok() && prev.End() == r.Start {
 		if mval, ok := (dirtySetFunctions{}).Merge(prev.Range(), prev.Value(), r, val); ok {
+			shrinkMaxGap := DirtytrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
 			prev.SetEndUnchecked(r.End)
 			prev.SetValue(mval)
+			if shrinkMaxGap {
+				gap.node.updateMaxGapLeaf()
+			}
 			if next.Ok() && next.Start() == r.End {
 				val = mval
 				if mval, ok := (dirtySetFunctions{}).Merge(prev.Range(), val, next.Range(), next.Value()); ok {
@@ -282,11 +314,16 @@ func (s *DirtySet) Insert(gap DirtyGapIterator, r __generics_imported0.MappableR
 	}
 	if next.Ok() && next.Start() == r.End {
 		if mval, ok := (dirtySetFunctions{}).Merge(r, val, next.Range(), next.Value()); ok {
+			shrinkMaxGap := DirtytrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
 			next.SetStartUnchecked(r.Start)
 			next.SetValue(mval)
+			if shrinkMaxGap {
+				gap.node.updateMaxGapLeaf()
+			}
 			return next
 		}
 	}
+
 	return s.InsertWithoutMergingUnchecked(gap, r, val)
 }
 
@@ -313,11 +350,15 @@ func (s *DirtySet) InsertWithoutMerging(gap DirtyGapIterator, r __generics_impor
 // Preconditions: r.Start >= gap.Start(); r.End <= gap.End().
 func (s *DirtySet) InsertWithoutMergingUnchecked(gap DirtyGapIterator, r __generics_imported0.MappableRange, val DirtyInfo) DirtyIterator {
 	gap = gap.node.rebalanceBeforeInsert(gap)
+	splitMaxGap := DirtytrackGaps != 0 && (gap.node.nrSegments == 0 || gap.Range().Length() == gap.node.maxGap.Get())
 	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++
+	if splitMaxGap {
+		gap.node.updateMaxGapLeaf()
+	}
 	return DirtyIterator{gap.node, gap.index}
 }
 
@@ -332,12 +373,20 @@ func (s *DirtySet) Remove(seg DirtyIterator) DirtyGapIterator {
 
 		seg.SetRangeUnchecked(victim.Range())
 		seg.SetValue(victim.Value())
+
+		nextAdjacentNode := seg.NextSegment().node
+		if DirtytrackGaps != 0 {
+			nextAdjacentNode.updateMaxGapLeaf()
+		}
 		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])
 	dirtySetFunctions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1])
 	seg.node.nrSegments--
+	if DirtytrackGaps != 0 {
+		seg.node.updateMaxGapLeaf()
+	}
 	return seg.node.rebalanceAfterRemove(DirtyGapIterator{seg.node, seg.index})
 }
 
@@ -387,6 +436,7 @@ func (s *DirtySet) MergeUnchecked(first, second DirtyIterator) DirtyIterator {
 
 			first.SetEndUnchecked(second.End())
 			first.SetValue(mval)
+
 			return s.Remove(second).PrevSegment()
 		}
 	}
@@ -562,6 +612,12 @@ type Dirtynode struct {
 	// than "isLeaf" because false must be the correct value for an empty root.
 	hasChildren bool
 
+	// The longest gap within this node. If the node is a leaf, it's simply the
+	// maximum gap among all the (nrSegments+1) gaps formed by its nrSegments keys
+	// including the 0th and nrSegments-th gap possibly shared with its upper-level
+	// nodes; if it's a non-leaf node, it's the max of all children's maxGap.
+	maxGap DirtydynamicGap
+
 	// Nodes store keys and values in separate arrays to maximize locality in
 	// the common case (scanning keys for lookup).
 	keys     [DirtymaxDegree - 1]__generics_imported0.MappableRange
@@ -607,12 +663,12 @@ func (n *Dirtynode) nextSibling() *Dirtynode {
 // required for insertion, and returns an updated iterator to the position
 // represented by gap.
 func (n *Dirtynode) rebalanceBeforeInsert(gap DirtyGapIterator) DirtyGapIterator {
-	if n.parent != nil {
-		gap = n.parent.rebalanceBeforeInsert(gap)
-	}
 	if n.nrSegments < DirtymaxDegree-1 {
 		return gap
 	}
+	if n.parent != nil {
+		gap = n.parent.rebalanceBeforeInsert(gap)
+	}
 	if n.parent == nil {
 
 		left := &Dirtynode{
@@ -648,6 +704,11 @@ func (n *Dirtynode) rebalanceBeforeInsert(gap DirtyGapIterator) DirtyGapIterator
 		n.hasChildren = true
 		n.children[0] = left
 		n.children[1] = right
+
+		if DirtytrackGaps != 0 {
+			left.updateMaxGapLocal()
+			right.updateMaxGapLocal()
+		}
 		if gap.node != n {
 			return gap
 		}
@@ -685,6 +746,11 @@ func (n *Dirtynode) rebalanceBeforeInsert(gap DirtyGapIterator) DirtyGapIterator
 	}
 	n.nrSegments = DirtyminDegree - 1
 
+	if DirtytrackGaps != 0 {
+		n.updateMaxGapLocal()
+		sibling.updateMaxGapLocal()
+	}
+
 	if gap.node != n {
 		return gap
 	}
@@ -730,6 +796,11 @@ func (n *Dirtynode) rebalanceAfterRemove(gap DirtyGapIterator) DirtyGapIterator
 			}
 			n.nrSegments++
 			sibling.nrSegments--
+
+			if DirtytrackGaps != 0 {
+				n.updateMaxGapLocal()
+				sibling.updateMaxGapLocal()
+			}
 			if gap.node == sibling && gap.index == sibling.nrSegments {
 				return DirtyGapIterator{n, 0}
 			}
@@ -758,6 +829,11 @@ func (n *Dirtynode) rebalanceAfterRemove(gap DirtyGapIterator) DirtyGapIterator
 			}
 			n.nrSegments++
 			sibling.nrSegments--
+
+			if DirtytrackGaps != 0 {
+				n.updateMaxGapLocal()
+				sibling.updateMaxGapLocal()
+			}
 			if gap.node == sibling {
 				if gap.index == 0 {
 					return DirtyGapIterator{n, n.nrSegments}
@@ -790,6 +866,7 @@ func (n *Dirtynode) rebalanceAfterRemove(gap DirtyGapIterator) DirtyGapIterator
 				p.children[0] = nil
 				p.children[1] = nil
 			}
+
 			if gap.node == left {
 				return DirtyGapIterator{p, gap.index}
 			}
@@ -836,10 +913,146 @@ func (n *Dirtynode) rebalanceAfterRemove(gap DirtyGapIterator) DirtyGapIterator
 		p.children[p.nrSegments] = nil
 		p.nrSegments--
 
+		if DirtytrackGaps != 0 {
+			left.updateMaxGapLocal()
+		}
+
 		n = p
 	}
 }
 
+// updateMaxGapLeaf updates maxGap bottom-up from the calling leaf until no
+// necessary update.
+//
+// Preconditions: n must be a leaf node, trackGaps must be 1.
+func (n *Dirtynode) updateMaxGapLeaf() {
+	if n.hasChildren {
+		panic(fmt.Sprintf("updateMaxGapLeaf should always be called on leaf node: %v", n))
+	}
+	max := n.calculateMaxGapLeaf()
+	if max == n.maxGap.Get() {
+
+		return
+	}
+	oldMax := n.maxGap.Get()
+	n.maxGap.Set(max)
+	if max > oldMax {
+
+		for p := n.parent; p != nil; p = p.parent {
+			if p.maxGap.Get() >= max {
+
+				break
+			}
+
+			p.maxGap.Set(max)
+		}
+		return
+	}
+
+	for p := n.parent; p != nil; p = p.parent {
+		if p.maxGap.Get() > oldMax {
+
+			break
+		}
+
+		parentNewMax := p.calculateMaxGapInternal()
+		if p.maxGap.Get() == parentNewMax {
+
+			break
+		}
+
+		p.maxGap.Set(parentNewMax)
+	}
+}
+
+// updateMaxGapLocal updates maxGap of the calling node solely with no
+// propagation to ancestor nodes.
+//
+// Precondition: trackGaps must be 1.
+func (n *Dirtynode) updateMaxGapLocal() {
+	if !n.hasChildren {
+
+		n.maxGap.Set(n.calculateMaxGapLeaf())
+	} else {
+
+		n.maxGap.Set(n.calculateMaxGapInternal())
+	}
+}
+
+// calculateMaxGapLeaf iterates the gaps within a leaf node and calculate the
+// max.
+//
+// Preconditions: n must be a leaf node.
+func (n *Dirtynode) calculateMaxGapLeaf() uint64 {
+	max := DirtyGapIterator{n, 0}.Range().Length()
+	for i := 1; i <= n.nrSegments; i++ {
+		if current := (DirtyGapIterator{n, i}).Range().Length(); current > max {
+			max = current
+		}
+	}
+	return max
+}
+
+// calculateMaxGapInternal iterates children's maxGap within an internal node n
+// and calculate the max.
+//
+// Preconditions: n must be a non-leaf node.
+func (n *Dirtynode) calculateMaxGapInternal() uint64 {
+	max := n.children[0].maxGap.Get()
+	for i := 1; i <= n.nrSegments; i++ {
+		if current := n.children[i].maxGap.Get(); current > max {
+			max = current
+		}
+	}
+	return max
+}
+
+// searchFirstLargeEnoughGap returns the first gap having at least minSize length
+// in the subtree rooted by n. If not found, return a terminal gap iterator.
+func (n *Dirtynode) searchFirstLargeEnoughGap(minSize uint64) DirtyGapIterator {
+	if n.maxGap.Get() < minSize {
+		return DirtyGapIterator{}
+	}
+	if n.hasChildren {
+		for i := 0; i <= n.nrSegments; i++ {
+			if largeEnoughGap := n.children[i].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		}
+	} else {
+		for i := 0; i <= n.nrSegments; i++ {
+			currentGap := DirtyGapIterator{n, i}
+			if currentGap.Range().Length() >= minSize {
+				return currentGap
+			}
+		}
+	}
+	panic(fmt.Sprintf("invalid maxGap in %v", n))
+}
+
+// searchLastLargeEnoughGap returns the last gap having at least minSize length
+// in the subtree rooted by n. If not found, return a terminal gap iterator.
+func (n *Dirtynode) searchLastLargeEnoughGap(minSize uint64) DirtyGapIterator {
+	if n.maxGap.Get() < minSize {
+		return DirtyGapIterator{}
+	}
+	if n.hasChildren {
+		for i := n.nrSegments; i >= 0; i-- {
+			if largeEnoughGap := n.children[i].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		}
+	} else {
+		for i := n.nrSegments; i >= 0; i-- {
+			currentGap := DirtyGapIterator{n, i}
+			if currentGap.Range().Length() >= minSize {
+				return currentGap
+			}
+		}
+	}
+	panic(fmt.Sprintf("invalid maxGap in %v", n))
+}
+
 // A Iterator is conceptually one of:
 //
 // - A pointer to a segment in a set; or
@@ -1145,6 +1358,114 @@ func (gap DirtyGapIterator) NextGap() DirtyGapIterator {
 	return seg.NextGap()
 }
 
+// NextLargeEnoughGap returns the iterated gap's first next gap with larger
+// length than minSize.  If not found, return a terminal gap iterator (does NOT
+// include this gap itself).
+//
+// Precondition: trackGaps must be 1.
+func (gap DirtyGapIterator) NextLargeEnoughGap(minSize uint64) DirtyGapIterator {
+	if DirtytrackGaps != 1 {
+		panic("set is not tracking gaps")
+	}
+	if gap.node != nil && gap.node.hasChildren && gap.index == gap.node.nrSegments {
+
+		gap.node = gap.NextSegment().node
+		gap.index = 0
+		return gap.nextLargeEnoughGapHelper(minSize)
+	}
+	return gap.nextLargeEnoughGapHelper(minSize)
+}
+
+// nextLargeEnoughGapHelper is the helper function used by NextLargeEnoughGap
+// to do the real recursions.
+//
+// Preconditions: gap is NOT the trailing gap of a non-leaf node.
+func (gap DirtyGapIterator) nextLargeEnoughGapHelper(minSize uint64) DirtyGapIterator {
+
+	for gap.node != nil &&
+		(gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == gap.node.nrSegments)) {
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+
+	if gap.node == nil {
+		return DirtyGapIterator{}
+	}
+
+	gap.index++
+	for gap.index <= gap.node.nrSegments {
+		if gap.node.hasChildren {
+			if largeEnoughGap := gap.node.children[gap.index].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		} else {
+			if gap.Range().Length() >= minSize {
+				return gap
+			}
+		}
+		gap.index++
+	}
+	gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	if gap.node != nil && gap.index == gap.node.nrSegments {
+
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+	return gap.nextLargeEnoughGapHelper(minSize)
+}
+
+// PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or
+// equal length than minSize.  If not found, return a terminal gap iterator
+// (does NOT include this gap itself).
+//
+// Precondition: trackGaps must be 1.
+func (gap DirtyGapIterator) PrevLargeEnoughGap(minSize uint64) DirtyGapIterator {
+	if DirtytrackGaps != 1 {
+		panic("set is not tracking gaps")
+	}
+	if gap.node != nil && gap.node.hasChildren && gap.index == 0 {
+
+		gap.node = gap.PrevSegment().node
+		gap.index = gap.node.nrSegments
+		return gap.prevLargeEnoughGapHelper(minSize)
+	}
+	return gap.prevLargeEnoughGapHelper(minSize)
+}
+
+// prevLargeEnoughGapHelper is the helper function used by PrevLargeEnoughGap
+// to do the real recursions.
+//
+// Preconditions: gap is NOT the first gap of a non-leaf node.
+func (gap DirtyGapIterator) prevLargeEnoughGapHelper(minSize uint64) DirtyGapIterator {
+
+	for gap.node != nil &&
+		(gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == 0)) {
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+
+	if gap.node == nil {
+		return DirtyGapIterator{}
+	}
+
+	gap.index--
+	for gap.index >= 0 {
+		if gap.node.hasChildren {
+			if largeEnoughGap := gap.node.children[gap.index].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		} else {
+			if gap.Range().Length() >= minSize {
+				return gap
+			}
+		}
+		gap.index--
+	}
+	gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	if gap.node != nil && gap.index == 0 {
+
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+	return gap.prevLargeEnoughGapHelper(minSize)
+}
+
 // 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.
@@ -1211,7 +1532,15 @@ func (n *Dirtynode) writeDebugString(buf *bytes.Buffer, prefix string) {
 			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 n.hasChildren {
+			if DirtytrackGaps != 0 {
+				buf.WriteString(fmt.Sprintf("- % 3d: %v => %v, maxGap: %d\n", i, n.keys[i], n.values[i], n.maxGap.Get()))
+			} else {
+				buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i]))
+			}
+		} else {
+			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))
@@ -1263,6 +1592,46 @@ func (s *DirtySet) ImportSortedSlices(sds *DirtySegmentDataSlices) error {
 	}
 	return nil
 }
+
+// segmentTestCheck returns an error if s is incorrectly sorted, does not
+// contain exactly expectedSegments segments, or contains a segment which
+// fails the passed check.
+//
+// This should be used only for testing, and has been added to this package for
+// templating convenience.
+func (s *DirtySet) segmentTestCheck(expectedSegments int, segFunc func(int, __generics_imported0.MappableRange, DirtyInfo) error) error {
+	havePrev := false
+	prev := uint64(0)
+	nrSegments := 0
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		next := seg.Start()
+		if havePrev && prev >= next {
+			return fmt.Errorf("incorrect order: key %d (segment %d) >= key %d (segment %d)", prev, nrSegments-1, next, nrSegments)
+		}
+		if segFunc != nil {
+			if err := segFunc(nrSegments, seg.Range(), seg.Value()); err != nil {
+				return err
+			}
+		}
+		prev = next
+		havePrev = true
+		nrSegments++
+	}
+	if nrSegments != expectedSegments {
+		return fmt.Errorf("incorrect number of segments: got %d, wanted %d", nrSegments, expectedSegments)
+	}
+	return nil
+}
+
+// countSegments counts the number of segments in the set.
+//
+// Similar to Check, this should only be used for testing.
+func (s *DirtySet) countSegments() (segments int) {
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		segments++
+	}
+	return segments
+}
 func (s *DirtySet) saveRoot() *DirtySegmentDataSlices {
 	return s.ExportSortedSlices()
 }
diff --git a/pkg/sentry/fs/fsutil/file_range_set_impl.go b/pkg/sentry/fs/fsutil/file_range_set_impl.go
index 01e7a2401..e5b6d1041 100755..100644
--- a/pkg/sentry/fs/fsutil/file_range_set_impl.go
+++ b/pkg/sentry/fs/fsutil/file_range_set_impl.go
@@ -9,6 +9,34 @@ import (
 	"fmt"
 )
 
+// trackGaps is an optional parameter.
+//
+// If trackGaps is 1, the Set will track maximum gap size recursively,
+// enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this
+// case, Key must be an unsigned integer.
+//
+// trackGaps must be 0 or 1.
+const FileRangetrackGaps = 0
+
+var _ = uint8(FileRangetrackGaps << 7) // Will fail if not zero or one.
+
+// dynamicGap is a type that disappears if trackGaps is 0.
+type FileRangedynamicGap [FileRangetrackGaps]uint64
+
+// Get returns the value of the gap.
+//
+// Precondition: trackGaps must be non-zero.
+func (d *FileRangedynamicGap) Get() uint64 {
+	return d[:][0]
+}
+
+// Set sets the value of the gap.
+//
+// Precondition: trackGaps must be non-zero.
+func (d *FileRangedynamicGap) Set(v uint64) {
+	d[:][0] = v
+}
+
 const (
 	// minDegree is the minimum degree of an internal node in a Set B-tree.
 	//
@@ -267,8 +295,12 @@ func (s *FileRangeSet) Insert(gap FileRangeGapIterator, r __generics_imported0.M
 	}
 	if prev.Ok() && prev.End() == r.Start {
 		if mval, ok := (FileRangeSetFunctions{}).Merge(prev.Range(), prev.Value(), r, val); ok {
+			shrinkMaxGap := FileRangetrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
 			prev.SetEndUnchecked(r.End)
 			prev.SetValue(mval)
+			if shrinkMaxGap {
+				gap.node.updateMaxGapLeaf()
+			}
 			if next.Ok() && next.Start() == r.End {
 				val = mval
 				if mval, ok := (FileRangeSetFunctions{}).Merge(prev.Range(), val, next.Range(), next.Value()); ok {
@@ -282,11 +314,16 @@ func (s *FileRangeSet) Insert(gap FileRangeGapIterator, r __generics_imported0.M
 	}
 	if next.Ok() && next.Start() == r.End {
 		if mval, ok := (FileRangeSetFunctions{}).Merge(r, val, next.Range(), next.Value()); ok {
+			shrinkMaxGap := FileRangetrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
 			next.SetStartUnchecked(r.Start)
 			next.SetValue(mval)
+			if shrinkMaxGap {
+				gap.node.updateMaxGapLeaf()
+			}
 			return next
 		}
 	}
+
 	return s.InsertWithoutMergingUnchecked(gap, r, val)
 }
 
@@ -313,11 +350,15 @@ func (s *FileRangeSet) InsertWithoutMerging(gap FileRangeGapIterator, r __generi
 // Preconditions: r.Start >= gap.Start(); r.End <= gap.End().
 func (s *FileRangeSet) InsertWithoutMergingUnchecked(gap FileRangeGapIterator, r __generics_imported0.MappableRange, val uint64) FileRangeIterator {
 	gap = gap.node.rebalanceBeforeInsert(gap)
+	splitMaxGap := FileRangetrackGaps != 0 && (gap.node.nrSegments == 0 || gap.Range().Length() == gap.node.maxGap.Get())
 	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++
+	if splitMaxGap {
+		gap.node.updateMaxGapLeaf()
+	}
 	return FileRangeIterator{gap.node, gap.index}
 }
 
@@ -332,12 +373,20 @@ func (s *FileRangeSet) Remove(seg FileRangeIterator) FileRangeGapIterator {
 
 		seg.SetRangeUnchecked(victim.Range())
 		seg.SetValue(victim.Value())
+
+		nextAdjacentNode := seg.NextSegment().node
+		if FileRangetrackGaps != 0 {
+			nextAdjacentNode.updateMaxGapLeaf()
+		}
 		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])
 	FileRangeSetFunctions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1])
 	seg.node.nrSegments--
+	if FileRangetrackGaps != 0 {
+		seg.node.updateMaxGapLeaf()
+	}
 	return seg.node.rebalanceAfterRemove(FileRangeGapIterator{seg.node, seg.index})
 }
 
@@ -387,6 +436,7 @@ func (s *FileRangeSet) MergeUnchecked(first, second FileRangeIterator) FileRange
 
 			first.SetEndUnchecked(second.End())
 			first.SetValue(mval)
+
 			return s.Remove(second).PrevSegment()
 		}
 	}
@@ -562,6 +612,12 @@ type FileRangenode struct {
 	// than "isLeaf" because false must be the correct value for an empty root.
 	hasChildren bool
 
+	// The longest gap within this node. If the node is a leaf, it's simply the
+	// maximum gap among all the (nrSegments+1) gaps formed by its nrSegments keys
+	// including the 0th and nrSegments-th gap possibly shared with its upper-level
+	// nodes; if it's a non-leaf node, it's the max of all children's maxGap.
+	maxGap FileRangedynamicGap
+
 	// Nodes store keys and values in separate arrays to maximize locality in
 	// the common case (scanning keys for lookup).
 	keys     [FileRangemaxDegree - 1]__generics_imported0.MappableRange
@@ -607,12 +663,12 @@ func (n *FileRangenode) nextSibling() *FileRangenode {
 // required for insertion, and returns an updated iterator to the position
 // represented by gap.
 func (n *FileRangenode) rebalanceBeforeInsert(gap FileRangeGapIterator) FileRangeGapIterator {
-	if n.parent != nil {
-		gap = n.parent.rebalanceBeforeInsert(gap)
-	}
 	if n.nrSegments < FileRangemaxDegree-1 {
 		return gap
 	}
+	if n.parent != nil {
+		gap = n.parent.rebalanceBeforeInsert(gap)
+	}
 	if n.parent == nil {
 
 		left := &FileRangenode{
@@ -648,6 +704,11 @@ func (n *FileRangenode) rebalanceBeforeInsert(gap FileRangeGapIterator) FileRang
 		n.hasChildren = true
 		n.children[0] = left
 		n.children[1] = right
+
+		if FileRangetrackGaps != 0 {
+			left.updateMaxGapLocal()
+			right.updateMaxGapLocal()
+		}
 		if gap.node != n {
 			return gap
 		}
@@ -685,6 +746,11 @@ func (n *FileRangenode) rebalanceBeforeInsert(gap FileRangeGapIterator) FileRang
 	}
 	n.nrSegments = FileRangeminDegree - 1
 
+	if FileRangetrackGaps != 0 {
+		n.updateMaxGapLocal()
+		sibling.updateMaxGapLocal()
+	}
+
 	if gap.node != n {
 		return gap
 	}
@@ -730,6 +796,11 @@ func (n *FileRangenode) rebalanceAfterRemove(gap FileRangeGapIterator) FileRange
 			}
 			n.nrSegments++
 			sibling.nrSegments--
+
+			if FileRangetrackGaps != 0 {
+				n.updateMaxGapLocal()
+				sibling.updateMaxGapLocal()
+			}
 			if gap.node == sibling && gap.index == sibling.nrSegments {
 				return FileRangeGapIterator{n, 0}
 			}
@@ -758,6 +829,11 @@ func (n *FileRangenode) rebalanceAfterRemove(gap FileRangeGapIterator) FileRange
 			}
 			n.nrSegments++
 			sibling.nrSegments--
+
+			if FileRangetrackGaps != 0 {
+				n.updateMaxGapLocal()
+				sibling.updateMaxGapLocal()
+			}
 			if gap.node == sibling {
 				if gap.index == 0 {
 					return FileRangeGapIterator{n, n.nrSegments}
@@ -790,6 +866,7 @@ func (n *FileRangenode) rebalanceAfterRemove(gap FileRangeGapIterator) FileRange
 				p.children[0] = nil
 				p.children[1] = nil
 			}
+
 			if gap.node == left {
 				return FileRangeGapIterator{p, gap.index}
 			}
@@ -836,10 +913,146 @@ func (n *FileRangenode) rebalanceAfterRemove(gap FileRangeGapIterator) FileRange
 		p.children[p.nrSegments] = nil
 		p.nrSegments--
 
+		if FileRangetrackGaps != 0 {
+			left.updateMaxGapLocal()
+		}
+
 		n = p
 	}
 }
 
+// updateMaxGapLeaf updates maxGap bottom-up from the calling leaf until no
+// necessary update.
+//
+// Preconditions: n must be a leaf node, trackGaps must be 1.
+func (n *FileRangenode) updateMaxGapLeaf() {
+	if n.hasChildren {
+		panic(fmt.Sprintf("updateMaxGapLeaf should always be called on leaf node: %v", n))
+	}
+	max := n.calculateMaxGapLeaf()
+	if max == n.maxGap.Get() {
+
+		return
+	}
+	oldMax := n.maxGap.Get()
+	n.maxGap.Set(max)
+	if max > oldMax {
+
+		for p := n.parent; p != nil; p = p.parent {
+			if p.maxGap.Get() >= max {
+
+				break
+			}
+
+			p.maxGap.Set(max)
+		}
+		return
+	}
+
+	for p := n.parent; p != nil; p = p.parent {
+		if p.maxGap.Get() > oldMax {
+
+			break
+		}
+
+		parentNewMax := p.calculateMaxGapInternal()
+		if p.maxGap.Get() == parentNewMax {
+
+			break
+		}
+
+		p.maxGap.Set(parentNewMax)
+	}
+}
+
+// updateMaxGapLocal updates maxGap of the calling node solely with no
+// propagation to ancestor nodes.
+//
+// Precondition: trackGaps must be 1.
+func (n *FileRangenode) updateMaxGapLocal() {
+	if !n.hasChildren {
+
+		n.maxGap.Set(n.calculateMaxGapLeaf())
+	} else {
+
+		n.maxGap.Set(n.calculateMaxGapInternal())
+	}
+}
+
+// calculateMaxGapLeaf iterates the gaps within a leaf node and calculate the
+// max.
+//
+// Preconditions: n must be a leaf node.
+func (n *FileRangenode) calculateMaxGapLeaf() uint64 {
+	max := FileRangeGapIterator{n, 0}.Range().Length()
+	for i := 1; i <= n.nrSegments; i++ {
+		if current := (FileRangeGapIterator{n, i}).Range().Length(); current > max {
+			max = current
+		}
+	}
+	return max
+}
+
+// calculateMaxGapInternal iterates children's maxGap within an internal node n
+// and calculate the max.
+//
+// Preconditions: n must be a non-leaf node.
+func (n *FileRangenode) calculateMaxGapInternal() uint64 {
+	max := n.children[0].maxGap.Get()
+	for i := 1; i <= n.nrSegments; i++ {
+		if current := n.children[i].maxGap.Get(); current > max {
+			max = current
+		}
+	}
+	return max
+}
+
+// searchFirstLargeEnoughGap returns the first gap having at least minSize length
+// in the subtree rooted by n. If not found, return a terminal gap iterator.
+func (n *FileRangenode) searchFirstLargeEnoughGap(minSize uint64) FileRangeGapIterator {
+	if n.maxGap.Get() < minSize {
+		return FileRangeGapIterator{}
+	}
+	if n.hasChildren {
+		for i := 0; i <= n.nrSegments; i++ {
+			if largeEnoughGap := n.children[i].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		}
+	} else {
+		for i := 0; i <= n.nrSegments; i++ {
+			currentGap := FileRangeGapIterator{n, i}
+			if currentGap.Range().Length() >= minSize {
+				return currentGap
+			}
+		}
+	}
+	panic(fmt.Sprintf("invalid maxGap in %v", n))
+}
+
+// searchLastLargeEnoughGap returns the last gap having at least minSize length
+// in the subtree rooted by n. If not found, return a terminal gap iterator.
+func (n *FileRangenode) searchLastLargeEnoughGap(minSize uint64) FileRangeGapIterator {
+	if n.maxGap.Get() < minSize {
+		return FileRangeGapIterator{}
+	}
+	if n.hasChildren {
+		for i := n.nrSegments; i >= 0; i-- {
+			if largeEnoughGap := n.children[i].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		}
+	} else {
+		for i := n.nrSegments; i >= 0; i-- {
+			currentGap := FileRangeGapIterator{n, i}
+			if currentGap.Range().Length() >= minSize {
+				return currentGap
+			}
+		}
+	}
+	panic(fmt.Sprintf("invalid maxGap in %v", n))
+}
+
 // A Iterator is conceptually one of:
 //
 // - A pointer to a segment in a set; or
@@ -1145,6 +1358,114 @@ func (gap FileRangeGapIterator) NextGap() FileRangeGapIterator {
 	return seg.NextGap()
 }
 
+// NextLargeEnoughGap returns the iterated gap's first next gap with larger
+// length than minSize.  If not found, return a terminal gap iterator (does NOT
+// include this gap itself).
+//
+// Precondition: trackGaps must be 1.
+func (gap FileRangeGapIterator) NextLargeEnoughGap(minSize uint64) FileRangeGapIterator {
+	if FileRangetrackGaps != 1 {
+		panic("set is not tracking gaps")
+	}
+	if gap.node != nil && gap.node.hasChildren && gap.index == gap.node.nrSegments {
+
+		gap.node = gap.NextSegment().node
+		gap.index = 0
+		return gap.nextLargeEnoughGapHelper(minSize)
+	}
+	return gap.nextLargeEnoughGapHelper(minSize)
+}
+
+// nextLargeEnoughGapHelper is the helper function used by NextLargeEnoughGap
+// to do the real recursions.
+//
+// Preconditions: gap is NOT the trailing gap of a non-leaf node.
+func (gap FileRangeGapIterator) nextLargeEnoughGapHelper(minSize uint64) FileRangeGapIterator {
+
+	for gap.node != nil &&
+		(gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == gap.node.nrSegments)) {
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+
+	if gap.node == nil {
+		return FileRangeGapIterator{}
+	}
+
+	gap.index++
+	for gap.index <= gap.node.nrSegments {
+		if gap.node.hasChildren {
+			if largeEnoughGap := gap.node.children[gap.index].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		} else {
+			if gap.Range().Length() >= minSize {
+				return gap
+			}
+		}
+		gap.index++
+	}
+	gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	if gap.node != nil && gap.index == gap.node.nrSegments {
+
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+	return gap.nextLargeEnoughGapHelper(minSize)
+}
+
+// PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or
+// equal length than minSize.  If not found, return a terminal gap iterator
+// (does NOT include this gap itself).
+//
+// Precondition: trackGaps must be 1.
+func (gap FileRangeGapIterator) PrevLargeEnoughGap(minSize uint64) FileRangeGapIterator {
+	if FileRangetrackGaps != 1 {
+		panic("set is not tracking gaps")
+	}
+	if gap.node != nil && gap.node.hasChildren && gap.index == 0 {
+
+		gap.node = gap.PrevSegment().node
+		gap.index = gap.node.nrSegments
+		return gap.prevLargeEnoughGapHelper(minSize)
+	}
+	return gap.prevLargeEnoughGapHelper(minSize)
+}
+
+// prevLargeEnoughGapHelper is the helper function used by PrevLargeEnoughGap
+// to do the real recursions.
+//
+// Preconditions: gap is NOT the first gap of a non-leaf node.
+func (gap FileRangeGapIterator) prevLargeEnoughGapHelper(minSize uint64) FileRangeGapIterator {
+
+	for gap.node != nil &&
+		(gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == 0)) {
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+
+	if gap.node == nil {
+		return FileRangeGapIterator{}
+	}
+
+	gap.index--
+	for gap.index >= 0 {
+		if gap.node.hasChildren {
+			if largeEnoughGap := gap.node.children[gap.index].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		} else {
+			if gap.Range().Length() >= minSize {
+				return gap
+			}
+		}
+		gap.index--
+	}
+	gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	if gap.node != nil && gap.index == 0 {
+
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+	return gap.prevLargeEnoughGapHelper(minSize)
+}
+
 // 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.
@@ -1211,7 +1532,15 @@ func (n *FileRangenode) writeDebugString(buf *bytes.Buffer, prefix string) {
 			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 n.hasChildren {
+			if FileRangetrackGaps != 0 {
+				buf.WriteString(fmt.Sprintf("- % 3d: %v => %v, maxGap: %d\n", i, n.keys[i], n.values[i], n.maxGap.Get()))
+			} else {
+				buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i]))
+			}
+		} else {
+			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))
@@ -1263,6 +1592,46 @@ func (s *FileRangeSet) ImportSortedSlices(sds *FileRangeSegmentDataSlices) error
 	}
 	return nil
 }
+
+// segmentTestCheck returns an error if s is incorrectly sorted, does not
+// contain exactly expectedSegments segments, or contains a segment which
+// fails the passed check.
+//
+// This should be used only for testing, and has been added to this package for
+// templating convenience.
+func (s *FileRangeSet) segmentTestCheck(expectedSegments int, segFunc func(int, __generics_imported0.MappableRange, uint64) error) error {
+	havePrev := false
+	prev := uint64(0)
+	nrSegments := 0
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		next := seg.Start()
+		if havePrev && prev >= next {
+			return fmt.Errorf("incorrect order: key %d (segment %d) >= key %d (segment %d)", prev, nrSegments-1, next, nrSegments)
+		}
+		if segFunc != nil {
+			if err := segFunc(nrSegments, seg.Range(), seg.Value()); err != nil {
+				return err
+			}
+		}
+		prev = next
+		havePrev = true
+		nrSegments++
+	}
+	if nrSegments != expectedSegments {
+		return fmt.Errorf("incorrect number of segments: got %d, wanted %d", nrSegments, expectedSegments)
+	}
+	return nil
+}
+
+// countSegments counts the number of segments in the set.
+//
+// Similar to Check, this should only be used for testing.
+func (s *FileRangeSet) countSegments() (segments int) {
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		segments++
+	}
+	return segments
+}
 func (s *FileRangeSet) saveRoot() *FileRangeSegmentDataSlices {
 	return s.ExportSortedSlices()
 }
diff --git a/pkg/sentry/fs/fsutil/frame_ref_set.go b/pkg/sentry/fs/fsutil/frame_ref_set.go
index 6564fd0c6..dd6f5aba6 100644
--- a/pkg/sentry/fs/fsutil/frame_ref_set.go
+++ b/pkg/sentry/fs/fsutil/frame_ref_set.go
@@ -18,6 +18,7 @@ import (
 	"math"
 
 	"gvisor.dev/gvisor/pkg/sentry/platform"
+	"gvisor.dev/gvisor/pkg/sentry/usage"
 )
 
 // FrameRefSetFunctions implements segment.Functions for FrameRefSet.
@@ -49,3 +50,42 @@ func (FrameRefSetFunctions) Merge(_ platform.FileRange, val1 uint64, _ platform.
 func (FrameRefSetFunctions) Split(_ platform.FileRange, val uint64, _ uint64) (uint64, uint64) {
 	return val, val
 }
+
+// IncRefAndAccount adds a reference on the range fr. All newly inserted segments
+// are accounted as host page cache memory mappings.
+func (refs *FrameRefSet) IncRefAndAccount(fr platform.FileRange) {
+	seg, gap := refs.Find(fr.Start)
+	for {
+		switch {
+		case seg.Ok() && seg.Start() < fr.End:
+			seg = refs.Isolate(seg, fr)
+			seg.SetValue(seg.Value() + 1)
+			seg, gap = seg.NextNonEmpty()
+		case gap.Ok() && gap.Start() < fr.End:
+			newRange := gap.Range().Intersect(fr)
+			usage.MemoryAccounting.Inc(newRange.Length(), usage.Mapped)
+			seg, gap = refs.InsertWithoutMerging(gap, newRange, 1).NextNonEmpty()
+		default:
+			refs.MergeAdjacent(fr)
+			return
+		}
+	}
+}
+
+// DecRefAndAccount removes a reference on the range fr and untracks segments
+// that are removed from memory accounting.
+func (refs *FrameRefSet) DecRefAndAccount(fr platform.FileRange) {
+	seg := refs.FindSegment(fr.Start)
+
+	for seg.Ok() && seg.Start() < fr.End {
+		seg = refs.Isolate(seg, fr)
+		if old := seg.Value(); old == 1 {
+			usage.MemoryAccounting.Dec(seg.Range().Length(), usage.Mapped)
+			seg = refs.Remove(seg).NextSegment()
+		} else {
+			seg.SetValue(old - 1)
+			seg = seg.NextSegment()
+		}
+	}
+	refs.MergeAdjacent(fr)
+}
diff --git a/pkg/sentry/fs/fsutil/frame_ref_set_impl.go b/pkg/sentry/fs/fsutil/frame_ref_set_impl.go
index 88695dbd1..413b037d1 100755..100644
--- a/pkg/sentry/fs/fsutil/frame_ref_set_impl.go
+++ b/pkg/sentry/fs/fsutil/frame_ref_set_impl.go
@@ -9,6 +9,34 @@ import (
 	"fmt"
 )
 
+// trackGaps is an optional parameter.
+//
+// If trackGaps is 1, the Set will track maximum gap size recursively,
+// enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this
+// case, Key must be an unsigned integer.
+//
+// trackGaps must be 0 or 1.
+const FrameReftrackGaps = 0
+
+var _ = uint8(FrameReftrackGaps << 7) // Will fail if not zero or one.
+
+// dynamicGap is a type that disappears if trackGaps is 0.
+type FrameRefdynamicGap [FrameReftrackGaps]uint64
+
+// Get returns the value of the gap.
+//
+// Precondition: trackGaps must be non-zero.
+func (d *FrameRefdynamicGap) Get() uint64 {
+	return d[:][0]
+}
+
+// Set sets the value of the gap.
+//
+// Precondition: trackGaps must be non-zero.
+func (d *FrameRefdynamicGap) Set(v uint64) {
+	d[:][0] = v
+}
+
 const (
 	// minDegree is the minimum degree of an internal node in a Set B-tree.
 	//
@@ -267,8 +295,12 @@ func (s *FrameRefSet) Insert(gap FrameRefGapIterator, r __generics_imported0.Fil
 	}
 	if prev.Ok() && prev.End() == r.Start {
 		if mval, ok := (FrameRefSetFunctions{}).Merge(prev.Range(), prev.Value(), r, val); ok {
+			shrinkMaxGap := FrameReftrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
 			prev.SetEndUnchecked(r.End)
 			prev.SetValue(mval)
+			if shrinkMaxGap {
+				gap.node.updateMaxGapLeaf()
+			}
 			if next.Ok() && next.Start() == r.End {
 				val = mval
 				if mval, ok := (FrameRefSetFunctions{}).Merge(prev.Range(), val, next.Range(), next.Value()); ok {
@@ -282,11 +314,16 @@ func (s *FrameRefSet) Insert(gap FrameRefGapIterator, r __generics_imported0.Fil
 	}
 	if next.Ok() && next.Start() == r.End {
 		if mval, ok := (FrameRefSetFunctions{}).Merge(r, val, next.Range(), next.Value()); ok {
+			shrinkMaxGap := FrameReftrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
 			next.SetStartUnchecked(r.Start)
 			next.SetValue(mval)
+			if shrinkMaxGap {
+				gap.node.updateMaxGapLeaf()
+			}
 			return next
 		}
 	}
+
 	return s.InsertWithoutMergingUnchecked(gap, r, val)
 }
 
@@ -313,11 +350,15 @@ func (s *FrameRefSet) InsertWithoutMerging(gap FrameRefGapIterator, r __generics
 // Preconditions: r.Start >= gap.Start(); r.End <= gap.End().
 func (s *FrameRefSet) InsertWithoutMergingUnchecked(gap FrameRefGapIterator, r __generics_imported0.FileRange, val uint64) FrameRefIterator {
 	gap = gap.node.rebalanceBeforeInsert(gap)
+	splitMaxGap := FrameReftrackGaps != 0 && (gap.node.nrSegments == 0 || gap.Range().Length() == gap.node.maxGap.Get())
 	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++
+	if splitMaxGap {
+		gap.node.updateMaxGapLeaf()
+	}
 	return FrameRefIterator{gap.node, gap.index}
 }
 
@@ -332,12 +373,20 @@ func (s *FrameRefSet) Remove(seg FrameRefIterator) FrameRefGapIterator {
 
 		seg.SetRangeUnchecked(victim.Range())
 		seg.SetValue(victim.Value())
+
+		nextAdjacentNode := seg.NextSegment().node
+		if FrameReftrackGaps != 0 {
+			nextAdjacentNode.updateMaxGapLeaf()
+		}
 		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])
 	FrameRefSetFunctions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1])
 	seg.node.nrSegments--
+	if FrameReftrackGaps != 0 {
+		seg.node.updateMaxGapLeaf()
+	}
 	return seg.node.rebalanceAfterRemove(FrameRefGapIterator{seg.node, seg.index})
 }
 
@@ -387,6 +436,7 @@ func (s *FrameRefSet) MergeUnchecked(first, second FrameRefIterator) FrameRefIte
 
 			first.SetEndUnchecked(second.End())
 			first.SetValue(mval)
+
 			return s.Remove(second).PrevSegment()
 		}
 	}
@@ -562,6 +612,12 @@ type FrameRefnode struct {
 	// than "isLeaf" because false must be the correct value for an empty root.
 	hasChildren bool
 
+	// The longest gap within this node. If the node is a leaf, it's simply the
+	// maximum gap among all the (nrSegments+1) gaps formed by its nrSegments keys
+	// including the 0th and nrSegments-th gap possibly shared with its upper-level
+	// nodes; if it's a non-leaf node, it's the max of all children's maxGap.
+	maxGap FrameRefdynamicGap
+
 	// Nodes store keys and values in separate arrays to maximize locality in
 	// the common case (scanning keys for lookup).
 	keys     [FrameRefmaxDegree - 1]__generics_imported0.FileRange
@@ -607,12 +663,12 @@ func (n *FrameRefnode) nextSibling() *FrameRefnode {
 // required for insertion, and returns an updated iterator to the position
 // represented by gap.
 func (n *FrameRefnode) rebalanceBeforeInsert(gap FrameRefGapIterator) FrameRefGapIterator {
-	if n.parent != nil {
-		gap = n.parent.rebalanceBeforeInsert(gap)
-	}
 	if n.nrSegments < FrameRefmaxDegree-1 {
 		return gap
 	}
+	if n.parent != nil {
+		gap = n.parent.rebalanceBeforeInsert(gap)
+	}
 	if n.parent == nil {
 
 		left := &FrameRefnode{
@@ -648,6 +704,11 @@ func (n *FrameRefnode) rebalanceBeforeInsert(gap FrameRefGapIterator) FrameRefGa
 		n.hasChildren = true
 		n.children[0] = left
 		n.children[1] = right
+
+		if FrameReftrackGaps != 0 {
+			left.updateMaxGapLocal()
+			right.updateMaxGapLocal()
+		}
 		if gap.node != n {
 			return gap
 		}
@@ -685,6 +746,11 @@ func (n *FrameRefnode) rebalanceBeforeInsert(gap FrameRefGapIterator) FrameRefGa
 	}
 	n.nrSegments = FrameRefminDegree - 1
 
+	if FrameReftrackGaps != 0 {
+		n.updateMaxGapLocal()
+		sibling.updateMaxGapLocal()
+	}
+
 	if gap.node != n {
 		return gap
 	}
@@ -730,6 +796,11 @@ func (n *FrameRefnode) rebalanceAfterRemove(gap FrameRefGapIterator) FrameRefGap
 			}
 			n.nrSegments++
 			sibling.nrSegments--
+
+			if FrameReftrackGaps != 0 {
+				n.updateMaxGapLocal()
+				sibling.updateMaxGapLocal()
+			}
 			if gap.node == sibling && gap.index == sibling.nrSegments {
 				return FrameRefGapIterator{n, 0}
 			}
@@ -758,6 +829,11 @@ func (n *FrameRefnode) rebalanceAfterRemove(gap FrameRefGapIterator) FrameRefGap
 			}
 			n.nrSegments++
 			sibling.nrSegments--
+
+			if FrameReftrackGaps != 0 {
+				n.updateMaxGapLocal()
+				sibling.updateMaxGapLocal()
+			}
 			if gap.node == sibling {
 				if gap.index == 0 {
 					return FrameRefGapIterator{n, n.nrSegments}
@@ -790,6 +866,7 @@ func (n *FrameRefnode) rebalanceAfterRemove(gap FrameRefGapIterator) FrameRefGap
 				p.children[0] = nil
 				p.children[1] = nil
 			}
+
 			if gap.node == left {
 				return FrameRefGapIterator{p, gap.index}
 			}
@@ -836,10 +913,146 @@ func (n *FrameRefnode) rebalanceAfterRemove(gap FrameRefGapIterator) FrameRefGap
 		p.children[p.nrSegments] = nil
 		p.nrSegments--
 
+		if FrameReftrackGaps != 0 {
+			left.updateMaxGapLocal()
+		}
+
 		n = p
 	}
 }
 
+// updateMaxGapLeaf updates maxGap bottom-up from the calling leaf until no
+// necessary update.
+//
+// Preconditions: n must be a leaf node, trackGaps must be 1.
+func (n *FrameRefnode) updateMaxGapLeaf() {
+	if n.hasChildren {
+		panic(fmt.Sprintf("updateMaxGapLeaf should always be called on leaf node: %v", n))
+	}
+	max := n.calculateMaxGapLeaf()
+	if max == n.maxGap.Get() {
+
+		return
+	}
+	oldMax := n.maxGap.Get()
+	n.maxGap.Set(max)
+	if max > oldMax {
+
+		for p := n.parent; p != nil; p = p.parent {
+			if p.maxGap.Get() >= max {
+
+				break
+			}
+
+			p.maxGap.Set(max)
+		}
+		return
+	}
+
+	for p := n.parent; p != nil; p = p.parent {
+		if p.maxGap.Get() > oldMax {
+
+			break
+		}
+
+		parentNewMax := p.calculateMaxGapInternal()
+		if p.maxGap.Get() == parentNewMax {
+
+			break
+		}
+
+		p.maxGap.Set(parentNewMax)
+	}
+}
+
+// updateMaxGapLocal updates maxGap of the calling node solely with no
+// propagation to ancestor nodes.
+//
+// Precondition: trackGaps must be 1.
+func (n *FrameRefnode) updateMaxGapLocal() {
+	if !n.hasChildren {
+
+		n.maxGap.Set(n.calculateMaxGapLeaf())
+	} else {
+
+		n.maxGap.Set(n.calculateMaxGapInternal())
+	}
+}
+
+// calculateMaxGapLeaf iterates the gaps within a leaf node and calculate the
+// max.
+//
+// Preconditions: n must be a leaf node.
+func (n *FrameRefnode) calculateMaxGapLeaf() uint64 {
+	max := FrameRefGapIterator{n, 0}.Range().Length()
+	for i := 1; i <= n.nrSegments; i++ {
+		if current := (FrameRefGapIterator{n, i}).Range().Length(); current > max {
+			max = current
+		}
+	}
+	return max
+}
+
+// calculateMaxGapInternal iterates children's maxGap within an internal node n
+// and calculate the max.
+//
+// Preconditions: n must be a non-leaf node.
+func (n *FrameRefnode) calculateMaxGapInternal() uint64 {
+	max := n.children[0].maxGap.Get()
+	for i := 1; i <= n.nrSegments; i++ {
+		if current := n.children[i].maxGap.Get(); current > max {
+			max = current
+		}
+	}
+	return max
+}
+
+// searchFirstLargeEnoughGap returns the first gap having at least minSize length
+// in the subtree rooted by n. If not found, return a terminal gap iterator.
+func (n *FrameRefnode) searchFirstLargeEnoughGap(minSize uint64) FrameRefGapIterator {
+	if n.maxGap.Get() < minSize {
+		return FrameRefGapIterator{}
+	}
+	if n.hasChildren {
+		for i := 0; i <= n.nrSegments; i++ {
+			if largeEnoughGap := n.children[i].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		}
+	} else {
+		for i := 0; i <= n.nrSegments; i++ {
+			currentGap := FrameRefGapIterator{n, i}
+			if currentGap.Range().Length() >= minSize {
+				return currentGap
+			}
+		}
+	}
+	panic(fmt.Sprintf("invalid maxGap in %v", n))
+}
+
+// searchLastLargeEnoughGap returns the last gap having at least minSize length
+// in the subtree rooted by n. If not found, return a terminal gap iterator.
+func (n *FrameRefnode) searchLastLargeEnoughGap(minSize uint64) FrameRefGapIterator {
+	if n.maxGap.Get() < minSize {
+		return FrameRefGapIterator{}
+	}
+	if n.hasChildren {
+		for i := n.nrSegments; i >= 0; i-- {
+			if largeEnoughGap := n.children[i].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		}
+	} else {
+		for i := n.nrSegments; i >= 0; i-- {
+			currentGap := FrameRefGapIterator{n, i}
+			if currentGap.Range().Length() >= minSize {
+				return currentGap
+			}
+		}
+	}
+	panic(fmt.Sprintf("invalid maxGap in %v", n))
+}
+
 // A Iterator is conceptually one of:
 //
 // - A pointer to a segment in a set; or
@@ -1145,6 +1358,114 @@ func (gap FrameRefGapIterator) NextGap() FrameRefGapIterator {
 	return seg.NextGap()
 }
 
+// NextLargeEnoughGap returns the iterated gap's first next gap with larger
+// length than minSize.  If not found, return a terminal gap iterator (does NOT
+// include this gap itself).
+//
+// Precondition: trackGaps must be 1.
+func (gap FrameRefGapIterator) NextLargeEnoughGap(minSize uint64) FrameRefGapIterator {
+	if FrameReftrackGaps != 1 {
+		panic("set is not tracking gaps")
+	}
+	if gap.node != nil && gap.node.hasChildren && gap.index == gap.node.nrSegments {
+
+		gap.node = gap.NextSegment().node
+		gap.index = 0
+		return gap.nextLargeEnoughGapHelper(minSize)
+	}
+	return gap.nextLargeEnoughGapHelper(minSize)
+}
+
+// nextLargeEnoughGapHelper is the helper function used by NextLargeEnoughGap
+// to do the real recursions.
+//
+// Preconditions: gap is NOT the trailing gap of a non-leaf node.
+func (gap FrameRefGapIterator) nextLargeEnoughGapHelper(minSize uint64) FrameRefGapIterator {
+
+	for gap.node != nil &&
+		(gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == gap.node.nrSegments)) {
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+
+	if gap.node == nil {
+		return FrameRefGapIterator{}
+	}
+
+	gap.index++
+	for gap.index <= gap.node.nrSegments {
+		if gap.node.hasChildren {
+			if largeEnoughGap := gap.node.children[gap.index].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		} else {
+			if gap.Range().Length() >= minSize {
+				return gap
+			}
+		}
+		gap.index++
+	}
+	gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	if gap.node != nil && gap.index == gap.node.nrSegments {
+
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+	return gap.nextLargeEnoughGapHelper(minSize)
+}
+
+// PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or
+// equal length than minSize.  If not found, return a terminal gap iterator
+// (does NOT include this gap itself).
+//
+// Precondition: trackGaps must be 1.
+func (gap FrameRefGapIterator) PrevLargeEnoughGap(minSize uint64) FrameRefGapIterator {
+	if FrameReftrackGaps != 1 {
+		panic("set is not tracking gaps")
+	}
+	if gap.node != nil && gap.node.hasChildren && gap.index == 0 {
+
+		gap.node = gap.PrevSegment().node
+		gap.index = gap.node.nrSegments
+		return gap.prevLargeEnoughGapHelper(minSize)
+	}
+	return gap.prevLargeEnoughGapHelper(minSize)
+}
+
+// prevLargeEnoughGapHelper is the helper function used by PrevLargeEnoughGap
+// to do the real recursions.
+//
+// Preconditions: gap is NOT the first gap of a non-leaf node.
+func (gap FrameRefGapIterator) prevLargeEnoughGapHelper(minSize uint64) FrameRefGapIterator {
+
+	for gap.node != nil &&
+		(gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == 0)) {
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+
+	if gap.node == nil {
+		return FrameRefGapIterator{}
+	}
+
+	gap.index--
+	for gap.index >= 0 {
+		if gap.node.hasChildren {
+			if largeEnoughGap := gap.node.children[gap.index].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
+				return largeEnoughGap
+			}
+		} else {
+			if gap.Range().Length() >= minSize {
+				return gap
+			}
+		}
+		gap.index--
+	}
+	gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	if gap.node != nil && gap.index == 0 {
+
+		gap.node, gap.index = gap.node.parent, gap.node.parentIndex
+	}
+	return gap.prevLargeEnoughGapHelper(minSize)
+}
+
 // 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.
@@ -1211,7 +1532,15 @@ func (n *FrameRefnode) writeDebugString(buf *bytes.Buffer, prefix string) {
 			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 n.hasChildren {
+			if FrameReftrackGaps != 0 {
+				buf.WriteString(fmt.Sprintf("- % 3d: %v => %v, maxGap: %d\n", i, n.keys[i], n.values[i], n.maxGap.Get()))
+			} else {
+				buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i]))
+			}
+		} else {
+			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))
@@ -1263,6 +1592,46 @@ func (s *FrameRefSet) ImportSortedSlices(sds *FrameRefSegmentDataSlices) error {
 	}
 	return nil
 }
+
+// segmentTestCheck returns an error if s is incorrectly sorted, does not
+// contain exactly expectedSegments segments, or contains a segment which
+// fails the passed check.
+//
+// This should be used only for testing, and has been added to this package for
+// templating convenience.
+func (s *FrameRefSet) segmentTestCheck(expectedSegments int, segFunc func(int, __generics_imported0.FileRange, uint64) error) error {
+	havePrev := false
+	prev := uint64(0)
+	nrSegments := 0
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		next := seg.Start()
+		if havePrev && prev >= next {
+			return fmt.Errorf("incorrect order: key %d (segment %d) >= key %d (segment %d)", prev, nrSegments-1, next, nrSegments)
+		}
+		if segFunc != nil {
+			if err := segFunc(nrSegments, seg.Range(), seg.Value()); err != nil {
+				return err
+			}
+		}
+		prev = next
+		havePrev = true
+		nrSegments++
+	}
+	if nrSegments != expectedSegments {
+		return fmt.Errorf("incorrect number of segments: got %d, wanted %d", nrSegments, expectedSegments)
+	}
+	return nil
+}
+
+// countSegments counts the number of segments in the set.
+//
+// Similar to Check, this should only be used for testing.
+func (s *FrameRefSet) countSegments() (segments int) {
+	for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
+		segments++
+	}
+	return segments
+}
 func (s *FrameRefSet) saveRoot() *FrameRefSegmentDataSlices {
 	return s.ExportSortedSlices()
 }
diff --git a/pkg/sentry/fs/fsutil/fsutil_impl_state_autogen.go b/pkg/sentry/fs/fsutil/fsutil_impl_state_autogen.go
index a0baca0c5..79d4610f0 100755..100644
--- a/pkg/sentry/fs/fsutil/fsutil_impl_state_autogen.go
+++ b/pkg/sentry/fs/fsutil/fsutil_impl_state_autogen.go
@@ -25,6 +25,7 @@ func (x *Dirtynode) save(m state.Map) {
 	m.Save("parent", &x.parent)
 	m.Save("parentIndex", &x.parentIndex)
 	m.Save("hasChildren", &x.hasChildren)
+	m.Save("maxGap", &x.maxGap)
 	m.Save("keys", &x.keys)
 	m.Save("values", &x.values)
 	m.Save("children", &x.children)
@@ -36,6 +37,7 @@ func (x *Dirtynode) load(m state.Map) {
 	m.Load("parent", &x.parent)
 	m.Load("parentIndex", &x.parentIndex)
 	m.Load("hasChildren", &x.hasChildren)
+	m.Load("maxGap", &x.maxGap)
 	m.Load("keys", &x.keys)
 	m.Load("values", &x.values)
 	m.Load("children", &x.children)
@@ -75,6 +77,7 @@ func (x *FileRangenode) save(m state.Map) {
 	m.Save("parent", &x.parent)
 	m.Save("parentIndex", &x.parentIndex)
 	m.Save("hasChildren", &x.hasChildren)
+	m.Save("maxGap", &x.maxGap)
 	m.Save("keys", &x.keys)
 	m.Save("values", &x.values)
 	m.Save("children", &x.children)
@@ -86,6 +89,7 @@ func (x *FileRangenode) load(m state.Map) {
 	m.Load("parent", &x.parent)
 	m.Load("parentIndex", &x.parentIndex)
 	m.Load("hasChildren", &x.hasChildren)
+	m.Load("maxGap", &x.maxGap)
 	m.Load("keys", &x.keys)
 	m.Load("values", &x.values)
 	m.Load("children", &x.children)
@@ -125,6 +129,7 @@ func (x *FrameRefnode) save(m state.Map) {
 	m.Save("parent", &x.parent)
 	m.Save("parentIndex", &x.parentIndex)
 	m.Save("hasChildren", &x.hasChildren)
+	m.Save("maxGap", &x.maxGap)
 	m.Save("keys", &x.keys)
 	m.Save("values", &x.values)
 	m.Save("children", &x.children)
@@ -136,6 +141,7 @@ func (x *FrameRefnode) load(m state.Map) {
 	m.Load("parent", &x.parent)
 	m.Load("parentIndex", &x.parentIndex)
 	m.Load("hasChildren", &x.hasChildren)
+	m.Load("maxGap", &x.maxGap)
 	m.Load("keys", &x.keys)
 	m.Load("values", &x.values)
 	m.Load("children", &x.children)
diff --git a/pkg/sentry/fs/fsutil/fsutil_state_autogen.go b/pkg/sentry/fs/fsutil/fsutil_state_autogen.go
index 80b93ad25..80b93ad25 100755..100644
--- a/pkg/sentry/fs/fsutil/fsutil_state_autogen.go
+++ b/pkg/sentry/fs/fsutil/fsutil_state_autogen.go
diff --git a/pkg/sentry/fs/fsutil/fsutil_unsafe_state_autogen.go b/pkg/sentry/fs/fsutil/fsutil_unsafe_state_autogen.go
index 00b0994f6..00b0994f6 100755..100644
--- a/pkg/sentry/fs/fsutil/fsutil_unsafe_state_autogen.go
+++ b/pkg/sentry/fs/fsutil/fsutil_unsafe_state_autogen.go