-
-
Notifications
You must be signed in to change notification settings - Fork 504
/
mgc.go
2527 lines (2267 loc) · 90.8 KB
/
mgc.go
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright 2009 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.
// Garbage collector (GC).
//
// The GC runs concurrently with mutator threads, is type accurate (aka precise), allows multiple
// GC thread to run in parallel. It is a concurrent mark and sweep that uses a write barrier. It is
// non-generational and non-compacting. Allocation is done using size segregated per P allocation
// areas to minimize fragmentation while eliminating locks in the common case.
//
// The algorithm decomposes into several steps.
// This is a high level description of the algorithm being used. For an overview of GC a good
// place to start is Richard Jones' gchandbook.org.
//
// The algorithm's intellectual heritage includes Dijkstra's on-the-fly algorithm, see
// Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978.
// On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978),
// 966-975.
// For journal quality proofs that these steps are complete, correct, and terminate see
// Hudson, R., and Moss, J.E.B. Copying Garbage Collection without stopping the world.
// Concurrency and Computation: Practice and Experience 15(3-5), 2003.
//
// 1. GC performs sweep termination.
//
// a. Stop the world. This causes all Ps to reach a GC safe-point.
//
// b. Sweep any unswept spans. There will only be unswept spans if
// this GC cycle was forced before the expected time.
//
// 2. GC performs the mark phase.
//
// a. Prepare for the mark phase by setting gcphase to _GCmark
// (from _GCoff), enabling the write barrier, enabling mutator
// assists, and enqueueing root mark jobs. No objects may be
// scanned until all Ps have enabled the write barrier, which is
// accomplished using STW.
//
// b. Start the world. From this point, GC work is done by mark
// workers started by the scheduler and by assists performed as
// part of allocation. The write barrier shades both the
// overwritten pointer and the new pointer value for any pointer
// writes (see mbarrier.go for details). Newly allocated objects
// are immediately marked black.
//
// c. GC performs root marking jobs. This includes scanning all
// stacks, shading all globals, and shading any heap pointers in
// off-heap runtime data structures. Scanning a stack stops a
// goroutine, shades any pointers found on its stack, and then
// resumes the goroutine.
//
// d. GC drains the work queue of grey objects, scanning each grey
// object to black and shading all pointers found in the object
// (which in turn may add those pointers to the work queue).
//
// e. Because GC work is spread across local caches, GC uses a
// distributed termination algorithm to detect when there are no
// more root marking jobs or grey objects (see gcMarkDone). At this
// point, GC transitions to mark termination.
//
// 3. GC performs mark termination.
//
// a. Stop the world.
//
// b. Set gcphase to _GCmarktermination, and disable workers and
// assists.
//
// c. Perform housekeeping like flushing mcaches.
//
// 4. GC performs the sweep phase.
//
// a. Prepare for the sweep phase by setting gcphase to _GCoff,
// setting up sweep state and disabling the write barrier.
//
// b. Start the world. From this point on, newly allocated objects
// are white, and allocating sweeps spans before use if necessary.
//
// c. GC does concurrent sweeping in the background and in response
// to allocation. See description below.
//
// 5. When sufficient allocation has taken place, replay the sequence
// starting with 1 above. See discussion of GC rate below.
// Concurrent sweep.
//
// The sweep phase proceeds concurrently with normal program execution.
// The heap is swept span-by-span both lazily (when a goroutine needs another span)
// and concurrently in a background goroutine (this helps programs that are not CPU bound).
// At the end of STW mark termination all spans are marked as "needs sweeping".
//
// The background sweeper goroutine simply sweeps spans one-by-one.
//
// To avoid requesting more OS memory while there are unswept spans, when a
// goroutine needs another span, it first attempts to reclaim that much memory
// by sweeping. When a goroutine needs to allocate a new small-object span, it
// sweeps small-object spans for the same object size until it frees at least
// one object. When a goroutine needs to allocate large-object span from heap,
// it sweeps spans until it frees at least that many pages into heap. There is
// one case where this may not suffice: if a goroutine sweeps and frees two
// nonadjacent one-page spans to the heap, it will allocate a new two-page
// span, but there can still be other one-page unswept spans which could be
// combined into a two-page span.
//
// It's critical to ensure that no operations proceed on unswept spans (that would corrupt
// mark bits in GC bitmap). During GC all mcaches are flushed into the central cache,
// so they are empty. When a goroutine grabs a new span into mcache, it sweeps it.
// When a goroutine explicitly frees an object or sets a finalizer, it ensures that
// the span is swept (either by sweeping it, or by waiting for the concurrent sweep to finish).
// The finalizer goroutine is kicked off only when all spans are swept.
// When the next GC starts, it sweeps all not-yet-swept spans (if any).
// GC rate.
// Next GC is after we've allocated an extra amount of memory proportional to
// the amount already in use. The proportion is controlled by GOGC environment variable
// (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M
// (this mark is tracked in next_gc variable). This keeps the GC cost in linear
// proportion to the allocation cost. Adjusting GOGC just changes the linear constant
// (and also the amount of extra memory used).
// Oblets
//
// In order to prevent long pauses while scanning large objects and to
// improve parallelism, the garbage collector breaks up scan jobs for
// objects larger than maxObletBytes into "oblets" of at most
// maxObletBytes. When scanning encounters the beginning of a large
// object, it scans only the first oblet and enqueues the remaining
// oblets as new scan jobs.
// 垃圾回收器 (GC).
//
// GC 与 mutator 线程同时运行,类型准确(也称为精确),允许多个 GC 线程并行运行。
// 它是一个使用 write barrier 的并发标记和扫描。它是 non-generational 和 non-compacting 的。
// 使用 per-P 分配区域隔离的大小来完成分配,以最小化碎片,同时消除通常情况下的加锁。
//
// 该算法分解为几个步骤。
// 这里给出的是正在使用的算法的高阶描述。有关 GC 的概述请参考 Richard Jones 的 gchandbook.org。
//
// 该算法的精神遗产包括 Dijkstra 的 on-the-fly 算法,参见:
// Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978.
// On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978),
// 966-975.
// 关于算法的完整性、正确性和可终止性证明,请参考期刊文献:
// Hudson, R., and Moss, J.E.B. Copying Garbage Collection without stopping the world.
// Concurrency and Computation: Practice and Experience 15(3-5), 2003.
//
// 1. GC 执行终止扫描 (sweep termination)
//
// a. 停止世界(STW, Stop the World),此操作会导致所有 P 进入 GC safe-point
//
// b. 扫描所有未被扫描过的 span。如果在预期的时间之前强制执行 GC 周期,那么只会有未清扫的span。
//
// 2. GC 执行 "mark" 阶段
//
// a. 通过将 gcphase 设置为 _GCmark(来自_GCoff),来启用 write barrier
// 启用 mutator assists 以及 root mark 任务入队以准备标记阶段。
// 在所有 P 启用 write barrier 之前,没有任何对象会被扫描,这是由 STW 完成的。
//
// b. 启动世界(start the world)。从这时开始,GC work 由调度器启动的
// mark worker 和作为分配的一部分执行的 assist 完成。write barrier 着色
// 被复用的指针以及任何指针写行为的指针新值。(见 mbarrier.go)。新分配的对象
// 会立即标记为黑色。
//
// c. GC 执行 root mark 任务。这包括扫描所有栈、着色所有全局变量、以及
// 堆外运行时数据结构中的任何堆指针。扫描栈的工作会停止运行的 goroutine,
// 并为栈中找到的所有指针进行着色,然后恢复 goroutine 的执行。
//
// d. GC 将灰色对象的工作队列排除,将每个灰色对象扫描为黑色,并对对象中找到的
// 所有指针进行着色(然后将这些指针添加回工作队列)。
//
// e. 因为 GC work 在不同的局部缓存中被分开,GC 使用分布式终止算法来检测何时
// 没有更多的 root 标记任务或灰色对象(见 gcMarkDone)
//
// 3. GC 执行 mark termination
//
// a. STW
//
// b. 设置 gcphase 为 _GCmarktermination,并禁用所有的 worker 和 assist
//
// c. Perform housekeeping like flushing mcaches.
//
// 4. GC 执行扫描阶段 (sweep phase)
//
// a. 通过设置 gcphase 到 _GCoff 来准备 sweep 阶段,设置 sweep 状态并禁用 write barrier。
//
// b. Start the world。这时,所有新创建的对象为白色,并在必要时分配 sweep span。
//
// c. GC 并发执行 sweep,来响应分配工作,见下面的描述。
//
// 5. 当用户进行了足够的分配工作后,重新从上面 1 开始。 请参阅下面有关 GC 频率的讨论。
// 并发 sweep.
//
// sweep 阶段与正常程序执行同时进行。堆懒惰的清扫 span-by-span(当 goroutine 需要另一个 span 时)
// 并且并发的在后台 goroutine 中扫描(这有助于不受 CPU 限制的程序)。
// 在 STW 标记终止结束时,所有 span 都标记为“需要清扫”。
//
// 后台 sweeper 简单的对一个个 span 进行 sweep。
//
// 为了避免在未扫描 span 时请求更多 OS 内存,当 goroutine 需要另一个 span 时,它首先尝试通过扫描来回收那么多内存。
// 当 goroutine 需要分配一个新的小对象 span 时,它会扫描相同对象大小的小对象 span,直到它释放至少一个对象。
// 当 goroutine 需要从堆中分配大对象 span 时,它会扫描 span,直到它将至少那么多页释放到堆中。
// 有一种情况,这可能是不够的:如果 goroutine 扫描并释放两个不相邻的单页 span 到堆,
// 它将分配一个新的两页 span,但仍然可以有其他单页未扫描 span 可能是合并为两页 span。
//
// 确保在未扫描的 span 上不进行任何操作(这会破坏 GC bitmap 中的标记位)至关重要。
// 在GC期间,所有 mcache 都被刷新到 mcentral 中,因此它们是空的。当 goroutine 抓住一个新的 span 到 mcache 时,它会扫过它。
// 当 goroutine 显式释放对象或设置 finalizer 时,它确保扫描 span(通过扫描它,或等待并发扫描完成)。
// 只有当所有 span 都被扫过时,finalizer goroutine 才会开始。当下一个 GC 开始时,它会扫描所有尚未扫描的 span(如果有的话)。
// GC 频率
// 下一次 GC 是在分配了与已经使用的量成比例的额外内存量之后开始。该比例由 GOGC 环境变量控制(默认为 100)。
// 如果 GOGC = 100 并且我们正在使用 4M,那么当我们达到 8M 时将再次使用 GC(此标记在 next_gc 变量中被跟踪)。
// 这使 GC 成本与分配成本成线性比例。调整 GOGC 只会改变线性常量(以及使用的额外内存量)。
// Oblets
//
// 为了防止在扫描大对象时出现长时间暂停并提高并行性,垃圾收集器将大于m axObletBytes 的对象的扫描 work
// 分解为最多 maxobletBytes 的 “oblets”。
// 当扫描遇到大对象的开头时,它只扫描第一个 oblet 并将剩余的 oblet 排队为新的扫描 work。
package runtime
import (
"internal/cpu"
"runtime/internal/atomic"
"unsafe"
)
const (
_DebugGC = 0
_ConcurrentSweep = true
_FinBlockSize = 4 * 1024
// debugScanConservative enables debug logging for stack
// frames that are scanned conservatively.
debugScanConservative = false
// sweepMinHeapDistance is a lower bound on the heap distance
// (in bytes) reserved for concurrent sweeping between GC
// cycles.
// sweepMinHeapDistance 是为 GC 周期之间的并发扫描保留的堆距离(以字节为单位)的下限。
sweepMinHeapDistance = 1024 * 1024
)
// heapminimum is the minimum heap size at which to trigger GC.
// For small heaps, this overrides the usual GOGC*live set rule.
//
// When there is a very small live set but a lot of allocation, simply
// collecting when the heap reaches GOGC*live results in many GC
// cycles and high total per-GC overhead. This minimum amortizes this
// per-GC overhead while keeping the heap reasonably small.
//
// During initialization this is set to 4MB*GOGC/100. In the case of
// GOGC==0, this will set heapminimum to 0, resulting in constant
// collection even when the heap size is small, which is useful for
// debugging.
var heapminimum uint64 = defaultHeapMinimum
// defaultHeapMinimum is the value of heapminimum for GOGC==100.
// defaultHeapMinimum 是 GOGC == 100 的 heapminimum 值。
const defaultHeapMinimum = 4 << 20
// Initialized from $GOGC. GOGC=off means no GC.
// 从 $GOGC 初始化. GOGC=off 表示禁用 GC.
var gcpercent int32
func gcinit() {
if unsafe.Sizeof(workbuf{}) != _WorkbufSize {
throw("size of Workbuf is suboptimal")
}
// No sweep on the first cycle.
// 第一个周期没有扫描。
mheap_.sweepdone = 1
// Set a reasonable initial GC trigger.
// 设置合理的初始 GC 触发比率。
memstats.triggerRatio = 7 / 8.0
// Fake a heap_marked value so it looks like a trigger at
// heapminimum is the appropriate growth from heap_marked.
// This will go into computing the initial GC goal.
// 伪造一个 heap_marked 值,使它看起来像一个触发器
// heapminimum 是 heap_marked的 适当增长。
// 这将用于计算初始 GC 目标。
memstats.heap_marked = uint64(float64(heapminimum) / (1 + memstats.triggerRatio))
// Set gcpercent from the environment. This will also compute
// and set the GC trigger and goal.
// 从环境中设置 gcpercent。这也将计算并设置 GC 触发器和目标。
_ = setGCPercent(readgogc())
work.startSema = 1
work.markDoneSema = 1
lockInit(&work.sweepWaiters.lock, lockRankSweepWaiters)
lockInit(&work.assistQueue.lock, lockRankAssistQueue)
lockInit(&work.wbufSpans.lock, lockRankWbufSpans)
}
func readgogc() int32 {
p := gogetenv("GOGC")
if p == "off" {
return -1
}
if n, ok := atoi32(p); ok {
return n
}
return 100
}
// gcenable is called after the bulk of the runtime initialization,
// just before we're about to start letting user code run.
// It kicks off the background sweeper goroutine, the background
// scavenger goroutine, and enables GC.
// 在我们即将开始让用户代码运行之前,在大量运行时初始化之后调用 gcenable。
// 它启用了后台 sweeper goroutine,后台 scavenger goroutine,并启用了 GC
func gcenable() {
// Kick off sweeping and scavenging.
c := make(chan int, 2)
go bgsweep(c)
go bgscavenge(c)
<-c
<-c
memstats.enablegc = true // now that runtime is initialized, GC is okay // 现在运行时已经初始化完毕了,GC 已就绪
}
//go:linkname setGCPercent runtime/debug.setGCPercent
func setGCPercent(in int32) (out int32) {
// Run on the system stack since we grab the heap lock.
// 需要获取 heap 锁,切换到系统栈
systemstack(func() {
lock(&mheap_.lock)
out = gcpercent
if in < 0 {
in = -1
}
gcpercent = in
heapminimum = defaultHeapMinimum * uint64(gcpercent) / 100
// Update pacing in response to gcpercent change.
// 更新步调来响应 gcpercent 变化
gcSetTriggerRatio(memstats.triggerRatio)
unlock(&mheap_.lock)
})
// If we just disabled GC, wait for any concurrent GC mark to
// finish so we always return with no GC running.
// 如果我们刚好禁用了 GC,则等待任何并发 GC 标记完成,从而我们总是能够在没有 GC 的情况下返回
if in < 0 {
gcWaitOnMark(atomic.Load(&work.cycles))
}
return out
}
// Garbage collector phase.
// Indicates to write barrier and synchronization task to perform.
// 垃圾回收期阶段,表示要执行 write barrier 和同步任务
var gcphase uint32
// The compiler knows about this variable.
// If you change it, you must change builtin/runtime.go, too.
// If you change the first four bytes, you must also change the write
// barrier insertion code.
// 编译器了解此变量
// 如果你修改它,你还需要修改 builtin/runtime.go
// 如果你修改前四个字节,则还需要修改插入的 write barrier 代码.
var writeBarrier struct {
enabled bool // compiler emits a check of this before calling write barrier
pad [3]byte // compiler uses 32-bit load for "enabled" field
needed bool // whether we need a write barrier for current GC phase
cgo bool // whether we need a write barrier for a cgo check
alignme uint64 // guarantee alignment so that compiler can use a 32 or 64-bit load
}
// gcBlackenEnabled is 1 if mutator assists and background mark
// workers are allowed to blacken objects. This must only be set when
// gcphase == _GCmark.
// gcBlackenEnabled 如果 mutator assists 和 background mark worker 被允许 blacken 对象。
// 它只有在 gcphase == _GCmark 时才被设置
var gcBlackenEnabled uint32
// _GCoff: GC 没有运行,sweep 在后台运行,写屏障没有启用
// _GCmark: GC 标记 roots 和 workbufs: 分配黑色,写屏障启用
// _GCmarktermination: GC 标记终止: 分配黑色, P's 帮助 GC, 写屏障启用
const (
_GCoff = iota // GC not running; sweeping in background, write barrier disabled
_GCmark // GC marking roots and workbufs: allocate black, write barrier ENABLED
_GCmarktermination // GC mark termination: allocate black, P's help GC, write barrier ENABLED
)
//go:nosplit
func setGCPhase(x uint32) {
atomic.Store(&gcphase, x)
writeBarrier.needed = gcphase == _GCmark || gcphase == _GCmarktermination
writeBarrier.enabled = writeBarrier.needed || writeBarrier.cgo
}
// gcMarkWorkerMode represents the mode that a concurrent mark worker
// should operate in.
//
// Concurrent marking happens through four different mechanisms. One
// is mutator assists, which happen in response to allocations and are
// not scheduled. The other three are variations in the per-P mark
// workers and are distinguished by gcMarkWorkerMode.
type gcMarkWorkerMode int
const (
// gcMarkWorkerNotWorker indicates that the next scheduled G is not
// starting work and the mode should be ignored.
gcMarkWorkerNotWorker gcMarkWorkerMode = iota
// gcMarkWorkerDedicatedMode indicates that the P of a mark
// worker is dedicated to running that mark worker. The mark
// worker should run without preemption.
gcMarkWorkerDedicatedMode
// gcMarkWorkerFractionalMode indicates that a P is currently
// running the "fractional" mark worker. The fractional worker
// is necessary when GOMAXPROCS*gcBackgroundUtilization is not
// an integer. The fractional worker should run until it is
// preempted and will be scheduled to pick up the fractional
// part of GOMAXPROCS*gcBackgroundUtilization.
gcMarkWorkerFractionalMode
// gcMarkWorkerIdleMode indicates that a P is running the mark
// worker because it has nothing else to do. The idle worker
// should run until it is preempted and account its time
// against gcController.idleMarkTime.
gcMarkWorkerIdleMode
)
// gcMarkWorkerModeStrings are the strings labels of gcMarkWorkerModes
// to use in execution traces.
var gcMarkWorkerModeStrings = [...]string{
"Not worker",
"GC (dedicated)",
"GC (fractional)",
"GC (idle)",
}
// gcController implements the GC pacing controller that determines
// when to trigger concurrent garbage collection and how much marking
// work to do in mutator assists and background marking.
//
// It uses a feedback control algorithm to adjust the memstats.gc_trigger
// trigger based on the heap growth and GC CPU utilization each cycle.
// This algorithm optimizes for heap growth to match GOGC and for CPU
// utilization between assist and background marking to be 25% of
// GOMAXPROCS. The high-level design of this algorithm is documented
// at https://golang.org/s/go15gcpacing.
//
// All fields of gcController are used only during a single mark
// cycle.
var gcController gcControllerState
type gcControllerState struct {
// scanWork is the total scan work performed this cycle. This
// is updated atomically during the cycle. Updates occur in
// bounded batches, since it is both written and read
// throughout the cycle. At the end of the cycle, this is how
// much of the retained heap is scannable.
//
// Currently this is the bytes of heap scanned. For most uses,
// this is an opaque unit of work, but for estimation the
// definition is important.
scanWork int64
// bgScanCredit is the scan work credit accumulated by the
// concurrent background scan. This credit is accumulated by
// the background scan and stolen by mutator assists. This is
// updated atomically. Updates occur in bounded batches, since
// it is both written and read throughout the cycle.
bgScanCredit int64
// assistTime is the nanoseconds spent in mutator assists
// during this cycle. This is updated atomically. Updates
// occur in bounded batches, since it is both written and read
// throughout the cycle.
assistTime int64
// dedicatedMarkTime is the nanoseconds spent in dedicated
// mark workers during this cycle. This is updated atomically
// at the end of the concurrent mark phase.
dedicatedMarkTime int64
// fractionalMarkTime is the nanoseconds spent in the
// fractional mark worker during this cycle. This is updated
// atomically throughout the cycle and will be up-to-date if
// the fractional mark worker is not currently running.
fractionalMarkTime int64
// idleMarkTime is the nanoseconds spent in idle marking
// during this cycle. This is updated atomically throughout
// the cycle.
idleMarkTime int64
// markStartTime is the absolute start time in nanoseconds
// that assists and background mark workers started.
markStartTime int64
// dedicatedMarkWorkersNeeded is the number of dedicated mark
// workers that need to be started. This is computed at the
// beginning of each cycle and decremented atomically as
// dedicated mark workers get started.
dedicatedMarkWorkersNeeded int64
// assistWorkPerByte is the ratio of scan work to allocated
// bytes that should be performed by mutator assists. This is
// computed at the beginning of each cycle and updated every
// time heap_scan is updated.
//
// Stored as a uint64, but it's actually a float64. Use
// float64frombits to get the value.
//
// Read and written atomically.
assistWorkPerByte uint64
// assistBytesPerWork is 1/assistWorkPerByte.
//
// Stored as a uint64, but it's actually a float64. Use
// float64frombits to get the value.
//
// Read and written atomically.
//
// Note that because this is read and written independently
// from assistWorkPerByte users may notice a skew between
// the two values, and such a state should be safe.
assistBytesPerWork uint64
// fractionalUtilizationGoal is the fraction of wall clock
// time that should be spent in the fractional mark worker on
// each P that isn't running a dedicated worker.
//
// For example, if the utilization goal is 25% and there are
// no dedicated workers, this will be 0.25. If the goal is
// 25%, there is one dedicated worker, and GOMAXPROCS is 5,
// this will be 0.05 to make up the missing 5%.
//
// If this is zero, no fractional workers are needed.
fractionalUtilizationGoal float64
_ cpu.CacheLinePad
}
// startCycle resets the GC controller's state and computes estimates
// for a new GC cycle. The caller must hold worldsema and the world
// must be stopped.
func (c *gcControllerState) startCycle() {
c.scanWork = 0
c.bgScanCredit = 0
c.assistTime = 0
c.dedicatedMarkTime = 0
c.fractionalMarkTime = 0
c.idleMarkTime = 0
// Ensure that the heap goal is at least a little larger than
// the current live heap size. This may not be the case if GC
// start is delayed or if the allocation that pushed heap_live
// over gc_trigger is large or if the trigger is really close to
// GOGC. Assist is proportional to this distance, so enforce a
// minimum distance, even if it means going over the GOGC goal
// by a tiny bit.
if memstats.next_gc < memstats.heap_live+1024*1024 {
memstats.next_gc = memstats.heap_live + 1024*1024
}
// Compute the background mark utilization goal. In general,
// this may not come out exactly. We round the number of
// dedicated workers so that the utilization is closest to
// 25%. For small GOMAXPROCS, this would introduce too much
// error, so we add fractional workers in that case.
totalUtilizationGoal := float64(gomaxprocs) * gcBackgroundUtilization
c.dedicatedMarkWorkersNeeded = int64(totalUtilizationGoal + 0.5)
utilError := float64(c.dedicatedMarkWorkersNeeded)/totalUtilizationGoal - 1
const maxUtilError = 0.3
if utilError < -maxUtilError || utilError > maxUtilError {
// Rounding put us more than 30% off our goal. With
// gcBackgroundUtilization of 25%, this happens for
// GOMAXPROCS<=3 or GOMAXPROCS=6. Enable fractional
// workers to compensate.
if float64(c.dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
// Too many dedicated workers.
c.dedicatedMarkWorkersNeeded--
}
c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(c.dedicatedMarkWorkersNeeded)) / float64(gomaxprocs)
} else {
c.fractionalUtilizationGoal = 0
}
// In STW mode, we just want dedicated workers.
if debug.gcstoptheworld > 0 {
c.dedicatedMarkWorkersNeeded = int64(gomaxprocs)
c.fractionalUtilizationGoal = 0
}
// Clear per-P state
for _, p := range allp {
p.gcAssistTime = 0
p.gcFractionalMarkTime = 0
}
// Compute initial values for controls that are updated
// throughout the cycle.
c.revise()
if debug.gcpacertrace > 0 {
assistRatio := float64frombits(atomic.Load64(&c.assistWorkPerByte))
print("pacer: assist ratio=", assistRatio,
" (scan ", memstats.heap_scan>>20, " MB in ",
work.initialHeapLive>>20, "->",
memstats.next_gc>>20, " MB)",
" workers=", c.dedicatedMarkWorkersNeeded,
"+", c.fractionalUtilizationGoal, "\n")
}
}
// revise updates the assist ratio during the GC cycle to account for
// improved estimates. This should be called whenever memstats.heap_scan,
// memstats.heap_live, or memstats.next_gc is updated. It is safe to
// call concurrently, but it may race with other calls to revise.
// revise 在 GC 周期期间更新 assist ratio 以考虑改进估计。
// 该函数应该在 STW 或者下调用,或每当 memstats.heap_scan,memstats.heap_live 或
// memstats.next_gc (在只有 mheap_.lock 的情况下)更新时调用。
//
// The result of this race is that the two assist ratio values may not line
// up or may be stale. In practice this is OK because the assist ratio
// moves slowly throughout a GC cycle, and the assist ratio is a best-effort
// heuristic anyway. Furthermore, no part of the heuristic depends on
// the two assist ratio values being exact reciprocals of one another, since
// the two values are used to convert values from different sources.
//
// The worst case result of this raciness is that we may miss a larger shift
// in the ratio (say, if we decide to pace more aggressively against the
// hard heap goal) but even this "hard goal" is best-effort (see #40460).
// The dedicated GC should ensure we don't exceed the hard goal by too much
// in the rare case we do exceed it.
//
// It should only be called when gcBlackenEnabled != 0 (because this
// is when assists are enabled and the necessary statistics are
// available).
func (c *gcControllerState) revise() {
gcpercent := gcpercent
if gcpercent < 0 {
// If GC is disabled but we're running a forced GC,
// act like GOGC is huge for the below calculations.
gcpercent = 100000
}
live := atomic.Load64(&memstats.heap_live)
scan := atomic.Load64(&memstats.heap_scan)
work := atomic.Loadint64(&c.scanWork)
// Assume we're under the soft goal. Pace GC to complete at
// next_gc assuming the heap is in steady-state.
heapGoal := int64(atomic.Load64(&memstats.next_gc))
// Compute the expected scan work remaining.
//
// This is estimated based on the expected
// steady-state scannable heap. For example, with
// GOGC=100, only half of the scannable heap is
// expected to be live, so that's what we target.
//
// (This is a float calculation to avoid overflowing on
// 100*heap_scan.)
scanWorkExpected := int64(float64(scan) * 100 / float64(100+gcpercent))
if int64(live) > heapGoal || work > scanWorkExpected {
// We're past the soft goal, or we've already done more scan
// work than we expected. Pace GC so that in the worst case it
// will complete by the hard goal.
const maxOvershoot = 1.1
heapGoal = int64(float64(heapGoal) * maxOvershoot)
// Compute the upper bound on the scan work remaining.
scanWorkExpected = int64(scan)
}
// Compute the remaining scan work estimate.
//
// Note that we currently count allocations during GC as both
// scannable heap (heap_scan) and scan work completed
// (scanWork), so allocation will change this difference
// slowly in the soft regime and not at all in the hard
// regime.
scanWorkRemaining := scanWorkExpected - work
if scanWorkRemaining < 1000 {
// We set a somewhat arbitrary lower bound on
// remaining scan work since if we aim a little high,
// we can miss by a little.
//
// We *do* need to enforce that this is at least 1,
// since marking is racy and double-scanning objects
// may legitimately make the remaining scan work
// negative, even in the hard goal regime.
scanWorkRemaining = 1000
}
// Compute the heap distance remaining.
heapRemaining := heapGoal - int64(live)
if heapRemaining <= 0 {
// This shouldn't happen, but if it does, avoid
// dividing by zero or setting the assist negative.
heapRemaining = 1
}
// Compute the mutator assist ratio so by the time the mutator
// allocates the remaining heap bytes up to next_gc, it will
// have done (or stolen) the remaining amount of scan work.
// Note that the assist ratio values are updated atomically
// but not together. This means there may be some degree of
// skew between the two values. This is generally OK as the
// values shift relatively slowly over the course of a GC
// cycle.
assistWorkPerByte := float64(scanWorkRemaining) / float64(heapRemaining)
assistBytesPerWork := float64(heapRemaining) / float64(scanWorkRemaining)
atomic.Store64(&c.assistWorkPerByte, float64bits(assistWorkPerByte))
atomic.Store64(&c.assistBytesPerWork, float64bits(assistBytesPerWork))
}
// endCycle computes the trigger ratio for the next cycle.
func (c *gcControllerState) endCycle() float64 {
if work.userForced {
// Forced GC means this cycle didn't start at the
// trigger, so where it finished isn't good
// information about how to adjust the trigger.
// Just leave it where it is.
return memstats.triggerRatio
}
// Proportional response gain for the trigger controller. Must
// be in [0, 1]. Lower values smooth out transient effects but
// take longer to respond to phase changes. Higher values
// react to phase changes quickly, but are more affected by
// transient changes. Values near 1 may be unstable.
const triggerGain = 0.5
// Compute next cycle trigger ratio. First, this computes the
// "error" for this cycle; that is, how far off the trigger
// was from what it should have been, accounting for both heap
// growth and GC CPU utilization. We compute the actual heap
// growth during this cycle and scale that by how far off from
// the goal CPU utilization we were (to estimate the heap
// growth if we had the desired CPU utilization). The
// difference between this estimate and the GOGC-based goal
// heap growth is the error.
goalGrowthRatio := gcEffectiveGrowthRatio()
actualGrowthRatio := float64(memstats.heap_live)/float64(memstats.heap_marked) - 1
assistDuration := nanotime() - c.markStartTime
// Assume background mark hit its utilization goal.
utilization := gcBackgroundUtilization
// Add assist utilization; avoid divide by zero.
if assistDuration > 0 {
utilization += float64(c.assistTime) / float64(assistDuration*int64(gomaxprocs))
}
triggerError := goalGrowthRatio - memstats.triggerRatio - utilization/gcGoalUtilization*(actualGrowthRatio-memstats.triggerRatio)
// Finally, we adjust the trigger for next time by this error,
// damped by the proportional gain.
triggerRatio := memstats.triggerRatio + triggerGain*triggerError
if debug.gcpacertrace > 0 {
// Print controller state in terms of the design
// document.
H_m_prev := memstats.heap_marked
h_t := memstats.triggerRatio
H_T := memstats.gc_trigger
h_a := actualGrowthRatio
H_a := memstats.heap_live
h_g := goalGrowthRatio
H_g := int64(float64(H_m_prev) * (1 + h_g))
u_a := utilization
u_g := gcGoalUtilization
W_a := c.scanWork
print("pacer: H_m_prev=", H_m_prev,
" h_t=", h_t, " H_T=", H_T,
" h_a=", h_a, " H_a=", H_a,
" h_g=", h_g, " H_g=", H_g,
" u_a=", u_a, " u_g=", u_g,
" W_a=", W_a,
" goalΔ=", goalGrowthRatio-h_t,
" actualΔ=", h_a-h_t,
" u_a/u_g=", u_a/u_g,
"\n")
}
return triggerRatio
}
// enlistWorker encourages another dedicated mark worker to start on
// another P if there are spare worker slots. It is used by putfull
// when more work is made available.
//
//go:nowritebarrier
func (c *gcControllerState) enlistWorker() {
// If there are idle Ps, wake one so it will run an idle worker.
// NOTE: This is suspected of causing deadlocks. See golang.org/issue/19112.
//
// if atomic.Load(&sched.npidle) != 0 && atomic.Load(&sched.nmspinning) == 0 {
// wakep()
// return
// }
// There are no idle Ps. If we need more dedicated workers,
// try to preempt a running P so it will switch to a worker.
if c.dedicatedMarkWorkersNeeded <= 0 {
return
}
// Pick a random other P to preempt.
if gomaxprocs <= 1 {
return
}
gp := getg()
if gp == nil || gp.m == nil || gp.m.p == 0 {
return
}
myID := gp.m.p.ptr().id
for tries := 0; tries < 5; tries++ {
id := int32(fastrandn(uint32(gomaxprocs - 1)))
if id >= myID {
id++
}
p := allp[id]
if p.status != _Prunning {
continue
}
if preemptone(p) {
return
}
}
}
// findRunnableGCWorker returns a background mark worker for _p_ if it
// should be run. This must only be called when gcBlackenEnabled != 0.
func (c *gcControllerState) findRunnableGCWorker(_p_ *p) *g {
if gcBlackenEnabled == 0 {
throw("gcControllerState.findRunnable: blackening not enabled")
}
if !gcMarkWorkAvailable(_p_) {
// No work to be done right now. This can happen at
// the end of the mark phase when there are still
// assists tapering off. Don't bother running a worker
// now because it'll just return immediately.
return nil
}
// Grab a worker before we commit to running below.
node := (*gcBgMarkWorkerNode)(gcBgMarkWorkerPool.pop())
if node == nil {
// There is at least one worker per P, so normally there are
// enough workers to run on all Ps, if necessary. However, once
// a worker enters gcMarkDone it may park without rejoining the
// pool, thus freeing a P with no corresponding worker.
// gcMarkDone never depends on another worker doing work, so it
// is safe to simply do nothing here.
//
// If gcMarkDone bails out without completing the mark phase,
// it will always do so with queued global work. Thus, that P
// will be immediately eligible to re-run the worker G it was
// just using, ensuring work can complete.
return nil
}
decIfPositive := func(ptr *int64) bool {
for {
v := atomic.Loadint64(ptr)
if v <= 0 {
return false
}
// TODO: having atomic.Casint64 would be more pleasant.
if atomic.Cas64((*uint64)(unsafe.Pointer(ptr)), uint64(v), uint64(v-1)) {
return true
}
}
}
if decIfPositive(&c.dedicatedMarkWorkersNeeded) {
// This P is now dedicated to marking until the end of
// the concurrent mark phase.
_p_.gcMarkWorkerMode = gcMarkWorkerDedicatedMode
} else if c.fractionalUtilizationGoal == 0 {
// No need for fractional workers.
gcBgMarkWorkerPool.push(&node.node)
return nil
} else {
// Is this P behind on the fractional utilization
// goal?
//
// This should be kept in sync with pollFractionalWorkerExit.
delta := nanotime() - gcController.markStartTime
if delta > 0 && float64(_p_.gcFractionalMarkTime)/float64(delta) > c.fractionalUtilizationGoal {
// Nope. No need to run a fractional worker.
gcBgMarkWorkerPool.push(&node.node)
return nil
}
// Run a fractional worker.
_p_.gcMarkWorkerMode = gcMarkWorkerFractionalMode
}
// Run the background mark worker.
gp := node.gp.ptr()
casgstatus(gp, _Gwaiting, _Grunnable)
if trace.enabled {
traceGoUnpark(gp, 0)
}
return gp
}
// pollFractionalWorkerExit reports whether a fractional mark worker
// should self-preempt. It assumes it is called from the fractional
// worker.
func pollFractionalWorkerExit() bool {
// This should be kept in sync with the fractional worker
// scheduler logic in findRunnableGCWorker.
now := nanotime()
delta := now - gcController.markStartTime
if delta <= 0 {
return true
}
p := getg().m.p.ptr()
selfTime := p.gcFractionalMarkTime + (now - p.gcMarkWorkerStartTime)
// Add some slack to the utilization goal so that the
// fractional worker isn't behind again the instant it exits.
return float64(selfTime)/float64(delta) > 1.2*gcController.fractionalUtilizationGoal
}
// gcSetTriggerRatio sets the trigger ratio and updates everything
// derived from it: the absolute trigger, the heap goal, mark pacing,
// and sweep pacing.
//
// This can be called any time. If GC is the in the middle of a
// concurrent phase, it will adjust the pacing of that phase.
//
// This depends on gcpercent, memstats.heap_marked, and
// memstats.heap_live. These must be up to date.
//
// mheap_.lock must be held or the world must be stopped.
func gcSetTriggerRatio(triggerRatio float64) {
assertWorldStoppedOrLockHeld(&mheap_.lock)
// Compute the next GC goal, which is when the allocated heap
// has grown by GOGC/100 over the heap marked by the last
// cycle.
goal := ^uint64(0)
if gcpercent >= 0 {
goal = memstats.heap_marked + memstats.heap_marked*uint64(gcpercent)/100
}
// Set the trigger ratio, capped to reasonable bounds.
if gcpercent >= 0 {
scalingFactor := float64(gcpercent) / 100
// Ensure there's always a little margin so that the
// mutator assist ratio isn't infinity.
maxTriggerRatio := 0.95 * scalingFactor
if triggerRatio > maxTriggerRatio {
triggerRatio = maxTriggerRatio
}
// If we let triggerRatio go too low, then if the application
// is allocating very rapidly we might end up in a situation
// where we're allocating black during a nearly always-on GC.
// The result of this is a growing heap and ultimately an
// increase in RSS. By capping us at a point >0, we're essentially
// saying that we're OK using more CPU during the GC to prevent
// this growth in RSS.
//
// The current constant was chosen empirically: given a sufficiently
// fast/scalable allocator with 48 Ps that could drive the trigger ratio
// to <0.05, this constant causes applications to retain the same peak
// RSS compared to not having this allocator.
minTriggerRatio := 0.6 * scalingFactor
if triggerRatio < minTriggerRatio {
triggerRatio = minTriggerRatio
}
} else if triggerRatio < 0 {
// gcpercent < 0, so just make sure we're not getting a negative
// triggerRatio. This case isn't expected to happen in practice,
// and doesn't really matter because if gcpercent < 0 then we won't
// ever consume triggerRatio further on in this function, but let's
// just be defensive here; the triggerRatio being negative is almost
// certainly undesirable.
triggerRatio = 0
}
memstats.triggerRatio = triggerRatio
// Compute the absolute GC trigger from the trigger ratio.
//
// We trigger the next GC cycle when the allocated heap has
// grown by the trigger ratio over the marked heap size.
// 根据触发器比率来计算绝对的 GC 触发器
//
// 当分配的堆的大小超过标记的堆大小时,我们触发下一个 GC 循环。
trigger := ^uint64(0)
if gcpercent >= 0 {
trigger = uint64(float64(memstats.heap_marked) * (1 + triggerRatio))
// Don't trigger below the minimum heap size.
// 小于最小堆大小时不触发
minTrigger := heapminimum