2.6.4.3 带宽控制 - 定时器

带宽控制器中有两个定时器，分别是 period_timer 与 slack_timer, 前者用来周期性地更新带宽时间并对cfs_rq解挂，后者用来酌情回收已经分配给下属cfs_rq的时间，本节我们将详细探讨他们的实现原理。

定时器的初始化发生在整个带宽控制器的初始化阶段：

/* file: kernel/sched/fair.c */
void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {
    raw_spin_lock_init(&cfs_b->lock);
    cfs_b->runtime = 0;
    /* 没有限额 */
    cfs_b->quota = RUNTIME_INF;
    /* 初始化周期为100ms */
    cfs_b->period = ns_to_ktime(default_cfs_period());

    /* 初始化 throttled 列表 */
    INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
    /* 初始化 period timer */
    hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED);
    cfs_b->period_timer.function = sched_cfs_period_timer;

    /* 初始化slack timer */
    hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
    cfs_b->slack_timer.function = sched_cfs_slack_timer;
    cfs_b->slack_started = false;
}

该函数在初始化任务组时被调用，可以看到两个定时器的回调函数分别是 sched_cfs_period_timer 与 sched_cfs_slack_timer, 这里我们先看前者。

/* file: kernel/sched/fair.c */

/* period
 * timer的回调函数，在cfs_bandwidth的初始化函数中注册，然后被定时器周期性调用 */
static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer) {
    struct cfs_bandwidth *cfs_b =
        container_of(timer, struct cfs_bandwidth, period_timer);
    unsigned long flags;
    int overrun;
    int idle = 0;
    int count = 0;

    raw_spin_lock_irqsave(&cfs_b->lock, flags);
    /* 函数的主体逻辑需要完成两件事情：
     * 1. 将定时器的过期时间往后推cfs_b->period这么长的时间，因为这里已经在处理当前周期的时间分配了，推移之后的过期时间就是下一个周期的结束时间。该动作通过函数hrtimer_forward_now完成；
     * 2. 为任务组分配带宽时间，并且解挂当前任务组中所有挂起的队列。该部分逻辑通过函数do_sched_cfs_period_timer完成；
     *
     * 第一件事还好，但第二件事可能需要花费一定时间。而任务组的period与quota是用户可以设置的量，如果用户将period设置的太小，那么极有可能在某些情况下导致上述两件事情办完之后，当前周期又已经过完了。
     *
     * 这里通过一个for循环来检测这种情况，如果连续3次都没有在当前周期内完成操作，则系统就对period与quota进行扩充，将二者都scale为原来的两倍。
     *
     * 注意：period有一个上限，就是常量max_cfs_quota_period所定义的1s
     * */
    for (;;) {
        /* 函数hrtimer_forward_now将定时器的过期时间重置为当前时间加上cfs_b->period的那个时间点。返回值overrun表示从上个过期时间点开始算，需要多少个period的时间才能再次将过期时间推到当前时间以后。如下图所示：
         * last expired               now
              |                        |
         * ---|------|------|------|------|---> time
         *    |-->p<-| p: period
         *    |-------->overrun = 4<------|
         *
         * 如果定时器上一次的到期时间还没有到，则说明当前周期还没有结束，函数不会做任何更新，返回值overrun=0.
         * */
        overrun = hrtimer_forward_now(timer, cfs_b->period);

        /* overrun==0表示当前周期还没有结束，退出循环。
         * 如果period的时长合理，则通常应该在第二次循环时发生这种情况，表示第一次循环时已经顺利完成工作了。
         */
        if (!overrun)
            break;

        /* 为任务组重置带宽时间并解挂被挂起的列表。返回1表示当前进程组还没有throttle任何cfs_rq
         */
        idle = do_sched_cfs_period_timer(cfs_b, overrun, flags);

        /* 如果经过多次循环都还没有成功地为任务组配置好带宽时间，则说明当前周期太短了，对period与quota进行scale
         */
        if (++count > 3) {
            u64 new, old = ktime_to_ns(cfs_b->period);

            new = old * 2;
            /* 如果没有超出period的最大限制（1s），则将period与quota的时长都加倍。
             * 加倍的原因见：https://github.com/torvalds/linux/commit/4929a4e6faa0f13289a67cae98139e727f0d4a97
             */
            if (new < max_cfs_quota_period) {
                cfs_b->period = ns_to_ktime(new);
                cfs_b->quota *= 2;
            }

            /* 扩容之后将重置计数器 */
            count = 0;
        }
    }
    if (idle)
        cfs_b->period_active = 0;
    raw_spin_unlock_irqrestore(&cfs_b->lock, flags);

    return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
}

