[RFC 0/2] new kfifo API

[RFC 0/2] new kfifo API

[Stefani Seibold]

This is a proposal of a new generic kernel FIFO implementation.

The current kernel fifo API is not very widely used, because it has to many
constrains. Only 13 files in the current 2.6.30 used it. FIFO's are
like list are a very basic thing and a kfifo API which handles the most use
case would save a lot of time and memory resources.

I think there are the following reasons why kfifo is not in use.

- There is a need of a spinlock despite you need it or not
- A fifo can only allocated dynamically
- There is no support for data records inside a fifo
- The FIFO size can only a power of two
- The API is to tall, some important functions are missing

So i decided to extend the kfifo in a more generic way without blowing up
the API to much. This was my design goals:

- Generic usage: For kernel internal use or device driver
- Provide an API for the most use case
- Preserve memory resource
- Linux style habit: DECLARE_KFIFO, DEFINE_KFIFO and INIT_KFIFO Macros
- Slim API: The whole API provides 13 functions.
- Ability to handle variable length records. Three type of records are
  supported:
  - Records between 0-255 bytes, with a record size field of 1 bytes
  - Records between 0-65535 bytes, with a record size field of 2 bytes
  - Byte stream, which no record size field
  Inside a fifo this record types it is not a good idea to mix them together.
- Direct copy_to_user from the fifo and copy_from_user into the fifo.
- Single structure: The fifo structure contains the management variables and
  the buffer. No extra indirection is needed to access the fifo buffer.
- Lockless access: if only one reader and one writer is active on the fifo,
  which is the common use case, there is no additional locking necessary.
- Performance
- Easy to use

The API:
--------

struct kfifo *kfifo_alloc(unsigned long size, gfp_t gfp_mask)
 Dynamically allocates a new fifo and returns the address
 @size: the size of the internal buffer to be allocated.
 @gfp_mask: get_free_pages mask, passed to kmalloc()

void kfifo_free(struct kfifo *fifo)
 frees a dynamic allocated FIFO
 @fifo: the fifo to be freed.

void kfifo_reset(struct kfifo *fifo)
 removes the entire FIFO contents
 @fifo: the fifo to be emptied.

unsigned long kfifo_used(struct kfifo *fifo)
 * kfifo_used - returns the number of bytes currently used in the FIFO
 * @fifo: the fifo to be used.

unsigned long kfifo_size(struct kfifo *fifo)
 returns the size of the fifo in bytes
 @fifo: the fifo to be used.

kfifo_empty(struct kfifo *fifo)
 returns true if the fifo is empty
 @fifo: the fifo to be used.

kfifo_is_full(struct kfifo *fifo)
 returns true if the fifo is full
 @fifo: the fifo to be used.

unsigned long kfifo_avail(struct kfifo *fifo)
 returns the number of bytes available in the FIFO
 @fifo: the fifo to be used.

unsigned long kfifo_put(struct kfifo *fifo,
	unsigned char *from, unsigned long n, unsigned long recsize,
	unsigned long flags, unsigned long *total)
 puts some data into the FIFO without locking

 This function copies at most @n bytes from the @from into
 the FIFO depending @flags argument, and returns the number of
 bytes which cannot be copied.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.

 @fifo: the fifo to be used.
 @from: the data to be added.
 @n: the length of the data to be added.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL

unsigned long kfifo_get(struct kfifo *fifo,
	unsigned char *to, unsigned long n, unsigned long recsize,
	unsigned long flags, unsigned long *total)
 Gets some data from the FIFO without locking.

 This function copies at most @n bytes from the @to into the FIFO depending
 on @flags argument, and returns the number of bytes which cannot be copied.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.

 @fifo: the fifo to be used.
 @to: where the data must be copied.
 @n: the size of the destination buffer.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL

unsigned long kfifo_from_user(struct kfifo *fifo,
	const void __user *from, unsigned long n, unsigned long recsize,
	unsigned long flags, unsigned long *total)
 Puts some data from user space into the FIFO.

 This function copies at most @n bytes from the @from into the FIFO depending
 on @flags argument, and returns the number of bytes which cannot be copied.

 Note that with only one concurrent reader and one concurrent
 writer, you don't need extra locking to use these functions.

 @fifo: the fifo to be used.
 @from: pointer to the data to be added.
 @n: the length of the data to be added.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL

unsigned long kfifo_to_user(struct kfifo *fifo,
		void __user *to, unsigned long n, unsigned long recsize,
		unsigned long flags, unsigned long *total)
 Gets data from the FIFO and write it to user space.

 @fifo: the fifo to be used.
 @to: where the data must be copied.
 @n: the size of the destination buffer.
 @recsize: size of record field
 @flags: KFIFO_F_NOTRIM = do not cut off if the record is to long
 @total: pointer where the total number of copied bytes should stored or NULL

 This function copies at most @n bytes from the FIFO into the @to depending
 on @flags argument.
 In case of an error, the function returns the number of bytes which cannot
 be copied.
 - If the flags KFIFO_F_NOTRIM is set and the returned value is greater than
   the n parameter this means that there is not enough space to copy the
   whole record
 - Otherwise this means that the copy_to_user() functions has failed.

 Note that with only one concurrent reader and one concurrent writer, you don't
 need extra locking to use these functions.

unsigned long kfifo_peek(struct kfifo *fifo, unsigned long recsize)
 Gets the size of the next FIFO record data.

 This function returns the size of the next FIFO record in number of bytes
 @fifo: the fifo to be used.
 @recsize: size of record field


Macros defined for kernel FIFO:
-------------------------------

KFIFO_F_NOTRIM 
	flags argumet: do not cut of the record

DECLARE_KFIFO(name, size)
	declare a kernel fifo (can be used inside a struct declaration)

DEFINE_KFIFO(name, size)
	define a kernel fifo

INIT_KFIFO(name)
	initialize a FIFO


