From patchwork Wed Jan 31 13:13:01 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: 136234 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 7542E43A1E; Wed, 31 Jan 2024 14:21:13 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 5982F402D0; Wed, 31 Jan 2024 14:21:13 +0100 (CET) Received: from EUR03-AM7-obe.outbound.protection.outlook.com (mail-am7eur03on2087.outbound.protection.outlook.com [40.107.105.87]) by mails.dpdk.org (Postfix) with ESMTP id 21388402A1 for ; Wed, 31 Jan 2024 14:21:11 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=UFDVX1fhMj2b6vcSFAVh3/97cRzTtyvI2DXYfnKYODjL2ssSve4JqjSWwEtEtc2vO0PW+JxEHwQU59EsEMlNlSm2p56IgGpmMPoEMYPvNXT8xAjQ58DaZzEJYkQYjF0zhPgdbocRj7R2EmXcTVhRj/rH+exteTntCtmzuIkccCqa2LdDk2YeaUyLgzjMAUmqMCOO/JoCNTX04dAJCOWXSgDLdTGLNSgG/ji7RzDSy6cmWLQK/eR3BfEnxx+ZPXqcCuajH4WwOWIZzpdMsgpxCieEQ4m1h+u6HP9ltrvUQn/h7jVW3gfHEyrnE9RYsER2sh/NlYMjLRaQkvKebvkCIg== 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=/+SS1YcQ4iThvA9ZYijAXCAxQiyikTcxKzfkAQ0ryjw=; b=Ff2FDmtgJMJglGOHQBNts0i78k3tvJkjsVw6pkm3Jt88SAO0qZ7ub5yEdX5zD+xLOZS5Ir1CeDunZc23qBJ6CfWp/dnfeo1uNlcG0NyZ1VRjm/MEE/NSnvQSOFTWImpKyrI4VIjJaEhsyFUGJbemgnpqERbuW4B5ms45TxpUmtgJcHjX6MRyxdjgsqnyDEgOcyuQp5K8X5hMlmaLlnbK+qb/dSOiJT5xgh8wWArtjOFH/4r0rdArcRATbdQYIO7xLLdUnsHJjwFvH8L1H3lPhT6+uXi7V0+9M9zmSTqn14XAHYxCJZujqmEZ6z9XglsbVTBN5QY9rRlBeMeDcw8ouA== 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=/+SS1YcQ4iThvA9ZYijAXCAxQiyikTcxKzfkAQ0ryjw=; b=VwXnBc9eYLrylrVkDT9IOcQDmU1Ezqq3uI8UaHKOuQcxa9/vxfSe0ctUdW2jUJKlHIEYTriocek9kVWqQZZJ0Vat7skqHOIC4GVhKjp8lqQ99Z8eSWnJc9g0FsnZvj8m1y2V3OBg0cmjugHPw8TZ2M7DtQ5Nwcxhqtd7at2856+8La8ge82Rj3pA3fy6dJjlvedQldDBPOZ+JEEnnUrBZdXHrAsCG/3znHSfSRq+W6KARomNW/luFKtUtW4INI0W+EsesgLhKBEA6gwv4vWO802DuWcxWgujnNkZPMKqSPn/9YIYd4QTK/RkRUIm8v6CMlMH1UEJ0G+klgC0loyURw== Received: from DB9PR06CA0002.eurprd06.prod.outlook.com (2603:10a6:10:1db::7) by AM7PR07MB6964.eurprd07.prod.outlook.com (2603:10a6:20b:1be::5) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7228.34; Wed, 31 Jan 2024 13:21:07 +0000 Received: from DB3PEPF0000885F.eurprd02.prod.outlook.com (2603:10a6:10:1db:cafe::7f) by DB9PR06CA0002.outlook.office365.com (2603:10a6:10:1db::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7249.23 via Frontend Transport; Wed, 31 Jan 2024 13:21:07 +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 DB3PEPF0000885F.mail.protection.outlook.com (10.167.242.10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7249.19 via Frontend Transport; Wed, 31 Jan 2024 13:21:07 +0000 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.61) with Microsoft SMTP Server id 15.2.1258.12; Wed, 31 Jan 2024 14:21:06 +0100 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id 1F9A21C006A; Wed, 31 Jan 2024 14:21:06 +0100 (CET) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , =?utf-8?q?Morten_Br=C3=B8rup?= , Tyler Retzlaff , =?utf-8?q?Mattias_R=C3=B6nnb?= =?utf-8?q?lom?= Subject: [RFC v3] eal: add bitset type Date: Wed, 31 Jan 2024 14:13:01 +0100 Message-ID: <20240131131301.418361-1-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: DB3PEPF0000885F:EE_|AM7PR07MB6964:EE_ X-MS-Office365-Filtering-Correlation-Id: 11ac6891-da73-411e-29da-08dc225f7bba X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: S4DtcKntX3f/jApusEcu7vVYIzojlpCWKRLnNDVyMVCET+7CYKVgb/jwIcjZMX45TrRMQ4Yo5teUsHhmPZVtzpzInpvtwvWo/LPmE9rEjNisp1fMAWiDOcVLLr2TAu5U56++GypkV4xHc2OVJfJFoV3TIrgKLaNoIvBW6sLVoMAALEoGFEuS02eijyat0fewNU+1LnfsrjdgSCTIlvtRXOGfQNbNPcmCAiLMscNXZbLf5GoJX7Gw1xB0M/oKZFWLeFA39DFN0mzaX6TtLjL74J3nCpq/r/4Urjjn0IGFGJwpwmOL6WhDG/xSrMVRxhy7w4BEKdzpwQlTQhoRUt6CEr/RpyFJlIVYMZlxSwVWj95ruS1r3E7wLP7EsUyPuOe1yJ05wQ+kCAML0x5ln40J/iJvaxpxFXihs7cEdzaHk4Jz8R1RV+VW045x+SPfwzw+HT1oKMn85BzDck+amnX+bSHjEIRDHmXwJjWMoeqsIdi6O/EYQtj0FH0I3kc7E1NBizOK05Edk+JMVTCjT68OGIIqLN8RMJ3/6OwFYyAZcNxdfbHizWdIbGMiqZhj7sES7BNU/GSPtBjRGgDvyJrLQFZnvOnlWzfeqZ0chYTSMIFI4pMd6T/7wOv/zUL54goFLbKc8Lbo5+c8vueSuYdS2evLzxTrdt2XG2pSBwAxfdiYPY2o2ABgoX87Qpaa9BK9QJ4okz3olMW7EEiTy/DtWHNu/lZjrMFVPY5mzGgIl4CixTJr2qYRkTlBfVZZjuPj1PSquX5B2rIeBqJLJq9zlZ1ls/iDpE4rRR2W7sQ3R038I+WgwqJLNTTRVwf2sJV/ 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)(346002)(136003)(39860400002)(376002)(230173577357003)(230273577357003)(230922051799003)(64100799003)(82310400011)(186009)(451199024)(1800799012)(36840700001)(40470700004)(46966006)(40480700001)(40460700003)(41300700001)(83380400001)(86362001)(82960400001)(36756003)(82740400003)(7636003)(356005)(36860700001)(66574015)(47076005)(2616005)(107886003)(1076003)(6266002)(336012)(26005)(2906002)(30864003)(478600001)(70206006)(6916009)(70586007)(316002)(54906003)(8676002)(4326008)(8936002)(5660300002)(6666004)(21314003)(579004); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 31 Jan 2024 13:21:07.2022 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 11ac6891-da73-411e-29da-08dc225f7bba 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: DB3PEPF0000885F.eurprd02.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM7PR07MB6964 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 elements. 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 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 --- app/test/meson.build | 1 + app/test/test_bitset.c | 645 +++++++++++++++++++++++++ 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 | 884 +++++++++++++++++++++++++++++++++++ lib/eal/version.map | 3 + 7 files changed, 1564 insertions(+) create mode 100644 app/test/test_bitset.c create mode 100644 lib/eal/common/rte_bitset.c create mode 100644 lib/eal/include/rte_bitset.h diff --git a/app/test/meson.build b/app/test/meson.build index dcc93f4a43..e218be11d8 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -32,6 +32,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..688349b03b --- /dev/null +++ b/app/test/test_bitset.c @@ -0,0 +1,645 @@ +/* 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++) + ((char *)buf)[i] = (char)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 int +test_test_set_size(size_t size) +{ + size_t i; + bool reference[size]; + uint64_t *bitset; + + rand_bool_ary(reference, size); + + bitset = alloc_bitset(size); + + if (bitset == NULL) + return TEST_FAILED; + + rte_bitset_init(bitset, size); + + for (i = 0; i < size; i++) { + if (reference[i]) + rte_bitset_set(bitset, i); + else + rte_bitset_clear(bitset, i); + } + + for (i = 0; i < size; i++) + if (reference[i] != rte_bitset_test(bitset, i)) + return TEST_FAILED; + + if (free_bitset(bitset, size) != TEST_SUCCESS) + return TEST_FAILED; + + return TEST_SUCCESS; +} + +#define RAND_ITERATIONS (10000) +#define RAND_SET_MAX_SIZE (1000) + +static int +test_test_set(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_test_set_size(size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +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); + + if (bitset == NULL) + return TEST_FAILED; + + 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; + } + + } + + if (free_bitset(bitset, size) != TEST_SUCCESS) + return TEST_FAILED; + + 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); + + if (bitset == NULL) + return TEST_FAILED; + + 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; + } + + if (free_bitset(bitset, size) != TEST_SUCCESS) + return TEST_FAILED; + + 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); + + if (bitset == NULL) + return TEST_FAILED; + + rte_bitset_init(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; + + if (free_bitset(bitset, size) != TEST_SUCCESS) + return TEST_FAILED; + + 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_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)); + + if (rte_bitset_equal(bitset_a, bitset_b, size)) + return TEST_FAILED; + + 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 int +test_bitset(void) +{ + if (test_test_set() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_find() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_foreach() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_count() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_define() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_equal() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_copy() != TEST_SUCCESS) + return TEST_FAILED; + + if (test_to_str() != TEST_SUCCESS) + return TEST_FAILED; + + return TEST_SUCCESS; +} + +REGISTER_FAST_TEST(bitset_autotest, true, true, test_bitset); 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..24c6ec3703 --- /dev/null +++ b/lib/eal/include/rte_bitset.h @@ -0,0 +1,884 @@ +/* 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)) + +/** + * @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 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 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 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. + * + * @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; + uint64_t unused_mask; + + /* + * 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]); + + unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size); + total += rte_popcount64(bitset[i] & unused_mask); + + 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 dst_bitset and @c src_bitset, and store the results 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_or(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. + * + * Bitwise and two bitsets. + * + * Perform a bitwise AND operation on all bits in the two equal-size + * bitsets @c dst_bitset and @c src_bitset, and store the results 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_and(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. + * + * Bitwise xor two bitsets. + * + * Perform a bitwise XOR operation on all bits in the two equal-size + * bitsets @c dst_bitset and @c src_bitset, and store the results 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_xor(uint64_t *__rte_restrict dst_bitset, + const uint64_t *__rte_restrict 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. + * + * 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. 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 Fri Feb 16 10:23:46 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: 136848 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 EE2A143B30; Fri, 16 Feb 2024 11:31:54 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id A7DB043260; Fri, 16 Feb 2024 11:31:50 +0100 (CET) Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-he1eur04on2052.outbound.protection.outlook.com [40.107.7.52]) by mails.dpdk.org (Postfix) with ESMTP id 64B194064A for ; Fri, 16 Feb 2024 11:31:48 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ELc23GRcd9gP0CUjc5O7iIjCz8dj0BtNvdkfBAlhYtpSQ8kJi9YEOpxHaKNdyGqPBYfvXR35XA7VV7Q+2ub+lksckcYDZoIDU/MpX8UAoILrbceT/+VZ6+ifks86K7DPtNxsANVx6+ia10PdGEPX1gklNZyoppi5wgkgup7aORjyWt2zXhZEmsWZmvbI3LYOp+08kSWOVJrx9FfN3aW5DadOG8pEKjZ5mpzh0dHLF64T+YuNoZ+sO+ZGgLFkQJ2uaLmt7aH57hhKkFKSzBsRJ8zVqoHB0IInzhyLmG5pYMvN3VATGhidPULL03LWVIDxSiKOEp5KEfgDehkVVJflqQ== 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=eucfxGFbUBfHjrrSKntV2aIfZy07luKgQDt+AUeda7c=; b=BKN9lYWAm5jInsPfTuY7cbcMYQqCB2eNKw87Z286gCHQWiTWBulFiIImfv6kGNRB1fHKdIgZ3LQzCtjW8HnNI0/QhjiaoLlEIcgrhfulhg/3lHti6nOlFGixGHpDZpZad6GmWcAjwxHXKUUw6VQ80ckMtH5jyMvev8UXUVMNww6NceR8XYklqCej7kq5YmQaA15Ye9QVsdD5XhJt4h8B3pKG1Bmfw7qr8AqzeWqD7a5OyVjJJWADeQmJGuyaoiswn/txuEOq4rHGWZXZOhpGyomxrSo9lROmM2AWe49jXO0hKmWFNIAb87Vo8saaMUm0dEqCCoiKBPT10m4a0szDwQ== 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=eucfxGFbUBfHjrrSKntV2aIfZy07luKgQDt+AUeda7c=; b=Wxr9HyJ5lNwo20dgoHIaThZMJMhUkwp9tOgx6iB8Lyh7h0wtAxnc1LXXiMQzORTGeC8oh7aKZp33OB2Q/dirkm7oPSkpIQn5n19a9KWh8nr8shNdJMQSd+0ijdN8+nPOhE2VrvcgziO5ZwuSbfN26jYAC27mUvZYGh+paa4ftC7Z9IcGC6zwV7fJRt0jTDBoaWDHqQryvhdMkyyjXajVQdRpObXPO1tTLjxeOSMhzMoOOMcZvzHBCf9D+IpopFBsHf5qx8Yha8bLYSc/Q+qgXd8oEfT7TvBlnKkmxU+Qzljdo4n/XsdOMaTCc7pwrmZP8U5fBn3JPY4FYAtisgB4YQ== Received: from DB8PR06CA0030.eurprd06.prod.outlook.com (2603:10a6:10:100::43) by DBAPR07MB6776.eurprd07.prod.outlook.com (2603:10a6:10:19c::13) 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:31:46 +0000 Received: from DU6PEPF0000B620.eurprd02.prod.outlook.com (2603:10a6:10:100:cafe::22) by DB8PR06CA0030.outlook.office365.com (2603:10a6:10:100::43) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7270.40 via Frontend Transport; Fri, 16 Feb 2024 10:31:46 +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 DU6PEPF0000B620.mail.protection.outlook.com (10.167.8.136) 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:31:45 +0000 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.65) with Microsoft SMTP Server id 15.2.1258.12; Fri, 16 Feb 2024 11:31:45 +0100 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id 38B4F1C0084; Fri, 16 Feb 2024 11:31:45 +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 2/4] eal: add bitset test suite Date: Fri, 16 Feb 2024 11:23:46 +0100 Message-ID: <20240216102348.480407-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> References: <20240131131301.418361-1-mattias.ronnblom@ericsson.com> <20240216102348.480407-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: DU6PEPF0000B620:EE_|DBAPR07MB6776:EE_ X-MS-Office365-Filtering-Correlation-Id: cb797b16-6bfc-4bee-7b8a-08dc2eda79c1 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 8hDrAvl/IyhzKYDB8jIemi2FVZNnPrjqHg0SHiuqWaXJFISZWQaJvqSEnaPCZhJsyUddeFnqHc/87RlwXtalwzIEGr7jFaBw2zn4vbVZTbsliG2JIiFh55UIWezeCTkyLwSiDKrSCqDvaqpOBK1B/tmndkBUMTnRrYcKbXIt1FLXHicJ0iSlyHXHExA566jhQBMdJb7l/Hd+MhRQgQxjF6pfvFvGVTcEs7lB6m8zgwjEqJJ9NJLNtrNgPNzpOVqoMG2mJeGEY+eWWigM7IMQMWAN/3V9iH6GxEdZRnkNkz/Jw5kxmw5FArNsbsTKSurE0MSU6SWy69cKORZfWLQer7SUQ4QqG37UXOacZfcXAh4nf3UkNaDW8SEwcR3fzBvIBT7jtQpc4zLpTCI1fRt3WpFvLpu3G4u8MKY97QL0lpXEXFXjD6Idsq1nVB3ew+C6av/4xibEUHo+ZZn5Z7krzShB0vHr8zRq9ALEn+5HtIeJn7uzv4sdOW7oF7mcmgvYc4kvsdgIguxUL3xQ8yJvwcyMYNbTbFtomrRlZmJiQSAiaVZv7Peo7w6ItNuxJlFWI0BPPkulBMlh3PR3SC2EEfBVLpfzLhvR/fGINv3c4S9IKNNhtoAxUm4otqZcS5WZlhjNXrzJjHbdG1Qv/OLxBaPDRiRsrErzmFNP8P+7p14= 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)(376002)(396003)(346002)(39860400002)(136003)(230922051799003)(64100799003)(451199024)(36860700004)(1800799012)(186009)(82310400011)(46966006)(40470700004)(8676002)(478600001)(41300700001)(8936002)(4326008)(2906002)(30864003)(5660300002)(70206006)(316002)(54906003)(6916009)(70586007)(2616005)(1076003)(336012)(83380400001)(66574015)(356005)(82960400001)(6266002)(107886003)(86362001)(7636003)(26005)(36756003)(82740400003); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Feb 2024 10:31:45.9301 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: cb797b16-6bfc-4bee-7b8a-08dc2eda79c1 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: DU6PEPF0000B620.eurprd02.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBAPR07MB6776 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 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 | 870 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 871 insertions(+) create mode 100644 app/test/test_bitset.c diff --git a/app/test/meson.build b/app/test/meson.build index b4382cf4ad..d5a7f771ae 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..84c8a117ee --- /dev/null +++ b/app/test/test_bitset.c @@ -0,0 +1,870 @@ +/* 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); +} + +static int +test_set_clear_size(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]) + rte_bitset_set(bitset, i); + else + rte_bitset_clear(bitset, i); + } + + for (i = 0; i < size; i++) + if (reference[i] != rte_bitset_test(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(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_set_clear_size(size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +static int +test_flip_size(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 = rte_bitset_test(bitset, i); + + rte_bitset_flip(bitset, i); + + TEST_ASSERT(rte_bitset_test(bitset, i) != value, + "Bit %zd was not flipped", i); + + rte_bitset_assign(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(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_flip_size(size) != TEST_SUCCESS) + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +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 Fri Feb 16 10:23:47 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: 136847 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 A299E43B30; Fri, 16 Feb 2024 11:31:49 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 8B1674064A; Fri, 16 Feb 2024 11:31:49 +0100 (CET) Received: from EUR01-HE1-obe.outbound.protection.outlook.com (mail-he1eur01on2073.outbound.protection.outlook.com [40.107.13.73]) by mails.dpdk.org (Postfix) with ESMTP id 4B389402DD for ; Fri, 16 Feb 2024 11:31:48 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=WBigcws+lQyqJyYTGwf4f6FpiJv2wrgNCbQCDeRF9eD4pnlORl4eL28MHqPUMfwtJLq+VqT8Th+64XwLUnVjhuq/R0a9tRYNx/wLhAkiOoL4486+OcXXJ99Vl8NkAI6Zylii+/VqsYQglOCeTZDDB7MeUWbzpFnJ45OOtUMUJQBczVEpmdK3COBK3IHJUgc2OxPHJ2dh4or3+QDltgYcbBNRoG7G0gCLt++3Hq3Ni8ja9PcNXDzZaVCnOuXLfF3+WjyJc1VY5tP5Axsj6UsuxD0DoxF5aS/mh8du6x5y8v7Z1EXL8VFdZvJbNEeVffEuIcRBe88S6zJMm3V7+nTEMw== 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=LF27ZtakQd1w3JbLIS/PV/zEOprNrFh4tTBt8lW4GMY=; b=Qd3LPrKLfyhxrhnx6tT5nxfEJV3saae0xdogUjuzjrkqoulaeurPmw27AmynxpTRonQdloUk6pSREnoDju53IY/bZ91Njw7KmH1CHvpS3z0Qfvv4wq2ykzJfbAoEkuT2Frw9rbUU/UZDOPZ8cb1xwrsEQFlbv5s4X4xQRSznb+d7NM6tz58c9i/DkvQWj+R63GUwht6ZEP+KYsGQkafhG3/jpCGq/P+ZlFV/++JSWoMdmth29CvQ58Lc4cmrg9FZlybThQgqaRG+M1bPAHgxjin9Th0v+QsjdbmYalo7k5CddqRmEmlrt4oS2zVQmw31NbSg4CS4QZIiHBcWs05fJA== 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=LF27ZtakQd1w3JbLIS/PV/zEOprNrFh4tTBt8lW4GMY=; b=bqMpwDrtfbfWJj4ZGrNCISbrP+7Putn0KMFihCDexGLOlOTkuxjuNDoioyg56WbKims7i5dgLgnaVqgv5F0cA2gn9DW8GZRYnwXyrIOeg6WNviWTlIaa6hkTXBqp7RIElG399U21x4MZ/Vs1FJ6/M8rJ6NI6BeAlcObEGOWEJc82VNVlxqqapZWJLfk6GejqPW7SRaYa5osT0Z1mWfdHfG9rXMIcF7ONTcDTaQId9MGqaXGKZN1tVHXR44P/S75LI6aHNZow4/62oiwv5h5TZeJfdPqajgLyx/3nWqMMvkft4ALtenvTl/zXPmIIauZL4slsqrgw0hF7IeXNNL3ZYw== Received: from AS8P189CA0006.EURP189.PROD.OUTLOOK.COM (2603:10a6:20b:31f::33) by AM7PR07MB6358.eurprd07.prod.outlook.com (2603:10a6:20b:134::8) 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:31:46 +0000 Received: from AM2PEPF0001C70F.eurprd05.prod.outlook.com (2603:10a6:20b:31f:cafe::19) by AS8P189CA0006.outlook.office365.com (2603:10a6:20b:31f::33) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7292.26 via Frontend Transport; Fri, 16 Feb 2024 10:31:46 +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 AM2PEPF0001C70F.mail.protection.outlook.com (10.167.16.203) 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:31:46 +0000 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.69) with Microsoft SMTP Server id 15.2.1258.12; Fri, 16 Feb 2024 11:31:45 +0100 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id 9EBA61C0084; Fri, 16 Feb 2024 11:31:45 +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 3/4] service: use multi-word bitset to represent service flags Date: Fri, 16 Feb 2024 11:23:47 +0100 Message-ID: <20240216102348.480407-3-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> References: <20240131131301.418361-1-mattias.ronnblom@ericsson.com> <20240216102348.480407-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM2PEPF0001C70F:EE_|AM7PR07MB6358:EE_ X-MS-Office365-Filtering-Correlation-Id: fb97e5c3-22c2-4193-2858-08dc2eda7a13 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: xtUxRX084LeoNUeF4umWOkcXCh11L69BHVrVCoe74S745zPGerAx+tXQL8KcG8aHXIloHdOhNJ7aFWDV8g4Csz5Xx2YEqxaNtTFqHa5DJJbLFg0fM6LH2PMwyMF17shViM0T5xong0lFWwF1TaMfTcknPKvusFK5der24/vKLwJQnahzE1AQvP3BzQ7KLCykZQsJtXxFggbL4SRKkegIDSJFQYqpzAqXXLgAX4fp3lbfgfxGoMq/xM1uQWJrKsSkhiituhm45+AUm3B6xJe1ifwEZubRvvGhztQ4NlKqH9KfLclDf5vIplpG1Tz2+ZEXV3ORBHwBscRnhHX0IS2vIBTJCJbfb4QCw87gaDyOuFJI7S7iCpp6scDOBpef0JDaMLUlxJOW+ASvxg9e1eFKFlhESxX0VC75EMSS7vz9h66K+TlAkkchUjI3zEN/N4HkUlUp/TUGyXTzKxzM3+i7eOH7FitmG/8m1zreuPagvgDHEoLT89ctbTcD7DEppVmFjjaWeoaYZYi3IkgIc4Hx2ddIa3SzGcCy+tw3U00MYk7FdsMdJHG2ga0r8Z3PyqGvey0KhSrnESPWfKPa72McrHW0dH5XP222lMNksPqNkvsmHrFru8av2T0CwCI2n3m5DWTUkiCjCeL403lkkrL3pMoRW9aNBt18swhSlqTzvGc= 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)(346002)(396003)(39860400002)(376002)(136003)(230922051799003)(64100799003)(1800799012)(451199024)(186009)(82310400011)(36860700004)(46966006)(40470700004)(4326008)(8936002)(8676002)(6916009)(5660300002)(2906002)(2616005)(41300700001)(26005)(1076003)(36756003)(478600001)(107886003)(82960400001)(356005)(82740400003)(7636003)(83380400001)(66574015)(6266002)(336012)(86362001)(70206006)(70586007)(316002)(54906003); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Feb 2024 10:31:46.4966 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: fb97e5c3-22c2-4193-2858-08dc2eda7a13 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: AM2PEPF0001C70F.eurprd05.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM7PR07MB6358 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 Use a multi-word bitset to track which services are mapped to which lcores, allowing the RTE_SERVICE_NUM_MAX compile-time constant to be > 64. Replace array-of-bytes service-currently-active flags with a more compact multi-word bitset-based representation, reducing memory footprint somewhat. Signed-off-by: Mattias Rönnblom --- lib/eal/common/rte_service.c | 70 ++++++++++++++---------------------- 1 file changed, 27 insertions(+), 43 deletions(-) diff --git a/lib/eal/common/rte_service.c b/lib/eal/common/rte_service.c index d959c91459..ac96ecaca8 100644 --- a/lib/eal/common/rte_service.c +++ b/lib/eal/common/rte_service.c @@ -11,6 +11,7 @@ #include #include +#include #include #include #include @@ -63,11 +64,11 @@ struct service_stats { /* the internal values of a service core */ struct core_state { /* map of services IDs are run on this core */ - uint64_t service_mask; + RTE_BITSET_DECLARE(mapped_services, RTE_SERVICE_NUM_MAX); RTE_ATOMIC(uint8_t) runstate; /* running or stopped */ RTE_ATOMIC(uint8_t) thread_active; /* indicates when thread is in service_run() */ uint8_t is_service_core; /* set if core is currently a service core */ - uint8_t service_active_on_lcore[RTE_SERVICE_NUM_MAX]; + RTE_BITSET_DECLARE(service_active_on_lcore, RTE_SERVICE_NUM_MAX); RTE_ATOMIC(uint64_t) loops; RTE_ATOMIC(uint64_t) cycles; struct service_stats service_stats[RTE_SERVICE_NUM_MAX]; @@ -81,11 +82,6 @@ static uint32_t rte_service_library_initialized; int32_t rte_service_init(void) { - /* Hard limit due to the use of an uint64_t-based bitmask (and the - * clzl intrinsic). - */ - RTE_BUILD_BUG_ON(RTE_SERVICE_NUM_MAX > 64); - if (rte_service_library_initialized) { EAL_LOG(NOTICE, "service library init() called, init flag %d", @@ -296,7 +292,7 @@ rte_service_component_unregister(uint32_t id) /* clear the run-bit in all cores */ for (i = 0; i < RTE_MAX_LCORE; i++) - lcore_states[i].service_mask &= ~(UINT64_C(1) << id); + rte_bitset_clear(lcore_states[i].mapped_services, id); memset(&rte_services[id], 0, sizeof(struct rte_service_spec_impl)); @@ -410,7 +406,7 @@ service_runner_do_callback(struct rte_service_spec_impl *s, /* Expects the service 's' is valid. */ static int32_t -service_run(uint32_t i, struct core_state *cs, uint64_t service_mask, +service_run(uint32_t i, struct core_state *cs, const uint64_t *mapped_services, struct rte_service_spec_impl *s, uint32_t serialize_mt_unsafe) { if (!s) @@ -424,12 +420,12 @@ service_run(uint32_t i, struct core_state *cs, uint64_t service_mask, RUNSTATE_RUNNING || rte_atomic_load_explicit(&s->app_runstate, rte_memory_order_acquire) != RUNSTATE_RUNNING || - !(service_mask & (UINT64_C(1) << i))) { - cs->service_active_on_lcore[i] = 0; + !rte_bitset_test(mapped_services, i)) { + rte_bitset_clear(cs->service_active_on_lcore, i); return -ENOEXEC; } - cs->service_active_on_lcore[i] = 1; + rte_bitset_set(cs->service_active_on_lcore, i); if ((service_mt_safe(s) == 0) && (serialize_mt_unsafe == 1)) { if (!rte_spinlock_trylock(&s->execute_lock)) @@ -454,7 +450,7 @@ rte_service_may_be_active(uint32_t id) return -EINVAL; for (i = 0; i < lcore_count; i++) { - if (lcore_states[ids[i]].service_active_on_lcore[id]) + if (rte_bitset_test(lcore_states[ids[i]].service_active_on_lcore, id)) return 1; } @@ -474,7 +470,9 @@ rte_service_run_iter_on_app_lcore(uint32_t id, uint32_t serialize_mt_unsafe) */ rte_atomic_fetch_add_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed); - int ret = service_run(id, cs, UINT64_MAX, s, serialize_mt_unsafe); + RTE_BITSET_DECLARE(all_services, RTE_SERVICE_NUM_MAX); + rte_bitset_set_all(all_services, RTE_SERVICE_NUM_MAX); + int ret = service_run(id, cs, all_services, s, serialize_mt_unsafe); rte_atomic_fetch_sub_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed); @@ -485,7 +483,6 @@ static int32_t service_runner_func(void *arg) { RTE_SET_USED(arg); - uint8_t i; const int lcore = rte_lcore_id(); struct core_state *cs = &lcore_states[lcore]; @@ -497,20 +494,11 @@ service_runner_func(void *arg) */ while (rte_atomic_load_explicit(&cs->runstate, rte_memory_order_acquire) == RUNSTATE_RUNNING) { + ssize_t id; - const uint64_t service_mask = cs->service_mask; - uint8_t start_id; - uint8_t end_id; - - if (service_mask == 0) - continue; - - start_id = rte_ctz64(service_mask); - end_id = 64 - rte_clz64(service_mask); - - for (i = start_id; i < end_id; i++) { + RTE_BITSET_FOREACH_SET(id, cs->mapped_services, RTE_SERVICE_NUM_MAX) { /* return value ignored as no change to code flow */ - service_run(i, cs, service_mask, service_get(i), 1); + service_run(id, cs, cs->mapped_services, service_get(id), 1); } rte_atomic_store_explicit(&cs->loops, cs->loops + 1, rte_memory_order_relaxed); @@ -519,8 +507,7 @@ service_runner_func(void *arg) /* Switch off this core for all services, to ensure that future * calls to may_be_active() know this core is switched off. */ - for (i = 0; i < RTE_SERVICE_NUM_MAX; i++) - cs->service_active_on_lcore[i] = 0; + rte_bitset_clear_all(cs->service_active_on_lcore, RTE_SERVICE_NUM_MAX); /* Use SEQ CST memory ordering to avoid any re-ordering around * this store, ensuring that once this store is visible, the service @@ -586,7 +573,7 @@ rte_service_lcore_count_services(uint32_t lcore) if (!cs->is_service_core) return -ENOTSUP; - return rte_popcount64(cs->service_mask); + return rte_bitset_count_set(cs->mapped_services, RTE_SERVICE_NUM_MAX); } int32_t @@ -639,25 +626,23 @@ service_update(uint32_t sid, uint32_t lcore, uint32_t *set, uint32_t *enabled) !lcore_states[lcore].is_service_core) return -EINVAL; - uint64_t sid_mask = UINT64_C(1) << sid; if (set) { - uint64_t lcore_mapped = lcore_states[lcore].service_mask & - sid_mask; + uint64_t lcore_mapped = rte_bitset_test(lcore_states[lcore].mapped_services, sid); if (*set && !lcore_mapped) { - lcore_states[lcore].service_mask |= sid_mask; + rte_bitset_set(lcore_states[lcore].mapped_services, sid); rte_atomic_fetch_add_explicit(&rte_services[sid].num_mapped_cores, 1, rte_memory_order_relaxed); } if (!*set && lcore_mapped) { - lcore_states[lcore].service_mask &= ~(sid_mask); + rte_bitset_clear(lcore_states[lcore].mapped_services, sid); rte_atomic_fetch_sub_explicit(&rte_services[sid].num_mapped_cores, 1, rte_memory_order_relaxed); } } if (enabled) - *enabled = !!(lcore_states[lcore].service_mask & (sid_mask)); + *enabled = rte_bitset_test(lcore_states[lcore].mapped_services, sid); return 0; } @@ -699,11 +684,11 @@ set_lcore_state(uint32_t lcore, int32_t state) int32_t rte_service_lcore_reset_all(void) { - /* loop over cores, reset all to mask 0 */ + /* loop over cores, reset all mapped services */ uint32_t i; for (i = 0; i < RTE_MAX_LCORE; i++) { if (lcore_states[i].is_service_core) { - lcore_states[i].service_mask = 0; + rte_bitset_clear_all(lcore_states[i].mapped_services, RTE_SERVICE_NUM_MAX); set_lcore_state(i, ROLE_RTE); /* runstate act as guard variable Use * store-release memory order here to synchronize @@ -731,7 +716,7 @@ rte_service_lcore_add(uint32_t lcore) set_lcore_state(lcore, ROLE_SERVICE); /* ensure that after adding a core the mask and state are defaults */ - lcore_states[lcore].service_mask = 0; + rte_bitset_clear_all(lcore_states[lcore].mapped_services, RTE_SERVICE_NUM_MAX); /* Use store-release memory order here to synchronize with * load-acquire in runstate read functions. */ @@ -814,12 +799,11 @@ rte_service_lcore_stop(uint32_t lcore) uint32_t i; struct core_state *cs = &lcore_states[lcore]; - uint64_t service_mask = cs->service_mask; for (i = 0; i < RTE_SERVICE_NUM_MAX; i++) { - int32_t enabled = service_mask & (UINT64_C(1) << i); - int32_t service_running = rte_service_runstate_get(i); - int32_t only_core = (1 == + bool enabled = rte_bitset_test(cs->mapped_services, i); + bool service_running = rte_service_runstate_get(i); + bool only_core = (1 == rte_atomic_load_explicit(&rte_services[i].num_mapped_cores, rte_memory_order_relaxed)); From patchwork Fri Feb 16 10:23:48 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: 136849 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 AED9C43B30; Fri, 16 Feb 2024 11:32:00 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id D20B94330E; Fri, 16 Feb 2024 11:31:51 +0100 (CET) Received: from EUR01-HE1-obe.outbound.protection.outlook.com (mail-he1eur01on2043.outbound.protection.outlook.com [40.107.13.43]) by mails.dpdk.org (Postfix) with ESMTP id BA630402DD for ; Fri, 16 Feb 2024 11:31:48 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Cn4JIMN1yypv1KmoSd17YJRdezzvnEJcqNPmReDIF5ZjIYbSaDJhmy31wH4Jqq6mkAhhGJztfCjip4s/XsSBH7W65YKURjf3xvewMIMLGArbH1sxhgDzHJD0LPdts7uBV9iR33iae8Cu2v4eMhAB77NS2zbMv/5/TDCik2WSGsZPg59kJayFkUdvDROQP+YF4aQA+EfKOuWO6030P9qgez0ftsfTtvgAO1EfGv9Z57BA5uHoBqF6OlTJh+4TMjmJAFCyj22hRdApsJkcr2YsCG+tsU2EKfIYTLqrSX+UD6O5Yhx8sX1YvYOEJ9FyFfugNhWtB4CAUM4ZG05Fi3Rixg== 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=+YSApPRKWcdd2D9JT2bZlPmblZF1koIbJYQpUH3KfZc=; b=CGS+TQKl7t10Au6Wl/XEaS2BqQWm1DJ87y+M5EboxckLKrdBpDPxW06jrLgYoq6XxeD2m6stLYRiT1QmMmIofDjb5ww+sgWpznF/IQdiII/AImEEu0eB+05zVEzcXn17VchMm27msYBgoftkw3tKOWf6Z9YzjKn1X8PUVPbAjiwtxe/e26tAFdpWWg60sWB0D/nQCooT61q1sVmjzKeAIMdhDviurbCddCK0WyYb642MIEw8ojNG1784urcOF36wFglGn0jiECPX1H3pTbOBh7KwSeJVMIHxVt779PpfOQ5IaIi9nZKrtw+COaAxsS4P2OZJVCBTsvVpfmIsFAxhgg== 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=+YSApPRKWcdd2D9JT2bZlPmblZF1koIbJYQpUH3KfZc=; b=XSAXduYXrAer/VJYb3gl50W1t9E/tduaZsZJHkUSRZpD8JOdVqTwpLhSbjTXiMtcB87+799KqP8OOqqmAQiarULAd1MRZGhMOkhTAy5XiZ/Nhys/wiZYjVC5hnwJhsJB6eHMdExq72yzc6qoYVV2wOkWcUT98q/2DJzFRE1wrHbulC8hzCs1zPKJHq/mAnAgaDDl47tdySGWDkn7RCKrpmK12JkSdK2B8W1xMNEraUpG7d0eHpeAh7Eb3J6b6kUaCLyKdPnHLbqIhyjG+hy/tb9DkV5AV7yxfmB0Xz8I3hoGCUeCDHD/5SSPKzlgrGU+uX6tyv0VQib21qXOunOtTQ== Received: from DU2PR04CA0278.eurprd04.prod.outlook.com (2603:10a6:10:28c::13) by GVXPR07MB10014.eurprd07.prod.outlook.com (2603:10a6:150:122::13) 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:31:47 +0000 Received: from DU6PEPF0000B621.eurprd02.prod.outlook.com (2603:10a6:10:28c:cafe::88) by DU2PR04CA0278.outlook.office365.com (2603:10a6:10:28c::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7270.40 via Frontend Transport; Fri, 16 Feb 2024 10:31:46 +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 DU6PEPF0000B621.mail.protection.outlook.com (10.167.8.138) 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:31:46 +0000 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.63) with Microsoft SMTP Server id 15.2.1258.12; Fri, 16 Feb 2024 11:31:46 +0100 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id 0B5F21C0084; Fri, 16 Feb 2024 11:31:46 +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 4/4] event/dsw: optimize serving port logic Date: Fri, 16 Feb 2024 11:23:48 +0100 Message-ID: <20240216102348.480407-4-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> References: <20240131131301.418361-1-mattias.ronnblom@ericsson.com> <20240216102348.480407-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: DU6PEPF0000B621:EE_|GVXPR07MB10014:EE_ X-MS-Office365-Filtering-Correlation-Id: 3c23fdc6-b8d0-4b5f-c48f-08dc2eda7a33 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: OnvdJnyYM41wf4BVWEgJnp6SsFGdOLApP1RS0sPY+DTlB+RRhnm2SfOrXTqnc6A/zALeVlDy7MRQWa3G/1VQB/S2WeL2b/R+Ts+/mqgehziRf2zeRrn/NTiGmjIjaRbgq3FISmXmfOZGXjfAPY5uIIIDUrbChp4qLkfuMbFIeUGoKH/xgzXm6903VF378EcLh621YjoxTrlu+jJPNGfgwGNfN67xc7M0wvuwyislLPQrldaBvgDKc9Vr1Kxug8uP/2ka6fz3G4GvExzPcof8Wddzoz3BDYFNOJNRQ2DSSJ3rT0V6ypUDxO4thysrUqqOAtQ0ocnAjKtoM3e09VEW2SDU7sjYdmfPL6a5w9yISmSchBOR4IIpPW4sh/MgAqEMvIya5ju05AD76vQD1aj90g/1PpZBi+MoEm/rwUeBpBFP/GYbqhJsKYyhxQSBzsssqGVb9tn6xlYOkRCI8EixdoyfbCar+72+UUVzbSIQF5FCuFkxsY3i0XjLWb/PBHWjK9XZ9/VEmReo0nm5oMxzlNhiXOfM5Cx1P5KCepQ9C8q7cAW+JaK4iK7uP7HalZHz+RzKYAzLNlE5C5ov73wJm9qReQKgCaN0ZmalyL+pACCILkBQGJcCVQVtVCx5U6Gx2Y62Pbn3JuhqjlYANM/qNGeu+z0pDDOpJot1lY/U44w= 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)(39860400002)(136003)(346002)(230922051799003)(82310400011)(36860700004)(451199024)(1800799012)(186009)(64100799003)(46966006)(40470700004)(82740400003)(316002)(82960400001)(7636003)(356005)(1076003)(8936002)(4326008)(2906002)(8676002)(6916009)(70586007)(70206006)(86362001)(26005)(107886003)(83380400001)(336012)(41300700001)(54906003)(6266002)(5660300002)(36756003)(2616005)(478600001); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 Feb 2024 10:31:46.6791 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 3c23fdc6-b8d0-4b5f-c48f-08dc2eda7a33 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: DU6PEPF0000B621.eurprd02.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: GVXPR07MB10014 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 To reduce flow migration overhead, replace the array-based representation of which set of ports are bound to a particular queue by a multi-word bitset. Signed-off-by: Mattias Rönnblom --- drivers/event/dsw/dsw_evdev.c | 34 +++++++++++++++++++--------------- drivers/event/dsw/dsw_evdev.h | 3 ++- drivers/event/dsw/dsw_event.c | 11 ++++------- 3 files changed, 25 insertions(+), 23 deletions(-) diff --git a/drivers/event/dsw/dsw_evdev.c b/drivers/event/dsw/dsw_evdev.c index 1209e73a9d..a0781e4141 100644 --- a/drivers/event/dsw/dsw_evdev.c +++ b/drivers/event/dsw/dsw_evdev.c @@ -118,6 +118,7 @@ dsw_queue_setup(struct rte_eventdev *dev, uint8_t queue_id, queue->schedule_type = conf->schedule_type; } + rte_bitset_init(queue->serving_ports, DSW_MAX_PORTS); queue->num_serving_ports = 0; return 0; @@ -144,24 +145,19 @@ dsw_queue_release(struct rte_eventdev *dev __rte_unused, static void queue_add_port(struct dsw_queue *queue, uint16_t port_id) { - queue->serving_ports[queue->num_serving_ports] = port_id; + rte_bitset_set(queue->serving_ports, port_id); queue->num_serving_ports++; } static bool queue_remove_port(struct dsw_queue *queue, uint16_t port_id) { - uint16_t i; + if (rte_bitset_test(queue->serving_ports, port_id)) { + queue->num_serving_ports--; + rte_bitset_clear(queue->serving_ports, port_id); + return true; + } - for (i = 0; i < queue->num_serving_ports; i++) - if (queue->serving_ports[i] == port_id) { - uint16_t last_idx = queue->num_serving_ports - 1; - if (i != last_idx) - queue->serving_ports[i] = - queue->serving_ports[last_idx]; - queue->num_serving_ports--; - return true; - } return false; } @@ -256,10 +252,18 @@ initial_flow_to_port_assignment(struct dsw_evdev *dsw) struct dsw_queue *queue = &dsw->queues[queue_id]; uint16_t flow_hash; for (flow_hash = 0; flow_hash < DSW_MAX_FLOWS; flow_hash++) { - uint8_t port_idx = - rte_rand() % queue->num_serving_ports; - uint8_t port_id = - queue->serving_ports[port_idx]; + uint8_t skip = rte_rand_max(queue->num_serving_ports); + uint8_t port_id; + + for (port_id = 0;; port_id++) { + if (rte_bitset_test(queue->serving_ports, + port_id)) { + if (skip == 0) + break; + skip--; + } + } + dsw->queues[queue_id].flow_to_port_map[flow_hash] = port_id; } diff --git a/drivers/event/dsw/dsw_evdev.h b/drivers/event/dsw/dsw_evdev.h index 6416a8a898..503a63cbb2 100644 --- a/drivers/event/dsw/dsw_evdev.h +++ b/drivers/event/dsw/dsw_evdev.h @@ -7,6 +7,7 @@ #include +#include #include #include @@ -234,7 +235,7 @@ struct dsw_port { struct dsw_queue { uint8_t schedule_type; - uint8_t serving_ports[DSW_MAX_PORTS]; + RTE_BITSET_DECLARE(serving_ports, DSW_MAX_PORTS); uint16_t num_serving_ports; uint8_t flow_to_port_map[DSW_MAX_FLOWS] __rte_cache_aligned; diff --git a/drivers/event/dsw/dsw_event.c b/drivers/event/dsw/dsw_event.c index 93bbeead2e..b855f9ecf1 100644 --- a/drivers/event/dsw/dsw_event.c +++ b/drivers/event/dsw/dsw_event.c @@ -447,13 +447,8 @@ static bool dsw_is_serving_port(struct dsw_evdev *dsw, uint8_t port_id, uint8_t queue_id) { struct dsw_queue *queue = &dsw->queues[queue_id]; - uint16_t i; - - for (i = 0; i < queue->num_serving_ports; i++) - if (queue->serving_ports[i] == port_id) - return true; - return false; + return rte_bitset_test(queue->serving_ports, port_id); } static bool @@ -575,7 +570,9 @@ dsw_schedule(struct dsw_evdev *dsw, uint8_t queue_id, uint16_t flow_hash) /* A single-link queue, or atomic/ordered/parallel but * with just a single serving port. */ - port_id = queue->serving_ports[0]; + port_id = (uint8_t)rte_bitset_find_first_set( + queue->serving_ports, DSW_MAX_PORTS + ); DSW_LOG_DP(DEBUG, "Event with queue_id %d flow_hash %d is scheduled " "to port %d.\n", queue_id, flow_hash, port_id);