8.5 - זכרון וירטואלי בחומרה - הרצאה

הקדמה¶

זכרון וירטואלי עבר עלינו כחוט השני לאורך הקורס:
- בפרק 2.5 למדנו על מנגנון הpaging - איך כתובות וירטואליות מתורגמות לכתובות פיזיות דרך טבלאות pages
- בפרק 2.6 למדנו על page faults - מה קורה כשpage לא ממופה
- בפרק 6.4 למדנו איך הקרנל של לינוקס מנהל את טבלאות הpages, VMAs, ו-demand paging

עכשיו הגיע הזמן ללמוד את הצד של החומרה - איך המעבד עצמו מתרגם כתובות, מהו הTLB, ואיך 4 רמות של טבלאות pages עובדות ב-x86-64.

הליכת טבלאות דפים - page table walk ב-x86-64¶

ב-x86-64, המעבד משתמש ב-4 רמות של טבלאות דפים (4-level paging). כל פעם שהמעבד צריך לתרגם כתובת וירטואלית לפיזית, הוא צריך לעבור 4 טבלאות - הליכה של 4 גישות לזכרון.

אוגר CR3¶

האוגר CR3 מכיל את הכתובת הפיזית של טבלת הpages הראשית (PML4) של הprocess הנוכחי. כשהקרנל מבצע context switch (כזכור מפרק 2.4 ו-6.3), הוא טוען CR3 עם הכתובת של טבלאות הpages של הprocess החדש.

; the kernel loads CR3 on a context switch:
mov cr3, rax    ; rax holds the physical address of the PML4 of the new process

חלוקת כתובת וירטואלית¶

כתובת וירטואלית ב-x86-64 היא 48 ביט (למרות שאוגרים הם 64 ביט - הביטים 48-63 הם sign extension של ביט 47). החלוקה:

Virtual address 48 bit:

+--------+---------+---------+---------+---------+----------+
| sign   | PML4    | PDPT    | PD      | PT      | Offset   |
| extend | Index   | Index   | Index   | Index   |          |
+--------+---------+---------+---------+---------+----------+
  16 bit   9 bit    9 bit    9 bit     9 bit     12 bit

  63..48   47..39   38..30   29..21    20..12    11..0

ביטים 47-39 (9 ביט): אינדקס ב-PML4 (Page Map Level 4) - 512 כניסות
ביטים 38-30 (9 ביט): אינדקס ב-PDPT (Page Directory Pointer Table) - 512 כניסות
ביטים 29-21 (9 ביט): אינדקס ב-PD (Page Directory) - 512 כניסות
ביטים 20-12 (9 ביט): אינדקס ב-PT (Page Table) - 512 כניסות
ביטים 11-0 (12 ביט): היסט (offset) בתוך הpage = 4096 בתים = 4KB

תהליך התרגום¶

  CR3 (physical address of PML4)
   |
   v
+--PML4--+     +-PDPT--+     +--PD---+     +--PT---+
|  [0]   |     | [0]   |     | [0]   |     | [0]   |
|  [1]   |     | [1]   |     | [1]   |     | [1]   |
|  ...   |     | ...   |     | ...   |     | ...   |
|  [i] --+---->| [j] --+---->| [k] --+---->| [l] --+----> physical page frame
|  ...   |     | ...   |     | ...   |     | ...   |            |
| [511]  |     | [511] |     | [511] |     | [511] |            |
+---------+     +-------+     +-------+     +-------+            |
                                                                  |
   i = bits 47-39    j = bits 38-30   k = bits 29-21  l = bits 20-12
                                                                  |
                                            physical address = frame + offset (bits 11-0)

צעד אחר צעד:
1. קרא את CR3 - מקבל כתובת פיזית של PML4
2. חשב אינדקס i מביטים 47-39 של הכתובת הוירטואלית
3. קרא PML4[i] מהזכרון - מקבל כתובת פיזית של PDPT
4. חשב אינדקס j מביטים 38-30
5. קרא PDPT[j] מהזכרון - מקבל כתובת פיזית של PD
6. חשב אינדקס k מביטים 29-21
7. קרא PD[k] מהזכרון - מקבל כתובת פיזית של PT
8. חשב אינדקס l מביטים 20-12
9. קרא PT[l] מהזכרון - מקבל כתובת של מסגרת דף פיזית (page frame)
10. חבר את מסגרת הpage עם הoffset (ביטים 11-0) - מקבל כתובת פיזית סופית

כל תרגום = 4 גישות לזכרון. בלי TLB, כל גישה לזכרון של התוכנית הייתה דורשת 4 גישות נוספות רק לתרגום!

כניסות בטבלאות דפים - page table entries¶

כל כניסה בכל אחת מ-4 הטבלאות היא 8 בתים (64 ביט). המבנה:

63  62..52  51..12              11..9  8  7  6  5  4  3  2  1  0
+---+------+--------------------+-----+--+--+--+--+--+--+--+--+
|NX | Avail| Physical Address   |Avail|G |PS|D |A |CD|WT|US|RW|P|
+---+------+--------------------+-----+--+--+--+--+--+--+--+--+

