Bitmap Operations

 기능

  • 비트맵은 대략적으로 하나의 unsigned long 타입이다.
    • 비트 수가 하나의 unsigned long 데이터 타입을 넘어가는 경우 unsigned long 배열로 관리된다.
  • nbits는 항상 컴파일 시 상수로 평가되어야 한다. 그렇지 않고 변수로 평가되는 경우 많은 inline으로 인해 코드 크기가 매우 커진다.
  • nbits가 1개의 unsigned long 데이터 타입으로 취급할 수 있는 경우와 그렇지 않은 경우의 구현 루틴이 나뉘어 있다.
    • 1개의 unsigned long 데이터로 처리하는 경우 보통 한 번의 조작 루틴을 사용하여 빠른 처리가 가능하다.
    • 여러 개의 unsigned long 데이터로 처리하는 경우 다량의 데이터 처리를 하느라 느리다.

include/linux/bitmap.h

/*
 * The available bitmap operations and their rough meaning in the
 * case that the bitmap is a single unsigned long are thus:
 *
 * Note that nbits should be always a compile time evaluable constant.
 * Otherwise many inlines will generate horrible code.
 *
 * 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_zero()

  • 목적 데이터의 각 비트를 0으로 초기화한다.
    • dst: 목적 데이터
    • nbits: 처리할 비트 수
    • small_const_nbits()를 호출하여 CPU가 한 번의 operation으로 처리할 수 있는지 여부를 판단하여
      • 처리할 수 있으면 한 번의 명령으로 목적 데이터에 0을 대입
      • 처리할 수 없으면 memset()으로 필요한 길이를 구해서 처리
        • CPU가 32비트: 길이는 4의 배수(4, 8, 12, …)
        • CPU가 64비트: 길이는 8의 배수(8, 16, 24, …)
static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
{
        if (small_const_nbits(nbits))
                *dst = 0UL;
        else {
                unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
                memset(dst, 0, len);
        }
}

 

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)
#ifdef CONFIG_64BIT
#define BITS_PER_LONG 64
#else
#define BITS_PER_LONG 32
#endif /* CONFIG_64BIT */

 

어셈블리를 사용하는 비트맵 함수 들

  • 아래 함수들은 어셈블리로 구현된 비트맵 함수이다.
    • 상위 6개의 비트맵 조작 함수는 atomic 하게 처리하도록 구현되어 있다.
    • 하위 4개의 비트맵 검색용 함수는 CPU 아키텍처의 엔디안에 맞게 처리루틴이 구분되어 있다.

include/linux/bitmap.h

/*
 * 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
 */

 

  set_bit()

  • set_bit() 함수는 지정된 비트를 atomic 하게 enable 조작한다.
  • 이 함수는 generic 표준에서도 제공하지만 ARM 아키텍처에서는 아래와 같은 매크로를 통해서 제공한다.

arch/arm/include/asm/bitops.h

#define set_bit(nr,p)                   ATOMIC_BITOP(set_bit,nr,p)

#ifndef CONFIG_SMP
/*
 * The __* form of bitops are non-atomic and may be reordered.
 */
