aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/go/_std_1.18/src/runtime/mbitmap.go
blob: 937968807b0eadd44688b6c3d398eb342e1ab50f (plain) (blame)
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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
// 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: type and heap bitmaps.
//
// Stack, data, and bss bitmaps
//
// Stack frames and global variables in the data and bss sections are
// described by bitmaps with 1 bit per pointer-sized word. A "1" bit
// means the word is a live pointer to be visited by the GC (referred to
// as "pointer"). A "0" bit means the word should be ignored by GC
// (referred to as "scalar", though it could be a dead pointer value).
//
// Heap bitmap
//
// The heap bitmap comprises 2 bits for each pointer-sized word in the heap,
// stored in the heapArena metadata backing each heap arena.
// That is, if ha is the heapArena for the arena starting a start,
// then ha.bitmap[0] holds the 2-bit entries for the four words start
// through start+3*ptrSize, ha.bitmap[1] holds the entries for
// start+4*ptrSize through start+7*ptrSize, and so on.
//
// In each 2-bit entry, the lower bit is a pointer/scalar bit, just
// like in the stack/data bitmaps described above. The upper bit
// indicates scan/dead: a "1" value ("scan") indicates that there may
// be pointers in later words of the allocation, and a "0" value
// ("dead") indicates there are no more pointers in the allocation. If
// the upper bit is 0, the lower bit must also be 0, and this
// indicates scanning can ignore the rest of the allocation.
//
// The 2-bit entries are split when written into the byte, so that the top half
// of the byte contains 4 high (scan) bits and the bottom half contains 4 low
// (pointer) bits. This form allows a copy from the 1-bit to the 4-bit form to
// keep the pointer bits contiguous, instead of having to space them out.
//
// The code makes use of the fact that the zero value for a heap
// bitmap means scalar/dead. This property must be preserved when
// modifying the encoding.
//
// The bitmap for noscan spans is not maintained. Code must ensure
// that an object is scannable before consulting its bitmap by
// checking either the noscan bit in the span or by consulting its
// type's information.

package runtime

import (
	"internal/goarch"
	"runtime/internal/atomic"
	"runtime/internal/sys"
	"unsafe"
)

const (
	bitPointer = 1 << 0
	bitScan    = 1 << 4

	heapBitsShift      = 1     // shift offset between successive bitPointer or bitScan entries
	wordsPerBitmapByte = 8 / 2 // heap words described by one bitmap byte

	// all scan/pointer bits in a byte
	bitScanAll    = bitScan | bitScan<<heapBitsShift | bitScan<<(2*heapBitsShift) | bitScan<<(3*heapBitsShift)
	bitPointerAll = bitPointer | bitPointer<<heapBitsShift | bitPointer<<(2*heapBitsShift) | bitPointer<<(3*heapBitsShift)
)

// addb returns the byte pointer p+n.
//go:nowritebarrier
//go:nosplit
func addb(p *byte, n uintptr) *byte {
	// Note: wrote out full expression instead of calling add(p, n)
	// to reduce the number of temporaries generated by the
	// compiler for this trivial expression during inlining.
	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + n))
}

// subtractb returns the byte pointer p-n.
//go:nowritebarrier
//go:nosplit
func subtractb(p *byte, n uintptr) *byte {
	// Note: wrote out full expression instead of calling add(p, -n)
	// to reduce the number of temporaries generated by the
	// compiler for this trivial expression during inlining.
	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - n))
}

// add1 returns the byte pointer p+1.
//go:nowritebarrier
//go:nosplit
func add1(p *byte) *byte {
	// Note: wrote out full expression instead of calling addb(p, 1)
	// to reduce the number of temporaries generated by the
	// compiler for this trivial expression during inlining.
	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + 1))
}

// subtract1 returns the byte pointer p-1.
//go:nowritebarrier
//
// nosplit because it is used during write barriers and must not be preempted.
//go:nosplit
func subtract1(p *byte) *byte {
	// Note: wrote out full expression instead of calling subtractb(p, 1)
	// to reduce the number of temporaries generated by the
	// compiler for this trivial expression during inlining.
	return (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) - 1))
}

// heapBits provides access to the bitmap bits for a single heap word.
// The methods on heapBits take value receivers so that the compiler
// can more easily inline calls to those methods and registerize the
// struct fields independently.
type heapBits struct {
	bitp  *uint8
	shift uint32
	arena uint32 // Index of heap arena containing bitp
	last  *uint8 // Last byte arena's bitmap
}

// Make the compiler check that heapBits.arena is large enough to hold
// the maximum arena frame number.
var _ = heapBits{arena: (1<<heapAddrBits)/heapArenaBytes - 1}

// markBits provides access to the mark bit for an object in the heap.
// bytep points to the byte holding the mark bit.
// mask is a byte with a single bit set that can be &ed with *bytep
// to see if the bit has been set.
// *m.byte&m.mask != 0 indicates the mark bit is set.
// index can be used along with span information to generate
// the address of the object in the heap.
// We maintain one set of mark bits for allocation and one for
// marking purposes.
type markBits struct {
	bytep *uint8
	mask  uint8
	index uintptr
}

//go:nosplit
func (s *mspan) allocBitsForIndex(allocBitIndex uintptr) markBits {
	bytep, mask := s.allocBits.bitp(allocBitIndex)
	return markBits{bytep, mask, allocBitIndex}
}

// refillAllocCache takes 8 bytes s.allocBits starting at whichByte
// and negates them so that ctz (count trailing zeros) instructions
// can be used. It then places these 8 bytes into the cached 64 bit
// s.allocCache.
func (s *mspan) refillAllocCache(whichByte uintptr) {
	bytes := (*[8]uint8)(unsafe.Pointer(s.allocBits.bytep(whichByte)))
	aCache := uint64(0)
	aCache |= uint64(bytes[0])
	aCache |= uint64(bytes[1]) << (1 * 8)
	aCache |= uint64(bytes[2]) << (2 * 8)
	aCache |= uint64(bytes[3]) << (3 * 8)
	aCache |= uint64(bytes[4]) << (4 * 8)
	aCache |= uint64(bytes[5]) << (5 * 8)
	aCache |= uint64(bytes[6]) << (6 * 8)
	aCache |= uint64(bytes[7]) << (7 * 8)
	s.allocCache = ^aCache
}

// nextFreeIndex returns the index of the next free object in s at
// or after s.freeindex.
// There are hardware instructions that can be used to make this
// faster if profiling warrants it.
func (s *mspan) nextFreeIndex() uintptr {
	sfreeindex := s.freeindex
	snelems := s.nelems
	if sfreeindex == snelems {
		return sfreeindex
	}
	if sfreeindex > snelems {
		throw("s.freeindex > s.nelems")
	}

	aCache := s.allocCache

	bitIndex := sys.Ctz64(aCache)
	for bitIndex == 64 {
		// Move index to start of next cached bits.
		sfreeindex = (sfreeindex + 64) &^ (64 - 1)
		if sfreeindex >= snelems {
			s.freeindex = snelems
			return snelems
		}
		whichByte := sfreeindex / 8
		// Refill s.allocCache with the next 64 alloc bits.
		s.refillAllocCache(whichByte)
		aCache = s.allocCache
		bitIndex = sys.Ctz64(aCache)
		// nothing available in cached bits
		// grab the next 8 bytes and try again.
	}
	result := sfreeindex + uintptr(bitIndex)
	if result >= snelems {
		s.freeindex = snelems
		return snelems
	}

	s.allocCache >>= uint(bitIndex + 1)
	sfreeindex = result + 1

	if sfreeindex%64 == 0 && sfreeindex != snelems {
		// We just incremented s.freeindex so it isn't 0.
		// As each 1 in s.allocCache was encountered and used for allocation
		// it was shifted away. At this point s.allocCache contains all 0s.
		// Refill s.allocCache so that it corresponds
		// to the bits at s.allocBits starting at s.freeindex.
		whichByte := sfreeindex / 8
		s.refillAllocCache(whichByte)
	}
	s.freeindex = sfreeindex
	return result
}

// isFree reports whether the index'th object in s is unallocated.
//
// The caller must ensure s.state is mSpanInUse, and there must have
// been no preemption points since ensuring this (which could allow a
// GC transition, which would allow the state to change).
func (s *mspan) isFree(index uintptr) bool {
	if index < s.freeindex {
		return false
	}
	bytep, mask := s.allocBits.bitp(index)
	return *bytep&mask == 0
}

// divideByElemSize returns n/s.elemsize.
// n must be within [0, s.npages*_PageSize),
// or may be exactly s.npages*_PageSize
// if s.elemsize is from sizeclasses.go.
func (s *mspan) divideByElemSize(n uintptr) uintptr {
	const doubleCheck = false

	// See explanation in mksizeclasses.go's computeDivMagic.
	q := uintptr((uint64(n) * uint64(s.divMul)) >> 32)

	if doubleCheck && q != n/s.elemsize {
		println(n, "/", s.elemsize, "should be", n/s.elemsize, "but got", q)
		throw("bad magic division")
	}
	return q
}

func (s *mspan) objIndex(p uintptr) uintptr {
	return s.divideByElemSize(p - s.base())
}

func markBitsForAddr(p uintptr) markBits {
	s := spanOf(p)
	objIndex := s.objIndex(p)
	return s.markBitsForIndex(objIndex)
}

