From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-3.9 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by dcvr.yhbt.net (Postfix) with ESMTP id 9BB6E1F466 for ; Tue, 4 Feb 2020 01:05:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726924AbgBDBFc (ORCPT ); Mon, 3 Feb 2020 20:05:32 -0500 Received: from injection.crustytoothpaste.net ([192.241.140.119]:53338 "EHLO injection.crustytoothpaste.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726369AbgBDBFb (ORCPT ); Mon, 3 Feb 2020 20:05:31 -0500 Received: from camp.crustytoothpaste.net (unknown [IPv6:2001:470:b978:101:b610:a2f0:36c1:12e3]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by injection.crustytoothpaste.net (Postfix) with ESMTPSA id 9A5236044F; Tue, 4 Feb 2020 01:05:29 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=crustytoothpaste.net; s=default; t=1580778329; bh=+7qrK9ONPj7JbN/AXxsJ20JYk7YQZgKhhLwda6wg8CQ=; h=Date:From:To:Cc:Subject:References:Content-Type: Content-Disposition:In-Reply-To:From:Reply-To:Subject:Date:To:CC: Resent-Date:Resent-From:Resent-To:Resent-Cc:In-Reply-To:References: Content-Type:Content-Disposition; b=H/sv7AI2u+POMLwaHipb7JHvsWjlyKcNX2+ZHBzGKsDHHvExyoVOr5pfl/tvN1r2/ +fQwVRGU2ncUd1DhOYaGtkUERWuLJCUnueQ+lq8CsgDJwds+RqtAC5qMcEWeNmOgxX peyeOk1PF4dtlSBfliQ5LdeYH2QUAefJLHq814Bv1+2H+gqB8wyn0oyLEECmii1UVq tY6A5RtXMy1keoKZJP5u6sdgOILkCOSqXNCDmEt8Odll1QYkVYqVRlmeJV7424rOPO FJo7dA+DQN9eWU7bLDwceDEauk4JNgAtpk9gnrmDkV4VjJCATeNq+JiXCuSYzAo4G2 rCRFHRY/V2/mHKlSCSHrAQ/Ju5LnS5XMT8pP42umd65HyCq1FhaIpAXCs0jG9eQeMF vBTvC7tmB121U5fwLWDycxY5fW2KRfQWNNUtmKQAauJvc04IfxPDdVsxs/0+xLllcy Y5LZ3LZBZuelfa9NLIqi7cXP7IDSms57d+xPd0ibE2fQTR8OTDQ Date: Tue, 4 Feb 2020 01:05:23 +0000 From: "brian m. carlson" To: Johan Herland Cc: git@vger.kernel.org, Johannes Schindelin Subject: Re: [PATCH 2/2] notes.c: fix off-by-one error when decreasing notes fanout Message-ID: <20200204010523.GR4113372@camp.crustytoothpaste.net> Mail-Followup-To: "brian m. carlson" , Johan Herland , git@vger.kernel.org, Johannes Schindelin References: <20200203210445.2854-1-johan@herland.net> <20200203210445.2854-2-johan@herland.net> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="ffBYM5qgR8HH9Mta" Content-Disposition: inline In-Reply-To: <20200203210445.2854-2-johan@herland.net> X-Machine: Running on camp using GNU/Linux on x86_64 (Linux kernel 5.3.0-3-amd64) Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org --ffBYM5qgR8HH9Mta Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On 2020-02-03 at 21:04:45, Johan Herland wrote: > As noted in the previous commit, the nature of the fanout heuristic > in the notes code causes the exact point at which we increase or > decrease the notes fanout to vary with the objects being annotated. > Since the object ids generated by the test environment are > deterministic (by design), the notes generated and tested by t3305 > are always the same, and we therefore happen to see the same fanout > behavior from one run to the next. >=20 > Coincidentally, if we were to change the test environment slightly > (say by making a test commit on an unrelated branch before we start > the t3305 test proper), we not only see the fanout switch happen at > different points, we also manage to trigger a _bug_ in the notes > code where the fanout 1 -> 0 switch is not applied uniformly across > the notes tree, but instead yields a notes tree like this: >=20 > ... > bdeafb301e44b0e4db0f738a2d2a7beefdb70b70 > bff2d39b4f7122bd4c5caee3de353a774d1e632a > d3/8ec8f851adf470131178085bfbaab4b12ad2a7 > e0b173960431a3e692ae929736df3c9b73a11d5b > eb3c3aede523d729990ac25c62a93eb47c21e2e3 > ... >=20 > The bug occurs when we are writing out a notes tree with a newly > decreased fanout, and the notes tree contains unexpanded subtrees > that should be consolidated into the parent tree as a consequence of > the decreased fanout): >=20 > Subtrees that happen to sit at an _even_ level in the internal notes > 16-tree structure (in other words: subtrees whose path - "d3" in the > example above - is unique in the first nibble - i.e. there are no > other note paths that start with "d") are _not_ unpacked as part of > the tree writeout. This error will repeat itself in subsequent note > trees until the subtree is forced to be unpacked. In t3305 this only > happens when the d38ec8f8 note is itself removed from the tree. >=20 > The error is not severe (no information is lost, and the notes code > is able to read/decode this tree and manipulate it correctly), but > this is nonetheless a bug in the current implementation that should > be fixed. >=20 > That said, fixing the off-by-one error is not without complications: > We must take into account that the load_subtree() call from > for_each_note_helper() (that is now done to correctly unpack the > subtree while we're writing out the notes tree) may end up inserting > unpacked non-notes into the linked list of non_note entries held by > the struct notes_tree. Since we are in the process of writing out the > notes tree, this linked list is currently in the process of being > traversed by write_each_non_note_until(). The unpacked non-notes are > necessarily inserted between the last non-note we wrote out, and the > next non-note to be written. Hence, we cannot simply hold the > next_non_note to write in struct write_each_note_data (as we would > then silently skip these newly inserted notes), but must instead > always follow the ->next pointer from the last non-note we wrote. > (This part is was caught by an existing test in t3304.) I think you have "is was" here. You probably want one or the other. > Cc: Johannes Schindelin > Cc: Brian M. Carlson I generally write my name in lower case, but I think typically we prefer to omit Cc lines in patches (unlike LKML), so it may just be better to remove these lines. > Signed-off-by: Johan Herland Patch 1 looked good to me. Your explanation here makes sense, but I must admit that I still don't understand this code, so I can't give an outright approval. I do appreciate that it comes with a test, though. I haven't tested, but I expect this series will make Dscho's patch unnecessary, so I'll drop it in my reroll unless one of you tells me to keep it. --=20 brian m. carlson: Houston, Texas, US OpenPGP: https://keybase.io/bk2204 --ffBYM5qgR8HH9Mta Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.2.19 (GNU/Linux) iQIzBAABCgAdFiEEX8OngXdrJt+H9ww3v1NdgR9S9osFAl44w1MACgkQv1NdgR9S 9ouyERAAvLCX696vfXd5unI1aM4Gdde36ouh+nqrqRotYk7HB9QsSzgX5CwzUZEf Jh8wQ7COXLuwSNGOcEsEAAZFlrHYAA7R3WXQVyvABnCn24f/+L1MeOAMDgiAW6Hu yWHbRlAEmWhJaEM9zVp/i3bo0y1VnxgZfofNtQvWedj/QCCq8byXD24vomog/x6g HEXd+HgGwCwPUtjRZI5uPGZMi1EDlaFgN3SH5rNsEEAcl1oLVLxSzWAK+S3R7s9q M+Smoc7r8AXgICwq4kQmOcBjVza7s/mswGjvFcIulqvmQANEN5lHuwdb/3cn7NYd DTqdS64SnaqlSZaJO0u59QGyzcQNqK8r8Pa5DTKt9tX0JJ0nsicE/8hS40Hk6afk tSWPY1kaer+djS0L8zdokFl/eUtI9FrZMllhjwEEsEQICh8xxPKEDss1sRTAaEZh yootBiIUoeVFLzP1Y/ekZOFaCv2zDgxC2pLsddgxUnjQ/jg45RUIDhOItBniGwT0 2JrZOC53dI9rtEaHpyXi7JzSb4wM4sb6eNZvKgk4VQgOs5hnam8C1/28iJFMasjx CCKLdJhN5mq8ThNdh+kZHFo7YO4UqWdr0anCUeRIJQ8zs5GTi3bYWt/AvqBNfBpp 5rHYmv6FP4sKHgc/IiBSsTwiX7IPPf0Zfd9apBM+tnpXSQ9WwUE= =vxpl -----END PGP SIGNATURE----- --ffBYM5qgR8HH9Mta--