Exercise 17 Lập Trình C – Learn C The Hard Way


Exercise 17: Heap And Stack Memory
Allocation

Trong bài học hôm nay, bài này là một bài thật sự khó, sẽ có những bạn thấy nó quá “tởm”. Tác giả cũng khẳng định điều này. Nhưng không sao, chuyện gì cũng có thể làm được. Tin tôi đi! :))
Không phải chúng ta học một exercise trong vòng một vài phút, hay một vài tiếng. Nhiều khi chúng ta phải học nó trong vài ngày. Giống như bài này chẳng hạn. Sau tất cả lời cảnh báo, chúng ta bắt đầu bài này nào. Vượt qua được bài này thì chúng ta sẽ ổn trong ngôn ngữ C.

Bài hôm nay, chúng ta sẽ xây dựng một chương trình “nhỏ” dùng để quản lý database. Lưu ý, chương trình này không có hiệu quả cao và cũng không chứa được nhiều data. Nhưng quan trọng, nó cho chúng ta thấy như thế nào là một chương trình thực tế, và quan trọng hơn là bạn biết những gì bạn cần phải học để thành master.
Trong bài này, chúng tôi cũng giới thiệu về về “memory” và bắt đầu làm việc với file. Trong này chúng sẽ sử dụng một số hàm xử lý file I/O nhưng chúng tôi sẽ không giải thích nó quá nhiều và để nó ở một bài khác.

Đoạn code sau đây khá dài

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

#define MAX_DATA 512
#define MAX_ROWS 100

struct Address {
    int id;
    int set;
    char name[MAX_DATA];
    char email[MAX_DATA];
};

struct Database {
    struct Address rows[MAX_ROWS];
};

struct Connection {
    FILE *file;
    struct Database *db;
};

void die(const char *message)
{
    if (errno) {
        perror(message);
    } else {
        printf("ERROR: %s\n", message);
    }

    exit(1);
}

void Address_print(struct Address *addr)
{
    printf("%d %s %s\n", addr->id, addr->name, addr->email);
}

void Database_load(struct Connection *conn)
{
    int rc = fread(conn->db, sizeof(struct Database), 1, conn->file);
    if (rc != 1)
        die("Failed to load database.");
}

struct Connection *Database_open(const char *filename, char mode)
{
    struct Connection *conn = malloc(sizeof(struct Connection));
    if (!conn)
        die("Memory error");

    conn->db = malloc(sizeof(struct Database));
    if (!conn->db)
        die("Memory error");

    if (mode == 'c') {
        conn->file = fopen(filename, "w");
    } else {
        conn->file = fopen(filename, "r+");

        if (conn->file) {
            Database_load(conn);
        }
    }

    if (!conn->file)
        die("Failed to open the file");

    return conn;
}

void Database_close(struct Connection *conn)
{
    if (conn) {
        if (conn->file)
            fclose(conn->file);
        if (conn->db)
            free(conn->db);
        free(conn);
    }
}

void Database_write(struct Connection *conn)
{
    rewind(conn->file);

    int rc = fwrite(conn->db, sizeof(struct Database), 1, conn->file);
    if (rc != 1)
        die("Failed to write database.");

    rc = fflush(conn->file);
    if (rc == -1)
        die("Cannot flush database.");
}

void Database_create(struct Connection *conn)
{
    int i = 0;

    for (i = 0; i < MAX_ROWS; i++) 
    { 
        // make a prototype to initialize it 
        struct Address addr = {.id = i,.set = 0 }; 
        
        // then just assign it 
        conn->db->rows[i] = addr;
    }
}

void Database_set(struct Connection *conn, int id, const char *name,
        const char *email)
{
    struct Address *addr = &conn->db->rows[id];
    if (addr->set)
        die("Already set, delete it first");

    addr->set = 1;
    // WARNING: bug, read the "How To Break It" and fix this
    char *res = strncpy(addr->name, name, MAX_DATA);
    // demonstrate the strncpy bug
    if (!res)
        die("Name copy failed");

    res = strncpy(addr->email, email, MAX_DATA);
    if (!res)
        die("Email copy failed");
}