func (s *mspan) markBitsForIndex(objIndex uintptr) markBits {
	bytep, mask := s.gcmarkBits.bitp(objIndex)
	return markBits{bytep, mask, objIndex}
}

func (s *mspan) markBitsForBase() markBits {
	return markBits{(*uint8)(s.gcmarkBits), uint8(1), 0}
}

// isMarked reports whether mark bit m is set.
func (m markBits) isMarked() bool {
	return *m.bytep&m.mask != 0
}

// setMarked sets the marked bit in the markbits, atomically.
func (m markBits) setMarked() {
	// Might be racing with other updates, so use atomic update always.
	// We used to be clever here and use a non-atomic update in certain
	// cases, but it's not worth the risk.
	atomic.Or8(m.bytep, m.mask)
}

// setMarkedNonAtomic sets the marked bit in the markbits, non-atomically.
func (m markBits) setMarkedNonAtomic() {
	*m.bytep |= m.mask
}

// clearMarked clears the marked bit in the markbits, atomically.
func (m markBits) clearMarked() {
	// Might be racing with other updates, so use atomic update always.
	// We used to be clever here and use a non-atomic update in certain
	// cases, but it's not worth the risk.
	atomic.And8(m.bytep, ^m.mask)
}

// markBitsForSpan returns the markBits for the span base address base.
func markBitsForSpan(base uintptr) (mbits markBits) {
	mbits = markBitsForAddr(base)
	if mbits.mask != 1 {
		throw("markBitsForSpan: unaligned start")
	}
	return mbits
}

// advance advances the markBits to the next object in the span.
func (m *markBits) advance() {
	if m.mask == 1<<7 {
		m.bytep = (*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(m.bytep)) + 1))
		m.mask = 1
	} else {
		m.mask = m.mask << 1
	}
	m.index++
}

// heapBitsForAddr returns the heapBits for the address addr.
// The caller must ensure addr is in an allocated span.
// In particular, be careful not to point past the end of an object.
//
// nosplit because it is used during write barriers and must not be preempted.
//go:nosplit
func heapBitsForAddr(addr uintptr) (h heapBits) {
	// 2 bits per word, 4 pairs per byte, and a mask is hard coded.
	arena := arenaIndex(addr)
	ha := mheap_.arenas[arena.l1()][arena.l2()]
	// The compiler uses a load for nil checking ha, but in this
	// case we'll almost never hit that cache line again, so it
	// makes more sense to do a value check.
	if ha == nil {
		// addr is not in the heap. Return nil heapBits, which
		// we expect to crash in the caller.
		return
	}
	h.bitp = &ha.bitmap[(addr/(goarch.PtrSize*4))%heapArenaBitmapBytes]
	h.shift = uint32((addr / goarch.PtrSize) & 3)
	h.arena = uint32(arena)
	h.last = &ha.bitmap[len(ha.bitmap)-1]
	return
}

// clobberdeadPtr is a special value that is used by the compiler to
// clobber dead stack slots, when -clobberdead flag is set.
const clobberdeadPtr = uintptr(0xdeaddead | 0xdeaddead<<((^uintptr(0)>>63)*32))

// badPointer throws bad pointer in heap panic.
func badPointer(s *mspan, p, refBase, refOff uintptr) {
	// Typically this indicates an incorrect use
	// of unsafe or cgo to store a bad pointer in
	// the Go heap. It may also indicate a runtime
	// bug.
	//
	// TODO(austin): We could be more aggressive
	// and detect pointers to unallocated objects
	// in allocated spans.
	printlock()
	print("runtime: pointer ", hex(p))
	if s != nil {
		state := s.state.get()
		if state != mSpanInUse {
			print(" to unallocated span")
		} else {
			print(" to unused region of span")
		}
		print(" span.base()=", hex(s.base()), " span.limit=", hex(s.limit), " span.state=", state)
	}
	print("\n")
	if refBase != 0 {
		print("runtime: found in object at *(", hex(refBase), "+", hex(refOff), ")\n")
		gcDumpObject("object", refBase, refOff)
	}
	getg().m.traceback = 2
	throw("found bad pointer in Go heap (incorrect use of unsafe or cgo?)")
}

// findObject returns the base address for the heap object containing
// the address p, the object's span, and the index of the object in s.
// If p does not point into a heap object, it returns base == 0.
//
// If p points is an invalid heap pointer and debug.invalidptr != 0,
// findObject panics.
//
// refBase and refOff optionally give the base address of the object
// in which the pointer p was found and the byte offset at which it
// was found. These are used for error reporting.
//
// It is nosplit so it is safe for p to be a pointer to the current goroutine's stack.
// Since p is a uintptr, it would not be adjusted if the stack were to move.
//go:nosplit
func findObject(p, refBase, refOff uintptr) (base uintptr, s *mspan, objIndex uintptr) {
	s = spanOf(p)
	// If s is nil, the virtual address has never been part of the heap.
	// This pointer may be to some mmap'd region, so we allow it.
	if s == nil {
		if (GOARCH == "amd64" || GOARCH == "arm64") && p == clobberdeadPtr && debug.invalidptr != 0 {
			// Crash if clobberdeadPtr is seen. Only on AMD64 and ARM64 for now,
			// as they are the only platform where compiler's clobberdead mode is
			// implemented. On these platforms clobberdeadPtr cannot be a valid address.
			badPointer(s, p, refBase, refOff)
		}
		return
	}
	// If p is a bad pointer, it may not be in s's bounds.
	//
	// Check s.state to synchronize with span initialization
	// before checking other fields. See also spanOfHeap.
	if state := s.state.get(); state != mSpanInUse || p < s.base() || p >= s.limit {
		// Pointers into stacks are also ok, the runtime manages these explicitly.
		if state == mSpanManual {
			return
		}
		// The following ensures that we are rigorous about what data
		// structures hold valid pointers.
		if debug.invalidptr != 0 {
			badPointer(s, p, refBase, refOff)
		}
		return
	}

	objIndex = s.objIndex(p)
	base = s.base() + objIndex*s.elemsize
	return
}

// verifyNotInHeapPtr reports whether converting the not-in-heap pointer into a unsafe.Pointer is ok.
//go:linkname reflect_verifyNotInHeapPtr reflect.verifyNotInHeapPtr
func reflect_verifyNotInHeapPtr(p uintptr) bool {
	// Conversion to a pointer is ok as long as findObject above does not call badPointer.
	// Since we're already promised that p doesn't point into the heap, just disallow heap
	// pointers and the special clobbered pointer.
	return spanOf(p) == nil && p != clobberdeadPtr
}

// next returns the heapBits describing the next pointer-sized word in memory.
// That is, if h describes address p, h.next() describes p+ptrSize.
// Note that next does not modify h. The caller must record the result.
//
// nosplit because it is used during write barriers and must not be preempted.
//go:nosplit
func (h heapBits) next() heapBits {
	if h.shift < 3*heapBitsShift {
		h.shift += heapBitsShift
	} else if h.bitp != h.last {
		h.bitp, h.shift = add1(h.bitp), 0
	} else {
		// Move to the next arena.
		return h.nextArena()
	}
	return h
}

// nextArena advances h to the beginning of the next heap arena.
//
// This is a slow-path helper to next. gc's inliner knows that
// heapBits.next can be inlined even though it calls this. This is
// marked noinline so it doesn't get inlined into next and cause next
// to be too big to inline.
//
//go:nosplit
//go:noinline
func (h heapBits) nextArena() heapBits {
	h.arena++
	ai := arenaIdx(h.arena)
	l2 := mheap_.arenas[ai.l1()]
	if l2 == nil {
		// We just passed the end of the object, which
		// was also the end of the heap. Poison h. It
		// should never be dereferenced at this point.
		return heapBits{}
	}
	ha := l2[ai.l2()]
	if ha == nil {
		return heapBits{}
	}
	h.bitp, h.shift = &ha.bitmap[0], 0
	h.last = &ha.bitmap[len(ha.bitmap)-1]
	return h
}

// forward returns the heapBits describing n pointer-sized words ahead of h in memory.
// That is, if h describes address p, h.forward(n) describes p+n*ptrSize.
// h.forward(1) is equivalent to h.next(), just slower.
// Note that forward does not modify h. The caller must record the result.
// bits returns the heap bits for the current word.
//go:nosplit
func (h heapBits) forward(n uintptr) heapBits {
	n += uintptr(h.shift) / heapBitsShift
	nbitp := uintptr(unsafe.Pointer(h.bitp)) + n/4
	h.shift = uint32(n%4) * heapBitsShift
	if nbitp <= uintptr(unsafe.Pointer(h.last)) {
		h.bitp = (*uint8)(unsafe.Pointer(nbitp))
		return h
	}

	// We're in a new heap arena.
	past := nbitp - (uintptr(unsafe.Pointer(h.last)) + 1)
	h.arena += 1 + uint32(past/heapArenaBitmapBytes)
	ai := arenaIdx(h.arena)
	if l2 := mheap_.arenas[ai.l1()]; l2 != nil && l2[ai.l2()] != nil {
		a := l2[ai.l2()]
		h.bitp = &a.bitmap[past%heapArenaBitmapBytes]
		h.last = &a.bitmap[len(a.bitmap)-1]
	} else {
		h.bitp, h.last = nil, nil
	}
	return h
}

