[RFC, 2.6] a simple FIFO implementation

[RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

Hi all,

Is there a reason there is no API implementing a simple in-kernel
FIFO ? A linked list is a bit overkill...

Besides my sonypi and meye drivers which could use this, there are
quite a few other drivers which re-implement the circular buffer
over and over again...

An initial implementation follows below. Comments ?

Thanks,

Stelian.

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-13 14:58:37.000000000 +0200
@@ -0,0 +1,179 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include <linux/spinlock.h>
+
+/*
+ * This is a simple FIFO implementation using a circular buffer.
+ */
+struct kfifo {
+	unsigned int head;
+	unsigned int tail;
+	unsigned int size;
+	unsigned int len;
+	spinlock_t lock;
+	unsigned char *buffer;
+};
+
+/*
+ * kfifo_alloc - allocates a new FIFO
+ * @size: the size of the internal buffer.
+ *
+ * Note that the allocation uses kmalloc(GFP_KERNEL).
+ */
+static inline struct kfifo *kfifo_alloc(unsigned int size) {
+	struct kfifo *fifo;
+
+	fifo = kmalloc(sizeof(struct kfifo), GFP_KERNEL);
+	if (!fifo)
+		return NULL;
+	
+	fifo->buffer = kmalloc(size, GFP_KERNEL);
+	if (!fifo->buffer) {
+		kfree(fifo);
+		return NULL;
+	}
+
+	fifo->head = fifo->tail = 0;
+	fifo->size = size;
+	fifo->len = 0;
+	fifo->lock = SPIN_LOCK_UNLOCKED;
+
+	return fifo;
+}
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+static inline void kfifo_free(struct kfifo *fifo) {
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo) {
+	unsigned long flags;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+	
+	fifo->head = fifo->tail = 0;
+	fifo->len = 0;
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+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;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+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;
+}
+
+/*
+ * 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;
+}
+
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Mon, Sep 13, 2004 at 03:52:53PM +0200, Stelian Pop wrote:

> Hi all,
> 
> Is there a reason there is no API implementing a simple in-kernel
> FIFO ? A linked list is a bit overkill...
> 
> Besides my sonypi and meye drivers which could use this, there are
> quite a few other drivers which re-implement the circular buffer
> over and over again...
> 
> An initial implementation follows below. Comments ?

Two days later, I've got no comments at all.

Is this because the idea or the implementation are just stupid ?

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Tonnerre]

[-- Attachment #1: Type: text/plain, Size: 300 bytes --]

Salut,

On Wed, Sep 15, 2004 at 12:20:03PM +0200, Stelian Pop wrote:
> Two days later, I've got no comments at all.
> 
> Is this because the idea or the implementation are just stupid ?

I will look at it Real Soon Now[tm] and consider it. But at the moment
I'm aborad.

			    Tonnerre


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC, 2.6] a simple FIFO implementation

[Alan Cox]

On Mer, 2004-09-15 at 11:20, Stelian Pop wrote:
> > An initial implementation follows below. Comments ?
> 
> Two days later, I've got no comments at all.
> 
> Is this because the idea or the implementation are just stupid ?

I certainly made no comment because it seemed completely correct and
needed no comment. If your drivers are using it I'd like to see it just
get merged

Re: [RFC, 2.6] a simple FIFO implementation

[Dmitry Torokhov]

On Monday 13 September 2004 08:52 am, Stelian Pop wrote:
> +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;
> +}

Hi,

I do not think that taking/releasing spinlock here serves any purpose as
len can get canged right after releasing the lock and therefore no longer
valid... And relying on result of kfifo_len to decide if the FIF can be
drained is not reliable so probably the inteface is better off without this
function.

Also I think that most users would put only sertain structures (homogenous?)
in their FIFOs so maybe it should be:

struct kfifo *kfifo_alloc(unsigned int el_size, unsigned int len)
unsigned int kfifo_put(struct kfifo *fifo, void *buffer)
unsigned int kfifo_get(struct kfifo *fifo, void *buffer)

Also, don't we have a rule that for functions the opening curly brace should
be on a new line?

-- 
Dmitry

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Wed, Sep 15, 2004 at 08:27:54AM -0500, Dmitry Torokhov wrote:

> On Monday 13 September 2004 08:52 am, Stelian Pop wrote:
> > +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;
> > +}
> 
> Hi,
> 
> I do not think that taking/releasing spinlock here serves any purpose as
> len can get canged right after releasing the lock and therefore no longer
> valid... 

Indeed, removed.

> And relying on result of kfifo_len to decide if the FIF can be
> drained is not reliable so probably the inteface is better off without this
> function.

Still, one should have a way to get at least a hint on whether the
FIFO has data or not (think poll() implementation).

What about adding a note in the header saying the function can be racy
and does not guarantee a subsequent kfifo_get will succeed ?

> Also I think that most users would put only sertain structures (homogenous?)
> in their FIFOs so maybe it should be:
> 
> struct kfifo *kfifo_alloc(unsigned int el_size, unsigned int len)
> unsigned int kfifo_put(struct kfifo *fifo, void *buffer)
> unsigned int kfifo_get(struct kfifo *fifo, void *buffer)

It's easy to adapt the generic interface to what you want, but difficult
to do the contrary. Let's be the most generic here (who knows, maybe 
somebody wants to add several structures at once...).

> Also, don't we have a rule that for functions the opening curly brace should
> be on a new line?

Sure, corrected.

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton]

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.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Wed, Sep 15, 2004 at 03:30:13PM -0700, Andrew Morton wrote:

> > +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.

Do you mean 'size' (the size of alloc'ed buffer) is redundant or 'len' 
(the amount of data in the FIFO) is redundant ? I see how 'len' could
be removed (and didn't do it in the first place because I choosed
code simplification over a 4 bytes gain in storage), but I hardly
see how 'size' could be removed...

> > +	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.

Like in __kfifo_get which doesn't lock and kfifo_get which does ?

I don't want to remove it completly since the whole point of this 
spinlock is to protect the fifo contents...

> This is too big to inline.
[...]
> whitespace damage
[...]

Oops. I will post an updated patch later today.

Thanks for the feedback.

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton]

Stelian Pop <stelian@popies.net> wrote:
>
> > 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.
> 
>  Do you mean 'size' (the size of alloc'ed buffer) is redundant or 'len' 
>  (the amount of data in the FIFO) is redundant ? I see how 'len' could
>  be removed (and didn't do it in the first place because I choosed
>  code simplification over a 4 bytes gain in storage), but I hardly
>  see how 'size' could be removed...

Well I'm not sure what the semantic difference is between `size' and `len'.
They're not very well-chosen identifiers, really.

My point is that there is no need to store the "number of bytes currently
in the buffer", because that is always equal to `head - tail' if you allow
those indices to freely wrap.

All the struct needs is `head', `tail' and `number_of_bytes_at_buf', all
unsigned.

add(char c)
{
	p->buf[p->head++ % p->number_of_bytes_at_buf] = c;
}

get()
{
	return p->buf[p->tail++ %  p->number_of_bytes_at_buf];
}

free_space()
{
	return p->head - p->tail;
}

pretty simple...

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 12:04:38AM -0700, Andrew Morton wrote:

> Stelian Pop <stelian@popies.net> wrote:
> >
> > > 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.
[...]

Here is the updated patch.

Changes from the previous version include:
- removed excessive inlining, extern functions go now to kernel/kfifo.c
- added __kfifo_get, __kfifo_put etc which do no locking at all
- kfifo_get/kfifo_put are now inline wrappers of the __ versions, which
  takes the spinlock to protect the fifo contents.
- corrected whitespace damage :)

> add(char c)
> {
> 	p->buf[p->head++ % p->number_of_bytes_at_buf] = c;
> }

I wonder if replacing the kfifo_get/kfifo_put implementations with
something like:

	while (remaining--)
		add(*buffer++);

instead of the memcpy() would be a gain in performance... I leaved
the memcpy() implementation for now but since the FIFOS are generally
used to buffer small structures (most of the time bytes or ints), the
character based method may be more efficient.

Stelian.

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-16 12:36:36.024185168 +0200
@@ -0,0 +1,131 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned int head;
+	unsigned int tail;
+	unsigned int size;
+	spinlock_t lock;
+	unsigned char *buffer;
+};
+
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask);
+extern void kfifo_free(struct kfifo *fifo);
+extern void __kfifo_reset(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_len(struct kfifo *fifo);
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-16 12:37:45.233663728 +0200
@@ -0,0 +1,138 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_alloc - allocates a new FIFO
+ * @size: the size of the internal buffer.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask)
+{
+	struct kfifo *fifo;
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return NULL;
+	
+	fifo->buffer = kmalloc(size, gfp_mask);
+	if (!fifo->buffer) {
+		kfree(fifo);
+		return NULL;
+	}
+
+	fifo->head = fifo->tail = 0;
+	fifo->size = size;
+	fifo->lock = SPIN_LOCK_UNLOCKED;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->head = fifo->tail = 0;
+}
+EXPORT_SYMBOL(__kfifo_reset);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int total, remaining, l;
+	
+	total = remaining = min(len, fifo->size - fifo->tail + fifo->head);
+	while (remaining > 0) {
+		l = min(remaining, fifo->size - (fifo->tail % fifo->size));
+		memcpy(fifo->buffer + (fifo->tail % fifo->size), buffer, l);
+		fifo->tail += l;
+		buffer += l;
+		remaining -= l;
+	}
+
+	return total;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int total, remaining, l;
+
+	total = remaining = min(len, fifo->tail - fifo->head);
+	while (remaining > 0) {
+		l = min(remaining, fifo->size - (fifo->head % fifo->size));
+		memcpy(buffer, fifo->buffer + (fifo->head % fifo->size), l);
+		fifo->head += l;
+		buffer += l;
+		remaining -= l;
+	}
+
+	return total;
+}
+EXPORT_SYMBOL(__kfifo_get);
+
+/*
+ * kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->tail - fifo->head;
+}
+EXPORT_SYMBOL(__kfifo_len);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.012343608 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o

-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Paul Jackson]

This still has a 'size' attribute.  As Andrew noted,
this might not be needed.

See for example:

  http://cse.stanford.edu/class/cs110/handouts/27Queues.pdf

for coding a fifo queue with just a put and get pointer.

The queue is empty if put == get, and it is full if adding one more
would make it empty.  The number of elements in the queue can be done
using modulo arithmetic on the difference between put and get (or what
the above *.pdf file and your code calls head and tail), with no
distinct 'size' element.   The head and tail wrap.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 06:57:50AM -0700, Paul Jackson wrote:

> This still has a 'size' attribute.  As Andrew noted,
> this might not be needed.

No, Andrew noted that 'len' was unneeded (although he talked about
'size', he really meant 'len' == the amount of data in the FIFO) (*)

> See for example:
> 
>   http://cse.stanford.edu/class/cs110/handouts/27Queues.pdf
> 
> for coding a fifo queue with just a put and get pointer.

... and a start and a end pointer. 

This is identical to my patch (minus the fact that 'start' is called
'buffer' in my patch and I have the 'size' field instead of an 'end'
pointer).
> 
> The queue is empty if put == get, and it is full if adding one more
> would make it empty.  The number of elements in the queue can be done
> using modulo arithmetic on the difference between put and get (or what
> the above *.pdf file and your code calls head and tail), with no
> distinct 'size' element.   The head and tail wrap.

Did you read my second patch ?

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Paul Jackson]

> Did you read my second patch ?

  Not closely enough ... ;).  Yes - your removal of 'len' does
  indeed seem to have addressed Andrews key initial comment.

> 'size' field instead of an 'end'

  The start, end, put, get names in that *.pdf might be a
  bit quicker to read.

  I suspect that more readers would come away with the right
  understanding, first time, if you struct was (taken roughly
  from the *.pdf, using an 'end' one bigger than *.pdf uses):

	/* kfifo is empty, not full, when head == tail */
	struct kfifo {
	    unsigned char *start;	/* [start, end) */
	    unsigned char *end;
	    unsigned char *head;	/* next input char goes in here */
	    unsigned char *tail;	/* next output char comes from here */
	    spinlock_t lock;
	};

  then your structure:

	struct kfifo {
	    unsigned int head;
	    unsigned int tail;
	    unsigned int size;
	    spinlock_t lock;
	    unsigned char *buffer;
	};

  Differences include names, all pointers, ordering of struct elements,
  and comments.  Perhaps some of these differences will look better to
  you than others.

> I wonder if replacing the kfifo_get/kfifo_put implementations with
> something like:

  Quite possibly.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 08:45:49AM -0700, Paul Jackson wrote:

> > 'size' field instead of an 'end'
> 
>   The start, end, put, get names in that *.pdf might be a
>   bit quicker to read.
> 
>   I suspect that more readers would come away with the right
>   understanding, first time, if you struct was (taken roughly
>   from the *.pdf, using an 'end' one bigger than *.pdf uses):
> 
> 	/* kfifo is empty, not full, when head == tail */
> 	struct kfifo {
> 	    unsigned char *start;	/* [start, end) */
> 	    unsigned char *end;
> 	    unsigned char *head;	/* next input char goes in here */
> 	    unsigned char *tail;	/* next output char comes from here */
> 	    spinlock_t lock;
> 	};
> 
>   then your structure:
> 
> 	struct kfifo {
> 	    unsigned int head;
> 	    unsigned int tail;
> 	    unsigned int size;
> 	    spinlock_t lock;
> 	    unsigned char *buffer;
> 	};
> 
>   Differences include names, all pointers,

Except that this implementation requires 'head' and 'tail' to be
constrained to be between 'start' and 'end', adding an if test instead
of arithmetic unsigned int wrap. 

> ordering of struct elements,

I could place buffer at the beginning of the struct, indeed.

>   and comments. 

And commenting the fields is of course a very good idea.

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Buddy Lucas]