One thing is that the new API is not compatible with the old one. I had
a look at the current user of the old kfifo API and it is easy to adapt it to
the new API. These are the files which use currently the kfifo API:

/usr/src/linux/./drivers/char/nozomi.c
/usr/src/linux/./drivers/char/sonypi.c
/usr/src/linux/./drivers/infiniband/hw/cxgb3/cxio_resource.c
/usr/src/linux/./drivers/media/video/meye.c
/usr/src/linux/./drivers/net/wireless/libertas/main.c
/usr/src/linux/./drivers/platform/x86/fujitsu-laptop.c
/usr/src/linux/./drivers/platform/x86/sony-laptop.c
/usr/src/linux/./drivers/scsi/libiscsi.c
/usr/src/linux/./drivers/scsi/libiscsi_tcp.c
/usr/src/linux/./drivers/scsi/libsrp.c
/usr/src/linux/./drivers/usb/host/fhci.h
/usr/src/linux/./net/dccp/probe.c

I will do this job if there is a tendency for substitute the old API. So i ask
for comments....

Greetings,
Stefani

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

On Monday 03 August 2009, Stefani Seibold wrote:
> This is a proposal of a new generic kernel FIFO implementation.
> 
> The current kernel fifo API is not very widely used, because it has to many
> constrains. Only 13 files in the current 2.6.30 used it. FIFO's are
> like list are a very basic thing and a kfifo API which handles the most use
> case would save a lot of time and memory resources.
> 
> I think there are the following reasons why kfifo is not in use.
> 
> - There is a need of a spinlock despite you need it or not
> - A fifo can only allocated dynamically
> - There is no support for data records inside a fifo
> - The FIFO size can only a power of two
> - The API is to tall, some important functions are missing

My guess is that more importantly

- few people so far needed the functionality.

All of the existing users are in relatively obscure device drivers,
a total of 16 committers have touched code using it since 2.6.12
and almost all the changes were in iSCSI (cc:ing maintainer).

> So i decided to extend the kfifo in a more generic way without blowing up
> the API to much. This was my design goals:
> 
> - Generic usage: For kernel internal use or device driver
> - Provide an API for the most use case
> - Preserve memory resource
> - Linux style habit: DECLARE_KFIFO, DEFINE_KFIFO and INIT_KFIFO Macros
> - Slim API: The whole API provides 13 functions.
> - Ability to handle variable length records. Three type of records are
>   supported:
>   - Records between 0-255 bytes, with a record size field of 1 bytes
>   - Records between 0-65535 bytes, with a record size field of 2 bytes
>   - Byte stream, which no record size field
>   Inside a fifo this record types it is not a good idea to mix them together.
> - Direct copy_to_user from the fifo and copy_from_user into the fifo.
> - Single structure: The fifo structure contains the management variables and
>   the buffer. No extra indirection is needed to access the fifo buffer.
> - Lockless access: if only one reader and one writer is active on the fifo,
>   which is the common use case, there is no additional locking necessary.
> - Performance
> - Easy to use

This sounds all nice, and your code looks clean and usable, but really,
what's your point?

If you have a new driver that will use all the new features, please
just tell us, that would make your point much clearer. Also, if
you can quantify an advantage (xxxx bytes code size reduce, yy%
performance improvement on Y benchmark) that would be really
helpful.

> One thing is that the new API is not compatible with the old one. I had
> a look at the current user of the old kfifo API and it is easy to adapt it to
> the new API. These are the files which use currently the kfifo API:
> 
> /usr/src/linux/./drivers/char/nozomi.c
> /usr/src/linux/./drivers/char/sonypi.c
> /usr/src/linux/./drivers/infiniband/hw/cxgb3/cxio_resource.c
> /usr/src/linux/./drivers/media/video/meye.c
> /usr/src/linux/./drivers/net/wireless/libertas/main.c
> /usr/src/linux/./drivers/platform/x86/fujitsu-laptop.c
> /usr/src/linux/./drivers/platform/x86/sony-laptop.c
> /usr/src/linux/./drivers/scsi/libiscsi.c
> /usr/src/linux/./drivers/scsi/libiscsi_tcp.c
> /usr/src/linux/./drivers/scsi/libsrp.c
> /usr/src/linux/./drivers/usb/host/fhci.h
> /usr/src/linux/./net/dccp/probe.c
> 
> I will do this job if there is a tendency for substitute the old API. So i ask
> for comments....

I don't think we should risk introducing regressions if the only possible
benefit is to make an interface easy to use that almost nobody uses.
We have also recently gained the include/linux/ring_buffer.h API which
appears to be a superset of the kfifo API.

	Arnd <><

Re: [RFC 0/2] new kfifo API

[Stefani Seibold]

Am Montag, den 03.08.2009, 16:42 +0200 schrieb Arnd Bergmann:
> On Monday 03 August 2009, Stefani Seibold wrote:
> > This is a proposal of a new generic kernel FIFO implementation.
> > 
> > The current kernel fifo API is not very widely used, because it has to many
> > constrains. Only 13 files in the current 2.6.30 used it. FIFO's are
> > like list are a very basic thing and a kfifo API which handles the most use
> > case would save a lot of time and memory resources.
> > 
> > I think there are the following reasons why kfifo is not in use.
> > 
> > - There is a need of a spinlock despite you need it or not
> > - A fifo can only allocated dynamically
> > - There is no support for data records inside a fifo
> > - The FIFO size can only a power of two
> > - The API is to tall, some important functions are missing
> 
> My guess is that more importantly
> 
> - few people so far needed the functionality.
> 

This is not true, that is only your view. Don't speak for other people.
A lot of device driver developer has its own implement of a fifo. I have
written a lot of device drivers for embedded system and i always missed
a clean designed and implemented fifo API subsystem.
 
