linux-kernel - Re: [PATCH v19 3/7] 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]
Date:   Wed, 13 Dec 2017 20:26:06 +0800
From:   Wei Wang <wei.w.wang@...el.com>
To:     Tetsuo Handa <penguin-kernel@...ove.SAKURA.ne.jp>,
        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
CC:     david@...hat.com, cornelia.huck@...ibm.com,
        mgorman@...hsingularity.net, aarcange@...hat.com,
        amit.shah@...hat.com, pbonzini@...hat.com, willy@...radead.org,
        liliang.opensource@...il.com, yang.zhang.wz@...il.com,
        quan.xu@...yun.com, nilal@...hat.com, riel@...hat.com
Subject: Re: [PATCH v19 3/7] xbitmap: add more operations

On 12/12/2017 09:20 PM, Tetsuo Handa wrote:
> Wei Wang wrote:
>> +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end)
>> +{
>> +	struct radix_tree_root *root = &xb->xbrt;
>> +	struct radix_tree_node *node;
>> +	void **slot;
>> +	struct ida_bitmap *bitmap;
>> +	unsigned int nbits;
>> +
>> +	for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
>> +		unsigned long index = start / IDA_BITMAP_BITS;
>> +		unsigned long bit = start % IDA_BITMAP_BITS;
>> +
>> +		bitmap = __radix_tree_lookup(root, index, &node, &slot);
>> +		if (radix_tree_exception(bitmap)) {
>> +			unsigned long ebit = bit + 2;
>> +			unsigned long tmp = (unsigned long)bitmap;
>> +
>> +			nbits = min(end - start + 1, BITS_PER_LONG - ebit);
>> +
>> +			if (ebit >= BITS_PER_LONG)
> What happens if we hit this "continue;" when "index == ULONG_MAX / IDA_BITMAP_BITS" ?

Thanks. I also improved the test case for this. I plan to change the 
implementation a little bit to avoid such overflow (has passed the test 
case that I have, just post out for another set of eyes):

{
...
         unsigned long idx = start / IDA_BITMAP_BITS;
         unsigned long bit = start % IDA_BITMAP_BITS;
         unsigned long idx_end = end / IDA_BITMAP_BITS;
         unsigned long ret;

         for (idx = start / IDA_BITMAP_BITS; idx <= idx_end; idx++) {
                 unsigned long ida_start = idx * IDA_BITMAP_BITS;

                 bitmap = __radix_tree_lookup(root, idx, &node, &slot);
                 if (radix_tree_exception(bitmap)) {
                         unsigned long tmp = (unsigned long)bitmap;
                         unsigned long ebit = bit + 2;

                         if (ebit >= BITS_PER_LONG)
                                 continue;
                         if (set)
                                 ret = find_next_bit(&tmp, 
BITS_PER_LONG, ebit);
                         else
                                 ret = find_next_zero_bit(&tmp, 
BITS_PER_LONG,
                                                          ebit);
                         if (ret < BITS_PER_LONG)
                                 return ret - 2 + ida_start;
                 } else if (bitmap) {
                         if (set)
                                 ret = find_next_bit(bitmap->bitmap,
                                                     IDA_BITMAP_BITS, bit);
                         else
                                 ret = find_next_zero_bit(bitmap->bitmap,
IDA_BITMAP_BITS, bit);
                         if (ret < IDA_BITMAP_BITS)
                                 return ret + ida_start;
                 } else if (!bitmap && !set) {
                         return bit + IDA_BITMAP_BITS * idx;
                 }
                 bit = 0;
         }

         return end;
}


>
> Can you eliminate exception path and fold all xbitmap patches into one, and
> post only one xbitmap patch without virtio-baloon changes? If exception path
> is valuable, you can add exception path after minimum version is merged.
> This series is too difficult for me to close corner cases.

That exception path is claimed to save memory, and I don't have a strong 
reason to remove that part.
Matthew, could we get your feedback on this?



>
>> +/**
>> + * xb_find_next_set_bit - find the next set bit in a range
>> + * @xb: the xbitmap to search
>> + * @start: the start of the range, inclusive
>> + * @end: the end of the range, exclusive
>> + *
>> + * Returns: the index of the found bit, or @end + 1 if no such bit is found.
>> + */
>> +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start,
>> +				   unsigned long end)
>> +{
>> +	return xb_find_next_bit(xb, start, end, 1);
>> +}
> Won't "exclusive" loose ability to handle ULONG_MAX ? Since this is a
> library module, missing ability to handle ULONG_MAX sounds like an omission.
> Shouldn't we pass (or return) whether "found or not" flag (e.g. strtoul() in
> C library function)?
>
>    bool xb_find_next_set_bit(struct xb *xb, unsigned long start, unsigned long end, unsigned long *result);
>    unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, unsigned long end, bool *found);

Yes, ULONG_MAX needs to be tested by xb_test_bit(). Compared to checking 
the return value, would it be the same to let the caller check for the 
ULONG_MAX boundary?

Best,
Wei