6.4 - ניהול זכרון - הרצאה

הקדמה¶

בפרק 2 למדנו על paging וזכרון וירטואלי ברמה הרעיונית - מה זה page table, איך כתובת וירטואלית מתורגמת לכתובת פיזית, ומדוע כל process חושב שהוא לבד בעולם. בפרק 5 השתמשנו ב-mmap כדי למפות זכרון ולעבוד עם קבצים ממופים, ולמדנו על fork וprocesses.

עכשיו הגיע הזמן לצלול פנימה ולהבין איך הקרנל של לינוקס באמת מנהל זכרון. מה קורה כשprocess ניגש לזכרון שלא מופה? איך הקרנל מחליט איזה page פיזי להקצות? מה קורה כשנגמר הRAM?

ניהול זכרון פיזי¶

הדף - page¶

היחידה הבסיסית ביותר בניהול זכרון של לינוקס היא הpage (page). בארכיטקטורת x86 גודל הpage הוא 4KB (4096 בתים). כל הזכרון הפיזי מחולק לpages, וכל הallocations, השחרורים, והמיפויים עובדים ביחידות של pages.

זה לא במקרה - ה-MMU (יחידת ניהול הזכרון בחומרה) עובד עם pages. ה-page tables שלמדנו עליהם בפרק 2 ממפים pages וירטואליים לpages פיזיים. אז טבעי שגם הקרנל ינהל את הזכרון בגרנולריות של pages.

struct page - הייצוג של page פיזי בקרנל¶

לכל page פיזי במערכת יש מבנה נתונים שמייצג אותו בקרנל - הstruct שנקרא struct page. אם למחשב יש 8GB של RAM, יש בערך 2 מיליון pages, ולכן יש 2 מיליון מופעים של struct page במערך גלובלי.

הנה הstruct (מפושט):

struct page {
    unsigned long flags;        // flags: dirty, locked, active, slab...
    atomic_t _refcount;         // reference count - how many users hold the page
    struct address_space *mapping;  // if the page belongs to a file - pointer to the file
    pgoff_t index;              // if the page belongs to a file - the offset in the file
    struct list_head lru;       // LRU list for page replacement
    // ... many more fields
};

כמה שדות חשובים:

flags - דגלים שמתארים את מצב הpage. האם הוא dirty (שונה ולא נכתב חזרה לדיסק)? האם הוא נעול? האם הוא ב-slab cache? יש עשרות דגלים אפשריים.
_refcount - מונה הפניות. כל עוד מישהו משתמש בpage, המונה גדול מאפס. כשהמונה מגיע לאפס, אפשר לשחרר את הpage.
mapping - אם הpage הוא חלק מקובץ (file-backed page), השדה הזה מצביע על הקובץ שהpage שייך אליו.
index - ההיסט של הpage בתוך הקובץ.

המקצה החבר - buddy allocator¶

הקרנל צריך דרך יעילה להקצות ולשחרר pages פיזיים. הפתרון של לינוקס הוא ה-buddy allocator (מקצה החבר).

הרעיון פשוט ואלגנטי: המקצה מנהל רשימות חופשיות (free lists) של בלוקים בגדלים שהם חזקות של 2. יש רשימה של בלוקים בגודל 1 page, רשימה של בלוקים בגודל 2 pages, רשימה של 4 pages, 8, 16, 32, וכן הלאה עד 1024 pages (4MB בx86).

כשהקרנל צריך להקצות, למשל, page אחד:

הוא מחפש ברשימה של בלוקים בגודל 1 page.
אם הרשימה ריקה - הוא הולך לרשימה של בלוקים בגודל 2, לוקח בלוק, ומפצל אותו לשניים. הpage אחד הולך למבקש, הpage השני חוזר לרשימת הבלוקים בגודל 1.
אם גם רשימת הבלוקים בגודל 2 ריקה - הוא מפצל בלוק בגודל 4 לשניים, ואז מפצל את אחד מהם שוב, וכן הלאה.

כששוחררים page, המקצה בודק את ה"חבר" (buddy) שלו - הpage השכן שהיה חלק מאותו בלוק גדול יותר. אם גם החבר חופשי, הם מתמזגים לבלוק גדול יותר. התהליך ממשיך רקורסיבית כלפי מעלה.