#define ATOMIC_BITOP(name,nr,p)                 \
        (__builtin_constant_p(nr) ? ____atomic_##name(nr, p) : _##name(nr,p))
#else
#define ATOMIC_BITOP(name,nr,p)         _##name(nr,p)
#endif

 

  • SMP에서는 아래의 루틴도 호출된다.
static inline void ____atomic_set_bit(unsigned int bit, volatile unsigned long *p)
{
        unsigned long flags;
        unsigned long mask = 1UL << (bit & 31);

        p += bit >> 5;

        raw_local_irq_save(flags);
        *p |= mask;
        raw_local_irq_restore(flags);
}

 

  • bitop 매크로를 사용하여 _set_bit에 대한 함수를 정의한다.

arch/arm/lib/setbit.S

bitop   _set_bit, orr


  • bitop에 대한 매크로이다.

arch/arm/lib/bitops.h

#if __LINUX_ARM_ARCH__ >= 6
        .macro  bitop, name, instr
ENTRY(  \name           )
UNWIND( .fnstart        )
        ands    ip, r1, #3
        strneb  r1, [ip]                @ assert word-aligned
        mov     r2, #1
        and     r3, r0, #31             @ Get bit offset
        mov     r0, r0, lsr #5
        add     r1, r1, r0, lsl #2      @ Get word offset
#if __LINUX_ARM_ARCH__ >= 7 && defined(CONFIG_SMP)
        .arch_extension mp
        ALT_SMP(W(pldw) [r1])
        ALT_UP(W(nop))
#endif
        mov     r3, r2, lsl r3
1:      ldrex   r2, [r1]
        \instr  r2, r2, r3
        strex   r0, r2, [r1]
        cmp     r0, #0
        bne     1b
        bx      lr
UNWIND( .fnend          )
ENDPROC(\name           )
        .endm

 

  • 아래는 set_bit() 함수에 대한 generic 표준이며 ARM에서는 사용하지 않으므로 참고만 하기로 한다.

include/asm-generic/bitops/atomic.h

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);
        unsigned long flags;

        _atomic_spin_lock_irqsave(p, flags);
        *p  |= mask;
        _atomic_spin_unlock_irqrestore(p, flags);
}

 

find_first_zero_bit()

arch/arm/include/asm/bitops.h

#ifndef __ARMEB__
#define find_first_zero_bit(p,sz)       _find_first_zero_bit_le(p,sz)
#else
#define find_first_zero_bit(p,sz)       _find_first_zero_bit_be(p,sz)
#endif
  • fls()가 find_first_zero_bit()와 세 가지 다른 점
    • 처리되는 데이터 타입이 다르다.
      • fls()는 unsigned int 타입에서 동작한다.
      • find_last_zero_bit()는 비트 제한이 없는 비트맵에서 동작한다.
    • 검색 비트 종류(set(1) bit / clear(0))
      • fls()는 set(1) bit를 검색한다.
      • find_first_zero_bit는 clear(0) bit를 검색한다.
    • 리턴되는 포지션 값
      • fls()는 bit0을 검색하면 1로 리턴한다. 검색되지 않으면 0을 리턴한다.
      • find_last_zero_bit는 bit0을 검색하면 0으로 리턴한다. 검색되지 않으면 max_bits 값을 리턴한다.
  • 이 매크로는 엔디안에 따라 구현 루틴이 다르다.

bitops-4a

_find_first_zero_bit_le()

arch/arm/lib/findbit.S

/*
 * Purpose  : Find a 'zero' bit
 * Prototype: int find_first_zero_bit(void *addr, unsigned int maxbit);
 */
ENTRY(_find_first_zero_bit_le)
                teq     r1, #0  
                beq     3f
                mov     r2, #0
