BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Shyam Kaushik]

Hi Folks,

We are using Ubuntu linux kernel 3.2.0-25-generic & 3.8.13-030813-generic
in our environments, but I think this bug is still present in mainline
kernel. Clients of IDR rollover at MAX_INT (NFSD & SCTP in kernel do this)
& others on MAX_IDR_MASK. This is ideally 2^31. But there is some BUG
within IDR that it wraps over at 2^30.

NFSD uses IDR for maintaining its stateids & tracks min_stateid with a
static variable which keeps incrementing. So over a period of time NFSD
could run into the issue that it allocates an ID with IDR, but IDR cant
locate this ID, resulting in NFSD constantly sending BAD_STATEIDS to all
its clients.

Following short driver (which closely resembles NFSD usage of IDR) shows
the BUG within IDR:

#include <linux/module.h>
#include <linux/init.h>
#include <linux/version.h>
#include <linux/idr.h>

static int log_idr_entry(int id, void *ptr, void *data)
{
        int     *expected_val = (int *)ptr;

        pr_info("\tIDR Actual ID[%d] %s Expected Value[%d]\n", id, (id ==
*expected_val)?"==":"!=", *expected_val);
        return 0;
}

static void process_idr_entry(struct idr *stateids, int min_stateid)
{
        int             new_stid;
        int             error;

        pr_info("\nProcessing for min_stateid[%d]\n", min_stateid);
        if (!idr_pre_get(stateids, GFP_KERNEL)) {
                pr_info("Failed to pre-get\n");
                return;
        }

        error = idr_get_new_above(stateids, &new_stid, min_stateid,
&new_stid);
        if (error) {
                pr_info("Failed to get new id\n");
                idr_remove(stateids, new_stid);
                return;
        }

        pr_info("Allocated new_stid[%d]\n", new_stid);

        if (!idr_find(stateids, new_stid))
                pr_info("BUG: Cant find ID[%d]\n", new_stid);

        pr_info("Dumping entries in IDR\n");
        idr_for_each(stateids, &log_idr_entry, NULL);
        idr_remove(stateids, new_stid);
}

void driver_exit(void)
{
}

int driver_init(void)
{
        struct idr      stateids;

        pr_info("%d\n", MAX_INT);
        idr_init(&stateids);
        process_idr_entry(&stateids, 0/*min_stateid*/);
        process_idr_entry(&stateids, 1073741823/*min_stateid*/);
        process_idr_entry(&stateids, 1073741824/*min_stateid*/);
        idr_remove_all(&stateids);
        idr_destroy(&stateids);
        return 0;
}

module_init(driver_init);
module_exit(driver_exit);


Upon loading the driver, the following message shows up
[71641.440846] Processing for min_stateid[0]
[71641.440857] Allocated new_stid[0]
[71641.440859] Dumping entries in IDR
[71641.440861]  IDR Actual ID[0] == Expected Value[0]
[71641.440864]
[71641.440864] Processing for min_stateid[1073741823]
[71641.440867] Allocated new_stid[1073741823]
[71641.440868] Dumping entries in IDR
[71641.440876]  IDR Actual ID[1073741823] == Expected Value[1073741823]
[71641.440878]
[71641.440878] Processing for min_stateid[1073741824]
[71641.440883] Allocated new_stid[1073741824]
[71641.440884] BUG: Cant find ID[1073741824]
[71641.440886] Dumping entries in IDR
[71641.440887]  IDR Actual ID[0] != Expected Value[1073741824]

i.e. when we allocate a stated==1073741824, IDR internally has it as 0.

--Shyam

Re: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Greg KH]

On Tue, Aug 13, 2013 at 12:31:29PM +0530, Shyam Kaushik wrote:
> Hi Folks,
> 
> We are using Ubuntu linux kernel 3.2.0-25-generic & 3.8.13-030813-generic
> in our environments, but I think this bug is still present in mainline
> kernel. Clients of IDR rollover at MAX_INT (NFSD & SCTP in kernel do this)
> & others on MAX_IDR_MASK. This is ideally 2^31. But there is some BUG
> within IDR that it wraps over at 2^30.
> 
> NFSD uses IDR for maintaining its stateids & tracks min_stateid with a
> static variable which keeps incrementing. So over a period of time NFSD
> could run into the issue that it allocates an ID with IDR, but IDR cant
> locate this ID, resulting in NFSD constantly sending BAD_STATEIDS to all
> its clients.
> 
> Following short driver (which closely resembles NFSD usage of IDR) shows
> the BUG within IDR:

The IDR code was rewritten very recently (3.9 or 3.10), so could you
test 3.10.6 out and let us know if this is still an issue there?  And if
so, cc: the idr developers (on cc:) would help out a lot.