void Database_get(struct Connection *conn, int id)
{
    struct Address *addr = &conn->db->rows[id];

    if (addr->set) {
        Address_print(addr);
    } else {
        die("ID is not set");
    }
}

void Database_delete(struct Connection *conn, int id)
{
    struct Address addr = {.id = id,.set = 0 };
    conn->db->rows[id] = addr;
}

void Database_list(struct Connection *conn)
{
    int i = 0;
    struct Database *db = conn->db;

    for (i = 0; i < MAX_ROWS; i++) { struct Address *cur = &db->rows[i];

        if (cur->set) {
            Address_print(cur);
        }
    }
}

int main(int argc, char *argv[])
{
    if (argc < 3)
        die("USAGE: ex17 <dbfile> <action> [action params]");

    char *filename = argv[1];
    char action = argv[2][0];
    struct Connection *conn = Database_open(filename, action);
    int id = 0;

    if (argc > 3) id = atoi(argv[3]);
    if (id >= MAX_ROWS) die("There's not that many records.");

    switch (action) {
        case 'c':
            Database_create(conn);
            Database_write(conn);
            break;

        case 'g':
            if (argc != 4)
                die("Need an id to get");

            Database_get(conn, id);
            break;

        case 's':
            if (argc != 6)
                die("Need id, name, email to set");

            Database_set(conn, id, argv[4], argv[5]);
            Database_write(conn);
            break;

        case 'd':
            if (argc != 4)
                die("Need id to delete");

            Database_delete(conn, id);
            Database_write(conn);
            break;

        case 'l':
            Database_list(conn);
            break;
        default:
            die("Invalid action: c=create, g=get, s=set, d=del, l=list");
    }

    Database_close(conn);

    return 0;
}

Đoạn code tởm lợm trên có 213 dòng code thôi, thật ra đối với các bạn mới học, nó rất “tởm”, nhưng đối với các bạn đã đi làm hay chịu khó mày mò và học rất tốt về C rồi thì đoạn code này cũng khá bình thường. Đi làm gặp toàn module mấy ngàn dòng code. Mà một project lớn có cả trăm module.

Trong chương trình này, chúng tôi đã sử dụng một vài hàm mà bạn chưa bao giờ gặp để tạo ra một chương trình quản lý database cực kì đơn giản. Công việc của bạn (rất quan trọng), hãy đọc từng dòng code và giải thích mỗi dòng cho đến khi bạn hiểu hết. Và đây là một vài từ khóa bạn nên chú ý:
#define for constants tôi đã sử dụng một chức năng mới của C để khai báo hằng số MAX_DATAMAX_ROWS (thay vì dùng từ khóa const). #define cũng hoạt động trong CPP. Đây là một cách đáng tin cậy để tạo ra các giá trị hằng.

#define MAX_DATA 512

Nói cho compiler biết rằng, khi nào thấy MAX_DATA thì thay thế nó bằng 512. Và đây còn gọi là tiền xử lý (Preprocessor).

Fixed Sized Structs các bạn hãy xem struct Address, mặc dù nó chứa hằng số nhưng nó đã có kích thước cố định, và struct Database cũng vậy. Và các bạn có biết máy tính sẽ cấp cho mỗi struct trên bao nhieu byte không? Câu trả lời sẽ nằm trong một topic khác (về vấn đề padding trong struct).

die function to abort with an error trong chương trình quản lý database nhỏ này, để tránh gây ra lỗi phiền phức, tuy đây là chương trình nhỏ nếu có gây lỗi cũng không sao. Nhưng trong các chương trình lớn, việc gây ra các bug có thể rất nghiêm trọng, đặc biệt trong hệ thống nhúng, nhiều khi sẽ phá hủy phần cứng. Ở trong chương trình này, chúng tôi sử dụng hàm die để kết thúc chương trình khi một hàm nào đó sinh ra lỗi. Thật ra hàm die này sẽ in ra một dòng chữ (do chúng ta tự định nghĩa) và sau đó chương trình sẽ gọi hàm exit để thoát khỏi function gây lỗi.

