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
bitmap_zero(unsigned long * addr,const unsigned int size)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
bitmap_fill(unsigned long * addr,const unsigned int size)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
bitmap_full(unsigned long * addr,const unsigned int size)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
bitmap_empty(unsigned long * addr,const unsigned int size)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
bitmap_set(unsigned long * map,unsigned int start,int nr)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
bitmap_clear(unsigned long * map,unsigned int start,int nr)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
bitmap_find_next_zero_area_off(const unsigned long * map,const unsigned int size,unsigned int start,unsigned int nr,unsigned int align_mask,unsigned int align_offset)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
bitmap_find_next_zero_area(const unsigned long * map,const unsigned int size,unsigned int start,unsigned int nr,unsigned int align_mask)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
bitmap_find_free_region(unsigned long * bitmap,int bits,int order)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
bitmap_allocate_region(unsigned long * bitmap,int pos,int order)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
bitmap_release_region(unsigned long * bitmap,int pos,int order)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
bitmap_weight(unsigned long * addr,const unsigned int size)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
bitmap_equal(const unsigned long * pa,const unsigned long * pb,unsigned size)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
bitmap_subset(const unsigned long * pa,const unsigned long * pb,unsigned size)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
bitmap_complement(unsigned long * dst,const unsigned long * src,const unsigned int size)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
bitmap_copy(unsigned long * dst,const unsigned long * src,const unsigned int size)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
bitmap_or(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)290 bitmap_or(unsigned long *dst, const unsigned long *src1,
291 const unsigned long *src2, const unsigned int size)
292 {
293 const unsigned int end = BITS_TO_LONGS(size);
294 unsigned int i;
295
296 for (i = 0; i != end; i++)
297 dst[i] = src1[i] | src2[i];
298 }
299
300 static inline void
bitmap_and(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)301 bitmap_and(unsigned long *dst, const unsigned long *src1,
302 const unsigned long *src2, const unsigned int size)
303 {
304 const unsigned int end = BITS_TO_LONGS(size);
305 unsigned int i;
306
307 for (i = 0; i != end; i++)
308 dst[i] = src1[i] & src2[i];
309 }
310
311 static inline void
bitmap_andnot(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)312 bitmap_andnot(unsigned long *dst, const unsigned long *src1,
313 const unsigned long *src2, const unsigned int size)
314 {
315 const unsigned int end = BITS_TO_LONGS(size);
316 unsigned int i;
317
318 for (i = 0; i != end; i++)
319 dst[i] = src1[i] & ~src2[i];
320 }
321
322 static inline void
bitmap_xor(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)323 bitmap_xor(unsigned long *dst, const unsigned long *src1,
324 const unsigned long *src2, const unsigned int size)
325 {
326 const unsigned int end = BITS_TO_LONGS(size);
327 unsigned int i;
328
329 for (i = 0; i != end; i++)
330 dst[i] = src1[i] ^ src2[i];
331 }
332
333 static inline unsigned long *
bitmap_alloc(unsigned int size,gfp_t flags)334 bitmap_alloc(unsigned int size, gfp_t flags)
335 {
336 return (kmalloc_array(BITS_TO_LONGS(size),
337 sizeof(unsigned long), flags));
338 }
339
340 static inline unsigned long *
bitmap_zalloc(unsigned int size,gfp_t flags)341 bitmap_zalloc(unsigned int size, gfp_t flags)
342 {
343 return (bitmap_alloc(size, flags | __GFP_ZERO));
344 }
345
346 static inline void
bitmap_free(const unsigned long * bitmap)347 bitmap_free(const unsigned long *bitmap)
348 {
349 kfree(bitmap);
350 }
351
352 #endif /* _LINUXKPI_LINUX_BITMAP_H_ */
353