Machine-Level Programming III: Functions and Call Stack in Computer Systems
Explore the concept of functions and call stack in machine-level programming, covering topics such as accessing registers, memory operations, control procedures, passing data, memory management, and more. Dive into the mechanisms involved in procedures and understand how control is passed within the code.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Machine-Level Programming III: Functions and the call stack cs154 Introduction to Computer Systems Junchen Jiang cs154
Today Accessing registers & memory Basic operations Control Procedures cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } Accomplished using instructions + conventions cs154
Mechanisms in Procedures P( ) { y = Q(x); print(y) } Passing control To beginning of procedure code Back to return point Passing data Procedure arguments Return value Memory management Allocate during procedure execution Deallocate upon return int Q(int i) { int t = 3*i; int v[10]; return v[t]; } Accomplished using instructions + conventions Recursions are just like function calls cs154
Today Procedures Stack Structure Calling Conventions Passing control Passing data Managing local data Illustration of Recursion
Stack in memory Memory address space 2^n Kernel User stack Registers PC CPU Shared libraries Runtime heap Loaded code 0 cs154
Stack in memory Memory address space 2^n Kernel yoo( ) { } User stack yoo s stack frame Registers PC CPU Shared libraries Runtime heap Loaded code 0 cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } yoo yoo who %rsp Stack pointer amI amI amI amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo who who amI amI %rsp amI amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo amI( ) { amI(); } who who amI amI amI amI %rsp amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo amI( ) { amI(); } who amI( ) { amI(); } who amI amI amI amI amI amI %rsp cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo amI( ) { amI(); } who amI( ) { amI(); } who amI amI amI( ) { amI(); } amI amI amI amI amI %rsp cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo amI( ) { amI(); } who amI( ) { amI(); } who amI amI amI amI amI amI %rsp cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo amI( ) { amI(); } who who amI amI amI amI %rsp amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo who who amI amI %rsp amI amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo amI( ) { amI(); } who who amI amI amI amI %rsp amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } } who( ) { amI(); amI(); yoo yoo who who amI amI %rsp amI amI cs154
Carnegie Mellon Stack Example yoo yoo( ) { who(); } yoo yoo who %rsp amI amI amI amI cs154
Carnegie Mellon x86-64/Linux Stack Frame Caller Stack Frame Return address Pushed by call instruction Arguments for this call (optional) Caller Frame Argument build (Optional) Return Addr Callee Stack Frame Saved register context Local variables If can t keep in registers Arguments for function about to call (optional) Saved Registers + Local Variables Callee Frame Stack pointer %rsp
Carnegie Mellon x86-64 Stack Stack Bottom Grows toward lower addresses Increasing Addresses Register %rsp contains lowest stack address address of top element Stack Grows Down Stack Pointer: %rsp Stack Top cs154
Carnegie Mellon x86-64 Stack: Push Stack Bottom pushq Src Fetch operand at Src Decrement %rsp by 8 Write operand at address given by %rsp Increasing Addresses Stack Grows Down Stack Pointer: %rsp Stack Top cs154
Carnegie Mellon x86-64 Stack: Push Stack Bottom pushq Src Fetch operand at Src Decrement %rsp by 8 Write operand at address given by %rsp Example: pushq %rbx Increasing Addresses %rbx 0xFF00 Stack Grows Down Stack Pointer: %rsp Stack Top cs154
Carnegie Mellon x86-64 Stack: Push Stack Bottom pushq Src Fetch operand at Src Decrement %rsp by 8 Write operand at address given by %rsp Example: pushq %rbx Increasing Addresses %rbx 0xFF00 Stack Grows Down -8 Stack Pointer: %rsp 0xFF00 Stack Top cs154
Carnegie Mellon x86-64 Stack: Pop Stack Bottom popq Dest Read value at address given by %rsp Increment %rsp by 8 Store value at Dest (must be register) Dest Increasing Addresses Stack Grows Down Stack Pointer: %rsp Stack Top cs154
Carnegie Mellon x86-64 Stack: Pop Stack Bottom popq Dest Read value at address given by %rsp Increment %rsp by 8 Store value at Dest (must be register) Example: popq %rbx Dest Increasing Addresses %rbx Stack Grows Down Stack Pointer: %rsp 0xFF00 Stack Top cs154
Carnegie Mellon x86-64 Stack: Pop Stack Bottom popq Dest Read value at address given by %rsp Increment %rsp by 8 Store value at Dest (must be register) Example: pushq %rbx Dest Increasing Addresses %rbx 0xFF00 Stack Grows Down Stack Pointer: %rsp +8 0xFF00 Stack Top cs154
Carnegie Mellon Today Procedures Stack Structure Calling Conventions Passing control Passing data Managing local data Illustration of Recursion
Code Examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400553: imul %rsi,%rax 400557: ret # a # a * b # Return cs154 #
Code Examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400553: imul %rsi,%rax 400557: ret # a # a * b # Return cs154 #
Code Examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400553: imul %rsi,%rax 400557: ret # a # a * b # Return cs154 #
Code Examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400553: imul %rsi,%rax 400557: ret # a # a * b # Return cs154 #
Code Examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400553: imul %rsi,%rax 400557: ret # a # a * b # Return cs154 #
Procedure Control Flow Procedure call: call label Push return address on stack Address of the next instruction right after call Jump to label Procedure return: ret Pop address from stack Jump to address cs154
Control Flow Example 0x130 0000000000400540 <multstore>: 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 0x128 0x120 %rsp 0x120 Stack Pointer %rip 0x400544 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400557: ret Next instruction of caller %rip: Program Counter (PC) cs154 #
Control Flow Example (cont.) 0x130 0000000000400540 <multstore>: 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 0x128 Return address saved here!! 0x120 0x118 0x400549 %rsp 0x118 Stack Pointer %rip 0x400550 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400557: ret Next instruction now in callee %rip: Program Counter (PC) cs154 #
Control Flow Example (cont.) 0x130 0000000000400540 <multstore>: 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 0x128 Return address 0x120 0x118 0x400549 %rsp 0x118 Stack Pointer %rip 0x400557 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400557: ret Next instruction now in callee %rip: Program Counter (PC) cs154 #
Control Flow Example (cont.) 0x130 0000000000400540 <multstore>: 400544: callq 400550 <mult2> 400549: mov %rax,(%rbx) 0x128 0x120 %rsp 0x120 Stack Pointer %rip 0x400549 0000000000400550 <mult2>: 400550: mov %rdi,%rax 400557: ret Next instruction = return addr! %rip: Program Counter (PC) cs154 #
Why Stack is so important The key to implementation of sub-routines Two stacks == Turing machine No register is needed (in theory)! Turing s report on Automatic Computing Engine (ACE) in 1945
Carnegie Mellon Procedure Data Flow Registers Stack First 6 arguments Caller Frame %rdi %rsi Arg n %rdx %rcx Argument build (Optional) %r8 Arg 8 Return Addr %r9 Arg 7 Return value %rax Only allocate stack space when registers are not enough
Data flow examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: # x in %rdi, y in %rsi, dest in %rdx 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> # t in %rax 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: # a in %rdi, b in %rsi 400550: mov %rdi,%rax 400553: imul %rsi,%rax # s in %rax 400557: ret # a # a * b # Return
Data flow examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: # x in %rdi, y in %rsi, dest in %rdx 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> # t in %rax 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: # a in %rdi, b in %rsi 400550: mov %rdi,%rax 400553: imul %rsi,%rax # s in %rax 400557: ret # a # a * b # Return
Data flow examples void multstore (long x, long y, long *dest){ long t = mult2(x, y); *dest = t; } 0000000000400540 <multstore>: # x in %rdi, y in %rsi, dest in %rdx 400540: push %rbx 400541: mov %rdx,%rbx 400544: callq 400550 <mult2> # t in %rax 400549: mov %rax,(%rbx) 40054c: pop %rbx 40054d: ret # Save %rbx # Save dest # mult2(x,y) # Save at dest # Restore %rbx # Return long mult2 (long a, long b) { long s = a * b; return s; } 0000000000400550 <mult2>: # a in %rdi, b in %rsi 400550: mov %rdi,%rax 400553: imul %rsi,%rax # s in %rax 400557: ret # a # a * b # Return