הביטים החשובים:

ביט	שם	תפקיד
0	Present (P)	האם הpage ממופה? 0 = לא -> page fault
1	Read/Write (R/W)	0 = קריאה בלבד, 1 = קריאה וכתיבה
2	User/Supervisor (U/S)	0 = רק ring 0, 1 = גם ring 3
5	Accessed (A)	המעבד מסמן 1 כשהpage נקרא. הקרנל משתמש בזה לאלגוריתם ההחלפה (LRU)
6	Dirty (D)	המעבד מסמן 1 כשהpage נכתב. הקרנל יודע שצריך לכתוב את הpage לדיסק לפני שמשחרר אותו
7	Page Size (PS)	ברמת PD: אם 1, זהו page ענק של 2MB (לא ממשיכים ל-PT)
63	No Execute (NX)	1 = אסור להריץ קוד מהpage הזה. קריטי לאבטחה - כזכור מפרק 6.11

כמה ביטים מותאמים אישית:
- ביט P: כשהקרנל רוצה לממש demand paging (כזכור מפרק 6.4), הוא מסמן P=0. כשהתוכנית ניגשת לpage, המעבד מייצר page fault, והקרנל מקצה page פיזי ומעדכן את הכניסה.
- ביט NX: מונע buffer overflow attacks שבהם התוקף שם shellcode על ה-stack ומנסה להריץ אותו. עם NX=1 על ה-stack, הרצת קוד מה-stack גורמת ל-page fault.
- ביטים A ו-D: נקבעים על ידי החומרה אוטומטית. הקרנל קורא אותם ומאפס אותם מדי פעם. זה מאפשר לקרנל לדעת אילו pages "חמים" (בשימוש) ואילו "קרים" (לא ניגשו אליהם מזמן).

הTLB - Translation Lookaside Buffer¶

הבעיה¶

כפי שראינו, תרגום כתובת דורש 4 גישות לזכרון. אם כל load/store בתוכנית דורש 4 loads נוספים רק לתרגום, הביצועים ייפגעו פי 5. זה לא מקובל.

הפתרון¶

הTLB הוא cache שמחזיק תרגומים אחרונים של כתובות וירטואליות לפיזיות. במקום לעשות page table walk מלא, המעבד קודם בודק את הTLB:

Virtual address
       |
       v
    +-----+
    | TLB | ----> Hit?  --(yes)--> Physical address (one cycle!)
    +-----+
       |
      (no)
       |
       v
   Page Table Walk (4 memory accesses, ~100 cycles)
       |
       v
   Physical address + TLB update

מאפייני TLB¶

TLB	כניסות (בערך)	זמן גישה
L1 ITLB (הוראות)	64-128	1 מחזור
L1 DTLB (נתונים)	64-96	1 מחזור
L2 TLB (משותף)	1024-2048	7-8 מחזורים

כל כניסה בTLB ממפה מספר page וירטואלי (VPN) למספר מסגרת פיזית (PFN), כולל הרשאות (R/W, U/S, NX).

הTLB הוא בדרך כלל fully associative (כל כניסה יכולה להיות בכל מקום) - כי הוא קטן מספיק שchip area לא מהווה בעיה, ו-conflict misses בTLB הם יקרים מאוד (page table walk).

שטיפת TLB ב-context switch¶

כש-context switch קורה (כזכור מפרקים 2.4 ו-6.3), CR3 משתנה. טבלאות הpages של הprocess החדש שונות, אז כל הכניסות בTLB של הprocess הקודם כבר לא תקפות. הפתרון הנאיבי: שטיפה מלאה של הTLB (TLB flush) - מחיקת כל הכניסות.

הבעיה: אחרי TLB flush, כל גישה ראשונה לpage היא TLB miss ודורשת page table walk. הprocess שחוזר לרוץ אחרי context switch מתחיל עם TLB "קר" - ביצועים גרועים למשך כמה אלפי הוראות.

מזהה תהליך - PCID (Process Context ID)¶

הפתרון המודרני: כל כניסה בTLB מתויגת עם מזהה תהליך (PCID) של 12 ביט. כש-context switch קורה, לא צריך לשטוף את הTLB - הכניסות הישנות נשארות אבל לא מתאימות (PCID שונה). אם הprocess חוזר לרוץ, הכניסות שלו עדיין שם.

TLB entry:
+------+------+------+----------+
| PCID | VPN  | PFN  | Permissions |
+------+------+------+----------+
|  3   | 0x7F | 0x1A | R/W, U   |
|  5   | 0x7F | 0x2B | R, U     |  <-- same VPN, different process!
|  3   | 0x80 | 0x1B | R/W, U   |
+------+------+------+----------+

הprocess עם PCID=3 מחפש VPN=0x7F ומוצא PFN=0x1A. הprocess עם PCID=5 מחפש אותו VPN ומוצא PFN=0x2B. שני הprocesses יכולים לשתף את הTLB בלי שטיפה!

דפים ענקיים - huge pages¶

