From patchwork Wed Sep 4 08:53:00 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13790126 Received: from fhigh6-smtp.messagingengine.com (fhigh6-smtp.messagingengine.com [103.168.172.157]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5E55D19750B for ; Wed, 4 Sep 2024 08:53:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.157 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725439986; cv=none; b=f0mQ2Bwv7odI0ym5fnA7BrrtYhAuxffStYZ/DjoWJBTaGrKDOfIXboSQ8Ygbf+DZAzUdPyjuzl9PLO/o3yM2FiFtwZGLX6s6Smn0sHiHb80xmXzBVcCMoJdPJzxfbRdVLJ1Xo6+m3lCAxJ/OXbhUEyuwcE8gCdBnL23D39UxBMc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725439986; c=relaxed/simple; bh=EJDmh61Sr6V+Q+nrp+xdWabQIwVGPt49fohkXo6Wbks=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=GqQsA78J8r5F+g6T2jWw7lpqgqFrQE1vk09nr2SQDjhETMckSmfv7Z9CVnmGF+TnO43y9mpcI/pU/INKmE0sJSM3yx5MvgsV6852p76gBLFPRSmOZR4ggKcVxORJgYekb6yNRKYSzGVGn8Ngd49soBh+RvXbReZfKRUfZqhFkuI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=OG4SUyop; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=AVhOv+2g; arc=none smtp.client-ip=103.168.172.157 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="OG4SUyop"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="AVhOv+2g" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfhigh.phl.internal (Postfix) with ESMTP id 72D1E11401AB; Wed, 4 Sep 2024 04:53:03 -0400 (EDT) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-02.internal (MEProxy); Wed, 04 Sep 2024 04:53:03 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm1; t=1725439983; x=1725526383; bh=rvUP/6fPYA MXChw9BRkcF3YWKAY3ugQCCYsWfrhQVQY=; b=OG4SUyopczsA2AFXdKOuiWTMPs D1YbgN+yRQvQLyXoNzDwZoyfy4bjVTDqdODto7sbx27b4rV0vUkbiGNshw42nnuh HC/QLmzWZeVnLZGuCGBHveHFZUEdCy4925u0I+zzIdbuuqZcUwSdpTIrc+dZdSkq uEbQrkjIVKc7q1QxyKRjbjqYfhKUYgIBTOUXHjd9xXeH2owv9mUPGwdK0B5EOYI9 g4J5D/JEy9ju9qCk/Q8Ky+mhonksHb1uDdy01v5hs+jzl2i70aX3lK6PUb7pGy1o HZv9vzSKIblPRKwfa3NmS5KxIkM9ozBzCRPteoEXKiEXnuuVBzb8Oys9tsXA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm1; t=1725439983; x=1725526383; bh=rvUP/6fPYAMXChw9BRkcF3YWKAY3 ugQCCYsWfrhQVQY=; b=AVhOv+2gkyzEnINuaMKE6/8xqzRl3zVWjNMJzeHpel3Z dRawHEJwS1+rwpJ/0Dfhz/6a2hW62cFSt0BNTMEkkzSTsjGMZ5YlRtEBXQep5hZg 7VtyjXYKhMDCw/Pnn5KxTy0Z1O01cNudrN6dXX6U15nEHUxnkw7UI+3mF0q4zTO5 bFHXbH3rg6idOKrQByYLdP/BksJqzSHutuYQBbKT2KTj2jWH3FkxFJksHXzc6wFl YXIh2mLMNO9AV975kJCI8tJ3Y12g95HhPC70BqTSMpm5arlt39Q2i9AXkQ5ZuqvR g9FE4FlRPOOwqrhLOc+kLGvaC89PaobyKhHMjUi38g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudehjedgtdelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhepfffhvfevuffkfhggtggujgesthdtredttddtvden ucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrdhimh eqnecuggftrfgrthhtvghrnhepveekkeffhfeitdeludeigfejtdetvdelvdduhefgueeg udfghfeukefhjedvkedtnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrg hilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepfedpmhhouggvpehs mhhtphhouhhtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprhgtph htthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohepghhi thesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Wed, 4 Sep 2024 04:53:02 -0400 (EDT) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 44d84265 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Wed, 4 Sep 2024 08:52:53 +0000 (UTC) Date: Wed, 4 Sep 2024 10:53:00 +0200 From: Patrick Steinhardt To: git@vger.kernel.org Cc: karthik nayak , Junio C Hamano Subject: [PATCH v2 1/3] wrapper: introduce `log2u()` 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: We have an implementation of a function that computes the log2 for an integer. While we could instead use log2(3P), that involves floating point numbers and is thus needlessly complex and inefficient. We're about to add a second caller that wants to compute log2 for a `size_t`. Let's thus move the function into "wrapper.h" such that it becomes generally available. While at it, tweak the implementation a bit: - The parameter is converted from `int` to `uintmax_t`. This conversion is safe to do in "bisect.c" because we already check that the argument is positive. - The return value is an `unsigned`. It cannot ever be negative, so it is pointless for it to be a signed integer. - Loop until `!n` instead of requiring that `n > 1` and then subtract 1 from the result and add a special case for `!sz`. This helps compilers to generate more efficient code. Compilers recognize the pattern of this function and optimize accordingly. On GCC 14.2 x86_64: log2u(unsigned long): test rdi, rdi je .L3 bsr rax, rdi ret .L3: mov eax, -1 ret Clang 18.1 does not yet recognize the pattern, but starts to do so on Clang trunk x86_64. The code isn't quite as efficient as the one generated by GCC, but still manages to optimize away the loop: log2u(unsigned long): test rdi, rdi je .LBB0_1 shr rdi bsr rcx, rdi mov eax, 127 cmovne rax, rcx xor eax, -64 add eax, 65 ret .LBB0_1: mov eax, -1 ret The pattern is also recognized on other platforms like ARM64 GCC 14.2.0, where we end up using `clz`: log2u(unsigned long): clz x2, x0 cmp x0, 0 mov w1, 63 sub w0, w1, w2 csinv w0, w0, wzr, ne ret Note that we have a similar function `fastlog2()` in the reftable code. As that codebase is separate from the Git codebase we do not adapt it to use the new function. Signed-off-by: Patrick Steinhardt --- bisect.c | 12 +----------- wrapper.h | 18 ++++++++++++++++++ 2 files changed, 19 insertions(+), 11 deletions(-) diff --git a/bisect.c b/bisect.c index 4406fc44cf9..4713226fad4 100644 --- a/bisect.c +++ b/bisect.c @@ -1130,16 +1130,6 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix) return res; } -static inline int log2i(int n) -{ - int log2 = 0; - - for (; n > 1; n >>= 1) - log2++; - - return log2; -} - static inline int exp2i(int n) { return 1 << n; @@ -1162,7 +1152,7 @@ int estimate_bisect_steps(int all) if (all < 3) return 0; - n = log2i(all); + n = log2u(all); e = exp2i(n); x = all - e; diff --git a/wrapper.h b/wrapper.h index 1b2b047ea06..a6b3e1f09ec 100644 --- a/wrapper.h +++ b/wrapper.h @@ -140,4 +140,22 @@ int csprng_bytes(void *buf, size_t len); */ uint32_t git_rand(void); +/* Provide log2 of the given `size_t`. */ +static inline unsigned log2u(uintmax_t sz) +{ + unsigned l = 0; + + /* + * Technically this isn't required, but it helps the compiler optimize + * this to a `bsr` instruction. + */ + if (!sz) + return 0; + + for (; sz; sz >>= 1) + l++; + + return l - 1; +} + #endif /* WRAPPER_H */ From patchwork Wed Sep 4 08:53:03 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13790127 Received: from fout1-smtp.messagingengine.com (fout1-smtp.messagingengine.com [103.168.172.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7F882199E8B for ; Wed, 4 Sep 2024 08:53:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725439989; cv=none; b=XR0yhYI/kqSkkT6jhLtgs3Ozas80wAegKRi9iYWUdV3gDu1DaKrErXP7oLWfMpKZ4BZECXYhysKDK8F0t3V1MOAEmrwIUPs3mqy7kq0+BiljQUXUUpVemfK8Nx4E+v8LKaIZFm9Q0u3ocf2m554oxUiRRSDuInrpw6ka7zEuLDw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725439989; c=relaxed/simple; bh=5lQTPuOgEuq4PV8KcSG0MApPb61mlWwpCttcFxN48fo=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=kWyBIP15AyzgzXxzDati7QNSibT10moI4ixCa/x8aEJPPjMTGQUjchX21Oc6l+vx7kLnyHvy7I+XaI3RWss5mkKqBZn6uYBAyYmcBWfkP0y2mEqTrF42Xs5JaOBZJ4Fzcv4JtitI5Gkf1FWUUuohJyiLoZhdZM85Ejd3HqBSpOc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=ZQXc9H+a; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=img4W13Z; arc=none smtp.client-ip=103.168.172.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="ZQXc9H+a"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="img4W13Z" Received: from phl-compute-04.internal (phl-compute-04.phl.internal [10.202.2.44]) by mailfout.phl.internal (Postfix) with ESMTP id 9D33B138032F; Wed, 4 Sep 2024 04:53:06 -0400 (EDT) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-04.internal (MEProxy); Wed, 04 Sep 2024 04:53:06 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm1; t=1725439986; x=1725526386; bh=9brIQmhJS5 veVHX7IJogk8m1bXErIl7FRTEcDeb63OU=; b=ZQXc9H+a8f8KtKkqLD5Qq6HzPu mXATMWpgBUdpTs05l+ZREnrYzdqmErI+nwXJB1BYWLOvd2PnC2nTPFyYIeguL7cw YIK4Rt3gRk4FDnwTnRzIaRN4VPNZtzbJX6mCzcZF729/o3QTOW5hbrna3ne/CSba S01Up72XNQJ5mEFZRbGKeTmD3OH1hpEHuCCdJQuEGNJje1v6v2JhOyolA5nsr+SM LYayb6s7o2EBJ/8i16tc99V7ivcG30+6FxGNkOJDr1tRFnn3NVHRND3OhcFgAymn 5IftigfQgL3PL/ZEJ4PM2j9QksOmjq4/ThVLxAwVTPHM5gmdKcrcFd7yga5g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm1; t=1725439986; x=1725526386; bh=9brIQmhJS5veVHX7IJogk8m1bXEr Il7FRTEcDeb63OU=; b=img4W13Zsa1YMmGAIkE6uuu48K+WmBIC3KNAMElWzcJt pNiQwnrxJ3cCZyaE/Zhbb3J7ILIt2cAauGfXpzCU83t5LLsbfuf7Ny7gMVVgNF5R lyg1QCbW9t6zmVvr3EBP291VRt1YDTHLCORNPJzO7YQAS8MkELIO/VYhXQg/mSkl zkrrcG0vq4eiZi8CJi2g8Z5vFmDTchJ3FYDPR3Fb3lXsbLI+IiiBXn7M2frt4xgv O0OMcCHre4SR73KbRj68PIStXmwMtcEC832pRlCRhqqlke9NQhvsPE7Vm7VFSkKS b7++38AnvcBDDM2YTZbbSUJDxt3SiKy3Zn0eBEvrwg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudehjedgtdelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhepfffhvfevuffkfhggtggujgesthdtredttddtvden ucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrdhimh eqnecuggftrfgrthhtvghrnhepveekkeffhfeitdeludeigfejtdetvdelvdduhefgueeg udfghfeukefhjedvkedtnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrg hilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepfedpmhhouggvpehs mhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomh dprhgtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohep ghhithhsthgvrhesphhosghogidrtghomh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Wed, 4 Sep 2024 04:53:05 -0400 (EDT) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 69d8a7fd (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Wed, 4 Sep 2024 08:52:56 +0000 (UTC) Date: Wed, 4 Sep 2024 10:53:03 +0200 From: Patrick Steinhardt To: git@vger.kernel.org Cc: karthik nayak , Junio C Hamano Subject: [PATCH v2 2/3] t0601: merge tests for auto-packing of refs Message-ID: <4a59cec205df7c09bc23a1f2609e728f2df5cef8.1725439407.git.ps@pks.im> 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: We have two tests in t0601 which exercise the same underlying logic, once via `git pack-refs --auto` and once via `git maintenance run --auto`. Merge these two tests into one such that it becomes easier to extend test coverage for both commands at the same time. Signed-off-by: Patrick Steinhardt --- t/t0601-reffiles-pack-refs.sh | 36 +++++++++++++++++++---------------- 1 file changed, 20 insertions(+), 16 deletions(-) diff --git a/t/t0601-reffiles-pack-refs.sh b/t/t0601-reffiles-pack-refs.sh index 60a544b8ee8..ed9652bb829 100755 --- a/t/t0601-reffiles-pack-refs.sh +++ b/t/t0601-reffiles-pack-refs.sh @@ -161,13 +161,6 @@ test_expect_success 'test --exclude takes precedence over --include' ' git pack-refs --include "refs/heads/pack*" --exclude "refs/heads/pack*" && test -f .git/refs/heads/dont_pack5' -test_expect_success '--auto packs and prunes refs as usual' ' - git branch auto && - test_path_is_file .git/refs/heads/auto && - git pack-refs --auto --all && - test_path_is_missing .git/refs/heads/auto -' - test_expect_success 'see if up-to-date packed refs are preserved' ' git branch q && git pack-refs --all --prune && @@ -367,14 +360,25 @@ test_expect_success 'pack-refs does not drop broken refs during deletion' ' test_cmp expect actual ' -test_expect_success 'maintenance --auto unconditionally packs loose refs' ' - git update-ref refs/heads/something HEAD && - test_path_is_file .git/refs/heads/something && - git rev-parse refs/heads/something >expect && - git maintenance run --task=pack-refs --auto && - test_path_is_missing .git/refs/heads/something && - git rev-parse refs/heads/something >actual && - test_cmp expect actual -' +for command in "git pack-refs --all --auto" "git maintenance run --task=pack-refs --auto" +do + test_expect_success "$command unconditionally packs loose refs" ' + test_when_finished "rm -rf repo" && + git init repo && + ( + cd repo && + git config set maintenance.auto false && + test_commit initial && + + git update-ref refs/heads/something HEAD && + test_path_is_file .git/refs/heads/something && + git rev-parse refs/heads/something >expect && + $command && + test_path_is_missing .git/refs/heads/something && + git rev-parse refs/heads/something >actual && + test_cmp expect actual + ) + ' +done test_done From patchwork Wed Sep 4 08:53:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13790128 Received: from fhigh6-smtp.messagingengine.com (fhigh6-smtp.messagingengine.com [103.168.172.157]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 91C011917DF for ; Wed, 4 Sep 2024 08:53:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.157 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725439993; cv=none; b=b/Svb7++7gotHgRgocaZVmMoEsQ0Xy3hMWALsHzgqbuB76JxV93fZzNw1qO1KwImvbIUCzEGcXFZ+mcOtq2elfYNsvxPl2HjjbxIDXMNBqH9JhfYzGzzXGlOkfQgyej14YIE+cl/lJ45pNWwMtVw5ahTh23he82MeNejmCE2cm0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725439993; c=relaxed/simple; bh=NBPR95cniluZlC/PT2+sYuUuyUmACe4HP12keYJZNVU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=uLsQ3v5qJHrzNYHO9aju5oYKTwGthghfS3hBif1EEu3w0lSKkU9DAWWfG4Y88VabZJRLpVSL6kViiVrrB33hpJ2t+eopw8VFHg2g15Pu10O4Mcy5uT8IadKmBSID24d1d8VvWRkGhSA+o0t6jB50JscFxxVcqo7A5B1JsUvjPTk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=U4sO0XkB; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=qqZh5Tqp; arc=none smtp.client-ip=103.168.172.157 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="U4sO0XkB"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="qqZh5Tqp" Received: from phl-compute-01.internal (phl-compute-01.phl.internal [10.202.2.41]) by mailfhigh.phl.internal (Postfix) with ESMTP id AF5B61140232; Wed, 4 Sep 2024 04:53:10 -0400 (EDT) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-01.internal (MEProxy); Wed, 04 Sep 2024 04:53:10 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm1; t=1725439990; x=1725526390; bh=fhrK0iElhb NwhCCSzf99bdeOm0F5kpsnSgt8PjnLY2U=; b=U4sO0XkBCuuXsPy3q0BcxfFnOU mFOajIFE8noS5iQKBDlQBWvu7aG+0yIF1C48UiCEGEvs4lbJruGP5FmdySwFBzK/ grtHNZ55ABHSnSyonkgm121Lnmz2Hleud5gsKmWNjv4PhOY5Wm7xrJh9NRXde7SJ W0v9XKCus/BvfYuA4Qr57CtxxtExZERq6G8T0dNyZpmaXZIRzke0BqB9ev7veLYR Rw94/obpL9LEMcw4U3ltDNgHMZj8LDMeEnptX7bHNoQJf/7BBlnTRzkfANdr+1JT 4rBx2jMQoOgNhiSHj0jyCFz9fROgw00jq1F0R3qcfKB/zLVARhr+Glece8tg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm1; t=1725439990; x=1725526390; bh=fhrK0iElhbNwhCCSzf99bdeOm0F5 kpsnSgt8PjnLY2U=; b=qqZh5TqpoAbTMriHw6kduJm4iEzGFN4u73SyGXAAzEkz HB9daUO3pEcBxUfgnqAbE0W7gvv5y+o1Fm+L/ejAOKPDxCWc+5nVjP+NbGxSFsHZ MwEfr15/sdtm1WnjFReM+3n0Hh7HuSqUqa8L4WoSVR1+xM57i+WTSDwfJCTyjGyy QLeMjHTf1EIvDtcM5cAiTgjVXFKesgrIcmwn+0sNk6Fjfg264+0eHAf17zJ2ryu3 chXkWCDD5BJpiIymjJ4GrtCVw18sZIMJmSJRIA3tfoyfFhCURx30gP+ManXwpFwu RO42PWB0qWAVRBhY+M/WBJS6xQG/9KogMFrpmjYLsQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeftddrudehjedgtdelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnh htshculddquddttddmnecujfgurhepfffhvfevuffkfhggtggujgesthdtredttddtvden ucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrdhimh eqnecuggftrfgrthhtvghrnhepveekkeffhfeitdeludeigfejtdetvdelvdduhefgueeg udfghfeukefhjedvkedtnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrg hilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepfedpmhhouggvpehs mhhtphhouhhtpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprh gtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpthhtohepkhgrrhht hhhikhdrudekkeesghhmrghilhdrtghomh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Wed, 4 Sep 2024 04:53:09 -0400 (EDT) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 2e10de45 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Wed, 4 Sep 2024 08:53:00 +0000 (UTC) Date: Wed, 4 Sep 2024 10:53:08 +0200 From: Patrick Steinhardt To: git@vger.kernel.org Cc: karthik nayak , Junio C Hamano Subject: [PATCH v2 3/3] refs/files: use heuristic to decide whether to repack with `--auto` Message-ID: <49f953142b1b20a63102b87a1d96f5bc1f79da82.1725439407.git.ps@pks.im> 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 `--auto` flag for git-pack-refs(1) allows the ref backend to decide whether or not a repack is in order. This switch has been introduced mostly with the "reftable" backend in mind, which already knows to auto-compact its tables during normal operations. When the flag is set, then it will use the same auto-compaction mechanism and thus end up doing nothing in most cases. The "files" backend does not have any such heuristic yet and instead packs any loose references unconditionally. So we rewrite the complete "packed-refs" file even if there's only a single loose reference to be packed. Even worse, starting with 9f6714ab3e (builtin/gc: pack refs when using `git maintenance run --auto`, 2024-03-25), `git pack-refs --auto` is unconditionally executed via our auto maintenance, so we end up repacking references every single time auto maintenance kicks in. And while that commit already mentioned that the "files" backend unconditionally packs refs now, the author obviously didn't quite think about the consequences thereof. So while the idea was sound, we really should have added a heuristic to the "files" backend before implementing it. Introduce a heuristic that decides whether or not it is worth to pack loose references. The important factors to decide here are the number of loose references in comparison to the overall size of the "packed-refs" file. The bigger the "packed-refs" file, the longer it takes to rewrite it and thus we scale up the limit of allowed loose references before we repack. As is the nature of heuristics, this mechansim isn't obviously "correct", but should rather be seen as a tradeoff between how much resources we spend packing refs and how inefficient the ref store becomes. For all I can say, we have successfully been using the exact same heuristic in Gitaly for several years by now. Signed-off-by: Patrick Steinhardt --- refs/files-backend.c | 65 +++++++++++++++++++++++++++ refs/packed-backend.c | 18 ++++++++ refs/packed-backend.h | 7 +++ t/t0601-reffiles-pack-refs.sh | 85 ++++++++++++++++++++++++++++++----- 4 files changed, 165 insertions(+), 10 deletions(-) diff --git a/refs/files-backend.c b/refs/files-backend.c index 1cff65f6ae5..51bcd16f821 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -1311,6 +1311,68 @@ static int should_pack_ref(struct files_ref_store *refs, return 0; } +static int should_pack_refs(struct files_ref_store *refs, + struct pack_refs_opts *opts) +{ + struct ref_iterator *iter; + size_t packed_size; + size_t refcount = 0; + size_t limit; + int ret; + + if (!(opts->flags & PACK_REFS_AUTO)) + return 1; + + ret = packed_refs_size(refs->packed_ref_store, &packed_size); + if (ret < 0) + die("cannot determine packed-refs size"); + + /* + * Packing loose references into the packed-refs file scales with the + * number of references we're about to write. We thus decide whether we + * repack refs by weighing the current size of the packed-refs file + * against the number of loose references. This is done such that we do + * not repack too often on repositories with a huge number of + * references, where we can expect a lot of churn in the number of + * references. + * + * As a heuristic, we repack if the number of loose references in the + * repository exceeds `log2(nr_packed_refs) * 5`, where we estimate + * `nr_packed_refs = packed_size / 100`, which scales as following: + * + * - 1kB ~ 10 packed refs: 16 refs + * - 10kB ~ 100 packed refs: 33 refs + * - 100kB ~ 1k packed refs: 49 refs + * - 1MB ~ 10k packed refs: 66 refs + * - 10MB ~ 100k packed refs: 82 refs + * - 100MB ~ 1m packed refs: 99 refs + * + * We thus allow roughly 16 additional loose refs per factor of ten of + * packed refs. This heuristic may be tweaked in the future, but should + * serve as a sufficiently good first iteration. + */ + limit = log2u(packed_size / 100) * 5; + if (limit < 16) + limit = 16; + + iter = cache_ref_iterator_begin(get_loose_ref_cache(refs, 0), NULL, + refs->base.repo, 0); + while ((ret = ref_iterator_advance(iter)) == ITER_OK) { + if (should_pack_ref(refs, iter->refname, iter->oid, + iter->flags, opts)) + refcount++; + if (refcount >= limit) { + ref_iterator_abort(iter); + return 1; + } + } + + if (ret != ITER_DONE) + die("error while iterating over references"); + + return 0; +} + static int files_pack_refs(struct ref_store *ref_store, struct pack_refs_opts *opts) { @@ -1323,6 +1385,9 @@ static int files_pack_refs(struct ref_store *ref_store, struct strbuf err = STRBUF_INIT; struct ref_transaction *transaction; + if (!should_pack_refs(refs, opts)) + return 0; + transaction = ref_store_transaction_begin(refs->packed_ref_store, &err); if (!transaction) return -1; diff --git a/refs/packed-backend.c b/refs/packed-backend.c index 7a0a695ca2f..07c57fd541a 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -1250,6 +1250,24 @@ int packed_refs_is_locked(struct ref_store *ref_store) return is_lock_file_locked(&refs->lock); } +int packed_refs_size(struct ref_store *ref_store, + size_t *out) +{ + struct packed_ref_store *refs = packed_downcast(ref_store, REF_STORE_READ, + "packed_refs_size"); + struct stat st; + + if (stat(refs->path, &st) < 0) { + if (errno != ENOENT) + return -1; + *out = 0; + return 0; + } + + *out = st.st_size; + return 0; +} + /* * The packed-refs header line that we write out. Perhaps other traits * will be added later. diff --git a/refs/packed-backend.h b/refs/packed-backend.h index 09437ad13bd..9481d5e7c2e 100644 --- a/refs/packed-backend.h +++ b/refs/packed-backend.h @@ -27,6 +27,13 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err) void packed_refs_unlock(struct ref_store *ref_store); int packed_refs_is_locked(struct ref_store *ref_store); +/* + * Obtain the size of the `packed-refs` file. Reports `0` as size in case there + * is no packed-refs file. Returns 0 on success, negative otherwise. + */ +int packed_refs_size(struct ref_store *ref_store, + size_t *out); + /* * Return true if `transaction` really needs to be carried out against * the specified packed_ref_store, or false if it can be skipped diff --git a/t/t0601-reffiles-pack-refs.sh b/t/t0601-reffiles-pack-refs.sh index ed9652bb829..d8cbd3f202b 100755 --- a/t/t0601-reffiles-pack-refs.sh +++ b/t/t0601-reffiles-pack-refs.sh @@ -362,21 +362,86 @@ test_expect_success 'pack-refs does not drop broken refs during deletion' ' for command in "git pack-refs --all --auto" "git maintenance run --task=pack-refs --auto" do - test_expect_success "$command unconditionally packs loose refs" ' + test_expect_success "$command does not repack below 16 refs without packed-refs" ' test_when_finished "rm -rf repo" && git init repo && ( cd repo && git config set maintenance.auto false && - test_commit initial && - - git update-ref refs/heads/something HEAD && - test_path_is_file .git/refs/heads/something && - git rev-parse refs/heads/something >expect && - $command && - test_path_is_missing .git/refs/heads/something && - git rev-parse refs/heads/something >actual && - test_cmp expect actual + git commit --allow-empty --message "initial" && + + # Create 14 additional references, which brings us to + # 15 together with the default branch. + printf "create refs/heads/loose-%d HEAD\n" $(test_seq 14) >stdin && + git update-ref --stdin stdin && + git update-ref --stdin stdin && + git update-ref --stdin stdin && + git update-ref --stdin stdin && + git update-ref --stdin