Gecko [ 167.86.127.34 ]

Name	Size	Permission
cgo	[ DIR ]	drwxr-xr-x
debug	[ DIR ]	drwxr-xr-x
internal	[ DIR ]	drwxr-xr-x
msan	[ DIR ]	drwxr-xr-x
pprof	[ DIR ]	drwxr-xr-x
race	[ DIR ]	drwxr-xr-x
testdata	[ DIR ]	drwxr-xr-x
trace	[ DIR ]	drwxr-xr-x
HACKING.md	13.07 KB	-rw-r--r--
Makefile	178 B	-rw-r--r--
alg.go	10.18 KB	-rw-r--r--
asm.s	1.16 KB	-rw-r--r--
asm_386.s	40.2 KB	-rw-r--r--
asm_amd64.s	45.78 KB	-rw-r--r--
asm_arm.s	30.89 KB	-rw-r--r--
asm_arm64.s	33.12 KB	-rw-r--r--
asm_mips64x.s	22.45 KB	-rw-r--r--
asm_mipsx.s	24.72 KB	-rw-r--r--
asm_ppc64x.h	1023 B	-rw-r--r--
asm_ppc64x.s	29.39 KB	-rw-r--r--
asm_riscv64.s	17.38 KB	-rw-r--r--
asm_s390x.s	26.35 KB	-rw-r--r--
asm_wasm.s	9.65 KB	-rw-r--r--
atomic_arm64.s	259 B	-rw-r--r--
atomic_mips64x.s	296 B	-rw-r--r--
atomic_mipsx.s	258 B	-rw-r--r--
atomic_pointer.go	2.62 KB	-rw-r--r--
atomic_ppc64x.s	433 B	-rw-r--r--
atomic_riscv64.s	307 B	-rw-r--r--
auxv_none.go	358 B	-rw-r--r--
callers_test.go	7.7 KB	-rw-r--r--
cgo.go	2.01 KB	-rw-r--r--
cgo_mmap.go	2.38 KB	-rw-r--r--
cgo_ppc64x.go	411 B	-rw-r--r--
cgo_sigaction.go	3.09 KB	-rw-r--r--
cgocall.go	21.38 KB	-rw-r--r--
cgocallback.go	317 B	-rw-r--r--
cgocheck.go	6.8 KB	-rw-r--r--
chan.go	19.71 KB	-rw-r--r--
chan_test.go	21.27 KB	-rw-r--r--
chanbarrier_test.go	1.4 KB	-rw-r--r--
checkptr.go	2.5 KB	-rw-r--r--
checkptr_test.go	1.27 KB	-rw-r--r--
closure_test.go	936 B	-rw-r--r--
compiler.go	413 B	-rw-r--r--
complex.go	1.59 KB	-rw-r--r--
complex_test.go	1.05 KB	-rw-r--r--
cpuflags.go	740 B	-rw-r--r--
cpuflags_amd64.go	533 B	-rw-r--r--
cpuprof.go	6.65 KB	-rw-r--r--
cputicks.go	478 B	-rw-r--r--
crash_cgo_test.go	13.71 KB	-rw-r--r--
crash_nonunix_test.go	385 B	-rw-r--r--
crash_test.go	20.24 KB	-rw-r--r--
crash_unix_test.go	8.89 KB	-rw-r--r--
debug.go	1.63 KB	-rw-r--r--
debug_test.go	6.16 KB	-rw-r--r--
debugcall.go	2.83 KB	-rw-r--r--
debuglog.go	17.08 KB	-rw-r--r--
debuglog_off.go	356 B	-rw-r--r--
debuglog_on.go	1.09 KB	-rw-r--r--
debuglog_test.go	4.56 KB	-rw-r--r--
defer_test.go	9.98 KB	-rw-r--r--
defs1_linux.go	844 B	-rw-r--r--
defs1_netbsd_386.go	2.84 KB	-rw-r--r--
defs1_netbsd_amd64.go	3.07 KB	-rw-r--r--
defs1_netbsd_arm.go	2.96 KB	-rw-r--r--
defs1_netbsd_arm64.go	3.18 KB	-rw-r--r--
defs1_solaris_amd64.go	4.02 KB	-rw-r--r--
defs2_linux.go	3.51 KB	-rw-r--r--
defs3_linux.go	1.09 KB	-rw-r--r--
defs_aix.go	4.16 KB	-rw-r--r--
defs_aix_ppc64.go	3.61 KB	-rw-r--r--
defs_arm_linux.go	2.67 KB	-rw-r--r--
defs_darwin.go	3.84 KB	-rw-r--r--
defs_darwin_386.go	5.98 KB	-rw-r--r--
defs_darwin_amd64.go	6.07 KB	-rw-r--r--
defs_darwin_arm.go	3.78 KB	-rw-r--r--
defs_darwin_arm64.go	3.84 KB	-rw-r--r--
defs_dragonfly.go	2.54 KB	-rw-r--r--
defs_dragonfly_amd64.go	3.25 KB	-rw-r--r--
defs_freebsd.go	3.84 KB	-rw-r--r--
defs_freebsd_386.go	4.35 KB	-rw-r--r--
defs_freebsd_amd64.go	4.62 KB	-rw-r--r--
defs_freebsd_arm.go	3.68 KB	-rw-r--r--
defs_freebsd_arm64.go	4 KB	-rw-r--r--
defs_illumos_amd64.go	285 B	-rw-r--r--
defs_linux.go	3.04 KB	-rw-r--r--
defs_linux_386.go	4.05 KB	-rw-r--r--
defs_linux_amd64.go	4.56 KB	-rw-r--r--
defs_linux_arm.go	3.31 KB	-rw-r--r--
defs_linux_arm64.go	3.23 KB	-rw-r--r--
defs_linux_mips64x.go	3.04 KB	-rw-r--r--
defs_linux_mipsx.go	3.18 KB	-rw-r--r--
defs_linux_ppc64.go	3.28 KB	-rw-r--r--
defs_linux_ppc64le.go	3.28 KB	-rw-r--r--
defs_linux_riscv64.go	3.27 KB	-rw-r--r--
defs_linux_s390x.go	2.76 KB	-rw-r--r--
defs_netbsd.go	2.74 KB	-rw-r--r--
defs_netbsd_386.go	854 B	-rw-r--r--
defs_netbsd_amd64.go	1.01 KB	-rw-r--r--
defs_netbsd_arm.go	763 B	-rw-r--r--
defs_openbsd.go	2.6 KB	-rw-r--r--
defs_openbsd_386.go	2.63 KB	-rw-r--r--
defs_openbsd_amd64.go	2.83 KB	-rw-r--r--
defs_openbsd_arm.go	2.74 KB	-rw-r--r--
defs_openbsd_arm64.go	2.34 KB	-rw-r--r--
defs_plan9_386.go	1.47 KB	-rw-r--r--
defs_plan9_amd64.go	1.66 KB	-rw-r--r--
defs_plan9_arm.go	1.73 KB	-rw-r--r--
defs_solaris.go	3.33 KB	-rw-r--r--
defs_solaris_amd64.go	1003 B	-rw-r--r--
defs_windows.go	2.07 KB	-rw-r--r--
defs_windows_386.go	3.75 KB	-rw-r--r--
defs_windows_amd64.go	4.51 KB	-rw-r--r--
defs_windows_arm.go	3.59 KB	-rw-r--r--
duff_386.s	8.24 KB	-rw-r--r--
duff_amd64.s	5.53 KB	-rw-r--r--
duff_arm.s	7.11 KB	-rw-r--r--
duff_arm64.s	5.25 KB	-rw-r--r--
duff_mips64x.s	11.28 KB	-rw-r--r--
duff_ppc64x.s	2.45 KB	-rw-r--r--
duff_s390x.s	507 B	-rw-r--r--
env_plan9.go	855 B	-rw-r--r--
env_posix.go	1.82 KB	-rw-r--r--
env_test.go	1.28 KB	-rw-r--r--
error.go	7.26 KB	-rw-r--r--
example_test.go	1.34 KB	-rw-r--r--
export_aix_test.go	204 B	-rw-r--r--
export_arm_test.go	226 B	-rw-r--r--
export_darwin_test.go	351 B	-rw-r--r--
export_debug_test.go	5.28 KB	-rw-r--r--
export_debuglog_test.go	1.27 KB	-rw-r--r--
export_futex_test.go	529 B	-rw-r--r--
export_linux_test.go	429 B	-rw-r--r--
export_mmap_test.go	481 B	-rw-r--r--
export_solaris_test.go	282 B	-rw-r--r--
export_test.go	23.58 KB	-rw-r--r--
export_unix_test.go	2.28 KB	-rw-r--r--
export_windows_test.go	652 B	-rw-r--r--
extern.go	11.6 KB	-rw-r--r--
fastlog2.go	1.22 KB	-rw-r--r--
fastlog2_test.go	784 B	-rw-r--r--
fastlog2table.go	904 B	-rw-r--r--
float.go	1.35 KB	-rw-r--r--
funcdata.h	2.44 KB	-rw-r--r--
futex_test.go	2.1 KB	-rw-r--r--
gc_test.go	13.22 KB	-rw-r--r--
gcinfo_test.go	6.18 KB	-rw-r--r--
go_tls.h	366 B	-rw-r--r--
hash32.go	2.51 KB	-rw-r--r--
hash64.go	2.6 KB	-rw-r--r--
hash_test.go	17.54 KB	-rw-r--r--
heapdump.go	17.1 KB	-rw-r--r--
iface.go	15.78 KB	-rw-r--r--
iface_test.go	6.81 KB	-rw-r--r--
lfstack.go	1.77 KB	-rw-r--r--
lfstack_32bit.go	522 B	-rw-r--r--
lfstack_64bit.go	2.15 KB	-rw-r--r--
lfstack_test.go	2.78 KB	-rw-r--r--
libfuzzer.go	2.58 KB	-rw-r--r--
libfuzzer_amd64.s	940 B	-rw-r--r--
libfuzzer_arm64.s	751 B	-rw-r--r--
lock_futex.go	5.06 KB	-rw-r--r--
lock_js.go	5.45 KB	-rw-r--r--
lock_sema.go	6.6 KB	-rw-r--r--
malloc.go	48.32 KB	-rw-r--r--
malloc_test.go	9.37 KB	-rw-r--r--
map.go	42.13 KB	-rw-r--r--
map_benchmark_test.go	10.16 KB	-rw-r--r--
map_fast32.go	12.18 KB	-rw-r--r--
map_fast64.go	12.37 KB	-rw-r--r--
map_faststr.go	13.82 KB	-rw-r--r--
map_test.go	27.11 KB	-rw-r--r--
mbarrier.go	12.14 KB	-rw-r--r--
mbitmap.go	67.53 KB	-rw-r--r--
mcache.go	5.61 KB	-rw-r--r--
mcentral.go	7.14 KB	-rw-r--r--
mem_aix.go	1.93 KB	-rw-r--r--
mem_bsd.go	2.05 KB	-rw-r--r--
mem_darwin.go	1.88 KB	-rw-r--r--
mem_js.go	2.32 KB	-rw-r--r--
mem_linux.go	5.58 KB	-rw-r--r--
mem_plan9.go	4.53 KB	-rw-r--r--
mem_windows.go	3.86 KB	-rw-r--r--
memclr_386.s	2.4 KB	-rw-r--r--
memclr_amd64.s	3.65 KB	-rw-r--r--
memclr_arm.s	2.44 KB	-rw-r--r--
memclr_arm64.s	3.48 KB	-rw-r--r--
memclr_mips64x.s	785 B	-rw-r--r--
memclr_mipsx.s	1.24 KB	-rw-r--r--
memclr_plan9_386.s	905 B	-rw-r--r--
memclr_plan9_amd64.s	433 B	-rw-r--r--
memclr_ppc64x.s	4.2 KB	-rw-r--r--
memclr_riscv64.s	848 B	-rwxr-xr-x
memclr_s390x.s	1.89 KB	-rw-r--r--
memclr_wasm.s	544 B	-rw-r--r--
memmove_386.s	4.45 KB	-rw-r--r--
memmove_amd64.s	12.33 KB	-rw-r--r--
memmove_arm.s	5.9 KB	-rw-r--r--
memmove_arm64.s	3.56 KB	-rw-r--r--
memmove_linux_amd64_test.go	1.61 KB	-rw-r--r--
memmove_mips64x.s	1.82 KB	-rw-r--r--
memmove_mipsx.s	4.39 KB	-rw-r--r--
memmove_plan9_386.s	3.06 KB	-rw-r--r--
memmove_plan9_amd64.s	3.04 KB	-rw-r--r--
memmove_ppc64x.s	3.33 KB	-rw-r--r--
memmove_riscv64.s	1.81 KB	-rwxr-xr-x
memmove_s390x.s	2.92 KB	-rw-r--r--
memmove_test.go	10.97 KB	-rw-r--r--
memmove_wasm.s	1.74 KB	-rw-r--r--
mfinal.go	14.8 KB	-rw-r--r--
mfinal_test.go	5.85 KB	-rw-r--r--
mfixalloc.go	2.72 KB	-rw-r--r--
mgc.go	74.87 KB	-rw-r--r--
mgcmark.go	46.5 KB	-rw-r--r--
mgcscavenge.go	30.95 KB	-rw-r--r--
mgcscavenge_test.go	12.34 KB	-rw-r--r--
mgcstack.go	10.55 KB	-rw-r--r--
mgcsweep.go	14.79 KB	-rw-r--r--
mgcsweepbuf.go	5.98 KB	-rw-r--r--
mgcwork.go	14.24 KB	-rw-r--r--
mheap.go	61.5 KB	-rw-r--r--
mkduff.go	6.23 KB	-rw-r--r--
mkfastlog2table.go	1.32 KB	-rw-r--r--
mkpreempt.go	13.33 KB	-rw-r--r--
mksizeclasses.go	8.62 KB	-rw-r--r--
mmap.go	847 B	-rw-r--r--
mpagealloc.go	35.25 KB	-rw-r--r--
mpagealloc_32bit.go	3.75 KB	-rw-r--r--
mpagealloc_64bit.go	6.51 KB	-rw-r--r--
mpagealloc_test.go	28.88 KB	-rw-r--r--
mpagecache.go	5.03 KB	-rw-r--r--
mpagecache_test.go	9.93 KB	-rw-r--r--
mpallocbits.go	10.69 KB	-rw-r--r--
mpallocbits_test.go	12.93 KB	-rw-r--r--
mprof.go	24.06 KB	-rw-r--r--
mranges.go	5.41 KB	-rw-r--r--
msan.go	1.39 KB	-rw-r--r--
msan0.go	647 B	-rw-r--r--
msan_amd64.s	2.03 KB	-rw-r--r--
msan_arm64.s	1.69 KB	-rw-r--r--
msize.go	785 B	-rw-r--r--
mstats.go	22.62 KB	-rw-r--r--
mwbbuf.go	10.07 KB	-rw-r--r--
nbpipe_fcntl_libc_test.go	463 B	-rw-r--r--
nbpipe_fcntl_unix_test.go	445 B	-rw-r--r--
nbpipe_pipe.go	411 B	-rw-r--r--
nbpipe_pipe2.go	509 B	-rw-r--r--
nbpipe_test.go	2.17 KB	-rw-r--r--
net_plan9.go	645 B	-rw-r--r--
netpoll.go	14.46 KB	-rw-r--r--
netpoll_aix.go	4.64 KB	-rw-r--r--
netpoll_epoll.go	4 KB	-rw-r--r--
netpoll_fake.go	648 B	-rw-r--r--
netpoll_kqueue.go	4.39 KB	-rw-r--r--
netpoll_solaris.go	10.56 KB	-rw-r--r--
netpoll_stub.go	1.3 KB	-rw-r--r--
netpoll_windows.go	4.51 KB	-rw-r--r--
norace_linux_test.go	888 B	-rw-r--r--
norace_test.go	979 B	-rw-r--r--
numcpu_freebsd_test.go	381 B	-rw-r--r--
os2_aix.go	20.67 KB	-rw-r--r--
os2_freebsd.go	302 B	-rw-r--r--
os2_openbsd.go	296 B	-rw-r--r--
os2_plan9.go	1.48 KB	-rw-r--r--
os2_solaris.go	320 B	-rw-r--r--
os3_plan9.go	3.99 KB	-rw-r--r--
os3_solaris.go	16.92 KB	-rw-r--r--
os_aix.go	8.29 KB	-rw-r--r--
os_android.go	463 B	-rw-r--r--
os_darwin.go	10.59 KB	-rw-r--r--
os_darwin_arm.go	749 B	-rw-r--r--
os_darwin_arm64.go	416 B	-rw-r--r--
os_dragonfly.go	6.2 KB	-rw-r--r--
os_freebsd.go	10.97 KB	-rw-r--r--
os_freebsd2.go	478 B	-rw-r--r--
os_freebsd_amd64.go	529 B	-rw-r--r--
os_freebsd_arm.go	1.32 KB	-rw-r--r--
os_freebsd_arm64.go	2.97 KB	-rw-r--r--
os_freebsd_noauxv.go	254 B	-rw-r--r--
os_illumos.go	3.93 KB	-rw-r--r--
os_js.go	2.93 KB	-rw-r--r--
os_linux.go	13.16 KB	-rw-r--r--
os_linux_arm.go	1.35 KB	-rw-r--r--
os_linux_arm64.go	1.02 KB	-rw-r--r--
os_linux_be64.go	816 B	-rw-r--r--
os_linux_generic.go	916 B	-rw-r--r--
os_linux_mips64x.go	999 B	-rw-r--r--
os_linux_mipsx.go	1.05 KB	-rw-r--r--
os_linux_noauxv.go	307 B	-rw-r--r--
os_linux_novdso.go	298 B	-rw-r--r--
os_linux_ppc64x.go	527 B	-rw-r--r--
os_linux_riscv64.go	198 B	-rw-r--r--
os_linux_s390x.go	455 B	-rw-r--r--
os_linux_x86.go	2.69 KB	-rw-r--r--
os_netbsd.go	8.49 KB	-rw-r--r--
os_netbsd_386.go	588 B	-rw-r--r--
os_netbsd_amd64.go	585 B	-rw-r--r--
os_netbsd_arm.go	1.13 KB	-rw-r--r--
os_netbsd_arm64.go	827 B	-rw-r--r--
os_nonopenbsd.go	436 B	-rw-r--r--
os_only_solaris.go	356 B	-rw-r--r--
os_openbsd.go	7.81 KB	-rw-r--r--
os_openbsd_arm.go	749 B	-rw-r--r--
os_openbsd_arm64.go	714 B	-rw-r--r--
os_plan9.go	9.3 KB	-rw-r--r--
os_plan9_arm.go	462 B	-rw-r--r--
os_solaris.go	6.49 KB	-rw-r--r--
os_windows.go	37.01 KB	-rw-r--r--
os_windows_arm.go	511 B	-rw-r--r--
panic.go	42.23 KB	-rw-r--r--
panic32.go	4.79 KB	-rw-r--r--
plugin.go	4.16 KB	-rw-r--r--
preempt.go	14.72 KB	-rw-r--r--
preempt_386.s	983 B	-rw-r--r--
preempt_amd64.s	1.62 KB	-rw-r--r--
preempt_arm.s	1.48 KB	-rw-r--r--
preempt_arm64.s	2.8 KB	-rw-r--r--
preempt_mips64x.s	2.71 KB	-rw-r--r--
preempt_mipsx.s	2.68 KB	-rw-r--r--
preempt_nonwindows.go	289 B	-rw-r--r--
preempt_ppc64x.s	2.71 KB	-rw-r--r--
preempt_riscv64.s	197 B	-rw-r--r--
preempt_s390x.s	1.01 KB	-rw-r--r--
preempt_wasm.s	176 B	-rw-r--r--
print.go	5.98 KB	-rw-r--r--
proc.go	149.75 KB	-rw-r--r--
proc_runtime_test.go	820 B	-rw-r--r--
proc_test.go	22.89 KB	-rw-r--r--
profbuf.go	18.26 KB	-rw-r--r--
profbuf_test.go	8.65 KB	-rw-r--r--
proflabel.go	1.52 KB	-rw-r--r--
race.go	18.11 KB	-rw-r--r--
race0.go	2.61 KB	-rw-r--r--
race_amd64.s	13.59 KB	-rw-r--r--
race_arm64.s	13.53 KB	-rw-r--r--
race_ppc64le.s	17.93 KB	-rw-r--r--
rand_test.go	783 B	-rw-r--r--
rdebug.go	553 B	-rw-r--r--
relax_stub.go	597 B	-rw-r--r--
rt0_aix_ppc64.s	4.33 KB	-rw-r--r--
rt0_android_386.s	822 B	-rw-r--r--
rt0_android_amd64.s	754 B	-rw-r--r--
rt0_android_arm.s	843 B	-rw-r--r--
rt0_android_arm64.s	941 B	-rw-r--r--
rt0_darwin_386.s	452 B	-rw-r--r--
rt0_darwin_amd64.s	399 B	-rw-r--r--
rt0_darwin_arm.s	290 B	-rw-r--r--
rt0_darwin_arm64.s	2.32 KB	-rw-r--r--
rt0_dragonfly_amd64.s	448 B	-rw-r--r--
rt0_freebsd_386.s	454 B	-rw-r--r--
rt0_freebsd_amd64.s	442 B	-rw-r--r--
rt0_freebsd_arm.s	298 B	-rw-r--r--
rt0_freebsd_arm64.s	2.46 KB	-rw-r--r--
rt0_illumos_amd64.s	311 B	-rw-r--r--
rt0_js_wasm.s	2.3 KB	-rw-r--r--
rt0_linux_386.s	450 B	-rw-r--r--
rt0_linux_amd64.s	307 B	-rw-r--r--
rt0_linux_arm.s	1007 B	-rw-r--r--
rt0_linux_arm64.s	2.39 KB	-rw-r--r--
rt0_linux_mips64x.s	1015 B	-rw-r--r--
rt0_linux_mipsx.s	798 B	-rw-r--r--
rt0_linux_ppc64.s	705 B	-rw-r--r--
rt0_linux_ppc64le.s	3.72 KB	-rw-r--r--
rt0_linux_riscv64.s	370 B	-rw-r--r--
rt0_linux_s390x.s	676 B	-rw-r--r--
rt0_netbsd_386.s	452 B	-rw-r--r--
rt0_netbsd_amd64.s	309 B	-rw-r--r--
rt0_netbsd_arm.s	296 B	-rw-r--r--
rt0_netbsd_arm64.s	2.39 KB	-rw-r--r--
rt0_openbsd_386.s	454 B	-rw-r--r--
rt0_openbsd_amd64.s	311 B	-rw-r--r--
rt0_openbsd_arm.s	298 B	-rw-r--r--
rt0_openbsd_arm64.s	2.42 KB	-rw-r--r--
rt0_plan9_386.s	523 B	-rw-r--r--
rt0_plan9_amd64.s	481 B	-rw-r--r--
rt0_plan9_arm.s	397 B	-rw-r--r--
rt0_solaris_amd64.s	311 B	-rw-r--r--
rt0_windows_386.s	1.28 KB	-rw-r--r--
rt0_windows_amd64.s	1.15 KB	-rw-r--r--
rt0_windows_arm.s	386 B	-rw-r--r--
runtime-gdb.py	14.83 KB	-rw-r--r--
runtime-gdb_test.go	16.85 KB	-rw-r--r--
runtime-lldb_test.go	5.09 KB	-rw-r--r--
runtime.go	1.42 KB	-rw-r--r--
runtime1.go	11.97 KB	-rw-r--r--
runtime2.go	37.85 KB	-rw-r--r--
runtime_linux_test.go	1.46 KB	-rw-r--r--
runtime_mmap_test.go	1.82 KB	-rw-r--r--
runtime_test.go	7.81 KB	-rw-r--r--
runtime_unix_test.go	1.2 KB	-rw-r--r--
rwmutex.go	3.4 KB	-rw-r--r--
rwmutex_test.go	4.03 KB	-rw-r--r--
select.go	13.24 KB	-rw-r--r--
sema.go	15.95 KB	-rw-r--r--
sema_test.go	2.41 KB	-rw-r--r--
semasleep_test.go	1.62 KB	-rw-r--r--
sigaction.go	460 B	-rw-r--r--
signal_386.go	2.14 KB	-rw-r--r--
signal_aix_ppc64.go	3.55 KB	-rw-r--r--
signal_amd64.go	2.56 KB	-rw-r--r--
signal_arm.go	2.63 KB	-rw-r--r--
signal_arm64.go	3.12 KB	-rw-r--r--
signal_darwin.go	2.13 KB	-rw-r--r--
signal_darwin_386.go	2.33 KB	-rw-r--r--
signal_darwin_amd64.go	3.85 KB	-rw-r--r--
signal_darwin_arm.go	2.71 KB	-rw-r--r--
signal_darwin_arm64.go	3.6 KB	-rw-r--r--
signal_dragonfly.go	2.17 KB	-rw-r--r--
signal_dragonfly_amd64.go	2.01 KB	-rw-r--r--
signal_freebsd.go	2.2 KB	-rw-r--r--
signal_freebsd_386.go	1.55 KB	-rw-r--r--
signal_freebsd_amd64.go	2.03 KB	-rw-r--r--
signal_freebsd_arm.go	2.18 KB	-rw-r--r--
signal_freebsd_arm64.go	3.23 KB	-rw-r--r--
signal_linux_386.go	1.59 KB	-rw-r--r--
signal_linux_amd64.go	2.05 KB	-rw-r--r--
signal_linux_arm.go	2.13 KB	-rw-r--r--
signal_linux_arm64.go	2.95 KB	-rw-r--r--
signal_linux_mips64x.go	3.35 KB	-rw-r--r--
signal_linux_mipsx.go	3.67 KB	-rw-r--r--
signal_linux_ppc64x.go	3.42 KB	-rw-r--r--
signal_linux_riscv64.go	2.92 KB	-rw-r--r--
signal_linux_s390x.go	4.45 KB	-rw-r--r--
signal_mips64x.go	3.16 KB	-rw-r--r--
signal_mipsx.go	3.05 KB	-rw-r--r--
signal_netbsd.go	2.18 KB	-rw-r--r--
signal_netbsd_386.go	1.76 KB	-rw-r--r--
signal_netbsd_amd64.go	2.33 KB	-rw-r--r--
signal_netbsd_arm.go	2.3 KB	-rw-r--r--
signal_netbsd_arm64.go	3.4 KB	-rw-r--r--
signal_openbsd.go	2.15 KB	-rw-r--r--
signal_openbsd_386.go	1.58 KB	-rw-r--r--
signal_openbsd_amd64.go	2.04 KB	-rw-r--r--
signal_openbsd_arm.go	2.12 KB	-rw-r--r--
signal_openbsd_arm64.go	3.38 KB	-rw-r--r--
signal_plan9.go	1.93 KB	-rw-r--r--
signal_ppc64x.go	3.61 KB	-rw-r--r--
signal_riscv64.go	2.45 KB	-rw-r--r--
signal_solaris.go	4.5 KB	-rw-r--r--
signal_solaris_amd64.go	2.47 KB	-rw-r--r--
signal_unix.go	35.95 KB	-rw-r--r--
signal_windows.go	8.54 KB	-rw-r--r--
signal_windows_test.go	1.6 KB	-rw-r--r--
sigqueue.go	7.69 KB	-rw-r--r--
sigqueue_note.go	654 B	-rw-r--r--
sigqueue_plan9.go	3.31 KB	-rw-r--r--
sigtab_aix.go	11.3 KB	-rw-r--r--
sigtab_linux_generic.go	3.49 KB	-rw-r--r--
sigtab_linux_mipsx.go	5.89 KB	-rw-r--r--
sizeclasses.go	7.9 KB	-rw-r--r--
sizeof_test.go	839 B	-rw-r--r--
slice.go	6.88 KB	-rw-r--r--
slice_test.go	8.78 KB	-rw-r--r--
softfloat64.go	10.7 KB	-rw-r--r--
softfloat64_test.go	4.05 KB	-rw-r--r--
stack.go	39.14 KB	-rw-r--r--
stack_test.go	19.9 KB	-rw-r--r--
string.go	11.52 KB	-rw-r--r--
string_test.go	10.35 KB	-rw-r--r--
stubs.go	13.08 KB	-rw-r--r--
stubs2.go	1.04 KB	-rw-r--r--
stubs3.go	289 B	-rw-r--r--
stubs32.go	393 B	-rw-r--r--
stubs_386.go	490 B	-rw-r--r--
stubs_amd64.go	348 B	-rw-r--r--
stubs_arm.go	454 B	-rw-r--r--
stubs_arm64.go	256 B	-rw-r--r--
stubs_linux.go	646 B	-rw-r--r--
stubs_mips64x.go	283 B	-rw-r--r--
stubs_mipsx.go	279 B	-rw-r--r--
stubs_nonlinux.go	297 B	-rw-r--r--
stubs_ppc64x.go	296 B	-rw-r--r--
stubs_s390x.go	256 B	-rw-r--r--
symtab.go	28.32 KB	-rw-r--r--
symtab_test.go	4.1 KB	-rw-r--r--
sys_aix_ppc64.s	7.17 KB	-rw-r--r--
sys_arm.go	521 B	-rw-r--r--
sys_arm64.go	469 B	-rw-r--r--
sys_darwin.go	15.96 KB	-rw-r--r--
sys_darwin_32.go	533 B	-rw-r--r--
sys_darwin_386.s	18.55 KB	-rw-r--r--
sys_darwin_64.go	513 B	-rw-r--r--
sys_darwin_amd64.s	18.07 KB	-rw-r--r--
sys_darwin_arm.s	13.7 KB	-rw-r--r--
sys_darwin_arm64.s	15.84 KB	-rw-r--r--
sys_dragonfly_amd64.s	8.32 KB	-rw-r--r--
sys_freebsd_386.s	8.92 KB	-rw-r--r--
sys_freebsd_amd64.s	10.72 KB	-rw-r--r--
sys_freebsd_arm.s	10.64 KB	-rw-r--r--
sys_freebsd_arm64.s	10.75 KB	-rw-r--r--
sys_linux_386.s	17.57 KB	-rw-r--r--
sys_linux_amd64.s	17.07 KB	-rw-r--r--
sys_linux_arm.s	14.9 KB	-rw-r--r--
sys_linux_arm64.s	14.32 KB	-rw-r--r--
sys_linux_mips64x.s	12 KB	-rw-r--r--
sys_linux_mipsx.s	11.13 KB	-rw-r--r--
sys_linux_ppc64x.s	14.71 KB	-rw-r--r--
sys_linux_riscv64.s	10.38 KB	-rw-r--r--

