From patchwork Tue Jan 16 22:09:06 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521286 Received: from mail-qv1-f46.google.com (mail-qv1-f46.google.com [209.85.219.46]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7AF1C20B0C for ; Tue, 16 Jan 2024 22:09:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442949; cv=none; b=b78f8HrEMPMFHp1KUjzyOrwh/Ti8kfTpo9Kz6TUP+7JVKQiO5i/8W03i0hED2Rprnc9/6Vqu3bjAyPKU40C5UuzIP93St3Fg06qfC77QPoRWDN/8O4W1i9NRTES9rrbQxzPRWNdyHxYsgewJjERc09JdH9w5Gno3vVi9sg6C0YU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442949; c=relaxed/simple; bh=6QabK8iOkfVQ8hAGV/TkKsGiqU6EhL/BjlUs3t2FC0A=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=CjicT3bH/oBIUJ6sfPA75xM/IgfVeHgkBCzLb3ibmmfuEIw0BsH4RAquXgkQD0Oe/bETOLnpuEi21eQ/45rv7OX3cdJivxxMLjafa4whnq/LU0QlV8zPnwWSxY84QIGi98l7x5UGzpL2NP03jV+4oe2uVpVjA8G4r+H3tm4kaEY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=DVAB2bzk; arc=none smtp.client-ip=209.85.219.46 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="DVAB2bzk" Received: by mail-qv1-f46.google.com with SMTP id 6a1803df08f44-680a06cc763so66642966d6.1 for ; Tue, 16 Jan 2024 14:09:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442947; x=1706047747; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=7G+r5rzKbT5AgMVhSAburbO0Bdu+mDyRx3iT4gSvO6o=; b=DVAB2bzkiF0ada92tzan9iaSLencsepwGYjg38j80BR9QhepgwvOLuZW6YowlCNAuP Pkj1TPiib0ZKNYqx2r4Fcy9slyzdAPxaLBobTHa9G7Cy8kiJ6ZmYMPr90fhZ+94zOHKO 5WiVFBM12XjgQkOtvHUyJuOVuWdeLhA+Cn98Exj3jQ9G9g038ygC6QUcTqGyeGZOaLfd lLJIspHzkSTcfolMAYK72ApHpR6BYYuS0/P3EIS1M5mklGcQL4G89htAIVU1Uhv4HMCv tBPH+sX+w4fn8hy4qrHsTIqQvp9U84Db/5qkKmYbQ3cb43Zt6HdBCfoX+6Nraz9u0sYP U+6g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442947; x=1706047747; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=7G+r5rzKbT5AgMVhSAburbO0Bdu+mDyRx3iT4gSvO6o=; b=UgtsWWuv7JlypX90z78G4ydxevM9+UZAFBFeTvk0xJil6hg5L/KqkA+ZF2B813bT/S XeUMknsi/4rigkJPJOGIqRWYMqDCjDEaQhY0crA2JXoH2BFiNg/S5JEHsFbQnNsFMmXs UL9l9LH8KcxuoSVPDhlJv96BSwiJb799IHGFeyjlksB/MvfT3p6d4MkP5N7DTvMcnSCQ zOyErWgWG42l79pzXrkckHWwvdFGXK876YU8kwWhStK9+ks0zJArTvJOD3SwpezLXWJE R2qDKaAWb/XvQgGo6ShI7LHrzB1wFYbVVwukOC1IEx0m54Qg02UQsKviWGnZbKKKZJvo w+jA== X-Gm-Message-State: AOJu0YyQpPIDsIuZA3Hh7Pfz77893iFk+p3ejH4Jc8klND5RuwhLjN5m 2bjC/JGx3I1x7AfgWBFn3svohXiO/1a408mZIpD12WRr06rNNg== X-Google-Smtp-Source: AGHT+IFbxgfCeuELFKL/LXIQhIPkoF378X5SZvY+cbZQG/KHyEWFup2Qf/94AsqwVBjL0L3wdIIXaA== X-Received: by 2002:a05:6214:5290:b0:681:68dc:58eb with SMTP id kj16-20020a056214529000b0068168dc58ebmr2609587qvb.88.1705442947201; Tue, 16 Jan 2024 14:09:07 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id x4-20020ad440c4000000b0068111bbd2ccsm4463334qvp.143.2024.01.16.14.09.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:07 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:06 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 01/17] t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()` Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The existing implementation of test_bloom_filters_not_used() asserts that the Bloom filter sub-system has not been initialized at all, by checking for the absence of any data from it from trace2. In the following commit, it will become possible to load Bloom filters without using them (e.g., because the `commitGraph.changedPathVersion` introduced later in this series is incompatible with the hash version with which the commit-graph's Bloom filters were written). When this is the case, it's possible to initialize the Bloom filter sub-system, while still not using any Bloom filters. When this is the case, check that the data dump from the Bloom sub-system is all zeros, indicating that no filters were used. Signed-off-by: Taylor Blau --- t/t4216-log-bloom.sh | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 2ba0324a69..b7baf49d62 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -82,7 +82,19 @@ test_bloom_filters_used () { test_bloom_filters_not_used () { log_args=$1 setup "$log_args" && - ! grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf" && + + if grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf" + then + # if the Bloom filter system is initialized, ensure that no + # filters were used + data="statistics:{" + data="$data\"filter_not_present\":0," + data="$data\"maybe\":0," + data="$data\"definitely_not\":0," + data="$data\"false_positive\":0}" + + grep -q "$data" "$TRASH_DIRECTORY/trace.perf" + fi && test_cmp log_wo_bloom log_w_bloom } From patchwork Tue Jan 16 22:09:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521287 Received: from mail-yw1-f179.google.com (mail-yw1-f179.google.com [209.85.128.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6588B20B35 for ; Tue, 16 Jan 2024 22:09:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442952; cv=none; b=XPJQwEcsr+KAWGJzOKH2TjNEYvQDcDwRB1Chp18XR8cye8VGSgQFn6Mj32d09XUGbg3M6Q3JYCuMLX/40zhXGmvjkbVGzOV6VgbcQ5ZLum5UJhrThj3hm964vL6AtSbvqqAqgJIW859e/v2bDEV2xJpjaB83BweumnbnE+RTtTc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442952; c=relaxed/simple; bh=W3g1coO4XrHXlj+TtIyfLqDZyhQ1zbjoKSqww7KFqMU=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:Content-Transfer-Encoding:In-Reply-To; b=A4One6LF5uXxYqqXmXvN8d6K4xoyiyGFLjsVIMlq+e/e6hOGQpyfbeK5EbhijA7qn8NR/f8dqoirmI8OZR9WaZuzElYmBLtYG5FDnWwqZuSP5VSYvKDXmD6qfIzhAvlw5Yy1TBXw3zw/Ch7bIM9BcrTWySJlSEVIhmCWI/GVryg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=ViOnmTxx; arc=none smtp.client-ip=209.85.128.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="ViOnmTxx" Received: by mail-yw1-f179.google.com with SMTP id 00721157ae682-5f0c0ca5ef1so101846637b3.2 for ; Tue, 16 Jan 2024 14:09:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442950; x=1706047750; darn=vger.kernel.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=HmBKDFIyiLwCv3D+Rmc4vI3oa2PvVVFnnjge3s7QzNI=; b=ViOnmTxx7uoYp5fJ18rsDsIFC27I12mDcMilhb2zYM3ZJbmmvLGz0LeozkgSzvaUtS m4tBcWzHzPePJtv6kVguEPeDN4m5LPv9T8dSZ9HM+QMcyDGB5Bwfy3cS5IrF3dIh/DRQ IE2KxcH7K2gPPyF4JJyy4S3qZreDRVFQiG/SpB7jHEy75BXBHfy9ncmcciKWEe7k8KO5 vKG2NDY5rDv8Zo6xFg6TIOHPbDS/RnDR6vCY6ECsVKZf4rYdzLD5g5gAFP4ZBDtBynOh djl+QbKT3NUBpKmkjYAZDOKU2cIOW05ZId6yLCl9iDdq9SSq74SnfKuwEja/nb2l7wgN qgWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442950; x=1706047750; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=HmBKDFIyiLwCv3D+Rmc4vI3oa2PvVVFnnjge3s7QzNI=; b=mGdDA7tWBp4h7GebryXiHzC72KZGLfyPZA6TCm9BxjqKFRqaEdXKYzyWuE2qw6nVAQ JS6q5rjqD/aVu61vO9MgY/yEAIuwMb47BV6o7ISt0RsDTHYOmLsN0UA32xJfCdoyNwaI KrMkwB67TOTXjI6WvDGeoyNRBJTO7mHD1kAvkyfRDfmiaDN1WsbwYdaAMlUECvkBo/Ea i9C1OALkSrIDs1kzy0pn/9iiwLsieksrOMaOC06fLxCqGEH06GhrmZAmsVd3M2V6AAej imDeZY1GoHcQ0Mh30L3vwwLf876A59su/o7B3fKw4uVG6fvO4OuBIpzq5Ft1OvwkM+qN JxXg== X-Gm-Message-State: AOJu0Yw06QYZvADlrb8IGga0y7d7SGIXpi5LVXh5wKl31wTMNDzyfuoZ vMCci/D0rRagq5MjwRm3g27bfkt06U7byUM1uDimTIH15HzWLw== X-Google-Smtp-Source: AGHT+IFcQXwg7QbSi5+qNAuv59OYH+yG3HO1t5zPPIP+kdEbST043u+HHXUnDf9WgcbLm+Wkptu0nA== X-Received: by 2002:a81:d101:0:b0:5f2:852b:3d08 with SMTP id w1-20020a81d101000000b005f2852b3d08mr5816293ywi.33.1705442950012; Tue, 16 Jan 2024 14:09:10 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id p15-20020a0cf68f000000b006817850b81esm346249qvn.136.2024.01.16.14.09.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:09 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:08 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 02/17] revision.c: consult Bloom filters for root commits Message-ID: <8f32fd5f460accd07f0d8c0a63f1a4580817a341.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The commit-graph stores changed-path Bloom filters which represent the set of paths included in a tree-level diff between a commit's root tree and that of its parent. When a commit has no parents, the tree-diff is computed against that commit's root tree and the empty tree. In other words, every path in that commit's tree is stored in the Bloom filter (since they all appear in the diff). Consult these filters during pathspec-limited traversals in the function `rev_same_tree_as_empty()`. Doing so yields a performance improvement where we can avoid enumerating the full set of paths in a parentless commit's root tree when we know that the path(s) of interest were not listed in that commit's changed-path Bloom filter. Suggested-by: SZEDER Gábor Original-patch-by: Jonathan Tan Signed-off-by: Taylor Blau --- revision.c | 26 ++++++++++++++++++++++---- t/t4216-log-bloom.sh | 8 ++++++-- 2 files changed, 28 insertions(+), 6 deletions(-) diff --git a/revision.c b/revision.c index 2424c9bd67..0e6f7d02b6 100644 --- a/revision.c +++ b/revision.c @@ -833,17 +833,28 @@ static int rev_compare_tree(struct rev_info *revs, return tree_difference; } -static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit) +static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit, + int nth_parent) { struct tree *t1 = repo_get_commit_tree(the_repository, commit); + int bloom_ret = -1; if (!t1) return 0; + if (!nth_parent && revs->bloom_keys_nr) { + bloom_ret = check_maybe_different_in_bloom_filter(revs, commit); + if (!bloom_ret) + return 1; + } + tree_difference = REV_TREE_SAME; revs->pruning.flags.has_changes = 0; diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning); + if (bloom_ret == 1 && tree_difference == REV_TREE_SAME) + count_bloom_filter_false_positive++; + return tree_difference == REV_TREE_SAME; } @@ -881,7 +892,7 @@ static int compact_treesame(struct rev_info *revs, struct commit *commit, unsign if (nth_parent != 0) die("compact_treesame %u", nth_parent); old_same = !!(commit->object.flags & TREESAME); - if (rev_same_tree_as_empty(revs, commit)) + if (rev_same_tree_as_empty(revs, commit, nth_parent)) commit->object.flags |= TREESAME; else commit->object.flags &= ~TREESAME; @@ -977,7 +988,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) return; if (!commit->parents) { - if (rev_same_tree_as_empty(revs, commit)) + /* + * Pretend as if we are comparing ourselves to the + * (non-existent) first parent of this commit object. Even + * though no such parent exists, its changed-path Bloom filter + * (if one exists) is relative to the empty tree, using Bloom + * filters is allowed here. + */ + if (rev_same_tree_as_empty(revs, commit, 0)) commit->object.flags |= TREESAME; return; } @@ -1058,7 +1076,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) case REV_TREE_NEW: if (revs->remove_empty_trees && - rev_same_tree_as_empty(revs, p)) { + rev_same_tree_as_empty(revs, p, nth_parent)) { /* We are adding all the specified * paths from this parent, so the * history beyond this parent is not diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index b7baf49d62..cc6ebc8140 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -88,7 +88,11 @@ test_bloom_filters_not_used () { # if the Bloom filter system is initialized, ensure that no # filters were used data="statistics:{" - data="$data\"filter_not_present\":0," + # unusable filters (e.g., those computed with a + # different value of commitGraph.changedPathsVersion) + # are counted in the filter_not_present bucket, so any + # value is OK there. + data="$data\"filter_not_present\":[0-9][0-9]*," data="$data\"maybe\":0," data="$data\"definitely_not\":0," data="$data\"false_positive\":0}" @@ -175,7 +179,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' ' test_bloom_filters_used_when_some_filters_are_missing () { log_args=$1 - bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":9" + bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":10" setup "$log_args" && grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" && test_cmp log_wo_bloom log_w_bloom From patchwork Tue Jan 16 22:09:11 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521288 Received: from mail-oi1-f171.google.com (mail-oi1-f171.google.com [209.85.167.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0E74A20DC4 for ; Tue, 16 Jan 2024 22:09:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442955; cv=none; b=g7Audtzk5ObxgUrWUhMIiIsiQW9wBVgEmQpuPqpGu3DjksPOX2cX00lEqRENZMLkXO6SzzH7aqjNNlC8zEq4KXA+vVpRvV0mYhy8M42o+zUgfKdEddQaCJ0+ar5x0qf4W8GJX7ZNCDw73EW+E/A5Hm+w3ub6D+i4ZTxMMSdxTrE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442955; c=relaxed/simple; bh=vQob6MiOc1Bz7W8/f5xsbZ/bSC59BpK4zHtnXhPAUC0=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:Content-Transfer-Encoding:In-Reply-To; b=WYF9xJ3x4M6F6Nyj6kzJAVbhkUctUBL/nvmTR8RSrJ93XAzSCz+3ybVQIzD+FzmJdc/xZH1MhZ1PAKVcDfme0GibVOeQfLZNkuI/5AcisSpEaERJUNQP9CknKGCtoRivktuwI6QIXmPathZvaqaIDAghvJWlgPTQ/Ul0o47FnP0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=W2PYfYQc; arc=none smtp.client-ip=209.85.167.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="W2PYfYQc" Received: by mail-oi1-f171.google.com with SMTP id 5614622812f47-3bd5c4cffefso4470016b6e.1 for ; Tue, 16 Jan 2024 14:09:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442953; x=1706047753; darn=vger.kernel.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=t668Q1+nUCAaFkiO1yqc4BI6/hd+nKN9qy0/HflmkC4=; b=W2PYfYQcAdaYnZ7NkhB4m/zhVLn8mVUoNAbz3612vkWfezPP4YPRl1DIueZX5hG5lz FfruPcdgDuDwMnPpLxppUUyXw/ScCaql3WJec6TZFkXgq4gKnE3MVuEOhvvYTATaZ8ju ysycfDkdZitbTfWOTS4mPtl/5+65k+Ox/y0oRrgex+ojHVczaETpxkMcQKTNuNwYf3lw KWIM2rHeFa4bZG8HHXBHNM+wM6scZfWuF6DraXIL8Chrorvb5/zds/Npxx1RckO7QRQq zXRxM+WBRcPBiFulYBxBbmMDRntTl77YK+k/8/6XM/2nE7zl8DBtR+h5rfe5yYbv/R5M hJfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442953; x=1706047753; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=t668Q1+nUCAaFkiO1yqc4BI6/hd+nKN9qy0/HflmkC4=; b=MPVJtt1sacVRCHdLCkkI3tjyX7vRj40hwezv8XMvkQ+UNiiEdaPchHfpOdKf6dKe4j LF6krBrPgn/rg0dKmnmcA2wXwSgndsTITBQdgIHNREbpp/+g4Z0MbAbWY4WUoumUYhHm 9HG/0yVbz7EnbuPNBJzEWxmzIhjX3iHJ4Cdl4iXjxz5vf7aYYd1AQlevIU4y5pHW2lcH UZb+ULfNTlKkPo00/aNhMUna+GNrty4SS0XQnzWkCDWChFHDEr/reLsHtjVwIF8gZeKZ 6ZHxO7E7w7IPPIAEjf/SuKzyVByJ5ASM+DRKlPZ1Fo3Xoy3BRXYt9KzjW5pG6f6+l+4k 3SmQ== X-Gm-Message-State: AOJu0Yxs+KjCA7IP97GGr3PebppB+H8nAjLEbWJo8Xhb01isoIx5FNn8 luzsXlSg3vWec77R3566i6RnT6PKYvQOtCYp2TfC4dQlu5VpMg== X-Google-Smtp-Source: AGHT+IGUYh4CYoDBywe5tNy2o7xtXyCa568qg7mBqsOKbToHfnAO0+LNFKli2VrDE0JBj6kQyEtNqw== X-Received: by 2002:a05:6808:3a0b:b0:3bc:8e1a:a4a with SMTP id gr11-20020a0568083a0b00b003bc8e1a0a4amr10814686oib.36.1705442952867; Tue, 16 Jan 2024 14:09:12 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id l8-20020a05620a0c0800b007831ca13f58sm4038368qki.84.2024.01.16.14.09.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:12 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:11 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 03/17] commit-graph: ensure Bloom filters are read with consistent settings Message-ID: <285b25f1b7cca0a64ec410613135d58f73133722.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The changed-path Bloom filter mechanism is parameterized by a couple of variables, notably the number of bits per hash (typically "m" in Bloom filter literature) and the number of hashes themselves (typically "k"). It is critically important that filters are read with the Bloom filter settings that they were written with. Failing to do so would mean that each query is liable to compute different fingerprints, meaning that the filter itself could return a false negative. This goes against a basic assumption of using Bloom filters (that they may return false positives, but never false negatives) and can lead to incorrect results. We have some existing logic to carry forward existing Bloom filter settings from one layer to the next. In `write_commit_graph()`, we have something like: if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) { struct commit_graph *g = ctx->r->objects->commit_graph; /* We have changed-paths already. Keep them in the next graph */ if (g && g->chunk_bloom_data) { ctx->changed_paths = 1; ctx->bloom_settings = g->bloom_filter_settings; } } , which drags forward Bloom filter settings across adjacent layers. This doesn't quite address all cases, however, since it is possible for intermediate layers to contain no Bloom filters at all. For example, suppose we have two layers in a commit-graph chain, say, {G1, G2}. If G1 contains Bloom filters, but G2 doesn't, a new G3 (whose base graph is G2) may be written with arbitrary Bloom filter settings, because we only check the immediately adjacent layer's settings for compatibility. This behavior has existed since the introduction of changed-path Bloom filters. But in practice, this is not such a big deal, since the only way up until this point to modify the Bloom filter settings at write time is with the undocumented environment variables: - GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY - GIT_TEST_BLOOM_SETTINGS_NUM_HASHES - GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS (it is still possible to tweak MAX_CHANGED_PATHS between layers, but this does not affect reads, so is allowed to differ across multiple graph layers). But in future commits, we will introduce another parameter to change the hash algorithm used to compute Bloom fingerprints itself. This will be exposed via a configuration setting, making this foot-gun easier to use. To prevent this potential issue, validate that all layers of a split commit-graph have compatible settings with the newest layer which contains Bloom filters. Reported-by: SZEDER Gábor Original-test-by: SZEDER Gábor Signed-off-by: Taylor Blau --- commit-graph.c | 25 +++++++++++++++++ t/t4216-log-bloom.sh | 65 +++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 89 insertions(+), 1 deletion(-) diff --git a/commit-graph.c b/commit-graph.c index bba316913c..00113b0f62 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -543,6 +543,30 @@ static int validate_mixed_generation_chain(struct commit_graph *g) return 0; } +static void validate_mixed_bloom_settings(struct commit_graph *g) +{ + struct bloom_filter_settings *settings = NULL; + for (; g; g = g->base_graph) { + if (!g->bloom_filter_settings) + continue; + if (!settings) { + settings = g->bloom_filter_settings; + continue; + } + + if (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry || + g->bloom_filter_settings->num_hashes != settings->num_hashes) { + g->chunk_bloom_indexes = NULL; + g->chunk_bloom_data = NULL; + FREE_AND_NULL(g->bloom_filter_settings); + + warning(_("disabling Bloom filters for commit-graph " + "layer '%s' due to incompatible settings"), + oid_to_hex(&g->oid)); + } + } +} + static int add_graph_to_chain(struct commit_graph *g, struct commit_graph *chain, struct object_id *oids, @@ -666,6 +690,7 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct repository *r, } validate_mixed_generation_chain(graph_chain); + validate_mixed_bloom_settings(graph_chain); free(oids); fclose(fp); diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index cc6ebc8140..20b0cf0c0e 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -421,8 +421,71 @@ test_expect_success 'Bloom generation backfills empty commits' ' ) ' +graph=.git/objects/info/commit-graph +graphdir=.git/objects/info/commit-graphs +chain=$graphdir/commit-graph-chain + +test_expect_success 'setup for mixed Bloom setting tests' ' + repo=mixed-bloom-settings && + + git init $repo && + for i in one two three + do + test_commit -C $repo $i file || return 1 + done +' + +test_expect_success 'ensure incompatible Bloom filters are ignored' ' + # Compute Bloom filters with "unusual" settings. + git -C $repo rev-parse one >in && + GIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \ + --stdin-commits --changed-paths --split in && + git -C $repo commit-graph write --stdin-commits --no-changed-paths \ + --split=no-merge in && + git -C $repo commit-graph write --stdin-commits --changed-paths \ + --split=no-merge expect 2>err && + git -C $repo log --oneline --no-decorate -- file >actual 2>err && + test_cmp expect actual && + grep "disabling Bloom filters for commit-graph layer .$layer." err +' + +test_expect_success 'merge graph layers with incompatible Bloom settings' ' + # Ensure that incompatible Bloom filters are ignored when + # merging existing layers. + git -C $repo commit-graph write --reachable --changed-paths 2>err && + grep "disabling Bloom filters for commit-graph layer .$layer." err && + + test_path_is_file $repo/$graph && + test_dir_is_empty $repo/$graphdir && + + git -C $repo -c core.commitGraph=false log --oneline --no-decorate -- \ + file >expect && + trace_out="$(pwd)/trace.perf" && + GIT_TRACE2_PERF="$trace_out" \ + git -C $repo log --oneline --no-decorate -- file >actual 2>err && + + test_cmp expect actual && + grep "statistics:{\"filter_not_present\":0," trace.perf && + test_must_be_empty err +' + corrupt_graph () { - graph=.git/objects/info/commit-graph && test_when_finished "rm -rf $graph" && git commit-graph write --reachable --changed-paths && corrupt_chunk_file $graph "$@" From patchwork Tue Jan 16 22:09:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521289 Received: from mail-qt1-f172.google.com (mail-qt1-f172.google.com [209.85.160.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C544067C42 for ; Tue, 16 Jan 2024 22:09:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442958; cv=none; b=SMzpSlRPDBefpU4UwiLUOUsaBykfd4ZFrns8ol7kBXGOsU9YW0HXJr4TVdPkGz4sbBgeF6wVxe6BJu87dqq4wEFs5ZD5ON4bbozaj9h0XsnvM172iPeKxDCu7gwMfDvYKYS9cPzMMKTcLQnrMN07g6tra8iiniJIPkgWJEXDJOs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442958; c=relaxed/simple; bh=3Tl3R7I4iT7YRgoWU8U8MZLak8vDstJFK1tsm2QyinA=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=K0epHixRJJa7Z6AfxCh97dJ4B8DpntCspR2iw2xTZDW2kHucKxFz8xp8XPlE0T4a4RLpMp0nFSeHYZ226W3fVkXcG9LiqFsT0mcCA9+0Wnw59xYy4S6Ecvle2xuPIoRT+I1/v0i/iWp+of3DSRa6JHCKLtee+B8W0Q0ZyzWjs/g= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=3PqfulWH; arc=none smtp.client-ip=209.85.160.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="3PqfulWH" Received: by mail-qt1-f172.google.com with SMTP id d75a77b69052e-42a0b1353adso3148451cf.1 for ; Tue, 16 Jan 2024 14:09:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442955; x=1706047755; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=dsxRs5wDbOrFFOE8V+8nbOEqjxePqs48kZcrUQVgITo=; b=3PqfulWHXylrI+NO6ElHPa3+mX7XUfNlSa+9i2UMw6zqUshsmhCMeDIc+QFhUAZ8hh jgdLKp1jsWzu6SsIbRQp19sg4odbNTu9TQ+Gfwv86et6QZ5VyAFmBb2FzPml5jhw7ZQg 907ixfMI+9FPgqwLHxaKH7mjeENhLBgDUSXR3MAnYzBdgrHN6qIs2qFqQox9CTPslr9N swtmlKjczwn1rrtMekjgHdqqSiGJPvs2Dioj13lWAA9KtCkYMsRqfKPG4jMA5P3/Heas lVhq3EbQcYz0UJmkICQRm1xUrElD8hiM9c3fcjZRShzWgeX8dcpxxoXnI3Bc8vQsEYzI GYGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442955; x=1706047755; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=dsxRs5wDbOrFFOE8V+8nbOEqjxePqs48kZcrUQVgITo=; b=iU9nrLr1YsY3697Hh9LZHAR/Kx5++J/mfPxwSasC7hy6ge3d0vVfXSZ89vI9cNWjCp XRUZnrciHEklITvu/X7CLlx0mopPfvUSq6nPmHcc72sVVLKqVYXoTxuh4tOb+IcP5pln ++lYjxfR/iLCqhKQqFDaeU22Snhl33zFY15qy9oAtdt18zFOP44z/YhYFtNAuE9cKBpz 4BlIM9SvkGzJdaun/bX+hxy8S9NFqG9RSTXb483XTQ5+vBu5e9LN4JD0DxxrwjtTqDIv CoqAf2ef83fgFYgXY1BnLTiNdrQLZli3yVOVAvrMKx0V45MAjqEXreM2ilnKZ4p7pOLw q9Ng== X-Gm-Message-State: AOJu0YyJ7TqYF+n/xxKTcfQd8k+a72hlyqfPCXTpxPrbo/ZNee7AqJiv TAqMoU3ZPgi5AzRxOdp8J67umAlvARkio3qxMD7QTJgEQyjYuA== X-Google-Smtp-Source: AGHT+IEQ6RdBNKEIwzl+dp3COE+KGupuPh6ohazNLQ200d9EuUl6UtkVo3YniQ+K9SfHMOC5i2yu7A== X-Received: by 2002:ac8:5806:0:b0:42a:7e0:35dd with SMTP id g6-20020ac85806000000b0042a07e035ddmr1218856qtg.129.1705442955541; Tue, 16 Jan 2024 14:09:15 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id gd19-20020a05622a5c1300b004282dc56470sm5207799qtb.15.2024.01.16.14.09.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:15 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:14 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 04/17] gitformat-commit-graph: describe version 2 of BDAT Message-ID: <0cee8078d42ffccc410588a14ff184edbe07b7d9.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: From: Jonathan Tan 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 Signed-off-by: Taylor Blau --- 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 Tue Jan 16 22:09:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521290 Received: from mail-vk1-f180.google.com (mail-vk1-f180.google.com [209.85.221.180]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9A20F4F8A7 for ; Tue, 16 Jan 2024 22:09:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442961; cv=none; b=c4AW6/O8ZlKo9s7gzZvUqk8QuF1AOTNKFw2mo1wVUcRqQ9g2335FB1Qy5nfic7cd9cPHrgypRY/3/imLGkTFK9AycKzN+u0Guv9n76pBoJ2FlN3kxaXhciRAeQqB73MeFs7Q5b1YbN7gtPcMF2IafCGfGr+UZI/jylqNOIycyzY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442961; c=relaxed/simple; bh=pEpS4Rn067IMFD2s2tXqVUBCSYLetWEeeZQ0YE4wDxU=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=be/kES8ulWIyJzD4trtAHlhXIYS1S48ef/ZOa0UkpjJwh912MnElSG85dIisYhsHniEJ0uRobz9T/txC7uTTdAkGLuOkFoWpChyPEc+PhJxWp4kznph5Bmb2yP1S8SRdornhte0jG61BDq2akMvqy/x2l0WPGY7qmlLB9le29wQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=bkM8f1yh; arc=none smtp.client-ip=209.85.221.180 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="bkM8f1yh" Received: by mail-vk1-f180.google.com with SMTP id 71dfb90a1353d-4b8e5d64a4bso1610446e0c.3 for ; Tue, 16 Jan 2024 14:09:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442958; x=1706047758; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=4OxaNJKgh9AvJM4IHM+UXdjTCzNWCqQ7vVaDczEpOVQ=; b=bkM8f1yhqZlpAngsMRK8OjUD22Mxg6SjIBT3cbZbHe8vJvxvUoaJbV4ckrNuHEbk3P QXo5kBvIUvsnOzl7UHuCYivQTTp3q2eqvC1y/D1tqcG+xi55B2CwQzM1lYAJSWYUWgMI AABohDh4knN/6GoyKpPhjE+xFUHL73VJgzFjGwasqgDPw0isQxv3E+PiLrSln4i2l6B6 YYJ9LQ1JN8CN8nf9z5855PiIrksdu86OKfM4gCHWs9aJhlNUaNX2uRvdWCStP8ZXUORC 2Y3uTdY9PejG52G2ZmodvGyD1CVg30LoK+9furg6kLZ5sLzGdkmwYrD/S+QY0MkMA4UN nFrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442958; x=1706047758; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=4OxaNJKgh9AvJM4IHM+UXdjTCzNWCqQ7vVaDczEpOVQ=; b=p8qxLOxzjjdoiyla9OjqOJ+VeAorr5Fi7z3MkIsKZrSEoekRgXfr4HrxzWkvbWwCy5 wlpJ0OpqOF4YHQ5zpMloy1LjOKKZ9Y/T3CWxQSnx+DT4jU9dFEa2hId1hjh66/ZbtmYe hYrj3P45lW8PkRlOifhhK2vSUMODf1qjgn4uyVjgmVgD68fZzOMKD/wFzpZX/hwuqLWD numQHyMqgjR0JXg7zGYA4h96BdlB85Ym9CddeBiB9ezfZYbRXuuwQGwrZC8RKwgwCTt3 2UmI9RvJ4VnzWCqHt6+C8IEDYv57eHXsbyWwP80ZcCoTwhCMZqOuhaP8NI6cpuYqS4Mc vFGg== X-Gm-Message-State: AOJu0Yzl12c30uS8f/GXTPi4zCGTZUnExdre1qUuPJg2jBKvmpIPQqFH ViLyDNqeoqJeex4JWDwf9BHdWn3km/7IMLK4w0z2Mre85cyo2w== X-Google-Smtp-Source: AGHT+IGnqaaFV4qs8aMwOOpfZxviKM2yVeW6PjOSS9vLIZvF0TgENfYsoN+cLYsSz1fiuupNUnBcSg== X-Received: by 2002:a05:6122:1827:b0:4b6:e6e1:49b3 with SMTP id ay39-20020a056122182700b004b6e6e149b3mr4026357vkb.17.1705442958349; Tue, 16 Jan 2024 14:09:18 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id u4-20020a0ced24000000b00680ec916840sm4537246qvq.118.2024.01.16.14.09.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:18 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:17 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 05/17] t/helper/test-read-graph.c: extract `dump_graph_info()` Message-ID: <1fc8d2828d8a40ce04cea646b43d03871b6a224b.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare for the 'read-graph' test helper to perform other tasks besides dumping high-level information about the commit-graph by extracting its main routine into a separate function. Signed-off-by: Taylor Blau Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- t/helper/test-read-graph.c | 31 ++++++++++++++++++------------- 1 file changed, 18 insertions(+), 13 deletions(-) diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index 8c7a83f578..3375392f6c 100644 --- a/t/helper/test-read-graph.c +++ b/t/helper/test-read-graph.c @@ -5,20 +5,8 @@ #include "bloom.h" #include "setup.h" -int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) +static void dump_graph_info(struct commit_graph *graph) { - struct commit_graph *graph = NULL; - struct object_directory *odb; - - setup_git_directory(); - odb = the_repository->objects->odb; - - prepare_repo_settings(the_repository); - - graph = read_commit_graph_one(the_repository, odb); - if (!graph) - return 1; - printf("header: %08x %d %d %d %d\n", ntohl(*(uint32_t*)graph->data), *(unsigned char*)(graph->data + 4), @@ -57,6 +45,23 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) if (graph->topo_levels) printf(" topo_levels"); printf("\n"); +} + +int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) +{ + struct commit_graph *graph = NULL; + struct object_directory *odb; + + setup_git_directory(); + odb = the_repository->objects->odb; + + prepare_repo_settings(the_repository); + + graph = read_commit_graph_one(the_repository, odb); + if (!graph) + return 1; + + dump_graph_info(graph); UNLEAK(graph); From patchwork Tue Jan 16 22:09:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521291 Received: from mail-yw1-f173.google.com (mail-yw1-f173.google.com [209.85.128.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 834A553E3D for ; Tue, 16 Jan 2024 22:09:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442963; cv=none; b=ciR6Fz/BqZOJPdDVoNAbeM0GgShidNnr3tKTh7sMjsYHYl2jpIZb0DvAiim8yc1KhXmpOb8qt5TQI+uiLDn22bRm3Y3mtyg0aOSFrviH29OWB5WyTAzwJ2hziasbVzE1zT1YdoaD0/2jPoNqbsPnE0Vyy6AoaoZ319/lz16q7hg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442963; c=relaxed/simple; bh=7Y0VQbdBTNNvjXd942nxSVtPoM4KcO4E1BPZjX0l+/Y=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=I2HkKBokjzILRImiys5+DfnPFgabyt5LW7gQayANLhf0caj0V9x0g0+BQP9vOXshN37hx68fXlcTvEdqz+0uwn1hEZZFZGe7oQcHN8HjR0hXf9LUUyQ+ajK6Rw87Y7RR5xs4UUihV8S9e2Y+WnvgmULf7RKg1j5q+A8fBwjm5/E= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=HBYqOrN2; arc=none smtp.client-ip=209.85.128.173 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="HBYqOrN2" Received: by mail-yw1-f173.google.com with SMTP id 00721157ae682-5ff6245c1deso3201767b3.1 for ; Tue, 16 Jan 2024 14:09:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442961; x=1706047761; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=VoWSPYAFRBARcZJPhkQSg3t6n6Fl1PB90395KKgCRb8=; b=HBYqOrN2oDQjt4LTBMsUGqNmmC6Su82P6se5IThyajCJ/AmAv5EplBF5gJkqHHdg/p VOI15bOewSb7MJ36vLNx9OWFOmtj9vi2z7fVchUNEr18cqVih0tjizwa/VrdLakC/zHO 3R0eQ1BJF+y1H7fV7BEFIIVhIq61/CnQwh1+Q9Tk7VjzHV6kwu0Fqw/qtmy1rY2j2opJ uCP3NZxNBxrvO0n6Lof+oWSY5ogyuIw8skpe6MFblDr1fGcR3Xjztqw0aLPBs4c83nqd w7Mn0KkXERX8V0sjg0hugKjlRm0dyg97KjiJKzwdn81jVZP9ZYHnuv5Drw++bhFQW6Ub R0ng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442961; x=1706047761; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=VoWSPYAFRBARcZJPhkQSg3t6n6Fl1PB90395KKgCRb8=; b=cOJDaqTDLQ8hqRDqMHdwAIYVS6OQRck9XRbWw+Fvhog+KcVB+/VBTaaQeCG0GCTRD4 EXHsLlWZ2I1dmpJT0IYcELdUZQgeFxnbpiivY67dVHRxnLciDY/p8Vwoe7XeAky6MtM4 Ejmhhu4ro9IKWcFEDDghef6anJhv84hQD0FUZbW1jfNfj7yjZYB+O++7rCOB4Ns7rSY4 w/PB60FTABS6v3Bnax34YXRxdc4uOGH6bDobZ8hDzwP24oNCX6zO9R//d/wt9Xlpyfwq Kuzvwn20Hit64UqTz/j2X5Ch31MQsrkwXTInjHt0N/SefCtH6vQbSorRZ1tbOPBKfPby cbjQ== X-Gm-Message-State: AOJu0YzNGTmEqC2pVW2jaSzuMIdRWwYgA2/0mA9mfIirul/LYHHhQy0a IOIRsS+i/QlEukS8SsEHlAkwg0Lr5BV8ZOJ3SjDHAcql+AHWJQ== X-Google-Smtp-Source: AGHT+IGdetmDZzv3/4o2TXvfiqkayEZgBnIYvKApq1g09G8s7JGh1pvvQC9MOj5B25Ze6ET7hzX4FQ== X-Received: by 2002:a0d:d80b:0:b0:5ff:6514:d0d1 with SMTP id a11-20020a0dd80b000000b005ff6514d0d1mr73164ywe.99.1705442961254; Tue, 16 Jan 2024 14:09:21 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id t14-20020ad45bce000000b00681783effa0sm355330qvt.122.2024.01.16.14.09.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:21 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:20 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 06/17] bloom.h: make `load_bloom_filter_from_graph()` public Message-ID: <03dd7cf30a5c35ad0bffaf5c8141fbf59ae5c84b.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare for a future commit to use the load_bloom_filter_from_graph() function directly to load specific Bloom filters out of the commit-graph for manual inspection (to be used during tests). Signed-off-by: Taylor Blau Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- bloom.c | 6 +++--- bloom.h | 5 +++++ 2 files changed, 8 insertions(+), 3 deletions(-) diff --git a/bloom.c b/bloom.c index e529f7605c..401999ed3c 100644 --- a/bloom.c +++ b/bloom.c @@ -48,9 +48,9 @@ static int check_bloom_offset(struct commit_graph *g, uint32_t pos, return -1; } -static int load_bloom_filter_from_graph(struct commit_graph *g, - struct bloom_filter *filter, - uint32_t graph_pos) +int load_bloom_filter_from_graph(struct commit_graph *g, + struct bloom_filter *filter, + uint32_t graph_pos) { uint32_t lex_pos, start_index, end_index; diff --git a/bloom.h b/bloom.h index adde6dfe21..1e4f612d2c 100644 --- a/bloom.h +++ b/bloom.h @@ -3,6 +3,7 @@ struct commit; struct repository; +struct commit_graph; struct bloom_filter_settings { /* @@ -68,6 +69,10 @@ struct bloom_key { uint32_t *hashes; }; +int load_bloom_filter_from_graph(struct commit_graph *g, + struct bloom_filter *filter, + uint32_t graph_pos); + /* * Calculate the murmur3 32-bit hash value for the given data * using the given seed. From patchwork Tue Jan 16 22:09:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521292 Received: from mail-oi1-f172.google.com (mail-oi1-f172.google.com [209.85.167.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3024C55C03 for ; Tue, 16 Jan 2024 22:09:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442966; cv=none; b=RTGRM3aXDGb29ujYtp89xOAyAjItGcJHR/fGgFK+kPTlv6rRPTEH1c+jvh38tBmBPSAE67noHY3QIGbK87zgQjq4ZIGp2DPZzwj2I4u7gaQQ0iyHziPS0X+trYoCNw6WBn45FpMDiYtpJ4Wt8mY5ImEKl4AOdr4WcSv/jl1HO/8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442966; c=relaxed/simple; bh=0IJrdJHY/qP58apoD2ow6blfL8xVKOwffsUEWgjiEn0=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=jcFnqK71f/Ok8CJDtU+Lzsa0p/Uy7JlVLO6JUcAcDhq0FQOhBlGTbqfvrzTCVci9lzTugpR/vGeDbRbilZYdHugiluCEUZK81CZkJMG4AtqLDLz2gXBZuMyZ8qZDgzYNPFJZJlAFK7ZYb0GN/8cwNiEHAVfx0nOyXQENsLakOYM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=XNYtvG9n; arc=none smtp.client-ip=209.85.167.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="XNYtvG9n" Received: by mail-oi1-f172.google.com with SMTP id 5614622812f47-3bd7477d7a3so1485903b6e.2 for ; Tue, 16 Jan 2024 14:09:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442964; x=1706047764; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=XBZBG0DIHtLbgIsZDa4P8j7yucGn6D6BmXj75W+N4Kc=; b=XNYtvG9nROQIaIdtQkzYb1CXlEuoyc7NqLs1qaw4dHf3xeUbuDYyRisCubu2Pg50Jw RqdXMVbREC80vWizlAkRM2DvNB5NoXkUs1uuiNK0lVLo0ukdVkbGBuyqYX3gfQK0u7xE bef6lkIFLrUmq4uA7a+RauS/txQ2i2Zg3kkn2wuvGxQ19e3TC+0HZe54AnQPqjCoYJqy KA5uVZqQU9YuGWL6Y5YnE4ZPWbEP6LjbDWTuaEWKnBH9QnrwpylsrABlgWpHUUMTvbli dB0IAwzm1Rg1K61BwI0OEWmnzm7okDqpYEVjpJFd6m8sM3bcOmPKTs/aF8+Vwr6bTrYw JP2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442964; x=1706047764; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=XBZBG0DIHtLbgIsZDa4P8j7yucGn6D6BmXj75W+N4Kc=; b=XCk5UpP0COZBfOnIjqqllAHFa+uiKN+xKu7YseVaUDvS3qsgIjRYuEw/pmJgJbL2ws BndhgfrySm4MybGNsrrejl7vmZ20z4LeXfKdy7mUGMLhO5MziL6IIC4CCj15/OK/rPp7 Wusvr3eX7D9gYpFadl2JOUavGmPM9y138cfVrxDatBx7Gg32UUcHb+xkQloHPC/rXusJ suKmfAFRKVaFQvBdoR+4ZqXw1Xu7zNZSmOaATfkd24NZVUiMHf1L0vUNdOe3DceI2Wdw ILYpWFL+oJYEHMelMcLYr4eV7hFT2EowxLqtLjGP3ZSJt4eKurPr2y+lHXewvQGOH9s5 IIAw== X-Gm-Message-State: AOJu0YzyVotqBaFMzin+viPJ/oYMwzbkCbRI1Xxa0LqFVpFRARMXNd2/ M5eZazcfOrzIgSZROTsVspXxAFcgBEr7Pmwi/6OWnJRBMT8KLQ== X-Google-Smtp-Source: AGHT+IE0iIIcyj4WcuvQ2tpzuFO2/tz+/Fz/zLcFxsJmQmtFiKg7FJet/fOEiZu/6U4eqIWeYsR2jQ== X-Received: by 2002:a05:6808:654a:b0:3bd:727f:1031 with SMTP id fn10-20020a056808654a00b003bd727f1031mr3812879oib.119.1705442964035; Tue, 16 Jan 2024 14:09:24 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id de28-20020a05620a371c00b00783395ce1d5sm3971188qkb.136.2024.01.16.14.09.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:23 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:22 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 07/17] t/helper/test-read-graph: implement `bloom-filters` mode Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Implement a mode of the "read-graph" test helper to dump out the hexadecimal contents of the Bloom filter(s) contained in a commit-graph. Signed-off-by: Taylor Blau Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- t/helper/test-read-graph.c | 44 +++++++++++++++++++++++++++++++++----- 1 file changed, 39 insertions(+), 5 deletions(-) diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index 3375392f6c..da9ac8584d 100644 --- a/t/helper/test-read-graph.c +++ b/t/helper/test-read-graph.c @@ -47,10 +47,32 @@ static void dump_graph_info(struct commit_graph *graph) printf("\n"); } -int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) +static void dump_graph_bloom_filters(struct commit_graph *graph) +{ + uint32_t i; + + for (i = 0; i < graph->num_commits + graph->num_commits_in_base; i++) { + struct bloom_filter filter = { 0 }; + size_t j; + + if (load_bloom_filter_from_graph(graph, &filter, i) < 0) { + fprintf(stderr, "missing Bloom filter for graph " + "position %"PRIu32"\n", i); + continue; + } + + for (j = 0; j < filter.len; j++) + printf("%02x", filter.data[j]); + if (filter.len) + printf("\n"); + } +} + +int cmd__read_graph(int argc, const char **argv) { struct commit_graph *graph = NULL; struct object_directory *odb; + int ret = 0; setup_git_directory(); odb = the_repository->objects->odb; @@ -58,12 +80,24 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) prepare_repo_settings(the_repository); graph = read_commit_graph_one(the_repository, odb); - if (!graph) - return 1; + if (!graph) { + ret = 1; + goto done; + } - dump_graph_info(graph); + if (argc <= 1) + dump_graph_info(graph); + else if (!strcmp(argv[1], "bloom-filters")) + dump_graph_bloom_filters(graph); + else { + fprintf(stderr, "unknown sub-command: '%s'\n", argv[1]); + ret = 1; + } +done: UNLEAK(graph); - return 0; + return ret; } + + From patchwork Tue Jan 16 22:09:25 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521293 Received: from mail-ot1-f50.google.com (mail-ot1-f50.google.com [209.85.210.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AF8F656B7F for ; Tue, 16 Jan 2024 22:09:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442969; cv=none; b=RpJd3oiGzQuIk+RuTF77IeYWIOUQCzFG3NQ/IaxMuVyx0Ybe6q3i0oYc/eZat5sg1JNhjqwzhbce9gBPfPpetanznE2FYFEz5+nDI61Ix/TjEmB6j5hnLtDR0oWB9L8vMt//1FIv6M1f85kUDWmWCiGGoAusMKC5QfUcCHCjdMI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442969; c=relaxed/simple; bh=v9fi1NZIhp1xi1G7evsRiRRy0PGycUDBhZ7s0X9mq6w=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=JAtt0MY36FgnUFyOCzqZckJWz035sp7XEF9J6qK21/ehoUy3qF+BR8GryEXL2GdjMv/sbfhUAPsVXDyCmB4c1Ddd98AzxfFb12aZRGQPrrjkYH77N/tnOMFkoy7CPXdqg3nC7S8ClQ3+5eCrBI9aJ5qcKghoYqcANuAemWV9gqo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=UVPyZCKG; arc=none smtp.client-ip=209.85.210.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="UVPyZCKG" Received: by mail-ot1-f50.google.com with SMTP id 46e09a7af769-6ddee0aa208so4900751a34.3 for ; Tue, 16 Jan 2024 14:09:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442966; x=1706047766; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=+XPN8KT3cfPkEbL9Y2+Wb2qHbLtIeC9qIuXubwQUSec=; b=UVPyZCKG/fzlz4x4KExOohctgNqylAkcZUpPXnc93SWZrVKfzCKtl38uxvKLKzg5RL OEp8FGP0NIgFf6CSVJn8g387rs2MoUOdPyqF19j7wI3d1YkfAQDfmD8+pAmdrB5Cy6rw 2h54HEAncJI65MLBdPH0Dsr7w6xGLw31eS4zXuWudUeo5OxhWi7tE83vtFg8iXxFBshW plkFHwBZGL9TviOLGDxaALW0cT7s12ZCZn1Y5+v+mZG6Qliz6h/r6aldMJbrV9zRK8En lHY/KpvRzt0Om0m9yCB+g1eUwVw3cH3zJ8+Td+P8T2IDPMdg9IEQq6nmUl6oTIKNcUTD K+Dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442966; x=1706047766; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=+XPN8KT3cfPkEbL9Y2+Wb2qHbLtIeC9qIuXubwQUSec=; b=EHkEneMr+8M/pIQuwudj07VlU63a2l6CuSQ0ojuFGQ/ecteSz3z5WMJ3za55UakpaT WaY0AG+WeJGWDhhnAqeh5v2kvgFciINmD+IzsoJFkdv7yA/Ohkfo9VdgWB3Jum3nehvb uWM9Fikfrjfu7GeRgzrE+ip/s7PDP5m5+vcNgymUFsZrOWS+Xq5Om1wKzAlC6CNuo4Gk THMaoonEqeTZWT8F9AOh69IQAwWLeS0Ok+3TNznemMc5x3TouRON4jmjEHeaxRFpWDAq GnRhqDPdKWWU7Vj9+zgt+76CPCNT6YIP4zzBKvpv0lzptT43VJp2NMVWg9h4/FWsNf3a V93w== X-Gm-Message-State: AOJu0YypDTHFLOyZCGL1JPK83qDDQuoMyH3MKeSwYpZ4ecu6baxKJ7Hy Gx9w8lVj8MtVZxiCZuTwAjGGvzQLP42HM56OdhuwYhHachOzig== X-Google-Smtp-Source: AGHT+IH7o974iCc1FrobWUaxvTu0gn9G0LhfcU8KfoHVjCU++U1qS3l7luB5JEgreTVv01KBUDp6wQ== X-Received: by 2002:a05:6830:b:b0:6df:b685:978 with SMTP id c11-20020a056830000b00b006dfb6850978mr8494331otp.35.1705442966772; Tue, 16 Jan 2024 14:09:26 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id b19-20020a05620a119300b007832575779esm4013031qkk.52.2024.01.16.14.09.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:26 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:25 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 08/17] t4216: test changed path filters with high bit paths Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: 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 Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- t/t4216-log-bloom.sh | 51 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 20b0cf0c0e..484dd093cd 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -485,6 +485,57 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' ' test_must_be_empty err ' +get_first_changed_path_filter () { + test-tool read-graph bloom-filters >filters.dat && + head -n 1 filters.dat +} + +# 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 && + echo "52a9" >expect && + get_first_changed_path_filter >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 'setup make another commit' ' + # "git log" does not use Bloom filters for root commits - see how, in + # revision.c, rev_compare_tree() (the only code path that eventually calls + # get_bloom_filter()) is only called by try_to_simplify_commit() when the commit + # has one parent. Therefore, make another commit so that we perform the tests on + # a non-root commit. + test_commit -C highbit1 anotherc1 "another$CENT" +' + +test_expect_success 'version 1 changed-path used when version 1 requested' ' + ( + cd highbit1 && + test_bloom_filters_used "-- another$CENT" + ) +' + corrupt_graph () { test_when_finished "rm -rf $graph" && git commit-graph write --reachable --changed-paths && From patchwork Tue Jan 16 22:09:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521294 Received: from mail-qk1-f178.google.com (mail-qk1-f178.google.com [209.85.222.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5937967C40 for ; Tue, 16 Jan 2024 22:09:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442972; cv=none; b=II05j1YPvsywFpwGtTnJwhUxtDPzKa+Hjk1FkUKRiucYnskcLLtnZquTIzoylCyv44Qatjft1SZAEdq/zGpB5fWwGMbBMRmPX1qh1s09UTAMo9E5+7WAWPTb0MRVT5SMpMUFt9f64ZPK9Lqwj2GK7ZPeY8T32AqiE0qq8Gr4CJk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442972; c=relaxed/simple; bh=mj+XMOTEQ1tVSk49H4wNdVXxkcaymiePObr1I4uF1xM=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=TjSuRpecWZz+5aXdF8ACEiYO1E2biBp6KZIODweE08qEnDB0XjwaIKFzM6BLHJFEVeAuFMfKnjPcK3FhNv+Vq5k+SL6rCN7R5ffwBinmdeHu719ljockYtkCWN6dde4LfxuUwJKUU8rvlocRqIehdhdXFnmmxIJiMM7iiS0v704= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=ASs4KTBd; arc=none smtp.client-ip=209.85.222.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="ASs4KTBd" Received: by mail-qk1-f178.google.com with SMTP id af79cd13be357-78313f4d149so1077311985a.1 for ; Tue, 16 Jan 2024 14:09:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442969; x=1706047769; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=pmn9fLMdffx5U61Q0oW8gq9ibGFbe2pfqlCbhU8FYg8=; b=ASs4KTBdfmqTR0DTldqlTYf1WSWgJ+n2PwC8sPjNXvYAUlVphG5vvaUc+3PKY/jTYO mmp5Iq/s61zll0S6ChTq8xJRjGZBAC0g7aADyuDsMyLI+UjauACbd0GhtCL1tL2lSB+e 0tPnlgYsF0thtShZhx5qAkBP5WqTEir3ElV9MbEZjybXhQDCFm4RQ+YNkiNlRhRG3C2V gb4UtywhW72FExzsitSORIiYH+lpdM+YR+niqTzB3WhE2J+oTfLEInzEPNKLfTQk46GV HYBxWcBw74Yc0u9ZEU8BcxBwww9vyA+3cutXICwjT0+JsWUK1P/4az97FHxBoTzXSgA4 bL+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442969; x=1706047769; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=pmn9fLMdffx5U61Q0oW8gq9ibGFbe2pfqlCbhU8FYg8=; b=hUMrFdVzkm/kvRnRTGLTfoedCteTzL08xjRep8gdCCodz5Gy1i4GSv297iDYUV51zO 3je0jZ0Df8LvreAPCqrHWpBwyFy8QuGpDdmKDJvf9IopdS6Ofcc98DzBatVMQ43w1/3/ CrAtkHs4z3LJDXeND6+dXG5IH46r686VMTpEUSlQgDPcngRo5gKimkjA1WKHytyCutWF dQmHPKkASiwYtlSlsvd4imPneR8Lkxu65uO2OeKu7Kasb6+YN/7W6qQ7JUr+rXBy2cqc HrvY6/bimKp9sWA8niBdohe8GA2ZMqngOrIeh56LgXGT2TjJMtLvsnEsOYKm2rCqVx7g Ufow== X-Gm-Message-State: AOJu0Yx5HF08i3rPt1R4vzSXV9y7Gvihx0FhK33EvdadfDlkj5erRQWi ns5+pmY10XXPM2aU/MhCNKxLeV3JPbeQOPaqhrNN7YGn/2btxQ== X-Google-Smtp-Source: AGHT+IHvX5Ob158jMTB8wjDRn/YqY5u6y19pSwC+NGDFXXzPW7ngzafFItqETxYNUoX6zcb0UaYWkg== X-Received: by 2002:a05:620a:2620:b0:783:53f0:5084 with SMTP id z32-20020a05620a262000b0078353f05084mr7065706qko.9.1705442969529; Tue, 16 Jan 2024 14:09:29 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id vy3-20020a05620a490300b00781eb1e7779sm4042726qkn.94.2024.01.16.14.09.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:29 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:28 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 09/17] repo-settings: introduce commitgraph.changedPathsVersion Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: 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 Signed-off-by: Taylor Blau --- Documentation/config/commitgraph.txt | 26 ++++++++++++++++++++++--- commit-graph.c | 5 +++-- oss-fuzz/fuzz-commit-graph.c | 2 +- repo-settings.c | 6 +++++- repository.h | 2 +- t/t4216-log-bloom.sh | 29 +++++++++++++++++++++++++++- 6 files changed, 61 insertions(+), 9 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 30604e4a4c..e68cdededa 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -9,6 +9,26 @@ 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 commitGraph.changedPathsVersion=-1 if true, and + commitGraph.changedPathsVersion=0 if false. (If commitGraph.changedPathVersion + is also set, commitGraph.changedPathsVersion takes precedence.) + +commitGraph.changedPathsVersion:: + Specifies the version of the changed-path Bloom filters that Git will read and + write. May be -1, 0 or 1. Note that values greater than 1 may be + incompatible with older versions of Git which do not yet understand + those versions. Use caution when operating in a mixed-version + environment. ++ +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 not read any Bloom filters, and will write version 1 Bloom +filters when instructed to write. ++ +If 1, Git will only read version 1 Bloom filters, and will write version 1 +Bloom filters. ++ +See linkgit:git-commit-graph[1] for more information. diff --git a/commit-graph.c b/commit-graph.c index 00113b0f62..91c98ebc6c 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -459,7 +459,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) { read_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, graph_read_bloom_index, graph); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, @@ -555,7 +555,8 @@ static void validate_mixed_bloom_settings(struct commit_graph *g) } if (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry || - g->bloom_filter_settings->num_hashes != settings->num_hashes) { + g->bloom_filter_settings->num_hashes != settings->num_hashes || + g->bloom_filter_settings->hash_version != settings->hash_version) { g->chunk_bloom_indexes = NULL; g->chunk_bloom_data = NULL; FREE_AND_NULL(g->bloom_filter_settings); diff --git a/oss-fuzz/fuzz-commit-graph.c b/oss-fuzz/fuzz-commit-graph.c index 2992079dd9..325c0b991a 100644 --- a/oss-fuzz/fuzz-commit-graph.c +++ b/oss-fuzz/fuzz-commit-graph.c @@ -19,7 +19,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 30cd478762..c821583fe5 100644 --- a/repo-settings.c +++ b/repo-settings.c @@ -23,6 +23,7 @@ void prepare_repo_settings(struct repository *r) int value; const char *strval; int manyfiles; + int read_changed_paths; if (!r->gitdir) BUG("Cannot add settings for uninitialized repository"); @@ -53,7 +54,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", &read_changed_paths, 1); + repo_cfg_int(r, "commitgraph.changedpathsversion", + &r->settings.commit_graph_changed_paths_version, + read_changed_paths ? -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 5f18486f64..f71154e12c 100644 --- a/repository.h +++ b/repository.h @@ -29,7 +29,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 fetch_write_commit_graph; int command_requires_full_index; diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 484dd093cd..642b960893 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -435,7 +435,7 @@ test_expect_success 'setup for mixed Bloom setting tests' ' done ' -test_expect_success 'ensure incompatible Bloom filters are ignored' ' +test_expect_success 'ensure Bloom filters with incompatible settings are ignored' ' # Compute Bloom filters with "unusual" settings. git -C $repo rev-parse one >in && GIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \ @@ -485,6 +485,33 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' ' test_must_be_empty err ' +test_expect_success 'ensure Bloom filter with incompatible versions are ignored' ' + rm "$repo/$graph" && + + git -C $repo log --oneline --no-decorate -- $CENT >expect && + + # Compute v1 Bloom filters for commits at the bottom. + git -C $repo rev-parse HEAD^ >in && + git -C $repo commit-graph write --stdin-commits --changed-paths \ + --split in && + git -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \ + --stdin-commits --changed-paths --split=no-merge actual 2>err && + test_cmp expect actual && + + layer="$(head -n 1 $repo/$chain)" && + cat >expect.err <<-EOF && + warning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings + EOF + test_cmp expect.err err +' + get_first_changed_path_filter () { test-tool read-graph bloom-filters >filters.dat && head -n 1 filters.dat From patchwork Tue Jan 16 22:09:31 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521295 Received: from mail-qt1-f172.google.com (mail-qt1-f172.google.com [209.85.160.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 165FE1DA34 for ; Tue, 16 Jan 2024 22:09:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442976; cv=none; b=Ih0XWrnZlmbmJleaxwzHj2vm66cnmZ4aAuFgmydjWJ1Jr3Z87L/Nh1TawBSvc8S3yg3T7lk9ko365FJ8bGs/gp8+COXXPJxm7oAszWCOCF21XTTev6WeQnyI8bdwpvmsiuZDc4ZLfYFt7jckac2wEEOWAX2b+BiilMl6IZUKBp4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442976; c=relaxed/simple; bh=ZU7qfIfJJjqNCNaIckXrSdDXIu4ahomnlg4JKwBzGl8=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=k+0KOSJAdHD4vvVaTs0wgdgTajMw4mKdMhhJgWJKeRUd+sX/0QfOIj7SLt1GI+r3ZRKdNIdI3icATKa7rlnmEv4+dkynToLJv0S/tGWap05bmZXkd3z0iWb+sAplpGDeLuGI97+e1B1bbmtpB99GDsVixwjKM43M+ctych6hsLU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=xB0uucuY; arc=none smtp.client-ip=209.85.160.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="xB0uucuY" Received: by mail-qt1-f172.google.com with SMTP id d75a77b69052e-429de32dad9so20052891cf.2 for ; Tue, 16 Jan 2024 14:09:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442973; x=1706047773; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=E6MJHvhKr59wfaZCS8YSeyy7sMlc3jc0XSQljfgy3MU=; b=xB0uucuY7Sc8VaAbS0KlKSqjtgISFvALdTDrCHExAy37msi130t4ALgO+A29JUU9oo bPq9qGeGUePEl4f/30Qxv+ChXEiqnUZf72dmxnGgp3wQypsr5YF2+hAXP8KVemKJxUqX z4jFks1P/YAqXjew9V+6PlFZg2lBazhyIR4/Q1mRO2D6GCSrhozdWWwJm2pk0VlLO1TQ RsLKJ9dPuKc/NuvzuG64kPYZfC27VoCZoMvY7QSrmr5ZJlsJKJtCnvT6p7AgX5jge8VP yhOlgxK8rZMzjL0dVSgEQ4dVv2BksYSHTaeuDJbpkJGbL/ZbdzPMTdU6WWNA3VSoZEGu sC5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442973; x=1706047773; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=E6MJHvhKr59wfaZCS8YSeyy7sMlc3jc0XSQljfgy3MU=; b=eCmpdRmt55qzUxs+TenDt4mxP9LqqfR+38fQDt+QG1ldqF7t9Co4oLNNzWcc5qjeAr 1iK7IamITBbmLnP2r2gwh6ZWyP9sCnDP1deSQm6uNKH1b5AuDx0jO8ebOdNlx0nIhNWN S38CC66doA+rqh7A5jM5r9uKk+J341CoEs9UCTxKsB7X5GGUY5Lk5zS4cHR/FINofB5Q LyTs5PkKUdfcTxVuA15LLUU82mHHiorvw69895sXddEuvyFKmy6ZQdFfCxcqP90mJfkE 8caEwOkCzOqrgJKOLoZvCJGLHIqyoYKsKAqki0KnAWqtc+WUtdvXomh6VnrvCbBPNxOc Q4oA== X-Gm-Message-State: AOJu0YzX0IVswKCsy1WrTwmQQKutx5ES/M0cx7nNepBThtXjGrowSMCS Z33T9fZtF8vBlQPAh97kOvRPTBRK8+SBynyUChbb81JyUtxzcg== X-Google-Smtp-Source: AGHT+IEa8XD0/pUuJWS9E0OqCr0V/36o1AtEbjISWLfaVTMAcbddp61u/sYd76pSA86/QafQTYHjCQ== X-Received: by 2002:a05:622a:178d:b0:429:ca8f:f4c5 with SMTP id s13-20020a05622a178d00b00429ca8ff4c5mr9650078qtk.53.1705442972707; Tue, 16 Jan 2024 14:09:32 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id fj5-20020a05622a550500b004299fd63fdesm5243645qtb.4.2024.01.16.14.09.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:32 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:31 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 10/17] commit-graph: new Bloom filter version that fixes murmur3 Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: 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 (thus, the changed path filters wouldn't be readable by other off-the-shelf implementatios 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 Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- Documentation/config/commitgraph.txt | 5 +- bloom.c | 69 +++++++++++++++- bloom.h | 8 +- commit-graph.c | 37 +++++++-- t/helper/test-bloom.c | 9 ++- t/t0095-bloom.sh | 8 ++ t/t4216-log-bloom.sh | 114 +++++++++++++++++++++++++++ 7 files changed, 234 insertions(+), 16 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index e68cdededa..7f8c9d6638 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -15,7 +15,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. Note that values greater than 1 may be + write. May be -1, 0, 1, or 2. Note that values greater than 1 may be incompatible with older versions of Git which do not yet understand those versions. Use caution when operating in a mixed-version environment. @@ -31,4 +31,7 @@ filters when instructed to write. If 1, Git will only read version 1 Bloom filters, and will write version 1 Bloom filters. + +If 2, Git will only read version 2 Bloom filters, and will write version 2 +Bloom filters. ++ See linkgit:git-commit-graph[1] for more information. diff --git a/bloom.c b/bloom.c index 401999ed3c..e9361b1c1f 100644 --- a/bloom.c +++ b/bloom.c @@ -99,7 +99,64 @@ 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; @@ -164,8 +221,14 @@ 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); + uint32_t hash0, hash1; + if (settings->hash_version == 2) { + hash0 = murmur3_seeded_v2(seed0, data, len); + hash1 = murmur3_seeded_v2(seed1, data, len); + } else { + hash0 = murmur3_seeded_v1(seed0, data, len); + hash1 = 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 1e4f612d2c..138d57a86b 100644 --- a/bloom.h +++ b/bloom.h @@ -8,9 +8,11 @@ struct commit_graph; 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; @@ -80,7 +82,7 @@ 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); void fill_bloom_key(const char *data, size_t len, diff --git a/commit-graph.c b/commit-graph.c index 91c98ebc6c..22237e7dfc 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -340,10 +340,16 @@ static int graph_read_bloom_index(const unsigned char *chunk_start, return 0; } +struct graph_read_bloom_data_context { + 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_context *c = data; + struct commit_graph *g = c->g; uint32_t hash_version; if (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) { @@ -354,13 +360,15 @@ static int graph_read_bloom_data(const unsigned char *chunk_start, return -1; } + hash_version = get_be32(chunk_start); + + if (*c->commit_graph_changed_paths_version == -1) + *c->commit_graph_changed_paths_version = hash_version; + else if (hash_version != *c->commit_graph_changed_paths_version) + return 0; + g->chunk_bloom_data = chunk_start; g->chunk_bloom_data_size = chunk_size; - hash_version = get_be32(chunk_start); - - if (hash_version != 1) - return 0; - g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); g->bloom_filter_settings->hash_version = hash_version; g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4); @@ -460,10 +468,14 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, } if (s->commit_graph_changed_paths_version) { + struct graph_read_bloom_data_context context = { + .g = graph, + .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version + }; read_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, graph_read_bloom_index, graph); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - graph_read_bloom_data, graph); + graph_read_bloom_data, &context); } if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) { @@ -2501,6 +2513,13 @@ int write_commit_graph(struct object_directory *odb, } if (!commit_graph_compatible(r)) return 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; + } CALLOC_ARRAY(ctx, 1); ctx->r = r; @@ -2513,6 +2532,8 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 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", @@ -2542,7 +2563,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 1281e66876..eefc1668c7 100644 --- a/t/helper/test-bloom.c +++ b/t/helper/test-bloom.c @@ -49,6 +49,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"; @@ -63,7 +64,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 642b960893..a7bf3a7dca 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -563,6 +563,120 @@ test_expect_success 'version 1 changed-path used when version 1 requested' ' ) ' +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 "-- another$CENT" + ) +' + +test_expect_success 'version 1 changed-path used when autodetect requested' ' + ( + cd highbit1 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- another$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 && + echo "options: bloom(1,10,7) read_generation_data" >expect && + test-tool read-graph >full && + grep options full >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 && + echo "c01f" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual + ) +' + +test_expect_success 'setup make another commit' ' + # "git log" does not use Bloom filters for root commits - see how, in + # revision.c, rev_compare_tree() (the only code path that eventually calls + # get_bloom_filter()) is only called by try_to_simplify_commit() when the commit + # has one parent. Therefore, make another commit so that we perform the tests on + # a non-root commit. + test_commit -C highbit2 anotherc2 "another$CENT" +' + +test_expect_success 'version 2 changed-path used when version 2 requested' ' + ( + cd highbit2 && + test_bloom_filters_used "-- another$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 "-- another$CENT" + ) +' + +test_expect_success 'version 2 changed-path used when autodetect requested' ' + ( + cd highbit2 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- another$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 && + echo "options: bloom(2,10,7) read_generation_data" >expect && + test-tool read-graph >full && + grep options full >actual && + test_cmp expect actual + ) +' + +test_expect_success 'when writing commit graph, do not reuse changed-path of another version' ' + git init doublewrite && + test_commit -C doublewrite c "$CENT" && + git -C doublewrite config --add commitgraph.changedPathsVersion 1 && + git -C doublewrite commit-graph write --reachable --changed-paths && + for v in -2 3 + do + git -C doublewrite config --add commitgraph.changedPathsVersion $v && + git -C doublewrite commit-graph write --reachable --changed-paths 2>err && + cat >expect <<-EOF && + warning: attempting to write a commit-graph, but ${SQ}commitgraph.changedPathsVersion${SQ} ($v) is not supported + EOF + test_cmp expect err || return 1 + done && + git -C doublewrite config --add commitgraph.changedPathsVersion 2 && + git -C doublewrite commit-graph write --reachable --changed-paths && + ( + cd doublewrite && + echo "c01f" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual + ) +' + corrupt_graph () { test_when_finished "rm -rf $graph" && git commit-graph write --reachable --changed-paths && From patchwork Tue Jan 16 22:09:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521296 Received: from mail-qk1-f174.google.com (mail-qk1-f174.google.com [209.85.222.174]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 746B420DD7 for ; Tue, 16 Jan 2024 22:09:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442977; cv=none; b=KtuAPlpK6uOUJE717pYwMDD1iJiU/06Pbt+eOLGxTgeCmnflfFBtBFUrej1Wg1nZ7jEQgZHIM9d0tIZkF+Ab3c7Y29Z3igT6G6+v9GWHkL96RVrLHZKw++mvV/DvGXqyiZlCAmc5v0AxJ8KboUcpfK0ALH7wBidGm9bOdrtXIWk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442977; c=relaxed/simple; bh=/tYvyrWw8Z03OpIP2g2toYGv5Z/FbuT7FVFBM8CivB4=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=SxygqK4CREfdCW396tI50hmymbDxNuh3Ffut400IxPeLfWX/yz6yrMvu7CWkh1EhbmSFgPhkF3pq10BhgkW919snmISO+8PdKWAsxfkpaIOEZS6a7n6ix2OFnufRvPJNmXtXnHEkoNtylh4PgSUsSP4Biy3hCTJDGeMp0Lb9/S0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=mAJ23vva; arc=none smtp.client-ip=209.85.222.174 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="mAJ23vva" Received: by mail-qk1-f174.google.com with SMTP id af79cd13be357-7831c604a84so766778185a.1 for ; Tue, 16 Jan 2024 14:09:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442975; x=1706047775; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=1X2EQuxGdrpinUTRzo9QBjTczTIMyYB3Z1D8Gx3CFGo=; b=mAJ23vvaYnebVkkfrm89Jb+GFaoACefQCtmUKxgxGLGiG0VY5R4a7O9JzEeSHe4WHk iqixQi0+OlkboSlvYum+vay6+qHTD/dT7UGElQ5/Q+cCBvCqjORVGziOTvNY1UK/d/hR aWWqq6nyJlC9Uyda5TrP87Jn+XvE70EI4kMSSE8TvpHdPppjajoAxON2sbDFkLfUh2w/ 2OfckLaja0Y+705cVaLX88VfnmKqyYCBWWwGFHbDzuW12mrEiHW1SzVGrHDUVsoK7ZC/ Ec5pRzXv6JL1E6slKBEWVIqY56RY+VLrQph661SZgrvYx+JKfa5AcE4cWHUFNIiIzatj zQuw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442975; x=1706047775; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=1X2EQuxGdrpinUTRzo9QBjTczTIMyYB3Z1D8Gx3CFGo=; b=lS4EjV3dRnFgU7/r/AgQVNK4W312AL/euD++Z+pQ6X6DVJAns2SE715i2S0tGtyBmp 1+L0na+e3O3Z+rpPv66vJvPjQIbarrHXBkcHqGRBcA6hUfyS8H4bQS8ADjNhJs7itegz x1Q7ZQHrNlTxixoT0vhlGAKHciWYk3j0vzR1E2jvOdMF8a8KOAjw4YzOPoPRc+H+7PYI CarrmiQAg0WThbkW0Q00OHc0XVg+97fD+gtKWpDW2Timk1naaotd9l79h2DEvNkr+4qq vYOu3QujYPZOf+2BlNO4+uBctXWmB+i/BrbT9nPKB1rlhGRep9AshxRUpZIdhAxDJQmZ bNnA== X-Gm-Message-State: AOJu0YxWG9yacj60NNvnlhMAISPoDHmkVjAy8rTZw8KJC8vyNHeYwjEU E6xQBjBikx7eLmFx833UMVmxF71xQyGsmOw08wn/XHTAvv7UQQ== X-Google-Smtp-Source: AGHT+IFc5B+iQ9TnJYe45P5TfyiQGGlts7h9x7UR2nT5kSROahvQtIM0No6vci7yHp+mv9ELyIqMFg== X-Received: by 2002:a05:6214:1cc4:b0:681:563d:1003 with SMTP id g4-20020a0562141cc400b00681563d1003mr5892072qvd.113.1705442975364; Tue, 16 Jan 2024 14:09:35 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id ee14-20020a0562140a4e00b0067f64c06bcesm4488080qvb.102.2024.01.16.14.09.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:35 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:34 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 11/17] bloom: annotate filters with hash version Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In subsequent commits, we will want to load existing Bloom filters out of a commit-graph, even when the hash version they were computed with does not match the value of `commitGraph.changedPathVersion`. In order to differentiate between the two, add a "version" field to each Bloom filter. Signed-off-by: Taylor Blau --- bloom.c | 11 ++++++++--- bloom.h | 1 + 2 files changed, 9 insertions(+), 3 deletions(-) diff --git a/bloom.c b/bloom.c index e9361b1c1f..9284b88e95 100644 --- a/bloom.c +++ b/bloom.c @@ -88,6 +88,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g, filter->data = (unsigned char *)(g->chunk_bloom_data + sizeof(unsigned char) * start_index + BLOOMDATA_CHUNK_HEADER_SIZE); + filter->version = g->bloom_filter_settings->hash_version; return 1; } @@ -273,11 +274,13 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, return strcmp(e1->path, e2->path); } -static void init_truncated_large_filter(struct bloom_filter *filter) +static void init_truncated_large_filter(struct bloom_filter *filter, + int version) { filter->data = xmalloc(1); filter->data[0] = 0xFF; filter->len = 1; + filter->version = version; } struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, @@ -362,13 +365,15 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } if (hashmap_get_size(&pathmap) > settings->max_changed_paths) { - init_truncated_large_filter(filter); + init_truncated_large_filter(filter, + settings->hash_version); if (computed) *computed |= BLOOM_TRUNC_LARGE; goto cleanup; } filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; + filter->version = settings->hash_version; if (!filter->len) { if (computed) *computed |= BLOOM_TRUNC_EMPTY; @@ -388,7 +393,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } else { for (i = 0; i < diff_queued_diff.nr; i++) diff_free_filepair(diff_queued_diff.queue[i]); - init_truncated_large_filter(filter); + init_truncated_large_filter(filter, settings->hash_version); if (computed) *computed |= BLOOM_TRUNC_LARGE; diff --git a/bloom.h b/bloom.h index 138d57a86b..330a140520 100644 --- a/bloom.h +++ b/bloom.h @@ -55,6 +55,7 @@ struct bloom_filter_settings { struct bloom_filter { unsigned char *data; size_t len; + int version; }; /* From patchwork Tue Jan 16 22:09:37 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521297 Received: from mail-qk1-f176.google.com (mail-qk1-f176.google.com [209.85.222.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A3934208D0 for ; Tue, 16 Jan 2024 22:09:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442981; cv=none; b=YtkAOFj/P14gL/Xy1WrmxziurkPesyMRWDrXTu97T2DksIwZcV1odOKb/i0KAY7IDccdnJnXytk3lxCgwCIDwro9NzTPxaxmev71OEYV3Wi7sd9UeHRLF01iSiGQkus67ewGurk+dpQ0vbml6bvtBgzejwByKQ+xMqlxJaEHBug= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442981; c=relaxed/simple; bh=PFihLOAGJeiXFMOkopSLql7ALrJgI82J0XketBAPwT8=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=DdNSEHHufiIqDVf54gBXxjmlHqAgSlh2AVlKeTGLhzPnc2oZjOVDsBdx8LtwzMDYzKoFyUkyd6XqMkqhjIVURj6YIeYCaLyHBoP/R5ah+m2oLv/anxOHrmWC7PA3GveodK2ymkarXJlCAJw8elcI0PrnHs7IFpL9JWbG4NdQu84= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=kQp2vfQs; arc=none smtp.client-ip=209.85.222.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="kQp2vfQs" Received: by mail-qk1-f176.google.com with SMTP id af79cd13be357-78336bfc489so818661685a.0 for ; Tue, 16 Jan 2024 14:09:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442978; x=1706047778; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=fsr4MwU9Zr9AKyAeizHU6UWPXptne0C0hlPQNbr05lo=; b=kQp2vfQsb50tixTEpQZGagdvs7piK3DRso+DuT2EWfsP/+s+W7oCMswbOyvH0l0f7f a1txUrkKJR2KRWRQKgTMgwLI8SJb9g5Q1fAo0ybSgi3jNlEvgY906jfzxfgKkIpRriAZ OcXi0Q8KUiT8ksdWSN/Oj06VlVGg0MA3/KOxHAyyT526EiQbiuJdDy15Z3oq940Jjx+n Sjx3JEL3sh0vJc0mM2aFKxtZPMRXAZrUmj2B9vjCm0/hnl4jZlrgDlox54CHe/BSTsSb 6ibau8cJImlpPlGKEZCoulc7j+Ss6qeFeupavyIRDoaVf2FxEo88+DMjKLL2JlqecTLZ 1WKQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442978; x=1706047778; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=fsr4MwU9Zr9AKyAeizHU6UWPXptne0C0hlPQNbr05lo=; b=EuZOIMCwB/QeH+S32Hk09w1wj8xMheVixww0kWqCuLXfu6KI3AaFd/7CghCR6emGf7 idWXLhDArMnTEjP5s+mYvX5/Yw9EAhyUtb5Ml78HGSN/3NofjHLFjfFXmMdWcMobYBBU vF3h8LKak5dJA8OovhJ+LrMKx3VWwwVBSTJ8SsbUPgbCym+YItQ6/H/JT0cXOWxaiLoY vLPn/a6U9MKyQXklp9snFLklwytHvQUo3GxSNpqQ6qLbFJaROkPAEk1Vj1y8N5YeAHCk c/lg7Sb4CZUVJz5AFodSGP+04yk+mB9QtxtHc/peonylDreNH00u3JbCBW/IB4V9Qp5/ O34g== X-Gm-Message-State: AOJu0YxSG3Nl05Nbm98oHWcV04r+SmSf5KryznwL0AJ8wtHgnRN7d6T7 LU65x31B5KJZ5db7h5HnZQny9y6GgpZiQBcJjCKd471L6dWZpw== X-Google-Smtp-Source: AGHT+IHdigsRNV7WfzCBocyd/lzjNq0Ce3TxDKrorrwii0JDTbsx3tjM2cTnNo5dQMyLvH5/HR0g1A== X-Received: by 2002:a05:620a:8420:b0:781:7591:80c8 with SMTP id pc32-20020a05620a842000b00781759180c8mr8360899qkn.86.1705442978419; Tue, 16 Jan 2024 14:09:38 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id h27-20020a05620a10bb00b0076db5b792basm4029335qkk.75.2024.01.16.14.09.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:38 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:37 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 12/17] bloom: prepare to discard incompatible Bloom filters Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Callers use the inline `get_bloom_filter()` implementation as a thin wrapper around `get_or_compute_bloom_filter()`. The former calls the latter with a value of "0" for `compute_if_not_present`, making `get_bloom_filter()` the default read-only path for fetching an existing Bloom filter. Callers expect the value returned from `get_bloom_filter()` is usable, that is that it's compatible with the configured value corresponding to `commitGraph.changedPathsVersion`. This is OK, since the commit-graph machinery only initializes its BDAT chunk (thereby enabling it to service Bloom filter queries) when the Bloom filter hash_version is compatible with our settings. So any value returned by `get_bloom_filter()` is trivially useable. However, subsequent commits will load the BDAT chunk even when the Bloom filters are built with incompatible hash versions. Prepare to handle this by teaching `get_bloom_filter()` to discard filters that are incompatible with the configured hash version. Callers who wish to read incompatible filters (e.g., for upgrading filters from v1 to v2) may use the lower level routine, `get_or_compute_bloom_filter()`. Signed-off-by: Taylor Blau --- bloom.c | 20 +++++++++++++++++++- bloom.h | 20 ++++++++++++++++++-- 2 files changed, 37 insertions(+), 3 deletions(-) diff --git a/bloom.c b/bloom.c index 9284b88e95..323d8012b8 100644 --- a/bloom.c +++ b/bloom.c @@ -283,6 +283,23 @@ static void init_truncated_large_filter(struct bloom_filter *filter, filter->version = version; } +struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c) +{ + struct bloom_filter *filter; + int hash_version; + + filter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL); + if (!filter) + return NULL; + + prepare_repo_settings(r); + hash_version = r->settings.commit_graph_changed_paths_version; + + if (!(hash_version == -1 || hash_version == filter->version)) + return NULL; /* unusable filter */ + return filter; +} + struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, struct commit *c, int compute_if_not_present, @@ -308,7 +325,8 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter, graph_pos); } - if (filter->data && filter->len) + if ((filter->data && filter->len) && + (!settings || settings->hash_version == filter->version)) return filter; if (!compute_if_not_present) return NULL; diff --git a/bloom.h b/bloom.h index 330a140520..bfe389e29c 100644 --- a/bloom.h +++ b/bloom.h @@ -110,8 +110,24 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, const struct bloom_filter_settings *settings, enum bloom_filter_computed *computed); -#define get_bloom_filter(r, c) get_or_compute_bloom_filter( \ - (r), (c), 0, NULL, NULL) +/* + * Find the Bloom filter associated with the given commit "c". + * + * If any of the following are true + * + * - the repository does not have a commit-graph, or + * - the repository disables reading from the commit-graph, or + * - the given commit does not have a Bloom filter computed, or + * - there is a Bloom filter for commit "c", but it cannot be read + * because the filter uses an incompatible version of murmur3 + * + * , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding + * Bloom filter will be returned. + * + * For callers who wish to inspect Bloom filters with incompatible hash + * versions, use get_or_compute_bloom_filter(). + */ +struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c); int bloom_filter_contains(const struct bloom_filter *filter, const struct bloom_key *key, From patchwork Tue Jan 16 22:09:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521298 Received: from mail-qk1-f174.google.com (mail-qk1-f174.google.com [209.85.222.174]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 72F9667C7B for ; Tue, 16 Jan 2024 22:09:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442983; cv=none; b=kHu0wrP8/DW38mzWVaelBEfL0dnke/xcbsKdRnN90J3EPyNA0csybIQNE1muqnwXOOC92LlQlONOVd8GFHdCw1VJFKxwR/aAZ3VKYnNXv1QeyDQzejeC10rrJ3FodSi1i/PAZTNeXXoISVL5bZJvYegZKb/kAZ+N0KFpDbgGsrY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442983; c=relaxed/simple; bh=qA4WQsDr2t6ADuVD3ZLuX28MtV0qd2DXrr/Ll8LGC48=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=jgoHJLdREDbcaeXLc/AlGGTFPWaTkaBi+fy5FiigN8xbhFdTO9v04z3hZQSZJMSnGYlzv+6ETNQ5kUocDc7o0rQUEyqdq8YHDMWjmNDsNQ+zfWCkWgnw6tOjr/BDnVWzbTEAx8SNHhWrc4zYHyjvlTeKJZsKmGHG+fvdB0QxIDI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=LFURnGS5; arc=none smtp.client-ip=209.85.222.174 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="LFURnGS5" Received: by mail-qk1-f174.google.com with SMTP id af79cd13be357-7835aea8012so140134585a.0 for ; Tue, 16 Jan 2024 14:09:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442981; x=1706047781; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=eJ6a8tmwL2Kcf8AgYsQbTKMtqUW3PoNTF+YWVM0HU4E=; b=LFURnGS5eRdmkyAIBRdc+7WDPHZaV/AQP41mmaMNfmIxP/aLatZW1gH0ZS3WKu1AYW 1FcfHszNBk+ATMDmenbV0aPN4wLm4jX4NxUy3r9Ymz7OQTjwVahhq2DY2ibzOoLZH9fR kbUFz8z3s8UX7pyf8YuONldb6r5KF4yJ+I5+AB5es2wbYNtQt69kBBx9ufTz3M9oAjn2 /hPVEtkVFHMPyNkQFUv/+bTeWT5CO2/XAiBFkJX0PaTwLdA5iT7BMloUm3KrcRQ6j9Cd rDYPlaE7Yp+hTPVWDmG2a1L80psjSYQO5uqJvXxmOdcoYOlUO4s0I0e3U0O9xaKt3oSN UOfg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442981; x=1706047781; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=eJ6a8tmwL2Kcf8AgYsQbTKMtqUW3PoNTF+YWVM0HU4E=; b=q27PR13EpKkR6Tb4KRzHbjBqSxjhY7o9K26wdSjUDbCWC0xNxk+Q9LqmUTvab0cWSG JZxdSrxSihOwxglU8D1JMa/XdTjVcDoT4U15EPLwK8utnekA/GKbSeW25AboaFhUxhCp ki/IK5yMCM9JdoaWwd36JhVnDW9pwGMtV4gu15yOGSSzPTLv/R7QQAbJXb88YUv0G7N0 GrVrvkp0UCgR7TXU4GXOP60gqUO3pum9NE9NAMOWFAYqp1oNhpJkjD5VTPB80yfYp1nn PoqKbJUC2/AsuYGPfMgaZnIuxMv0I4jTO2hjKLo/IuPIrUOyJho3SHA2/De2Gd0Jw00/ PIvw== X-Gm-Message-State: AOJu0YzHvFYHo9f8zaUBF9DP9S1hlqRed9hMRFQgDodmHXKutb+O8ACn oTkUe9nDmaHg7UvrX9s+uuW1qEq+pyoIhowNHvlZ121FgswqpA== X-Google-Smtp-Source: AGHT+IFlqXNikD9OV+OR8OOrqiDecdJ2OvFxwOMpOOcnDDjlkDtiuxXzQ4GPWI4wHJcsmrGSgZDE3A== X-Received: by 2002:a05:620a:8111:b0:783:3790:71f5 with SMTP id os17-20020a05620a811100b00783379071f5mr8401299qkn.57.1705442981353; Tue, 16 Jan 2024 14:09:41 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id t5-20020a05620a034500b0078363648c4csm1481798qkm.117.2024.01.16.14.09.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:41 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:40 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 13/17] commit-graph.c: unconditionally load Bloom filters Message-ID: <72aabd289b9e455b5fa0331fe27f73d4e6792794.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In an earlier commit, we began ignoring the Bloom data ("BDAT") chunk for commit-graphs whose Bloom filters were computed using a hash version incompatible with the value of `commitGraph.changedPathVersion`. Now that the Bloom API has been hardened to discard these incompatible filters (with the exception of low-level APIs), we can safely load these Bloom filters unconditionally. We no longer want to return early from `graph_read_bloom_data()`, and similarly do not want to set the bloom_settings' `hash_version` field as a side-effect. The latter is because we want to wait until we know which Bloom settings we're using (either the defaults, from the GIT_TEST variables, or from the previous commit-graph layer) before deciding what hash_version to use. If we detect an existing BDAT chunk, we'll infer the rest of the settings (e.g., number of hashes, bits per entry, and maximum number of changed paths) from the earlier graph layer. The hash_version will be inferred from the previous layer as well, unless one has already been specified via configuration. Once all of that is done, we normalize the value of the hash_version to either "1" or "2". Signed-off-by: Taylor Blau --- commit-graph.c | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index 22237e7dfc..a2063d5f91 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -362,11 +362,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start, hash_version = get_be32(chunk_start); - if (*c->commit_graph_changed_paths_version == -1) - *c->commit_graph_changed_paths_version = hash_version; - else if (hash_version != *c->commit_graph_changed_paths_version) - return 0; - g->chunk_bloom_data = chunk_start; g->chunk_bloom_data_size = chunk_size; g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); @@ -2532,8 +2527,7 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 0; - bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2 - ? 2 : 1; + bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version; 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", @@ -2565,10 +2559,18 @@ int write_commit_graph(struct object_directory *odb, /* We have changed-paths already. Keep them in the next graph */ if (g && g->bloom_filter_settings) { ctx->changed_paths = 1; - ctx->bloom_settings = g->bloom_filter_settings; + + /* don't propagate the hash_version unless unspecified */ + if (bloom_settings.hash_version == -1) + bloom_settings.hash_version = g->bloom_filter_settings->hash_version; + bloom_settings.bits_per_entry = g->bloom_filter_settings->bits_per_entry; + bloom_settings.num_hashes = g->bloom_filter_settings->num_hashes; + bloom_settings.max_changed_paths = g->bloom_filter_settings->max_changed_paths; } } + bloom_settings.hash_version = bloom_settings.hash_version == 2 ? 2 : 1; + if (ctx->split) { struct commit_graph *g = ctx->r->objects->commit_graph; From patchwork Tue Jan 16 22:09:44 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521299 Received: from mail-qt1-f172.google.com (mail-qt1-f172.google.com [209.85.160.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9E60867C7B for ; Tue, 16 Jan 2024 22:09:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442988; cv=none; b=pugt4fxPFz527A0R/AEoYhob7V9w7jsQgMa6JlhSk8HDcQqA5paGpwR6Tse0jyRaRQS4QMv+Dn0ZPAGWvAP3yIyPdIvXLYpcxvs2DuNWIKHv22iCtWIS+sVl1wv5f6dm34yjkE64odppML5MgOz4Gu5V9oPI7+3GHq5ZdYTK31Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442988; c=relaxed/simple; bh=xnYeMQ3HhqUftzICV3tavgVci5QpiYn8kDLlSnOuT0Y=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=ho5GFpgib3BLk+wJhz5Yg43i075DHqcvEtiWBUUTSpCdT6+TUWQMZGs3aUkaVjPUDIlprn/HMZi9JZv4YBvbdnXh0ZvnGcU/3Es92yNtxwZwoGU14eKkcDjE+en/nV8/UtmGnpXoHyLFtvTaisZUsLIYEnO/QFJbzpgXHM9br+0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=dQ4yvBpI; arc=none smtp.client-ip=209.85.160.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="dQ4yvBpI" Received: by mail-qt1-f172.google.com with SMTP id d75a77b69052e-42a029c8e62so6356501cf.1 for ; Tue, 16 Jan 2024 14:09:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442985; x=1706047785; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=QWx5+UTeuBcy9EdfxiH4bZ1HlcQmsyhhWeSJxv/FmxY=; b=dQ4yvBpIC/ri/XDjfiIHJOSAZMDso4RI3aAOMyzD6Oojxvm1stpMKtqwp4zyg4wEiW WqzrCtxjqKxqgWLbdQGRANhDIkh848FyvV0/sFavd4TtYaXyoiSBjoUP/80qmpF5pktA yrOUCq5Wc96FEx9Hg3rxNsda7K32mqm65u6vV1iRzH0RFHwz3pg5xG5u9L9TnS7tMOkX MnHpxzQQK21sZBp/TzU8nFd5sUhhIB8sHBAHIulFJPs4hIsFSA/WNVQKes8Pio4I8I+g fS818aqqXBTltw0Fr2AfIWw7vqxi6jgR/yjQSwh4ddmvZbNFuMQdu3Nq6K9JaqPaNWHe mHJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442985; x=1706047785; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=QWx5+UTeuBcy9EdfxiH4bZ1HlcQmsyhhWeSJxv/FmxY=; b=oBia8LvjK4OqwR/X/5XQwlHW3XJwxmzdDb+yMBeDDiPGkxFFoOuKwKmIrnz7TyvxGc nv2n9ecg/vEILhdC3b5VxKXKGmycJo5Cct5PPaeQcgM+8IGAS+wkgOq97lbhYTn2OFar ZeKarfzr/F6Bdm/sKtE3FUuIyMIaFJLrjAUfnEHlFyOzJZCNmRSvu7WpsB7S2b9J3oyz FlHkPVAvJf/F85AWZEtSH2NE6AuVB8DxAMeBdMOHv31RxSL2HwGfp9Qo+ACacBw3uY6Q WEOhgjaGhdm3JyXDeyV6bij16uvb1aYnJbESpbCy9fhKDexm6yZRW5UROkiaqvBJb88V s3sA== X-Gm-Message-State: AOJu0YwSDxtE62rw+ggwT+qzzZPAe28IieS47AO9s1RATk7A/robtHGQ PB8DzN09KLiBcOYcVT2F/aPSEs0xZPjsX+KQ0PJjHjdwW1boVw== X-Google-Smtp-Source: AGHT+IHiSmrMZ8urnxK2Rdq8W8Bmbj6P/n8QgTz9TJN6Twpw802/4mk98OnYcgSJFUOQqH+J0BSmRw== X-Received: by 2002:a05:622a:44d:b0:429:7412:a30b with SMTP id o13-20020a05622a044d00b004297412a30bmr10742234qtx.6.1705442985496; Tue, 16 Jan 2024 14:09:45 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id fb18-20020a05622a481200b004281ce041f6sm5257501qtb.21.2024.01.16.14.09.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:45 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:44 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 14/17] commit-graph: drop unnecessary `graph_read_bloom_data_context` Message-ID: <526beb9766a25dc97b9a4913fc02701908c0612e.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The `graph_read_bloom_data_context` struct was introduced in an earlier commit in order to pass pointers to the commit-graph and changed-path Bloom filter version when reading the BDAT chunk. The previous commit no longer writes through the changed_paths_version pointer, making the surrounding context structure unnecessary. Drop it and pass a pointer to the commit-graph directly when reading the BDAT chunk. Noticed-by: Jonathan Tan Signed-off-by: Taylor Blau --- commit-graph.c | 14 ++------------ 1 file changed, 2 insertions(+), 12 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index a2063d5f91..a02556716d 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -340,16 +340,10 @@ static int graph_read_bloom_index(const unsigned char *chunk_start, return 0; } -struct graph_read_bloom_data_context { - 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 graph_read_bloom_data_context *c = data; - struct commit_graph *g = c->g; + struct commit_graph *g = data; uint32_t hash_version; if (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) { @@ -463,14 +457,10 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, } if (s->commit_graph_changed_paths_version) { - struct graph_read_bloom_data_context context = { - .g = graph, - .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version - }; read_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, graph_read_bloom_index, graph); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - graph_read_bloom_data, &context); + graph_read_bloom_data, graph); } if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) { From patchwork Tue Jan 16 22:09:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521300 Received: from mail-qv1-f51.google.com (mail-qv1-f51.google.com [209.85.219.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9C6EE2136A for ; Tue, 16 Jan 2024 22:09:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442990; cv=none; b=q7hMlIyaPeOZ2uoPsRjXHiMi+uYz4/eLIiymALnDWtdCW8p04xasTPga8/S114swyxsl4A7gPbYtPcYEyH2lNLkvNQbOizBNrcVaIlKnWmqq36QBxf5fikTivdeJHuxAxDKn+KW0Fe0oJvKJZhg+f16ewyZbx+kMZx+riHvWDaY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442990; c=relaxed/simple; bh=22F9Bhu28H1UjgXGUBadL4LV+KptX6Xj9iVcYUxIoAM=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=OxUwcq9YLuzLL5D5aaz4MB3O0CM436bYEwz6VUdPiS/gqnQGiH8fw+0CUqfzOVlBpxrbgD78le5Sy9g+Qq9YOggvzWkN+W+hxgpEv92tTBk1fjf60hW/4ymuAFNsnpmhSXzxO7pUE/tEIc4QgnXxolQels3i9cjWzkhFly/K0dk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=0byTZHGZ; arc=none smtp.client-ip=209.85.219.51 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="0byTZHGZ" Received: by mail-qv1-f51.google.com with SMTP id 6a1803df08f44-68176e698e3so4548746d6.1 for ; Tue, 16 Jan 2024 14:09:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442988; x=1706047788; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=GRw+VCe4f+5VG4o6oN1F+ZzVT/It3zgP/nQn8mbSGaU=; b=0byTZHGZ6QsZKJBX/CdoQeqXBNbngS5z+Xi61Utdqotd6CdXh6tI653HsMl+NeZzF9 4vx7w8cnApaaOn/Dp/6guh9BUgcULdZawbKqVTOC1eyY9pvBbzTWGQ1QjmiyEBBdFsHo 1fSs9U6vvxK6OPXtN2YjIi0PiMnnQf+4a2Y3I52tkSASr3cv8O6qG/H4WxkjFMmzzHMP we7Oe3nqIMlF50O437sVSry0teFz6Ws1AfigdJH2lBg6NO5H/BgtQs/+cHni0IaSKbBW 0DjZOIlfg2FIzGK/S+1EnMexRHijoBIHWIVUP3nFoe9OhqnhBqEipRo8BZgb2U8Pabm2 CUyg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442988; x=1706047788; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=GRw+VCe4f+5VG4o6oN1F+ZzVT/It3zgP/nQn8mbSGaU=; b=RBzHOAmRFuiyIqJWnu2DGit/8auFMRC7nszR87WdhcX1o7N9G5ENTgCzQFkBujpoSH XVNfj+YE/SIqoU4nq4tD8N2eCrYV4uTG4w0VmBz1IVsW8HEfKA6dGoX7sOkGYcYEHFie afVAb0UVaBDumnXfgaRSQOiyC98EPeoZqRildT8mtTgdGExwggTY53aqzLf/0E+PM0k3 qDDhUvAUYoC4D3ooXLuzyyA9eEao2aFjr+wdJyaAkLriDWpm63b8nlrkxAnjRoGaGeBu mi5TPChso8FkdSnLILhB1C4nYJwtmFYYtJS6a77uxkcJCnvdnaKGbmLvEMVrrRNaI3S7 3muA== X-Gm-Message-State: AOJu0YyYb3OW0oYMlaY9HglpjqKXtuFGd3YQP6ix9QBdp65eePoinYyQ lw355FIK20iSa4mRgzs9OrPgIsPbMzIFg0ro6WmluWEbceZzQg== X-Google-Smtp-Source: AGHT+IElABwJNp7IAWiuyO2IzeAbjs63+Ig6emNx0/jzQyjyTpolFT9kKYaVhS/+a8eHpe/gWuTZiQ== X-Received: by 2002:a05:6214:410:b0:681:3a94:789 with SMTP id z16-20020a056214041000b006813a940789mr10425035qvx.78.1705442988462; Tue, 16 Jan 2024 14:09:48 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id db6-20020a056214170600b00681770c1aaesm488198qvb.125.2024.01.16.14.09.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:48 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:47 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 15/17] object.h: fix mis-aligned flag bits table Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Bit position 23 is one column too far to the left. Signed-off-by: Taylor Blau --- object.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/object.h b/object.h index 114d45954d..db25714b4e 100644 --- a/object.h +++ b/object.h @@ -62,7 +62,7 @@ void object_array_init(struct object_array *array); /* * object flag allocation: - * revision.h: 0---------10 15 23------27 + * revision.h: 0---------10 15 23------27 * fetch-pack.c: 01 67 * negotiator/default.c: 2--5 * walker.c: 0-2 From patchwork Tue Jan 16 22:09:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521301 Received: from mail-qv1-f53.google.com (mail-qv1-f53.google.com [209.85.219.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 06B552136A for ; Tue, 16 Jan 2024 22:09:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442994; cv=none; b=KTSKZkgiJ4f3VK8VvyJSigfJ3Gq3ihIWFuB1+klUX6c1s9JemTz1x3C8KBBFCJgJOvZ4mbQbXvVVF/NpwlnPHsHNOWkzoF7y45YRGFUlAYCUKPuy8B3LY6jPsPNm5nUNeMWwbKtV48ZRF58/fa8chWcYutGG0us8CoeVrrLiEVc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442994; c=relaxed/simple; bh=czkZiKcnqdH+xamLI0LQh9hDOJCz2frhG5RMKz3Lh2I=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:Content-Transfer-Encoding:In-Reply-To; b=cVzXq8mrtCCsHFwQojPAoX3UaGgJeyitmJgevHx1ebb69QGM3nDLKVWZ9oRYt6xTlFdJzNENzUdhUyD8YXiNPMhoVYtrd3KM5d1+eD5Ljba26/8KZMHzs3WQb5PBgNQXPHRu6EZbSMhhJGuL5JGjU+DPfecPh5QSWZGFF2MEtZM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=rf3diiEx; arc=none smtp.client-ip=209.85.219.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="rf3diiEx" Received: by mail-qv1-f53.google.com with SMTP id 6a1803df08f44-68137fd70b4so30272246d6.2 for ; Tue, 16 Jan 2024 14:09:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442991; x=1706047791; darn=vger.kernel.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=6Vw0DofzGiQ8Me7Dn5JbN0yEve9RLY4MvKA+x24gCto=; b=rf3diiExWAuMAiUrNPFtrjnO7KWPpxajhhDXhoAc390iVrzg6sDbuYfJYFcidclBb5 qlJ/UcJEcydGcr1TzO10dagPxQQ76YgeQSD+/5BZbfOb4pJZQ6oiWYvP4fFixIRePbVw MiEpDOztAPWdz/A+js2j/QCvZe4Xcq7A2ZRw0GZjmUQDgBMLg/98BawUVhAvKPalytyt sy61QPWLgsXW95GC46kOI8LIThF2i6AWLysMkgNlWBmKBwj1+N78eVwQOAuqVYY2m3bY gejMcXFBlFKoJfdfnKY1wzB292PFFpn7Hk6GSHB4cwQhGCpR1BEBmskXs3jFI7y7TyM2 JZDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442991; x=1706047791; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=6Vw0DofzGiQ8Me7Dn5JbN0yEve9RLY4MvKA+x24gCto=; b=K64QZcZanod5F6xccpzmxg9HiKHG5Oy09PHzC4vdR+S/lFBagGPfkL2Nql6PQOaBzz T5wkg0Z3oaGBciM8HQlL+ViRFmiyrPOAbyjGKbsKquFKh8dDvgmo2tMpqMNHuJZN9kGI Fb2jTWW/3/MjGIKn5iGJEjNKaoEuZfckgJpCMl8MNlymJyEVETD/Ip0qchlxL3Sp0oMs FiwMhWQrrD1XacE2bxuilFOUPJjmYIBuuBy+7Cyk39t+g97rpHjW/TKaOR1C08+4yY/Y Pg6aMsipWiwVOiiTpJJ/AWPryGmMD1yLjqS5uRDoiYK6GyOjCDvhP3Z9JxdRCRvI0GrY Wabw== X-Gm-Message-State: AOJu0YyA9IvuBR5aSP8ztQuZ0b7z7FiRm0r08zWr4WIyxxT4dxAQA7SV MbroX9RmqqD3PIno0VdeM8HLjBmbKY3uVcBroh8L7EqBerlUOg== X-Google-Smtp-Source: AGHT+IHQ1nySocbwCWvzWqVLwycSHuOyGllkbrQQr80XjxPBv5G0QiQMnmUf2H8uv+mKTv/RfZX7Wg== X-Received: by 2002:a05:6214:1245:b0:681:24af:49b7 with SMTP id r5-20020a056214124500b0068124af49b7mr8812156qvv.27.1705442991504; Tue, 16 Jan 2024 14:09:51 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id ee20-20020a0562140a5400b0067f3a71ad96sm4499566qvb.72.2024.01.16.14.09.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:51 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:50 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 16/17] commit-graph: reuse existing Bloom filters where possible Message-ID: <4bf043be9aff322279854ce96afe697f362ac60b.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In an earlier commit, a bug was described where it's possible for Git to produce non-murmur3 hashes when the platform's "char" type is signed, and there are paths with characters whose highest bit is set (i.e. all characters >= 0x80). That patch allows the caller to control which version of Bloom filters are read and written. However, even on platforms with a signed "char" type, it is possible to reuse existing Bloom filters if and only if there are no changed paths in any commit's first parent tree-diff whose characters have their highest bit set. When this is the case, we can reuse the existing filter without having to compute a new one. This is done by marking trees which are known to have (or not have) any such paths. When a commit's root tree is verified to not have any such paths, we mark it as such and declare that the commit's Bloom filter is reusable. Note that this heuristic only goes in one direction. If neither a commit nor its first parent have any paths in their trees with non-ASCII characters, then we know for certain that a path with non-ASCII characters will not appear in a tree-diff against that commit's first parent. The reverse isn't necessarily true: just because the tree-diff doesn't contain any such paths does not imply that no such paths exist in either tree. So we end up recomputing some Bloom filters that we don't strictly have to (i.e. their bits are the same no matter which version of murmur3 we use). But culling these out is impossible, since we'd have to perform the full tree-diff, which is the same effort as computing the Bloom filter from scratch. But because we can cache our results in each tree's flag bits, we can often avoid recomputing many filters, thereby reducing the time it takes to run $ git commit-graph write --changed-paths --reachable when upgrading from v1 to v2 Bloom filters. To benchmark this, let's generate a commit-graph in linux.git with v1 changed-paths in generation order[^1]: $ git clone git@github.com:torvalds/linux.git $ cd linux $ git commit-graph write --reachable --changed-paths $ graph=".git/objects/info/commit-graph" $ mv $graph{,.bak} Then let's time how long it takes to go from v1 to v2 filters (with and without the upgrade path enabled), resetting the state of the commit-graph each time: $ git config commitGraph.changedPathsVersion 2 $ hyperfine -p 'cp -f $graph.bak $graph' -L v 0,1 \ 'GIT_TEST_UPGRADE_BLOOM_FILTERS={v} git.compile commit-graph write --reachable --changed-paths' On linux.git (where there aren't any non-ASCII paths), the timings indicate that this patch represents a speed-up over recomputing all Bloom filters from scratch: Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths Time (mean ± σ): 124.873 s ± 0.316 s [User: 124.081 s, System: 0.643 s] Range (min … max): 124.621 s … 125.227 s 3 runs Benchmark 2: GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths Time (mean ± σ): 79.271 s ± 0.163 s [User: 74.611 s, System: 4.521 s] Range (min … max): 79.112 s … 79.437 s 3 runs Summary 'GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths' ran 1.58 ± 0.01 times faster than 'GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths' On git.git, we do have some non-ASCII paths, giving us a more modest improvement from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up. On my machine, the stats for git.git are: - 8,285 Bloom filters computed from scratch - 10 Bloom filters generated as empty - 4 Bloom filters generated as truncated due to too many changed paths - 65,114 Bloom filters were reused when transitioning from v1 to v2. [^1]: Note that this is is important, since `--stdin-packs` or `--stdin-commits` orders commits in the commit-graph by their pack position (with `--stdin-packs`) or in the raw input (with `--stdin-commits`). Since we compute Bloom filters in the same order that commits appear in the graph, we must see a commit's (first) parent before we process the commit itself. This is only guaranteed to happen when sorting commits by their generation number. Signed-off-by: Taylor Blau --- bloom.c | 90 ++++++++++++++++++++++++++++++++++++++++++-- bloom.h | 1 + commit-graph.c | 5 +++ object.h | 1 + t/t4216-log-bloom.sh | 35 ++++++++++++++++- 5 files changed, 128 insertions(+), 4 deletions(-) diff --git a/bloom.c b/bloom.c index 323d8012b8..a1c616bc71 100644 --- a/bloom.c +++ b/bloom.c @@ -6,6 +6,9 @@ #include "commit-graph.h" #include "commit.h" #include "commit-slab.h" +#include "tree.h" +#include "tree-walk.h" +#include "config.h" define_commit_slab(bloom_filter_slab, struct bloom_filter); @@ -283,6 +286,73 @@ static void init_truncated_large_filter(struct bloom_filter *filter, filter->version = version; } +#define VISITED (1u<<21) +#define HIGH_BITS (1u<<22) + +static int has_entries_with_high_bit(struct repository *r, struct tree *t) +{ + if (parse_tree(t)) + return 1; + + if (!(t->object.flags & VISITED)) { + struct tree_desc desc; + struct name_entry entry; + + init_tree_desc(&desc, t->buffer, t->size); + while (tree_entry(&desc, &entry)) { + size_t i; + for (i = 0; i < entry.pathlen; i++) { + if (entry.path[i] & 0x80) { + t->object.flags |= HIGH_BITS; + goto done; + } + } + + if (S_ISDIR(entry.mode)) { + struct tree *sub = lookup_tree(r, &entry.oid); + if (sub && has_entries_with_high_bit(r, sub)) { + t->object.flags |= HIGH_BITS; + goto done; + } + } + + } + +done: + t->object.flags |= VISITED; + } + + return !!(t->object.flags & HIGH_BITS); +} + +static int commit_tree_has_high_bit_paths(struct repository *r, + struct commit *c) +{ + struct tree *t; + if (repo_parse_commit(r, c)) + return 1; + t = repo_get_commit_tree(r, c); + if (!t) + return 1; + return has_entries_with_high_bit(r, t); +} + +static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c, + struct bloom_filter *filter, + int hash_version) +{ + struct commit_list *p = c->parents; + if (commit_tree_has_high_bit_paths(r, c)) + return NULL; + + if (p && commit_tree_has_high_bit_paths(r, p->item)) + return NULL; + + filter->version = hash_version; + + return filter; +} + struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c) { struct bloom_filter *filter; @@ -325,9 +395,23 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter, graph_pos); } - if ((filter->data && filter->len) && - (!settings || settings->hash_version == filter->version)) - return filter; + if (filter->data && filter->len) { + struct bloom_filter *upgrade; + if (!settings || settings->hash_version == filter->version) + return filter; + + /* version mismatch, see if we can upgrade */ + if (compute_if_not_present && + git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) { + upgrade = upgrade_filter(r, c, filter, + settings->hash_version); + if (upgrade) { + if (computed) + *computed |= BLOOM_UPGRADED; + return upgrade; + } + } + } if (!compute_if_not_present) return NULL; diff --git a/bloom.h b/bloom.h index bfe389e29c..e3a9b68905 100644 --- a/bloom.h +++ b/bloom.h @@ -102,6 +102,7 @@ enum bloom_filter_computed { BLOOM_COMPUTED = (1 << 1), BLOOM_TRUNC_LARGE = (1 << 2), BLOOM_TRUNC_EMPTY = (1 << 3), + BLOOM_UPGRADED = (1 << 4), }; struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, diff --git a/commit-graph.c b/commit-graph.c index a02556716d..b285e32043 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1167,6 +1167,7 @@ struct write_commit_graph_context { int count_bloom_filter_not_computed; int count_bloom_filter_trunc_empty; int count_bloom_filter_trunc_large; + int count_bloom_filter_upgraded; }; static int write_graph_chunk_fanout(struct hashfile *f, @@ -1774,6 +1775,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte ctx->count_bloom_filter_trunc_empty); trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large", ctx->count_bloom_filter_trunc_large); + trace2_data_intmax("commit-graph", ctx->r, "filter-upgraded", + ctx->count_bloom_filter_upgraded); } static void compute_bloom_filters(struct write_commit_graph_context *ctx) @@ -1815,6 +1818,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) ctx->count_bloom_filter_trunc_empty++; if (computed & BLOOM_TRUNC_LARGE) ctx->count_bloom_filter_trunc_large++; + } else if (computed & BLOOM_UPGRADED) { + ctx->count_bloom_filter_upgraded++; } else if (computed & BLOOM_NOT_COMPUTED) ctx->count_bloom_filter_not_computed++; ctx->total_bloom_filter_data_size += filter diff --git a/object.h b/object.h index db25714b4e..2e5e08725f 100644 --- a/object.h +++ b/object.h @@ -75,6 +75,7 @@ void object_array_init(struct object_array *array); * commit-reach.c: 16-----19 * sha1-name.c: 20 * list-objects-filter.c: 21 + * bloom.c: 2122 * builtin/fsck.c: 0--3 * builtin/gc.c: 0 * builtin/index-pack.c: 2021 diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index a7bf3a7dca..823d1cf773 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -222,6 +222,10 @@ test_filter_trunc_large () { grep "\"key\":\"filter-trunc-large\",\"value\":\"$1\"" $2 } +test_filter_upgraded () { + grep "\"key\":\"filter-upgraded\",\"value\":\"$1\"" $2 +} + test_expect_success 'correctly report changes over limit' ' git init limits && ( @@ -656,7 +660,13 @@ test_expect_success 'when writing another commit graph, preserve existing versio test_expect_success 'when writing commit graph, do not reuse changed-path of another version' ' git init doublewrite && test_commit -C doublewrite c "$CENT" && + git -C doublewrite config --add commitgraph.changedPathsVersion 1 && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C doublewrite commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace2.txt && + test_filter_upgraded 0 trace2.txt && + git -C doublewrite commit-graph write --reachable --changed-paths && for v in -2 3 do @@ -667,8 +677,13 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano EOF test_cmp expect err || return 1 done && + git -C doublewrite config --add commitgraph.changedPathsVersion 2 && - git -C doublewrite commit-graph write --reachable --changed-paths && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C doublewrite commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace2.txt && + test_filter_upgraded 0 trace2.txt && + ( cd doublewrite && echo "c01f" >expect && @@ -677,6 +692,24 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano ) ' +test_expect_success 'when writing commit graph, reuse changed-path of another version where possible' ' + git init upgrade && + + test_commit -C upgrade base no-high-bits && + + git -C upgrade config --add commitgraph.changedPathsVersion 1 && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C upgrade commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace2.txt && + test_filter_upgraded 0 trace2.txt && + + git -C upgrade config --add commitgraph.changedPathsVersion 2 && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C upgrade commit-graph write --reachable --changed-paths && + test_filter_computed 0 trace2.txt && + test_filter_upgraded 1 trace2.txt +' + corrupt_graph () { test_when_finished "rm -rf $graph" && git commit-graph write --reachable --changed-paths && From patchwork Tue Jan 16 22:09:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13521302 Received: from mail-qv1-f42.google.com (mail-qv1-f42.google.com [209.85.219.42]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 839CD57302 for ; Tue, 16 Jan 2024 22:09:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442996; cv=none; b=J9cG1kmDirBCEG+37dlK+MFRCsayNllXrsWToMJvbm4IPDRrBVb1ibh8Bql4TwD/Q3k7OyWH8g6EEpOJDn5K/SamYg32pkGnL+khJvcnpUt7nY7586ecVgYdEJ6Awh1O3r0N/5px6usFzvQ47OlLUGdcg+UwOl1vaq23DEBfCoE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1705442996; c=relaxed/simple; bh=jXv0e7vl7xxRbLuml1Ep0eWejDjf4awpXIOYEIfYS9A=; h=Received:DKIM-Signature:X-Google-DKIM-Signature: X-Gm-Message-State:X-Google-Smtp-Source:X-Received:Received:Date: From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type: Content-Disposition:In-Reply-To; b=POfcjfNDLg/57vD6cP8sr6PX7CpQHljDN5E6hlqkB9+aiwBTJwYSzaXikY1zm9NoLXpOpbQK/roHXJm+qDkDkKsPrNY47iLjyasNnLcSRrFoGHSzcmebfryS2e+yvkfaS1rdhxG53cqPwioyrHat8j8QrXk51A0SQRV0JIpvj4w= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=QfDdPVTC; arc=none smtp.client-ip=209.85.219.42 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="QfDdPVTC" Received: by mail-qv1-f42.google.com with SMTP id 6a1803df08f44-68175861f3eso4618516d6.3 for ; Tue, 16 Jan 2024 14:09:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1705442994; x=1706047794; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=20F2pHVGsJi0lMQBok531KeHnqA3E6H/Lw1Uc5J8/FI=; b=QfDdPVTCXUsFNgu9bIShZvOJyc0mD+R8t1EXFibdW8KRXaswPSeBH8Eannfev9wE6j hikQnC4cn5PutQBVm0QKIudJW55xz9Dtg/PNgNuzQKvy1UHYcUKdxyBQH1iieBxGzqr5 H+bLwie+9Z6KXE92mmtXZyrshsnEZw+nhSfPLcewZ8IG77vM1En8+2fxZ9c6AsfvpuIh VF/9igc8/vmgbKjt3UvYzDIP5dKPm91pBiI4nZ07r6N37EzznpqFPHRuTmBI0RmjLWQY PoksoSPpXuCEHdZhqfeDpwsM3d1kt5EvSzfHdUYj7ynHF7S3dXXsVCJGjipMJ/teWUKv q2Lw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705442994; x=1706047794; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=20F2pHVGsJi0lMQBok531KeHnqA3E6H/Lw1Uc5J8/FI=; b=PTTInTUMWbU9KmlePqXC3QJQeBHoPKHEFVIk3hFBa5ft5RhmB/LjEAQhit1QUTJ+bf cW6KrmguEpvribQ80SDMOFTCMRk0e89TupPg8aenC5V566fwU8ilEjDe7cO2olQAbA8U yqWLln4mNZApEtJ1UEgmLZTLYpidqAfiqv4yXvutgKA2G1JyW1boGenUFkPz9+cTPo73 yXx6TEGfYIQVQD/AIL/WNcdSBJQBiiE9t06k08o3Yo460QdsY+TuhuM4wDg2uYq5wXYl /T7zYE/aOVXjrIJsrFg8G15R/lXm5X2ZPJOjlpFYLxKiJfqoTY4nRTWpKjxQBMWjMnc2 uuHg== X-Gm-Message-State: AOJu0YxEur+m8KEo1hZCJkaG+yZClWqLCzAm7l3kicUBjXrRFiu/rnBC KaZg1Sy40xoOZQyYzBOZqncLj9s7feiWHQlw8moXodf+TI5eeQ== X-Google-Smtp-Source: AGHT+IEu6p1jhLUcGuyahQTDE4Gppk+YdyTkgPSidovfsoSSUa4V1NdKyk4a+0rLhSbdCtu2qi8g6w== X-Received: by 2002:a05:6214:c4b:b0:681:77e8:be93 with SMTP id r11-20020a0562140c4b00b0068177e8be93mr951991qvj.67.1705442994258; Tue, 16 Jan 2024 14:09:54 -0800 (PST) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id ee20-20020a0562140a5400b0067f3a71ad96sm4499601qvb.72.2024.01.16.14.09.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Jan 2024 14:09:54 -0800 (PST) Date: Tue, 16 Jan 2024 17:09:53 -0500 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , "Eric W. Biederman" , Jeff King , Junio C Hamano , Patrick Steinhardt , Jonathan Tan , SZEDER =?utf-8?b?R8OhYm9y?= Subject: [PATCH v5 17/17] bloom: introduce `deinit_bloom_filters()` Message-ID: <7daa0d8833ebe9aba0de90f43f279dd6d87d634f.1705442923.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: After we are done using Bloom filters, we do not currently clean up any memory allocated by the commit slab used to store those filters in the first place. Besides the bloom_filter structures themselves, there is mostly nothing to free() in the first place, since in the read-only path all Bloom filter's `data` members point to a memory mapped region in the commit-graph file itself. But when generating Bloom filters from scratch (or initializing truncated filters) we allocate additional memory to store the filter's data. Keep track of when we need to free() this additional chunk of memory by using an extra pointer `to_free`. Most of the time this will be NULL (indicating that we are representing an existing Bloom filter stored in a memory mapped region). When it is non-NULL, free it before discarding the Bloom filters slab. Suggested-by: Jonathan Tan Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- bloom.c | 16 +++++++++++++++- bloom.h | 3 +++ commit-graph.c | 4 ++++ 3 files changed, 22 insertions(+), 1 deletion(-) diff --git a/bloom.c b/bloom.c index a1c616bc71..dbcc0f4f50 100644 --- a/bloom.c +++ b/bloom.c @@ -92,6 +92,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g, sizeof(unsigned char) * start_index + BLOOMDATA_CHUNK_HEADER_SIZE); filter->version = g->bloom_filter_settings->hash_version; + filter->to_free = NULL; return 1; } @@ -264,6 +265,18 @@ void init_bloom_filters(void) init_bloom_filter_slab(&bloom_filters); } +static void free_one_bloom_filter(struct bloom_filter *filter) +{ + if (!filter) + return; + free(filter->to_free); +} + +void deinit_bloom_filters(void) +{ + deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key, @@ -280,7 +293,7 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, static void init_truncated_large_filter(struct bloom_filter *filter, int version) { - filter->data = xmalloc(1); + filter->data = filter->to_free = xmalloc(1); filter->data[0] = 0xFF; filter->len = 1; filter->version = version; @@ -482,6 +495,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter->len = 1; } CALLOC_ARRAY(filter->data, filter->len); + filter->to_free = filter->data; hashmap_for_each_entry(&pathmap, &iter, e, entry) { struct bloom_key key; diff --git a/bloom.h b/bloom.h index e3a9b68905..d20e64bfbb 100644 --- a/bloom.h +++ b/bloom.h @@ -56,6 +56,8 @@ struct bloom_filter { unsigned char *data; size_t len; int version; + + void *to_free; }; /* @@ -96,6 +98,7 @@ void add_key_to_filter(const struct bloom_key *key, const struct bloom_filter_settings *settings); void init_bloom_filters(void); +void deinit_bloom_filters(void); enum bloom_filter_computed { BLOOM_NOT_COMPUTED = (1 << 0), diff --git a/commit-graph.c b/commit-graph.c index b285e32043..1841638801 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -830,6 +830,7 @@ struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r) void close_commit_graph(struct raw_object_store *o) { clear_commit_graph_data_slab(&commit_graph_data_slab); + deinit_bloom_filters(); free_commit_graph(o->commit_graph); o->commit_graph = NULL; } @@ -2648,6 +2649,9 @@ int write_commit_graph(struct object_directory *odb, res = write_commit_graph_file(ctx); + if (ctx->changed_paths) + deinit_bloom_filters(); + if (ctx->split) mark_commit_graphs(ctx);