Commit | Line | Data |
---|---|---|
602cbe91 DS |
1 | /* SPDX-License-Identifier: GPL-2.0 */ |
2 | ||
3 | #ifndef BTRFS_MISC_H | |
4 | #define BTRFS_MISC_H | |
5 | ||
602035d7 DS |
6 | #include <linux/types.h> |
7 | #include <linux/bitmap.h> | |
602cbe91 DS |
8 | #include <linux/sched.h> |
9 | #include <linux/wait.h> | |
cde7417c | 10 | #include <linux/math64.h> |
e9a28dc5 | 11 | #include <linux/rbtree.h> |
602cbe91 | 12 | |
d549ff7b DS |
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 | ||
602cbe91 DS |
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)) | |
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)) | |
40 | wake_up(wq); | |
41 | } | |
42 | ||
428c8e03 | 43 | static inline u64 mult_perc(u64 num, u32 percent) |
784352fe | 44 | { |
428c8e03 | 45 | return div_u64(num * percent, 100); |
784352fe | 46 | } |
79c8264e DS |
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 | ||
e9a28dc5 QW |
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 | ||
2917f741 | 69 | static inline struct rb_node *rb_simple_search(const struct rb_root *root, u64 bytenr) |
e9a28dc5 QW |
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 | ||
87c11705 JB |
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 | */ | |
2917f741 | 96 | static inline struct rb_node *rb_simple_search_first(const struct rb_root *root, |
87c11705 JB |
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 | ||
e9a28dc5 QW |
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, p); | |
142 | rb_insert_color(node, root); | |
143 | return NULL; | |
144 | } | |
145 | ||
b5345d6c NA |
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, start + nbits, 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, start + nbits, start); | |
163 | return (found_set == start + nbits); | |
164 | } | |
165 | ||
602cbe91 | 166 | #endif |