<kernel v5.10>
Bitmap Operations
- 비트맵은 하나 이상의 unsigned long 타입을 사용한다.
- nbits는 항상 컴파일 시 상수로 평가되어야 한다. 그렇지 않고 변수로 평가되는 경우 많은 inline으로 인해 코드 크기가 매우 커진다.
- nbits가 1개의 unsigned long 데이터 타입으로 취급할 수 있는 경우와 그렇지 않은 경우의 구현 루틴이 나뉘어 있다.
- 1개의 unsigned long 데이터로 처리하는 경우 보통 한 번의 조작 루틴을 사용하여 빠른 처리가 가능하다.
- 여러 개의 unsigned long 데이터로 처리하는 경우 다량의 데이터 처리를 하느라 느리다.
bitmap 아키텍처별 헤더 및 c 파일
비트맵을 다루는 api들은 bitmap operation과 bit operations 양쪽에 구현되어 있다.
bitmap operation은 다음과 같이 기본 구현 헤더와 generic 라이브러리 파일로 준비되어 있다.
- 기본 구현 헤더
- include/linux/bitmap.h
- Generic 라이브러리
- lib/bitmap.c
비트맵 선언
DECLARE_BITMAP()
include/linux/bitmap.h
#define DECLARE_BITMAP(name,bits) \
unsigned long name[BITS_TO_LONGS(bits)]
정적 비트맵을 선언하는 매크로 함수이다.
- 예) DECLARE_BITMAP(foo, 96);
- unsigned long foo[2]; (64bits 기준)
비트맵 API들
include/linux/bitmap.h
/** * DOC: bitmap overview * * The available bitmap operations and their rough meaning in the * case that the bitmap is a single unsigned long are thus: * * The generated code is more efficient when nbits is known at * compile-time and at most BITS_PER_LONG. * * :: * * bitmap_zero(dst, nbits) *dst = 0UL * bitmap_fill(dst, nbits) *dst = ~0UL * bitmap_copy(dst, src, nbits) *dst = *src * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) * bitmap_complement(dst, src, nbits) *dst = ~(*src) * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2? * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set bits * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area * bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above * bitmap_next_clear_region(map, &start, &end, nbits) Find next clear region * bitmap_next_set_region(map, &start, &end, nbits) Find next set region * bitmap_for_each_clear_region(map, rs, re, start, end) * Iterate over all clear regions * bitmap_for_each_set_region(map, rs, re, start, end) * Iterate over all set regions * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest * bitmap_replace(dst, old, new, mask, nbits) *dst = (*old & ~(*mask)) | (*new & *mask) * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit) * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap * bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz * bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf * bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from kernel buf * bitmap_parselist_user(buf, dst, nbits) Parse bitmap dst from user buf * bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region * bitmap_release_region(bitmap, pos, order) Free specified bit region * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst * bitmap_get_value8(map, start) Get 8bit value from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start * * Note, bitmap_zero() and bitmap_fill() operate over the region of * unsigned longs, that is, bits behind bitmap till the unsigned long * boundary will be zeroed or filled as well. Consider to use * bitmap_clear() or bitmap_set() to make explicit zeroing or filling * respectively. */
bitmap_zero()
include/linux/bitmap.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);
}
비트맵 @dst의 @nbits 만큼의 비트를 0으로 클리어한다.
- 아래 small_const_nbits()를 사용하는 방법을 제거하였다.
small_const_nbits()
include/linux/bitmap.h
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
CPU 아키텍처가 한 번의 operation으로 비트맵을 처리할 수 있는지 여부를 판단한다.
- 먼저 __builtin_constant_p()를 사용하여 인수가 상수(변수가 아닌)인지를 알아낸다.
- 인수가 상수인 경우 true를 리턴하고,
- 변수인 경우는 무조건 false를 리턴한다.
- BITS_PER_LONG(32 or 64) 값 보다 작거나 같은 경우 true
비트맵 bitops API들
아래는 bitmap에서 사용할 수 있는 bitops 함수들이다.
- 상위 7개의 비트맵 조작 함수는 atomic 하게 처리하도록 구현되어 있다.
- 하위 5개의 비트맵 검색용 함수이다.
- 참고: Bit Operations | 문c
include/linux/bitmap.h
/** * DOC: bitmap bitops * * Also the following operations in asm/bitops.h apply to bitmaps.:: * * set_bit(bit, addr) *addr |= bit * clear_bit(bit, addr) *addr &= ~bit * change_bit(bit, addr) *addr ^= bit * test_bit(bit, addr) Is bit set in *addr? * test_and_set_bit(bit, addr) Set bit and return old value * test_and_clear_bit(bit, addr) Clear bit and return old value * test_and_change_bit(bit, addr) Change bit and return old value * find_first_zero_bit(addr, nbits) Position first zero bit in *addr * find_first_bit(addr, nbits) Position first set bit in *addr * find_next_zero_bit(addr, nbits, bit) * Position next zero bit in *addr >= bit * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit * find_next_and_bit(addr1, addr2, nbits, bit) * Same as find_next_bit, but in * (*addr1 & *addr2) */
비트맵 카운트
bitmap_weight()
include/linux/bitmap.h
static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
{
if (small_const_nbits(nbits))
return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
return __bitmap_weight(src, nbits);
}
src 비트맵의 nbits 이내에서 1로 설정되어 있는 bit 수를 리턴한다.
__bitmap_weight()
lib/bitmap.c
int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
{
unsigned int k, lim = bits/BITS_PER_LONG;
int w = 0;
for (k = 0; k < lim; k++)
w += hweight_long(bitmap[k]);
if (bits % BITS_PER_LONG)
w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
return w;
}
EXPORT_SYMBOL(__bitmap_weight);
bitmap의 nbits 이내에서 1로 설정되어 있는 bit 수를 리턴한다.
할당할 연속된 공간 찾기
bitmap_find_next_zero_area()
include/linux/bitmap.h
/** * bitmap_find_next_zero_area - find a contiguous aligned zero area * @map: The address to base the search on * @size: The bitmap size in bits * @start: The bitnumber to start searching at * @nr: The number of zeroed bits we're looking for * @align_mask: Alignment mask for zero area * * The @align_mask should be one less than a power of 2; the effect is that * the bit offset of all zero areas this function finds is multiples of that * power of 2. A @align_mask of 0 means no alignment is required. */
static inline unsigned long
bitmap_find_next_zero_area(unsigned long *map,
unsigned long size,
unsigned long start,
unsigned int nr,
unsigned long align_mask)
{
return bitmap_find_next_zero_area_off(map, size, start, nr,
align_mask, 0);
}
bitmap에서 제한된 size 범위내에서 start 위치부터 align_mask 된 연속된 nr 갯수의 0 비트를 찾아 그 비트 위치를 반환한다. (based 0)
bitmap_find_next_zero_area_off()
lib/bitmap.c
/** * bitmap_find_next_zero_area_off - find a contiguous aligned zero area * @map: The address to base the search on * @size: The bitmap size in bits * @start: The bitnumber to start searching at * @nr: The number of zeroed bits we're looking for * @align_mask: Alignment mask for zero area * @align_offset: Alignment offset for zero area. * * The @align_mask should be one less than a power of 2; the effect is that * the bit offset of all zero areas this function finds plus @align_offset * is multiple of that power of 2. */
unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
unsigned long size,
unsigned long start,
unsigned int nr,
unsigned long align_mask,
unsigned long align_offset)
{
unsigned long index, end, i;
again:
index = find_next_zero_bit(map, size, start);
/* Align allocation */
index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
end = index + nr;
if (end > size)
return end;
i = find_next_bit(map, end, index);
if (i < end) {
start = i + 1;
goto again;
}
return index;
}
EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
bitmap에서 제한된 size 범위내에서 start 위치부터 align_mask 된 연속된 nr 갯수의 0 비트를 찾아 그 비트 위치를 반환한다. (based 0)
- bitmap_find_next_zero_area() 함수와 다르게 align_offset을 추가하여 align_mask로 정렬 시 align_offset을 더해 정렬한 후 다시 뺀다.
- cma_alloc() 함수에서 사용된다.
BITMAP_FIRST_WORD_MASK()
include/linux/bitmap.h
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
@start 이상의 비트들이 모두 1로 설정된 값에서, @start가 위치한 처음 워드(unsigned long)만을 반환한다.
예) 32비트 시스템에서 인수에 따른 결과는
- start = 0: 0xffff_ffff (0이 아님에 주의)
- start = 1: 0xffff_fffe
- start = 16: 0xffff_0000
- start = 32: 0xffff_ffff
- start = 40: 0xffff_ff00
예) 64비트 시스템에서 인수에 따른 결과는
- start = 0: 0xffff_ffff_ffff_ffff (0이 아님에 주의)
- start = 1: 0xffff_ffff_ffff_fffe
- start = 16: 0xffff_ffff_ffff_0000
- start = 32: 0xffff_ffff_0000_0000
- start = 40: 0xffff_ff00_0000_0000
- start = 66: 0xffff_ffff_ffff_fffc
BITMAP_LAST_WORD_MASK()
include/linux/bitmap.h
#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
@nbits 이하의 비트들이 모두 1로 설정된 값에서, @nbits가 위치한 마지막 워드(unsigned long)만을 반환한다.
예) 32비트 시스템에서 인수에 따른 결과는
- nbits = 0: 0xffff_ffff (0이 아님에 주의)
- nbits = 1: 0x0000_0001
- nbits = 16: 0x0000_ffff
- nbits = 32: 0xffff_ffff
- nbits = 40: 0x0000_000f
예) 64비트 시스템에서 인수에 따른 결과는
- nbits = 0: 0xffff_ffff_ffff_ffff (0이 아님에 주의)
- nbits = 1: 0x0000_0000_0000_0001
- nbits = 16: 0x0000_0000_0000_ffff
- nbits = 32: 0x0000_0000_ffff_ffff
- nbits = 40: 0x0000_00ff_ffff_ffff
- nbits = 66: 0x0000_0000_0000_0003
참고
- Bit operations | 문c
- Exclusive loads and store | 문c
- Barriers | 문c
- READ_ONCE() 및 WRITE_ONCE()와 lockless 리스트 | 문c
- Atomic Operation | 문c