bitops.h revision 289624 
1/* $FreeBSD: head/sys/ofed/include/linux/bitops.h 289624 2015-10-20 11:40:04Z hselasky $ */
2/*-
3 * Copyright (c) 2010 Isilon Systems, Inc.
4 * Copyright (c) 2010 iX Systems, Inc.
5 * Copyright (c) 2010 Panasas, Inc.
6 * Copyright (c) 2013-2015 Mellanox Technologies, Ltd.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice unmodified, this list of conditions, and the following
14 *    disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30#ifndef	_LINUX_BITOPS_H_
31#define	_LINUX_BITOPS_H_
32
33#include <sys/types.h>
34#include <sys/systm.h>
35
36#define	BIT(nr)			(1UL << (nr))
37#ifdef __LP64__
38#define	BITS_PER_LONG		64
39#else
40#define	BITS_PER_LONG		32
41#endif
42#define	BITMAP_FIRST_WORD_MASK(start)	(~0UL << ((start) % BITS_PER_LONG))
43#define	BITMAP_LAST_WORD_MASK(n)	(~0UL >> (BITS_PER_LONG - (n)))
44#define	BITS_TO_LONGS(n)	howmany((n), BITS_PER_LONG)
45#define	BIT_MASK(nr)		(1UL << ((nr) & (BITS_PER_LONG - 1)))
46#define BIT_WORD(nr)		((nr) / BITS_PER_LONG)
47#define	GENMASK(lo, hi)		(((2UL << ((hi) - (lo))) - 1UL) << (lo))
48#define BITS_PER_BYTE           8
49
50static inline int
51__ffs(int mask)
52{
53	return (ffs(mask) - 1);
54}
55
56static inline int
57__fls(int mask)
58{
59	return (fls(mask) - 1);
60}
61
62static inline int
63__ffsl(long mask)
64{
65	return (ffsl(mask) - 1);
66}
67
68static inline int
69__flsl(long mask)
70{
71	return (flsl(mask) - 1);
72}
73
74
75#define	ffz(mask)	__ffs(~(mask))
76
77static inline int get_count_order(unsigned int count)
78{
79        int order;
80
81        order = fls(count) - 1;
82        if (count & (count - 1))
83                order++;
84        return order;
85}
86
87static inline unsigned long
88find_first_bit(unsigned long *addr, unsigned long size)
89{
90	long mask;
91	int bit;
92
93	for (bit = 0; size >= BITS_PER_LONG;
94	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
95		if (*addr == 0)
96			continue;
97		return (bit + __ffsl(*addr));
98	}
99	if (size) {
100		mask = (*addr) & BITMAP_LAST_WORD_MASK(size);
101		if (mask)
102			bit += __ffsl(mask);
103		else
104			bit += size;
105	}
106	return (bit);
107}
108
109static inline unsigned long
110find_first_zero_bit(unsigned long *addr, unsigned long size)
111{
112	long mask;
113	int bit;
114
115	for (bit = 0; size >= BITS_PER_LONG;
116	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
117		if (~(*addr) == 0)
118			continue;
119		return (bit + __ffsl(~(*addr)));
120	}
121	if (size) {
122		mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size);
123		if (mask)
124			bit += __ffsl(mask);
125		else
126			bit += size;
127	}
128	return (bit);
129}
130
131static inline unsigned long
132find_last_bit(unsigned long *addr, unsigned long size)
133{
134	long mask;
135	int offs;
136	int bit;
137	int pos;
138
139	pos = size / BITS_PER_LONG;
140	offs = size % BITS_PER_LONG;
141	bit = BITS_PER_LONG * pos;
142	addr += pos;
143	if (offs) {
144		mask = (*addr) & BITMAP_LAST_WORD_MASK(offs);
145		if (mask)
146			return (bit + __flsl(mask));
147	}
148	while (--pos) {
149		addr--;
150		bit -= BITS_PER_LONG;
151		if (*addr)
152			return (bit + __flsl(mask));
153	}
154	return (size);
155}
156
157static inline unsigned long
158find_next_bit(unsigned long *addr, unsigned long size, unsigned long offset)
159{
160	long mask;
161	int offs;
162	int bit;
163	int pos;
164
165	if (offset >= size)
166		return (size);
167	pos = offset / BITS_PER_LONG;
168	offs = offset % BITS_PER_LONG;
169	bit = BITS_PER_LONG * pos;
170	addr += pos;
171	if (offs) {
172		mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs);
173		if (mask)
174			return (bit + __ffsl(mask));
175		if (size - bit <= BITS_PER_LONG)
176			return (size);
177		bit += BITS_PER_LONG;
178		addr++;
179	}
180	for (size -= bit; size >= BITS_PER_LONG;
181	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
182		if (*addr == 0)
183			continue;
184		return (bit + __ffsl(*addr));
185	}
186	if (size) {
187		mask = (*addr) & BITMAP_LAST_WORD_MASK(size);
188		if (mask)
189			bit += __ffsl(mask);
190		else
191			bit += size;
192	}
193	return (bit);
194}
195
196static inline unsigned long
197find_next_zero_bit(unsigned long *addr, unsigned long size,
198    unsigned long offset)
199{
200	long mask;
201	int offs;
202	int bit;
203	int pos;
204
205	if (offset >= size)
206		return (size);
207	pos = offset / BITS_PER_LONG;
208	offs = offset % BITS_PER_LONG;
209	bit = BITS_PER_LONG * pos;
210	addr += pos;
211	if (offs) {
212		mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs);
213		if (mask)
214			return (bit + __ffsl(mask));
215		if (size - bit <= BITS_PER_LONG)
216			return (size);
217		bit += BITS_PER_LONG;
218		addr++;
219	}
220	for (size -= bit; size >= BITS_PER_LONG;
221	    size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
222		if (~(*addr) == 0)
223			continue;
224		return (bit + __ffsl(~(*addr)));
225	}
226	if (size) {
227		mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size);
228		if (mask)
229			bit += __ffsl(mask);
230		else
231			bit += size;
232	}
233	return (bit);
234}
235
236static inline void
237bitmap_zero(unsigned long *addr, int size)
238{
239	int len;
240
241	len = BITS_TO_LONGS(size) * sizeof(long);
242	memset(addr, 0, len);
243}
244
245static inline void
246bitmap_fill(unsigned long *addr, int size)
247{
248	int tail;
249	int len;
250
251	len = (size / BITS_PER_LONG) * sizeof(long);
252	memset(addr, 0xff, len);
253	tail = size & (BITS_PER_LONG - 1);
254	if (tail)
255		addr[size / BITS_PER_LONG] = BITMAP_LAST_WORD_MASK(tail);
256}
257
258static inline int
259bitmap_full(unsigned long *addr, int size)
260{
261	unsigned long mask;
262	int tail;
263	int len;
264	int i;
265
266	len = size / BITS_PER_LONG;
267	for (i = 0; i < len; i++)
268		if (addr[i] != ~0UL)
269			return (0);
270	tail = size & (BITS_PER_LONG - 1);
271	if (tail) {
272		mask = BITMAP_LAST_WORD_MASK(tail);
273		if ((addr[i] & mask) != mask)
274			return (0);
275	}
276	return (1);
277}
278
279static inline int
280bitmap_empty(unsigned long *addr, int size)
281{
282	unsigned long mask;
283	int tail;
284	int len;
285	int i;
286
287	len = size / BITS_PER_LONG;
288	for (i = 0; i < len; i++)
289		if (addr[i] != 0)
290			return (0);
291	tail = size & (BITS_PER_LONG - 1);
292	if (tail) {
293		mask = BITMAP_LAST_WORD_MASK(tail);
294		if ((addr[i] & mask) != 0)
295			return (0);
296	}
297	return (1);
298}
299
300#define	__set_bit(i, a)							\
301    atomic_set_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i))
302
303#define	set_bit(i, a)							\
304    atomic_set_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i))
305
306#define	__clear_bit(i, a)						\
307    atomic_clear_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i))
308
309#define	clear_bit(i, a)							\
310    atomic_clear_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i))
311
312#define	test_bit(i, a)							\
313    !!(atomic_load_acq_long(&((volatile long *)(a))[BIT_WORD(i)]) &	\
314    BIT_MASK(i))
315
316static inline long
317test_and_clear_bit(long bit, long *var)
318{
319	long val;
320
321	var += BIT_WORD(bit);
322	bit %= BITS_PER_LONG;
323	bit = (1UL << bit);
324	do {
325		val = *(volatile long *)var;
326	} while (atomic_cmpset_long(var, val, val & ~bit) == 0);
327
328	return !!(val & bit);
329}
330
331static inline long
332test_and_set_bit(long bit, long *var)
333{
334	long val;
335
336	var += BIT_WORD(bit);
337	bit %= BITS_PER_LONG;
338	bit = (1UL << bit);
339	do {
340		val = *(volatile long *)var;
341	} while (atomic_cmpset_long(var, val, val | bit) == 0);
342
343	return !!(val & bit);
344}
345
346static inline void
347bitmap_set(unsigned long *map, int start, int nr)
348{
349	unsigned long *p = map + BIT_WORD(start);
350	const int size = start + nr;
351	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
352	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
353
354	while (nr - bits_to_set >= 0) {
355		*p |= mask_to_set;
356		nr -= bits_to_set;
357		bits_to_set = BITS_PER_LONG;
358		mask_to_set = ~0UL;
359		p++;
360	}
361	if (nr) {
362		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
363		*p |= mask_to_set;
364	}
365}
366
367static inline void
368bitmap_clear(unsigned long *map, int start, int nr)
369{
370	unsigned long *p = map + BIT_WORD(start);
371	const int size = start + nr;
372	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
373	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
374
375	while (nr - bits_to_clear >= 0) {
376		*p &= ~mask_to_clear;
377		nr -= bits_to_clear;
378		bits_to_clear = BITS_PER_LONG;
379		mask_to_clear = ~0UL;
380		p++;
381	}
382	if (nr) {
383		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
384		*p &= ~mask_to_clear;
385	}
386}
387
388enum {
389        REG_OP_ISFREE,
390        REG_OP_ALLOC,
391        REG_OP_RELEASE,
392};
393
394static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
395{
396        int nbits_reg;
397        int index;
398        int offset;
399        int nlongs_reg;
400        int nbitsinlong;
401        unsigned long mask;
402        int i;
403        int ret = 0;
404
405        nbits_reg = 1 << order;
406        index = pos / BITS_PER_LONG;
407        offset = pos - (index * BITS_PER_LONG);
408        nlongs_reg = BITS_TO_LONGS(nbits_reg);
409        nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
410
411        mask = (1UL << (nbitsinlong - 1));
412        mask += mask - 1;
413        mask <<= offset;
414
415        switch (reg_op) {
416        case REG_OP_ISFREE:
417                for (i = 0; i < nlongs_reg; i++) {
418                        if (bitmap[index + i] & mask)
419                                goto done;
420                }
421                ret = 1;
422                break;
423
424        case REG_OP_ALLOC:
425                for (i = 0; i < nlongs_reg; i++)
426                        bitmap[index + i] |= mask;
427                break;
428
429        case REG_OP_RELEASE:
430                for (i = 0; i < nlongs_reg; i++)
431                        bitmap[index + i] &= ~mask;
432                break;
433        }
434done:
435        return ret;
436}
437
438static inline int
439bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
440{
441        int pos;
442        int end;
443
444        for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
445                if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
446                        continue;
447                __reg_op(bitmap, pos, order, REG_OP_ALLOC);
448                return pos;
449        }
450        return -ENOMEM;
451}
452
453static inline int
454bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
455{
456        if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
457                return -EBUSY;
458        __reg_op(bitmap, pos, order, REG_OP_ALLOC);
459        return 0;
460}
461
462static inline void
463bitmap_release_region(unsigned long *bitmap, int pos, int order)
464{
465        __reg_op(bitmap, pos, order, REG_OP_RELEASE);
466}
467
468
469#define for_each_set_bit(bit, addr, size) \
470	for ((bit) = find_first_bit((addr), (size));		\
471	     (bit) < (size);					\
472	     (bit) = find_next_bit((addr), (size), (bit) + 1))
473
474#endif	/* _LINUX_BITOPS_H_ */
475