Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Dan Carpenter]

On Mon, Jul 22, 2019 at 12:23:56PM +0800, laokz wrote:
> Hello,
> 
> A couple of weeks ago, I reported the respect author/maintainers. Haven't
> got reply yet, so I come here. 
> 
> The following is based on kernel 5.2-rc6.
> 
> include/linux/kfifo.h::kfifo_init() initialize a fifo using a preallocated
> buffer. It requests the buffer size should be power_of_two, if not so, the
> actual worker __kfifo_init() will round UP it to the next power of two. For
> it just records the new size in fifo's internal parameters, does not touch
> the real buffer, obviously this may introduce buffer overflow. 
> 
> In the source tree, I found an instance.
> 
> In drivers/scsi/ibmvscsi_tgt/libsrp.c::srp_iu_pool_alloc(), it calls
> kcalloc() and kfifo_init() with buffer size=max*sizeof(void
> *)=INITIAL_SRP_LIMIT*sizeof(void *), most likely be
> 800*8d00. That is NOT power of 2, KFIFO will treat it as 8192 big! Bad.
> 
> Here is its only call-chain:
>   #define INITIAL_SRP_LIMIT 800                       /* ibmvscsi_tgt.c */
>   ibmvscsis_probe()::vscsi->request_limit=INITIAL_SRP_LIMIT
>     -> srp_target_alloc(,vscsi->request_limit,)       /* libsrp.c */
>       ->srp_iu_pool_alloc(,nr,)                /* nr=vscsi->request_limit */
>         ->kfifo_init(,max*sizeof(void *),)     /* max=nr */
> 
> I know before kernel 3.9 __kfifo_init() algorithm was rounddown. I don't
> know why changed to roundup, but it is safe and more robust to rounddown
> instead of roundup.
> 
> If i'm wrong, please let me know also. Thanks.

It looks like you're right.  Probably the fix is to:
1) Change INITIAL_SRP_LIMIT to 8192
2) Change kfifo_init() to round down like you say
3) Add a WARN_ONCE() in kfifo_alloc and kfifo_init() if the size isn't
   a power of two.

regards,
dan carpenter

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Dan Carpenter]

On Mon, Jul 22, 2019 at 02:47:00PM +0300, Dan Carpenter wrote:
> On Mon, Jul 22, 2019 at 12:23:56PM +0800, laokz wrote:
> > Hello,
> > 
> > A couple of weeks ago, I reported the respect author/maintainers. Haven't
> > got reply yet, so I come here. 
> > 
> > The following is based on kernel 5.2-rc6.
> > 
> > include/linux/kfifo.h::kfifo_init() initialize a fifo using a preallocated
> > buffer. It requests the buffer size should be power_of_two, if not so, the
> > actual worker __kfifo_init() will round UP it to the next power of two. For
> > it just records the new size in fifo's internal parameters, does not touch
> > the real buffer, obviously this may introduce buffer overflow. 
> > 
> > In the source tree, I found an instance.
> > 
> > In drivers/scsi/ibmvscsi_tgt/libsrp.c::srp_iu_pool_alloc(), it calls
> > kcalloc() and kfifo_init() with buffer size=max*sizeof(void
> > *)=INITIAL_SRP_LIMIT*sizeof(void *), most likely be
> > 800*8d00. That is NOT power of 2, KFIFO will treat it as 8192 big! Bad.
> > 
> > Here is its only call-chain:
> >   #define INITIAL_SRP_LIMIT 800                       /* ibmvscsi_tgt.c */
> >   ibmvscsis_probe()::vscsi->request_limit=INITIAL_SRP_LIMIT
> >     -> srp_target_alloc(,vscsi->request_limit,)       /* libsrp.c */
> >       ->srp_iu_pool_alloc(,nr,)                /* nr=vscsi->request_limit */
> >         ->kfifo_init(,max*sizeof(void *),)     /* max=nr */
> > 
> > I know before kernel 3.9 __kfifo_init() algorithm was rounddown. I don't
> > know why changed to roundup, but it is safe and more robust to rounddown
> > instead of roundup.
> > 
> > If i'm wrong, please let me know also. Thanks.
> 
> It looks like you're right.  Probably the fix is to:
> 1) Change INITIAL_SRP_LIMIT to 8192

I meant 1024 not 8192.