// forwardOrBoundary is like forward, but stops at boundaries between
// contiguous sections of the bitmap. It returns the number of words
// advanced over, which will be <= n.
func (h heapBits) forwardOrBoundary(n uintptr) (heapBits, uintptr) {
	maxn := 4 * ((uintptr(unsafe.Pointer(h.last)) + 1) - uintptr(unsafe.Pointer(h.bitp)))
	if n > maxn {
		n = maxn
	}
	return h.forward(n), n
}

// The caller can test morePointers and isPointer by &-ing with bitScan and bitPointer.
// The result includes in its higher bits the bits for subsequent words
// described by the same bitmap byte.
//
// nosplit because it is used during write barriers and must not be preempted.
//go:nosplit
func (h heapBits) bits() uint32 {
	// The (shift & 31) eliminates a test and conditional branch
	// from the generated code.
	return uint32(*h.bitp) >> (h.shift & 31)
}

// morePointers reports whether this word and all remaining words in this object
// are scalars.
// h must not describe the second word of the object.
func (h heapBits) morePointers() bool {
	return h.bits()&bitScan != 0
}

// isPointer reports whether the heap bits describe a pointer word.
//
// nosplit because it is used during write barriers and must not be preempted.
//go:nosplit
func (h heapBits) isPointer() bool {
	return h.bits()&bitPointer != 0
}

// bulkBarrierPreWrite executes a write barrier
// for every pointer slot in the memory range [src, src+size),
// using pointer/scalar information from [dst, dst+size).
// This executes the write barriers necessary before a memmove.
// src, dst, and size must be pointer-aligned.
// The range [dst, dst+size) must lie within a single object.
// It does not perform the actual writes.
//
// As a special case, src == 0 indicates that this is being used for a
// memclr. bulkBarrierPreWrite will pass 0 for the src of each write
// barrier.
//
// Callers should call bulkBarrierPreWrite immediately before
// calling memmove(dst, src, size). This function is marked nosplit
// to avoid being preempted; the GC must not stop the goroutine
// between the memmove and the execution of the barriers.
// The caller is also responsible for cgo pointer checks if this
// may be writing Go pointers into non-Go memory.
//
// The pointer bitmap is not maintained for allocations containing
// no pointers at all; any caller of bulkBarrierPreWrite must first
// make sure the underlying allocation contains pointers, usually
// by checking typ.ptrdata.
//
// Callers must perform cgo checks if writeBarrier.cgo.
//
//go:nosplit
func bulkBarrierPreWrite(dst, src, size uintptr) {
	if (dst|src|size)&(goarch.PtrSize-1) != 0 {
		throw("bulkBarrierPreWrite: unaligned arguments")
	}
	if !writeBarrier.needed {
		return
	}
	if s := spanOf(dst); s == nil {
		// If dst is a global, use the data or BSS bitmaps to
		// execute write barriers.
		for _, datap := range activeModules() {
			if datap.data <= dst && dst < datap.edata {
				bulkBarrierBitmap(dst, src, size, dst-datap.data, datap.gcdatamask.bytedata)
				return
			}
		}
		for _, datap := range activeModules() {
			if datap.bss <= dst && dst < datap.ebss {
				bulkBarrierBitmap(dst, src, size, dst-datap.bss, datap.gcbssmask.bytedata)
				return
			}
		}
		return
	} else if s.state.get() != mSpanInUse || dst < s.base() || s.limit <= dst {
		// dst was heap memory at some point, but isn't now.
		// It can't be a global. It must be either our stack,
		// or in the case of direct channel sends, it could be
		// another stack. Either way, no need for barriers.
		// This will also catch if dst is in a freed span,
		// though that should never have.
		return
	}

	buf := &getg().m.p.ptr().wbBuf
	h := heapBitsForAddr(dst)
	if src == 0 {
		for i := uintptr(0); i < size; i += goarch.PtrSize {
			if h.isPointer() {
				dstx := (*uintptr)(unsafe.Pointer(dst + i))
				if !buf.putFast(*dstx, 0) {
					wbBufFlush(nil, 0)
				}
			}
			h = h.next()
		}
	} else {
		for i := uintptr(0); i < size; i += goarch.PtrSize {
			if h.isPointer() {
				dstx := (*uintptr)(unsafe.Pointer(dst + i))
				srcx := (*uintptr)(unsafe.Pointer(src + i))
				if !buf.putFast(*dstx, *srcx) {
					wbBufFlush(nil, 0)
				}
			}
			h = h.next()
		}
	}
}

// bulkBarrierPreWriteSrcOnly is like bulkBarrierPreWrite but
// does not execute write barriers for [dst, dst+size).
//
// In addition to the requirements of bulkBarrierPreWrite
// callers need to ensure [dst, dst+size) is zeroed.
//
// This is used for special cases where e.g. dst was just
// created and zeroed with malloc.
//go:nosplit
func bulkBarrierPreWriteSrcOnly(dst, src, size uintptr) {
	if (dst|src|size)&(goarch.PtrSize-1) != 0 {
		throw("bulkBarrierPreWrite: unaligned arguments")
	}
	if !writeBarrier.needed {
		return
	}
	buf := &getg().m.p.ptr().wbBuf
	h := heapBitsForAddr(dst)
	for i := uintptr(0); i < size; i += goarch.PtrSize {
		if h.isPointer() {
			srcx := (*uintptr)(unsafe.Pointer(src + i))
			if !buf.putFast(0, *srcx) {
				wbBufFlush(nil, 0)
			}
		}
		h = h.next()
	}
}

// bulkBarrierBitmap executes write barriers for copying from [src,
// src+size) to [dst, dst+size) using a 1-bit pointer bitmap. src is
// assumed to start maskOffset bytes into the data covered by the
// bitmap in bits (which may not be a multiple of 8).
//
// This is used by bulkBarrierPreWrite for writes to data and BSS.
//
//go:nosplit
func bulkBarrierBitmap(dst, src, size, maskOffset uintptr, bits *uint8) {
	word := maskOffset / goarch.PtrSize
	bits = addb(bits, word/8)
	mask := uint8(1) << (word % 8)

	buf := &getg().m.p.ptr().wbBuf
	for i := uintptr(0); i < size; i += goarch.PtrSize {
		if mask == 0 {
			bits = addb(bits, 1)
			if *bits == 0 {
				// Skip 8 words.
				i += 7 * goarch.PtrSize
				continue
			}
			mask = 1
		}
		if *bits&mask != 0 {
			dstx := (*uintptr)(unsafe.Pointer(dst + i))
			if src == 0 {
				if !buf.putFast(*dstx, 0) {
					wbBufFlush(nil, 0)
				}
			} else {
				srcx := (*uintptr)(unsafe.Pointer(src + i))
				if !buf.putFast(*dstx, *srcx) {
					wbBufFlush(nil, 0)
				}
			}
		}
		mask <<= 1
	}
}

// typeBitsBulkBarrier executes a write barrier for every
// pointer that would be copied from [src, src+size) to [dst,
// dst+size) by a memmove using the type bitmap to locate those
// pointer slots.
//
// The type typ must correspond exactly to [src, src+size) and [dst, dst+size).
// dst, src, and size must be pointer-aligned.
// The type typ must have a plain bitmap, not a GC program.
// The only use of this function is in channel sends, and the
// 64 kB channel element limit takes care of this for us.
//
// Must not be preempted because it typically runs right before memmove,
// and the GC must observe them as an atomic action.
//
// Callers must perform cgo checks if writeBarrier.cgo.
//
//go:nosplit
func typeBitsBulkBarrier(typ *_type, dst, src, size uintptr) {
	if typ == nil {
		throw("runtime: typeBitsBulkBarrier without type")
	}
	if typ.size != size {
		println("runtime: typeBitsBulkBarrier with type ", typ.string(), " of size ", typ.size, " but memory size", size)
		throw("runtime: invalid typeBitsBulkBarrier")
	}
	if typ.kind&kindGCProg != 0 {
		println("runtime: typeBitsBulkBarrier with type ", typ.string(), " with GC prog")
		throw("runtime: invalid typeBitsBulkBarrier")
	}
	if !writeBarrier.needed {
		return
	}
	ptrmask := typ.gcdata
	buf := &getg().m.p.ptr().wbBuf
	var bits uint32
	for i := uintptr(0); i < typ.ptrdata; i += goarch.PtrSize {
		if i&(goarch.PtrSize*8-1) == 0 {
			bits = uint32(*ptrmask)
			ptrmask = addb(ptrmask, 1)
		} else {
			bits = bits >> 1
		}
		if bits&1 != 0 {
			dstx := (*uintptr)(unsafe.Pointer(dst + i))
			srcx := (*uintptr)(unsafe.Pointer(src + i))
			if !buf.putFast(*dstx, *srcx) {
				wbBufFlush(nil, 0)
			}
		}
	}
}

// The methods operating on spans all require that h has been returned
// by heapBitsForSpan and that size, n, total are the span layout description
// returned by the mspan's layout method.
// If total > size*n, it means that there is extra leftover memory in the span,
// usually due to rounding.
//
// TODO(rsc): Perhaps introduce a different heapBitsSpan type.

