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 5B72B42DC2; Mon, 3 Jul 2023 14:39:44 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id D560840EF0; Mon, 3 Jul 2023 14:39:43 +0200 (CEST) Received: from mx0b-0016f401.pphosted.com (mx0a-0016f401.pphosted.com [67.231.148.174]) by mails.dpdk.org (Postfix) with ESMTP id 0150E40ED5 for ; Mon, 3 Jul 2023 14:39:41 +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 363CPMaO021364; Mon, 3 Jul 2023 05:39:40 -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=49uGlw5vNaKicpqT53OWtJWFpjNInQn+tPxBZVU9dM0=; b=IBPVQ3DLTEGnubwxT3qZsiP1lJbGbDH3YrJyAbdTnaxIMMj7e3EHp00/JF4HOV1A4n4m +hq7b4TvzC01JEJHGPIF5yQuc4+gDKzMQjXULwA0ha6qeiCW6EoHu4dtoJOfEXU+xWcG cFqIpROKkcNJkB9QcmLvwwdi/cwoBX6//zUGosPnXvwvobEHMPYbqkfNgHEkzuPEEI6m 0+6kPqg4F1jd4z7jNV/+7KrgbStuiuNm8M9DpcUOEiXjkHFLar78nsqzfME2U0F25j0P Tlh5MYi3Wv0FNAZLwpEvLEbzECvAjwvmC+UyPal3MLp7XHRfAnhcN9OLVGSf4pVkA17K cw== Received: from dc5-exch01.marvell.com ([199.233.59.181]) by mx0a-0016f401.pphosted.com (PPS) with ESMTPS id 3rjhgndjmc-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Mon, 03 Jul 2023 05:39:39 -0700 Received: from DC5-EXCH02.marvell.com (10.69.176.39) by DC5-EXCH01.marvell.com (10.69.176.38) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Mon, 3 Jul 2023 05:39:37 -0700 Received: from maili.marvell.com (10.69.176.80) by DC5-EXCH02.marvell.com (10.69.176.39) with Microsoft SMTP Server id 15.0.1497.48 via Frontend Transport; Mon, 3 Jul 2023 05:39:37 -0700 Received: from cavium-DT10.. (unknown [10.28.34.39]) by maili.marvell.com (Postfix) with ESMTP id E68D43F7040; Mon, 3 Jul 2023 05:39:35 -0700 (PDT) From: Volodymyr Fialko To: , CC: , , , Volodymyr Fialko Subject: [PATCH v5] bitmap: add scan from offset function Date: Mon, 3 Jul 2023 14:39:08 +0200 Message-ID: <20230703123909.328480-1-vfialko@marvell.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230703093130.198304-1-vfialko@marvell.com> References: <20230703093130.198304-1-vfialko@marvell.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-Proofpoint-ORIG-GUID: rJ8Ashg26aI1apCEsepFUsiCvEFZVVRR X-Proofpoint-GUID: rJ8Ashg26aI1apCEsepFUsiCvEFZVVRR X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-07-03_09,2023-06-30_01,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 --- v2: - added rte_bitmap_scan_from_offset v3: - added note for internal use only for init_at function v4: - marked init_at function as __rte_internal v5: - removed __rte_internal due to build errors app/test/test_bitmap.c | 33 +++++++++++++++++++++- lib/eal/include/rte_bitmap.h | 55 ++++++++++++++++++++++++++++++++++++ 2 files changed, 87 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..cc14b1ed2e 100644 --- a/lib/eal/include/rte_bitmap.h +++ b/lib/eal/include/rte_bitmap.h @@ -137,6 +137,29 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp) bmp->go2 = 0; } +/** + * Bitmap initialize internal scan pointers at the given position for the scan function. + * + * Note: for private/internal use, for public: + * @see rte_bitmap_scan_from_offset() + * + * @param bmp + * Handle to bitmap instance + * @param pos + * Bit position to start scan + */ +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 +614,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