2019q1 Homework1 (lab0)

contributed by < Superdanby >

Environment Setup

• Fedora 29
• gcc (GCC) 8.2.1 20181215 (Red Hat 8.2.1-6)

1. sudo dnf install cppcheck colordiff

Function Analysis

queue_t *q_new()

Should one type cast malloc?

The first problem I encountered is whether I should type cast the memory returned from malloc. If I remembered right, there would be a warning/error if one didn't do it. Thus, I searched and found that it is suggested not doing so in C.

Note that C and C++ have different behaviors on this issue.

void q_free(queue_t *q)

Needs to iterate through the queue and release the memory of value entry of each element.

bool q_insert_head(queue_t *q, char *s)

Should also link tail if tail is empty.

bool q_insert_tail(queue_t *q, char *s), O(1)

Should also link head if head is empty.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)

The first things I was thinking is that if I allocate sp a new block of memory with malloc, the caller will not receive the returned string. And then, I saw bufsize, which is when I realized the caller will malloc on its side.

int q_size(queue_t *q), O(1)

Add a new entry in queue_t, and this could be done in O(1).

void q_reverse(queue_t *q)

Should not allocate or release memory.

Needs to traverse the whole queue and reverse each element one by one.

Version History

Version 1

• Score: 56/100
• Got lots of : ERROR: Failed to store removed value

After checking my code, I found that the if statement I used to check whether to copy head->value to sp in bool q_remove_head(queue_t *q, char *sp, size_t bufsize) is wrong.

Wrong version:

// Check sp and bufsize availability
if (!sp && (temp->value) && bufsize)

Corrected version:

// Check sp and bufsize availability
if (sp && (temp->value) && bufsize)

The reason why I code it wrong is because I wanted to write sp != NULL, but I gone lazy and make it !sp which is really stupid. I should be more cautious next time.

Version 2

• Score: 93/100
• Test remove_head with NULL argument results in:
  ERROR: Freed queue, but 1 blocks are still allocated

Wrong version:

if (sp && (temp->value) && bufsize) {
    strncpy(sp, temp->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    // Release value memory
    free(temp->value);
    temp->value = NULL;
}

Corrected version:

if (temp->value) {
    if (sp && bufsize) {
        strncpy(sp, temp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    // Release value memory
    free(temp->value);
    temp->value = NULL;
}

temp->value needs to be cleared even if it couldn't be copied to sp.

Version 3

• Score: 100/100

Automated Grading System

Looking at Makefile, we can see that the make test executes scripts/driver.py.

driver.py

run method

Increments the total score by the corresponding value in maxScores if no error detected after executing runTrace; the total score will not be incremented otherwise.

runTrace method

Executes qtest with different arguements composed in clist

qtest

• Checks memory leaks with allocation_check().
• Checks errors with error_check().

bool error_check()

Checks if an error had occured and clears error_occurred.

size_t allocation_check()

Returns the number of blocks of memory still allocated. The number is actually stored in allocated_count and is incremented and decremented in test_malloc and test_free respectively. Thus, we can infer from this fact that all operations for memory allocation / release will be tested with these 2 functions.
Searching all files with find . -exec grep 'test_free\|test_malloc' {} + 2> /dev/null, we get the following result:

./harness.c:void *test_malloc(size_t size)
./harness.c:void test_free(void *p)
./harness.c:    void *new = test_malloc(len);
./harness.h:void *test_malloc(size_t size);
./harness.h:void test_free(void *p);
./harness.h:#define malloc test_malloc
./harness.h:#define free test_free
Binary file ./queue.o matches
Binary file ./qtest matches

From the result, we can know that all files which include harness.h have there free() and malloc() from standard library replaced with those of harness.h.
Next, using find . -exec grep '#include "harness.h"' {} + 2> /dev/null, we can see the following:

./harness.c:#include "harness.h"
./qtest.c:#include "harness.h"
./queue.c:#include "harness.h"

The file queue.c we were modifying is also using "harness.h"

char *test_strdup(const char *s)

This function utilizes test_malloc to allocate memory, copies the contents of s to the newly allocated memory, and returns it. #define strdup test_strdup is also written in line 61 in "harness.h". It seems that we should use this function in q_remove_head to return the string being deleted.

But, the operation returns a new address other than the given one recorded in sp of bool q_remove_head(queue_t *q, char *sp, size_t bufsize). Thus, the caller of bool q_remove_head would never get q->head->value in sp if the implementation is sp = strdup(q->head->value)

void sigsegvhandler(int sig)

Triggers when there is a segementation fault with SIGSEGV.

void sigalrmhandler(int sig)

Triggers when time limit exceeded with SIGALRM.

bool exception_setup(bool limit_time)

Saves states and sets up alarm.

if (sigsetjmp(env, 1)) {
    /* Got here from longjmp */
    jmp_ready = false;
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    if (error_message) {
        report_event(MSG_ERROR, error_message);
    }
    error_message = "";
    return false;
} else {
    /* Got here from initial call */
    jmp_ready = true;
    if (limit_time) {
        alarm(time_limit);
        time_limited = true;
    }
    return true;
}

State is saved in line 1. It can later be recovered with siglongjmp in void trigger_exception(char *msg) if any exception is triggered.

From man alarm:

alarm() arranges for a SIGALRM signal to be delivered to the calling process in seconds seconds.
If seconds is zero, any pending alarm is canceled.
In any event any previously set alarm() is canceled.

In line 17, time limit is set with limit_time, which is a bool type. So, the time limit is 1 second if time limit is set.

This function results in the behavior of ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient when --valgrind option is set, meaning valgrind affects the execution time of each operation:

$ ./scripts/driver.py --valgrind 2> /dev/null | grep "TOTAL"
---	TOTAL		79/100

$ ./scripts/driver.py 2> /dev/null | grep "TOTAL"
---	TOTAL		100/100