Code Editor : mpagealloc.go

// Copyright 2019 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Page allocator.
//
// The page allocator manages mapped pages (defined by pageSize, NOT
// physPageSize) for allocation and re-use. It is embedded into mheap.
//
// Pages are managed using a bitmap that is sharded into chunks.
// In the bitmap, 1 means in-use, and 0 means free. The bitmap spans the
// process's address space. Chunks are managed in a sparse-array-style structure
// similar to mheap.arenas, since the bitmap may be large on some systems.
//
// The bitmap is efficiently searched by using a radix tree in combination
// with fast bit-wise intrinsics. Allocation is performed using an address-ordered
// first-fit approach.
//
// Each entry in the radix tree is a summary that describes three properties of
// a particular region of the address space: the number of contiguous free pages
// at the start and end of the region it represents, and the maximum number of
// contiguous free pages found anywhere in that region.
//
// Each level of the radix tree is stored as one contiguous array, which represents
// a different granularity of subdivision of the processes' address space. Thus, this
// radix tree is actually implicit in these large arrays, as opposed to having explicit
// dynamically-allocated pointer-based node structures. Naturally, these arrays may be
// quite large for system with large address spaces, so in these cases they are mapped
// into memory as needed. The leaf summaries of the tree correspond to a bitmap chunk.
//
// The root level (referred to as L0 and index 0 in pageAlloc.summary) has each
// summary represent the largest section of address space (16 GiB on 64-bit systems),
// with each subsequent level representing successively smaller subsections until we
// reach the finest granularity at the leaves, a chunk.
//
// More specifically, each summary in each level (except for leaf summaries)
// represents some number of entries in the following level. For example, each
// summary in the root level may represent a 16 GiB region of address space,
// and in the next level there could be 8 corresponding entries which represent 2
// GiB subsections of that 16 GiB region, each of which could correspond to 8
// entries in the next level which each represent 256 MiB regions, and so on.
//
// Thus, this design only scales to heaps so large, but can always be extended to
// larger heaps by simply adding levels to the radix tree, which mostly costs
// additional virtual address space. The choice of managing large arrays also means
// that a large amount of virtual address space may be reserved by the runtime.

