// Copyright 2019 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package runtime_test

import (
	"fmt"
	"math/rand"
	. "runtime"
	"testing"
)

// makePallocData produces an initialized PallocData by setting
// the ranges of described in alloc and scavenge.
func makePallocData(alloc, scavenged []BitRange) *PallocData {
	b := new(PallocData)
	for _, v := range alloc {
		if v.N == 0 {
			// Skip N==0. It's harmless and allocRange doesn't
			// handle this case.
			continue
		}
		b.AllocRange(v.I, v.N)
	}
	for _, v := range scavenged {
		if v.N == 0 {
			// See the previous loop.
			continue
		}
		b.ScavengedSetRange(v.I, v.N)
	}
	return b
}

func TestFillAligned(t *testing.T) {
	fillAlignedSlow := func(x uint64, m uint) uint64 {
		if m == 1 {
			return x
		}
		out := uint64(0)
		for i := uint(0); i < 64; i += m {
			for j := uint(0); j < m; j++ {
				if x&(uint64(1)<<(i+j)) != 0 {
					out |= ((uint64(1) << m) - 1) << i
					break
				}
			}
		}
		return out
	}
	check := func(x uint64, m uint) {
		want := fillAlignedSlow(x, m)
		if got := FillAligned(x, m); got != want {
			t.Logf("got:  %064b", got)
			t.Logf("want: %064b", want)
			t.Errorf("bad fillAligned(%016x, %d)", x, m)
		}
	}
	for m := uint(1); m <= 64; m *= 2 {
		tests := []uint64{
			0x0000000000000000,
			0x00000000ffffffff,
			0xffffffff00000000,
			0x8000000000000001,
			0xf00000000000000f,
			0xf00000010050000f,
			0xffffffffffffffff,
			0x0000000000000001,
			0x0000000000000002,
			0x0000000000000008,
			uint64(1) << (m - 1),
			uint64(1) << m,
			// Try a few fixed arbitrary examples.
			0xb02b9effcf137016,
			0x3975a076a9fbff18,
			0x0f8c88ec3b81506e,
			0x60f14d80ef2fa0e6,
		}
		for _, test := range tests {
			check(test, m)
		}
		for i := 0; i < 1000; i++ {
			// Try a pseudo-random numbers.
			check(rand.Uint64(), m)

			if m > 1 {
				// For m != 1, let's construct a slightly more interesting
				// random test. Generate a bitmap which is either 0 or
				// randomly set bits for each m-aligned group of m bits.
				val := uint64(0)
				for n := uint(0); n < 64; n += m {
					// For each group of m bits, flip a coin:
					// * Leave them as zero.
					// * Set them randomly.
					if rand.Uint64()%2 == 0 {
						val |= (rand.Uint64() & ((1 << m) - 1)) << n
					}
				}
				check(val, m)
			}
		}
	}
}

