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 #include <linux/bio.h> 15 16 /* 17 * Enumerate bits using enum autoincrement. Define the @name as the n-th bit. 18 */ 19 #define ENUM_BIT(name) \ 20 __ ## name ## _BIT, \ 21 name = (1U << __ ## name ## _BIT), \ 22 __ ## name ## _SEQ = __ ## name ## _BIT 23 24 static inline phys_addr_t bio_iter_phys(struct bio *bio, struct bvec_iter *iter) 25 { 26 struct bio_vec bv = bio_iter_iovec(bio, *iter); 27 28 return bvec_phys(&bv); 29 } 30 31 /* 32 * Iterate bio using btrfs block size. 33 * 34 * This will handle large folio and highmem. 35 * 36 * @paddr: Physical memory address of each iteration 37 * @bio: The bio to iterate 38 * @iter: The bvec_iter (pointer) to use. 39 * @blocksize: The blocksize to iterate. 40 * 41 * This requires all folios in the bio to cover at least one block. 42 */ 43 #define btrfs_bio_for_each_block(paddr, bio, iter, blocksize) \ 44 for (; (iter)->bi_size && \ 45 (paddr = bio_iter_phys((bio), (iter)), 1); \ 46 bio_advance_iter_single((bio), (iter), (blocksize))) 47 48 /* Initialize a bvec_iter to the size of the specified bio. */ 49 static inline struct bvec_iter init_bvec_iter_for_bio(struct bio *bio) 50 { 51 struct bio_vec *bvec; 52 u32 bio_size = 0; 53 int i; 54 55 bio_for_each_bvec_all(bvec, bio, i) 56 bio_size += bvec->bv_len; 57 58 return (struct bvec_iter) { 59 .bi_sector = 0, 60 .bi_size = bio_size, 61 .bi_idx = 0, 62 .bi_bvec_done = 0, 63 }; 64 } 65 66 #define btrfs_bio_for_each_block_all(paddr, bio, blocksize) \ 67 for (struct bvec_iter iter = init_bvec_iter_for_bio(bio); \ 68 (iter).bi_size && \ 69 (paddr = bio_iter_phys((bio), &(iter)), 1); \ 70 bio_advance_iter_single((bio), &(iter), (blocksize))) 71 72 static inline void cond_wake_up(struct wait_queue_head *wq) 73 { 74 /* 75 * This implies a full smp_mb barrier, see comments for 76 * waitqueue_active why. 77 */ 78 if (wq_has_sleeper(wq)) 79 wake_up(wq); 80 } 81 82 static inline void cond_wake_up_nomb(struct wait_queue_head *wq) 83 { 84 /* 85 * Special case for conditional wakeup where the barrier required for 86 * waitqueue_active is implied by some of the preceding code. Eg. one 87 * of such atomic operations (atomic_dec_and_return, ...), or a 88 * unlock/lock sequence, etc. 89 */ 90 if (waitqueue_active(wq)) 91 wake_up(wq); 92 } 93 94 static inline u64 mult_perc(u64 num, u32 percent) 95 { 96 return div_u64(num * percent, 100); 97 } 98 /* Copy of is_power_of_two that is 64bit safe */ 99 static inline bool is_power_of_two_u64(u64 n) 100 { 101 return n != 0 && (n & (n - 1)) == 0; 102 } 103 104 static inline bool has_single_bit_set(u64 n) 105 { 106 return is_power_of_two_u64(n); 107 } 108 109 /* 110 * Simple bytenr based rb_tree relate structures 111 * 112 * Any structure wants to use bytenr as single search index should have their 113 * structure start with these members. 114 */ 115 struct rb_simple_node { 116 struct rb_node rb_node; 117 u64 bytenr; 118 }; 119 120 static inline struct rb_node *rb_simple_search(const struct rb_root *root, u64 bytenr) 121 { 122 struct rb_node *node = root->rb_node; 123 struct rb_simple_node *entry; 124 125 while (node) { 126 entry = rb_entry(node, struct rb_simple_node, rb_node); 127 128 if (bytenr < entry->bytenr) 129 node = node->rb_left; 130 else if (bytenr > entry->bytenr) 131 node = node->rb_right; 132 else 133 return node; 134 } 135 return NULL; 136 } 137 138 /* 139 * Search @root from an entry that starts or comes after @bytenr. 140 * 141 * @root: the root to search. 142 * @bytenr: bytenr to search from. 143 * 144 * Return the rb_node that start at or after @bytenr. If there is no entry at 145 * or after @bytner return NULL. 146 */ 147 static inline struct rb_node *rb_simple_search_first(const struct rb_root *root, 148 u64 bytenr) 149 { 150 struct rb_node *node = root->rb_node, *ret = NULL; 151 struct rb_simple_node *entry, *ret_entry = NULL; 152 153 while (node) { 154 entry = rb_entry(node, struct rb_simple_node, rb_node); 155 156 if (bytenr < entry->bytenr) { 157 if (!ret || entry->bytenr < ret_entry->bytenr) { 158 ret = node; 159 ret_entry = entry; 160 } 161 162 node = node->rb_left; 163 } else if (bytenr > entry->bytenr) { 164 node = node->rb_right; 165 } else { 166 return node; 167 } 168 } 169 170 return ret; 171 } 172 173 static int rb_simple_node_bytenr_cmp(struct rb_node *new, const struct rb_node *existing) 174 { 175 struct rb_simple_node *new_entry = rb_entry(new, struct rb_simple_node, rb_node); 176 struct rb_simple_node *existing_entry = rb_entry(existing, struct rb_simple_node, rb_node); 177 178 if (new_entry->bytenr < existing_entry->bytenr) 179 return -1; 180 else if (new_entry->bytenr > existing_entry->bytenr) 181 return 1; 182 183 return 0; 184 } 185 186 static inline struct rb_node *rb_simple_insert(struct rb_root *root, 187 struct rb_simple_node *simple_node) 188 { 189 return rb_find_add(&simple_node->rb_node, root, rb_simple_node_bytenr_cmp); 190 } 191 192 static inline bool bitmap_test_range_all_set(const unsigned long *addr, 193 unsigned long start, 194 unsigned long nbits) 195 { 196 unsigned long found_zero; 197 198 found_zero = find_next_zero_bit(addr, start + nbits, start); 199 return (found_zero == start + nbits); 200 } 201 202 static inline bool bitmap_test_range_all_zero(const unsigned long *addr, 203 unsigned long start, 204 unsigned long nbits) 205 { 206 unsigned long found_set; 207 208 found_set = find_next_bit(addr, start + nbits, start); 209 return (found_set == start + nbits); 210 } 211 212 static inline u64 folio_end(struct folio *folio) 213 { 214 return folio_pos(folio) + folio_size(folio); 215 } 216 217 #endif 218