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 
cond_wake_up(struct wait_queue_head * wq)13 static inline void cond_wake_up(struct wait_queue_head *wq)
14 {
15 	/*
16 	 * This implies a full smp_mb barrier, see comments for
17 	 * waitqueue_active why.
18 	 */
19 	if (wq_has_sleeper(wq))
20 		wake_up(wq);
21 }
22 
cond_wake_up_nomb(struct wait_queue_head * wq)23 static inline void cond_wake_up_nomb(struct wait_queue_head *wq)
24 {
25 	/*
26 	 * Special case for conditional wakeup where the barrier required for
27 	 * waitqueue_active is implied by some of the preceding code. Eg. one
28 	 * of such atomic operations (atomic_dec_and_return, ...), or a
29 	 * unlock/lock sequence, etc.
30 	 */
31 	if (waitqueue_active(wq))
32 		wake_up(wq);
33 }
34 
div_factor(u64 num,int factor)35 static inline u64 div_factor(u64 num, int factor)
36 {
37 	if (factor == 10)
38 		return num;
39 	num *= factor;
40 	return div_u64(num, 10);
41 }
42 
div_factor_fine(u64 num,int factor)43 static inline u64 div_factor_fine(u64 num, int factor)
44 {
45 	if (factor == 100)
46 		return num;
47 	num *= factor;
48 	return div_u64(num, 100);
49 }
50 
51 /* Copy of is_power_of_two that is 64bit safe */
is_power_of_two_u64(u64 n)52 static inline bool is_power_of_two_u64(u64 n)
53 {
54 	return n != 0 && (n & (n - 1)) == 0;
55 }
56 
has_single_bit_set(u64 n)57 static inline bool has_single_bit_set(u64 n)
58 {
59 	return is_power_of_two_u64(n);
60 }
61 
62 /*
63  * Simple bytenr based rb_tree relate structures
64  *
65  * Any structure wants to use bytenr as single search index should have their
66  * structure start with these members.
67  */
68 struct rb_simple_node {
69 	struct rb_node rb_node;
70 	u64 bytenr;
71 };
72 
rb_simple_search(struct rb_root * root,u64 bytenr)73 static inline struct rb_node *rb_simple_search(struct rb_root *root, u64 bytenr)
74 {
75 	struct rb_node *node = root->rb_node;
76 	struct rb_simple_node *entry;
77 
78 	while (node) {
79 		entry = rb_entry(node, struct rb_simple_node, rb_node);
80 
81 		if (bytenr < entry->bytenr)
82 			node = node->rb_left;
83 		else if (bytenr > entry->bytenr)
84 			node = node->rb_right;
85 		else
86 			return node;
87 	}
88 	return NULL;
89 }
90 
91 /*
92  * Search @root from an entry that starts or comes after @bytenr.
93  *
94  * @root:	the root to search.
95  * @bytenr:	bytenr to search from.
96  *
97  * Return the rb_node that start at or after @bytenr.  If there is no entry at
98  * or after @bytner return NULL.
99  */
rb_simple_search_first(struct rb_root * root,u64 bytenr)100 static inline struct rb_node *rb_simple_search_first(struct rb_root *root,
101 						     u64 bytenr)
102 {
103 	struct rb_node *node = root->rb_node, *ret = NULL;
104 	struct rb_simple_node *entry, *ret_entry = NULL;
105 
106 	while (node) {
107 		entry = rb_entry(node, struct rb_simple_node, rb_node);
108 
109 		if (bytenr < entry->bytenr) {
110 			if (!ret || entry->bytenr < ret_entry->bytenr) {
111 				ret = node;
112 				ret_entry = entry;
113 			}
114 
115 			node = node->rb_left;
116 		} else if (bytenr > entry->bytenr) {
117 			node = node->rb_right;
118 		} else {
119 			return node;
120 		}
121 	}
122 
123 	return ret;
124 }
125 
rb_simple_insert(struct rb_root * root,u64 bytenr,struct rb_node * node)126 static inline struct rb_node *rb_simple_insert(struct rb_root *root, u64 bytenr,
127 					       struct rb_node *node)
128 {
129 	struct rb_node **p = &root->rb_node;
130 	struct rb_node *parent = NULL;
131 	struct rb_simple_node *entry;
132 
133 	while (*p) {
134 		parent = *p;
135 		entry = rb_entry(parent, struct rb_simple_node, rb_node);
136 
137 		if (bytenr < entry->bytenr)
138 			p = &(*p)->rb_left;
139 		else if (bytenr > entry->bytenr)
140 			p = &(*p)->rb_right;
141 		else
142 			return parent;
143 	}
144 
145 	rb_link_node(node, parent, p);
146 	rb_insert_color(node, root);
147 	return NULL;
148 }
149 
150 #endif
151