LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] kfifo: overflow of unsigned integer
@ 2007-02-08  9:07 Cong WANG
  2007-02-08  9:38 ` Andrew Morton
  0 siblings, 1 reply; 3+ messages in thread
From: Cong WANG @ 2007-02-08  9:07 UTC (permalink / raw)
  To: linux-kernel

Kfifo is a ring-buffer in kernel which can be used as a lock-free way
for concurrent read/write when there are only one producer and one
consumer. Details of its design can be found in kernel/kfifo.c and
include/linux/kfifo.h.

You will find that the 'in' and 'out' fields of 'struct kfifo' are
both represented as 'unsigned int' and in most cases 'in' is larger
than 'out' and their difference will NOT be  over 'size'.

Now the problem is that 'in' will be *smaller* than 'out' when 'in'
overflows and 'out' doesn't (Yes, this may occur quietly.). This is
NOT what we expect, though it may not cause any serious problems if we
carefully use kfifo*() functions. And this is really a bug. This bug
affects the kernel since version 2.6.10. I have tested this patch on
x86 machines.

Signed-off-by: WANG Cong  <xiyou.wangcong@gmail.com>

---

--- kernel/kfifo.c.orig	2007-02-07 19:42:51.000000000 +0800
+++ kernel/kfifo.c	2007-02-07 19:43:31.000000000 +0800
@@ -24,6 +24,7 @@
 #include <linux/slab.h>
 #include <linux/err.h>
 #include <linux/kfifo.h>
+#include <linux/compiler.h>

 /**
  * kfifo_init - allocates a new FIFO using a preallocated buffer
@@ -120,6 +121,12 @@ unsigned int __kfifo_put(struct kfifo *f
 {
 	unsigned int l;

+	/*If only fifo->in overflows, let both overflow!*/
+	if (unlikely(fifo->in < fifo->out)) {
+		fifo->out += fifo->size;
+		fifo->in  += fifo->size;
+	}
+
 	len = min(len, fifo->size - fifo->in + fifo->out);

 	/*
@@ -166,6 +173,12 @@ unsigned int __kfifo_get(struct kfifo *f
 {
 	unsigned int l;

+	/*If only fifo->in overflows, let both overflow!*/
+	if (unlikely(fifo->in < fifo->out)) {
+		fifo->out += fifo->size;
+		fifo->in  += fifo->size;
+	}
+
 	len = min(len, fifo->in - fifo->out);

 	/*

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] kfifo: overflow of unsigned integer
  2007-02-08  9:07 [PATCH] kfifo: overflow of unsigned integer Cong WANG
@ 2007-02-08  9:38 ` Andrew Morton
       [not found]   ` <2375c9f90702080416s54664351q3df54e80459c63af@mail.gmail.com>
  0 siblings, 1 reply; 3+ messages in thread
From: Andrew Morton @ 2007-02-08  9:38 UTC (permalink / raw)
  To: Cong WANG; +Cc: linux-kernel, Stelian Pop

On Thu, 8 Feb 2007 17:07:28 +0800 "Cong WANG" <xiyou.wangcong@gmail.com> wrote:

> Kfifo is a ring-buffer in kernel which can be used as a lock-free way
> for concurrent read/write when there are only one producer and one
> consumer. Details of its design can be found in kernel/kfifo.c and
> include/linux/kfifo.h.
> 
> You will find that the 'in' and 'out' fields of 'struct kfifo' are
> both represented as 'unsigned int' and in most cases 'in' is larger
> than 'out' and their difference will NOT be  over 'size'.
> 
> Now the problem is that 'in' will be *smaller* than 'out' when 'in'
> overflows and 'out' doesn't (Yes, this may occur quietly.). This is
> NOT what we expect, though it may not cause any serious problems if we
> carefully use kfifo*() functions. And this is really a bug.

You seem to be saying that it's not a bug, but it's a bug.

Exactly what goes wrong?

> This bug
> affects the kernel since version 2.6.10. I have tested this patch on
> x86 machines.
> 
> Signed-off-by: WANG Cong  <xiyou.wangcong@gmail.com>
> 
> ---
> 
> --- kernel/kfifo.c.orig	2007-02-07 19:42:51.000000000 +0800
> +++ kernel/kfifo.c	2007-02-07 19:43:31.000000000 +0800
> @@ -24,6 +24,7 @@
>  #include <linux/slab.h>
>  #include <linux/err.h>
>  #include <linux/kfifo.h>
> +#include <linux/compiler.h>
> 
>  /**
>   * kfifo_init - allocates a new FIFO using a preallocated buffer
> @@ -120,6 +121,12 @@ unsigned int __kfifo_put(struct kfifo *f
>  {
>  	unsigned int l;
> 
> +	/*If only fifo->in overflows, let both overflow!*/
> +	if (unlikely(fifo->in < fifo->out)) {
> +		fifo->out += fifo->size;
> +		fifo->in  += fifo->size;
> +	}
> +

hm.   That would indicate that there's a problem elsewhere in the logic.


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] kfifo: overflow of unsigned integer
       [not found]     ` <20070209003732.03012671.akpm@linux-foundation.org>
