비트맵(Bitmap)といえば、このようなイメージを思い浮かべることが多い.もちろんこれもビットマップですが、本章で説明するLinuxカーネルのビットマップはこれとは少し違います.もちろん、根本的な概念はbit+24579142です.つまり、ビット(map)を地図のように並べた(bit)がmappedです.

1.Linuxカーネルのビットマップは

Linuxでは、ビットマップ(Bitmap)は、ビット単位のデータを処理するために割り当てられたbitmap型配列のデータ型と見なすことができる.しかし、ビット単位でデータを処理しようとしても、Cのすべての資料型の最小単位はlongであることが知られている.したがって,byteのビットマップのみを作成しようとしても,実際にはその大きさを省略することができる.

// 300-bit 크기의 비트맵을 만들기 위해 선언한 my_bitmap
long my_bitmap[5]; // long 이 64-bit 이라 가정, 20-bit 초과

実装に関するコードはLinuxカーネルでファイルを開いて表示されます.

2.ビット関連マクロの定義

// tools/include/linux/bitops.h
#define BITS_TO_BYTES(bits) (((bits) + BITS_PER_BYTE - 1) / BITS_PER_BYTE)

// include/uapi/linux/kernel.h
#define __KERNEL_DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
#define DIV_ROUND_UP __KERNEL_DIV_ROUND_UP

// include/linux/bitops.h
#define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))

上のコードはLinuxカーネルのビットマップ関連マクロの集合です.
上から順番に説明すると….

300 bit > BITS_TO_BYTES(bits)ビット数を表す最小バイト数を表します.(include/linux/bitops.hが1 byteであると仮定する)8 bitを表現するには、少なくとも30 bitが必要であると仮定する.実際のLinuxカーネル内のコードでは、上のコードではなく、次の4 byte関数が使用されます.

8 * 4 = 32 > DIV_ROUND_UP __KERNEL_DIV_ROUND_UP(n, d)をinclude/linux/kernel.hで割った結果、無条件に増加した値を示す.nと仮定し、その値はdであるが、上記の関数を使用して4 / 3を返す.

1.333... > 2 DIV_ROUND_UPのマクロをマッピングするだけです.

include/linux/kernel.h > __KERNEL_DIV_ROUND_UPデータ型を桁数で表します.BITS_PER_TYPE(type)はinclude/linux/bitops.hであるため、shortに戻る.(sizeof(short) * 8が16であると仮定)

.

short > 2 byte受信ビット数BITS_TO_LONGS(nr)は、そのビットを含むことができるinclude/linux/bitops.hのデータ型のサイズを計算する.1番で見られるnrを作成するために、転送longはmy_bitmapに戻る.

重要なのは、実際にこのパスに入る定義方法を理解し、確認することです.300の場合は筆者の定義とは異なるので確認できる.

3.サンプルコードの作成(5)

上記のマクロをテストするサンプルコードを作成します.2番において各マクロについて説明すると、BITS_TO_BYTES(bits)>bitmap1.cとして表示されるので、各ファイルに挿入することができる.

マクロ

/**
	M: Yeounsu Moon <[email protected]>
	W: https://velog.io/@mythos
	F: test/bits/bitmap1.c
	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License
*/

#include <stdio.h>
#include <stdlib.h>
#include "linux/types.h"
#include "linux/bits.h"
#include "linux/bitops.h"
#include "linux/kernel.h"

#include <inttypes.h>

int main(void)
{
	s32 i;
	u64 size;

	printf("char = %zu bits\n", BITS_PER_TYPE(char));
	printf("int = %zu bits\n", BITS_PER_TYPE(int));
	printf("long = %zu bits\n", BITS_PER_TYPE(long));

	for (i = 0; i < 321; i+= 32) {
		size = BITS_TO_LONGS(i);
		printf("%3" PRId32 ": size = %" PRIu64 " \n", i, size);
	}

	DECLARE_BITMAP(bitv, 300);
	printf("bitv size = %zu bits\n", sizeof(bitv) * BITS_PER_BYTE);

	return 0;
}

上記のコードをコンパイルして実行すると、次の結果が得られます.

