2020q3 Homework1 (lab0)

contributed by < Rsysz >

tags: `sysprog`

Outline

2020q3 Homework1 (lab0)
- Outline
- 環境
- 作業要求
- 實作流程
  - queue.h
  - queue.c
  - qtest.c
- 疑難排解
- Valgrind & Massif
- 參考資料
- TODO

環境









$ uname -a
Linux itlab-right 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux


$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

作業要求

q_new: 建立新的「空」佇列;
q_free: 釋放佇列所佔用的記憶體;
q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
q_size: 計算佇列中的元素數量。
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
q_sort: 以遞增順序來排序鏈結串列的元素

實作流程

queue.h

根據作業提示

Return number of elements in queue. Return 0 if q is NULL or empty Remember: It should operate in O(1)time

You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail

新增 int size 與 list_ele_t * tail 到 struct queue_t:





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

queue.c

q_new
- 初始化queue_t前先檢測是否成功分配記憶體空間，避免Segmentation fault











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

q_free
- 新增list_ele_t * tmp暫存q->head指標，遍歷queue_t將內部所有記憶體空間釋放














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

q_insert_head
- 新增節點newh後先行判定有無記憶體空間
- 利用newh->value = malloc(sizeof(char) * (strlen(s) + 1))於list_ele_t * newh結構內取得記憶體空間後判定有無取得結構內記憶體空間
- 使用strncpy(newh->value, s, strlen(s) + 1)複製strlen(s) + 1長度的字串(含'\0')至newh->value的記憶體空間中
  1. 將newh->next指向q->head，後取代原先的q->head
  2. 當新增的元素為queue_t中第一個元素時q->tail指向newh























 bool q_insert_head(queue_t *q, char *s)
 {
     if (!q)
         return false;
     list_ele_t *newh = malloc(sizeof(list_ele_t));
     /* DONE: What should you do if the q is NULL? */
     if (!newh)
         return false;
     newh->value = malloc(sizeof(char) * (strlen(s) + 1)); /*add 1 for '\0'*/
     if (!newh->value) {
         free(newh);
         return false;
     }
     strncpy(newh->value, s, strlen(s) + 1);
     /* Don't forget to allocate space for the string and copy it */
     /* What if either call to malloc returns NULL? */
     newh->next = q->head;
     q->head = newh;
     if (!q->tail)
         q->tail = q->head;
     q->size++;
     return true;
 }

q_insert_tail
- 新增節點newt後先行判定有無記憶體空間
- 利用newt->value = malloc(sizeof(char) * (strlen(s) + 1))於list_ele_t * newt結構內取得記憶體空間後判定有無取得結構內記憶體空間
- 使用strncpy(newh->value, s, strlen(s) + 1)複製strlen(s) + 1長度的字串(含'\0')至newt->value的記憶體空間中
  1. 當新增的元素為queue_t中第一個元素時q->head指向newt
  2. 若非第一個元素將q->tail->next指向newt
  3. 上述兩者執行完後將q->tail指向newt，更新q->tail指標























 bool q_insert_tail(queue_t *q, char *s)
 {
     /* Remember: It should operate in O(1) time */
     if (!q)
         return false;
     list_ele_t *newt = malloc(sizeof(list_ele_t));
     if (!newt)
         return false;
     newt->value = malloc(sizeof(char) * (strlen(s) + 1));
     if (!newt->value) {
         free(newt);
         return false;
     }
     strncpy(newt->value, s, strlen(s) + 1);
     newt->next = NULL;
     if (q->tail)
         q->tail->next = newt;
     else
         q->head = newt;
     q->tail = newt;
     q->size++;
     return true;
 }

q_remove_head
- 利用list_ele_t * tmp暫存q->head以便於將待刪除節點內的value存入char *sp
- 當傳入的buffersp不為NULL時，利用snprintf比較bufsize與sp的大小以確保'\0'的存入，避免Memory overflow
- 釋放刪除節點記憶體空間，當刪除的節點為最後一個時將q->tail指向NULL















 bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
 {
     if (!q_size(q))
         return false;
     list_ele_t *tmp = q->head;
     q->head = q->head->next;
     if (sp)
         snprintf(sp, bufsize, "%s", tmp->value);
     free(tmp->value);
     free(tmp);
     q->size--;
     if (!q_size(q))
         q->tail = NULL;
     return true;
 }

q_size
- 原本使用?做三元條件運算，但發現額外的else會導致超時，因此修改為單純if做判斷






 int q_size(queue_t *q)
 {
     if (!q)
         return 0;
     return q->size;
 }

q_reverse
- 利用cursor遍歷queue_t，重定q->head->next指標方向














 void q_reverse(queue_t *q)
 {
     if (!q || q->head == q->tail)  // Empty 0 | 1
         return;
     list_ele_t *cursor = NULL;
     q->tail = q->head;
     while (q->head) {
         list_ele_t *next = q->head->next;
         q->head->next = cursor;
         cursor = q->head;
         q->head = next;
     }
     q->head = cursor;
 }

q_sort
- q_sort僅作為副函數接口使用
- 為確保每種情況皆符合
  $O (n l o g (n))$ 的時間複雜度使用Top-down方法遞迴實現merge_sort
