Zephyr内核Timeout模块简介

Creative Commons
本作品采用知识共享署名
发表于 | 分类于 | | 阅读次数：

本文分析说明Zephyr内核的Timeout模块。

在Zephyr Tick Clock简介一文中分析tick clock的工作原理提到每个tick中断的时候将会调用z_clock_announce，通知现在已经走了一个tick了，同时也提到了tick clock是sheep time和wait timeout的基础设施，本文将分析Zephyr的Timeout模块，说明Zephyr如何管理timeout对象，以及如果驱动timeout。
Timeout本身会去驱动Zephyr内核的时间片，本文不对该部分进行分析。同时我们继续以tickless kernel既一个tick一次中断来分析。

Timeout分析

Timeout节点

Zephyr的Timeout模块管理的是一组struct _timeout节点，节点内描述该节点要在多少个tick后超时和超时后要调用的callback

1
2
3
4
5
6
7
typedef void (*_timeout_func_t)(struct _timeout *t);

struct _timeout {
	sys_dnode_t node;
	s32_t dticks;			//超时tick
	_timeout_func_t fn;		//超时后调用fn
};

Timeout实现

Timeout模块的代码在kernel/timeout.c中，Timeout模块的管理实现如下图:
timeout
Timeout本身维护一个双向链表，链表的timeout_list, 链表内等待timeout的节点已等待的tick数从小到大排序，某一个节点要等待的dick数是从链表的头一直累加到该节点:例如
T1等待的时间是T1->dticks,
T2等待的时间是T2->dticks+T1->dticks
T3等待的时间是T3->dticks+T2->dticks+T1->dticks
这样做的好处是，每次tick中断到后只用更新第一个节点的dticks，就等于对所有节点需要等待的ticks的更新，而不用遍历整个链表，这样可以有效缩短tick中断的时间。

分析前提:
我们任然以非tickless kernel(1个tick一次中断)为前提进行分析，所以不在tick中断内时announce_remaining永远为0，z_clock_elapsed()也会返回为0，进一步的elapsed()返回值也会退化为0

1
2
3
4
static s32_t elapsed(void)
{
	return announce_remaining == 0 ? z_clock_elapsed() : 0;
}

当有使用者需要进行timeout时通过z_add_timeout将timeout的节点加入到链表。

z_add_timeout

从下面的流程分析可以看到，插入一个timeout节点时，会从头开始遍历链表，刨除比自己小的节点等待的tick数，然后让自己的后续节点刨除该节点要等待的tick数(图中红色部分)

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
void z_add_timeout(struct _timeout *to, _timeout_func_t fn, s32_t ticks)
{
	//注册回调
	to->fn = fn;
	//必须等待至少一个tick
	ticks = MAX(1, ticks);

	LOCKED(&timeout_lock) {
		struct _timeout *t;

		to->dticks = ticks + elapsed();		//elapsed()为0，to->dticks为ticks
		//开始遍历链表，将to按照ticks从小到大的顺序排列
		for (t = first(); t != NULL; t = next(t)) {
			__ASSERT(t->dticks >= 0, "");


			if (t->dticks > to->dticks) {
				//更新插入节点后一个节点的等待ticks数,
				t->dticks -= to->dticks;
				sys_dlist_insert(&t->node, &to->node);
				break;
			}

			//减去前面节点的tick数
			to->dticks -= t->dticks;
		}

		//如果链表为NULL，者直接将节点放入链表的head
		if (t == NULL) {
			sys_dlist_append(&timeout_list, &to->node);
		}

		//该流程对非tickless kernel无效
		if (to == first()) {
			z_clock_set_timeout(next_timeout(), false);
		}
	}
}

添加了timeout对象也可以通过z_abort_timeout移除对应的timeout对象。

z_abort_timeout

由于移除节点会将tick数一并移除，所以要将移除的tick数还到后续节点内(图中绿色部分)

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
int z_abort_timeout(struct _timeout *to)
{
	int ret = -EINVAL;

	LOCKED(&timeout_lock) {
		//在链表中找到要移除的节点
		if (sys_dnode_is_linked(&to->node)) {
			//移除该节点
			remove_timeout(to);
			ret = 0;
		}
	}

	return ret;
}

static void remove_timeout(struct _timeout *t)
{
	//如果要移除的节点有后续节点，需要将要移除的节点tick数补回到后续节点去
	if (next(t) != NULL) {
		next(t)->dticks += t->dticks;
	}
	//从链表中移除节点
	sys_dlist_remove(&t->node);
}

Timeout更新

每次tick中断发生时，就会驱动引擎z_clock_announce，在z_clock_announce内会对链表的tick数进行更新并检查，如果发现节点超时将移除节点并进行callback
对于非tickless kernel每一个tick中断都会调用z_clock_announce，传入的参数为ticks = 1，代码分析如下

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
void z_clock_announce(s32_t ticks)
{
	k_spinlock_key_t key = k_spin_lock(&timeout_lock);

	announce_remaining = ticks;

	//第一个节点超时，移除第一个节点循环检查后面的节点是否超时
	//可能存在多个节点同一时刻超时的情况
	while (first() != NULL && first()->dticks <= 1) {
		struct _timeout *t = first();
		int dt = t->dticks;

		//系统tick累加
		curr_tick += dt;

		//announce_remaining被变为0
		announce_remaining -= dt;

		//移除超时节点
		t->dticks = 0;
		remove_timeout(t);

		//超时节点回调z_add_timeout的fn
		k_spin_unlock(&timeout_lock, key);
		t->fn(t);
		key = k_spin_lock(&timeout_lock);
	}

	//如果之前有节点超时announce_remaining会被清0，这里操作无意义
	//如果之前没有节点超时，这里对链表的超时tick进行更新
	if (first() != NULL) {
		first()->dticks -= announce_remaining;
	}

	//统tick累加
	curr_tick += announce_remaining;
	announce_remaining = 0;

	//对于非tickless kernel, z_clock_set_timeout不会生效
	z_clock_set_timeout(next_timeout(), false);

	k_spin_unlock(&timeout_lock, key);

其它API

下面介绍一些在非tickless kernel下使用的其它API，原理比较简单不再展开分析，有兴趣可以翻阅代码
s32_t z_timeout_remaining(struct _timeout *timeout) 获取指定timeout还剩多少tick超时
s64_t z_tick_get(void) 返回系统运行了多少个tick，也就是curr_tick
u32_t z_tick_get_32(void) 返回系统运行了多少个tick，取curr_tick低32位

Tickless Kernel

在Tickless kernel下，会在每次Tick中断时通过timeout的next_timeout计算下一次超时要多少个tick，并以该时间设置systick，让其在超时的时候才产生中断，这也将大大减少tick中断的上下文切换，之后会有文章专门分析该部分流程。

关于k_time

在zephyr内核中提供了一个k_timer, kernel/timer.c， 其实就是包装了timeout模块，因此使用k_timer要特别注意过期回调函数，因为k_timer注册的过期回调函数最后是通过timeout模块在tick isr中执行，如果执行时间过长会影响zephyr的tick调度。