package runtime

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

const (
	// The size of a bitmap chunk, i.e. the amount of bits (that is, pages) to consider
	// in the bitmap at once.
	pallocChunkPages    = 1 << logPallocChunkPages
	pallocChunkBytes    = pallocChunkPages * pageSize
	logPallocChunkPages = 9
	logPallocChunkBytes = logPallocChunkPages + pageShift

// The number of radix bits for each level.
	//
	// The value of 3 is chosen such that the block of summaries we need to scan at
	// each level fits in 64 bytes (2^3 summaries * 8 bytes per summary), which is
	// close to the L1 cache line width on many systems. Also, a value of 3 fits 4 tree
	// levels perfectly into the 21-bit pallocBits summary field at the root level.
	//
	// The following equation explains how each of the constants relate:
	// summaryL0Bits + (summaryLevels-1)*summaryLevelBits + logPallocChunkBytes = heapAddrBits
	//
	// summaryLevels is an architecture-dependent value defined in mpagealloc_*.go.
	summaryLevelBits = 3
	summaryL0Bits    = heapAddrBits - logPallocChunkBytes - (summaryLevels-1)*summaryLevelBits

// pallocChunksL2Bits is the number of bits of the chunk index number
	// covered by the second level of the chunks map.
	//
	// See (*pageAlloc).chunks for more details. Update the documentation
	// there should this change.
	pallocChunksL2Bits  = heapAddrBits - logPallocChunkBytes - pallocChunksL1Bits
	pallocChunksL1Shift = pallocChunksL2Bits

// Maximum searchAddr value, which indicates that the heap has no free space.
	//
	// We subtract arenaBaseOffset because we want this to represent the maximum
	// value in the shifted address space, but searchAddr is stored as a regular
	// memory address. See arenaBaseOffset for details.
	maxSearchAddr = ^uintptr(0) - arenaBaseOffset

// Minimum scavAddr value, which indicates that the scavenger is done.
	//
	// minScavAddr + arenaBaseOffset == 0
	minScavAddr = (^arenaBaseOffset + 1) & uintptrMask
)

