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 * $FreeBSD$
27 */
28
29#ifndef _LINUX_BITMAP_H_
30#define	_LINUX_BITMAP_H_
31
32#include <linux/bitops.h>
33#include <linux/slab.h>
34
35static inline void
36bitmap_zero(unsigned long *addr, const unsigned int size)
37{
38	memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
39}
40
41static inline void
42bitmap_fill(unsigned long *addr, const unsigned int size)
43{
44	const unsigned int tail = size & (BITS_PER_LONG - 1);
45
46	memset(addr, 0xff, BIT_WORD(size) * sizeof(long));
47
48	if (tail)
49		addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
50}
51
52static inline int
53bitmap_full(unsigned long *addr, const unsigned int size)
54{
55	const unsigned int end = BIT_WORD(size);
56	const unsigned int tail = size & (BITS_PER_LONG - 1);
57	unsigned int i;
58
59	for (i = 0; i != end; i++) {
60		if (addr[i] != ~0UL)
61			return (0);
62	}
63
64	if (tail) {
65		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
66
67		if ((addr[end] & mask) != mask)
68			return (0);
69	}
70	return (1);
71}
72
73static inline int
74bitmap_empty(unsigned long *addr, const unsigned int size)
75{
76	const unsigned int end = BIT_WORD(size);
77	const unsigned int tail = size & (BITS_PER_LONG - 1);
78	unsigned int i;
79
80	for (i = 0; i != end; i++) {
81		if (addr[i] != 0)
82			return (0);
83	}
84
85	if (tail) {
86		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
87
88		if ((addr[end] & mask) != 0)
89			return (0);
90	}
91	return (1);
92}
93
94static inline void
95bitmap_set(unsigned long *map, unsigned int start, int nr)
96{
97	const unsigned int size = start + nr;
98	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
99	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
100
101	map += BIT_WORD(start);
102
103	while (nr - bits_to_set >= 0) {
104		*map |= mask_to_set;
105		nr -= bits_to_set;
106		bits_to_set = BITS_PER_LONG;
107		mask_to_set = ~0UL;
108		map++;
109	}
110
111	if (nr) {
112		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
113		*map |= mask_to_set;
114	}
115}
116
117static inline void
118bitmap_clear(unsigned long *map, unsigned int start, int nr)
119{
120	const unsigned int size = start + nr;
121	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
122	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
123
124	map += BIT_WORD(start);
125
126	while (nr - bits_to_clear >= 0) {
127		*map &= ~mask_to_clear;
128		nr -= bits_to_clear;
129		bits_to_clear = BITS_PER_LONG;
130		mask_to_clear = ~0UL;
131		map++;
132	}
133
134	if (nr) {
135		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
136		*map &= ~mask_to_clear;
137	}
138}
139
140static inline unsigned int
141bitmap_find_next_zero_area_off(const unsigned long *map,
142    const unsigned int size, unsigned int start,
143    unsigned int nr, unsigned int align_mask,
144    unsigned int align_offset)
145{
146	unsigned int index;
147	unsigned int end;
148	unsigned int i;
149
150retry:
151	index = find_next_zero_bit(map, size, start);
152
153	index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;
154
155	end = index + nr;
156	if (end > size)
157		return (end);
158
159	i = find_next_bit(map, end, index);
160	if (i < end) {
161		start = i + 1;
162		goto retry;
163	}
164	return (index);
165}
166
167static inline unsigned int
168bitmap_find_next_zero_area(const unsigned long *map,
169    const unsigned int size, unsigned int start,
170    unsigned int nr, unsigned int align_mask)
171{
172	return (bitmap_find_next_zero_area_off(map, size,
173	    start, nr, align_mask, 0));
174}
175
176static inline int
177bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
178{
179	int pos;
180	int end;
181
182	for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
183		if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
184			continue;
185		linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
186		return (pos);
187	}
188	return (-ENOMEM);
189}
190
191static inline int
192bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
193{
194	if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
195		return (-EBUSY);
196	linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
197	return (0);
198}
199
200static inline void
201bitmap_release_region(unsigned long *bitmap, int pos, int order)
202{
203	linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
204}
205
206static inline unsigned int
207bitmap_weight(unsigned long *addr, const unsigned int size)
208{
209	const unsigned int end = BIT_WORD(size);
210	const unsigned int tail = size & (BITS_PER_LONG - 1);
211	unsigned int retval = 0;
212	unsigned int i;
213
214	for (i = 0; i != end; i++)
215		retval += hweight_long(addr[i]);
216
217	if (tail) {
218		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
219
220		retval += hweight_long(addr[end] & mask);
221	}
222	return (retval);
223}
224
225static inline int
226bitmap_equal(const unsigned long *pa,
227    const unsigned long *pb, unsigned size)
228{
229	const unsigned int end = BIT_WORD(size);
230	const unsigned int tail = size & (BITS_PER_LONG - 1);
231	unsigned int i;
232
233	for (i = 0; i != end; i++) {
234		if (pa[i] != pb[i])
235			return (0);
236	}
237
238	if (tail) {
239		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
240
241		if ((pa[end] ^ pb[end]) & mask)
242			return (0);
243	}
244	return (1);
245}
246
247static inline int
248bitmap_subset(const unsigned long *pa,
249    const unsigned long *pb, unsigned size)
250{
251	const unsigned end = BIT_WORD(size);
252	const unsigned tail = size & (BITS_PER_LONG - 1);
253	unsigned i;
254
255	for (i = 0; i != end; i++) {
256		if (pa[i] & ~pb[i])
257			return (0);
258	}
259
260	if (tail) {
261		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
262
263		if (pa[end] & ~pb[end] & mask)
264			return (0);
265	}
266	return (1);
267}
268
269static inline void
270bitmap_complement(unsigned long *dst, const unsigned long *src,
271    const unsigned int size)
272{
273	const unsigned int end = BITS_TO_LONGS(size);
274	unsigned int i;
275
276	for (i = 0; i != end; i++)
277		dst[i] = ~src[i];
278}
279
280static inline void
281bitmap_copy(unsigned long *dst, const unsigned long *src,
282    const unsigned int size)
283{
284	const unsigned int end = BITS_TO_LONGS(size);
285	unsigned int i;
286
287	for (i = 0; i != end; i++)
288		dst[i] = src[i];
289}
290
291static inline void
292bitmap_or(unsigned long *dst, const unsigned long *src1,
293    const unsigned long *src2, const unsigned int size)
294{
295	const unsigned int end = BITS_TO_LONGS(size);
296	unsigned int i;
297
298	for (i = 0; i != end; i++)
299		dst[i] = src1[i] | src2[i];
300}
301
302static inline void
303bitmap_and(unsigned long *dst, const unsigned long *src1,
304    const unsigned long *src2, const unsigned int size)
305{
306	const unsigned int end = BITS_TO_LONGS(size);
307	unsigned int i;
308
309	for (i = 0; i != end; i++)
310		dst[i] = src1[i] & src2[i];
311}
312
313static inline void
314bitmap_andnot(unsigned long *dst, const unsigned long *src1,
315    const unsigned long *src2, const unsigned int size)
316{
317	const unsigned int end = BITS_TO_LONGS(size);
318	unsigned int i;
319
320	for (i = 0; i != end; i++)
321		dst[i] = src1[i] & ~src2[i];
322}
323
324static inline void
325bitmap_xor(unsigned long *dst, const unsigned long *src1,
326    const unsigned long *src2, const unsigned int size)
327{
328	const unsigned int end = BITS_TO_LONGS(size);
329	unsigned int i;
330
331	for (i = 0; i != end; i++)
332		dst[i] = src1[i] ^ src2[i];
333}
334
335static inline unsigned long *
336bitmap_alloc(unsigned int size, gfp_t flags)
337{
338	return (kmalloc_array(BITS_TO_LONGS(size),
339	    sizeof(unsigned long), flags));
340}
341
342static inline unsigned long *
343bitmap_zalloc(unsigned int size, gfp_t flags)
344{
345	return (bitmap_alloc(size, flags | __GFP_ZERO));
346}
347
348static inline void
349bitmap_free(const unsigned long *bitmap)
350{
351	kfree(bitmap);
352}
353
354#endif					/* _LINUX_BITMAP_H_ */
355