Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton <akpm@osdl.org>]

Stelian Pop <stelian@popies.net> 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.