17e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#ifndef _PERF_LINUX_BITOPS_H_ 27e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define _PERF_LINUX_BITOPS_H_ 37e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 47e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#include <linux/kernel.h> 57e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#include <linux/compiler.h> 67e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#include <asm/hweight.h> 77e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 87e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#ifndef __WORDSIZE 97e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define __WORDSIZE (__SIZEOF_LONG__ * 8) 107e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#endif 117e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 127e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITS_PER_LONG __WORDSIZE 137e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITS_PER_BYTE 8 147e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) 157e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITS_TO_U64(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64)) 167e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITS_TO_U32(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32)) 177e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITS_TO_BYTES(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE) 187e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 197e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define for_each_set_bit(bit, addr, size) \ 207e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh for ((bit) = find_first_bit((addr), (size)); \ 217e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh (bit) < (size); \ 227e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh (bit) = find_next_bit((addr), (size), (bit) + 1)) 237e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 247e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh/* same as for_each_set_bit() but use bit as value to start with */ 257e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define for_each_set_bit_from(bit, addr, size) \ 267e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh for ((bit) = find_next_bit((addr), (size), (bit)); \ 277e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh (bit) < (size); \ 287e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh (bit) = find_next_bit((addr), (size), (bit) + 1)) 297e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 307e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic inline void set_bit(int nr, unsigned long *addr) 317e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 327e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh addr[nr / BITS_PER_LONG] |= 1UL << (nr % BITS_PER_LONG); 337e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 347e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 357e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic inline void clear_bit(int nr, unsigned long *addr) 367e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 377e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh addr[nr / BITS_PER_LONG] &= ~(1UL << (nr % BITS_PER_LONG)); 387e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 397e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 407e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic __always_inline int test_bit(unsigned int nr, const unsigned long *addr) 417e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 427e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return ((1UL << (nr % BITS_PER_LONG)) & 437e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh (((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0; 447e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 457e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 467e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic inline unsigned long hweight_long(unsigned long w) 477e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 487e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return sizeof(w) == 4 ? hweight32(w) : hweight64(w); 497e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 507e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 517e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) 527e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 537e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh/** 547e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh * __ffs - find first bit in word. 557e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh * @word: The word to search 567e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh * 577e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh * Undefined if no bit exists, so code should check against 0 first. 587e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh */ 597e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic __always_inline unsigned long __ffs(unsigned long word) 607e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 617e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh int num = 0; 627e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 637e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#if BITS_PER_LONG == 64 647e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((word & 0xffffffff) == 0) { 657e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh num += 32; 667e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh word >>= 32; 677e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 687e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#endif 697e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((word & 0xffff) == 0) { 707e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh num += 16; 717e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh word >>= 16; 727e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 737e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((word & 0xff) == 0) { 747e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh num += 8; 757e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh word >>= 8; 767e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 777e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((word & 0xf) == 0) { 787e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh num += 4; 797e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh word >>= 4; 807e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 817e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((word & 0x3) == 0) { 827e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh num += 2; 837e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh word >>= 2; 847e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 857e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((word & 0x1) == 0) 867e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh num += 1; 877e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return num; 887e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 897e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 907e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh/* 917e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh * Find the first set bit in a memory region. 927e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh */ 937e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic inline unsigned long 947e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshfind_first_bit(const unsigned long *addr, unsigned long size) 957e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 967e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh const unsigned long *p = addr; 977e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh unsigned long result = 0; 987e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh unsigned long tmp; 997e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 1007e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh while (size & ~(BITS_PER_LONG-1)) { 1017e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((tmp = *(p++))) 1027e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh goto found; 1037e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh result += BITS_PER_LONG; 1047e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh size -= BITS_PER_LONG; 1057e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 1067e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (!size) 1077e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return result; 1087e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 1097e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh tmp = (*p) & (~0UL >> (BITS_PER_LONG - size)); 1107e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (tmp == 0UL) /* Are any bits set? */ 1117e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return result + size; /* Nope. */ 1127e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshfound: 1137e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return result + __ffs(tmp); 1147e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 1157e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 1167e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh/* 1177e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh * Find the next set bit in a memory region. 1187e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh */ 1197e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshstatic inline unsigned long 1207e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshfind_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 1217e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh{ 1227e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh const unsigned long *p = addr + BITOP_WORD(offset); 1237e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh unsigned long result = offset & ~(BITS_PER_LONG-1); 1247e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh unsigned long tmp; 1257e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 1267e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (offset >= size) 1277e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return size; 1287e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh size -= result; 1297e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh offset %= BITS_PER_LONG; 1307e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (offset) { 1317e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh tmp = *(p++); 1327e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh tmp &= (~0UL << offset); 1337e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (size < BITS_PER_LONG) 1347e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh goto found_first; 1357e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (tmp) 1367e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh goto found_middle; 1377e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh size -= BITS_PER_LONG; 1387e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh result += BITS_PER_LONG; 1397e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 1407e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh while (size & ~(BITS_PER_LONG-1)) { 1417e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if ((tmp = *(p++))) 1427e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh goto found_middle; 1437e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh result += BITS_PER_LONG; 1447e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh size -= BITS_PER_LONG; 1457e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh } 1467e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (!size) 1477e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return result; 1487e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh tmp = *p; 1497e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 1507e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshfound_first: 1517e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh tmp &= (~0UL >> (BITS_PER_LONG - size)); 1527e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh if (tmp == 0UL) /* Are any bits set? */ 1537e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return result + size; /* Nope. */ 1547e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntoshfound_middle: 1557e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh return result + __ffs(tmp); 1567e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh} 1577e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh 1587e2f4e9d384d501cf86118ebac4b8de2b86eac53Than McIntosh#endif 159