From patchwork Wed May 31 23:12:35 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13262848 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 03AA9C77B73 for ; Wed, 31 May 2023 23:12:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230479AbjEaXMu (ORCPT ); Wed, 31 May 2023 19:12:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35882 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230240AbjEaXMq (ORCPT ); Wed, 31 May 2023 19:12:46 -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 0BD76A0 for ; Wed, 31 May 2023 16:12:45 -0700 (PDT) Received: by mail-yb1-xb4a.google.com with SMTP id 3f1490d57ef6-babb79a17b8so251669276.0 for ; Wed, 31 May 2023 16:12:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1685574764; x=1688166764; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=fAbyktMYeUWuFx8SBNLBrbw5SHRA0C9xAPJ1GVIEFHs=; b=LCh4j56Ae1H8Yuumyidj253fe23iUfeT4XwE/NINtLVLuVXD8aFJAUYfbs/z/8bpXe i3eh/1AFz7opXm4MA9GHMQAi9MMFooNO3wCYUdaOlEJLvyoA+4QH6aBbR9oqBU7zLgcZ GEKyj1kSPe7quohd9gaJ908I1kCLXrBJdWR+ToVYin+6EPEuszVyCKhXd3BOhcVTgxSO Ai4Dr+5oRMSnyB/IqYWa2E35LkJ5i2QT93kw83z67uwdTSPW1PFY3rOqZZo6wESKnBzr haozooLvU0ut9eUDYWVbgDwtyVwzLOCmkEGW1Xm3ndIdQXOHbN+l3es8EvxinxRKvrk1 rKFQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685574764; x=1688166764; 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=fAbyktMYeUWuFx8SBNLBrbw5SHRA0C9xAPJ1GVIEFHs=; b=DG0d87Q0io/7MWsSTlc+DFEJZ6RKgydGdvhGKT8fEdz46VJdU+M8/AGIeAYdsorpUI JuDg3NVkNcg5WTlAOQYkA6K567ITv/6p1FfOQZ385eGIuQRxCUzTd3FxB1JOzUf6Sh6R 01ld6HvDXoue8OOBxRO+E40UA3CjcUPVRzW3PNYoFJ2h5IvrA4A8NeftKlsISTLRWLdG aLOdAn8vwBbykmPgZU1O4rJgqQc02Jd7shZSfOcXSXfOD9l7teVYSl2oaAZ+tg7G4kQk ntu6AkQgyZIj/8KLEsoAvfAlsKE7mxR5NClxmKhsXyKLgcU522r3S4FL3UxO1w25uOTe xNZA== X-Gm-Message-State: AC+VfDzLUjXSeiCExtpzm/S3OZwJJlXD0ip6k4ukwwvr/HBPXKSA9rrc hgOiZ0cD8tIyT1f57h36oaCWBpdfh3uoAZ56QqaNmBmD5FzJcxTbyqhwE1qJBGWYJqhgkr/HeiR EZWDXOtUBQV64adwSPW1kZXiuRXJbTJnKTYa0B3Ox6NMrCP6HpK+FAsneZ/LqCrZn6xZ8Ft7egY 25 X-Google-Smtp-Source: ACHHUZ43anDcvjW4p0ty3tV5jghRxiF/ZKHmhm2t77sEGRT6ldaTOO15J6qHXitheI4GG45D4rELtUYvA0DpH6pHUqAY X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:2ee:ade5:9636:9867]) (user=jonathantanmy job=sendgmr) by 2002:a25:8747:0:b0:ba9:9a4f:a40 with SMTP id e7-20020a258747000000b00ba99a4f0a40mr4104195ybn.13.1685574764170; Wed, 31 May 2023 16:12:44 -0700 (PDT) Date: Wed, 31 May 2023 16:12:35 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.rc0.172.g3f132b7071-goog Message-ID: <175dc912fe4cc7f79c5106875cc9e8c30618ab7a.1685574402.git.jonathantanmy@google.com> Subject: [PATCH v2 1/3] 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 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 --- t/t4216-log-bloom.sh | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index fa9d32facf..2ec5b5b5e7 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -404,4 +404,38 @@ 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 "\xc2\xa2") + +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 'check value of version 1 changed-path' ' + (cd highbit1 && + printf "52a9" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual) +' + +test_expect_success 'version 1 changed-path used when version 1 requested' ' + (cd highbit1 && + test_bloom_filters_used "-- $CENT") +' + test_done From patchwork Wed May 31 23:12:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13262849 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 5D109C7EE29 for ; Wed, 31 May 2023 23:12:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230473AbjEaXMw (ORCPT ); Wed, 31 May 2023 19:12:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35924 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230471AbjEaXMt (ORCPT ); Wed, 31 May 2023 19:12:49 -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 86402134 for ; Wed, 31 May 2023 16:12:46 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-565d1b86a63so2664257b3.0 for ; Wed, 31 May 2023 16:12:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1685574765; x=1688166765; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=2ZxUFq+XFpm6iER00Cpqd1NymxfgQWsham2KB2kIWao=; b=hkOZKkpi7lCyOLs1BPmAW+/YuXCjIkb8KDb/Z/tAkwf7LV9olrwV0aiWvl7kYCmQen 1YrEJ2PLTl7Q14xkNOEszB7H2rRkyDxZP3P6T4ADSqtn+OctvRQDCEVs9HItDRHwiERl 0VfY4oITrd5uF69pfszL9deZl8tdAiW6HF5qJvoPWXOmyQHTSdXgkClZqyYfot6/sW/g pjkFNQg2yJQXsNDk44ypWwL2vz49TYXjtxE1wKrnIqgKkC6YbBg8ysAultILNE0YfQcc jS/7s9mCcIeCBqqOJvTNPWsaoQ2F7EoYeyi1+aQMr6DXhcCmBx5wn3GlscCJ8iKkFvlf 3qOg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685574766; x=1688166766; 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=2ZxUFq+XFpm6iER00Cpqd1NymxfgQWsham2KB2kIWao=; b=TI4t64FNEKICm42cEQJfD4fYnRRM7FaAbdpBFRwyZlExn3zbziv9YShOoc/0t0dCKt brchUJRCqRz2ECEOu1ipFx2h6/CZh12+Khx3mKiKWFcoBkfeCVILnXdGpyBBjC7g13qg ya7U8/B+vMi6/rrNPZ0NuqrRCmbrPQUczhoyKJ8iH5qjikH4rzGWlXUTnekUgSftmgAK Yk8zU7eC2Azirre4HeD+fgsx2pXxKCBXhTLrcN3n230RRinYerfe6YACXYA4Z2f20owJ jLrW9aS+XPh83LylFoX7UXpk4NEaVAxV9f+7HFUP5MkYiue8Z72OHzK6qseZyYBbWCWf ylQw== X-Gm-Message-State: AC+VfDw3Gq/jbhJvE0do8cSgZgILSE+ZELqdYZiVR7TanXWCHZ0hDrsh ERlHdhp+m7G+FsvOXdfQPOLCwESi9doyDMScKLs67H76myz/NIKNcjSUP9OPTj2AC5XXsUMQC3F hLHYWaQn3JqaCVoLwusrJO9eW2L+R4zc3IVgFKbJNpSuxeTV4Tsrhvm8m/giW/7mR89pKw1YpJu I0 X-Google-Smtp-Source: ACHHUZ5teGAoAJp5nu0HKNC2KBUmf/LoeSWM4OfVdho28J7rHex22yGYglNBXgadp5pKNntLxyvndZvKzDXyDFxPNQov X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:2ee:ade5:9636:9867]) (user=jonathantanmy job=sendgmr) by 2002:a25:bb0c:0:b0:b8f:6b84:33cb with SMTP id z12-20020a25bb0c000000b00b8f6b8433cbmr3057577ybg.11.1685574765752; Wed, 31 May 2023 16:12:45 -0700 (PDT) Date: Wed, 31 May 2023 16:12:36 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.rc0.172.g3f132b7071-goog Message-ID: <4a7553f3fb69b91c80535632c80181b51fd2d015.1685574402.git.jonathantanmy@google.com> Subject: [PATCH v2 2/3] repo-settings: introduce commitgraph.changedPathsVersion From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Derrick Stolee , Junio C Hamano 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 is to be accepted when read (and which version to write), 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 0, 1, or 2. Signed-off-by: Jonathan Tan --- Documentation/config/commitgraph.txt | 16 +++++++++++++--- commit-graph.c | 2 +- oss-fuzz/fuzz-commit-graph.c | 2 +- repo-settings.c | 6 +++++- repository.h | 2 +- 5 files changed, 21 insertions(+), 7 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 30604e4a4c..eaa10bf232 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -9,6 +9,16 @@ 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 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 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..bd448047f1 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 == 1) { 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..6cbe02681b 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 Wed May 31 23:12:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13262850 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 E6055C7EE23 for ; Wed, 31 May 2023 23:13:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230462AbjEaXM7 (ORCPT ); Wed, 31 May 2023 19:12:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35968 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230240AbjEaXMw (ORCPT ); Wed, 31 May 2023 19:12:52 -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 75DE2184 for ; Wed, 31 May 2023 16:12:48 -0700 (PDT) Received: by mail-yb1-xb4a.google.com with SMTP id 3f1490d57ef6-bb05f0e6ef9so266376276.1 for ; Wed, 31 May 2023 16:12:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1685574767; x=1688166767; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=MHQG3DsPUY73/BmPuEqo5PhogLoChsPhkPxKspUB8mU=; b=1BCwvoN+ViYoAILiKcbbYxm+Jq+tBOF4GTdUooWQ1+/YfchVYuEdN3Jz0tUPqRVIg/ 1/IvUZJMEs7NMSm2nyavRJY2wJdFiHBoQtJq1bgQT1JvMbj4ep4ridSV+ikGDABXnchB DSiqmmSz3ykHNtmma3kpXyBAFM4POl/VjlLd8TQmT8N6kE8d/OPDSEdgRdpcZhKuuri2 Q0qYLnC9doi1lXdx0dUI2pAxUNK6crfEuwCEttO9blgLUPk/hCRDFpQUefqBClZIdpMl J39sUme804ELeu3Aj5OIkz60rrGa7RG21jlOLS1m+g4MaJ7RZVWDFMBNZal1uSdI/Z1i cOFw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685574767; x=1688166767; 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=MHQG3DsPUY73/BmPuEqo5PhogLoChsPhkPxKspUB8mU=; b=dyQO8/1NUVeiJ7R9RfHvRQXFQqZZmuUc2XQVVokAwXdFLGmoyhLPQLPe/t5LtfMDbS QZzF0BjaKhYHb4C4O3XFahF3MmttK2yHmoNhcn47AMlhYw2dYygHaaU2YXx0VKGwzKfj 6emH/Pr0tcQ9JCVMLmossm9L6iH9jXcvENbEpwQynsqviqwo2/BmCibbXPOQDgaa7A2K 4fbzHG4Sasor//l/PPunZw0l/DHmy/CUF2mQpxYxYRy6P1Bj4o4DRfqfF6wk4lPVOe1B gRuM/a9jbEpzNIVRHubYDC8s9HYbjt45ymIYJZyDa+t2k5IYbv0BhcN9QA6NYBRRi9ee 6SVA== X-Gm-Message-State: AC+VfDxZhX6q/qw3C1SmyKv/y/a22lp5Sj6k0Ncg34blJkA4/xL1rivY Cbr31zxZY6fZuewGmxcQzx31Ok1OdPWS8H9yL2OyHTjMqzn1snv84lSqdh/tNYbRq9VKRoqyq7a BpLeGGuKp3Dhm8R1NLfHtlGhBNkLLz160l90w6LNz49V+rNmoY8wGKH0zXj+bRSH9RZWZM12EdN Ft X-Google-Smtp-Source: ACHHUZ7YzmodOEruRAmDPXWP1nZXIsITOcyGh236Yet1w7ihWZf32R7VCseuKj/QmMPw6iMG6wkOWypNi4id58kgwNhN X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:202:2ee:ade5:9636:9867]) (user=jonathantanmy job=sendgmr) by 2002:a25:e60e:0:b0:ba8:95dd:3ccb with SMTP id d14-20020a25e60e000000b00ba895dd3ccbmr4252876ybh.5.1685574767681; Wed, 31 May 2023 16:12:47 -0700 (PDT) Date: Wed, 31 May 2023 16:12:37 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.rc0.172.g3f132b7071-goog Message-ID: Subject: [PATCH v2 3/3] commit-graph: new filter ver. that fixes murmur3 From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Derrick Stolee , Junio C Hamano 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. 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 --- Documentation/config/commitgraph.txt | 2 +- bloom.c | 65 ++++++++++++++++++++++++++-- bloom.h | 8 ++-- commit-graph.c | 29 ++++++++++--- t/helper/test-bloom.c | 9 +++- t/t0095-bloom.sh | 8 ++++ t/t4216-log-bloom.sh | 31 +++++++++++++ 7 files changed, 139 insertions(+), 13 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index eaa10bf232..c64ee4f459 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 0 or 1. Any changed-path Bloom filters on disk that do not + write. May be 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 bd448047f1..36e6d09e74 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -302,15 +302,21 @@ 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) + if (hash_version != d->commit_graph_changed_paths_version) return 0; g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); @@ -399,11 +405,16 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, graph->read_generation_data = 1; } - if (s->commit_graph_changed_paths_version == 1) { + if (s->commit_graph_changed_paths_version == 1 + || s->commit_graph_changed_paths_version == 2) { + 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 +2313,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 < 0 + || 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 +2350,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 2ec5b5b5e7..764c6dee0f 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -438,4 +438,35 @@ 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 '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_done