aboutsummaryrefslogtreecommitdiff
path: root/src/runtime
diff options
context:
space:
mode:
Diffstat (limited to 'src/runtime')
-rw-r--r--src/runtime/export_test.go22
-rw-r--r--src/runtime/mpagecache.go154
-rw-r--r--src/runtime/mpagecache_test.go364
-rw-r--r--src/runtime/mpallocbits.go12
4 files changed, 552 insertions, 0 deletions
diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go
index 48628370db..b1ebfba0d1 100644
--- a/src/runtime/export_test.go
+++ b/src/runtime/export_test.go
@@ -684,6 +684,25 @@ func (d *PallocData) Scavenged() *PallocBits {
// Expose fillAligned for testing.
func FillAligned(x uint64, m uint) uint64 { return fillAligned(x, m) }
+// Expose pageCache for testing.
+type PageCache pageCache
+
+const PageCachePages = pageCachePages
+
+func NewPageCache(base uintptr, cache, scav uint64) PageCache {
+ return PageCache(pageCache{base: base, cache: cache, scav: scav})
+}
+func (c *PageCache) Empty() bool { return (*pageCache)(c).empty() }
+func (c *PageCache) Base() uintptr { return (*pageCache)(c).base }
+func (c *PageCache) Cache() uint64 { return (*pageCache)(c).cache }
+func (c *PageCache) Scav() uint64 { return (*pageCache)(c).scav }
+func (c *PageCache) Alloc(npages uintptr) (uintptr, uintptr) {
+ return (*pageCache)(c).alloc(npages)
+}
+func (c *PageCache) Flush(s *PageAlloc) {
+ (*pageCache)(c).flush((*pageAlloc)(s))
+}
+
// Expose chunk index type.
type ChunkIdx chunkIdx
@@ -694,6 +713,9 @@ type PageAlloc pageAlloc
func (p *PageAlloc) Alloc(npages uintptr) (uintptr, uintptr) {
return (*pageAlloc)(p).alloc(npages)
}
+func (p *PageAlloc) AllocToCache() PageCache {
+ return PageCache((*pageAlloc)(p).allocToCache())
+}
func (p *PageAlloc) Free(base, npages uintptr) {
(*pageAlloc)(p).free(base, npages)
}
diff --git a/src/runtime/mpagecache.go b/src/runtime/mpagecache.go
new file mode 100644
index 0000000000..6581d40801
--- /dev/null
+++ b/src/runtime/mpagecache.go
@@ -0,0 +1,154 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime
+
+import (
+ "math/bits"
+ "unsafe"
+)
+
+const pageCachePages = 8 * unsafe.Sizeof(pageCache{}.cache)
+
+// pageCache represents a per-p cache of pages the allocator can
+// allocate from without a lock. More specifically, it represents
+// a pageCachePages*pageSize chunk of memory with 0 or more free
+// pages in it.
+type pageCache struct {
+ base uintptr // base address of the chunk
+ cache uint64 // 64-bit bitmap representing free pages (1 means free)
+ scav uint64 // 64-bit bitmap representing scavenged pages (1 means scavenged)
+}
+
+// empty returns true if the pageCache has any free pages, and false
+// otherwise.
+func (c *pageCache) empty() bool {
+ return c.cache == 0
+}
+
+// alloc allocates npages from the page cache and is the main entry
+// point for allocation.
+//
+// Returns a base address and the amount of scavenged memory in the
+// allocated region in bytes.
+//
+// Returns a base address of zero on failure, in which case the
+// amount of scavenged memory should be ignored.
+func (c *pageCache) alloc(npages uintptr) (uintptr, uintptr) {
+ if c.cache == 0 {
+ return 0, 0
+ }
+ if npages == 1 {
+ i := uintptr(bits.TrailingZeros64(c.cache))
+ scav := (c.scav >> i) & 1
+ c.cache &^= 1 << i // set bit to mark in-use
+ c.scav &^= 1 << i // clear bit to mark unscavenged
+ return c.base + i*pageSize, uintptr(scav) * pageSize
+ }
+ return c.allocN(npages)
+}
+
+// allocN is a helper which attempts to allocate npages worth of pages
+// from the cache. It represents the general case for allocating from
+// the page cache.
+//
+// Returns a base address and the amount of scavenged memory in the
+// allocated region in bytes.
+func (c *pageCache) allocN(npages uintptr) (uintptr, uintptr) {
+ i := findBitRange64(c.cache, uint(npages))
+ if i >= 64 {
+ return 0, 0
+ }
+ mask := ((uint64(1) << npages) - 1) << i
+ scav := bits.OnesCount64(c.scav & mask)
+ c.cache &^= mask // mark in-use bits
+ c.scav &^= mask // clear scavenged bits
+ return c.base + uintptr(i*pageSize), uintptr(scav) * pageSize
+}
+
+// flush empties out unallocated free pages in the given cache
+// into s. Then, it clears the cache, such that empty returns
+// true.
+//
+// s.mheapLock must be held or the world must be stopped.
+func (c *pageCache) flush(s *pageAlloc) {
+ if c.empty() {
+ return
+ }
+ ci := chunkIndex(c.base)
+ pi := chunkPageIndex(c.base)
+
+ // This method is called very infrequently, so just do the
+ // slower, safer thing by iterating over each bit individually.
+ for i := uint(0); i < 64; i++ {
+ if c.cache&(1<<i) != 0 {
+ s.chunks[ci].free1(pi + i)
+ }
+ if c.scav&(1<<i) != 0 {
+ s.chunks[ci].scavenged.setRange(pi+i, 1)
+ }
+ }
+ // Since this is a lot like a free, we need to make sure
+ // we update the searchAddr just like free does.
+ if s.compareSearchAddrTo(c.base) < 0 {
+ s.searchAddr = c.base
+ }
+ s.update(c.base, pageCachePages, false, false)
+ *c = pageCache{}
+}
+
+// allocToCache acquires a pageCachePages-aligned chunk of free pages which
+// may not be contiguous, and returns a pageCache structure which owns the
+// chunk.
+//
+// s.mheapLock must be held.
+func (s *pageAlloc) allocToCache() pageCache {
+ // If the searchAddr refers to a region which has a higher address than
+ // any known chunk, then we know we're out of memory.
+ if chunkIndex(s.searchAddr) >= s.end {
+ return pageCache{}
+ }
+ c := pageCache{}
+ ci := chunkIndex(s.searchAddr) // chunk index
+ if s.summary[len(s.summary)-1][ci] != 0 {
+ // Fast path: there's free pages at or near the searchAddr address.
+ j, _ := s.chunks[ci].find(1, chunkPageIndex(s.searchAddr))
+ if j < 0 {
+ throw("bad summary data")
+ }
+ c = pageCache{
+ base: chunkBase(ci) + alignDown(uintptr(j), 64)*pageSize,
+ cache: ^s.chunks[ci].pages64(j),
+ scav: s.chunks[ci].scavenged.block64(j),
+ }
+ } else {
+ // Slow path: the searchAddr address had nothing there, so go find
+ // the first free page the slow way.
+ addr, _ := s.find(1)
+ if addr == 0 {
+ // We failed to find adequate free space, so mark the searchAddr as OoM
+ // and return an empty pageCache.
+ s.searchAddr = maxSearchAddr
+ return pageCache{}
+ }
+ ci := chunkIndex(addr)
+ c = pageCache{
+ base: alignDown(addr, 64*pageSize),
+ cache: ^s.chunks[ci].pages64(chunkPageIndex(addr)),
+ scav: s.chunks[ci].scavenged.block64(chunkPageIndex(addr)),
+ }
+ }
+
+ // Set the bits as allocated and clear the scavenged bits.
+ s.allocRange(c.base, pageCachePages)
+
+ // Update as an allocation, but note that it's not contiguous.
+ s.update(c.base, pageCachePages, false, true)
+
+ // We're always searching for the first free page, and we always know the
+ // up to pageCache size bits will be allocated, so we can always move the
+ // searchAddr past the cache.
+ s.searchAddr = c.base + pageSize*pageCachePages
+ return c
+}
diff --git a/src/runtime/mpagecache_test.go b/src/runtime/mpagecache_test.go
new file mode 100644
index 0000000000..6fdaa04d72
--- /dev/null
+++ b/src/runtime/mpagecache_test.go
@@ -0,0 +1,364 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime_test
+
+import (
+ "math/rand"
+ . "runtime"
+ "testing"
+)
+
+func checkPageCache(t *testing.T, got, want PageCache) {
+ if got.Base() != want.Base() {
+ t.Errorf("bad pageCache base: got 0x%x, want 0x%x", got.Base(), want.Base())
+ }
+ if got.Cache() != want.Cache() {
+ t.Errorf("bad pageCache bits: got %016x, want %016x", got.Base(), want.Base())
+ }
+ if got.Scav() != want.Scav() {
+ t.Errorf("bad pageCache scav: got %016x, want %016x", got.Scav(), want.Scav())
+ }
+}
+
+func TestPageCacheAlloc(t *testing.T) {
+ base := PageBase(BaseChunkIdx, 0)
+ type hit struct {
+ npages uintptr
+ base uintptr
+ scav uintptr
+ }
+ tests := map[string]struct {
+ cache PageCache
+ hits []hit
+ }{
+ "Empty": {
+ cache: NewPageCache(base, 0, 0),
+ hits: []hit{
+ {1, 0, 0},
+ {2, 0, 0},
+ {3, 0, 0},
+ {4, 0, 0},
+ {5, 0, 0},
+ {11, 0, 0},
+ {12, 0, 0},
+ {16, 0, 0},
+ {27, 0, 0},
+ {32, 0, 0},
+ {43, 0, 0},
+ {57, 0, 0},
+ {64, 0, 0},
+ {121, 0, 0},
+ },
+ },
+ "Lo1": {
+ cache: NewPageCache(base, 0x1, 0x1),
+ hits: []hit{
+ {1, base, PageSize},
+ {1, 0, 0},
+ {10, 0, 0},
+ },
+ },
+ "Hi1": {
+ cache: NewPageCache(base, 0x1<<63, 0x1),
+ hits: []hit{
+ {1, base + 63*PageSize, 0},
+ {1, 0, 0},
+ {10, 0, 0},
+ },
+ },
+ "Swiss1": {
+ cache: NewPageCache(base, 0x20005555, 0x5505),
+ hits: []hit{
+ {2, 0, 0},
+ {1, base, PageSize},
+ {1, base + 2*PageSize, PageSize},
+ {1, base + 4*PageSize, 0},
+ {1, base + 6*PageSize, 0},
+ {1, base + 8*PageSize, PageSize},
+ {1, base + 10*PageSize, PageSize},
+ {1, base + 12*PageSize, PageSize},
+ {1, base + 14*PageSize, PageSize},
+ {1, base + 29*PageSize, 0},
+ {1, 0, 0},
+ {10, 0, 0},
+ },
+ },
+ "Lo2": {
+ cache: NewPageCache(base, 0x3, 0x2<<62),
+ hits: []hit{
+ {2, base, 0},
+ {2, 0, 0},
+ {1, 0, 0},
+ },
+ },
+ "Hi2": {
+ cache: NewPageCache(base, 0x3<<62, 0x3<<62),
+ hits: []hit{
+ {2, base + 62*PageSize, 2 * PageSize},
+ {2, 0, 0},
+ {1, 0, 0},
+ },
+ },
+ "Swiss2": {
+ cache: NewPageCache(base, 0x3333<<31, 0x3030<<31),
+ hits: []hit{
+ {2, base + 31*PageSize, 0},
+ {2, base + 35*PageSize, 2 * PageSize},
+ {2, base + 39*PageSize, 0},
+ {2, base + 43*PageSize, 2 * PageSize},
+ {2, 0, 0},
+ },
+ },
+ "Hi53": {
+ cache: NewPageCache(base, ((uint64(1)<<53)-1)<<10, ((uint64(1)<<16)-1)<<10),
+ hits: []hit{
+ {53, base + 10*PageSize, 16 * PageSize},
+ {53, 0, 0},
+ {1, 0, 0},
+ },
+ },
+ "Full53": {
+ cache: NewPageCache(base, ^uint64(0), ((uint64(1)<<16)-1)<<10),
+ hits: []hit{
+ {53, base, 16 * PageSize},
+ {53, 0, 0},
+ {1, base + 53*PageSize, 0},
+ },
+ },
+ "Full64": {
+ cache: NewPageCache(base, ^uint64(0), ^uint64(0)),
+ hits: []hit{
+ {64, base, 64 * PageSize},
+ {64, 0, 0},
+ {1, 0, 0},
+ },
+ },
+ "FullMixed": {
+ cache: NewPageCache(base, ^uint64(0), ^uint64(0)),
+ hits: []hit{
+ {5, base, 5 * PageSize},
+ {7, base + 5*PageSize, 7 * PageSize},
+ {1, base + 12*PageSize, 1 * PageSize},
+ {23, base + 13*PageSize, 23 * PageSize},
+ {63, 0, 0},
+ {3, base + 36*PageSize, 3 * PageSize},
+ {3, base + 39*PageSize, 3 * PageSize},
+ {3, base + 42*PageSize, 3 * PageSize},
+ {12, base + 45*PageSize, 12 * PageSize},
+ {11, 0, 0},
+ {4, base + 57*PageSize, 4 * PageSize},
+ {4, 0, 0},
+ {6, 0, 0},
+ {36, 0, 0},
+ {2, base + 61*PageSize, 2 * PageSize},
+ {3, 0, 0},
+ {1, base + 63*PageSize, 1 * PageSize},
+ {4, 0, 0},
+ {2, 0, 0},
+ {62, 0, 0},
+ {1, 0, 0},
+ },
+ },
+ }
+ for name, test := range tests {
+ test := test
+ t.Run(name, func(t *testing.T) {
+ c := test.cache
+ for i, h := range test.hits {
+ b, s := c.Alloc(h.npages)
+ if b != h.base {
+ t.Fatalf("bad alloc base #%d: got 0x%x, want 0x%x", i, b, h.base)
+ }
+ if s != h.scav {
+ t.Fatalf("bad alloc scav #%d: got %d, want %d", i, s, h.scav)
+ }
+ }
+ })
+ }
+}
+
+func TestPageCacheFlush(t *testing.T) {
+ bits64ToBitRanges := func(bits uint64, base uint) []BitRange {
+ var ranges []BitRange
+ start, size := uint(0), uint(0)
+ for i := 0; i < 64; i++ {
+ if bits&(1<<i) != 0 {
+ if size == 0 {
+ start = uint(i) + base
+ }
+ size++
+ } else {
+ if size != 0 {
+ ranges = append(ranges, BitRange{start, size})
+ size = 0
+ }
+ }
+ }
+ if size != 0 {
+ ranges = append(ranges, BitRange{start, size})
+ }
+ return ranges
+ }
+ runTest := func(t *testing.T, base uint, cache, scav uint64) {
+ // Set up the before state.
+ beforeAlloc := map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{base, 64}},
+ }
+ beforeScav := map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {},
+ }
+ b := NewPageAlloc(beforeAlloc, beforeScav)
+ defer FreePageAlloc(b)
+
+ // Create and flush the cache.
+ c := NewPageCache(PageBase(BaseChunkIdx, base), cache, scav)
+ c.Flush(b)
+ if !c.Empty() {
+ t.Errorf("pageCache flush did not clear cache")
+ }
+
+ // Set up the expected after state.
+ afterAlloc := map[ChunkIdx][]BitRange{
+ BaseChunkIdx: bits64ToBitRanges(^cache, base),
+ }
+ afterScav := map[ChunkIdx][]BitRange{
+ BaseChunkIdx: bits64ToBitRanges(scav, base),
+ }
+ want := NewPageAlloc(afterAlloc, afterScav)
+ defer FreePageAlloc(want)
+
+ // Check to see if it worked.
+ checkPageAlloc(t, want, b)
+ }
+
+ // Empty.
+ runTest(t, 0, 0, 0)
+
+ // Full.
+ runTest(t, 0, ^uint64(0), ^uint64(0))
+
+ // Random.
+ for i := 0; i < 100; i++ {
+ // Generate random valid base within a chunk.
+ base := uint(rand.Intn(PallocChunkPages/64)) * 64
+
+ // Generate random cache.
+ cache := rand.Uint64()
+ scav := rand.Uint64() & cache
+
+ // Run the test.
+ runTest(t, base, cache, scav)
+ }
+}
+
+func TestPageAllocAllocToCache(t *testing.T) {
+ tests := map[string]struct {
+ before map[ChunkIdx][]BitRange
+ scav map[ChunkIdx][]BitRange
+ hits []PageCache // expected base addresses and patterns
+ after map[ChunkIdx][]BitRange
+ }{
+ "AllFree": {
+ before: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {},
+ },
+ scav: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{1, 1}, {64, 64}},
+ },
+ hits: []PageCache{
+ NewPageCache(PageBase(BaseChunkIdx, 0), ^uint64(0), 0x2),
+ NewPageCache(PageBase(BaseChunkIdx, 64), ^uint64(0), ^uint64(0)),
+ NewPageCache(PageBase(BaseChunkIdx, 128), ^uint64(0), 0),
+ NewPageCache(PageBase(BaseChunkIdx, 192), ^uint64(0), 0),
+ },
+ after: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, 256}},
+ },
+ },
+ "ManyArena": {
+ before: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ BaseChunkIdx + 1: {{0, PallocChunkPages}},
+ BaseChunkIdx + 2: {{0, PallocChunkPages - 64}},
+ },
+ scav: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ BaseChunkIdx + 1: {{0, PallocChunkPages}},
+ BaseChunkIdx + 2: {},
+ },
+ hits: []PageCache{
+ NewPageCache(PageBase(BaseChunkIdx+2, PallocChunkPages-64), ^uint64(0), 0),
+ },
+ after: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ BaseChunkIdx + 1: {{0, PallocChunkPages}},
+ BaseChunkIdx + 2: {{0, PallocChunkPages}},
+ },
+ },
+ "NotContiguous": {
+ before: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ BaseChunkIdx + 0xff: {{0, 0}},
+ },
+ scav: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ BaseChunkIdx + 0xff: {{31, 67}},
+ },
+ hits: []PageCache{
+ NewPageCache(PageBase(BaseChunkIdx+0xff, 0), ^uint64(0), ((uint64(1)<<33)-1)<<31),
+ },
+ after: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ BaseChunkIdx + 0xff: {{0, 64}},
+ },
+ },
+ "First": {
+ before: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, 32}, {33, 31}, {96, 32}},
+ },
+ scav: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{1, 4}, {31, 5}, {66, 2}},
+ },
+ hits: []PageCache{
+ NewPageCache(PageBase(BaseChunkIdx, 0), 1<<32, 1<<32),
+ NewPageCache(PageBase(BaseChunkIdx, 64), (uint64(1)<<32)-1, 0x3<<2),
+ },
+ after: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, 128}},
+ },
+ },
+ "Fail": {
+ before: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ },
+ hits: []PageCache{
+ NewPageCache(0, 0, 0),
+ NewPageCache(0, 0, 0),
+ NewPageCache(0, 0, 0),
+ },
+ after: map[ChunkIdx][]BitRange{
+ BaseChunkIdx: {{0, PallocChunkPages}},
+ },
+ },
+ }
+ for name, v := range tests {
+ v := v
+ t.Run(name, func(t *testing.T) {
+ b := NewPageAlloc(v.before, v.scav)
+ defer FreePageAlloc(b)
+
+ for _, expect := range v.hits {
+ checkPageCache(t, b.AllocToCache(), expect)
+ if t.Failed() {
+ return
+ }
+ }
+ want := NewPageAlloc(v.after, v.scav)
+ defer FreePageAlloc(want)
+
+ checkPageAlloc(t, want, b)
+ })
+ }
+}
diff --git a/src/runtime/mpallocbits.go b/src/runtime/mpallocbits.go
index b460c032bf..669a41e08f 100644
--- a/src/runtime/mpallocbits.go
+++ b/src/runtime/mpallocbits.go
@@ -16,6 +16,11 @@ func (b *pageBits) get(i uint) uint {
return uint((b[i/64] >> (i % 64)) & 1)
}
+// block64 returns the 64-bit aligned block of bits containing the i'th bit.
+func (b *pageBits) block64(i uint) uint64 {
+ return b[i/64]
+}
+
// set sets bit i of pageBits.
func (b *pageBits) set(i uint) {
b[i/64] |= 1 << (i % 64)
@@ -339,6 +344,13 @@ func (b *pallocBits) freeAll() {
(*pageBits)(b).clearAll()
}
+// pages64 returns a 64-bit bitmap representing a block of 64 pages aligned
+// to 64 pages. The returned block of pages is the one containing the i'th
+// page in this pallocBits. Each bit represents whether the page is in-use.
+func (b *pallocBits) pages64(i uint) uint64 {
+ return (*pageBits)(b).block64(i)
+}
+
// findBitRange64 returns the bit index of the first set of
// n consecutive 1 bits. If no consecutive set of 1 bits of
// size n may be found in c, then it returns an integer >= 64.
generated by cgit v1.3-5-g9baa (git 2.53.0) at 2026-04-17 15:59:05 +0000