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  
cond_wake_up(struct wait_queue_head * wq)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  
cond_wake_up_nomb(struct wait_queue_head * wq)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  
mult_perc(u64 num,u32 percent)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 */
is_power_of_two_u64(u64 n)48  static inline bool is_power_of_two_u64(u64 n)
49  {
50  	return n != 0 && (n & (n - 1)) == 0;
51  }
52  
has_single_bit_set(u64 n)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  
rb_simple_search(const struct rb_root * root,u64 bytenr)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   */
rb_simple_search_first(const struct rb_root * root,u64 bytenr)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  
rb_simple_insert(struct rb_root * root,u64 bytenr,struct rb_node * node)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  
bitmap_test_range_all_set(const unsigned long * addr,unsigned long start,unsigned long nbits)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  
bitmap_test_range_all_zero(const unsigned long * addr,unsigned long start,unsigned long nbits)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