func TestPallocDataFindScavengeCandidate(t *testing.T) {
	type test struct {
		alloc, scavenged []BitRange
		min, max         uintptr
		want             BitRange
	}
	tests := map[string]test{
		"MixedMin1": {
			alloc:     []BitRange{{0, 40}, {42, PallocChunkPages - 42}},
			scavenged: []BitRange{{0, 41}, {42, PallocChunkPages - 42}},
			min:       1,
			max:       PallocChunkPages,
			want:      BitRange{41, 1},
		},
		"MultiMin1": {
			alloc:     []BitRange{{0, 63}, {65, 20}, {87, PallocChunkPages - 87}},
			scavenged: []BitRange{{86, 1}},
			min:       1,
			max:       PallocChunkPages,
			want:      BitRange{85, 1},
		},
	}
	// Try out different page minimums.
	for m := uintptr(1); m <= 64; m *= 2 {
		suffix := fmt.Sprintf("Min%d", m)
		tests["AllFree"+suffix] = test{
			min:  m,
			max:  PallocChunkPages,
			want: BitRange{0, PallocChunkPages},
		}
		tests["AllScavenged"+suffix] = test{
			scavenged: []BitRange{{0, PallocChunkPages}},
			min:       m,
			max:       PallocChunkPages,
			want:      BitRange{0, 0},
		}
		tests["NoneFree"+suffix] = test{
			alloc:     []BitRange{{0, PallocChunkPages}},
			scavenged: []BitRange{{PallocChunkPages / 2, PallocChunkPages / 2}},
			min:       m,
			max:       PallocChunkPages,
			want:      BitRange{0, 0},
		}
		tests["StartFree"+suffix] = test{
			alloc: []BitRange{{uint(m), PallocChunkPages - uint(m)}},
			min:   m,
			max:   PallocChunkPages,
			want:  BitRange{0, uint(m)},
		}
		tests["StartFree"+suffix] = test{
			alloc: []BitRange{{uint(m), PallocChunkPages - uint(m)}},
			min:   m,
			max:   PallocChunkPages,
			want:  BitRange{0, uint(m)},
		}
		tests["EndFree"+suffix] = test{
			alloc: []BitRange{{0, PallocChunkPages - uint(m)}},
			min:   m,
			max:   PallocChunkPages,
			want:  BitRange{PallocChunkPages - uint(m), uint(m)},
		}
		tests["Straddle64"+suffix] = test{
			alloc: []BitRange{{0, 64 - uint(m)}, {64 + uint(m), PallocChunkPages - (64 + uint(m))}},
			min:   m,
			max:   2 * m,
			want:  BitRange{64 - uint(m), 2 * uint(m)},
		}
		tests["BottomEdge64WithFull"+suffix] = test{
			alloc:     []BitRange{{64, 64}, {128 + 3*uint(m), PallocChunkPages - (128 + 3*uint(m))}},
			scavenged: []BitRange{{1, 10}},
			min:       m,
			max:       3 * m,
			want:      BitRange{128, 3 * uint(m)},
		}
		tests["BottomEdge64WithPocket"+suffix] = test{
			alloc:     []BitRange{{64, 62}, {127, 1}, {128 + 3*uint(m), PallocChunkPages - (128 + 3*uint(m))}},
			scavenged: []BitRange{{1, 10}},
			min:       m,
			max:       3 * m,
			want:      BitRange{128, 3 * uint(m)},
		}
		tests["Max0"+suffix] = test{
			scavenged: []BitRange{{0, PallocChunkPages - uint(m)}},
			min:       m,
			max:       0,
			want:      BitRange{PallocChunkPages - uint(m), uint(m)},
		}
		if m <= 8 {
			tests["OneFree"] = test{
				alloc: []BitRange{{0, 40}, {40 + uint(m), PallocChunkPages - (40 + uint(m))}},
				min:   m,
				max:   PallocChunkPages,
				want:  BitRange{40, uint(m)},
			}
			tests["OneScavenged"] = test{
				alloc:     []BitRange{{0, 40}, {40 + uint(m), PallocChunkPages - (40 + uint(m))}},
				scavenged: []BitRange{{40, 1}},
				min:       m,
				max:       PallocChunkPages,
				want:      BitRange{0, 0},
			}
		}
		if m > 1 {
			tests["MaxUnaligned"+suffix] = test{
				scavenged: []BitRange{{0, PallocChunkPages - uint(m*2-1)}},
				min:       m,
				max:       m - 2,
				want:      BitRange{PallocChunkPages - uint(m), uint(m)},
			}
			tests["SkipSmall"+suffix] = test{
				alloc: []BitRange{{0, 64 - uint(m)}, {64, 5}, {70, 11}, {82, PallocChunkPages - 82}},
				min:   m,
				max:   m,
				want:  BitRange{64 - uint(m), uint(m)},
			}
			tests["SkipMisaligned"+suffix] = test{
				alloc: []BitRange{{0, 64 - uint(m)}, {64, 63}, {127 + uint(m), PallocChunkPages - (127 + uint(m))}},
				min:   m,
				max:   m,
				want:  BitRange{64 - uint(m), uint(m)},
			}
			tests["MaxLessThan"+suffix] = test{
				scavenged: []BitRange{{0, PallocChunkPages - uint(m)}},
				min:       m,
				max:       1,
				want:      BitRange{PallocChunkPages - uint(m), uint(m)},
			}
		}
	}
	if PhysHugePageSize > uintptr(PageSize) {
		// Check hugepage preserving behavior.
		bits := uint(PhysHugePageSize / uintptr(PageSize))
		tests["PreserveHugePageBottom"] = test{
			alloc: []BitRange{{bits + 2, PallocChunkPages - (bits + 2)}},
			min:   1,
			max:   3, // Make it so that max would have us try to break the huge page.
			want:  BitRange{0, bits + 2},
		}
		if 3*bits < PallocChunkPages {
			// We need at least 3 huge pages in a chunk for this test to make sense.
			tests["PreserveHugePageMiddle"] = test{
				alloc: []BitRange{{0, bits - 10}, {2*bits + 10, PallocChunkPages - (2*bits + 10)}},
				min:   1,
				max:   12, // Make it so that max would have us try to break the huge page.
				want:  BitRange{bits, bits + 10},
			}
		}
		tests["PreserveHugePageTop"] = test{
			alloc: []BitRange{{0, PallocChunkPages - bits}},
			min:   1,
			max:   1, // Even one page would break a huge page in this case.
			want:  BitRange{PallocChunkPages - bits, bits},
		}
	}
	for name, v := range tests {
		v := v
		t.Run(name, func(t *testing.T) {
			b := makePallocData(v.alloc, v.scavenged)
			start, size := b.FindScavengeCandidate(PallocChunkPages-1, v.min, v.max)
			got := BitRange{start, size}
			if !(got.N == 0 && v.want.N == 0) && got != v.want {
				t.Fatalf("candidate mismatch: got %v, want %v", got, v.want)
			}
		})
	}
}

