1 | /* |
---|---|

2 | * Test for find_*_bit functions. |

3 | * |

4 | * Copyright (c) 2017 Cavium. |

5 | * |

6 | * This program is free software; you can redistribute it and/or |

7 | * modify it under the terms of version 2 of the GNU General Public |

8 | * License as published by the Free Software Foundation. |

9 | * |

10 | * This program is distributed in the hope that it will be useful, but |

11 | * WITHOUT ANY WARRANTY; without even the implied warranty of |

12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |

13 | * General Public License for more details. |

14 | */ |

15 | |

16 | /* |

17 | * find_bit functions are widely used in kernel, so the successful boot |

18 | * is good enough test for correctness. |

19 | * |

20 | * This test is focused on performance of traversing bitmaps. Two typical |

21 | * scenarios are reproduced: |

22 | * - randomly filled bitmap with approximately equal number of set and |

23 | * cleared bits; |

24 | * - sparse bitmap with few set bits at random positions. |

25 | */ |

26 | |

27 | #include <linux/bitops.h> |

28 | #include <linux/kernel.h> |

29 | #include <linux/list.h> |

30 | #include <linux/module.h> |

31 | #include <linux/printk.h> |

32 | #include <linux/random.h> |

33 | |

34 | #define BITMAP_LEN (4096UL * 8 * 10) |

35 | #define SPARSE 500 |

36 | |

37 | static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; |

38 | static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; |

39 | |

40 | /* |

41 | * This is Schlemiel the Painter's algorithm. It should be called after |

42 | * all other tests for the same bitmap because it sets all bits of bitmap to 1. |

43 | */ |

44 | static int __init test_find_first_bit(void *bitmap, unsigned long len) |

45 | { |

46 | unsigned long i, cnt; |

47 | ktime_t time; |

48 | |

49 | time = ktime_get(); |

50 | for (cnt = i = 0; i < len; cnt++) { |

51 | i = find_first_bit(bitmap, len); |

52 | __clear_bit(i, bitmap); |

53 | } |

54 | time = ktime_get() - time; |

55 | pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); |

56 | |

57 | return 0; |

58 | } |

59 | |

60 | static int __init test_find_next_bit(const void *bitmap, unsigned long len) |

61 | { |

62 | unsigned long i, cnt; |

63 | ktime_t time; |

64 | |

65 | time = ktime_get(); |

66 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) |

67 | i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; |

68 | time = ktime_get() - time; |

69 | pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); |

70 | |

71 | return 0; |

72 | } |

73 | |

74 | static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) |

75 | { |

76 | unsigned long i, cnt; |

77 | ktime_t time; |

78 | |

79 | time = ktime_get(); |

80 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) |

81 | i = find_next_zero_bit(bitmap, len, i) + 1; |

82 | time = ktime_get() - time; |

83 | pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); |

84 | |

85 | return 0; |

86 | } |

87 | |

88 | static int __init test_find_last_bit(const void *bitmap, unsigned long len) |

89 | { |

90 | unsigned long l, cnt = 0; |

91 | ktime_t time; |

92 | |

93 | time = ktime_get(); |

94 | do { |

95 | cnt++; |

96 | l = find_last_bit(bitmap, len); |

97 | if (l >= len) |

98 | break; |

99 | len = l; |

100 | } while (len); |

101 | time = ktime_get() - time; |

102 | pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); |

103 | |

104 | return 0; |

105 | } |

106 | |

107 | static int __init test_find_next_and_bit(const void *bitmap, |

108 | const void *bitmap2, unsigned long len) |

109 | { |

110 | unsigned long i, cnt; |

111 | ktime_t time; |

112 | |

113 | time = ktime_get(); |

114 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) |

115 | i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); |

116 | time = ktime_get() - time; |

117 | pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); |

118 | |

119 | return 0; |

120 | } |

121 | |

122 | static int __init find_bit_test(void) |

123 | { |

124 | unsigned long nbits = BITMAP_LEN / SPARSE; |

125 | |

126 | pr_err("\nStart testing find_bit() with random-filled bitmap\n"); |

127 | |

128 | get_random_bytes(bitmap, sizeof(bitmap)); |

129 | get_random_bytes(bitmap2, sizeof(bitmap2)); |

130 | |

131 | test_find_next_bit(bitmap, BITMAP_LEN); |

132 | test_find_next_zero_bit(bitmap, BITMAP_LEN); |

133 | test_find_last_bit(bitmap, BITMAP_LEN); |

134 | |

135 | /* |

136 | * test_find_first_bit() may take some time, so |

137 | * traverse only part of bitmap to avoid soft lockup. |

138 | */ |

139 | test_find_first_bit(bitmap, BITMAP_LEN / 10); |

140 | test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |

141 | |

142 | pr_err("\nStart testing find_bit() with sparse bitmap\n"); |

143 | |

144 | bitmap_zero(bitmap, BITMAP_LEN); |

145 | bitmap_zero(bitmap2, BITMAP_LEN); |

146 | |

147 | while (nbits--) { |

148 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap); |

149 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap2); |

150 | } |

151 | |

152 | test_find_next_bit(bitmap, BITMAP_LEN); |

153 | test_find_next_zero_bit(bitmap, BITMAP_LEN); |

154 | test_find_last_bit(bitmap, BITMAP_LEN); |

155 | test_find_first_bit(bitmap, BITMAP_LEN); |

156 | test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |

157 | |

158 | /* |

159 | * Everything is OK. Return error just to let user run benchmark |

160 | * again without annoying rmmod. |

161 | */ |

162 | return -EINVAL; |

163 | } |

164 | module_init(find_bit_test); |

165 | |

166 | MODULE_LICENSE("GPL"); |

167 |