Computer System II Assignment 10 and 11 (200 points) Solution

$30.00

Description

References

http://cfaq.com

https://cdecl.org

Intel 64 and IA-32 architectures software developer’s manual combined volumes 2A, 2B, 2C, and 2D: Instruction set reference, A-Z

2 Any and All

(20 x 2 = 40 points) Implement the following macros in a header, macros.h:

1. Macro TEST IF ANY SET(v, start, end) that tests if any of the bits between indices

start and end (inclusive) in vector v is set.

2. Macro TEST IF ALL SET(v, start, end) that tests if all of the bits between indices start and end (inclusive) in vector v are set.

This is along the lines of what you did in a previous lab. If you need to implement helper macros, you are free to do so. You are guaranteed that when the macro is tested, the start index will be greater than or equal to the end index.

2.1 Examples

Macro

v

start

end

Evaluates

TEST IF ANY SET

0xDEADBEEFDEADBEEF

63

0

1

TEST IF ALL SET

0xDEADBEEFDEADBEEF

63

0

0

TEST IF ANY SET

0xDEADBEEFDEADBEEF

35

32

1

TEST IF ALL SET

0xDEADBEEFDEADBEEF

35

32

1

TEST IF ANY SET

0xDEADBEEFDEADBEEF

7

4

1

3 Rotate

(80 points) Implement a function unsigned long rotate(unsigned long val, unsigned long num, unsigned long direction); using 64-bit Intel x86 assembly in rotate.S. The direction is 0 or 1 where 0 implies right and 1 implies left. The function implements

a rotate right/left operation. It is expected to shift val right or left (depending on direc- tion) num number of times with a rotate behavior. This means that the bit that is shifted out through left shift (the most-significant bit) is brought back in as the least-significant bit, and the bit that is shifted out during right shift (the least-significant bit) is brought back as the most-significant bit.

3.1 Examples

Val

Num

Direction

Output

0xDEADBEEFDEADBEEF

2

1

0x7AB6FBBF7AB6FBBF

0xDEADBEEFDEADBEEF

2

0

0xF7AB6FBBF7AB6FBB

0xDEADBEEFDEADBEEF

66

1

0x7AB6FBBF7AB6FBBF

0X1

1

0

0x8000000000000000

3.2 Hints

NOTE: rotate(val, num, direction) is the same as rotate(val, num%64, direction).

You are guaranteed that direction is either 0 or 1.

val and num can be any unsigned long number.

4 Backtracing

(80 points) Declare a function prototype void print backtrace(int count) in bt.h and implement a function definition in file bt.c. This function will print no more than count number of return addresses in preceding calling functions or up to main, whichever smaller. The call trace should be similar to what is obtained when we type bt on gdb, except the following:

This function will not print the names of the functions in the trace, just the return addresses in the callee functions.

This function will not print the instruction pointer’s address (#0 in GDB).

You are free to implement helper functions. You are guaranteed that all functions in the program will use frame pointer, and that main() will have a single ret instruction.

4.1 Example

For example, the following source code in main.c

1 #i n c l u d e < s t d i o . h>

#i n c l u d e b t . h

3

v o i d b a z ( ) {

5 p r i n t b a c k t r a c e ( 4 ) ;

}

7

v o i d b a r ( ) {

9 b a z ( ) ;

}

11

v o i d f o o ( ) {

13 b a r ( ) ;

}

15

i n t main ( i n t a r g c , c h a r a r g v [ ] ) {

17 f o o ( ) ;

r e t u r n 0 ;

19 }

produces the disassembly

1 . . .

4 0 0 5 3 e <b az >:

3 . . .

4 0 0 5 4 7 : e 8 da f f f f f f c a l l 4 0 0 5 2 6 < p r i n t b a c k t r a c e >

5 4 0 0 5 4 c : 9 0 nop

. . .

9

4 0 0 5 5 8 : e 8 e 1 f f

f f

f f

c a l l

4 0 0 5 3 e

<b az>

4 0 0 5 5 d : 9 0 nop

11

. . .

4 0 0 5 6 0 <f o o >:

13 . . .

4 0 0 5 6 9 : e 8 e 1 f f f f f f c a l l 4 0 0 5 4 f <b a r>

15 4 0 0 5 6 e : 9 0 nop

. . .

17 4 0 0 5 7 1 <main >:

. . .

19 4 0 0 5 8 5 : e 8 d6 f f f f f f c a l l 4 0 0 5 6 0 <f o o >

4 0 0 5 8 a : b8 0 0 0 0 0 0 0 0 mov e a x , 0 x0

21 . . .

. . .

Your implementation of print backtrace would then produce the following output:

#1

0 x 0 0 0 0 0 0 0 0 0 0 4 0 0 5 4 c

2

#2

0 x 0 0 0 0 0 0 0 0 0 0 4 0 0 5 5 d

#3

0 x 0 0 0 0 0 0 0 0 0 0 4 0 0 5 6 e

4

#4

0 x 0 0 0 0 0 0 0 0 0 0 4 0 0 5 8 a

Note that there is a horizontal tabulation character (\t) between the number and the return address, and each return address is right-justified with zeroes such that it is always

18 characters wide (i.e. 0x followed by 16 hex digits forming the address).

4.2 Hint

A backtrace is nothing but the sequence of return addresses in the preceding stack frames. A couple of points to note:

1. The return address (in the calling function) is stored on the stack.

2. On entry to each function, the old frame pointer (rbp register) is pushed on to the stack (its position is right after the return address).

3. In any given function, the return address is always stored at [rbp+8] and the base pointer of the calling frame is always stored at [rbp].

4.3 Strategy

1. As a first step, find the bounds of main function (you may do this in a separate function). Start from address of main, and start reading bytes until you hit the return instruction. Note the address of the return instruction. The start of main function and the address of the return instruction form the bounds of main function.

2. The goal now is to print count number of return addresses in the preceding frames, or until you hit a return address that is inside main function. So:

curr_rbp <- get current rbp while count > 0:

ret_addr <- get current return address which is in [curr_rbp + 8]

print ret_addr

if ret_addr is an address in main:

return

curr_rbp <- get rbp for previous frame, which is in [curr_rbp]

decrement count

3. So, how would you get the current base pointer? You have 2 choices. (1) Implement an assembly function that will move rbp into raxand return, or (2) look at the address of count and infer the address to which rbp points.