Hãy hình dung một cái kệ kho dài, ban đầu xếp kín những thùng hàng đủ mọi kích cỡ. Bạn lấy đi ngẫu nhiên chín trong mười thùng — kệ giờ đầy khoảng trống. Nhìn qua thì "còn bao nhiêu chỗ trống", nhưng khi cần đặt một thùng to vào, bạn phát hiện không khe hở nào đủ rộng: các khoảng trống tuy nhiều nhưng nhỏ và nằm rải rác, xen giữa những thùng còn lại. Cả cái kệ dài vẫn bị coi là "đã dùng" dù phần lớn đang rỗng. Đó gần như đúng những gì xảy ra với heap của một chương trình khi cấp và free loạn nhiều cỡ — hiện tượng gọi là phân mảnh (fragmentation).

Hai phần trước đo hai allocator "gọn gàng": arena cấp bằng tăng con trỏ rồi giải phóng cả lô, và free list/pool cấp/free từng ô cùng cỡ O(1). Cả hai đều tránh được cái mà malloc/free thông thường phải sống chung. Khi bạn cấp và free nhiều đối tượng khác cỡ xen kẽ nhau, heap vỡ thành nhiều hố trống rải rác không liền nhau — và điều đó tốn kém hơn "chỉ là lãng phí một chút bộ nhớ" rất nhiều. Tôi đo cái giá thật của phân mảnh trong container gcc:13 bằng cách đọc RSS thật của tiến trình, và con số cho thấy hai niềm tin phổ biến đều sai.

Free không trả về hệ điều hành, và hố nhỏ không lấp được request lớn

Có một mô hình tinh thần đơn giản mà nhiều người mang theo: "malloc xin bộ nhớ, free trả nó lại; free xong thì bộ nhớ về hệ điều hành, RSS giảm". Thực tế phức tạp hơn nhiều, và hai điểm sau là gốc của mọi chi phí phân mảnh:

  • free thường không trả bộ nhớ về hệ điều hành. Với các khối nhỏ, glibc cấp từ một vùng heap mở rộng bằng brk. Khi bạn free, nó chỉ đánh dấu khối là trống và giữ lại trong danh sách trống của chính nó để tái dùng — chứ không thu hẹp heap trả về nhân. Nên RSS (bộ nhớ thật tiến trình đang chiếm) không giảm dù dữ liệu sống của bạn tụt xuống.
  • Hố trống rời rạc không phải lúc nào cũng dùng lại được. Nếu các hố nhỏ và nằm rải rác giữa các khối còn sống, một request lớn hơn không lọt vào bất kỳ hố nào. malloc không thể gộp các hố không liền nhau thành một khối lớn, nên nó buộc phải xin thêm bộ nhớ — heap phình ra dù đang còn rất nhiều chỗ trống cộng lại.

Đây là external fragmentation (phân mảnh ngoài): tổng bộ nhớ trống thì nhiều, nhưng bị chia vụn thành những mảnh quá nhỏ để dùng cho việc cần — đúng cái kệ kho đầy khe hở nhưng không nhét nổi thùng to. Nó khác với chuyện vector mọc lại hay căn lề — đây là hệ quả của lịch sử cấp/free, không phải của một cấu trúc đơn lẻ.

Đo: giữ gấp 12 lần, và cấp lại làm phình thêm 563 MB

Tôi dựng một mẫu cấp/free "loạn": cấp 4 triệu ô cỡ ngẫu nhiên 16–271 byte, chạm vào từng ô để nó thật sự vào RSS, rồi free ngẫu nhiên ~90% — để lại các hố nhỏ rải rác. Sau đó cấp lại 2 triệu ô 512 byte (lớn hơn phần lớn hố). Đọc RSS thật từ /proc/self/statm ở mỗi mốc:

RSS thật (/proc/self/statm), g++ -O2:

A. NHIỀU CỠ (16..271 byte, gây phân mảnh):
   Pha 1  cấp 4tr ô        : RSS 655 MB, sống 547 MB
   Pha 2  free 90% ngẫu nhiên: RSS 655 MB, sống  55 MB  -> RSS/sống = 12x
   Pha 3  cấp lại 2tr ô 512B : RSS phình +563 MB (hố nhỏ không lấp được)

B. CÙNG CỠ 64 byte (tái dùng hố, không phân mảnh):
   Pha 3  cấp lại 2tr ô 64B  : RSS phình +0 MB  (tái dùng đúng các hố vừa free)

Nhìn A pha 2 — đây là con số làm tôi phải nhìn lại hai lần: sau khi free 90% số ô, dữ liệu sống chỉ còn 55 MB, nhưng RSS vẫn giữ nguyên 655 MB. Tiến trình đang chiếm gấp 12 lần bộ nhớ nó thực sự cần. free đã chạy đủ 3,6 triệu lần, nhưng không một byte nào trả về hệ điều hành — glibc giữ hết trong heap để tái dùng sau. Nếu bạn nhìn top hay cột RES và tưởng "chương trình đang dùng 655 MB dữ liệu", bạn sai gấp 12 lần.

Nhìn A pha 3 — con số phá vỡ niềm tin thứ hai. Ta vừa có 600 MB "trống" nằm trong heap (các hố 16–271 byte). Nhưng khi cấp 2 triệu ô 512 byte, chúng không lọt vào những hố nhỏ đó, và malloc không gộp được các hố rời rạc — nên heap phải phình thêm 563 MB. Bộ nhớ trống thì có thừa, nhưng sai kích thước và rời rạc, nên vô dụng. Phân mảnh không chỉ giữ bộ nhớ cũ; nó còn ép bạn xin bộ nhớ mới.

Nhìn B để thấy tương phản: làm đúng cùng chuỗi thao tác nhưng mọi ô đều 64 byte. Sau khi free 90% rồi cấp lại 2 triệu ô cùng 64 byte, heap phình +0 MB — vì mỗi ô mới lọt đúng vào một hố vừa free. Cùng kích thước nghĩa là mọi hố đều tái dùng được, nên không có phân mảnh ngoài. Đây chính là lý do pool free list của phần trước chống phân mảnh: nó ép mọi ô cùng cỡ.

Một lưu ý cho sòng phẳng: RSS tuyệt đối ở kịch bản B cao vì nó chạy sau A trong cùng tiến trình và thừa hưởng phần heap mà A đã giữ lại — thêm một bằng chứng nữa rằng bộ nhớ không được trả về. Con số có ý nghĩa ở B là mức phình +0 MB, so với +563 MB của A.

