[linux] find_first_zero_bit() 분석

 

 

find_first_zero_bit(unsigned long *addr, unsigned long size) 함수는 addr 부터 시작해서 size(size 의 단위는 byte 가 아니라, bit 단위이다) 만큼 검색하면서 첫번째 cleared bit 을 찾는 함수이다. 함수가 정의한 대로 사용하면 그만이지만, 그 안에서 어떻게 구현했는지 궁금해졌다.

 

이 함수는 다음 파일에서 config 에 따라 다음과 같이 정의된다. 즉  CONFIG_GENERIC_FIND_FIRST_BIT 이 정의되어 있는 경우 _find_first_zero_bit_le() 함수가 호출되고, 정의되어 있지 않으면, find_next_bit() 이 호출된다.

 

각각에 대해서 알아보자

 

<include/asm-generic/bitops/find.h>

#ifdef CONFIG_GENERIC_FIND_FIRST_BIT

extern unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size);

#else

#define find_first_bit(addr, size) find_next_bit((addr), (size), 0)

#endif

 

<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)

 

1. _find_first_zero_bit_le()

<linux/arch/arm/lib/findbit.S>

 

 20 /*

 21  * Purpose  : Find a 'zero' bit

 22  * Prototype: int find_first_zero_bit(void *addr, unsigned int maxbit);

 23  */

 24 ENTRY(_find_first_zero_bit_le)

 25         teq r1, #0

 26         beq 3f

 27         mov r2, #0

 28 1:

 29  ARM(       ldrb    r3, [r0, r2, lsr #3]    )

 30  THUMB(     lsr r3, r2, #3      )

 31  THUMB(     ldrb    r3, [r0, r3]        )

 32         eors    r3, r3, #0xff       @ invert bits

 33         bne .L_found        @ any now set - found zero bit

 34         add r2, r2, #8      @ next bit pointer

 35 2:      cmp r2, r1          @ any more?

 36         blo 1b

 37 3:      mov r0, r1          @ no free bits

 38         mov pc, lr

 39 ENDPROC(_find_first_zero_bit_le)

...

 

 

위에 보면 ARM() / THUMB() 으로 되어있는 부분이 있다. 이 부분은 ARM / THUMB 명령어에 따라서 다르게 정의되는 것이라고 생각하면 된다. 이에 대한 정의는 다음에서 찾아볼 수 있다. 즉 Config 에 따라서 둘중 하나만 컴파일 된다고 생각하면 된다.

 

<arch/arm/include/asm/unified.h>

#ifdef CONFIG_THUMB2_KERNEL

...

#define ARM(x...)

#define THUMB(x...) x

...

#else

...

#define ARM(x...)   x

#define THUMB(x...)

...

#endif

 

다시 _find_first_zero_bit 으로 돌아가서, 함수의 파라미터는 r0, r1 에 각각 대응되어 넘어오기 때문에, 실제 함수가 호출되었을 때의 인수가 저장되어있을 것이다. 즉, r0 에는 addr, r1 에는 maxbits 가 저장되어 있는 상태로 ENTRY(_find_first_zero_bit_le) 가 시작된다.

 

 25         teq r1, #0

 26         beq 3f

 27         mov r2, #0

 

teq : 두 32bit 값이 같은지 비교, 상태 플래그만 업데이트

beq : z flag 설정되어 있으면 branch

mov Rd, N : Rd = N

 

25~27: (r0: addr, r1: maxbits)

r1(size) 이 0 인지 비교해서 0 인 경우 3: 으로 점프한다. 즉 size 가 0 인 경우 리턴값에 0을 넣고 함수를 리턴한다. size 가 있는 경우 r2 레지스터에 0 을 저장한다.

 

 28 1:

 29  ARM(       ldrb    r3, [r0, r2, lsr #3]    )

 30  THUMB(     lsr r3, r2, #3      )

 31  THUMB(     ldrb    r3, [r0, r3]        )

 

ldrb Rd, [Rn, #Rm, shift #shift_num] : load byte

==> Rd = mem8[Rn + Rm shift L or R shift_num] : Rm 을 shift num 만큼 shift 한 값을 Rn 과 더한 주소의 값(byte )를 읽어서 Rd 에 넣음.

 

28~29: 

ldrb    r3, [r0, r2, lsr #3] : r3 에 r0 의 값을 base addr 로 하고, r2 의 값을 >> 3 한 값을 offset 으로 하는 값을 저장함. r2 에 현재 0 이 들어있기 때문에, r2 >> 3 의 값은 여전히 0, r0 에는 address 가 들어있기 때문에, [ ] 안의 최종값은 r0 의 값과 동일하다.

ldrb (load byte) 명령이기 때문에, r0 주소가 가리키는 곳의 1byte 를 r3 에 저장한다.

r2 >> 3 을 하는 것으로 보아 r2 는 bit offset 을 나타낸다는 것을 알 수 있다.

 

 32         eors    r3, r3, #0xff       @ invert bits

 33         bne .L_found        @ any now set - found zero bit

 34         add r2, r2, #8      @ next bit pointer

 35 2:      cmp r2, r1          @ any more?

 36         blo 1b

 

eors Rd, Rn, N : Rd = Rn ^ N  그리고 상태 레지스터 변경함.

bne : zero flag 가 set 되어 있지 않은 경우 branch

add Rd, Rn, N : Rd = Rn + N

cmp Rn, N : Rn - N 의 결과에 따라 상태 레지스터만 변경

blo 는 아래 참고

 

32~33:

r3 의 모든 bit 을 invert 하여 저장하고, 그 값이 0 이 아닌 경우 L_found 로 점프하고, 리턴한다. 즉 로드한 byte 의 값중에 하나라도 cleared bit 이 있는 경우(invert 가 0 이 아닌 조건) L_found 로 점프한다.

 

34~36:

r3 invert bit 값이 0 인 경우 r2 에 8 만큼 더하고, r1 값과 비교하여 r1 보다 적은 경우 레이블 1로 점프하도록 한다.

(즉 maxbits 에 도달할 때까지 8bit 씩 더해가면서 루프를 돈다)

 

 37 3:      mov r0, r1          @ no free bits

 38         mov pc, lr

 

mov Rd, Rn : Rd = Rn

 

37~38:

r1(maxbits) 를 r0(return value) 에 저장하고 리턴한다.

 

레이블 1로 점프하는 경우에 r2 의 값이 8씩 증가하기 때문에 r2 >> 3 을 하게 되면 실제 r0(addr) 에 1바이트씩 증가하게 되는 효과를 갖는다.

 

 

# 참고 blo instruction:

BLO is a synonym for BCC; it performs a conditional branch based on the carry © flag being clear in the PSR, which is the case when one unsigned value compares lower (LO) than another.

BCC 와 동일. PSR 의 Carry flag 에 따라서 조건부 분기를 수행한다. Carry flag 는 부호없는 수로 비교하여 다른 수보다 작은 경우에 발생한다. 즉 비교 결과 Carry flag 가 0 인 경우 BLO 조건을 만족하여 분기가 일어난다.

 

 

 

2. _fund_next_bit_le()

<arch/arm/lib/findbit.S>

 61 /*

 62  * Purpose  : Find a 'one' bit

 63  * Prototype: int find_first_bit(const unsigned long *addr, unsigned int maxbit);

 64  */

 65 ENTRY(_find_first_bit_le)

 66         teq r1, #0

 67         beq 3f

 68         mov r2, #0

 69 1:

 70  ARM(       ldrb    r3, [r0, r2, lsr #3]    )

 71  THUMB(     lsr r3, r2, #3      )

 72  THUMB(     ldrb    r3, [r0, r3]        )

 73         movs    r3, r3

 74         bne .L_found        @ any now set - found zero bit

 75         add r2, r2, #8      @ next bit pointer

 76 2:      cmp r2, r1          @ any more?

 77         blo 1b

 78 3:      mov r0, r1          @ no free bits

 79         mov pc, lr

 80 ENDPROC(_find_first_bit_le)

 81

 82 /*

 83  * Purpose  : Find next 'one' bit

 84  * Prototype: int find_next_zero_bit(void *addr, unsigned int maxbit, int offset)

 85  */

 86 ENTRY(_find_next_bit_le)

 87         teq r1, #0

 88         beq 3b

 89         ands    ip, r2, #7

 90         beq 1b          @ If new byte, goto old routine

 91  ARM(       ldrb    r3, [r0, r2, lsr #3]    )

 92  THUMB(     lsr r3, r2, #3      )

 93  THUMB(     ldrb    r3, [r0, r3]        )

 94         movs    r3, r3, lsr ip      @ shift off unused bits

 95         bne .L_found

 96         orr r2, r2, #7      @ if zero, then no bits here

 97         add r2, r2, #1      @ align bit pointer

 98         b   2b          @ loop for next bit

 99 ENDPROC(_find_next_bit_le)

 

r0 에는 addr, r1 에는 maxbit, r2 에는 offset 이 저장되어 있다.

 

위 코드도 유사하게 분석할 수 있다. 여기서 분석은 생략한다~ (귀찮음 ㅠ)

 

다음은 L_found 루틴이다. L_found 루틴으로 점프할 때, r0 에는 addr, r1 에는 size(max bits), r2 에는 bitoffset, r3 에는 r0 + (r2 >> 3) 주소에 저장된 값의 invert 된 값이 들어 있다.

 

172 /*

173  * One or more bits in the LSB of r3 are assumed to be set.

174  */

175 .L_found:

176 #if __LINUX_ARM_ARCH__ >= 5

177         rsb r0, r3, #0

178         and r3, r3, r0

179         clz r3, r3

180         rsb r3, r3, #31

181         add r0, r2, r3

182 #else

...

192 #endif

193         cmp r1, r0          @ Clamp to maxbit

194         movlo   r0, r1

95         mov pc, lr

 

rsb Rd, Rn, N : Rd = N - Rn (reverse substract, cf) SUB Rd, Rn, N : Rd = Rn - N)

and Rd, Rn, N : Rd = Rn & N

clz Rd, Rn : Rd = count leading zero (1이 세팅된 곳까지 0의 개수를 센다)

cmp Rn, N : Rn - N 에 따른 상태 플래그 변경

movlo Rn, N : 상태플래그 C 가 0 인 경우(이전 연산으로 carriage 가 발생하지 않음.)

 

177-179

r0 에 r3 의 값을 반전시킨 값을 넣는다. (r0 = 0 - r3)

반전시킨 r0 와 원래 값 r3 를 and 시키면, 원래 값중 1이 처음 나타나는 곳의 값을 넘긴다.(하위bit로 부터 시작)

즉 원래 값이 01011000 인 경우 177/178 라인을 거치고 나면 r3 에 00001000 값이 저장된다.

179 라인에서 1이 세팅된 곳까지의 leading zero 를 count 한다. 위의 예(00001000)에서는 r3 값에 4가 저장된다.

 

180-181

그 값을 다시 rsb r3, r3, #31 명령을 수행하게 되면, 31 - r3(4) = 27 즉 r3 에 27 이 저장된다. 이 값은 LSB(least significnat bit) 으로부터 떨어진 bit offset 을 나타낸다. 최초 r3 의 값이 원래값의 invert 값이기 때문에 27 이란 값은 0인 bit 의 LSB 로부터의 bit offset 을 나타낸다.

181 문에서 r0 에 최초 파라미터로 들어온 r2(bit offset) 과 찾은 clear bit offset (r3) 를 더해서 r0 에 넣는다.

 

193-195

찾은 bit offset (r0) 와 max bits 인 (r1) 을 비교해서 r1 이 큰 경우, (cmp r1, r0) 즉 r0 가 찾으려는 범위 내에 있는 경우는 바로 return 하고, r0 가 찾으려는 범위를 넘는 경우에는 max bit offset 인 r1 을 r0 에 넣고 리턴한다.

(주의, cmp r1, r0 에서 r1 > r0 인 경우 carry flag 가 set 된다. lo 는 carry flag 가 clear 인 경우에만 실행한다)