From e61acfb5eaec4450587116573f708284a0fe7849 Mon Sep 17 00:00:00 2001
From: Jamie Liu <jamieliu@google.com>
Date: Tue, 16 Jun 2020 16:14:26 -0700
Subject: Correctly handle multiple resizings in pgalloc.findAvailableRange().

PiperOrigin-RevId: 316778032
---
 pkg/sentry/pgalloc/pgalloc.go      | 60 +++++++++++++++++++++-----------------
 pkg/sentry/pgalloc/pgalloc_test.go |  8 +++++
 2 files changed, 42 insertions(+), 26 deletions(-)

(limited to 'pkg')

diff --git a/pkg/sentry/pgalloc/pgalloc.go b/pkg/sentry/pgalloc/pgalloc.go
index 46f19d218..afab97c0a 100644
--- a/pkg/sentry/pgalloc/pgalloc.go
+++ b/pkg/sentry/pgalloc/pgalloc.go
@@ -441,53 +441,61 @@ func (f *MemoryFile) Allocate(length uint64, kind usage.MemoryKind) (platform.Fi
 // Precondition: alignment must be a power of 2.
 func findAvailableRange(usage *usageSet, fileSize int64, length, alignment uint64) (platform.FileRange, bool) {
 	alignmentMask := alignment - 1
-	for gap := usage.UpperBoundGap(uint64(fileSize)); gap.Ok(); gap = gap.PrevLargeEnoughGap(length) {
-		// Start searching only at end of file.
+
+	// Search for space in existing gaps, starting at the current end of the
+	// file and working backward.
+	lastGap := usage.LastGap()
+	gap := lastGap
+	for {
 		end := gap.End()
 		if end > uint64(fileSize) {
 			end = uint64(fileSize)
 		}
 
-		// Start at the top and align downwards.
-		start := end - length
-		if start > end {
-			break // Underflow.
+		// Try to allocate from the end of this gap, with the start of the
+		// allocated range aligned down to alignment.
+		unalignedStart := end - length
+		if unalignedStart > end {
+			// Negative overflow: this and all preceding gaps are too small to
+			// accommodate length.
+			break
 		}
-		start &^= alignmentMask
-
-		// Is the gap still sufficient?
-		if start < gap.Start() {
-			continue
+		if start := unalignedStart &^ alignmentMask; start >= gap.Start() {
+			return platform.FileRange{start, start + length}, true
 		}
 
-		// Allocate in the given gap.
-		return platform.FileRange{start, start + length}, true
+		gap = gap.PrevLargeEnoughGap(length)
+		if !gap.Ok() {
+			break
+		}
 	}
 
 	// Check that it's possible to fit this allocation at the end of a file of any size.
-	min := usage.LastGap().Start()
+	min := lastGap.Start()
 	min = (min + alignmentMask) &^ alignmentMask
 	if min+length < min {
-		// Overflow.
+		// Overflow: allocation would exceed the range of uint64.
 		return platform.FileRange{}, false
 	}
 
 	// Determine the minimum file size required to fit this allocation at its end.
 	for {
-		if fileSize >= 2*fileSize {
-			// Is this because it's initially empty?
-			if fileSize == 0 {
-				fileSize += chunkSize
-			} else {
-				// fileSize overflow.
+		newFileSize := 2 * fileSize
+		if newFileSize <= fileSize {
+			if fileSize != 0 {
+				// Overflow: allocation would exceed the range of int64.
 				return platform.FileRange{}, false
 			}
-		} else {
-			// Double the current fileSize.
-			fileSize *= 2
+			newFileSize = chunkSize
+		}
+		fileSize = newFileSize
+
+		unalignedStart := uint64(fileSize) - length
+		if unalignedStart > uint64(fileSize) {
+			// Negative overflow: fileSize is still inadequate.
+			continue
 		}
-		start := (uint64(fileSize) - length) &^ alignmentMask
-		if start >= min {
+		if start := unalignedStart &^ alignmentMask; start >= min {
 			return platform.FileRange{start, start + length}, true
 		}
 	}
diff --git a/pkg/sentry/pgalloc/pgalloc_test.go b/pkg/sentry/pgalloc/pgalloc_test.go
index b5b68eb52..405db141f 100644
--- a/pkg/sentry/pgalloc/pgalloc_test.go
+++ b/pkg/sentry/pgalloc/pgalloc_test.go
@@ -142,6 +142,14 @@ func TestFindUnallocatedRange(t *testing.T) {
 			alignment: hugepage,
 			start:     hugepage,
 		},
+		{
+			desc:      "Allocation doubles file size more than once if necessary",
+			usage:     &usageSegmentDataSlices{},
+			fileSize:  page,
+			length:    4 * page,
+			alignment: page,
+			start:     0,
+		},
 		{
 			desc: "Allocations are compact if possible",
 			usage: &usageSegmentDataSlices{
-- 
cgit v1.2.3