[PATCH 0/7] new kfifo API

[PATCH 0/7] 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 21 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:
--------

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask)
 Allocates a new FIFO internal buffer
 @fifo: the fifo to assign then new buffer
 @size: the size of the internal buffer to be allocated.
 @gfp_mask: get_free_pages mask, passed to kmalloc()


void kfifo_init(struct kfifo *fifo, unsigned char *buffer, unsigned int size)
 Initialize a FIFO using a preallocated buffer

 The buffer will be release with kfifo_free().

 @fifo: the fifo to assign the buffer
 @buffer: the preallocated buffer to be used.
 @size: the size of the internal buffer, this have to be a power of 2.


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.


void kfifo_reset_in(struct kfifo *fifo)
 Skip input FIFO contents
 @fifo: the fifo to be emptied.


void kfifo_reset_out(struct kfifo *fifo)
 Skip output FIFO contents
 @fifo: the fifo to be emptied.


unsigned int kfifo_len(struct kfifo *fifo)
 Returns the number of used bytes in the FIFO
 @fifo: the fifo to be used.


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


kfifo_is_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 int kfifo_avail(struct kfifo *fifo)
 Returns the number of bytes available in the FIFO
 @fifo: the fifo to be used.


unsigned int kfifo_in(struct kfifo *fifo, unsigned char *from, unsigned int n)
 Puts some data into the FIFO.

 This function copies at most @n bytes from @from into
 the FIFO depending on the free space, and returns the number of
 bytes 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.


unsigned int kfifo_out(struct kfifo *fifo, unsigned char *to, unsigned int n)
 Gets some data from the FIFO.

 This function copies at most @n bytes from the FIFO into
 @to and returns the number of copied bytes.

 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.

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

 This function copies at most @n bytes from the @from into the FIFO
 and returns the number of copied bytes.

 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.


unsigned int kfifo_to_user(struct kfifo *fifo, void __user *to, unsigned int n)
 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.

 This function copies at most @n bytes from the FIFO into @to
 and returns the number of copied bytes.

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


These are the functions for handling records:
---------------------------------------------

unsigned int kfifo_in_rec(struct kfifo *fifo,
	unsigned char *from, unsigned int n, unsigned int recsize)
 Puts some record data into the FIFO.

 This function copies @n bytes from the @from into
 the FIFO and returns the number of bytes which cannot be copied.
 A returned value greater than the @n value means that the record doesn't
 fit into the buffer.

 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


unsigned int kfifo_out_rec(struct kfifo *fifo,
	unsigned char *to, unsigned int n, unsigned int recsize,
	unsigned int *total)
 Gets some record data from the FIFO.
 
 This function copies at most @n bytes from the @to into
 the FIFO and returns the number of bytes which cannot be copied.

 A returned value greater than the @n value means that the record doesn't
 fit into the @to buffer.

 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
 @total: pointer where the total number of to copied bytes should stored


unsigned int kfifo_from_user_rec(struct kfifo *fifo,
	const void __user *from, unsigned int n, unsigned int recsize)
 Puts some data from user space into the FIFO
 
 This function copies @n bytes from the @from into the
 FIFO and returns the number of bytes which cannot be copied. If the 
 returned value is equal or less the @n value, the copy_from_user() functions has 
 failed. Otherwise the record doesn't fit into the buffer.
 
 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


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

 This function copies at most @n bytes from the FIFO into @to.
 In case of an error, the function returns the number of bytes which cannot
 be copied. If the returned value is equal or less the @n value, the
 copy_to_user() functions has failed. Otherwise the record doesn't fit into
 the @to buffer.

 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
 @total: pointer where the total number of to copied bytes should stored


