From fe70866d1dc8c44ab19180ecab2b5c5b8628265a Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Wed, 15 Jul 2020 18:56:39 +0000 Subject: runtime: throw on zero-sized range passed to addrRanges.add addrRanges represents a set of addresses. Currently, passing in a zero-sized range will cause that range to be added to the list, even though it doesn't represent any address (addrRanges.contains will still always return false, and findSucc will give surprising results). We could ignore this input, but it's almost always a bug for the calling code to pass in a zero-sized range, so just throw. Change-Id: I8ed09e15b79a3a33e2d0cf5ed55f9e497388e7a5 Reviewed-on: https://go-review.googlesource.com/c/go/+/242817 Run-TryBot: Michael Knyszek TryBot-Result: Go Bot Trust: Michael Knyszek Reviewed-by: Michael Pratt Reviewed-by: Austin Clements --- src/runtime/mranges.go | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'src/runtime/mranges.go') diff --git a/src/runtime/mranges.go b/src/runtime/mranges.go index 2c0eb2c2dd..1109f506a6 100644 --- a/src/runtime/mranges.go +++ b/src/runtime/mranges.go @@ -218,7 +218,7 @@ func (a *addrRanges) contains(addr uintptr) bool { // add inserts a new address range to a. // -// r must not overlap with any address range in a. +// r must not overlap with any address range in a and r.size() must be > 0. func (a *addrRanges) add(r addrRange) { // The copies in this function are potentially expensive, but this data // structure is meant to represent the Go heap. At worst, copying this @@ -229,6 +229,12 @@ func (a *addrRanges) add(r addrRange) { // of 16) and Go heaps are usually mostly contiguous, so the chance that // an addrRanges even grows to that size is extremely low. + // An empty range has no effect on the set of addresses represented + // by a, but passing a zero-sized range is almost always a bug. + if r.size() == 0 { + print("runtime: range = {", hex(r.base.addr()), ", ", hex(r.limit.addr()), "}\n") + throw("attempted to add zero-sized address range") + } // Because we assume r is not currently represented in a, // findSucc gives us our insertion index. i := a.findSucc(r.base.addr()) -- cgit v1.2.1 From 8ebc58452af3a586a3da1f68725bc83c78d4b073 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Wed, 29 Jul 2020 20:25:05 +0000 Subject: runtime: delineate which memstats are system stats with a type This change modifies the type of several mstats fields to be a new type: sysMemStat. This type has the same structure as the fields used to have. The purpose of this change is to make it very clear which stats may be used in various functions for accounting (usually the platform-specific sys* functions, but there are others). Currently there's an implicit understanding that the *uint64 value passed to these functions is some kind of statistic whose value is atomically managed. This understanding isn't inherently problematic, but we're about to change how some stats (which currently use mSysStatInc and mSysStatDec) work, so we want to make it very clear what the various requirements are around "sysStat". This change also removes mSysStatInc and mSysStatDec in favor of a method on sysMemStat. Note that those two functions were originally written the way they were because atomic 64-bit adds required a valid G on ARM, but this hasn't been the case for a very long time (since golang.org/cl/14204, but even before then it wasn't clear if mutexes required a valid G anymore). Today we implement 64-bit adds on ARM with a spinlock table. Change-Id: I4e9b37cf14afc2ae20cf736e874eb0064af086d7 Reviewed-on: https://go-review.googlesource.com/c/go/+/246971 Run-TryBot: Michael Knyszek TryBot-Result: Go Bot Trust: Michael Knyszek Reviewed-by: Michael Pratt --- src/runtime/mranges.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/runtime/mranges.go') diff --git a/src/runtime/mranges.go b/src/runtime/mranges.go index 1109f506a6..16acadcff1 100644 --- a/src/runtime/mranges.go +++ b/src/runtime/mranges.go @@ -160,10 +160,10 @@ type addrRanges struct { totalBytes uintptr // sysStat is the stat to track allocations by this type - sysStat *uint64 + sysStat *sysMemStat } -func (a *addrRanges) init(sysStat *uint64) { +func (a *addrRanges) init(sysStat *sysMemStat) { ranges := (*notInHeapSlice)(unsafe.Pointer(&a.ranges)) ranges.len = 0 ranges.cap = 16 -- cgit v1.2.1 From 76bce1dd52b0c2a06d48bf7db4e89e8dec47c507 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Tue, 14 Jul 2020 21:45:16 +0000 Subject: runtime: implement addrRanges.findSucc with a binary search This change modifies addrRanges.findSucc to more efficiently find the successor range in an addrRanges by using a binary search to narrow down large addrRanges and iterate over no more than 8 addrRanges. This change makes the runtime more robust against systems that may aggressively randomize the address space mappings it gives the runtime (e.g. Fuchsia). For #40191. Change-Id: If529df2abd2edb1b1496d8690ddd284ecd7138c2 Reviewed-on: https://go-review.googlesource.com/c/go/+/242679 Trust: Michael Knyszek Reviewed-by: Austin Clements Reviewed-by: Michael Pratt --- src/runtime/mranges.go | 40 +++++++++++++++++++++++++++++++++------- 1 file changed, 33 insertions(+), 7 deletions(-) (limited to 'src/runtime/mranges.go') diff --git a/src/runtime/mranges.go b/src/runtime/mranges.go index 16acadcff1..84a2c06dbb 100644 --- a/src/runtime/mranges.go +++ b/src/runtime/mranges.go @@ -172,20 +172,46 @@ func (a *addrRanges) init(sysStat *sysMemStat) { a.totalBytes = 0 } -// findSucc returns the first index in a such that base is +// findSucc returns the first index in a such that addr is // less than the base of the addrRange at that index. func (a *addrRanges) findSucc(addr uintptr) int { - // TODO(mknyszek): Consider a binary search for large arrays. - // While iterating over these ranges is potentially expensive, - // the expected number of ranges is small, ideally just 1, - // since Go heaps are usually mostly contiguous. base := offAddr{addr} - for i := range a.ranges { + + // Narrow down the search space via a binary search + // for large addrRanges until we have at most iterMax + // candidates left. + const iterMax = 8 + bot, top := 0, len(a.ranges) + for top-bot > iterMax { + i := ((top - bot) / 2) + bot + if a.ranges[i].contains(base.addr()) { + // a.ranges[i] contains base, so + // its successor is the next index. + return i + 1 + } + if base.lessThan(a.ranges[i].base) { + // In this case i might actually be + // the successor, but we can't be sure + // until we check the ones before it. + top = i + } else { + // In this case we know base is + // greater than or equal to a.ranges[i].limit-1, + // so i is definitely not the successor. + // We already checked i, so pick the next + // one. + bot = i + 1 + } + } + // There are top-bot candidates left, so + // iterate over them and find the first that + // base is strictly less than. + for i := bot; i < top; i++ { if base.lessThan(a.ranges[i].base) { return i } } - return len(a.ranges) + return top } // findAddrGreaterEqual returns the smallest address represented by a -- cgit v1.2.1