该函数相当于是一个控制层，保证带宽的period与quota的大小合适，并且确保实际工作顺利完成，函数 do_sched_cfs_period_timer 可以精简为如下逻辑：

/* file: kernel/sched/fair.c */

static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun,
                                     unsigned long flags) {
    int throttled;

    throttled = !list_empty(&cfs_b->throttled_cfs_rq);

    /* 重置带宽时间：cfs_b->runtime = cfs_b->quota */
    __refill_cfs_bandwidth_runtime(cfs_b);

    /* 没有cfs_rq被挂起，已经重置了带宽时间，返回即可 */
    if (!throttled) {
        cfs_b->idle = 1;
        return 0;
    }

    /*
     * 一直循环到所有被挂起的cfs_rq都解挂为止
     */
    while (throttled && cfs_b->runtime > 0) {
        /* 实际完成解挂的函数 */
        distribute_cfs_runtime(cfs_b);

        throttled = !list_empty(&cfs_b->throttled_cfs_rq);
    }
}

重置好带宽的时间之后，最后调用函数 distribute_cfs_runtime 来解挂所有的被挂起的队列：

/* file: kernel/sched/fair.c */

/* 该函数主要目的是将 cfs_b 的挂起列表中的队列解挂，因此其为每个 cfs_rq
 * 分配时间时，在补上其上周期透支时间后只象征性地加了1ns, 因此每个 cfs_rq
 * 具体申请时间的操作还是通过函数 assign_cfs_rq_runtime 来完成的 */
static void distribute_cfs_runtime(struct cfs_bandwidth *cfs_b) {
    struct cfs_rq *cfs_rq;
    u64 runtime, remaining = 1;

    rcu_read_lock();
    /* 遍历带宽控制器的挂起列表 */
    list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq, throttled_list) {
        struct rq *rq = rq_of(cfs_rq);
        struct rq_flags rf;

        rq_lock_irqsave(rq, &rf);
        /* 如果当前的 cfs_rq 已经被解挂了，则直接跳到循环体末尾继续下一次循环 */
        if (!cfs_rq_throttled(cfs_rq))
            goto next;

        /* 接下来操作带宽控制器的时间，需要先加锁 */
        raw_spin_lock(&cfs_b->lock);
        /* 补充上个周期内透支的时间（cfs_rq->runtime_remaining为负），另外再分配1ns,
         * 在这里保证其时间大于0即可 */
        runtime = -cfs_rq->runtime_remaining + 1;
        /* 当然分配给 cfs_rq 的时间不能超过带宽控制器这周期的剩余时间 */
        if (runtime > cfs_b->runtime)
            runtime = cfs_b->runtime;
        /* 从带宽控制器中减掉分配给 cfs_rq 的时间 */
        cfs_b->runtime -= runtime;
        remaining = cfs_b->runtime;
        raw_spin_unlock(&cfs_b->lock);

        /* 将分配给 cfs_rq 的时间加上去 */
        cfs_rq->runtime_remaining += runtime;

        /* 如果分配到了时间，则解挂该cfs_rq */
        if (cfs_rq->runtime_remaining > 0)
            /* 解挂函数在前面章节已经介绍过 */
            unthrottle_cfs_rq(cfs_rq);

    next:
        rq_unlock_irqrestore(rq, &rf);

        /* 如果带宽控制器的时间已经耗尽，则退出 */
        if (!remaining)
            break;
    }
    rcu_read_unlock();
}

至此，整个 period_timer 就介绍完毕了，接下来我们看一下 slack_timer 是做什么的。