unsigned long kfifo_peek_rec(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


unsigned int kfifo_skip_rec(struct kfifo *fifo,	unsigned int recsize)
 Skip the next output record

 This function skips the next FIFO record

 @fifo: the fifo to be used.
 @recsize: size of record field


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

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 was 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

The patch is splitted into 7 parts:
 Part 1: Code reorganization, no functional change
 Part 2: Move out spinlock
 Part 3: Cleanup namespace
 Part 4: rename kfifo_put... -> kfifo_in... and kfifo_get... -> kfifo_out...
 Part 5: add DEFINE_KFIFO and friends, add very tiny functions
 Part 6: add kfifo_from_user and kfifo_to_user
 Part 7: add record handling functions (does some reorg)

Greetings,
Stefani

Re: [PATCH 0/7] new kfifo API

[Arnd Bergmann]

On Wednesday 12 August 2009, Stefani Seibold wrote:
> This is a proposal of a new generic kernel FIFO implementation.

Hi Stefani,

The patches look mostly good content-wise, but you don't have
separate changelog entries. The text of your introductory
mail will be lost in git history when the patches get
applied, so all the reaoning why a patch makes sense needs
to get into the patch description.

Similarly, the patch shortlog, i.e. the subject lines of
your mails, should be the lines you mention below.

> The patch is splitted into 7 parts:
>  Part 1: Code reorganization, no functional change

This one is not 'no functional change', because it
actually changes the interface, so the description needs
to be adapted.

Making the fifo itself a member of the data structure is
a very good idea, which should be what the changeset
comment describes (why that is done, not how of course).

The other change in here is that you add a 'spinlock_t *'
argument to kfifo_alloc and kfifo_init. AFAICT this is
unrelated, and it gets reverted by the next patch, so it
would be more straightforward to leave that change out.

>  Part 2: Move out spinlock

I don't see this one as worthwhile, but I don't mind
either. The contents look correct.

>  Part 3: Cleanup namespace

Looks good, it's the obvious consequence of the patch before.

>  Part 4: rename kfifo_put... -> kfifo_in... and kfifo_get... -> kfifo_out...

That one is new, right?

It's probably better to have this, just to make sure everyone
understands that the API is different now and no (out of tree)
drivers or patches accidentally break.

It only changes code that you already changed in patches 2 and 3
though, so I'd recommend folding the respective changes into
those patches.

>  Part 5: add DEFINE_KFIFO and friends, add very tiny functions
>  Part 6: add kfifo_from_user and kfifo_to_user

These look good. The macros in patch 5 could use some kerneldoc
comments so they show up in Documentation/Docbook/kernel-api.*.

>  Part 7: add record handling functions (does some reorg)

This one adds a lot of extra complexity in unused code.
I'll add my Acked-by to the first six patches if you do the
minor modifications I mention above, but for the last one,
I suggest you either add an actual user of that code, or find
someone else to advocate its inclusion.

	Arnd <><

Re: [PATCH 0/7] new kfifo API

[Stefani Seibold]

Am Mittwoch, den 12.08.2009, 16:58 +0200 schrieb Arnd Bergmann:
> On Wednesday 12 August 2009, Stefani Seibold wrote:
> > This is a proposal of a new generic kernel FIFO implementation.
> 
> Hi Stefani,
> 

Hi Arnd,

Thanks for reviewing my code.

> The patches look mostly good content-wise, but you don't have
> separate changelog entries. The text of your introductory
> mail will be lost in git history when the patches get
> applied, so all the reaoning why a patch makes sense needs
> to get into the patch description.
> 

It was so late in the night... sorry i was tiered and i will do a more
accurate description the next time ;-)
 
> Similarly, the patch shortlog, i.e. the subject lines of
> your mails, should be the lines you mention below.
> 
> > The patch is splitted into 7 parts:
> >  Part 1: Code reorganization, no functional change
> 
> This one is not 'no functional change', because it
> actually changes the interface, so the description needs
> to be adapted.
> 
> Making the fifo itself a member of the data structure is
> a very good idea, which should be what the changeset
> comment describes (why that is done, not how of course).
> 
> The other change in here is that you add a 'spinlock_t *'
> argument to kfifo_alloc and kfifo_init. AFAICT this is
> unrelated, and it gets reverted by the next patch, so it
> would be more straightforward to leave that change out.
> 

