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