fs/btrfs/misc.h

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