本文主要讨论timer heap在Go中的管理,以及运行时对于时间是如何获取的问题,从而引出一个结论,我们对于timer的准确度可以有多大的依赖.
首先我们看一下Go是如何获取时间的,找到time.Now,发现最终调用的是下面这个汇编函数.
// func now() (sec int64, nsec int32)
TEXT time·now(SB),NOSPLIT,$16
// Be careful. We're calling a function with gcc calling convention here.
// We're guaranteed 128 bytes on entry, and we've taken 16, and the
// call uses another 8.
// That leaves 104 for the gettime code to use. Hope that's enough!
// 这里只能保证调用gettime函数的时候有104个字节给这个函数作为栈
// 因为返回值用了16个字节,这个函数本身会用8个字节,到调用gettime的时候只剩104个字节可以用.
MOVQ runtime·__vdso_clock_gettime_sym(SB), AX
CMPQ AX, $0
JEQ fallback
MOVL $0, DI // CLOCK_REALTIME
LEAQ 0(SP), SI
CALL AX
MOVQ 0(SP), AX // sec
MOVQ 8(SP), DX // nsec
MOVQ AX, sec+0(FP)
MOVL DX, nsec+8(FP)
RET
fallback:
LEAQ 0(SP), DI
MOVQ $0, SI
MOVQ runtime·__vdso_gettimeofday_sym(SB), AX
CALL AX
MOVQ 0(SP), AX // sec
MOVL 8(SP), DX // usec
IMULQ $1000, DX
MOVQ AX, sec+0(FP)
MOVL DX, nsec+8(FP)
RET
第一行TEXT time·now(SB),NOSPLIT,$16, 其中time·now(SB)表示函数now的地址,NOSPLIT标志不依赖参数,$16表示返回的内容是16个字节,Go的汇编语法具体可以参考Go asm文档[1].
首先是取出__vdso_clock_gettime_sym(SB)(这是一个符号,指向的其实是clock_gettime函数,man clock_gettime可以看到glibc的定义)的地址,如果符号不为空的话就把栈顶的地址计算出来传入SI(LEA 指令). DI和SI分别是system call的前两个参数的寄存器,这个相当于调用clock_gettime(0,&ret). fallback分支是当对应的符号没有初始化就退而求其次调用gettimeofday(man gettimeofday 可以看到libc的定义)这个函数.
Go的函数调用确保会有至少128个字节的栈(注意不是goroutine的栈),具体可以参考runtime/stack.go里的_StackSmall,但是进入对应的c函数以后,栈的增长就不能够由Go控制了,所以剩下的104个字节要确保这个调用不会栈溢出.(不过一般不会,因为这两个获取时间的函数不复杂).
先说函数符号的事,查阅相关资料可以看出来,VDSO是Virtual Dynamic Shared Object,就是内核提供的虚拟的.so,这个.so文件不在磁盘上，而是在内核里头,映射到了用户空间. 具体细节可以看so上的一个回答[2].其中一个链接中有一些描述[3].
One way of obtaining a fast gettimeofday() is by writing the current time in a fixed place, on a page mapped into the memory of all applications, and updating this location on each clock interrupt.
These applications could then read this fixed location with a single instruction - no system call required.
Concerning gettimeofday(), a vsyscall version for the x86-64 is already part of the vanilla kernel.
Patches for i386 exist. (An example of the kind of timing differences: John Stultz reports on an experiment where he measures gettimeofday() and finds 1.67 us for the int 0x80 way, 1.24 us for the sysenter way, and 0.88 us for the vsyscall.)
简单来说就是一种加速系统调用的机制加兼容模式. 像gettimeofday这样的函数如果像普通系统调用一样的话,有太多的上下文切换,特别是一些频繁获取时间的程序,所以一般gettimeofday是通过这种机制调用的.单独在用户空间映射了一段地址,在里面的是内核暴露的一些系统调用,具体可能是syscall或者int 80或者systenter的方式,由内核决定更快的调用方式,防止出现glibc版本和kernel版本不兼容的问题.(vDSO是vsyscall的一个升级版本,避免了一些安全问题,映射不再静态固定).
从内核中可以看出获取系统调用是由时间中断更新的,其调用栈如下[5].
Hardware timer interrupt (generated by the Programmable Interrupt Timer - PIT)
-> tick_periodic();
-> do_timer(1);
-> update_wall_time();
-> timekeeping_update(tk, false);
-> update_vsyscall(tk);
update_wall_time使用的是时钟源(clock source)的时间,精度能达到ns级别.
但是一般Linux kernel的时间中断是100HZ,高的也有1000HZ的,也就是说这个时间一般是在10ms或者1ms中断处理时更新一次.
从操作系统的角度看时间粒度大概是ms级别.但是,这个只是一个基准值.每次获取时间的时候还是会取得时钟源
的时间（时钟源有很多种[9]，可能是硬件的计数器，也可能就是中断的jiffy，一般是可以达到ns）.获取时间的精度还是能到us和几百ns之间。
因为系统调用本身还要花时间，理论上更精确的时间就不是通过这个系统调用获得了，而是需要直接用汇编指令”rdtsc”读CPU的cycle来得到精确时间.
接下来说，获取时间的函数符号的寻找过程又涉及了ELF的一些内容,其实就是动态链接的过程,把.so中的函数符号的地址解析到并且存入函数指针中,比如__vdso_clock_gettime_sym,关于链接的内容可以阅读”程序员的自我修养”这本书[4].
其他函数例如TEXT runtime·nanotime(SB),NOSPLIT,$16也是类似的过程.这个函数就能获取时间.
看完时间获取的过程,再来看看Go运行时的部分,瞧瞧timer heap是如何管理的.
// Package time knows the layout of this structure.
// If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
// For GOOS=nacl, package syscall knows the layout of this structure.
// If this struct changes, adjust ../syscall/net_nacl.go:/runtimeTimer.
type timer struct {
i int // heap index
// Timer wakes up at when, and then at when+period, ... (period > 0 only)
// each time calling f(now, arg) in the timer goroutine, so f must be
// a well-behaved function and not block.
when int64
period int64
f func(interface{}, uintptr)
arg interface{}
seq uintptr
}
timer是以heap的形式管理的, heap是个完全二叉树, 用数组就可以存下,i是heap的index.
when是goroutine被唤醒的时间,period是唤醒的间隙,下次唤醒的时间是when+period,依次类推.
调用函数f(now, arg), now是时间戳.
var timers struct {
lock mutex
gp *g
created bool
sleeping bool
rescheduling bool
waitnote note
t []*timer
}
整个的timer heap由timers管理.gp 指向的是一个g的指针,也就是调度器当中的G结构,一个goroutine的状态维护的结构,指向的是时间管理器的单独的一个goroutine,这个不属于用户而是运行时启动的goroutine.(当然只有使用了timer才会启动,不然不会有这个goroutine).lock保证timers的线程安全.waitnote是一个条件变量.
看一下addtimer函数,他是整个计时器开始的入口,当然本身只是加了锁.
func addtimer(t *timer) {
lock(&timers.lock)
addtimerLocked(t)
unlock(&timers.lock)
}
再看addtimerLocked可以看到就是入heap的过程了.
// Add a timer to the heap and start or kick the timer proc.
// If the new timer is earlier than any of the others.
// Timers are locked.
func addtimerLocked(t *timer) {
// when must never be negative; otherwise timerproc will overflow
// during its delta calculation and never expire other runtime·timers.
if t.when < 0 {
t.when = 1<<63 - 1
}
t.i = len(timers.t)
timers.t = append(timers.t, t)
siftupTimer(t.i)
if t.i == 0 {
// siftup moved to top: new earliest deadline.
if timers.sleeping {
timers.sleeping = false
notewakeup(&timers.waitnote)
}
if timers.rescheduling {
timers.rescheduling = false
goready(timers.gp, 0)
}
}
if !timers.created {
timers.created = true
go timerproc()
}
}
先从下面的if !timers.created分支看起,如果timers对应没有创建就go一个timerproc, timeproc的定义如下.
// Timerproc runs the time-driven events.
// It sleeps until the next event in the timers heap.
// If addtimer inserts a new earlier event, addtimer1 wakes timerproc early.
func timerproc() {
timers.gp = getg()
for {
lock(&timers.lock)
timers.sleeping = false
now := nanotime()
delta := int64(-1)
for {
if len(timers.t) == 0 {
delta = -1
break
}
t := timers.t[0]
delta = t.when - now
if delta > 0 {
break
}
if t.period > 0 {
// leave in heap but adjust next time to fire
t.when += t.period * (1 + -delta/t.period)
siftdownTimer(0)
} else {
// remove from heap
last := len(timers.t) - 1
if last > 0 {
timers.t[0] = timers.t[last]
timers.t[0].i = 0
}
timers.t[last] = nil
timers.t = timers.t[:last]
if last > 0 {
siftdownTimer(0)
}
t.i = -1 // mark as removed
}
f := t.f
arg := t.arg
seq := t.seq
unlock(&timers.lock)
if raceenabled {
raceacquire(unsafe.Pointer(t))
}
f(arg, seq)
lock(&timers.lock)
}
if delta < 0 || faketime > 0 {
// No timers left - put goroutine to sleep.
timers.rescheduling = true
// 如果没有timers剩余,就让G进入sleep状态.
// goparkunlock的作用是解开G和M的联系,让goroutine sleep而M
// 寻找下一个G来执行.
goparkunlock(&timers.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
continue
}
// At least one timer pending. Sleep until then.
timers.sleeping = true
// 清零waitnote.
noteclear(&timers.waitnote)
unlock(&timers.lock)
// 调用M结构对应的OS-dependent, OS-thread的信号量让M进入sleep状态.
// 只会在超时的时候或者条件变量waitnote触发才会被唤醒.
notetsleepg(&timers.waitnote, delta)
}
}
timeproc的主体就是从最小堆中取出timer然后回调函数,如果period大于0就把timer的when修改并且存回heap并调整,如果小于0就直接删除(对应的分别是标准库的ticker和timer),进入OS信号量中睡眠等待下次处理,(当然可以被waitnote变量唤醒),这样一直循环,说白了就是靠信号量的超时机制来实现了运行时的sleep[8].然后当完全没有timer剩余的时候,G结构表示的goroutine进入睡眠状态,承载goroutine的M结构所代表的OS-thread会寻找其它可运行的goroutine执行.具体关于运行时调度的细节可以参考雨痕大叔的笔记[7].
看完这一路case,回到addtimerLocked,当加入一个新的timer时,会作依次检查,也就是说最新插入的timer是在堆顶的话,会唤醒睡眠的timergorountine开始从heap上检查过时的timer并执行.这里的唤醒和之前的睡眠是两种对应的状态timers.sleeping是进入了M的os信号量睡眠.timers.rescheduling是进入了G的调度睡眠,而M并没有睡眠,让G重新进入可运行状态.时间超时和新timer的加入,两者结合成为了timer运行时的驱动力.
看完了time的实现,再回过头来回答文章最初的问题”timer可以有多精确”,其实和两个原因有关,一个是操作系统本身的时间粒度,一般是us级别的,时间基准更新是ms级别的，时间精度能到us级别, 另外一个就是timer本身的goroutine的调度问题,如果运行时的负载过大或者操作系统本身的负载过大,会导致timer本身的goroutine响应不及时,导致timer触发并不及时,可能导致一个20ms的timer和一个30ms的timer之间像是并发的一样(这也是笔者碰到的问题,特别是一些被cgroup限制了的容器环境,cpu时间分配很少的条件下),所以有时候我们不能过分相信timer的时序来保证程序的正常运行.NewTimer的注释也强调了”NewTimer creates a new Timer that will send the current time on its channel after at least duration d.”,没有人能保证timer按点执行,当然如果你的间隔离谱的大的话其实就可以忽略这方面的影响了:)
```
参考链接:
- Go Assembly https://golang.org/doc/asm
- http://stackoverflow.com/questions/19938324/what-are-vdso-and-vsyscall
- http://www.win.tue.nl/~aeb/linux/lk/lk-4.html
- http://book.douban.com/subject/3652388/
- http://linuxmogeb.blogspot.com/2013/10/how-does-clockgettime-work.html
- 时钟源 http://blog.csdn.net/droidphone/article/details/7975694
- Go源码剖析 https://github.com/qyuhen/book/blob/maste/Go%201.5%20%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.pdfr
- 带超时的信号量的实现 http://lxr.free-electrons.com/source/kernel/locking/semaphore.c#L204
- 内核的时钟源 http://blog.csdn.net/droidphone/article/details/7975694
有疑问加站长微信联系（非本文作者）
