| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20240830191043.1028827-6-mathieu.desnoyers@efficios.com>
Date: Fri, 30 Aug 2024 15:10:42 -0400
From: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To: Yury Norov <yury.norov@...il.com>,
Rasmus Villemoes <linux@...musvillemoes.dk>
Cc: linux-kernel@...r.kernel.org,
Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Subject: [PATCH v3 5/6] lib: benchmark bitmap sets binary operation find
Benchmark the following bitmap find functions applying binary operations
on sets of two bitmaps:
- find_first_andnot_bit,
- find_first_nor_bit,
- find_next_andnot_bit,
- find_next_nor_bit,
- find_next_or_bit.
Note that find_first_or_bit is not part of the current API, so it is not
covered.
Use "len" parameters rather than BITMAP_LEN within all benchmark
functions (changed across the whole file).
Example output:
(AMD EPYC 9654 96-Core Processor)
Start testing find_bit() with random-filled bitmap
find_next_bit: 595816 ns, 163603 iterations
find_next_zero_bit: 613227 ns, 164078 iterations
find_last_bit: 464619 ns, 163602 iterations
find_nth_bit: 2647830 ns, 16413 iterations
find_first_bit: 1240485 ns, 16414 iterations
find_first_and_bit: 623258 ns, 8136 iterations
find_next_and_bit: 321039 ns, 81576 iterations
find_first_andnot_bit: 929316 ns, 8279 iterations
find_next_andnot_bit: 324820 ns, 82027 iterations
find_first_nor_bit: 971359 ns, 8241 iterations
find_next_nor_bit: 346981 ns, 82058 iterations
find_next_or_bit: 882343 ns, 245623 iterations
Start testing find_bit() with sparse bitmap
find_next_bit: 8751 ns, 656 iterations
find_next_zero_bit: 1184552 ns, 327025 iterations
find_last_bit: 8820 ns, 656 iterations
find_nth_bit: 1111597 ns, 655 iterations
find_first_bit: 4980 ns, 59 iterations
find_first_and_bit: 550 ns, 1 iterations
find_next_and_bit: 3110 ns, 1 iterations
find_first_andnot_bit: 7420 ns, 59 iterations
find_next_andnot_bit: 9500 ns, 656 iterations
find_first_nor_bit: 3889256 ns, 32647 iterations
find_next_nor_bit: 1254026 ns, 326370 iterations
find_next_or_bit: 14341 ns, 1311 iterations
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Yury Norov <yury.norov@...il.com>
Cc: Rasmus Villemoes <linux@...musvillemoes.dk>
---
Changes since v2:
- Use bitmap_alloc rather than a local static variable for bitmaps.
- Divide BITMAP_LEN by 10 for all find_first tests to ensure the test
runs fast enough (a few ms per test).
- Fix alignment of text output.
- Clear/set bits only within range, fixing an out-of-bound access.
- Use "len" parameters rather than BITMAP_LEN within all benchmark
functions (changed across the whole file).
---
lib/find_bit_benchmark.c | 119 +++++++++++++++++++++++++++++++++++----
1 file changed, 107 insertions(+), 12 deletions(-)
diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 81d358fb459b..5ab72829e7ee 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -47,7 +47,7 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)
__clear_bit(i, cp);
}
time = ktime_get() - time;
- pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt);
+ pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt);
return 0;
}
@@ -67,7 +67,47 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
__clear_bit(i, cp);
}
time = ktime_get() - time;
- pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+ pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+ return 0;
+}
+
+static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
+{
+ unsigned long *cp __free(bitmap) = bitmap_alloc(len, GFP_KERNEL);
+ unsigned long i, cnt;
+ ktime_t time;
+
+ bitmap_copy(cp, bitmap, len);
+
+ time = ktime_get();
+ for (cnt = i = 0; i < len; cnt++) {
+ i = find_first_andnot_bit(cp, bitmap2, len);
+ if (i < len)
+ __clear_bit(i, cp);
+ }
+ time = ktime_get() - time;
+ pr_err("find_first_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+ return 0;
+}
+
+static int __init test_find_first_nor_bit(void *bitmap, const void *bitmap2, unsigned long len)
+{
+ unsigned long *cp __free(bitmap) = bitmap_alloc(len, GFP_KERNEL);
+ unsigned long i, cnt;
+ ktime_t time;
+
+ bitmap_copy(cp, bitmap, len);
+
+ time = ktime_get();
+ for (cnt = i = 0; i < len; cnt++) {
+ i = find_first_nor_bit(cp, bitmap2, len);
+ if (i < len)
+ __set_bit(i, cp);
+ }
+ time = ktime_get() - time;
+ pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
return 0;
}
@@ -78,10 +118,10 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len)
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < BITMAP_LEN; cnt++)
- i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
+ for (cnt = i = 0; i < len; cnt++)
+ i = find_next_bit(bitmap, len, i) + 1;
time = ktime_get() - time;
- pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt);
+ pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt);
return 0;
}
@@ -92,10 +132,10 @@ static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < BITMAP_LEN; cnt++)
+ for (cnt = i = 0; i < len; cnt++)
i = find_next_zero_bit(bitmap, len, i) + 1;
time = ktime_get() - time;
- pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
+ pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
return 0;
}
@@ -114,7 +154,7 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
len = l;
} while (len);
time = ktime_get() - time;
- pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt);
+ pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt);
return 0;
}
@@ -130,7 +170,7 @@ static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long l
WARN_ON(l >= len);
}
time = ktime_get() - time;
- pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w);
+ pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w);
return 0;
}
@@ -142,10 +182,55 @@ static int __init test_find_next_and_bit(const void *bitmap,
ktime_t time;
time = ktime_get();
- for (cnt = i = 0; i < BITMAP_LEN; cnt++)
- i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
+ for (cnt = i = 0; i < len; cnt++)
+ i = find_next_and_bit(bitmap, bitmap2, len, i + 1);
+ time = ktime_get() - time;
+ pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+ return 0;
+}
+
+static int __init test_find_next_andnot_bit(const void *bitmap,
+ const void *bitmap2, unsigned long len)
+{
+ unsigned long i, cnt;
+ ktime_t time;
+
+ time = ktime_get();
+ for (cnt = i = 0; i < len; cnt++)
+ i = find_next_andnot_bit(bitmap, bitmap2, len, i + 1);
+ time = ktime_get() - time;
+ pr_err("find_next_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+ return 0;
+}
+
+static int __init test_find_next_nor_bit(const void *bitmap,
+ const void *bitmap2, unsigned long len)
+{
+ unsigned long i, cnt;
+ ktime_t time;
+
+ time = ktime_get();
+ for (cnt = i = 0; i < len; cnt++)
+ i = find_next_nor_bit(bitmap, bitmap2, len, i + 1);
+ time = ktime_get() - time;
+ pr_err("find_next_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+ return 0;
+}
+
+static int __init test_find_next_or_bit(const void *bitmap,
+ const void *bitmap2, unsigned long len)
+{
+ unsigned long i, cnt;
+ ktime_t time;
+
+ time = ktime_get();
+ for (cnt = i = 0; i < len; cnt++)
+ i = find_next_or_bit(bitmap, bitmap2, len, i + 1);
time = ktime_get() - time;
- pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+ pr_err("find_next_or_bit: %18llu ns, %6ld iterations\n", time, cnt);
return 0;
}
@@ -171,6 +256,11 @@ static int __init find_bit_test(void)
test_find_first_bit(bitmap, BITMAP_LEN / 10);
test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10);
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
+ test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+ test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+ test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+ test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
+ test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
pr_err("\nStart testing find_bit() with sparse bitmap\n");
@@ -189,6 +279,11 @@ static int __init find_bit_test(void)
test_find_first_bit(bitmap, BITMAP_LEN / 10);
test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10);
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
+ test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+ test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+ test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+ test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
+ test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
/*
* Everything is OK. Return error just to let user run benchmark
--
2.39.2
Powered by blists - more mailing lists