Lovely Cabin - lilac.
所有文章 标签 分类 系列 文档 关于
Lovely Cabin - lilac.

目录

目录

Linux的软件预取

lilac avatar  收录于  系列 数据Cache预取
     约 3954 字   预计阅读 18 分钟 
系列 - 数据Cache预取

Linux对软件预取的使用主要集中在IO设备驱动和网络协议栈里——这比较好理解：因为IO设备驱动的内存访问模型大多是处理DMA Ring上通过指针间接访问的RX/TX buffer，特别适合使用软件预取。然而这类场景并不是我们关心的重点（后面别的项目中会有类似场景的分析），这里的分析主要关注于内核调度和内存管理相关的部分。

Linux调度和内存管理部分（kernel和mm目录下）用到软件预取的地方只有屈指可数的6～7处，说明其对预取的使用相当谨慎。而且大部分是针对硬件预取器所无法解决的间接访存循环的预取。

从前面“针对预取的软件优化”章节中的分析我们可以知道，针对遍历迭代的预取优化是软件预取的最典型使用场景。

rcu_process_callbacks内的预取是最简单的对单向链表遍历预取的场景：

/* Invoke the RCU callbacks whose grace period has elapsed.  */
static __latent_entropy void rcu_process_callbacks(struct softirq_action *unused)
{
    struct rcu_head *next, *list;
    ...

    /* Invoke the callbacks on the local list. */
    while (list) {
        next = list->next;
        prefetch(next);  // 对链表的下个节点进行预取，注意这里不需要判断指针合法性
        debug_rcu_head_unqueue(list);
        local_bh_disable();
        rcu_reclaim_tiny(list);  // 这里涉及到kfree或回调，能保证有足够的计算时间
        local_bh_enable();
        list = next;  //  使用next变量缓存了预取地址，避免重复计算
    }
}

由于rcu_reclaim_tiny()对链表节点有足够的计算量，因此链表节点预取调度距离仅能为1的限制也没什么影响。

Queued Spinlock是Linux 4.2之后用来替代标准Spinlock的锁机制。其本身从设计上就是为了解决在高并发系统中传统Spinlock的Cache弹跳问题：由于多个CPU上的线程均在同一个共享的spinlock锁变量上自旋，而申请核释放锁都必须对该变量进行修改，这将导致所有参与竞争自旋锁的处理器的该行Cache Line失效。如果自旋锁的竞争比较激烈的话，频繁的核间缓存同步操作会导致大量访存，降低系统性能。而实际上由于每次解锁也只会有一个竞争者获胜，那么就干脆只让锁的所有者和其中一个竞争者在共享变量上自旋好了，别的竞争者按照请求锁的先后持续在队列中排队等待（实际上是在另一个本地变量上自旋）。共享锁变量就像接力棒一样依次传递给队列中的线程：只有得到接力棒的线程才会真正地在共享变量上自旋，并在得到锁以后再通知队列中的下个线程接棒自旋（具体细节可以自己Google一下）。

queued_spin_lock_slowpath()函数即实施这个排队等待过程：若出现3个或以上线程竞争自旋锁，则从第三个线程开始会进入该函数开始排队：当其发现自己前面还有正在等锁的线程时，即把自己加入等待队列，并在本地变量node->locked上自旋：

/*
 * if there was a previous node; link it and wait until reaching the
 * head of the waitqueue.
 */
if (old & _Q_TAIL_MASK) {
    prev = decode_tail(old);
 
    /* Link @node into the waitqueue. */
    WRITE_ONCE(prev->next, node);
 
    pv_wait_node(node, prev);
    arch_mcs_spin_lock_contended(&node->locked);  // 在本地变量上自旋等待前一线程开始竞争锁

当排在该线程前面的等待者得到锁之后，会如下将下个等待者解除自旋：

    arch_mcs_spin_unlock_contended(&next->locked);  // 解除next在本地变量上的自旋
    pv_kick_node(lock, next);

所以只要线程从node->locked自旋中退出，就意味着其成为了第一等待者，可以真正地去全局锁变量上自旋竞争。然而在此之前它会执行如下软件预取：

    next = READ_ONCE(node->next);
    if (next)  // <==== 实际上这个if不需要，完全可以直接预取减少分支跳转
        prefetchw(next);
}

