From 76bce1dd52b0c2a06d48bf7db4e89e8dec47c507 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Tue, 14 Jul 2020 21:45:16 +0000 Subject: [PATCH] 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(-) 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 -- 2.50.0