From patchwork Tue Jan 28 16:38:38 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952778 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 3B21F1DE2DF for ; Tue, 28 Jan 2025 16:39:10 +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=1738082352; cv=none; b=fqqsFXLX3g8HvnmjoJpS9nFDTNLI7+wOOLzGMBAYZDoUhbURZgSa+E0Hy0BPeumb4u/Do0rGQLBh0nXnj79lHd1W/kBVmcfKAhkVtOyWQmM9qC4lgp/iESvvjj+4cxMGu8dWzQdoNQZzQ77mdbJWFS2VJHiNET/L7wOCsfAUFBM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082352; c=relaxed/simple; bh=w527x+/NhVUL9yP2qw2Z9aDUTEwaqV205Icu1Yf0vqg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=NIhtlgLyR1rNZBwpVnhUhdfDs7gBq6P8ONlG5neazZS3y+y2Dq0aF09rnVO+T/y+lV+mHD0QHJjeTzSDtQ2oFMsTY3x2TSeULaCXnX6BuYRvfDL9PGzGWVQ85w7JJoaCmqnCgEhNttrow5TgheAltuhqMhvjJBXaAezll6TfIMk= 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=fUVgdNNE; 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="fUVgdNNE" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082350; 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=/oRKZspjjnbQgCvlCmKMk/rnifqjvsX5F8ZygRJOO1k=; b=fUVgdNNEOCjEUkihszSzBUxVBiAL0QUPbpo/0xjqfRHgUAn9wa6VPhPaY27JNf61JjUjn7 jErl2yy9ATtfLNWKwWcx5eMQfQerITbzIfkYX+S+PSA+i7ts+piQPgVRJxULifE+3e566w qrKTy9R7ZQ4EThFrCNiT2lWqNj9AogQ= Received: from mx-prod-mc-03.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-54-E8pEr2SSNi2FMZbt11YTXQ-1; Tue, 28 Jan 2025 11:39:06 -0500 X-MC-Unique: E8pEr2SSNi2FMZbt11YTXQ-1 X-Mimecast-MFC-AGG-ID: E8pEr2SSNi2FMZbt11YTXQ 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-03.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id A29EB19560BB; Tue, 28 Jan 2025 16:39:05 +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 B8108180035E; Tue, 28 Jan 2025 16:39:03 +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 01/21] bcachefs: remove dead code in is_aligned Date: Tue, 28 Jan 2025 17:38:38 +0100 Message-ID: <20250128163859.1883260-2-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 This statement does nothing. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.c | 1 - 1 file changed, 1 deletion(-) diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 2eaffe37b5e7..c0fdfe909cf2 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -20,7 +20,6 @@ static bool is_aligned(const void *base, size_t size, unsigned char align) { unsigned char lsbits = (unsigned char)size; - (void)base; #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS lsbits |= (unsigned char)(uintptr_t)base; #endif 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: 13952779 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:40 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952780 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 00FB01DE2C7 for ; Tue, 28 Jan 2025 16:39:15 +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=1738082358; cv=none; b=WAXa5awmyoV+Za1VdaWYxyqAM5Ei9UikJE20R0hSys+6fnR3bLDot0mrAXM3v4nC38iJ0fCSwg6uK6Br8oci6JgB9hWm2wGS1rfrqV5/wSO11m24O4ih6FQ4TQgOga+Ar54sghfMHirsJuVWiIZsJIkkt5OnIFWcxLeVzGOHX18= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082358; c=relaxed/simple; bh=EgLfDuwKZsdfjpSLwn6zWm6ZYKMx3rY9kKTB7LFXIA4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Y1LNmgG6q2UuTXyk+2TBn2xKWWG9zXUxLaRhE5ZodxlTQq5j6uyWTE7pBxxFOHmwHQAUNuTTlv/YYE4t/pS2vJv8SP/8AORAs38lvVTJ26Q8nysZigopvyT5Wrp8G2wAlDSow4mioeHzvjza3KaCAXHl5Xa9Gz7ohl8ht+/PdTw= 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=frvjIKZ+; 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="frvjIKZ+" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082354; 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=QGhonjcczzQ0bAfctgBIvgS7yZnG/z7g4mNrxvS9W2U=; b=frvjIKZ+HW0dt+NnBF2Xtff7EPuFDO8DFk9A53PgXZtWCQQBc9o64yKvoMhao3GEBcq+vb vqmBJp9VvKrPKxXvWGwBIn2SkMr1w3Fi8/VDhwGKfb4FiwWJhTzrVxYP4SE2i4vLl55OVr M71so57DJ8Dk+wKoR3to76O8Nl7YENY= 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-194-x5vRj3D9MKuCmGYjQ4d-OA-1; Tue, 28 Jan 2025 11:39:11 -0500 X-MC-Unique: x5vRj3D9MKuCmGYjQ4d-OA-1 X-Mimecast-MFC-AGG-ID: x5vRj3D9MKuCmGYjQ4d-OA 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 727661800360; Tue, 28 Jan 2025 16:39:10 +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 9D1D4180035E; Tue, 28 Jan 2025 16:39:08 +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 03/21] bcachefs: Run the eytzinger tests on modprobe Date: Tue, 28 Jan 2025 17:38:40 +0100 Message-ID: <20250128163859.1883260-4-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 FOR DEBUGGING ONLY -- DO NOT MERGE! Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.c | 12 +++--------- fs/bcachefs/eytzinger.h | 4 ++++ fs/bcachefs/super.c | 5 +++++ fs/bcachefs/util.c | 2 +- fs/bcachefs/util.h | 4 ++++ 5 files changed, 17 insertions(+), 10 deletions(-) diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index c0fdfe909cf2..08549ab3c18e 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -242,7 +242,7 @@ void eytzinger0_sort(void *base, size_t n, size_t size, return eytzinger0_sort_r(base, n, size, _CMP_WRAPPER, SWAP_WRAPPER, &w); } -#if 0 +#if 1 #include #include #include @@ -263,7 +263,7 @@ static int mycmp(const void *a, const void *b) return 0; } -static int test(void) +void eytzinger_sort_test(void) { size_t N, i; ktime_t start, end; @@ -288,17 +288,11 @@ static int test(void) u32 prev = 0; eytzinger0_for_each(i, N) { - if (prev > arr[i]) - goto err; + BUG_ON(prev > arr[i]); prev = arr[i]; } kfree(arr); } - return 0; - -err: - kfree(arr); - return -1; } #endif diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 0541192d7bc0..16303908ccff 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -5,6 +5,8 @@ #include #include +#define EYTZINGER_DEBUG + #ifdef EYTZINGER_DEBUG #define EYTZINGER_BUG_ON(cond) BUG_ON(cond) #else @@ -316,4 +318,6 @@ void eytzinger0_sort_r(void *, size_t, size_t, cmp_r_func_t, swap_r_func_t, const void *); void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t); +void eytzinger_sort_test(void); + #endif /* _EYTZINGER_H */ diff --git a/fs/bcachefs/super.c b/fs/bcachefs/super.c index a6ed9a0bf1c7..d8ad43fb48fc 100644 --- a/fs/bcachefs/super.c +++ b/fs/bcachefs/super.c @@ -2120,6 +2120,11 @@ static int __init bcachefs_init(void) { bch2_bkey_pack_test(); + eytzinger_sort_test(); + eytzinger1_test(); + eytzinger0_test(); + eytzinger0_find_test(); + if (!(bcachefs_kset = kset_create_and_add("bcachefs", NULL, fs_kobj)) || bch2_btree_key_cache_init() || bch2_chardev_init() || diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index e0a876cbaa6b..9a63d971ee65 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -698,7 +698,7 @@ void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) } } -#if 0 +#if 1 void eytzinger1_test(void) { unsigned inorder, eytz, size; diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index fb02c1c36004..b963c523f5d7 100644 --- a/fs/bcachefs/util.h +++ b/fs/bcachefs/util.h @@ -696,4 +696,8 @@ static inline bool test_bit_le64(size_t bit, __le64 *addr) return (addr[bit / 64] & cpu_to_le64(BIT_ULL(bit % 64))) != 0; } +void eytzinger1_test(void); +void eytzinger0_test(void); +void eytzinger0_find_test(void); + #endif /* _BCACHEFS_UTIL_H */ 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: 13952781 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:42 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952782 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 0C27E1DE3AA for ; Tue, 28 Jan 2025 16:39:21 +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=kLmSjFZ3a/c/cnAqetAtKXuoSCeY5GMSsXJl4Jg5a0ptFH12ZbFXh4v9AHHxhNFOAODyrmrIPo0V/MS1CPQPEG898+KJGmqY4lt74RCLTtZlEu0xWzPddSDDlg+6KOrjjU1+hqt0SvfMHq4xFsxPe8iRh3JiKvOdlse7nzaWMXk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082363; c=relaxed/simple; bh=uZ0aGlJuTJXH0fBO0zlo6dgQolJCoTc7xB+/waRCzzU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=pZJzsy+Oci7kxz1ZfdOh/tkanTierAgoryuGufpXDibLMOglIT3pLpfnrS4p4fftB9oA6sv8K4+/dQxVlNjN6hLKl5mgKoLXYGNyBu625Z2GAQGTWPthQnOckIB37vLMIcVbe2KhPG6dGpX23U8QoCxfo1L0jNx3hZkTtdEVkeI= 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=ePxO5tqL; 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="ePxO5tqL" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082360; 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=q/GAn/SXepDYjnAlZBYdkJTu1emedkGC4rPyfHvCkE0=; b=ePxO5tqLkxt9DRq2FP/LJuRCPBRnfkdxRLiYFcvyEa41vE+xLRc8rg+vZHvoIGaf4eu073 1dVG4eGWC6mn+MuV7NDfcKu6GVtDLWciQ9qgDWCTROIVd0B9TFlirMJYkvC1IMmGcDAWg7 xqoKfLLMArNU9ZssPtAu+WzDH4DICig= 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-138-ujW_-aM_Ps2dtK3x44ntww-1; Tue, 28 Jan 2025 11:39:16 -0500 X-MC-Unique: ujW_-aM_Ps2dtK3x44ntww-1 X-Mimecast-MFC-AGG-ID: ujW_-aM_Ps2dtK3x44ntww 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 659FC1955DC8; Tue, 28 Jan 2025 16:39:15 +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 8605318008C8; Tue, 28 Jan 2025 16:39:13 +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 05/21] bcachefs: eytzinger self tests: eytzinger0_for_each loop cleanups Date: Tue, 28 Jan 2025 17:38:42 +0100 Message-ID: <20250128163859.1883260-6-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 The iterator variable of eytzinger0_for_each loops has been changed to be locally scoped at some point, so remove variables defined outside the loop that are now unused. In addition and for clarity, use a different variable inside those loops where an outside variable would be shadowed. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 9a63d971ee65..58a7b962847d 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -473,10 +473,10 @@ void bch2_time_stats_to_text(struct printbuf *out, struct bch2_time_stats *stats u64 last_q = 0; prt_printf(out, "quantiles (%s):\t", u->name); - eytzinger0_for_each(i, NR_QUANTILES) { - bool is_last = eytzinger0_next(i, NR_QUANTILES) == -1; + eytzinger0_for_each(j, NR_QUANTILES) { + bool is_last = eytzinger0_next(j, NR_QUANTILES) == -1; - u64 q = max(quantiles->entries[i].m, last_q); + u64 q = max(quantiles->entries[j].m, last_q); prt_printf(out, "%llu ", div64_u64(q, u->nsecs)); if (is_last) prt_newline(out); @@ -701,7 +701,7 @@ void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter) #if 1 void eytzinger1_test(void) { - unsigned inorder, eytz, size; + unsigned inorder, size; pr_info("1 based eytzinger test:"); @@ -734,7 +734,7 @@ void eytzinger1_test(void) void eytzinger0_test(void) { - unsigned inorder, eytz, size; + unsigned inorder, size; pr_info("0 based eytzinger test:"); @@ -764,7 +764,7 @@ void eytzinger0_test(void) } } -static inline int cmp_u16(const void *_l, const void *_r, size_t size) +static inline int cmp_u16(const void *_l, const void *_r) { const u16 *l = _l, *r = _r; @@ -787,8 +787,8 @@ static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) c2 = test_array[i]; if (c1 != c2) { - eytzinger0_for_each(i, nr) - pr_info("[%3u] = %12u", i, test_array[i]); + eytzinger0_for_each(j, nr) + pr_info("[%3u] = %12u", j, test_array[j]); pr_info("find_le(%2u) -> [%2zi] = %2i should be %2i", i, r, c1, c2); } @@ -806,9 +806,9 @@ void eytzinger0_find_test(void) eytzinger0_sort(test_array, nr, sizeof(test_array[0]), cmp_u16, NULL); /* verify array is sorted correctly: */ - eytzinger0_for_each(i, nr) - BUG_ON(i != eytzinger0_last(nr) && - test_array[i] > test_array[eytzinger0_next(i, nr)]); + eytzinger0_for_each(j, nr) + BUG_ON(j != eytzinger0_last(nr) && + test_array[j] > test_array[eytzinger0_next(j, nr)]); for (i = 0; i < U16_MAX; i += 1 << 12) eytzinger0_find_test_val(test_array, nr, i); 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: 13952783 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:44 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952784 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 7B5271DE3A9 for ; Tue, 28 Jan 2025 16:39:25 +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=1738082366; cv=none; b=FPz0on05di78cr+Oi8HGTM9z15hhXIO1UrUhI+XXwwCgNrpNNpLgGIUHO7A755KIM+vn1gnqMSoZbguW/hFs/eW3s4ExYBT9bt2U2/NwGvfJwEfVq8KWIZk0vmO6D5AlhHZgMjNgZCSCQkO9HGkY9P5iT3iBTVptwiDUIv4w7oI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082366; c=relaxed/simple; bh=26+fZjoj5DpFgwjWuVjxZioQ6e93bfSV9rMpdHN3BS8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=eSfVwkFV72aCbFZKHPgW0Uk7JDifOKh/Fd8B9OxCA4kdV43J7+ljGvWzUF1YFR9ktka7Fn39BMjBpnITyWiEv3pX+XV1z2hL3lo0C42QWvaBylVoej+zaaqxnOJOCIFUT+BVuRVXxehkmvPmJmIzLSNuTxU/7AditIU3feq+uEg= 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=MQ2z71nM; 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="MQ2z71nM" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082364; 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=jctk5R+SR8nBvr4ywsdyrPgUcAu2wJfq11Wb8lyGBzU=; b=MQ2z71nMYX+fWN5AhVl0rJ4Vuh6WBzqLGTYSjX7EbkLycxDp4sZxMsKR2y4SJs7S7tRz11 i1/aVJDVqMDvs/uA25/f0Lf8THArS8M0PwTX3vwEtkYQkuxirnbe3nGbWXvmvhvE90td/h /Ky3BHj4NHGYR+l7xRGpTMGjVOYcGCQ= 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-439-pPxWYbZKM7axE1krNLqh0g-1; Tue, 28 Jan 2025 11:39:21 -0500 X-MC-Unique: pPxWYbZKM7axE1krNLqh0g-1 X-Mimecast-MFC-AGG-ID: pPxWYbZKM7axE1krNLqh0g 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 2B9E01800A01; Tue, 28 Jan 2025 16:39:20 +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 3602B18008D4; Tue, 28 Jan 2025 16:39:17 +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 07/21] bcachefs: eytzinger self tests: fix cmp_u16 typo Date: Tue, 28 Jan 2025 17:38:44 +0100 Message-ID: <20250128163859.1883260-8-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 Fix an obvious typo in cmp_u16(). Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 7cf319290a88..0ffbd22d3a5e 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -768,7 +768,7 @@ static inline int cmp_u16(const void *_l, const void *_r) { const u16 *l = _l, *r = _r; - return (*l > *r) - (*r - *l); + return (*l > *r) - (*r > *l); } static void eytzinger0_find_test_val(u16 *test_array, unsigned nr, u16 search) 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: 13952785 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:46 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952786 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 52ECB1DE3A4 for ; Tue, 28 Jan 2025 16:39:32 +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=1738082373; cv=none; b=T/UhD239kKa7R/ORLGrIdpYdI256WSX/B25sS/8VFb2ZCdy83JD/SargjgelwyUiFvSg15OOdX4oNJGNpgSeOGh1nQ4keMMvZzH4xQvH0DMrxg6tRma4iC/gP/ERsqH5Z0VrAeMQzlS/iZPWdYQslG1Wsd9f6C0x/PknoceepaM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082373; c=relaxed/simple; bh=bWlS4pA1AQioApkfjVizknM0UCXQZYs07W1FkGUHMds=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=tOtWizKY32M94kvRZZsdMSr+BYuCfqx6p8FCmxAZqWQhoXgbnKT9h0J4ol+LwwbxqcoN3TgfRLnqMlkpRW1cK/svfKdcff3JbwZa5X1Cct/mDIA39SG6ouWlgN3bF253FCP+QwUDiQLzbrdPAANVkoTGQL+DNoieDNU+PMEedus= 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=jG7hpgcW; 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="jG7hpgcW" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082371; 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=H+t5+IyxXZJWdw4WRuFCHidcqeNnjaqNu5ZB+WiJxrw=; b=jG7hpgcWyuJMeIJupJt+g9wrKNl/U/7vYmTWqhCXxUqnbVdevVaUt2vwudUVpne79SOcYh fMxQ90+HJOiNKAyLYSuiuRNPLeD+bkBPKe66FDmduPujWM4tSjdKHX/kl5Ymiqi3RQ7vKO wix4Vh6qws/X2V7Han2qTflZZgrqyBs= 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-223-_VAdzJY-NJun8_8Cupr9Lg-1; Tue, 28 Jan 2025 11:39:26 -0500 X-MC-Unique: _VAdzJY-NJun8_8Cupr9Lg-1 X-Mimecast-MFC-AGG-ID: _VAdzJY-NJun8_8Cupr9Lg 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 001D7180188B; Tue, 28 Jan 2025 16:39:25 +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 0653E18008C8; Tue, 28 Jan 2025 16:39:22 +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 09/21] bcachefs: eytzinger0_find_test improvement Date: Tue, 28 Jan 2025 17:38:46 +0100 Message-ID: <20250128163859.1883260-10-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 eytzinger0_find_test(), remember the smallest element seen so far instead of comparing adjacent array elements. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 4122012ddfb2..87502e1ac7ce 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -802,15 +802,18 @@ void eytzinger0_find_test(void) u16 *test_array = kmalloc_array(allocated, sizeof(test_array[0]), GFP_KERNEL); for (nr = 1; nr < allocated; nr++) { + u16 prev = 0; + 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); /* verify array is sorted correctly: */ - eytzinger0_for_each(j, nr) - BUG_ON(j != eytzinger0_last(nr) && - test_array[j] > test_array[eytzinger0_next(j, nr)]); + eytzinger0_for_each(j, nr) { + BUG_ON(test_array[j] < prev); + prev = test_array[j]; + } for (i = 0; i < U16_MAX; i += 1 << 12) eytzinger0_find_test_val(test_array, nr, i); From patchwork Tue Jan 28 16:38:47 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952788 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 E0FBF1DE3AC for ; Tue, 28 Jan 2025 16:39:35 +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=1738082377; cv=none; b=O31kCX6F9oyoBW+Un5xO55QZD+anLzy/lC2uo3xpBEAGgF7nq/TFV5BW5sJJ2mLIAW0MaKLnVcZBo69Nyy0NKkI5ItDeI5KhCqSbbMC3bAI/FtjK4biDpo0VNvHfZ3AD4n+XAYKMfooE+bQeS6jmcWQxzaZuWyjNPYQgC0vGwg4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082377; c=relaxed/simple; bh=Q4L+OrPQw64EmyoWqeElIQQS4K6CLQeCegeDdBXVELc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=joAOWSK5/EDEH0jrmFAz2/q2HC1wA8GCGqFAToO9/D4EPVyWZv3S0vtg7YYfM0O8fO3H6rIbkCu7GczJIjTjNvMIeFqmmaWVvW/tVr/Xbq6txn8um2OL6Qek7rjO+uc/s9EbwW30jwm16G0CwsDDuWpziuSRsF7u/djCGtJvTOY= 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=JN2GbuWc; 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="JN2GbuWc" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082375; 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=STYFZq9yGDZAcEa5KK0r23b7pY53kibk/xnRBI6F77I=; b=JN2GbuWcGJCu+q58NBGt2/yVi6bDA4JSmV/ak6U+Lp/sGnt0sth+weURbnzdbu0fo9juPx /D7m+2vnuT2NJLYaKWhFR3qQYlf6uwJCPnAmhfzJePGrhYyWea3AG/cTUivXG2puRQie1z /0uhaC3wuRmIMJqj6BYbYOdAlckdmmU= 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-678-DhthYg2JPcaI-lC5nhuTGA-1; Tue, 28 Jan 2025 11:39:31 -0500 X-MC-Unique: DhthYg2JPcaI-lC5nhuTGA-1 X-Mimecast-MFC-AGG-ID: DhthYg2JPcaI-lC5nhuTGA 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 73E8C19560AB; Tue, 28 Jan 2025 16:39:27 +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 7D676180035E; Tue, 28 Jan 2025 16:39:25 +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 10/21] bcachefs: add eytzinger0_for_each_prev Date: Tue, 28 Jan 2025 17:38:47 +0100 Message-ID: <20250128163859.1883260-11-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 Add an eytzinger0_for_each_prev() macro for iterating through an eytzinger array in reverse. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 5 +++++ fs/bcachefs/util.c | 9 +++++++++ 2 files changed, 14 insertions(+) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 6fa6d51a5420..f25c895aa184 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -246,6 +246,11 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size) (_i) != -1; \ (_i) = eytzinger0_next((_i), (_size))) +#define eytzinger0_for_each_prev(_i, _size) \ + for (unsigned (_i) = eytzinger0_last((_size)); \ + (_i) != -1; \ + (_i) = eytzinger0_prev((_i), (_size))) + /* return greatest node <= @search, or -1 if not found */ static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 87502e1ac7ce..3fe9a3b8c696 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -763,6 +763,15 @@ void eytzinger0_test(void) inorder++; } BUG_ON(inorder != size); + + inorder = size - 1; + eytzinger0_for_each_prev(eytz, size) { + BUG_ON(eytz != eytzinger0_first(size) && + eytzinger0_next(eytzinger0_prev(eytz, size), size) != eytz); + + inorder--; + } + BUG_ON(inorder != -1); } } 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: 13952787 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: 13952789 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:50 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952790 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 0B4FD1DE3A4 for ; Tue, 28 Jan 2025 16:39:40 +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=1738082382; cv=none; b=L2F3yoCxuFOXw1WDYl48klMYyqviHnLnfiTut8zOIGppdxXC3Niygvyb24QYAYF0U8hdqGwuTTF6HDcUnMI5Gx8rMorWYiWF7oVDqhLz3boPZ1jplAlFh9kT5eGOgp5ZBdWZmh1bqMn4Q+eE/MLb0t4d13bG8Q4tlkNIAToK4YU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082382; c=relaxed/simple; bh=to7YVz+ZP9wZQ/hf5G31EeF2GtYmyr37A/IQfP8eOd4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=u2jjZ1W6atuII4GPfubWCC6pronjxV36TEHtB3B0zOagpKWvWTybIAa7POrixdNImf+xpUPop97IBxbLzqlpqnu7Hz+1wdog/Oe83wPQ5RAaHxZJMIRWXV7TdhB9lK5qUqu73prlaGAb1ScMR5cucvU6kYefzwm3TBE++N64WlY= 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=RzWpAc8l; 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="RzWpAc8l" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082380; 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=1q5oEad9tu+f1M8WQTNmmoY3EsgfSb3rycHQaS+bJ9k=; b=RzWpAc8lDRMwmxGQ0790+QMN6lJYA9czPGbN9RjKHSbNFnHlRDxKUqR2B/gN+NHkoAynm1 5PguNSPB6nIQDPohOkpCHDtYwEwRZxmy/p7FFv7upunQdEHwqmSDwmdW+WueoQ/E12L3sn 2JeVmATbFiC/p1Qz1slt/uFSKc/lQ44= 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-297-8H8nEUDlMuitbEhniwwn7w-1; Tue, 28 Jan 2025 11:39:35 -0500 X-MC-Unique: 8H8nEUDlMuitbEhniwwn7w-1 X-Mimecast-MFC-AGG-ID: 8H8nEUDlMuitbEhniwwn7w 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 52FAA18009B7; Tue, 28 Jan 2025 16:39:34 +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 7C754180035E; Tue, 28 Jan 2025 16:39:32 +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 13/21] bcachefs: convert eytzinger0_find_le to be 1-based Date: Tue, 28 Jan 2025 17:38:50 +0100 Message-ID: <20250128163859.1883260-14-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 eytzinger0_find_le() is also easy to concert to 1-based eytzinger (but see the next commit). Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index d3e8b9edf335..130f5fe30bd7 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -255,27 +255,27 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size) static inline int eytzinger0_find_le(void *base, size_t nr, size_t size, cmp_func_t cmp, const void *search) { - unsigned i, n = 0; + void *base1 = base - size; + unsigned i, n = 1; if (!nr) return -1; do { i = n; - n = eytzinger0_child(i, cmp(base + i * size, search) <= 0); - } while (n < nr); + n = eytzinger1_child(i, cmp(base1 + i * size, search) <= 0); + } while (n <= nr); - if (n & 1) { + if (!(n & 1)) { /* * @i was greater than @search, return previous node: * * if @i was leftmost/smallest element, - * eytzinger0_prev(eytzinger0_first())) returns -1, as expected + * eytzinger1_prev(eytzinger1_first())) returns 0, as expected */ - return eytzinger0_prev(i, nr); - } else { - return i; + i = eytzinger1_prev(i, nr); } + return i - 1; } static inline int eytzinger0_find_gt(void *base, size_t nr, size_t size, 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: 13952791 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:52 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952792 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 8F4481DE3B1 for ; Tue, 28 Jan 2025 16:39:46 +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=1738082388; cv=none; b=GAa9sGuFG2UAXKXdKpHbQfn2+9Bq6ilVNKK0ID7HVsABP7SMdVIlLd7k+MSUkan1iGMKa8XT7rfjwQmfQJKlg8aPiDPwsRjw/ELoXe93qG1P3SEvy/z5sPSHYu0Ma3/fTSiSZBjMCxekNZGnRU1wCpkSXOBIFMy/wc0WrsFPgas= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082388; c=relaxed/simple; bh=gD2MOqZe8ovnHyS3V8WoY1tpKSobqoC+vaRjGdjO01A=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=kzIbss81m+60DcJu3blH46kuK4tJ2EALCDdvdf9HHFlfvjJAXK+q36iOFL+mArFBzQQGDay4z2mNexIdIKznc8mrgZqdBxxvdFpTJWEXOvpTOI7Xei6qwHD0CSENP5aBzOUbKFDKaAsesJ1Uvag0UU2XP8vPBpOsy7cJVFa3MPg= 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=Rvj2adIU; 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="Rvj2adIU" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082385; 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=1zVELwI01VWAwpCtMhLCBjEE0cAM4DjBjLNjy0PGD28=; b=Rvj2adIU9kViPCZCqdbjm2FYONQX83fPtson5JZsUMnnHod3+nnrIjDVaplPQgaazAwBKo /kYYUJB24JNTfI5lBKfW+6mpxn3CK8Z59khdt7O/dyjF2fbhBIUBtEEZW71oYgtY2JU95L DMu9E22w0rc7JeWo0CUanS+fz+y8AlY= 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-303-H4hacxvaPoGPcm4bJc962A-1; Tue, 28 Jan 2025 11:39:40 -0500 X-MC-Unique: H4hacxvaPoGPcm4bJc962A-1 X-Mimecast-MFC-AGG-ID: H4hacxvaPoGPcm4bJc962A 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 60A7A19560B7; Tue, 28 Jan 2025 16:39:39 +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 3151C18008C0; Tue, 28 Jan 2025 16:39:36 +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 15/21] bcachefs: add eytzinger0_find_gt tests Date: Tue, 28 Jan 2025 17:38:52 +0100 Message-ID: <20250128163859.1883260-16-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 Add eytzinger0_find_gt() tests similar to the eytzinger0_find_le() tests. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index c772629783f3..d84632870b56 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -819,9 +819,47 @@ static void eytzinger0_find_test_le(u16 *test_array, unsigned nr, u16 search) } } +static void eytzinger0_find_test_gt(u16 *test_array, unsigned nr, u16 search) +{ + int r, s; + bool bad; + + r = eytzinger0_find_gt(test_array, nr, + sizeof(test_array[0]), + cmp_u16, &search); + if (r >= 0) { + if (test_array[r] <= search) { + bad = true; + } else { + s = eytzinger0_prev(r, nr); + bad = s >= 0 && test_array[s] > search; + } + } else { + s = eytzinger0_first(nr); + bad = s >= 0 && test_array[s] > search; + } + + if (bad) { + s = -1; + eytzinger0_for_each(j, nr) { + if (test_array[j] > search) { + s = j; + break; + } + } + + eytzinger0_for_each(j, nr) + pr_info("[%3u] = %12u\n", j, test_array[j]); + pr_info("find_gt(%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); + eytzinger0_find_test_gt(test_array, nr, search); } void eytzinger0_find_test(void) 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: 13952793 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:54 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952794 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 5553C1DE3AC for ; Tue, 28 Jan 2025 16:39:49 +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=1738082390; cv=none; b=CsT8Hdp4y+1NE3R6CWy7aA1YzHGabYooUEK6aUMsvw1AwsR7FTDIvepNQ2iHJlLBiqrbDfZgXvpSp5Z8ePHYjDMocJJaHAotphvurKZiOGRnkEHYqjdzFIDKF41UbbvrUTkBh9TJ5ElsQGVDcuJPLvANwvPOyhODvhGgFdd6Pgg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082390; c=relaxed/simple; bh=KsiPRQhSWT9pPQiGEox7uuCGsif9fmMpan+bE+vvNqw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=ZZDy/hbQbJVhlgA6MKMZQovZbjgs9pkqJd9UmdLs2PIO/FawhDb8yK+qM+uA0m3MEDEy1/lyi7QdH7Pueinda2sHWBAMrcwjlo35HDvMO0rTaqLP6jG/GKDHhkOf1rN+Iq6JxhBhpbcVQ35U4+vHnO7GKXDhYLWp5uG5527ebuM= 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=akSRlHzo; 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="akSRlHzo" 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=kWFaJg/6twIrbICir/G61SugpATzgaIb6ENB42VFtQA=; b=akSRlHzobecYOenvJSpl+OKrl/ivaHT+CNnjz/oXO9SPU4OcREMS0tlOihxZVpSKhNKA+R ueLk4A5eOA+bf01RHsgyB5ei4Lv7WfF8MgT4Y6yDth0dKU7/dB8BOo8sQHsaoVu5VtKwzW MP1ryUor+cg3wYgPM453jQymLa3mBuE= 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-140-iEm3Ih-1MnKLU4ItbBFLDA-1; Tue, 28 Jan 2025 11:39:45 -0500 X-MC-Unique: iEm3Ih-1MnKLU4ItbBFLDA-1 X-Mimecast-MFC-AGG-ID: iEm3Ih-1MnKLU4ItbBFLDA 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 10F241956087; Tue, 28 Jan 2025 16:39:44 +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 3955F180035E; Tue, 28 Jan 2025 16:39:41 +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 17/21] bcachefs: add eytzinger0_find_ge tests Date: Tue, 28 Jan 2025 17:38:54 +0100 Message-ID: <20250128163859.1883260-18-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 Add eytzinger0_find_ge() tests similar to the eytzinger0_find_gt() tests. Note that the current implementation of eytzinger0_find_ge() doesn't always find the first element >= @search, so the tests will occasionally fail. The next commit fixes that. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/util.c | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index d84632870b56..e75329399c6e 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -856,10 +856,48 @@ static void eytzinger0_find_test_gt(u16 *test_array, unsigned nr, u16 search) } } +static void eytzinger0_find_test_ge(u16 *test_array, unsigned nr, u16 search) +{ + int r, s; + bool bad; + + r = eytzinger0_find_ge(test_array, nr, + sizeof(test_array[0]), + cmp_u16, &search); + if (r >= 0) { + if (test_array[r] < search) { + bad = true; + } else { + s = eytzinger0_prev(r, nr); + bad = s >= 0 && test_array[s] >= search; + } + } else { + s = eytzinger0_first(nr); + bad = s >= 0 && test_array[s] >= search; + } + + if (bad) { + s = -1; + eytzinger0_for_each(j, nr) { + if (test_array[j] >= search) { + s = j; + break; + } + } + + eytzinger0_for_each(j, nr) + pr_info("[%3u] = %12u\n", j, test_array[j]); + pr_info("find_ge(%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); eytzinger0_find_test_gt(test_array, nr, search); + eytzinger0_find_test_ge(test_array, nr, search); } void eytzinger0_find_test(void) 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: 13952795 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:56 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952796 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 21DD91DE3C3 for ; Tue, 28 Jan 2025 16:39:54 +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=1738082395; cv=none; b=UWI0fL3W2m5UU5V9AHJlNUqS/Xf0sjitaV4EcX49PGv6Ep5CnuNKvdxd2pELICsRiB//BoXSWgl0VTLhcVXBScKM/yxIHH+dg5lMy0oeHIxsCP4OTJTZrkx3HErAlFVRfBTYu5DIVwVeEO4iYtx1dX0BcvIHUmAVMhaE1UfsY+M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082395; c=relaxed/simple; bh=tJkAXjEvufeX/5dKW+3RT/KX1TbldSWqPOBH1co00lE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=BHDIW9VDLZf2Q553fAnRLR5ZrN5MlEDs6BCfRkow7yky633Ak0pAZJcU9KTWbc4w1cKS4CcB3WpH+jzdriceI9j2VyOuD5MKcbKFOQl+ELIqTxnueKJ+tdU26PorWuHocLSuDRz7PGA6L2xB1S7pxEZhrCVSVTe2h45l8MecwcA= 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=gtsO/AMR; 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="gtsO/AMR" 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=8ltYxlBO7b3sbhJky1/A71Z0Wfo/ecXnBT4MAz0bUNU=; b=gtsO/AMR+vci+S5BJzF7OfK4CHcx3B4fq2MsmNGH8eamVVjx0rDdOHPnYCmPiohhurTIvn MZVq0wR/kl2uZ3VxNpBHH+lxRvRc3uvdUvOpl9qoNGn94qw71q2wE1WwsyAZY8lohRPUYC GrE5dYOSZqIWN5CRE7geTGpC853nUI0= Received: from mx-prod-mc-03.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-121-YEwM4907PKG855x_XNCrPA-1; Tue, 28 Jan 2025 11:39:49 -0500 X-MC-Unique: YEwM4907PKG855x_XNCrPA-1 X-Mimecast-MFC-AGG-ID: YEwM4907PKG855x_XNCrPA 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-03.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id C0F8619560BB; Tue, 28 Jan 2025 16:39:48 +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 E11A218008D8; Tue, 28 Jan 2025 16:39:46 +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 19/21] bcachefs: convert eytzinger sort to be 1-based (1) Date: Tue, 28 Jan 2025 17:38:56 +0100 Message-ID: <20250128163859.1883260-20-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 first step, convert the eytzinger sort functions to use 1-based primitives. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.c | 48 +++++++++++++++++++++++++---------------- 1 file changed, 29 insertions(+), 19 deletions(-) diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c index 08549ab3c18e..93a5819a6878 100644 --- a/fs/bcachefs/eytzinger.c +++ b/fs/bcachefs/eytzinger.c @@ -147,28 +147,28 @@ static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *pr return cmp(a, b, priv); } -static inline int eytzinger0_do_cmp(void *base, size_t n, size_t size, +static inline int eytzinger1_do_cmp(void *base1, size_t n, size_t size, cmp_r_func_t cmp_func, const void *priv, size_t l, size_t r) { - return do_cmp(base + inorder_to_eytzinger0(l, n) * size, - base + inorder_to_eytzinger0(r, n) * size, + return do_cmp(base1 + inorder_to_eytzinger1(l, n) * size, + base1 + inorder_to_eytzinger1(r, n) * size, cmp_func, priv); } -static inline void eytzinger0_do_swap(void *base, size_t n, size_t size, +static inline void eytzinger1_do_swap(void *base1, size_t n, size_t size, swap_r_func_t swap_func, const void *priv, size_t l, size_t r) { - do_swap(base + inorder_to_eytzinger0(l, n) * size, - base + inorder_to_eytzinger0(r, n) * size, + do_swap(base1 + inorder_to_eytzinger1(l, n) * size, + base1 + inorder_to_eytzinger1(r, n) * size, size, swap_func, priv); } -void eytzinger0_sort_r(void *base, size_t n, size_t size, - cmp_r_func_t cmp_func, - swap_r_func_t swap_func, - const void *priv) +static void eytzinger1_sort_r(void *base1, size_t n, size_t size, + cmp_r_func_t cmp_func, + swap_r_func_t swap_func, + const void *priv) { int i, j, k; @@ -177,9 +177,9 @@ void eytzinger0_sort_r(void *base, size_t n, size_t size, swap_func = NULL; if (!swap_func) { - if (is_aligned(base, size, 8)) + if (is_aligned(base1, size, 8)) swap_func = SWAP_WORDS_64; - else if (is_aligned(base, size, 4)) + else if (is_aligned(base1, size, 4)) swap_func = SWAP_WORDS_32; else swap_func = SWAP_BYTES; @@ -189,47 +189,57 @@ void eytzinger0_sort_r(void *base, size_t n, size_t size, for (i = n / 2 - 1; i >= 0; --i) { /* Find the sift-down path all the way to the leaves. */ for (j = i; k = j * 2 + 1, k + 1 < n;) - j = eytzinger0_do_cmp(base, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1; + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1; /* Special case for the last leaf with no sibling. */ if (j * 2 + 2 == n) j = j * 2 + 1; /* Backtrack to the correct location. */ - while (j != i && eytzinger0_do_cmp(base, n, size, cmp_func, priv, i, j) >= 0) + while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i + 1, j + 1) >= 0) j = (j - 1) / 2; /* Shift the element into its correct place. */ for (k = j; j != i;) { j = (j - 1) / 2; - eytzinger0_do_swap(base, n, size, swap_func, priv, j, k); + eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); } } /* sort */ for (i = n - 1; i > 0; --i) { - eytzinger0_do_swap(base, n, size, swap_func, priv, 0, i); + eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i + 1); /* Find the sift-down path all the way to the leaves. */ for (j = 0; k = j * 2 + 1, k + 1 < i;) - j = eytzinger0_do_cmp(base, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1; + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1; /* Special case for the last leaf with no sibling. */ if (j * 2 + 2 == i) j = j * 2 + 1; /* Backtrack to the correct location. */ - while (j && eytzinger0_do_cmp(base, n, size, cmp_func, priv, 0, j) >= 0) + while (j && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j + 1) >= 0) j = (j - 1) / 2; /* Shift the element into its correct place. */ for (k = j; j;) { j = (j - 1) / 2; - eytzinger0_do_swap(base, n, size, swap_func, priv, j, k); + eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1); } } } +void eytzinger0_sort_r(void *base, size_t n, size_t size, + cmp_r_func_t cmp_func, + swap_r_func_t swap_func, + const void *priv) +{ + void *base1 = base - size; + + return eytzinger1_sort_r(base1, n, size, cmp_func, swap_func, priv); +} + void eytzinger0_sort(void *base, size_t n, size_t size, cmp_func_t cmp_func, swap_func_t swap_func) 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: 13952797 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); } } } From patchwork Tue Jan 28 16:38:58 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Gruenbacher X-Patchwork-Id: 13952798 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 CDE391DE3BC for ; Tue, 28 Jan 2025 16:39:59 +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=1738082401; cv=none; b=LoNomRNsQIlni3dYcMd9bNesQzqPaliJ0pzGAIKf4/HEHlrYqCTHFpA9oC9r4DYkkTr3zScS4CJBmYEMeHXwrSNYhNw4ExZFUhY9lke8jOJZupWQQfmKgNFrbTjaIaGfmqAE1OhWhbTxU0/CDHKFXfki0/dIu4C5NJR9pv1olAs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738082401; c=relaxed/simple; bh=YNzhwcYPDLV67byFZgoIbQn00IWONldLlQseNt6ENKU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=RDXrE87gRv5CCB2+VR6xrjrUyPiRBfrWA7tsTFgLaEn3ADM7zPkCUfvze2vG8Rz+4k6DbmBWOQtDS9U2qtvDYPUjwhv84NK7H5oPHucu1zbXC8KEv95I2dxt7KuYaXeDrZ9/KODf9rOJ5SA2Qrv0hAZbR00n7wx+1PUO41f586E= 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=ehtt5vjk; 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="ehtt5vjk" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1738082398; 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=k/H6mEbuvMQmYWFYf4QRWAbACluB3EmA21tCT2XkWd8=; b=ehtt5vjkCV3nAth4TLpFwvoYs8tOrk13EOBQiziznbDGp11trmKxGnIUiz0OcuNDGUgMZu Vyhj58NZqC2XeepQB2WbVATJJzxCrSZn1F2ECrgsfpER87du5yiQrzndahb9Ui2dcFRUuU knLN0/TO02jFNJLyM1WfQ9rmaXAQIC8= 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-237-dYBTKi9lNyaakQnTa0g_mg-1; Tue, 28 Jan 2025 11:39:54 -0500 X-MC-Unique: dYBTKi9lNyaakQnTa0g_mg-1 X-Mimecast-MFC-AGG-ID: dYBTKi9lNyaakQnTa0g_mg 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 AB4571955DCC; Tue, 28 Jan 2025 16:39:53 +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 961D518008C0; Tue, 28 Jan 2025 16:39:51 +0000 (UTC) From: Andreas Gruenbacher To: Kent Overstreet , Shuah Khan Cc: Andreas Gruenbacher , linux-bcachefs@vger.kernel.org, linux-kselftest@vger.kernel.org, Andreas Gruenbacher Subject: [PATCH 21/21] bcachefs: eytzinger1_{next,prev} cleanup Date: Tue, 28 Jan 2025 17:38:58 +0100 Message-ID: <20250128163859.1883260-22-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 From: Andreas Gruenbacher The eytzinger code was previously relying on the following wrap-around properties and their "eytzinger0" equivalents: eytzinger1_prev(0, size) == eytzinger1_last(size) eytzinger1_next(0, size) == eytzinger1_first(size) However, these properties are no longer relied upon and no longer necessary, so remove the corresponding asserts and forbid the use of eytzinger1_prev(0, size) and eytzinger1_next(0, size). This allows to further simplify the code in eytzinger1_next() and eytzinger1_prev(): where the left shifting happens, eytzinger1_next() is trying to move i to the lowest child on the left, which is equivalent to doubling i until the next doubling would cause it to be greater than size. This is implemented by shifting i to the left so that the most significant bits align and then shifting i to the right by one if the result is greater than size. Likewise, eytzinger1_prev() is trying to move to the lowest child on the right; the same applies here. The 1-offset in (size - 1) in eytzinger1_next() isn't needed at all, but the equivalent offset in eytzinger1_prev() is surprisingly needed to preserve the 'eytzinger1_prev(0, size) == eytzinger1_last(size)' property. However, since we no longer support that property, we can get rid of these offsets as well. This saves one addition in each function and makes the code less confusing. Signed-off-by: Andreas Gruenbacher --- fs/bcachefs/eytzinger.h | 18 ++++-------------- fs/bcachefs/util.c | 12 ------------ 2 files changed, 4 insertions(+), 26 deletions(-) diff --git a/fs/bcachefs/eytzinger.h b/fs/bcachefs/eytzinger.h index 6a363b12bd21..e600a7d52001 100644 --- a/fs/bcachefs/eytzinger.h +++ b/fs/bcachefs/eytzinger.h @@ -59,24 +59,14 @@ static inline unsigned eytzinger1_last(unsigned size) return rounddown_pow_of_two(size + 1) - 1; } -/* - * eytzinger1_next() and eytzinger1_prev() have the nice properties that - * - * eytzinger1_next(0) == eytzinger1_first()) - * eytzinger1_prev(0) == eytzinger1_last()) - * - * eytzinger1_prev(eytzinger1_first()) == 0 - * eytzinger1_next(eytzinger1_last()) == 0 - */ - static inline unsigned eytzinger1_next(unsigned i, unsigned size) { - EYTZINGER_BUG_ON(i > size); + EYTZINGER_BUG_ON(i == 0 || i > size); if (eytzinger1_right_child(i) <= size) { i = eytzinger1_right_child(i); - i <<= __fls(size + 1) - __fls(i); + i <<= __fls(size) - __fls(i); i >>= i > size; } else { i >>= ffz(i) + 1; @@ -87,12 +77,12 @@ static inline unsigned eytzinger1_next(unsigned i, unsigned size) static inline unsigned eytzinger1_prev(unsigned i, unsigned size) { - EYTZINGER_BUG_ON(i > size); + EYTZINGER_BUG_ON(i == 0 || i > size); if (eytzinger1_left_child(i) <= size) { i = eytzinger1_left_child(i) + 1; - i <<= __fls(size + 1) - __fls(i); + i <<= __fls(size) - __fls(i); i -= 1; i >>= i > size; } else { diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index e75329399c6e..0257a4c3bb4e 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -713,12 +713,6 @@ void eytzinger1_test(void) if (!(size % 4096)) 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)); - - BUG_ON(eytzinger1_prev(eytzinger1_first(size), size) != 0); - BUG_ON(eytzinger1_next(eytzinger1_last(size), size) != 0); - inorder = 1; eytzinger1_for_each(eytz, size) { BUG_ON(__inorder_to_eytzinger1(inorder, size, extra) != eytz); @@ -747,12 +741,6 @@ void eytzinger0_test(void) if (!(size % 4096)) 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)); - - BUG_ON(eytzinger0_prev(eytzinger0_first(size), size) != -1); - BUG_ON(eytzinger0_next(eytzinger0_last(size), size) != -1); - inorder = 0; eytzinger0_for_each(eytz, size) { BUG_ON(__inorder_to_eytzinger0(inorder, size, extra) != eytz);