Description

5/5 - (2 votes)

1    References

 

 

 

 

 

 

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.

 

  1. 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.

 

  1. 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).

 

  1. 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.

 

  1. 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

 

 

  1. 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.