《Linux内核设计与实现》内核数据结构6.2队列 P78-81

标签：esize 队列 out fifo 内核 81 kfifo P78 size

队列与堆栈

队列

只允许在队列的前端（front，队头）进行删除操作，而在队列的后端（rear，队尾）进行插入操作。当队列中没有元素时，即front=rear，称为空队列。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。队列符合先进先出(FIFO—first in first out)原则

堆栈

栈：又名堆栈，只允许在栈顶插入和删除元素。栈顶是低位，栈底是高位。栈中没有元素时称为空栈，栈符合先进后出原则(LIFO,last in first out)。
操作： push入栈、pop出栈

6.2.1 kfifo入队列和出队列

 

 

（1）空的kfifo

（2）推入一个buffer后

（3）摘取一个buffer后，出口偏移（out）加上摘取的元素数目

（4）当此时put的buffer长度超出in到末尾长度时，则将剩下的移到头部去

参考：https://zhuanlan.zhihu.com/p/548021636

 

 

6.2.2 创建队列

struct __kfifo {
    unsigned int    in;   // 队列头，删除操作
    unsigned int    out;  // 队列尾，插入操作
    unsigned int    mask; // 缓存区大小，byte
    unsigned int    esize; // 缓存区元素占用的字节数，比如char时，eszie为1，int时esize为4
    void        *data;    // 存放数据的缓存区地址
};

kfifo_alloc由内核调用kmalloc_array函数来申请内存空间

int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,         size_t esize, gfp_t gfp_mask) {     /* 向上对齐到2的幂 */     size = roundup_pow_of_two(size);
    fifo->in = 0;     fifo->out = 0;     fifo->esize = esize;
    if (size < 2) {         fifo->data = NULL;         fifo->mask = 0;         return -EINVAL;     }
    fifo->data = kmalloc_array(esize, size, gfp_mask);
    if (!fifo->data) {         fifo->mask = 0;         return -ENOMEM;     }     fifo->mask = size - 1;
    return 0; }

 用户申请好一个buffer，再使用kfifo_init初始化为kfifo队列

int __kfifo_init(struct __kfifo *fifo, void *buffer,
        unsigned int size, size_t esize)
{
    size /= esize;

    if (!is_power_of_2(size))
        size = rounddown_pow_of_two(size);

    fifo->in = 0;
    fifo->out = 0;
    fifo->esize = esize;
    fifo->data = buffer;

    if (size < 2) {
        fifo->mask = 0;
        return -EINVAL;
    }
    fifo->mask = size - 1;

    return 0;
}

 

6.2.7队列使用举例

（1）kfifo_in推入数据（0-31）

 

 （2）kfifo_out_peek读取第0位置的元素，但不删除，out不增加

 

（3）kfifo_out从出口偏移（out）拷贝出一个4byte

 

标签：esize,队列,out,fifo,内核,81,kfifo,P78,size
From： https://www.cnblogs.com/cai-zi/p/16887612.html