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