CS50 week 4 - Memory 筆記

👀 8 min read 👀

大家好,我是 Cindy,最近跟同事小夥伴相約一起看 CS50 的課程,CS50 (Introduction to Computer Science)是一堂美國哈佛大學知名的通識課程,完全免費,在 edxyoutubeCS50-Study-Group github 都可以非常容易地看到。

這系列的文章會是我的個人筆記,歡迎有興趣的人一定要自己去看看 CS50 的課程歐。

今天這篇是 CS50 week 4 筆記,想先看之前筆記的人可以點選下面連結:

十六進位(Hexadecimal)

用 1 2 3 4 5 6 7 8 9 A B C D E F 表示每個數字,例如十進位的 10 改成用十六進位表示的話就是 A。

RGB

紅綠藍三種顏色用十六進位表示,就是我們常看到的 #FF0000 #00FF00 #0000FF

記憶體位址

int n = 50; 當我們定義一個變數並給值,這些會被存在記憶體的位址中。

c 語言中可以看見變數的 addresses 是什麼:

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void)
{
int n = 50;
printf("%p\n", &n);
}

// 0x7ffd80792f7c (0x 前綴用來表示是 16 進位)

& 表示變數 n 的 address 是什麼,%p 表示 address 的 format (pointer)。

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void)
{
int n = 50;
printf("%i\n", *&n);
}

// 50

* 表示進去 address 裡面看。

Pointers

在記憶體中儲存著變數的 address 就叫做 pointer,可以當作是指向記憶體變數的指標。

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

int main(void)
{
int n = 50;
int *p = &n;
printf("%p\n", p);
}

// 0x12345678

將 address 儲存至變數時,前面要加一個 * 表示我知道自己在做什麼。
Pointer 往往佔了 8 bytes。

Strings

存在記憶體中連續的位址,用 \0 結尾,pointer 表示的是 string 第一個字母在記憶體的位址。
Char * 給你一個 pointer 指向字串中的第一個 character,其實就是 cs50 library 中的 string data type,而在 C 語言中會用 Char * 來表示。

  • Segmentation fault: 當我們觸碰了不該觸碰的記憶體區域,會發生的錯誤。

compare

char * 定義的變數進行比較時,比較的會是 address 而不是字母本身,可以用 strcmp()(來自 string.h 的方法)進行比較。

copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>

int main(void)
{
char *s = get_string("s: ");

char *t = s;

t[0] = toupper(t[0]);

printf("s: %s\n", s);
printf("t: %s\n", t);
}

上面這段程式碼因為複製的是指標位址,所以結果會將 s 和 t 都一起改變(因為指向同一個位址)。類似我之前寫過的這篇文章。

malloc & free

上一個問題可以用下面的程式碼解決,其中 malloc 是當我們直接跟 c 語言要記憶體空間時可以使用(分配記憶體空間),t == NULL 表示記憶體空間 address 不存在的錯誤,最後 free 將先前用 malloc 要的記憶體空間釋出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
char *s = get_string("s: ");

char *t = malloc(strlen(s) + 1);
if (t == NULL)
{
return 1;
}

for (int i = 0, n = strlen(s); i < n + 1; i++)
{
t[i] = s[i];
}

if (strlen(t) > 0)
{
t[0] = toupper(t[0]);
}

printf("s: %s\n", s);
printf("t: %s\n", t);

free(t);
}

valgrind

valgrind 是一個協助我們找出關於記憶體錯誤的工具,例如下面這段程式碼,很明顯我們使用了 malloc 要記憶體空間卻沒有使用 free 釋放記憶體空間,且我們只跟記憶體要了 3 byte 的空間,卻使用了 4 bytes,當我們執行 valgrind ./memory 可以看到這些錯誤的提示訊息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// memory.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
char *s = malloc(3); // 應該改成 char *s = malloc(4);
s[0] = 'H';
s[1] = 'I';
s[2] = '!';
s[3] = '\0';
printf("%s\n", s);
// 應該加上 free(s);
}

Garbage values

在我們將變數放進記憶體前,我們都不應該相信記憶體中已存在的東西,因為記憶體空間會被重複使用,曾經使用過記憶體空間不會被 reset,所以會存有所謂的 Garbage values,如果我們嘗試 dereference 還沒有被初始化過的 value,程式可能會發生 Segmentation fault,即我們觸碰了不該觸碰的記憶體空間。

這邊讓我想到 Ruby Conf Taiwan 2019 的時候 Aaron Patterson 大大演講的 Compacting GC for MRI,順便懷念一下我菜逼巴的心得

swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

void swap(int a, int b);

int main(void)
{
int x = 1;
int y = 2;

printf("x is %i, y is %i\n", x, y);
swap(x, y);
printf("x is %i, y is %i\n", x, y);
}

void swap(int a, int b)
{
int tmp = a;
a = b;
b = tmp;
}

上面這段程式碼實際上不會交換 x 和 y,原因如下:

Memory Layout

記憶體的空間配置如下:

  • machine code
  • globals
  • heap 往下 (每當我們使用 malloc 會從這個區域分配空間)
    |
  • stack 往上 (當我們 call function 的時候,使用的是這個區域的空間)

swap function 和 main function 會分別存在 stack 中的不同位置,當 swap 執行完畢時,交換的是 a 和 b,而不是 x 和 y,即 a 和 b 只是 x 和 y 複製而成的值,所以我們改成將 x y 的位置傳進去 swap,修改後的程式碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

void swap(int *a, int *b);

int main(void)
{
int x = 1;
int y = 2;

printf("x is %i, y is %i\n", x, y);
swap(&x, &y);
printf("x is %i, y is %i\n", x, y);
}

void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}

Heap overflow & Stack overflow

當 call function 的時候在記憶中 stack 的區域不停的往上使用空間,直到碰到了正在使用的 heap 區域,就被稱為 Stack overflow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
int height = get_int("Height: ");
draw(height);
}

void draw(int h)
{
draw(h - 1);

for (int i = 0; i < h; i++)
{
printf("#");
}
printf("\n");
}

當我們使用 recursion 時要特別注意,因為當我們不停的 call 自己的 function 時,而沒有給他停下來條件的話,程式會不停的往上使用 stack 的空間,最後出現 Segmentation fault,所以要將上面的程式碼改成下面這段程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void draw(int h)
{
if (h == 0)
{
return;
}

draw(h - 1);

for (int i = 0; i < h; i++)
{
printf("#");
}
printf("\n");
}

也就是說迭代(Iteration)可以確定不會發生 Stack overflow 的問題,但遞歸(Recursion)就要特別小心這個問題。

Buffer Overflow

表示我們使用了超過 Buffer 的記憶體空間。

scanf

當我們想要使用用戶輸入的值,可以使用 scanf,範例如下:

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void)
{
int x;
printf("x: ");
scanf("%i", &x);
printf("x: %i\n", x);
}
1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void)
{
char s[4];
printf("s: ");
scanf("%s", s);
printf("s: %s\n", s);
}

File I/O

範例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
FILE *file = fopen("phonebook.csv", "a");
if (file == NULL)
{
return 1;
}

char *name = get_string("Name: ");
char *number = get_string("Number: ");

fprintf(file, "%s,%s\n", name, number);

fclose(file);
}

特殊檔案例如 jpeg 有特殊的開頭(BYTE),可以查文件。