1:
 ARM(           ldrb    r3, [r0, r2, lsr #3]    )
 THUMB(         lsr     r3, r2, #3              )
 THUMB(         ldrb    r3, [r0, r3]            ) 
                eors    r3, r3, #0xff           @ invert bits
                bne     .L_found                @ any now set - found zero bit
                add     r2, r2, #8              @ next bit pointer
2:              cmp     r2, r1                  @ any more?
                blo     1b
3:              mov     r0, r1                  @ no free bits
                ret     lr
ENDPROC(_find_first_zero_bit_le)
  • 레지스터 용도
    • r0(addr): 비트맵이 위치한 주소
    • r1(maxbit): maxbit로 처리할 최대 비트 수
    • r0(결과): clear(0) bit를 찾은 비트 번호를 리턴
      • 0~n: 첫 번째 비트가 clear bit.
      • maxbit: 비트맵 범위내에서 찾지 못함(not found).
    • r2(currbit): 현재 검색하고 있는 비트
      • 다음 바이트를 검색할 때마다 8비트씩 증가
    • r3(8bit 비트맵): 읽어들인 1바이트(8비트) 비트맵
  • 비트맵에서 1 바이트(8비트) 단위로 읽어와서 clear(0) 비트가 있는지 검사하여 있으면 .L_found 레이블로 이동한다.
  • teq     r1, #0
    • 처리할 비트가 없으며(maxbit가 0이면) r0←0(error)를 리턴
  • mov      r2, #0
    • currbit를 0으로 대입(처음 시작 비트)
  • 1: ldrb    r3, [r0, r2, lsr #3]
    • r3에 비트맵 주소 + currbit / 8을 하여 1바이트를 읽어온다.
  • eors    r3, r3, #0xff
    • 읽어들인 데이터를 반전(invert) 시킨다.
  • bne     .L_found
    • 즉, 읽어들인 8비트 비트맵에 clear(bit)가 존재하면 .L_found로 이동
  • add     r3, r3, #8
    • currbit += 8
      • 다음 바이트로 이동
  • cmp r2, r1
    • 아직 끝나지 않았으면(curbit < maxbit) 1b로 이동
  • #3: mov r0, r1
    • r0 ← r1(maxbit) 값을 리턴(not found)
/*
 * One or more bits in the LSB of r3 are assumed to be set.
 */
.L_found:
                rsb     r0, r3, #0
                and     r3, r3, r0
                clz     r3, r3
                rsb     r3, r3, #31
                add     r0, r2, r3

                cmp     r1, r0                  @ Clamp to maxbit
                movlo   r0, r1
                ret     lr
  • rsb     r0, r3, #0
    • r0 = -r3
  • and     r3, r3, r0
    • r3 &= r0
    • 위의 rsb, and 명령은 r3 &= -r3와 동일한 연산이고 이렇게 하면 set(bit)가 lsb 쪽에 하나만 남게된다.

bitops-5

  • clz     r3, r3
    • 시작 비트만 남겨놨으니 그 앞쪽에 있는 0 bit를 카운트한다.
    • counter leading zero로 bit31부터 시작해서 set(1) bit가 발견되기 전까지의 clear(0) bit 수를 카운트 한다.
      • clz(0x90) -> 24
      • clz(0x7777_7777) -> 1
  • rsb     r3, r3, #31
    • 31 – r3(0 비트 갯수)
  • add     r0, r2, r3
    • r0 ← r2(curbit) + r3(바이트 내에서 찾은 위치)
  • movlo   r0, r1
    • 범위를 벗어난 위치에서 비트가 발견되면r0 ← maxbit(not found)를 리턴
    • r1(maxbit> < r0(찾은 위치)

 

find_first_bit()

arch/arm/include/asm/bitops.h

#define find_first_bit(p,sz)            _find_first_bit_le(p,sz)

비트맵에서 비트 값이 1인 가장 처음 발견되는 비트 번호를 알아온다. (based 0) 구현은 엔디안에 따라 두 개로 나뉘어 있다.

  • 예) *addr[]=0x8800_0000_0000_0000, size=64 -> 59
  • 예) *addr[]=0x0000_0011, size=32 -> 0

 

/*
 * Purpose  : Find a 'one' bit
 * Prototype: int find_first_bit(const unsigned long *addr, unsigned int maxbit);
 */
ENTRY(_find_first_bit_le)
                teq     r1, #0  
                beq     3f
                mov     r2, #0
1:
 ARM(           ldrb    r3, [r0, r2, lsr #3]    )
 THUMB(         lsr     r3, r2, #3              )
 THUMB(         ldrb    r3, [r0, r3]            )
                movs    r3, r3
                bne     .L_found                @ any now set - found zero bit
                add     r2, r2, #8              @ next bit pointer
2:              cmp     r2, r1                  @ any more?
                blo     1b
3:              mov     r0, r1                  @ no free bits
                ret     lr
ENDPROC(_find_first_bit_le)
  • 레지스터 용도
    • r0(addr): 비트맵이 위치한 주소
    • r1(maxbit): maxbit로 처리할 최대 비트 수
    • r0(결과): clear(0) bit를 찾은 비트 번호를 리턴
      • 0~n: set bit가 발견된 비트 위치.
      • maxbit: 비트맵 범위내에서 찾지 못함(not found).
    • r2(currbit): 현재 검색하고 있는 비트(0, 8, 16, 24, …)
      • 다음 바이트를 검색할 때마다 8비트씩 증가
    • r3(8bit 비트맵): 읽어들인 1바이트(8비트) 비트맵

비트맵에서 1 바이트(8비트) 단위로 읽어와서 clear(0) 비트가 있는지 검사하여 있으면 .L_found 레이블로 이동한다.

  • teq     r1, #0
    • 처리할 비트가 없으며(maxbit가 0이면) r0←0(error)를 리턴
  • mov      r2, #0
    • currbit를 0으로 대입(처음 시작 비트)
  • 1: ldrb    r3, [r0, r2, lsr #3]
    • r3에 비트맵 주소 + currbit / 8을 하여 1바이트를 읽어온다.
  • bne     .L_found
    • 즉, 읽어들인 8비트 비트맵에 set bit가 존재하면 .L_found로 이동
  • add     r3, r3, #8
    • currbit += 8
      • 다음 바이트로 이동
  • cmp r2, r1
    • 아직 끝나지 않았으면(curbit < maxbit) 1b로 이동
  • 3: mov r0, r1
    • r0 ← r1(maxbit) 값을 리턴(not found)
  • .L_found는 _find_first_zero_bit_le()에서 사용한 루틴과 동일하다.
  • 예) byte *addr[] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x88}, size=64
    • -> 59
  • 예) byte *addr[] = {0x11, 0x00, 0x00, 0x00}, size=32
    • -> 0

 

find_last_bit()

lib/find_last_bit.c

/**     
 * find_last_bit - find the last set bit in a memory region
 * @addr: The address to start the search at
 * @size: The maximum size to search
 *       
 * Returns the bit number of the first set bit, or size.
 */ 
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
        unsigned long words;
        unsigned long tmp;

        /* Start at final word. */
        words = size / BITS_PER_LONG;

        /* Partial final word? */
        if (size & (BITS_PER_LONG-1)) {
                tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
                                         - (size & (BITS_PER_LONG-1)))));
                if (tmp)
                        goto found;
        }

        while (words) {
                tmp = addr[--words];
                if (tmp) {
found:
                        return words * BITS_PER_LONG + __fls(tmp);
                }
        }

        /* Not found */
        return size; 
}                                  
EXPORT_SYMBOL(find_last_bit);

