1 | /* SPDX-License-Identifier: GPL-2.0 */ |
2 | |
3 | #ifndef BTRFS_MISC_H |
4 | #define BTRFS_MISC_H |
5 | |
6 | #include <linux/sched.h> |
7 | #include <linux/wait.h> |
8 | #include <linux/math64.h> |
9 | #include <linux/rbtree.h> |
10 | |
11 | /* |
12 | * Enumerate bits using enum autoincrement. Define the @name as the n-th bit. |
13 | */ |
14 | #define ENUM_BIT(name) \ |
15 | __ ## name ## _BIT, \ |
16 | name = (1U << __ ## name ## _BIT), \ |
17 | __ ## name ## _SEQ = __ ## name ## _BIT |
18 | |
19 | static inline void cond_wake_up(struct wait_queue_head *wq) |
20 | { |
21 | /* |
22 | * This implies a full smp_mb barrier, see comments for |
23 | * waitqueue_active why. |
24 | */ |
25 | if (wq_has_sleeper(wq_head: wq)) |
26 | wake_up(wq); |
27 | } |
28 | |
29 | static inline void cond_wake_up_nomb(struct wait_queue_head *wq) |
30 | { |
31 | /* |
32 | * Special case for conditional wakeup where the barrier required for |
33 | * waitqueue_active is implied by some of the preceding code. Eg. one |
34 | * of such atomic operations (atomic_dec_and_return, ...), or a |
35 | * unlock/lock sequence, etc. |
36 | */ |
37 | if (waitqueue_active(wq_head: wq)) |
38 | wake_up(wq); |
39 | } |
40 | |
41 | static inline u64 mult_perc(u64 num, u32 percent) |
42 | { |
43 | return div_u64(dividend: num * percent, divisor: 100); |
44 | } |
45 | /* Copy of is_power_of_two that is 64bit safe */ |
46 | static inline bool is_power_of_two_u64(u64 n) |
47 | { |
48 | return n != 0 && (n & (n - 1)) == 0; |
49 | } |
50 | |
51 | static inline bool has_single_bit_set(u64 n) |
52 | { |
53 | return is_power_of_two_u64(n); |
54 | } |
55 | |
56 | /* |
57 | * Simple bytenr based rb_tree relate structures |
58 | * |
59 | * Any structure wants to use bytenr as single search index should have their |
60 | * structure start with these members. |
61 | */ |
62 | struct rb_simple_node { |
63 | struct rb_node rb_node; |
64 | u64 bytenr; |
65 | }; |
66 | |
67 | static inline struct rb_node *rb_simple_search(struct rb_root *root, u64 bytenr) |
68 | { |
69 | struct rb_node *node = root->rb_node; |
70 | struct rb_simple_node *entry; |
71 | |
72 | while (node) { |
73 | entry = rb_entry(node, struct rb_simple_node, rb_node); |
74 | |
75 | if (bytenr < entry->bytenr) |
76 | node = node->rb_left; |
77 | else if (bytenr > entry->bytenr) |
78 | node = node->rb_right; |
79 | else |
80 | return node; |
81 | } |
82 | return NULL; |
83 | } |
84 | |
85 | /* |
86 | * Search @root from an entry that starts or comes after @bytenr. |
87 | * |
88 | * @root: the root to search. |
89 | * @bytenr: bytenr to search from. |
90 | * |
91 | * Return the rb_node that start at or after @bytenr. If there is no entry at |
92 | * or after @bytner return NULL. |
93 | */ |
94 | static inline struct rb_node *rb_simple_search_first(struct rb_root *root, |
95 | u64 bytenr) |
96 | { |
97 | struct rb_node *node = root->rb_node, *ret = NULL; |
98 | struct rb_simple_node *entry, *ret_entry = NULL; |
99 | |
100 | while (node) { |
101 | entry = rb_entry(node, struct rb_simple_node, rb_node); |
102 | |
103 | if (bytenr < entry->bytenr) { |
104 | if (!ret || entry->bytenr < ret_entry->bytenr) { |
105 | ret = node; |
106 | ret_entry = entry; |
107 | } |
108 | |
109 | node = node->rb_left; |
110 | } else if (bytenr > entry->bytenr) { |
111 | node = node->rb_right; |
112 | } else { |
113 | return node; |
114 | } |
115 | } |
116 | |
117 | return ret; |
118 | } |
119 | |
120 | static inline struct rb_node *rb_simple_insert(struct rb_root *root, u64 bytenr, |
121 | struct rb_node *node) |
122 | { |
123 | struct rb_node **p = &root->rb_node; |
124 | struct rb_node *parent = NULL; |
125 | struct rb_simple_node *entry; |
126 | |
127 | while (*p) { |
128 | parent = *p; |
129 | entry = rb_entry(parent, struct rb_simple_node, rb_node); |
130 | |
131 | if (bytenr < entry->bytenr) |
132 | p = &(*p)->rb_left; |
133 | else if (bytenr > entry->bytenr) |
134 | p = &(*p)->rb_right; |
135 | else |
136 | return parent; |
137 | } |
138 | |
139 | rb_link_node(node, parent, rb_link: p); |
140 | rb_insert_color(node, root); |
141 | return NULL; |
142 | } |
143 | |
144 | static inline bool bitmap_test_range_all_set(const unsigned long *addr, |
145 | unsigned long start, |
146 | unsigned long nbits) |
147 | { |
148 | unsigned long found_zero; |
149 | |
150 | found_zero = find_next_zero_bit(addr, size: start + nbits, offset: start); |
151 | return (found_zero == start + nbits); |
152 | } |
153 | |
154 | static inline bool bitmap_test_range_all_zero(const unsigned long *addr, |
155 | unsigned long start, |
156 | unsigned long nbits) |
157 | { |
158 | unsigned long found_set; |
159 | |
160 | found_set = find_next_bit(addr, size: start + nbits, offset: start); |
161 | return (found_set == start + nbits); |
162 | } |
163 | |
164 | #endif |
165 | |