kfifo has temporarily invalid in pointer?

kfifo has temporarily invalid in pointer?

[Robert P. J. Day]

  (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
========================================================================

Re: kfifo has temporarily invalid in pointer?

[Daniel Baluta]

Hi Robert,

On Mon, Mar 15, 2010 at 4:58 PM, Robert P. J. Day <rpjday@crashcourse.ca> wrote:
>
>  (i am not trying to be annoyingly obsessive about the kernel kfifo,
> i am merely succeeding.)
:P
>  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:len = min(kfifo_avail(fifo), len);

Wrong :). If you notice len is truncated using:
len = min(kfifo_avail(fifo), len);

>
> =====
> static inline void __kfifo_add_in(struct kfifo *fifo,
>                                unsigned int off)
> {
>        smp_wmb();
>        fifo->in += off;
> }
So,  fifo->in + min(kfifo_avail(fifo), len) < fifo->size, every time.

thanks,
Daniel.

Re: kfifo has temporarily invalid in pointer?

[Robert P. J. Day]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1855 bytes --]

On Mon, 15 Mar 2010, Daniel Baluta wrote:

> Hi Robert,
>
> On Mon, Mar 15, 2010 at 4:58 PM, Robert P. J. Day <rpjday@crashcourse.ca> wrote:
> >
> >  (i am not trying to be annoyingly obsessive about the kernel kfifo,
> > i am merely succeeding.)
> :P
> >  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:len = min(kfifo_avail(fifo), len);
>
> Wrong :). If you notice len is truncated using:
> len = min(kfifo_avail(fifo), len);

  kfifo_avail() is defined as returning the number of available bytes
left in the buffer ready to accept incoming data, even if that
incorporates wraparound.  that is not relevant to the point i was
making.

rday
--

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

            Linux Consulting, Training and Kernel Pedantry.

Web page:                                          http://crashcourse.ca
Twitter:                                       http://twitter.com/rpjday
========================================================================