From 14849f0fa57c67996bb00bd42bb14cef9f4e9a1e Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Mon, 12 Aug 2019 22:30:39 +0000 Subject: [PATCH] runtime: add new page allocator constants and description This change is the first of a series of changes which replace the current page allocator (which is based on the contents of mgclarge.go and some of mheap.go) with one based on free/used bitmaps. It adds in the key constants for the page allocator as well as a comment describing the implementation. Updates #35112. Change-Id: I839d3a07f46842ad379701d27aa691885afdba63 Reviewed-on: https://go-review.googlesource.com/c/go/+/190619 Run-TryBot: Michael Knyszek Reviewed-by: Keith Randall Reviewed-by: Austin Clements --- src/runtime/mpagealloc.go | 72 +++++++++++++++++++++++++++++++++ src/runtime/mpagealloc_32bit.go | 23 +++++++++++ src/runtime/mpagealloc_64bit.go | 14 +++++++ 3 files changed, 109 insertions(+) create mode 100644 src/runtime/mpagealloc.go create mode 100644 src/runtime/mpagealloc_32bit.go create mode 100644 src/runtime/mpagealloc_64bit.go diff --git a/src/runtime/mpagealloc.go b/src/runtime/mpagealloc.go new file mode 100644 index 0000000000..1818c7a353 --- /dev/null +++ b/src/runtime/mpagealloc.go @@ -0,0 +1,72 @@ +// 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. + +// Page allocator. +// +// The page allocator manages mapped pages (defined by pageSize, NOT +// physPageSize) for allocation and re-use. It is embedded into mheap. +// +// Pages are managed using a bitmap that is sharded into chunks. +// In the bitmap, 1 means in-use, and 0 means free. The bitmap spans the +// process's address space. Chunks are allocated using a SLAB allocator +// and pointers to chunks are managed in one large array, which is mapped +// in as needed. +// +// The bitmap is efficiently searched by using a radix tree in combination +// with fast bit-wise intrinsics. Allocation is performed using an address-ordered +// first-fit approach. +// +// Each entry in the radix tree is a summary that describes three properties of +// a particular region of the address space: the number of contiguous free pages +// at the start and end of the region it represents, and the maximum number of +// contiguous free pages found anywhere in that region. +// +// Each level of the radix tree is stored as one contiguous array, which represents +// a different granularity of subdivision of the processes' address space. Thus, this +// radix tree is actually implicit in these large arrays, as opposed to having explicit +// dynamically-allocated pointer-based node structures. Naturally, these arrays may be +// quite large for system with large address spaces, so in these cases they are mapped +// into memory as needed. The leaf summaries of the tree correspond to a bitmap chunk. +// +// The root level (referred to as L0 and index 0 in pageAlloc.summary) has each +// summary represent the largest section of address space (16 GiB on 64-bit systems), +// with each subsequent level representing successively smaller subsections until we +// reach the finest granularity at the leaves, a chunk. +// +// More specifically, each summary in each level (except for leaf summaries) +// represents some number of entries in the following level. For example, each +// summary in the root level may represent a 16 GiB region of address space, +// and in the next level there could be 8 corresponding entries which represent 2 +// GiB subsections of that 16 GiB region, each of which could correspond to 8 +// entries in the next level which each represent 256 MiB regions, and so on. +// +// Thus, this design only scales to heaps so large, but can always be extended to +// larger heaps by simply adding levels to the radix tree, which mostly costs +// additional virtual address space. The choice of managing large arrays also means +// that a large amount of virtual address space may be reserved by the runtime. + +package runtime + +const ( + // The size of a bitmap chunk, i.e. the amount of bits (that is, pages) to consider + // in the bitmap at once. + pallocChunkPages = 1 << logPallocChunkPages + pallocChunkBytes = pallocChunkPages * pageSize + logPallocChunkPages = 9 + logPallocChunkBytes = logPallocChunkPages + pageShift + + // The number of radix bits for each level. + // + // The value of 3 is chosen such that the block of summaries we need to scan at + // each level fits in 64 bytes (2^3 summaries * 8 bytes per summary), which is + // close to the L1 cache line width on many systems. Also, a value of 3 fits 4 tree + // levels perfectly into the 21-bit mallocBits summary field at the root level. + // + // The following equation explains how each of the constants relate: + // summaryL0Bits + (summaryLevels-1)*summaryLevelBits + logPallocChunkBytes = heapAddrBits + // + // summaryLevels is an architecture-dependent value defined in mpagealloc_*.go. + summaryLevelBits = 3 + summaryL0Bits = heapAddrBits - logPallocChunkBytes - (summaryLevels-1)*summaryLevelBits +) diff --git a/src/runtime/mpagealloc_32bit.go b/src/runtime/mpagealloc_32bit.go new file mode 100644 index 0000000000..c91b2bbe3f --- /dev/null +++ b/src/runtime/mpagealloc_32bit.go @@ -0,0 +1,23 @@ +// 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. + +// +build 386 arm mips mipsle wasm darwin,arm64 + +// wasm is a treated as a 32-bit architecture for the purposes of the page +// allocator, even though it has 64-bit pointers. This is because any wasm +// pointer always has its top 32 bits as zero, so the effective heap address +// space is only 2^32 bytes in size (see heapAddrBits). + +// darwin/arm64 is treated as a 32-bit architecture for the purposes of the +// page allocator, even though it has 64-bit pointers and a 33-bit address +// space (see heapAddrBits). The 33 bit address space cannot be rounded up +// to 64 bits because there are too many summary levels to fit in just 33 +// bits. + +package runtime + +const ( + // The number of levels in the radix tree. + summaryLevels = 4 +) diff --git a/src/runtime/mpagealloc_64bit.go b/src/runtime/mpagealloc_64bit.go new file mode 100644 index 0000000000..7991f344fc --- /dev/null +++ b/src/runtime/mpagealloc_64bit.go @@ -0,0 +1,14 @@ +// 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. + +// +build amd64 !darwin,arm64 mips64 mips64le ppc64 ppc64le s390x + +// See mpagealloc_32bit.go for why darwin/arm64 is excluded here. + +package runtime + +const ( + // The number of levels in the radix tree. + summaryLevels = 5 +) -- 2.48.1