Bitmap Operations

<kernel v5.0>

Bitmap Operations

  • 비트맵은 대략적으로 하나의 unsigned long 타입이다.
    • 비트 수가 하나의 unsigned long 데이터 타입을 넘어가는 경우 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

 

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)  as above
 *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
 *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
 *  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
 *
 * 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);
}

비트맵 데이터의 각 비트를 0으로 초기화한다.

 

small_const_nbits()

CPU 아키텍처가 한 번의 operation으로 비트맵을 처리할 수 있는지 여부를 판단한다.

  • 먼저 __builtin_constant_p()를 사용하여 인수가 상수(변수가 아닌)인지를 알아낸다.
    • 인수가 상수인 경우 true를 리턴하고,
    • 변수인 경우는 무조건 false를 리턴한다.
      • BITS_PER_LONG(32 or 64) 값 보다 작거나 같은 경우 true
#define small_const_nbits(nbits) \
        (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

 

BITS_PER_LONG
#ifdef CONFIG_64BIT
#define BITS_PER_LONG 64
#else
#define BITS_PER_LONG 32
#endif /* CONFIG_64BIT */

 

Atomic 비트맵 함수 들

아래는 bitmap에서 사용할 수 있는 bitops 함수들이다.

  • 상위 7개의 비트맵 조작 함수는 atomic 하게 처리하도록 구현되어 있다.
  • 하위 4개의 비트맵 검색용 함수는 CPU 아키텍처의 엔디안에 맞게 처리루틴이 구분되어 있다.
  • 참고: Bit Operations | 문c
/**
 * 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() 함수에서 사용된다.

 

기타

DECLARE_BITMAP & BITMAP_LAST_WORD_MASK()

  • 다음은 비트맵 선언매크로와 비트맵의 마지막 워드부분을 마스크하는 매크로이다.

include/linux/bitmap.h

#define DECLARE_BITMAP(name,bits) \
        unsigned long name[BITS_TO_LONGS(bits)]

#define BITMAP_LAST_WORD_MASK(nbits)                                    \
(                                                                       \
        ((nbits) % BITS_PER_LONG) ?                                     \
                (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL               \
)

그 외 비트 관련 매크로

include/linux/bits.h

#define BIT(nr)                 (1UL << (nr))
#define BIT_ULL(nr)             (1ULL << (nr))
#define BIT_MASK(nr)            (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
#define BIT_ULL_MASK(nr)        (1ULL << ((nr) % BITS_PER_LONG_LONG))
#define BIT_ULL_WORD(nr)        ((nr) / BITS_PER_LONG_LONG)
#define BITS_PER_BYTE           8

 

참고

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다