Loading...
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
19static 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
29static 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
41static 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 */
46static inline bool is_power_of_two_u64(u64 n)
47{
48 return n != 0 && (n & (n - 1)) == 0;
49}
50
51static 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 */
62struct rb_simple_node {
63 struct rb_node rb_node;
64 u64 bytenr;
65};
66
67static 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 */
94static 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
120static 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
144static 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
154static 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
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 <asm/div64.h>
9#include <linux/rbtree.h>
10
11#define in_range(b, first, len) ((b) >= (first) && (b) < (first) + (len))
12
13static inline void cond_wake_up(struct wait_queue_head *wq)
14{
15 /*
16 * This implies a full smp_mb barrier, see comments for
17 * waitqueue_active why.
18 */
19 if (wq_has_sleeper(wq))
20 wake_up(wq);
21}
22
23static inline void cond_wake_up_nomb(struct wait_queue_head *wq)
24{
25 /*
26 * Special case for conditional wakeup where the barrier required for
27 * waitqueue_active is implied by some of the preceding code. Eg. one
28 * of such atomic operations (atomic_dec_and_return, ...), or a
29 * unlock/lock sequence, etc.
30 */
31 if (waitqueue_active(wq))
32 wake_up(wq);
33}
34
35static inline u64 div_factor(u64 num, int factor)
36{
37 if (factor == 10)
38 return num;
39 num *= factor;
40 return div_u64(num, 10);
41}
42
43static inline u64 div_factor_fine(u64 num, int factor)
44{
45 if (factor == 100)
46 return num;
47 num *= factor;
48 return div_u64(num, 100);
49}
50
51/* Copy of is_power_of_two that is 64bit safe */
52static inline bool is_power_of_two_u64(u64 n)
53{
54 return n != 0 && (n & (n - 1)) == 0;
55}
56
57static inline bool has_single_bit_set(u64 n)
58{
59 return is_power_of_two_u64(n);
60}
61
62/*
63 * Simple bytenr based rb_tree relate structures
64 *
65 * Any structure wants to use bytenr as single search index should have their
66 * structure start with these members.
67 */
68struct rb_simple_node {
69 struct rb_node rb_node;
70 u64 bytenr;
71};
72
73static inline struct rb_node *rb_simple_search(struct rb_root *root, u64 bytenr)
74{
75 struct rb_node *node = root->rb_node;
76 struct rb_simple_node *entry;
77
78 while (node) {
79 entry = rb_entry(node, struct rb_simple_node, rb_node);
80
81 if (bytenr < entry->bytenr)
82 node = node->rb_left;
83 else if (bytenr > entry->bytenr)
84 node = node->rb_right;
85 else
86 return node;
87 }
88 return NULL;
89}
90
91static inline struct rb_node *rb_simple_insert(struct rb_root *root, u64 bytenr,
92 struct rb_node *node)
93{
94 struct rb_node **p = &root->rb_node;
95 struct rb_node *parent = NULL;
96 struct rb_simple_node *entry;
97
98 while (*p) {
99 parent = *p;
100 entry = rb_entry(parent, struct rb_simple_node, rb_node);
101
102 if (bytenr < entry->bytenr)
103 p = &(*p)->rb_left;
104 else if (bytenr > entry->bytenr)
105 p = &(*p)->rb_right;
106 else
107 return parent;
108 }
109
110 rb_link_node(node, parent, p);
111 rb_insert_color(node, root);
112 return NULL;
113}
114
115#endif