From patchwork Mon Feb 17 15:50:15 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978093 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 350C9231CA5 for ; Mon, 17 Feb 2025 15:50:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807430; cv=none; b=drGZGbzFE+D4wHrJ7xhk1uR3LWAo6QYvS1N4aCOU5afqwIFjXhHBA6WEbvEdJ6LEXijLsMUvPbxUl8QIgp3mlg9SinbhxKqhiuzljGEU79UEA7JPYR/oSQsaA/+Wj4kpWh/P/eOP80e67xqPMqZLTELY3lejrCYv0DlLOiwCF5g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807430; c=relaxed/simple; bh=dTaVVldAkYLADkQpViT4TnkFPa/9dHQTVO7Oxahz6ck=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=JrigzJP323lW/Hw0a0zqHtXJZ47GeA3IQB3/Yy0E9rn8T0myQwrkAlaRAIdq6IKCVky6sTQCpcnd6f/Oq8o+gv9ojRqu98cenMiwC4HYTwxnLVSPnADp/WOh+K7N4626tEu20Qx2pb9uTxrIqTpElz+mUoWASkTJFbc+13Uq4wA= 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=hke8xlxb; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=b/2T4Qg9; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="hke8xlxb"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="b/2T4Qg9" Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfout.stl.internal (Postfix) with ESMTP id 39B821140185; Mon, 17 Feb 2025 10:50:27 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-05.internal (MEProxy); Mon, 17 Feb 2025 10:50:27 -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=fm3; t=1739807427; x=1739893827; bh=lS4E3341V1QwRkhrxVmLTnyoSE18r65AH4/LVnWHeow=; b= hke8xlxbKj+5DvnO/8EwSAxaeRM+uQkyN0sbP7bunPeuiTLRc/soylTk9Dtt46l+ x3ArakMJTt+mIPFgWQrWRHdlNmBw0c3nOrp5r13G4Al46U9Nkmdwoscc10vuaLoM LTkcUUUFu24Gu8R6B/B+t3+eXZeQNT20qewPOqet/GTPjbKGciLk11Qu/iLRnlqZ VTsaKgc1E5lczci1sb4LvmAnF+QHg4Ja2gGSeV4YDTVzGwA9BVZuC6K6qDWi2kEM sM41sEMX+jzN2HsRl/TBAWGYmPFS8HBJMnPwl68CMgPcbWiERfWSBbbLTe3ZCY2n GmGv1sm0N0nfwoxQIgZefg== 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=fm3; t=1739807427; x= 1739893827; bh=lS4E3341V1QwRkhrxVmLTnyoSE18r65AH4/LVnWHeow=; b=b /2T4Qg9eBEDljCz13VIIAZj+fKR2IwHLeuGTEdoGRCw36ovadKwKQqAOgRF7r5UH 2oIm7DRzwHu6NMzhUDsqKLfj64JPbRxD5jU7gHB8nLQwWwUvc0JwcHslFVQ2FO8f 02Zyqlqx9S/YkP0TJKz3PMnVWbdCUbaEPh+AGwDENd1bmQ+hduk4dEzktVwBDb+a IhQX9dKzn7mmLMHhfTvSCrHuBDwZ90Bl2XkBbPWLu+/zMNQXnk6dXOgiUgHJdqrf jBmjhP6IbjH78oSYfl2SsHjY2SMSZb0g7QzwYqeurbWMFoNc16sl1Lwy1UAhIbNh ifMpFIpq5bnxDPsfpLUEA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopehpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtoheptghhrhhi shgtohholhesthhugihfrghmihhlhidrohhrghdprhgtphhtthhopehgihhtsehvghgvrh drkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtgho mhdprhgtphhtthhopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnh gvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:25 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id ea38487d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:23 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:15 +0100 Subject: [PATCH 01/14] 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: <20250217-pks-update-ref-optimization-v1-1-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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..bc0265ad2a1 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..fb5a97b2c8e 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 Mon Feb 17 15:50:16 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978094 Received: from fhigh-b1-smtp.messagingengine.com (fhigh-b1-smtp.messagingengine.com [202.12.124.152]) (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 2B986225A48 for ; Mon, 17 Feb 2025 15:50:28 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807430; cv=none; b=dqo2VYaPhTSt4F3+d9XZsS8IvFRQF58bNITbNg4LgnEb0L1f28rtjO1P7JqrZCSi/CO5EKFgZZqagofnWFlbTgl2wCq6O97q04uP7fq3Td6Zh58FQ0iReEpniocdGviwr7S8/7jhH5C3L5v/a9OeVfIm5fcNW/CPHk/AWrti9zg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807430; c=relaxed/simple; bh=G2EvjM7vgNw4uXBAPunsAh2IXURPndinaevDpATevek=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=lGDCZZH1fcKM9HkwyqN76K+qYLpuFmFs8XNrB5FXgSJwWOsYik1KvYg/0wuC0ExJYzgLBwN+ztPC89CS8vfybyNq3rqwi8Qr+CsjBWLIcd/pKms6SOdWps5hxwTsI/LWEOy+U1KsTvRSt/iWkGAHs9tUk4+oNvWH1o9F3A6x4Ao= 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=FkbNoZDq; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=Q0VNcATV; arc=none smtp.client-ip=202.12.124.152 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="FkbNoZDq"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="Q0VNcATV" Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfhigh.stl.internal (Postfix) with ESMTP id 3048F254010E; Mon, 17 Feb 2025 10:50:28 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-05.internal (MEProxy); Mon, 17 Feb 2025 10:50:28 -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=fm3; t=1739807428; x=1739893828; bh=p/F5sAqFDMRBYQ5NjN4k9ezzr4FyDN+Cf8ixyfTl+Ls=; b= FkbNoZDq6jzfM8qxJt84iQ3zG2Zv+s58vveAwvBblIhv1FAbBNqoyExPkCjOkO1d vrdEYVcX1KfW4RhSwZsDG2S1g/6ROy14by1mTh/2w4fDAe63R2OnIdwRiEE4/xap bqi4T8Kj++q7mhOsL/UyAnL5EqXWFId3/Ga14zJeRzS31DtSj57IKR/GNTFvfxbC XIuI3D8rqA8XcTMU/YqNJJkRG0fNT1VcLlziM1CUlt3AFo4AyKV7V98WT52umoeh EPegG4CptztZfaWSmaki2ooHnBRxEZTJjOjgGN9yJk9Q0Dm1lkqkU2H+HLdqiO4N DRw4aPhjpE8LmlI0b5pu1Q== 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=fm3; t=1739807428; x= 1739893828; bh=p/F5sAqFDMRBYQ5NjN4k9ezzr4FyDN+Cf8ixyfTl+Ls=; b=Q 0VNcATVdYAGRILX3KpK/lb18/frZ2GX1q612g9NkBwIO1oOiBHnx9ut9hXHxXdYX GLV4gm/h+Um8Ie+OmlH4XnpwQpUvBMHOwWt+M9SjCcT/1srNNT+ZmohcoUh2wjPQ RMwm9Gbl15p902071IpPJOkcdcN3pPkUvUIP3OPOiHtrDrsyGxO9TTRX9cwnW5bY 3JhmQlCP8MSbsEv/DBqkCLOmFSOkjL/0FOJ8IUEZOl+quXLBv46G+SCcJYqhHjMD A9zLyObGK01xRH4eCPDvXdPgOyN8MT/Ra+nfLheCmN15mAn/OPJPNqTrwaTNVEUh f0heWs9ZB/MDICPX6xB8A== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprh gtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepshgr nhgurghlshestghruhhsthihthhoohhthhhprghsthgvrdhnvghtpdhrtghpthhtohepph gvfhhfsehpvghffhdrnhgvthdprhgtphhtthhopehkrghrthhhihhkrddukeeksehgmhgr ihhlrdgtohhmpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:26 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 2edb19b7 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:24 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:16 +0100 Subject: [PATCH 02/14] 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: <20250217-pks-update-ref-optimization-v1-2-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 | 1 + object-name.c | 4 +++- 2 files changed, 4 insertions(+), 1 deletion(-) diff --git a/hash.h b/hash.h index 4367acfec50..aeb705d6850 100644 --- a/hash.h +++ b/hash.h @@ -204,6 +204,7 @@ struct object_id { #define GET_OID_ONLY_TO_DIE 04000 #define GET_OID_REQUIRE_PATH 010000 #define GET_OID_HASH_ANY 020000 +#define GET_OID_HASH_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 bc0265ad2a1..0b23a65d2ed 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_HASH_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 Mon Feb 17 15:50:17 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978144 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 378AA232364 for ; Mon, 17 Feb 2025 15:50:29 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807432; cv=none; b=OHlgiku3O6GtMublQxCvcCUfKvuKinI9kIOld2qSEI9XRFQpzljLNESJp4eJ2BHsQdv3a58gd23uJxiTCCqmsaI071ZlOhs29kq7h29RgyEEbebSXw7oNG/B9m4qux5hMMlFZtGWrt9Ulr1Q0WcLtDcK53HQ381sQnZ1i/9UEcU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807432; c=relaxed/simple; bh=Ai99b/uUdMwPoekRYqPG/ZUDmUUd7r7Ba/9lxgwkBVI=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=K2VuAV4FV7mCenx1td9PztEiKL49oGSnphh5Z/xiDhZleUWgCoNuktKVCRfNLwWH/I6KjpHuKx9G2y1YQe+NgDwsAzjioHUVegzWLp6xihEVU5fsO15VLcauj/0dBFKskAXpoVllPUNqrYt4YDSixg/2CuWpaqZ4uoPe/pinlUQ= 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=pveavqaA; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=lHGkS7u8; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="pveavqaA"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="lHGkS7u8" Received: from phl-compute-11.internal (phl-compute-11.phl.internal [10.202.2.51]) by mailfout.stl.internal (Postfix) with ESMTP id 2B6351140186; Mon, 17 Feb 2025 10:50:29 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-11.internal (MEProxy); Mon, 17 Feb 2025 10:50:29 -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=fm3; t=1739807429; x=1739893829; bh=6j2iX6QmkMB0jJg9WGPRU7Ht5o27SYUm24ZVsb9AHNo=; b= pveavqaAKypY6lStiv02B9Ry6rtN2BWEeF+aNNGJBJMWljYNBsFn+ah4dvsE87k4 W1SK6AmyfO3XxirzbNmlPCoLikzkSnr0v9zhfGOessyPI6W1/oEVCQVWcvpqqBo3 xTkUZnBNeTuvOiARan8Z+Oa2stD+SO3u0MaZh3odpHWJ5wewyBQIjrLPFer92RzD wASykrCxGoKmee29hnPfWCObQpX9WpSf3EdGNFp4krGIE6cgdnrnbXZFnrPynidX IONqD32L9ZBh65pYARK4OkvbKRgM4A0E6QuMhRFDf6/3sdtDYQP7w0qsncjr7JpE rQtfgR/l8yJJRIp0Ud7rFw== 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=fm3; t=1739807429; x= 1739893829; bh=6j2iX6QmkMB0jJg9WGPRU7Ht5o27SYUm24ZVsb9AHNo=; b=l HGkS7u8lpD+lqEYt5GtpzvvqGaL93ukgl6N6Q8qqvEpgJbbUiB65/0tJawg8tBT4 IIGMkBTXiWvYSdF25s13QKlHDl1F3ZkmkgwDn1lVE+AREnZdDxbILfabHnailmbE E/5G7/N0pYwkmz+dhgE1MsZEsBPGfPFcuujPVtrucNONCgiGteejsiwVOci/gwSM foF4TOIg/DxyqFAafZjYGHMraRlkQsh9XRCWdmeHuksBwkE3esv4CeVc2VEMf9Xr 5pT4qHb72teEngCmpBTMnvg3ZER7HcZmaM8e88AMNA+d2vPbM9dVZf5Xgtd8JobX RjD+4HEKjCxFjLTHmBKqQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthekredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepfefhueegleehfeejkedtffehvdfhvdetfefgtddu ffduveevteegueeutdekhfegnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthht ohepghhithhsthgvrhesphhosghogidrtghomhdprhgtphhtthhopehpvghffhesphgvfh hfrdhnvghtpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghs thgvrdhnvghtpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:27 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 449e3970 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:25 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:17 +0100 Subject: [PATCH 03/14] 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: <20250217-pks-update-ref-optimization-v1-3-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 references, 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 out of two 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. 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. Disable the warning in git-update-ref(1), which provides a significant speedup with both backends. 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 | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/builtin/update-ref.c b/builtin/update-ref.c index 4d35bdc4b4b..ac330748244 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_HASH_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_HASH_SKIP_AMBIGUITY_CHECK)) goto invalid; } else if (flags & PARSE_SHA1_ALLOW_EMPTY) { /* With -z, treat an empty value as all zeros: */ @@ -772,7 +774,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_HASH_SKIP_AMBIGUITY_CHECK)) die("%s: not a valid SHA1", value); } @@ -783,7 +786,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_HASH_SKIP_AMBIGUITY_CHECK)) die("%s: not a valid old SHA1", oldval); } From patchwork Mon Feb 17 15:50:18 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978145 Received: from fhigh-b1-smtp.messagingengine.com (fhigh-b1-smtp.messagingengine.com [202.12.124.152]) (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 2E505232379 for ; Mon, 17 Feb 2025 15:50:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807433; cv=none; b=A3cvjlvKnfFg8Glpb4fAOmFlAZ0ySurT6qYWuF40KjZtcEkdcEQQmjwLBUvrLI8Ewg6Yr7yb7vLkBtoL8dc6QGFvX9VFWZRne46NT0ItCjbOhldtXFfIQaRQhcAi9u85rc1VXWP/CQfiW99R1HgldbStvetr5phuQWEE66061Co= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807433; c=relaxed/simple; bh=5gFC7EdB8/xgFsWt2M0tBFstQFI/o40iljpqi0GLwfk=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=UHVBo/JEpf/lchMNxsWegYSVVpG1+lsLO/2kGlCFMz7FEXVcxTqdutOxXHHkGo3xFca0BJXXLR+peaB0RnsWf2a4oX8JSmEGdI97TKiV3i8joxRgeUOzefFIq3NuAUbKK4caT1xR8vFca3M4KMyPsYyPMosXefEFEaoESO5k/bE= 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=BHYtbeiS; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=1FEPeULg; arc=none smtp.client-ip=202.12.124.152 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="BHYtbeiS"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="1FEPeULg" Received: from phl-compute-06.internal (phl-compute-06.phl.internal [10.202.2.46]) by mailfhigh.stl.internal (Postfix) with ESMTP id 2D3912540195; Mon, 17 Feb 2025 10:50:30 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-06.internal (MEProxy); Mon, 17 Feb 2025 10:50:30 -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=fm3; t=1739807430; x=1739893830; bh=pDlSVTnv+ExdQia0H72GhO6Tv2RISPyZbQpJAjatYfw=; b= BHYtbeiShgf6D4NkRiBMJYMEc8W3+/GwLJCuFj97CMxoLUcgLnr7r29aW4PjXBW9 dWbBF04iOX/SjLk5SqJZ0BpNwOYPp6W8ZUqNXvszuAnxEulbifUUoDLFhnqztJ7M GBpagCNsyIk02IV6qkCAdMyaOzJfgRQoQkWCykzII7K0ep0a+Wr5oIYvdLtvg4wz cg6eUbFv7U4VIqEw5lNjWEN3YHWAjHUobvJaeyYD6xlwF+piDpZzeycxAbxBIFe9 SoNxfmiHTxsgnp2ERBzcaGmAlzdK0Qg8PH8tbi0avtA2zfhZhNUB2OLSc2XSbWGH 6/G1sDbE87U38ddkv8bIag== 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=fm3; t=1739807430; x= 1739893830; bh=pDlSVTnv+ExdQia0H72GhO6Tv2RISPyZbQpJAjatYfw=; b=1 FEPeULgs839XGGNe+lt0D+xWxjhrjgIiE0/WYaeqi+Gtf3UaBB4V1nXjDpa8dQJS 6KML+DbvnW5GWdQE9I3gJD3x7oBihwq99oKK1N0WhsmtFKAC9yinQwwaKg1ohc6o khMgBCL8WG4+L09RTzJucMqfadz6Fkbm15wKbXV7PL/8m6eapYJVVCYl+t/SMWx0 HOXzNze3s/A/PdrkxvdHL3lmGEnYU0Vo7hOj4QZFyWYsbKMagEmEWbhnKcIc92Ye PmFCX9AvZsiI4diBGX4DSQDSmFj96SijFyID2HkyMHlmmRYBUhmQnBpfiTtvMgHj 9/4+cQMTGyAOvHhrNKCyA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgepudenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthh hprghsthgvrdhnvghtpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhl hidrohhrghdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpth htohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthhopehpvghffhes phgvfhhfrdhnvghtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:28 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id e3cbf738 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:26 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:18 +0100 Subject: [PATCH 04/14] 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: <20250217-pks-update-ref-optimization-v1-4-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 Mon Feb 17 15:50:19 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978146 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 312DF2327A1 for ; Mon, 17 Feb 2025 15:50:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807433; cv=none; b=Jmsrfsozv/H78W6SdJcR0sTy/7MezMU4F3DbgitMKnjLwFY8XzY50BzDzM/YZVnUpn8ylMSSjeGB5ZS8dwm9ecid0PmVhM7cV93aQanGlics+bLSPL9ZwZ5fSwXIzgVFnyzXVVAFqL8WSJYr2Bp//eKAWTxVZ5xCDKPDuBO/9t8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807433; c=relaxed/simple; bh=/QjHUxYfq1u4c6AQa1kSj63F2wRyztyNm3Fcc1Ohkgc=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=oqJx1YvJAeCklc+sjiIDS3cG+9hfMOcasTstQ/tD9gcLgV2UJmGH09nQ7v0swx2mCh0U9eTu4DvScXXpCvSTxnkJGK9drzVbSSg5z0i1ecB8Fgj/xA3JwlnodKvivL6ASDQEKHlcWzoyq13IC2mkqUoY5xZV7JTBgQFLGKM/iR4= 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=jm3lC32S; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=jAtOq5Cb; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="jm3lC32S"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="jAtOq5Cb" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfout.stl.internal (Postfix) with ESMTP id 122DA114018C; Mon, 17 Feb 2025 10:50:31 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-02.internal (MEProxy); Mon, 17 Feb 2025 10:50:31 -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=fm3; t=1739807430; x=1739893830; bh=5jnUOKOxc/qWmsir5F3qRrC8u/gkNvtLHHZHbFfcHp8=; b= jm3lC32SXxL27VE5PTZDEf3l9j7ARaQtcdShFlSSAxjsKYt6weguIX48J3p3dcR+ U0+jiZ+OIjdhb5ZauxGlEiA8Qoa9ozL4T0fvGDCMVTxw0gfpnMhwaVUI1Xlpqy7X NPo/VtmxiqbiqTgZxYwTIwy/OQluWuMzbM//a7+kC0UYYDsIgkaQrrq1nsSZnbml TPBODV90N+sDQhKzwrRxEb1+2fS8U871TrHve80JSV2vwtTFLqCV26aA/G5fWZnr 3Yxf4eprLzku/Az6KVgZrUH0taUKFPUrhuern3Zr6D7AakS72oqsBxayd+UjcX5j hHogOQ0KLtmFvKHfVuVEEw== 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=fm3; t=1739807430; x= 1739893830; bh=5jnUOKOxc/qWmsir5F3qRrC8u/gkNvtLHHZHbFfcHp8=; b=j AtOq5CbI5zH24mrW2sudvECsXIwXuWU5LxurEC4wAohAZvtk+VcLrKJsdkaO7G6R GTir8FyC4UOdqFFk3JOPSHX6qbXRaJCCUndmf4XAuCA9jEOpkdHM0VekUsjdJGr0 QR/gXpzeXjwltEIg6JMi0HvCMdEd4HuCCNMj9OZDYtCvZAcnbn2wHhVEfnpIC6vK OkksxO81MbjE1os4Hf+qsgsYuBq4VzhKDr/jG7DTC1iPGjSGwXasYDmMuPnFEW7Z lLl6KOvruZBGeUT0pxfJXWvABEEkbdi6gFYl9kaLP7yUnQ7rHsObx96eQmM8/Zl2 Fc0A4TZvel7tVxV6VEtXQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprh gtphhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohep tghhrhhishgtohholhesthhugihfrghmihhlhidrohhrghdprhgtphhtthhopehsrghnug grlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvthdprhgtphhtthhopehpvghf fhesphgvfhhfrdhnvghtpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:29 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 8f51f704 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:27 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:19 +0100 Subject: [PATCH 05/14] refs/reftable: start using `refs_verify_refnames_available()` Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Message-Id: <20250217-pks-update-ref-optimization-v1-5-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 we essentially still call `refs_verify_refname_available()` in a loop, but this will change in subsequent commits. 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 Mon Feb 17 15:50:20 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978147 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 54366233149 for ; Mon, 17 Feb 2025 15:50:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807435; cv=none; b=gmAeOqX8G0D/uy7Tjp1tp3LezZQPNBdWbVqdReL7GL/A7UnSBaGoVHSzA8I9FqxPTFO8R2bed/6oW9PISfHPVIxFR4aAAacZXTWulgvQqXtBmN2L6TQHrXRRG9R2UcGGUWLNI+DlEQu0x0qVsjqFb1j/DCRZ8qWMi4AHJyeapCo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807435; c=relaxed/simple; bh=GRybU3ddo8jNa/e4H/h4o6w6c55Rs2sgp2EONBlIfSM=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Xr6FPE1xsjoADfHdYt6UrU60ZIu6nXu1YHYolLtQD81y0nt+I2lYAn2Nu07IrHqSiwo2SegZdcy2yMXgJVzqUzZAE/VXLO9MULx7y1qgo47TS/dWV8g+st3Wzww3vQGKA/74mF3SVpUhTVE+hKO31+PuwHNiC/LNkV+5f9jIqHo= 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=WiTzJ9/j; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=vuijySbN; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="WiTzJ9/j"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="vuijySbN" Received: from phl-compute-01.internal (phl-compute-01.phl.internal [10.202.2.41]) by mailfout.stl.internal (Postfix) with ESMTP id 65C58114018F; Mon, 17 Feb 2025 10:50:32 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-01.internal (MEProxy); Mon, 17 Feb 2025 10:50:32 -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=fm3; t=1739807432; x=1739893832; bh=gj8adUcl5mtfgWscozBKmUTV3R6tsqe6NsfpjkcikGA=; b= WiTzJ9/j6CVf7dy4nLRg4Lp0oLNq7QzdSLEUpfvFnXoemg+EzeAWePuFqOzk3Vwg LdkTN2IWsia24tGkjr2F+GChaY/5JoXbEIrg6eNTAu3d5o0l56j2/Ty5rJyunLNW 0ouESr/cvPsWVMeITYMz5RFA5IDVsC5QB4znB7fZ5tTGByVw/OxSb/X/jO7h54WS h7PnYL2li8tCQM00/Lv2ULCFpOmDB097PRc1pjgmgquixedovyB0x4uBGVMUgEUN OLv2oj+9G0ifFtfFRjI1RyBkoRBNBJNIOmDCUNikP+jgQ/6ZOpDF3Ot/wueB3EMR bjc/DtDyzfvGLlFmdjOWgA== 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=fm3; t=1739807432; x= 1739893832; bh=gj8adUcl5mtfgWscozBKmUTV3R6tsqe6NsfpjkcikGA=; b=v uijySbNOCBqkK4QYKGu8DVRERH9FFBjOI8tboeqtv3u6l3i5ZbT6lgL+2lwwLN07 1FlBWp+jvf/CdNhK6PVh5pvrgqg0JesmoqDflUQmIYBg+tfDEssW+8yw2N0UdQ1r OJUw5pFAzgLsiuqakhEj7okg5IBVqTP31IT55g5nZlZc9yP/DcX4cBsstw+fqwT/ hLjPjX56fgwGsWmGEU5n/UCwv2pyJbNop4Um7EPn0UfWGibQhTocfMdx44AmWSJS enl+f3sYbtc7f66cSukx4lDIzxiFj5jq+CZisMghDekfuOaY12E/OiFRCsfyrD/R 2o/P+2VLAtOl8T1YV+RgA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthekredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepfefhueegleehfeejkedtffehvdfhvdetfefgtddu ffduveevteegueeutdekhfegnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrdhorhhgpdhr tghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthhhprghsthgvrdhnvghtpd hrtghpthhtohepphgvfhhfsehpvghffhdrnhgvthdprhgtphhtthhopehgihhtshhtvghr sehpohgsohigrdgtohhmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:30 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 660f2543 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:28 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:20 +0100 Subject: [PATCH 06/14] 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: <20250217-pks-update-ref-optimization-v1-6-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 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~) Note that the same speedup cannot be observed for the "files" backend because it still performs availability check per reference. 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 Mon Feb 17 15:50:21 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978148 Received: from fhigh-b1-smtp.messagingengine.com (fhigh-b1-smtp.messagingengine.com [202.12.124.152]) (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 007AF23315B for ; Mon, 17 Feb 2025 15:50:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807436; cv=none; b=F+42kdQQBQollKYcECzCVyYKjsnEUpHT7u2JEz1y7j/HjetT6acax4sowWeOm/ix3S3KKntW+KeAkQkQQ4gWxJPxEUHxPmN7/pRGMv97d9YvlxHa0ytoy3aHrgLRE3YPSeXK7CyISP9VfglCmmRuDTnHeWK1cIQa341bI+LmvSQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807436; c=relaxed/simple; bh=gdA+WOjGzMKsx83TECNZjsl4DzTcmeKGyqOJfH698LQ=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=l0Le9hnsOCDUptQvqvfOIUYhIzPR34BteHSbgR8oah4WKPNNGnLMcgvgFHASqVTsshjk3n9vxw4vQMkh8DrDUX62XvIZ5Z/+478wfHOS9uR51AmBJcz59WrdaTeoLU8GmEB25whT1z4s5rUWtjIOr2Z/WmDtTnRipExwkfu5m8s= 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=Rg9bFnLA; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=btJYKCfU; arc=none smtp.client-ip=202.12.124.152 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="Rg9bFnLA"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="btJYKCfU" Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfhigh.stl.internal (Postfix) with ESMTP id EA79B25400E0; Mon, 17 Feb 2025 10:50:32 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-05.internal (MEProxy); Mon, 17 Feb 2025 10:50:33 -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=fm3; t=1739807432; x=1739893832; bh=sWC5e/9NKpAfQZZb+W0cLHtoB3fIAMQvEYtkkYPFhy4=; b= Rg9bFnLAYyl62r9GMc8fDu9LM8LuzicfNUSKpbAZn13iIyOo+TrhovX+tvBOn89O MQF/OPdppimvw+gSKxR6dQmG5dfsiU9oqaWXTA9EABngAH32kCHbtmPnmQATXT5c Og7Td6nTpWlD5RIAHtkLEZASTUHgsnJHfl8fVZlylnQ2YhQSi6Yv14Ipno3XpIvR /B8hcqd5mWfMEFw4VOw3Q/XFyYT16+2ZBt8K45U60AmkQHNCQSv66TdIUeqocMmi RuU0UjQR5xl7uKEFqdLb3398zswAs/wMtSWzPZzlyEaxwwJkHTDnlhn0FOjqMDfO 1OLOwsszt89EV79HVlgXnA== 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=fm3; t=1739807432; x= 1739893832; bh=sWC5e/9NKpAfQZZb+W0cLHtoB3fIAMQvEYtkkYPFhy4=; b=b tJYKCfUUXc4JSYp4RsK44KSXZ3YiHMcTVbbIXiWnZqwI+Gdxq7+ZGuIJDuBkavCI nvrrU1Dx70SZeOn+AujqSAnYiZrSCXRjp9OJzzSk3dofV+h5gICRifEL6rfzP0qy 4s8Be9TsNsczCi8ox5Y7mrFQPNNjRMyUdKJcFV8mhS330Gm9K1B2+YPQ2GCBcwZy 0hlSt+5qahbCO3uUC1hL6vnPql/eTtYCh3a3wakPdc2daUx5Gzd1eP+9xXEcKOgo E+J6m7zUh8W98BJlbyt1Ag/vFn15+mlV0NygeomCmhK5x7Auni/Jwlhxbzwoiv3d ec/ZIGOozD1f5tZlATuDQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgepvdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthhoohhthh hprghsthgvrdhnvghtpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhl hidrohhrghdprhgtphhtthhopehgihhtshhtvghrsehpohgsohigrdgtohhmpdhrtghpth htohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtthhopehgihht sehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgvfhhfsehpvghffhdrnh gvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:31 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id d10bc3d3 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:29 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:21 +0100 Subject: [PATCH 07/14] 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: <20250217-pks-update-ref-optimization-v1-7-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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. 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 | 13 ++---- 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 | 31 +++++---------- refs/reftable-backend.c | 34 ++++------------ t/helper/test-dir-iterator.c | 1 + 12 files changed, 99 insertions(+), 189 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..01f51f6bac1 100644 --- a/dir-iterator.h +++ b/dir-iterator.h @@ -27,10 +27,8 @@ * goto error_handler; * * while ((ok = dir_iterator_advance(iter)) == ITER_OK) { - * if (want_to_stop_iteration()) { - * ok = dir_iterator_abort(iter); + * if (want_to_stop_iteration()) * break; - * } * * // Access information about the current path: * if (S_ISDIR(iter->st.st_mode)) @@ -39,6 +37,7 @@ * * if (ok != ITER_DONE) * handle_error(); + * dir_iterator_release(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 +106,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/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 29f08dced40..9511b6f3448 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -919,10 +919,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; } @@ -935,23 +931,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( @@ -1382,7 +1372,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; } } @@ -1390,6 +1380,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; } @@ -1456,6 +1447,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; } @@ -2303,9 +2295,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; } @@ -2315,23 +2304,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, @@ -3808,6 +3791,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..27ff822cf43 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. @@ -292,10 +292,8 @@ enum do_for_each_ref_flags { * struct ref_iterator *iter = ...; * * while ((ok = ref_iterator_advance(iter)) == ITER_OK) { - * if (want_to_stop_iteration()) { - * ok = ref_iterator_abort(iter); + * if (want_to_stop_iteration()) * break; - * } * * // Access information about the current reference: * if (!(iter->flags & REF_ISSYMREF)) @@ -307,6 +305,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 +332,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 +433,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 +451,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 Mon Feb 17 15:50:22 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978149 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EB732233D86 for ; Mon, 17 Feb 2025 15:50:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807436; cv=none; b=hcSQUjP/mzCQwMKPQvmvuBAT3wixag0iBuM4jSo08iqEk0fyAMIGGUHLZcvZF3YNI7qGXchrkUY3vHJMJd+JImQmE+ytOeQ5dN1tFP0+0Zs7eIGn+oHUvTuHfjKHsDhzFfApQkVydoeJieQEy8YpFNvxMcjham1Kf6BFnz7d46U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807436; c=relaxed/simple; bh=vXe6dsYH/UJ66Dzrv6IQh6R1vyj0gK6uCqakXTjoVmI=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=OWfhJ+PwnuWqCuUQ1AKM3jzd8rnlKrxICWEX0Ye4ZirdZgsj9yMSugF28cKpeGsLlxwNp8877x3U68bDJ4S1i9xt9XcsX5H/QGct++isfz978Y26D1mYRu6+48PfXgNh078JVLN/dJHUq3XTfebmo97bG9DP2Q+4KiHs3KgqjEI= 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=byY3TT5G; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=W1WQRtQj; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="byY3TT5G"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="W1WQRtQj" Received: from phl-compute-06.internal (phl-compute-06.phl.internal [10.202.2.46]) by mailfout.stl.internal (Postfix) with ESMTP id 3BE021140185; Mon, 17 Feb 2025 10:50:34 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-06.internal (MEProxy); Mon, 17 Feb 2025 10:50:34 -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=fm3; t=1739807434; x=1739893834; bh=hzRBof5FcLcH7RaVPec6qrcrnIKPePWwq9W/gB06RhI=; b= byY3TT5GCIyImxPVJWBEcA/LXhLbvkjaAzhN1n7kBwVhrkApsvsyJ1dRDAyG8RqU 7aazHYG2e9Gbq0hEIrEtHFRGgAWSy5stKuEMXehu9+b1PMgE2kBkl/6ibSlnUcat 46u1uEEtDPBfskMD2EjORMmIW3G78cuqH3FudaDnDvrnU6ylueYNFHEGRqD3Q7G2 FD5DbkPSwVqzUnOgtaujkUGAq/YH5EZc8AF+emWlNc+9FtJ7BEzjDDQow9v1TdTa EI97tMQYVI+vvIqPsLmAhUS21PkU+erDiOG0xTSN63vroUU3ajYC9x8i4ZVw01tG pE+yb/3CIcjsinkX0lMwWQ== 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=fm3; t=1739807434; x= 1739893834; bh=hzRBof5FcLcH7RaVPec6qrcrnIKPePWwq9W/gB06RhI=; b=W 1WQRtQjuUT6yZjEbSOnGXF5+wi5j7jyqfsyFZjNBBgMn6yzPudpW/Ttz9aU8icwS 5j36iScxchUy3ejhuUu34sla/cEo6T2MipClwP4IoMN94REYwshRdDCpRa/ad3sx OXvfkCCX4CyfXYUNUc1qVh/jCPuwy4xf4ClsBQngTXksSiZdiomEzc9J+stYnQ0p EvAYZK0xI5Pwg0XK/iTdExtkjp/6YOzD/3qf4NqcjRm2m3pR7uaWfnAyzF3eexP5 Us8aN5Lh+nUyQB+z9CgM83lhncf8GmMELQaHxmVTubGLvZS43ifazN1CTDyAGE2N 8DyLzFyXMr0R4CyUUQ6jw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgepudenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprh gtphhtthhopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvthdp rhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrdhorhhgpdhrtghpth htohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtthhopehpvghf fhesphgvfhhfrdhnvghtpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:32 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 8b9dbc94 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:30 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:22 +0100 Subject: [PATCH 08/14] 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: <20250217-pks-update-ref-optimization-v1-8-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 re-seek an iterator. It is expected to be functionally the same as calling `refs_ref_iterator_begin()` with a different (or the same) prefix. 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 | 23 +++++++++++++++++++++++ 3 files changed, 58 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 27ff822cf43..5fade7e8408 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -325,6 +325,21 @@ 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. + * + * 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. @@ -443,6 +458,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. */ @@ -457,6 +479,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 Mon Feb 17 15:50:23 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978150 Received: from fhigh-b1-smtp.messagingengine.com (fhigh-b1-smtp.messagingengine.com [202.12.124.152]) (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 03AED233D97 for ; Mon, 17 Feb 2025 15:50:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807437; cv=none; b=aTke3LxN6fxENeXHDOl83N2WyzjvCE5HPFwnNvgBW9irj2y0MZVGB2iVIzRUo8Lrwq5hI//aO5eovl4hh2mAC4TAL8/EZIIMkE+HQhqwpRRhUwpFNmsZvL1s4ctx7JkC6j9vdbTICRQc9B2JrbQeh8pV31ItDjUs2uzqfmOoh8c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807437; c=relaxed/simple; bh=nqPR6QxpLyDrwNhnblazDYbUp0phAk08xfA5JD/X+Qc=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Ra7Oq4o07JGRXgPerTyXs/gxkqpJCd1JZ1uYPC2vb28AV5oJhPD3gq8Ut+cP9NgYpea1eAG9cA287m4qQLA3ce5nk1L9EhaF6amDhr3ydQxFUCxXYSd6dkTSE8gyJXsR1V7XznqS2BIWochgHVn7txpWPapFOeF3tAZd3tTdl2g= 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=Zcd7CbCQ; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=rnSXWCuK; arc=none smtp.client-ip=202.12.124.152 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="Zcd7CbCQ"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="rnSXWCuK" Received: from phl-compute-03.internal (phl-compute-03.phl.internal [10.202.2.43]) by mailfhigh.stl.internal (Postfix) with ESMTP id E088E25400EE; Mon, 17 Feb 2025 10:50:34 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-03.internal (MEProxy); Mon, 17 Feb 2025 10:50:35 -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=fm3; t=1739807434; x=1739893834; bh=aWrY+mzuczK8DdPfwl3S9rUds8JICIR0qkSs77G5/LI=; b= Zcd7CbCQiHWJUlt82MZGHEKR7MLwX3S+ClBCePRQIo6X7tPWzGSykZxv+imY5xQG CdLrVkBJS3f2Ru606ayU0nnvLersTyG7hPwgpEKG9OilMPI1h5pBHzS8Dh5Z55jE M06/n6VRaYLJN3mg2WOb9hLknxAspeUVonwvrh6uks++aCjQiNXrCR7h9XBMzUJP E1+TJumcJGBlPV3rrx7qC39a4Yt9bdytvdPSNQy5o2wZjp0L7MZLOEpHY7hXweUa AWQfPMkTWf9H5L+HxyF2D8Y151oT5iFa/v1sut1IQyn1bZokwrFRhWmFVmOPRpl2 cNWL2LvkCRfeozPVkAFJhA== 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=fm3; t=1739807434; x= 1739893834; bh=aWrY+mzuczK8DdPfwl3S9rUds8JICIR0qkSs77G5/LI=; b=r nSXWCuKmfr4qunXuCZkdhHcXBDWpJ+bmC2AoD5e6gldTIJbbRQbEeRsBeR10idzB bcN96ZZigBkPSG3+m8VDO1u+3NpkFE4jPDkJbw/3X3nyPiyrl7rigS9iYAAiNPj+ dMwj/IUGGyNNJGLck7XyPmPCXQNejFEjDSrghJOlgJds9tuUetsOIRdZgciJyCnv 07ggZyg1IjGGQo5ywgP5FNvdj/DXRgNvE55yCB2S+251zzuGSbvI1c2B3pPVO127 AcLqAgkdm9gLdT4Wop1VQlv133MNtb1jDEGUVjCM/RcUZeCLOXAkI/q8xtIu8fjG h47svB8MrPYDZxULFsNcg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgepfeenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopehsrghnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdr nhgvthdprhgtphhtthhopehpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtohepghhith esvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthhopehgihhtshhtvghrsehpohgs ohigrdgtohhmpdhrtghpthhtoheptghhrhhishgtohholhesthhugihfrghmihhlhidroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:33 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 2f2d2ae2 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:31 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:23 +0100 Subject: [PATCH 09/14] 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: <20250217-pks-update-ref-optimization-v1-9-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 Mon Feb 17 15:50:24 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978151 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 114912343BE for ; Mon, 17 Feb 2025 15:50:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807438; cv=none; b=Ve8hDM3PXq4bnkaU+k0hydf5fEhlAT/ILjORlP3Hd6O8uUA0A960tY2w8DDrgOPtTfWo4hwf4cW10a7Ou0JraibbI/9vo1bCJ+5215J7NID3HvsYTz7tJaq4mc2bhld+siH+5ZU0oJhW0noMvMSYzUDQXSlVph7cjk3ToA+kXtI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807438; c=relaxed/simple; bh=t+78s95Fr/AZALcVXVm/3Y4kSZ68GgUea7LFzXxeVFY=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=PVtQVrLS/PRjt5trJbzUy6xBbwPFBaq7OM5IytIpHaFPobcXhCE3HD+XV4qFdaqsno4wmBYC0Hm1ZHMZ6IoqJ0x1elfxrVEqEZtJZfFDFremIS391eJ422D01jlb1xDGBdHKqeKoCWZUSP9itqYSvmdNKQoRCqlDKJyIjFYz744= 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=h7VKBkvb; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=zC/zEvKl; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="h7VKBkvb"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="zC/zEvKl" Received: from phl-compute-05.internal (phl-compute-05.phl.internal [10.202.2.45]) by mailfout.stl.internal (Postfix) with ESMTP id 17A4C114018D; Mon, 17 Feb 2025 10:50:36 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-05.internal (MEProxy); Mon, 17 Feb 2025 10:50:36 -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=fm3; t=1739807435; x=1739893835; bh=bUQoO4X3F/YsI0DEHSWA6Zn2qHIueWoh36yqFCQ5E9c=; b= h7VKBkvbPSCXQZrrtTfQm4E2HrumlOd9wcko0bg8dG3o+VQlSDc+SnJk2YwviCwI lqnpeIt0T6PLakmX8VGfN/p9HwhVX9yaiIZI8FF2SfPftIW2ziNyzuEIso50ky+E qMVgDYoyu9CFz4RFqJ3fh4lnuzThKWVa0zAmePErCktdK/Puz+j1zqjSDMmzTeLT 7pbXptQV60M1KwWEFYdbXL4Btwkr66Wmg0gN2pSEtmATNf33VC5ZUFYFxylRLpqi J+IcftkxwYFwiSmHu1wMP7fr3S+UTVLnXuvoUQJA4chbGJqnUop/+oS+HYwABsZV OzMo+VF6Yq52VWMgGJOdqA== 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=fm3; t=1739807435; x= 1739893835; bh=bUQoO4X3F/YsI0DEHSWA6Zn2qHIueWoh36yqFCQ5E9c=; b=z C/zEvKlDJAsxeN9lj4V+labiNMl/b9NeOeRexw5+HHRTc6YEgTXEguRa453vbJPr YWbMGXV+ZMH9FPwvRxpdgbOKw3epJ0urQy9L4zPld3FI1AAyxOpdUe/SzKhadem/ u3JlqRXjazppt6GBO5ebjP7cp/EyBaT/c2U3kBW7cDgVS9enGUiAAjxY5W0At09e i025nyd9LuBn2oEd7og6iNfFBAbZ9304S55nmcEgytu68Fdyzwz/KOEu2dNIsbHS XlrcT6Mr79w0AJrmIHK9dktutQwJ/bSl8hoBQzpRy3Hc13ARX2BuDTIeS6E99k35 A2K4BbpGnTeWDg4FbfcZg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgepfeenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepphgvfhhfsehpvghffhdrnhgvthdprhgtphhtth hopegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrdhorhhgpdhrtghpthhtohepkhgr rhhthhhikhdrudekkeesghhmrghilhdrtghomhdprhgtphhtthhopehsrghnuggrlhhsse gtrhhushhthihtohhothhhphgrshhtvgdrnhgvthdprhgtphhtthhopehgihhtshhtvghr sehpohgsohigrdgtohhmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:34 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 2e6d2dab (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:32 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:24 +0100 Subject: [PATCH 10/14] 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: <20250217-pks-update-ref-optimization-v1-10-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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. - 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 Mon Feb 17 15:50:25 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978152 Received: from fhigh-b1-smtp.messagingengine.com (fhigh-b1-smtp.messagingengine.com [202.12.124.152]) (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 DAD8A23496B for ; Mon, 17 Feb 2025 15:50:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807439; cv=none; b=FzV27tMjr9tOxcwn7zbPCfI/egGIIKLaFyKjF+6UM5iK+GdT9uDXv7EdImSjXjq8u7vaRSskhtWXwEnvfldBZ8fmP41zUbtQFesHZ0A5eigcBcfy37vB9hznTUOwtdV4ldBHqU3foWY6G2TNZapkBhjB9Irb/EASQ4lWe7IFBcw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807439; c=relaxed/simple; bh=zXIFpULq0cvFfooG7wMGne/aY0RhwJmDV1nfUfGymaY=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Z5/MioOkNRb5mxQhZFVv+IRPSoTf93mB9Lq7sPInMn+8dKNzgMkEeFoy0VBHOYtRlpXTT2iv04E05Sx2w3x8FIc/W6in6EfyXgFVxHLShb3SA1jK5grPNHQVDqUhfFkbETK8uN6f8jLEdTi2ZsQdeJMjkVTzqkwMRQs3fzeU6TY= 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=EmbRzhxu; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=mmpn7NvO; arc=none smtp.client-ip=202.12.124.152 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="EmbRzhxu"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="mmpn7NvO" Received: from phl-compute-04.internal (phl-compute-04.phl.internal [10.202.2.44]) by mailfhigh.stl.internal (Postfix) with ESMTP id D12D3254019A; Mon, 17 Feb 2025 10:50:36 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-04.internal (MEProxy); Mon, 17 Feb 2025 10:50:37 -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=fm3; t=1739807436; x=1739893836; bh=5gSR1Q9V11ebmZTwzsW+5r4buPtOeV46c/+QHKi9ZYw=; b= EmbRzhxuy1nROrn6MpyuJ9DDuM38GlPUTJS/YT5IWgLaIgJ+S4nNMAU5/zXuxwiY FDDEsTwUFjEVeP+FsmWDrX810xq+LUkA1nOcbr9tLGthZEb2z6y0cQupgYBHiHQ1 BSQjBJYG/d+TlkGKy3iyud4jOiHUTay5dFdfaNzWmN6JCNzCxNn9bMLRlFRTiMGV inaVVkAG0inmv6vmaGOLH6afTXEOEp3XjXS5UtwsznydSbZRF2f5FZuO4zxhaT0M JjjvIzuFzVElNo4iDt0B1jUMs2N5MHye/sVpNudk9XF8ryUX2BFFVUmuX3GaIwNC bqmklySoQJZxYgFRjSz1dA== 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=fm3; t=1739807436; x= 1739893836; bh=5gSR1Q9V11ebmZTwzsW+5r4buPtOeV46c/+QHKi9ZYw=; b=m mpn7NvOe+fQRnXnZfwiJzbtfxMz5O6oNHpO2y9R43G0FkLbeaFWaNd91QPS5Hf2B zgp+J+u9QhYTfw3cVgr5d3nKMpiZq7sGKrovAnEYrrvJg/pNwuugGNaA8Mh/TxtM THxocn8IZ1gs3Fr/ny1pF964uglBP5OX6txDW9IE+R1lCehGwSRi3OppAh59qpA2 i7ez4FRRWdOs498I2LjPWKFNgytlkKPtSGSNd6GeXMT/RmpGpj1vE11VWQln7lAD NBlbqAwlADlwpK35RAzWMZwLbE+ihpg78RLJa1wrmY1+hdHa7d80zHttbjygZe3v wM29ZHswe9oNZS8Ewiy6g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtghomhdprh gtphhtthhopehkrghrthhhihhkrddukeeksehgmhgrihhlrdgtohhmpdhrtghpthhtohep tghhrhhishgtohholhesthhugihfrghmihhlhidrohhrghdprhgtphhtthhopehsrghnug grlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvthdprhgtphhtthhopehgihht sehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgvfhhfsehpvghffhdrnh gvth X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:35 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id c36f0167 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:33 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:25 +0100 Subject: [PATCH 11/14] 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: <20250217-pks-update-ref-optimization-v1-11-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 corncern 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 | 74 ++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 48 insertions(+), 26 deletions(-) diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 6457e02c1ea..b54547d71ee 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; @@ -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,40 @@ 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 ref_dir *dir; + + dir = get_ref_dir(iter->cache->root); + if (prefix && *prefix) + dir = find_containing_dir(dir, prefix); + + if (dir) { + struct cache_ref_iterator_level *level; + + 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) { + iter->prefix = xstrdup(prefix); + level->prefix_state = PREFIX_WITHIN_DIR; + } else { + level->prefix_state = PREFIX_CONTAINS_DIR; + } + } else { + iter->levels_nr = 0; + } + + return 0; +} + static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -462,6 +500,7 @@ static void cache_ref_iterator_release(struct ref_iterator *ref_iterator) 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 +510,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 Mon Feb 17 15:50:26 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978153 Received: from fhigh-b1-smtp.messagingengine.com (fhigh-b1-smtp.messagingengine.com [202.12.124.152]) (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 B2E9723497D for ; Mon, 17 Feb 2025 15:50:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807440; cv=none; b=neBRCkG2Xi67lghkgsmLTZlZx40oD1rNQSPzDJtdASsgYM6aAS/VZzJJkJLOSRGrFICbbBXg380WhBQbXQj4rd8jjo39KMNM4bQW4Cgre3YAEm9QEnXIukPe6CXSCqheS4U/WZiKq7VuMT04vd4CeW8A0SXPn/3f03CxFPlI168= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807440; c=relaxed/simple; bh=B2s7cOW4Abj29R7T+5uWGCDTTPfwBi+gHffjmiGW6B0=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Sfy6FOvu9MIyK5GFQUJamgNgcc9+ZKiw8gKQcLB1/J4L217xYFOxyp22dbpC55MRZ80zUVCufrBXUYY0rRmBe99arlSt4gFFk1tA8mUV3kasyW1qrcekZd8IinZ3EV1i+gOIzjWmGLctjoA5XyZETMVprS+2HpxmQ2XXvpyTrQk= 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=LVF3Ihxw; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=cyMx5oKQ; arc=none smtp.client-ip=202.12.124.152 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="LVF3Ihxw"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="cyMx5oKQ" Received: from phl-compute-01.internal (phl-compute-01.phl.internal [10.202.2.41]) by mailfhigh.stl.internal (Postfix) with ESMTP id EB6EF254010E; Mon, 17 Feb 2025 10:50:37 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-01.internal (MEProxy); Mon, 17 Feb 2025 10:50:38 -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=fm3; t=1739807437; x=1739893837; bh=btxvst6qh0SPVkvsX7Tu+niXZPEf35b2HvaSP+9QAgU=; b= LVF3IhxwYR4nnT/w2HIdDXkbsu6uSJ3Q9INRZ++fXo2VU/BB5xyc/X049LKBHFLV pNPFNhR35YSwPBsdYnju54wnuFJ/ujNYhhQuMJ5FQwZu7/Z59IoAC5ziA04hFKIz t0jLZofegl58YrP4xr5nAZ8ivBzWWYGa3hibP83K1D02pHcAnUhStRL5Yq0GR6bA pxTypLwJ85FmBB9WqZtD2z+tCiGJStNasLqryWxV5xFWOvdlL7oyrcXyoQMTKA/P TZkQN/dV6Oyez7WQT+jwjjeVOCDtwwCgWK8B3TWIKjKQwu/Zb0U6q8XcpRGkpfY0 +dUiDrROhEMHLVodBeWmpA== 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=fm3; t=1739807437; x= 1739893837; bh=btxvst6qh0SPVkvsX7Tu+niXZPEf35b2HvaSP+9QAgU=; b=c yMx5oKQSz4xBUtMUQe//fIjgWFcYsK2WTbbGbpfExjjdKeA9j5d9UKSZskni0H6R kKdZQBAD+AN8iazQJAODfD5zxovxAVpTDrBjSK5c9DuAQfofOj42/ju3ozqj3EYk JeUZxZ/1j+ckLnWBfWjEXc9SyQuMPx2or4HqPTd94SIgKej+E1MMIwe0ugkNO+jx YuEWN8ncLOYilgguf4jPeOn7gZDmKsa1UqZfgKmIFJ/1ARvHt7s1VAhOfrJbjpQJ T6OOK/4lYd7Keo4Q0OZjUsK+KGw8gB136MD3CVRy4t9bTWQdxWfkXLrouwfzSkiZ bFDKh12v+q2JCtGjoSSog== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopegthhhrihhstghoohhlsehtuhigfhgrmhhilhihrdhorhhgpdhr tghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdrohhrghdprhgtphhtthhopehsrg hnuggrlhhssegtrhhushhthihtohhothhhphgrshhtvgdrnhgvthdprhgtphhtthhopehp vghffhesphgvfhhfrdhnvghtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtg homh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:36 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id d43244d1 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:34 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:26 +0100 Subject: [PATCH 12/14] 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: <20250217-pks-update-ref-optimization-v1-12-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 | 62 +++++++++++++++++++++++++++++++++------------------ 1 file changed, 40 insertions(+), 22 deletions(-) diff --git a/refs/packed-backend.c b/refs/packed-backend.c index 38a1956d1a8..71a38acfedc 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,12 @@ 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); + packed_ref_iterator_seek(&iter->base, prefix); return ref_iterator; } From patchwork Mon Feb 17 15:50:27 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978154 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A82AF226164 for ; Mon, 17 Feb 2025 15:50:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807441; cv=none; b=HGskIwX/cYbpFvZnqzwSNULwO+iqYtpikJA4+z4bifkHH2AEQP9NN6MNdysOzpkgAXCPddkLXREM50WcN+Mx9+Cp65UhqcpqcEEZ0NtAEWI+1oigHi+GjaZDDkeDILkvBWnP8zxac3QOu1dVpydWto3KXAUuNgeFqUlF11s6Qxs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807441; c=relaxed/simple; bh=FAw7E6D8hVaD2NlviC3DKf8NzcOCLFWq3tCAnYrXw7Y=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=LFbsXy8mlo+Kw4TGwzg9GNwHI8T+uG7fQCc69OycEo/tPKRFTFKuBWDOMoSm4jSVWYyjMeq2lI2TPHsB7eSXzK62fLceNH1/wT9vgwqsi+NUJc2BzFVaT1V+aAVf/jKN86vB0ZcfTUBJu/HIpxXOFOskBXL6lRSLJ/BRlytPr5w= 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=Ty5iWyy9; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=lGNNzf4C; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="Ty5iWyy9"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="lGNNzf4C" Received: from phl-compute-04.internal (phl-compute-04.phl.internal [10.202.2.44]) by mailfout.stl.internal (Postfix) with ESMTP id D00931140190; Mon, 17 Feb 2025 10:50:38 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-04.internal (MEProxy); Mon, 17 Feb 2025 10:50:39 -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=fm3; t=1739807438; x=1739893838; bh=xnYZPOJE4NpKJ4WHQ+iMDRaEa0xJ0PwXGnTVFnK9OUc=; b= Ty5iWyy9oPUdPIgtmy5nxA8bY4dLeGB1OI6mCpIYJj7F3C/zrSXACj7ce4j3Tt1Y IeSS8dcf/nV2sWenSoqGK3CzcnwVh17VSmDL1fikkmigeLYN/oK9rJaJ++gwKjB4 qk2nq686t/GSqdVCP2xUjQOHuelhvJICEKcfJsSVNnO7wI37t6/r1/FQsSRJU7MS NHsQnZpaWTTMp1i0HhjiAq/ZZwoaBBSqQE3xCpOihdc3O9VnR5XtmKyqXiw0B6jj sbidF4eVk+PQhzf0cB3Kt8kb5vLZNmY1BVJLOZ4bVK0oVWA2Z0oNYSXEsu3NAhzR 2TJ8MKKyLrGTHqRvW/EDkQ== 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=fm3; t=1739807438; x= 1739893838; bh=xnYZPOJE4NpKJ4WHQ+iMDRaEa0xJ0PwXGnTVFnK9OUc=; b=l GNNzf4CZp6TpmoREIZVYvcLaOsGHnS2Pex8bR56hoNjI/Ck1GdnnvS+hx/Z2rEvC 3UMXldrAYWD2JJycjqmI5EQeyORXZv2A0uTvSM7Is+8+Ow5SLpP28QPvBsgvdmhZ RyRfU4xVHCMTEDkGwwlnTWwkepMWDzNJjhywGGuVOccsQ+sxNj2MDkaTOzfyygPx DcDeeNZHZcnGTwzs7lCneRGfZ1qqXSQ8ixpt59klZCPS4MOD60+Mbxl26VLpp7hO c8ObDlKqAx1USymDseKKFVLDT4TvZL4FguKrdvIIJnZY7290LWfVrvlbz9YHI+U+ +TQQIjgGoojwWqt/hn6BA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeekudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthejredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepffeuiedujedvkeehuedvkeefffeivdeuleetkedu heejteekgedvudfgtdfgieelnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopehpvghffhesphgvfhhfrdhnvghtpdhrtghpthhtohepshgrnhgu rghlshestghruhhsthihthhoohhthhhprghsthgvrdhnvghtpdhrtghpthhtoheptghhrh hishgtohholhesthhugihfrghmihhlhidrohhrghdprhgtphhtthhopehgihhtshhtvghr sehpohgsohigrdgtohhmpdhrtghpthhtohepghhithesvhhgvghrrdhkvghrnhgvlhdroh hrgh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:37 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id bd3f6110 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:35 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:27 +0100 Subject: [PATCH 13/14] 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: <20250217-pks-update-ref-optimization-v1-13-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 9511b6f3448..acc28e1ad81 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -922,6 +922,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) { @@ -940,6 +948,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, }; @@ -2298,6 +2307,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) { @@ -2313,6 +2328,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 Mon Feb 17 15:50:28 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13978155 Received: from fout-b1-smtp.messagingengine.com (fout-b1-smtp.messagingengine.com [202.12.124.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0B3AA23535E for ; Mon, 17 Feb 2025 15:50:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.12.124.144 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807442; cv=none; b=RTKTiWDyClkDqhZMZUQkvJFN2+U4cqdV0INWpeyPGqQ1TYzC+gWKox8GB4IqgeitnilSjBj8hepD0mE7lPxe670I0ygEKZLh0nquF/nblKn9k1wiY13Mwi1xes9DeHpxSjKI3M5aKvLicxL1vP3kMUrdN0VHm+iCKPT2a/YppJw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739807442; c=relaxed/simple; bh=9OeAJA2kLpYwq/IN5OzeZUEwPB5n+vXE4JtQVW77iV4=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=JsIoV3p6tPwga1h8PY31vHnygfaSGW8PziFhwS2AgAe5ac8IHPo+FkR3Br5tD+a0ptJmn0LZf3rOlyH6XSXW0BDULzgojtWbztT+YpqLoG+2nTqHpyCnM/dxK8uODp46nSPBhs354BF2u7P4VskDkeL6PAPjVF8dviE7dESUb+I= 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=gl6jpbCc; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=jRFx0s5q; arc=none smtp.client-ip=202.12.124.144 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="gl6jpbCc"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="jRFx0s5q" Received: from phl-compute-13.internal (phl-compute-13.phl.internal [10.202.2.53]) by mailfout.stl.internal (Postfix) with ESMTP id 0B72E1140186; Mon, 17 Feb 2025 10:50:40 -0500 (EST) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-13.internal (MEProxy); Mon, 17 Feb 2025 10:50:40 -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=fm3; t=1739807439; x=1739893839; bh=NsLZuRcf9Q5id3sIlSaSf0EBH5X4YWl3g1hSxQFr638=; b= gl6jpbCcqTSgMPFTCbMJuwROY+EaUFb+8ehl3hnBimR+MSXpNkfYFelUDWQ762Jg ORfBbtLuOf71xAGmWPc38/Sr+TOI7Co9vyFymO7ecygc2kXHHt6nozO4GAL2FnFE NeD6jMigxpe/4J2MNg5n61u1q2gJ60wuIgWi9F0flRmhU7nicTMi0Z83aRiVflU4 a83/0bJvW2fknDnUYF5sa3qz+rzlBpgYWy5GEYffRxrSW8ulGCQl0L2D9gsLwsUE I64uFiBbbreTNx3+z+er9xEqIL82EHQp9Q2PGHu+zV3rwC+kNOruiykA/OYT4qYJ SbPjXWA/4diCb6sWE7Evwg== 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=fm3; t=1739807439; x= 1739893839; bh=NsLZuRcf9Q5id3sIlSaSf0EBH5X4YWl3g1hSxQFr638=; b=j RFx0s5qBV7gNZjQvd8GUbF/R4PhsM5RO9mln1sRDEtjlt9lh7bGER3GTq9nA1n4N Eq573KmkYw2+mvA3Qct08kyeLt1IoGdjUxP1jVRjsogmrH2SKn9VaS/2sFb5pUL8 3i8LPduPHK+ywDlTckmUIIOYjCW138BeeoS8Pv7hEjN0hbCUvyWw77nu6ImGx/c2 aEvdNaymNCtv0cHopmDD1LJ2WqUtzbJ0h7YXsY1WIEjg5a13XGyzPcch+ch9QiU3 OYRwIxBIsyDW1YvSQos1nq5NutvzrXm5srQkTmG3nuk0w54QM2aHc5C1C655oMRw yQo2Z4uy10KNv7l26+Ogw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdehkeektdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpggftfghnshhusghstghrihgsvgdp uffrtefokffrpgfnqfghnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivg hnthhsucdlqddutddtmdenucfjughrpefhfffugggtgffkfhgjvfevofesthekredtredt jeenucfhrhhomheprfgrthhrihgtkhcuufhtvghinhhhrghrughtuceophhssehpkhhsrd himheqnecuggftrfgrthhtvghrnhepfefhueegleehfeejkedtffehvdfhvdetfefgtddu ffduveevteegueeutdekhfegnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpe hmrghilhhfrhhomhepphhssehpkhhsrdhimhdpnhgspghrtghpthhtohepiedpmhhouggv pehsmhhtphhouhhtpdhrtghpthhtohepkhgrrhhthhhikhdrudekkeesghhmrghilhdrtg homhdprhgtphhtthhopehgihhtsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthht ohepphgvfhhfsehpvghffhdrnhgvthdprhgtphhtthhopegthhhrihhstghoohhlsehtuh igfhgrmhhilhihrdhorhhgpdhrtghpthhtohepshgrnhgurghlshestghruhhsthihthho ohhthhhprghsthgvrdhnvghtpdhrtghpthhtohepghhithhsthgvrhesphhosghogidrtg homh X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 17 Feb 2025 10:50:38 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id da13434d (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 17 Feb 2025 15:50:36 +0000 (UTC) From: Patrick Steinhardt Date: Mon, 17 Feb 2025 16:50:28 +0100 Subject: [PATCH 14/14] 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: <20250217-pks-update-ref-optimization-v1-14-a2b6d87a24af@pks.im> References: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> In-Reply-To: <20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@pks.im> To: git@vger.kernel.org Cc: Karthik Nayak , "brian m. carlson" , Jeff King , Junio C Hamano , 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 speedup with the reftable backend, which is the only backend that knows to batch refname availability checks: 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~) 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);