// initSpan initializes the heap bitmap for a span.
// If this is a span of pointer-sized objects, it initializes all
// words to pointer/scan.
// Otherwise, it initializes all words to scalar/dead.
func (h heapBits) initSpan(s *mspan) {
	// Clear bits corresponding to objects.
	nw := (s.npages << _PageShift) / goarch.PtrSize
	if nw%wordsPerBitmapByte != 0 {
		throw("initSpan: unaligned length")
	}
	if h.shift != 0 {
		throw("initSpan: unaligned base")
	}
	isPtrs := goarch.PtrSize == 8 && s.elemsize == goarch.PtrSize
	for nw > 0 {
		hNext, anw := h.forwardOrBoundary(nw)
		nbyte := anw / wordsPerBitmapByte
		if isPtrs {
			bitp := h.bitp
			for i := uintptr(0); i < nbyte; i++ {
				*bitp = bitPointerAll | bitScanAll
				bitp = add1(bitp)
			}
		} else {
			memclrNoHeapPointers(unsafe.Pointer(h.bitp), nbyte)
		}
		h = hNext
		nw -= anw
	}
}

// countAlloc returns the number of objects allocated in span s by
// scanning the allocation bitmap.
func (s *mspan) countAlloc() int {
	count := 0
	bytes := divRoundUp(s.nelems, 8)
	// Iterate over each 8-byte chunk and count allocations
	// with an intrinsic. Note that newMarkBits guarantees that
	// gcmarkBits will be 8-byte aligned, so we don't have to
	// worry about edge cases, irrelevant bits will simply be zero.
	for i := uintptr(0); i < bytes; i += 8 {
		// Extract 64 bits from the byte pointer and get a OnesCount.
		// Note that the unsafe cast here doesn't preserve endianness,
		// but that's OK. We only care about how many bits are 1, not
		// about the order we discover them in.
		mrkBits := *(*uint64)(unsafe.Pointer(s.gcmarkBits.bytep(i)))
		count += sys.OnesCount64(mrkBits)
	}
	return count
}

