From 4208dbef161c554b30607f48c347a6c97add80b3 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Mon, 28 Oct 2019 19:17:21 +0000 Subject: [PATCH] runtime: make allocNeedsZero lock-free In preparation for a lockless fast path in the page allocator, this change makes it so that checking if an allocation needs to be zeroed may be done atomically. Unfortunately, this means there is a CAS-loop to ensure monotonicity of the zeroedBase value in heapArena. This CAS-loop exits if an allocator acquiring memory further on in the arena wins or if it succeeds. The CAS-loop should have a relatively small amount of contention because of this monotonicity, though it would be ideal if we could just have CAS-ers with the greatest value always win. The CAS-loop is unnecessary in the steady-state, but should bring some start-up performance gains as it's likely cheaper than the additional zeroing required, especially for large allocations. For very large allocations that span arenas, the CAS-loop should be completely uncontended for most of the arenas it touches, it may only encounter contention on the first and last arena. Updates #35112. Change-Id: If3d19198b33f1b1387b71e1ce5902d39a5c0f98e Reviewed-on: https://go-review.googlesource.com/c/go/+/203859 Run-TryBot: Michael Knyszek TryBot-Result: Gobot Gobot Reviewed-by: Austin Clements --- src/runtime/mheap.go | 40 +++++++++++++++++++++++++--------------- 1 file changed, 25 insertions(+), 15 deletions(-) diff --git a/src/runtime/mheap.go b/src/runtime/mheap.go index 6ff82a7089..c2a23267bc 100644 --- a/src/runtime/mheap.go +++ b/src/runtime/mheap.go @@ -256,7 +256,7 @@ type heapArena struct { // needs to be zeroed because the page allocator follows an // address-ordered first-fit policy. // - // Reads and writes are protected by mheap_.lock. + // Read atomically and written with an atomic CAS. zeroedBase uintptr } @@ -1038,29 +1038,29 @@ func (h *mheap) setSpans(base, npage uintptr, s *mspan) { // they're fresh from the operating system. It updates heapArena metadata that is // critical for future page allocations. // -// h must be locked. +// There are no locking constraints on this method. func (h *mheap) allocNeedsZero(base, npage uintptr) (needZero bool) { for npage > 0 { ai := arenaIndex(base) ha := h.arenas[ai.l1()][ai.l2()] + zeroedBase := atomic.Loaduintptr(&ha.zeroedBase) arenaBase := base % heapArenaBytes - if arenaBase > ha.zeroedBase { - // zeroedBase relies on an address-ordered first-fit allocation policy - // for pages. We ended up past the zeroedBase, which means we could be - // allocating in the middle of an arena, and so the assumption - // zeroedBase relies on has been violated. - print("runtime: base = ", hex(base), ", npages = ", npage, "\n") - print("runtime: ai = ", ai, ", ha.zeroedBase = ", ha.zeroedBase, "\n") - throw("pages considered for zeroing in the middle of an arena") - } else if arenaBase < ha.zeroedBase { + if arenaBase < zeroedBase { // We extended into the non-zeroed part of the // arena, so this region needs to be zeroed before use. // + // zeroedBase is monotonically increasing, so if we see this now then + // we can be sure we need to zero this memory region. + // // We still need to update zeroedBase for this arena, and // potentially more arenas. needZero = true } + // We may observe arenaBase > zeroedBase if we're racing with one or more + // allocations which are acquiring memory directly before us in the address + // space. But, because we know no one else is acquiring *this* memory, it's + // still safe to not zero. // Compute how far into the arena we extend into, capped // at heapArenaBytes. @@ -1068,10 +1068,20 @@ func (h *mheap) allocNeedsZero(base, npage uintptr) (needZero bool) { if arenaLimit > heapArenaBytes { arenaLimit = heapArenaBytes } - if arenaLimit > ha.zeroedBase { - // This allocation extends past the zeroed section in - // this arena, so we should bump up the zeroedBase. - ha.zeroedBase = arenaLimit + // Increase ha.zeroedBase so it's >= arenaLimit. + // We may be racing with other updates. + for arenaLimit > zeroedBase { + if atomic.Casuintptr(&ha.zeroedBase, zeroedBase, arenaLimit) { + break + } + zeroedBase = atomic.Loaduintptr(&ha.zeroedBase) + // Sanity check zeroedBase. + if zeroedBase <= arenaLimit && zeroedBase > arenaBase { + // The zeroedBase moved into the space we were trying to + // claim. That's very bad, and indicates someone allocated + // the same region we did. + throw("potentially overlapping in-use allocations detected") + } } // Move base forward and subtract from npage to move into -- 2.50.0