The University of New South Wales
Term 2, 2023
COMP1521: Computer Systems Fundamentals

22T2 Final Exam

β€” Tuesday 22 August 2023 β€”
10 questions β€” 100 marks
10 minutes reading; 3 hours working

Examination Information

Examination Instructions and Conditions

  • You can start reading the text of this examination when instructed to do so by your invigilator.

  • You can start working on examination questions when instructed to do so by your invigilator.

  • You must stop working on examination questions immediately when instructed to do so by your invigilator.

  • Only submissions made before this time will be marked.

    For students with approved examination extensions from UNSW Equitable Learning Services,
    You should continue working until your extended working time expires.

    Your invigilator will tell you when this time expires.

  • You must not communicate with any person during the examination
    except for COMP1521 Course Staff and Exam Invigilators.

  • You are not permitted to talk, email, telephone, message , etc. all
    except to COMP1521 Course Staff and Exam Invigilators.

  • You must not get help from anyone during this exam,
    except from COMP1521 Course Staff and Exam Invigilators.

  • You must not communicate (email, message, post, ...) your exam answers to anyone, even after the exam has finished.

    There are two sessions, so other students may still be taking the exam after you have finished.

    Additionally Some students have extended time to complete the exam.

    And some students may be taking the exam on a different day.

  • Communicating your answers to other students, even after the exam, may be academic misconduct.

  • You must ensure that, during and after the examination, no other person can access your work.

  • You must not use code-synthesis tools, such as GitHub Copilot, during this exam.

  • Your zPass should not be disclosed to any other person. If you have disclosed your zPass, you should change it immediately.

  • This is a closed-book examination.

  • You are not permitted to access papers, books, or any other written materials.

  • You are not permitted to access files on your computer or other computers, except the files provided by the exam.

  • You are not permitted to access web pages or other Internet resources, except the web pages provided by the exam, and the online language documentation linked below.

Deliberate violation of exam conditions is academic misconduct,
and will be referred to the UNSW Student Conduct and Integrity Unit.

Examination Structure

  • This examination has 10 questions,
    worth a total of 100 marks.
    Questions are worth equal marks.

  • All 10 questions are practical questions.

  • Not all questions may provide files. You should create any files needed for submission if they are not provided.

  • You must answer each question in a separate file. Each question specifies the name of the file to use. Make sure you use exactly this file name.

  • When you finish working on a question, you should submit your files using the give command specified in the question. You should not wait until the submission deadline to submit your answers. Running autotests does not automatically submit your code.

  • You do not receive additional time for submitting your answers.

    You must submit all questions before the end of the 3 hour exam period.

    Failing to logout immediately at the end of the exam period is academic misconduct.

  • You may submit as many times as you like; only the last submission will be marked.

  • You can verify what submissions you have made with 1521 classrun -check

Available Resources: Language Documentation

You may access this language documentation while attempting this test:

Troubleshooting

If you are having issues working on the exam:

  • Immediately inform your invigilator.

Fit-to-Sit

This exam is covered by UNSW's Fit-to-Sit policy. That means that, by sitting this exam, you are declaring yourself well enough to do so. You will be unable to apply for special consideration after the exam for circumstances affecting you before it began.

Getting Started

All provided files for this exam are located in your home directory.

simply open a terminal or text editor in your home directory and you will be able to access all the files.

If you make a mistake and need a new copy of a particular file, you can do the following:

rm broken-file
1521 fetch exam_22t2final

Only files that don't exist will be recreated. All other files will remain untouched.

Question 1 (10 marks)

Count zero bits is an operation on a list of bits that counts how many zero-bits are present.

For example, in the case of an 8-bit number,

  • count_zero_bits(0b11111111) == 0
  • count_zero_bits(0b11101111) == 1
  • count_zero_bits(0b10011111) == 2
  • count_zero_bits(0b00011001) == 5
  • count_zero_bits(0b00010000) == 7
  • count_zero_bits(0b00000000) == 8

You must implement this operation for 32-bit values.

You have been given 22t2final_q1.c:

// COMP1521 22T2 ... final exam, question 1

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int count_zero_bits(uint32_t x) {
	// TODO
	return 42;
}

Add code to the function count_zero_bits so that it counts and returns the number of zero bits in a 32-bit unsigned integer x.

For example:

make 22t2final_q1
0 == 0x00000000
./22t2final_q1 0
32
305419896 == 0x12345678
./22t2final_q1 305419896
19
4294967295 == 0xFFFFFFFF
./22t2final_q1 4294967295
0

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q1

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q1 22t2final_q1.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q1

Question 2 (10 marks)

You have been given 22t2final_q2.s, a MIPS assembler program that reads an integer and then prints 42.

Add code to 22t2final_q2.s so that it prints the amount of zero bits in the integer that was read in.

In other words, it should behave the same as final_q1.

For example:

1521 mipsy 22t2final_q2.s
0
32
1521 mipsy 22t2final_q2.s
1
31
1521 mipsy 22t2final_q2.s
100000
26
1521 mipsy 22t2final_q2.s
-1
0

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q2

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q2 22t2final_q2.s

To verify your submissions for this activity:

1521 classrun -check 22t2final_q2

Question 3 (10 marks)

You have been given 22t2final_q3.c, which contains a C function 22t2final_q3, that currently takes one integer value, and then returns the value unchanged.

Add code to the function 22t2final_q3 so that, given a uint32_t value, it returns the provided value but with its bytes reversed.

For example, 0x12345678 becomes 0x78563412

Note that your task is to reverse the order of bytes, not to reverse the order of bits.

For example:

./22t2final_q3 0x12345678
22t2final_q3(0x12345678) returned 0x78563412
./22t2final_q3 0x43000090
22t2final_q3(0x43000090) returned 0x90000043
./22t2final_q3 0x55001248
22t2final_q3(0x55001248) returned 0x48120055
./22t2final_q3 0x55000001
22t2final_q3(0x55000001) returned 0x01000055
./22t2final_q3 0x10000080
22t2final_q3(0x10000080) returned 0x80000010
./22t2final_q3 0xFF00FF00
22t2final_q3(0xFF00FF00) returned 0x00FF00FF
./22t2final_q3 0xFF0000FF
22t2final_q3(0xFF0000FF) returned 0xFF0000FF
./22t2final_q3 0x00000001
22t2final_q3(0x00000001) returned 0x01000000
./22t2final_q3 0x10000000
22t2final_q3(0x10000000) returned 0x00000010
./22t2final_q3 0x00000000
22t2final_q3(0x00000000) returned 0x00000000
./22t2final_q3 0xFFFFFFFF
22t2final_q3(0xFFFFFFFF) returned 0xFFFFFFFF

You can use make(1) to build your code:

make 22t2final_q3

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q3

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q3 22t2final_q3.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q3

Question 4 (10 marks)

You have been given 22t2final_q4.s, a MIPS program that currently reads 10 numbers and then prints 42.

Your task is to modify 22t2final_q4.s so that it is equivalent to this C program:

// Reads 10 numbers into an array
// Prints the length of the longest sequence
// of strictly increasing numbers in the array.

#include <stdio.h>

int main(void) {
	int i;
	int numbers[10] = { 0 };

	i = 0;
	while (i < 10) {
		scanf("%d", &numbers[i]);
		i++;
	}

	int max_run = 1;
	int current_run = 1;
	i = 1;
	while (i < 10) {
		if (numbers[i] > numbers[i - 1]) {
			current_run++;
		} else {
			current_run = 1;
		}

		if (current_run > max_run) {
			max_run = current_run;
		}

		i++;
	}

	printf("%d\n", max_run);

	return 0;
}

The program 22t2final_q4.c returns the length of the longest consecutive sequence of strictly increasing numbers.

For example:

1521 mipsy 22t2final_q4.s
1
2
3
4
5
6
7
8
9
10
10
1521 mipsy 22t2final_q4.s
1
2
3
4
5
6
7
7
8
9
7
1521 mipsy 22t2final_q4.s
1
2
3
1
2
4
5
5
6
6
4
1521 mipsy 22t2final_q4.s
10
9
8
7
6
5
4
3
2
1
1

