1、1從程序到可執行代碼匯編（1）6次課2虛擬存儲器3摘要虛存概念地址、內容虛子區域地址的大小地址增大引入的問題Byte ordering大端、小端可見性4虛存虛存是byte的線性數組一般的存儲介質都有兩個基本操作WRITE(name, value) value READ(name)介紹name和value是兩個重要的概念 contents0 xffffffff0 xfffffffe0 x20 x10 x0addresses5Virtual MemoryValue has only fixed size (byte)Name (address) belongs to a set of consec

2、utive integers started from 0The virtual memory is a conceptual image presented to the machine-level program and does not exist actuallyprovides the program with what appears to be a monolithic byte array6Way to the AbstractionTaking something physical and abstract it logicalVirtual memoryOperatingS

3、ystemSpecialhardwareAbstractionlayerRAMChipsDiskstoragePhysicallayerWRITE(vadd value)READ(vadd)WRITE(padd value)READ(padd)7編譯器和運行時將虛存劃分為若干個子區域每個子區域存儲不同的program objects如：數據指令控制信息8Word Size vs. Data SizeWord size indicates the size of addressMachines support multiple data formatsEach has its own size

4、(data size)Word size is also the size of pointer dataData SizeSizes of C Objects (in Bytes)C Data Type 32-bit 64-bitchar11short22int44long int48long long int 88char *48float44double8810ExampleMany programmers assume that a program object declared as type int can be used to store a pointerThis works

5、fine for most 32-bit machines But leads to problems on an 64-bit machine11Address issuesIBM S/360: 24-bit addressPDP-11: 16-bit addressIntel 8086: 16-bit addressX86 (80386): 32-bit addressX86 64: 64-bit address 1264-bit data modelsData modelshortintlonglong longpointersSample operating systemsLLP641

6、632326464Microsoft Win64 (X64/IA64)LP641632646464Most Unix and Unix-like systems (Solaris, Linux, etc.)ILP641664646464HAL(Fujitsu subsidiary) SILP646464646464?13intN_t and uintN_tAnother class of integer types specifying N-bit signed and unsigned integersIntroduced by the ISO C99 standard In the fil

7、e stdint.h. Typical valuesint8_t, int16_t, int32_t, int64_tunit8_t, uint16_t, uint32_t, uint64_tN are implementation dependent14Byte OrderingHow should a large object be stored in memory?For program objects that span multiple bytesWhat will be the address of the object?How will we order the bytes in

8、 memory?A multi-byte object is stored as a contiguous sequence of bytes with the address of the object given by the smallest address of the bytes used15Byte OrderingLittle EndianLeast significant byte has lowest addressIntelBig EndianLeast significant byte has highest addressSun, IBMBi-EndianMachine

9、s can be configured to operate as either little- or big-endianMany recent microprocessors16Big Endian (0 x1234567)0 x1000 x1010 x1020 x1030123456717Little Endian (0 x1234567)0 x1000 x1010 x1020 x1036745230118How to Access an Object The actual machine-level program generated by C compiler simply trea

10、ts each program object as a block of bytesThe value of a pointer in Cis the virtual address of the first byte of the above block of storage19How to Access an Object The C compiler Associates type information with each pointerGenerates different machine-level code to access the pointed value stored a

11、t the location designated by the pointer depending on the type of that valueThe actual machine-level program generated by C compiler has no information about data types 20Code to Print Byte Representationtypedef unsigned char *byte_pointer;void show_bytes(byte_pointer start, int len)int i; for (i =

12、0; i len; i+) printf(0 x%pt0 x%.2xn, start+i, starti);printf(n);21Code to Print Byte Representationvoid show_int(int x) show_bytes(byte_pointer) &x, sizeof(int);void show_float(float x) show_bytes(byte_pointer) &x, sizeof(float);void show_pointer(void *x) show_bytes(byte_pointer) &x, sizeof(void *);

13、22ExampleLinux 32: Intel IA32 processor running LinuxWindows: Intel IA32 processor running WindowsSun: Sun Microsystems SPARC processor running SolarisLinux 64: Intel x86-64 processor running Linux23Byte Ordering es Visible Circumvent the normal type systemCommunicate between different machinesDisas

14、sembler 80483bd: 01 05 64 94 04 08 add %eax, 0 x804946424匯編的引入和尋址模式25摘要簡單C程序及其對應的匯編引入指令的概念通過C程序中的操作數引入寄存器、內存單元和立即數尋址模式舉例C程序中的變量在匯編中的表示26Characteristics of the high level programming languagesAbstraction ProductivereliableType checkingAs efficient as hand written codeCan be compiled and executed on a