// heapBitsSetType records that the new allocation [x, x+size)
// holds in [x, x+dataSize) one or more values of type typ.
// (The number of values is given by dataSize / typ.size.)
// If dataSize < size, the fragment [x+dataSize, x+size) is
// recorded as non-pointer data.
// It is known that the type has pointers somewhere;
// malloc does not call heapBitsSetType when there are no pointers,
// because all free objects are marked as noscan during
// heapBitsSweepSpan.
//
// There can only be one allocation from a given span active at a time,
// and the bitmap for a span always falls on byte boundaries,
// so there are no write-write races for access to the heap bitmap.
// Hence, heapBitsSetType can access the bitmap without atomics.
//
// There can be read-write races between heapBitsSetType and things
// that read the heap bitmap like scanobject. However, since
// heapBitsSetType is only used for objects that have not yet been
// made reachable, readers will ignore bits being modified by this
// function. This does mean this function cannot transiently modify
// bits that belong to neighboring objects. Also, on weakly-ordered
// machines, callers must execute a store/store (publication) barrier
// between calling this function and making the object reachable.
func heapBitsSetType(x, size, dataSize uintptr, typ *_type) {
	const doubleCheck = false // slow but helpful; enable to test modifications to this code

	const (
		mask1 = bitPointer | bitScan                        // 00010001
		mask2 = bitPointer | bitScan | mask1<<heapBitsShift // 00110011
		mask3 = bitPointer | bitScan | mask2<<heapBitsShift // 01110111
	)

	// dataSize is always size rounded up to the next malloc size class,
	// except in the case of allocating a defer block, in which case
	// size is sizeof(_defer{}) (at least 6 words) and dataSize may be
	// arbitrarily larger.
	//
	// The checks for size == goarch.PtrSize and size == 2*goarch.PtrSize can therefore
	// assume that dataSize == size without checking it explicitly.

	if goarch.PtrSize == 8 && size == goarch.PtrSize {
		// It's one word and it has pointers, it must be a pointer.
		// Since all allocated one-word objects are pointers
		// (non-pointers are aggregated into tinySize allocations),
		// initSpan sets the pointer bits for us. Nothing to do here.
		if doubleCheck {
			h := heapBitsForAddr(x)
			if !h.isPointer() {
				throw("heapBitsSetType: pointer bit missing")
			}
			if !h.morePointers() {
				throw("heapBitsSetType: scan bit missing")
			}
		}
		return
	}

	h := heapBitsForAddr(x)
	ptrmask := typ.gcdata // start of 1-bit pointer mask (or GC program, handled below)

	// 2-word objects only have 4 bitmap bits and 3-word objects only have 6 bitmap bits.
	// Therefore, these objects share a heap bitmap byte with the objects next to them.
	// These are called out as a special case primarily so the code below can assume all
	// objects are at least 4 words long and that their bitmaps start either at the beginning
	// of a bitmap byte, or half-way in (h.shift of 0 and 2 respectively).

	if size == 2*goarch.PtrSize {
		if typ.size == goarch.PtrSize {
			// We're allocating a block big enough to hold two pointers.
			// On 64-bit, that means the actual object must be two pointers,
			// or else we'd have used the one-pointer-sized block.
			// On 32-bit, however, this is the 8-byte block, the smallest one.
			// So it could be that we're allocating one pointer and this was
			// just the smallest block available. Distinguish by checking dataSize.
			// (In general the number of instances of typ being allocated is
			// dataSize/typ.size.)
			if goarch.PtrSize == 4 && dataSize == goarch.PtrSize {
				// 1 pointer object. On 32-bit machines clear the bit for the
				// unused second word.
				*h.bitp &^= (bitPointer | bitScan | (bitPointer|bitScan)<<heapBitsShift) << h.shift
				*h.bitp |= (bitPointer | bitScan) << h.shift
			} else {
				// 2-element array of pointer.
				*h.bitp |= (bitPointer | bitScan | (bitPointer|bitScan)<<heapBitsShift) << h.shift
			}
			return
		}
		// Otherwise typ.size must be 2*goarch.PtrSize,
		// and typ.kind&kindGCProg == 0.
		if doubleCheck {
			if typ.size != 2*goarch.PtrSize || typ.kind&kindGCProg != 0 {
				print("runtime: heapBitsSetType size=", size, " but typ.size=", typ.size, " gcprog=", typ.kind&kindGCProg != 0, "\n")
				throw("heapBitsSetType")
			}
		}
		b := uint32(*ptrmask)
		hb := b & 3
		hb |= bitScanAll & ((bitScan << (typ.ptrdata / goarch.PtrSize)) - 1)
		// Clear the bits for this object so we can set the
		// appropriate ones.
		*h.bitp &^= (bitPointer | bitScan | ((bitPointer | bitScan) << heapBitsShift)) << h.shift
		*h.bitp |= uint8(hb << h.shift)
		return
	} else if size == 3*goarch.PtrSize {
		b := uint8(*ptrmask)
		if doubleCheck {
			if b == 0 {
				println("runtime: invalid type ", typ.string())
				throw("heapBitsSetType: called with non-pointer type")
			}
			if goarch.PtrSize != 8 {
				throw("heapBitsSetType: unexpected 3 pointer wide size class on 32 bit")
			}
			if typ.kind&kindGCProg != 0 {
				throw("heapBitsSetType: unexpected GC prog for 3 pointer wide size class")
			}
			if typ.size == 2*goarch.PtrSize {
				print("runtime: heapBitsSetType size=", size, " but typ.size=", typ.size, "\n")
				throw("heapBitsSetType: inconsistent object sizes")
			}
		}
		if typ.size == goarch.PtrSize {
			// The type contains a pointer otherwise heapBitsSetType wouldn't have been called.
			// Since the type is only 1 pointer wide and contains a pointer, its gcdata must be exactly 1.
			if doubleCheck && *typ.gcdata != 1 {
				print("runtime: heapBitsSetType size=", size, " typ.size=", typ.size, "but *typ.gcdata", *typ.gcdata, "\n")
				throw("heapBitsSetType: unexpected gcdata for 1 pointer wide type size in 3 pointer wide size class")
			}
			// 3 element array of pointers. Unrolling ptrmask 3 times into p yields 00000111.
			b = 7
		}

		hb := b & 7
		// Set bitScan bits for all pointers.
		hb |= hb << wordsPerBitmapByte
		// First bitScan bit is always set since the type contains pointers.
		hb |= bitScan
		// Second bitScan bit needs to also be set if the third bitScan bit is set.
		hb |= hb & (bitScan << (2 * heapBitsShift)) >> 1

		// For h.shift > 1 heap bits cross a byte boundary and need to be written part
		// to h.bitp and part to the next h.bitp.
		switch h.shift {
		case 0:
			*h.bitp &^= mask3 << 0
			*h.bitp |= hb << 0
		case 1:
			*h.bitp &^= mask3 << 1
			*h.bitp |= hb << 1
		case 2:
			*h.bitp &^= mask2 << 2
			*h.bitp |= (hb & mask2) << 2
			// Two words written to the first byte.
			// Advance two words to get to the next byte.
			h = h.next().next()
			*h.bitp &^= mask1
			*h.bitp |= (hb >> 2) & mask1
		case 3:
			*h.bitp &^= mask1 << 3
			*h.bitp |= (hb & mask1) << 3
			// One word written to the first byte.
			// Advance one word to get to the next byte.
			h = h.next()
			*h.bitp &^= mask2
			*h.bitp |= (hb >> 1) & mask2
		}
		return
	}

	// Copy from 1-bit ptrmask into 2-bit bitmap.
	// The basic approach is to use a single uintptr as a bit buffer,
	// alternating between reloading the buffer and writing bitmap bytes.
	// In general, one load can supply two bitmap byte writes.
	// This is a lot of lines of code, but it compiles into relatively few
	// machine instructions.

	outOfPlace := false
	if arenaIndex(x+size-1) != arenaIdx(h.arena) || (doubleCheck && fastrandn(2) == 0) {
		// This object spans heap arenas, so the bitmap may be
		// discontiguous. Unroll it into the object instead
		// and then copy it out.
		//
		// In doubleCheck mode, we randomly do this anyway to
		// stress test the bitmap copying path.
		outOfPlace = true
		h.bitp = (*uint8)(unsafe.Pointer(x))
		h.last = nil
	}

	var (
		// Ptrmask input.
		p     *byte   // last ptrmask byte read
		b     uintptr // ptrmask bits already loaded
		nb    uintptr // number of bits in b at next read
		endp  *byte   // final ptrmask byte to read (then repeat)
		endnb uintptr // number of valid bits in *endp
		pbits uintptr // alternate source of bits

		// Heap bitmap output.
		w     uintptr // words processed
		nw    uintptr // number of words to process
		hbitp *byte   // next heap bitmap byte to write
		hb    uintptr // bits being prepared for *hbitp
	)

	hbitp = h.bitp

	// Handle GC program. Delayed until this part of the code
	// so that we can use the same double-checking mechanism
	// as the 1-bit case. Nothing above could have encountered
	// GC programs: the cases were all too small.
	if typ.kind&kindGCProg != 0 {
		heapBitsSetTypeGCProg(h, typ.ptrdata, typ.size, dataSize, size, addb(typ.gcdata, 4))
		if doubleCheck {
			// Double-check the heap bits written by GC program
			// by running the GC program to create a 1-bit pointer mask
			// and then jumping to the double-check code below.
			// This doesn't catch bugs shared between the 1-bit and 4-bit
			// GC program execution, but it does catch mistakes specific
			// to just one of those and bugs in heapBitsSetTypeGCProg's
			// implementation of arrays.
			lock(&debugPtrmask.lock)
			if debugPtrmask.data == nil {
				debugPtrmask.data = (*byte)(persistentalloc(1<<20, 1, &memstats.other_sys))
			}
			ptrmask = debugPtrmask.data
			runGCProg(addb(typ.gcdata, 4), nil, ptrmask, 1)
		}
		goto Phase4
	}

	// Note about sizes:
	//
	// typ.size is the number of words in the object,
	// and typ.ptrdata is the number of words in the prefix
	// of the object that contains pointers. That is, the final
	// typ.size - typ.ptrdata words contain no pointers.
	// This allows optimization of a common pattern where
	// an object has a small header followed by a large scalar
	// buffer. If we know the pointers are over, we don't have
	// to scan the buffer's heap bitmap at all.
	// The 1-bit ptrmasks are sized to contain only bits for
	// the typ.ptrdata prefix, zero padded out to a full byte
	// of bitmap. This code sets nw (below) so that heap bitmap
	// bits are only written for the typ.ptrdata prefix; if there is
	// more room in the allocated object, the next heap bitmap
	// entry is a 00, indicating that there are no more pointers
	// to scan. So only the ptrmask for the ptrdata bytes is needed.
	//
	// Replicated copies are not as nice: if there is an array of
	// objects with scalar tails, all but the last tail does have to
	// be initialized, because there is no way to say "skip forward".
	// However, because of the possibility of a repeated type with
	// size not a multiple of 4 pointers (one heap bitmap byte),
	// the code already must handle the last ptrmask byte specially
	// by treating it as containing only the bits for endnb pointers,
	// where endnb <= 4. We represent large scalar tails that must
	// be expanded in the replication by setting endnb larger than 4.
	// This will have the effect of reading many bits out of b,
	// but once the real bits are shifted out, b will supply as many
	// zero bits as we try to read, which is exactly what we need.

	p = ptrmask
	if typ.size < dataSize {
		// Filling in bits for an array of typ.
		// Set up for repetition of ptrmask during main loop.
		// Note that ptrmask describes only a prefix of
		const maxBits = goarch.PtrSize*8 - 7
		if typ.ptrdata/goarch.PtrSize <= maxBits {
			// Entire ptrmask fits in uintptr with room for a byte fragment.
			// Load into pbits and never read from ptrmask again.
			// This is especially important when the ptrmask has
			// fewer than 8 bits in it; otherwise the reload in the middle
			// of the Phase 2 loop would itself need to loop to gather
			// at least 8 bits.

			// Accumulate ptrmask into b.
			// ptrmask is sized to describe only typ.ptrdata, but we record
			// it as describing typ.size bytes, since all the high bits are zero.
			nb = typ.ptrdata / goarch.PtrSize
			for i := uintptr(0); i < nb; i += 8 {
				b |= uintptr(*p) << i
				p = add1(p)
			}
			nb = typ.size / goarch.PtrSize

			// Replicate ptrmask to fill entire pbits uintptr.
			// Doubling and truncating is fewer steps than
			// iterating by nb each time. (nb could be 1.)
			// Since we loaded typ.ptrdata/goarch.PtrSize bits
			// but are pretending to have typ.size/goarch.PtrSize,
			// there might be no replication necessary/possible.
			pbits = b
			endnb = nb
			if nb+nb <= maxBits {
				for endnb <= goarch.PtrSize*8 {
					pbits |= pbits << endnb
					endnb += endnb
				}
				// Truncate to a multiple of original ptrmask.
				// Because nb+nb <= maxBits, nb fits in a byte.
				// Byte division is cheaper than uintptr division.
				endnb = uintptr(maxBits/byte(nb)) * nb
				pbits &= 1<<endnb - 1
				b = pbits
				nb = endnb
			}

			// Clear p and endp as sentinel for using pbits.
			// Checked during Phase 2 loop.
			p = nil
			endp = nil
		} else {
			// Ptrmask is larger. Read it multiple times.
			n := (typ.ptrdata/goarch.PtrSize+7)/8 - 1
			endp = addb(ptrmask, n)
			endnb = typ.size/goarch.PtrSize - n*8
		}
	}
	if p != nil {
		b = uintptr(*p)
		p = add1(p)
		nb = 8
	}

	if typ.size == dataSize {
		// Single entry: can stop once we reach the non-pointer data.
		nw = typ.ptrdata / goarch.PtrSize
	} else {
		// Repeated instances of typ in an array.
		// Have to process first N-1 entries in full, but can stop
		// once we reach the non-pointer data in the final entry.
		nw = ((dataSize/typ.size-1)*typ.size + typ.ptrdata) / goarch.PtrSize
	}
	if nw == 0 {
		// No pointers! Caller was supposed to check.
		println("runtime: invalid type ", typ.string())
		throw("heapBitsSetType: called with non-pointer type")
		return
	}

	// Phase 1: Special case for leading byte (shift==0) or half-byte (shift==2).
	// The leading byte is special because it contains the bits for word 1,
	// which does not have the scan bit set.
	// The leading half-byte is special because it's a half a byte,
	// so we have to be careful with the bits already there.
	switch {
	default:
		throw("heapBitsSetType: unexpected shift")

	case h.shift == 0:
		// Ptrmask and heap bitmap are aligned.
		//
		// This is a fast path for small objects.
		//
		// The first byte we write out covers the first four
		// words of the object. The scan/dead bit on the first
		// word must be set to scan since there are pointers
		// somewhere in the object.
		// In all following words, we set the scan/dead
		// appropriately to indicate that the object continues
		// to the next 2-bit entry in the bitmap.
		//
		// We set four bits at a time here, but if the object
		// is fewer than four words, phase 3 will clear
		// unnecessary bits.
		hb = b & bitPointerAll
		hb |= bitScanAll
		if w += 4; w >= nw {
			goto Phase3
		}
		*hbitp = uint8(hb)
		hbitp = add1(hbitp)
		b >>= 4
		nb -= 4

	case h.shift == 2:
		// Ptrmask and heap bitmap are misaligned.
		//
		// On 32 bit architectures only the 6-word object that corresponds
		// to a 24 bytes size class can start with h.shift of 2 here since
		// all other non 16 byte aligned size classes have been handled by
		// special code paths at the beginning of heapBitsSetType on 32 bit.
		//
		// Many size classes are only 16 byte aligned. On 64 bit architectures
		// this results in a heap bitmap position starting with a h.shift of 2.
		//
		// The bits for the first two words are in a byte shared
		// with another object, so we must be careful with the bits
		// already there.
		//
		// We took care of 1-word, 2-word, and 3-word objects above,
		// so this is at least a 6-word object.
		hb = (b & (bitPointer | bitPointer<<heapBitsShift)) << (2 * heapBitsShift)
		hb |= bitScan << (2 * heapBitsShift)
		if nw > 1 {
			hb |= bitScan << (3 * heapBitsShift)
		}
		b >>= 2
		nb -= 2
		*hbitp &^= uint8((bitPointer | bitScan | ((bitPointer | bitScan) << heapBitsShift)) << (2 * heapBitsShift))
		*hbitp |= uint8(hb)
		hbitp = add1(hbitp)
		if w += 2; w >= nw {
			// We know that there is more data, because we handled 2-word and 3-word objects above.
			// This must be at least a 6-word object. If we're out of pointer words,
			// mark no scan in next bitmap byte and finish.
			hb = 0
			w += 4
			goto Phase3
		}
	}

	// Phase 2: Full bytes in bitmap, up to but not including write to last byte (full or partial) in bitmap.
	// The loop computes the bits for that last write but does not execute the write;
	// it leaves the bits in hb for processing by phase 3.
	// To avoid repeated adjustment of nb, we subtract out the 4 bits we're going to
	// use in the first half of the loop right now, and then we only adjust nb explicitly
	// if the 8 bits used by each iteration isn't balanced by 8 bits loaded mid-loop.
	nb -= 4
	for {
		// Emit bitmap byte.
		// b has at least nb+4 bits, with one exception:
		// if w+4 >= nw, then b has only nw-w bits,
		// but we'll stop at the break and then truncate
		// appropriately in Phase 3.
		hb = b & bitPointerAll
		hb |= bitScanAll
		if w += 4; w >= nw {
			break
		}
		*hbitp = uint8(hb)
		hbitp = add1(hbitp)
		b >>= 4

		// Load more bits. b has nb right now.
		if p != endp {
			// Fast path: keep reading from ptrmask.
			// nb unmodified: we just loaded 8 bits,
			// and the next iteration will consume 8 bits,
			// leaving us with the same nb the next time we're here.
			if nb < 8 {
				b |= uintptr(*p) << nb
				p = add1(p)
			} else {
				// Reduce the number of bits in b.
				// This is important if we skipped
				// over a scalar tail, since nb could
				// be larger than the bit width of b.
				nb -= 8
			}
		} else if p == nil {
			// Almost as fast path: track bit count and refill from pbits.
			// For short repetitions.
			if nb < 8 {
				b |= pbits << nb
				nb += endnb
			}
			nb -= 8 // for next iteration
		} else {
			// Slow path: reached end of ptrmask.
			// Process final partial byte and rewind to start.
			b |= uintptr(*p) << nb
			nb += endnb
			if nb < 8 {
				b |= uintptr(*ptrmask) << nb
				p = add1(ptrmask)
			} else {
				nb -= 8
				p = ptrmask
			}
		}

		// Emit bitmap byte.
		hb = b & bitPointerAll
		hb |= bitScanAll
		if w += 4; w >= nw {
			break
		}
		*hbitp = uint8(hb)
		hbitp = add1(hbitp)
		b >>= 4
	}

Phase3:
	// Phase 3: Write last byte or partial byte and zero the rest of the bitmap entries.
	if w > nw {
		// Counting the 4 entries in hb not yet written to memory,
		// there are more entries than possible pointer slots.
		// Discard the excess entries (can't be more than 3).
		mask := uintptr(1)<<(4-(w-nw)) - 1
		hb &= mask | mask<<4 // apply mask to both pointer bits and scan bits
	}

	// Change nw from counting possibly-pointer words to total words in allocation.
	nw = size / goarch.PtrSize

	// Write whole bitmap bytes.
	// The first is hb, the rest are zero.
	if w <= nw {
		*hbitp = uint8(hb)
		hbitp = add1(hbitp)
		hb = 0 // for possible final half-byte below
		for w += 4; w <= nw; w += 4 {
			*hbitp = 0
			hbitp = add1(hbitp)
		}
	}

	// Write final partial bitmap byte if any.
	// We know w > nw, or else we'd still be in the loop above.
	// It can be bigger only due to the 4 entries in hb that it counts.
	// If w == nw+4 then there's nothing left to do: we wrote all nw entries
	// and can discard the 4 sitting in hb.
	// But if w == nw+2, we need to write first two in hb.
	// The byte is shared with the next object, so be careful with
	// existing bits.
	if w == nw+2 {
		*hbitp = *hbitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | uint8(hb)
	}

Phase4:
	// Phase 4: Copy unrolled bitmap to per-arena bitmaps, if necessary.
	if outOfPlace {
		// TODO: We could probably make this faster by
		// handling [x+dataSize, x+size) specially.
		h := heapBitsForAddr(x)
		// cnw is the number of heap words, or bit pairs
		// remaining (like nw above).
		cnw := size / goarch.PtrSize
		src := (*uint8)(unsafe.Pointer(x))
		// We know the first and last byte of the bitmap are
		// not the same, but it's still possible for small
		// objects span arenas, so it may share bitmap bytes
		// with neighboring objects.
		//
		// Handle the first byte specially if it's shared. See
		// Phase 1 for why this is the only special case we need.
		if doubleCheck {
			if !(h.shift == 0 || h.shift == 2) {
				print("x=", x, " size=", size, " cnw=", h.shift, "\n")
				throw("bad start shift")
			}
		}
		if h.shift == 2 {
			*h.bitp = *h.bitp&^((bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift)<<(2*heapBitsShift)) | *src
			h = h.next().next()
			cnw -= 2
			src = addb(src, 1)
		}
		// We're now byte aligned. Copy out to per-arena
		// bitmaps until the last byte (which may again be
		// partial).
		for cnw >= 4 {
			// This loop processes four words at a time,
			// so round cnw down accordingly.
			hNext, words := h.forwardOrBoundary(cnw / 4 * 4)

			// n is the number of bitmap bytes to copy.
			n := words / 4
			memmove(unsafe.Pointer(h.bitp), unsafe.Pointer(src), n)
			cnw -= words
			h = hNext
			src = addb(src, n)
		}
		if doubleCheck && h.shift != 0 {
			print("cnw=", cnw, " h.shift=", h.shift, "\n")
			throw("bad shift after block copy")
		}
		// Handle the last byte if it's shared.
		if cnw == 2 {
			*h.bitp = *h.bitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | *src
			src = addb(src, 1)
			h = h.next().next()
		}
		if doubleCheck {
			if uintptr(unsafe.Pointer(src)) > x+size {
				throw("copy exceeded object size")
			}
			if !(cnw == 0 || cnw == 2) {
				print("x=", x, " size=", size, " cnw=", cnw, "\n")
				throw("bad number of remaining words")
			}
			// Set up hbitp so doubleCheck code below can check it.
			hbitp = h.bitp
		}
		// Zero the object where we wrote the bitmap.
		memclrNoHeapPointers(unsafe.Pointer(x), uintptr(unsafe.Pointer(src))-x)
	}

	// Double check the whole bitmap.
	if doubleCheck {
		// x+size may not point to the heap, so back up one
		// word and then advance it the way we do above.
		end := heapBitsForAddr(x + size - goarch.PtrSize)
		if outOfPlace {
			// In out-of-place copying, we just advance
			// using next.
			end = end.next()
		} else {
			// Don't use next because that may advance to
			// the next arena and the in-place logic
			// doesn't do that.
			end.shift += heapBitsShift
			if end.shift == 4*heapBitsShift {
				end.bitp, end.shift = add1(end.bitp), 0
			}
		}
		if typ.kind&kindGCProg == 0 && (hbitp != end.bitp || (w == nw+2) != (end.shift == 2)) {
			println("ended at wrong bitmap byte for", typ.string(), "x", dataSize/typ.size)
			print("typ.size=", typ.size, " typ.ptrdata=", typ.ptrdata, " dataSize=", dataSize, " size=", size, "\n")
			print("w=", w, " nw=", nw, " b=", hex(b), " nb=", nb, " hb=", hex(hb), "\n")
			h0 := heapBitsForAddr(x)
			print("initial bits h0.bitp=", h0.bitp, " h0.shift=", h0.shift, "\n")
			print("ended at hbitp=", hbitp, " but next starts at bitp=", end.bitp, " shift=", end.shift, "\n")
			throw("bad heapBitsSetType")
		}

		// Double-check that bits to be written were written correctly.
		// Does not check that other bits were not written, unfortunately.
		h := heapBitsForAddr(x)
		nptr := typ.ptrdata / goarch.PtrSize
		ndata := typ.size / goarch.PtrSize
		count := dataSize / typ.size
		totalptr := ((count-1)*typ.size + typ.ptrdata) / goarch.PtrSize
		for i := uintptr(0); i < size/goarch.PtrSize; i++ {
			j := i % ndata
			var have, want uint8
			have = (*h.bitp >> h.shift) & (bitPointer | bitScan)
			if i >= totalptr {
				if typ.kind&kindGCProg != 0 && i < (totalptr+3)/4*4 {
					// heapBitsSetTypeGCProg always fills
					// in full nibbles of bitScan.
					want = bitScan
				}
			} else {
				if j < nptr && (*addb(ptrmask, j/8)>>(j%8))&1 != 0 {
					want |= bitPointer
				}
				want |= bitScan
			}
			if have != want {
				println("mismatch writing bits for", typ.string(), "x", dataSize/typ.size)
				print("typ.size=", typ.size, " typ.ptrdata=", typ.ptrdata, " dataSize=", dataSize, " size=", size, "\n")
				print("kindGCProg=", typ.kind&kindGCProg != 0, " outOfPlace=", outOfPlace, "\n")
				print("w=", w, " nw=", nw, " b=", hex(b), " nb=", nb, " hb=", hex(hb), "\n")
				h0 := heapBitsForAddr(x)
				print("initial bits h0.bitp=", h0.bitp, " h0.shift=", h0.shift, "\n")
				print("current bits h.bitp=", h.bitp, " h.shift=", h.shift, " *h.bitp=", hex(*h.bitp), "\n")
				print("ptrmask=", ptrmask, " p=", p, " endp=", endp, " endnb=", endnb, " pbits=", hex(pbits), " b=", hex(b), " nb=", nb, "\n")
				println("at word", i, "offset", i*goarch.PtrSize, "have", hex(have), "want", hex(want))
				if typ.kind&kindGCProg != 0 {
					println("GC program:")
					dumpGCProg(addb(typ.gcdata, 4))
				}
				throw("bad heapBitsSetType")
			}
			h = h.next()
		}
		if ptrmask == debugPtrmask.data {
			unlock(&debugPtrmask.lock)
		}
	}
}

