2023q1 Homework1 (lab0)

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;

    INIT_LIST_HEAD(new);

    return new;
}

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *safe, *it;
    list_for_each_entry_safe (it, safe, l, list)
        q_release_element(it);

    free(l);
}

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    struct list_head *safe;
    struct list_head *it;

    list_for_each_safe (it, safe, l) {
        list_del(it);
        free(it);
    }

    free(l);
}

@@ -5,8 +5,10 @@ void q_free(struct list_head *l)
     struct list_head *it;
 
     list_for_each_safe (it, safe, l) {
+        element_t *elem = list_entry(it, element_t, list);
         list_del(it);
-        free(it);
+        free(elem->value);
+        free(elem);
     }
 
     free(l);

@@ -1,14 +1,12 @@
 /* Free all storage used by queue */
 void q_free(struct list_head *l)
 {
-    struct list_head *safe;
-    struct list_head *it;
+    element_t *safe;
+    element_t *it;
 
-    list_for_each_safe (it, safe, l) {
-        element_t *elem = list_entry(it, element_t, list);
-        list_del(it);
-        free(elem->value);
-        free(elem);
+    list_for_each_entry_safe (it, safe, l, list) {
+        list_del(&it->list);
+        q_release_element(it);
     }
 
     free(l);

@@ -1,13 +1,12 @@
 /* Free all storage used by queue */
 void q_free(struct list_head *l)
 {
-    element_t *safe;
-    element_t *it;
+    if (!l)
+        return;
 
-    list_for_each_entry_safe (it, safe, l, list) {
-        list_del(&it->list);
+    element_t *safe, *it;
+    list_for_each_entry_safe (it, safe, l, list)
         q_release_element(it);
-    }
 
     free(l);
 }

/* Create a new element with the provided string */
static inline element_t *q_new_elem(char *s)
{
    element_t *elem = malloc(sizeof(element_t));
    if (!elem)
        return NULL;

    char *tmp = strdup(s);
    if (!tmp) {
        free(elem);
        return NULL;
    }

    elem->value = tmp;
    return elem;
}

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = q_new_elem(s);
    if (!elem)
        return false;

    list_add(&elem->list, head);

    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = q_new_elem(s);
    if (!elem)
        return false;

    list_add_tail(&elem->list, head);

    return true;
}

static inline void q_copy_string(char *dest, size_t size, const char *src)
{
    size_t i;
    for (i = 0; i < size - 1 && src[i] != '\0'; i++)
        dest[i] = src[i];

    dest[i] = '\0';
}

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *elem = list_first_entry(head, element_t, list);
    list_del(&elem->list);

    if (sp && bufsize)
        q_copy_string(sp, bufsize, elem->value);

    return elem;
}

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int count = 0;
    struct list_head *it;

    list_for_each (it, head)
        count++;

    return count;
}

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *left = head->next;
    struct list_head *right = head->prev;

    while (left != right && left->next != right) {
        left = left->next;
        right = right->prev;
    }

    list_del(right);
    element_t *elem = list_entry(right, element_t, list);
    q_release_element(elem);

    return true;
}

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    LIST_HEAD(pending);
    element_t *it, *safe;
    struct list_head *cut = head;

    list_for_each_entry_safe (it, safe, head, list) {
        if (&safe->list != head && !strcmp(safe->value, it->value))
            continue;
        /* Detect duplicated elements */
        if (it->list.prev != cut) {
            LIST_HEAD(tmp);
            list_cut_position(&tmp, cut, &it->list);
            list_splice(&tmp, &pending);
        }
        cut = safe->list.prev;
    }

    /* Process pending list */
    list_for_each_entry_safe (it, safe, &pending, list)
        q_release_element(it);

    return true;
}

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *it, *safe;
    /* Iterate the list and move each item to the head */
    list_for_each_safe (it, safe, head)
        list_move(it, head);
}

diff --git a/queue.c b/queue.c
diff --git a/queue.c b/queue.c
     struct list_head *it, *safe;
     /* Iterate the list and move each item to the head */
-    list_for_each_safe (it, safe, head) {
+    list_for_each_safe (it, safe, head)
         list_move(it, head);
-    }
 }

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    struct list_head *it, *safe, *cut;
    int count = k;
    cut = head;
    list_for_each_safe (it, safe, head) {
        if (--count)
            continue;
        LIST_HEAD(tmp);
        count = k;
        list_cut_position(&tmp, cut, it);
        q_reverse(&tmp);
        list_splice(&tmp, cut);
        cut = safe->prev;
    }
}

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    q_reverseK(head, 2);
}

