ADVERTISEMENT
ADVERTISEMENT

Tìm hiểu cách cấp phát bộ nhớ cho quá trình trong hệ điều hành unix.

ADVERTISEMENT

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ề

Việc cấp phát bộ nhớ trong vùng nhớ
heap được tiến hành theo giải thuật first-fit, nghĩa là vùng nhớ nào thỏa mãn
yêu cầu độ dài đầu tiên sẽ được trả về. Ưu điểm của phương pháp này là tối ưu về
thời gian cấp phát nhưng nó có một nhược điểm rất rõ là làm phân mảnh bộ nhớ.

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

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

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

Các hàm hệ thống được cung cấp trong
thư viện glibc cho phép thay đổi program break

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

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]; 
};

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ý

Đồng thời chúng ta định nghĩa luôn độ dài cấu trúc quản lý, lưu ý rằng trường data luôn nằm ở vị trí cuối cùng của s_block và độ dài của meta-data không bao gồm độ dài của trường này, do đó độ dài của meta-data được định nghĩa như sau

#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)

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)

    sb = sbrk(BLOCK_SIZE + s);

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)

    while(b && !(b->free && b->size >= size))

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)

    new = (t_block)(b->data + s);

    new->size = b->size – s – BLOCK_SIZE;

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)

        b = find_block(&last, s);

            if(b->size – s >= (BLOCK_SIZE + 4))

            b = extend_heap(last, s);

        b = extend_heap(NULL, s);

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)

        if(p > base && p < sbrk(0))  

            return (p == (get_block(p))->ptr);

        if(b->prev && b->prev->free) 

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;

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:

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)

   
new = tmalloc(number*size);

       
s4 = align4(number*size) << 2;

Hàm realloc resize
lại vùng nhớ đã được cấp phát

void *trealloc(void *p, size_t size)

            if(b->size -s >= (BLOCK_SIZE + 4))

            if(b->next && b->next->free 

            && (b->size + BLOCK_SIZE + b->next->size) >= s) 

                if(b->size – s >= (BLOCK_SIZE + 4))

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

Cơ sở lý thuyết về bộ nhớ ảo, bộ nhớ logic và bộ nhớ vật lý Hoạt động ánh xạ địa chỉ ảo tới địa chỉ vật lý Linux cung cấp cho các tiến trình hệ thống quản lý bộ nhớ ảo, nơi mỗi địa chỉ nhớ ảo có khả năng được ánh xạ tới một địa chỉ vật lý. Với độ dài 32 bit, toàn bộ không gian địa chỉ mỗi tiến trình có khả năng truy nhập là 2^32 ~ 4 Gigabit. Linux chia không gian địa chỉ này thành các trang nhớ (page) có độ dài bằng nhau (4096 bytes), mỗi khi tiến trình yêu cầu một vùng nhớ, cả trang nhớ tương ứng (chứa vùng nhớ) sẽ được cấp cho tiến trình. Bộ nhớ vật lý hệ thống chính là lượng RAM có trong hệ thống, Linux cũng chia bộ nhớ vật lý này thành các trang bằng nhau, gọi là các page frame, mỗi page frame được đánh số thứ tự gọi là các page frame number. Các địa chỉ ảo có thể sẽ được ánh xạ thành địa chỉ vật lý dựa vào các phần cứng gọi là các MMU (Memory Management Unit) theo một phương pháp gọi là lazy allocation . Theo phương pháp này, mỗi khi một vùng nhớ ảo được cấp phát cho tiến

Lời mở đầu Nhân hệ điều hành Linux được cấu thành từ rất nhiều các sub-system, mỗi sub-system này thực hiện các chức năng riêng biệt nhau, tuy nhiên một số nhóm sub-system có thể mong muốn nhận tập các sự kiện giống nhau. Nhân Linux thiết kế một phương pháp truyền thông để có thể chia sẻ một sự kiện tới nhiều các sub-system vừa tạo ra sự linh hoạt trong code vừa có khả năng mở rộng dễ dàng trong tương lai. Phương pháp đó gọi là notifier-call chain. Việc hiểu rõ hoạt động của phương pháp này là một nhu cầu giúp cho các kỹ sư thiết kế kiến trúc phần mềm có thể có một chất liệu phục vụ cho việc xây dựng hệ thống phần mềm của chính mình. Tổng quan về notifier-call chain Notifier-call chain là một danh sách liên kết đơn của các hàm sẽ được thực hiện tuần tự khi một sự kiện nhất định xảy ra. Mỗi hàm có chức năng giúp cho một sub-system nhất định biết về sự kiện và có hành động tương ứng đối với sự kiện đó. Như vậy notifi-call chain bao gồm hai thành phần, bên chủ động thông báo sự

ADVERTISEMENT
ADVERTISEMENT

Related Posts

Next Post

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Bài Viết Mới

ADVERTISEMENT