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

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

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

#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]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] 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
//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

//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ự