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))
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
43 static inline u64 mult_perc(u64 num, u32 percent)
44 {
45 return div_u64(num * percent, 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(const 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(const 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, 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, 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
166 #endif
167
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.