linux-kernel - Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation

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: <CANN689HKPKeZ-sqqwXGPhv=Jno4c=v=ffeOxLPkOFmMzEVXexw@mail.gmail.com>
Date:	Mon, 6 Aug 2012 14:55:45 -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, torvalds@...ux-foundation.org
Subject: Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation

On Mon, Aug 6, 2012 at 8:38 AM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Mon, 2012-08-06 at 16:17 +0200, Peter Zijlstra wrote:
>
>> Why would every user need to replicate the propagate and rotate
>> boilerplate?
>
> So I don't have a tree near that any of this applies to (hence no actual
> patch)

All right, here are instructions to get a tree this will apply to :)
1- fetch linux-next tree
2- check out next-20120806
3- revert e406c4110c968b7691c4ccfadcd866a74a72fa5b (was sent as
previous RFC version of this series, didn't realize it had made it
into -mm)
4- apply patches 1 and 3-9 of this series (patch 2 was also sent as
previous RFC version and made it into -mm)

> but why can't we have something like:
>
> struct rb_augment_callback {
>         const bool (*update)(struct rb_node *node);
>         const int offset;
>         const int size;
> };
>
> #define RB_AUGMENT_CALLBACK(_update, _type, _rb_member, _aug_member)    \
> (struct rb_augment_callback){                                           \
>         .update = _update,                                              \
>         .offset = offsetof(_type, _aug_member) -                        \
>                   offsetof(_type, _rb_member),                          \
>         .size   = sizeof(((_type *)NULL)->_aug_member),                 \
> }
>
> static __always_inline void
> augment_copy(struct rb_node *dst, struct rb_node *src,
>              const rb_augment_callback *ac)
> {
>         memcpy((void *)dst + ac->offset,
>                (void *)src + ac->offset,
>                ac->size);
> }
>
> static __always_inline void
> augment_propagate(struct rb_node *rb, struct rb_node *stop,
>                   const struct rb_augment_callback *ac)
> {
>         while (rb != stop) {
>                 if (!ac->update(rb))
>                         break;
>                 rb = rb_parent(rb);
>         }
> }
>
> static __always_inline void
> augment_rotate(struct rb_node *old, struct rb_node *new.
>                const struct rb_augment_callback *ac)
> {
>         augment_copy(new, old, ac);
>         (void)ac->update(old);
> }

I don't think this would work well, because ac->offset and ac->size
wouldn't be known at the point where they are needed, so the memcpy
wouldn't be nicely optimized into a fetch and store of the desired
size.

However, I wouldn't have a problem with declaring all 3 callbacks (and
the struct holding them) using a preprocessor macro as you propose.
Would that seem fine with you ? I can send an add-on patch to do that.

-- 
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/