15、 number of different machines27C constructsVariableDifferent data types can be declaredOperationArithmetic expression evaluationcontrolLoopsProcedure calls and returns28Code ExamplesC codeint accum = 0;int sum(int x, int y) int t = x+y; accum += t; return t;29Code ExamplesC codeint accum = 0;int sum

16、(int x, int y) int t = x+y; accum += t; return t;_sum:pushl %ebpmovl %esp,%ebpmovl 12(%ebp),%eaxaddl 8(%ebp),%eax addl %eax, accummovl %ebp,%esppopl %ebpretObtain with commandgcc O2 -S code.cAssembly file code.saddl 8(%ebp),%eaxinstruction30Characteristics of the assembly programming languagesLow le

17、vel instructions to carry out the computationManaging memoryHighly machine specific31OperandsIn high level languagesEither constantsOr variableExampleA = A + 4variableconstant32Assembly CodeOperands:x:Register%eaxy:MemoryM%ebp+84:Immediate $433IA-32RegisterMemoryDiskThe fastest storage units in comp

18、uter systems, typically 32-bit long34Registers vs. Virtual MemoryWRITE(name, value) value READ(name)How to name registers Using specific names, For example, in IA-32%eax, %ecx, %edx, %ebx, %esi, %edi, %esp, %ebpHow to name virtual memoryUsing address as we have studiedWhats the differenceAccessing v

19、alues in Registers is fast Number of the registers is smallMost modern instructions can access registers onlyWhere are the variables? registers & Memory%eax%edx%ecx%ebx%esi%edi%esp%ebp 0 xffffffff0 xfffffffe0 x20 x10 x0addressescontents36OperandsCounterparts in assembly languagesImmediate ( constant

20、 )Register ( variable )Memory ( variable )Examplemovl 8(%ebp), %eaxaddl $4, %eaxmemoryregisterimmediate37Express Variables in Assembly (Addressing Mode)Immediaterepresents a constant The format is $imm ($4, $0 xffffffff)Registers Register mode Ea%eaxThe value stored in the register %eaxNoted as REa

21、(R%eax)38Indexed Addressing ModeAn expression for a memory address (or an array index)Most general formImm(Eb, Ei, s)Constant “displacement” Imm: 1, 2 or 4 bytesBase register Eb: Any of 8 integer registersIndex register Ei : Any, except for %espS: Scale: 1, 2, 4, or 839Memory Addressing ModeThe addr

22、ess represented by the above formimm + REb + REi * sIt gives the valueMimm + REb + REi * s40指令的順序執行mov指令41摘要用戶可見狀態寄存器、內存、PC、條件碼寄存器介紹PC以及匯編程序的順序執行模式mov指令和棧操作舉例指針與地址42Assembly Programmers ViewFFFFFFFFBFFFFFFF7FFFFFFF3FFFFFFFC0000000800000004000000000000000StackDLLsTextDataHeapHeap08000000%eax%edx%ecx%

23、ebx%esi%edi%esp%ebp%eip%eflagAddressesDataInstructionsCPUMemory43Programmer-Visible StatesProgram Counter(%eip)Address of the next instructionRegister FileHeavily used program dataInteger and floating-point44Programmer-Visible StatesConditional code register (%eflags)Hold status information about th

24、e most recently executed instructionImplement conditional changes in the control flowVirtual Memory 45Understanding Machine Execution Where the sequence of instructions are stored?In virtual memoryCode areaHow the instructions are executed?%eip stores an address of memory, from the address, machine

25、can read a whole instruction oncethen execute it increase %eip%eip is also called program counter (PC)46Code Layoutkernel virtual memoryRead only codeRead only dataRead/write dataforbiddenmemory invisible to user codeLinux/x86processmemory image0 xffffffff0 xc00000000 x08048000%eip47Sequential execu

26、tionf()int i = 3 ;00000000 : 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 83 ec 14 sub $0 x14,%esp 6: c7 45 fc movl $03, -0 x4(%ebp) d: c9 03 00 00 00 leave e: c3 ret 48Sequential execution00000000 : 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 83 ec 14 sub $0 x14,%esp 6: c7 45 fc 03 00 00 00 movl $0 x3,-

27、0 x4(%ebp) d: c9 leave e: c3 ret c3ret c9 leavec000000038fc45 c7movl $0 x3,-0 x4(%ebp)144ec 83sub $0 x14,%espe5 89mov %esp,%ebp 0 55 push %ebp00 00 00 00 PC00 00 00 01 PC00 00 00 03 PC00 00 00 06 PC00 00 00 0d PC00 00 00 0e PC49Move InstructionsFormatmov src, destThe only possible combinations of th

