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 bool 268 bitmap_intersects(const unsigned long *pa, const unsigned long *pb, 269 unsigned size) 270 { 271 const unsigned end = BIT_WORD(size); 272 const unsigned tail = size & (BITS_PER_LONG - 1); 273 unsigned i; 274 275 for (i = 0; i != end; i++) 276 if (pa[i] & pb[i]) 277 return (true); 278 279 if (tail) { 280 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 281 282 if (pa[end] & pb[end] & mask) 283 return (true); 284 } 285 return (false); 286 } 287 288 static inline void 289 bitmap_complement(unsigned long *dst, const unsigned long *src, 290 const unsigned int size) 291 { 292 const unsigned int end = BITS_TO_LONGS(size); 293 unsigned int i; 294 295 for (i = 0; i != end; i++) 296 dst[i] = ~src[i]; 297 } 298 299 static inline void 300 bitmap_copy(unsigned long *dst, const unsigned long *src, 301 const unsigned int size) 302 { 303 const unsigned int end = BITS_TO_LONGS(size); 304 unsigned int i; 305 306 for (i = 0; i != end; i++) 307 dst[i] = src[i]; 308 } 309 310 static inline void 311 bitmap_to_arr32(uint32_t *dst, const unsigned long *src, unsigned int size) 312 { 313 const unsigned int end = howmany(size, 32); 314 315 #ifdef __LP64__ 316 unsigned int i = 0; 317 while (i < end) { 318 dst[i++] = (uint32_t)(*src & UINT_MAX); 319 if (i < end) 320 dst[i++] = (uint32_t)(*src >> 32); 321 src++; 322 } 323 #else 324 bitmap_copy((unsigned long *)dst, src, size); 325 #endif 326 if ((size % 32) != 0) /* Linux uses BITS_PER_LONG. Seems to be a bug */ 327 dst[end - 1] &= (uint32_t)(UINT_MAX >> (32 - (size % 32))); 328 } 329 330 static inline void 331 bitmap_from_arr32(unsigned long *dst, const uint32_t *src, 332 unsigned int size) 333 { 334 const unsigned int end = BIT_WORD(size); 335 const unsigned int tail = size & (BITS_PER_LONG - 1); 336 337 #ifdef __LP64__ 338 const unsigned int end32 = howmany(size, 32); 339 unsigned int i = 0; 340 341 while (i < end32) { 342 dst[i++/2] = (unsigned long) *(src++); 343 if (i < end32) 344 dst[i++/2] |= ((unsigned long) *(src++)) << 32; 345 } 346 #else 347 bitmap_copy(dst, (const unsigned long *)src, size); 348 #endif 349 if ((size % BITS_PER_LONG) != 0) 350 dst[end] &= BITMAP_LAST_WORD_MASK(tail); 351 } 352 353 static inline void 354 bitmap_or(unsigned long *dst, const unsigned long *src1, 355 const unsigned long *src2, const unsigned int size) 356 { 357 const unsigned int end = BITS_TO_LONGS(size); 358 unsigned int i; 359 360 for (i = 0; i != end; i++) 361 dst[i] = src1[i] | src2[i]; 362 } 363 364 static inline void 365 bitmap_and(unsigned long *dst, const unsigned long *src1, 366 const unsigned long *src2, const unsigned int size) 367 { 368 const unsigned int end = BITS_TO_LONGS(size); 369 unsigned int i; 370 371 for (i = 0; i != end; i++) 372 dst[i] = src1[i] & src2[i]; 373 } 374 375 static inline void 376 bitmap_andnot(unsigned long *dst, const unsigned long *src1, 377 const unsigned long *src2, const unsigned int size) 378 { 379 const unsigned int end = BITS_TO_LONGS(size); 380 unsigned int i; 381 382 for (i = 0; i != end; i++) 383 dst[i] = src1[i] & ~src2[i]; 384 } 385 386 static inline void 387 bitmap_xor(unsigned long *dst, const unsigned long *src1, 388 const unsigned long *src2, const unsigned int size) 389 { 390 const unsigned int end = BITS_TO_LONGS(size); 391 unsigned int i; 392 393 for (i = 0; i != end; i++) 394 dst[i] = src1[i] ^ src2[i]; 395 } 396 397 static inline void 398 bitmap_shift_right(unsigned long *dst, const unsigned long *src, 399 unsigned int shift, unsigned int size) 400 { 401 const unsigned int end = BITS_TO_LONGS(size); 402 const unsigned int tail = size & (BITS_PER_LONG - 1); 403 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 404 const unsigned int off = BIT_WORD(shift); 405 const unsigned int rem = shift & (BITS_PER_LONG - 1); 406 unsigned long left, right; 407 unsigned int i, srcpos; 408 409 for (i = 0, srcpos = off; srcpos < end; i++, srcpos++) { 410 right = src[srcpos]; 411 left = 0; 412 413 if (srcpos == end - 1) 414 right &= mask; 415 416 if (rem != 0) { 417 right >>= rem; 418 if (srcpos + 1 < end) { 419 left = src[srcpos + 1]; 420 if (srcpos + 1 == end - 1) 421 left &= mask; 422 left <<= (BITS_PER_LONG - rem); 423 } 424 } 425 dst[i] = left | right; 426 } 427 if (off != 0) 428 memset(dst + end - off, 0, off * sizeof(unsigned long)); 429 } 430 431 static inline unsigned long * 432 bitmap_alloc(unsigned int size, gfp_t flags) 433 { 434 return (kmalloc_array(BITS_TO_LONGS(size), 435 sizeof(unsigned long), flags)); 436 } 437 438 static inline unsigned long * 439 bitmap_zalloc(unsigned int size, gfp_t flags) 440 { 441 return (bitmap_alloc(size, flags | __GFP_ZERO)); 442 } 443 444 static inline void 445 bitmap_free(const unsigned long *bitmap) 446 { 447 kfree(bitmap); 448 } 449 450 #endif /* _LINUXKPI_LINUX_BITMAP_H_ */ 451