2018q3 Homework2 (lab0)

contributed by < kevin110604 >

記得補上實驗環境
課程助教

好的
kevic110604

tags: 2018q3

開發過程

q_new()

  • malloc 空間給 queue_t *q 。

q_insert_head()

  • 這邊我原本忘了考慮到如果第二次 malloc() 失敗，要記得把第一次 malloc() 的空間先 free() 再 return 。
  • 在分配記憶體給字串的時候要記得多保留 1 bit 給 \0 的空間。
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    
    if (q == NULL)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    
    newh->value = malloc(strlen(s) + 1);   // watch out!!!
    if (newh->value == NULL) {
        free(newh);                        // watch out!!!
        return false;
    }
    ...
}

q_remove_head()

  • 這邊經朋友提醒 strncpy() 前要先檢查 sp 是否不為 NULL 。
  • 同樣地要預留一個空間給 \0 ，並在 strncpy() 之後自己在結尾補上 \0。
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
 {
     /* You need to fix up this code. */
     if (q == NULL || q->head == NULL)
         return false;
     if (sp != NULL) {             // watch out!!!
         strncpy(sp, q->head->value, bufsize - 1);
         sp[bufsize - 1] = '\0';   // watch out!!!
    }
    ...
}

q_free()

  • 在 free 掉每一個 node 之前，要先 free 裡面儲存字串的空間。

q_insert_tail()

  • 為了因應要求 operate in O(1) time ，所以修改了 structure:
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* 新增 tail 指標指向尾巴的節點 */
    int size;
} queue_t;

q_size()

  • 同樣為了因應要求 operate in O(1) time ，所以修改了 structure:
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* 新增 tail 指標指向尾巴的節點 */
    int size;         /* 隨時記錄現在有幾個節點 */
} queue_t;

q_reverse()

  • 這邊我用 for loop ，從頭 traverse linked list 每一個 element 的方式去完成。

自動評分系統運作的原理

當我們 make test 的時候，會執行 scripts/driver.py 這支程式，而由 class Tracer 裡面的 runTrace() 這個函式，可以發現：














    def runTrace(self, tid):
        if not tid in self.traceDict:
            print "ERROR: No trace with id %d" % tid
            return False
        fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
        vname = "%d" % self.verbLevel
        clist = [self.qtest, "-v", vname, "-f", fname]
        try:
            retcode = subprocess.call(clist)  # 執行 qtest
        except Exception as e:
            print "Call of '%s' failed: %s" % (" ".join(clist), e)
            return False
        return retcode == 0

在第68行， driver.py 去 run qtest 。而在 class Tracer 裡面的 run() 裡可以看到評分的過程：















        score = 0
        maxscore = 0
        for t in tidList:
            tname = self.traceDict[t]
            if self.verbLevel > 0:
                print "+++ TESTING trace %s:" % tname
            ok = self.runTrace(t)
            maxval = self.maxScores[t]
            tval = maxval if ok else 0  # 檢查有無發生意外
            print "---\t%s\t%d/%d" % (tname, tval, maxval)
            score += tval      # 計算分數
            maxscore += maxval
            scoreDict[t] = tval
        print "---\tTOTAL\t\t%d/%d" % (score, maxscore)

測資是來自 traces/ 裡的15個檔案。每一個測資都有個別的分數，執行結果正確並且沒有發生 exception 就可以拿到分數。

qtest 的行為和裡頭的技巧

觀察 qtest.c 裡的 main()


















































int main(int argc, char *argv[])
{
    /* To hold input file name */
    char buf[BUFSIZE];
    char *infile_name = NULL;
    char lbuf[BUFSIZE];
    char *logfile_name = NULL;
    int level = 4;
    int c;

    while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
        switch (c) {
        case 'h':
            usage(argv[0]);
            break;
        case 'f':
            strncpy(buf, optarg, BUFSIZE);
            buf[BUFSIZE - 1] = '\0';
            infile_name = buf;
            break;
        case 'v':
            level = atoi(optarg);
            break;
        case 'l':
            strncpy(lbuf, optarg, BUFSIZE);
            buf[BUFSIZE - 1] = '\0';
            logfile_name = lbuf;
            break;
        default:
            printf("Unknown option '%c'\n", c);
            usage(argv[0]);
            break;
        }
    }
    queue_init();
    init_cmd();
    console_init();
    set_verblevel(level);
    if (level > 1) {
        set_echo(true);
    }
    if (logfile_name)
        set_logfile(logfile_name);
    add_quit_helper(queue_quit);
    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;
}

前面大致上是一些初始化的設定，直到573行的 run_console(infile_name); 才是真正開始執行整個 console 的地方。值得注意的是從 console.c 和 console_init():













static void console_init()
{
    add_cmd("new", do_new, "                | Create new queue");
    add_cmd("free", do_free, "                | Delete queue");
    add_cmd("ih", do_insert_head,
            " str [n]        | Insert string str at head of queue n times "
            "(default: n == 1)");
    add_cmd("it", do_insert_tail,
            " str [n]        | Insert string str at tail of queue n times "
            "(default: n == 1)");
    ...
}

可以發現有使用到 GDB (GNU debugger) ，舉例來說，上面就利用 add_cmd() 來新增 new, free, ih, it…等指令，後面的 do_new, do_free, do_insert_head… 則是這些指令的函式實作，裡面會呼叫我們在 queue.c 裡寫的函式，例如 q_new(), q_free(), q_insert_head()…。

harness.[ch]

以下內容是詢問朋友 ChingChieh 後才知道的。

在 harness.h 裡可以發現我們之前使用的 malloc(), free() 都是自己定義的




/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free

先看 block_ele_t 的定義

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() ，可以在裡面發現真正使用 malloc() 的地方



block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));

也就是說，除了我們需要 allocate 的大小 size bits 之外，這個 pointer new_block 還包含了 sizeof(block_ele_t) bits 的空間和 sizeof(size_t) bits 的空間。
而 test_malloc() 最後 return 的 p 實際上是

void *p = (void *) &new_block->payload;

也就是我們 return 的 pointer p 指向的是 new_block->payload 之後的空間。
綜合以上幾點的觀察，我們可以推測 new_block 的空間分配情形如下圖

digraph graphname{

    node[shape=record]


    memory[label="struct block_ele_t| size bits|size_t"]
}

又 test_malloc() 裡面有這段 code




    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;

然後 find_footer() 回傳的是那個我們在 queue.c malloc 的那段空間的尾巴

/* Given pointer to block, find its footer */
static size_t *find_footer(block_ele_t *b)
{
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    return p;
}

也就是說我們在 queue.c malloc 的那段空間的頭 new_block->magic_header 和我們在 queue.c malloc 的那段空間的尾巴 *find_footer(new_block) 都被assign 成某個特定的值，所以我們可以透過檢查這些值來偵測是否有不合法的空間存取。例如在 test_free() 裡：





if (footer != MAGICFOOTER) {
    ...
    error_occurred = true;
}

實驗環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic

$ cat /proc/version
Linux version 4.15.0-34-generic (buildd@lgw01-amd64-047) (gcc version 7.3.0 (Ubuntu 7.3.0-16ubuntu3)) #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018
Select a repo