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: <20190701074630.GM3402@hirez.programming.kicks-ass.net>
Date:   Mon, 1 Jul 2019 09:46:30 +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:
> - Change the definition of the RBCOMPUTE function. The propagate
>   callback repeatedly calls RBCOMPUTE as it moves from leaf to root.
>   it wants to stop recomputing once the augmented subtree information
>   doesn't change. This was previously checked using the == operator,
>   but that only works when the augmented subtree information is a
>   scalar field. This commit modifies the RBCOMPUTE function so that
>   it now sets the augmented subtree information instead of returning it,
>   and returns a boolean value indicating if the propagate callback
>   should stop.
> 
> - Reorder the RB_DECLARE_CALLBACKS macro arguments, following the
>   style of the INTERVAL_TREE_DEFINE macro, so that RBSTATIC and RBNAME
>   are passed last.
> 
> The generated code should not change when the RBCOMPUTE function is inlined,
> which is the typical / intended case.

This seems something that shoud (:-) be easy to verify; no reason to be
uncertain about this. Either it does or does not change generated code.

> The motivation for this change is that I want to introduce augmented rbtree
> uses where the augmented data for the subtree is a struct instead of a scalar.
> 
> Signed-off-by: Michel Lespinasse <walken@...gle.com>

> @@ -66,11 +66,14 @@ static u64 compute_subtree_max_end(struct memtype *data)
>  	if (child_max_end > max_end)
>  		max_end = child_max_end;
>  
> -	return max_end;
> +	if (exit && data->subtree_max_end == max_end)
> +		return true;
> +	data->subtree_max_end = max_end;
> +	return false;
>  }

> @@ -35,11 +35,14 @@ compute_subtree_last(struct drbd_interval *node)
>  		if (right > max)
>  			max = right;
>  	}
> -	return max;
> +	if (exit && node->end == max)
> +		return true;
> +	node->end = max;
> +	return false;
>  }

> @@ -57,11 +58,15 @@ static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)	      \
>  		if (max < subtree_last)					      \
>  			max = subtree_last;				      \
>  	}								      \
> -	return max;							      \
> +	if (exit && node->ITSUBTREE == max)				      \
> +		return true;						      \
> +	node->ITSUBTREE = max;						      \
> +	return false;							      \
>  }									      \

> @@ -91,11 +91,14 @@ static inline u32 augment_recompute(struct test_node *node)
>  		if (max < child_augmented)
>  			max = child_augmented;
>  	}
> -	return max;
> +	if (exit && node->augmented == max)
> +		return true;
> +	node->augmented = max;
> +	return false;
>  }

> @@ -318,7 +318,10 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma)
>  		if (subtree_gap > max)
>  			max = subtree_gap;
>  	}
> -	return max;
> +	if (exit && vma->rb_subtree_gap == max)
> +		return true;
> +	vma->rb_subtree_gap = max;
> +	return false;
>  }

And that is _really_ unfortunate, as in 5 copies of exactly the same
logic sucks.

Can't we have a helper macro that converts an old (scalar) style compute
into a new style compute and avoid this unfortunate and error prone
copy/pasta ?

Something like:

#define RBCOMPUTE_SCALAR(_comp, _rb _exit)
({
	RBSTRUCT *node = rb_entry((_rb), RBSTRUCT, RBFIELD);
	RBTYPE augmented = _comp(node);
	bool ret = true;
	if (!((_exit) && node->RBAUGMENTED == augmented)) {
		node->RBAUGMENTED = augmented;
		ret = false;
	}
	ret;
})