Try   HackMD

2019q1 Homework1 (lab0)

contributed by < F74021200 >

基本功能

1.Update q_new() ––(7/100)

  • Return NULL if no space to create queue.

2.Update q_free() ––(7/100)

  • Add the code for q_free().

3.Update q_insert_head() ––(7/100)

  • Use strdup() duplicate inserted string and store it into queue.

使用 qtest 測試:
cmd>show
cmd>show
q = NULL
cmd>new
cmd>new
q = []
cmd>ih 2
cmd>hi 2
q = [2]
cmd>free
dmc>free
當 free 時,發現有以下錯誤:
ERROR: Attempted to free unallocated block. Address = 0x55d10753eb10
ERROR: Attempted to free unallocated or corrupted block. Address = 0x55d10753eb10
ERROR: Corruption detected in block with address 0x55d10753eb10 when attempting to free it
ERROR: Attempted to free unallocated block. Address = 0x55d10753eb10

因為目前只實作了 q_new() 與 q_free() 與 q_insert_head() ，依照錯誤訊息，有使用到 unallocated block ，所以問題應該出在 malloc ，由 man page：The malloc() function allocates size bytes and returns a pointer to the allocated memory. 且由 Return Value : malloc() returns a pointer to the allocated memory that is suitably aligned for any kind of variable. On error, these functions return NULL.，如果無法找到這樣的空間， malloc 會回傳 NULL ， 但是這個 malloc 沒有回傳 NULL ，代表確實有記憶體能夠使用;另外，不太了解 unallocated block 的意思;之後在討論區有看到原來 malloc 有在 harness.h 被重新定義，於是便開始看 harness.c 的程式碼。

避免用「就我所知」這樣的話語，明明有一堆語言和執行環境規範可參照，你為何不列出 man page 或者相關 POSIX 規範出來呢？
工程人員實事求是的精神要拿出來，及早脫離「文組TM」

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

在 harness.c 中，使用一個 linked list 來管理使用的記憶體，在這個 linked list 中，每個 node 的資料型態是 BELE(block element) ，每次分配的空間都會用一個 BELE 的 node 連接，以監控所使用的記憶體；以下針對 BELE 的內部 element 作說明：

  1. BELE *next
    用來指向下一個 BELE 的節點 。

  2. BELE *prev
    用來指向上一個 BELE 的節點 。

  3. size_t payload_size
    用來紀錄連結這個 BELE 節點的空間大小，也就是需要分配的空間大小。

  4. size_t magic_header
    用來標記分配的空間是經由 test_malloc() 所 allocate 的。
    另外，在 test_malloc 中，使用 malloc() 時，給 malloc 的參數是：需要分配的空間大小
    (size) + BELE 節點大小 + size_t 這個型態的大小，其中，最後一個 size_t 在
    test_malloc 中會被賦予 0xbeefdead ，也就是 MAGICFOOTER 代表的值，用來標示所分配
    空間的結尾。

  5. unsigned char payload[0]
    紀錄分配的記憶體的開頭位址。

4. Allocate memory in q_insert_head() ––(14/100)

  • Use malloc two times.The first malloc allocates memory for queue node,
    and the second allocates memory for string.

5. No-space-for-string condition in q_insert_head() ––(21/100)

  • When the second malloc function fails to allocate memory, before
    returning false, the memory allocated by the first malloc should be
    freed to prevent memory leak.

在 q_insert_head 中，當第二次的 malloc 回傳 NULL 時，若沒有先 free 第一次分配的空間，在
git commit 時會出現 "(error) Memory leak: newh"

6. update q_insert_tail() ––(21/100)

  • Add a field, tail, with type list_ele_t* in structure queue_t for inserting
    from tail in O(1) time.

7. update q_insert_head() ––(21/100)

  • Before inserting a new queue node from head, if the head pointer is NULL,
    then let tail pointer point to the new node.

8. Add insert-from-tail operation ––(28/100)

  • Initialize tail in q_new()
  • In q_insert_tail, malloc two space
    for a queue node and a string, respectively.After copying inserted
    string to the allocated space,let "value" pointer of the new queue node
    point to the duplicate.When inserting, let the "next" pointer of the
    node pointed by "tail" point to the new node, and then let "tail" point
    to the new node.If "tail" is NULL, let "tail" and "head" both point to
    the new node.
  • Change the initial "return false" to "return true"

