lkml.org 
[lkml]   [2004]   [Sep]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC, 2.6] a simple FIFO implementation

On Thu, 16 Sep 2004, Andrew Morton wrote:
> My point is that there is no need to store the "number of bytes currently
> in the buffer", because that is always equal to `head - tail' if you allow
> those indices to freely wrap.
>
> All the struct needs is `head', `tail' and `number_of_bytes_at_buf', all
> unsigned.
>
> add(char c)
> {
> p->buf[p->head++ % p->number_of_bytes_at_buf] = c;
> }
>
> get()
> {
> return p->buf[p->tail++ % p->number_of_bytes_at_buf];
> }

The "just let it wrap" approach will only work if number_of_bytes_at_buf
is a power of two. If it isn't, then the FIFO will skip back to zero at
the wrong place after correctly storing 2^32 bytes. I'll explain:

S = size of storage buffer
N = 1<<32 (or whatever size int is on a platform)

The hidden assumption is:
a % S == (a % N) % S

But this is only true if:
N % S == 0

Or in other words, that S is a power of two less than N.

> free_space()
> {
> return p->head - p->tail;
> }

This will of course always work fine, since S is not involved.

> pretty simple...

"Things should be made as simple as possible -- but no simpler."
- Albert Einstein

IMHO restricting it to powers of two may not be so bad, and allows us to
get away with using faster bitwise ANDs instead of modulus operations.
Most FIFOs are probably power-of-two sizes anyway. However, if the
interface exports using any size, it'd better work that way, and not fail
after working correctly for the first 4GB.

This is a perfect example of why we need a common, well tested
implementation that all the drivers, etc. can use. Keep up the excellent
work :)

- Jim Bruce
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:06    [W:0.482 / U:0.356 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site