---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `oucs638` >
## Test Environment
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping: 13
CPU MHz: 3594.185
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## Implement Progress Records
> [Homework Requirement](https://hackmd.io/@sysprog/linux2022-lab0)
- There is the Linux-like doubly-linked list implementation in [lab0-c/list.h](https://github.com/oucs638/lab0-c/blob/master/list.h).
- Reference: [Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
- Simplify the code with these APIs.
### q_new
- Create empty queue.
- Return `NULL` if failed to allocate enough memory space.
- Initialize queue before returning it.
```c
struct list_head *q_new()
{
// allocate memory space for list head
struct list_head *head = malloc(sizeof(struct list_head));
// failed to allocate space
if (!head)
return NULL;
// allocate space success, init it
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
- Iterate over list entries and release every element.
- Use `list_for_each_entry_safe(entry, safe, head, member)` to iterate since it will save the next node in temporary storage, so it allows removing the current node.
- Invoke `q_release_element(element_t *e)` to free the node.
```c
void q_free(struct list_head *l)
{
if (!l)
return;
// iterate over list entries and release every element
element_t *cur = NULL, *nxt = NULL;
list_for_each_entry_safe (cur, nxt, l, list)
q_release_element(cur);
// release list head
free(l);
}
```
### q_insert_head
- Allocate memory space for new element.
- Allocate memory space for value in new element before copying the string into it.
- Invoke `memcpy()` to copy the string into value in new element.
- Invoke `list_add()` to add the new node to the beginning of the list.
```c
bool q_insert_head(struct list_head *head, char *s)
{
// return flase if queue if NULL
if (!head)
return false;
// allocate memory space for new queue element
// return false if allocate space failed
// initialize "list" in new element
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
INIT_LIST_HEAD(&new->list);
// allocate memory space for "value" in new element
// allocate one addtional character of memory space for '\0'
// return false if allocate space failed
size_t len = strlen(s) + 1;
new->value = malloc(len * sizeof(char));
if (!new->value) {
free(new);
return false;
}
// copy the string into value in new element
memcpy(new->value, s, len);
// add the new node to the beginning of the list
list_add(&new->list, head);
return true;
}
```
### q_insert_tail
- Similar to `q_insert_head` but `list_add()` is replaced by `list_add_tail()` to add the new node to the end of the list.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
// return flase if queue if NULL
if (!head)
return false;
// allocate memory space for new queue element
// return false if allocate space failed
// initialize "list" in new element
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
INIT_LIST_HEAD(&new->list);
// allocate memory space for "value" in new element
// allocate one addtional character of memory space for '\0'
// return false if allocate space failed
size_t len = strlen(s) + 1;
new->value = malloc(len * sizeof(char));
if (!new->value) {
free(new);
return false;
}
// copy the string into value in new element
memcpy(new->value, s, len);
// add the new node to the end of the list
list_add_tail(&new->list, head);
return true;
}
```
### q_remove_head
- Find the target entry from the list and remove it from the list.
- Invoke `list_first_entry()` to get the first entry of the list.
- Invoke `list_del_init()` to remove the node from the list.
- Invoke `memcpy()` to copy the removed string into `sp`.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
// return NULL if queue is NULL or empty
if (!head || list_empty(head))
return NULL;
// get the first entry of the list
// and remove it from the list
element_t *target = list_first_entry(head, element_t, list);
list_del_init(&target->list);
// copy the removed string if sp is non-NULL
if (sp) {
// copy the removed string and plus a null terminator
memcpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return target;
}
```
### q_remove_tail
- Similat to `q_insert_head` but `list_first_entry()` is replaced by `list_last_entry()` to get the last entry of the list.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
// return NULL if queue if NULL or empty
if (!head || list_empty(head))
return NULL;
// get the last entry of the list
// and remove it from the list
element_t *target = list_last_entry(head, element_t, list);
list_del(head->prev);
// copy the removed string if sp is non-NULL
if (sp) {
// copy the removed string and plus a null terminator
memcpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return target;
}
```
### q_size
- Invoke `list_for_each()` to iterate over list nodes.
```c
int q_size(struct list_head *head)
{
// return 0 if queue is NULL or empty
if (!head || list_empty(head))
return 0;
int size = 0;
// iterate over list nodes and count the number of nodes
struct list_head *tmp;
list_for_each (tmp, head)
size++;
return size;
}
```
### q_delete_mid
- Iterate from both directions with two iterater to find the middle node.
- Invoke `list_entry()` to get the entry of the middle node.
- Invoke `list_del_init()` to remove the middle from list.
- Invoke `q_release_element()` to free the node.
```c
bool q_delete_mid(struct list_head *head)
{
// return false if queue is NULL or empty
if (!head || list_empty(head))
return false;
// find the middle node
struct list_head *l = head->next, *r = head->prev;
while (l != r && l->next != r) {
l = l->next;
r = r->prev;
}
// delete the middle node in list
element_t *mid = list_entry(r, element_t, list);
list_del_init(&mid->list);
q_release_element(mid);
return true;
}
```
### q_delete_dup
- Invoke `list_for_each_entry_safe()` to iterate over list entries because it allow deletes.
- Use `flg` to represent whether the current node needs to be deleted or not.
- If the value of current node is same as the value of next node, delete current node and set the `flg` to true.
```c
bool q_delete_dup(struct list_head *head)
{
// return false if queue is NULL
if (!head)
return false;
// return true without checking if queue is empty or singular
// if (list_empty(head) || list_is_singular(head))
// return true;
bool flg = false;
element_t *cur = NULL, *nxt = NULL;
list_for_each_entry_safe (cur, nxt, head, list) {
if ((cur->list.next != head) &&
(strcmp(cur->value,
list_entry(cur->list.next, element_t, list)->value) == 0)) {
list_del(&cur->list);
q_release_element(cur);
flg = true;
} else if (flg) {
list_del(&cur->list);
q_release_element(cur);
flg = false;
}
}
return true;
}
```
### q_swap
- Do nothing if queue if NULL or empty or singular.
- Use two `list_head *` `a` and `b` to implement `swap(a, b)`.
```c=
void q_swap(struct list_head *head)
{
// do nothing if queue is NULL or empty or singular
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *a = head->next;
// check if there are still unprocessed nodes
// and more than one node has not been processed
while (a != head && a->next != head) {
// implement swap (a, b) to swap (a, b) to (b, a)
struct list_head *b = a->next;
a->next = b->next;
b->prev = a->prev;
a->prev->next = b;
b->next->prev = a;
a->prev = b;
b->next = a;
a = a->next;
}
}
```
::: spoiler Explain with diagram
- The original state.
```graphviz
digraph swap_node {
rankdir=LR
hd
n0
n1
n2
n3
hd -> n0 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 0 : line 12
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n0 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 1 : line 13
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n0 [label = "next"]
n0 -> n2 [label = "next" color = red]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 2 : line 14
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n0 [label = "next"]
n0 -> n2 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n1 [label = "prev"]
n1 -> hd [label = "prev" color = red]
n0 -> hd [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 3 : line 15
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n1 [label = "next" color = red]
n0 -> n2 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n1 [label = "prev"]
n1 -> hd [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 4 : line 16
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n1 [label = "next"]
n0 -> n2 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n0 [label = "prev" color = red]
n1 -> hd [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 5 : line 17
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n1 [label = "next"]
n0 -> n2 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n0 [label = "prev"]
n1 -> hd [label = "prev"]
n0 -> n1 [label = "prev" color = red]
hd -> n3 [label = "prev"]
}
```
- Step 6 : line 18
```graphviz
digraph swap_node {
rankdir=LR
hd
n0 [label = a color = blue]
n1 [label = b color = green]
n2
n3
hd -> n1 [label = "next"]
n0 -> n2 [label = "next"]
n1 -> n0 [label = "next" color = red]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n0 [label = "prev"]
n1 -> hd [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n3 [label = "prev"]
}
```
- Step 7 : line 19
```graphviz
digraph swap_node {
rankdir=LR
hd
n0
n1
n2 [label = a color = blue]
n3 [label = b color = green]
hd -> n1 [label = "next"]
n0 -> n2 [label = "next"]
n1 -> n0 [label = "next"]
n2 -> n3 [label = "next"]
n3 -> hd [label = "next"]
n3 -> n2 [label = "prev"]
n2 -> n0 [label = "prev"]
n1 -> hd [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n3 [label = "prev"]
}
```
:::
### q_reverse
```c=
void q_reverse(struct list_head *head)
{
// do nothing if queue is NULL or empty
if (!head || list_empty(head))
return;
struct list_head *cur = head;
// save the original next node of current node first
// then make the original prev node into the new next node
// and make the origin next node into the new prev node
// iterate after done, process all node the same
do {
struct list_head *nxt = cur->next;
cur->next = cur->prev;
cur->prev = nxt;
cur = nxt;
} while (cur != head);
}
```
::: spoiler Explain with diagrams
- The original state.
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0
n1
n2
hd -> n0 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n2 [label = "prev"]
}
```
- Step 0 : line 14
```graphviz
digraph reverse_node {
rankdir=LR
hd [label = "cur" color = blue]
n0 [label = "nxt" color = green]
n1
n2
hd -> n0 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n2 [label = "prev"]
}
```
- Step 1 : 15
```graphviz
digraph reverse_node {
rankdir=LR
hd [label = "cur" color = blue]
n0 [label = "nxt" color = green]
n1
n2
hd -> n2 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n2 [label = "prev"]
}
```
- Step 2 : line 16
```graphviz
digraph reverse_node {
rankdir=LR
hd [label = "cur" color = blue]
n0 [label = "nxt" color = green]
n1
n2
hd -> n2 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n0 [label = "prev"]
}
```
- Step 3 : line 17
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0 [label = "cur" color = blue]
n1 [label = "nxt" color = green]
n2
hd -> n2 [label = "next"]
n0 -> n1 [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n0 [label = "prev"]
}
```
- Repeat the step 1 to step 3
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0 [label = "cur" color = blue]
n1 [label = "nxt" color = green]
n2
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> hd [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0 [label = "cur" color = blue]
n1 [label = "nxt" color = green]
n2
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0
n1 [label = "cur" color = blue]
n2 [label = "nxt" color = green]
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n2 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0
n1 [label = "cur" color = blue]
n2 [label = "nxt" color = green]
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n0 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0
n1 [label = "cur" color = blue]
n2 [label = "nxt" color = green]
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n2 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd [label = "nxt" color = green]
n0
n1
n2 [label = "cur" color = blue]
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> hd [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n2 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd [label = "nxt" color = green]
n0
n1
n2 [label = "cur" color = blue]
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> n1 [label = "next"]
n2 -> n1 [label = "prev"]
n1 -> n2 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
```graphviz
digraph reverse_node {
rankdir=LR
hd [label = "nxt" color = green]
n0
n1
n2 [label = "cur" color = blue]
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> n1 [label = "next"]
n2 -> hd [label = "prev"]
n1 -> n2 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
- The complete state.
```graphviz
digraph reverse_node {
rankdir=LR
hd
n0
n1
n2
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> n1 [label = "next"]
n2 -> hd [label = "prev"]
n1 -> n2 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
- Equal to:
```graphviz
digraph reverse_node {
rankdir=LR
hd
n2
n1
n0
hd -> n2 [label = "next"]
n0 -> hd [label = "next"]
n1 -> n0 [label = "next"]
n2 -> n1 [label = "next"]
n2 -> hd [label = "prev"]
n1 -> n2 [label = "prev"]
n0 -> n1 [label = "prev"]
hd -> n0 [label = "prev"]
}
```
:::
### q_sort
- Sort the list with merge sort.
- The `merge` function refer to [Leetcode NO.23 Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/).
- Merge the sorted lists in an iterative way to prevent excessive function call in a recursive way lead to stack overflow.
- Refer to [linux: lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) to improve the `merge` function.
```c
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
if (!l1)
return l2;
if (!l2)
return l1;
struct list_head *res = NULL, **cur = &res;
while (l1 && l2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) > 0) {
*cur = l2;
cur = &l2->next;
l2 = l2->next;
} else {
*cur = l1;
cur = &l1->next;
l1 = l1->next;
}
}
if (l1)
*cur = l1;
if (l2)
*cur = l2;
return res;
}
```
- The `mergeSort` function refer to [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/).
```c
struct list_head *mergeSort(struct list_head *l)
{
if (!l || !l->next)
return l;
// split the list
struct list_head *fst = l->next, *slw = l;
while (fst && fst->next) {
slw = slw->next;
fst = fst->next->next;
}
fst = slw->next;
slw->next = NULL;
return merge(mergeSort(l), mergeSort(fst));
}
```
- Refer to [linux: lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) to treat the list as singly linked list.
```c
void q_sort(struct list_head *head)
{
// do nothing if queue is NULL or empty or singular
if (!head || list_empty(head) || list_is_singular(head))
return;
// treat the list as a singly linked list
head->prev->next = NULL;
// sort the list with merge sort
head->next = mergeSort(head->next);
// recover the list as doubly linked list
struct list_head *cur = head;
while (cur->next != NULL) {
cur->next->prev = cur;
cur = cur->next;
}
head->prev = cur;
cur->next = head;
}
```
### q_shuffle
- Refer to [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) to implement `do_shuffle` in `q_test.c`.
- Pseudo code.
```
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
- C code
```c
// https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
static bool do_shuffle()
{
if (!l_meta.l)
report(3, "Warning: Calling shuffle on null queue");
error_check();
int i = l_meta.size;
// for i from n - 1 downto 1
for(struct list_head *ptr1 = l_meta.l->prev; i > 0; i--, ptr1 = ptr1->prev) {
struct list_head *ptr2 = l_meta.l->next;
// j random integer such that 0 <= j <= i
for (int j = rand() % i; j > 0; j--, ptr2 = ptr2->next);
// exchange a[i] and a[j]
element_t *ele1 = list_entry(ptr1, element_t, list),
*ele2 = list_entry(ptr2, element_t, list);
char *tmp = ele1->value;
ele1->value = ele2->value;
ele2->value = tmp;
}
show_queue(3);
return !error_check();
}
```
- Add the command in `console_init()`.
```c
ADD_COMMAND(
shuffle, " | Shuffle all nodes in queue");
```
## Improve the Code Progress Records
### Problems to be solved
- Failed the last test.
```shell
+++ TESTING trace trace-17-complexity:
--- trace-17-complexity 0/5
--- TOTAL 95/100
```
- But the code works on the local side, so it means `q_insert_head`, `q_insert_tail`, `q_remove_head`, or `q_remove_tail` are not stable.
- Profile the `q_test` with valgrind.
```shell
make && valgrind ./qtest < traces/trace-17-complexity.cmd
```
:::spoiler Result
```shell
make: Nothing to be done for 'all'.
Probably constant time
ERROR: Probably not constant time
Probably constant time
Probably constant time
==4162== 32 bytes in 1 blocks are still reachable in loss record 1 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DB69: init_cmd (console.c:408)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 2 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DB83: init_cmd (console.c:409)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 3 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DB9D: init_cmd (console.c:410)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 4 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DBB7: init_cmd (console.c:411)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 5 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DBD1: init_cmd (console.c:412)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 6 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DBEB: init_cmd (console.c:413)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 7 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10DC05: init_cmd (console.c:414)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 8 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C4DF: console_init (qtest.c:767)
==4162== by 0x10C4DF: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 9 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C4F9: console_init (qtest.c:768)
==4162== by 0x10C4F9: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 10 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C513: console_init (qtest.c:769)
==4162== by 0x10C513: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 11 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C52D: console_init (qtest.c:773)
==4162== by 0x10C52D: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 12 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C547: console_init (qtest.c:777)
==4162== by 0x10C547: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 13 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C561: console_init (qtest.c:781)
==4162== by 0x10C561: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 14 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C57B: console_init (qtest.c:785)
==4162== by 0x10C57B: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 15 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C595: console_init (qtest.c:788)
==4162== by 0x10C595: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 16 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C5AF: console_init (qtest.c:789)
==4162== by 0x10C5AF: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 17 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C5C9: console_init (qtest.c:790)
==4162== by 0x10C5C9: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 18 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C5E3: console_init (qtest.c:792)
==4162== by 0x10C5E3: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 19 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C5FD: console_init (qtest.c:793)
==4162== by 0x10C5FD: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 20 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C617: console_init (qtest.c:794)
==4162== by 0x10C617: main (qtest.c:945)
==4162==
==4162== 32 bytes in 1 blocks are still reachable in loss record 21 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D7DF: add_cmd (console.c:89)
==4162== by 0x10C631: console_init (qtest.c:796)
==4162== by 0x10C631: main (qtest.c:945)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 22 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10DC24: init_cmd (console.c:415)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 23 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10DC43: init_cmd (console.c:416)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 24 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10DC62: init_cmd (console.c:417)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 25 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10DC81: init_cmd (console.c:418)
==4162== by 0x10C4C5: main (qtest.c:944)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 26 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10C650: console_init (qtest.c:798)
==4162== by 0x10C650: main (qtest.c:945)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 27 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10C66F: console_init (qtest.c:800)
==4162== by 0x10C66F: main (qtest.c:945)
==4162==
==4162== 40 bytes in 1 blocks are still reachable in loss record 28 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D859: add_param (console.c:110)
==4162== by 0x10C68E: console_init (qtest.c:802)
==4162== by 0x10C68E: main (qtest.c:945)
==4162==
==4162== 52 bytes in 6 blocks are still reachable in loss record 29 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x4A4B50E: strdup (strdup.c:42)
==4162== by 0x110875: linenoiseHistoryAdd (linenoise.c:1236)
==4162== by 0x10E1CF: run_console (console.c:650)
==4162== by 0x10C6E0: main (qtest.c:962)
==4162==
==4162== 104 bytes in 1 blocks are still reachable in loss record 30 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x4A4B50E: strdup (strdup.c:42)
==4162== by 0x110901: linenoiseHistoryAdd (linenoise.c:1236)
==4162== by 0x10E1CF: run_console (console.c:650)
==4162== by 0x10C6E0: main (qtest.c:962)
==4162==
==4162== 160 bytes in 1 blocks are still reachable in loss record 31 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x1108C1: linenoiseHistoryAdd (linenoise.c:1224)
==4162== by 0x10E1CF: run_console (console.c:650)
==4162== by 0x10C6E0: main (qtest.c:962)
==4162==
==4162== 8,216 bytes in 1 blocks are still reachable in loss record 32 of 32
==4162== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162== by 0x10CD55: malloc_or_fail (report.c:189)
==4162== by 0x10D3D8: push_file (console.c:439)
==4162== by 0x10E19B: run_console (console.c:641)
==4162== by 0x10C6E0: main (qtest.c:962)
==4162==
```
:::
- It is found that `q_insert_head()` has a problem after reading the test data.
- After a few days of trying, it still get the same error. It is found that the test script may also call `q_sort` a lot, so try to improve the efficiency of `q_sort`.
- Replace `memcpy()` with `strncpy()` in `q_remove_head()` and `q_remove_tail()`.
- Finally, the code pass the automatic test. [link](https://github.com/oucs638/lab0-c/runs/5345047461?check_suite_focus=true)
```shell
+++ TESTING trace trace-17-complexity:
--- trace-17-complexity 5/5
--- TOTAL 100/100
▍▃
▍▃▅
▊╷▘▝ ▂▀▆▍╌▘
╹╷▔▖ ▃▅╷╷▁▗▘ ▁▁
▝▖│▝▀▅▆▆▅▅▆▆▅╷▁▂▀ ▁▂▃▀▅▀▔▃▔▗
▍▝▆╷╷╷╷╷╷╷╷╷▝▍ ▂▃▅▆▅╷╷╷╷╷╷╷╷▗
▕┢╷╷╷╷╷╷╷╷▂▂▁▋▝ ▋▔▃▃▃▃▃▃▃▃▃▃▂▂▁▘
▏▗▖▃▅╷╸╷┫┗▘▋▁╷▃▀▆▔╋▍╷╷╷╷╷╷╷╷╷╷▗
▆▅▀▃▎▝▃▘╷▁▂▂▂▖╷▗▔▃▋╷╷╷▗▘╷▂▂▃▀▀▅▅▆▆
▝▖╷╷╷▌▗▖▝▝▗▅▃▃▎╷▝▀▀▘╷╷▗▖╷╷▎
▅▂╷▝▅▘╷╷▝▂▂▗┋╷▀┏▅╷▗▘▁▋╷╷▎
▆▀▂▖▔╷▝╷━▅━╷╷╷▗▃▌▔╊▂▂▃▘
▅▖▁▏╷╷╷╷╷╷╷╷╷╷▝▅▝▀▀▖
▊▆╿▔╷▆╷╷╷╷╷╷╷╷╷╷╷▌▘╷▊
▖╷╷╷╷╷╷╷╷╷╷╷╷╷╷╷▝╺▔
▝▃╷▀▀▃▃▂▁─╷╷╷╷╷╷▋▋
▆▅▀▀▃▂▁▅▃▁╷╷▁▂▘
▆▅▀▖━▌
▃▊
```
- However, when I profiled the code with Valgrind, the last test still had some problems.
:::spoiler Result
```shell
make && valgrind ./qtest < traces/trace-17-complexity.cmd
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
Probably constant time
Probably constant time
Probably constant time
Probably constant time
Freeing queue
==17905== 156 bytes in 7 blocks are still reachable in loss record 1 of 3
==17905== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17905== by 0x4A4B50E: strdup (strdup.c:42)
==17905== by 0x110850: linenoiseHistoryAdd (linenoise.c:1236)
==17905== by 0x10E1CF: run_console (console.c:650)
==17905== by 0x10C6E0: main (qtest.c:962)
==17905==
==17905== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==17905== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17905== by 0x11089C: linenoiseHistoryAdd (linenoise.c:1224)
==17905== by 0x11146F: linenoiseHistoryLoad (linenoise.c:1325)
==17905== by 0x10C6B0: main (qtest.c:951)
==17905==
==17905== 528 bytes in 13 blocks are still reachable in loss record 3 of 3
==17905== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17905== by 0x4A4B50E: strdup (strdup.c:42)
==17905== by 0x110850: linenoiseHistoryAdd (linenoise.c:1236)
==17905== by 0x11146F: linenoiseHistoryLoad (linenoise.c:1325)
==17905== by 0x10C6B0: main (qtest.c:951)
==17905==
```
:::
### Fixed the memory error generated during the excution of `q_test()`
- After `q_test()` is excuted, the memory allocated by `linenoiseHistoryAdd()` or `linenoiseHistoryLoad()` is not properly released.
```shell
$ make && valgrind ./qtest < traces/trace-01-ops.cmd
make: Nothing to be done for 'all'.
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
==7332== 131 bytes in 11 blocks are still reachable in loss record 1 of 3
==7332== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7332== by 0x4A4B50E: strdup (strdup.c:42)
==7332== by 0x110913: linenoiseHistoryAdd (linenoise.c:1236)
==7332== by 0x10E292: run_console (console.c:650)
==7332== by 0x10C7A3: main (qtest.c:987)
==7332==
==7332== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==7332== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7332== by 0x11095F: linenoiseHistoryAdd (linenoise.c:1224)
==7332== by 0x111532: linenoiseHistoryLoad (linenoise.c:1325)
==7332== by 0x10C773: main (qtest.c:976)
==7332==
==7332== 179 bytes in 9 blocks are still reachable in loss record 3 of 3
==7332== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7332== by 0x4A4B50E: strdup (strdup.c:42)
==7332== by 0x110913: linenoiseHistoryAdd (linenoise.c:1236)
==7332== by 0x111532: linenoiseHistoryLoad (linenoise.c:1325)
==7332== by 0x10C773: main (qtest.c:976)
==7332==
```
- The function `linenoiseHistoryAdd()` will called by `run_console()` and `linenoiseHistoryLoad()`.
- In `linenoiseHistoryAdd()`, the program will allocate memory for a global variable `static char **history = NULL`.
```c
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
if (history_max_len == 0)
return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len);
...
}
```
- And there is a funtion named `freeHistory()` will called by `linenoiseAtExit()`.
- The function `linenoiseAtExit()` may be registered by `enableRawMode()`.
- The function `enableRawMode()` may be called by `linenoiseRaw()`.
- The function `linenoiseRaw()` may be called by `linenoise()`.
- The only place where it is possible to call `linenoise()` is `run_console()`.
```c
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
...
}
```
- If `has_infile` is `true`, `run_console()` will not call `linenoise()`, so `linenoiseAtExit()` will not be registered.
- Try to add function to register `linenoiseAtExit()` if `has_infile` is true. Since the global variable `atexit_registered` can not be used out of `linenoise.c`, so it need to create a new function.
```c
void addHistoryFree()
{
if (!atexit_registered) {
atexit(linenoiseAtExit);
atexit_registered = 1;
}
}
```
- Try to add the new function.
```c
bool run_console(char *infile_name)
{
...
if (!has_infile) {
...
} else {
addHistoreyFree();
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
...
}
```
- But it failed. Then I found there may also be cases in `linenoise()` with out registering `linenoiseAtExit()`.
- So I try to call `addHistoryFree()` whether `has_infile` is true or not.
```c
bool run_console(char *infile_name)
{
...
addHistoryFree();
if (!has_infile) {
...
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
...
}
```
- And it work, after `q_test` is excuted, there has no error message.
```shell
$ make && valgrind ./qtest < traces/trace-01-ops.cmd
CC console.o
CC linenoise.o
LD qtest
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
```
- But there will still be an error at the end of the last test.
:::spoiler Last Test
```shell
make && valgrind ./qtest < traces/trace-17-complexity.cmd
make: Nothing to be done for 'all'.
Probably constant time
Probably constant time
Probably constant time
Probably constant time
==11358== 32 bytes in 1 blocks are still reachable in loss record 1 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DC2C: init_cmd (console.c:408)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 2 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DC46: init_cmd (console.c:409)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 3 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DC60: init_cmd (console.c:410)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 4 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DC7A: init_cmd (console.c:411)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 5 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DC94: init_cmd (console.c:412)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 6 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DCAE: init_cmd (console.c:413)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 7 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10DCC8: init_cmd (console.c:414)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 8 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C588: console_init (qtest.c:791)
==11358== by 0x10C588: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 9 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C5A2: console_init (qtest.c:792)
==11358== by 0x10C5A2: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 10 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C5BC: console_init (qtest.c:793)
==11358== by 0x10C5BC: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 11 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C5D6: console_init (qtest.c:797)
==11358== by 0x10C5D6: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 12 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C5F0: console_init (qtest.c:801)
==11358== by 0x10C5F0: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 13 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C60A: console_init (qtest.c:805)
==11358== by 0x10C60A: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 14 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C624: console_init (qtest.c:809)
==11358== by 0x10C624: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 15 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C63E: console_init (qtest.c:812)
==11358== by 0x10C63E: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 16 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C658: console_init (qtest.c:813)
==11358== by 0x10C658: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 17 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C672: console_init (qtest.c:814)
==11358== by 0x10C672: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 18 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C68C: console_init (qtest.c:816)
==11358== by 0x10C68C: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 19 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C6A6: console_init (qtest.c:817)
==11358== by 0x10C6A6: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 20 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C6C0: console_init (qtest.c:818)
==11358== by 0x10C6C0: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 21 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C6DA: console_init (qtest.c:820)
==11358== by 0x10C6DA: main (qtest.c:970)
==11358==
==11358== 32 bytes in 1 blocks are still reachable in loss record 22 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D8A2: add_cmd (console.c:89)
==11358== by 0x10C6F4: console_init (qtest.c:822)
==11358== by 0x10C6F4: main (qtest.c:970)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 23 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10DCE7: init_cmd (console.c:415)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 24 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10DD06: init_cmd (console.c:416)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 25 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10DD25: init_cmd (console.c:417)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 26 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10DD44: init_cmd (console.c:418)
==11358== by 0x10C56E: main (qtest.c:969)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 27 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10C713: console_init (qtest.c:824)
==11358== by 0x10C713: main (qtest.c:970)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 28 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10C732: console_init (qtest.c:826)
==11358== by 0x10C732: main (qtest.c:970)
==11358==
==11358== 40 bytes in 1 blocks are still reachable in loss record 29 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D91C: add_param (console.c:110)
==11358== by 0x10C751: console_init (qtest.c:828)
==11358== by 0x10C751: main (qtest.c:970)
==11358==
==11358== 8,216 bytes in 1 blocks are still reachable in loss record 30 of 30
==11358== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358== by 0x10CE18: malloc_or_fail (report.c:189)
==11358== by 0x10D49B: push_file (console.c:439)
==11358== by 0x10E25E: run_console (console.c:641)
==11358== by 0x10C7A3: main (qtest.c:987)
==11358==
```
:::
- After tracing the code, it found that in `init_cmd()` will allocate memory space for `cmd_list`.
- There is a function named `finish_cmd()` that will call `do_quit()` to free the momory of `cmd_list()`.
- Refer to [AmyLin](https://hackmd.io/@AmyLin0210/rJpekw9kc)'s note, the `main` function of `q_test` may not call the `finish_cmd()` if the `ok` is false.
- So modify a line in `main` of `q_test`.
```c
# replace this line
ok = ok && finish_cmd();
# with
ok = finish_cmd() && ok;
```
Sign in with Wallet
Connect another wallet