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 _LINUXKPI_LINUX_BITMAP_H_
30 #define	_LINUXKPI_LINUX_BITMAP_H_
31 
32 #include <linux/bitops.h>
33 #include <linux/slab.h>
34 
35 static inline void
36 bitmap_zero(unsigned long *addr, const unsigned int size)
37 {
38 	memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
39 }
40 
41 static inline void
42 bitmap_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 
52 static inline int
53 bitmap_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 
73 static inline int
74 bitmap_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 
94 static inline void
95 bitmap_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 
117 static inline void
118 bitmap_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 
140 static inline unsigned int
141 bitmap_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 
150 retry:
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 
167 static inline unsigned int
168 bitmap_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 
176 static inline int
177 bitmap_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 
191 static inline int
192 bitmap_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 
200 static inline void
201 bitmap_release_region(unsigned long *bitmap, int pos, int order)
202 {
203 	linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
204 }
205 
206 static inline unsigned int
207 bitmap_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 
225 static inline int
226 bitmap_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 
247 static inline int
248 bitmap_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 
269 static inline void
270 bitmap_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 
280 static inline void
281 bitmap_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 
291 static inline void
292 bitmap_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 
302 static inline void
303 bitmap_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 
313 static inline void
314 bitmap_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 
324 static inline void
325 bitmap_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 
335 static inline unsigned long *
336 bitmap_alloc(unsigned int size, gfp_t flags)
337 {
338 	return (kmalloc_array(BITS_TO_LONGS(size),
339 	    sizeof(unsigned long), flags));
340 }
341 
342 static inline unsigned long *
343 bitmap_zalloc(unsigned int size, gfp_t flags)
344 {
345 	return (bitmap_alloc(size, flags | __GFP_ZERO));
346 }
347 
348 static inline void
349 bitmap_free(const unsigned long *bitmap)
350 {
351 	kfree(bitmap);
352 }
353 
354 #endif					/* _LINUXKPI_LINUX_BITMAP_H_ */
355