@ 2007-02-10  1:56       ` Cong WANG
  0 siblings, 0 replies; 3+ messages in thread
From: Cong WANG @ 2007-02-10  1:56 UTC (permalink / raw)
  To: Andrew Morton, linux-kernel

2007/2/9, Andrew Morton <akpm@linux-foundation.org>:
> On Thu, 8 Feb 2007 20:16:55 +0800 "Cong WANG" <xiyou.wangcong@gmail.com> wrote:
>
> > 2007/2/8, Andrew Morton <akpm@linux-foundation.org>:
> > > On Thu, 8 Feb 2007 17:07:28 +0800 "Cong WANG" <xiyou.wangcong@gmail.com> wrote:
> > >
> > > > Kfifo is a ring-buffer in kernel which can be used as a lock-free way
> > > > for concurrent read/write when there are only one producer and one
> > > > consumer. Details of its design can be found in kernel/kfifo.c and
> > > > include/linux/kfifo.h.
> > > >
> > > > You will find that the 'in' and 'out' fields of 'struct kfifo' are
> > > > both represented as 'unsigned int' and in most cases 'in' is larger
> > > > than 'out' and their difference will NOT be  over 'size'.
> > > >
> > > > Now the problem is that 'in' will be *smaller* than 'out' when 'in'
> > > > overflows and 'out' doesn't (Yes, this may occur quietly.). This is
> > > > NOT what we expect, though it may not cause any serious problems if we
> > > > carefully use kfifo*() functions. And this is really a bug.
> > >
> > > You seem to be saying that it's not a bug, but it's a bug.
> > >
> > > Exactly what goes wrong?
> >
> > I wrote a module on my machine to test this bug. And when the overflow
> > occurs, I cann't put any data into the fifo even though it is not
> > full.
>
> Why did you remove the mailing list?  Please don't do that.

Sorry. I used the poor 'reply'.

>
> I can't find any bug.
>
> I converted the code so that it'll run in userspace:
>
> http://userweb.kernel.org/~akpm/kfifo.c
> http://userweb.kernel.org/~akpm/kfifo.h
>
> Please see if you can reproduce the problem with that setup and then let's
> see if we can understand what's going on, and fix it.
>
>

Thanks for your work. And you are right.

I think the OLD /proc API which I used in my module confused my eyes.
I got completely lost by that. OLD /proc API is very bad, isn't it?

BTW, can you tell me which way do you use to exchange information
between user-space and kernel-space when debugging the kernel?

Thanks again! And have a nice day!

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2007-02-10  1:56 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-02-08  9:07 [PATCH] kfifo: overflow of unsigned integer Cong WANG
2007-02-08  9:38 ` Andrew Morton
     [not found]   ` <2375c9f90702080416s54664351q3df54e80459c63af@mail.gmail.com>
     [not found]     ` <20070209003732.03012671.akpm@linux-foundation.org>
2007-02-10  1:56       ` Cong WANG

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).