这是因为在其排队的过程中，别的线程可能也加入了等待队列（修改node->next指向自己）。因为当前线程在经过短暂的自旋得到锁之后很快也要调用arch_mcs_spin_unlock_contended()交棒给下一顺位，因此这里在竞争锁之前先对下一节点进行写预取，以便让预取时延和后面对锁的竞争并发（注意自旋锁是面向短时间持锁的场景，因此这里由于竞争锁时间过长导致“早”预取的可能性很小）。

在这里可能会有个疑问：由于在别的处理器修改node->next时也同时会导致node所在Cache Line在当前处理器上失效，这里计算预取地址node->next时为何不需要对node进行预取？这是因为在数据结构定义中本地自旋变量lock和next在同一Cache Line内，因此在当前线程从node->locked中退出自旋时该Cache Line一定已经从内存中更新了，所以取node->next时不会再触发Cache Miss：

struct mcs_spinlock {
    struct mcs_spinlock *next;
    int locked; /* 1 if lock acquired */
    int count;  /* nesting count, see qspinlock.c */
};

这里看似仅做了一次预取似乎没有太大价值。但是如果动态地考虑整个Queue Spinlock的执行过程：由于每个处于队头的线程都会执行这次预取，在整个队列遍历过程中实际上是对该单向链表的每个节点都执行了一次预取，依然是个循环遍历场景。

在进程CFS调度过程中会频繁调用的task_sched_runtime()函数内有这么一处奇怪的单点预取：

rq = task_rq_lock(p, &rf);
/*
 * Must be ->curr _and_ ->on_rq.  If dequeued, we would
 * project cycles that may never be accounted to this
 * thread, breaking clock_gettime().
 */
if (task_current(rq, p) && task_on_rq_queued(p)) {
    prefetch_curr_exec_start(p);  // <==== 奇怪的单点预取
    update_rq_clock(rq);
    p->sched_class->update_curr(rq);
}
ns = p->se.sum_exec_runtime;
task_rq_unlock(rq, p, &rf);
 
return ns;

prefetch_curr_exec_start()这个名字也起得奇丑无比：从函数名上看是对curr和curr->exec_start的预取，然而在调用上下文中根本看不到对所预取的数据结构的引用，十分费解。

查看注释后得知，在其后调用的p->sched_class->update_curr(rq)（实际调用kernel/sched/fair.c:update_curr()）里会访问curr和curr->exec_start，且实测若不加预取，这里会产生大量的Cache Miss。加入预取后对性能有改善：

/*
 * The function fair_sched_class.update_curr accesses the struct curr
 * and its field curr->exec_start; when called from task_sched_runtime(),
 * we observe a high rate of cache misses in practice.
 * Prefetching this data results in improved performance.
 */
static inline void prefetch_curr_exec_start(struct task_struct *p)
{
#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity *curr = (&p->se)->cfs_rq->curr;
#else
    struct sched_entity *curr = (&task_rq(p)->cfs)->curr;
#endif
    prefetch(curr);
    prefetch(&curr->exec_start);
}

这里实际上是预取了cur所指的结构体的头两条Cache Line：

struct sched_entity {
    /* For load-balancing: */
    struct load_weight		load;	// <==== Cache Line 0
    struct rb_node			run_node;
    struct list_head		group_node;
    unsigned int			on_rq;

    u64				exec_start;	// <==== Cache Line 1
    u64				sum_exec_runtime;
    u64				vruntime;
    u64				prev_sum_exec_runtime;
    u64				nr_migrations;
    struct sched_statistics		statistics;
    ...
};

可以看出这种类型的预取实际上产生了严重的抽象泄露：其将update_curr()函数内具体访问的数据结构暴露在毫不相干的task_sched_runtime()函数内，本来已经通过函数指针抽象化的策略解耦又被丑陋的预取给死死地绑在一起了——这对程序的模块化和可读性带来严重的破坏。而且未来若这里的逻辑或时序有变化，必须记得同时修改预取的位置和地址，也增加了代码的维护成本。应该是这处预取对性能的改善十分可观，否则以Linus的洁癖不可能让这样的代码进去。

