1/*
2 * Copyright (c) 2013-2017 Mellanox Technologies, Ltd.
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
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice unmodified, this list of conditions, and the following
10 *    disclaimer.
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 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#ifndef _LINUXKPI_LINUX_BITMAP_H_
28#define	_LINUXKPI_LINUX_BITMAP_H_
29
30#include <linux/bitops.h>
31#include <linux/slab.h>
32
33static inline void
34bitmap_zero(unsigned long *addr, const unsigned int size)
35{
36	memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
37}
38
39static inline void
40bitmap_fill(unsigned long *addr, const unsigned int size)
41{
42	const unsigned int tail = size & (BITS_PER_LONG - 1);
43
44	memset(addr, 0xff, BIT_WORD(size) * sizeof(long));
45
46	if (tail)
47		addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
48}
49
50static inline int
51bitmap_full(unsigned long *addr, const unsigned int size)
52{
53	const unsigned int end = BIT_WORD(size);
54	const unsigned int tail = size & (BITS_PER_LONG - 1);
55	unsigned int i;
56
57	for (i = 0; i != end; i++) {
58		if (addr[i] != ~0UL)
59			return (0);
60	}
61
62	if (tail) {
63		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
64
65		if ((addr[end] & mask) != mask)
66			return (0);
67	}
68	return (1);
69}
70
71static inline int
72bitmap_empty(unsigned long *addr, const unsigned int size)
73{
74	const unsigned int end = BIT_WORD(size);
75	const unsigned int tail = size & (BITS_PER_LONG - 1);
76	unsigned int i;
77
78	for (i = 0; i != end; i++) {
79		if (addr[i] != 0)
80			return (0);
81	}
82
83	if (tail) {
84		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
85
86		if ((addr[end] & mask) != 0)
87			return (0);
88	}
89	return (1);
90}
91
92static inline void
93bitmap_set(unsigned long *map, unsigned int start, int nr)
94{
95	const unsigned int size = start + nr;
96	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
97	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
98
99	map += BIT_WORD(start);
100
101	while (nr - bits_to_set >= 0) {
102		*map |= mask_to_set;
103		nr -= bits_to_set;
104		bits_to_set = BITS_PER_LONG;
105		mask_to_set = ~0UL;
106		map++;
107	}
108
109	if (nr) {
110		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
111		*map |= mask_to_set;
112	}
113}
114
115static inline void
116bitmap_clear(unsigned long *map, unsigned int start, int nr)
117{
118	const unsigned int size = start + nr;
119	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
120	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
121
122	map += BIT_WORD(start);
123
124	while (nr - bits_to_clear >= 0) {
125		*map &= ~mask_to_clear;
126		nr -= bits_to_clear;
127		bits_to_clear = BITS_PER_LONG;
128		mask_to_clear = ~0UL;
129		map++;
130	}
131
132	if (nr) {
133		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
134		*map &= ~mask_to_clear;
135	}
136}
137
138static inline unsigned int
139bitmap_find_next_zero_area_off(const unsigned long *map,
140    const unsigned int size, unsigned int start,
141    unsigned int nr, unsigned int align_mask,
142    unsigned int align_offset)
143{
144	unsigned int index;
145	unsigned int end;
146	unsigned int i;
147
148retry:
149	index = find_next_zero_bit(map, size, start);
150
151	index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;
152
153	end = index + nr;
154	if (end > size)
155		return (end);
156
157	i = find_next_bit(map, end, index);
158	if (i < end) {
159		start = i + 1;
160		goto retry;
161	}
162	return (index);
163}
164
165static inline unsigned int
166bitmap_find_next_zero_area(const unsigned long *map,
167    const unsigned int size, unsigned int start,
168    unsigned int nr, unsigned int align_mask)
169{
170	return (bitmap_find_next_zero_area_off(map, size,
171	    start, nr, align_mask, 0));
172}
173
174static inline int
175bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
176{
177	int pos;
178	int end;
179
180	for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
181		if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
182			continue;
183		linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
184		return (pos);
185	}
186	return (-ENOMEM);
187}
188
189static inline int
190bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
191{
192	if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
193		return (-EBUSY);
194	linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
195	return (0);
196}
197
198static inline void
199bitmap_release_region(unsigned long *bitmap, int pos, int order)
200{
201	linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
202}
203
204static inline unsigned int
205bitmap_weight(unsigned long *addr, const unsigned int size)
206{
207	const unsigned int end = BIT_WORD(size);
208	const unsigned int tail = size & (BITS_PER_LONG - 1);
209	unsigned int retval = 0;
210	unsigned int i;
211
212	for (i = 0; i != end; i++)
213		retval += hweight_long(addr[i]);
214
215	if (tail) {
216		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
217
218		retval += hweight_long(addr[end] & mask);
219	}
220	return (retval);
221}
222
223static inline int
224bitmap_equal(const unsigned long *pa,
225    const unsigned long *pb, unsigned size)
226{
227	const unsigned int end = BIT_WORD(size);
228	const unsigned int tail = size & (BITS_PER_LONG - 1);
229	unsigned int i;
230
231	for (i = 0; i != end; i++) {
232		if (pa[i] != pb[i])
233			return (0);
234	}
235
236	if (tail) {
237		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
238
239		if ((pa[end] ^ pb[end]) & mask)
240			return (0);
241	}
242	return (1);
243}
244
245static inline int
246bitmap_subset(const unsigned long *pa,
247    const unsigned long *pb, unsigned size)
248{
249	const unsigned end = BIT_WORD(size);
250	const unsigned tail = size & (BITS_PER_LONG - 1);
251	unsigned i;
252
253	for (i = 0; i != end; i++) {
254		if (pa[i] & ~pb[i])
255			return (0);
256	}
257
258	if (tail) {
259		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
260
261		if (pa[end] & ~pb[end] & mask)
262			return (0);
263	}
264	return (1);
265}
266
267static inline bool
268bitmap_intersects(const unsigned long *pa, const unsigned long *pb,
269    unsigned size)
270{
271	const unsigned end = BIT_WORD(size);
272	const unsigned tail = size & (BITS_PER_LONG - 1);
273	unsigned i;
274
275	for (i = 0; i != end; i++)
276		if (pa[i] & pb[i])
277			return (true);
278
279	if (tail) {
280		 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
281
282		if (pa[end] & pb[end] & mask)
283			return (true);
284	}
285	return (false);
286}
287
288static inline void
289bitmap_complement(unsigned long *dst, const unsigned long *src,
290    const unsigned int size)
291{
292	const unsigned int end = BITS_TO_LONGS(size);
293	unsigned int i;
294
295	for (i = 0; i != end; i++)
296		dst[i] = ~src[i];
297}
298
299static inline void
300bitmap_copy(unsigned long *dst, const unsigned long *src,
301    const unsigned int size)
302{
303	const unsigned int end = BITS_TO_LONGS(size);
304	unsigned int i;
305
306	for (i = 0; i != end; i++)
307		dst[i] = src[i];
308}
309
310static inline void
311bitmap_to_arr32(uint32_t *dst, const unsigned long *src, unsigned int size)
312{
313	const unsigned int end = howmany(size, 32);
314
315#ifdef __LP64__
316	unsigned int i = 0;
317	while (i < end) {
318		dst[i++] = (uint32_t)(*src & UINT_MAX);
319		if (i < end)
320			dst[i++] = (uint32_t)(*src >> 32);
321		src++;
322	}
323#else
324	bitmap_copy((unsigned long *)dst, src, size);
325#endif
326	if ((size % 32) != 0) /* Linux uses BITS_PER_LONG. Seems to be a bug */
327		dst[end - 1] &= (uint32_t)(UINT_MAX >> (32 - (size % 32)));
328}
329
330static inline void
331bitmap_from_arr32(unsigned long *dst, const uint32_t *src,
332    unsigned int size)
333{
334	const unsigned int end = BIT_WORD(size);
335	const unsigned int tail = size & (BITS_PER_LONG - 1);
336
337#ifdef __LP64__
338	const unsigned int end32 = howmany(size, 32);
339	unsigned int i = 0;
340
341	while (i < end32) {
342		dst[i++/2] = (unsigned long) *(src++);
343		if (i < end32)
344			dst[i++/2] |= ((unsigned long) *(src++)) << 32;
345	}
346#else
347	bitmap_copy(dst, (const unsigned long *)src, size);
348#endif
349	if ((size % BITS_PER_LONG) != 0)
350		dst[end] &= BITMAP_LAST_WORD_MASK(tail);
351}
352
353static inline void
354bitmap_or(unsigned long *dst, const unsigned long *src1,
355    const unsigned long *src2, const unsigned int size)
356{
357	const unsigned int end = BITS_TO_LONGS(size);
358	unsigned int i;
359
360	for (i = 0; i != end; i++)
361		dst[i] = src1[i] | src2[i];
362}
363
364static inline void
365bitmap_and(unsigned long *dst, const unsigned long *src1,
366    const unsigned long *src2, const unsigned int size)
367{
368	const unsigned int end = BITS_TO_LONGS(size);
369	unsigned int i;
370
371	for (i = 0; i != end; i++)
372		dst[i] = src1[i] & src2[i];
373}
374
375static inline void
376bitmap_andnot(unsigned long *dst, const unsigned long *src1,
377    const unsigned long *src2, const unsigned int size)
378{
379	const unsigned int end = BITS_TO_LONGS(size);
380	unsigned int i;
381
382	for (i = 0; i != end; i++)
383		dst[i] = src1[i] & ~src2[i];
384}
385
386static inline void
387bitmap_xor(unsigned long *dst, const unsigned long *src1,
388    const unsigned long *src2, const unsigned int size)
389{
390	const unsigned int end = BITS_TO_LONGS(size);
391	unsigned int i;
392
393	for (i = 0; i != end; i++)
394		dst[i] = src1[i] ^ src2[i];
395}
396
397static inline void
398bitmap_shift_right(unsigned long *dst, const unsigned long *src,
399    unsigned int shift, unsigned int size)
400{
401	const unsigned int end = BITS_TO_LONGS(size);
402	const unsigned int tail = size & (BITS_PER_LONG - 1);
403	const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
404	const unsigned int off = BIT_WORD(shift);
405	const unsigned int rem = shift & (BITS_PER_LONG - 1);
406	unsigned long left, right;
407	unsigned int i, srcpos;
408
409	for (i = 0, srcpos = off; srcpos < end; i++, srcpos++) {
410		right = src[srcpos];
411		left = 0;
412
413		if (srcpos == end - 1)
414			right &= mask;
415
416		if (rem != 0) {
417			right >>= rem;
418			if (srcpos + 1 < end) {
419				left = src[srcpos + 1];
420				if (srcpos + 1 == end - 1)
421					left &= mask;
422				left <<= (BITS_PER_LONG - rem);
423			}
424		}
425		dst[i] = left | right;
426	}
427	if (off != 0)
428		memset(dst + end - off, 0, off * sizeof(unsigned long));
429}
430
431static inline unsigned long *
432bitmap_alloc(unsigned int size, gfp_t flags)
433{
434	return (kmalloc_array(BITS_TO_LONGS(size),
435	    sizeof(unsigned long), flags));
436}
437
438static inline unsigned long *
439bitmap_zalloc(unsigned int size, gfp_t flags)
440{
441	return (bitmap_alloc(size, flags | __GFP_ZERO));
442}
443
444static inline void
445bitmap_free(const unsigned long *bitmap)
446{
447	kfree(bitmap);
448}
449
450#endif					/* _LINUXKPI_LINUX_BITMAP_H_ */
451