我正在为 bcache Linux 模块编写补丁,并努力在 Linux 核心中找到通用的 LIFO 实现。我在 defines 上找到了几个 FIFO 实现。和 without .但是,后进先出法没有什么不同。
在哪里可以找到?最好是 C,不是 asm,也不是基于定义,但任何一个都应该可以工作。
如果没有提供抽象的 LIFO,那么最容易实现 LIFO 的结构是什么(例如 Linux 核心中的通用堆栈实现)?
最佳答案
如果后进先出具有固定的最大深度,并且不是动态分配的,那么它就像
#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 攻击等问题。
关于c - Linux 核心中的通用堆栈实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43293295/