什么是 RSEQ（可重新启动序列）以及如何使用它们？

Question

Linux 4.18 引入了rseq(2)系统调用。我在SO上发现只有一个问题提到了rseq，而且网上关于它的信息相对较少，所以我决定问一下。什么是可重新启动序列以及程序员如何使用它们？

我必须寻找restartable sequences: fast user-space percpu critical sections才能获得任何有意义的结果。我能够找到向内核添加相关功能的提交。进一步的研究让我看到了2013 年的演讲，我认为这是第一次介绍这个概念。许多工作是由 EfficiOS 公司的团队完成的。他们描述了向 Linux 内核贡献此功能的意图。

看起来这个功能很少有人知道，但显然它是用来优化TCMalloc 分配器的性能的。一般来说，看起来是某种并发优化。

尽管列出的来源提供了背景信息，但尚未对 SO 上提供的 RSEQ 进行解释。了解它们在实践中的其他用途以及如何使用会很有用。

编辑：实际例子

假设我正在创建一个 C++ 作业系统。其中一部分是无锁多生产者单消费者队列。如何将rseq(2)系统调用的使用引入到我的代码中以潜在地提高其性能？

class mpsc_list_node
{
    mpsc_list_node* _next;

    template<typename T>
        requires std::derived_from<T, mpsc_list_node>
    friend class mpsc_list;
};

template<typename T>
    requires std::derived_from<T, mpsc_list_node>
class mpsc_list
{
private:
    std::atomic<T*> head{ nullptr };

private:
    static constexpr size_t COMPLETED_SENTINEL = 42;

public:
    mpsc_list() noexcept = default;
    mpsc_list(mpsc_list&& other) noexcept :
        head{ other.head.exchange(reinterpret_cast<T*>(COMPLETED_SENTINEL), std::memory_order_relaxed) }
    {
    }

    bool try_enqueue(T& to_append)
    {
        T* old_head = head.load(std::memory_order_relaxed);
        do
        {
            if (reinterpret_cast<size_t>(old_head) == COMPLETED_SENTINEL)
                [[unlikely]]
                {
                    return false;
                }
            to_append._next = old_head;
        } while (!head.compare_exchange_weak(old_head, &to_append, std::memory_order_release, std::memory_order_relaxed));
        return true;
    }

    template<typename Func>
    void complete_and_iterate(Func&& func) noexcept(std::is_nothrow_invocable_v<Func, T&>)
    {
        T* p = head.exchange(reinterpret_cast<T*>(COMPLETED_SENTINEL), std::memory_order_acquire);
        while (p)
            [[likely]]
            {
                T* cur  = p;
                T* next = static_cast<T*>(p->_next);
                p       = next;
                func(*cur);
            }
    }
};

我很好地解释了这样做的目的mpsc_list及其在工作系统中的地位README：

作业间同步

唯一使用的同步原语是原子计数器。这个想法源于著名的GDC 演讲， 主题是在顽皮狗的游戏引擎中使用纤程实现作业系统。

jobs 的公共承诺类型 ( promise_base) 实际上是来自 的派生类型 mpsc_list，即多生产者单消费者列表。该列表存储依赖于当前作业的作业。它是一个使用原子操作实现的无锁链表。每个节点都存储一个指向依赖者的 Promise 和下一个节点的指针。有趣的是，这个链表不使用任何动态内存分配。

当一个作业co_await是一组（可能是 1 大小）依赖作业时，它会执行一些操作。首先，它的承诺将其自己的内部原子计数器设置为依赖作业的数量。然后，它（在堆栈上）分配依赖项计数大小的notifier对象数组。类型notifier是链表节点的类型。创建的notifiers 都指向作业被挂起。他们没有下一个节点。

然后，该作业会遍历其每个依赖项作业，并尝试将相应的作业附加 notifier到依赖项列表中。如果该依赖关系已完成，则此操作将失败。这是因为当作业返回时，它将其列表的头部设置为特殊的哨兵值。如果依赖关系已经完成（例如，在不同的线程上），则挂起作业只会减少其自己的原子计数器。如果依赖项尚未完成，则会将 附加notifier到该依赖项的列表中。它使用CAS 循环来实现这一点。

在检查完每个依赖项后，挂起作业会检查其依赖项的数量已完成。如果全部都有，那么它不会挂起并立即继续执行。这不仅仅是一个优化。这是工作系统正常运行所必需的。这是因为该作业系统没有挂起的作业队列。作业系统只有一个就绪作业队列。挂起的作业仅存储在其依赖项的链表中。因此，如果一个作业挂起，但没有任何依赖关系，它就永远不会恢复。

当作业返回时，它会遍历其依赖项的链接列表。首先，它将列表的头部设置为特殊的哨兵值。然后，它会遍历所有作业，自动递减它们的原子计数器。递减是RMW 操作，因此作业读取计数器的先前值。如果是一个，那么它就知道这是该作业要完成的最后一个依赖项，并将其push添加到作业队列中。

Answer 1

引入系统rseq调用是restartable sequences为了允许per-cpu variables在用户空间中使用。每个 cpu 变量在内核空间中很容易，因为您可以在引用每个 cpu 时随时禁用抢占。

在用户空间中，如果您想相对于当前线程/CPU 一致地处理每个 cpu 变量，则必须考虑不需要的抢占。为此restartable sequences引入了该机制