Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 4115-410, F’04- 1 -Stack DisciplineSep. 01, 2004Lecture assembled byLecture assembled byDave EckhardtBruce MaggsReview slides from 15-213 originally Review slides from 15-213 originally developed by Randy Bryant and developed by Randy Bryant and Dave O'Halloran.Dave O'Halloran.L02_Stack15-410“Way easier than when we were students”15-410, F’04- 1 -OutlineZoom-speed reviewZoom-speed reviewProcess memory modelLinux memory model as an example, yours will be differentIA32 stack organizationYou will need to understand this fullyRegister saving conventionsYou will need to understand this fully““New material”New material”Before & after main()Project 015-410, F’04- 1 -Private Address SpacesEach process has its own private address space.Each process has its own private address space.kernel virtual memory(code, data, heap, stack)memory mapped region forshared librariesrun-time heap(managed by malloc)user stack(created at runtime)unused0%esp (stack pointer)memoryinvisible touser codebrk0xc00000000x080480000x40000000read/write segment(.data, .bss)read-only segment(.init, .text, .rodata)loaded from the executable file0xffffffff15-410, F’04- 1 -Linux Memory LayoutStackStackRuntime stack (8MB limit)HeapHeapDynamically allocated storageWhen call malloc, calloc, newShared/Dynamic Libraries aka Shared ObjectsShared/Dynamic Libraries aka Shared ObjectsLibrary routines (e.g., printf, malloc)Linked into object code when first executedWindows has “DLLs” (semantic differences)Data, BSSData, BSSStatically allocated dataE.g., arrays & strings declared in codeText, RODATAText, RODATAText - Executable machine instructionsRODATA – Read-only (e.g., “const”)Upper 2 hex digits of addressRed Hatv. 6.2~1920MBmemorylimitFFBF7F3FC0804000StackSharedLibrariesTextDataHeapHeap0815-410, F’04- 1 -Linux Memory AllocationLinkedBF7F3F804000StackLibrariesTextData08Some HeapBF7F3F804000StackLibrariesTextDataHeap08MoreHeapBF7F3F804000StackLibrariesTextDataHeapHeap08InitiallyBF7F3F804000StackTextData0815-410, F’04- 1 -IA32 StackRegion of memory managed with stack disciplineGrows toward lower addressesRegister %esp indicates lowest stack addressaddress of top elementStackPointer%espStack GrowsDownIncreasingAddressesStack “Top”Stack “Bottom”15-410, F’04- 1 -IA32 Stack PushingPushingPushingpushl SrcFetch operand at SrcDecrement %esp by 4Write operand at address given by %espStack GrowsDownIncreasingAddressesStack “Top”Stack “Bottom”StackPointer%esp-415-410, F’04- 1 -IA32 Stack PoppingPoppingPoppingpopl DestRead operand at address given by %espIncrement %esp by 4Write to DestStackPointer%espStack GrowsDownIncreasingAddressesStack “Top”Stack “Bottom”+415-410, F’04- 1 -Procedure Control FlowUse stack to support procedure call and returnProcedure call:Procedure call:call la bel Push return address on stack; Jump to labelReturn address valueReturn address valueAddress of instruction beyond callExample from disassembly 804854e: e8 3d 06 00 00 call 8048b90 <main> 8048553: 50 pushl %eaxReturn address = 0x8048553Procedure return:Procedure return:ret Pop address from stack; Jump to address15-410, F’04- 1 -%esp%eip%esp%eip 0x804854e0x1080x1080x10c0x1100x1040x804854e0x8048553123Procedure Call Example0x1080x10c0x1101230x108call 8048b90804854e: e8 3d 06 00 00 call 8048b90 <main>8048553: 50 pushl %eax0x8048b900x104%eip is program counter15-410, F’04- 1 -%esp%eip0x104%esp%eip 0x80485910x80485910x1040x1040x1080x10c0x1100x8048553123Procedure Return Example0x1080x10c0x110123ret8048591: c3 ret0x108%eip is program counter0x80485530x804855315-410, F’04- 1 -Stack-Based LanguagesLanguages that Support RecursionLanguages that Support Recursione.g., C, Pascal, JavaCode must be “Reentrant”Multiple simultaneous instantiations of single procedureNeed some place to store state of each instantiationArgumentsLocal variablesReturn pointerStack DisciplineStack DisciplineState for given procedure needed for limited timeFrom when called to when returnCallee returns before caller doesStack Allocated in Stack Allocated in FramesFramesstate for single procedure instantiation15-410, F’04- 1 -Call Chain ExampleCode StructureCode Structureyoo(…){••who();••}who(…){• • •amI();• • •amI();• • •}amI(…){••amI();••}yoowhoamIamIamICall ChainProcedure amI recursiveamI15-410, F’04- 1 -StackPointer%espyoowhoprocFramePointer%ebpStack“Top”Stack FramesContentsContentsLocal variablesReturn informationTemporary spaceManagementManagementSpace allocated when enter procedure“Set-up” codeDeallocated when return“Finish” codePointersPointersStack pointer %esp indicates stack topFrame pointer %ebp indicates start of current frameamI15-410, F’04- 1 -IA32/Linux Stack FrameCurrent Stack Frame (“Top” Current Stack Frame (“Top” to Bottom)to Bottom)Parameters for function about to call“Argument build”Local variablesIf can’t keep in registersSaved register contextOld frame pointerCaller Stack FrameCaller Stack FrameReturn addressPushed by call instructionArguments for this callStack Pointer(%esp)Frame Pointer(%ebp)Return AddrSavedRegisters+LocalVariablesArgumentBuildOld %ebpArgumentsCallerFrame15-410, F’04- 1 -swapvoid swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0;}int zip1 = 15213;int zip2 = 91125;void call_swap(){ swap(&zip1, &zip2);}call_swap:• • •pushl $zip2 # Global Varpushl $zip1 # Global Varcall swap• • •&zip2&zip1Rtn adr%espResultingStack•••Calling swap from call_swap15-410, F’04- 1 -swapvoid swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp = t0;}swap:pushl %ebpmovl %esp,%ebppushl %ebxmovl 12(%ebp),%ecxmovl 8(%ebp),%edxmovl (%ecx),%eaxmovl (%edx),%ebxmovl %eax,(%edx)movl %ebx,(%ecx)movl -4(%ebp),%ebxmovl %ebp,%esppopl %ebpretBodySetUpFinish15-410, F’04- 1 -swap Setup #1swap:pushl %ebpmovl %esp,%ebppushl
View Full Document
Unlocking...