golang程序启动流程详解

golang程序启动流程详解

环境

go1.16.5 linux/amd64

用例

1
2
3
4
5
6
7
package main

import "fmt"

func main() {
fmt.Println(42)
}

编译

-gcflags “-N -l”: 关闭优化和内联,方便调试跟踪

1
$ go build -gcflags "-N -l" -o hello hello.go 

gdb跟踪执行流程

1
2
3
$ gdb hello

$ source /usr/lib/go/src/runtime/runtime-gdb.py # 加载Go运行时支持

预备知识:

1. GMP调度模型
  • Golang的调度器模型是”GMP”模型,P作为逻辑cpu的抽象,解决了竞争全局队列等问题.
  • M是操作系统线程,M必须关联到某个P上,从P上获取工作goroutine
  • 一个P可能有多个M,当某个M阻塞时.

GMP模型

2. runtime/proc.go中定义了一些重要的全局符号,下面分析启动流程会涉及这些符号:
1
2
3
4
5
6
var (
m0 m // 第一个m
g0 g // 第一个goroutine
mcache0 *mcache // m0的cache
raceprocctx0 uintptr // 用于竞争检测
)
  • g0: 主线程上的第一个协程g0, g0拥有这个线程的系统栈,这个栈很大.g0还有创建新协程的职责,当我们调用go func创建新协程都会在g0的栈上执行.
  • m0: 第一个工作线程,主线程
  • mcache0: m0的cache
3. tls线程私有存储

每个线程的私有存储空间,golang主要用其来设置每个m当前正在运行的goroutine,这样可以快速获取到当前上下文的goroutine. 类似于linux内核中的current宏.

4. sched全局结构