static int q_merge_two(struct list_head *first, struct list_head *second)
{
    if (!first || !second)
        return 0;

    int count = 0;
    LIST_HEAD(tmp);
    while (!list_empty(first) && !list_empty(second)) {
        element_t *f = list_first_entry(first, element_t, list);
        element_t *s = list_first_entry(second, element_t, list);
        if (strcmp(f->value, s->value) <= 0)
            list_move_tail(&f->list, &tmp);
        else
            list_move_tail(&s->list, &tmp);
        count++;
    }
    count += q_size(first) + q_size(second);
    list_splice(&tmp, first);
    list_splice_tail_init(second, first);

    return count;
}

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    /* Try to use merge sort*/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    /* Find middle point */
    struct list_head *mid, *left, *right;
    left = right = head;
    do {
        left = left->next;
        right = right->prev;
    } while (left != right && left->next != right);
    mid = left;

    /* Divide into two part */
    LIST_HEAD(second);
    list_cut_position(&second, mid, head->prev);

    /* Conquer */
    q_sort(head);
    q_sort(&second);

    /* Merge */
    q_merge_two(head, &second);
}

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /**
     * Traverse from the last entry and remove the element that is
     * smaller or equal to its right. Also count the number of elements.
     */
    int cnt = 1;
    element_t *cur = list_last_entry(head, element_t, list);
    while (cur->list.prev != head) {
        element_t *prev = list_last_entry(&cur->list, element_t, list);
        if (strcmp(prev->value, cur->value) < 0) {
            list_del(&prev->list);
            q_release_element(prev);
        } else {
            cnt++;
            cur = prev;
        }
    }

    return cnt;
}

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;

    if (list_is_singular(head))
        return list_first_entry(head, queue_contex_t, chain)->size;

    /* Use 2-merge algorithm in https://arxiv.org/pdf/1801.04641.pdf */
    LIST_HEAD(pending);
    LIST_HEAD(empty);
    int n = 0;
    while (!list_empty(head)) {
        list_move(head->next, &pending);
        n++;

        while (n > 3) {
            queue_contex_t *x, *y, *z;
            x = list_first_entry(&pending, queue_contex_t, chain);
            y = list_first_entry(&x->chain, queue_contex_t, chain);
            z = list_first_entry(&x->chain, queue_contex_t, chain);

            if (y->size >= z->size << 1)
                break;

            if (x->size < z->size) {
                y->size = q_merge_two(y->q, x->q);
                list_move(&x->chain, &empty);
                n--;
            } else {
                z->size = q_merge_two(z->q, y->q);
                list_move(&y->chain, &empty);
                n--;
            }
        }
    }

    /* Merge remaining list */
    while (n > 1) {
        queue_contex_t *x, *y;
        x = list_first_entry(&pending, queue_contex_t, chain);
        y = list_first_entry(&x->chain, queue_contex_t, chain);
        y->size = q_merge_two(y->q, x->q);
        list_move(&x->chain, &empty);
        n--;
    }

    /* Move the last queue and empty queue to head */
    list_splice(&empty, head);
    list_splice(&pending, head);

    return list_first_entry(head, queue_contex_t, chain)->size;
}

int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /**
     * Traverse from the last entry and remove the element that is
     * smaller or equal to its right. Also count the number of elements.
     */
    int cnt = 1;
    element_t *cur = list_last_entry(head, element_t, list);
    while (cur->list.prev != head) {
        element_t *prev = list_last_entry(&cur->list, element_t, list);
        if (strcmp(prev->value, cur->value) > 0) {
            list_del(&prev->list);
            q_release_element(prev);
        } else {
            cnt++;
            cur = prev;
        }
    }

    return cnt;
}

valgrind: valgrind_existence
	# Explicitly disable sanitizer(s)
	$(MAKE) clean SANITIZER=0 qtest
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)
	scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==30743== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==30743==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==30743==    by 0x10CBE6: do_new (qtest.c:146)
==30743==    by 0x10DE12: interpret_cmda (console.c:181)
==30743==    by 0x10E3C7: interpret_cmd (console.c:201)
==30743==    by 0x10E7C8: cmd_select (console.c:610)
==30743==    by 0x10F0B4: run_console (console.c:705)
==30743==    by 0x10D204: main (qtest.c:1228)
==30743== 

