From patchwork Fri Feb 16 10:23:45 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: 136850 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 74F4A43B30; Fri, 16 Feb 2024 11:41:47 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 5A12543001; Fri, 16 Feb 2024 11:41:47 +0100 (CET) Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2059.outbound.protection.outlook.com [40.107.21.59]) by mails.dpdk.org (Postfix) with ESMTP id 40B8D4064A for ; Fri, 16 Feb 2024 11:41:46 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=jCBMHG+JyYRwyH+JudVs/MnoxW6/+Qamgsg9heJ9WLHTKqjlVwct54pBEE1uZlZg8OyEyo1017/+A5HeYqTkzlgea+2Pwi1C4QA5PpsMhKpbDQf4fp4ZWbXXSwCwwf4EFDz3KfC//sPkwwGohYEf9gwfSWYjbYIIDQAEvG1Kme2lRq4xxUY8R1MDaMnAnJsXwA3LPpNzGZ40drUBBzwUpRHzvrvLBlTW46P9UDcJ9EwDfjdRYV0RFjf00c6GJ5UsmWQRGjdwY/194cs5Bg7ef3jw0L6ryRPFI0LAGuQ5bheaXix7f36WDTQSCEPoG9/7j6jZRrn5Ne8Z8I00sUNrQQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=TutJfe/HOO3zDhYGKbGWx/NlCBc3uRoTXQOhXJG5nbs=; b=AVD5++mTPnarvYnko2KZZA64gytakxqbgFNQI7Xuyh1WssyibFiZSjP+TFzeX7bhyEvWvARQ+RsumEXsAHBamIqoQ1fZe659usjBEVlY71oRhpXjVXgMQ1KymFEtWJH29lF0ee0nfbwx32j0deFs3nRLPPBoO1EVfGeJo3f6dsQj3iH5Ndi8C4se6LDX67SHlQ6X5fJkYUoN8rAzwGa1stpTTJNJEig4w/QQOPnadM/k5XIFaHoyHrwgT6BrVxhEyAf3u3lHZTmJPGoT1PZw0zGKVtBAdxZK0hqai6bLeszjaWDYP20OJRSDv5ZinyHf4XYiD+AvG3rHUe2hQkKjrw== 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=TutJfe/HOO3zDhYGKbGWx/NlCBc3uRoTXQOhXJG5nbs=; b=v7tYcW0mhIfOeFkM1S2jQnR2qlY9NM+2/lbRhMbJ/ml7C+ooXsCu7CkdFQifqhEoSk75VOvdUbAM27bCfK4RixsF5eX4KKTrv5T+VMMVj+2/DDabgYF+kBi5mr7OdJncvDROuzPHGAXqkKgQLRbx+YVQDyjjxOLjpZcQkSpwyVgWOgcKTdq8OM3lbXSH0bePkZf+0nzKpUVxPQq1NU0W9klDTK0BdvYjrlgqAAl1miBpgLGMGzx6BH9etLHrsj5kpefPWxXG7bFCAvLzOyNX9X/q8fHf4GAV69sF8gKsrnUSoSKTHQgD3UoAG/FsqoBAeMkX2StegoUg2eN1aMl/dg== Received: from AS4PR09CA0030.eurprd09.prod.outlook.com (2603:10a6:20b:5d4::20) by PA4PR07MB7648.eurprd07.prod.outlook.com (2603:10a6:102:c5::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7292.31; Fri, 16 Feb 2024 10:41:43 +0000 Received: from AM4PEPF00027A61.eurprd04.prod.outlook.com (2603:10a6:20b:5d4:cafe::e2) by AS4PR09CA0030.outlook.office365.com (2603:10a6:20b:5d4::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7270.39 via Frontend Transport; Fri, 16 Feb 2024 10:41:43 +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 AM4PEPF00027A61.mail.protection.outlook.com (10.167.16.70) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7292.25 via Frontend Transport; Fri, 16 Feb 2024 10:41:43 +0000 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.64) with Microsoft SMTP Server id 15.2.1258.12; Fri, 16 Feb 2024 11:41:42 +0100 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id A15E51C007C; Fri, 16 Feb 2024 11:31:44 +0100 (CET) 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: [RFC v4 1/4] eal: add bitset type Date: Fri, 16 Feb 2024 11:23:45 +0100 Message-ID: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240131131301.418361-1-mattias.ronnblom@ericsson.com> References: <20240131131301.418361-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM4PEPF00027A61:EE_|PA4PR07MB7648:EE_ X-MS-Office365-Filtering-Correlation-Id: 6e8af048-0c55-4282-bdc0-08dc2edbde01 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 5WV6itClTCcKLsahzq7pT1KHtlUZcfm7d/hd6+OT6X2yCL40VC9bPgaL/i4kNd7d8sutU6R2mS8/2AZjYjUqTg/Vz+n/nVJst2a3tpQDs3W154nCPuuTJKoffx2mJA2tpBZqwd6++P6WGcb2GKfag/Nu7iQ48WhLfPLkuBPLb1IzqWyqVeg9i8ZjKzKhsZtvSN0xv3cuwiCpfrlMmReZQpzHN1wdmOC+XW8MAlbVU5hm0mTnrtZJOwej8JXSDVh5ep7gSpmXMuDhxw1cyEHQbxVTJ8epiIu9nE2zvxJRKdS0Nb5vLGS+Ysqq+BZRIEpCFQmGtVDiGOAm1ia8Am7oa73gNNrjuKFXiWey6+Ki1lJCLQqKWJzsi4JlAfVM2FnQpyeV928NxvFtJhcdW8RF6naVZRQSr1TIngurRIrSjS+yccyD7EJO0R9lTEQkZZhao7ski9hYXojIGWH9o+Eb/aZBmrMSI52sZApzwcmQcS3BRVgaYd95V7ZW7Vphh3Wwnh77c9ZKbY527a8ITPDsf0RQKTRD+f60rcFR2HaYXC8Qn7Q+HCK64mwlSdRgjbYc+fCgHvU2SqjPOo3PVJBBhkVxnr5xW98SuMykWvIuB/yekT2AU/f/R4bMhFQoLdW5hL5o2rHchQXNSse/Gk7S8kYLh4jNpC8mJVYxtxZCcEQ= 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:(13230031)(4636009)(396003)(376002)(346002)(39860400002)(136003)(230273577357003)(230922051799003)(451199024)(36860700004)(186009)(82310400011)(1800799012)(64100799003)(40470700004)(46966006)(30864003)(2906002)(5660300002)(6916009)(4326008)(7636003)(41300700001)(86362001)(82740400003)(82960400001)(107886003)(356005)(26005)(1076003)(2616005)(54906003)(70206006)(316002)(70586007)(8676002)(8936002)(83380400001)(36756003)(336012)(6266002)(66574015)(478600001); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Feb 2024 10:41:43.5889 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 6e8af048-0c55-4282-bdc0-08dc2edbde01 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: AM4PEPF00027A61.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: PA4PR07MB7648 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 Introduce a set of functions and macros that operate on sets of bits, kept in arrays of 64-bit words. RTE bitset is designed for bitsets which are larger than what fits in a single machine word (i.e., 64 bits). For very large bitsets, the API may be a more appropriate choice. RFC v4: * Add function rte_bitset_flip() to change the value of a bit. * Add function rte_bitset_complement(), flipping the value of all bits. * Add function rte_bitset_assign(), setting the value of a bit based on a 'bool' parameter. * Add functions to perform logical shift the bitset left or right. * Add explicit destination bitset to logic operation type functions (e.g., rte_bitset_and()), to increase flexibility. * Split implementation and test suite into distinct commits. RFC v3: * Split the bitset from the htimer patchset, where it was originally hosted. * Rebase to current DPDK main. * Add note that rte_bitset_init() need not be called if bitset words have already been zeroed. * Use REGISTER_FAST_TEST instead of REGISTER_TEST_COMMAND. * Use rte_popcount64() instead of compiler builtin. RFC v2: * Replaced with include, to properly get size_t typedef. * Add to get __rte_experimental in . Signed-off-by: Mattias Rönnblom --- lib/eal/common/meson.build | 1 + lib/eal/common/rte_bitset.c | 29 + lib/eal/include/meson.build | 1 + lib/eal/include/rte_bitset.h | 1080 ++++++++++++++++++++++++++++++++++ lib/eal/version.map | 3 + 5 files changed, 1114 insertions(+) create mode 100644 lib/eal/common/rte_bitset.c create mode 100644 lib/eal/include/rte_bitset.h diff --git a/lib/eal/common/meson.build b/lib/eal/common/meson.build index 22a626ba6f..c1bbf26654 100644 --- a/lib/eal/common/meson.build +++ b/lib/eal/common/meson.build @@ -31,6 +31,7 @@ sources += files( 'eal_common_uuid.c', 'malloc_elem.c', 'malloc_heap.c', + 'rte_bitset.c', 'rte_malloc.c', 'rte_random.c', 'rte_reciprocal.c', diff --git a/lib/eal/common/rte_bitset.c b/lib/eal/common/rte_bitset.c new file mode 100644 index 0000000000..35e55a64db --- /dev/null +++ b/lib/eal/common/rte_bitset.c @@ -0,0 +1,29 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Ericsson AB + */ + +#include + +#include "rte_bitset.h" + +ssize_t +rte_bitset_to_str(const uint64_t *bitset, size_t num_bits, char *buf, + size_t capacity) +{ + size_t i; + + if (capacity < (num_bits + 1)) + return -EINVAL; + + for (i = 0; i < num_bits; i++) { + bool value; + + value = rte_bitset_test(bitset, num_bits - 1 - i); + + buf[i] = value ? '1' : '0'; + } + + buf[num_bits] = '\0'; + + return num_bits + 1; +} diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build index e94b056d46..4b5f120a66 100644 --- a/lib/eal/include/meson.build +++ b/lib/eal/include/meson.build @@ -5,6 +5,7 @@ includes += include_directories('.') headers += files( 'rte_alarm.h', + 'rte_bitset.h', 'rte_bitmap.h', 'rte_bitops.h', 'rte_branch_prediction.h', diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h new file mode 100644 index 0000000000..35631a2a12 --- /dev/null +++ b/lib/eal/include/rte_bitset.h @@ -0,0 +1,1080 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Ericsson AB + */ + +#ifndef _RTE_BITSET_H_ +#define _RTE_BITSET_H_ + +/** + * @file + * RTE Bitset + * + * This file provides functions and macros for querying and + * manipulating sets of bits kept in arrays of @c uint64_t-sized + * elements. + * + * The bits in a bitset are numbered from 0 to @c size - 1, with the + * lowest index being the least significant bit. + * + * The bitset array must be properly aligned. + * + * For optimal performance, the @c size parameter, required by + * many of the API's functions, should be a compile-time constant. + * + * For large bitsets, the rte_bitmap.h API may be more appropriate. + * + * @warning + * All functions modifying a bitset may overwrite any unused bits of + * the last word. Such unused bits are ignored by all functions reading + * bits. + * + */ + +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * The size (in bytes) of each element in the array used to represent + * a bitset. + */ +#define RTE_BITSET_WORD_SIZE (sizeof(uint64_t)) + +/** + * The size (in bits) of each element in the array used to represent + * a bitset. + */ +#define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT) + +/** + * Computes the number of words required to store @c size bits. + */ +#define RTE_BITSET_NUM_WORDS(size) \ + ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS) + +/** + * Computes the amount of memory (in bytes) required to fit a bitset + * holding @c size bits. + */ +#define RTE_BITSET_SIZE(size) \ + ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE)) + +#define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS) +#define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS) +#define __RTE_BITSET_UNUSED(size) \ + ((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) \ + - (size)) +#define __RTE_BITSET_USED_MASK(size) \ + (UINT64_MAX >> __RTE_BITSET_UNUSED(size)) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Declare a bitset. + * + * Declare (e.g., as a struct field) or define (e.g., as a stack + * variable) a bitset of the specified size. + * + * @param size + * The number of bits the bitset must be able to represent. Must be + * a compile-time constant. + * @param name + * The field or variable name of the resulting definition. + */ +#define RTE_BITSET_DECLARE(name, size) \ + uint64_t name[RTE_BITSET_NUM_WORDS(size)] + +/* XXX: should one include flags here and use to avoid a comparison? */ +/* XXX: would this be better off as a function? */ + +#define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) \ + ((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) : \ + (size) - (start_bit) + (var))) + +#define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags) \ + for ((var) = __rte_bitset_find(bitset, size, start_bit, len, \ + flags); \ + (var) != -1; \ + (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, \ + len) > 0 ? \ + __rte_bitset_find(bitset, size, \ + ((var) + 1) % (size), \ + __RTE_BITSET_FOREACH_LEFT(var, \ + size, \ + start_bit, \ + len), \ + flags) : -1) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all bits set. + * + * This macro iterates over all bits set (i.e., all ones) in the + * bitset, in the forward direction (i.e., starting with the least + * significant '1'). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive + * iteration, this variable will hold the bit index of a set bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + */ + +#define RTE_BITSET_FOREACH_SET(var, bitset, size) \ + __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all bits cleared. + * + * This macro iterates over all bits cleared in the bitset, in the + * forward direction (i.e., starting with the lowest-indexed set bit). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive iteration, + * this variable will hold the bit index of a cleared bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + */ + +#define RTE_BITSET_FOREACH_CLEAR(var, bitset, size) \ + __RTE_BITSET_FOREACH(var, bitset, size, 0, size, \ + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all bits set within a range. + * + * This macro iterates over all bits set (i.e., all ones) in the + * specified range, in the forward direction (i.e., starting with the + * least significant '1'). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive iteration, + * this variable will hold the bit index of a set bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The length (in bits) of the range. @c start_bit + @c len must be less + * than or equal to @c size. + */ + +#define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all cleared bits within a range. + * + * This macro iterates over all bits cleared (i.e., all zeroes) in the + * specified range, in the forward direction (i.e., starting with the + * least significant '0'). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive iteration, + * this variable will hold the bit index of a set bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The length (in bits) of the range. @c start_bit + @c len must be less + * than or equal to @c size. + */ + +#define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) + +#define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ + __RTE_BITSET_FIND_FLAG_WRAP) + +#define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ + __RTE_BITSET_FIND_FLAG_WRAP | \ + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Initializes a bitset. + * + * All bits are cleared. + * + * In case all words in the bitset array are already set to zero by + * other means (e.g., at the time of memory allocation), this function + * need not be called. + * + * @param bitset + * A pointer to the array of bitset 64-bit words. + * @param size + * The size of the bitset (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_init(uint64_t *bitset, size_t size) +{ + memset(bitset, 0, RTE_BITSET_SIZE(size)); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Set a bit in the bitset. + * + * Bits are numbered from 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be set. + */ + +__rte_experimental +static inline void +rte_bitset_set(uint64_t *bitset, size_t bit_num) +{ + size_t word; + size_t offset; + uint64_t mask; + + word = __RTE_BITSET_WORD_IDX(bit_num); + offset = __RTE_BITSET_BIT_OFFSET(bit_num); + mask = UINT64_C(1) << offset; + + bitset[word] |= mask; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Clear a bit in the bitset. + * + * Bits are numbered 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be cleared. + */ + +__rte_experimental +static inline void +rte_bitset_clear(uint64_t *bitset, size_t bit_num) +{ + size_t word; + size_t offset; + uint64_t mask; + + word = __RTE_BITSET_WORD_IDX(bit_num); + offset = __RTE_BITSET_BIT_OFFSET(bit_num); + mask = ~(UINT64_C(1) << offset); + + bitset[word] &= mask; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Set or clear a bit in the bitset. + * + * Bits are numbered 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be set or cleared. + * @param bit_value + * Control if the bit should be set or cleared. + */ + +__rte_experimental +static inline void +rte_bitset_assign(uint64_t *bitset, size_t bit_num, bool bit_value) +{ + if (bit_value) + rte_bitset_set(bitset, bit_num); + else + rte_bitset_clear(bitset, bit_num); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Change the value of a bit in the bitset. + * + * Bits are numbered 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be flipped. + */ + +__rte_experimental +static inline void +rte_bitset_flip(uint64_t *bitset, size_t bit_num) +{ + size_t word; + size_t offset; + uint64_t mask; + + word = __RTE_BITSET_WORD_IDX(bit_num); + offset = __RTE_BITSET_BIT_OFFSET(bit_num); + mask = UINT64_C(1) << offset; + + bitset[word] ^= mask; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Set all bits in the bitset. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_set_all(uint64_t *bitset, size_t size) +{ + memset(bitset, 0xFF, RTE_BITSET_SIZE(size)); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Clear all bits in the bitset. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_clear_all(uint64_t *bitset, size_t size) +{ + rte_bitset_init(bitset, size); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Count all set bits (also known as the @e weight). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the number of '1' bits in the bitset. + */ + +__rte_experimental +static inline size_t +rte_bitset_count_set(const uint64_t *bitset, size_t size) +{ + size_t i; + size_t total = 0; + + /* + * Unused bits in a rte_bitset are always '0', and thus are + * not included in this count. + */ + for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) + total += rte_popcount64(bitset[i]); + + total += rte_popcount64(bitset[i] & __RTE_BITSET_USED_MASK(size)); + + return total; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Count all cleared bits. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the number of '0' bits in the bitset. + */ + +__rte_experimental +static inline size_t +rte_bitset_count_clear(const uint64_t *bitset, size_t size) +{ + return size - rte_bitset_count_set(bitset, size); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Test if a bit is set. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * Index of the bit to test. Index 0 is the least significant bit. + * @return + * Returns true if the bit is '1', and false if the bit is '0'. + */ + +__rte_experimental +static inline bool +rte_bitset_test(const uint64_t *bitset, size_t bit_num) +{ + size_t word; + size_t offset; + + word = __RTE_BITSET_WORD_IDX(bit_num); + offset = __RTE_BITSET_BIT_OFFSET(bit_num); + + return (bitset[word] >> offset) & 1; +} + +#define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0) +#define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1) + +__rte_experimental +static inline ssize_t +__rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size, + size_t start_bit, size_t len, bool find_clear) +{ + size_t word_idx; + size_t offset; + size_t end_bit = start_bit + len; + + RTE_ASSERT(end_bit <= size); + + if (unlikely(len == 0)) + return -1; + + word_idx = __RTE_BITSET_WORD_IDX(start_bit); + offset = __RTE_BITSET_BIT_OFFSET(start_bit); + + while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) { + uint64_t word; + int word_ffs; + + word = bitset[word_idx]; + if (find_clear) + word = ~word; + + word >>= offset; + + word_ffs = __builtin_ffsll(word); + + if (word_ffs != 0) { + ssize_t ffs = start_bit + word_ffs - 1; + + /* + * Check if set bit were among the last, + * unused bits, in the last word. + */ + if (unlikely(ffs >= (ssize_t)end_bit)) + return -1; + + return ffs; + } + + start_bit += (RTE_BITSET_WORD_BITS - offset); + word_idx++; + offset = 0; + } + + return -1; + +} + +__rte_experimental +static inline ssize_t +__rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit, + size_t len, unsigned int flags) +{ + bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR; + bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP; + bool does_wrap = (start_bit + len) > size; + ssize_t rc; + + RTE_ASSERT(len <= size); + if (!may_wrap) + RTE_ASSERT(!does_wrap); + + if (may_wrap && does_wrap) { + size_t len0 = size - start_bit; + size_t len1 = len - len0; + + rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0, + find_clear); + if (rc < 0) + rc = __rte_bitset_find_nowrap(bitset, size, + 0, len1, find_clear); + } else + rc = __rte_bitset_find_nowrap(bitset, size, start_bit, + len, find_clear); + + return rc; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first bit set. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), and returns the index of the first '1'. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the index of the least significant '1', or -1 if all + * bits are '0'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_first_set(const uint64_t *bitset, size_t size) +{ + return __rte_bitset_find(bitset, size, 0, size, 0); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first bit set at offset. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset, and returns the index of the first '1' encountered. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '1', or -1 if all + * bits are '0'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_set(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, 0); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first bit set at offset, with wrap-around. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset. If no '1' is encountered before the end of the bitset, the search + * will continue at index 0. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '1', or -1 if all + * bits are '0'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, + __RTE_BITSET_FIND_FLAG_WRAP); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first cleared bit. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), and returns the index of the first '0'. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the index of the least significant '0', or -1 if all + * bits are '1'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_first_clear(const uint64_t *bitset, size_t size) +{ + return __rte_bitset_find(bitset, size, 0, size, + __RTE_BITSET_FIND_FLAG_FIND_CLEAR); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first cleared bit at offset. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset, and returns the index of the first '0' encountered. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '0', or -1 if all + * bits are '1'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_clear(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, + __RTE_BITSET_FIND_FLAG_FIND_CLEAR); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first cleared bit at offset, with wrap-around. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset. If no '0' is encountered before the end of the bitset, the + * search will continue at index 0. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '0', or -1 if all + * bits are '1'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, + __RTE_BITSET_FIND_FLAG_FIND_CLEAR | + __RTE_BITSET_FIND_FLAG_WRAP); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Copy bitset. + * + * Copy the bits of the @c src_bitset to the @c dst_bitset. + * + * The bitsets may not overlap and must be of equal size. + * + * @param dst_bitset + * A pointer to the array of words making up the bitset. + * @param src_bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_copy(uint64_t *__rte_restrict dst_bitset, + const uint64_t *__rte_restrict src_bitset, + size_t size) +{ + rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size)); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitwise or two bitsets. + * + * Perform a bitwise OR operation on all bits in the two equal-size + * bitsets @c src_bitset0 and @c src_bitset1, and store the results in + * @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset0 + * A pointer to the first source bitset. + * @param src_bitset1 + * A pointer to the second source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset0, + const uint64_t *src_bitset1, size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = src_bitset0[i] | src_bitset1[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitwise and two bitsets. + * + * Perform a bitwise AND operation on all bits in the two equal-size + * bitsets @c src_bitset0 and @c src_bitset1, and store the result in + * @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset0 + * A pointer to the first source bitset. + * @param src_bitset1 + * A pointer to the second source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset0, + const uint64_t *src_bitset1, size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = src_bitset0[i] & src_bitset1[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitwise xor two bitsets. + * + * Perform a bitwise XOR operation on all bits in the two equal-size + * bitsets @c src_bitset0 and @c src_bitset1, and store the result in + * @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset0 + * A pointer to the first source bitset. + * @param src_bitset1 + * A pointer to the second source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_xor(uint64_t *dst_bitset, const uint64_t *src_bitset0, + const uint64_t *src_bitset1, size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = src_bitset0[i] ^ src_bitset1[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Compute the bitwise complement of a bitset. + * + * Flip every bit in the @c src_bitset, and store the result in @c + * dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_complement(uint64_t *dst_bitset, const uint64_t *src_bitset, + size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = ~src_bitset[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Shift bitset left. + * + * Perform a logical shift left of (multiply) @c src_bitset, and store + * the result in @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + * @param shift_bits + * The number of bits to shift the bitset. + */ + +__rte_experimental +static inline void +rte_bitset_shift_left(uint64_t *dst_bitset, const uint64_t *src_bitset, + size_t size, size_t shift_bits) +{ + const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; + const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; + unsigned int dst_idx; + + for (dst_idx = 0; dst_idx < RTE_BITSET_NUM_WORDS(size); dst_idx++) { + int src_high_idx = dst_idx - src_word_offset; + uint64_t low_bits = 0; + uint64_t high_bits = 0; + + if (src_high_idx >= 0) { + int src_low_idx = src_high_idx - 1; + + high_bits = src_bitset[src_high_idx] << src_bit_offset; + + if (src_bit_offset > 0 && src_low_idx >= 0) + low_bits = src_bitset[src_low_idx] >> + (RTE_BITSET_WORD_BITS - src_bit_offset); + } + dst_bitset[dst_idx] = low_bits | high_bits; + } +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Shift bitset right. + * + * Perform a logical shift right of (divide) @c src_bitset, and store + * the result in @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + * @param shift_bits + * The number of bits to shift the bitset. + */ + +__rte_experimental +static inline void +rte_bitset_shift_right(uint64_t *dst_bitset, const uint64_t *src_bitset, + size_t size, size_t shift_bits) +{ + const int num_words = RTE_BITSET_NUM_WORDS(size); + const uint64_t used_mask = __RTE_BITSET_USED_MASK(size); + const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; + const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; + int dst_idx; + + for (dst_idx = 0; dst_idx < num_words; dst_idx++) { + int src_low_idx = src_word_offset + dst_idx; + int src_high_idx = src_low_idx + 1; + uint64_t src_low_word_bits = 0; + uint64_t src_high_word_bits = 0; + + if (src_low_idx < num_words) { + src_low_word_bits = src_bitset[src_low_idx]; + + if (src_low_idx == (num_words - 1)) + src_low_word_bits &= used_mask; + + src_low_word_bits >>= src_bit_offset; + + if (src_bit_offset > 0 && src_high_idx < num_words) { + src_high_word_bits = src_bitset[src_high_idx]; + + if (src_high_idx == (num_words - 1)) + src_high_word_bits &= used_mask; + + src_high_word_bits <<= + (RTE_BITSET_WORD_BITS - src_bit_offset); + } + } + dst_bitset[dst_idx] = src_low_word_bits | src_high_word_bits; + } +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Compare two bitsets. + * + * Compare two bitsets for equality. + * + * @param bitset_a + * A pointer to the destination bitset. + * @param bitset_b + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline bool +rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b, + size_t size) +{ + size_t i; + uint64_t last_a, last_b; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) + if (bitset_a[i] != bitset_b[i]) + return false; + + last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size); + last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size); + + return last_a == last_b; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Converts a bitset to a string. + * + * This function prints a string representation of the bitstring to + * the supplied buffer. + * + * Each bit is represented either by '0' or '1' in the output, with + * the first (left-most) character in the output being the most + * significant bit. The resulting string is NUL terminated. + * + * @param bitset + * A pointer to the array of bitset 64-bit words. + * @param size + * The number of bits the bitset represent. + * @param buf + * A buffer to hold the output. + * @param capacity + * The size of the buffer. Must be @c size + 1 or larger. + * @return + * Returns the number of bytes written (i.e., @c size + 1), or -EINVAL + * in case the buffer capacity was too small. + */ + +__rte_experimental +ssize_t +rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf, + size_t capacity); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_BITSET_H_ */ diff --git a/lib/eal/version.map b/lib/eal/version.map index 5e0cd47c82..639ccfe4b0 100644 --- a/lib/eal/version.map +++ b/lib/eal/version.map @@ -393,6 +393,9 @@ EXPERIMENTAL { # added in 23.07 rte_memzone_max_get; rte_memzone_max_set; + + # added in 24.03 + rte_bitset_to_str; }; INTERNAL { From patchwork Sun May 5 07:33:09 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: 139863 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 A7BC243FAC; Sun, 5 May 2024 09:43:52 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id A3789402F2; Sun, 5 May 2024 09:43:40 +0200 (CEST) Received: from EUR02-DB5-obe.outbound.protection.outlook.com (mail-db5eur02on2071.outbound.protection.outlook.com [40.107.249.71]) by mails.dpdk.org (Postfix) with ESMTP id 1FCE24025D for ; Sun, 5 May 2024 09:43:37 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=CU6/l40190e0wzTcYqYZ6GMIHiClQfjOzuVk3Vzq8IEhjDbgezMy0sWZssyWAEJ4qNOTZqXLKERX99m8Q/zPDsR5sdnXjjBH/cHgLDDAeZ1Y892XQx1iDZ8Sl240oeB9dC4OofcdSwv0SXa6q+4M8WKO5JW8Azjk58LcGgVeJy5ZOkSCxwwKH3KsYmwDQxTF3TFwqVVdRagf7mY/0hrBJUZoV83K9snebPoLqDwbwYIFGH1lBW3Ous5GzWWMA6TaOyHc71xmmDXNHBW+k4joXUZU1YCdsq3zxxZC0h4D0vxMc81E63lkOQ9KckzSi9eRqdEbZb8XZ3AlflZr0On9Tw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=oaVwGNpBSY3m97DQec8v9JHEuk4A+Xw7OeMp/v5XVe0=; b=fBJH1ZPPvhMtRAUxsJMxHqnjOXttpM3TiWq/Cig6CUEJvamMhDNiEToHNE81LuMbuSYhpkmeYefz575rjq1UeRLFe7sDQRNGgP6XSxLMUwd1DozFVHfxQaYm4YUt97/nVE6QJUWSkKP2bUVHWw2CtJ7EtOw4JzTUc8QWbqCZtuNvC5UOWOK8GFBLmKSv8qRHG2HBpagKLkOg8aKaMCDBnNZDyu6I6ip4TEes4bItDKcRsQGLwIItaq4dnjtYdeNwOhXwFIt7ObB2gklGC6erIIu49PZR19uB0iE8mhuRpvcO0SnRa+HHsinNK7vFVPbIyp9QJiY3tLfKNmpFoHvIDA== 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=oaVwGNpBSY3m97DQec8v9JHEuk4A+Xw7OeMp/v5XVe0=; b=QtZGh/Xjwer3xevZnPQiTO/sAsGFcjzxFlxJkTuxHpNAFLgwcen+xTALbkWK1p6bXJmSur9PmS83w08DmCi3YK8VN1ecDloZV21/p8r0gEM7//Lfgw5cTq1H+APrCafUlG0Hqmbd3pWkja8d/DH3HaAjfThEQZHwRnoRhb/Cyue4z/DnHNKdjH6z3PW78zb+MNmsd3LcKl9dEEJfYoiBEVyp/D2J1B0fwP/2en0hiX7GAKuaFx9j6DKzZWkgOdf3pIAvEBjhLdt+O/6JUWAvOh1ctClPP/W6mg7CZogTlOq8s0O2qKM36j4IKvVGC2y1wi0hgzIGrQs6R9cfp8MAFw== Received: from AM5PR0101CA0011.eurprd01.prod.exchangelabs.com (2603:10a6:206:16::24) by PAXPR07MB8471.eurprd07.prod.outlook.com (2603:10a6:102:2b7::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39; Sun, 5 May 2024 07:43:35 +0000 Received: from AM3PEPF00009B9C.eurprd04.prod.outlook.com (2603:10a6:206:16:cafe::21) by AM5PR0101CA0011.outlook.office365.com (2603:10a6:206:16::24) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.40 via Frontend Transport; Sun, 5 May 2024 07:43:34 +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 AM3PEPF00009B9C.mail.protection.outlook.com (10.167.16.21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.18 via Frontend Transport; Sun, 5 May 2024 07:43:34 +0000 Received: from seliicinfr00049.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.9; Sun, 5 May 2024 09:43:32 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00049.seli.gic.ericsson.se (Postfix) with ESMTP id AD9DD38007A; Sun, 5 May 2024 09:43:32 +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: [RFC v5 2/6] eal: add bitset test suite Date: Sun, 5 May 2024 09:33:09 +0200 Message-ID: <20240505073313.118515-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> References: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> <20240505073313.118515-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM3PEPF00009B9C:EE_|PAXPR07MB8471:EE_ X-MS-Office365-Filtering-Correlation-Id: 44d3e3f4-2a48-4a41-d02f-08dc6cd711a7 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230031|1800799015|376005|36860700004|82310400017; X-Microsoft-Antispam-Message-Info: =?utf-8?q?yPRwWhsFqILFl3iJ8MPPgzuzhUKIw/t?= =?utf-8?q?OO49Pc2V7WX+KJdKAFb5c2NBM+tn5n72jFHQ6gkFAF18WQXXlNvXcxIcEXYk17Ntv?= =?utf-8?q?vTpugSP2lzpAOGKs4Ze2OXlpfG4oQnsBA32TxTXUikSX3fLuuKmGQsz9gEEIRFMln?= =?utf-8?q?0VPVVZY4Nq78hPrjhTDx8iwdJtPJrz1cC/5ZIX0RJm1IISqAJX5bDzM5h+5aEjwq+?= =?utf-8?q?pdvP6C6DnvwmKgBaiTywFBKyWkus+X1pyYb89kt0ZI0kDXZnLovT0Re53PJoD4QG+?= =?utf-8?q?YWEjfzQRheQJlg2cSeIPTUPBj5vkzYkWIJTVWgMu/TNBKM0BEvGjskSXFT89bPn2N?= =?utf-8?q?dUTKtRLFQhgdXLe36H4QCybgr2t+yIMS9yNnG7Z53PuTcPK8LncfdLLhaywyTe1g3?= =?utf-8?q?CTRJs/DPZmjClVjGXXsP0kwYYu8w1ZOjlHW4TfZHSBndAf2s0iz1doOkbaqDKVb6H?= =?utf-8?q?kGZYUixkJYx6MPc7niKEZNW78toahZTH0IIksg+FTavHH18ZjBAD58G7xVvZqtbG0?= =?utf-8?q?X2TIkFoUbNIY/d8/2OWgKauMTR5PFjG+BnkixGHkxmEFM3xrjT6ErtG/eQlFkbLNT?= =?utf-8?q?naVROf6wIh612t82hJNHpJxXaN7sV4P+mVJ8ozp39G4gi0oDukdQeNb6eNUJPtvVD?= =?utf-8?q?yvovAFCLxNWnfQbHqjVKFN7+MOKy6Vvnbyn/QeoqtSuQeeVNj+EI5mb7LrrcbpSOB?= =?utf-8?q?MNyPxal1E9+qw9quisVYfZvNZdd65t7Pw9pZjedm6T/oMnep8qXbmcT730/sK33Z2?= =?utf-8?q?XtzRapaGlvcdTDAw/U+BoOSDOR7aKbXc2Pw2S6PkoiqmmSO4LUYtE4KzbYv/Sf6Rq?= =?utf-8?q?h0iCO7ThscnYtsCdTwu3KUEkM3FPARDCgxaz8LfZ0fCCJ9EnIJ6EOgqdAhamKxTGy?= =?utf-8?q?XY4thZEPNIgSum9LCe95Lx5am2m94dmBH8c6Gu3jLZyR6OkmQ9QuU3IGR6MObTMgV?= =?utf-8?q?867F4GfPCGaumAXCfO+tbtxtJS0O7nX0jkTCdW7V+bIGH5k8QNf+SfPdsE1+FoV8p?= =?utf-8?q?MNqc95H6bCLyNQw16frOBPsodptgWaOtnkez93UNGjQylxBiEYuALn2KgfQtSoB/3?= =?utf-8?q?B55IeBEm+brsa3qs3rVWHSwk8ASzaePLsf7QBCbWY9nZVYw8teZbE6BGLYhJv06vp?= =?utf-8?q?pGoQtJXfzYxQe9jZLmcj6i01bj76X+OyNtLBCCazLiiQRLcuO14e8Us1pIUg7A0wU?= =?utf-8?q?GPzIqvoDPYWrc6gBk2AfOpYhd18fRQJzqjXV74cKkIF9SP986AAx1QmGecwFLvv4w?= =?utf-8?q?FIUThpXzCoVS0Ew4o5UxhUvYCUkTV7GZx/bXZo8uTXEDyxlbt8sDV/JWBZlCnKh3m?= =?utf-8?q?gz0uTZh8OBGs?= 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:(13230031)(1800799015)(376005)(36860700004)(82310400017); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2024 07:43:34.8653 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 44d3e3f4-2a48-4a41-d02f-08dc6cd711a7 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: AM3PEPF00009B9C.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: PAXPR07MB8471 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 to exercise . 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. Signed-off-by: Mattias Rönnblom --- 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 7d909039ae..633af5ce05 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); From patchwork Sun May 5 07:33:10 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: 139862 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 404C343FAC; Sun, 5 May 2024 09:43:43 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 9C84C402E1; Sun, 5 May 2024 09:43:38 +0200 (CEST) Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-ve1eur01on2081.outbound.protection.outlook.com [40.107.14.81]) by mails.dpdk.org (Postfix) with ESMTP id 415024025D for ; Sun, 5 May 2024 09:43:36 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=b+m/w39QFRggUL9MXYXUSi8ezR+NQ07SC6pXtdAoTFtgzQ2feKhdIR/gYmxjcJgjALo/Ds0IkKWSvvr9CLi3wqnI8Y80OywhA8PSFSqZ8WpneYeO7f30GSosswLxEJvwoRUxeArZca3DzCVkA23oW0r5g8fn/dchtugwjJRWj2WYZjwH5RyRlRwHFNl9Oggcjs1pOrOH8rSXkvwmqR9+i+qhL6B2k7AepukD8In1NI5XQzR6HMIp5o7zj5bwO9m1Ksi9vA5+5rEM+b4gcuOboAKP8nEQp1Cna32Ojz1YlEOncHiEkiumcFj1PsPOQmZaxBgyLdevUQHMu/TuknMZTw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=Q/piwczi3n4aqfjxagcziK2QUx6rtehUaviNWwb6gFI=; b=Nh56iDndiaY0mp+ftcihY7xXJZMBXUtm0ytrVooWdMWaxosc4ZwYlVcpy4xhoqTTB5UldZOYtay/VvZ7doNhE+GugEVm0ljb19AmtAc+QPHmcOIt6wHLDW7Q0WN0hdTXqVRvCm6UTmSbKNu9UC7bDXHVOkoGPJ/nrRoAjlWjfDBBsMZFuXEn1vVV+jWGe5L/ilPLjWgTYpPKGEFgrCSSJcIXwM7lcv+QeedsWypAXc8467AS0/0q64J3S9aJ4r/XrwVGBjIbUOpHbDsQD1GfbYXkolWOsbJv0swDMUSgj8elqQjqWy/n+9B6sd+PBQJ42YEzNpKsmkGLX4eL0R85xA== 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=Q/piwczi3n4aqfjxagcziK2QUx6rtehUaviNWwb6gFI=; b=fnMgUoJ3B3XWyKP208pdZVKYoIzKWVIrKtfFdcizysN9c2v5LOFntcge3tYLT2Ktwq/poW4Vq9pshXbwzvQAc43mEk6/rHvwh6nnlIGO4gPOor5ON/8D8B6c3t22V1UNV8l5GE1NrZJ6FWgAD4q1gFMzuU5uVndrjX2oHgtKDlVHh7l5kMeDcwFCiFBCKuxpdz7bKTyBeJanXYAu4xFDtZ0CgRhhbOAkJAme7IVYcrZ+KRyxhf09XRxGdQ259SK26nQ7LAn4rsUUKKsSavqK/+lM3Phsf+SIHUtJLfaT9x6qb9d/vWhjaHfbbMo7hlpNrixLY3Cra9kEUs0CHtsm8g== Received: from AM6PR04CA0001.eurprd04.prod.outlook.com (2603:10a6:20b:92::14) by PAWPR07MB9484.eurprd07.prod.outlook.com (2603:10a6:102:34f::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.28; Sun, 5 May 2024 07:43:34 +0000 Received: from AM2PEPF0001C717.eurprd05.prod.outlook.com (2603:10a6:20b:92:cafe::c0) by AM6PR04CA0001.outlook.office365.com (2603:10a6:20b:92::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.40 via Frontend Transport; Sun, 5 May 2024 07:43:34 +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 AM2PEPF0001C717.mail.protection.outlook.com (10.167.16.187) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.18 via Frontend Transport; Sun, 5 May 2024 07:43:33 +0000 Received: from seliicinfr00049.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.60) with Microsoft SMTP Server id 15.2.1544.9; Sun, 5 May 2024 09:43:33 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00049.seli.gic.ericsson.se (Postfix) with ESMTP id 53A1B38007A; Sun, 5 May 2024 09:43:33 +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: [RFC v5 3/6] eal: add atomic bitset functions Date: Sun, 5 May 2024 09:33:10 +0200 Message-ID: <20240505073313.118515-3-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> References: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> <20240505073313.118515-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM2PEPF0001C717:EE_|PAWPR07MB9484:EE_ X-MS-Office365-Filtering-Correlation-Id: 6353fccc-f6bd-4e76-e806-08dc6cd71115 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230031|376005|1800799015|82310400017|36860700004; X-Microsoft-Antispam-Message-Info: =?utf-8?q?7zL3tc5iYlklzYRgN+OLzrSmRQyK5Q3?= =?utf-8?q?UCtYAcuBH4KHw6mns/RcRtNXVTNc3NvwgfmiRYmsBY5po1pJbRuVnUGpnqhcgumDi?= =?utf-8?q?MCjm+m82L5kDeBPJ5zpvDY0varhgIPAZHTqbolCHchmuVnfNWj9gi8hRd1uc6EWhn?= =?utf-8?q?Xn1lRg0aD57ut+auoBzJGMwIno9xpngfASR6Hnx0b9juiD0AtJiwwaV7w+m7gpXxs?= =?utf-8?q?qyqUgWKlG6ojq2JyxZWh58882c3bWOPdfzUT4Vy86+pXzWYjEvJaSkbFpBGj6entC?= =?utf-8?q?4ixuPcVi3VHoZ7+Jr9IOkVT2hBAjw8YZ7KsdMNVib3E1EfzNcueIe+wwgGP4mnrzD?= =?utf-8?q?PyPW6Se2WBAtnvR7M7bv+qkvLQBf/8XH0f+NUzdKbTg3lC+2BFYoDp9uy0mg8hsg1?= =?utf-8?q?1xrq5O7eI2NrGNJrKjoz2Ju11tAh5pL7FKFmp/cBevvCETrBn/WPmmcrZqGdSh7Bx?= =?utf-8?q?qqz8ZZ3VDRv7UY8t68CAhCK99y0O3tNdN9qXds87uvRCcJcaCW6OBCk8N31RSWmwn?= =?utf-8?q?NINMfVZqhqBku8E/H1AUO9iA95GR6WKUjhMYXwzc371HXRnr+Y5Z3eOewWbj+V1OO?= =?utf-8?q?7QTgQQgqu/+udX0+4aJ55VIS092RE/pWdv/0/iZCdqwOHuMhGLq/Q0XTHirnXL+sx?= =?utf-8?q?bvstJ54A139okjrI98JOteiKRIsRDTF1AlxFO4+1o/OLh08oJr+y+LDI/ppw6E4FD?= =?utf-8?q?V6u8Y28KJqZiDIxUf905O035AMhpyb82NKIrLjsaTEjHE9YnTtEJmAZi3mk9APyG+?= =?utf-8?q?ZvipiFqsEZwoCGxRNy4J3BSyqExgnSrku31M5MW9sVRaf9UMlVfzt2ytISgVRIEuy?= =?utf-8?q?F2LLbF1DSXVuSFTXeG0dSXvCKjFyFrlRh5NnZ3I+8IYD5E1B/3SxXB9Yx2u62bR4H?= =?utf-8?q?DaSaLcYUgYcYyXdnF5SLO9l/EtMZL0oFCw1k01zF3FIGi119RlhDncgVzAmdA/71S?= =?utf-8?q?ct44H+J8YCaZilCDZyqpL/GAgUaiOdMXNb1BytZPZRhilEkdsKR/1dIvuc9+4Xrqs?= =?utf-8?q?05qvTnRkmG4qfyRLSK3KgzUO86FutSU7HvijaC+Jw88ra69dDdsus5Jt6ILwwxbGQ?= =?utf-8?q?9/1X8vIY4rlaAxpLoHCXfsYoDyGA0P7yt87sXJniZ1xoCo9myiUEuBYD3VvYN7bAS?= =?utf-8?q?lNM4lRP0Rp2RJ4K0we3dLzqjmFmPY3+Pz8CYt77c02YhjqTHtxtsxIyWZvZL0NBCn?= =?utf-8?q?Xu8u9DpY+dCC3ej4++BlCo5OkG4GqP7Vkz56LoKI470zV0ssT1Mrk6fGNI7nHWFZU?= =?utf-8?q?KXH633g3f+KiLqc9v7tFoz/6y7/NJeqJPIfEwz/cLHTjkyCVBO/yeT7A=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:(13230031)(376005)(1800799015)(82310400017)(36860700004); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2024 07:43:33.9403 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 6353fccc-f6bd-4e76-e806-08dc6cd71115 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: AM2PEPF0001C717.eurprd05.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: PAWPR07MB9484 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 Extend the bitset API with atomic versions of the most basic bitset operations. Signed-off-by: Mattias Rönnblom --- lib/eal/include/rte_bitset.h | 155 +++++++++++++++++++++++++++++++++++ 1 file changed, 155 insertions(+) diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h index 49a07c77b8..c0441b0e22 100644 --- a/lib/eal/include/rte_bitset.h +++ b/lib/eal/include/rte_bitset.h @@ -376,6 +376,161 @@ rte_bitset_flip(uint64_t *bitset, size_t bit_num) __RTE_BITSET_DELEGATE(rte_bit_flip, bitset, bit_num); } +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Atomically test if a bit is set. + * + * Atomically test if a bit in a bitset is set with the specified + * memory ordering. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * Index of the bit to test. Index 0 is the least significant bit. + * @param memory_order + * The memory order to use. + * @return + * Returns true if the bit is '1', and false if the bit is '0'. + */ + +__rte_experimental +static inline bool +rte_bitset_atomic_test(const uint64_t *bitset, size_t bit_num, + int memory_order) +{ + return __RTE_BITSET_DELEGATE_N(rte_bit_atomic_test, bitset, bit_num, + memory_order); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Atomically set a bit in the bitset. + * + * Set a bit in a bitset as an atomic operation, with the specified + * memory ordering. + * + * rte_bitset_atomic_set() is multi-thread safe, provided all threads + * acting in parallel on the same bitset does so through + * @c rte_bitset_atomic_*() functions. + * + * Bits are numbered from 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be set. + * @param memory_order + * The memory order to use. + */ + +__rte_experimental +static inline void +rte_bitset_atomic_set(uint64_t *bitset, size_t bit_num, int memory_order) +{ + __RTE_BITSET_DELEGATE_N(rte_bit_atomic_set, bitset, bit_num, + memory_order); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Atomically clear a bit in the bitset. + * + * Clear a bit in a bitset as an atomic operation, with the specified + * memory ordering. + * + * rte_bitset_atomic_clear() is multi-thread safe, provided all + * threads acting in parallel on the same bitset does so through @c + * rte_bitset_atomic_*() functions. + * + * Bits are numbered from 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be cleared. + * @param memory_order + * The memory order to use. + */ + +__rte_experimental +static inline void +rte_bitset_atomic_clear(uint64_t *bitset, size_t bit_num, int memory_order) +{ + __RTE_BITSET_DELEGATE_N(rte_bit_atomic_clear, bitset, bit_num, + memory_order); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Atomically set or clear a bit in the bitset. + * + * Assign a value to a bit in a bitset as an atomic operation, with + * the specified memory ordering. + * + * rte_bitset_atomic_assign() is multi-thread safe, provided all + * threads acting in parallel on the same bitset does so through + * @c rte_bitset_atomic_*() functions. + * + * Bits are numbered from 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be set or cleared. + * @param bit_value + * Control if the bit should be set or cleared. + * @param memory_order + * The memory order to use. + */ + +__rte_experimental +static inline void +rte_bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value, + int memory_order) +{ + __RTE_BITSET_DELEGATE_N(rte_bit_atomic_assign, bitset, bit_num, + bit_value, memory_order); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Atomically change the value of a bit in the bitset. + * + * Flip a bit in a bitset as an atomic operation, with the specified + * memory ordering. + * + * rte_bitset_atomic_flip() is multi-thread safe, provided all threads + * acting in parallel on the same bitset does so through + * @c rte_bitset_atomic_*() functions. + * + * Bits are numbered from 0 to (size - 1) (inclusive). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be flipped. + * @param memory_order + * The memory order to use. + */ + +__rte_experimental +static inline void +rte_bitset_atomic_flip(uint64_t *bitset, size_t bit_num, int memory_order) +{ + __RTE_BITSET_DELEGATE_N(rte_bit_atomic_flip, bitset, bit_num, + memory_order); +} + /** * @warning * @b EXPERIMENTAL: this API may change without prior notice. From patchwork Sun May 5 07:33:11 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: 139861 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 B65DB43FAC; Sun, 5 May 2024 09:43:37 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 34339402DC; Sun, 5 May 2024 09:43:37 +0200 (CEST) Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-db3eur04on2052.outbound.protection.outlook.com [40.107.6.52]) by mails.dpdk.org (Postfix) with ESMTP id D434D4025D for ; Sun, 5 May 2024 09:43:35 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ZHb82ZjgexmFXvOantSXizdIbSZ1vXAfGZeYbXTwuif+cWaabAm62/B+/FgOeieOMVwvyvbuI1ZNHp0gQWZqwEJjazcqpTmemeEkv/1WMCWg3FMSSdEd3akfUjYTBxgTpbfLAi9kmx5PzDpU8u8un1hXIzhAXCyAgjHtRein+EOGFDdY/vpPJKI25fsvVXqkCIFzIfjTMQJfnvFsoZvpZRaUUFAtYOSVds9ZREaDYh6ofdIVgA+h/AmpPKbni3ARN7diGtvc5yfII9qWbUbpwco3vkZO/vyb65CtML53nYVVz4cqQO5ysx6HKVa8NgdnmwAI28LxJgZM7ttBDN12dg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=pgqb9JEA77f9APhXHTEjz7+NixtL0Wc7nymsW0DjEkk=; b=GSdjQ8sdPblcrVgbhBF400LjatpgKcTnpNzxcyYe5rGCetx08iHYyY5kWVeXhSoFf86w6vyYTW+kHEd3dHOeICmMI2s7rATfAo1wBSfuhytktGT3aa8rfJsbM0w642+ppCeHhwFrIOVZqrj0Op/zmxju8vyqMengrOYO8N4GRak31dsjn59Q+/PB/E5Evy4n93YEWtbrLRqWaqUHhxhL88MX3E6IuNTpJvxlhKo+n2VYpnj+1Ic1wcHW+ieYfkYYf/o3odJSNmUpJce7fPBOmTh3Tk9gYD8wIu5wtdCWzxkj0h9+Wmjr86gIaQgk8SbF/RuekLGDwjYyJeri8gDUcg== 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=pgqb9JEA77f9APhXHTEjz7+NixtL0Wc7nymsW0DjEkk=; b=W6U9e6kDv5ThERgJz+Rc0qcD88ciu5N2rBC92Qe3BimSNgE0b2qgqofSx3nB/RjPtIBmFGYJigBvdlrMNmtcSjIywXeSg7pz8J5SqJmnqjyUCjDwCSRac5DeyDGac8Z0W63hUNbXb8thRKxb04JMgPtOzy++CfmdiZVlqO5UNAzrPsbyyqFgBxlQaDlVmhLyv+L2vLVFll3a1v0tHADv6oYVyLIDG5p71B0Z1l6NNMAwUbtepciLWjCrHaByIf1JCw2nhNwJamFAKnne2CT2rOWYC2KsRV/Umjvcdso3iHB8two+1GV3SGQl5hF1S02wEb+71LpY28IMas87jakm6Q== Received: from AM6PR04CA0029.eurprd04.prod.outlook.com (2603:10a6:20b:92::42) by AM9PR07MB7938.eurprd07.prod.outlook.com (2603:10a6:20b:2fc::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39; Sun, 5 May 2024 07:43:34 +0000 Received: from AM2PEPF0001C717.eurprd05.prod.outlook.com (2603:10a6:20b:92:cafe::a5) by AM6PR04CA0029.outlook.office365.com (2603:10a6:20b:92::42) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39 via Frontend Transport; Sun, 5 May 2024 07:43:34 +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 AM2PEPF0001C717.mail.protection.outlook.com (10.167.16.187) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.18 via Frontend Transport; Sun, 5 May 2024 07:43:34 +0000 Received: from seliicinfr00049.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.60) with Microsoft SMTP Server id 15.2.1544.9; Sun, 5 May 2024 09:43:34 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00049.seli.gic.ericsson.se (Postfix) with ESMTP id EE86738007A; Sun, 5 May 2024 09:43:33 +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: [RFC v5 4/6] eal: add unit tests for atomic bitset operations Date: Sun, 5 May 2024 09:33:11 +0200 Message-ID: <20240505073313.118515-4-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> References: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> <20240505073313.118515-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM2PEPF0001C717:EE_|AM9PR07MB7938:EE_ X-MS-Office365-Filtering-Correlation-Id: 42a7bea7-e7af-4ad2-a86b-08dc6cd71177 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230031|82310400017|36860700004|1800799015|376005; X-Microsoft-Antispam-Message-Info: =?utf-8?q?8sQE57oJqaK7xvO7kxrbqoEnhXic4My?= =?utf-8?q?q3CTQgntxvOdFTIHeCdoqmb1SmKFv5Kz9UCjKTddQ/i4N9Z06ekJ0UmB8E/PCdnQh?= =?utf-8?q?jY2GoW3mrzSHsAlXU3M3o0/UDH8TbIS8qIYNkwXZmIWBJaxitk1lo0RxZGLTby6FO?= =?utf-8?q?Dam1DcM8OumlUcqY17Meh9KGswEWbGvFdOIQ2aMzLqP91Px/3gpoM82kSaZCCx4Xd?= =?utf-8?q?NkdgVAoYMInPWaNUg6WgocldKTCmIdzVany+iwZijmrjg8TraM9ogfP9tGmjMtKnQ?= =?utf-8?q?HvrrBYh5CbIkAxM+//HBuIUtwS5j8lpDNchjvvIHiu0oZGxSwiKpGjYQ3P5QL74/0?= =?utf-8?q?IJZ8sM5hka/4x12VzKxwt7jA5zpGcpg0vGVyBCKeRSCsTl0Uz7H3mkFpSz4ob1Cxk?= =?utf-8?q?zlstA6PxGoxtURRD/H66gw17q+W3yHNumx/81PWW7bylD/l1vId2JIfR4EAHj0YHk?= =?utf-8?q?zcaAACmvs8XeQ+IIFHt9wF+1iaHygF3q3AaN1Z/B5IRcakLNrjyl4VTuokj2nqaW8?= =?utf-8?q?1miqSINHcib6qY/FQL+/m/DeJDdgj6LXZuGe43KzOe1XjGyxsALjdUL41cczivUTG?= =?utf-8?q?1Lv52UYF0ztCVD/MYJ5zJ60sbWEd5VS92l7fw1EK5JNJqZA2EOfq5Bo16eMaU/f3j?= =?utf-8?q?r2B3CyWKMj5aTC7IVojX/FdSYerNlSbH8VSRMENR/dNG8ptjGP2N2idp8KYM/FVSh?= =?utf-8?q?USfEy5fbrlkg+t8+RXEkTtqKlJ5QeKfYwegpHyYNMuXATCfnrKQrqwGEpM8n9+Zk3?= =?utf-8?q?50c8p2UGKYQRnGpV07w/ZMfspnzSSuVNsRIPdRoj+qhfg6CQ+MTCT2eAH4go/tVwV?= =?utf-8?q?mskBD2Mc5wJLXmNS85ImjcAQVTmNLgCyTvcTSILE2q9+dpeIT++3EV9uzdjgcd0tl?= =?utf-8?q?Wo9FFx3cFbCgYt2I/VpGytGGLFIlFdKQiuhygsaOdGwC/CYOGpXn/47VkO0k4PylZ?= =?utf-8?q?drUfYvqlzygYYxpkOuhggRhks36dQbKzYi7acR9D6M5WK3tgGQR3rZ0Q95Ne3V3Fn?= =?utf-8?q?V1zV0eL/QJuO/8i3UT+1UosJ+mKWy5y3TdkpLpwwgE0E3B/76vyesstTBX6kAavfM?= =?utf-8?q?TcagPBw8Ej5fzF4e/oZ493hfVByAr8//sFj0hT2fa6ykSjcsKUseTmE5ESFCAIZWO?= =?utf-8?q?X2pQAs80Y6Ue6cmNcJfmTryXhygiNGIZgzNs5g5CGy7vJrG5SaJ7nGU6VAFcUAbAI?= =?utf-8?q?JS64C72UnEvgFE6msn5Oi1W8p8+vL9+HDHBxV8LsQXQ4tOkiSGcCPlCmIi1Y7k1yz?= =?utf-8?q?RVnztIfidbhtgNk+YkopCVSiXsLDgWPbDFTD+fAPSTp4q4dB8Xv7UsVc=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:(13230031)(82310400017)(36860700004)(1800799015)(376005); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2024 07:43:34.5653 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 42a7bea7-e7af-4ad2-a86b-08dc6cd71177 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: AM2PEPF0001C717.eurprd05.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM9PR07MB7938 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 Extend bitset tests to cover the basic operation of the rte_bitset_atomic_*() family of functions. Signed-off-by: Mattias Rönnblom --- app/test/test_bitset.c | 48 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) diff --git a/app/test/test_bitset.c b/app/test/test_bitset.c index b3496df1c0..32224a1eee 100644 --- a/app/test/test_bitset.c +++ b/app/test/test_bitset.c @@ -222,6 +222,52 @@ test_flip(void) rte_bitset_flip); } +static bool +bitset_atomic_test(const uint64_t *bitset, size_t bit_num) +{ + return rte_bitset_atomic_test(bitset, bit_num, + rte_memory_order_relaxed); +} + +static void +bitset_atomic_set(uint64_t *bitset, size_t bit_num) +{ + rte_bitset_atomic_set(bitset, bit_num, rte_memory_order_relaxed); +} + +static void +bitset_atomic_clear(uint64_t *bitset, size_t bit_num) +{ + rte_bitset_atomic_clear(bitset, bit_num, rte_memory_order_relaxed); +} + +static void +bitset_atomic_flip(uint64_t *bitset, size_t bit_num) +{ + rte_bitset_atomic_flip(bitset, bit_num, rte_memory_order_relaxed); +} + +static void +bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value) +{ + rte_bitset_atomic_assign(bitset, bit_num, bit_value, + rte_memory_order_relaxed); +} + +static int +test_atomic_set_clear(void) +{ + return test_set_clear_fun(bitset_atomic_test, bitset_atomic_set, + bitset_atomic_clear); +} + +static int +test_atomic_flip(void) +{ + return test_flip_fun(bitset_atomic_test, bitset_atomic_assign, + bitset_atomic_flip); +} + static ssize_t find(const bool *ary, size_t num_bools, size_t start, size_t len, bool set) { @@ -868,6 +914,8 @@ static struct unit_test_suite bitset_tests = { .unit_test_cases = { TEST_CASE_ST(NULL, NULL, test_set_clear), TEST_CASE_ST(NULL, NULL, test_flip), + TEST_CASE_ST(NULL, NULL, test_atomic_set_clear), + TEST_CASE_ST(NULL, NULL, test_atomic_flip), TEST_CASE_ST(NULL, NULL, test_find), TEST_CASE_ST(NULL, NULL, test_foreach), TEST_CASE_ST(NULL, NULL, test_count),