1e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#ifndef _PERF_LINUX_BITOPS_H_ 2e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define _PERF_LINUX_BITOPS_H_ 3e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 4e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#include <linux/kernel.h> 5e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#include <linux/compiler.h> 6e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#include <asm/hweight.h> 7e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 8e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#ifndef __WORDSIZE 9e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define __WORDSIZE (__SIZEOF_LONG__ * 8) 10e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#endif 11e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 12e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITS_PER_LONG __WORDSIZE 13e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITS_PER_BYTE 8 14e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) 15e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITS_TO_U64(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64)) 16e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITS_TO_U32(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32)) 17e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITS_TO_BYTES(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE) 18e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 19e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define for_each_set_bit(bit, addr, size) \ 20e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng for ((bit) = find_first_bit((addr), (size)); \ 21e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (bit) < (size); \ 22e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (bit) = find_next_bit((addr), (size), (bit) + 1)) 23e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 24e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng/* same as for_each_set_bit() but use bit as value to start with */ 25e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define for_each_set_bit_from(bit, addr, size) \ 26e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng for ((bit) = find_next_bit((addr), (size), (bit)); \ 27e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (bit) < (size); \ 28e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (bit) = find_next_bit((addr), (size), (bit) + 1)) 29e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 30e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void set_bit(int nr, unsigned long *addr) 31e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 32e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng addr[nr / BITS_PER_LONG] |= 1UL << (nr % BITS_PER_LONG); 33e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 34e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 35e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline void clear_bit(int nr, unsigned long *addr) 36e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 37e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng addr[nr / BITS_PER_LONG] &= ~(1UL << (nr % BITS_PER_LONG)); 38e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 39e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 40e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic __always_inline int test_bit(unsigned int nr, const unsigned long *addr) 41e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 42e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return ((1UL << (nr % BITS_PER_LONG)) & 43e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng (((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0; 44e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 45e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 46e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline unsigned long hweight_long(unsigned long w) 47e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 48e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return sizeof(w) == 4 ? hweight32(w) : hweight64(w); 49e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 50e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 51e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) 52e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 53e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng/** 54e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * __ffs - find first bit in word. 55e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * @word: The word to search 56e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * 57e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Undefined if no bit exists, so code should check against 0 first. 58e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 59e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic __always_inline unsigned long __ffs(unsigned long word) 60e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 61e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng int num = 0; 62e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 63e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#if BITS_PER_LONG == 64 64e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((word & 0xffffffff) == 0) { 65e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng num += 32; 66e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng word >>= 32; 67e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 68e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#endif 69e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((word & 0xffff) == 0) { 70e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng num += 16; 71e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng word >>= 16; 72e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 73e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((word & 0xff) == 0) { 74e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng num += 8; 75e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng word >>= 8; 76e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 77e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((word & 0xf) == 0) { 78e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng num += 4; 79e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng word >>= 4; 80e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 81e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((word & 0x3) == 0) { 82e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng num += 2; 83e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng word >>= 2; 84e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 85e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((word & 0x1) == 0) 86e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng num += 1; 87e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return num; 88e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 89e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 90e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng/* 91e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Find the first set bit in a memory region. 92e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 93e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline unsigned long 94e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengfind_first_bit(const unsigned long *addr, unsigned long size) 95e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 96e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng const unsigned long *p = addr; 97e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng unsigned long result = 0; 98e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng unsigned long tmp; 99e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 100e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng while (size & ~(BITS_PER_LONG-1)) { 101e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((tmp = *(p++))) 102e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng goto found; 103e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng result += BITS_PER_LONG; 104e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng size -= BITS_PER_LONG; 105e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 106e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (!size) 107e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return result; 108e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 109e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = (*p) & (~0UL >> (BITS_PER_LONG - size)); 110e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (tmp == 0UL) /* Are any bits set? */ 111e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return result + size; /* Nope. */ 112e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengfound: 113e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return result + __ffs(tmp); 114e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 115e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 116e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng/* 117e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng * Find the next set bit in a memory region. 118e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng */ 119e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengstatic inline unsigned long 120e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengfind_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 121e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng{ 122e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng const unsigned long *p = addr + BITOP_WORD(offset); 123e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng unsigned long result = offset & ~(BITS_PER_LONG-1); 124e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng unsigned long tmp; 125e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 126e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (offset >= size) 127e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return size; 128e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng size -= result; 129e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng offset %= BITS_PER_LONG; 130e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (offset) { 131e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = *(p++); 132e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp &= (~0UL << offset); 133e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (size < BITS_PER_LONG) 134e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng goto found_first; 135e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (tmp) 136e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng goto found_middle; 137e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng size -= BITS_PER_LONG; 138e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng result += BITS_PER_LONG; 139e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 140e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng while (size & ~(BITS_PER_LONG-1)) { 141e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if ((tmp = *(p++))) 142e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng goto found_middle; 143e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng result += BITS_PER_LONG; 144e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng size -= BITS_PER_LONG; 145e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng } 146e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (!size) 147e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return result; 148e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp = *p; 149e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 150e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengfound_first: 151e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng tmp &= (~0UL >> (BITS_PER_LONG - size)); 152e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng if (tmp == 0UL) /* Are any bits set? */ 153e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return result + size; /* Nope. */ 154e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Chengfound_middle: 155e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng return result + __ffs(tmp); 156e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng} 157e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng 158e6e8a0bd7cffcc9ae2e0e75546fb12a19213d4aeBen Cheng#endif 159