From patchwork Wed Apr 2 14:54:09 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filipe Manana X-Patchwork-Id: 14036120 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (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 CDCB823C8AD for ; Wed, 2 Apr 2025 14:54:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605658; cv=none; b=KWybp6+BiKfP/KGh+cikLH7v1b/x3HpKT+Fop1o3lk7vhuJeGLZVf+/FKYEn28vh6BT6OyiqE4mZtyAb1S57chTbRgnemFvGDy44VHcg/ATO90MIXlQD0YZK34jJLCDbcSBASA+XueaSvltcSA16MWPstE965Y51ZeY8N9wvjJU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605658; c=relaxed/simple; bh=D2uFBeAwqiEl/ocwtBlcwQeYyKQALWHpO51KWBko2mg=; h=From:To:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=LrfecaWaq616lg1pS0yqEvnkpTui8hSeeQ9iZ4Z7+uE7ksx1gYxhjVkjdItqcUPCI9/EpYg3Lhh5OO7bSht+mH/7c4oAfFQGDeSwMcFdRzAGy0kyOZHav/acIm1WdUe4Xb8Kx5b6jhMNVSUd4aOYdbSAAnQ/YDiHFd97QrE6GB0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=HFgNBzoC; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="HFgNBzoC" Received: by smtp.kernel.org (Postfix) with ESMTPSA id B4787C4CEDD for ; Wed, 2 Apr 2025 14:54:16 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1743605657; bh=D2uFBeAwqiEl/ocwtBlcwQeYyKQALWHpO51KWBko2mg=; h=From:To:Subject:Date:In-Reply-To:References:From; b=HFgNBzoCrfPN6Ney3GuplMzeZNcfG+SqwJux/AKhN1yNDe+T60pzeMmdW86js2RhS 2BTxxuFLQ+NGH748E9bGElS7qHNa5TYIgh03CRyhJy246mq+9R2wh2muhgrnVSBH7U EHiuoF1nynf55/SACjz7ENef1DTp3qU3ZxzaWVlUCv0jENoTAKGnFvog6a+UM4oN9K krC2Fc0zxDRK9pLcFw8YPwNXRTLJVU2Y0wt6SvzVPUu3O7MCjUBpZvKATSCNzEZMfJ 0pa+dznUUqmRc7IONlWCYI0g29bxaVB3JiQ9L7cn5ukeaFZmN5GAj7RnXbZzDlwFlw 53TZ2JsV9IXwA== From: fdmanana@kernel.org To: linux-btrfs@vger.kernel.org Subject: [PATCH 1/4] btrfs: fix documentation for tree_search_for_insert() Date: Wed, 2 Apr 2025 15:54:09 +0100 Message-Id: <37c8d8c041a01c8aa59673ffbd26bb0829f89ac8.1743604119.git.fdmanana@suse.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 From: Filipe Manana There are several things wrong with the documentation: 1) At the top it's only mentioned that we search for an entry containing the given offset, but when such entry does not exists we search for the first entry that starts and ends after that offset; 2) It mentions that @node_ret and @parent_ret aren't changed if the returned entry contains the given offset - that is true only if the returned entry starts exactly at @offset, otherwise those arguments are changed; 3) It mentions that if no entry containing offset is found then we return the first entry ending before the offset - that is not true, we return the first entry that starts and ends after that offset; 4) It also mentions that NULL is never returned. This is false as in case there's no entry containing offset or any entry that starts and ends after offset, NULL is returned. So fix the documentation. Signed-off-by: Filipe Manana --- fs/btrfs/extent-io-tree.c | 22 ++++++++++++++-------- 1 file changed, 14 insertions(+), 8 deletions(-) diff --git a/fs/btrfs/extent-io-tree.c b/fs/btrfs/extent-io-tree.c index 3c138e6c2397..355c24449776 100644 --- a/fs/btrfs/extent-io-tree.c +++ b/fs/btrfs/extent-io-tree.c @@ -233,21 +233,23 @@ static inline struct extent_state *prev_state(struct extent_state *state) } /* - * Search @tree for an entry that contains @offset. Such entry would have - * entry->start <= offset && entry->end >= offset. + * Search @tree for an entry that contains @offset or if none exists for the + * first entry that starts and ends after that offset. * * @tree: the tree to search - * @offset: offset that should fall within an entry in @tree + * @offset: search offset * @node_ret: pointer where new node should be anchored (used when inserting an * entry in the tree) * @parent_ret: points to entry which would have been the parent of the entry, * containing @offset * - * Return a pointer to the entry that contains @offset byte address and don't change - * @node_ret and @parent_ret. + * Return a pointer to the entry that contains @offset byte address. * - * If no such entry exists, return pointer to entry that ends before @offset - * and fill parameters @node_ret and @parent_ret, ie. does not return NULL. + * If no such entry exists, return the first entry that starts and ends after + * @offset if one exists, otherwise NULL. + * + * If the returned entry starts at @offset, then @node_ret and @parent_ret + * aren't changed. */ static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree, u64 offset, @@ -276,7 +278,11 @@ static inline struct extent_state *tree_search_for_insert(struct extent_io_tree if (parent_ret) *parent_ret = prev; - /* Search neighbors until we find the first one past the end */ + /* + * Return either the current entry if it contains offset (it ends after + * or at offset) or the first entry that starts and ends after offset if + * one exists, or NULL. + */ while (entry && offset > entry->end) entry = next_state(entry); From patchwork Wed Apr 2 14:54:10 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filipe Manana X-Patchwork-Id: 14036121 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (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 C2B6223C8CD for ; Wed, 2 Apr 2025 14:54:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605659; cv=none; b=D/bUQckFuYlNRTiN9egety1IrLdSivjTpHH+zpxNz3z+BJXdKVJDyAor4mt5Sjh/ZMB0k6IXcTv2fSoxtzsdKr8u1FxllLTSwaGyPQ1yrfoTx6zyWi4o6684uOrI6G8pzSsKVIlDYexFw27OeBynM+b5Re7g2x3E648IK0uz/i4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605659; c=relaxed/simple; bh=pulcjm3sjJuVepIWdS8YnVZ6qwAP0c7Tyz0KbJmUoyw=; h=From:To:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=kWsnszAaVejtmwQZ8nXfgleqbFJz9akMvsSSuIDseGuhENLAZY6P7vSRdajbAlQWdeJ6gatU48rfc2JgQJv5Kybvp/pHf9NRP2DudeXWdMbQgjLkCibY81faVNMyf3A1MdR6vfKgjOP5YUinPlwh4fDPnufJNm4ZksckgGuaMvE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=Yb3SNb90; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="Yb3SNb90" Received: by smtp.kernel.org (Postfix) with ESMTPSA id BA674C4CEE9 for ; Wed, 2 Apr 2025 14:54:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1743605658; bh=pulcjm3sjJuVepIWdS8YnVZ6qwAP0c7Tyz0KbJmUoyw=; h=From:To:Subject:Date:In-Reply-To:References:From; b=Yb3SNb90H980yA9gZ3APNTTqXG1Tq61fxFUZTfC6UVqT2asoMko37iBKv866vx0Dg r9e785NpVGuTuCq3vTYlIA0KaX/6V+hYdGz67zcvIR/5EJ7VjmCQ70CShGA7MFwCxR 30n0At0tq5na6xmquR3eS3Zbp5omBIJUKcjlcCrFvjDnUcWXZ/ELKu2xS9iVCPUmbw 6SVk5INAcIzcTrmFABZt8IRqcZZ3lTdd5MJk5jsYo9PB8YTBFiK5zBz0VVULYqYa+A xqxqyfOKZR+OR6JhQlWsAdGKdPQdZjTt30BDQbS4Ex2YfDatANwUk01ruduhSWbb9M TtsMml19AP+cQ== From: fdmanana@kernel.org To: linux-btrfs@vger.kernel.org Subject: [PATCH 2/4] btrfs: remove redundant check at find_first_extent_bit_state() Date: Wed, 2 Apr 2025 15:54:10 +0100 Message-Id: <53332cd42e8da6a425195ce329c9c571c6d3a4e6.1743604119.git.fdmanana@suse.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 From: Filipe Manana The tree_search() function always returns an entry that either contains the search offset or the first entry in the tree that starts after the offset. So checking at find_first_extent_bit_state() if the returned entry ends at or after the search offset is pointless. Remove the check. Signed-off-by: Filipe Manana --- fs/btrfs/extent-io-tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/fs/btrfs/extent-io-tree.c b/fs/btrfs/extent-io-tree.c index 355c24449776..18b10e7ed815 100644 --- a/fs/btrfs/extent-io-tree.c +++ b/fs/btrfs/extent-io-tree.c @@ -877,7 +877,7 @@ static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *t */ state = tree_search(tree, start); while (state) { - if (state->end >= start && (state->state & bits)) + if (state->state & bits) return state; state = next_state(state); } From patchwork Wed Apr 2 14:54:11 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filipe Manana X-Patchwork-Id: 14036122 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (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 C2B0023C8CC for ; Wed, 2 Apr 2025 14:54:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605659; cv=none; b=jxExqnOfqYtp+1aijlLA5wL0xiVzyEB78CWMQu8oZu8FMflqxg2ZlwcyKFB16AXYkTbpmIdcUDFJGsebpJ9FQasu5GkZPYb+pcjUEkneGx4C1zPHKlpJI8WmOlRwL11ZVcDakQqYFnfIcRypQ+Qf1i7G844dXpLOCteVonehH3o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605659; c=relaxed/simple; bh=qoPaV5QdIf7LLDf5kvIo+S19fQ80L0RJa7HzjpxuBno=; h=From:To:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=hpRL0dJA+CNX2dYdRF4e82IcSoEGyMDTXiDu9paxfu8wTVgmz8pKiGU4G0YSUZzx1/iFlOzY3UBXEhAYF9GPikD/fEVTxQw6DOOaSXatsBUQwDMymJqJ3xQ3N1lLJkzEtFXIQDbTnjA5XK3gtFyk4K63hxpEM3GA47ymTuINzjg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=ZQ/pMfgl; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="ZQ/pMfgl" Received: by smtp.kernel.org (Postfix) with ESMTPSA id BFCE4C4CEEA for ; Wed, 2 Apr 2025 14:54:18 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1743605659; bh=qoPaV5QdIf7LLDf5kvIo+S19fQ80L0RJa7HzjpxuBno=; h=From:To:Subject:Date:In-Reply-To:References:From; b=ZQ/pMfgl8xzR7H451jjTvfQJ5VoSKfdo75tooKFTRZeXUi9koO5bANhvoOugyMYzj mYhxoxxLZIm+sYlKDsxWWW7gD+MM4JWL7mQYQsiHTJRJQZV+3u1bYw24y4hiKMzlzG MCIJYxa9Ieszm+13MXzYsr7QXIL6cnaHZTZR9Cw2x2e9Nu6GXu480J7YtoaTz0blpr Ljf18g0EUS0dZZNFFHMNmQUkkwapbSzGqwkW5YCLnvTVbNAo9zU2bqq0OVhrBlk6ci VmdRrtmvr5TwbZkE2ch0bS+YbBJieX6aTyNWNAa5Y78RKajMnTptiySggi3zMyoTa6 q2j+9fSrzPbcw== From: fdmanana@kernel.org To: linux-btrfs@vger.kernel.org Subject: [PATCH 3/4] btrfs: simplify last record detection at test_range_bit() Date: Wed, 2 Apr 2025 15:54:11 +0100 Message-Id: <53c0bc370a45abf176ec74d1257f66cbdfdb645b.1743604119.git.fdmanana@suse.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 From: Filipe Manana The overflow detection for the start offset of the next record is not really necessary, we can just stop iterating if the current record ends at or after out end offset. This removes the need to test if the current record end offset is (u64)-1 and to check if adding 1 to the current end offset results in 0. By testing only if the current record ends at or after the end offset, we also don't need anymore to test the new start offset at the head of the while loop. This makes both the source code and assembly code simpler, more efficient and shorter (reducing the object text size). Also remove the pointless initializion to NULL of the state variable, as we don't use it before the first assignment to it. This may help avoid some warnings with clang tools such as the one reported/fixed by commit 966de47ff0c9 ("btrfs: remove redundant initialization of variables in log_new_ancestors"). Signed-off-by: Filipe Manana --- fs/btrfs/extent-io-tree.c | 13 ++++--------- 1 file changed, 4 insertions(+), 9 deletions(-) diff --git a/fs/btrfs/extent-io-tree.c b/fs/btrfs/extent-io-tree.c index 18b10e7ed815..b321f826d008 100644 --- a/fs/btrfs/extent-io-tree.c +++ b/fs/btrfs/extent-io-tree.c @@ -1790,7 +1790,7 @@ void get_range_bits(struct extent_io_tree *tree, u64 start, u64 end, u32 *bits, bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, struct extent_state *cached) { - struct extent_state *state = NULL; + struct extent_state *state; bool bitset = true; ASSERT(is_power_of_2(bit)); @@ -1801,7 +1801,7 @@ bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, state = cached; else state = tree_search(tree, start); - while (state && start <= end) { + while (state) { if (state->start > start) { bitset = false; break; @@ -1815,16 +1815,11 @@ bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, break; } - if (state->end == (u64)-1) + if (state->end >= end) break; - /* - * Last entry (if state->end is (u64)-1 and overflow happens), - * or next entry starts after the range. - */ + /* Next state must start where this one ends. */ start = state->end + 1; - if (start > end || start == 0) - break; state = next_state(state); } From patchwork Wed Apr 2 14:54:12 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filipe Manana X-Patchwork-Id: 14036123 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (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 7A82723CEF7 for ; Wed, 2 Apr 2025 14:54:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605660; cv=none; b=ZdxhEtNvbWNwpkI+pzFd6oSJioFy+nliLvqnqXH2hfIilWcfI9HZvtPwgs9la0vxRnfD4TnTe8o24juITgOmSH26t4e62NzdQVtecbdJuDvbK/vhyeMhZFiZcNzIHZ1Nhq42uhA2NSu/XQz7gdwtBtBN8hqj5OjEWhu1LmfJRN4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1743605660; c=relaxed/simple; bh=TIqodMa/kk2byT3jWMKDCpe65AvXRgvOvSZ6/O0v6EI=; h=From:To:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=eEL5vDRIFvkQXPuqVYihtTDch5+ltvNDYWwU1mFbLZbsbASUlvulFKnBLDRd2LdE8fZJv6Crk/Nd6Bua6ducfKfAwg7gLhmuaCNgh3JKVp1NPEhViYHnNPcj1HFx2GsB6pv21NljCPX04WuBc1jvM6y6fswcrTyUUD83NippgO0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=vGqbqJNP; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="vGqbqJNP" Received: by smtp.kernel.org (Postfix) with ESMTPSA id C6A6EC4CEDD for ; Wed, 2 Apr 2025 14:54:19 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1743605660; bh=TIqodMa/kk2byT3jWMKDCpe65AvXRgvOvSZ6/O0v6EI=; h=From:To:Subject:Date:In-Reply-To:References:From; b=vGqbqJNPZKIoUypSKsKKcBvPnFaDByscKb1s6qQS6CxGOprxLma1ZvSzLaRkMuLfq t5RALgU3uwolK+td7YXmdyQi9phSH+NJLjQS4x5Jc6GrF2cekVXBCNk5U9XgevfqX0 fuUL3F5OZjcS4GQ1e6oyEPnmYfzwSDgyPgS7e80UYiwT2G1ERbKMNfDdXP5N8dIqa+ cfE6fEupAFpYMJ6qXD0rqs3rVAZR+6i+ZfhMEID+uSzL55MK0PRBRRE11zJwYLk5Jx sVMtPBj/LRdSho8ZXzLpTXOElg3fqUAO05GurdErLzXo5mk9trcHCSBp8oENV2RJ85 5OaLt1b4L26lw== From: fdmanana@kernel.org To: linux-btrfs@vger.kernel.org Subject: [PATCH 4/4] btrfs: remove redudant record start offset check at test_range_bit() Date: Wed, 2 Apr 2025 15:54:12 +0100 Message-Id: X-Mailer: git-send-email 2.34.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 From: Filipe Manana It's pointless to check if the current record's start offset is greater than the end offset, as before we just tested if it was greater than the start offset - and if it's not it means it's less than or equal to the start offset, so it can not be greater than the end offset, as our start offset is always smaller than the end offset. So remove that check and also add an assertion to verify the start offset is smaller then the end offset. Signed-off-by: Filipe Manana --- fs/btrfs/extent-io-tree.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/fs/btrfs/extent-io-tree.c b/fs/btrfs/extent-io-tree.c index b321f826d008..d833ab2d69a1 100644 --- a/fs/btrfs/extent-io-tree.c +++ b/fs/btrfs/extent-io-tree.c @@ -1794,6 +1794,7 @@ bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, bool bitset = true; ASSERT(is_power_of_2(bit)); + ASSERT(start < end); spin_lock(&tree->lock); if (cached && extent_state_in_tree(cached) && cached->start <= start && @@ -1807,9 +1808,6 @@ bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, break; } - if (state->start > end) - break; - if ((state->state & bit) == 0) { bitset = false; break;