אפשר לראות את מצב ה-buddy allocator בכל רגע נתון:

cat /proc/buddyinfo

הפלט נראה משהו כזה:

Node 0, zone   Normal   1234   567   234   89   34   12   5   2   1   0   0

המספרים מייצגים כמה בלוקים חופשיים יש בכל גודל (מ-1 page בצד שמאל עד 1024 pages בצד ימין).

אזורי זכרון - memory zones¶

לא כל הזכרון הפיזי שווה. חלק מהחומרה יכול לגשת רק לחלקים מסוימים של הזכרון (למשל, התקני DMA ישנים יכולים לגשת רק ל-16MB הראשונים). לכן לינוקס מחלק את הזכרון הפיזי לאזורים (zones):

ZONE_DMA - 16MB הראשונים. שמור להתקני ISA DMA ישנים שיכולים לגשת רק לכתובות נמוכות.
ZONE_DMA32 - עד 4GB. להתקנים שיכולים לגשת לכתובות של 32 ביט אבל לא מעבר.
ZONE_NORMAL - הזכרון ה"רגיל". בארכיטקטורת 64 ביט, זה כל הזכרון מעל 4GB (ומתחת לגבול של ZONE_DMA32).
ZONE_HIGHMEM - קיים רק במערכות 32 ביט. בקרנל 32 ביט, הקרנל יכול לגשת ישירות רק ל-896MB הראשונים (כי הוא תופס 1GB מתוך 4GB של מרחב כתובות וירטואלי). זכרון מעל 896MB נמצא ב-ZONE_HIGHMEM וצריך מיפוי מיוחד כדי לגשת אליו. במערכות 64 ביט אין צורך בזה.

כל zone מנהל buddy allocator משלו.

ניהול זכרון וירטואלי¶

mm_struct - מתאר הזכרון של process¶

כל process בלינוקס מקבל מרחב כתובות וירטואלי משלו. המבנה שמנהל את הזכרון הוירטואלי של process הוא struct mm_struct. הוא נמצא בתוך ה-task_struct שלמדנו עליו ב-6.3 (מתזמן התהליכים).

struct mm_struct {
    pgd_t *pgd;                // pointer to the top-level page table
    atomic_t mm_users;         // how many processes share this mm
    atomic_t mm_count;         // reference count
    struct maple_tree mm_mt;   // maple tree containing all the VMAs
    unsigned long total_vm;    // total virtual pages
    unsigned long locked_vm;   // locked pages (not swappable)
    unsigned long start_code, end_code;    // code area
    unsigned long start_data, end_data;    // data area
    unsigned long start_brk, brk;          // the heap area
    unsigned long start_stack;             // start of the stack
    // ... more fields
};

השדה הכי חשוב כאן הוא pgd - המצביע לטבלת הpages ברמה העליונה. זוכרים מפרק 2 את מבנה העץ של page tables? ה-pgd הוא השורש של העץ הזה. כשהמתזמן עובר מprocess לprocess (context switch), הוא טוען את ה-pgd של הprocess החדש לתוך הרגיסטר CR3, וככה ה-MMU יודע לתרגם כתובות לפי טבלת הpages של הprocess הנוכחי.

VMA - vm_area_struct¶

בתוך מרחב הכתובות של process, לא כל כתובת תקפה. הזכרון הוירטואלי מורכב מאזורים רציפים, וכל אזור כזה מיוצג על ידי struct שנקרא vm_area_struct (בקיצור VMA).

כל שורה ב-/proc/[pid]/maps מתאימה ל-VMA אחד. למשל:

00400000-0040b000 r-xp 00000000 08:01 131074  /usr/bin/cat
00600000-00601000 rw-p 0000b000 08:01 131074  /usr/bin/cat
7f1234560000-7f1234720000 r-xp 00000000 08:01 262150  /lib/x86_64-linux-gnu/libc-2.27.so
7ffc12340000-7ffc12361000 rw-p 00000000 00:00 0       [stack]

הנה ה-struct (מפושט):