On Thu, 16 Sep 2004 12:45:36 +0200, Stelian Pop <stelian@popies.net> wrote:
> On Thu, Sep 16, 2004 at 12:04:38AM -0700, Andrew Morton wrote:
> 
> > Stelian Pop <stelian@popies.net> wrote:
> > >
> > > > 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.
> [...]
> 
> Here is the updated patch.
>
[ .. ] 
>
> +unsigned int __kfifo_put(struct kfifo *fifo,
> +                        unsigned char *buffer, unsigned int len)
> +{
> +       unsigned int total, remaining, l;
> +
> +       total = remaining = min(len, fifo->size - fifo->tail + fifo->head);

I could be mistaken (long day at the office ;-) but doesn't this fail after 
wrapping?

> +       while (remaining > 0) {
> +               l = min(remaining, fifo->size - (fifo->tail % fifo->size));
> +               memcpy(fifo->buffer + (fifo->tail % fifo->size), buffer, l);
> +               fifo->tail += l;
> +               buffer += l;
> +               remaining -= l;
> +       }
> +
> +       return total;
> +}
> +EXPORT_SYMBOL(__kfifo_put);
> +
> +/*
> + * kfifo_get - gets some data from the FIFO, no locking version
> + * @fifo: the fifo to be used.
> + * @buffer: where the data must be copied.
> + * @len: the size of the destination buffer.
> + *
> + * This function copies at most 'len' bytes from the FIFO into the
> + * 'buffer' and returns the number of copied bytes.
> + */
> +unsigned int __kfifo_get(struct kfifo *fifo,
> +                        unsigned char *buffer, unsigned int len)
> +{
> +       unsigned int total, remaining, l;
> +
> +       total = remaining = min(len, fifo->tail - fifo->head);

Same here?

> +       while (remaining > 0) {
> +               l = min(remaining, fifo->size - (fifo->head % fifo->size));
> +               memcpy(buffer, fifo->buffer + (fifo->head % fifo->size), l);
> +               fifo->head += l;
> +               buffer += l;
> +               remaining -= l;
> +       }
> +
> +       return total;
> +}
> +EXPORT_SYMBOL(__kfifo_get);
> +
> +/*
> + * kfifo_len - returns the number of bytes available in the FIFO, no locking version
> + * @fifo: the fifo to be used.
> + */
> +unsigned int __kfifo_len(struct kfifo *fifo)
> +{
> +       return fifo->tail - fifo->head;
> +}
> +EXPORT_SYMBOL(__kfifo_len);
> --- linux-2.6/kernel/Makefile.orig      2004-09-16 12:27:29.012343608 +0200
> +++ linux-2.6/kernel/Makefile   2004-09-16 11:58:26.000000000 +0200
> @@ -7,7 +7,7 @@
>            sysctl.o capability.o ptrace.o timer.o user.o \
>            signal.o sys.o kmod.o workqueue.o pid.o \
>            rcupdate.o intermodule.o extable.o params.o posix-timers.o \
> -           kthread.o
> +           kthread.o kfifo.o
> 
> obj-$(CONFIG_FUTEX) += futex.o
> obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
> 
> --
> 
> 
> Stelian Pop <stelian@popies.net>
> -
> 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/
>

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 05:09:51PM +0200, Buddy Lucas wrote:

> > +       total = remaining = min(len, fifo->size - fifo->tail + fifo->head);
> 
> I could be mistaken (long day at the office ;-) but doesn't this fail after 
> wrapping?

No, because the type is *unsigned* int. 

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Buddy Lucas]

On Thu, 16 Sep 2004 17:29:19 +0200, Stelian Pop <stelian@popies.net> wrote:
> On Thu, Sep 16, 2004 at 05:09:51PM +0200, Buddy Lucas wrote:
> 
> > > +       total = remaining = min(len, fifo->size - fifo->tail + fifo->head);
> >
> > I could be mistaken (long day at the office ;-) but doesn't this fail after
> > wrapping?
> 
> No, because the type is *unsigned* int.

Indeed, that would exactly be the reason *why* this would fail. ;-) 

The expression fifo->size - fifo->tail + fifo->head might be negative
at some point, right? (fifo->head has wrapped to some small value and
fifo->tail > fifo->size)


Cheers,
Buddy

> 
> Stelian.
> --
> 
> 
> Stelian Pop <stelian@popies.net>
>

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 05:51:04PM +0200, Buddy Lucas wrote:

> > No, because the type is *unsigned* int.
> 
> Indeed, that would exactly be the reason *why* this would fail. ;-) 
> 
> The expression fifo->size - fifo->tail + fifo->head might be negative
> at some point, right? (fifo->head has wrapped to some small value and
> fifo->tail > fifo->size)

And what is the value of an unsigned int holding that 'negative' value ? :)

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Buddy Lucas]

On Thu, 16 Sep 2004 17:52:47 +0200, Stelian Pop <stelian@popies.net> wrote:
> On Thu, Sep 16, 2004 at 05:51:04PM +0200, Buddy Lucas wrote:
> 
> > > No, because the type is *unsigned* int.
> >
> > Indeed, that would exactly be the reason *why* this would fail. ;-)
> >
> > The expression fifo->size - fifo->tail + fifo->head might be negative
> > at some point, right? (fifo->head has wrapped to some small value and
> > fifo->tail > fifo->size)
> 
> And what is the value of an unsigned int holding that 'negative' value ? :)
> 

Which unsigned int?! ;-) The expression a - b is negative for unsigned
ints a and b where a < b. So, your unsigned ints "total" and
"remaining" won't be negative of
course, but they won't reflect what is actually left in the buffer;
they will equal the
value of len (in some cases) after fifo->head has wrapped (because of the 
unsignedness) and fifo->tail has not. Which would not be correct.


Cheers,
Buddy

> 
> 
> Stelian.
> --
> Stelian Pop <stelian@popies.net>
>

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 06:07:07PM +0200, Buddy Lucas wrote:

> > > Indeed, that would exactly be the reason *why* this would fail. ;-)
> > >
> > > The expression fifo->size - fifo->tail + fifo->head might be negative
> > > at some point, right? (fifo->head has wrapped to some small value and
> > > fifo->tail > fifo->size)
> > 
> > And what is the value of an unsigned int holding that 'negative' value ? :)
> > 
> 
> Which unsigned int?! ;-) The expression a - b is negative for unsigned
> ints a and b where a < b. So, your unsigned ints "total" and
> "remaining" won't be negative of
> course, but they won't reflect what is actually left in the buffer;
> they will equal the
> value of len (in some cases) after fifo->head has wrapped (because of the 
> unsignedness) and fifo->tail has not. Which would not be correct.

It is, thanks to modular arithmetic.

Let's imagine we use unsigned char instead of unsigned int (simpler
to explain), and we have a 200 bytes buffer.

At the beginning:
	head = tail = 0
We add 200 bytes:
	head = 0, tail = 200
We extract 200 bytes:
	head = 200, tail = 200
We add 200 bytes more:
	head = 200, tail = (200 + 200) % 256 = 144
Now the buffer length is:
	144 - 200 = (-56) % 256 = 200

Thanks to modular arithmetic magic, we get the correct answer: 200.

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [RFC, 2.6] a simple FIFO implementation

[Buddy Lucas]

On Thu, 16 Sep 2004 20:30:30 +0200, Stelian Pop <stelian@popies.net> wrote:
> On Thu, Sep 16, 2004 at 06:07:07PM +0200, Buddy Lucas wrote:
> 
> > > > Indeed, that would exactly be the reason *why* this would fail. ;-)
> > > >
> > > > The expression fifo->size - fifo->tail + fifo->head might be negative
> > > > at some point, right? (fifo->head has wrapped to some small value and
> > > > fifo->tail > fifo->size)
> > >
> > > And what is the value of an unsigned int holding that 'negative' value ? :)
> > >
> >
> > Which unsigned int?! ;-) The expression a - b is negative for unsigned
> > ints a and b where a < b. So, your unsigned ints "total" and
> > "remaining" won't be negative of
> > course, but they won't reflect what is actually left in the buffer;
> > they will equal the
> > value of len (in some cases) after fifo->head has wrapped (because of the
> > unsignedness) and fifo->tail has not. Which would not be correct.

Argh! Headless chicken routine.
 
> It is, thanks to modular arithmetic.
> 
> Let's imagine we use unsigned char instead of unsigned int (simpler
> to explain), and we have a 200 bytes buffer.
> 
> At the beginning:
>         head = tail = 0
> We add 200 bytes:
>         head = 0, tail = 200
> We extract 200 bytes:
>         head = 200, tail = 200
> We add 200 bytes more:
>         head = 200, tail = (200 + 200) % 256 = 144
> Now the buffer length is:
>         144 - 200 = (-56) % 256 = 200
> 
> Thanks to modular arithmetic magic, we get the correct answer: 200.

Indeed. I didn't notice you were getting at my head. ;-) 
Sorry for the noise, Stelian.

> 
> 
> Stelian.
> --
> Stelian Pop <stelian@popies.net>
>

Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton]

Stelian Pop <stelian@popies.net> wrote:
>
> Here is the updated patch.

Looks good to me.

You're using `head' as "the place from which `get' gets characters" and
you're using `tail' as "the place where `put' puts characters".  So the
FIFO is, logically:


          tail            head
    * ->  ********************   -> *
     put                         get


I've always done it the other way: you put stuff onto the head and take
stuff off the tail.  Now I have a horid feeling that I've always been
arse-about.  hrm.  

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 10:00:50AM -0700, Andrew Morton wrote:

> Stelian Pop <stelian@popies.net> wrote:
> >
> > Here is the updated patch.
> 
> Looks good to me.
> 
> You're using `head' as "the place from which `get' gets characters" and
> you're using `tail' as "the place where `put' puts characters".  So the
> FIFO is, logically:
> 
> 
>           tail            head
>     * ->  ********************   -> *
>      put                         get
> 

That was the intent, yes.

> I've always done it the other way: you put stuff onto the head and take
> stuff off the tail.  Now I have a horid feeling that I've always been
> arse-about.  hrm.  

Maybe I should use 'start' and 'end' as indices after all, they
are less subject to confusion.

Stelian.
-- 
Stelian Pop <stelian@popies.net>

Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton]

Stelian Pop <stelian@popies.net> wrote:
>
> > I've always done it the other way: you put stuff onto the head and take
> > stuff off the tail.  Now I have a horid feeling that I've always been
> > arse-about.  hrm.  
> 
> Maybe I should use 'start' and 'end' as indices after all, they
> are less subject to confusion.

`in' and `out' would be more meaningful, yes?  I'll edit the diff.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 05:18:17PM -0700, Andrew Morton wrote:

> Stelian Pop <stelian@popies.net> wrote:
> >
> > > I've always done it the other way: you put stuff onto the head and take
> > > stuff off the tail.  Now I have a horid feeling that I've always been
> > > arse-about.  hrm.  
> > 
> > Maybe I should use 'start' and 'end' as indices after all, they
> > are less subject to confusion.
> 
> `in' and `out' would be more meaningful, yes?  I'll edit the diff.

There is more than just this rename.

A third and I hope final version of the patch follows. It includes
several changes as suggested by Paul Jackson and Bill Davidsen
among others:
	- rename head/tail to in/out (data goes at 'in', gets out from 'out')
	- add some documentation to the struct kfifo fields
	- optimize __kfifo_put/__kfifo_get by removing the 
	  while() loop, the 'remaining' variable, and some 
	  unnecessary operations.
	- if the fifo becomes empty after a get() sets in = out = 0
	  so only a memcpy() will be needed not two in the next put/get.

Stelian.