> All of the existing users are in relatively obscure device drivers,
> a total of 16 committers have touched code using it since 2.6.12
> and almost all the changes were in iSCSI (cc:ing maintainer).
> 
> > So i decided to extend the kfifo in a more generic way without blowing up
> > the API to much. This was my design goals:
> > 
> > - Generic usage: For kernel internal use or device driver
> > - Provide an API for the most use case
> > - Preserve memory resource
> > - Linux style habit: DECLARE_KFIFO, DEFINE_KFIFO and INIT_KFIFO Macros
> > - Slim API: The whole API provides 13 functions.
> > - Ability to handle variable length records. Three type of records are
> >   supported:
> >   - Records between 0-255 bytes, with a record size field of 1 bytes
> >   - Records between 0-65535 bytes, with a record size field of 2 bytes
> >   - Byte stream, which no record size field
> >   Inside a fifo this record types it is not a good idea to mix them together.
> > - Direct copy_to_user from the fifo and copy_from_user into the fifo.
> > - Single structure: The fifo structure contains the management variables and
> >   the buffer. No extra indirection is needed to access the fifo buffer.
> > - Lockless access: if only one reader and one writer is active on the fifo,
> >   which is the common use case, there is no additional locking necessary.
> > - Performance
> > - Easy to use
> 
> This sounds all nice, and your code looks clean and usable, but really,
> what's your point?
> 
> If you have a new driver that will use all the new features, please
> just tell us, that would make your point much clearer. Also, if
> you can quantify an advantage (xxxx bytes code size reduce, yy%
> performance improvement on Y benchmark) that would be really
> helpful.
> 

Yes, i have some drivers where i use a former version of the kfifo API.
But the real advantage is not benchmarking.

First if we have a useable kfifo API i think other developer will use
it. And this will save memory.

Second: The feature to store variable length records in the fifo is IMHO
very nice. It save memory and give you a very flexible method to store
datagrams. Especially many usb devices which works with variable data
packages length. So the new API gives a very easy way to queue this kind
of datagrams.

Third: The old API did not have a kfifo_to_user oder a kfifo_from_user
functionality, so everybody wo need to store userspace data must write
it own version of this.

Fourth: We don't discus about a havy API change, it is more subtle. And
it doesn't blow up the kernel, okay, a little little bit. But i am sure
that this well be gained back, if/when developer use this new API.    

> > One thing is that the new API is not compatible with the old one. I had
> > a look at the current user of the old kfifo API and it is easy to adapt it to
> > the new API. These are the files which use currently the kfifo API:
> > 
> > /usr/src/linux/./drivers/char/nozomi.c
> > /usr/src/linux/./drivers/char/sonypi.c
> > /usr/src/linux/./drivers/infiniband/hw/cxgb3/cxio_resource.c
> > /usr/src/linux/./drivers/media/video/meye.c
> > /usr/src/linux/./drivers/net/wireless/libertas/main.c
> > /usr/src/linux/./drivers/platform/x86/fujitsu-laptop.c
> > /usr/src/linux/./drivers/platform/x86/sony-laptop.c
> > /usr/src/linux/./drivers/scsi/libiscsi.c
> > /usr/src/linux/./drivers/scsi/libiscsi_tcp.c
> > /usr/src/linux/./drivers/scsi/libsrp.c
> > /usr/src/linux/./drivers/usb/host/fhci.h
> > /usr/src/linux/./net/dccp/probe.c
> > 
> > I will do this job if there is a tendency for substitute the old API. So i ask
> > for comments....
> 
> I don't think we should risk introducing regressions if the only possible
> benefit is to make an interface easy to use that almost nobody uses.

I think this is a typical killer argument. Above you wrote the kfifo API
is used only by some obscure device driver. Now you say it is to risky
to change the API. The code is straightforward. If you don't use the new
functionality, especially the variable records, there is only a minor
difference between the old and the new API.
 
> We have also recently gained the include/linux/ring_buffer.h API which
> appears to be a superset of the kfifo API.
> 

The ring_buffer API is in my opinion not the right thing for device
drivers. I think the design goal for this was deep in kernel use.

> 	Arnd <><

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

On Monday 03 August 2009, Stefani Seibold wrote:
> Am Montag, den 03.08.2009, 16:42 +0200 schrieb Arnd Bergmann:
> > My guess is that more importantly
> > 
> > - few people so far needed the functionality.
> 
> This is not true, that is only your view. Don't speak for other people.
> A lot of device driver developer has its own implement of a fifo. I have
> written a lot of device drivers for embedded system and i always missed
> a clean designed and implemented fifo API subsystem.

As I said, I was only guessing from the only evidence we both had, which
is the current use in the kernel. Your extrapolation was that it did
not get used much because of the quality of the existing API, my
extrapolation was that there is no need for it (at least I was
never looking for it in any of my drivers).

> > This sounds all nice, and your code looks clean and usable, but really,
> > what's your point?
> > 
> > If you have a new driver that will use all the new features, please
> > just tell us, that would make your point much clearer. Also, if
> > you can quantify an advantage (xxxx bytes code size reduce, yy%
> > performance improvement on Y benchmark) that would be really
> > helpful.
> > 
> 
> Yes, i have some drivers where i use a former version of the kfifo API.
> But the real advantage is not benchmarking.
>
> First if we have a useable kfifo API i think other developer will use
> it. And this will save memory.

Being able to simplify code is obviously good, but the normal
approach of doing it is to make it obvious in what ways. Exchanging
a whole API at once makes it unobvious what changes you do for which
purpose. 

If you split out every logical change into a separate patch,
you can easily show how to subsequently make use of that.
That also avoids the problem of adding functions that end up
being unused.

Submitting patches would also make it easier to review than
a rewrite.

> Third: The old API did not have a kfifo_to_user oder a kfifo_from_user
> functionality, so everybody wo need to store userspace data must write
> it own version of this.

That sounds like a feature that can be easily separated from the
incompatible API changes.

