1a7aa8068SFrançois Tigeot /*-
2a7aa8068SFrançois Tigeot * Copyright (c) 2010 Isilon Systems, Inc.
3a7aa8068SFrançois Tigeot * Copyright (c) 2010 iX Systems, Inc.
4a7aa8068SFrançois Tigeot * Copyright (c) 2010 Panasas, Inc.
5a9f40f57SFrançois Tigeot * Copyright (c) 2015-2020 François Tigeot <ftigeot@wolfpond.org>
6a7aa8068SFrançois Tigeot * All rights reserved.
7a7aa8068SFrançois Tigeot *
8a7aa8068SFrançois Tigeot * Redistribution and use in source and binary forms, with or without
9a7aa8068SFrançois Tigeot * modification, are permitted provided that the following conditions
10a7aa8068SFrançois Tigeot * are met:
11a7aa8068SFrançois Tigeot * 1. Redistributions of source code must retain the above copyright
12a7aa8068SFrançois Tigeot * notice unmodified, this list of conditions, and the following
13a7aa8068SFrançois Tigeot * disclaimer.
14a7aa8068SFrançois Tigeot * 2. Redistributions in binary form must reproduce the above copyright
15a7aa8068SFrançois Tigeot * notice, this list of conditions and the following disclaimer in the
16a7aa8068SFrançois Tigeot * documentation and/or other materials provided with the distribution.
17a7aa8068SFrançois Tigeot *
18a7aa8068SFrançois Tigeot * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19a7aa8068SFrançois Tigeot * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20a7aa8068SFrançois Tigeot * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21a7aa8068SFrançois Tigeot * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22a7aa8068SFrançois Tigeot * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23a7aa8068SFrançois Tigeot * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24a7aa8068SFrançois Tigeot * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25a7aa8068SFrançois Tigeot * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26a7aa8068SFrançois Tigeot * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27a7aa8068SFrançois Tigeot * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28a7aa8068SFrançois Tigeot */
29a7aa8068SFrançois Tigeot #ifndef _LINUX_BITOPS_H_
30a7aa8068SFrançois Tigeot #define _LINUX_BITOPS_H_
31a7aa8068SFrançois Tigeot
3239cfddd2SFrançois Tigeot #include <asm/types.h>
3339cfddd2SFrançois Tigeot
34e149d068SMichael Neumann #define BIT(nr) (1UL << (nr))
35dde54508SFrançois Tigeot #define BIT_ULL(nb) (1ULL << (nb))
36a7aa8068SFrançois Tigeot #define BIT_MASK(n) (~0UL >> (BITS_PER_LONG - (n)))
37a7aa8068SFrançois Tigeot #define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG)
38a7aa8068SFrançois Tigeot #define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
3939cfddd2SFrançois Tigeot #define BITS_PER_BYTE 8
40a7aa8068SFrançois Tigeot
41a9f40f57SFrançois Tigeot #include <asm/bitops.h>
42a9f40f57SFrançois Tigeot
43dde54508SFrançois Tigeot #include <sys/types.h>
44dde54508SFrançois Tigeot #include <sys/systm.h>
45dde54508SFrançois Tigeot
46a7aa8068SFrançois Tigeot static inline int
__ffs(int mask)47a7aa8068SFrançois Tigeot __ffs(int mask)
48a7aa8068SFrançois Tigeot {
49a7aa8068SFrançois Tigeot return (ffs(mask) - 1);
50a7aa8068SFrançois Tigeot }
51a7aa8068SFrançois Tigeot
52a7aa8068SFrançois Tigeot static inline int
__fls(int mask)53a7aa8068SFrançois Tigeot __fls(int mask)
54a7aa8068SFrançois Tigeot {
55a7aa8068SFrançois Tigeot return (fls(mask) - 1);
56a7aa8068SFrançois Tigeot }
57a7aa8068SFrançois Tigeot
58a7aa8068SFrançois Tigeot static inline int
__ffsl(long mask)59a7aa8068SFrançois Tigeot __ffsl(long mask)
60a7aa8068SFrançois Tigeot {
61a7aa8068SFrançois Tigeot return (ffsl(mask) - 1);
62a7aa8068SFrançois Tigeot }
63a7aa8068SFrançois Tigeot
64a7aa8068SFrançois Tigeot static inline int
__flsl(long mask)65a7aa8068SFrançois Tigeot __flsl(long mask)
66a7aa8068SFrançois Tigeot {
67a7aa8068SFrançois Tigeot return (flsl(mask) - 1);
68a7aa8068SFrançois Tigeot }
69a7aa8068SFrançois Tigeot
70*2cecdd68SFrançois Tigeot /*
71*2cecdd68SFrançois Tigeot * fls64 - find leftmost set bit in a 64-bit word
72*2cecdd68SFrançois Tigeot *
73*2cecdd68SFrançois Tigeot * Returns 0 if no bit is set or the bit
74*2cecdd68SFrançois Tigeot * position counted from 1 to 64 otherwise
75*2cecdd68SFrançois Tigeot */
76*2cecdd68SFrançois Tigeot static inline int
fls64(__u64 x)77*2cecdd68SFrançois Tigeot fls64(__u64 x)
78*2cecdd68SFrançois Tigeot {
79*2cecdd68SFrançois Tigeot return flsl(x);
80*2cecdd68SFrançois Tigeot }
81a7aa8068SFrançois Tigeot
82a7aa8068SFrançois Tigeot #define ffz(mask) __ffs(~(mask))
83a7aa8068SFrançois Tigeot
get_count_order(unsigned int count)84a7aa8068SFrançois Tigeot static inline int get_count_order(unsigned int count)
85a7aa8068SFrançois Tigeot {
86a7aa8068SFrançois Tigeot int order;
87a7aa8068SFrançois Tigeot
88a7aa8068SFrançois Tigeot order = fls(count) - 1;
89a7aa8068SFrançois Tigeot if (count & (count - 1))
90a7aa8068SFrançois Tigeot order++;
91a7aa8068SFrançois Tigeot return order;
92a7aa8068SFrançois Tigeot }
93a7aa8068SFrançois Tigeot
94a7aa8068SFrançois Tigeot static inline unsigned long
find_first_bit(unsigned long * addr,unsigned long size)95a7aa8068SFrançois Tigeot find_first_bit(unsigned long *addr, unsigned long size)
96a7aa8068SFrançois Tigeot {
97a7aa8068SFrançois Tigeot long mask;
98a7aa8068SFrançois Tigeot int bit;
99a7aa8068SFrançois Tigeot
100a7aa8068SFrançois Tigeot for (bit = 0; size >= BITS_PER_LONG;
101a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
102a7aa8068SFrançois Tigeot if (*addr == 0)
103a7aa8068SFrançois Tigeot continue;
104a7aa8068SFrançois Tigeot return (bit + __ffsl(*addr));
105a7aa8068SFrançois Tigeot }
106a7aa8068SFrançois Tigeot if (size) {
107a7aa8068SFrançois Tigeot mask = (*addr) & BIT_MASK(size);
108a7aa8068SFrançois Tigeot if (mask)
109a7aa8068SFrançois Tigeot bit += __ffsl(mask);
110a7aa8068SFrançois Tigeot else
111a7aa8068SFrançois Tigeot bit += size;
112a7aa8068SFrançois Tigeot }
113a7aa8068SFrançois Tigeot return (bit);
114a7aa8068SFrançois Tigeot }
115a7aa8068SFrançois Tigeot
116a7aa8068SFrançois Tigeot static inline unsigned long
find_first_zero_bit(unsigned long * addr,unsigned long size)117a7aa8068SFrançois Tigeot find_first_zero_bit(unsigned long *addr, unsigned long size)
118a7aa8068SFrançois Tigeot {
119a7aa8068SFrançois Tigeot long mask;
120a7aa8068SFrançois Tigeot int bit;
121a7aa8068SFrançois Tigeot
122a7aa8068SFrançois Tigeot for (bit = 0; size >= BITS_PER_LONG;
123a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
124a7aa8068SFrançois Tigeot if (~(*addr) == 0)
125a7aa8068SFrançois Tigeot continue;
126a7aa8068SFrançois Tigeot return (bit + __ffsl(~(*addr)));
127a7aa8068SFrançois Tigeot }
128a7aa8068SFrançois Tigeot if (size) {
129a7aa8068SFrançois Tigeot mask = ~(*addr) & BIT_MASK(size);
130a7aa8068SFrançois Tigeot if (mask)
131a7aa8068SFrançois Tigeot bit += __ffsl(mask);
132a7aa8068SFrançois Tigeot else
133a7aa8068SFrançois Tigeot bit += size;
134a7aa8068SFrançois Tigeot }
135a7aa8068SFrançois Tigeot return (bit);
136a7aa8068SFrançois Tigeot }
137a7aa8068SFrançois Tigeot
138a7aa8068SFrançois Tigeot static inline unsigned long
find_last_bit(unsigned long * addr,unsigned long size)139a7aa8068SFrançois Tigeot find_last_bit(unsigned long *addr, unsigned long size)
140a7aa8068SFrançois Tigeot {
141a7aa8068SFrançois Tigeot long mask;
142a7aa8068SFrançois Tigeot int offs;
143a7aa8068SFrançois Tigeot int bit;
144a7aa8068SFrançois Tigeot int pos;
145a7aa8068SFrançois Tigeot
146a7aa8068SFrançois Tigeot pos = size / BITS_PER_LONG;
147a7aa8068SFrançois Tigeot offs = size % BITS_PER_LONG;
148a7aa8068SFrançois Tigeot bit = BITS_PER_LONG * pos;
149a7aa8068SFrançois Tigeot addr += pos;
150a7aa8068SFrançois Tigeot if (offs) {
151a7aa8068SFrançois Tigeot mask = (*addr) & BIT_MASK(offs);
152a7aa8068SFrançois Tigeot if (mask)
153a7aa8068SFrançois Tigeot return (bit + __flsl(mask));
154a7aa8068SFrançois Tigeot }
155a7aa8068SFrançois Tigeot while (--pos) {
156a7aa8068SFrançois Tigeot addr--;
157a7aa8068SFrançois Tigeot bit -= BITS_PER_LONG;
158a7aa8068SFrançois Tigeot if (*addr)
159a7aa8068SFrançois Tigeot return (bit + __flsl(mask));
160a7aa8068SFrançois Tigeot }
161a7aa8068SFrançois Tigeot return (size);
162a7aa8068SFrançois Tigeot }
163a7aa8068SFrançois Tigeot
164a7aa8068SFrançois Tigeot static inline unsigned long
find_next_bit(unsigned long * addr,unsigned long size,unsigned long offset)165a7aa8068SFrançois Tigeot find_next_bit(unsigned long *addr, unsigned long size, unsigned long offset)
166a7aa8068SFrançois Tigeot {
167a7aa8068SFrançois Tigeot long mask;
168a7aa8068SFrançois Tigeot int offs;
169a7aa8068SFrançois Tigeot int bit;
170a7aa8068SFrançois Tigeot int pos;
171a7aa8068SFrançois Tigeot
172a7aa8068SFrançois Tigeot if (offset >= size)
173a7aa8068SFrançois Tigeot return (size);
174a7aa8068SFrançois Tigeot pos = offset / BITS_PER_LONG;
175a7aa8068SFrançois Tigeot offs = offset % BITS_PER_LONG;
176a7aa8068SFrançois Tigeot bit = BITS_PER_LONG * pos;
177a7aa8068SFrançois Tigeot addr += pos;
178a7aa8068SFrançois Tigeot if (offs) {
179a7aa8068SFrançois Tigeot mask = (*addr) & ~BIT_MASK(offs);
180a7aa8068SFrançois Tigeot if (mask)
181a7aa8068SFrançois Tigeot return (bit + __ffsl(mask));
182a7aa8068SFrançois Tigeot bit += BITS_PER_LONG;
183a7aa8068SFrançois Tigeot addr++;
184a7aa8068SFrançois Tigeot }
185a7aa8068SFrançois Tigeot for (size -= bit; size >= BITS_PER_LONG;
186a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
187a7aa8068SFrançois Tigeot if (*addr == 0)
188a7aa8068SFrançois Tigeot continue;
189a7aa8068SFrançois Tigeot return (bit + __ffsl(*addr));
190a7aa8068SFrançois Tigeot }
191a7aa8068SFrançois Tigeot if (size) {
192a7aa8068SFrançois Tigeot mask = (*addr) & BIT_MASK(size);
193a7aa8068SFrançois Tigeot if (mask)
194a7aa8068SFrançois Tigeot bit += __ffsl(mask);
195a7aa8068SFrançois Tigeot else
196a7aa8068SFrançois Tigeot bit += size;
197a7aa8068SFrançois Tigeot }
198a7aa8068SFrançois Tigeot return (bit);
199a7aa8068SFrançois Tigeot }
200a7aa8068SFrançois Tigeot
201a7aa8068SFrançois Tigeot static inline unsigned long
find_next_zero_bit(unsigned long * addr,unsigned long size,unsigned long offset)202a7aa8068SFrançois Tigeot find_next_zero_bit(unsigned long *addr, unsigned long size,
203a7aa8068SFrançois Tigeot unsigned long offset)
204a7aa8068SFrançois Tigeot {
205a7aa8068SFrançois Tigeot long mask;
206a7aa8068SFrançois Tigeot int offs;
207a7aa8068SFrançois Tigeot int bit;
208a7aa8068SFrançois Tigeot int pos;
209a7aa8068SFrançois Tigeot
210a7aa8068SFrançois Tigeot if (offset >= size)
211a7aa8068SFrançois Tigeot return (size);
212a7aa8068SFrançois Tigeot pos = offset / BITS_PER_LONG;
213a7aa8068SFrançois Tigeot offs = offset % BITS_PER_LONG;
214a7aa8068SFrançois Tigeot bit = BITS_PER_LONG * pos;
215a7aa8068SFrançois Tigeot addr += pos;
216a7aa8068SFrançois Tigeot if (offs) {
217a7aa8068SFrançois Tigeot mask = ~(*addr) & ~BIT_MASK(offs);
218a7aa8068SFrançois Tigeot if (mask)
219a7aa8068SFrançois Tigeot return (bit + __ffsl(mask));
220a7aa8068SFrançois Tigeot bit += BITS_PER_LONG;
221a7aa8068SFrançois Tigeot addr++;
222a7aa8068SFrançois Tigeot }
223a7aa8068SFrançois Tigeot for (size -= bit; size >= BITS_PER_LONG;
224a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
225a7aa8068SFrançois Tigeot if (~(*addr) == 0)
226a7aa8068SFrançois Tigeot continue;
227a7aa8068SFrançois Tigeot return (bit + __ffsl(~(*addr)));
228a7aa8068SFrançois Tigeot }
229a7aa8068SFrançois Tigeot if (size) {
230a7aa8068SFrançois Tigeot mask = ~(*addr) & BIT_MASK(size);
231a7aa8068SFrançois Tigeot if (mask)
232a7aa8068SFrançois Tigeot bit += __ffsl(mask);
233a7aa8068SFrançois Tigeot else
234a7aa8068SFrançois Tigeot bit += size;
235a7aa8068SFrançois Tigeot }
236a7aa8068SFrançois Tigeot return (bit);
237a7aa8068SFrançois Tigeot }
238a7aa8068SFrançois Tigeot
239a7aa8068SFrançois Tigeot static inline void
bitmap_zero(unsigned long * addr,int size)240a7aa8068SFrançois Tigeot bitmap_zero(unsigned long *addr, int size)
241a7aa8068SFrançois Tigeot {
242a7aa8068SFrançois Tigeot int len;
243a7aa8068SFrançois Tigeot
244a7aa8068SFrançois Tigeot len = BITS_TO_LONGS(size) * sizeof(long);
245a7aa8068SFrançois Tigeot memset(addr, 0, len);
246a7aa8068SFrançois Tigeot }
247a7aa8068SFrançois Tigeot
248a7aa8068SFrançois Tigeot static inline void
bitmap_fill(unsigned long * addr,int size)249a7aa8068SFrançois Tigeot bitmap_fill(unsigned long *addr, int size)
250a7aa8068SFrançois Tigeot {
251a7aa8068SFrançois Tigeot int tail;
252a7aa8068SFrançois Tigeot int len;
253a7aa8068SFrançois Tigeot
254a7aa8068SFrançois Tigeot len = (size / BITS_PER_LONG) * sizeof(long);
255a7aa8068SFrançois Tigeot memset(addr, 0xff, len);
256a7aa8068SFrançois Tigeot tail = size & (BITS_PER_LONG - 1);
257a7aa8068SFrançois Tigeot if (tail)
258a7aa8068SFrançois Tigeot addr[size / BITS_PER_LONG] = BIT_MASK(tail);
259a7aa8068SFrançois Tigeot }
260a7aa8068SFrançois Tigeot
261a7aa8068SFrançois Tigeot static inline int
bitmap_full(unsigned long * addr,int size)262a7aa8068SFrançois Tigeot bitmap_full(unsigned long *addr, int size)
263a7aa8068SFrançois Tigeot {
264a7aa8068SFrançois Tigeot long mask;
265a7aa8068SFrançois Tigeot int tail;
266a7aa8068SFrançois Tigeot int len;
267a7aa8068SFrançois Tigeot int i;
268a7aa8068SFrançois Tigeot
269a7aa8068SFrançois Tigeot len = size / BITS_PER_LONG;
270a7aa8068SFrançois Tigeot for (i = 0; i < len; i++)
271a7aa8068SFrançois Tigeot if (addr[i] != ~0UL)
272a7aa8068SFrançois Tigeot return (0);
273a7aa8068SFrançois Tigeot tail = size & (BITS_PER_LONG - 1);
274a7aa8068SFrançois Tigeot if (tail) {
275a7aa8068SFrançois Tigeot mask = BIT_MASK(tail);
276a7aa8068SFrançois Tigeot if ((addr[i] & mask) != mask)
277a7aa8068SFrançois Tigeot return (0);
278a7aa8068SFrançois Tigeot }
279a7aa8068SFrançois Tigeot return (1);
280a7aa8068SFrançois Tigeot }
281a7aa8068SFrançois Tigeot
282a7aa8068SFrançois Tigeot static inline int
bitmap_empty(unsigned long * addr,int size)283a7aa8068SFrançois Tigeot bitmap_empty(unsigned long *addr, int size)
284a7aa8068SFrançois Tigeot {
285a7aa8068SFrançois Tigeot long mask;
286a7aa8068SFrançois Tigeot int tail;
287a7aa8068SFrançois Tigeot int len;
288a7aa8068SFrançois Tigeot int i;
289a7aa8068SFrançois Tigeot
290a7aa8068SFrançois Tigeot len = size / BITS_PER_LONG;
291a7aa8068SFrançois Tigeot for (i = 0; i < len; i++)
292a7aa8068SFrançois Tigeot if (addr[i] != 0)
293a7aa8068SFrançois Tigeot return (0);
294a7aa8068SFrançois Tigeot tail = size & (BITS_PER_LONG - 1);
295a7aa8068SFrançois Tigeot if (tail) {
296a7aa8068SFrançois Tigeot mask = BIT_MASK(tail);
297a7aa8068SFrançois Tigeot if ((addr[i] & mask) != 0)
298a7aa8068SFrançois Tigeot return (0);
299a7aa8068SFrançois Tigeot }
300a7aa8068SFrançois Tigeot return (1);
301a7aa8068SFrançois Tigeot }
302a7aa8068SFrançois Tigeot
303a7aa8068SFrançois Tigeot #define NBLONG (NBBY * sizeof(long))
304a7aa8068SFrançois Tigeot
305a7aa8068SFrançois Tigeot #define set_bit(i, a) \
306a3268cb6SMatthew Dillon atomic_set_long(&((volatile long *)(a))[(i)/NBLONG], 1LU << ((i) % NBLONG))
307a7aa8068SFrançois Tigeot
308a7aa8068SFrançois Tigeot #define clear_bit(i, a) \
309a3268cb6SMatthew Dillon atomic_clear_long(&((volatile long *)(a))[(i)/NBLONG], 1LU << ((i) % NBLONG))
310a7aa8068SFrançois Tigeot
311a7aa8068SFrançois Tigeot #define test_bit(i, a) \
312a7aa8068SFrançois Tigeot !!(atomic_load_acq_long(&((volatile long *)(a))[(i)/NBLONG]) & \
313a3268cb6SMatthew Dillon (1LU << ((i) % NBLONG)))
314a7aa8068SFrançois Tigeot
315a7aa8068SFrançois Tigeot static inline long
test_and_clear_bit(long bit,long * var)316a7aa8068SFrançois Tigeot test_and_clear_bit(long bit, long *var)
317a7aa8068SFrançois Tigeot {
318a7aa8068SFrançois Tigeot long val;
319a7aa8068SFrançois Tigeot
320a7aa8068SFrançois Tigeot var += bit / (sizeof(long) * NBBY);
321a7aa8068SFrançois Tigeot bit %= sizeof(long) * NBBY;
322a3268cb6SMatthew Dillon bit = 1L << bit;
323a7aa8068SFrançois Tigeot do {
324a7aa8068SFrançois Tigeot val = *(volatile long *)var;
325a7aa8068SFrançois Tigeot } while (atomic_cmpset_long(var, val, val & ~bit) == 0);
326a7aa8068SFrançois Tigeot
327a7aa8068SFrançois Tigeot return !!(val & bit);
328a7aa8068SFrançois Tigeot }
329a7aa8068SFrançois Tigeot
330fb0ecf7cSFrançois Tigeot static inline unsigned long
__test_and_clear_bit(unsigned int bit,volatile unsigned long * ptr)331fb0ecf7cSFrançois Tigeot __test_and_clear_bit(unsigned int bit, volatile unsigned long *ptr)
332fb0ecf7cSFrançois Tigeot {
333fb0ecf7cSFrançois Tigeot const unsigned int units = (sizeof(*ptr) * NBBY);
334fb0ecf7cSFrançois Tigeot volatile unsigned long *const p = &ptr[bit / units];
335fb0ecf7cSFrançois Tigeot const unsigned long mask = (1UL << (bit % units));
336fb0ecf7cSFrançois Tigeot unsigned long v;
337fb0ecf7cSFrançois Tigeot
338fb0ecf7cSFrançois Tigeot v = *p;
339fb0ecf7cSFrançois Tigeot *p &= ~mask;
340fb0ecf7cSFrançois Tigeot
341fb0ecf7cSFrançois Tigeot return ((v & mask) != 0);
342fb0ecf7cSFrançois Tigeot }
343fb0ecf7cSFrançois Tigeot
344a7aa8068SFrançois Tigeot static inline long
test_and_set_bit(long bit,volatile unsigned long * var)34581efc3b7SFrançois Tigeot test_and_set_bit(long bit, volatile unsigned long *var)
346a7aa8068SFrançois Tigeot {
347a7aa8068SFrançois Tigeot long val;
348a7aa8068SFrançois Tigeot
349a7aa8068SFrançois Tigeot var += bit / (sizeof(long) * NBBY);
350a7aa8068SFrançois Tigeot bit %= sizeof(long) * NBBY;
351a3268cb6SMatthew Dillon bit = 1L << bit;
352a7aa8068SFrançois Tigeot do {
353a7aa8068SFrançois Tigeot val = *(volatile long *)var;
354a7aa8068SFrançois Tigeot } while (atomic_cmpset_long(var, val, val | bit) == 0);
355a7aa8068SFrançois Tigeot
356a7aa8068SFrançois Tigeot return !!(val & bit);
357a7aa8068SFrançois Tigeot }
358a7aa8068SFrançois Tigeot
359a7aa8068SFrançois Tigeot
360a7aa8068SFrançois Tigeot #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
361a7aa8068SFrançois Tigeot #define BITMAP_LAST_WORD_MASK(nbits) \
362a7aa8068SFrançois Tigeot ( \
363a7aa8068SFrançois Tigeot ((nbits) % BITS_PER_LONG) ? \
364a7aa8068SFrançois Tigeot (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
365a7aa8068SFrançois Tigeot )
366a7aa8068SFrançois Tigeot
367a7aa8068SFrançois Tigeot
368a7aa8068SFrançois Tigeot static inline void
bitmap_set(unsigned long * map,int start,int nr)369a7aa8068SFrançois Tigeot bitmap_set(unsigned long *map, int start, int nr)
370a7aa8068SFrançois Tigeot {
371a7aa8068SFrançois Tigeot unsigned long *p = map + BIT_WORD(start);
372a7aa8068SFrançois Tigeot const int size = start + nr;
373a7aa8068SFrançois Tigeot int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
374a7aa8068SFrançois Tigeot unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
375a7aa8068SFrançois Tigeot
376a7aa8068SFrançois Tigeot while (nr - bits_to_set >= 0) {
377a7aa8068SFrançois Tigeot *p |= mask_to_set;
378a7aa8068SFrançois Tigeot nr -= bits_to_set;
379a7aa8068SFrançois Tigeot bits_to_set = BITS_PER_LONG;
380a7aa8068SFrançois Tigeot mask_to_set = ~0UL;
381a7aa8068SFrançois Tigeot p++;
382a7aa8068SFrançois Tigeot }
383a7aa8068SFrançois Tigeot if (nr) {
384a7aa8068SFrançois Tigeot mask_to_set &= BITMAP_LAST_WORD_MASK(size);
385a7aa8068SFrançois Tigeot *p |= mask_to_set;
386a7aa8068SFrançois Tigeot }
387a7aa8068SFrançois Tigeot }
388a7aa8068SFrançois Tigeot
389a7aa8068SFrançois Tigeot static inline void
bitmap_clear(unsigned long * map,int start,int nr)390a7aa8068SFrançois Tigeot bitmap_clear(unsigned long *map, int start, int nr)
391a7aa8068SFrançois Tigeot {
392a7aa8068SFrançois Tigeot unsigned long *p = map + BIT_WORD(start);
393a7aa8068SFrançois Tigeot const int size = start + nr;
394a7aa8068SFrançois Tigeot int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
395a7aa8068SFrançois Tigeot unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
396a7aa8068SFrançois Tigeot
397a7aa8068SFrançois Tigeot while (nr - bits_to_clear >= 0) {
398a7aa8068SFrançois Tigeot *p &= ~mask_to_clear;
399a7aa8068SFrançois Tigeot nr -= bits_to_clear;
400a7aa8068SFrançois Tigeot bits_to_clear = BITS_PER_LONG;
401a7aa8068SFrançois Tigeot mask_to_clear = ~0UL;
402a7aa8068SFrançois Tigeot p++;
403a7aa8068SFrançois Tigeot }
404a7aa8068SFrançois Tigeot if (nr) {
405a7aa8068SFrançois Tigeot mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
406a7aa8068SFrançois Tigeot *p &= ~mask_to_clear;
407a7aa8068SFrançois Tigeot }
408a7aa8068SFrançois Tigeot }
409a7aa8068SFrançois Tigeot
410a7aa8068SFrançois Tigeot enum {
411a7aa8068SFrançois Tigeot REG_OP_ISFREE, /* true if region is all zero bits */
412a7aa8068SFrançois Tigeot REG_OP_ALLOC, /* set all bits in region */
413a7aa8068SFrançois Tigeot REG_OP_RELEASE, /* clear all bits in region */
414a7aa8068SFrançois Tigeot };
415a7aa8068SFrançois Tigeot
__reg_op(unsigned long * bitmap,int pos,int order,int reg_op)416a7aa8068SFrançois Tigeot static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
417a7aa8068SFrançois Tigeot {
418a7aa8068SFrançois Tigeot int nbits_reg; /* number of bits in region */
419a7aa8068SFrançois Tigeot int index; /* index first long of region in bitmap */
420a7aa8068SFrançois Tigeot int offset; /* bit offset region in bitmap[index] */
421a7aa8068SFrançois Tigeot int nlongs_reg; /* num longs spanned by region in bitmap */
422a7aa8068SFrançois Tigeot int nbitsinlong; /* num bits of region in each spanned long */
423a7aa8068SFrançois Tigeot unsigned long mask; /* bitmask for one long of region */
424a7aa8068SFrançois Tigeot int i; /* scans bitmap by longs */
425a7aa8068SFrançois Tigeot int ret = 0; /* return value */
426a7aa8068SFrançois Tigeot
427a7aa8068SFrançois Tigeot /*
428a7aa8068SFrançois Tigeot * Either nlongs_reg == 1 (for small orders that fit in one long)
429a7aa8068SFrançois Tigeot * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
430a7aa8068SFrançois Tigeot */
431a7aa8068SFrançois Tigeot nbits_reg = 1 << order;
432a7aa8068SFrançois Tigeot index = pos / BITS_PER_LONG;
433a7aa8068SFrançois Tigeot offset = pos - (index * BITS_PER_LONG);
434a7aa8068SFrançois Tigeot nlongs_reg = BITS_TO_LONGS(nbits_reg);
435a7aa8068SFrançois Tigeot nbitsinlong = min(nbits_reg, BITS_PER_LONG);
436a7aa8068SFrançois Tigeot
437a7aa8068SFrançois Tigeot /*
438a7aa8068SFrançois Tigeot * Can't do "mask = (1UL << nbitsinlong) - 1", as that
439a7aa8068SFrançois Tigeot * overflows if nbitsinlong == BITS_PER_LONG.
440a7aa8068SFrançois Tigeot */
441a7aa8068SFrançois Tigeot mask = (1UL << (nbitsinlong - 1));
442a7aa8068SFrançois Tigeot mask += mask - 1;
443a7aa8068SFrançois Tigeot mask <<= offset;
444a7aa8068SFrançois Tigeot
445a7aa8068SFrançois Tigeot switch (reg_op) {
446a7aa8068SFrançois Tigeot case REG_OP_ISFREE:
447a7aa8068SFrançois Tigeot for (i = 0; i < nlongs_reg; i++) {
448a7aa8068SFrançois Tigeot if (bitmap[index + i] & mask)
449a7aa8068SFrançois Tigeot goto done;
450a7aa8068SFrançois Tigeot }
451a7aa8068SFrançois Tigeot ret = 1; /* all bits in region free (zero) */
452a7aa8068SFrançois Tigeot break;
453a7aa8068SFrançois Tigeot
454a7aa8068SFrançois Tigeot case REG_OP_ALLOC:
455a7aa8068SFrançois Tigeot for (i = 0; i < nlongs_reg; i++)
456a7aa8068SFrançois Tigeot bitmap[index + i] |= mask;
457a7aa8068SFrançois Tigeot break;
458a7aa8068SFrançois Tigeot
459a7aa8068SFrançois Tigeot case REG_OP_RELEASE:
460a7aa8068SFrançois Tigeot for (i = 0; i < nlongs_reg; i++)
461a7aa8068SFrançois Tigeot bitmap[index + i] &= ~mask;
462a7aa8068SFrançois Tigeot break;
463a7aa8068SFrançois Tigeot }
464a7aa8068SFrançois Tigeot done:
465a7aa8068SFrançois Tigeot return ret;
466a7aa8068SFrançois Tigeot }
467a7aa8068SFrançois Tigeot
468a7aa8068SFrançois Tigeot /**
469a7aa8068SFrançois Tigeot * bitmap_find_free_region - find a contiguous aligned mem region
470a7aa8068SFrançois Tigeot * @bitmap: array of unsigned longs corresponding to the bitmap
471a7aa8068SFrançois Tigeot * @bits: number of bits in the bitmap
472a7aa8068SFrançois Tigeot * @order: region size (log base 2 of number of bits) to find
473a7aa8068SFrançois Tigeot *
474a7aa8068SFrançois Tigeot * Find a region of free (zero) bits in a @bitmap of @bits bits and
475a7aa8068SFrançois Tigeot * allocate them (set them to one). Only consider regions of length
476a7aa8068SFrançois Tigeot * a power (@order) of two, aligned to that power of two, which
477a7aa8068SFrançois Tigeot * makes the search algorithm much faster.
478a7aa8068SFrançois Tigeot *
479a7aa8068SFrançois Tigeot * Return the bit offset in bitmap of the allocated region,
480a7aa8068SFrançois Tigeot * or -errno on failure.
481a7aa8068SFrançois Tigeot */
482a7aa8068SFrançois Tigeot static inline int
bitmap_find_free_region(unsigned long * bitmap,int bits,int order)483a7aa8068SFrançois Tigeot bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
484a7aa8068SFrançois Tigeot {
485a7aa8068SFrançois Tigeot int pos, end; /* scans bitmap by regions of size order */
486a7aa8068SFrançois Tigeot
487a7aa8068SFrançois Tigeot for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
488a7aa8068SFrançois Tigeot if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
489a7aa8068SFrançois Tigeot continue;
490a7aa8068SFrançois Tigeot __reg_op(bitmap, pos, order, REG_OP_ALLOC);
491a7aa8068SFrançois Tigeot return pos;
492a7aa8068SFrançois Tigeot }
493a7aa8068SFrançois Tigeot return -ENOMEM;
494a7aa8068SFrançois Tigeot }
495a7aa8068SFrançois Tigeot
496a7aa8068SFrançois Tigeot /**
497a7aa8068SFrançois Tigeot * bitmap_release_region - release allocated bitmap region
498a7aa8068SFrançois Tigeot * @bitmap: array of unsigned longs corresponding to the bitmap
499a7aa8068SFrançois Tigeot * @pos: beginning of bit region to release
500a7aa8068SFrançois Tigeot * @order: region size (log base 2 of number of bits) to release
501a7aa8068SFrançois Tigeot *
502a7aa8068SFrançois Tigeot * This is the complement to __bitmap_find_free_region() and releases
503a7aa8068SFrançois Tigeot * the found region (by clearing it in the bitmap).
504a7aa8068SFrançois Tigeot *
505a7aa8068SFrançois Tigeot * No return value.
506a7aa8068SFrançois Tigeot */
507a7aa8068SFrançois Tigeot static inline void
bitmap_release_region(unsigned long * bitmap,int pos,int order)508a7aa8068SFrançois Tigeot bitmap_release_region(unsigned long *bitmap, int pos, int order)
509a7aa8068SFrançois Tigeot {
510a7aa8068SFrançois Tigeot __reg_op(bitmap, pos, order, REG_OP_RELEASE);
511a7aa8068SFrançois Tigeot }
512a7aa8068SFrançois Tigeot
513f57dc5d0SFrançois Tigeot /* Returns a contiguous bitmask from bits h to l */
514f57dc5d0SFrançois Tigeot #define GENMASK(h, l) \
51539cfddd2SFrançois Tigeot (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l)))
516f57dc5d0SFrançois Tigeot
517dde54508SFrançois Tigeot #define GENMASK_ULL(h, l) \
518dde54508SFrançois Tigeot (((~0ULL) >> (BITS_PER_LONG_LONG - 1 - (h))) & ((~0ULL) << (l)))
519dde54508SFrançois Tigeot
520e3440f96SFrançois Tigeot #include <asm/bitops/non-atomic.h>
5213ee3144dSFrançois Tigeot #include <asm/bitops/const_hweight.h>
522a7aa8068SFrançois Tigeot
523b44a8500SFrançois Tigeot #define for_each_set_bit(bit, addr, size) \
524b44a8500SFrançois Tigeot for ((bit) = find_first_bit((addr), (size)); \
525b44a8500SFrançois Tigeot (bit) < (size); \
526b44a8500SFrançois Tigeot (bit) = find_next_bit((addr), (size), (bit) + 1))
527b44a8500SFrançois Tigeot
528541d9ce9SFrançois Tigeot #define for_each_clear_bit(bit, addr, size) \
529541d9ce9SFrançois Tigeot for ((bit) = find_first_zero_bit((addr), (size)); \
530541d9ce9SFrançois Tigeot (bit) < (size); \
531541d9ce9SFrançois Tigeot (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
532fccb38abSFrançois Tigeot
533fccb38abSFrançois Tigeot static inline int64_t
sign_extend64(uint64_t value,int index)534fccb38abSFrançois Tigeot sign_extend64(uint64_t value, int index)
535fccb38abSFrançois Tigeot {
536fccb38abSFrançois Tigeot uint8_t shift = 63 - index;
537fccb38abSFrançois Tigeot return (int64_t)(value << shift) >> shift;
538fccb38abSFrançois Tigeot }
539fccb38abSFrançois Tigeot
540a7aa8068SFrançois Tigeot #endif /* _LINUX_BITOPS_H_ */
541