kfifo: possible weird violation of what should be invariant

kfifo: possible weird violation of what should be invariant

[Robert P. J. Day]

  since i may not have explained myself clearly the first time, let me
try again.  based on my perusal of the current implementation of the
kfifo code, it seems that there's a really strange and potentially
confusing violation of a property that really should be invariant, so
you can tell me if i'm out to lunch here.

  the actual definition of the structure kind of gives it away:

struct kfifo {
        unsigned char *buffer;  /* the buffer holding the data */
        unsigned int size;      /* the size of the allocated buffer */
        unsigned int in;        /* data is added at offset (in % size) */
        unsigned int out;       /* data is extracted from off. (out % size) */
};

  note the comments, which explain that the two offsets into the
allocated buffer need not actually lie in that range.  they could
potentially be larger, but must always be checked modulo the "size"
value.  why those two values aren't consistently checked and forced to
exist within the range [0 - buffer size-1] isn't at all clear, but it
seems that allowing them to, even temporarily, be outside the range
might make debugging more entertaining than it has to be.

  as a concrete example, consider once again the basic kfifo_in()
routine, which enqueues data to the kfifo:

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

  the above makes perfect sense -- add the passed data to the current
offset of zero (relative to the "in" pointer), then immediately bump
up the "in" pointer to reflect the new available offset for enqueueing
more data.

  as i read it, the __kfifo_in_data() routine properly checks if you
need to wraparound, and will enqueue the data properly, taking the
possible wraparound into account.  but the subsequent __kfifo_add_in()
routine ignores possible wraparound entirely:

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

  it simply adds the size of the enqueued data to the current fifo
"in" pointer, even if that forces it to exceed the size of the kfifo
buffer. in short, the new value of fifo->in is clearly nonsensical, is
it not?

  admittedly, that doesn't last long as the next time something is
enqueued or dequeued, there's a reference to __kfifo_off(), which
recalculates offset thusly:

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

  clearly, that performs the necessary module operation to reset
any offset back within the valid range but, in the meantime, for
however long it was between operations, the value of fifo->in is, as i
said, nonsensical.

  sure, the code seems to work, but allowing the internal values of a
kfifo to contain invalid values on a regular basis would seem to make
a mess of, say, tracing or debugging.  making sure that offset values
actually lie within their valid range would seem to be one of those
ASSERT() things that should always be true, should it not?  is there a
reason the design is like this?

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: possible weird violation of what should be invariant

[Roland Dreier]

 >   sure, the code seems to work, but allowing the internal values of a
 > kfifo to contain invalid values on a regular basis would seem to make
 > a mess of, say, tracing or debugging.  making sure that offset values
 > actually lie within their valid range would seem to be one of those
 > ASSERT() things that should always be true, should it not?  is there a
 > reason the design is like this?

Actually I believe having the values be free-running without clamping
them makes the code much simpler -- the reason being that you preserve
the invariant of "in" always being ahead of "out".  If you reduce the
pointers modulo the size, then you end up having a lot of code that has
two cases: one to handle "in > out", and one to handle "in < out because
in has wrapped and out hasn't yet".

 - R.
-- 
Roland Dreier  <rolandd@cisco.com>
For corporate legal information go to:
http://www.cisco.com/web/about/doing_business/legal/cri/index.html

Re: kfifo: possible weird violation of what should be invariant

[Robert P. J. Day]

On Tue, 16 Mar 2010, Roland Dreier wrote:

>  >   sure, the code seems to work, but allowing the internal values of a
>  > kfifo to contain invalid values on a regular basis would seem to make
>  > a mess of, say, tracing or debugging.  making sure that offset values
>  > actually lie within their valid range would seem to be one of those
>  > ASSERT() things that should always be true, should it not?  is there a
>  > reason the design is like this?
>
> Actually I believe having the values be free-running without
> clamping them makes the code much simpler -- the reason being that
> you preserve the invariant of "in" always being ahead of "out".  If
> you reduce the pointers modulo the size, then you end up having a
> lot of code that has two cases: one to handle "in > out", and one to
> handle "in < out because in has wrapped and out hasn't yet".

  yes, i see your point.  so, as i read it, the internal kfifo "in"
and "out" pointers are *never* actually normalized modulo the buffer
size, which means that, at any time, you can easily check how much
*total* data has gone through the kfifo.  potentially useful.  perhaps
there should be a comment or note to that effect stuffed in there
somewhere as some kernel programmers might find that handy, who knows?

rday
--

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

            Linux Consulting, Training and Kernel Pedantry.

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