runtime: incorrect sanity checks in the page allocator

[rasky]

While investigating the optimizations performed by my prove CL 196679, I found out these two instances of what looks like dead code:

go/src/runtime/mpagealloc.go

Lines 726 to 734 in d99fe1f

	j, searchIdx := s.chunkOf(ci).find(npages, 0)
	if j < 0 {
	// We couldn't find any space in this chunk despite the summaries telling
	// us it should be there. There's likely a bug, so dump some state and throw.
	sum := s.summary[len(s.summary)-1][i]
	print("runtime: summary[", len(s.summary)-1, "][", i, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
	print("runtime: npages = ", npages, "\n")
	throw("bad summary data")
	}

go/src/runtime/mpagealloc.go

Lines 768 to 773 in d99fe1f

	j, searchIdx := s.chunkOf(i).find(npages, chunkPageIndex(s.searchAddr))
	if j < 0 {
	print("runtime: max = ", max, ", npages = ", npages, "\n")
	print("runtime: searchIdx = ", chunkPageIndex(s.searchAddr), ", s.searchAddr = ", hex(s.searchAddr), "\n")
	throw("bad summary data")
	}

That branch is never taken because pallocBits.find() return an unsigned number:

go/src/runtime/mpallocbits.go

Lines 197 to 206 in d99fe1f

	// find searches for npages contiguous free pages in pallocBits and returns
	// the index where that run starts, as well as the index of the first free page
	// it found in the search. searchIdx represents the first known free page and
	// where to begin the search from.
	//
	// If find fails to find any free space, it returns an index of ^uint(0) and
	// the new searchIdx should be ignored.
	//
	// Note that if npages == 1, the two returned values will always be identical.
	func (b *pallocBits) find(npages uintptr, searchIdx uint) (uint, uint) {

Given the documentation, it looks like the failure is reported as ^uint(0) so the above checks are probably wrong.

/cc @aclements @mknyszek

[mknyszek]

Ah! Thank you. I'll fix that right away.

Earlier on in the review process the return value was indeed an int, but this was used as a shift in multiple places, so I changed the whole pallocBits API to return uints.

Luckily these are just sanity checks, but if there is a bug in the page allocator, it could lead to bad pointers being returned (and possibly memory corruption).

[gopherbot]

Change https://golang.org/cl/226297 mentions this issue: runtime: check the sanity condition in the page allocator

[mknyszek]

Uploaded a fix. We may want to backport this. Like I said before, if there's a bug in the page allocator that would cause these sanity checks to fail, it would manifest as memory corruption as opposed to the immediate failure it was supposed to be.

CC @bcmills who has been tracking a bunch of the memory corruption issues.
CC @randall77 @cherrymui who have been looking into some of the memory corruption issues.

[rasky]

I wonder whether this should become a vet check. I think with vet, we can at least find very simple instance (eg: unsigned number < 0); prove is able to find similar always-true or always-false conditions in more complicated situations which vet wouldn't be able to; but prove of course cannot emit a compile-time error.

Maybe this should go into what @dr2chase was doing, that is a log of "important information" written by the compiler during compilation.