סנכרון בקרנל - kernel synchronization

מבוא

בסעיף 5.8 למדנו על מנעולים (mutexes) במרחב המשתמש - ראינו איך תהליכים ו-threads יכולים לסנכרן גישה למשאבים משותפים. עכשיו נצלול לתוך מנגנוני הסנכרון של הקרנל עצמו, ונגלה שהם הרבה יותר מורכבים.

למה? כי הקרנל מתמודד עם אתגרים שלא קיימים ב-user space:

• מספר מעבדים (CPUs) מריצים קוד קרנל בו-זמנית
• פסיקות (interrupts) יכולות לקטוע קוד קרנל בכל רגע
• חלק מההקשרים בקרנל לא יכולים לישון (interrupt handlers, softirqs)
• דדלוק בקרנל = הקפאה מוחלטת של המערכת

אין פה מנגנון הגנה שיציל אתכם - אם הקרנל נתקע, כל המערכת נתקעת. לכן הסנכרון בקרנל הוא נושא קריטי.

---

למה סנכרון בקרנל קשה יותר

ריבוי מעבדים - SMP

במערכת עם מספר מעבדים (SMP - Symmetric Multiprocessing), שני מעבדים שונים יכולים להריץ קוד קרנל באותו רגע ממש. למשל, שני תהליכים על שני מעבדים שונים יכולים לקרוא לאותו syscall ולגשת לאותו מבנה נתונים בקרנל.

ב-user space, ה-scheduler מחליף בין threads, אבל בכל רגע נתון רק thread אחד רץ (על CPU אחד). בקרנל, המצב שונה לגמרי - קוד קרנל רץ במקביל אמיתי.

פסיקות - interrupts

נניח שקוד קרנל מעדכן מבנה נתונים, ובדיוק באמצע - מגיעה פסיקה מכרטיס הרשת. ה-interrupt handler רץ על אותו CPU, ואם הוא ניגש לאותו מבנה נתונים - יש לנו בעיה.

הקשרים שלא יכולים לישון

ב-user space, mutex פשוט שולח את ה-thread לישון אם המנעול תפוס. אבל בקרנל, יש הקשרים שבהם אסור לישון:

• הקשר פסיקה - interrupt handler: לא שייך לשום תהליך, אז אי אפשר לשים אותו ב-sleep queue
• הקשר softirq ו-tasklet: מטפלים בפסיקות "רכות", גם הם לא יכולים לישון
• כשמחזיקים spinlock: כי spinlock משבית preemption, ואם נירדם נתקע

---

פעולות אטומיות - atomic operations

הרמה הבסיסית ביותר של סנכרון. עבור פעולות פשוטות כמו הגדלת מונה, אין צורך במנעול מלא - מספיקה פעולה אטומית.

הטיפוס atomic_t

#include <linux/types.h>

atomic_t counter = ATOMIC_INIT(0);

הפעולות העיקריות:

int val = atomic_read(&counter);    // קריאה אטומית
atomic_set(&counter, 42);           // כתיבה אטומית
atomic_add(5, &counter);            // counter += 5
atomic_sub(3, &counter);            // counter -= 3
atomic_inc(&counter);               // counter++
atomic_dec(&counter);               // counter--

// פעולות שגם מחזירות ערך
int old = atomic_inc_return(&counter);  // ++counter, מחזיר ערך חדש
if (atomic_dec_and_test(&counter))      // --counter, מחזיר true אם התוצאה 0

מימוש ברמת החומרה

על ארכיטקטורת x86, פעולות אטומיות מומשות באמצעות הפקודה LOCK prefix:

lock incl (%rdi)    ; atomic increment

הפקודה LOCK נועלת את ה-memory bus (או cache line ספציפי) למשך הפעולה, ומבטיחה שאף CPU אחר לא יגש לאותו כתובת באמצע.

על ארכיטקטורות אחרות, משתמשים ב-compare-and-swap (cmpxchg) או ב-load-linked/store-conditional (LL/SC).

