스택 탐색을 통한 백트레이스 구현

출처: 열씨미와 게을러의 리눅스 개발 노하우 탐험기
2009/08/17 - [Programming] - diff, find, md5sum, patch
2009/08/17 - [Programming] - find, grep, ctags, cscope, global
2009/08/17 - [Programming] - shared library, strace, ldconfig, ldd, gcc, strings, od, nm, c++filt, readelf
2009/09/14 - [Programming] - configure
2009/09/21 - [Programming] - 자동화된 빌드 시스템 구축
2009/09/21 - [Programming] - 자동화된 빌드 시스템 구축 (2)
2009/09/21 - [Programming] - 숨겨진 1인치의 의존성을 찾아서 - make
2009/09/22 - [Programming] - 메모리 디버깅을 위한 친구
2009/09/22 - [Programming] - 프로그램을 동적으로 추적하는 도구
2009/09/23 - [Programming] - 스택 탐색을 통한 디버깅

glibc로 백트레이스 구현하기
backtrace1.c

glibc에는 백트레이스를 추적하도록 지원하는 함수 3개가 존재(execinfo.h)

1. int backtrace(void** buffer, int size)
• 현재 thread에 대한 backtrace를 pointer list로 얻어 buffer에 저장
• size: buffer를 채우는 void* 항목의 최대 개수
  
• return: buffer에 채운 실제 항목 개수
  
• buffer에 채워진 pointer는 stack을 검사해서 얻은 return address
  
• stack frame당 return address 하나씩 할당
  
2. char** backtrace_symbols(void* const* buffer, int size)
• backtrace 함수에서 얻은 정보를 해석해서 string array로 변환
  
• buffer: backtrace function에서 얻은 address array를 가리키는 pointer
  
• size: backtrace return value
  
• return: string array를 가리키는 pointer. 각 string은 buffer 해당 항목에 대응하는 사람이 인식할 수 있는 stack frame information, 함수 변위, 16진수 실제 return address
  
• 내부 memory allocation에 malloc을 사용하므로, 반드시 free를 사용해서 명시적으로 return value에 대한 memory를 해제해야 함
  
• ELF를 사용할 경우에만 함수 이름과 변위를 얻을 수 있으며, linker에게 추가적인 flag를 넘겨서 link 과정에서 함수 이름을 결정해야 함. 이 때 필요한 -rdynamic option에 대한 설명은 나중의 항목을 참조
  
3. void backtrace_symbols_fd(void* const* buffer, int size, int fd)
• backtrace_symbols와 동일한 작용을 하지만, 결과를 행 단위로 file에 기록
  
• 내부적으로 malloc을 사용하지 않아 memory 문제 없음

backtrace_main1.c

-rdynamic option: linker에게 symbol address를 name으로 사상하라고 지시. kernel의 ksymoops에서 symbol 사상을 처리하는 작업과 유사

실행 결과를 보면  main -> baz -> boo -> bar -> foo -> print_gnu_backtrace로 이어지는 호출 체인이 드러난다. debugging 정보를 사용하지 않기 때문에 file name과 line number 대신 해당 function entry point를 기준으로 변위를 출력한다.
최적화 option을 붙이는 경우 backtrace function이 오동작할 가능성도 있고, frame pointer 삭제 option을 붙여서 compile하면 아예 동작을 안하며, glibc가 없는 환경에서는 사용할 수 없다는 단점이 있다.

gcc로 백트레이스 구현하기
backtrace2.c

GNU gcc에는 백트레이스를 추적하도록 간접으로 지원하는 함수가 존재

1. void* __builtin_frame_address(unsigned int level)
   
• level: 0인 경우 current function frame address를, 1인 경우 current function을 호출한 function frame address를 반환
  
• return: function frame address
  
• frame은 auto variable과 register를 저장한 stack area이고 일반적으로 frame address는 function이 stack에 쌓아올린 첫 번째 word의 address
  
2. void* __builtin_return_address(unsigned int level)
   
• level: 호출 스택을 찾기 위한 frame number. 0인 경우 current function address, 1인 경우 current function을 호출한 function address를 반환
  
• return: function address

x86에서는 %ebp register가 stack frame을 가리키는 pointer가 되므로, inline assembly를 사용해 직접 %ebp register의 값을 구하거나 gcc 확장 함수인 __builtin_frame_address를 사용해서 간접적으로 stack frame address를 얻어야 한다. 일단 stack frame address를 얻어왔으면 다음 stack frame area가 가리키는 ebp와 해당 stack frame에 대응되는 function address를 가리키는 ret를 member로 지정한 layout structure를 활용해서 호출 체인을 계속 추적할 수 있다.

backtrace_main2.c

__builtin_frame_address는 단순히 주소만 반환하므로 출력 결과도 주소만 있다. 함수 이름, 행과 같은 정보를 얻으려면 debugging 정보를 사용해서 후 가공이 필요한데, BFD(Binary File Descriptor)를 사용해서 object file 정보를 얻어야 한다.
이 방법을 사용하는 경우 inline function을 사용하면 오동작할 가능성이 있고, frame pointer 삭제 option을 붙여서 compile을 하면 아예 동작을 하지 않는다. 그러나 glibc가 없어도 다양한 운영체제에서 동작한다는 장점이 있다.

