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