linux-kernel - BUG REPORT - IDR wraps around at 30-bits

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 13 Aug 2013 12:31:29 +0530
From:	Shyam Kaushik <shyam@...arastorage.com>
To:	linux-kernel@...r.kernel.org
Subject: BUG REPORT - IDR wraps around at 30-bits - works very bad with NFSD/SCTP

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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/