Signed-off-by: Stelian Pop <stelian@popies.net>

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-17 10:23:48.000000000 +0200
@@ -0,0 +1,131 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned char *buffer;	/* the buffer holding the data */
+	unsigned int size;	/* the size of the allocated buffer */
+	unsigned int in;	/* data is added at offset (in % size) */
+	unsigned int out;	/* data is extracted from off. (out % size) */
+	spinlock_t lock;	/* protects concurrent modifications */
+};
+
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask);
+extern void kfifo_free(struct kfifo *fifo);
+extern void __kfifo_reset(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_len(struct kfifo *fifo);
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-17 10:51:26.000000000 +0200
@@ -0,0 +1,146 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_alloc - allocates a new FIFO
+ * @size: the size of the internal buffer.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask)
+{
+	struct kfifo *fifo;
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return NULL;
+	
+	fifo->buffer = kmalloc(size, gfp_mask);
+	if (!fifo->buffer) {
+		kfree(fifo);
+		return NULL;
+	}
+
+	fifo->in = fifo->out = 0;
+	fifo->size = size;
+	fifo->lock = SPIN_LOCK_UNLOCKED;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->in = fifo->out = 0;
+}
+EXPORT_SYMBOL(__kfifo_reset);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+	
+	len = min(len, fifo->size - fifo->in + fifo->out);
+
+	/* first put the data starting from fifo->in to buffer end */
+	l = min(len, fifo->size - (fifo->in % fifo->size));
+	memcpy(fifo->buffer + (fifo->in % fifo->size), buffer, l);
+
+	/* then put the rest (if any) at the beginning of the buffer */	
+	memcpy(fifo->buffer, buffer + l, len - l);
+
+	fifo->in += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+
+	len = min(len, fifo->in - fifo->out);
+
+	/* first get the data from fifo->out until the end of the buffer */
+	l = min(len, fifo->size - (fifo->out % fifo->size));
+	memcpy(buffer, fifo->buffer + (fifo->out % fifo->size), l);
+
+	/* then get the rest (if any) from the beginning of the buffer */
+	memcpy(buffer, fifo->buffer + l, len - l);
+
+	fifo->out += len;
+
+	/* if the FIFO is empty, set the indices to 0 so we don't wrap the next time */
+	if (fifo->in == fifo->out)
+		fifo->in = fifo->out = 0;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_get);
+
+/*
+ * kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->in - fifo->out;
+}
+EXPORT_SYMBOL(__kfifo_len);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.000000000 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Paul Jackson]

Stelian wrote:
> A third and I hope final version of the patch follows.

The struct kfifo is quite a bit more readable - nice.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [RFC, 2.6] a simple FIFO implementation

[Hugh Dickins]

On Fri, 17 Sep 2004, Stelian Pop wrote:
> 	- if the fifo becomes empty after a get() sets in = out = 0
> 	  so only a memcpy() will be needed not two in the next put/get.

Within the lockless __kfifo_get?  Doesn't that violate an essential
property of such a circular buffer, that the producer manipulates
only the "in" index and the consumer only the "out" index?
Within the locking version's kfifo_get wrapper, perhaps.

Hugh

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 12:44:35PM +0100, Hugh Dickins wrote:

> On Fri, 17 Sep 2004, Stelian Pop wrote:
> > 	- if the fifo becomes empty after a get() sets in = out = 0
> > 	  so only a memcpy() will be needed not two in the next put/get.
> 
> Within the lockless __kfifo_get?  Doesn't that violate an essential
> property of such a circular buffer, that the producer manipulates
> only the "in" index and the consumer only the "out" index?
> Within the locking version's kfifo_get wrapper, perhaps.

Indeed. Moved the optimization to the wrapper and added some
documentation to __kfifo_get()/__kfifo_put() saying that you don't
need extra locking if you have only one concurrent reader and one
concurrent writer.

Thanks.

Stelian.

Signed-off-by: Stelian Pop <stelian@popies.net>

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-17 14:18:16.828691528 +0200
@@ -0,0 +1,138 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned char *buffer;	/* the buffer holding the data */
+	unsigned int size;	/* the size of the allocated buffer */
+	unsigned int in;	/* data is added at offset (in % size) */
+	unsigned int out;	/* data is extracted from off. (out % size) */
+	spinlock_t lock;	/* protects concurrent modifications */
+};
+
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask);
+extern void kfifo_free(struct kfifo *fifo);
+extern void __kfifo_reset(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_len(struct kfifo *fifo);
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	/* 
+	 * optimization: if the FIFO is empty, set the indices to 0 
+	 * so we don't wrap the next time
+	 */
+	if (fifo->in == fifo->out)
+		fifo->in = fifo->out = 0;
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(&fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(&fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-17 14:20:36.355480232 +0200
@@ -0,0 +1,148 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_alloc - allocates a new FIFO
+ * @size: the size of the internal buffer.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask)
+{
+	struct kfifo *fifo;
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return NULL;
+	
+	fifo->buffer = kmalloc(size, gfp_mask);
+	if (!fifo->buffer) {
+		kfree(fifo);
+		return NULL;
+	}
+
+	fifo->in = fifo->out = 0;
+	fifo->size = size;
+	fifo->lock = SPIN_LOCK_UNLOCKED;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->in = fifo->out = 0;
+}
+EXPORT_SYMBOL(__kfifo_reset);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+	
+	len = min(len, fifo->size - fifo->in + fifo->out);
+
+	/* first put the data starting from fifo->in to buffer end */
+	l = min(len, fifo->size - (fifo->in % fifo->size));
+	memcpy(fifo->buffer + (fifo->in % fifo->size), buffer, l);
+
+	/* then put the rest (if any) at the beginning of the buffer */	
+	memcpy(fifo->buffer, buffer + l, len - l);
+
+	fifo->in += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+
+	len = min(len, fifo->in - fifo->out);
+
+	/* first get the data from fifo->out until the end of the buffer */
+	l = min(len, fifo->size - (fifo->out % fifo->size));
+	memcpy(buffer, fifo->buffer + (fifo->out % fifo->size), l);
+
+	/* then get the rest (if any) from the beginning of the buffer */
+	memcpy(buffer, fifo->buffer + l, len - l);
+
+	fifo->out += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_get);
+
+/*
+ * kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->in - fifo->out;
+}
+EXPORT_SYMBOL(__kfifo_len);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.000000000 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Duncan Sands]

> + * Note that with only one concurrent reader and one concurrent 
> + * writer, you don't need extra locking to use these functions.
                                 ^^^^^ which functions? (ambiguous)
And what does "extra locking" mean?

> +	len = min(len, fifo->size - fifo->in + fifo->out);

After all, since you are reading both in and out here, some kind of
locking is needed.

Ciao,

Duncan.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 02:37:57PM +0200, Duncan Sands wrote:

> > + * Note that with only one concurrent reader and one concurrent 
> > + * writer, you don't need extra locking to use these functions.
>                                  ^^^^^ which functions? (ambiguous)

Well, the same comment is for two adjacent functions, so I don't
think it's so ambiguous. Or s/these/this/ if you prefer.

> And what does "extra locking" mean?

Some kind of locking, like the one the wrapper kfifo_get/kfifo_put
propose.

> > +	len = min(len, fifo->size - fifo->in + fifo->out);
> 
> After all, since you are reading both in and out here, some kind of
> locking is needed.

But the order in which in and out get modified guarantees that you
will still have a coherent content (provided the assignments are 
atomic, which they are).

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Duncan Sands]

On Friday 17 September 2004 14:48, Stelian Pop wrote:
> On Fri, Sep 17, 2004 at 02:37:57PM +0200, Duncan Sands wrote:
> 
> > > + * Note that with only one concurrent reader and one concurrent 
> > > + * writer, you don't need extra locking to use these functions.
> >                                  ^^^^^ which functions? (ambiguous)
> 
> Well, the same comment is for two adjacent functions, so I don't
> think it's so ambiguous. Or s/these/this/ if you prefer.
> 
> > And what does "extra locking" mean?
> 
> Some kind of locking, like the one the wrapper kfifo_get/kfifo_put
> propose.
> 
> > > +	len = min(len, fifo->size - fifo->in + fifo->out);
> > 
> > After all, since you are reading both in and out here, some kind of
> > locking is needed.
> 
> But the order in which in and out get modified guarantees that you
> will still have a coherent content (provided the assignments are 
> atomic, which they are).

Hi Stelian, what is to stop the compiler putting, say, "in" in a register
for the process calling __kfifo_get, so that it only sees a constant
value.  Then after a while that process will think there is nothing
to get even though another process is shoving stuff into the fifo and
modifying "in".

By the way, the comment for __kfifo_get has a typo:

+ * kfifo_get - gets some data from the FIFO, no locking version
    ^^^^^^^^^ should be __kfifo_get

Ciao,

Duncan.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 03:00:35PM +0200, Duncan Sands wrote:

> > But the order in which in and out get modified guarantees that you
> > will still have a coherent content (provided the assignments are 
> > atomic, which they are).
> 
> Hi Stelian, what is to stop the compiler putting, say, "in" in a register
> for the process calling __kfifo_get, so that it only sees a constant
> value.  Then after a while that process will think there is nothing
> to get even though another process is shoving stuff into the fifo and
> modifying "in".

This can happen all right, but the buffer (or the indices) will not
get corrupt (this is what I call coherent). Its just like the __kfifo_get()
was executed entirely before the __kfifo_put().

There is no problem here.

> 
> By the way, the comment for __kfifo_get has a typo:
> 
> + * kfifo_get - gets some data from the FIFO, no locking version
>     ^^^^^^^^^ should be __kfifo_get

Same for kfifo_len, too much cut & paste here. Thanks.

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Duncan Sands]

> > Hi Stelian, what is to stop the compiler putting, say, "in" in a register
> > for the process calling __kfifo_get, so that it only sees a constant
> > value.  Then after a while that process will think there is nothing
> > to get even though another process is shoving stuff into the fifo and
> > modifying "in".
> 
> This can happen all right, but the buffer (or the indices) will not
> get corrupt (this is what I call coherent). Its just like the __kfifo_get()
> was executed entirely before the __kfifo_put().

Hi Stelian, that's not how I read the comment

+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.

so maybe it is better to avoid confusion and be more explicit here.

Ciao,

Duncan.

Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli]

this is nice, I had to write a ring buffer myself last month for
bootcache (you can find the patch on l-k searching for "bootcache"). It
was fun so I don't mind but certainly it took me a few reboots to make
it work ;)

My main issue with this is that I don't like to use kmalloc, I expect
most people will use a page anyways, I'm using alloc_page myself (and I
may want to switch to vmalloc to get a larger buffer, that's fine for
bootcache since the allocation is in a slow path). I wonder if it worth
to generalize the allocator passing down a callback or something like
that. I can still use kmalloc but it'd be just a waste of some memory
and risk fragmentation for >PAGE_SIZE (OTOH the callback as well will
waste some byte).

The other issue with the locking is that I will not need locking since
I've my own external locking used for other stuff too that serializes
the fifo as well, so I wonder if the "spinlock_t *" could as well be
passed down to kfifo_get so I won't need to allocate the spinlock
structure as well inside the kfifo.  Otherwise I could start to use such
a spinlock inside the kfifo for the external locking too (and then I
could call only the __ functions), that means guys outside your
kfifo.[ch] would use the kfifo->lock which doesn't sound that clean,
kfifo using an external lock passed down by the caller as parameter
looks more robust.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 03:15:23PM +0200, Andrea Arcangeli wrote:

> this is nice, I had to write a ring buffer myself last month for
> bootcache (you can find the patch on l-k searching for "bootcache"). It
> was fun so I don't mind but certainly it took me a few reboots to make
> it work ;)

Making the code separate helps also for testing it in usermode (minus
the lock), so I haven't had to reboot (yet) :)

> My main issue with this is that I don't like to use kmalloc, I expect
> most people will use a page anyways, I'm using alloc_page myself (and I
> may want to switch to vmalloc to get a larger buffer, that's fine for
> bootcache since the allocation is in a slow path). I wonder if it worth
> to generalize the allocator passing down a callback or something like
> that. I can still use kmalloc but it'd be just a waste of some memory
> and risk fragmentation for >PAGE_SIZE (OTOH the callback as well will
> waste some byte).

What about leaving kfifo_alloc as is (using kmalloc) and adding
	struct kfifo *kfifo_init(unsigned char *buffer, spinlock_t *lock);
	
which let's you specify the buffer and the spinlock you want to use.
Of course, one should not call kfifo_free() on such a struct kfifo...

As a special case, the spinlock can be NULL and in this case it 
allocates it. But in this case we should also make a kfifo_delete()
to deallocate the lock...

> The other issue with the locking is that I will not need locking since
> I've my own external locking used for other stuff too that serializes
> the fifo as well, so I wonder if the "spinlock_t *" could as well be
> passed down to kfifo_get so I won't need to allocate the spinlock
> structure as well inside the kfifo.  Otherwise I could start to use such
> a spinlock inside the kfifo for the external locking too (and then I
> could call only the __ functions), that means guys outside your
> kfifo.[ch] would use the kfifo->lock which doesn't sound that clean,
> kfifo using an external lock passed down by the caller as parameter
> looks more robust.

See above for the lock.

It is better to use an external lock if you want to use it for more
that just protecting the fifo. Unfortunately we cannot hide the
internal spinlock from the users, this is just C.

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli]

On Fri, Sep 17, 2004 at 03:36:58PM +0200, Stelian Pop wrote:
> What about leaving kfifo_alloc as is (using kmalloc) and adding
> 	struct kfifo *kfifo_init(unsigned char *buffer, spinlock_t *lock);
> 	
> which let's you specify the buffer and the spinlock you want to use.
> Of course, one should not call kfifo_free() on such a struct kfifo...

I guess you need to pass down the size of the buffer too.

> 
> As a special case, the spinlock can be NULL and in this case it 
> allocates it. But in this case we should also make a kfifo_delete()
> to deallocate the lock...

that's fine with me, but allocating a lock dynamically? then probably
you should force the caller to allocate it, and force it to pass it down
either in the alloc or in the init function, the caller is going to have
a bigger data structure where it will embed the kfifo structure, so it'd
be normally zerocost for the caller to allocate a lock outside the
kfifo, even if the API becomes a bit uglier, but I don't see the need of
separate slab allocation for a single spinlock. 

> that just protecting the fifo. Unfortunately we cannot hide the
> internal spinlock from the users, this is just C.

indeed ;) (should be in theory a private field)

thanks.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 03:41:45PM +0200, Andrea Arcangeli wrote:

> On Fri, Sep 17, 2004 at 03:36:58PM +0200, Stelian Pop wrote:
> > What about leaving kfifo_alloc as is (using kmalloc) and adding
> > 	struct kfifo *kfifo_init(unsigned char *buffer, spinlock_t *lock);
> > 	
> > which let's you specify the buffer and the spinlock you want to use.
> > Of course, one should not call kfifo_free() on such a struct kfifo...
> 
> I guess you need to pass down the size of the buffer too.

Of course... 

> > As a special case, the spinlock can be NULL and in this case it 
> > allocates it. But in this case we should also make a kfifo_delete()
> > to deallocate the lock...
> 
> that's fine with me, but allocating a lock dynamically? then probably
> you should force the caller to allocate it, and force it to pass it down
> either in the alloc or in the init function, the caller is going to have
> a bigger data structure where it will embed the kfifo structure, so it'd
> be normally zerocost for the caller to allocate a lock outside the
> kfifo, even if the API becomes a bit uglier, but I don't see the need of
> separate slab allocation for a single spinlock. 


Hmmm, allocating a single lock is ugly indeed, but I still want
the high level kfifo_get / kfifo_put to do the locking themselves...

We could do that by having a 'spinlock_t internal_lock' and a 
'spinlock_t * lock' fields, in struct kfifo: we always use 'lock' and
we initialize lock to either &internal_lock or to the user lock.

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli]

On Fri, Sep 17, 2004 at 04:00:21PM +0200, Stelian Pop wrote:
> We could do that by having a 'spinlock_t internal_lock' and a 
> 'spinlock_t * lock' fields, in struct kfifo: we always use 'lock' and
> we initialize lock to either &internal_lock or to the user lock.

the whole point was to save memory, this will actually waste another 4/8
(32bit/64bit) bytes...

note that you would still do the locking in your highlevel inlines, it's
just that the caller will have the responsability of allocating a lock.

Re: [RFC, 2.6] a simple FIFO implementation

[Paul Jackson]

This discussion reminds me of a fifo I did long ago, when
I had both 80386 and 68020 chips sharing the same fifo.

The key was putting both the put and get (in and out)
indices into one word, and updating them using compare
and swap (cmpxchg, I guess it's called now).

No additional locking needed.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [RFC, 2.6] a simple FIFO implementation

[James R Bruce]

On Thu, 16 Sep 2004, Andrew Morton wrote:
> My point is that there is no need to store the "number of bytes currently
> in the buffer", because that is always equal to `head - tail' if you allow
> those indices to freely wrap.
>
> All the struct needs is `head', `tail' and `number_of_bytes_at_buf', all
> unsigned.
>
> add(char c)
> {
> 	p->buf[p->head++ % p->number_of_bytes_at_buf] = c;
> }
>
> get()
> {
> 	return p->buf[p->tail++ %  p->number_of_bytes_at_buf];
> }

The "just let it wrap" approach will only work if number_of_bytes_at_buf 
is a power of two.  If it isn't, then the FIFO will skip back to zero at 
the wrong place after correctly storing 2^32 bytes.  I'll explain:

S = size of storage buffer
N = 1<<32 (or whatever size int is on a platform)

The hidden assumption is:
   a % S == (a % N) % S

But this is only true if:
   N % S == 0

Or in other words, that S is a power of two less than N.

> free_space()
> {
> 	return p->head - p->tail;
> }

This will of course always work fine, since S is not involved.

> pretty simple...

"Things should be made as simple as possible -- but no simpler."
  - Albert Einstein

IMHO restricting it to powers of two may not be so bad, and allows us to 
get away with using faster bitwise ANDs instead of modulus operations. 
Most FIFOs are probably power-of-two sizes anyway.  However, if the 
interface exports using any size, it'd better work that way, and not fail 
after working correctly for the first 4GB.

This is a perfect example of why we need a common, well tested 
implementation that all the drivers, etc. can use.  Keep up the excellent 
work :)

  - Jim Bruce

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 08:52:46AM -0400, James R Bruce wrote:

> The "just let it wrap" approach will only work if number_of_bytes_at_buf 
> is a power of two.  If it isn't, then the FIFO will skip back to zero at 
> the wrong place after correctly storing 2^32 bytes.  I'll explain:
[...]

Good catch !

> This is a perfect example of why we need a common, well tested 
> implementation that all the drivers, etc. can use.

:)

Here is take 5:
	- in kfifo_alloc(), round up to the next power of 2.
	- add kfifo_init() which lets the caller pass a preallocated 
	  buffer (but expect that the size of this buffer is a power
	  of 2).
	- the spinlock is now provided by the caller.
	- put kfifo_len and kfifo_reset back inline.

Stelian.

Signed-off-by: Stelian Pop <stelian@popies.net>

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-17 17:30:48.955634248 +0200
@@ -0,0 +1,157 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned char *buffer;	/* the buffer holding the data */
+	unsigned int size;	/* the size of the allocated buffer */
+	unsigned int in;	/* data is added at offset (in % size) */
+	unsigned int out;	/* data is extracted from off. (out % size) */
+	spinlock_t *lock;	/* protects concurrent modifications */
+};
+
+extern struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
+				int gfp_mask, spinlock_t *lock);
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask,
+				 spinlock_t *lock);
+extern void kfifo_free(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+static inline void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->in = fifo->out = 0;
+}
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	/* 
+	 * optimization: if the FIFO is empty, set the indices to 0 
+	 * so we don't wrap the next time
+	 */
+	if (fifo->in == fifo->out)
+		fifo->in = fifo->out = 0;
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * __kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+static inline unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->in - fifo->out;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-17 17:37:01.065065016 +0200
@@ -0,0 +1,174 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_init - allocates a new FIFO using a preallocated buffer
+ * @buffer: the preallocated buffer to be used.
+ * @size: the size of the internal buffer, this have to be a power of 2.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * Do NOT pass the kfifo to kfifo_free() after use ! Simply free the
+ * struct kfifo with kfree().
+ */
+struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, 
+			 int gfp_mask, spinlock_t *lock)
+{
+	unsigned int newsize;
+	struct kfifo *fifo;
+
+	/* verify that size is a power of 2 */
+	newsize = 1;
+	while (newsize < size)
+		newsize <<= 1;
+	if (newsize != size)
+		return NULL;
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return NULL;
+
+	fifo->buffer = buffer;
+	fifo->size = newsize;
+	fifo->in = fifo->out = 0;
+	fifo->lock = lock;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_init);
+
+/*
+ * kfifo_alloc - allocates a new FIFO and its internal buffer
+ * @size: the size of the internal buffer to be allocated.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * The size will be rounded-up to a power of 2.
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask, spinlock_t *lock)
+{
+	unsigned int newsize;
+	unsigned char *buffer;
+	struct kfifo *ret;
+
+	/* 
+	 * round up to the next power of 2, since our 'let the indices
+	 * wrap' tachnique works only in this case.
+	 */
+	if (size > 0x80000000)
+		return NULL;
+	newsize = 1;
+	while (newsize < size)
+		newsize <<= 1;
+
+	buffer = kmalloc(newsize, gfp_mask);
+	if (!buffer)
+		return NULL;
+
+	ret = kfifo_init(buffer, size, gfp_mask, lock);
+
+	if (!ret)
+		kfree(buffer);
+	
+	return ret;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+	
+	len = min(len, fifo->size - fifo->in + fifo->out);
+
+	/* first put the data starting from fifo->in to buffer end */
+	l = min(len, fifo->size - (fifo->in % fifo->size));
+	memcpy(fifo->buffer + (fifo->in % fifo->size), buffer, l);
+
+	/* then put the rest (if any) at the beginning of the buffer */	
+	memcpy(fifo->buffer, buffer + l, len - l);
+
+	fifo->in += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * __kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+
+	len = min(len, fifo->in - fifo->out);
+
+	/* first get the data from fifo->out until the end of the buffer */
+	l = min(len, fifo->size - (fifo->out % fifo->size));
+	memcpy(buffer, fifo->buffer + (fifo->out % fifo->size), l);
+
+	/* then get the rest (if any) from the beginning of the buffer */
+	memcpy(buffer, fifo->buffer + l, len - l);
+
+	fifo->out += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_get);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.000000000 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o

