Skip to contentSkip to conversation

kfifo: possible weird violation of what should be invariant

DISCUSSION Robert P. J. Day 2 participants 3 messages Mar 15, 2010 – Mar 17, 2010

lore
Share & tools
lore
#0 lore raw

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

========================================================================

#1 lore raw
Quoted 6 lines

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.

Signature · 3 lines
Roland Dreier  <[email protected]>
For corporate legal information go to:
http://www.cisco.com/web/about/doing_business/legal/cri/index.html
#2 lore raw
Quoted 7 lines · Roland Dreier
Quoted 6 lines

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?

Quoted 6 lines

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

========================================================================