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: releng/11.0/sys/compat/linuxkpi/common/include/linux/bitops.h 300506 2016-05-23 13:18:15Z 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) 49300490Shselasky#define GENMASK(h, l) (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l))) 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 76300503Shselaskystatic inline uint32_t 77300503Shselaskyror32(uint32_t word, unsigned int shift) 78300503Shselasky{ 79219820Sjeff 80300503Shselasky return ((word >> shift) | (word << (32 - shift))); 81300503Shselasky} 82300503Shselasky 83219820Sjeff#define ffz(mask) __ffs(~(mask)) 84219820Sjeff 85255932Salfredstatic inline int get_count_order(unsigned int count) 86255932Salfred{ 87255932Salfred int order; 88255932Salfred 89255932Salfred order = fls(count) - 1; 90255932Salfred if (count & (count - 1)) 91255932Salfred order++; 92255932Salfred return order; 93255932Salfred} 94255932Salfred 95219820Sjeffstatic inline unsigned long 96300506Shselaskyfind_first_bit(const unsigned long *addr, unsigned long size) 97219820Sjeff{ 98219820Sjeff long mask; 99219820Sjeff int bit; 100219820Sjeff 101219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 102219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 103219820Sjeff if (*addr == 0) 104219820Sjeff continue; 105219820Sjeff return (bit + __ffsl(*addr)); 106219820Sjeff } 107219820Sjeff if (size) { 108289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 109219820Sjeff if (mask) 110219820Sjeff bit += __ffsl(mask); 111219820Sjeff else 112219820Sjeff bit += size; 113219820Sjeff } 114219820Sjeff return (bit); 115219820Sjeff} 116219820Sjeff 117219820Sjeffstatic inline unsigned long 118300506Shselaskyfind_first_zero_bit(const unsigned long *addr, unsigned long size) 119219820Sjeff{ 120219820Sjeff long mask; 121219820Sjeff int bit; 122219820Sjeff 123219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 124219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 125219820Sjeff if (~(*addr) == 0) 126219820Sjeff continue; 127219820Sjeff return (bit + __ffsl(~(*addr))); 128219820Sjeff } 129219820Sjeff if (size) { 130289621Shselasky mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 131219820Sjeff if (mask) 132219820Sjeff bit += __ffsl(mask); 133219820Sjeff else 134219820Sjeff bit += size; 135219820Sjeff } 136219820Sjeff return (bit); 137219820Sjeff} 138219820Sjeff 139219820Sjeffstatic inline unsigned long 140300506Shselaskyfind_last_bit(const unsigned long *addr, unsigned long size) 141219820Sjeff{ 142219820Sjeff long mask; 143219820Sjeff int offs; 144219820Sjeff int bit; 145219820Sjeff int pos; 146219820Sjeff 147219820Sjeff pos = size / BITS_PER_LONG; 148219820Sjeff offs = size % BITS_PER_LONG; 149219820Sjeff bit = BITS_PER_LONG * pos; 150219820Sjeff addr += pos; 151219820Sjeff if (offs) { 152289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(offs); 153219820Sjeff if (mask) 154219820Sjeff return (bit + __flsl(mask)); 155219820Sjeff } 156297444Shselasky while (pos--) { 157219820Sjeff addr--; 158219820Sjeff bit -= BITS_PER_LONG; 159219820Sjeff if (*addr) 160297444Shselasky return (bit + __flsl(*addr)); 161219820Sjeff } 162219820Sjeff return (size); 163219820Sjeff} 164219820Sjeff 165219820Sjeffstatic inline unsigned long 166300506Shselaskyfind_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 167219820Sjeff{ 168219820Sjeff long mask; 169219820Sjeff int offs; 170219820Sjeff int bit; 171219820Sjeff int pos; 172219820Sjeff 173219820Sjeff if (offset >= size) 174219820Sjeff return (size); 175219820Sjeff pos = offset / BITS_PER_LONG; 176219820Sjeff offs = offset % BITS_PER_LONG; 177219820Sjeff bit = BITS_PER_LONG * pos; 178219820Sjeff addr += pos; 179219820Sjeff if (offs) { 180289621Shselasky mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs); 181219820Sjeff if (mask) 182219820Sjeff return (bit + __ffsl(mask)); 183282741Smarkj if (size - bit <= BITS_PER_LONG) 184282741Smarkj return (size); 185219820Sjeff bit += BITS_PER_LONG; 186219820Sjeff addr++; 187219820Sjeff } 188219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 189219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 190219820Sjeff if (*addr == 0) 191219820Sjeff continue; 192219820Sjeff return (bit + __ffsl(*addr)); 193219820Sjeff } 194219820Sjeff if (size) { 195289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 196219820Sjeff if (mask) 197219820Sjeff bit += __ffsl(mask); 198219820Sjeff else 199219820Sjeff bit += size; 200219820Sjeff } 201219820Sjeff return (bit); 202219820Sjeff} 203219820Sjeff 204219820Sjeffstatic inline unsigned long 205300506Shselaskyfind_next_zero_bit(const unsigned long *addr, unsigned long size, 206219820Sjeff unsigned long offset) 207219820Sjeff{ 208219820Sjeff long mask; 209219820Sjeff int offs; 210219820Sjeff int bit; 211219820Sjeff int pos; 212219820Sjeff 213219820Sjeff if (offset >= size) 214219820Sjeff return (size); 215219820Sjeff pos = offset / BITS_PER_LONG; 216219820Sjeff offs = offset % BITS_PER_LONG; 217219820Sjeff bit = BITS_PER_LONG * pos; 218219820Sjeff addr += pos; 219219820Sjeff if (offs) { 220289621Shselasky mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs); 221219820Sjeff if (mask) 222219820Sjeff return (bit + __ffsl(mask)); 223282741Smarkj if (size - bit <= BITS_PER_LONG) 224282741Smarkj return (size); 225219820Sjeff bit += BITS_PER_LONG; 226219820Sjeff addr++; 227219820Sjeff } 228219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 229219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 230219820Sjeff if (~(*addr) == 0) 231219820Sjeff continue; 232219820Sjeff return (bit + __ffsl(~(*addr))); 233219820Sjeff } 234219820Sjeff if (size) { 235289621Shselasky mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 236219820Sjeff if (mask) 237219820Sjeff bit += __ffsl(mask); 238219820Sjeff else 239219820Sjeff bit += size; 240219820Sjeff } 241219820Sjeff return (bit); 242219820Sjeff} 243219820Sjeff 244219820Sjeffstatic inline void 245219820Sjeffbitmap_zero(unsigned long *addr, int size) 246219820Sjeff{ 247219820Sjeff int len; 248219820Sjeff 249219820Sjeff len = BITS_TO_LONGS(size) * sizeof(long); 250219820Sjeff memset(addr, 0, len); 251219820Sjeff} 252219820Sjeff 253219820Sjeffstatic inline void 254219820Sjeffbitmap_fill(unsigned long *addr, int size) 255219820Sjeff{ 256219820Sjeff int tail; 257219820Sjeff int len; 258219820Sjeff 259219820Sjeff len = (size / BITS_PER_LONG) * sizeof(long); 260219820Sjeff memset(addr, 0xff, len); 261219820Sjeff tail = size & (BITS_PER_LONG - 1); 262219820Sjeff if (tail) 263289621Shselasky addr[size / BITS_PER_LONG] = BITMAP_LAST_WORD_MASK(tail); 264219820Sjeff} 265219820Sjeff 266219820Sjeffstatic inline int 267219820Sjeffbitmap_full(unsigned long *addr, int size) 268219820Sjeff{ 269289621Shselasky unsigned long mask; 270219820Sjeff int tail; 271219820Sjeff int len; 272219820Sjeff int i; 273219820Sjeff 274219820Sjeff len = size / BITS_PER_LONG; 275219820Sjeff for (i = 0; i < len; i++) 276219820Sjeff if (addr[i] != ~0UL) 277219820Sjeff return (0); 278219820Sjeff tail = size & (BITS_PER_LONG - 1); 279219820Sjeff if (tail) { 280289621Shselasky mask = BITMAP_LAST_WORD_MASK(tail); 281219820Sjeff if ((addr[i] & mask) != mask) 282219820Sjeff return (0); 283219820Sjeff } 284219820Sjeff return (1); 285219820Sjeff} 286219820Sjeff 287219820Sjeffstatic inline int 288219820Sjeffbitmap_empty(unsigned long *addr, int size) 289219820Sjeff{ 290289621Shselasky unsigned long mask; 291219820Sjeff int tail; 292219820Sjeff int len; 293219820Sjeff int i; 294219820Sjeff 295219820Sjeff len = size / BITS_PER_LONG; 296219820Sjeff for (i = 0; i < len; i++) 297219820Sjeff if (addr[i] != 0) 298219820Sjeff return (0); 299219820Sjeff tail = size & (BITS_PER_LONG - 1); 300219820Sjeff if (tail) { 301289621Shselasky mask = BITMAP_LAST_WORD_MASK(tail); 302219820Sjeff if ((addr[i] & mask) != 0) 303219820Sjeff return (0); 304219820Sjeff } 305219820Sjeff return (1); 306219820Sjeff} 307219820Sjeff 308277396Shselasky#define __set_bit(i, a) \ 309300506Shselasky atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 310277396Shselasky 311219820Sjeff#define set_bit(i, a) \ 312300506Shselasky atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 313219820Sjeff 314277396Shselasky#define __clear_bit(i, a) \ 315300506Shselasky atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 316277396Shselasky 317219820Sjeff#define clear_bit(i, a) \ 318300506Shselasky atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 319219820Sjeff 320219820Sjeff#define test_bit(i, a) \ 321300506Shselasky !!(atomic_load_acq_long(&((volatile unsigned long *)(a))[BIT_WORD(i)]) & \ 322289621Shselasky BIT_MASK(i)) 323219820Sjeff 324300506Shselaskystatic inline int 325300506Shselaskytest_and_clear_bit(long bit, volatile unsigned long *var) 326219820Sjeff{ 327219820Sjeff long val; 328219820Sjeff 329289621Shselasky var += BIT_WORD(bit); 330289621Shselasky bit %= BITS_PER_LONG; 331267395Shselasky bit = (1UL << bit); 332219820Sjeff do { 333300506Shselasky val = *var; 334219820Sjeff } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 335219820Sjeff 336219820Sjeff return !!(val & bit); 337219820Sjeff} 338219820Sjeff 339300506Shselaskystatic inline int 340300506Shselaskytest_and_set_bit(long bit, volatile unsigned long *var) 341219820Sjeff{ 342219820Sjeff long val; 343219820Sjeff 344289621Shselasky var += BIT_WORD(bit); 345289621Shselasky bit %= BITS_PER_LONG; 346267395Shselasky bit = (1UL << bit); 347219820Sjeff do { 348300506Shselasky val = *var; 349219820Sjeff } while (atomic_cmpset_long(var, val, val | bit) == 0); 350219820Sjeff 351219820Sjeff return !!(val & bit); 352219820Sjeff} 353219820Sjeff 354255932Salfredstatic inline void 355255932Salfredbitmap_set(unsigned long *map, int start, int nr) 356255932Salfred{ 357255932Salfred unsigned long *p = map + BIT_WORD(start); 358255932Salfred const int size = start + nr; 359255932Salfred int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 360255932Salfred unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 361255932Salfred 362255932Salfred while (nr - bits_to_set >= 0) { 363255932Salfred *p |= mask_to_set; 364255932Salfred nr -= bits_to_set; 365255932Salfred bits_to_set = BITS_PER_LONG; 366255932Salfred mask_to_set = ~0UL; 367255932Salfred p++; 368255932Salfred } 369255932Salfred if (nr) { 370255932Salfred mask_to_set &= BITMAP_LAST_WORD_MASK(size); 371255932Salfred *p |= mask_to_set; 372255932Salfred } 373255932Salfred} 374255932Salfred 375255932Salfredstatic inline void 376255932Salfredbitmap_clear(unsigned long *map, int start, int nr) 377255932Salfred{ 378255932Salfred unsigned long *p = map + BIT_WORD(start); 379255932Salfred const int size = start + nr; 380255932Salfred int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 381255932Salfred unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 382255932Salfred 383255932Salfred while (nr - bits_to_clear >= 0) { 384255932Salfred *p &= ~mask_to_clear; 385255932Salfred nr -= bits_to_clear; 386255932Salfred bits_to_clear = BITS_PER_LONG; 387255932Salfred mask_to_clear = ~0UL; 388255932Salfred p++; 389255932Salfred } 390255932Salfred if (nr) { 391255932Salfred mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 392255932Salfred *p &= ~mask_to_clear; 393255932Salfred } 394255932Salfred} 395255932Salfred 396255932Salfredenum { 397289621Shselasky REG_OP_ISFREE, 398289621Shselasky REG_OP_ALLOC, 399289621Shselasky REG_OP_RELEASE, 400255932Salfred}; 401255932Salfred 402300506Shselaskystatic inline int 403300506Shselasky__reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 404255932Salfred{ 405289621Shselasky int nbits_reg; 406289621Shselasky int index; 407289621Shselasky int offset; 408289621Shselasky int nlongs_reg; 409289621Shselasky int nbitsinlong; 410289621Shselasky unsigned long mask; 411289621Shselasky int i; 412289621Shselasky int ret = 0; 413255932Salfred 414255932Salfred nbits_reg = 1 << order; 415255932Salfred index = pos / BITS_PER_LONG; 416255932Salfred offset = pos - (index * BITS_PER_LONG); 417255932Salfred nlongs_reg = BITS_TO_LONGS(nbits_reg); 418255932Salfred nbitsinlong = min(nbits_reg, BITS_PER_LONG); 419255932Salfred 420255932Salfred mask = (1UL << (nbitsinlong - 1)); 421255932Salfred mask += mask - 1; 422255932Salfred mask <<= offset; 423255932Salfred 424255932Salfred switch (reg_op) { 425255932Salfred case REG_OP_ISFREE: 426255932Salfred for (i = 0; i < nlongs_reg; i++) { 427255932Salfred if (bitmap[index + i] & mask) 428255932Salfred goto done; 429255932Salfred } 430289621Shselasky ret = 1; 431255932Salfred break; 432255932Salfred 433255932Salfred case REG_OP_ALLOC: 434255932Salfred for (i = 0; i < nlongs_reg; i++) 435255932Salfred bitmap[index + i] |= mask; 436255932Salfred break; 437255932Salfred 438255932Salfred case REG_OP_RELEASE: 439255932Salfred for (i = 0; i < nlongs_reg; i++) 440255932Salfred bitmap[index + i] &= ~mask; 441255932Salfred break; 442255932Salfred } 443255932Salfreddone: 444255932Salfred return ret; 445255932Salfred} 446255932Salfred 447255932Salfredstatic inline int 448255932Salfredbitmap_find_free_region(unsigned long *bitmap, int bits, int order) 449255932Salfred{ 450289621Shselasky int pos; 451289621Shselasky int end; 452255932Salfred 453255932Salfred for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 454255932Salfred if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 455255932Salfred continue; 456255932Salfred __reg_op(bitmap, pos, order, REG_OP_ALLOC); 457255932Salfred return pos; 458255932Salfred } 459255932Salfred return -ENOMEM; 460255932Salfred} 461255932Salfred 462270710Shselaskystatic inline int 463270710Shselaskybitmap_allocate_region(unsigned long *bitmap, int pos, int order) 464270710Shselasky{ 465270710Shselasky if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 466270710Shselasky return -EBUSY; 467270710Shselasky __reg_op(bitmap, pos, order, REG_OP_ALLOC); 468270710Shselasky return 0; 469270710Shselasky} 470270710Shselasky 471255932Salfredstatic inline void 472255932Salfredbitmap_release_region(unsigned long *bitmap, int pos, int order) 473255932Salfred{ 474255932Salfred __reg_op(bitmap, pos, order, REG_OP_RELEASE); 475255932Salfred} 476255932Salfred 477270710Shselasky#define for_each_set_bit(bit, addr, size) \ 478270710Shselasky for ((bit) = find_first_bit((addr), (size)); \ 479270710Shselasky (bit) < (size); \ 480270710Shselasky (bit) = find_next_bit((addr), (size), (bit) + 1)) 481270710Shselasky 482294829Shselaskystatic inline unsigned 483294829Shselaskybitmap_weight(unsigned long *bitmap, unsigned nbits) 484294829Shselasky{ 485294829Shselasky unsigned bit; 486294829Shselasky unsigned retval = 0; 487294829Shselasky 488294829Shselasky for_each_set_bit(bit, bitmap, nbits) 489294829Shselasky retval++; 490294829Shselasky return (retval); 491294829Shselasky} 492294829Shselasky 493294829Shselaskystatic inline int 494294829Shselaskybitmap_equal(const unsigned long *pa, 495294829Shselasky const unsigned long *pb, unsigned bits) 496294829Shselasky{ 497294829Shselasky unsigned x; 498294829Shselasky unsigned y = bits / BITS_PER_LONG; 499294829Shselasky 500294829Shselasky for (x = 0; x != y; x++) { 501294829Shselasky if (pa[x] != pb[x]) 502294829Shselasky return (0); 503294829Shselasky } 504294829Shselasky 505294829Shselasky y = bits % BITS_PER_LONG; 506294829Shselasky if (y != 0) { 507294829Shselasky if ((pa[x] ^ pb[x]) & BITMAP_LAST_WORD_MASK(y)) 508294829Shselasky return (0); 509294829Shselasky } 510294829Shselasky return (1); 511294829Shselasky} 512294829Shselasky 513219820Sjeff#endif /* _LINUX_BITOPS_H_ */ 514