From patchwork Tue Oct 9 07:54:58 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vivek Sharma X-Patchwork-Id: 46315 X-Patchwork-Delegate: cristian.dumitrescu@intel.com Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 10CE85F4D; Tue, 9 Oct 2018 09:55:25 +0200 (CEST) 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 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+?= qTl1YeIZ+Bcim7Y0n3vMPbsXF6MB8tf/i0hht/e6RsAgoTeCFGKFJXe37jR1UtqYJp4p1C1R71tkBM2S2+lFdjsrCD4baWtgATEyzMtGVd9h8p3VarSGyg+MI8zaMR4Uzc2gYBlyubRq494ST6J0oQFK9m8iR7vOKeMLRIah7ZfVYWIfRoG8y8ZZIpup7Xgf7+AQGx+k1Duwcg+TMcxASjqhUq/bs5LPmw82gOG2CbT8AudcRtQh4PBLtIYwlrNDd4VZrVg4kW/oqD55irn3jaH3HeiFGdk+wwPBH97YRuQKRG4jwGymNIgewxe+V0I0faG1decZ1nyJWgoZlzzgA2ch7Uah4v3ywxHhsn7fY9w3JNTKh796D6WpdOM2XAE6qwEDeUqDOLcdu+kUtW5WcR6sXSjI+wLKz393bgHHTWbBKluUA5lLEhWRjo2Gjifgg56Rp4n9vLQaii8EzHXaYxbMIlSmfruMwNtBqym06jxmQBRr3sXhRoVHGkTHpyjmNjSUnHEuVB59+NkC+DwaVICyrIxsrOtDdL7bdzFboNMUL7eBceramBnmhycnKJ1jvG0bK5L1O7NQBedWcVpvqOfHfS37qDg9c1a9sY/C5uQpJSYHfkXZ0LpzfzxukHIh6Vu2dkEaemTGs5HPdqHitZL00fw5/rvlcVAQXxgX++yP7tRvZBknUcPeXv9321Wc1PcbLO7uuvf457+GlgmG5ubJia6SI7rSv7imuih6w3acYiv1dfk8Kj6wrjmy5q56tnNHWoOdLf/J9jqVr0IR2j0VVZNyExD1k8ian6ytjvkuZkyctvVlbspQJGNnj1SPsXFkMse5M2tFKGTOCUUa4Ci+PXYZkLEiYfpKZ5gjhQ9JNRo89dd7PXg+pPWDS2tqc64w7iVVrhbqdixCp84rPDuKaVwwg09muJIhNtYpN4sRlJzeJpo4fLg5kcEHG+gzx+wINhsd1nnpQRQ9bCk6s/Jettrt4j59+qC2E8mF9YcW6Y+eoUAaqsndSQ05siFd0i2pUVuzDDcjSApUDMNKhil7HiTKnSVJqS9oNwb4BGQr7x0NovjlSPgBxA7W76FYVP/UlN/E6K2Pj3dq/CX2SvaVKzDdoTgMq1xHLkbrngBzI8eeCb5/iWuar9dsZurHrsw9qMW/EASDhs5NwjnwYUBeiYV/bxzHL8bEprwGOraC/edI2XzglRvgJDaCA3/tN/ctgR4/OBboLxH2FVL9XWj23WxP4teGx+xZYEI3iH1tZyN5mDMFy8cOUAQB6Bw4zU= 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 From patchwork Tue Oct 9 07:54:59 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vivek Sharma X-Patchwork-Id: 46316 X-Patchwork-Delegate: cristian.dumitrescu@intel.com Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id A8256683E; Tue, 9 Oct 2018 09:55:26 +0200 (CEST) Received: from NAM01-SN1-obe.outbound.protection.outlook.com (mail-sn1nam01on0055.outbound.protection.outlook.com [104.47.32.55]) by dpdk.org (Postfix) with ESMTP id 22AF45F32 for ; Tue, 9 Oct 2018 09:55:24 +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=LnRdpIXJ9OiSEHd7HYuMxcdOMs+5cJ/vAMN3GQzCS60=; b=CWuWs818tQdR6zK8vYkmoe5GDhnczukpgHpzJ7cGozjmMj9dtr2vE4ZMgOEYhiTVNSWXVChOgK/4gB9ht3ZIS/5/GzL8u0eaohQKyeRtCpDxOwGHXaVZvuRDFpuwQyAsAH631H/RkdplXU3ho3O95K4YjIA7XCkfDi1qWmkq1FY= 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:21 +0000 From: Vivek Sharma To: dev@dpdk.org Cc: cristian.dumitrescu@intel.com, Vivek Sharma Date: Tue, 9 Oct 2018 13:24:59 +0530 Message-Id: <1539071699-29963-3-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 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: 70364575-68a4-40a1-a74b-08d62dbc912a 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:QjEOJIUDwDRuc+N6TSStkvHSdBBV9/WH5dxvlRblEpX/PzS4vGPgiuMNlcK0+QdVsaQY5fHVE21q5RE6rUwZL5/oPDCti2q9ExTlFBZOnvjLlYVZTxXsAMhm1ttuRDWlJNBImSNJwKAhfX/jrVLUqXUv5YMz4+UVFxRc1zBLcZFdT9RcEigeTvp+HPLCx/MtnWwaNPdn+UBfwJAgb99MdkF+bJ+WDIv6cPD4DdctSXqwgTDVupJv5S1oP0Alz4Gj; 25:Xf70ew+EtRE/v2a+nbM/4+h/3Veb/xd+3kZ5PcNJhU0CeUN2XXhf3oylpZwJ8M0Zlcjw9eZ3AssGfyEB3Hmb0ps+h+ZH5hO+5FVkpWKrb8WpxxLv8Pjr+OX33yk/m1+0Cid5aYF1BpFZIaaXpHh5Wnx7coZhDrApxQ+SixaG+iB2buISVemLUGk7MPVQ5O1X0XITfo3OyWIsgL2xE03wORLk+rbRLiyxxYLv4Ep8emPQIEDxa1EuBGSklBl02Itfodei+RDT92RVdJLDCp7a523+OKbThpOFMeouSZj9cIA1QfhLwri/Es8+HkIUR3bhNSgl9pKrNGHVFx0oVD7V/Q==; 31:1Z1mkFAN/qMRXX65VG2iPbjCEAveDN2Ri4r6HknVSNd1qf+DjJPLzzLd48QxciRDjb5uIu1tEdtsLVc3bmQCcGu6ZzgzpawNDLxOfDK9qm/YIyIzsv6v5pXRPcDw7HEiV6NQ3C3qt/kqns8kXjX5FBfTpUpvuY3RnvZigMmPrDatSm3fu22XupJlPpJMr2WscEnD5A6bLO5bolqqJS/ILAydYBKJS1KSbPfRiU+n1Bw= X-MS-TrafficTypeDiagnostic: BN7PR07MB5380: X-Microsoft-Exchange-Diagnostics: 1; BN7PR07MB5380; 20:/+QPtUfqHoj2JE5XUJfNfpC+eRgfWPp2Cu6rSg0xqzCE7uf1WLvOj5KdD33amFJa6UMUkqhmQbtZHz3apDfhFoHErnKzrS8GdCiaCl2x3jWOH/iFyvFrkr/29AnljTGSEn3pyG+Nq8YNTVVzgaFiIsLwj3ZcBuHLXIjGduisjGvUraLHrqm7uCXBpgfboSyfcfyeQbVbePAzzqdKzDOR367PaVi2k7QVW72NLkR7WZvbGcg5znaULWNY/P+t4vHKIQ9FnSPm3BciwTjObf7D1sKtjhx+b5g4D/yw/53aJeKWKnR9cM4K02GjpTlnmms+tdPBJFGCNvxqdy+GFUChU6k4YhVWUzWhd4uNqacAPKuZRwXElI78xBoVtVaM20sBg6DczuVGGd3guPj3gofJSs0VksKYWJ9Zxo1DQKZWcuTCXU2bcV6dif0Aq4sukNhfMK9aERrFcMEpKEannvZ1ib0cx1zCFVCOeMtCz5W60cf2glteL5/bIMZR0BXHAFaF/aJ+v+0NailHcbGKC3TIOI6Z7zUS/p4UYDbLeEDI2PF6eTYhNTm74l54uMJob5xeTJNrHfRjHwBtlYhx+BquQdE4Lrnvpegma/IttuwAY2g=; 4:9j9v9LRQbRvMvXMZ2jvpO7S8UFsWNUeTrdu+602KsdRoGezXmYSXJDLdAJYc0vDglIoqVzFCpFkLGtjXcis839MC98QPwAsmruX8FA6U4RcNIyvktLnuCz9YSiK5e77ttkIXplPlu/6zuQsxWxOEkwDjPpD+I10iy7XRT8hiIYP45WuRoTQzV3sAbMqljbwBMXvdoB5Px/KXNwP+LW7rvjT8Sh5mbL1kOA7wLFL7L0gl8VEa/p87Z9R70RKbnejlVXQC3kyVYypaNlyRCRvZMw== 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)(575784001)(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:n0GfIxcw7exQPW1sT5Pf3/bSaMlIAbb+KjcsfSCgQ?= NIj1lyJYgS5kiyRafvhKfITtP9xQVzR9oHKD/4hpjrO3+FbV43FJ9o1fa4RHcTp7iASXIa+oN40KDAGZqLeSl7pM8InHIMBvtNg2Bl/ekCPqHsrh3CDJi4o80zlyFSuDeUrlMh5fDXW9B85rYvEHF7hEacbOK1sqcL8eU2sYj5nScR+0xubDL5cVv3pkxxs/jvuhY0a8rpObwUAVD7Q+OTbyO96dlwD0FhnDOKX8qoQtcBaMlxRMoYimU2K8gPeZH6NJ2qmg/CPBFAzMH/JNMLKbowqyV+w1ui4NvhE4O1nTInIes09HH0sBBfbDQmu9CDT9az/iYgGLtf5AyRUP85e8yIQF9UgTCIldXLFHcABQgCs/Fr4rc9XLb4YuMDIah85XCttdO1+RzBalj8kjWF8msN0Fem9skYziWtbEs68KlcCsNhqh35ExgpCnHocCK5iNrJ25EFJbG67Q/iF7yZvHCCFyXmJvfNbbdyjvckJoPrXZjtMgy1fNcmL5P88j6xJFQC6CzcTFWiTi6cqcmINnmeJL2k5sgRkZCDDpjuRXOXOmcektkzduutoGYbI1s7wwGB9s9IpOjB2a0eX/FmiAv3Zb2i0Q8zdWNEK6TicDgnSuxFZG0AutAu3TZ6I5Vejslw5rDtjjAVSCFSnWiz7V3qPZjG11/5mzYVMAiF9GGjBKWT3K6QUfB+HQioC5Ykvt/j9RMEY3BLhD8VEbsmrEcOdyNpgiaPWll9s7fV4jGJ17VBnpdLeclLXQQOjAoFoX/fxhcXPVOu7DQO/dXjxf9IcZ3w4Yb5JHCXR4+3U7shC/7K2cBAWJQ7NYkRiV9LNbV86lP+ZqSnezCDtTiNB+MmsDre1Mwl3kuSfNDRIQAegSn3NkTO+02/YRCyYGuQ1MQPg2yARnBcJxTmsRnfP7N0QWFsfJKIreo8EKm3w/kkMWXFaXPgSsvpzJFaaTye/jOKq0qoN7dwSM9101AvcXSbxGNfzZ2IHiEGpbBiutT9845VCKbwX93V9YmqcqKmEqsD3o7PRH/FR2sWlSB4MzlX0/hbwHmOUhYmHbjr6fC67LRKCfi9eIMDeGDlmKwGGHeat8tiCDQIB+E6jtPd9tmvOIc0F/7GIVTgN8WvJqZYWBf6Ag85kchP8vJvg48zn8oij01N7ELBZ9ml8P/xRAejeTTPjpAQNjnqXmPYoIf0Fx9LwbQURpsRxdGlVT0ZzAKIBt59Ek+rjGa98IlhOqoodPOHV0XBsF8su9xg4X4VDT4wylQXQxOGT+x4wfubRSWPVtV5ETlheElbk6BAv X-Microsoft-Antispam-Message-Info: vUla+r2qtzsO3VQ4/ksj08zavNreDVCShE53l5xWJjKYCgBESsY/sqFxGcNuyokZoJ5E6KyOIygODNEtW4GtctiwLUYf4HBwBeSfHnc+EEQ+SUN81DYG+aBHxOTFwD0bXq6gNbORnMvF9voiRA1w0LlkLW+mgs4NAAU6zmZoRe8HNfSd1oCA9y6GhzaGWy33QpywJliUntYBK3mtlUhV5CBYzG8/xX+lQIvNrV2QIrKJbSQyaebZ09vZka1YPfo8eLuFLL06oWz5Gw6MdDig6/Mlw1z5KHLyJRiM1aDGGjXPXiQ/ZCwORalzTpox8ILoRNG0KtugGx44RyV+1B4ma1mFBwIGwCz26tvQFxzc+JU= X-Microsoft-Exchange-Diagnostics: 1; BN7PR07MB5380; 6:2YyQ4+lE8/TZu8RSwVdL/4IFP4I3fqfHmfJMeYBIcLss20IDJZLPHoVV76pXjLisGvsn49wCM5PlnTsncXJmyDRsJOakXIItrQf7THv7Dx4CueQyANbCPUIB9jz38NmdsFTHc6YDNV8PvrVRt0n43KOob2Ry+fbpWeUhrcTUmAGksp0WybFsQTvs69j1EqbHDfCu2kUyfl49O1HwtN3S6YUczLnc7Jw3yOXFx4GacQD4nChfXg/yI3FvLde+jC8VLU+LImfLBmbPavwkAZAuVN/EsVx13hqNTG7g+arqP++yV6hWB0I7gpA1ArhADAYi+x2Lx8A5ea3Kkqq+zzkkxukMjlbfJ7UQhbyl8eQyuna3vGvS4gf5z1TlHGSXWfUJj8qnHjPV5HZrWu6uwCIYtiVFxQxbU6CvFLsdcq3LvxJLCxoUyibRMAbx1cn/EIjR2kQTv3KL1hsH/pFo2xNf9A==; 5:zhRs9rLQ+/fkfDA+h8BrFPP4hpHibGGDlJoiYPcKtvySq8lRqQLAwMaGVqC15aHbyWsSvYxtYeG4gvnY8u1yx7hvMwgplmstwAcNHs9S8pBOpHudCq1QQiMQnZimQBNYDlbFdF7KLl6qATh6TewDzjze0YA+rg/zN2RUcF0wRfM=; 7:hWgYjToExHkNt4kTb018l2yRz01eWBT7/tZmCp82FZsHUzzG0ac0jnoXAPMdP+BggMOBG8cnMBYYxZvitO6+m49FMsqHGisJPu7MVAx65PLTCNqQmYKVYW2hNrqt+NSYZwsFTc+5okNXO8I3dN1ZNKxfQd1ytznReRYTrCA51ogbLiyPHnMhglSCc9dYJJWDN5yMngogif+lYmUk5ZLl6zpdGJm56bt3R6x18JLDmyWLzSjN6G8Ai92PG8Sh1c4V SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: caviumnetworks.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Oct 2018 07:55:21.8815 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 70364575-68a4-40a1-a74b-08d62dbc912a 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 2/2] test/bitmap: implement reverse bitmap scan test 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" This patch implements support for testing bitmap reverse scan. Bits in bitmap are changed to be an exact multiple of slab size. Signed-off-by: Vivek Sharma --- Prerequisite: * Note that this patchset is dependent on patch: 'http://patches.dpdk.org/patch/45307/' test/test/test_bitmap.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 70 insertions(+), 1 deletion(-) diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c index 95c5184..21a193b 100644 --- a/test/test/test_bitmap.c +++ b/test/test/test_bitmap.c @@ -11,7 +11,7 @@ #include "test.h" -#define MAX_BITS 1000 +#define MAX_BITS 1024 static int test_bitmap_scan_operations(struct rte_bitmap *bmp) @@ -74,6 +74,72 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) } static int +test_bitmap_scan_reverse_operations(struct rte_bitmap *bmp) +{ + uint32_t pos = 0; + uint64_t slab1_magic = 0xBADC0FFEEBADF00D; + uint64_t slab2_magic = 0xFEEDDEADDEADF00D; + uint64_t out_slab = 0; + + rte_bitmap_reset(bmp); + + rte_bitmap_set_slab(bmp, MAX_BITS - RTE_BITMAP_SLAB_BIT_SIZE, + slab2_magic); + rte_bitmap_set_slab(bmp, MAX_BITS - (2 * RTE_BITMAP_SLAB_BIT_SIZE), + slab1_magic); + + if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab, + RTE_BITMAP_REV_SCAN)) { + printf("Failed to get slab from bitmap.\n"); + return TEST_FAILED; + } + + if (slab2_magic != out_slab) { + printf("Scan operation sanity failed.\n"); + return TEST_FAILED; + } + + if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab, + RTE_BITMAP_REV_SCAN)) { + printf("Failed to get slab from bitmap.\n"); + return TEST_FAILED; + } + + if (slab1_magic != out_slab) { + printf("Scan operation sanity failed.\n"); + return TEST_FAILED; + } + + /* Wrap around */ + if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab, + RTE_BITMAP_REV_SCAN)) { + printf("Failed to get slab from bitmap.\n"); + return TEST_FAILED; + } + + if (slab2_magic != out_slab) { + printf("Scan operation wrap around failed.\n"); + return TEST_FAILED; + } + + /* Scan reset check. */ + __rte_bitmap_scan_init_generic(bmp, RTE_BITMAP_REV_SCAN); + + if (!rte_bitmap_scan_generic(bmp, &pos, &out_slab, + RTE_BITMAP_REV_SCAN)) { + printf("Failed to get slab from bitmap.\n"); + return TEST_FAILED; + } + + if (slab2_magic != out_slab) { + printf("Scan reset operation failed.\n"); + return TEST_FAILED; + } + + return TEST_SUCCESS; +} + +static int test_bitmap_slab_set_get(struct rte_bitmap *bmp) { uint32_t pos = 0; @@ -176,6 +242,9 @@ test_bitmap(void) if (test_bitmap_scan_operations(bmp) < 0) return TEST_FAILED; + if (test_bitmap_scan_reverse_operations(bmp) < 0) + return TEST_FAILED; + rte_bitmap_free(bmp); rte_free(mem);