From patchwork Thu Feb 1 07:51:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13540761 Received: from wfout3-smtp.messagingengine.com (wfout3-smtp.messagingengine.com [64.147.123.146]) (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 63BB9158D66 for ; Thu, 1 Feb 2024 07:52:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.146 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773923; cv=none; b=K1kEAQtPGqpre+8IMQo79HT4wA27/FCaf16UeHgplKWcOoFIECphUt7t8dNdc1N31/fuUatL50hXy4WoqLmOAA6/4luZLAI2bcHWWICe7aVnvrkHbgsOTcWy9VkzGAD7nZ8q0y5d+/2ZLwxp/2h1Sl0GoU1nciJBQILlOj4jKsE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773923; c=relaxed/simple; bh=9lhm9BrmUSzT/FRqdJA0OMgkj4DdK2bvq5Txy+TzcLY=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=j+iraWdUMfZU1BZslBxOtAr9hH3pwtrQmShTvH0p38e2ZyfW1V4bp4s5ltAVI2xyBMTHZ1PnTDMGw8RkvWuj0WnrqcXMRHRUPpvTdS8U3plWFGa78EsOnJnYTSe/7BeZUNkBzR1+3yFa4+pzozDWn2XCsBsi2czhtz2iQXAcTWc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none 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=YxU+u5r9; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=dt8i4gDl; arc=none smtp.client-ip=64.147.123.146 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none 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="YxU+u5r9"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="dt8i4gDl" Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailfout.west.internal (Postfix) with ESMTP id 17DEC1C00069; Thu, 1 Feb 2024 02:52:00 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Thu, 01 Feb 2024 02:52:01 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1706773920; x=1706860320; bh=zy7fp1TsAn wdqDSCYTVtkx4q1A96ArZxxyywa6k8ILQ=; b=YxU+u5r9VU6oxQ1E1LRZCOFYIF jjI7m2Yc1BnsKUGNyHS0Pf4xQ56rgvmTEs7VfZ/7zNxGgyPJcywSAxUJ9MlDbiEM hs+nHKhX5MbefiR5T1K4M3U9MFtcDvZ6Oiu2lgSUpEhdKNrwgDJU42WrnNg5Qenr TCTjMG81yFLCEQJAStwnHw7mdS+nH9BYMfRvTP2UuaaAgRg9trgF10zYUsiGTgKn I6v74XIl1a9Uh/14+OKUi6jreV3oFJbL7vrQJPFE0h/kU2jrDnwx5g3vVF/bnIX6 8nOFqLDZHFOzyY7NklagtgPfjX1quckar9xLF/Y75CacSxS+SFWjIpEXQcRw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1706773920; x=1706860320; bh=zy7fp1TsAnwdqDSCYTVtkx4q1A96 ArZxxyywa6k8ILQ=; b=dt8i4gDlaWJr7J5GLQSiHdOyDCLdzyD5scGfg/5lLYsA DfpzsSSuzmwBlBagVQijHaw8Azh61xdA/YrvHgabc7ARBXC3skUp0db1WFEXXOum iNKSGDeXBIQ6QizAG6X2WodK0UgR2IcjFRRXI7HUrdegOxV+9RiftxNxpRTH6s7H OKOa82Q+3UuglcZhd2eEYjyD6MBTJ6jpLMzssXjhLpCENXYVItJgj7UPWiIJxT/o NDY2opu1ylw/C/8koq5qi82I6KWm4nbrJ1wHP255vYU5Lnrd5malfMAc2l3PLiIc v4cQXCSU6bIM7ALSY+eUvO7YfKxeqPPBv8o34X/D5g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedutddguddutdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleff teenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 1 Feb 2024 02:51:59 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 7475996a (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 1 Feb 2024 07:48:36 +0000 (UTC) Date: Thu, 1 Feb 2024 08:51:56 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Junio C Hamano , Toon Claes , Kristoffer Haugsbakk Subject: [PATCH v2 1/5] reftable/reader: be more careful about errors in indexed seeks Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When doing an indexed seek we first need to do a linear seek in order to find the index block for our wanted key. We do not check the returned error of the linear seek though. This is likely not an issue because the next call to `table_iter_next()` would return error, too. But it very much is a code smell when an error variable is being assigned to without actually checking it. Safeguard the code by checking for errors. Signed-off-by: Patrick Steinhardt --- reftable/reader.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/reftable/reader.c b/reftable/reader.c index 64dc366fb1..278f727a3d 100644 --- a/reftable/reader.c +++ b/reftable/reader.c @@ -509,6 +509,9 @@ static int reader_seek_indexed(struct reftable_reader *r, goto done; err = reader_seek_linear(&index_iter, &want_index); + if (err < 0) + goto done; + while (1) { err = table_iter_next(&index_iter, &index_result); table_iter_block_done(&index_iter); From patchwork Thu Feb 1 07:52:00 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13540762 Received: from wfhigh3-smtp.messagingengine.com (wfhigh3-smtp.messagingengine.com [64.147.123.154]) (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 C0915158D8B for ; Thu, 1 Feb 2024 07:52:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.154 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773927; cv=none; b=nQC/h0wFRRegjyZ5DzFMe9xLpxmFYvQ6u+ge2Mj2XDjWkKaIJvEJJ9NzzibQzBqkZDzVBYcT/faY9bL+YPN8QnTMgv/NOoTTA9Kjd/Tmbk3Qmb1IJUX2X0aAK1kLKfWn/NvFUjgyjaZuOSJg1MyY2vTLoiZsUr5GzPgC3B1iUFo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773927; c=relaxed/simple; bh=LEZIHfuVjYRw/3uEB7/dB6ODg8nZZizDMWIl2X5goJk=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=OTcWAw69MTSFJu1kkwP/AtJXkWx/ZK0dIONyY1BUSsnFd52d8HRXhVDnj8C3kr9L4aq9KoinrW8FpVVQt40TXSNfmUKHFdXdzwA+s8AidUh2BXJGA0G6qJvMejGH3N6/Js3YyXyhcrwsmOI2WUR9OXr3fYWGHb3lk2eyb7XxggE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none 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=MN+ow+At; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=XSProfIP; arc=none smtp.client-ip=64.147.123.154 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none 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="MN+ow+At"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="XSProfIP" Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailfhigh.west.internal (Postfix) with ESMTP id A9F261800079; Thu, 1 Feb 2024 02:52:04 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute1.internal (MEProxy); Thu, 01 Feb 2024 02:52:05 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1706773924; x=1706860324; bh=dhvGIyfDC7 3YbY4Qip7QO1UmZanFqNCV3put3TaN2Ts=; b=MN+ow+At+gZKT52TNIpy2C3Ge4 +7ME5SS1ZJrhOxO4u5MMEaZVpiyAc83e5CAhgHFbXTt6D8CeDDd33agEzzftIzWM 9P3TrNkxH2RiwWZkVYBszfMbhfGbES4f+ngLb5tQ1PrS5MjGZRegsenbWYLL5Lg8 9r/BT+D0H2gANnWDF08NQ+rH2aXj6ZHE/MXgtYv/ZwLChtHPa+WYfWdglXzBFTTu +ghyFKOeDZbbcvaUNuFlSlfMajF02QyJkvMg8d9ePw3JDlTXooQA9ukJkvbkQJvR 7qoZEdy0aHRWuGNVZ94DUzvJfTjtEUBccYV2cbF+SooO8GvhI0nIJS8eMS1w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1706773924; x=1706860324; bh=dhvGIyfDC73YbY4Qip7QO1UmZanF qNCV3put3TaN2Ts=; b=XSProfIPZD4YZR/FBuHuDF9SzDAGXPe94VGyj6SS+oFc ksMMdCQ26jmtU8iZb2Ih4t+LHn+obsTpeQzd4XLwBaR0x0GapnHSqBntsEOldrFh 2KdZR1ysGmPRU+AvSyE0NgwiL18p8v+SZEEejvIZIpbLZv48RFH/qncQOC19YahJ 6qOFaAtHq68RM04xRQPdI1kuVWqC3yR74uCA8nQGreIBLkRv0/8Xh2IcvXDwiFzO aaKSxmp+d+a1drOyIQKZzB2+Qr73AerlboxkNG1k3wL0PbdA2P+hJ3gE4toxqVkt glDxRKhSuYerhwfPjpvtfyIlLyJWZiI6DXKaZ/YV7g== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedutddguddutdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleff teenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 1 Feb 2024 02:52:02 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 51865484 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 1 Feb 2024 07:48:40 +0000 (UTC) Date: Thu, 1 Feb 2024 08:52:00 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Junio C Hamano , Toon Claes , Kristoffer Haugsbakk Subject: [PATCH v2 2/5] reftable/writer: use correct type to iterate through index entries Message-ID: <88541d03bef7c6ff425d330b153f3e3d94ca7567.1706773842.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The reftable writer is tracking the number of blocks it has to index via the `index_len` variable. But while this variable is of type `size_t`, some sites use an `int` to loop through the index entries. Convert the code to consistently use `size_t`. Signed-off-by: Patrick Steinhardt --- reftable/writer.c | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/reftable/writer.c b/reftable/writer.c index 92935baa70..5a0b87b406 100644 --- a/reftable/writer.c +++ b/reftable/writer.c @@ -379,20 +379,21 @@ int reftable_writer_add_logs(struct reftable_writer *w, static int writer_finish_section(struct reftable_writer *w) { + struct reftable_block_stats *bstats = NULL; uint8_t typ = block_writer_type(w->block_writer); uint64_t index_start = 0; int max_level = 0; - int threshold = w->opts.unpadded ? 1 : 3; + size_t threshold = w->opts.unpadded ? 1 : 3; int before_blocks = w->stats.idx_stats.blocks; - int err = writer_flush_block(w); - int i = 0; - struct reftable_block_stats *bstats = NULL; + int err; + + err = writer_flush_block(w); if (err < 0) return err; while (w->index_len > threshold) { struct reftable_index_record *idx = NULL; - int idx_len = 0; + size_t i, idx_len; max_level++; index_start = w->next; @@ -630,11 +631,8 @@ int reftable_writer_close(struct reftable_writer *w) static void writer_clear_index(struct reftable_writer *w) { - int i = 0; - for (i = 0; i < w->index_len; i++) { + for (size_t i = 0; i < w->index_len; i++) strbuf_release(&w->index[i].last_key); - } - FREE_AND_NULL(w->index); w->index_len = 0; w->index_cap = 0; From patchwork Thu Feb 1 07:52:04 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13540763 Received: from wfhigh3-smtp.messagingengine.com (wfhigh3-smtp.messagingengine.com [64.147.123.154]) (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 7AB531586FE for ; Thu, 1 Feb 2024 07:52:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.154 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773930; cv=none; b=urL96k/MjqqYvMk4OXBVLiTZdaqX2Rx5J8DKyRlr/mJaX63gpzxcQX9Cy2+l9B6N1HTPZyQB6+NObEwRBCC3bGD3NF1Pqly2ec5rYX53YahtK19mR9M96ZYWwVMIu1hY7gU1f7pN0ESUDOQLtTA2himFcztZxDr9X0xVrPrNi7g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773930; c=relaxed/simple; bh=cbX34zuD64EuECwd3TsXdFD3/b8P9/v/p2nmTe1YxEs=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=goRELJsfc9H+UrIJrr+6Lz3tiTrfsrC7QfEu9izREZ9Nq/BOYC+PcyGnprlD9Ep/N4/dasxF+8YqDfZ7SA2zaQ7isa0/p/hRzSD30SLD9EJTOKWaktLfMNopgKQb731baRkGpb3Aad2AtmAKBCop6un75EEY54c5Xsk2o8dUCBk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none 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=QKag0iiP; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=WO1Lv6Sp; arc=none smtp.client-ip=64.147.123.154 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none 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="QKag0iiP"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="WO1Lv6Sp" Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailfhigh.west.internal (Postfix) with ESMTP id 2D94F180007C; Thu, 1 Feb 2024 02:52:08 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute2.internal (MEProxy); Thu, 01 Feb 2024 02:52:08 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1706773927; x=1706860327; bh=IFt0NGLBHF AUz1Wj8tfSBcQpb4lj0WEM+nLD5hv7Knc=; b=QKag0iiP9/BpIthAG6l1Lg3HFP g4rbAqT3142as0GYTBrizHo/41bcXVPrD0f5p+IobXk170+SK+BZ6CnO0Y7MjoIA /qNMw34yf/B4abImGCJgTyJ5hxZCoCSribcC/3s4pter8X1JWaB1UgscpK/N8zOh PhUcMJqdSUzwsMA/zRgvLElV7PdFi5nGtlKBLsYio0O/I5KuwRcjv5AIVyUd23q7 flGqaUoG/vzsxDBHem5xwUVCHChDELurgdIyzvxDjbeXAKiiTqxCC2qjMDajUelj yev+NM6ncTh67JETQJTjlZZq/fbnGgUo3XF8H/a4eiyLddrY565VSYvn0bgw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1706773927; x=1706860327; bh=IFt0NGLBHFAUz1Wj8tfSBcQpb4lj 0WEM+nLD5hv7Knc=; b=WO1Lv6SpbfCJs67xIGqhIdEXwmwNvdCyJeH2QsXQCgT7 I0m2fR8uRLJrPvEcZSulR+2VDhRuVXCmB5s+X5LG0O2tG/Y4L0J76kUoYDhvS9BJ VvAtyXodfp8Oz8aXAIR+qX8ig+ZQa/XtxbizqjM6C3z9C7IjZcQ9fQgCpraUKaMn QT+gqfcHFJlrmg8LLzleNq2Esr7zO8OAfh0W6QHGf1ddJMPSHn34oPRElyiwdE0J KQmU8hLR7WGNoQimFVR587NbC/6Fp3U9NqrWi7FjRYY/kPbtc0/TzsLNAo6SdRw3 GMAo/UNwVC/uxSDQnmH74gnSfshc4ijv6oGEUzClRg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedutddgudduudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleff teenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 1 Feb 2024 02:52:06 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 8d790735 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 1 Feb 2024 07:48:44 +0000 (UTC) Date: Thu, 1 Feb 2024 08:52:04 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Junio C Hamano , Toon Claes , Kristoffer Haugsbakk Subject: [PATCH v2 3/5] reftable/writer: simplify writing index records Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When finishing the current section some index records might be written for the section to the table. The logic that adds these records to the writer duplicates what we already have in `writer_add_record()`, making this more complicated than it really has to be. Simplify the code by using `writer_add_record()` instead. While at it, drop the unneeded braces around a loop to make the code conform to our code style better. Signed-off-by: Patrick Steinhardt --- reftable/writer.c | 18 +++--------------- 1 file changed, 3 insertions(+), 15 deletions(-) diff --git a/reftable/writer.c b/reftable/writer.c index 5a0b87b406..b5bcce0292 100644 --- a/reftable/writer.c +++ b/reftable/writer.c @@ -412,26 +412,14 @@ static int writer_finish_section(struct reftable_writer *w) .idx = idx[i], }, }; - if (block_writer_add(w->block_writer, &rec) == 0) { - continue; - } - err = writer_flush_block(w); + err = writer_add_record(w, &rec); if (err < 0) return err; - - writer_reinit_block_writer(w, BLOCK_TYPE_INDEX); - - err = block_writer_add(w->block_writer, &rec); - if (err != 0) { - /* write into fresh block should always succeed - */ - abort(); - } } - for (i = 0; i < idx_len; i++) { + + for (i = 0; i < idx_len; i++) strbuf_release(&idx[i].last_key); - } reftable_free(idx); } From patchwork Thu Feb 1 07:52:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13540764 Received: from wfout3-smtp.messagingengine.com (wfout3-smtp.messagingengine.com [64.147.123.146]) (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 DF78E1586FE for ; Thu, 1 Feb 2024 07:52:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.146 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773935; cv=none; b=fTNKgwRBBb8Pi5WuJbe+71PV7/HNKnqHVahReHeb5Chl8xiX9NHk/lyMJTR7uIB7/UNw8Dbi9e9POdAPFa7Af+xYebo9Yhgl5vekt3N2H3KdEBShs3PO7wHLyVLu6Oh97mq3Ii84oXoGcA5YXQovMCa7+qtE3RFyH0eYt069nUo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773935; c=relaxed/simple; bh=G6dNrwF5mEshdodv/fJBoobjOrseFZx+tuddoan9Hp4=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=VIrc56pKtB1cfEJcwt5amQUxFukdDsJBQQr2QVaVvzTMhb/tVXuJQ0gHJggbVSiyu3vUX8uaTjYy7qM0amy40WRZMYXJ+GbgkvUbuvyxax/oNgIXUVUc0sU4bGmr4boiIgM0j1lO1HO6nmqvoClFghveDak3cjbsGLpcDlaWXM0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none 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=bA3wslVp; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=PRX6koWS; arc=none smtp.client-ip=64.147.123.146 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none 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="bA3wslVp"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="PRX6koWS" Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailfout.west.internal (Postfix) with ESMTP id 8F5B61C00069; Thu, 1 Feb 2024 02:52:12 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute3.internal (MEProxy); Thu, 01 Feb 2024 02:52:13 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1706773932; x=1706860332; bh=jnc3Elxjgu sL3k70dddV7Y1JLBzFgjWEkiJaZ2W9+D0=; b=bA3wslVp196y0HoPyM7AwANrMM /4KFrX8HNyPQEn4VoTtdsQYF9r1STOix/dOdLvpvjKpGXZPILcX9abzDbPX51XbG kdrOtvyyT2nz4xDO231mSf74BUCCEMTkVIWYemq3XrJKeNvC9Ot3X0En/k7sT3MQ eI39Bo+1RnMcDku2jbEfhHatZeCdwLydcR1FNF15dyOiRw3wEcdOD8dc2VsqXvmE vGsS4/2+prYzc6+ZqJXmVBdj8K74UddEtyCh9xryE2vQnugtIQfWhRx3oQdeU5K+ AYUMwmdCrM7iCFxGj2vhZ8TTir0XumI9pbw7f1Levfyt7MWfosQk5/0Y6kQA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1706773932; x=1706860332; bh=jnc3ElxjgusL3k70dddV7Y1JLBzF gjWEkiJaZ2W9+D0=; b=PRX6koWSH9CtKKOlZs58d6EXvL/E9q0hBGzKofCDxj2r 8iZ4TS67MbDqdx6sB1ujM4s5HzFR+ipILbY09igdCaxMBjjmw5KjWQH9nebXZRmV h2nXO7G1hLmvGEvbYsEpu6i0xd+RGcZWI0syxuSChTrGSZOn1nYgY1Kj2GFhkApU +LSxei10ZN1Db2fruWdvm7TU33sSc7TNkx2G3dpX/zRTcN3XDttyedmriLQsGJTH 5tpKa+Iq64ZYXEh+mSq3o+GnZXetgBgIcSYNBIRMLdJ3DhLHLKUQpe8t7ujwNaFM AIUU1NAVjfk5Eqv74CTVeUD1X3UoknMVss9aojCzdw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedutddguddutdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleff teenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 1 Feb 2024 02:52:10 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id 8fdbf104 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 1 Feb 2024 07:48:48 +0000 (UTC) Date: Thu, 1 Feb 2024 08:52:08 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Junio C Hamano , Toon Claes , Kristoffer Haugsbakk Subject: [PATCH v2 4/5] reftable/writer: fix writing multi-level indices Message-ID: <89a88cf83eeb50542d3878c5c6e56e46f2bc3e73.1706773842.git.ps@pks.im> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: When finishing a section we will potentially write an index that makes it more efficient to look up relevant blocks. The index records written will encode, for each block of the indexed section, what the offset of that block is as well as the last key of that block. Thus, the reader would iterate through the index records to find the first key larger or equal to the wanted key and then use the encoded offset to look up the desired block. When there are a lot of blocks to index though we may end up writing multiple index blocks, too. To not require a linear search across all index blocks we instead end up writing a multi-level index. Instead of referring to the block we are after, an index record may point to another index block. The reader will then access the highest-level index and follow down the chain of index blocks until it hits the sought-after block. It has been observed though that it is impossible to seek ref records of the last ref block when using a multi-level index. While the multi-level index exists and looks fine for most of the part, the highest-level index was missing an index record pointing to the last block of the next index. Thus, every additional level made more refs become unseekable at the end of the ref section. The root cause is that we are not flushing the last block of the current level once done writing the level. Consequently, it wasn't recorded in the blocks that need to be indexed by the next-higher level and thus we forgot about it. Fix this bug by flushing blocks after we have written all index records. Signed-off-by: Patrick Steinhardt --- reftable/readwrite_test.c | 56 +++++++++++++++++++++++++++++++++++++++ reftable/writer.c | 8 +++--- 2 files changed, 60 insertions(+), 4 deletions(-) diff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c index 6b99daeaf2..853923397e 100644 --- a/reftable/readwrite_test.c +++ b/reftable/readwrite_test.c @@ -866,6 +866,61 @@ static void test_write_multiple_indices(void) strbuf_release(&buf); } +static void test_write_multi_level_index(void) +{ + struct reftable_write_options opts = { + .block_size = 100, + }; + struct strbuf writer_buf = STRBUF_INIT, buf = STRBUF_INIT; + struct reftable_block_source source = { 0 }; + struct reftable_iterator it = { 0 }; + const struct reftable_stats *stats; + struct reftable_writer *writer; + struct reftable_reader *reader; + int err; + + writer = reftable_new_writer(&strbuf_add_void, &noop_flush, &writer_buf, &opts); + reftable_writer_set_limits(writer, 1, 1); + for (size_t i = 0; i < 200; i++) { + struct reftable_ref_record ref = { + .update_index = 1, + .value_type = REFTABLE_REF_VAL1, + .value.val1 = {i}, + }; + + strbuf_reset(&buf); + strbuf_addf(&buf, "refs/heads/%03" PRIuMAX, (uintmax_t)i); + ref.refname = buf.buf, + + err = reftable_writer_add_ref(writer, &ref); + EXPECT_ERR(err); + } + reftable_writer_close(writer); + + /* + * The written refs should be sufficiently large to result in a + * multi-level index. + */ + stats = reftable_writer_stats(writer); + EXPECT(stats->ref_stats.max_index_level == 2); + + block_source_from_strbuf(&source, &writer_buf); + err = reftable_new_reader(&reader, &source, "filename"); + EXPECT_ERR(err); + + /* + * Seeking the last ref should work as expected. + */ + err = reftable_reader_seek_ref(reader, &it, "refs/heads/199"); + EXPECT_ERR(err); + + reftable_iterator_destroy(&it); + reftable_writer_free(writer); + reftable_reader_free(reader); + strbuf_release(&writer_buf); + strbuf_release(&buf); +} + static void test_corrupt_table_empty(void) { struct strbuf buf = STRBUF_INIT; @@ -916,5 +971,6 @@ int readwrite_test_main(int argc, const char *argv[]) RUN_TEST(test_write_object_id_length); RUN_TEST(test_write_object_id_min_length); RUN_TEST(test_write_multiple_indices); + RUN_TEST(test_write_multi_level_index); return 0; } diff --git a/reftable/writer.c b/reftable/writer.c index b5bcce0292..0349094d29 100644 --- a/reftable/writer.c +++ b/reftable/writer.c @@ -418,15 +418,15 @@ static int writer_finish_section(struct reftable_writer *w) return err; } + err = writer_flush_block(w); + if (err < 0) + return err; + for (i = 0; i < idx_len; i++) strbuf_release(&idx[i].last_key); reftable_free(idx); } - err = writer_flush_block(w); - if (err < 0) - return err; - writer_clear_index(w); bstats = writer_reftable_block_stats(w, typ); From patchwork Thu Feb 1 07:52:12 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13540765 Received: from wout1-smtp.messagingengine.com (wout1-smtp.messagingengine.com [64.147.123.24]) (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 02C14159586 for ; Thu, 1 Feb 2024 07:52:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.24 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773938; cv=none; b=LQNiN6QOcgsvAUzPBHNcW/jRW4vid5XRLGMeYLenIhmVvClnnN/VUUlrAFuTBEOa89+zFTOay3Aum7Y1IkxVq7bgobh3Jg/Pc33wIrutnC0HpGwOfwC3iIYUS+AIx7sZEzaBTBu1UV/yi7MpOQMxsa2xoyuk/Kj+v5DQAv367NI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1706773938; c=relaxed/simple; bh=rQqegkjdGseutip1iHybIlMwPt+JNxZdD1ANJ/Gt7go=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=RBlEKTuIzsVwqXtsGMNwXSlX2v8sluju63TGKPraa2N6NS/HF5Q3AaqRgnCjIA6YlC1sPfKZFr76oIJ3KL+vhsxcCZOD+Gji6xOUnHOfQZl70IxDlVTUXwENL9wr9SmTYUofk9iYRybrU4s6GHSdNontvoMxubENCfxAGVxoCpE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none 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=IJFnAMt5; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=sLR+9GmA; arc=none smtp.client-ip=64.147.123.24 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none 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="IJFnAMt5"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="sLR+9GmA" Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.west.internal (Postfix) with ESMTP id E7D143200B4D; Thu, 1 Feb 2024 02:52:15 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute3.internal (MEProxy); Thu, 01 Feb 2024 02:52:16 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm3; t=1706773935; x=1706860335; bh=conp/zc7SZ i/7gXUuJrtjSjM73BgGv8fQbEH997vCBc=; b=IJFnAMt5gpvKk3SSRVImSXEb/r je3OdJFrt7+PuW0V89crQ6T3YflZQSMcDzxb+ZjC/eCMTNLyyLowpV+U6i9d6toC gKbu150N7g/zNMM0ep5EBBz/zegyOT3RDp3zydWh9krqMsUhGCCARWVS8JuWIEPH VYm67IXFTCV50bbBtUzTNB14vNj8Ejci0Fcf/ldq3WAm+1BQyHrXrSJrkEYDUVp2 7ggQBUlhT1gDqR4AZlVtOL7buNz01KpORPWWu7dTd+bScZSEBKk2B5zqKl2UkTsO gCzcIbjKo0xaLgJRK1FZvXw1SxK86YjxS2kBy6dZAAMsmoauiavocrZI5pYQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1706773935; x=1706860335; bh=conp/zc7SZi/7gXUuJrtjSjM73Bg Gv8fQbEH997vCBc=; b=sLR+9GmA/zuhdBUMr/HGVuRsYWfWWsfbyeixqWvk9Jf1 4q08mBRIHzllcNensU9SckPlxtt9iOJQByq9V2tGF3P8k4Upd+9UILobY85PFd6R 9eCZyBhwrr7RpZy5XlYcUOsgk4yTTMbXOcUp4Tp86Ey4AX0I4kPCDtLFTexvVYkr G6zAUG/8Z3nrRTsxWOnumNOlOqTRV8vRA1mm6YZKNDMaoJg73KTqw9NXqTt2WSGY yiqWsoPqSV7N34cyZdCW3TyzdZSpAuYJ3enTvSAZVq64e5hxs21jwKYmY0ZQu0h6 7DJ7xzfO5sg1HonqB0auNnizXmgOoJO8yLcAZeS+yg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrfedutddguddutdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleff teenucevlhhushhtvghrufhiiigvpedunecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 1 Feb 2024 02:52:14 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id eed9a01a (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Thu, 1 Feb 2024 07:48:52 +0000 (UTC) Date: Thu, 1 Feb 2024 08:52:12 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Junio C Hamano , Toon Claes , Kristoffer Haugsbakk Subject: [PATCH v2 5/5] reftable: document reading and writing indices Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The way the index gets written and read is not trivial at all and requires the reader to piece together a bunch of parts to figure out how it works. Add some documentation to hopefully make this easier to understand for the next reader. Signed-off-by: Patrick Steinhardt --- reftable/reader.c | 27 +++++++++++++++++++++++++++ reftable/writer.c | 23 +++++++++++++++++++++++ 2 files changed, 50 insertions(+) diff --git a/reftable/reader.c b/reftable/reader.c index 278f727a3d..6011d0aa04 100644 --- a/reftable/reader.c +++ b/reftable/reader.c @@ -508,11 +508,38 @@ static int reader_seek_indexed(struct reftable_reader *r, if (err < 0) goto done; + /* + * The index may consist of multiple levels, where each level may have + * multiple index blocks. We start by doing a linear search in the + * highest layer that identifies the relevant index block as well as + * the record inside that block that corresponds to our wanted key. + */ err = reader_seek_linear(&index_iter, &want_index); if (err < 0) goto done; + /* + * Traverse down the levels until we find a non-index entry. + */ while (1) { + /* + * In case we seek a record that does not exist the index iter + * will tell us that the iterator is over. This works because + * the last index entry of the current level will contain the + * last key it knows about. So in case our seeked key is larger + * than the last indexed key we know that it won't exist. + * + * There is one subtlety in the layout of the index section + * that makes this work as expected: the highest-level index is + * at end of the section and will point backwards and thus we + * start reading from the end of the index section, not the + * beginning. + * + * If that wasn't the case and the order was reversed then the + * linear seek would seek into the lower levels and traverse + * all levels of the index only to find out that the key does + * not exist. + */ err = table_iter_next(&index_iter, &index_result); table_iter_block_done(&index_iter); if (err != 0) diff --git a/reftable/writer.c b/reftable/writer.c index 0349094d29..e23953e498 100644 --- a/reftable/writer.c +++ b/reftable/writer.c @@ -391,6 +391,24 @@ static int writer_finish_section(struct reftable_writer *w) if (err < 0) return err; + /* + * When the section we are about to index has a lot of blocks then the + * index itself may span across multiple blocks, as well. This would + * require a linear scan over index blocks only to find the desired + * indexed block, which is inefficient. Instead, we write a multi-level + * index where index records of level N+1 will refer to index blocks of + * level N. This isn't constant time, either, but at least logarithmic. + * + * This loop handles writing this multi-level index. Note that we write + * the lowest-level index pointing to the indexed blocks first. We then + * continue writing additional index levels until the current level has + * less blocks than the threshold so that the highest level will be at + * the end of the index section. + * + * Readers are thus required to start reading the index section from + * its end, which is why we set `index_start` to the beginning of the + * last index section. + */ while (w->index_len > threshold) { struct reftable_index_record *idx = NULL; size_t i, idx_len; @@ -427,6 +445,11 @@ static int writer_finish_section(struct reftable_writer *w) reftable_free(idx); } + /* + * The index may still contain a number of index blocks lower than the + * threshold. Clear it so that these entries don't leak into the next + * index section. + */ writer_clear_index(w); bstats = writer_reftable_block_stats(w, typ);