In this part of the assignment, you will attempt to debug and fix a program written in C.
Read the following C program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
///////
// This code implements a very simple version of malloc.
// It is correct and can be ignored while answering this quesiton.
// We are using it to simplify the debugging process.
char my_heap[4096];
int my_heap_cur = 0;
void* my_malloc(int nbytes) {
void* result = &my_heap[my_heap_cur];
my_heap_cur += nbytes;
return result;
}
// The bug is below this line.
/////////
char *names[10];
int num_names = 0;
void add_name(char *name) {
// Allocate space for a copy of the name
names[num_names] = my_malloc(sizeof(name));
// Copy name to new area in memory
strcpy(names[num_names], name);
// Add one to num_names
num_names++;
}
void print_names(void) {
for (int i = 0; i < num_names; i++) {
printf("Name %d: %s\n", i + 1, names[i]);
}
}
int main(void) {
add_name("John Alexander Macdonald");
add_name("Alexander Mackenzie");
add_name("John Joseph Caldwell Abbott");
add_name("John Sparrow David Thompson");
add_name("Mackenzie Bowell");
add_name("Charles Tupper");
add_name("Henri Charles Wilfrid Laurier");
add_name("Robert Laird Borden");
add_name("Arthur Meighen");
add_name("William Lyon Mackenzie King");
print_names();
return 0;
}
Based on your analysis of the program above, what is the intended output of the program?
Name 1: John Alexander Macdonald Name 2: Alexander Mackenzie Name 3: John Joseph Caldwell Abbott Name 4: John Sparrow David Thompson Name 5: Mackenzie Bowell Name 6: Charles Tupper Name 7: Henri Charles Wilfrid Laurier Name 8: Robert Laird Borden Name 9: Arthur Meighen Name 10: William Lyon Mackenzie King
Now compile and run your program.
After running the program, what did it actually print out? NOTE: The error in this program can cause different kinds of side effects in different operating systems or environments. To ensure consistency, please provide the output generated by this program in one of the department's Linux servers.
Name 1: John AleAlexandeJohn JosJohn SpaMackenziCharles Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 2: AlexandeJohn JosJohn SpaMackenziCharles Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 3: John JosJohn SpaMackenziCharles Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 4: John SpaMackenziCharles Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 5: MackenziCharles Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 6: Charles Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 7: Henri ChRobert LArthur MWilliam Lyon Mackenzie King Name 8: Robert LArthur MWilliam Lyon Mackenzie King Name 9: Arthur MWilliam Lyon Mackenzie King Name 10: William Lyon Mackenzie King
In the previous question, you found out that the namelist program doesn't produce the expected output. Now, your job is to fix the problem that caused the mismatch. Load the program into a debugger using the following command:
gdb namelist
(or lldb namelist on macOS). Add a breakpoint inside your program (e.g., use b main to stop at the first line of function main). To run the program, type run. If it hits a breakpoint, gdb will pause execution so you can decide what to do next.
At this point, you can use s ("step", step into functions) or n ("next", jump over functions) to navigate through the code. At some points of the code you may want to print the values of specific variables (e.g., p num_names to print the value of num_names), to identify when a change that could affect the output happened.
If you are unable to step through lines on the code, your code may have been compiled without passing the -g option to gcc (that option adds debug symbols).
Through the analysis of the program in gdb, you are expected to identify at which point the value of the variables used in the output is changed to something different than expected. What is the name of the function where this change happens? Focus on the most specific function that is part of this program's code (i.e., not a library function nor my_malloc).
add_name
By finding out which function causes the change of values, you have narrowed down the cause of the problem. This is an important step in debugging. Look at this line of code carefully.
Which of the following best describes the bug in this code?
add_name in main are incorrectmy_malloc only allocates the size of a char pointernames is wrongprint_names accesses the wrong indices in namesstrcpy are incorrectnum_names should not be incrementednames is not initialized with the correct number of elementsWith an idea of why it isn't working, you should be able to propose a fix to the program. Change the erroneous line of code to make the program work as expected. Hint: you only need to change a single line.
Produce a fixed version of the code which compiles, runs, and successfully outputs what you expected it to output in the first part of this set of questions. Submit this change below.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
///////
// This code implements a very simple version of malloc.
// It is correct and can be ignored while answering this quesiton.
// We are using it to simplify the debugging process.
char my_heap[4096];
int my_heap_cur = 0;
void *my_malloc(int nbytes) {
void *result = &my_heap[my_heap_cur];
my_heap_cur += nbytes;
return result;
}
// The bug is below this line.
/////////
char *names[10];
int num_names = 0;
void add_name(char *name) {
// Allocate space for a copy of the name
names[num_names] = my_malloc(strlen(name) + 1);
// Copy name to new area in memory
strcpy(names[num_names], name);
// Add one to num_names
num_names++;
}
void print_names(void) {
for (int i = 0; i < num_names; i++) {
printf("Name %d: %s\n", i + 1, names[i]);
}
}
int main(void) {
add_name("John Alexander Macdonald");
add_name("Alexander Mackenzie");
add_name("John Joseph Caldwell Abbott");
add_name("John Sparrow David Thompson");
add_name("Mackenzie Bowell");
add_name("Charles Tupper");
add_name("Henri Charles Wilfrid Laurier");
add_name("Robert Laird Borden");
add_name("Arthur Meighen");
add_name("William Lyon Mackenzie King");
print_names();
return 0;
}
The file BinaryTree.java contains a Java program that implements a simple, binary tree. Examine its code. Compile and run it from the UNIX command line (or in your IDE such as IntelliJ or Eclipse):
import static java.lang.System.out;
/**
* A runnable class that implements and tests an ordered binary tree of integer values.
*/
public class BinaryTree {
/**
* A node of the binary tree containing the node's integer value
* and pointers to its right and left children (or null).
*/
static class Node {
int value;
Node parent;
Node left;
Node right;
/**
* Create a new node with no children.
*/
Node (int value) {
this.value = value;
this.parent = null;
this.left = null;
this.right = null;
}
/**
* Insert the node n into the binary tree rooted by this node.
*/
void insert (Node n) {
if (n.value <= value) {
if (left==null) {
left = n;
n.parent = this;
} else {
left.insert(n);
}
} else {
if (right==null) {
right = n;
n.parent = this;
} else {
right.insert(n);
}
}
}
/**
* Print the contents entire binary tree in order of ascending integer value.
*/
void printInOrder() {
if (left != null)
left.printInOrder();
out.printf ("%d\n", value);
if (right != null)
right.printInOrder();
}
/**
* Print path of values from root to specified node in orderer starting from root.
* Each node in path indicates direction taken (i.e., left or right) from parent to arive at node.
*/
void printPath() {
if (parent != null) {
parent.printPath();
}
out.printf("%s: %d\n", parent == null? "from root": parent .left == this? "left to": "right to", value);
}
}
/**
* Create a new tree populated with values provided on the command line and
* print it in depth-first order.
*/
public static void main (String[] args) {
Node root = null;
// read values from command line and add them to the tree
Node lastNodeInserted = null;
for (String arg: args) {
int value = Integer.parseInt (arg);
Node n = new Node (value);
if (root == null)
root = n;
else
root.insert (n);
lastNodeInserted = n;
}
// print results
if (root != null) {
out.printf("In Order:\n");
root.printInOrder();
out.printf("Path to %d:\n", lastNodeInserted.value);
lastNodeInserted.printPath();
}
}
}
javac BinaryTree.java java BinaryTree 4 3 2 1
When the program runs, the command-line arguments (in this case the numbers 4, 3, 2 and 1) are added to the tree and then printed in depth-first order based on their value. You can provide an arbitrary number of values on the command line with any numeric values you like.
The file BinaryTree.c is a skeleton of a C program that is meant to do the same thing. Using the Java program as your guide, implement the C program. The translation is pretty much line for line, translating Java's classes/objects to C's structs.
#include <stdlib.h>
#include <stdio.h>
/**
* A node of the binary tree containing the node's integer value
* and pointers to its right and left children (or null).
*/
struct Node {
// TODO
};
/**
* Create a new node with no children.
*/
struct Node* create (int value) {
// TODO
return NULL;
}
/**
* Insert the node n into the binary tree rooted by toNode.
*/
void insert (struct Node* toNode, struct Node* n) {
// TODO
}
/**
* Print the contents entire binary tree in order of ascending integer value.
*/
void printInOrder (struct Node* node) {
// TODO
}
/**
* Print path of values from root to specified node in orderer starting from root.
* Each node in path indicates direction taken (i.e., left or right) from parent to arive at node.
*/
void printPath (struct Node* node) {
// TODO
}
/**
* Create a new tree populated with values provided on the command line and
* print it in depth-first order.
*/
int main (int argc, char* argv[]) {
struct Node* root = 0;
// read values from command line and add them to the tree
struct Node* lastNodeInserted = NULL;
for (int i=1; i<argc; i++) {
int value = atoi (argv [i]);
struct Node* node = create (value);
if (i==1)
root = node;
else
insert (root, node);
lastNodeInserted = node;
}
// print results
if (root) {
printf("In Order:\n");
printInOrder (root);
printf("Path to %d:\n", 0); // TODO: replace 0 with expression that gets value of lastNodeInserted
printPath(lastNodeInserted);
}
}
Note that since C is not object-oriented, C procedures are not invoked on an object (or a struct). Thus, Java instance methods converted to C have an extra argument: a pointer to the object on which the method is invoked in the Java version (i.e., what would be "this" in Java).
Of course, C also doesn't have new; for this you must use malloc. Note that all that malloc does is allocate memory; it does not do the other things a Java constructor does such as initialize instance variables. C also doesn't have "null"; for this you can use NULL or 0.
Finally, C doesn’t have out.printf, use printf instead. Your goal is to have the C program produce the same exact output as the Java program for any inputs.
You will also need to provide a Makefile to compile your new C program into the program BinaryTree. You may use the Makefile provided in previous questions as a basis. Please try to compile the program with your Makefile before submitting it.
You might follow these steps:
Node struct. Note that like a Java class, the struct lists the instance variables stored in a node object; i.e., value, left, and right. Note that in Java left and right are variables that store a reference to a node object. Consult your notes to see how you declare a variable in C that stores a reference to a structcreate procedure that calls malloc to create a new struct Node, initializes the values of value, left, and right, and returns a pointer to this new node. Then call this procedure to allocate one node with the value 100 and declare a variable root to point to it.printInOrder and compile and test your program to print this one node. Do not proceed to the next step until it works.insert. You may test it by inserting two child nodes to root: one with value 50 and one with value 150. So, now you have a tree with three nodes. Also review printInOrder so that, when you call printInOrder on root, you should get the output 50 100 150.main to insert nodes into the tree with values that come from the command line instead of the hardcoded values 50, 100, and 150. Test it again and celebrate.#include <stdlib.h>
#include <stdio.h>
/**
* A node of the binary tree containing the node's integer value
* and pointers to its right and left children (or null).
*/
struct Node {
int value;
struct Node* parent;
struct Node* left;
struct Node* right;
};
/**
* Create a new node with no children.
*/
struct Node* create (int value) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->value = value;
node->parent = NULL;
node->left = NULL;
node->right = NULL;
return node;
}
/**
* Insert the node n into the binary tree rooted by toNode.
*/
void insert (struct Node* toNode, struct Node* n) {
if (n->value <= toNode->value) {
if (toNode->left != NULL) {
insert(toNode->left, n);
return;
}
toNode->left = n;
n->parent = toNode;
return;
}
if (toNode->right != NULL) {
insert(toNode->right, n);
return;
}
toNode->right = n;
n->parent = toNode;
}
/**
* Print the contents entire binary tree in order of ascending integer value.
*/
void printInOrder (struct Node* node) {
if (node == NULL) return;
if (node->left != NULL) printInOrder(node->left);
printf("%d\n", node->value);
if (node->right != NULL) printInOrder(node->right);
}
/**
* Print path of values from root to specified node in orderer starting from root.
* Each node in path indicates direction taken (i.e., left or right) from parent to arive at node.
*/
void printPath (struct Node* node) {
if (node->parent != NULL) {
printPath(node->parent);
}
if (node->parent == NULL) {
printf("from root");
} else if (node->parent->left == node) {
printf("left to");
} else {
printf("right to");
}
printf(": %d\n", node->value);
}
/**
* Create a new tree populated with values provided on the command line and
* print it in depth-first order.
*/
int main (int argc, char* argv[]) {
struct Node* root = 0;
// read values from command line and add them to the tree
struct Node* lastNodeInserted = NULL;
for (int i=1; i<argc; i++) {
int value = atoi (argv [i]);
struct Node* node = create (value);
if (i==1)
root = node;
else
insert (root, node);
lastNodeInserted = node;
}
// print results
if (root) {
printf("In Order:\n");
printInOrder (root);
printf("Path to %d:\n", lastNodeInserted->value);
printPath(lastNodeInserted);
}
}
CFLAGS += -std=gnu11 -g EXES = BinaryTree all: $(EXES) clean: -rm -f $(EXES) BinaryTree: BinaryTree.c # don't treat all and clean as file targets .PHONY: all clean
In this question, you will combine your understanding of snippets S1, S2 (from the assignment 2 handout) and S4
Note the following code in C:
struct S {
int x[2];
int *y;
struct S *z;
};
int i;
int v0, v1, v2, v3;
struct S s;
void foo() {
v0 = s.x[i];
v1 = s.y[i];
v2 = s.z->x[i];
v3 = s.z->z->y[i];
}
Implement this code in SM213 assembly by following these steps:
q3.s with three sections, each with its own .pos: one for code, one for the static data, and one for the "heap". For example:.pos 0x1000
code:
.pos 0x2000
static:
.pos 0x3000
heap:
.long directives allocate the variables i, v0, v1, v2, v3, and s in the static data section. Note the variable s is a “struct S” and so to allocate space for it here you need to understand how big it its. This section of your file should look something like this (the ellipsis indicates more lines like the previous one):.pos 0x2000
static:
i: .long 0
v0: .long 0
v1: .long 0
v2: .long 0
v3: .long 0
s: .long 0
...
In order for the autograder to recognize your solution you must use variable names for the labels. You are strongly encouraged to add comments to the lines above indicating what each of these values represent, particularly for the s struct.
s.y, s.z, s.z->z, and s.z->z->y) to point to locations in "heap", as if malloc had been called for each of them. For each y array, allocate two integers. In essence, you want to create a snapshot of what memory would look like after the program has executed these statements:s.y = malloc(2 * sizeof(int));
s.z = malloc(sizeof(struct S));
s.z->z = malloc(sizeof(struct S));
s.z->z->y = malloc(2 * sizeof(int));
You may assign labels to each of these locations. For example, after the first malloc runs, maybe the memory looks like this:
s: .long 0 # x[0]
.long 0 # x[1]
.long s_y # y
heap:
s_y: .long 0 #s.y[0]
.long 0 #s.y[1]
foo (not any other part of the procedure) in SM213 assembly in the code section of your file. Comment every line carefully. NOTE: you cannot use any dynamically computed addresses as constants in your code. So, for example, you cannot use the labels s_y, s_z, etc. in your code. The only labels your code should use are the ones assigned to the global variables above: i, v0, v1, v2, v3 and s..pos 0x1000
code:
# v0 = s.x[i];
ld $i, r0 # r0 = address of i
ld (r0), r0 # r0 = i
ld $s, r1
ld $v0, r2
ld (r1, r0, 4), r3 # r3 = s.x[i]
st r3, (r2) # v0 = s.x[i]
# v1 = s.y[i];
ld 8(r1), r3 # r3 = s.y
ld (r3, r0, 4), r4 # r4 = s.y[i]
ld $v1, r2
st r4, (r2) # v1 = s.y[i]
# v2 = s.z->x[i];
ld 12(r1), r3 # r3 = s.z
ld (r3, r0, 4), r4 # r4 = s.z->x[i]
ld $v2, r2
st r4, (r2) # v2 = s.z->x[i]
# v3 = s.z->z->y[i];
ld 12(r1), r3 # r3 = s.z
ld 12(r3), r3 # r3 = s.z->z
ld 8(r3), r3 # r3 = s.z->z->y
ld (r3, r0, 4), r4 # r4 = s.z->z->y[i]
ld $v3, r2
st r4, (r2) # v3 = s.z->z->y[i]
halt
.pos 0x2000
static:
i: .long 0
v0: .long 0
v1: .long 0
v2: .long 0
v3: .long 0
s: .long 0 # x[0]
.long 0 # x[1]
.long s_y # *y
.long s_z # *z
.pos 0x3000
heap:
s_y: .long 0
.long 0
s_z: .long 0 # x[0]
.long 0 # x[1]
.long 0 # *y
.long s_z_z # *z
s_z_z: .long 0 # x[0]
.long 0 # x[1]
.long s_z_z_y # *y
.long 0 # *z
s_z_z_y: .long 0
.long 0
Review the C code from the previous question (reprinted here for convenience).
struct S {
int x[2];
int *y;
struct S *z;
};
int i;
int v0, v1, v2, v3;
struct S s;
void foo() {
v0 = s.x[i];
v1 = s.y[i];
v2 = s.z->x[i];
v3 = s.z->z->y[i];
}
Use your solution from the previous question and the simulator to help you answer these questions. When counting the number of distinct memory locations that are read, do not include the locations involved in the Fetch stage of the simulator (i.e., do not count the process of reading the instruction itself). In all of these cases, assume there are no optimizations, that is, assume that values from previous instructions (e.g., the value of i) are not re-used in future instructions, and are re-read if necessary.
How many distinct memory locations are read when the first line of foo() executes?
2
How many distinct memory locations are read when the second line of foo() executes?
3
How many distinct memory locations are read when the third line of foo() executes?
3
How many distinct memory locations are read when the fourth line of foo() executes?
5