Linux的页分配器中free_pcppages_bulk()函数将PCP（Per CPU Page）缓存中指定数量的页面批量还回Buddy System伙伴系统（这些概念读者可自行Google）。在早先的实现中，一个while大循环负责逐页寻找和释放符合条件的页面。可能是出于对数据预取的考虑，在当前版本（5.7.14）的实现中被拆成了两个循环：第一个while循环负责寻找符合条件的页面并放入一个临时链表；之后遍历这个临时链表将前面找到的所有待释放页面释放回伙伴系统。

在第一个寻找页面的while循环中会对选中待释放页面的伙伴页的page结构体进行预取：

do {
    page = list_last_entry(list, struct page, lru);
    /* must delete to avoid corrupting pcp list */
    list_del(&page->lru);
    pcp->count--;
 
    if (bulkfree_pcp_prepare(page))
        continue;
 
    list_add_tail(&page->lru, &head);  // 将选中的页加入临时链表准备释放
 
    /*
     * We are going to put the page back to the global
     * pool, prefetch its buddy to speed up later access
     * under zone->lock. It is believed the overhead of
     * an additional test and calculating buddy_pfn here
     * can be offset by reduced memory latency later. To
     * avoid excessive prefetching due to large count, only
     * prefetch buddy for the first pcp->batch nr of pages.
     */
    if (prefetch_nr++ < pcp->batch)  // 对预取数量有限制，避免“早”预取
        prefetch_buddy(page);  // 预取的是这个页面的伙伴页
} while (--count && --batch_free && !list_empty(list));

这是因为在后面将要进行的遍历释放链表中__free_one_page()里需要访问被释放页面的伙伴页结构——这又是一个抽象泄露的地方。不过这个抽象泄露对于很熟悉Linux内存管理的人来说并非无法理解：因为往伙伴系统里释放页面往往伴随着对伙伴页的访问，比起前面那个纯粹测出来的Miss点来说这里还算合乎逻辑：

spin_lock(&zone->lock);
...
list_for_each_entry_safe(page, tmp, &head, lru) {
    ...
    __free_one_page(page, page_to_pfn(page), zone, 0, mt, true);  // 这里面会访问对应的伙伴页
    ...
}
spin_unlock(&zone->lock);

这一预取的地址计算开销相对较大：其中涉及了一系列地址变换——虽然Linux已经将这类页面转换设计得非常高效了。因此前面在注释中也很详细地说明了根据测试结果，这里预取产生的性能增益足以抵消这些开销：

static inline void prefetch_buddy(struct page *page)
{
    unsigned long pfn = page_to_pfn(page);
    unsigned long buddy_pfn = __find_buddy_pfn(pfn, 0);
    struct page *buddy = page + (buddy_pfn - pfn);

    prefetch(buddy);
}

另外，其对于预取的总数也有限制：不超过pcp->batch个，推测是为了避免“早”预取。毕竟如果一次要释放的页面较多，一下子全预取了有可能导致前面预取的伙伴页、或是临时链表中的待释放页面被换出Cache。从伙伴页page结构的访存规律上看未预取的部分也不像是能利用硬件预取的样子，访问时仍会产生Cache Miss。推测Linux的开发者应该是根据测试结果认为使用这样的门限已足以解决大部分性能问题，在性能和风险中取得平衡。

对于这个预取的实现，有一点疑惑是为何不放在list_for_each_entry_safe()循环中预取？这样对代码可读性的破坏相对小一些：预取处和数据的访问处在代码中的距离更近，便于维护且不用限制预取总数。猜测之所以不这样做可能是因为在遍历链表的循环体内预取最多只能提前预取一个节点（链表的局限性），可能在测试中发现预取距离不足而不得不提前到上一个循环批量预取。

调度和内存管理均为Linux内核中最为性能敏感的模块，然而其中对软件预取的使用却远比我们所想象得少，可以看出Linux对这一技术的使用是非常有节制的。除了典型的迭代遍历场景，内核中每处非常规的预取前都加入了非常详细的注释，说明了为何要加入预取以及预取能所带来的收益——可以看出这些预取的背后都有性能测试结果背书，以足够大的性能增益交换对代码可读性和额外开销的影响。

更新于 2026-01-20
 | 主页