CS50 week 4 - Memory 筆記

,
👀 8 min read 👀

大家好，我是 Cindy，最近跟同事小夥伴相約一起看 CS50 的課程，CS50 (Introduction to Computer Science）是一堂美國哈佛大學知名的通識課程，完全免費，在 edx 或 youtube 或 CS50-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)，可以查文件。