--- a/qtest.c
+++ b/qtest.c
@@ -1059,7 +1059,6 @@ static void q_init()
 
 static bool q_quit(int argc, char *argv[])
 {
-    return true;
     report(3, "Freeing queue");
     if (current && current->size > BIG_LIST_SIZE)
         set_cautious_mode(false);

==33817== 130 bytes in 10 blocks are still reachable in loss record 1 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817== 
==33817== 130 bytes in 10 blocks are still reachable in loss record 2 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x10F10C: run_console (console.c:692)
==33817==    by 0x10D2D7: main (qtest.c:1227)
==33817== 
==33817== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x112205: line_history_add (linenoise.c:1263)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817== 

--- a/linenoise.c
+++ b/linenoise.c
@@ -243,10 +243,6 @@ static int enable_raw_mode(int fd)
 {
     if (!isatty(STDIN_FILENO))
         goto fatal;
-    if (!atexit_registered) {
-        atexit(line_atexit);
-        atexit_registered = true;
-    }
     if (tcgetattr(fd, &orig_termios) == -1)
         goto fatal;
 
@@ -1189,6 +1185,11 @@ char *linenoise(const char *prompt)
 {
     char buf[LINENOISE_MAX_LINE];
 
+    if (!atexit_registered) {
+        atexit(line_atexit);
+        atexit_registered = true;
+    }
+
     if (!isatty(STDIN_FILENO)) {
         /* Not a tty: read from file / pipe. In this mode we don't want any
          * limit to the line size, so we call a function to handle that. */

make clean
make SANITIZER=1

         element_t *f = list_first_entry(first, element_t, list);
         element_t *s = list_first_entry(second, element_t, list);
-        if (strcmp(f->value, s->value) <= 0)
+        int cmp = strcmp(f->value, s->value);
+        if (descend)
+            cmp = -cmp;
+        if (cmp <= 0)
             list_move_tail(&f->list, &tmp);
         else
             list_move_tail(&s->list, &tmp);

static int q_merge_two(struct list_head *first,
                       struct list_head *second,
                       bool descend)

static int q_cmp_descend(void *priv,
                         const struct list_head *a,
                         const struct list_head *b)
{
    return -q_cmp(priv, a, b);
}

void q_ksort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    list_cmp_func_t cmp = descend ? q_cmp_descend : q_cmp;

    list_sort(NULL, head, cmp);
}

static int q_cmp(void *priv,
                 const struct list_head *a,
                 const struct list_head *b)
{
    // cppcheck-suppress nullPointer
    element_t *elem_a = list_entry(a, element_t, list);
    // cppcheck-suppress nullPointer
    element_t *elem_b = list_entry(b, element_t, list);

    return strcmp(elem_a->value, elem_b->value);
}

static int use_ksort = 0;

add_param("ksort", &use_ksort,
          "Whether to use Linux kernel sorting algorithm", NULL);

new
option ksort 1/0 <= 跟據要測試的排序實作進行切換
ih RAND 2000000
shuffle
time sort        <= 執行 10 次取平均， 中間以 shuffle 間隔

struct list_head **entries = malloc(sizeof(struct list_head *) * size);

int i = 0;
list_for_each (node, head)
    entries[i++] = node;

int n;
do {
    n = rand();
} while (n >= RAND_MAX - (RAND_MAX % (i + 1)));
n %= i + 1;

option entropy 1
new
it RAND 10

l = [haiowq(29.69%) wncthutns(32.81%) yhzrx(26.56%) dfjqntag(35.94%) whgushb(29.69%) ciahh(21.88%) oidgffg(26.56%) pmeqkxou(35.94%) xffww(17.19%) nrgavix(32.81%)]

case 'r':
    char *endptr;
    errno = 0;
    qrandom_impl = strtol(optarg, &endptr, 10);
    if (errno != 0 || endptr == optarg) {
        fprintf(stderr, "Invalid random number generator\n");
        exit(EXIT_FAILURE);
    }
    generate_randombytes();
    break;

#define RANDOM_BYTES 1048576
static void generate_randombytes(void)
{
    uint8_t *buf = malloc(RANDOM_BYTES);
    if (!buf)
        exit(1);

    do {
        qrandombytes(buf, RANDOM_BYTES);
    } while (fwrite(buf, RANDOM_BYTES, 1, stdout));

    exit(0);
}

./qtest -r 1 | head -c 10M | ent
Entropy = 7.999998 bits per byte

Optimum compression would reduce the size
of this 104857600 byte file by 0 percent.

Chi square distribution for 104857600 samples is 264.69, and randomly
would exceed this value 32.52 percent of the times.

Arithmetic mean value of data bytes is 127.4997 (127.5 = random).
Monte Carlo value for Pi is 3.142157713 (error 0.02 percent).
Serial correlation coefficient is 0.000097 (totally uncorrelated = 0.0).

$ ./qtest -r 0 | head -c 10M | ent
Entropy = 7.999983 bits per byte.

Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.

Chi square distribution for 10485760 samples is 248.23, and randomly
would exceed this value 60.75 percent of the times.

Arithmetic mean value of data bytes is 127.4847 (127.5 = random).
Monte Carlo value for Pi is 3.141642434 (error 0.00 percent).
Serial correlation coefficient is -0.000522 (totally uncorrelated = 0.0).

typedef struct __dudect_config dudect_config_t;

typedef void (*dudect_prepare_func_t)(void *priv,
                                      dudect_config_t *conf,
                                      uint8_t *input_data,
                                      uint8_t *classes);

typedef uint8_t (*dudect_compute_func_t)(void *priv,
                                         size_t size,
                                         uint8_t *data);

struct __dudect_config {
    size_t chunk_size;
    size_t number_measurements;
    void *priv;
    dudect_prepare_func_t prepare;
    dudect_compute_func_t compute;
};

typedef enum {
    DUDECT_LEAKAGE_FOUND = 0,
    DUDECT_NO_LEAKAGE_EVIDENCE_YET,
    DUDECT_NOT_ENOUGHT_MEASUREMENTS,
} dudect_state_t;

diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index 56c7d9e..6ed0b93 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -8,6 +8,7 @@ jobs:
     steps:
     - uses: actions/checkout@v3.3.0
     - uses: webfactory/ssh-agent@v0.7.0
+      continue-on-error: true
       with:
           ssh-private-key: ${{ secrets.SSH_PRIVATE_KEY }}
     - name: install-dependencies