Machine Problem 5, due at the end of Apr 15
Part of
the homework for CS:2630, Spring 2024
|
A problem:
The following file contains a shell archive:
https://homepage.cs.uiowa.edu/~dwjones/assem/hw/mp5shar.txt
This shell archive contains:
However, the body of the file liststack.a is mostly missing.
The Makefile supports make demo which will assemble, link and launch the Hawk emulator and waiting for you to hit the r key to actually make the code run. Of course, it will only work if you provide the code missing from liststack.a.
Your assignment is to write the code that is missing in liststack.a. This code must implement stacks using linked lists, where pushing a word on the list-stack involves a call to MALLOC to create a new list item and popping a value from the list-stack involves a call to FREE to deallocate the node that held the popped value. Each object representing a list stack will hold a list head plus any other fields needed to implement it.
You must create a directory (call it mp5) to hold your project, and then install the shell archive there before you can begin work.
Eventually, the only code you submit will be your code in liststack.a.
Your should not change any other files in the project, but you will almost certainly need to explore them. Feel free to use the organization of the code from arraystack.a. Your code will need to conform to the interface specificaiton given in stack.h and liststack.h. Your code will need to work when used by main.a.
Grading: 5 points. Correct output is worth 2.5 points. The remaining credit will be offered only for those who have correct output.
Code that does not assemble will not earn any credit.
Code that still says YOUR NAME HERE in the title will be discarded.
Stylistically clean code is important; that is why half the credit is reserved for style, but only if the code works. When integrating your code into a larger pre-existing project, it is always a good idea to try to match the style of the pre-existing code so your contribution blends into it. There should be no need to duplicate the nitpicking style requirements from previous assignments here. They still apply.
Submission: To submit your work, it must be in a file named liststack.a in your mp5 directory on the CLAS Linux system, and you must know your section number. Make sure mp5 is the current directory. In the following, what you type is shown in bold face. Begin at the linux command-line prompt:
[HawkID@fastx?? ~]$ ~dwjones/submit 0A0X liststack.a
Note: The ~dwjones must be verbatim, do not substitute another name. Also, use your section number (one of 0A01 to 0A05).
In the event of insurmountable trouble, do not delete or edit files you have submitted until the graded work is returned. The operating system record of the last edit time and date and the backups maintained by the operating system are proof of what you did and when, and they allow us to investigate what happened. until your graded work is returned. This way, the time stamp marking the time of last edit is a trustworthy indicator of whether you did the work on time.
Note: Up until now, we have been able to assume that your code begins at address 100016 so all you had to do in order to convert between addresses in your listing and addresses in your code is add 100016 to the address in your code. This has been particularly important in interpreting bus traps and other error messages.
Now that our project requires multiple object files that are combined by the linker, this doesn't work. Note that the linker has an option that is very useful in this context. If you run hawklink -help, it will output its command line options. One of these in quite useful. The hawklink -d option causes the linker to output a dump of all the symbols it knows about.
If you add this linker option to the hawklink command in Makefile, the linker will create not only stackdemo.o (the executable object file), but also stackdemo.d, a dump showing the values of all the symbols known to the linker.
The annoying thing about this dump is that it shows all the symbols, not just the ones you care about. You get the addresses of every Hawk monitor routine, the addresses of all your external symbol. External symbol names are always prefixed with R, so look for RMAIN and RNEWARRAYSTACK for the main program and the constructor for array stacks. Assuming you put your list-stack constructor at the start of your code, the value of RNEWLISTSTACK will tell you where your code begins. Since you're not editing the other files in the project, this will tend to be the same from one make to the next.
If I used:
MACRO NODE data,next W data W next ENDMAC
Would this work for creating nodes in my list-stack class?
No. That macro will create nodes in ROM that can never be changed. Your list stack must create nodes in RAM in response to requests to push and pop data. You based your proposed macro on the macro used to create a constant tree in the tree demo distributed on Feb. 20. That demo traversed a constant tree. Everything else in that demo is relevant, including the way the fields of tree nodes are declared right before the macro, but you will have to dynamically create tree nodes using MALLOC.
In my list-push code, I need to call MALLOC, which I assume is modifying registers 3-7 when it is called. Therefore, I need to store the parameters from R3 and R4 in the activation record. I thought I do this using the activation record for NEWLISTSTACK, since the list push, pop, and empty methods do not have their own activation records -- that is, they are not their own subroutines. Is this right?
Each callable subroutine, function or method, whatever you call it, is entitled to its own activation record, if it needs one. NEWLISTSTACK is directly callable from the outside world. The PUSH, POP and EMPTY methods are callable indirectly, through the stack object, but they are very much callable and entitled to have any local variables they may individually need. These should be declared in their own activation records.
Note that the ARRAYSTACK PUSH, POP and EMPTY methods did not need their own activation records because they could completely accomplish their jobs using only R3 to R7. They did not even store their return addresses on the stack because they never needed R1. You are right that you can't make this optimization in any code that calls MALLOC or FREE.
I would like to be able to see where my code in liststack.a starts. I am trying to follow the instructions for adding a hawklink -d option to the Makefile, but I am not sure what to add.
There are two ways to do this that have the same net effect. You can change the definition of hawklink to this:
hawklink=~dwjones/bin/hawklink -d
Or, you can change the actual invocation of the linker with this:
$(hawklink) -d -o stackdemo main.o arraystack.o liststack.o
Do not do both. Either one has the same net effect. You might also want to change make clean so it deletes the stackdemo.d.
Should I create a variable in my activation record to keep track of what each node in the linked list points to?
A variable in your activation record is just a local variable, akin to a local variable in C, C++, Java, etc. Would you create a local variable in your activation to keep track of this for each node if you were programming in one of those languages?
Keep in mind that activation records are allocated on entry to a called routine and they are deallocated on exit. Nothing in the activation record exists between calls to a subroutine, and methods of a class are a kind of subroutine. When you call s.push(v), the value v is pushed on the stack s, then the local variables go away, but the stack s still exists. When you call s.pop(), the value v you pushed earlier is returned. Therefore, local variables cannot have any role in the long-term storage of the stack.
Local variables only matter between the time a routine is called and the time it returns. They are temporary places to keep things that can't be stored in registers.
Or is there another way to go about this?
There certainly is. First, if you were a Java programmer, you'd be asked 'what classes do I need to solve this problem?' Your first class is obviously linked-list-stack, since you need to create that subclass of stack. But what other class do you need? It's a private one, nobody outside of your code ever needs to know it exists, but you've already named it. You called it class node. So you're going to be using MALLOC to get linked-list-stack objects, but you're also going to be using it to get node objects.
I am getting this error when I do a make:
~dwjones/bin/hawklink -o stackdemo main.o arraystack.o liststack.o
7 value out of bounds B R
7 value out of bounds B R
I've included my source code. What does this mean?
Your error message comes from the hawk linker. The problem is that, somewhere in your code, you had a one-byte field (the B in the error message) that referenced relocatable address zero (the R in the error message). That address (probably a ROM address in the range from 100016 to FFFF16) would not fit in one byte. I looked at your code and found this at the start:
; each list node will hold a data word and pointer to next node
NODE:
DATA = 0 ;Data field
NEXT = 4 ;Next field
This is well-intentioned code to describe one node in a linked list, but the label NODE is really more of a comment, since list nodes have no address in ROM, which is where your code goes. Later, I found this:
LIS R5, NODE ;Parameter (size of node)
LIL R1, MALLOC
JSRS R1, R1 ;Allocate new node
The LIS R5,NODE is the source of the linker error, but there are more errors here. The comment hints at one of them. The parameter should be the constant size of the node, not a label on a memory location. Just like we have ARSIZE for the size of an activation record, and the array-stack code had OBJSIZE for the size of an array-stack object, this code needs something like NODESIZE for the size of a list-node object.
Also, the call to MALLOC is ignoring the register use that MALLOC requires for its parameters. For some reason, the code tries to pass the size of a node in R5, where MALLOC expects this in R3.
My code is compiling but nothing is being output. I don't know where I'm going wrong.
You might want to study the main program and look for paths through the code that produce no output. The main program code is there for you to read!
Since all pushes and pops in the main program are in groups of three, one on each stack, all stacks should be empty when any one stack is empty. The program checks that this is true, so if you get the message "stacks not all empty," you probably have a stack that is prematurely empty or a stack where popping did not empty it.
The way to get no output at all is to have a pop method that returns a zero or negative value instead of the strictly positive value that was pushed.
My push function "works" (doesn't throw any error), but when the test program cycles through and calls it again, it gives the error mesage "MALLOC() called from 0000121C; when heap corrupted." What is going on?
The "heap corrupted" error poses a challenge. The message comes from MALLOC because that is where the corruption is detected, but the corruption almost certainly happened elsewhere before the call to MALLOC.
The heap gets corrupted when you change something in the heap outside the bounds of the objects you have currently allocated (but not yet freed). You might do this by freeing an item and then altering its contents, by allocating less memory than an object needs, or by using an uninitialized index register to access memory.
Looking at the code you sent with your question, I think you did the latter. When your code called MALLOC, R4 to R7 are wiped out, probably used to hold addresses of blocks in the heap while MALLOC searched for a big enough free block. Then your code used R5 as an index register to update some field of an object you were intending to manipulate, having forgotten to save things in your activation record.