Source file src/runtime/mpallocbits_test.go

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package runtime_test
     6  
     7  import (
     8  	"fmt"
     9  	"math/rand"
    10  	. "runtime"
    11  	"testing"
    12  )
    13  
    14  // Ensures that got and want are the same, and if not, reports
    15  // detailed diff information.
    16  func checkPallocBits(t *testing.T, got, want *PallocBits) bool {
    17  	d := DiffPallocBits(got, want)
    18  	if len(d) != 0 {
    19  		t.Errorf("%d range(s) different", len(d))
    20  		for _, bits := range d {
    21  			t.Logf("\t@ bit index %d", bits.I)
    22  			t.Logf("\t|  got: %s", StringifyPallocBits(got, bits))
    23  			t.Logf("\t| want: %s", StringifyPallocBits(want, bits))
    24  		}
    25  		return false
    26  	}
    27  	return true
    28  }
    29  
    30  // makePallocBits produces an initialized PallocBits by setting
    31  // the ranges in s to 1 and the rest to zero.
    32  func makePallocBits(s []BitRange) *PallocBits {
    33  	b := new(PallocBits)
    34  	for _, v := range s {
    35  		b.AllocRange(v.I, v.N)
    36  	}
    37  	return b
    38  }
    39  
    40  // Ensures that PallocBits.AllocRange works, which is a fundamental
    41  // method used for testing and initialization since it's used by
    42  // makePallocBits.
    43  func TestPallocBitsAllocRange(t *testing.T) {
    44  	test := func(t *testing.T, i, n uint, want *PallocBits) {
    45  		checkPallocBits(t, makePallocBits([]BitRange{{i, n}}), want)
    46  	}
    47  	t.Run("OneLow", func(t *testing.T) {
    48  		want := new(PallocBits)
    49  		want[0] = 0x1
    50  		test(t, 0, 1, want)
    51  	})
    52  	t.Run("OneHigh", func(t *testing.T) {
    53  		want := new(PallocBits)
    54  		want[PallocChunkPages/64-1] = 1 << 63
    55  		test(t, PallocChunkPages-1, 1, want)
    56  	})
    57  	if PallocChunkPages >= 512 {
    58  		t.Run("Inner", func(t *testing.T) {
    59  			want := new(PallocBits)
    60  			want[:][2] = 0x3e
    61  			test(t, 129, 5, want)
    62  		})
    63  		t.Run("Aligned", func(t *testing.T) {
    64  			want := new(PallocBits)
    65  			want[:][2] = ^uint64(0)
    66  			want[:][3] = ^uint64(0)
    67  			test(t, 128, 128, want)
    68  		})
    69  		t.Run("Begin", func(t *testing.T) {
    70  			want := new(PallocBits)
    71  			want[:][0] = ^uint64(0)
    72  			want[:][1] = ^uint64(0)
    73  			want[:][2] = ^uint64(0)
    74  			want[:][3] = ^uint64(0)
    75  			want[:][4] = ^uint64(0)
    76  			want[:][5] = 0x1
    77  			test(t, 0, 321, want)
    78  		})
    79  		t.Run("End", func(t *testing.T) {
    80  			// avoid constant overflow when PallocChunkPages is small
    81  			var PallocChunkPages uint = PallocChunkPages
    82  			want := new(PallocBits)
    83  			want[PallocChunkPages/64-1] = ^uint64(0)
    84  			want[PallocChunkPages/64-2] = ^uint64(0)
    85  			want[PallocChunkPages/64-3] = ^uint64(0)
    86  			want[PallocChunkPages/64-4] = 1 << 63
    87  			test(t, PallocChunkPages-(64*3+1), 64*3+1, want)
    88  		})
    89  	}
    90  	t.Run("All", func(t *testing.T) {
    91  		want := new(PallocBits)
    92  		for i := range want {
    93  			want[i] = ^uint64(0)
    94  		}
    95  		test(t, 0, PallocChunkPages, want)
    96  	})
    97  }
    98  
    99  // Inverts every bit in the PallocBits.
   100  func invertPallocBits(b *PallocBits) {
   101  	for i := range b {
   102  		b[i] = ^b[i]
   103  	}
   104  }
   105  
   106  // Ensures two packed summaries are identical, and reports a detailed description
   107  // of the difference if they're not.
   108  func checkPallocSum(t testing.TB, got, want PallocSum) {
   109  	if got.Start() != want.Start() {
   110  		t.Errorf("inconsistent start: got %d, want %d", got.Start(), want.Start())
   111  	}
   112  	if got.Max() != want.Max() {
   113  		t.Errorf("inconsistent max: got %d, want %d", got.Max(), want.Max())
   114  	}
   115  	if got.End() != want.End() {
   116  		t.Errorf("inconsistent end: got %d, want %d", got.End(), want.End())
   117  	}
   118  }
   119  
   120  func TestMallocBitsPopcntRange(t *testing.T) {
   121  	type test struct {
   122  		i, n uint // bit range to popcnt over.
   123  		want uint // expected popcnt result on that range.
   124  	}
   125  	type testCase struct {
   126  		init  []BitRange // bit ranges to set to 1 in the bitmap.
   127  		tests []test     // a set of popcnt tests to run over the bitmap.
   128  	}
   129  	tests := map[string]testCase{
   130  		"None": {
   131  			tests: []test{
   132  				{0, 1, 0},
   133  				{5, 3, 0},
   134  				{2, 11, 0},
   135  				{PallocChunkPages/4 + 1, PallocChunkPages / 2, 0},
   136  				{0, PallocChunkPages, 0},
   137  			},
   138  		},
   139  		"All": {
   140  			init: []BitRange{{0, PallocChunkPages}},
   141  			tests: []test{
   142  				{0, 1, 1},
   143  				{5, 3, 3},
   144  				{2, 11, 11},
   145  				{PallocChunkPages/4 + 1, PallocChunkPages / 2, PallocChunkPages / 2},
   146  				{0, PallocChunkPages, PallocChunkPages},
   147  			},
   148  		},
   149  		"Half": {
   150  			init: []BitRange{{PallocChunkPages / 2, PallocChunkPages / 2}},
   151  			tests: []test{
   152  				{0, 1, 0},
   153  				{5, 3, 0},
   154  				{2, 11, 0},
   155  				{PallocChunkPages/2 - 1, 1, 0},
   156  				{PallocChunkPages / 2, 1, 1},
   157  				{PallocChunkPages/2 + 10, 1, 1},
   158  				{PallocChunkPages/2 - 1, 2, 1},
   159  				{PallocChunkPages / 4, PallocChunkPages / 4, 0},
   160  				{PallocChunkPages / 4, PallocChunkPages/4 + 1, 1},
   161  				{PallocChunkPages/4 + 1, PallocChunkPages / 2, PallocChunkPages/4 + 1},
   162  				{0, PallocChunkPages, PallocChunkPages / 2},
   163  			},
   164  		},
   165  	}
   166  	if PallocChunkPages >= 512 {
   167  		tests["OddBound"] = testCase{
   168  			init: []BitRange{{0, 111}},
   169  			tests: []test{
   170  				{0, 1, 1},
   171  				{5, 3, 3},
   172  				{2, 11, 11},
   173  				{110, 2, 1},
   174  				{99, 50, 12},
   175  				{110, 1, 1},
   176  				{111, 1, 0},
   177  				{99, 1, 1},
   178  				{120, 1, 0},
   179  				{PallocChunkPages / 2, PallocChunkPages / 2, 0},
   180  				{0, PallocChunkPages, 111},
   181  			},
   182  		}
   183  		tests["Scattered"] = testCase{
   184  			init: []BitRange{
   185  				{1, 3}, {5, 1}, {7, 1}, {10, 2}, {13, 1}, {15, 4},
   186  				{21, 1}, {23, 1}, {26, 2}, {30, 5}, {36, 2}, {40, 3},
   187  				{44, 6}, {51, 1}, {53, 2}, {58, 3}, {63, 1}, {67, 2},
   188  				{71, 10}, {84, 1}, {89, 7}, {99, 2}, {103, 1}, {107, 2},
   189  				{111, 1}, {113, 1}, {115, 1}, {118, 1}, {120, 2}, {125, 5},
   190  			},
   191  			tests: []test{
   192  				{0, 11, 6},
   193  				{0, 64, 39},
   194  				{13, 64, 40},
   195  				{64, 64, 34},
   196  				{0, 128, 73},
   197  				{1, 128, 74},
   198  				{0, PallocChunkPages, 75},
   199  			},
   200  		}
   201  	}
   202  	for name, v := range tests {
   203  		t.Run(name, func(t *testing.T) {
   204  			b := makePallocBits(v.init)
   205  			for _, h := range v.tests {
   206  				if got := b.PopcntRange(h.i, h.n); got != h.want {
   207  					t.Errorf("bad popcnt (i=%d, n=%d): got %d, want %d", h.i, h.n, got, h.want)
   208  				}
   209  			}
   210  		})
   211  	}
   212  }
   213  
   214  // Ensures computing bit summaries works as expected by generating random
   215  // bitmaps and checking against a reference implementation.
   216  func TestPallocBitsSummarizeRandom(t *testing.T) {
   217  	b := new(PallocBits)
   218  	for i := 0; i < 1000; i++ {
   219  		// Randomize bitmap.
   220  		for i := range b {
   221  			b[i] = rand.Uint64()
   222  		}
   223  		// Check summary against reference implementation.
   224  		checkPallocSum(t, b.Summarize(), SummarizeSlow(b))
   225  	}
   226  }
   227  
   228  // Ensures computing bit summaries works as expected.
   229  func TestPallocBitsSummarize(t *testing.T) {
   230  	var emptySum = PackPallocSum(PallocChunkPages, PallocChunkPages, PallocChunkPages)
   231  	type test struct {
   232  		free []BitRange // Ranges of free (zero) bits.
   233  		hits []PallocSum
   234  	}
   235  	tests := make(map[string]test)
   236  	tests["NoneFree"] = test{
   237  		free: []BitRange{},
   238  		hits: []PallocSum{
   239  			PackPallocSum(0, 0, 0),
   240  		},
   241  	}
   242  	tests["OnlyStart"] = test{
   243  		free: []BitRange{{0, 10}},
   244  		hits: []PallocSum{
   245  			PackPallocSum(10, 10, 0),
   246  		},
   247  	}
   248  	tests["OnlyEnd"] = test{
   249  		free: []BitRange{{PallocChunkPages - 40, 40}},
   250  		hits: []PallocSum{
   251  			PackPallocSum(0, 40, 40),
   252  		},
   253  	}
   254  	tests["StartAndEnd"] = test{
   255  		free: []BitRange{{0, 11}, {PallocChunkPages - 23, 23}},
   256  		hits: []PallocSum{
   257  			PackPallocSum(11, 23, 23),
   258  		},
   259  	}
   260  	if PallocChunkPages >= 512 {
   261  		tests["StartMaxEnd"] = test{
   262  			free: []BitRange{{0, 4}, {50, 100}, {PallocChunkPages - 4, 4}},
   263  			hits: []PallocSum{
   264  				PackPallocSum(4, 100, 4),
   265  			},
   266  		}
   267  		tests["OnlyMax"] = test{
   268  			free: []BitRange{{1, 20}, {35, 241}, {PallocChunkPages - 50, 30}},
   269  			hits: []PallocSum{
   270  				PackPallocSum(0, 241, 0),
   271  			},
   272  		}
   273  		tests["MultiMax"] = test{
   274  			free: []BitRange{{35, 2}, {40, 5}, {100, 5}},
   275  			hits: []PallocSum{
   276  				PackPallocSum(0, 5, 0),
   277  			},
   278  		}
   279  	}
   280  	tests["One"] = test{
   281  		free: []BitRange{{2, 1}},
   282  		hits: []PallocSum{
   283  			PackPallocSum(0, 1, 0),
   284  		},
   285  	}
   286  	tests["AllFree"] = test{
   287  		free: []BitRange{{0, PallocChunkPages}},
   288  		hits: []PallocSum{
   289  			emptySum,
   290  		},
   291  	}
   292  	for name, v := range tests {
   293  		t.Run(name, func(t *testing.T) {
   294  			b := makePallocBits(v.free)
   295  			// In the PallocBits we create 1's represent free spots, but in our actual
   296  			// PallocBits 1 means not free, so invert.
   297  			invertPallocBits(b)
   298  			for _, h := range v.hits {
   299  				checkPallocSum(t, b.Summarize(), h)
   300  			}
   301  		})
   302  	}
   303  }
   304  
   305  // Benchmarks how quickly we can summarize a PallocBits.
   306  func BenchmarkPallocBitsSummarize(b *testing.B) {
   307  	patterns := []uint64{
   308  		0,
   309  		^uint64(0),
   310  		0xaa,
   311  		0xaaaaaaaaaaaaaaaa,
   312  		0x80000000aaaaaaaa,
   313  		0xaaaaaaaa00000001,
   314  		0xbbbbbbbbbbbbbbbb,
   315  		0x80000000bbbbbbbb,
   316  		0xbbbbbbbb00000001,
   317  		0xcccccccccccccccc,
   318  		0x4444444444444444,
   319  		0x4040404040404040,
   320  		0x4000400040004000,
   321  		0x1000404044ccaaff,
   322  	}
   323  	for _, p := range patterns {
   324  		buf := new(PallocBits)
   325  		for i := 0; i < len(buf); i++ {
   326  			buf[i] = p
   327  		}
   328  		b.Run(fmt.Sprintf("Unpacked%02X", p), func(b *testing.B) {
   329  			checkPallocSum(b, buf.Summarize(), SummarizeSlow(buf))
   330  			for i := 0; i < b.N; i++ {
   331  				buf.Summarize()
   332  			}
   333  		})
   334  	}
   335  }
   336  
   337  // Ensures page allocation works.
   338  func TestPallocBitsAlloc(t *testing.T) {
   339  	type test struct {
   340  		before []BitRange
   341  		after  []BitRange
   342  		npages uintptr
   343  		hits   []uint
   344  	}
   345  	tests := map[string]test{
   346  		"AllFree1": {
   347  			npages: 1,
   348  			hits:   []uint{0, 1, 2, 3, 4, 5},
   349  			after:  []BitRange{{0, 6}},
   350  		},
   351  		"AllFree2": {
   352  			npages: 2,
   353  			hits:   []uint{0, 2, 4, 6, 8, 10},
   354  			after:  []BitRange{{0, 12}},
   355  		},
   356  		"AllFree5": {
   357  			npages: 5,
   358  			hits:   []uint{0, 5, 10, 15, 20},
   359  			after:  []BitRange{{0, 25}},
   360  		},
   361  		"NoneFree1": {
   362  			before: []BitRange{{0, PallocChunkPages}},
   363  			npages: 1,
   364  			hits:   []uint{^uint(0), ^uint(0)},
   365  			after:  []BitRange{{0, PallocChunkPages}},
   366  		},
   367  		"NoneFree2": {
   368  			before: []BitRange{{0, PallocChunkPages}},
   369  			npages: 2,
   370  			hits:   []uint{^uint(0), ^uint(0)},
   371  			after:  []BitRange{{0, PallocChunkPages}},
   372  		},
   373  		"NoneFree5": {
   374  			before: []BitRange{{0, PallocChunkPages}},
   375  			npages: 5,
   376  			hits:   []uint{^uint(0), ^uint(0)},
   377  			after:  []BitRange{{0, PallocChunkPages}},
   378  		},
   379  		"NoneFree65": {
   380  			before: []BitRange{{0, PallocChunkPages}},
   381  			npages: 65,
   382  			hits:   []uint{^uint(0), ^uint(0)},
   383  			after:  []BitRange{{0, PallocChunkPages}},
   384  		},
   385  		"ExactFit1": {
   386  			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 - 2, PallocChunkPages/2 + 2}},
   387  			npages: 1,
   388  			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
   389  			after:  []BitRange{{0, PallocChunkPages}},
   390  		},
   391  		"ExactFit2": {
   392  			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 - 1, PallocChunkPages/2 + 1}},
   393  			npages: 2,
   394  			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
   395  			after:  []BitRange{{0, PallocChunkPages}},
   396  		},
   397  		"ExactFit5": {
   398  			before: []BitRange{{0, PallocChunkPages/2 - 3}, {PallocChunkPages/2 + 2, PallocChunkPages/2 - 2}},
   399  			npages: 5,
   400  			hits:   []uint{PallocChunkPages/2 - 3, ^uint(0)},
   401  			after:  []BitRange{{0, PallocChunkPages}},
   402  		},
   403  	}
   404  	if PallocChunkPages >= 512 {
   405  		// avoid constant overflow when PallocChunkPages is small
   406  		var PallocChunkPages uint = PallocChunkPages
   407  		tests["AllFree64"] = test{
   408  			npages: 64,
   409  			hits:   []uint{0, 64, 128},
   410  			after:  []BitRange{{0, 192}},
   411  		}
   412  		tests["AllFree65"] = test{
   413  			npages: 65,
   414  			hits:   []uint{0, 65, 130},
   415  			after:  []BitRange{{0, 195}},
   416  		}
   417  		tests["SomeFree64"] = test{
   418  			before: []BitRange{{0, 32}, {64, 32}, {100, PallocChunkPages - 100}},
   419  			npages: 64,
   420  			hits:   []uint{^uint(0)},
   421  			after:  []BitRange{{0, 32}, {64, 32}, {100, PallocChunkPages - 100}},
   422  		}
   423  		tests["ExactFit65"] = test{
   424  			before: []BitRange{{0, PallocChunkPages/2 - 31}, {PallocChunkPages/2 + 34, PallocChunkPages/2 - 34}},
   425  			npages: 65,
   426  			hits:   []uint{PallocChunkPages/2 - 31, ^uint(0)},
   427  			after:  []BitRange{{0, PallocChunkPages}},
   428  		}
   429  		tests["SomeFree161"] = test{
   430  			before: []BitRange{{0, 185}, {331, 1}},
   431  			npages: 161,
   432  			hits:   []uint{332},
   433  			after:  []BitRange{{0, 185}, {331, 162}},
   434  		}
   435  	}
   436  	for name, v := range tests {
   437  		t.Run(name, func(t *testing.T) {
   438  			b := makePallocBits(v.before)
   439  			for iter, i := range v.hits {
   440  				a, _ := b.Find(v.npages, 0)
   441  				if i != a {
   442  					t.Fatalf("find #%d picked wrong index: want %d, got %d", iter+1, i, a)
   443  				}
   444  				if i != ^uint(0) {
   445  					b.AllocRange(a, uint(v.npages))
   446  				}
   447  			}
   448  			want := makePallocBits(v.after)
   449  			checkPallocBits(t, b, want)
   450  		})
   451  	}
   452  }
   453  
   454  // Ensures page freeing works.
   455  func TestPallocBitsFree(t *testing.T) {
   456  	type test struct {
   457  		beforeInv []BitRange
   458  		afterInv  []BitRange
   459  		frees     []uint
   460  		npages    uintptr
   461  	}
   462  	tests := map[string]test{
   463  		"NoneFree1": {
   464  			npages:   1,
   465  			frees:    []uint{0, 1, 2, 3, 4, 5},
   466  			afterInv: []BitRange{{0, 6}},
   467  		},
   468  		"NoneFree2": {
   469  			npages:   2,
   470  			frees:    []uint{0, 2, 4, 6, 8, 10},
   471  			afterInv: []BitRange{{0, 12}},
   472  		},
   473  		"NoneFree5": {
   474  			npages:   5,
   475  			frees:    []uint{0, 5, 10, 15, 20},
   476  			afterInv: []BitRange{{0, 25}},
   477  		},
   478  	}
   479  	if PallocChunkPages >= 512 {
   480  		tests["SomeFree"] = test{
   481  			npages:    1,
   482  			beforeInv: []BitRange{{0, 32}, {64, 32}, {100, 1}},
   483  			frees:     []uint{32},
   484  			afterInv:  []BitRange{{0, 33}, {64, 32}, {100, 1}},
   485  		}
   486  		tests["NoneFree64"] = test{
   487  			npages:   64,
   488  			frees:    []uint{0, 64, 128},
   489  			afterInv: []BitRange{{0, 192}},
   490  		}
   491  		tests["NoneFree65"] = test{
   492  			npages:   65,
   493  			frees:    []uint{0, 65, 130},
   494  			afterInv: []BitRange{{0, 195}},
   495  		}
   496  	}
   497  	for name, v := range tests {
   498  		t.Run(name, func(t *testing.T) {
   499  			b := makePallocBits(v.beforeInv)
   500  			invertPallocBits(b)
   501  			for _, i := range v.frees {
   502  				b.Free(i, uint(v.npages))
   503  			}
   504  			want := makePallocBits(v.afterInv)
   505  			invertPallocBits(want)
   506  			checkPallocBits(t, b, want)
   507  		})
   508  	}
   509  }
   510  
   511  func TestFindBitRange64(t *testing.T) {
   512  	check := func(x uint64, n uint, result uint) {
   513  		i := FindBitRange64(x, n)
   514  		if result == ^uint(0) && i < 64 {
   515  			t.Errorf("case (%016x, %d): got %d, want failure", x, n, i)
   516  		} else if result != ^uint(0) && i != result {
   517  			t.Errorf("case (%016x, %d): got %d, want %d", x, n, i, result)
   518  		}
   519  	}
   520  	for i := uint(1); i <= 64; i++ {
   521  		check(^uint64(0), i, 0)
   522  	}
   523  	for i := uint(1); i <= 64; i++ {
   524  		check(0, i, ^uint(0))
   525  	}
   526  	check(0x8000000000000000, 1, 63)
   527  	check(0xc000010001010000, 2, 62)
   528  	check(0xc000010001030000, 2, 16)
   529  	check(0xe000030001030000, 3, 61)
   530  	check(0xe000030001070000, 3, 16)
   531  	check(0xffff03ff01070000, 16, 48)
   532  	check(0xffff03ff0107ffff, 16, 0)
   533  	check(0x0fff03ff01079fff, 16, ^uint(0))
   534  }
   535  
   536  func BenchmarkFindBitRange64(b *testing.B) {
   537  	patterns := []uint64{
   538  		0,
   539  		^uint64(0),
   540  		0xaa,
   541  		0xaaaaaaaaaaaaaaaa,
   542  		0x80000000aaaaaaaa,
   543  		0xaaaaaaaa00000001,
   544  		0xbbbbbbbbbbbbbbbb,
   545  		0x80000000bbbbbbbb,
   546  		0xbbbbbbbb00000001,
   547  		0xcccccccccccccccc,
   548  		0x4444444444444444,
   549  		0x4040404040404040,
   550  		0x4000400040004000,
   551  	}
   552  	sizes := []uint{
   553  		2, 8, 32,
   554  	}
   555  	for _, pattern := range patterns {
   556  		for _, size := range sizes {
   557  			b.Run(fmt.Sprintf("Pattern%02XSize%d", pattern, size), func(b *testing.B) {
   558  				for i := 0; i < b.N; i++ {
   559  					FindBitRange64(pattern, size)
   560  				}
   561  			})
   562  		}
   563  	}
   564  }
   565  

View as plain text