コードには파일のパスが指定されています.test/bits/bitmap1.cにコンパイルするパスをlinuxに変更することに注意してください.また、フォーマット文字に関するエラーが発生する可能性がありますが、これは大きな問題ではなく、無視できます.

4.ビットマップの宣言

// include/linux/types.h
#define DECLARE_BITMAP(name, bits) \
unsigned long name[BITS_TO_LONGS(bits)]

gccは、includeサイズのビット数を含むことができるDECLARE_BITMAPという変数を定義する.上記のすべてのマクロを理解すれば、理解に支障はありません.次に、これらのマクロとbitsヘッダファイルで提供される関数を使用して、ウィジェットを作成します.
ビットヘッダファイルには、ビットマップに関連する様々な関数が提供される.いろいろな関数がありますが、筆者はnameとinclude/linux/bitmap.hの関数を使ってみました.次の関数の定義をコピーし、ローカルbitmap_zero()ヘッダーのコピーを貼り付けます.

bitmap_fill()

#include <string.h>

static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
{
	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
	memset(dst, 0, len);
}

static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
{
	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
	memset(dst, 0xff, len);
}

include/linux/bitmap.h関数は、入力パラメータのinclude/linux/bitmap.hビットマップのbitmap_zeroをdstに充填する.逆に、nbits関数は、入力パラメータの0ビットマップのbitmap_fillをdstに充填する.このほかにも複数の関数があるので、ヘッダファイルを1回参照することをお勧めします.

5.サンプルコードの作成(nbits)

1

/**
	M: Yeounsu Moon <[email protected]>
	W: https://www.kernel.bz
	F: test/bits/bitmap2.c
	This program is free software; you cna redistribute it and/or
	modify it under the terms of the GNU General Public License
*/

#include <stdio.h>
#include <stdlib.h>

#include "linux/types.h"
#include "linux/bits.h"
#include "linux/bitops.h" 
#include "linux/kernel.h"
#include "linux/bitmap.h"

void bits_print(unsigned long *v, u32 nbits)
{
	s32 i;
	u32 wc = BIT_WORD(nbits);
	u64 mask1, mask2 = BIT(BITS_PER_TYPE(long) - 1);

	for (i = wc; i >= 0; i--) {
		printf("v[%d] = ", i);
		mask1 = mask2;
		while (mask1) {
			printf("%d", (v[i] & mask1 ? 1 : 0));
			mask1 >>= 1;
		}
		printf("\n");
	}

	printf("\n");
}

int main(int argc, char *argv[])
{
	long nbits;
	char *test;

	if (argc != 2)
		exit(EXIT_FAILURE);

	nbits = strtol(argv[1], &test, 10);
	if (argv[1] == test)
		exit(EXIT_FAILURE);

	u32 v = BITS_TO_LONGS(nbits);
	u32 len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);

	printf("nbits = %u, array = %u, bytes = %u, bits = %u\n\n",
		nbits, v, len, len * BITS_PER_BYTE);

	DECLARE_BITMAP(bitv, nbits);
	bits_print(bitv, nbits);

	bitmap_zero(bitv, nbits);
	bits_print(bitv, nbits);

	bitmap_fill(bitv, nbits);
	bits_print(bitv, nbits);

	return 0;
}

bitmap2.cは以前に記述された関数と似ているが、出力された値はtest/bits/bitmap2.cであり、これは以前の関数とは異なる.bits_printの最後のビットを開き、右にnbitsを出力し、mask2の各ビットを出力します.shifting関数では、宣言および初期化されていないv[i](ゴミ値)が出力され、2番目の出力はすべてのビットが空の結果であり、最後にすべてのビットが満の結果が出力される.実際の実行結果は次のとおりです.

コンパイル時に発行される警告情報は無視できます.実施結果に注目する.最初に出力されたvはゴミ値を有するため、コンピュータごとに出力結果が異なる場合がある.筆者の場合は変な位が出た.
2つ目はすべてのビットがmainで、あなたが見たように、bitvが簡潔に空いています.最後の出力結果は、すべてのビットが開いていることを決定することもできる.

ソース

[写真]https://www.vectorstock.com/royalty-free-vector/africa-bitmap-8-bit-tech-logo-icon-vector-24171577
[書]Linuxカーネルソースコード解説:基礎入門(鄭在俊著)