Go runtime memory allocation — heap, mcache, and tcmalloc

Contents

  1. 1. Go runtime memory pool
    1. 1.1. Overview
    2. 1.2. Memory layout
    3. 1.3. Data structures
      1. 1.3.1. mspan
      2. 1.3.2. mcache
      3. 1.3.3. mcentral
      4. 1.3.4. mheap
    4. 1.4. Allocation flow
      1. 1.4.1. Allocate
      2. 1.4.2. Free
      3. 1.4.3. Source trace
    5. 1.5. Summary

Go runtime memory pool

Overview

Go manages memory for you: a heap allocator plus the GC. Most of the time you never touch malloc yourself. Below: the pool allocator in the runtime (Go 1.10.3) and how the pieces connect.

The design follows tcmalloc (thread-caching malloc): per-thread caches for small objects (≤32 KiB), then central lists, then the heap, then the OS. Tiered caches shrink lock contention and fragmentation.

Below: how memory is carved up, the main structs, then the allocation path in source.

Memory layout

At init the runtime maps one contiguous region and splits it into spans metadata, bitmap, and arena (runtime/malloc.go).

On 64-bit (pointer size 8 bytes):

  • Arena — the heap pool (~512 GiB virtual).
  • Bitmap — which arena words hold objects and whether they contain pointers; 1 byte covers 4 pointer slots (2 bits per pointer) → ~16 GiB metadata.
  • Spans — one pointer slot per 8 KiB heap page → ~512 MiB.

Arena, bitmap, and spans relative sizes

Data structures

Overall allocator layout

mspan

A run of contiguous pages for a given size class — the basic allocation unit. The stack pool also chains mspan values (runtime/stack.go) to cut stack alloc cost for goroutines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
type mspan struct {
next *mspan // next span in list, or nil if none
prev *mspan // previous span in list, or nil if none
list *mSpanList // For debugging. TODO: Remove.

startAddr uintptr // address of first byte of span aka s.base()
npages uintptr // number of pages in span

manualFreeList gclinkptr // list of free objects in _MSpanManual spans

freeindex uintptr
nelems uintptr // number of object in the span.
allocCache uint64
allocBits *gcBits
gcmarkBits *gcBits

sweepgen uint32
divMul uint16 // for divide by elemsize - divMagic.mul
baseMask uint16 // if non-0, elemsize is a power of 2, & this will get object allocation base
allocCount uint16 // number of allocated objects
spanclass spanClass // size class and noscan (uint8)
incache bool // being used by an mcache
state mSpanState // mspaninuse etc
needzero uint8 // needs to be zeroed before allocation
divShift uint8 // for divide by elemsize - divMagic.shift
divShift2 uint8 // for divide by elemsize - divMagic.shift2
elemsize uintptr // computed from sizeclass or from npages
unusedsince int64 // first time spotted by gc in mspanfree state
npreleased uintptr // number of pages released to the os
limit uintptr // end of data in span
speciallock mutex // guards specials list
specials *special // linked list of special records sorted by offset.
}

Notable fields:

  • freeindex — index of next free slot in [0, nelems); slots before it are allocated.
  • allocBits — bitmap of free slots (1 = free).
  • allocCache — complemented bits from freeindex for fast ctz scanning (sys.Ctz64).
  • spanclass — size class + noscan flag.
  • elemsize — object size for size class; page multiple for large spans.

mcache

Per-P cache (only one M holds a given P at a time) — no lock for small allocs. alloc holds 67 *mspan buckets (local cache).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type mcache struct {
next_sample int32
local_scan uintptr

tiny uintptr
tinyoffset uintptr
local_tinyallocs uintptr

alloc [numSpanClasses]*mspan

stackcache [_NumStackOrders]stackfreelist

local_nlookup uintptr
local_largefree uintptr
local_nlargefree uintptr
local_nsmallfree [_NumSizeClasses]uintptr
}
  • alloc — one active span per span class.
  • tiny / tinyoffset — bump pointer for sub-16 B tiny objects.

class_to_size in sizeclasses.go lists byte sizes per class (8, 16, … up to 32768).

mcentral

Central free lists per size class. mcache refills from nonempty; may sweep spans; if still empty, asks mheap.

1
2
3
4
5
6
7
type mcentral struct {
lock mutex
spanclass spanClass
nonempty mSpanList
empty mSpanList
nmalloc uint64
}

mheap

