1/* SPDX-License-Identifier: BSD-3-Clause */
2/*  Copyright (c) 2024, Intel Corporation
3 *  All rights reserved.
4 *
5 *  Redistribution and use in source and binary forms, with or without
6 *  modification, are permitted provided that the following conditions are met:
7 *
8 *   1. Redistributions of source code must retain the above copyright notice,
9 *      this list of conditions and the following disclaimer.
10 *
11 *   2. Redistributions in binary form must reproduce the above copyright
12 *      notice, this list of conditions and the following disclaimer in the
13 *      documentation and/or other materials provided with the distribution.
14 *
15 *   3. Neither the name of the Intel Corporation nor the names of its
16 *      contributors may be used to endorse or promote products derived from
17 *      this software without specific prior written permission.
18 *
19 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 *  POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#ifndef _ICE_BITOPS_H_
33#define _ICE_BITOPS_H_
34
35#include "ice_defs.h"
36#include "ice_osdep.h"
37
38/* Define the size of the bitmap chunk */
39typedef u32 ice_bitmap_t;
40
41/* NOTE!
42 * Do not use any of the functions declared in this file
43 * on memory that was not declared with ice_declare_bitmap.
44 * Not following this rule might cause issues like split
45 * locks.
46 */
47
48/* Number of bits per bitmap chunk */
49#define BITS_PER_CHUNK		(BITS_PER_BYTE * sizeof(ice_bitmap_t))
50/* Determine which chunk a bit belongs in */
51#define BIT_CHUNK(nr)		((nr) / BITS_PER_CHUNK)
52/* How many chunks are required to store this many bits */
53#define BITS_TO_CHUNKS(sz)	(((sz) + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK)
54/* Which bit inside a chunk this bit corresponds to */
55#define BIT_IN_CHUNK(nr)	((nr) % BITS_PER_CHUNK)
56/* How many bits are valid in the last chunk, assumes nr > 0 */
57#define LAST_CHUNK_BITS(nr)	((((nr) - 1) % BITS_PER_CHUNK) + 1)
58/* Generate a bitmask of valid bits in the last chunk, assumes nr > 0 */
59#define LAST_CHUNK_MASK(nr)	(((ice_bitmap_t)~0) >> \
60				 (BITS_PER_CHUNK - LAST_CHUNK_BITS(nr)))
61
62#define ice_declare_bitmap(A, sz) \
63	ice_bitmap_t A[BITS_TO_CHUNKS(sz)]
64
65static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
66{
67	return !!(*bitmap & BIT(nr));
68}
69
70/*
71 * If atomic version of the bitops are required, each specific OS
72 * implementation will need to implement OS/platform specific atomic
73 * version of the functions below:
74 *
75 * ice_clear_bit_internal
76 * ice_set_bit_internal
77 * ice_test_and_clear_bit_internal
78 * ice_test_and_set_bit_internal
79 *
80 * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
81 * implementation.
82 */
83static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
84{
85	*bitmap &= ~BIT(nr);
86}
87
88static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
89{
90	*bitmap |= BIT(nr);
91}
92
93static inline bool ice_test_and_clear_bit_internal(u16 nr,
94						   ice_bitmap_t *bitmap)
95{
96	if (ice_is_bit_set_internal(nr, bitmap)) {
97		ice_clear_bit_internal(nr, bitmap);
98		return true;
99	}
100	return false;
101}
102
103static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
104{
105	if (ice_is_bit_set_internal(nr, bitmap))
106		return true;
107
108	ice_set_bit_internal(nr, bitmap);
109	return false;
110}
111
112/**
113 * ice_is_bit_set - Check state of a bit in a bitmap
114 * @bitmap: the bitmap to check
115 * @nr: the bit to check
116 *
117 * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
118 * is less than the size of the bitmap.
119 */
120static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
121{
122	return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
123				       &bitmap[BIT_CHUNK(nr)]);
124}
125
126/**
127 * ice_clear_bit - Clear a bit in a bitmap
128 * @bitmap: the bitmap to change
129 * @nr: the bit to change
130 *
131 * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
132 * bitmap.
133 */
134static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
135{
136	ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
137}
138
139/**
140 * ice_set_bit - Set a bit in a bitmap
141 * @bitmap: the bitmap to change
142 * @nr: the bit to change
143 *
144 * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
145 * bitmap.
146 */
147static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
148{
149	ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
150}
151
152/**
153 * ice_test_and_clear_bit - Atomically clear a bit and return the old bit value
154 * @nr: the bit to change
155 * @bitmap: the bitmap to change
156 *
157 * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
158 * of the bitmap.
159 */
160static inline bool
161ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
162{
163	return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
164					       &bitmap[BIT_CHUNK(nr)]);
165}
166
167/**
168 * ice_test_and_set_bit - Atomically set a bit and return the old bit value
169 * @nr: the bit to change
170 * @bitmap: the bitmap to change
171 *
172 * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
173 * the bitmap.
174 */
175static inline bool
176ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
177{
178	return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
179					     &bitmap[BIT_CHUNK(nr)]);
180}
181
182/* ice_zero_bitmap - set bits of bitmap to zero.
183 * @bmp: bitmap to set zeros
184 * @size: Size of the bitmaps in bits
185 *
186 * Set all of the bits in a bitmap to zero. Note that this function assumes it
187 * operates on an ice_bitmap_t which was declared using ice_declare_bitmap. It
188 * will zero every bit in the last chunk, even if those bits are beyond the
189 * size.
190 */
191static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
192{
193	ice_memset(bmp, 0, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
194		   ICE_NONDMA_MEM);
195}
196
197/**
198 * ice_and_bitmap - bitwise AND 2 bitmaps and store result in dst bitmap
199 * @dst: Destination bitmap that receive the result of the operation
200 * @bmp1: The first bitmap to intersect
201 * @bmp2: The second bitmap to intersect wit the first
202 * @size: Size of the bitmaps in bits
203 *
204 * This function performs a bitwise AND on two "source" bitmaps of the same size
205 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
206 * size as the "source" bitmaps to avoid buffer overflows. This function returns
207 * a non-zero value if at least one bit location from both "source" bitmaps is
208 * non-zero.
209 */
210static inline int
211ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
212	       const ice_bitmap_t *bmp2, u16 size)
213{
214	ice_bitmap_t res = 0, mask;
215	u16 i;
216
217	/* Handle all but the last chunk */
218	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) {
219		dst[i] = bmp1[i] & bmp2[i];
220		res |= dst[i];
221	}
222
223	/* We want to take care not to modify any bits outside of the bitmap
224	 * size, even in the destination bitmap. Thus, we won't directly
225	 * assign the last bitmap, but instead use a bitmask to ensure we only
226	 * modify bits which are within the size, and leave any bits above the
227	 * size value alone.
228	 */
229	mask = LAST_CHUNK_MASK(size);
230	dst[i] = (dst[i] & ~mask) | ((bmp1[i] & bmp2[i]) & mask);
231	res |= dst[i] & mask;
232
233	return res != 0;
234}
235
236/**
237 * ice_or_bitmap - bitwise OR 2 bitmaps and store result in dst bitmap
238 * @dst: Destination bitmap that receive the result of the operation
239 * @bmp1: The first bitmap to intersect
240 * @bmp2: The second bitmap to intersect wit the first
241 * @size: Size of the bitmaps in bits
242 *
243 * This function performs a bitwise OR on two "source" bitmaps of the same size
244 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
245 * size as the "source" bitmaps to avoid buffer overflows.
246 */
247static inline void
248ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
249	      const ice_bitmap_t *bmp2, u16 size)
250{
251	ice_bitmap_t mask;
252	u16 i;
253
254	/* Handle all but last chunk */
255	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
256		dst[i] = bmp1[i] | bmp2[i];
257
258	/* We want to only OR bits within the size. Furthermore, we also do
259	 * not want to modify destination bits which are beyond the specified
260	 * size. Use a bitmask to ensure that we only modify the bits that are
261	 * within the specified size.
262	 */
263	mask = LAST_CHUNK_MASK(size);
264	dst[i] = (dst[i] & ~mask) | ((bmp1[i] | bmp2[i]) & mask);
265}
266
267/**
268 * ice_xor_bitmap - bitwise XOR 2 bitmaps and store result in dst bitmap
269 * @dst: Destination bitmap that receive the result of the operation
270 * @bmp1: The first bitmap of XOR operation
271 * @bmp2: The second bitmap to XOR with the first
272 * @size: Size of the bitmaps in bits
273 *
274 * This function performs a bitwise XOR on two "source" bitmaps of the same size
275 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
276 * size as the "source" bitmaps to avoid buffer overflows.
277 */
278static inline void
279ice_xor_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
280	       const ice_bitmap_t *bmp2, u16 size)
281{
282	ice_bitmap_t mask;
283	u16 i;
284
285	/* Handle all but last chunk */
286	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
287		dst[i] = bmp1[i] ^ bmp2[i];
288
289	/* We want to only XOR bits within the size. Furthermore, we also do
290	 * not want to modify destination bits which are beyond the specified
291	 * size. Use a bitmask to ensure that we only modify the bits that are
292	 * within the specified size.
293	 */
294	mask = LAST_CHUNK_MASK(size);
295	dst[i] = (dst[i] & ~mask) | ((bmp1[i] ^ bmp2[i]) & mask);
296}
297
298/**
299 * ice_andnot_bitmap - bitwise ANDNOT 2 bitmaps and result in dst bitmap
300 * @dst: Destination bitmap that receive the result of the operation
301 * @bmp1: The first bitmap of ANDNOT operation
302 * @bmp2: The second bitmap to ANDNOT operation
303 * @size: Size of the bitmaps in bits
304 *
305 * This function performs a bitwise ANDNOT on two "source" bitmaps of the same
306 * size, and stores the result to "dst" bitmap. The "dst" bitmap must be of the
307 * same size as the "source" bitmaps to avoid buffer overflows.
308 */
309static inline void
310ice_andnot_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
311		  const ice_bitmap_t *bmp2, u16 size)
312{
313	ice_bitmap_t mask;
314	u16 i;
315
316	/* Handle all but last chunk */
317	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
318		dst[i] = bmp1[i] & ~bmp2[i];
319
320	/* We want to only clear bits within the size. Furthermore, we also do
321	 * not want to modify destination bits which are beyond the specified
322	 * size. Use a bitmask to ensure that we only modify the bits that are
323	 * within the specified size.
324	 */
325	mask = LAST_CHUNK_MASK(size);
326	dst[i] = (dst[i] & ~mask) | ((bmp1[i] & ~bmp2[i]) & mask);
327}
328
329/**
330 * ice_find_next_bit - Find the index of the next set bit of a bitmap
331 * @bitmap: the bitmap to scan
332 * @size: the size in bits of the bitmap
333 * @offset: the offset to start at
334 *
335 * Scans the bitmap and returns the index of the first set bit which is equal
336 * to or after the specified offset. Will return size if no bits are set.
337 */
338static inline u16
339ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
340{
341	u16 i, j;
342
343	if (offset >= size)
344		return size;
345
346	/* Since the starting position may not be directly on a chunk
347	 * boundary, we need to be careful to handle the first chunk specially
348	 */
349	i = BIT_CHUNK(offset);
350	if (bitmap[i] != 0) {
351		u16 off = i * BITS_PER_CHUNK;
352
353		for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) {
354			if (ice_is_bit_set(bitmap, off + j))
355				return min(size, (u16)(off + j));
356		}
357	}
358
359	/* Now we handle the remaining chunks, if any */
360	for (i++; i < BITS_TO_CHUNKS(size); i++) {
361		if (bitmap[i] != 0) {
362			u16 off = i * BITS_PER_CHUNK;
363
364			for (j = 0; j < BITS_PER_CHUNK; j++) {
365				if (ice_is_bit_set(bitmap, off + j))
366					return min(size, (u16)(off + j));
367			}
368		}
369	}
370	return size;
371}
372
373/**
374 * ice_find_first_bit - Find the index of the first set bit of a bitmap
375 * @bitmap: the bitmap to scan
376 * @size: the size in bits of the bitmap
377 *
378 * Scans the bitmap and returns the index of the first set bit. Will return
379 * size if no bits are set.
380 */
381static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
382{
383	return ice_find_next_bit(bitmap, size, 0);
384}
385
386#define ice_for_each_set_bit(_bitpos, _addr, _maxlen)	\
387	for ((_bitpos) = ice_find_first_bit((_addr), (_maxlen)); \
388	     (_bitpos) < (_maxlen); \
389	     (_bitpos) = ice_find_next_bit((_addr), (_maxlen), (_bitpos) + 1))
390
391/**
392 * ice_is_any_bit_set - Return true of any bit in the bitmap is set
393 * @bitmap: the bitmap to check
394 * @size: the size of the bitmap
395 *
396 * Equivalent to checking if ice_find_first_bit returns a value less than the
397 * bitmap size.
398 */
399static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
400{
401	return ice_find_first_bit(bitmap, size) < size;
402}
403
404/**
405 * ice_cp_bitmap - copy bitmaps
406 * @dst: bitmap destination
407 * @src: bitmap to copy from
408 * @size: Size of the bitmaps in bits
409 *
410 * This function copy bitmap from src to dst. Note that this function assumes
411 * it is operating on a bitmap declared using ice_declare_bitmap. It will copy
412 * the entire last chunk even if this contains bits beyond the size.
413 */
414static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
415{
416	ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
417		   ICE_NONDMA_TO_NONDMA);
418}
419
420/**
421 * ice_bitmap_set - set a number of bits in bitmap from a starting position
422 * @dst: bitmap destination
423 * @pos: first bit position to set
424 * @num_bits: number of bits to set
425 *
426 * This function sets bits in a bitmap from pos to (pos + num_bits) - 1.
427 * Note that this function assumes it is operating on a bitmap declared using
428 * ice_declare_bitmap.
429 */
430static inline void
431ice_bitmap_set(ice_bitmap_t *dst, u16 pos, u16 num_bits)
432{
433	u16 i;
434
435	for (i = pos; i < pos + num_bits; i++)
436		ice_set_bit(i, dst);
437}
438
439/**
440 * ice_bitmap_hweight - hamming weight of bitmap
441 * @bm: bitmap pointer
442 * @size: size of bitmap (in bits)
443 *
444 * This function determines the number of set bits in a bitmap.
445 * Note that this function assumes it is operating on a bitmap declared using
446 * ice_declare_bitmap.
447 */
448static inline int
449ice_bitmap_hweight(ice_bitmap_t *bm, u16 size)
450{
451	int count = 0;
452	u16 bit = 0;
453
454	while (size > (bit = ice_find_next_bit(bm, size, bit))) {
455		count++;
456		bit++;
457	}
458
459	return count;
460}
461
462/**
463 * ice_cmp_bitmap - compares two bitmaps
464 * @bmp1: the bitmap to compare
465 * @bmp2: the bitmap to compare with bmp1
466 * @size: Size of the bitmaps in bits
467 *
468 * This function compares two bitmaps, and returns result as true or false.
469 */
470static inline bool
471ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
472{
473	ice_bitmap_t mask;
474	u16 i;
475
476	/* Handle all but last chunk */
477	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
478		if (bmp1[i] != bmp2[i])
479			return false;
480
481	/* We want to only compare bits within the size */
482	mask = LAST_CHUNK_MASK(size);
483	if ((bmp1[i] & mask) != (bmp2[i] & mask))
484		return false;
485
486	return true;
487}
488
489/**
490 * ice_bitmap_from_array32 - copies u32 array source into bitmap destination
491 * @dst: the destination bitmap
492 * @src: the source u32 array
493 * @size: size of the bitmap (in bits)
494 *
495 * This function copies the src bitmap stored in an u32 array into the dst
496 * bitmap stored as an ice_bitmap_t.
497 */
498static inline void
499ice_bitmap_from_array32(ice_bitmap_t *dst, u32 *src, u16 size)
500{
501	u32 remaining_bits, i;
502
503#define BITS_PER_U32	(sizeof(u32) * BITS_PER_BYTE)
504	/* clear bitmap so we only have to set when iterating */
505	ice_zero_bitmap(dst, size);
506
507	for (i = 0; i < (u32)(size / BITS_PER_U32); i++) {
508		u32 bit_offset = i * BITS_PER_U32;
509		u32 entry = src[i];
510		u32 j;
511
512		for (j = 0; j < BITS_PER_U32; j++) {
513			if (entry & BIT(j))
514				ice_set_bit((u16)(j + bit_offset), dst);
515		}
516	}
517
518	/* still need to check the leftover bits (i.e. if size isn't evenly
519	 * divisible by BITS_PER_U32
520	 **/
521	remaining_bits = size % BITS_PER_U32;
522	if (remaining_bits) {
523		u32 bit_offset = i * BITS_PER_U32;
524		u32 entry = src[i];
525		u32 j;
526
527		for (j = 0; j < remaining_bits; j++) {
528			if (entry & BIT(j))
529				ice_set_bit((u16)(j + bit_offset), dst);
530		}
531	}
532}
533
534#undef BIT_CHUNK
535#undef BIT_IN_CHUNK
536#undef LAST_CHUNK_BITS
537#undef LAST_CHUNK_MASK
538
539#endif /* _ICE_BITOPS_H_ */
540