28、e (src, dest) are(immediate, register)(memory, register)load(register, register)(immediate, memory)(register, memory)store50Data MovementInstructionEffectDescriptionmovl S, DD SMove double wordmovw S, DD SMove wordmovb S, DD SMove bytemovsbl S, DD SignedExtend( S)Move sign-extended bytemovzbl S, DD

29、ZeroExtend(S)Move zero-extended bytepushl SR%esp R%esp-4MR%esp SPushpopl DD MR%espR%esp R%esp+4Pop51Data FormatsMove data instruction mov (general) movb (move byte) movw (move word) movl (move double word)52Access Objects with Different Sizes int main(void) char c = 1; short s = 2; int i = 4; long l

30、 = 4L; long long ll = 8LL; return;8048335:c6 movb $0 x1,0 xffffffe5(%ebp)8048339:66 movw $0 x2,0 xffffffe6(%ebp)804833f:c7 movl $0 x4,0 xffffffe8(%ebp)8048346:c7 movl $0 x4,0 xffffffec(%ebp)804834d:c7 movl $0 x8,0 xfffffff0(%ebp)8048354:c7 movl $0 x0,0 xfffffff4(%ebp)-20-24-12-26-16-8-27%ebp53Array

31、in AssemblyPersistent usageStore the base addressvoid f(void)int i, a16;for(i=0; i16; i+)ai=i;movl%eax,-0 x44(%ebp,%edx,4)a: -0 x44(%ebp)i: %edx54Stack operationStack is a special kind of data structureIt can store objects of the same typeThe top of the stack must be explicitly specifiedIt is denote

32、d as top There are two operations on the stackpush and popThere is a hardware stack in x86its bottom has high address numberits top is indicated by %esp55Stack Layoutkernel virtual memoryRead only codeRead only dataRead/write dataforbiddenmemory invisible to user codeLinux/x86 processmemory image0 x

33、ffffffff0 xc00000000 x08048000%eipStackDownward growth%esp56Stack OperationInstructionEffectDescriptionpushl SR%esp R%esp-4MR%esp SPushpopl DD MR%espR%esp R%esp+4Pop57Pointers in Cint main()int a = 4 ; /* “address of” operator creates a pointer */int b = exchange(&a, 3); printf(“a = %d, b = %dn”, a,

34、 b);58Pointers in C%ebpStack4abCan variable a be in a register?59Pointers in C3&a%espStack4ab%ebp60Pointers in Cint exchange(int *xp, int y) /* operator * performs deferencing */int x = *xp ; *xp = y ;return x ;61Pointers in Cint exchange(int *xp, int y)int x = *xp ;*xp = y ;return x ;1 pushl %ebp2

35、movl %esp, %ebp3 movl 8(%ebp), %eax4 movl 12(%ebp), %edx5 movl (%eax), %ecx6 movl %edx, (%eax)7 movl %ecx, %eax8 movl %ebp, %esp9 popl %ebp62Pointers in C3&aRtn adr%espStack4abyxp%ebp63Pointers in C3&aRtn adrOld %ebp%esp 0 4 8 12 Stack1 pushl %ebp3&aRtn adr%espStack44abyxpabyxp%ebp%ebp64Pointers in

36、C3&aRtn adrOld %ebp%ebp%esp 0 4 8 12 OffsetStack2 movl %esp, %ebp4abyxp65Pointers in C3 movl 8(%ebp), %eax%eax: xp 20(%ebp)3&aRtn adrOld %ebp%ebp%esp 0 4 8 12 OffsetStack4abyxp66Pointers in C3 movl 8(%ebp), %eax4 movl 12(%ebp), %edx%eax: xp%edx: 33&aRtn adrOld %ebp%ebp%esp 0 4 8 12 OffsetStack4abyxp

37、67Pointers in C3 movl 8(%ebp), %eax4 movl 12(%ebp), %edx5 movl (%eax), %ecx%eax: xp%edx: 3%ecx: 43&aRtn adrOld %ebp%ebp%esp 0 4 8 12 OffsetStack4abyxp68Pointers in C3 movl 8(%ebp), %eax4 movl 12(%ebp), %edx5 movl (%eax), %ecx6 movl %edx, (%eax)%eax: xp%edx: 3%ecx: 4*xp(a): 33&aRtn adrOld %ebp%ebp%es