(Môi trường đo: container gcc:13 trên host ARM AArch64, glibc malloc, g++ -O2, RSS đọc từ /proc/self/statm — số trang resident × kích thước trang. Con số đổi theo allocator và hệ; cái cần nhìn là tỉ lệ RSS/sống 12x và mức phình +563 MB vs +0 MB.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với một mô hình ngây thơ: "free(p) là trả p về hệ điều hành; free hết thì RSS về gần 0". Con số bác thẳng: sau khi free 90% của 4 triệu ô nhỏ, RSS vẫn giữ 655 MB trong khi dữ liệu sống chỉ 55 MB — glibc giữ lại các hố nhỏ trong heap brk để tái dùng, không trả về nhân. "Free xong là hết chiếm" là sai: một dịch vụ chạy lâu có thể phình RSS lên đỉnh rồi giữ nguyên mãi, dù tải đã giảm — người ta hay nhầm đó là "rò rỉ bộ nhớ" trong khi thực ra là phân mảnh và giữ lại.

Nhưng có một niềm tin ngược lại cũng sai: "phân mảnh thì cũng chỉ là lãng phí một ít bộ nhớ thôi, không sao". Đo cho thấy nó tệ hơn thế: các hố nhỏ rời rạc không lấp được request lớn hơn, nên cấp lại 2 triệu ô 512B làm heap phình thêm 563 MB — phân mảnh không chỉ giữ bộ nhớ cũ mà còn ép xin bộ nhớ mới, và các đối tượng nằm rải rác khắp một heap lớn cũng làm cache tệ đi (như phần duyệt mảng vs danh sách). Nó là một chi phí kép: RAM và tốc độ.

Về đến code hằng ngày

Điều đầu tiên: với dịch vụ chạy lâu cấp/free nhiều cỡ, đừng đọc RSS như "dữ liệu đang dùng". RSS phản ánh đỉnh bộ nhớ heap từng chạm cộng phần giữ lại, không phải dữ liệu sống hiện tại. Một tiến trình phình lên lúc tải cao rồi giữ nguyên RSS khi tải giảm thường là phân mảnh và giữ lại, không phải rò rỉ. Muốn phân biệt: đo dữ liệu sống thật của bạn và so với RSS — chênh nhiều lần nhưng ổn định (không tăng vô hạn) là dấu hiệu phân mảnh, còn tăng mãi mới là rò rỉ. Tôi từng ngồi truy một "rò rỉ" hàng giờ trước khi nhận ra RSS đã đứng yên từ lâu — nó chưa bao giờ rò, chỉ là không trả lại.

Điều thứ hai: khi bạn cấp/free nhiều đối tượng nhỏ cùng cỡ với tần suất cao, dùng pool/free list hoặc arena để cắt phân mảnh. Đây là chỗ ba phần nối vào nhau: cùng cỡ và chết rời rạc → pool free list (mọi hố tái dùng được, +0 MB như đo); chết cùng lúc → arena (bump rồi reset cả lô, không có hố nào). Cả hai ép một trật tự lên bộ nhớ mà malloc đa cỡ không có được.

Và chỗ này không riêng gì C/C++ — nó lý giải rất nhiều thứ ở các tầng cao hơn. Các allocator hiện đại như jemalloc và tcmalloc chia bộ nhớ thành các "size class" cùng cỡ đúng để mọi hố tái dùng được, giống kịch bản B. Trong Java và Go, garbage collector không chỉ thu hồi mà còn nén (compact/copy) — dồn các đối tượng sống lại liền nhau để xóa hố, một việc mà malloc/free thủ công không tự làm; đó là lý do heap của JVM ít bị phân mảnh ngoài hơn nhưng phải trả giá bằng những đợt GC dừng-thế-giới. Còn database thì gọi thẳng tên vấn đề: PostgreSQL có "bloat" khi update/delete để lại tuple chết rải rác trong trang, và VACUUM/pg_repack chính là thao tác gom-nén tương đương. Cùng một hình dạng bài toán — lịch sử cấp/giải phóng để lại lỗ hổng — chỉ đổi tên ở mỗi tầng.

Muốn tự thấy thì viết một vòng cấp 4 triệu khối cỡ ngẫu nhiên nhỏ (16–271 byte), chạm vào từng khối, rồi đọc RSS từ /proc/self/statm (số trang resident × kích thước trang). Ghi lại RSS và tổng byte sống. Giờ free ngẫu nhiên 90% số khối và đọc lại: bạn sẽ thấy dữ liệu sống tụt còn ~10%, nhưng RSS gần như không đổi — free không trả về hệ điều hành. Rồi cấp thêm vài triệu khối lớn hơn (512 byte) và xem RSS phình ra dù bạn vừa "giải phóng" hàng trăm MB — vì các hố quá nhỏ và rời rạc. Cuối cùng, lặp lại toàn bộ nhưng cho mọi khối cùng một cỡ: lần này cấp lại không làm phình gì, vì mỗi khối mới lọt đúng một hố cũ. Vài phút đó cho bạn thấy điều mà "free là trả bộ nhớ về hệ điều hành" giấu đi: bộ nhớ đã cấp và free để lại một cái heap vỡ vụn, và chính hình dạng của những mảnh vỡ đó — chứ không phải tổng dung lượng — quyết định lần cấp sau nhanh hay chậm, gọn hay phình.