内存屏障踩坑

最近为了给linux系统装上一个新的scheduler，连续一周在熬夜看linux的内核源码。打算等有时间出一个详细的教程怎么搞这类东西作为存档，也要再学习一下。但是这不是今天的主题，今天的主题是一个非常坑爹的bug。

在linux内核模块中，调度器为了提高性能，在每次进行调度的时候，除了会使用各个scheduler class自己提供的pick_next_task方法之外，还会做一些负载均衡的工作。如果我们启用了SMP，也就是Symmetric Multi-Processor，那么在每次调度的时候，还会调用balance方法，这个方法会在每个cpu上找到一个负载最低的cpu，然后将这个cpu上的一个task迁移到负载最高的cpu上。这个方法的实现在kernel/sched/中.

因为是每次调度的时候都会使用，所以这个方法的安全和性能对于整个系统来说都非常重要。假如我们在某些地方写了死锁，那么在一些并发量比较低的场景可能根本不会形成环路等待条件，就算形成了，也一般不会有什么严重后果，但是如果这个方法出了问题，那么就会导致整个系统的负载不均衡，甚至死锁，这个问题就非常严重了。（哭了，这个方法写崩对于系统是有不可逆的损伤的，我重装了至少5次Kernel）

然后在写balance函数的时候，我们观看了一下实施调度器rt.c里面的实现，大概程序可以分为以下几步

• 先从外部环境解锁当前执行队列
• 然后判断有没有需要负载均衡的cpu
• 如果没有，那么就直接返回，如果有，那么就先拿到负载最高的cpu的执行队列的自旋锁，还得同时拿到本队列的自旋锁
• 那么就从负载最高的cpu上拿出一个task，然后放到负载最低的cpu的对应的执行队列上，cpu设置mask一下
• 最后再把自旋锁都解锁，再给外部环境加锁

static inline void balance_xx(struct rq *rq, struct task_struct *p, struct rq_flag *rf)
{
    外部环境加锁();
    
    判断有没有过载cpu();

    if (没有需要负载均衡的cpu)
        return;

    负载最高的cpu的执行队列的自旋锁();
    本队列的自旋锁();

    从负载最高的cpu上拿出一个task();

    本队列的自旋锁解锁();
    负载最高的cpu的执行队列的自旋锁解锁();

    外部环境解锁();
}

比如我们可以看到rt.c里面的实现，这个实现是比较简单的，因为rt的调度器是不会有负载均衡的，所以直接返回就好了。

static void balance_rt(struct rq *rq, struct task_struct *p, struct rq_flag *rf)
{
    if (task_on_rq_queued(p) && need_pull_rt_task(rq)) {
        rq_unpin_lock(rq, rf);
        pull_rt_task(rq);
        rq_repin_lock(rq, rf);
    }
}

这么来的，我们于是也写了个类似的逻辑。

但是，诡异的事情发生了，我们写出来的东西能跑，但不完全能跑。大概10次里面有一次可以正常启动，其他的都会卡在启动的时候，然后我们就开始了一段漫长的debug之旅。多长呢？大概让我这周一整周都干到了凌晨三点。

首先判断是死锁，但是问题来了

• 既然死锁，为什么偶尔能全部开机？
• 如果开机的时候会死锁，为什么开机之后系统表现完全正常？

带着这样的疑问我们毫无头绪得看了三天，人都快疯了。然后直到我们选择了重构。

为了解决问题，我队友把上面的函数拆成了pull_task， need_pull_task和balance三个函数。

我选择了直接用手添加spinlock，其他什么也没改，就好了！！ 我和队友的程序几乎在同时间恢复正常了。

这就很让人迷惑了，为什么之前不行，但这样就可以了呢？我们的代码逻辑完全一样啊，为什么会出现这样的问题呢？

然后最后总结了一下，发现问题可能出在代码重排上。

因为我们的编译器能够利用的寄存器是有限的，所以在编译的时候，编译器会对代码进行重排，以便能够更好的利用寄存器。但是这个重排是有可能会改变程序的执行顺序的(可这是自旋锁啊！)。虽然我记得代码重排应该至少保证a的读在a的写前面，但是这个重排是有可能会改变程序的执行顺序的。所以我们的代码可能会变成这样

    外部环境加锁();
    
    判断有没有过载cpu();

    if (没有需要负载均衡的cpu)
        return;
    负载最高的cpu的执行队列的自旋锁解锁();
    负载最高的cpu的执行队列的自旋锁();
    从负载最高的cpu上拿出一个task();
    本队列的自旋锁解锁();
    本队列的自旋锁();
    
    

    外部环境解锁();
    

结论

这样的话，就会出现问题了，从负载最高的cpu上拿出一个task() 因为只涉及几个cpu的bitmask，所以可能触发了某些神秘的机制，导致我们还没有加锁的时候就解锁了，或者让我们的两个锁形成了环路等待条件，所以g掉了。而且这个二进制指令一旦被正确生成，就不会再改变了，所以这也解释了我们为什么有些时候运气好开了机，然后程序完全正常，完全没有崩溃。有的开到一般就g了，有的直接冲坏了kernel。

那为什么内核里面的代码不会出现这样的问题呢？

因为代码被放到了两个函数里面，如队友1和rt的代码所作，而且rt里面的加锁其实是放在两个函数和一个for里面去做的，这样的高级控制语句使得编译器不太会对代码进行重排，所以就不会出现这样的问题了。(不确定是不是在某一处加了内存屏障)

如何解决这个问题呢？我们可以在代码里加上内存屏障，来阻止编译器对代码进行重排。但是这个内存屏障会带来一些性能损失，所以我们选择了重构。比如我们可以把代码重构成这样

static inline void balance_xx(struct rq *rq, struct task_struct *p, struct rq_flag *rf)
{
    外部环境加锁();
    
    判断有没有过载cpu();

    if (没有需要负载均衡的cpu)
        return;

    负载最高的cpu的执行队列的自旋锁();
    本队列的自旋锁();

    smp_wmb(); // 内存屏障，阻止编译器对代码进行重排
    从负载最高的cpu上拿出一个task();

    本队列的自旋锁解锁();
    负载最高的cpu的执行队列的自旋锁解锁();

    外部环境解锁();
}

这样的话，就能保证代码的执行顺序了。