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#include <linux/slab.h> 34 35static inline void 36bitmap_zero(unsigned long *addr, const unsigned int size) 37{ 38 memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long)); 39} 40 41static inline void 42bitmap_fill(unsigned long *addr, const unsigned int size) 43{ 44 const unsigned int tail = size & (BITS_PER_LONG - 1); 45 46 memset(addr, 0xff, BIT_WORD(size) * sizeof(long)); 47 48 if (tail) 49 addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail); 50} 51 52static inline int 53bitmap_full(unsigned long *addr, const unsigned int size) 54{ 55 const unsigned int end = BIT_WORD(size); 56 const unsigned int tail = size & (BITS_PER_LONG - 1); 57 unsigned int i; 58 59 for (i = 0; i != end; i++) { 60 if (addr[i] != ~0UL) 61 return (0); 62 } 63 64 if (tail) { 65 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 66 67 if ((addr[end] & mask) != mask) 68 return (0); 69 } 70 return (1); 71} 72 73static inline int 74bitmap_empty(unsigned long *addr, const unsigned int size) 75{ 76 const unsigned int end = BIT_WORD(size); 77 const unsigned int tail = size & (BITS_PER_LONG - 1); 78 unsigned int i; 79 80 for (i = 0; i != end; i++) { 81 if (addr[i] != 0) 82 return (0); 83 } 84 85 if (tail) { 86 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 87 88 if ((addr[end] & mask) != 0) 89 return (0); 90 } 91 return (1); 92} 93 94static inline void 95bitmap_set(unsigned long *map, unsigned int start, int nr) 96{ 97 const unsigned int size = start + nr; 98 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 99 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 100 101 map += BIT_WORD(start); 102 103 while (nr - bits_to_set >= 0) { 104 *map |= mask_to_set; 105 nr -= bits_to_set; 106 bits_to_set = BITS_PER_LONG; 107 mask_to_set = ~0UL; 108 map++; 109 } 110 111 if (nr) { 112 mask_to_set &= BITMAP_LAST_WORD_MASK(size); 113 *map |= mask_to_set; 114 } 115} 116 117static inline void 118bitmap_clear(unsigned long *map, unsigned int start, int nr) 119{ 120 const unsigned int size = start + nr; 121 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 122 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 123 124 map += BIT_WORD(start); 125 126 while (nr - bits_to_clear >= 0) { 127 *map &= ~mask_to_clear; 128 nr -= bits_to_clear; 129 bits_to_clear = BITS_PER_LONG; 130 mask_to_clear = ~0UL; 131 map++; 132 } 133 134 if (nr) { 135 mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 136 *map &= ~mask_to_clear; 137 } 138} 139 140static inline unsigned int 141bitmap_find_next_zero_area_off(const unsigned long *map, 142 const unsigned int size, unsigned int start, 143 unsigned int nr, unsigned int align_mask, 144 unsigned int align_offset) 145{ 146 unsigned int index; 147 unsigned int end; 148 unsigned int i; 149 150retry: 151 index = find_next_zero_bit(map, size, start); 152 153 index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset; 154 155 end = index + nr; 156 if (end > size) 157 return (end); 158 159 i = find_next_bit(map, end, index); 160 if (i < end) { 161 start = i + 1; 162 goto retry; 163 } 164 return (index); 165} 166 167static inline unsigned int 168bitmap_find_next_zero_area(const unsigned long *map, 169 const unsigned int size, unsigned int start, 170 unsigned int nr, unsigned int align_mask) 171{ 172 return (bitmap_find_next_zero_area_off(map, size, 173 start, nr, align_mask, 0)); 174} 175 176static inline int 177bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 178{ 179 int pos; 180 int end; 181 182 for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) { 183 if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE)) 184 continue; 185 linux_reg_op(bitmap, pos, order, REG_OP_ALLOC); 186 return (pos); 187 } 188 return (-ENOMEM); 189} 190 191static inline int 192bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 193{ 194 if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE)) 195 return (-EBUSY); 196 linux_reg_op(bitmap, pos, order, REG_OP_ALLOC); 197 return (0); 198} 199 200static inline void 201bitmap_release_region(unsigned long *bitmap, int pos, int order) 202{ 203 linux_reg_op(bitmap, pos, order, REG_OP_RELEASE); 204} 205 206static inline unsigned int 207bitmap_weight(unsigned long *addr, const unsigned int size) 208{ 209 const unsigned int end = BIT_WORD(size); 210 const unsigned int tail = size & (BITS_PER_LONG - 1); 211 unsigned int retval = 0; 212 unsigned int i; 213 214 for (i = 0; i != end; i++) 215 retval += hweight_long(addr[i]); 216 217 if (tail) { 218 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 219 220 retval += hweight_long(addr[end] & mask); 221 } 222 return (retval); 223} 224 225static inline int 226bitmap_equal(const unsigned long *pa, 227 const unsigned long *pb, unsigned size) 228{ 229 const unsigned int end = BIT_WORD(size); 230 const unsigned int tail = size & (BITS_PER_LONG - 1); 231 unsigned int i; 232 233 for (i = 0; i != end; i++) { 234 if (pa[i] != pb[i]) 235 return (0); 236 } 237 238 if (tail) { 239 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 240 241 if ((pa[end] ^ pb[end]) & mask) 242 return (0); 243 } 244 return (1); 245} 246 247static inline int 248bitmap_subset(const unsigned long *pa, 249 const unsigned long *pb, unsigned size) 250{ 251 const unsigned end = BIT_WORD(size); 252 const unsigned tail = size & (BITS_PER_LONG - 1); 253 unsigned i; 254 255 for (i = 0; i != end; i++) { 256 if (pa[i] & ~pb[i]) 257 return (0); 258 } 259 260 if (tail) { 261 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail); 262 263 if (pa[end] & ~pb[end] & mask) 264 return (0); 265 } 266 return (1); 267} 268 269static inline void 270bitmap_complement(unsigned long *dst, const unsigned long *src, 271 const unsigned int size) 272{ 273 const unsigned int end = BITS_TO_LONGS(size); 274 unsigned int i; 275 276 for (i = 0; i != end; i++) 277 dst[i] = ~src[i]; 278} 279 280static inline void 281bitmap_copy(unsigned long *dst, const unsigned long *src, 282 const unsigned int size) 283{ 284 const unsigned int end = BITS_TO_LONGS(size); 285 unsigned int i; 286 287 for (i = 0; i != end; i++) 288 dst[i] = src[i]; 289} 290 291static inline void 292bitmap_or(unsigned long *dst, const unsigned long *src1, 293 const unsigned long *src2, const unsigned int size) 294{ 295 const unsigned int end = BITS_TO_LONGS(size); 296 unsigned int i; 297 298 for (i = 0; i != end; i++) 299 dst[i] = src1[i] | src2[i]; 300} 301 302static inline void 303bitmap_and(unsigned long *dst, const unsigned long *src1, 304 const unsigned long *src2, const unsigned int size) 305{ 306 const unsigned int end = BITS_TO_LONGS(size); 307 unsigned int i; 308 309 for (i = 0; i != end; i++) 310 dst[i] = src1[i] & src2[i]; 311} 312 313static inline void 314bitmap_andnot(unsigned long *dst, const unsigned long *src1, 315 const unsigned long *src2, const unsigned int size) 316{ 317 const unsigned int end = BITS_TO_LONGS(size); 318 unsigned int i; 319 320 for (i = 0; i != end; i++) 321 dst[i] = src1[i] & ~src2[i]; 322} 323 324static inline void 325bitmap_xor(unsigned long *dst, const unsigned long *src1, 326 const unsigned long *src2, const unsigned int size) 327{ 328 const unsigned int end = BITS_TO_LONGS(size); 329 unsigned int i; 330 331 for (i = 0; i != end; i++) 332 dst[i] = src1[i] ^ src2[i]; 333} 334 335static inline unsigned long * 336bitmap_alloc(unsigned int size, gfp_t flags) 337{ 338 return (kmalloc_array(BITS_TO_LONGS(size), 339 sizeof(unsigned long), flags)); 340} 341 342static inline unsigned long * 343bitmap_zalloc(unsigned int size, gfp_t flags) 344{ 345 return (bitmap_alloc(size, flags | __GFP_ZERO)); 346} 347 348static inline void 349bitmap_free(const unsigned long *bitmap) 350{ 351 kfree(bitmap); 352} 353 354#endif /* _LINUX_BITMAP_H_ */ 355