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 
34 static inline void
35 bitmap_zero(unsigned long *addr, const unsigned int size)
36 {
37 	memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
38 }
39 
40 static inline void
41 bitmap_fill(unsigned long *addr, const unsigned int size)
42 {
43 	const unsigned int tail = size & (BITS_PER_LONG - 1);
44 
45 	memset(addr, 0xff, BIT_WORD(size) * sizeof(long));
46 
47 	if (tail)
48 		addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
49 }
50 
51 static inline int
52 bitmap_full(unsigned long *addr, const unsigned int size)
53 {
54 	const unsigned int end = BIT_WORD(size);
55 	const unsigned int tail = size & (BITS_PER_LONG - 1);
56 	unsigned int i;
57 
58 	for (i = 0; i != end; i++) {
59 		if (addr[i] != ~0UL)
60 			return (0);
61 	}
62 
63 	if (tail) {
64 		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
65 
66 		if ((addr[end] & mask) != mask)
67 			return (0);
68 	}
69 	return (1);
70 }
71 
72 static inline int
73 bitmap_empty(unsigned long *addr, const unsigned int size)
74 {
75 	const unsigned int end = BIT_WORD(size);
76 	const unsigned int tail = size & (BITS_PER_LONG - 1);
77 	unsigned int i;
78 
79 	for (i = 0; i != end; i++) {
80 		if (addr[i] != 0)
81 			return (0);
82 	}
83 
84 	if (tail) {
85 		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
86 
87 		if ((addr[end] & mask) != 0)
88 			return (0);
89 	}
90 	return (1);
91 }
92 
93 static inline void
94 bitmap_set(unsigned long *map, unsigned int start, int nr)
95 {
96 	const unsigned int size = start + nr;
97 	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
98 	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
99 
100 	map += BIT_WORD(start);
101 
102 	while (nr - bits_to_set >= 0) {
103 		*map |= mask_to_set;
104 		nr -= bits_to_set;
105 		bits_to_set = BITS_PER_LONG;
106 		mask_to_set = ~0UL;
107 		map++;
108 	}
109 
110 	if (nr) {
111 		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
112 		*map |= mask_to_set;
113 	}
114 }
115 
116 static inline void
117 bitmap_clear(unsigned long *map, unsigned int start, int nr)
118 {
119 	const unsigned int size = start + nr;
120 	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
121 	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
122 
123 	map += BIT_WORD(start);
124 
125 	while (nr - bits_to_clear >= 0) {
126 		*map &= ~mask_to_clear;
127 		nr -= bits_to_clear;
128 		bits_to_clear = BITS_PER_LONG;
129 		mask_to_clear = ~0UL;
130 		map++;
131 	}
132 
133 	if (nr) {
134 		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
135 		*map &= ~mask_to_clear;
136 	}
137 }
138 
139 static inline unsigned int
140 bitmap_find_next_zero_area_off(const unsigned long *map,
141     const unsigned int size, unsigned int start,
142     unsigned int nr, unsigned int align_mask,
143     unsigned int align_offset)
144 {
145 	unsigned int index;
146 	unsigned int end;
147 	unsigned int i;
148 
149 retry:
150 	index = find_next_zero_bit(map, size, start);
151 
152 	index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;
153 
154 	end = index + nr;
155 	if (end > size)
156 		return (end);
157 
158 	i = find_next_bit(map, end, index);
159 	if (i < end) {
160 		start = i + 1;
161 		goto retry;
162 	}
163 	return (index);
164 }
165 
166 static inline unsigned int
167 bitmap_find_next_zero_area(const unsigned long *map,
168     const unsigned int size, unsigned int start,
169     unsigned int nr, unsigned int align_mask)
170 {
171 	return (bitmap_find_next_zero_area_off(map, size,
172 	    start, nr, align_mask, 0));
173 }
174 
175 static inline int
176 bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
177 {
178 	int pos;
179 	int end;
180 
181 	for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
182 		if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
183 			continue;
184 		linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
185 		return (pos);
186 	}
187 	return (-ENOMEM);
188 }
189 
190 static inline int
191 bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
192 {
193 	if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
194 		return (-EBUSY);
195 	linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
196 	return (0);
197 }
198 
199 static inline void
200 bitmap_release_region(unsigned long *bitmap, int pos, int order)
201 {
202 	linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
203 }
204 
205 static inline unsigned int
206 bitmap_weight(unsigned long *addr, const unsigned int size)
207 {
208 	const unsigned int end = BIT_WORD(size);
209 	const unsigned int tail = size & (BITS_PER_LONG - 1);
210 	unsigned int retval = 0;
211 	unsigned int i;
212 
213 	for (i = 0; i != end; i++)
214 		retval += hweight_long(addr[i]);
215 
216 	if (tail) {
217 		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
218 
219 		retval += hweight_long(addr[end] & mask);
220 	}
221 	return (retval);
222 }
223 
224 static inline int
225 bitmap_equal(const unsigned long *pa,
226     const unsigned long *pb, unsigned size)
227 {
228 	const unsigned int end = BIT_WORD(size);
229 	const unsigned int tail = size & (BITS_PER_LONG - 1);
230 	unsigned int i;
231 
232 	for (i = 0; i != end; i++) {
233 		if (pa[i] != pb[i])
234 			return (0);
235 	}
236 
237 	if (tail) {
238 		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
239 
240 		if ((pa[end] ^ pb[end]) & mask)
241 			return (0);
242 	}
243 	return (1);
244 }
245 
246 static inline void
247 bitmap_or(unsigned long *dst, const unsigned long *src1,
248     const unsigned long *src2, const unsigned int size)
249 {
250 	const unsigned int end = BITS_TO_LONGS(size);
251 	unsigned int i;
252 
253 	for (i = 0; i != end; i++)
254 		dst[i] = src1[i] | src2[i];
255 }
256 
257 static inline void
258 bitmap_and(unsigned long *dst, const unsigned long *src1,
259     const unsigned long *src2, const unsigned int size)
260 {
261 	const unsigned int end = BITS_TO_LONGS(size);
262 	unsigned int i;
263 
264 	for (i = 0; i != end; i++)
265 		dst[i] = src1[i] & src2[i];
266 }
267 
268 static inline void
269 bitmap_xor(unsigned long *dst, const unsigned long *src1,
270     const unsigned long *src2, const unsigned int size)
271 {
272 	const unsigned int end = BITS_TO_LONGS(size);
273 	unsigned int i;
274 
275 	for (i = 0; i != end; i++)
276 		dst[i] = src1[i] ^ src2[i];
277 }
278 
279 #endif					/* _LINUX_BITMAP_H_ */
280