Example left below for them...

thanks,

greg k-h

> 
> #include <linux/module.h>
> #include <linux/init.h>
> #include <linux/version.h>
> #include <linux/idr.h>
> 
> static int log_idr_entry(int id, void *ptr, void *data)
> {
>         int     *expected_val = (int *)ptr;
> 
>         pr_info("\tIDR Actual ID[%d] %s Expected Value[%d]\n", id, (id ==
> *expected_val)?"==":"!=", *expected_val);
>         return 0;
> }
> 
> static void process_idr_entry(struct idr *stateids, int min_stateid)
> {
>         int             new_stid;
>         int             error;
> 
>         pr_info("\nProcessing for min_stateid[%d]\n", min_stateid);
>         if (!idr_pre_get(stateids, GFP_KERNEL)) {
>                 pr_info("Failed to pre-get\n");
>                 return;
>         }
> 
>         error = idr_get_new_above(stateids, &new_stid, min_stateid,
> &new_stid);
>         if (error) {
>                 pr_info("Failed to get new id\n");
>                 idr_remove(stateids, new_stid);
>                 return;
>         }
> 
>         pr_info("Allocated new_stid[%d]\n", new_stid);
> 
>         if (!idr_find(stateids, new_stid))
>                 pr_info("BUG: Cant find ID[%d]\n", new_stid);
> 
>         pr_info("Dumping entries in IDR\n");
>         idr_for_each(stateids, &log_idr_entry, NULL);
>         idr_remove(stateids, new_stid);
> }
> 
> void driver_exit(void)
> {
> }
> 
> int driver_init(void)
> {
>         struct idr      stateids;
> 
>         pr_info("%d\n", MAX_INT);
>         idr_init(&stateids);
>         process_idr_entry(&stateids, 0/*min_stateid*/);
>         process_idr_entry(&stateids, 1073741823/*min_stateid*/);
>         process_idr_entry(&stateids, 1073741824/*min_stateid*/);
>         idr_remove_all(&stateids);
>         idr_destroy(&stateids);
>         return 0;
> }
> 
> module_init(driver_init);
> module_exit(driver_exit);
> 
> 
> Upon loading the driver, the following message shows up
> [71641.440846] Processing for min_stateid[0]
> [71641.440857] Allocated new_stid[0]
> [71641.440859] Dumping entries in IDR
> [71641.440861]  IDR Actual ID[0] == Expected Value[0]
> [71641.440864]
> [71641.440864] Processing for min_stateid[1073741823]
> [71641.440867] Allocated new_stid[1073741823]
> [71641.440868] Dumping entries in IDR
> [71641.440876]  IDR Actual ID[1073741823] == Expected Value[1073741823]
> [71641.440878]
> [71641.440878] Processing for min_stateid[1073741824]
> [71641.440883] Allocated new_stid[1073741824]
> [71641.440884] BUG: Cant find ID[1073741824]
> [71641.440886] Dumping entries in IDR
> [71641.440887]  IDR Actual ID[0] != Expected Value[1073741824]
> 
> i.e. when we allocate a stated==1073741824, IDR internally has it as 0.
> 
> --Shyam
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

RE: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Shyam Kaushik]

Hi Greg,

Unfortunately we don’t have a 3.9/3.10 environment here. So if IDR
developers can try the example code, it should show if the bug is still
present in there. Thanks.

--Shyam

-----Original Message-----
From: Greg KH [mailto:gregkh@linuxfoundation.org]
Sent: Tuesday, August 13, 2013 12:50 PM
To: Shyam Kaushik
Cc: Tejun Heo; Andrew Morton; linux-kernel@vger.kernel.org
Subject: Re: BUG REPORT - IDR wraps around at 30-bits - works very bad
with NFSD/SCTP

On Tue, Aug 13, 2013 at 12:31:29PM +0530, Shyam Kaushik wrote:
> Hi Folks,
>
> We are using Ubuntu linux kernel 3.2.0-25-generic &
3.8.13-030813-generic
> in our environments, but I think this bug is still present in mainline
> kernel. Clients of IDR rollover at MAX_INT (NFSD & SCTP in kernel do
this)
> & others on MAX_IDR_MASK. This is ideally 2^31. But there is some BUG
> within IDR that it wraps over at 2^30.
>
> NFSD uses IDR for maintaining its stateids & tracks min_stateid with a
> static variable which keeps incrementing. So over a period of time NFSD
> could run into the issue that it allocates an ID with IDR, but IDR cant
> locate this ID, resulting in NFSD constantly sending BAD_STATEIDS to all
> its clients.
>
> Following short driver (which closely resembles NFSD usage of IDR) shows
> the BUG within IDR:

The IDR code was rewritten very recently (3.9 or 3.10), so could you
test 3.10.6 out and let us know if this is still an issue there?  And if
so, cc: the idr developers (on cc:) would help out a lot.

Example left below for them...

thanks,

greg k-h

>
> #include <linux/module.h>
> #include <linux/init.h>
> #include <linux/version.h>
> #include <linux/idr.h>
>
> static int log_idr_entry(int id, void *ptr, void *data)
> {
>         int     *expected_val = (int *)ptr;
>
>         pr_info("\tIDR Actual ID[%d] %s Expected Value[%d]\n", id, (id
==
> *expected_val)?"==":"!=", *expected_val);
>         return 0;
> }
>
> static void process_idr_entry(struct idr *stateids, int min_stateid)
> {
>         int             new_stid;
>         int             error;
>
>         pr_info("\nProcessing for min_stateid[%d]\n", min_stateid);
>         if (!idr_pre_get(stateids, GFP_KERNEL)) {
>                 pr_info("Failed to pre-get\n");
>                 return;
>         }
>
>         error = idr_get_new_above(stateids, &new_stid, min_stateid,
> &new_stid);
>         if (error) {
>                 pr_info("Failed to get new id\n");
>                 idr_remove(stateids, new_stid);
>                 return;
>         }
>
>         pr_info("Allocated new_stid[%d]\n", new_stid);
>
>         if (!idr_find(stateids, new_stid))
>                 pr_info("BUG: Cant find ID[%d]\n", new_stid);
>
>         pr_info("Dumping entries in IDR\n");
>         idr_for_each(stateids, &log_idr_entry, NULL);
>         idr_remove(stateids, new_stid);
> }
>
> void driver_exit(void)
> {
> }
>
> int driver_init(void)
> {
>         struct idr      stateids;
>
>         pr_info("%d\n", MAX_INT);
>         idr_init(&stateids);
>         process_idr_entry(&stateids, 0/*min_stateid*/);
>         process_idr_entry(&stateids, 1073741823/*min_stateid*/);
>         process_idr_entry(&stateids, 1073741824/*min_stateid*/);
>         idr_remove_all(&stateids);
>         idr_destroy(&stateids);
>         return 0;
> }
>
> module_init(driver_init);
> module_exit(driver_exit);
>
>
> Upon loading the driver, the following message shows up
> [71641.440846] Processing for min_stateid[0]
> [71641.440857] Allocated new_stid[0]
> [71641.440859] Dumping entries in IDR
> [71641.440861]  IDR Actual ID[0] == Expected Value[0]
> [71641.440864]
> [71641.440864] Processing for min_stateid[1073741823]
> [71641.440867] Allocated new_stid[1073741823]
> [71641.440868] Dumping entries in IDR
> [71641.440876]  IDR Actual ID[1073741823] == Expected Value[1073741823]
> [71641.440878]
> [71641.440878] Processing for min_stateid[1073741824]
> [71641.440883] Allocated new_stid[1073741824]
> [71641.440884] BUG: Cant find ID[1073741824]
> [71641.440886] Dumping entries in IDR
> [71641.440887]  IDR Actual ID[0] != Expected Value[1073741824]
>
> i.e. when we allocate a stated==1073741824, IDR internally has it as 0.
>
> --Shyam
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel"
in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.2904 / Virus Database: 3211/6571 - Release Date: 08/12/13

Re: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Greg KH]

On Tue, Aug 13, 2013 at 12:51:14PM +0530, Shyam Kaushik wrote:
> Hi Greg,
> 
> Unfortunately we don’t have a 3.9/3.10 environment here. So if IDR
> developers can try the example code, it should show if the bug is still
> present in there. Thanks.

There shouldn't be anything in 3.10 preventing you from building and
testing it out, is there?  Or do you have something that restricts you
to specific kernel versions?

thanks,

greg k-h

Re: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Greg KH]

On Tue, Aug 13, 2013 at 12:31:29PM +0530, Shyam Kaushik wrote:
>         pr_info("%d\n", MAX_INT);

How did this line build, there is no MAX_INT in the kernel tree.

odd.

greg k-h

RE: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Shyam Kaushik]

Sorry I added this later, but realized I couldn’t compile.

Working version of the example is

#include <linux/module.h>
#include <linux/init.h>
#include <linux/version.h>
#include <linux/idr.h>

static int log_idr_entry(int id, void *ptr, void *data)
{
        int     *expected_val = (int *)ptr;

        pr_info("\tIDR Actual ID[%d] %s Expected Value[%d]\n", id, (id ==
*expected_val)?"==":"!=", *expected_val);
        return 0;
}

