Re: [RFC, 2.6] a simple FIFO implementation

From: Andrew Morton
Date: Wed Sep 15 2004 - 17:33:59 EST


Stelian Pop <stelian@xxxxxxxxxx> wrote:
>
> Hi all,
>
> Is there a reason there is no API implementing a simple in-kernel
> FIFO ? A linked list is a bit overkill...
>
> +struct kfifo {
> + unsigned int head;
> + unsigned int tail;
> + unsigned int size;
> + unsigned int len;
> + spinlock_t lock;
> + unsigned char *buffer;
> +};

A circular buffer implementation needs only head and tail indices. `size'
above appears to be redundant.

Implementation-wise, the head and tail indices should *not* be constrained
to be less than the size of the buffer. They should be allowed to wrap all
the way back to zero. This allows you to distinguish between the
completely-empty and completely-full states while using 100% of the storage.

> +static inline struct kfifo *kfifo_alloc(unsigned int size) {

This should not be inlined, and the caller should pass in the gfp_flags.

> +static inline void kfifo_reset(struct kfifo *fifo) {

uninline this.

> + unsigned long flags;
> +
> + spin_lock_irqsave(&fifo->lock, flags);
> +
> + fifo->head = fifo->tail = 0;
> + fifo->len = 0;
> +
> + spin_unlock_irqrestore(&fifo->lock, flags);
> +}

The caller should provide the locking. The spinlock should be removed.

Or maybe provide a separate higher-level API which does the locking for
you.

> +static inline unsigned int kfifo_put(struct kfifo *fifo,
> + unsigned char *buffer, unsigned int len) {
> + unsigned long flags;
> + unsigned int total, remaining;
> +
> + spin_lock_irqsave(&fifo->lock, flags);
> +
> + total = remaining = min(len, fifo->size - fifo->len);
> + while (remaining > 0) {
> + unsigned int l = min(remaining, fifo->size - fifo->tail);
> + memcpy(fifo->buffer + fifo->tail, buffer, l);
> + fifo->tail += l;
> + fifo->tail %= fifo->size;
> + fifo->len += l;
> + buffer += l;
> + remaining -= l;
> + }
> +
> + spin_unlock_irqrestore(&fifo->lock, flags);
> +
> + return total;
> +}

This is too big to inline.

> +static inline unsigned int kfifo_get(struct kfifo *fifo,
> + unsigned char *buffer, unsigned int len) {
> + unsigned long flags;
> + unsigned int total, remaining;
> +
> + spin_lock_irqsave(&fifo->lock, flags);
> +
> + total = remaining = min(len, fifo->len);
> + while (remaining > 0) {
> + unsigned int l = min(remaining, fifo->size - fifo->head);
> + memcpy(buffer, fifo->buffer + fifo->head, l);
> + fifo->head += l;
> + fifo->head %= fifo->size;
> + fifo->len -= l;
> + buffer += l;
> + remaining -= l;
> + }
> +
> + spin_unlock_irqrestore(&fifo->lock, flags);
> +
> + return total;

whitespace damage

> +}

Too big to inline.

> +/*
> + * kfifo_len - returns the number of bytes available in the FIFO
> + * @fifo: the fifo to be used.
> + */
> +static inline unsigned int kfifo_len(struct kfifo *fifo) {
> + unsigned long flags;
> + unsigned int result;
> +
> + spin_lock_irqsave(&fifo->lock, flags);
> +
> + result = fifo->len;
> +
> + spin_unlock_irqrestore(&fifo->lock, flags);
> +
> + return result;
> +}

And this.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/