2021q1 Homework1 (lab0)

contributed by < RZHuangJeff >

tags: `linux2021`

Environment

$ uname -a
Linux vostro-5471 5.8.0-44-generic #50-Ubuntu SMP Tue Feb 9 06:29:41 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version | head -1
gcc (Ubuntu 10.2.0-13ubuntu1) 10.2.0

Goal of Homework

Impelment following functions in queue.[ch]:

q_new: Create a new, empty queue.
q_free: Free all storage used by a queue.
q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
q_remove_head: Attempt to remove the element at the head of the queue.
q_size: Compute the number of elements in the queue.
q_reverse: Reorder the list so that the queue elements are reversed in order. This function should notallocate or free any list elements.
q_sort: Sort the elements of the given queue in ascending order.

Development Flow

queue.h

queue.c

q_new

Make sure if q is valid before inititalizing its contents.











queue_t *q_new()
{
    queue_t *q;
    if (!(q = malloc(sizeof(queue_t))))
        return NULL;

    q->head = NULL;
    q->tail = &(q->head);
    q->size = 0;
    return q;
}

q_free

Free all storage used by queue
Do not thing if q is NULL

Run through entire queue with a temporary variable cur and free the space pointed by cur
















void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *cur;
    while (q->head) {
        cur = q->head;
        q->head = cur->next;

        free(cur->value);
        free(cur);
    }

    free(q);
}

q_insert_head

Insert an element at head of queue
Allocate a space explicitly to copy string into it
Make sure that all pointers are valid

























bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    size_t slen = strlen(s) + 1;
    list_ele_t *newh;
    if (!(newh = malloc(sizeof(list_ele_t))))
        return false;

    if (!(newh->value = malloc(slen))) {
        free(newh);
        return false;
    }

    memcpy(newh->value, s, slen);

    newh->next = q->head;
    q->head = newh;
    q->size++;
    if (!(newh->next))
        q->tail = &(newh->next);
        
    return true;
}

q_remove_head

Remove an element from head of queue
Copy the value of removed element into sp if sp is not NULL
























bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !(q->head))
        return false;

    list_ele_t *rem = q->head;
    size_t remlen = strlen(rem->value);
    size_t cpylen = remlen < bufsize - 1 ? remlen : bufsize - 1;

    if (sp) {
        memcpy(sp, rem->value, cpylen);
        sp[cpylen] = '\0';
    }

    q->head = rem->next;
    q->size--;
    if (!(q->head))
        q->tail = &(q->head);

    free(rem->value);
    free(rem);

    return true;
}

q_insert_tail

Insert an element to tail of queue
Do nothing while q is NULL
Allocate a space explicitly to copy string into it
Operating in O(1) time

In order to reach O(1) operation time, tail is introduced to queue_t, which is type of list_ele_t**. The reason why defines tail as list_ele_t** is to simplify checking of edge condition such as insert tail in the empty queue.





























typedef struct {
    /* Other fields in structure */
    list_ele_t **tail;
} queue_t;

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    size_t slen = strlen(s) + 1;
    list_ele_t *newt;
    if (!(newt = malloc(sizeof(list_ele_t))))
        return false;

    if (!(newt->value = malloc(slen))) {
        free(newt);
        return false;
    }

    memcpy(newt->value, s, slen);

    newt->next = NULL;
    *(q->tail) = newt;
    q->tail = &(newt->next);
    q->size++;

    return true;
}

q_reverse

Reverse the order of elements in the queue
No effect if q is NULL or empty or with only one element in it
No allocations of elements

temp_head reprecents the head of reversed queue, in each loop round, cur points to the element would be reverse.


















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

    q->tail = &(q->head->next);

    list_ele_t *tmp_head = NULL, *cur;
    while (q->head) {
        cur = q->head;
        q->head = cur->next;

        cur->next = tmp_head;
        tmp_head = cur;
    }

    q->head = tmp_head;
}

q_size

Report the size of given queue
Return 0 for NULL or empty queue
Operating in O(1) time

In order to reach O(1) operation time, size was introduced to queue_t, initialized with zero, and will be updated each time an element is inserted or removed via q_insert_head, q_insert_tail or q_remove_head.










typedef struct {
    /* Other fields in structure ... */
    
    size_t size;
} queue_t;

int q_size(queue_t *q)
{
    return !q ? 0 : q->size;
}

q_sort

