mranges.go

Documentation: runtime

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