git: 25392fac9488 - main - libalias: Fix splay comparsion bug
Rob Wing
rob.fx907 at gmail.com
Fri Aug 6 16:44:16 UTC 2021
Hey Gleb,
as a heads up (in case you missed it)...about a week ago Lutz mentioned
he’d be AFK for three weeks.
On Friday, August 6, 2021, Gleb Smirnoff <glebius at freebsd.org> wrote:
> Lutz,
>
> Wouldn't declaring 'i' to u_short fix the root of the problem?
>
> 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 at FreeBSD.org>
> L> AuthorDate: 2021-07-02 21:41:25 +0000
> L> Commit: Lutz Donnerhacke <donner at 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
>
More information about the dev-commits-src-all
mailing list