You can use make(1) to build the provided C code:

make 22t2final_q4

You can use 1521 mipsy to run your MIPS code:

1521 mipsy 22t2final_q4.s

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q4

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q4 22t2final_q4.s

To verify your submissions for this activity:

1521 classrun -check 22t2final_q4

Question 5 (10 marks)

You have been given final_q5.c: a C program with an empty implementation of the function print_bytes.

// COMP1521 22T2 ... final exam, question 5

#include <stdio.h>

void print_bytes(FILE *file, long n) {
	// TODO
}

Add code to the function print_bytes so that, if n is positive (or zero), it prints the first n bytes from the provided file file.

If n is negative, it should instead print all but the last |n| bytes of the provided file, where |n| is the absolute value of n; e.g. if n is -5, then |n| is 5.

If n extends outside the range of the file (e.g. n = 50 or n = -50 in a 10 byte file, then your program should behave as if n was 10 in the first case, and as if n was -10 in the second case. i.e., extending outside the range of the file has no additional effect.

Note that you cannot assume that the provided file is an ASCII text file. In particular, the provided file may contain NUL bytes (i.e. zero bytes). This means that you cannot use string-based functions such as fgets to read from the provided file.

For example:

make 22t2final_q5
echo 'you are doing great, keep it up!' >my_file
./22t2final_q5 my_file 19
you are doing great
^^^ no terminating newline
./22t2final_q5 my_file 7
you are
^^^ no terminating newline
./22t2final_q5 my_file 10000
you are doing great, keep it up!
./22t2final_q5 my_file -14
you are doing great
^^^ no terminating newline

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q5

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q5 22t2final_q5.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q5

Question 6 (10 marks)

You have been given 22t2final_q6.c, which contains a C function 22t2final_q6, that takes three parameters...

  • char *utf8_string: a UTF-8 encoded string,
  • unsigned int range_start: the (inclusive) starting index,
  • unsigned int range_end: the (exclusive) ending index.

... and returns a char *.

#include <string.h>
#include <stdlib.h>

/**
 * given a `UTF-8` encoded string,
 * return a new string that is only
 * the characters within the provided range.
 *
 * Note:
 * `range_start` is INCLUSIVE
 * `range_end`   is EXCLUSIVE
 *
 * eg:
 * "hello world", 0, 5
 * would return "hello"
 *
 * "πŸ“πŸ‡πŸˆπŸπŸ", 2, 5
 * would return "🍈🍍🍐"
**/

char *_22t2final_q6(char *utf8_string, unsigned int range_start, unsigned int range_end) {
	char *new_string = strdup(utf8_string);

	return new_string;
}

Add code to the function 22t2final_q6 so that, given the above parameters, it returns a new string comprised of the UTF-8 code-points that lie in the range of range_start to range_end in the provided utf8_string.

Note that the returned string must be a new string; i.e. you must not modify the provided utf8_string -- you must instead use malloc (or otherwise, such as strdup) to allocate new memory that you can then return. main will later free that memory for you.

For example:

make 22t2final_q6
./22t2final_q6 "hello world" 3 8
22t2final_q6("hello world", 3, 8) returned "lo wo"
./22t2final_q6 "πŸ“πŸ‡πŸˆπŸπŸπŸ–πŸ§πŸ†πŸŠπŸž" 2 4
22t2final_q6("πŸ“πŸ‡πŸˆπŸπŸπŸ–πŸ§πŸ†πŸŠπŸž", 2, 4) returned "🍈🍍"
./22t2final_q6 "β‡œβ‡Ώβ†΄β†›β‡³β‡™β†œβ†§β‡₯β†–β‡Έβ‡‹β‡ˆβ‡˜β†Ÿβ†Ήβ‡β†©β†₯β‡Šβ‡‡β‡“β‡Ÿβ‡¬β‡©" 22 25
22t2final_q6("β‡œβ‡Ώβ†΄β†›β‡³β‡™β†œβ†§β‡₯β†–β‡Έβ‡‹β‡ˆβ‡˜β†Ÿβ†Ήβ‡β†©β†₯β‡Šβ‡‡β‡“β‡Ÿβ‡¬β‡©", 22, 25) returned "β‡Ÿβ‡¬β‡©"

A reminder of how UTF-8 is encoded:

#bytes #bits Byte 1 Byte 2 Byte 3 Byte 4
1 7 0xxxxxxx - - -
2 11 110xxxxx 10xxxxxx - -
3 16 1110xxxx 10xxxxxx 10xxxxxx -
4 21 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q6

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q6 22t2final_q6.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q6

Question 7 (10 marks)

You have been given 22t2final_q7.c: a C program with an empty implementation of the function 22t2final_q7.

void _22t2final_q7(char *directory, char *name, int min_depth, int max_depth) {
    // TODO
}

Add code to the function 22t2final_q7 such that it recursively looks through the provided directory for files and directories that match the given criteria. If a file or directory is found that matches the given criteria, the path to that file should be printed out.

Note that if you find a directory that does not match the given criteria, you should still recursively search inside of it; just don't print it out.

The possible criteria are:

  • char *name:

    If name is NULL, then this restriction does not apply.

    Otherwise, before printing out any found file or directory, you must first check that the file or directory's name exactly matches the provided name.

    You can find the name of a found file or directory through the d_name field in the struct dirent * returned by readdir.

  • int min_depth:

    If min_depth is -1, then this restriction does not apply.

    Otherwise, before printing out any found file or directory, you must first check if the current search is at least min_depth directories deep.

    You should keep track of your current depth through a recursive parameter.

    The initial depth of the files directly inside the provided directory is 0.

  • int max_depth:

    If max_depth is -1, then this restriction does not apply.

    Otherwise, before printing out any found file or directory, you must first check if the current search is at most max_depth directories deep.

    You should keep track of your current depth through a recursive parameter.

    The initial depth of the files directly inside the provided directory is 0.

Note that the order in which you print out found files and directories does not matter; your output is alphabetically sorted before autotest checks for correctness. All that matters is that you print the correct files and directories.

For example:

make 22t2final_q7
unzip 22t2final_q7_dirs.zip
[lots of output]
./22t2final_q7 22t2final_q7_dirs 'a' 1 3 | sort
22t2final_q7_dirs/dir1/a
22t2final_q7_dirs/dir1/a/a
22t2final_q7_dirs/dir1/b/a
22t2final_q7_dirs/dir1/c/a
22t2final_q7_dirs/dir2/a
22t2final_q7_dirs/dir4/a
./22t2final_q7 22t2final_q7_dirs 'a' -1 1 | sort
22t2final_q7_dirs/a
22t2final_q7_dirs/dir1/a
22t2final_q7_dirs/dir2/a
22t2final_q7_dirs/dir4/a
./22t2final_q7 22t2final_q7_dirs 'a' 5 -1 | sort
22t2final_q7_dirs/dir2/deep/deep/deep/deep/deep/deep/deep/deep/deep/deep/a
./22t2final_q7 22t2final_q7_dirs 'e' | sort
22t2final_q7_dirs/dir1/a/e
22t2final_q7_dirs/dir1/b/e
22t2final_q7_dirs/dir1/c/e
22t2final_q7_dirs/dir4/e
22t2final_q7_dirs/e
./22t2final_q7 22t2final_q7_dirs '' 2 2 | sort
22t2final_q7_dirs/dir1/a/.
22t2final_q7_dirs/dir1/a/..
22t2final_q7_dirs/dir1/a/a
22t2final_q7_dirs/dir1/a/b
22t2final_q7_dirs/dir1/a/c
22t2final_q7_dirs/dir1/a/d
22t2final_q7_dirs/dir1/a/e
22t2final_q7_dirs/dir1/b/.
22t2final_q7_dirs/dir1/b/..
22t2final_q7_dirs/dir1/b/a
22t2final_q7_dirs/dir1/b/b
22t2final_q7_dirs/dir1/b/c
22t2final_q7_dirs/dir1/b/d
22t2final_q7_dirs/dir1/b/e
22t2final_q7_dirs/dir1/c/.
22t2final_q7_dirs/dir1/c/..
22t2final_q7_dirs/dir1/c/a
22t2final_q7_dirs/dir1/c/b
22t2final_q7_dirs/dir1/c/c
22t2final_q7_dirs/dir1/c/d
22t2final_q7_dirs/dir1/c/e
22t2final_q7_dirs/dir2/deep/.
22t2final_q7_dirs/dir2/deep/..
22t2final_q7_dirs/dir2/deep/deep

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q7

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q7 22t2final_q7.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q7

Question 8 (10 marks)

You have been given 22t2final_q8.s:

# COMP1521 22T2 ... final exam, question 8

	.data

# char default_char = ' ';
default_char:	.byte ' '


	.text
# void move_disks(char size, char *target, char *peg1, char *peg2) {
move_disks:
	# TODO: Complete this function
	jr	$ra


	.text
# char *find_lowest_target(char *target) {
find_lowest_target:
	# TODO: Complete this function
	jr	$ra

Add code to 22t2final_q8.s to make it equivalent to this C program which you have been given as 22t2final_q8.c:

// // // // // // // // DO NOT CHANGE THIS FILE! // // // // // // // //
// COMP1521 22T2 ... final exam, question 8

#include <stdlib.h>

#include "22t2final_q8.h"

char default_char = ' ';

void move_disks(char size, char *target, char *peg1, char *peg2) {
    char *peg_max = &default_char;
    char *source = NULL;
    char *other = NULL;

    for (int i = 0; peg1[i] != '\0'; i++) {
        if (peg1[i] > *peg_max && peg1[i] <= size) {
            peg_max = peg1 + i;
            source = peg1;
            other = peg2;
        }
        if (peg2[i] > *peg_max && peg2[i] <= size) {
            peg_max = peg2 + i;
            source = peg2;
            other = peg1;
        }
    }

    if (*peg_max == ' ') return;

    move_disks(size - 1, other, source, target);
    char *lowest_target = find_lowest_target(target);
    swap(peg_max, lowest_target);

    while (*peg_max != *(peg_max + 1)) {
        swap(peg_max, peg_max + 1);
        peg_max++;
    }

    print_towers();
    move_disks(size - 1, target, source, other);
}

char *find_lowest_target(char *target) {
    if (*target == ' ') return target;
    return find_lowest_target(target + 1);
}

22t2final_q8.c is part of a larger program that helps solve the "Towers of Hanoi" problem - a famous mathematical game played with three towers of disks.

You must translate both functions to MIPS assembler and following the standard calling conventions used in lectures.

Note that you have been provided a 22t2final_q8_main.s file which includes a main function to help test your code, along with a complete implementation of the swap function which is used in the C code provided above.

For example:

1521 mipsy 22t2final_q8_main.s 22t2final_q8.s
================
|g f e d c b a |
|              |
|              |
================
================
|g f e d c b   |
|a             |
|              |
================
[lots of output]
================
|a             |
|g f e d c b   |
|              |
================
================
|              |
|g f e d c b a |
|              |
================
You should check your MIPS code against the C reference code:
make 22t2final_q8
./22t2final_q8 >c.output
1521 mipsy 22t2final_q8_main.s 22t2final_q8.s >mips.output
diff c.output mips.output

(no output from diff is good!)

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q8

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q8 22t2final_q8.s

To verify your submissions for this activity:

1521 classrun -check 22t2final_q8

Question 9 (10 marks)

Despite the growing storage capacity of computers in recent decades, there are many situations where computers run out of space to store files. It can be very inconvenient to discover (e.g. in the middle of an exam) that you have no space left on your computer. Therefore, it can often be useful to have programs which continuously watch your file usage, and warn you when you hit a certain limit.

In 22t2final_q9, your task is to write a program which spawns threads to watch multple files on your computer, and keep track of the files' collective size. Each file must be watched by its own thread. i.e., if the user wants to watch the files foo, bar, and baz, your program should have four threads -- the initial main thread waiting for further input, and one thread for each of the three files.

If the files' combined size exceeds a (#define'd) quota, a single warning should be printed out to the user. When the user fixes the issue, a single message should be printed out, to let the user know the problem is solved. Each thread should continue watching files until they are deleted; the overall program should terminate when all files are deleted.

