From nobody Tue Oct 12 21:27:28 2021 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id B5AC512D3989; Tue, 12 Oct 2021 21:27:48 +0000 (UTC) (envelope-from lutz@iks-jena.de) Received: from annwfn.iks-jena.de (annwfn.iks-jena.de [IPv6:2001:4bd8::19]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4HTTKH3TPgz3llv; Tue, 12 Oct 2021 21:27:47 +0000 (UTC) (envelope-from lutz@iks-jena.de) X-SMTP-Sender: IPv6:2001:4bd8:0:666:248:54ff:fe12:ee3f Received: from belenus.iks-jena.de (belenus.iks-jena.de [IPv6:2001:4bd8:0:666:248:54ff:fe12:ee3f]) by annwfn.iks-jena.de (8.15.2/8.15.2) with ESMTPS id 19CLRSIM003836 (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Tue, 12 Oct 2021 23:27:29 +0200 X-MSA-Host: belenus.iks-jena.de Received: (from lutz@localhost) by belenus.iks-jena.de (8.14.3/8.14.1/Submit) id 19CLRSRp000786; Tue, 12 Oct 2021 23:27:28 +0200 Date: Tue, 12 Oct 2021 23:27:28 +0200 From: Lutz Donnerhacke To: Gleb Smirnoff Cc: Lutz Donnerhacke , src-committers@freebsd.org, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Subject: Re: git: 25392fac9488 - main - libalias: Fix splay comparsion bug Message-ID: <20211012212728.GA390@belenus.iks-jena.de> References: <202107022232.162MWUIY049889@gitrepo.freebsd.org> List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-message-flag: Please send plain text messages only. Thank you. User-Agent: Mutt/1.5.17 (2007-11-01) X-Rspamd-Queue-Id: 4HTTKH3TPgz3llv X-Spamd-Bar: - Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=pass (mx1.freebsd.org: domain of lutz@iks-jena.de designates 2001:4bd8::19 as permitted sender) smtp.mailfrom=lutz@iks-jena.de X-Spamd-Result: default: False [-1.50 / 15.00]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; R_SPF_ALLOW(-0.20)[+ip6:2001:4bd8::/48]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[donnerhacke.de]; NEURAL_HAM_LONG(-1.00)[-1.000]; RCPT_COUNT_FIVE(0.00)[5]; NEURAL_SPAM_SHORT(0.60)[0.598]; FORGED_SENDER(0.30)[lutz@donnerhacke.de,lutz@iks-jena.de]; RCVD_IN_DNSWL_LOW(-0.10)[2001:4bd8:0:666:248:54ff:fe12:ee3f:received]; R_DKIM_NA(0.00)[]; MIME_TRACE(0.00)[0:+]; ASN(0.00)[asn:15725, ipnet:2001:4bd8::/29, country:DE]; FROM_NEQ_ENVFROM(0.00)[lutz@donnerhacke.de,lutz@iks-jena.de]; RCVD_TLS_ALL(0.00)[]; RCVD_COUNT_TWO(0.00)[2] X-Spam: Yes X-ThisMailContainsUnwantedMimeParts: N 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 > L> AuthorDate: 2021-07-02 21:41:25 +0000 > L> Commit: Lutz Donnerhacke > 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