Re: git: 25392fac9488 - main - libalias: Fix splay comparsion bug

On Fri, Aug 06, 2021 at 08:00:39AM -0700, Gleb Smirnoff wrote:
> Wouldn't declaring 'i' to u_short fix the root of the problem?

Oh, I missed this mail.

No, switching to a different "zero" in the ring of modular operations, does
not fix the inherent problem of the space needed for all possible results.

The arithmetic of subtraction may generate results from -x to +x, if x is
the largest possible value (according to some "zero") in the source
distribution using n bits. Hence you need at least more than one bit in the
result type (a single bit is not sufficient, you have to deal with 2^n+1
values).

Because the type, we are operation on, is 32bit, the result type needs to be
at least 34bit. This needs to propagate down into the algorithm. You have to
avoid any implicit integer type conversion at any cost. Otherwise the
modular arithmetic error will kick in again.

In order to simplify the operation for the reader, and to avoid to repeat
the mistakes, I already made, I choosed to make the comparsions explicit.

> 
> On Fri, Jul 02, 2021 at 10:32:30PM +0000, Lutz Donnerhacke wrote:
> L> The branch main has been updated by donner:
> L> 
> L> URL: https://cgit.FreeBSD.org/src/commit/?id=25392fac9488bcae5c451500df2e2945430484a6
> L> 
> L> commit 25392fac9488bcae5c451500df2e2945430484a6
> L> Author:     Lutz Donnerhacke <donner@FreeBSD.org>
> L> AuthorDate: 2021-07-02 21:41:25 +0000
> L> Commit:     Lutz Donnerhacke <donner@FreeBSD.org>
> L> CommitDate: 2021-07-02 22:31:53 +0000
> L> 
> L>     libalias: Fix splay comparsion bug
> L>     
> L>     Comparing elements in a tree requires transitiviy.  If a < b and b < c
> L>     then a must be smaller than c.  This way the tree elements are always
> L>     pairwise comparable.
> L>     
> L>     Tristate comparsion functions returning values lower, equal, or
> L>     greater than zero, are usually implemented by a simple subtraction of
> L>     the operands.  If the size of the operands are equal to the size of
> L>     the result, integer modular arithmetics kick in and violates the
> L>     transitivity.
> L>     
> L>     Example:
> L>     Working on byte with 0, 120, and 240. Now computing the differences:
> L>       120 -   0 = 120
> L>       240 - 120 = 120
> L>       240 -   0 = -16
> L>     
> L>     MFC after:      3 days
> L>  sys/netinet/libalias/alias_db.h | 13 +++++++------
> L>  1 file changed, 7 insertions(+), 6 deletions(-)
> L> 
> L> diff --git a/sys/netinet/libalias/alias_db.h b/sys/netinet/libalias/alias_db.h
> L> index ec0b69c01f82..971ca305c1a6 100644
> L> --- a/sys/netinet/libalias/alias_db.h
> L> +++ b/sys/netinet/libalias/alias_db.h
> L> @@ -351,10 +351,10 @@ static inline int
> L>  cmp_out(struct alias_link *a, struct alias_link *b) {
> L>  	int i = a->src_port - b->src_port;
> L>  	if (i != 0) return (i);
> L> -	i = a->src_addr.s_addr - b->src_addr.s_addr;
> L> -	if (i != 0) return (i);
> L> -	i = a->dst_addr.s_addr - b->dst_addr.s_addr;
> L> -	if (i != 0) return (i);
> L> +	if (a->src_addr.s_addr > b->src_addr.s_addr) return (1);
> L> +	if (a->src_addr.s_addr < b->src_addr.s_addr) return (-1);
> L> +	if (a->dst_addr.s_addr > b->dst_addr.s_addr) return (1);
> L> +	if (a->dst_addr.s_addr < b->dst_addr.s_addr) return (-1);
> L>  	i = a->dst_port - b->dst_port;
> L>  	if (i != 0) return (i);
> L>  	i = a->link_type - b->link_type;
> L> @@ -368,8 +368,9 @@ cmp_in(struct group_in *a, struct group_in *b) {
> L>  	if (i != 0) return (i);
> L>  	i = a->link_type - b->link_type;
> L>  	if (i != 0) return (i);
> L> -	i = a->alias_addr.s_addr - b->alias_addr.s_addr;
> L> -	return (i);
> L> +	if (a->alias_addr.s_addr > b->alias_addr.s_addr) return (1);
> L> +	if (a->alias_addr.s_addr < b->alias_addr.s_addr) return (-1);
> L> +	return (0);
> L>  }
> L>  SPLAY_PROTOTYPE(splay_in, group_in, in, cmp_in);
> L>  
> 
> -- 
> Gleb Smirnoff