1// Copyright 2019 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package runtime 6 7import ( 8 "runtime/internal/sys" 9 "unsafe" 10) 11 12const pageCachePages = 8 * unsafe.Sizeof(pageCache{}.cache) 13 14// pageCache represents a per-p cache of pages the allocator can 15// allocate from without a lock. More specifically, it represents 16// a pageCachePages*pageSize chunk of memory with 0 or more free 17// pages in it. 18type pageCache struct { 19 base uintptr // base address of the chunk 20 cache uint64 // 64-bit bitmap representing free pages (1 means free) 21 scav uint64 // 64-bit bitmap representing scavenged pages (1 means scavenged) 22} 23 24// empty reports whether the page cache has no free pages. 25func (c *pageCache) empty() bool { 26 return c.cache == 0 27} 28 29// alloc allocates npages from the page cache and is the main entry 30// point for allocation. 31// 32// Returns a base address and the amount of scavenged memory in the 33// allocated region in bytes. 34// 35// Returns a base address of zero on failure, in which case the 36// amount of scavenged memory should be ignored. 37func (c *pageCache) alloc(npages uintptr) (uintptr, uintptr) { 38 if c.cache == 0 { 39 return 0, 0 40 } 41 if npages == 1 { 42 i := uintptr(sys.TrailingZeros64(c.cache)) 43 scav := (c.scav >> i) & 1 44 c.cache &^= 1 << i // set bit to mark in-use 45 c.scav &^= 1 << i // clear bit to mark unscavenged 46 return c.base + i*pageSize, uintptr(scav) * pageSize 47 } 48 return c.allocN(npages) 49} 50 51// allocN is a helper which attempts to allocate npages worth of pages 52// from the cache. It represents the general case for allocating from 53// the page cache. 54// 55// Returns a base address and the amount of scavenged memory in the 56// allocated region in bytes. 57func (c *pageCache) allocN(npages uintptr) (uintptr, uintptr) { 58 i := findBitRange64(c.cache, uint(npages)) 59 if i >= 64 { 60 return 0, 0 61 } 62 mask := ((uint64(1) << npages) - 1) << i 63 scav := sys.OnesCount64(c.scav & mask) 64 c.cache &^= mask // mark in-use bits 65 c.scav &^= mask // clear scavenged bits 66 return c.base + uintptr(i*pageSize), uintptr(scav) * pageSize 67} 68 69// flush empties out unallocated free pages in the given cache 70// into s. Then, it clears the cache, such that empty returns 71// true. 72// 73// p.mheapLock must be held. 74// 75// Must run on the system stack because p.mheapLock must be held. 76// 77//go:systemstack 78func (c *pageCache) flush(p *pageAlloc) { 79 assertLockHeld(p.mheapLock) 80 81 if c.empty() { 82 return 83 } 84 ci := chunkIndex(c.base) 85 pi := chunkPageIndex(c.base) 86 87 // This method is called very infrequently, so just do the 88 // slower, safer thing by iterating over each bit individually. 89 for i := uint(0); i < 64; i++ { 90 if c.cache&(1<<i) != 0 { 91 p.chunkOf(ci).free1(pi + i) 92 93 // Update density statistics. 94 p.scav.index.free(ci, pi+i, 1) 95 } 96 if c.scav&(1<<i) != 0 { 97 p.chunkOf(ci).scavenged.setRange(pi+i, 1) 98 } 99 } 100 101 // Since this is a lot like a free, we need to make sure 102 // we update the searchAddr just like free does. 103 if b := (offAddr{c.base}); b.lessThan(p.searchAddr) { 104 p.searchAddr = b 105 } 106 p.update(c.base, pageCachePages, false, false) 107 *c = pageCache{} 108} 109 110// allocToCache acquires a pageCachePages-aligned chunk of free pages which 111// may not be contiguous, and returns a pageCache structure which owns the 112// chunk. 113// 114// p.mheapLock must be held. 115// 116// Must run on the system stack because p.mheapLock must be held. 117// 118//go:systemstack 119func (p *pageAlloc) allocToCache() pageCache { 120 assertLockHeld(p.mheapLock) 121 122 // If the searchAddr refers to a region which has a higher address than 123 // any known chunk, then we know we're out of memory. 124 if chunkIndex(p.searchAddr.addr()) >= p.end { 125 return pageCache{} 126 } 127 c := pageCache{} 128 ci := chunkIndex(p.searchAddr.addr()) // chunk index 129 var chunk *pallocData 130 if p.summary[len(p.summary)-1][ci] != 0 { 131 // Fast path: there's free pages at or near the searchAddr address. 132 chunk = p.chunkOf(ci) 133 j, _ := chunk.find(1, chunkPageIndex(p.searchAddr.addr())) 134 if j == ^uint(0) { 135 throw("bad summary data") 136 } 137 c = pageCache{ 138 base: chunkBase(ci) + alignDown(uintptr(j), 64)*pageSize, 139 cache: ^chunk.pages64(j), 140 scav: chunk.scavenged.block64(j), 141 } 142 } else { 143 // Slow path: the searchAddr address had nothing there, so go find 144 // the first free page the slow way. 145 addr, _ := p.find(1) 146 if addr == 0 { 147 // We failed to find adequate free space, so mark the searchAddr as OoM 148 // and return an empty pageCache. 149 p.searchAddr = maxSearchAddr() 150 return pageCache{} 151 } 152 ci = chunkIndex(addr) 153 chunk = p.chunkOf(ci) 154 c = pageCache{ 155 base: alignDown(addr, 64*pageSize), 156 cache: ^chunk.pages64(chunkPageIndex(addr)), 157 scav: chunk.scavenged.block64(chunkPageIndex(addr)), 158 } 159 } 160 161 // Set the page bits as allocated and clear the scavenged bits, but 162 // be careful to only set and clear the relevant bits. 163 cpi := chunkPageIndex(c.base) 164 chunk.allocPages64(cpi, c.cache) 165 chunk.scavenged.clearBlock64(cpi, c.cache&c.scav /* free and scavenged */) 166 167 // Update as an allocation, but note that it's not contiguous. 168 p.update(c.base, pageCachePages, false, true) 169 170 // Update density statistics. 171 p.scav.index.alloc(ci, uint(sys.OnesCount64(c.cache))) 172 173 // Set the search address to the last page represented by the cache. 174 // Since all of the pages in this block are going to the cache, and we 175 // searched for the first free page, we can confidently start at the 176 // next page. 177 // 178 // However, p.searchAddr is not allowed to point into unmapped heap memory 179 // unless it is maxSearchAddr, so make it the last page as opposed to 180 // the page after. 181 p.searchAddr = offAddr{c.base + pageSize*(pageCachePages-1)} 182 return c 183} 184