From ea5f9b666ccf7affca596be3ab0dc523ca4444fb Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Tue, 28 Apr 2020 21:30:57 +0000 Subject: runtime: use offAddr in more parts of the runtime This change uses the new offAddr type in more parts of the runtime where we've been implicitly switching from the default address space to a contiguous view. The purpose of offAddr is to represent addresses in the contiguous view of the address space, and to make direct computations between real addresses and offset addresses impossible. This change thus improves readability in the runtime. Updates #35788. Change-Id: I4e1c5fed3ed68aa12f49a42b82eb3f46aba82fc1 Reviewed-on: https://go-review.googlesource.com/c/go/+/230718 Run-TryBot: Michael Knyszek TryBot-Result: Gobot Gobot Reviewed-by: Austin Clements --- src/runtime/mpagealloc.go | 132 +++++++++++++++++++++------------------------- 1 file changed, 60 insertions(+), 72 deletions(-) (limited to 'src/runtime/mpagealloc.go') diff --git a/src/runtime/mpagealloc.go b/src/runtime/mpagealloc.go index 5078738b60..a28dd26cb5 100644 --- a/src/runtime/mpagealloc.go +++ b/src/runtime/mpagealloc.go @@ -81,15 +81,14 @@ const ( // there should this change. pallocChunksL2Bits = heapAddrBits - logPallocChunkBytes - pallocChunksL1Bits pallocChunksL1Shift = pallocChunksL2Bits - - // Maximum searchAddr value, which indicates that the heap has no free space. - // - // We subtract arenaBaseOffset because we want this to represent the maximum - // value in the shifted address space, but searchAddr is stored as a regular - // memory address. See arenaBaseOffset for details. - maxSearchAddr = ^uintptr(0) - arenaBaseOffset ) +// Maximum searchAddr value, which indicates that the heap has no free space. +// +// We alias maxOffAddr just to make it clear that this is the maximum address +// for the page allocator's search space. See maxOffAddr for details. +var maxSearchAddr = maxOffAddr + // Global chunk index. // // Represents an index into the leaf level of the radix tree. @@ -134,6 +133,18 @@ func (i chunkIdx) l2() uint { } } +// offAddrToLevelIndex converts an address in the offset address space +// to the index into summary[level] containing addr. +func offAddrToLevelIndex(level int, addr offAddr) int { + return int((addr.a + arenaBaseOffset) >> levelShift[level]) +} + +// levelIndexToOffAddr converts an index into summary[level] into +// the corresponding address in the offset address space. +func levelIndexToOffAddr(level, idx int) offAddr { + return offAddr{(uintptr(idx) << levelShift[level]) - arenaBaseOffset} +} + // addrsToSummaryRange converts base and limit pointers into a range // of entries for the given summary level. // @@ -232,7 +243,7 @@ type pageAlloc struct { // 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 uintptr + searchAddr offAddr // start and end represent the chunk indices // which pageAlloc knows about. It assumes @@ -271,13 +282,13 @@ type pageAlloc struct { // released is the amount of memory released this generation. released uintptr - // scavLWM is the lowest address that the scavenger reached this + // scavLWM is the lowest (offset) address that the scavenger reached this // scavenge generation. - scavLWM uintptr + scavLWM offAddr - // freeHWM is the highest address of a page that was freed to + // freeHWM is the highest (offset) address of a page that was freed to // the page allocator this scavenge generation. - freeHWM uintptr + freeHWM offAddr } // mheap_.lock. This level of indirection makes it possible @@ -319,29 +330,6 @@ func (s *pageAlloc) init(mheapLock *mutex, sysStat *uint64) { s.scav.scavLWM = maxSearchAddr } -// compareSearchAddrTo compares an address against s.searchAddr in a linearized -// view of the address space on systems with discontinuous process address spaces. -// This linearized view is the same one generated by chunkIndex and arenaIndex, -// done by adding arenaBaseOffset. -// -// On systems without a discontinuous address space, it's just a normal comparison. -// -// Returns < 0 if addr is less than s.searchAddr in the linearized address space. -// Returns > 0 if addr is greater than s.searchAddr in the linearized address space. -// Returns 0 if addr and s.searchAddr are equal. -func (s *pageAlloc) compareSearchAddrTo(addr uintptr) int { - // Compare with arenaBaseOffset added because it gives us a linear, contiguous view - // of the heap on architectures with signed address spaces. - lAddr := addr + arenaBaseOffset - lSearchAddr := s.searchAddr + arenaBaseOffset - if lAddr < lSearchAddr { - return -1 - } else if lAddr > lSearchAddr { - return 1 - } - return 0 -} - // chunkOf returns the chunk at the given chunk index. func (s *pageAlloc) chunkOf(ci chunkIdx) *pallocData { return &s.chunks[ci.l1()][ci.l2()] @@ -378,10 +366,10 @@ func (s *pageAlloc) grow(base, size uintptr) { s.inUse.add(makeAddrRange(base, limit)) // A grow operation is a lot like a free operation, so if our - // chunk ends up below the (linearized) s.searchAddr, update - // s.searchAddr to the new address, just like in free. - if s.compareSearchAddrTo(base) < 0 { - s.searchAddr = base + // chunk ends up below s.searchAddr, update s.searchAddr to the + // new address, just like in free. + if b := (offAddr{base}); b.lessThan(s.searchAddr) { + s.searchAddr = b } // Add entries into chunks, which is sparse, if needed. Then, @@ -545,7 +533,7 @@ func (s *pageAlloc) allocRange(base, npages uintptr) uintptr { // searchAddr returned is invalid and must be ignored. // // s.mheapLock must be held. -func (s *pageAlloc) find(npages uintptr) (uintptr, uintptr) { +func (s *pageAlloc) find(npages uintptr) (uintptr, offAddr) { // Search algorithm. // // This algorithm walks each level l of the radix tree from the root level @@ -585,13 +573,13 @@ func (s *pageAlloc) find(npages uintptr) (uintptr, uintptr) { // firstFree is updated by calling foundFree each time free space in the // heap is discovered. // - // At the end of the search, base-arenaBaseOffset is the best new + // At the end of the search, base.addr() is the best new // searchAddr we could deduce in this search. firstFree := struct { - base, bound uintptr + base, bound offAddr }{ - base: 0, - bound: (1< firstFree.bound) { + firstFree.bound = addr.add(size - 1) + } else if !(addr.add(size-1).lessThan(firstFree.base) || firstFree.bound.lessThan(addr)) { // This range only partially overlaps with the firstFree range, // so throw. - print("runtime: addr = ", hex(addr), ", size = ", size, "\n") - print("runtime: base = ", hex(firstFree.base), ", bound = ", hex(firstFree.bound), "\n") + print("runtime: addr = ", hex(addr.addr()), ", size = ", size, "\n") + print("runtime: base = ", hex(firstFree.base.addr()), ", bound = ", hex(firstFree.bound.addr()), "\n") throw("range partially overlaps") } } @@ -642,7 +630,7 @@ nextLevel: // searchAddr on the previous level or we're on the root leve, in which // case the searchAddr should be the same as i after levelShift. j0 := 0 - if searchIdx := int((s.searchAddr + arenaBaseOffset) >> levelShift[l]); searchIdx&^(entriesPerBlock-1) == i { + if searchIdx := offAddrToLevelIndex(l, s.searchAddr); searchIdx&^(entriesPerBlock-1) == i { j0 = searchIdx & (entriesPerBlock - 1) } @@ -668,7 +656,7 @@ nextLevel: // We've encountered a non-zero summary which means // free memory, so update firstFree. - foundFree(uintptr((i+j)<= uint(npages) { @@ -706,8 +694,8 @@ nextLevel: if size >= uint(npages) { // We found a sufficiently large run of free pages straddling // some boundary, so compute the address and return it. - addr := uintptr(i<= s.end { + if chunkIndex(s.searchAddr.addr()) >= s.end { return 0, 0 } // If npages has a chance of fitting in the chunk where the searchAddr is, // search it directly. - searchAddr := uintptr(0) - if pallocChunkPages-chunkPageIndex(s.searchAddr) >= uint(npages) { + searchAddr := minOffAddr + if pallocChunkPages-chunkPageIndex(s.searchAddr.addr()) >= uint(npages) { // npages is guaranteed to be no greater than pallocChunkPages here. - i := chunkIndex(s.searchAddr) + i := chunkIndex(s.searchAddr.addr()) if max := s.summary[len(s.summary)-1][i].max(); max >= uint(npages) { - j, searchIdx := s.chunkOf(i).find(npages, chunkPageIndex(s.searchAddr)) + j, searchIdx := s.chunkOf(i).find(npages, chunkPageIndex(s.searchAddr.addr())) if j == ^uint(0) { print("runtime: max = ", max, ", npages = ", npages, "\n") - print("runtime: searchIdx = ", chunkPageIndex(s.searchAddr), ", s.searchAddr = ", hex(s.searchAddr), "\n") + print("runtime: searchIdx = ", chunkPageIndex(s.searchAddr.addr()), ", s.searchAddr = ", hex(s.searchAddr.addr()), "\n") throw("bad summary data") } addr = chunkBase(i) + uintptr(j)*pageSize - searchAddr = chunkBase(i) + uintptr(searchIdx)*pageSize + searchAddr = offAddr{chunkBase(i) + uintptr(searchIdx)*pageSize} goto Found } } @@ -807,10 +795,10 @@ Found: // Go ahead and actually mark the bits now that we have an address. scav = s.allocRange(addr, npages) - // If we found a higher (linearized) searchAddr, we know that all the - // heap memory before that searchAddr in a linear address space is + // If we found a higher searchAddr, we know that all the + // heap memory before that searchAddr in an offset address space is // allocated, so bump s.searchAddr up to the new one. - if s.compareSearchAddrTo(searchAddr) > 0 { + if s.searchAddr.lessThan(searchAddr) { s.searchAddr = searchAddr } return addr, scav @@ -820,14 +808,14 @@ Found: // // s.mheapLock must be held. func (s *pageAlloc) free(base, npages uintptr) { - // If we're freeing pages below the (linearized) s.searchAddr, update searchAddr. - if s.compareSearchAddrTo(base) < 0 { - s.searchAddr = base + // If we're freeing pages below the s.searchAddr, update searchAddr. + if b := (offAddr{base}); b.lessThan(s.searchAddr) { + s.searchAddr = b } // Update the free high watermark for the scavenger. limit := base + npages*pageSize - 1 - if s.scav.freeHWM < limit { - s.scav.freeHWM = limit + if offLimit := (offAddr{limit}); s.scav.freeHWM.lessThan(offLimit) { + s.scav.freeHWM = offLimit } if npages == 1 { // Fast path: we're clearing a single bit, and we know exactly -- cgit v1.3