linux-kernel - Re: [PATCH 02/11] lib/interval-tree: add an equivalent tree with [a,b) intervals

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: <20191004110224.GA253758@google.com>
Date:   Fri, 4 Oct 2019 04:02:24 -0700
From:   Michel Lespinasse <walken@...gle.com>
To:     Davidlohr Bueso <dave@...olabs.net>
Cc:     akpm@...ux-foundation.org, peterz@...radead.org,
        linux-kernel@...r.kernel.org, linux-mm@...ck.org,
        dri-devel@...ts.freedesktop.org, linux-rdma@...r.kernel.org,
        Davidlohr Bueso <dbueso@...e.de>
Subject: Re: [PATCH 02/11] lib/interval-tree: add an equivalent tree with
 [a,b) intervals

On Thu, Oct 03, 2019 at 01:18:49PM -0700, Davidlohr Bueso wrote:
> +/*									      \
> + * Iterate over intervals intersecting [start;end)			      \
> + *									      \
> + * Note that a node's interval intersects [start;end) iff:		      \
> + *   Cond1: ITSTART(node) < end						      \
> + * and									      \
> + *   Cond2: start < ITEND(node)						      \
> + */									      \
> +									      \
> +static ITSTRUCT *							      \
> +ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE end)	      \
> +{									      \
> +	while (true) {							      \
> +		/*							      \
> +		 * Loop invariant: start <= node->ITSUBTREE		      \
Should be start < node->ITSUBTREE
> +		 * (Cond2 is satisfied by one of the subtree nodes)	      \
> +		 */							      \
> +		if (node->ITRB.rb_left) {				      \
> +			ITSTRUCT *left = rb_entry(node->ITRB.rb_left,	      \
> +						  ITSTRUCT, ITRB);	      \
> +			if (start < left->ITSUBTREE) {			      \
> +				/*					      \
> +				 * Some nodes in left subtree satisfy Cond2.  \
> +				 * Iterate to find the leftmost such node N.  \
> +				 * If it also satisfies Cond1, that's the     \
> +				 * match we are looking for. Otherwise, there \
> +				 * is no matching interval as nodes to the    \
> +				 * right of N can't satisfy Cond1 either.     \
> +				 */					      \
> +				node = left;				      \
> +				continue;				      \
> +			}						      \
> +		}							      \
> +		if (ITSTART(node) < end) {		/* Cond1 */	      \
> +			if (start < ITEND(node))	/* Cond2 */	      \
> +				return node;	/* node is leftmost match */  \
> +			if (node->ITRB.rb_right) {			      \
> +				node = rb_entry(node->ITRB.rb_right,	      \
> +						ITSTRUCT, ITRB);	      \
> +				if (start <= node->ITSUBTREE)		      \
Should be start < node->ITSUBTREE
> +					continue;			      \
> +			}						      \
> +		}							      \
> +		return NULL;	/* No match */				      \
> +	}								      \
> +}									      \

Other than that, the change looks good to me.

This is something I might use, regardless of the status of converting
other current users.

The name "interval_tree_gen.h" makes it ambiguous wether gen stands
for "generic" or "generator". This may sounds like a criticism,
but it's not - I think it really stands for both :)

Reviewed-by: Michel Lespinasse <walken@...gle.com>

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.