errno and perror() for error reporting khi mà một hàm nào đó return một lỗi, thì cái lỗi đó THƯỜNG được đưa vào một biến “external” có tên là errno, và biến này sẽ nói cho chúng ta biết chuyện gì đã xảy ra. Và làm cách nào để có thể in lỗi này ra màn hình, dĩ nhiên là không dùng lệnh printf rồi. Chúng ta dùng hàm perror (print error) để in giá trị trong biến errno ra ngoài.

FILE function trong chương trình nhỏ này, chúng tôi sử dụng một số hàm mới như fopen, fread, fcloserewind để làm việc với file. Và các bạn cần tìm hiểu thêm về các hàm xử lý file này nhé. Và những hàm này nằm trong thư viện chuẩn của C.

nested struct pointers các bạn có thể thấy những cấu trúc khá phức tạp như sau &conn->db->rows[i]. Đây được gọi là con trỏ struct lồng nhau. Biểu thức trên có nghĩa là, lấy địa chỉ (bằng phép toán &) của: phần tử thứ i trong mảng rows (nhớ rằng mảng rows là mảng các phần tử struct, nó chứa một đống struct trong đó), rows trong struct db, db trong struc conn.

copying struct prototypes phần này được chỉ rõ nhất trong hàm database_delete, các bạn có thể thấy biến addr (có kiểu struc Address) trong hàm database_delete. Nó đang thiết lập các member trong struct là idset. Và sau đó sao chép dữ liệu vào phần tử thứ id của mảng rows. Trong C bạn có thể sử dụng phép gán như thế để gán một sruct này cho một struct khác.

processing complex arguments các bạn có thể thấy có những hàm có đối số truyền khá phức tạp, và những thứ như vậy, chúng ta sẽ phân tích nó sâu hơn ở các bài sau. Bài này các bạn chỉ cần hiểu sơ, chúng ta chỉ cần hiểu một chương trình thực sự là như thế nào.

converting strings to ints chúng tôi sử dụng hàm atoi để lấy string ở biến id lấy được trên command line và chuyển nó thành biến id interger. Hàm này dùng khá đơn giản.

allocating large data on the “heap” tất cả các con trỏ trong này chúng tôi sử dụng hàm malloc để bảo hệ điều hành cấp pháp cho chúng bộ nhớ và đây là một bộ nhớ khá lớn. Và chúng tôi sẽ giải thích chuyện này bên dưới.

NULL is 0 so boolean works NULL các bạn có thể hiểu là 0 nhé. if(!ptr) die(“fail!”) tương đương với if(ptr == NULL) die(“fail!”).

What You Should See

Bạn nên dành thời gian ra để test chương trình này. Và sau đó dùng valgrind để tiếp tục chạy và quan trọng là xác nhận lại chúng ta sử dụng bộ nhớ rất đúng.
Kết quả bạn nên nhìn thấy trên màn hình như sau

$ make ex17 
cc -Wall -g ex17.c -o ex17 
$ ./ex17 db.dat c 
$ ./ex17 db.dat s 1 zed zed@zedshaw.com 
$ ./ex17 db.dat s 2 frank frank@zedshaw.com 
$ ./ex17 db.dat s 3 joe joe@zedshaw.com 
$ 
$ ./ex17 db.dat l 
1 zed zed@zedshaw.com 
2 frank frank@zedshaw.com 
3 joe joe@zedshaw.com 
$ ./ex17 db.dat d 3 
$ ./ex17 db.dat l 
1 zed zed@zedshaw.com 
2 frank frank@zedshaw.com 
$ ./ex17 db.dat g 2 
2 frank frank@zedshaw.com 
$ 
$ valgrind --leak-check=yes ./ex17 db.dat g 2 
# cut valgrind output... 
$

Valgrind có thể cho chúng ta thấy các leaks memory. Các bạn hãy đọc và nghiên cứu các thông báo mà valgrind show ra.