비트맵에서 가장 마지막 비트가 1인 비트 번호를 알아온다. (based 0)

  • 예) *addr[]=0x8800_0000_0000_0000, size=64 -> 63
  • 예) *addr[]=0x0000_0001, size=32 -> 0

 

  • words = size / BITS_PER_LONG;
    • 온전한 long 워드 수
  • if (size & (BITS_PER_LONG-1)) {
    • size가 partial long인 경우
  • tmp = (addr[words] & (~0UL >> (BITS_PER_LONG – (size & (BITS_PER_LONG-1)))));
    • tmp에 마지막 long 워드의 남은 비트들만 추출
  • if (tmp) goto found;
    • tmp 값이 있는 경우 found로 이동한다.
  • while (words) {
    • tmp 값을 long 워드 수만큼 루프를 돈다.
  • tmp = addr[–words];
    • tmp에 words를 1감소 시킨 인덱스의 long 워드 값을 담는다.
  • found: return words * BITS_PER_LONG + __fls(tmp);
    • 마지막 비트가 1인 비트 번호를 리턴한다.
      • 예) 0x8000_0000 -> 31
      • 예) 0x0000_0001 -> 0

 

비트맵 카운트

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 수를 리턴한다.

 

hweight_long()

include/linux/bitops.h

static inline unsigned long hweight_long(unsigned long w)
{
        return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
}

long 타입 w에 대해 1로 설정되어 있는 bit 수를 리턴한다.

 

hweight**()

include/asm-generic/bitops/const_hweight.h

/*
 * Generic interface.
 */
#define hweight8(w) (__builtin_constant_p(w) ? __const_hweight8(w) : __arch_hweight8(w))
#define hweight16(w) (__builtin_constant_p(w) ? __const_hweight16(w) : __arch_hweight16(w))
#define hweight32(w) (__builtin_constant_p(w) ? __const_hweight32(w) : __arch_hweight32(w))
#define hweight64(w) (__builtin_constant_p(w) ? __const_hweight64(w) : __arch_hweight64(w))

