linux-kernel - Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

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-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <201712231159.ECI73411.tFFFJOHOVMOLQS@I-love.SAKURA.ne.jp>
Date:   Sat, 23 Dec 2017 11:59:54 +0900
From:   Tetsuo Handa <penguin-kernel@...ove.SAKURA.ne.jp>
To:     willy@...radead.org, wei.w.wang@...el.com
Cc:     virtio-dev@...ts.oasis-open.org, linux-kernel@...r.kernel.org,
        qemu-devel@...gnu.org, virtualization@...ts.linux-foundation.org,
        kvm@...r.kernel.org, linux-mm@...ck.org, mst@...hat.com,
        mhocko@...nel.org, akpm@...ux-foundation.org,
        mawilcox@...rosoft.com
Subject: Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

Matthew Wilcox wrote:
> +/**
> + * xb_set_bit() - Set a bit in the XBitmap.
> + * @xb: The XBitmap.
> + * @bit: Index of the bit to set.
> + *
> + * This function is used to set a bit in the xbitmap.
> + *
> + * Return: 0 on success. -ENOMEM if memory could not be allocated.
> + */
> +int xb_set_bit(struct xb *xb, unsigned long bit)
> +{
> +	unsigned long index = bit / IDA_BITMAP_BITS;
> +	struct radix_tree_root *root = &xb->xbrt;
> +	struct radix_tree_iter iter;
> +	void __rcu **slot;
> +	struct ida_bitmap *bitmap;
> +
> +	bit %= IDA_BITMAP_BITS;
> +	radix_tree_iter_init(&iter, index);
> +	slot = idr_get_free_cmn(root, &iter, GFP_NOWAIT | __GFP_NOWARN, index);
> +	if (IS_ERR(slot)) {
> +		if (slot == ERR_PTR(-ENOSPC))
> +			return 0;	/* Already set */

Why already set? I guess something is there, but is it guaranteed that
there is a bitmap with the "bit" set?

> +		return -ENOMEM;
> +	}
> +	bitmap = rcu_dereference_raw(*slot);
> +	if (!bitmap) {
> +		bitmap = this_cpu_xchg(ida_bitmap, NULL);
> +		if (!bitmap)
> +			return -ENOMEM;

I can't understand this. I can understand if it were

  BUG_ON(!bitmap);

because you called xb_preload().

But

	/*
	 * Regular test 2
	 * set bit 2000, 2001, 2040
	 * Next 1 in [0, 2048)		--> 2000
	 * Next 1 in [2000, 2002)	--> 2000
	 * Next 1 in [2002, 2041)	--> 2040
	 * Next 1 in [2002, 2040)	--> none
	 * Next 0 in [2000, 2048)	--> 2002
	 * Next 0 in [2048, 2060)	--> 2048
	 */
	xb_preload(GFP_KERNEL);
	assert(!xb_set_bit(&xb1, 2000));
	assert(!xb_set_bit(&xb1, 2001));
	assert(!xb_set_bit(&xb1, 2040));
	nbit = 0;
	assert(xb_find_set(&xb1, 2048, &nbit) == true);
	assert(nbit == 2000);
	assert(xb_find_set(&xb1, 2002, &nbit) == true);
	assert(nbit == 2000);
	nbit = 2002;
	assert(xb_find_set(&xb1, 2041, &nbit) == true);
	assert(nbit == 2040);
	nbit = 2002;
	assert(xb_find_set(&xb1, 2040, &nbit) == true);
	assert(nbit == 2040);
	nbit = 2000;
	assert(xb_find_zero(&xb1, 2048, &nbit) == true);
	assert(nbit == 2002);
	nbit = 2048;
	assert(xb_find_zero(&xb1, 2060, &nbit) == true);
	assert(nbit == 2048);
	xb_zero(&xb1, 0, 2047);
	nbit = 0;
	assert(xb_find_set(&xb1, 2048, &nbit) == false);
	assert(nbit == 0);
	xb_preload_end();

you are not calling xb_preload() prior to each xb_set_bit() call.
This means that, if each xb_set_bit() is not surrounded with
xb_preload()/xb_preload_end(), there is possibility of hitting
this_cpu_xchg(ida_bitmap, NULL) == NULL.

If bitmap == NULL at this_cpu_xchg(ida_bitmap, NULL) is allowed,
you can use kzalloc(sizeof(*bitmap), GFP_NOWAIT | __GFP_NOWARN)
and get rid of xb_preload()/xb_preload_end().

You are using idr_get_free_cmn(GFP_NOWAIT | __GFP_NOWARN), which
means that the caller has to be prepared for allocation failure
when calling xb_set_bit(). Thus, there is no need to use preload
in order to avoid failing to allocate "bitmap".



Also, please clarify why it is OK to just return here.
I don't know what

  radix_tree_iter_replace(root, &iter, slot, bitmap);

is doing. If you created a slot but did not assign "bitmap",
what the caller of xb_test_bit() etc. will find? If there is an
assumption about this slot, won't this cause a problem?

> +		memset(bitmap, 0, sizeof(*bitmap));
> +		radix_tree_iter_replace(root, &iter, slot, bitmap);
> +	}
> +
> +	__set_bit(bit, bitmap->bitmap);
> +	if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
> +		radix_tree_iter_tag_clear(root, &iter, IDR_FREE);
> +	return 0;
> +}