CS2106- Tutorial 1: Process Abstraction Solved

[Function invocation – the gory details] Let's use a "simple" function to really understand the idea of stack frames and calling conventions. Note that the stack frame layout in this question is slightly different from the one covered in lecture 2. So, ensure you have a good understanding of the basics before attempting this question.
Given below is an iterative factorial function in C.

 

C
int iFact( int N ) 

{    

     int result = 1, i; 

 

     for (i = 2; i <= N; i++){          result = result * i; 

     }  

     return result; 

}
 

[Code translation] Take a look at the partial assembly code translation on pages 4 & 5. You should find most of it (vaguely) familiar from your basic assembly programming course. The remaining missing pieces are all related to the function call (setup/tear down of stack frame).
 

Suppose the following stack frame is used on this platform. For simplicity, all integers and registers are assumed to occupy 4 bytes, and the stack region is "growing" towards lower address.

      

Unused Stack Memory Space
Local Variable
-36
[result]
-32
[i]
Parameter
-28
[N]
Return Result 
-24
 
Saved Registers 
-20
[$11]
-16
[$12]
-12
[$13]
Saved SP
-8
 
Saved FP
-4
 
Saved PC
 0
 
-- Stack Pointer ($sp)

 

 -- Frame Pointer ($fp)

 

Complete the memory offsets in the lw/sw instructions (they are tagged with "Part a").  You can assume that the $sp and $fp registers are initialized properly. 

 

[Stack frame – caller prepares to call a function] Refer to the calling convention sample given in lecture 2. Assume we make the following function call iterativeFactorial( 10 ) from the main()
 

Essentially, you need to:

Pass the parameter ("10") onto the stack.
Save the PC to return to on the stack. For simplicity, we assume there is a "call function offset(register)" This instruction saves the next PC to the memory address specified by "offset(register)", then jumps to the specified "function".
Complete the relevant portions tagged with "Part b".

 

[Stack frame – callee enters function] Now, let us fill in the instructions for the callee to setup the stack frame upon entering the function. Tasks required:Save the registers used in the caller (i.e. $11-$13).
Save the current FP, SP registers on the stack.
Allocate space for local variables, i.e. "Result", "i".
Adjust the special registers FP, SP.
 

[Stack frame – callee exits function] At the end of the function, we need to:Place the return result onto stack frame.
Restores the saved registers, FP, and SP.
Return to the caller with the saved PC. For simplicity, we assume there is a "return offset(register)" instruction, which overwrites the PC with the value stored at the memory location "offset(register)".
With (d), we now have a complete demonstration of the idea of stack frames, calling conventions and the usage of stack / frame pointers. 

[Extra challenge – not discussed] Draft a solution for a recursive version of  The bits and pieces from (a), (c) and (d) are very similar, the only tricky part is that the recursive factorial function is both a caller and a callee… So, figuring out where (b) should be placed is the main challenge.
Notes: To illustrate a generic calling convention, we have to provide several made-up instructions, e.g. call and return. Feel free to explore other real calling conventions on different platforms, e.g. Intel x86, MIPS, etc, for different languages, e.g. C/C++, Python and Java on JVM.  You should be able to see the same ideas echoed across different environments. 

MIPS-like Assembly Code
iFact: 

      #Part (c) – Callee enter function

                              #save registers        

                              #save $fp, $sp

        

                              #move $fp, $sp to  

                              #     new position

      #Part (c) – Callee enter function ends

 

      addi $11, $0, 1         #init "result"       sw   $11, ____($fp)     ##Part (a) result = 1 

 

      addi $12, $0, 2         #init "i"       sw   $12, ____($fp)     ##Part (a) i = 2

 

      lw   $13, ____($fp)     ##Part (a) Get N loop: bgt  $12, $13, end 

       

      mul  $11, $11, $12      #assume no overflow       sw   $11, ___($fp)      ##Part (a) update result 

 

      addi $12, $12, 1 

      sw   $12, ___($fp)      ##Part (a) i++       j loop 

 end:   

      #Part (d) – Callee exit function       

                              #save return result  

                              #restore registers

        

 

                              #restore $sp, $fp

         

      return         #resume execution of the caller          

 

 #Continues on the next page

 

 

