# 2017q1 Homework4 (mergesort-concurrent)
contributed by <`hugikun999`>

## mergesort-concurrent

### 支援 string
按照作業解說的步驟，在執行時卻產生了錯誤。

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。

list_add(_list, atol(buffer));

對 `node_t` 增加一個 `char *lastname` 以便儲存名字，另外新增 `list_addc` `node_addc` 兩個函式處理字串的新增。這邊的 mergetsort 是以數字進行比較，必須另外提供一個 `string to val_t` 以取得每個字串的代表大小。

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;

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;
}

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`。

  /* 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 檢查記憶體是否有確實釋放

==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` 釋放了很多空間卻產生了錯誤@@

==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

void list_free_nodes(llist_t *list)
{
    node_t *cur = list->head;
    while (cur) {
        list->head = list->head->next;
        free(cur);
        cur = list->head;
    }
}

==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)

==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 所分配的記憶體，目前還不知道要怎麼去釋放他們