LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: "Cong WANG" <xiyou.wangcong@gmail.com>
To: linux-kernel@vger.kernel.org
Subject: [PATCH] kfifo: overflow of unsigned integer
Date: Thu, 8 Feb 2007 17:07:28 +0800	[thread overview]
Message-ID: <2375c9f90702080107v7088f835h7cdf5373d36d3c14@mail.gmail.com> (raw)

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);

 	/*

             reply	other threads:[~2007-02-08  9:07 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-02-08  9:07 Cong WANG [this message]
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

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=2375c9f90702080107v7088f835h7cdf5373d36d3c14@mail.gmail.com \
    --to=xiyou.wangcong@gmail.com \
    --cc=linux-kernel@vger.kernel.org \
    --subject='Re: [PATCH] kfifo: overflow of unsigned integer' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

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