- 利用原生strcmp比較兩字串長度並將較小值放入遞迴中的list_ele_t * head進行merge














































 void q_sort(queue_t *q)
 {
     if (!q || q->head == q->tail)  // Empty 0 | 1
         return;
     q->head = q->tail = merge_sort(q->head);
     while (q->tail->next)
         q->tail = q->tail->next;
 }
 list_ele_t *merge_sort(list_ele_t *head)
 {
     if (!head || !head->next)
         return head;
     list_ele_t *l_head = head;
     list_ele_t *l_tail = head->next;
     /*split*/
     while (l_tail && l_tail->next) {
         l_head = l_head->next;
         l_tail = l_tail->next->next;
     }
     l_tail = l_head->next;
     l_head->next = NULL;
     l_head = head;
     /*sorting*/
     list_ele_t *l_h = merge_sort(l_head);
     list_ele_t *l_t = merge_sort(l_tail);
 
     return merge(l_h, l_t);
 }
 
 list_ele_t *merge(list_ele_t *l_h, list_ele_t *l_t)
 {
     list_ele_t *head = NULL;
     list_ele_t **cur = &head;
     while (l_h && l_t) {
         if (strcmp(l_h->value, l_t->value) > 0) {
             *cur = l_t;
             l_t = l_t->next;
         } else {
             *cur = l_h;
             l_h = l_h->next;
         }
         cur = &((*cur)->next);
     }
     *cur = l_t ? l_t : l_h;
     return head;

qtest.c

fill_rand_string














  static void fill_rand_string(char *buf, size_t buf_size)
  {
      size_t len = 0;
      if (buf_size < MIN_RANDSTR_LEN)  // not gonna happen cuz buf_size is set to
                                       // MAX_RADNSTR_LEN
          buf_size = MAX_RANDSTR_LEN;
      while (len < MIN_RANDSTR_LEN)
          len = rand() % buf_size;
  
      for (size_t n = 0; n < len; n++) {
          buf[n] = charset[rand() % (sizeof charset - 1)];
      }
      buf[len] = '\0';
  }

do_sort
- 為了使make test正常運行也修改了 traces 裡面的腳本將sort改為sort a
- 另外將trace-16-perf內部sort與reverse整合為sort d

















































  bool do_sort(int argc, char *argv[])
  {
      if (argc != 2) {
          report(1, "%s usage:[a/d]", argv[0]);
          return false;
      }
  
      if (!q)
          report(3, "Warning: Calling sort on null queue");
      error_check();
  
      int cnt = q_size(q);
      if (cnt < 2)
          report(3, "Warning: Calling sort on single node");
      error_check();
  
      set_noallocate_mode(true);
      if (exception_setup(true))
          q_sort(q);
      exception_cancel();
      set_noallocate_mode(false);
  
      if (!strcasecmp(argv[1], "d"))
          q_reverse(q);
  
      bool ok = true;
      if (q) {
          for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
              /* Ensure each element in ascending order */
              /* DONE: add an option to specify sorting order */
              if (!strcasecmp(argv[1], "a")) {
                  if (strcasecmp(e->value, e->next->value) > 0) {
                      report(1, "ERROR: Not sorted in ascending order");
                      ok = false;
                      break;
                  }
              } else {
                  if (strcasecmp(e->value, e->next->value) < 0) {
                      report(1, "ERROR: Not sorted in descending order");
                      ok = false;
                      break;
                  }
              }
          }
      }
 
      show_queue(3);
      return ok && !error_check();
  }

疑難排解

q_size

利用 ? 做三元條件運算
!q ? 0 : q->size;相當於if (!q) {return 0;} else {return q->size;}
後來發現這種方法會導致當無元素的queue_t不斷調用q_size時無法符合
$O (1)$ 的時間複雜度的需求
然後現在還不是很確定究竟if(!q || !q->head)是省掉的時間還是佔用的時間多




 int q_size(queue_t *q)
 {
     return !q ? 0 : q->size;
 }

q_sort

過程中的辛酸血淚待補









 void q_sort(queue_t *q)
 {
     if (!q || q->head == q->tail)  // empty 0 1
         return;
     q->head = q->tail = merge_sort(q->head);
     while (q->tail->next)
         q->tail = q->tail->next;
 }

Valgrind & Massif

使用以下指令測試Massif圖像化功能


$ valgrind --tool=massif ./qtest -v 3 -f traces/trace-eg.cmd
$ ms_print massif.out.[PID]

沒視窗介面不能使用Massif-Visualizer 可憐阿

--------------------------------------------------------------------------------
Command:            ./qtest -v 3 -f traces/trace-eg.cmd
Massif arguments:   (none)
ms_print arguments: massif.out.12119
--------------------------------------------------------------------------------


    KB
11.16^                                                                    #   
     |                                                          : ::@::@::#:  
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                                ::@::@::::::::@: @::#:: 
     |                                               :@:@::@::::::::@: @::#::@
   0 +----------------------------------------------------------------------->ki
     0                                                                   312.1

參考資料

TODO

運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
研讀論文 Dude, is my code constant time?

2020q3 Homework1 (lab0)

tags: sysprog

Outline

環境

作業要求

實作流程

queue.h

queue.c

qtest.c

疑難排解

Valgrind & Massif

參考資料

TODO

Read more

MTK / Bluetooth

ONVM-IPS / Hyperscan

VPP & DPDK

2020q3 Gameboy-emu

tags: `sysprog`