> Fourth: We don't discus about a havy API change, it is more subtle. And
> it doesn't blow up the kernel, okay, a little little bit. But i am sure
> that this well be gained back, if/when developer use this new API.    

Can you separate the incompatible API changes from the compatible
extensions?

	Arnd <><

Re: [RFC 0/2] new kfifo API

[Stefani Seibold]

Am Montag, den 03.08.2009, 20:23 +0200 schrieb Arnd Bergmann:
> On Monday 03 August 2009, Stefani Seibold wrote:
> > Am Montag, den 03.08.2009, 16:42 +0200 schrieb Arnd Bergmann:
> > > My guess is that more importantly
> > > 
> > > - few people so far needed the functionality.
> > 
> > This is not true, that is only your view. Don't speak for other people.
> > A lot of device driver developer has its own implement of a fifo. I have
> > written a lot of device drivers for embedded system and i always missed
> > a clean designed and implemented fifo API subsystem.
> 
> As I said, I was only guessing from the only evidence we both had, which
> is the current use in the kernel. Your extrapolation was that it did
> not get used much because of the quality of the existing API, my
> extrapolation was that there is no need for it (at least I was
> never looking for it in any of my drivers).
> 

Maybe..... 

> > > This sounds all nice, and your code looks clean and usable, but really,
> > > what's your point?
> > > 
> > > If you have a new driver that will use all the new features, please
> > > just tell us, that would make your point much clearer. Also, if
> > > you can quantify an advantage (xxxx bytes code size reduce, yy%
> > > performance improvement on Y benchmark) that would be really
> > > helpful.
> > > 
> > 
> > Yes, i have some drivers where i use a former version of the kfifo API.
> > But the real advantage is not benchmarking.
> >
> > First if we have a useable kfifo API i think other developer will use
> > it. And this will save memory.
> 
> Being able to simplify code is obviously good, but the normal
> approach of doing it is to make it obvious in what ways. Exchanging
> a whole API at once makes it unobvious what changes you do for which
> purpose. 
> 

It is not a complete change of the API. There are two main things which
are different:

The kfifo_get and kfifo_put functions are extended by two new
parameters: flag and total. Setting both to there will result in the old
behavior.

And i remove the spinlock which is logical not a part of the fifo and
should be handled outside if necessary.

   
> If you split out every logical change into a separate patch,
> you can easily show how to subsequently make use of that.
> That also avoids the problem of adding functions that end up
> being unused.
> 

> Submitting patches would also make it easier to review than
> a rewrite.
> 

Agree, but the code is very tiny and the functionality depends on the
whole. Since many of the functions are inlines, which will not generate
any code until there are used. So the kernel will not be bloated.

> > Third: The old API did not have a kfifo_to_user oder a kfifo_from_user
> > functionality, so everybody wo need to store userspace data must write
> > it own version of this.
> 
> That sounds like a feature that can be easily separated from the
> incompatible API changes.
> 
> > Fourth: We don't discus about a havy API change, it is more subtle. And
> > it doesn't blow up the kernel, okay, a little little bit. But i am sure
> > that this well be gained back, if/when developer use this new API.    
> 
> Can you separate the incompatible API changes from the compatible
> extensions?
> 

No, thats not makes not real sense. If i do this i have exactly the old
API. Again, the API is not really incompatible, the change is from the
view of the old API very tiny.
 
> 	Arnd <><

Stefani

Re: [RFC 0/2] new kfifo API

[Mike Christie]

On 08/03/2009 09:42 AM, Arnd Bergmann wrote:
> On Monday 03 August 2009, Stefani Seibold wrote:
>> This is a proposal of a new generic kernel FIFO implementation.
>>
>> The current kernel fifo API is not very widely used, because it has to many
>> constrains. Only 13 files in the current 2.6.30 used it. FIFO's are
>> like list are a very basic thing and a kfifo API which handles the most use
>> case would save a lot of time and memory resources.
>>
>> I think there are the following reasons why kfifo is not in use.
>>
>> - There is a need of a spinlock despite you need it or not
>> - A fifo can only allocated dynamically
>> - There is no support for data records inside a fifo
>> - The FIFO size can only a power of two


For iscsi, the only thing we have not liked with the current code is 
having to have the fifo a power of 2. It has not been that big a deal 
though.

Re: [RFC 0/2] new kfifo API

[Andi Kleen]

Stefani Seibold <stefani@seibold.net> writes:
>   the buffer. No extra indirection is needed to access the fifo buffer.
> - Lockless access: if only one reader and one writer is active on the fifo,
>   which is the common use case, there is no additional locking necessary.

Would it also be NMI safe?  I've been looking at a new log buffer
for MCE/NMI. One option was the fifo in ftrace, but it seems
so big that it would blow up the machine check code considerably.

There was also an own new fifo that Ying Huang implemented,
but that one wasn't very popular.

This might be indeed an alternative. Requirement is NMI-safeness.

> The API:
> --------
>
> struct kfifo *kfifo_alloc(unsigned long size, gfp_t gfp_mask)
>  Dynamically allocates a new fifo and returns the address
>  @size: the size of the internal buffer to be allocated.
>  @gfp_mask: get_free_pages mask, passed to kmalloc()

For the MCE use case this would need to be able to optionally use
bootmem because the first initialization happens too early.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

On Monday 03 August 2009, Andi Kleen wrote:
> > struct kfifo *kfifo_alloc(unsigned long size, gfp_t gfp_mask)
> >  Dynamically allocates a new fifo and returns the address
> >  @size: the size of the internal buffer to be allocated.
> >  @gfp_mask: get_free_pages mask, passed to kmalloc()
> 
> For the MCE use case this would need to be able to optionally use
> bootmem because the first initialization happens too early.

The existing API has a kfifo_init for that purpose, so you can
pass a preallocated (bootmem, static, coherent, aligned, ...) buffer
into the FIFO.