-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli]

On Fri, Sep 17, 2004 at 05:48:35PM +0200, Stelian Pop wrote:
> +	/* verify that size is a power of 2 */
> +	newsize = 1;
> +	while (newsize < size)
> +		newsize <<= 1;
> +	if (newsize != size)
> +		return NULL;

I think you mean:

	BUG_ON(size & (size-1));

;)

> +	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
> +	if (!fifo)
> +		return NULL;

this could be ERR_PTR(-ENOMEM).

> +	buffer = kmalloc(newsize, gfp_mask);
> +	if (!buffer)
> +		return NULL;

same here.

Re: [RFC, 2.6] a simple FIFO implementation

[Hugh Dickins]

On Fri, 17 Sep 2004, Stelian Pop wrote:
> + * The size will be rounded-up to a power of 2.

> +	l = min(len, fifo->size - (fifo->in % fifo->size));
> +	memcpy(fifo->buffer + (fifo->in % fifo->size), buffer, l);

> +	l = min(len, fifo->size - (fifo->out % fifo->size));
> +	memcpy(buffer, fifo->buffer + (fifo->out % fifo->size), l);

The moduli can now be replaced by faster masks "& (fifo->size - 1)".

Hugh

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 05:14:06PM +0100, Hugh Dickins wrote:

> The moduli can now be replaced by faster masks "& (fifo->size - 1)".

With this and the latest Andrea suggestions the patch is now close
to final.

Andrew, I guess you can apply this one to your tree.

Thanks.

Stelian.