Note, you must not attempt to get the size of files yourself. You are provided a (thread-safe) function, file_size, which does this for you. We will modify the file_size function during testing, so you must not rely on any internal behaviour, or attempt to recreate it yourself.

Note: This is a concurrency-oriented exercise, that is solvable using mutexes, atomics, or a combination of the two. An atomic solution is trickier to get right, but executes faster and is less prone to some issues, such as deadlocking. A mutex solution is simpler to write, but executes slower and is more prone to some issues, such as deadlocking. Both approaches, when written correctly (without fault), are valid strategies to receive full marks.

We have provided you with the files 22t2final_q9_helper.h and 22t2final_q9_helper.c which contain the following information:

  • the #defined constant QUOTA_EXCEEDED_MESSAGE, which you should print when the quota is exceeded.
  • the #defined constant QUOTA_RESOLVED_MESSAGE, which you should print when the user has resolved the quota issue.
  • the #defined constant QUOTA, a postive number of bytes, which is the maximum combined file size before the user should be informed.
  • the function file_size, which takes a file name, and returns either its size, or the constant FILE_NOT_FOUND if the file has been deleted.

The following example shows a user in two terminals at once. The quota (QUOTA) in this example is 10 bytes.

make 22t2final_q9
touch file1
echo "abcdefg" >file2 
TERMINAL 1
./22t2final_q9
file1
file2
... over to terminal 2


