From: Matthew Wilcox <mawilcox@microsoft.com>
To: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Cc: Tejun Heo <tj@kernel.org>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
Lai Jiangshan <jiangshanlai@gmail.com>,
"Jens Axboe" <axboe@kernel.dk>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
"linux-block@vger.kernel.org" <linux-block@vger.kernel.org>,
"dri-devel@lists.freedesktop.org"
<dri-devel@lists.freedesktop.org>,
"Andrew Morton" <akpm@linux-foundation.org>
Subject: RE: [RFC 00/10] implement alternative and much simpler id allocator
Date: Fri, 23 Dec 2016 17:03:51 +0000 [thread overview]
Message-ID: <BY2PR21MB003659BCA2EC02603245CD2ACB950@BY2PR21MB0036.namprd21.prod.outlook.com> (raw)
In-Reply-To: <87pokjjznr.fsf@rasmusvillemoes.dk>
From: Rasmus Villemoes [mailto:linux@rasmusvillemoes.dk]
> Nice work! A few random comments/questions:
>
> - It does add some complexity, but I think a few comments would make it
> more digestable.
I'm open to adding some comments ... I need some time between writing the code and writing the comments to be sure what comments are useful.
> - Hm, maybe I'm confused, and I certainly don't understand how the whole
> radix tree works. But do you use every leaf node as an exceptional
> entry initially, to allocate the first 62 ids from that level? This
> code
I do! And that question tells me one useful comment to add!
> if ((bit + RADIX_TREE_EXCEPTIONAL_SHIFT) <
> BITS_PER_LONG) {
> bit += RADIX_TREE_EXCEPTIONAL_SHIFT;
> radix_tree_iter_replace(root, &iter, slot,
> (void *)((1UL << bit) |
> RADIX_TREE_EXCEPTIONAL_ENTRY));
> *id = new;
> return 0;
> }
>
> operates on bit, which is the offset from index*IDA_BITMAP_BITS, and
> it seems to create an exceptional entry somewhere down the tree
> (which may of course be the root).
>
> But we don't seem to allocate another bit from that exceptional entry
> ever unless it happened to sit at index 0; the code
>
> unsigned long tmp = (unsigned long)bitmap;
> if (start < BITS_PER_LONG) {
> unsigned tbit = find_next_zero_bit(&tmp,
> BITS_PER_LONG, start);
> if (tbit < BITS_PER_LONG) {
> tmp |= 1UL << tbit;
> rcu_assign_pointer(*slot, (void *)tmp);
> *id = new + tbit -
> RADIX_TREE_EXCEPTIONAL_SHIFT;
> return 0;
> }
> }
>
> is only used for small values of start (though it does seem to
> account for a non-zero value of new == iter.index * IDA_BITMAP_BITS).
Ahh. You're reading the code wrong, and I wrote the code wrongly too, so it's clearly overly complex. I was testing with 'start' set to 0, allocating N entries, and then freeing them. If I'd set start to 1024 and allocated two entries, I'd've seen the failure.
Please see the top commit here ("Improve IDA exceptional entry handling"): http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-12-20
> - In the micro-optimization department, I think we should avoid
> find_next_zero_bit on a single word, and instead use __ffs. Something
> like (assuming we can use bit instead of start)
>
> if (bit + RADIX_TREE_EXCEPTIONAL_SHIFT < BITS_PER_LONG) {
> tmp = (~(unsigned long)bitmap) >> (bit + RADIX_TREE_EXCEPTIONAL_SHIFT);
> if (tmp) {
> tbit = __ffs(tmp) + bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
> tmp = (unsigned long)bitmap | (1UL << tbit);
> rcu_assign_pointer(*slot, (void *)tmp);
> *id = new + tbit - RADIX_TREE_EXCEPTIONAL_SHIFT;
> return 0;
> }
> }
I'm certainly open to microoptimisations, but I'll have to think about this one for a bit.
next prev parent reply other threads:[~2016-12-23 17:19 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-08 1:22 [RFC 00/10] implement alternative and much simpler id allocator Rasmus Villemoes
2016-12-08 1:22 ` [RFC 01/10] lib/idr.c: reused free bitmaps are already clear Rasmus Villemoes
2016-12-08 1:22 ` [RFC 02/10] lib/idr.c: delete useless condition Rasmus Villemoes
2016-12-08 1:22 ` [RFC 03/10] lib/idr.c: only fill ida->idr when needed Rasmus Villemoes
2016-12-08 1:22 ` [RFC 04/10] lib/tida.c: a very simple integer id allocator Rasmus Villemoes
2016-12-08 1:23 ` [RFC 05/10] kernel/workqueue.c: replace id allocator ida with tida Rasmus Villemoes
2016-12-08 1:23 ` [RFC 06/10] block: use tida as small id allocator Rasmus Villemoes
2016-12-08 3:56 ` Jens Axboe
2016-12-08 11:02 ` Greg Kroah-Hartman
2016-12-08 1:23 ` [RFC 07/10] drivers/base/platform.c: use simpler " Rasmus Villemoes
2016-12-08 1:23 ` [RFC 08/10] lib/tida.c: introduce tida_get_above Rasmus Villemoes
2016-12-08 1:23 ` [RFC 09/10] drm: use simpler id allocator Rasmus Villemoes
2016-12-08 1:23 ` [RFC 10/10] fs/devpts: use tida for id allocation Rasmus Villemoes
2016-12-09 13:49 ` [RFC 00/10] implement alternative and much simpler id allocator Tejun Heo
2016-12-09 22:01 ` Andrew Morton
2016-12-12 17:09 ` Tejun Heo
2016-12-12 17:35 ` Matthew Wilcox
2016-12-12 18:05 ` Tejun Heo
2016-12-16 19:14 ` Matthew Wilcox
2016-12-16 20:32 ` Rasmus Villemoes
2016-12-16 21:09 ` Matthew Wilcox
2016-12-17 13:28 ` Matthew Wilcox
2016-12-22 23:46 ` Rasmus Villemoes
2016-12-23 17:03 ` Matthew Wilcox [this message]
2016-12-18 2:42 ` Matthew Wilcox
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=BY2PR21MB003659BCA2EC02603245CD2ACB950@BY2PR21MB0036.namprd21.prod.outlook.com \
--to=mawilcox@microsoft.com \
--cc=akpm@linux-foundation.org \
--cc=axboe@kernel.dk \
--cc=dri-devel@lists.freedesktop.org \
--cc=gregkh@linuxfoundation.org \
--cc=jiangshanlai@gmail.com \
--cc=linux-block@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=tj@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).