Computer Systems: A Programmer's Perspective Chương 9 · Virtual Memory

Chương 9 · Bộ nhớ ảo Chapter 9 · Virtual Memory

Một lớp ảo hoá lặng lẽ cho mỗi tiến trình ảo giác được độc chiếm bộ nhớ Mỗi chương trình tưởng mình có cả bộ nhớ — nhờ một trò ảo thuật A quiet layer of indirection that gives each process the illusion of owning all of memory

Bryant và O'Hallaron mở đầu bằng một nghịch lý: các tiến trình phải dùng chung CPU và bộ nhớ chính, nhưng bộ nhớ dùng chung dễ cạn và dễ bị hỏng — một tiến trình ghi nhầm có thể làm tiến trình khác chết theo cách khó hiểu. Lời giải là bộ nhớ ảo (virtual memory), một trừu tượng của bộ nhớ chính được dựng từ sự phối hợp của ngoại lệ phần cứng, dịch địa chỉ (address translation), bộ nhớ chính, tệp trên đĩa và phần mềm nhân.1

Nhiều chương trình phải chia nhau một bộ nhớ. Nếu để chúng tự tranh nhau thì dễ hết chỗ, lại dễ giẫm chân nhau. Máy tính giải quyết bằng một trò khéo: mỗi chương trình được cho một "bản đồ bộ nhớ" riêng, tưởng như cả máy là của mình. Trò đó tên là bộ nhớ ảo. Nhớ nhé: mỗi chương trình có bản đồ nhớ riêng, không giẫm lên nhau.

Bryant and O'Hallaron open with a paradox: processes must share the CPU and main memory, yet shared memory runs out and is easily corrupted — one process writing to the wrong place can kill another in bewildering ways. The answer is virtual memory, an abstraction of main memory built from the interaction of hardware exceptions, address translation, main memory, disk files, and kernel software.1

Điều tinh tế là cách tổ chức: thay vì để chương trình chạm thẳng vào bộ nhớ vật lý, CPU sinh ra một địa chỉ ảo (virtual address), và một phần cứng chuyên dụng trên chip — đơn vị quản lý bộ nhớ (memory management unit, MMU) — dịch nó sang địa chỉ vật lý (physical address) ngay khi đang chạy, dựa trên một bảng tra do hệ điều hành quản lý.1 Nhờ một cơ chế duy nhất này, bộ nhớ ảo đồng thời làm được ba việc: dùng bộ nhớ chính như một bộ đệm (cache) cho không gian địa chỉ lưu trên đĩa, đơn giản hoá việc quản lý bộ nhớ, và bảo vệ không gian địa chỉ của mỗi tiến trình khỏi bị tiến trình khác phá.1 Các tác giả nhấn mạnh lý do lập trình viên cần hiểu nó: bộ nhớ ảo trung tâm (xuyên suốt mọi tầng hệ thống), mạnh mẽ (cho phép ánh xạ tệp, chia sẻ bộ nhớ) và nguy hiểm (gốc rễ của những lỗi bộ nhớ hiểm hóc).1

Luận đề của chương: bộ nhớ ảo là một lớp gián tiếp — CPU sinh địa chỉ ảo, MMU dịch sang địa chỉ vật lý qua bảng trang (page table) — và chỉ một cơ chế ấy đủ để làm ba việc lớn: dùng bộ nhớ chính như bộ đệm cho đĩa, đơn giản hoá quản lý bộ nhớ, và bảo vệ từng tiến trình; hiểu nó là hiểu vì sao malloc, mmap hoạt động và vì sao con trỏ hỏng lại gây ra "segmentation fault".1

Ý chính: máy cho mỗi chương trình một địa chỉ "ảo" rồi lặng lẽ dịch sang chỗ thật trong bộ nhớ. Một trò khéo mà làm được ba việc: tiết kiệm bộ nhớ, dễ quản lý, và giữ các chương trình không phá nhau. Nhớ nhé: địa chỉ bạn thấy là ảo; máy mới biết nó nằm thật ở đâu.

The chapter's thesis: virtual memory is a layer of indirection — the CPU emits virtual addresses and the MMU translates them to physical addresses through a page table — and that single mechanism does three big jobs: it uses main memory as a cache for disk, it simplifies memory management, and it protects each process; understanding it is understanding why malloc and mmap work and why a bad pointer yields a "segmentation fault".1

Cụm khái niệm 01 Concept cluster 01

Địa chỉ ảo và vật lý, và ba vai trò của bộ nhớ ảo Địa chỉ "ảo" là gì, và nó giúp được ba việc Virtual versus physical addressing, and VM's three roles

Bộ nhớ chính được tổ chức như một mảng gồm M ô nhớ cỡ một byte liên tiếp, mỗi ô có một địa chỉ vật lý (physical address, PA) riêng. Cách đơn giản nhất để CPU truy cập bộ nhớ là dùng thẳng địa chỉ vật lý — gọi là định địa chỉ vật lý (physical addressing); các PC đời đầu và nhiều chip xử lý tín hiệu số, vi điều khiển nhúng, siêu máy tính Cray vẫn làm vậy.1 Nhưng bộ xử lý hiện đại dùng định địa chỉ ảo (virtual addressing): CPU sinh một địa chỉ ảo (virtual address, VA), và MMU dịch nó sang địa chỉ vật lý nhờ một bảng tra trong bộ nhớ do hệ điều hành quản lý.1

Hãy coi bộ nhớ như một dãy ô có đánh số. Số thật của ô gọi là địa chỉ vật lý. Ngày xưa chương trình gọi thẳng số thật đó. Nay thì khác: chương trình đọc theo một "số ảo", và một bộ phận nhỏ trong chip âm thầm đổi số ảo thành số thật. Nhớ nhé: chương trình nói số ảo, chip dịch ra số thật.