static void process_idr_entry(struct idr *stateids, int min_stateid)
{
        int             new_stid;
        int             error;

        pr_info("\nProcessing for min_stateid[%d]\n", min_stateid);
        if (!idr_pre_get(stateids, GFP_KERNEL)) {
                pr_info("Failed to pre-get\n");
                return;
        }

        error = idr_get_new_above(stateids, &new_stid, min_stateid,
&new_stid);
        if (error) {
                pr_info("Failed to get new id\n");
                idr_remove(stateids, new_stid);
                return;
        }

        pr_info("Allocated new_stid[%d]\n", new_stid);

        if (!idr_find(stateids, new_stid))
                pr_info("BUG: Cant find ID[%d]\n", new_stid);

        pr_info("Dumping entries in IDR\n");
        idr_for_each(stateids, &log_idr_entry, NULL);
        idr_remove(stateids, new_stid);
}

void driver_exit(void)
{
}

int driver_init(void)
{
        struct idr      stateids;

        idr_init(&stateids);
        process_idr_entry(&stateids, 0/*min_stateid*/);
        process_idr_entry(&stateids, 1073741823/*min_stateid*/);
        process_idr_entry(&stateids, 1073741824/*min_stateid*/);
        idr_remove_all(&stateids);
        idr_destroy(&stateids);
        return 0;
}

module_init(driver_init);
module_exit(driver_exit);

-----Original Message-----
From: Greg KH [mailto:gregkh@linuxfoundation.org]
Sent: Tuesday, August 13, 2013 1:03 PM
To: Shyam Kaushik
Cc: linux-kernel@vger.kernel.org
Subject: Re: BUG REPORT - IDR wraps around at 30-bits - works very bad
with NFSD/SCTP

On Tue, Aug 13, 2013 at 12:31:29PM +0530, Shyam Kaushik wrote:
>         pr_info("%d\n", MAX_INT);

How did this line build, there is no MAX_INT in the kernel tree.

odd.

greg k-h

-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.2904 / Virus Database: 3211/6571 - Release Date: 08/12/13

RE: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Shyam Kaushik]

It was just more time from me on this:-) But anyways since you wanted I
tried.

I tested 3.10.6-031006-generic & it works perfect in there!

[  832.513688] Processing for min_stateid[0]
[  832.513701] Allocated new_stid[0]
[  832.513703] Dumping entries in IDR
[  832.513705]  IDR Actual ID[0] == Expected Value[0]
[  832.513710]
[  832.513710] Processing for min_stateid[1073741823]
[  832.513713] Allocated new_stid[1073741823]
[  832.513714] Dumping entries in IDR
[  832.513729]  IDR Actual ID[1073741823] == Expected Value[1073741823]
[  832.513731]
[  832.513731] Processing for min_stateid[1073741824]
[  832.513736] Allocated new_stid[1073741824]
[  832.513737] Dumping entries in IDR
[  832.513739]  IDR Actual ID[1073741824] == Expected Value[1073741824]
[  832.513754]
[  832.513754] Processing for min_stateid[2147483647]
[  832.513763] Allocated new_stid[2147483647]
[  832.513765] Dumping entries in IDR
[  832.513779]  IDR Actual ID[2147483647] == Expected Value[2147483647]

Any chances of backporting some parts of fix to <3.9 kernels?

Thanks.

--Shyam

-----Original Message-----
From: Greg KH [mailto:gregkh@linuxfoundation.org]
Sent: Tuesday, August 13, 2013 12:56 PM
To: Shyam Kaushik
Cc: Tejun Heo; Andrew Morton; linux-kernel@vger.kernel.org
Subject: Re: BUG REPORT - IDR wraps around at 30-bits - works very bad
with NFSD/SCTP

On Tue, Aug 13, 2013 at 12:51:14PM +0530, Shyam Kaushik wrote:
> Hi Greg,
>
> Unfortunately we don't have a 3.9/3.10 environment here. So if IDR
> developers can try the example code, it should show if the bug is still
> present in there. Thanks.

There shouldn't be anything in 3.10 preventing you from building and
testing it out, is there?  Or do you have something that restricts you
to specific kernel versions?

thanks,

greg k-h

-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2013.0.2904 / Virus Database: 3211/6571 - Release Date: 08/12/13

Re: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

[Tejun Heo]

Hello,

On Tue, Aug 13, 2013 at 01:21:12PM +0530, Shyam Kaushik wrote:
> Any chances of backporting some parts of fix to <3.9 kernels?

For kernels which are too old for -stable, backporting is up to the
distros which hopefully are still maintaining the kernel (you really
don't want to run an unmaintained distro anyway).  The IDR changes
shouldn't be difficult to pick up and the best way to make that happen
would be filing a bug with the distro.

Thanks.

-- 
tejun