Quota exceeded!
... over to terminal 2


Quota resolved!
... over to terminal 2





file3
Quota exceeded!

... over to terminal 2


Quota resolved!
[program exited with return code 0]
TERMINAL 2




echo "abcdefg" >> file1
... back to terminal 1


rm file1 file1 no longer watched
... back to terminal 1


echo "abcdefg" > file1
^^ no effect - file1 no longer watched

echo "abcdefg" > file3
... back to terminal 1




rm file2 file3
... back to terminal 1

You can modify the provided 22t2final_q9_helper.h constants (you may want to modify the QUOTA constant for testing), but note that when autotesting and after submitting, we will use the original 22t2final_q9_helper.h instead.

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q9

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q9 22t2final_q9.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q9

Question 10 (10 marks)

A shell is an interactive prompt commonly found on UNIX systems that allows a user to enter commands to perform, and displays the output of those commands.

Your task in this question is to create a very simple shell that will allow the user to enter commands and display the output of those commands. We will call this shell "rush" β€” a feeling you may currently be experiencing. The features of your shell have been allocated into smaller portions of marks, as seen below.

markfeature
10%exit
20%cd and pwd
25%executing fully qualified commands
25%executing commands from the PATH
20%globbing arguments

Note that each feature depends on the previous one when testing and marking your code, so please ensure you complete the features in order!