Main memory is organized as an array of M contiguous byte-size cells, each with its own physical address (PA). The simplest way for a CPU to access memory is to use physical addresses directly — physical addressing; early PCs and many digital signal processors, embedded microcontrollers, and Cray supercomputers still do.1 But modern processors use virtual addressing: the CPU generates a virtual address (VA), and the MMU translates it to a physical address using a lookup table in memory that the operating system manages.1

Định nghĩa. Một không gian địa chỉ (address space) là tập có thứ tự các số nguyên không âm. Với bộ nhớ ảo, CPU sinh địa chỉ từ một không gian địa chỉ ảo (virtual address space) cỡ N = 2n địa chỉ; hệ thống cũng có một không gian địa chỉ vật lý (physical address space) ứng với M = 2m byte bộ nhớ thật. Khái niệm này tách bạch đối tượng dữ liệu (byte) khỏi thuộc tính của nó (địa chỉ) — nhờ đó một byte có thể có nhiều địa chỉ độc lập.1

Nói đơn giản. "Không gian địa chỉ" chỉ là dãy các số dùng để đánh địa chỉ. Máy có hai dãy: dãy ảo (chương trình thấy) và dãy thật (bộ nhớ có). Nhớ nhé: có hai hệ số — số ảo và số thật.

Definition. An address space is an ordered set of nonnegative integers. With virtual memory the CPU generates addresses from a virtual address space of N = 2n addresses; the system also has a physical address space of M = 2m bytes of real memory. The idea cleanly separates a data object (a byte) from its attribute (an address) — so one byte can have several independent addresses.1

VA --[MMU]--> PA
trang ảo (VP) ⇄ trang vật lý (PP)
3 trạng thái trang:
  chưa cấp · đã đệm · chưa đệm
miss đệm = page fault

số ảo --> (MMU) --> số thật
bộ nhớ chia thành "trang"
thiếu trang --> nạp từ đĩa

VA --[MMU]--> PA
virtual page (VP) ⇄ physical page (PP)
3 page states:
  unallocated · cached · uncached