var debugPtrmask struct {
	lock mutex
	data *byte
}

// heapBitsSetTypeGCProg implements heapBitsSetType using a GC program.
// progSize is the size of the memory described by the program.
// elemSize is the size of the element that the GC program describes (a prefix of).
// dataSize is the total size of the intended data, a multiple of elemSize.
// allocSize is the total size of the allocated memory.
//
// GC programs are only used for large allocations.
// heapBitsSetType requires that allocSize is a multiple of 4 words,
// so that the relevant bitmap bytes are not shared with surrounding
// objects.
func heapBitsSetTypeGCProg(h heapBits, progSize, elemSize, dataSize, allocSize uintptr, prog *byte) {
	if goarch.PtrSize == 8 && allocSize%(4*goarch.PtrSize) != 0 {
		// Alignment will be wrong.
		throw("heapBitsSetTypeGCProg: small allocation")
	}
	var totalBits uintptr
	if elemSize == dataSize {
		totalBits = runGCProg(prog, nil, h.bitp, 2)
		if totalBits*goarch.PtrSize != progSize {
			println("runtime: heapBitsSetTypeGCProg: total bits", totalBits, "but progSize", progSize)
			throw("heapBitsSetTypeGCProg: unexpected bit count")
		}
	} else {
		count := dataSize / elemSize

		// Piece together program trailer to run after prog that does:
		//	literal(0)
		//	repeat(1, elemSize-progSize-1) // zeros to fill element size
		//	repeat(elemSize, count-1) // repeat that element for count
		// This zero-pads the data remaining in the first element and then
		// repeats that first element to fill the array.
		var trailer [40]byte // 3 varints (max 10 each) + some bytes
		i := 0
		if n := elemSize/goarch.PtrSize - progSize/goarch.PtrSize; n > 0 {
			// literal(0)
			trailer[i] = 0x01
			i++
			trailer[i] = 0
			i++
			if n > 1 {
				// repeat(1, n-1)
				trailer[i] = 0x81
				i++
				n--
				for ; n >= 0x80; n >>= 7 {
					trailer[i] = byte(n | 0x80)
					i++
				}
				trailer[i] = byte(n)
				i++
			}
		}
		// repeat(elemSize/ptrSize, count-1)
		trailer[i] = 0x80
		i++
		n := elemSize / goarch.PtrSize
		for ; n >= 0x80; n >>= 7 {
			trailer[i] = byte(n | 0x80)
			i++
		}
		trailer[i] = byte(n)
		i++
		n = count - 1
		for ; n >= 0x80; n >>= 7 {
			trailer[i] = byte(n | 0x80)
			i++
		}
		trailer[i] = byte(n)
		i++
		trailer[i] = 0
		i++

		runGCProg(prog, &trailer[0], h.bitp, 2)

		// Even though we filled in the full array just now,
		// record that we only filled in up to the ptrdata of the
		// last element. This will cause the code below to
		// memclr the dead section of the final array element,
		// so that scanobject can stop early in the final element.
		totalBits = (elemSize*(count-1) + progSize) / goarch.PtrSize
	}
	endProg := unsafe.Pointer(addb(h.bitp, (totalBits+3)/4))
	endAlloc := unsafe.Pointer(addb(h.bitp, allocSize/goarch.PtrSize/wordsPerBitmapByte))
	memclrNoHeapPointers(endProg, uintptr(endAlloc)-uintptr(endProg))
}