38、p 0 4 8 12 OffsetStack3abyxp69Pointers in C3 movl 8(%ebp), %eax4 movl 12(%ebp), %edx5 movl (%eax), %ecx6 movl %edx, (%eax)7 movl %ecx, %eax%eax: xp%edx: y%ecx: 4*xp(a): 3%eax: 4 (old *xp) return value3&aRtn adrOld %ebp%ebp%esp 0 4 8 12 OffsetStack3abyxp70Pointers in C8 movl %ebp, %esp (do nothing) 9

39、 popl %ebp3&aRtn adr%esp 0 4 8 12 Stack3abyxp%ebp71Pointers in Cint main()int a = 4 ; /* “address of” operator creates a pointer */int b = exchange(&a, 3); printf(“a = %d, b = %dn”, a, b);72Pointers in C3&a%espOffsetStack3%eax 4Return valueb73Pointers in C3&a%espOffsetStack43b74Data Manipulation75Ar

40、ithmetic and Logical OperationsInstructionEffectDescriptionleal S, DD &SLoad effective addressincl DD D + 1Incrementdecl DD D 1Decrementnegl DD -DNegatenotl DD DComplementaddl S, DD D + SAddsubl S, DD D SSubtractimull S, DD D * SMultiply76Arithmetic and Logical OperationsInstructionEffectDescription

41、xorl S, DD D SExclusive-ororl S, DD D | SOrandl S, DD D & SAndsall k, DD D kLeft shiftshll k, DD D kArithmetic right shiftshrl k, DD D kLogical right shift77Assembly Code for Arithmetic Expressionsint arith(int x, int y, int z) int t1 = x+y; int t2 = z*48; int t3 = t1&0 xFFFF; int t4 = t2*t3; return

42、 t4;movl 12(%ebp),%eaxGet ymovl 16(%ebp),%edx Get zaddl 8(%ebp),%eaxCompute t1=x+yleal (%edx,%edx,2),%edx Compute 3*zsall $4,%edxCompute t2=48*zandl $0 xFFFF,%eaxCompute t3=t1&FFFFimull %edx,%eaxSet t4 as return val78Special Arithmetic Operationsimull SR%edx:R%eax S*R%eaxSigned full multiplymull SR%

43、edx:R%eax S*R%eaxUnsigned full multiplyCltdR%edx:R%eax SignExtend(R%eax)Convert to quad wordidiv SR%edx R%edx:R%eax mod SR%eax R%edx:R%eax SSigned dividedivl SR%edx R%edx:R%eax mod SR%eax R%edx:R%eax SUnsigned divide79Conditional Codes & Control flow80摘要條件碼寄存器組成設置（隱私、顯示）使用跳轉指令C程序控制流翻譯if，循環，switchLab

44、el在binary中的表示81Assembly Programmers ViewFFBF7F3FC0804000StackDLLsTextDataHeapHeap08%eax%edx%ecx%ebx%esi%edi%esp%ebp%al%ah%dl%dh%cl%ch%bl%bh%eip%eflagAddressesDataInstructions82Condition codesCondition codesA set of single-bitMaintained in a condition code registerDescribe attributes of the most rece

45、ntly arithmetic or logical operation83Condition codesEFLAGSCF: Carry FlagOF: Overflow FlagZF: Zero FlagSF: Sign Flag84Setting Conditional CodesImplicit Setting By Arithmetic Operationsaddl Src,DestC analog: t = a+bCF set if carry out from most significant bitUsed to detect unsigned overflowZF set if

46、 t = 0SF set if t 0 & b0 & t0) | (a0 & b=0)85Setting Conditional CodesImplicit Setting By Arithmetic Operationsaddl Src,DestExplicit Settingcmpl Src2,Src1 cmpl b,a like computing a-b without setting destinationtestl Src2,Src1testl b,a like computing a&b without setting86Accessing Conditional CodesIn

47、structionSynonymEffectSet ConditionSeteSetzZFEqual/zeroSetneSetnzZFNot equal/not zeroSetsSFNegativeSetnsSFNonnegativeSetlSetngeSFOFLessSetleSetng(SFOF)|ZFLess or EqualSetgSetnle(SFOF)&ZFGreaterSetgeSetnl(SFOF)Greater or EqualSetaSetnbeCF&ZFAboveSetaeSetnbCFAbove or equalSetbSetnaeCFBelowSetbeSetnaCF

48、|ZFBelow or equal87Unconditional jumpJumps unconditionallyDirect jump: jmp labeljmp .LIndirect jump: jmp *Operandjmp *%eaxjmp *(%eax)88Conditional jumpEither jump or continue executing at the next instruction in the code sequenceDepending on some combination of the condition codesSuch as jl, jge, jb

