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 426C442CA5; Tue, 13 Jun 2023 17:41:05 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 1ACDA40C35; Tue, 13 Jun 2023 17:41:05 +0200 (CEST) Received: from mx0b-0016f401.pphosted.com (mx0a-0016f401.pphosted.com [67.231.148.174]) by mails.dpdk.org (Postfix) with ESMTP id E65DB40A8A for ; Tue, 13 Jun 2023 17:41:03 +0200 (CEST) Received: from pps.filterd (m0045849.ppops.net [127.0.0.1]) by mx0a-0016f401.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 35DBUNX6031900; Tue, 13 Jun 2023 08:41:03 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=marvell.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding : content-type; s=pfpt0220; bh=BjhEX2Tv7AQzH7MxdSfFWzsQZw6i9gx1qlQqjRUoCZE=; b=T/JDJJRBSu10d9/EADs3c2zJ3gxUu5cnmteOh+lbYck9bDdvBppVmvEpFK5nYUby6DLR L9D0Q9HWZ8syaO/JW+7pRa5eYZIH+D3VC+QI91XEpoWpzOLnSvuoihdNlIhbPfc7UIpY qaCeHMTj8NqUGULBfK4Elc2q9autFCvKnzFjOJkrRCwACNGKcp80VfdC3kzz2PImTQ/0 OiS2cmMfo02OIi8SO+9IWOCcX4QFsaRMY7TIiztvaxUef+DJP1aZsM4HLIF0hOVjkkqr NplIzhhThJ5bvNkXJ0GMdosdi3hNOoKAkhLD318mGszQQYya5WU2qtJEhpeZxy/+l4O4 Jw== Received: from dc5-exch02.marvell.com ([199.233.59.182]) by mx0a-0016f401.pphosted.com (PPS) with ESMTPS id 3r6qn2h1fp-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Tue, 13 Jun 2023 08:41:02 -0700 Received: from DC5-EXCH01.marvell.com (10.69.176.38) by DC5-EXCH02.marvell.com (10.69.176.39) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Tue, 13 Jun 2023 08:41:01 -0700 Received: from maili.marvell.com (10.69.176.80) by DC5-EXCH01.marvell.com (10.69.176.38) with Microsoft SMTP Server id 15.0.1497.48 via Frontend Transport; Tue, 13 Jun 2023 08:41:01 -0700 Received: from cavium-DT10.. (unknown [10.28.34.39]) by maili.marvell.com (Postfix) with ESMTP id 570183F7041; Tue, 13 Jun 2023 08:40:59 -0700 (PDT) From: Volodymyr Fialko To: , CC: , , , Volodymyr Fialko Subject: [PATCH v2] bitmap: add scan from offset function Date: Tue, 13 Jun 2023 17:40:13 +0200 Message-ID: <20230613154013.2648333-1-vfialko@marvell.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230414083943.270651-1-vfialko@marvell.com> References: <20230414083943.270651-1-vfialko@marvell.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-Proofpoint-ORIG-GUID: QDTVyALzDelDdsxNaSgZWcR3T1yhHy-n X-Proofpoint-GUID: QDTVyALzDelDdsxNaSgZWcR3T1yhHy-n X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.176.26 definitions=2023-06-13_18,2023-06-12_02,2023-05-22_02 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 Currently, in the case when we search for a bit set after a particular value, the bitmap has to be scanned from the beginning and rte_bitmap_scan() has to be called multiple times until we hit the value. Add a new rte_bitmap_scan_from_offset() function to initialize scan state at the given offset and perform scan, this will allow getting the next set bit after certain offset within one scan call. Signed-off-by: Volodymyr Fialko --- app/test/test_bitmap.c | 33 ++++++++++++++++++++- lib/eal/include/rte_bitmap.h | 56 ++++++++++++++++++++++++++++++++++++ 2 files changed, 88 insertions(+), 1 deletion(-) diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c index e9c61590ae..9e38087408 100644 --- a/app/test/test_bitmap.c +++ b/app/test/test_bitmap.c @@ -18,8 +18,8 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) { uint64_t slab1_magic = 0xBADC0FFEEBADF00D; uint64_t slab2_magic = 0xFEEDDEADDEADF00D; + int i, nb_clear, nb_set, next_cl; uint32_t pos = 0, start_pos; - int i, nb_clear, nb_set; uint64_t out_slab = 0; rte_bitmap_reset(bmp); @@ -71,6 +71,37 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) return TEST_FAILED; } + /* Scan with offset check. */ + if (!rte_bitmap_scan_from_offset(bmp, RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) { + printf("Failed to get slab from bitmap with scan from offset.\n"); + return TEST_FAILED; + } + + if (slab2_magic != out_slab) { + printf("Scan from offset operation failed.\n"); + return TEST_FAILED; + } + + /* Scan with offset wrap around check. */ + if (!rte_bitmap_scan_from_offset(bmp, 2 * RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) { + printf("Failed to get slab from bitmap with scan from offset.\n"); + return TEST_FAILED; + } + + if (slab1_magic != out_slab) { + printf("Scan from offset with wrap around operation failed.\n"); + return TEST_FAILED; + } + + /* Test scan when the bit set is on a next cline */ + rte_bitmap_reset(bmp); + next_cl = RTE_MIN(RTE_BITMAP_CL_BIT_SIZE, MAX_BITS); + rte_bitmap_set(bmp, next_cl); + if (!rte_bitmap_scan_from_offset(bmp, 0, &pos, &out_slab)) { + printf("Failed to get slab from next cache line from bitmap.\n"); + return TEST_FAILED; + } + /* Test scan when a cline is half full */ rte_bitmap_reset(bmp); for (i = 0; i < MAX_BITS; i++) diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h index 27ee3d18a4..624365b9c5 100644 --- a/lib/eal/include/rte_bitmap.h +++ b/lib/eal/include/rte_bitmap.h @@ -137,6 +137,30 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp) bmp->go2 = 0; } +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitmap initialize internal scan pointers at the given position for the scan function. + * + * @param bmp + * Handle to bitmap instance + * @param pos + * Bit position to start scan + */ +__rte_experimental +static inline void +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos) +{ + uint64_t *slab1; + + bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); + bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; + bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; + slab1 = bmp->array1 + bmp->index1; + bmp->go2 = *slab1 & (1llu << bmp->offset1); +} + /** * Bitmap memory footprint calculation * @@ -591,6 +615,38 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) return 0; } +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitmap scan from the given offset. + * Function will reset internal scan state to start scanning from the offset + * position. + * @see rte_bitmap_scan() + * + * @param bmp + * Handle to bitmap instance + * @param offset + * Bit offset to start scan + * @param pos + * When function call returns 1, pos contains the position of the next set + * bit, otherwise not modified + * @param slab + * When function call returns 1, slab contains the value of the entire 64-bit + * slab where the bit indicated by pos is located. + * When function call returns 0, slab is not modified. + * @return + * 0 if there is no bit set in the bitmap, 1 otherwise + */ +__rte_experimental +static inline int +rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset, + uint32_t *pos, uint64_t *slab) +{ + __rte_bitmap_scan_init_at(bmp, offset); + return rte_bitmap_scan(bmp, pos, slab); +} + #ifdef __cplusplus } #endif -- 2.34.1