关于PX4在linux上调度的bug

作者

PX4 在linux上调度，会遇到一个问题：
[linux] occasionally trap in deadloop on weak SOCs https://github.com/PX4/PX4-Autopilot/issues/19358

具体来说，就是在hrt的call_out链表，会出现把重复entry 添加进去，导致出现 node->next = node 的情况。这样的话，链表就出现了一个环，一旦遍历链表进入这个环之后，就再也无法出去。表现在Linux上，就会发现PX4的线程占了CPU 几乎100%的时间，但是整个PX4却仍然被卡住。

之前我已经在PX4的社区上提过，但是由于很难复现，最终也没有引起重视。
最近我打算在rust 重新写一个专门在linux上跑的飞控，调度方式准备参考PX4的 线程+workqueue的方式来做，但是之前这个bug其实我还没弄得很清楚。正如我在上面那个帖子上的回复一样，多核的情况下，风险点还是比较好分析的，但是单核的情况，我一直没找到一个好的原因来解释。

这个bug的解决办法其实比较简单：https://github.com/AutopilotPi/PX4-Autopilot/commit/121b652fac0baf39d6ad80bcd2750852842931e9
主要就是调整了一下删除call out中entry的时间点。

这几天重新看了一遍，总算想通了，这里记录一下。

PX4的调度方式

主要是几个重点， 各个workqueue都是跑在各自的线程上，这些线程的调度策略都是FIFO的。同时，每个workqueue上有ScheduledWorkItem. 实际上这些ScheduledWorkItem就是各个驱动了，比如说ICM20600的驱动，跑在SPI 的workqueue上。

那么这些驱动里面，就可以调用一些调度的方法，类似于ScheduleOnInterval，或者ScheduleDelayed这样的方法，从而达到使自己下一次还能够被调度到。

