linux-kernel - Re: [PATCH v4 11/13] rbtree.h: Generic Red-Black Trees

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] [day] [month] [year] [list]

Date:	Wed, 27 Jun 2012 15:00:08 +0200
From:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
To:	Daniel Santos <daniel.santos@...ox.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	Christopher Li <sparse@...isli.org>,
	David Daney <david.daney@...ium.com>,
	David Howells <dhowells@...hat.com>,
	David Rientjes <rientjes@...gle.com>,
	Hidetoshi Seto <seto.hidetoshi@...fujitsu.com>,
	"H. Peter Anvin" <hpa@...or.com>, Ingo Molnar <mingo@...e.hu>,
	Ingo Molnar <mingo@...nel.org>, Joe Perches <joe@...ches.com>,
	Konstantin Khlebnikov <khlebnikov@...nvz.org>,
	linux-doc@...r.kernel.org, linux-sparse@...r.kernel.org,
	LKML <linux-kernel@...r.kernel.org>,
	Paul Gortmaker <paul.gortmaker@...driver.com>,
	Paul Turner <pjt@...gle.com>,
	Pavel Pisa <pisa@....felk.cvut.cz>,
	Richard Weinberger <richard@....at>,
	Rob Landley <rob@...dley.net>,
	Steven Rostedt <rostedt@...dmis.org>,
	Suresh Siddha <suresh.b.siddha@...el.com>
Subject: Re: [PATCH v4 11/13] rbtree.h: Generic Red-Black Trees

On Fri, 2012-06-22 at 23:00 -0500, Daniel Santos wrote:

> +typedef long (*rb_compare_f)(const void *a, const void *b);

> +struct rb_relationship {
> +	ssize_t root_offset;
> +	ssize_t left_offset;
> +	ssize_t right_offset;
> +	ssize_t count_offset;
> +	ssize_t node_offset;
> +	ssize_t key_offset;
> +	int flags;
> +	const rb_compare_f compare;
> +	const rb_augment_f augment;
> +};

> +static __always_inline __flatten
> +struct rb_node *__rb_find(
> +		struct rb_node *node,
> +		const void *key,
> +		const struct rb_relationship *rel)
> +{
> +	__rb_assert_good_rel(rel);
> +	while (node) {
> +		long diff = rel->compare(key, __rb_node_to_key(node, rel));
> +
> +		if (diff > 0)
> +			node = node->rb_right;
> +		else if (diff < 0)
> +			node = node->rb_left;
> +		else
> +			return node;
> +	}
> +
> +	return 0;
> +}

> +#define RB_RELATIONSHIP(						\
> +		cont_type, root, left, right, count,			\
> +		obj_type, node, key,					\
> +		_flags, _compare, _augment) {				\
> +	.root_offset     = offsetof(cont_type, root),			\
> +	.left_offset     = OPT_OFFSETOF(cont_type, left),		\
> +	.right_offset    = OPT_OFFSETOF(cont_type, right),		\
> +	.count_offset    = OPT_OFFSETOF(cont_type, count),		\
> +	.node_offset     = offsetof(obj_type, node),			\
> +	.key_offset      = offsetof(obj_type, key),			\
> +	.flags           = (_flags)					\
> +			 | IFF_EMPTY(left ,    0,  RB_HAS_LEFTMOST)	\
> +			 | IFF_EMPTY(right,    0,  RB_HAS_RIGHTMOST)	\
> +			 | IFF_EMPTY(count,    0,  RB_HAS_COUNT)	\
> +			 | IFF_EMPTY(_augment, 0,  RB_IS_AUGMENTED),	\
> +	.compare         = (const rb_compare_f) (_compare),		\
> +	.augment         = IFF_EMPTY(_augment, 0, _augment)		\
> +}

> +#define RB_DEFINE_INTERFACE(						\
> +	prefix,								\
> +	cont_type, root, left, right, count,				\
> +	obj_type, node, key,						\
> +	flags, compare, augment,					\
> +	find_mod, insert_mod, find_near_mod, insert_near_mod)		\
> +									\
> 									\
> +static const struct rb_relationship prefix ## _rel =			\
> +RB_RELATIONSHIP(							\
> +	cont_type, root, left, right, count,				\
> +	obj_type, node, key,						\
> +	flags, compare, augment);					\
> +									\
> +IFF_EMPTY(find_mod, static __always_inline, find_mod)			\
> +obj_type *prefix ## _find(cont_type *cont,				\
> +			  const typeof(((obj_type *)0)->key) *_key)	\
> +{									\
> +	struct rb_node *ret = rb_find(					\
> +			&cont->root, _key, &prefix ## _rel);		\
> +	return ret ? rb_entry(ret, obj_type, node) : 0;			\
> +}									\


So the one thing I noticed was your 'fixed' long return type for
compare. I guess that's one of the things that inspired your CFS compare
'hack' since on 32bit that's too short.

I tried playing with typeof() and return types of function pointers, but
I couldn't make it work. Bummer. That leaves explicitly passing it to
the RB_DEFINE_INTERFACE() and pulling all relevant inline functions into
the macro as well.


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