我们知道cfs_rq每次向任务组申请5ms的时间，对于CPU而言这个时间也不少了，但如果该cfs_rq中的任务刚好在申请完时间额度之后就进入了睡眠状态，并且还一睡不醒，那么让它在睡眠过程中一直持有这么多时间是不合理的，这完全可能导致任务组在其他CPU上的cfs_rq在本周期内分配不到时间而被挂起。时间是个宝贵的资源，我们必须保证它的利用率，如果这种情况下我们能将cfs_rq的时间返回一部分给任务组的话，其它有需要的cfs_rq就可以使用了。

返回时间的操作发生在调度器对任务进行dequeue操作时：

/* file: kernel/sched/fair.c */

static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                           int flags) {
    /* 当开启带宽控制时，该函数会酌情返回一部分时间给任务组 */
    return_cfs_rq_runtime(cfs_rq);
}

static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {
    if (!cfs_bandwidth_used())
        return;

    /* cfs_rq->nr_running用来检查该队列是否还有可运行的任务，如果没有的话才考虑返回时间
     */
    if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
        return;

    /* 实际返回时间的函数 */
    __return_cfs_rq_runtime(cfs_rq);
}

static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {
    struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
    /* min_cfs_rq_runtime为1ms, 为自己保留1ms, 剩下的还给组织 */
    s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;

    /* 自己的预留时间都不够的话就算了 */
    if (slack_runtime <= 0)
        return;

    raw_spin_lock(&cfs_b->lock);
    /* 确实有限额，那么返回时间才有意义。cfs_b->quota==RUNTIME_INF的话任何时候cfs_rq都可以申请到时间
     */
    if (cfs_b->quota != RUNTIME_INF) {
        /* 将时间还给组织 */
        cfs_b->runtime += slack_runtime;

        /* we are under rq->lock, defer unthrottling using a timer */
        /* 如果归还了时间之后发现任务组有了足够的时间以供申请，并且此时已经有了被挂起的队列，那么可以对其解挂。
         * 函数start_cfs_slack_bandwidth用来开启slack定时器，因为此时我们还持有着rq->lock,
         * 因此通过定时器来完成解挂操作
         */
        if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
            !list_empty(&cfs_b->throttled_cfs_rq))
            start_cfs_slack_bandwidth(cfs_b);
    }
    raw_spin_unlock(&cfs_b->lock);

    /* 即便不用返回时间这里也从 cfs_rq 中减去，避免下次再尝试返回时间 */
    cfs_rq->runtime_remaining -= slack_runtime;
}

函数 start_cfs_slack_bandwidth 用来开启 slack 定时器，该定时器的回调函数是 sched_cfs_slack_timer, 该函数调用 do_sched_cfs_slack_timer 来完成解挂操作：

/* file: kernel/sched/fair.c */

static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b) {
    /* slice 是5ms, 也是cfs_rq一次申请的时间片大小 */
    u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
    unsigned long flags;

    /* confirm we're still not at a refresh boundary */
    raw_spin_lock_irqsave(&cfs_b->lock, flags);
    cfs_b->slack_started = false;

    /* 判断是否period timer马上就要执行了，如果是的话，就等period
     * timer来处理工作，不必在此多此一举 */
    if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
        raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
        return;
    }

    /* 确保runtime > 5ms, 因为cfs_rq一次申请的时间片大小就是5ms,
     * 否则解挂的队列也无法申请时间，还会再次被挂起 */
    if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice)
        runtime = cfs_b->runtime;

    raw_spin_unlock_irqrestore(&cfs_b->lock, flags);

    /* 带宽控制器当前周期的时间总量剩余小于5ms, 没必要去解挂队列了 */
    if (!runtime)
        return;

    /* 尝试着解挂 cfs_rq, 能解挂多少就解挂多少 */
    distribute_cfs_runtime(cfs_b);
}

可以看出 slack 定时器其实是一个辅助角色，它在cfs_rq归还时间后被CFS开启，然后尽可能地提前解挂其它队列，以便提升带宽时间的利用率。