2017q1 Homework4 (mergesort-concurrent)

# 2017q1 Homework4 (mergesort-concurrent) contributed by <`hugikun999`> ## mergesort-concurrent ### 支援 string 按照作業解說的步驟，在執行時卻產生了錯誤。 ```shell= hugikun@hugikun:~/embedded/mergesort-concurrent$ ./sort 4 8 Segmentation fault (core dumped) ``` 看了 `main.c`，第二個參數是要給**檔名**而非一個數字。改成給檔名之後雖然有結果，可是卻是一堆`0`，應該還有錯誤，繼續讀 `main.c`。會一直噴`0`的原因是在 `build_list_from_file` 中 `atol` 轉出來的東西是 `0`，所以代表根本沒有成功給到值。且因為我們想要存的是 `char`，`node` 裡面只提供存 `intptr_t` 所以要另外新增 member。 ```C list_add(_list, atol(buffer)); ``` 對 `node_t` 增加一個 `char *lastname` 以便儲存名字，另外新增 `list_addc` `node_addc` 兩個函式處理字串的新增。這邊的 mergetsort 是以數字進行比較，必須另外提供一個 `string to val_t` 以取得每個字串的代表大小。 ```C typedef struct node { #ifdef WORD char *lastname; #endif val_t data; /**< Data of the node */ struct node *next; /**< Pointer to the next node */ } node_t; ``` ```C tatic node_t *node_newc(char *lastname, node_t *next) { node_t *node = malloc(sizeof(node_t)); node->data = chartolint(lastname); node->lastname = lastname; node->next = next; return node; } int list_addc(llist_t * const list, char *lastname) { node_t *e= node_newc(lastname, NULL); e->next = list->head; list->head = e; list->size++; return list->size; } ``` ```C val_t chartolint(char *lastname) { val_t data = 0; for(int i = 0; i < MAX_NAME_SIZE; i++) { long int ctoli = (long int)lastname[i] - 96; if(lastname[i] != '\0' && lastname[i] != '\n') data += ctoli * pow(27, MAX_NAME_SIZE - i - 4); else break; } return data; } ``` 這邊遇到一個卡比較久的問題是我利用 buffer 讀取資料，之後將 buffer 直接賦值給 node 裡面的 lastname，問題是這樣做會將 lastname 指向 buffer 而非內容給予 lastname 值，所以剛開始我做出來的結果是所有 node 的 lastname 都一樣且一離開 `build_list_from_file` 就會印出奇怪的值。之後改用 `mmap` 的方式把每個 lastname 指到對應的位置。 ### pthread 在 task_run 的最後會讀到一個 func 為 NULL 的 task，這個時候就會跳出 while(1)，雖然有呼叫 `pthread_exit(NULL)` 卻沒有確保所有 thread 都跳出之後才繼續執行，因此多加上 `pthread_join`。 ```C /* Start when the first task launches. */ gettimeofday(&start, NULL); /* launch the first task */ tqueue_push(pool->queue, task_new(cut_local_list, the_list)); for(int i = 0; i < thread_count; i++) pthread_join(pool->threads[i], NULL); /* release thread pool */ consumed_tasks = tpool_free(pool); gettimeofday(&end, NULL); ``` ### memory leak 透過 valgrind 檢查記憶體是否有確實釋放 ```shell= ==9019== HEAP SUMMARY: ==9019== in use at exit: 8,399,382 bytes in 349,908 blocks ==9019== total heap usage: 1,049,727 allocs, 699,819 frees, 19,607,878 bytes allocated ==9019== ==9019== LEAK SUMMARY: ==9019== definitely lost: 16 bytes in 1 blocks ==9019== indirectly lost: 0 bytes in 0 blocks ==9019== possibly lost: 0 bytes in 0 blocks ==9019== still reachable: 8,399,366 bytes in 349,907 blocks ==9019== suppressed: 0 bytes in 0 blocks ==9019== Rerun with --leak-check=full to see details of leaked memory ==9019== ==9019== For counts of detected and suppressed errors, rerun with: -v ==9019== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ``` 重新檢查程式碼並補上釋放的動作，雖然用了 `list_free_nodes` 釋放了很多空間卻產生了錯誤@@ ```shell= ==8828== HEAP SUMMARY: ==8828== in use at exit: 1,806 bytes in 9 blocks ==8828== total heap usage: 1,049,727 allocs, 1,049,718 frees, 19,607,878 bytes allocated ==8828== ==8828== LEAK SUMMARY: ==8828== definitely lost: 40 bytes in 2 blocks ==8828== indirectly lost: 0 bytes in 0 blocks ==8828== possibly lost: 0 bytes in 0 blocks ==8828== still reachable: 1,766 bytes in 7 blocks ==8828== suppressed: 0 bytes in 0 blocks ==8828== Rerun with --leak-check=full to see details of leaked memory ==8828== ==8828== For counts of detected and suppressed errors, rerun with: -v ==8828== ERROR SUMMARY: 349899 errors from 1 contexts (suppressed: 0 from 0) ``` 修改過 `list_free_node` 之後成功消滅的error ```C void list_free_nodes(llist_t *list) { node_t *cur = list->head; while (cur) { list->head = list->head->next; free(cur); cur = list->head; } } ``` ```shell= ==12409== HEAP SUMMARY: ==12409== in use at exit: 1,630 bytes in 5 blocks ==12409== total heap usage: 1,049,727 allocs, 1,049,722 frees, 19,607,878 bytes allocated ==12409== ==12409== LEAK SUMMARY: ==12409== definitely lost: 16 bytes in 1 blocks ==12409== indirectly lost: 0 bytes in 0 blocks ==12409== possibly lost: 0 bytes in 0 blocks ==12409== still reachable: 1,614 bytes in 4 blocks ==12409== suppressed: 0 bytes in 0 blocks ==12409== Rerun with --leak-check=full to see details of leaked memory ==12409== ==12409== For counts of detected and suppressed errors, rerun with: -v ==12409== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ``` ```shell= ==6558== 1,182 bytes in 1 blocks are still reachable in loss record 5 of 5 ==6558== at 0x4C2FB55: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==6558== by 0x400BA25: _dl_new_object (dl-object.c:75) ==6558== by 0x400633C: _dl_map_object_from_fd (dl-load.c:1006) ==6558== by 0x4008A56: _dl_map_object (dl-load.c:2476) ==6558== by 0x40153A6: dl_open_worker (dl-open.c:237) ==6558== by 0x4010393: _dl_catch_error (dl-error.c:187) ==6558== by 0x4014BD8: _dl_open (dl-open.c:660) ==6558== by 0x54A29BC: do_dlopen (dl-libc.c:87) ==6558== by 0x4010393: _dl_catch_error (dl-error.c:187) ==6558== by 0x54A2A73: dlerror_run (dl-libc.c:46) ==6558== by 0x54A2A73: __libc_dlopen_mode (dl-libc.c:163) ==6558== by 0x515491A: pthread_cancel_init (unwind-forcedunwind.c:52) ==6558== by 0x5154B03: _Unwind_ForcedUnwind (unwind-forcedunwind.c:126) ``` >這裡有出現一些感覺是 kernel 所分配的記憶體，目前還不知道要怎麼去釋放他們

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.