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

View as plain text