You have been provided with a file that prints prompts and reads input, vageuly resembling a shell like bash, but currently missing all of the above functionality:

dcc 22t2final_q10.c -o 22t2final_q10
./22t2final_q10
[rush] exit
TODO: add your code here
[rush] cd ..
TODO: add your code here
[rush] pwd
TODO: add your code here
[rush] ./foo
TODO: add your code here
[rush] ls
TODO: add your code here
[rush] ls -l *
TODO: add your code here

As you can see, the program doesn't do much but print a [rush] prompt, and a TODO message after every input currently. Once your program is working in its entirety, the output may look something like this:

dcc 22t2final_q10.c -o 22t2final_q10
./22t2final_q10
[rush] cd /home/zac/stuff/
[rush] pwd
/home/zac/stuff
[rush] dcc hello.c -o hello
[rush] ./hello
Hello, world!
[rush] tail -n +1 ~/secrets/*
==> /home/zac/secrets/1521_master_password.txt <==
hunter2

==> /home/zac/secrets/diary.txt <==
spim bad
[rush] exit

In your provided starter code, you will find:

  • All the#includes you should need for the exercise (you may add more).
  • Some convenience#defines that illustrate reasonable limits (you may add more).
  • Amain function that sets up some variables and gets you started.
  • Anis_executable function that is useful later for executing commands.
  • Ado_glob function that is useful later for globbing.

Following, each feature will be described for you to base your implementation on. If you are unsure what your program should do in a particular case, we have provided a working reference solution for you. Use 1521 rush to access the reference solution and try to match your solution to its behaviour. If 1521 rush crashes with an assertion failure, it means that you do not have to consider that case.

Feature 1: exit

The exit command will exit the shell. You should not produce any additional output when this command is run. Any additional arguments should be ignored.

For example,

dcc 22t2final_q10.c -o 22t2final_q10
./22t2final_q10
[rush] exit
./22t2final_q10
[rush] exit foo
./22t2final_q10
[rush] exit foo bar baz

Feature 2: cd and pwd

The cd and pwd commands respectively modify and display the shell's current working directory.

When the shell is first launched, the current working directory is fetched with the getcwd(3) function into the cwd variable (this is already completed for you).

The cd command will change the current working directory to the specified path. If the cd command is given no arguments, the path should be assumed to be the user's home directory. You can fetch the user's home directory with the getenv(3) function, requesting the HOME environment variable.

Changing the current working directory should be achieved with the chdir(2) function. You may also want to update the cwd variable at this time, as mentioned previously. If chdir(2) fails, you should print an error messaging in the format: fprintf(stderr, "cannot cd to %s\n", directory);

The pwd command will print the current working directory. This should be achieved either with the getcwd(3) function or the cwd variable, depending on your particular approach.

The cd command should ignore any arguments after the first one (i.e. the path to change to), and similarly the pwd command should ignore any provided arguments.

For example,

dcc 22t2final_q10.c -o 22t2final_q10
pwd
/home/zac/stuff
./22t2final_q10
[rush] pwd
/home/zac/stuff
[rush] cd ..
[rush] pwd
/home/zac
[rush] cd /
[rush] pwd
/
[rush] cd
[rush] pwd
/home/zac
[rush] cd hdhhfdhjf
cannot cd to hdhhfdhjf
[rush] 

Feature 3: executing qualified commands

For this feature, you will expand your shell to accept qualified commands, which it will then execute. "Qualified" in this context means that the command is a path to a file, and your shell should simply be able to execute that file with posix_spawn(3).

You should "tokenize" input you have been given, by splitting it on the space character. This can be done with the strtok(3) function, passing " " as the delim.

From this tokenization, the first token should be considered the command to execute. The remaining tokens should each be considered as an individual argument to the command's argv. Recall that programs expect argv[0] to be the command name β€” so you should prepend the command name to the arguments.

You must also check that the command you are executing is actually executable. You can do this with the is_executable function. If the command is not executable, you should print an error message in the following format: fprintf(stderr, "%s: cannot execute command\n", command);, and then continue the main loop to wait for further input.

You should then use the posix_spawn(3) function to execute the command. You can set the file_actions and attrp arguments to NULL, but all other arguments should be set correctly.

Finally, your shell should waitpid(2) on the spawned process in order to ensure that the shell does not continue before the command has finished.

For example,

dcc 22t2final_q10.c -o 22t2final_q10
./22t2final_q10
[rush] /bin/echo hello world!
hello world!
[rush] /bin/ls
22t2final_q10  22t2final_q10.c
[rush] /bin/ls -l
total 132
-rwxrwxr-x 1 zac zac 123192 Jan 01 12:00 22t2final_q10
-rw-rw-r-- 1 zac zac   5004 Jan 01 12:00 22t2final_q10.c
[rush] /bin/file 22t2final_q10.c
22t2final_q10.c: C source, ASCII text
[rush] ./hdhhfdhjf
hdhhfdhjf: cannot execute command
[rush] ./22t2final_q10.c
./22t2final_q10.c: cannot execute command
[rush] 

Feature 4: executing commands from the PATH

Similarly to the previous feature, you should expand your shell to accept unqualified commands, which it will then execute. "Unqualified" in this context means that the command is not an exact path to a file, but simply the name of a command that will appear in the PATH. You can tell whether a command is unqualified by checking whether it has a '/' character in it (e.g. with the strchr(3) function).

In this case, you need to search the PATH for the requested command. You can retrieve the PATH with the getenv(3) function, requesting the PATH environment variable.

You should then use the strtok(3) function to tokenize the PATH on the : character. Each token should be considered an individual directory to search.

For each directory, you should then use the is_executable function to check whether a program with the requested name exists and is executable in that directory (snprintf(3) is useful to join the strings together).

Once you have found the first executable file, you should then continue to execute it with posix_spawn(3) as explained previously.

If you do not find an executable file, you should print an error message in the same format as previously.

For example,

dcc 22t2final_q10.c -o 22t2final_q10
./22t2final_q10
[rush] echo hello world!
hello world!
[rush] ls
22t2final_q10  22t2final_q10.c
[rush] ls -l
total 132
-rwxrwxr-x 1 zac zac 123192 Jan 01 12:00 22t2final_q10
-rw-rw-r-- 1 zac zac   5004 Jan 01 12:00 22t2final_q10.c
[rush] file 22t2final_q10.c
22t2final_q10.c: C source, ASCII text
[rush] hdhhfdhjf
hdhhfdhjf: cannot execute command
[rush] 

Note: you are not allowed to use posix_spawnp(3) for this feature. You must search the PATH manually, and use posix_spawn(3) instead.

Feature 5: globbing arguments

For this feature, you will need to modify 22t2final_q10.c to support filename expansion, sometimes referred to as globbing.

Any arguments to commands (i.e. cd, qualified commands, unqualified commands) should be fed into the glob(3) function in order to expand any special characters, such as ~ and *.

The exact usage of glob(3) has been provided for you in the do_glob function. You can pass it text to glob (in this case, arguments to commands), and it will return a glob_t.

A glob_t contains the following fields that are useful to us:

typedef struct {
    size_t   gl_pathc;    /* Count of glob expansions  */
    char   **gl_pathv;    /* The list of glob expansions  */
} glob_t;