struct vm_area_struct {
    unsigned long vm_start;         // start address
    unsigned long vm_end;           // end address (exclusive)
    vm_flags_t vm_flags;            // permission flags: VM_READ, VM_WRITE, VM_EXEC
    struct file *vm_file;           // pointer to the file (if file-backed), or NULL
    unsigned long vm_pgoff;         // offset in the file (in units of pages)
    struct mm_struct *vm_mm;        // pointer back to the process's mm_struct
    const struct vm_operations_struct *vm_ops;  // operations specific to the VMA
    // ...
};

השדות החשובים:

vm_start, vm_end - טווח הכתובות של האזור. שימו לב ש-vm_end הוא exclusive (לא כולל).
vm_flags - ההרשאות. האם אפשר לקרוא (VM_READ)? לכתוב (VM_WRITE)? להריץ קוד (VM_EXEC)? האם האזור משותף (VM_SHARED)?
vm_file - אם האזור ממופה לקובץ (כמו ספריה דינמית או קובץ שמופה עם mmap), השדה מצביע על הקובץ. אם זה מיפוי אנונימי (heap, stack), השדה הוא NULL.
vm_pgoff - ההיסט בקובץ, ביחידות של pages.

העץ של הVMA-ים¶

כל ה-VMAs של process צריכים להיות מאורגנים במבנה נתונים שמאפשר חיפוש מהיר לפי כתובת. כשקורה page fault, הקרנל צריך למצוא את ה-VMA שמתאים לכתובת הפוגעת - ומהר.

עד גרסה 6.1 של הקרנל, ה-VMAs היו מאורגנים בעץ אדום-שחור (red-black tree). מגרסה 6.1 המבנה הוחלף לעץ maple (maple tree) - מבנה נתונים יעיל יותר שתוכנן במיוחד עבור טווחים.

בנוסף ל-tree, ה-VMAs מקושרים גם ברשימה מקושרת לפי סדר כתובות, כדי שיהיה קל לעבור על כולם לפי הסדר.

מה קורה כשקוראים ל-mmap¶

כשprocess קורא ל-syscall של mmap (כפי שלמדנו בפרק 5.7), הנה מה שקורה בתוך הקרנל:

הקרנל מחפש חור פנוי במרחב הכתובות הוירטואלי (כתובות שאין עליהן VMA).
הוא יוצר struct vm_area_struct חדש עם הפרמטרים שנתנו (כתובת התחלה, גודל, הרשאות, קובץ).
הוא מכניס את ה-VMA לעץ ה-maple ולרשימה המקושרת.
הוא מחזיר את כתובת ההתחלה של ה-VMA.

שימו לב מה לא קורה: שום page פיזי לא מוקצה! טבלת הpages לא מתעדכנת. הpages הוירטואליים עדיין לא ממופים לpages פיזיים. זה allocation עצלנית (lazy allocation), ורק כשהprocess באמת ניגש לאחת הכתובות האלה - אז יקרה page fault והקרנל יקצה page פיזי.

שגיאת דף - page fault¶

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

הזרימה¶

