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