1219820Sjeff/*- 2219820Sjeff * Copyright (c) 2010 Isilon Systems, Inc. 3219820Sjeff * Copyright (c) 2010 iX Systems, Inc. 4219820Sjeff * Copyright (c) 2010 Panasas, Inc. 5328653Shselasky * Copyright (c) 2013-2017 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: stable/11/sys/compat/linuxkpi/common/include/linux/bitops.h 368828 2020-12-30 01:11:14Z hselasky $ 30219820Sjeff */ 31219820Sjeff#ifndef _LINUX_BITOPS_H_ 32219820Sjeff#define _LINUX_BITOPS_H_ 33219820Sjeff 34328653Shselasky#include <sys/param.h> 35289621Shselasky#include <sys/types.h> 36289621Shselasky#include <sys/systm.h> 37290335Shselasky#include <sys/errno.h> 38328653Shselasky#include <sys/libkern.h> 39289621Shselasky 40289621Shselasky#define BIT(nr) (1UL << (nr)) 41328653Shselasky#define BIT_ULL(nr) (1ULL << (nr)) 42219820Sjeff#ifdef __LP64__ 43219820Sjeff#define BITS_PER_LONG 64 44219820Sjeff#else 45219820Sjeff#define BITS_PER_LONG 32 46219820Sjeff#endif 47328653Shselasky 48330854Shselasky#define BITS_PER_LONG_LONG 64 49330854Shselasky 50289621Shselasky#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 51289621Shselasky#define BITMAP_LAST_WORD_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 52219820Sjeff#define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 53289621Shselasky#define BIT_MASK(nr) (1UL << ((nr) & (BITS_PER_LONG - 1))) 54345914Shselasky#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 55300490Shselasky#define GENMASK(h, l) (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l))) 56330854Shselasky#define GENMASK_ULL(h, l) (((~0ULL) >> (BITS_PER_LONG_LONG - (h) - 1)) & ((~0ULL) << (l))) 57345914Shselasky#define BITS_PER_BYTE 8 58345914Shselasky#define BITS_PER_TYPE(t) (sizeof(t) * BITS_PER_BYTE) 59270710Shselasky 60328653Shselasky#define hweight8(x) bitcount((uint8_t)(x)) 61328653Shselasky#define hweight16(x) bitcount16(x) 62328653Shselasky#define hweight32(x) bitcount32(x) 63328653Shselasky#define hweight64(x) bitcount64(x) 64328653Shselasky#define hweight_long(x) bitcountl(x) 65328653Shselasky 66219820Sjeffstatic inline int 67219820Sjeff__ffs(int mask) 68219820Sjeff{ 69219820Sjeff return (ffs(mask) - 1); 70219820Sjeff} 71219820Sjeff 72219820Sjeffstatic inline int 73219820Sjeff__fls(int mask) 74219820Sjeff{ 75219820Sjeff return (fls(mask) - 1); 76219820Sjeff} 77219820Sjeff 78219820Sjeffstatic inline int 79219820Sjeff__ffsl(long mask) 80219820Sjeff{ 81219820Sjeff return (ffsl(mask) - 1); 82219820Sjeff} 83219820Sjeff 84219820Sjeffstatic inline int 85219820Sjeff__flsl(long mask) 86219820Sjeff{ 87219820Sjeff return (flsl(mask) - 1); 88219820Sjeff} 89219820Sjeff 90328653Shselaskystatic inline int 91328653Shselaskyfls64(uint64_t mask) 92328653Shselasky{ 93328653Shselasky return (flsll(mask)); 94328653Shselasky} 95328653Shselasky 96300503Shselaskystatic inline uint32_t 97300503Shselaskyror32(uint32_t word, unsigned int shift) 98300503Shselasky{ 99300503Shselasky return ((word >> shift) | (word << (32 - shift))); 100300503Shselasky} 101300503Shselasky 102219820Sjeff#define ffz(mask) __ffs(~(mask)) 103219820Sjeff 104255932Salfredstatic inline int get_count_order(unsigned int count) 105255932Salfred{ 106255932Salfred int order; 107255932Salfred 108255932Salfred order = fls(count) - 1; 109255932Salfred if (count & (count - 1)) 110255932Salfred order++; 111255932Salfred return order; 112255932Salfred} 113255932Salfred 114219820Sjeffstatic inline unsigned long 115300506Shselaskyfind_first_bit(const unsigned long *addr, unsigned long size) 116219820Sjeff{ 117219820Sjeff long mask; 118219820Sjeff int bit; 119219820Sjeff 120219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 121219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 122219820Sjeff if (*addr == 0) 123219820Sjeff continue; 124219820Sjeff return (bit + __ffsl(*addr)); 125219820Sjeff } 126219820Sjeff if (size) { 127289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 128219820Sjeff if (mask) 129219820Sjeff bit += __ffsl(mask); 130219820Sjeff else 131219820Sjeff bit += size; 132219820Sjeff } 133219820Sjeff return (bit); 134219820Sjeff} 135219820Sjeff 136219820Sjeffstatic inline unsigned long 137300506Shselaskyfind_first_zero_bit(const unsigned long *addr, unsigned long size) 138219820Sjeff{ 139219820Sjeff long mask; 140219820Sjeff int bit; 141219820Sjeff 142219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 143219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 144219820Sjeff if (~(*addr) == 0) 145219820Sjeff continue; 146219820Sjeff return (bit + __ffsl(~(*addr))); 147219820Sjeff } 148219820Sjeff if (size) { 149289621Shselasky mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 150219820Sjeff if (mask) 151219820Sjeff bit += __ffsl(mask); 152219820Sjeff else 153219820Sjeff bit += size; 154219820Sjeff } 155219820Sjeff return (bit); 156219820Sjeff} 157219820Sjeff 158219820Sjeffstatic inline unsigned long 159300506Shselaskyfind_last_bit(const unsigned long *addr, unsigned long size) 160219820Sjeff{ 161219820Sjeff long mask; 162219820Sjeff int offs; 163219820Sjeff int bit; 164219820Sjeff int pos; 165219820Sjeff 166219820Sjeff pos = size / BITS_PER_LONG; 167219820Sjeff offs = size % BITS_PER_LONG; 168219820Sjeff bit = BITS_PER_LONG * pos; 169219820Sjeff addr += pos; 170219820Sjeff if (offs) { 171289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(offs); 172219820Sjeff if (mask) 173219820Sjeff return (bit + __flsl(mask)); 174219820Sjeff } 175297444Shselasky while (pos--) { 176219820Sjeff addr--; 177219820Sjeff bit -= BITS_PER_LONG; 178219820Sjeff if (*addr) 179297444Shselasky return (bit + __flsl(*addr)); 180219820Sjeff } 181219820Sjeff return (size); 182219820Sjeff} 183219820Sjeff 184219820Sjeffstatic inline unsigned long 185300506Shselaskyfind_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 186219820Sjeff{ 187219820Sjeff long mask; 188219820Sjeff int offs; 189219820Sjeff int bit; 190219820Sjeff int pos; 191219820Sjeff 192219820Sjeff if (offset >= size) 193219820Sjeff return (size); 194219820Sjeff pos = offset / BITS_PER_LONG; 195219820Sjeff offs = offset % BITS_PER_LONG; 196219820Sjeff bit = BITS_PER_LONG * pos; 197219820Sjeff addr += pos; 198219820Sjeff if (offs) { 199289621Shselasky mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs); 200219820Sjeff if (mask) 201219820Sjeff return (bit + __ffsl(mask)); 202282741Smarkj if (size - bit <= BITS_PER_LONG) 203282741Smarkj return (size); 204219820Sjeff bit += BITS_PER_LONG; 205219820Sjeff addr++; 206219820Sjeff } 207219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 208219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 209219820Sjeff if (*addr == 0) 210219820Sjeff continue; 211219820Sjeff return (bit + __ffsl(*addr)); 212219820Sjeff } 213219820Sjeff if (size) { 214289621Shselasky mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 215219820Sjeff if (mask) 216219820Sjeff bit += __ffsl(mask); 217219820Sjeff else 218219820Sjeff bit += size; 219219820Sjeff } 220219820Sjeff return (bit); 221219820Sjeff} 222219820Sjeff 223219820Sjeffstatic inline unsigned long 224300506Shselaskyfind_next_zero_bit(const unsigned long *addr, unsigned long size, 225219820Sjeff unsigned long offset) 226219820Sjeff{ 227219820Sjeff long mask; 228219820Sjeff int offs; 229219820Sjeff int bit; 230219820Sjeff int pos; 231219820Sjeff 232219820Sjeff if (offset >= size) 233219820Sjeff return (size); 234219820Sjeff pos = offset / BITS_PER_LONG; 235219820Sjeff offs = offset % BITS_PER_LONG; 236219820Sjeff bit = BITS_PER_LONG * pos; 237219820Sjeff addr += pos; 238219820Sjeff if (offs) { 239289621Shselasky mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs); 240219820Sjeff if (mask) 241219820Sjeff return (bit + __ffsl(mask)); 242282741Smarkj if (size - bit <= BITS_PER_LONG) 243282741Smarkj return (size); 244219820Sjeff bit += BITS_PER_LONG; 245219820Sjeff addr++; 246219820Sjeff } 247219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 248219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 249219820Sjeff if (~(*addr) == 0) 250219820Sjeff continue; 251219820Sjeff return (bit + __ffsl(~(*addr))); 252219820Sjeff } 253219820Sjeff if (size) { 254289621Shselasky mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 255219820Sjeff if (mask) 256219820Sjeff bit += __ffsl(mask); 257219820Sjeff else 258219820Sjeff bit += size; 259219820Sjeff } 260219820Sjeff return (bit); 261219820Sjeff} 262219820Sjeff 263277396Shselasky#define __set_bit(i, a) \ 264300506Shselasky atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 265277396Shselasky 266219820Sjeff#define set_bit(i, a) \ 267300506Shselasky atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 268219820Sjeff 269277396Shselasky#define __clear_bit(i, a) \ 270300506Shselasky atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 271277396Shselasky 272219820Sjeff#define clear_bit(i, a) \ 273300506Shselasky atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 274219820Sjeff 275219820Sjeff#define test_bit(i, a) \ 276361177Shselasky !!(READ_ONCE(((volatile const unsigned long *)(a))[BIT_WORD(i)]) & BIT_MASK(i)) 277219820Sjeff 278300506Shselaskystatic inline int 279300506Shselaskytest_and_clear_bit(long bit, volatile unsigned long *var) 280219820Sjeff{ 281219820Sjeff long val; 282219820Sjeff 283289621Shselasky var += BIT_WORD(bit); 284289621Shselasky bit %= BITS_PER_LONG; 285267395Shselasky bit = (1UL << bit); 286219820Sjeff 287337898Shselasky val = *var; 288337898Shselasky while (!atomic_fcmpset_long(var, &val, val & ~bit)) 289337898Shselasky ; 290219820Sjeff return !!(val & bit); 291219820Sjeff} 292219820Sjeff 293300506Shselaskystatic inline int 294328653Shselasky__test_and_clear_bit(long bit, volatile unsigned long *var) 295328653Shselasky{ 296328653Shselasky long val; 297328653Shselasky 298328653Shselasky var += BIT_WORD(bit); 299328653Shselasky bit %= BITS_PER_LONG; 300328653Shselasky bit = (1UL << bit); 301328653Shselasky 302328653Shselasky val = *var; 303328653Shselasky *var &= ~bit; 304328653Shselasky 305328653Shselasky return !!(val & bit); 306328653Shselasky} 307328653Shselasky 308328653Shselaskystatic inline int 309300506Shselaskytest_and_set_bit(long bit, volatile unsigned long *var) 310219820Sjeff{ 311219820Sjeff long val; 312219820Sjeff 313289621Shselasky var += BIT_WORD(bit); 314289621Shselasky bit %= BITS_PER_LONG; 315267395Shselasky bit = (1UL << bit); 316219820Sjeff 317337898Shselasky val = *var; 318337898Shselasky while (!atomic_fcmpset_long(var, &val, val | bit)) 319337898Shselasky ; 320219820Sjeff return !!(val & bit); 321219820Sjeff} 322219820Sjeff 323328653Shselaskystatic inline int 324328653Shselasky__test_and_set_bit(long bit, volatile unsigned long *var) 325255932Salfred{ 326328653Shselasky long val; 327255932Salfred 328328653Shselasky var += BIT_WORD(bit); 329328653Shselasky bit %= BITS_PER_LONG; 330328653Shselasky bit = (1UL << bit); 331255932Salfred 332328653Shselasky val = *var; 333328653Shselasky *var |= bit; 334255932Salfred 335328653Shselasky return !!(val & bit); 336255932Salfred} 337255932Salfred 338255932Salfredenum { 339289621Shselasky REG_OP_ISFREE, 340289621Shselasky REG_OP_ALLOC, 341289621Shselasky REG_OP_RELEASE, 342255932Salfred}; 343255932Salfred 344300506Shselaskystatic inline int 345328653Shselaskylinux_reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 346255932Salfred{ 347289621Shselasky int nbits_reg; 348289621Shselasky int index; 349289621Shselasky int offset; 350289621Shselasky int nlongs_reg; 351289621Shselasky int nbitsinlong; 352289621Shselasky unsigned long mask; 353289621Shselasky int i; 354289621Shselasky int ret = 0; 355255932Salfred 356255932Salfred nbits_reg = 1 << order; 357255932Salfred index = pos / BITS_PER_LONG; 358255932Salfred offset = pos - (index * BITS_PER_LONG); 359255932Salfred nlongs_reg = BITS_TO_LONGS(nbits_reg); 360368828Shselasky nbitsinlong = MIN(nbits_reg, BITS_PER_LONG); 361255932Salfred 362255932Salfred mask = (1UL << (nbitsinlong - 1)); 363255932Salfred mask += mask - 1; 364255932Salfred mask <<= offset; 365255932Salfred 366255932Salfred switch (reg_op) { 367255932Salfred case REG_OP_ISFREE: 368255932Salfred for (i = 0; i < nlongs_reg; i++) { 369255932Salfred if (bitmap[index + i] & mask) 370255932Salfred goto done; 371255932Salfred } 372289621Shselasky ret = 1; 373255932Salfred break; 374255932Salfred 375255932Salfred case REG_OP_ALLOC: 376255932Salfred for (i = 0; i < nlongs_reg; i++) 377255932Salfred bitmap[index + i] |= mask; 378255932Salfred break; 379255932Salfred 380255932Salfred case REG_OP_RELEASE: 381255932Salfred for (i = 0; i < nlongs_reg; i++) 382255932Salfred bitmap[index + i] &= ~mask; 383255932Salfred break; 384255932Salfred } 385255932Salfreddone: 386255932Salfred return ret; 387255932Salfred} 388255932Salfred 389270710Shselasky#define for_each_set_bit(bit, addr, size) \ 390270710Shselasky for ((bit) = find_first_bit((addr), (size)); \ 391270710Shselasky (bit) < (size); \ 392270710Shselasky (bit) = find_next_bit((addr), (size), (bit) + 1)) 393270710Shselasky 394330855Shselasky#define for_each_clear_bit(bit, addr, size) \ 395330855Shselasky for ((bit) = find_first_zero_bit((addr), (size)); \ 396330855Shselasky (bit) < (size); \ 397330855Shselasky (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 398294829Shselasky 399328653Shselaskystatic inline uint64_t 400328653Shselaskysign_extend64(uint64_t value, int index) 401294829Shselasky{ 402328653Shselasky uint8_t shift = 63 - index; 403294829Shselasky 404328653Shselasky return ((int64_t)(value << shift) >> shift); 405294829Shselasky} 406294829Shselasky 407219820Sjeff#endif /* _LINUX_BITOPS_H_ */ 408