regards,
dan carpenter

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Greg KH]

On Mon, Jul 22, 2019 at 09:26:23PM +0800, laokz wrote:
> Hello Dan,
> 
> On Mon, Jul 22, 2019 at 14:50 +0300，Dan Carpenter wrote:
> > > It looks like you're right.  Probably the fix is to:
> > > 1) Change INITIAL_SRP_LIMIT to 8192
> > 
> > I meant 1024 not 8192.
> 
> Nice to see that. It really helped for me. Thank you very much.

Did anything ever happen with this?  Was a patch submitted to resolve
this issue?

thanks,

greg k-h

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Kees Cook]

On Tue, Aug 06, 2019 at 06:27:13PM +0800, laokz wrote:
> On Fri, Aug 2, 2019 at 09:30 +0200，Greg KH wrote:
> > On Mon, Jul 22, 2019 at 09:26:23PM +0800, laokz wrote:
> > > Hello Dan,
> > > 
> > > On Mon, Jul 22, 2019 at 14:50 +0300，Dan Carpenter wrote:
> > > > > It looks like you're right.  Probably the fix is to:
> > > > > 1) Change INITIAL_SRP_LIMIT to 8192
> > > > 
> > > > I meant 1024 not 8192.
> > > 
> > > Nice to see that. It really helped for me. Thank you very much.
> > 
> > Did anything ever happen with this?  Was a patch submitted to resolve
> > this issue?
> Sorry for the late reply. I didn't submit any patch, for as newbie I wasn't
> quite sure about the severity of this issue. The developers may do their
> choice.

It's worth fixing regardless. :) Did a patch get sent for this?

-- 
Kees Cook

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Linus Torvalds]

On Tue, Aug 6, 2019 at 3:29 AM laokz <laokz@foxmail.com> wrote:
>
> Sorry for the late reply. I didn't submit any patch, for as newbie I wasn't
> quite sure about the severity of this issue. The developers may do their
> choice.

It does seem pretty bad.

Also, INIT_KFIFO() and DECLARE_KFIFO() should probably have a

     BUILD_BUG_ON(!__is_kfifo_ptr && !is_power_of_2(ARRAY_SIZE(__tmp->buf)));

or something. Probably worth indirection through a helper macro to set
the ".mask" field.

And yes, commit dfe2a77fd243 ("kfifo: fix kfifo_alloc() and
kfifo_init()") seems wrong, It's fine for the __kfifo_alloc() case
where we actually allocate the rounded-up size, but it's completely
wrong for the __kfifo_init() case where somebody _else_ allocated the
size.

So the kfifo_init() case needs to just use a round_down, and possibly
add a WARN_ON_ONCE() too.

Anybody?

             Linus

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 194 bytes --]

On Thu, Aug 29, 2019 at 11:48 AM Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Anybody?

This is ENTIRELY UNTESTED.

Anybody willing to test and take ownership?

              Linus

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 1915 bytes --]

 include/linux/kfifo.h | 12 ++++++++----
 lib/kfifo.c           |  4 +++-
 2 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/include/linux/kfifo.h b/include/linux/kfifo.h
index fc4b0b10210f..078f52c20aad 100644
--- a/include/linux/kfifo.h
+++ b/include/linux/kfifo.h
@@ -117,6 +117,12 @@ struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);
  */
 #define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo
 
