From 14d06064d26b1cd9e2ccad08ebe997e704092eb8 Mon Sep 17 00:00:00 2001 From: Michael Pratt Date: Mon, 16 Jul 2018 18:18:06 -0700 Subject: Start allocation and reclaim scans only where they may find a match If usageSet is heavily fragmented, findUnallocatedRange and findReclaimable can spend excessive cycles linearly scanning the set for unallocated/free pages. Improve common cases by beginning the scan only at the first page that could possibly contain an unallocated/free page. This metadata only guarantees that there is no lower unallocated/free page, but a scan may still be required (especially for multi-page allocations). That said, this heuristic can still provide significant performance improvements for certain applications. PiperOrigin-RevId: 204841833 Change-Id: Ic41ad33bf9537ecd673a6f5852ab353bf63ea1e6 --- pkg/sentry/platform/filemem/filemem_test.go | 106 ++++++++++++++++++++-------- 1 file changed, 76 insertions(+), 30 deletions(-) (limited to 'pkg/sentry/platform/filemem/filemem_test.go') diff --git a/pkg/sentry/platform/filemem/filemem_test.go b/pkg/sentry/platform/filemem/filemem_test.go index 46ffcf116..4b165dc48 100644 --- a/pkg/sentry/platform/filemem/filemem_test.go +++ b/pkg/sentry/platform/filemem/filemem_test.go @@ -27,18 +27,22 @@ const ( func TestFindUnallocatedRange(t *testing.T) { for _, test := range []struct { - desc string - usage *usageSegmentDataSlices - length uint64 - alignment uint64 - start uint64 + desc string + usage *usageSegmentDataSlices + start uint64 + length uint64 + alignment uint64 + unallocated uint64 + minUnallocated uint64 }{ { - desc: "Initial allocation succeeds", - usage: &usageSegmentDataSlices{}, - length: page, - alignment: page, - start: 0, + desc: "Initial allocation succeeds", + usage: &usageSegmentDataSlices{}, + start: 0, + length: page, + alignment: page, + unallocated: 0, + minUnallocated: 0, }, { desc: "Allocation begins at start of file", @@ -47,9 +51,11 @@ func TestFindUnallocatedRange(t *testing.T) { End: []uint64{2 * page}, Values: []usageInfo{{refs: 1}}, }, - length: page, - alignment: page, - start: 0, + start: 0, + length: page, + alignment: page, + unallocated: 0, + minUnallocated: 0, }, { desc: "In-use frames are not allocatable", @@ -58,9 +64,11 @@ func TestFindUnallocatedRange(t *testing.T) { End: []uint64{page, 2 * page}, Values: []usageInfo{{refs: 1}, {refs: 2}}, }, - length: page, - alignment: page, - start: 2 * page, + start: 0, + length: page, + alignment: page, + unallocated: 2 * page, + minUnallocated: 2 * page, }, { desc: "Reclaimable frames are not allocatable", @@ -69,9 +77,11 @@ func TestFindUnallocatedRange(t *testing.T) { End: []uint64{page, 2 * page, 3 * page}, Values: []usageInfo{{refs: 1}, {refs: 0}, {refs: 1}}, }, - length: page, - alignment: page, - start: 3 * page, + start: 0, + length: page, + alignment: page, + unallocated: 3 * page, + minUnallocated: 3 * page, }, { desc: "Gaps between in-use frames are allocatable", @@ -80,9 +90,11 @@ func TestFindUnallocatedRange(t *testing.T) { End: []uint64{page, 3 * page}, Values: []usageInfo{{refs: 1}, {refs: 1}}, }, - length: page, - alignment: page, - start: page, + start: 0, + length: page, + alignment: page, + unallocated: page, + minUnallocated: page, }, { desc: "Inadequately-sized gaps are rejected", @@ -91,9 +103,11 @@ func TestFindUnallocatedRange(t *testing.T) { End: []uint64{page, 3 * page}, Values: []usageInfo{{refs: 1}, {refs: 1}}, }, - length: 2 * page, - alignment: page, - start: 3 * page, + start: 0, + length: 2 * page, + alignment: page, + unallocated: 3 * page, + minUnallocated: page, }, { desc: "Hugepage alignment is honored", @@ -104,9 +118,37 @@ func TestFindUnallocatedRange(t *testing.T) { End: []uint64{page, hugepage + 2*page}, Values: []usageInfo{{refs: 1}, {refs: 1}}, }, - length: hugepage, - alignment: hugepage, - start: 2 * hugepage, + start: 0, + length: hugepage, + alignment: hugepage, + unallocated: 2 * hugepage, + minUnallocated: page, + }, + { + desc: "Pages before start ignored", + usage: &usageSegmentDataSlices{ + Start: []uint64{page, 3 * page}, + End: []uint64{2 * page, 4 * page}, + Values: []usageInfo{{refs: 1}, {refs: 2}}, + }, + start: page, + length: page, + alignment: page, + unallocated: 2 * page, + minUnallocated: 2 * page, + }, + { + desc: "start may be in the middle of segment", + usage: &usageSegmentDataSlices{ + Start: []uint64{0, 3 * page}, + End: []uint64{2 * page, 4 * page}, + Values: []usageInfo{{refs: 1}, {refs: 2}}, + }, + start: page, + length: page, + alignment: page, + unallocated: 2 * page, + minUnallocated: 2 * page, }, } { t.Run(test.desc, func(t *testing.T) { @@ -114,8 +156,12 @@ func TestFindUnallocatedRange(t *testing.T) { if err := usage.ImportSortedSlices(test.usage); err != nil { t.Fatalf("Failed to initialize usage from %v: %v", test.usage, err) } - if got, want := findUnallocatedRange(&usage, test.length, test.alignment), test.start; got != want { - t.Errorf("findUnallocatedRange(%v, %d, %d): got %d, wanted %d", test.usage, test.length, test.alignment, got, want) + unallocated, minUnallocated := findUnallocatedRange(&usage, test.start, test.length, test.alignment) + if unallocated != test.unallocated { + t.Errorf("findUnallocatedRange(%v, %x, %x, %x): got unallocated %x, wanted %x", test.usage, test.start, test.length, test.alignment, unallocated, test.unallocated) + } + if minUnallocated != test.minUnallocated { + t.Errorf("findUnallocatedRange(%v, %x, %x, %x): got minUnallocated %x, wanted %x", test.usage, test.start, test.length, test.alignment, minUnallocated, test.minUnallocated) } }) } -- cgit v1.2.3