mranges.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  // Address range data structure.
     6  //
     7  // This file contains an implementation of a data structure which
     8  // manages ordered address ranges.
     9  
    10  package runtime
    11  
    12  import (
    13  	"internal/goarch"
    14  	"internal/runtime/atomic"
    15  	"unsafe"
    16  )
    17  
    18  // addrRange represents a region of address space.
    19  //
    20  // An addrRange must never span a gap in the address space.
    21  type addrRange struct {
    22  	// base and limit together represent the region of address space
    23  	// [base, limit). That is, base is inclusive, limit is exclusive.
    24  	// These are address over an offset view of the address space on
    25  	// platforms with a segmented address space, that is, on platforms
    26  	// where arenaBaseOffset != 0.
    27  	base, limit offAddr
    28  }
    29  
    30  // makeAddrRange creates a new address range from two virtual addresses.
    31  //
    32  // Throws if the base and limit are not in the same memory segment.
    33  func makeAddrRange(base, limit uintptr) addrRange {
    34  	r := addrRange{offAddr{base}, offAddr{limit}}
    35  	if (base-arenaBaseOffset >= base) != (limit-arenaBaseOffset >= limit) {
    36  		throw("addr range base and limit are not in the same memory segment")
    37  	}
    38  	return r
    39  }
    40  
    41  // size returns the size of the range represented in bytes.
    42  func (a addrRange) size() uintptr {
    43  	if !a.base.lessThan(a.limit) {
    44  		return 0
    45  	}
    46  	// Subtraction is safe because limit and base must be in the same
    47  	// segment of the address space.
    48  	return a.limit.diff(a.base)
    49  }
    50  
    51  // contains returns whether or not the range contains a given address.
    52  func (a addrRange) contains(addr uintptr) bool {
    53  	return a.base.lessEqual(offAddr{addr}) && (offAddr{addr}).lessThan(a.limit)
    54  }
    55  
    56  // subtract takes the addrRange toPrune and cuts out any overlap with
    57  // from, then returns the new range. subtract assumes that a and b
    58  // either don't overlap at all, only overlap on one side, or are equal.
    59  // If b is strictly contained in a, thus forcing a split, it will throw.
    60  func (a addrRange) subtract(b addrRange) addrRange {
    61  	if b.base.lessEqual(a.base) && a.limit.lessEqual(b.limit) {
    62  		return addrRange{}
    63  	} else if a.base.lessThan(b.base) && b.limit.lessThan(a.limit) {
    64  		throw("bad prune")
    65  	} else if b.limit.lessThan(a.limit) && a.base.lessThan(b.limit) {
    66  		a.base = b.limit
    67  	} else if a.base.lessThan(b.base) && b.base.lessThan(a.limit) {
    68  		a.limit = b.base
    69  	}
    70  	return a
    71  }
    72  
    73  // takeFromFront takes len bytes from the front of the address range, aligning
    74  // the base to align first. On success, returns the aligned start of the region
    75  // taken and true.
    76  func (a *addrRange) takeFromFront(len uintptr, align uint8) (uintptr, bool) {
    77  	base := alignUp(a.base.addr(), uintptr(align)) + len
    78  	if base > a.limit.addr() {
    79  		return 0, false
    80  	}
    81  	a.base = offAddr{base}
    82  	return base - len, true
    83  }
    84  
    85  // takeFromBack takes len bytes from the end of the address range, aligning
    86  // the limit to align after subtracting len. On success, returns the aligned
    87  // start of the region taken and true.
    88  func (a *addrRange) takeFromBack(len uintptr, align uint8) (uintptr, bool) {
    89  	limit := alignDown(a.limit.addr()-len, uintptr(align))
    90  	if a.base.addr() > limit {
    91  		return 0, false
    92  	}
    93  	a.limit = offAddr{limit}
    94  	return limit, true
    95  }
    96  
    97  // removeGreaterEqual removes all addresses in a greater than or equal
    98  // to addr and returns the new range.
    99  func (a addrRange) removeGreaterEqual(addr uintptr) addrRange {
   100  	if (offAddr{addr}).lessEqual(a.base) {
   101  		return addrRange{}
   102  	}
   103  	if a.limit.lessEqual(offAddr{addr}) {
   104  		return a
   105  	}
   106  	return makeAddrRange(a.base.addr(), addr)
   107  }
   108  
   109  var (
   110  	// minOffAddr is the minimum address in the offset space, and
   111  	// it corresponds to the virtual address arenaBaseOffset.
   112  	minOffAddr = offAddr{arenaBaseOffset}
   113  
   114  	// maxOffAddr is the maximum address in the offset address
   115  	// space. It corresponds to the highest virtual address representable
   116  	// by the page alloc chunk and heap arena maps.
   117  	maxOffAddr = offAddr{(((1 << heapAddrBits) - 1) + arenaBaseOffset) & uintptrMask}
   118  )
   119  
   120  // offAddr represents an address in a contiguous view
   121  // of the address space on systems where the address space is
   122  // segmented. On other systems, it's just a normal address.
   123  type offAddr struct {
   124  	// a is just the virtual address, but should never be used
   125  	// directly. Call addr() to get this value instead.
   126  	a uintptr
   127  }
   128  
   129  // add adds a uintptr offset to the offAddr.
   130  func (l offAddr) add(bytes uintptr) offAddr {
   131  	return offAddr{a: l.a + bytes}
   132  }
   133  
   134  // sub subtracts a uintptr offset from the offAddr.
   135  func (l offAddr) sub(bytes uintptr) offAddr {
   136  	return offAddr{a: l.a - bytes}
   137  }
   138  
   139  // diff returns the amount of bytes in between the
   140  // two offAddrs.
   141  func (l1 offAddr) diff(l2 offAddr) uintptr {
   142  	return l1.a - l2.a
   143  }
   144  
   145  // lessThan returns true if l1 is less than l2 in the offset
   146  // address space.
   147  func (l1 offAddr) lessThan(l2 offAddr) bool {
   148  	return (l1.a - arenaBaseOffset) < (l2.a - arenaBaseOffset)
   149  }
   150  
   151  // lessEqual returns true if l1 is less than or equal to l2 in
   152  // the offset address space.
   153  func (l1 offAddr) lessEqual(l2 offAddr) bool {
   154  	return (l1.a - arenaBaseOffset) <= (l2.a - arenaBaseOffset)
   155  }
   156  
   157  // equal returns true if the two offAddr values are equal.
   158  func (l1 offAddr) equal(l2 offAddr) bool {
   159  	// No need to compare in the offset space, it
   160  	// means the same thing.
   161  	return l1 == l2
   162  }
   163  
   164  // addr returns the virtual address for this offset address.
   165  func (l offAddr) addr() uintptr {
   166  	return l.a
   167  }
   168  
   169  // atomicOffAddr is like offAddr, but operations on it are atomic.
   170  // It also contains operations to be able to store marked addresses
   171  // to ensure that they're not overridden until they've been seen.
   172  type atomicOffAddr struct {
   173  	// a contains the offset address, unlike offAddr.
   174  	a atomic.Int64
   175  }
   176  
   177  // Clear attempts to store minOffAddr in atomicOffAddr. It may fail
   178  // if a marked value is placed in the box in the meanwhile.
   179  func (b *atomicOffAddr) Clear() {
   180  	for {
   181  		old := b.a.Load()
   182  		if old < 0 {
   183  			return
   184  		}
   185  		if b.a.CompareAndSwap(old, int64(minOffAddr.addr()-arenaBaseOffset)) {
   186  			return
   187  		}
   188  	}
   189  }
   190  
   191  // StoreMin stores addr if it's less than the current value in the
   192  // offset address space if the current value is not marked.
   193  func (b *atomicOffAddr) StoreMin(addr uintptr) {
   194  	new := int64(addr - arenaBaseOffset)
   195  	for {
   196  		old := b.a.Load()
   197  		if old < new {
   198  			return
   199  		}
   200  		if b.a.CompareAndSwap(old, new) {
   201  			return
   202  		}
   203  	}
   204  }
   205  
   206  // StoreUnmark attempts to unmark the value in atomicOffAddr and
   207  // replace it with newAddr. markedAddr must be a marked address
   208  // returned by Load. This function will not store newAddr if the
   209  // box no longer contains markedAddr.
   210  func (b *atomicOffAddr) StoreUnmark(markedAddr, newAddr uintptr) {
   211  	b.a.CompareAndSwap(-int64(markedAddr-arenaBaseOffset), int64(newAddr-arenaBaseOffset))
   212  }
   213  
   214  // StoreMarked stores addr but first converted to the offset address
   215  // space and then negated.
   216  func (b *atomicOffAddr) StoreMarked(addr uintptr) {
   217  	b.a.Store(-int64(addr - arenaBaseOffset))
   218  }
   219  
   220  // Load returns the address in the box as a virtual address. It also
   221  // returns if the value was marked or not.
   222  func (b *atomicOffAddr) Load() (uintptr, bool) {
   223  	v := b.a.Load()
   224  	wasMarked := false
   225  	if v < 0 {
   226  		wasMarked = true
   227  		v = -v
   228  	}
   229  	return uintptr(v) + arenaBaseOffset, wasMarked
   230  }
   231  
   232  // addrRanges is a data structure holding a collection of ranges of
   233  // address space.
   234  //
   235  // The ranges are coalesced eagerly to reduce the
   236  // number ranges it holds.
   237  //
   238  // The slice backing store for this field is persistentalloc'd
   239  // and thus there is no way to free it.
   240  //
   241  // addrRanges is not thread-safe.
   242  type addrRanges struct {
   243  	// ranges is a slice of ranges sorted by base.
   244  	ranges []addrRange
   245  
   246  	// totalBytes is the total amount of address space in bytes counted by
   247  	// this addrRanges.
   248  	totalBytes uintptr
   249  
   250  	// sysStat is the stat to track allocations by this type
   251  	sysStat *sysMemStat
   252  }
   253  
   254  func (a *addrRanges) init(sysStat *sysMemStat) {
   255  	ranges := (*notInHeapSlice)(unsafe.Pointer(&a.ranges))
   256  	ranges.len = 0
   257  	ranges.cap = 16
   258  	ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), goarch.PtrSize, sysStat))
   259  	a.sysStat = sysStat
   260  	a.totalBytes = 0
   261  }
   262  
   263  // findSucc returns the first index in a such that addr is
   264  // less than the base of the addrRange at that index.
   265  func (a *addrRanges) findSucc(addr uintptr) int {
   266  	base := offAddr{addr}
   267  
   268  	// Narrow down the search space via a binary search
   269  	// for large addrRanges until we have at most iterMax
   270  	// candidates left.
   271  	const iterMax = 8
   272  	bot, top := 0, len(a.ranges)
   273  	for top-bot > iterMax {
   274  		i := int(uint(bot+top) >> 1)
   275  		if a.ranges[i].contains(base.addr()) {
   276  			// a.ranges[i] contains base, so
   277  			// its successor is the next index.
   278  			return i + 1
   279  		}
   280  		if base.lessThan(a.ranges[i].base) {
   281  			// In this case i might actually be
   282  			// the successor, but we can't be sure
   283  			// until we check the ones before it.
   284  			top = i
   285  		} else {
   286  			// In this case we know base is
   287  			// greater than or equal to a.ranges[i].limit-1,
   288  			// so i is definitely not the successor.
   289  			// We already checked i, so pick the next
   290  			// one.
   291  			bot = i + 1
   292  		}
   293  	}
   294  	// There are top-bot candidates left, so
   295  	// iterate over them and find the first that
   296  	// base is strictly less than.
   297  	for i := bot; i < top; i++ {
   298  		if base.lessThan(a.ranges[i].base) {
   299  			return i
   300  		}
   301  	}
   302  	return top
   303  }
   304  
   305  // findAddrGreaterEqual returns the smallest address represented by a
   306  // that is >= addr. Thus, if the address is represented by a,
   307  // then it returns addr. The second return value indicates whether
   308  // such an address exists for addr in a. That is, if addr is larger than
   309  // any address known to a, the second return value will be false.
   310  func (a *addrRanges) findAddrGreaterEqual(addr uintptr) (uintptr, bool) {
   311  	i := a.findSucc(addr)
   312  	if i == 0 {
   313  		return a.ranges[0].base.addr(), true
   314  	}
   315  	if a.ranges[i-1].contains(addr) {
   316  		return addr, true
   317  	}
   318  	if i < len(a.ranges) {
   319  		return a.ranges[i].base.addr(), true
   320  	}
   321  	return 0, false
   322  }
   323  
   324  // contains returns true if a covers the address addr.
   325  func (a *addrRanges) contains(addr uintptr) bool {
   326  	i := a.findSucc(addr)
   327  	if i == 0 {
   328  		return false
   329  	}
   330  	return a.ranges[i-1].contains(addr)
   331  }
   332  
   333  // add inserts a new address range to a.
   334  //
   335  // r must not overlap with any address range in a and r.size() must be > 0.
   336  func (a *addrRanges) add(r addrRange) {
   337  	// The copies in this function are potentially expensive, but this data
   338  	// structure is meant to represent the Go heap. At worst, copying this
   339  	// would take ~160µs assuming a conservative copying rate of 25 GiB/s (the
   340  	// copy will almost never trigger a page fault) for a 1 TiB heap with 4 MiB
   341  	// arenas which is completely discontiguous. ~160µs is still a lot, but in
   342  	// practice most platforms have 64 MiB arenas (which cuts this by a factor
   343  	// of 16) and Go heaps are usually mostly contiguous, so the chance that
   344  	// an addrRanges even grows to that size is extremely low.
   345  
   346  	// An empty range has no effect on the set of addresses represented
   347  	// by a, but passing a zero-sized range is almost always a bug.
   348  	if r.size() == 0 {
   349  		print("runtime: range = {", hex(r.base.addr()), ", ", hex(r.limit.addr()), "}\n")
   350  		throw("attempted to add zero-sized address range")
   351  	}
   352  	// Because we assume r is not currently represented in a,
   353  	// findSucc gives us our insertion index.
   354  	i := a.findSucc(r.base.addr())
   355  	coalescesDown := i > 0 && a.ranges[i-1].limit.equal(r.base)
   356  	coalescesUp := i < len(a.ranges) && r.limit.equal(a.ranges[i].base)
   357  	if coalescesUp && coalescesDown {
   358  		// We have neighbors and they both border us.
   359  		// Merge a.ranges[i-1], r, and a.ranges[i] together into a.ranges[i-1].
   360  		a.ranges[i-1].limit = a.ranges[i].limit
   361  
   362  		// Delete a.ranges[i].
   363  		copy(a.ranges[i:], a.ranges[i+1:])
   364  		a.ranges = a.ranges[:len(a.ranges)-1]
   365  	} else if coalescesDown {
   366  		// We have a neighbor at a lower address only and it borders us.
   367  		// Merge the new space into a.ranges[i-1].
   368  		a.ranges[i-1].limit = r.limit
   369  	} else if coalescesUp {
   370  		// We have a neighbor at a higher address only and it borders us.
   371  		// Merge the new space into a.ranges[i].
   372  		a.ranges[i].base = r.base
   373  	} else {
   374  		// We may or may not have neighbors which don't border us.
   375  		// Add the new range.
   376  		if len(a.ranges)+1 > cap(a.ranges) {
   377  			// Grow the array. Note that this leaks the old array, but since
   378  			// we're doubling we have at most 2x waste. For a 1 TiB heap and
   379  			// 4 MiB arenas which are all discontiguous (both very conservative
   380  			// assumptions), this would waste at most 4 MiB of memory.
   381  			oldRanges := a.ranges
   382  			ranges := (*notInHeapSlice)(unsafe.Pointer(&a.ranges))
   383  			ranges.len = len(oldRanges) + 1
   384  			ranges.cap = cap(oldRanges) * 2
   385  			ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), goarch.PtrSize, a.sysStat))
   386  
   387  			// Copy in the old array, but make space for the new range.
   388  			copy(a.ranges[:i], oldRanges[:i])
   389  			copy(a.ranges[i+1:], oldRanges[i:])
   390  		} else {
   391  			a.ranges = a.ranges[:len(a.ranges)+1]
   392  			copy(a.ranges[i+1:], a.ranges[i:])
   393  		}
   394  		a.ranges[i] = r
   395  	}
   396  	a.totalBytes += r.size()
   397  }
   398  
   399  // removeLast removes and returns the highest-addressed contiguous range
   400  // of a, or the last nBytes of that range, whichever is smaller. If a is
   401  // empty, it returns an empty range.
   402  func (a *addrRanges) removeLast(nBytes uintptr) addrRange {
   403  	if len(a.ranges) == 0 {
   404  		return addrRange{}
   405  	}
   406  	r := a.ranges[len(a.ranges)-1]
   407  	size := r.size()
   408  	if size > nBytes {
   409  		newEnd := r.limit.sub(nBytes)
   410  		a.ranges[len(a.ranges)-1].limit = newEnd
   411  		a.totalBytes -= nBytes
   412  		return addrRange{newEnd, r.limit}
   413  	}
   414  	a.ranges = a.ranges[:len(a.ranges)-1]
   415  	a.totalBytes -= size
   416  	return r
   417  }
   418  
   419  // removeGreaterEqual removes the ranges of a which are above addr, and additionally
   420  // splits any range containing addr.
   421  func (a *addrRanges) removeGreaterEqual(addr uintptr) {
   422  	pivot := a.findSucc(addr)
   423  	if pivot == 0 {
   424  		// addr is before all ranges in a.
   425  		a.totalBytes = 0
   426  		a.ranges = a.ranges[:0]
   427  		return
   428  	}
   429  	removed := uintptr(0)
   430  	for _, r := range a.ranges[pivot:] {
   431  		removed += r.size()
   432  	}
   433  	if r := a.ranges[pivot-1]; r.contains(addr) {
   434  		removed += r.size()
   435  		r = r.removeGreaterEqual(addr)
   436  		if r.size() == 0 {
   437  			pivot--
   438  		} else {
   439  			removed -= r.size()
   440  			a.ranges[pivot-1] = r
   441  		}
   442  	}
   443  	a.ranges = a.ranges[:pivot]
   444  	a.totalBytes -= removed
   445  }
   446  
   447  // cloneInto makes a deep clone of a's state into b, re-using
   448  // b's ranges if able.
   449  func (a *addrRanges) cloneInto(b *addrRanges) {
   450  	if len(a.ranges) > cap(b.ranges) {
   451  		// Grow the array.
   452  		ranges := (*notInHeapSlice)(unsafe.Pointer(&b.ranges))
   453  		ranges.len = 0
   454  		ranges.cap = cap(a.ranges)
   455  		ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), goarch.PtrSize, b.sysStat))
   456  	}
   457  	b.ranges = b.ranges[:len(a.ranges)]
   458  	b.totalBytes = a.totalBytes
   459  	copy(b.ranges, a.ranges)
   460  }
   461
View as plain text