[PATCH] [0/6] kfifo fixes/improvements

[PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

While porting some of my code to kfifo I found some issues, which
are addressed in the following patch series.

Some of the problems were serious, particularly the non atomic kfifo_in()
problem. That's probably 2.6.33 material at least. 

-Andi

[PATCH] [1/6] kfifo: Use void * pointers for user buffers

[Andi Kleen]

The pointers to user buffers are currently unsigned char *, which requires
a lot of casting in the caller for any non-char typed buffers. Use 
void * instead.

Signed-off-by: Andi Kleen <ak@linux.intel.com>

---
 include/linux/kfifo.h |   10 +++++-----
 kernel/kfifo.c        |    8 ++++----
 2 files changed, 9 insertions(+), 9 deletions(-)

Index: linux/include/linux/kfifo.h
===================================================================
--- linux.orig/include/linux/kfifo.h
+++ linux/include/linux/kfifo.h
@@ -105,15 +105,15 @@ union { \
 
 #undef __kfifo_initializer
 
-extern void kfifo_init(struct kfifo *fifo, unsigned char *buffer,
+extern void kfifo_init(struct kfifo *fifo, void *buffer,
 			unsigned int size);
 extern __must_check int kfifo_alloc(struct kfifo *fifo, unsigned int size,
 			gfp_t gfp_mask);
 extern void kfifo_free(struct kfifo *fifo);
 extern unsigned int kfifo_in(struct kfifo *fifo,
-				const unsigned char *from, unsigned int len);
+				const void *from, unsigned int len);
 extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
-				unsigned char *to, unsigned int len);
+				void *to, unsigned int len);
 
 /**
  * kfifo_reset - removes the entire FIFO contents
@@ -195,7 +195,7 @@ static inline __must_check unsigned int
  * bytes copied.
  */
 static inline unsigned int kfifo_in_locked(struct kfifo *fifo,
-		const unsigned char *from, unsigned int n, spinlock_t *lock)
+		const void *from, unsigned int n, spinlock_t *lock)
 {
 	unsigned long flags;
 	unsigned int ret;
@@ -220,7 +220,7 @@ static inline unsigned int kfifo_in_lock
  * @to buffer and returns the number of copied bytes.
  */
 static inline __must_check unsigned int kfifo_out_locked(struct kfifo *fifo,
-	unsigned char *to, unsigned int n, spinlock_t *lock)
+	void *to, unsigned int n, spinlock_t *lock)
 {
 	unsigned long flags;
 	unsigned int ret;
Index: linux/kernel/kfifo.c
===================================================================
--- linux.orig/kernel/kfifo.c
+++ linux/kernel/kfifo.c
@@ -28,7 +28,7 @@
 #include <linux/log2.h>
 #include <linux/uaccess.h>
 
-static void _kfifo_init(struct kfifo *fifo, unsigned char *buffer,
+static void _kfifo_init(struct kfifo *fifo, void *buffer,
 		unsigned int size)
 {
 	fifo->buffer = buffer;
@@ -44,7 +44,7 @@ static void _kfifo_init(struct kfifo *fi
  * @size: the size of the internal buffer, this have to be a power of 2.
  *
  */
-void kfifo_init(struct kfifo *fifo, unsigned char *buffer, unsigned int size)
+void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)
 {
 	/* size must be a power of 2 */
 	BUG_ON(!is_power_of_2(size));
@@ -235,7 +235,7 @@ EXPORT_SYMBOL(__kfifo_in_n);
  * Note that with only one concurrent reader and one concurrent
  * writer, you don't need extra locking to use these functions.
  */
-unsigned int kfifo_in(struct kfifo *fifo, const unsigned char *from,
+unsigned int kfifo_in(struct kfifo *fifo, const void *from,
 				unsigned int len)
 {
 	len = min(kfifo_avail(fifo), len);
@@ -277,7 +277,7 @@ EXPORT_SYMBOL(__kfifo_out_n);
  * Note that with only one concurrent reader and one concurrent
  * writer, you don't need extra locking to use these functions.
  */
-unsigned int kfifo_out(struct kfifo *fifo, unsigned char *to, unsigned int len)
+unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len)
 {
 	len = min(kfifo_len(fifo), len);
 

[PATCH] [2/6] kfifo: Make kfifo_in atomic

[Andi Kleen]

Right now kfifo_in allows copying in less than the input
amount. This is unfortunately not a good idea on any
record oriented users: if the size of the kfifo is not
a multiple of the record (and that can easily happen due
to the power-of-two requirement) then when the FIFO fills
up partial records could be put in. Such a condition would
be fatal for any record consumer who would get permanently
desynchronized. In fact I doubt unless the input 
is a totally boundary less data stream I doubt anything
could handle this.

Change kfifo_in() to always put in everything or nothing.

The return value is now always 0 or the full length.

Signed-off-by: Andi Kleen <ak@linux.intel.com>

---
 kernel/kfifo.c |    9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

Index: linux/kernel/kfifo.c
===================================================================
--- linux.orig/kernel/kfifo.c
+++ linux/kernel/kfifo.c
@@ -228,9 +228,8 @@ EXPORT_SYMBOL(__kfifo_in_n);
  * @from: the data to be added.
  * @len: the length of the data to be added.
  *
- * This function copies at most @len bytes from the @from buffer into
- * the FIFO depending on the free space, and returns the number of
- * bytes copied.
+ * This function copies @len bytes from the @from buffer into
+ * the FIFO and returns 0 if there is not enough space.
  *
  * Note that with only one concurrent reader and one concurrent
  * writer, you don't need extra locking to use these functions.
@@ -238,8 +237,8 @@ EXPORT_SYMBOL(__kfifo_in_n);
 unsigned int kfifo_in(struct kfifo *fifo, const void *from,
 				unsigned int len)
 {
-	len = min(kfifo_avail(fifo), len);
-
+	if (kfifo_avail(fifo) < len)
+		return 0;
 	__kfifo_in_data(fifo, from, len, 0);
 	__kfifo_add_in(fifo, len);
 	return len;

[PATCH] [3/6] kfifo: Sanitize *_user error handling

[Andi Kleen]

Right now for kfifo_*_user it's not easily possible to distingush between a 
user copy failing and the FIFO not containing enough data. The problem 
is that both conditions are multiplexed into the same return code.

Avoid this by moving the "copy length" into a separate output parameter
and only return 0/-EFAULT in the main return value.

I didn't fully adapt the weird "record" variants, those seem 
to be unused anyways and were rather messy (should they be just removed?)

I would appreciate some double checking if I did all the conversions
correctly.

Signed-off-by: Andi Kleen <ak@linux.intel.com>

---
 include/linux/kfifo.h |    8 ++---
 kernel/kfifo.c        |   76 ++++++++++++++++++++++++++++++++------------------
 2 files changed, 53 insertions(+), 31 deletions(-)

Index: linux/include/linux/kfifo.h
===================================================================
--- linux.orig/include/linux/kfifo.h
+++ linux/include/linux/kfifo.h
@@ -243,11 +243,11 @@ static inline __must_check unsigned int
 
 extern void kfifo_skip(struct kfifo *fifo, unsigned int len);
 
-extern __must_check unsigned int kfifo_from_user(struct kfifo *fifo,
-	const void __user *from, unsigned int n);
+extern __must_check int kfifo_from_user(struct kfifo *fifo,
+	const void __user *from, unsigned int n, unsigned *lenout);
 
-extern __must_check unsigned int kfifo_to_user(struct kfifo *fifo,
-	void __user *to, unsigned int n);
+extern __must_check int kfifo_to_user(struct kfifo *fifo,
+	void __user *to, unsigned int n, unsigned *lenout);
 
 /**
  * __kfifo_add_out internal helper function for updating the out offset
Index: linux/kernel/kfifo.c
===================================================================
--- linux.orig/kernel/kfifo.c
+++ linux/kernel/kfifo.c
@@ -159,8 +159,9 @@ static inline void __kfifo_out_data(stru
 	memcpy(to + l, fifo->buffer, len - l);
 }
 
-static inline unsigned int __kfifo_from_user_data(struct kfifo *fifo,
-	 const void __user *from, unsigned int len, unsigned int off)
+static inline int __kfifo_from_user_data(struct kfifo *fifo,
+	 const void __user *from, unsigned int len, unsigned int off,
+	 unsigned *lenout)
 {
 	unsigned int l;
 	int ret;
@@ -177,16 +178,20 @@ static inline unsigned int __kfifo_from_
 	/* first put the data starting from fifo->in to buffer end */
 	l = min(len, fifo->size - off);
 	ret = copy_from_user(fifo->buffer + off, from, l);
-
-	if (unlikely(ret))
-		return ret + len - l;
+	if (unlikely(ret)) {
+		*lenout = ret;
+		return -EFAULT;
+	}
+	*lenout = l;
 
 	/* then put the rest (if any) at the beginning of the buffer */
-	return copy_from_user(fifo->buffer, from + l, len - l);
+	ret = copy_from_user(fifo->buffer, from + l, len - l);
+	*lenout += ret ? ret : len - l;
+	return ret ? -EFAULT : 0;
 }
 
-static inline unsigned int __kfifo_to_user_data(struct kfifo *fifo,
-		void __user *to, unsigned int len, unsigned int off)
+static inline int __kfifo_to_user_data(struct kfifo *fifo,
+		void __user *to, unsigned int len, unsigned int off, unsigned *lenout)
 {
 	unsigned int l;
 	int ret;
@@ -203,12 +208,21 @@ static inline unsigned int __kfifo_to_us
 	/* first get the data from fifo->out until the end of the buffer */
 	l = min(len, fifo->size - off);
 	ret = copy_to_user(to, fifo->buffer + off, l);
-
-	if (unlikely(ret))
-		return ret + len - l;
+	*lenout = l;
+	if (unlikely(ret)) {
+		*lenout -= ret;
+		return -EFAULT;
+	}
 
 	/* then get the rest (if any) from the beginning of the buffer */
-	return copy_to_user(to + l, fifo->buffer, len - l);
+	len -= l;
+	ret = copy_to_user(to + l, fifo->buffer, len);
+	if (unlikely(ret)) {
+		*lenout += len - ret;
+		return -EFAULT;
+	}
+	*lenout += len;
+	return 0;
 }
 
 unsigned int __kfifo_in_n(struct kfifo *fifo,
@@ -298,10 +312,13 @@ EXPORT_SYMBOL(__kfifo_out_generic);
 unsigned int __kfifo_from_user_n(struct kfifo *fifo,
 	const void __user *from, unsigned int len, unsigned int recsize)
 {
+	unsigned total;
+
 	if (kfifo_avail(fifo) < len + recsize)
 		return len + 1;
 
-	return __kfifo_from_user_data(fifo, from, len, recsize);
+	__kfifo_from_user_data(fifo, from, len, recsize, &total);
+	return total;
 }
 EXPORT_SYMBOL(__kfifo_from_user_n);
 
@@ -312,18 +329,21 @@ EXPORT_SYMBOL(__kfifo_from_user_n);
  * @len: the length of the data to be added.
  *
  * This function copies at most @len bytes from the @from into the
- * FIFO depending and returns the number of copied bytes.
+ * FIFO depending and returns -EFAULT/0.
  *
  * Note that with only one concurrent reader and one concurrent
  * writer, you don't need extra locking to use these functions.
  */
-unsigned int kfifo_from_user(struct kfifo *fifo,
-	const void __user *from, unsigned int len)
+int kfifo_from_user(struct kfifo *fifo,
+        const void __user *from, unsigned int len, unsigned *total)
 {
+	int ret;
 	len = min(kfifo_avail(fifo), len);
-	len -= __kfifo_from_user_data(fifo, from, len, 0);
+	ret = __kfifo_from_user_data(fifo, from, len, 0, total);
+	if (ret)
+		return ret;
 	__kfifo_add_in(fifo, len);
-	return len;
+	return 0;
 }
 EXPORT_SYMBOL(kfifo_from_user);
 
@@ -338,17 +358,17 @@ unsigned int __kfifo_to_user_n(struct kf
 	void __user *to, unsigned int len, unsigned int reclen,
 	unsigned int recsize)
 {
-	unsigned int ret;
+	unsigned int ret, total;
 
 	if (kfifo_len(fifo) < reclen + recsize)
 		return len;
 
-	ret = __kfifo_to_user_data(fifo, to, reclen, recsize);
+	ret = __kfifo_to_user_data(fifo, to, reclen, recsize, &total);
 
 	if (likely(ret == 0))
 		__kfifo_add_out(fifo, reclen + recsize);
 
-	return ret;
+	return total;
 }
 EXPORT_SYMBOL(__kfifo_to_user_n);
 
@@ -357,20 +377,22 @@ EXPORT_SYMBOL(__kfifo_to_user_n);
  * @fifo: the fifo to be used.
  * @to: where the data must be copied.
  * @len: the size of the destination buffer.
+ @ @lenout: pointer to output variable with copied data
  *
  * This function copies at most @len bytes from the FIFO into the
- * @to buffer and returns the number of copied bytes.
+ * @to buffer and 0 or -EFAULT.
  *
  * Note that with only one concurrent reader and one concurrent
  * writer, you don't need extra locking to use these functions.
  */
-unsigned int kfifo_to_user(struct kfifo *fifo,
-	void __user *to, unsigned int len)
+int kfifo_to_user(struct kfifo *fifo,
+	void __user *to, unsigned int len, unsigned *lenout)
 {
+	int ret;
 	len = min(kfifo_len(fifo), len);
-	len -= __kfifo_to_user_data(fifo, to, len, 0);
-	__kfifo_add_out(fifo, len);
-	return len;
+	ret = __kfifo_to_user_data(fifo, to, len, 0, lenout);
+	__kfifo_add_out(fifo, *lenout);
+	return ret;
 }
 EXPORT_SYMBOL(kfifo_to_user);
 

[PATCH] [4/6] kfifo: add kfifo_out_peek

[Andi Kleen]

In some upcoming code it's useful to peek into a FIFO without
permanentely removing data. This patch implements a new 
kfifo_out_peek() to do this. 

Signed-off-by: Andi Kleen <ak@linux.intel.com>

---
 include/linux/kfifo.h |    3 +++
 kernel/kfifo.c        |   21 +++++++++++++++++++++
 2 files changed, 24 insertions(+)

Index: linux/include/linux/kfifo.h
===================================================================
--- linux.orig/include/linux/kfifo.h
+++ linux/include/linux/kfifo.h
@@ -114,6 +114,9 @@ extern unsigned int kfifo_in(struct kfif
 				const void *from, unsigned int len);
 extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
 				void *to, unsigned int len);
+extern __must_check unsigned int kfifo_out_peek(struct kfifo *fifo,
+				void *to, unsigned int len, unsigned offset);
+
 
 /**
  * kfifo_reset - removes the entire FIFO contents
Index: linux/kernel/kfifo.c
===================================================================
--- linux.orig/kernel/kfifo.c
+++ linux/kernel/kfifo.c
@@ -301,6 +301,27 @@ unsigned int kfifo_out(struct kfifo *fif
 }
 EXPORT_SYMBOL(kfifo_out);
 
+/**
+ * kfifo_out_peek - copy some data from the FIFO, but do not remove it
+ * @fifo: the fifo to be used.
+ * @to: where the data must be copied.
+ * @len: the size of the destination buffer.
+ * @offset: offset into the fifo
+ *
+ * This function copies at most @len bytes at @offset from the FIFO
+ * into the @to buffer and returns the number of copied bytes.
+ * The data is not removed from the FIFO.
+ */
+unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len,
+			    unsigned offset)
+{
+	len = min(kfifo_len(fifo), len + offset);
+
+	__kfifo_out_data(fifo, to, len, offset);
+	return len;
+}
+EXPORT_SYMBOL(kfifo_out_peek);
+
 unsigned int __kfifo_out_generic(struct kfifo *fifo,
 	void *to, unsigned int len, unsigned int recsize,
 	unsigned int *total)

[PATCH] [5/6] kfifo: Add kfifo_initialized

[Andi Kleen]

Simple inline that checks if kfifo_init() has been executed
on a fifo.

This is useful for walking all per CPU fifos, when some of them
might not have been brought up yet.

Signed-off-by: Andi Kleen <ak@linux.intel.com>

---
 include/linux/kfifo.h |   10 ++++++++++
 1 file changed, 10 insertions(+)

Index: linux/include/linux/kfifo.h
===================================================================
--- linux.orig/include/linux/kfifo.h
+++ linux/include/linux/kfifo.h
@@ -117,6 +117,16 @@ extern __must_check unsigned int kfifo_o
 extern __must_check unsigned int kfifo_out_peek(struct kfifo *fifo,
 				void *to, unsigned int len, unsigned offset);
 
+/**
+ * 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.
+ */
+static inline bool kfifo_initialized(struct kfifo *fifo)
+{
+	return fifo->buffer != 0;
+}
 
 /**
  * kfifo_reset - removes the entire FIFO contents

[PATCH] [6/6] kfifo: Document everywhere that size has to be power of two

[Andi Kleen]

On my first try using them I missed that the fifos need to 
be power of two, resulting in a runtime bug. Document that requirement
everywhere (and fix one grammar bug)

Signed-off-by: Andi Kleen <ak@linux.intel.com>

---
 include/linux/kfifo.h |    4 ++--
 kernel/kfifo.c        |    2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

Index: linux/include/linux/kfifo.h
===================================================================
--- linux.orig/include/linux/kfifo.h
+++ linux/include/linux/kfifo.h
@@ -67,7 +67,7 @@ struct kfifo {
 /**
  * DECLARE_KFIFO - macro to declare a kfifo and the associated buffer
  * @name: name of the declared kfifo datatype
- * @size: size of the fifo buffer
+ * @size: size of the fifo buffer. Must be a power of two.
  *
  * Note1: the macro can be used inside struct or union declaration
  * Note2: the macro creates two objects:
@@ -91,7 +91,7 @@ union { \
 /**
  * DEFINE_KFIFO - macro to define and initialize a kfifo
  * @name: name of the declared kfifo datatype
- * @size: size of the fifo buffer
+ * @size: size of the fifo buffer. Must be a power of two.
  *
  * Note1: the macro can be used for global and local kfifo data type variables
  * Note2: the macro creates two objects:
Index: linux/kernel/kfifo.c
===================================================================
--- linux.orig/kernel/kfifo.c
+++ linux/kernel/kfifo.c
@@ -41,7 +41,7 @@ static void _kfifo_init(struct kfifo *fi
  * kfifo_init - initialize a FIFO using a preallocated buffer
  * @fifo: the fifo to assign the buffer
  * @buffer: the preallocated buffer to be used.
- * @size: the size of the internal buffer, this have to be a power of 2.
+ * @size: the size of the internal buffer, this has to be a power of 2.
  *
  */
 void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> While porting some of my code to kfifo I found some issues, which
> are addressed in the following patch series.
> 
> Some of the problems were serious, particularly the non atomic kfifo_in()
> problem. That's probably 2.6.33 material at least. 
> 

I am not happy to see you to take over my project. Especial as most of
your fixes are part of my new macro based implementation. Have a look at
http://patchwork.kernel.org/patch/69093/

Stefani

Re: [PATCH] [3/6] kfifo: Sanitize *_user error handling

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> Right now for kfifo_*_user it's not easily possible to distingush between a 
> user copy failing and the FIFO not containing enough data. The problem 
> is that both conditions are multiplexed into the same return code.
> 
> Avoid this by moving the "copy length" into a separate output parameter
> and only return 0/-EFAULT in the main return value.
> 

I don't like this idea. kfifo_from_user and kfifo_to_user should have
the same semantics as copy_from_user and copy_to_user. 

> I didn't fully adapt the weird "record" variants, those seem 
> to be unused anyways and were rather messy (should they be just removed?)
> 

Believe it or not, it will be used in future. 

> I would appreciate some double checking if I did all the conversions
> correctly.
> 
> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> ---
>  include/linux/kfifo.h |    8 ++---
>  kernel/kfifo.c        |   76 ++++++++++++++++++++++++++++++++------------------
>  2 files changed, 53 insertions(+), 31 deletions(-)
> 
> Index: linux/include/linux/kfifo.h
> ===================================================================
> --- linux.orig/include/linux/kfifo.h
> +++ linux/include/linux/kfifo.h
> @@ -243,11 +243,11 @@ static inline __must_check unsigned int
>  
>  extern void kfifo_skip(struct kfifo *fifo, unsigned int len);
>  
> -extern __must_check unsigned int kfifo_from_user(struct kfifo *fifo,
> -	const void __user *from, unsigned int n);
> +extern __must_check int kfifo_from_user(struct kfifo *fifo,
> +	const void __user *from, unsigned int n, unsigned *lenout);
>  
> -extern __must_check unsigned int kfifo_to_user(struct kfifo *fifo,
> -	void __user *to, unsigned int n);
> +extern __must_check int kfifo_to_user(struct kfifo *fifo,
> +	void __user *to, unsigned int n, unsigned *lenout);
>  
>  /**
>   * __kfifo_add_out internal helper function for updating the out offset
> Index: linux/kernel/kfifo.c
> ===================================================================
> --- linux.orig/kernel/kfifo.c
> +++ linux/kernel/kfifo.c
> @@ -159,8 +159,9 @@ static inline void __kfifo_out_data(stru
>  	memcpy(to + l, fifo->buffer, len - l);
>  }
>  
> -static inline unsigned int __kfifo_from_user_data(struct kfifo *fifo,
> -	 const void __user *from, unsigned int len, unsigned int off)
> +static inline int __kfifo_from_user_data(struct kfifo *fifo,
> +	 const void __user *from, unsigned int len, unsigned int off,
> +	 unsigned *lenout)
>  {
>  	unsigned int l;
>  	int ret;
> @@ -177,16 +178,20 @@ static inline unsigned int __kfifo_from_
>  	/* first put the data starting from fifo->in to buffer end */
>  	l = min(len, fifo->size - off);
>  	ret = copy_from_user(fifo->buffer + off, from, l);
> -
> -	if (unlikely(ret))
> -		return ret + len - l;
> +	if (unlikely(ret)) {
> +		*lenout = ret;
> +		return -EFAULT;
> +	}
> +	*lenout = l;
>  
>  	/* then put the rest (if any) at the beginning of the buffer */
> -	return copy_from_user(fifo->buffer, from + l, len - l);
> +	ret = copy_from_user(fifo->buffer, from + l, len - l);
> +	*lenout += ret ? ret : len - l;
> +	return ret ? -EFAULT : 0;
>  }
>  
> -static inline unsigned int __kfifo_to_user_data(struct kfifo *fifo,
> -		void __user *to, unsigned int len, unsigned int off)
> +static inline int __kfifo_to_user_data(struct kfifo *fifo,
> +		void __user *to, unsigned int len, unsigned int off, unsigned *lenout)
>  {
>  	unsigned int l;
>  	int ret;
> @@ -203,12 +208,21 @@ static inline unsigned int __kfifo_to_us
>  	/* first get the data from fifo->out until the end of the buffer */
>  	l = min(len, fifo->size - off);
>  	ret = copy_to_user(to, fifo->buffer + off, l);
> -
> -	if (unlikely(ret))
> -		return ret + len - l;
> +	*lenout = l;
> +	if (unlikely(ret)) {
> +		*lenout -= ret;
> +		return -EFAULT;
> +	}
>  
>  	/* then get the rest (if any) from the beginning of the buffer */
> -	return copy_to_user(to + l, fifo->buffer, len - l);
> +	len -= l;
> +	ret = copy_to_user(to + l, fifo->buffer, len);
> +	if (unlikely(ret)) {
> +		*lenout += len - ret;
> +		return -EFAULT;
> +	}
> +	*lenout += len;
> +	return 0;
>  }
>  
>  unsigned int __kfifo_in_n(struct kfifo *fifo,
> @@ -298,10 +312,13 @@ EXPORT_SYMBOL(__kfifo_out_generic);
>  unsigned int __kfifo_from_user_n(struct kfifo *fifo,
>  	const void __user *from, unsigned int len, unsigned int recsize)
>  {
> +	unsigned total;
> +
>  	if (kfifo_avail(fifo) < len + recsize)
>  		return len + 1;
>  
> -	return __kfifo_from_user_data(fifo, from, len, recsize);
> +	__kfifo_from_user_data(fifo, from, len, recsize, &total);
> +	return total;
>  }
>  EXPORT_SYMBOL(__kfifo_from_user_n);
>  
> @@ -312,18 +329,21 @@ EXPORT_SYMBOL(__kfifo_from_user_n);
>   * @len: the length of the data to be added.
>   *
>   * This function copies at most @len bytes from the @from into the
> - * FIFO depending and returns the number of copied bytes.
> + * FIFO depending and returns -EFAULT/0.
>   *
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
>   */
> -unsigned int kfifo_from_user(struct kfifo *fifo,
> -	const void __user *from, unsigned int len)
> +int kfifo_from_user(struct kfifo *fifo,
> +        const void __user *from, unsigned int len, unsigned *total)
>  {
> +	int ret;
>  	len = min(kfifo_avail(fifo), len);
> -	len -= __kfifo_from_user_data(fifo, from, len, 0);
> +	ret = __kfifo_from_user_data(fifo, from, len, 0, total);
> +	if (ret)
> +		return ret;
>  	__kfifo_add_in(fifo, len);
> -	return len;
> +	return 0;
>  }
>  EXPORT_SYMBOL(kfifo_from_user);
>  
> @@ -338,17 +358,17 @@ unsigned int __kfifo_to_user_n(struct kf
>  	void __user *to, unsigned int len, unsigned int reclen,
>  	unsigned int recsize)
>  {
> -	unsigned int ret;
> +	unsigned int ret, total;
>  
>  	if (kfifo_len(fifo) < reclen + recsize)
>  		return len;
>  
> -	ret = __kfifo_to_user_data(fifo, to, reclen, recsize);
> +	ret = __kfifo_to_user_data(fifo, to, reclen, recsize, &total);
>  
>  	if (likely(ret == 0))
>  		__kfifo_add_out(fifo, reclen + recsize);
>  
> -	return ret;
> +	return total;
>  }
>  EXPORT_SYMBOL(__kfifo_to_user_n);
>  
> @@ -357,20 +377,22 @@ EXPORT_SYMBOL(__kfifo_to_user_n);
>   * @fifo: the fifo to be used.
>   * @to: where the data must be copied.
>   * @len: the size of the destination buffer.
> + @ @lenout: pointer to output variable with copied data
>   *
>   * This function copies at most @len bytes from the FIFO into the
> - * @to buffer and returns the number of copied bytes.
> + * @to buffer and 0 or -EFAULT.
>   *
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
>   */
> -unsigned int kfifo_to_user(struct kfifo *fifo,
> -	void __user *to, unsigned int len)
> +int kfifo_to_user(struct kfifo *fifo,
> +	void __user *to, unsigned int len, unsigned *lenout)
>  {
> +	int ret;
>  	len = min(kfifo_len(fifo), len);
> -	len -= __kfifo_to_user_data(fifo, to, len, 0);
> -	__kfifo_add_out(fifo, len);
> -	return len;
> +	ret = __kfifo_to_user_data(fifo, to, len, 0, lenout);
> +	__kfifo_add_out(fifo, *lenout);
> +	return ret;
>  }
>  EXPORT_SYMBOL(kfifo_to_user);
>  

Re: [PATCH] [2/6] kfifo: Make kfifo_in atomic

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> Right now kfifo_in allows copying in less than the input
> amount. This is unfortunately not a good idea on any
> record oriented users: if the size of the kfifo is not
> a multiple of the record (and that can easily happen due
> to the power-of-two requirement) then when the FIFO fills
> up partial records could be put in. Such a condition would
> be fatal for any record consumer who would get permanently
> desynchronized. In fact I doubt unless the input 
> is a totally boundary less data stream I doubt anything
> could handle this.
> 
> Change kfifo_in() to always put in everything or nothing.
> 
> The return value is now always 0 or the full length.
> 

That is why had written the macro version of kfifo. This provide an type
save kfifo implementation where struct records never will be splitted.
Have a look at the sample code in
http://patchwork.kernel.org/patch/69093/

> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> ---
>  kernel/kfifo.c |    9 ++++-----
>  1 file changed, 4 insertions(+), 5 deletions(-)
> 
> Index: linux/kernel/kfifo.c
> ===================================================================
> --- linux.orig/kernel/kfifo.c
> +++ linux/kernel/kfifo.c
> @@ -228,9 +228,8 @@ EXPORT_SYMBOL(__kfifo_in_n);
>   * @from: the data to be added.
>   * @len: the length of the data to be added.
>   *
> - * This function copies at most @len bytes from the @from buffer into
> - * the FIFO depending on the free space, and returns the number of
> - * bytes copied.
> + * This function copies @len bytes from the @from buffer into
> + * the FIFO and returns 0 if there is not enough space.
>   *
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
> @@ -238,8 +237,8 @@ EXPORT_SYMBOL(__kfifo_in_n);
>  unsigned int kfifo_in(struct kfifo *fifo, const void *from,
>  				unsigned int len)
>  {
> -	len = min(kfifo_avail(fifo), len);
> -
> +	if (kfifo_avail(fifo) < len)
> +		return 0;
>  	__kfifo_in_data(fifo, from, len, 0);
>  	__kfifo_add_in(fifo, len);
>  	return len;

Re: [PATCH] [1/6] kfifo: Use void * pointers for user buffers

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> The pointers to user buffers are currently unsigned char *, which requires
> a lot of casting in the caller for any non-char typed buffers. Use 
> void * instead.
> 

Agree. But this has gone in the macro version of the kfifo
implementation, which is type safe.

Stefani

> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> ---
>  include/linux/kfifo.h |   10 +++++-----
>  kernel/kfifo.c        |    8 ++++----
>  2 files changed, 9 insertions(+), 9 deletions(-)
> 
> Index: linux/include/linux/kfifo.h
> ===================================================================
> --- linux.orig/include/linux/kfifo.h
> +++ linux/include/linux/kfifo.h
> @@ -105,15 +105,15 @@ union { \
>  
>  #undef __kfifo_initializer
>  
> -extern void kfifo_init(struct kfifo *fifo, unsigned char *buffer,
> +extern void kfifo_init(struct kfifo *fifo, void *buffer,
>  			unsigned int size);
>  extern __must_check int kfifo_alloc(struct kfifo *fifo, unsigned int size,
>  			gfp_t gfp_mask);
>  extern void kfifo_free(struct kfifo *fifo);
>  extern unsigned int kfifo_in(struct kfifo *fifo,
> -				const unsigned char *from, unsigned int len);
> +				const void *from, unsigned int len);
>  extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
> -				unsigned char *to, unsigned int len);
> +				void *to, unsigned int len);
>  
>  /**
>   * kfifo_reset - removes the entire FIFO contents
> @@ -195,7 +195,7 @@ static inline __must_check unsigned int
>   * bytes copied.
>   */
>  static inline unsigned int kfifo_in_locked(struct kfifo *fifo,
> -		const unsigned char *from, unsigned int n, spinlock_t *lock)
> +		const void *from, unsigned int n, spinlock_t *lock)
>  {
>  	unsigned long flags;
>  	unsigned int ret;
> @@ -220,7 +220,7 @@ static inline unsigned int kfifo_in_lock
>   * @to buffer and returns the number of copied bytes.
>   */
>  static inline __must_check unsigned int kfifo_out_locked(struct kfifo *fifo,
> -	unsigned char *to, unsigned int n, spinlock_t *lock)
> +	void *to, unsigned int n, spinlock_t *lock)
>  {
>  	unsigned long flags;
>  	unsigned int ret;
> Index: linux/kernel/kfifo.c
> ===================================================================
> --- linux.orig/kernel/kfifo.c
> +++ linux/kernel/kfifo.c
> @@ -28,7 +28,7 @@
>  #include <linux/log2.h>
>  #include <linux/uaccess.h>
>  
> -static void _kfifo_init(struct kfifo *fifo, unsigned char *buffer,
> +static void _kfifo_init(struct kfifo *fifo, void *buffer,
>  		unsigned int size)
>  {
>  	fifo->buffer = buffer;
> @@ -44,7 +44,7 @@ static void _kfifo_init(struct kfifo *fi
>   * @size: the size of the internal buffer, this have to be a power of 2.
>   *
>   */
> -void kfifo_init(struct kfifo *fifo, unsigned char *buffer, unsigned int size)
> +void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)
>  {
>  	/* size must be a power of 2 */
>  	BUG_ON(!is_power_of_2(size));
> @@ -235,7 +235,7 @@ EXPORT_SYMBOL(__kfifo_in_n);
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
>   */
> -unsigned int kfifo_in(struct kfifo *fifo, const unsigned char *from,
> +unsigned int kfifo_in(struct kfifo *fifo, const void *from,
>  				unsigned int len)
>  {
>  	len = min(kfifo_avail(fifo), len);
> @@ -277,7 +277,7 @@ EXPORT_SYMBOL(__kfifo_out_n);
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
>   */
> -unsigned int kfifo_out(struct kfifo *fifo, unsigned char *to, unsigned int len)
> +unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len)
>  {
>  	len = min(kfifo_len(fifo), len);
>  

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> In some upcoming code it's useful to peek into a FIFO without
> permanentely removing data. This patch implements a new 
> kfifo_out_peek() to do this. 
> 

Yes this function can be useful. I will implement it in the macro
version of the kfifo.

> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> ---
>  include/linux/kfifo.h |    3 +++
>  kernel/kfifo.c        |   21 +++++++++++++++++++++
>  2 files changed, 24 insertions(+)
> 
> Index: linux/include/linux/kfifo.h
> ===================================================================
> --- linux.orig/include/linux/kfifo.h
> +++ linux/include/linux/kfifo.h
> @@ -114,6 +114,9 @@ extern unsigned int kfifo_in(struct kfif
>  				const void *from, unsigned int len);
>  extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
>  				void *to, unsigned int len);
> +extern __must_check unsigned int kfifo_out_peek(struct kfifo *fifo,
> +				void *to, unsigned int len, unsigned offset);
> +
>  
>  /**
>   * kfifo_reset - removes the entire FIFO contents
> Index: linux/kernel/kfifo.c
> ===================================================================
> --- linux.orig/kernel/kfifo.c
> +++ linux/kernel/kfifo.c
> @@ -301,6 +301,27 @@ unsigned int kfifo_out(struct kfifo *fif
>  }
>  EXPORT_SYMBOL(kfifo_out);
>  
> +/**
> + * kfifo_out_peek - copy some data from the FIFO, but do not remove it
> + * @fifo: the fifo to be used.
> + * @to: where the data must be copied.
> + * @len: the size of the destination buffer.
> + * @offset: offset into the fifo
> + *
> + * This function copies at most @len bytes at @offset from the FIFO
> + * into the @to buffer and returns the number of copied bytes.
> + * The data is not removed from the FIFO.
> + */
> +unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len,
> +			    unsigned offset)
> +{
> +	len = min(kfifo_len(fifo), len + offset);
> +
> +	__kfifo_out_data(fifo, to, len, offset);
> +	return len;
> +}
> +EXPORT_SYMBOL(kfifo_out_peek);
> +
>  unsigned int __kfifo_out_generic(struct kfifo *fifo,
>  	void *to, unsigned int len, unsigned int recsize,
>  	unsigned int *total)

Re: [PATCH] [6/6] kfifo: Document everywhere that size has to be power of two

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> On my first try using them I missed that the fifos need to 
> be power of two, resulting in a runtime bug. Document that requirement
> everywhere (and fix one grammar bug)
> 
> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 

Acked: Stefani Seibold <Stefani@Seibold.net>

> ---
>  include/linux/kfifo.h |    4 ++--
>  kernel/kfifo.c        |    2 +-
>  2 files changed, 3 insertions(+), 3 deletions(-)
> 
> Index: linux/include/linux/kfifo.h
> ===================================================================
> --- linux.orig/include/linux/kfifo.h
> +++ linux/include/linux/kfifo.h
> @@ -67,7 +67,7 @@ struct kfifo {
>  /**
>   * DECLARE_KFIFO - macro to declare a kfifo and the associated buffer
>   * @name: name of the declared kfifo datatype
> - * @size: size of the fifo buffer
> + * @size: size of the fifo buffer. Must be a power of two.
>   *
>   * Note1: the macro can be used inside struct or union declaration
>   * Note2: the macro creates two objects:
> @@ -91,7 +91,7 @@ union { \
>  /**
>   * DEFINE_KFIFO - macro to define and initialize a kfifo
>   * @name: name of the declared kfifo datatype
> - * @size: size of the fifo buffer
> + * @size: size of the fifo buffer. Must be a power of two.
>   *
>   * Note1: the macro can be used for global and local kfifo data type variables
>   * Note2: the macro creates two objects:
> Index: linux/kernel/kfifo.c
> ===================================================================
> --- linux.orig/kernel/kfifo.c
> +++ linux/kernel/kfifo.c
> @@ -41,7 +41,7 @@ static void _kfifo_init(struct kfifo *fi
>   * kfifo_init - initialize a FIFO using a preallocated buffer
>   * @fifo: the fifo to assign the buffer
>   * @buffer: the preallocated buffer to be used.
> - * @size: the size of the internal buffer, this have to be a power of 2.
> + * @size: the size of the internal buffer, this has to be a power of 2.
>   *
>   */
>  void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size)

Re: [PATCH] [5/6] kfifo: Add kfifo_initialized

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> Simple inline that checks if kfifo_init() has been executed
> on a fifo.
> 
> This is useful for walking all per CPU fifos, when some of them
> might not have been brought up yet.
> 

Could be useful, i can implement it. But with the new macro based kfifo
there are also real in place fifo's, where the buffer is a part of the
kfifo structure. But in this case i can return always true.

Stefani

> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> ---
>  include/linux/kfifo.h |   10 ++++++++++
>  1 file changed, 10 insertions(+)
> 
> Index: linux/include/linux/kfifo.h
> ===================================================================
> --- linux.orig/include/linux/kfifo.h
> +++ linux/include/linux/kfifo.h
> @@ -117,6 +117,16 @@ extern __must_check unsigned int kfifo_o
>  extern __must_check unsigned int kfifo_out_peek(struct kfifo *fifo,
>  				void *to, unsigned int len, unsigned offset);
>  
> +/**
> + * 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.
> + */
> +static inline bool kfifo_initialized(struct kfifo *fifo)
> +{
> +	return fifo->buffer != 0;
> +}
>  
>  /**
>   * kfifo_reset - removes the entire FIFO contents

Re: [PATCH] [6/6] kfifo: Document everywhere that size has to be power of two

[Dmitry Torokhov]

On Sun, Dec 27, 2009 at 10:50:32PM +0100, Stefani Seibold wrote:
> Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > On my first try using them I missed that the fifos need to 
> > be power of two, resulting in a runtime bug. Document that requirement
> > everywhere (and fix one grammar bug)
> > 
> > Signed-off-by: Andi Kleen <ak@linux.intel.com>
> > 
> 
> Acked: Stefani Seibold <Stefani@Seibold.net>
> 

Now, does it really _have_ to be this way? For record-oriented
FIFO's it is customary to be 2*pow(n)*sizeof(rec) which is rarely
2*pow(m).

-- 
Dmitry

Re: [PATCH] [6/6] kfifo: Document everywhere that size has to be power of two

[Stefani Seibold]

Am Sonntag, den 27.12.2009, 14:14 -0800 schrieb Dmitry Torokhov:
> On Sun, Dec 27, 2009 at 10:50:32PM +0100, Stefani Seibold wrote:
> > Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > > On my first try using them I missed that the fifos need to 
> > > be power of two, resulting in a runtime bug. Document that requirement
> > > everywhere (and fix one grammar bug)
> > > 
> > > Signed-off-by: Andi Kleen <ak@linux.intel.com>
> > > 
> > 
> > Acked: Stefani Seibold <Stefani@Seibold.net>
> > 
> 
> Now, does it really _have_ to be this way? For record-oriented
> FIFO's it is customary to be 2*pow(n)*sizeof(rec) which is rarely
> 2*pow(m).
> 

Right. This is why i wrote the new macro base kfifo API, where i am able
to do this in that way.

Stefani

Re: [PATCH] [3/6] kfifo: Sanitize *_user error handling

[Andi Kleen]

> I don't like this idea. kfifo_from_user and kfifo_to_user should have
> the same semantics as copy_from_user and copy_to_user. 

Maybe they should have, but the big difference is that the source
FIFO might not have enough data. And both conditions need
to be reported, but not mixed together.

The actual reporting of the unused length is not
too useful anyways. It's only used very rarely for real
c*u(), and these cases are usually misdesigned interfaces.

> > I didn't fully adapt the weird "record" variants, those seem 
> > to be unused anyways and were rather messy (should they be just removed?)
> > 
> 
> Believe it or not, it will be used in future. 

Normally in Linux code is only added when it's actually used.
Otherwise it'll bitrot anyways.

-Andi

Re: [PATCH] [6/6] kfifo: Document everywhere that size has to be power of two

[Andi Kleen]

On Sun, Dec 27, 2009 at 02:14:38PM -0800, Dmitry Torokhov wrote:
> On Sun, Dec 27, 2009 at 10:50:32PM +0100, Stefani Seibold wrote:
> > Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > > On my first try using them I missed that the fifos need to 
> > > be power of two, resulting in a runtime bug. Document that requirement
> > > everywhere (and fix one grammar bug)
> > > 
> > > Signed-off-by: Andi Kleen <ak@linux.intel.com>
> > > 
> > 
> > Acked: Stefani Seibold <Stefani@Seibold.net>
> > 
> 
> Now, does it really _have_ to be this way? For record-oriented
> FIFO's it is customary to be 2*pow(n)*sizeof(rec) which is rarely
> 2*pow(m).

Yes I agree, but the kfifos are not fully record oriented unfortunately.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

On Sun, Dec 27, 2009 at 10:36:40PM +0100, Stefani Seibold wrote:
> Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > While porting some of my code to kfifo I found some issues, which
> > are addressed in the following patch series.
> > 
> > Some of the problems were serious, particularly the non atomic kfifo_in()
> > problem. That's probably 2.6.33 material at least. 
> > 
> 
> I am not happy to see you to take over my project. Especial as most of

I'm just trying to use kfifos and ran into lots of issues that
I fixed. Especially the non atomic kfifo_in problem seemed pretty fatal
BTW.

> your fixes are part of my new macro based implementation. Have a look at
> http://patchwork.kernel.org/patch/69093/

Even if that was merged the older interfaces still need to be fixed.

Or are you saying the new interface would completely replace kfifos?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Andi Kleen]

On Sun, Dec 27, 2009 at 10:49:49PM +0100, Stefani Seibold wrote:
> Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > In some upcoming code it's useful to peek into a FIFO without
> > permanentely removing data. This patch implements a new 
> > kfifo_out_peek() to do this. 
> > 
> 
> Yes this function can be useful. I will implement it in the macro
> version of the kfifo.

Well that doesn't help me -- I need a working kfifo on a 2.6.33
base. Or do you want to abandon the old interface?

I must say I'm a little surprised by the general tone of  
your comments -- first you submit these patches all the time and when they 
finally get reviewed and merged and people start to use them and make them 
production ready you state it's all abandoned.

I hope it's not all abandonware.

Anyways Andrew could you please merge these fixes? Thanks.

-Andi

Re: [PATCH] [0/6] kfifo fixes/improvements

[Roland Dreier]

 > I am not happy to see you to take over my project. Especial as most of
 > your fixes are part of my new macro based implementation. Have a look at
 > http://patchwork.kernel.org/patch/69093/

I don't really understand.  You spent a lot of time getting the kfifo
stuff merged, and now you want to merge (quoting from that patch above)
"a complete reimplementation of the new kfifo API"?

What happened here?  Couldn't you have done the reimplementation before
merging?

 - R.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

On Sun, Dec 27, 2009 at 04:12:06PM -0800, Roland Dreier wrote:
> 
>  > I am not happy to see you to take over my project. Especial as most of
>  > your fixes are part of my new macro based implementation. Have a look at
>  > http://patchwork.kernel.org/patch/69093/
> 
> I don't really understand.  You spent a lot of time getting the kfifo
> stuff merged, and now you want to merge (quoting from that patch above)
> "a complete reimplementation of the new kfifo API"?
> 
> What happened here?  Couldn't you have done the reimplementation before
> merging?

I guess the reimplementation came too late (happens sometimes)
And I agree that making kfifos record oriented makes sense.

Still now that the old one is in we have to fix it at least
until there are no users left.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Montag, den 28.12.2009, 00:38 +0100 schrieb Andi Kleen:
> On Sun, Dec 27, 2009 at 10:36:40PM +0100, Stefani Seibold wrote:
> > Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > > While porting some of my code to kfifo I found some issues, which
> > > are addressed in the following patch series.
> > > 
> > > Some of the problems were serious, particularly the non atomic kfifo_in()
> > > problem. That's probably 2.6.33 material at least. 
> > > 
> > 
> > I am not happy to see you to take over my project. Especial as most of
> 
> I'm just trying to use kfifos and ran into lots of issues that
> I fixed. Especially the non atomic kfifo_in problem seemed pretty fatal
> BTW.
> 
> > your fixes are part of my new macro based implementation. Have a look at
> > http://patchwork.kernel.org/patch/69093/
> 
> Even if that was merged the older interfaces still need to be fixed.
> 
> Or are you saying the new interface would completely replace kfifos?
> 

Yes, the new macro based kfifos does completely replace the current
kfifos. It would be great if you can review the code. There is all in.

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Montag, den 28.12.2009, 02:41 +0100 schrieb Andi Kleen:
> On Sun, Dec 27, 2009 at 04:12:06PM -0800, Roland Dreier wrote:
> > 
> >  > I am not happy to see you to take over my project. Especial as most of
> >  > your fixes are part of my new macro based implementation. Have a look at
> >  > http://patchwork.kernel.org/patch/69093/
> > 
> > I don't really understand.  You spent a lot of time getting the kfifo
> > stuff merged, and now you want to merge (quoting from that patch above)
> > "a complete reimplementation of the new kfifo API"?
> > 

Yes, because of the limitations. The new merge kfifo stuff was based on
the old one. So i overtake this it. But the new one is fully compatible
to the merged kfifo.

> > What happened here?  Couldn't you have done the reimplementation before
> > merging?
> 

I am sorry, but did not recognized all constrains and features which are
really necessary for a real generic fifo interface. And also i did't saw
the possibility to do it as a template, because C does not support it.
It takes time the mature the idea to implement this as a macro set.

BTW, you give me the idea to reimplementation for kfifo, because you ask
me if it is not possible to merge my kqueue RFC. 

> I guess the reimplementation came too late (happens sometimes)
> And I agree that making kfifos record oriented makes sense.

What does it mean? To late for 2.6.33 or to late to replace it for ever?
I think it is easy to replace, because it is fully tested and 100
percent compatible to the new kfifo implementation.

> 
> Still now that the old one is in we have to fix it at least
> until there are no users left.
> 

The only user of the new features are currently you.

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Stefani Seibold]

Am Montag, den 28.12.2009, 00:41 +0100 schrieb Andi Kleen:
> On Sun, Dec 27, 2009 at 10:49:49PM +0100, Stefani Seibold wrote:
> > Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > > In some upcoming code it's useful to peek into a FIFO without
> > > permanentely removing data. This patch implements a new 
> > > kfifo_out_peek() to do this. 
> > > 
> > 
> > Yes this function can be useful. I will implement it in the macro
> > version of the kfifo.
> 
> Well that doesn't help me -- I need a working kfifo on a 2.6.33
> base. Or do you want to abandon the old interface?
> 
> I must say I'm a little surprised by the general tone of  
> your comments -- first you submit these patches all the time and when they 
> finally get reviewed and merged and people start to use them and make them 
> production ready you state it's all abandoned.
> 
> I hope it's not all abandonware.
> 

As i wrote: Yes and No. I would like to sedd the merged kfifo interface
which the new macro based. The API is still compatible but the code is
completely changed.

Stefani

Re: [PATCH] [3/6] kfifo: Sanitize *_user error handling

[Stefani Seibold]

Am Montag, den 28.12.2009, 00:34 +0100 schrieb Andi Kleen:
> > I don't like this idea. kfifo_from_user and kfifo_to_user should have
> > the same semantics as copy_from_user and copy_to_user. 
> 
> Maybe they should have, but the big difference is that the source
> FIFO might not have enough data. And both conditions need
> to be reported, but not mixed together.
> 
> The actual reporting of the unused length is not
> too useful anyways. It's only used very rarely for real
> c*u(), and these cases are usually misdesigned interfaces.
> 
> > > I didn't fully adapt the weird "record" variants, those seem 
> > > to be unused anyways and were rather messy (should they be just removed?)
> > > 
> > 
> > Believe it or not, it will be used in future. 
> 
> Normally in Linux code is only added when it's actually used.
> Otherwise it'll bitrot anyways.
> 

I know a lot of places and structures inside the kernel where it is not
this case. 

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Anyway, I ack all your patches, expect the "2/6 Make kfifo_in atomic"
which will break my future work.

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

> > I guess the reimplementation came too late (happens sometimes)
> > And I agree that making kfifos record oriented makes sense.
> 
> What does it mean? To late for 2.6.33 or to late to replace it for ever?

For 2.6.33 it's too late. Perhaps 2.6.34.

For 2.6.33 we just have to fix what's in. That is why I think
my patches are needed.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

On Mon, Dec 28, 2009 at 08:42:16AM +0100, Stefani Seibold wrote:
> Anyway, I ack all your patches, expect the "2/6 Make kfifo_in atomic"
> which will break my future work.

That's the most important patch. Without those kfifo_in() is 
unusable for any record size not a power of two imho.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Montag, den 28.12.2009, 15:57 +0100 schrieb Andi Kleen:
> On Mon, Dec 28, 2009 at 08:42:16AM +0100, Stefani Seibold wrote:
> > Anyway, I ack all your patches, expect the "2/6 Make kfifo_in atomic"
> > which will break my future work.
> 
> That's the most important patch. Without those kfifo_in() is 
> unusable for any record size not a power of two imho.
> 

Yes, i understand. That is why i rewrote the API. But if we apply this
patch, the future type safe interface will be broken. Because the
current implementation is based on the "unsigned char" type. And for
this types it works as expected.

kfifo_in() and kfifo_out() process max. elements (not in bytes) and
returns the number of processed elements. For processing a single
element the new kfifo_put(), kfifo_get(), kfifo_peek() are introduced.

The new macro based kfifo is type based. So for example a

struct foo {
	int	a;
	short	b;
};

static DECLARE_KFIFO(bar, struct foo, 32);
 
will reserve 32 elements of the type "struct foo". So the power of two
is in the new implementation not the number of bytes, it is in the
meaning of elements.

So please draw back this patch, you will get exactly what you want and
need in the next release. I have now a clean, slim and fast
implementation. All what i need is a review and some ack's

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

First having to rely on another large patchkit makes 
it annoying to develop for this (it's the linux kernel
equivalent of DLL hell), but ok. I hope the interface
doesn't change again at least.

> So please draw back this patch, you will get exactly what you want and
> need in the next release. I have now a clean, slim and fast
> implementation. All what i need is a review and some ack's

How about the current users for 2.6.33?  Unless they are not 
record oriented or always put in power-of-two records they will
need this patch, otherwise they risk desynchronization on fifo
full.

I think the patch is needed.

Also should drop the unused interfaces for 2.6.33 before anyone
else tries to use them and gets the same nasty surprise as me.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Montag, den 28.12.2009, 18:26 +0100 schrieb Andi Kleen:
> First having to rely on another large patchkit makes 
> it annoying to develop for this (it's the linux kernel
> equivalent of DLL hell), but ok. I hope the interface
> doesn't change again at least.
> 

The interface hasn't been changed, only the implementation. So it should
be not a big issue for the users of the kfifo API! Programming is
sometimes like evolution. But i think the macro based version is now the
right and best solution which a lot of benefits for the users. 

> > So please draw back this patch, you will get exactly what you want and
> > need in the next release. I have now a clean, slim and fast
> > implementation. All what i need is a review and some ack's
> 
> How about the current users for 2.6.33?  Unless they are not 
> record oriented or always put in power-of-two records they will
> need this patch, otherwise they risk desynchronization on fifo
> full.
> 
> I think the patch is needed.
> 

It is exactly the same behavior as the old kfifo API, so no user relies
on the new "kfifo_in atomic" feature. The only user is you. And it is
easy for you to to check if enough room is available with kfifo_avail()
before calling kfifo_in(). That is exactly what your patch do inside the
kfifo_in() function. 

> Also should drop the unused interfaces for 2.6.33 before anyone
> else tries to use them and gets the same nasty surprise as me.
> 

Nasty surprise? Sorry, but i accepted all your patches, excluded one,
which breaks my future work. And i implemented all your suggestions in
my new macro based kfifo API in less than a day. So where is the
problem? You modified the interface not me! Nobody relies currently on
your patches, it's only you.
 
I will send a patch to Andrew for removing kfifo_*_rec() functions if
you like and i hope for your cooperation. Again please draw back your
"kfifo_in atomic" patch. 

And for 2.6.34 everything will be fine :-)

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andi Kleen]

On Mon, Dec 28, 2009 at 09:04:13PM +0100, Stefani Seibold wrote:
> The interface hasn't been changed, only the implementation. So it should

Ok I guess I was still thinking of your earlier version which
had a new interface.

> It is exactly the same behavior as the old kfifo API, so no user relies
> on the new "kfifo_in atomic" feature. The only user is you. And it is

That's not established. They might be just broken.

OK i checked and they all use power-of-two currently so by sheer
luck (I doubt it is by design) they work. Still I think that
open deathtrap should be fixed.

I also don't understand how that patch "breaks your future work"
Please elaborate on that.

-Andi

P.S.: I must say you make it really hard to use kfifos.

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Montag, den 28.12.2009, 21:40 +0100 schrieb Andi Kleen:


> OK i checked and they all use power-of-two currently so by sheer
> luck (I doubt it is by design) they work. Still I think that
> open deathtrap should be fixed.
> 

It is fixed, and i hope it will be included in 2.6.34.

> I also don't understand how that patch "breaks your future work"
> Please elaborate on that.
> 

Very difficult to explain in a email, but i will try it:

The new macro based kfifo API handles everything as elements of a given
type. So you can have the old "unsigned char"-fifo, but also fifo of
every other type like int's, struct's and so on. The kfifo_in() and
kfifo_out() len parameter is than in the meaning of elements not bytes.
So you are able to process more than one value at a time and the macros
will return the number of processed elements (not bytes). 

kfifo_in(), kfifo_out() and kfifi_out_peek() are more in a meaning of a
max. memcpy(). For a single value it is better to use new introduced
macros kfifo_put(), kfifo_get() and kfifo_peek(), which doesn't require
the len parameter and are faster pod data types.

With this solution i have full compatibility to the orig kfifo
implementation, i can fill a fifo with a minimum of operations, and   
the desynchronization problem is also gone.

Have a look at example:

#include "kfifo.h"

#define FIFO_ELEMS	32

// declare a fifo named test with 32 int's
static DECLARE_KFIFO(test, int, FIFO_ELEMS);

void testfunc(void)
{
	int		i;
	int		buf[6];
	unsigned int 	ret;

	INIT_KFIFO(test);

	for(i = 20; i != 30; i++)
		kfifo_put(&test, &i);

	// show the number of elements in the fifo
	printk("queue len: %u\n", kfifo_len(&test)); 

	// get max. two int elements from the fifo
	ret = kfifo_out(&test, buf, 2);

	// show the number of processed elements
	printk("ret: %d\n", ret);

	// put max. two int elements in the fifo
	ret = kfifo_in(&test, buf, 2);

	// show the number of processed elements
	printk("ret: %d\n", ret);

	if (kfifo_peek(&test, &i))
		printk("%d\n", i);

	while(kfifo_get(&test, &i))
		printk("%d\n", i);
}

> -Andi
> 
> P.S.: I must say you make it really hard to use kfifos.
> 

Sorry, that was not my intention. But the old API was much harder to
use ;-)

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Dmitry Torokhov]

On Dec 29, 2009, at 12:40 AM, Stefani Seibold <stefani@seibold.net>  
wrote:

> Am Montag, den 28.12.2009, 21:40 +0100 schrieb Andi Kleen:
>
>
>> OK i checked and they all use power-of-two currently so by sheer
>> luck (I doubt it is by design) they work. Still I think that
>> open deathtrap should be fixed.
>>
>
> It is fixed, and i hope it will be included in 2.6.34.
>
>> I also don't understand how that patch "breaks your future work"
>> Please elaborate on that.
>>
>
> Very difficult to explain in a email, but i will try it:
>
> The new macro based kfifo API handles everything as elements of a  
> given
> type. So you can have the old "unsigned char"-fifo, but also fifo of
> every other type like int's, struct's and so on. The kfifo_in() and
> kfifo_out() len parameter is than in the meaning of elements not  
> bytes.
> So you are able to process more than one value at a time and the  
> macros
> will return the number of processed elements (not bytes).

Does anyone want this kind of functionality though? Why can't we keep  
the old interface as is (and maybe deprecate it) and use the new  
record API you mentioned below for record-oriented kfifos.

Thanks.

-- 
Dmitry

Re: [PATCH] [0/6] kfifo fixes/improvements

[Vikram Dhillon]

IMHO you can process elements rather than bytes, which is a good
improvement, but then again its my opinion, if others don't like it
then we can always change it :D

Regards,
Vikram Dhillon

~~~
There are lots of Linux users who don't care how the kernel works, but
only want to use it. That is a tribute to how good Linux is.
-- Linus Torvalds



On Tue, Dec 29, 2009 at 5:27 PM, Dmitry Torokhov
<dmitry.torokhov@gmail.com> wrote:
> On Dec 29, 2009, at 12:40 AM, Stefani Seibold <stefani@seibold.net> wrote:
>
>> Am Montag, den 28.12.2009, 21:40 +0100 schrieb Andi Kleen:
>>
>>
>>> OK i checked and they all use power-of-two currently so by sheer
>>> luck (I doubt it is by design) they work. Still I think that
>>> open deathtrap should be fixed.
>>>
>>
>> It is fixed, and i hope it will be included in 2.6.34.
>>
>>> I also don't understand how that patch "breaks your future work"
>>> Please elaborate on that.
>>>
>>
>> Very difficult to explain in a email, but i will try it:
>>
>> The new macro based kfifo API handles everything as elements of a given
>> type. So you can have the old "unsigned char"-fifo, but also fifo of
>> every other type like int's, struct's and so on. The kfifo_in() and
>> kfifo_out() len parameter is than in the meaning of elements not bytes.
>> So you are able to process more than one value at a time and the macros
>> will return the number of processed elements (not bytes).
>
> Does anyone want this kind of functionality though? Why can't we keep the
> old interface as is (and maybe deprecate it) and use the new record API you
> mentioned below for record-oriented kfifos.
>
> Thanks.
>
> --
> Dmitry
>
> --
> 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: [PATCH] [0/6] kfifo fixes/improvements

[Dmitry Torokhov]

A: http://en.wikipedia.org/wiki/Top_post
Q: Were do I find info about this thing called top-posting?
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?

On Tue, Dec 29, 2009 at 08:18:50PM -0500, Vikram Dhillon wrote:
> IMHO you can process elements rather than bytes, which is a good
> improvement, but then again its my opinion, if others don't like it
> then we can always change it :D

Right, I was not arguing against having a record-oriented interface, I
was questioning the utility of processing several records at a time.
Kfifo users that I have seen so far were working in a record-at-a-time
mode.

Thanks.

-- 
Dmitry

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

> On Tue, Dec 29, 2009 at 08:18:50PM -0500, Vikram Dhillon wrote:
> > IMHO you can process elements rather than bytes, which is a good
> > improvement, but then again its my opinion, if others don't like it
> > then we can always change it :D
> 
> Right, I was not arguing against having a record-oriented interface, I
> was questioning the utility of processing several records at a time.
> Kfifo users that I have seen so far were working in a record-at-a-time
> mode.
> 

Fascinating, i get a lot of comments, but no one is trying the new macro
base implementation. If someone would, this person would see, that is
100% compatible to the current one and absolut easy to use. Please try
it first bevor argue and complain.

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Dmitry Torokhov]

On Wed, Dec 30, 2009 at 10:29:50AM +0100, Stefani Seibold wrote:
> 
> > On Tue, Dec 29, 2009 at 08:18:50PM -0500, Vikram Dhillon wrote:
> > > IMHO you can process elements rather than bytes, which is a good
> > > improvement, but then again its my opinion, if others don't like it
> > > then we can always change it :D
> > 
> > Right, I was not arguing against having a record-oriented interface, I
> > was questioning the utility of processing several records at a time.
> > Kfifo users that I have seen so far were working in a record-at-a-time
> > mode.
> > 
> 
> Fascinating, i get a lot of comments, but no one is trying the new macro
> base implementation. If someone would, this person would see, that is
> 100% compatible to the current one and absolut easy to use. Please try
> it first bevor argue and complain.
> 

I do not need to try the new behavior - you explained it quite well.
You changed the old API to allow processing multiple records at a time
and it does not quite work the way you want with Andi's patch. Now the
question is: when working with _records_ does anyone really want to
put/get more than 1 record at a time? My answer would be "no, most users
work with 1 record at a time". Thus your changes to the old API are not
needed.

-- 
Dmitry

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Mittwoch, den 30.12.2009, 02:43 -0800 schrieb Dmitry Torokhov:
> On Wed, Dec 30, 2009 at 10:29:50AM +0100, Stefani Seibold wrote:
> >
> I do not need to try the new behavior - you explained it quite well.
> You changed the old API to allow processing multiple records at a time
> and it does not quite work the way you want with Andi's patch. Now the

Wrong, i did not change the behavior of the old API. It is exactly the
same at is was!!!!

> question is: when working with _records_ does anyone really want to
> put/get more than 1 record at a time? My answer would be "no, most users

Your answer is wrong. All current user depend on it, because it
(miss)use a byte stream to store values other than bytes to it.
 
> work with 1 record at a time". Thus your changes to the old API are not
> needed.
> 

A lot of hot air... Better you check the code before complain.

Stefani

Re: [PATCH] [0/6] kfifo fixes/improvements

[Dmitry Torokhov]

On Wed, Dec 30, 2009 at 11:52:15AM +0100, Stefani Seibold wrote:
> Am Mittwoch, den 30.12.2009, 02:43 -0800 schrieb Dmitry Torokhov:
> > On Wed, Dec 30, 2009 at 10:29:50AM +0100, Stefani Seibold wrote:
> > >
> > I do not need to try the new behavior - you explained it quite well.
> > You changed the old API to allow processing multiple records at a time
> > and it does not quite work the way you want with Andi's patch. Now the
> 
> Wrong, i did not change the behavior of the old API. It is exactly the
> same at is was!!!!

You said:

"The kfifo_in() and kfifo_out() len parameter is than in the meaning
of elements not bytes."

This is the change from the existing API which works with _bytes_:

/**
 * kfifo_in - puts some data into the FIFO
 * @fifo: the fifo to be used.
 * @from: the data to be added.
 * @len: the length of the data to be added.
 *
 * This function copies at most @len bytes from the @from buffer into
                                ^^^^^^^^^^
 * the FIFO depending on the free space, and returns the number of
 * bytes copied.


> 
> > question is: when working with _records_ does anyone really want to
> > put/get more than 1 record at a time? My answer would be "no, most users
> 
> Your answer is wrong. All current user depend on it, because it
> (miss)use a byte stream to store values other than bytes to it.

However all of them that I know of deposit and fetch exactly one record
at a time (the fact that they are more than 1 byte is immaterial).

>  
> > work with 1 record at a time". Thus your changes to the old API are not
> > needed.
> > 
> 
> A lot of hot air...

*sigh* That's an iron-clad argument right there.

-- 
Dmitry

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Mittwoch, den 30.12.2009, 03:07 -0800 schrieb Dmitry Torokhov:
> On Wed, Dec 30, 2009 at 11:52:15AM +0100, Stefani Seibold wrote:
> > Am Mittwoch, den 30.12.2009, 02:43 -0800 schrieb Dmitry Torokhov:
> > > On Wed, Dec 30, 2009 at 10:29:50AM +0100, Stefani Seibold wrote:
> > > >
> > > I do not need to try the new behavior - you explained it quite well.
> > > You changed the old API to allow processing multiple records at a time
> > > and it does not quite work the way you want with Andi's patch. Now the
> > 
> > Wrong, i did not change the behavior of the old API. It is exactly the
> > same at is was!!!!
> 
> You said:
> 
> "The kfifo_in() and kfifo_out() len parameter is than in the meaning
> of elements not bytes."
> 
> This is the change from the existing API which works with _bytes_:
> 
> /**
>  * kfifo_in - puts some data into the FIFO
>  * @fifo: the fifo to be used.
>  * @from: the data to be added.
>  * @len: the length of the data to be added.
>  *
>  * This function copies at most @len bytes from the @from buffer into
>                                 ^^^^^^^^^^
>  * the FIFO depending on the free space, and returns the number of
>  * bytes copied.
> 
> 

There is no change!!!!!! For a byte type fifo, which is the old orig
type, the number of elements is exactly the number of bytes. 

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andy Walls]

On Tue, 2009-12-29 at 14:27 -0800, Dmitry Torokhov wrote:
> On Dec 29, 2009, at 12:40 AM, Stefani Seibold <stefani@seibold.net>  
> wrote:
> 
> > Am Montag, den 28.12.2009, 21:40 +0100 schrieb Andi Kleen:
> >
> >
> >> OK i checked and they all use power-of-two currently so by sheer
> >> luck (I doubt it is by design) they work. Still I think that
> >> open deathtrap should be fixed.
> >>
> >
> > It is fixed, and i hope it will be included in 2.6.34.
> >
> >> I also don't understand how that patch "breaks your future work"
> >> Please elaborate on that.
> >>
> >
> > Very difficult to explain in a email, but i will try it:
> >
> > The new macro based kfifo API handles everything as elements of a  
> > given
> > type. So you can have the old "unsigned char"-fifo, but also fifo of
> > every other type like int's, struct's and so on. The kfifo_in() and
> > kfifo_out() len parameter is than in the meaning of elements not  
> > bytes.
> > So you are able to process more than one value at a time and the  
> > macros
> > will return the number of processed elements (not bytes).
> 
> Does anyone want this kind of functionality though? Why can't we keep  
> the old interface as is (and maybe deprecate it) and use the new  
> record API you mentioned below for record-oriented kfifos.

Yes.  I will eventually convert my use of kfifo to use records of size
'u32' as opposed to reading and writing in multiples of 4 bytes.  (I
have some ugly checks right now to make sure whenever I read from a
kfifo I get back a multiple of 4 bytes.)

I'm just waiting for the churn to settle.

Regards,
Andy

> Thanks.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andy Walls]

On Tue, 2009-12-29 at 18:08 -0800, Dmitry Torokhov wrote:
> A: http://en.wikipedia.org/wiki/Top_post
> Q: Were do I find info about this thing called top-posting?
> A: Because it messes up the order in which people normally read text.
> Q: Why is top-posting such a bad thing?
> 
> On Tue, Dec 29, 2009 at 08:18:50PM -0500, Vikram Dhillon wrote:
> > IMHO you can process elements rather than bytes, which is a good
> > improvement, but then again its my opinion, if others don't like it
> > then we can always change it :D
> 
> Right, I was not arguing against having a record-oriented interface, I
> was questioning the utility of processing several records at a time.
> Kfifo users that I have seen so far were working in a record-at-a-time
> mode.

I have a use case in linux/drivers/media/video/cx23885/cx23888-ir.c
right now.

I have a hardware fifo that can hold up to 8 values, 17 bits each - and
the high bit of the value is a flag indicating if more data is in the
hardware fifo.

The hardware fifo watermark for generating an interrupt is 4 or more
values in the hardware fifo.

I use a kfifo that needs to be protected with a spinlock.

It in much better in the IRQ context to drain the hardware fifo and then
put records in the kfifo all at once (or at least in groups of 8 or less
but usually greater than 1).

Regards,
Andy

> Thanks.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Dmitry Torokhov]

On Wed, Dec 30, 2009 at 12:29:12PM -0500, Andy Walls wrote:
> On Tue, 2009-12-29 at 18:08 -0800, Dmitry Torokhov wrote:
> > A: http://en.wikipedia.org/wiki/Top_post
> > Q: Were do I find info about this thing called top-posting?
> > A: Because it messes up the order in which people normally read text.
> > Q: Why is top-posting such a bad thing?
> > 
> > On Tue, Dec 29, 2009 at 08:18:50PM -0500, Vikram Dhillon wrote:
> > > IMHO you can process elements rather than bytes, which is a good
> > > improvement, but then again its my opinion, if others don't like it
> > > then we can always change it :D
> > 
> > Right, I was not arguing against having a record-oriented interface, I
> > was questioning the utility of processing several records at a time.
> > Kfifo users that I have seen so far were working in a record-at-a-time
> > mode.
> 
> I have a use case in linux/drivers/media/video/cx23885/cx23888-ir.c
> right now.
> 
> I have a hardware fifo that can hold up to 8 values, 17 bits each - and
> the high bit of the value is a flag indicating if more data is in the
> hardware fifo.
> 
> The hardware fifo watermark for generating an interrupt is 4 or more
> values in the hardware fifo.
> 
> I use a kfifo that needs to be protected with a spinlock.
> 
> It in much better in the IRQ context to drain the hardware fifo and then
> put records in the kfifo all at once (or at least in groups of 8 or less
> but usually greater than 1).

Hmm, so there you have a local buffer that you fill by reading from the
device word by word, then you copy that data over into fifo and then you
upper layer again fetches that fifo as byte stream...

I'd probably simply move the processing that you are doing in
cx23888_ir_rx_read() into cx23888_ir_irq_handler() (since it is very
simple) and then used kfifo in simple byte mode (since that is what
upper layer seem to expect).

-- 
Dmitry

Re: [PATCH] [0/6] kfifo fixes/improvements

[Stefani Seibold]

Am Mittwoch, den 30.12.2009, 23:35 -0800 schrieb Dmitry Torokhov:

> > I have a use case in linux/drivers/media/video/cx23885/cx23888-ir.c
> > right now.
> > 
> > I have a hardware fifo that can hold up to 8 values, 17 bits each - and
> > the high bit of the value is a flag indicating if more data is in the
> > hardware fifo.
> > 
> > The hardware fifo watermark for generating an interrupt is 4 or more
> > values in the hardware fifo.
> > 
> > I use a kfifo that needs to be protected with a spinlock.
> > 
> > It in much better in the IRQ context to drain the hardware fifo and then
> > put records in the kfifo all at once (or at least in groups of 8 or less
> > but usually greater than 1).
> 
> Hmm, so there you have a local buffer that you fill by reading from the
> device word by word, then you copy that data over into fifo and then you
> upper layer again fetches that fifo as byte stream...
> 
> I'd probably simply move the processing that you are doing in
> cx23888_ir_rx_read() into cx23888_ir_irq_handler() (since it is very
> simple) and then used kfifo in simple byte mode (since that is what
> upper layer seem to expect).
> 

Why using byte mode? He can use any type he like, the new macro based
implementation is record based! And a record can be a byte or any other
data type. Why do you discuss about code you didn't understand and want
not try? Why to discuss and waste time about less than 400 bytes of
library code? Terminate this useless discussion.

Re: [PATCH] [0/6] kfifo fixes/improvements

[Dmitry Torokhov]

On Thu, Dec 31, 2009 at 09:59:51AM +0100, Stefani Seibold wrote:
> Am Mittwoch, den 30.12.2009, 23:35 -0800 schrieb Dmitry Torokhov:
> 
> > > I have a use case in linux/drivers/media/video/cx23885/cx23888-ir.c
> > > right now.
> > > 
> > > I have a hardware fifo that can hold up to 8 values, 17 bits each - and
> > > the high bit of the value is a flag indicating if more data is in the
> > > hardware fifo.
> > > 
> > > The hardware fifo watermark for generating an interrupt is 4 or more
> > > values in the hardware fifo.
> > > 
> > > I use a kfifo that needs to be protected with a spinlock.
> > > 
> > > It in much better in the IRQ context to drain the hardware fifo and then
> > > put records in the kfifo all at once (or at least in groups of 8 or less
> > > but usually greater than 1).
> > 
> > Hmm, so there you have a local buffer that you fill by reading from the
> > device word by word, then you copy that data over into fifo and then you
> > upper layer again fetches that fifo as byte stream...
> > 
> > I'd probably simply move the processing that you are doing in
> > cx23888_ir_rx_read() into cx23888_ir_irq_handler() (since it is very
> > simple) and then used kfifo in simple byte mode (since that is what
> > upper layer seem to expect).
> > 
> 
> Why using byte mode? He can use any type he like, the new macro based
> implementation is record based! And a record can be a byte or any other
> data type. Why do you discuss about code you didn't understand and want
> not try? Why to discuss and waste time about less than 400 bytes of
> library code? Terminate this useless discussion.
> 

Yes, indeed. 

-- 
Dmitry

Re: [PATCH] [0/6] kfifo fixes/improvements

[Andy Walls]

On Wed, 2009-12-30 at 23:35 -0800, Dmitry Torokhov wrote:
> On Wed, Dec 30, 2009 at 12:29:12PM -0500, Andy Walls wrote:
> > On Tue, 2009-12-29 at 18:08 -0800, Dmitry Torokhov wrote:
> > > A: http://en.wikipedia.org/wiki/Top_post
> > > Q: Were do I find info about this thing called top-posting?
> > > A: Because it messes up the order in which people normally read text.
> > > Q: Why is top-posting such a bad thing?
> > > 
> > > On Tue, Dec 29, 2009 at 08:18:50PM -0500, Vikram Dhillon wrote:
> > > > IMHO you can process elements rather than bytes, which is a good
> > > > improvement, but then again its my opinion, if others don't like it
> > > > then we can always change it :D
> > > 
> > > Right, I was not arguing against having a record-oriented interface, I
> > > was questioning the utility of processing several records at a time.
> > > Kfifo users that I have seen so far were working in a record-at-a-time
> > > mode.
> > 
> > I have a use case in linux/drivers/media/video/cx23885/cx23888-ir.c
> > right now.
> > 
> > I have a hardware fifo that can hold up to 8 values, 17 bits each - and
> > the high bit of the value is a flag indicating if more data is in the
> > hardware fifo.
> > 
> > The hardware fifo watermark for generating an interrupt is 4 or more
> > values in the hardware fifo.
> > 
> > I use a kfifo that needs to be protected with a spinlock.
> > 
> > It in much better in the IRQ context to drain the hardware fifo and then
> > put records in the kfifo all at once (or at least in groups of 8 or less
> > but usually greater than 1).
> 
> Hmm, so there you have a local buffer that you fill by reading from the
> device word by word, then you copy that data over into fifo and then you
> upper layer again fetches that fifo as byte stream...

Well technically the upper layer should be fetching data as a 4 byte
(u32 record) stream, but at the time I wrote my usage, kfifo only had
byte oriented usage for reading out of the kfifo.

Now that the spinlock has moved out of kfifo, I suppose when I convert
to record based usage, I don't strictly need multiple record puts into
the kfifo.  Since now my code can have fine grained control of when the
spinlock is taken and released, when I move to record based, I could
just put records into the kfifo one at a time with little penalty.

It really doesn't matter to me since the spinlock acquire and release,
saving and restoring the processor flags, was the big penalty.


> I'd probably simply move the processing that you are doing in
> cx23888_ir_rx_read() into cx23888_ir_irq_handler() (since it is very
> simple) and then used kfifo in simple byte mode (since that is what
> upper layer seem to expect).

Well, the the upper layer is really in a work handler that calls

	cx23885-input.c:cx23885_input_process_pulse_widths_rc5()

for RC-5 decoding for example.  It ends up calling cx23888_ir_rx_read()
to read in a number of 4 bytes (u32) pulse width records in a batch.  It
then feeds those records through the RC-5 decoding process one record at
a time (because that was the simple way to implement a decoding state
machine).

The idea was to avoid all the spinlock acquire release penalties
associtaed with accessing the kfifo, and to avoid contention with the
IRQ handler.


(BTW, I split the unit conversion work out to cx23888_ir_rx_read() with
IRQ latency in mind.  Since this is a video capture card with other,
more important interrupts to service, I just didn't want to spend any
extra CPU cycles in the cx23888_ir_irq_handler than necessary.  A work
handler context calling into cx23888_ir_rx_read() is a preferable
context in which to perform unit conversions compared to an IRQ context,
IMO.)
	


So in summary, I think any need I had for multiple record kfifo access
can be worked around by having the spinlock separate from the kfifo
calls.  However, with multiple record kfifo access methods available,
I'd likely find a convenient use for such methods.

Regards,
Andy

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Andrew Morton]

On Mon, 28 Dec 2009 00:41:37 +0100
Andi Kleen <andi@firstfloor.org> wrote:

> On Sun, Dec 27, 2009 at 10:49:49PM +0100, Stefani Seibold wrote:
> > Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> > > In some upcoming code it's useful to peek into a FIFO without
> > > permanentely removing data. This patch implements a new 
> > > kfifo_out_peek() to do this. 
> > > 
> > 
> > Yes this function can be useful. I will implement it in the macro
> > version of the kfifo.
> 
> Well that doesn't help me -- I need a working kfifo on a 2.6.33
> base. Or do you want to abandon the old interface?
> 
> I must say I'm a little surprised by the general tone of  
> your comments -- first you submit these patches all the time and when they 
> finally get reviewed and merged and people start to use them and make them 
> production ready you state it's all abandoned.

Yup, the first priority is to get the 2.6.33 code fixed up.  It is
unwise to assume that we'll be merging some other patch some time in
the future.

Macros are unpopular, for good reasons.  But the case for a
template-based container such as this is a good one.  However I worry
about the code bloat whcih the macro version might add.  We worry about
all this later on.

> 
> Anyways Andrew could you please merge these fixes? Thanks.

I shall.  Stefani, pelase review those patches for 2.6.33 suitability. 
Let's not worry about a big rewrite at this time.

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Alan Cox]

> Macros are unpopular, for good reasons.  But the case for a
> template-based container such as this is a good one.  However I worry
> about the code bloat whcih the macro version might add.  We worry about
> all this later on.

Its really a special case for structs and fixed objects.

Bloat is going to be a big issue if its macro and all the serial/tty
stuff switches to it. Please keep the bytewise one none macro - even if
its a lib/foo.c file that simply uses the macros to produce the existing
new API.

Re: [PATCH] [3/6] kfifo: Sanitize *_user error handling

[Stefani Seibold]

Andrew ask me for a review... Don't do multiplexing again, lenout should
return the number of copied bytes and not an error code.

Am Sonntag, den 27.12.2009, 22:03 +0100 schrieb Andi Kleen:
> Right now for kfifo_*_user it's not easily possible to distingush between a 
> user copy failing and the FIFO not containing enough data. The problem 
> is that both conditions are multiplexed into the same return code.
> 
> Avoid this by moving the "copy length" into a separate output parameter
> and only return 0/-EFAULT in the main return value.
> 
> I didn't fully adapt the weird "record" variants, those seem 
> to be unused anyways and were rather messy (should they be just removed?)
> 
> I would appreciate some double checking if I did all the conversions
> correctly.
> 
> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> ---
>  include/linux/kfifo.h |    8 ++---
>  kernel/kfifo.c        |   76 ++++++++++++++++++++++++++++++++------------------
>  2 files changed, 53 insertions(+), 31 deletions(-)
> 
> Index: linux/include/linux/kfifo.h
> ===================================================================
> --- linux.orig/include/linux/kfifo.h
> +++ linux/include/linux/kfifo.h
> @@ -243,11 +243,11 @@ static inline __must_check unsigned int
>  
>  extern void kfifo_skip(struct kfifo *fifo, unsigned int len);
>  
> -extern __must_check unsigned int kfifo_from_user(struct kfifo *fifo,
> -	const void __user *from, unsigned int n);
> +extern __must_check int kfifo_from_user(struct kfifo *fifo,
> +	const void __user *from, unsigned int n, unsigned *lenout);
>  
> -extern __must_check unsigned int kfifo_to_user(struct kfifo *fifo,
> -	void __user *to, unsigned int n);
> +extern __must_check int kfifo_to_user(struct kfifo *fifo,
> +	void __user *to, unsigned int n, unsigned *lenout);
>  
>  /**
>   * __kfifo_add_out internal helper function for updating the out offset
> Index: linux/kernel/kfifo.c
> ===================================================================
> --- linux.orig/kernel/kfifo.c
> +++ linux/kernel/kfifo.c
> @@ -159,8 +159,9 @@ static inline void __kfifo_out_data(stru
>  	memcpy(to + l, fifo->buffer, len - l);
>  }
>  
> -static inline unsigned int __kfifo_from_user_data(struct kfifo *fifo,
> -	 const void __user *from, unsigned int len, unsigned int off)
> +static inline int __kfifo_from_user_data(struct kfifo *fifo,
> +	 const void __user *from, unsigned int len, unsigned int off,
> +	 unsigned *lenout)
>  {
>  	unsigned int l;
>  	int ret;
> @@ -177,16 +178,20 @@ static inline unsigned int __kfifo_from_
>  	/* first put the data starting from fifo->in to buffer end */
>  	l = min(len, fifo->size - off);
>  	ret = copy_from_user(fifo->buffer + off, from, l);
> -
> -	if (unlikely(ret))
> -		return ret + len - l;
> +	if (unlikely(ret)) {
> +		*lenout = ret;

Should lenout not contain the number of copied bytes? So i would prefer 
		  *lenout = l -ret;

> +		return -EFAULT;
> +	}
> +	*lenout = l;

Unnecessary.... Would 

>  
>  	/* then put the rest (if any) at the beginning of the buffer */
> -	return copy_from_user(fifo->buffer, from + l, len - l);
> +	ret = copy_from_user(fifo->buffer, from + l, len - l);
> +	*lenout += ret ? ret : len - l;

	if (unlikely(ret)) {
		*lenout = len - ret;
		return -EFAULT;
	}
> 
> +	return ret ? -EFAULT : 0;

Sould be return 0;

>  }

>  
> -static inline unsigned int __kfifo_to_user_data(struct kfifo *fifo,
> -		void __user *to, unsigned int len, unsigned int off)
> +static inline int __kfifo_to_user_data(struct kfifo *fifo,
> +		void __user *to, unsigned int len, unsigned int off, unsigned *lenout)
>  {
>  	unsigned int l;
>  	int ret;
> @@ -203,12 +208,21 @@ static inline unsigned int __kfifo_to_us
>  	/* first get the data from fifo->out until the end of the buffer */
>  	l = min(len, fifo->size - off);
>  	ret = copy_to_user(to, fifo->buffer + off, l);
> -
> -	if (unlikely(ret))
> -		return ret + len - l;
> +	*lenout = l;
> +	if (unlikely(ret)) {
> +		*lenout -= ret;
> +		return -EFAULT;
> +	}
>  
>  	/* then get the rest (if any) from the beginning of the buffer */
> -	return copy_to_user(to + l, fifo->buffer, len - l);
> +	len -= l;
> +	ret = copy_to_user(to + l, fifo->buffer, len);
> +	if (unlikely(ret)) {
> +		*lenout += len - ret;
> +		return -EFAULT;
> +	}
> +	*lenout += len;
> +	return 0;
>  }
>  
>  unsigned int __kfifo_in_n(struct kfifo *fifo,
> @@ -298,10 +312,13 @@ EXPORT_SYMBOL(__kfifo_out_generic);
>  unsigned int __kfifo_from_user_n(struct kfifo *fifo,
>  	const void __user *from, unsigned int len, unsigned int recsize)
>  {
> +	unsigned total;
> +
>  	if (kfifo_avail(fifo) < len + recsize)
>  		return len + 1;
>  
> -	return __kfifo_from_user_data(fifo, from, len, recsize);
> +	__kfifo_from_user_data(fifo, from, len, recsize, &total);
> +	return total;
>  }
>  EXPORT_SYMBOL(__kfifo_from_user_n);
>  
> @@ -312,18 +329,21 @@ EXPORT_SYMBOL(__kfifo_from_user_n);
>   * @len: the length of the data to be added.
>   *
>   * This function copies at most @len bytes from the @from into the
> - * FIFO depending and returns the number of copied bytes.
> + * FIFO depending and returns -EFAULT/0.
>   *
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
>   */
> -unsigned int kfifo_from_user(struct kfifo *fifo,
> -	const void __user *from, unsigned int len)
> +int kfifo_from_user(struct kfifo *fifo,
> +        const void __user *from, unsigned int len, unsigned *total)
>  {
> +	int ret;
>  	len = min(kfifo_avail(fifo), len);
> -	len -= __kfifo_from_user_data(fifo, from, len, 0);
> +	ret = __kfifo_from_user_data(fifo, from, len, 0, total);
> +	if (ret)
> +		return ret;
>  	__kfifo_add_in(fifo, len);
> -	return len;
> +	return 0;
>  }
>  EXPORT_SYMBOL(kfifo_from_user);
>  
> @@ -338,17 +358,17 @@ unsigned int __kfifo_to_user_n(struct kf
>  	void __user *to, unsigned int len, unsigned int reclen,
>  	unsigned int recsize)
>  {
> -	unsigned int ret;
> +	unsigned int ret, total;
>  
>  	if (kfifo_len(fifo) < reclen + recsize)
>  		return len;
>  
> -	ret = __kfifo_to_user_data(fifo, to, reclen, recsize);
> +	ret = __kfifo_to_user_data(fifo, to, reclen, recsize, &total);
>  
>  	if (likely(ret == 0))
>  		__kfifo_add_out(fifo, reclen + recsize);
>  
> -	return ret;
> +	return total;
>  }
>  EXPORT_SYMBOL(__kfifo_to_user_n);
>  
> @@ -357,20 +377,22 @@ EXPORT_SYMBOL(__kfifo_to_user_n);
>   * @fifo: the fifo to be used.
>   * @to: where the data must be copied.
>   * @len: the size of the destination buffer.
> + @ @lenout: pointer to output variable with copied data
>   *
>   * This function copies at most @len bytes from the FIFO into the
> - * @to buffer and returns the number of copied bytes.
> + * @to buffer and 0 or -EFAULT.
>   *
>   * Note that with only one concurrent reader and one concurrent
>   * writer, you don't need extra locking to use these functions.
>   */
> -unsigned int kfifo_to_user(struct kfifo *fifo,
> -	void __user *to, unsigned int len)
> +int kfifo_to_user(struct kfifo *fifo,
> +	void __user *to, unsigned int len, unsigned *lenout)
>  {
> +	int ret;
>  	len = min(kfifo_len(fifo), len);
> -	len -= __kfifo_to_user_data(fifo, to, len, 0);
> -	__kfifo_add_out(fifo, len);
> -	return len;
> +	ret = __kfifo_to_user_data(fifo, to, len, 0, lenout);
> +	__kfifo_add_out(fifo, *lenout);
> +	return ret;
>  }
>  EXPORT_SYMBOL(kfifo_to_user);
>  

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Stefani Seibold]

Am Montag, den 04.01.2010, 22:24 +0000 schrieb Alan Cox:
> > Macros are unpopular, for good reasons.  But the case for a
> > template-based container such as this is a good one.  However I worry
> > about the code bloat whcih the macro version might add.  We worry about
> > all this later on.
> 
> Its really a special case for structs and fixed objects.
> 
> Bloat is going to be a big issue if its macro and all the serial/tty
> stuff switches to it. Please keep the bytewise one none macro - even if
> its a lib/foo.c file that simply uses the macros to produce the existing
> new API.

Nope, currently the bytewise is the special case. Most of the user of
kfifo try to store other type then bytes in a fifo. 

The new macro based kfifo does not bloat the code, the opposite is the
truth. I checked the assembler output on intel and ppc and the generated
code is smaller and better.

The macro are written in a way that you get a useful single line compile
time error message.

Also "the power of two" thing will make the kfifo not very useable to
handle not multiple of 2 datas, in a fifo.

At last a type safe kfifo is 100% compatible to the current kfifo if the
the is a "unsigned char".

It would be better to discuss this in the "[PATCH] new kfifo API v.08"
threat from 28.12.2009.

Regards,
Stefani

Re: [PATCH] [4/6] kfifo: add kfifo_out_peek

[Alan Cox]

> > Bloat is going to be a big issue if its macro and all the serial/tty
> > stuff switches to it. Please keep the bytewise one none macro - even if
> > its a lib/foo.c file that simply uses the macros to produce the existing
> > new API.
> 
> Nope, currently the bytewise is the special case. Most of the user of
> kfifo try to store other type then bytes in a fifo. 

If the tty layer switches to it then the bytewise one will dominately
quite rapidly as it can replace the uart_circ stuff

> The new macro based kfifo does not bloat the code, the opposite is the
> truth. I checked the assembler output on intel and ppc and the generated
> code is smaller and better.

Thats excellent