Các kiến thức cơ bản về hệ thống
Thư viện glibc trong Linux cung cấp cho chúng ta bốn hàm cơ bản để quản lý bộ nhớ động, ba trong số đó là các hàm cấp phát bộ nhớ, hàm còn lại là giải phóng bộ nhớ- Hàm void *malloc(size_t size) nhận đầu vào số byte cần cấp phát và trả lại vùng nhớ được cấp phát. Nếu không tìm thấy vùng nhớ thỏa mãn độ dài cần cấp phát malloc sẽ trả về NULL
- Hàm void *calloc(size_t nmemb, size_t size ) sẽ cấp phát bộ nhớ cho một mảng nmemb*size và trả về con trỏ tới vùng nhớ được cấp phát, nhớ rằng mặc dù cấp phát bộ nhớ cho một mảng các phần tử nhưng nó vẫn là một vùng nhớ liên tục trong heap, vùng nhớ này được ghi giá trị 0 trên toàn vùng trước khi trả về
- Hàm void *realloc(void *ptr, size_t size) sẽ thay đổi số byte được cấp phát ở ptr và trả lại một vùng nhớ được cấp phát có độ dài size và có nội dung như là vùng nhớ ở ptr. Vùng nhớ được trả lại bởi realloc có thể chính là ptr trong trường hợp các vùng xung quanh ptr có thể đủ khả năng cung cấp một vùng dài hơn độ dài size được yêu cầu trong realloc. Nếu ptr truyền vào là NULL realloc sẽ tương đương malloc(size)
- Hàm void free(void *ptr) sẽ giải phóng bộ nhớ tại địa chỉ ptr, vùng nhớ đó có thể được tái cấp phát ở hàm malloc/calloc/realloc. Hàm free không trả về
Trong các hệ thống yêu cầu hiệu năng cao như các hệ thống
thời gian thực hoặc datapath (data plane) của các tiến trình, việc cấp phát và
giải phóng bộ nhớ được yêu cầu rất cao về thời gian xử lý. Một sự hiểu biết tường
minh về cách hệ thống cấp phát/giải phóng bộ nhớ động là một nhu cầu thiết yếu.Bài
viết này sẽ cung cấp một giải pháp cấp phát và giải phóng bộ nhớ động để người
đọc có thể hình dung được cách thức cấp phát/giải phóng bộ nhớ động trong hệ thống
Linux
Bộ nhớ tiến trình
Mỗi tiến trình trong hệ thồng Linux có một không gian
địa chỉ gọi là bộ nhớ ảo, không gian địa chỉ này sẽ được dịch thành vùng nhớ thực
trong RAM (physical address) hoặc trên đĩa (swapped disk) dựa vào một phần cứng
là MMU. Không gian địa chỉ này được tổ chức làm 4 vùng, vùng text (read-only)
chứa mã lệnh của tiến trình, vùng data segment được khởi tạo chứa các biến toàn
cục (global) và biến cục bộ được khởi tạo, vùng data segment không được khởi tạo
chứa các biến toàn cục và biến cục bộ không được khởi tạo, vùng stack bao gồm
các stack frame, mỗi stack frame được cấp phát mỗi khi có một hàm được gọi và một
vùng cấp phát bộ nhớ động gọi là heap. Đỉnh của vùng heap được cấp phát được gọi
là program break
Program break và page boundary
Thực tế khi nhân hệ thống cấp phát bộ nhớ cho tiến
trình, nó sẽ nạp cả một trang nhớ (page size), trong hệ điều hành Linux, một
page size có độ dài 4096 bytes, việc truy cập vào một trang nhớ chưa được nạp
(nằm trong vùng Unmapped region) sẽ khiến cho nhân Linux gửi một signal SIGSEGV
tới tiến trình làm tiến trình mặc định dừng lại. Tuy nhiên, đối với trang nhớ
đang chứa địa chỉ của program break, nó đã được nạp do đó tiến trình có thể
truy nhập bình thường, program break chia trang nhớ này thành hai phần, thuộc
vùng các Mapped region và Unmapped Region. Việc truy nhập vào vùng Unmapped
Region (thường gây ra do các lỗi buffer overflow) ,nhưng chương trình vẫn chạy
bình thường tại thời điểm truy nhập có thể gây ra những lỗi trầm trọng hơn và
khó tìm ra nguyên nhân gốc ban đầu, đặc biệt trong các hệ thống multi-core,
multi-thread khi một buffer lỗi ban đầu được luôn chuyển qua quá nhiều module
Để hiểu được hoạt động của các hàm cấp phát/giải phóng
bộ nhớ chúng ta cần phải biết về vị trí bộ nhớ heap bắt đầu hay vị trí của
program break, và chúng ta cũng phải có khả năng di chuyển program break. Các
hoạt động này được hệ điều hành Linux cung cấp thông qua các lời gọi hệ thống
là brk và sbrk
Hàm hệ thống và các nguyên tắc cơ bản
Các hàm hệ thống được cung cấp trong
thư viện glibc cho phép thay đổi program break
int brk(void * addr)
void *sbrk(intptr_t *increment)
Hàm brk sẽ đặt địa chỉ của program
break tới addr và trả về 0 nếu thành công và trả về -1 nếu lỗi. Biến errno được
thiết lập để nhận ra loại lỗi mà hàm gặp phải
Hàm sbrk tăng/giảm program break một
lượng tuyệt đối là increment, trong Linux hàm trả về địa chỉ của program break
trước đó, nếu truyền 0 vào sbrk chúng ta sẽ có địa chỉ của program break hiện tại
Như vậy chúng ta có các nguyên tắc cơ bản khi thiết kế
hàm cấp phát/giải phóng bộ nhớ. Đó là khi cấp phát chúng ta gọi sbrk để tăng
program break và khi giải phóng thì gọi hàm brk để kéo program break về vị trí
ban đầu
Tổ chức bộ nhớ heap
Việc thiết kế các hàm cấp phát và
giải phóng đòi hỏi một số các yêu cầu khác ngoài yêu cầu cung cấp/giải phóng bộ
nhớ cho tiến trình
- Hàm cấp phát sẽ cấp phát ra một lượng bộ nhớ đã được align tới kích thước của integer (4 bytes) so với yêu cầu đầu vào
- Hàm cấp phát /giải phóng bộ nhớ bộ nhớ phải đủ nhanh, phải trả về lập tức, tránh bất kỳ hình thức nào khiến cho tiến trình phải ngủ hay chờ đợi một điều kiện nào đó.
- Hàm cấp phát/giải phóng bộ nhớ tránh gọi các hàm hệ thống brk và sbrk nhiều nhất có thể, vì lời gọi hệ thống sẽ dẫn đến context-switching từ không gian người dùng (user space) về không gian nhân (kernel space) và ngược lại
- Hàm cấp phát phải có khả năng resize lại vùng nhớ đã được cấp phát và khả năng tái cấp phát một vùng nhớ đã được giải phóng
- Hàm giải phóng bộ nhớ phải có khả năng hợp nhất các vùng nhớ đã được giải phóng nằm lân cận nhau tạo thành một vùng nhớ lớn, điểm này giúp giảm thiểu việc phân mảnh bộ nhớ tối đa
- Hàm giải phóng phải có khả năng dò ra một số lỗi cơ bản như free NULL pointer hay double free
- Hệ thống có khả năng hỗ trợ tìm các lỗi về bộ nhớ buffer overflow, dangling pointer hay memory leak
Để đáp ứng các yêu cầu trên thì một vùng quản lý thông
tin bộ nhớ được tạo ra cho mỗi vùng nhớ được cấp phát (gọi là meta-data), nghĩa
là mỗi vùng nhớ được cấp phát sẽ được cấp nhiều hơn để chứa thông tin quản lý
và thông tin này sẽ nằm phía trước mỗi con trỏ được trả về ở hàm cấp phát
Và hệ thống sẽ sử dụng một cấu trúc dữ liệu dạng danh
sách liên kết (linked list) để tổ chức các thông thông tin này. Cấu trúc dữ liệu
cho vùng meta-data như sau
struct s_block
{
unsigned int magic;
size_t size;
t_block next;
t_block prev;
int free;
void *ptr;
char data[1];
};
{
unsigned int magic;
size_t size;
t_block next;
t_block prev;
int free;
void *ptr;
char data[1];
};
Vì chúng ta sẽ luôn sử dụng cấu
trúc dữ liệu này ở dạng con trỏ, cho nên chúng ta định nghĩa kiểu con trỏ
t_block của cấu trúc dữ liệu meta-data
Ý nghĩa các trường của meta-data
như sau:
o
Trường
magic luôn mang một giá trí cố định, sử dụng cho mục đích debug các lỗi liên
quan tới buffer overflow, lưu ý rằng trường này luôn ở vị trí đầu tiên của cấu
trúc(trong trường hợp muốn sửa đổi cấu trúc, thêm vào các trường khác cho các mục
đích khác nhau)
o
Trường
size lưu độ dài của vùng data được cấp phát
o
Hai
trường con trỏ next và prev trỏ tới cấu trúc meta-data tiếp theo và trước đó
o
Trường
free sử dụng để mô tả vùng nhớ đó đã được cấp phát hay chưa
o
Trường
ptr trỏ tới vùng nhớ được cấp phát cho tiến trình
o
Trường
data giống như ptr nhưng dùng để truy nhập dữ liệu người dùng (dữ liệu tiến
trình), trường data này luôn nằm ở vị trí cuối cùng của cấu trúc, trường này
không thuộc về dữ liệu thông tin quản lý khi địa chỉ của nó luôn trùng với địa
chỉ của byte đầu tiên cấp phát cho người dùng, do đó trường này được loại bỏ
khi tính toán độ dài của cấu trúc quản lý
#define BLOCK_SIZE offsetof(struct s_block, data)
Các yêu cầu cấp phát luôn phải được
align tới độ dài là bội của integer (4 bytes trong hệ thống 32bits và 8bytes
trong hệ thống 64bits) hiện tại chúng ta chỉ xem xét ở 32bit
#define
align4(x) (((((x) - 1) >> 2)<<2)+4)
Thiết kế hàm malloc
Hàm malloc được tiến hành theo giải
thuật first-fit, nghĩa là vùng nhớ đầu tiên thỏa mãn độ dài của yêu cầu cấp
phát sẽ được trả về, hàm sẽ hoạt động trong các user-case sau :
Ở lần gọi đầu tiên, malloc sẽ gọi tới
sbrk để lấy bộ nhớ từ heap, khi vùng nhớ này được trả về nó sẽ được tổ chức một
meta-data để quản lý nó, vùng này sẽ được đưa vào một danh sách liên kết và được
đánh dấu là đã được cấp phát
Nếu malloc không phải ở lần gọi đầu
tiên, nó sẽ tìm trong danh sách liên kết quản lý các meta-data hiện tại và tìm
một vùng nhớ có độ dài phù hợp, vùng nhớ phù hợp là vùng nhớ có độ dài lớn hơn
độ dài của cấu trúc meta-data cộng với độ dài của yêu cầu cấp phát sau khi đã
được align
Nếu nó tìm thấy một vùng nhớ phù hợp
trong danh sách liên kết mà độ lớn của vùng nhớ này lớn hơn độ lớn yêu cầu,
vùng nhớ này sẽ được tái tổ chức thành hai vùng, một vùng có độ dài bằng với độ
dài yêu cầu, sẽ được đánh dấu là đã được cấp phát và một vùng có độ dài là phần
còn lại, được đánh dấu là chưa được cấp phát và thêm vào danh sách liên kết của
các meta-data
Nếu nó không tìm thấy vùng nhớ nào
phù hợp trong danh sách liên kết, nó sẽ tìm tới sbrk và mở rộng heap để có được
vùng nhớ có độ dài phù hợp. Tất nhiên vùng nhớ mới này cũng sẽ được tổ chức một
meta-data để quản lý và thêm vào danh sách liên kết các meta-data (meta-data list)
Hàm extend_heap để cấp phát một vùng nhớ mới và tổ chức
meta-data cho nó
t_block extend_heap(t_block last, size_t s)
{
void *sb;
t_block b;
b = sbrk(0);
sb = sbrk(BLOCK_SIZE + s);
if(sb == NULL)
return NULL;
b->size = s;
b->next = NULL;
b->prev = last;
b->ptr = b->data;
if(last)
last->next = b;
b->free = 0;
return b;
}
Chúng ta biết rằng hàm hệ thống
sbrk truyền vào giá trị 0 sẽ trả về địa chỉ program break hiện tại, và đó cũng
chính là vùng nhớ mới được cấp phát sau khi program break đã được dịch đi một
khoảng BLOCK_SIZE + độ dài vùng nhớ yêu cầu, vùng nhớ mới được cấp phát này sẽ
được tổ chức vào meta-data list dựa vào phần tử last hiện đã nằm trong
meta-data list
Hàm find_block duyệt toàn bộ
meta-data list và tìm một vùng nhớ có độ dài phù hợp
t_block find_block(t_block *last, size_t size)
{
t_block b=base;
while(b && !(b->free && b->size >= size))
{
*last = b;
b = b->next;
}
return b;
}
Hàm split_block phân chia một vùng nhớ lớn đã được tổ
chức trong meta-data list thành hai vùng nhỏ hơn, một vùng có độ dài bằng với độ
dài của yêu câu cấp phát và vùng có độ dài còn lại, hai vùng này sẽ đều được
đưa tới meta-data list
void split_block(t_block b, size_t s)
{
t_block new;
new = (t_block)(b->data + s);
new->magic = MAGIC_NUM;
new->size = b->size - s - BLOCK_SIZE;
new->next = b->next;
new->prev = b;
new->free = 1;
new->ptr = new->data;
b->size = s;
b->next = new;
if(new->next)
new->next->prev = new;
}
Một block sau khi split như sau:
Từ các hàm con đã đầy đủ, ta có hàm malloc, chúng ta
dùng con trỏ toàn cục base để đánh dấu lần đầu tiên malloc được goi đồng thời
đánh dấu vị trí đỉnh của vùng nhớ heap, sau có thể được sử dụng để thống kê
void *tmalloc(size_t size)
{
t_block b, last;
if(size == 0)
return NULL;
size_t s = align4(size);
if(base)
{
last = base;
b = find_block(&last, s);
if(b)
{
if(b->size - s >= (BLOCK_SIZE + 4))
split_block(b,s);
b->free = 0;
}
else
{
b = extend_heap(last, s);
if(!b)
return NULL;
}
}
else
{
b = extend_heap(NULL, s);
if(!b)
return NULL;
base = b;
}
return b->data;
}
Thiết kế hàm free
Hàm free ngoài chức năng giải phóng bộ nhớ, dịch ngược
program break về đỉnh của heap, free còn phải có khả năng hợp nhất các vùng nhớ
nhỏ đã được giải phóng trong meta-data list để tạo thành một vùng nhớ lớn hơn.
Để làm được điều này mỗi khi free được gọi nó sẽ kiểm tra các vùng lân cận (phía
trước và phía sau) của nó để hợp nhất thành một vùng lớn hơn
t_block get_block(void *p)
{
return p-= BLOCK_SIZE;
}
int valid_addr(void *p)
{
if(base)
{
if(p > base && p < sbrk(0))
{
return (p == (get_block(p))->ptr);
}
}
return 0;
}
void tfree(void *p)
{
t_block b;
if(valid_addr(p))
{
b = get_block(p);
b->free = 1;
if(b->prev && b->prev->free)
b = fusion(b->prev);
if(b->next)
fusion(b);
else
{
if(b->prev)
b->prev->next = NULL;
else
base = NULL;
brk(b);
}
}
}
Trước khi hàm free giải phóng bộ nhớ
trở lại, nó sẽ tiến hành kiểm tra vùng nhớ được yêu cầu giải phóng có hợp lệ
hay không, vùng nhớ đó cần phải nằm trong Mapped region, tức là trong khoảng từ
program break hiện tại tới địa chỉ base ở lần đầu cấp phát. Hàm free sẽ tìm lại
thông tin của vùng nhớ được giải phóng. Tại đây nếu cần thiết free có tiến hành
rất nhiều các phương pháp kiểm tra vùng nhớ dựa vào thông tin quản lý, các lỗi
liên quan tới vùng nhớ hầu hết có thể tìm được ở đây, các lỗi phổ biến là
buffer overflow, memory leak, dangling pointer, memory corruption, free
unexpected area, double free. Tôi sẽ trình bày phương pháp phát hiện và sửa các
lỗi này sử dụng thông tin quản lý bộ nhớ trong bài sau
Trở lại hàm free, khi một vùng nhớ
đã được giải phóng, nếu vùng nhớ trước nó cũng là một vùng nhớ đã được giải
phóng, free sẽ sử dụng hàm fusion để hợp nhất hai vùng nhớ lại.
t_block fusion(t_block b)
{
if(b->next && b->next->free)
{
b->size += BLOCK_SIZE + b->next->size;
b->next = b->next->next;
if(b->next)
b->next->prev = b;
}
return b;
}
Khi đó thông tin quản lý vùng nhớ được hợp nhất sẽ nằm
ở vùng nhớ phía trước
Tiếp theo hàm free
sẽ tìm kiếm ở phía trước vùng nhớ vừa được hợp nhất, hoặc vùng nhớ được yêu cầu
giải phóng để tìm xem nó có phải là vùng nhớ đã được giải phóng không. Tại sao ở
đây free không tiếp tục tìm về phía sau nó. Đơn giản là vì giải thuật của free
cho phép tất cả các vùng nhớ phía sau đã được hợp nhất lại trước khi nó được gọi.
Do đó tại điểm này nó chỉ cần tìm về phía trước, nếu vùng nhớ phía trước cũng
là vùng nhớ đã được giải phóng, free sẽ gọi fusion lần nữa để hợp nhất chúng lại.
Tại thời điểm này
free sẽ xem xét vùng nhớ được yêu cầu giải phóng hoặc vùng nhớ hợp nhất có phải
là vùng nhớ nằm ở vị trí cuối cùng trong meta-data list hay không (kiểm tra con
trỏ next của nó), nếu nó là vùng nhớ nằm ở vị trí cuối cùng thì địa chỉ kết
thúc của nó sẽ là program break, và vì nó đã được giải phóng cho nên cần phải
kéo program break trở lại, free sẽ dùng hàm hệ thống brk để kéo program break
trở lại trước địa chỉ chứa thông tin quản lý vùng nhớ đó, vùng nhớ đó đồng thời
cũng sẽ được xóa khỏi meta-data list , và nếu như không còn vùng nhớ nào trong
meta-data list, con trỏ base sẽ được đưa về NULL (xóa meta-data list).
Giải thuật hàm
free như sau:
Thiết kế hàm calloc
Hàm calloc chính
là hàm malloc nhưng giá trị trên toàn vùng được cấp ra là 0
void *tcalloc(size_t number, size_t size)
{
size_t *new;
size_t s4, i;
new = tmalloc(number*size);
if(new)
{
s4 = align4(number*size) << 2;
for(i=0; i<s4; i++)
new[i] = 0;
}
return new;
}
Thiết kế hàm realloc
Hàm realloc resize
lại vùng nhớ đã được cấp phát
void *trealloc(void *p, size_t size)
{
size_t s;
t_block b, new;
void *newp;
if(!p)
return tmalloc(size);
if(valid_addr(p))
{
s = align4(size);
b = get_block(p);
if(b->size >= s)
{
if(b->size -s >= (BLOCK_SIZE + 4))
split_block(b,s);
}
else
{
if(b->next && b->next->free
&& (b->size + BLOCK_SIZE + b->next->size) >= s)
{
fusion(b);
if(b->size - s >= (BLOCK_SIZE + 4))
{
split_block(b,s);
}
}
else
{
newp = tmalloc(s);
if(!newp)
return NULL;
new = get_block(newp);
copy_block(b, new);
tfree(p);
return newp;
}
}
return p;
}
return NULL;
}
Trước hết, nếu con
trỏ truyền vào là NULL, hàm realloc sẽ hoạt động như hàm malloc. Nếu không,
realloc giống như free, nó sẽ kiểm tra tính hợp lệ của vùng nhớ được truyền
vào, sau đó realloc sẽ xem xét kích thước resize nếu nhỏ hơn vùng nhớ được
resize, recalloc đơn giản sẽ chỉ split vùng nhớ đó theo kích thước mới và trả về,
nếu kích thước resize lớn hơn vùng nhớ được resize, calloc sẽ xem xét xung
quanh vùng nhớ được resize có các vùng đã được giải phóng không, nếu có,
realloc sẽ hợp nhất các vùng này lại và xem độ dài vùng hợp nhất có thỏa mãn
không, nếu thỏa mãn lớn hơn kích thước cần resize, nó sẽ được split thành kích
thước resize và trả về. Ngược lại nếu không thỏa mãn nó sẽ dùng malloc để cấp
phát vùng nhớ mới, copy nội dung vùng nhớ cũ sang và giải phóng vùng nhớ cũ
Như vây trong bài viết này chúng ta đã tìm hiểu cách thức quản lý bộ nhớ ảo trong hệ điều hành Linux và thiết kế của các hàm cấp phát/giải phóng bộ nhớ cơ bản. Trong bài viết tới tôi sẽ đưa ra các đánh giá về hiệu năng, các phương pháp tìm và sửa lỗi bộ nhớ
và đánh giá các môi trường hoạt động khác nhau như 32bit/64bit,
multi-thread/multi-core
Toàn bộ mã nguồn của framework các bạn có thê download tại GitHub của Nhã Uyên Education
https://github.com/nhauyeneducation/linux_systemtraining
Tin học Nhã Uyên là một tổ chức thành lập với mục tiêu đào tạo kỹ sư lập trình hệ thống, kỹ sư lập trình nhúng và kỹ sư lập trình mạng trên nền tảng hệ điều hành Linux/Unix tại Việt Nam.
Mời các bạn vào Facebook của Tin học Nhã Uyên tại
https://www.facebook.com/tinhocnhauyen/ để theo dõi các bài viết kỹ thuật chất lượng tiếp theo của Tin học Nhã Uyên. Xin trân trọng cảm ơn các bạn
Toàn bộ mã nguồn của framework các bạn có thê download tại GitHub của Nhã Uyên Education
https://github.com/nhauyeneducation/linux_systemtraining
Tin học Nhã Uyên là một tổ chức thành lập với mục tiêu đào tạo kỹ sư lập trình hệ thống, kỹ sư lập trình nhúng và kỹ sư lập trình mạng trên nền tảng hệ điều hành Linux/Unix tại Việt Nam.
Mời các bạn vào Facebook của Tin học Nhã Uyên tại
https://www.facebook.com/tinhocnhauyen/ để theo dõi các bài viết kỹ thuật chất lượng tiếp theo của Tin học Nhã Uyên. Xin trân trọng cảm ơn các bạn
Comments
Post a Comment