2019q1 Homework1 (lab0)

contributed by < chenIshi >

實驗環境

OS: Ubuntu 16.04.5 LTS
Kernel: 4.15.0-36-generic
CPU: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Byte-order: Little Endian

是不是該升級 Ubuntu Linux 系統呢？
jserv

不過 Autoware 官方好像是建議用 16.04 的 Ubuntu 加上 ROS kinetic
為此裝兩個版本的 Ubuntu 或開虛擬機跑 autoware 好像都有點不適合
陳奕熹

C Programming Lab 第一份作業要求

1. 整份程式目標在1~2小時內完成
2. 需要處理不合法的操作，像是嘗試對 NULL/ Empty List 作 remove
3. 部份操作要求在常數時間內完成，像 q_size()

free()對不同資料結構實做狀況

1. 起因：q_free() 需要把 link list 全部記憶體釋放（不能只釋放queue_t）
2. 實驗：資料儲存型態以及free()後記憶體狀態

struct offset 操作

#include <stdlib.h>
#include <string.h>

typedef struct ELE {
    struct ELE *next;
    char *value;
} list_t;

int main()
{
    /* set queue head */
    list_t *queue;
    queue = malloc(sizeof(list_t));

    queue->value = strdup("hello world");

    /* call next by in-struct pointer */
    list_t *to_be_insert;
    to_be_insert = malloc(sizeof(list_t));

    queue->next = to_be_insert;
    to_be_insert->value = strdup("bye world");

    /* call next by memory offset */
    (queue + 1)->value = strdup("weird world");
    (queue + 1)->next = NULL;

    return 0;
}

為了減少queue_t裡面 metadata 的數量，我試著看能不能用 queue size 推出指向tail的記憶體位址

一開始因為不熟悉 pointer 的加減法，所以誤用 *(queue + 1) 去存取結構
後來才發現到的確是可以用 queue + sizeof(list_t) / sizeof(queue) * size 的方法拿到 tail 的，不過有一個很重要的前提在於 struct 結構間不能有其他的動態分配記憶體，不然這樣取記憶體位移就會錯誤，所以最後也沒有採取這樣的方法

有個變形的 XOR linked list 就利用指標之間的數值落差，做出節省記憶體開銷的資料結構
jserv

但是在用 gdb 檢查記憶體狀況的時候，發現了部份應該屬於 你所不知道的C語言 範疇的問題

1. 結構元素在記憶體對應的順序先後是怎麼決定的？

list_t 元素宣告時，是 struct ELE *next 先於 char *value
但是記憶體對應位址先後卻是相反 ?

2. 結構元素間的記憶體位移大小為什麼都是0x20(也就是十進位的16)，明明每個元素大小應該都只有 pointer 大小，也就是 0x10?

神奇的 git hook

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    char *val;
    val = strdup(s);
    if (val == NULL)
        free(newh);
        return false;

以上是 q_insert_tail() 一開始初始化記憶體部份，一開始 commit 的時候
我忘記在 line 60 可以把 newh 記憶體空間釋放，很神奇的是 git hook 有抓到這個 memory leak
而且 debug 訊息非常明確，不是在 line 55 需要我去釋放 NULL 的記憶體配置
這讓我不禁開始懷疑背後要怎麼實做，畢竟編譯器最佳化印象中沒提到這個部份
正如老師說的，工程師說出「似乎」「印象中」這種話是相當不負責任的，

看懂 cppcheck 如何做程式靜態分析嗎？
jserv

q_free()

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    /* Free queue head first */
    if (q == NULL)
        return;

    list_ele_t *free_ptr;
    list_ele_t *temp;
    free_ptr = q->head;
    while (free_ptr != NULL) {
        temp = free_ptr;
        free_ptr = free_ptr->next;
        free(temp);
    }
    free(q);
}

原本在 line 13 ~ 15 有嘗試釋放 value 的記憶體位址，不過就從錯誤訊息來看
該位址並沒有被 malloc() 過，因此嘗試釋放它可能會導致失敗或甚至 core dump
因為一直不清楚 qtest 會怎麼呼叫 q_insert_head/tail()
畢竟執行 qtest 時只會顯示插入的值