// Global chunk index.
//
// Represents an index into the leaf level of the radix tree.
// Similar to arenaIndex, except instead of arenas, it divides the address
// space into chunks.
type chunkIdx uint

// chunkIndex returns the global index of the palloc chunk containing the
// pointer p.
func chunkIndex(p uintptr) chunkIdx {
	return chunkIdx((p + arenaBaseOffset) / pallocChunkBytes)
}

// chunkIndex returns the base address of the palloc chunk at index ci.
func chunkBase(ci chunkIdx) uintptr {
	return uintptr(ci)*pallocChunkBytes - arenaBaseOffset
}

// chunkPageIndex computes the index of the page that contains p,
// relative to the chunk which contains p.
func chunkPageIndex(p uintptr) uint {
	return uint(p % pallocChunkBytes / pageSize)
}

// l1 returns the index into the first level of (*pageAlloc).chunks.
func (i chunkIdx) l1() uint {
	if pallocChunksL1Bits == 0 {
		// Let the compiler optimize this away if there's no
		// L1 map.
		return 0
	} else {
		return uint(i) >> pallocChunksL1Shift
	}
}

// l2 returns the index into the second level of (*pageAlloc).chunks.
func (i chunkIdx) l2() uint {
	if pallocChunksL1Bits == 0 {
		return uint(i)
	} else {
		return uint(i) & (1<<pallocChunksL2Bits - 1)
	}
}

