enhanced reimplemention of the kfifo API

This is a complete reimplementation of the new kfifo API, which is now really generic, type save and type definable.

...

diff -u -N -r -p linux-2.6.33-rc5.dummy/include/linux/kfifo.h linux-2.6.33-rc5.new/include/linux/kfifo.h

include/linux/kfifo.h +13 -0

+
+#define __kfifo_initializer(fifo) \
+	(typeof(fifo)) { \
+		{ \
+			{ \
+			.in	= 0, \
+			.out	= 0, \
+			.mask	= __is_kfifo_ptr(&fifo) ? \
+				  0 : \
+				  sizeof((fifo).buf)/sizeof(*(fifo).buf) - 1, \
+			.esize	= sizeof(*(fifo).buf), \
+			.data	= __is_kfifo_ptr(&fifo) ? \
+				NULL : \

include/linux/kfifo.h +13 -0

+/*
+ * DECLARE_KFIFO - macro to declare a fifo object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */
+#define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo
+
+/*
+ * DEFINE_KFIFO - macro to define and initialize a fifo
+ * @fifo: name of the declared fifo datatype
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.

include/linux/kfifo.h +7 -0

+/*
+ * kfifo_size - returns the size of the fifo in elements
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_size(fifo)	((fifo)->kfifo.mask + 1)
+
+/*

include/linux/kfifo.h +3 -0

+	__tmp->kfifo.in = __tmp->kfifo.out = 0; \
+})
+
 
...

...

include/linux/kfifo.h +11 -0

+/*
+ * kfifo_out_locked - gets some data from the fifo using a spinlock for locking
+ * @fifo: the fifo to be used.
+ * @buf: pointer to the storage buffer
+ * @n: max. number of elements to get
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro get the data from the fifo and return the numbers of elements
+ * copied.
+ */
+#define	kfifo_out_locked(fifo, buf, n, lock) \

include/linux/kfifo.h +45 -0

+/*
+ * kfifo_from_user - puts some data from user space into the fifo
+ * @fifo: the fifo to be used.
+ * @from: pointer to the data to be added.
+ * @len: the length of the data to be added.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the @from into the
+ * fifo, depending of the available space and returns -EFAULT/0
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kfifo_from_user(fifo, from, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	const void __user *__from = (from); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \
+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_from_user_r(__kfifo, __from, __len,  __copied, __recsize) : \
+	__kfifo_from_user(__kfifo, __from, __len, __copied); \
+}) \
+)
+
+/*
+ * kfifo_to_user - copies data from the fifo into user space
+ * @fifo: the fifo to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the fifo into the
+ * @to buffer and returns -EFAULT/0.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kfifo_to_user(fifo, to, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \

include/linux/kfifo.h +15 -0

+/*
+ * kfifo_dma_in_prepare - setup a scatterlist for DMA input
+ * @fifo: the fifo to be used.
+ * @sgl: pointer to the scatterlist array.
+ * @nents: number of entries in the scatterlist array
+ * @len: number of elements to transfer.
+ *
+ * This macro fills a scatterlist for DMA input.
+ * It returns the number entries in the scatterlist array
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macros.
+ */
+#define	kfifo_dma_in_prepare(fifo, sgl, nents, len) \
+({ \

...

kernel/kfifo.c +25 -0

@@ -0,0 +1,583 @@
+/*
+ * A generic kernel FIFO implementation
+ *
+ * Copyright (C) 2009/2010 Stefani Seibold <[email protected]>
+ *
+ * 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>

kernel/kfifo.c +4 -0

+int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
+		size_t esize, gfp_t gfp_mask)
+{
+	/*

kernel/kfifo.c +12 -0

+	fifo->data = kmalloc(size * esize, gfp_mask);
+
+	if (!fifo->data) {
+		fifo->mask = 0;
+		return -ENOMEM;
+	}
+
+	fifo->mask = size - 1;
+	fifo->esize = esize;
+
+	return 0;
+}

kernel/kfifo.c +28 -0

+
+int __kfifo_init(struct __kfifo *fifo, void *buffer,
+		unsigned int size, size_t esize)
+{
+	size /= esize;
+
+	if (size)
+		size = rounddown_pow_of_two(size);
+
+	if (size < 2)
+		return -EINVAL;
+
+	fifo->data = buffer;
+	fifo->in = fifo->out = 0;
+	fifo->mask = size - 1;
+	fifo->esize = esize;
+	return 0;
+}
+EXPORT_SYMBOL(__kfifo_init);
+
+static void kfifo_copy_in(struct __kfifo *fifo, const void *src,
+		unsigned int len, unsigned int off)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+
+	off &= fifo->mask;

kernel/kfifo.c +19 -0

+}
+
 
...
 
+static unsigned long kfifo_copy_from_user(struct __kfifo *fifo,
+	const void *src, unsigned int len, unsigned int off,
+	unsigned int *copied)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+	unsigned long ret;
+
+	off &= fifo->mask;
+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+

kernel/kfifo.c +56 -0

+int __kfifo_from_user(struct __kfifo *fifo, const void __user *from,
+		unsigned long len, unsigned int *copied)
+{
+	unsigned int l;
+	unsigned long ret;
+	unsigned int esize = fifo->esize;
+	int err;
+
+	if (esize != 1)
+		len /= esize;
+
+	l = kfifo_unused(fifo);
+	if (len > l)
+		len = l;
+
+	ret = kfifo_copy_from_user(fifo, from, len, fifo->in, copied);
+	if (unlikely(ret)) {
+		len -= ret;
+		err = -EFAULT;
+	}
+	else
+		err = 0;
+	fifo->in += len;
+	return err;
+}
+EXPORT_SYMBOL(__kfifo_from_user);
+
 
...
 
+static int setup_sgl_buf(struct scatterlist *sgl, void *buf, 
+		int nents, unsigned int len)
+{
+	int n;
+	unsigned int l;
+	unsigned int off;
+	struct page *page;
+
+	if (!nents)
+		return 0;
+
+	if (!len)
+		return 0;
+
+	n = 0;
+	page = virt_to_page(buf);
+	off = offset_in_page(buf);
+	l = 0;
+	
+	while(len >= l + PAGE_SIZE - off) {
+		struct page *npage;
+
+		l += PAGE_SIZE;
+		buf += PAGE_SIZE;
+		npage = virt_to_page(buf);
+		if (page_to_phys(page) != page_to_phys(npage) - l) {
+			sgl->page_link = 0;
+			sg_set_page(sgl++, page, l - off, off); 
+			if (++n == nents)

...

+/**
+ * __kfifo_peek_n internal helper function for determinate the length of
+ * the next record in the fifo
+ */

kernel/kfifo.c +13 -0

+static unsigned int __kfifo_peek_n(struct __kfifo *fifo, size_t recsize)
+{
+	unsigned int l;
+	unsigned int mask = fifo->mask;
+	unsigned char *data = fifo->data;
+
+	l = __KFIFO_PEEK(data, fifo->out, mask);
+
+	if (--recsize)
+		l |= __KFIFO_PEEK(data, fifo->out + 1, mask) << 8;
+
+	return l;
+}

...

Quoted 9 lines · On Wed, 27 Jan 2010 14:00:43 +0100 Stefani Seibold <[email protected]> wrote:

This is a complete reimplementation of the new kfifo API, which is now really generic, type save and type definable.

...

diff -u -N -r -p linux-2.6.33-rc5.dummy/include/linux/kfifo.h linux-2.6.33-rc5.new/include/linux/kfifo.h

include/linux/kfifo.h line 115

Quoted 9 lines

include/linux/kfifo.h +6 -0

 
...
 
+/*
+ * DECLARE_KFIFO_PTR - macro to declare a fifo pointer object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */

Throughout this patch the comments are in kerneldoc form, but they don't use the /** opening token, so the kerneldoc tools will ignore them.

Please fix that up and test it.

include/linux/kfifo.h line 119

Quoted 4 lines

include/linux/kfifo.h +4 -0

+#define DECLARE_KFIFO_PTR(fifo, type)	STRUCT_KFIFO_PTR(type) fifo
+
+/* helper macro */
+#define	__is_kfifo_ptr(fifo)	(sizeof(*fifo) == sizeof(struct __kfifo))

This is weird. It's a compile-time constant. What's it here for?

Quoted 13 lines

include/linux/kfifo.h +13 -0

+
+#define __kfifo_initializer(fifo) \
+	(typeof(fifo)) { \
+		{ \
+			{ \
+			.in	= 0, \
+			.out	= 0, \
+			.mask	= __is_kfifo_ptr(&fifo) ? \
+				  0 : \
+				  sizeof((fifo).buf)/sizeof(*(fifo).buf) - 1, \
+			.esize	= sizeof(*(fifo).buf), \
+			.data	= __is_kfifo_ptr(&fifo) ? \
+				NULL : \

include/linux/kfifo.h line 142

Quoted 10 lines

include/linux/kfifo.h +10 -0

+				(fifo).buf, \
+			} \
+		} \
+	}
+
+/*
+ * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
+ * @fifo: name of the declared fifo datatype
+ */
+#define INIT_KFIFO(fifo)	fifo = __kfifo_initializer(fifo)

Some versions of gcc generate quite poor code for

	struct foo f = { ... };

It would generate an instance of the struct into the stack and then would memcpy it over, iirc. Please take a look, see if that's happening with this construct (might need to use an old gcc version) and if so, see if there's a fix?

Quoted 13 lines

include/linux/kfifo.h +13 -0

+/*
+ * DECLARE_KFIFO - macro to declare a fifo object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */
+#define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo
+
+/*
+ * DEFINE_KFIFO - macro to define and initialize a fifo
+ * @fifo: name of the declared fifo datatype
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.

include/linux/kfifo.h line 166

Quoted 10 lines

include/linux/kfifo.h +10 -0

+ *
+ * Note: the macro can be used for global and local fifo data type variables
+ */
+#define DEFINE_KFIFO(fifo, type, size) \
+	DECLARE_KFIFO(fifo, type, size) = __kfifo_initializer(fifo)
+
+static inline unsigned int __must_check __kfifo_check(unsigned int val)
+{
+	return val;
+}

"check" is a poor term. Check what? For what? Unclear.

If I knew what this was supposed to check, I could suggest a better name. But it's called "check", so I don't know :(

include/linux/kfifo.h line 176

Quoted 9 lines

include/linux/kfifo.h +9 -0

+/*
+ * kfifo_initialized - Check if kfifo is initialized.
+ * @fifo: fifo to check
+ * Return %true if FIFO is initialized, otherwise %false.
+ * Assumes the fifo was 0 before.
+ *
+ * Note: for in place fifo's this macro returns alway true
+ */
+#define kfifo_initialized(fifo) ((fifo)->kfifo.data != NULL)

kfifo_initialized() is suspicious. Any code which doesn't know whether its kfifo was initialised is probably confused, lame and broken. Fortunately kfifo_initialized() is not used anywhere. Please prepare a separate patch to kill it sometime.

include/linux/kfifo.h line 182

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_esize - returns the size of the element managed by the fifo
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_esize(fifo)	((fifo)->kfifo.esize)

This doesn't seem to be used anywhere either.

include/linux/kfifo.h line 188

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_recsize - returns the size of the record length field
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_recsize(fifo)	(sizeof(*(fifo)->rectype))

Neither is this. What's going on?

Quoted 7 lines

include/linux/kfifo.h +7 -0

+/*
+ * kfifo_size - returns the size of the fifo in elements
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_size(fifo)	((fifo)->kfifo.mask + 1)
+
+/*

include/linux/kfifo.h line 206

Quoted 10 lines

include/linux/kfifo.h +10 -0

+ * kfifo_reset - removes the entire fifo content
+ * @fifo: the fifo to be used.
+ *
+ * Note: usage of kfifo_reset() is dangerous. It should be only called when the
+ * fifo is exclusived locked or when it is secured that no other thread is
+ * accessing the fifo.
+ */
+#define kfifo_reset(fifo) \
+(void)({ \
+	typeof(fifo + 1) __tmp = (fifo); \

What does the "+ 1" trick do?

Quoted 5 lines

include/linux/kfifo.h +3 -0

+	__tmp->kfifo.in = __tmp->kfifo.out = 0; \
+})
+
 
...

include/linux/kfifo.h line 361

Quoted 10 lines

include/linux/kfifo.h +9 -0

 
+/*
+ * kfifo_put - put data into the fifo
+ * @fifo: the fifo to be used.
+ * @val: the data to be added.
+ *
+ * This macro copies the given value into the fifo.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.

There are quite a few typos in the comments in this patch.

Quoted 14 lines

...

include/linux/kfifo.h +11 -0

+/*
+ * kfifo_out_locked - gets some data from the fifo using a spinlock for locking
+ * @fifo: the fifo to be used.
+ * @buf: pointer to the storage buffer
+ * @n: max. number of elements to get
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro get the data from the fifo and return the numbers of elements
+ * copied.
+ */
+#define	kfifo_out_locked(fifo, buf, n, lock) \

include/linux/kfifo.h line 563

Quoted 10 lines

include/linux/kfifo.h +10 -0

+__kfifo_check( \
+({ \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	__ret = kfifo_out(fifo, buf, n); \
+	spin_unlock_irqrestore(lock, __flags); \
+	__ret; \
+}) \
+)

This is poorly named. Generally "foo_locked" is to be called when the caller has already taken the lock. This identifier inverts that convention.

Quoted 49 lines

include/linux/kfifo.h +49 -0

+/*
+ * kfifo_from_user - puts some data from user space into the fifo
+ * @fifo: the fifo to be used.
+ * @from: pointer to the data to be added.
+ * @len: the length of the data to be added.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the @from into the
+ * fifo, depending of the available space and returns -EFAULT/0
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kfifo_from_user(fifo, from, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	const void __user *__from = (from); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \
+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_from_user_r(__kfifo, __from, __len,  __copied, __recsize) : \
+	__kfifo_from_user(__kfifo, __from, __len, __copied); \
+}) \
+)
+
+/*
+ * kfifo_to_user - copies data from the fifo into user space
+ * @fifo: the fifo to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the fifo into the
+ * @to buffer and returns -EFAULT/0.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kfifo_to_user(fifo, to, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	void __user *__to = (to); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \

include/linux/kfifo.h line 619

Quoted 6 lines

include/linux/kfifo.h +6 -0

+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_to_user_r(__kfifo, __to, __len, __copied, __recsize) : \
+	__kfifo_to_user(__kfifo, __to, __len, __copied); \
+}) \
+)

Do these have any callers?

Quoted 20 lines

include/linux/kfifo.h +20 -0

+/*
+ * kfifo_dma_in_prepare - setup a scatterlist for DMA input
+ * @fifo: the fifo to be used.
+ * @sgl: pointer to the scatterlist array.
+ * @nents: number of entries in the scatterlist array
+ * @len: number of elements to transfer.
+ *
+ * This macro fills a scatterlist for DMA input.
+ * It returns the number entries in the scatterlist array
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macros.
+ */
+#define	kfifo_dma_in_prepare(fifo, sgl, nents, len) \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	struct scatterlist *__sgl = (sgl); \
+	int __nents = (nents); \
+	unsigned int __len = (len); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \

include/linux/kfifo.h line 645

Quoted 5 lines

include/linux/kfifo.h +5 -0

+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_dma_in_prepare_r(__kfifo, __sgl, __nents, __len, __recsize) : \
+	__kfifo_dma_in_prepare(__kfifo,__sgl, __nents, __len); \
+})

Do the DMA functions have any callers? If not, why was all this stuff added?

Quoted 31 lines

...

kernel/kfifo.c +25 -0

@@ -0,0 +1,583 @@
+/*
+ * A generic kernel FIFO implementation
+ *
+ * Copyright (C) 2009/2010 Stefani Seibold <[email protected]>
+ *
+ * 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>

kernel/kfifo.c line 35

Quoted 10 lines

kernel/kfifo.c +10 -0

+#include <linux/kfifo.h>
+#include <linux/log2.h>
+#include <linux/uaccess.h>
+
+static unsigned int roundup_diff(unsigned int val, unsigned int size)
+{
+	if (size <= 1) 
+		return size;
+	return (val + size - 1) / size;
+}

Would be useful to add a comment explaining why this exists.

Can we not use existing general facilities?

Should this be added to the existing general facilities?

kernel/kfifo.c line 40

Quoted 4 lines

kernel/kfifo.c +4 -0

+static inline unsigned int kfifo_unused(struct __kfifo *fifo)
+{
+	return (fifo->mask + 1) - (fifo->in - fifo->out);
+}

hm, how does this differ from kfifo_avail()?

Should this use existing helpers such as kfifo_avail(), kfifo_len(), etc?

Quoted 4 lines

kernel/kfifo.c +4 -0

+int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
+		size_t esize, gfp_t gfp_mask)
+{
+	/*

kernel/kfifo.c line 55

Quoted 10 lines

kernel/kfifo.c +10 -0

+	 * round up to the next power of 2, since our 'let the indices
+	 * wrap' technique works only in this case.
+	 */
+	if (!is_power_of_2(size))
+		size = rounddown_pow_of_two(size);
+
+	if (size < 2)
+		return -EINVAL;
+
+	fifo->in = fifo->out = 0;

	fifo->in = 0;
	fifo->out = 0;

is usually preferred.

Quoted 12 lines

kernel/kfifo.c +12 -0

+	fifo->data = kmalloc(size * esize, gfp_mask);
+
+	if (!fifo->data) {
+		fifo->mask = 0;
+		return -ENOMEM;
+	}
+
+	fifo->mask = size - 1;
+	fifo->esize = esize;
+
+	return 0;
+}

kernel/kfifo.c line 77

Quoted 10 lines

kernel/kfifo.c +10 -0

+EXPORT_SYMBOL(__kfifo_alloc);
+
+void __kfifo_free(struct __kfifo *fifo)
+{
+	kfree(fifo);
+	fifo->data = 0;
+	fifo->mask = 0; 
+	fifo->in = fifo->out = 0;
+}
+EXPORT_SYMBOL(__kfifo_free);

err, no. This scribbles on memory after having returned it to slab!

Which implies that this code wasn't tested with suitable kernel debugging options enabled. Please absorb Documentation/SubmitChecklist.

Initialising memory to zero just prior to freeing it is lame anyway. And it can hide bugs. Just remove this and return the fifo to slab as-is.

Quoted 28 lines

kernel/kfifo.c +28 -0

+
+int __kfifo_init(struct __kfifo *fifo, void *buffer,
+		unsigned int size, size_t esize)
+{
+	size /= esize;
+
+	if (size)
+		size = rounddown_pow_of_two(size);
+
+	if (size < 2)
+		return -EINVAL;
+
+	fifo->data = buffer;
+	fifo->in = fifo->out = 0;
+	fifo->mask = size - 1;
+	fifo->esize = esize;
+	return 0;
+}
+EXPORT_SYMBOL(__kfifo_init);
+
+static void kfifo_copy_in(struct __kfifo *fifo, const void *src,
+		unsigned int len, unsigned int off)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+
+	off &= fifo->mask;

kernel/kfifo.c line 115

Quoted 10 lines

kernel/kfifo.c +10 -0

+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+
+	memcpy(fifo->data + off, src, l);
+	memcpy(fifo->data, src + l, len - l);
+	smp_wmb();

It would be better if all the barriers in this code had comments explaining why they're there. Looking at the above code it's quite hard to determine which other code the barrier is protecting the data against.

Quoted 22 lines

kernel/kfifo.c +19 -0

+}
+
 
...
 
+static unsigned long kfifo_copy_from_user(struct __kfifo *fifo,
+	const void *src, unsigned int len, unsigned int off,
+	unsigned int *copied)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+	unsigned long ret;
+
+	off &= fifo->mask;
+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+

kernel/kfifo.c line 202

Quoted 10 lines

kernel/kfifo.c +10 -0

+	ret = copy_from_user(fifo->data + off, src, l);
+	if (unlikely(ret))
+		ret = roundup_diff(ret + len - l, esize);
+	else {
+		ret = copy_from_user(fifo->data, src + l, len - l);
+		if (unlikely(ret))
+			ret = roundup_diff(ret, esize);
+	}
+	smp_wmb();
+	if (copied)

Can `copied' ever be NULL? If not, remove this test.

kernel/kfifo.c line 205

Quoted 3 lines

kernel/kfifo.c +3 -0

+		*copied = len - ret;
+	return ret;
+}

All pointers which refer to userspace should have the __user tag. And the code should be checked with sparse, please.

It's rather hard to work out the meaning of this function's return value.

Quoted 59 lines

kernel/kfifo.c +56 -0

+int __kfifo_from_user(struct __kfifo *fifo, const void __user *from,
+		unsigned long len, unsigned int *copied)
+{
+	unsigned int l;
+	unsigned long ret;
+	unsigned int esize = fifo->esize;
+	int err;
+
+	if (esize != 1)
+		len /= esize;
+
+	l = kfifo_unused(fifo);
+	if (len > l)
+		len = l;
+
+	ret = kfifo_copy_from_user(fifo, from, len, fifo->in, copied);
+	if (unlikely(ret)) {
+		len -= ret;
+		err = -EFAULT;
+	}
+	else
+		err = 0;
+	fifo->in += len;
+	return err;
+}
+EXPORT_SYMBOL(__kfifo_from_user);
+
 
...
 
+static int setup_sgl_buf(struct scatterlist *sgl, void *buf, 
+		int nents, unsigned int len)
+{
+	int n;
+	unsigned int l;
+	unsigned int off;
+	struct page *page;
+
+	if (!nents)
+		return 0;
+
+	if (!len)
+		return 0;
+
+	n = 0;
+	page = virt_to_page(buf);
+	off = offset_in_page(buf);
+	l = 0;
+	
+	while(len >= l + PAGE_SIZE - off) {
+		struct page *npage;
+
+		l += PAGE_SIZE;
+		buf += PAGE_SIZE;
+		npage = virt_to_page(buf);
+		if (page_to_phys(page) != page_to_phys(npage) - l) {
+			sgl->page_link = 0;
+			sg_set_page(sgl++, page, l - off, off); 
+			if (++n == nents)

kernel/kfifo.c line 328

Quoted 10 lines

kernel/kfifo.c +10 -0

+				return n;
+			page = npage;
+			len -= l - off;
+			l = off = 0;
+		}
+	}
+	sgl->page_link = 0;
+	sg_set_page(sgl++, page, len, off); 
+	return n + 1;
+}

Again, I just don't see why all this sg and dma stuff is here. Has it been tested?

Quoted 7 lines

...

+/**
+ * __kfifo_peek_n internal helper function for determinate the length of
+ * the next record in the fifo
+ */

This comment purports to be kerneldoc ("/**") but it isn't.

Quoted 13 lines

kernel/kfifo.c +13 -0

+static unsigned int __kfifo_peek_n(struct __kfifo *fifo, size_t recsize)
+{
+	unsigned int l;
+	unsigned int mask = fifo->mask;
+	unsigned char *data = fifo->data;
+
+	l = __KFIFO_PEEK(data, fifo->out, mask);
+
+	if (--recsize)
+		l |= __KFIFO_PEEK(data, fifo->out + 1, mask) << 8;
+
+	return l;
+}

kernel/kfifo.c line 417

Quoted 10 lines

kernel/kfifo.c +10 -0

+
+#define	__KFIFO_POKE(data, in, mask, val) \
+	( \
+	(data)[(in) & (mask)] = (unsigned char)(val) \
+	)
+
+/**
+ * __kfifo_poke_n internal helper function for storeing the length of
+ * the record into the fifo
+ */

Please check all kerneldoc stuff.

Quoted 3 lines

...

Quoted 9 lines · On Wed, 27 Jan 2010 14:00:43 +0100 Stefani Seibold <[email protected]> wrote:

This is a complete reimplementation of the new kfifo API, which is now really generic, type save and type definable.

...

diff -u -N -r -p linux-2.6.33-rc5.dummy/include/linux/kfifo.h linux-2.6.33-rc5.new/include/linux/kfifo.h

include/linux/kfifo.h line 115

Quoted 9 lines

include/linux/kfifo.h +6 -0

 
...
 
+/*
+ * DECLARE_KFIFO_PTR - macro to declare a fifo pointer object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */

Throughout this patch the comments are in kerneldoc form, but they don't use the /** opening token, so the kerneldoc tools will ignore them.

Please fix that up and test it.

include/linux/kfifo.h line 119

Quoted 4 lines

include/linux/kfifo.h +4 -0

+#define DECLARE_KFIFO_PTR(fifo, type)	STRUCT_KFIFO_PTR(type) fifo
+
+/* helper macro */
+#define	__is_kfifo_ptr(fifo)	(sizeof(*fifo) == sizeof(struct __kfifo))

This is weird. It's a compile-time constant. What's it here for?

Quoted 11 lines

include/linux/kfifo.h +10 -0

+
+#define __kfifo_initializer(fifo) \
+	(typeof(fifo)) { \
+		{ \
+			{ \
+			.in	= 0, \
+			.out	= 0, \
+			.mask	= __is_kfifo_ptr(&fifo) ? \
+				  0 : \
+				  sizeof((fifo).buf)/sizeof(*(fifo).buf) - 1, \

include/linux/kfifo.h line 137

Quoted 8 lines

include/linux/kfifo.h +8 -0

+			.esize	= sizeof(*(fifo).buf), \
+			.data	= __is_kfifo_ptr(&fifo) ? \
+				NULL : \
+				(fifo).buf, \
+			} \
+		} \
+	}
+

include/linux/kfifo.h line 142

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
+ * @fifo: name of the declared fifo datatype
+ */
+#define INIT_KFIFO(fifo)	fifo = __kfifo_initializer(fifo)

Some versions of gcc generate quite poor code for

	struct foo f = { ... };

It would generate an instance of the struct into the stack and then would memcpy it over, iirc. Please take a look, see if that's happening with this construct (might need to use an old gcc version) and if so, see if there's a fix?

Quoted 13 lines

include/linux/kfifo.h +13 -0

+/*
+ * DECLARE_KFIFO - macro to declare a fifo object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */
+#define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo
+
+/*
+ * DEFINE_KFIFO - macro to define and initialize a fifo
+ * @fifo: name of the declared fifo datatype
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.

include/linux/kfifo.h line 166

Quoted 10 lines

include/linux/kfifo.h +10 -0

+ *
+ * Note: the macro can be used for global and local fifo data type variables
+ */
+#define DEFINE_KFIFO(fifo, type, size) \
+	DECLARE_KFIFO(fifo, type, size) = __kfifo_initializer(fifo)
+
+static inline unsigned int __must_check __kfifo_check(unsigned int val)
+{
+	return val;
+}

"check" is a poor term. Check what? For what? Unclear.

If I knew what this was supposed to check, I could suggest a better name. But it's called "check", so I don't know :(

Quoted 6 lines

+/*
+ * kfifo_initialized - Check if kfifo is initialized.
+ * @fifo: fifo to check
+ * Return %true if FIFO is initialized, otherwise %false.
+ * Assumes the fifo was 0 before.
+ *

Quoted 3 lines

+ * Note: for in place fifo's this macro returns alway true
+ */
+#define kfifo_initialized(fifo) ((fifo)->kfifo.data != NULL)

kfifo_initialized() is suspicious. Any code which doesn't know whether its kfifo was initialised is probably confused, lame and broken. Fortunately kfifo_initialized() is not used anywhere. Please prepare a separate patch to kill it sometime.

include/linux/kfifo.h line 182

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_esize - returns the size of the element managed by the fifo
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_esize(fifo)	((fifo)->kfifo.esize)

This doesn't seem to be used anywhere either.

include/linux/kfifo.h line 188

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_recsize - returns the size of the record length field
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_recsize(fifo)	(sizeof(*(fifo)->rectype))

Neither is this. What's going on?

Quoted 11 lines

include/linux/kfifo.h +11 -0

+/*
+ * kfifo_size - returns the size of the fifo in elements
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_size(fifo)	((fifo)->kfifo.mask + 1)
+
+/*
+ * kfifo_reset - removes the entire fifo content
+ * @fifo: the fifo to be used.
+ *
+ * Note: usage of kfifo_reset() is dangerous. It should be only called when the

include/linux/kfifo.h line 206

Quoted 6 lines

+ * fifo is exclusived locked or when it is secured that no other thread is
+ * accessing the fifo.
+ */

include/linux/kfifo.h +3 -0

+#define kfifo_reset(fifo) \
+(void)({ \
+	typeof(fifo + 1) __tmp = (fifo); \

What does the "+ 1" trick do?

Quoted 6 lines

include/linux/kfifo.h +3 -0

+	__tmp->kfifo.in = __tmp->kfifo.out = 0; \
+})
+
 
...

Quoted 9 lines

+/*
+ * kfifo_put - put data into the fifo
+ * @fifo: the fifo to be used.
+ * @val: the data to be added.
+ *
+ * This macro copies the given value into the fifo.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.

There are quite a few typos in the comments in this patch.

Quoted 20 lines

...

include/linux/kfifo.h +17 -0

+/*
+ * kfifo_out_locked - gets some data from the fifo using a spinlock for locking
+ * @fifo: the fifo to be used.
+ * @buf: pointer to the storage buffer
+ * @n: max. number of elements to get
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro get the data from the fifo and return the numbers of elements
+ * copied.
+ */
+#define	kfifo_out_locked(fifo, buf, n, lock) \
+__kfifo_check( \
+({ \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	__ret = kfifo_out(fifo, buf, n); \

include/linux/kfifo.h line 541

Quoted 4 lines

include/linux/kfifo.h +4 -0

+	spin_unlock_irqrestore(lock, __flags); \
+	__ret; \
+}) \
+)

This is poorly named. Generally "foo_locked" is to be called when the caller has already taken the lock. This identifier inverts that convention.

Quoted 49 lines

include/linux/kfifo.h +49 -0

+/*
+ * kfifo_from_user - puts some data from user space into the fifo
+ * @fifo: the fifo to be used.
+ * @from: pointer to the data to be added.
+ * @len: the length of the data to be added.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the @from into the
+ * fifo, depending of the available space and returns -EFAULT/0
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kfifo_from_user(fifo, from, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	const void __user *__from = (from); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \
+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_from_user_r(__kfifo, __from, __len,  __copied, __recsize) : \
+	__kfifo_from_user(__kfifo, __from, __len, __copied); \
+}) \
+)
+
+/*
+ * kfifo_to_user - copies data from the fifo into user space
+ * @fifo: the fifo to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the fifo into the
+ * @to buffer and returns -EFAULT/0.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */
+#define	kfifo_to_user(fifo, to, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	void __user *__to = (to); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \

include/linux/kfifo.h line 619

Quoted 6 lines

include/linux/kfifo.h +6 -0

+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_to_user_r(__kfifo, __to, __len, __copied, __recsize) : \
+	__kfifo_to_user(__kfifo, __to, __len, __copied); \
+}) \
+)

Do these have any callers?

Quoted 20 lines

include/linux/kfifo.h +20 -0

+/*
+ * kfifo_dma_in_prepare - setup a scatterlist for DMA input
+ * @fifo: the fifo to be used.
+ * @sgl: pointer to the scatterlist array.
+ * @nents: number of entries in the scatterlist array
+ * @len: number of elements to transfer.
+ *
+ * This macro fills a scatterlist for DMA input.
+ * It returns the number entries in the scatterlist array
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macros.
+ */
+#define	kfifo_dma_in_prepare(fifo, sgl, nents, len) \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	struct scatterlist *__sgl = (sgl); \
+	int __nents = (nents); \
+	unsigned int __len = (len); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \

include/linux/kfifo.h line 645

Quoted 5 lines

include/linux/kfifo.h +5 -0

+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_dma_in_prepare_r(__kfifo, __sgl, __nents, __len, __recsize) : \
+	__kfifo_dma_in_prepare(__kfifo,__sgl, __nents, __len); \
+})

Do the DMA functions have any callers? If not, why was all this stuff added?

Quoted 31 lines

...

kernel/kfifo.c +25 -0

@@ -0,0 +1,583 @@
+/*
+ * A generic kernel FIFO implementation
+ *
+ * Copyright (C) 2009/2010 Stefani Seibold <[email protected]>
+ *
+ * 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>

kernel/kfifo.c line 35

Quoted 10 lines

kernel/kfifo.c +10 -0

+#include <linux/kfifo.h>
+#include <linux/log2.h>
+#include <linux/uaccess.h>
+
+static unsigned int roundup_diff(unsigned int val, unsigned int size)
+{
+	if (size <= 1) 
+		return size;
+	return (val + size - 1) / size;
+}

Would be useful to add a comment explaining why this exists.

Can we not use existing general facilities?

Should this be added to the existing general facilities?

kernel/kfifo.c line 40

Quoted 4 lines

kernel/kfifo.c +4 -0

+static inline unsigned int kfifo_unused(struct __kfifo *fifo)
+{
+	return (fifo->mask + 1) - (fifo->in - fifo->out);
+}

hm, how does this differ from kfifo_avail()?

Should this use existing helpers such as kfifo_avail(), kfifo_len(), etc?

Quoted 4 lines

kernel/kfifo.c +4 -0

+int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
+		size_t esize, gfp_t gfp_mask)
+{
+	/*

kernel/kfifo.c line 55

Quoted 10 lines

kernel/kfifo.c +10 -0

+	 * round up to the next power of 2, since our 'let the indices
+	 * wrap' technique works only in this case.
+	 */
+	if (!is_power_of_2(size))
+		size = rounddown_pow_of_two(size);
+
+	if (size < 2)
+		return -EINVAL;
+
+	fifo->in = fifo->out = 0;

	fifo->in = 0;
	fifo->out = 0;

is usually preferred.

Quoted 16 lines

kernel/kfifo.c +16 -0

+	fifo->data = kmalloc(size * esize, gfp_mask);
+
+	if (!fifo->data) {
+		fifo->mask = 0;
+		return -ENOMEM;
+	}
+
+	fifo->mask = size - 1;
+	fifo->esize = esize;
+
+	return 0;
+}
+EXPORT_SYMBOL(__kfifo_alloc);
+
+void __kfifo_free(struct __kfifo *fifo)
+{

kernel/kfifo.c line 77

Quoted 6 lines

kernel/kfifo.c +6 -0

+	kfree(fifo);
+	fifo->data = 0;
+	fifo->mask = 0; 
+	fifo->in = fifo->out = 0;
+}
+EXPORT_SYMBOL(__kfifo_free);

err, no. This scribbles on memory after having returned it to slab!

Which implies that this code wasn't tested with suitable kernel debugging options enabled. Please absorb Documentation/SubmitChecklist.

Initialising memory to zero just prior to freeing it is lame anyway. And it can hide bugs. Just remove this and return the fifo to slab as-is.

Quoted 35 lines

kernel/kfifo.c +35 -0

+
+int __kfifo_init(struct __kfifo *fifo, void *buffer,
+		unsigned int size, size_t esize)
+{
+	size /= esize;
+
+	if (size)
+		size = rounddown_pow_of_two(size);
+
+	if (size < 2)
+		return -EINVAL;
+
+	fifo->data = buffer;
+	fifo->in = fifo->out = 0;
+	fifo->mask = size - 1;
+	fifo->esize = esize;
+	return 0;
+}
+EXPORT_SYMBOL(__kfifo_init);
+
+static void kfifo_copy_in(struct __kfifo *fifo, const void *src,
+		unsigned int len, unsigned int off)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+
+	off &= fifo->mask;
+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+

kernel/kfifo.c line 115

Quoted 3 lines

kernel/kfifo.c +3 -0

+	memcpy(fifo->data + off, src, l);
+	memcpy(fifo->data, src + l, len - l);
+	smp_wmb();

It would be better if all the barriers in this code had comments explaining why they're there. Looking at the above code it's quite hard to determine which other code the barrier is protecting the data against.

Quoted 26 lines

kernel/kfifo.c +23 -0

+}
+
 
...
 
+static unsigned long kfifo_copy_from_user(struct __kfifo *fifo,
+	const void *src, unsigned int len, unsigned int off,
+	unsigned int *copied)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+	unsigned long ret;
+
+	off &= fifo->mask;
+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+
+	ret = copy_from_user(fifo->data + off, src, l);
+	if (unlikely(ret))
+		ret = roundup_diff(ret + len - l, esize);
+	else {

kernel/kfifo.c line 202

Quoted 6 lines

kernel/kfifo.c +6 -0

+		ret = copy_from_user(fifo->data, src + l, len - l);
+		if (unlikely(ret))
+			ret = roundup_diff(ret, esize);
+	}
+	smp_wmb();
+	if (copied)

Can `copied' ever be NULL? If not, remove this test.

kernel/kfifo.c line 205

Quoted 4 lines

kernel/kfifo.c +3 -0

+		*copied = len - ret;
+	return ret;
+}

All pointers which refer to userspace should have the __user tag. And the code should be checked with sparse, please.

It's rather hard to work out the meaning of this function's return value.

Quoted 64 lines

kernel/kfifo.c +61 -0

+int __kfifo_from_user(struct __kfifo *fifo, const void __user *from,
+		unsigned long len, unsigned int *copied)
+{
+	unsigned int l;
+	unsigned long ret;
+	unsigned int esize = fifo->esize;
+	int err;
+
+	if (esize != 1)
+		len /= esize;
+
+	l = kfifo_unused(fifo);
+	if (len > l)
+		len = l;
+
+	ret = kfifo_copy_from_user(fifo, from, len, fifo->in, copied);
+	if (unlikely(ret)) {
+		len -= ret;
+		err = -EFAULT;
+	}
+	else
+		err = 0;
+	fifo->in += len;
+	return err;
+}
+EXPORT_SYMBOL(__kfifo_from_user);
+
 
...
 
+static int setup_sgl_buf(struct scatterlist *sgl, void *buf, 
+		int nents, unsigned int len)
+{
+	int n;
+	unsigned int l;
+	unsigned int off;
+	struct page *page;
+
+	if (!nents)
+		return 0;
+
+	if (!len)
+		return 0;
+
+	n = 0;
+	page = virt_to_page(buf);
+	off = offset_in_page(buf);
+	l = 0;
+	
+	while(len >= l + PAGE_SIZE - off) {
+		struct page *npage;
+
+		l += PAGE_SIZE;
+		buf += PAGE_SIZE;
+		npage = virt_to_page(buf);
+		if (page_to_phys(page) != page_to_phys(npage) - l) {
+			sgl->page_link = 0;
+			sg_set_page(sgl++, page, l - off, off); 
+			if (++n == nents)
+				return n;
+			page = npage;
+			len -= l - off;
+			l = off = 0;
+		}

kernel/kfifo.c line 328

Quoted 5 lines

kernel/kfifo.c +5 -0

+	}
+	sgl->page_link = 0;
+	sg_set_page(sgl++, page, len, off); 
+	return n + 1;
+}

Again, I just don't see why all this sg and dma stuff is here. Has it been tested?

Quoted 7 lines

...

+/**
+ * __kfifo_peek_n internal helper function for determinate the length of
+ * the next record in the fifo
+ */

This comment purports to be kerneldoc ("/**") but it isn't.

Quoted 17 lines

kernel/kfifo.c +17 -0

+static unsigned int __kfifo_peek_n(struct __kfifo *fifo, size_t recsize)
+{
+	unsigned int l;
+	unsigned int mask = fifo->mask;
+	unsigned char *data = fifo->data;
+
+	l = __KFIFO_PEEK(data, fifo->out, mask);
+
+	if (--recsize)
+		l |= __KFIFO_PEEK(data, fifo->out + 1, mask) << 8;
+
+	return l;
+}
+
+#define	__KFIFO_POKE(data, in, mask, val) \
+	( \
+	(data)[(in) & (mask)] = (unsigned char)(val) \

kernel/kfifo.c line 417

Quoted 6 lines

kernel/kfifo.c +6 -0

+	)
+
+/**
+ * __kfifo_poke_n internal helper function for storeing the length of
+ * the record into the fifo
+ */

Please check all kerneldoc stuff.

Am Mittwoch, den 03.02.2010, 12:05 -0800 schrieb Andrew Morton:

Quoted 25 lines

Quoted 9 lines · On Wed, 27 Jan 2010 14:00:43 +0100 Stefani Seibold <[email protected]> wrote:

This is a complete reimplementation of the new kfifo API, which is now really generic, type save and type definable.

...

diff -u -N -r -p linux-2.6.33-rc5.dummy/include/linux/kfifo.h linux-2.6.33-rc5.new/include/linux/kfifo.h

include/linux/kfifo.h line 115

Quoted 9 lines

include/linux/kfifo.h +6 -0

 
...
 
+/*
+ * DECLARE_KFIFO_PTR - macro to declare a fifo pointer object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */

Throughout this patch the comments are in kerneldoc form, but they don't use the /** opening token, so the kerneldoc tools will ignore them.

Quoted 8 lines

Please fix that up and test it.

include/linux/kfifo.h line 119

Quoted 4 lines

include/linux/kfifo.h +4 -0

+#define DECLARE_KFIFO_PTR(fifo, type)	STRUCT_KFIFO_PTR(type) fifo
+
+/* helper macro */
+#define	__is_kfifo_ptr(fifo)	(sizeof(*fifo) == sizeof(struct __kfifo))

This is weird. It's a compile-time constant. What's it here for?

I need it to distinguish between real in place fifo, where the fifo array is a part of the structure, and the fifo type where the array is outside of the fifo structure.

Quoted 10 lines

include/linux/kfifo.h line 142

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
+ * @fifo: name of the declared fifo datatype
+ */
+#define INIT_KFIFO(fifo)	fifo = __kfifo_initializer(fifo)

Some versions of gcc generate quite poor code for

	struct foo f = { ... };

Quoted 5 lines

It would generate an instance of the struct into the stack and then would memcpy it over, iirc. Please take a look, see if that's happening with this construct (might need to use an old gcc version) and if so, see if there's a fix?

The current version of the kfifo implementation did it in the same way. Why is it now wrong?

Which gcc version do you mean?

Quoted 6 lines

Quoted 6 lines

+/*
+ * kfifo_initialized - Check if kfifo is initialized.
+ * @fifo: fifo to check
+ * Return %true if FIFO is initialized, otherwise %false.
+ * Assumes the fifo was 0 before.
+ *

Quoted 9 lines

Quoted 3 lines

+ * Note: for in place fifo's this macro returns alway true
+ */
+#define kfifo_initialized(fifo) ((fifo)->kfifo.data != NULL)

kfifo_initialized() is suspicious. Any code which doesn't know whether its kfifo was initialised is probably confused, lame and broken. Fortunately kfifo_initialized() is not used anywhere. Please prepare a separate patch to kill it sometime.

This function was introduced as a patch by andi kleen and you have it already applied.

Quoted 8 lines

include/linux/kfifo.h line 182

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_esize - returns the size of the element managed by the fifo
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_esize(fifo)	((fifo)->kfifo.esize)

This doesn't seem to be used anywhere either.

It is a part of the API. It returns the the size of the handled element, If a driver developer need it, it is there.

Quoted 8 lines

include/linux/kfifo.h line 188

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_recsize - returns the size of the record length field
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_recsize(fifo)	(sizeof(*(fifo)->rectype))

Neither is this. What's going on?

Dito... This returns the size of the record length field. 0 means this is not a variable record fifo.

Quoted 17 lines

Quoted 17 lines

include/linux/kfifo.h +17 -0

+/*
+ * kfifo_out_locked - gets some data from the fifo using a spinlock for locking
+ * @fifo: the fifo to be used.
+ * @buf: pointer to the storage buffer
+ * @n: max. number of elements to get
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro get the data from the fifo and return the numbers of elements
+ * copied.
+ */
+#define	kfifo_out_locked(fifo, buf, n, lock) \
+__kfifo_check( \
+({ \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	__ret = kfifo_out(fifo, buf, n); \

Quoted 9 lines

include/linux/kfifo.h line 541

Quoted 4 lines

include/linux/kfifo.h +4 -0

+	spin_unlock_irqrestore(lock, __flags); \
+	__ret; \
+}) \
+)

This is poorly named. Generally "foo_locked" is to be called when the caller has already taken the lock. This identifier inverts that convention.

This is the same name as the current kfifo API. Renaming it would break a lot of drivers. But if there is no complain and you insist i will rename it and fix the current users.

Quoted 19 lines

Quoted 19 lines

+ * @fifo: the fifo to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the fifo into the
+ * @to buffer and returns -EFAULT/0.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */

include/linux/kfifo.h +8 -0

+#define	kfifo_to_user(fifo, to, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \
+	void __user *__to = (to); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \

Quoted 9 lines

include/linux/kfifo.h line 619

Quoted 6 lines

include/linux/kfifo.h +6 -0

+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_to_user_r(__kfifo, __to, __len, __copied, __recsize) : \
+	__kfifo_to_user(__kfifo, __to, __len, __copied); \
+}) \
+)

