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