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

הקדמה¶

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

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

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

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

אוגר CR3¶

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

; הקרנל טוען CR3 ב-context switch:
mov cr3, rax    ; rax מכיל את הכתובת הפיזית של PML4 של התהליך החדש

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

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

כתובת וירטואלית 48 ביט:

+--------+---------+---------+---------+---------+----------+
| 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) בתוך הדף = 4096 בתים = 4KB

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

  CR3 (כתובת פיזית של PML4)
   |
   v
+--PML4--+     +-PDPT--+     +--PD---+     +--PT---+
|  [0]   |     | [0]   |     | [0]   |     | [0]   |
|  [1]   |     | [1]   |     | [1]   |     | [1]   |
|  ...   |     | ...   |     | ...   |     | ...   |
|  [i] --+---->| [j] --+---->| [k] --+---->| [l] --+----> מסגרת דף פיזית
|  ...   |     | ...   |     | ...   |     | ...   |            |
| [511]  |     | [511] |     | [511] |     | [511] |            |
+---------+     +-------+     +-------+     +-------+            |
                                                                  |
   i = bits 47-39    j = bits 38-30   k = bits 29-21  l = bits 20-12
                                                                  |
                                            כתובת פיזית = מסגרת + 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. חבר את מסגרת הדף עם ה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)	האם הדף ממופה? 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 כשהדף נקרא. הקרנל משתמש בזה לאלגוריתם ההחלפה (LRU)
6	Dirty (D)	המעבד מסמן 1 כשהדף נכתב. הקרנל יודע שצריך לכתוב את הדף לדיסק לפני שמשחרר אותו
7	Page Size (PS)	ברמת PD: אם 1, זהו דף ענק של 2MB (לא ממשיכים ל-PT)
63	No Execute (NX)	1 = אסור להריץ קוד מהדף הזה. קריטי לאבטחה - כזכור מפרק 6.11

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

הTLB - Translation Lookaside Buffer¶

הבעיה¶

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

הפתרון¶

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

כתובת וירטואלית
       |
       v
    +-----+
    | TLB | ----> Hit?  --(כן)--> כתובת פיזית (מחזור אחד!)
    +-----+
       |
      (לא)
       |
       v
   Page Table Walk (4 גישות לזכרון, ~100 מחזורים)
       |
       v
   כתובת פיזית + עדכון TLB

מאפייני TLB¶

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

כל כניסה בTLB ממפה מספר דף וירטואלי (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 משתנה. טבלאות הדפים של התהליך החדש שונות, אז כל הכניסות בTLB של התהליך הקודם כבר לא תקפות. הפתרון הנאיבי: שטיפה מלאה של הTLB (TLB flush) - מחיקת כל הכניסות.

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

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

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

כניסת TLB:
+------+------+------+----------+
| PCID | VPN  | PFN  | הרשאות   |
+------+------+------+----------+
|  3   | 0x7F | 0x1A | R/W, U   |
|  5   | 0x7F | 0x2B | R, U     |  <-- אותו VPN, תהליך אחר!
|  3   | 0x80 | 0x1B | R/W, U   |
+------+------+------+----------+

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

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

הבעיה¶

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

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

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

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

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

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

שימושים¶

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

Transparent Huge Pages (THP)¶

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

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

שימוש מפורש:

#include <sys/mman.h>

// הקצאת 2MB עם דף ענק מפורש
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:

כתובת וירטואלית 57 ביט:
PML5 Index (9) | PML4 Index (9) | PDPT (9) | PD (9) | PT (9) | Offset (12)

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

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

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

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

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

סיכום¶

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

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