From patchwork Tue Jul 11 14:33:31 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 118595 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp535903vqm; Tue, 11 Jul 2023 07:52:50 -0700 (PDT) X-Google-Smtp-Source: APBJJlH6+vRTee6UUIj3sZdN0b6YwIESHo2j7PitH+8By3X/jDvEDeCwjqqmWewgrEXkXRZW+DaD X-Received: by 2002:a92:d4c9:0:b0:346:67ab:f5d5 with SMTP id o9-20020a92d4c9000000b0034667abf5d5mr4150875ilm.27.1689087170537; Tue, 11 Jul 2023 07:52:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689087170; cv=none; d=google.com; s=arc-20160816; b=j6gi+tsjE6fXUa5I5pmToBtKCNB0Do3vgSQl5zbvciy/AY1aVQ17qfTud1Yq0Sy8lo 85ETkyAg9kwbsUZAiKYZ3gRxF47rZAGp8OkoqFi1R1cIo6XHKJeqRzl3OnRcPAfARpcR xsw+fX97q0pNx7ymGmbsvftyBgKkbNf26ftOn58EJlqHPJZxyC6ssYk/gs6wG2v4rp/s HKD/EOEMVZgV1G+/t/YAwO4xr833AFUET6P3jxdjr24I/7D37lORjlnKzzRA1PxSyFWA U4N/fFkKXsaIWTT4+trtA5EfWorAz/iYK6AoSO66Y+ifPJ9Vd14y5Dlc1J8hsHfgCPdq qLAw== 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=ZG8bZ4twWR1jt7HjafvL/lgzsyb7PZicKS8ufxQRQ/QbM5mwHeXOtTH9ov0A7wZxp/ jPpXeFKtoVqLTvZSunKNx2N4xGxpcU45IoWgCrKpwUYP6h78FU4Fddn/4EBZpnKS7rx5 Pfa45nUImj2PYMLNS4pa+UJS2twjEu1EUi7lPo1MKrNGfNMA/r9N55hIrkSWpzkoqlnH aA3dkFUjV3smQKtJAIqNqDRFjzZD0nweibEhNoLUvTkgr+SHEtGpiZYw5mly9NTW6ZKr Iap+OTs58cU9zANMDuSTxz7HkOhBp+cqXrbnoZ4xJHVZFJ2L8HqKDbb+76kuQN6IGk1f Owhw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=bF7ks1NO; 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 lw3-20020a17090b180300b0025ea380f868si9940872pjb.2.2023.07.11.07.52.37; Tue, 11 Jul 2023 07:52:50 -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=bF7ks1NO; 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 S233092AbjGKOeR (ORCPT + 99 others); Tue, 11 Jul 2023 10:34:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43088 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233242AbjGKOeG (ORCPT ); Tue, 11 Jul 2023 10:34:06 -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 261B71712 for ; Tue, 11 Jul 2023 07:33:59 -0700 (PDT) Received: by mail-ed1-x54a.google.com with SMTP id 4fb4d7f45d1cf-51dd16f823bso3914674a12.0 for ; Tue, 11 Jul 2023 07:33:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689086037; x=1691678037; 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=bF7ks1NOiP3BF1aqWMehZ/RymXHgICxwrRGh0fmfl8YsDQilu2nmGiaXt7lq7KHWZ/ e9N/L9vmQVA2AkmiBicDeuxKhtL0clapuMiVkJRboNpfFhF0gnkJtLlA5nH221cM06C8 w8ghPuSDsktDOO4BW/h6HGUuU2I56zCEwXmGcY8/d5lUyTen5sfwTBWKA0JKu2d1nbhU OhUNrvMLxhBq2k+psa7klp3nulrB2kSJtBx2vVJ6EgDgszJ4V5GX848W2L0X5CZxd1FI i2VCWpnJ7RjEds/XnyZFZeXfg0WKbqcobeZg8o+VHatLpaakqsxWcz13vMxE+PonafDG DLeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689086037; x=1691678037; 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=bdJnqriFXscCG5FGz7tFPLW8v0mLDhTA0AhFdLAzRMKImmjw9eyr7MPUAErDSUNTvs qo+Z+Fh09+mnGrLR0V8/Vp/3HRmHPFpCKIIEwicEyZZKmu/BproKceLGkSX73Xu2PlsQ 3veaEZ1OKibMnWbA7h4AupExkpFgfDi8s5mKKMr4UCeLRrVxqWzvLOcccB66L4tpAbaO eIFWR7RSTwlOBGIYyCLQGqSFDO5GqB6AIXZgFlQ2laTVSX6jR4g7Sfs9pJEhQhcjPt3r RtnrCwl8YLhbTwXNpIkfrQbBl+8JepnsJ1DII+/NsiVM81XdNCbZxNuxHR41E0BuVYjr CrEQ== X-Gm-Message-State: ABy/qLaxAqPFwtk+pS87RgWx6nunGnjfjAXuWlZzc2bAIcUz3ddkme52 NUbO+/LgYRVAzh/QOypEU1ztgt+4xHc= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:564d:3aaa:6b5f:4419]) (user=glider job=sendgmr) by 2002:a50:a6c9:0:b0:51e:2514:309d with SMTP id f9-20020a50a6c9000000b0051e2514309dmr75741edc.7.1689086037613; Tue, 11 Jul 2023 07:33:57 -0700 (PDT) Date: Tue, 11 Jul 2023 16:33:31 +0200 In-Reply-To: <20230711143337.3086664-1-glider@google.com> Mime-Version: 1.0 References: <20230711143337.3086664-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230711143337.3086664-5-glider@google.com> Subject: [PATCH 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: 1771136268811385643 X-GMAIL-MSGID: 1771136268811385643 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 ");