xref: /openbmc/linux/fs/btrfs/misc.h (revision aaa746ad)
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 #define in_range(b, first, len) ((b) >= (first) && (b) < (first) + (len))
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(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, p);
142 	rb_insert_color(node, root);
143 	return NULL;
144 }
145 
146 #endif
147