Heap vs. Stack Allocation

Khi bạn lập trình với Python hay Ruby, bạn tạo các biến (variable) hay các đối tượng (object – khái niệm này trong lập trình hướng đối tượng OOP) mà không hề quan tâm nó nằm đâu trong bộ nhớ. Bạn không hề quan tâm là nó nằm trong stack hay là heap. Vậy stack và heap là cái gì mà chúng ta phải quan tâm tới nó?

Các bạn hãy nhớ rằng chúng ta đang học lập trình C, mà C là ngôn ngữ rất gần với phần cứng máy tính. Vậy khi làm việc với phần cứng, cái chúng ta đặt biệt phải quan tâm đó chính là việc quản lý bộ nhớ (memory managerment). Từ đó mới sinh ra 2 khái niệm stack và heap.

Heap rất dễ giải thích, nó là tất cả các vùng nhớ “dư” trong máy tính của bạn, khi bạn gọi hàm malloc, nghĩa là bạn đang truy cập vào heap, lúc này OS sẽ dành ra một khoảng nhớ nào đó nằm trong heap và trả về một con trỏ cho bạn, và con trỏ này trỏ tới vùng nhớ heap mà bạn mới được cấp. Và khi bạn dùng hàm free, thì OS sẽ lấy lại vùng nhớ vừa mới cấp. Nói nôm na là OS nó cho thuê xong nó lấy lại đó (khái niệm này gọi là giải phóng bộ nhớ). Nhiều khi bạn không giải phóng được, hay gặp vấn đề gì đó mà bộ nhớ heap không được giải phóng, thì chương trình sẽ bị “leak” memory. Và Valgrind là tool có thể giúp bạn xem xem bạn bị “leak” như thế nào.

Stack là một vùng nhớ đặt biệt, nó là nơi lưu các biến tạm mà mỗi hàm tạo ra trong đó và các đối số của hàm (argument). Các đối số (argument) của hàm sẽ được đẩy (pushed) vào stack, và sau đó nó được sử dụng bên trong hàm. Và stack la một cấu trúc dữ liệu theo kiểu “LIFO” nghĩa là last in first out (Tôi sẽ làm một bài về stack và heap đầy đủ hơn, trong phạm vi Learn C The Hard Way chỉ đề cập như vậy). Và sau khi một hàm thực hiện xong, các biến trong hàm sẽ bị xóa sạch để tránh việc leak memory.

Một cách cực kì dễ nhớ thế này: Nếu bạn khai báo biến mà không dùng malloc thì biến sẽ được lưu trên stack (trừ static và biến global – sẽ nằm trong topic khác).

Ba vấn đề hay gặp trong stack và heap như sau:
1. Khi bạn lấy một khối bộ nhớ từ malloc, dĩ nhiên các ô nhớ này sẽ nằm trong heap. Và chương trình sẽ trả về cho bạn một con trỏ để trỏ tới vùng nhớ này, nhưng con trỏ này lại nằm trong stack, và dĩ nhiên khi function kết thúc, con trỏ bị xóa khỏi stack nhưng trong heap thì vẫn còn, và bạn không thể kiểm soát được.
2. Bộ nhớ stack thông thường chỉ vỏn vẹn 1MB, cho nên khi bạn có quá nhiều dữ liệu trong stack, sẽ gặp một hiện tượng là “stack overflow”. Đó là lý do tại sao bạn nên dùng cấp pháp động (malloc) để sử dụng vùng nhớ heap.
3. Nếu bạn có một con trỏ trên stack và sau đó con trỏ này nhảy qua khỏi vùng nhớ hay return con trỏ từ một hàm, bạn sẽ nhận được một lỗi là “segmentation fault” vì dữ liệu thực ban đầu đã bị biến mất (stack).

Và khi kết thúc chương trình, OS sẽ xóa mọi thứ bạn đã tạo ra trong chương trình.

Advertisements

2 thoughts on “Exercise 17 Lập Trình C – Learn C The Hard Way

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s