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: <201712212337.JFC57368.tLFOJFVSFHMOOQ@I-love.SAKURA.ne.jp>
Date:   Thu, 21 Dec 2017 23:37:49 +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_find_set - find the next set bit in a range of bits
> > + * @xb: the xbitmap to search from
> > + * @offset: the offset in the range to start searching
> > + * @size: the size of the range
> > + *
> > + * Returns: the found bit or, @size if no set bit is found.
> > + */
> > +unsigned long xb_find_set(struct xb *xb, unsigned long size,
> > +			  unsigned long offset)
> > +{
> > +	struct radix_tree_root *root = &xb->xbrt;
> > +	struct radix_tree_node *node;
> > +	void __rcu **slot;
> > +	struct ida_bitmap *bitmap;
> > +	unsigned long index = offset / IDA_BITMAP_BITS;
> > +	unsigned long index_end = size / IDA_BITMAP_BITS;
> > +	unsigned long bit = offset % IDA_BITMAP_BITS;
> > +
> > +	if (unlikely(offset >= size))
> > +		return size;
> > +
> > +	while (index <= index_end) {
> > +		unsigned long ret;
> > +		unsigned int nbits = size - index * IDA_BITMAP_BITS;
> > +
> > +		bitmap = __radix_tree_lookup(root, index, &node, &slot);
> > +
> > +		if (!node && !bitmap)
> > +			return size;
> > +
> > +		if (bitmap) {
> > +			if (nbits > IDA_BITMAP_BITS)
> > +				nbits = IDA_BITMAP_BITS;
> > +
> > +			ret = find_next_bit(bitmap->bitmap, nbits, bit);
> > +			if (ret != nbits)
> > +				return ret + index * IDA_BITMAP_BITS;
> > +		}
> > +		bit = 0;
> > +		index++;
> > +	}
> > +
> > +	return size;
> > +}
> > +EXPORT_SYMBOL(xb_find_set);
> 
> This is going to be slower than the implementation I sent yesterday.  If I
> call:
> 	xb_init(xb);
> 	xb_set_bit(xb, ULONG_MAX);
> 	xb_find_set(xb, ULONG_MAX, 0);
> 
> it's going to call __radix_tree_lookup() 16 quadrillion times.
> My implementation will walk the tree precisely once.
> 
Yes. Wei's patch still can not work.
We should start reviewing Matthew's implementation.