Sort the elements in the given queue in acensing order
Capable for passing NULL or empty queue as argument
No Allocations or frees for temporary storage
Operating in O(nlogn) time

In order to reach O(nlogn) operation time, merge sort is choosen as the algorithm of implementation.
There are two functions, divide and merge, introduced and will cooperate with q_sort to fulfill the task.
Function divide aims to cut a queue into two. It first set the size of subqueue(line 15), then run through the list to find the point to cut(for loop around line 19), finally resets all coresponding fields around cut to make divide happend. Notice that there is no checking for edge conditions such as NULL or the queue with no more than 2 elements in it, since it will only be called by q_sort, which has already checked such conditions(line 3).
Function merge expects two queues with their elements are both in acensing order as its arguments. To merge these queues, it will run through each elements in a(for loop between line 32 - 41), find the right place for each element in b(line 33), and insert them to that place(line 35 - 39). Since that elements in b are in acensing order, it should only run through a once. Finally, if there are any element in b after the for loop, those elements will be attached to the tail of a. With the same condition mentioned above, this function does not provide checking for edge condition.


















































void q_sort(queue_t *q)
{
    if (!q || !(q->head) || !(q->head->next))
        return;

    queue_t b;
    divide(q, &b);
    q_sort(q);
    q_sort(&b);
    merge(q, &b);
}

static void divide(queue_t *a, queue_t *b)
{
    b->size = a->size / 2;
    b->tail = a->tail;

    list_ele_t *cut = a->head;
    for (size_t i = b->size; i > 1; i--)
        cut = cut->next;

    b->head = cut->next;

    cut->next = NULL;
    a->tail = &(cut->next);
    a->size -= b->size;
}

static void merge(queue_t *a, volatile queue_t *b)
{
    list_ele_t *tmp, **ori_tail = a->tail;
    for (a->tail = &(a->head); *(a->tail) && b->head;
         a->tail = &((*(a->tail))->next)) {
        if (strcmp((*(a->tail))->value, b->head->value) > 0) {
            tmp = b->head;
            b->head = b->head->next;

            tmp->next = *(a->tail);
            *(a->tail) = tmp;
        }
    }

    if (b->head) {
        *(a->tail) = b->head;
        a->tail = b->tail;
    } else
        a->tail = ori_tail;

    a->size += b->size;
}

Address Sanitizer Error in `qtest`

How I Locate the Error

First, I follow the step mentioned in homework description, which make error happend.







































































$ make SANITIZER=1

$ ./qtest
cmd> help
cmd> help
Commands:
        #        ...            | Display comment
        free                    | Delete queue
        help                    | Show documentation
        ih       str [n]        | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        it       str [n]        | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        log      file           | Copy output to file
        new                     | Create new queue
        option   [name val]     | Display or set options
        quit                    | Exit program
        reverse                 | Reverse queue
        rh       [str]          | Remove from head of queue.  Optionally compare to expected value str
        rhq                     | Remove from head of queue without reporting value.
        show                    | Show queue contents
        size     [n]            | Compute queue size n times (default: n == 1)
        sort                    | Sort queue in ascending order
        source   file           | Read commands from source file
        time     cmd arg ...    | Time command execution
Options:
=================================================================
==60472==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55d6527d07a0 at pc 0x55d6527c042f bp 0x7ffcb7b353a0 sp 0x7ffcb7b35390
READ of size 4 at 0x55d6527d07a0 thread T0
    #0 0x55d6527c042e in do_help_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306
    #1 0x55d6527c0542 in interpret_cmda /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:220
    #2 0x55d6527c0f7c in interpret_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:243
    #3 0x55d6527c1e4c in cmd_select /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:607
    #4 0x55d6527c1ffc in run_console /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:628
    #5 0x55d6527bf066 in main /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest.c:772
    #6 0x7f35e48d2cb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #7 0x55d6527bc88d in _start (/media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest+0x788d)

0x55d6527d07a1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:58:13' (0x55d6527d07a0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306 in do_help_cmd
Shadow bytes around the buggy address:
  0x0abb4a4f20a0: 00 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0abb4a4f20b0: 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
  0x0abb4a4f20c0: 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9
  0x0abb4a4f20d0: 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0abb4a4f20e0: 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
=>0x0abb4a4f20f0: f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
  0x0abb4a4f2100: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0abb4a4f2110: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abb4a4f2120: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abb4a4f2130: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abb4a4f2140: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==60472==ABORTING

