Line data    Source code

       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    57871291 : 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    57871291 :         if (wq_has_sleeper(wq))
      28       70355 :                 wake_up(wq);
      29    57878940 : }
      30             : 
      31    28293019 : 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    28293019 :         if (waitqueue_active(wq))
      40        4434 :                 wake_up(wq);
      41    28293019 : }
      42             : 
      43             : static inline u64 mult_perc(u64 num, u32 percent)
      44             : {
      45    62075462 :         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   256213011 :         return n != 0 && (n & (n - 1)) == 0;
      51             : }
      52             : 
      53             : static inline bool has_single_bit_set(u64 n)
      54             : {
      55   252239825 :         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     2926216 :         struct rb_node *node = root->rb_node;
      72     2926216 :         struct rb_simple_node *entry;
      73             : 
      74    18746812 :         while (node) {
      75    18622245 :                 entry = rb_entry(node, struct rb_simple_node, rb_node);
      76             : 
      77    18622245 :                 if (bytenr < entry->bytenr)
      78     7886298 :                         node = node->rb_left;
      79    10735947 :                 else if (bytenr > entry->bytenr)
      80     7934298 :                         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     4001570 : static inline struct rb_node *rb_simple_insert(struct rb_root *root, u64 bytenr,
     123             :                                                struct rb_node *node)
     124             : {
     125     4001570 :         struct rb_node **p = &root->rb_node;
     126     4001570 :         struct rb_node *parent = NULL;
     127     4001570 :         struct rb_simple_node *entry;
     128             : 
     129    17556799 :         while (*p) {
     130    13555229 :                 parent = *p;
     131    13555229 :                 entry = rb_entry(parent, struct rb_simple_node, rb_node);
     132             : 
     133    13555229 :                 if (bytenr < entry->bytenr)
     134     8001253 :                         p = &(*p)->rb_left;
     135     5553976 :                 else if (bytenr > entry->bytenr)
     136     5553976 :                         p = &(*p)->rb_right;
     137             :                 else
     138           0 :                         return parent;
     139             :         }
     140             : 
     141     4001570 :         rb_link_node(node, parent, p);
     142     4001570 :         rb_insert_color(node, root);
     143     4001570 :         return NULL;
     144             : }
     145             : 
     146             : static inline bool bitmap_test_range_all_set(const unsigned long *addr,
     147             :                                              unsigned long start,
     148             :                                              unsigned long nbits)
     149             : {
     150           0 :         unsigned long found_zero;
     151             : 
     152           0 :         found_zero = find_next_zero_bit(addr, start + nbits, start);
     153           0 :         return (found_zero == start + nbits);
     154             : }
     155             : 
     156             : static inline bool bitmap_test_range_all_zero(const unsigned long *addr,
     157             :                                               unsigned long start,
     158             :                                               unsigned long nbits)
     159             : {
     160           0 :         unsigned long found_set;
     161             : 
     162           0 :         found_set = find_next_bit(addr, start + nbits, start);
     163           0 :         return (found_set == start + nbits);
     164             : }
     165             : 
     166             : #endif