c - Linux 核心中的通用堆栈实现

Question

我正在为 bcache Linux 模块编写补丁，并努力在 Linux 核心中找到通用的 LIFO 实现。我在 defines 上找到了几个 FIFO 实现。和 without .但是，后进先出法没有什么不同。

在哪里可以找到？最好是 C，不是 asm，也不是基于定义，但任何一个都应该可以工作。

如果没有提供抽象的 LIFO，那么最容易实现 LIFO 的结构是什么(例如 Linux 核心中的通用堆栈实现)？

Answer 1

如果后进先出具有固定的最大深度，并且不是动态分配的，那么它就像

#define LIFO_MAXDEPTH  16

static spinlock_t   lifo_lock = SPIN_LOCK_UNLOCKED;
static size_t       lifo_count = 0;
static struct item  lifo_entry[LIFO_MAXDEPTH];

int lifo_push(const struct item *from)
{
    spin_lock(&lifo_lock);
    if (lifo_count >= LIFO_MAXDEPTH) {
        spin_unlock(&lifo_lock);
        return -1;
    }

    lifo_entry[lifo_count++] = *from;

    spin_unlock(&lifo_lock);
    return 0;
}

int lifo_pop(struct item *to)
{
    spin_lock(&lifo_lock);
    if (lifo_count < 1) {
        spin_unlock(&lifo_lock);
        return -1;
    }

    *to = lifo_entry[--lifo_count];

    spin_unlock(&lifo_lock);
    return 0;
}

因为我们只需要在很短的时间内保持锁定状态，所以自旋锁就足够了。

如果后进先出法是动态分配的，事情就会变得更复杂。特别是，因为我们可能必须调用 kmalloc() 或 kfree()，所以我们不能使用自旋锁。您还希望将堆栈拆分为页面大小的 block ，因为高阶分配可能会失败。然后，您必须考虑诸如恶意用户试图使用该工具进行 DOS 攻击等问题。