cache miss = page fault

  1. virtual addressing

    Định địa chỉ ảo — MMU dịch địa chỉ ngay khi chạy Địa chỉ ảo — chip tự đổi số ảo thành số thật Virtual addressing — the MMU translates on the fly

    Với định địa chỉ ảo, CPU truy cập bộ nhớ bằng cách sinh một địa chỉ ảo, được chuyển thành địa chỉ vật lý trước khi gửi tới bộ nhớ. Việc chuyển này gọi là dịch địa chỉ (address translation) và cần phần cứng CPU phối hợp chặt với hệ điều hành: phần cứng chuyên dụng là MMU, còn bảng tra thì nằm trong bộ nhớ chính và do hệ điều hành quản lý.1

    Chương trình chỉ nói "cho tôi ô số 4100". Trước khi chạm bộ nhớ thật, một bộ phận trong chip (MMU) tra bảng và đổi 4100 thành ô thật, ví dụ ô số 4. Người lập trình không thấy bước này. Nhớ nhé: mọi địa chỉ đều đi qua một bước dịch trước khi chạm bộ nhớ thật.

    With virtual addressing, the CPU accesses memory by generating a virtual address, which is converted to a physical address before it reaches memory. This conversion is address translation and requires CPU hardware and the OS to cooperate closely: the dedicated hardware is the MMU, while the lookup table lives in main memory and is managed by the operating system.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi lần chương trình đọc hay ghi một biến, một bước dịch địa chỉ âm thầm diễn ra trong MMU — nhanh đến mức bạn không bao giờ nhận ra. Mỗi lần đọc hay ghi một biến, bước dịch âm thầm xảy ra rồi. Every time a program reads or writes a variable, a translation step quietly runs inside the MMU — so fast you never notice it.

    Số bit và kích cỡ không gian

    Cỡ một không gian địa chỉ tính bằng số bit cần để biểu diễn địa chỉ lớn nhất; không gian N = 2n địa chỉ gọi là không gian n-bit. Hệ hiện đại thường hỗ trợ không gian địa chỉ ảo 32 bit hoặc 64 bit.1

    Nối với các chương khác

    Bộ nhớ ảo xuyên suốt mọi tầng: ngoại lệ phần cứng (Chương 8), trình liên kết và trình nạp (Chương 7), tệp và tiến trình (Chương 8). Hiểu nó giúp hiểu toàn hệ thống hoạt động ra sao.1

  2. VM as caching

    Bộ nhớ ảo như bộ đệm — trang, bảng trang, và page fault Bộ nhớ ảo như bộ đệm — chia thành trang, thiếu thì nạp VM as caching — pages, page tables, and page faults

    Về mặt khái niệm, bộ nhớ ảo là một mảng lưu trên đĩa, được đệm trong bộ nhớ chính. Nó được chia thành các khối cố định gọi là trang ảo (virtual pages, VPs), mỗi trang P = 2p byte; bộ nhớ vật lý cũng chia thành trang vật lý (physical pages, PPs) cùng cỡ. Do chi phí miss khổng lồ — đọc byte đầu từ đĩa chậm hơn từ bộ nhớ khoảng 100.000 lần — nên trang thường lớn (điển hình 4 KB đến 2 MB), bộ đệm DRAM là liên kết đầy đủ (fully associative) và luôn ghi-lùi (write-back).1

    Hãy hình dung toàn bộ bộ nhớ của bạn thật ra nằm trên đĩa, còn bộ nhớ chính chỉ giữ những "trang" hay dùng. Khi cần một trang chưa có trong bộ nhớ, máy phải chạy ra đĩa lấy — việc này rất chậm, nên mỗi trang được làm to (thường vài nghìn byte). Nhớ nhé: bộ nhớ chính chỉ là chỗ giữ tạm những trang hay dùng của một kho lớn hơn trên đĩa.

    Conceptually, virtual memory is an array stored on disk that is cached in main memory. It is partitioned into fixed-size blocks called virtual pages (VPs) of P = 2p bytes; physical memory is partitioned into same-size physical pages (PPs). Because the miss cost is enormous — reading the first byte from disk is about 100,000 times slower than from memory — pages are large (typically 4 KB to 2 MB), the DRAM cache is fully associative, and it always uses write-back.1

    Bạn gặp nó ở đâuWhere you meet it Khi một chương trình vừa khởi động chậm (đang nạp các trang từ đĩa — demand paging) rồi chạy mượt dần, hoặc khi máy "giật lag" vì thrashing — các trang bị tống ra và nạp lại liên tục.1 Khi một ứng dụng mở lần đầu hơi khựng rồi sau đó nhanh dần. When a program starts slowly (paging in from disk — demand paging) then runs smoothly, or when a machine stalls from thrashing — pages evicted and reloaded over and over.1

    Bảng trang và page fault

    Một bảng trang (page table) là mảng các mục bảng trang (page table entries, PTEs), mỗi mục gồm một bit hợp lệ và một trường địa chỉ. Khi CPU chạm một trang chưa được đệm, bit hợp lệ bằng 0 khiến MMU kích hoạt một page fault (một lần miss của bộ đệm DRAM): trình xử lý trong nhân chọn một trang nạn nhân, ghi lùi nếu bẩn, rồi nạp trang cần thiết từ đĩa và chạy lại lệnh.1

    Vì sao nó chạy tốt: tính cục bộ

    Bộ nhớ ảo nghe có vẻ chậm, nhưng hiệu quả nhờ tính cục bộ (locality): tại mỗi thời điểm chương trình chỉ làm việc trên một tập nhỏ trang gọi là tập làm việc (working set). Nếu tập làm việc vượt bộ nhớ vật lý, xảy ra thrashing.1 Bộ nhớ ảo được phát minh từ đầu thập niên 1960, trước cả khe hở CPU–bộ nhớ sinh ra cache SRAM.1

  3. management + protection

    Quản lý và bảo vệ — một không gian riêng cho mỗi tiến trình Quản lý và bảo vệ — mỗi chương trình một vùng riêng, có khoá Management & protection — a private space per process

    Hệ điều hành cấp cho mỗi tiến trình một bảng trang riêng, tức một không gian địa chỉ ảo riêng. Điều này đơn giản hoá bốn việc: liên kết (mọi tiến trình dùng cùng một bố cục bộ nhớ — mã 64-bit luôn bắt đầu ở địa chỉ ảo 0x400000), nạp (ánh xạ chứ không chép dữ liệu), chia sẻ (nhiều trang ảo trỏ về cùng một trang vật lý), và cấp phát (các trang vật lý được cấp có thể nằm rải rác).1 Thêm vài bit quyền (permission bits) — SUP, READ, WRITE — vào mỗi PTE là có luôn cơ chế bảo vệ bộ nhớ mức trang.1

    Mỗi chương trình được phát một bản đồ nhớ riêng, nên chúng không đạp lên nhau và mọi chương trình đều thấy bố cục giống nhau — rất dễ cho máy sắp xếp. Mỗi ô trong bản đồ còn gắn "khoá": được đọc không, được ghi không. Phá khoá là bị chặn. Nhớ nhé: bản đồ riêng + khoá từng vùng = an toàn và gọn gàng.

    The OS gives each process its own page table — its own virtual address space. This simplifies four things: linking (every process shares one memory layout — 64-bit code always starts at virtual address 0x400000), loading (mapping rather than copying data), sharing (several virtual pages pointing to one physical page), and allocation (the physical pages given out can be scattered).1 Adding a few permission bits — SUP, READ, WRITE — to each PTE yields page-level memory protection for free.1

    Bạn gặp nó ở đâuWhere you meet it Khi một tiến trình chạy ở chế độ người dùng cố ghi vào mã chỉ-đọc hay đọc bộ nhớ của tiến trình khác, CPU sinh lỗi bảo vệ (general protection fault), nhân gửi tín hiệu SIGSEGV, và shell báo "segmentation fault".1 Khi bạn thấy dòng chữ "segmentation fault" — đó là máy chặn chương trình đụng vào vùng cấm. When a user-mode process tries to write read-only code or read another process's memory, the CPU raises a general protection fault, the kernel sends SIGSEGV, and the shell reports a "segmentation fault".1

    Khi bộ nhớ ảo nhỏ hơn bộ nhớ thật

    Các tác giả nhắc một điểm phản trực giác: vài hệ đời đầu như DEC PDP-11/70 có không gian địa chỉ ảo nhỏ hơn bộ nhớ vật lý, nhưng bộ nhớ ảo vẫn hữu ích vì nó đơn giản hoá quản lý bộ nhớ và cho một cách tự nhiên để bảo vệ.1

    Bit SUP, READ, WRITE

    Bit SUP cho biết trang chỉ truy cập được ở chế độ nhân (supervisor); READ và WRITE kiểm soát quyền đọc/ghi. Tiến trình người dùng chỉ chạm được các trang có SUP = 0, và chỉ theo quyền đã định.1

Cụm khái niệm 02 Concept cluster 02

Dịch địa chỉ: TLB, bảng trang nhiều cấp, và hệ Intel Core i7/Linux Máy dịch địa chỉ nhanh ra sao — và một ví dụ chip thật Address translation: the TLB, multi-level page tables, and the Core i7/Linux system

Dịch địa chỉ là một ánh xạ từ không gian địa chỉ ảo sang không gian địa chỉ vật lý. Một thanh ghi điều khiển, thanh ghi gốc bảng trang (page table base register, PTBR), trỏ tới bảng trang hiện hành. Địa chỉ ảo n bit tách làm hai: p bit thấp là phần bù trang ảo (virtual page offset, VPO), và (n − p) bit cao là số trang ảo (virtual page number, VPN). MMU dùng VPN để chọn một PTE, lấy ra số trang vật lý (physical page number, PPN), rồi ghép PPN với VPO (vì VPO ≡ PPO) thành địa chỉ vật lý.1

