linux-kernel - Re: [PATCH 2/2] augmented rbtree: rework the RB_DECLARE

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: <20190701073137.GL3402@hirez.programming.kicks-ass.net>
Date:   Mon, 1 Jul 2019 09:31:37 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Michel Lespinasse <walken@...gle.com>
Cc:     Davidlohr Bueso <dave@...olabs.net>,
        David Howells <dhowells@...hat.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH 2/2] augmented rbtree: rework the RB_DECLARE_CALLBACKS
 macro definition

On Fri, Jun 28, 2019 at 05:49:52PM -0700, Michel Lespinasse wrote:
> --- a/tools/include/linux/rbtree_augmented.h
> +++ b/tools/include/linux/rbtree_augmented.h
> @@ -74,39 +74,48 @@ rb_insert_augmented_cached(struct rb_node *node,
>  			      newleft, &root->rb_leftmost, augment->rotate);
>  }
>  
> -#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
> -			     rbtype, rbaugmented, rbcompute)		\
> +/*
> + * Template for declaring augmented rbtree callbacks
> + *
> + * RBSTRUCT:    struct type of the tree nodes
> + * RBFIELD:     name of struct rb_node field within RBSTRUCT
> + * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
> + * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
> + * RBSTATIC:    'static' or empty
> + * RBNAME:      name of the rb_augment_callbacks structure
> + */
> +
> +#define RB_DECLARE_CALLBACKS(RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE,	\
> +			     RBSTATIC, RBNAME)				\
>  static inline void							\
> -rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
> +RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
>  {									\
>  	while (rb != stop) {						\
> -		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
> -		rbtype augmented = rbcompute(node);			\
> -		if (node->rbaugmented == augmented)			\
> +		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
> +		if (RBCOMPUTE(node, true))				\
>  			break;						\
> -		node->rbaugmented = augmented;				\
> -		rb = rb_parent(&node->rbfield);				\
> +		rb = rb_parent(&node->RBFIELD);				\
>  	}								\
>  }									\
>  static inline void							\
> -rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
> +RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
>  {									\
> -	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
> -	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
> -	new->rbaugmented = old->rbaugmented;				\
> +	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
> +	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
> +	new->RBAUGMENTED = old->RBAUGMENTED;				\
>  }									\
>  static void								\
> -rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
> +RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
>  {									\
> -	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
> -	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
> -	new->rbaugmented = old->rbaugmented;				\
> -	old->rbaugmented = rbcompute(old);				\
> +	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
> +	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
> +	new->RBAUGMENTED = old->RBAUGMENTED;				\
> +	RBCOMPUTE(old, false);						\
>  }									\
> -rbstatic const struct rb_augment_callbacks rbname = {			\
> -	.propagate = rbname ## _propagate,				\
> -	.copy = rbname ## _copy,					\
> -	.rotate = rbname ## _rotate					\
> +RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
> +	.propagate = RBNAME ## _propagate,				\
> +	.copy = RBNAME ## _copy,					\
> +	.rotate = RBNAME ## _rotate					\
>  };

I'm thinking that should've been in the previous patch.