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