Mỗi địa chỉ ảo gồm hai phần: phần "số trang" (trang nào) và phần "lệch trong trang" (ô nào trong trang). Máy chỉ cần đổi phần số trang từ ảo sang thật, còn phần lệch giữ nguyên. Giống như đổi "toà nhà" nhưng giữ nguyên "số phòng". Nhớ nhé: dịch địa chỉ chỉ đổi số trang, giữ nguyên vị trí trong trang.

Address translation is a mapping from the virtual address space to the physical one. A control register, the page table base register (PTBR), points to the current page table. An n-bit virtual address splits in two: the low p bits are the virtual page offset (VPO), and the high (n − p) bits are the virtual page number (VPN). The MMU uses the VPN to select a PTE, extracts the physical page number (PPN), and concatenates it with the VPO (since VPO ≡ PPO) to form the physical address.1

Định nghĩa. Đệm dịch địa chỉ (translation lookaside buffer, TLB) là một bộ đệm nhỏ, liên kết tập, nằm trong MMU, lưu các PTE hay dùng để khỏi phải ra bộ nhớ tra bảng mỗi lần. Khi TLB trúng, cả quá trình dịch diễn ra trong chip nên rất nhanh; khi TLB trượt, MMU phải lấy PTE từ cache L1.1

Nói đơn giản. Để khỏi tra bảng chậm mỗi lần, chip giữ sẵn vài kết quả dịch gần đây trong một ngăn nhớ tí hon tên là TLB. Trúng TLB là xong ngay. Nhớ nhé: TLB là sổ tay ghi nhớ nhanh các lần dịch gần đây.

Definition. The translation lookaside buffer (TLB) is a small, set-associative cache inside the MMU that holds frequently used PTEs so it need not go to memory on every access. On a TLB hit the whole translation happens on-chip and is fast; on a TLB miss the MMU must fetch the PTE from the L1 cache.1

i7: VA 48-bit (256 TB)
  PA 52-bit (4 PB)
VPN 36-bit = 4 × 9-bit
  VPO 12-bit (trang 4 KB)
bảng trang 4 cấp

địa chỉ ảo i7: 48 bit
số trang chia 4 khúc 9 bit
--> 4 tầng bảng trang

i7: VA 48-bit (256 TB)
  PA 52-bit (4 PB)
VPN 36-bit = 4 × 9-bit
  VPO 12-bit (4 KB pages)
