Stack이라는 자료구조가 가장 많이 사용되는 곳이, 바로 우리가 프로그램 실행 시에 필요로 하는 Stack입니다. (-,.- ) 말이 좀 이상하지만, 자료 구조로서의 Stack과 우리가 사용하는 임시 저장소라든가, History를 관리하기 위하여 사용하는 Stack이 이름이 같습니다. 공교롭네요. 뭐, 어차피 Stack은 Stack의 원리를 이용한 거니까 뭐 그 넘이 그 넘이지요 뭐.
Embedded system에서는 Heap도, Stack도 사실은 전역변수의 Array로 선언되어 있습니다. - 꼭 전역변수로 선언할 필요는 없긴 해요. 예를 들면 연속적인 memory 영역을 잡아 놓고 그 영역을 stack나 heap으로 사용할 수도 있지만, 보통 array로 잡게 되면 자연스레 연속적인 memory 영역으로 잡을 수 있을 뿐 아니라, 이름을 아니까 언제든지 debugging시에 access할 수 있는 장점이 있다고 봐야겠죠 -
이런 array를 이용한 구현관점에서 더욱 자세히 들여다 봅시다.
예를 들어, recipe_task에서 사용할 Stack은 dword recipe_stack[20000] 이런 식으로 선언되고, 역시나 공용으로 사용할 heap은 static uint32 commonMemoryPool[20000]; 이런 식으로 선언을 하여, Memory 상에 일단 어떤 영역을 확보 한 후, 이 영역에 대하여 어떻게 Handling을 할 것인가에 의해 stack이냐, Heap이냐를 구분하는 것입니다.
이런 식이라면, Stack이나 Heap도 Bootup 시에 내가 원하는 대로 여러 가지 종류로 선언해서 사용할 수 있겠습니다. 이런 식으로 선언된 전역변수는 Linker가 어떻게 알아볼 것이냐! 하는 문제에서 초기화 되지 않은 (Uninitialized) 전역변수 배열
이라고 알아볼 것이 뻔합니다. 결국엔, .bss section, 즉 ZI중 하나가 되겠죠.
두 번째로는 이 영역이 어떻게 채워지느냐에 관한 문제인데, (이걸 Growth 방향, Data가 쌓여가는 방향) 우리가 보통 사용하는 stack과 heap은 다음과 같은 모양으로 Data가 쌓여 갑니다.
보통 Stack은 높은 주소에서 낮은 주소로, Heap은 낮은 주소에서 높은 주소로 쌓아가게 되는데, 어떻게 쌓아 할 것이냐는 것은 stack이나 heap을 어떻게 다룰 것이냐에 따라 다릅니다만, 제가 관심을 두고 있는 Embedded system은 이렇게 쌓아가고 있습니다. 이 이유는 다음에 더 자세히 레츠고 하시고, Stack이나 Heap에 대한 더 자세한 내용을 다룰 때, 자신이 관심을 두는 stack이나 heap이 어떻게 data를 쌓는지 확인하시는 것이 상당히 중요합니다. 이걸 모르면 Stack Back Tracing을 못합니다. 고급 디버깅의 초석이에요.
Stack이나 heap이나 어떻게 쌓아가는지는 그 구현에 따라 틀리니까, 그때 그때 다르게 생각해야 합니다~. 아래 그림은 우리 Embedded system에서 일반적으로 사용하는 Stack과 heap인데요, Stack은 낮은 주소로~, heap은 높은 주소로 점점 생겨나는 게 일반적인 구조에요.
그리고, 헷갈리는 부분에서 낮은 주소라는 건 숫자가 더 작은 주소, 높은 주소라는 건 숫자가 더 큰 주소를 의미하고요 보통은 낮은 주소를 밑에 그리지만, 아래 그림처럼 외워 두시면 더 편할 꺼에요. 만일 아래 그림 중 stack을 recipe_stack[200000] 영역이라고 한다면, stack중 가장 늦게 쌓이게 되는 stack limit은 recipe_stack[0]을 의미하고요, stack에서 제일 먼저 쌓이는 곳은 recipe_stack[199999] 이에요. 이 그림대로 알고 있으면 나중에 debugger랑 연결해서 stack overflow를 이해할 때 편리하니까 잘 기억해 둡시다.
Stack에 대해서 구현에 따른 방법들을 살펴 본다면~ 다음과 같이 4가지로 정리할 수 있습니다. 뭐, 그림은 ARM specification에서 따왔구요. 너무 따분하게 생각 마시고 잘 따라가면 오호라 정말 간단하구나 하는 생각을 틀림없이 하시게 될 겁니다.
아래의 ST어쩌하고 LD어쩌구는 Destination Register가 가리키는 곳에 Parameter Register들을 한꺼번에 Multiple Store할 수 있는 명령어를 말하며, 아래 R9을 R13(SP)으로 대치 하면 Stack으로 사용 가능하게 해 주는 원리에요. 그런데, 위의 그림이랑은 반대로 더 큰 숫자의 주소가 위로 가게 그려 놓았네요. 아이 헷갈려라~ 미안합니다. - 반대 쪽으로 그림을 그릴려다가 대부분의 specification이 아래와 같이 notation을 해 놓는 바람에 -
우선, 알아둘 것들이 있습니다. Stack은 자라는 방향이 높은 주소로 자라는 것, 그리고 낮은 주소로 자라는 것이 있습니다. 높은 주소로 자라는 것은 Ascending, 낮은 주소로 자라는 것은 Descending Satck으로 분류합니다. 또한 현재 Stack pointer가 방금 push나 pop을 한 Data를 포함하면 Full, 아니면 empty로 분류하고요, 마지막으로 Stack pointer가 Data를 넣은 후 변하느냐 아니면 먼저 변하고 SP가 변하느냐에 따라 After와 Before로 나뉩니다.
뭐 어렵진 않죠? - 라고 말해놓고 겁나 머리 아픕니다. 이런 걸 외우고 있는 괴물들이 있는 한, 조금은 흉내라도 내야 하니깐, 가장 쉬운 방법으로 따라갈 수 있는 방법을 찾아봐야 하겠습니다. - 왜 이런 얘기를 이 시점에 꺼내느냐 하면, Stack Pointer가 특정시점에서 어떻게 update되어 있느냐가 Stack back tracing의 핵심이기 때문에 Stack Pointer가 어떻게 update되는지를 염두 해 두고 읽으면 더욱 도움이 될 것으로 생각됩니다.
일단은 Stack에는 Multiple register transfer addressing 명령어를 이용하여, push를 하거나, pop을 합니다. 이때 이용되는 명령어들이 위의 명령어 들인데 한번 분석해 봅시다요. 처음 두자리는 ST/ LD로 표시되며, ST는 store, LD는 Load로서, 각각 push냐, pop이냐를 나눌 수 있습니다. 가운데 M은 Multiple이라는 의미에서 모든 명령어에 들어가고요. 나머지 뒷 두 자리가 좀 복잡한데,
IB는 Increase Before로서 SP를 Data를 넣기 전에 증가 시킨다는 의미이고요
IA는 Increase After로서 SP를 Data를 넣고 난 후에 증가 시킨다는 뜻이에요.
DB는 Decrease Before로서 SP를 Data를 넣기 전에 감소 시킨다는 의미이고요,
DA는 Decrease After로서 SP를 Data를 넣고 난 후에 감소 시킨다는 의미입니다.
그러니까 앞에 꺼의 목적어는 SP, 뒤의 것의 목적어는 Data입니다. 뒤에 거를 먼저 수행하고 앞에 것을 수행한다는 의미에요. SP 어쩌구 Data라고 하면 쉽죠. IB는 SP Increase Before Data 니까 Data전에 SP를 increase한다 뭐 이런 뜻이에요.
또한
FA는 Full Ascending이고, SP는 유효한 Data를 가르키고 큰 주소 방향으로 늘어난다는 뜻이고요
FD는 Full Descending이고, SP는 유효한 Data를 가르키고 작은 주소 방향으로 늘어난다는 뜻이에요.
EA는 Empty Ascending이고, SP는 유효한 Data를 가르키지 않고, 큰 주소 방향으로 늘어난다는 듯이고,
ED는 Empty Descending이고, SP는 유효한 Data를 가르키지 않고, 작은 주소 방향으로 늘어난다는 뜻이에요.
헥헥.
그리고 명령어의 형식은 위의 예제 중에 하나를 따서 보는 게 좋을 거 같습니다.
명령어 r9!, {r0, r1, r5}
는 R9가 가리키는 곳에 R0, R1, R5를 넣고 넣은 개수 3개 만큼 R9을 update하라는 의미입니다.
그러니까, 첫 번째 예를 들면,
STMIA r9! {r0, r1, r5} 라고 한다면,
R9가 가리키는 곳에 R0, R1, R5를 집어 넣는데 R9 (SP)을 데이터 먼저 넣고, R9을 나중에 늘려라
라는 뜻이죠. 간단합니까? 휴~ 저는 맨날 헷갈리는데
자 그러면 그림을 보면서 찬찬히 뜯어 볼까요?
첫번째
STMIA r9! {r0, r1, r5}는
Store하는데, R9을 Data를 넣고 Increase해라 라는 거니까, R9가 가리키는 곳부터 R0 넣고 R9++, R1넣고 R9++, R5넣고 R9++ 하라는 의미죠. 그러면 어떤 뜻일까요 주소가 더 큰 방향으로 Stack이 자라날 것이고, 결국 R9는 R5가 들어있는 주소보다 하나 더 큰 곳을 가리키게 됩니다.
이것의 특징은 R9는 실제 유효한 Data를 품고 있지 않으니까, Empty이고요, 더 큰 주소로 Stack을 쌓으니까 Ascending 입니다.
결국
STMEA r9! {r0, r1, r5}와 같은 의미이지요? 그래서 table에 보시면 같은 칸에 자리잡고 있습니다.
그럼 두 번째
STMIB r9! {r0, r1, r5}는
Store하는데, R9를 Increase 먼저 하고 Data를 넣고 가라 라는 건데요, R9++하고 R0넣고, R9++하고 R1넣고, R9++하고 R5넣고 넣습니다. 그러면 주소가 더 큰 방향으로 Stack이 자라나고, 결국 R9은 마지막 R5가 들어 있는 곳을 가리키게 되지요. 이것의 특징은 R9에 실제 유효한 Data를 품고 있으니까 Full이고요, 더 큰 주소로 Stack을 쌓으니까 Ascending입니다.
결국
STMFA r9! {r0, r1, r5}와 같은 의미가 되며 그래서 table에 보시면 같은 칸에 자리 잡고 있습니다.
똑같이 세 번째는
STMDA r9! {r0, r1, r5}는
Store하는데, 데이터를 넣고 R9을 Decrease하라는 의미 인데요. 원래 R9이 가리키는 주소에 R0 넣고 R9--하고, R1넣고 R9--하고, R5넣고 R-- 하라는 의미니까요 그러면 주소가 더 작은 방향으로 Data를 쌓게 되고, 결국 R9은 마지막 R5가 들어간 곳 보다 하나 더 적은 주소를 가리키게 됩니다. 이것의 특징은 R9은 R5를 가리키고 있지 않으니까 Data를 품고 있지 않아서 Empty이고요, 더 작은 주소 쪽으로 Data를 쌓고 있으니까
결국
STMED r9! {r0, r1, r5}와 같은 의미가 됩니다. 헥헥.
마지막은 한번 연습해 보시면,
STMDB r9! {r0, r1, r5} = STMFD r9!, {r0, r1, r5}로 정리할 수 있습니다.
Load도 마찬가지겠습니다. 아 어지러워라.. 뭐 별거 있겠사옵니까? 보통 우리가 사용하는 Stack은 Full Descending으로 구현되어, 더 낮은 주소로 Stack이 자라고, SP가 가리키는 주소는 Valid한 Data를 품고 있습니다. 그르니까, Stack에 Full Descending으로 넣고 빼는 일은
stmfd sp!, {r4-r12,lr}
ldmfd sp!, {r4-r12,lr}
으로 넣고 빼면 됩니다요. 여기에서 sp는 R13 stack pointer이고요, lr은 Linked Register로서 R14를 의미해요!
자, 그르면, Stack Initialize는 어떻게 하는 걸까요? R13을 엮는 일만 잘하면 됩니다. 예를 들어 Abort mode의 Stack 주소를 R13에 엮어 주기만 하면 됩니다. 아래가 그 실 예인데요, Abort mode로 CPU mode를 바꾸고, Abort stack을 r13에 엮어주는 과정입니다.
msr CPSR_c, #PSR_Abort
ldr r13, =abort_stack+Abort_Stack_Size
오, 간단간단입니다. 완전 간단이죠. 뭘 해도 이렇게만 하면 됩니다. r13에만 묶어주면 알아서 굴러 갑니다. r13에 엮인 주소부터 push와 pop을 하는 거죠.
자, 보시면 아까 위의 그림대로 가장 먼저 쌓이는 곳이 abort_stack의 시작 번지 + Abort_Stack_Size이죠? 높은 주소에서부터 시작해서 abort_stack 시작 번지까지 쌓여가는 구조니까 그래요~
한가지 더! ARM sate와 Thumb state에서의 Stack관련한 명령어가 틀립니다. ARM state에서는 Stack에 관련된 명령어를 위의 Multiple Register Transfer 명령을 사용하지만, Thumb state에서는 Push/ Pop이라는 명령으로 대신합니다. 그러니까 Thumb state에서 Stack을 사용하는 자리에 stmfd나 ldmfd 뭐 이런 거 없다고 해서 놀라시면 안되어요!
Linked at 임베디드 시스템 개발자 되기 .. at 2009/07/27 23:09 Commented by SueKim at 2009/07/28 15:53 
Commented by 히언 at 2009/07/28 20:21 Commented by 초보자 at 2009/07/29 11:03 Commented by 히언 at 2009/07/29 21:58
친절한 임베디드 시스템 개발자 되기 강좌 글 전체 리스트 (링크) - 
댓글