That might be nice to keep, by leaving the 'buffer' as pointer
in struct kfifo, which could still point to a buffer that is
allocated together with the structu kfifo.

	Arnd <><

Re: [RFC 0/2] new kfifo API

[Stefani Seibold]

Am Montag, den 03.08.2009, 20:27 +0200 schrieb Andi Kleen:
> Stefani Seibold <stefani@seibold.net> writes:
> >   the buffer. No extra indirection is needed to access the fifo buffer.
> > - Lockless access: if only one reader and one writer is active on the fifo,
> >   which is the common use case, there is no additional locking necessary.
> 
> Would it also be NMI safe?  I've been looking at a new log buffer
> for MCE/NMI. One option was the fifo in ftrace, but it seems
> so big that it would blow up the machine check code considerably.
> 

Yes, it is. If you have only one reader and one writer there is no
locking necessary.

> There was also an own new fifo that Ying Huang implemented,
> but that one wasn't very popular.
> 
> This might be indeed an alternative. Requirement is NMI-safeness.
> 
> > The API:
> > --------
> >
> > struct kfifo *kfifo_alloc(unsigned long size, gfp_t gfp_mask)
> >  Dynamically allocates a new fifo and returns the address
> >  @size: the size of the internal buffer to be allocated.
> >  @gfp_mask: get_free_pages mask, passed to kmalloc()
> 
> For the MCE use case this would need to be able to optionally use
> bootmem because the first initialization happens too early.
> 

You can use a global variable for your fifo if you like. Or you can
greate a fifo inside a bootmem object. Which this API you have the
freedom of choice ;-)

> -Andi
> 

Stefani

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

Going through your list again:

On Monday 03 August 2009, Stefani Seibold wrote:
> - Generic usage: For kernel internal use or device driver

no change here, right?

> - Linux style habit: DECLARE_KFIFO, DEFINE_KFIFO and INIT_KFIFO Macros

DEFINE_KFIFO looks useful, but I probably wouldn't expose
the other macros, so you could define them as __KFIFO_* or
integrate them into a larger DEFINE_KFIFO.

> - Ability to handle variable length records. Three type of records are
>   supported:
>   - Records between 0-255 bytes, with a record size field of 1 bytes
>   - Records between 0-65535 bytes, with a record size field of 2 bytes
>   - Byte stream, which no record size field
>   Inside a fifo this record types it is not a good idea to mix them together.

Not sure if having both 1 and 2 byte record lengths really helps.
If you want to avoid mixing the two, maybe just leave the existing
API for byte streams in a compatible, and provide extra functions
for records with a definite length.

> - Direct copy_to_user from the fifo and copy_from_user into the fifo.

Sounds useful, as mentioned.

> - Single structure: The fifo structure contains the management variables and
>   the buffer. No extra indirection is needed to access the fifo buffer.

I see two problems here:

1. you can no longer use preallocated buffers, which limits the possible
users to those that are unrestricted to the type of allocation.
2. The size of the buffer is no longer power-of-two. In fact, it's guaranteed
to be non-power-of-two because kmalloc gives you a power-of-two allocation
but now you also put the struct kfifo in there.

Users that need a power-of-two buffer (the common case) now waste almost
50% of the space.

The requirement for power-of-two also meant a much faster __kfifo_off
function on certain embedded platforms that don't have an integer division
instruction in hardware.

> - Lockless access: if only one reader and one writer is active on the fifo,
>   which is the common use case, there is no additional locking necessary.

The existing API already provides this, you can simply call __kfifo_put()
and __kfifo_get() directly, rather than their wrappers, which are just
helpers to make the code more robust. Half the existing users do that
already.

	Arnd <><

Re: [RFC 0/2] new kfifo API

[Stefani Seibold]

Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
> Going through your list again:
> 
> On Monday 03 August 2009, Stefani Seibold wrote:
> > - Generic usage: For kernel internal use or device driver
> 
> no change here, right?
> 
> > - Linux style habit: DECLARE_KFIFO, DEFINE_KFIFO and INIT_KFIFO Macros

> DEFINE_KFIFO looks useful, but I probably wouldn't expose
> the other macros, so you could define them as __KFIFO_* or
> integrate them into a larger DEFINE_KFIFO.
> 

DECLARE_KFIFO looks for me more useful, because i can use it inside a
struct decalaration. And then i need INIT_KFIFO for initializing this.

BTW: DECLARE_...., DEFINE_..... and INIT_..... are linux style. Habe a
look at workqueue.h, wait.h, types.h, semaphore.h, rwsem-spinlock.h,
interrupt.h, completion.h, seqlock.h and so on....

> > - Ability to handle variable length records. Three type of records are
> >   supported:
> >   - Records between 0-255 bytes, with a record size field of 1 bytes
> >   - Records between 0-65535 bytes, with a record size field of 2 bytes
> >   - Byte stream, which no record size field
> >   Inside a fifo this record types it is not a good idea to mix them together.
> 
> Not sure if having both 1 and 2 byte record lengths really helps.
> If you want to avoid mixing the two, maybe just leave the existing
> API for byte streams in a compatible, and provide extra functions
> for records with a definite length.
> 

Streams are only a specially case of a very huge record. I personally
never needed records greater than 65535 byte. But i is easy to extend it
to support 3 and 4 byte records length field too. 

And mixing different record size fields makes no sense. If you know that
your records can be create than 255 bytes then use a 2 byte record
field. It is only the recsize parameter, which can be 0, 1 or 2.

0 means byte stream mode, 1 means records size from 0 to 255, and 2
means records size from 0 to 65535. 

It is designed like any other container or lists in the linux kernel.
The developer must know what she is doing ;-) Error checking wastes cpu
rescources.