4-level page table

  1. page table walk

    Dịch bằng bảng trang — năm bước khi trang đã có Dịch bằng bảng trang — các bước khi trang sẵn sàng Translating with a page table — five steps on a hit

    Khi trang đã được đệm (page hit), phần cứng làm năm bước: (1) CPU sinh địa chỉ ảo gửi MMU; (2) MMU tính địa chỉ PTE và yêu cầu nó từ cache/bộ nhớ; (3) cache/bộ nhớ trả PTE; (4) MMU dựng địa chỉ vật lý; (5) cache/bộ nhớ trả về từ dữ liệu. Khi page fault, bước 4 khác: bit hợp lệ bằng 0, MMU sinh ngoại lệ, trình xử lý trong nhân nạp trang rồi chạy lại lệnh.1

    Nếu trang cần dùng đã có sẵn trong bộ nhớ, chip chỉ việc tra bảng, ghép địa chỉ, lấy dữ liệu — vài bước là xong. Nếu trang chưa có, máy phải tạm dừng, chạy ra đĩa nạp trang về, rồi làm lại. Nhớ nhé: có sẵn thì nhanh; thiếu thì phải ra đĩa nạp, chậm hơn nhiều.

    On a page hit the hardware does five steps: (1) the CPU sends a virtual address to the MMU; (2) the MMU computes the PTE address and requests it from the cache/memory; (3) the cache/memory returns the PTE; (4) the MMU builds the physical address; (5) the cache/memory returns the data word. On a page fault step 4 differs: the valid bit is 0, the MMU raises an exception, the kernel's handler pages in and reruns the instruction.1

    Bạn gặp nó ở đâuWhere you meet it Sách dẫn một ví dụ làm tay trọn vẹn với hệ nhỏ: địa chỉ ảo 14 bit, địa chỉ vật lý 12 bit, trang 64 byte, TLB 4-way 16 mục — bạn dịch được 0x03d4 thành 0x354 chỉ bằng giấy bút.1 Trong sách có một ví dụ nhỏ để bạn tự dịch địa chỉ bằng giấy bút, không cần máy. The book works a full by-hand example on a tiny system: 14-bit virtual addresses, 12-bit physical, 64-byte pages, a 4-way 16-entry TLB — you translate 0x03d4 to 0x354 with pencil and paper.1
  2. TLB + multi-level

    TLB và bảng trang nhiều cấp — nén bảng, tăng tốc tra TLB và bảng nhiều tầng — bảng gọn hơn, tra nhanh hơn TLB and multi-level page tables — compact and fast

    Một bảng trang phẳng rất tốn chỗ: với không gian 32 bit, trang 4 KB, PTE 4 byte, cần một bảng 4 MB thường trú trong bộ nhớ — và vấn đề còn tệ hơn với hệ 64 bit. Giải pháp là bảng trang nhiều cấp (multi-level page tables): một cây bảng, trong đó bảng cấp 1 chỉ cần luôn ở bộ nhớ, còn các bảng cấp dưới được tạo và nạp khi cần — nếu một mục cấp trên là rỗng thì cả bảng con bên dưới không cần tồn tại.1 Việc phải tra nhiều cấp không làm chậm đáng kể vì TLB đệm luôn các PTE ở mọi cấp.1

    Một bảng tra duy nhất cho cả bộ nhớ thì to khủng khiếp. Nên người ta chia bảng thành nhiều tầng, như mục lục của mục lục: tầng trên chỉ tới tầng dưới, và tầng nào không dùng thì khỏi tạo. Nhờ TLB nhớ sẵn, tra nhiều tầng vẫn nhanh. Nhớ nhé: chia bảng thành tầng để khỏi phí chỗ cho phần không dùng.

    A flat page table is huge: for a 32-bit space, 4 KB pages, and 4-byte PTEs it needs a 4 MB table resident in memory — and 64-bit systems are worse. The fix is multi-level page tables: a tree of tables where only the level-1 table must stay in memory while lower levels are created and paged in on demand — if an upper-level entry is null, the whole sub-table below it need not exist.1 Walking several levels is not much slower because the TLB caches PTEs from every level.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi chương trình thật chỉ dùng một mẩu nhỏ của không gian địa chỉ 48-bit khổng lồ; bảng trang nhiều cấp cho phép phần còn lại "không tồn tại" mà không tốn bộ nhớ.1 Chương trình thật chỉ dùng một phần nhỏ bộ nhớ; phần còn lại khỏi cần bảng tra. A real program uses only a sliver of the vast 48-bit space; multi-level tables let the rest simply "not exist" at no memory cost.1

    Thành phần địa chỉ ảo để tra TLB

    Để tra TLB, VPN lại chia làm hai: chỉ số TLB (TLB index, TLBI) chọn tập, và thẻ TLB (TLB tag, TLBT) phân biệt các VPN cùng ánh xạ vào một tập.1

    Tra k cấp

    Với cây k cấp, địa chỉ ảo chia thành k số trang (VPN 1…k) và một VPO; mỗi PTE ở cấp j < k trỏ tới gốc bảng cấp j+1, còn PTE ở cấp k chứa PPN. MMU phải truy cập k PTE trước khi dựng được địa chỉ vật lý.1

  3. Core i7 / Linux

    Nghiên cứu hệ Intel Core i7/Linux — các con số thật Ví dụ chip Intel Core i7 chạy Linux — số liệu thật Case study: the Intel Core i7/Linux system — real numbers

    Core i7 (vi kiến trúc Haswell) hỗ trợ không gian địa chỉ ảo 48-bit (256 TB) và vật lý 52-bit (4 PB). Mỗi lõi có phân cấp TLB và cache riêng: L1 d-TLB 64 mục 4-way, L1 i-TLB 128 mục 4-way, L2 TLB hợp nhất 512 mục 4-way; cache L1 d/i mỗi cái 32 KB 8-way, L2 hợp nhất 256 KB 8-way, L3 hợp nhất 8 MB 16-way dùng chung cho cả bốn lõi.13 Trang cấu hình được 4 KB hoặc 4 MB; Linux dùng trang 4 KB. MMU dùng bảng trang bốn cấp: VPN 36-bit chia thành bốn khúc 9-bit, VPO 12-bit; thanh ghi CR3 giữ địa chỉ vật lý bảng cấp 1 và là một phần ngữ cảnh tiến trình.1

    Đây là số liệu từ một con chip thật: Intel Core i7. Nó cho mỗi chương trình một không gian địa chỉ cực lớn, dùng bảng tra bốn tầng, và có mấy ngăn nhớ TLB để dịch nhanh. Linux chia bộ nhớ thành trang 4 KB. Nhớ nhé: lý thuyết ở trên chính là cách một con chip thật đang chạy.

    The Core i7 (Haswell microarchitecture) supports a 48-bit (256 TB) virtual and 52-bit (4 PB) physical address space. Each core has its own TLB and cache hierarchy: an L1 d-TLB of 64 entries (4-way), an L1 i-TLB of 128 entries (4-way), and a unified L2 TLB of 512 entries (4-way); L1 d/i caches of 32 KB each (8-way), a unified 256 KB L2 (8-way), and a unified 8 MB L3 (16-way) shared by all four cores.13 Pages can be 4 KB or 4 MB; Linux uses 4 KB. The MMU uses a four-level page table: the 36-bit VPN splits into four 9-bit chunks, with a 12-bit VPO; the CR3 register holds the physical address of the level-1 table and is part of each process context.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi PTE của i7 có bit XD (execute-disable, giới thiệu trên hệ 64-bit) cho phép nhân cấm thực thi lệnh từ các trang nhất định — giảm rủi ro tấn công tràn bộ đệm bằng cách chỉ cho thực thi vùng mã chỉ-đọc.13 Chip có một "khoá" cấm chạy mã từ vùng dữ liệu — giúp chặn một kiểu tấn công phổ biến. Each i7 PTE has an XD (execute-disable, introduced on 64-bit systems) bit letting the kernel forbid instruction fetches from certain pages — reducing buffer-overflow attack risk by restricting execution to read-only code.13

    Tên bốn cấp bảng của Linux

    Linux đặt tên bốn cấp: thư mục trang toàn cục (page global directory), thư mục trang trên (page upper directory), thư mục trang giữa (page middle directory), và bảng trang (page table). Mỗi mục cấp 1 phủ một vùng 512 GB, cấp 2 là 1 GB, cấp 3 là 2 MB, cấp 4 là 4 KB.1

    Linux tổ chức vùng nhớ

    Linux coi bộ nhớ ảo của tiến trình là tập các vùng (areas). Mỗi tiến trình có một task_struct trỏ tới mm_struct (chứa pgd và mmap); danh sách vm_area_struct mô tả từng vùng (vm_start, vm_end, vm_prot, vm_flags). Trình xử lý page fault của Linux kiểm ba điều: địa chỉ có hợp lệ không, truy cập có được phép không, rồi mới nạp trang.1

Cụm khái niệm 03 Concept cluster 03

