2019q1 Homework1 (lab0)

contributed by < njjack >

注意看 2019q1 Homework1 (作業區) 的要求，HackMD 網址應採 publish 後的網址，請留意細節，及早變更。包含空白和排版，均有指定格式。
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

jserv

C Programming Lab

環境

$ cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.3 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.3 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              61
Model name:            Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
製程：              4
CPU MHz：             1609.716
CPU max MHz:           2700.0000
CPU min MHz:           500.0000
BogoMIPS:              4389.82
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

題目

實作 queue functions

• q_new
• q_free
• q_insert_head
• q_insert_tail
• q_remove_head
• q_size
• q_reverse

實作

考慮題目要求 q_insert_tail( ) 和 q_size( ) 執行時間需為

$O(1)$，在 queue_t 結構中加入 size 和 tail

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q) {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q) {
        list_ele_t *temp;
        while (q->head) {
            temp = q->head;
            q->head = temp->next;
            free(temp);
        }
        free(q);
    }
}

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }

    newh->next = q->head;
    q->head = newh;
    if (q->size == 0) {
        q->tail = newh;
    }
    q->size++;
    return true;
}

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }

    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    q->tail = newh;
    q->size++;
    return true;
}

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0) {
        return false;
    }
    list_ele_t *temp = q->head;
    if (sp) {
        memcpy(sp, temp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    q->head = temp->next;
    free(temp);
    q->size--;
    return true;
}

q_size

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (!q)
        return 0;
    return q->size;
}

q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size == 0) {
        return;
    }
    list_ele_t *current = q->head;
    list_ele_t *cnext = current->next;
    list_ele_t *temp = current;
    while (cnext) {
        current = cnext;
        cnext = cnext->next;
        current->next = temp;
        temp = current;
    }
    q->tail = q->head;
    q->tail->next = NULL;
    q->head = current;
}

自動評分系統運作原理

command

command 以 struct CELE 表示，儲存在 single linked list 中

struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

呼叫 add_cmd 將一個新的 command 加入 linked list 中適當位置（按字母順序排序）

void add_cmd(char *name, cmd_function operation, char *documentation)
{
    cmd_ptr next_cmd = cmd_list;
    cmd_ptr *last_loc = &cmd_list;
    while (next_cmd && strcmp(name, next_cmd->name) > 0) {
        last_loc = &next_cmd->next;
        next_cmd = next_cmd->next;
    }
    cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
    ele->name = name;
    ele->operation = operation;
    ele->documentation = documentation;
    ele->next = next_cmd;
    *last_loc = ele;
}

每次 command 輸入會呼叫 interpret_cmda 來搜尋 linked list ，找到並呼叫 command 對應之處理函式
(實際上每次 command 輸入按 function call 順序會呼叫 cmd_select , interpret_cmd , parse_args, 最後才將 parsing 後得到之 "command that has already been split into arguments" 作為 input 呼叫 interpret_cmda )

/* Execute a command that has already been split into arguments */
static bool interpret_cmda(int argc, char *argv[])
{
    if (argc == 0)
        return true;
    /* Try to find matching command */
    cmd_ptr next_cmd = cmd_list;
    bool ok = true;
    while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
        next_cmd = next_cmd->next;
    if (next_cmd) {
        ok = next_cmd->operation(argc, argv);
        if (!ok)
            record_error();
    } else {
        report(1, "Unknown command '%s'", argv[0]);
        record_error();
        ok = false;
    }
    return ok;
}

memory management

• harness.h 中藉由 macro 將 malloc 和 free 替換成 test_malloc 和 test_free

#define malloc test_malloc
#define free test_free

• 以 block_ele_t 結構實作一 doubly linked list ，記錄已分配之記憶體空間。
• 其中 payload[0] 為 Array of Length Zero 技巧之使用。每一段已分配記憶體空間都有一 block_ele_t 結構之 header ，藉由存取 payload 可直接存取此 header 之後的記憶體空間。

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

• 呼叫 test_malloc 實際會分配的記憶體空間，除了提出請求之記憶體大小，還包含 header(一個 block_ele_t 結構) 和 tail (一個 magic number)
• test_malloc 成功配置記憶體空間後，會將 header 中 magic_header 設 MAGICHEADER ， 並呼叫 find_footer 找到 tail 的 magic number 設為 MAGICFOOTER
• MAGICHEADER 和 MAGICFOOTER 分別為常數 0xdeadbeef 和 0xbeefdead ，作為存取位置是否合法的判斷依據

void *test_malloc(size_t size)
{
    ...
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }
    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    ...
}

• test_free 會檢查 tail 的 magic number 是否為 MAGICFOOTER ，若否，則釋放此空間非合法動作
• test_free 將magic_header 和 tail 的 magic number 都設為 MAGICFREE

void test_free(void *p)
{
    ...
    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    ...
}

• test_malloc 和 test_free 都會將配置或是放的記憶體空間初始為常數 FILLCHAR 已避免若某位置存放數值恰為前述已使用過之常數，可能造成判斷合法與否時誤判
  `