owned this note
owned this note
Published
Linked with GitHub
# 2021q1 Homework1 (lab0)
contributed by < `ilkclord` >
## Schedule
* [x] struct of queue
* [x] q_new
* [x] q_free
* [x] q_insert_head
* [x] q_insert_tail
* [x] q_remove_head
* [x] q_size
* [x] q_reverse
* [x] q_sort
* [x] console.h
* [x] qtest_debugging
* [ ] qtest-completing
## Development Detail
### queue.h
* **q_struct**
* ***head** the start of the linked list
* ***tail** use to make $O(1)$ time in insert_tail
```clike=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
* **q_new**
* create a new queue
* initialize the queue
``` clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return q;
q->head = NULL;
q->tail = q->head;
q->size = 0;
return q;
}
```
* **q_free**
* ***tmp** use for rember the address of next node
* free the string first then free the node
```clike=
void q_free(queue_t *q)
{
if (q != NULL) {
while (q->head != NULL) {
list_ele_t *tmp = q->head->next;
free(q->head->value);
free(q->head);
q->head = tmp;
}
free(q);
}
}
```
* **q_insert_head**
* Three checking gate to prevent acting on NULL ,empty and lack of memory
* Contents a special case for the inserting when th queue is empty
```clike=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
free(newh);
return false;
}
char *tmp = malloc(strlen(s) + 1);
if (tmp == NULL) {
free(tmp);
free(newh);
return false;
}
strncpy(tmp, s, strlen(s));
tmp[strlen(s)] = '\0';
if (q->head == NULL) // special case
q->tail = newh;
newh->value = tmp;
newh->next = q->head;
q->head = newh;
q->size = q->size + 1;
return true;
}
```
* **q_insert_tail**
* Three checking gate to prevent acting on NULL ,empty and lack of memory
* Contents a special case for the inserting when queue is empty
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (newt == NULL) {
free(newt);
return false;
}
char *tmp = malloc(strlen(s) + 1);
if (tmp == NULL) {
free(tmp);
free(newt);
return false;
}
strncpy(tmp, s, strlen(s));
tmp[strlen(s)] = '\0';
newt->next = NULL;
newt->value = tmp;
if (q->tail == NULL) { // special case
q->tail = newt;
q->head = newt;
return true;
}
q->tail->next = newt;
q->tail = newt;
q->size = q->size + 1;
return true;
}
```
* **q_remove_head**
* A checking gate for NULL and empty queue
* A checking gate for NULL sp
* free the string first then the node
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL)
return false;
if (sp != NULL) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_ele_t *tmp = q->head->next;
free(q->head->value);
free(q->head);
q->head = tmp;
q->size = q->size - 1;
return true;
}
```
* **q_size**
* Operate in $O(1)$ time
* A checking gate for NULL and empty queue
```clike=
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL)
return 0;
return q->size;
}
```
* **q_reverse**
* First check if the queue has at least 2 elements
* Change the direction between each elements
* Break the loop if reach the end (NULL)
```clike=
void q_reverse(queue_t *q)
{
if (q != NULL && q->head != NULL && q->head->next != NULL) {
q->tail = q->head;
list_ele_t *tmp = q->head->next;
list_ele_t *tmp2 = NULL;
q->head->next = NULL;
while (tmp != NULL) {
tmp2 = tmp->next;
tmp->next = q->head;
q->head = tmp;
tmp = tmp2;
}
}
}
```
* **q_sort**
* Add three function to complete the Task
```clike=
void q_sort(queue_t *q)
{
if (q == NULL || q->head == NULL || q->head->next == NULL)
return;
q->head = merge_split(q->head, q->size);
q->tail = merge_find(q->size, q->head);
}
```
* **merge**
* The merging process
* **q1** and **q2** represents two linked list
* Can merge two linked list with diffrent size
* Return a **merged** linked list
* First if_else determine the head of **merged** linked list
```clike=
list_ele_t *merge(list_ele_t *q1, list_ele_t *q2)
{
list_ele_t *leads = NULL, *root;
if (strcmp(q1->value, q2->value) < 0) {
leads = q1;
q1 = q1->next;
} else {
leads = q2;
q2 = q2->next;
}
root = leads;
while (q1 != NULL && q2 != NULL) {
if (strcmp(q1->value, q2->value) < 0) {
leads->next = q1;
q1 = q1->next;
} else {
leads->next = q2;
q2 = q2->next;
}
leads = leads->next;
}
if (q1 == NULL)
leads->next = q2;
else
leads->next = q1;
return root;
}
```
* **merge_find**
* Find the node in specific position
```clike=
list_ele_t *merge_find(int a, list_ele_t *root)
{
while (a > 1) {
root = root->next;
a = a - 1;
}
return root;
}
```
* **merge_split**
* First split the linked list to two linkend list
* The tail points to the NULL
* Do the merge-sort to the two linked list
* Recursively , return root if it has only ine elements
* Finally merge the two linked list to one
* Return the **merged-sorted** linked list
```clike=
list_ele_t *merge_split(list_ele_t *root, int size)
{
if (size / 2 > 0) {
list_ele_t *tmp = merge_find(size / 2, root);
list_ele_t *q2 = tmp->next;
tmp->next = NULL;
root = merge_split(root, size / 2);
q2 = merge_split(q2, size - size / 2);
return merge(root, q2);
} else {
root->next = NULL;
return root;
}
}
```
## Some Error
When making the test score 100/100 , there are some condition that i didn't notice
* **NULL States**
In the function below , I called the data in the nodes but the nodes are NULL actually.
* **q_insert_head**
The first insertion needs to initialize the tail too , so a gate is added
```clike=
if (q->head == NULL) // special case
q->tail = newh;
```
* **q_insert_tail**
The first insertion will failed because the tail is NULL ,and can't be called , so the gate below is added.
```clike=
if (q->tail == NULL) { // special case
q->tail = newt;
q->head = newt;
return true;
}
```
* **q_sort**
When finished sorting ,because the return linked list were copy to head, but tail has to modified too.
```clike=
q->tail = merge_find(q->size, q->head);
```
## Error in qtest
### Variable echo
By the command
```
$ make clean
$ make SANITIZER=1
$ ./qtest
$ cmd>help
```
We get the error message below
```clike
==11584==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555e3e8143c0 at pc 0x555e3e7fd7bd bp 0x7ffce26b18b0 sp 0x7ffce26b18a0
READ of size 4 at 0x555e3e8143c0 thread T0
#0 0x555e3e7fd7bc in do_help_cmd /home/ilkclord/linux2020/lab0-c/console.c:307
#1 0x555e3e7fd8d0 in interpret_cmda /home/ilkclord/linux2020/lab0-c/console.c:221
#2 0x555e3e7fe0b5 in interpret_cmd /home/ilkclord/linux2020/lab0-c/console.c:244
#3 0x555e3e7ff7f8 in run_console /home/ilkclord/linux2020/lab0-c/console.c:660
#4 0x555e3e7fc3e5 in main /home/ilkclord/linux2020/lab0-c/qtest.c:780
#5 0x7fc192aea0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x555e3e7f9b8d in _start (/home/ilkclord/linux2020/lab0-c/qtest+0x8b8d)
0x555e3e8143c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x555e3e8143c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ilkclord/linux2020/lab0-c/console.c:307 in do_help_cmd
```
From the error message below we can figure out that
* The error occur in global variable **echo**
* It happend because reading size 4 in a size 1 memory
* The **echo** is a 1 byte variable
```clike
==11584==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555e3e8143c0 at pc 0x555e3e7fd7bd bp 0x7ffce26b18b0 sp 0x7ffce26b18a0
READ of size 4 at 0x555e3e8143c0 thread T0
```
```clike
0x555e3e8143c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x555e3e8143c0) of size 1
```
Find the definition of **echo** in console.c
```clike
static bool echo = 0;
```
Find out the line first error occured
```clike
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
```
We can know there are somthing wrong in 3 parameters , and they all belongs to **plist** which the type is **param_ptr**
```clike
param_ptr plist = param_list;
```
And the sturct of **param_ptr** can be find in console.h
```clike
typedef struct PELE param_ele, *param_ptr;
struct PELE {
char *name;
int *valp;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
Because the size of type **char** is 1 , the only possibe parameters which cause error is **int** ***valp**
TSo we find out that the **echo** is used to initialize **valp**
```clike
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
And **add_param()** add a new node with type **param_ptr**
```clike
// part of the function
param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
ele->name = name;
ele->valp = valp;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
```
Apparently **(int\*)&echo** is a invalid use ,because the size doesn't match (1 -> 4) .
To fix it ,we can just let the type of **echo** be **int** ,because there aren't any assinging true or false to **echo** action.
After applying the change , we fix it !
### Variable simulation
By the command
```clike
$ make clean
$ make SANITIZER=1
$ make test
```
We get the error message
```clike
==13139==ERROR: AddressSanitizer: global-buffer-overflow on address 0x564b115bb5e0 at pc 0x564b115a3ae8 bp 0x7ffe28ebd340 sp 0x7ffe28ebd330
READ of size 4 at 0x564b115bb5e0 thread T0
#0 0x564b115a3ae7 in do_option_cmd /home/ilkclord/linux2020/lab0-c/console.c:369
#1 0x564b115a28d0 in interpret_cmda /home/ilkclord/linux2020/lab0-c/console.c:221
#2 0x564b115a30b5 in interpret_cmd /home/ilkclord/linux2020/lab0-c/console.c:244
#3 0x564b115a42e1 in cmd_select /home/ilkclord/linux2020/lab0-c/console.c:594
#4 0x564b115a485b in run_console /home/ilkclord/linux2020/lab0-c/console.c:667
#5 0x564b115a13e5 in main /home/ilkclord/linux2020/lab0-c/qtest.c:780
#6 0x7f1b857f80b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#7 0x564b1159eb8d in _start (/home/ilkclord/linux2020/lab0-c/qtest+0x8b8d)
0x564b115bb5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x564b115bb5e0) of size 1
'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ilkclord/linux2020/lab0-c/console.c:369 in do_option_cmd
```
From the error message we find the similar information of **simulation** as **echo**
* The error occur in global variable **simulation**
* It happend because reading size 4 in a size 1 memory
* The **simulation** is a 1 byte variable
```clike
==13139==ERROR: AddressSanitizer: global-buffer-overflow on address 0x564b115bb5e0 at pc 0x564b115a3ae8 bp 0x7ffe28ebd340 sp 0x7ffe28ebd330
READ of size 4 at 0x564b115bb5e0 thread T0
```
```clike
0x564b115bb5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x564b115bb5e0) of size 1
'simulation' is ascii string ''
```
We cna find out where **simulation** is used
```clike
add_param("simulation",(int*)&simulation, "Start/Stop simulation mode", NULL);
```
And since the definition shows that **simulation** is **bool** type , it is a inavalid tranfer .
```clike=
bool simulation = false;
```
We fixed it by changing the declared type to int, but then the error occured
```clike
ilkclord~01:36:38>~/linux2020/lab0-c>$ make SANTILIZER=1
CC qtest.o
CC report.o
CC console.o
console.c:21:5: error: conflicting types for ‘simulation’
21 | int simulation = false;
| ^~~~~~~~~~
In file included from console.c:3:
console.h:11:13: note: previous declaration of ‘simulation’ was here
11 | extern bool simulation;
| ^~~~~~~~~~
make: *** [Makefile:50: console.o] Error 1
```
So we go to console.h ,and change the type **bool** to **int** , then we fixed it !
```clike
extern int simulation;
```
Google Drive
Gist
Clipboard
Sign in with Wallet
