From patchwork Mon Feb 28 08:48:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yishai Hadas X-Patchwork-Id: 12762564 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2D0C5C433F5 for ; Mon, 28 Feb 2022 08:49:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234074AbiB1IuD (ORCPT ); Mon, 28 Feb 2022 03:50:03 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60386 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234073AbiB1IuB (ORCPT ); Mon, 28 Feb 2022 03:50:01 -0500 Received: from NAM12-DM6-obe.outbound.protection.outlook.com (mail-dm6nam12on2063.outbound.protection.outlook.com [40.107.243.63]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EE5D836E16 for ; Mon, 28 Feb 2022 00:49:09 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=nkbFakF1d4yUgCPVi3lQl3eNtjvgiVlmSWV7t5HTEhzP/XMBh1f6s2d2Mkr7QGeXIio50CclTff4JaEUL7NSUeru+3boNsxix2PMmdSdENkBLnUUpv3kyOcEgHKo1BQGUIJsCfHQe6ZMH82bAClyI7I7aCHaMSxg18yWXQCBQzHp/4B7vy8fdFnwIlU8bHlQge9CTGROo68mnGVp8lVkVtBM9p4p+JC8ucESRTzhQgQ6BpVUYa76LcXsUsSNV9e5qmbN/1qZX1JNe2p3zmSSsZ5YicFwlKcb9/+CRzMehI7TNp9VoEM2+P3eD0i4ywb8UzqLexxpXFYG7eG66bCGPA== 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=aRiN0joKavkHRGNddfgERd6WKP7A9+TrcRfQu6Dk2tg=; b=JdDtEyfw4DelRh4r/gRPCQW1n594gJ7ARFz9V6IvW6YWtNSM0Wf1NVga8/EVZAYTqYOG6CRG5C9lP/ijVS0W4PV1FXQT3BfyX7Yjyh5EGDCffW/P8AlU2gAlO98rmlJxb+Z5d/TuytzVkh1tHHo0iR3JIbYVd3vyZvt6L6je7gUGg1Rh+TR1aBLlSY0dQnz2n9NAJpzx3UdUOIK9a8525RLNFRZkYrDsOvv8njH7shPROXc0mnVMQsfPQmk1xdaUhMOwhsg5ZzQE5uCXdQIv19xokpA52XrAFnAWXK1HVEqvK2uFrs19tmCTTIlEUHPx3Sd5Fg6iy+qjSya9LAdcXw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 12.22.5.238) smtp.rcpttodomain=huawei.com smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=aRiN0joKavkHRGNddfgERd6WKP7A9+TrcRfQu6Dk2tg=; b=tn6RJllzXoE8jgnp8R5qLQiEnDZBz9REdxx8VV2BIItXCkiCmnWofMNCtBkMsGbnJtYc1q8PxHN++SvEzYjs9zUVJt0OA0ot4ma01qDe88/hjg4V+gwcX9grx+ub/hnWqSMWGoPBzZ5iwMOLcH8PhgfJS+LLCwdc/X3ueNsTi4boSYxhNaHs8nIBWsv3oNX39e6H2qWaZuJ+mMueqHCcvUIhHTiupnbc7MLoanFklsqKfGEfZBbSV8Rl4F9Jw/gpT3fPkAQj1+woyeWQcsKXTQCLDnX65rZSfXi3BLJmU1RoW5RxfpGNOLyu1GbWEwYm4ypp+v6MeeW0PfGRCkS6aQ== Received: from BN8PR12CA0013.namprd12.prod.outlook.com (2603:10b6:408:60::26) by CH2PR12MB3782.namprd12.prod.outlook.com (2603:10b6:610:23::28) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.26; Mon, 28 Feb 2022 08:49:07 +0000 Received: from BN8NAM11FT057.eop-nam11.prod.protection.outlook.com (2603:10b6:408:60:cafe::88) by BN8PR12CA0013.outlook.office365.com (2603:10b6:408:60::26) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.23 via Frontend Transport; Mon, 28 Feb 2022 08:49:07 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 12.22.5.238) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 12.22.5.238 as permitted sender) receiver=protection.outlook.com; client-ip=12.22.5.238; helo=mail.nvidia.com; Received: from mail.nvidia.com (12.22.5.238) by BN8NAM11FT057.mail.protection.outlook.com (10.13.177.49) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.5017.22 via Frontend Transport; Mon, 28 Feb 2022 08:49:06 +0000 Received: from rnnvmail205.nvidia.com (10.129.68.10) by DRHQMAIL105.nvidia.com (10.27.9.14) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Mon, 28 Feb 2022 08:49:05 +0000 Received: from rnnvmail202.nvidia.com (10.129.68.7) by rnnvmail205.nvidia.com (10.129.68.10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.986.9; Mon, 28 Feb 2022 00:49:04 -0800 Received: from vdi.nvidia.com (10.127.8.10) by mail.nvidia.com (10.129.68.7) with Microsoft SMTP Server id 15.2.986.9 via Frontend Transport; Mon, 28 Feb 2022 00:49:02 -0800 From: Yishai Hadas To: CC: , , , , , Avihai Horon Subject: [PATCH rdma-core 1/5] util: Add new bitmap API Date: Mon, 28 Feb 2022 10:48:26 +0200 Message-ID: <20220228084830.96274-2-yishaih@nvidia.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20220228084830.96274-1-yishaih@nvidia.com> References: <20220228084830.96274-1-yishaih@nvidia.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 329abb35-534c-429b-20ba-08d9fa972de0 X-MS-TrafficTypeDiagnostic: CH2PR12MB3782:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 63Qb8FZ13r5HqgPVH1fJKUrMDGA1Whc3f+cBbxylidBLzcQ0eInB02umv8Y7wnRFQgxsHchjj1sIzLyL7oDyrTRxqTdWErsgD8JfAMQgCNqBP0y1wF+7jE7hwihL4S2w0Ty+Vty/k3B5w8L+skfnf0/s6xsK58wrCEXCkNCcdv+tO7jrZz8N9sIu2kwMvNbVRdZImkFoCVAhtBek1m1TRyA4RKl1mz7EgiQrl23IWYDlah5q6QKiyHvG2C89KCwQBF8otr/ZawHChvWqj70YTQrX2hQISBaKJdvU53CWzRgKoVo4+9fxQkEYdKQlWFqpakTLP4mWE5YmDRQnNfhGxZyWXkC1w71Ml4IB3/kWmI67DoXFuIpkzNwxpYOKYogekHfVuuPBVXNYo/YwGBEbYuQhYtEox1saWDBDP0rW/fZ7mPhjx/tHKagISRPvbXyCrqCGVSlBNPAOCGZ8VEWXGQeEeby/s6PqZdcH1bEC/Wm8ZK7NcDNm8mZg00npZczmstES+BwX+WcpWCagm2ElvOEcAOGO7zmJNljTzdYOysERXoKU1qEwxA6csl00ouymiLWYRj56qRgpf9x8IUoJZCvykTle40twTsH40VOC0S4aWiBYEhbwBbpM2bGBgW6Da7N65Iumpf8TBFcZP9Em3/sqb3+I2gFAN+/cTjlPlH80BGZjXR/8NK42+sG3lMuevpb8AS1kPxHT+Wa2gU07nQ== X-Forefront-Antispam-Report: CIP:12.22.5.238;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:mail.nvidia.com;PTR:InfoNoRecords;CAT:NONE;SFS:(13230001)(4636009)(40470700004)(36840700001)(46966006)(1076003)(8676002)(4326008)(2906002)(82310400004)(36860700001)(2616005)(7696005)(70206006)(70586007)(508600001)(86362001)(6666004)(8936002)(107886003)(40460700003)(81166007)(5660300002)(356005)(54906003)(6916009)(336012)(186003)(26005)(316002)(36756003)(426003)(47076005)(83380400001)(36900700001);DIR:OUT;SFP:1101; X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Feb 2022 08:49:06.3961 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 329abb35-534c-429b-20ba-08d9fa972de0 X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a;Ip=[12.22.5.238];Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: BN8NAM11FT057.eop-nam11.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH2PR12MB3782 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org From: Maher Sanalla Adds new bitmap implementation to util directory, which replaces the ccan equivalent, due to the license used (LGPLv2+) which is not fitting in rdma-core. Signed-off-by: Maher Sanalla Reviewed-by: Avihai Horon Signed-off-by: Yishai Hadas --- providers/mlx5/bitmap.h | 2 - util/CMakeLists.txt | 2 + util/bitmap.c | 180 ++++++++++++++++++++++++++++++++++++++++++++++++ util/bitmap.h | 120 ++++++++++++++++++++++++++++++++ util/util.h | 1 + 5 files changed, 303 insertions(+), 2 deletions(-) create mode 100644 util/bitmap.c create mode 100644 util/bitmap.h diff --git a/providers/mlx5/bitmap.h b/providers/mlx5/bitmap.h index 034fb98..b2c8a36 100644 --- a/providers/mlx5/bitmap.h +++ b/providers/mlx5/bitmap.h @@ -54,8 +54,6 @@ #define MLX5_SHMAT_FLAGS 0 #endif -#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG) - #ifndef HPAGE_SIZE #define HPAGE_SIZE (2UL * 1024 * 1024) #endif diff --git a/util/CMakeLists.txt b/util/CMakeLists.txt index d8a66be..58c77d5 100644 --- a/util/CMakeLists.txt +++ b/util/CMakeLists.txt @@ -1,4 +1,5 @@ publish_internal_headers(util + bitmap.h cl_qmap.h compiler.h interval_set.h @@ -9,6 +10,7 @@ publish_internal_headers(util ) set(C_FILES + bitmap.c cl_map.c interval_set.c node_name_map.c diff --git a/util/bitmap.c b/util/bitmap.c new file mode 100644 index 0000000..e5ed30e --- /dev/null +++ b/util/bitmap.c @@ -0,0 +1,180 @@ +/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */ + +#include "bitmap.h" + +#define BMP_WORD_INDEX(n) (BITS_TO_LONGS((n) + 1) - 1) +#define BMP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) +#define BMP_LAST_WORD_MASK(end) (~BMP_FIRST_WORD_MASK(end)) + +static unsigned long __word_ffs(const unsigned long *word) +{ + unsigned long i; + + for (i = 0; i < BITS_PER_LONG; i++) { + if (bitmap_test_bit(word, i)) + return i; + } + + return i; +} + +static unsigned long word_ffs(const unsigned long *word, + unsigned long bmp_index, unsigned long end) +{ + unsigned long set_bit; + + set_bit = __word_ffs(word); + set_bit += bmp_index * BITS_PER_LONG; + if (set_bit >= end) + return end; + + return set_bit; +} + +/* + * Finds the first set bit in the bitmap starting from + * 'start' bit until ('end'-1) bit. + * + * Returns the set bit index if found, otherwise returns 'end'. + */ +unsigned long bitmap_find_first_bit(const unsigned long *bmp, + unsigned long start, unsigned long end) +{ + unsigned long mask; + unsigned long first_word; + unsigned long curr_idx = BMP_WORD_INDEX(start); + unsigned long end_idx = BMP_WORD_INDEX(end); + + assert(start <= end); + + mask = BMP_FIRST_WORD_MASK(start); + + first_word = bmp[curr_idx] & mask; + if (first_word) + return word_ffs(&first_word, curr_idx, end); + + for (curr_idx++; curr_idx <= end_idx; curr_idx++) { + if (!bmp[curr_idx]) + continue; + + return word_ffs(&bmp[curr_idx], curr_idx, end); + } + + return end; +} + +/* + * Zeroes bitmap bits in the following range: [start,end-1] + */ +void bitmap_zero_region(unsigned long *bmp, unsigned long start, + unsigned long end) +{ + unsigned long start_mask; + unsigned long last_mask; + unsigned long curr_idx = BMP_WORD_INDEX(start); + unsigned long end_idx = BMP_WORD_INDEX(end); + + assert(start <= end); + + start_mask = BMP_FIRST_WORD_MASK(start); + last_mask = BMP_LAST_WORD_MASK(end); + + if (curr_idx == end_idx) { + bmp[curr_idx] &= ~(start_mask & last_mask); + return; + } + + bmp[curr_idx] &= ~start_mask; + + for (curr_idx++; curr_idx < end_idx; curr_idx++) + bmp[curr_idx] = 0; + + bmp[curr_idx] &= ~last_mask; +} + +/* + * Sets bitmap bits in the following range: [start,end-1] + */ +void bitmap_fill_region(unsigned long *bmp, unsigned long start, + unsigned long end) +{ + unsigned long start_mask; + unsigned long last_mask; + unsigned long curr_idx = BMP_WORD_INDEX(start); + unsigned long end_idx = BMP_WORD_INDEX(end); + + assert(start <= end); + + start_mask = BMP_FIRST_WORD_MASK(start); + last_mask = BMP_LAST_WORD_MASK(end); + + if (curr_idx == end_idx) { + bmp[curr_idx] |= (start_mask & last_mask); + return; + } + + bmp[curr_idx] |= start_mask; + + for (curr_idx++; curr_idx < end_idx; curr_idx++) + bmp[curr_idx] = ULONG_MAX; + + bmp[curr_idx] |= last_mask; +} + +/* + * Checks whether the contiguous region of region_size bits starting from + * start is free. + * + * Returns true if the said region is free, otherwise returns false. + */ +static bool bitmap_is_free_region(unsigned long *bmp, unsigned long start, + unsigned long region_size) +{ + unsigned long curr_idx; + unsigned long last_idx; + unsigned long last_mask; + unsigned long start_mask; + + curr_idx = BMP_WORD_INDEX(start); + start_mask = BMP_FIRST_WORD_MASK(start); + last_idx = BMP_WORD_INDEX(start + region_size); + last_mask = BMP_LAST_WORD_MASK(start + region_size); + + if (curr_idx == last_idx) + return !(bmp[curr_idx] & start_mask & last_mask); + + if (bmp[curr_idx] & start_mask) + return false; + + for (curr_idx++; curr_idx < last_idx; curr_idx++) { + if (bmp[curr_idx]) + return false; + } + + return !(bmp[curr_idx] & last_mask); +} + +/* + * Finds a contiguous region with the size of region_size + * in the bitmap that is not set. + * + * Returns first index of such region if found, + * otherwise returns nbits. + */ +unsigned long bitmap_find_free_region(unsigned long *bmp, + unsigned long nbits, + unsigned long region_size) +{ + unsigned long start; + + for (start = 0; start + region_size <= nbits; start++) { + if (bitmap_test_bit(bmp, start)) + continue; + + if (bitmap_is_free_region(bmp, start, region_size)) + return start; + } + + return nbits; +} + diff --git a/util/bitmap.h b/util/bitmap.h new file mode 100644 index 0000000..c48706a --- /dev/null +++ b/util/bitmap.h @@ -0,0 +1,120 @@ +/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */ + +#ifndef UTIL_BITMAP_H +#define UTIL_BITMAP_H + +#include +#include +#include +#include +#include + +#include "util.h" + +#define BMP_DECLARE(name, nbits) \ + unsigned long (name)[BITS_TO_LONGS((nbits))] + +unsigned long bitmap_find_first_bit(const unsigned long *bmp, + unsigned long start, unsigned long end); + +void bitmap_zero_region(unsigned long *bmp, unsigned long start, + unsigned long end); + +void bitmap_fill_region(unsigned long *bmp, unsigned long start, + unsigned long end); + +unsigned long bitmap_find_free_region(unsigned long *bmp, + unsigned long nbits, + unsigned long region_size); + +static inline void bitmap_fill(unsigned long *bmp, unsigned long nbits) +{ + unsigned long size = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + + memset(bmp, 0xff, size); +} + +static inline void bitmap_zero(unsigned long *bmp, unsigned long nbits) +{ + unsigned long size = BITS_TO_LONGS(nbits) * sizeof(unsigned long); + + memset(bmp, 0, size); +} + +static inline bool bitmap_empty(const unsigned long *bmp, unsigned long nbits) +{ + unsigned long i; + unsigned long mask = ULONG_MAX; + + assert(nbits); + + for (i = 0; i < BITS_TO_LONGS(nbits) - 1; i++) { + if (bmp[i] != 0) + return false; + } + + if (nbits % BITS_PER_LONG) + mask = (1UL << (nbits % BITS_PER_LONG)) - 1; + + return (bmp[i] & mask) ? false : true; +} + +static inline bool bitmap_full(const unsigned long *bmp, unsigned long nbits) +{ + unsigned long i; + unsigned long mask = ULONG_MAX; + + assert(nbits); + + for (i = 0; i < BITS_TO_LONGS(nbits) - 1; i++) { + if (bmp[i] != -1UL) + return false; + } + + if (nbits % BITS_PER_LONG) + mask = (1UL << (nbits % BITS_PER_LONG)) - 1; + + return ((bmp[i] & mask) ^ (mask)) ? false : true; +} + +static inline void bitmap_set_bit(unsigned long *bmp, unsigned long idx) +{ + bmp[(idx / BITS_PER_LONG)] |= (1UL << (idx % BITS_PER_LONG)); +} + +static inline void bitmap_clear_bit(unsigned long *bmp, unsigned long idx) +{ + bmp[(idx / BITS_PER_LONG)] &= ~(1UL << (idx % BITS_PER_LONG)); +} + +static inline bool bitmap_test_bit(const unsigned long *bmp, unsigned long idx) +{ + return !!(bmp[(idx / BITS_PER_LONG)] & + (1UL << (idx % BITS_PER_LONG))); +} + +static inline unsigned long *bitmap_alloc0(unsigned long size) +{ + unsigned long *bmp; + + bmp = calloc(BITS_TO_LONGS(size), sizeof(long)); + if (!bmp) + return NULL; + + return bmp; +} + +static inline unsigned long *bitmap_alloc1(unsigned long size) +{ + unsigned long *bmp; + + bmp = bitmap_alloc0(size); + if (!bmp) + return NULL; + + bitmap_fill(bmp, size); + + return bmp; +} + +#endif diff --git a/util/util.h b/util/util.h index f721b83..af03c42 100644 --- a/util/util.h +++ b/util/util.h @@ -28,6 +28,7 @@ static inline bool __good_snprintf(size_t len, int rc) #define BITS_PER_LONG (8 * sizeof(long)) #define BITS_PER_LONG_LONG (8 * sizeof(long long)) +#define BITS_TO_LONGS(nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) #define GENMASK(h, l) \ (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h)))) From patchwork Mon Feb 28 08:48:27 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yishai Hadas X-Patchwork-Id: 12762568 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 79639C433EF for ; Mon, 28 Feb 2022 08:49:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234076AbiB1IuH (ORCPT ); Mon, 28 Feb 2022 03:50:07 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33048 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231856AbiB1IuC (ORCPT ); Mon, 28 Feb 2022 03:50:02 -0500 Received: from NAM10-DM6-obe.outbound.protection.outlook.com (mail-dm6nam10on2073.outbound.protection.outlook.com [40.107.93.73]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C2945377F5 for ; Mon, 28 Feb 2022 00:49:12 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=DlCeSHLtmHRTujtD/3+HPpM97pZsHOqhTwwBuqWS0jlYdf2AzDpAPteX+6a1kjAxhIGmJrz5wQqhDo2y9fyb4yVz/VAeyObW3D/rR4SjHzDkZZ1+G6cSSSY7qtgViv08MW7h7bK2W1F+QLmNHKEMq+ypPOvrPPdYyWcuvXGA8R0I1nPHm+6ABBNY2AULodgbg+kLgrEopX825f7Ij/y3IXepVfc9sysLJp+f1fE7NmSozfp04Exvhn+RMREqzDpvInnfRu/4wX+2RW+qje2gGDnybDqe/jhUd+buoEJSEW5I6MsiS/7jNGXWL3EP9i3rz+p0ETr7smd+9VF3uRnaIQ== 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=N5vKTkV0XyDO439PVu105FquebGNlXL6Oo0E4CE0xds=; b=DctDtbrxoziwh4l0xo/B6RZtULeb5mDJJ/E4fjR6NNJy+Dfm2akd9RRjZgMjQxQOoadrnBSK3JZAqpN2TH7G8ejH06pXVDT5ZZpXKImHw46g2AENMLOuvHvQxWST7m5Jc7G4GEmnhbmRJ51AswOVhhvJNfL6CoYlDwvrLUMZX7VzdYMHvAvpi19A2xjV2undKKXHfb8gA9PTIsaeIhhfg94DZ/mGzgWu+uMoNI/ef9L7Wczy3fiQeIRLPLo88kBGjc1TsrY1vuF2tiIldCH7Xly7dYw1LFVxZomtYBSbW4CYRjqw96lVfo6RzM1yopBR2WmF5ajhhzpPCAmfdQg2pA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 12.22.5.234) smtp.rcpttodomain=huawei.com smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=N5vKTkV0XyDO439PVu105FquebGNlXL6Oo0E4CE0xds=; b=XPliktbhOmpbqYfC1ABy1LLpAnhT5sARAZ00hjimDcER4SlLX3q/43ILXF3VpBYJEYMwZ9Qll0PUzD6exxR/dW+X7646OkbaJ4lJzP9ipvYz2i0PTZv37op1pD+Qpj8xq5JoGgQLjydnaoxEzbWaNb5ctvvIM0IKvM2X3yvJCRgz7MME0dHYcjC6OOcatTTDbwCuKDCTicINC4rzYVQh4g2L3uchDNBFCl30Dm0YLqZYUZg+pmJRYFpk1ZFyaq8Niq50no0Qw5mGXzam7AOHgu2BsLI66rwXPobLp090uZHKH/qkPGY2VoUL2SHBgjuzk3UskGv1z18CnOgaXOifDQ== Received: from DM5PR11CA0023.namprd11.prod.outlook.com (2603:10b6:3:115::33) by BYAPR12MB2903.namprd12.prod.outlook.com (2603:10b6:a03:139::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.26; Mon, 28 Feb 2022 08:49:10 +0000 Received: from DM6NAM11FT027.eop-nam11.prod.protection.outlook.com (2603:10b6:3:115:cafe::17) by DM5PR11CA0023.outlook.office365.com (2603:10b6:3:115::33) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.21 via Frontend Transport; Mon, 28 Feb 2022 08:49:10 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 12.22.5.234) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 12.22.5.234 as permitted sender) receiver=protection.outlook.com; client-ip=12.22.5.234; helo=mail.nvidia.com; Received: from mail.nvidia.com (12.22.5.234) by DM6NAM11FT027.mail.protection.outlook.com (10.13.172.205) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.5017.22 via Frontend Transport; Mon, 28 Feb 2022 08:49:09 +0000 Received: from rnnvmail205.nvidia.com (10.129.68.10) by DRHQMAIL101.nvidia.com (10.27.9.10) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Mon, 28 Feb 2022 08:49:08 +0000 Received: from rnnvmail202.nvidia.com (10.129.68.7) by rnnvmail205.nvidia.com (10.129.68.10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.986.9; Mon, 28 Feb 2022 00:49:07 -0800 Received: from vdi.nvidia.com (10.127.8.10) by mail.nvidia.com (10.129.68.7) with Microsoft SMTP Server id 15.2.986.9 via Frontend Transport; Mon, 28 Feb 2022 00:49:05 -0800 From: Yishai Hadas To: CC: , , , , , Avihai Horon Subject: [PATCH rdma-core 2/5] mlx5: Adapt bitmap usage to use util API Date: Mon, 28 Feb 2022 10:48:27 +0200 Message-ID: <20220228084830.96274-3-yishaih@nvidia.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20220228084830.96274-1-yishaih@nvidia.com> References: <20220228084830.96274-1-yishaih@nvidia.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: f5ca8fe1-ed6a-46bc-f2c1-08d9fa972fc8 X-MS-TrafficTypeDiagnostic: BYAPR12MB2903:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: Hd0V+MNa362P1cVkNTwzjc2v/0nxL0rkxTbtOAuN/oI0nmjusxLOGGpuVYCFC0piiwBH+0yrbsX6HXS+ijpXxuJIYjCTh91Ihc2gWi/rd0GFlkMdXll8hFxjzxD3GaTNQvrOxLbqahLi1Zt24m7IVXNCPA8ojgy1yAeol02ZNiN2kiJYRzxT5fsaCO2+BPRXC0wzviyPboWu4QuUH3NaBDz5Yxk+lZUSa6Aqv2wZxgQ5WSMW8ov4KnrAAFPCpCWbNXR7Iq5sbs6lia+Eo6Oo+M0i6gAevSilKDt/dtxIioNAmo7iFGcoCpiExqJ7sP4lwun4Gf5OoXE7P0Jxq/H/AHK7ESRP9vuuCi8mry9/jB/jLdNkuH4OyWcyMgqln+dJy3YpVnNxjarlw2b8JEoYXdU0Fw/UdViTECWPb3csDMQUfM3hcp9gPU+8IklakL+KOQnADBYhX3OOU4yFXlQVjBDSgx1G/DFwCsF5rMnMEfrhy7RCtyAwBhE0VLQcyKgo7r7HnWb1aBY2ntQcCf/MYOJQiZcaNA+HHCssJKV4ODylaOrRH96vizijILoOUn5xLda0pU/jjlcmgPo2ah9CtGdfb7ISQAllBlqn2g821RaArfq/Lk3dHBKqTEQ3ybvjEdUgTdgdLQS8uzVfCmElsBv2qkvTHOkaMgbg9AZ8RUSbb9aquFQFEns4LtLLGJmyvJBobYgf8w/zAhX9rzVp7tULTH50kXk3AnzcgRdCNbr686w5dCFZcPEzSMShQcSR X-Forefront-Antispam-Report: CIP:12.22.5.234;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:mail.nvidia.com;PTR:InfoNoRecords;CAT:NONE;SFS:(13230001)(4636009)(40470700004)(36840700001)(46966006)(36756003)(8936002)(54906003)(5660300002)(508600001)(6916009)(2616005)(47076005)(316002)(6666004)(30864003)(4326008)(8676002)(70586007)(70206006)(7696005)(336012)(2906002)(186003)(83380400001)(426003)(1076003)(107886003)(82310400004)(86362001)(40460700003)(36860700001)(356005)(81166007)(26005)(461764006)(36900700001);DIR:OUT;SFP:1101; X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Feb 2022 08:49:09.6621 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: f5ca8fe1-ed6a-46bc-f2c1-08d9fa972fc8 X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a;Ip=[12.22.5.234];Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: DM6NAM11FT027.eop-nam11.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR12MB2903 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org From: Maher Sanalla Replace the usage of ccan bitmap with the newly added bitmap implementation in util. As part of it, remove mlx5 bitmap API. Signed-off-by: Maher Sanalla Reviewed-by: Avihai Horon Signed-off-by: Yishai Hadas --- providers/mlx5/bitmap.h | 109 -------------------------- providers/mlx5/buf.c | 187 +++++++++------------------------------------ providers/mlx5/dr_buddy.c | 12 +-- providers/mlx5/mlx5.h | 17 +---- providers/mlx5/mlx5_vfio.c | 3 +- providers/mlx5/mlx5_vfio.h | 2 +- providers/mlx5/mlx5dv_dr.h | 6 +- 7 files changed, 53 insertions(+), 283 deletions(-) delete mode 100644 providers/mlx5/bitmap.h diff --git a/providers/mlx5/bitmap.h b/providers/mlx5/bitmap.h deleted file mode 100644 index b2c8a36..0000000 --- a/providers/mlx5/bitmap.h +++ /dev/null @@ -1,109 +0,0 @@ -/* - * Copyright (c) 2000, 2011 Mellanox Technology Inc. All rights reserved. - * - * This software is available to you under a choice of one of two - * licenses. You may choose to be licensed under the terms of the GNU - * General Public License (GPL) Version 2, available from the file - * COPYING in the main directory of this source tree, or the - * OpenIB.org BSD license below: - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * - * - Redistributions of source code must retain the above - * copyright notice, this list of conditions and the following - * disclaimer. - * - * - Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials - * provided with the distribution. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS - * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN - * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN - * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#ifndef BITMAP_H -#define BITMAP_H - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "mlx5.h" - -/* Only ia64 requires this */ -#ifdef __ia64__ -#define MLX5_SHM_ADDR ((void *)0x8000000000000000UL) -#define MLX5_SHMAT_FLAGS (SHM_RND) -#else -#define MLX5_SHM_ADDR NULL -#define MLX5_SHMAT_FLAGS 0 -#endif - -#ifndef HPAGE_SIZE -#define HPAGE_SIZE (2UL * 1024 * 1024) -#endif - -#define MLX5_SHM_LENGTH HPAGE_SIZE -#define MLX5_Q_CHUNK_SIZE 32768 -#define MLX5_SHM_NUM_REGION 64 - -static inline unsigned long mlx5_ffz(uint32_t word) -{ - return __builtin_ffs(~word) - 1; -} - -static inline uint32_t mlx5_find_first_zero_bit(const unsigned long *addr, - uint32_t size) -{ - const unsigned long *p = addr; - uint32_t result = 0; - unsigned long tmp; - - while (size & ~(BITS_PER_LONG - 1)) { - tmp = *(p++); - if (~tmp) - goto found; - result += BITS_PER_LONG; - size -= BITS_PER_LONG; - } - if (!size) - return result; - - tmp = (*p) | (~0UL << size); - if (tmp == (uint32_t)~0UL) /* Are any bits zero? */ - return result + size; /* Nope. */ -found: - return result + mlx5_ffz(tmp); -} - -static inline void mlx5_set_bit(unsigned int nr, unsigned long *addr) -{ - addr[(nr / BITS_PER_LONG)] |= (1 << (nr % BITS_PER_LONG)); -} - -static inline void mlx5_clear_bit(unsigned int nr, unsigned long *addr) -{ - addr[(nr / BITS_PER_LONG)] &= ~(1 << (nr % BITS_PER_LONG)); -} - -static inline int mlx5_test_bit(unsigned int nr, const unsigned long *addr) -{ - return !!(addr[(nr / BITS_PER_LONG)] & (1 << (nr % BITS_PER_LONG))); -} - -#endif diff --git a/providers/mlx5/buf.c b/providers/mlx5/buf.c index 83c32b0..3a3a792 100644 --- a/providers/mlx5/buf.c +++ b/providers/mlx5/buf.c @@ -38,155 +38,38 @@ #include #include #include +#include +#include #include "mlx5.h" -#include "bitmap.h" -static int mlx5_bitmap_init(struct mlx5_bitmap *bmp, uint32_t num, - uint32_t mask) -{ - bmp->last = 0; - bmp->top = 0; - bmp->max = num; - bmp->avail = num; - bmp->mask = mask; - bmp->avail = bmp->max; - bmp->table = calloc(BITS_TO_LONGS(bmp->max), sizeof(*bmp->table)); - if (!bmp->table) - return -ENOMEM; - - return 0; -} - -static void bitmap_free_range(struct mlx5_bitmap *bmp, uint32_t obj, - int cnt) -{ - int i; +/* Only ia64 requires this */ +#ifdef __ia64__ +#define MLX5_SHM_ADDR ((void *)0x8000000000000000UL) +#define MLX5_SHMAT_FLAGS (SHM_RND) +#else +#define MLX5_SHM_ADDR NULL +#define MLX5_SHMAT_FLAGS 0 +#endif - obj &= bmp->max - 1; - - for (i = 0; i < cnt; i++) - mlx5_clear_bit(obj + i, bmp->table); - bmp->last = min(bmp->last, obj); - bmp->top = (bmp->top + bmp->max) & bmp->mask; - bmp->avail += cnt; -} - -static int mlx5_bitmap_empty(struct mlx5_bitmap *bmp) -{ - return (bmp->avail == bmp->max) ? 1 : 0; -} - -static int bitmap_avail(struct mlx5_bitmap *bmp) -{ - return bmp->avail; -} +#ifndef HPAGE_SIZE +#define HPAGE_SIZE (2UL * 1024 * 1024) +#endif -static void mlx5_bitmap_cleanup(struct mlx5_bitmap *bmp) -{ - if (bmp->table) - free(bmp->table); -} +#define MLX5_SHM_LENGTH HPAGE_SIZE +#define MLX5_Q_CHUNK_SIZE 32768 static void free_huge_mem(struct mlx5_hugetlb_mem *hmem) { - mlx5_bitmap_cleanup(&hmem->bitmap); + if (hmem->bitmap) + free(hmem->bitmap); + if (shmdt(hmem->shmaddr) == -1) mlx5_dbg(stderr, MLX5_DBG_CONTIG, "%s\n", strerror(errno)); shmctl(hmem->shmid, IPC_RMID, NULL); free(hmem); } -static int mlx5_bitmap_alloc(struct mlx5_bitmap *bmp) -{ - uint32_t obj; - int ret; - - obj = mlx5_find_first_zero_bit(bmp->table, bmp->max); - if (obj < bmp->max) { - mlx5_set_bit(obj, bmp->table); - bmp->last = (obj + 1); - if (bmp->last == bmp->max) - bmp->last = 0; - obj |= bmp->top; - ret = obj; - } else - ret = -1; - - if (ret != -1) - --bmp->avail; - - return ret; -} - -static uint32_t find_aligned_range(unsigned long *bmp, - uint32_t start, uint32_t nbits, - int len, int alignment) -{ - uint32_t end, i; - -again: - start = align(start, alignment); - - while ((start < nbits) && mlx5_test_bit(start, bmp)) - start += alignment; - - if (start >= nbits) - return -1; - - end = start + len; - if (end > nbits) - return -1; - - for (i = start + 1; i < end; i++) { - if (mlx5_test_bit(i, bmp)) { - start = i + 1; - goto again; - } - } - - return start; -} - -static int bitmap_alloc_range(struct mlx5_bitmap *bmp, int cnt, - int align) -{ - uint32_t obj; - int ret, i; - - if (cnt == 1 && align == 1) - return mlx5_bitmap_alloc(bmp); - - if (cnt > bmp->max) - return -1; - - obj = find_aligned_range(bmp->table, bmp->last, - bmp->max, cnt, align); - if (obj >= bmp->max) { - bmp->top = (bmp->top + bmp->max) & bmp->mask; - obj = find_aligned_range(bmp->table, 0, bmp->max, - cnt, align); - } - - if (obj < bmp->max) { - for (i = 0; i < cnt; i++) - mlx5_set_bit(obj + i, bmp->table); - if (obj == bmp->last) { - bmp->last = (obj + cnt); - if (bmp->last >= bmp->max) - bmp->last = 0; - } - obj |= bmp->top; - ret = obj; - } else - ret = -1; - - if (ret != -1) - bmp->avail -= cnt; - - return obj; -} - static struct mlx5_hugetlb_mem *alloc_huge_mem(size_t size) { struct mlx5_hugetlb_mem *hmem; @@ -209,12 +92,14 @@ static struct mlx5_hugetlb_mem *alloc_huge_mem(size_t size) goto out_rmid; } - if (mlx5_bitmap_init(&hmem->bitmap, shm_len / MLX5_Q_CHUNK_SIZE, - shm_len / MLX5_Q_CHUNK_SIZE - 1)) { + hmem->bitmap = bitmap_alloc0(shm_len / MLX5_Q_CHUNK_SIZE); + if (!hmem->bitmap) { mlx5_dbg(stderr, MLX5_DBG_CONTIG, "%s\n", strerror(errno)); goto out_shmdt; } + hmem->bmp_size = shm_len / MLX5_Q_CHUNK_SIZE; + /* * Marked to be destroyed when process detaches from shmget segment */ @@ -250,9 +135,13 @@ static int alloc_huge_buf(struct mlx5_context *mctx, struct mlx5_buf *buf, mlx5_spin_lock(&mctx->hugetlb_lock); list_for_each(&mctx->hugetlb_list, hmem, entry) { - if (bitmap_avail(&hmem->bitmap)) { - buf->base = bitmap_alloc_range(&hmem->bitmap, nchunk, 1); - if (buf->base != -1) { + if (!bitmap_full(hmem->bitmap, hmem->bmp_size)) { + buf->base = bitmap_find_free_region(hmem->bitmap, + hmem->bmp_size, + nchunk); + if (buf->base != hmem->bmp_size) { + bitmap_fill_region(hmem->bitmap, buf->base, + buf->base + nchunk); buf->hmem = hmem; found = 1; break; @@ -266,16 +155,14 @@ static int alloc_huge_buf(struct mlx5_context *mctx, struct mlx5_buf *buf, if (!hmem) return -1; - buf->base = bitmap_alloc_range(&hmem->bitmap, nchunk, 1); - if (buf->base == -1) { - free_huge_mem(hmem); - return -1; - } + buf->base = 0; + assert(nchunk <= hmem->bmp_size); + bitmap_fill_region(hmem->bitmap, 0, nchunk); buf->hmem = hmem; mlx5_spin_lock(&mctx->hugetlb_lock); - if (bitmap_avail(&hmem->bitmap)) + if (nchunk != hmem->bmp_size) list_add(&mctx->hugetlb_list, &hmem->entry); else list_add_tail(&mctx->hugetlb_list, &hmem->entry); @@ -295,8 +182,8 @@ static int alloc_huge_buf(struct mlx5_context *mctx, struct mlx5_buf *buf, out_fork: mlx5_spin_lock(&mctx->hugetlb_lock); - bitmap_free_range(&hmem->bitmap, buf->base, nchunk); - if (mlx5_bitmap_empty(&hmem->bitmap)) { + bitmap_zero_region(hmem->bitmap, buf->base, buf->base + nchunk); + if (bitmap_empty(hmem->bitmap, hmem->bmp_size)) { list_del(&hmem->entry); mlx5_spin_unlock(&mctx->hugetlb_lock); free_huge_mem(hmem); @@ -315,8 +202,8 @@ static void free_huge_buf(struct mlx5_context *ctx, struct mlx5_buf *buf) return; mlx5_spin_lock(&ctx->hugetlb_lock); - bitmap_free_range(&buf->hmem->bitmap, buf->base, nchunk); - if (mlx5_bitmap_empty(&buf->hmem->bitmap)) { + bitmap_zero_region(buf->hmem->bitmap, buf->base, buf->base + nchunk); + if (bitmap_empty(buf->hmem->bitmap, buf->hmem->bmp_size)) { list_del(&buf->hmem->entry); mlx5_spin_unlock(&ctx->hugetlb_lock); free_huge_mem(buf->hmem); diff --git a/providers/mlx5/dr_buddy.c b/providers/mlx5/dr_buddy.c index e153677..8713fe4 100644 --- a/providers/mlx5/dr_buddy.c +++ b/providers/mlx5/dr_buddy.c @@ -34,23 +34,23 @@ */ #include -#include +#include #include "mlx5dv_dr.h" struct dr_icm_pool; struct dr_icm_buddy_mem; -static int dr_find_first_bit(const bitmap *set_addr, - const bitmap *addr, +static int dr_find_first_bit(const unsigned long *set_addr, + const unsigned long *addr, unsigned int size) { unsigned int set_size = (size - 1) / BITS_PER_LONG + 1; unsigned long set_idx; /* find the first free in the first level */ - set_idx = bitmap_ffs(set_addr, 0, set_size); + set_idx = bitmap_find_first_bit(set_addr, 0, set_size); /* find the next level */ - return bitmap_ffs(addr, set_idx * BITS_PER_LONG, size); + return bitmap_find_first_bit(addr, set_idx * BITS_PER_LONG, size); } int dr_buddy_init(struct dr_icm_buddy_mem *buddy, uint32_t max_order) @@ -161,7 +161,7 @@ static void dr_buddy_update_upper_bitmap(struct dr_icm_buddy_mem *buddy, /* clear upper layer of search if needed */ dr_buddy_get_seg_borders(seg, &l, &h); - m = bitmap_ffs(buddy->bits[order], l, h); + m = bitmap_find_first_bit(buddy->bits[order], l, h); if (m == h) /* nothing in the long that includes seg */ bitmap_clear_bit(buddy->set_bit[order], seg / BITS_PER_LONG); } diff --git a/providers/mlx5/mlx5.h b/providers/mlx5/mlx5.h index 1eca478..4656153 100644 --- a/providers/mlx5/mlx5.h +++ b/providers/mlx5/mlx5.h @@ -44,9 +44,8 @@ #include #include #include "mlx5-abi.h" -#include +#include #include -#include "bitmap.h" #include #include "mlx5dv.h" @@ -289,7 +288,7 @@ struct mlx5_hca_cap_2_caps { }; struct reserved_qpn_blk { - bitmap *bmp; + unsigned long *bmp; uint32_t first_qpn; struct list_node entry; unsigned int next_avail_slot; @@ -419,19 +418,11 @@ struct mlx5_context { pthread_mutex_t crypto_login_mutex; }; -struct mlx5_bitmap { - uint32_t last; - uint32_t top; - uint32_t max; - uint32_t avail; - uint32_t mask; - unsigned long *table; -}; - struct mlx5_hugetlb_mem { int shmid; void *shmaddr; - struct mlx5_bitmap bitmap; + unsigned long *bitmap; + unsigned long bmp_size; struct list_node entry; }; diff --git a/providers/mlx5/mlx5_vfio.c b/providers/mlx5/mlx5_vfio.c index 3f1811d..b9cdfeb 100644 --- a/providers/mlx5/mlx5_vfio.c +++ b/providers/mlx5/mlx5_vfio.c @@ -142,7 +142,8 @@ static int mlx5_vfio_alloc_page(struct mlx5_vfio_context *ctx, uint64_t *iova) pthread_mutex_lock(&ctx->mem_alloc.block_list_mutex); while (true) { list_for_each(&ctx->mem_alloc.block_list, page_block, next_block) { - pg = bitmap_ffs(page_block->free_pages, 0, MLX5_VFIO_BLOCK_NUM_PAGES); + pg = bitmap_find_first_bit(page_block->free_pages, 0, + MLX5_VFIO_BLOCK_NUM_PAGES); if (pg != MLX5_VFIO_BLOCK_NUM_PAGES) { bitmap_clear_bit(page_block->free_pages, pg); *iova = page_block->iova + pg * MLX5_ADAPTER_PAGE_SIZE; diff --git a/providers/mlx5/mlx5_vfio.h b/providers/mlx5/mlx5_vfio.h index 2165a22..88cc332 100644 --- a/providers/mlx5/mlx5_vfio.h +++ b/providers/mlx5/mlx5_vfio.h @@ -163,7 +163,7 @@ struct page_block { void *page_ptr; uint64_t iova; struct list_node next_block; - BITMAP_DECLARE(free_pages, MLX5_VFIO_BLOCK_NUM_PAGES); + BMP_DECLARE(free_pages, MLX5_VFIO_BLOCK_NUM_PAGES); }; struct vfio_mem_allocator { diff --git a/providers/mlx5/mlx5dv_dr.h b/providers/mlx5/mlx5dv_dr.h index 16e5340..3cc3035 100644 --- a/providers/mlx5/mlx5dv_dr.h +++ b/providers/mlx5/mlx5dv_dr.h @@ -35,7 +35,7 @@ #include #include -#include +#include #include #include "mlx5dv.h" #include "mlx5_ifc.h" @@ -1619,9 +1619,9 @@ int dr_send_postsend_action(struct mlx5dv_dr_domain *dmn, struct dr_icm_mr; struct dr_icm_buddy_mem { - bitmap **bits; + unsigned long **bits; unsigned int *num_free; - bitmap **set_bit; + unsigned long **set_bit; uint32_t max_order; struct list_node list_node; struct dr_icm_mr *icm_mr; From patchwork Mon Feb 28 08:48:28 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yishai Hadas X-Patchwork-Id: 12762567 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 20BD0C43217 for ; Mon, 28 Feb 2022 08:49:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234060AbiB1IuH (ORCPT ); Mon, 28 Feb 2022 03:50:07 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33132 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234079AbiB1IuC (ORCPT ); Mon, 28 Feb 2022 03:50:02 -0500 Received: from NAM12-BN8-obe.outbound.protection.outlook.com (mail-bn8nam12on2051.outbound.protection.outlook.com [40.107.237.51]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B9B053968F for ; Mon, 28 Feb 2022 00:49:21 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=OKUmbHoDUxnZ/XjW9720R1/1XZJm9c8xefXNLkhRHPoojmlT/8KBmTBtFNOaOMECJMTtDvc9s/p8PXItYHWR4ch2YqhT0XBPFBe5KXvKMMx3uqIHQI9GUSWFFbDmwAnM/ekZlNxq+27hj3lTZ9S3b7Y0SJRLcDz1BWW3bRJhwKMRvmcEuYJXldpgdKLVK9WjHtQrrzOLQ626qtVuP776DPK91118NOObGv3wLm2ch1nFTsaLq36QsitzA/3GNTSPzDWO9HNqg52TADpNPqu0BaQmhMkbwgBq2IPbw91aOInf1wGuB2s15x4NtIV9yGFp/AJwHRz4aRJrD0Ktmck6SA== 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=m/hqhnu7S18/YyLUfRGRO4z4qgbe9nF2fAYOgo1wNRY=; b=NAaCqAyfhayL1TUlvNN+H0gWcjLDeamB+n11/IDYmHEpOHv9QB7fcIOUSKmw5CTvN3FK4o1Tu17bikFwpxRL/N+/cNtao6kYJpPuEdKJ6MzE/7VunQSxru5lWxQRWlYsl/vkLF8RDj4hbZIJ/spW95EsujXtFLZbqUbtQlAl+knZVGqbfRjbTMXFdkV7W+sJBjgNW2JmHaKbX2xbToQ5IIQow48eFtPrjar9sV010fSy6d5aewx73eW8FKWKlbGDMzxemwKMleBCquEx24t1vidq4NaemPjZe88n6fJqDAZGWHqQKwUZo32db+tH8VytiN7X44GGX8YuhFIELPmM7w== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 12.22.5.236) smtp.rcpttodomain=huawei.com smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=m/hqhnu7S18/YyLUfRGRO4z4qgbe9nF2fAYOgo1wNRY=; b=VSNibjfTElSRS47mFCAt+kv0aT8ot4n3nEWPqZzUKzDsk+6K4etB2akhOVZknee5X8uDcxG3fMm6HYhtg+PRw7fueIAbcuulgZ6xJEUt/0c8x2QTO5XZyRmKkEKMx9xWXh5efGLmYna4yYKTGpbd2v9QU4M6Kstei9/uSzXtF4de1MjNDQoMVyoEnyDLIdri+Pp/SebBVhZIYWuzI2yhXoMrVsyiIo/OiSQR3/XuW8XSFZVTLoeAvO3c/T5XtOod7cKP24qPYdaRX0tJOLCve46pBpOp6hCvuZbeq/jcE8k9RXxQip7bM9G96hcCBGAr0r/Da8RgJnGCGfGth61U/g== Received: from BN0PR04CA0052.namprd04.prod.outlook.com (2603:10b6:408:e8::27) by DM6PR12MB2665.namprd12.prod.outlook.com (2603:10b6:5:41::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.21; Mon, 28 Feb 2022 08:49:20 +0000 Received: from BN8NAM11FT055.eop-nam11.prod.protection.outlook.com (2603:10b6:408:e8:cafe::46) by BN0PR04CA0052.outlook.office365.com (2603:10b6:408:e8::27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.21 via Frontend Transport; Mon, 28 Feb 2022 08:49:19 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 12.22.5.236) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 12.22.5.236 as permitted sender) receiver=protection.outlook.com; client-ip=12.22.5.236; helo=mail.nvidia.com; Received: from mail.nvidia.com (12.22.5.236) by BN8NAM11FT055.mail.protection.outlook.com (10.13.177.62) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.5017.22 via Frontend Transport; Mon, 28 Feb 2022 08:49:19 +0000 Received: from rnnvmail205.nvidia.com (10.129.68.10) by DRHQMAIL109.nvidia.com (10.27.9.19) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Mon, 28 Feb 2022 08:49:11 +0000 Received: from rnnvmail202.nvidia.com (10.129.68.7) by rnnvmail205.nvidia.com (10.129.68.10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.986.9; Mon, 28 Feb 2022 00:49:09 -0800 Received: from vdi.nvidia.com (10.127.8.10) by mail.nvidia.com (10.129.68.7) with Microsoft SMTP Server id 15.2.986.9 via Frontend Transport; Mon, 28 Feb 2022 00:49:07 -0800 From: Yishai Hadas To: CC: , , , , , Avihai Horon Subject: [PATCH rdma-core 3/5] libhns: Adapt bitmap usage to use util API Date: Mon, 28 Feb 2022 10:48:28 +0200 Message-ID: <20220228084830.96274-4-yishaih@nvidia.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20220228084830.96274-1-yishaih@nvidia.com> References: <20220228084830.96274-1-yishaih@nvidia.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: d52c956e-e639-42d1-7dc9-08d9fa97356f X-MS-TrafficTypeDiagnostic: DM6PR12MB2665:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 0RTci3JRYr4eFVwfWL92xfE7RZGaCHiYX0r4cGvB9b1OcMiDCc8M6l6cb3MFz01aPr/XzDILK1mNZZNLJXjOuVyVqCeqcyA/zSZCwqtHIYbGil+mSiixgUD62WAnYsncCwySW4exV6Bc5wUSUb3e1bXEpprTDV7osUVpkQYx+ppujv28ra8lwOaLYyssRUljvmIcEOUwPAFd4BC6frcV3FYhtvXN2lAfKY6vNJwORq2oBqa9/bs7i0W3HBCRVLBOwITEqYLwUzfPLWOoNZohk1iR0AvkJuOr7e9W99c3PxI6vkIQkkiXcfZfd16lkUDEkMM6UyPVQHkqoFV1Nlp8lQoTW0qEV6lz62dzoy8M2YyrlsmQBRGgZSeHKS6UZlSEFTFVQTq8xF/vOCQpPJ+M6aVfJP8bv5ai+AseAReq5FhgRTVAcQz8NTqnRKv/8NCGVKAgjMJ3Wh18kRtol3tHZNBBf+rdrYt2zzEpmSi+OfX29VfBb1dur5mN2MMpKR5yL+UQ2p1CCwV3/A7gEkxQsf+lY8MVxq0uDxLsiA6h6fwCQ6d919Du5BOKZwBZz+uFB7BdnExEzenZFAOdqzizhjy7ppjr4TBvxRpNZcBBvqpyZ8/Y6Y7VHS2tf91tKbC28MIdWIslIAZptuQEorIyI86kHD1/kJmh9XCEKh32UjJo5jT+TT6lQV+W+LC+onGiRlyU9HP0AjsXBVbX8kUV8Q== X-Forefront-Antispam-Report: CIP:12.22.5.236;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:mail.nvidia.com;PTR:InfoNoRecords;CAT:NONE;SFS:(13230001)(4636009)(36840700001)(46966006)(40470700004)(86362001)(36756003)(1076003)(6666004)(2616005)(7696005)(508600001)(107886003)(26005)(336012)(426003)(186003)(54906003)(83380400001)(6916009)(47076005)(36860700001)(70206006)(70586007)(4326008)(8676002)(316002)(5660300002)(81166007)(8936002)(356005)(82310400004)(2906002)(40460700003)(36900700001);DIR:OUT;SFP:1101; X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Feb 2022 08:49:19.1265 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: d52c956e-e639-42d1-7dc9-08d9fa97356f X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a;Ip=[12.22.5.236];Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: BN8NAM11FT055.eop-nam11.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR12MB2665 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org From: Maher Sanalla Replace the usage of ccan bitmap with the newly added bitmap implementation in util. Signed-off-by: Maher Sanalla Reviewed-by: Avihai Horon Signed-off-by: Yishai Hadas --- providers/hns/hns_roce_u.h | 4 ++-- providers/hns/hns_roce_u_db.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/providers/hns/hns_roce_u.h b/providers/hns/hns_roce_u.h index 2b4ba18..d786efb 100644 --- a/providers/hns/hns_roce_u.h +++ b/providers/hns/hns_roce_u.h @@ -42,7 +42,7 @@ #include #include #include -#include +#include #include #include #include "hns_roce_u_abi.h" @@ -193,7 +193,7 @@ struct hns_roce_db_page { struct hns_roce_buf buf; unsigned int num_db; unsigned int use_cnt; - bitmap *bitmap; + unsigned long *bitmap; }; struct hns_roce_context { diff --git a/providers/hns/hns_roce_u_db.c b/providers/hns/hns_roce_u_db.c index f7aaa6e..f5acac2 100644 --- a/providers/hns/hns_roce_u_db.c +++ b/providers/hns/hns_roce_u_db.c @@ -33,7 +33,7 @@ #include #include #include -#include +#include #include "hns_roce_u.h" #include "hns_roce_u_db.h" @@ -109,7 +109,7 @@ void *hns_roce_alloc_db(struct hns_roce_context *ctx, found: ++page->use_cnt; - npos = bitmap_ffs(page->bitmap, 0, page->num_db); + npos = bitmap_find_first_bit(page->bitmap, 0, page->num_db); bitmap_clear_bit(page->bitmap, npos); db = page->buf.buf + npos * db_size[type]; From patchwork Mon Feb 28 08:48:29 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yishai Hadas X-Patchwork-Id: 12762566 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 50BDFC4332F for ; Mon, 28 Feb 2022 08:49:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234075AbiB1IuG (ORCPT ); Mon, 28 Feb 2022 03:50:06 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33134 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234060AbiB1IuC (ORCPT ); Mon, 28 Feb 2022 03:50:02 -0500 Received: from NAM10-DM6-obe.outbound.protection.outlook.com (mail-dm6nam10on2064.outbound.protection.outlook.com [40.107.93.64]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BEC0938BC0 for ; Mon, 28 Feb 2022 00:49:17 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=kO43RiJMGHBLccqHns8J/9c6jHXKU0fEMXPwk0bo24TCmpUv0QaA641sLGNJvS7p3UT0Jq6eiwwAmMGnCkJgBZ4poAikuvzqhlSL5CnnLz7Ih7Ux7ICNZXaAr4V2M2Td2Lo7hW1W+MBnoi19yl7PVSL+pMassY77yOiNu+poVyjwv7mXskReBTwNYeZCrdT7s+1RNWUfgsZDFpB7T5W2OhF6zbkATSQV3D9VhCd16QY/cUQD4TwsQNr0LGO7YLIq+kdUmFoBZFrS0QB6aYqDCz7U9KQCZ835aUM52A85CrCPQNIm3+RaccwlGL8L3g9el3yqc+i6xDx9WdhzdrkRsw== 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=yHEXWYtDQMnt0Hc5VSFNTf1Qm8eIexqP7WsK57ATNro=; b=KJt6ThXH/fpmHO/kAJAH6srQKM8r+M0KUjs8QGJ1ML8YGnINq3f0rQFnK4I9TAS3Pg3LIt8+FqRtiuYAV8/E5pOCB8tfR2yOJLniFxP5vlnszoeka4gGvY3/ToM3YdtZ79vv/H4Tyq4ZtMGM4tkKux+Unc49JYMnGp8onU6MFw1Eynxdl1KlyYOd7uzQCQY22qb6OSS0FZmDrZ65sEpXwOYSAH3AJld81mP9a/dJPZc5jeID3wPOCKzi28EX0eS49HdMfZRDjrkQwl+3ERd+n5VXxFxhfswLjVgATg4mDlsyjajidWWaazCuozEtLGpvy4IdGukZffojkgXs0L1GZg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 12.22.5.234) smtp.rcpttodomain=huawei.com smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=yHEXWYtDQMnt0Hc5VSFNTf1Qm8eIexqP7WsK57ATNro=; b=QVShPhITw+7t0oUywjTFd2Xr4mkRX8k9TbRRqiem2AfvRIV/DbCSVJKkOcXeHAF71MIplVkfZujL0DFejYLE3fzieS+8eA65SUqcvPGCQUMoYHUdChpmfs0RnEpHceYtDVanceG7sOy8VqNKM213tX9FXjBKb2LMUg+mVHTDyJb+p4ElMLmyduyxqVb7qpfi3LIbtetXpAEytWO9vD4/ORJpWrOHp8WuuskGBIoMJ3jM6UgXUuUmM9yAmJPIh4dyJJ8E8xXt+qAIYlf6AJk5vwze62jjAW5Nz16D+xlKUwsPtsVplDrOBEPQPPJ4NgK8Od4qBPMAEHJQpBft8ahrjw== Received: from DM5PR21CA0025.namprd21.prod.outlook.com (2603:10b6:3:ed::11) by MW4PR12MB5603.namprd12.prod.outlook.com (2603:10b6:303:16a::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.22; Mon, 28 Feb 2022 08:49:13 +0000 Received: from DM6NAM11FT053.eop-nam11.prod.protection.outlook.com (2603:10b6:3:ed:cafe::52) by DM5PR21CA0025.outlook.office365.com (2603:10b6:3:ed::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5061.1 via Frontend Transport; Mon, 28 Feb 2022 08:49:15 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 12.22.5.234) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 12.22.5.234 as permitted sender) receiver=protection.outlook.com; client-ip=12.22.5.234; helo=mail.nvidia.com; Received: from mail.nvidia.com (12.22.5.234) by DM6NAM11FT053.mail.protection.outlook.com (10.13.173.74) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.5017.22 via Frontend Transport; Mon, 28 Feb 2022 08:49:14 +0000 Received: from rnnvmail203.nvidia.com (10.129.68.9) by DRHQMAIL101.nvidia.com (10.27.9.10) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Mon, 28 Feb 2022 08:49:13 +0000 Received: from rnnvmail202.nvidia.com (10.129.68.7) by rnnvmail203.nvidia.com (10.129.68.9) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.986.9; Mon, 28 Feb 2022 00:49:12 -0800 Received: from vdi.nvidia.com (10.127.8.10) by mail.nvidia.com (10.129.68.7) with Microsoft SMTP Server id 15.2.986.9 via Frontend Transport; Mon, 28 Feb 2022 00:49:10 -0800 From: Yishai Hadas To: CC: , , , , , Avihai Horon Subject: [PATCH rdma-core 4/5] verbs: Adapt bitmap usage to use util API Date: Mon, 28 Feb 2022 10:48:29 +0200 Message-ID: <20220228084830.96274-5-yishaih@nvidia.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20220228084830.96274-1-yishaih@nvidia.com> References: <20220228084830.96274-1-yishaih@nvidia.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 10fb8446-2fc2-4b40-4dcb-08d9fa9732ca X-MS-TrafficTypeDiagnostic: MW4PR12MB5603:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 9ta81KSxpcbeJe3edgpShZ/fpasEK4MipTDz5iVjJgbsGn5X2IXKGsyFpcwoz43FHejmH0C3BuTXf4yIbQZsUmMlxFMcgroYy7i+fh4Hox2y4BgFp9EcfekK41kzpUhqQwn6TF8VPamJ61DeCi+VwSkMtlYnQyVknJy94GkvCKj23ek//52TDB+mReTRUkoYOo6YMyP9VlN04SoE0G0fOc8wh9LzkI88WOFns/3k/a62TjFpC1Rg5miEosa0fIMbEKFAQITKObvTBhqsi77zN5/g3mgfFVfAo5wselP9ZlycmY8tZAtXHsoPbNEoz2UhZGS+vpDoWljGcsVKrrBxMGvP+/+eqwZMKeRz71JhoIjdlhBuuV7U5/WhvfFw/UCcKrgUNh8jUHsOK6WTw9kC7Ag3+MQFnONyaR1KzVWyhfDpLTEU9WL2o7WDeD8p1caM4ZGV8COFspCMcmVC43rXfAObHYlfSNreWsbmFmULLpdYWJczkdO/1jd/LMBy2sMdylzwWxGvwVCsSt/CNb3HSZfSZhLTZL/wyo+g+eqwP1dkEArORqi5IFM76an2Th3hQJBG8vaIlHuVJ6pVLbayctI9sEdFaxEoH1pomApG5GuYtbiYT289Dds8h1LRpDpUsKFXvI5Ker6S+zqi5xHFjmUDG+VJikfdWeZ/49sxCmLl6HpsElYZLaU0Mm7Wta5ClbtzXV3X9mGtEBySqylEWQ== X-Forefront-Antispam-Report: CIP:12.22.5.234;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:mail.nvidia.com;PTR:InfoNoRecords;CAT:NONE;SFS:(13230001)(4636009)(40470700004)(46966006)(36840700001)(2616005)(1076003)(40460700003)(54906003)(316002)(47076005)(70586007)(6916009)(86362001)(26005)(336012)(186003)(426003)(508600001)(36860700001)(2906002)(81166007)(82310400004)(70206006)(5660300002)(36756003)(356005)(107886003)(7696005)(6666004)(8936002)(8676002)(4744005)(4326008)(83380400001)(36900700001);DIR:OUT;SFP:1101; X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Feb 2022 08:49:14.7510 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 10fb8446-2fc2-4b40-4dcb-08d9fa9732ca X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a;Ip=[12.22.5.234];Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: DM6NAM11FT053.eop-nam11.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW4PR12MB5603 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org From: Maher Sanalla Replace the usage of ccan bitmap with the newly added bitmap implementation in util. Signed-off-by: Maher Sanalla Reviewed-by: Avihai Horon Signed-off-by: Yishai Hadas --- libibverbs/ibverbs.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/libibverbs/ibverbs.h b/libibverbs/ibverbs.h index 5e60ace..33f83a7 100644 --- a/libibverbs/ibverbs.h +++ b/libibverbs/ibverbs.h @@ -37,7 +37,7 @@ #include #include -#include +#include #define INIT __attribute__((constructor)) @@ -70,7 +70,7 @@ void load_drivers(void); #endif struct verbs_ex_private { - BITMAP_DECLARE(unsupported_ioctls, VERBS_OPS_NUM); + BMP_DECLARE(unsupported_ioctls, VERBS_OPS_NUM); uint32_t driver_id; bool use_ioctl_write; struct verbs_context_ops ops; From patchwork Mon Feb 28 08:48:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yishai Hadas X-Patchwork-Id: 12762565 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id ACD50C433EF for ; Mon, 28 Feb 2022 08:49:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234073AbiB1IuF (ORCPT ); Mon, 28 Feb 2022 03:50:05 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33140 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234080AbiB1IuD (ORCPT ); Mon, 28 Feb 2022 03:50:03 -0500 Received: from NAM12-BN8-obe.outbound.protection.outlook.com (mail-bn8nam12on2065.outbound.protection.outlook.com [40.107.237.65]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4B7F139BA5 for ; Mon, 28 Feb 2022 00:49:24 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=PuBHpSzKUyJPtchLNBQWXTxfhf9NCPcOj2/uXKmf0ZUD6r9qUzau5sqsXg5BNIIo4tp3wR5blgMmUkycBUC7nDbVDOoyOoiNfLQfTcz3zLynrv+VI6s5aPoxUQ5CQcALegvJcOkiEmJb0/o2Hv0BUaVDn98Xfw8YanGNCwsi6rgJko5DBGYiPiMxOnYRxwNexbvvz8ehqhhdoPSCDRKlsPwqjrwPsyNriLNdhgTIDy6N8oYJcFej8x03wxTMoPdO4EtDdRGf0QpmiYFKWEKpJXkAryRwx2w9pUth4HIeNQgs61cixTaP2E0pbQkpTEAQ4ss9fMA/funJYZvRfiZRUA== 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=SJC3xzdEqZmOTR5T9/huWT9XU3UuqecI15Jc3fJrL/c=; b=hDzm+9pAFSevMif0RTha22MxXuKQz7i/aXF0YtvbNtVScYBGFaTJ3WjCf0wctOEJsTw2muTCgpoTqIItjw851dU67xiRY2GS3pOPxVB/dOzDuN0JDyo2UBQhk2uD7Ylyn1mXP6oV+tShA5oRjo9OPi1+MUyzcht80hNfSxRkjs6GEMq+wC8ukOQG1orMZXY5BK1LgarxIQLZ3fnySFQEXBP/wd0PDxsI+wJQcM2VO+c2CZHdp7zn6S/yxt1whFSyly6+F9qc5MaCvTkYO1lRrpQs2p1/AHZn6LWefTSnhkWJvJIZ5MeGMt7O+MfYkT2QeruxfhxSqDjZmNIWOoBPlA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 12.22.5.236) smtp.rcpttodomain=huawei.com smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=SJC3xzdEqZmOTR5T9/huWT9XU3UuqecI15Jc3fJrL/c=; b=bUCBOtElIbiGJpYTwBVw12aGqOu10jdQGwCNQbtFq+uFolYvoBMHdIIN/65Gd541DWHLtfmb7EcDeOB83rm7f4g/Tg96lRdSnK9EcKgikQnsLeUoy0aW/1VrCbvrFkiyiQ95hdAe4SyZX47TUpX1KfptAmyGAxnoik2CRzrUb7FENLbedSbudGFeNANdtd4BDvMbNCIlCsTMbnn6JVbeeYj6F8/hmb9lO5/5599siasU8JgDH84ini7UbfqWHLCPuynAQiZQ3i/Rc2ER7gRlbSoiwKuRmfO9pa3YNzXqoUGzNJ96qCVg4EvwaK/fJaR2x+UFjeorH1UtwErxvVuWIQ== Received: from BN0PR04CA0050.namprd04.prod.outlook.com (2603:10b6:408:e8::25) by BY5PR12MB3761.namprd12.prod.outlook.com (2603:10b6:a03:1af::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.24; Mon, 28 Feb 2022 08:49:20 +0000 Received: from BN8NAM11FT055.eop-nam11.prod.protection.outlook.com (2603:10b6:408:e8:cafe::2b) by BN0PR04CA0050.outlook.office365.com (2603:10b6:408:e8::25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.21 via Frontend Transport; Mon, 28 Feb 2022 08:49:20 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 12.22.5.236) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 12.22.5.236 as permitted sender) receiver=protection.outlook.com; client-ip=12.22.5.236; helo=mail.nvidia.com; Received: from mail.nvidia.com (12.22.5.236) by BN8NAM11FT055.mail.protection.outlook.com (10.13.177.62) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.5017.22 via Frontend Transport; Mon, 28 Feb 2022 08:49:20 +0000 Received: from rnnvmail204.nvidia.com (10.129.68.6) by DRHQMAIL109.nvidia.com (10.27.9.19) with Microsoft SMTP Server (TLS) id 15.0.1497.18; Mon, 28 Feb 2022 08:49:16 +0000 Received: from rnnvmail202.nvidia.com (10.129.68.7) by rnnvmail204.nvidia.com (10.129.68.6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.986.9; Mon, 28 Feb 2022 00:49:15 -0800 Received: from vdi.nvidia.com (10.127.8.10) by mail.nvidia.com (10.129.68.7) with Microsoft SMTP Server id 15.2.986.9 via Frontend Transport; Mon, 28 Feb 2022 00:49:13 -0800 From: Yishai Hadas To: CC: , , , , , Avihai Horon Subject: [PATCH rdma-core 5/5] ccan: Remove bitmap code Date: Mon, 28 Feb 2022 10:48:30 +0200 Message-ID: <20220228084830.96274-6-yishaih@nvidia.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20220228084830.96274-1-yishaih@nvidia.com> References: <20220228084830.96274-1-yishaih@nvidia.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 1cfbd5b0-9bd0-45ed-add9-08d9fa973624 X-MS-TrafficTypeDiagnostic: BY5PR12MB3761:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 42Mrwfq2y1VURkHeCKFjNV3xktxEW2HXrEuxAhznPYlawCwFaU4Mv4ffvEQhIJUf/TAlPweKnACVwXKuRxO+vev2ZWd8PZyuydYFszfTZghSA8XhzHPbKBqhRg2PNJg0aBMqxVwMzauQcD7613lrhksMbp4v62/7l1i/7dNV2QBJS7fkfYqmmoozAQncQ0z0ZMyTmRcf4QOBtZFRnHt6GUOlM2ifz3kNU56c/JEHKPtWeQcmM1NXd1rSCcpT6wzS9PxbQ+t6pRCt3HlLMNSopiq9kxdvsz03W87vnJi3yDZ23M0z2s6zNZqqkYqwWSorENJ7oJhv9tPw0SyFidmRPL0gEZUV5X36VtAqqUMpxjHmd5mEUh0zfHHfNfRiMXb0Jd7Y8LESmk446xSM3wztBJIb1Ljfyde5O0vgoMHAe5d/7CKoCzn8WvKqe2S0f/bZ9ftZfVArc6oMkCFvPT5rFb+FBhTnBzyyBAVNDPwS8pMckEyjXgQkGL2ljxhfLOn3xbhCSFjYTbP5Tayhln2505qkTZpjuKX+2+iWmpv8bo2pK6Sgm/lddwuHDaHD7tPtxdPjCWvuYomsWR7lHnA60623k5V9e/UUBGyfJeyFZX5753zd5IfD9a47gEm0YB4SN9CM4X0E2R6X7pfrZo/Axx3RKw6DVboy6pky0A2/K5/UGUb1bamliLMU/G7JnRlxOy1ODSlbVvfZeCs0poCykg== X-Forefront-Antispam-Report: CIP:12.22.5.236;CTRY:US;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:mail.nvidia.com;PTR:InfoNoRecords;CAT:NONE;SFS:(13230001)(4636009)(46966006)(40470700004)(36840700001)(83380400001)(36860700001)(107886003)(82310400004)(8936002)(47076005)(1076003)(36756003)(7696005)(26005)(186003)(40460700003)(426003)(336012)(2616005)(508600001)(6916009)(54906003)(316002)(81166007)(356005)(4326008)(8676002)(2906002)(86362001)(5660300002)(70586007)(70206006)(6666004)(36900700001);DIR:OUT;SFP:1101; X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 28 Feb 2022 08:49:20.3296 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 1cfbd5b0-9bd0-45ed-add9-08d9fa973624 X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a;Ip=[12.22.5.236];Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: BN8NAM11FT055.eop-nam11.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR12MB3761 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org From: Maher Sanalla Removes ccan bitmap implementation, along with adjustments to the ccan Makefile. Signed-off-by: Maher Sanalla Reviewed-by: Avihai Horon Signed-off-by: Yishai Hadas --- ccan/CMakeLists.txt | 2 - ccan/bitmap.c | 125 --------------------------- ccan/bitmap.h | 239 ---------------------------------------------------- 3 files changed, 366 deletions(-) delete mode 100644 ccan/bitmap.c delete mode 100644 ccan/bitmap.h diff --git a/ccan/CMakeLists.txt b/ccan/CMakeLists.txt index 5c5c6a2..d370a8e 100644 --- a/ccan/CMakeLists.txt +++ b/ccan/CMakeLists.txt @@ -1,6 +1,5 @@ publish_internal_headers(ccan array_size.h - bitmap.h build_assert.h check_type.h compiler.h @@ -13,7 +12,6 @@ publish_internal_headers(ccan ) set(C_FILES - bitmap.c ilog.c list.c str.c diff --git a/ccan/bitmap.c b/ccan/bitmap.c deleted file mode 100644 index ea5531c..0000000 --- a/ccan/bitmap.c +++ /dev/null @@ -1,125 +0,0 @@ -/* Licensed under LGPLv2.1+ - see LICENSE file for details */ - -#include "config.h" - -#include - -#include - -#define BIT_ALIGN_DOWN(n) ((n) & ~(BITMAP_WORD_BITS - 1)) -#define BIT_ALIGN_UP(n) BIT_ALIGN_DOWN((n) + BITMAP_WORD_BITS - 1) - -void bitmap_zero_range(bitmap *bmap, unsigned long n, unsigned long m) -{ - unsigned long an = BIT_ALIGN_UP(n); - unsigned long am = BIT_ALIGN_DOWN(m); - bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS); - bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS)); - - assert(m >= n); - - if (am < an) { - BITMAP_WORD(bmap, n) &= ~bitmap_bswap(headmask & tailmask); - return; - } - - if (an > n) - BITMAP_WORD(bmap, n) &= ~bitmap_bswap(headmask); - - if (am > an) - memset(&BITMAP_WORD(bmap, an), 0, - (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word)); - - if (m > am) - BITMAP_WORD(bmap, m) &= ~bitmap_bswap(tailmask); -} - -void bitmap_fill_range(bitmap *bmap, unsigned long n, unsigned long m) -{ - unsigned long an = BIT_ALIGN_UP(n); - unsigned long am = BIT_ALIGN_DOWN(m); - bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS); - bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS)); - - assert(m >= n); - - if (am < an) { - BITMAP_WORD(bmap, n) |= bitmap_bswap(headmask & tailmask); - return; - } - - if (an > n) - BITMAP_WORD(bmap, n) |= bitmap_bswap(headmask); - - if (am > an) - memset(&BITMAP_WORD(bmap, an), 0xff, - (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word)); - - if (m > am) - BITMAP_WORD(bmap, m) |= bitmap_bswap(tailmask); -} - -static int bitmap_clz(bitmap_word w) -{ -#if HAVE_BUILTIN_CLZL - return __builtin_clzl(w); -#else - int lz = 0; - bitmap_word mask = 1UL << (BITMAP_WORD_BITS - 1); - - while (!(w & mask)) { - lz++; - mask >>= 1; - } - - return lz; -#endif -} - -unsigned long bitmap_ffs(const bitmap *bmap, - unsigned long n, unsigned long m) -{ - unsigned long an = BIT_ALIGN_UP(n); - unsigned long am = BIT_ALIGN_DOWN(m); - bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS); - bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS)); - - assert(m >= n); - - if (am < an) { - bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, n)); - - w &= (headmask & tailmask); - - return w ? am + bitmap_clz(w) : m; - } - - if (an > n) { - bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, n)); - - w &= headmask; - - if (w) - return BIT_ALIGN_DOWN(n) + bitmap_clz(w); - } - - while (an < am) { - bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, an)); - - if (w) - return an + bitmap_clz(w); - - an += BITMAP_WORD_BITS; - } - - if (m > am) { - bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, m)); - - w &= tailmask; - - if (w) - return am + bitmap_clz(w); - } - - return m; -} diff --git a/ccan/bitmap.h b/ccan/bitmap.h deleted file mode 100644 index ff0b8c8..0000000 --- a/ccan/bitmap.h +++ /dev/null @@ -1,239 +0,0 @@ -/* Licensed under LGPLv2+ - see LICENSE file for details */ -#ifndef CCAN_BITMAP_H_ -#define CCAN_BITMAP_H_ - -#include -#include -#include -#include - -typedef unsigned long bitmap_word; - -#define BITMAP_WORD_BITS (sizeof(bitmap_word) * CHAR_BIT) -#define BITMAP_NWORDS(_n) \ - (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS) - -/* - * We wrap each word in a structure for type checking. - */ -typedef struct { - bitmap_word w; -} bitmap; - -#define BITMAP_DECLARE(_name, _nbits) \ - bitmap (_name)[BITMAP_NWORDS(_nbits)] - -static inline size_t bitmap_sizeof(unsigned long nbits) -{ - return BITMAP_NWORDS(nbits) * sizeof(bitmap_word); -} - -static inline bitmap_word bitmap_bswap(bitmap_word w) -{ - /* We do not need to have the bitmap in any specific endianness */ - return w; -} - -#define BITMAP_WORD(_bm, _n) ((_bm)[(_n) / BITMAP_WORD_BITS].w) -#define BITMAP_WORDBIT(_n) \ - (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1))) - -#define BITMAP_HEADWORDS(_nbits) \ - ((_nbits) / BITMAP_WORD_BITS) -#define BITMAP_HEADBYTES(_nbits) \ - (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word)) - -#define BITMAP_TAILWORD(_bm, _nbits) \ - ((_bm)[BITMAP_HEADWORDS(_nbits)].w) -#define BITMAP_HASTAIL(_nbits) (((_nbits) % BITMAP_WORD_BITS) != 0) -#define BITMAP_TAILBITS(_nbits) \ - (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS)))) -#define BITMAP_TAIL(_bm, _nbits) \ - (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits)) - -static inline void bitmap_set_bit(bitmap *bmap, unsigned long n) -{ - BITMAP_WORD(bmap, n) |= BITMAP_WORDBIT(n); -} - -static inline void bitmap_clear_bit(bitmap *bmap, unsigned long n) -{ - BITMAP_WORD(bmap, n) &= ~BITMAP_WORDBIT(n); -} - -static inline void bitmap_change_bit(bitmap *bmap, unsigned long n) -{ - BITMAP_WORD(bmap, n) ^= BITMAP_WORDBIT(n); -} - -static inline bool bitmap_test_bit(const bitmap *bmap, unsigned long n) -{ - return !!(BITMAP_WORD(bmap, n) & BITMAP_WORDBIT(n)); -} - -void bitmap_zero_range(bitmap *bmap, unsigned long n, unsigned long m); -void bitmap_fill_range(bitmap *bmap, unsigned long n, unsigned long m); - -static inline void bitmap_zero(bitmap *bmap, unsigned long nbits) -{ - memset(bmap, 0, bitmap_sizeof(nbits)); -} - -static inline void bitmap_fill(bitmap *bmap, unsigned long nbits) -{ - memset(bmap, 0xff, bitmap_sizeof(nbits)); -} - -static inline void bitmap_copy(bitmap *dst, const bitmap *src, - unsigned long nbits) -{ - memcpy(dst, src, bitmap_sizeof(nbits)); -} - -#define BITMAP_DEF_BINOP(_name, _op) \ - static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \ - unsigned long nbits) \ - { \ - unsigned long i = 0; \ - for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \ - dst[i].w = src1[i].w _op src2[i].w; \ - } \ - } - -BITMAP_DEF_BINOP(and, &) -BITMAP_DEF_BINOP(or, |) -BITMAP_DEF_BINOP(xor, ^) -BITMAP_DEF_BINOP(andnot, & ~) - -#undef BITMAP_DEF_BINOP - -static inline void bitmap_complement(bitmap *dst, const bitmap *src, - unsigned long nbits) -{ - unsigned long i; - - for (i = 0; i < BITMAP_NWORDS(nbits); i++) - dst[i].w = ~src[i].w; -} - -static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2, - unsigned long nbits) -{ - return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0) - && (!BITMAP_HASTAIL(nbits) - || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits))); -} - -static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2, - unsigned long nbits) -{ - unsigned long i; - - for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { - if (src1[i].w & src2[i].w) - return true; - } - if (BITMAP_HASTAIL(nbits) && - (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits))) - return true; - return false; -} - -static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2, - unsigned long nbits) -{ - unsigned long i; - - for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { - if (src1[i].w & ~src2[i].w) - return false; - } - if (BITMAP_HASTAIL(nbits) && - (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits))) - return false; - return true; -} - -static inline bool bitmap_full(const bitmap *bmap, unsigned long nbits) -{ - unsigned long i; - - for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { - if (bmap[i].w != -1UL) - return false; - } - if (BITMAP_HASTAIL(nbits) && - (BITMAP_TAIL(bmap, nbits) != BITMAP_TAILBITS(nbits))) - return false; - - return true; -} - -static inline bool bitmap_empty(const bitmap *bmap, unsigned long nbits) -{ - unsigned long i; - - for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { - if (bmap[i].w != 0) - return false; - } - if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bmap, nbits) != 0)) - return false; - - return true; -} - -unsigned long bitmap_ffs(const bitmap *bmap, - unsigned long n, unsigned long m); - -/* - * Allocation functions - */ -static inline bitmap *bitmap_alloc(unsigned long nbits) -{ - return malloc(bitmap_sizeof(nbits)); -} - -static inline bitmap *bitmap_alloc0(unsigned long nbits) -{ - bitmap *bmap; - - bmap = bitmap_alloc(nbits); - if (bmap) - bitmap_zero(bmap, nbits); - return bmap; -} - -static inline bitmap *bitmap_alloc1(unsigned long nbits) -{ - bitmap *bmap; - - bmap = bitmap_alloc(nbits); - if (bmap) - bitmap_fill(bmap, nbits); - return bmap; -} - -static inline bitmap *bitmap_realloc0(bitmap *bmap, unsigned long obits, - unsigned long nbits) -{ - bmap = realloc(bmap, bitmap_sizeof(nbits)); - - if ((nbits > obits) && bmap) - bitmap_zero_range(bmap, obits, nbits); - - return bmap; -} - -static inline bitmap *bitmap_realloc1(bitmap *bmap, unsigned long obits, - unsigned long nbits) -{ - bmap = realloc(bmap, bitmap_sizeof(nbits)); - - if ((nbits > obits) && bmap) - bitmap_fill_range(bmap, obits, nbits); - - return bmap; -} - -#endif /* CCAN_BITMAP_H_ */