Tự viết hàm malloc cho riêng mình
C
27
White

huydx viết ngày 14/03/2016

Mở đầu

Warning: bài viết khá dài, nên bạn hãy tranh thủ ra pha tách trà rồi vừa nhâm nhi vừa đọc nhé :D.

Để đọc hiểu bài viết này thì bạn đọc cần chỉ cần nắm rõ một chút cơ bản về lập trình C, trong bài viết sẽ không sử dụng bất kì kiến thức lập trình C cao siêu nào cả (vì thực ra mình cũng chỉ biết cực kì cơ bản về C :v), thế nên bạn hãy hoàn toàn yên tâm mà enjoy bài viết. Okey, đầu tiên chúng ta hãy bắt đầu từ những khái niệm cơ bản: thế nào là malloc.

Cơ bản

Hãy dượt qua lại một chút về malloc cho những bạn nào còn chưa nắm rõ: malloc là một hàm nằm trong bộ thư viện chuẩn của ngôn ngữ C, nhằm mục đích chính là để "cấp" một vùng nhớ với một kích cỡ bất kì cho tiến trình đang chạy. Vùng nhớ được cấp này sẽ nằm ở bộ nhớ heap. Nhiều bạn mới lập trình sẽ có thiên hướng "tưởng" rằng malloc là một hàm syscall của unix kernel, hay là một tính năng của ngôn ngữ C. Nhưng thực ra không phải, malloc chỉ là một hàm nằm trong thư viện chuẩn của C (chính xác là ở stdlib.h), và logic của malloc có thể hiểu được chỉ với một chút kĩ năng C cơ bản.

Tutorial này không nhằm mục đích giúp bạn viết một hàm malloc cực kì hiệu quả hay hỗ trợ multi-threaded, mà chỉ nhằm để bạn hiểu hơn về những gì nằm dưới hệ thống quản lý bộ nhớ mà bạn dùng hàng ngày. Tự viết hàm malloc là một best practice để hiểu thêm về memory, về unix, về quản lý bộ nhớ dưới một góc nhìn rất thú vị. Cụ thể hơn thông qua bài viết này chúng ta sẽ nắm được:

  • Heap memory
  • Linked list
  • brk và sbrk syscall trong unix

Để bắt đầu viết những dòng code đầu tiên cho hàm malloc của riêng bạn, đầu tiên bạn phải hiểu được: memory được quản lý thế nào trong một process.

Process memory

Mỗi process quản lý vùng nhớ của mình thông qua địa chỉ ảo (virtual address space), và vùng nhớ này sẽ được mapping với vùng nhớ thực trên RAM thông qua MMU (Memory management unit) và kernel. Vùng nhớ của process được chia nhỏ thành 2 vùng chính là StackHeap. Stack là vùng nhớ cố định thường được sử dụng cho các biến cục bộ, biến toàn cục..., còn Heap là vùng nhớ mà có thể cấp phát một cách mềm dẻo tại real time.
Trong bài này chúng ta sẽ nói đến Heap, bởi malloc chính là hàm dùng để cấp phát "thêm" bộ nhớ cho vùng nhớ này. Heap của một process sẽ được mô hình bởi hình dưới đây:

alt text

Vùng nhớ Heap là một vùng địa chỉ liên tiếp. Heap được chia thành 3 "giới hạn" (bound) chính (được thể hiện bằng những đường phân cách trên hình ở trên)

  • Điểm khởi đầu (starting point)
  • Điểm kết thúc (maximum limit, hay là rlimit: là giá trị qui định trong sys/resource.h, thể hiện vùng nhớ max có thể lấy được thông qua cấp phát động)
  • break point: điểm sử dụng, thể hiện việc bao nhiêu memory đã đang được process hiện tại sử dụng đến

Để code được malloc thì chúng ta chỉ cần biết 2 giá trị: địa chỉ vùng nhớ bắt đầu heap (starting point), và vị trí vùng nhớ của break point. Và để biết được 2 giá trị này, kernel cấp cho chúng ta 2 hàm syscall là brksbrk. Lưu ý lại với bạn đọc là chúng ta không thể thao tác với vùng nhớ được quản lý bằng kernel bằng việc "tay không bắt giặc" được, mà phải thông qua các hàm low level hơn được cung cấp bởi kernel.

brksbrk

brk và sbrk là 2 hàm dùng để thao tác với vùng nhớ heap ở mức kernel. Chúng ta hãy xem signature của chúng nhé:

int brk(const void *addr);
void* sbrk(intptr_t incr);

