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 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 */
  48 static inline bool is_power_of_two_u64(u64 n)
  49 {
  50         return n != 0 && (n & (n - 1)) == 0;
  51 }
  52
  53 static 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 structures
  60  *
  61  * Any structure wants to use bytenr as single search index should have their
  62  * structure start with these members.
  63  */
  64 struct rb_simple_node {
  65         struct rb_node rb_node;
  66         u64 bytenr;
  67 };
  68
  69 static inline struct rb_node *rb_simple_search(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                 else
  82                         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 at
  94  * or after @bytner return NULL.
  95  */
  96 static inline struct rb_node *rb_simple_search_first(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
 122 static 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                 else
 138                         return parent;
 139         }
 140
 141         rb_link_node(node, parent, p);
 142         rb_insert_color(node, root);
 143         return NULL;
 144 }
 145
 146 #endif