Do these have any callers?

Currently not, but this is a part of the current kfifo implementation. A lot of developer like this idea and it will be used in the near future.

Quoted 7 lines

include/linux/kfifo.h

Quoted 4 lines

include/linux/kfifo.h +4 -0

+static inline unsigned int kfifo_unused(struct __kfifo *fifo)
+{
+	return (fifo->mask + 1) - (fifo->in - fifo->out);
+}

hm, how does this differ from kfifo_avail()?

This is similar to kfifo_avail, but due the nature of macro and type conversation i have not longer the original type information available. So i can't call the macros in kfifo.h from the functions defined in kfifo.c.

Quoted 21 lines

Quoted 21 lines

include/linux/kfifo.h +21 -0

+static unsigned long kfifo_copy_from_user(struct __kfifo *fifo,
+	const void *src, unsigned int len, unsigned int off,
+	unsigned int *copied)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+	unsigned long ret;
+
+	off &= fifo->mask;
+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+
+	ret = copy_from_user(fifo->data + off, src, l);
+	if (unlikely(ret))
+		ret = roundup_diff(ret + len - l, esize);
+	else {

Quoted 8 lines

include/linux/kfifo.h

Quoted 6 lines

include/linux/kfifo.h +6 -0

+		ret = copy_from_user(fifo->data, src + l, len - l);
+		if (unlikely(ret))
+			ret = roundup_diff(ret, esize);
+	}
+	smp_wmb();
+	if (copied)