### Main Function 
main: 

    ......                #irrelevant code omitted  

#Part (b) – Caller prepare to call function     addi  $13, $0, 10     #Use $13 to store 10 sw                    #Where should the "10" go?

    call iFact,        #start executing the function 

 

[Functions and stack – AY1819S1 Midterm] In many programming languages, function parameter can be passed by reference. Consider this fictional C-like language example:
Mr. Holdabeer feels that he has the perfect solution that works for this example by relying on stack pointer and frame pointer. The key idea is to load main's local variable "myInt" whenever the variable "i" is used in the change() function.

Given that the stack frame arrangement shown independently as follows:

 

For Main()
For change()
 
 
ç $SP 

 

 

ç $FP 
 

 
 
ç $SP 

ç $FP 
…
…
Saved SP
-8
myInt 
-12
Saved FP
-4
Saved SP
-8
Saved PC
0
Saved FP
-4
 
Saved PC
0
 

Suppose the main()'s and change()'s stack frame has been properly setup, and change() is now executing, show how to store the value "1234" into the right location. You only need pseudo-instructions like below. [3 marks]
Register_D ß Load Offset( Register_S )
Load the value at memory location [Register_S] + Offset and put into

Register_D

e.g. $R1 ß Load -4($FP)

Offset(Register_S) ß Store Value
Put the value into memory location [Register_S] + Offset, e.g. -4($FP) ß Store 1234

Briefly describe another usage scenario for pass-by-reference parameter that will not work with this approach.
Briefly describe a better, universal approach to handle pass-by-reference parameter on stack frame. Sketch the stack frame for the change() function to illustrate your idea.
[Process state] Suppose we compile and execute the following C code. Using the 5-state process model, trace the corresponding process state transitions for the executable (“exe”) produced from the code below.
int main() 

{ 

    int input, result; 

 

    // will either cause a state transition?

    printf(“Give input below:\n”);     scanf(“%d”, &input); 

 

    // takes a long time – math operations only     result = ComplexFunc( input );  

      

    // write result to disk     saveToDisk( result );

   printf(“Result is %d\n”, result); 

 

  return 0; 

}
 

Discussion question if time permits:  

[Process control block] Question 1 focuses on the use of stack memory within a single program. Let us take a step back and look at multiple executing programs. Suppose we execute the program containing the factorial function twice and both processes run in parallel (i.e. exist at the same time). Draw the PCBs of the two processes (similar to lecture 2’s slide on PCBs), indicate clearly what is laid out in the physical memory and how the different memory regions of a process fit together.
Additional exercise question if time permits:  

 

[MIPS and stack frames – a refresher] A snapshot of the current state of a program’s stack (along with the current locations of the stack and frame pointer) is given below. In this example, the second column refers to the difference in memory address from the Saved PC, and the third column refers to the value currently at that position. For simplicity, all integers and registers are assumed to occupy 4 bytes, and the stack region is "growing" towards lower addresses.
From this state, we execute a few MIPS-like instructions. Assume we have a function named print which prints the value in register $1. We can call it using: call print. What would be printed as a result of running each set of instructions? If there is no clear answer, state precisely why. 

Also, recall that the second parameter of the lw/sw instruction has the form of offset(register), e.g.  -12($fp) == (content of register $fp) - 12.

(Each sub-part of this question is independent, e.g.  b) behaves like a) never happened, and so on)

Unused Stack Memory Space
Local Variable
-36
22
-32
8
Parameter
-28
16
Return Result 
-24
7
Saved Registers 
-20
9
-16
1
-12
3
Saved SP
-8
not relevant 
Saved FP
-4
not relevant
Saved PC
 0
not relevant
 -- Stack Pointer ($sp)

 -- Frame Pointer ($fp)

 
 

MIPS-like Assembly Code
      lw   $1, 0($sp)       call print  
 

 
MIPS-like Assembly Code
      lw   $2, -16($fp)        add  $sp, $sp, $2        lw   $1, 0($sp)       call print  
 
 

MIPS-like Assembly Code
      lw   $sp, -16($fp)        lw   $1, 0($sp)       call print