// Tests end-to-end scavenging on a pageAlloc.
func TestPageAllocScavenge(t *testing.T) {
	if GOOS == "openbsd" && testing.Short() {
		t.Skip("skipping because virtual memory is limited; see #36210")
	}
	type test struct {
		request, expect uintptr
	}
	minPages := PhysPageSize / PageSize
	if minPages < 1 {
		minPages = 1
	}
	type setup struct {
		beforeAlloc map[ChunkIdx][]BitRange
		beforeScav  map[ChunkIdx][]BitRange
		expect      []test
		afterScav   map[ChunkIdx][]BitRange
	}
	tests := map[string]setup{
		"AllFreeUnscavExhaust": {
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {},
				BaseChunkIdx + 1: {},
				BaseChunkIdx + 2: {},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {},
				BaseChunkIdx + 1: {},
				BaseChunkIdx + 2: {},
			},
			expect: []test{
				{^uintptr(0), 3 * PallocChunkPages * PageSize},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {{0, PallocChunkPages}},
				BaseChunkIdx + 1: {{0, PallocChunkPages}},
				BaseChunkIdx + 2: {{0, PallocChunkPages}},
			},
		},
		"NoneFreeUnscavExhaust": {
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {{0, PallocChunkPages}},
				BaseChunkIdx + 1: {},
				BaseChunkIdx + 2: {{0, PallocChunkPages}},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {},
				BaseChunkIdx + 1: {{0, PallocChunkPages}},
				BaseChunkIdx + 2: {},
			},
			expect: []test{
				{^uintptr(0), 0},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {},
				BaseChunkIdx + 1: {{0, PallocChunkPages}},
				BaseChunkIdx + 2: {},
			},
		},
		"ScavHighestPageFirst": {
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx: {},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
			},
			expect: []test{
				{1, minPages * PageSize},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(minPages)}},
			},
		},
		"ScavMultiple": {
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx: {},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx: {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
			},
			expect: []test{
				{minPages * PageSize, minPages * PageSize},
				{minPages * PageSize, minPages * PageSize},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx: {{0, PallocChunkPages}},
			},
		},
		"ScavMultiple2": {
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {},
				BaseChunkIdx + 1: {},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
				BaseChunkIdx + 1: {{0, PallocChunkPages - uint(2*minPages)}},
			},
			expect: []test{
				{2 * minPages * PageSize, 2 * minPages * PageSize},
				{minPages * PageSize, minPages * PageSize},
				{minPages * PageSize, minPages * PageSize},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:     {{0, PallocChunkPages}},
				BaseChunkIdx + 1: {{0, PallocChunkPages}},
			},
		},
		"ScavDiscontiguous": {
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx:       {},
				BaseChunkIdx + 0xe: {},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:       {{uint(minPages), PallocChunkPages - uint(2*minPages)}},
				BaseChunkIdx + 0xe: {{uint(2 * minPages), PallocChunkPages - uint(2*minPages)}},
			},
			expect: []test{
				{2 * minPages * PageSize, 2 * minPages * PageSize},
				{^uintptr(0), 2 * minPages * PageSize},
				{^uintptr(0), 0},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:       {{0, PallocChunkPages}},
				BaseChunkIdx + 0xe: {{0, PallocChunkPages}},
			},
		},
	}
	if PageAlloc64Bit != 0 {
		tests["ScavAllVeryDiscontiguous"] = setup{
			beforeAlloc: map[ChunkIdx][]BitRange{
				BaseChunkIdx:          {},
				BaseChunkIdx + 0x1000: {},
			},
			beforeScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:          {},
				BaseChunkIdx + 0x1000: {},
			},
			expect: []test{
				{^uintptr(0), 2 * PallocChunkPages * PageSize},
				{^uintptr(0), 0},
			},
			afterScav: map[ChunkIdx][]BitRange{
				BaseChunkIdx:          {{0, PallocChunkPages}},
				BaseChunkIdx + 0x1000: {{0, PallocChunkPages}},
			},
		}
	}
	for name, v := range tests {
		v := v
		runTest := func(t *testing.T, mayUnlock bool) {
			b := NewPageAlloc(v.beforeAlloc, v.beforeScav)
			defer FreePageAlloc(b)

			for iter, h := range v.expect {
				if got := b.Scavenge(h.request, mayUnlock); got != h.expect {
					t.Fatalf("bad scavenge #%d: want %d, got %d", iter+1, h.expect, got)
				}
			}
			want := NewPageAlloc(v.beforeAlloc, v.afterScav)
			defer FreePageAlloc(want)

			checkPageAlloc(t, want, b)
		}
		t.Run(name, func(t *testing.T) {
			runTest(t, false)
		})
		t.Run(name+"MayUnlock", func(t *testing.T) {
			runTest(t, true)
		})
	}
}