Signed-off-by: Stelian Pop <stelian@popies.net>

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-17 17:30:48.000000000 +0200
@@ -0,0 +1,157 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned char *buffer;	/* the buffer holding the data */
+	unsigned int size;	/* the size of the allocated buffer */
+	unsigned int in;	/* data is added at offset (in % size) */
+	unsigned int out;	/* data is extracted from off. (out % size) */
+	spinlock_t *lock;	/* protects concurrent modifications */
+};
+
+extern struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
+				int gfp_mask, spinlock_t *lock);
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask,
+				 spinlock_t *lock);
+extern void kfifo_free(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+static inline void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->in = fifo->out = 0;
+}
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	/* 
+	 * optimization: if the FIFO is empty, set the indices to 0 
+	 * so we don't wrap the next time
+	 */
+	if (fifo->in == fifo->out)
+		fifo->in = fifo->out = 0;
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * __kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+static inline unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->in - fifo->out;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-17 22:34:08.000000000 +0200
@@ -0,0 +1,170 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/err.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_init - allocates a new FIFO using a preallocated buffer
+ * @buffer: the preallocated buffer to be used.
+ * @size: the size of the internal buffer, this have to be a power of 2.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * Do NOT pass the kfifo to kfifo_free() after use ! Simply free the
+ * struct kfifo with kfree().
+ */
+struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, 
+			 int gfp_mask, spinlock_t *lock)
+{
+	struct kfifo *fifo;
+
+	/* size must be a power of 2 */
+	BUG_ON(size & (size - 1));
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return ERR_PTR(-ENOMEM);
+
+	fifo->buffer = buffer;
+	fifo->size = size;
+	fifo->in = fifo->out = 0;
+	fifo->lock = lock;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_init);
+
+/*
+ * kfifo_alloc - allocates a new FIFO and its internal buffer
+ * @size: the size of the internal buffer to be allocated.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * The size will be rounded-up to a power of 2.
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask, spinlock_t *lock)
+{
+	unsigned int newsize;
+	unsigned char *buffer;
+	struct kfifo *ret;
+
+	/* 
+	 * round up to the next power of 2, since our 'let the indices
+	 * wrap' tachnique works only in this case.
+	 */
+	if (size > 0x80000000)
+		return ERR_PTR(-EINVAL);
+	newsize = 1;
+	while (newsize < size)
+		newsize <<= 1;
+
+	buffer = kmalloc(newsize, gfp_mask);
+	if (!buffer)
+		return ERR_PTR(-ENOMEM);
+
+	ret = kfifo_init(buffer, size, gfp_mask, lock);
+
+	if (IS_ERR(ret))
+		kfree(buffer);
+	
+	return ret;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+	
+	len = min(len, fifo->size - fifo->in + fifo->out);
+
+	/* first put the data starting from fifo->in to buffer end */
+	l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
+	memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
+
+	/* then put the rest (if any) at the beginning of the buffer */	
+	memcpy(fifo->buffer, buffer + l, len - l);
+
+	fifo->in += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * __kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+
+	len = min(len, fifo->in - fifo->out);
+
+	/* first get the data from fifo->out until the end of the buffer */
+	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
+	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
+
+	/* then get the rest (if any) from the beginning of the buffer */
+	memcpy(buffer, fifo->buffer + l, len - l);
+
+	fifo->out += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_get);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.000000000 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli]

On Fri, Sep 17, 2004 at 10:50:12PM +0200, Stelian Pop wrote:
> +	spinlock_t *lock;	/* protects concurrent modifications */

if we've to spend 4 bytes into a pointer, then we could as well have a
spinlock_t. The idea was to pass the pointer through the stack every
time we call a method of the class so no locking-memory would be
allocated at all in the kfifo struct.

Anyways if you like the above I don't mind 4 more bytes per struct
(especially in my usage that is entirely in a slow path and dynamically
allocated). we reached a state where the patch looks good enough, so we
can merge it and later over time can do further modifications
incrementally.

> +	/* 
> +	 * round up to the next power of 2, since our 'let the indices
> +	 * wrap' tachnique works only in this case.
> +	 */
> +	if (size > 0x80000000)
> +		return ERR_PTR(-EINVAL);
> +	newsize = 1;
> +	while (newsize < size)
> +		newsize <<= 1;

this could be:

	newsize = size;
	if (size & (size-1)) {
		BUG_ON(size > 0x80000000);
		newsize = 1;
		while (newsize < size)
			newsize <<= 1;
	}

so we get the fast path when people asks for PAGE_SIZE multiples.

I also wonder if a O(1) algorithm exists to roundup to the next power of
two (doesn't come to mind by memory, hmm maybe it's not that easy
problem).

Thanks Stelian. Now if you like to keep working in this area and you
would like to also change do_syslog to use your new object, more power
to you and good luck! 8)

Re: [RFC, 2.6] a simple FIFO implementation

[Ryan Cumming]

[-- Attachment #1: Type: text/plain, Size: 406 bytes --]

On Friday 17 September 2004 14:28, Andrea Arcangeli wrote:
> I also wonder if a O(1) algorithm exists to roundup to the next power of
> two (doesn't come to mind by memory, hmm maybe it's not that easy
> problem).

Assuming that the architecture has an O(1) fls() function, this should work 
for non-zero values:

inline unsigned int roundup(unsigned int x)
{
 return (1 << fls(x));
}

-Ryan

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC, 2.6] a simple FIFO implementation

[Andrea Arcangeli]

On Fri, Sep 17, 2004 at 02:54:00PM -0700, Ryan Cumming wrote:
> On Friday 17 September 2004 14:28, Andrea Arcangeli wrote:
> > I also wonder if a O(1) algorithm exists to roundup to the next power of
> > two (doesn't come to mind by memory, hmm maybe it's not that easy
> > problem).
> 
> Assuming that the architecture has an O(1) fls() function, this should work 
> for non-zero values:
> 
> inline unsigned int roundup(unsigned int x)
> {
>  return (1 << fls(x));
> }

looks good, hardware helps here ;) really I was trying to do it with
math, not with hardware but sounds like this is the best we can do.

doing it with unsigned long retval and 1UL is probably better.

This is likely a candidate to go in include/linux/kernel.h (maybe under
the name roundup_pow_of_two to avoid misunderstanding with the much more
common PAGE_SIZE roundups)

thanks!

Re: [RFC, 2.6] a simple FIFO implementation

[Ryan Cumming]

[-- Attachment #1.1: Type: text/plain, Size: 265 bytes --]

On Friday 17 September 2004 15:00, Andrea Arcangeli wrote:
> This is likely a candidate to go in include/linux/kernel.h (maybe under
> the name roundup_pow_of_two to avoid misunderstanding with the much more
> common PAGE_SIZE roundups)

How does this look?

-Ryan

[-- Attachment #1.2: roundup-pow-two.diff --]
[-- Type: text/x-diff, Size: 584 bytes --]

--- include/linux/kernel.h	2004-09-16 06:38:19.000000000 -0700
+++ include/linux/kernel.h	2004-09-17 15:12:20.598844004 -0700
@@ -12,6 +12,7 @@
 #include <linux/stddef.h>
 #include <linux/types.h>
 #include <linux/compiler.h>
+#include <linux/bitops.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
 
@@ -111,6 +112,10 @@
 	return r;
 }
 
+static inline unsigned long __attribute_pure__ roundup_pow_of_two(int x)
+{
+	return (1UL << fls(x));
+}
 
 extern int printk_ratelimit(void);
 extern int __printk_ratelimit(int ratelimit_jiffies, int ratelimit_burst);

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton]

Ryan Cumming <ryan@spitfire.gotdns.org> wrote:
>
> How does this look?
> 
>  ...
> +static inline unsigned long __attribute_pure__ roundup_pow_of_two(int x)
> +{
> +	return (1UL << fls(x));
> +}

Any reason for making the argument an integer, rather than unsigned long?

Re: [RFC, 2.6] a simple FIFO implementation

[Ryan Cumming]

[-- Attachment #1: Type: text/plain, Size: 502 bytes --]

On Friday 17 September 2004 15:35, Andrew Morton wrote:
> Ryan Cumming <ryan@spitfire.gotdns.org> wrote:
> > How does this look?
> >
> >  ...
> > +static inline unsigned long __attribute_pure__ roundup_pow_of_two(int x)
> > +{
> > + return (1UL << fls(x));
> > +}
>
> Any reason for making the argument an integer, rather than unsigned long?

I originally had it as unsigned long, but I changed it to match what fls() 
takes. Would it be better as an unsigned long despite that?

-Ryan

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC, 2.6] a simple FIFO implementation

[Ryan Cumming]

[-- Attachment #1.1: Type: text/plain, Size: 94 bytes --]

Er, sorry, the last patch was had an off-by-one error (it would round 4 up to 
8).

-Ryan

[-- Attachment #1.2: roundup-pow-two.diff --]
[-- Type: text/x-diff, Size: 588 bytes --]

--- include/linux/kernel.h	2004-09-16 06:38:19.000000000 -0700
+++ include/linux/kernel.h	2004-09-17 15:12:20.598844004 -0700
@@ -12,6 +12,7 @@
 #include <linux/stddef.h>
 #include <linux/types.h>
 #include <linux/compiler.h>
+#include <linux/bitops.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
 
@@ -111,6 +112,10 @@
 	return r;
 }
 
+static inline unsigned long __attribute_pure__ roundup_pow_of_two(int x)
+{
+	return (1UL << fls(x - 1));
+}
 
 extern int printk_ratelimit(void);
 extern int __printk_ratelimit(int ratelimit_jiffies, int ratelimit_burst);

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC, 2.6] a simple FIFO implementation

[Kyle Moffett]

On Sep 17, 2004, at 18:29, Ryan Cumming wrote:
> Er, sorry, the last patch was had an off-by-one error (it would round 
> 4 up to
> 8).
>
> +static inline unsigned long __attribute_pure__ roundup_pow_of_two(int 
> x)

