1a7aa8068SFrançois Tigeot /*- 2a7aa8068SFrançois Tigeot * Copyright (c) 2010 Isilon Systems, Inc. 3a7aa8068SFrançois Tigeot * Copyright (c) 2010 iX Systems, Inc. 4a7aa8068SFrançois Tigeot * Copyright (c) 2010 Panasas, Inc. 5*b44a8500SFrançois Tigeot * Copyright (c) 2015-2016 François Tigeot 6a7aa8068SFrançois Tigeot * All rights reserved. 7a7aa8068SFrançois Tigeot * 8a7aa8068SFrançois Tigeot * Redistribution and use in source and binary forms, with or without 9a7aa8068SFrançois Tigeot * modification, are permitted provided that the following conditions 10a7aa8068SFrançois Tigeot * are met: 11a7aa8068SFrançois Tigeot * 1. Redistributions of source code must retain the above copyright 12a7aa8068SFrançois Tigeot * notice unmodified, this list of conditions, and the following 13a7aa8068SFrançois Tigeot * disclaimer. 14a7aa8068SFrançois Tigeot * 2. Redistributions in binary form must reproduce the above copyright 15a7aa8068SFrançois Tigeot * notice, this list of conditions and the following disclaimer in the 16a7aa8068SFrançois Tigeot * documentation and/or other materials provided with the distribution. 17a7aa8068SFrançois Tigeot * 18a7aa8068SFrançois Tigeot * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19a7aa8068SFrançois Tigeot * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20a7aa8068SFrançois Tigeot * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21a7aa8068SFrançois Tigeot * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22a7aa8068SFrançois Tigeot * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23a7aa8068SFrançois Tigeot * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24a7aa8068SFrançois Tigeot * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25a7aa8068SFrançois Tigeot * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26a7aa8068SFrançois Tigeot * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27a7aa8068SFrançois Tigeot * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28a7aa8068SFrançois Tigeot */ 29a7aa8068SFrançois Tigeot #ifndef _LINUX_BITOPS_H_ 30a7aa8068SFrançois Tigeot #define _LINUX_BITOPS_H_ 31a7aa8068SFrançois Tigeot 32e3440f96SFrançois Tigeot #include <sys/types.h> 33e3440f96SFrançois Tigeot #include <sys/systm.h> 34e3440f96SFrançois Tigeot 35e149d068SMichael Neumann #define BIT(nr) (1UL << (nr)) 36a7aa8068SFrançois Tigeot #ifdef __LP64__ 37a7aa8068SFrançois Tigeot #define BITS_PER_LONG 64 38a7aa8068SFrançois Tigeot #else 39a7aa8068SFrançois Tigeot #define BITS_PER_LONG 32 40a7aa8068SFrançois Tigeot #endif 41a7aa8068SFrançois Tigeot #define BIT_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 42a7aa8068SFrançois Tigeot #define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 43a7aa8068SFrançois Tigeot #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 44a7aa8068SFrançois Tigeot 45a7aa8068SFrançois Tigeot static inline int 46a7aa8068SFrançois Tigeot __ffs(int mask) 47a7aa8068SFrançois Tigeot { 48a7aa8068SFrançois Tigeot return (ffs(mask) - 1); 49a7aa8068SFrançois Tigeot } 50a7aa8068SFrançois Tigeot 51a7aa8068SFrançois Tigeot static inline int 52a7aa8068SFrançois Tigeot __fls(int mask) 53a7aa8068SFrançois Tigeot { 54a7aa8068SFrançois Tigeot return (fls(mask) - 1); 55a7aa8068SFrançois Tigeot } 56a7aa8068SFrançois Tigeot 57a7aa8068SFrançois Tigeot static inline int 58a7aa8068SFrançois Tigeot __ffsl(long mask) 59a7aa8068SFrançois Tigeot { 60a7aa8068SFrançois Tigeot return (ffsl(mask) - 1); 61a7aa8068SFrançois Tigeot } 62a7aa8068SFrançois Tigeot 63a7aa8068SFrançois Tigeot static inline int 64a7aa8068SFrançois Tigeot __flsl(long mask) 65a7aa8068SFrançois Tigeot { 66a7aa8068SFrançois Tigeot return (flsl(mask) - 1); 67a7aa8068SFrançois Tigeot } 68a7aa8068SFrançois Tigeot 69a7aa8068SFrançois Tigeot 70a7aa8068SFrançois Tigeot #define ffz(mask) __ffs(~(mask)) 71a7aa8068SFrançois Tigeot 72a7aa8068SFrançois Tigeot static inline int get_count_order(unsigned int count) 73a7aa8068SFrançois Tigeot { 74a7aa8068SFrançois Tigeot int order; 75a7aa8068SFrançois Tigeot 76a7aa8068SFrançois Tigeot order = fls(count) - 1; 77a7aa8068SFrançois Tigeot if (count & (count - 1)) 78a7aa8068SFrançois Tigeot order++; 79a7aa8068SFrançois Tigeot return order; 80a7aa8068SFrançois Tigeot } 81a7aa8068SFrançois Tigeot 82a7aa8068SFrançois Tigeot static inline unsigned long 83a7aa8068SFrançois Tigeot find_first_bit(unsigned long *addr, unsigned long size) 84a7aa8068SFrançois Tigeot { 85a7aa8068SFrançois Tigeot long mask; 86a7aa8068SFrançois Tigeot int bit; 87a7aa8068SFrançois Tigeot 88a7aa8068SFrançois Tigeot for (bit = 0; size >= BITS_PER_LONG; 89a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 90a7aa8068SFrançois Tigeot if (*addr == 0) 91a7aa8068SFrançois Tigeot continue; 92a7aa8068SFrançois Tigeot return (bit + __ffsl(*addr)); 93a7aa8068SFrançois Tigeot } 94a7aa8068SFrançois Tigeot if (size) { 95a7aa8068SFrançois Tigeot mask = (*addr) & BIT_MASK(size); 96a7aa8068SFrançois Tigeot if (mask) 97a7aa8068SFrançois Tigeot bit += __ffsl(mask); 98a7aa8068SFrançois Tigeot else 99a7aa8068SFrançois Tigeot bit += size; 100a7aa8068SFrançois Tigeot } 101a7aa8068SFrançois Tigeot return (bit); 102a7aa8068SFrançois Tigeot } 103a7aa8068SFrançois Tigeot 104a7aa8068SFrançois Tigeot static inline unsigned long 105a7aa8068SFrançois Tigeot find_first_zero_bit(unsigned long *addr, unsigned long size) 106a7aa8068SFrançois Tigeot { 107a7aa8068SFrançois Tigeot long mask; 108a7aa8068SFrançois Tigeot int bit; 109a7aa8068SFrançois Tigeot 110a7aa8068SFrançois Tigeot for (bit = 0; size >= BITS_PER_LONG; 111a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 112a7aa8068SFrançois Tigeot if (~(*addr) == 0) 113a7aa8068SFrançois Tigeot continue; 114a7aa8068SFrançois Tigeot return (bit + __ffsl(~(*addr))); 115a7aa8068SFrançois Tigeot } 116a7aa8068SFrançois Tigeot if (size) { 117a7aa8068SFrançois Tigeot mask = ~(*addr) & BIT_MASK(size); 118a7aa8068SFrançois Tigeot if (mask) 119a7aa8068SFrançois Tigeot bit += __ffsl(mask); 120a7aa8068SFrançois Tigeot else 121a7aa8068SFrançois Tigeot bit += size; 122a7aa8068SFrançois Tigeot } 123a7aa8068SFrançois Tigeot return (bit); 124a7aa8068SFrançois Tigeot } 125a7aa8068SFrançois Tigeot 126a7aa8068SFrançois Tigeot static inline unsigned long 127a7aa8068SFrançois Tigeot find_last_bit(unsigned long *addr, unsigned long size) 128a7aa8068SFrançois Tigeot { 129a7aa8068SFrançois Tigeot long mask; 130a7aa8068SFrançois Tigeot int offs; 131a7aa8068SFrançois Tigeot int bit; 132a7aa8068SFrançois Tigeot int pos; 133a7aa8068SFrançois Tigeot 134a7aa8068SFrançois Tigeot pos = size / BITS_PER_LONG; 135a7aa8068SFrançois Tigeot offs = size % BITS_PER_LONG; 136a7aa8068SFrançois Tigeot bit = BITS_PER_LONG * pos; 137a7aa8068SFrançois Tigeot addr += pos; 138a7aa8068SFrançois Tigeot if (offs) { 139a7aa8068SFrançois Tigeot mask = (*addr) & BIT_MASK(offs); 140a7aa8068SFrançois Tigeot if (mask) 141a7aa8068SFrançois Tigeot return (bit + __flsl(mask)); 142a7aa8068SFrançois Tigeot } 143a7aa8068SFrançois Tigeot while (--pos) { 144a7aa8068SFrançois Tigeot addr--; 145a7aa8068SFrançois Tigeot bit -= BITS_PER_LONG; 146a7aa8068SFrançois Tigeot if (*addr) 147a7aa8068SFrançois Tigeot return (bit + __flsl(mask)); 148a7aa8068SFrançois Tigeot } 149a7aa8068SFrançois Tigeot return (size); 150a7aa8068SFrançois Tigeot } 151a7aa8068SFrançois Tigeot 152a7aa8068SFrançois Tigeot static inline unsigned long 153a7aa8068SFrançois Tigeot find_next_bit(unsigned long *addr, unsigned long size, unsigned long offset) 154a7aa8068SFrançois Tigeot { 155a7aa8068SFrançois Tigeot long mask; 156a7aa8068SFrançois Tigeot int offs; 157a7aa8068SFrançois Tigeot int bit; 158a7aa8068SFrançois Tigeot int pos; 159a7aa8068SFrançois Tigeot 160a7aa8068SFrançois Tigeot if (offset >= size) 161a7aa8068SFrançois Tigeot return (size); 162a7aa8068SFrançois Tigeot pos = offset / BITS_PER_LONG; 163a7aa8068SFrançois Tigeot offs = offset % BITS_PER_LONG; 164a7aa8068SFrançois Tigeot bit = BITS_PER_LONG * pos; 165a7aa8068SFrançois Tigeot addr += pos; 166a7aa8068SFrançois Tigeot if (offs) { 167a7aa8068SFrançois Tigeot mask = (*addr) & ~BIT_MASK(offs); 168a7aa8068SFrançois Tigeot if (mask) 169a7aa8068SFrançois Tigeot return (bit + __ffsl(mask)); 170a7aa8068SFrançois Tigeot bit += BITS_PER_LONG; 171a7aa8068SFrançois Tigeot addr++; 172a7aa8068SFrançois Tigeot } 173a7aa8068SFrançois Tigeot for (size -= bit; size >= BITS_PER_LONG; 174a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 175a7aa8068SFrançois Tigeot if (*addr == 0) 176a7aa8068SFrançois Tigeot continue; 177a7aa8068SFrançois Tigeot return (bit + __ffsl(*addr)); 178a7aa8068SFrançois Tigeot } 179a7aa8068SFrançois Tigeot if (size) { 180a7aa8068SFrançois Tigeot mask = (*addr) & BIT_MASK(size); 181a7aa8068SFrançois Tigeot if (mask) 182a7aa8068SFrançois Tigeot bit += __ffsl(mask); 183a7aa8068SFrançois Tigeot else 184a7aa8068SFrançois Tigeot bit += size; 185a7aa8068SFrançois Tigeot } 186a7aa8068SFrançois Tigeot return (bit); 187a7aa8068SFrançois Tigeot } 188a7aa8068SFrançois Tigeot 189a7aa8068SFrançois Tigeot static inline unsigned long 190a7aa8068SFrançois Tigeot find_next_zero_bit(unsigned long *addr, unsigned long size, 191a7aa8068SFrançois Tigeot unsigned long offset) 192a7aa8068SFrançois Tigeot { 193a7aa8068SFrançois Tigeot long mask; 194a7aa8068SFrançois Tigeot int offs; 195a7aa8068SFrançois Tigeot int bit; 196a7aa8068SFrançois Tigeot int pos; 197a7aa8068SFrançois Tigeot 198a7aa8068SFrançois Tigeot if (offset >= size) 199a7aa8068SFrançois Tigeot return (size); 200a7aa8068SFrançois Tigeot pos = offset / BITS_PER_LONG; 201a7aa8068SFrançois Tigeot offs = offset % BITS_PER_LONG; 202a7aa8068SFrançois Tigeot bit = BITS_PER_LONG * pos; 203a7aa8068SFrançois Tigeot addr += pos; 204a7aa8068SFrançois Tigeot if (offs) { 205a7aa8068SFrançois Tigeot mask = ~(*addr) & ~BIT_MASK(offs); 206a7aa8068SFrançois Tigeot if (mask) 207a7aa8068SFrançois Tigeot return (bit + __ffsl(mask)); 208a7aa8068SFrançois Tigeot bit += BITS_PER_LONG; 209a7aa8068SFrançois Tigeot addr++; 210a7aa8068SFrançois Tigeot } 211a7aa8068SFrançois Tigeot for (size -= bit; size >= BITS_PER_LONG; 212a7aa8068SFrançois Tigeot size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 213a7aa8068SFrançois Tigeot if (~(*addr) == 0) 214a7aa8068SFrançois Tigeot continue; 215a7aa8068SFrançois Tigeot return (bit + __ffsl(~(*addr))); 216a7aa8068SFrançois Tigeot } 217a7aa8068SFrançois Tigeot if (size) { 218a7aa8068SFrançois Tigeot mask = ~(*addr) & BIT_MASK(size); 219a7aa8068SFrançois Tigeot if (mask) 220a7aa8068SFrançois Tigeot bit += __ffsl(mask); 221a7aa8068SFrançois Tigeot else 222a7aa8068SFrançois Tigeot bit += size; 223a7aa8068SFrançois Tigeot } 224a7aa8068SFrançois Tigeot return (bit); 225a7aa8068SFrançois Tigeot } 226a7aa8068SFrançois Tigeot 227a7aa8068SFrançois Tigeot static inline void 228a7aa8068SFrançois Tigeot bitmap_zero(unsigned long *addr, int size) 229a7aa8068SFrançois Tigeot { 230a7aa8068SFrançois Tigeot int len; 231a7aa8068SFrançois Tigeot 232a7aa8068SFrançois Tigeot len = BITS_TO_LONGS(size) * sizeof(long); 233a7aa8068SFrançois Tigeot memset(addr, 0, len); 234a7aa8068SFrançois Tigeot } 235a7aa8068SFrançois Tigeot 236a7aa8068SFrançois Tigeot static inline void 237a7aa8068SFrançois Tigeot bitmap_fill(unsigned long *addr, int size) 238a7aa8068SFrançois Tigeot { 239a7aa8068SFrançois Tigeot int tail; 240a7aa8068SFrançois Tigeot int len; 241a7aa8068SFrançois Tigeot 242a7aa8068SFrançois Tigeot len = (size / BITS_PER_LONG) * sizeof(long); 243a7aa8068SFrançois Tigeot memset(addr, 0xff, len); 244a7aa8068SFrançois Tigeot tail = size & (BITS_PER_LONG - 1); 245a7aa8068SFrançois Tigeot if (tail) 246a7aa8068SFrançois Tigeot addr[size / BITS_PER_LONG] = BIT_MASK(tail); 247a7aa8068SFrançois Tigeot } 248a7aa8068SFrançois Tigeot 249a7aa8068SFrançois Tigeot static inline int 250a7aa8068SFrançois Tigeot bitmap_full(unsigned long *addr, int size) 251a7aa8068SFrançois Tigeot { 252a7aa8068SFrançois Tigeot long mask; 253a7aa8068SFrançois Tigeot int tail; 254a7aa8068SFrançois Tigeot int len; 255a7aa8068SFrançois Tigeot int i; 256a7aa8068SFrançois Tigeot 257a7aa8068SFrançois Tigeot len = size / BITS_PER_LONG; 258a7aa8068SFrançois Tigeot for (i = 0; i < len; i++) 259a7aa8068SFrançois Tigeot if (addr[i] != ~0UL) 260a7aa8068SFrançois Tigeot return (0); 261a7aa8068SFrançois Tigeot tail = size & (BITS_PER_LONG - 1); 262a7aa8068SFrançois Tigeot if (tail) { 263a7aa8068SFrançois Tigeot mask = BIT_MASK(tail); 264a7aa8068SFrançois Tigeot if ((addr[i] & mask) != mask) 265a7aa8068SFrançois Tigeot return (0); 266a7aa8068SFrançois Tigeot } 267a7aa8068SFrançois Tigeot return (1); 268a7aa8068SFrançois Tigeot } 269a7aa8068SFrançois Tigeot 270a7aa8068SFrançois Tigeot static inline int 271a7aa8068SFrançois Tigeot bitmap_empty(unsigned long *addr, int size) 272a7aa8068SFrançois Tigeot { 273a7aa8068SFrançois Tigeot long mask; 274a7aa8068SFrançois Tigeot int tail; 275a7aa8068SFrançois Tigeot int len; 276a7aa8068SFrançois Tigeot int i; 277a7aa8068SFrançois Tigeot 278a7aa8068SFrançois Tigeot len = size / BITS_PER_LONG; 279a7aa8068SFrançois Tigeot for (i = 0; i < len; i++) 280a7aa8068SFrançois Tigeot if (addr[i] != 0) 281a7aa8068SFrançois Tigeot return (0); 282a7aa8068SFrançois Tigeot tail = size & (BITS_PER_LONG - 1); 283a7aa8068SFrançois Tigeot if (tail) { 284a7aa8068SFrançois Tigeot mask = BIT_MASK(tail); 285a7aa8068SFrançois Tigeot if ((addr[i] & mask) != 0) 286a7aa8068SFrançois Tigeot return (0); 287a7aa8068SFrançois Tigeot } 288a7aa8068SFrançois Tigeot return (1); 289a7aa8068SFrançois Tigeot } 290a7aa8068SFrançois Tigeot 291a7aa8068SFrançois Tigeot #define NBLONG (NBBY * sizeof(long)) 292a7aa8068SFrançois Tigeot 293a7aa8068SFrançois Tigeot #define set_bit(i, a) \ 294a7aa8068SFrançois Tigeot atomic_set_long(&((volatile long *)(a))[(i)/NBLONG], 1 << (i) % NBLONG) 295a7aa8068SFrançois Tigeot 296a7aa8068SFrançois Tigeot #define clear_bit(i, a) \ 297a7aa8068SFrançois Tigeot atomic_clear_long(&((volatile long *)(a))[(i)/NBLONG], 1 << (i) % NBLONG) 298a7aa8068SFrançois Tigeot 299a7aa8068SFrançois Tigeot #define test_bit(i, a) \ 300a7aa8068SFrançois Tigeot !!(atomic_load_acq_long(&((volatile long *)(a))[(i)/NBLONG]) & \ 301a7aa8068SFrançois Tigeot 1 << ((i) % NBLONG)) 302a7aa8068SFrançois Tigeot 303a7aa8068SFrançois Tigeot static inline long 304a7aa8068SFrançois Tigeot test_and_clear_bit(long bit, long *var) 305a7aa8068SFrançois Tigeot { 306a7aa8068SFrançois Tigeot long val; 307a7aa8068SFrançois Tigeot 308a7aa8068SFrançois Tigeot var += bit / (sizeof(long) * NBBY); 309a7aa8068SFrançois Tigeot bit %= sizeof(long) * NBBY; 310a7aa8068SFrançois Tigeot bit = 1 << bit; 311a7aa8068SFrançois Tigeot do { 312a7aa8068SFrançois Tigeot val = *(volatile long *)var; 313a7aa8068SFrançois Tigeot } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 314a7aa8068SFrançois Tigeot 315a7aa8068SFrançois Tigeot return !!(val & bit); 316a7aa8068SFrançois Tigeot } 317a7aa8068SFrançois Tigeot 318a7aa8068SFrançois Tigeot static inline long 31981efc3b7SFrançois Tigeot test_and_set_bit(long bit, volatile unsigned long *var) 320a7aa8068SFrançois Tigeot { 321a7aa8068SFrançois Tigeot long val; 322a7aa8068SFrançois Tigeot 323a7aa8068SFrançois Tigeot var += bit / (sizeof(long) * NBBY); 324a7aa8068SFrançois Tigeot bit %= sizeof(long) * NBBY; 325a7aa8068SFrançois Tigeot bit = 1 << bit; 326a7aa8068SFrançois Tigeot do { 327a7aa8068SFrançois Tigeot val = *(volatile long *)var; 328a7aa8068SFrançois Tigeot } while (atomic_cmpset_long(var, val, val | bit) == 0); 329a7aa8068SFrançois Tigeot 330a7aa8068SFrançois Tigeot return !!(val & bit); 331a7aa8068SFrançois Tigeot } 332a7aa8068SFrançois Tigeot 333a7aa8068SFrançois Tigeot 334a7aa8068SFrançois Tigeot #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 335a7aa8068SFrançois Tigeot #define BITMAP_LAST_WORD_MASK(nbits) \ 336a7aa8068SFrançois Tigeot ( \ 337a7aa8068SFrançois Tigeot ((nbits) % BITS_PER_LONG) ? \ 338a7aa8068SFrançois Tigeot (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ 339a7aa8068SFrançois Tigeot ) 340a7aa8068SFrançois Tigeot 341a7aa8068SFrançois Tigeot 342a7aa8068SFrançois Tigeot static inline void 343a7aa8068SFrançois Tigeot bitmap_set(unsigned long *map, int start, int nr) 344a7aa8068SFrançois Tigeot { 345a7aa8068SFrançois Tigeot unsigned long *p = map + BIT_WORD(start); 346a7aa8068SFrançois Tigeot const int size = start + nr; 347a7aa8068SFrançois Tigeot int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 348a7aa8068SFrançois Tigeot unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 349a7aa8068SFrançois Tigeot 350a7aa8068SFrançois Tigeot while (nr - bits_to_set >= 0) { 351a7aa8068SFrançois Tigeot *p |= mask_to_set; 352a7aa8068SFrançois Tigeot nr -= bits_to_set; 353a7aa8068SFrançois Tigeot bits_to_set = BITS_PER_LONG; 354a7aa8068SFrançois Tigeot mask_to_set = ~0UL; 355a7aa8068SFrançois Tigeot p++; 356a7aa8068SFrançois Tigeot } 357a7aa8068SFrançois Tigeot if (nr) { 358a7aa8068SFrançois Tigeot mask_to_set &= BITMAP_LAST_WORD_MASK(size); 359a7aa8068SFrançois Tigeot *p |= mask_to_set; 360a7aa8068SFrançois Tigeot } 361a7aa8068SFrançois Tigeot } 362a7aa8068SFrançois Tigeot 363a7aa8068SFrançois Tigeot static inline void 364a7aa8068SFrançois Tigeot bitmap_clear(unsigned long *map, int start, int nr) 365a7aa8068SFrançois Tigeot { 366a7aa8068SFrançois Tigeot unsigned long *p = map + BIT_WORD(start); 367a7aa8068SFrançois Tigeot const int size = start + nr; 368a7aa8068SFrançois Tigeot int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 369a7aa8068SFrançois Tigeot unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 370a7aa8068SFrançois Tigeot 371a7aa8068SFrançois Tigeot while (nr - bits_to_clear >= 0) { 372a7aa8068SFrançois Tigeot *p &= ~mask_to_clear; 373a7aa8068SFrançois Tigeot nr -= bits_to_clear; 374a7aa8068SFrançois Tigeot bits_to_clear = BITS_PER_LONG; 375a7aa8068SFrançois Tigeot mask_to_clear = ~0UL; 376a7aa8068SFrançois Tigeot p++; 377a7aa8068SFrançois Tigeot } 378a7aa8068SFrançois Tigeot if (nr) { 379a7aa8068SFrançois Tigeot mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 380a7aa8068SFrançois Tigeot *p &= ~mask_to_clear; 381a7aa8068SFrançois Tigeot } 382a7aa8068SFrançois Tigeot } 383a7aa8068SFrançois Tigeot 384a7aa8068SFrançois Tigeot enum { 385a7aa8068SFrançois Tigeot REG_OP_ISFREE, /* true if region is all zero bits */ 386a7aa8068SFrançois Tigeot REG_OP_ALLOC, /* set all bits in region */ 387a7aa8068SFrançois Tigeot REG_OP_RELEASE, /* clear all bits in region */ 388a7aa8068SFrançois Tigeot }; 389a7aa8068SFrançois Tigeot 390a7aa8068SFrançois Tigeot static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 391a7aa8068SFrançois Tigeot { 392a7aa8068SFrançois Tigeot int nbits_reg; /* number of bits in region */ 393a7aa8068SFrançois Tigeot int index; /* index first long of region in bitmap */ 394a7aa8068SFrançois Tigeot int offset; /* bit offset region in bitmap[index] */ 395a7aa8068SFrançois Tigeot int nlongs_reg; /* num longs spanned by region in bitmap */ 396a7aa8068SFrançois Tigeot int nbitsinlong; /* num bits of region in each spanned long */ 397a7aa8068SFrançois Tigeot unsigned long mask; /* bitmask for one long of region */ 398a7aa8068SFrançois Tigeot int i; /* scans bitmap by longs */ 399a7aa8068SFrançois Tigeot int ret = 0; /* return value */ 400a7aa8068SFrançois Tigeot 401a7aa8068SFrançois Tigeot /* 402a7aa8068SFrançois Tigeot * Either nlongs_reg == 1 (for small orders that fit in one long) 403a7aa8068SFrançois Tigeot * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) 404a7aa8068SFrançois Tigeot */ 405a7aa8068SFrançois Tigeot nbits_reg = 1 << order; 406a7aa8068SFrançois Tigeot index = pos / BITS_PER_LONG; 407a7aa8068SFrançois Tigeot offset = pos - (index * BITS_PER_LONG); 408a7aa8068SFrançois Tigeot nlongs_reg = BITS_TO_LONGS(nbits_reg); 409a7aa8068SFrançois Tigeot nbitsinlong = min(nbits_reg, BITS_PER_LONG); 410a7aa8068SFrançois Tigeot 411a7aa8068SFrançois Tigeot /* 412a7aa8068SFrançois Tigeot * Can't do "mask = (1UL << nbitsinlong) - 1", as that 413a7aa8068SFrançois Tigeot * overflows if nbitsinlong == BITS_PER_LONG. 414a7aa8068SFrançois Tigeot */ 415a7aa8068SFrançois Tigeot mask = (1UL << (nbitsinlong - 1)); 416a7aa8068SFrançois Tigeot mask += mask - 1; 417a7aa8068SFrançois Tigeot mask <<= offset; 418a7aa8068SFrançois Tigeot 419a7aa8068SFrançois Tigeot switch (reg_op) { 420a7aa8068SFrançois Tigeot case REG_OP_ISFREE: 421a7aa8068SFrançois Tigeot for (i = 0; i < nlongs_reg; i++) { 422a7aa8068SFrançois Tigeot if (bitmap[index + i] & mask) 423a7aa8068SFrançois Tigeot goto done; 424a7aa8068SFrançois Tigeot } 425a7aa8068SFrançois Tigeot ret = 1; /* all bits in region free (zero) */ 426a7aa8068SFrançois Tigeot break; 427a7aa8068SFrançois Tigeot 428a7aa8068SFrançois Tigeot case REG_OP_ALLOC: 429a7aa8068SFrançois Tigeot for (i = 0; i < nlongs_reg; i++) 430a7aa8068SFrançois Tigeot bitmap[index + i] |= mask; 431a7aa8068SFrançois Tigeot break; 432a7aa8068SFrançois Tigeot 433a7aa8068SFrançois Tigeot case REG_OP_RELEASE: 434a7aa8068SFrançois Tigeot for (i = 0; i < nlongs_reg; i++) 435a7aa8068SFrançois Tigeot bitmap[index + i] &= ~mask; 436a7aa8068SFrançois Tigeot break; 437a7aa8068SFrançois Tigeot } 438a7aa8068SFrançois Tigeot done: 439a7aa8068SFrançois Tigeot return ret; 440a7aa8068SFrançois Tigeot } 441a7aa8068SFrançois Tigeot 442a7aa8068SFrançois Tigeot /** 443a7aa8068SFrançois Tigeot * bitmap_find_free_region - find a contiguous aligned mem region 444a7aa8068SFrançois Tigeot * @bitmap: array of unsigned longs corresponding to the bitmap 445a7aa8068SFrançois Tigeot * @bits: number of bits in the bitmap 446a7aa8068SFrançois Tigeot * @order: region size (log base 2 of number of bits) to find 447a7aa8068SFrançois Tigeot * 448a7aa8068SFrançois Tigeot * Find a region of free (zero) bits in a @bitmap of @bits bits and 449a7aa8068SFrançois Tigeot * allocate them (set them to one). Only consider regions of length 450a7aa8068SFrançois Tigeot * a power (@order) of two, aligned to that power of two, which 451a7aa8068SFrançois Tigeot * makes the search algorithm much faster. 452a7aa8068SFrançois Tigeot * 453a7aa8068SFrançois Tigeot * Return the bit offset in bitmap of the allocated region, 454a7aa8068SFrançois Tigeot * or -errno on failure. 455a7aa8068SFrançois Tigeot */ 456a7aa8068SFrançois Tigeot static inline int 457a7aa8068SFrançois Tigeot bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 458a7aa8068SFrançois Tigeot { 459a7aa8068SFrançois Tigeot int pos, end; /* scans bitmap by regions of size order */ 460a7aa8068SFrançois Tigeot 461a7aa8068SFrançois Tigeot for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 462a7aa8068SFrançois Tigeot if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 463a7aa8068SFrançois Tigeot continue; 464a7aa8068SFrançois Tigeot __reg_op(bitmap, pos, order, REG_OP_ALLOC); 465a7aa8068SFrançois Tigeot return pos; 466a7aa8068SFrançois Tigeot } 467a7aa8068SFrançois Tigeot return -ENOMEM; 468a7aa8068SFrançois Tigeot } 469a7aa8068SFrançois Tigeot 470a7aa8068SFrançois Tigeot /** 471a7aa8068SFrançois Tigeot * bitmap_release_region - release allocated bitmap region 472a7aa8068SFrançois Tigeot * @bitmap: array of unsigned longs corresponding to the bitmap 473a7aa8068SFrançois Tigeot * @pos: beginning of bit region to release 474a7aa8068SFrançois Tigeot * @order: region size (log base 2 of number of bits) to release 475a7aa8068SFrançois Tigeot * 476a7aa8068SFrançois Tigeot * This is the complement to __bitmap_find_free_region() and releases 477a7aa8068SFrançois Tigeot * the found region (by clearing it in the bitmap). 478a7aa8068SFrançois Tigeot * 479a7aa8068SFrançois Tigeot * No return value. 480a7aa8068SFrançois Tigeot */ 481a7aa8068SFrançois Tigeot static inline void 482a7aa8068SFrançois Tigeot bitmap_release_region(unsigned long *bitmap, int pos, int order) 483a7aa8068SFrançois Tigeot { 484a7aa8068SFrançois Tigeot __reg_op(bitmap, pos, order, REG_OP_RELEASE); 485a7aa8068SFrançois Tigeot } 486a7aa8068SFrançois Tigeot 487f57dc5d0SFrançois Tigeot /* Returns a contiguous bitmask from bits h to l */ 488f57dc5d0SFrançois Tigeot #define GENMASK(h, l) \ 4899d5e6bc5SMatthew Dillon ((~0UL) >> (BITS_PER_LONG - h - 1)) & ((~0UL) << l) 490f57dc5d0SFrançois Tigeot 491e3440f96SFrançois Tigeot #include <asm/bitops/non-atomic.h> 4923ee3144dSFrançois Tigeot #include <asm/bitops/const_hweight.h> 493a7aa8068SFrançois Tigeot 494*b44a8500SFrançois Tigeot #define for_each_set_bit(bit, addr, size) \ 495*b44a8500SFrançois Tigeot for ((bit) = find_first_bit((addr), (size)); \ 496*b44a8500SFrançois Tigeot (bit) < (size); \ 497*b44a8500SFrançois Tigeot (bit) = find_next_bit((addr), (size), (bit) + 1)) 498*b44a8500SFrançois Tigeot 499a7aa8068SFrançois Tigeot #endif /* _LINUX_BITOPS_H_ */ 500