/* * Copyright (c) 2016,2021 Intel Corporation * * SPDX-License-Identifier: Apache-2.0 */ #include #include #include #include #include #include #include #ifdef CONFIG_BIG_ENDIAN #define BIT_INDEX(bit) ((3 - ((bit >> 3) & 0x3)) + 4*(bit >> 5)) #else #define BIT_INDEX(bit) (bit >> 3) #endif #define BIT_VAL(bit) (1 << (bit & 0x7)) #define BITFIELD_SIZE 512 /** * @addtogroup kernel_common_tests * @{ */ /* Helper function to compare two bitarrays */ static bool cmp_u32_arrays(uint32_t *a1, uint32_t *a2, size_t sz) { bool are_equal = true; size_t i; for (i = 0; i < sz; i++) { if (a1[i] != a2[i]) { are_equal = false; printk("%s: [%zu] 0x%x != 0x%x", __func__, i, a1[i], a2[i]); break; } } return are_equal; } #define FAIL_ALLOC_MSG_FMT "sys_bitarray_alloc with region size %i allocated incorrectly" #define FAIL_ALLOC_RET_MSG_FMT "sys_bitarray_alloc with region size %i returned incorrect result" #define FAIL_ALLOC_OFFSET_MSG_FMT "sys_bitarray_alloc with region size %i gave incorrect offset" #define FAIL_FREE_MSG_FMT "sys_bitarray_free with region size %i and offset %i failed" #define FREE 0U void validate_bitarray_define(sys_bitarray_t *ba, size_t num_bits) { size_t num_bundles; int i; num_bundles = ROUND_UP(ROUND_UP(num_bits, 8) / 8, sizeof(uint32_t)) / sizeof(uint32_t); zassert_equal(ba->num_bits, num_bits, "SYS_BITARRAY_DEFINE num_bits expected %u, got %u", num_bits, ba->num_bits); zassert_equal(ba->num_bundles, num_bundles, "SYS_BITARRAY_DEFINE num_bundles expected %u, got %u", num_bundles, ba->num_bundles); for (i = 0; i < num_bundles; i++) { zassert_equal(ba->bundles[i], FREE, "SYS_BITARRAY_DEFINE bundles[%u] not free for num_bits %u", i, num_bits); } } /** * @brief Test defining of bitarrays * * @see SYS_BITARRAY_DEFINE() */ ZTEST(bitarray, test_bitarray_declare) { SYS_BITARRAY_DEFINE(ba_1_bit, 1); SYS_BITARRAY_DEFINE(ba_32_bit, 32); SYS_BITARRAY_DEFINE(ba_33_bit, 33); SYS_BITARRAY_DEFINE(ba_64_bit, 64); SYS_BITARRAY_DEFINE(ba_65_bit, 65); SYS_BITARRAY_DEFINE(ba_128_bit, 128); SYS_BITARRAY_DEFINE(ba_129_bit, 129); /* Test SYS_BITFIELD_DECLARE by asserting that a sufficient number of uint32_t * in the declared array are set as free to represent the number of bits */ validate_bitarray_define(&ba_1_bit, 1); validate_bitarray_define(&ba_32_bit, 32); validate_bitarray_define(&ba_33_bit, 33); validate_bitarray_define(&ba_64_bit, 64); validate_bitarray_define(&ba_65_bit, 65); validate_bitarray_define(&ba_128_bit, 128); validate_bitarray_define(&ba_129_bit, 129); } bool bitarray_bundles_is_zero(sys_bitarray_t *ba) { bool ret = true; unsigned int i; for (i = 0; i < ba->num_bundles; i++) { if (ba->bundles[i] != 0) { ret = false; break; } } return ret; } /** * @brief Test bitarrays set and clear * * @see sys_bitarray_set_bit() * @see sys_bitarray_clear_bit() * @see sys_bitarray_test_bit() * @see sys_bitarray_test_and_set_bit() * @see sys_bitarray_test_and_clear_bit() */ ZTEST(bitarray, test_bitarray_set_clear) { int ret; int bit_val; size_t bit, bundle_idx, bit_idx_in_bundle; /* Bitarrays have embedded spinlocks and can't on the stack. */ if (IS_ENABLED(CONFIG_KERNEL_COHERENCE)) { ztest_test_skip(); } SYS_BITARRAY_DEFINE(ba, 234); for (bit = 0U; bit < ba.num_bits; ++bit) { bundle_idx = bit / (sizeof(ba.bundles[0]) * 8); bit_idx_in_bundle = bit % (sizeof(ba.bundles[0]) * 8); ret = sys_bitarray_set_bit(&ba, bit); zassert_equal(ret, 0, "sys_bitarray_set_bit failed on bit %d", bit); zassert_equal(ba.bundles[bundle_idx], BIT(bit_idx_in_bundle), "sys_bitarray_set_bit did not set bit %d\n", bit); zassert_not_equal(sys_bitfield_test_bit((mem_addr_t)ba.bundles, bit), 0, "sys_bitarray_set_bit did not set bit %d\n", bit); ret = sys_bitarray_test_bit(&ba, bit, &bit_val); zassert_equal(ret, 0, "sys_bitarray_test_bit failed at bit %d", bit); zassert_equal(bit_val, 1, "sys_bitarray_test_bit did not detect bit %d\n", bit); ret = sys_bitarray_clear_bit(&ba, bit); zassert_equal(ret, 0, "sys_bitarray_clear_bit failed at bit %d", bit); zassert_equal(ba.bundles[bundle_idx], 0, "sys_bitarray_clear_bit did not clear bit %d\n", bit); zassert_equal(sys_bitfield_test_bit((mem_addr_t)ba.bundles, bit), 0, "sys_bitarray_set_bit did not set bit %d\n", bit); ret = sys_bitarray_test_bit(&ba, bit, &bit_val); zassert_equal(ret, 0, "sys_bitarray_test_bit failed at bit %d", bit); zassert_equal(bit_val, 0, "sys_bitarray_test_bit erroneously detected bit %d\n", bit); ret = sys_bitarray_test_and_set_bit(&ba, bit, &bit_val); zassert_equal(ret, 0, "sys_bitarray_test_and_set_bit failed at bit %d", bit); zassert_equal(bit_val, 0, "sys_bitarray_test_and_set_bit erroneously detected bit %d\n", bit); zassert_equal(ba.bundles[bundle_idx], BIT(bit_idx_in_bundle), "sys_bitarray_test_and_set_bit did not set bit %d\n", bit); zassert_not_equal(sys_bitfield_test_bit((mem_addr_t)ba.bundles, bit), 0, "sys_bitarray_set_bit did not set bit %d\n", bit); ret = sys_bitarray_test_and_set_bit(&ba, bit, &bit_val); zassert_equal(ret, 0, "sys_bitarray_test_and_set_bit failed at bit %d", bit); zassert_equal(bit_val, 1, "sys_bitarray_test_and_set_bit did not detect bit %d\n", bit); zassert_equal(ba.bundles[bundle_idx], BIT(bit_idx_in_bundle), "sys_bitarray_test_and_set_bit cleared bit %d\n", bit); zassert_not_equal(sys_bitfield_test_bit((mem_addr_t)ba.bundles, bit), 0, "sys_bitarray_set_bit did not set bit %d\n", bit); ret = sys_bitarray_test_and_clear_bit(&ba, bit, &bit_val); zassert_equal(ret, 0, "sys_bitarray_test_and_clear_bit failed at bit %d", bit); zassert_equal(bit_val, 1, "sys_bitarray_test_and_clear_bit did not detect bit %d\n", bit); zassert_equal(ba.bundles[bundle_idx], 0, "sys_bitarray_test_and_clear_bit did not clear bit %d\n", bit); zassert_equal(sys_bitfield_test_bit((mem_addr_t)ba.bundles, bit), 0, "sys_bitarray_set_bit did not set bit %d\n", bit); ret = sys_bitarray_test_and_clear_bit(&ba, bit, &bit_val); zassert_equal(ret, 0, "sys_bitarray_test_and_clear_bit failed at bit %d", bit); zassert_equal(bit_val, 0, "sys_bitarray_test_and_clear_bit erroneously detected bit %d\n", bit); zassert_equal(ba.bundles[bundle_idx], 0, "sys_bitarray_test_and_clear_bit set bit %d\n", bit); zassert_equal(sys_bitfield_test_bit((mem_addr_t)ba.bundles, bit), 0, "sys_bitarray_set_bit did not set bit %d\n", bit); } /* All this should fail because we go outside of * total bits in bit array. Also needs to make sure bits * are not changed. */ ret = sys_bitarray_set_bit(&ba, ba.num_bits); zassert_not_equal(ret, 0, "sys_bitarray_set_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_set_bit() erroneously changed bitarray"); ret = sys_bitarray_clear_bit(&ba, ba.num_bits); zassert_not_equal(ret, 0, "sys_bitarray_clear_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_clear_bit() erroneously changed bitarray"); ret = sys_bitarray_test_bit(&ba, ba.num_bits, &bit_val); zassert_not_equal(ret, 0, "sys_bitarray_test_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_test_bit() erroneously changed bitarray"); ret = sys_bitarray_test_and_set_bit(&ba, ba.num_bits, &bit_val); zassert_not_equal(ret, 0, "sys_bitarray_test_and_set_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_test_and_set_bit() erroneously changed bitarray"); ret = sys_bitarray_test_and_clear_bit(&ba, ba.num_bits, &bit_val); zassert_not_equal(ret, 0, "sys_bitarray_test_and_clear_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_test_and_clear_bit() erroneously changed bitarray"); ret = sys_bitarray_set_bit(&ba, -1); zassert_not_equal(ret, 0, "sys_bitarray_set_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_set_bit() erroneously changed bitarray"); ret = sys_bitarray_clear_bit(&ba, -1); zassert_not_equal(ret, 0, "sys_bitarray_clear_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_clear_bit() erroneously changed bitarray"); ret = sys_bitarray_test_bit(&ba, -1, &bit_val); zassert_not_equal(ret, 0, "sys_bitarray_test_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_test_bit() erroneously changed bitarray"); ret = sys_bitarray_test_and_set_bit(&ba, -1, &bit_val); zassert_not_equal(ret, 0, "sys_bitarray_test_and_set_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_test_and_set_bit() erroneously changed bitarray"); ret = sys_bitarray_test_and_clear_bit(&ba, -1, &bit_val); zassert_not_equal(ret, 0, "sys_bitarray_test_and_clear_bit() should fail but not"); zassert_true(bitarray_bundles_is_zero(&ba), "sys_bitarray_test_and_clear_bit() erroneously changed bitarray"); } void alloc_and_free_predefined(void) { int ret; size_t offset; uint32_t ba_128_expected[4]; SYS_BITARRAY_DEFINE(ba_128, 128); printk("Testing bit array alloc and free with predefined patterns\n"); /* Pre-populate the bits */ ba_128.bundles[0] = 0x0F0F070F; ba_128.bundles[1] = 0x0F0F0F0F; ba_128.bundles[2] = 0x0F0F0F0F; ba_128.bundles[3] = 0x0F0F0000; /* Expected values */ ba_128_expected[0] = 0x0F0FFF0F; ba_128_expected[1] = 0x0F0F0F0F; ba_128_expected[2] = 0x0F0F0F0F; ba_128_expected[3] = 0x0F0F0000; ret = sys_bitarray_alloc(&ba_128, 5, &offset); zassert_equal(ret, 0, "sys_bitarray_alloc() failed: %d", ret); zassert_equal(offset, 11, "sys_bitarray_alloc() offset expected %d, got %d", 11, offset); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_alloc() failed bits comparison"); ret = sys_bitarray_alloc(&ba_128, 16, &offset); ba_128_expected[2] = 0xFF0F0F0F; ba_128_expected[3] = 0x0F0F0FFF; zassert_equal(ret, 0, "sys_bitarray_alloc() failed: %d", ret); zassert_equal(offset, 92, "sys_bitarray_alloc() offset expected %d, got %d", 92, offset); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_alloc() failed bits comparison"); ret = sys_bitarray_free(&ba_128, 5, 11); ba_128_expected[0] = 0x0F0F070F; zassert_equal(ret, 0, "sys_bitarray_free() failed: %d", ret); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_free() failed bits comparison"); ret = sys_bitarray_free(&ba_128, 5, 0); zassert_not_equal(ret, 0, "sys_bitarray_free() should fail but not"); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_free() failed bits comparison"); ret = sys_bitarray_free(&ba_128, 24, 92); zassert_not_equal(ret, 0, "sys_bitarray_free() should fail but not"); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_free() failed bits comparison"); ret = sys_bitarray_free(&ba_128, 16, 92); ba_128_expected[2] = 0x0F0F0F0F; ba_128_expected[3] = 0x0F0F0000; zassert_equal(ret, 0, "sys_bitarray_free() failed: %d", ret); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_free() failed bits comparison"); /* test in-between bundles */ ba_128.bundles[0] = 0x7FFFFFFF; ba_128.bundles[1] = 0xFFFFFFFF; ba_128.bundles[2] = 0x00000000; ba_128.bundles[3] = 0x00000000; ba_128_expected[0] = 0x7FFFFFFF; ba_128_expected[1] = 0xFFFFFFFF; ba_128_expected[2] = 0xFFFFFFFF; ba_128_expected[3] = 0x00000003; ret = sys_bitarray_alloc(&ba_128, 34, &offset); zassert_equal(ret, 0, "sys_bitarray_alloc() failed: %d", ret); zassert_equal(offset, 64, "sys_bitarray_alloc() offset expected %d, got %d", 64, offset); zassert_true(cmp_u32_arrays(ba_128.bundles, ba_128_expected, ba_128.num_bundles), "sys_bitarray_alloc() failed bits comparison"); } static inline size_t count_bits(uint32_t val) { /* Implements Brian Kernighan’s Algorithm * to count bits. */ size_t cnt = 0; while (val != 0) { val = val & (val - 1); cnt++; } return cnt; } size_t get_bitarray_popcnt(sys_bitarray_t *ba) { size_t popcnt = 0; unsigned int idx; for (idx = 0; idx < ba->num_bundles; idx++) { popcnt += count_bits(ba->bundles[idx]); } return popcnt; } void alloc_and_free_loop(int divisor) { int ret; size_t offset; size_t bit; size_t num_bits; size_t cur_popcnt; size_t expected_popcnt = 0; SYS_BITARRAY_DEFINE(ba, 234); printk("Testing bit array alloc and free with divisor %d\n", divisor); for (bit = 0U; bit < ba.num_bits; ++bit) { cur_popcnt = get_bitarray_popcnt(&ba); zassert_equal(cur_popcnt, expected_popcnt, "bit count expected %u, got %u (at bit %u)", expected_popcnt, cur_popcnt, bit); /* Allocate half of remaining bits */ num_bits = (ba.num_bits - bit) / divisor; ret = sys_bitarray_alloc(&ba, num_bits, &offset); if (num_bits == 0) { zassert_not_equal(ret, 0, "sys_bitarray_free() should fail but not (bit %u)", bit); } else { zassert_equal(ret, 0, "sys_bitarray_alloc() failed (%d) at bit %u", ret, bit); zassert_equal(offset, bit, "sys_bitarray_alloc() offset expected %d, got %d", bit, offset); expected_popcnt += num_bits; } cur_popcnt = get_bitarray_popcnt(&ba); zassert_equal(cur_popcnt, expected_popcnt, "bit count expected %u, got %u (at bit %u)", expected_popcnt, cur_popcnt, bit); /* Free all but the first bit of allocated region */ ret = sys_bitarray_free(&ba, (num_bits - 1), (bit + 1)); if ((num_bits == 0) || ((num_bits - 1) == 0)) { zassert_not_equal(ret, 0, "sys_bitarray_free() should fail but not (bit %u)", bit); } else { zassert_equal(ret, 0, "sys_bitarray_free() failed (%d) at bit %u", ret, (bit + 1)); expected_popcnt -= num_bits - 1; } } } void alloc_and_free_interval(void) { int ret; size_t cnt; size_t offset; size_t expected_offset; size_t expected_popcnt, cur_popcnt; /* Make sure number of bits is multiple of 8 */ SYS_BITARRAY_DEFINE(ba, 152); printk("Testing bit array interval alloc and free\n"); /* Pre-populate the bits so that 4-bit already allocated, * then 4 free bits, and repeat. */ for (cnt = 0; cnt < ba.num_bundles; cnt++) { ba.bundles[cnt] = 0x0F0F0F0F; } expected_offset = 4; expected_popcnt = get_bitarray_popcnt(&ba); for (cnt = 0; cnt <= (ba.num_bits / 8); cnt++) { ret = sys_bitarray_alloc(&ba, 4, &offset); if (cnt == (ba.num_bits / 8)) { zassert_not_equal(ret, 0, "sys_bitarray_free() should fail but not (cnt %u)", cnt); } else { zassert_equal(ret, 0, "sys_bitarray_alloc() failed (%d) (cnt %u)", ret, cnt); zassert_equal(offset, expected_offset, "offset expected %u, got %u (cnt %u)", expected_offset, offset, cnt); expected_popcnt += 4; cur_popcnt = get_bitarray_popcnt(&ba); zassert_equal(cur_popcnt, expected_popcnt, "bit count expected %u, got %u (cnt %u)", expected_popcnt, cur_popcnt, cnt); expected_offset += 8; } } } /** * @brief Test bitarrays allocation and free * * @see sys_bitarray_alloc() * @see sys_bitarray_free() */ ZTEST(bitarray, test_bitarray_alloc_free) { int i; /* Bitarrays have embedded spinlocks and can't on the stack. */ if (IS_ENABLED(CONFIG_KERNEL_COHERENCE)) { ztest_test_skip(); } alloc_and_free_predefined(); i = 1; while (i < 65) { alloc_and_free_loop(i); i *= 2; } alloc_and_free_interval(); } ZTEST(bitarray, test_bitarray_popcount_region) { int ret; size_t count; /* Bitarrays have embedded spinlocks and can't on the stack. */ if (IS_ENABLED(CONFIG_KERNEL_COHERENCE)) { ztest_test_skip(); } SYS_BITARRAY_DEFINE(ba, 128); printk("Testing bit array region popcount spanning single bundle\n"); /* Pre-populate the bits */ ba.bundles[0] = 0x00000005; ba.bundles[1] = 0x00000000; ba.bundles[2] = 0x00000000; ba.bundles[3] = 0x00000000; ret = sys_bitarray_popcount_region(&ba, 1, 0, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 1, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 1, 1, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 0, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 2, 0, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 1, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 3, 0, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 2, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 3, 1, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 1, "sys_bitarray_popcount_region() returned unexpected count: %d", count); printk("Testing bit array region popcount spanning multiple bundles\n"); /* Pre-populate the bits. * First and last bit of bitarray are set */ ba.bundles[0] = 0x00000001; ba.bundles[1] = 0x00000000; ba.bundles[2] = 0x00000000; ba.bundles[3] = 0x80000000; ret = sys_bitarray_popcount_region(&ba, 126, 1, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 0, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 126, 0, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 1, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 127, 1, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 1, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 1, 127, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 1, "sys_bitarray_popcount_region() returned unexpected count: %d", count); ret = sys_bitarray_popcount_region(&ba, 128, 0, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); zassert_equal(count, 2, "sys_bitarray_popcount_region() returned unexpected count: %d", count); printk("Testing edge/error cases\n"); ret = sys_bitarray_popcount_region(&ba, 0, 0, &count); zassert_equal(ret, -EINVAL, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); ret = sys_bitarray_popcount_region(&ba, 0, 128, &count); zassert_equal(ret, -EINVAL, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); ret = sys_bitarray_popcount_region(&ba, 128, 0, &count); zassert_equal(ret, 0, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); ret = sys_bitarray_popcount_region(&ba, 128, 1, &count); zassert_equal(ret, -EINVAL, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); ret = sys_bitarray_popcount_region(&ba, 129, 0, &count); zassert_equal(ret, -EINVAL, "sys_bitarray_popcount_region() returned unexpected value: %d", ret); } ZTEST(bitarray, test_bitarray_xor) { int ret; /* Bitarrays have embedded spinlocks and can't on the stack. */ if (IS_ENABLED(CONFIG_KERNEL_COHERENCE)) { ztest_test_skip(); } SYS_BITARRAY_DEFINE(ba, 128); SYS_BITARRAY_DEFINE(bb, 128); SYS_BITARRAY_DEFINE(bc, 129); printk("Testing bit array region xor spanning single bundle\n"); /* Pre-populate the bits */ ba.bundles[0] = 0x80001001; ba.bundles[1] = 0x10000008; ba.bundles[2] = 0xFFFFFFFF; ba.bundles[3] = 0x00000000; bb.bundles[0] = 0x80010001; bb.bundles[1] = 0x10000008; bb.bundles[2] = 0xFFFFFFFF; bb.bundles[3] = 0x00000000; ret = sys_bitarray_xor(&ba, &bb, 32, 0); zassert_equal(ret, 0, "sys_bitarray_xor() returned unexpected value: %d", ret); zassert_equal(ba.bundles[0], 0x00011000, "sys_bitarray_xor() result unexpected: %x", ba.bundles[0]); zassert_equal(bb.bundles[0], 0x80010001, "sys_bitarray_xor() result unexpected: %x", bb.bundles[0]); zassert_equal(ba.bundles[1], 0x10000008, "sys_bitarray_xor() result unexpected: %x", ba.bundles[1]); zassert_equal(bb.bundles[1], 0x10000008, "sys_bitarray_xor() result unexpected: %x", bb.bundles[1]); zassert_equal(ba.bundles[2], 0xFFFFFFFF, "sys_bitarray_xor() result unexpected: %x", ba.bundles[2]); zassert_equal(bb.bundles[2], 0xFFFFFFFF, "sys_bitarray_xor() result unexpected: %x", bb.bundles[2]); zassert_equal(ba.bundles[3], 0x00000000, "sys_bitarray_xor() result unexpected: %x", ba.bundles[3]); zassert_equal(bb.bundles[3], 0x00000000, "sys_bitarray_xor() result unexpected: %x", bb.bundles[3]); /* Pre-populate the bits */ ba.bundles[0] = 0x80001001; ba.bundles[1] = 0x10000008; ba.bundles[2] = 0xFFFFFFFF; ba.bundles[3] = 0x00000000; bb.bundles[0] = 0x80010001; bb.bundles[1] = 0x10000008; bb.bundles[2] = 0xFFFFFFFF; bb.bundles[3] = 0x00000000; ret = sys_bitarray_xor(&ba, &bb, 16, 0); zassert_equal(ret, 0, "sys_bitarray_xor() returned unexpected value: %d", ret); zassert_equal(ba.bundles[0], 0x80001000, "sys_bitarray_xor() result unexpected: %x", ba.bundles[0]); zassert_equal(bb.bundles[0], 0x80010001, "sys_bitarray_xor() result unexpected: %x", bb.bundles[0]); /* Pre-populate the bits */ ba.bundles[0] = 0x80001001; ba.bundles[1] = 0x10000008; ba.bundles[2] = 0xFFFFFFFF; ba.bundles[3] = 0x00000000; bb.bundles[0] = 0x80010001; bb.bundles[1] = 0x10000008; bb.bundles[2] = 0xFFFFFFFF; bb.bundles[3] = 0x00000000; ret = sys_bitarray_xor(&ba, &bb, 16, 16); zassert_equal(ret, 0, "sys_bitarray_xor() returned unexpected value: %d", ret); zassert_equal(ba.bundles[0], 0x00011001, "sys_bitarray_xor() result unexpected: %x", ba.bundles[0]); zassert_equal(bb.bundles[0], 0x80010001, "sys_bitarray_xor() result unexpected: %x", bb.bundles[0]); printk("Testing bit array region xor spanning multiple bundles\n"); /* Pre-populate the bits */ ba.bundles[0] = 0x00000000; ba.bundles[1] = 0xFFFFFFFF; ba.bundles[2] = 0xFFFFFFFF; ba.bundles[3] = 0xFFFFFFFF; bb.bundles[0] = 0x00000000; bb.bundles[1] = 0xFFFFFFFF; bb.bundles[2] = 0xFFFFFFFF; bb.bundles[3] = 0xFFFFFFFF; ret = sys_bitarray_xor(&ba, &bb, 32*3 - 2, 32 + 1); zassert_equal(ret, 0, "sys_bitarray_xor() returned unexpected value: %d", ret); zassert_equal(ba.bundles[0], 0x00000000, "sys_bitarray_xor() result unexpected: %x", ba.bundles[0]); zassert_equal(ba.bundles[1], 0x00000001, "sys_bitarray_xor() result unexpected: %x", ba.bundles[1]); zassert_equal(ba.bundles[2], 0x00000000, "sys_bitarray_xor() result unexpected: %x", ba.bundles[2]); zassert_equal(ba.bundles[3], 0x80000000, "sys_bitarray_xor() result unexpected: %x", ba.bundles[3]); printk("Testing error cases\n"); /* Pre-populate the bits */ ba.bundles[0] = 0x00000000; ba.bundles[1] = 0x00000000; ba.bundles[2] = 0x00000000; ba.bundles[3] = 0x00000000; bb.bundles[0] = 0x00000000; bb.bundles[1] = 0x00000000; bb.bundles[2] = 0x00000000; bb.bundles[3] = 0x00000000; bc.bundles[0] = 0x00000000; bc.bundles[1] = 0x00000000; bc.bundles[2] = 0x00000000; bc.bundles[3] = 0x00000000; bc.bundles[4] = 0x00000000; ret = sys_bitarray_xor(&ba, &bb, 32, 0); zassert_equal(ret, 0, "sys_bitarray_xor() returned unexpected value: %d", ret); ret = sys_bitarray_xor(&ba, &bc, 32, 0); zassert_equal(ret, -EINVAL, "sys_bitarray_xor() returned unexpected value: %d", ret); ret = sys_bitarray_xor(&bc, &ba, 32, 0); zassert_equal(ret, -EINVAL, "sys_bitarray_xor() returned unexpected value: %d", ret); ret = sys_bitarray_xor(&ba, &bb, 128, 0); zassert_equal(ret, 0, "sys_bitarray_xor() returned unexpected value: %d", ret); ret = sys_bitarray_xor(&ba, &bb, 128, 1); zassert_equal(ret, -EINVAL, "sys_bitarray_xor() returned unexpected value: %d", ret); ret = sys_bitarray_xor(&ba, &bb, 129, 0); zassert_equal(ret, -EINVAL, "sys_bitarray_xor() returned unexpected value: %d", ret); ret = sys_bitarray_xor(&ba, &bb, 0, 0); zassert_equal(ret, -EINVAL, "sys_bitarray_xor() returned unexpected value: %d", ret); } ZTEST(bitarray, test_bitarray_find_nth_set) { int ret; size_t found_at; /* Bitarrays have embedded spinlocks and can't on the stack. */ if (IS_ENABLED(CONFIG_KERNEL_COHERENCE)) { ztest_test_skip(); } SYS_BITARRAY_DEFINE(ba, 128); printk("Testing bit array nth bit set finding spanning single bundle\n"); /* Pre-populate the bits */ ba.bundles[0] = 0x80000001; ba.bundles[1] = 0x80000001; ba.bundles[2] = 0x80000001; ba.bundles[3] = 0x80000001; ret = sys_bitarray_find_nth_set(&ba, 1, 1, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 0, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 1, 32, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 0, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 2, 32, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 31, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 1, 31, 1, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 31, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 2, 31, 1, &found_at); zassert_equal(ret, 1, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); printk("Testing bit array nth bit set finding spanning multiple bundles\n"); ret = sys_bitarray_find_nth_set(&ba, 1, 128, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 0, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 8, 128, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 127, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 8, 128, 1, &found_at); zassert_equal(ret, -EINVAL, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); ret = sys_bitarray_find_nth_set(&ba, 7, 127, 1, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 127, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 7, 127, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 96, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 6, 127, 1, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 96, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 6, 127, 1, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 96, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 1, 32, 48, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 63, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); ret = sys_bitarray_find_nth_set(&ba, 2, 32, 48, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); zassert_equal(found_at, 64, "sys_bitarray_find_nth_set() returned unexpected found_at: %d", found_at); printk("Testing error cases\n"); ret = sys_bitarray_find_nth_set(&ba, 1, 128, 0, &found_at); zassert_equal(ret, 0, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); ret = sys_bitarray_find_nth_set(&ba, 1, 128, 1, &found_at); zassert_equal(ret, -EINVAL, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); ret = sys_bitarray_find_nth_set(&ba, 1, 129, 0, &found_at); zassert_equal(ret, -EINVAL, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); ret = sys_bitarray_find_nth_set(&ba, 0, 128, 0, &found_at); zassert_equal(ret, -EINVAL, "sys_bitarray_find_nth_set() returned unexpected value: %d", ret); } ZTEST(bitarray, test_bitarray_region_set_clear) { int ret; /* Bitarrays have embedded spinlocks and can't on the stack. */ if (IS_ENABLED(CONFIG_KERNEL_COHERENCE)) { ztest_test_skip(); } uint32_t ba_expected[4]; SYS_BITARRAY_DEFINE(ba, 64); printk("Testing bit array region bit tests\n"); /* Pre-populate the bits */ ba.bundles[0] = 0xFF0F0F0F; ba.bundles[1] = 0x0F0F0FFF; zassert_true(sys_bitarray_is_region_set(&ba, 4, 0)); zassert_true(sys_bitarray_is_region_set(&ba, 12, 32)); zassert_true(sys_bitarray_is_region_set(&ba, 8, 32)); zassert_true(sys_bitarray_is_region_set(&ba, 14, 30)); zassert_true(sys_bitarray_is_region_set(&ba, 20, 24)); zassert_false(sys_bitarray_is_region_cleared(&ba, 4, 0)); zassert_false(sys_bitarray_is_region_cleared(&ba, 12, 32)); zassert_false(sys_bitarray_is_region_cleared(&ba, 8, 32)); zassert_false(sys_bitarray_is_region_cleared(&ba, 14, 30)); zassert_false(sys_bitarray_is_region_cleared(&ba, 20, 24)); ba.bundles[0] = ~ba.bundles[0]; ba.bundles[1] = ~ba.bundles[1]; zassert_true(sys_bitarray_is_region_cleared(&ba, 4, 0)); zassert_true(sys_bitarray_is_region_cleared(&ba, 12, 32)); zassert_true(sys_bitarray_is_region_cleared(&ba, 8, 32)); zassert_true(sys_bitarray_is_region_cleared(&ba, 14, 30)); zassert_true(sys_bitarray_is_region_cleared(&ba, 20, 24)); zassert_false(sys_bitarray_is_region_set(&ba, 4, 0)); zassert_false(sys_bitarray_is_region_set(&ba, 12, 32)); zassert_false(sys_bitarray_is_region_set(&ba, 8, 32)); zassert_false(sys_bitarray_is_region_set(&ba, 14, 30)); zassert_false(sys_bitarray_is_region_set(&ba, 20, 24)); zassert_false(sys_bitarray_is_region_set(&ba, 10, 60)); zassert_false(sys_bitarray_is_region_cleared(&ba, 10, 60)); zassert_false(sys_bitarray_is_region_set(&ba, 8, 120)); zassert_false(sys_bitarray_is_region_cleared(&ba, 8, 120)); printk("Testing bit array region bit manipulations\n"); /* Pre-populate the bits */ ba.bundles[0] = 0xFF0F0F0F; ba.bundles[1] = 0x0F0F0FFF; /* Expected values */ ba_expected[0] = 0xFF0F0F0F; ba_expected[1] = 0x0F0F0FFF; ret = sys_bitarray_set_region(&ba, 4, 0); zassert_equal(ret, 0, "sys_bitarray_set_region() failed: %d", ret); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_set_region() failed bits comparison"); ret = sys_bitarray_set_region(&ba, 4, 4); ba_expected[0] = 0xFF0F0FFF; zassert_equal(ret, 0, "sys_bitarray_set_region() failed: %d", ret); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_set_region() failed bits comparison"); ret = sys_bitarray_clear_region(&ba, 4, 4); ba_expected[0] = 0xFF0F0F0F; zassert_equal(ret, 0, "sys_bitarray_clear_region() failed: %d", ret); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_clear_region() failed bits comparison"); ret = sys_bitarray_clear_region(&ba, 14, 30); ba_expected[0] = 0x3F0F0F0F; ba_expected[1] = 0x0F0F0000; zassert_equal(ret, 0, "sys_bitarray_clear_region() failed: %d", ret); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_clear_region() failed bits comparison"); ret = sys_bitarray_set_region(&ba, 14, 30); ba_expected[0] = 0xFF0F0F0F; ba_expected[1] = 0x0F0F0FFF; zassert_equal(ret, 0, "sys_bitarray_set_region() failed: %d", ret); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_set_region() failed bits comparison"); ret = sys_bitarray_set_region(&ba, 10, 60); zassert_equal(ret, -EINVAL, "sys_bitarray_set_region() should fail but not"); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_set_region() failed bits comparison"); ret = sys_bitarray_set_region(&ba, 8, 120); zassert_equal(ret, -EINVAL, "sys_bitarray_set_region() should fail but not"); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_set_region() failed bits comparison"); ret = sys_bitarray_clear_region(&ba, 10, 60); zassert_equal(ret, -EINVAL, "sys_bitarray_clear_region() should fail but not"); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_clear_region() failed bits comparison"); ret = sys_bitarray_clear_region(&ba, 8, 120); zassert_equal(ret, -EINVAL, "sys_bitarray_clear_region() should fail but not"); zassert_true(cmp_u32_arrays(ba.bundles, ba_expected, ba.num_bundles), "sys_bitarray_clear_region() failed bits comparison"); SYS_BITARRAY_DEFINE(bw, 128); /* Pre-populate the bits */ bw.bundles[0] = 0xFF0F0F0F; bw.bundles[1] = 0xF0000000; bw.bundles[2] = 0xFFFFFFFF; bw.bundles[3] = 0x0000000F; zassert_true(sys_bitarray_is_region_set(&bw, 40, 60)); zassert_false(sys_bitarray_is_region_cleared(&bw, 40, 60)); bw.bundles[2] = 0xFFFEEFFF; zassert_false(sys_bitarray_is_region_set(&bw, 40, 60)); zassert_false(sys_bitarray_is_region_cleared(&bw, 40, 60)); bw.bundles[1] = 0x0FFFFFFF; bw.bundles[2] = 0x00000000; bw.bundles[3] = 0xFFFFFFF0; zassert_true(sys_bitarray_is_region_cleared(&bw, 40, 60)); zassert_false(sys_bitarray_is_region_set(&bw, 40, 60)); bw.bundles[2] = 0x00011000; zassert_false(sys_bitarray_is_region_cleared(&bw, 40, 60)); zassert_false(sys_bitarray_is_region_set(&bw, 40, 60)); } /** * @brief Test find MSB and LSB operations * * @details Verify the functions that find out the most significant * bit and least significant bit work as expected. * * @see find_msb_set(), find_lsb_set() */ ZTEST(bitarray, test_ffs) { uint32_t value; unsigned int bit; /* boundary test, input is min */ value = 0x0; zassert_equal(find_msb_set(value), 0, "MSB is not matched"); zassert_equal(find_lsb_set(value), 0, "LSB is not matched"); /* boundary test, input is min + 1 */ value = 0x00000001; zassert_equal(find_msb_set(value), 1, "MSB is not matched"); zassert_equal(find_lsb_set(value), 1, "LSB is not matched"); /* average value test */ value = 0x80000000; zassert_equal(find_msb_set(value), 32, "MSB is not matched"); zassert_equal(find_lsb_set(value), 32, "LSB is not matched"); /* mediate value test */ value = 0x000FF000; zassert_equal(find_msb_set(value), 20, "MSB is not matched"); zassert_equal(find_lsb_set(value), 13, "LSB is not matched"); /* boundary test, input is max */ value = 0xffffffff; zassert_equal(find_msb_set(value), 32, "MSB is not matched"); zassert_equal(find_lsb_set(value), 1, "LSB is not matched"); /* boundary test, input is max - 1 */ value = 0xfffffffe; zassert_equal(find_msb_set(value), 32, "MSB is not matched"); zassert_equal(find_lsb_set(value), 2, "LSB is not matched"); /* equivalent class testing, each bit means a class */ for (bit = 0; bit < 32 ; bit++) { value = 1UL << bit; zassert_equal(find_msb_set(value), bit + 1, "MSB is not matched"); zassert_equal(find_lsb_set(value), bit + 1, "LSB is not matched"); } } extern void *common_setup(void); ZTEST_SUITE(bitarray, NULL, common_setup, NULL, NULL, NULL); /** * @} */