linux-kernel - kfifo has temporarily invalid in pointer?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 15 Mar 2010 10:58:00 -0400 (EDT)
From:	"Robert P. J. Day" <rpjday@...shcourse.ca>
To:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: kfifo has temporarily invalid in pointer?

  (i am not trying to be annoyingly obsessive about the kernel kfifo,
i am merely succeeding.)

  what appears to be a bit of an oddity WRT kfifo:  since a kfifo is
defined with a fixed buffer size, it obviously enqueues and dequeues
in a circular fashion.  so, the code to add some data to a kfifo (from
kernel/kfifo.c):

=====
unsigned int kfifo_in(struct kfifo *fifo, const void *from,
                                unsigned int len)
{
        len = min(kfifo_avail(fifo), len);

        __kfifo_in_data(fifo, from, len, 0);
        __kfifo_add_in(fifo, len);
        return len;
}
=====

 fair enough -- that first routine adds the data itself, while the
second one correspondingly bumps up the pointer, which could
conceivably wrap around to follow the data, correct?  but from
include/linux.kfifo.h:

=====
static inline void __kfifo_add_in(struct kfifo *fifo,
                                unsigned int off)
{
        smp_wmb();
        fifo->in += off;
}
=====

  note that there is no attempt to check for wraparound -- the new
value of "fifo->in" could (theoretically) be off the end of the
kfifo's buffer.  to make a long story short, when one subsequently
tries to *dequeue* data, one eventually invokes:

=====
static inline void __kfifo_out_data(struct kfifo *fifo,
                void *to, unsigned int len, unsigned int off)
{
        unsigned int l;

        /*
         * Ensure that we sample the fifo->in index -before- we
         * start removing bytes from the kfifo.
         */

        smp_rmb();

        off = __kfifo_off(fifo, fifo->out + off);   <----- there
        ... snip...
=====

where __kfifo_off is defined as:

=====
static inline unsigned int __kfifo_off(struct kfifo *fifo, unsigned int off)
{
        return off & (fifo->size - 1);
}
=====

which is clearly what takes a given offset and *now* adjusts it if it
represents a wraparound.

  but that seems to suggest that, between the time data is enqueued
which represents a circular wraparound and the time that data is
dequeued, the value of fifo->in is temporarily rubbish -- it might
have a value that's off the end of the kfifo buffer, no?

  admittedly, the code seems to work in that it always takes the above
into account, but it would seem to make a mess of debugging, since if
you were printing out the contents of a kfifo, you could conceivably
read a value of fifo->in that's larger than the buffer size.

  am i reading this correctly?  should i care?

rday
--

========================================================================
Robert P. J. Day                               Waterloo, Ontario, CANADA

            Linux Consulting, Training and Kernel Pedantry.

Web page:                                          http://crashcourse.ca
Twitter:                                       http://twitter.com/rpjday
========================================================================
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/