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