+#define VERIFY_POWER_OF2(x) \
+	((x)+BUILD_BUG_ON_ZERO((x) & ((x)-1)))
+
+#define __KFIFO_MASK_SIZE(fifo) \
+	(__is_kfifo_ptr(&(fifo)) ? 0 : VERIFY_POWER_OF2(ARRAY_SIZE((fifo).buf)) - 1)
+
 /**
  * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
  * @fifo: name of the declared fifo datatype
@@ -127,7 +133,7 @@ struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);
 	struct __kfifo *__kfifo = &__tmp->kfifo; \
 	__kfifo->in = 0; \
 	__kfifo->out = 0; \
-	__kfifo->mask = __is_kfifo_ptr(__tmp) ? 0 : ARRAY_SIZE(__tmp->buf) - 1;\
+	__kfifo->mask = __KFIFO_MASK_SIZE(fifo); \
 	__kfifo->esize = sizeof(*__tmp->buf); \
 	__kfifo->data = __is_kfifo_ptr(__tmp) ?  NULL : __tmp->buf; \
 })
@@ -147,9 +153,7 @@ struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);
 			{ \
 			.in	= 0, \
 			.out	= 0, \
-			.mask	= __is_kfifo_ptr(&(fifo)) ? \
-				  0 : \
-				  ARRAY_SIZE((fifo).buf) - 1, \
+			.mask	= __KFIFO_MASK_SIZE(fifo), \
 			.esize	= sizeof(*(fifo).buf), \
 			.data	= __is_kfifo_ptr(&(fifo)) ? \
 				NULL : \
diff --git a/lib/kfifo.c b/lib/kfifo.c
index 117ad0e7fbf4..7f145cb41e6d 100644
--- a/lib/kfifo.c
+++ b/lib/kfifo.c
@@ -68,7 +68,9 @@ int __kfifo_init(struct __kfifo *fifo, void *buffer,
 {
 	size /= esize;
 
-	size = roundup_pow_of_two(size);
+	/* Warn because we had a bug here and would round up */
+	if (WARN_ON_ONCE(!is_power_of_2(size)))
+		size = rounddown_pow_of_two(size);
 
 	fifo->in = 0;
 	fifo->out = 0;

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Stefani Seibold]

Hi Linus,

i am back from vacation next week. I will have a look on it.

Stefani

Am Donnerstag, den 29.08.2019, 12:32 -0700 schrieb Linus Torvalds:
> On Thu, Aug 29, 2019 at 11:48 AM Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> > Anybody?
> 
> This is ENTIRELY UNTESTED.
> 
> Anybody willing to test and take ownership?
> 
>               Linus

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Kees Cook]

On Thu, Aug 29, 2019 at 12:32:41PM -0700, Linus Torvalds wrote:
> On Thu, Aug 29, 2019 at 11:48 AM Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >
> > Anybody?
> 
> This is ENTIRELY UNTESTED.
> 
> Anybody willing to test and take ownership?

I don't know this code at all, but note below...

> 
>               Linus

>  include/linux/kfifo.h | 12 ++++++++----
>  lib/kfifo.c           |  4 +++-
>  2 files changed, 11 insertions(+), 5 deletions(-)
> 
> diff --git a/include/linux/kfifo.h b/include/linux/kfifo.h
> index fc4b0b10210f..078f52c20aad 100644
> --- a/include/linux/kfifo.h
> +++ b/include/linux/kfifo.h
> @@ -117,6 +117,12 @@ struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);
>   */
>  #define DECLARE_KFIFO(fifo, type, size)	STRUCT_KFIFO(type, size) fifo
>  
> +#define VERIFY_POWER_OF2(x) \
> +	((x)+BUILD_BUG_ON_ZERO((x) & ((x)-1)))
> +
> +#define __KFIFO_MASK_SIZE(fifo) \
> +	(__is_kfifo_ptr(&(fifo)) ? 0 : VERIFY_POWER_OF2(ARRAY_SIZE((fifo).buf)) - 1)
> +
>  /**
>   * INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO
>   * @fifo: name of the declared fifo datatype
> @@ -127,7 +133,7 @@ struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);
>  	struct __kfifo *__kfifo = &__tmp->kfifo; \
>  	__kfifo->in = 0; \
>  	__kfifo->out = 0; \
> -	__kfifo->mask = __is_kfifo_ptr(__tmp) ? 0 : ARRAY_SIZE(__tmp->buf) - 1;\
> +	__kfifo->mask = __KFIFO_MASK_SIZE(fifo); \

I think this should be:

+	__kfifo->mask = __KFIFO_MASK_SIZE(*__tmp); \

? I didn't compile it, but I saw the others were using (fifo).buf but
this was using __tmp->buf.

>  	__kfifo->esize = sizeof(*__tmp->buf); \
>  	__kfifo->data = __is_kfifo_ptr(__tmp) ?  NULL : __tmp->buf; \
>  })
> @@ -147,9 +153,7 @@ struct kfifo_rec_ptr_2 __STRUCT_KFIFO_PTR(unsigned char, 2, void);
>  			{ \
>  			.in	= 0, \
>  			.out	= 0, \
> -			.mask	= __is_kfifo_ptr(&(fifo)) ? \
> -				  0 : \
> -				  ARRAY_SIZE((fifo).buf) - 1, \
> +			.mask	= __KFIFO_MASK_SIZE(fifo), \
>  			.esize	= sizeof(*(fifo).buf), \
>  			.data	= __is_kfifo_ptr(&(fifo)) ? \
>  				NULL : \
> diff --git a/lib/kfifo.c b/lib/kfifo.c
> index 117ad0e7fbf4..7f145cb41e6d 100644
> --- a/lib/kfifo.c
> +++ b/lib/kfifo.c
> @@ -68,7 +68,9 @@ int __kfifo_init(struct __kfifo *fifo, void *buffer,
>  {
>  	size /= esize;
>  
> -	size = roundup_pow_of_two(size);
> +	/* Warn because we had a bug here and would round up */
> +	if (WARN_ON_ONCE(!is_power_of_2(size)))
> +		size = rounddown_pow_of_two(size);
>  
>  	fifo->in = 0;
>  	fifo->out = 0;