> > - Direct copy_to_user from the fifo and copy_from_user into the fifo.
> 
> Sounds useful, as mentioned.
> 
> > - Single structure: The fifo structure contains the management variables and
> >   the buffer. No extra indirection is needed to access the fifo buffer.
> 
> I see two problems here:
> 
> 1. you can no longer use preallocated buffers, which limits the possible
> users to those that are unrestricted to the type of allocation.
> 2. The size of the buffer is no longer power-of-two. In fact, it's guaranteed
> to be non-power-of-two because kmalloc gives you a power-of-two allocation
> but now you also put the struct kfifo in there.
> 
> Users that need a power-of-two buffer (the common case) now waste almost
> 50% of the space.
> 

Okay, give me a thought about this....... yes you are right ;-( But what
is with vmalloc? 128 MB should be enough?

> The requirement for power-of-two also meant a much faster __kfifo_off
> function on certain embedded platforms that don't have an integer division
> instruction in hardware.
> 

Yes i know this argument, but since the day of the 6502 and Z80 i have
never seen this kind of CPU. Okay i forgot to mention the stupid ARM
CPU, but newer ARM cores have a hardware division support.

Stefani <\_,
         ^ ^

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

On Monday 03 August 2009, Stefani Seibold wrote:
> Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
> 
> DECLARE_KFIFO looks for me more useful, because i can use it inside a
> struct decalaration. And then i need INIT_KFIFO for initializing this.
> 
> BTW: DECLARE_...., DEFINE_..... and INIT_..... are linux style. Habe a
> look at workqueue.h, wait.h, types.h, semaphore.h, rwsem-spinlock.h,
> interrupt.h, completion.h, seqlock.h and so on....

Yes, you are right. I realized that myself after I sent out my
comments.

> > 1. you can no longer use preallocated buffers, which limits the possible
> > users to those that are unrestricted to the type of allocation.
> > 2. The size of the buffer is no longer power-of-two. In fact, it's guaranteed
> > to be non-power-of-two because kmalloc gives you a power-of-two allocation
> > but now you also put the struct kfifo in there.
> > 
> > Users that need a power-of-two buffer (the common case) now waste almost
> > 50% of the space.
> > 
> 
> Okay, give me a thought about this....... yes you are right ;-( But what
> is with vmalloc? 128 MB should be enough?

vmalloc also has performance problems on some architectures that can
access the linear mapping faster than paged memory and it is
rather wasteful if you have 64kb pages.

I don't think the total size matters, the 128 MB limit only exists
if you have a 32 bit CPU and 1GB or more of memory, which is hopefully
getting rarer and already causes other problems (highmem...).

kmalloc currently limits the kfifo size to something like 128kb (arch
specific), if you need more than that, you need alloc_pages(), which
is limited to a power-of-two amount of pages.

> > The requirement for power-of-two also meant a much faster __kfifo_off
> > function on certain embedded platforms that don't have an integer division
> > instruction in hardware.
>
> Yes i know this argument, but since the day of the 6502 and Z80 i have
> never seen this kind of CPU. Okay i forgot to mention the stupid ARM
> CPU, but newer ARM cores have a hardware division support.

I think this is actually more relevant than the vmalloc limit you mentioned,
demand for tiny processors will probably stay because of cost reasons.
Architectures that we support in Linux without integer divide include
arm, blackfin, h8300, ia64 (!), m68k, microblaze, sh and xtensa.

Your first version with the non-power-of-two buffers also had a bug
in the handling because it would not handle 32 bit integer overflows
correctly. To get those right, you need an extra branch every time you
add to the counter.

Your second version is ok in this regard because it uses the original
size logic.

	Arnd <><

Re: [RFC 0/2] new kfifo API

[Stefani Seibold]

Am Dienstag, den 04.08.2009, 14:24 +0200 schrieb Arnd Bergmann:
> On Monday 03 August 2009, Stefani Seibold wrote:
> > Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
> > 
> > DECLARE_KFIFO looks for me more useful, because i can use it inside a
> > struct decalaration. And then i need INIT_KFIFO for initializing this.
> > 
> > BTW: DECLARE_...., DEFINE_..... and INIT_..... are linux style. Habe a
> > look at workqueue.h, wait.h, types.h, semaphore.h, rwsem-spinlock.h,
> > interrupt.h, completion.h, seqlock.h and so on....
> 
> Yes, you are right. I realized that myself after I sent out my
> comments.
> 
> > > 1. you can no longer use preallocated buffers, which limits the possible
> > > users to those that are unrestricted to the type of allocation.
> > > 2. The size of the buffer is no longer power-of-two. In fact, it's guaranteed
> > > to be non-power-of-two because kmalloc gives you a power-of-two allocation
> > > but now you also put the struct kfifo in there.
> > > 
> > > Users that need a power-of-two buffer (the common case) now waste almost
> > > 50% of the space.
> > > 
> > 
> > Okay, give me a thought about this....... yes you are right ;-( But what
> > is with vmalloc? 128 MB should be enough?
> 
> vmalloc also has performance problems on some architectures that can
> access the linear mapping faster than paged memory and it is
> rather wasteful if you have 64kb pages.
> 
> I don't think the total size matters, the 128 MB limit only exists
> if you have a 32 bit CPU and 1GB or more of memory, which is hopefully
> getting rarer and already causes other problems (highmem...).
> 
> kmalloc currently limits the kfifo size to something like 128kb (arch
> specific), if you need more than that, you need alloc_pages(), which
> is limited to a power-of-two amount of pages.
> 

You are right, i don't like vmalloc too. It was only a first thought ;-)

> > > The requirement for power-of-two also meant a much faster __kfifo_off
> > > function on certain embedded platforms that don't have an integer division
> > > instruction in hardware.
> >
> > Yes i know this argument, but since the day of the 6502 and Z80 i have
> > never seen this kind of CPU. Okay i forgot to mention the stupid ARM
> > CPU, but newer ARM cores have a hardware division support.
> 
> I think this is actually more relevant than the vmalloc limit you mentioned,
> demand for tiny processors will probably stay because of cost reasons.
> Architectures that we support in Linux without integer divide include
> arm, blackfin, h8300, ia64 (!), m68k, microblaze, sh and xtensa.
> 

I'm embedded developer too... so i know what you mean. But for the fifo
this is not really a problem, managing and copying the data will be the
bigger amount. But with my new version i go back to the old power of two
method.

> Your first version with the non-power-of-two buffers also had a bug
> in the handling because it would not handle 32 bit integer overflows
> correctly. To get those right, you need an extra branch every time you
> add to the counter.
> 

Ooops, that was a real bug... Thanks.

> Your second version is ok in this regard because it uses the original
> size logic.

Does it mean you like it now ;-) ???? I think we are on a good way!

> 
> 	Arnd <><

Stefani <\_,

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

On Tuesday 04 August 2009, Stefani Seibold wrote:
> > Your second version is ok in this regard because it uses the original
> > size logic.
> 
> Does it mean you like it now ;-) ???? I think we are on a good way!

It looks much better now, but I still think you are doing too many
things at once, and I disagree about the locking changes.

I think it would be best to have an incremental set of patches
to the original code, along the lines of

[PATCH 1/x] kfifo: preparation code reorg, no functional change
[PATCH 2/x] kfifo: add DEFINE_KFIFO and friends
[PATCH 3/x] kfifo: add kfifo_{to,from}_user
[PATCH 4/x] kfifo: add kfifo_{get,put}_rec
[PATCH 5/x] kfifo: ...

About the locking stuff, I think it should best be left in place.
The __kfifo_{get,put} functions should probably be declared part
of the official interface and documented as such -- people are
using them anyways. It's generally a good idea to have the obvious
interface work in an entirely safe way (kfifo_get doing all the
locking it might need), with a __foo variant of the same function
for people that want the extra performance and know what they are
doing.

I would also leave out the recsize argument, using an 'unsigned short'
for the record length unconditionally won't waste any real space but
simplifies both the implementation and the interface.

Finally, I don't see a reason for the optional KFIFO_F_NOTRIM argument.
If you have fixed records, I would guess that you always need it
anyway, so you could just make it the default and remove the function
argument.

	Arnd <><

Re: [RFC 0/2] new kfifo API

[Stefani Seibold]

Am Dienstag, den 04.08.2009, 15:45 +0200 schrieb Arnd Bergmann:
> On Tuesday 04 August 2009, Stefani Seibold wrote:
> > > Your second version is ok in this regard because it uses the original
> > > size logic.
> > 
> > Does it mean you like it now ;-) ???? I think we are on a good way!
> 
> It looks much better now, but I still think you are doing too many
> things at once, and I disagree about the locking changes.
> 

