From patchwork Tue Jul 11 14:42:30 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 118598 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp537570vqm; Tue, 11 Jul 2023 07:55:53 -0700 (PDT) X-Google-Smtp-Source: APBJJlEWWz0KmFOfJkwF6DabOFrfq4i4YyFDaYyzEOLrq7oGWNliL9VkMx8ozaDlwC2+7NbxoNlP X-Received: by 2002:a05:6a20:487:b0:128:f513:55ed with SMTP id 7-20020a056a20048700b00128f51355edmr11668729pzc.54.1689087353299; Tue, 11 Jul 2023 07:55:53 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689087353; cv=none; d=google.com; s=arc-20160816; b=wYl6g+QG+AUJ2k8flRhwLzIdkyFC0lg2LLWy4pzTS88N/z6CXkIrT8Pdhmpc2PxvT5 i1KdnSUP3BdMbpstJuPOWhFPjxlsCMgeDnYsSZ9ZN8b9DblHWrHTmBIE7JoFavzuIZCf qKyyHz239nui0+l2KKQTWR0kkqAvj37FY/Fl4/FvIxZUbD0XESDQXFoPs104L1WT1CI9 9AI7y5U6t5kR6XdqIg7K+xGHYlDSmaInEM3EZTkGXMndz4pp8exgFp1CwAIgcSeBLWxg VVvS6NbDUD424efyvKJeoNQGwmvkRpx9dL+sNNDapeaXrG7461piseYcDiU7PBeYQWMG XScg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=i17FLoNCi12ib3F8C35t83wNdppeBZG3dj7HY/hu0Qg=; fh=iAJec5y5uW60OtAwJ48IXZG7gbwwd7b6kg4lfH240Po=; b=gx2UvRReBxVSE3Qt3tNnChh+qev12SgJpWr2ISVhkRGeQhQouN/xOcS09ThoOgMHic 78VoMz60A9Nfctvl6O7TYKScVw8r1JTX/ZmSqJILdg/P8XLoia+Hr18C9NdBQYLcc2ha F1vDY7CJQCtyGAxn6CFqu55m08poocqJnacMQp4EY9aqN+wtY9cn9VFa2BkzM5KAVrwU Q9JQND+qXFPJsyzrR7bwUxXV0aMc5f5fwBjJuogBCpLLkce4gvBEbwzYYF6iTG9HArYT nErDmv3t+UUpLe+jWWR58wJPQ3//27Lp0A4zNfdKcv3zb8+uBINZpNC29aHDFNdmEGI0 tmeA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=JVxA60rx; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id a62-20020a639041000000b0055c3f915b0asi1573718pge.733.2023.07.11.07.55.38; Tue, 11 Jul 2023 07:55:53 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=JVxA60rx; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232138AbjGKOmx (ORCPT + 99 others); Tue, 11 Jul 2023 10:42:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51276 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231978AbjGKOmr (ORCPT ); Tue, 11 Jul 2023 10:42:47 -0400 Received: from mail-ed1-x54a.google.com (mail-ed1-x54a.google.com [IPv6:2a00:1450:4864:20::54a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0F7EAE60 for ; Tue, 11 Jul 2023 07:42:45 -0700 (PDT) Received: by mail-ed1-x54a.google.com with SMTP id 4fb4d7f45d1cf-51dd16f823bso3920404a12.0 for ; Tue, 11 Jul 2023 07:42:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689086563; x=1691678563; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=i17FLoNCi12ib3F8C35t83wNdppeBZG3dj7HY/hu0Qg=; b=JVxA60rxbQakJABYgGrtZoU/wRUB7v5l4kceDuaI7uXWajFkbhwwj93aPZdEJ1/hT5 MtH233z9IrqWyrX1H7MbpiDkLuLhWNBS1E3tERMBFGpRoahhe7Aa5q12gcs0ms/s3rCE Ep0Ri9uZeBFsw2dC++Wco60/2TnxU5djoKJy9VosD6b4EYFGaGJndhEVF1USkrrH9vwt /d0H9S/0equRVn66mlwE7bFdmzyK2jbM80X2+I0sdFWcUmNRVgTmL887gfDSLApbj0Do WBeorBaG6JIjhl3t4mnJ/Te8IilTOA3CXIhOICvmw+v6SzqsMaKAQltxqK7saUWNzQ1D ZvPQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689086563; x=1691678563; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=i17FLoNCi12ib3F8C35t83wNdppeBZG3dj7HY/hu0Qg=; b=NLEqpOkChzJ+Trf1JbqO9lsNvS6b8EB0QNYbraKEkxRxg4XqceghBAuqjkfsUHePCS Zae2g107HiMeMPve/W1ajKVt03bQs4rQ9V64Q1cVc3WqnbPBvyIkwk/ImmO0DMVnhpo0 w9ZswROiEGgzVOntCkaQjaMLxdiQ9MFVLIqq92L3lUJgWb1XPfDReFohrbHd9MK1D5lg INFU30uE2ii91VHoaf8Am+bpUbnzO1Rr8mcLLQUtmUSVaRQp5U2BLUMMxLRyqM2GCXzc f752K7jNIffDgusZ2jGVBPSt5K1VZmIoGCCyGvWjSW0nYeopfQcmd+qBykw/c7XEsp4F ONcA== X-Gm-Message-State: ABy/qLbO3TsVqr9exWdvGcdjZCgsESQpXyqCvrfWYa8fDm140d73dKtA sJv/N2Kp8bJVmZRFgYiFRk1jAbNwlqI= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:564d:3aaa:6b5f:4419]) (user=glider job=sendgmr) by 2002:a50:d681:0:b0:51a:60b6:f4e6 with SMTP id r1-20020a50d681000000b0051a60b6f4e6mr92152edi.5.1689086563460; Tue, 11 Jul 2023 07:42:43 -0700 (PDT) Date: Tue, 11 Jul 2023 16:42:30 +0200 In-Reply-To: <20230711144233.3129207-1-glider@google.com> Mime-Version: 1.0 References: <20230711144233.3129207-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230711144233.3129207-3-glider@google.com> Subject: [Resend v1 2/5] linux/bitqueue.h: add a KUnit test for bitqueue.h From: Alexander Potapenko To: glider@google.com, catalin.marinas@arm.com, will@kernel.org, pcc@google.com, andreyknvl@gmail.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com, yury.norov@gmail.com X-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771136460137814801 X-GMAIL-MSGID: 1771136460137814801 Add tests checking that struct bitq correctly handles sub-byte values. Signed-off-by: Alexander Potapenko --- lib/Kconfig.debug | 8 ++ lib/Makefile | 1 + lib/test_bitqueue.c | 244 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 253 insertions(+) create mode 100644 lib/test_bitqueue.c diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index ce51d4dc6803e..a6598b2c250d5 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -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 " if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + Enable this option to test the kernel's bit queue implementation + (). + config TEST_UDELAY tristate "udelay test driver" help diff --git a/lib/Makefile b/lib/Makefile index 876fcdeae34ec..7efb6aba31cf9 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -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 diff --git a/lib/test_bitqueue.c b/lib/test_bitqueue.c new file mode 100644 index 0000000000000..aec04b3a5f068 --- /dev/null +++ b/lib/test_bitqueue.c @@ -0,0 +1,244 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Test cases for struct bitq, a simple bit queue. + */ + +#include +#include +#include + +/* 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 ");