Shulou(Shulou.com)05/31 Report--

In this issue, the editor will bring you about how to analyze the memory allocation of Go language. The article is rich in content and analyzed and described from a professional point of view. I hope you can get something after reading this article.

The Go language has a built-in runtime (that is, runtime), which abandons the traditional memory allocation method and manages it independently. This allows you to autonomously implement better memory usage patterns, such as memory pools, pre-allocation, and so on. In this way, system calls are not required for every memory allocation.

The memory allocation algorithm of Golang runtime mainly comes from the TCMalloc algorithm developed by Google for C language, which is called Thread-Caching Malloc. The core idea is to divide memory into multi-level management, so as to reduce the granularity of locks. It manages the available heap memory by two-level allocation: each thread maintains an independent memory pool on its own, allocates memory from this memory pool first, and applies to the global memory pool only when the memory pool is insufficient to avoid frequent competition between different threads for the global memory pool.

Basic concept

When the program starts, Go will first request a piece of memory from the operating system (note that it is only a virtual address space at this time, and will not really allocate memory), cut it into small pieces and manage it itself.

The applied memory block is assigned three regions, which are 512MB, 16GB, and 512GB respectively on X64.

Overview of stacking area

The arena area is what we call the heap area. Go dynamically allocates memory in this area. It divides the memory into 8KB-sized pages, and some pages are combined as mspan.

The bitmap area identifies which addresses in the arena area hold the object, and uses 4bit flag bits to indicate whether the object contains pointer and GC tag information. A byte-sized memory in bitmap corresponds to the memory of four pointer sizes (pointer size 8B) in the arena area, so the size of the bitmap area is 512GB/ (4pointer 8B) = 16GB.

Bitmap arena

Bitmap arena

From the figure above, you can actually see that the high address part of the bitmap points to the low address part of the arena area, that is, the address of the bitmap grows from the high address to the low address.

The spans area holds pointers to mspan (that is, the basic memory management units of some arena-segmented pages, which we'll talk about later), each corresponding to a page, so the size of the spans area is 512GB/8KB*8B=512MB. Dividing by 8KB calculates the number of pages in the arena area, and the final multiplication by 8 calculates the size of all pointers in the spans area. When you create a mspan, you fill the corresponding spans area by page, and when you recycle the object, you can easily find the mspan to which it belongs according to the address.

Memory management unit

The basic unit of memory management in mspan:Go is a large block of memory consisting of a contiguous piece of 8KB pages. Note that the page here is not the same as the page of the operating system itself, it is usually several times the size of the page of the operating system. To sum up: mspan is a double-ended linked list containing the starting address, mspan specification, number of pages, and so on.

Each mspan is split into several object according to the size of its own property, Size Class, and each object can store an object. And a bitmap is used to mark its unused object. The property Size Class determines the size of the object, while mspan is only assigned to objects that are close to the size of the object, of course, the size of the object is smaller than the size of the object. There is another concept: Span Class, which has the same meaning as Size Class.

Size_Class = Span_Class / 2

This is because each Size Class actually has two mspan, that is, two Span Class. One of them is assigned to an object that contains a pointer and the other to an object that does not contain a pointer. This will bring benefits to the garbage collection mechanism, which will be discussed in a later article.

As shown in the following figure, mspan consists of a contiguous set of pages, divided into object according to a certain size.

Page mspan

There are 67 Size Class of mspan in Go1.9.2, and the object size of each mspan partition is a multiple of 8x2n, which is written in the code:

/ / path: / usr/local/go/src/runtime/sizeclasses.go

Const _ NumSizeClasses = 67

Var class_to_size = [_ NumSizeClasses] uint16 {0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144,6528, 6784, 6912, 8192, 9472,9728,10240,10880,12288,13568, 14336,16384,18432 19072, 20480, 21760, 24576, 27264, 28672, 32768}

The object size divided by mspan can be obtained according to its Size Class. For example, the size of Size Class equals 3Jet object is 32B. 32B-sized object can store objects whose size ranges from 17B~32B. For small objects (less than 16B), the allocator merges them and allocates several objects into the same object.

The largest number in the array is 32768, that is, 32KB. Beyond this size is a large object, which is given special treatment, which will be discussed later. By the way, the type Size Class of 0 represents large objects, which are actually allocated directly by heap memory, while small objects are allocated through mspan.

For mspan, its Size Class determines the number of pages it can get, which is also written in the code:

/ / path: / usr/local/go/src/runtime/sizeclasses.go

Const _ NumSizeClasses = 67

Var class_to_allocnpages = [_ NumSizeClasses] uint8 {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 9, 7, 5, 8, 3, 10, 7, 4}

For example, when we apply for a mspan with an object size of 32B, the corresponding index in class_to_size is 3, and the corresponding number of pages in index 3 in the class_to_allocnpages array is 1.

Mspan structure definition:

/ / path: / usr/local/go/src/runtime/mheap.go

Type mspan struct {

/ / list forward pointer, which is used to link span

Next * mspan

/ / list forward pointer, which is used to link span

Prev * mspan

/ / starting address, that is, the address of the managed page

StartAddr uintptr

/ / number of pages managed

Npages uintptr

/ / number of blocks, indicating how many blocks are available for allocation

Nelems uintptr

/ / assign a bitmap. Each bit represents whether a block has been allocated.

AllocBits * gcBits

/ / number of allocated blocks

AllocCount uint16

/ / class ID in the class table, related to Size Classs

Spanclass spanClass

/ / object size in the class table, that is, block size

Elemsize uintptr

}

Let's look at mspan from a larger perspective:

Mspan has a larger perspective

As you can see in the figure above, there are two S pointing to the same mspan, because the P that the two S points to belongs to the same mspan. So, you can quickly find the S pointing to it through the address on the arena, and you can find the mspan through S, remembering that each pointer to the mspan area we mentioned earlier corresponds to a page.

Assuming that the Size Class of the first mspan on the far left is equal to 10, according to the previous class_to_size array, it is concluded that the object size of this msapn partition is 144B, and the number of objects that can be allocated is 8KB/144B=56.89, rounding 56, so some memory will be wasted. The source code of Go contains the amount of memory wasted by the mspan of all Size Class. According to the class_to_allocnpages array, the mspan is only composed of 1 page. Assuming that the mspan is assigned to an object without a pointer, then spanClass equals 20.

StartAddr points directly to a location in the arena area, indicating the starting address of the mspan, allocBits points to a bitmap, each represents whether a block has been assigned objects, and allocCount represents the total number of objects allocated.

In this way, the field parameters of the first mspan from the left are shown in the following figure:

The first mspan specific value from the left

Memory management component

Memory allocation is done by the memory allocator. The allocator consists of three components: mcache, mcentral, and mheap.

Mcache

Mcache: each worker thread binds a mcache, which locally caches available mspan resources, so that it can be allocated directly to Goroutine, because there is no Goroutine contention, so lock resources are not consumed.

The structure definition of mcache:

/ / path: / usr/local/go/src/runtime/mcache.go

Type mcache struct {

Alloc [numSpanClasses] * mspan

}

NumSpanClasses = _ NumSizeClasses

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.