linux-kernel - Re: [PATCH 4/6] rbtree: faster augmented insert

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:	Fri, 27 Jul 2012 14:43:15 -0700
From:	Michel Lespinasse <walken@...gle.com>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	riel@...hat.com, daniel.santos@...ox.com, aarcange@...hat.com,
	dwmw2@...radead.org, akpm@...ux-foundation.org, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 4/6] rbtree: faster augmented insert

On Fri, Jul 27, 2012 at 12:26 PM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote:
>> --- a/lib/rbtree.c
>> +++ b/lib/rbtree.c
>> @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
>>                 root->rb_node = new;
>>  }
>>
>> -void rb_insert_color(struct rb_node *node, struct rb_root *root)
>> +inline void rb_insert_augmented(struct rb_node *node, struct rb_root *root,
>> +                               rb_augment_rotate *augment)
>
> Daniel probably knows best, but I would have expected something like:
>
> __always_inline void
> __rb_insert(struct rb_node *node, struct rb_root *root,
>             const rb_augment_rotate *augment)
>
> Where you force inline and use a const function pointer since GCC is
> better with inlining them -- iirc, Daniel?

This hasn't been necessary with my compiler, but I can see how this
might help with older gcc versions. I really haven't investigated that
much and would be open to daniel's suggestions there.

To answer your question in the next email, we're using a gcc 4.6
variant with some local patches. TBH I don't know precisely what's in
there, however I think our compiler team makes a good job of working
with upstream so whatever changes they have are probably coming to a
future gcc version :)

>>  {
>>         struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
>>
>> @@ -152,6 +153,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
>>                                         rb_set_parent_color(tmp, parent,
>>                                                             RB_BLACK);
>>                                 rb_set_parent_color(parent, node, RB_RED);
>> +                               augment(parent, node);
>
> And possibly:
>                 if (augment)
>                         augment(parent, node);
>
> That would obviate the need for the dummy..

__rb_insert() gets instanciated two times, one as rb_insert_color()
with dummy callbacks, and one as rb_insert_augmented() itself with
user-passed callbacks. Using NULL instead of dummy callbacks would
generate the same code in the rb_insert_color() instance, but not in
the version that takes user-passed callbacks (i.e. there would be an
extra check for NULL there, which we don't want).

>> +void rb_insert_color(struct rb_node *node, struct rb_root *root) {
>
> placed your { wrong..

Oops (caught myself a few times doing that, missed this one
apparently... thanks for noticing)

>> +       rb_insert_augmented(node, root, dummy);
>> +}
>>  EXPORT_SYMBOL(rb_insert_color);
>
> And use Daniel's __flatten here, like:
>
> void rb_insert_color(struct rb_node *node, struct rb_root *root)
> __flatten
> {
>         __rb_insert(node, root, NULL);
> }
> EXPORT_SYMBOL(rb_insert_color);
>
> void rb_insert_augmented(struct rb_node *node, struct rb_root *root,
>                          const rb_augment_rotate *augment) __flatten
> {
>         __rb_insert(node, root, augment);
> }
> EXPORT_SYMBOL(rb_insert_augmented);

Looks good, I'll try that and resubmit.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
--
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/