// addrsToSummaryRange converts base and limit pointers into a range
// of entries for the given summary level.
//
// The returned range is inclusive on the lower bound and exclusive on
// the upper bound.
func addrsToSummaryRange(level int, base, limit uintptr) (lo int, hi int) {
	// This is slightly more nuanced than just a shift for the exclusive
	// upper-bound. Note that the exclusive upper bound may be within a
	// summary at this level, meaning if we just do the obvious computation
	// hi will end up being an inclusive upper bound. Unfortunately, just
	// adding 1 to that is too broad since we might be on the very edge of
	// of a summary's max page count boundary for this level
	// (1 << levelLogPages[level]). So, make limit an inclusive upper bound
	// then shift, then add 1, so we get an exclusive upper bound at the end.
	lo = int((base + arenaBaseOffset) >> levelShift[level])
	hi = int(((limit-1)+arenaBaseOffset)>>levelShift[level]) + 1
	return
}

// blockAlignSummaryRange aligns indices into the given level to that
// level's block width (1 << levelBits[level]). It assumes lo is inclusive
// and hi is exclusive, and so aligns them down and up respectively.
func blockAlignSummaryRange(level int, lo, hi int) (int, int) {
	e := uintptr(1) << levelBits[level]
	return int(alignDown(uintptr(lo), e)), int(alignUp(uintptr(hi), e))
}

type pageAlloc struct {
	// Radix tree of summaries.
	//
	// Each slice's cap represents the whole memory reservation.
	// Each slice's len reflects the allocator's maximum known
	// mapped heap address for that level.
	//
	// The backing store of each summary level is reserved in init
	// and may or may not be committed in grow (small address spaces
	// may commit all the memory in init).
	//
	// The purpose of keeping len <= cap is to enforce bounds checks
	// on the top end of the slice so that instead of an unknown
	// runtime segmentation fault, we get a much friendlier out-of-bounds
	// error.
	//
	// To iterate over a summary level, use inUse to determine which ranges
	// are currently available. Otherwise one might try to access
	// memory which is only Reserved which may result in a hard fault.
	//
	// We may still get segmentation faults < len since some of that
	// memory may not be committed yet.
	summary [summaryLevels][]pallocSum

// chunks is a slice of bitmap chunks.
	//
	// The total size of chunks is quite large on most 64-bit platforms
	// (O(GiB) or more) if flattened, so rather than making one large mapping
	// (which has problems on some platforms, even when PROT_NONE) we use a
	// two-level sparse array approach similar to the arena index in mheap.
	//
	// To find the chunk containing a memory address `a`, do:
	//   chunkOf(chunkIndex(a))
	//
	// Below is a table describing the configuration for chunks for various
	// heapAddrBits supported by the runtime.
	//
	// heapAddrBits | L1 Bits | L2 Bits | L2 Entry Size
	// ------------------------------------------------
	// 32           | 0       | 10      | 128 KiB
	// 33 (iOS)     | 0       | 11      | 256 KiB
	// 48           | 13      | 13      | 1 MiB
	//
	// There's no reason to use the L1 part of chunks on 32-bit, the
	// address space is small so the L2 is small. For platforms with a
	// 48-bit address space, we pick the L1 such that the L2 is 1 MiB
	// in size, which is a good balance between low granularity without
	// making the impact on BSS too high (note the L1 is stored directly
	// in pageAlloc).
	//
	// To iterate over the bitmap, use inUse to determine which ranges
	// are currently available. Otherwise one might iterate over unused
	// ranges.
	//
	// TODO(mknyszek): Consider changing the definition of the bitmap
	// such that 1 means free and 0 means in-use so that summaries and
	// the bitmaps align better on zero-values.
	chunks [1 << pallocChunksL1Bits]*[1 << pallocChunksL2Bits]pallocData

// The address to start an allocation search with. It must never
	// point to any memory that is not contained in inUse, i.e.
	// inUse.contains(searchAddr) must always be true.
	//
	// When added with arenaBaseOffset, we guarantee that
	// all valid heap addresses (when also added with
	// arenaBaseOffset) below this value are allocated and
	// not worth searching.
	//
	// Note that adding in arenaBaseOffset transforms addresses
	// to a new address space with a linear view of the full address
	// space on architectures with segmented address spaces.
	searchAddr uintptr

// The address to start a scavenge candidate search with. It
	// need not point to memory contained in inUse.
	scavAddr uintptr

// The amount of memory scavenged since the last scavtrace print.
	//
	// Read and updated atomically.
	scavReleased uintptr

// start and end represent the chunk indices
	// which pageAlloc knows about. It assumes
	// chunks in the range [start, end) are
	// currently ready to use.
	start, end chunkIdx

// inUse is a slice of ranges of address space which are
	// known by the page allocator to be currently in-use (passed
	// to grow).
	//
	// This field is currently unused on 32-bit architectures but
	// is harmless to track. We care much more about having a
	// contiguous heap in these cases and take additional measures
	// to ensure that, so in nearly all cases this should have just
	// 1 element.
	//
	// All access is protected by the mheapLock.
	inUse addrRanges

// mheap_.lock. This level of indirection makes it possible
	// to test pageAlloc indepedently of the runtime allocator.
	mheapLock *mutex

// sysStat is the runtime memstat to update when new system
	// memory is committed by the pageAlloc for allocation metadata.
	sysStat *uint64

// Whether or not this struct is being used in tests.
	test bool
}

