[PATCH 1/2] kfifo: round up the fifo size power of 2

[PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

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 <stefani@seibold.net>
Cc: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Yuanhan Liu <yuanhan.liu@linux.intel.com>
---
 kernel/kfifo.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/kfifo.c b/kernel/kfifo.c
index 59dcf5b..0f78378 100644
--- a/kernel/kfifo.c
+++ b/kernel/kfifo.c
@@ -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;
-- 
1.7.7.6

[PATCH 2/2] kfifo: handle the case that alloc size is equal to 0

[Yuanhan Liu]

is_power_of_2(size) will be failed if size is 0, and then it calls
roundup_pow_of_two(0), then will return a quite *huge* value(well, the
comments at roundup_pow_of_two macro says: the result is undefined when
n == 0).

Moving the size check before power of 2 testing and rounding will fix
this "not really happened yet" issue.

Cc: Stefani Seibold <stefani@seibold.net>
Cc: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Yuanhan Liu <yuanhan.liu@linux.intel.com>
---
 kernel/kfifo.c |   22 ++++++++++------------
 1 files changed, 10 insertions(+), 12 deletions(-)

diff --git a/kernel/kfifo.c b/kernel/kfifo.c
index 0f78378..e3a63c6 100644
--- a/kernel/kfifo.c
+++ b/kernel/kfifo.c
@@ -38,13 +38,6 @@ static inline unsigned int kfifo_unused(struct __kfifo *fifo)
 int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
 		size_t esize, gfp_t gfp_mask)
 {
-	/*
-	 * 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 = roundup_pow_of_two(size);
-
 	fifo->in = 0;
 	fifo->out = 0;
 	fifo->esize = esize;
@@ -54,6 +47,12 @@ int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
 		fifo->mask = 0;
 		return -EINVAL;
 	}
+	/*
+	 * 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 = roundup_pow_of_two(size);
 
 	fifo->data = kmalloc(size * esize, gfp_mask);
 
@@ -81,20 +80,19 @@ EXPORT_SYMBOL(__kfifo_free);
 int __kfifo_init(struct __kfifo *fifo, void *buffer,
 		unsigned int size, size_t esize)
 {
-	size /= esize;
-
-	if (!is_power_of_2(size))
-		size = roundup_pow_of_two(size);
-
 	fifo->in = 0;
 	fifo->out = 0;
 	fifo->esize = esize;
 	fifo->data = buffer;
 
+	size /= esize;
 	if (size < 2) {
 		fifo->mask = 0;
 		return -EINVAL;
 	}
+	if (!is_power_of_2(size))
+		size = roundup_pow_of_two(size);
+
 	fifo->mask = size - 1;
 
 	return 0;
-- 
1.7.7.6

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:
> 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.

> Thanks,
> Yuanhan Liu
> -----
> 
> Cc: Stefani Seibold <stefani@seibold.net>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Signed-off-by: Yuanhan Liu <yuanhan.liu@linux.intel.com>
> ---
>  kernel/kfifo.c |    6 +++---
>  1 files changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/kfifo.c b/kernel/kfifo.c
> index 59dcf5b..0f78378 100644
> --- a/kernel/kfifo.c
> +++ b/kernel/kfifo.c
> @@ -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;

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Fri, Oct 26, 2012 at 11:30:27AM +0200, Stefani Seibold wrote:
> Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:
> > 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, isn't it better to 'correct' it? ;-)

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

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

Thanks,
Yuanhan Liu
> > 
> > Cc: Stefani Seibold <stefani@seibold.net>
> > Cc: Andrew Morton <akpm@linux-foundation.org>
> > Signed-off-by: Yuanhan Liu <yuanhan.liu@linux.intel.com>
> > ---
> >  kernel/kfifo.c |    6 +++---
> >  1 files changed, 3 insertions(+), 3 deletions(-)
> > 
> > diff --git a/kernel/kfifo.c b/kernel/kfifo.c
> > index 59dcf5b..0f78378 100644
> > --- a/kernel/kfifo.c
> > +++ b/kernel/kfifo.c
> > @@ -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;
> 

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Freitag, den 26.10.2012, 20:33 +0800 schrieb Yuanhan Liu:
> On Fri, Oct 26, 2012 at 11:30:27AM +0200, Stefani Seibold wrote:
> > Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:
> > > 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, 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.

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

Greetings,
Stefani

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Fri, Oct 26, 2012 at 03:39:46PM +0200, Stefani Seibold wrote:
> Am Freitag, den 26.10.2012, 20:33 +0800 schrieb Yuanhan Liu:
> > On Fri, Oct 26, 2012 at 11:30:27AM +0200, Stefani Seibold wrote:
> > > Am Freitag, den 26.10.2012, 15:56 +0800 schrieb Yuanhan Liu:
> > > > 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, 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.
> 
> > 
> > > 
> > > 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.

Since you are the original athour, your comments matter :D

Thanks,
Yuanhan Liu

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Alan Cox]

IMHO absent any reason to make the allocation change we should keep the
existing behaviour. Absent any reason to fiddle with the code we should
leave it alone.

It's delicate, tricky, tiny and works. Don't fiddle.

For the size question if the default behaviour is to pack them in
then a caller can do their own padding if they want it, for the reverse
case you propose as a change this ceases to be true.

Thus I would say the current API is right anyway.

Alan

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Andrew Morton]

On Fri, 26 Oct 2012 15:56:57 +0800
Yuanhan Liu <yuanhan.liu@linux.intel.com> wrote:

> 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.
>
> ...
>
> --- a/kernel/kfifo.c
> +++ b/kernel/kfifo.c
> @@ -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;

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!

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Mon, Oct 29, 2012 at 01:59:35PM -0700, Andrew Morton wrote:
> On Fri, 26 Oct 2012 15:56:57 +0800
> Yuanhan Liu <yuanhan.liu@linux.intel.com> wrote:
> 
> > 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.
> >
> > ...
> >
> > --- a/kernel/kfifo.c
> > +++ b/kernel/kfifo.c
> > @@ -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;
> 
> 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.

Hi Andrew,

Yes, and I guess the same to give them a 64-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!

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

	--yliu

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Mittwoch, den 31.10.2012, 13:59 +0800 schrieb Yuanhan Liu:
> On Mon, Oct 29, 2012 at 01:59:35PM -0700, Andrew Morton wrote:
> > On Fri, 26 Oct 2012 15:56:57 +0800
> > Yuanhan Liu <yuanhan.liu@linux.intel.com> wrote:
> > 
> > > 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.
> > >
> > > ...
> > >  	if (!is_power_of_2(size))
> > > -		size = rounddown_pow_of_two(size);
> > > +		size = roundup_pow_of_two(size);
> > >  
> > >  	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.
> 
> > 
> > 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!
> 
> 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.

Stefani

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Wed, Oct 31, 2012 at 07:30:33AM +0100, Stefani Seibold wrote:
> Am Mittwoch, den 31.10.2012, 13:59 +0800 schrieb Yuanhan Liu:
> > On Mon, Oct 29, 2012 at 01:59:35PM -0700, Andrew Morton wrote:
> > > On Fri, 26 Oct 2012 15:56:57 +0800
> > > Yuanhan Liu <yuanhan.liu@linux.intel.com> wrote:
> > > 
> > > > 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.
> > > >
> > > > ...
> > > >  	if (!is_power_of_2(size))
> > > > -		size = rounddown_pow_of_two(size);
> > > > +		size = roundup_pow_of_two(size);
> > > >  
> > > >  	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.
> > 
> > > 
> > > 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!
> > 
> > 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.

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

	--yliu

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Mittwoch, den 31.10.2012, 14:49 +0800 schrieb Yuanhan Liu:
> On Wed, Oct 31, 2012 at 07:30:33AM +0100, Stefani Seibold wrote:
> > Am Mittwoch, den 31.10.2012, 13:59 +0800 schrieb Yuanhan Liu:
> > > On Mon, Oct 29, 2012 at 01:59:35PM -0700, Andrew Morton wrote:
> > > > On Fri, 26 Oct 2012 15:56:57 +0800
> > > > Yuanhan Liu <yuanhan.liu@linux.intel.com> wrote:
> > > > 
> > > > > 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.
> > > > >
> > > > > ...
> > > > >  	if (!is_power_of_2(size))
> > > > > -		size = rounddown_pow_of_two(size);
> > > > > +		size = roundup_pow_of_two(size);
> > > > >  
> > > > >  	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.
> > > 
> > > > 
> > > > 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!
> > > 
> > > 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.
> 
> > 
> > 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?
> 

Yes, do it. It would give as the best results.

Greetings,
Stefani

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Andrew Morton]

On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:

> > Yes, and I guess the same to give them a 64-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!
> > 
> > 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.

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

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Janne Kulmala]

On 10/31/2012 08:52 AM, Andrew Morton wrote:
> On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:
>
>>> Yes, and I guess the same to give them a 64-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!
>>>
>>> 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 can not be done, since the index manipulation kfifo does not use locks.

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

The index is just increased, and the access side masks the bottom bits 
from that to obtain the actual position. This exploit integer wrapping 
and the index will always wrap correctly to the begin of the fifo.

Using modulus and non-power-of-two size would produce wrong results and 
require adding locking.

-- 
Janne Kulmala <janne.t.kulmala@tut.fi>

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Andrew Morton]

On Wed, 31 Oct 2012 10:11:06 +0200 Janne Kulmala <janne.t.kulmala@tut.fi> wrote:

> On 10/31/2012 08:52 AM, Andrew Morton wrote:
> > On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:
> >
> >>> Yes, and I guess the same to give them a 64-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!
> >>>
> >>> 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 can not be done, since the index manipulation kfifo does not use locks.

Oh come on.  Look:

                        __kfifo->out++; \

and look:

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

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Dienstag, den 30.10.2012, 23:52 -0700 schrieb Andrew Morton:
> On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:
> 
> > > Yes, and I guess the same to give them a 64-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!
> > > 
> > > 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.
> 

And you will increase the code size, since kfifo_put and kfifo_get are
inline code. Also the speculative execution path of modern CPUs must
kick away the pipeline in case of are false branch prediction.
 
> > 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.

The power-of-2 thing is a design restriction, a balance between
performance and code size and usability.

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Tue, Oct 30, 2012 at 11:52:10PM -0700, Andrew Morton wrote:
> On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:
> 
> > > Yes, and I guess the same to give them a 64-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!
> > > 
> > > 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.

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 :)

Thanks!

	--yliu

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

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Donnerstag, den 08.11.2012, 20:24 +0800 schrieb Yuanhan Liu:
> On Tue, Oct 30, 2012 at 11:52:10PM -0700, Andrew Morton wrote:
> > On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:
> > 
> > > > Yes, and I guess the same to give them a 64-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!
> > > > 
> > > > 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.
> 
> 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.
> 

This will go away with a log API.

> 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 :)
> 

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.

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Thu, Nov 08, 2012 at 01:37:15PM +0100, Stefani Seibold wrote:
> Am Donnerstag, den 08.11.2012, 20:24 +0800 schrieb Yuanhan Liu:
> > On Tue, Oct 30, 2012 at 11:52:10PM -0700, Andrew Morton wrote:
> > > On Wed, 31 Oct 2012 07:30:33 +0100 Stefani Seibold <stefani@seibold.net> wrote:
> > > 
> > > > > Yes, and I guess the same to give them a 64-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!
> > > > > 
> > > > > 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.
> > 
> > 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.
> > 
> 
> This will go away with a log API.
> 
> > 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 :)
> > 
> 
> Dirty, Ugly, Hacky and this will produce a lot of overhead, especially
> for kfifo_put and kfifo_get which are inlined code.

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.

So, Stefani, what's your comments on that?

Thanks!

	--yliu
 
> 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.
> 

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Stefani Seibold]

Am Freitag, den 09.11.2012, 10:32 +0800 schrieb Yuanhan Liu:
> On Thu, Nov 08, 2012 at 01:37:15PM +0100, Stefani Seibold wrote:
> > 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.

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.

- Stefani

Re: [PATCH 1/2] kfifo: round up the fifo size power of 2

[Yuanhan Liu]

On Wed, Nov 14, 2012 at 08:03:49AM +0100, Stefani Seibold wrote:
> Am Freitag, den 09.11.2012, 10:32 +0800 schrieb Yuanhan Liu:
> > On Thu, Nov 08, 2012 at 01:37:15PM +0100, Stefani Seibold wrote:
> > > 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.
> 
> 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.

There are only 2 kfifo_init users: libiscsi.c and libsrp.c under
drivers/scsi/, and they are with same logic.

I propose to replace them with kfifo_alloc. I will make patch for
this later to see if scsi guys OK with it or not.  If OK, we can
remove kfifo_init.

	--yliu