סנכרון בקרנל - פתרון

תרגיל 1 - בחירת מנגנון סנכרון

א. מונה חבילות רשת (מתעדכן מ-interrupt handler)

פעולות אטומיות (atomic_t) - זה מונה פשוט שצריך רק increment. פעולה אטומית מספיקה ועובדת גם מהקשר פסיקה. אלטרנטיבה טובה: per-CPU counter - כל CPU סופר בנפרד, ורק כשרוצים את הסכום הכולל קוראים מכולם. זה אפילו יעיל יותר כי אין cache line bouncing בין מעבדים.

// אפשרות 1 - atomic:
atomic_t packet_count = ATOMIC_INIT(0);
// ב-interrupt handler:
atomic_inc(&packet_count);

// אפשרות 2 - per-CPU (עדיף):
DEFINE_PER_CPU(unsigned long, packet_count);
// ב-interrupt handler:
this_cpu_inc(packet_count);

ב. עץ עם הקצאת זיכרון בעדכון

mutex - כי העדכון כולל הקצאת זיכרון (kmalloc עם GFP_KERNEL), שיכולה לישון. ב-spinlock אסור לישון, אז mutex הוא הבחירה הנכונה. זה גם מתרחש רק ב-process context (יצירת קובץ ע"י משתמש).

static DEFINE_MUTEX(tree_mutex);

void create_file_entry(...)
{
    mutex_lock(&tree_mutex);
    struct node *n = kmalloc(sizeof(*n), GFP_KERNEL);
    // ... insert to tree ...
    mutex_unlock(&tree_mutex);
}

ג. טבלת ניתוב - קריאות תכופות, כתיבות נדירות

RCU - זה בדיוק ה-use case הקלאסי של RCU. הקריאות (lookup לכל חבילה) קורות אלפי פעמים בשנייה ולא צריכות מנעול בכלל. העדכונים הנדירים משלמים מחיר גבוה יותר (העתקה ו-grace period), אבל זה קורה רק לעיתים רחוקות. בפועל, זה בדיוק מה שלינוקס עושה עם טבלת הניתוב.

ד. מונה context switches לכל CPU

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

DEFINE_PER_CPU(unsigned long, cs_count);

// בקוד ה-scheduler:
this_cpu_inc(cs_count);

ה. רשימת חיבורים - גישה מ-interrupt handler ומ-process context

spinlock עם irqsave - כי interrupt handler צריך לגשת לרשימה (אסור mutex), וגם process context ניגש (צריך להגן מפני פסיקות). חייבים להשתמש ב-spin_lock_irqsave כדי למנוע דדלוק בין process context ל-interrupt handler.

DEFINE_SPINLOCK(conn_lock);

// ב-interrupt handler:
spin_lock(&conn_lock);
// ... search list ...
spin_unlock(&conn_lock);

// ב-process context:
spin_lock_irqsave(&conn_lock, flags);
// ... add/remove connection ...
spin_unlock_irqrestore(&conn_lock, flags);

---

תרגיל 2 - זיהוי דדלוקים

קטע א - דדלוק! (ABBA)

כן, יש סכנת דדלוק.

הסיטואציה:
1. Thread 1 נועל lock_a, מנסה לנעול lock_b
2. Thread 2 נועל lock_b, מנסה לנעול lock_a
3. שניהם מסתובבים לנצח - דדלוק!

תיקון: תמיד לנעול באותו סדר:

// Thread 2 - תוקן:
spin_lock(&lock_a);    // אותו סדר כמו Thread 1
spin_lock(&lock_b);
// ... work ...
spin_unlock(&lock_b);
spin_unlock(&lock_a);

קטע ב - דדלוק! (פסיקה)

כן, יש סכנת דדלוק.

הסיטואציה:
1. my_process_func נועלת data_lock
2. בדיוק באותו רגע, מגיעה פסיקה על אותו CPU
3. my_irq_handler מנסה לנעול data_lock
4. ה-handler מסתובב, אבל הפונקציה שמחזיקה את המנעול לא יכולה לרוץ (כי ה-handler רץ על אותו CPU) - דדלוק!

תיקון: ב-process context, להשתמש ב-spin_lock_irqsave:

void my_process_func(void)
{
    unsigned long flags;
    spin_lock_irqsave(&data_lock, flags);   // משבית פסיקות!
    // ... read shared data ...
    spin_unlock_irqrestore(&data_lock, flags);
}

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

קטע ג - תקין

אין סכנת דדלוק.

הקוד תקין - mutex יכול לישון, ו-kmalloc עם GFP_KERNEL יכול לישון, ושניהם ב-process context. מותר לישון כשמחזיקים mutex (בניגוד ל-spinlock). הקוד גם מטפל נכון בכשלון (משחרר את ה-mutex לפני return).

קטע ד - שגוי! (לא דדלוק, אבל באג)

זו שגיאה, לא בהכרח דדלוק.

mutex_lock יכול לישון, ו-interrupt handler לא יכול לישון (הוא לא שייך לתהליך, אז אין לו process context שניתן להרדים). זה יגרום ל-kernel oops/panic.

תיקון: להשתמש ב-spinlock (עם irqsave אם צריך):

void my_interrupt_handler(int irq, void *dev)
{
    spin_lock(&my_spinlock);
    // ... update data ...
    spin_unlock(&my_spinlock);
}

---

תרגיל 3 - השלמת קוד עם spinlock

#include <linux/list.h>
#include <linux/slab.h>
#include <linux/spinlock.h>

struct message {
    struct list_head list;
    char data[256];
    int priority;
};

static LIST_HEAD(message_queue);
static DEFINE_SPINLOCK(queue_lock);    /* spinlock כי get_message נקראת מ-interrupt */

int add_message(const char *data, int priority)
{
    struct message *msg;
    unsigned long flags;

    /* GFP_ATOMIC כי ייתכן שנקראים מהקשר שלא יכול לישון,
       או כי ננעול spinlock מיד אחרי. אם add_message נקראת
       רק מ-process context, אפשר GFP_KERNEL ולהקצות לפני הנעילה. */
    msg = kmalloc(sizeof(*msg), GFP_ATOMIC);
    if (!msg)
        return -ENOMEM;

    strscpy(msg->data, data, sizeof(msg->data));
    msg->priority = priority;

    spin_lock_irqsave(&queue_lock, flags);
    list_add_tail(&msg->list, &message_queue);
    spin_unlock_irqrestore(&queue_lock, flags);

    return 0;
}

struct message *get_message(void)
{
    struct message *msg = NULL;
    unsigned long flags;

    spin_lock_irqsave(&queue_lock, flags);
    if (!list_empty(&message_queue)) {
        msg = list_first_entry(&message_queue, struct message, list);
        list_del(&msg->list);
    }
    spin_unlock_irqrestore(&queue_lock, flags);

    return msg;
}

הסבר:
- השתמשנו ב-spinlock כי get_message נקראת מ-interrupt handler (שלא יכול לישון)
- השתמשנו ב-irqsave כי add_message עלולה להיקרא מ-process context ואז פסיקה שקוראת ל-get_message תיצור דדלוק
- השתמשנו ב-GFP_ATOMIC כי ההקצאה קורית בהקשר שצריך spinlock (אם ההקצאה תמיד מ-process context, אפשר להקצות לפני הנעילה עם GFP_KERNEL)

---

תרגיל 4 - RCU

struct config {
    int max_connections;
    int timeout_ms;
    char server_name[64];
    struct rcu_head rcu;
};

static struct config __rcu *current_config;

// callback לשחרור אחרי grace period:
static void config_free_rcu(struct rcu_head *head)
{
    struct config *cfg = container_of(head, struct config, rcu);
    kfree(cfg);
}

// קריאת הגדרות:
int get_timeout(void)
{
    int timeout;

    rcu_read_lock();
    struct config *cfg = rcu_dereference(current_config);
    if (cfg)
        timeout = cfg->timeout_ms;
    else
        timeout = -1;     // ברירת מחדל אם אין הגדרות
    rcu_read_unlock();

    return timeout;
}

// עדכון הגדרות:
int update_config(int max_conn, int timeout, const char *name)
{
    struct config *new_cfg, *old_cfg;

    new_cfg = kmalloc(sizeof(*new_cfg), GFP_KERNEL);
    if (!new_cfg)
        return -ENOMEM;

    new_cfg->max_connections = max_conn;
    new_cfg->timeout_ms = timeout;
    strscpy(new_cfg->server_name, name, sizeof(new_cfg->server_name));

    // מחליפים את המצביע (אטומית):
    old_cfg = rcu_dereference_protected(current_config,
                                         lockdep_is_held(&config_update_mutex));
    rcu_assign_pointer(current_config, new_cfg);

    // משחררים את ההגדרות הישנות אחרי grace period:
    if (old_cfg)
        call_rcu(&old_cfg->rcu, config_free_rcu);

    return 0;
}

הסבר:
- rcu_read_lock() / rcu_read_unlock() - רק משביתים/מפעילים preemption. אפס overhead.
- rcu_dereference() - קוראת את המצביע בצורה בטוחה (מבטיחה שהקומפיילר וה-CPU לא יסדרו מחדש את הקריאה)
- rcu_assign_pointer() - מעדכנת את המצביע באופן אטומי עם memory barrier
- call_rcu() - רושמת callback שייקרא אחרי שכל הקוראים הקיימים סיימו (grace period). רק אז בטוח לשחרר את הזיכרון הישן.

הערה: בפועל, צריך גם mutex על פעולות הכתיבה כדי למנוע מצב ששני writers מתחרים. הוספתי התייחסות ל-config_update_mutex ב-rcu_dereference_protected.

---

תרגיל 5 - ניתוח lockdep

א. אילו שני מנעולים מעורבים?

• table_lock - מנעול על טבלת הניתוב
• socket_lock - מנעול על ה-socket

ב. סדר הנעילה שגורם לבעיה:

נתיב 1 (process_packet):
1. נועל socket_lock (ב-process_packet+0x15)
2. מנסה לנעול table_lock (ב-update_routing_table+0x28)

נתיב 2 (update_routing_table):
1. נועל table_lock (ב-update_routing_table+0x28)
2. קורא ל-send_notification שנועל socket_lock (ב-send_notification+0x35)

כלומר: נתיב 1 נועל socket -> table, ונתיב 2 נועל table -> socket.

ג. למה זה עלול ליצור דדלוק?

זה דדלוק ABBA קלאסי:
1. Thread A (process_packet) נועל socket_lock, מנסה לנעול table_lock
2. Thread B (update_routing_table) נועל table_lock, מנסה לנעול socket_lock
3. שניהם ממתינים אחד לשני לנצח

ד. איך לתקן?

יש כמה אפשרויות:

1. לקבוע סדר נעילה אחיד - למשל, תמיד table_lock לפני socket_lock. אז ב-process_packet צריך לנעול table_lock לפני socket_lock.

2. ב-update_routing_table, לא לקרוא ל-send_notification בתוך הנעילה - לשחרר את table_lock לפני שליחת ההודעה, או לדחות את ההודעה לאחרי שחרור המנעול.

3. לאחד את שני המנעולים למנעול אחד - אם הם תמיד משמשים יחד, אולי אפשר מנעול אחד (אבל זה מקטין את ה-concurrency).

אפשרות 2 היא בדרך כלל הטובה ביותר - לצמצם את העבודה שנעשית בתוך הנעילה.