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 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 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 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 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 */ 52 static inline bool is_power_of_two_u64(u64 n) 53 { 54 return n != 0 && (n & (n - 1)) == 0; 55 } 56 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 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 */ 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 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