From patchwork Tue Jan 28 16:38:39 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860511 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) (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 DE29A1DE3A3 for ; Tue, 28 Jan 2025 16:39:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082354; cv=none; b=nAQjZPLd4L6WJ/uWmB5FqbrThBHZ4oCsQiwP8+Mew934EJD4zi3BUQ1nHztlz107LjBz2Yb3jno4kWxILm0k1Rarb+Kjt/d612L3Qd2qtuh8BaMF4U5xyUZwHton/cFsRWY2ZH8mY3qsU9OZxDet87vnRhKMeDEyCwRQD+XAjtc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082354; c=relaxed/simple; bh=QSSCrbCHUTi6mmqQy8079+qeB9Q6HjqXahfBctCfGfQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=folqWzKoProk7OeEXHy5KGPpUxvO0SAN878E5qm0ZcSOgNnY6Mv3kbZJXkelzHj8+gIn1sGqBToAwc8cgjPU9qlOJB5vUlnGPiz/y+leaijqe0QkmLO8/40zDUn9eo9gfY7PCSBxkOFbKEluYQoVqooEu+vxbJuiHOVglGc22fg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=VhLWYtv6; arc=none smtp.client-ip=170.10.129.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="VhLWYtv6" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082351; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=xPqh7tzevPX9P8a6Tkudby8UMfLNbKjPJVuBI0QzHUE=; b=VhLWYtv6mOgKs1pGPIaQhu1VH4tN90+Ay+QjfYHxsEGN86iRJxycq3lltSmbpKoMJp27+5 yzNh76dXNlG/IOq8rdCw9S8VmWVonLabxHfYiI0qEYg/ehr4SQUUu1d8AVjhnv7JpJvtlk tSyCWpPeykwk2AJS7RU5Edc396yD7pk= Received: from mx-prod-mc-06.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-219-jHDZR_QFP4W_0og6MO-dQg-1; Tue, 28 Jan 2025 11:39:09 -0500 X-MC-Unique: jHDZR_QFP4W_0og6MO-dQg-1 X-Mimecast-MFC-AGG-ID: jHDZR_QFP4W_0og6MO-dQg Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 0B02118009E5; Tue, 28 Jan 2025 16:39:08 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 26217180035E; Tue, 28 Jan 2025 16:39:05 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 02/21] bcachefs: bch2_blacklist_entries_gc cleanup Date: Tue, 28 Jan 2025 17:38:39 +0100 Message-ID: <20250128163859.1883260-3-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 Use an eytzinger0_for_each loop here. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/journal_seq_blacklist.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/fs/bcachefs/journal_seq_blacklist.c b/fs/bcachefs/journal_seq_blacklist.c index 1f25c111c54c..e463d2d95359 100644 --- a/fs/bcachefs/journal_seq_blacklist.c +++ b/fs/bcachefs/journal_seq_blacklist.c @@ -231,15 +231,14 @@ bool bch2_blacklist_entries_gc(struct bch_fs *c) struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table; BUG_ON(nr != t->nr); - unsigned i; - for (src = bl->start, i = t->nr == 0 ? 0 : eytzinger0_first(t->nr); - src < bl->start + nr; - src++, i = eytzinger0_next(i, nr)) { + src = bl->start; + eytzinger0_for_each(i, nr) { BUG_ON(t->entries[i].start != le64_to_cpu(src->start)); BUG_ON(t->entries[i].end != le64_to_cpu(src->end)); if (t->entries[i].dirty || t->entries[i].end >= c->journal.oldest_seq_found_ondisk) *dst++ = *src; + src++; } unsigned new_nr = dst - bl->start; From patchwork Tue Jan 28 16:38:41 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860510 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) (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 5EA2F1DE3AB for ; Tue, 28 Jan 2025 16:39:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082361; cv=none; b=Cs4mbtw96dOcRf5n7+o/S6uVzJDejH+uftiB4A1krtKALEKyJzTyfneJUwHA7g2HOQC1ezjKt/amJph4GWo9kAdcpfCPJ6djyQ+tv4TDEbTBm/erEz2sPCIz7571HKdHNmHEXo24mhs6BhiK1W2dNCq7/Ziuha5DQggXdJG2vf8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082361; c=relaxed/simple; bh=80V5ZD3kqKIEt9ykSkK9ujmtNKhjg0TdGjBMSGp3CxM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Efc8v+AwhUYAtgPtt30JcG5T6xjCMoq/SUkM1G16zG3+BOY6uId/hBsXXCnihYOE4IVvr0G5JjSQ6TfNAi1v6ffPXs5rqZPRwTaDJA60NP1+GwO8i2MKwNE/CHQGNTRbyyN4PPs6sxDxAgg+5X8f3Bo1D/yOXDtx7jfBycn3vso= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=KHlGokxM; arc=none smtp.client-ip=170.10.129.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="KHlGokxM" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082359; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=RFsVTpVx9tfu2gtY/FcLf9k1nGGY3NJBOkFAp0nnMYI=; b=KHlGokxMQmudMPJFBUAtrUxMCDuWjNw/Zj5LsR4MPBVXq7kv49wjz7QtcbIXy0Hlq7nAb7 1vUb/PjZac7a5PnMGcnX34PvDyb7WPULV+qp2ayLmViWcF8tVGuKjiQtQCWA0Opn+laRSz J4npp5vxy+KpqBSmcHjJKH56F8ngjM0= Received: from mx-prod-mc-05.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-493-i_O4QtVUMoCT3VCvHwK1gA-1; Tue, 28 Jan 2025 11:39:13 -0500 X-MC-Unique: i_O4QtVUMoCT3VCvHwK1gA-1 X-Mimecast-MFC-AGG-ID: i_O4QtVUMoCT3VCvHwK1gA Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-05.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id CB4CB195608B; Tue, 28 Jan 2025 16:39:12 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id EB4A4180035E; Tue, 28 Jan 2025 16:39:10 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 04/21] bcachefs: EYTZINGER_DEBUG fix Date: Tue, 28 Jan 2025 17:38:41 +0100 Message-ID: <20250128163859.1883260-5-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 When EYTZINGER_DEBUG is defined, needs to be included. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 1 + 1 file changed, 1 insertion(+) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 16303908ccff..6fa6d51a5420 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -8,6 +8,7 @@ #define EYTZINGER_DEBUG #ifdef EYTZINGER_DEBUG +#include #define EYTZINGER_BUG_ON(cond) BUG_ON(cond) #else #define EYTZINGER_BUG_ON(cond) From patchwork Tue Jan 28 16:38:43 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860509 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 654261DE3AB for ; Tue, 28 Jan 2025 16:39:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082363; cv=none; b=O8qxpbb47Kt8psZh/Rq5qIRDMtC/MZ9Gzqn9XdgcACpkK4IzEyRhQFuDHEfV61O/XF49rg0GnW0fdJVZfp7QOb8SzWK650rCCOlnX04QhDJH9Gdjx1vnN+w+mUg7Fw+Ww1NaOr+q+d8SHQYr6bA+Ml0gQTRW+FwFHTdPicjQsHA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082363; c=relaxed/simple; bh=RLhmpcLSLz2d4R2iTc94unl567IghN9yXrv2qbuFyCI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=GQg1PBnuEqrUCFRRXRav2Au9T4TC9fOQ/7K8o707XJOpMdS6DNZezgaWTjzLz6LbPdeR6qkGGmRjEDkZt5K7BDKI9uRSrnNG4xujHJJdzsmQm6zdX8O6APMrvg1oNSUgWFOKy3456rkhAvViD1kDPcKe2XgP2Or17ajzW20xKXk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=g30XD/gV; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="g30XD/gV" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082361; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=GcbXjcntav8HQWgL6QsKfaxRCHFx880QRWv2hDtxguE=; b=g30XD/gVHQyY8ItdIlR0M+zIoyuJu+2pizPniwF9RnE8NQ2443/e5jaRyBhUq9jZ2jP1XY T4YSUaPR0vAbZDBI8/Ht3LZQbe94TZmArwAYXci7IJdoqe2urK1NlV3HFIcWcyYM8jiAkR +xL7+mjiZPFh+w8MfiFJvzK9Tk5MSqM= Received: from mx-prod-mc-06.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-410-cCPWAJv_Mw2lxzWfMVwm3Q-1; Tue, 28 Jan 2025 11:39:19 -0500 X-MC-Unique: cCPWAJv_Mw2lxzWfMVwm3Q-1 X-Mimecast-MFC-AGG-ID: cCPWAJv_Mw2lxzWfMVwm3Q Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id B07BA1800366; Tue, 28 Jan 2025 16:39:17 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id DDC0618008C8; Tue, 28 Jan 2025 16:39:15 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 06/21] bcachefs: eytzinger self tests: missing newline termination Date: Tue, 28 Jan 2025 17:38:43 +0100 Message-ID: <20250128163859.1883260-7-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 pr_info() format strings need to be newline terminated. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 58a7b962847d..7cf319290a88 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -703,7 +703,7 @@ void eytzinger1_test(void) { unsigned inorder, size; - pr_info("1 based eytzinger test:"); + pr_info("1 based eytzinger test:\n"); for (size = 2; size < 65536; @@ -711,7 +711,7 @@ void eytzinger1_test(void) unsigned extra = eytzinger1_extra(size); if (!(size % 4096)) - pr_info("tree size %u", size); + pr_info("tree size %u\n", size); BUG_ON(eytzinger1_prev(0, size) != eytzinger1_last(size)); BUG_ON(eytzinger1_next(0, size) != eytzinger1_first(size)); @@ -736,7 +736,7 @@ void eytzinger0_test(void) unsigned inorder, size; - pr_info("0 based eytzinger test:"); + pr_info("0 based eytzinger test:\n"); for (size = 1; size < 65536; @@ -744,7 +744,7 @@ void eytzinger0_test(void) unsigned extra = eytzinger0_extra(size); if (!(size % 4096)) - pr_info("tree size %u", size); + pr_info("tree size %u\n", size); BUG_ON(eytzinger0_prev(-1, size) != eytzinger0_last(size)); BUG_ON(eytzinger0_next(-1, size) != eytzinger0_first(size)); @@ -788,8 +788,8 @@ static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) if (c1 != c2) { eytzinger0_for_each(j, nr) - pr_info("[%3u] = %12u", j, test_array[j]); - pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", + pr_info("[%3u] = %12u\n", j, test_array[j]); + pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n", i, r, c1, c2); } } @@ -800,7 +800,7 @@ void eytzinger0_find_test(void) u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); for (nr = 1; nr < allocated; nr++) { - pr_info("testing %u elems", nr); + pr_info("testing %u elems\n", nr); get_random_bytes(test_array, nr * sizeof(test_array[0])); eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); From patchwork Tue Jan 28 16:38:45 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860508 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 08F901DE3A9 for ; Tue, 28 Jan 2025 16:39:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082369; cv=none; b=GMtPE0F3GrC5vLzVF1Uv/lZLFdXIQEX2MZW1PsD2vyw6b8wUoiQRYWPEartmd5KdTub/cf8l8ue1aO55aQB1MVOJvhFhOQMPPQu9tHUa9b2KkHa+5sKdL6DxnaW1O1iUbe4cJkdIMnROMnZxuVy1iu0zAwvYC+RpXo+5IJTCE8M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082369; c=relaxed/simple; bh=/KpLabA68Ak2gO3Zh94uYnvL6rYJdCKG7nz2pp0x+k0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=k1UJ4kspdE5OZR1y/wIV4MpfaBDQ30WBHgRGbqzPhUyS8rdgssyiPnQDz9FkwWB3NfqeRfjb0Oxgh+xvqyx0L7jxmsFIEMr9V6Ht59epd2172vh6liZcB5XlWcKeRDSoS5jnbYcgjWYTskuZEHaOzlJPlifv41rMNHQiTAhZiLk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=ZOJeXyw8; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="ZOJeXyw8" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082367; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=jiV6Ffp4rIGL2pzCQowSbFsXQuw9liHvQJLcfMUmaC4=; b=ZOJeXyw8Zy99mwvyj5ooQ1Tlgq3UCJkvMXoePc2IPcSI5x38tI7APdq4Km6lOW1cHnSm0H TcLAryYGYelu13xJKQ8gBtHrYHXYnEbe5JJmG1gP+nybTXIJcH5qzxbaBM9TIzVJ6Veqch ivZA1COUhYF7ST82QIE6Qa6318CN0Ak= Received: from mx-prod-mc-04.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-524-NoLPzyDaOg-Hq3XADMbm4g-1; Tue, 28 Jan 2025 11:39:23 -0500 X-MC-Unique: NoLPzyDaOg-Hq3XADMbm4g-1 X-Mimecast-MFC-AGG-ID: NoLPzyDaOg-Hq3XADMbm4g Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-04.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 9D7FE1955DCD; Tue, 28 Jan 2025 16:39:22 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id A205C18008D4; Tue, 28 Jan 2025 16:39:20 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 08/21] bcachefs: eytzinger[01]_test improvement Date: Tue, 28 Jan 2025 17:38:45 +0100 Message-ID: <20250128163859.1883260-9-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 In eytzinger[01]_test(), make sure that eytzinger[01]_for_each() iterates over all array elements. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 0ffbd22d3a5e..4122012ddfb2 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -728,6 +728,7 @@ void eytzinger1_test(void) inorder++; } + BUG_ON(inorder - 1 != size); } } @@ -761,6 +762,7 @@ void eytzinger0_test(void) inorder++; } + BUG_ON(inorder != size); } } From patchwork Tue Jan 28 16:38:48 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860507 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 4FF891DE3A4 for ; Tue, 28 Jan 2025 16:39:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082375; cv=none; b=semIJzaIdDgoA2wwtS/+K6zgIX2JKbxh/wFyPib42Aalx4HBhyMxL/DqQKsFwl29pEKgk+co2xscPE6Dm9By9IHwAr60shLHXb9yMa5HzBEkqePovFCRtPhKwtzVOERIIx6EdRfUKgxtH2a1GLhZ35QW8CDxARLPO9K9h4hQ1KA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082375; c=relaxed/simple; bh=xYYKSzeUNhktelKMGtWaDjWVNkHylHHNM7lBAJ0mpXU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=t4DbpbLA+79H0X/+kW0kxPFno5uVgU07o2+43KBlxsW3UEUIV3FK0Rvl/0wCkliFEBKzJAfIJSL3mg8VwA2OCCImoMB2ExlNFEDf+5dfNT6dAR1kAAhX8oE5OrgFSqyxlINzs8J8WQ4z/Sw3A91lsFRTQvLGLNeiIhLDhZY3dMY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=axO6gsMo; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="axO6gsMo" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082373; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=jSTjRU8OGvFCT9OatwrBdkc0jw3p9R5xmeWWLyB1Jg8=; b=axO6gsMoqRIlUH43jnoxOfr+KR2J/FnLGu9WiP2o1Z0PTz4ucjzMW5hLXn2IYljT6GsdI9 qwKB8dRyt9dQtJ+SPlzJWMwt3p+7XhG9dqJmImzhiXX7QdHEFGulK14EDqZMQXgYwD6Tja ra2uajBeJICsnx1GAGDmZSLoe27vDpg= Received: from mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-692-0Me6OjgyPEOTm2bDVyCZGg-1; Tue, 28 Jan 2025 11:39:31 -0500 X-MC-Unique: 0Me6OjgyPEOTm2bDVyCZGg-1 X-Mimecast-MFC-AGG-ID: 0Me6OjgyPEOTm2bDVyCZGg Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id A2EE11800373; Tue, 28 Jan 2025 16:39:29 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id CD98D180035E; Tue, 28 Jan 2025 16:39:27 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 11/21] bcachefs: improve the eytzinger0_find_le tests Date: Tue, 28 Jan 2025 17:38:48 +0100 Message-ID: <20250128163859.1883260-12-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 Rename eytzinger0_find_test_val() to eytzinger0_find_test_le() and add a new eytzinger0_find_test_val() wrapper that calls it. We have already established that the array is sorted in eytzinger order, so we can use the eytzinger iterator functions and check the boundary conditions to verify the result of eytzinger0_find_le(). Only scan the entire array if we get an incorrect result. When we need to scan, use eytzinger0_for_each_prev() so that we'll stop at the highest matching element in the array in case there are duplicates; going through the array linearly wouldn't give us that. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 41 ++++++++++++++++++++++++++++++----------- 1 file changed, 30 insertions(+), 11 deletions(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 3fe9a3b8c696..c772629783f3 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -782,29 +782,48 @@ static inline int cmp_u16(const void *_l, const void *_r) return (*l > *r) - (*r > *l); } -static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) { - int i, c1 = -1, c2 = -1; - ssize_t r; + int r, s; + bool bad; r = eytzinger0_find_le(test_array, nr, sizeof(test_array[0]), cmp_u16, &search); - if (r >= 0) - c1 = test_array[r]; + if (r >= 0) { + if (test_array[r] > search) { + bad = true; + } else { + s = eytzinger0_next(r, nr); + bad = s >= 0 && test_array[s] <= search; + } + } else { + s = eytzinger0_last(nr); + bad = s >= 0 && test_array[s] <= search; + } - for (i = 0; i < nr; i++) - if (test_array[i] <= search && test_array[i] > c2) - c2 = test_array[i]; + if (bad) { + s = -1; + eytzinger0_for_each_prev(j, nr) { + if (test_array[j] <= search) { + s = j; + break; + } + } - if (c1 != c2) { eytzinger0_for_each(j, nr) pr_info("[%3u] = %12u\n", j, test_array[j]); - pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i\n", - i, r, c1, c2); + pr_info("find_le(%12u) = %3i should be %3i\n", + search, r, s); + BUG(); } } +static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) +{ + eytzinger0_find_test_le(test_array, nr, search); +} + void eytzinger0_find_test(void) { unsigned i, nr, allocated = 1 << 12; From patchwork Tue Jan 28 16:38:49 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860506 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 616291DE3B3 for ; Tue, 28 Jan 2025 16:39:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082379; cv=none; b=ok0huyKEWgEiXRuHf3JQW8Fy1L3VC4KpVNFtV6ZJSluNqQGRq4LQX0xNSwhShISRSReDQeymxX1BtlwrIKKGbqBWLpRuhI+6cYwmrTJHGapUQ9zFaCbge8pJq40hw87fy4YucSPJwkRIBelip15G1oz4ZkQwAHvuAaLQLmo/pck= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082379; c=relaxed/simple; bh=LG8n3miZYclcHNS+6JY2e+S4GP1ksWsI7kF8xUhji2A=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=qQ1KUEUJvfE5/9ZarQCVjvO47ZSAlnhyCbFHC0U1gpq3MEdXEuYAlgLHFcbFlt1m1o2XOidAOm47xz0URJzlPBf0KPC/ujfYKZ2rZGaQ/2ZKoSkBAwPzImx2KhseTzSOvh6ycbEiz0kW2CdiezDOueOdp1VqyPc/YanYr840cZE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=OQLDKcse; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="OQLDKcse" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082377; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=M2Ve77QJmE41Ot0UBKq5NH4Iw6Uhwg4TTTg428aDJSU=; b=OQLDKcseagwtgQci3L1TWFaTfAzwb1apNiLx/JxwI4HYjMRSky8vgECAYGNbRRPPc95q8A q7PUK5iQ6yqR33gYuIlUOV6D4BVwb9oGKnQK8edIgbooc2J+pD2r/2FSN+UvhMBw/lY2Zy xCIpkzKu6aIEb2yK2ljop22Zge+qN14= Received: from mx-prod-mc-02.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-270-fvPVB1yJMdCWjwHQO-bn9Q-1; Tue, 28 Jan 2025 11:39:34 -0500 X-MC-Unique: fvPVB1yJMdCWjwHQO-bn9Q-1 X-Mimecast-MFC-AGG-ID: fvPVB1yJMdCWjwHQO-bn9Q Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-02.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 044671955DC6; Tue, 28 Jan 2025 16:39:32 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 2C04518008C8; Tue, 28 Jan 2025 16:39:29 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 12/21] bcachefs: convert eytzinger0_find to be 1-based Date: Tue, 28 Jan 2025 17:38:49 +0100 Message-ID: <20250128163859.1883260-13-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 Several of the algorithms on eytzinger trees are implemented in terms of the eytzinger0 primitives. However, those algorithms can just as easily be expressed in terms of the eytzinger1 primitives, and that leads to better and easier to understand code. Start by converting eytzinger0_find(). Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index f25c895aa184..d3e8b9edf335 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -307,17 +307,17 @@ static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, #define eytzinger0_find(base, nr, size, _cmp, search) \ ({ \ - void *_base = (base); \ + size_t _size = (size); \ + void *_base1 = (base) - _size; \ const void *_search = (search); \ size_t _nr = (nr); \ - size_t _size = (size); \ - size_t _i = 0; \ + size_t _i = 1; \ int _res; \ \ - while (_i < _nr && \ - (_res = _cmp(_search, _base + _i * _size))) \ - _i = eytzinger0_child(_i, _res > 0); \ - _i; \ + while (_i <= _nr && \ + (_res = _cmp(_search, _base1 + _i * _size))) \ + _i = eytzinger1_child(_i, _res > 0); \ + _i - 1; \ }) void eytzinger0_sort_r(void *, size_t, size_t, From patchwork Tue Jan 28 16:38:51 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860505 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 514191DE3BA for ; Tue, 28 Jan 2025 16:39:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082383; cv=none; b=Gv7Fngd+tDd8N+a8yJHOA460Lc/vDwf9LB2cvH/sZVH+3/759yKmmE+I593XlUlun4nFIWeJsIY3hPFnOR1VNreTdrmHf7+MaZ+MfnEchBI1iWlWM2IhF02JLymLzFPQ0N9qD/1IBQ+SAsjazXV3+RialxWpgjte42INjwKEa00= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082383; c=relaxed/simple; bh=cA0DcHmOCbjpertJ2WrDIHOP2x5boUglDbhmPkrFt9k=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=bTEq3usTWB0YjlfC3m3LVx7OVf37zJSJyag/U2KWvrBuSjGCT9UJEGozGavoXrNXIrqXZo+Iaavfx6w7oY91CEAlXj2flQ6lIB23cqsbp+qkI+nwuhVfC3ZiUZGHPLq2Wdrj/Tz2fgC3sP+nHdEu62VJZuSD6q613+rp6s00vi4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=EfvGG1k6; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="EfvGG1k6" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082381; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=PZd8+r0Ld1kBa8nPrqbyJF0th13OifpvbO/JPmMcyGI=; b=EfvGG1k6KTubg3/vpgdWB+7LmOHLFBzQTIK3yf+V56JI5PO/KYOXAcdLg1GX1AzIPrNrCK zZzWA66KEYV2AD8egmrDOuIASHK6fLCNYtfnr1ls2G2mfDs8llmL8IfCq9ChQwe9i0189+ vW7O4ogHuzkV+mFEvRJWXH7cLlDp0XY= Received: from mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-450-RWm3NFUJNJiinvZ0xkH_Dw-1; Tue, 28 Jan 2025 11:39:38 -0500 X-MC-Unique: RWm3NFUJNJiinvZ0xkH_Dw-1 X-Mimecast-MFC-AGG-ID: RWm3NFUJNJiinvZ0xkH_Dw Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id A96D819560B2; Tue, 28 Jan 2025 16:39:36 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id CC2DC18008C0; Tue, 28 Jan 2025 16:39:34 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 14/21] bcachefs: simplify eytzinger0_find_le Date: Tue, 28 Jan 2025 17:38:51 +0100 Message-ID: <20250128163859.1883260-15-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 Replace the over-complicated implementation of eytzinger0_find_le() by an equivalent, simplifer version. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 26 ++++++-------------------- 1 file changed, 6 insertions(+), 20 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 130f5fe30bd7..89a0e4192212 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -256,26 +256,12 @@ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { void *base1 = base - size; - unsigned i, n = 1; - - if (!nr) - return -1; - - do { - i = n; - n = eytzinger1_child(i, cmp(base1 + i * size, search) <= 0); - } while (n <= nr); - - if (!(n & 1)) { - /* - * @i was greater than @search, return previous node: - * - * if @i was leftmost/smallest element, - * eytzinger1_prev(eytzinger1_first())) returns 0, as expected - */ - i = eytzinger1_prev(i, nr); - } - return i - 1; + unsigned n = 1; + + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) <= 0); + n >>= __ffs(n) + 1; + return n - 1; } static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, From patchwork Tue Jan 28 16:38:53 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860504 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 0202D1DE3A4 for ; Tue, 28 Jan 2025 16:39:47 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082389; cv=none; b=BghLwaWjZdADrdtCWhYoatRLecn4+eWe96cXInobtbFiu1hjMhiG9sLH9xWQStzTujmLw7sjI9ohVaUk2cP0UvlGeSTsOtUAMTv1M5F/zfRfF7LLeqhKPXjR5X3in02trTF4ahZ3bhX0oWLN5xPKGXJJ0Poejf34AiYN5CAnsqM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082389; c=relaxed/simple; bh=hCYzWmeREswyOqDKN0hO11Gqo6hqhwbVhxuhpDZUWFo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=BGAGjEhoSZ0q5YghvRrq//8xsEI+Fq9Q7lRpFTfVVoKZ/cw5L5h79Sa9hi71aj5xMX3z2SAHYPupsD3L5RrpAcW57PXd65JTrtixAS8epeWzhvpmjP/4r8cRjxR6Lc7sOqf7jDheqgAev7Fy0fk/qBKdpxZJ4dzRvY/se5Ye3bA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=Jr7XZohe; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="Jr7XZohe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082387; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=kiKzAzNKHRucdz5+dAtojCcsKcpO9nfZcdT/qXSkqrk=; b=Jr7XZohejkUq5bhD3EZ8ATmxtTCt51njdgSV1uF0WI7NfHbo7wXTTkRk/xdh3SiPwwqun4 REXH4xa8whxvvV/BkB3CNnXasgsmlpUbarugCpQkWqmy4tt/s+X20QCw3DivqUFNIk6jDV PT9eHCO4WL/l/xTYyaaJLdNSNPrLT+o= Received: from mx-prod-mc-06.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-466-3ilIVotcOpOy5CXDdqeTDQ-1; Tue, 28 Jan 2025 11:39:42 -0500 X-MC-Unique: 3ilIVotcOpOy5CXDdqeTDQ-1 X-Mimecast-MFC-AGG-ID: 3ilIVotcOpOy5CXDdqeTDQ Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id B1D8B1800268; Tue, 28 Jan 2025 16:39:41 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id D96D3180035E; Tue, 28 Jan 2025 16:39:39 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 16/21] bcachefs: implement eytzinger0_find_gt directly Date: Tue, 28 Jan 2025 17:38:53 +0100 Message-ID: <20250128163859.1883260-17-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 Instead of implementing eytzinger0_find_gt() in terms of eytzinger0_find_le() and adjusting the result, implement it directly. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 89a0e4192212..a5a1abae5b13 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -264,20 +264,17 @@ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, return n - 1; } +/* return smallest node > @search, or -1 if not found */ static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search); + void *base1 = base - size; + unsigned n = 1; - /* - * if eytitzinger0_find_le() returned -1 - no element was <= search - we - * want to return the first element; next/prev identities mean this work - * as expected - * - * similarly if find_le() returns last element, we should return -1; - * identities mean this all works out: - */ - return eytzinger0_next(idx, nr); + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) <= 0); + n >>= __ffs(n + 1) + 1; + return n - 1; } static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, From patchwork Tue Jan 28 16:38:55 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860503 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) (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 BE5671DE3A4 for ; Tue, 28 Jan 2025 16:39:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082391; cv=none; b=nY3LsZX2rRC3h5iWm7HqzKJ1joW+ZN3NMvNpbjFvhCopJIZ6MgOt6K8Lwz+UY+PZ3KNsgLmVsyjiisGLEhD2/QFolvI8sOYlYvIRc4YYgC5lkZwG+ms12aX1s8d2bZodfGDqXo5VNve+v4zAppGoUWsDFIOxbzS0PamAfcINpTo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082391; c=relaxed/simple; bh=WT6LDUTqjhajsR2GRb9lcoCB8LRksI0PepNobb98dHM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=EHa6YjKQeJRhqbwHlV5DIP0+/nIxk+CWHSPYq8um8TQDsue2kWkJ/dRqlhqCFUQ6R6HwF9VtqDBcliZ5TyZ9KW5woBv2V4YTdaga9Opnc0d24kUdjEnliA3xWuM+rJ2j3CH2v+zsk8pyl8LBzbE3LjcyOcQXWp6FEaYIGghz4Js= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=EI8A3DN/; arc=none smtp.client-ip=170.10.129.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="EI8A3DN/" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082388; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=EQtguPtI0hZKEL7ASRVQSa5xY2NgHNYjl1fv4dXwRLM=; b=EI8A3DN/GQfrHWJFxsEjijDT63Ho1/Esr7yspiut0HhDmOp89FRRxeYHsPeHa+7Ugljz5i hfD2MIZ1gfUcu9IpdspJVySnfeP5R2U12aJmbLNF4K1zD1DfImgB7C7eMTGc6xdWaeYeju PsaGHfpjPXL/rBkbDrv9HRr31B5ReIk= Received: from mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-675-OQEGotc_MWaqkZKWCeUkkA-1; Tue, 28 Jan 2025 11:39:47 -0500 X-MC-Unique: OQEGotc_MWaqkZKWCeUkkA-1 X-Mimecast-MFC-AGG-ID: OQEGotc_MWaqkZKWCeUkkA Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 682051801882; Tue, 28 Jan 2025 16:39:46 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 888A618008C8; Tue, 28 Jan 2025 16:39:44 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 18/21] bcachefs: implement eytzinger0_find_ge directly Date: Tue, 28 Jan 2025 17:38:55 +0100 Message-ID: <20250128163859.1883260-19-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 Implement eytzinger0_find_ge() directly instead of implementing it in terms of eytzinger0_find_le() and adjusting the result. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index a5a1abae5b13..6a363b12bd21 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -277,15 +277,17 @@ static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, return n - 1; } +/* return smallest node >= @search, or -1 if not found */ static inline int eytzinger0_find_ge(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - ssize_t idx = eytzinger0_find_le(base, nr, size, cmp, search); - - if (idx < nr && !cmp(base + idx * size, search)) - return idx; + void *base1 = base - size; + unsigned n = 1; - return eytzinger0_next(idx, nr); + while (n <= nr) + n = eytzinger1_child(n, cmp(base1 + n * size, search) < 0); + n >>= __ffs(n + 1) + 1; + return n - 1; } #define eytzinger0_find(base, nr, size, _cmp, search) \ From patchwork Tue Jan 28 16:38:57 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 860502 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) (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 7969F1DE3AC for ; Tue, 28 Jan 2025 16:39:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082396; cv=none; b=iDYhtHwGxCohGLD61cd9XKgOvCqAseUWKL1oCptZix6ddWuBdfF0MjUtX0Xhnrv4wgcKSf67VNUSxZxE8chmLTQvPbDB0nSpvsXhXfBVTY1n9LDxxyGVqJab+ZR3aW5mooO8MQc6OvbbAfIpEt6+mbVBE1XaQP+A2o8aMoqaXS0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082396; c=relaxed/simple; bh=8tQ6XBEMYbx9V0iHjreFT9NgZ5mT2GIi/oiDgPetvHw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Zyd4BHeG4K+Je2p1xHp2UfxkjY1HJfG5eRophJc91iJlSa8rNvTlyL2Y5azWN7p20lbaFzQSnW7G05+6GGyPu2kVBagZ0DwftcwP9YtlWtM7fUhf+yO2Sp22MxprwfXba5vtzhN6PCS2ScZdEUXes/ZDLl4O7yw3QvCNKWcXt1s= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com; spf=pass smtp.mailfrom=redhat.com; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b=h2sIk1D4; arc=none smtp.client-ip=170.10.133.124 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=redhat.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=redhat.com header.i=@redhat.com header.b="h2sIk1D4" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082393; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=sNmPQEOvHYWrUX4j7maHpPPS+nivyRuwSBqiMy5hzYE=; b=h2sIk1D4BSXVy81dRV/fLVBddL06EGBxAgFjF4fWb5j44vwPZ65JekuoiI4HRj9FlKmId+ sysDQeLifGC2K72OqLlCPYlhrzUv80KwK2oJ4wZU4wHY1XgqWo2RqI2LHEglhcq/g3AYfb kgd9eapS9NiRLaZhoOK8/8M5kjIJEAA= Received: from mx-prod-mc-04.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-610-jGpuxaPmPfGE9fbCFRERiA-1; Tue, 28 Jan 2025 11:39:52 -0500 X-MC-Unique: jGpuxaPmPfGE9fbCFRERiA-1 X-Mimecast-MFC-AGG-ID: jGpuxaPmPfGE9fbCFRERiA Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-04.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 1BCB819560B4; Tue, 28 Jan 2025 16:39:51 +0000 (UTC) Received: from pasta.fast.eng.rdu2.dc.redhat.com (unknown [10.45.225.106]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 455DF180035E; Tue, 28 Jan 2025 16:39:49 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 20/21] bcachefs: convert eytzinger sort to be 1-based (2) Date: Tue, 28 Jan 2025 17:38:57 +0100 Message-ID: <20250128163859.1883260-21-agruenba@redhat.com> In-Reply-To: <20250128163859.1883260-1-agruenba@redhat.com> References: <20250128163859.1883260-1-agruenba@redhat.com> Precedence: bulk X-Mailing-List: linux-kselftest@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 In this second step, transform the eytzinger indexes i, j, and k in eytzinger1_sort_r() from 0-based to 1-based. This step looks a bit messy, but the resulting code is slightly better. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.c | 42 ++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-) diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 93a5819a6878..00cc5f0826e3 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -170,7 +170,7 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size, swap_r_func_t swap_func, const void *priv) { - int i, j, k; + unsigned i, j, k; /* called from 'sort' without swap function, let's pick the default */ if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap_func) @@ -186,46 +186,46 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size, } /* heapify */ - for (i = n / 2 - 1; i >= 0; --i) { + for (i = n / 2; i >= 1; --i) { /* Find the sift-down path all the way to the leaves. */ - for (j = i; k = j * 2 + 1, k + 1 < n;) - j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1; + for (j = i; k = j * 2, k < n;) + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1; /* Special case for the last leaf with no sibling. */ - if (j * 2 + 2 == n) - j = j * 2 + 1; + if (j * 2 == n) + j *= 2; /* Backtrack to the correct location. */ - while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i + 1, j + 1) >= 0) - j = (j - 1) / 2; + while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i, j) >= 0) + j /= 2; /* Shift the element into its correct place. */ for (k = j; j != i;) { - j = (j - 1) / 2; - eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); + j /= 2; + eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k); } } /* sort */ - for (i = n - 1; i > 0; --i) { - eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i + 1); + for (i = n; i > 1; --i) { + eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i); /* Find the sift-down path all the way to the leaves. */ - for (j = 0; k = j * 2 + 1, k + 1 < i;) - j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1; + for (j = 1; k = j * 2, k + 1 < i;) + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1; /* Special case for the last leaf with no sibling. */ - if (j * 2 + 2 == i) - j = j * 2 + 1; + if (j * 2 + 1 == i) + j *= 2; /* Backtrack to the correct location. */ - while (j && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j + 1) >= 0) - j = (j - 1) / 2; + while (j >= 1 && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j) >= 0) + j /= 2; /* Shift the element into its correct place. */ - for (k = j; j;) { - j = (j - 1) / 2; - eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); + for (k = j; j > 1;) { + j /= 2; + eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k); } } }