mranges_test.go

     1  // Copyright 2020 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  	. "runtime"
     9  	"testing"
    10  )
    11  
    12  func validateAddrRanges(t *testing.T, a *AddrRanges, want ...AddrRange) {
    13  	ranges := a.Ranges()
    14  	if len(ranges) != len(want) {
    15  		t.Errorf("want %v, got %v", want, ranges)
    16  		t.Fatal("different lengths")
    17  	}
    18  	gotTotalBytes := uintptr(0)
    19  	wantTotalBytes := uintptr(0)
    20  	for i := range ranges {
    21  		gotTotalBytes += ranges[i].Size()
    22  		wantTotalBytes += want[i].Size()
    23  		if ranges[i].Base() >= ranges[i].Limit() {
    24  			t.Error("empty range found")
    25  		}
    26  		// Ensure this is equivalent to what we want.
    27  		if !ranges[i].Equals(want[i]) {
    28  			t.Errorf("range %d: got [0x%x, 0x%x), want [0x%x, 0x%x)", i,
    29  				ranges[i].Base(), ranges[i].Limit(),
    30  				want[i].Base(), want[i].Limit(),
    31  			)
    32  		}
    33  		if i != 0 {
    34  			// Ensure the ranges are sorted.
    35  			if ranges[i-1].Base() >= ranges[i].Base() {
    36  				t.Errorf("ranges %d and %d are out of sorted order", i-1, i)
    37  			}
    38  			// Check for a failure to coalesce.
    39  			if ranges[i-1].Limit() == ranges[i].Base() {
    40  				t.Errorf("ranges %d and %d should have coalesced", i-1, i)
    41  			}
    42  			// Check if any ranges overlap. Because the ranges are sorted
    43  			// by base, it's sufficient to just check neighbors.
    44  			if ranges[i-1].Limit() > ranges[i].Base() {
    45  				t.Errorf("ranges %d and %d overlap", i-1, i)
    46  			}
    47  		}
    48  	}
    49  	if wantTotalBytes != gotTotalBytes {
    50  		t.Errorf("expected %d total bytes, got %d", wantTotalBytes, gotTotalBytes)
    51  	}
    52  	if b := a.TotalBytes(); b != gotTotalBytes {
    53  		t.Errorf("inconsistent total bytes: want %d, got %d", gotTotalBytes, b)
    54  	}
    55  	if t.Failed() {
    56  		t.Errorf("addrRanges: %v", ranges)
    57  		t.Fatal("detected bad addrRanges")
    58  	}
    59  }
    60  
    61  func TestAddrRangesAdd(t *testing.T) {
    62  	a := NewAddrRanges()
    63  
    64  	// First range.
    65  	a.Add(MakeAddrRange(512, 1024))
    66  	validateAddrRanges(t, &a,
    67  		MakeAddrRange(512, 1024),
    68  	)
    69  
    70  	// Coalesce up.
    71  	a.Add(MakeAddrRange(1024, 2048))
    72  	validateAddrRanges(t, &a,
    73  		MakeAddrRange(512, 2048),
    74  	)
    75  
    76  	// Add new independent range.
    77  	a.Add(MakeAddrRange(4096, 8192))
    78  	validateAddrRanges(t, &a,
    79  		MakeAddrRange(512, 2048),
    80  		MakeAddrRange(4096, 8192),
    81  	)
    82  
    83  	// Coalesce down.
    84  	a.Add(MakeAddrRange(3776, 4096))
    85  	validateAddrRanges(t, &a,
    86  		MakeAddrRange(512, 2048),
    87  		MakeAddrRange(3776, 8192),
    88  	)
    89  
    90  	// Coalesce up and down.
    91  	a.Add(MakeAddrRange(2048, 3776))
    92  	validateAddrRanges(t, &a,
    93  		MakeAddrRange(512, 8192),
    94  	)
    95  
    96  	// Push a bunch of independent ranges to the end to try and force growth.
    97  	expectedRanges := []AddrRange{MakeAddrRange(512, 8192)}
    98  	for i := uintptr(0); i < 64; i++ {
    99  		dRange := MakeAddrRange(8192+(i+1)*2048, 8192+(i+1)*2048+10)
   100  		a.Add(dRange)
   101  		expectedRanges = append(expectedRanges, dRange)
   102  		validateAddrRanges(t, &a, expectedRanges...)
   103  	}
   104  
   105  	// Push a bunch of independent ranges to the beginning to try and force growth.
   106  	var bottomRanges []AddrRange
   107  	for i := uintptr(0); i < 63; i++ {
   108  		dRange := MakeAddrRange(8+i*8, 8+i*8+4)
   109  		a.Add(dRange)
   110  		bottomRanges = append(bottomRanges, dRange)
   111  		validateAddrRanges(t, &a, append(bottomRanges, expectedRanges...)...)
   112  	}
   113  }
   114  
   115  func TestAddrRangesFindSucc(t *testing.T) {
   116  	var large []AddrRange
   117  	for i := 0; i < 100; i++ {
   118  		large = append(large, MakeAddrRange(5+uintptr(i)*5, 5+uintptr(i)*5+3))
   119  	}
   120  
   121  	type testt struct {
   122  		name   string
   123  		base   uintptr
   124  		expect int
   125  		ranges []AddrRange
   126  	}
   127  	tests := []testt{
   128  		{
   129  			name:   "Empty",
   130  			base:   12,
   131  			expect: 0,
   132  			ranges: []AddrRange{},
   133  		},
   134  		{
   135  			name:   "OneBefore",
   136  			base:   12,
   137  			expect: 0,
   138  			ranges: []AddrRange{
   139  				MakeAddrRange(14, 16),
   140  			},
   141  		},
   142  		{
   143  			name:   "OneWithin",
   144  			base:   14,
   145  			expect: 1,
   146  			ranges: []AddrRange{
   147  				MakeAddrRange(14, 16),
   148  			},
   149  		},
   150  		{
   151  			name:   "OneAfterLimit",
   152  			base:   16,
   153  			expect: 1,
   154  			ranges: []AddrRange{
   155  				MakeAddrRange(14, 16),
   156  			},
   157  		},
   158  		{
   159  			name:   "OneAfter",
   160  			base:   17,
   161  			expect: 1,
   162  			ranges: []AddrRange{
   163  				MakeAddrRange(14, 16),
   164  			},
   165  		},
   166  		{
   167  			name:   "ThreeBefore",
   168  			base:   3,
   169  			expect: 0,
   170  			ranges: []AddrRange{
   171  				MakeAddrRange(6, 10),
   172  				MakeAddrRange(12, 16),
   173  				MakeAddrRange(19, 22),
   174  			},
   175  		},
   176  		{
   177  			name:   "ThreeAfter",
   178  			base:   24,
   179  			expect: 3,
   180  			ranges: []AddrRange{
   181  				MakeAddrRange(6, 10),
   182  				MakeAddrRange(12, 16),
   183  				MakeAddrRange(19, 22),
   184  			},
   185  		},
   186  		{
   187  			name:   "ThreeBetween",
   188  			base:   11,
   189  			expect: 1,
   190  			ranges: []AddrRange{
   191  				MakeAddrRange(6, 10),
   192  				MakeAddrRange(12, 16),
   193  				MakeAddrRange(19, 22),
   194  			},
   195  		},
   196  		{
   197  			name:   "ThreeWithin",
   198  			base:   9,
   199  			expect: 1,
   200  			ranges: []AddrRange{
   201  				MakeAddrRange(6, 10),
   202  				MakeAddrRange(12, 16),
   203  				MakeAddrRange(19, 22),
   204  			},
   205  		},
   206  		{
   207  			name:   "Zero",
   208  			base:   0,
   209  			expect: 1,
   210  			ranges: []AddrRange{
   211  				MakeAddrRange(0, 10),
   212  			},
   213  		},
   214  		{
   215  			name:   "Max",
   216  			base:   ^uintptr(0),
   217  			expect: 1,
   218  			ranges: []AddrRange{
   219  				MakeAddrRange(^uintptr(0)-5, ^uintptr(0)),
   220  			},
   221  		},
   222  		{
   223  			name:   "LargeBefore",
   224  			base:   2,
   225  			expect: 0,
   226  			ranges: large,
   227  		},
   228  		{
   229  			name:   "LargeAfter",
   230  			base:   5 + uintptr(len(large))*5 + 30,
   231  			expect: len(large),
   232  			ranges: large,
   233  		},
   234  		{
   235  			name:   "LargeBetweenLow",
   236  			base:   14,
   237  			expect: 2,
   238  			ranges: large,
   239  		},
   240  		{
   241  			name:   "LargeBetweenHigh",
   242  			base:   249,
   243  			expect: 49,
   244  			ranges: large,
   245  		},
   246  		{
   247  			name:   "LargeWithinLow",
   248  			base:   25,
   249  			expect: 5,
   250  			ranges: large,
   251  		},
   252  		{
   253  			name:   "LargeWithinHigh",
   254  			base:   396,
   255  			expect: 79,
   256  			ranges: large,
   257  		},
   258  		{
   259  			name:   "LargeWithinMiddle",
   260  			base:   250,
   261  			expect: 50,
   262  			ranges: large,
   263  		},
   264  	}
   265  
   266  	for _, test := range tests {
   267  		t.Run(test.name, func(t *testing.T) {
   268  			a := MakeAddrRanges(test.ranges...)
   269  			i := a.FindSucc(test.base)
   270  			if i != test.expect {
   271  				t.Fatalf("expected %d, got %d", test.expect, i)
   272  			}
   273  		})
   274  	}
   275  }
   276
View as plain text