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 _LINUXKPI_LINUX_BITMAP_H_ 30 #define _LINUXKPI_LINUX_BITMAP_H_ 31 32 #include <linux/bitops.h> 33 #include <linux/slab.h> 34 35 static inline void 36 bitmap_zero(unsigned long *addr, const unsigned int size) 37 { 38 memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long)); 39 } 40 41 static inline void 42 bitmap_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 52 static inline int 53 bitmap_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 73 static inline int 74 bitmap_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 94 static inline void 95 bitmap_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 117 static inline void 118 bitmap_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 140 static inline unsigned int 141 bitmap_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 150 retry: 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 167 static inline unsigned int 168 bitmap_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 176 static inline int 177 bitmap_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 191 static inline int 192 bitmap_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 200 static inline void 201 bitmap_release_region(unsigned long *bitmap, int pos, int order) 202 { 203 linux_reg_op(bitmap, pos, order, REG_OP_RELEASE); 204 } 205 206 static inline unsigned int 207 bitmap_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 225 static inline int 226 bitmap_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 247 static inline int 248 bitmap_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 269 static inline void 270 bitmap_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 280 static inline void 281 bitmap_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 291 static inline void 292 bitmap_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 302 static inline void 303 bitmap_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 313 static inline void 314 bitmap_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 324 static inline void 325 bitmap_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 335 static inline unsigned long * 336 bitmap_alloc(unsigned int size, gfp_t flags) 337 { 338 return (kmalloc_array(BITS_TO_LONGS(size), 339 sizeof(unsigned long), flags)); 340 } 341 342 static inline unsigned long * 343 bitmap_zalloc(unsigned int size, gfp_t flags) 344 { 345 return (bitmap_alloc(size, flags | __GFP_ZERO)); 346 } 347 348 static inline void 349 bitmap_free(const unsigned long *bitmap) 350 { 351 kfree(bitmap); 352 } 353 354 #endif /* _LINUXKPI_LINUX_BITMAP_H_ */ 355