golang使用一个全局schedt结构来控制全局调度(runtime2.go),里面主要的信息如全局运行队列,所有m,所有p的状态信息,系统监控sysmon等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var (
allm *m
gomaxprocs int32
ncpu int32
forcegc forcegcstate
sched schedt
newprocs int32

// allpLock protects P-less reads and size changes of allp, idlepMask,
// and timerpMask, and all writes to allp.
allpLock mutex
// len(allp) == gomaxprocs; may change at safe points, otherwise
// immutable.
allp []*p

程序入口函数:

  • 为g0分配栈空间
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
runtime.asm_amd64.s:89

TEXT runtime·rt0_go<ABIInternal>(SB),NOSPLIT,$0
// copy arguments forward on an even stack
MOVQ DI, AX // x64上使用rdi,rsi传递入参, di:argc si:argv
MOVQ SI, BX // argv
SUBQ $(4*8+7), SP // 开辟栈空间,用于存放argc, argv和两个局部变量
ANDQ $~15, SP //与~15& 保障SP 16字节对齐
MOVQ AX, 16(SP) // 存储argc, argv
MOVQ BX, 24(SP) //

MOVQ $runtime·g0(SB), DI // 将g0存储到DI寄存器
LEAQ (-64*1024+104)(SP), BX // 为g0开辟64kb栈空间
MOVQ BX, g_stackguard0(DI) // 将栈底地址保存到g0->stackguard0
MOVQ BX, g_stackguard1(DI)
MOVQ BX, (g_stack+stack_lo)(DI) // 将栈底保存到g0->stack->lo
MOVQ SP, (g_stack+stack_hi)(DI) // 将栈顶保存到g0->stack->hi

// 下面是g0的结构:
type g struct {
// Stack parameters.
// stack describes the actual stack memory: [stack.lo, stack.hi).
// stackguard0 is the stack pointer compared in the Go stack growth prologue.
// It is stack.lo+StackGuard normally, but can be StackPreempt to trigger a preemption.
// stackguard1 is the stack pointer compared in the C stack growth prologue.
// It is stack.lo+StackGuard on g0 and gsignal stacks.
// It is ~0 on other goroutine stacks, to trigger a call to morestackc (and crash).
stack stack // offset known to runtime/cgo
stackguard0 uintptr // offset known to liblink
stackguard1 uintptr // offset known to liblink
  • 获取cpu相关信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// find out information about the processor we're on
MOVL $0, AX // 获取CPUID信息
CPUID
MOVL AX, SI // 我本机获取到的cpuid为0xd
CMPL AX, $0 //判断是否获取到了cpuid,成功
JE nocpuinfo

// 判断cpu的型号,并设置标志,如是否是intel.
// 主要是需要确定RDTSC的获取方式,即cpu时间戳计数器
CMPL BX, $0x756E6547 // "Genu" 正式版 o
JNE notintel
CMPL DX, $0x49656E69 // "ineI"
JNE notintel
CMPL CX, $0x6C65746E // "ntel"
JNE notintel
MOVB $1, runtime·isIntel(SB) //is inel
MOVB $1, runtime·lfenceBeforeRdtsc(SB) //

...
  • 初始化tls,设置m->g0, g0->m,初始化sched信息
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
   MOVQ	_cgo_init(SB), AX // 查看是否有_cgo_init,如果有则需要调用,我们的例子中没有_cgo_init
TESTQ AX, AX
JZ needtls //设置tls

...
LEAQ runtime·m0+m_tls(SB), DI //获取m0中的tls结构
CALL runtime·settls(SB) // 调用sys_linux_amd64.s:658来设置tls, linux上设置tls主要是通过arch_pcrtl实现,设置当前线程的FS信息.

// store through it, to make sure it works
get_tls(BX) //下面代码主要测试tls是否正确工作.
MOVQ $0x123, g(BX)
MOVQ runtime·m0+m_tls(SB), AX
CMPQ AX, $0x123
JEQ 2(PC)
CALL runtime·abort(SB)

...
// set the per-goroutine and per-mach "registers"
get_tls(BX)
LEAQ runtime·g0(SB), CX // 将g0保存到tls中
MOVQ CX, g(BX) // save g0 to tls
LEAQ runtime·m0(SB), AX // ax -->m0

// save m->g0 = g0
MOVQ CX, m_g0(AX) //将g0保存到m0中
// save m0 to g0->m
MOVQ AX, g_m(CX) // 将m0设置到g0中

CLD // convention is D is always left cleared
CALL runtime·check(SB) //runtime1.go:137 检查一些cas和原子操作工作是否正确

MOVL 16(SP), AX // 获取之前保存到栈中的argc, argv
MOVL AX, 0(SP)
MOVQ 24(SP), AX // copy argv
MOVQ AX, 8(SP)
CALL runtime·args(SB) //runtime1.go:61 设置argc, argv到全局变量runtime1.argc, runtime1.argv
CALL runtime·osinit(SB) //301 os初始化,根据cpu亲和性获取可用cpu个数,获取大页信息
CALL runtime·schedinit(SB) //600 sched初始化,这是一个go函数,先来看一下。
1
2
3
4
type m struct {
g0 *g // goroutine with scheduling stack
...
tls [6]uintptr // thread-local storage (for x86 extern register)
sched初始化

sched内容比较多,我们详细来看一下:

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
_g_ := getg()  // 获取当前的goroutine, 之前已经保存在tls中了,getg就是从tls中获取
if raceenabled {
_g_.racectx, raceprocctx0 = raceinit()
}

sched.maxmcount = 10000 //设置最大m线程个数为10000

// The world starts stopped.
worldStopped()

stackinit() // 栈缓存初始化,golang运行时需要分配栈时优先使用缓存
mallocinit() // 内存管理初始化
fastrandinit() // must run before mcommoninit, 快速随机数初始化
mcommoninit(_g_.m, -1) // m初始化并将其放到全局allm链表中
cpuinit() // must run before alginit, cpu初始化
alginit() // maps must not be used before this call
modulesinit() // provides activeModules
typelinksinit() // uses maps, activeModules
itabsinit() // uses activeModules

sigsave(&_g_.m.sigmask) // 保存当前信号掩码到m
initSigmask = _g_.m.sigmask

goargs()
goenvs()
parsedebugvars()
gcinit() // 初始化gc

lock(&sched.lock)
sched.lastpoll = uint64(nanotime())
procs := ncpu
if n, ok := atoi32(gogetenv("GOMAXPROCS")); ok && n > 0 { //环境变量是否设置了GOMAXPROCS
procs = n
}
if procresize(procs) != nil { // 重新调整p的数量.
throw("unknown runnable goroutine during bootstrap")
}
unlock(&sched.lock)

// World is effectively started now, as P's can run.
worldStarted()

...
sched初始化就完成了,主要就是一些全局信息,包括内存,栈缓存,P的个数,gc等.

再回到汇编:

  • 设置主协程入口函数runtime.mainPC,调用newproc创建主协程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CALL	runtime·schedinit(SB) //600

// create a new goroutine to start program
MOVQ $runtime·mainPC(SB), AX // 新goroutine的入口函数
PUSHQ AX // 压入栈中下面传递给newproc
PUSHQ $0 // arg size
CALL runtime·newproc(SB) // 创建新的p,这也是一个go函数,重点分析一下.
POPQ AX
POPQ AX

// start this M
CALL runtime·mstart(SB) //mstart loop

CALL runtime·abort(SB) // mstart should never return
RET
newproc:
  • 创建主协程并将其放到p的本地队列中,systemstack函数表示在系统栈上执行goroutine的创建操作
1
2
3
4
5
6
7
8
9
10
11
12
13
argp := add(unsafe.Pointer(&fn), sys.PtrSize) // 获取argp
gp := getg() // 获取当前goroutine
pc := getcallerpc()
systemstack(func() { // 调用systemstack来执行
newg := newproc1(fn, argp, siz, gp, pc)

_p_ := getg().m.p.ptr()
runqput(_p_, newg, true)

if mainStarted {
wakep()
}
})
systemstack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TEXT runtime·systemstack(SB), NOSPLIT, $0-8
MOVQ fn+0(FP), DI // DI = fn, 将要执行的函数指针放到rdi.
get_tls(CX) // 获取当前goroutine
MOVQ g(CX), AX // AX = g, g0
MOVQ g_m(AX), BX // BX = m, m0

CMPQ AX, m_gsignal(BX) //判断当前goroutine是否是用于处理信号的goroutine
JEQ noswitch

MOVQ m_g0(BX), DX // DX = g0
CMPQ AX, DX // 判断当前goroutine是否是当前栈的使用者
JEQ noswitch // 如果是则不需要切换栈, 这里明显是,因此直接跳转到noswitch

CMPQ AX, m_curg(BX)
JNE bad

noswitch:
// already on m stack; tail call the function
// Using a tail call here cleans up tracebacks since we won't stop
// at an intermediate systemstack.
MOVQ DI, DX
MOVQ 0(DI), DI // di是之前传递给systemstack的fn
JMP DI // 执行fn
1
2
3
4
5
6
7
8
9
10
systemstack(func() {
newg := newproc1(fn, argp, siz, gp, pc) //创建新goroutine执行fn

_p_ := getg().m.p.ptr()
runqput(_p_, newg, true)

if mainStarted {
wakep()
}
})
newproc1:

newproc1的作用是为执行函数分配新的goroutine

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
func newproc1(fn *funcval, argp unsafe.Pointer, narg int32, callergp *g, callerpc uintptr) *g {
_g_ := getg() // 获取当前g

if fn == nil {
_g_.m.throwing = -1 // do not dump full stacks
throw("go of nil func value")
}
acquirem() // 锁定m,禁止抢占
siz := narg
siz = (siz + 7) &^ 7

_p_ := _g_.m.p.ptr() // 获取当前的p
newg := gfget(_p_) // 查找是否有缓存的goroutine,这些goroutine是dead状态的,可以直接使用的.如果本地没有还会从全局查找,最后都没有才会真的申请新的goroutine

if newg == nil { // 当前没有可重复使用的缓存gorutine
newg = malg(_StackMin) // 申请新的goroutine
casgstatus(newg, _Gidle, _Gdead) // 初始状态为Gdead.
allgadd(newg) // 将newg加入全局allg
}

/*为newg 准备栈和参数*/
totalSize := 4*sys.RegSize + uintptr(siz) + sys.MinFrameSize // extra space in case of reads slightly beyond frame
totalSize += -totalSize & (sys.SpAlign - 1) // align to spAlign
sp := newg.stack.hi - totalSize
spArg := sp
if usesLR {
// caller's LR
*(*uintptr)(unsafe.Pointer(sp)) = 0
prepGoExitFrame(sp)
spArg += sys.MinFrameSize
}

...
/*设置newg的sp, pc, g, startpc等 信息*/
newg.sched.sp = sp
newg.stktopsp = sp
newg.sched.pc = funcPC(goexit) + sys.PCQuantum // +PCQuantum so that previous instruction is in same function
newg.sched.g = guintptr(unsafe.Pointer(newg))
gostartcallfn(&newg.sched, fn)
newg.gopc = callerpc
newg.ancestors = saveAncestors(callergp)
newg.startpc = fn.fn

casgstatus(newg, _Gdead, _Grunnable) // 修改newg状态为runnable

if _p_.goidcache == _p_.goidcacheend {
// Sched.goidgen is the last allocated id,
// this batch must be [sched.goidgen+1, sched.goidgen+GoidCacheBatch].
// At startup sched.goidgen=0, so main goroutine receives goid=1.
_p_.goidcache = atomic.Xadd64(&sched.goidgen, _GoidCacheBatch)
_p_.goidcache -= _GoidCacheBatch - 1
_p_.goidcacheend = _p_.goidcache + _GoidCacheBatch
}
newg.goid = int64(_p_.goidcache) // 设置goroutie id.
_p_.goidcache++

...

创建好新的goroutine后,继续:

1
2
3
4
5
6
7
8
9
10
systemstack(func() {
newg := newproc1(fn, argp, siz, gp, pc) //创建新goroutine执行fn

_p_ := getg().m.p.ptr() // 获取新routine的p.
runqput(_p_, newg, true) // 将新routine放入运行队列. 首先尝试放入本地队列,如果本地队列满则放入全局队列.本地队列最大256.

if mainStarted {
wakep()
}
})
新goroutine创建完成,再启动一个m,这个m目前是主线程,即m0
1
2
3
4
5
6
7
8
9
CALL	runtime·newproc(SB)
POPQ AX
POPQ AX

// start this M
CALL runtime·mstart(SB) //调用mstart启动m

CALL runtime·abort(SB) // mstart should never return
RET
初始化m0,设置线程id
1
2
3
4
5
6
7
8
func minit() {
minitSignals() // 初始化信号处理,设置信号处理栈和掩码

// Cgo-created threads and the bootstrap m are missing a
// procid. We need this for asynchronous preemption and it's
// useful in debuggers.
getg().m.procid = uint64(gettid()) //设置m的procid,即线程id
}
  • m0,g0都初始化完成后就开始执行主协程,这时通过汇编代码gogo执行主协程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TEXT runtime·gogo(SB), NOSPLIT, $16-8
MOVQ buf+0(FP), BX // gobuf
MOVQ gobuf_g(BX), DX
MOVQ 0(DX), CX // make sure g != nil
get_tls(CX)
MOVQ DX, g(CX)
MOVQ gobuf_sp(BX), SP // restore SP
MOVQ gobuf_ret(BX), AX
MOVQ gobuf_ctxt(BX), DX
MOVQ gobuf_bp(BX), BP
MOVQ $0, gobuf_sp(BX) // clear to help garbage collector
MOVQ $0, gobuf_ret(BX)
MOVQ $0, gobuf_ctxt(BX)
MOVQ $0, gobuf_bp(BX)
MOVQ gobuf_pc(BX), BX // 执行之前的runtime.mainPC,即主协程入口
JMP BX
  • 执行主协程入口proc.go: main

主协程会启动sysmon线程进行监控,然后执行package main里我们实现的main函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
...
mainStarted = true // 设置main开始标志,这样才允许新协程启动新的M.

if GOARCH != "wasm" { // no threads on wasm yet, so no sysmon
// For runtime_syscall_doAllThreadsSyscall, we
// register sysmon is not ready for the world to be
// stopped.
atomic.Store(&sched.sysmonStarting, 1)
systemstack(func() {
newm(sysmon, nil, -1) // 启动sysmon
})

...
fn := main_main // 执行package main中主函数
fn()

上面就是一个go程序的启动流程,总结一下:

go程序启动流程

我们再来分析一下调用go func创建协程的流程

go func流程

  • go func关键字会被编译器转换为runtime.newproc调用创建新协程
  • 新协程加入当前p的本地队列
  • 如果本地队列已满,则批量将一半的goroutine放入全局队列
  • 之前主协程已经设置了mainStarted标志,因此会调用wakeup尝试唤醒更多空闲的p来工作

C语言中协程调度实现原理

协程切换原理

使用glibc中<ucontext.h>提供的相关函数

用户态切换简单来说就是保存当前上下文,切换到新的上下文.
用户态程序的上下文一般包含如下信息:

  • 各种寄存器
  • 信号掩码: linux信号掩码是基于线程的,协程也需要支持单独设置信号掩码信息

我们来看一下glibc定义的用户态上下文结构ucontext_t:

1
2
3
4
5
6
7
8
9
10
typedef struct ucontext_t
{
unsigned long int __ctx(uc_flags);
struct ucontext_t *uc_link; // 链接下一个ucontext_t,当前上下文结束后自动切换到这个上下文,用于被动切换
stack_t uc_stack; // 当前上下文的栈信息, 24字节
mcontext_t uc_mcontext; // 当前上下文的通用寄存器, 23个通用寄存器,1个指向fpu结构的指针,64字节保留信息. 总共256字节
sigset_t uc_sigmask; //当前上下文的信号掩码, 128字节
struct _libc_fpstate __fpregs_mem; // fpu相关寄存器
unsigned long long int __ssp[4];
} ucontext_t; // 总共968字节

通过上述结构定义,我们也可以看出,用户态上下文主要就是寄存器和栈,另外还有信号掩码信息.

ucontext相关api实现

由于ucontext api使用汇编代码实现,因此我们先来学习一些汇编基础知识.
  • x64上使用rdi, rsi, rdx, rcx, r9, r10传递参数,如果参数大于6个则使用栈
  • leaq指令用于取地址,类似于c中的&
另外为了理解如何保存当前栈和指令寄存器,我们要熟悉一下x64上函数调用的相关知识:

x64函数调用规范

    1. 当上一个函数使用call指令调用当前函数时,会将上一个函数的返回地址prev rip压入栈中,这样当被调用函数调用ret指令返回时就会从栈中pop出这个地址进行返回
    1. 当前函数执行时,会将上一级函数的rbp压入栈中,用于函数返回时还原,然后将rbp设置为当前的栈底,再调用rsp开辟当前函数的栈.
    1. 现在我们考虑在当前函数中调用getcontext会发生什么, 通过call调用getcontext后,当前函数的返回地址current rip被压入栈中:

1. 保存当前上下文

getcontext能够将当前的上下文信息保存起来,用于后面还原.我们来看下具体实现:

函数原型
1
int getcontext(ucontext_t *ucp);
函数详解
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
ENTRY(__getcontext)
/* Save the preserved registers, the registers used for passing
args, and the return address. */
movq %rbx, oRBX(%rdi) // rdi即为每一个函数参数,即我们传递的ucontext_t
movq %rbp, oRBP(%rdi)
movq %r12, oR12(%rdi)
movq %r13, oR13(%rdi)
movq %r14, oR14(%rdi)
movq %r15, oR15(%rdi)

movq %rdi, oRDI(%rdi)
movq %rsi, oRSI(%rdi)
movq %rdx, oRDX(%rdi)
movq %rcx, oRCX(%rdi)
movq %r8, oR8(%rdi)
movq %r9, oR9(%rdi) // 保存所有的通用寄存器到ucontext_t中

movq (%rsp), %rcx //
movq %rcx, oRIP(%rdi) // 通过上述分析,我们知道当前rsp里保存的是函数的返回地址,将其保存到ucontext_t中
leaq 8(%rsp), %rcx /* Exclude the return address. */
movq %rcx, oRSP(%rdi) // 将当前函数的rsp保存起来,注意这里+8是为了跳过刚才的函数返回地址.
...
leaq oFPREGSMEM(%rdi), %rcx // 保存浮点计算相关寄存器
movq %rcx, oFPREGS(%rdi)
/* Save the floating-point environment. */
fnstenv (%rcx)
fldenv (%rcx)
stmxcsr oMXCSR(%rdi)

/* Save the current signal mask with
rt_sigprocmask (SIG_BLOCK
, NULL, set,_NSIG/8). */
/* 保存当前的信号掩码,这里通过rt_sigprocmask系统调用实现的 */
leaq oSIGMASK(%rdi), %rdx // 通过rdx传递第3个参数,即ucontext中uc_sigmask的地址
xorl %esi,%esi // 第2个参数为NULL
#if SIG_BLOCK == 0
xorl %edi, %edi
#else
movl $SIG_BLOCK, %edi // 第一个参数为SIG_BLOCK
#endif
movl $_NSIG8,%r10d // 第4个参数
movl $__NR_rt_sigprocmask, %eax // 调用系统调用rt_sigprocmask
syscall
cmpq $-4095, %rax /* Check %rax for error. */
jae SYSCALL_ERROR_LABEL /* Jump to error handler if error. */

/* All done, return 0 for success. */
xorl %eax, %eax // 系统调用成功返回
ret
PSEUDO_END(__getcontext)

2. 设置上下文:

setcontext函数能够还原之前的ucontext_t中的状态.

函数原型:
1
int setcontext(const ucontext_t *ucp);
实现详解:
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
ENTRY(__setcontext)
/* Save argument since syscall will destroy it. */
pushq %rdi // rdi即我们传递的ucontext_t,将其保存到栈里,因为后面系统调用会破坏rdi,我们先保存起来
cfi_adjust_cfa_offset(8) //这是汇编指令,用于实现cfi功能,与我们讨论的内容无关可以不用关心,如果感兴趣可以看下面的文章了解:
https://stackoverflow.com/questions/51962243/what-is-cfi-adjust-cfa-offset-and-cfi-rel-offset

https://blog.csdn.net/pwl999/article/details/107569603

/* Set the signal mask with
rt_sigprocmask (SIG_SETMASK, mask, NULL, _NSIG/8). */
/* 设置ucontext_t中的信号掩码*/
leaq oSIGMASK(%rdi), %rsi //将之前保存的信号掩码设置到rsi即rt_sigprocmask第2个参数
xorl %edx, %edx
movl $SIG_SETMASK, %edi
movl $_NSIG8,%r10d
movl $__NR_rt_sigprocmask, %eax
syscall
/* Pop the pointer into RDX. The choice is arbitrary, but
leaving RDI and RSI available for use later can avoid
shuffling values. */
popq %rdx // 还原之前保存的ucontext_t
cfi_adjust_cfa_offset(-8)
cmpq $-4095, %rax /* Check %rax for error. */
jae SYSCALL_ERROR_LABEL /* Jump to error handler if error. */

/* Restore the floating-point context. Not the registers, only the
rest. */
movq oFPREGS(%rdx), %rcx //恢复之前的浮点寄存器
fldenv (%rcx)
ldmxcsr oMXCSR(%rdx)


/* Load the new stack pointer, the preserved registers and
registers used for passing args. */
cfi_def_cfa(%rdx, 0)
cfi_offset(%rbx,oRBX)
cfi_offset(%rbp,oRBP)
cfi_offset(%r12,oR12)
cfi_offset(%r13,oR13)
cfi_offset(%r14,oR14)
cfi_offset(%r15,oR15)
cfi_offset(%rsp,oRSP)
cfi_offset(%rip,oRIP)

movq oRSP(%rdx), %rsp //还原保存的rsp
movq oRBX(%rdx), %rbx //还原之前保存的rbx
movq oRBP(%rdx), %rbp //还原之前保存的rbp和其它通用寄存器
movq oR12(%rdx), %r12
movq oR13(%rdx), %r13
movq oR14(%rdx), %r14
movq oR15(%rdx), %r15
...
/* The following ret should return to the address set with
getcontext. Therefore push the address on the stack. */
movq oRIP(%rdx), %rcx //将原来保存的rip压入栈中
pushq %rcx

movq oRSI(%rdx), %rsi
movq oRDI(%rdx), %rdi
movq oRCX(%rdx), %rcx
movq oR8(%rdx), %r8
movq oR9(%rdx), %r9

/* Setup finally %rdx. */
movq oRDX(%rdx), %rdx //恢复原来的rdx

/* End FDE here, we fall into another context. */
cfi_endproc
cfi_startproc

/* Clear rax to indicate success. */
xorl %eax, %eax
ret // ret指令会将之前`pushq %rcx`压入栈中的old rip弹出执行,这样就执行回之前上下文的指令了
PSEUDO_END(__setcontext)

下面的图示详细展示了执行setcontext后的栈布局:

setcontext返回

一个例子

下面我们通过getcontext, setcontext来实现一个示例直观理解一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <ucontext.h>

int main()
{
ucontext_t uc;

getcontext(&uc); // 保存当前上下文
printf("hello the world\r\n");
sleep(1);
setcontext(&uc); // 还原之前上下文,代码又执行到printf了.
return 0;
}

执行上面代码会看到反复打印”hello the world”

1
2
3
4
5
6
7
安哥6@ubuntu:~$ ./a.out
hello the world
hello the world
hello the world
hello the world
hello the world
...

上面的两个函数只实现了简单的保存当前上下文和设置上下文的功能,要实现更复杂的协程切换,我们需要灵活地创建上下文和在两个上下文之间切换,因此makecontext, swapcontext就派上用场了:

3. makecontext

makecontext能够让我们设置栈的位置,要执行的函数即要传递的参数,这样就具备了创建协程运行环境的功能.

函数原型
1
void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...);
  • ucp: 上下文结构
  • func: 关联的函数
  • argc: 关联的函数的参数个数
  • …: 关联的参数
函数详解
  • uc_link解释: 当我们创建的ucontext_t中的函数执行结束后,应该切换到哪里去?为了能够指明这个信息,ucontext_t中有一个uc_link指针,它指向另外一个ucontext_t结构,这就是uc_link的作用.

  • 跳板代码: (__start_context函数)
    由跳板代码完成uc_link的加载和切换,这样ucontext_t结束时就能切换到uc_link.
    跳板代码放在ucontext_t函数栈的最顶端,这样ucontext_t结束时就能通过ret弹出并执行了.

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
__makecontext (ucontext_t *ucp, void (*func) (void), int argc, ...)
...

/* Generate room on stack for parameter if needed and uc_link. */
sp = (greg_t *) ((uintptr_t) ucp->uc_stack.ss_sp
+ ucp->uc_stack.ss_size); // 首先设置sp的值,由我们传入的ucp中的sp和大小相加
sp -= (argc > 6 ? argc - 6 : 0) + 1; // 如果参数大于6个,则需要额外开辟栈空间,额外再加1是要为uc_link预留空间
/* Align stack and make space for trampoline address. */
sp = (greg_t *) ((((uintptr_t) sp) & -16L) - 8);  //sp字节对齐并为跳板代码预留空间.


idx_uc_link = (argc > 6 ? argc - 6 : 0) + 1; // 根据参数个数计算uc_link在sp中的位置

/* Setup context ucp. */
/* Address to jump to. */
ucp->uc_mcontext.gregs[REG_RIP] = (uintptr_t) func; //保存func地址到rip
/* Setup rbx.*/
ucp->uc_mcontext.gregs[REG_RBX] = (uintptr_t) &sp[idx_uc_link]; //rbx设置uc_link在sp中的地址
ucp->uc_mcontext.gregs[REG_RSP] = (uintptr_t) sp; //保存sp

...
sp[0] = (uintptr_t) &__start_context; //跳板代码地址,切换上下文时通过跳板代码实现
sp[idx_uc_link] = (uintptr_t) ucp->uc_link; //存储uc_link地址

va_start (ap, argc);

/*下面代码是将要传递的参数保存起来*/
for (i = 0; i < argc; ++i)
switch (i)
{
case 0:
ucp->uc_mcontext.gregs[REG_RDI] = va_arg (ap, greg_t);
break;
case 1:
ucp->uc_mcontext.gregs[REG_RSI] = va_arg (ap, greg_t);
break;
case 2:
ucp->uc_mcontext.gregs[REG_RDX] = va_arg (ap, greg_t);
break;
case 3:
ucp->uc_mcontext.gregs[REG_RCX] = va_arg (ap, greg_t);
break;
case 4:
ucp->uc_mcontext.gregs[REG_R8] = va_arg (ap, greg_t);
break;
case 5:
ucp->uc_mcontext.gregs[REG_R9] = va_arg (ap, greg_t);
break;
default:
/* Put value on stack. */
sp[i - 5] = va_arg (ap, greg_t); //大于6个参数用栈保存
break;
}
va_end (ap);

4. swapcontext

将当前上下文保存并切换到另一个上下文中

函数原型
1
int swapcontext(ucontext_t *oucp, const ucontext_t *ucp);

详细实现

swapcontext的前半部分和getcontext类似保存当前上下文,后半部分和setcontext类似,因此只分析关键部分

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
    /* Load the new stack pointer and the preserved registers.  */
movq oRSP(%rdx), %rsp /*还原通用寄存器*/
movq oRBX(%rdx), %rbx
movq oRBP(%rdx), %rbp
movq oR12(%rdx), %r12
movq oR13(%rdx), %r13
movq oR14(%rdx), %r14
movq oR15(%rdx), %r15
...
/* The following ret should return to the address set with
getcontext. Therefore push the address on the stack. */
movq oRIP(%rdx), %rcx // 将新context_t中的rip放入栈中,这样下面的`ret`指令就会弹出并执行了
pushq %rcx

/* Setup registers used for passing args. */
movq oRDI(%rdx), %rdi
movq oRSI(%rdx), %rsi
movq oRCX(%rdx), %rcx
movq oR8(%rdx), %r8
movq oR9(%rdx), %r9

/* Setup finally %rdx. */
movq oRDX(%rdx), %rdx

/* Clear rax to indicate success. */
xorl %eax, %eax
ret // 从栈中弹出新ucontext_t的`rip`并执行
swapcontext后的栈布局

swapcontext

最后我们看一下当切换后的ucontext_t执行完后如何通过跳板代码执行到uc_link.

跳板代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ENTRY(__start_context)
/* This removes the parameters passed to the function given to
'makecontext' from the stack. RBX contains the address
on the stack pointer for the next context. */
movq %rbx, %rsp // 取出uc_link地址

/* Don't use pop here so that stack is aligned to 16 bytes. */
movq (%rsp), %rdi // 将uc_link的值放入rdi,准备setcontext
testq %rdi, %rdi // 如果uc_link是NULL,则退出程序
je 2f /* If it is zero exit. */

call __setcontext // 调用__setcontext完成上下文设置,uc_link已放入rdi,即第一个参数.
/* If this returns (which can happen if the syscall fails) we'll
exit the program with the return error value (-1). */
movq %rax,%rdi

2:
call HIDDEN_JUMPTARGET(exit)
/* The 'exit' call should never return. In case it does cause
the process to terminate. */
L(hlt):
hlt
END(__start_context)

C语言中支持golang中的协程

C语言协程库实现说明

在C语言中一步一步实现一个完整的协程框架.

代码实现

1. 当前支持的功能概览

1.1 创建任意数量协程并在协程中yield

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
#include <stdio.h>
#include <stdlib.h>

#include <pthread.h>

#include "gtest/gtest.h"

#include "coroutine.h"
#include "asyncio.h"

static int g_run_sums = 0;
static pthread_mutex_t g_lock = PTHREAD_MUTEX_INITIALIZER;

static void co(void *args)
{
int num = *((int *)args);

pthread_mutex_lock(&g_lock);
g_run_sums += num; // 每个协程分别递增全局变量
pthread_mutex_unlock(&g_lock);

printf("coroutine:%d begin...\r\n", num);
coroutine_yield();
printf("coroutine:%d ended...\r\n", num);
}

TEST(coroutine_create, three_cos_run_success)
{
int a = 1, b = 2, c = 3; //a, b, c三个协程依次对全局变量g_run_sums增加1,2,3
coroutine_init();
coroutine_create(co, (void*)&a);
coroutine_create(co, (void*)&b);
coroutine_create(co, (void*)&c);

coroutine_loop();

EXPECT_EQ(g_run_sums, 6); // 最终全局变量为6
}

1.2 创建2个协程,其中一个睡眠100ms

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
  
#include <stdio.h>
#include <stdlib.h>

#include <pthread.h>

#include "gtest/gtest.h"

#include "coroutine.h"
#include "asyncio.h"

static int seq = 0;
static int co_seq[2] = {0};

static void co_sleep(void *args)
{
printf("co sleep begin.\r\n");
asyncio_sleep(100); // 调用asyncio api睡眠100ms.
co_seq[seq++] = 100;
printf("co sleep end.\r\n");
}

static void co_nosleep(void *args)
{
printf("co no sleep begin.\r\n");
co_seq[seq++] = 200;
printf("co no sleep end.\r\n");
}

TEST(coroutine_run, co_sleep)
{
coroutine_init();
coroutine_create(co_sleep, NULL);
coroutine_create(co_nosleep, NULL);

coroutine_loop();

EXPECT_EQ(co_seq[0], 200); //验证未睡眠协程先完成了执行
EXPECT_EQ(co_seq[1], 100);
}

2. COROUTINE状态

corouting有3种状态, RUNNALBE, RUNNING, WAITING.

  • WAITING: corouting暂停并等待一些条件以继续运行.比如:sleep, 系统调用,同步操作(原子或锁操作),这种延迟是性能差的根源.
  • RUNNABLE: corouting具备运行条件正在等待分配processor以执行指令
  • RUNNING: corouting已经分配到processor,并正在上面执行指令

3. 调度器实现

  • processor_t: 管理一个实际的os线程,内部使用队列维护分配给它的coroutine,使用epoll进行事件循环.
  • processors_t: 全局processor_t管理器,创建时会按照实际的cpu个数创建对应的processor_t, 它负责将新协程按照一定算法分配给某个processor_t.
    同时负责检测没有任何协程时退出进程.

3.1 主进程何时退出

当没有任何协程存在时,则退出主进程.

3.1.1 实现原理

模拟实现了Golang中的waitGroup, 用于等待所有协程退出.新协程创建会调用waitGroup_add,协程结束会调用waitGroup_del,当waitGroup空闲时
则说明所有协程都已经退出.

3.2 processor_t调度主循环处理

    1. 循环遍历coroutine就绪队列,依次运行coroutine.
    1. 如果没有就绪的coroutine且本地队列上coroutine个数为0,则进行步骤3,否则进行步骤4
    1. 通过条件变量等待分配新的coroutine,如果收到了条件变量且是退出指令,则进行步骤5,否则进行步骤1.
    1. 本地队列还有coroutine,但是coroutine都在等待事件,则进行事件循环以等待指定事件的到来,这样就会有coroutine就绪,进行步骤1.
    1. 退出主循环

3.3 上下文切换实现

3.3.1 原理

corouting在用户态进行上下文切换,上下文主要包括:堆栈,寄存器(IP, SP等).
上下文切换主要通过<ucontext.h>中定义的getcontext, setcontext, makecontext, swapcontext实现.

3.3.2 上下文切换时机

  • corouting主动调用coroutine_yield(),如果有其它待运行的coroutine则主动让出processor_t
  • 协程中调用了协程库asyncio API,则由API选择合适的时机进行上下文切换,如调用阻塞API,如corouting_sleep.
  • 如果你在协程中执行cpu密集型操作或直接调用阻塞的C api,那么会影响当前processor的调度和运行.

3.3.3 堆栈使用

  • 每个processor_t维护1M的堆栈空间M
  • 协程刚创建时为RUNNABLE状态,此时直接使用M作为堆栈,当协程需要放权时保存当前堆栈到协程自己的空间M0
  • 协程恢复运行时,将保存的堆栈M0还原到M中继续运行

这样每个协程最大都可以有1M的堆栈空间,且堆栈空间能够按需分配,每个processor_t上堆栈的消耗为所有协程
实际使用的堆栈内存+1M.

如果不这样实现,每个协程都需要初始分配1M空间,消耗为协程个数*1M.

4. 异步操作协程库asyncio实现

  • asyncio提供一系列api用于在协程环境中编写并发代码.
  • asyncio是coroutine框架提供的api可以用于实现高性能网络服务器,数据库连接库,分布式任务队列等.
  • asyncio适合IO密集型和高级别的结构化网络程序

4.1 当前支持的API

  • coroutine_sleep(long delay_ms): 当前协程休眠指定ms.
  • coroutine_yield(): 当前协程主动放权给其它就绪协程,由调度器选择合适时机再重新调度.

5. 代码说明

5.1 编译代码

1
2
3

cmake -H. -Bbuild
cmake --build ./build

5.2 运行测试

1
2
cd build
ctest --verbose

记一次惨痛的编程考试经历

一次惨痛的编程考试经历

最近一个月,一直在刷leetcode来准备公司的上机编程考试,平均每天刷3道题左右,主要是中等题型,偶尔也刷困难题.
按照题目的类型在刷,如分治,递归回溯,二叉树,dfs,bfs,dp,前缀和这些.自以为准备的很充分,结果还是挂了.
心中的郁闷可想而知,俗话说,”大痛者必有大志”,从成长型思维来看,还是很有必要总结一下失败的经验的.
先来回顾一下考试题目:
1.一道系统设计题目,主要考查如何组织代码实现不同的排序策略,整体上比较简单,也做出来了
2.一道深度优先遍历题目,本来以为能轻松做出,可是没有AC,也一直没有想出原因,也因此而挂了
3.二维前缀和+合并区间,只想到了用二维前缀和,后面合并区间没有优化,造成超时

其中第2题还一直怀疑用例有问题,一直没有发现代码中的bug.直到几天后,才发现问题.代码其实仔细推敲就会发现不符合题目要求,没有考虑清楚  
叶子节点的情形.

总结了下失利原因有以下几点:

  1. 准备考试要首先搞清楚考的是什么?算法一般不会考太难的,重点还是在于有没有好的编程习惯.编程习惯包括如何审题分析线索,如何设计用例,如何调试,如何熟练的使用语言等.
  2. 体会到了测试驱动开发的重要性,如何根据题目设计有效的用例和考虑清楚所有边界条件.
  3. 之前刷题只注重有没有解题思路和题目的难度上,用例不过也是直接看失败用例,造成思维逻辑有漏洞
  4. 完全没有练习如何对照题目的限制条件设计用例,如何调试代码验证符合预期,一味地追求刷题数量,忽略了本质.
  5. 做题不纯粹是速度,更重要的是准确,如果代码有bug和没有代码是一样的.

归并排序

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

def merge_sort(a):
def merge_array(a, i, j):
if i >= j:
return a

def merge(a, left_i, left_j, right_i, right_j):
new_a = []
i, j = left_i, right_i
while i <= left_j and j <= right_j:
if a[i] <= a[j]:
pos = i
i += 1
else:
pos = j
j += 1
new_a.append(a[pos])

if i <= left_j:
new_a.extend(a[i:left_j+1])

if right_i <= right_j:
new_a.extend(a[j:right_j+1])

a[left_i:right_j+1] = new_a

mid = i + (j - i) // 2
merge_array(a, i, mid)
merge_array(a, mid+1, j)
merge(a, i, mid, mid+1, j)
return a

return merge_array(a, 0, len(a)-1)

if __name__ == "__main__":
print(merge_sort([1, 3, 2, 4, 6, 8, 7]))
print(merge_sort([8]))
print(merge_sort([9, 8, 7, 4, 3, 2, 0]))
print(merge_sort([9, 10, 12, 14, 13, 22, 100]))

查找第k大元素

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

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p215 file
Author: zhangxiaoan 00565442
Create: 2021/4/30 16:19
"""

def top_k(nums, k):
def partition(nums, left, right):
if left >= right:
return 1

sel = nums[right]
pos = left-1
start = left
while start < right:
if nums[start] > sel:
pos += 1
if start != pos:
tmp = nums[pos]
nums[pos] = nums[start]
nums[start] = tmp
start += 1
pos += 1
nums[pos], nums[right] = sel, nums[pos]
return pos - left + 1

def quick_find(nums, left, right, k):
m = partition(nums, left, right)
if m == k:
return nums[left + m - 1]

if m > k:
return quick_find(nums, left, left + m - 2, k)
else:
return quick_find(nums, left + m, right, k - m)
return quick_find(nums, 0, len(nums)-1, k)

if __name__ == "__main__":
print(top_k([1], 1))
print(top_k([3, 1, 2, 4], 2))
print(top_k([3, 2, 1, 5, 6, 4], 2))
print(top_k([5, 2, 4, 1, 3, 6, 0], 4))

给表达式添加运算符

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
"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p282 file
Author: zhangxiaoan 00565442
Create: 2021/4/29 9:25
"""


def add_operators(num, target):
n = len(num)
ans = []

def gen_expr(num, index, expr, prev_op, prev_value, value):
nonlocal n, target, ans

start = num[index]
end = index
while end < n:
val = int(num[index:end + 1])
expr.append(prev_op)
expr.append(num[index:end + 1])


if prev_op == '+':
next_val = value + val
if prev_op == '-':
next_val = value - val
if prev_op == '*':
next_val = value + prev_value * val

if end == n - 1:
if next_val == target:
ans.append("".join(expr[1:]))

expr.pop()
expr.pop()
return

if prev_op == '+':
gen_expr(num, end + 1, expr, "*", val, value)
elif prev_op == '-':
gen_expr(num, end + 1, expr, "*", -val, value)
else:
gen_expr(num, end + 1, expr, "*", prev_value * val, value)


gen_expr(num, end + 1, expr, "+", 0, next_val)
gen_expr(num, end + 1, expr, "-", 0, next_val)
expr.pop()
expr.pop()

if start == '0':
break

end += 1

gen_expr(num, 0, [], "+", 0, 0)
return ans


if __name__ == "__main__":
print(add_operators("123", 6))
print(add_operators("232", 8))
print(add_operators("105", 5))
print(add_operators("00", 0))
print(add_operators("3456237490", 9191))
print(add_operators("134562379", 134562379))
print(add_operators("123456789", 45))

查找两个有序数组的中位数


def find_media_sorted_arrays(nums1, nums2):
    m, n = len(nums1), len(nums2)

    def find_kth(nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        if m < n:
            return find_kth(nums2, nums1, k)

        if n == 0:
            return nums1[k-1] 

        if k == 1:
            return min(nums1[0], nums2[0])

        m2 = min(n, (k+1)//2)
        m1 = k - m2
        if nums1[m1-1] < nums2[m2-1]:
            return find_kth(nums1[m1:], nums2, k - m1)
        else:
            return find_kth(nums1, nums2[m2:], k - m2)
        

    total = m + n
    if total % 2 != 0:
        return find_kth(nums1, nums2, total//2 + 1)
    else:
        return (find_kth(nums1, nums2, total//2) + find_kth(nums1, nums2, total//2 + 1))/2

    
if __name__ == "__main__":
    print(find_media_sorted_arrays([1, 3], [2]))
    print(find_media_sorted_arrays([1, 2], [3, 4]))