bitops.h revision 219820 
1/*-
2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice unmodified, this list of conditions, and the following
12 *    disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28#ifndef	_LINUX_BITOPS_H_
29#define	_LINUX_BITOPS_H_
30
31#ifdef __LP64__
32#define	BITS_PER_LONG		64
33#else
34#define	BITS_PER_LONG		32
35#endif
36#define	BIT_MASK(n)		(~0UL >> (BITS_PER_LONG - (n)))
37#define	BITS_TO_LONGS(n)	howmany((n), BITS_PER_LONG)
38
39static inline int
40__ffs(int mask)
41{
42	return (ffs(mask) - 1);
43}
44
45static inline int
46__fls(int mask)
47{
48	return (fls(mask) - 1);
49}
50
51static inline int
52__ffsl(long mask)
53{
54	return (ffsl(mask) - 1);
55}
56
57static inline int
58__flsl(long mask)
59{
60	return (flsl(mask) - 1);
61}
62
63
64#define	ffz(mask)	__ffs(~(mask))
65
66static inline unsigned long
67find_first_bit(unsigned long *addr, unsigned long size)
68{
69	long mask;
70	int bit;
71
72	for (bit = 0; size >= BITS_PER_LONG;
73	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
74		if (*addr == 0)
75			continue;
76		return (bit + __ffsl(*addr));
77	}
78	if (size) {
79		mask = (*addr) & BIT_MASK(size);
80		if (mask)
81			bit += __ffsl(mask);
82		else
83			bit += size;
84	}
85	return (bit);
86}
87
88static inline unsigned long
89find_first_zero_bit(unsigned long *addr, unsigned long size)
90{
91	long mask;
92	int bit;
93
94	for (bit = 0; size >= BITS_PER_LONG;
95	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
96		if (~(*addr) == 0)
97			continue;
98		return (bit + __ffsl(~(*addr)));
99	}
100	if (size) {
101		mask = ~(*addr) & BIT_MASK(size);
102		if (mask)
103			bit += __ffsl(mask);
104		else
105			bit += size;
106	}
107	return (bit);
108}
109
110static inline unsigned long
111find_last_bit(unsigned long *addr, unsigned long size)
112{
113	long mask;
114	int offs;
115	int bit;
116	int pos;
117
118	pos = size / BITS_PER_LONG;
119	offs = size % BITS_PER_LONG;
120	bit = BITS_PER_LONG * pos;
121	addr += pos;
122	if (offs) {
123		mask = (*addr) & BIT_MASK(offs);
124		if (mask)
125			return (bit + __flsl(mask));
126	}
127	while (--pos) {
128		addr--;
129		bit -= BITS_PER_LONG;
130		if (*addr)
131			return (bit + __flsl(mask));
132	}
133	return (size);
134}
135
136static inline unsigned long
137find_next_bit(unsigned long *addr, unsigned long size, unsigned long offset)
138{
139	long mask;
140	int offs;
141	int bit;
142	int pos;
143
144	if (offset >= size)
145		return (size);
146	pos = offset / BITS_PER_LONG;
147	offs = offset % BITS_PER_LONG;
148	bit = BITS_PER_LONG * pos;
149	addr += pos;
150	if (offs) {
151		mask = (*addr) & ~BIT_MASK(offs);
152		if (mask)
153			return (bit + __ffsl(mask));
154		bit += BITS_PER_LONG;
155		addr++;
156	}
157	for (size -= bit; size >= BITS_PER_LONG;
158	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
159		if (*addr == 0)
160			continue;
161		return (bit + __ffsl(*addr));
162	}
163	if (size) {
164		mask = (*addr) & BIT_MASK(size);
165		if (mask)
166			bit += __ffsl(mask);
167		else
168			bit += size;
169	}
170	return (bit);
171}
172
173static inline unsigned long
174find_next_zero_bit(unsigned long *addr, unsigned long size,
175    unsigned long offset)
176{
177	long mask;
178	int offs;
179	int bit;
180	int pos;
181
182	if (offset >= size)
183		return (size);
184	pos = offset / BITS_PER_LONG;
185	offs = offset % BITS_PER_LONG;
186	bit = BITS_PER_LONG * pos;
187	addr += pos;
188	if (offs) {
189		mask = ~(*addr) & ~BIT_MASK(offs);
190		if (mask)
191			return (bit + __ffsl(mask));
192		bit += BITS_PER_LONG;
193		addr++;
194	}
195	for (size -= bit; size >= BITS_PER_LONG;
196	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
197		if (~(*addr) == 0)
198			continue;
199		return (bit + __ffsl(~(*addr)));
200	}
201	if (size) {
202		mask = ~(*addr) & BIT_MASK(size);
203		if (mask)
204			bit += __ffsl(mask);
205		else
206			bit += size;
207	}
208	return (bit);
209}
210
211static inline void
212bitmap_zero(unsigned long *addr, int size)
213{
214	int len;
215
216	len = BITS_TO_LONGS(size) * sizeof(long);
217	memset(addr, 0, len);
218}
219
220static inline void
221bitmap_fill(unsigned long *addr, int size)
222{
223	int tail;
224	int len;
225
226	len = (size / BITS_PER_LONG) * sizeof(long);
227	memset(addr, 0xff, len);
228	tail = size & (BITS_PER_LONG - 1);
229	if (tail)
230		addr[size / BITS_PER_LONG] = BIT_MASK(tail);
231}
232
233static inline int
234bitmap_full(unsigned long *addr, int size)
235{
236	long mask;
237	int tail;
238	int len;
239	int i;
240
241	len = size / BITS_PER_LONG;
242	for (i = 0; i < len; i++)
243		if (addr[i] != ~0UL)
244			return (0);
245	tail = size & (BITS_PER_LONG - 1);
246	if (tail) {
247		mask = BIT_MASK(tail);
248		if ((addr[i] & mask) != mask)
249			return (0);
250	}
251	return (1);
252}
253
254static inline int
255bitmap_empty(unsigned long *addr, int size)
256{
257	long mask;
258	int tail;
259	int len;
260	int i;
261
262	len = size / BITS_PER_LONG;
263	for (i = 0; i < len; i++)
264		if (addr[i] != 0)
265			return (0);
266	tail = size & (BITS_PER_LONG - 1);
267	if (tail) {
268		mask = BIT_MASK(tail);
269		if ((addr[i] & mask) != 0)
270			return (0);
271	}
272	return (1);
273}
274
275#define	NBINT	(NBBY * sizeof(int))
276
277#define	set_bit(i, a)							\
278    atomic_set_int(&((volatile int *)(a))[(i)/NBINT], 1 << (i) % NBINT)
279
280#define	clear_bit(i, a)							\
281    atomic_clear_int(&((volatile int *)(a))[(i)/NBINT], 1 << (i) % NBINT)
282
283#define	test_bit(i, a)							\
284    !!(atomic_load_acq_int(&((volatile int *)(a))[(i)/NBINT]) & 1 << ((i) % NBINT))
285
286static inline long
287test_and_clear_bit(long bit, long *var)
288{
289	long val;
290
291	bit = 1 << bit;
292	do {
293		val = *(volatile long *)var;
294	} while (atomic_cmpset_long(var, val, val & ~bit) == 0);
295
296	return !!(val & bit);
297}
298
299static inline long
300test_and_set_bit(long bit, long *var)
301{
302	long val;
303
304	bit = 1 << bit;
305	do {
306		val = *(volatile long *)var;
307	} while (atomic_cmpset_long(var, val, val | bit) == 0);
308
309	return !!(val & bit);
310}
311
312#endif	/* _LINUX_BITOPS_H_ */
313