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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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