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
bitmap_zero(unsigned long * addr,const unsigned int size)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
bitmap_fill(unsigned long * addr,const unsigned int size)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
bitmap_full(unsigned long * addr,const unsigned int size)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
bitmap_empty(unsigned long * addr,const unsigned int size)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
bitmap_set(unsigned long * map,unsigned int start,int nr)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
bitmap_clear(unsigned long * map,unsigned int start,int nr)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
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)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
bitmap_find_next_zero_area(const unsigned long * map,const unsigned int size,unsigned int start,unsigned int nr,unsigned int align_mask)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
bitmap_find_free_region(unsigned long * bitmap,int bits,int order)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
bitmap_allocate_region(unsigned long * bitmap,int pos,int order)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
bitmap_release_region(unsigned long * bitmap,int pos,int order)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
bitmap_weight(unsigned long * addr,const unsigned int size)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
bitmap_equal(const unsigned long * pa,const unsigned long * pb,unsigned size)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
bitmap_complement(unsigned long * dst,const unsigned long * src,const unsigned int size)247 bitmap_complement(unsigned long *dst, const unsigned long *src,
248 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] = ~src[i];
255 }
256
257 static inline void
bitmap_or(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)258 bitmap_or(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
bitmap_and(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)269 bitmap_and(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 static inline void
bitmap_xor(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,const unsigned int size)280 bitmap_xor(unsigned long *dst, const unsigned long *src1,
281 const unsigned long *src2, const unsigned int size)
282 {
283 const unsigned int end = BITS_TO_LONGS(size);
284 unsigned int i;
285
286 for (i = 0; i != end; i++)
287 dst[i] = src1[i] ^ src2[i];
288 }
289
290 #endif /* _LINUX_BITMAP_H_ */
291