Can `copied' ever be NULL? If not, remove this test.

It was only a feature. If you don't like i will remove it.

Quoted 35 lines · On Wed, 03 Feb 2010 23:09:51 +0100 Stefani Seibold <[email protected]> wrote:

Am Mittwoch, den 03.02.2010, 12:05 -0800 schrieb Andrew Morton:

Quoted 33 lines

Quoted 9 lines · On Wed, 27 Jan 2010 14:00:43 +0100 Stefani Seibold <[email protected]> wrote:

This is a complete reimplementation of the new kfifo API, which is now really generic, type save and type definable.

...

diff -u -N -r -p linux-2.6.33-rc5.dummy/include/linux/kfifo.h linux-2.6.33-rc5.new/include/linux/kfifo.h

include/linux/kfifo.h line 115

Quoted 9 lines

include/linux/kfifo.h +6 -0

 
...
 
+/*
+ * DECLARE_KFIFO_PTR - macro to declare a fifo pointer object
+ * @fifo: name of the declared fifo
+ * @type: type of the fifo elements
+ * @size: the number of elements in the fifo, this must be a power of 2.
+ */

Throughout this patch the comments are in kerneldoc form, but they don't use the /** opening token, so the kerneldoc tools will ignore them.

Please fix that up and test it.

include/linux/kfifo.h line 119

Quoted 4 lines

include/linux/kfifo.h +4 -0

+#define DECLARE_KFIFO_PTR(fifo, type)	STRUCT_KFIFO_PTR(type) fifo
+
+/* helper macro */
+#define	__is_kfifo_ptr(fifo)	(sizeof(*fifo) == sizeof(struct __kfifo))

This is weird. It's a compile-time constant. What's it here for?

Quoted 3 lines

I need it to distinguish between real in place fifo, where the fifo array is a part of the structure, and the fifo type where the array is outside of the fifo structure.

OK, please add a comment?

Quoted 11 lines

Quoted 11 lines

include/linux/kfifo.h line 142

Quoted 6 lines

include/linux/kfifo.h +5 -0

+/*
+ * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
+ * @fifo: name of the declared fifo datatype
+ */
+#define INIT_KFIFO(fifo)	fifo = __kfifo_initializer(fifo)

Some versions of gcc generate quite poor code for

	struct foo f = { ... };

Quoted 8 lines

Quoted 5 lines

It would generate an instance of the struct into the stack and then would memcpy it over, iirc. Please take a look, see if that's happening with this construct (might need to use an old gcc version) and if so, see if there's a fix?

The current version of the kfifo implementation did it in the same way. Why is it now wrong?

It was wrong before, too.

Quoted 1 line

Which gcc version do you mean?

I don't recall. The oldest gcc the kernel permits is 3.2, so checking any 3.x should be OK.

Quoted 16 lines

Quoted 15 lines

include/linux/kfifo.h line 176

Quoted 9 lines

include/linux/kfifo.h +9 -0

+/*
+ * kfifo_initialized - Check if kfifo is initialized.
+ * @fifo: fifo to check
+ * Return %true if FIFO is initialized, otherwise %false.
+ * Assumes the fifo was 0 before.
+ *
+ * Note: for in place fifo's this macro returns alway true
+ */
+#define kfifo_initialized(fifo) ((fifo)->kfifo.data != NULL)

kfifo_initialized() is suspicious. Any code which doesn't know whether its kfifo was initialised is probably confused, lame and broken. Fortunately kfifo_initialized() is not used anywhere. Please prepare a separate patch to kill it sometime.

Quoted 2 lines

This function was introduced as a patch by andi kleen and you have it already applied.

Let's delete it?

Quoted 9 lines

Quoted 8 lines

include/linux/kfifo.h line 182

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_esize - returns the size of the element managed by the fifo
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_esize(fifo)	((fifo)->kfifo.esize)

This doesn't seem to be used anywhere either.

Quoted 2 lines

It is a part of the API. It returns the the size of the handled element, If a driver developer need it, it is there.

Well, if there's no proven need for it now, it will remain dead code for an unknown period of time.

Also, there was no need to implement this as a macro (was there?). If not, conversion to a more typesafe C function would be better.

Quoted 11 lines

Quoted 8 lines

include/linux/kfifo.h line 188

Quoted 5 lines

include/linux/kfifo.h +5 -0

+/*
+ * kfifo_recsize - returns the size of the record length field
+ * @fifo: the fifo to be used.
+ */
+#define kfifo_recsize(fifo)	(sizeof(*(fifo)->rectype))

Neither is this. What's going on?

Dito... This returns the size of the record length field. 0 means this is not a variable record fifo.

ditto.

Quoted 27 lines

Quoted 17 lines

Quoted 17 lines

include/linux/kfifo.h +17 -0

+/*
+ * kfifo_out_locked - gets some data from the fifo using a spinlock for locking
+ * @fifo: the fifo to be used.
+ * @buf: pointer to the storage buffer
+ * @n: max. number of elements to get
+ * @lock: pointer to the spinlock to use for locking.
+ *
+ * This macro get the data from the fifo and return the numbers of elements
+ * copied.
+ */
+#define	kfifo_out_locked(fifo, buf, n, lock) \
+__kfifo_check( \
+({ \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	__ret = kfifo_out(fifo, buf, n); \

Quoted 9 lines

include/linux/kfifo.h line 541

Quoted 4 lines

include/linux/kfifo.h +4 -0

+	spin_unlock_irqrestore(lock, __flags); \
+	__ret; \
+}) \
+)

This is poorly named. Generally "foo_locked" is to be called when the caller has already taken the lock. This identifier inverts that convention.

Quoted 3 lines

This is the same name as the current kfifo API. Renaming it would break a lot of drivers. But if there is no complain and you insist i will rename it and fix the current users.

argh, we goofed.

yeah, it'd be nice to fix it sometime, please. Not urgent.

A good way to fix it would be to add a new function with a new name then migrate all callers over to that name then when it's done, remove the old name.

Quoted 29 lines

Quoted 28 lines

Quoted 15 lines

+ * @fifo: the fifo to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ * @copied: pointer to output variable to store the number of copied bytes.
+ *
+ * This macro copies at most @len bytes from the fifo into the
+ * @to buffer and returns -EFAULT/0.
+ *
+ * Note that with only one concurrent reader and one concurrent
+ * writer, you don't need extra locking to use these macro.
+ */

include/linux/kfifo.h +4 -0

+#define	kfifo_to_user(fifo, to, len, copied) \
+__kfifo_check( \
+({ \
+	typeof(fifo + 1) __tmp = (fifo); \

include/linux/kfifo.h line 619

Quoted 10 lines

include/linux/kfifo.h +10 -0

+	void __user *__to = (to); \
+	unsigned int __len = (len); \
+	unsigned int *__copied = (copied); \
+	const size_t __recsize = sizeof(*__tmp->rectype); \
+	struct __kfifo *__kfifo = &__tmp->kfifo; \
+	(__recsize) ? \
+	__kfifo_to_user_r(__kfifo, __to, __len, __copied, __recsize) : \
+	__kfifo_to_user(__kfifo, __to, __len, __copied); \
+}) \
+)

Do these have any callers?

Quoted 2 lines

Currently not, but this is a part of the current kfifo implementation. A lot of developer like this idea and it will be used in the near future.

OK. Please describe the presently-unused interfaces in the changelog, with particular attention to the reason for including them at this time.

Quoted 8 lines

Quoted 7 lines

include/linux/kfifo.h

Quoted 4 lines

include/linux/kfifo.h +4 -0

+static inline unsigned int kfifo_unused(struct __kfifo *fifo)
+{
+	return (fifo->mask + 1) - (fifo->in - fifo->out);
+}

hm, how does this differ from kfifo_avail()?

Quoted 4 lines

This is similar to kfifo_avail, but due the nature of macro and type conversation i have not longer the original type information available. So i can't call the macros in kfifo.h from the functions defined in kfifo.c.

OK, please add a comment there. (As a general rule: if this reader needed more info then other readers will want more info as well).

Quoted 30 lines

Quoted 29 lines

Quoted 17 lines

include/linux/kfifo.h +17 -0

+static unsigned long kfifo_copy_from_user(struct __kfifo *fifo,
+	const void *src, unsigned int len, unsigned int off,
+	unsigned int *copied)
+{
+	unsigned int size = fifo->mask + 1;
+	unsigned int esize = fifo->esize;
+	unsigned int l;
+	unsigned long ret;
+
+	off &= fifo->mask;
+	if (esize != 1) {
+		off *= esize;
+		size *= esize;
+		len *= esize;
+	}
+	l = min(len, size - off);
+

include/linux/kfifo.h

Quoted 10 lines

include/linux/kfifo.h +10 -0

+	ret = copy_from_user(fifo->data + off, src, l);
+	if (unlikely(ret))
+		ret = roundup_diff(ret + len - l, esize);
+	else {
+		ret = copy_from_user(fifo->data, src + l, len - l);
+		if (unlikely(ret))
+			ret = roundup_diff(ret, esize);
+	}
+	smp_wmb();
+	if (copied)

Can `copied' ever be NULL? If not, remove this test.

