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]

Date:	Mon, 6 Aug 2012 14:38:33 -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 7:29 AM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Thu, 2012-08-02 at 15:34 -0700, Michel Lespinasse wrote:
>> +void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
>> +       void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
>> +{
>> +       __rb_insert(node, root, augment_rotate);
>> +}
>> +EXPORT_SYMBOL(__rb_insert_augmented);
>> +
>> +void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
>> +                       const struct rb_augment_callbacks *augment)
>> +{
>> +       __rb_erase(node, root, augment);
>> +}
>> +EXPORT_SYMBOL(rb_erase_augmented);
>
> From a symmetry POV I'd say have both take the rb_augment_callbacks
> thing. The two taking different arguments is confusing at best.

The idea there is that from the user's point of view, both take the
struct rb_augment_callbacks. Note that include/linux/rbtree.h has
this:

static inline void
rb_insert_augmented(struct rb_node *node, struct rb_root *root,
                    const struct rb_augment_callbacks *augment)
{
        __rb_insert_augmented(node, root, augment->rotate);
}

Now the reason why the actual implementation takes the function
pointer directly (and not the struct) is that the expected case is
that the call site will have the struct declared as a const, so the
compiler will be able to optimize out the dereference and directly
pass out the function pointer as a constant.

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