почему kfifo - это круговая очередь в некоторых блогах

Question

Есть ли в kfifo очередь Circlar?

В очереди Circlar WIKI (https://en.wikipedia.org/wiki/Circular_buffer) сказал " он был подключен сквозным. ". Но в linux-4.16.12 \ lib \ kfifo.c

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

    size = roundup_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;
}

Я не нахожу точку начального указателя на указатель конца, поэтому:

1) Имеет ли kfifo очередь Circlar?

2) если да, то как это доказать?

Answer 1

На странице Википедии, которую вы упомянули , говорится, что циклический буфер ведет себя , как если бы буфер был подключен вплотную.На практике циклический буфер - это просто массив определенной фиксированной длины, с двумя указателями индекса (обычно называемыми head и tail или in и out), представляющими «границы» записанных данных.Чтобы избежать записи за пределы буфера, все арифметические операции над этими индексами выполняются по модулю длина буфера.

Обычно значение указателей:

• tail или out указывает на последний прочитанный («удаленный») слот.

Есть также два граничных состояния:

• , если tail равно head, тогда буфер пуст.
• при увеличении tailПо длине буфера по модулю tail и head будут равны, тогда буфер заполнится.

Большинство реализаций сохранит индексы в пределах буфера, используя один из этих подходов:

// check if index overflowed and reset
int fifo_increment_index(struct fifo *fifo, int index)
{
     index = index + 1; 
     if (index > fifo->capacity)
         index = 0;
     return index;
}

// use the modulo operator (slower due to division,
// although it avoids branching)
int fifo_increment_index(struct fifo *fifo, int index)
{
     index = (index + 1) % fifo->capacity; // modulo
     return index;
}

// use a bitwise mask (in most cases the fastest approach),
// but works ONLY if capacity is a power of 2
int fifo_increment_index(struct fifo *fifo, int index)
{
     // if capacity is 1024 (0x400), then
     // mask will be 1023 (0x3FF)

     index = (index + 1) & fifo->mask; // bitwise and
     return index;
}

Linux kfifo использует последний подход (побитовое маскирование), поэтому всегда гарантирует, что емкость является степенью двойки внутри функции инициализации (size = roundup_pow_of_two(size)).

Тем не менее, он не сбрасывает индексы, как только они меняются, но крысыона маскирует их при каждом доступе к буферу:

#define __KFIFO_PEEK(data, out, mask) ( (data)[(out) & (mask)] )
#define __KFIFO_POKE(data, in, mask, val) ( (data)[(in) & (mask)] = (unsigned char)(val) )

Для буфера uint8_t макрос __KFIFO_PEEK в основном:

static inline uint8_t kfifo_peek(struct __kfifo *fifo)
{
     int index = fifo->out & fifo->mask;
     return fifo->data[index];
}