From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM01-SN1-obe.outbound.protection.outlook.com (mail-sn1nam01on0047.outbound.protection.outlook.com [104.47.32.47]) by dpdk.org (Postfix) with ESMTP id 7E8D85F14 for ; Tue, 9 Oct 2018 09:55:22 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=CAVIUMNETWORKS.onmicrosoft.com; s=selector1-cavium-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=bjUhgdlpaZzXc5GzWWqdHJ42T5durskpHNqKMSLOY+Q=; b=RkSkfJMdOo7uNjENXmUu34qDjpEPGtrRcim/TrfyShtpKZAEZC8XnoyNAPrgddOzFp5AEoUTyPrr8Cfc0UHsNCOM2nKb6Pa1tuY9Arm3l85qRSQMdQFPtHBi0EjmYqDIKoXCz5wLjJ+0j99zqYAQJwHD3ZtnEuxkSG+eteaMcAM= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Vivek.Sharma@cavium.com; Received: from dell-e5540.Dlink (119.82.92.140) by BN7PR07MB5380.namprd07.prod.outlook.com (2603:10b6:408:2e::27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.23; Tue, 9 Oct 2018 07:55:20 +0000 From: Vivek Sharma To: dev@dpdk.org Cc: cristian.dumitrescu@intel.com, Vivek Sharma Date: Tue, 9 Oct 2018 13:24:58 +0530 Message-Id: <1539071699-29963-2-git-send-email-vivek.sharma@caviumnetworks.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1539071699-29963-1-git-send-email-vivek.sharma@caviumnetworks.com> References: <1539071699-29963-1-git-send-email-vivek.sharma@caviumnetworks.com> MIME-Version: 1.0 Content-Type: text/plain X-Originating-IP: [119.82.92.140] X-ClientProxiedBy: BMXPR01CA0048.INDPRD01.PROD.OUTLOOK.COM (2603:1096:b00:c::34) To BN7PR07MB5380.namprd07.prod.outlook.com (2603:10b6:408:2e::27) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 982d8df9-6f02-46c4-ec94-08d62dbc900e X-Microsoft-Antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(2017052603328)(7153060)(7193020); SRVR:BN7PR07MB5380; X-Microsoft-Exchange-Diagnostics: 1; BN7PR07MB5380; 3:6QwTDRHbTlWn56RQF0FWFDK85zywo8nGiDbR0YtisIvoH5o06MQArz+rWvFHKxyC+GBveN6mSBvvFtEAXyWeAW/WYWAL/iG9+SZwIhjM64DDrFfZIC2u0w4x8CyIS1TaDhzay130Fpumk4E+2UN79JEUzEIPGuk+QS5M8PHTfcb2IWQvfbXszRqyM5Lfx2eLJgK4ppRgh92DwkT7+peEm0Dswt3/1mnEBDZ5oslk1io7vQ5f5GpC9RVydqbQQK3A; 25:yS4b/jj/xjo2j7LRsHvBSzuXN4Y7rCKqpkzlebnGCwM6Uakk25AiMHKZwL52CcfPSpYE1rSkwjJX47qhOeLQlPBF2d64cZrK0tuP8UHUoiJp9mj9XZvvbjMVe9dYdPs5ihIni4mLxQwImmvVD67e/CcZpfBiH+X+JWiDB8pgOnu9eDnxlUPRI8k0+xm7gEEsZ0iMWYJrn75GWKkuMNAXDNKwivkN/Oz9ey4Ad68lP6cTwfgGJHqsz5Ws3l7gxF6/z5asCxaYGq7s2gJV7lxnH5YCpyPCB/YCXctRR3ZUQ1ykKQGvGppjefj3V6nb0JilvdATUb8mD38j5//i3jm2kQ==; 31:VEAt4ZOv8AyVK1+0UkMmwffiQZEUqQAzvPPl6n0o4OCRyVpwLaqbTstysX7uA7suSL2/vB3ZNRRa7ZjeWvPdigUtiYxYVxZZp7myE+Ei0fUdGyyy859pAldwk1T77BcHU0F7FVFBoxy9pr6zmR74aO117tRlDqoUTDLw9ZizI437a0haywv4z/L4Q8i7RQOPUjZkl6LdaVZbF6cHdgjb+502TxsdnWmDJUOskWd+ONY= X-MS-TrafficTypeDiagnostic: BN7PR07MB5380: X-Microsoft-Exchange-Diagnostics: 1; BN7PR07MB5380; 20:xQ7yoY4ZK3nTKw0RK1Dr7PnOwflIpJmT/TFWYJXWW0Suuyf8ZkrMsWEuEfov6AACzJImHyf+W4abNfnv80MvUTDz9YscPp+u+bg9YqOvDZkwC9szFjavW17NHoYKuZBDxppuImJFNtMlz9/hgVmeswfXv6jkzKL04lV803tKBL/+Zv6CQDkQTjArIxSJ8Z6GxQ/xPi6nidX2P3tiRkc0KLGwJ5zaFEwUPLcXcR7sYkXNknRkw1E09FQaVk2jZ/onV838xAdN/Asj9v9y+y2BQR1V51rMl1hHssFyARMBifsw99B1yIO4kQU5jbwxUWb1M0UiP98CROs9UZ2a9QOlq6fsG1SMaIDaj+5lcrodFT86cAp4/IVkeAlYUA8ncwnrT+3ir8ElNOYUboCOnADrsmHlIFoKcKCuaDURnLTWJVvXgRGwWqYy4FxkboVUUHAKYBXWkjN++E0/9ApGOgML5rrYVJjIkZCdPgRYB5XJmZ60dt9a5bLo0Y2yv6tbijEwvOshIayqPnsEMDuSFdABFKmn97msMrr8snIeZvqTBKkvX3BZRSgKi4bMVbDCCG6vkrs25KOln76j7GslymD/2BthVAJdCu7DVgVFyd3S9lU=; 4:x3olWhH11GHc9ZPvNsgjCduYGQyn+nEZ5Kkf3cF4a7FASJYj/bBWS7RhkEDdjRPAgVq3hEpWMdk4L3nFzmZXJrcV8in23O281tLW8CGpDJNvlQaZ88oGvxsZ0CklWA6706IbHS0BWYy/vTOcMSVfovigO8UtEWs1X6PiZZPfRnTSxypB5gbIUzp/9YkACo4CTKPB3KN08jvEwtgJk5WP+wAqVubC5c8NPn8KZOAUvhEMjUqb9krgftgnf5nXPv2a1w6degIjuuF62DWWc9LXbw== X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(3231355)(944501410)(4982022)(52105095)(3002001)(10201501046)(149066)(150057)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123560045)(20161123558120)(20161123564045)(201708071742011)(7699051); SRVR:BN7PR07MB5380; BCL:0; PCL:0; RULEID:; SRVR:BN7PR07MB5380; X-Forefront-PRVS: 08200063E9 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(136003)(376002)(346002)(396003)(366004)(39860400002)(199004)(189003)(2361001)(53936002)(42882007)(50226002)(107886003)(81166006)(68736007)(14444005)(72206003)(8676002)(6116002)(47776003)(97736004)(6486002)(6512007)(6306002)(16526019)(26005)(3846002)(8936002)(81156014)(186003)(25786009)(6916009)(305945005)(7736002)(478600001)(48376002)(2351001)(105586002)(2906002)(4326008)(50466002)(6666003)(36756003)(16586007)(2616005)(52116002)(51416003)(6506007)(5660300001)(11346002)(486006)(476003)(44832011)(316002)(386003)(956004)(76176011)(66066001)(106356001)(446003); DIR:OUT; SFP:1101; SCL:1; SRVR:BN7PR07MB5380; H:dell-e5540.Dlink; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; Received-SPF: None (protection.outlook.com: cavium.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; BN7PR07MB5380; 23:DTjv8CDs7NKPWpaWIktTzgn1xRa7dtjoFauUy/HI+?= =?us-ascii?Q?qTl1YeIZ+Bcim7Y0n3vMPbsXF6MB8tf/i0hht/e6RsAgoTeCFGKFJXe37jR1?= =?us-ascii?Q?UtqYJp4p1C1R71tkBM2S2+lFdjsrCD4baWtgATEyzMtGVd9h8p3VarSGyg+M?= =?us-ascii?Q?I8zaMR4Uzc2gYBlyubRq494ST6J0oQFK9m8iR7vOKeMLRIah7ZfVYWIfRoG8?= =?us-ascii?Q?y8ZZIpup7Xgf7+AQGx+k1Duwcg+TMcxASjqhUq/bs5LPmw82gOG2CbT8Audc?= =?us-ascii?Q?RtQh4PBLtIYwlrNDd4VZrVg4kW/oqD55irn3jaH3HeiFGdk+wwPBH97YRuQK?= =?us-ascii?Q?RG4jwGymNIgewxe+V0I0faG1decZ1nyJWgoZlzzgA2ch7Uah4v3ywxHhsn7f?= =?us-ascii?Q?Y9w3JNTKh796D6WpdOM2XAE6qwEDeUqDOLcdu+kUtW5WcR6sXSjI+wLKz393?= =?us-ascii?Q?bgHHTWbBKluUA5lLEhWRjo2Gjifgg56Rp4n9vLQaii8EzHXaYxbMIlSmfruM?= =?us-ascii?Q?wNtBqym06jxmQBRr3sXhRoVHGkTHpyjmNjSUnHEuVB59+NkC+DwaVICyrIxs?= =?us-ascii?Q?rOtDdL7bdzFboNMUL7eBceramBnmhycnKJ1jvG0bK5L1O7NQBedWcVpvqOfH?= =?us-ascii?Q?fS37qDg9c1a9sY/C5uQpJSYHfkXZ0LpzfzxukHIh6Vu2dkEaemTGs5HPdqHi?= =?us-ascii?Q?tZL00fw5/rvlcVAQXxgX++yP7tRvZBknUcPeXv9321Wc1PcbLO7uuvf457+G?= =?us-ascii?Q?lgmG5ubJia6SI7rSv7imuih6w3acYiv1dfk8Kj6wrjmy5q56tnNHWoOdLf/J?= =?us-ascii?Q?9jqVr0IR2j0VVZNyExD1k8ian6ytjvkuZkyctvVlbspQJGNnj1SPsXFkMse5?= =?us-ascii?Q?M2tFKGTOCUUa4Ci+PXYZkLEiYfpKZ5gjhQ9JNRo89dd7PXg+pPWDS2tqc64w?= =?us-ascii?Q?7iVVrhbqdixCp84rPDuKaVwwg09muJIhNtYpN4sRlJzeJpo4fLg5kcEHG+gz?= =?us-ascii?Q?x+wINhsd1nnpQRQ9bCk6s/Jettrt4j59+qC2E8mF9YcW6Y+eoUAaqsndSQ05?= =?us-ascii?Q?siFd0i2pUVuzDDcjSApUDMNKhil7HiTKnSVJqS9oNwb4BGQr7x0NovjlSPgB?= =?us-ascii?Q?xA7W76FYVP/UlN/E6K2Pj3dq/CX2SvaVKzDdoTgMq1xHLkbrngBzI8eeCb5/?= =?us-ascii?Q?iWuar9dsZurHrsw9qMW/EASDhs5NwjnwYUBeiYV/bxzHL8bEprwGOraC/edI?= =?us-ascii?Q?2XzglRvgJDaCA3/tN/ctgR4/OBboLxH2FVL9XWj23WxP4teGx+xZYEI3iH1t?= =?us-ascii?Q?ZyN5mDMFy8cOUAQB6Bw4zU=3D?= X-Microsoft-Antispam-Message-Info: 93iaAYsylXzc4n4nweVcVv1pJ0T1eEPYuRKGddWrq32skmAqA/m5FPTm6+VREPwE25dNAVkcK4SboCHQwB1iOp1dGYcBHKxp3li0pi5TGhKIqQlidPLgdImAyzxUgEbLrvArBN5KdxOjC7b1AZTFJw2pIf4OX1/1bpq8bKC+2sgcn52+iFCwli+WDlzq9+jM4HFaMzAzNvLUWcPYJgVD+K7ZLoOg2Ha1zuvoxCOpip4ap7y9kBeUI7448yCEwf21rgAp0XV9Us+xfMeGlZlF9BYF8hIP4Zcw/suS/YZhkzJ+llm7a+82ds4ZSL9q2yEocolyeDFnPCuJ1TYWZpbvNwfJBfTkD5kjLC40BZ1pz4c= X-Microsoft-Exchange-Diagnostics: 1; BN7PR07MB5380; 6:ttuDgys3DJJF1+StCXG1YiANcw96s1GL7V44LjhJhqyRTdZzJIKAm33RZ6hJHNP6Qf1IPQJeFKVzjbtH2olVpG383mRTWdKqi3tX547iKW8JRhh3F2y1PdjGSj8NN+bd4WBRMycH1IAtw6fIIfwm0swqrHykyti6Rde8Cn57hN6h2TBjbFN8if/HJ35ffpk3Vl308FJrMuepde4P02hthENhSzkVQ7p96jK0wJw+CuV4ncvw/W5PW1AueqMdRu4zhaKBIX+cJZww7tqpbUHAaNUkOkU5/GwR7nhpWC6pvuq8ldBYQ8jXbPhmT6idFQHe9WlW/7k0GsDNiJCzdQ+KiAfeAf61CkaPnxrTvjrQ41DtI7Yk+nwTX+TsGRDbuEib4npjU/9Vw6E8d/pzeBptQm0bK0gVq7qM4bN/Qx0XJcKmQnd2zZELpuw9Bq0d9QMfVYndwVeQRjh8ohsrYNRCrg==; 5:lp70gT09Vu/4U+tD7cTrEVm/OhUV2+Yrvc01W8dmfkS1oxC0vepT2G8Hnkt5OGEXqv50g0vLwi/p7LXBtpfTVs8Z5XhSrje4m3WVGVf3oCYgSKcKtHTncmCxknzPuXpQ+RXXCn1BHVc5D+FhS+RT4Eh9FO73fV0v0YphFGRrItw=; 7:bLfysjy10bxhgUQsodWqvC6kf4kjbiuQVYoIpwumX5joqfQDEzs5Z39ybeXnQJwK1yKh1XGStXt1Qx0yfY3hqgAwA152Wr7RC5ZeyDmSuIWZC0sD6vAdIw2VnY5jMb38wDpr3N4nxJU946WyH5MaTphgf8cdhGlPhkATPSgaT1Eo39WCEUiSDhgasKlghYZDLecK3Nrw7YbYBbMZqgBFoiwdiSS0zZv1h+EeYoAOg3dMxf7WTkNoSHRKzXZkS6vD SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: caviumnetworks.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Oct 2018 07:55:20.0533 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 982d8df9-6f02-46c4-ec94-08d62dbc900e X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 711e4ccf-2e9b-4bcf-a551-4094005b6194 X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN7PR07MB5380 Subject: [dpdk-dev] [PATCH 1/2] eal/bitmap: support bitmap reverse scanning X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 09 Oct 2018 07:55:23 -0000 Currently bitmap supports only forward scanning starting from zero bit position. This patch implements reverse scanning starting from highest bit position towards zero bit position. Signed-off-by: Vivek Sharma --- Prerequisite: * Note that this patchset is dependent on patch: 'http://patches.dpdk.org/patch/45307/' lib/librte_eal/common/include/rte_bitmap.h | 164 +++++++++++++++++++++++++---- 1 file changed, 143 insertions(+), 21 deletions(-) diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h index 7a36ce7..4b3437e 100644 --- a/lib/librte_eal/common/include/rte_bitmap.h +++ b/lib/librte_eal/common/include/rte_bitmap.h @@ -61,6 +61,11 @@ extern "C" { #define RTE_BITMAP_CL_SLAB_SIZE_LOG2 (RTE_BITMAP_CL_BIT_SIZE_LOG2 - RTE_BITMAP_SLAB_BIT_SIZE_LOG2) #define RTE_BITMAP_CL_SLAB_MASK (RTE_BITMAP_CL_SLAB_SIZE - 1) +enum rte_scan_dir { + RTE_BITMAP_REV_SCAN = -1, + RTE_BITMAP_FWD_SCAN = 1 +}; + /** Bitmap data structure */ struct rte_bitmap { /* Context for array1 and array2 */ @@ -74,6 +79,7 @@ struct rte_bitmap { uint32_t offset1; /**< Bitmap scan: Offset of current bit within current array1 slab */ uint32_t index2; /**< Bitmap scan: Index of current array2 slab */ uint32_t go2; /**< Bitmap scan: Go/stop condition for current array2 cache line */ + enum rte_scan_dir dir; /**< Bitmap scan: Current scan direction */ /* Storage space for array1 and array2 */ uint8_t memory[]; @@ -82,13 +88,16 @@ struct rte_bitmap { static inline void __rte_bitmap_index1_inc(struct rte_bitmap *bmp) { - bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1); + bmp->index1 = (bmp->index1 + bmp->dir) & (bmp->array1_size - 1); } static inline uint64_t __rte_bitmap_mask1_get(struct rte_bitmap *bmp) { - return (~1llu) << bmp->offset1; + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + return (~1llu) << bmp->offset1; + else + return (~0llu) ^ ((~0llu) << bmp->offset1); } static inline void @@ -110,6 +119,16 @@ rte_bsf64(uint64_t slab, uint32_t *pos) return 1; } +static inline int +rte_bsl64(uint64_t slab, uint32_t *pos) +{ + if (likely(!slab)) + return 0; + + *pos = RTE_BITMAP_SLAB_BIT_SIZE - 1 - __builtin_clzll(slab); + return 1; +} + #else static inline int @@ -132,6 +151,25 @@ rte_bsf64(uint64_t slab, uint32_t *pos) return 0; } +static inline int +rte_bsl64(uint64_t slab, uint32_t *pos) +{ + uint64_t mask; + int i; + + if (likely(!slab)) + return 0; + + for (i = RTE_BITMAP_SLAB_BIT_SIZE - 1, mask = 1; i >= 0; i--) { + if (unlikely(slab & (mask << i))) { + *pos = i; + return 1; + } + } + + return 0; +} + #endif static inline uint32_t @@ -167,16 +205,29 @@ __rte_bitmap_get_memory_footprint(uint32_t n_bits, } static inline void -__rte_bitmap_scan_init(struct rte_bitmap *bmp) +__rte_bitmap_scan_init_generic(struct rte_bitmap *bmp, enum rte_scan_dir dir) { - bmp->index1 = bmp->array1_size - 1; - bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; - __rte_bitmap_index2_set(bmp); - bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE; - + if (dir == RTE_BITMAP_FWD_SCAN) { + bmp->index1 = bmp->array1_size - 1; + bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; + __rte_bitmap_index2_set(bmp); + bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE; + bmp->dir = RTE_BITMAP_FWD_SCAN; + } else { + bmp->index1 = 0; + bmp->offset1 = 0; + bmp->index2 = 0; + bmp->dir = RTE_BITMAP_REV_SCAN; + } bmp->go2 = 0; } +static inline void +__rte_bitmap_scan_init(struct rte_bitmap *bmp) +{ + __rte_bitmap_scan_init_generic(bmp, RTE_BITMAP_FWD_SCAN); +} + /** * Bitmap memory footprint calculation * @@ -439,19 +490,32 @@ __rte_bitmap_scan_search(struct rte_bitmap *bmp) value1 = bmp->array1[bmp->index1]; value1 &= __rte_bitmap_mask1_get(bmp); - if (rte_bsf64(value1, &bmp->offset1)) { - return 1; + if (bmp->dir == RTE_BITMAP_FWD_SCAN) { + if (rte_bsf64(value1, &bmp->offset1)) + return 1; + } else { + if (rte_bsl64(value1, &bmp->offset1)) + return 1; } __rte_bitmap_index1_inc(bmp); - bmp->offset1 = 0; + + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + bmp->offset1 = 0; + else + bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; /* Look for another array1 slab */ - for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) { + for (i = 0; i < bmp->array1_size; + i++, __rte_bitmap_index1_inc(bmp)) { value1 = bmp->array1[bmp->index1]; - if (rte_bsf64(value1, &bmp->offset1)) { - return 1; + if (bmp->dir == RTE_BITMAP_FWD_SCAN) { + if (rte_bsf64(value1, &bmp->offset1)) + return 1; + } else { + if (rte_bsl64(value1, &bmp->offset1)) + return 1; } } @@ -462,8 +526,12 @@ static inline void __rte_bitmap_scan_read_init(struct rte_bitmap *bmp) { __rte_bitmap_index2_set(bmp); + + if (bmp->dir == RTE_BITMAP_REV_SCAN) + bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE - 1; + bmp->go2 = 1; - rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8)); + rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8 * bmp->dir)); } static inline int @@ -472,23 +540,42 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) uint64_t *slab2; slab2 = bmp->array2 + bmp->index2; - for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) { + + for ( ; bmp->go2; ) { if (*slab2) { *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2; *slab = *slab2; - bmp->index2 ++; - slab2 ++; - bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + bmp->index2 += bmp->dir; + slab2 += bmp->dir; + + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + bmp->go2 = + bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + else + /* stop once index2 crosses zero while + * decreasing. + */ + bmp->go2 = (bmp->index2 ^ (~0)); return 1; } + + bmp->index2 += bmp->dir; + slab2 += bmp->dir; + + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + else + bmp->go2 = (bmp->index2 ^ (~0)); + + bmp->index2 &= RTE_BITMAP_CL_SLAB_MASK; } return 0; } /** - * Bitmap scan (with automatic wrap-around) + * Bitmap scan generic (with automatic wrap-around) * * @param bmp * Handle to bitmap instance @@ -504,12 +591,20 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) * after this slab, so the same slab will not be returned again if it * contains more than one bit which is set. When function call returns 0, * slab is not modified. + * @param dir + * Scanning direction, whether in forward/positive(increasing bit index) + * or reverse/backward/negative(decreasing bit index) direction. * @return * 0 if there is no bit set in the bitmap, 1 otherwise */ static inline int -rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) +rte_bitmap_scan_generic(struct rte_bitmap *bmp, uint32_t *pos, + uint64_t *slab, enum rte_scan_dir dir) { + /* Init scan parameters as per requested scan direction */ + if (unlikely(bmp->dir != dir)) + __rte_bitmap_scan_init_generic(bmp, dir); + /* Return data from current array2 line if available */ if (__rte_bitmap_scan_read(bmp, pos, slab)) { return 1; @@ -526,6 +621,33 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) return 0; } +/** + * Bitmap scan (with automatic wrap-around) + * + * @param bmp + * Handle to bitmap instance + * @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. Slabs are always 64-bit + * aligned, so the position of the first bit of the slab (this bit is not + * necessarily set) is pos / 64. Once a slab has been returned by the bitmap + * scan operation, the internal pointers of the bitmap are updated to point + * after this slab, so the same slab will not be returned again if it + * contains more than one bit which is set. When function call returns 0, + * slab is not modified. + * @return + * 0 if there is no bit set in the bitmap, 1 otherwise + */ +static inline int +rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, + uint64_t *slab) +{ + return rte_bitmap_scan_generic(bmp, pos, slab, RTE_BITMAP_FWD_SCAN); +} + #ifdef __cplusplus } #endif -- 2.7.4