This should probably be __const__, which is a stricter class of 
__pure__.
The "__pure__" attribute means it has no side effects, whereas the
"__const__" attribute means that it also _only_ depends on its 
arguments,
not on any global memory or the data at any pointers passed to it.

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a17 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$
L++++(+++) E W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+
PGP+++ t+(+++) 5 X R? tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$ r  
!y?(-)
------END GEEK CODE BLOCK------

Re: [RFC, 2.6] a simple FIFO implementation

[Ryan Cumming]

[-- Attachment #1.1: Type: text/plain, Size: 554 bytes --]

On Friday 17 September 2004 20:41, Kyle Moffett wrote:
> This should probably be __const__, which is a stricter class of
> __pure__.
> The "__pure__" attribute means it has no side effects, whereas the
> "__const__" attribute means that it also _only_ depends on its
> arguments,
> not on any global memory or the data at any pointers passed to it.

Good call. I was just copying the __pure__ from long_log2 function in 
kernel.h, which looks like it should be __const__ too.

Here's a third try, with Andrew's and your suggestions.

-Ryan

[-- Attachment #1.2: roundup-pow-two.diff --]
[-- Type: text/x-diff, Size: 599 bytes --]

--- include/linux/kernel.h	2004-09-16 06:38:19.000000000 -0700
+++ include/linux/kernel.h	2004-09-17 15:12:20.598844004 -0700
@@ -12,6 +12,7 @@
 #include <linux/stddef.h>
 #include <linux/types.h>
 #include <linux/compiler.h>
+#include <linux/bitops.h>
 #include <asm/byteorder.h>
 #include <asm/bug.h>
 
@@ -111,6 +112,10 @@
 	return r;
 }
 
+static inline unsigned long __attribute_const__ roundup_pow_of_two(unsigned long x)
+{
+	return (1UL << fls(x - 1));
+}
 
 extern int printk_ratelimit(void);
 extern int __printk_ratelimit(int ratelimit_jiffies, int ratelimit_burst);

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC, 2.6] a simple FIFO implementation

[Andrew Morton]

Andrea Arcangeli <andrea@novell.com> wrote:
>
> Thanks Stelian. Now if you like to keep working in this area and you
> would like to also change do_syslog to use your new object, more power
> to you and good luck! 8)

heh, we'll burst his brain.  log_buf has two distinct `out' indices ;)

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 11:28:47PM +0200, Andrea Arcangeli wrote:

> On Fri, Sep 17, 2004 at 10:50:12PM +0200, Stelian Pop wrote:
> > +	spinlock_t *lock;	/* protects concurrent modifications */
> 
> if we've to spend 4 bytes into a pointer, then we could as well have a
> spinlock_t. The idea was to pass the pointer through the stack every
> time we call a method of the class so no locking-memory would be
> allocated at all in the kfifo struct.

I guess if we're going to not put the spinlock at all into the kfifo
struct then there is no reason to have the high level locking functions
at all... Which is not necessarly a bad idea in fact.

Let's leave it like it is for now...

> Anyways if you like the above I don't mind 4 more bytes per struct
> (especially in my usage that is entirely in a slow path and dynamically
> allocated). 

Hmm, I wonder why one would want to _allocate_ a fifo on a fast path :)

> we reached a state where the patch looks good enough, so we
> can merge it and later over time can do further modifications
> incrementally.

Agreed. Andrew, what do you think ?

> I also wonder if a O(1) algorithm exists to roundup to the next power of
> two (doesn't come to mind by memory, hmm maybe it's not that easy
> problem).

Andrew: the attached version uses the Ryan's roundup_pow_of_two()
routine, make sure you also apply his patch if you're going to accept 
this one.

> Thanks Stelian. Now if you like to keep working in this area 

Sure, if this can be further enhanced I'm all ears !

> and you
> would like to also change do_syslog to use your new object, more power
> to you and good luck! 8)

As Andrew said, do_syslog uses two 'out' pointers and I'm not sure
using a kfifo instead of its private queue would improve something.

However, there are some fifo users (all keyboard drivers, I saw some
network drivers too) which could probably be converted to kfifo. I'll
try to do that in the next weeks if time permits.

Thanks.

Stelian.


Signed-off-by: Stelian Pop <stelian@popies.net>

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-17 17:30:48.000000000 +0200
@@ -0,0 +1,157 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned char *buffer;	/* the buffer holding the data */
+	unsigned int size;	/* the size of the allocated buffer */
+	unsigned int in;	/* data is added at offset (in % size) */
+	unsigned int out;	/* data is extracted from off. (out % size) */
+	spinlock_t *lock;	/* protects concurrent modifications */
+};
+
+extern struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
+				int gfp_mask, spinlock_t *lock);
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask,
+				 spinlock_t *lock);
+extern void kfifo_free(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+static inline void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->in = fifo->out = 0;
+}
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	/* 
+	 * optimization: if the FIFO is empty, set the indices to 0 
+	 * so we don't wrap the next time
+	 */
+	if (fifo->in == fifo->out)
+		fifo->in = fifo->out = 0;
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * __kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+static inline unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->in - fifo->out;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-20 09:35:32.420960576 +0200
@@ -0,0 +1,170 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/err.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_init - allocates a new FIFO using a preallocated buffer
+ * @buffer: the preallocated buffer to be used.
+ * @size: the size of the internal buffer, this have to be a power of 2.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * Do NOT pass the kfifo to kfifo_free() after use ! Simply free the
+ * struct kfifo with kfree().
+ */
+struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, 
+			 int gfp_mask, spinlock_t *lock)
+{
+	struct kfifo *fifo;
+
+	/* size must be a power of 2 */
+	BUG_ON(size & (size - 1));
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return ERR_PTR(-ENOMEM);
+
+	fifo->buffer = buffer;
+	fifo->size = size;
+	fifo->in = fifo->out = 0;
+	fifo->lock = lock;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_init);
+
+/*
+ * kfifo_alloc - allocates a new FIFO and its internal buffer
+ * @size: the size of the internal buffer to be allocated.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * The size will be rounded-up to a power of 2.
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask, spinlock_t *lock)
+{
+	unsigned int newsize;
+	unsigned char *buffer;
+	struct kfifo *ret;
+
+	/* 
+	 * round up to the next power of 2, since our 'let the indices
+	 * wrap' tachnique works only in this case.
+	 */
+	newsize = size;
+	if (size & (size - 1)) {
+		BUG_ON(size > 0x80000000);
+		newsize = roundup_pow_of_two(size);
+	}
+
+	buffer = kmalloc(newsize, gfp_mask);
+	if (!buffer)
+		return ERR_PTR(-ENOMEM);
+
+	ret = kfifo_init(buffer, size, gfp_mask, lock);
+
+	if (IS_ERR(ret))
+		kfree(buffer);
+	
+	return ret;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+	
+	len = min(len, fifo->size - fifo->in + fifo->out);
+
+	/* first put the data starting from fifo->in to buffer end */
+	l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
+	memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
+
+	/* then put the rest (if any) at the beginning of the buffer */	
+	memcpy(fifo->buffer, buffer + l, len - l);
+
+	fifo->in += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * __kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+
+	len = min(len, fifo->in - fifo->out);
+
+	/* first get the data from fifo->out until the end of the buffer */
+	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
+	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
+
+	/* then get the rest (if any) from the beginning of the buffer */
+	memcpy(buffer, fifo->buffer + l, len - l);
+
+	fifo->out += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_get);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.000000000 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Sasha Khapyorsky]

On Mon, 20 Sep 2004 17:14:26 +0200
Stelian Pop <stelian@popies.net> wrote:

