ANITA’S SUPER AWESOMERECITATION SLIDES15/18-213: Introduction to Computer SystemsStacks and Buflab, 23 Sept 2013Anita ZhangWHAT’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!” Not (quite) true Buf Lab out Tuesday (tomorrow), 11:59 PM 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 instructionsJUMP 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 0x4006000x400600: 0x00000000004004d1 0x00000000004004c80x400610: 0x00000000004004c8 0x00000000004004be0x400620: 0x00000000004004c1 0x00000000004004d70x400630: 0x00000000004004c8 0x00000000004004beASSEMBLY 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 instructionSPARSE SWITCH EXAMPLEmovl 8(%ebp),%eax # get xcmpl $444,%eax # x:444je L8jg L16cmpl $111,%eax # x:111je L5jg L17testl %eax,%eax # x:0je L4jmp L14int div111(int x) {switch(x) {case 0: return 0;case 111: return 1;case 222: return 2;case 333: return 3;case 444: return 4;case 555: return 5;case 666: return 6;case 777: return 7;case 888: return 8;case 999: return 9;default: return -1;}}. . .L5:movl $1,%eaxjmp L19L6:movl $2,%eaxjmp L19L7:movl $3,%eaxjmp L19L8:movl $4,%eaxjmp 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 Like boxes on the side of memory Caller save 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 functionASIDE: WHY BOTH? Why do we have both caller and callee save? Performance Not all registers need to be savedIA32 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 functionSPECIAL IA32 REGISTERS Base Pointer %ebp Points to the “bottom” of the stack frame The location of old %ebp that gets pushed on entry Stack Pointer %esp Points to the “top” of the stack Usually whatever was last pushed on the stack Instruction Pointer (Program Counter) %eip Points to the next instruction to be executedIA32 TERMINOLOGYDirection of stackgrowth%esp“top”“bottom”Higher addresses(ie. 0xFFFFFFFF)Lower addresses(ie. 0x00000000)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 stacksASIDE: 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) ArchitectureASIDE: 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 - downWHAT HAPPENS IN IA32: PUSH Pushing on the stack In general, pushl translates to (in AT&T syntax): subl $0x4, %espmovl src, (%esp)pushl %eax%esp %esp 0x15 0x150x213“bottom”“bottom”WHAT HAPPENS IN IA32: POP Popping off the stack In general, popl translates to (in AT&T syntax): movl (%esp), destaddl $0x4, %esppopl %eax%esp %esp 0x1000x1000x213“bottom”“bottom”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……Earlier Frames…Caller’s frameArgument n…Argument 1Return AddressFrame Pointer%ebp Saved (old)
View Full Document
Unlocking...