---
# System prepended metadata

title: 2021q1 quiz6

---

# 2021q1 quiz6
* [2021q1 第 6 週測驗題
](https://hackmd.io/@sysprog/linux2021-quiz6)

## 測驗 2 - hashmap - twoSum

### malloc array of pointer to structure 問題
請問在第六週測驗題內 hash table 的實作
在 `map_init()` 內
`map->ht` 這個 pointer to array of `hlist_head` 是什麼時候定義出來的呢？
為什麼在這一行
`(map->ht)[i].first = NULL;`
可以直接對 array 內的成員做初始化呢？
```c=
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    ...
}
// in map_init()
map_t *map_init(int bits) {
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}
```

#### 推導過程
`map->ht` 是 pointer to array of `hlist_head`, 
然後在 line 13 我們分配了一個 element 數量為 2^bits^ 的 array 給 `map->ht` 這個 pointer to `hlist_head`, 他會指向整個 array 的第一個 element, 我們可以使用 `(map->ht)[i]` 來 access 每個 element 

以下為 gdb 的實驗結果
```shell
Starting program: quiz6/twoSum

Breakpoint 1, map_init (bits=21845) at twoSum.c:11
11	map_t *map_init(int bits) {
(gdb) n
12	    map_t *map = malloc(sizeof(map_t));
(gdb) n
13	    if (!map)
(gdb) n
16	    map->bits = bits;
(gdb) n
17	    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
(gdb) n
18	    if (map->ht) {
(gdb) ptype map->ht
type = struct hlist_head {
    struct hlist_node *first;
} *
(gdb) n
19	        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(gdb) n
20	             (map->ht)[i].first = NULL;
(gdb) ptype (map->ht)[0]
type = struct hlist_head {
    struct hlist_node *first;
}
(gdb)
```

:::warning
可改用 GDB 的 [watch](https://sourceware.org/gdb/onlinedocs/gdb/Set-Watchpoints.html) 命令
:notes: jserv
:::

由上面的 code 可得知 `map->ht` 的型態確實為 pointer to `hlist_head`
```cpp
(gdb) ptype map->ht
type = struct hlist_head {
    struct hlist_node *first;
} *
```

而 `(map->ht)[0]` 的型態為 hlist_head
```cpp
(gdb) ptype (map->ht)[0]
type = struct hlist_head {
    struct hlist_node *first;
}
```

#### gdb `watch` command 實驗

* set watchpoint at `(map->ht)[10].first`
    * 使用
    * 預想當我們 assign `NULL` 給 `(map->ht)[10].first` 時會停止程式
    * 問題: 為什麼第一次會無法觸發，但是第二次可以呢？
    * [stackoverflow - GDB: How to force a watchpoint to not be deleted after a function returned?](https://stackoverflow.com/questions/25938830/gdb-how-to-force-a-watchpoint-to-not-be-deleted-after-a-function-returned)
    * [Is the “struct hack” technically undefined behavior?](https://stackoverflow.com/questions/3711233/is-the-struct-hack-technically-undefined-behavior)
這裡的行數與一開始不同！
```shell=
(gdb) b 18
Breakpoint 1 at 0x11ca: file twoSum.c, line 18.
(gdb) r
Starting program: /home/ubuntu/repo/unknowntpo/sandbox/linux/linux2021spring/quiz6/twoSum

Breakpoint 1, map_init (bits=10) at twoSum.c:18
18	    if (map->ht) {
(gdb) watch -l (map->ht)[10].first
Hardware watchpoint 2: -location (map->ht)[10].first
(gdb) c
Continuing.
[Inferior 1 (process 67597) exited normally]
(gdb) info breakpoints
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x00005555555551ca in map_init at twoSum.c:18
	breakpoint already hit 1 time
2       hw watchpoint  keep y                      -location (map->ht)[10].first
(gdb) r
Starting program: /home/ubuntu/repo/unknowntpo/sandbox/linux/linux2021spring/quiz6/twoSum

Breakpoint 1, map_init (bits=10) at twoSum.c:18
18	    if (map->ht) {
(gdb) c
Continuing.

Hardware watchpoint 2: -location (map->ht)[10].first

Old value = <unreadable>
New value = (struct hlist_node *) 0x0
map_init (bits=10) at twoSum.c:19
19	        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
```

:::info
對於兩次實驗結果不符合預期有點在意，是不是自己漏掉了什麼條件沒考慮到？
:::

#### :question: 延伸問題: 是否可以越界存取 heap 內超過 array 範圍的地址？

程式碼如下: 
```c=1
#include <stdio.h>
#include <stdlib.h>

#define TABLESIZE 10

int main() {
    int a[TABLESIZE];

    // pointer to array of integer
    int *pa;
    pa = malloc(sizeof(int) * TABLESIZE);
    
    // init array elements
    for (int i = 0; i < TABLESIZE; i++)
        (pa)[i] = 5;

    // try to access pa[40]
    printf("pa[40] = %d\n", pa[40]);
}
```

使用 gdb 測試

```shell=1
Reading symbols from ./malloc...
(gdb) b 11
Breakpoint 1 at 0x11a4: file malloc.c, line 11.
(gdb) r
Starting program: /home/ubuntu/xxx/malloc/malloc

Breakpoint 1, main () at malloc.c:11
warning: Source file is more recent than executable.
11	    pa = malloc(sizeof(int) * TABLESIZE);
(gdb) n
12	    for (int i = 0; i < TABLESIZE; i++)
(gdb) n
13	        (pa)[i] = 5;
(gdb) n

...

16	    printf("pa[40] = %d\n", pa[40]);
(gdb)
pa[40] = 0
17	}
(gdb) x/40xw &pa[0]
0x5555555592a0:	0x00000005	0x00000005	0x00000005	0x00000005
0x5555555592b0:	0x00000005	0x00000005	0x00000005	0x00000005
0x5555555592c0:	0x00000005	0x00000005	0x00000411	0x00000000
0x5555555592d0:	0x345b6170	0x3d205d30	0x000a3020	0x00000000
0x5555555592e0:	0x00000000	0x00000000	0x00000000	0x00000000
0x5555555592f0:	0x00000000	0x00000000	0x00000000	0x00000000
0x555555559300:	0x00000000	0x00000000	0x00000000	0x00000000
0x555555559310:	0x00000000	0x00000000	0x00000000	0x00000000
0x555555559320:	0x00000000	0x00000000	0x00000000	0x00000000
0x555555559330:	0x00000000	0x00000000	0x00000000	0x00000000
```

結果發現 `pa[40]` 是可以被 access 的！
如果 `pa[40]`所在的地址已經被別人使用的話會不會造成安全問題呢？

根據林志恩同學的回答

>如果存取超出範圍會是未定義行為。
以下為 Committee Draft — December 2, 2010 ISO/IEC 9899:201x
J.2 Undefined behavior
An array subscript is out of range, even if an object is apparently accessible with the given subscript (as in the lvalue expression a[1][7] given the declaration int a[4][5]) (6.5.6).
其他相關討論也可以看這篇 stackoverflow 的文章：
[Is it undefined behaviour to access an array beyond its end, if that area is allocated? [duplicate]](https://stackoverflow.com/questions/12354413/is-it-undefined-behaviour-to-access-an-array-beyond-its-end-if-that-area-is-all)

## [測驗 3](https://hackmd.io/@sysprog/linux2021-quiz6#%E6%B8%AC%E9%A9%97-3)