From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 929B541D9B; Tue, 28 Feb 2023 10:45:22 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 6331D42BC9; Tue, 28 Feb 2023 10:45:08 +0100 (CET) Received: from EUR02-DB5-obe.outbound.protection.outlook.com (mail-db5eur02on2041.outbound.protection.outlook.com [40.107.249.41]) by mails.dpdk.org (Postfix) with ESMTP id 9145341181 for ; Tue, 28 Feb 2023 10:45:05 +0100 (CET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=YYgLSEX54NIlWx2SnA1wMkYC2BNQBLy8NsfBhh1nIoupTAO4Xz7aLTzRgaA6QM+PeVkhKvmrVcA4ScdoQCJVaKIABx+K6SPOGvXfWHtyjnnj3mmp9to1YRqyKhpcvpXEB4i4ordPfeJTzOGVmYUP1JKRj0fG4Ep1czeiIBQQEWbGlXIaImirVvdo+zOdbAuOnfikUQJcGAUOUkLWDHI3WGrq+cu1rv+5y/lcuQ5N7NRl1jxWM8vr0meggy5SuHrJvgMFAuNePufMH6rOWt8i5nTDU1/q1T//oXkHKd1v8c8LSzQO8tkpXHbh2iXRj8EiFDFFoIElc/9HfVELM9c+Rg== 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=orYH3OtjnmJP44ssb7/CYcaaz0dyB2ijS3qX517VOxw=; b=WJShEa4IAvBKqAngDut/DBhSRxgYhe3N5sNcc2dZDjcpqC2hgOua17hInXYlXhFMUsbWd03+AVdXYwmHkyCcSsiNFIAKd8qW4QDFrYIgIwGINtD3h1V/aauCu3KL04v6mHfKcJ2oFsrc5rt+XLQKFcgjCeOqMdio8hxSrv1D8Xedg8ezy3mAhU8R+scNda8DW89W9BAyCoT3XSyB+HAKSPqQ1crMRb64odvJYHuRsFNyBZZgO8OInQ7CzCx6j+YO+V+2cg85kJQ6T5St0YutnrZNDOU9d2YtToeDYWPVyrSo1GfsvXBOX+uVMd222nWTis4a/ZpzLduV+2osi7JyvA== 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 Received: from AM5PR0101CA0002.eurprd01.prod.exchangelabs.com (2603:10a6:206:16::15) by DU2PR07MB8285.eurprd07.prod.outlook.com (2603:10a6:10:277::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6134.30; Tue, 28 Feb 2023 09:45:00 +0000 Received: from AM0EUR02FT050.eop-EUR02.prod.protection.outlook.com (2603:10a6:206:16:cafe::28) by AM5PR0101CA0002.outlook.office365.com (2603:10a6:206:16::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6134.30 via Frontend Transport; Tue, 28 Feb 2023 09:45:00 +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 AM0EUR02FT050.mail.protection.outlook.com (10.13.54.117) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256) id 15.20.6156.12 via Frontend Transport; Tue, 28 Feb 2023 09:45:00 +0000 Received: from ESESBMB502.ericsson.se (153.88.183.169) by ESESSMB502.ericsson.se (153.88.183.163) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.2507.17; Tue, 28 Feb 2023 10:44:59 +0100 Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.183.153) by smtp.internal.ericsson.com (153.88.183.185) with Microsoft SMTP Server id 15.1.2507.17 via Frontend Transport; Tue, 28 Feb 2023 10:44:59 +0100 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id 8759A1C006A; Tue, 28 Feb 2023 10:44:59 +0100 (CET) From: =?UTF-8?q?Mattias=20R=C3=B6nnblom?= To: CC: Erik Gabriel Carrillo , David Marchand , , Stefan Sundkvist , =?UTF-8?q?Mattias=20R=C3=B6nnblom?= Subject: [RFC 1/2] eal: add bitset type Date: Tue, 28 Feb 2023 10:39:15 +0100 Message-ID: <20230228093916.87206-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230228093916.87206-1-mattias.ronnblom@ericsson.com> References: <20230228093916.87206-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM0EUR02FT050:EE_|DU2PR07MB8285:EE_ X-MS-Office365-Filtering-Correlation-Id: 88ea363a-c44a-465b-83ff-08db19707580 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: o6sivawecBM/8N9EDXVoL6qGfofolaVgM3aQrGH4BbUQVJ1SL3vP/gxf3nVhXVznEOJBJqtwi8CBI33Lv/gEkUB2UGlneVk9jcIafE6L2VKVkIs4IqQ/UqLVAO2SHn2grLzMSNNTdllubSdjFyS0yye5qnBygkhfUdk6P1nUe0j5tKOzRYl2v7/RJacC9+tTZo7nTucpYudTjU0F/990It/Nbldkt0arg1g5J3Z26KDeVtTtlire/Ig32Y/M8DbPzdTESiiVjz9JJND6SAtzFqEBIwv+eJhVdKq+dr0e0og17TWm8dEd0ol2r+sz6rqdGgI13nmdhZCHNl5NI506q/ag6skGRkxUF6xH3uhhEEtLVoqXhNdw6316XaZWIFOs28gZWpPIIYs5FYwl7AJEzr7fm888yMX/8NMIy26HK4yZIYSAgVxiT1o1KypdOUTk7VOEJ3P+3ZOSObPonPbBi8sk8AzHQ9RufN8j8tzxoLzsF6G5OJ9TIfSdpSlW5BRYvZqIoJyppfZoyFLkZFT8i7q1FzYyElEH+f8dB70DGBqXtEZRmTK3zpaHiZMou7n3DuWHeFt3LZB8os998d+syloCCJzkOHakV3KfoOV0DM6xZfM1q0gEVp+jlGD3ELRBRvk6WlRRuUDWhbq4Ql48ft2uJmfLbVxKIuqkNivCEPzzzd+HeRJVYVIXVDqo4ZGXYRWvUZnwOUOZA/7Exlp5SW/Gz/wQstBn9SfS+vv7pD8= 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:(13230025)(4636009)(39860400002)(376002)(346002)(136003)(396003)(451199018)(40470700004)(46966006)(36840700001)(86362001)(36756003)(5660300002)(6916009)(70206006)(41300700001)(40480700001)(8676002)(4326008)(8936002)(2906002)(30864003)(36860700001)(82960400001)(7636003)(356005)(82740400003)(107886003)(478600001)(54906003)(316002)(70586007)(6666004)(82310400005)(40460700003)(83380400001)(66574015)(47076005)(2616005)(26005)(6266002)(186003)(336012)(1076003)(21314003)(579004); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Feb 2023 09:45:00.0820 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 88ea363a-c44a-465b-83ff-08db19707580 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: AM0EUR02FT050.eop-EUR02.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU2PR07MB8285 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. Signed-off-by: Mattias Rönnblom --- app/test/meson.build | 4 +- app/test/test_bitset.c | 646 ++++++++++++++++++++++++++ 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 | 878 +++++++++++++++++++++++++++++++++++ lib/eal/version.map | 3 + 7 files changed, 1561 insertions(+), 1 deletion(-) 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 f34d19e3c3..03811ff692 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -13,8 +13,9 @@ test_sources = files( 'test_alarm.c', 'test_atomic.c', 'test_barrier.c', - 'test_bitops.c', 'test_bitmap.c', + 'test_bitset.c', + 'test_bitops.c', 'test_bpf.c', 'test_byteorder.c', 'test_cksum.c', @@ -164,6 +165,7 @@ fast_tests = [ ['bpf_autotest', true, true], ['bpf_convert_autotest', true, true], ['bitops_autotest', true, true], + ['bitset_autotest', true, true], ['byteorder_autotest', true, true], ['cksum_autotest', true, true], ['cmdline_autotest', true, true], diff --git a/app/test/test_bitset.c b/app/test/test_bitset.c new file mode 100644 index 0000000000..504363e86e --- /dev/null +++ b/app/test/test_bitset.c @@ -0,0 +1,646 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Ericsson AB + */ + +#include +#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_TEST_COMMAND(bitset_autotest, test_bitset); diff --git a/lib/eal/common/meson.build b/lib/eal/common/meson.build index 917758cc65..687ae51d87 100644 --- a/lib/eal/common/meson.build +++ b/lib/eal/common/meson.build @@ -32,6 +32,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 b0db9b3b3a..fa3cb884e9 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..e333e527e5 --- /dev/null +++ b/lib/eal/include/rte_bitset.h @@ -0,0 +1,878 @@ +/* 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 + +#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 sucessive 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 sucessive 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 sucessive 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. + * + * @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 += __builtin_popcountll(bitset[i]); + + unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size); + total += __builtin_popcountll(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 6d6978f108..9136a71c73 100644 --- a/lib/eal/version.map +++ b/lib/eal/version.map @@ -430,6 +430,9 @@ EXPERIMENTAL { rte_thread_create_control; rte_thread_set_name; __rte_eal_trace_generic_blob; + + # added in X.Y + rte_bitset_to_str; }; INTERNAL { -- 2.34.1