new kfifo API
cover new kfifo API
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
Quoted 7 lines · 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.
Quoted 7 lines
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).
Quoted 13 lines
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_KFIFOandINIT_KFIFOMacros
- 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
Quoted 8 lines
Inside a fifo this record types it is not a good idea to mix them together.
- Directcopy_to_userfrom the fifo andcopy_from_userinto 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.
Quoted 17 lines
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
Quoted 2 lines
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 <><
Am Montag, den 03.08.2009, 16:42 +0200 schrieb Arnd Bergmann:
Quoted 16 lines · Stefani Seibold
Quoted 7 lines
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.
Quoted 7 lines
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
Quoted 4 lines
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.
Quoted 26 lines
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).
Quoted 13 lines
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_KFIFOandINIT_KFIFOMacros
- 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 fieldQuoted 8 lines
Inside a fifo this record types it is not a good idea to mix them together.
- Directcopy_to_userfrom the fifo andcopy_from_userinto 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
Quoted 9 lines
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.
Quoted 17 lines
Quoted 17 lines
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
Quoted 5 lines
Quoted 2 lines
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.
Quoted 3 lines
We have also recently gained the
include/linux/ring_buffer.hAPI 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.
Quoted 1 line
Arnd <><
Quoted 8 lines · Arnd Bergmann
Quoted 7 lines · 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.
Quoted 6 lines
Quoted 6 lines
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.
Quoted 9 lines · Stefani Seibold
Am Montag, den 03.08.2009, 16:42 +0200 schrieb Arnd Bergmann:
Quoted 3 lines
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).
Quoted 10 lines
Quoted 9 lines
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.
Quoted 5 lines
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.
Quoted 3 lines
Third: The old API did not have a
kfifo_to_useroder akfifo_from_userfunctionality, 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.
Quoted 3 lines
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 <><
Quoted 3 lines · Stefani Seibold
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.
Quoted 7 lines
The API:
--------struct kfifo *kfifo_alloc(unsigned long size,
gfp_tgfp_mask)
Dynamically allocates a new fifo and returns the address @size: the size of the internal buffer to be allocated. @gfp_mask:get_free_pagesmask, passed tokmalloc()
For the MCE use case this would need to be able to optionally use bootmem because the first initialization happens too early.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
Quoted 7 lines · Andi Kleen
Quoted 4 lines
struct kfifo *kfifo_alloc(unsigned long size,
gfp_tgfp_mask)
Dynamically allocates a new fifo and returns the address @size: the size of the internal buffer to be allocated. @gfp_mask:get_free_pagesmask, passed tokmalloc()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 <><
Am Montag, den 03.08.2009, 20:23 +0200 schrieb Arnd Bergmann:
Quoted 11 lines · Stefani Seibold
Quoted 9 lines
Am Montag, den 03.08.2009, 16:42 +0200 schrieb Arnd Bergmann:
Quoted 3 lines
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.
Quoted 6 lines
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.....
Quoted 13 lines
Quoted 13 lines
Quoted 9 lines
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.
Quoted 8 lines
Quoted 2 lines
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.
Quoted 9 lines
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.
Quoted 7 lines
Quoted 3 lines
Third: The old API did not have a
kfifo_to_useroder akfifo_from_userfunctionality, 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.
Quoted 7 lines
Quoted 3 lines
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.
Quoted 1 line
Arnd <><
Stefani
Am Montag, den 03.08.2009, 20:27 +0200 schrieb Andi Kleen:
Quoted 9 lines
Quoted 3 lines · Stefani Seibold
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.
Quoted 8 lines
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.
Quoted 3 lines
The API:
--------
Quoted 8 lines
Quoted 4 lines
struct kfifo *kfifo_alloc(unsigned long size,
gfp_tgfp_mask)
Dynamically allocates a new fifo and returns the address @size: the size of the internal buffer to be allocated. @gfp_mask:get_free_pagesmask, passed tokmalloc()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 ;-)
Quoted 2 lines
-Andi
Stefani
Going through your list again:
Quoted 1 line · Stefani Seibold
- Generic usage: For kernel internal use or device driver
no change here, right?
Quoted 1 line
- Linux style habit:
DECLARE_KFIFO,DEFINE_KFIFOandINIT_KFIFOMacros
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.
Quoted 6 lines
- 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.
Quoted 1 line
- Direct
copy_to_userfrom the fifo andcopy_from_userinto the fifo.
Sounds useful, as mentioned.
Quoted 2 lines
- 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.
Quoted 2 lines
- 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 <><
Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
Quoted 5 lines
Going through your list again:
Quoted 1 line · Stefani Seibold
- Generic usage: For kernel internal use or device driver
Quoted 8 lines
no change here, right?
Quoted 1 line
- Linux style habit:
DECLARE_KFIFO,DEFINE_KFIFOandINIT_KFIFOMacros
DEFINE_KFIFOlooks useful, but I probably wouldn't expose the other macros, so you could define them as __KFIFO_* or integrate them into a largerDEFINE_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....
Quoted 7 lines
Quoted 6 lines
- 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.
Quoted 5 lines
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.
Quoted 9 lines
Quoted 1 line
- Direct
copy_to_userfrom the fifo andcopy_from_userinto the fifo.Sounds useful, as mentioned.
Quoted 2 lines
- 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:
Quoted 9 lines
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?
Quoted 4 lines
The requirement for power-of-two also meant a much faster
__kfifo_offfunction 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 <\_,
^ ^
Quoted 8 lines · Stefani Seibold
Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
DECLARE_KFIFOlooks for me more useful, because i can use it inside a struct decalaration. And then i needINIT_KFIFOfor initializing this.BTW:
DECLARE_....,DEFINE_..... andINIT_..... are linux style. Habe a look atworkqueue.h,wait.h,types.h,semaphore.h,rwsem-spinlock.h,interrupt.h,completion.h,seqlock.hand so on....
Yes, you are right. I realized that myself after I sent out my comments.
Quoted 6 lines
Quoted 6 lines
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.
Quoted 6 lines
Quoted 3 lines
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.
Quoted 7 lines
Quoted 3 lines
The requirement for power-of-two also meant a much faster
__kfifo_offfunction 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 <><
Am Dienstag, den 04.08.2009, 14:24 +0200 schrieb Arnd Bergmann:
Quoted 30 lines · Stefani Seibold
Quoted 8 lines
Am Montag, den 03.08.2009, 21:00 +0200 schrieb Arnd Bergmann:
DECLARE_KFIFOlooks for me more useful, because i can use it inside a struct decalaration. And then i needINIT_KFIFOfor initializing this.BTW:
DECLARE_....,DEFINE_..... andINIT_..... are linux style. Habe a look atworkqueue.h,wait.h,types.h,semaphore.h,rwsem-spinlock.h,interrupt.h,completion.h,seqlock.hand so on....Yes, you are right. I realized that myself after I sent out my comments.
Quoted 6 lines
Quoted 6 lines
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.Quoted 6 lines
Quoted 3 lines
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.
Quoted 8 lines
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 ;-)
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
The requirement for power-of-two also meant a much faster
__kfifo_offfunction on certain embedded platforms that don't have an integer division instruction in hardware.
Quoted 9 lines
Quoted 3 lines
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.
Quoted 5 lines
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.
Quoted 2 lines
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!
Quoted 2 lines
Arnd <><
Stefani <\_,
Quoted 4 lines · Stefani Seibold
Quoted 2 lines
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 <><
Am Dienstag, den 04.08.2009, 15:45 +0200 schrieb Arnd Bergmann:
Quoted 9 lines · Stefani Seibold
Quoted 4 lines
Quoted 2 lines
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.
Quoted 4 lines
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.
Quoted 5 lines
[PATCH 2/x] kfifo: add
DEFINE_KFIFOand 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.
Quoted 9 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_getdoing all the locking it might need), with a__foovariant 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.
Quoted 4 lines
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).
Quoted 5 lines
Finally, I don't see a reason for the optional
KFIFO_F_NOTRIMargument. 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
Quoted 7 lines · Stefani Seibold
Am Dienstag, den 04.08.2009, 15:45 +0200 schrieb Arnd Bergmann:
Quoted 6 lines · Stefani Seibold
Quoted 4 lines
Quoted 2 lines
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!
Quoted 7 lines
Quoted 3 lines
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_putandkfifo_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 ;-)
Quoted 9 lines
Quoted 5 lines
[PATCH 2/x] kfifo: add
DEFINE_KFIFOand 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.
Quoted 2 lines
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.
Quoted 10 lines
Quoted 9 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_getdoing all the locking it might need), with a__foovariant of the same function for people that want the extra performance and know what they are doing.
Quoted 3 lines
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?
Quoted 9 lines
Quoted 4 lines
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_putakfifo_getoperation can happen (or visa verse).
I don't understand what you mean by that or what it has to do with the recsize argument.
Quoted 10 lines
Quoted 4 lines
Finally, I don't see a reason for the optional
KFIFO_F_NOTRIMargument. 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_pand 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.
Quoted 7 lines
I would get a little bit confused ... Why did you not say "please add only the
kfifo_from_user()andkfifo_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.
Quoted 10 lines
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_KFIFOand friends
[PATCH 4/x] kfifo: add kfifo_{to,from}_user
[PATCH 5/x] kfifo: add kfifo_{get,put}_recIs this acceptable? It would be nice to have your support.
Yes, that looks good.
Arnd <><