kfifo: round up the fifo size power of 2

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.
----
I know it works with rounddown_pow_of_two as well, since size is maintained in the kfifo internal part. But, I'm quite curious why Stefani chose rounddown_pow_of_two. To reduce memory?

Thanks,
Yuanhan Liu
-----

Cc Stefani Seibold <[email protected]>

Cc Andrew Morton <[email protected]>

Signed-off-by Yuanhan Liu <[email protected]>

---
 kernel/kfifo.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

kernel/kfifo.c +3 -3

index 59dcf5b..0f78378 100644
@@ -39,11 +39,11 @@ int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
 		size_t esize, gfp_t gfp_mask)
 {
 	/*
-	 * round down to the next power of 2, since our 'let the indices
+	 * round up to the next power of 2, since our 'let the indices
 	 * wrap' technique works only in this case.
 	 */
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

@@ -84,7 +84,7 @@ int __kfifo_init(struct __kfifo *fifo, void *buffer,
 	size /= esize;
 
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:

Quoted 7 lines

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.
----
I know it works with rounddown_pow_of_two as well, since size is maintained in the kfifo internal part. But, I'm quite curious why Stefani chose rounddown_pow_of_two. To reduce memory?

Yes, exactly, if a user do the wrong thing, than the user will get also a wrong result, and did not waste memory.

But anyway, if the majority like this patch it is okay for me.

Quoted 35 lines

Cc Stefani Seibold <[email protected]>

Cc Andrew Morton <[email protected]>

Signed-off-by Yuanhan Liu <[email protected]>

---
 kernel/kfifo.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

kernel/kfifo.c +3 -3

index 59dcf5b..0f78378 100644
@@ -39,11 +39,11 @@ int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
 		size_t esize, gfp_t gfp_mask)
 {
 	/*
-	 * round down to the next power of 2, since our 'let the indices
+	 * round up to the next power of 2, since our 'let the indices
 	 * wrap' technique works only in this case.
 	 */
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

@@ -84,7 +84,7 @@ int __kfifo_init(struct __kfifo *fifo, void *buffer,
 	size /= esize;
 
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

Quoted 9 lines

Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:

Quoted 7 lines

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.
----
I know it works with rounddown_pow_of_two as well, since size is maintained in the kfifo internal part. But, I'm quite curious why Stefani chose rounddown_pow_of_two. To reduce memory?

Quoted 2 lines

Yes, exactly, if a user do the wrong thing, than the user will get also a wrong result, and did not waste memory.

But, isn't it better to 'correct' it? ;-)

Quoted 3 lines

But anyway, if the majority like this patch it is okay for me.

Sorry, do you mean you are OK with this patch?

Am Freitag, den 26.10.2012, 20:33 +0800 schrieb Yuanhan Liu:

Quoted 10 lines · Stefani Seibold

Quoted 9 lines

Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:

Quoted 7 lines

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.
----
I know it works with rounddown_pow_of_two as well, since size is maintained in the kfifo internal part. But, I'm quite curious why Stefani chose rounddown_pow_of_two. To reduce memory?

Quoted 4 lines

Quoted 2 lines

Yes, exactly, if a user do the wrong thing, than the user will get also a wrong result, and did not waste memory.

But, isn't it better to 'correct' it? ;-)

Both is wrong. This depends on the view. For me it is better to get less and don't wast space. For example: requesting 1025 will yield in your case to a fifo which 2048 elements, which requires double of the memory as expected.

Quoted 2 lines

Quoted 2 lines

Quoted 4 lines

Quoted 1 line

But anyway, if the majority like this patch it is okay for me.

Sorry, do you mean you are OK with this patch?

I depends not on me, ask for a democratic decisions.

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.

...

kernel/kfifo.c +2 -2

@@ -39,11 +39,11 @@ int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
 		size_t esize, gfp_t gfp_mask)
 {
 	/*
-	 * round down to the next power of 2, since our 'let the indices
+	 * round up to the next power of 2, since our 'let the indices
 	 * wrap' technique works only in this case.
 	 */
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

Quoted 28 lines · On Fri, 26 Oct 2012 15:56:57 +0800 Yuanhan Liu <[email protected]>…

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.

...

kernel/kfifo.c +3 -3

@@ -39,11 +39,11 @@ int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
 		size_t esize, gfp_t gfp_mask)
 {
 	/*
-	 * round down to the next power of 2, since our 'let the indices
+	 * round up to the next power of 2, since our 'let the indices
 	 * wrap' technique works only in this case.
 	 */
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

@@ -84,7 +84,7 @@ int __kfifo_init(struct __kfifo *fifo, void *buffer,
 	size /= esize;
 
 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);
 

kernel/kfifo.c int __kfifo_init(struct __kfifo *fifo, void *buffer, · line 90

Quoted 2 lines

kernel/kfifo.c +0 -0

 	fifo->in = 0;
 	fifo->out = 0;

hm, well, if the user asked for a 100-element fifo then it is a bit strange and unexpected to give them a 128-element one.

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 11 lines

Quoted 8 lines · On Fri, 26 Oct 2012 15:56:57 +0800 Yuanhan Liu <[email protected]>…

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.

...

kernel/kfifo.c +1 -1

 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +0 -0

 	fifo->in = 0;
 	fifo->out = 0;

hm, well, if the user asked for a 100-element fifo then it is a bit strange and unexpected to give them a 128-element one.

Yes, and I guess the same to give them a 64-element one.

Quoted 6 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

Quoted 3 lines

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

Am Mittwoch, den 31.10.2012, 13:59 +0800 schrieb Yuanhan Liu:

Quoted 31 lines · Andrew Morton

Quoted 11 lines

Quoted 8 lines · On Fri, 26 Oct 2012 15:56:57 +0800 Yuanhan Liu <[email protected]>…

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.

...

kernel/kfifo.c +1 -1

 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +0 -0

 	fifo->in = 0;
 	fifo->out = 0;

hm, well, if the user asked for a 100-element fifo then it is a bit strange and unexpected to give them a 128-element one.

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Andrew is right, this is an API miss design. So it would be good to rework the kfifo_init () and kfifo_alloc() to pass in log2 of the size, not the size itself.

Quoted 32 lines

Am Mittwoch, den 31.10.2012, 13:59 +0800 schrieb Yuanhan Liu:

Quoted 31 lines · Andrew Morton

Quoted 11 lines

Quoted 8 lines · On Fri, 26 Oct 2012 15:56:57 +0800 Yuanhan Liu <[email protected]>…

Say, if we want to allocate a filo with size of 6 bytes, it would be safer to allocate 8 bytes instead of 4 bytes.

...

kernel/kfifo.c +1 -1

 	if (!is_power_of_2(size))
-		size = rounddown_pow_of_two(size);
+		size = roundup_pow_of_two(size);

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +0 -0

 	fifo->in = 0;
 	fifo->out = 0;

hm, well, if the user asked for a 100-element fifo then it is a bit strange and unexpected to give them a 128-element one.

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 7 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Right.

Quoted 1 line

Quoted 3 lines

Andrew is right, this is an API miss design. So it would be good to rework the kfifo_init () and kfifo_alloc() to pass in log2 of the size, not the size itself.

Yes, this would make this issue gone completely. Would you mind to let me do that?

Quoted 12 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Andrew is right, this is an API miss design. So it would be good to rework the kfifo_init () and kfifo_alloc() to pass in log2 of the size, not the size itself.

Quoted 12 lines · On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <[email protected]> wrote:

Quoted 12 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 6 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Probably an insignificant change in performance.

It could be made much smaller by just never doing the modulus operation
- instead do

	if (++index == max)
		index = 0;

this does introduce one problem: it's no longer possible to distinguish the "full" and "empty" states by comparing the head and tail indices. But that is soluble.

Quoted 3 lines

Andrew is right, this is an API miss design. So it would be good to rework the kfifo_init () and kfifo_alloc() to pass in log2 of the size, not the size itself.

The power-of-2 thing is just a restriction in the current implementation - it's not a good idea to cement that into the interface. Of course, it could later be uncemented if the implementation's restriction was later relaxed.

Quoted 23 lines · Andrew Morton

Quoted 12 lines · On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <[email protected]> wrote:

Quoted 12 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 6 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Probably an insignificant change in performance.

Quoted 6 lines

It could be made much smaller by just never doing the modulus operation
- instead do

	if (++index == max)
		index = 0;

This can not be done, since the index manipulation kfifo does not use locks.

Quoted 13 lines

Quoted 13 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 6 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Probably an insignificant change in performance.

It could be made much smaller by just never doing the modulus operation
- instead do

	if (++index == max)
		index = 0;

this does introduce one problem: it's no longer possible to distinguish the "full" and "empty" states by comparing the head and tail indices. But that is soluble.

Quoted 3 lines

Andrew is right, this is an API miss design. So it would be good to rework the kfifo_init () and kfifo_alloc() to pass in log2 of the size, not the size itself.

The power-of-2 thing is just a restriction in the current implementation - it's not a good idea to cement that into the interface. Of course, it could later be uncemented if the implementation's restriction was later relaxed.

Quoted 12 lines · On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <[email protected]> wrote:

Quoted 12 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 6 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Probably an insignificant change in performance.

It could be made much smaller by just never doing the modulus operation
- instead do

	if (++index == max)
		index = 0;

this does introduce one problem: it's no longer possible to distinguish the "full" and "empty" states by comparing the head and tail indices. But that is soluble.

Quoted 4 lines

Andrew is right, this is an API miss design. So it would be good to rework the kfifo_init () and kfifo_alloc() to pass in log2 of the size, not the size itself.

The power-of-2 thing is just a restriction in the current implementation - it's not a good idea to cement that into the interface. Of course, it could later be uncemented if the implementation's restriction was later relaxed.

Quoted 26 lines · On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <[email protected]> wrote:

Quoted 13 lines

Quoted 13 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 6 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Probably an insignificant change in performance.

It could be made much smaller by just never doing the modulus operation
- instead do

Quoted 6 lines

	if (++index == max)
		index = 0;

this does introduce one problem: it's no longer possible to distinguish the "full" and "empty" states by comparing the head and tail indices. But that is soluble.

Hi Andrew,

Yes, it is soluble. How about the following solution?

Add 2 more fields(in_off and out_off) in __kfifo structure, so that in and out will keep increasing each time, while in_off and out_off will be wrapped to head if goes to the end of fifo buffer.

So, we can use in and out for counting unused space, and distinguish the "full" and "empty" state, and also, of course no need for locking.

Stefani, sorry for quite late reply. I checked all the code used kfifo_alloc and kfifo_init. Firstly, there are a lot of users ;-)

And secondly, I did find some examples used kfifo as it supports none-power-of-2 kfifo. Say, the one at drivers/hid/hid-logitech-dj.c:

       if (kfifo_alloc(&djrcv_dev->notif_fifo,
                       DJ_MAX_NUMBER_NOTIFICATIONS * sizeof(struct dj_report),
                       GFP_KERNEL)) {

which means it wants to allocate a kfifo buffer which can store DJ_MAX_NUMBER_NOTIFICATIONS(8 here) dj_report(each 15 bytes) at once.

And DJ_MAX_NUMBER_NOTIFICATIONS * sizeof(struct dj_report) = 8 * 15. Then current code would allocate a size of rounddown_power_of_2(120) = 64 bytes, which can hold 4 dj_report only once, which is a half of expected.

There are few more examples like this.

And, kfifo_init used a pre-allocated buffer, it would be a little strange to ask user to pre-allocate a power of 2 size aligned buffer.

So, I guess it's would be good to support none-power-of-2 kfifo?

I know you care the performance a lot. Well, as Andrew said, it may introduce a little insignificant drop(no modulus, few more add/dec). Thus, do you have some benchmarks for that? I can have a test to check if it is a insignificant change on performance or not :)

Am Donnerstag, den 08.11.2012, 20:24 +0800 schrieb Yuanhan Liu:

Quoted 54 lines · Andrew Morton

Quoted 26 lines · On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <[email protected]> wrote:

Quoted 13 lines

Quoted 13 lines

Yes, and I guess the same to give them a 64-element one.

Quoted 9 lines

If there's absolutely no prospect that the kfifo code will ever support 100-byte fifos then I guess we should rework the API so that the caller has to pass in log2 of the size, not the size itself. That way there will be no surprises and no mistakes.

That being said, the power-of-2 limitation isn't at all intrinsic to a fifo, so we shouldn't do this. Ideally, we'd change the kfifo implementation so it does what the caller asked it to do!

Quoted 6 lines

Quoted 3 lines

I'm fine with removing the power-of-2 limitation. Stefani, what's your comment on that?

You can't remove the power-of-2-limitation, since this would result in a performance decrease (bit wise and vs. modulo operation).

Probably an insignificant change in performance.

It could be made much smaller by just never doing the modulus operation
- instead do

Quoted 6 lines

	if (++index == max)
		index = 0;

this does introduce one problem: it's no longer possible to distinguish the "full" and "empty" states by comparing the head and tail indices. But that is soluble.

Hi Andrew,

Yes, it is soluble. How about the following solution?

Add 2 more fields(in_off and out_off) in __kfifo structure, so that in and out will keep increasing each time, while in_off and out_off will be wrapped to head if goes to the end of fifo buffer.

So, we can use in and out for counting unused space, and distinguish the "full" and "empty" state, and also, of course no need for locking.

Stefani, sorry for quite late reply. I checked all the code used kfifo_alloc and kfifo_init. Firstly, there are a lot of users ;-)

And secondly, I did find some examples used kfifo as it supports none-power-of-2 kfifo. Say, the one at drivers/hid/hid-logitech-dj.c:

       if (kfifo_alloc(&djrcv_dev->notif_fifo,
                       DJ_MAX_NUMBER_NOTIFICATIONS * sizeof(struct dj_report),
                       GFP_KERNEL)) {

Quoted 7 lines

which means it wants to allocate a kfifo buffer which can store DJ_MAX_NUMBER_NOTIFICATIONS(8 here) dj_report(each 15 bytes) at once.

And DJ_MAX_NUMBER_NOTIFICATIONS * sizeof(struct dj_report) = 8 * 15. Then current code would allocate a size of rounddown_power_of_2(120) = 64 bytes, which can hold 4 dj_report only once, which is a half of expected.

This will go away with a log API.

Quoted 7 lines

There are few more examples like this.

And, kfifo_init used a pre-allocated buffer, it would be a little strange to ask user to pre-allocate a power of 2 size aligned buffer.

So, I guess it's would be good to support none-power-of-2 kfifo?

Quoted 5 lines

I know you care the performance a lot. Well, as Andrew said, it may introduce a little insignificant drop(no modulus, few more add/dec). Thus, do you have some benchmarks for that? I can have a test to check if it is a insignificant change on performance or not :)

Dirty, Ugly, Hacky and this will produce a lot of overhead, especially for kfifo_put and kfifo_get which are inlined code.

In the kernel world it was always a regular use case to use power-of-2 restricted API's, f.e. the slab cache.

I see no benefit for a none-power-of-2 kfifo, only drawbacks.

Quoted 1 line

Am Donnerstag, den 08.11.2012, 20:24 +0800 schrieb Yuanhan Liu:

Yes, it is. I will try log API then.

Stefani, I found an issue while rework to current API. Say the current code of __kfifo_init:

    int __kfifo_init(struct __kfifo *fifo, void *buffer,
                    unsigned int size, size_t esize)
    {
        size /= esize;

        if (!is_power_of_2(size))
                size = rounddown_pow_of_two(size);
        ....
    }

Even thought I changed the API to something like:

    int __kfifo_init(struct __kfifo *fifo, void *buffer,
                    int size_order, size_t esize)
    {
	unsigned int size = 1 << size_order;

	size /= esize;
	...
    }

See? There is still a divide and we can't make it sure that it will be power of 2 after that.

So, I came up 2 proposal to fix this.

1. refactor the meaning of 'size' argument first.

'size' means the size of pre-allocated buffer. We can refactor it to meaning of 'the number of fifo elements' just like __kfifo_alloc, so that we don't need do the size /= esize stuff.

2. remove kfifo_init

As we can't make sure that kfifo will do exactly what users asked(in the way of fifo size). It would be safe and good to maintain buffer and buffer size inside kfifo. So, I propose to remove it and use kfifo_alloc instead.

git grep 'kfifo_init\>' shows that we currently have 2 users only.

The first way is hacky, and it doesn't make much sense to me. Since buffer is pre-allocated by user but not kfifo. User has to calculate element size and the number of elements, which is not friendly.

The second way does make more sense to me.

Am Freitag, den 09.11.2012, 10:32 +0800 schrieb Yuanhan Liu:

Quoted 52 lines · Stefani Seibold

Quoted 1 line

Am Donnerstag, den 08.11.2012, 20:24 +0800 schrieb Yuanhan Liu:

Yes, it is. I will try log API then.

Stefani, I found an issue while rework to current API. Say the current code of __kfifo_init:

    int __kfifo_init(struct __kfifo *fifo, void *buffer,
                    unsigned int size, size_t esize)
    {
        size /= esize;

        if (!is_power_of_2(size))
                size = rounddown_pow_of_two(size);
        ....
    }

Even thought I changed the API to something like:

    int __kfifo_init(struct __kfifo *fifo, void *buffer,
                    int size_order, size_t esize)
    {
	unsigned int size = 1 << size_order;

	size /= esize;
	...
    }

See? There is still a divide and we can't make it sure that it will be power of 2 after that.

So, I came up 2 proposal to fix this.

1. refactor the meaning of 'size' argument first.

'size' means the size of pre-allocated buffer. We can refactor it to meaning of 'the number of fifo elements' just like __kfifo_alloc, so that we don't need do the size /= esize stuff.

2. remove kfifo_init

As we can't make sure that kfifo will do exactly what users asked(in the way of fifo size). It would be safe and good to maintain buffer and buffer size inside kfifo. So, I propose to remove it and use kfifo_alloc instead.

git grep 'kfifo_init\>' shows that we currently have 2 users only.

The first way is hacky, and it doesn't make much sense to me. Since buffer is pre-allocated by user but not kfifo. User has to calculate element size and the number of elements, which is not friendly.

Quoted 1 line

The second way does make more sense to me.

kfifo_init() was requested by some kernel developers, i never liked it. If you have a better and cleaner solution than do it, otherwise kick it away if you like.