// progToPointerMask returns the 1-bit pointer mask output by the GC program prog.
// size the size of the region described by prog, in bytes.
// The resulting bitvector will have no more than size/goarch.PtrSize bits.
func progToPointerMask(prog *byte, size uintptr) bitvector {
	n := (size/goarch.PtrSize + 7) / 8
	x := (*[1 << 30]byte)(persistentalloc(n+1, 1, &memstats.buckhash_sys))[:n+1]
	x[len(x)-1] = 0xa1 // overflow check sentinel
	n = runGCProg(prog, nil, &x[0], 1)
	if x[len(x)-1] != 0xa1 {
		throw("progToPointerMask: overflow")
	}
	return bitvector{int32(n), &x[0]}
}

// Packed GC pointer bitmaps, aka GC programs.
//
// For large types containing arrays, the type information has a
// natural repetition that can be encoded to save space in the
// binary and in the memory representation of the type information.
//
// The encoding is a simple Lempel-Ziv style bytecode machine
// with the following instructions:
//
//	00000000: stop
//	0nnnnnnn: emit n bits copied from the next (n+7)/8 bytes
//	10000000 n c: repeat the previous n bits c times; n, c are varints
//	1nnnnnnn c: repeat the previous n bits c times; c is a varint

// runGCProg executes the GC program prog, and then trailer if non-nil,
// writing to dst with entries of the given size.
// If size == 1, dst is a 1-bit pointer mask laid out moving forward from dst.
// If size == 2, dst is the 2-bit heap bitmap, and writes move backward
// starting at dst (because the heap bitmap does). In this case, the caller guarantees
// that only whole bytes in dst need to be written.
//
// runGCProg returns the number of 1- or 2-bit entries written to memory.
func runGCProg(prog, trailer, dst *byte, size int) uintptr {
	dstStart := dst

	// Bits waiting to be written to memory.
	var bits uintptr
	var nbits uintptr

	p := prog
Run:
	for {
		// Flush accumulated full bytes.
		// The rest of the loop assumes that nbits <= 7.
		for ; nbits >= 8; nbits -= 8 {
			if size == 1 {
				*dst = uint8(bits)
				dst = add1(dst)
				bits >>= 8
			} else {
				v := bits&bitPointerAll | bitScanAll
				*dst = uint8(v)
				dst = add1(dst)
				bits >>= 4
				v = bits&bitPointerAll | bitScanAll
				*dst = uint8(v)
				dst = add1(dst)
				bits >>= 4
			}
		}

		// Process one instruction.
		inst := uintptr(*p)
		p = add1(p)
		n := inst & 0x7F
		if inst&0x80 == 0 {
			// Literal bits; n == 0 means end of program.
			if n == 0 {
				// Program is over; continue in trailer if present.
				if trailer != nil {
					p = trailer
					trailer = nil
					continue
				}
				break Run
			}
			nbyte := n / 8
			for i := uintptr(0); i < nbyte; i++ {
				bits |= uintptr(*p) << nbits
				p = add1(p)
				if size == 1 {
					*dst = uint8(bits)
					dst = add1(dst)
					bits >>= 8
				} else {
					v := bits&0xf | bitScanAll
					*dst = uint8(v)
					dst = add1(dst)
					bits >>= 4
					v = bits&0xf | bitScanAll
					*dst = uint8(v)
					dst = add1(dst)
					bits >>= 4
				}
			}
			if n %= 8; n > 0 {
				bits |= uintptr(*p) << nbits
				p = add1(p)
				nbits += n
			}
			continue Run
		}

		// Repeat. If n == 0, it is encoded in a varint in the next bytes.
		if n == 0 {
			for off := uint(0); ; off += 7 {
				x := uintptr(*p)
				p = add1(p)
				n |= (x & 0x7F) << off
				if x&0x80 == 0 {
					break
				}
			}
		}

		// Count is encoded in a varint in the next bytes.
		c := uintptr(0)
		for off := uint(0); ; off += 7 {
			x := uintptr(*p)
			p = add1(p)
			c |= (x & 0x7F) << off
			if x&0x80 == 0 {
				break
			}
		}
		c *= n // now total number of bits to copy

		// If the number of bits being repeated is small, load them
		// into a register and use that register for the entire loop
		// instead of repeatedly reading from memory.
		// Handling fewer than 8 bits here makes the general loop simpler.
		// The cutoff is goarch.PtrSize*8 - 7 to guarantee that when we add
		// the pattern to a bit buffer holding at most 7 bits (a partial byte)
		// it will not overflow.
		src := dst
		const maxBits = goarch.PtrSize*8 - 7
		if n <= maxBits {
			// Start with bits in output buffer.
			pattern := bits
			npattern := nbits

			// If we need more bits, fetch them from memory.
			if size == 1 {
				src = subtract1(src)
				for npattern < n {
					pattern <<= 8
					pattern |= uintptr(*src)
					src = subtract1(src)
					npattern += 8
				}
			} else {
				src = subtract1(src)
				for npattern < n {
					pattern <<= 4
					pattern |= uintptr(*src) & 0xf
					src = subtract1(src)
					npattern += 4
				}
			}

			// We started with the whole bit output buffer,
			// and then we loaded bits from whole bytes.
			// Either way, we might now have too many instead of too few.
			// Discard the extra.
			if npattern > n {
				pattern >>= npattern - n
				npattern = n
			}

			// Replicate pattern to at most maxBits.
			if npattern == 1 {
				// One bit being repeated.
				// If the bit is 1, make the pattern all 1s.
				// If the bit is 0, the pattern is already all 0s,
				// but we can claim that the number of bits
				// in the word is equal to the number we need (c),
				// because right shift of bits will zero fill.
				if pattern == 1 {
					pattern = 1<<maxBits - 1
					npattern = maxBits
				} else {
					npattern = c
				}
			} else {
				b := pattern
				nb := npattern
				if nb+nb <= maxBits {
					// Double pattern until the whole uintptr is filled.
					for nb <= goarch.PtrSize*8 {
						b |= b << nb
						nb += nb
					}
					// Trim away incomplete copy of original pattern in high bits.
					// TODO(rsc): Replace with table lookup or loop on systems without divide?
					nb = maxBits / npattern * npattern
					b &= 1<<nb - 1
					pattern = b
					npattern = nb
				}
			}

			// Add pattern to bit buffer and flush bit buffer, c/npattern times.
			// Since pattern contains >8 bits, there will be full bytes to flush
			// on each iteration.
			for ; c >= npattern; c -= npattern {
				bits |= pattern << nbits
				nbits += npattern
				if size == 1 {
					for nbits >= 8 {
						*dst = uint8(bits)
						dst = add1(dst)
						bits >>= 8
						nbits -= 8
					}
				} else {
					for nbits >= 4 {
						*dst = uint8(bits&0xf | bitScanAll)
						dst = add1(dst)
						bits >>= 4
						nbits -= 4
					}
				}
			}

			// Add final fragment to bit buffer.
			if c > 0 {
				pattern &= 1<<c - 1
				bits |= pattern << nbits
				nbits += c
			}
			continue Run
		}

		// Repeat; n too large to fit in a register.
		// Since nbits <= 7, we know the first few bytes of repeated data
		// are already written to memory.
		off := n - nbits // n > nbits because n > maxBits and nbits <= 7
		if size == 1 {
			// Leading src fragment.
			src = subtractb(src, (off+7)/8)
			if frag := off & 7; frag != 0 {
				bits |= uintptr(*src) >> (8 - frag) << nbits
				src = add1(src)
				nbits += frag
				c -= frag
			}
			// Main loop: load one byte, write another.
			// The bits are rotating through the bit buffer.
			for i := c / 8; i > 0; i-- {
				bits |= uintptr(*src) << nbits
				src = add1(src)
				*dst = uint8(bits)
				dst = add1(dst)
				bits >>= 8
			}
			// Final src fragment.
			if c %= 8; c > 0 {
				bits |= (uintptr(*src) & (1<<c - 1)) << nbits
				nbits += c
			}
		} else {
			// Leading src fragment.
			src = subtractb(src, (off+3)/4)
			if frag := off & 3; frag != 0 {
				bits |= (uintptr(*src) & 0xf) >> (4 - frag) << nbits
				src = add1(src)
				nbits += frag
				c -= frag
			}
			// Main loop: load one byte, write another.
			// The bits are rotating through the bit buffer.
			for i := c / 4; i > 0; i-- {
				bits |= (uintptr(*src) & 0xf) << nbits
				src = add1(src)
				*dst = uint8(bits&0xf | bitScanAll)
				dst = add1(dst)
				bits >>= 4
			}
			// Final src fragment.
			if c %= 4; c > 0 {
				bits |= (uintptr(*src) & (1<<c - 1)) << nbits
				nbits += c
			}
		}
	}

	// Write any final bits out, using full-byte writes, even for the final byte.
	var totalBits uintptr
	if size == 1 {
		totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*8 + nbits
		nbits += -nbits & 7
		for ; nbits > 0; nbits -= 8 {
			*dst = uint8(bits)
			dst = add1(dst)
			bits >>= 8
		}
	} else {
		totalBits = (uintptr(unsafe.Pointer(dst))-uintptr(unsafe.Pointer(dstStart)))*4 + nbits
		nbits += -nbits & 3
		for ; nbits > 0; nbits -= 4 {
			v := bits&0xf | bitScanAll
			*dst = uint8(v)
			dst = add1(dst)
			bits >>= 4
		}
	}
	return totalBits
}

