@@ -2678,6 +2678,14 @@ config SIPHASH_KUNIT_TEST
This is intended to help people writing architecture-specific
optimized versions. If unsure, say N.
+config BITQUEUE_KUNIT_TEST
+ tristate "Test <linux/bitqueue.h>" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ default KUNIT_ALL_TESTS
+ help
+ Enable this option to test the kernel's bit queue implementation
+ (<linux/bitqueue.h>).
+
config TEST_UDELAY
tristate "udelay test driver"
help
@@ -394,6 +394,7 @@ CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN)
obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o
obj-$(CONFIG_STRSCPY_KUNIT_TEST) += strscpy_kunit.o
obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o
+obj-$(CONFIG_BITQUEUE_KUNIT_TEST) += test_bitqueue.o
obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o
new file mode 100644
@@ -0,0 +1,244 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Test cases for struct bitq, a simple bit queue.
+ */
+
+#include <kunit/test.h>
+#include <linux/bitqueue.h>
+#include <linux/slab.h>
+
+/* Set up a bit queue containing @size bytes. */
+static void bitq_setup(struct bitq *it, size_t size)
+{
+ u8 *data = kmalloc(size, GFP_KERNEL);
+
+ bitq_init(it, data, size);
+}
+
+/* Tear down the bit queue. */
+static void bitq_teardown(struct bitq *it)
+{
+ kfree(it->data);
+ memset(it, 0, sizeof(*it));
+}
+
+/* Test that nothing can be popped from an empty queue. */
+static void test_empty(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+
+ /* Allocate a two-byte queue. */
+ bitq_setup(&it, 2);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), -1);
+ bitq_teardown(&it);
+}
+
+/* Test that simple byte-granular enqueue/dequeue operations work. */
+static void test_basic_enqueue_dequeue(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+
+ /* Allocate a two-byte queue. */
+ bitq_setup(&it, 2);
+ /* Enqueue two 8-bit values. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0xaa, 8), 8);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0xbb, 8), 8);
+ /* Cannot enqueue the third byte. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 1, 8), -1);
+ /* Dequeue two bytes. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0xaa);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0xbb);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), -1);
+ bitq_teardown(&it);
+}
+
+/* Test that values shorter than 8 bits can be enqueued and dequeued. */
+static void test_shorter_than_byte(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+
+ /* Allocate a two-byte queue. */
+ bitq_setup(&it, 2);
+ /* Enqueue two 0b101 values. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b101, 3), 3);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b101, 3), 3);
+ /* The first byte of the queue is now 0b10110100. */
+
+ /* Now dequeue three 2-bit values: 0b10, 0b11, 0b01. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 2), 2);
+ KUNIT_EXPECT_EQ(test, val, 0b10);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 2), 2);
+ KUNIT_EXPECT_EQ(test, val, 0b11);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 2), 2);
+ KUNIT_EXPECT_EQ(test, val, 0b01);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 1), -1);
+ bitq_teardown(&it);
+}
+
+/* Test that bits are carried over correctly if they do not fit. */
+static void test_carryover(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+ int i;
+
+ /* Allocate a three-byte queue. */
+ bitq_setup(&it, 3);
+ /* Enqueue 0b100 seven times. */
+ for (i = 0; i < 7; i++)
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b100, 3), 3);
+ /* Now dequeue three 7-bit values: 0b1001001, 0b0010010, 0b0100100. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 7), 7);
+ KUNIT_EXPECT_EQ(test, val, 0b1001001);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 7), 7);
+ KUNIT_EXPECT_EQ(test, val, 0b0010010);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 7), 7);
+ KUNIT_EXPECT_EQ(test, val, 0b0100100);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 1), -1);
+ bitq_teardown(&it);
+}
+
+/*
+ * Test case extracted from the EA0 tag compression algorithm, where
+ * carried over bits were accidentally written into the previous byte.
+ */
+static void test_carryover_ea0(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+
+ /* Allocate a three-byte queue. */
+ bitq_setup(&it, 3);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b100, 3), 3);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b1010, 4), 4);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b0000, 4), 4);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b1010, 4), 4);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0b1011, 4), 4);
+
+ /* Now dequeue two byte values: 0b10010100, 0b00010101. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0b10010100);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0b00010101);
+ /* And the remaining 0b011. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 3), 3);
+ KUNIT_EXPECT_EQ(test, val, 0b011);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 1), -1);
+ bitq_teardown(&it);
+}
+
+/* Test that upper bits of the pushed value are discarded. */
+static void test_trim_upper_bits(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+
+ /* Allocate a two-byte queue. */
+ bitq_setup(&it, 2);
+ /* Enqueue two values that do not fit into 4 bits. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0xab, 4), 4);
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0xab, 4), 4);
+ /* The first byte of the queue is now 0xbb. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0xbb);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 1), -1);
+ bitq_teardown(&it);
+}
+
+/* Another test for discarding the upper bits. */
+static void test_trim_upper_bits2(struct kunit *test)
+{
+ struct bitq it;
+ u8 val = 0;
+
+ /* Allocate a two-byte queue. */
+ bitq_setup(&it, 2);
+ /* Push seven zero bits. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0, 7), 7);
+ /* Push a single 1 bit, but pass a bigger value to bitq_enqueue(). */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0xff, 1), 1);
+ /* The first byte of the queue is now 0x01. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0x01);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 1), -1);
+ bitq_teardown(&it);
+}
+
+/* Test that a NULL value can be used as output of bitq_dequeue() */
+static void test_dequeue_to_null(struct kunit *test)
+{
+ struct bitq it;
+
+ /* Allocate a two-byte queue. */
+ bitq_setup(&it, 2);
+ /* Enqueue a byte value. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 0xab, 8), 8);
+ /* Dequeue the byte, but discard its value. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, NULL, 8), 8);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, NULL, 1), -1);
+ bitq_teardown(&it);
+}
+
+/* Test that bitq_init_full works. */
+static void test_init_full(struct kunit *test)
+{
+ struct bitq it;
+ u8 data[2] = { 0xaa, 0xbb };
+ u8 val = 0;
+
+ /* Initialize a queue with the contents of @data */
+ bitq_init_full(&it, data, 2);
+ /* Cannot enqueue anything else. */
+ KUNIT_EXPECT_EQ(test, bitq_enqueue(&it, 1, 8), -1);
+ /* Dequeue two bytes. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0xaa);
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, &val, 8), 8);
+ KUNIT_EXPECT_EQ(test, val, 0xbb);
+
+ /* Queue is empty. */
+ KUNIT_EXPECT_EQ(test, bitq_dequeue(&it, NULL, 1), -1);
+}
+
+static struct kunit_case bitq_test_cases[] = {
+ KUNIT_CASE(test_empty),
+ KUNIT_CASE(test_basic_enqueue_dequeue),
+ KUNIT_CASE(test_shorter_than_byte),
+ KUNIT_CASE(test_carryover),
+ KUNIT_CASE(test_carryover_ea0),
+ KUNIT_CASE(test_trim_upper_bits),
+ KUNIT_CASE(test_trim_upper_bits2),
+ KUNIT_CASE(test_dequeue_to_null),
+ KUNIT_CASE(test_init_full),
+ {}
+};
+
+static struct kunit_suite bitq_test_suite = {
+ .name = "bitq",
+ .test_cases = bitq_test_cases,
+};
+kunit_test_suites(&bitq_test_suite);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Alexander Potapenko <glider@google.com>");