2019q1 Homework1 (lab0)

contributed by < JulianATA >

Evironment

$ uname -a
Linux 4.15.0-20-generic
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

Code analysis

Struct queue_t

From Overview of HW request,

In the starter code, this structure contains only a single field
head, but you will want to add other fields.

and the request of execution time

$O(1)$ of 2 functions, q_insert_tail and q_size.

I simply added tail and q_size for keeping the infomation of the position and the size of queue.

Then, I can implement the 2 function I mentioned in constant time in an easy way.

/* Queue structure */
typedef struct {
/* Linked list of elements */
    list_ele_t *head; 
    list_ele_t *tail;
    size_t q_size;
} queue_t;

q_new()

The key part of this function is to test if the memory allocate of q is successful or not.

If it is a successful allocate, initial its field(head, tail, q_size).
If not, return NULL.

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->q_size = 0;
        return q;
    }
    return NULL;

q_free()

Same, deal with the condition if q is NULL.
If not, create a pointer of element, use it to record the address to be deleted.

From head to tail, pointer record the head address, then let head record the next of itself, until the the next of itself is NULL.
Free the memory field of pointer every interation.

void q_free(queue_t *q)
{
    /* Free queue structure */
    if (q == NULL)
        return;
    list_ele_t *prev = NULL;
    while (q->head) {
        prev = q->head;
        q->head = q->head->next;
        free(prev->value);
        free(prev);
    }
    free(q);

q_insert_head(), q_insert_tail()

These two functions are alike, I'll explain the same part at once.

Still, check if q is NULL or not.
Then, I deal with these function from small component.

Memory allocating for value, check if it is NULL or not.
Use the (strlen(s)+1) as the string length, cause we need 1 more char for the NULL character.

Then, memory allocating for new head (or tail), check if it is NULL or not.

Crucial part of here is to free the memory of new value if the new element memory allocate failed, or it'll cause memory leak.

If q has no element, let both head and tail be the new element.

Increase the size for function q_size().

For q_insert_head, simply concate it to the origin queue.

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q == NULL)
        return false;
    char *val = malloc((strlen(s) + 1) * sizeof(char));
    if (val == NULL)
        return false;
    memset(val, '\0', strlen(s) + 1);
    strcpy(val, s);
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        free(val);
        return false;
    }

    newh->value = val;
    newh->next = q->head;

    q->q_size++;
    if (q->head == NULL)
        q->tail = newh;
    q->head = newh;
    return true;
}

For q_insert_tail,
concate it to the tail of the queue.

We require that your implementations operate in time O(1).

To achieve

$O(1)$ execution time, the simpliest way I have is to keep the address of the tail, and I can implement this funciton as q_insert_head.

Look forward to find out other solutions.

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    if (q == NULL)
        return false;
    char *val = malloc((strlen(s) + 1) * sizeof(char));
    if (val == NULL)
        return false;
    memset(val, '\0', strlen(s) + 1);
    strcpy(val, s);
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        free(val);
        return false;
    }
    newt->value = val;
    q->q_size++;
    if (q->tail == NULL) {
        q->head = newt;
        q->tail = newt;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    newt->next = NULL;
    return true;
}

q_remove_head()

Key part of this function is not to check if q is NULL and if head of q is NULL at once.

In situation that q is NULL, it'll indicate to deferencing of pointer.

Then check if sp is NULL. If it is not, copy the head value to it as required.

I free the head by an oldschool way –- Using a pointer.

Use a tmp pointer point to the head element.
Let the head pointer point to its own next element.
free the tmp element value and itself.

And remember to decrease the size for function q_size().

if(!q || !q->head)
raiso
可以參閱 C99 Standard §6.5.14 Logical OR operator
求值順序是由左向右，並且如果遇到非零數字將不會繼續往右求值
HexRabbit
非常感謝兩位！我原本的寫法是錯在我寫的是if(!q->head||!q)
才造成在q = NULL的情況下會出錯。
Julian Fang

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q||!q->head)
        return false;
        
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *tmp;
    tmp = q->head;
    q->head = q->head->next;
    q->q_size--;
    free(tmp->value);
    free(tmp);
    return true;
}

q_size

Two of the functions: q_insert_tail and q_size will require some effort on your part to meet the required performance standards. …
We require that your implementations operate in time O(1),

To meet the standard of

$O(1)$, I use q_size (structure member) to record the increase and decrease of elements in q_remove_head, q_insert_head, and q_insert_tail.

Still, do not forget to check if it is NULL, if not return q_size(structure member), else return 0.

int q_size(queue_t *q)
{
    if (q)
        return q->q_size;
    return 0;
}

q_reverse()

First, check if q, head of q, next of head is NULL or not "seperately" to avoid deferencing a pointer.

I used a naive way of three element pointers to implement this function.

Use head pointer as middle pointer can reduce some instructions.