49、, etc.All direct jump89Control Constructs in CGotosgoto LbreakcontinueBranchif () else switch () 90Control Constructs in CLoopwhile () do while ()for (init; test; incr) 91Translating Conditional Branches if ( test-expr ) then-statement elseelse-statement t = test-expr ; if ( t )goto true ; else-stat

50、ement goto done true:then-statement done:92Translating Conditional Branches int absdiff(int x, int y) if (x y) return y x; else return x y; int absdiff(int x, int y) int rval ; if (x y) goto less rval = x y ; goto done; less: rval = y x; done: return rval;93Jump Instructions movl 8(%ebp), %edx get x

51、 movl 12(%ebp), %eax get y cmpl %eax, %edx cal x - y jl .L3 if x y goto less subl %eax, %edx compute x - y movl %edx, %eax set return val jmp .L5 goto done.L3:less: subl %edx, %eax compute y x .L5:done: Begin Completion code94Do-while Translation do body-statement while (test-expr) loop: body-statem

52、ent t = test-expr; if ( t )goto loop ;95While Loop Translation while (test-expr) body-statement loop:if ( !test-expr) t = test-expr goto done;if ( !t )dogoto done; body-statementbody-statementwhile(test-expr)goto loop; done: done:96For Loop Translation for ( init-expr; test-expr; update-expr)body-st

53、atementinit-expr;while ( test-expr ) body-statementupdate-expr; 97Conditional Move(a) Original C code1 int absdiff(int x, int y) 2 return x y ? y-x : x-y;3 (b) Implementation using conditional assignment1 int cmovdiff(int x, int y) 2 int tval = y-x;3 int rval = x-y;4 int test = x y;5 /* Line below r

54、equires6 single instruction: */7 if (test) rval = tval;8 return rval;9 98Conditional Move(c) Generated assembly code x at %ebp+8, y at %ebp+121 movl 8(%ebp), %ecx Get x2 movl 12(%ebp), %edx Get y3 movl %edx, %ebx Copy y4 subl %ecx, %ebxCompute y-x5 movl %ecx, %eax Copy x6 subl %edx, %eax Compute x-y

55、 and set as return value7 cmpl %edx, %ecx Compare x:y8 cmovl %ebx, %eax If 6 ) goto loc_def ; /defaultgoto jtxi; loc_a: /100result *= 13 ;goto done ;loc_b: /102result += 10 ; /* fall through*/loc_c: /103result +=11; goto done ; loc_d: /104, 106result *= result ;goto done ; loc_def: /defaultresult =

56、0 ; done:return result ; code jt7 = loc_a, loc_def, loc_b, loc_c, loc_d, loc_def, loc_d;106Code Layoutkernel virtual memoryRead only codeRead only dataRead/write dataforbiddenmemory invisible to user codeLinux/x86processmemory image0 xffffffff0 xc00000000 x08048000%eipJump Table .section .rodata .al

57、ign 4 .L7: .long .L3case 100: loc_a .long .L2case 101: loc_def .long .L4case 102: loc_b .long .L5case 103: loc_c .long .L6case 104: loc_d .long .L2case 105: loc_def .long .L6case 106: loc_d107108Jump Table Implementation movl8(%ebp), %edxget x movl12(%ebp), %eaxget n subl$100, %eaxcompute index = n

58、100 cmpl$6, %eaxcompare index:6 ja.L2If , goto default jmp *.L7(, %eax, 4) .L2:default: mov $0, %eaxresult = 0jmp .L8goto done109Jump Table Implementation .L5:loc_c: / 103 movl%edx, %eaxresult = x jmp.L9goto rest .L3:loc_a: / 100 leal(%edx, %edx, 2), %eaxresult = x * 3 leal(%edx, %eax, 4), %eaxresul

59、t = x + 4 * result jmp.L8goto done .L4:loc_b: / 102 leal 10(%edx), %eaxresult = x + 10110Jump Table Implementation .L9:rest: / fall through addl$11, %eaxresult += 11 jmp.L8goto done .L6:loc_d: / 104, 106 movl%edx, %eaxresult = x imull%edx, %eaxresult *= x .L8:done:111Jump Targets in BinaryTwo forms

60、to represent a jump targetPC-relative Jump target is an offset relative to the address of the instruction just followed jump (pointed by PC)Absolute address Jump target is an absolute address112Examplejle .L2.L5:movl %edx, %eaxsarl $1, %eaxsubl %eax, %edxLeal (%edx, %edx, 2), %edxtestl %edx, %edxjg