runtime: pageAlloc.searchAddr may point to unmapped memory in discontiguous heaps, violating its invariant

[mknyszek]

It's been brought to my attention by the Fuchsia team that in cases where the Go heap is very discontiguous, the documented invariant for (*pageAlloc).searchAddr may be violated, leading to errant segfaults.

Consider the following case.

n                   = 0   1   2   ... i-1 i    i+1 ...
summary[0][n].max() = 0   0   0   ... 0   1    100 ...

Suppose searchAddr points into the region described by summary i-1, and on the last page allocation, it was exhausted. An allocation then comes in looking for, say, 12 consecutive pages. (*pageAlloc).find will look at summary i, and skip over it, but will set the "free window" to the first page of the region described by summary i, which need not be mapped.

In a contiguous heap we're unlikely to run into this case because the first page of i is likely to be mapped, so the summary would be there.

Most operating systems, even when not following the address hints provided to sysReserve in the runtime, tend to keep the heap contiguous. Fuchsia specifically goes out of its way to map memory discontinuously unless a flag (ZX_VM_COMPACT) is passed to the equivalent function.

This is a real problem, even for existing systems. Note that the above scenario need not happen for summary level 0, it can happen at any level (say there's a small hole in the address space due to a region being reserved by the OS or something and we allocate virtual address space around it).

Fixing this problem is not straight-forward without some kind of performance consequences (though it's unclear to me how big those consequences will be).

Fundamentally, this issue arises because we try to update searchAddr "on the way" to allocating memory which may not be the first free page. One simplifying solution is to simply not do that. It means that there will need to be more iteration when allocating, and we're less likely to take the fast path, but it will be correct.

Another option is to actually find the first piece of mapped memory in that region, which would be possible by iterating over (*pageAlloc).inUse (inUse will be large, but the search could be turned into a binary search as per the comment in addrRanges.findSucc). We could also find it by walking down the summaries, but this is unnecessary and is basically like doing the find operation twice, which is a bit wasteful.

A third option is to remove the invariant on searchAddr altogether and just be a lot more strict in all the places where we try to use searchAddr to access summaries directly (mostly on fast paths in the page allocator and scavenger). The trouble with this is that the only efficient way to verify that searchAddr is valid (short of walking the tree, which we're hoping to avoid in these cases!) is to check inUse, but that's not exactly efficient either. In this case, it would likely be better to just always move searchAddr to the right location on the slow path by checking inUse.

My vote is for option 2. It's not terribly complicated, and the change is local to just the find operation. Option 1 might be preferred anyway just because it simplifies find a bunch, though.

This issue should not be considered a blocking issue for Go 1.15 because the bug was technically introduced in Go 1.14, but it should be fixed and probably backported too, since it can cause failures with no workaround.

CC @aclements @prattmic

[mknyszek]

@gopherbot Please open a backport issue to Go 1.14.

[gopherbot]

Backport issue(s) opened: #40192 (for 1.14).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases.

[randall77]

but will set the "free window" to the first page of the region described by summary i, which need not be mapped.

Why then is there a free page indicated in unmapped memory? How is page i not mapped?
I would think all unmapped pages have either max==0 (not allocatable), or max==64 (allocatable, but not allocated yet).

[mknyszek]

@randall77 The higher-level summaries describe large portions of the address space, some of which may not be mapped. IIRC each level-0 summary on linux/amd64 represents 128 GiB of address space. If your heap is small (like one arena in size) then one level-0 summary will indicate that pages are free in that 128 GiB region are free, but not all of that 128 GiB need be mapped. You're right that unmapped pages necessarily have max == 0 at the chunk level (since chunks are <= the arena size), but when describing larger regions there could be a mix of mapped and unmapped memory in there.

Also, d'oh, I forgot to CC you. Sorry about that.

[prattmic]

As an addendum to option two: pageAlloc.find can do a lookup in mheap.arenas to determine if the candidate free window falls in an existing arena as a fast path. If not, it needs to fallback to searching inUse for the first usable page.

[gopherbot]

Change https://golang.org/cl/242680 mentions this issue: runtime: ensure pageAlloc.find returns a valid searchAddr

[gopherbot]

Change https://golang.org/cl/242678 mentions this issue: runtime: add tests for addrRanges.findSucc

[gopherbot]

Change https://golang.org/cl/242677 mentions this issue: runtime: define the AddrRange used for testing in terms of addrRange

[gopherbot]

Change https://golang.org/cl/242679 mentions this issue: runtime: implement addrRanges.findSucc with a binary search

[gopherbot]

Change https://golang.org/cl/246197 mentions this issue: [release-branch.go.1.14] runtime: validate candidate searchAddr in pageAlloc.find