bitops.h revision 290335
1219820Sjeff/*- 2219820Sjeff * Copyright (c) 2010 Isilon Systems, Inc. 3219820Sjeff * Copyright (c) 2010 iX Systems, Inc. 4219820Sjeff * Copyright (c) 2010 Panasas, Inc. 5289621Shselasky * Copyright (c) 2013-2015 Mellanox Technologies, Ltd. 6219820Sjeff * All rights reserved. 7219820Sjeff * 8219820Sjeff * Redistribution and use in source and binary forms, with or without 9219820Sjeff * modification, are permitted provided that the following conditions 10219820Sjeff * are met: 11219820Sjeff * 1. Redistributions of source code must retain the above copyright 12219820Sjeff * notice unmodified, this list of conditions, and the following 13219820Sjeff * disclaimer. 14219820Sjeff * 2. Redistributions in binary form must reproduce the above copyright 15219820Sjeff * notice, this list of conditions and the following disclaimer in the 16219820Sjeff * documentation and/or other materials provided with the distribution. 17219820Sjeff * 18219820Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19219820Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20219820Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21219820Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22219820Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23219820Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24219820Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25219820Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26219820Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27219820Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28289644Shselasky * 29289644Shselasky * $FreeBSD: head/sys/compat/linuxkpi/common/include/linux/bitops.h 290335 2015-11-03 12:37:55Z hselasky $ 30219820Sjeff */ 31219820Sjeff#ifndef _LINUX_BITOPS_H_ 32219820Sjeff#define _LINUX_BITOPS_H_ 33219820Sjeff 34289621Shselasky#include <sys/types.h> 35289621Shselasky#include <sys/systm.h> 36290335Shselasky#include <sys/errno.h> 37289621Shselasky 38289621Shselasky#define BIT(nr) (1UL << (nr)) 39219820Sjeff#ifdef __LP64__ 40219820Sjeff#define BITS_PER_LONG 64 41219820Sjeff#else 42219820Sjeff#define BITS_PER_LONG 32 43219820Sjeff#endif 44289621Shselasky#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 45289621Shselasky#define BITMAP_LAST_WORD_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 46219820Sjeff#define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 47289621Shselasky#define BIT_MASK(nr) (1UL << ((nr) & (BITS_PER_LONG - 1))) 48255932Salfred#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 49289621Shselasky#define GENMASK(lo, hi) (((2UL << ((hi) - (lo))) - 1UL) << (lo)) 50270710Shselasky#define BITS_PER_BYTE 8 51270710Shselasky 52219820Sjeffstatic inline int 53219820Sjeff__ffs(int mask) 54219820Sjeff{ 55219820Sjeff return (ffs(mask) - 1); 56219820Sjeff} 57219820Sjeff 58219820Sjeffstatic inline int 59219820Sjeff__fls(int mask) 60219820Sjeff{ 61219820Sjeff return (fls(mask) - 1); 62219820Sjeff} 63219820Sjeff 64219820Sjeffstatic inline int 65219820Sjeff__ffsl(long mask) 66219820Sjeff{ 67219820Sjeff return (ffsl(mask) - 1); 68219820Sjeff} 69219820Sjeff 70219820Sjeffstatic inline int 71219820Sjeff__flsl(long mask) 72219820Sjeff{ 73219820Sjeff return (flsl(mask) - 1); 74219820Sjeff} 75219820Sjeff 76219820Sjeff 77219820Sjeff#define ffz(mask) __ffs(~(mask)) 78219820Sjeff 79255932Salfredstatic inline int get_count_order(unsigned int count) 80255932Salfred{ 81255932Salfred int order; 82255932Salfred 83255932Salfred order = fls(count) - 1; 84255932Salfred if (count & (count - 1)) 85255932Salfred order++; 86255932Salfred return order; 87255932Salfred} 88255932Salfred 89219820Sjeffstatic inline unsigned long 90219820Sjefffind_first_bit(unsigned long *addr, unsigned long size) 91219820Sjeff{ 92219820Sjeff long mask; 93219820Sjeff int bit; 94219820Sjeff 95219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 96219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 97219820Sjeff if (*addr == 0) 98219820Sjeff continue; 99219820Sjeff return (bit + __ffsl(*addr)); 100219820Sjeff } 101219820Sjeff if (size) { 102289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 103219820Sjeff if (mask) 104219820Sjeff bit += __ffsl(mask); 105219820Sjeff else 106219820Sjeff bit += size; 107219820Sjeff } 108219820Sjeff return (bit); 109219820Sjeff} 110219820Sjeff 111219820Sjeffstatic inline unsigned long 112219820Sjefffind_first_zero_bit(unsigned long *addr, unsigned long size) 113219820Sjeff{ 114219820Sjeff long mask; 115219820Sjeff int bit; 116219820Sjeff 117219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 118219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 119219820Sjeff if (~(*addr) == 0) 120219820Sjeff continue; 121219820Sjeff return (bit + __ffsl(~(*addr))); 122219820Sjeff } 123219820Sjeff if (size) { 124289621Shselasky mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 125219820Sjeff if (mask) 126219820Sjeff bit += __ffsl(mask); 127219820Sjeff else 128219820Sjeff bit += size; 129219820Sjeff } 130219820Sjeff return (bit); 131219820Sjeff} 132219820Sjeff 133219820Sjeffstatic inline unsigned long 134219820Sjefffind_last_bit(unsigned long *addr, unsigned long size) 135219820Sjeff{ 136219820Sjeff long mask; 137219820Sjeff int offs; 138219820Sjeff int bit; 139219820Sjeff int pos; 140219820Sjeff 141219820Sjeff pos = size / BITS_PER_LONG; 142219820Sjeff offs = size % BITS_PER_LONG; 143219820Sjeff bit = BITS_PER_LONG * pos; 144219820Sjeff addr += pos; 145219820Sjeff if (offs) { 146289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(offs); 147219820Sjeff if (mask) 148219820Sjeff return (bit + __flsl(mask)); 149219820Sjeff } 150219820Sjeff while (--pos) { 151219820Sjeff addr--; 152219820Sjeff bit -= BITS_PER_LONG; 153219820Sjeff if (*addr) 154219820Sjeff return (bit + __flsl(mask)); 155219820Sjeff } 156219820Sjeff return (size); 157219820Sjeff} 158219820Sjeff 159219820Sjeffstatic inline unsigned long 160219820Sjefffind_next_bit(unsigned long *addr, unsigned long size, unsigned long offset) 161219820Sjeff{ 162219820Sjeff long mask; 163219820Sjeff int offs; 164219820Sjeff int bit; 165219820Sjeff int pos; 166219820Sjeff 167219820Sjeff if (offset >= size) 168219820Sjeff return (size); 169219820Sjeff pos = offset / BITS_PER_LONG; 170219820Sjeff offs = offset % BITS_PER_LONG; 171219820Sjeff bit = BITS_PER_LONG * pos; 172219820Sjeff addr += pos; 173219820Sjeff if (offs) { 174289621Shselasky mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs); 175219820Sjeff if (mask) 176219820Sjeff return (bit + __ffsl(mask)); 177282741Smarkj if (size - bit <= BITS_PER_LONG) 178282741Smarkj return (size); 179219820Sjeff bit += BITS_PER_LONG; 180219820Sjeff addr++; 181219820Sjeff } 182219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 183219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 184219820Sjeff if (*addr == 0) 185219820Sjeff continue; 186219820Sjeff return (bit + __ffsl(*addr)); 187219820Sjeff } 188219820Sjeff if (size) { 189289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 190219820Sjeff if (mask) 191219820Sjeff bit += __ffsl(mask); 192219820Sjeff else 193219820Sjeff bit += size; 194219820Sjeff } 195219820Sjeff return (bit); 196219820Sjeff} 197219820Sjeff 198219820Sjeffstatic inline unsigned long 199219820Sjefffind_next_zero_bit(unsigned long *addr, unsigned long size, 200219820Sjeff unsigned long offset) 201219820Sjeff{ 202219820Sjeff long mask; 203219820Sjeff int offs; 204219820Sjeff int bit; 205219820Sjeff int pos; 206219820Sjeff 207219820Sjeff if (offset >= size) 208219820Sjeff return (size); 209219820Sjeff pos = offset / BITS_PER_LONG; 210219820Sjeff offs = offset % BITS_PER_LONG; 211219820Sjeff bit = BITS_PER_LONG * pos; 212219820Sjeff addr += pos; 213219820Sjeff if (offs) { 214289621Shselasky mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs); 215219820Sjeff if (mask) 216219820Sjeff return (bit + __ffsl(mask)); 217282741Smarkj if (size - bit <= BITS_PER_LONG) 218282741Smarkj return (size); 219219820Sjeff bit += BITS_PER_LONG; 220219820Sjeff addr++; 221219820Sjeff } 222219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 223219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 224219820Sjeff if (~(*addr) == 0) 225219820Sjeff continue; 226219820Sjeff return (bit + __ffsl(~(*addr))); 227219820Sjeff } 228219820Sjeff if (size) { 229289621Shselasky mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 230219820Sjeff if (mask) 231219820Sjeff bit += __ffsl(mask); 232219820Sjeff else 233219820Sjeff bit += size; 234219820Sjeff } 235219820Sjeff return (bit); 236219820Sjeff} 237219820Sjeff 238219820Sjeffstatic inline void 239219820Sjeffbitmap_zero(unsigned long *addr, int size) 240219820Sjeff{ 241219820Sjeff int len; 242219820Sjeff 243219820Sjeff len = BITS_TO_LONGS(size) * sizeof(long); 244219820Sjeff memset(addr, 0, len); 245219820Sjeff} 246219820Sjeff 247219820Sjeffstatic inline void 248219820Sjeffbitmap_fill(unsigned long *addr, int size) 249219820Sjeff{ 250219820Sjeff int tail; 251219820Sjeff int len; 252219820Sjeff 253219820Sjeff len = (size / BITS_PER_LONG) * sizeof(long); 254219820Sjeff memset(addr, 0xff, len); 255219820Sjeff tail = size & (BITS_PER_LONG - 1); 256219820Sjeff if (tail) 257289621Shselasky addr[size / BITS_PER_LONG] = BITMAP_LAST_WORD_MASK(tail); 258219820Sjeff} 259219820Sjeff 260219820Sjeffstatic inline int 261219820Sjeffbitmap_full(unsigned long *addr, int size) 262219820Sjeff{ 263289621Shselasky unsigned long mask; 264219820Sjeff int tail; 265219820Sjeff int len; 266219820Sjeff int i; 267219820Sjeff 268219820Sjeff len = size / BITS_PER_LONG; 269219820Sjeff for (i = 0; i < len; i++) 270219820Sjeff if (addr[i] != ~0UL) 271219820Sjeff return (0); 272219820Sjeff tail = size & (BITS_PER_LONG - 1); 273219820Sjeff if (tail) { 274289621Shselasky mask = BITMAP_LAST_WORD_MASK(tail); 275219820Sjeff if ((addr[i] & mask) != mask) 276219820Sjeff return (0); 277219820Sjeff } 278219820Sjeff return (1); 279219820Sjeff} 280219820Sjeff 281219820Sjeffstatic inline int 282219820Sjeffbitmap_empty(unsigned long *addr, int size) 283219820Sjeff{ 284289621Shselasky unsigned long mask; 285219820Sjeff int tail; 286219820Sjeff int len; 287219820Sjeff int i; 288219820Sjeff 289219820Sjeff len = size / BITS_PER_LONG; 290219820Sjeff for (i = 0; i < len; i++) 291219820Sjeff if (addr[i] != 0) 292219820Sjeff return (0); 293219820Sjeff tail = size & (BITS_PER_LONG - 1); 294219820Sjeff if (tail) { 295289621Shselasky mask = BITMAP_LAST_WORD_MASK(tail); 296219820Sjeff if ((addr[i] & mask) != 0) 297219820Sjeff return (0); 298219820Sjeff } 299219820Sjeff return (1); 300219820Sjeff} 301219820Sjeff 302277396Shselasky#define __set_bit(i, a) \ 303289621Shselasky atomic_set_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 304277396Shselasky 305219820Sjeff#define set_bit(i, a) \ 306289621Shselasky atomic_set_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 307219820Sjeff 308277396Shselasky#define __clear_bit(i, a) \ 309289621Shselasky atomic_clear_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 310277396Shselasky 311219820Sjeff#define clear_bit(i, a) \ 312289621Shselasky atomic_clear_long(&((volatile long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 313219820Sjeff 314219820Sjeff#define test_bit(i, a) \ 315289621Shselasky !!(atomic_load_acq_long(&((volatile long *)(a))[BIT_WORD(i)]) & \ 316289621Shselasky BIT_MASK(i)) 317219820Sjeff 318219820Sjeffstatic inline long 319219820Sjefftest_and_clear_bit(long bit, long *var) 320219820Sjeff{ 321219820Sjeff long val; 322219820Sjeff 323289621Shselasky var += BIT_WORD(bit); 324289621Shselasky bit %= BITS_PER_LONG; 325267395Shselasky bit = (1UL << bit); 326219820Sjeff do { 327219820Sjeff val = *(volatile long *)var; 328219820Sjeff } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 329219820Sjeff 330219820Sjeff return !!(val & bit); 331219820Sjeff} 332219820Sjeff 333219820Sjeffstatic inline long 334219820Sjefftest_and_set_bit(long bit, long *var) 335219820Sjeff{ 336219820Sjeff long val; 337219820Sjeff 338289621Shselasky var += BIT_WORD(bit); 339289621Shselasky bit %= BITS_PER_LONG; 340267395Shselasky bit = (1UL << bit); 341219820Sjeff do { 342219820Sjeff val = *(volatile long *)var; 343219820Sjeff } while (atomic_cmpset_long(var, val, val | bit) == 0); 344219820Sjeff 345219820Sjeff return !!(val & bit); 346219820Sjeff} 347219820Sjeff 348255932Salfredstatic inline void 349255932Salfredbitmap_set(unsigned long *map, int start, int nr) 350255932Salfred{ 351255932Salfred unsigned long *p = map + BIT_WORD(start); 352255932Salfred const int size = start + nr; 353255932Salfred int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 354255932Salfred unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 355255932Salfred 356255932Salfred while (nr - bits_to_set >= 0) { 357255932Salfred *p |= mask_to_set; 358255932Salfred nr -= bits_to_set; 359255932Salfred bits_to_set = BITS_PER_LONG; 360255932Salfred mask_to_set = ~0UL; 361255932Salfred p++; 362255932Salfred } 363255932Salfred if (nr) { 364255932Salfred mask_to_set &= BITMAP_LAST_WORD_MASK(size); 365255932Salfred *p |= mask_to_set; 366255932Salfred } 367255932Salfred} 368255932Salfred 369255932Salfredstatic inline void 370255932Salfredbitmap_clear(unsigned long *map, int start, int nr) 371255932Salfred{ 372255932Salfred unsigned long *p = map + BIT_WORD(start); 373255932Salfred const int size = start + nr; 374255932Salfred int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 375255932Salfred unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 376255932Salfred 377255932Salfred while (nr - bits_to_clear >= 0) { 378255932Salfred *p &= ~mask_to_clear; 379255932Salfred nr -= bits_to_clear; 380255932Salfred bits_to_clear = BITS_PER_LONG; 381255932Salfred mask_to_clear = ~0UL; 382255932Salfred p++; 383255932Salfred } 384255932Salfred if (nr) { 385255932Salfred mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 386255932Salfred *p &= ~mask_to_clear; 387255932Salfred } 388255932Salfred} 389255932Salfred 390255932Salfredenum { 391289621Shselasky REG_OP_ISFREE, 392289621Shselasky REG_OP_ALLOC, 393289621Shselasky REG_OP_RELEASE, 394255932Salfred}; 395255932Salfred 396255932Salfredstatic int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 397255932Salfred{ 398289621Shselasky int nbits_reg; 399289621Shselasky int index; 400289621Shselasky int offset; 401289621Shselasky int nlongs_reg; 402289621Shselasky int nbitsinlong; 403289621Shselasky unsigned long mask; 404289621Shselasky int i; 405289621Shselasky int ret = 0; 406255932Salfred 407255932Salfred nbits_reg = 1 << order; 408255932Salfred index = pos / BITS_PER_LONG; 409255932Salfred offset = pos - (index * BITS_PER_LONG); 410255932Salfred nlongs_reg = BITS_TO_LONGS(nbits_reg); 411255932Salfred nbitsinlong = min(nbits_reg, BITS_PER_LONG); 412255932Salfred 413255932Salfred mask = (1UL << (nbitsinlong - 1)); 414255932Salfred mask += mask - 1; 415255932Salfred mask <<= offset; 416255932Salfred 417255932Salfred switch (reg_op) { 418255932Salfred case REG_OP_ISFREE: 419255932Salfred for (i = 0; i < nlongs_reg; i++) { 420255932Salfred if (bitmap[index + i] & mask) 421255932Salfred goto done; 422255932Salfred } 423289621Shselasky ret = 1; 424255932Salfred break; 425255932Salfred 426255932Salfred case REG_OP_ALLOC: 427255932Salfred for (i = 0; i < nlongs_reg; i++) 428255932Salfred bitmap[index + i] |= mask; 429255932Salfred break; 430255932Salfred 431255932Salfred case REG_OP_RELEASE: 432255932Salfred for (i = 0; i < nlongs_reg; i++) 433255932Salfred bitmap[index + i] &= ~mask; 434255932Salfred break; 435255932Salfred } 436255932Salfreddone: 437255932Salfred return ret; 438255932Salfred} 439255932Salfred 440255932Salfredstatic inline int 441255932Salfredbitmap_find_free_region(unsigned long *bitmap, int bits, int order) 442255932Salfred{ 443289621Shselasky int pos; 444289621Shselasky int end; 445255932Salfred 446255932Salfred for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 447255932Salfred if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 448255932Salfred continue; 449255932Salfred __reg_op(bitmap, pos, order, REG_OP_ALLOC); 450255932Salfred return pos; 451255932Salfred } 452255932Salfred return -ENOMEM; 453255932Salfred} 454255932Salfred 455270710Shselaskystatic inline int 456270710Shselaskybitmap_allocate_region(unsigned long *bitmap, int pos, int order) 457270710Shselasky{ 458270710Shselasky if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 459270710Shselasky return -EBUSY; 460270710Shselasky __reg_op(bitmap, pos, order, REG_OP_ALLOC); 461270710Shselasky return 0; 462270710Shselasky} 463270710Shselasky 464255932Salfredstatic inline void 465255932Salfredbitmap_release_region(unsigned long *bitmap, int pos, int order) 466255932Salfred{ 467255932Salfred __reg_op(bitmap, pos, order, REG_OP_RELEASE); 468255932Salfred} 469255932Salfred 470255932Salfred 471270710Shselasky#define for_each_set_bit(bit, addr, size) \ 472270710Shselasky for ((bit) = find_first_bit((addr), (size)); \ 473270710Shselasky (bit) < (size); \ 474270710Shselasky (bit) = find_next_bit((addr), (size), (bit) + 1)) 475270710Shselasky 476219820Sjeff#endif /* _LINUX_BITOPS_H_ */ 477