runtime: heap pageAlloc.searchAddr strategy may be wrong

[dreamerjackson]

i read the heap alloc code. and find the pageAlloc.searchAddr may have a problem, as the comment say
i hope someone can review it @mknyszek

type pageAlloc struct {
	// The address to start an allocation search with. It must never
	// point to any memory that is not contained in inUse, i.e.
	// inUse.contains(searchAddr) must always be true.
	//
	// When added with arenaBaseOffset, we guarantee that
	// all valid heap addresses (when also added with
	// arenaBaseOffset) below this value are allocated and
	// not worth searching.
	//
	// Note that adding in arenaBaseOffset transforms addresses
	// to a new address space with a linear view of the full address
	// space on architectures with segmented address spaces.
	searchAddr offAddr

why i think it may have problem? when we find the continue npages in radix tree（code is below）, the searchAddr will increase when j++ into new entry in the same level. but it only mean below searchAddr just not enough contiguous space to alloc npages。but it may can alloc mpages(mpages < npages) below searchAddr。 so next time when we want to alloc mpages, we give up the change to alloc mpages which address below searchAddr, so we can't use the heap Efficiently。
and we may alloc more memory because when we can't find mpages we will grow the memory.

func (s *pageAlloc) find(npages uintptr) (uintptr, offAddr) {
   for j := j0; j < len(entries); j++ {
			..
			// We've encountered a non-zero summary which means
			// free memory, so update firstFree.
			foundFree(levelIndexToOffAddr(l, i+j), (uintptr(1)<<logMaxPages)*pageSize)
			....
		if size >= uint(npages) {
			addr := levelIndexToOffAddr(l, i).add(uintptr(base) * pageSize).addr()
			return addr, firstFree.base
		}
}

and , the searchAddr can only recover when free npages

func (s *pageAlloc) free(base, npages uintptr) {
	// If we're freeing pages below the s.searchAddr, update searchAddr.
	if b := (offAddr{base}); b.lessThan(s.searchAddr) {
		s.searchAddr = b
	}

[mknyszek]

I'm not sure I follow. The invariant of searchAddr is that every page below it is allocated. find makes its best guess as to what the first free page is (that's what the firstFree struct is tracking). It only knows that with certainty when npages=1. It then returns that guess, and alloc decides whether its better than the allocator's current searchAddr. In this way, we'll never miss the lowest-address contiguous block of pages that fits npages because we're only pruning the parts of the search space that we know have zero free memory (or should be, anyway).

That being said, there have been bugs here before. I've written tests for as many cases as I could think of in mpagealloc_test.go. If you can show in a test that the allocator is going to miss some memory, that would be very helpful.

[dreamerjackson]

@mknyszek I tested it carefully and you are right. before i mistake the foundFree in find function.

i just found another detail. in the allocfunction. does we should judge the addr( find function return) near the s.searchAddr?
if addr near s.searchAddr, we should just s.searchAddr += size, so we can get the accurate s.searchAddr. i find we have no change to handle this , if the searchAddr not accurate, it will cause to search in radix tree rather than find in pallocBits in quick path

func (s *pageAlloc) alloc(npages uintptr) (addr uintptr, scav uintptr) {
	 ....
	addr, searchAddr = s.find(npages)
	if s.searchAddr.lessThan(searchAddr) {
		s.searchAddr = searchAddr
	}

       //  here  this is my thought
      if addr nearby  s.searchAddr{
          s.searchAddr += npages size
      }

	return addr, scav
}