---------------------------------------------------------------- find_next_zero_bit() ---------------------------------------------------------------- 内核注释： 1.功能： find_next_zero_bit - find the first zero bit in a memory region 但是参数条件为：@offset指定了开始搜索的位号(bitnumber)。在一段连续的内存中找到第一个为'0'的位。
2.参数： @addr: The address to base the search on @offset: The bitnumber to start searching at @size: The maximum size to search
int find_next_zero_bit(const unsigned long *addr, int size, int offset); 内核中这个文件只给出了函数的声明，并没给出实现代码。 -------------------------------------------------------------- 我从几个不同CPU种类的头文件中抽取的代码来为例子来仔细的研究： -------------------------------------------------------------- include\asm-v850\bitops.h ffz() -------------------------------------------------------------- 1.功能：ffz = Find First Zero in word.在双字中找到第一个为'0'的位。
2.注意：Undefined if no zero exists.The functions are not atomic. 对全'1'这种情况无定义，但是由于右移时，最高位填充'0'，while循环可以结束，这时返回result == 32,也就是全'1'的这种情况。
extern __inline__ unsigned long ffz (unsigned long word) { unsigned long result = 0;
while (word & 1) { result++; word >>= 1; } return result; } -------------------------------------------------------------- include\asm-m32r\bitops.h ffz() -------------------------------------------------------------- 功能,注意同前. static __inline__ unsigned long ffz(unsigned long word) { int k;
word = ~word; k = 0; if (!(word & 0x0000ffff)) { k += 16; word >>= 16; } if (!(word & 0x000000ff)) { k += 8; word >>= 8; } if (!(word & 0x0000000f)) { k += 4; word >>= 4; } if (!(word & 0x00000003)) { k += 2; word >>= 2; } if (!(word & 0x00000001)) { k += 1; }
return k; } 分析： 1.问题转化： 在word中寻找为第一个为'0'的位 word = ~word;这就使问题转化为在word中寻找为第一个为'1'的位
4.类似上面的，下面分别以4位，2位，1位来分界之：若条件满足则将高4位，2位，1位右移至低4位，2位，1位，同时位计数器相应相加。 if (!(word & 0x0000000f)) { k += 4; word >>= 4; } if (!(word & 0x00000003)) { k += 2; word >>= 2; } if (!(word & 0x00000001)) { k += 1; }
5.带几个数进行运算,验证程序逻辑： 本是要找word中的第一个为'0'的位置<===>找~word中的第一个为'1'的位置: --------------------------------------------------------------- word == ~word == 0x00000001 (即word == 0xfffffffe) 执行如下： if (!(word & 0x0000ffff)) { k += 16; word >>= 16; } 条件不满足，k == 0, word == 0x00000001
if (!(word & 0x000000ff)) { k += 8; word >>= 8; } 条件不满足, k == 0, word == 0x00000001
if (!(word & 0x0000000f)) { k += 4; word >>= 4; } 条件不满足, k == 0, word == 0x00000001
if (!(word & 0x00000003)) { k += 2; word >>= 2; } 条件不满足, k == 0, word == 0x00000001
if (!(word & 0x00000001)) { k += 1; } 条件满足, k == 1, word == 0x00000001 ---------------------------------------------------------------
word == ~word == 0x10000000 执行如下： if (!(word & 0x0000ffff)) { k += 16; word >>= 16; } 条件满足，k == 16, word == 0x00001000
if (!(word & 0x000000ff)) { k += 8; word >>= 8; } 条件满足, k == 24, word == 0x00000010
if (!(word & 0x0000000f)) { k += 4; word >>= 4; } 条件满足, k == 28, word == 0x00000008
if (!(word & 0x00000003)) { k += 2; word >>= 2; } 条件满足, k == 30, word == 0x00000002
if (!(word & 0x00000001)) { k += 1; } 条件满足, k == 31, word == 0x00000001 ---------------------------------------------------------------
word == ~word == 0x00ff0000 执行如下： if (!(word & 0x0000ffff)) { k += 16; word >>= 16; } 条件满足，k == 16, word == 0x000000ff
if (!(word & 0x000000ff)) { k += 8; word >>= 8; } 条件不满足, k == 16, word == 0x000000ff
if (!(word & 0x0000000f)) { k += 4; word >>= 4; } 条件不满足, k == 16, word == 0x000000ff
if (!(word & 0x00000003)) { k += 2; word >>= 2; } 条件不满足, k == 16, word == 0x000000ff
if (!(word & 0x00000001)) { k += 1; } 条件不满足, k == 16, word == 0x000000ff --------------------------------------------------------------- word == ~word == 0x0000 f000 执行如下： if (!(word & 0x0000 ffff)) { k += 16; word >>= 16; } 条件不满足，k == 0, word == 0x0000 f000
if (!(word & 0x0000 00ff)) { k += 8; word >>= 8; } 条件满足, k == 8, word == 0x0000 00f0
if (!(word & 0x0000 000f)) { k += 4; word >>= 4; } 条件满足, k == 12, word == 0x0000 000f
if (!(word & 0x0000 0003)) { k += 2; word >>= 2; } 条件不满足, k == 12, word == 0x0000 000f
if (!(word & 0x0000 0001)) { k += 1; } 条件不满足, k == 12, word == 0x0000 000f -------------------------------------------------------------- word == ~word == 0x05 00 00 00 0000 0101 ... 执行如下： if (!(word & 0x0000ffff)) { k += 16; word >>= 16; } 条件满足，k == 16, word == 0x0000 0500
if (!(word & 0x000000ff)) { k += 8; word >>= 8; } 条件满足, k == 24, word == 0x0000 0005
if (!(word & 0x0000000f)) { k += 4; word >>= 4; } 条件不满足, k == 24, word == 0x0000 0005
if (!(word & 0x00000003)) { k += 2; word >>= 2; } 条件不满足, k == 24, word == 0x0000 0005
if (!(word & 0x00000001)) { k += 1; } 条件不满足, k == 24, word == 0x0000 0005 -------------------------------------------------------------- find_next_zero_bit() -------------------------------------------------------------- @addr: The address to base the search on @offset: The bitnumber to start searching at @size: The maximum size to search set,res,offset,bit以位为单位; p,addr,以字节为单位； 功能：从offset所指向的位开始，在一段连续的内存中，找从这里起（含offset这一位）的后面第一个为'0'的位。 static __inline__ int find_next_zero_bit(void *addr, int size, int offset) { unsigned long *p = ((unsigned long *)addr) + (offset >> 5); int set = 0, bit = offset & 31, res; if (bit) { /* * Look for zero in first byte */ __asm__("bsfl %1,%0\n\t" "jne 1f\n\t" "movl $32, %0\n" "1:" : "=r"(set) :"r"(~ (*p >> bit))); if (set < (32 - bit)) return set + offset; set = 32 - bit; p++; } /* * No zero yet, search remaining full bytes for a zero */ res = find_first_zero_bit(p, size - 32 * (p - (unsigned long *)addr)); return (offset + set + res); }
movl $32, %0 ： 当从offset位开始的后面的32个位为全'0',即：取反前为全'1'，这时置set = 32 -------------------------------------------------------------- 6.有三种情况： 1)set,res,offset,bit以位为单位; p,addr,以字节为单位； unsigned long *p = ((unsigned long *)addr) + (offset >> 5); int set = 0, bit = offset & 31, res; addr:指向首地址，p指向指向offset所指向的起始位所处的那个unsigned long型4B双字的开始处。offset指向的待search的起始位'*'。bit: offset所指向的起始位位于所处在的那个unsigned long型4B双字中的第几位。 此时bit不为0，执行if体。 if (bit) { /* * Look for zero in first byte */ __asm__("bsfl %1,%0\n\t" "jne 1f\n\t" "movl $32, %0\n" "1:" : "=r"(set) :"r"(~ (*p >> bit))); 经过if中的汇编指令的执行，得到了set，'*'距离'0'的距离长度。由于此时，以offset所指向的search起始位为unsigned long 型4B的首位。于是，'0'的位置可能在以p所指的32位中，也可在其外，这里考虑在其内的情况。 p offset | | | | |----32-----| | | 32-bit| | | | addr | | | | |bit|set| | | | | | | ------------------------------ | | * '0' | | | | | | ------------------------------ | | | | |-----------size-------------| if (set < (32 - bit)) return set + offset; 由于set < (32 - bit),所以返回set + offset.从图知这就是自'*',offset起始处后第一个为'0'处。
-------------------------------------------------------------- 2)unsigned long *p = ((unsigned long *)addr) + (offset >> 5); int set = 0, bit = offset & 31, res; addr:指向首地址，p指向指向offset所指向的起始位所处的那个unsigned long型4B双字的开始处。offset指向的待search的起始位'*'。bit: offset所指向的起始位位于所处在的那个unsigned long型4B双字中的第几位。 p offset p(p++) | | | | | | |----32-----| | | 32-bit| | | | addr | | |res| | |bit|--set--| | | | | | | ------------------------------ | | * | '0' | | | | | ------------------------------ | |-set调整前-| | | | |-----------size-------------| 此时bit不为0，执行if体。经过if中的汇编指令的执行，得到了‘set调整前’距离'0'的距离长度。由于此时，以offset所指向的search起始位为unsigned long 型4B的首位。于是，'0'的位置可能在以p所指的32位中，也可在其外，这里考虑在其外的情况。 if (bit) { /* * Look for zero in first byte */ __asm__("bsfl %1,%0\n\t" "jne 1f\n\t" "movl $32, %0\n" "1:" : "=r"(set) :"r"(~ (*p >> bit))); 当'0'在p所指向的32位其外，即上图情况时候。经汇编指令得到的set值，设为‘set调整前’ > (32 - bit)见上图。则进行set调整set = 32 - bit;见上图set.然后p++,p移动32位，指向下一个unsigned long型4B。 if (set < (32 - bit)) return set + offset; set = 32 - bit; p++; } res:见上图示意，易懂。 res = find_first_zero_bit(p, size - 32 * (p - (unsigned long *)addr));
return (offset + set + res); /* * No zero yet, search remaining full bytes for a zero */ res = find_first_zero_bit(p, size - 32 * (p - (unsigned long *)addr)); return (offset + set + res); -------------------------------------------------------------- 3）若offset位于unsigned long边界上，见图所示： unsigned long *p = ((unsigned long *)addr) + (offset >> 5); int set = 0, bit = offset & 31, res; 分析：bit == 0,set == 0
if (bit) 条件不成立。
res = find_first_zero_bit(p, size - 32 * (p - (unsigned long *)addr)); return (offset + set + res)<==>return(offset + res)
offset p | | |----32-----| | | | | addr | | | | | | |-res--| | ------------------------------ | * '0' | | | | | | ------------------------------ | | | | |-----------size-------------| --------------------------------------------------------------- __ffs() ---------------------------------------------------------------- 功能：__ffs - find first bit '1''s bit number in word.在一个双字中找到第一个为'1'的位。
参数：@word: The word to search
说明： Undefined if no bit exists, so code should check against 0 first.
if (!x) return 0; if (!(x & 0xffff)) {x >>= 16; r += 16; } if (!(x & 0xff)) {x >>= 8; r += 8; } if (!(x & 0xf)) {x >>= 4; r += 4; } if (!(x & 3)) {x >>= 2; r += 2; } if (!(x & 1)) {x >>= 1; r += 1; } return r; } 比较：ffs():找双字中第一个为'1'的位 ffz():找双字中第一个为'0'的位 ---------------------------------------------------------------- find_first_bit() ---------------------------------------------------------------- 功能：find the first set bit in a memory region,其实是在一段连续的内存中找到第一个为'1'的位。
参数：@addr: The address to start the search at @size: The maximum size to search(以位计)
返回值：Returns the bit-number of the first set bit, not the number of the byte containing this bit.
static inline int find_first_bit(const unsigned long *addr, unsigned size) { int x = 0;
while (x < size) { unsigned long val = *addr++; if (val) return __ffs(val) + x; x += (sizeof(*addr)<<3); } return x; } 在const的作用下，addr可以变，但addr所指向的内容不能变。 ---------------------------------------------------------------- 比较异同 ---------------------------------------------------------------- find_first_zero_bit(const unsigned long *addr, unsigned size): find the first zero bit in a memory region 在连续的内存中找到第一个为0的位，并将该位的序号返回。
ffz(unsigned long word): Find First Zero in word.在双字中找到第一个为'0'的位。
find_next_zero_bit(void *addr, int size, int offset):从offset所指向的位开始，在一段连续的内存中，找从这里起（含offset这一位）的后面第一个为'0'的位。 这三个函数是找第一个为'0'的位，但找的对象一个为连续的内存，一个为双字，还有一个虽是双字，但是却指定了起始位置：offset。 ---------------------------------------------------------------- __ffs(unsigned long word): find first bit '1''s bit number in word.在一个双字中找到第一个为'1'的位。
find_first_bit(const unsigned long *addr, unsigned size):是在一段连续的内存中找到第一个为'1'的位。 这二个函数是找第一个为'1'的位，但找的对象一个为连续的内存，一个为双字， ---------------------------------------------------------------- ffz() ---------------------------------------------------------------- 本是在双字中找到第一个为'0'的位，但~word,则为'0'的位变为'1',则转化为找第一个为'1'的位。 static inline unsigned long ffz(unsigned long word) { __asm__("bsfl %1,%0" :"=r" (word) :"r" (~word)); return word; } ---------------------------------------------------------------- sched_find_first_bit() ---------------------------------------------------------------- 内核注释： Every architecture must define this function. It's the fastest way of searching a 140-bit bitmap where the first 100 bits are unlikely to be set. It's guaranteed that at least one of the 140 bits is cleared.
static inline int sched_find_first_bit(const unsigned long *b) { if (unlikely(b[0])) return __ffs(b[0]); if (unlikely(b[1])) return __ffs(b[1]) + 32; if (unlikely(b[2])) return __ffs(b[2]) + 64; if (b[3]) return __ffs(b[3]) + 96; return __ffs(b[4]) + 128; } 要快速设置长位（如：160位）中的高位中的位，如果从低位扫描上来就慢了。运用数组一次就以4B（32位）为单位来提取，这就只须对这4B，32位进行扫描，大大提高了效率。然后再运用unlikely()直接对可能性小的地方，让编译器优化之。 ---------------------------------------------------------------- ffs() ---------------------------------------------------------------- ffs():find first bit '1''s bit-number in a word @x: the word to search
static inline int ffs(int x) { int r;
__asm__("bsfl %1,%0\n\t" "jnz 1f\n\t" "movl $-1,%0\n" "1:" : "=r" (r) : "rm" (x)); return r+1; } ---------------------------------------------------------------- 预备工作： \include\linux\bitops.h ---------------------------------------------------------------- ---------------------------------------------------------------- generic_hweight32() ---------------------------------------------------------------- Hamming weight is the number of "1" bits in the binary sequence. /* * hweightN: returns the hamming weight (i.e. the number * of bits set) of a N-bit word. */ 求32位二进制数中的'1'的个数：
static inline unsigned int generic_hweight32(unsigned int w) { unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555); res = (res & 0x33333333) + ((res >> 2) & 0x33333333); res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F); res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF); return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF); }
分析： *************************************************************** 1.具体分析： unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
#include <linux/config.h> -------------------------------------------------------------- LOCK_PREFIX -------------------------------------------------------------- #ifdef CONFIG_SMP #define LOCK_PREFIX "lock ; " #else #define LOCK_PREFIX "" #endif -------------------------------------------------------------- ADDR -------------------------------------------------------------- #define ADDR (*(volatile long *) addr) -------------------------------------------------------------- set_bit() -------------------------------------------------------------- 功能：set_bit - Atomically set a bit in memory
参数： @nr: the bit to set @addr: the address to start counting from
说明： 1.This function is atomic and may not be reordered. 2.@nr may be almost arbitrarily large; this function is not restricted to acting on a single-word quantity.
static __inline__ void set_bit(int nr, volatile void * addr) { __asm__ __volatile__( LOCK_PREFIX "btsl %1,%0" :"=m" (ADDR) :"dIr" (nr) : "memory"); } 1.I:0-31的常数 2.d：使用寄存器edx 3.bts oprd1,oprd2 (Intel) 位测试并置位指令，被测试位送CF并且被测试位置1 oprd1:可以是16位或32位通用寄存器和16位或32位存储单元，用于指定要测试的内容。 oprd2:必须是8位立即数或与操作数oprd1长度相等的通用寄存器，用于指定要测试的位。但AT&T的btsl oprd2,oprd1源/目地操作数顺序相反。 -------------------------------------------------------------- __set_bit() -------------------------------------------------------------- 说明：Unlike set_bit(), this function is non-atomic and may be reordered.
参数： @nr: Bit to clear @addr: Address to start counting from
说明： clear_bit() is atomic and may not be reordered. However, it does not contain a memory barrier, so if it is used for locking purposes,you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit() in order to ensure changes are visible on other processors.
#define smp_mb__before_clear_bit() barrier() #define smp_mb__after_clear_bit() barrier() 清位前/后的多处理器的内存屏障。 -------------------------------------------------------------- __change_bit() -------------------------------------------------------------- 功能： __change_bit - Toggle a bit in memory
参数： @nr: the bit to change @addr: the address to start counting from
说明： Unlike change_bit(), this function is non-atomic and may be reordered.
static __inline__ void __change_bit(int nr, volatile void * addr) { __asm__ __volatile__( "btcl %1,%0" :"=m" (ADDR) :"dIr" (nr)); } -------------------------------------------------------------- change_bit() -------------------------------------------------------------- 说明：change_bit() is atomic and may not be reordered.Note that @nr may be almost arbitrarily large; this function is not restricted to acting on a single-word quantity.
static __inline__ void change_bit(int nr, volatile void * addr) { __asm__ __volatile__( LOCK_PREFIX "btcl %1,%0" :"=m" (ADDR) :"dIr" (nr)); } -------------------------------------------------------------- test_and_set_bit() -------------------------------------------------------------- 功能： test_and_set_bit - Set a bit and return its old value 注意返回值：当指定的该位为0时，返回0;当指定的该位为1时，返回-1，源代码有误，作者在计算机上设计一个主函数调用之，证实了这一想法。
参数： @nr: Bit to set @addr: Address to count from
说明： This operation is atomic and cannot be reordered.It also implies a memory barrier.
static __inline__ int test_and_set_bit(int nr, volatile void * addr) { int oldbit;
__asm__ __volatile__( LOCK_PREFIX "btsl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (ADDR) :"dIr" (nr) : "memory"); return oldbit; } -------------------------------------------------------------- __test_and_set_bit() -------------------------------------------------------------- This operation is non-atomic and can be reordered. 注意返回值：当指定的该位为0时，返回0;当指定的该位为1时，返回-1，源代码有误，作者在计算机上设计一个主函数调用之，证实了这一想法。
static __inline__ int __test_and_set_bit(int nr, volatile void * addr) { int oldbit;
__asm__( "btsl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (ADDR) :"dIr" (nr)); return oldbit; } -------------------------------------------------------------- test_and_clear_bit() -------------------------------------------------------------- 功能： test_and_clear_bit - Clear a bit and return its old value 注意返回值：当指定的该位为0时，返回0;当指定的该位为1时，返回-1，源代码有误，作者在计算机上设计一个主函数调用之，证实了这一想法。
参数： @nr: Bit to clear @addr: Address to count from
功能： This operation is atomic and cannot be reordered.It also implies a memory barrier.
static __inline__ int test_and_clear_bit(int nr, volatile void * addr) { int oldbit;
__asm__ __volatile__( LOCK_PREFIX "btrl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (ADDR) :"dIr" (nr) : "memory"); return oldbit; } -------------------------------------------------------------- __test_and_clear_bit() -------------------------------------------------------------- 说明： This operation is non-atomic and can be reordered. 注意返回值：当指定的该位为0时，返回0;当指定的该位为1时，返回-1，源代码有误，作者在计算机上设计一个主函数调用之，证实了这一想法。
static __inline__ int __test_and_clear_bit(int nr, volatile void * addr) { int oldbit;
__asm__( "btrl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (ADDR) :"dIr" (nr)); return oldbit; } -------------------------------------------------------------- __test_and_change_bit() -------------------------------------------------------------- /* WARNING: non atomic and it can be reordered! */ 注意返回值：当指定的该位为0时，返回0;当指定的该位为1时，返回-1，源代码有误，作者在计算机上设计一个主函数调用之，证实了这一想法。
static __inline__ int __test_and_change_bit(int nr, volatile void * addr) { int oldbit;
__asm__ __volatile__( "btcl %2,%1\n\tsbbl %0,%0" :"=r" (oldbit),"=m" (ADDR) :"dIr" (nr) : "memory"); return oldbit; } -------------------------------------------------------------- test_and_change_bit() -------------------------------------------------------------- 说明： This operation is atomic and cannot be reordered.It also implies a memory barrier. 注意返回值：当指定的该位为0时，返回0;当指定的该位为1时，返回-1，源代码有误，作者在计算机上设计一个主函数调用之，证实了这一想法。
static __inline__ int test_and_change_bit(int nr, volatile void * addr) { int oldbit;
__builtin_constant_p (exp)： 1）函数功能： You can use the built-in function __builtin_constant_p to determine if a value is known to be constant at compile-time and hence that GCC can perform constantfolding on expressions involving that value.
2）参数： The argument of the function is the value to test. 返回 1： if the argument is known to be a compiletime constant 返回 0 ：if it is not known to be a compile-time constant. -------------------------------------------------------------- set_bit_string() -------------------------------------------------------------- static inline void set_bit_string(unsigned long *bitmap, unsigned long i,int len) { unsigned long end = i + len; while (i < end) { __set_bit(i, bitmap); i++; } } 功能： 对bitmap所指向的内存单元，从i所指定的位开始，将len个位置1。