-- 
Kees Cook

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Will Deacon]

On Thu, Aug 29, 2019 at 01:00:21PM -0700, Linus Torvalds wrote:
> [ at the dentist, sorry for mobile html gunk ]
> 
> On Thu, Aug 29, 2019, 12:42 Kees Cook <keescook@chromium.org> wrote:
> 
>     On Thu, 
> 
>     I don't know this code at all, but note below...
> 
>     > +     __kfifo->mask = __KFIFO_MASK_SIZE(fifo); \
> 
>     I think this should be:
> 
>     +       __kfifo->mask = __KFIFO_MASK_SIZE(*__tmp); \
> 
>     ? 
> 
> 
> If it matters, we're in deep doo-doo. It only uses the type of the thing, not
> the value, so it's immaterial. I think it's easier to use the original type
> rather than the temporary that we created using it..
> 
> But that's the least of my worries in that code.

If it makes you feel any better [perhaps as a distraction from the dreaded
dentist], the memory ordering side of things is suspicious as well:

https://lore.kernel.org/lkml/CAGXu5jKkqf-9ksvNTCS5xgB_JtfvCc=Eot2uWYYP8rpoKLw=mg@mail.gmail.com/

When I started pulling on it, it all fell apart, so I haven't had a
chance to do a proper set of fixes.

Will

Re: Bug report: KFIFO kfifo_init() may introduce buffer overflow

[Linus Torvalds]

On Sun, Sep 1, 2019 at 10:11 AM laokz <laokz@foxmail.com> wrote:
>
> At first glance, I thought this issue was serious, based on user space
> experience. Later I realized it may be trivial in kernel space, for kmalloc
> also using roundup_power_of_2 algorithm through SLAB/SLUB.

No, there are definitely slab sizes that aren't always powers of two.

It may be that almost by mistake, the particular one problem you point
out (ibmvscsi_tgt) ends up having its allocation grown to a power of
two, so it's not a problem in practice, but you definitely found a
bug.

I ended up doing a minimal half-revert in commit ab9bb6318b09
("Partially revert "kfifo: fix kfifo_alloc() and kfifo_init()"") which
fixes the basic problem.

> > Also, INIT_KFIFO() and DECLARE_KFIFO() should probably have a
> >
> >      BUILD_BUG_ON(!__is_kfifo_ptr && !is_power_of_2(ARRAY_SIZE(__tmp-
> > >buf)));
> >
> > or something. Probably worth indirection through a helper macro to set
> > the ".mask" field.
>
> Now, I learned that actual scenario may be more complex and uncontrollable
> in some degree, supposing this issue had a statically allocated buffer. So,
> it's worth to use least cost to keep kernel from potential damage.

It turns out that DECLARE_KFIFO ends up protecting against bad kfifo
sizes, because __STRUCT_KFIFO() does this:

        type            buf[((size < 2) || (size & (size - 1))) ? -1 : size]; \

which is making sure that size is at least 2 and a power-of-two. If it
isn't, the compiler will error out due to a negative array size thanks
to that check.

So it's _probably_ the case that the only actual problem was
kfifo_init() itself. And yes, it's quite possible that the only user
that didn't use a power of two ended up having SLAB round that
allocation up for the size it *did* use.

But your bug report was valid, and I'd love you to double-check all
this. Code that just happens to work by mistake is still a serious bug
waiting to happen.

Thanks,

             Linus