Ánh xạ bộ nhớ, cấp phát động, và thu gom rác Ánh xạ tệp, xin–trả bộ nhớ, và dọn rác tự động Memory mapping, dynamic allocation, and garbage collection

Linux khởi tạo nội dung một vùng bộ nhớ ảo bằng cách gắn nó với một đối tượng (object) trên đĩa — quá trình gọi là ánh xạ bộ nhớ (memory mapping). Vùng có thể ánh xạ tới một tệp thường trong hệ tệp, hoặc một tệp ẩn danh (anonymous file) toàn số 0 do nhân tạo ra (trang demand-zero). Nhưng nhiều lúc chương trình cần thêm bộ nhớ ngay khi chạy mà chưa biết trước kích cỡ; khi đó nó dùng cấp phát động (dynamic memory allocation) qua heap.1

Máy có thể "gắn" một vùng nhớ với một tệp trên đĩa — gọi là ánh xạ bộ nhớ. Còn khi chương trình cần thêm chỗ nhớ lúc đang chạy mà chưa biết trước cần bao nhiêu, nó xin thêm từ một kho gọi là heap — đó là cấp phát động. Nhớ nhé: cần thêm nhớ lúc chạy thì xin từ heap, dùng xong nhớ trả lại.

Linux initializes the contents of a virtual memory area by tying it to an object on disk — a process called memory mapping. An area can map to a regular file in the file system, or to an anonymous file of all zeros created by the kernel (demand-zero pages). But often a program needs more memory at run time without knowing the size in advance; then it uses dynamic memory allocation on the heap.1

Định nghĩa. Một bộ cấp phát (allocator) quản lý heap như một tập các khối: khối đã cấp hoặc đang rỗi. Với bộ cấp phát tường minh như gói malloc của C, chương trình tự xin khối bằng malloc và tự trả bằng free. Bộ cấp phát phải đáp ứng yêu cầu bất kỳ, trả lời tức thì, chỉ dùng heap, căn chỉnh khối, và không được dời khối đã cấp.15

Nói đơn giản. Heap như một kho chung. Bạn gọi malloc để mượn một ô, dùng xong gọi free để trả. Nếu quên trả, kho đầy dần. Nhớ nhé: mượn bằng malloc, trả bằng free — quên trả là rò rỉ.

Definition. An allocator manages the heap as a set of blocks, each allocated or free. With an explicit allocator like C's malloc package, the program requests blocks with malloc and returns them with free. The allocator must handle arbitrary requests, respond immediately, use only the heap, align blocks, and never move an allocated block.15

thông lượng = số yêu cầu / giây
  (vd 1.000 thao tác/giây)
tận dụng đỉnh U_k = max P_i / H_k
phân mảnh: trong & ngoài

nhanh (thông lượng)
  vs tiết kiệm (tận dụng)
kẻ thù: phân mảnh

throughput = requests / sec
  (e.g. 1,000 ops/sec)
