ggaaooppeenngg

为什么计算机科学是无限的但生命是有限的

timer 在 Golang 中可以有多精确？

发表于 更新于 Disqus：

本文主要讨论 timer heap 在 Go 中的管理，以及运行时对于时间是如何获取的问题，从而引出一个结论，我们对于 timer 的准确度可以有多大的依赖。

首先我们看一下 Go 是如何获取时间的，找到time.Now, 发现最终调用的是下面这个汇编函数。

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

// 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是如何管理的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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 是时间戳。

1
2
3
4
5
6
7
8
9
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函数，他是整个计时器开始的入口，当然本身只是加了锁。

1
2
3
4
5
6
func addtimer(t *timer) {
        lock(&timers.lock)
        addtimerLocked(t)
        unlock(&timers.lock)
}

再看addtimerLocked可以看到就是入 heap 的过程了。

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
// 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 的定义如下。

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
// 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 按点执行，当然如果你的间隔离谱的大的话其实就可以忽略这方面的影响了：)


参考链接：

1.  Go Assembly https://golang.org/doc/asm
2.  http://stackoverflow.com/questions/19938324/what-are-vdso-and-vsyscall
3.  http://www.win.tue.nl/~aeb/linux/lk/lk-4.html
4.  http://book.douban.com/subject/3652388/
5.  http://linuxmogeb.blogspot.com/2013/10/how-does-clockgettime-work.html
6.  时钟源 http://blog.csdn.net/droidphone/article/details/7975694
7.  Go 源码剖析 https://github.com/qyuhen/book/blob/master
    /Go%201.5%20%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.pdf
8.  带超时的信号量的实现 http://lxr.free-electrons.com/source/kernel/locking/semaphore.c#L204
9.  内核的时钟源 http://blog.csdn.net/droidphone/article/details/7975694