// materializeGCProg allocates space for the (1-bit) pointer bitmask
// for an object of size ptrdata.  Then it fills that space with the
// pointer bitmask specified by the program prog.
// The bitmask starts at s.startAddr.
// The result must be deallocated with dematerializeGCProg.
func materializeGCProg(ptrdata uintptr, prog *byte) *mspan {
	// Each word of ptrdata needs one bit in the bitmap.
	bitmapBytes := divRoundUp(ptrdata, 8*goarch.PtrSize)
	// Compute the number of pages needed for bitmapBytes.
	pages := divRoundUp(bitmapBytes, pageSize)
	s := mheap_.allocManual(pages, spanAllocPtrScalarBits)
	runGCProg(addb(prog, 4), nil, (*byte)(unsafe.Pointer(s.startAddr)), 1)
	return s
}
func dematerializeGCProg(s *mspan) {
	mheap_.freeManual(s, spanAllocPtrScalarBits)
}

func dumpGCProg(p *byte) {
	nptr := 0
	for {
		x := *p
		p = add1(p)
		if x == 0 {
			print("\t", nptr, " end\n")
			break
		}
		if x&0x80 == 0 {
			print("\t", nptr, " lit ", x, ":")
			n := int(x+7) / 8
			for i := 0; i < n; i++ {
				print(" ", hex(*p))
				p = add1(p)
			}
			print("\n")
			nptr += int(x)
		} else {
			nbit := int(x &^ 0x80)
			if nbit == 0 {
				for nb := uint(0); ; nb += 7 {
					x := *p
					p = add1(p)
					nbit |= int(x&0x7f) << nb
					if x&0x80 == 0 {
						break
					}
				}
			}
			count := 0
			for nb := uint(0); ; nb += 7 {
				x := *p
				p = add1(p)
				count |= int(x&0x7f) << nb
				if x&0x80 == 0 {
					break
				}
			}
			print("\t", nptr, " repeat ", nbit, " × ", count, "\n")
			nptr += nbit * count
		}
	}
}

// Testing.

func getgcmaskcb(frame *stkframe, ctxt unsafe.Pointer) bool {
	target := (*stkframe)(ctxt)
	if frame.sp <= target.sp && target.sp < frame.varp {
		*target = *frame
		return false
	}
	return true
}

// gcbits returns the GC type info for x, for testing.
// The result is the bitmap entries (0 or 1), one entry per byte.
//go:linkname reflect_gcbits reflect.gcbits
func reflect_gcbits(x any) []byte {
	ret := getgcmask(x)
	typ := (*ptrtype)(unsafe.Pointer(efaceOf(&x)._type)).elem
	nptr := typ.ptrdata / goarch.PtrSize
	for uintptr(len(ret)) > nptr && ret[len(ret)-1] == 0 {
		ret = ret[:len(ret)-1]
	}
	return ret
}

// Returns GC type info for the pointer stored in ep for testing.
// If ep points to the stack, only static live information will be returned
// (i.e. not for objects which are only dynamically live stack objects).
func getgcmask(ep any) (mask []byte) {
	e := *efaceOf(&ep)
	p := e.data
	t := e._type
	// data or bss
	for _, datap := range activeModules() {
		// data
		if datap.data <= uintptr(p) && uintptr(p) < datap.edata {
			bitmap := datap.gcdatamask.bytedata
			n := (*ptrtype)(unsafe.Pointer(t)).elem.size
			mask = make([]byte, n/goarch.PtrSize)
			for i := uintptr(0); i < n; i += goarch.PtrSize {
				off := (uintptr(p) + i - datap.data) / goarch.PtrSize
				mask[i/goarch.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
			}
			return
		}

		// bss
		if datap.bss <= uintptr(p) && uintptr(p) < datap.ebss {
			bitmap := datap.gcbssmask.bytedata
			n := (*ptrtype)(unsafe.Pointer(t)).elem.size
			mask = make([]byte, n/goarch.PtrSize)
			for i := uintptr(0); i < n; i += goarch.PtrSize {
				off := (uintptr(p) + i - datap.bss) / goarch.PtrSize
				mask[i/goarch.PtrSize] = (*addb(bitmap, off/8) >> (off % 8)) & 1
			}
			return
		}
	}

	// heap
	if base, s, _ := findObject(uintptr(p), 0, 0); base != 0 {
		hbits := heapBitsForAddr(base)
		n := s.elemsize
		mask = make([]byte, n/goarch.PtrSize)
		for i := uintptr(0); i < n; i += goarch.PtrSize {
			if hbits.isPointer() {
				mask[i/goarch.PtrSize] = 1
			}
			if !hbits.morePointers() {
				mask = mask[:i/goarch.PtrSize]
				break
			}
			hbits = hbits.next()
		}
		return
	}

	// stack
	if _g_ := getg(); _g_.m.curg.stack.lo <= uintptr(p) && uintptr(p) < _g_.m.curg.stack.hi {
		var frame stkframe
		frame.sp = uintptr(p)
		_g_ := getg()
		gentraceback(_g_.m.curg.sched.pc, _g_.m.curg.sched.sp, 0, _g_.m.curg, 0, nil, 1000, getgcmaskcb, noescape(unsafe.Pointer(&frame)), 0)
		if frame.fn.valid() {
			locals, _, _ := getStackMap(&frame, nil, false)
			if locals.n == 0 {
				return
			}
			size := uintptr(locals.n) * goarch.PtrSize
			n := (*ptrtype)(unsafe.Pointer(t)).elem.size
			mask = make([]byte, n/goarch.PtrSize)
			for i := uintptr(0); i < n; i += goarch.PtrSize {
				off := (uintptr(p) + i - frame.varp + size) / goarch.PtrSize
				mask[i/goarch.PtrSize] = locals.ptrbit(off)
			}
		}
		return
	}

	// otherwise, not something the GC knows about.
	// possibly read-only data, like malloc(0).
	// must not have pointers
	return
}