מתי להשתמש

פעולות אטומיות מתאימות לדברים פשוטים:
- מוני התייחסות (reference counters)
- דגלים (flags)
- סטטיסטיקות פשוטות

אם צריך לעדכן מבנה נתונים מורכב - צריך מנעול אמיתי.

---

מנעולי סיבוב - spinlocks

ה-spinlock הוא המנעול הפשוט ביותר בקרנל, והשימוש הנפוץ ביותר בהקשרים שלא יכולים לישון.

העיקרון

כשתהליך מנסה לקבל spinlock שתפוס, הוא מסתובב בלולאה (spins) ובודק שוב ושוב אם המנעול התפנה. הוא לא הולך לישון - הוא פשוט ממתין בפעילות (busy-wait).

#include <linux/spinlock.h>

DEFINE_SPINLOCK(my_lock);     // הגדרה סטטית
// או
spinlock_t my_lock;
spin_lock_init(&my_lock);     // הגדרה דינמית

spin_lock(&my_lock);
// ... קטע קריטי ...
spin_unlock(&my_lock);

למה busy-wait ולא sleep?

כי spinlock משמש בהקשרים שבהם אסור לישון (interrupt handlers, softirqs). בנוסף, אם הקטע הקריטי קצר מאוד (כמה שורות קוד), ה-overhead של הרדמה והקצה מחדש גדול יותר מאשר לסובב קצת.

spinlock ופסיקות

נניח את התרחיש הבא:
1. תהליך A לוקח spinlock
2. מגיעה פסיקה על אותו CPU
3. ה-interrupt handler מנסה לקחת את אותו spinlock
4. דדלוק! - ה-handler מסתובב, אבל תהליך A לא יכול לשחרר כי ה-handler רץ על אותו CPU

הפתרון - להשבית פסיקות ביחד עם לקיחת ה-lock:

unsigned long flags;

spin_lock_irqsave(&my_lock, flags);     // נועל + משבית פסיקות + שומר מצב
// ... קטע קריטי ...
spin_unlock_irqrestore(&my_lock, flags); // משחרר + משחזר מצב פסיקות

// אם יודעים בוודאות שפסיקות מופעלות:
spin_lock_irq(&my_lock);     // נועל + משבית פסיקות
// ... קטע קריטי ...
spin_unlock_irq(&my_lock);   // משחרר + מפעיל פסיקות

השיטה irqsave בטוחה יותר כי היא שומרת את מצב הפסיקות המקורי (אולי הן כבר היו מושבתות).

spinlock על מעבד יחיד

על מערכת עם CPU אחד, אין צורך ב-spinning אמיתי - הרי אין CPU אחר שמחזיק את המנעול. במקום זה, spinlock פשוט משבית preemption על ה-CPU המקומי, מה שמבטיח שאף קוד אחר לא ירוץ עד ששוחררים את המנעול.

כללים חשובים

