Re: [RFC, 2.6] a simple FIFO implementation

[Buddy Lucas <buddy.lucas@gmail.com>]

On Thu, 16 Sep 2004 12:45:36 +0200, Stelian Pop <stelian@popies.net> wrote:
> On Thu, Sep 16, 2004 at 12:04:38AM -0700, Andrew Morton wrote:
> 
> > Stelian Pop <stelian@popies.net> wrote:
> > >
> > > > Implementation-wise, the head and tail indices should *not* be constrained
> > >  > to be less than the size of the buffer.  They should be allowed to wrap all
> > >  > the way back to zero.  This allows you to distinguish between the
> > >  > completely-empty and completely-full states while using 100% of the storage.
> [...]
> 
> Here is the updated patch.
>
[ .. ] 
>
> +unsigned int __kfifo_put(struct kfifo *fifo,
> +                        unsigned char *buffer, unsigned int len)
> +{
> +       unsigned int total, remaining, l;
> +
> +       total = remaining = min(len, fifo->size - fifo->tail + fifo->head);

I could be mistaken (long day at the office ;-) but doesn't this fail after 
wrapping?

> +       while (remaining > 0) {
> +               l = min(remaining, fifo->size - (fifo->tail % fifo->size));
> +               memcpy(fifo->buffer + (fifo->tail % fifo->size), buffer, l);
> +               fifo->tail += l;
> +               buffer += l;
> +               remaining -= l;
> +       }
> +
> +       return total;
> +}
> +EXPORT_SYMBOL(__kfifo_put);
> +
> +/*
> + * kfifo_get - gets some data from the FIFO, no locking version
> + * @fifo: the fifo to be used.
> + * @buffer: where the data must be copied.
> + * @len: the size of the destination buffer.
> + *
> + * This function copies at most 'len' bytes from the FIFO into the
> + * 'buffer' and returns the number of copied bytes.
> + */
> +unsigned int __kfifo_get(struct kfifo *fifo,
> +                        unsigned char *buffer, unsigned int len)
> +{
> +       unsigned int total, remaining, l;
> +
> +       total = remaining = min(len, fifo->tail - fifo->head);

Same here?

> +       while (remaining > 0) {
> +               l = min(remaining, fifo->size - (fifo->head % fifo->size));
> +               memcpy(buffer, fifo->buffer + (fifo->head % fifo->size), l);
> +               fifo->head += l;
> +               buffer += l;
> +               remaining -= l;
> +       }
> +
> +       return total;
> +}
> +EXPORT_SYMBOL(__kfifo_get);
> +
> +/*
> + * kfifo_len - returns the number of bytes available in the FIFO, no locking version
> + * @fifo: the fifo to be used.
> + */
> +unsigned int __kfifo_len(struct kfifo *fifo)
> +{
> +       return fifo->tail - fifo->head;
> +}
> +EXPORT_SYMBOL(__kfifo_len);
> --- linux-2.6/kernel/Makefile.orig      2004-09-16 12:27:29.012343608 +0200
> +++ linux-2.6/kernel/Makefile   2004-09-16 11:58:26.000000000 +0200
> @@ -7,7 +7,7 @@
>            sysctl.o capability.o ptrace.o timer.o user.o \
>            signal.o sys.o kmod.o workqueue.o pid.o \
>            rcupdate.o intermodule.o extable.o params.o posix-timers.o \
> -           kthread.o
> +           kthread.o kfifo.o
> 
> obj-$(CONFIG_FUTEX) += futex.o
> obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
> 
> --
> 
> 
> Stelian Pop <stelian@popies.net>
> -
> 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/
>