ANITA S SUPER AWESOME RECITATION SLIDES 15 18 213 Introduction to Computer Systems Stacks and Buflab 23 Sept 2013 Anita Zhang WHAT S NEW OR NOT Bomb Lab is due Tuesday tomorrow 11 59 PM Your late days are wasted here Student But if you wait until the last minute then it only takes a minute Buf Lab out Tuesday tomorrow 11 59 PM Not quite true Hacking the stack Stacks will be on the exams They re tough at first but I believe in you SPEAKING OF THE EXAM Midterm Wed 16 Oct Sat 19 Oct 2013 Covers everything up to and including caches Chapters 1 3 and 6 of textbook Up to and including Cache Lab Lectures up to and including Caches 1 Oct 2013 Recitation exam review the week of exam Read each chapter 3 times work the practice problems and do previous exams Do enough midterms until you feel comfortable with the material at least 5 recent ones Depending on the semester caches can be found in Exam 2 TO THOSE WHO WANT A COOL SHELL http www contrib andrew cmu edu anitazha 15213 tips html Scroll down to the part about Shell of Choice Follow the directions Your terminal will look something like this JOURNEY THROUGH TIME Basic Assembly Review Jump Tables vs Sparse Switch Terminology Stacks IA32 Stack Discipline Function Call Overview Stack Walkthrough Extras on x86 64 stacks Buf Lab Quick Start Essential Items of Business Miscellany Demo ASSEMBLY COVERAGE JUMP TABLES Jump tables Think of it as an array of addresses in memory Use jump instructions to execute from these addresses Using assembly it is possible to index into the array Each entry of will hold addresses of instructions JUMP TABLE EXAMPLE The tip off is something like this jmpq 0x400600 rax 8 Empty base means implied 0 rax is the index 8 is the scale 64 bit machine addresses are 8 bytes indicates a dereference like in C notation Like leal does not do a dereference with parenthesis Put it all together Jump to the address stored in the address 0x400600 rax 8 Using GDB example output x 8g 0x400600 0x400600 0x00000000004004d1 0x00000000004004c8 0x400610 0x00000000004004c8 0x00000000004004be 0x400620 0x00000000004004c1 0x00000000004004d7 0x400630 0x00000000004004c8 0x00000000004004be ASSEMBLY COVERAGE SPARSE SWITCH Sparse switch vs jump tables Jump tables work if every entry has a jump location Sparse switches cover cases where there are less densely packed cases Does not make sense to allocate space for 100 entries if only 1 and 100 are used as cases In the following example uses labels to go to the next instruction SPARSE SWITCH EXAMPLE int div111 int x switch x case 0 return 0 movl 8 ebp eax get x cmpl 444 eax x 444 je L8 case 111 return 1 jg L16 case 222 return 2 cmpl 111 eax case 333 return 3 je L5 case 444 return 4 jg L17 case 555 return 5 testl eax eax x 0 case 666 return 6 je L4 case 777 return 7 jmp L14 x 111 L5 movl 1 eax jmp L19 L6 movl 2 eax jmp L19 L7 movl 3 eax jmp L19 case 888 return 8 case 999 return 9 default return 1 L8 movl 4 eax jmp L19 SOME KIND OF STACK MOTIVATION In order to support general recursion a language needs a way to allocate different activation records for different invocations of the same function That way local variables allocated in one recursive call can coexist with local variables allocated in a different call credits to stack overflow DEFINITIONS AND CONVENTIONS Register Some place in hardware that stores bits Caller save Like boxes on the side of memory Saved by the caller of a function Before a function call the caller must save any caller save register values it wants preserved Callee save Saved by the callee of a function The callee is required to save restore values in these registers if it is using these registers in the function ASIDE WHY BOTH Why do we have both caller and callee save Performance Not all registers need to be saved IA32 REGISTERS 6 general purpose registers Caller save eax ecx edx Saved by the caller of a function Callee save ebx edi esi Saved by the callee of a function SPECIAL IA32 REGISTERS Base Pointer ebp Points to the bottom of the stack frame Stack Pointer esp Points to the top of the stack The location of old ebp that gets pushed on entry Usually whatever was last pushed on the stack Instruction Pointer Program Counter eip Points to the next instruction to be executed IA32 TERMINOLOGY Higher addresses ie 0xFFFFFFFF bottom Direction of stack growth esp Lower addresses ie 0x00000000 top ASIDE TECHNOLOGY NOTE AGAIN This class is strictly x86 64 Other architectures may have different conventions May not use stacks at all weird I know Stacks grow down up depending on implementation Very confusing to those new to stacks ASIDE DIRECTION OF GROWTH Stack direction REALLY doesn t matter Direction of growth is dependent on the processor May be selectable for up down Or some other direction BAM CIRCULAR STACK SPARC scalable processor architecture Architecture ASIDE DIRECTION OF GROWTH Examples from StackOverflow x86 down SPARC in a circle System z in a linked list down at least for zLinux ARM selectable PDP11 down WHAT HAPPENS IN IA32 PUSH Pushing on the stack bottom bottom pushl eax 0x15 0x15 esp 0x213 esp In general pushl translates to in AT T syntax subl 0x4 esp movl src esp WHAT HAPPENS IN IA32 POP Popping off the stack bottom bottom popl eax 0x100 esp esp 0x100 0x213 In general popl translates to in AT T syntax movl esp dest addl 0x4 esp STACK FRAMES WHATCHAMACALLITS Every function call gets a stack frame All the useful stuff can go on the stack Local variables scalars arrays structs What the compiler couldn t fit into registers Callee caller save registers Temporary variables Arguments Stacks can make recursion work Key idea Storage for each instance of procedure call stolen out of 15 410 slides SO THAT S WHAT IT LOOKS LIKE Increasing Addresses Earlier Frames Argument n Caller s frame Argument 1 Return Address Frame Pointer ebp Saved old ebp Saved registers local variables and temporaries Argument build area Stack Pointer esp Current callee frame ROLES OF A FUNCTION CALLER Caller Save push relevant caller save registers Push arguments Call function Caller after function return Remove add to esp or pop arguments Restore pop saved caller save registers ROLES OF A FUNCTION CALLEE Callee Push ebp save stack frame Copy move esp into ebp Save push callee save registers it wants to use Callee before return Restore pop callee save registers previously saved Copy move ebp into esp Moves stack pointer to the saved ebp Restore pop ebp FUNCTION CALLS OTHER OPERATIONS Implied operations
View Full Document
Unlocking...