Owns virtual arena addresses; small and large objects; global stats.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type mheap struct {
lock mutex
free [_MaxMHeapList]mSpanList
freelarge mTreap
busy [_MaxMHeapList]mSpanList
busylarge mSpanList
// ... sweep fields, stats ...

allspans []*mspan
spans []*mspan

arena_start uintptr
arena_used uintptr
arena_alloc uintptr
arena_end uintptr

central [numSpanClasses]struct {
mcentral mcentral
pad [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
}

spanalloc fixalloc
cachealloc fixalloc
// ...
}
  • freelarge — treap of large free spans (best-fit; see mgclarge.go).
  • spans — page index → mspan.
  • central — array of mcentral.

fixalloc hands out fixed-size metadata objects (mspan, mcache, treap nodes) without fragmentation:

1
2
3
4
5
6
7
8
9
10
11
type fixalloc struct {
size uintptr
first func(arg, p unsafe.Pointer)
arg unsafe.Pointer
list *mlink
chunk uintptr
nchunk uint32
inuse uintptr
stat *uint64
zero bool
}

Allocation flow

malloc flow diagram

Allocate

  • > 32 KiB — large object from mheap.
  • < 16 B — tiny allocator in mcache (packed tiny objects, with alignment rules 8/4/2/1 byte). Some waste, faster access.
  • 16 B … 32 KiB — pick sizeClass, alloc from mcache.alloc[class].
  • mcache miss → mcentral → mheap (best-fit span, split remainder) → OS (≥1 MiB pages).

Free

Object returns to mcache; may flush to mcentral then mheap. Sweep: mspan.sweep in runtime/mgcsweep.go.

Source trace

1
2
3
func newobject(typ *_type) unsafe.Pointer {
return mallocgc(typ.size, typ, true)
}

mallocgc (abbreviated behavior):

  • Tiny (noscan, size < maxTinySize): align tinyoffset, bump in current tiny block or grab new span; zero 16 bytes when starting fresh block.
  • Small: map size → sizeclass, nextFreeFast or mcache.nextFree → refill chain.
  • Large: largeAlloc → mheap.alloc.

nextFreeFast uses allocCache and Ctz64.

mcache.nextFree calls refill → mcentral → mheap → sysAlloc.

largeAlloc rounds to pages, mheap_.alloc, sets limit.

Full mallocgc path (Go 1.10):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
func newobject(typ *_type) unsafe.Pointer {
return mallocgc(typ.size, typ, true)
}

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
...

dataSize := size
c := gomcache()
var x unsafe.Pointer
noscan := typ == nil || typ.kind&kindNoPointers != 0
if size <= maxSmallSize {
if noscan && size < maxTinySize {
off := c.tinyoffset
if size&7 == 0 {
off = round(off, 8)
} else if size&3 == 0 {
off = round(off, 4)
} else if size&1 == 0 {
off = round(off, 2)
}
if off+size <= maxTinySize && c.tiny != 0 {
x = unsafe.Pointer(c.tiny + off)
c.tinyoffset = off + size
c.local_tinyallocs++
mp.mallocing = 0
releasem(mp)
return x
}
span := c.alloc[tinySpanClass]
v := nextFreeFast(span)
if v == 0 {
v, _, shouldhelpgc = c.nextFree(tinySpanClass)
}
x = unsafe.Pointer(v)
(*[2]uint64)(x)[0] = 0
(*[2]uint64)(x)[1] = 0
if size < c.tinyoffset || c.tiny == 0 {
c.tiny = uintptr(x)
c.tinyoffset = size
}
size = maxTinySize
} else {
var sizeclass uint8
if size <= smallSizeMax-8 {
sizeclass = size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]
} else {
sizeclass = size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]
}
size = uintptr(class_to_size[sizeclass])
spc := makeSpanClass(sizeclass, noscan)
span := c.alloc[spc]
v := nextFreeFast(span)
if v == 0 {
v, span, shouldhelpgc = c.nextFree(spc)
}
x = unsafe.Pointer(v)
if needzero && span.needzero != 0 {
memclrNoHeapPointers(unsafe.Pointer(v), size)
}
}
} else {
var s *mspan
shouldhelpgc = true
systemstack(func() {
s = largeAlloc(size, needzero, noscan)
})
s.freeindex = 1
s.allocCount = 1
x = unsafe.Pointer(s.base())
size = s.elemsize
}

...

return x
}

func nextFreeFast(s *mspan) gclinkptr {
theBit := sys.Ctz64(s.allocCache)
if theBit < 64 {
result := s.freeindex + uintptr(theBit)
if result < s.nelems {
freeidx := result + 1
if freeidx%64 == 0 && freeidx != s.nelems {
return 0
}
s.allocCache >>= uint(theBit + 1)
s.freeindex = freeidx
s.allocCount++
return gclinkptr(result*s.elemsize + s.base())
}
}
return 0
}

func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
s = c.alloc[spc]
shouldhelpgc = false
freeIndex := s.nextFreeIndex()
if freeIndex == s.nelems {
if uintptr(s.allocCount) != s.nelems {
println("runtime: s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
throw("s.allocCount != s.nelems && freeIndex == s.nelems")
}
systemstack(func() {
c.refill(spc)
})
shouldhelpgc = true
s = c.alloc[spc]

freeIndex = s.nextFreeIndex()
}

if freeIndex >= s.nelems {
throw("freeIndex is not valid")
}

v = gclinkptr(freeIndex*s.elemsize + s.base())
s.allocCount++
if uintptr(s.allocCount) > s.nelems {
println("s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
throw("s.allocCount > s.nelems")
}
return
}

func largeAlloc(size uintptr, needzero bool, noscan bool) *mspan {
if size+_PageSize < size {
throw("out of memory")
}
npages := size >> _PageShift
if size&_PageMask != 0 {
npages++
}

deductSweepCredit(npages*_PageSize, npages)

s := mheap_.alloc(npages, makeSpanClass(0, noscan), true, needzero)
if s == nil {
throw("out of memory")
}
s.limit = s.base() + size
heapBitsForSpan(s.base()).initSpan(s)
return s
}

Summary

Go tiers allocation: tiny bump buffer, size-class spans in per-P caches, central lists, then heap pages from the OS. Fixed size classes limit fragmentation; caching amortizes locks and syscalls.

  • Tiny (<16 B): mcache tiny allocator
  • Small (16 B–32 KiB): size class + mcache / mcentral
  • Large (>32 KiB): mheap directly

Reference

http://www.cnblogs.com/zkweb/p/7880099.html
https://studygolang.com/articles/11030

Questions? Leave a comment below or email: newbvirgil@gmail.com