1602cbe91SDavid Sterba /* SPDX-License-Identifier: GPL-2.0 */ 2602cbe91SDavid Sterba 3602cbe91SDavid Sterba #ifndef BTRFS_MISC_H 4602cbe91SDavid Sterba #define BTRFS_MISC_H 5602cbe91SDavid Sterba 6602cbe91SDavid Sterba #include <linux/sched.h> 7602cbe91SDavid Sterba #include <linux/wait.h> 8cde7417cSKari Argillander #include <linux/math64.h> 9e9a28dc5SQu Wenruo #include <linux/rbtree.h> 10602cbe91SDavid Sterba 11602cbe91SDavid Sterba #define in_range(b, first, len) ((b) >= (first) && (b) < (first) + (len)) 12602cbe91SDavid Sterba 13*d549ff7bSDavid Sterba /* 14*d549ff7bSDavid Sterba * Enumerate bits using enum autoincrement. Define the @name as the n-th bit. 15*d549ff7bSDavid Sterba */ 16*d549ff7bSDavid Sterba #define ENUM_BIT(name) \ 17*d549ff7bSDavid Sterba __ ## name ## _BIT, \ 18*d549ff7bSDavid Sterba name = (1U << __ ## name ## _BIT), \ 19*d549ff7bSDavid Sterba __ ## name ## _SEQ = __ ## name ## _BIT 20*d549ff7bSDavid Sterba 21602cbe91SDavid Sterba static inline void cond_wake_up(struct wait_queue_head *wq) 22602cbe91SDavid Sterba { 23602cbe91SDavid Sterba /* 24602cbe91SDavid Sterba * This implies a full smp_mb barrier, see comments for 25602cbe91SDavid Sterba * waitqueue_active why. 26602cbe91SDavid Sterba */ 27602cbe91SDavid Sterba if (wq_has_sleeper(wq)) 28602cbe91SDavid Sterba wake_up(wq); 29602cbe91SDavid Sterba } 30602cbe91SDavid Sterba 31602cbe91SDavid Sterba static inline void cond_wake_up_nomb(struct wait_queue_head *wq) 32602cbe91SDavid Sterba { 33602cbe91SDavid Sterba /* 34602cbe91SDavid Sterba * Special case for conditional wakeup where the barrier required for 35602cbe91SDavid Sterba * waitqueue_active is implied by some of the preceding code. Eg. one 36602cbe91SDavid Sterba * of such atomic operations (atomic_dec_and_return, ...), or a 37602cbe91SDavid Sterba * unlock/lock sequence, etc. 38602cbe91SDavid Sterba */ 39602cbe91SDavid Sterba if (waitqueue_active(wq)) 40602cbe91SDavid Sterba wake_up(wq); 41602cbe91SDavid Sterba } 42602cbe91SDavid Sterba 43784352feSDavid Sterba static inline u64 div_factor(u64 num, int factor) 44784352feSDavid Sterba { 45784352feSDavid Sterba if (factor == 10) 46784352feSDavid Sterba return num; 47784352feSDavid Sterba num *= factor; 48784352feSDavid Sterba return div_u64(num, 10); 49784352feSDavid Sterba } 50784352feSDavid Sterba 51784352feSDavid Sterba static inline u64 div_factor_fine(u64 num, int factor) 52784352feSDavid Sterba { 53784352feSDavid Sterba if (factor == 100) 54784352feSDavid Sterba return num; 55784352feSDavid Sterba num *= factor; 56784352feSDavid Sterba return div_u64(num, 100); 57784352feSDavid Sterba } 58784352feSDavid Sterba 5979c8264eSDavid Sterba /* Copy of is_power_of_two that is 64bit safe */ 6079c8264eSDavid Sterba static inline bool is_power_of_two_u64(u64 n) 6179c8264eSDavid Sterba { 6279c8264eSDavid Sterba return n != 0 && (n & (n - 1)) == 0; 6379c8264eSDavid Sterba } 6479c8264eSDavid Sterba 6579c8264eSDavid Sterba static inline bool has_single_bit_set(u64 n) 6679c8264eSDavid Sterba { 6779c8264eSDavid Sterba return is_power_of_two_u64(n); 6879c8264eSDavid Sterba } 6979c8264eSDavid Sterba 70e9a28dc5SQu Wenruo /* 71e9a28dc5SQu Wenruo * Simple bytenr based rb_tree relate structures 72e9a28dc5SQu Wenruo * 73e9a28dc5SQu Wenruo * Any structure wants to use bytenr as single search index should have their 74e9a28dc5SQu Wenruo * structure start with these members. 75e9a28dc5SQu Wenruo */ 76e9a28dc5SQu Wenruo struct rb_simple_node { 77e9a28dc5SQu Wenruo struct rb_node rb_node; 78e9a28dc5SQu Wenruo u64 bytenr; 79e9a28dc5SQu Wenruo }; 80e9a28dc5SQu Wenruo 81e9a28dc5SQu Wenruo static inline struct rb_node *rb_simple_search(struct rb_root *root, u64 bytenr) 82e9a28dc5SQu Wenruo { 83e9a28dc5SQu Wenruo struct rb_node *node = root->rb_node; 84e9a28dc5SQu Wenruo struct rb_simple_node *entry; 85e9a28dc5SQu Wenruo 86e9a28dc5SQu Wenruo while (node) { 87e9a28dc5SQu Wenruo entry = rb_entry(node, struct rb_simple_node, rb_node); 88e9a28dc5SQu Wenruo 89e9a28dc5SQu Wenruo if (bytenr < entry->bytenr) 90e9a28dc5SQu Wenruo node = node->rb_left; 91e9a28dc5SQu Wenruo else if (bytenr > entry->bytenr) 92e9a28dc5SQu Wenruo node = node->rb_right; 93e9a28dc5SQu Wenruo else 94e9a28dc5SQu Wenruo return node; 95e9a28dc5SQu Wenruo } 96e9a28dc5SQu Wenruo return NULL; 97e9a28dc5SQu Wenruo } 98e9a28dc5SQu Wenruo 9987c11705SJosef Bacik /* 10087c11705SJosef Bacik * Search @root from an entry that starts or comes after @bytenr. 10187c11705SJosef Bacik * 10287c11705SJosef Bacik * @root: the root to search. 10387c11705SJosef Bacik * @bytenr: bytenr to search from. 10487c11705SJosef Bacik * 10587c11705SJosef Bacik * Return the rb_node that start at or after @bytenr. If there is no entry at 10687c11705SJosef Bacik * or after @bytner return NULL. 10787c11705SJosef Bacik */ 10887c11705SJosef Bacik static inline struct rb_node *rb_simple_search_first(struct rb_root *root, 10987c11705SJosef Bacik u64 bytenr) 11087c11705SJosef Bacik { 11187c11705SJosef Bacik struct rb_node *node = root->rb_node, *ret = NULL; 11287c11705SJosef Bacik struct rb_simple_node *entry, *ret_entry = NULL; 11387c11705SJosef Bacik 11487c11705SJosef Bacik while (node) { 11587c11705SJosef Bacik entry = rb_entry(node, struct rb_simple_node, rb_node); 11687c11705SJosef Bacik 11787c11705SJosef Bacik if (bytenr < entry->bytenr) { 11887c11705SJosef Bacik if (!ret || entry->bytenr < ret_entry->bytenr) { 11987c11705SJosef Bacik ret = node; 12087c11705SJosef Bacik ret_entry = entry; 12187c11705SJosef Bacik } 12287c11705SJosef Bacik 12387c11705SJosef Bacik node = node->rb_left; 12487c11705SJosef Bacik } else if (bytenr > entry->bytenr) { 12587c11705SJosef Bacik node = node->rb_right; 12687c11705SJosef Bacik } else { 12787c11705SJosef Bacik return node; 12887c11705SJosef Bacik } 12987c11705SJosef Bacik } 13087c11705SJosef Bacik 13187c11705SJosef Bacik return ret; 13287c11705SJosef Bacik } 13387c11705SJosef Bacik 134e9a28dc5SQu Wenruo static inline struct rb_node *rb_simple_insert(struct rb_root *root, u64 bytenr, 135e9a28dc5SQu Wenruo struct rb_node *node) 136e9a28dc5SQu Wenruo { 137e9a28dc5SQu Wenruo struct rb_node **p = &root->rb_node; 138e9a28dc5SQu Wenruo struct rb_node *parent = NULL; 139e9a28dc5SQu Wenruo struct rb_simple_node *entry; 140e9a28dc5SQu Wenruo 141e9a28dc5SQu Wenruo while (*p) { 142e9a28dc5SQu Wenruo parent = *p; 143e9a28dc5SQu Wenruo entry = rb_entry(parent, struct rb_simple_node, rb_node); 144e9a28dc5SQu Wenruo 145e9a28dc5SQu Wenruo if (bytenr < entry->bytenr) 146e9a28dc5SQu Wenruo p = &(*p)->rb_left; 147e9a28dc5SQu Wenruo else if (bytenr > entry->bytenr) 148e9a28dc5SQu Wenruo p = &(*p)->rb_right; 149e9a28dc5SQu Wenruo else 150e9a28dc5SQu Wenruo return parent; 151e9a28dc5SQu Wenruo } 152e9a28dc5SQu Wenruo 153e9a28dc5SQu Wenruo rb_link_node(node, parent, p); 154e9a28dc5SQu Wenruo rb_insert_color(node, root); 155e9a28dc5SQu Wenruo return NULL; 156e9a28dc5SQu Wenruo } 157e9a28dc5SQu Wenruo 158602cbe91SDavid Sterba #endif 159