1로 설정되어 있는 bit 수를 리턴한다.

 

__const_hweight**()

include/asm-generic/bitops/const_hweight.h

/*
 * Compile time versions of __arch_hweightN()
 */
#define __const_hweight8(w)             \
        ((unsigned int)                 \
         ((!!((w) & (1ULL << 0))) +     \
          (!!((w) & (1ULL << 1))) +     \
          (!!((w) & (1ULL << 2))) +     \
          (!!((w) & (1ULL << 3))) +     \
          (!!((w) & (1ULL << 4))) +     \
          (!!((w) & (1ULL << 5))) +     \
          (!!((w) & (1ULL << 6))) +     \
          (!!((w) & (1ULL << 7)))))
 
#define __const_hweight16(w) (__const_hweight8(w)  + __const_hweight8((w)  >> 8 ))
#define __const_hweight32(w) (__const_hweight16(w) + __const_hweight16((w) >> 16))
#define __const_hweight64(w) (__const_hweight32(w) + __const_hweight32((w) >> 32))

1로 설정되어 있는 bit 수를 리턴한다.

 

__arch_hweight**()

include/asm-generic/bitops/arch_hweight.h

static inline unsigned int __arch_hweight32(unsigned int w)
{
        return __sw_hweight32(w);
}

static inline unsigned int __arch_hweight16(unsigned int w)
{
        return __sw_hweight16(w);
}

static inline unsigned int __arch_hweight8(unsigned int w)
{
        return __sw_hweight8(w);
}

static inline unsigned long __arch_hweight64(__u64 w)
{
        return __sw_hweight64(w);
}

 

__sw_hweight32()

lib/hweight.c

/**
 * hweightN - returns the hamming weight of a N-bit word
 * @x: the word to weigh
 *
 * The Hamming Weight of a number is the total number of bits set in it.
 */

unsigned int __sw_hweight32(unsigned int w)
{       
#ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
        w -= (w >> 1) & 0x55555555;
        w =  (w & 0x33333333) + ((w >> 2) & 0x33333333);
        w =  (w + (w >> 4)) & 0x0f0f0f0f;
        return (w * 0x01010101) >> 24;
#else
        unsigned int res = w - ((w >> 1) & 0x55555555);
        res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
        res = (res + (res >> 4)) & 0x0F0F0F0F;
        res = res + (res >> 8);
        return (res + (res >> 16)) & 0x000000FF;
#endif
}
EXPORT_SYMBOL(__sw_hweight32);

 

__sw_hweight16()

lib/hweight.c

unsigned int __sw_hweight16(unsigned int w)
{
        unsigned int res = w - ((w >> 1) & 0x5555);
        res = (res & 0x3333) + ((res >> 2) & 0x3333);
        res = (res + (res >> 4)) & 0x0F0F;
        return (res + (res >> 8)) & 0x00FF;
}
EXPORT_SYMBOL(__sw_hweight16);

 

__sw_hweight8()

lib/hweight.c

unsigned int __sw_hweight8(unsigned int w)
{
        unsigned int res = w - ((w >> 1) & 0x55);
        res = (res & 0x33) + ((res >> 2) & 0x33);
        return (res + (res >> 4)) & 0x0F;
}
EXPORT_SYMBOL(__sw_hweight8);

 

__sw_hweight64()

lib/hweight.c

unsigned long __sw_hweight64(__u64 w)
{
#if BITS_PER_LONG == 32
        return __sw_hweight32((unsigned int)(w >> 32)) +
               __sw_hweight32((unsigned int)w);
#elif BITS_PER_LONG == 64
#ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
        w -= (w >> 1) & 0x5555555555555555ul;
        w =  (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
        w =  (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
        return (w * 0x0101010101010101ul) >> 56;
#else
        __u64 res = w - ((w >> 1) & 0x5555555555555555ul);
        res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
        res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
        res = res + (res >> 8);
        res = res + (res >> 16);
        return (res + (res >> 32)) & 0x00000000000000FFul;
#endif
#endif
}
EXPORT_SYMBOL(__sw_hweight64);

 

__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/bitops.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
#define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

 

참고

답글 남기기

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