2018q3 Homework2 (lab0)

# 2018q3 Homework2 (lab0) contributed by < `TsundereChen` > ###### tags: `sysprog` `TsundereChen` >* Please list your environment >* Pull the latest from the original repo also > >[name=TA][color=red] > * [GitHub Repo](https://github.com/TsundereChen/lab0-c) ## console.c & console.h ## harness.c & harness.h * In harness.h, we can notice that this program uses it's own malloc and free, which is defined at the bottom of the file, and the malloc is correspond to `test_malloc`, free is correspond to `test_free` * These two files are being used to check if there exists common allocation errors * In the beginning of harness.c, there are some values that are being used to check block status, here, block means the memory allocated by malloc * This program uses doubly-linked list to represent allocated blocks * In harness.c, there's a interesting function called `fail_allocation`, which looks like this ```clike static bool fail_allocation() { double weight = (double) random() / RAND_MAX; return (weight / 0.01 * fail_probability); } ``` :::info Would this code fail ? If so, why ? ::: * At line 58 of harness.c, the code is `static jmp_buf env;`, here, there's a keyword called "**jmp_buf**" * * At line 59 of harness.c, the code is `static volatile sig_atomic_t jmp_ready = false;`, here, there's a keyword called "**volatile**" * **Keyword "volatile"** * This keyword indicates that a value may change between different accesses, even if it does not appear to be modified. * Prevert compiler from optimizing this variable * Use case: * Allow access to memory-mapped I/O devices * Allow uses of variables between **setjmp** and **longjmp** * Allow uses of ***sig_atomic_t*** variables in signal handlers * **Atomic Operation** * Atomic Operation is a function provided by kernel to do synchronization, this operation is useful when the data you're trying to protect is simple * **sig_atomic_t** * An integer type which can be accessed as an atomic entity even in the presence of asynchronous interrupts made by signals :::info Need further explaination ::: ## qtest.c & qtest.h ## queue.c & queue.h ### struct queue_t * This is the struct of queue_t * Because `head` is not enough for us to create functions in `queue.c`, to trace queue easier, I added `tail` * And due to the requirement of O(1) time in `q_size` function, I added `int size` to queue_t ```clike typedef struct { /* Linked list of elements You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail */ list_ele_t *head; list_ele_t *tail; int size; } queue_t; ``` ### q_new * `q_new` is a function to create empty queue, and return NULL if malloc failed * I add an `if` statement here, to check if `malloc` succeed, and because I added `tail` and `size` to queue_t, so I also initialized these values. ```clike queue_t *q_new() { /* What if malloc returned NULL? */ queue_t *q = malloc(sizeof(queue_t)); if(q == NULL) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` ### q_free * Not only should you free `list_ele_t`, but you should also free `value` in every element * But, **Don't free anything if q is NULL or both q->head and q->tail are pointed to NULL** ```clike void q_free(queue_t *q) { if (q != NULL) { /* How about freeing the list elements and the strings? */ /* Free queue structure */ while (q->head != q->tail) { list_ele_t *del_t = q->head; free(q->head->value); q->head = q->head->next; free(del_t); } if (q->head != NULL || q->tail != NULL) { free(q->tail->value); free(q->tail); } free(q); } } ``` ### q_insert_head * `q_insert_head` is a function that insert a new `list_ele_t` to the head of the queue * It seems simple, but need to remember what to do if the element you are adding into the queue is **the first element you add into the queue** * And need to be careful about `strcpy`, I choose to use `strncpy`, and add one more char byte to the destination array, to try to avoid buffer overflow ```clike bool q_insert_head(queue_t *q, char *s) { /* What should you do if the q is NULL? */ /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ if(q == NULL) return false; list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); newh->value = malloc(sizeof(char) * (strlen(s) + 1)); if(newh == NULL || newh->value == NULL) return false; strncpy(newh->value, s, strlen(s) + 1); newh->next = q->head; q->head = newh; if(q->tail == NULL) q->tail = newh; q->size = q->size + 1; return true; } ``` ### q_insert_tail * This function created a new list_ele_t object, and link it to the tail of the linked list. * Both this object and it's value is created using malloc * I forgot to point the linked list's tail to the new object, which can cause bugs ```clike bool q_insert_tail(queue_t *q, char *s) { if (q == NULL) return false; list_ele_t *newt; newt = malloc(sizeof(list_ele_t)); if (newt == NULL) return false; newt->value = malloc(sizeof(char) * (strlen(s) + 1)); if (newt->value == NULL) { free(newt); return false; } strncpy(newt->value, s, strlen(s) + 1); newt->next = NULL; q->tail->next = newt; q->tail = newt; if (q->head == NULL) q->head = newt; q->size = q->size + 1; return true; } ``` ### q_remove_head * This function acts like 'pop', it removes the head of the queue * Need to notice what would happe if queue's size is zero after the removal * There's a function called `do_remove_head_quiet` in qtest.c, and it call q_remove_head in this format `"q_remove_head(q, NULL, 0)"` * So due to this function, need to detect if `sp` is pointed to NULL, and if it's pointed to NULL, don't copy the string, just remove the head. ```clike bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (q == NULL || q->size == 0) return false; if (sp == NULL && bufsize == 0) { /* This is do_remove_head_quiet in qtest.c */ list_ele_t *delh = q->head; q->size = q->size - 1; if (q->size == 0) { q->head = NULL; q->tail = NULL; } else { q->head = q->head->next; } free(delh->value); free(delh); return true; } else { char buf_str[bufsize]; memset(buf_str, '\0', bufsize); memset(sp, '\0', bufsize); strncpy(buf_str, q->head->value, bufsize - 1); strncpy(sp, buf_str, bufsize); list_ele_t *delh = q->head; q->size = q->size - 1; if (q->size == 0) { q->head = NULL; q->tail = NULL; } else { q->head = q->head->next; } free(delh->value); free(delh); return true; } } ``` ### q_size * By adding a value `size` in queue_t, we can get the size of the queue just by accessing q->size * But if q is NULL, return 0 ```clike int q_size(queue_t *q) { if (q != NULL) return q->size; else return 0; } ``` ### q_reverse * At first, I tried to do reverse by tracking from q->head to q->tail's previous object, and I can point the object's ->next->next, which is tail's next, to the object itself, and step back one by one * This method worked, but it takes too much time, it think the time complexity is O(n^2) * This method can't pass `make test`, so a better solution is needed * I found this page online [Linked List: 新增資料、刪除資料、反轉](http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html) * By using the method provided in the page, the time complexity changes to O(n), and passed the test. ```clike void q_reverse(queue_t *q) { if (q == NULL || q->size < 2) return; else { list_ele_t *tmph = q->head; list_ele_t *tmpt = q->tail; list_ele_t *previous = NULL; list_ele_t *current = q->head; list_ele_t *preceding = q->head->next; while (preceding != NULL) { current->next = previous; previous = current; current = preceding; preceding = preceding->next; } current->next = previous; q->head = tmpt; q->tail = tmph; return; } } ``` ## report.c & report.h ## Test Environment ```bash tsundere:~/ $ uname -a Linux Tsundere-X240s 4.18.10-zen1-1-zen #1 ZEN SMP PREEMPT Wed Sep 26 09:48:45 UTC 2018 x86_64 GNU/Linux tsundere:~/ $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 69 Model name: Intel(R) Core(TM) i7-4500U CPU @ 1.80GHz Stepping: 1 CPU MHz: 910.648 CPU max MHz: 3000.0000 CPU min MHz: 800.0000 BogoMIPS: 4790.56 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 4096K NUMA node0 CPU(s): 0-3 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d tsundere:~/ $ hostnamectl Static hostname: Tsundere-X240s Icon name: computer-laptop Chassis: laptop Machine ID: 35c34f0e79b049048648088e195686e6 Boot ID: 8f1ca5b31e8a4965a3d3a30feee9ec0e Operating System: Arch Linux Kernel: Linux 4.18.10-zen1-1-zen Architecture: x86-64 ``` ## Resources * [C Programming Lab: Assessing Your C Programming Skills](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) * [CMU CS:15-122 Linked Lists](http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/10-linkedlist.pdf) * [CMU CS:15-122 Sorting Arrays](http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/05-sort.pdf)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.