9. update q_remove_head() ––(54/100)

  • Check whether q is NULL or empty.Then, check whether sp is non-NULL.If
    not, copy the removed string to sp, in which strncpy is used.
  • According to man page, A simple implementation of strncpy() might be:












char *
strncpy(char *dest, const char *src, size_t n)
{
    size_t i;

   for (i = 0; i < n && src[i] != '\0'; i++)
        dest[i] = src[i];
    for ( ; i < n; i++)
        dest[i] = '\0';

   return dest;
}

​​​​One valid (and intended) use of strncpy() is to copy a C string to a 
​​​​fixed-length buffer while ensuring both that the buffer is not 
​​​​overflowed and that unused bytes in the target buffer are zeroed out.
​​​​However, if the length of src is longer than n, the terminating null 
​​​​byte ('\0') should be set to the last byte of dest.Instead of comparison
​​​​the length, I set '\0' to the last byte of sp no matter the length of
​​​​the string is longer than that of sp or not for the reason that at each
​​​​time, the comparison is implemented one time and assigning is if the
​​​​comparison  returns true,in which at least one instruction is implemented
​​​​and sometimes two.Therefore, assigning is implemented every time to 
​​​​make only one instruction implemented at the part.
  • After copy the removed string, use a temporary pointer to point to the
    removed queue element,and then have the head of q point to the next of
    the removed queue element.Finally, free the string and the queue element,
    and return true.

10. Get the size of the queue ––(74/100)

  • Add a field, q_size,with type int to queue_t structure in queue.h and
    initialize q_size in q_new() with zero.Add 1 to q_size when inserting
    from head and inserting from tail.Substract 1 from q_size when
    removing from head. In the function ,q_size(),return 0, when queue
    is NULL,otherwise, return q_size of the queue.

11. Let q be able to be reversed ––(93/100)

  • If q is not NULL and q is not empty,reverse is available. At first,declare
    two pointers,ele_next and ele_now, to help reverse the queue.The idea
    is that the function have a pointer go through the old queue list from
    the head to the tail.Before that pointer goes to the next,the current
    pointed element is inserted in queue from the head.ele_next is the
    moving pointer mentioned above, and ele_now is used to point to the
    element to be inserted to the queue from the head.
  • Actually, ele_next begin going from the next of the element pointed by
    the head of q.For the initial element to be the tail of the reversed queue,
    NULL should be set to the next of the element.

Error message

ERROR:Segmentation fault occurred. You dereferenced a NULL or invalid pointer
ERROR:Segmentation fault occurred. You dereferenced a NULL or invalid pointer
ERROR:Segmentation fault occurred. You dereferenced a NULL or invalid pointer
––(93/100)

After adding checking whether the inserted q is NULL in q_free(),
ERROR:Segmentation fault occurred. You dereferenced a NULL or invalid pointer
ERROR:Segmentation fault occurred. You dereferenced a NULL or invalid pointer
––(93/100)

After adding checking whether the inserted q is NULL in ,q_insert_head(),
ERROR:Segmentation fault occurred. You dereferenced a NULL or invalid pointer
––(93/100)

After adding checking whether the inserted q is NULL in ,q_insert_tail(),
––(100/100)

Address NULL-q contitions.

  • In q_free(), if q is NULL,do nothing.
  • In q_insert_head(), first check whether q is NULL, if yes, return false.
  • In q_insert_tail(), first check whether q is NULL, if yes, return false.

By doing above, the function can prevent from segmentation fault caused
by get some fields at NULL.

Simplify codes in q_remove_head()

  • Change the below




if(q == NULL)
    return false;
else if(q->head == NULL)
    return false;

to



if(q == NULL || q->head == NULL)
    return false;

The above two codes have the same operation.According to ISO/IEC 9899 (a.k.a C99 Standard) at page 89, we know that "the || operator guarantees left-to-right evaluation;
there is a sequence point after the evaluation of the first operand. If the first operand
compares unequal to 0, the second operand is not evaluated."
Therefore, if q is NULL, "q->head == NULL" is not evaluated, and segmantation error
can't occur.

Narrow the scope of some local variables

Last changed by 
 
F74021200
0
346
Published on HackMD