Cấp phát động
Cho tới giờ, mọi mảng ta khai báo đều có kích thước cố định viết sẵn trong mã, ví dụ
int arr[5];. Nhưng nhiều khi tới lúc chạy ta mới biết cần bao nhiêu phần tử: người
dùng nhập n sinh viên, đọc một tệp chưa rõ độ dài. Lời giải là cấp phát bộ nhớ
động (dynamic memory allocation): xin hệ điều hành cấp một vùng nhớ với kích thước
tuỳ ý ngay lúc chạy.
Hãy hình dung chương trình quản lý điểm cho một lớp học phần. Lớp có thể 30 sinh viên,
cũng có thể 120. Khai báo cứng int diem[200]; thì lớp nhỏ vẫn chiếm chỗ của 200 người,
mà lớp 250 người lại vỡ trận vì mảng không đủ. Kích thước cố định buộc ta phải đoán, mà
đoán thì hoặc thừa hoặc thiếu.
Thử ngay: xem cấp phát động chạy từng bước
Bấm ▶ Chạy (hoặc kéo thanh trượt) để theo dõi: con trỏ arr sống trên stack, còn
vùng mảng thật nằm trên heap. Khi giải phóng, vùng heap được đánh dấu đã trả lại. Hai khu
nhớ stack và heap là gì, xin và trả vùng nhớ bằng hàm nào, các mục bên dưới sẽ giải thích.
1#include <stdlib.h>2int main(void) {3 int n = 4;4 int *arr = malloc(n * sizeof(int));5 for (int i = 0; i < n; i++)6 arr[i] = i * i;7 free(arr);8 arr = NULL;9 return 0;10}
Khi nào cần cấp phát động
Mảng tĩnh đơn giản hơn và tự dọn dẹp, nên chỉ chuyển sang cấp phát động khi thật cần.
- Kích thước chỉ biết lúc chạy: do người dùng nhập, do đọc từ tệp, do một phép tính trước đó quyết định.
- Kích thước thay đổi khi đang chạy: danh sách càng đọc càng dài, phải nới rộng vùng nhớ.
- Dữ liệu cần sống lâu hơn hàm tạo ra nó: mảng cục bộ chết khi hàm kết thúc, vùng heap thì không.
- Dữ liệu quá lớn cho stack: stack thường chỉ vài megabyte, còn heap rộng hơn nhiều.
Stack và heap
Các biến cục bộ của hàm sống trong một khu gọi là stack, tự sinh ra khi vào hàm và tự mất khi hàm kết thúc. Vùng nhớ cấp phát động lại nằm trong một khu khác gọi là heap. Điểm mấu chốt: vùng trên heap không tự mất khi hàm kết thúc, ta phải tự trả lại khi dùng xong. Một con trỏ trên stack giữ địa chỉ của vùng dữ liệu thật trên heap.
malloc, calloc và free
Các hàm cấp phát nằm trong thư viện <stdlib.h>. Hàm cấp phát theo byte trả về địa chỉ
đầu vùng nhớ (một con trỏ), hoặc NULL nếu xin không được. Để xin chỗ cho một mảng số
nguyên có n phần tử, ta tính số byte bằng n nhân kích thước một phần tử.
#include <stdio.h>
#include <stdlib.h> // malloc, free
int main(void) {
int n = 4;
int *arr = malloc(n * sizeof(int)); // ask for n ints on the heap
if (arr == NULL) { // allocation may fail
printf("out of memory\n");
return 1;
}
for (int i = 0; i < n; i++)
arr[i] = i * i; // use it like a normal array
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
free(arr); // give the memory back
arr = NULL; // avoid dangling pointer
return 0;
}
Sau khi cấp phát thành công, ta dùng arr y như một mảng thường nhờ số học con trỏ.
Khi không cần nữa, hàm free trả vùng nhớ lại cho hệ thống. Gán con trỏ về NULL sau
đó là thói quen tốt để tránh lỡ dùng lại con trỏ đã giải phóng.
sizeof, size_t và con trỏ void
Có hai chi tiết đáng dừng lại ở dòng malloc(n * sizeof(int)). Thứ nhất, sizeof(int)
cho biết một số nguyên chiếm bao nhiêu byte trên máy đang chạy, thường là 4 nhưng không
phải lúc nào cũng vậy, nên viết sizeof(int) an toàn hơn gõ cứng con số 4. Kết quả của
sizeof có kiểu size_t, một số nguyên không dấu đủ lớn để đong đếm mọi kích thước bộ
nhớ; nhân n với nó cũng cho ra size_t, nhờ vậy phép tính số byte không bị âm và có
biên rộng ngay cả khi mảng lớn. Thứ hai, hàm cấp phát trả về kiểu void *, tức một địa
chỉ chưa gắn kiểu. Trong C, void * tự chuyển sang int * khi gán nên ta không bắt buộc
phải ép kiểu, và người ta thường khuyên đừng ép để khỏi vô tình che mất lỗi thiếu
#include <stdlib.h>. Điều cần nhớ là bản thân vùng nhớ chỉ là một dãy byte trơn; chính
kiểu con trỏ mới quyết định mỗi bước nhảy arr[i] dài bao nhiêu byte và đọc ra giá trị
theo kiểu nào.
Hàm calloc giống cấp phát theo byte nhưng thêm một việc: nó đặt toàn bộ vùng nhớ về
0. Dùng calloc khi bạn muốn mảng khởi đầu sạch sẽ bằng 0; dùng malloc khi bạn sẽ
ghi đè ngay nên không cần dọn trước.
Kiểm tra NULL không phải thủ tục cho vui
Nhiều bạn bỏ qua bước kiểm tra NULL vì nghĩ máy nhiều RAM nên xin không bao giờ trượt.
Nhưng khi số phần tử do người dùng nhập, chỉ cần gõ nhầm một số rất lớn là lời xin thất
bại và hàm cấp phát trả về NULL. Ghi vào một con trỏ NULL thì chương trình đổ ngay.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n = 1000;
int *a = calloc(n, sizeof(int)); // n elements, all set to 0
if (a == NULL) { // ALWAYS check
fprintf(stderr, "cannot allocate %d ints\n", n);
return 1;
}
printf("a[0] = %d, a[999] = %d\n", a[0], a[999]); // both are 0
free(a);
return 0;
}
Hàm calloc nhận hai đối số, số phần tử và kích thước một phần tử, rồi đặt toàn bộ vùng
nhớ về 0, nên a[0] và a[999] đều in ra 0. Với malloc, hai giá trị đó là rác.
realloc: đổi kích thước vùng đã cấp
Đôi khi cấp phát xong mới biết là thiếu chỗ, ví dụ đọc số từ bàn phím cho tới khi người
dùng dừng. Hàm realloc đổi kích thước một vùng đã cấp và giữ nguyên dữ liệu cũ.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int *a = malloc(3 * sizeof(int));
if (a == NULL) return 1;
for (int i = 0; i < 3; i++) a[i] = i + 1; // 1 2 3
int *tmp = realloc(a, 6 * sizeof(int)); // grow to 6
if (tmp == NULL) { free(a); return 1; } // old block still valid
a = tmp; // safe to overwrite now
for (int i = 3; i < 6; i++) a[i] = i + 1; // 4 5 6
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
free(a);
return 0;
}
Cái bẫy nằm ở con trỏ tạm tmp. Nếu realloc thất bại, nó trả về NULL nhưng vùng nhớ
cũ vẫn còn nguyên. Viết a = realloc(a, ...) thì khi thất bại, a bị ghi đè thành
NULL, địa chỉ vùng cũ mất luôn và không còn cách nào giải phóng: rò rỉ.
Khi cần nới rộng, realloc thử kéo dài ngay tại chỗ; nhưng nếu ngay sau vùng cũ đã có
dữ liệu khác chiếm chỗ thì không còn khoảng trống liền kề để lớn thêm. Gốc rễ nằm ở chỗ
heap bị phân mảnh: các vùng cấp phát nằm xen kẽ nhau, không có gì bảo đảm phía sau một
vùng luôn còn chỗ trống. Khi đó realloc buộc phải xin một vùng mới đủ lớn ở nơi khác,
chép toàn bộ dữ liệu cũ sang, giải phóng vùng cũ rồi trả về địa chỉ mới. Hệ quả trực
tiếp: mọi con trỏ hay địa chỉ phần tử bạn đã lưu từ vùng cũ lập tức thành con trỏ treo.
Vì thế sau realloc phải luôn dùng con trỏ mới mà nó trả về, và tuyệt đối không giữ lại
địa chỉ các phần tử lấy được trước lúc gọi.
malloc(size) xin size byte, nội dung là rác. calloc(n, size) xin n * size byte và
đặt tất cả về 0. realloc(p, size) đổi kích thước vùng mà p đang trỏ tới. Cả ba đều có
thể trả về NULL, và cả ba đều kết thúc bằng đúng một lần free.
Xem chạy thêm: realloc dời vùng, con trỏ cũ thành treo
Bản trace ở đầu bài minh hoạ malloc rồi free. Trace này minh hoạ realloc khi phải dời vùng
nhớ đi nơi khác: nó cấp một vùng mới, chép dữ liệu sang rồi giải phóng vùng cũ, nên mọi
con trỏ cũ lập tức thành con trỏ treo. Chỉ con trỏ mới mà realloc trả về mới còn hợp lệ.
1#include <stdlib.h>2int main(void) {3 int *a = malloc(2 * sizeof(int));4 a[0] = 1;5 a[1] = 2;6 int *old = a;7 int *tmp = realloc(a, 4 * sizeof(int));8 a = tmp;9 a[2] = 3;10 free(a);11 return 0;12}
Rò rỉ bộ nhớ
Nếu ta cấp phát mà quên giải phóng, vùng nhớ đó vẫn bị giữ nhưng không ai còn dùng được, vì con trỏ tới nó đã mất. Đó là rò rỉ bộ nhớ (memory leak). Một chương trình rò rỉ chạy càng lâu càng ngốn bộ nhớ, cuối cùng có thể làm chậm hoặc treo máy.
Mỗi lần cấp phát thành công phải tương ứng đúng một lần giải phóng. Quên giải phóng thì
rò rỉ; giải phóng hai lần cùng một con trỏ thì hỏng dữ liệu quản lý heap; dùng con trỏ
sau khi đã giải phóng thì kết quả khó lường. Gán NULL ngay sau khi giải phóng để
phòng.
Con trỏ treo
Con trỏ treo (dangling pointer) là con trỏ vẫn giữ một địa chỉ, nhưng vùng nhớ ở địa
chỉ đó đã bị giải phóng: sau free(p), biến p vẫn nằm trên stack và vẫn chứa con số
địa chỉ cũ. Nó nguy hiểm hơn NULL nhiều, vì dùng con trỏ NULL thì chương trình đổ
ngay nên ta biết mà sửa, còn dùng con trỏ treo thì chương trình có thể vẫn chạy, in ra dữ
liệu trông có vẻ đúng, rồi hỏng ở một chỗ khác vào một lúc khác.
- Quên
free: rò rỉ, chương trình chạy lâu thì ngốn dần bộ nhớ. - Gọi
freehai lần trên cùng một con trỏ (double free): hỏng cấu trúc quản lý heap. GánNULLsaufreegiúp tránh, vìfree(NULL)là hợp lệ và không làm gì cả. - Dùng sau khi giải phóng (use after free): đọc hoặc ghi qua con trỏ treo.
- Ghi quá biên: cấp
nphần tử nhưng ghi vàoa[n]. Chỉ số hợp lệ chỉ từ 0 tớin - 1. - Tưởng
sizeof(p)cho kích thước vùng heap. Nó chỉ cho kích thước bản thân con trỏ, thường 8 byte. Vùng heap không mang theo độ dài, bạn phải tự giữ biếnnbên cạnh.
Mảng hai chiều động
Ma trận m dòng n cột với m, n chỉ biết lúc chạy có hai cách dựng. Cách thứ nhất là
mảng con trỏ: cấp một mảng gồm m con trỏ, mỗi con trỏ lại trỏ tới một dòng gồm n số
nguyên. Truy cập tự nhiên bằng mt[i][j], nhưng giải phóng phải làm ngược thứ tự cấp
phát, từng dòng trước rồi mới tới mảng con trỏ.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int m = 2, n = 3;
int **mt = malloc(m * sizeof(int *)); // m row pointers
if (mt == NULL) return 1;
for (int i = 0; i < m; i++) {
mt[i] = malloc(n * sizeof(int)); // one row of n ints
if (mt[i] == NULL) return 1;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
mt[i][j] = i * n + j; // use it like a 2D array
for (int i = 0; i < m; i++) free(mt[i]); // free rows first
free(mt); // then the pointer array
return 0;
}
Cách thứ hai là làm phẳng: cấp một vùng duy nhất m * n số nguyên bằng
int *mt = malloc(m * n * sizeof(int));, rồi truy cập ô dòng i cột j qua công thức
mt[i * n + j]. Chỉ một lần cấp phát và một lần giải phóng nên ít cơ hội sai hơn hẳn,
tránh được cảnh quên giải phóng một dòng rồi rò rỉ mà không biết. Người mới học nên ưu
tiên cách này.
Bài tập thực hành
Bài tập 1: trung bình cộng của mảng cấp phát động
Cấp phát một mảng số nguyên có n phần tử với n do người dùng nhập. Nhập n số,
tính và in trung bình cộng. Nhớ kiểm tra kết quả cấp phát có phải NULL không, và giải
phóng trước khi kết thúc.
Lời giải chi tiết
Số phần tử chỉ biết lúc chạy, nên ta cấp phát động đúng n ô. Luôn kiểm tra NULL
ngay sau khi cấp phát vì việc xin bộ nhớ có thể thất bại. Cuối cùng giải phóng đúng một
lần để không rò rỉ.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n;
if (scanf("%d", &n) != 1) return 1; // check what scanf actually read
if (n <= 0) return 1; // n must be positive: we divide by it later
int *a = malloc(n * sizeof(int)); // n known only at run time
if (a == NULL) return 1; // allocation may fail
long sum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
printf("average = %.2f\n", (double)sum / n);
free(a); // release before exit
return 0;
}
Ý chính: cấp phát động cho phép kích thước tuỳ ý lúc chạy, kèm nghĩa vụ kiểm tra NULL
và giải phóng.
Bài tập 2: nhìn thấy rò rỉ bộ nhớ rồi sửa
Cho một hàm cấp phát một mảng nhưng không bao giờ giải phóng, vì vậy vùng nhớ bị rò rỉ mỗi lần gọi. Hãy chỉ ra dòng gây rò rỉ, rồi viết lại để hàm gọi nhận con trỏ và tự giải phóng sau khi dùng.
Lời giải chi tiết
Trong bản gốc, hàm cấp phát rồi trả về sau khi mất con trỏ, nên không còn cách nào giải phóng: đó là rò rỉ. Cách sửa là cho hàm trả về con trỏ vùng đã cấp, để hàm gọi sở hữu và giải phóng đúng lúc.
#include <stdio.h>
#include <stdlib.h>
// Leaky version (do NOT do this): the array is never freed.
// void tao(int n) { int *a = malloc(n * sizeof(int)); } // a is lost -> leak
int *tao(int n) {
int *a = malloc(n * sizeof(int)); // caller takes ownership
if (a == NULL) return NULL; // never write through a NULL pointer
for (int i = 0; i < n; i++) a[i] = i;
return a; // hand the pointer back
}
int main(void) {
int *a = tao(4);
if (a == NULL) return 1;
for (int i = 0; i < 4; i++) printf("%d ", a[i]);
printf("\n");
free(a); // caller frees -> no leak
return 0;
}
Ý chính: con trỏ tới vùng cấp phát phải được giữ lại để giải phóng; đánh mất nó là rò rỉ.
Bài tập 3: sao chép một mảng sang vùng heap mới
Viết hàm int *sao_chep(int a[], int n) cấp phát động một mảng mới n phần tử, sao
chép nội dung từ a sang rồi trả về con trỏ mảng mới. Trong main, gọi hàm, in mảng
sao chép và giải phóng nó. Chỉ rõ nếu quên giải phóng thì rò rỉ ở đâu.
Lời giải chi tiết
Hàm cấp phát một vùng heap mới rồi chép từng phần tử sang. Vùng này tách biệt với mảng gốc, sửa bản sao không ảnh hưởng bản gốc. Hàm gọi nhận con trỏ và có nghĩa vụ giải phóng; nếu quên, đúng vùng vừa cấp trong hàm sẽ rò rỉ.
#include <stdio.h>
#include <stdlib.h>
int *sao_chep(int a[], int n) {
int *b = malloc(n * sizeof(int)); // new region on the heap
if (b == NULL) return NULL;
for (int i = 0; i < n; i++) b[i] = a[i]; // copy each element
return b;
}
int main(void) {
int a[4] = {10, 20, 30, 40};
int *b = sao_chep(a, 4);
if (b == NULL) return 1;
for (int i = 0; i < 4; i++) printf("%d ", b[i]);
printf("\n");
free(b); // forgetting this leaks the region malloc'd inside sao_chep
return 0;
}
Ý chính: mỗi vùng cấp phát trong hàm phải có một con trỏ giữ lại và một lần giải phóng tương ứng ở hàm gọi.
Bài tập 4: ma trận động rồi tính tổng mỗi dòng
Nhập m và n, cấp phát một ma trận m nhân n bằng cách làm phẳng, nhập các phần tử
rồi in tổng của từng dòng. Giải phóng đúng một lần trước khi kết thúc.
Lời giải chi tiết
Ma trận làm phẳng chỉ là một mảng một chiều m * n phần tử, ô dòng i cột j nằm ở chỉ
số i * n + j. Nhờ vậy chỉ có một lần cấp phát và một lần giải phóng.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int m, n;
if (scanf("%d %d", &m, &n) != 2) return 1;
if (m <= 0 || n <= 0) return 1; // guard against bad sizes
int *mt = malloc((size_t)m * n * sizeof(int));
if (mt == NULL) return 1;
for (int i = 0; i < m * n; i++) scanf("%d", &mt[i]);
for (int i = 0; i < m; i++) {
long tong = 0;
for (int j = 0; j < n; j++) tong += mt[i * n + j]; // row i, col j
printf("Tong dong %d = %ld\n", i, tong);
}
free(mt);
return 0;
}
Ý chính: một vùng phẳng cộng phép quy đổi chỉ số i * n + j thay được mảng hai chiều, mà
chỉ cần một cặp cấp phát và giải phóng.
Bài tập 5: đọc số tới khi hết rồi nới mảng bằng realloc
Đọc các số nguyên từ bàn phím cho tới khi hết dữ liệu, lưu tất cả vào một mảng cấp phát
động. Vì chưa biết trước có bao nhiêu số, hãy khởi đầu với sức chứa nhỏ rồi gấp đôi bằng
realloc mỗi khi đầy. In lại toàn bộ số đã đọc rồi giải phóng đúng một lần.
Lời giải chi tiết
Ý tưởng là tách biệt sức chứa cap (đã cấp bao nhiêu ô) với số phần tử thực len (đã
dùng bao nhiêu ô). Khi len chạm cap, ta gấp đôi cap rồi gọi realloc, luôn hứng
vào con trỏ tạm để không mất vùng cũ nếu chẳng may thất bại.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int cap = 2, len = 0;
int *a = malloc(cap * sizeof(int)); // start small
if (a == NULL) return 1;
int x;
while (scanf("%d", &x) == 1) { // read until input ends
if (len == cap) { // full: grow the block
cap *= 2;
int *tmp = realloc(a, cap * sizeof(int));
if (tmp == NULL) { free(a); return 1; } // old block still valid
a = tmp; // adopt the new block
}
a[len++] = x;
}
for (int i = 0; i < len; i++) printf("%d ", a[i]);
printf("\n");
free(a);
return 0;
}
Ý chính: gấp đôi sức chứa giúp số lần gọi realloc ít đi hẳn, và luôn hứng kết quả
realloc vào con trỏ tạm để một lần thất bại không kéo theo rò rỉ vùng cũ.
Tự kiểm tra
Vì sao một con trỏ trên stack sống lâu hơn vùng heap nó từng trỏ tới?
Vì stack và heap là hai khu nhớ tách biệt. Con trỏ là biến cục bộ trên stack, hết hàm
mới mất. Vùng heap nó trỏ tới được giải phóng ngay khi ta gọi free. Sau lúc đó con
trỏ vẫn còn nhưng trỏ tới vùng không hợp lệ (con trỏ treo), nên ta gán nó về NULL.
Câu hỏi tự kiểm
- 1Khi realloc thất bại, điều gì đúng?
- 2Với con trỏ p trỏ tới một vùng heap n phần tử, sizeof(p) cho biết gì?
- 3calloc(n, sizeof(int)) khác malloc(n * sizeof(int)) ở điểm nào?
- 4Vì sao nên gán arr = NULL ngay sau free(arr)?
Tóm tắt
| Việc cần làm | Hàm hoặc thao tác | Điểm dễ sai |
|---|---|---|
| Xin bộ nhớ, không dọn | malloc(n * sizeof(int)) | nội dung là rác, ghi trước khi đọc |
| Xin bộ nhớ và đặt về 0 | calloc(n, sizeof(int)) | hai đối số, không phải một |
| Đổi kích thước | realloc(p, size) | phải hứng vào con trỏ tạm |
| Kiểm tra thất bại | so sánh với NULL | bỏ qua là mầm của lỗi đổ vỡ |
| Trả bộ nhớ về hệ thống | free(p) | đúng một lần cho mỗi lần cấp phát |
| Vô hiệu hoá con trỏ cũ | p = NULL; | quên thì còn con trỏ treo |
| Biết số phần tử | tự giữ biến n | sizeof(p) không cho biết điều này |
Heap không tự dọn: mọi lần cấp phát đều kèm nghĩa vụ giải phóng, và nghĩa vụ đó thuộc về ai giữ con trỏ. Con trỏ chỉ là một địa chỉ, nó không biết vùng nó trỏ tới dài bao nhiêu và còn hợp lệ hay không, nên chính bạn phải giữ lấy hai thông tin đó.
Vùng cấp phát động sống trên heap, không tự mất khi hàm kết thúc. Mỗi lần cấp phát
thành công phải đi với đúng một lần giải phóng, và giải phóng xong thì gán con trỏ về
NULL. Quên giải phóng là rò rỉ bộ nhớ.