The generic binary search function bsearch() has no unit tests, while the adjacent sort() function already has KUnit test coverage.
Add comprehensive KUnit tests covering: - Empty arrays, single-element arrays - First/middle/last element hits - Keys outside the array range and in gaps between elements - Duplicate elements and all-identical arrays - Different element sizes (u8, int, u64) - Descending-order arrays with reversed comparator - Struct-based search where key type differs from element type The tests exercise both the exported bsearch() and the inline __inline_bsearch() implementation through the standard API. Signed-off-by: Liu Zhuoran <[email protected]> --- lib/Kconfig.debug | 10 ++ lib/tests/Makefile | 1 + lib/tests/bsearch_kunit.c | 275 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 286 insertions(+) create mode 100644 lib/tests/bsearch_kunit.c diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 8ff5adcfe..67d600e86 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2348,6 +2348,16 @@ config TEST_SORT If unsure, say N. +config BSEARCH_KUNIT_TEST + tristate "Array-based bsearch test" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This option enables the KUnit test for 'bsearch()' at boot, + or at module load time. + + If unsure, say N. + config TEST_DIV64 tristate "64bit/32bit division and modulo test" depends on DEBUG_KERNEL || m diff --git a/lib/tests/Makefile b/lib/tests/Makefile index 7e9c2fa52..4c8b758ef 100644 --- a/lib/tests/Makefile +++ b/lib/tests/Makefile @@ -5,6 +5,7 @@ # KUnit tests CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_BASE64_KUNIT) += base64_kunit.o +obj-$(CONFIG_BSEARCH_KUNIT_TEST) += bsearch_kunit.o obj-$(CONFIG_BITOPS_KUNIT) += bitops_kunit.o obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o obj-$(CONFIG_BITS_TEST) += test_bits.o diff --git a/lib/tests/bsearch_kunit.c b/lib/tests/bsearch_kunit.c new file mode 100644 index 000000000..b3b1d5d98 --- /dev/null +++ b/lib/tests/bsearch_kunit.c @@ -0,0 +1,275 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * KUnit tests for bsearch() + */ + +#include <kunit/test.h> +#include <linux/bsearch.h> +#include <linux/module.h> + +static int cmp_int(const void *a, const void *b) +{ + return *(int *)a - *(int *)b; +} + +static int cmp_int_desc(const void *a, const void *b) +{ + return *(int *)b - *(int *)a; +} + +/* Empty array should return NULL */ +static void bsearch_test_empty(struct kunit *test) +{ + int arr[] = {1}; + int key = 1; + void *result; + + result = bsearch(&key, arr, 0, sizeof(int), cmp_int); + KUNIT_EXPECT_PTR_EQ(test, result, NULL); +} + +/* Single element: found */ +static void bsearch_test_single_hit(struct kunit *test) +{ + int arr[] = {42}; + int key = 42; + void *result; + + result = bsearch(&key, arr, 1, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 42); +} + +/* Single element: not found */ +static void bsearch_test_single_miss(struct kunit *test) +{ + int arr[] = {42}; + int key = 99; + void *result; + + result = bsearch(&key, arr, 1, sizeof(int), cmp_int); + KUNIT_EXPECT_PTR_EQ(test, result, NULL); +} + +/* Multi-element: key at beginning */ +static void bsearch_test_first_element(struct kunit *test) +{ + int arr[] = {10, 20, 30, 40, 50}; + int key = 10; + void *result; + + result = bsearch(&key, arr, 5, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 10); +} + +/* Multi-element: key at end */ +static void bsearch_test_last_element(struct kunit *test) +{ + int arr[] = {10, 20, 30, 40, 50}; + int key = 50; + void *result; + + result = bsearch(&key, arr, 5, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 50); +} + +/* Multi-element: key in the middle */ +static void bsearch_test_middle_element(struct kunit *test) +{ + int arr[] = {10, 20, 30, 40, 50}; + int key = 30; + void *result; + + result = bsearch(&key, arr, 5, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 30); +} + +/* Key smaller than all elements */ +static void bsearch_test_below_range(struct kunit *test) +{ + int arr[] = {10, 20, 30}; + int key = 5; + void *result; + + result = bsearch(&key, arr, 3, sizeof(int), cmp_int); + KUNIT_EXPECT_PTR_EQ(test, result, NULL); +} + +/* Key larger than all elements */ +static void bsearch_test_above_range(struct kunit *test) +{ + int arr[] = {10, 20, 30}; + int key = 35; + void *result; + + result = bsearch(&key, arr, 3, sizeof(int), cmp_int); + KUNIT_EXPECT_PTR_EQ(test, result, NULL); +} + +/* Key in gap between elements */ +static void bsearch_test_in_gap(struct kunit *test) +{ + int arr[] = {10, 20, 30, 40, 50}; + int key = 25; + void *result; + + result = bsearch(&key, arr, 5, sizeof(int), cmp_int); + KUNIT_EXPECT_PTR_EQ(test, result, NULL); +} + +/* Duplicate elements: should find one of them */ +static void bsearch_test_duplicates(struct kunit *test) +{ + int arr[] = {10, 20, 20, 20, 30}; + int key = 20; + void *result; + + result = bsearch(&key, arr, 5, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 20); +} + +/* All elements identical */ +static void bsearch_test_all_same(struct kunit *test) +{ + int arr[] = {7, 7, 7, 7}; + int key = 7; + void *result; + + result = bsearch(&key, arr, 4, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 7); +} + +/* Descending order with reversed comparator */ +static void bsearch_test_descending(struct kunit *test) +{ + int arr[] = {50, 40, 30, 20, 10}; + int key = 30; + void *result; + + result = bsearch(&key, arr, 5, sizeof(int), cmp_int_desc); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 30); +} + +/* 1-byte elements (u8) */ +static int cmp_u8(const void *a, const void *b) +{ + return *(u8 *)a - *(u8 *)b; +} + +static void bsearch_test_u8(struct kunit *test) +{ + u8 arr[] = {1, 3, 5, 7, 9, 11}; + u8 key = 7; + void *result; + + result = bsearch(&key, arr, 6, sizeof(u8), cmp_u8); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(u8 *)result, (u8)7); +} + +/* 8-byte elements (u64) */ +static int cmp_u64(const void *a, const void *b) +{ + if (*(u64 *)a < *(u64 *)b) + return -1; + if (*(u64 *)a > *(u64 *)b) + return 1; + return 0; +} + +static void bsearch_test_u64(struct kunit *test) +{ + u64 arr[] = {100, 200, 300, 400, 500}; + u64 key = 300; + void *result; + + result = bsearch(&key, arr, 5, sizeof(u64), cmp_u64); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(u64 *)result, (u64)300); +} + +/* Two elements: hit first, hit last, miss */ +static void bsearch_test_two_elements(struct kunit *test) +{ + int arr[] = {10, 20}; + int key; + void *result; + + key = 10; + result = bsearch(&key, arr, 2, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 10); + + key = 20; + result = bsearch(&key, arr, 2, sizeof(int), cmp_int); + KUNIT_EXPECT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, *(int *)result, 20); + + key = 15; + result = bsearch(&key, arr, 2, sizeof(int), cmp_int); + KUNIT_EXPECT_PTR_EQ(test, result, NULL); +} + +/* Struct-based search (key type differs from element type) */ +struct sample { + int id; + const char *name; +}; + +static int cmp_sample(const void *key, const void *element) +{ + return *(const int *)key - ((const struct sample *)element)->id; +} + +static void bsearch_test_struct(struct kunit *test) +{ + struct sample arr[] = { + {10, "alpha"}, + {20, "beta"}, + {30, "gamma"}, + {40, "delta"}, + }; + int key = 30; + struct sample *result; + + result = bsearch(&key, arr, 4, sizeof(struct sample), cmp_sample); + KUNIT_ASSERT_NOT_NULL(test, result); + KUNIT_EXPECT_EQ(test, result->id, 30); + KUNIT_EXPECT_STREQ(test, result->name, "gamma"); +} + +static struct kunit_case bsearch_test_cases[] = { + KUNIT_CASE(bsearch_test_empty), + KUNIT_CASE(bsearch_test_single_hit), + KUNIT_CASE(bsearch_test_single_miss), + KUNIT_CASE(bsearch_test_first_element), + KUNIT_CASE(bsearch_test_last_element), + KUNIT_CASE(bsearch_test_middle_element), + KUNIT_CASE(bsearch_test_below_range), + KUNIT_CASE(bsearch_test_above_range), + KUNIT_CASE(bsearch_test_in_gap), + KUNIT_CASE(bsearch_test_duplicates), + KUNIT_CASE(bsearch_test_all_same), + KUNIT_CASE(bsearch_test_descending), + KUNIT_CASE(bsearch_test_u8), + KUNIT_CASE(bsearch_test_u64), + KUNIT_CASE(bsearch_test_two_elements), + KUNIT_CASE(bsearch_test_struct), + {} +}; + +static struct kunit_suite bsearch_test_suite = { + .name = "bsearch", + .test_cases = bsearch_test_cases, +}; + +kunit_test_suites(&bsearch_test_suite); + +MODULE_DESCRIPTION("KUnit tests for bsearch()"); +MODULE_LICENSE("GPL"); -- 2.54.0