That is the problem: If i do to much in one patch set it is bad... but
if i try to make smaller patch which are viable, than i need some
intermediate steps. So what is the right way???
  
> >  Part 2: Move out spinlock
> 
> I don't see this one as worthwhile, but I don't mind
> either. The contents look correct. 

Andrew like the idea too, because it gibe the user the freedom of choice
which locking he needs, in most case no locking is required.

> 
> >  Part 3: Cleanup namespace
> 
> Looks good, it's the obvious consequence of the patch before.
> 
> >  Part 4: rename kfifo_put... -> kfifo_in... and kfifo_get... -> kfifo_out...
> 
> That one is new, right?
> 
> It's probably better to have this, just to make sure everyone
> understands that the API is different now and no (out of tree)
> drivers or patches accidentally break.
> 

Yes, it new. It was your suggestion to make the new API miss use save. I
like the idea, but i am not very happy with the names. The old names was
much more logical.
 
> It only changes code that you already changed in patches 2 and 3
> though, so I'd recommend folding the respective changes into
> those patches.
> 
> >  Part 5: add DEFINE_KFIFO and friends, add very tiny functions
> >  Part 6: add kfifo_from_user and kfifo_to_user
> 
> These look good. The macros in patch 5 could use some kerneldoc
> comments so they show up in Documentation/Docbook/kernel-api.*.
> 

I will have a look on these....

> >  Part 7: add record handling functions (does some reorg)
> 
> This one adds a lot of extra complexity in unused code.
> I'll add my Acked-by to the first six patches if you do the
> minor modifications I mention above, but for the last one,
> I suggest you either add an actual user of that code, or find
> someone else to advocate its inclusion.
> 

Thats the reason why i made a separate patch for this. But i fixed a lot
of your objections since last time. Please have a look on it. It solves
much of the use case needed by the current users.

a.) It doesn't copy anything if the FIFO supply not enough data
b.) It doesn't copy anything if the target buffer has not enough space
c.) It returns the number of bytes which could not copied, or 0 if okay.
This makes error handling much easier.
d.) It gives device driver developer more flexibility to store variable
length data into the FIFO.
e.) It also gives a better support for fixed record size entries.

I still have an actual user for this... a lot of my device drivers
depend on it and some of them are also interesting for the community,
like my USB NRP-Sensor (Rohde&Schwarz) driver. 