func (s *pageAlloc) init(mheapLock *mutex, sysStat *uint64) {
	if levelLogPages[0] > logMaxPackedValue {
		// We can't represent 1<<levelLogPages[0] pages, the maximum number
		// of pages we need to represent at the root level, in a summary, which
		// is a big problem. Throw.
		print("runtime: root level max pages = ", 1<<levelLogPages[0], "\n")
		print("runtime: summary max pages = ", maxPackedValue, "\n")
		throw("root level max pages doesn't fit in summary")
	}
	s.sysStat = sysStat

// Initialize s.inUse.
	s.inUse.init(sysStat)

// System-dependent initialization.
	s.sysInit()

// Start with the searchAddr in a state indicating there's no free memory.
	s.searchAddr = maxSearchAddr

// Start with the scavAddr in a state indicating there's nothing more to do.
	s.scavAddr = minScavAddr

// Set the mheapLock.
	s.mheapLock = mheapLock
}

// compareSearchAddrTo compares an address against s.searchAddr in a linearized
// view of the address space on systems with discontinuous process address spaces.
// This linearized view is the same one generated by chunkIndex and arenaIndex,
// done by adding arenaBaseOffset.
//
// On systems without a discontinuous address space, it's just a normal comparison.
//
// Returns < 0 if addr is less than s.searchAddr in the linearized address space.
// Returns > 0 if addr is greater than s.searchAddr in the linearized address space.
// Returns 0 if addr and s.searchAddr are equal.
func (s *pageAlloc) compareSearchAddrTo(addr uintptr) int {
	// Compare with arenaBaseOffset added because it gives us a linear, contiguous view
	// of the heap on architectures with signed address spaces.
	lAddr := addr + arenaBaseOffset
	lSearchAddr := s.searchAddr + arenaBaseOffset
	if lAddr < lSearchAddr {
		return -1
	} else if lAddr > lSearchAddr {
		return 1
	}
	return 0
}

// chunkOf returns the chunk at the given chunk index.
func (s *pageAlloc) chunkOf(ci chunkIdx) *pallocData {
	return &s.chunks[ci.l1()][ci.l2()]
}

// grow sets up the metadata for the address range [base, base+size).
// It may allocate metadata, in which case *s.sysStat will be updated.
//
// s.mheapLock must be held.
func (s *pageAlloc) grow(base, size uintptr) {
	// Round up to chunks, since we can't deal with increments smaller
	// than chunks. Also, sysGrow expects aligned values.
	limit := alignUp(base+size, pallocChunkBytes)
	base = alignDown(base, pallocChunkBytes)

// Grow the summary levels in a system-dependent manner.
	// We just update a bunch of additional metadata here.
	s.sysGrow(base, limit)

// Update s.start and s.end.
	// If no growth happened yet, start == 0. This is generally
	// safe since the zero page is unmapped.
	firstGrowth := s.start == 0
	start, end := chunkIndex(base), chunkIndex(limit)
	if firstGrowth || start < s.start {
		s.start = start
	}
	if end > s.end {
		s.end = end
	}
	// Note that [base, limit) will never overlap with any existing
	// range inUse because grow only ever adds never-used memory
	// regions to the page allocator.
	s.inUse.add(addrRange{base, limit})

// A grow operation is a lot like a free operation, so if our
	// chunk ends up below the (linearized) s.searchAddr, update
	// s.searchAddr to the new address, just like in free.
	if s.compareSearchAddrTo(base) < 0 {
		s.searchAddr = base
	}

// Add entries into chunks, which is sparse, if needed. Then,
	// initialize the bitmap.
	//
	// Newly-grown memory is always considered scavenged.
	// Set all the bits in the scavenged bitmaps high.
	for c := chunkIndex(base); c < chunkIndex(limit); c++ {
		if s.chunks[c.l1()] == nil {
			// Create the necessary l2 entry.
			//
			// Store it atomically to avoid races with readers which
			// don't acquire the heap lock.
			r := sysAlloc(unsafe.Sizeof(*s.chunks[0]), s.sysStat)
			atomic.StorepNoWB(unsafe.Pointer(&s.chunks[c.l1()]), r)
		}
		s.chunkOf(c).scavenged.setRange(0, pallocChunkPages)
	}

// Update summaries accordingly. The grow acts like a free, so
	// we need to ensure this newly-free memory is visible in the
	// summaries.
	s.update(base, size/pageSize, true, false)
}

// update updates heap metadata. It must be called each time the bitmap
// is updated.
//
// If contig is true, update does some optimizations assuming that there was
// a contiguous allocation or free between addr and addr+npages. alloc indicates
// whether the operation performed was an allocation or a free.
//
// s.mheapLock must be held.
func (s *pageAlloc) update(base, npages uintptr, contig, alloc bool) {
	// base, limit, start, and end are inclusive.
	limit := base + npages*pageSize - 1
	sc, ec := chunkIndex(base), chunkIndex(limit)

// Handle updating the lowest level first.
	if sc == ec {
		// Fast path: the allocation doesn't span more than one chunk,
		// so update this one and if the summary didn't change, return.
		x := s.summary[len(s.summary)-1][sc]
		y := s.chunkOf(sc).summarize()
		if x == y {
			return
		}
		s.summary[len(s.summary)-1][sc] = y
	} else if contig {
		// Slow contiguous path: the allocation spans more than one chunk
		// and at least one summary is guaranteed to change.
		summary := s.summary[len(s.summary)-1]

// Update the summary for chunk sc.
		summary[sc] = s.chunkOf(sc).summarize()

// Update the summaries for chunks in between, which are
		// either totally allocated or freed.
		whole := s.summary[len(s.summary)-1][sc+1 : ec]
		if alloc {
			// Should optimize into a memclr.
			for i := range whole {
				whole[i] = 0
			}
		} else {
			for i := range whole {
				whole[i] = freeChunkSum
			}
		}

// Update the summary for chunk ec.
		summary[ec] = s.chunkOf(ec).summarize()
	} else {
		// Slow general path: the allocation spans more than one chunk
		// and at least one summary is guaranteed to change.
		//
		// We can't assume a contiguous allocation happened, so walk over
		// every chunk in the range and manually recompute the summary.
		summary := s.summary[len(s.summary)-1]
		for c := sc; c <= ec; c++ {
			summary[c] = s.chunkOf(c).summarize()
		}
	}

// Walk up the radix tree and update the summaries appropriately.
	changed := true
	for l := len(s.summary) - 2; l >= 0 && changed; l-- {
		// Update summaries at level l from summaries at level l+1.
		changed = false

// "Constants" for the previous level which we
		// need to compute the summary from that level.
		logEntriesPerBlock := levelBits[l+1]
		logMaxPages := levelLogPages[l+1]

// lo and hi describe all the parts of the level we need to look at.
		lo, hi := addrsToSummaryRange(l, base, limit+1)

// Iterate over each block, updating the corresponding summary in the less-granular level.
		for i := lo; i < hi; i++ {
			children := s.summary[l+1][i<<logEntriesPerBlock : (i+1)<<logEntriesPerBlock]
			sum := mergeSummaries(children, logMaxPages)
			old := s.summary[l][i]
			if old != sum {
				changed = true
				s.summary[l][i] = sum
			}
		}
	}
}

