From patchwork Thu Jul 13 21:42:08 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13312665 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EA73AC001DF for ; Thu, 13 Jul 2023 21:43:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234506AbjGMVnR (ORCPT ); Thu, 13 Jul 2023 17:43:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46438 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234545AbjGMVm7 (ORCPT ); Thu, 13 Jul 2023 17:42:59 -0400 Received: from mail-yb1-xb4a.google.com (mail-yb1-xb4a.google.com [IPv6:2607:f8b0:4864:20::b4a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 131DA30CA for ; Thu, 13 Jul 2023 14:42:33 -0700 (PDT) Received: by mail-yb1-xb4a.google.com with SMTP id 3f1490d57ef6-c83284edf0eso1070365276.3 for ; Thu, 13 Jul 2023 14:42:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689284536; x=1691876536; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=CK5HCzRVo86namNxblZ7MyVZoMEExkrrhKKpMQwHq/M=; b=KHJrWy7RxapIQz4WLuYL2VOF6R5/9x0WAiMAWISykiSKN/+LDmVJKUsOkJjSS/tKrg x5gs8tw2Mwe8UiS4HwqUO/5O7NjckDZz/LLh+q9yA/KU6piiPLN5vkLKjPQO/dD9VVCe pp5lMOLAQ69GeJ2Rckz1nZ2aZBOx/P7qb4KkZI2lUrOqk9hKeoUAYa+x4hKhwJn/inG/ rRAvi8bj4o2bQ6RpKjwGDFZFnN/ZwiuPLyBJWQ4v5rkNyoW68bnC1CsvseGnRU/8JhnO puE5zxJIo2GKdGBGkkheT7JdehCsNULJQ1pN5P3ztRKs3HXzu6T/ZOfTBoTiwZAyGtbZ qpNg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689284536; x=1691876536; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=CK5HCzRVo86namNxblZ7MyVZoMEExkrrhKKpMQwHq/M=; b=RmkuT0dyuhMtTi4jDbSIO1x20fa54JYF9/DI/Ke45+Jlczl0K0uihShOP6HOZp7sKN dNS/hwIOYiHUx/asjHmKNPNpCHLJCjiZVdLbkMdQ8KH1leZ2NjvzNAmLRvqk4CjCoAvd xr0SzXITQwDHc4tnBFPAkqTHf8QwDN/dJOjT6KvPU19fREECanIL1mbcgZ7jOtJ+N01N cyVOQg2xY4dLjziExETE8nABDrybdnNFzOLNW+3SD9xcVrWdpMnPJQoT8+UCTJeJeqJ0 3FUylO8fBnP4zIsexNGgRDoPyf002XcOGZT1/PY2JgGWL/9LC1rzfzgRaEe6itffueEy DCRw== X-Gm-Message-State: ABy/qLa+t2naz4zAkUFxbXu38ZfgmuqYOuDTZq+gzA9SkEMCgbNRe+dr gB/1QH95dHcOywFCNvEpII3WntXhuBgGh+gAhJiy8KKmA93R3tqW1nxfVwsG8qEliy1saeaRQ1i DIHYqH6SuOcZMPB4mZIGb7vWetG/VEzAWsqDd0YJpAZfIm7usbk21Tf9Aq8iO/JhOeaAGtWVaLt Ao X-Google-Smtp-Source: APBJJlHuuCgB1dKqZIVUI9gdPoJB8xK30j5Pdq5jn6z2YKmQTbp+Ocp5qKpeERmhzadN+wiB8m6VRkytu0e1XOPaEcxc X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:8bde:aac2:2aa0:da1a]) (user=jonathantanmy job=sendgmr) by 2002:a25:c594:0:b0:cb4:285:721a with SMTP id v142-20020a25c594000000b00cb40285721amr11171ybe.11.1689284536548; Thu, 13 Jul 2023 14:42:16 -0700 (PDT) Date: Thu, 13 Jul 2023 14:42:08 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <52e281eef0e857de93e5bdc6e0ef50065adaab2c.1689283789.git.jonathantanmy@google.com> Subject: [PATCH v5 1/4] gitformat-commit-graph: describe version 2 of BDAT From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Derrick Stolee , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The code change to Git to support version 2 will be done in subsequent commits. Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano --- Documentation/gitformat-commit-graph.txt | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/Documentation/gitformat-commit-graph.txt b/Documentation/gitformat-commit-graph.txt index 31cad585e2..3e906e8030 100644 --- a/Documentation/gitformat-commit-graph.txt +++ b/Documentation/gitformat-commit-graph.txt @@ -142,13 +142,16 @@ All multi-byte numbers are in network byte order. ==== Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional] * It starts with header consisting of three unsigned 32-bit integers: - - Version of the hash algorithm being used. We currently only support - value 1 which corresponds to the 32-bit version of the murmur3 hash + - Version of the hash algorithm being used. We currently support + value 2 which corresponds to the 32-bit version of the murmur3 hash implemented exactly as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double hashing technique using seed values 0x293ae76f and 0x7e646e2 as described in https://doi.org/10.1007/978-3-540-30494-4_26 "Bloom Filters - in Probabilistic Verification" + in Probabilistic Verification". Version 1 Bloom filters have a bug that appears + when char is signed and the repository has path names that have characters >= + 0x80; Git supports reading and writing them, but this ability will be removed + in a future version of Git. - The number of times a path is hashed and hence the number of bit positions that cumulatively determine whether a file is present in the commit. - The minimum number of bits 'b' per entry in the Bloom filter. If the filter From patchwork Thu Jul 13 21:42:09 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13312664 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id AB21BC0015E for ; Thu, 13 Jul 2023 21:43:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234478AbjGMVnP (ORCPT ); Thu, 13 Jul 2023 17:43:15 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46232 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234578AbjGMVnA (ORCPT ); Thu, 13 Jul 2023 17:43:00 -0400 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4EBF530E3 for ; Thu, 13 Jul 2023 14:42:40 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-573d70da2dcso9886707b3.1 for ; Thu, 13 Jul 2023 14:42:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689284538; x=1691876538; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=DK0ao0Orh6lg7P6T5DVt24+SXVly2XykhJWYESLEgxw=; b=kt/6P6dFGOMr9JJ+g/U29rKUKjz3jvj9VXep5imBJT8TMM1jg4gPzVlEPgL4yrh8sR /FkWc5rJ4pg9eVBfcPfqJLaFw5kncxs78M2rZmOK/6mSo3gnJOZeM86z/Euw8h8FfhHE 5nWMSkW3V09WuxlC5CHSCW6xo4p6DYLyYeI4s/7LcjAYUDAiqT7wrT537DK9tBS6tWoT QjhC1uS4gD8ZofGnl0d+hRFmtlFZzAR494S/3m18ttZpQaCsA29bCgopaulEvB8u52Is PXnjxrfChk3ShkY5jh3CD1DKg96/xrbimFk29yL3AVN56POROkYIbjeAgdKV3g/6JoPT Fr8g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689284538; x=1691876538; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=DK0ao0Orh6lg7P6T5DVt24+SXVly2XykhJWYESLEgxw=; b=UEXUV8+9tEYqjjKYkpka8+FpEjjIPZYue4jjIEU1JcSBDH7z+6euNubLTZrB1cw/08 JDy7nU+6KPtFzdrZIRizfTrXXeRaH8Q9dpmxm4UMDSGmYMLtk92w0YcHbLeLm9lZ8Y1Z ZZ4gAedSaY+o0asDm13iVKuwqgUxMlF7zbav/6LAU5bCk24zXhI3EHhPPRMsDkYeN0kT bhgxHiZCPdwNUj8akhey3b87DXxwKiPXl1a9m6oZEI668sH4ClqiPN7NV9gp8H0Biq2M wGQy5uuKmUpeM78PMt0v8wNVpG/XPR6+LmxhvkWbhVtffXw0vgLuA6ML6LO/ipTi4CqY 8Ghw== X-Gm-Message-State: ABy/qLaokBffnCOVSeyQWYTQPU8nAepnqVuuLIZtsiPgWEsmoKhK2pwY ykcifdrOiU6lteU0w8cVUz+ZCEJj8ofPJS/eFZM2gnOSrHsTab4/IK+fmqIVa7nv3f160sAbA0X FGAywWZxV0G3n8mFOeMfI6h/jeKsyAOQx8W3yO7Ta5Y2glVxDemRBUd3PnZXRTC8axiCPNOCu1H fT X-Google-Smtp-Source: APBJJlHef1SCFNqdJGqQQapP7s+9QCrdDJSGnJezWp76GttvtkfXqnc5vZ0nvtRCEtz1gaLmuffPnNQlxe3VMkZfC1xD X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:8bde:aac2:2aa0:da1a]) (user=jonathantanmy job=sendgmr) by 2002:a81:ae5b:0:b0:56d:2a88:49e5 with SMTP id g27-20020a81ae5b000000b0056d2a8849e5mr21048ywk.2.1689284538561; Thu, 13 Jul 2023 14:42:18 -0700 (PDT) Date: Thu, 13 Jul 2023 14:42:09 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <94a4c7af38525d04f3effc035084e661fe382dcd.1689283789.git.jonathantanmy@google.com> Subject: [PATCH v5 2/4] t4216: test changed path filters with high bit paths From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Derrick Stolee , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Subsequent commits will teach Git another version of changed path filter that has different behavior with paths that contain at least one character with its high bit set, so test the existing behavior as a baseline. Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano --- t/t4216-log-bloom.sh | 47 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index fa9d32facf..0cf208fdf5 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -404,4 +404,51 @@ test_expect_success 'Bloom generation backfills empty commits' ' ) ' +get_bdat_offset () { + perl -0777 -ne \ + 'print unpack("N", "$1") if /BDAT\0\0\0\0(....)/ or exit 1' \ + .git/objects/info/commit-graph +} + +get_first_changed_path_filter () { + BDAT_OFFSET=$(get_bdat_offset) && + perl -0777 -ne \ + 'print unpack("H*", substr($_, '$BDAT_OFFSET' + 12, 2))' \ + .git/objects/info/commit-graph +} + +# chosen to be the same under all Unicode normalization forms +CENT=$(printf "\302\242") + +test_expect_success 'set up repo with high bit path, version 1 changed-path' ' + git init highbit1 && + test_commit -C highbit1 c1 "$CENT" && + git -C highbit1 commit-graph write --reachable --changed-paths +' + +test_expect_success 'setup check value of version 1 changed-path' ' + (cd highbit1 && + printf "52a9" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual) +' + +# expect will not match actual if char is unsigned by default. Write the test +# in this way, so that a user running this test script can still see if the two +# files match. (It will appear as an ordinary success if they match, and a skip +# if not.) +if test_cmp highbit1/expect highbit1/actual +then + test_set_prereq SIGNED_CHAR_BY_DEFAULT +fi +test_expect_success SIGNED_CHAR_BY_DEFAULT 'check value of version 1 changed-path' ' + # Only the prereq matters for this test. + true +' + +test_expect_success 'version 1 changed-path used when version 1 requested' ' + (cd highbit1 && + test_bloom_filters_used "-- $CENT") +' + test_done From patchwork Thu Jul 13 21:42:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13312663 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7CCDAC001DF for ; Thu, 13 Jul 2023 21:43:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234388AbjGMVnN (ORCPT ); Thu, 13 Jul 2023 17:43:13 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46472 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234595AbjGMVnA (ORCPT ); Thu, 13 Jul 2023 17:43:00 -0400 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 29E9D30E8 for ; Thu, 13 Jul 2023 14:42:41 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-57059e6f9c7so17510587b3.0 for ; Thu, 13 Jul 2023 14:42:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689284540; x=1691876540; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=6ak48/ijFj0jw5zdBPImoI74xXDRoo4vJT+6IP9zYTg=; b=DxMk4G1kbQLp4035g+Dlf52S9ewj1sgGX2DnvZrNuhYLHpjCu+GgGRPHwxxjIGCq0o lOzXirezkOA/03LgXrjF8BXPcUxt0+gcslTRG5No2Jf760mTPx8U5zSIm3OwR1j4j+Hm CLWeH+gd2kMNvFCzLQ4QmsMyz4nN9TVy989GyMZFEtUR6WUba7H95Tm7cRwweDaDtI3w J4jAZi7NEhcGrtyPNG2EQ5paySpeqT9K+jMy2dMRw4nhZ6SIfggqZseCpZshfybx/aDu rQ8UP0jgHXCP3nVbUXvlOM+kmMDRfrQ+SIoU4g9NttsEnyTU8b9rIFFI0Jp43VmMoA40 AQxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689284540; x=1691876540; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=6ak48/ijFj0jw5zdBPImoI74xXDRoo4vJT+6IP9zYTg=; b=LiS7riLwMTfrhCTexFaLf1Pc9hEfyafj3sQMTvnQJbO/EZsINhmlvvbJ6dAKbVtlyb RKCvW5PPeElmqZPDmyCt/By8EoPZXM9Xt9kFiDYzwAGhJdhXX09u5uHVPMiOc036n+aR kiULCtth8lJtavYVVHkqxI9PhGa/ad2xC7N6WV+caz/3CC9qU4eOM+I1wOmcJUWX2gt2 0hdKbg8F1L9wIx6HM//U77pkybriEvQYbx6CjduKGYRMCDcqnHCMZSV81naqCDYgwwk5 lc2hj1BcHK24R5mJoN0GNBYvUAKGd3nSVgslyLazWBSFirYzckCYDGtbxY+BU+A8/vif vjEw== X-Gm-Message-State: ABy/qLaGSRgNCMxtegyQgTVwoeM2EPBnP1TQqkpiA24lbmI6tf83QInY vSXbFp6ujE/gR3fFZRWwEFxxk41mBgqzE7MXps5/NAAZtzubisWAOWwxO5VV60iTOlRhHPG3U6E 051biH+GHCnqs9z0gc9kBb2FHf9cZkMn/+jDfj7wRjIPhWEPdGv4YHa3//88Vv3BlQ1CvkpP2+S xS X-Google-Smtp-Source: APBJJlGNB+5qRgxZJubVyhrLEVnUd7ueAfme1hyG34CxZDxGjpg1cSbMezj/5hazL13hFovxdnqUQ9b+kBxSbDZhlNgS X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:8bde:aac2:2aa0:da1a]) (user=jonathantanmy job=sendgmr) by 2002:a81:c606:0:b0:56c:f903:8678 with SMTP id l6-20020a81c606000000b0056cf9038678mr12646ywi.2.1689284540176; Thu, 13 Jul 2023 14:42:20 -0700 (PDT) Date: Thu, 13 Jul 2023 14:42:10 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <131095666d414ff68416526112c8f8deb31ac9e1.1689283789.git.jonathantanmy@google.com> Subject: [PATCH v5 3/4] repo-settings: introduce commitgraph.changedPathsVersion From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Derrick Stolee , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org A subsequent commit will introduce another version of the changed-path filter in the commit graph file. In order to control which version to write (and read), a config variable is needed. Therefore, introduce this config variable. For forwards compatibility, teach Git to not read commit graphs when the config variable is set to an unsupported version. Because we teach Git this, commitgraph.readChangedPaths is now redundant, so deprecate it and define its behavior in terms of the config variable we introduce. This commit does not change the behavior of writing (Git writes changed path filters when explicitly instructed regardless of any config variable), but a subsequent commit will restrict Git such that it will only write when commitgraph.changedPathsVersion is a recognized value. Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano --- Documentation/config/commitgraph.txt | 19 ++++++++++++++++--- commit-graph.c | 2 +- oss-fuzz/fuzz-commit-graph.c | 2 +- repo-settings.c | 6 +++++- repository.h | 2 +- 5 files changed, 24 insertions(+), 7 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 30604e4a4c..07f3799e05 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -9,6 +9,19 @@ commitGraph.maxNewFilters:: commit-graph write` (c.f., linkgit:git-commit-graph[1]). commitGraph.readChangedPaths:: - If true, then git will use the changed-path Bloom filters in the - commit-graph file (if it exists, and they are present). Defaults to - true. See linkgit:git-commit-graph[1] for more information. + Deprecated. Equivalent to changedPathsVersion=-1 if true, and + changedPathsVersion=0 if false. + +commitGraph.changedPathsVersion:: + Specifies the version of the changed-path Bloom filters that Git will read and + write. May be -1, 0 or 1. Any changed-path Bloom filters on disk that do not + match the version set in this config variable will be ignored. ++ +Defaults to -1. ++ +If -1, Git will use the version of the changed-path Bloom filters in the +repository, defaulting to 1 if there are none. ++ +If 0, git will write version 1 Bloom filters when instructed to write. ++ +See linkgit:git-commit-graph[1] for more information. diff --git a/commit-graph.c b/commit-graph.c index c11b59f28b..9b72319450 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -399,7 +399,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, graph->read_generation_data = 1; } - if (s->commit_graph_read_changed_paths) { + if (s->commit_graph_changed_paths_version != 0) { pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, &graph->chunk_bloom_indexes); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, diff --git a/oss-fuzz/fuzz-commit-graph.c b/oss-fuzz/fuzz-commit-graph.c index 914026f5d8..b56731f51a 100644 --- a/oss-fuzz/fuzz-commit-graph.c +++ b/oss-fuzz/fuzz-commit-graph.c @@ -18,7 +18,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) * possible. */ the_repository->settings.commit_graph_generation_version = 2; - the_repository->settings.commit_graph_read_changed_paths = 1; + the_repository->settings.commit_graph_changed_paths_version = 1; g = parse_commit_graph(&the_repository->settings, (void *)data, size); repo_clear(the_repository); free_commit_graph(g); diff --git a/repo-settings.c b/repo-settings.c index 3dbd3f0e2e..e3b6565ffc 100644 --- a/repo-settings.c +++ b/repo-settings.c @@ -24,6 +24,7 @@ void prepare_repo_settings(struct repository *r) int value; const char *strval; int manyfiles; + int readChangedPaths; if (!r->gitdir) BUG("Cannot add settings for uninitialized repository"); @@ -54,7 +55,10 @@ void prepare_repo_settings(struct repository *r) /* Commit graph config or default, does not cascade (simple) */ repo_cfg_bool(r, "core.commitgraph", &r->settings.core_commit_graph, 1); repo_cfg_int(r, "commitgraph.generationversion", &r->settings.commit_graph_generation_version, 2); - repo_cfg_bool(r, "commitgraph.readchangedpaths", &r->settings.commit_graph_read_changed_paths, 1); + repo_cfg_bool(r, "commitgraph.readchangedpaths", &readChangedPaths, 1); + repo_cfg_int(r, "commitgraph.changedpathsversion", + &r->settings.commit_graph_changed_paths_version, + readChangedPaths ? -1 : 0); repo_cfg_bool(r, "gc.writecommitgraph", &r->settings.gc_write_commit_graph, 1); repo_cfg_bool(r, "fetch.writecommitgraph", &r->settings.fetch_write_commit_graph, 0); diff --git a/repository.h b/repository.h index e8c67ffe16..1f1c32a6dd 100644 --- a/repository.h +++ b/repository.h @@ -32,7 +32,7 @@ struct repo_settings { int core_commit_graph; int commit_graph_generation_version; - int commit_graph_read_changed_paths; + int commit_graph_changed_paths_version; int gc_write_commit_graph; int gc_cruft_packs; int fetch_write_commit_graph; From patchwork Thu Jul 13 21:42:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13312666 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3B578C0015E for ; Thu, 13 Jul 2023 21:43:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234514AbjGMVnT (ORCPT ); Thu, 13 Jul 2023 17:43:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46498 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234629AbjGMVnC (ORCPT ); Thu, 13 Jul 2023 17:43:02 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AE23530EE for ; Thu, 13 Jul 2023 14:42:42 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-5734d919156so10256907b3.3 for ; Thu, 13 Jul 2023 14:42:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689284542; x=1691876542; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=pK+wIImnEPYj5Y8MsUR9ydGw35AR2uY8OW7UTlHgS0o=; b=KPzWCT2A3og+NioY741OtULsPNqPna6Mt78DccZsKrTzSysLGOtQm6PeOXpzBvGHcu Qk13k9ON+AAX+nbkqJt5NF9E9dsS/wNY/j1f56c4NsUaOJW15tyCZasgn6DLrNj3PEr9 JnpYPFH7Xz9eOmm5D0go/a4RffZdRaB7kFWCYMQaIigaTRNWCXVIyxiPbfeXPoTKLhcK MxdXGHTnIogKYXui8scSml1GYngtAGSYllXUfWc7To3Xwve0Z1cEJQ/cSX43A6xc0uZB t65r0/X/5CJ7N02rYPQfNKImAiasX5Ae7DMIRGrRUbXUf6ZnmyT7/j/9WJvn3btcCjKn 7IqQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689284542; x=1691876542; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=pK+wIImnEPYj5Y8MsUR9ydGw35AR2uY8OW7UTlHgS0o=; b=YzJPZxufnrOKLgw7YwUb7HKPJ2HhatIkhK/gSYNriCW9I/lPQ/J5L6D/OD4CKwi2It Ed9086Mb2c+4/ZBz+1SbOtAYvwtLw+gGkhls78h422gQ0gz3ZUlPRznnFe9fmY3n/KWI SO7azGRSajlr7u4QNgawZIxnKm1OOteFrYJPPu6I3jUXJSV1FXJ1x8mWl/SZN64q0f4r jlYPbotiIHIJkYhYheu4v7WUZr8F08S4zwLzG4iyH4DkW6OgksruvUvonpQF5xjH8rjO AMPJqLBtA5s5kJAzVfk6c/HmsZVwQtj/S+0+Z3saklzWugW6X7tzVxIeBFQSetWWADBu 5mzA== X-Gm-Message-State: ABy/qLY1zA9DZy/yWk34McaczbHNPfMLjhusHq3KXW/tFvDCwkbNiOG2 hKL+ZMZD/QdsnDH2xErhxzydZXkkiUhY6E+xyeOzZTCI7qmABJviwd3Cl7Ft33kmaiFOoogEad5 igno13W0blC7BvRoEOBqcKDZTBHDWw17IgmHhLgneVd3zfcD970P+HLAVgDfWzpnnGw8qv8FBL8 ZI X-Google-Smtp-Source: APBJJlHUA8apRjGgIDXp2adc0Kd2YeZhTe1JQjZDSA2aiylrrFFzJb/lXhKFXoOShSGOspxOmzdBU9thAdn8AfrhFh03 X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:8bde:aac2:2aa0:da1a]) (user=jonathantanmy job=sendgmr) by 2002:a81:b306:0:b0:577:4540:905d with SMTP id r6-20020a81b306000000b005774540905dmr20810ywh.8.1689284542545; Thu, 13 Jul 2023 14:42:22 -0700 (PDT) Date: Thu, 13 Jul 2023 14:42:11 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <47ba89c565d3383a8a14272fe52ac274be82d0be.1689283789.git.jonathantanmy@google.com> Subject: [PATCH v5 4/4] commit-graph: new filter ver. that fixes murmur3 From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Derrick Stolee , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The murmur3 implementation in bloom.c has a bug when converting series of 4 bytes into network-order integers when char is signed (which is controllable by a compiler option, and the default signedness of char is platform-specific). When a string contains characters with the high bit set, this bug causes results that, although internally consistent within Git, does not accord with other implementations of murmur3 and even with Git binaries that were compiled with different signedness of char. This bug affects both how Git writes changed path filters to disk and how Git interprets changed path filters on disk. Therefore, introduce a new version (2) of changed path filters that corrects this problem. The existing version (1) is still supported and is still the default, but users should migrate away from it as soon as possible. Because this bug only manifests with characters that have the high bit set, it may be possible that some (or all) commits in a given repo would have the same changed path filter both before and after this fix is applied. However, in order to determine whether this is the case, the changed paths would first have to be computed, at which point it is not much more expensive to just compute a new changed path filter. So this patch does not include any mechanism to "salvage" changed path filters from repositories. There is also no "mixed" mode - for each invocation of Git, reading and writing changed path filters are done with the same version number; this version number may be explicitly stated (typically if the user knows which version they need) or automatically determined from the version of the existing changed path filters in the repository. There is a change in write_commit_graph(). graph_read_bloom_data() makes it possible for chunk_bloom_data to be non-NULL but bloom_filter_settings to be NULL, which causes a segfault later on. I produced such a segfault while developing this patch, but couldn't find a way to reproduce it neither after this complete patch (or before), but in any case it seemed like a good thing to include that might help future patch authors. The value in t0095 was obtained from another murmur3 implementation using the following Go source code: package main import "fmt" import "github.com/spaolacci/murmur3" func main() { fmt.Printf("%x\n", murmur3.Sum32([]byte("Hello world!"))) fmt.Printf("%x\n", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff})) } Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano --- Documentation/config/commitgraph.txt | 2 +- bloom.c | 65 +++++++++++++++++++++++-- bloom.h | 8 ++-- commit-graph.c | 31 ++++++++++-- t/helper/test-bloom.c | 9 +++- t/t0095-bloom.sh | 8 ++++ t/t4216-log-bloom.sh | 72 +++++++++++++++++++++++++++- 7 files changed, 181 insertions(+), 14 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 07f3799e05..b93ccfba8f 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -14,7 +14,7 @@ commitGraph.readChangedPaths:: commitGraph.changedPathsVersion:: Specifies the version of the changed-path Bloom filters that Git will read and - write. May be -1, 0 or 1. Any changed-path Bloom filters on disk that do not + write. May be -1, 0, 1, or 2. Any changed-path Bloom filters on disk that do not match the version set in this config variable will be ignored. + Defaults to -1. diff --git a/bloom.c b/bloom.c index d0730525da..915d8e5a31 100644 --- a/bloom.c +++ b/bloom.c @@ -65,7 +65,64 @@ static int load_bloom_filter_from_graph(struct commit_graph *g, * Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len) +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len) +{ + const uint32_t c1 = 0xcc9e2d51; + const uint32_t c2 = 0x1b873593; + const uint32_t r1 = 15; + const uint32_t r2 = 13; + const uint32_t m = 5; + const uint32_t n = 0xe6546b64; + int i; + uint32_t k1 = 0; + const char *tail; + + int len4 = len / sizeof(uint32_t); + + uint32_t k; + for (i = 0; i < len4; i++) { + uint32_t byte1 = (uint32_t)(unsigned char)data[4*i]; + uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8; + uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16; + uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24; + k = byte1 | byte2 | byte3 | byte4; + k *= c1; + k = rotate_left(k, r1); + k *= c2; + + seed ^= k; + seed = rotate_left(seed, r2) * m + n; + } + + tail = (data + len4 * sizeof(uint32_t)); + + switch (len & (sizeof(uint32_t) - 1)) { + case 3: + k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16; + /*-fallthrough*/ + case 2: + k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8; + /*-fallthrough*/ + case 1: + k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0; + k1 *= c1; + k1 = rotate_left(k1, r1); + k1 *= c2; + seed ^= k1; + break; + } + + seed ^= (uint32_t)len; + seed ^= (seed >> 16); + seed *= 0x85ebca6b; + seed ^= (seed >> 13); + seed *= 0xc2b2ae35; + seed ^= (seed >> 16); + + return seed; +} + +static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len) { const uint32_t c1 = 0xcc9e2d51; const uint32_t c2 = 0x1b873593; @@ -130,8 +187,10 @@ void fill_bloom_key(const char *data, int i; const uint32_t seed0 = 0x293ae76f; const uint32_t seed1 = 0x7e646e2c; - const uint32_t hash0 = murmur3_seeded(seed0, data, len); - const uint32_t hash1 = murmur3_seeded(seed1, data, len); + const uint32_t hash0 = (settings->hash_version == 2 + ? murmur3_seeded_v2 : murmur3_seeded_v1)(seed0, data, len); + const uint32_t hash1 = (settings->hash_version == 2 + ? murmur3_seeded_v2 : murmur3_seeded_v1)(seed1, data, len); key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t)); for (i = 0; i < settings->num_hashes; i++) diff --git a/bloom.h b/bloom.h index adde6dfe21..0c33ae282c 100644 --- a/bloom.h +++ b/bloom.h @@ -7,9 +7,11 @@ struct repository; struct bloom_filter_settings { /* * The version of the hashing technique being used. - * We currently only support version = 1 which is + * The newest version is 2, which is * the seeded murmur3 hashing technique implemented - * in bloom.c. + * in bloom.c. Bloom filters of version 1 were created + * with prior versions of Git, which had a bug in the + * implementation of the hash function. */ uint32_t hash_version; @@ -75,7 +77,7 @@ struct bloom_key { * Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len); +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len); void fill_bloom_key(const char *data, size_t len, diff --git a/commit-graph.c b/commit-graph.c index 9b72319450..c50107eed5 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -302,16 +302,25 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start, return 0; } +struct graph_read_bloom_data_data { + struct commit_graph *g; + int *commit_graph_changed_paths_version; +}; + static int graph_read_bloom_data(const unsigned char *chunk_start, size_t chunk_size, void *data) { - struct commit_graph *g = data; + struct graph_read_bloom_data_data *d = data; + struct commit_graph *g = d->g; uint32_t hash_version; g->chunk_bloom_data = chunk_start; hash_version = get_be32(chunk_start); - if (hash_version != 1) - return 0; + if (*d->commit_graph_changed_paths_version == -1) { + *d->commit_graph_changed_paths_version = hash_version; + } else if (hash_version != *d->commit_graph_changed_paths_version) { + return 0; + } g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); g->bloom_filter_settings->hash_version = hash_version; @@ -400,10 +409,14 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, } if (s->commit_graph_changed_paths_version != 0) { + struct graph_read_bloom_data_data data = { + .g = graph, + .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version + }; pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, &graph->chunk_bloom_indexes); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - graph_read_bloom_data, graph); + graph_read_bloom_data, &data); } if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) { @@ -2302,6 +2315,14 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 0; + if (r->settings.commit_graph_changed_paths_version < -1 + || r->settings.commit_graph_changed_paths_version > 2) { + warning(_("attempting to write a commit-graph, but 'commitgraph.changedPathsVersion' (%d) is not supported"), + r->settings.commit_graph_changed_paths_version); + return 0; + } + bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2 + ? 2 : 1; bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY", bloom_settings.bits_per_entry); bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES", @@ -2331,7 +2352,7 @@ int write_commit_graph(struct object_directory *odb, g = ctx->r->objects->commit_graph; /* We have changed-paths already. Keep them in the next graph */ - if (g && g->chunk_bloom_data) { + if (g && g->bloom_filter_settings) { ctx->changed_paths = 1; ctx->bloom_settings = g->bloom_filter_settings; } diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c index 6c900ca668..34b8dd9164 100644 --- a/t/helper/test-bloom.c +++ b/t/helper/test-bloom.c @@ -48,6 +48,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid) static const char *bloom_usage = "\n" " test-tool bloom get_murmur3 \n" +" test-tool bloom get_murmur3_seven_highbit\n" " test-tool bloom generate_filter [...]\n" " test-tool bloom get_filter_for_commit \n"; @@ -62,7 +63,13 @@ int cmd__bloom(int argc, const char **argv) uint32_t hashed; if (argc < 3) usage(bloom_usage); - hashed = murmur3_seeded(0, argv[2], strlen(argv[2])); + hashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2])); + printf("Murmur3 Hash with seed=0:0x%08x\n", hashed); + } + + if (!strcmp(argv[1], "get_murmur3_seven_highbit")) { + uint32_t hashed; + hashed = murmur3_seeded_v2(0, "\x99\xaa\xbb\xcc\xdd\xee\xff", 7); printf("Murmur3 Hash with seed=0:0x%08x\n", hashed); } diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh index b567383eb8..c8d84ab606 100755 --- a/t/t0095-bloom.sh +++ b/t/t0095-bloom.sh @@ -29,6 +29,14 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' ' test_cmp expect actual ' +test_expect_success 'compute unseeded murmur3 hash for test string 3' ' + cat >expect <<-\EOF && + Murmur3 Hash with seed=0:0xa183ccfd + EOF + test-tool bloom get_murmur3_seven_highbit >actual && + test_cmp expect actual +' + test_expect_success 'compute bloom key for empty string' ' cat >expect <<-\EOF && Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004| diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 0cf208fdf5..6ff26e5af5 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -410,6 +410,13 @@ get_bdat_offset () { .git/objects/info/commit-graph } +get_changed_path_filter_version () { + BDAT_OFFSET=$(get_bdat_offset) && + perl -0777 -ne \ + 'print unpack("H*", substr($_, '$BDAT_OFFSET', 4))' \ + .git/objects/info/commit-graph +} + get_first_changed_path_filter () { BDAT_OFFSET=$(get_bdat_offset) && perl -0777 -ne \ @@ -426,7 +433,7 @@ test_expect_success 'set up repo with high bit path, version 1 changed-path' ' git -C highbit1 commit-graph write --reachable --changed-paths ' -test_expect_success 'setup check value of version 1 changed-path' ' +test_expect_success 'check value of version 1 changed-path' ' (cd highbit1 && printf "52a9" >expect && get_first_changed_path_filter >actual && @@ -451,4 +458,67 @@ test_expect_success 'version 1 changed-path used when version 1 requested' ' test_bloom_filters_used "-- $CENT") ' +test_expect_success 'version 1 changed-path not used when version 2 requested' ' + (cd highbit1 && + git config --add commitgraph.changedPathsVersion 2 && + test_bloom_filters_not_used "-- $CENT") +' + +test_expect_success 'version 1 changed-path used when autodetect requested' ' + (cd highbit1 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- $CENT") +' + +test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' ' + test_commit -C highbit1 c1double "$CENT$CENT" && + git -C highbit1 commit-graph write --reachable --changed-paths && + (cd highbit1 && + git config --add commitgraph.changedPathsVersion -1 && + printf "00000001" >expect && + get_changed_path_filter_version >actual && + test_cmp expect actual) +' + +test_expect_success 'set up repo with high bit path, version 2 changed-path' ' + git init highbit2 && + git -C highbit2 config --add commitgraph.changedPathsVersion 2 && + test_commit -C highbit2 c2 "$CENT" && + git -C highbit2 commit-graph write --reachable --changed-paths +' + +test_expect_success 'check value of version 2 changed-path' ' + (cd highbit2 && + printf "c01f" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual) +' + +test_expect_success 'version 2 changed-path used when version 2 requested' ' + (cd highbit2 && + test_bloom_filters_used "-- $CENT") +' + +test_expect_success 'version 2 changed-path not used when version 1 requested' ' + (cd highbit2 && + git config --add commitgraph.changedPathsVersion 1 && + test_bloom_filters_not_used "-- $CENT") +' + +test_expect_success 'version 2 changed-path used when autodetect requested' ' + (cd highbit2 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- $CENT") +' + +test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' ' + test_commit -C highbit2 c2double "$CENT$CENT" && + git -C highbit2 commit-graph write --reachable --changed-paths && + (cd highbit2 && + git config --add commitgraph.changedPathsVersion -1 && + printf "00000002" >expect && + get_changed_path_filter_version >actual && + test_cmp expect actual) +' + test_done