• החזיקו spinlock לזמן קצר ככל האפשר - כל מי שמחכה מבזבז CPU cycles
• לעולם אל תישנו בתוך spinlock - אסור לקרוא לפונקציות שעלולות לישון (kmalloc עם GFP_KERNEL, copy_from_user, וכו')
• אם צריכים לישון - השתמשו ב-mutex

---

מנעולים בקרנל - kernel mutexes

ה-mutex בקרנל דומה למה שראינו ב-user space, אבל עם כמה הבדלים חשובים.

#include <linux/mutex.h>

DEFINE_MUTEX(my_mutex);        // הגדרה סטטית
// או
struct mutex my_mutex;
mutex_init(&my_mutex);          // הגדרה דינמית

mutex_lock(&my_mutex);          // נועל, ישן אם המנעול תפוס
// ... קטע קריטי (יכול לישון!) ...
mutex_unlock(&my_mutex);        // משחרר

// גרסה שלא חוסמת:
if (mutex_trylock(&my_mutex)) {
    // הצלחנו לנעול
    mutex_unlock(&my_mutex);
}

// גרסה שניתנת להפרעה ע"י סיגנל:
if (mutex_lock_interruptible(&my_mutex) == 0) {
    // הצלחנו לנעול
    mutex_unlock(&my_mutex);
}

מתי mutex ומתי spinlock?

מאפיין	spinlock	mutex
התנהגות כשתפוס	מסתובב (busy-wait)	הולך לישון
שימוש ב-interrupt handler	כן	לא!
מותר לישון בתוכו	לא!	כן
קטע קריטי ארוך	לא מומלץ	כן
overhead כשהמנעול פנוי	מינימלי	קצת יותר

תכונות מיוחדות

ל-mutex בקרנל יש כמה תכונות שאין ל-spinlock:
- מעקב בעלות (owner tracking) - רק מי שנעל יכול לשחרר
- תמיכה ב-lockdep - מערכת הדיבאג של הקרנל יכולה לזהות סדרי נעילה שגויים
- אופטימיזציה של fast path - אם המנעול פנוי, הנעילה היא פעולה אטומית אחת בלבד

---

מנעולי קריאה-כתיבה - read-write locks

לפעמים יש מבנה נתונים שנקרא הרבה אבל נכתב מעט. למשל, טבלת ניתוב (routing table) - כל חבילת רשת צריכה לקרוא ממנה, אבל עדכונים מגיעים לעיתים רחוקות.

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

גרסת spinlock - rwlock_t

#include <linux/rwlock.h>

DEFINE_RWLOCK(my_rwlock);

// קריאה:
read_lock(&my_rwlock);
// ... קוראים מהמבנה ...
read_unlock(&my_rwlock);

// כתיבה:
write_lock(&my_rwlock);
// ... מעדכנים את המבנה ...
write_unlock(&my_rwlock);

כמו spinlock רגיל - לא ישן, מסתובב. יש גם גרסאות עם irqsave.

גרסת semaphore - rw_semaphore

#include <linux/rwsem.h>

DECLARE_RWSEM(my_rwsem);

// קריאה:
down_read(&my_rwsem);
// ... קוראים (יכולים לישון) ...
up_read(&my_rwsem);

// כתיבה:
down_write(&my_rwsem);
// ... כותבים (יכולים לישון) ...
up_write(&my_rwsem);

בעיות אפשריות

• הרעבת כותבים (writer starvation) - אם כל הזמן יש קוראים חדשים, הכותב לעולם לא מקבל תור
• ב-Linux הבעיה מטופלת - כשכותב מחכה, קוראים חדשים נחסמים גם הם

---

RCU - Read-Copy-Update

זהו מנגנון הסנכרון המתקדם ביותר ב-Linux, והוא משמש באופן נרחב ברחבי הקרנל. הרעיון הבסיסי גאוני בפשטותו.

העיקרון

• קוראים לא צריכים מנעול בכלל - אפס overhead!
• כותבים יוצרים עותק, מעדכנים אותו, ואז מחליפים את המצביע בפעולה אטומית
• הנתונים הישנים משוחררים רק אחרי שכל הקוראים סיימו (תקופת חסד - grace period)

איך זה עובד

קורא 1:  [----קורא מנתונים ישנים----]
קורא 2:       [----קורא מנתונים ישנים/חדשים----]
כותב:    עותק -> עדכון -> החלפת מצביע
                                        |--- grace period ---|
                                                              שחרור נתונים ישנים

1. הכותב מקצה עותק חדש של מבנה הנתונים
2. מעדכן את העותק החדש
3. מחליף את המצביע (פעולה אטומית - rcu_assign_pointer())
4. מחכה שכל הקוראים שהחלו לפני ההחלפה יסיימו (grace period)
5. משחרר את הנתונים הישנים

ממשק קריאה

#include <linux/rcupdate.h>

rcu_read_lock();
struct my_data *p = rcu_dereference(global_ptr);  // קריאה בטוחה של מצביע
// ... שימוש ב-p ...
// אסור לישון כאן!
rcu_read_unlock();

מה עושים rcu_read_lock() ו-rcu_read_unlock() בפועל? רק משביתים ומפעילים preemption! זה כל מה שצריך כדי להגן על הקורא. ה-overhead הוא אפסי - שתי פקודות מעבד פשוטות.

ממשק כתיבה

// החלפת מצביע (אטומית):
rcu_assign_pointer(global_ptr, new_data);

// שחרור נתונים ישנים - שתי אפשרויות:

// 1. סנכרוני - חוסם עד שכל הקוראים סיימו:
synchronize_rcu();
kfree(old_data);

// 2. אסנכרוני - קורא callback כשבטוח:
call_rcu(&old_data->rcu_head, my_rcu_callback);

דוגמה מלאה

struct my_entry {
    int key;
    int value;
    struct rcu_head rcu;
};

struct my_entry __rcu *global_entry;

// קריאה (מאוד מהירה):
int read_value(void)
{
    int val;
    rcu_read_lock();
    struct my_entry *p = rcu_dereference(global_entry);
    if (p)
        val = p->value;
    else
        val = -1;
    rcu_read_unlock();
    return val;
}

// callback לשחרור:
static void free_entry_rcu(struct rcu_head *head)
{
    struct my_entry *entry = container_of(head, struct my_entry, rcu);
    kfree(entry);
}

// כתיבה:
void update_value(int new_key, int new_value)
{
    struct my_entry *new = kmalloc(sizeof(*new), GFP_KERNEL);
    struct my_entry *old;

    new->key = new_key;
    new->value = new_value;

    old = rcu_dereference_protected(global_entry, lockdep_is_held(&update_mutex));
    rcu_assign_pointer(global_entry, new);

    if (old)
        call_rcu(&old->rcu, free_entry_rcu);
}

איפה משתמשים ב-RCU

ב-Linux RCU משמש בכל מקום:
- טבלאות ניתוב ברשת
- חיפוש קבצים במערכת הקבצים (dcache)
- רשימת מודולים טעונים
- טבלאות תהליכים
- ועוד הרבה - יש אלפי שימושים בקרנל

---

סמפורים - semaphores

#include <linux/semaphore.h>

struct semaphore sem;
sema_init(&sem, 1);    // ערך התחלתי 1 = binary semaphore (כמו mutex)
sema_init(&sem, 5);    // ערך התחלתי 5 = מאפשר 5 נועלים במקביל

down(&sem);            // ממתין (ישן) עד שהערך > 0, ואז מקטין
// ... קטע קריטי ...
up(&sem);              // מגדיל את הערך

down_interruptible(&sem);  // ניתן להפרעה ע"י סיגנל
down_trylock(&sem);        // לא חוסם

סמפורים הם מנגנון ישן יותר שהיה בקרנל לפני ש-mutex נוסף. כיום, ברוב המקרים עדיף להשתמש ב-mutex (שיש לו אופטימיזציות ומעקב טובים יותר). סמפורים עדיין שימושיים כש-counting semaphore נדרש (מספר נועלים במקביל).

---

משתנים לכל מעבד - per-CPU variables

הגישה הטובה ביותר לסנכרון היא... להימנע ממנו!

אם לכל CPU יש עותק משלו של משתנה, אין צורך בנעילה בכלל. זה בדיוק מה ש-per-CPU variables עושים.

#include <linux/percpu.h>

// הגדרה סטטית:
DEFINE_PER_CPU(int, my_counter);

// שימוש:
int cpu = get_cpu();                    // משבית preemption ומחזיר מספר CPU
per_cpu(my_counter, cpu)++;             // גישה למשתנה של ה-CPU הנוכחי
put_cpu();                              // מפעיל preemption

// או בצורה קצרה:
get_cpu_var(my_counter)++;
put_cpu_var(my_counter);

// הקצאה דינמית:
int __percpu *dynamic_counter = alloc_percpu(int);
int *ptr = per_cpu_ptr(dynamic_counter, cpu);
*ptr = 42;
free_percpu(dynamic_counter);

שימושים נפוצים

• מוני סטטיסטיקות - כל CPU מעדכן את המונה שלו, ורק כשרוצים את הסכום הכולל קוראים מכל ה-CPUs
• מטמונים (caches) - כל CPU שומר עותק מקומי של נתונים שנגישים תכופות
• מקצי זיכרון - ה-slab allocator משתמש ב-per-CPU caches

למה זה עובד

get_cpu() משבית preemption - מה שמבטיח שהתהליך לא יעבור ל-CPU אחר באמצע הגישה למשתנה. זה מספיק כי CPU אחר לא ניגש למשתנה הזה (לכל CPU יש עותק משלו).

---

מניעת דדלוקים בקרנל

דדלוק בקרנל הוא אסון - המערכת קופאת ואין דרך להתאושש (חוץ מ-restart). לכן הקרנל מספק כלים וכללים למניעת דדלוקים.

כללי ברזל

1. תמיד תנעלו מנעולים באותו סדר

// נכון - תמיד A לפני B:
spin_lock(&lock_a);
spin_lock(&lock_b);
// ...
spin_unlock(&lock_b);
spin_unlock(&lock_a);

// שגוי - עלול ליצור דדלוק!
// thread 1: lock_a -> lock_b
// thread 2: lock_b -> lock_a

2. לעולם אל תישנו כשמחזיקים spinlock

spin_lock(&my_lock);
kmalloc(size, GFP_ATOMIC);    // נכון - GFP_ATOMIC לא ישן
// kmalloc(size, GFP_KERNEL); // שגוי! GFP_KERNEL יכול לישון
spin_unlock(&my_lock);

3. אל תנסו לנעול spinlock שכבר מחזיקים (non-recursive)

spin_lock(&my_lock);
spin_lock(&my_lock);   // דדלוק! spinlock ב-Linux לא רקורסיבי

lockdep - גילוי דדלוקים בזמן ריצה

ה-Linux kernel כולל מערכת גאונית בשם lockdep (מופעלת עם CONFIG_PROVE_LOCKING) שמזהה פוטנציאל לדדלוק עוד לפני שהוא קורה.

איך? lockdep עוקב אחרי סדר הנעילות. אם הוא רואה שב-thread אחד נעלתם A ואז B, ואז ב-thread אחר נעלתם B ואז A - הוא מתריע מיד, גם אם דדלוק עדיין לא קרה בפועל.

=============================================
WARNING: possible circular locking dependency detected
5.10.0 #1 Not tainted
---------------------------------------------
process/1234 is trying to acquire lock:
 (&lock_b){+.+.}-{2:2}, at: my_function+0x42/0x100

but task is already holding lock:
 (&lock_a){+.+.}-{2:2}, at: my_function+0x20/0x100

which lock already depends on the new lock.
...

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

---

סיכום - מתי להשתמש במה

מנגנון	ישן?	הקשר פסיקה?	ביצועים	שימוש טיפוסי
פעולות אטומיות - atomic operations	לא	כן	הכי מהיר	מונים, דגלים
spinlock	לא	כן	מהיר	קטעים קריטיים קצרים
mutex	כן	לא	טוב	קטעים קריטיים ארוכים
rwlock	לא	כן	מהיר לקוראים	נתונים שנקראים הרבה
RCU	לא (קוראים)	כן (קוראים)	הכי מהיר לקוראים	רשימות, טבלאות
משתנים per-CPU	לא	כן	הכי מהיר (אין נעילה)	מונים, מטמונים

הכלל הפשוט: השתמשו במנגנון הקל ביותר שמספיק. אם מספיק atomic - אל תשתמשו ב-spinlock. אם מספיק spinlock - אל תשתמשו ב-mutex. ואם אפשר per-CPU - זו האפשרות הטובה ביותר.