> +unsigned int __kfifo_get(struct kfifo *fifo, 
> +			 unsigned char *buffer, unsigned int len)
> +{
> +	unsigned int l;
> +
> +	len = min(len, fifo->in - fifo->out);
> +
> +	/* first get the data from fifo->out until the end of the buffer */
> +	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
> +	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
> +
> +	/* then get the rest (if any) from the beginning of the buffer */
> +	memcpy(buffer, fifo->buffer + l, len - l);

I guess last line should be:

  memcpy(buffer + l, fifo->buffer, len - i)

Sasha.

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Mon, Sep 20, 2004 at 09:01:34PM +0300, Sasha Khapyorsky wrote:

> > +	/* then get the rest (if any) from the beginning of the buffer */
> > +	memcpy(buffer, fifo->buffer + l, len - l);
> 
> I guess last line should be:
> 
>   memcpy(buffer + l, fifo->buffer, len - i)

Of course, even the comment says so :(

Argh, how many revisions I'll have to make before getting this thing right ?
Given that each and every line in my original patch has been rewritten 
I guess we're almost there... :)

Latest and greatest version attached.

Thanks Sasha.


Signed-off-by: Stelian Pop <stelian@popies.net>

--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h	2004-09-17 17:30:48.000000000 +0200
@@ -0,0 +1,157 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+
+struct kfifo {
+	unsigned char *buffer;	/* the buffer holding the data */
+	unsigned int size;	/* the size of the allocated buffer */
+	unsigned int in;	/* data is added at offset (in % size) */
+	unsigned int out;	/* data is extracted from off. (out % size) */
+	spinlock_t *lock;	/* protects concurrent modifications */
+};
+
+extern struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size,
+				int gfp_mask, spinlock_t *lock);
+extern struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask,
+				 spinlock_t *lock);
+extern void kfifo_free(struct kfifo *fifo);
+extern unsigned int __kfifo_put(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+extern unsigned int __kfifo_get(struct kfifo *fifo, 
+				unsigned char *buffer, unsigned int len);
+
+/*
+ * __kfifo_reset - removes the entire FIFO contents, no locking version
+ * @fifo: the fifo to be emptied.
+ */
+static inline void __kfifo_reset(struct kfifo *fifo)
+{
+	fifo->in = fifo->out = 0;
+}
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	__kfifo_reset(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied. 
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_put(fifo, buffer, len);
+	
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo, 
+				     unsigned char *buffer, unsigned int len)
+{
+	unsigned long flags;
+	unsigned int ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_get(fifo, buffer, len);
+
+	/* 
+	 * optimization: if the FIFO is empty, set the indices to 0 
+	 * so we don't wrap the next time
+	 */
+	if (fifo->in == fifo->out)
+		fifo->in = fifo->out = 0;
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+/*
+ * __kfifo_len - returns the number of bytes available in the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ */
+static inline unsigned int __kfifo_len(struct kfifo *fifo)
+{
+	return fifo->in - fifo->out;
+}
+
+/*
+ * 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 ret;
+
+	spin_lock_irqsave(fifo->lock, flags);
+
+	ret = __kfifo_len(fifo);
+
+	spin_unlock_irqrestore(fifo->lock, flags);
+
+	return ret;
+}
+
+#else
+#warning "don't include kernel headers in userspace"
+#endif /* __KERNEL__ */
+#endif
--- /dev/null	2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/kernel/kfifo.c	2004-09-20 20:15:31.431779992 +0200
@@ -0,0 +1,170 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop <stelian@popies.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/err.h>
+#include <linux/kfifo.h>
+
+/*
+ * kfifo_init - allocates a new FIFO using a preallocated buffer
+ * @buffer: the preallocated buffer to be used.
+ * @size: the size of the internal buffer, this have to be a power of 2.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * Do NOT pass the kfifo to kfifo_free() after use ! Simply free the
+ * struct kfifo with kfree().
+ */
+struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, 
+			 int gfp_mask, spinlock_t *lock)
+{
+	struct kfifo *fifo;
+
+	/* size must be a power of 2 */
+	BUG_ON(size & (size - 1));
+
+	fifo = kmalloc(sizeof(struct kfifo), gfp_mask);
+	if (!fifo)
+		return ERR_PTR(-ENOMEM);
+
+	fifo->buffer = buffer;
+	fifo->size = size;
+	fifo->in = fifo->out = 0;
+	fifo->lock = lock;
+
+	return fifo;
+}
+EXPORT_SYMBOL(kfifo_init);
+
+/*
+ * kfifo_alloc - allocates a new FIFO and its internal buffer
+ * @size: the size of the internal buffer to be allocated.
+ * @gfp_mask: get_free_pages mask, passed to kmalloc()
+ * @lock: the lock to be used to protect the fifo buffer
+ *
+ * The size will be rounded-up to a power of 2.
+ */
+struct kfifo *kfifo_alloc(unsigned int size, int gfp_mask, spinlock_t *lock)
+{
+	unsigned int newsize;
+	unsigned char *buffer;
+	struct kfifo *ret;
+
+	/* 
+	 * round up to the next power of 2, since our 'let the indices
+	 * wrap' tachnique works only in this case.
+	 */
+	newsize = size;
+	if (size & (size - 1)) {
+		BUG_ON(size > 0x80000000);
+		newsize = roundup_pow_of_two(size);
+	}
+
+	buffer = kmalloc(newsize, gfp_mask);
+	if (!buffer)
+		return ERR_PTR(-ENOMEM);
+
+	ret = kfifo_init(buffer, size, gfp_mask, lock);
+
+	if (IS_ERR(ret))
+		kfree(buffer);
+	
+	return ret;
+}
+EXPORT_SYMBOL(kfifo_alloc);
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+void kfifo_free(struct kfifo *fifo)
+{
+	kfree(fifo->buffer);
+	kfree(fifo);
+}
+EXPORT_SYMBOL(kfifo_free);
+
+/*
+ * __kfifo_put - puts some data into the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_put(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+	
+	len = min(len, fifo->size - fifo->in + fifo->out);
+
+	/* first put the data starting from fifo->in to buffer end */
+	l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
+	memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
+
+	/* then put the rest (if any) at the beginning of the buffer */	
+	memcpy(fifo->buffer, buffer + l, len - l);
+
+	fifo->in += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_put);
+
+/*
+ * __kfifo_get - gets some data from the FIFO, no locking version
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ *
+ * Note that with only one concurrent reader and one concurrent 
+ * writer, you don't need extra locking to use these functions.
+ */
+unsigned int __kfifo_get(struct kfifo *fifo, 
+			 unsigned char *buffer, unsigned int len)
+{
+	unsigned int l;
+
+	len = min(len, fifo->in - fifo->out);
+
+	/* first get the data from fifo->out until the end of the buffer */
+	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
+	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);
+
+	/* then get the rest (if any) from the beginning of the buffer */
+	memcpy(buffer + l, fifo->buffer, len - l);
+
+	fifo->out += len;
+
+	return len;
+}
+EXPORT_SYMBOL(__kfifo_get);
--- linux-2.6/kernel/Makefile.orig	2004-09-16 12:27:29.000000000 +0200
+++ linux-2.6/kernel/Makefile	2004-09-16 11:58:26.000000000 +0200
@@ -7,7 +7,7 @@
 	    sysctl.o capability.o ptrace.o timer.o user.o \
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o intermodule.o extable.o params.o posix-timers.o \
-	    kthread.o
+	    kthread.o kfifo.o
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Richard B. Johnson]

Why __kfifo_put ?
    __kfifo_get ?
    ^^__________  Usually reserved for weak (hidden) references

in header files.


Cheers,
Dick Johnson
Penguin : Linux version 2.4.26 on an i686 machine (5570.56 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: [RFC, 2.6] a simple FIFO implementation

[Bill Davidsen]

Stelian Pop wrote:
> Hi all,
> 
> Is there a reason there is no API implementing a simple in-kernel
> FIFO ? A linked list is a bit overkill...
> 
> Besides my sonypi and meye drivers which could use this, there are
> quite a few other drivers which re-implement the circular buffer
> over and over again...
> 
> An initial implementation follows below. Comments ?

Many.

- you don't need both size and len, just the length
- you don't need a count of what's in the fifo, calc from tail-head
- you don't need remaining, when the tail reaches the head
   you're out of data.
- you want to do at most two memcpy operations, the loop is just
   unproductive overhead.
- if the fifo goes empty set the head and tail back to zero so you don't
   wrap (assumes doing just two memcpy ops) when you don't need to

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 11:57:34AM -0400, Bill Davidsen wrote:

> >An initial implementation follows below. Comments ?
> 
> Many.
> 
> - you don't need both size and len, just the length
> - you don't need a count of what's in the fifo, calc from tail-head

The second patch already did that.

> - you don't need remaining, when the tail reaches the head
>   you're out of data.
> - you want to do at most two memcpy operations, the loop is just
>   unproductive overhead.
> - if the fifo goes empty set the head and tail back to zero so you don't
>   wrap (assumes doing just two memcpy ops) when you don't need to

I hope the third patch (which I just posted) answers those points too.

Thanks.

Stelian.
-- 
Stelian Pop <stelian@popies.net>    

Re: [RFC, 2.6] a simple FIFO implementation

[Peter Chubb]

>>>>> "Andrew" == Andrew Morton <akpm@osdl.org> writes:


Andrew> All the struct needs is `head', `tail' and
Andrew> `number_of_bytes_at_buf', all unsigned.

Andrew> add(char c) {
Andrew>       p-> buf[p->head++ % p->number_of_bytes_at_buf] = c;
Andrew> }

This depends on how expensive % is.  On IA64, something like this:

     add(char c) {
	     int i = p->head == p->len ? p->head++ : 0;
	     p->buf[i] = c;
     }

is cheaper, as % generates a subroutine call to __modsi3.  It also is
shorter =-- 12 bundles as opposed to 15.
     


-- 
Dr Peter Chubb  http://www.gelato.unsw.edu.au  peterc AT gelato.unsw.edu.au
The technical we do immediately,  the political takes *forever*

Re: [RFC, 2.6] a simple FIFO implementation

[Chris Friesen]

Peter Chubb wrote:

> This depends on how expensive % is.  On IA64, something like this:
> 
>      add(char c) {
> 	     int i = p->head == p->len ? p->head++ : 0;
> 	     p->buf[i] = c;
>      }
> 
> is cheaper, as % generates a subroutine call to __modsi3.  It also is
> shorter =-- 12 bundles as opposed to 15.

I did a similar test once for ppc that found that an increment followed by a 
test (marked unlikely) was actually quicker in practice than modulo arithmetic. 
  The branch predictor got it right most of the time, so the test was almost free.

Chris

Re: [RFC, 2.6] a simple FIFO implementation

[Anton Blanchard]

> I did a similar test once for ppc that found that an increment followed by 
> a test (marked unlikely) was actually quicker in practice than modulo 
> arithmetic. The branch predictor got it right most of the time, so the 
>  test was almost free.

Yep x % y where y isnt constant could result in a divide which will blow
away 60+ cycles on some ppc machines. You can do a whole lot in those 60
cycles. Many memcpys for example :)

We removed all modulo arithmetic in the e1000 driver (replaced it with
if (x > y) x = 0) and managed to measure an improvement. 

Anton

Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Fri, Sep 17, 2004 at 11:00:22AM +1000, Peter Chubb wrote:

> Andrew> All the struct needs is `head', `tail' and
> Andrew> `number_of_bytes_at_buf', all unsigned.
> 
> Andrew> add(char c) {
> Andrew>       p-> buf[p->head++ % p->number_of_bytes_at_buf] = c;
> Andrew> }
> 
> This depends on how expensive % is.  On IA64, something like this:
> 
>      add(char c) {
> 	     int i = p->head == p->len ? p->head++ : 0;
> 	     p->buf[i] = c;
>      }
> 
> is cheaper, as % generates a subroutine call to __modsi3.  It also is
> shorter =-- 12 bundles as opposed to 15.

Yup, but this is when doing char-by-char operations.

When using one or two memcpy() we have only two '%' intead of 
(perhaps) many 'if's.

Of course the memcpy() has its own while() loop but since it's 
optimized in assembly (and I guess we're not going to implement
kfifo_get/put in assembly) I will stay with the memcpy + '%' version.

Stelian.
-- 
Stelian Pop <stelian@popies.net>