Quoted 1 line

It was only a feature. If you don't like i will remove it.

No strong opinion. But if present callers don't pass NULL then that's a sign that future callers won't, too. We may as well save the speed/space overhead until we actually need it.

...

Quoted 25 lines

Quoted 17 lines

Quoted 7 lines

Quoted 7 lines

include/linux/kfifo.h +7 -0

+#define	kfifo_out_locked(fifo, buf, n, lock) \
+__kfifo_check( \
+({ \
+	unsigned long __flags; \
+	unsigned int __ret; \
+	spin_lock_irqsave(lock, __flags); \
+	__ret = kfifo_out(fifo, buf, n); \

Quoted 9 lines

include/linux/kfifo.h line 541

Quoted 4 lines

include/linux/kfifo.h +4 -0

+	spin_unlock_irqrestore(lock, __flags); \
+	__ret; \
+}) \
+)

This is poorly named. Generally "foo_locked" is to be called when the caller has already taken the lock. This identifier inverts that convention.

Quoted 3 lines

This is the same name as the current kfifo API. Renaming it would break a lot of drivers. But if there is no complain and you insist i will rename it and fix the current users.

argh, we goofed.

yeah, it'd be nice to fix it sometime, please. Not urgent.

Quoted 4 lines

A good way to fix it would be to add a new function with a new name then migrate all callers over to that name then when it's done, remove the old name.

I will do this in the next release. Would be kfifo_out_spinlocked() and kfifo_in_spinlocked() for the new names okay?

One offer to solve the egg and chicken problem: Let us include the functions kfifo_to_user(), kfifo_from_user(), kfifo_esize(), kfifo_recsize() and the dynamic record handling. If there will be no users in at least 9 months we remove it from the API. We talk here about 400 bytes of code.

In the mean time me and other developer will have a change to modify the existing driver to the new API and/or post drivers or core kernel code which is using this functionality.