1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Benchmark find_next_bit and related bit operations.
4 *
5 * Copyright 2020 Google LLC.
6 */
7#include <stdlib.h>
8#include "bench.h"
9#include "../util/stat.h"
10#include <linux/bitmap.h>
11#include <linux/bitops.h>
12#include <linux/time64.h>
13#include <subcmd/parse-options.h>
14
15static unsigned int outer_iterations = 5;
16static unsigned int inner_iterations = 100000;
17
18static const struct option options[] = {
19	OPT_UINTEGER('i', "outer-iterations", &outer_iterations,
20		"Number of outer iterations used"),
21	OPT_UINTEGER('j', "inner-iterations", &inner_iterations,
22		"Number of inner iterations used"),
23	OPT_END()
24};
25
26static const char *const bench_usage[] = {
27	"perf bench mem find_bit <options>",
28	NULL
29};
30
31static unsigned int accumulator;
32static unsigned int use_of_val;
33
34static noinline void workload(int val)
35{
36	use_of_val += val;
37	accumulator++;
38}
39
40#if (defined(__i386__) || defined(__x86_64__)) && defined(__GCC_ASM_FLAG_OUTPUTS__)
41static bool asm_test_bit(long nr, const unsigned long *addr)
42{
43	bool oldbit;
44
45	asm volatile("bt %2,%1"
46		     : "=@ccc" (oldbit)
47		     : "m" (*(unsigned long *)addr), "Ir" (nr) : "memory");
48
49	return oldbit;
50}
51#else
52#define asm_test_bit test_bit
53#endif
54
55static int do_for_each_set_bit(unsigned int num_bits)
56{
57	unsigned long *to_test = bitmap_alloc(num_bits);
58	struct timeval start, end, diff;
59	u64 runtime_us;
60	struct stats fb_time_stats, tb_time_stats;
61	double time_average, time_stddev;
62	unsigned int bit, i, j;
63	unsigned int set_bits, skip;
64	unsigned int old;
65
66	init_stats(&fb_time_stats);
67	init_stats(&tb_time_stats);
68
69	for (set_bits = 1; set_bits <= num_bits; set_bits <<= 1) {
70		bitmap_zero(to_test, num_bits);
71		skip = num_bits / set_bits;
72		for (i = 0; i < num_bits; i += skip)
73			set_bit(i, to_test);
74
75		for (i = 0; i < outer_iterations; i++) {
76			old = accumulator;
77			gettimeofday(&start, NULL);
78			for (j = 0; j < inner_iterations; j++) {
79				for_each_set_bit(bit, to_test, num_bits)
80					workload(bit);
81			}
82			gettimeofday(&end, NULL);
83			assert(old + (inner_iterations * set_bits) == accumulator);
84			timersub(&end, &start, &diff);
85			runtime_us = diff.tv_sec * USEC_PER_SEC + diff.tv_usec;
86			update_stats(&fb_time_stats, runtime_us);
87
88			old = accumulator;
89			gettimeofday(&start, NULL);
90			for (j = 0; j < inner_iterations; j++) {
91				for (bit = 0; bit < num_bits; bit++) {
92					if (asm_test_bit(bit, to_test))
93						workload(bit);
94				}
95			}
96			gettimeofday(&end, NULL);
97			assert(old + (inner_iterations * set_bits) == accumulator);
98			timersub(&end, &start, &diff);
99			runtime_us = diff.tv_sec * USEC_PER_SEC + diff.tv_usec;
100			update_stats(&tb_time_stats, runtime_us);
101		}
102
103		printf("%d operations %d bits set of %d bits\n",
104			inner_iterations, set_bits, num_bits);
105		time_average = avg_stats(&fb_time_stats);
106		time_stddev = stddev_stats(&fb_time_stats);
107		printf("  Average for_each_set_bit took: %.3f usec (+- %.3f usec)\n",
108			time_average, time_stddev);
109		time_average = avg_stats(&tb_time_stats);
110		time_stddev = stddev_stats(&tb_time_stats);
111		printf("  Average test_bit loop took:    %.3f usec (+- %.3f usec)\n",
112			time_average, time_stddev);
113
114		if (use_of_val == accumulator)  /* Try to avoid compiler tricks. */
115			printf("\n");
116	}
117	bitmap_free(to_test);
118	return 0;
119}
120
121int bench_mem_find_bit(int argc, const char **argv)
122{
123	int err = 0, i;
124
125	argc = parse_options(argc, argv, options, bench_usage, 0);
126	if (argc) {
127		usage_with_options(bench_usage, options);
128		exit(EXIT_FAILURE);
129	}
130
131	for (i = 1; i <= 2048; i <<= 1)
132		do_for_each_set_bit(i);
133
134	return err;
135}
136