Linux 内核数据结构:位图(Bitmap).doc
《Linux 内核数据结构:位图(Bitmap).doc》由会员分享,可在线阅读,更多相关《Linux 内核数据结构:位图(Bitmap).doc(14页珍藏版)》请在三一文库上搜索。
1、Linux 内核数据结构:位图(Bitmap)位图和位运算除了各种链式和树形数据结构,Linux内核还提供了位图接口。位图在Linux内核中大量使用。下面的源代码文件包含这些结构的通用接口:lib/bitmap.cinclude/linux/bitmap.h除了这两个文件,还有一个特定的架构头文件,对特定架构的位运算进行优化。对于x86_64架构,使用下面头文件:arch/x86/include/asm/bitops.h正如我前面提到的,位图在Linux内核中大量使用。比如,位图可以用来存储系统在线/离线处理器,来支持CPU热插拔;再比如,位图在Linux内核等初始化过程中存储已分配的中断请求
2、。因此,本文重点分析位图在Linux内核中的具体实现。位图声明位图接口使用前,应当知晓Linux内核是如何声明位图的。一种简单的位图声明方式,即unsigned long数组。比如:Cunsigned long my_bitmap81unsigned long my_bitmap8第二种方式,采用DECLARE_BITMAP宏,此宏位于头文件include/linux/types.h中:C#define DECLARE_BITMAP(name,bits) unsigned long nameBITS_TO_LONGS(bits)12#define DECLARE_BITMAP(name,bit
3、s)unsigned long nameBITS_TO_LONGS(bits)DECLARE_BITMAP宏有两个参数:name 位图名字;bits 位图中比特总数目并且扩展元素大小为BITS_TO_LONGS(bits)、类型unsigned long的数组,而BITS_TO_LONGS宏将位转换为long类型,或者说计算出bits中包含多少byte元素:C#define BITS_PER_BYTE 8#define DIV_ROUND_UP(n,d) (n) + (d) - 1) / (d)#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PE
4、R_BYTE * sizeof(long)123#define BITS_PER_BYTE 8#define DIV_ROUND_UP(n,d) (n) + (d) - 1) / (d)#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)例如:DECLARE_BITMAP(my_bitmap, 64)结果为:C (64) + (64) - 1) / (64)112 (64) + (64) - 1) / (64)1和:Cunsigned long my_bitmap1;1unsigned long my_b
5、itmap1;位图声明后,我们就可以使用它了。特定架构的位运算我们已经查看了操作位图接口的两个源码文件和一个头文件。位图最重要最广泛的应用接口是特定架构,它位于头文件arch/x86/include/asm/bitops.h中首先,我们来看两个重要的函数:set_bit;clear_bit.我认为没有必要介绍这些函数是做什么的,通过函数名就可以知晓。我们来看函数的实现。进入头文件arch/x86/include/asm/bitops.h,你会注意到每个函数分两种类型:原子类型和非原子类型。在深入这些函数实现前,我们需要先了解一些原子性运算。一言以蔽之,原子性操作保障,位于同一数据上的两个甚至多
6、个运算,不能并发执行。x86架构提供一组原子性指令,如指令xchg、指令cmpxchg。除了原子性指令,一些非原子性指令可借助指令lock进行原子性运算。目前我们了解这些原子性运算就足够了,接下来可以开始考虑set_bit和clear_bit函数。先从非原子性类型的函数开始,非原子性set_bit和clear_bit函数名始于双下划线。正如你所了解的,所有的函数定义在头文件arch/x86/include/asm/bitops.h中,第一个函数_set_bit:Cstatic inline void _set_bit(long nr, volaTIle unsigned long *addr)
7、 asm volaTIle(bts %1,%0 : ADDR : Ir (nr) : memory);1234staTIc inline void _set_bit(long nr, volaTIle unsigned long *addr)asm volatile(bts %1,%0 : ADDR : Ir (nr) : memory);它拥有两个参数:nr 位图中比特数目addr 位图中某个比特需要设值的地址注意参数addr定义为volatile,告诉编译器此值或许被某个地址改变。而_set_bit容易实现。正如你所见,恰好它包含一行内联汇编代码。本例中,使用指令bts选择位图中的某个比特
8、值作为首个操作数,将已选择比特值存入寄存器CF标签中,并设置此比特。此处可以看到nr的用法,那addr呢?或许你已猜到其中的奥秘就在ADDR中。而ADDR是定义在头文件中的宏,扩展字符串,在该地址前面加入+m约束:C#define ADDR BITOP_ADDR(addr)#define BITOP_ADDR(x) +m (*(volatile long *) (x)12#define ADDRBITOP_ADDR(addr)#define BITOP_ADDR(x) +m (*(volatile long *) (x)除了+m,我们可以看到_set_bit函数中其它约束。让我们查看这些约束,
9、试着理解其中的含义:+m 表示内存操作数,+表示此操作数为输入和输出操作数;I 表示整数常数;r -表示寄存器操作数除了这些约束,还看到关键字memory,它会告知编译器此代码会更改内存中的值。接下来,我们来看同样功能,原子类型函数。它看起来要比非原子类型函数复杂得多:Cstatic _always_inline voidset_bit(long nr, volatile unsigned long *addr) if (IS_IMMEDIATE(nr) asm volatile(LOCK_PREFIX orb %1,%0 : CONST_MASK_ADDR(nr, addr) : iq (u
10、8)CONST_MASK(nr) : memory); else asm volatile(LOCK_PREFIX bts %1,%0 : BITOP_ADDR(addr) : Ir (nr) : memory); 12345678910111213static _always_inline voidset_bit(long nr, volatile unsigned long *addr)if (IS_IMMEDIATE(nr) asm volatile(LOCK_PREFIX orb %1,%0: CONST_MASK_ADDR(nr, addr): iq (u8)CONST_MASK(n
11、r): memory); else asm volatile(LOCK_PREFIX bts %1,%0: BITOP_ADDR(addr) : Ir (nr) : memory);注意它与函数_set_bit含有相同的参数列表,不同的是函数被标记有属性_always_inline。_always_inline是定义在include/linux/compiler-gcc.h中的宏,只是扩展了always_inline属性:C#define _always_inline inline _attribute_(always_inline)1#define _always_inline inline
12、 _attribute_(always_inline)这意味着函数会被内联以减少Linux内核镜像的大小。接着,我们试着去理解函数set_bit实现。函数set_bit伊始,便对比特数目进行检查。IS_IMMEDIATE是定义在相同头文件中的宏,用于扩展内置函数gcc:C#define IS_IMMEDIATE(nr) (_builtin_constant_p(nr)1#define IS_IMMEDIATE(nr)(_builtin_constant_p(nr)内置函数_builtin_constant_p返回1的条件是此参数在编译期为常数;否则返回0。无需使用指令bts设置比特值,因为编译
13、期比特数目为一常量。仅对已知字节地址进行按位或运算,并对比特数目bits进行掩码,使其高位为1,其它为0. 而比特数目在编译期若非常量,函数_set_bit中运算亦相同。宏CONST_MASK_ADDR:C#define CONST_MASK_ADDR(nr, addr) BITOP_ADDR(void *)(addr) + (nr)3)1#define CONST_MASK_ADDR(nr, addr) BITOP_ADDR(void *)(addr) + (nr)3)采用偏移量扩展某个地址为包含已知比特的字节。比如地址0x1000,以及比特数目0x9。0x9等于一个字节,加一个比特,地址为
14、addr+1:C hex(0x1000 + (0x9 3)0x100112 hex(0x1000 + (0x9 3)0x1001宏CONST_MASK表示看做字节的某已知比特数目,高位为1,其它比特为0:C#define CONST_MASK(nr) (1 1#define CONST_MASK(nr)(1 C bin(1 bin(1 0b10最后,我们使用按位或运算。假设address为0x4097,需要设置ox9比特:C bin(0x4097)0b100000010010111 bin(0x4097 0x9) | (1 bin(0x4097)0b100000010010111 bin(0x
15、4097 0x9) | (1 0b100010第九个比特将被设置注意所有的操作均标记有LOCK_PREFIX,即扩展为指令lock,确保运算以原子方式执行。如我们所知,除了set_bit和_set_bit运算,Linux内核还提供了两个逆向函数以原子或非原子方式清理比特,clear_bit和_clear_bit。这个两个函数均定义在相同的头文件中,并拥有相同的参数列表。当然不仅是参数相似,函数本身和set_bit以及 _set_bit都很相似。我们先来看非原子性函数_clear_bitCstatic inline void _clear_bit(long nr, volatile unsign
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Linux 内核数据结构:位图Bitmap 内核 数据结构 位图 Bitmap
链接地址:https://www.31doc.com/p-3255210.html