From head to tail, use forward pointer to keep the origin next of middle pointer, backward pointer as the original previous element of middle.

Assign backward to next of middle, and let backward pointer point to middle, middle pointer point to forward.
Then let forward point to its own next, and repeat until the next of forward is NULL.

void q_reverse(queue_t *q)
{
    if (!q||!q->head||!q->head->next)
        return;
    list_ele_t *forward, *backward;

    backward = q->head;
    q->tail = q->head;
    q->head = q->head->next;
    forward = q->head->next;
    backward->next = NULL;

    while (forward) {
        q->head->next = backward;
        backward = q->head;
        q->head = forward;
        forward = forward->next;
    }
    q->head->next = backward;
}

Still not really fond of this naive solution.
Trying to figure out other way to implement it.

Technique and Behavior of qtest

First of all, I checked Makefile, then went through header files.
Excerpt from Makefile:

.
.
queue.o: queue.c queue.h harness.h
	$(CC) $(CFLAGS) -c queue.c 
.
.
.

Why we need harness.h for making queue.o?
Julian Fang

So, I take a deep look at harness.h.
Julian Fang

harness.h and harness.c

Excerpt from harness.h:

/*
  This test harness enables us to do stringent testing of code.
  It overloads the library versions of malloc and free with ones that
  allow checking for common allocation errors.
*/

#define malloc test_malloc
#define free test_free

At the beginning of harnes.h, we can see description, which indicate that one of the key parts is to overloads malloc and free.

Then, we take a deep look at test_malloc and test_free in harness.c.

Deep look at test_malloc() and test_free()

These functions are alike, I'll describe common part of my observation first.

First part of these functions, we have a mode-lock to pass back NULL for condition malloc or free failed.

Second, we have a failing simulators in test_malloc() for usual conditions.

Excerpt from harness.c:

void *test_malloc(size_t size)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to malloc disallowed");
        return NULL;
    }
    if (fail_allocation()) {
        report_event(MSG_WARN, "Malloc returning NULL");
        return NULL;
    }
.
.
.

In test_malloc(), it still uses malloc to allocate memory, but the parameter is different.
It gives every element(new_block) 1 memory size ofsize_t(for Magicfooter),and 1 size we required(for queue element we want), and 1 size of block_ele_t.

.
.
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }
.
.
.

Then, pass MAGICHEADER and MAGICFOOTER, or MAGICFREE for test_free(), to element(new_block).

.
.
    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    void *p = (void *) &new_block->payload;
.
.
.

Why do we need MAGICHEADER, MAGICFOOTER, and MAGICFREE?
Julian Fang

Describe at the begining of harness.c, and structure definition of block_ele_t.
Julian Fang

Excerpt from harness.c:

/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead

Filled the queue element we required with 0x55(bitmask).

I don't know why we need this bitmask here, I'll complete here after I find out.
Julian Fang

Finally, concatenate new_block to lastest block allocated.

.
.
    memset(p, FILLCHAR, size);
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

First part of testfree(), simply check mode and check if p is NULL or not.

void test_free(void *p)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to free disallowed");
        return;
    }
    if (p == NULL) {
        report(MSG_ERROR, "Attempt to free NULL");
        error_occurred = true;
        return;
    }
.
.
.

Use block_ele_t pointer to get value in p, check if footer is the magic footer or not.

.
.
    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
.
.
.

Set the header and footer to MAGICFREE, reoder the block doubly link list, and done!

.
.

    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);

    /* Unlink from list */
    block_ele_t *bn = b->next;
    block_ele_t *bp = b->prev;
    if (bp)
        bp->next = bn;
    else
        allocated = bn;
    if (bn)
        bn->prev = bp;

    free(b);
    allocated_count--;
}

We can notice that when error occurs, like when header is not MAGICHEADER, when trying free a NULL pointer … …, an bool variable error_occurred will set to true.

We can see that we have a corresponding function here.

Excerpt form harness.c:

/*
  Return whether any errors have occurred since last time set error limit
 */
bool error_check()
{
    bool e = error_occurred;
    error_occurred = false;
    return e;
}

This one of the key parts of the error detection.

Now, I knew roughly how it detect memory allocation and free errors without crashing.

And, we'll find out how the simple command-line interface works.

Test on MAGICHEADER, MAGICFOOTER, MAGICFREE

Todo

console.h and console.c

First, take a look at console.h.

Excerpt form console.h:

/* Each command defined in terms of a function */
typedef bool (*cmd_function)(int argc, char *argv[]);
.
.
.

It uses function pointer for each command.
At the begining of the console.h, we knew that each command will trigger a corresponding function.

I have a doubt that where should I start to trace an unfamiliar code of C?
I used to start from Makefile, and then headers.
Is there a formal order?
-Julian Fang

tags: Cprogramming LinuxKernel