Re: [RFC, 2.6] a simple FIFO implementation

[James R Bruce]

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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/