Bài viết này nói về cách viết một bộ phân bổ bộ nhớ đơn giản trong C.
Chúng ta sẽ triển khai malloc(), calloc(), realloc() và free().
Đây là bài viết dành cho người mới bắt đầu, vì vậy tôi sẽ không giải thích chi tiết.
Bộ phân bổ bộ nhớ này sẽ không nhanh và hiệu quả, chúng ta sẽ không điều chỉnh bộ nhớ được phân bổ để căn chỉnh với ranh giới trang, nhưng chúng ta sẽ xây dựng một bộ phân bổ bộ nhớ hoạt động. Vậy là xong.
Trước khi bắt đầu xây dựng bộ phân bổ bộ nhớ, bạn cần phải quen thuộc với bố cục bộ nhớ của một chương trình. Một quy trình chạy trong không gian địa chỉ ảo của riêng nó, khác với không gian địa chỉ ảo của các quy trình khác. Không gian địa chỉ ảo này thường bao gồm 5 phần:
Phần văn bản: Phần chứa các lệnh nhị phân để bộ xử lý thực thi.
Phần dữ liệu: Chứa dữ liệu tĩnh được khởi tạo khác không.
BSS (Khối bắt đầu bằng ký hiệu): Chứa dữ liệu tĩnh được khởi
tạo bằng không. Dữ liệu tĩnh chưa được khởi tạo trong chương trình được khởi tạo 0 và nằm ở đây.
Heap: Chứa dữ liệu được phân bổ động.
Stack: Chứa các biến tự động, đối số hàm, bản sao của con trỏ cơ sở, v.v.
Như bạn có thể thấy trong hình, ngăn xếp và đống phát triển theo hướng ngược nhau. Đôi khi các phần dữ liệu, bss và đống được gọi chung là "phân đoạn dữ liệu", phần cuối của phân định bằng một con trỏ có tên là chương trình ngắt hoặc brk. Nghĩa là, brk trỏ đến phần cuối của đống.
Bây giờ nếu chúng ta muốn phân bổ thêm bộ nhớ trong đống, chúng ta cần yêu cầu hệ thống tăng brk. Tương tự như vậy, để giải phóng bộ nhớ, chúng ta cần yêu cầu hệ thống giảm brk. Giả sử chúng ta chạy Linux (hoặc hệ thống giống Unix), chúng ta có thể sử dụng lệnh gọi hệ thống sbrk() cho phép chúng ta thao tác chương trình ngắt.
Gọi sbrk(0) sẽ cung cấp địa chỉ hiện tại của chương trình ngắt.
Gọi sbrk(x) với giá trị dương sẽ tăng brk x byte, do đó phân bổ bộ nhớ.
Gọi sbrk(-x) với giá trị âm sẽ giảm brk x byte, do đó giải phóng bộ nhớ.
Khi thất bại, sbrk() trả về (void*) -1.
Thành thật mà nói, sbrk() không phải là người bạn tốt nhất của chúng ta trong năm 2015. Hiện nay có những lựa chọn thay thế tốt hơn như mmap(). sbrk() không thực sự an toàn cho luồng. Nó chỉ có thể tăng hoặc giảm theo thứ tự LIFO.
Nếu bạn thực hiện lệnh man 2 sbrk trên macbook, nó sẽ cho bạn biết:
Thành thật mà nói, sbrk() không phải là người bạn tốt nhất của chúng ta trong năm 2015. Hiện nay có những lựa chọn thay thế tốt hơn như mmap(). sbrk() không thực sự an toàn cho luồng. Nó chỉ có thể tăng hoặc giảm theo thứ tự LIFO.
Nếu bạn thực hiện lệnh man 2 sbrk trên macbook, nó sẽ cho bạn biết:
The brk and sbrk functions are historical curiosities left over from earlier days before the advent of virtual memory management.
Tuy nhiên, triển khai glibc của malloc vẫn sử dụng sbrk() để phân bổ bộ nhớ không quá lớn.[1]. Vì vậy, chúng ta sẽ tiếp tục với sbrk() cho trình phân bổ bộ nhớ đơn giản của mình.
1.malloc()
Hàm malloc(size) phân bổ size byte bộ nhớ và trả về một con trỏ đến bộ nhớ được phân bổ. malloc đơn giản của chúng ta sẽ trông như thế này:
void *malloc(size_t size)
{
void *block;
block = sbrk(size);
if (block == (void*) -1)
return NULL;
return block;
}
Trong đoạn mã trên, chúng ta gọi sbrk() với kích thước đã cho. Khi thành công, các byte kích thước được phân bổ trên heap.
Thật dễ dàng. Đúng không?
Phần khó khăn là giải phóng bộ nhớ này. Hàm free(ptr) giải phóng khối bộ nhớ được trỏ tới bởi ptr, khối này phải được trả về bởi lệnh gọi malloc(), calloc() hoặc realloc() trước đó. Nhưng để giải phóng một khối bộ nhớ, nhiệm vụ đầu tiên là phải biết kích thước của khối bộ nhớ cần giải phóng. Trong sơ đồ hiện tại, điều này là không thể vì thông tin kích thước không được lưu trữ ở bất kỳ đâu. Vì vậy, chúng ta sẽ phải tìm cách lưu trữ kích thước của khối được phân bổ ở đâu đó.
Hơn nữa, chúng ta cần hiểu rằng bộ nhớ heap mà hệ điều hành cung cấp là liền kề. Vì vậy, chúng ta chỉ có thể giải phóng bộ nhớ ở cuối heap. Chúng ta không thể giải phóng một khối bộ nhớ ở giữa cho hệ điều hành. Hãy tưởng tượng đống của bạn giống như một ổ bánh mì dài mà bạn có thể kéo dài và thu nhỏ ở một đầu, nhưng bạn phải giữ nó nguyên vẹn.
Để giải quyết vấn đề không thể giải phóng bộ nhớ không nằm ở cuối đống, chúng ta sẽ phân biệt giữa giải phóng bộ nhớ và giải phóng bộ nhớ.
Từ giờ trở đi, giải phóng một khối bộ nhớ không nhất thiết có nghĩa là chúng ta giải phóng bộ nhớ trở lại hệ điều hành. Nó chỉ có nghĩa là chúng ta giữ khối được đánh dấu là trống. Khối được đánh dấu là trống này có thể được sử dụng lại trong lệnh gọi malloc() sau đó. Vì bộ nhớ không nằm ở cuối đống không thể được giải phóng, nên đây là cách duy nhất để chúng ta tiến lên phía trước.
Bây giờ, chúng ta có hai thứ để lưu trữ cho mọi khối bộ nhớ được phân bổ:
1. kích thước
2. Một khối có trống hay không?
Để lưu trữ thông tin này, chúng ta sẽ thêm tiêu đề vào mọi khối bộ nhớ mới được phân bổ. Tiêu đề sẽ trông giống như thế này:
struct header_t {
size_t size;
unsigned is_free;
};
Ý tưởng rất đơn giản. Khi một chương trình yêu cầu kích thước byte bộ nhớ, chúng ta tính total_size = header_size + size và gọi sbrk(total_size). Chúng ta sử dụng không gian bộ nhớ này được trả về bởi sbrk() để phù hợp với cả header và khối bộ nhớ thực tế. Header được quản lý nội bộ và được ẩn hoàn toàn khỏi chương trình gọi.
Bây giờ, mỗi khối bộ nhớ của chúng ta sẽ trông như sau:
Chúng ta không thể hoàn toàn chắc chắn rằng các khối bộ nhớ được phân bổ bởi malloc của chúng ta là liền kề. Hãy tưởng tượng chương trình gọi có một sbrk() ngoại lai, hoặc có một phần bộ nhớ mmap() được đặt giữa các khối bộ nhớ của chúng ta. Chúng ta cũng cần một cách để duyệt qua các khối của mình để lấy bộ nhớ (tại sao phải duyệt? chúng ta sẽ biết khi xem xét việc triển khai free()). Vì vậy, để theo dõi bộ nhớ được phân bổ bởi malloc của chúng ta, chúng ta sẽ đặt chúng vào một danh sách được liên kết. Bây giờ tiêu đề của chúng ta sẽ trông như thế này:
struct header_t {
size_t size;
unsigned is_free;
struct header_t *next;
};
và danh sách liên kết các khối bộ nhớ như thế này:
Bây giờ, hãy gói toàn bộ cấu trúc header trong một union cùng với một biến stub có kích thước 16 byte. Điều này khiến header kết thúc ở một địa chỉ bộ nhớ được căn chỉnh thành 16 byte. Hãy nhớ rằng kích thước của union là kích thước lớn hơn của các thành viên của nó. Vì vậy, union đảm bảo rằng phần cuối của header được căn chỉnh theo bộ nhớ. Phần cuối của header là nơi khối bộ nhớ thực sự bắt đầu và do đó bộ nhớ được cung cấp cho người gọi bởi trình phân bổ sẽ được căn chỉnh thành 16 byte.
typedef char ALIGN[16];
union header {
struct {
size_t size;
unsigned is_free;
union header *next;
} s;
ALIGN stub;
};
typedef union header header_t;
Chúng ta sẽ có một con trỏ đầu và đuôi để theo dõi danh sách.
header_t *head, *tail;
Để ngăn hai hoặc nhiều luồng truy cập đồng thời vào bộ nhớ, chúng ta sẽ đặt một cơ chế khóa cơ bản. Chúng ta sẽ có một khóa toàn cục và trước mỗi hành động trên bộ nhớ, bạn phải có được khóa và sau khi hoàn tất, bạn phải giải phóng khóa.
pthread_mutex_t global_malloc_lock;
malloc của chúng ta hiện được sửa đổi thành:
void *malloc(size_t size)
{
size_t total_size;
void *block;
header_t *header;
if (!size)
return NULL;
pthread_mutex_lock(&global_malloc_lock);
header = get_free_block(size);
if (header) {
header->s.is_free = 0;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
total_size = sizeof(header_t) + size;
block = sbrk(total_size);
if (block == (void*) -1) {
pthread_mutex_unlock(&global_malloc_lock);
return NULL;
}
header = block;
header->s.size = size;
header->s.is_free = 0;
header->s.next = NULL;
if (!head)
head = header;
if (tail)
tail->s.next = header;
tail = header;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
header_t *get_free_block(size_t size)
{
header_t *curr = head;
while(curr) {
if (curr->s.is_free && curr->s.size >= size)
return curr;
curr = curr->s.next;
}
return NULL;
}
Để tôi giải thích đoạn mã:
Chúng tôi kiểm tra xem kích thước yêu cầu có bằng không không. Nếu có, thì chúng tôi trả về NULL.
Đối với kích thước hợp lệ, trước tiên chúng tôi lấy khóa. Chúng tôi gọi get_free_block() - nó duyệt qua danh sách được liên kết và xem liệu đã tồn tại khối bộ nhớ nào được đánh dấu là trống và có thể chứa kích thước đã cho hay chưa. Ở đây, chúng tôi áp dụng phương pháp first-fit để tìm kiếm danh sách được liên kết.
Nếu tìm thấy khối trống đủ lớn, chúng tôi sẽ chỉ cần đánh dấu khối đó là không trống, giải phóng khóa toàn cục, sau đó trả về một con trỏ đến khối đó. Trong trường hợp như vậy, con trỏ tiêu đề sẽ tham chiếu đến phần tiêu đề của khối bộ nhớ mà chúng tôi vừa tìm thấy bằng cách duyệt qua danh sách. Hãy nhớ rằng, chúng tôi phải ẩn sự tồn tại của tiêu đề đối với một bên ngoài. Khi chúng tôi thực hiện (tiêu đề + 1), nó sẽ trỏ đến byte ngay sau khi kết thúc tiêu đề. Đây cũng là byte đầu tiên của khối bộ nhớ thực tế, khối mà người gọi quan tâm. Điều này được ép kiểu thành (void*) và trả về.
Nếu chúng ta không tìm thấy một khối trống đủ lớn, thì chúng ta phải mở rộng heap bằng cách gọi sbrk(). Heap phải được mở rộng theo kích thước phù hợp với kích thước được yêu cầu cũng như tiêu đề. Để làm được điều đó, trước tiên chúng ta tính tổng kích thước: total_size = sizeof(header_t) + size;. Bây giờ, chúng ta yêu cầu HĐH tăng chương trình break: sbrk(total_size).
Trong bộ nhớ thu được từ HĐH, trước tiên chúng ta tạo không gian cho tiêu đề. Trong C, không cần phải ép kiểu void* thành bất kỳ kiểu con trỏ nào khác, nó luôn được thăng cấp một cách an toàn. Đó là lý do tại sao chúng ta không thực hiện rõ ràng: header = (header_t *)block;
Chúng ta điền tiêu đề này bằng kích thước được yêu cầu (không phải tổng kích thước) và đánh dấu là không rảnh. Chúng ta cập nhật con trỏ tiếp theo, head và tail để phản ánh trạng thái mới của danh sách được liên kết. Như đã giải thích trước đó, chúng ta ẩn tiêu đề khỏi trình gọi và do đó trả về (void*)(header + 1). Chúng ta đảm bảo rằng chúng ta cũng giải phóng khóa toàn cục.
2.free()
Bây giờ, chúng ta sẽ xem free() nên làm gì. free() trước tiên phải xác định xem khối cần giải phóng có ở cuối heap không. Nếu có, chúng ta có thể giải phóng nó cho OS. Nếu không, tất cả những gì chúng ta làm là đánh dấu nó là 'miễn phí', hy vọng có thể sử dụng lại sau.
void free(void *block)
{
header_t *header, *tmp;
void *programbreak;
if (!block)
return;
pthread_mutex_lock(&global_malloc_lock);
header = (header_t*)block - 1;
programbreak = sbrk(0);
if ((char*)block + header->s.size == programbreak) {
if (head == tail) {
head = tail = NULL;
} else {
tmp = head;
while (tmp) {
if(tmp->s.next == tail) {
tmp->s.next = NULL;
tail = tmp;
}
tmp = tmp->s.next;
}
}
sbrk(0 - sizeof(header_t) - header->s.size);
pthread_mutex_unlock(&global_malloc_lock);
return;
}
header->s.is_free = 1;
pthread_mutex_unlock(&global_malloc_lock);
}
Ở đây, trước tiên chúng ta lấy header của khối mà chúng ta muốn giải phóng. Tất cả những gì chúng ta cần làm là lấy một con trỏ nằm sau khối theo khoảng cách bằng kích thước của header. Vì vậy, chúng ta ép kiểu block thành một con trỏ header và di chuyển nó ra sau 1 đơn vị.
header = (header_t*)block - 1;
sbrk(0) cung cấp giá trị hiện tại của program break. Để kiểm tra xem khối cần giải phóng có ở cuối heap hay không, trước tiên chúng ta tìm phần cuối của khối hiện tại. Phần cuối có thể được tính là (char*)block + header->s.size. Sau đó, giá trị này được so sánh với program break.
Nếu thực tế là ở phần cuối, thì chúng ta có thể thu nhỏ kích thước của heap và giải phóng bộ nhớ cho OS. Trước tiên, chúng ta đặt lại các con trỏ head và tail để phản ánh sự mất mát của khối cuối cùng. Sau đó, lượng bộ nhớ cần giải phóng được tính toán. Đây là tổng kích thước của header và khối thực tế: sizeof(header_t) + header->s.size. Để giải phóng lượng bộ nhớ này, chúng ta gọi sbrk() với giá trị âm của giá trị này.
Trong trường hợp khối không phải là khối cuối cùng trong danh sách được liên kết, chúng ta chỉ cần đặt trường is_free của tiêu đề của nó. Đây là trường được get_free_block() kiểm tra trước khi thực sự gọi sbrk() trên malloc().
3.calloc()
Hàm calloc(num, nsize) phân bổ bộ nhớ cho một mảng gồm num phần tử, mỗi phần tử có nsize byte và trả về một con trỏ đến bộ nhớ được phân bổ. Ngoài ra, bộ nhớ được đặt thành số không.
void *calloc(size_t num, size_t nsize)
{
size_t size;
void *block;
if (!num || !nsize)
return NULL;
size = num * nsize;
/* check mul overflow */
if (nsize != size / num)
return NULL;
block = malloc(size);
if (!block)
return NULL;
memset(block, 0, size);
return block;
}
Ở đây, chúng ta thực hiện kiểm tra nhanh để tìm tràn số nhân, sau đó gọi malloc() của chúng ta,và xóa bộ nhớ được phân bổ thành tất cả các số không bằng cách sử dụng memset().
4.realloc()
realloc() thay đổi kích thước của khối bộ nhớ đã cho thành kích thước đã cho.
void *realloc(void *block, size_t size)
{
header_t *header;
void *ret;
if (!block || !size)
return malloc(size);
header = (header_t*)block - 1;
if (header->s.size >= size)
return block;
ret = malloc(size);
if (ret) {
memcpy(ret, block, header->s.size);
free(block);
}
return ret;
}
Ở đây, trước tiên chúng ta lấy tiêu đề của khối và xem khối đã có đủ kích thước để chứa kích thước được yêu cầu hay chưa. Nếu có, không cần làm gì cả.
Nếu khối hiện tại không có kích thước được yêu cầu, thì chúng ta gọi malloc() để lấy một khối có kích thước yêu cầu và di chuyển nội dung đến khối mới lớn hơn bằng memcpy(). Sau đó, khối bộ nhớ cũ được giải phóng.
Biên dịch và sử dụng bộ phân bổ bộ nhớ của chúng tôi. Chúng tôi sẽ biên dịch bộ phân bổ bộ nhớ của mình và sau đó chạy một tiện ích như ls bằng bộ phân bổ bộ nhớ của chúng tôi.
Để thực hiện điều đó, trước tiên chúng tôi sẽ biên dịch nó thành một tệp thư viện.
$ gcc -o memalloc.so -fPIC -shared memalloc.c
Các tùy chọn -fPIC và -shared đảm bảo đầu ra đã biên dịch có mã độc lập với vị trí và yêu cầu trình liên kết tạo ra một đối tượng được chia sẻ phù hợp với liên kết động.
Trên Linux, nếu bạn đặt biến môi trường LD_PRELOAD thành đường dẫn của một đối tượng được chia sẻ, tệp đó sẽ được tải trước bất kỳ thư viện nào khác. Chúng ta có thể sử dụng thủ thuật này để tải tệp thư viện đã biên dịch của mình trước, để các lệnh sau chạy trong shell sẽ sử dụng malloc(), free(), calloc() và realloc() của chúng ta.
$ export LD_PRELOAD=$PWD/memalloc.so
Hiện nay,
$ ls
memalloc.c memalloc.so
Đó là bộ phân bổ bộ nhớ của chúng ta phục vụ ls. In một số thông báo gỡ lỗi trong malloc() và tự mình xem nếu bạn không tin tôi.
Cảm ơn bạn đã đọc. Mọi bình luận đều được hoan nghênh. Vui lòng báo cáo lỗi nếu bạn tìm thấy bất kỳ lỗi nào.
Bây giờ, hãy gói toàn bộ cấu trúc header trong một union cùng với một biến stub có kích thước 16 byte. Điều này khiến header kết thúc ở một địa chỉ bộ nhớ được căn chỉnh thành 16 byte. Hãy nhớ rằng kích thước của union là kích thước lớn hơn của các thành viên của nó. Vì vậy, union đảm bảo rằng phần cuối của header được căn chỉnh theo bộ nhớ. Phần cuối của header là nơi khối bộ nhớ thực sự bắt đầu và do đó bộ nhớ được cung cấp cho người gọi bởi trình phân bổ sẽ được căn chỉnh thành 16 byte.