I also can fix some of the current user to use the new API function. But
i have none of this hardware, so i am unable to test it :-( I can do it
for you as an examples how things will be simplified.

One of the main reasons for this patch was to get in the record support.
So i still hope that you and/or andrew give it a try. It does not really
blow the kernel, because the functionality is most inline.
 
> 	Arnd <><

Greetings,
Stefani

Re: [PATCH 0/7] new kfifo API

[Arnd Bergmann]

On Wednesday 12 August 2009, Stefani Seibold wrote:
> Am Mittwoch, den 12.08.2009, 16:58 +0200 schrieb Arnd Bergmann:
> > On Wednesday 12 August 2009, Stefani Seibold wrote:
> > > This is a proposal of a new generic kernel FIFO implementation.

> > Making the fifo itself a member of the data structure is
> > a very good idea, which should be what the changeset
> > comment describes (why that is done, not how of course).
> > 
> > The other change in here is that you add a 'spinlock_t *'
> > argument to kfifo_alloc and kfifo_init. AFAICT this is
> > unrelated, and it gets reverted by the next patch, so it
> > would be more straightforward to leave that change out.
> > 
> 
> That is the problem: If i do to much in one patch set it is bad... but
> if i try to make smaller patch which are viable, than i need some
> intermediate steps. So what is the right way???

In general, smaller patches are better. As I said above, your
patch 1 actually does two things when it should just do one.

Since the patch immediately following it undoes one of the two
changes, the right option is to not do that part at all.
   
> > >  Part 2: Move out spinlock
> > 
> > I don't see this one as worthwhile, but I don't mind
> > either. The contents look correct. 
> 
> Andrew like the idea too, because it gibe the user the freedom of choice
> which locking he needs, in most case no locking is required.

Well, the original code already gives you the option by calling
__kfifo_get instead of __kfifo_put, as a number of drivers do.
Your patch does not change that, it only means that you save a few
bytes in the kfifo struct if you don't use a lock.

This was one of the options suggested for the initial submission
of the kfifo API back in 2004, and it was not chosen for some reason.
As I said, I don't mind much either way, but ideally you would try
to find out what the reason for doing it the other way initially
was, and describing in your patch what has changed now.

I suppose something along the lines of "we used to think that most
users would need the lock, it turned out that most actually don't,
so let's safe a tiny bit of space and time for the common case" would
do.

> > That one is new, right?
> > 
> > It's probably better to have this, just to make sure everyone
> > understands that the API is different now and no (out of tree)
> > drivers or patches accidentally break.
> 
> Yes, it new. It was your suggestion to make the new API miss use save. I
> like the idea, but i am not very happy with the names. The old names was
> much more logical.

Well, it's probably bad to move to a less logical naming, so if you
can't come up with something that is as good as the old one but still
different, you might want to leave this change out after all.

> > >  Part 7: add record handling functions (does some reorg)
> > 
> > This one adds a lot of extra complexity in unused code.
> > I'll add my Acked-by to the first six patches if you do the
> > minor modifications I mention above, but for the last one,
> > I suggest you either add an actual user of that code, or find
> > someone else to advocate its inclusion.
> 
> Thats the reason why i made a separate patch for this. But i fixed a lot
> of your objections since last time. Please have a look on it. It solves
> much of the use case needed by the current users.
> 
> a.) It doesn't copy anything if the FIFO supply not enough data
> b.) It doesn't copy anything if the target buffer has not enough space
> c.) It returns the number of bytes which could not copied, or 0 if okay.
> This makes error handling much easier.
> d.) It gives device driver developer more flexibility to store variable
> length data into the FIFO.
> e.) It also gives a better support for fixed record size entries.

ok, good. I'll have another look the next time you submit this.

> I still have an actual user for this... a lot of my device drivers
> depend on it and some of them are also interesting for the community,
> like my USB NRP-Sensor (Rohde&Schwarz) driver. 

Ok, fair enough, that's all I was asking for. So I guess you should just
leave out this patch from the current series and submit it together with
one of your drivers using the interface. That will make it much clearer
how the code is used.

	Arnd <><

Re: [PATCH 0/7] new kfifo API

[Amerigo Wang]

On Wed, Aug 12, 2009 at 12:31:13AM +0200, Stefani Seibold wrote:
>This is a proposal of a new generic kernel FIFO implementation.
>The patch is splitted into 7 parts:
> Part 1: Code reorganization, no functional change
> Part 2: Move out spinlock
> Part 3: Cleanup namespace
> Part 4: rename kfifo_put... -> kfifo_in... and kfifo_get... -> kfifo_out...
> Part 5: add DEFINE_KFIFO and friends, add very tiny functions
> Part 6: add kfifo_from_user and kfifo_to_user
> Part 7: add record handling functions (does some reorg)

Hi, Stefani

Can you put these patches into one thread? I have to search my
inbox to find all of them. :)

And, personally I don't like your splitting of these patches,
I prefer to see kfifo API changes first, then their usages.

Anyway, nice work! Thanks!

Re: [PATCH 0/7] new kfifo API

[Arnd Bergmann]

On Thursday 13 August 2009 03:09:03 Amerigo Wang wrote:

> And, personally I don't like your splitting of these patches,
> I prefer to see kfifo API changes first, then their usages.
 
Note that they are relatively hard to split without breaking
git-bisect. That can only work if you are able to introduce
the API under a different name first and then change the
users, finally removing the old API.

	Arnd <><