From patchwork Thu Mar 6 15:08:32 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004652 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 8CB2518EFDE for ; Thu, 6 Mar 2025 15:08:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273727; cv=none; b=O8mudzFDXoyvw4+nJijTxHM6NVb39nT9g3iaVh5jY1mNtZ4NUA12KbUbXWl0k1wnQiOXD+9K0apN0sJ9IMnaLrp1ZdLpSr6r/moZatkq7zKrJeKfIu1ihxlf5FnPVcGxL3oYdfdZ6bRtxrGRXTpvbvbycW7Eqyd/MbYNerR6Wws= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273727; c=relaxed/simple; bh=5adQ0qQct2pehqMypYo1bjERL/f3sDcV8S82/y6nHcE=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=OGALKYkbHkOm0mw94wNJNi3lVgtmOP9zJykA0OyepiphuoFSqLGgjhnDuzOuaW9YxfVKAfI7pvwwLONORdKsLEa1iqCW2ZU44z7aAUKgYCKqt2xJaGHob57apa97c1YR+JBTF8NiH6tPPvgV4XDfoXqvW6F6RZFGqdmoIya6N34= 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=QYrGd3i0; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=SXXmZ2F1; arc=none smtp.client-ip=202.12.124.147 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="QYrGd3i0"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="SXXmZ2F1" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfout.stl.internal (Postfix) with ESMTP id 6ED3C11400C9; Thu, 6 Mar 2025 10:08:44 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-02.internal (MEProxy); Thu, 06 Mar 2025 10:08:44 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273724; x=1741360124; bh=jzPMSpng1BPHpC2pMuJy197lByckBPxGahRwFokrSCY=; b= QYrGd3i0zqMkYALkopv8YCpFggzw33e5vjVC/rD6iJcpjtorYcVVce1zYt+wHhHR kLOFiaW767Q/fv88efTiseHD8bET1dyCkUk4OCU5i+2IyXj6XDRQVwx9a2qA3gqM NrIvETAwUgw+lGYYR160eOvPQLTgbZp/YjGaMzds5lUoceHwOcDTuf6eQ5OnD00t T/wJh6pnGZhCAKyluCkrJXbdKcJNeBD/2LTChGX1qsUTuHRzswCErzJjISAt342k GaO6qOPUcV8ghokJemNbW5RUYUnNXYgtl9pfrfO2moaZQV5HRs9aLyvpJ9twKnA3 nJUrzwy+Nk/bHnuBHONbPw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273724; x= 1741360124; bh=jzPMSpng1BPHpC2pMuJy197lByckBPxGahRwFokrSCY=; b=S XXmZ2F1WxAQdpYJXsIiznCmEMGKlPW+6CijILQXhFBiWeVmZKNTaGs7DmkOpSzmv AIls/nuZQgmJ69SIgVsAZ6+DIU4aejEWgav52K+NsiArGz10DFb7R9I/u8Wii3qh C0O950d5n74hps5FsFP3XdLZvEInXVpxBQGdh1pFJizWp4wLWZleXr+bDSijBzg9 VqdP8hNCGeIIfNaD0cPsHJXoaScbUbqk14lTtxG40pP79aJ6yhFeNKH+YH7jVboF qC1LaPV5QJpzKZVb971IQV+bJCV2Jrivp37bmlxOkiCT8kVAgjHfaUBf6Kex+ExM cjHsDC92BU0B3B7tIkRpg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpd hrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtthho pegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrdhorhhgpdhrtghpthhtohepghhith esvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthhopehpvghffhesphgvfhhfrdhn vghtpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghsthgvrd hnvghtpdhrtghpthhtohepshhhvghjihgrlhhuohesghhmrghilhdrtghomh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:42 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id bcb13bde (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:40 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:32 +0100 Subject: [PATCH v5 01/16] object-name: introduce `repo_get_oid_with_flags()` Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-1-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Introduce a new function `repo_get_oid_with_flags()`. This function behaves the same as `repo_get_oid()`, except that it takes an extra `flags` parameter that it ends up passing to `get_oid_with_context()`. This function will be used in a subsequent commit. Signed-off-by: Patrick Steinhardt --- object-name.c | 14 ++++++++------ object-name.h | 6 ++++++ 2 files changed, 14 insertions(+), 6 deletions(-) diff --git a/object-name.c b/object-name.c index 945d5bdef25..233f3f861e3 100644 --- a/object-name.c +++ b/object-name.c @@ -1794,18 +1794,20 @@ void object_context_release(struct object_context *ctx) strbuf_release(&ctx->symlink_path); } -/* - * This is like "get_oid_basic()", except it allows "object ID expressions", - * notably "xyz^" for "parent of xyz" - */ -int repo_get_oid(struct repository *r, const char *name, struct object_id *oid) +int repo_get_oid_with_flags(struct repository *r, const char *name, + struct object_id *oid, unsigned flags) { struct object_context unused; - int ret = get_oid_with_context(r, name, 0, oid, &unused); + int ret = get_oid_with_context(r, name, flags, oid, &unused); object_context_release(&unused); return ret; } +int repo_get_oid(struct repository *r, const char *name, struct object_id *oid) +{ + return repo_get_oid_with_flags(r, name, oid, 0); +} + /* * This returns a non-zero value if the string (built using printf * format and the given arguments) is not a valid object. diff --git a/object-name.h b/object-name.h index 8dba4a47a47..cda4934cd5f 100644 --- a/object-name.h +++ b/object-name.h @@ -51,6 +51,12 @@ void strbuf_repo_add_unique_abbrev(struct strbuf *sb, struct repository *repo, void strbuf_add_unique_abbrev(struct strbuf *sb, const struct object_id *oid, int abbrev_len); +/* + * This is like "get_oid_basic()", except it allows "object ID expressions", + * notably "xyz^" for "parent of xyz". Accepts GET_OID_* flags. + */ +int repo_get_oid_with_flags(struct repository *r, const char *str, + struct object_id *oid, unsigned flags); int repo_get_oid(struct repository *r, const char *str, struct object_id *oid); __attribute__((format (printf, 2, 3))) int get_oidf(struct object_id *oid, const char *fmt, ...); From patchwork Thu Mar 6 15:08:33 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004653 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 04C3C20897F for ; Thu, 6 Mar 2025 15:08:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273727; cv=none; b=hbjGdLG+h6ID8IkSNjZuXiKcffXtdFVrfAe2agFRnPLMD7seqWIxOLq8WQkiBSZWJYOIvS6pdGIzlam8LKqbX9XjtqhKO6cxgCbLGGkrkm1B1sVjde15XuHgtK2zF6pkScEu8g15RkuRcHdaYaWwmuvaBynTmei1PABsYWHKd8U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273727; c=relaxed/simple; bh=LTZ901PIO4nZtZkOQxDbRW6bFFdhVn1Wkbh7cfYizCE=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=jNLpaHU0usuWpGDj23eUobgrIyqs2h49mwq39VXuyAmCc5Xs2lD7F8dN/nvAy2vXrV8mh2vlIWLLoLbpi4U0VpAXtA6FfzdMHo5S395BeEyeOQQNFSnUuZt1yweZJwSuRwLq0fg485nRvBi08nGSIY7MtogzvJHRjs2uUSLc4tA= 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=T82B+qpH; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=MhZlgIrQ; arc=none smtp.client-ip=202.12.124.147 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="T82B+qpH"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="MhZlgIrQ" Received: from phl-compute-04.internal (phl-compute-04.phl.internal [10.202.2.44]) by mailfout.stl.internal (Postfix) with ESMTP id EAAB311401DB; Thu, 6 Mar 2025 10:08:44 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-04.internal (MEProxy); Thu, 06 Mar 2025 10:08:45 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273724; x=1741360124; bh=Re/jjcNAK68m1c0Cf3VEwVaT/V2heXqHXg++4K2b/PY=; b= T82B+qpHj2CML1H8pLLxXEzoeIq8jXcbFdwz5UeD8oeZmPpiyrS7Do+0+d1pjmhm GkgZEvANXhEE8Wbv/BV1ZVsUm7GIClLkj7sfBTN2hgJVNqWDbOiEWHdLZ3uoJtWv w0KwWrHPA+cV03+kzA8o4D1b6EwkjORfGotBK2QnyfNDqxprWATnNbGMLAdZWsTS 85MzXtSRWCM+i/o6EIhPN8V9Fv39lQWOSJA3B3d2zovT/TU8sI1xshBYrcmkDt4n q4zmFwS1ICHzrT57SeyTSEfWjbECk9Ty7/8AHWN3F4TXOk2jwnMxz2tIIyZ8d4XL pMGcHRgX7aVaGQUCDDwVkw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273724; x= 1741360124; bh=Re/jjcNAK68m1c0Cf3VEwVaT/V2heXqHXg++4K2b/PY=; b=M hZlgIrQC2DKeBvCzAmn8+J6K9pwgz6oxdCvkK0yJgXaeY305ECzrUSQyQo5T+QI8 oMPfXxguciDeAVRjJQEW7t/JUOZubL0zCjYtQ8wWxdVnIRr0TygkUFBZ+6iVk0Bw IxbTn5MB4tkr9gd0X+eV4DfZz2PorvmhjUjACC6hjiv9CvjKiCpbg74Qyp/HNqkk 4I0pRTZJ9itNTS/+K08vPxDyMf4Q7X0BUc1qekeRe6i97iYy6W01VRmIJ63o2of5 T8tS3BYeEWqt7d7LOqL8pmHqnXVcSyxCmulx7Mlw9gxc4Ya16k9W7gnBd/WyIGYh nDKqwFqVFQ1cIlQxafBFg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdelucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpd hrtghpthhtohepshhhvghjihgrlhhuohesghhmrghilhdrtghomhdprhgtphhtthhopehk rghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohepshgrnhgurghlsh estghruhhsthihthhoohhthhhprghsthgvrdhnvghtpdhrtghpthhtohepphgvfhhfsehp vghffhdrnhgvthdprhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrd horhhgpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:43 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 21ec19f7 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:41 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:33 +0100 Subject: [PATCH v5 02/16] object-name: allow skipping ambiguity checks in `get_oid()` family Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-2-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 When reading an object ID via `get_oid_basic()` or any of its related functions we perform a check whether the object ID is ambiguous, which can be the case when a reference with the same name exists. While the check is generally helpful, there are cases where it only adds to the runtime overhead without providing much of a benefit. Add a new flag that allows us to disable the check. The flag will be used in a subsequent commit. Signed-off-by: Patrick Steinhardt --- hash.h | 23 ++++++++++++----------- object-name.c | 4 +++- 2 files changed, 15 insertions(+), 12 deletions(-) diff --git a/hash.h b/hash.h index 4367acfec50..5e3c462dc5e 100644 --- a/hash.h +++ b/hash.h @@ -193,17 +193,18 @@ struct object_id { int algo; /* XXX requires 4-byte alignment */ }; -#define GET_OID_QUIETLY 01 -#define GET_OID_COMMIT 02 -#define GET_OID_COMMITTISH 04 -#define GET_OID_TREE 010 -#define GET_OID_TREEISH 020 -#define GET_OID_BLOB 040 -#define GET_OID_FOLLOW_SYMLINKS 0100 -#define GET_OID_RECORD_PATH 0200 -#define GET_OID_ONLY_TO_DIE 04000 -#define GET_OID_REQUIRE_PATH 010000 -#define GET_OID_HASH_ANY 020000 +#define GET_OID_QUIETLY 01 +#define GET_OID_COMMIT 02 +#define GET_OID_COMMITTISH 04 +#define GET_OID_TREE 010 +#define GET_OID_TREEISH 020 +#define GET_OID_BLOB 040 +#define GET_OID_FOLLOW_SYMLINKS 0100 +#define GET_OID_RECORD_PATH 0200 +#define GET_OID_ONLY_TO_DIE 04000 +#define GET_OID_REQUIRE_PATH 010000 +#define GET_OID_HASH_ANY 020000 +#define GET_OID_SKIP_AMBIGUITY_CHECK 040000 #define GET_OID_DISAMBIGUATORS \ (GET_OID_COMMIT | GET_OID_COMMITTISH | \ diff --git a/object-name.c b/object-name.c index 233f3f861e3..85444dbb15b 100644 --- a/object-name.c +++ b/object-name.c @@ -961,7 +961,9 @@ static int get_oid_basic(struct repository *r, const char *str, int len, int fatal = !(flags & GET_OID_QUIETLY); if (len == r->hash_algo->hexsz && !get_oid_hex(str, oid)) { - if (repo_settings_get_warn_ambiguous_refs(r) && warn_on_object_refname_ambiguity) { + if (!(flags & GET_OID_SKIP_AMBIGUITY_CHECK) && + repo_settings_get_warn_ambiguous_refs(r) && + warn_on_object_refname_ambiguity) { refs_found = repo_dwim_ref(r, str, len, &tmp_oid, &real_ref, 0); if (refs_found > 0) { warning(warn_msg, len, str); From patchwork Thu Mar 6 15:08:34 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004654 Received: from fhigh-b5-smtp.messagingengine.com (fhigh-b5-smtp.messagingengine.com [202.12.124.156]) (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 7B62720D4EB for ; Thu, 6 Mar 2025 15:08:47 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.156 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273729; cv=none; b=cqY0t56r9yeUxmGylacrw5mkU2RJ6Lt+LnoWOO8U1n3ZdqSFfV2D13m40MQdy46EFcsuMG+0hwmi8sdPRB59U45m8Rt+XEsil0U2BboRduOzU037rTwXTPFIzTpF+mXhmKmm1MxjDDqsFXbHV+MHV3uXjpxUITsV+73HOISQdJ0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273729; c=relaxed/simple; bh=Bj59QpE5CmuY8gGaz9xpAji0XBAG/hRpO5VBer7nPgY=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=mPGdoAu66UYdW3c2f4brdNIMUQJrxtqYs4TUMEVLHzNAgn/FxkwBRp6vv5VA8rqSE6cB+s2cb4lzvm8iJG4ElDTc2WmXgatS40XvcflCK4SNGwbTPdiC03Gb4dWcUcUFXUwJP80Y77WdUqGIy1ugTmMTOQqF4waHPAB/H47FDT8= 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=cDVJwi2Y; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=EF5Scycz; arc=none smtp.client-ip=202.12.124.156 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="cDVJwi2Y"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="EF5Scycz" Received: from phl-compute-01.internal (phl-compute-01.phl.internal [10.202.2.41]) by mailfhigh.stl.internal (Postfix) with ESMTP id 71181254016F; Thu, 6 Mar 2025 10:08:46 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-01.internal (MEProxy); Thu, 06 Mar 2025 10:08:46 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273726; x=1741360126; bh=3GFK0R+2Yi1vt7crwjEysdxfkATZiwA48VLZos2UG2U=; b= cDVJwi2YxrXaE8oVZWfXfrM4it9P5L58xqd3luupbhUECLruNLajJWb7nbIB9DDZ fq+WTfwpYHRcN4qC0Us5aOlCoXophrYTPsTChe7E3Yp3yFwdqfWxaz61C8LVlopB naNGYoq6bSMEvw2gtkfZGHJ+wTWM3grHbS3Rk4p7uCQbfT8IjsBHQecn/oF/ze+s k/zDMCAcXzD/QOZNsYPxiPjQx2sduo7SnvHETfAPJrhqXsvF3hVh20QiQ7nn6C+d VU6BJE5jPz59BrZAKDlwADY4vNQ/LaBJcrfMKFJmfTqXsMmYcIbZ+lWyMFQWNJxc BiP80sbg/98GC1eZJVS+rw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273726; x= 1741360126; bh=3GFK0R+2Yi1vt7crwjEysdxfkATZiwA48VLZos2UG2U=; b=E F5Scycz5KCDYAt5Lw6SHVzNDx5BZ+ta42yyZO865ItpbdlkeIpuRZSaprPYOPKri Q5UJeDhQHeFahXSzxKBXp5MqL0yHnsUeFDlGgRP9HMFsKWnyj48Y8t/1z7zJUplF rOdP0+SxQrXx/KbNsznPgV0s+ZzEKTDgKn9iSsy4FceriDAwmijPyr5nXcwOhrTb qMN7rq3bw62ALwkQk5BONqzducL/C9x56OMdWmGdcoQS1mGpIeg2ryF75BKFJKD+ aY8ddnPgd9wCWPLuPeF6dlNRM0ykPnlKJ3U8rGzBeq9Dbx2rQmDomDJnHmMPwOQ/ x4xK1AKfsvGWJNKxWwm3A== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtkeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeefhfeugeelheefjeektdffhedvhfdvteefgfdt udffudevveetgeeuuedtkefhgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehshhgvjhhirghluhhosehgmhgrihhlrdgtoh hmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthho pehpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesgh hmrghilhdrtghomhdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhr tghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghsthgvrdhnvghtpd hrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:44 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 696cd2fe (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:41 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:34 +0100 Subject: [PATCH v5 03/16] builtin/update-ref: skip ambiguity checks when parsing object IDs Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-3-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Most of the commands in git-update-ref(1) accept an old and/or new object ID to update a specific reference to. These object IDs get parsed via `repo_get_oid()`, which not only handles plain object IDs, but also those that have a suffix like "~" or "^2". More surprisingly though, it even knows to resolve arbitrary revisions, despite the fact that its manpage does not mention this fact even once. One consequence of this is that we also check for ambiguous references: when parsing a full object ID where the DWIM mechanism would also cause us to resolve it as a branch, we'd end up printing a warning. While this check makes sense to have in general, it is arguably less useful in the context of git-update-ref(1). This is due to multiple reasons: - The manpage is explicitly structured around object IDs. So if we see a fully blown object ID, the intent should be quite clear in general. - The command is part of our plumbing layer and not a tool that users would generally use in interactive workflows. As such, the warning will likely not be visible to anybody in the first place. - Users can and should use the fully-qualified refname in case there is any potential for ambiguity. And given that this command is part of our plumbing layer, one should always try to be as defensive as possible and use fully-qualified refnames. Furthermore, this check can be quite expensive when updating lots of references via `--stdin`, because we try to read multiple references per object ID that we parse according to the DWIM rules. This effect can be seen both with the "files" and "reftable" backend. The issue is not unique to git-update-ref(1), but was also an issue in git-cat-file(1), where it was addressed by disabling the ambiguity check in 25fba78d36b (cat-file: disable object/refname ambiguity check for batch mode, 2013-07-12). Disable the warning in git-update-ref(1), which provides a significant speedup with both backends. The user-visible outcome is unchanged even when ambiguity exists, except that we don't show the warning anymore. The following benchmark creates 10000 new references with a 100000 preexisting refs with the "files" backend: Benchmark 1: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD~) Time (mean ± σ): 467.3 ms ± 5.1 ms [User: 100.0 ms, System: 365.1 ms] Range (min … max): 461.9 ms … 479.3 ms 10 runs Benchmark 2: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) Time (mean ± σ): 394.1 ms ± 5.8 ms [User: 63.3 ms, System: 327.6 ms] Range (min … max): 384.9 ms … 405.7 ms 10 runs Summary update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) ran 1.19 ± 0.02 times faster than update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD~) And with the "reftable" backend: Benchmark 1: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~) Time (mean ± σ): 146.9 ms ± 2.2 ms [User: 90.4 ms, System: 56.0 ms] Range (min … max): 142.7 ms … 150.8 ms 19 runs Benchmark 2: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) Time (mean ± σ): 63.2 ms ± 1.1 ms [User: 41.0 ms, System: 21.8 ms] Range (min … max): 61.1 ms … 66.6 ms 41 runs Summary update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) ran 2.32 ± 0.05 times faster than update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~) Note that the absolute improvement with both backends is roughly in the same ballpark, but the relative improvement for the "reftable" backend is more significant because writing the new table to disk is faster in the first place. Signed-off-by: Patrick Steinhardt --- builtin/update-ref.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) diff --git a/builtin/update-ref.c b/builtin/update-ref.c index 4d35bdc4b4b..1d541e13ade 100644 --- a/builtin/update-ref.c +++ b/builtin/update-ref.c @@ -179,7 +179,8 @@ static int parse_next_oid(const char **next, const char *end, (*next)++; *next = parse_arg(*next, &arg); if (arg.len) { - if (repo_get_oid(the_repository, arg.buf, oid)) + if (repo_get_oid_with_flags(the_repository, arg.buf, oid, + GET_OID_SKIP_AMBIGUITY_CHECK)) goto invalid; } else { /* Without -z, an empty value means all zeros: */ @@ -197,7 +198,8 @@ static int parse_next_oid(const char **next, const char *end, *next += arg.len; if (arg.len) { - if (repo_get_oid(the_repository, arg.buf, oid)) + if (repo_get_oid_with_flags(the_repository, arg.buf, oid, + GET_OID_SKIP_AMBIGUITY_CHECK)) goto invalid; } else if (flags & PARSE_SHA1_ALLOW_EMPTY) { /* With -z, treat an empty value as all zeros: */ @@ -299,7 +301,8 @@ static void parse_cmd_symref_update(struct ref_transaction *transaction, die("symref-update %s: expected old value", refname); if (!strcmp(old_arg, "oid")) { - if (repo_get_oid(the_repository, old_target, &old_oid)) + if (repo_get_oid_with_flags(the_repository, old_target, &old_oid, + GET_OID_SKIP_AMBIGUITY_CHECK)) die("symref-update %s: invalid oid: %s", refname, old_target); have_old_oid = 1; @@ -772,7 +775,8 @@ int cmd_update_ref(int argc, refname = argv[0]; value = argv[1]; oldval = argv[2]; - if (repo_get_oid(the_repository, value, &oid)) + if (repo_get_oid_with_flags(the_repository, value, &oid, + GET_OID_SKIP_AMBIGUITY_CHECK)) die("%s: not a valid SHA1", value); } @@ -783,7 +787,8 @@ int cmd_update_ref(int argc, * must not already exist: */ oidclr(&oldoid, the_repository->hash_algo); - else if (repo_get_oid(the_repository, oldval, &oldoid)) + else if (repo_get_oid_with_flags(the_repository, oldval, &oldoid, + GET_OID_SKIP_AMBIGUITY_CHECK)) die("%s: not a valid old SHA1", oldval); } From patchwork Thu Mar 6 15:08:35 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004655 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 2ABE618C92F for ; Thu, 6 Mar 2025 15:08:47 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273729; cv=none; b=pWwhs0LFGkAbv4lBYvRcnApL66G3DpDsWIOBj4WkSHVjwsm0Q+LMFqJH4pHVmTEys7jWheMxoeThkuQmU9rMyBvrB7EoMr89v4xaZnq1TH0H5nh1LnfLn4D0VNBypkiykXcdQpJ/G6pzesWEosEIu/K73PXd0MEPRMEpTImchVU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273729; c=relaxed/simple; bh=sb3XjAxABCfF4cxMqn2HFJpx9Zi3qxhebaNSB7qO7N8=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=pZFjFga3UqpBkueU15W0PVpJTzV30o4LJcVhh/xiah9b0RUJgHNE76mZfEWCRBwAu+IQRHqx4bpwu0S3OaQT8PTW0yBARitxhOgD6PYL1huDpRfyFIt6mYsCQ4JQYLzRCgg8YJTVjDaJgGO1FZSIFfgaSVy2PLNsDRtFBS30ySk= 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=jNi1sGEQ; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=cRIZmSZh; arc=none smtp.client-ip=202.12.124.147 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="jNi1sGEQ"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="cRIZmSZh" Received: from phl-compute-09.internal (phl-compute-09.phl.internal [10.202.2.49]) by mailfout.stl.internal (Postfix) with ESMTP id 1B2DC1140159; Thu, 6 Mar 2025 10:08:47 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-09.internal (MEProxy); Thu, 06 Mar 2025 10:08:47 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273726; x=1741360126; bh=5L67u+lvaBbUnCLveZ5tFpci4yebngppu3PmualLKfM=; b= jNi1sGEQi2/bnF9x43zlEkdzgHEe6bg4LzJC2dT4cZNDetcYJkjB2G/1SQVU8A/5 ii4UMz8SJw4qyVm1ulGXm7Tr0wbJAWqHHC9lo3GN7zEP2fe90gNfaZ4hlD+s2g56 nDXlGv2GvH2T8YeZM590jtVmyvzQwjiThmmA+gJLCTnkGbXXWAMlegQ7U+bn/s+r GlADYaa3VGBvV/oPP+3b+0eLd3Yc84+XN0i5HlQVryuNsLLBzeSHpOKcywSNiy00 B9ae78wVN2g6YMk633rG/mrVCMdIhhZtH5xek/2V/qS3SyRWDb2Z6YgVHyGzvjRN fldw9MA9EFJtsjMKFwfhLQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273726; x= 1741360126; bh=5L67u+lvaBbUnCLveZ5tFpci4yebngppu3PmualLKfM=; b=c RIZmSZhczDWJMENA0lsi3RpHCi8mMF4RpNRoNx0QN0HcgK7Ov+NvgctLuc+H0y9E 6/wQqDyxXYa/i1MkhZ6I+wZgYFX9dhiCuSUraDEWz8/p/x4VYPXgoNnZwKfaBWns QZeLSPDwSUrBBwSuJGYAK4j0xnjdfVcE1124UDWwzFFvGPJRQzc6V5Yz5G0lbXE+ tC2fSKSjhDK1YY1W2mZKmgvzNJm8jqYYNtQrjbv8m2TueoygKu2ZvOY0e5UrRTMs vtZN1BZyXMF0V04OjFcqvmadhjOEWOyzvLECi3fI7JZXNkbDPs+srBgR1j46wo3T 7lOs6QG+NkZ7DAFl5iz4Q== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdelucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilh ihrdhorhhgpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghs thgvrdhnvghtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprhgtph htthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohepshhh vghjihgrlhhuohesghhmrghilhdrtghomhdprhgtphhtthhopehpvghffhesphgvfhhfrd hnvghtpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:45 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 9daacd11 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:42 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:35 +0100 Subject: [PATCH v5 04/16] refs: introduce function to batch refname availability checks Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-4-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 The `refs_verify_refname_available()` functions checks whether a reference update can be committed or whether it would conflict with either a prefix or suffix thereof. This function needs to be called once per reference that one wants to check, which requires us to redo a couple of checks every time the function is called. Introduce a new function `refs_verify_refnames_available()` that does the same, but for a list of references. For now, the new function uses the exact same implementation, except that we loop through all refnames provided by the caller. This will be tuned in subsequent commits. The existing `refs_verify_refname_available()` function is reimplemented on top of the new function. As such, the diff is best viewed with the `--ignore-space-change option`. Signed-off-by: Patrick Steinhardt --- refs.c | 169 +++++++++++++++++++++++++++++++++++++---------------------------- refs.h | 12 +++++ 2 files changed, 109 insertions(+), 72 deletions(-) diff --git a/refs.c b/refs.c index f4094a326a9..5a9b0f2fa1e 100644 --- a/refs.c +++ b/refs.c @@ -2467,19 +2467,15 @@ int ref_transaction_commit(struct ref_transaction *transaction, return ret; } -int refs_verify_refname_available(struct ref_store *refs, - const char *refname, - const struct string_list *extras, - const struct string_list *skip, - unsigned int initial_transaction, - struct strbuf *err) +int refs_verify_refnames_available(struct ref_store *refs, + const struct string_list *refnames, + const struct string_list *extras, + const struct string_list *skip, + unsigned int initial_transaction, + struct strbuf *err) { - const char *slash; - const char *extra_refname; struct strbuf dirname = STRBUF_INIT; struct strbuf referent = STRBUF_INIT; - struct object_id oid; - unsigned int type; int ret = -1; /* @@ -2489,79 +2485,91 @@ int refs_verify_refname_available(struct ref_store *refs, assert(err); - strbuf_grow(&dirname, strlen(refname) + 1); - for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) { - /* - * Just saying "Is a directory" when we e.g. can't - * lock some multi-level ref isn't very informative, - * the user won't be told *what* is a directory, so - * let's not use strerror() below. - */ - int ignore_errno; - /* Expand dirname to the new prefix, not including the trailing slash: */ - strbuf_add(&dirname, refname + dirname.len, slash - refname - dirname.len); + for (size_t i = 0; i < refnames->nr; i++) { + const char *refname = refnames->items[i].string; + const char *extra_refname; + struct object_id oid; + unsigned int type; + const char *slash; + + strbuf_reset(&dirname); + + for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) { + /* + * Just saying "Is a directory" when we e.g. can't + * lock some multi-level ref isn't very informative, + * the user won't be told *what* is a directory, so + * let's not use strerror() below. + */ + int ignore_errno; + + /* Expand dirname to the new prefix, not including the trailing slash: */ + strbuf_add(&dirname, refname + dirname.len, slash - refname - dirname.len); + + /* + * We are still at a leading dir of the refname (e.g., + * "refs/foo"; if there is a reference with that name, + * it is a conflict, *unless* it is in skip. + */ + if (skip && string_list_has_string(skip, dirname.buf)) + continue; + + if (!initial_transaction && + !refs_read_raw_ref(refs, dirname.buf, &oid, &referent, + &type, &ignore_errno)) { + strbuf_addf(err, _("'%s' exists; cannot create '%s'"), + dirname.buf, refname); + goto cleanup; + } + + if (extras && string_list_has_string(extras, dirname.buf)) { + strbuf_addf(err, _("cannot process '%s' and '%s' at the same time"), + refname, dirname.buf); + goto cleanup; + } + } /* - * We are still at a leading dir of the refname (e.g., - * "refs/foo"; if there is a reference with that name, - * it is a conflict, *unless* it is in skip. + * We are at the leaf of our refname (e.g., "refs/foo/bar"). + * There is no point in searching for a reference with that + * name, because a refname isn't considered to conflict with + * itself. But we still need to check for references whose + * names are in the "refs/foo/bar/" namespace, because they + * *do* conflict. */ - if (skip && string_list_has_string(skip, dirname.buf)) - continue; + strbuf_addstr(&dirname, refname + dirname.len); + strbuf_addch(&dirname, '/'); + + if (!initial_transaction) { + struct ref_iterator *iter; + int ok; + + iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, + DO_FOR_EACH_INCLUDE_BROKEN); + while ((ok = ref_iterator_advance(iter)) == ITER_OK) { + if (skip && + string_list_has_string(skip, iter->refname)) + continue; + + strbuf_addf(err, _("'%s' exists; cannot create '%s'"), + iter->refname, refname); + ref_iterator_abort(iter); + goto cleanup; + } - if (!initial_transaction && - !refs_read_raw_ref(refs, dirname.buf, &oid, &referent, - &type, &ignore_errno)) { - strbuf_addf(err, _("'%s' exists; cannot create '%s'"), - dirname.buf, refname); - goto cleanup; + if (ok != ITER_DONE) + BUG("error while iterating over references"); } - if (extras && string_list_has_string(extras, dirname.buf)) { + extra_refname = find_descendant_ref(dirname.buf, extras, skip); + if (extra_refname) { strbuf_addf(err, _("cannot process '%s' and '%s' at the same time"), - refname, dirname.buf); + refname, extra_refname); goto cleanup; } } - /* - * We are at the leaf of our refname (e.g., "refs/foo/bar"). - * There is no point in searching for a reference with that - * name, because a refname isn't considered to conflict with - * itself. But we still need to check for references whose - * names are in the "refs/foo/bar/" namespace, because they - * *do* conflict. - */ - strbuf_addstr(&dirname, refname + dirname.len); - strbuf_addch(&dirname, '/'); - - if (!initial_transaction) { - struct ref_iterator *iter; - int ok; - - iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, - DO_FOR_EACH_INCLUDE_BROKEN); - while ((ok = ref_iterator_advance(iter)) == ITER_OK) { - if (skip && - string_list_has_string(skip, iter->refname)) - continue; - - strbuf_addf(err, _("'%s' exists; cannot create '%s'"), - iter->refname, refname); - ref_iterator_abort(iter); - goto cleanup; - } - - if (ok != ITER_DONE) - BUG("error while iterating over references"); - } - - extra_refname = find_descendant_ref(dirname.buf, extras, skip); - if (extra_refname) - strbuf_addf(err, _("cannot process '%s' and '%s' at the same time"), - refname, extra_refname); - else - ret = 0; + ret = 0; cleanup: strbuf_release(&referent); @@ -2569,6 +2577,23 @@ int refs_verify_refname_available(struct ref_store *refs, return ret; } +int refs_verify_refname_available(struct ref_store *refs, + const char *refname, + const struct string_list *extras, + const struct string_list *skip, + unsigned int initial_transaction, + struct strbuf *err) +{ + struct string_list_item item = { .string = (char *) refname }; + struct string_list refnames = { + .items = &item, + .nr = 1, + }; + + return refs_verify_refnames_available(refs, &refnames, extras, skip, + initial_transaction, err); +} + struct do_for_each_reflog_help { each_reflog_fn *fn; void *cb_data; diff --git a/refs.h b/refs.h index a0cdd99250e..185aed5a461 100644 --- a/refs.h +++ b/refs.h @@ -124,6 +124,18 @@ int refs_verify_refname_available(struct ref_store *refs, unsigned int initial_transaction, struct strbuf *err); +/* + * Same as `refs_verify_refname_available()`, but checking for a list of + * refnames instead of only a single item. This is more efficient in the case + * where one needs to check multiple refnames. + */ +int refs_verify_refnames_available(struct ref_store *refs, + const struct string_list *refnames, + const struct string_list *extras, + const struct string_list *skip, + unsigned int initial_transaction, + struct strbuf *err); + int refs_ref_exists(struct ref_store *refs, const char *refname); int should_autocreate_reflog(enum log_refs_config log_all_ref_updates, From patchwork Thu Mar 6 15:08:36 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004656 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 7CB4F20897F for ; Thu, 6 Mar 2025 15:08:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273731; cv=none; b=WYKjOIkqTcnIzrcAgsmv0+qmgg++dC9jsQMyBf9vyN1YsXAmfBwKJ/4gZ6ov43tsITOK6yI7nLmG9trzVylyD0cbUy+jgeQ9a81hcYCnF8wERv4Le2ihAW3BKAq+5RaSPYnxs+Ljxwg+kaL+lhPizTeHi7jZMHMvN6iNll3uqPs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273731; c=relaxed/simple; bh=BF5wtmUe1XZEe3gRWoVlmpeBoEvugVXNMSCQKdPZZRE=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Cx+NHMv7H7Mqhyw7ofaotVv+edtaSZooBUTEz47FeAcYA0Gzp8sfzAASySVtmKYaGERLGZJBRYjBdHj4UEJVnXkT2pryBT4vVEsLJECnUbSVrX79m30TjkQH2IDhW4BVBGJul3X9n1BNJiVZaoh+GJzxhvtL7s4sm9WQFN9JQbM= 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=m5LeIkOn; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=09bABsk7; arc=none smtp.client-ip=202.12.124.147 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="m5LeIkOn"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="09bABsk7" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfout.stl.internal (Postfix) with ESMTP id 6AEF91140106; Thu, 6 Mar 2025 10:08:48 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-02.internal (MEProxy); Thu, 06 Mar 2025 10:08:48 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273728; x=1741360128; bh=Gkpk2yNagRtaVqgMY0LYBj2dB1FOlgSLKE27KW096RU=; b= m5LeIkOno1kjoSA6TlMdcfA0jBesRXotzNPaaw1tTIHr5tgU2sSNUQJ6rETbgewW D90UyA7Nt4VNaL4kNYBNASabh1v42FmRz7QbVy3ER3KrGS8KpVXu7yhVGfPja6gP aCQqA+pEMUnhzyxtqdR6grzhHPuBbUgGQuyr0Zk3yel5hADyAYPCY0CBCo/oE1gX mQsT0XtVnEYXeD8mzCnd1tbivD6+lZjdIPjpozm3unG0ErKp7XsYvSAqTFN/m+iV gOZkPNl+jPZWRBF2beNzvencSapDXZRhgAbdmeYmdeZdXUbqmVXh/xa6CqqU0Lkh hWuEag9K00A+ap6nnXo2Ag== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273728; x= 1741360128; bh=Gkpk2yNagRtaVqgMY0LYBj2dB1FOlgSLKE27KW096RU=; b=0 9bABsk7tQIYkBHwZf4rku0aqcj0rha3oba6kBuwcn2k9RPXkjTaJT/7a4ugiPc83 I5eusjR4OoX6m6wg9VYRQEhUF8x0X1CUF8xoIxprVu+gvHNBf34RGcc9NrPXUJjP vjLIROMOfBGwcH++fLbjvD1QCASacTgPpZ9A57I9vDf+UkMWONd/okxbJ0iyMORQ n6zPhWvG8jGGUpemCkX497/Nfzw7PkiEl6Ey0qJkvk0p0o0wsWkGStB7v2iqzP5z Y6BuDSayPlXQ/cbDe1UKykTrENx609ZoPupvLPqF1u0GlWSJaVYiYni2wwfy9Shs 2O6Bc8ddTRuNCc3mKrJjA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehsrghnuggrlhhssegtrhhushhthihtohhoth hhphgrshhtvgdrnhgvthdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhm pdhrtghpthhtohepshhhvghjihgrlhhuohesghhmrghilhdrtghomhdprhgtphhtthhope hkrghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohepphgvfhhfsehp vghffhdrnhgvthdprhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrd horhhgpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:46 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 0d90c211 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:43 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:36 +0100 Subject: [PATCH v5 05/16] refs/reftable: batch refname availability checks Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-5-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Refactor the "reftable" backend to batch the availability check for refnames. This does not yet have an effect on performance as `refs_verify_refnames_available()` effectively still performs the availability check for each refname individually. But this will be optimized in subsequent commits, where we learn to optimize some parts of the logic when checking multiple refnames for availability. Signed-off-by: Patrick Steinhardt --- refs/reftable-backend.c | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-) diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index d39a14c5a46..2a90e7cb391 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -1069,6 +1069,7 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, reftable_be_downcast(ref_store, REF_STORE_WRITE|REF_STORE_MAIN, "ref_transaction_prepare"); struct strbuf referent = STRBUF_INIT, head_referent = STRBUF_INIT; struct string_list affected_refnames = STRING_LIST_INIT_NODUP; + struct string_list refnames_to_check = STRING_LIST_INIT_NODUP; struct reftable_transaction_data *tx_data = NULL; struct reftable_backend *be; struct object_id head_oid; @@ -1224,12 +1225,7 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, * can output a proper error message instead of failing * at a later point. */ - ret = refs_verify_refname_available(ref_store, u->refname, - &affected_refnames, NULL, - transaction->flags & REF_TRANSACTION_FLAG_INITIAL, - err); - if (ret < 0) - goto done; + string_list_append(&refnames_to_check, u->refname); /* * There is no need to write the reference deletion @@ -1379,6 +1375,13 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, } } + string_list_sort(&refnames_to_check); + ret = refs_verify_refnames_available(ref_store, &refnames_to_check, &affected_refnames, NULL, + transaction->flags & REF_TRANSACTION_FLAG_INITIAL, + err); + if (ret < 0) + goto done; + transaction->backend_data = tx_data; transaction->state = REF_TRANSACTION_PREPARED; @@ -1394,6 +1397,7 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, string_list_clear(&affected_refnames, 0); strbuf_release(&referent); strbuf_release(&head_referent); + string_list_clear(&refnames_to_check, 0); return ret; } From patchwork Thu Mar 6 15:08:37 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004657 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 1866520E016 for ; Thu, 6 Mar 2025 15:08:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273731; cv=none; b=hhdN/hkeJFPezh/R2Wxfv8ky25AtnlNcZuTviIZK6n0FAA5h0/BW7Gj442s/nWjf93o/vYF2yUyhd4O3t7VwQLF+I10FJg6L5EFcB2SYnZo3CmMhAqGWPmnUT4ycv7SmQI1fUw4aBtluIJ4tupi4Su/O/XkGurzpbNdSsJQott0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273731; c=relaxed/simple; bh=sIrzJj0ozy+yWL9q8qDuo7nbf7MR1gvy+JXbP2zNIUM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=YuTwC6laGX1HnYHLk+Qu3pJHSBt3q/T9xr4Z9ULVXeuabF1GOM0dfTkDPR/mHuummpuGQSO3H0PPHOw/ixOWbnlJvxFlmi1OH+vP8sqHrxQKYaxwDAKMvZD5j/aC2bGXLhypOeo6okxjpMFZqdRsQC23FJ6K9iCguQxloI7V5V8= 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=W8bFldHc; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=it/RCsUf; arc=none smtp.client-ip=202.12.124.147 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="W8bFldHc"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="it/RCsUf" Received: from phl-compute-13.internal (phl-compute-13.phl.internal [10.202.2.53]) by mailfout.stl.internal (Postfix) with ESMTP id 1EA8D11400C9; Thu, 6 Mar 2025 10:08:49 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-13.internal (MEProxy); Thu, 06 Mar 2025 10:08:49 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273728; x=1741360128; bh=7ZMpfbXD8DZFHMcrIdgHDhTTGGQ5/egavgo0IN9yleo=; b= W8bFldHcYMz8Fp4G/dfxx933+un+bUvm2Q72AwRssA4XFAhGFV0H3ERsOwz80GnA 11P+NDitUtxUMniW74BnI5etyF05NM5zWqK/Et+FUtb5wlL4EWpvJnapRJ0t889k lBw9Fa5eQbyw2exyhjqqfbXKqLvioXUKT17PBhMics5YpcKlAaGCeHjyOJY5ZRau Dcje5gf+6ei+LZs33oN+LgI4efbz9KP2jhLoveIc2yye8pWxfwo5JPa5LhGxG7IA KQkDoKiClPS868cfiiO6XwsH8/5ONhgO3zo+jMyPi77cp822jHNPX6zdhiwW+pOA ZahpCzcJc0nf7RevLj2TGQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273728; x= 1741360128; bh=7ZMpfbXD8DZFHMcrIdgHDhTTGGQ5/egavgo0IN9yleo=; b=i t/RCsUffbhlo6xjnOIzM9Y64efumhhyA1KQelJzRH0Etjvku2qnH5/VMCXl++tni TeDggmW7D8Rx2jdz2Hite3LigEfIXu0MiziGGp1HxBVkTxnFRktS3TqInZ+XykdA uJAyhTkKk9kTZiHtCYkUEcpVRDWg7YWSWlakzWcaOXnieEewVWhHDK+Fc4ABFHgC gFWGBxEDb7X+wttGpOtjXnvEpaDJM6/FsPY1ABec4xmGXtn6ZFM4H9qy7iBGGG2c y+ssj2rtg6f+rWhIXmUKdviuMRqy7wQHNghHoSL0P8EPgXu6LsB0X2QC39TydjES WAg3NeJ7kKo1o04FRhJcQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehsrghnuggrlhhssegtrhhushhthihtohhoth hhphgrshhtvgdrnhgvthdprhgtphhtthhopehshhgvjhhirghluhhosehgmhgrihhlrdgt ohhmpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprhgtphhtthhope hpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtoheptghhrhhishgtohholhesthhugihf rghmihhlhidrohhrghdprhgtphhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrd gtohhmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:47 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 61a539e7 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:44 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:37 +0100 Subject: [PATCH v5 06/16] refs/files: batch refname availability checks for normal transactions Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-6-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Same as the "reftable" backend that we have adapted in the preceding commit to use batched refname availability checks we can also do so for the "files" backend. Things are a bit more intricate here though, as we call `refs_verify_refname_available()` in a set of different contexts: 1. `lock_raw_ref()` when it hits either EEXISTS or EISDIR when creating a new reference, mostly to create a nice, user-readable error message. This is nothing we have to care about too much, as we only hit this code path at most once when we hit a conflict. 2. `lock_raw_ref()` when it _could_ create the lockfile to check whether it is conflicting with any packed refs. In the general case, this code path will be hit once for every (successful) reference update. 3. `lock_ref_oid_basic()`, but it is only executed when copying or renaming references or when expiring reflogs. It will thus not be called in contexts where we have many references queued up. 4. `refs_refname_ref_available()`, but again only when copying or renaming references. It is thus not interesting due to the same reason as the previous case. 5. `files_transaction_finish_initial()`, which is only executed when creating a new repository or migrating references. So out of these, only (2) and (5) are viable candidates to use the batched checks. Adapt `lock_raw_ref()` accordingly by queueing up reference names that need to be checked for availability and then checking them after we have processed all updates. This check is done before we (optionally) lock the `packed-refs` file, which is somewhat flawed because it means that the `packed-refs` could still change after the availability check and thus create an undetected conflict. But unconditionally locking the file would change semantics that users are likely to rely on, so we keep the current locking sequence intact, even if it's suboptmial. The refactoring of `files_transaction_finish_initial()` will be done in the next commit. Signed-off-by: Patrick Steinhardt --- refs/files-backend.c | 42 +++++++++++++++++++++++++++++++----------- 1 file changed, 31 insertions(+), 11 deletions(-) diff --git a/refs/files-backend.c b/refs/files-backend.c index 29f08dced40..6ce79cf0791 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -678,6 +678,7 @@ static void unlock_ref(struct ref_lock *lock) */ static int lock_raw_ref(struct files_ref_store *refs, const char *refname, int mustexist, + struct string_list *refnames_to_check, const struct string_list *extras, struct ref_lock **lock_p, struct strbuf *referent, @@ -855,16 +856,11 @@ static int lock_raw_ref(struct files_ref_store *refs, } /* - * If the ref did not exist and we are creating it, - * make sure there is no existing packed ref that - * conflicts with refname: + * If the ref did not exist and we are creating it, we have to + * make sure there is no existing packed ref that conflicts + * with refname. This check is deferred so that we can batch it. */ - if (refs_verify_refname_available( - refs->packed_ref_store, refname, - extras, NULL, 0, err)) { - ret = TRANSACTION_NAME_CONFLICT; - goto error_return; - } + string_list_insert(refnames_to_check, refname); } ret = 0; @@ -2569,6 +2565,7 @@ static int lock_ref_for_update(struct files_ref_store *refs, struct ref_update *update, struct ref_transaction *transaction, const char *head_ref, + struct string_list *refnames_to_check, struct string_list *affected_refnames, struct strbuf *err) { @@ -2597,7 +2594,7 @@ static int lock_ref_for_update(struct files_ref_store *refs, lock->count++; } else { ret = lock_raw_ref(refs, update->refname, mustexist, - affected_refnames, + refnames_to_check, affected_refnames, &lock, &referent, &update->type, err); if (ret) { @@ -2811,6 +2808,7 @@ static int files_transaction_prepare(struct ref_store *ref_store, size_t i; int ret = 0; struct string_list affected_refnames = STRING_LIST_INIT_NODUP; + struct string_list refnames_to_check = STRING_LIST_INIT_NODUP; char *head_ref = NULL; int head_type; struct files_transaction_backend_data *backend_data; @@ -2898,7 +2896,8 @@ static int files_transaction_prepare(struct ref_store *ref_store, struct ref_update *update = transaction->updates[i]; ret = lock_ref_for_update(refs, update, transaction, - head_ref, &affected_refnames, err); + head_ref, &refnames_to_check, + &affected_refnames, err); if (ret) goto cleanup; @@ -2930,6 +2929,26 @@ static int files_transaction_prepare(struct ref_store *ref_store, } } + /* + * Verify that none of the loose reference that we're about to write + * conflict with any existing packed references. Ideally, we'd do this + * check after the packed-refs are locked so that the file cannot + * change underneath our feet. But introducing such a lock now would + * probably do more harm than good as users rely on there not being a + * global lock with the "files" backend. + * + * Another alternative would be to do the check after the (optional) + * lock, but that would extend the time we spend in the globally-locked + * state. + * + * So instead, we accept the race for now. + */ + if (refs_verify_refnames_available(refs->packed_ref_store, &refnames_to_check, + &affected_refnames, NULL, 0, err)) { + ret = TRANSACTION_NAME_CONFLICT; + goto cleanup; + } + if (packed_transaction) { if (packed_refs_lock(refs->packed_ref_store, 0, err)) { ret = TRANSACTION_GENERIC_ERROR; @@ -2972,6 +2991,7 @@ static int files_transaction_prepare(struct ref_store *ref_store, cleanup: free(head_ref); string_list_clear(&affected_refnames, 0); + string_list_clear(&refnames_to_check, 0); if (ret) files_transaction_cleanup(refs, transaction); From patchwork Thu Mar 6 15:08:38 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004658 Received: from fhigh-b5-smtp.messagingengine.com (fhigh-b5-smtp.messagingengine.com [202.12.124.156]) (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 6D12A20F075 for ; Thu, 6 Mar 2025 15:08:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.156 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273733; cv=none; b=kSMya6RLfn7hRPhy7SLeIRmvCW+lyIl2+cEH68yRi5deHFysTR4wgi5pcZzxad/q0OfLjM5hfMWIFFWCnaeVw+Esfwc2OiT65TJogOQiODaoQWRheJjIjQ23MvYn8m0Y8P5RjAg5+9APh4Dy+yy3sH7tSql+iFuiHpSFp6stD7k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273733; c=relaxed/simple; bh=+JLNqljak4qfGe2JPwUAvupebX0+qYevELT7CjUuBYY=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=DS5gQCxWUQ0KBBY0UocgY/RP2q9LauZjRDmL/8M0FeXQkYdMl2qnE0+/NKLbGoMBW4OiaE3XaXcG6bgq6cL/51zg/BGlcs0BS8bz/wLpN9QubDYoVFQEwltNZtkfmi0Wk/p7fRIlLbE6sdptQV3Q0ANGNeZTTdYP45OrbrfXt2s= 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=SdWpDAvv; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=T+XKm5Sg; arc=none smtp.client-ip=202.12.124.156 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="SdWpDAvv"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="T+XKm5Sg" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfhigh.stl.internal (Postfix) with ESMTP id 60D01254016F; Thu, 6 Mar 2025 10:08:50 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-02.internal (MEProxy); Thu, 06 Mar 2025 10:08:50 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273730; x=1741360130; bh=ReK4dza0+5uQcJ0poVZRvn7ljPsV38euQD7J8wj4uWU=; b= SdWpDAvvCQplF6doYWdq2pC3up8cKqNwC1nwMRsTQ1Eu+kS/IGPC8rJNHw+n8Qvq q3bBRTsSIKh/+Ci5cr52ICo7Qtg1jNPGKE1vw03q/e6wt++8B6rfqnKlfJ7msbsz 6EvTC8YmmyybV1oZfnwpmFSUeE1UNG8bX1BOLvetp15J914GkImWVxjmBbP2GYtb EkJU5c66Bhlso6lMCP3eT1eS6cezFVOmWLm9V4tahv4me3/uRV3N2YhhYygodyY3 13C4GrsrmmdiBahVb/+DeyWaJ8XbMZAyx2brMkeXxAfpOeECwpwK+NluJQvOJ5ab bePZdOaL8eXlia5+EKiwZg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273730; x= 1741360130; bh=ReK4dza0+5uQcJ0poVZRvn7ljPsV38euQD7J8wj4uWU=; b=T +XKm5SgNr3QpSrJhgS19/ovfVfu2dmVtBnZqYVDWK30HQYQ91tEE5/CfWi/HfAUK NqUWij38y5fU9Qq80Rgg8UsMQA3Y1OWG0SiA2gdq37ozf8rs/IjAUmyl8pBr9ReY CrDHVbQ7SfLVrb//czikj34okqp8Flb1S8D6QqCeKKWxwLHlafM65qNo7Q0tbHqH xLcFDh6T8cepnRyRWxWeMmn7EyPYeVfgTBM450cKD5HDB+1oE+et9w/g8vVP2Vgb Z0mZMJCJWPMjKrZgQhWO7o134CMHPh+a6aAOIcwBcl22/sBXGV9hZf17Qk7tnQCV dz0AG7grb8b0nO2lyGgjw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehshhgvjhhirghluhhosehgmhgrihhlrdgtoh hmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthho pehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpthhtoheptghhrhhishgtohholh esthhugihfrghmihhlhidrohhrghdprhgtphhtthhopehpvghffhesphgvfhhfrdhnvght pdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtth hopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:48 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 03b7f417 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:45 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:38 +0100 Subject: [PATCH v5 07/16] refs/files: batch refname availability checks for initial transactions Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-7-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 The "files" backend explicitly carves out special logic for its initial transaction so that it can avoid writing out every single reference as a loose reference. While the assumption is that there shouldn't be any preexisting references, we still have to verify that none of the newly written references will conflict with any other new reference in the same transaction. Refactor the initial transaction to use batched refname availability checks. This does not yet have an effect on performance as we still call `refs_verify_refname_available()` in a loop. But this will change in subsequent commits and then impact performance when cloning a repository with many references or when migrating references to the "files" format. This will improve performance when cloning a repository with many references or when migrating references from any format to the "files" format once the availability checks have learned to optimize checks for many references in a subsequent commit. Signed-off-by: Patrick Steinhardt --- refs/files-backend.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) diff --git a/refs/files-backend.c b/refs/files-backend.c index 6ce79cf0791..11a620ea11a 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -3056,6 +3056,7 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, size_t i; int ret = 0; struct string_list affected_refnames = STRING_LIST_INIT_NODUP; + struct string_list refnames_to_check = STRING_LIST_INIT_NODUP; struct ref_transaction *packed_transaction = NULL; struct ref_transaction *loose_transaction = NULL; @@ -3105,11 +3106,7 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, !is_null_oid(&update->old_oid)) BUG("initial ref transaction with old_sha1 set"); - if (refs_verify_refname_available(&refs->base, update->refname, - &affected_refnames, NULL, 1, err)) { - ret = TRANSACTION_NAME_CONFLICT; - goto cleanup; - } + string_list_append(&refnames_to_check, update->refname); /* * packed-refs don't support symbolic refs, root refs and reflogs, @@ -3145,8 +3142,19 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, } } - if (packed_refs_lock(refs->packed_ref_store, 0, err) || - ref_transaction_commit(packed_transaction, err)) { + if (packed_refs_lock(refs->packed_ref_store, 0, err)) { + ret = TRANSACTION_GENERIC_ERROR; + goto cleanup; + } + + if (refs_verify_refnames_available(&refs->base, &refnames_to_check, + &affected_refnames, NULL, 1, err)) { + packed_refs_unlock(refs->packed_ref_store); + ret = TRANSACTION_NAME_CONFLICT; + goto cleanup; + } + + if (ref_transaction_commit(packed_transaction, err)) { ret = TRANSACTION_GENERIC_ERROR; goto cleanup; } @@ -3167,6 +3175,7 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, ref_transaction_free(packed_transaction); transaction->state = REF_TRANSACTION_CLOSED; string_list_clear(&affected_refnames, 0); + string_list_clear(&refnames_to_check, 0); return ret; } From patchwork Thu Mar 6 15:08:39 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004659 Received: from fhigh-b5-smtp.messagingengine.com (fhigh-b5-smtp.messagingengine.com [202.12.124.156]) (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 39CEC20A5C3 for ; Thu, 6 Mar 2025 15:08:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.156 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273735; cv=none; b=jzqvS2wrOiA42xDrQn13+oTcTtiaiMnkP3Nea/z+Wg9niqd4mUk79gbZX4gc/t6fiRKNt+SsCnK5mNCbWNE1kNv5QXXd6UpOucGyTvtW937sPqY9yh3BhWlXLKKYQhjRHXPEHkgvfn9P97daqrn8gYjqpJoZ4x+FI9anvfU8V30= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273735; c=relaxed/simple; bh=g309z4lpPFfc92DHQgf0Sr0PWz90aVgPHX5MIkrcPOk=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=B+JNSucRT7NDWAoOySuAErtamF7H9ASi96yDfyWI+gfLzigDAhLcp3eGs8wZd96rT+vUzr8iVFjU5AE+CWYPCd+D0JkdRXaefuatNXQzNMaUWgMwwT/lnQmaFIIAS/607nTJpOnr8k4egBvbeOvmUdESRDw9Jr1EeW1HNCyD5hI= 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=kC/uRoaC; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=MCNb6QcK; arc=none smtp.client-ip=202.12.124.156 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="kC/uRoaC"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="MCNb6QcK" Received: from phl-compute-09.internal (phl-compute-09.phl.internal [10.202.2.49]) by mailfhigh.stl.internal (Postfix) with ESMTP id 1169D25401EA; Thu, 6 Mar 2025 10:08:51 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-09.internal (MEProxy); Thu, 06 Mar 2025 10:08:51 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273730; x=1741360130; bh=6RbOaUK9X4EFI0P6ELntM3L/LLIBGOffzWAmhyNn4mo=; b= kC/uRoaCNMlKJqW5+teluBoDj8Sg13PISXau3JGdgkW2yO6sy86P4RjxetZwPMDK kjterVHhnjPHOJPH/6yFnLV3WvzMB5i2IhHzlzHR1SYKtBJjZLgA2tRT9fmMDPk+ IXjlw5STgn6EHSQP//+gbE6l/LtBYcJS5h5jMfD0O37WYe8g0QgYOUgefUbzOoKU 68yTd3ktmYV50uqPmwqMmqJn0UKoQMwOHbemNTUR0TvKRNapPYatfgxlSo5uHvOH o5MFHFkCBY8Etyoitx7kgK0xs2OjN9/iJdQre2Uf8lERiR61l8uUBUZccEArZFkM wLTDDiGk8KTMbvAQhZhcGA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273730; x= 1741360130; bh=6RbOaUK9X4EFI0P6ELntM3L/LLIBGOffzWAmhyNn4mo=; b=M CNb6QcKQ5+LpGDeT1ZLXcQ5wssXSIcBzrYZXHc0z8qtjcI/vug2pdWsAZzW0PH8w Bnqeei5HEaqIJhLyMg+0orv9yEQPff949CZnBZ4V2rBgAFP++Bq9nfiW/rzcxJt7 5QjPvqVX73u7L0Dg9XW4HAfcrATaSA0dMT5sdVRbwlLxZSQOnpVDXrJoTekzFwPT mmUDKtT0QOCzJb9CrcBjNW484GfHVySYUkNX2AuCtdntCC0kyQ44IbVYnYeQ+0oW p7d4HOJRby3aQB118E/u5QbfRzKc0xiBUXRxBdndKg4oUjUsIcZhwrd2rkE5SBBb vdLb4Ud0GcDHv6Yf1jA0Q== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdelucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtkeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeefhfeugeelheefjeektdffhedvhfdvteefgfdt udffudevveetgeeuuedtkefhgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehshhgvjhhirghluhhosehgmhgrihhlrdgtoh hmpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidrohhrghdprhgt phhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohepph gvfhhfsehpvghffhdrnhgvthdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgt ohhmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtth hopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:49 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 99a4d734 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:46 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:39 +0100 Subject: [PATCH v5 08/16] refs: stop re-verifying common prefixes for availability Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-8-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 One of the checks done by `refs_verify_refnames_available()` is whether any of the prefixes of a reference already exists. For example, given a reference "refs/heads/main", we'd check whether "refs/heads" or "refs" already exist, and if so we'd abort the transaction. When updating multiple references at once, this check is performed for each of the references individually. Consequently, because references tend to have common prefixes like "refs/heads/" or refs/tags/", we evaluate the availability of these prefixes repeatedly. Naturally this is a waste of compute, as the availability of those prefixes should in general not change in the middle of a transaction. And if it would, backends would notice at a later point in time. Optimize this pattern by storing prefixes in a `strset` so that we can trivially track those prefixes that we have already checked. This leads to a significant speedup with the "reftable" backend when creating many references that all share a common prefix: Benchmark 1: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~) Time (mean ± σ): 63.1 ms ± 1.8 ms [User: 41.0 ms, System: 21.6 ms] Range (min … max): 60.6 ms … 69.5 ms 38 runs Benchmark 2: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) Time (mean ± σ): 40.0 ms ± 1.3 ms [User: 29.3 ms, System: 10.3 ms] Range (min … max): 38.1 ms … 47.3 ms 61 runs Summary update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) ran 1.58 ± 0.07 times faster than update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~) For the "files" backend we see an improvement, but a much smaller one: Benchmark 1: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD~) Time (mean ± σ): 395.8 ms ± 5.3 ms [User: 63.6 ms, System: 330.5 ms] Range (min … max): 387.0 ms … 404.6 ms 10 runs Benchmark 2: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) Time (mean ± σ): 386.0 ms ± 4.0 ms [User: 51.5 ms, System: 332.8 ms] Range (min … max): 380.8 ms … 392.6 ms 10 runs Summary update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) ran 1.03 ± 0.02 times faster than update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD~) This change also leads to a modest improvement when writing references with "initial" semantics, for example when migrating references. The following benchmarks are migrating 1m references from the "reftable" to the "files" backend: Benchmark 1: migrate reftable:files (refcount = 1000000, revision = HEAD~) Time (mean ± σ): 836.6 ms ± 5.6 ms [User: 645.2 ms, System: 185.2 ms] Range (min … max): 829.6 ms … 845.9 ms 10 runs Benchmark 2: migrate reftable:files (refcount = 1000000, revision = HEAD) Time (mean ± σ): 759.8 ms ± 5.1 ms [User: 574.9 ms, System: 178.9 ms] Range (min … max): 753.1 ms … 768.8 ms 10 runs Summary migrate reftable:files (refcount = 1000000, revision = HEAD) ran 1.10 ± 0.01 times faster than migrate reftable:files (refcount = 1000000, revision = HEAD~) And vice versa: Benchmark 1: migrate files:reftable (refcount = 1000000, revision = HEAD~) Time (mean ± σ): 870.7 ms ± 5.7 ms [User: 735.2 ms, System: 127.4 ms] Range (min … max): 861.6 ms … 883.2 ms 10 runs Benchmark 2: migrate files:reftable (refcount = 1000000, revision = HEAD) Time (mean ± σ): 799.1 ms ± 8.5 ms [User: 661.1 ms, System: 130.2 ms] Range (min … max): 787.5 ms … 812.6 ms 10 runs Summary migrate files:reftable (refcount = 1000000, revision = HEAD) ran 1.09 ± 0.01 times faster than migrate files:reftable (refcount = 1000000, revision = HEAD~) The impact here is significantly smaller given that we don't perform any reference reads with "initial" semantics, so the speedup only comes from us doing less string list lookups. Signed-off-by: Patrick Steinhardt --- refs.c | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/refs.c b/refs.c index 5a9b0f2fa1e..eaf41421f50 100644 --- a/refs.c +++ b/refs.c @@ -2476,6 +2476,7 @@ int refs_verify_refnames_available(struct ref_store *refs, { struct strbuf dirname = STRBUF_INIT; struct strbuf referent = STRBUF_INIT; + struct strset dirnames; int ret = -1; /* @@ -2485,6 +2486,8 @@ int refs_verify_refnames_available(struct ref_store *refs, assert(err); + strset_init(&dirnames); + for (size_t i = 0; i < refnames->nr; i++) { const char *refname = refnames->items[i].string; const char *extra_refname; @@ -2514,6 +2517,14 @@ int refs_verify_refnames_available(struct ref_store *refs, if (skip && string_list_has_string(skip, dirname.buf)) continue; + /* + * If we've already seen the directory we don't need to + * process it again. Skip it to avoid checking checking + * common prefixes like "refs/heads/" repeatedly. + */ + if (!strset_add(&dirnames, dirname.buf)) + continue; + if (!initial_transaction && !refs_read_raw_ref(refs, dirname.buf, &oid, &referent, &type, &ignore_errno)) { @@ -2574,6 +2585,7 @@ int refs_verify_refnames_available(struct ref_store *refs, cleanup: strbuf_release(&referent); strbuf_release(&dirname); + strset_clear(&dirnames); return ret; } From patchwork Thu Mar 6 15:08:40 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004661 Received: from fhigh-b5-smtp.messagingengine.com (fhigh-b5-smtp.messagingengine.com [202.12.124.156]) (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 9481820FAB0 for ; Thu, 6 Mar 2025 15:08:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.156 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273736; cv=none; b=LCB1y4jHAEtXcgc/fAs23AZru2rhBQocMGh1TR7mqm7WQJsIyw1H9/kYAFFK7Mt9FjBSRNYyZlKO28OZoFTcBGqfC9YCkBL/q3ozjgl4XEahv7VA+lPESc8Rcc3BJuU8A3I9g5KliJD5BrmFQQ4N31Y+HiWDB5WNGMBQTErgCKQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273736; c=relaxed/simple; bh=veWv7mAb3LhzC32wen9+dnZP5ADlRgoHUnWrQRBqB3E=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=B6QtftLTdnaoA+Sxq8fg9Axea5u/yZ7wY+YjxAHylC6AQrLzdd9P2f0ny/sasEv2tELz2fAl3RSKW0vR+sdu3lhR59wfuqyX578XScWFzvQXQUT7pdYAHeVu6YP0UXBL7nlwdUjgZo6Scw1ZudffaGSfLpbX39eaQYlU2GC81lw= 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=mNdY/QDH; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=rTPnYXnt; arc=none smtp.client-ip=202.12.124.156 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="mNdY/QDH"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="rTPnYXnt" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfhigh.stl.internal (Postfix) with ESMTP id 4A99E25401EB; Thu, 6 Mar 2025 10:08:52 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-02.internal (MEProxy); Thu, 06 Mar 2025 10:08:52 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273732; x=1741360132; bh=vGKSLeCU4q9ezxoi5GCrYB16v+9u0mzUr0cUbJqEV3M=; b= mNdY/QDHPIwy+96A5FUIzMU5/kTAJVGjR75is/XvxyJfhFk2eJpf930XbcyFgOvo FCP1Gh9xi4/xgGJ0Y/uVLbXs6c5qUed3GBW1YvaRH99xRkxY8Q3KPEF0TdpOpagT PfGAumrDpMTpcvP4e96gUepua6cuzfl1IT2P0SmZ5rMjzvKaXC+VyWWikkhHuFGu oyhGFZa1Srqz8WwBaR61KvJb63ecPoeqp+oTnIkGNuEh8xzKsSJDyH7Mn5Aig735 4c/BsnX/XopHJzpyvYkkh7hCw/3WSo4UwxHzVcRD29mk6AwS6AZl6DD08izXT8T+ JnaEu5APXyHIF6Qe7u/ljg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273732; x= 1741360132; bh=vGKSLeCU4q9ezxoi5GCrYB16v+9u0mzUr0cUbJqEV3M=; b=r TPnYXntbeAXH7vjufbf3JTbf2v8QPp1jAFeIH5oDkQMgwarTEjpDAERKGr4+fn8y v6qb1pp4pIuoCRTzoIYadkx6t4kViUqtDhhCsRZvCkTSDeJZk6U+or2ejmOQE2WD sq5nTS1Y4K8jRUpatWl8mX7FWcCT8qJGkKZYK5Hy2mxHW1WX3QEMtmiLm11HFyoS PqLLyXG/Us0ARdh6yUST60FysMGG/WGaAsCxHoNTtOuPZ7w5TexsyM47oS8mMG8K NmOP0Cl7ywBHlrxPjsKEe0CHJ7XTD/+kBXIQPfPy/Ll4886BiAuYV2i9IL4p8jCr m65YfiZrm5tQLHPwe9+ag== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrd gtohhmpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprhgtphhtthho pehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepshgrnhgurghlsh estghruhhsthihthhoohhthhhprghsthgvrdhnvghtpdhrtghpthhtohepphgvfhhfsehp vghffhdrnhgvthdprhgtphhtthhopehshhgvjhhirghluhhosehgmhgrihhlrdgtohhmpd hrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:50 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id c13ee92d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:47 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:40 +0100 Subject: [PATCH v5 09/16] refs/iterator: separate lifecycle from iteration Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-9-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 The ref and reflog iterators have their lifecycle attached to iteration: once the iterator reaches its end, it is automatically released and the caller doesn't have to care about that anymore. When the iterator should be released before it has been exhausted, callers must explicitly abort the iterator via `ref_iterator_abort()`. This lifecycle is somewhat unusual in the Git codebase and creates two problems: - Callsites need to be very careful about when exactly they call `ref_iterator_abort()`, as calling the function is only valid when the iterator itself still is. This leads to somewhat awkward calling patterns in some situations. - It is impossible to reuse iterators and re-seek them to a different prefix. This feature isn't supported by any iterator implementation except for the reftable iterators anyway, but if it was implemented it would allow us to optimize cases where we need to search for specific references repeatedly by reusing internal state. Detangle the lifecycle from iteration so that we don't deallocate the iterator anymore once it is exhausted. Instead, callers are now expected to always call a newly introduce `ref_iterator_free()` function that deallocates the iterator and its internal state. Note that the `dir_iterator` is somewhat special because it does not implement the `ref_iterator` interface, but is only used to implement other iterators. Consequently, we have to provide `dir_iterator_free()` instead of `dir_iterator_release()` as the allocated structure itself is managed by the `dir_iterator` interfaces, as well, and not freed by `ref_iterator_free()` like in all the other cases. While at it, drop the return value of `ref_iterator_abort()`, which wasn't really required by any of the iterator implementations anyway. Furthermore, stop calling `base_ref_iterator_free()` in any of the backends, but instead call it in `ref_iterator_free()`. Signed-off-by: Patrick Steinhardt --- builtin/clone.c | 2 + dir-iterator.c | 24 +++++------ dir-iterator.h | 11 ++--- iterator.h | 2 +- refs.c | 7 +++- refs/debug.c | 9 ++--- refs/files-backend.c | 36 +++++------------ refs/iterator.c | 95 ++++++++++++++------------------------------ refs/packed-backend.c | 27 ++++++------- refs/ref-cache.c | 9 ++--- refs/refs-internal.h | 29 +++++--------- refs/reftable-backend.c | 34 ++++------------ t/helper/test-dir-iterator.c | 1 + 13 files changed, 100 insertions(+), 186 deletions(-) diff --git a/builtin/clone.c b/builtin/clone.c index fd001d800c6..ac3e84b2b18 100644 --- a/builtin/clone.c +++ b/builtin/clone.c @@ -426,6 +426,8 @@ static void copy_or_link_directory(struct strbuf *src, struct strbuf *dest, strbuf_setlen(src, src_len); die(_("failed to iterate over '%s'"), src->buf); } + + dir_iterator_free(iter); } static void clone_local(const char *src_repo, const char *dest_repo) diff --git a/dir-iterator.c b/dir-iterator.c index de619846f29..857e1d9bdaf 100644 --- a/dir-iterator.c +++ b/dir-iterator.c @@ -193,9 +193,9 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) if (S_ISDIR(iter->base.st.st_mode) && push_level(iter)) { if (errno != ENOENT && iter->flags & DIR_ITERATOR_PEDANTIC) - goto error_out; + return ITER_ERROR; if (iter->levels_nr == 0) - goto error_out; + return ITER_ERROR; } /* Loop until we find an entry that we can give back to the caller. */ @@ -211,11 +211,11 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) int ret = next_directory_entry(level->dir, iter->base.path.buf, &de); if (ret < 0) { if (iter->flags & DIR_ITERATOR_PEDANTIC) - goto error_out; + return ITER_ERROR; continue; } else if (ret > 0) { if (pop_level(iter) == 0) - return dir_iterator_abort(dir_iterator); + return ITER_DONE; continue; } @@ -223,7 +223,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) } else { if (level->entries_idx >= level->entries.nr) { if (pop_level(iter) == 0) - return dir_iterator_abort(dir_iterator); + return ITER_DONE; continue; } @@ -232,22 +232,21 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) if (prepare_next_entry_data(iter, name)) { if (errno != ENOENT && iter->flags & DIR_ITERATOR_PEDANTIC) - goto error_out; + return ITER_ERROR; continue; } return ITER_OK; } - -error_out: - dir_iterator_abort(dir_iterator); - return ITER_ERROR; } -int dir_iterator_abort(struct dir_iterator *dir_iterator) +void dir_iterator_free(struct dir_iterator *dir_iterator) { struct dir_iterator_int *iter = (struct dir_iterator_int *)dir_iterator; + if (!iter) + return; + for (; iter->levels_nr; iter->levels_nr--) { struct dir_iterator_level *level = &iter->levels[iter->levels_nr - 1]; @@ -266,7 +265,6 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator) free(iter->levels); strbuf_release(&iter->base.path); free(iter); - return ITER_DONE; } struct dir_iterator *dir_iterator_begin(const char *path, unsigned int flags) @@ -301,7 +299,7 @@ struct dir_iterator *dir_iterator_begin(const char *path, unsigned int flags) return dir_iterator; error_out: - dir_iterator_abort(dir_iterator); + dir_iterator_free(dir_iterator); errno = saved_errno; return NULL; } diff --git a/dir-iterator.h b/dir-iterator.h index 6d438809b6e..ccd6a197343 100644 --- a/dir-iterator.h +++ b/dir-iterator.h @@ -28,7 +28,7 @@ * * while ((ok = dir_iterator_advance(iter)) == ITER_OK) { * if (want_to_stop_iteration()) { - * ok = dir_iterator_abort(iter); + * ok = ITER_DONE; * break; * } * @@ -39,6 +39,7 @@ * * if (ok != ITER_DONE) * handle_error(); + * dir_iterator_free(iter); * * Callers are allowed to modify iter->path while they are working, * but they must restore it to its original contents before calling @@ -107,11 +108,7 @@ struct dir_iterator *dir_iterator_begin(const char *path, unsigned int flags); */ int dir_iterator_advance(struct dir_iterator *iterator); -/* - * End the iteration before it has been exhausted. Free the - * dir_iterator and any associated resources and return ITER_DONE. On - * error, free the dir_iterator and return ITER_ERROR. - */ -int dir_iterator_abort(struct dir_iterator *iterator); +/* Free the dir_iterator and any associated resources. */ +void dir_iterator_free(struct dir_iterator *iterator); #endif diff --git a/iterator.h b/iterator.h index 0f6900e43ad..6b77dcc2626 100644 --- a/iterator.h +++ b/iterator.h @@ -12,7 +12,7 @@ #define ITER_OK 0 /* - * The iterator is exhausted and has been freed. + * The iterator is exhausted. */ #define ITER_DONE -1 diff --git a/refs.c b/refs.c index eaf41421f50..8eff60a2186 100644 --- a/refs.c +++ b/refs.c @@ -2476,6 +2476,7 @@ int refs_verify_refnames_available(struct ref_store *refs, { struct strbuf dirname = STRBUF_INIT; struct strbuf referent = STRBUF_INIT; + struct ref_iterator *iter = NULL; struct strset dirnames; int ret = -1; @@ -2552,7 +2553,6 @@ int refs_verify_refnames_available(struct ref_store *refs, strbuf_addch(&dirname, '/'); if (!initial_transaction) { - struct ref_iterator *iter; int ok; iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, @@ -2564,12 +2564,14 @@ int refs_verify_refnames_available(struct ref_store *refs, strbuf_addf(err, _("'%s' exists; cannot create '%s'"), iter->refname, refname); - ref_iterator_abort(iter); goto cleanup; } if (ok != ITER_DONE) BUG("error while iterating over references"); + + ref_iterator_free(iter); + iter = NULL; } extra_refname = find_descendant_ref(dirname.buf, extras, skip); @@ -2586,6 +2588,7 @@ int refs_verify_refnames_available(struct ref_store *refs, strbuf_release(&referent); strbuf_release(&dirname); strset_clear(&dirnames); + ref_iterator_free(iter); return ret; } diff --git a/refs/debug.c b/refs/debug.c index fbc4df08b43..a9786da4ba1 100644 --- a/refs/debug.c +++ b/refs/debug.c @@ -179,19 +179,18 @@ static int debug_ref_iterator_peel(struct ref_iterator *ref_iterator, return res; } -static int debug_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void debug_ref_iterator_release(struct ref_iterator *ref_iterator) { struct debug_ref_iterator *diter = (struct debug_ref_iterator *)ref_iterator; - int res = diter->iter->vtable->abort(diter->iter); - trace_printf_key(&trace_refs, "iterator_abort: %d\n", res); - return res; + diter->iter->vtable->release(diter->iter); + trace_printf_key(&trace_refs, "iterator_abort\n"); } static struct ref_iterator_vtable debug_ref_iterator_vtable = { .advance = debug_ref_iterator_advance, .peel = debug_ref_iterator_peel, - .abort = debug_ref_iterator_abort, + .release = debug_ref_iterator_release, }; static struct ref_iterator * diff --git a/refs/files-backend.c b/refs/files-backend.c index 11a620ea11a..859f1c11941 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -915,10 +915,6 @@ static int files_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - iter->iter0 = NULL; - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - ok = ITER_ERROR; - return ok; } @@ -931,23 +927,17 @@ static int files_ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator_peel(iter->iter0, peeled); } -static int files_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void files_ref_iterator_release(struct ref_iterator *ref_iterator) { struct files_ref_iterator *iter = (struct files_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->iter0) - ok = ref_iterator_abort(iter->iter0); - - base_ref_iterator_free(ref_iterator); - return ok; + ref_iterator_free(iter->iter0); } static struct ref_iterator_vtable files_ref_iterator_vtable = { .advance = files_ref_iterator_advance, .peel = files_ref_iterator_peel, - .abort = files_ref_iterator_abort, + .release = files_ref_iterator_release, }; static struct ref_iterator *files_ref_iterator_begin( @@ -1378,7 +1368,7 @@ static int should_pack_refs(struct files_ref_store *refs, iter->flags, opts)) refcount++; if (refcount >= limit) { - ref_iterator_abort(iter); + ref_iterator_free(iter); return 1; } } @@ -1386,6 +1376,7 @@ static int should_pack_refs(struct files_ref_store *refs, if (ret != ITER_DONE) die("error while iterating over references"); + ref_iterator_free(iter); return 0; } @@ -1452,6 +1443,7 @@ static int files_pack_refs(struct ref_store *ref_store, packed_refs_unlock(refs->packed_ref_store); prune_refs(refs, &refs_to_prune); + ref_iterator_free(iter); strbuf_release(&err); return 0; } @@ -2299,9 +2291,6 @@ static int files_reflog_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - iter->dir_iterator = NULL; - if (ref_iterator_abort(ref_iterator) == ITER_ERROR) - ok = ITER_ERROR; return ok; } @@ -2311,23 +2300,17 @@ static int files_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSED, BUG("ref_iterator_peel() called for reflog_iterator"); } -static int files_reflog_iterator_abort(struct ref_iterator *ref_iterator) +static void files_reflog_iterator_release(struct ref_iterator *ref_iterator) { struct files_reflog_iterator *iter = (struct files_reflog_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->dir_iterator) - ok = dir_iterator_abort(iter->dir_iterator); - - base_ref_iterator_free(ref_iterator); - return ok; + dir_iterator_free(iter->dir_iterator); } static struct ref_iterator_vtable files_reflog_iterator_vtable = { .advance = files_reflog_iterator_advance, .peel = files_reflog_iterator_peel, - .abort = files_reflog_iterator_abort, + .release = files_reflog_iterator_release, }; static struct ref_iterator *reflog_iterator_begin(struct ref_store *ref_store, @@ -3837,6 +3820,7 @@ static int files_fsck_refs_dir(struct ref_store *ref_store, ret = error(_("failed to iterate over '%s'"), sb.buf); out: + dir_iterator_free(iter); strbuf_release(&sb); strbuf_release(&refname); return ret; diff --git a/refs/iterator.c b/refs/iterator.c index d25e568bf0b..aaeff270437 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -21,9 +21,14 @@ int ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator->vtable->peel(ref_iterator, peeled); } -int ref_iterator_abort(struct ref_iterator *ref_iterator) +void ref_iterator_free(struct ref_iterator *ref_iterator) { - return ref_iterator->vtable->abort(ref_iterator); + if (ref_iterator) { + ref_iterator->vtable->release(ref_iterator); + /* Help make use-after-free bugs fail quickly: */ + ref_iterator->vtable = NULL; + free(ref_iterator); + } } void base_ref_iterator_init(struct ref_iterator *iter, @@ -36,20 +41,13 @@ void base_ref_iterator_init(struct ref_iterator *iter, iter->flags = 0; } -void base_ref_iterator_free(struct ref_iterator *iter) -{ - /* Help make use-after-free bugs fail quickly: */ - iter->vtable = NULL; - free(iter); -} - struct empty_ref_iterator { struct ref_iterator base; }; -static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator) +static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator UNUSED) { - return ref_iterator_abort(ref_iterator); + return ITER_DONE; } static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, @@ -58,16 +56,14 @@ static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, BUG("peel called for empty iterator"); } -static int empty_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void empty_ref_iterator_release(struct ref_iterator *ref_iterator UNUSED) { - base_ref_iterator_free(ref_iterator); - return ITER_DONE; } static struct ref_iterator_vtable empty_ref_iterator_vtable = { .advance = empty_ref_iterator_advance, .peel = empty_ref_iterator_peel, - .abort = empty_ref_iterator_abort, + .release = empty_ref_iterator_release, }; struct ref_iterator *empty_ref_iterator_begin(void) @@ -151,11 +147,13 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (!iter->current) { /* Initialize: advance both iterators to their first entries */ if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) { + ref_iterator_free(iter->iter0); iter->iter0 = NULL; if (ok == ITER_ERROR) goto error; } if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) { + ref_iterator_free(iter->iter1); iter->iter1 = NULL; if (ok == ITER_ERROR) goto error; @@ -166,6 +164,7 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) * entry: */ if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) { + ref_iterator_free(*iter->current); *iter->current = NULL; if (ok == ITER_ERROR) goto error; @@ -179,9 +178,8 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) iter->select(iter->iter0, iter->iter1, iter->cb_data); if (selection == ITER_SELECT_DONE) { - return ref_iterator_abort(ref_iterator); + return ITER_DONE; } else if (selection == ITER_SELECT_ERROR) { - ref_iterator_abort(ref_iterator); return ITER_ERROR; } @@ -195,6 +193,7 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (selection & ITER_SKIP_SECONDARY) { if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) { + ref_iterator_free(*secondary); *secondary = NULL; if (ok == ITER_ERROR) goto error; @@ -211,7 +210,6 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) } error: - ref_iterator_abort(ref_iterator); return ITER_ERROR; } @@ -227,28 +225,18 @@ static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator_peel(*iter->current, peeled); } -static int merge_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void merge_ref_iterator_release(struct ref_iterator *ref_iterator) { struct merge_ref_iterator *iter = (struct merge_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->iter0) { - if (ref_iterator_abort(iter->iter0) != ITER_DONE) - ok = ITER_ERROR; - } - if (iter->iter1) { - if (ref_iterator_abort(iter->iter1) != ITER_DONE) - ok = ITER_ERROR; - } - base_ref_iterator_free(ref_iterator); - return ok; + ref_iterator_free(iter->iter0); + ref_iterator_free(iter->iter1); } static struct ref_iterator_vtable merge_ref_iterator_vtable = { .advance = merge_ref_iterator_advance, .peel = merge_ref_iterator_peel, - .abort = merge_ref_iterator_abort, + .release = merge_ref_iterator_release, }; struct ref_iterator *merge_ref_iterator_begin( @@ -310,10 +298,10 @@ struct ref_iterator *overlay_ref_iterator_begin( * them. */ if (is_empty_ref_iterator(front)) { - ref_iterator_abort(front); + ref_iterator_free(front); return back; } else if (is_empty_ref_iterator(back)) { - ref_iterator_abort(back); + ref_iterator_free(back); return front; } @@ -350,19 +338,10 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) { int cmp = compare_prefix(iter->iter0->refname, iter->prefix); - if (cmp < 0) continue; - - if (cmp > 0) { - /* - * As the source iterator is ordered, we - * can stop the iteration as soon as we see a - * refname that comes after the prefix: - */ - ok = ref_iterator_abort(iter->iter0); - break; - } + if (cmp > 0) + return ITER_DONE; if (iter->trim) { /* @@ -386,9 +365,6 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - iter->iter0 = NULL; - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - return ITER_ERROR; return ok; } @@ -401,23 +377,18 @@ static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator_peel(iter->iter0, peeled); } -static int prefix_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void prefix_ref_iterator_release(struct ref_iterator *ref_iterator) { struct prefix_ref_iterator *iter = (struct prefix_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->iter0) - ok = ref_iterator_abort(iter->iter0); + ref_iterator_free(iter->iter0); free(iter->prefix); - base_ref_iterator_free(ref_iterator); - return ok; } static struct ref_iterator_vtable prefix_ref_iterator_vtable = { .advance = prefix_ref_iterator_advance, .peel = prefix_ref_iterator_peel, - .abort = prefix_ref_iterator_abort, + .release = prefix_ref_iterator_release, }; struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0, @@ -453,20 +424,14 @@ int do_for_each_ref_iterator(struct ref_iterator *iter, current_ref_iter = iter; while ((ok = ref_iterator_advance(iter)) == ITER_OK) { retval = fn(iter->refname, iter->referent, iter->oid, iter->flags, cb_data); - if (retval) { - /* - * If ref_iterator_abort() returns ITER_ERROR, - * we ignore that error in deference to the - * callback function's return value. - */ - ref_iterator_abort(iter); + if (retval) goto out; - } } out: current_ref_iter = old_ref_iter; if (ok == ITER_ERROR) - return -1; + retval = -1; + ref_iterator_free(iter); return retval; } diff --git a/refs/packed-backend.c b/refs/packed-backend.c index a7b6f74b6e3..38a1956d1a8 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -954,9 +954,6 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - ok = ITER_ERROR; - return ok; } @@ -976,23 +973,19 @@ static int packed_ref_iterator_peel(struct ref_iterator *ref_iterator, } } -static int packed_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void packed_ref_iterator_release(struct ref_iterator *ref_iterator) { struct packed_ref_iterator *iter = (struct packed_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - strbuf_release(&iter->refname_buf); free(iter->jump); release_snapshot(iter->snapshot); - base_ref_iterator_free(ref_iterator); - return ok; } static struct ref_iterator_vtable packed_ref_iterator_vtable = { .advance = packed_ref_iterator_advance, .peel = packed_ref_iterator_peel, - .abort = packed_ref_iterator_abort + .release = packed_ref_iterator_release, }; static int jump_list_entry_cmp(const void *va, const void *vb) @@ -1362,8 +1355,10 @@ static int write_with_updates(struct packed_ref_store *refs, */ iter = packed_ref_iterator_begin(&refs->base, "", NULL, DO_FOR_EACH_INCLUDE_BROKEN); - if ((ok = ref_iterator_advance(iter)) != ITER_OK) + if ((ok = ref_iterator_advance(iter)) != ITER_OK) { + ref_iterator_free(iter); iter = NULL; + } i = 0; @@ -1411,8 +1406,10 @@ static int write_with_updates(struct packed_ref_store *refs, * the iterator over the unneeded * value. */ - if ((ok = ref_iterator_advance(iter)) != ITER_OK) + if ((ok = ref_iterator_advance(iter)) != ITER_OK) { + ref_iterator_free(iter); iter = NULL; + } cmp = +1; } else { /* @@ -1449,8 +1446,10 @@ static int write_with_updates(struct packed_ref_store *refs, peel_error ? NULL : &peeled)) goto write_error; - if ((ok = ref_iterator_advance(iter)) != ITER_OK) + if ((ok = ref_iterator_advance(iter)) != ITER_OK) { + ref_iterator_free(iter); iter = NULL; + } } else if (is_null_oid(&update->new_oid)) { /* * The update wants to delete the reference, @@ -1499,9 +1498,7 @@ static int write_with_updates(struct packed_ref_store *refs, get_tempfile_path(refs->tempfile), strerror(errno)); error: - if (iter) - ref_iterator_abort(iter); - + ref_iterator_free(iter); delete_tempfile(&refs->tempfile); return -1; } diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 02f09e4df88..6457e02c1ea 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -409,7 +409,7 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) if (++level->index == level->dir->nr) { /* This level is exhausted; pop up a level */ if (--iter->levels_nr == 0) - return ref_iterator_abort(ref_iterator); + return ITER_DONE; continue; } @@ -452,21 +452,18 @@ static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator, return peel_object(iter->repo, ref_iterator->oid, peeled) ? -1 : 0; } -static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void cache_ref_iterator_release(struct ref_iterator *ref_iterator) { struct cache_ref_iterator *iter = (struct cache_ref_iterator *)ref_iterator; - free((char *)iter->prefix); free(iter->levels); - base_ref_iterator_free(ref_iterator); - return ITER_DONE; } static struct ref_iterator_vtable cache_ref_iterator_vtable = { .advance = cache_ref_iterator_advance, .peel = cache_ref_iterator_peel, - .abort = cache_ref_iterator_abort + .release = cache_ref_iterator_release, }; struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache, diff --git a/refs/refs-internal.h b/refs/refs-internal.h index aaab711bb96..74e2c03cef1 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -273,11 +273,11 @@ enum do_for_each_ref_flags { * the next reference and returns ITER_OK. The data pointed at by * refname and oid belong to the iterator; if you want to retain them * after calling ref_iterator_advance() again or calling - * ref_iterator_abort(), you must make a copy. When the iteration has + * ref_iterator_free(), you must make a copy. When the iteration has * been exhausted, ref_iterator_advance() releases any resources * associated with the iteration, frees the ref_iterator object, and * returns ITER_DONE. If you want to abort the iteration early, call - * ref_iterator_abort(), which also frees the ref_iterator object and + * ref_iterator_free(), which also frees the ref_iterator object and * any associated resources. If there was an internal error advancing * to the next entry, ref_iterator_advance() aborts the iteration, * frees the ref_iterator, and returns ITER_ERROR. @@ -293,7 +293,7 @@ enum do_for_each_ref_flags { * * while ((ok = ref_iterator_advance(iter)) == ITER_OK) { * if (want_to_stop_iteration()) { - * ok = ref_iterator_abort(iter); + * ok = ITER_DONE; * break; * } * @@ -307,6 +307,7 @@ enum do_for_each_ref_flags { * * if (ok != ITER_DONE) * handle_error(); + * ref_iterator_free(iter); */ struct ref_iterator { struct ref_iterator_vtable *vtable; @@ -333,12 +334,8 @@ int ref_iterator_advance(struct ref_iterator *ref_iterator); int ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled); -/* - * End the iteration before it has been exhausted, freeing the - * reference iterator and any associated resources and returning - * ITER_DONE. If the abort itself failed, return ITER_ERROR. - */ -int ref_iterator_abort(struct ref_iterator *ref_iterator); +/* Free the reference iterator and any associated resources. */ +void ref_iterator_free(struct ref_iterator *ref_iterator); /* * An iterator over nothing (its first ref_iterator_advance() call @@ -438,13 +435,6 @@ struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0, void base_ref_iterator_init(struct ref_iterator *iter, struct ref_iterator_vtable *vtable); -/* - * Base class destructor for ref_iterators. Destroy the ref_iterator - * part of iter and shallow-free the object. This is meant to be - * called only by the destructors of derived classes. - */ -void base_ref_iterator_free(struct ref_iterator *iter); - /* Virtual function declarations for ref_iterators: */ /* @@ -463,15 +453,14 @@ typedef int ref_iterator_peel_fn(struct ref_iterator *ref_iterator, /* * Implementations of this function should free any resources specific - * to the derived class, then call base_ref_iterator_free() to clean - * up and free the ref_iterator object. + * to the derived class. */ -typedef int ref_iterator_abort_fn(struct ref_iterator *ref_iterator); +typedef void ref_iterator_release_fn(struct ref_iterator *ref_iterator); struct ref_iterator_vtable { ref_iterator_advance_fn *advance; ref_iterator_peel_fn *peel; - ref_iterator_abort_fn *abort; + ref_iterator_release_fn *release; }; /* diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 2a90e7cb391..06543f79c64 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -711,17 +711,10 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) break; } - if (iter->err > 0) { - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - return ITER_ERROR; + if (iter->err > 0) return ITER_DONE; - } - - if (iter->err < 0) { - ref_iterator_abort(ref_iterator); + if (iter->err < 0) return ITER_ERROR; - } - return ITER_OK; } @@ -740,7 +733,7 @@ static int reftable_ref_iterator_peel(struct ref_iterator *ref_iterator, return -1; } -static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void reftable_ref_iterator_release(struct ref_iterator *ref_iterator) { struct reftable_ref_iterator *iter = (struct reftable_ref_iterator *)ref_iterator; @@ -751,14 +744,12 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) free(iter->exclude_patterns[i]); free(iter->exclude_patterns); } - free(iter); - return ITER_DONE; } static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .advance = reftable_ref_iterator_advance, .peel = reftable_ref_iterator_peel, - .abort = reftable_ref_iterator_abort + .release = reftable_ref_iterator_release, }; static int qsort_strcmp(const void *va, const void *vb) @@ -2017,17 +2008,10 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator) break; } - if (iter->err > 0) { - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - return ITER_ERROR; + if (iter->err > 0) return ITER_DONE; - } - - if (iter->err < 0) { - ref_iterator_abort(ref_iterator); + if (iter->err < 0) return ITER_ERROR; - } - return ITER_OK; } @@ -2038,21 +2022,19 @@ static int reftable_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSE return -1; } -static int reftable_reflog_iterator_abort(struct ref_iterator *ref_iterator) +static void reftable_reflog_iterator_release(struct ref_iterator *ref_iterator) { struct reftable_reflog_iterator *iter = (struct reftable_reflog_iterator *)ref_iterator; reftable_log_record_release(&iter->log); reftable_iterator_destroy(&iter->iter); strbuf_release(&iter->last_name); - free(iter); - return ITER_DONE; } static struct ref_iterator_vtable reftable_reflog_iterator_vtable = { .advance = reftable_reflog_iterator_advance, .peel = reftable_reflog_iterator_peel, - .abort = reftable_reflog_iterator_abort + .release = reftable_reflog_iterator_release, }; static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftable_ref_store *refs, diff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c index 6b297bd7536..8d46e8ba409 100644 --- a/t/helper/test-dir-iterator.c +++ b/t/helper/test-dir-iterator.c @@ -53,6 +53,7 @@ int cmd__dir_iterator(int argc, const char **argv) printf("(%s) [%s] %s\n", diter->relative_path, diter->basename, diter->path.buf); } + dir_iterator_free(diter); if (iter_status != ITER_DONE) { printf("dir_iterator_advance failure\n"); From patchwork Thu Mar 6 15:08:41 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004662 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 D352C210190 for ; Thu, 6 Mar 2025 15:08:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273736; cv=none; b=JbmCnLI6Vd2n/HEQnZR7gEvNZv3EbkAVK2B8Pi9j6Cvj873e2ZrjMehRKXZiCPNBEjoyqcbg4YdGLT/IZr/9wYob5Xocq1eFJS4lNDe/Kwn+e0V8cB1j7kKWBEiZmNvrt9RxsT+vuibidyFTUMnEGfkgEDG1D9bfY8do2hsIfPg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273736; c=relaxed/simple; bh=pv8ud+1MjJ9xodgqkR1kb4AuamYpEC7kMXOqprQGKcU=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=b3oT2lqSU1UZ6ahuoH7SoDvbtBhnZg5AttpVXw6Nb9loadpbXEw92M6vHplvPDKgkEL5x0ymiS3sbQwCKgi4ZUkDe+/qvGr7Hfzmccdhi5iZc4kU6cH/eMC/QuGS1KN1qquxntYF6PwZI+8b8ZbCEhEGgWc3px8bJVzxVmLNNio= 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=IymkYseg; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=WmyCEKME; arc=none smtp.client-ip=202.12.124.147 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="IymkYseg"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="WmyCEKME" Received: from phl-compute-13.internal (phl-compute-13.phl.internal [10.202.2.53]) by mailfout.stl.internal (Postfix) with ESMTP id C027911401DC; Thu, 6 Mar 2025 10:08:52 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-13.internal (MEProxy); Thu, 06 Mar 2025 10:08:52 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273732; x=1741360132; bh=vKCwJZlssfutLO7eX3AOqrMh0+EqAiVDpdgdMz3CBVQ=; b= IymkYseg4j73MXpDKWLJtQQC3gjN4kbeKTJ502Y+vj2oe9c8IeX7OSksN9XpSawP 8JWI03Op0zwO6ODLdGKJk8A5XNDy4T/Vb9pA+Wq6XtUH0vVj/qcS0tkX1I9tP7p4 MDOzYRvxeEjxKXj1PRJ1HjFvkgYXzFC097y8cefdQFsOkj2dfXnr87vSJdu9JT4G M2b4pTh/L3SF2GPO1qyKKQG37rGvizBRvppJ9O/b2yz6T7RjpYVYJd5WNufJx9lN y5TzNYtbb2seLtwfSFL1jnV9OUJ1ijaE+ZyQIJmmVVfztTa9wE71Wj0ymLVURECt 2NrulV2CCmcmTgjngPCALg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273732; x= 1741360132; bh=vKCwJZlssfutLO7eX3AOqrMh0+EqAiVDpdgdMz3CBVQ=; b=W myCEKMERV2WZLAY4EuANN9jB2qCRjD1OgOn4Ga976eaTVn9nD8BygCK2Jme2Cgxt 8I7dmb47cBOsqW2r4HfvXFsg+/e7oiygeGXc46bYv0dQgMJq0+8rVWumJB9/+TZT B2695J9AxGgC+93VJrOmEVj7fXlZHV84YpCmbpIYfzi+yoZ4AMn7tEKm9t7kALva uMReP2EnOXLkErp9dCY4HPay1p3qvEA+Nz6SZOVd7zrpjRo/x5CJlecpkf5JkHRU KR1lsDEgY8ScHI64HZKQ3y8/rnuKhwvy37Qe8zK6Xpi1t0/F1rieIyu+94/pwweu JM/2ZvsjmelGq22gjFK0g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilh ihrdhorhhgpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomhdp rhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpthhtohepshhhvg hjihgrlhhuohesghhmrghilhdrtghomhdprhgtphhtthhopehpvghffhesphgvfhhfrdhn vghtpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtth hopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:51 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id eb443f1f (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:48 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:41 +0100 Subject: [PATCH v5 10/16] refs/iterator: provide infrastructure to re-seek iterators Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-10-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Reftable iterators need to be scrapped after they have either been exhausted or aren't useful to the caller anymore, and it is explicitly not possible to reuse them for iterations. But enabling for reuse of iterators may allow us to tune them by reusing internal state of an iterator. The reftable iterators for example can already be reused internally, but we're not able to expose this to any users outside of the reftable backend. Introduce a new `.seek` function in the ref iterator vtable that allows callers to seek an iterator multiple times. It is expected to be functionally the same as calling `refs_ref_iterator_begin()` with a different (or the same) prefix. Note that it is not possible to adjust parameters other than the seeked prefix for now, so exclude patterns, trimmed prefixes and flags will remain unchanged. We do not have a usecase for changing these parameters right now, but if we ever find one we can adapt accordingly. Implement the callback for trivial cases. The other iterators will be implemented in subsequent commits. Signed-off-by: Patrick Steinhardt --- refs/debug.c | 11 +++++++++++ refs/iterator.c | 24 ++++++++++++++++++++++++ refs/refs-internal.h | 24 ++++++++++++++++++++++++ 3 files changed, 59 insertions(+) diff --git a/refs/debug.c b/refs/debug.c index a9786da4ba1..5390fa9c187 100644 --- a/refs/debug.c +++ b/refs/debug.c @@ -169,6 +169,16 @@ static int debug_ref_iterator_advance(struct ref_iterator *ref_iterator) return res; } +static int debug_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct debug_ref_iterator *diter = + (struct debug_ref_iterator *)ref_iterator; + int res = diter->iter->vtable->seek(diter->iter, prefix); + trace_printf_key(&trace_refs, "iterator_seek: %s: %d\n", prefix ? prefix : "", res); + return res; +} + static int debug_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -189,6 +199,7 @@ static void debug_ref_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable debug_ref_iterator_vtable = { .advance = debug_ref_iterator_advance, + .seek = debug_ref_iterator_seek, .peel = debug_ref_iterator_peel, .release = debug_ref_iterator_release, }; diff --git a/refs/iterator.c b/refs/iterator.c index aaeff270437..757b105261a 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -15,6 +15,12 @@ int ref_iterator_advance(struct ref_iterator *ref_iterator) return ref_iterator->vtable->advance(ref_iterator); } +int ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + return ref_iterator->vtable->seek(ref_iterator, prefix); +} + int ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -50,6 +56,12 @@ static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator UNUSED) return ITER_DONE; } +static int empty_ref_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *prefix UNUSED) +{ + return 0; +} + static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, struct object_id *peeled UNUSED) { @@ -62,6 +74,7 @@ static void empty_ref_iterator_release(struct ref_iterator *ref_iterator UNUSED) static struct ref_iterator_vtable empty_ref_iterator_vtable = { .advance = empty_ref_iterator_advance, + .seek = empty_ref_iterator_seek, .peel = empty_ref_iterator_peel, .release = empty_ref_iterator_release, }; @@ -368,6 +381,16 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) return ok; } +static int prefix_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct prefix_ref_iterator *iter = + (struct prefix_ref_iterator *)ref_iterator; + free(iter->prefix); + iter->prefix = xstrdup_or_null(prefix); + return ref_iterator_seek(iter->iter0, prefix); +} + static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -387,6 +410,7 @@ static void prefix_ref_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable prefix_ref_iterator_vtable = { .advance = prefix_ref_iterator_advance, + .seek = prefix_ref_iterator_seek, .peel = prefix_ref_iterator_peel, .release = prefix_ref_iterator_release, }; diff --git a/refs/refs-internal.h b/refs/refs-internal.h index 74e2c03cef1..8f18274a165 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -327,6 +327,22 @@ struct ref_iterator { */ int ref_iterator_advance(struct ref_iterator *ref_iterator); +/* + * Seek the iterator to the first reference with the given prefix. + * The prefix is matched as a literal string, without regard for path + * separators. If prefix is NULL or the empty string, seek the iterator to the + * first reference again. + * + * This function is expected to behave as if a new ref iterator with the same + * prefix had been created, but allows reuse of iterators and thus may allow + * the backend to optimize. Parameters other than the prefix that have been + * passed when creating the iterator will remain unchanged. + * + * Returns 0 on success, a negative error code otherwise. + */ +int ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix); + /* * If possible, peel the reference currently being viewed by the * iterator. Return 0 on success. @@ -445,6 +461,13 @@ void base_ref_iterator_init(struct ref_iterator *iter, */ typedef int ref_iterator_advance_fn(struct ref_iterator *ref_iterator); +/* + * Seek the iterator to the first reference matching the given prefix. Should + * behave the same as if a new iterator was created with the same prefix. + */ +typedef int ref_iterator_seek_fn(struct ref_iterator *ref_iterator, + const char *prefix); + /* * Peels the current ref, returning 0 for success or -1 for failure. */ @@ -459,6 +482,7 @@ typedef void ref_iterator_release_fn(struct ref_iterator *ref_iterator); struct ref_iterator_vtable { ref_iterator_advance_fn *advance; + ref_iterator_seek_fn *seek; ref_iterator_peel_fn *peel; ref_iterator_release_fn *release; }; From patchwork Thu Mar 6 15:08:42 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004660 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 C818A20E016 for ; Thu, 6 Mar 2025 15:08:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273735; cv=none; b=F26E85nUrC51c4KMe2QV+UXRtZ3HQemkaERwz4BGyjwLqY9YVoxHN9nHDUGGe6ByB9V1cIKn00/RIunc6drmzTmJOmbsxev6qudRaRI60C12zfsYiGczeXkVhMUZQuCvFsGbUemMLfAO8Q565OvOO1reVm2SO67EMj+kmzBu9rM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273735; c=relaxed/simple; bh=PR1MErk/1XGCuIs7qu1Fqh6lkyJK6Tq5J9PksgCtn8g=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=qo3qSGtsheYmpoN0JVRIulCsx3xZELOLQZhb/UnXoHgDJP56V+/ndwomzSusJA46fseSR3uwqkPLlk09I6MQYDAH65c4pf5X0yIssCMt7yhz2EkSstmgDFvcGP9TiI+pZlzq2W96V7IFBFqJTj3V1ppSc0z58/zzr7YaVQjCTyk= 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=CC6XDP8o; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=O727ChwN; arc=none smtp.client-ip=202.12.124.147 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="CC6XDP8o"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="O727ChwN" Received: from phl-compute-12.internal (phl-compute-12.phl.internal [10.202.2.52]) by mailfout.stl.internal (Postfix) with ESMTP id 0475711400C9; Thu, 6 Mar 2025 10:08:52 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-12.internal (MEProxy); Thu, 06 Mar 2025 10:08:53 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273732; x=1741360132; bh=ipS1Td7FVfRKKTDTQ5uQxSakqlyxgsFYjSxQkX/1X+Y=; b= CC6XDP8oH9hwMtTcK92ivBYRBdyE/b4WYXxnO+Q2Q1qmUBhOsIgq6QqtxzHQCWsx 5xnRJH0N0EMc6ISRQfhD+QP8bgHOKMqL94YqFLHCuKZ+bg3Um3pqewZRNkyqn0NG AVgYf+XXACtKqlqUf55o51BYCgKkvSI4koCST3ad15PHoUAD25Qd2gBxU6dIVNQB RsGT6eHboDLg+O8LNbtNGkF9u23ltwMGLf3EaND2jQsQ0wug5nUtma0h15XK9XuC el/JZ4PjY1oOFDxvC0wVz4X5sfrqsFGmydOiVPJC637pAMcTPEm+PJRKJWBOF1qe fs3cUSRopgAFciGZDthQZA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273732; x= 1741360132; bh=ipS1Td7FVfRKKTDTQ5uQxSakqlyxgsFYjSxQkX/1X+Y=; b=O 727ChwN3PvTpU+SHLxEW2QYcC3OAWFxCMFc/mg3iwm91MU5x5mduhj2r22qwXohX NtOY2wKlglpzvJiZkJK7AWCou0E5qAOoVC4Gmq+8X8WZ+pZPYYN1VEKTpwXg0tjN sRp/D7rIYkIuB9XdPBBGePYEZ2LsMBRLCQ0UAyxUJs12v7BQW/XrAKPb81/E5KRY /XMr4k8/QvrMuG6PHqj9Rhjg6pLtUgijWcUZSmuOt7SqMCZ8XtWEQz+11D1b0eA6 gybxQreJmErWu5rL6JzSSkILjXVuGj5cAT/vGR5mh1G2uzw59irnvuEmzf3K9RF+ HVv3UTTnzeI9utobBD0HA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehsrghnuggrlhhssegtrhhushhthihtohhoth hhphgrshhtvgdrnhgvthdprhgtphhtthhopehpvghffhesphgvfhhfrdhnvghtpdhrtghp thhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtthhopegthh hrihhstghoohhlsehtuhigfhgrmhhilhihrdhorhhgpdhrtghpthhtohepghhithesvhhg vghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrd gtohhmpdhrtghpthhtohepshhhvghjihgrlhhuohesghhmrghilhdrtghomh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:51 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id b7a2a87d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:49 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:42 +0100 Subject: [PATCH v5 11/16] refs/iterator: implement seeking for merged iterators Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-11-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Implement seeking on merged iterators. The implementation is rather straight forward, with the only exception that we must not deallocate the underlying iterators once they have been exhausted. Signed-off-by: Patrick Steinhardt --- refs/iterator.c | 38 +++++++++++++++++++++++++++++--------- 1 file changed, 29 insertions(+), 9 deletions(-) diff --git a/refs/iterator.c b/refs/iterator.c index 757b105261a..63608ef9907 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -96,7 +96,8 @@ int is_empty_ref_iterator(struct ref_iterator *ref_iterator) struct merge_ref_iterator { struct ref_iterator base; - struct ref_iterator *iter0, *iter1; + struct ref_iterator *iter0, *iter0_owned; + struct ref_iterator *iter1, *iter1_owned; ref_iterator_select_fn *select; void *cb_data; @@ -160,13 +161,11 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (!iter->current) { /* Initialize: advance both iterators to their first entries */ if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) { - ref_iterator_free(iter->iter0); iter->iter0 = NULL; if (ok == ITER_ERROR) goto error; } if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) { - ref_iterator_free(iter->iter1); iter->iter1 = NULL; if (ok == ITER_ERROR) goto error; @@ -177,7 +176,6 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) * entry: */ if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) { - ref_iterator_free(*iter->current); *iter->current = NULL; if (ok == ITER_ERROR) goto error; @@ -206,7 +204,6 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (selection & ITER_SKIP_SECONDARY) { if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) { - ref_iterator_free(*secondary); *secondary = NULL; if (ok == ITER_ERROR) goto error; @@ -226,6 +223,28 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_ERROR; } +static int merge_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct merge_ref_iterator *iter = + (struct merge_ref_iterator *)ref_iterator; + int ret; + + iter->current = NULL; + iter->iter0 = iter->iter0_owned; + iter->iter1 = iter->iter1_owned; + + ret = ref_iterator_seek(iter->iter0, prefix); + if (ret < 0) + return ret; + + ret = ref_iterator_seek(iter->iter1, prefix); + if (ret < 0) + return ret; + + return 0; +} + static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -242,12 +261,13 @@ static void merge_ref_iterator_release(struct ref_iterator *ref_iterator) { struct merge_ref_iterator *iter = (struct merge_ref_iterator *)ref_iterator; - ref_iterator_free(iter->iter0); - ref_iterator_free(iter->iter1); + ref_iterator_free(iter->iter0_owned); + ref_iterator_free(iter->iter1_owned); } static struct ref_iterator_vtable merge_ref_iterator_vtable = { .advance = merge_ref_iterator_advance, + .seek = merge_ref_iterator_seek, .peel = merge_ref_iterator_peel, .release = merge_ref_iterator_release, }; @@ -268,8 +288,8 @@ struct ref_iterator *merge_ref_iterator_begin( */ base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable); - iter->iter0 = iter0; - iter->iter1 = iter1; + iter->iter0 = iter->iter0_owned = iter0; + iter->iter1 = iter->iter1_owned = iter1; iter->select = select; iter->cb_data = cb_data; iter->current = NULL; From patchwork Thu Mar 6 15:08:43 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004663 Received: from fhigh-b5-smtp.messagingengine.com (fhigh-b5-smtp.messagingengine.com [202.12.124.156]) (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 62F1E20F08F for ; Thu, 6 Mar 2025 15:08:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.156 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273737; cv=none; b=LNOjXwNXhe365cDhcFgTLmIC0sG47YRDU3RyyrGONHuslMR4diR9w3SGq6Z/KD+xsBdbc/YYyQdfLvC09OKuwsnrSi7vLPqaBnkBmIPyIkvuzuPEHDn4SH1yLdECCIV2n53wC4M2re6NHSKe8vsVdzfvLegJh/OVDqbC8ZHvePc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273737; c=relaxed/simple; bh=UJNvGhux4NX9CzNSDnsHT01rFjCpiDAdonEkYb6Em6k=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=QF/swQi07IihW3txNEgVaqJBXnO4DMsQeGBcjsF6RXmLwC6K5uzz7c1DZcd4wu/LvpminL6t6hejFzC6mtIGZMi7iC4PHjhRdprRKDN9pQYU4S+kKnTepSyECcJe56DSc6ulQ95/VQxO0SGheHDS1OX0JGp/GfB4yi/8WgDAq7I= 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=ZSHphhmy; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=WtX8j0Iv; arc=none smtp.client-ip=202.12.124.156 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="ZSHphhmy"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="WtX8j0Iv" Received: from phl-compute-12.internal (phl-compute-12.phl.internal [10.202.2.52]) by mailfhigh.stl.internal (Postfix) with ESMTP id 44FF3254016F; Thu, 6 Mar 2025 10:08:54 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-12.internal (MEProxy); Thu, 06 Mar 2025 10:08:54 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273734; x=1741360134; bh=nNm0S+yS2lk8rd7nCGb527Lalq91mMEYhFqgFYfYwuE=; b= ZSHphhmy5zadken4pP+QTtqqBu9CAupfFx/K9hcNfrrGUXITCjj0DHIu8jMFRhsK hi0jKxZPnVir1m1DHbbsCokKCaPrbXy8CPFuRoKcL+CTPHq3phf4uqfiruMGl4ZG B9UsT4YWmtUSax2QSUD+59QT/ZYeazIPrkH06n+K94+nl6rciOIL6y+BRz12iqGv +o5ikqud8pOOcTutO9PISJjupD5MfOP9w/QsZbbYFCY7BF1m2rorhEIo1nY9iWQV 6N8YJjhqEvtXZpnksJhwjx6KRtQUOJMsrrOuXXjtRTxtJRiKIjBabjqQhe1NN0wQ 2lSKXbpw/ltfIZ7MclMH7Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273734; x= 1741360134; bh=nNm0S+yS2lk8rd7nCGb527Lalq91mMEYhFqgFYfYwuE=; b=W tX8j0IvpOkXnf816wyEZkzKb3D1+0eM7VZdo5gxj6Ejs/aJ3ua5T43jlwVsLfnOh 9h8I8VPPCfwrnYQBrvjLBXo1BbwyvgeTvzyOIQblGhgWUwgZGOCyti2kIqmDCFys vnTyLDaRhzy4u0hlG5CmSNKGc5SgL+euiz3RAz6K/25xQCbEDsOgrmYkbE7qO/HD Rs5er5ovueOCKVfwnQHZ4bwu5TTOLOBM48QTpXnheYj5wMbUjxQaxQw6gE3305Ou ltB8zXWYoSr6WkDNTS3xHwRU5RdXXKwr5VOpnAhJk4C9Jw9fCbm0r4nZvRYfrtdJ RaDQtnsq+UYCryVXws2Uw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedvnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrd gtohhmpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidrohhrghdp rhgtphhtthhopehpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtohepghhithhsthgvrh esphhosghogidrtghomhdprhgtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdho rhhgpdhrtghpthhtohepshhhvghjihgrlhhuohesghhmrghilhdrtghomhdprhgtphhtth hopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:52 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 29bb12c6 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:50 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:43 +0100 Subject: [PATCH v5 12/16] refs/iterator: implement seeking for reftable iterators Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-12-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Implement seeking of reftable iterators. As the low-level reftable iterators already support seeking this change is straight-forward. Two notes though: - We do not support seeking on reflog iterators. It is unclear what seeking would even look like in this context, as you typically would want to seek to a specific entry in the reflog for a specific ref. There is currently no use case for this, but if one arises in the future, we can still implement seeking at that later point. - We start to check whether `reftable_stack_init_ref_iterator()` is successful. Signed-off-by: Patrick Steinhardt --- refs/reftable-backend.c | 35 ++++++++++++++++++++++++++++++----- 1 file changed, 30 insertions(+), 5 deletions(-) diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 06543f79c64..b0c09f34433 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -547,7 +547,7 @@ struct reftable_ref_iterator { struct reftable_ref_record ref; struct object_id oid; - const char *prefix; + char *prefix; size_t prefix_len; char **exclude_patterns; size_t exclude_patterns_index; @@ -718,6 +718,20 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } +static int reftable_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct reftable_ref_iterator *iter = + (struct reftable_ref_iterator *)ref_iterator; + + free(iter->prefix); + iter->prefix = xstrdup_or_null(prefix); + iter->prefix_len = prefix ? strlen(prefix) : 0; + iter->err = reftable_iterator_seek_ref(&iter->iter, prefix); + + return iter->err; +} + static int reftable_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -744,10 +758,12 @@ static void reftable_ref_iterator_release(struct ref_iterator *ref_iterator) free(iter->exclude_patterns[i]); free(iter->exclude_patterns); } + free(iter->prefix); } static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .advance = reftable_ref_iterator_advance, + .seek = reftable_ref_iterator_seek, .peel = reftable_ref_iterator_peel, .release = reftable_ref_iterator_release, }; @@ -806,8 +822,6 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ iter = xcalloc(1, sizeof(*iter)); base_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable); - iter->prefix = prefix; - iter->prefix_len = prefix ? strlen(prefix) : 0; iter->base.oid = &iter->oid; iter->flags = flags; iter->refs = refs; @@ -821,8 +835,11 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ if (ret) goto done; - reftable_stack_init_ref_iterator(stack, &iter->iter); - ret = reftable_iterator_seek_ref(&iter->iter, prefix); + ret = reftable_stack_init_ref_iterator(stack, &iter->iter); + if (ret) + goto done; + + ret = reftable_ref_iterator_seek(&iter->base, prefix); if (ret) goto done; @@ -2015,6 +2032,13 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } +static int reftable_reflog_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *prefix UNUSED) +{ + BUG("reftable reflog iterator cannot be seeked"); + return -1; +} + static int reftable_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSED, struct object_id *peeled UNUSED) { @@ -2033,6 +2057,7 @@ static void reftable_reflog_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable reftable_reflog_iterator_vtable = { .advance = reftable_reflog_iterator_advance, + .seek = reftable_reflog_iterator_seek, .peel = reftable_reflog_iterator_peel, .release = reftable_reflog_iterator_release, }; From patchwork Thu Mar 6 15:08:44 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004665 Received: from fhigh-b5-smtp.messagingengine.com (fhigh-b5-smtp.messagingengine.com [202.12.124.156]) (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 CEC94210F65 for ; Thu, 6 Mar 2025 15:08:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.156 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273737; cv=none; b=Wp9LZXwQhc8Eqr1tAHp8eCJQWRPrM7YkHH4SApXdAz7tMw+PKDCDOdoISsWxFltQ7q2be6ZRePY2LvZI6lvtt4Qz5/Q5AB4eSFFxyGzWmRw1FqdbfnMQTDqdIKVaZN4sUJ17ET0tf/DEIjt6/ygcGM1u3VQk+dWu3wCFtDrwL3I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273737; c=relaxed/simple; bh=OqPafakSv32e9G4369dEmfUM5koTXIHwGg3I9+vFWf0=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=N8pHufOwXU5hr0mBBXkiWaLDi3hRNlHB1rQ2CxlHTEI0Yog+5bWqedw0n6nfreBjfxHFx/aFRYG6H2HGLRvFkwNZgIpQiBurt+exiqVyloBEHRonGU9XohmSDh0hTqvPiWIYl3a41lh7kEGL/Yl6sFfDb/Y1JXXuiS8ZHs++S7M= 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=GD1m9KpR; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=U9QHpsDg; arc=none smtp.client-ip=202.12.124.156 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="GD1m9KpR"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="U9QHpsDg" Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfhigh.stl.internal (Postfix) with ESMTP id CA29D25401EE; Thu, 6 Mar 2025 10:08:54 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-05.internal (MEProxy); Thu, 06 Mar 2025 10:08:55 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273734; x=1741360134; bh=HvBKrHKNrexVTshHCEMMlQI0RjCgScPNH7mho0HcgjU=; b= GD1m9KpRrcsng7Q+nWzbZlFBBRrmp7GMXMsYBz9rQ+8IJzZNNyxMid7HrEPlGB8T 49WYF0F89VjVjc9Aya9c+11T7gfDfbLR1Ad3rfLDoBDvTfBPKnNpnn3d36Am3m1R hUjicFeijF80HEJppNS/XVNxTiMKHEucZMnyFWVA8XNOFwDQQxnkzwyZqd3ye5BY 72M+4Gr+fHJ8e30T2ctPcdWP+pbdM1Xd0Q7SbfsUmRgbqoPFLG2Mk8DP2mEotdk2 HVdUG3V0Yvk4r5tBZGYevjOIAnskmrHIvYFDiGKEC8gbENpN/AuUaPJDunRaFGfk enl1tjEAK12Zb8u6TwULeg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273734; x= 1741360134; bh=HvBKrHKNrexVTshHCEMMlQI0RjCgScPNH7mho0HcgjU=; b=U 9QHpsDghdFYejCclM70RP6Evyj6q/cPgFWu0eugNkzZar7lkZu5TQpAQcWlviKj1 PjZ+M/aCLJRqNm/sgrLLUNsiui1yvZLoVjO2t6NxsM1yC3EWfxjJFhgZXrMidhxZ 2Cbgq+FOiVIjUymj7SrBz02BkiWxkHMxYvjY/x4jqf0X4+FiW2HXSdeGAYLGE8q4 yrQ57MCGTQYiYisUPiJ3wJZTWmTOJjbp3isu0xuQdCS/tEHd4vP9IJ5l1FuQavUE PDNWjbqv2qPRcs/mn377roEpTsd987OLZQxL0yWYjh55EfNm/HAVauJDLZIexn5E pxaCM6CNSQMsk5zmHnD/Q== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedvnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrd gtohhmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphht thhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpthhtohepshhhvghjihgrlh huohesghhmrghilhdrtghomhdprhgtphhtthhopehpvghffhesphgvfhhfrdhnvghtpdhr tghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghsthgvrdhnvghtpd hrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:53 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id f3825876 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:51 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:44 +0100 Subject: [PATCH v5 13/16] refs/iterator: implement seeking for ref-cache iterators Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-13-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Implement seeking of ref-cache iterators. This is done by splitting most of the logic to seek iterators out of `cache_ref_iterator_begin()` and putting it into `cache_ref_iterator_seek()` so that we can reuse the logic. Note that we cannot use the optimization anymore where we return an empty ref iterator when there aren't any references, as otherwise it wouldn't be possible to reseek the iterator to a different prefix that may exist. This shouldn't be much of a performance concern though as we now start to bail out early in case `advance()` sees that there are no more directories to be searched. Signed-off-by: Patrick Steinhardt --- refs/ref-cache.c | 79 ++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 51 insertions(+), 28 deletions(-) diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 6457e02c1ea..c1f1bab1d50 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -362,9 +362,7 @@ struct cache_ref_iterator { struct ref_iterator base; /* - * The number of levels currently on the stack. This is always - * at least 1, because when it becomes zero the iteration is - * ended and this struct is freed. + * The number of levels currently on the stack. */ size_t levels_nr; @@ -376,7 +374,7 @@ struct cache_ref_iterator { * The prefix is matched textually, without regard for path * component boundaries. */ - const char *prefix; + char *prefix; /* * A stack of levels. levels[0] is the uppermost level that is @@ -389,6 +387,9 @@ struct cache_ref_iterator { struct cache_ref_iterator_level *levels; struct repository *repo; + struct ref_cache *cache; + + int prime_dir; }; static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) @@ -396,6 +397,9 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) struct cache_ref_iterator *iter = (struct cache_ref_iterator *)ref_iterator; + if (!iter->levels_nr) + return ITER_DONE; + while (1) { struct cache_ref_iterator_level *level = &iter->levels[iter->levels_nr - 1]; @@ -444,6 +448,41 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) } } +static int cache_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct cache_ref_iterator *iter = + (struct cache_ref_iterator *)ref_iterator; + struct cache_ref_iterator_level *level; + struct ref_dir *dir; + + dir = get_ref_dir(iter->cache->root); + if (prefix && *prefix) + dir = find_containing_dir(dir, prefix); + if (!dir) { + iter->levels_nr = 0; + return 0; + } + + if (iter->prime_dir) + prime_ref_dir(dir, prefix); + iter->levels_nr = 1; + level = &iter->levels[0]; + level->index = -1; + level->dir = dir; + + if (prefix && *prefix) { + free(iter->prefix); + iter->prefix = xstrdup(prefix); + level->prefix_state = PREFIX_WITHIN_DIR; + } else { + FREE_AND_NULL(iter->prefix); + level->prefix_state = PREFIX_CONTAINS_DIR; + } + + return 0; +} + static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -456,12 +495,13 @@ static void cache_ref_iterator_release(struct ref_iterator *ref_iterator) { struct cache_ref_iterator *iter = (struct cache_ref_iterator *)ref_iterator; - free((char *)iter->prefix); + free(iter->prefix); free(iter->levels); } static struct ref_iterator_vtable cache_ref_iterator_vtable = { .advance = cache_ref_iterator_advance, + .seek = cache_ref_iterator_seek, .peel = cache_ref_iterator_peel, .release = cache_ref_iterator_release, }; @@ -471,39 +511,22 @@ struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache, struct repository *repo, int prime_dir) { - struct ref_dir *dir; struct cache_ref_iterator *iter; struct ref_iterator *ref_iterator; - struct cache_ref_iterator_level *level; - - dir = get_ref_dir(cache->root); - if (prefix && *prefix) - dir = find_containing_dir(dir, prefix); - if (!dir) - /* There's nothing to iterate over. */ - return empty_ref_iterator_begin(); - - if (prime_dir) - prime_ref_dir(dir, prefix); CALLOC_ARRAY(iter, 1); ref_iterator = &iter->base; base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable); ALLOC_GROW(iter->levels, 10, iter->levels_alloc); - iter->levels_nr = 1; - level = &iter->levels[0]; - level->index = -1; - level->dir = dir; + iter->repo = repo; + iter->cache = cache; + iter->prime_dir = prime_dir; - if (prefix && *prefix) { - iter->prefix = xstrdup(prefix); - level->prefix_state = PREFIX_WITHIN_DIR; - } else { - level->prefix_state = PREFIX_CONTAINS_DIR; + if (cache_ref_iterator_seek(&iter->base, prefix) < 0) { + ref_iterator_free(&iter->base); + return NULL; } - iter->repo = repo; - return ref_iterator; } From patchwork Thu Mar 6 15:08:45 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004664 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 0C39121128A for ; Thu, 6 Mar 2025 15:08:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273737; cv=none; b=s0XEDW8kZunTwBJ1IHJXtJYTfFNYEY4jGQI64N2RUMAvyk7eEAR0DoS1S0hwriKIEYZr5AdS46b3PmrpcizDaoTZLq+1qR90SZJLPyAoYY+0bcOBMewSgP3LnV7URY9/6RZTOggvuseWoAbNjw6Z6iAWwtWn1EotZ5Y7xbhL0uE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273737; c=relaxed/simple; bh=eQktM5kWYkU1TcxRbzAgYV4CH7VOl5+KWlP987rQLIc=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=A3BxvBQjN15SXM4UazW0RJnYt10fxn9XqXjW0g0yF45ZbcMeo/J94M+88T10Hw9aXPZUW58GMabdwBbd9ONLx6z6q/8DISzyxdPxK6clyw6EOFLvvIlaAr/OY5FV1vPuQGZ3z5jS7PBAznLAxDRIyDKG/BpUCOkInmfkJkiskyk= 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=YyreXh3p; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=CnFvrG01; arc=none smtp.client-ip=202.12.124.147 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="YyreXh3p"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="CnFvrG01" Received: from phl-compute-11.internal (phl-compute-11.phl.internal [10.202.2.51]) by mailfout.stl.internal (Postfix) with ESMTP id 2628311401E2; Thu, 6 Mar 2025 10:08:55 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-11.internal (MEProxy); Thu, 06 Mar 2025 10:08:55 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273735; x=1741360135; bh=B2sr2MMIvTkvlsPTzK24wVsW3b7XhDVvulJDMqJOMPo=; b= YyreXh3pydP2nDRVzRvhRTbjL/4wizZ84e8doSnhQlWtsaxW4YiTv+2bAMWO/GDJ bNgunAVMtebwsSSdy/xrLqcnvL/sKZw3k9kZKt0+43cMoaiqM7P+8eeH2OhZ62OK D3T0Xb6+lUktCdG28fsT1l9THFWl8Waq1XeDZn+rrzANaytwfzChUuApkxrnvDW5 DfdA/4ZMNJ/TSqSqxgJvWuMv9/dSM7jsQYydVj59GJi0UpnipNInnS40at/DQMJ7 GiVw1Va+hy5DITr+vIKHpMGpkjG4tlMP0ojcNk786nKfSp3Zt8h+foH9ig334UxI gBAIu8nrOoIW6GQj1M6Yug== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273735; x= 1741360135; bh=B2sr2MMIvTkvlsPTzK24wVsW3b7XhDVvulJDMqJOMPo=; b=C nFvrG01N9hCbR/d/BbaX4UWz55lBTcDoF3y0toyotMckODt7MQKZa+a92aZcAh5s Ua4/5WyljI4jpvtry+rUXM9i0Imkh8VajHphcQiM2y7CVN2wU57C/Gafo3VKJybh EtX9ONl9U6PikDxgJ4slG6QbsihWtxMT/XUsa3lZGoXGtJThb6Rwp8lGUSGhDvbJ FX61d9On6kRvDSsQ+gkLyaRTZ6RJGdnw6BQLLYfhGYkbsL+jgHOW1GYC1I8U6B4c OYYoU3Z4JrweD8C8rPSWSL0E6xoWTNu26YZcE3wZ8Py3jpsjXBVqiJDDRrF1+MOW sdi7pDIv40NFWjfZT6uIw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehshhgvjhhirghluhhosehgmhgrihhlrdgtoh hmpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprhgtphhtthhopehk rghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohepshgrnhgurghlsh estghruhhsthihthhoohhthhhprghsthgvrdhnvghtpdhrtghpthhtoheptghhrhhishgt ohholhesthhugihfrghmihhlhidrohhrghdprhgtphhtthhopehpvghffhesphgvfhhfrd hnvghtpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:53 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id e4d51737 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:52 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:45 +0100 Subject: [PATCH v5 14/16] refs/iterator: implement seeking for packed-ref iterators Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-14-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Implement seeking of `packed-ref` iterators. The implementation is again straight forward, except that we cannot continue to use the prefix iterator as we would otherwise not be able to reseek the iterator anymore in case one first asks for an empty and then for a non-empty prefix. Instead, we open-code the logic to in `advance()`. Signed-off-by: Patrick Steinhardt --- refs/packed-backend.c | 65 ++++++++++++++++++++++++++++++++++----------------- 1 file changed, 43 insertions(+), 22 deletions(-) diff --git a/refs/packed-backend.c b/refs/packed-backend.c index 38a1956d1a8..f4c82ba2c7d 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -819,6 +819,8 @@ struct packed_ref_iterator { struct snapshot *snapshot; + char *prefix; + /* The current position in the snapshot's buffer: */ const char *pos; @@ -841,11 +843,9 @@ struct packed_ref_iterator { }; /* - * Move the iterator to the next record in the snapshot, without - * respect for whether the record is actually required by the current - * iteration. Adjust the fields in `iter` and return `ITER_OK` or - * `ITER_DONE`. This function does not free the iterator in the case - * of `ITER_DONE`. + * Move the iterator to the next record in the snapshot. Adjust the fields in + * `iter` and return `ITER_OK` or `ITER_DONE`. This function does not free the + * iterator in the case of `ITER_DONE`. */ static int next_record(struct packed_ref_iterator *iter) { @@ -942,6 +942,9 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) int ok; while ((ok = next_record(iter)) == ITER_OK) { + const char *refname = iter->base.refname; + const char *prefix = iter->prefix; + if (iter->flags & DO_FOR_EACH_PER_WORKTREE_ONLY && !is_per_worktree_ref(iter->base.refname)) continue; @@ -951,12 +954,41 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) &iter->oid, iter->flags)) continue; + while (prefix && *prefix) { + if (*refname < *prefix) + BUG("packed-refs backend yielded reference preceding its prefix"); + else if (*refname > *prefix) + return ITER_DONE; + prefix++; + refname++; + } + return ITER_OK; } return ok; } +static int packed_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct packed_ref_iterator *iter = + (struct packed_ref_iterator *)ref_iterator; + const char *start; + + if (prefix && *prefix) + start = find_reference_location(iter->snapshot, prefix, 0); + else + start = iter->snapshot->start; + + free(iter->prefix); + iter->prefix = xstrdup_or_null(prefix); + iter->pos = start; + iter->eof = iter->snapshot->eof; + + return 0; +} + static int packed_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -979,11 +1011,13 @@ static void packed_ref_iterator_release(struct ref_iterator *ref_iterator) (struct packed_ref_iterator *)ref_iterator; strbuf_release(&iter->refname_buf); free(iter->jump); + free(iter->prefix); release_snapshot(iter->snapshot); } static struct ref_iterator_vtable packed_ref_iterator_vtable = { .advance = packed_ref_iterator_advance, + .seek = packed_ref_iterator_seek, .peel = packed_ref_iterator_peel, .release = packed_ref_iterator_release, }; @@ -1097,7 +1131,6 @@ static struct ref_iterator *packed_ref_iterator_begin( { struct packed_ref_store *refs; struct snapshot *snapshot; - const char *start; struct packed_ref_iterator *iter; struct ref_iterator *ref_iterator; unsigned int required_flags = REF_STORE_READ; @@ -1113,14 +1146,6 @@ static struct ref_iterator *packed_ref_iterator_begin( */ snapshot = get_snapshot(refs); - if (prefix && *prefix) - start = find_reference_location(snapshot, prefix, 0); - else - start = snapshot->start; - - if (start == snapshot->eof) - return empty_ref_iterator_begin(); - CALLOC_ARRAY(iter, 1); ref_iterator = &iter->base; base_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable); @@ -1130,19 +1155,15 @@ static struct ref_iterator *packed_ref_iterator_begin( iter->snapshot = snapshot; acquire_snapshot(snapshot); - - iter->pos = start; - iter->eof = snapshot->eof; strbuf_init(&iter->refname_buf, 0); - iter->base.oid = &iter->oid; - iter->repo = ref_store->repo; iter->flags = flags; - if (prefix && *prefix) - /* Stop iteration after we've gone *past* prefix: */ - ref_iterator = prefix_ref_iterator_begin(ref_iterator, prefix, 0); + if (packed_ref_iterator_seek(&iter->base, prefix) < 0) { + ref_iterator_free(&iter->base); + return NULL; + } return ref_iterator; } From patchwork Thu Mar 6 15:08:46 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004666 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 3F6E620E016 for ; Thu, 6 Mar 2025 15:08:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273738; cv=none; b=AaFSg5BN+xRdEVR3XFR0hrDI/9y6GgTDllKaTmz4vPoRC1r6GTT4AoFJxC8NoRyoWD5DYn3wtJzO6bG9ZxuLkU/UilBhNDBZhrZUSNcSvsr1GkBXVPOA7X3zupOZYq2pZaJfmKvR5Mj9oVz6w/plH/pyzGgb9Bp9ei2UrljRQ1w= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273738; c=relaxed/simple; bh=dDB5ene1M2tyA9QtQHJvkIk+ykfX85KsYEu1fBFoXqE=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=b60uCR6ly0GzzxD6KlWWvnIktxIXLODIYdb/yVEf4a4zo1FwsjgX0L94j0WL6e5HT4iRS2i2uqjdKeW97rwjJ8dRSkA4poHX0RuYHD5lQWRdmEbW5DGz/HoBIxBv9Gxwf7iptW3dF2ZE/kCxLDLPEzNBrzI20RbgjBgjPNgkmC8= 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=A7sumibP; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=qE9377y8; arc=none smtp.client-ip=202.12.124.147 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="A7sumibP"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="qE9377y8" Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfout.stl.internal (Postfix) with ESMTP id 4891D11401E0; Thu, 6 Mar 2025 10:08:56 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-05.internal (MEProxy); Thu, 06 Mar 2025 10:08:56 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273736; x=1741360136; bh=W/CICbvvl1qwG0o85IrKeqoAktjxwGQP+8+LnUBJYN8=; b= A7sumibPgGL4QHUtyJdR4CIrd7YZTxwb0+mTpvLBNvP3zH1NtI3pZjhu9K/e8SJk aKb4oyNimI1rZNnJwjUlqou/CGlzuRposC0N2AM2jV+5Ddr9U5KLgAHWJ5ER/Aac 4kLMsDTDClHAHnyBnADXlbUdp8azT1QElYHk2ya+mYMT5nDvJseRLa+9L3aK9TcZ epiyxuoCVEnfvMBgKj4Adxn7IQ8f3CbrcGP+8vuAlsiQriHVWZqmWFOZk+eq5RXE zYuiQKB7PfvnevbzxcQtmAvAwQOrKatseozpY/t9mwxLCmgDFKK+0fmgGM2oquaK 4ZGJy3QGGX38oVS0pK0Pzw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273736; x= 1741360136; bh=W/CICbvvl1qwG0o85IrKeqoAktjxwGQP+8+LnUBJYN8=; b=q E9377y8ywejjQC++cSotQckrWK0+PT0CbX9al9vFMVdy1GKTP4+/j1En+A+XccC/ lcaPFAmxhzme/5Vrv8otEHlY464s2ggGfBRoXwipTo2UPLt5MvASHC9Ye+ohk2g/ v3y6HugC+O6wAcVY7S8TF76RgjgOOehu9qFBSUI0HiRYGIojTE6wqMnuLTwpY1Jy KV/pOsZ9vYR/7fPns0GlOV0tijXzp/RdFqRqNLFmrLbUzDBTu50kJRPkWzCMvJ4H 5DCi9TJOBNnWwCzC/p4nvJrj/XG/QFkq2uXkISENtzDw8j9w3Y3++g1wY/dxR7dk Dxx/q7ZHwQkCxuEo7raIQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtjeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeffueeiudejvdekheeuvdekfeffiedvueelteek udehjeetkeegvddugfdtgfeileenucevlhhushhtvghrufhiiigvpedvnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorh hgpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghsthgvrdhn vghtpdhrtghpthhtohepshhhvghjihgrlhhuohesghhmrghilhdrtghomhdprhgtphhtth hopehpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtoheptghhrhhishgtohholhesthhu gihfrghmihhlhidrohhrghdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtoh hmpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:54 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 626de277 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:53 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:46 +0100 Subject: [PATCH v5 15/16] refs/iterator: implement seeking for files iterators Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-15-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 Implement seeking for "files" iterators. As we simply use a ref-cache iterator under the hood the implementation is straight-forward. Note that we do not implement seeking on reflog iterators, same as with the "reftable" backend. Signed-off-by: Patrick Steinhardt --- refs/files-backend.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/refs/files-backend.c b/refs/files-backend.c index 859f1c11941..4e1c50fead3 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -918,6 +918,14 @@ static int files_ref_iterator_advance(struct ref_iterator *ref_iterator) return ok; } +static int files_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct files_ref_iterator *iter = + (struct files_ref_iterator *)ref_iterator; + return ref_iterator_seek(iter->iter0, prefix); +} + static int files_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -936,6 +944,7 @@ static void files_ref_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable files_ref_iterator_vtable = { .advance = files_ref_iterator_advance, + .seek = files_ref_iterator_seek, .peel = files_ref_iterator_peel, .release = files_ref_iterator_release, }; @@ -2294,6 +2303,12 @@ static int files_reflog_iterator_advance(struct ref_iterator *ref_iterator) return ok; } +static int files_reflog_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *prefix UNUSED) +{ + BUG("ref_iterator_seek() called for reflog_iterator"); +} + static int files_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSED, struct object_id *peeled UNUSED) { @@ -2309,6 +2324,7 @@ static void files_reflog_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable files_reflog_iterator_vtable = { .advance = files_reflog_iterator_advance, + .seek = files_reflog_iterator_seek, .peel = files_reflog_iterator_peel, .release = files_reflog_iterator_release, }; From patchwork Thu Mar 6 15:08:47 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 14004667 Received: from fout-b4-smtp.messagingengine.com (fout-b4-smtp.messagingengine.com [202.12.124.147]) (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 B838B2116FB for ; Thu, 6 Mar 2025 15:08:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.147 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273739; cv=none; b=ojHhrAxt9hNH5VvZv2B7pOIKLrGa6mpaDuAV1OL5/SXgYu98fMD/Nc2I+VSi3TtbEzbxwDwVHd7rv7nh48urghSi8wrh0fT0MC3bZT0muWIIQj71i1gnp78KKgVLF50F3XVTVYoS+ThOUPk5GuKKt5NJWTXxFfNR73t8QVJ3tZU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741273739; c=relaxed/simple; bh=EIUWgnF6nPkecTSJyHi4Lgk+3OGi40/RNEs5Ej9rMOM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=p0IvnLxzq5YivyNoa8hhkURCfRP6ePl5sOkTDXFD3bDyv2OVNpB/3V1RXslSesjnikkh5DEp4Z2pDBa7wllih/MwkQF7pGLMrGu0Ie0EflwsShY9A1Xns3//D9kX1xhYLxdx9fgPtfK9e/K1e7QUV9M5Ih+b5DLeqkF9jb8vBjU= 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=RIYRbkbD; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=FDJPsZ5O; arc=none smtp.client-ip=202.12.124.147 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="RIYRbkbD"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="FDJPsZ5O" Received: from phl-compute-09.internal (phl-compute-09.phl.internal [10.202.2.49]) by mailfout.stl.internal (Postfix) with ESMTP id C118B11401E3; Thu, 6 Mar 2025 10:08:56 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-09.internal (MEProxy); Thu, 06 Mar 2025 10:08:56 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-transfer-encoding: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=1741273736; x=1741360136; bh=CHW07G9lowZ+RQKpucrknjTSmezbfl09mEXkRp5IoDo=; b= RIYRbkbDHKd481UqtLh2a4dEeW8JI28ne1nrn93ppJ+sxcX0HMqKZPNxcnrJLaBm A51XgWLbV+C/B1wHuqOmoOtNGTql2ayICaiMuibFR972+NVyH2o8eX/9fxk/yRVc jwIZCn3gKVK2V9DHU3g4rWShAovd7oftgyWI4LR4jgcWxgBClSFITWlz7uZbv/zf IEzmNRGy9WnlupDRbds/7ickWuNgRQS7MxCZAW4FF3sLUuNa05rYyrCfYd7h2PJ1 9c+b8hn5kfzAq56PW8phnNYld/tWDCldLRXoa2Z7FcB5MrAS+y1Y2ejK+aRlwTzN jr6w8Q+uEl0lVAC0bys/7A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :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-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741273736; x= 1741360136; bh=CHW07G9lowZ+RQKpucrknjTSmezbfl09mEXkRp5IoDo=; b=F DJPsZ5O/9n6wE5sjec5dBF3l7qm8jDoASNaAGvg6QRVpGtlmNlA/Af5XPRen8Xfl w0Id6pQLxEQ6KIfLqVQMgzR30f95zEkyKzH97YFbuVhPhSCdmWTlTth6DT/FGo94 l5P0VKdI2xcLYxn8mGG3qCawxgBVugjZV96BrCbLifduxZAQNl/4OhCpL/8hqPbB U1FitAbtXDlY4AofH7FM77mjaCadFR9zO3LEKeYV5FySKZrgSkAw6G0YMssZLt0o /OaeiUw8uUSlyrFcG+LffwuVkeFLyz4lV8Eba+Bq8pxUpX276U3suK8Bwbnsnpf+ sx5KyFq/iBENDDoo6kAPA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddutdektdelucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhephfffufggtgfgkfhfjgfvvefosehtkeertder tdejnecuhfhrohhmpefrrghtrhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhksh drihhmqeenucggtffrrghtthgvrhhnpeefhfeugeelheefjeektdffhedvhfdvteefgfdt udffudevveetgeeuuedtkefhgeenucevlhhushhtvghrufhiiigvpedvnecurfgrrhgrmh epmhgrihhlfhhrohhmpehpshesphhkshdrihhmpdhnsggprhgtphhtthhopeejpdhmohgu vgepshhmthhpohhuthdprhgtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorh hgpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidrohhrghdprhgt phhtthhopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvthdprh gtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpthhtohepkhgrrhht hhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtthhopehshhgvjhhirghluhhose hgmhgrihhlrdgtohhmpdhrtghpthhtohepphgvfhhfsehpvghffhdrnhgvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 6 Mar 2025 10:08:55 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 74a449b1 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 6 Mar 2025 15:08:54 +0000 (UTC) From: Patrick Steinhardt Date: Thu, 06 Mar 2025 16:08:47 +0100 Subject: [PATCH v5 16/16] refs: reuse iterators when determining refname availability Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250306-pks-update-ref-optimization-v5-16-dcb2ee037e97@pks.im> References: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> In-Reply-To: <20250306-pks-update-ref-optimization-v5-0-dcb2ee037e97@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , shejialuo , Christian Couder X-Mailer: b4 0.14.2 When verifying whether refnames are available we have to verify whether any reference exists that is nested under the current reference. E.g. given a reference "refs/heads/foo", we must make sure that there is no other reference "refs/heads/foo/*". This check is performed using a ref iterator with the prefix set to the nested reference namespace. Until now it used to not be possible to reseek iterators, so we always had to reallocate the iterator for every single reference we're about to check. This keeps us from reusing state that the iterator may have and that may make it work more efficiently. Refactor the logic to reseek iterators. This leads to a sizeable speedup with the "reftable" backend: Benchmark 1: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~) Time (mean ± σ): 39.8 ms ± 0.9 ms [User: 29.7 ms, System: 9.8 ms] Range (min … max): 38.4 ms … 42.0 ms 62 runs Benchmark 2: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) Time (mean ± σ): 31.9 ms ± 1.1 ms [User: 27.0 ms, System: 4.5 ms] Range (min … max): 29.8 ms … 34.3 ms 74 runs Summary update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) ran 1.25 ± 0.05 times faster than update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~) The "files" backend doesn't really show a huge impact: Benchmark 1: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD~) Time (mean ± σ): 392.3 ms ± 7.1 ms [User: 59.7 ms, System: 328.8 ms] Range (min … max): 384.6 ms … 404.5 ms 10 runs Benchmark 2: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) Time (mean ± σ): 387.7 ms ± 7.4 ms [User: 54.6 ms, System: 329.6 ms] Range (min … max): 377.0 ms … 397.7 ms 10 runs Summary update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) ran 1.01 ± 0.03 times faster than update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD~) This is mostly because it is way slower to begin with because it has to create a separate file for each new reference, so the milliseconds we shave off by reseeking the iterator doesn't really translate into a significant relative improvement. Signed-off-by: Patrick Steinhardt --- refs.c | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/refs.c b/refs.c index 8eff60a2186..6cbb9decdb0 100644 --- a/refs.c +++ b/refs.c @@ -2555,8 +2555,13 @@ int refs_verify_refnames_available(struct ref_store *refs, if (!initial_transaction) { int ok; - iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, - DO_FOR_EACH_INCLUDE_BROKEN); + if (!iter) { + iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, + DO_FOR_EACH_INCLUDE_BROKEN); + } else if (ref_iterator_seek(iter, dirname.buf) < 0) { + goto cleanup; + } + while ((ok = ref_iterator_advance(iter)) == ITER_OK) { if (skip && string_list_has_string(skip, iter->refname)) @@ -2569,9 +2574,6 @@ int refs_verify_refnames_available(struct ref_store *refs, if (ok != ITER_DONE) BUG("error while iterating over references"); - - ref_iterator_free(iter); - iter = NULL; } extra_refname = find_descendant_ref(dirname.buf, extras, skip);