비트맵(Bitmap)
이라 하면 흔히 이런 이미지를 생각할 수 있다. 물론 이것도 비트맵은 맞지만 이번 장에서 말하고자 하는 리눅스 커널의 비트맵은 이것과는 살짝 다르다. 물론 근본 개념은 bit
+ map
이라는점에서 같다. 아무튼 비트(bit
)를 지도처럼 쭉 늘여 놓은(mapped
) 것이 bitmap
이다.
Bitmap
이란 리눅스에서 비트맵(bitmap
) 이란 데이터를 비트 단위로 처리하기 위해 long
형의 배열로 할당한 자료형이라 볼 수 있다. 다만 비트 단위로 데이터를 다루려 해도 알다시피 C 의 모든 자료형은 최소 단위가 byte
이다. 따라서 딱 300 bit
의 비트맵을 만들고 싶어도 실제론 그 크기를 살짝 넘길 수 있다.
// 300-bit 크기의 비트맵을 만들기 위해 선언한 my_bitmap long my_bitmap[5]; // long 이 64-bit 이라 가정, 20-bit 초과
구현에 관한 코드는 리눅스 커널의 파일을 뜯어가며 살펴볼 것이다.
// 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))
위 코드는 리눅스 커널의 비트맵 관련 매크로를 모아서 묶어 놓은 것이다.
위에서 부터 순서대로 설명하면...
BITS_TO_BYTES(bits)
> include/linux/bitops.h
1 byte
는 8 bit
로 가정) 가령 30 bit
를 표현하고 싶다면, 적어도 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
nr
을 받아서 이 비트를 담을 수 있는 long
자료형의 크기를 계산한다. 1번 에서 본 my_bitmap
을 만들기 위해 300
을 전달하면 5
를 반환한다.실제 해당 경로에 들어가서 어떤 식으로 정의되어 있는지 이해하고 또 확인하는 것이 중요하다. BITS_TO_BYTES(bits)
의 경우 필자가 작성한 정의와는 다르게 생겼으므로 한번쯤 확인해봐도 좋을 것이다.
bitmap1.c
) 위 매크로를 테스트하기 위한 예제 코드를 작성해보겠다. 2번 에서 각 매크로에 대해 설명할 때, 다음과 같이 매크로
> 파일
의 형태로 표시했으므로 각 파일에 삽입하면 된다.
test/bits/bitmap1.c
/** M: Yeounsu Moon <yyyynoom@gmail.com> 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; }
위 코드를 컴파일하여 실행하면 다음과 같은 결과가 나온다:
코드 내에서 linux
경로를 명시했으므로 gcc
로 컴파일할 경로를 include
로 바꾸는 것에 유의하라. 또한 서식 문자와 관련한 에러가 발생할 수 있으나 큰 문제는 아니므로 무시해도 된다.
// include/linux/types.h #define DECLARE_BITMAP(name, bits) \ unsigned long name[BITS_TO_LONGS(bits)]
DECLARE_BITMAP
은 bits
크기의 비트 수를 포함할 수 있는 name
이라는 이름의 가진 변수를 정의한다. 위에서 설명했던 매크로를 모두 이해했다면 이해하는데 별 무리는 없을 것이다. 이제 이 매크로와 include/linux/bitmap.h
헤더 파일에서 제공하는 함수들을 통해 작은 프로그램을 만들어 볼 것이다.
위 헤더파일에선 비트맵과 관련된 다양한 함수를 제공한다. 매우 다양한 함수가 있지만 필자는 bitmap_zero()
와 bitmap_fill()
함수를 사용해보려 한다. 다음 함수의 정의를 복사해서 로컬의 include/linux/bitmap.h
헤더의 복사 붙여넣기 한다.
include/linux/bitmap.h
#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); }
bitmap_zero
함수는 인자로 들어온 dst
비트맵의 nbits
를 0
으로 가득 채운다. 반대로 bitmap_fill
함수는 인자로 들어온 dst
비트맵의 nbits
를 1
로 채운다. 이 밖에도 다양한 함수가 있으므로 한번쯤 헤더파일을 흝어보는걸 추천한다.
bitmap2.c
)
test/bits/bitmap2.c
/** M: Yeounsu Moon <yyyynoom@gmail.com> 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; }
bits_print
는 이전에 작성했던 함수와 비슷하지만 nbits
만큼 출력한다는 점에서 이전 함수와는 다소 다르다. mask2
의 마지막 비트를 켜고 오른쪽으로 한번씩 shifting
하여 v[i]
의 각 비트를 출력한다. main
함수에서는 선언하고 초기화하지 않은 bitv
를 출력(쓰레기값)하고, 두 번째로 모든 비트를 비운 결과를, 마지막으로 모든 비트를 가득 채운 결과를 출력한다. 실제 실행 결과는 다음과 같다:
컴파일 시 나오는 경고 메세지는 무시해도 좋다. 실행결과에 주목하라. 처음으로 출력한 v 는 쓰레기 값을 가지고 있으므로 컴퓨터마다 그 출력결과가 다를 수 있다. 필자의 경우는 요상한 비트가 출력 되었다.
두 번째는 모든 비트를 clear
한 것인데 보는 것과 같이 깔끔하게 0
으로 비워진 상태로 출력 되었다. 마지막 출력 결과 역시 모든 비트가 켜진 상태임을 확인할 수 있다.
[사진] https://www.vectorstock.com/royalty-free-vector/africa-bitmap-8-bit-tech-logo-icon-vector-24171577
[책] 리눅스 커널 소스 해설: 기초입문 (정재준 저)