2019q1 Homework1 (lab0)

contributed by < TsundereChen >

tags: sysprog TsundereChen

• GitHub Repo

Report

queue.h & queue.c

struct queue_t

• Add list_ele_t *tail and int size in order to track queue more easily

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

queue_t *q_new()

• It's just initializing queue, using malloc
• Check if malloc failed

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

void q_free(queue_t *q)

• Check if queue is valid, and free from the head to the tail

void q_free(queue_t *q)
{
    if (q != NULL && ((q->head != NULL) && (q->tail != NULL))) {
        while (q->head != q->tail) {
            list_ele_t *del_t = q->head;
            q->head = q->head->next;
            free(del_t->value);
            free(del_t);
        }
        free(q->tail->value);
        free(q->tail);
    }
    free(q);
}

bool q_insert_head(queue_t *q, char *s)

• Insert an element at head of the queue
• I thought this was easy, until I got a problem
• When doing malloc to new_h->value, I allocated 1 more char's size to it
  I did the same thing at strncpy(new_h->value...
• I thought the right way to copy the value is to allocate only the string's size,
  and don't need one more char's space.
  But that failed, and add one more char's space makes me passes all the tests
• I don't know why

Find out the problem

TsundereChen

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *new_h = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (new_h == NULL)
        return false;
    new_h->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (new_h->value == NULL) {
        free(new_h);
        return false;
    }
    strncpy(new_h->value, s, strlen(s) + 1);
    new_h->next = q->head;
    q->head = new_h;
    if (q->tail == NULL)
        q->tail = new_h;
    q->size += 1;
    return true;
}

bool q_insert_tail(queue_t *q, char *s)

• Basically the same as q_insert_head
• And have the same issue just like q_insert_head

Find out the problem

TsundereChen

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *new_t = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (new_t == NULL)
        return false;
    new_t->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (new_t->value == NULL) {
        free(new_t);
        return false;
    }
    strncpy(new_t->value, s, strlen(s) + 1);
    new_t->next = NULL;
    if (q->tail != NULL)
        q->tail->next = new_t;
    q->tail = new_t;
    if (q->head == NULL)
        q->head = new_t;
    q->size += 1;
    return true;
}

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

• There's a function called do_remove_head_quiet inside qtest.c,
  what this function does is call q_remove_head(queue, NULL, 0)
• So need to check the value of *sp and bufsize

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0)
        return false;
    if (sp == NULL && bufsize == 0) {
        // Do nothing, skip to value removal
    } else {
        memset(sp, '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *del_h = q->head;
    q->size -= 1;
    if (q->size == 0) {
        q->head = NULL;
        q->tail = NULL;
    } else
        q->head = q->head->next;
    free(del_h->value);
    free(del_h);
    return true;
}

int q_size(queue_t *q)

• By adding int size in struct queue_t,
  this function just need to check if q is valid, and return q->size

int q_size(queue_t *q)
{
    if (q != NULL)
        return q->size;
    else
        return 0;
}

void q_reverse(queue_t *q)

• I found this page online: Linked List: 新增資料、刪除資料、反轉
• This method keeps the time complexity in O(n), which can pass the test

void q_reverse(queue_t *q)
{
   	if (q == NULL || q->size < 2)
       	return;
   	else {
       	list_ele_t *tmph = q->head;
       	list_ele_t *tmpt = q->tail;
       	list_ele_t *previous = NULL;
       	list_ele_t *current = q->head;
       	list_ele_t *preceding = q->head->next;
       	while (preceding != NULL) {
           	current->next = previous;
           	previous = current;
           	current = preceding;
           	preceding = preceding->next;
       	}
       	current->next = previous;
       	q->head = tmpt;
       	q->tail = tmph;
       	return;
   	}
}

qtest.c

• There are two kinds of malloc/free/strdup
  One is provided by <string.h>, the other one is written by CMU
  Latter is for tracking if your program behaves correctly or not
  Check harness.c & harness.h for more information

report.c & report.h

harness.h

• In these files, there are some functions related to testing the program

void *test_malloc(size_t size)

void test_free(void *p)

char *test_strdup(const cahr *s)

Functions below are defined only if INTERNAL is defined

size_t allocation_check()

int fail_probability

void set_cautious_mode(bool cautious)

void set_noallocate_mode(bool noallocate)

bool error_check()

bool exception_setup(bool limit_time)

void exception_cancel()

void trigger_exception(char *msg)

harness.c

• Test program has designed few values for checking the program
  • MAGICHEADER, value at start of every allocated block
  • MAGICFREE, value when deallocate block
  • MAGICFOOTER, value at end of every block
  • FILLCHAR, value to fill every malloced space
• The qtest program validates the queue using these values
• Inside harness.c, there are boolean values being used to change
  behavior while testing the queue
  • cautious_mode
  • noallocate_mode
• There's a comment called Data for managing exceptions, and there are
  three variables
  • static jmp_buf env
  • static volatile sig_atomic_t jmp_ready = false
  • static bool time_limited
  • According to this page C 語言 setjmp 與 longjmp 函數用法教學
    • The testing program is using static jmp_buf env to jump back when error occured
  • And according to C99 standard - 5.1.2.3 Program execution - Point 5
    • volatile is keep the variable stable when previous acceses
      are completed and subsequent accesses haven't yet occured
    • In other words, volatile means when using this variable, program must get its value from its address
  • And according to GNU libc Manual - 24.4.7.2 Atomic Types
    • sig_atomic_t can guarantee that read/write to this data type must happen in a single instruction, so there's no chance for "interruption"
  • volatile sig_atomic_t can ensure that this variable won't be optimized by compiler,
    and operation related to this variable must be done in single instruction

console.c & console.h

TODO

• Modify queue.c/.h to pass make test
• Find the issue with q_insert_head and q_insert_tail
• Test lab0-c with valgrind
• Understand how auto-testing system works

Environment

tsundere:~/ $ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  1
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               45
Model name:          Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz
Stepping:            7
CPU MHz:             1588.970
CPU max MHz:         2400.0000
CPU min MHz:         1200.0000
BogoMIPS:            4787.82
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            10240K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm arat pln pts flush_l1d
tsundere:~/ $ free -h
              total        used        free      shared  buff/cache   available
Mem:           7.7G        327M        130M        1.5M        7.3G        7.1G
Swap:          4.0G        1.0M        4.0G
tsundere:~/ $ hostnamectl
   Static hostname: tsundere-ml350p-gen8
         Icon name: computer-desktop
           Chassis: desktop
        Machine ID: 720027c2530340c2adc88062a5ca9e3d
           Boot ID: 20ff904e3f6f454e8095de141c1e3c10
  Operating System: Ubuntu 18.04.2 LTS
            Kernel: Linux 4.15.0-45-generic
      Architecture: x86-64

Reference