At this moment, I notice several lines of this error message, which helps me to locate where exactly error happends: First, at line 24, after showing Options: there should be several lines of options. Second, from the stack trace shown by Address Sanitizer(around line 28 - 35), it shows that the error happends at line 306 in file console.c.


/* Line 306 of console.c */
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation);

What Happend

Since that the stack trace of Address Sanitizer says that the error happened in do_help_cmd, not in report, furthermore, at line 27 of error message shown above, it says that a READ of size 4 at 0x55d6527d07a0 causes the error.
At this moment, I can roughly determine that *plist->valp causes the error, since that only field valp, which has type of int*, can cause a read of size 4 while dereferencing it and passing it as argument.
Since parm_list was initialized in function init_cmd, I turn my attention to this function. According to add_param in console.c, the parameters in param_list are ranked with dictionary order, we can find that parameter echo added at line 106 in console.c causes that error.
At line 58, echo is defined as type bool rather than int. Dereferencing it as int* may cause the error. To confirm my hypothesis, I comment out line 106, which add option echo into option list, then following happends:

















## Lines of outputs
==61145==ERROR: AddressSanitizer: global-buffer-overflow on address 0x56434c3bb940 at pc 0x56434c3a942f bp 0x7fff1611ca50 sp 0x7fff1611ca40
READ of size 4 at 0x56434c3bb940 thread T0
    #0 0x56434c3a942e in do_help_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306
    #1 0x56434c3a9542 in interpret_cmda /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:220
    #2 0x56434c3a9f7c in interpret_cmd /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:243
    #3 0x56434c3aae2d in cmd_select /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:607
    #4 0x56434c3aafdd in run_console /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:628
    #5 0x56434c3a8066 in main /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest.c:772
    #6 0x7f1a37a50cb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #7 0x56434c3a588d in _start (/media/forward1105/DATA_1/CCodes/linux2021/lab0-c/qtest+0x788d)

0x56434c3bb941 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x56434c3bb940) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/console.c:306 in do_help_cmd

## Following lines are omited

The same error happended on parameter simulation, which also defined as type bool. And both echo and simulation are casted to int* while being added into param_list.
Since here, I guess that the difference between the size of bool and int causes the error. To ensure that, I compile and run the following code(with compile flags -fsanitize=address -fno-omit-frame-pointer -fno-common).














#include <stdio.h>
#include <stdbool.h>

static bool a = false;

int main()
{
    printf("sizeof bool: %lu\nsizeof int: %lu\n", sizeof(bool), sizeof(int));

    int *aptr = (int*)&a;
    int result = *aptr;

    return 0;
}

The program reports that the size of bool and int are 1 and 4, respectively. And it also causes the same error while tries to access a via aptr(reported at line 6 - 7 in following error messages):













$ ./test
sizeof bool: 1
sizeof int: 4
=================================================================
==61999==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e53027e0e0 at pc 0x55e53027b252 bp 0x7fffe53b2d90 sp 0x7fffe53b2d80
READ of size 4 at 0x55e53027e0e0 thread T0
    #0 0x55e53027b251 in main /media/forward1105/DATA_1/CCodes/linux2021/lab0-c/test.c:11
    #1 0x7f1b9b053cb1 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #2 0x55e53027b12d in _start (/media/forward1105/DATA_1/CCodes/linux2021/lab0-c/test+0x112d)

0x55e53027e0e1 is located 0 bytes to the right of global variable 'a' defined in 'test.c:4:13' (0x55e53027e0e0) of size 1

## Following lines are omited

With such evidence, I believe that dereferencing a pointer to int, which actually points to variable with type bool, causes the error.

Solution

The first solution came up my mind is to redefine echo and simulation as type int. I think this solution works fine to echo, since it is a static variable, which can only be accessed inside console.c, but not for simulation, which is defined export in console.h and would be accessed in qtest.c, redefine it will cause a chain effect to recheck files that access it.
Cause the reson mentioned above, I'm still figuring out if there is another solution.

2021q1 Homework1 (lab0)

tags: linux2021

Environment

Goal of Homework

Development Flow

queue.h

queue.c

Address Sanitizer Error in qtest

How I Locate the Error

What Happend

Solution

Read more

2021-04-06 RZHuangJeff

Linux 核心搶佔

2021q1 Homework5 (quiz5)

2021q1 Homework4 (quiz4)

tags: `linux2021`

Address Sanitizer Error in `qtest`