הבעיה¶

הpage הרגיל הוא 4KB. תוכנית שמשתמשת ב-2GB RAM צריכה 524,288 pages. זה אומר:
- 524,288 כניסות בטבלאות pages
- טבלאות הpages עצמן תופסות מקום ב-RAM
- הTLB מחזיק רק 64-2048 כניסות - TLB misses תכופים

הפתרון: הpages הגדולים יותר¶

x86-64 תומך בpages ענקיים:

סוג	גודל	ביטי offset	רמות page table walk
הpage הרגיל	4 KB	12 ביט	4 רמות
דף ענק - huge page	2 MB	21 ביט	3 רמות (PD מצביע ישירות על page)
דף ענק ענק - gigantic page	1 GB	30 ביט	2 רמות (PDPT מצביע ישירות על page)

הpage הענק של 2MB: במקום 512 כניסות בPT שמצביעות על 512 pages של 4KB, כניסה אחת בPD (עם ביט PS=1) מצביעה ישירות על מסגרת פיזית של 2MB.

היתרונות:
- פחות כניסות TLB: 2GB דורשים 1024 כניסות (עם 2MB pages) במקום 524,288 (עם 4KB)
- page table walk קצר יותר: 3 רמות במקום 4
- פחות זכרון לטבלאות pages: פחות רמות = פחות טבלאות

שימושים¶

בסיסי נתונים: PostgreSQL, MySQL - מחזיקים מאגרי זכרון גדולים
מכונות וירטואליות: KVM/QEMU - RAM של הVM
חישוב מדעי (HPC): מערכים ענקיים

Transparent Huge Pages (THP)¶

הקרנל של לינוקס (כזכור מפרק 6.4) יכול אוטומטית להשתמש בpages ענקיים כשזה משתלם - בלי שהתוכנית צריכה לבקש. זה נקרא THP.

הקרנל מחפש מקרים שבהם 512 pages רגילים עוקבים ממופים לכתובות פיזיות עוקבות, ומאחד אותם לpage ענק אחד של 2MB.

שימוש מפורש:

#include <sys/mman.h>

// allocate 2MB with an explicit huge page
void *ptr = mmap(NULL, 2 * 1024 * 1024,
                 PROT_READ | PROT_WRITE,
                 MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
                 -1, 0);

5 רמות - 5-level paging¶

הבעיה¶

עם 4 רמות ו-48 ביט של כתובת וירטואלית, מרחב הכתובות הוא 256 TB. זה נשמע הרבה, אבל שרתים מודרניים מתקרבים לגבול הזה (במיוחד מכונות וירטואליות ובסיסי נתונים גדולים).

הפתרון¶

החל ממעבדי Intel Ice Lake (2019), יש תמיכה ב-5-level paging:

Virtual address 57 bit:
PML5 Index (9) | PML4 Index (9) | PDPT (9) | PD (9) | PT (9) | Offset (12)

מרחב כתובות: 128 PB (Petabytes) - מספיק לזמן רב.

המחיר: page table walk של 5 גישות לזכרון במקום 4. אבל TLB מסתיר את זה ברוב המקרים.

IOMMU - טבלאות pages להתקנים¶

יש עוד בעיה: התקני חומרה (כמו כרטיסי רשת ודיסקים) יכולים לגשת לRAM ישירות דרך DMA (Direct Memory Access), כזכור מפרק 6.8 על דרייברים. בלי הגנה, התקן דרייבר פגום או זדוני יכול לקרוא/לכתוב לכל מקום בRAM.

הIOMMU (Input/Output Memory Management Unit) הוא יחידת תרגום כתובות להתקנים. בדיוק כמו שהMMU מתרגם כתובות של processes, הIOMMU מתרגם כתובות של התקני DMA. כל התקן "רואה" מרחב כתובות וירטואלי משלו, וטבלאות pages (שמנוהלות על ידי הקרנל) קובעות לאילו כתובות פיזיות יש להתקן גישה.

סיכום¶

מושג	הסבר
אוגר CR3	מצביע לטבלת הpages הראשית (PML4)
הליכת טבלאות - page table walk	4 גישות לזכרון לתרגום כתובת
ביט Present (P)	האם הpage ממופה - 0 גורם ל-page fault
ביט NX (No Execute)	מניעת הרצת קוד מpages מסוימים
ביטים Accessed/Dirty	מסומנים אוטומטית ע"י החומרה
TLB	הcache תרגומי כתובות - חוסך page table walks
שטיפת TLB - TLB flush	מחיקת כניסות ב-context switch
PCID	מזהה process בTLB - נמנע משטיפה מלאה
דפים ענקיים - huge pages	2MB או 1GB - פחות TLB misses
THP	הקרנל משתמש בpages ענקיים אוטומטית
IOMMU	טבלאות pages להתקנים (DMA)

בפרק הבא (8.6) נחבר את כל מה שלמדנו בפרויקט סיכום - נכתוב קוד שמשתמש בידע על cache, branch prediction, ו-false sharing, ונמדוד ביצועים עם perf.