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