I had a look at the user of the kfifo_put and kfifo_get, most did not
really depend on the spinlock, because there are single read/single
write users.
 
> I think it would be best to have an incremental set of patches
> to the original code, along the lines of
> 
> [PATCH 1/x] kfifo: preparation code reorg, no functional change

This is not possible. You cannot cleanup functionality without changing
and breaking anything.

> [PATCH 2/x] kfifo: add DEFINE_KFIFO and friends
> [PATCH 3/x] kfifo: add kfifo_{to,from}_user
> [PATCH 4/x] kfifo: add kfifo_{get,put}_rec
> [PATCH 5/x] kfifo: ...
> 

Thats will work... but the first patch will break something. Why is
everybody depending on this stupid split patch dogma, beside it make
sense or not?

If i do this in that why, then the first patch will change 13 files, and
modify about 70 lines.
 
> About the locking stuff, I think it should best be left in place.
> The __kfifo_{get,put} functions should probably be declared part
> of the official interface and documented as such -- people are
> using them anyways. It's generally a good idea to have the obvious
> interface work in an entirely safe way (kfifo_get doing all the
> locking it might need), with a __foo variant of the same function
> for people that want the extra performance and know what they are
> doing.
> 

Believe me, nobody need this locking stuff. The common use case is one
writer/one reader, so it is complete useless. Have a look on the current
source file wich use it.

But kfifo_put() and kfifo_put will() be in the next version static
inlines to __kfifo_put() and __kfifo_get(). So we are compatible at this
point. 

> I would also leave out the recsize argument, using an 'unsigned short'
> for the record length unconditionally won't waste any real space but
> simplifies both the implementation and the interface.
> 

You are wrong. It is designed to be look free until one reader and one
writer is in use. If i split the record operation i must introduce a
lock, because between two kfifo_put a kfifo_get operation can happen (or
visa verse).
   
> Finally, I don't see a reason for the optional KFIFO_F_NOTRIM argument.
> If you have fixed records, I would guess that you always need it
> anyway, so you could just make it the default and remove the function
> argument.
> 

The design is to have variable length records, so it it not always true
that the destination of an operation have enough space. Cutting of the
record is not always what then is desired. It also does not cost any
code or performance since it is handle by __build_constant_p and will be
complete optimized away.

I would get a little bit confused ... Why did you not say "please add
only the kfifo_from_user() and kfifo_to_user() stuff and throw the rest
away"?. I am thankful for your review and your objections, but if my
idea is melt down in that way i would prefer not do the job.

Why do you have so much fear to change an interfaces which is currently
used by very few sources? Most of them are not critical.  

I think it is a quiet clean interface, easy to use, easy to understand
and handles 99 percent of the use cases.

So my offer is to split it into 5 patches against the current 2.6.31
tree:

[PATCH 1/x] kfifo  code cleanup and preparation (includes for broken sources)
[PATCH 2/x] kfifo: remove spinlock (includes fix for broken sources) 
[PATCH 3/x] kfifo: add DEFINE_KFIFO and friends
[PATCH 4/x] kfifo: add kfifo_{to,from}_user
[PATCH 5/x] kfifo: add kfifo_{get,put}_rec

Is this acceptable? It would be nice to have your support.

Stefani

