Received: by 2002:ab2:6991:0:b0:1f2:fff1:ace7 with SMTP id v17csp123724lqo; Wed, 27 Mar 2024 08:31:50 -0700 (PDT) X-Forwarded-Encrypted: i=3; AJvYcCUbDVFXUOfX7KnGxXaxxf8EUzdC73/uZyp9/P5C2Sn5P2rTl60+k57NSY9rdlowiGj4iAjT8SAgNYX4jDt3cLHDnoLlW+j+fmOAlZ089Q== X-Google-Smtp-Source: AGHT+IFYdbSp8sBOUHqTfUMGNX0ahYQUiG1noU2eJMXvofbALojzYrfGDllkY1CEVKYJ5PQ7DkX3 X-Received: by 2002:a05:620a:108b:b0:78a:2b1b:e56b with SMTP id g11-20020a05620a108b00b0078a2b1be56bmr6444868qkk.68.1711553510706; Wed, 27 Mar 2024 08:31:50 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1711553510; cv=pass; d=google.com; s=arc-20160816; b=DhCDXtPEE/hC0KSaXhuOV8uNbhzSkckhSvivIBCJMO4QYzA+B1wasQoVPDQqlHbkS5 gySUGBeo1/TPCqN2C53L9o3+Kq4u3YJl3cdhQkqVQPi7BVdmmshbfzoo8cjFdjK/rJLe QKoEUBonBL011ToMWme4VlC1MartVcedjM+maNvkeCfKVGR4ZlP5WRoDDdYm0W3Kd9b4 BSgVzPXKTnU4fujF+PRsZAHqUc9zXQTC/KAD/MQ2uOFLXxTkOMnoNZyx+RzBGuXe2itT 0mqLRyC80qYiKxzBab0naK/ADhKoU66/4d2diUS3mRaXFbjbHkLBnJpkgm8TRLiw6w/i LurA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:in-reply-to:message-id :date:subject:cc:to:from:dkim-signature; bh=WZ1GcCw6RWHzigxLpB7LM0VlCoO1Bab0KJTeIiX+UCg=; fh=3LTsKEUzK3WJ46Fl1goLUrMQHuCSg7tyeTq5Cyuu+Cc=; b=rFV5x/cu5Kp3hopcvQcXfGmbYgkDHK5d06wYuQoWlmS64Z+Qj9lSwJbJL+glm+/IEi hPxkGeOmUdN8XNZcrDROVjDR4LW9Hy5hfwXbJGwujkcVp2fq+u0FeaY7CCwg1Xacftt7 OwoH8NXwEGSKTpINMRKMxWBBJ5DzW8v7VQg5vLFcHm80uRa//tjHpxSA/KqGKfJbiLXj 0a8XxdLj6c+pqGYMPNLKh6dKhCSmKtbLJT4Jbh51dPcrSoc8bRCpzeLn3NJACYDaopM6 A0SawMHB5/nopZ4/Kx5Nocg8j2SM4QMq5DCkF1qzyH8rfBdw0E1+3RBrihrZhAw5VpUg gs4g==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@intel.com header.s=Intel header.b=OW++ry41; arc=pass (i=1 spf=pass spfdomain=intel.com dkim=pass dkdomain=intel.com dmarc=pass fromdomain=intel.com); spf=pass (google.com: domain of linux-kernel+bounces-121513-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) smtp.mailfrom="linux-kernel+bounces-121513-linux.lists.archive=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Return-Path: Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [147.75.199.223]) by mx.google.com with ESMTPS id g1-20020a05620a40c100b0078a731dc425si1028430qko.668.2024.03.27.08.31.50 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 27 Mar 2024 08:31:50 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel+bounces-121513-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223; Authentication-Results: mx.google.com; dkim=pass header.i=@intel.com header.s=Intel header.b=OW++ry41; arc=pass (i=1 spf=pass spfdomain=intel.com dkim=pass dkdomain=intel.com dmarc=pass fromdomain=intel.com); spf=pass (google.com: domain of linux-kernel+bounces-121513-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) smtp.mailfrom="linux-kernel+bounces-121513-linux.lists.archive=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ny.mirrors.kernel.org (Postfix) with ESMTPS id E22FF1C2CAD6 for ; Wed, 27 Mar 2024 15:31:47 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id E55DB1419B3; Wed, 27 Mar 2024 15:24:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=intel.com header.i=@intel.com header.b="OW++ry41" Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.19]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BC3AF137C58; Wed, 27 Mar 2024 15:24:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.175.65.19 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1711553093; cv=none; b=i3A/MBtQyc8uxXSPyF83Cg03IPpLmQ/EdxV30XOnShy1aTDVR44Ajsp2QkfIAmoXvDXXKDeYva+d4iLEFAzYpESdkiZO3dq4gkeXVnhBpAfRcwpP1oWFiE9Dx/VmaGSOq8KWUOTERnM+Ah7DpdqeqRjFLoqyKhZV2KDbWyDzz7Q= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1711553093; c=relaxed/simple; bh=nlAv8DcC/nsFTR/JMjfsbTOZRgfJCpZQWTDLxH5GJ+w=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=GgYR1XtV9l5wRPKJB0kNX4pLK1LTFfMo7wOcImFWl0wZG1fiY4STUufVdQMnxZL8BkKJBNqObss2DtrEHJzERn/Gx6HVX618H0VdsJp+5N41FnsGFHZsHxrGTEK/Q2ilYAqX0TSja8PEC6dikCYBCgbyhldujh6kYA3oDZosp+M= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=intel.com; spf=pass smtp.mailfrom=intel.com; dkim=pass (2048-bit key) header.d=intel.com header.i=@intel.com header.b=OW++ry41; arc=none smtp.client-ip=198.175.65.19 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=intel.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=intel.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1711553091; x=1743089091; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=nlAv8DcC/nsFTR/JMjfsbTOZRgfJCpZQWTDLxH5GJ+w=; b=OW++ry419FY1ANmKwhVc3xqCQK8F4QFcWfvQARmXZgmfoyzxO//cIM6u jQX894rrx282Hh68SppIQZ6p1wDrQF36kvBRdXrkW95EVCv73KqzbmjEN 1jFWMpT52Js+ggjEa/v7OcV3vgeoIpuOdotsbqA7bBDV7fUwkyNUDkvRE Pr90Qei7opwRsnBaGF8Aaa+ZbYm1b/m/rozaHFScFdlEmTDV0SZ0GsTtd hfJgmzBP+zCjCQBoo+9vdyWkaxYrpS7JwDrQkR7Ov6xLFHcUmGjwVnLPD NKfGVGPZhLFjfvxZxSjRNCmgcnlOM4b25DRwhpifCXQutXahyYLKfZKDJ w==; X-CSE-ConnectionGUID: cTOZcIBRSCCJciD9dY+wEA== X-CSE-MsgGUID: Xq6S+T4XTmyZ0rx4ZPSGcQ== X-IronPort-AV: E=McAfee;i="6600,9927,11026"; a="6518096" X-IronPort-AV: E=Sophos;i="6.07,159,1708416000"; d="scan'208";a="6518096" Received: from fmviesa008.fm.intel.com ([10.60.135.148]) by orvoesa111.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 27 Mar 2024 08:24:42 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.07,159,1708416000"; d="scan'208";a="16414091" Received: from newjersey.igk.intel.com ([10.102.20.203]) by fmviesa008.fm.intel.com with ESMTP; 27 Mar 2024 08:24:40 -0700 From: Alexander Lobakin To: "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni Cc: Alexander Lobakin , Yury Norov , Alexander Potapenko , nex.sw.ncis.osdt.itp.upstreaming@intel.com, intel-wired-lan@lists.osuosl.org, netdev@vger.kernel.org, linux-kernel@vger.kernel.org, Andy Shevchenko Subject: [PATCH net-next v6 02/21] lib/test_bitmap: add tests for bitmap_{read,write}() Date: Wed, 27 Mar 2024 16:23:39 +0100 Message-ID: <20240327152358.2368467-3-aleksander.lobakin@intel.com> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240327152358.2368467-1-aleksander.lobakin@intel.com> References: <20240327152358.2368467-1-aleksander.lobakin@intel.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit From: Alexander Potapenko Add basic tests ensuring that values can be added at arbitrary positions of the bitmap, including those spanning into the adjacent unsigned longs. Two new performance tests, test_bitmap_read_perf() and test_bitmap_write_perf(), can be used to assess future performance improvements of bitmap_read() and bitmap_write(): [ 0.431119][ T1] test_bitmap: Time spent in test_bitmap_read_perf: 615253 [ 0.433197][ T1] test_bitmap: Time spent in test_bitmap_write_perf: 916313 (numbers from a Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz machine running QEMU). Signed-off-by: Alexander Potapenko Reviewed-by: Andy Shevchenko Acked-by: Yury Norov Signed-off-by: Yury Norov Signed-off-by: Alexander Lobakin --- lib/test_bitmap.c | 179 ++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 172 insertions(+), 7 deletions(-) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 6b2b33579f56..9198e93b7985 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -60,18 +60,17 @@ static const unsigned long exp3_1_0[] __initconst = { }; static bool __init -__check_eq_uint(const char *srcfile, unsigned int line, - const unsigned int exp_uint, unsigned int x) +__check_eq_ulong(const char *srcfile, unsigned int line, + const unsigned long exp_ulong, unsigned long x) { - if (exp_uint != x) { - pr_err("[%s:%u] expected %u, got %u\n", - srcfile, line, exp_uint, x); + if (exp_ulong != x) { + pr_err("[%s:%u] expected %lu, got %lu\n", + srcfile, line, exp_ulong, x); return false; } return true; } - static bool __init __check_eq_bitmap(const char *srcfile, unsigned int line, const unsigned long *exp_bmap, const unsigned long *bmap, @@ -185,7 +184,8 @@ __check_eq_str(const char *srcfile, unsigned int line, result; \ }) -#define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__) +#define expect_eq_ulong(...) __expect_eq(ulong, ##__VA_ARGS__) +#define expect_eq_uint(x, y) expect_eq_ulong((unsigned int)(x), (unsigned int)(y)) #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__) #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__) #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__) @@ -1286,6 +1286,168 @@ static void __init test_bitmap_const_eval(void) BUILD_BUG_ON(~var != ~BIT(25)); } +/* + * Test bitmap should be big enough to include the cases when start is not in + * the first word, and start+nbits lands in the following word. + */ +#define TEST_BIT_LEN (1000) + +/* + * Helper function to test bitmap_write() overwriting the chosen byte pattern. + */ +static void __init test_bitmap_write_helper(const char *pattern) +{ + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); + DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN); + DECLARE_BITMAP(pat_bitmap, TEST_BIT_LEN); + unsigned long w, r, bit; + int i, n, nbits; + + /* + * Only parse the pattern once and store the result in the intermediate + * bitmap. + */ + bitmap_parselist(pattern, pat_bitmap, TEST_BIT_LEN); + + /* + * Check that writing a single bit does not accidentally touch the + * adjacent bits. + */ + for (i = 0; i < TEST_BIT_LEN; i++) { + bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN); + bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN); + for (bit = 0; bit <= 1; bit++) { + bitmap_write(bitmap, bit, i, 1); + __assign_bit(i, exp_bitmap, bit); + expect_eq_bitmap(exp_bitmap, bitmap, + TEST_BIT_LEN); + } + } + + /* Ensure writing 0 bits does not change anything. */ + bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN); + bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN); + for (i = 0; i < TEST_BIT_LEN; i++) { + bitmap_write(bitmap, ~0UL, i, 0); + expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN); + } + + for (nbits = BITS_PER_LONG; nbits >= 1; nbits--) { + w = IS_ENABLED(CONFIG_64BIT) ? 0xdeadbeefdeadbeefUL + : 0xdeadbeefUL; + w >>= (BITS_PER_LONG - nbits); + for (i = 0; i <= TEST_BIT_LEN - nbits; i++) { + bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN); + bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN); + for (n = 0; n < nbits; n++) + __assign_bit(i + n, exp_bitmap, w & BIT(n)); + bitmap_write(bitmap, w, i, nbits); + expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN); + r = bitmap_read(bitmap, i, nbits); + expect_eq_ulong(r, w); + } + } +} + +static void __init test_bitmap_read_write(void) +{ + unsigned char *pattern[3] = {"", "all:1/2", "all"}; + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); + unsigned long zero_bits = 0, bits_per_long = BITS_PER_LONG; + unsigned long val; + int i, pi; + + /* + * Reading/writing zero bits should not crash the kernel. + * READ_ONCE() prevents constant folding. + */ + bitmap_write(NULL, 0, 0, READ_ONCE(zero_bits)); + /* Return value of bitmap_read() is undefined here. */ + bitmap_read(NULL, 0, READ_ONCE(zero_bits)); + + /* + * Reading/writing more than BITS_PER_LONG bits should not crash the + * kernel. READ_ONCE() prevents constant folding. + */ + bitmap_write(NULL, 0, 0, READ_ONCE(bits_per_long) + 1); + /* Return value of bitmap_read() is undefined here. */ + bitmap_read(NULL, 0, READ_ONCE(bits_per_long) + 1); + + /* + * Ensure that bitmap_read() reads the same value that was previously + * written, and two consequent values are correctly merged. + * The resulting bit pattern is asymmetric to rule out possible issues + * with bit numeration order. + */ + for (i = 0; i < TEST_BIT_LEN - 7; i++) { + bitmap_zero(bitmap, TEST_BIT_LEN); + + bitmap_write(bitmap, 0b10101UL, i, 5); + val = bitmap_read(bitmap, i, 5); + expect_eq_ulong(0b10101UL, val); + + bitmap_write(bitmap, 0b101UL, i + 5, 3); + val = bitmap_read(bitmap, i + 5, 3); + expect_eq_ulong(0b101UL, val); + + val = bitmap_read(bitmap, i, 8); + expect_eq_ulong(0b10110101UL, val); + } + + for (pi = 0; pi < ARRAY_SIZE(pattern); pi++) + test_bitmap_write_helper(pattern[pi]); +} + +static void __init test_bitmap_read_perf(void) +{ + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); + unsigned int cnt, nbits, i; + unsigned long val; + ktime_t time; + + bitmap_fill(bitmap, TEST_BIT_LEN); + time = ktime_get(); + for (cnt = 0; cnt < 5; cnt++) { + for (nbits = 1; nbits <= BITS_PER_LONG; nbits++) { + for (i = 0; i < TEST_BIT_LEN; i++) { + if (i + nbits > TEST_BIT_LEN) + break; + /* + * Prevent the compiler from optimizing away the + * bitmap_read() by using its value. + */ + WRITE_ONCE(val, bitmap_read(bitmap, i, nbits)); + } + } + } + time = ktime_get() - time; + pr_err("Time spent in %s:\t%llu\n", __func__, time); +} + +static void __init test_bitmap_write_perf(void) +{ + DECLARE_BITMAP(bitmap, TEST_BIT_LEN); + unsigned int cnt, nbits, i; + unsigned long val = 0xfeedface; + ktime_t time; + + bitmap_zero(bitmap, TEST_BIT_LEN); + time = ktime_get(); + for (cnt = 0; cnt < 5; cnt++) { + for (nbits = 1; nbits <= BITS_PER_LONG; nbits++) { + for (i = 0; i < TEST_BIT_LEN; i++) { + if (i + nbits > TEST_BIT_LEN) + break; + bitmap_write(bitmap, val, i, nbits); + } + } + } + time = ktime_get() - time; + pr_err("Time spent in %s:\t%llu\n", __func__, time); +} + +#undef TEST_BIT_LEN + static void __init selftest(void) { test_zero_clear(); @@ -1303,6 +1465,9 @@ static void __init selftest(void) test_bitmap_cut(); test_bitmap_print_buf(); test_bitmap_const_eval(); + test_bitmap_read_write(); + test_bitmap_read_perf(); + test_bitmap_write_perf(); test_find_nth_bit(); test_for_each_set_bit(); -- 2.44.0