// allocRange marks the range of memory [base, base+npages*pageSize) as
// allocated. It also updates the summaries to reflect the newly-updated
// bitmap.
//
// Returns the amount of scavenged memory in bytes present in the
// allocated range.
//
// s.mheapLock must be held.
func (s *pageAlloc) allocRange(base, npages uintptr) uintptr {
	limit := base + npages*pageSize - 1
	sc, ec := chunkIndex(base), chunkIndex(limit)
	si, ei := chunkPageIndex(base), chunkPageIndex(limit)

scav := uint(0)
	if sc == ec {
		// The range doesn't cross any chunk boundaries.
		chunk := s.chunkOf(sc)
		scav += chunk.scavenged.popcntRange(si, ei+1-si)
		chunk.allocRange(si, ei+1-si)
	} else {
		// The range crosses at least one chunk boundary.
		chunk := s.chunkOf(sc)
		scav += chunk.scavenged.popcntRange(si, pallocChunkPages-si)
		chunk.allocRange(si, pallocChunkPages-si)
		for c := sc + 1; c < ec; c++ {
			chunk := s.chunkOf(c)
			scav += chunk.scavenged.popcntRange(0, pallocChunkPages)
			chunk.allocAll()
		}
		chunk = s.chunkOf(ec)
		scav += chunk.scavenged.popcntRange(0, ei+1)
		chunk.allocRange(0, ei+1)
	}
	s.update(base, npages, true, true)
	return uintptr(scav) * pageSize
}

// find searches for the first (address-ordered) contiguous free region of
// npages in size and returns a base address for that region.
//
// It uses s.searchAddr to prune its search and assumes that no palloc chunks
// below chunkIndex(s.searchAddr) contain any free memory at all.
//
// find also computes and returns a candidate s.searchAddr, which may or
// may not prune more of the address space than s.searchAddr already does.
//
// find represents the slow path and the full radix tree search.
//
// Returns a base address of 0 on failure, in which case the candidate
// searchAddr returned is invalid and must be ignored.
//
// s.mheapLock must be held.
func (s *pageAlloc) find(npages uintptr) (uintptr, uintptr) {
	// Search algorithm.
	//
	// This algorithm walks each level l of the radix tree from the root level
	// to the leaf level. It iterates over at most 1 << levelBits[l] of entries
	// in a given level in the radix tree, and uses the summary information to
	// find either:
	//  1) That a given subtree contains a large enough contiguous region, at
	//     which point it continues iterating on the next level, or
	//  2) That there are enough contiguous boundary-crossing bits to satisfy
	//     the allocation, at which point it knows exactly where to start
	//     allocating from.
	//
	// i tracks the index into the current level l's structure for the
	// contiguous 1 << levelBits[l] entries we're actually interested in.
	//
	// NOTE: Technically this search could allocate a region which crosses
	// the arenaBaseOffset boundary, which when arenaBaseOffset != 0, is
	// a discontinuity. However, the only way this could happen is if the
	// page at the zero address is mapped, and this is impossible on
	// every system we support where arenaBaseOffset != 0. So, the
	// discontinuity is already encoded in the fact that the OS will never
	// map the zero page for us, and this function doesn't try to handle
	// this case in any way.

// i is the beginning of the block of entries we're searching at the
	// current level.
	i := 0

// firstFree is the region of address space that we are certain to
	// find the first free page in the heap. base and bound are the inclusive
	// bounds of this window, and both are addresses in the linearized, contiguous
	// view of the address space (with arenaBaseOffset pre-added). At each level,
	// this window is narrowed as we find the memory region containing the
	// first free page of memory. To begin with, the range reflects the
	// full process address space.
	//
	// firstFree is updated by calling foundFree each time free space in the
	// heap is discovered.
	//
	// At the end of the search, base-arenaBaseOffset is the best new
	// searchAddr we could deduce in this search.
	firstFree := struct {
		base, bound uintptr
	}{
		base:  0,
		bound: (1<<heapAddrBits - 1),
	}
	// foundFree takes the given address range [addr, addr+size) and
	// updates firstFree if it is a narrower range. The input range must
	// either be fully contained within firstFree or not overlap with it
	// at all.
	//
	// This way, we'll record the first summary we find with any free
	// pages on the root level and narrow that down if we descend into
	// that summary. But as soon as we need to iterate beyond that summary
	// in a level to find a large enough range, we'll stop narrowing.
	foundFree := func(addr, size uintptr) {
		if firstFree.base <= addr && addr+size-1 <= firstFree.bound {
			// This range fits within the current firstFree window, so narrow
			// down the firstFree window to the base and bound of this range.
			firstFree.base = addr
			firstFree.bound = addr + size - 1
		} else if !(addr+size-1 < firstFree.base || addr > firstFree.bound) {
			// This range only partially overlaps with the firstFree range,
			// so throw.
			print("runtime: addr = ", hex(addr), ", size = ", size, "\n")
			print("runtime: base = ", hex(firstFree.base), ", bound = ", hex(firstFree.bound), "\n")
			throw("range partially overlaps")
		}
	}

// lastSum is the summary which we saw on the previous level that made us
	// move on to the next level. Used to print additional information in the
	// case of a catastrophic failure.
	// lastSumIdx is that summary's index in the previous level.
	lastSum := packPallocSum(0, 0, 0)
	lastSumIdx := -1

nextLevel:
	for l := 0; l < len(s.summary); l++ {
		// For the root level, entriesPerBlock is the whole level.
		entriesPerBlock := 1 << levelBits[l]
		logMaxPages := levelLogPages[l]

// We've moved into a new level, so let's update i to our new
		// starting index. This is a no-op for level 0.
		i <<= levelBits[l]

// Slice out the block of entries we care about.
		entries := s.summary[l][i : i+entriesPerBlock]

// Determine j0, the first index we should start iterating from.
		// The searchAddr may help us eliminate iterations if we followed the
		// searchAddr on the previous level or we're on the root leve, in which
		// case the searchAddr should be the same as i after levelShift.
		j0 := 0
		if searchIdx := int((s.searchAddr + arenaBaseOffset) >> levelShift[l]); searchIdx&^(entriesPerBlock-1) == i {
			j0 = searchIdx & (entriesPerBlock - 1)
		}

// Run over the level entries looking for
		// a contiguous run of at least npages either
		// within an entry or across entries.
		//
		// base contains the page index (relative to
		// the first entry's first page) of the currently
		// considered run of consecutive pages.
		//
		// size contains the size of the currently considered
		// run of consecutive pages.
		var base, size uint
		for j := j0; j < len(entries); j++ {
			sum := entries[j]
			if sum == 0 {
				// A full entry means we broke any streak and
				// that we should skip it altogether.
				size = 0
				continue
			}

// We've encountered a non-zero summary which means
			// free memory, so update firstFree.
			foundFree(uintptr((i+j)<<levelShift[l]), (uintptr(1)<<logMaxPages)*pageSize)

s := sum.start()
			if size+s >= uint(npages) {
				// If size == 0 we don't have a run yet,
				// which means base isn't valid. So, set
				// base to the first page in this block.
				if size == 0 {
					base = uint(j) << logMaxPages
				}
				// We hit npages; we're done!
				size += s
				break
			}
			if sum.max() >= uint(npages) {
				// The entry itself contains npages contiguous
				// free pages, so continue on the next level
				// to find that run.
				i += j
				lastSumIdx = i
				lastSum = sum
				continue nextLevel
			}
			if size == 0 || s < 1<<logMaxPages {
				// We either don't have a current run started, or this entry
				// isn't totally free (meaning we can't continue the current
				// one), so try to begin a new run by setting size and base
				// based on sum.end.
				size = sum.end()
				base = uint(j+1)<<logMaxPages - size
				continue
			}
			// The entry is completely free, so continue the run.
			size += 1 << logMaxPages
		}
		if size >= uint(npages) {
			// We found a sufficiently large run of free pages straddling
			// some boundary, so compute the address and return it.
			addr := uintptr(i<<levelShift[l]) - arenaBaseOffset + uintptr(base)*pageSize
			return addr, firstFree.base - arenaBaseOffset
		}
		if l == 0 {
			// We're at level zero, so that means we've exhausted our search.
			return 0, maxSearchAddr
		}

// We're not at level zero, and we exhausted the level we were looking in.
		// This means that either our calculations were wrong or the level above
		// lied to us. In either case, dump some useful state and throw.
		print("runtime: summary[", l-1, "][", lastSumIdx, "] = ", lastSum.start(), ", ", lastSum.max(), ", ", lastSum.end(), "\n")
		print("runtime: level = ", l, ", npages = ", npages, ", j0 = ", j0, "\n")
		print("runtime: s.searchAddr = ", hex(s.searchAddr), ", i = ", i, "\n")
		print("runtime: levelShift[level] = ", levelShift[l], ", levelBits[level] = ", levelBits[l], "\n")
		for j := 0; j < len(entries); j++ {
			sum := entries[j]
			print("runtime: summary[", l, "][", i+j, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
		}
		throw("bad summary data")
	}

// Since we've gotten to this point, that means we haven't found a
	// sufficiently-sized free region straddling some boundary (chunk or larger).
	// This means the last summary we inspected must have had a large enough "max"
	// value, so look inside the chunk to find a suitable run.
	//
	// After iterating over all levels, i must contain a chunk index which
	// is what the final level represents.
	ci := chunkIdx(i)
	j, searchIdx := s.chunkOf(ci).find(npages, 0)
	if j < 0 {
		// We couldn't find any space in this chunk despite the summaries telling
		// us it should be there. There's likely a bug, so dump some state and throw.
		sum := s.summary[len(s.summary)-1][i]
		print("runtime: summary[", len(s.summary)-1, "][", i, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
		print("runtime: npages = ", npages, "\n")
		throw("bad summary data")
	}

// Compute the address at which the free space starts.
	addr := chunkBase(ci) + uintptr(j)*pageSize

// Since we actually searched the chunk, we may have
	// found an even narrower free window.
	searchAddr := chunkBase(ci) + uintptr(searchIdx)*pageSize
	foundFree(searchAddr+arenaBaseOffset, chunkBase(ci+1)-searchAddr)
	return addr, firstFree.base - arenaBaseOffset
}

// alloc allocates npages worth of memory from the page heap, returning the base
// address for the allocation and the amount of scavenged memory in bytes
// contained in the region [base address, base address + npages*pageSize).
//
// Returns a 0 base address on failure, in which case other returned values
// should be ignored.
//
// s.mheapLock must be held.
func (s *pageAlloc) alloc(npages uintptr) (addr uintptr, scav uintptr) {
	// If the searchAddr refers to a region which has a higher address than
	// any known chunk, then we know we're out of memory.
	if chunkIndex(s.searchAddr) >= s.end {
		return 0, 0
	}

// If npages has a chance of fitting in the chunk where the searchAddr is,
	// search it directly.
	searchAddr := uintptr(0)
	if pallocChunkPages-chunkPageIndex(s.searchAddr) >= uint(npages) {
		// npages is guaranteed to be no greater than pallocChunkPages here.
		i := chunkIndex(s.searchAddr)
		if max := s.summary[len(s.summary)-1][i].max(); max >= uint(npages) {
			j, searchIdx := s.chunkOf(i).find(npages, chunkPageIndex(s.searchAddr))
			if j < 0 {
				print("runtime: max = ", max, ", npages = ", npages, "\n")
				print("runtime: searchIdx = ", chunkPageIndex(s.searchAddr), ", s.searchAddr = ", hex(s.searchAddr), "\n")
				throw("bad summary data")
			}
			addr = chunkBase(i) + uintptr(j)*pageSize
			searchAddr = chunkBase(i) + uintptr(searchIdx)*pageSize
			goto Found
		}
	}
	// We failed to use a searchAddr for one reason or another, so try
	// the slow path.
	addr, searchAddr = s.find(npages)
	if addr == 0 {
		if npages == 1 {
			// We failed to find a single free page, the smallest unit
			// of allocation. This means we know the heap is completely
			// exhausted. Otherwise, the heap still might have free
			// space in it, just not enough contiguous space to
			// accommodate npages.
			s.searchAddr = maxSearchAddr
		}
		return 0, 0
	}
Found:
	// Go ahead and actually mark the bits now that we have an address.
	scav = s.allocRange(addr, npages)

// If we found a higher (linearized) searchAddr, we know that all the
	// heap memory before that searchAddr in a linear address space is
	// allocated, so bump s.searchAddr up to the new one.
	if s.compareSearchAddrTo(searchAddr) > 0 {
		s.searchAddr = searchAddr
	}
	return addr, scav
}

// free returns npages worth of memory starting at base back to the page heap.
//
// s.mheapLock must be held.
func (s *pageAlloc) free(base, npages uintptr) {
	// If we're freeing pages below the (linearized) s.searchAddr, update searchAddr.
	if s.compareSearchAddrTo(base) < 0 {
		s.searchAddr = base
	}
	if npages == 1 {
		// Fast path: we're clearing a single bit, and we know exactly
		// where it is, so mark it directly.
		i := chunkIndex(base)
		s.chunkOf(i).free1(chunkPageIndex(base))
	} else {
		// Slow path: we're clearing more bits so we may need to iterate.
		limit := base + npages*pageSize - 1
		sc, ec := chunkIndex(base), chunkIndex(limit)
		si, ei := chunkPageIndex(base), chunkPageIndex(limit)

if sc == ec {
			// The range doesn't cross any chunk boundaries.
			s.chunkOf(sc).free(si, ei+1-si)
		} else {
			// The range crosses at least one chunk boundary.
			s.chunkOf(sc).free(si, pallocChunkPages-si)
			for c := sc + 1; c < ec; c++ {
				s.chunkOf(c).freeAll()
			}
			s.chunkOf(ec).free(0, ei+1)
		}
	}
	s.update(base, npages, true, false)
}

const (
	pallocSumBytes = unsafe.Sizeof(pallocSum(0))

// maxPackedValue is the maximum value that any of the three fields in
	// the pallocSum may take on.
	maxPackedValue    = 1 << logMaxPackedValue
	logMaxPackedValue = logPallocChunkPages + (summaryLevels-1)*summaryLevelBits

freeChunkSum = pallocSum(uint64(pallocChunkPages) |
		uint64(pallocChunkPages<<logMaxPackedValue) |
		uint64(pallocChunkPages<<(2*logMaxPackedValue)))
)

// pallocSum is a packed summary type which packs three numbers: start, max,
// and end into a single 8-byte value. Each of these values are a summary of
// a bitmap and are thus counts, each of which may have a maximum value of
// 2^21 - 1, or all three may be equal to 2^21. The latter case is represented
// by just setting the 64th bit.
type pallocSum uint64

// packPallocSum takes a start, max, and end value and produces a pallocSum.
func packPallocSum(start, max, end uint) pallocSum {
	if max == maxPackedValue {
		return pallocSum(uint64(1 << 63))
	}
	return pallocSum((uint64(start) & (maxPackedValue - 1)) |
		((uint64(max) & (maxPackedValue - 1)) << logMaxPackedValue) |
		((uint64(end) & (maxPackedValue - 1)) << (2 * logMaxPackedValue)))
}

// start extracts the start value from a packed sum.
func (p pallocSum) start() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint(uint64(p) & (maxPackedValue - 1))
}

// max extracts the max value from a packed sum.
func (p pallocSum) max() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1))
}