The gl_pathc field contains the number of glob expansions, recalling that a single argument may expand to multiple files (e.g. with the '*' character). This means that the program you intend to spawn may have more arguments than you expected!

The gl_pathv field contains the list of glob expansions, and it will have length gl_pathc.

Note that you need to glob the individual arguments to commands, not the entire input line, nor the command itself. This implies that commands such as ~/bin/my_program will not work due to the '~' not being expanded, but it simplifies your implementation.

For example,

dcc 22t2final_q10.c -o 22t2final_q10
./22t2final_q10
[rush] ls
22t2final_q10  22t2final_q10.c
[rush] echo my files are *
my files are 22t2final_q10 22t2final_q10.c
[rush] wc *
291   2308 123480 22t2final_q10
180    581   5458 22t2final_q10.c
471   2889 128938 total
[rush] cd ~/stuff
[rush] pwd
/home/zac/stuff
[rush] 

other information

When you think your program is working, you can run some simple automated tests:

1521 autotest 22t2final_q10

When you are finished working on this activity, you must submit your work by running give:

give cs1521 22t2final_q10 22t2final_q10.c

To verify your submissions for this activity:

1521 classrun -check 22t2final_q10

Submission

When you are finished working on a question, submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any questions you haven't attempted.

Do not leave it to the deadline to submit your answers.

Submit each question when you finish working on it.

Running autotests does not automatically submit your code.

β€” End of examination. β€”