而这些调度方法，底层其实就是像hrt的call_out 链表中，加入一个个的entry。这些entry包含信息有：

  • deadline: 下一次执行的时间(戳）
  • period:如果不是周期性的工作，period为0
  • callback: 这个callback其实不干别的事，主要就是把这个驱动，也就是这个ScheduledWorkItem重新添加到他对应的workqueue中

而hrt thread作为优先级最高的FIFO线程，它会取出他的call_out链表中的head，也就是第一个到时间的entry，调用它的call_back。

这里面有几个重点：

  • hrt thread 只负责周期性的从call_out拿出entry，并调用其call_back，这个callback一般是将某个驱动加入到它的队列中
  • 驱动的执行是在他自己的workqueue中，不是在hrt thread里面
  • ScheduleDelayed这些方法的调用，也就是添加entry 到hrt的call_out链表这个动作，也是在ScheduledWorkItem自己的线程中，不是在hrt thread里面

好了，明白了调度方式，我们重新来看下有bug的地方

bug分析

hrt_call_invoke就是 hrt_thread 取出第一个entry，然后调用call back的函数。

static void
hrt_call_invoke()
{
    struct hrt_call *call;
    hrt_abstime deadline;

    hrt_lock();

    while (true) {
        /* get the current time */
        hrt_abstime now = hrt_absolute_time();

        call = (struct hrt_call *)sq_peek(&callout_queue);

        if (call == nullptr) {
            break;
        }

        if (call->deadline > now) {
            break;
        }

        sq_rem(&call->link, &callout_queue);
        //PX4_INFO("call pop");

        /* save the intended deadline for periodic calls */
        deadline = call->deadline;

        /* zero the deadline, as the call has occurred */
        call->deadline = 0;

        /* invoke the callout (if there is one) */
        if (call->callout) {
            // Unlock so we don't deadlock in callback
            hrt_unlock();

            //PX4_INFO("call %p: %p(%p)", call, call->callout, call->arg);
            call->callout(call->arg);

            hrt_lock();
        }

        /* if the callout has a non-zero period, it has to be re-entered */
        if (call->period != 0) {
            // re-check call->deadline to allow for
            // callouts to re-schedule themselves
            // using hrt_call_delay()
            if (call->deadline <= now) {
                call->deadline = deadline + call->period;
                //PX4_INFO("call deadline set to %lu now=%lu", call->deadline,  now);
            }

            hrt_call_enter(call);
        }
    }

    hrt_unlock();
}

注意看35行到40行之间，可以看到在这里，hrt的锁释放后，又重新锁上了。这里是一个风险点，因为这里创造了一个间隙，一旦这个时候有其他线程一直在等hrt的锁，这个时候hrt的锁就会被其他线程抢走。
什么情况下会发生这种情况呢？

多核情况

多核很好分析，假设此时其他线程刚好执行到ScheduleOnInterval里面去，正在准备下一次的调用。ScheduleOnInterval内部其实就是hrt_call_internal

static void
hrt_call_internal(struct hrt_call *entry, hrt_abstime deadline, hrt_abstime interval, hrt_callout callout, void *arg)
{
    PX4_DEBUG("hrt_call_internal deadline=%lu interval = %lu", deadline, interval);
    hrt_lock();

    if (entry->deadline != 0) {
        sq_rem(&entry->link, &callout_queue);
    }

    entry->deadline = deadline;
    entry->period = interval;
    entry->callout = callout;
    entry->arg = arg;

    hrt_call_enter(entry);  # 这里会将entry 添加进call_out 链表中
    hrt_unlock();
}

那么由于其他线程执行到这个函数的时候，在等待hrt_lock()而陷入阻塞，此时 hrt_thread 那边居然大发慈悲地把锁释放了，于是这边迅速拿到了锁，并马上关门，迅速将自己的entry 添加进call_out中。最后在hrt_call_enter中，会遍历整个call_out链表，找到这个entry合适的地方。于是call_out里面现在有一个entry.

接下来回到hrt_call_invoke, 它重新地拿到了锁，结果到了76行，又发现原来这小子是周期任务，于是又自己调用了一下hrt_call_enter。于是这样之后，call_out 里面，就会有同一个entry出现两次，且还形成了一个环。

单核情况

单核情况比较复杂了，主要的原因在于：

  • hrt thread是FIFO调度的，且优先级最高，根本没有其他线程可以打断它。即使它释放了锁，也不会让其他线程运行
  • 跟hrt thread 一样优先级的还有rate_ctrl这个workqueue，但是看了一下他的item都是些速率控制的东西，而且这些速率控制器里面并没有使用ScheduleOnInterval类似的函数去控制调度，而是订阅了一些uorb的话题，通过uorb话题的更新来触发他们的callback，从而实现调度的。

当时我在这里卡了很久，一直也没找出一种case。但是按照之前debug这个问题的经验，我用我当时的解决办法，是可以在单核的机器上解决这个问题的。那么解决方法是有效的，说明很可能单核的情况也和多核的情况一样，最主要的问题出现在hrt_call_invoke中间释放了一下锁这个事上。

仔细考虑下面这种情况：

如果在hrt_thread 释放锁后，不是要调用entry的callback么，如果在callback中，它因为某些原因被阻塞，那么此时就可以由其他线程运行了。

有可能么？还真有。这些callback，其实主要都是要把自己给添加回workqueue的链表中：

void WorkQueue::Add(WorkItem *item)
{
    work_lock();

#if defined(ENABLE_LOCKSTEP_SCHEDULER)

    if (_lockstep_component == -1) {
        _lockstep_component = px4_lockstep_register_component();
    }

#endif // ENABLE_LOCKSTEP_SCHEDULER

    _q.push(item);
    work_unlock();

    SignalWorkerThread();
}

可以看到，这里还真有一个锁，如果hrt_thread真的在这里等待了这个锁，那么确实此时运行权就被其他线程拿走了。这个锁在workqueue遍历执行所有的item的时候会使用。

同时，如果这个workqueue优先级跟hrt_thread一样，那么即使这个workqueue把这个锁释放了，hrt_thread也不会马上重新运行，必须等这个线程进入阻塞，才会重新轮到hrt_thread。

好了，现在找到一种case能把hrt thread给打断了，但是光打断也没用。这个线程还需要调用ScheduleOnInterval这一类的函数，才能像多核情况一样，创造出一个环。

结果仔细找了下rate_ctrl这个workqueue，发现还有一个MixingOutput的驱动，会在运行的过程中，将自己的workqueue变到rate_ctrl里面，同时它还会调用ScheduleOnInterval

好嘛，这下齐活了。所以呢，在单核的情况下，只要MixingOutput进入到rate_ctrl中运行时，且碰巧在rate_ctrl遍历item的时候，打断了hrt_thread，那么就很可能会出现这个bug。

总结

好了，以上就是这个问题的分析。对于如何做一个线程+队列的调度器，有一些教训值得学习一下：

  • hrt调度中间，不要释放锁，让其他线程能够乘虚而入。 为什么PX4中间要释放锁呢？因为他认为hrt call_out 的entry的callback 不是受自己控制的，那么callback中可能有需要将自己重新添加回链表的需求。但其实px4代码中，几乎所有的callback都只是用来将workitem添加回workqueue而已，根本不会操作到hrt的call out。因此可以干脆把这个callback固定下来，不要让开发者可以自定义entry的callback
  • hrt thread的优先级应该是最高，且没有其他线程并列。在上面单核的情况，只要rate_ctrl的优先级没hrt_thread的优先级高，根本不会出现hrt thread被打断的情况。

发表评论