Cả 2 hàm này đều dùng để thao tác với "break position", bạn có thể hình dung nó như một cái rào chắn. Kernel cung cấp cho chúng ta bộ tool để thao tác với cái rào chắn đó. Mỗi lần cần cấp phát vùng nhớ mới cho process sử dụng, bạn sử dụng những hàm này để "nâng" cái rào chắn lên, nhằm báo cho kernel là: tao dùng đến đây nhé, nhớ đừng cho thằng khác đụng vào vùng nhớ của tao.

Cả 2 hàm đều có nhiệm vụ là "nâng rào chắn", tuy nhiên có chút khác nhau về interface: hàm brk sẽ đặt rào tại địa chỉ được truyền vào addr, còn hàm sbrk sẽ nâng rào lên thêm incr bytes kể từ vị trí hiện tại. Rõ ràng là hàm sbrk cho chúng ta một interface gần với hàm malloc hơn, tiện hơn, còn nếu sử dụng brk chúng ta sẽ phải tự tính toán địa chỉ nên sẽ mất công hơn. Do đó trong bài viết này chúng ta sẽ sử dụng sbrk là chính.

Vùng nhớ unmapped và vùng nhớ tự do

Trờ lại hình của vùng nhớ Heap ở trên, chúng ta thấy có 2 vùng nằm phía sau rào chắn là Unmapped RegionUnvailable Space. Nếu sử dụng phải phần đằng sau rào chắn thì chúng ta sẽ gặp phải lỗi bus error. Bạn có thể tìm hiểu thêm về lỗi này tại wiki.

Một điểm cần lưu ý nữa là vùng nhớ nói chung được kernel quản lý theo trang (Pages), tức là theo từng cụm 4096 bytes một sẽ là một trang (trên hầu hết các hệ thống hiện tại).

alt text

Ở hình trên chúng ta có thể thấy khi địa chỉ của break không nằm ở một vị trí chia hết cho 4096, thì hiển nhiên địa chỉ break sẽ nằm lơ lửng trong 1 page. Vậy sẽ có một "đoạn" bộ nhớ nằm từ vị trí break đến địa chỉ của page kế tiếp, và đoạn bộ nhớ đó có sử dụng được không? Thực tế là đoạn bộ nhớ đó có thể sử dụng được, và nó được gọi là vùng nhớ tự do. Vùng nhớ này chính là nguyên
nhân của rất nhiều loại bug khi bạn thao tác không chuẩn với pointer, khiến cho nó "nhảy" nhầm đến vùng nhớ tự do này.

Tự làm một hàm malloc đơn giản nhất

#include <sys/types.h>
#include <unistd.h>

void *malloc(size_t size) {
 void* p;
 p = sbrk(0);
 if (sbrk(size) == (void*)-1) return NULL;
 return p;
}

Đoạn code làm những điều khá đơn giản

  • Đầu tiên gọi sbrk(0) là để lưu lại địa chỉ của rào chắn hiện tại để trả về vị trí hiện tại của rào chắn vào biến p
  • Sau đó gọi sbrk(size) để nâng rào chắn thêm size bytes
  • Cuối cùng trả về vị trí của p để có thể sử dụng vùng nhớ vừa được cấp phát

Vậy với sbrk bạn đã có một hàm malloc đơn giản. Bạn tự hỏi, vậy thì malloc khác gì một wrapper của sbrk nhỉ? Có gì thú vị ở đây?
Thực ra đây chỉ là một implementation đơn giản nhất có thể thôi. Malloc khó ở chỗ khi bạn allocate nhiều vùng nhớ với nhiều size khác nhau, một cách liên tục, làm thế nào để tận dụng bộ nhớ mà không bị phân mảnh, với tốc đọ cao nhất. Trong bài viết tiếp theo mình sẽ viết về điều đó, các bạn nhớ đón xem :D.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

115 bài viết.
855 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
135 8
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết hơn 1 năm trước
135 8
White
109 14
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết gần 3 năm trước
109 14
White
86 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết hơn 2 năm trước
86 10
Bài viết liên quan
White
3 1
Chú ý: Bài viết này trình bày chủ yếu cho CentOS 64 bit, tuy nhiên ý tưởng có thể áp dụng cho các hệ điều hành khác. Cuối bài có ghi chú cho Ubunt...
Ngoc Dao viết gần 2 năm trước
3 1
White
17 2
Gần đây tôi có dịp đụng vào CMake, nên có tìm hiểu một chút về nó. Hy vọng có ích cho anh em. Nó cung cấp tính năng sinh ra Makefile một cách hiệu...
Phùng Văn Tú viết hơn 2 năm trước
17 2
White
6 0
Xử lí song song từ xa xưa cho đến gần đây là lãnh vực cao cấp hầu như chỉ dành cho các nhà khoa học. Có ít nhất 2 nguyên nhân: Xử lí song song đòi...
Ngoc Dao viết gần 2 năm trước
6 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
115 bài viết.
855 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!