C programming 언어만으로 백트레이스 구현하기
glibc와 gcc에 의존하지 않고 %ebp를 구하는 편법이 있으나, 16진수 주소가 아니라 함수 이름을 출력하려면 여전히 glibc의 도움을 받아야 한다.

backtrace3.c

getEBP

1. x86 환경에서 %ebp를 구하는 편법을 보여주는 함수
   
• 매개변수 dummy 주소를 얻어서 2만큼 음수 변위를 주면 바로 %ebp 값이 된다는 사실을 이용
  
2. print_walk_through
   
• getEBP를 사용해 %ebp를 얻은 다음 변위 1을 더해서 함수 주소를 획득하고(앞의 backtrace2.c의 struct layout structure 참조), 계속해서 %ebp의 내용을 추적해 다음 stack frame으로 이동
  
• gcc의 __builtin_frame-address나 inline assembly를 사용하지 않고서도 %ebp를 구할 수 있다는 점이 장점
  
• platform마다 차이가 나는 ABI를 참조해서 구현해야 하므로 호환성이 떨어진다는 점이 단점
  
• C compiler의 특성도 타는 듯 보이는데, Fedora 일부 배포판의 gcc를 사용하는 경우 getEBP 함수 내부에서 무의미한 printf 출력 코드를 하나 넣어야 제대로 %ebp 값을 읽어올 수 있음(주석 처리한 printf 참고).

함수 이름을 얻기 위해 dladdr 함수를 사용
dlfcn.h 헤더파일 선언 전에 __GNU_SOURCE macro를 정의해야 한다.
dladdr(3) 함수는 dynamic library linker loader를 위한 dl library에 속해 있으며, 함수 pointer를 얻어 해당 함수에 대한 정보(파일 이름, 적재 주소)를 Dl_info structure에 넣는다. 여기서 dladdr 함수를 제고하고 다음과 같이 작성하면 backtrace2.c와 동일한 기능을 하게 된다.

backtrace4.c

backtrace_main3.c

-ldl option: dynamic library dl API를 사용

dummy란 매개 변수를 두어 이것을 기준으로 stack frame address를 구한다.
x86 전용이므로, 다른 platform에서는 동작하지 않는다.

기타
backtrace2 예제의 BFD는 addr2line을 이용해 별도 programming 없이 함수 정보를 얻을 수 있다.

addr2line -e [executable file] -f [function address]

시작 코드(_start)와 같은 library 내부 코드 정보는 제대로 보이지 않지만 foo, bar, boo, baz, main으로 이어지는 호출 체인 정보가 제대로 나오는 것을 볼 수 있다. 단 Max OS X와 같이 BFD가 제대로 구현되지 않은 platform의 경우 이 방법을 쓰기 어렵다.

x86_64의 경우

x86_64는 함수 인자를 레지스터에서 가져와 프레임 포인터 바로 위 스택에 푸시한다. 따라서 이 인수 주소를 가져와 1을 더하면 직전 프레임 포인터를 얻는다. 여기에 한 가지 주의 사항이 있는데, getRBP를 사용해서 얻은 RBP를 함수 반환 주소와 함께 저장해야 한다. printf와 dladdr 호출이 스택 맨 위 값을 덮어쓰기 때문이다.

-fomit-frame-pointer / -fno-omit-frame-pointer option

최적화 컴파일러 중 stack frame 정보를 담는 register를 아껴 다른 최적화 목적으로 전용하는 경우가 있는데 이럴 경우 stack 영역을 추적할 방법이 없다. 하지만 gdb와 같은 debugger는 -fomit-frame-pointer로 frame pointer를 제거해도 debugging 정보만으로 휴리스틱을 적용해 stack 영역을 제대로 백트레이스 하기도 한다. 만일 stack 정보를 program 내부에서 처리해야 한다면 반드시 -fno-omit-frame-pointer option으로 ebp 값을 제대로 얻어오게 해야 한다.

결론

1. glibc는 backtrace function을 제공
2. gcc는 stack frame information을 얻는 built in function을 제공
3. stack 구조를 제대로 파악한다면 C programming language만으로 backtrace를 구현 가능. 하지만 platform 별로 방식은 다르다
4. glibc는 dynamic library 관련 정보를 추출하는 dl 계열 함수를 제공
5. libc와 gcc를 사용해서 symbol information을 얻으려면 runtime linker에 의존해야 한다
6. BFD를 사용하는 addr2line 명령으로 함수 주소를 함수 이름으로 변환 가능
7. -fomit-frame-pointer option을 compiler에 넘기면 stack frame 관련 정보를 삭제해서 backtrace 불가능. 이 경우 -fno-omit-frame-pointer option을 고려

참고
backtrace 관련 GNU manual: http://www.gnu.org/software/libc/manual/html_node/Backtraces.html
function frame address 관련 GNU manual: http://gcc.gnu.org/onlinedocs/gcc-3.3.1/gcc/Return-Address.html
BFD: http://en.wikipedia.org/wiki/Binary_File_Descriptor
dladdr manual page: http://linux.die.net/man/3/dladdr
기타: '스택 탐색을 통한 디버깅' 부분