Linuxカーネルデータ構造-BitMAP

Linuxカーネルデータ構造-BitMAP
1.概要
ドライバでは、ビットマップを使用してリソースを管理する場合があります.この方法は分かりやすいです.効率に特に要求がない場合、ビットマップを採用することは良い選択である.
実はカーネルソースコードにもビットマップを使用する場所がたくさんあります.例えば、cpumaskはその1つです.

typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;

ビットマップ管理の「リソース」を簡単に理解すると、0は「リソース」が利用可能であることを示し、1は「リソース」が占有されていることを示し、分かりやすい.もちろんカーネルには多くのビットマップ操作のAPIが提供されており、「拿来主義」の精神を十分に発揚すればよい.
2.ビットマップ定義
ドライバでカーネルを使用して提供されるビットマップは簡単です.定義されたインタフェースは次のとおりです.

#define DECLARE_BITMAP(name,bits) \
	unsigned long name[BITS_TO_LONGS(bits)]
#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))

実はDECLARE_を利用してBITMAP(name,bits)マクロはunsigned longの配列を定義し、bitsは必要なビットマップのbit個数を表し、nameは配列名であり、bit空間の開始アドレスも表す
3.ビットマップ操作
ビットマップ操作を説明する前に、カーネルでよく使われるbit操作関数をいくつか説明します.
3.1 bitビット操作

static inline void __set_bit(int nr, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);

	*p  |= mask;
}

static inline void __clear_bit(int nr, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);

	*p &= ~mask;
}
static inline void __change_bit(int nr, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);

	*p ^= mask;
}

set_bitは、bitmapにおいて対応するbit位置1を用いるものであり、nrは、bit indexが[0,bits-1]

に属する.

clear_bitとset_bitとは逆に、対応する位置のbitをビット0をクリアし、パラメータ定義をset_bit一致

change_bit該当位置の値を逆にし、0->1,1->0

もう3つのtest付き対応関数があります:test_and_set_bit;test_and_clear_bit;test_and_change_bit,old値を返す機能が多くなった
他にもtest_bit関数は、対応する位置がセットされているかどうかをテストするために使用されます

static inline int test_bit(int nr, const volatile unsigned long *addr)
{
	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
}

3.2 bitビット遍歴
bitビットの遍歴については以下のインタフェースがある

find_first_zero_bit(p,sz)		  bitmap     0   ，   
find_next_zero_bit(p,sz,off)	 offset  ，  bitmap     0   ，   
find_first_bit(p,sz)		  	  bitmap     1   ，   
find_next_bit(p,sz,off)			 offset  ，  bitmap     0   ，   

#define for_each_set_bit(bit, addr, size) \
	for ((bit) = find_first_bit((addr), (size));		\
	     (bit) < (size);					\
	     (bit) = find_next_bit((addr), (size), (bit) + 1))

/* same as for_each_set_bit() but use bit as value to start with */
#define for_each_set_bit_from(bit, addr, size) \
	for ((bit) = find_next_bit((addr), (size), (bit));	\
	     (bit) < (size);					\
	     (bit) = find_next_bit((addr), (size), (bit) + 1))

#define for_each_clear_bit(bit, addr, size) \
	for ((bit) = find_first_zero_bit((addr), (size));	\
	     (bit) < (size);					\
	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

/* same as for_each_clear_bit() but use bit as value to start with */
#define for_each_clear_bit_from(bit, addr, size) \
	for ((bit) = find_next_zero_bit((addr), (size), (bit));	\
	     (bit) < (size);					\
	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

for_each_set_bit:0ビットシーケンスからsize-1にループし、各ビットbitのビットシーケンス

を返す.

for_each_set_bit_from:上記の関数とほぼ同じですが、開始ビットが1つ追加され、特定の位置から検索が開始されると

に戻ります.

for_each_clear_bit:0ビットシーケンスからループし、0 bitの各ビットシーケンス

を返す

for_each_clear_bit_from:上と一致し、特定の位置から0 bitに戻るビットシーケンス

を検索する.
4.ビットマップの応用
冒頭で述べたように、ビットマップはリソースを管理する手段として使用できます.次に例を挙げます.

#include 
#include 

typedef   unsigned short uint16;
typedef   unsigned int   uint32;

#define BITMAP_LEN 128

DECLARE_BITMAP(Test, BITMAP_LEN);

static ssize_t bitmap_debug_get_usable_index(struct device *dev,
					 struct device_attribute *attr,
					 char *buf)
{
	uint16 index =0;
			
	index = find_first_zero_bit(Test,128);	

	printk("
   index:%d\r
",index);
	
	return 0;
					 
}

static ssize_t bitmap_debug_set_used_index(struct device *dev,
					  struct device_attribute *attr,
					  const char *buf, size_t count)
{
	uint32 start = 0;
	uint32 end   = 0;
	uint32 index = 0;
	uint32 old   = 0;
	
	sscanf(buf, "%u%u", &start, &end);
	
	if( start > end) printk("index start input error
\r");
	
	for(index = start; index <= end; index++) old = test_and_set_bit(index, Test);
			
	
	return count;
}

static	DEVICE_ATTR(get_index, S_IRUSR, bitmap_debug_get_usable_index,NULL);
static  DEVICE_ATTR(set_index, S_IWUSR, NULL,bitmap_debug_set_used_index);

struct attribute *bitmap_attrs[] = {
	
	&dev_attr_get_index.attr,
	&dev_attr_set_index.attr,
	
	NULL,
};

struct attribute_group bitmap_group = {
	.name  	= "bitmap",
	.attrs  = bitmap_attrs,
};

上のコードには128 bitmapの長さが定義されており、128部のリソースを表し、1は使用不可、0は使用可能を表し、sysfsを利用してbitmapのデバッグインタフェースを追加した結果は以下の通りである.

# cd /sys/devices/platform/debug/bitmap/
# cat get_index 

   index:0


# echo 0 100 > set_index 
# cat get_index 

   index:101