Date: Wed, 15 Sep 2004 15:30:13 -0700
From: Andrew Morton <akpm@osdl.org>
To: Stelian Pop <stelian@popies.net>
Cc: linux-kernel@vger.kernel.org
Subject: Re: [RFC, 2.6] a simple FIFO implementation
Message-Id: <20040915153013.32e797c8.akpm@osdl.org>
In-Reply-To: <20040913135253.GA3118@crusoe.alcove-fr>
References: <20040913135253.GA3118@crusoe.alcove-fr>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3241
Lines: 124

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.

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