Re: [RFC 0/2] new kfifo API

[Arnd Bergmann]

On Tuesday 04 August 2009, Stefani Seibold wrote:
> Am Dienstag, den 04.08.2009, 15:45 +0200 schrieb Arnd Bergmann:
> > On Tuesday 04 August 2009, Stefani Seibold wrote:
> > > > Your second version is ok in this regard because it uses the original
> > > > size logic.
> > > 
> > > Does it mean you like it now ;-) ???? I think we are on a good way!
> > 
> > It looks much better now, but I still think you are doing too many
> > things at once, and I disagree about the locking changes.
> > 
> 
> I had a look at the user of the kfifo_put and kfifo_get, most did not
> really depend on the spinlock, because there are single read/single
> write users.

The question is not so much what the common use case is but what
the safe one is. Except for Andi's NMI driver, everyone can use
the locked version, even if many could use the unlocked version
if they want it to be faster.

You could of course change the existing users of the locked
interface to use the unlocked one, but I wouldn't bother.
Changing the behaviour of an existing interface without changing
the name is not so nice though.

If you read the original discussion about kfifo, a lot of
it focused around how locking should be done:
http://linux.derkeiler.com/Mailing-Lists/Kernel/2004-09/4195.html

Of course I realize that the locking gets into the way if you
want to do copy_{to,from}_user, but the last person that had
this problem also worked around that by defining user access
only for the unlocked versions:
http://linux.derkeiler.com/Mailing-Lists/Kernel/2007-06/msg04959.html

No idea why this was never merged ;-)

> > [PATCH 2/x] kfifo: add DEFINE_KFIFO and friends
> > [PATCH 3/x] kfifo: add kfifo_{to,from}_user
> > [PATCH 4/x] kfifo: add kfifo_{get,put}_rec
> > [PATCH 5/x] kfifo: ...
> > 
> 
> Thats will work... but the first patch will break something. Why is
> everybody depending on this stupid split patch dogma, beside it make
> sense or not?

multiple reasons:

- it makes reviews easier. You want the patches to get merged, so it's
your job to make it easy to see how they help and don't cause bugs.

- the patches with the separate changelogs become part of the
bisectable git history. If something breaks, we can find the specific
change that caused it and see the problem, potentially reverting
the patch.

- the patch description becomes part of the documentation of the code.
if you don't understand why code is done in a specific way, you can
look at the patch that introduced it. Your 0/2 mail contents are very
detailed, but don't get anywhere, while a patch description lives
forever.

All of these are much more important for infrastructure changes than
for device drivers.

> If i do this in that why, then the first patch will change 13 files, and
> modify about 70 lines.

That doesn't sound too much.

> > About the locking stuff, I think it should best be left in place.
> > The __kfifo_{get,put} functions should probably be declared part
> > of the official interface and documented as such -- people are
> > using them anyways. It's generally a good idea to have the obvious
> > interface work in an entirely safe way (kfifo_get doing all the
> > locking it might need), with a __foo variant of the same function
> > for people that want the extra performance and know what they are
> > doing.
> > 
> 
> Believe me, nobody need this locking stuff. The common use case is one
> writer/one reader, so it is complete useless. Have a look on the current
> source file wich use it.

ok. Mostly true, but looking at it conservatively:

sonypi.c: multiple readers: sonypi_misc_read can be called concurrently,
	which is probably a driver bug

meyeioc.c: ioctl can race with irq

sony-laptop.c: sony_pic_irq can race with sony_nc_notify, sonypi_misc_read
	can race with do_sony_laptop_release_key

cxio_resource.c: I have no idea what that code does, do you?

> > I would also leave out the recsize argument, using an 'unsigned short'
> > for the record length unconditionally won't waste any real space but
> > simplifies both the implementation and the interface.
> > 
> 
> You are wrong. It is designed to be look free until one reader and one
> writer is in use. If i split the record operation i must introduce a
> lock, because between two kfifo_put a kfifo_get operation can happen (or
> visa verse).

I don't understand what you mean by that or what it has to do with
the recsize argument.

> > Finally, I don't see a reason for the optional KFIFO_F_NOTRIM argument.
> > If you have fixed records, I would guess that you always need it
> > anyway, so you could just make it the default and remove the function
> > argument.
> 
> The design is to have variable length records, so it it not always true
> that the destination of an operation have enough space. Cutting of the
> record is not always what then is desired. It also does not cost any
> code or performance since it is handle by __build_constant_p and will be
> complete optimized away.

I did not object to the implementation complexity but everybody having
to specify an extra argument which is likely to be the same in all cases,
just like you argue that we don't need both locked and unlocked versions
when everyone could live with the unlocked API.

> I would get a little bit confused ... Why did you not say "please add
> only the kfifo_from_user() and kfifo_to_user() stuff and throw the rest
> away"?. I am thankful for your review and your objections, but if my
> idea is melt down in that way i would prefer not do the job.
> 
> Why do you have so much fear to change an interfaces which is currently
> used by very few sources? Most of them are not critical.

especially because it is so rarely used, any regressions would likely
not get found early, so it would be better to only touch the code
when the change is "obviously correct" and a significant improvement.

Adding new interfaces obviously doesn't cause regressions, but counts
as untested (or bitrotten) code until there are actual users in the
tree, which you don't have.

> So my offer is to split it into 5 patches against the current 2.6.31
> tree:
> 
> [PATCH 1/x] kfifo  code cleanup and preparation (includes for broken sources)
> [PATCH 2/x] kfifo: remove spinlock (includes fix for broken sources) 
> [PATCH 3/x] kfifo: add DEFINE_KFIFO and friends
> [PATCH 4/x] kfifo: add kfifo_{to,from}_user
> [PATCH 5/x] kfifo: add kfifo_{get,put}_rec
> 
> Is this acceptable? It would be nice to have your support.

Yes, that looks good.

	Arnd <><