// end extracts the end value from a packed sum.
func (p pallocSum) end() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}

// unpack unpacks all three values from the summary.
func (p pallocSum) unpack() (uint, uint, uint) {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue, maxPackedValue, maxPackedValue
	}
	return uint(uint64(p) & (maxPackedValue - 1)),
		uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1)),
		uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}

// mergeSummaries merges consecutive summaries which may each represent at
// most 1 << logMaxPagesPerSum pages each together into one.
func mergeSummaries(sums []pallocSum, logMaxPagesPerSum uint) pallocSum {
	// Merge the summaries in sums into one.
	//
	// We do this by keeping a running summary representing the merged
	// summaries of sums[:i] in start, max, and end.
	start, max, end := sums[0].unpack()
	for i := 1; i < len(sums); i++ {
		// Merge in sums[i].
		si, mi, ei := sums[i].unpack()

// Merge in sums[i].start only if the running summary is
		// completely free, otherwise this summary's start
		// plays no role in the combined sum.
		if start == uint(i)<<logMaxPagesPerSum {
			start += si
		}

// Recompute the max value of the running sum by looking
		// across the boundary between the running sum and sums[i]
		// and at the max sums[i], taking the greatest of those two
		// and the max of the running sum.
		if end+si > max {
			max = end + si
		}
		if mi > max {
			max = mi
		}

// Merge in end by checking if this new summary is totally
		// free. If it is, then we want to extend the running sum's
		// end by the new summary. If not, then we have some alloc'd
		// pages in there and we just want to take the end value in
		// sums[i].
		if ei == 1<<logMaxPagesPerSum {
			end += 1 << logMaxPagesPerSum
		} else {
			end = ei
		}
	}
	return packPallocSum(start, max, end)
}

${this.title}

Code Editor : mpagealloc.go