peak utilization U_k = max P_i / H_k
fragmentation: internal & external

  1. memory mapping

    Ánh xạ bộ nhớ — một thao tác, nhiều việc Ánh xạ bộ nhớ — gắn vùng nhớ với tệp trên đĩa Memory mapping — one operation, many jobs

    Ánh xạ một tập trang ảo liên tục vào một đối tượng tuỳ ý trên đĩa chính là cách Linux nạp chương trình và thư viện: trình nạp chỉ ánh xạ các trang mã và dữ liệu, chúng được nạp theo nhu cầu lần đầu được chạm — không hề chép sẵn từ đĩa. Chương trình có thể tự ánh xạ bằng lời gọi hệ thống mmap.14

    Thay vì chép cả chương trình từ đĩa vào bộ nhớ, máy chỉ "gắn" chúng lại rồi nạp từng trang khi thật sự cần. Chương trình cũng có thể tự gắn một tệp vào bộ nhớ bằng lệnh mmap để đọc tệp như đọc một mảng. Nhớ nhé: gắn trước, nạp sau — chỉ nạp phần thật sự dùng.

    Mapping a set of contiguous virtual pages to an arbitrary object on disk is exactly how Linux loads programs and libraries: the loader merely maps the code and data pages, which are paged in on demand the first time they are touched — nothing is copied up front. A program can map things itself with the mmap system call.14

    Bạn gặp nó ở đâuWhere you meet it Khi nhiều tiến trình cùng chạy bash hay dùng chung thư viện C chuẩn: mã chỉ-đọc đó được ánh xạ chung một bản vật lý thay vì nhân bản cho mỗi tiến trình.1 Khi nhiều chương trình dùng chung một thư viện, máy chỉ giữ một bản trong bộ nhớ. When many processes run bash or use the standard C library: that read-only code is mapped to one shared physical copy instead of duplicated per process.1

    Tệp thường và tệp ẩn danh

    Vùng ánh xạ tới tệp thường lấy nội dung từ tệp (phần dư được đệm số 0); vùng ánh xạ tới tệp ẩn danh toàn số 0 — lần đầu chạm, nhân tìm trang nạn nhân, xoá về 0 và đánh dấu thường trú, nên gọi là trang demand-zero. Sau khi khởi tạo, trang được hoán đổi với một tệp hoán đổi (swap file); dung lượng swap chặn tổng số trang ảo có thể cấp.1

    Cấp phát động vì sao cần

    Thường ta không biết trước kích cỡ của vài cấu trúc dữ liệu cho tới khi chạy. Cấp phát mảng với kích cỡ cứng là ý tồi; cấp phát động cho phép kích cỡ chỉ bị giới hạn bởi lượng bộ nhớ ảo còn trống.1

  2. malloc / free

    Cấp phát động — phân mảnh, danh sách rỗi, và gộp khối Xin–trả bộ nhớ — vì sao bộ nhớ bị vụn và cách gộp lại Dynamic allocation — fragmentation, free lists, coalescing

    Kẻ thù của tận dụng heap là phân mảnh (fragmentation): phân mảnh trong (internal) khi khối cấp lớn hơn tải trọng (do căn chỉnh hay cỡ tối thiểu), và phân mảnh ngoài (external) khi tổng chỗ rỗi đủ nhưng không khối rỗi nào đủ lớn. Để theo dõi khối, bộ cấp phát dùng danh sách rỗi ngầm (implicit free list): mỗi khối có một header một từ ghi kích cỡ và bit đã-cấp — vì căn chỉnh 8 byte nên 3 bit thấp luôn bằng 0 và được tận dụng.1

    Dùng heap lâu, bộ nhớ dễ bị vụn: nhiều mảnh rỗi nhỏ rải rác, cộng lại thì đủ nhưng không mảnh nào đủ to cho yêu cầu. Để dễ quản, máy ghi chú ngay trong mỗi khối rằng nó to bao nhiêu và còn rỗi hay đã dùng. Nhớ nhé: bộ nhớ dùng lâu dễ vụn; gộp các mảnh rỗi cạnh nhau sẽ đỡ vụn.

    The enemy of heap utilization is fragmentation: internal (an allocated block larger than its payload, from alignment or a minimum size) and external (enough free space in total, but no single free block large enough). To track blocks, allocators use an implicit free list: each block has a one-word header recording size and an allocated bit — with 8-byte alignment the low 3 bits are always 0 and are reused for flags.1

    Bạn gặp nó ở đâuWhere you meet it Khi chọn chính sách đặt khối — first fit, next fit (do Knuth đề xuất), hay best fit — bạn đang đánh đổi tốc độ lấy tận dụng; best fit thường tận dụng tốt hơn nhưng phải quét cả heap.17 Chọn cách tìm chỗ trống nhanh hay chọn chỗ vừa khít nhất — luôn phải đánh đổi. When choosing a placement policy — first fit, next fit (proposed by Knuth), or best fit — you trade speed for utilization; best fit usually utilizes better but must scan the whole heap.17

    Gộp khối và thẻ biên

    Khi giải phóng, các khối rỗi cạnh nhau phải được gộp (coalescing) để tránh "phân mảnh giả". Gộp khối kế sau thì dễ; để gộp khối trước trong thời gian hằng, Knuth nghĩ ra thẻ biên (boundary tags) — thêm một footer sao chép header ở cuối mỗi khối.17

    Danh sách rỗi phân hạng

    Bộ cấp phát chất lượng sản phẩm như gói GNU malloc dùng segregated fits: một mảng các danh sách rỗi theo lớp kích cỡ, nên một tìm kiếm first-fit trong danh sách phân hạng xấp xỉ best-fit trên cả heap mà không phải quét toàn bộ.1

  3. garbage collection

    Thu gom rác — tự động đòi lại bộ nhớ không còn dùng Thu gom rác — máy tự dọn bộ nhớ bỏ quên Garbage collection — reclaiming memory automatically

    Một bộ thu gom rác (garbage collector) tự động trả lại các khối đã cấp mà chương trình không còn cần (gọi là rác). Nó xem bộ nhớ như một đồ thị khả đạt (reachability graph): các nút gốc (thanh ghi, biến trên ngăn xếp, biến toàn cục) trỏ vào heap; nút nào không còn đường đi từ gốc tới là rác và có thể đòi lại. Thu gom rác có từ các hệ Lisp do John McCarthy phát triển đầu thập niên 1960.16

    Trong vài ngôn ngữ, bạn không phải tự trả bộ nhớ — máy tự dọn giúp. Nó dò xem khối nào còn ai dùng tới không; khối nào không ai với tới được thì coi là rác và thu lại. Ý tưởng này có từ ngôn ngữ Lisp những năm 1960. Nhớ nhé: khối không ai với tới được nữa là rác, máy có thể tự dọn.

    A garbage collector automatically frees allocated blocks the program no longer needs (called garbage). It views memory as a reachability graph: root nodes (registers, stack variables, global variables) point into the heap; any node with no path from a root is garbage and can be reclaimed. Garbage collection dates back to the Lisp systems John McCarthy developed in the early 1960s.16

    Bạn gặp nó ở đâuWhere you meet it Trong Java, ML, Perl bạn gọi cấp phát mà không bao giờ gọi free; với C/C++ có thể cài bộ thu gom bảo thủ (conservative) trên nền malloc — nó đánh dấu đúng mọi khối khả đạt nhưng đôi khi giữ nhầm khối thật ra là rác.1 Trong Java hay Python bạn hầu như không phải tự trả bộ nhớ — máy lo việc đó. In Java, ML, and Perl you allocate but never free; for C/C++ a conservative collector can run atop malloc — it marks every reachable block correctly but may keep some that are actually garbage.1

    Thuật toán Mark&Sweep

    Bộ thu gom Mark&Sweep gốc của McCarthy gồm hai pha: pha mark đánh dấu mọi khối đã cấp còn khả đạt từ các gốc, pha sweep quét toàn heap giải phóng mọi khối đã cấp mà chưa đánh dấu. Một bit thấp còn trống trong header dùng để ghi dấu.1

    Vì sao C phải "bảo thủ"

    C không gắn kiểu cho ô nhớ, nên một int có thể trông như con trỏ. Bộ thu gom không thể biết chắc một giá trị là địa chỉ hay dữ liệu, nên phải bảo thủ đánh dấu khối đó là khả đạt — đúng về an toàn, nhưng có thể để lại phân mảnh ngoài không cần thiết.1

Ba lỗi bộ nhớ và ngộ nhận thường gặp Three common memory bugs and misconceptions

“Bộ nhớ heap mặc định đã được xoá về 0” “Heap memory is initialized to zero by default”

Ngộ nhận: vùng malloc trả về chứa toàn số 0, như biến toàn cục.

