From patchwork Fri Aug 9 20:14:36 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Mattias_R=C3=B6nnblom?= X-Patchwork-Id: 143059 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 0931B4577D; Fri, 9 Aug 2024 22:24:57 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 13D1942EA0; Fri, 9 Aug 2024 22:24:25 +0200 (CEST) Received: from EUR02-VI1-obe.outbound.protection.outlook.com (mail-vi1eur02on2083.outbound.protection.outlook.com [40.107.241.83]) by mails.dpdk.org (Postfix) with ESMTP id 3E07242E58 for ; Fri, 9 Aug 2024 22:24:20 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=RMvbYCXvoScbuebAYNdgkHl0JfgjNUSYwdu8LGVpXA8CSlV0peJ3KWVGplRL07qyNvdW1HQ0D6EPAvAZ5CgIJlc98RFsuyw/TCH2LJe5d0lFb/C6sr64xPoiVbMh8XAYpKW8dEQ8RlKnOUI+5j9lGm5ZTTqo9g7Xb8Gmk5VAAQf8JBz7kqb3L66SO8KDQ3OZhbPEeV2egwhcJXGYJbsPvqjz/jkbD/iukJJYUlBRXQf0li08/sUe3bln39M7xzfUQCPAAmpVXHxUrWaxR58q3z28dHVMWISWeS/tqaVXi3k5LBKEMOixIxDVCdEfcdx6GNyqcU0LPgG3920EchWOIA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=VkCkMGh9ILWbh8tNxIgfZlaD6gLf18LkBqkNHp1LM4o=; b=HzHCjVSij1wzy2rRUnLH4/Bw8DsxMq/hQJwekroQLHRgmqU1O3UHnv6nRRt4BQGYDI5n7mEvX3LH9prEag3ls8oCnw++CxAyTz1ebWkCK3jlKrwRslR/GqK/4F5vcYUm77gMZrLXyXMyH9bwnKqIJSCTvkAUHnA04c8TW0/Nly7ZLM9mxVBPFvNrKUwjKrPDt7TgMzDyycL2H2nHm1Kw5l293gMblVGQM1XkEgqDb/ul7Z/WWRKsS8ZWXbzbinw2Pdgif7pKfcJOEMewnCB7AlgbaG/I2mY3ptKbn6+qAUkJGSg5MIoXR0SheBvFBSgh+GqvCbyj0Fmljb9NLddgeQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 192.176.1.74) smtp.rcpttodomain=dpdk.org smtp.mailfrom=ericsson.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=ericsson.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ericsson.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=VkCkMGh9ILWbh8tNxIgfZlaD6gLf18LkBqkNHp1LM4o=; b=ugTpK6zQKqNTYlLBhgl+mwBY69vd+uEBYgOLLtwsCjfwHMSLSuw9y6cIzcvnImE/QpJU1P8GdAtg1C5G4/tfhddnqvgZvyxkhOSnN4d8FAbGxUpiViJegnZwyNuW/djsJpbQR3dB6mpXsGVHWMIqFnLZ8qnsIzTeU6qrWjMKy3MzDePeF2Z1mB+yVOD5p3uOBX+HR729nia7tG2yt38dylZSq/A9aZ+PCIuV2f7UTV2q0zDDqykr/ugkWW4qhYisIUFJ231xHjeFKOZzJysQkuHsAwuSSVKKOnHYZc+R9r+B6gM5fDICcWWSI39at6pW67p2eWtcb14gZvOJxxnuAA== Received: from AM0PR02CA0073.eurprd02.prod.outlook.com (2603:10a6:208:154::14) by DBBPR07MB7435.eurprd07.prod.outlook.com (2603:10a6:10:1e2::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7849.14; Fri, 9 Aug 2024 20:24:17 +0000 Received: from AM3PEPF0000A794.eurprd04.prod.outlook.com (2603:10a6:208:154:cafe::4c) by AM0PR02CA0073.outlook.office365.com (2603:10a6:208:154::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7849.15 via Frontend Transport; Fri, 9 Aug 2024 20:24:17 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 192.176.1.74) smtp.mailfrom=ericsson.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=ericsson.com; Received-SPF: Pass (protection.outlook.com: domain of ericsson.com designates 192.176.1.74 as permitted sender) receiver=protection.outlook.com; client-ip=192.176.1.74; helo=oa.msg.ericsson.com; pr=C Received: from oa.msg.ericsson.com (192.176.1.74) by AM3PEPF0000A794.mail.protection.outlook.com (10.167.16.123) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7849.8 via Frontend Transport; Fri, 9 Aug 2024 20:24:16 +0000 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.66) with Microsoft SMTP Server id 15.2.1544.11; Fri, 9 Aug 2024 22:24:15 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id 8A7C01C006B; Fri, 9 Aug 2024 22:24:15 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , =?utf-8?q?Morten_Br=C3=B8rup?= , Tyler Retzlaff , Stephen Hemminger , Harry van Haaren , =?utf-8?q?Mattias_R=C3=B6nnb?= =?utf-8?q?lom?= Subject: [PATCH 2/6] eal: add bitset test suite Date: Fri, 9 Aug 2024 22:14:36 +0200 Message-ID: <20240809201440.590464-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240809201440.590464-1-mattias.ronnblom@ericsson.com> References: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> <20240809201440.590464-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM3PEPF0000A794:EE_|DBBPR07MB7435:EE_ X-MS-Office365-Filtering-Correlation-Id: 1dee5326-db49-4daa-fe3c-08dcb8b13dd5 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230040|36860700013|1800799024|376014|82310400026; X-Microsoft-Antispam-Message-Info: =?utf-8?q?tXYTrZr3xPkUOcbpaDCuFhjoElv31rk?= =?utf-8?q?4B5LYkVFK3C04MwnTMPXgmZWkg6pK9reKwKJJIKgqE1JYuCxb8ifZ3AL8/eACFH+P?= =?utf-8?q?MlkPikWrhNJGpDB24qYBANWMk4mura5iWXCjBSP8nUAo+UIl3rguwQJmpfZB+F8qC?= =?utf-8?q?ynN0AK8r6urmsE+B9AlJYaBWAW8uR0VMIMP1fETBwh6pfNTApFqPg5PF2BzZh5wNf?= =?utf-8?q?wIyaI3+3HBIYm08+GaJ2qdes3A4BC/gYznQVKPCK6EWMxtUbgxnBfiWpdhpjvJrln?= =?utf-8?q?DGG9o1o0z6lk7fdnVUX6G6hqXPy8KESX9F1ghaUptBfoTLgpQeQiZmohTAUVLXar0?= =?utf-8?q?tJaEuD9iqZFSjdt814Fi4HOIQLA3xr4MOAeAU2o3RwSv4C0EGtQJ/xPEB7Fg+/+F3?= =?utf-8?q?YdPbjz1mQiQ8GWcrim/bjQ8D86qjoYw6k1/irt8idmQxmLcrdd0Q+5boZnd6Y0hPl?= =?utf-8?q?ABMHp4s2/56bs5VuHOjlVFX0VRbY1bhqetvmtWTTa/o5tI92++MoEvy+UubKRWgBh?= =?utf-8?q?vDSjyNdnPXv7bQXWCz/cDcexhgIPIKkX4z2BfGC/p9YP6+9CuhhHvvHfiR9LjR3us?= =?utf-8?q?KrVYVHCKt7fMedR2gM6+6CF48V5YLtgjJmk0ne4T2YiDb4jal+W0NHOxe4NHXPZYQ?= =?utf-8?q?T3xyggZn8m90rR5tuGRk+OVVD8Jle89pPpqbjmEoulvVpQAifH1gfveTV5RgKgtme?= =?utf-8?q?CpMgWYX94m78NDgjopIkWQmBoaK6xlT+PgFLHs9injPR2P1lZzde5E7uifJzdhNKk?= =?utf-8?q?AaIZzidK7g39WOCddqnw4CwtSwucljqTaU4JDQXD9juP1ADqoYElPBpSNnnYqxcUj?= =?utf-8?q?oui4Iv9KoltLpfjK6p4sYjXLY7qAFiq7xPGnxGBF70g2nt8ZPf0qQRAivrdLs17Ow?= =?utf-8?q?wiQQBPPgruMqLdMEccnXUee8cGzxD9stXUkTUmv2NlMs3/VCFnAMP4ea1S3Dr8fKj?= =?utf-8?q?sJMY35IhdnP5d6p+GYxFzFjlStXka1e4Ai+zcNsHMhltkYvQNDy8Eh/nXi6YxsjmI?= =?utf-8?q?ZENGza/0YOSwlfV0yWrXZPSvZ992GK3NuMSQCYxJ5jRbISrx8lZ4A28kUuCgYU8PA?= =?utf-8?q?MND7AlRyxFPEYeOuHTvUsNHWHyS/epQRfW081IAn21dEk3dYBI318e03gxuRGWEM7?= =?utf-8?q?6ZZTQdWc6vWA+5M4YRLI9x+agXKqwl/hPbvdqmW0n//WOv7OgZ5+URBw2DFFmGTdf?= =?utf-8?q?DvSMjR+bbP6GoDJhDkhG4HSVbuwHxcqibDUVkJe9NBGpYw+OZqmM1MbuFQ4uVvkyc?= =?utf-8?q?wKTdSgXuCwiGS2AwDkBf9aVLtSbXL8Ix1k1x1HF1MZXY7/7qwyfcCG+YfEtBay9EY?= =?utf-8?q?BeFMgMWBh2FM5zE2BqIavuRGZpRrAmKFAA=3D=3D?= X-Forefront-Antispam-Report: CIP:192.176.1.74; CTRY:SE; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:oa.msg.ericsson.com; PTR:office365.se.ericsson.net; CAT:NONE; SFS:(13230040)(36860700013)(1800799024)(376014)(82310400026); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Aug 2024 20:24:16.5455 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 1dee5326-db49-4daa-fe3c-08dcb8b13dd5 X-MS-Exchange-CrossTenant-Id: 92e84ceb-fbfd-47ab-be52-080c6b87953f X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=92e84ceb-fbfd-47ab-be52-080c6b87953f; Ip=[192.176.1.74]; Helo=[oa.msg.ericsson.com] X-MS-Exchange-CrossTenant-AuthSource: AM3PEPF0000A794.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBBPR07MB7435 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Add test suite exercising . Signed-off-by: Mattias Rönnblom Acked-by: Tyler Retzlaff --- RFC v5: * Parameterize tests to allow reuse across both atomic and non-atomic functions. RFC v4: * Fix signed char issue in test cases. (Stephen Hemminger) * Add test cases for logic operations. * Use the unit test suite runner helper. --- app/test/meson.build | 1 + app/test/test_bitset.c | 894 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 895 insertions(+) create mode 100644 app/test/test_bitset.c diff --git a/app/test/meson.build b/app/test/meson.build index e29258e6ec..fe248b786c 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -33,6 +33,7 @@ source_file_deps = { 'test_bitcount.c': [], 'test_bitmap.c': [], 'test_bitops.c': [], + 'test_bitset.c': [], 'test_bitratestats.c': ['metrics', 'bitratestats', 'ethdev'] + sample_packet_forward_deps, 'test_bpf.c': ['bpf', 'net'], 'test_byteorder.c': [], diff --git a/app/test/test_bitset.c b/app/test/test_bitset.c new file mode 100644 index 0000000000..b3496df1c0 --- /dev/null +++ b/app/test/test_bitset.c @@ -0,0 +1,894 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Ericsson AB + */ + +#include +#include + +#include + +#include + +#include "test.h" + +#define MAGIC UINT64_C(0xdeadbeefdeadbeef) + +static void +rand_buf(void *buf, size_t n) +{ + size_t i; + + for (i = 0; i < n; i++) + ((unsigned char *)buf)[i] = rte_rand(); +} + +static uint64_t * +alloc_bitset(size_t size) +{ + uint64_t *p; + + p = malloc(RTE_BITSET_SIZE(size) + 2 * sizeof(uint64_t)); + + if (p == NULL) + rte_panic("Unable to allocate memory\n"); + + rand_buf(&p[0], RTE_BITSET_SIZE(size)); + + p[0] = MAGIC; + p[RTE_BITSET_NUM_WORDS(size) + 1] = MAGIC; + + return p + 1; +} + + +static int +free_bitset(uint64_t *bitset, size_t size) +{ + uint64_t *p; + + p = bitset - 1; + + if (p[0] != MAGIC) + return TEST_FAILED; + + if (p[RTE_BITSET_NUM_WORDS(size) + 1] != MAGIC) + return TEST_FAILED; + + free(p); + + return TEST_SUCCESS; +} + +static bool +rand_bool(void) +{ + return rte_rand_max(2); +} + +static void +rand_bool_ary(bool *ary, size_t len) +{ + size_t i; + + for (i = 0; i < len; i++) + ary[i] = rand_bool(); +} + +static void +rand_unused_bits(uint64_t *bitset, size_t size) +{ + uint64_t bits = rte_rand() & ~__RTE_BITSET_USED_MASK(size); + + bitset[RTE_BITSET_NUM_WORDS(size) - 1] |= bits; +} + +static void +rand_bitset(uint64_t *bitset, size_t size) +{ + size_t i; + + rte_bitset_init(bitset, size); + + for (i = 0; i < size; i++) + rte_bitset_assign(bitset, i, rand_bool()); + + rand_unused_bits(bitset, size); +} + +typedef bool test_fun(const uint64_t *bitset, size_t bit_num); +typedef void set_fun(uint64_t *bitset, size_t bit_num); +typedef void clear_fun(uint64_t *bitset, size_t bit_num); +typedef void assign_fun(uint64_t *bitset, size_t bit_num, bool value); +typedef void flip_fun(uint64_t *bitset, size_t bit_num); + +static int +test_set_clear_size(test_fun test_fun, set_fun set_fun, clear_fun clear_fun, + size_t size) +{ + size_t i; + bool reference[size]; + uint64_t *bitset; + + rand_bool_ary(reference, size); + + bitset = alloc_bitset(size); + + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); + + rte_bitset_init(bitset, size); + + for (i = 0; i < size; i++) { + if (reference[i]) + set_fun(bitset, i); + else + clear_fun(bitset, i); + } + + for (i = 0; i < size; i++) + if (reference[i] != test_fun(bitset, i)) + return TEST_FAILED; + + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, + "Buffer over- or underrun detected"); + + return TEST_SUCCESS; +} + +#define RAND_ITERATIONS (10000) +#define RAND_SET_MAX_SIZE (1000) + +static int +test_set_clear_fun(test_fun test_fun, set_fun set_fun, clear_fun clear_fun) +{ + size_t i; + + for (i = 0; i < RAND_ITERATIONS; i++) { + size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); + + if (test_set_clear_size(test_fun, set_fun, clear_fun, + size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +static int +test_set_clear(void) +{ + return test_set_clear_fun(rte_bitset_test, rte_bitset_set, + rte_bitset_clear); +} + +static int +test_flip_size(test_fun test_fun, assign_fun assign_fun, flip_fun flip_fun, + size_t size) +{ + size_t i; + uint64_t *bitset; + + bitset = alloc_bitset(size); + + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); + + rand_bitset(bitset, size); + + for (i = 0; i < size; i++) { + RTE_BITSET_DECLARE(reference, size); + + rte_bitset_copy(reference, bitset, size); + + bool value = test_fun(bitset, i); + + flip_fun(bitset, i); + + TEST_ASSERT(test_fun(bitset, i) != value, + "Bit %zd was not flipped", i); + + assign_fun(reference, i, !value); + + TEST_ASSERT(rte_bitset_equal(bitset, reference, size), + "Not only the target bit %zd was flipped", i); + + + } + + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, + "Buffer over- or underrun detected"); + + return TEST_SUCCESS; +} + +static int +test_flip_fun(test_fun test_fun, assign_fun assign_fun, flip_fun flip_fun) +{ + size_t i; + + for (i = 0; i < RAND_ITERATIONS; i++) { + size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); + + if (test_flip_size(test_fun, assign_fun, flip_fun, + size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +static int +test_flip(void) +{ + return test_flip_fun(rte_bitset_test, rte_bitset_assign, + rte_bitset_flip); +} + +static ssize_t +find(const bool *ary, size_t num_bools, size_t start, size_t len, bool set) +{ + size_t i; + + for (i = 0; i < len; i++) { + ssize_t idx = (start + i) % num_bools; + + if (ary[idx] == set) + return idx; + } + + return -1; +} + +static ssize_t +find_set(const bool *ary, size_t num_bools, size_t start, size_t len) +{ + return find(ary, num_bools, start, len, true); +} + +static ssize_t +find_clear(const bool *ary, size_t num_bools, size_t start, size_t len) +{ + return find(ary, num_bools, start, len, false); +} + +#define FFS_ITERATIONS (100) + +static int +test_find_size(size_t size, bool set) +{ + uint64_t *bitset; + bool reference[size]; + size_t i; + + bitset = alloc_bitset(size); + + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); + + rte_bitset_init(bitset, size); + + for (i = 0; i < size; i++) { + bool bit = rand_bool(); + reference[i] = bit; + + if (bit) + rte_bitset_set(bitset, i); + else /* redundant, still useful for testing */ + rte_bitset_clear(bitset, i); + } + + for (i = 0; i < FFS_ITERATIONS; i++) { + size_t start_bit = rte_rand_max(size); + size_t len = rte_rand_max(size + 1); + bool full_range = len == size && start_bit == 0; + bool wraps = start_bit + len > size; + ssize_t rc; + + if (set) { + if (full_range && rand_bool()) + rc = rte_bitset_find_first_set(bitset, + size); + else if (wraps || rand_bool()) { + rc = rte_bitset_find_set_wrap(bitset, size, + start_bit, len); + + } else + rc = rte_bitset_find_set(bitset, size, + start_bit, len); + + if (rc != find_set(reference, size, start_bit, + len)) + return TEST_FAILED; + } else { + if (full_range && rand_bool()) + rc = rte_bitset_find_first_clear(bitset, + size); + else if (wraps || rand_bool()) + rc = rte_bitset_find_clear_wrap(bitset, + size, + start_bit, len); + else + rc = rte_bitset_find_clear(bitset, size, + start_bit, len); + + if (rc != find_clear(reference, size, start_bit, + len)) + return TEST_FAILED; + } + + } + + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, + "Buffer over- or underrun detected"); + + return TEST_SUCCESS; +} + +static int +test_find_set_size(size_t size) +{ + return test_find_size(size, true); +} + +static int +test_find_clear_size(size_t size) +{ + return test_find_size(size, false); +} + +static int +test_find(void) +{ + size_t i; + + for (i = 0; i < RAND_ITERATIONS; i++) { + size_t size = 2 + rte_rand_max(RAND_SET_MAX_SIZE - 2); + + if (test_find_set_size(size) != TEST_SUCCESS) + return TEST_FAILED; + + if (test_find_clear_size(size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +static int +record_match(ssize_t match_idx, size_t size, int *calls) +{ + if (match_idx < 0 || (size_t)match_idx >= size) + return TEST_FAILED; + + calls[match_idx]++; + + return TEST_SUCCESS; +} + +static int +test_foreach_size(ssize_t size, bool may_wrap, bool set) +{ + bool reference[size]; + int calls[size]; + uint64_t *bitset; + ssize_t i; + ssize_t start_bit; + ssize_t len; + bool full_range; + size_t total_calls = 0; + + rand_bool_ary(reference, size); + + bitset = alloc_bitset(size); + + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); + + memset(calls, 0, sizeof(calls)); + + start_bit = rte_rand_max(size); + len = may_wrap ? rte_rand_max(size + 1) : + rte_rand_max(size - start_bit + 1); + + rte_bitset_init(bitset, size); + + /* random data in the unused bits should not matter */ + rand_buf(bitset, RTE_BITSET_SIZE(size)); + + for (i = start_bit; i < start_bit + len; i++) { + size_t idx = i % size; + + if (reference[idx]) + rte_bitset_set(bitset, idx); + else + rte_bitset_clear(bitset, idx); + + if (rte_bitset_test(bitset, idx) != reference[idx]) + return TEST_FAILED; + } + + full_range = (len == size && start_bit == 0); + + /* XXX: verify iteration order as well */ + if (set) { + if (full_range && rand_bool()) { + RTE_BITSET_FOREACH_SET(i, bitset, size) { + if (record_match(i, size, calls) != + TEST_SUCCESS) + return TEST_FAILED; + } + } else if (may_wrap) { + RTE_BITSET_FOREACH_SET_WRAP(i, bitset, size, + start_bit, len) { + if (record_match(i, size, calls) != + TEST_SUCCESS) { + printf("failed\n"); + return TEST_FAILED; + } + } + } else { + RTE_BITSET_FOREACH_SET_RANGE(i, bitset, size, + start_bit, len) { + if (record_match(i, size, calls) != + TEST_SUCCESS) + return TEST_FAILED; + } + } + } else { + if (full_range && rand_bool()) { + RTE_BITSET_FOREACH_CLEAR(i, bitset, size) + if (record_match(i, size, calls) != + TEST_SUCCESS) + return TEST_FAILED; + } else if (may_wrap) { + RTE_BITSET_FOREACH_CLEAR_WRAP(i, bitset, size, + start_bit, len) { + if (record_match(i, size, calls) != + TEST_SUCCESS) + return TEST_FAILED; + } + } else { + RTE_BITSET_FOREACH_CLEAR_RANGE(i, bitset, size, + start_bit, len) + if (record_match(i, size, calls) != + TEST_SUCCESS) + return TEST_FAILED; + } + } + + for (i = 0; i < len; i++) { + size_t idx = (start_bit + i) % size; + + if (reference[idx] == set && calls[idx] != 1) { + printf("bit %zd shouldn't have been found %d " + "times\n", idx, calls[idx]); + return TEST_FAILED; + } + + if (reference[idx] != set && calls[idx] != 0) { + puts("bar"); + return TEST_FAILED; + } + + total_calls += calls[idx]; + } + + if (full_range) { + size_t count; + + count = set ? rte_bitset_count_set(bitset, size) : + rte_bitset_count_clear(bitset, size); + + if (count != total_calls) + return TEST_FAILED; + } + + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, + "Buffer over- or underrun detected"); + + return TEST_SUCCESS; +} + +static int +test_foreach(void) +{ + size_t i; + + for (i = 0; i < RAND_ITERATIONS; i++) { + size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); + + if (test_foreach_size(size, false, true) != TEST_SUCCESS) + return TEST_FAILED; + + if (test_foreach_size(size, false, false) != TEST_SUCCESS) + return TEST_FAILED; + + if (test_foreach_size(size, true, true) != TEST_SUCCESS) + return TEST_FAILED; + + if (test_foreach_size(size, true, false) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +static int +test_count_size(size_t size) +{ + uint64_t *bitset; + + bitset = alloc_bitset(size); + + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); + + rte_bitset_init(bitset, size); + + rand_unused_bits(bitset, size); + + if (rte_bitset_count_set(bitset, size) != 0) + return TEST_FAILED; + + if (rte_bitset_count_clear(bitset, size) != size) + return TEST_FAILED; + + rte_bitset_set_all(bitset, size); + + if (rte_bitset_count_set(bitset, size) != size) + return TEST_FAILED; + + if (rte_bitset_count_clear(bitset, size) != 0) + return TEST_FAILED; + + rte_bitset_clear_all(bitset, size); + + if (rte_bitset_count_set(bitset, size) != 0) + return TEST_FAILED; + + if (rte_bitset_count_clear(bitset, size) != size) + return TEST_FAILED; + + rte_bitset_set(bitset, rte_rand_max(size)); + + if (rte_bitset_count_set(bitset, size) != 1) + return TEST_FAILED; + + if (rte_bitset_count_clear(bitset, size) != (size - 1)) + return TEST_FAILED; + + rte_bitset_clear_all(bitset, size); + if (rte_bitset_count_set(bitset, size) != 0) + return TEST_FAILED; + if (rte_bitset_count_clear(bitset, size) != size) + return TEST_FAILED; + + rte_bitset_set_all(bitset, size); + if (rte_bitset_count_set(bitset, size) != size) + return TEST_FAILED; + if (rte_bitset_count_clear(bitset, size) != 0) + return TEST_FAILED; + + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, + "Buffer over- or underrun detected"); + + return TEST_SUCCESS; +} + +static int +test_count(void) +{ + size_t i; + + if (test_count_size(128) != TEST_SUCCESS) + return TEST_FAILED; + if (test_count_size(1) != TEST_SUCCESS) + return TEST_FAILED; + if (test_count_size(63) != TEST_SUCCESS) + return TEST_FAILED; + if (test_count_size(64) != TEST_SUCCESS) + return TEST_FAILED; + if (test_count_size(65) != TEST_SUCCESS) + return TEST_FAILED; + + for (i = 0; i < RAND_ITERATIONS; i++) { + size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); + + if (test_count_size(size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +#define GEN_DECLARE(size) \ + { \ + RTE_BITSET_DECLARE(bitset, size); \ + size_t idx; \ + \ + idx = rte_rand_max(size); \ + rte_bitset_init(bitset, size); \ + \ + rte_bitset_set(bitset, idx); \ + if (!rte_bitset_test(bitset, idx)) \ + return TEST_FAILED; \ + if (rte_bitset_count_set(bitset, size) != 1) \ + return TEST_FAILED; \ + return TEST_SUCCESS; \ + } + +static int +test_define(void) +{ + GEN_DECLARE(1); + GEN_DECLARE(64); + GEN_DECLARE(65); + GEN_DECLARE(4097); +} + +static int test_logic_op(void (*bitset_op)(uint64_t *, const uint64_t *, + const uint64_t *, size_t), + bool (*bool_op)(bool, bool)) +{ + const size_t size = 1 + rte_rand_max(200); + RTE_BITSET_DECLARE(bitset_a, size); + RTE_BITSET_DECLARE(bitset_b, size); + RTE_BITSET_DECLARE(bitset_d, size); + + bool ary_a[size]; + bool ary_b[size]; + bool ary_d[size]; + + rand_bool_ary(ary_a, size); + rand_bool_ary(ary_b, size); + + size_t i; + for (i = 0; i < size; i++) { + rte_bitset_assign(bitset_a, i, ary_a[i]); + rte_bitset_assign(bitset_b, i, ary_b[i]); + ary_d[i] = bool_op(ary_a[i], ary_b[i]); + } + + bitset_op(bitset_d, bitset_a, bitset_b, size); + + for (i = 0; i < size; i++) + TEST_ASSERT_EQUAL(rte_bitset_test(bitset_d, i), + ary_d[i], "Unexpected value of bit %zd", i); + + return TEST_SUCCESS; +} + +static bool +bool_or(bool a, bool b) +{ + return a || b; +} + +static int +test_or(void) +{ + return test_logic_op(rte_bitset_or, bool_or); +} + +static bool +bool_and(bool a, bool b) +{ + return a && b; +} + +static int +test_and(void) +{ + return test_logic_op(rte_bitset_and, bool_and); +} + +static bool +bool_xor(bool a, bool b) +{ + return a != b; +} + +static int +test_xor(void) +{ + return test_logic_op(rte_bitset_xor, bool_xor); +} + +static int +test_complement(void) +{ + int i; + + for (i = 0; i < RAND_ITERATIONS; i++) { + const size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); + + RTE_BITSET_DECLARE(src, size); + + rand_bitset(src, size); + + bool bit_idx = rte_rand_max(size); + bool bit_value = rte_bitset_test(src, bit_idx); + + RTE_BITSET_DECLARE(dst, size); + + rte_bitset_complement(dst, src, size); + + TEST_ASSERT(bit_value != rte_bitset_test(dst, bit_idx), + "Bit %d was not flipped", bit_idx); + } + + return TEST_SUCCESS; +} + +static int +test_shift(bool right) +{ + int i; + + const char *direction = right ? "right" : "left"; + + for (i = 0; i < 10000; i++) { + const int size = 1 + (int)rte_rand_max(500); + const int shift_count = (int)rte_rand_max(1.5 * size); + int src_idx; + + RTE_BITSET_DECLARE(src, size); + RTE_BITSET_DECLARE(reference, size); + + rte_bitset_init(src, size); + rte_bitset_init(reference, size); + + rand_unused_bits(src, size); + rand_unused_bits(reference, size); + + for (src_idx = 0; src_idx < size; src_idx++) { + bool value = rand_bool(); + + rte_bitset_assign(src, src_idx, value); + + int dst_idx = right ? src_idx - shift_count : + src_idx + shift_count; + + if (dst_idx >= 0 && dst_idx < size) + rte_bitset_assign(reference, dst_idx, value); + } + + uint64_t *dst = alloc_bitset(size); + + if (right) + rte_bitset_shift_right(dst, src, size, shift_count); + else + rte_bitset_shift_left(dst, src, size, shift_count); + + TEST_ASSERT(rte_bitset_equal(dst, reference, size), + "Unexpected result from shifting bitset of size " + "%d bits %d bits %s", size, shift_count, direction); + + TEST_ASSERT_EQUAL(free_bitset(dst, size), TEST_SUCCESS, + "Shift %s operation overwrote buffer", + direction); + } + + return TEST_SUCCESS; +} + +static int +test_shift_right(void) +{ + return test_shift(true); +} + +static int +test_shift_left(void) +{ + return test_shift(false); +} + +static int +test_equal(void) +{ + const size_t size = 100; + RTE_BITSET_DECLARE(bitset_a, size); + RTE_BITSET_DECLARE(bitset_b, size); + + rand_buf(bitset_a, RTE_BITSET_SIZE(size)); + rand_buf(bitset_b, RTE_BITSET_SIZE(size)); + + rte_bitset_init(bitset_a, size); + rte_bitset_init(bitset_b, size); + + rte_bitset_set(bitset_a, 9); + rte_bitset_set(bitset_b, 9); + rte_bitset_set(bitset_a, 90); + rte_bitset_set(bitset_b, 90); + + if (!rte_bitset_equal(bitset_a, bitset_b, size)) + return TEST_FAILED; + + /* set unused bit, which should be ignored */ + rte_bitset_set(&bitset_a[1], 60); + + if (!rte_bitset_equal(bitset_a, bitset_b, size)) + return TEST_FAILED; + + return TEST_SUCCESS; +} + +static int +test_copy(void) +{ + const size_t size = 100; + RTE_BITSET_DECLARE(bitset_a, size); + RTE_BITSET_DECLARE(bitset_b, size); + + rand_buf(bitset_a, RTE_BITSET_SIZE(size)); + rand_buf(bitset_b, RTE_BITSET_SIZE(size)); + + rte_bitset_copy(bitset_a, bitset_b, size); + + if (!rte_bitset_equal(bitset_a, bitset_b, size)) + return TEST_FAILED; + + return TEST_SUCCESS; +} + +static int +test_to_str(void) +{ + char buf[1024]; + RTE_BITSET_DECLARE(bitset, 128); + + rte_bitset_init(bitset, 128); + rte_bitset_set(bitset, 1); + + if (rte_bitset_to_str(bitset, 2, buf, 3) != 3) + return TEST_FAILED; + if (strcmp(buf, "10") != 0) + return TEST_FAILED; + + rte_bitset_set(bitset, 0); + + if (rte_bitset_to_str(bitset, 1, buf, sizeof(buf)) != 2) + return TEST_FAILED; + if (strcmp(buf, "1") != 0) + return TEST_FAILED; + + rte_bitset_init(bitset, 99); + rte_bitset_set(bitset, 98); + + if (rte_bitset_to_str(bitset, 99, buf, sizeof(buf)) != 100) + return TEST_FAILED; + + if (buf[0] != '1' || strchr(&buf[1], '1') != NULL) + return TEST_FAILED; + + if (rte_bitset_to_str(bitset, 128, buf, 64) != -EINVAL) + return TEST_FAILED; + + return TEST_SUCCESS; +} + +static struct unit_test_suite bitset_tests = { + .suite_name = "bitset test suite", + .unit_test_cases = { + TEST_CASE_ST(NULL, NULL, test_set_clear), + TEST_CASE_ST(NULL, NULL, test_flip), + TEST_CASE_ST(NULL, NULL, test_find), + TEST_CASE_ST(NULL, NULL, test_foreach), + TEST_CASE_ST(NULL, NULL, test_count), + TEST_CASE_ST(NULL, NULL, test_define), + TEST_CASE_ST(NULL, NULL, test_or), + TEST_CASE_ST(NULL, NULL, test_and), + TEST_CASE_ST(NULL, NULL, test_xor), + TEST_CASE_ST(NULL, NULL, test_complement), + TEST_CASE_ST(NULL, NULL, test_shift_right), + TEST_CASE_ST(NULL, NULL, test_shift_left), + TEST_CASE_ST(NULL, NULL, test_equal), + TEST_CASE_ST(NULL, NULL, test_copy), + TEST_CASE_ST(NULL, NULL, test_to_str), + TEST_CASES_END() + } +}; + +static int +test_bitset(void) +{ + return unit_test_suite_runner(&bitset_tests); +} + +REGISTER_FAST_TEST(bitset_autotest, true, true, test_bitset);