הprocess ניגש לכתובת וירטואלית - למשל, קריאה מכתובת שמופה כ-VMA אבל עדיין אין לה page פיזי.
הMMU מגלה שאין מיפוי בpage table - הוא מפעיל חריגה (exception) מסוג page fault (חריגה מספר 14 בx86, שנקראת #PF).
הקרנל תופס את החריגה - הפונקציה do_page_fault רצה. היא מקבלת את הכתובת שגרמה לpage fault ואת סיבת הpage fault (קריאה/כתיבה, user/kernel).
חיפוש VMA - הקרנל מחפש בעץ ה-maple את ה-VMA שמתאים לכתובת. הפונקציה find_vma מקבלת את ה-mm_struct ואת הכתובת, ומחזירה את ה-VMA.
אם לא נמצא VMA - הכתובת לא תקפה. הprocess ניגש לזכרון שלא שייך לו. הקרנל שולח SIGSEGV - segmentation fault. הprocess מת.
אם נמצא VMA אבל ההרשאות לא מתאימות - למשל, הprocess ניסה לכתוב לאזור שמסומן כread-only. גם כאן - SIGSEGV.
אם נמצא VMA והכל תקין - הקרנל ממשיך ל-handle_mm_fault, שמקצה page פיזי, ממלא אותו בתוכן המתאים, ומעדכן את טבלת הpages כך שהכתובת הוירטואלית ממופה לpage הפיזי החדש.
חזרה לprocess - הפקודה שגרמה ל-page fault רצה שוב. הפעם ה-MMU מוצא את המיפוי ב-page table, ותרגום הכתובת מצליח.

סוגי page faults¶

לא כל ה-page faults שווים:

שגיאה קטנה - minor fault - הpage צריך רק להיות מוקצה בזכרון. לא צריך לקרוא שום דבר מהדיסק.

דוגמאות:
- גישה ראשונה לזכרון שהוקצה עם mmap אנונימי - הקרנל מקצה page פיזי מאותחל לאפסים.
- גישה לstack שגדל - הקרנל מקצה pages חדשים ל-stack.

שגיאה גדולה - major fault - הקרנל צריך לקרוא נתונים מהדיסק. זה הרבה יותר איטי.

דוגמאות:
- גישה לpage של קובץ ממופה (file-backed mmap) שעדיין לא נטען לזכרון - הקרנל קורא את הpage מהדיסק.
- גישה לpage שהועבר ל-swap (החלפה) - הקרנל קורא אותו חזרה מ-swap.

הקצאה לפי דרישה - demand paging¶

מנגנון ה-page faults מאפשר את מה שנקרא demand paging - הpages מוקצים רק כשמישהו ניגש אליהם.

נזכר בדוגמה מפרק 5.7: כשקוראים ל-mmap על קובץ, הקרנל לא טוען את כל הקובץ לRAM. הוא רק יוצר VMA. כשהprocess ניגש לבית מסוים בקובץ, קורה page fault, הקרנל קורא את הpage המתאים מהדיסק, ממפה אותו, והprocess ממשיך. אם הקובץ הוא 1GB אבל הprocess קורא רק את 10KB הראשונים - רק שלושה pages ייטענו לזכרון.

זה גם מסביר למה הקרנל משתמש ב-mmap כדי לטעון קבצי ELF להרצה (כפי שלמדנו ב-5.7). קובץ הרצה יכול להיות גדול, אבל בהרצה רגילה רוב הקוד אף פעם לא רץ (קוד טיפול בשגיאות, פיצ'רים שלא בשימוש). עם demand paging, רק הpages שבאמת נדרשים נטענים.

העתקה-בכתיבה - Copy-on-Write¶

זוכרים מפרק 5.2 את fork? כשprocess קורא ל-fork(), נוצר process בן שהוא עותק של האב. אבל להעתיק את כל הזכרון של process זה יקר מאוד. אם לprocess יש 500MB של זכרון, לא נרצה להעתיק חצי גיגה בכל fork.

הפתרון הוא Copy-on-Write (בקיצור COW), וככה זה עובד:

ברגע ה-fork - הקרנל לא מעתיק שום page פיזי. במקום זאת, הוא יוצר mm_struct חדש לprocess הבן עם VMAs חדשים, אבל טבלאות הpages של שני הprocesses מצביעות על אותם pages פיזיים. כל הpages האלה מסומנים כ-read-only בטבלת הpages של שני הprocesses.
כל עוד שניהם רק קוראים - הכל עובד בסדר. שני הprocesses חולקים את אותו זכרון פיזי.
כשמישהו מנסה לכתוב - קורה page fault (כי הpage מסומן read-only). הקרנל מזהה שזה COW fault:
הוא מקצה page פיזי חדש.
הוא מעתיק את תוכן הpage הישן לpage החדש.
הוא מעדכן את טבלת הpages של הכותב כך שהכתובת ממופה לpage החדש, עם הרשאת כתיבה.
הpage הישן נשאר ממופה לprocess השני (ואם יש רק process אחד שמשתמש בו, גם הוא מקבל חזרה הרשאת כתיבה).
מנקודה זו - כל process יש לו עותק פרטי של אותו page, ושניהם יכולים לכתוב בלי להשפיע אחד על השני.

היופי במנגנון הזה הוא שהעתקה מתבצעת רק על pages שבאמת משתנים. אם process עושה fork ואז מיד קורא ל-exec (מה שקורה בכל פעם שמריצים פקודה מה-shell), כמעט אף page לא מועתק - כי exec מחליף את כל הזכרון בתמונה חדשה.

החלפה - swapping¶

מה קורה כשנגמר הRAM? הקרנל לא יכול פשוט לחדול מלהקצות זכרון - הprocesses ימותו. במקום זאת, הוא מעביר pages שלא בשימוש פעיל לדיסק, לאזור שנקרא swap space.

איך הקרנל מחליט מה להעביר ל-swap¶

הקרנל מנהל רשימות LRU (Least Recently Used) של pages:

רשימה פעילה - active list - הpages שנגישו לאחרונה.
רשימה לא פעילה - inactive list - הpages שלא נגישו כבר זמן מה.

הpages זזים בין הרשימות: הpage שלא נגישו אליו מספיק זמן עובר מהרשימה הפעילה ללא פעילה. הpage ברשימה הלא פעילה שניגשים אליו חוזר לפעילה.

כשצריך לשחרר זכרון, הקרנל לוקח pages מסוף הרשימה הלא פעילה - אלה הpages שלא ניגשו אליהם הכי הרבה זמן.

הדמון kswapd¶

הדמון kswapd רץ ברקע ודואג שתמיד יהיו כמה pages חופשיים זמינים. הוא לא מחכה שהזכרון ייגמר לגמרי - הוא מתחיל לפעול כשמספר הpages החופשיים יורד מתחת לסף מסוים (watermark).

הוא עובר על הרשימה הלא פעילה ומשחרר pages:

הpages של קבצים ממופים שלא השתנו - הקרנל פשוט זורק אותם. הם קיימים על הדיסק ואפשר לטעון אותם מחדש אם צריך.
הpages dirty של קבצים ממופים - הקרנל כותב אותם חזרה לקובץ ואז זורק אותם.
הpages אנונימיים (heap, stack) - אלה צריכים ללכת ל-swap space, כי אין להם קובץ על הדיסק.

הרוצח OOM - OOM Killer¶

מה קורה כשגם הRAM מלא וגם ה-swap space מלא? המערכת במצב קריטי - אי אפשר להקצות זכרון לשום דבר.

במצב כזה, הקרנל מפעיל את ה-OOM Killer (Out Of Memory Killer). זה מנגנון שבורר process ל"הריגה" כדי לשחרר את הזכרון שלו.

איך הוא בוחר את הקורבן¶

לכל process יש oom_score שאפשר לראות:

cat /proc/[pid]/oom_score

הציון מחושב לפי כמה זכרון הprocess משתמש, כמה זמן הוא רץ, ופרמטרים נוספים. הprocesses שמשתמשים בהרבה זכרון מקבלים ציון גבוה יותר ולכן סביר יותר שייבחרו.

אפשר גם לכוון את הציון ידנית:

echo -1000 > /proc/[pid]/oom_score_adj  # maximum protection (won't be killed)
echo 1000 > /proc/[pid]/oom_score_adj   # high priority for killing

ה-OOM Killer הוא מנגנון שנוי במחלוקת. מצד אחד, הוא מציל את המערכת מקריסה מוחלטת. מצד שני, הוא הורג process שלא ביקש להיהרג - וזה יכול להיות process חשוב. בשרתי production, מנהלי מערכת מגדירים oom_score_adj לprocesses קריטיים כדי להגן עליהם.

סיכום¶

בפרק הזה ראינו איך הקרנל של לינוקס מנהל זכרון ברמה העמוקה:

זכרון פיזי - מנוהל בpages של 4KB. כל page מיוצג ב-struct page. ה-buddy allocator מקצה בלוקים של pages ביעילות. הזכרון הפיזי מחולק לzones.
זכרון וירטואלי - לכל process יש mm_struct שמנהל את מרחב הכתובות שלו. אזורים רציפים מיוצגים כ-VMAs ומאורגנים בעץ maple.
שגיאות דף - page faults - המנגנון המרכזי שמחבר בין זכרון וירטואלי לפיזי. מאפשר demand paging - allocation pages רק כשבאמת צריך.
העתקה-בכתיבה - COW - מאפשר fork מהיר בלי להעתיק זכרון שלא משתנה.
החלפה - swapping - מעבירה pages לא פעילים לדיסק כשנגמר הRAM.
OOM Killer - מוצא אחרון כשממש אין יותר זכרון.

כל החלקים האלה עובדים ביחד כדי ליצור את האשליה שלכל process יש זכרון אינסופי ובלעדי - בזמן שבמציאות כולם חולקים את אותו RAM פיזי.