Thực tế: chỉ bộ nhớ bss (biến toàn cục chưa khởi tạo) mới được trình nạp xoá về 0; bộ nhớ heap thì không. Phải tự xoá hoặc dùng calloc.1

Myth: memory from malloc is all zeros, like a global.

Reality: only bss memory (uninitialized globals) is zeroed by the loader; heap memory is not. Zero it yourself or use calloc.1

“Con trỏ cùng cỡ với thứ nó trỏ tới” “A pointer is the same size as what it points to”

Ngộ nhận: viết sizeof(int) thay cho sizeof(int *) khi cấp mảng con trỏ cũng chẳng sao; vòng lặp <= n chỉ lệch một chút.

Thực tế: trên i7 con trỏ lớn hơn int, nên lỗi cỡ ghi đè quá mảng; lỗi lệch-một (off-by-one) ghi đè vùng kế tiếp — cả hai thường lộ ra rất muộn.1

Myth: writing sizeof(int) for sizeof(int *) when allocating a pointer array is fine; a <= n loop is only slightly off.

Reality: on the i7 a pointer is larger than an int, so the size bug writes past the array; an off-by-one bug overwrites the next region — both surface much later.1

“Trả xong vẫn dùng con trỏ được; quên free cũng không sao” “A freed pointer still works; forgetting free is harmless”

Ngộ nhận: sau free(x) vẫn đọc/ghi qua x; không gọi free thì chương trình vẫn chạy.

Thực tế: dùng khối đã giải phóng (dangling pointer) có thể ghi đè khối khác; quên free gây rò rỉ bộ nhớ (memory leak) — đặc biệt chết người với daemon và máy chủ chạy mãi không dừng.1

Myth: after free(x) you can still read/write through x; skipping free is fine.

Reality: using a freed block (a dangling pointer) can overwrite another block; forgetting free causes a memory leak — deadly for daemons and servers that never terminate.1

Tự kiểm Self-check

Năm câu hỏi để biết bạn đã nắm bộ nhớ ảo Năm câu hỏi kiểm tra nhanh Five questions to check you grasped virtual memory

Trả lời được những câu này nghĩa là bạn đã theo trọn hành trình từ địa chỉ ảo tới trang vật lý, qua dịch địa chỉ, cấp phát và các lỗi bộ nhớ.

Nếu trả lời được, nghĩa là bạn đã hiểu chương này.

Answering these means you followed the whole path from virtual address to physical page, through translation, allocation, and the memory bugs.

  1. Phân biệt địa chỉ ảo và địa chỉ vật lý; MMU và bảng trang đóng vai trò gì khi dịch giữa chúng?

    Gợi ý sâu hơn: VPN, VPO, PPN, PPO khớp với nhau thế nào, và vì sao VPO ≡ PPO?

  2. Nêu ba vai trò của bộ nhớ ảo, và cho biết vai trò nào dựa vào các bit quyền trong PTE.

    Gợi ý sâu hơn: một page fault khác một lỗi bảo vệ (protection fault) ở điểm nào?

  3. TLB giải quyết vấn đề gì, và vì sao bảng trang nhiều cấp lại tiết kiệm bộ nhớ?

    Gợi ý sâu hơn: trong hệ i7, VPN 36-bit được chia ra sao cho bốn cấp bảng?

  4. Phân mảnh trong khác phân mảnh ngoài thế nào, và gộp khối với thẻ biên giúp gì?

    Gợi ý sâu hơn: vì sao segregated fits xấp xỉ được best fit mà không phải quét cả heap?

  5. Bộ thu gom Mark&Sweep đòi lại bộ nhớ ra sao, và vì sao với C nó phải "bảo thủ"?

    Gợi ý sâu hơn: lỗi dùng con trỏ treo (dangling) và rò rỉ bộ nhớ khác nhau ở hậu quả nào?

  1. Địa chỉ "ảo" khác địa chỉ "thật" ở chỗ nào? Ai đổi từ ảo sang thật?

  2. Bộ nhớ ảo giúp được những việc gì? Kể một việc.

  3. Vì sao máy cần một "sổ tay nhớ nhanh" (TLB) khi dịch địa chỉ?

  4. Mượn bộ nhớ bằng lệnh gì, trả bằng lệnh gì? Quên trả thì sao?

  5. Sau khi trả bộ nhớ, còn dùng con trỏ cũ được không? Vì sao?

  1. How does a virtual address differ from a physical one? What role do the MMU and page table play?

  2. Name the three roles of virtual memory, and say which relies on the PTE permission bits.

  3. What problem does the TLB solve, and why do multi-level page tables save memory?

  4. How do internal and external fragmentation differ, and what do boundary tags help with?

  5. How does a Mark&Sweep collector reclaim memory, and why must it be conservative for C?

Khép lại chương Closing the chapter

Bộ nhớ ảo là một lớp gián tiếp — CPU nói địa chỉ ảo, MMU lặng lẽ dịch sang địa chỉ vật lý qua bảng trang — và chỉ một cơ chế ấy vừa đệm, vừa quản lý, vừa bảo vệ bộ nhớ. Hiểu nó là hiểu vì sao malloc và mmap chạy được, và vì sao con trỏ hỏng lại kết thúc bằng "segmentation fault".1

Bộ nhớ ảo là một trò khéo giấu phía sau: bạn nói địa chỉ ảo, máy đổi ra chỗ thật. Một trò mà làm được ba việc: tiết kiệm, gọn gàng, an toàn. Nhớ nhé: hiểu bộ nhớ ảo thì con trỏ và bộ nhớ hết còn là bí ẩn.

Virtual memory is a layer of indirection — the CPU speaks virtual addresses, the MMU quietly translates them to physical ones through a page table — and that one mechanism caches, manages, and protects memory at once. Understanding it is understanding why malloc and mmap work, and why a bad pointer ends in a "segmentation fault".1