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 
33 static inline void
34 bitmap_zero(unsigned long *addr, const unsigned int size)
35 {
36 	memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
37 }
38 
39 static inline void
40 bitmap_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 
50 static inline int
51 bitmap_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 
71 static inline int
72 bitmap_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 
92 static inline void
93 bitmap_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 
115 static inline void
116 bitmap_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 
138 static inline unsigned int
139 bitmap_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 
148 retry:
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 
165 static inline unsigned int
166 bitmap_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 
174 static inline int
175 bitmap_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 
189 static inline int
190 bitmap_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 
198 static inline void
199 bitmap_release_region(unsigned long *bitmap, int pos, int order)
200 {
201 	linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
202 }
203 
204 static inline unsigned int
205 bitmap_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 
223 static inline int
224 bitmap_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 
245 static inline int
246 bitmap_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 
267 static inline void
268 bitmap_complement(unsigned long *dst, const unsigned long *src,
269     const unsigned int size)
270 {
271 	const unsigned int end = BITS_TO_LONGS(size);
272 	unsigned int i;
273 
274 	for (i = 0; i != end; i++)
275 		dst[i] = ~src[i];
276 }
277 
278 static inline void
279 bitmap_copy(unsigned long *dst, const unsigned long *src,
280     const unsigned int size)
281 {
282 	const unsigned int end = BITS_TO_LONGS(size);
283 	unsigned int i;
284 
285 	for (i = 0; i != end; i++)
286 		dst[i] = src[i];
287 }
288 
289 static inline void
290 bitmap_to_arr32(uint32_t *dst, const unsigned long *src, unsigned int size)
291 {
292 	const unsigned int end = howmany(size, 32);
293 
294 #ifdef __LP64__
295 	unsigned int i = 0;
296 	while (i < end) {
297 		dst[i++] = (uint32_t)(*src & UINT_MAX);
298 		if (i < end)
299 			dst[i++] = (uint32_t)(*src >> 32);
300 		src++;
301 	}
302 #else
303 	bitmap_copy((unsigned long *)dst, src, size);
304 #endif
305 	if ((size % 32) != 0) /* Linux uses BITS_PER_LONG. Seems to be a bug */
306 		dst[end - 1] &= (uint32_t)(UINT_MAX >> (32 - (size % 32)));
307 }
308 
309 static inline void
310 bitmap_or(unsigned long *dst, const unsigned long *src1,
311     const unsigned long *src2, const unsigned int size)
312 {
313 	const unsigned int end = BITS_TO_LONGS(size);
314 	unsigned int i;
315 
316 	for (i = 0; i != end; i++)
317 		dst[i] = src1[i] | src2[i];
318 }
319 
320 static inline void
321 bitmap_and(unsigned long *dst, const unsigned long *src1,
322     const unsigned long *src2, const unsigned int size)
323 {
324 	const unsigned int end = BITS_TO_LONGS(size);
325 	unsigned int i;
326 
327 	for (i = 0; i != end; i++)
328 		dst[i] = src1[i] & src2[i];
329 }
330 
331 static inline void
332 bitmap_andnot(unsigned long *dst, const unsigned long *src1,
333     const unsigned long *src2, const unsigned int size)
334 {
335 	const unsigned int end = BITS_TO_LONGS(size);
336 	unsigned int i;
337 
338 	for (i = 0; i != end; i++)
339 		dst[i] = src1[i] & ~src2[i];
340 }
341 
342 static inline void
343 bitmap_xor(unsigned long *dst, const unsigned long *src1,
344     const unsigned long *src2, const unsigned int size)
345 {
346 	const unsigned int end = BITS_TO_LONGS(size);
347 	unsigned int i;
348 
349 	for (i = 0; i != end; i++)
350 		dst[i] = src1[i] ^ src2[i];
351 }
352 
353 static inline unsigned long *
354 bitmap_alloc(unsigned int size, gfp_t flags)
355 {
356 	return (kmalloc_array(BITS_TO_LONGS(size),
357 	    sizeof(unsigned long), flags));
358 }
359 
360 static inline unsigned long *
361 bitmap_zalloc(unsigned int size, gfp_t flags)
362 {
363 	return (bitmap_alloc(size, flags | __GFP_ZERO));
364 }
365 
366 static inline void
367 bitmap_free(const unsigned long *bitmap)
368 {
369 	kfree(bitmap);
370 }
371 
372 #endif					/* _LINUXKPI_LINUX_BITMAP_H_ */
373