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

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

לכל אחד מהתרחישים הבאים, בחרו את מנגנון הסנכרון המתאים ביותר (atomic, spinlock, mutex, rwlock, RCU, per-CPU) והסבירו למה:

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

ב. מבנה נתונים מורכב (עץ) שמעודכן כשמשתמש יוצר קובץ חדש. העדכון כולל הקצאת זיכרון.

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

ד. מונה שסופר את מספר ה-context switches שקרו על כל CPU.

ה. רשימה מקושרת של חיבורי רשת פתוחים. interrupt handler צריך לחפש חיבור ברשימה, ותהליך user space צריך להוסיף ולהסיר חיבורים.

---

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

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

קטע א

// Thread 1:
spin_lock(&lock_a);
spin_lock(&lock_b);
// ... work ...
spin_unlock(&lock_b);
spin_unlock(&lock_a);

// Thread 2:
spin_lock(&lock_b);
spin_lock(&lock_a);
// ... work ...
spin_unlock(&lock_a);
spin_unlock(&lock_b);

קטע ב

// Interrupt handler:
void my_irq_handler(int irq, void *dev)
{
    spin_lock(&data_lock);
    // ... update shared data ...
    spin_unlock(&data_lock);
}

// Process context:
void my_process_func(void)
{
    spin_lock(&data_lock);
    // ... read shared data ...
    spin_unlock(&data_lock);
}

קטע ג

void allocate_resource(void)
{
    mutex_lock(&resource_mutex);
    void *mem = kmalloc(4096, GFP_KERNEL);
    if (!mem) {
        mutex_unlock(&resource_mutex);
        return;
    }
    // ... use memory ...
    mutex_unlock(&resource_mutex);
}

קטע ד

void my_interrupt_handler(int irq, void *dev)
{
    mutex_lock(&my_mutex);
    // ... update data ...
    mutex_unlock(&my_mutex);
}

---

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

הקוד הבא מנהל רשימה מקושרת של הודעות בקרנל. הוסיפו את מנגנון הסנכרון המתאים. שימו לב - הפונקציה get_message נקראת גם מתוך interrupt handler.

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

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

static LIST_HEAD(message_queue);
/* TODO: הגדירו את מנגנון הסנכרון המתאים */

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

    msg = kmalloc(sizeof(*msg), /* TODO: באיזה דגל? */);
    if (!msg)
        return -ENOMEM;

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

    /* TODO: נעילה */
    list_add_tail(&msg->list, &message_queue);
    /* TODO: שחרור */

    return 0;
}

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

    /* TODO: נעילה */
    if (!list_empty(&message_queue)) {
        msg = list_first_entry(&message_queue, struct message, list);
        list_del(&msg->list);
    }
    /* TODO: שחרור */

    return msg;
}

---

תרגיל 4 - RCU

הקוד הבא מנהל הגדרת תצורה (configuration) שנקראת לעיתים קרובות מאוד אבל מתעדכנת לעיתים רחוקות. השלימו את הקוד כך שישתמש ב-RCU:

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

static struct config __rcu *current_config;

// קריאת הגדרות (נקראת אלפי פעמים בשנייה):
int get_timeout(void)
{
    int timeout;
    /* TODO: קריאה בטוחה עם RCU */
    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));

    /* TODO: החלפת ושחרור עם RCU */

    return 0;
}

---

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

הודעת lockdep הבאה הופיעה בלוג הקרנל. קראו אותה ותענו על השאלות:

============================================
WARNING: possible circular locking dependency detected
5.15.0-debug #1 Not tainted
--------------------------------------------
NetworkManager/1842 is trying to acquire lock:
ffff8881234567 (&table_lock){+.+.}-{2:2}, at: update_routing_table+0x28/0x100

but task is already holding lock:
ffff8881234890 (&socket_lock){+.+.}-{2:2}, at: process_packet+0x15/0x80

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #1 (&socket_lock){+.+.}-{2:2}:
       lock_acquire+0x1a8/0x340
       _raw_spin_lock+0x2c/0x40
       send_notification+0x35/0x90
       update_routing_table+0x68/0x100

-> #0 (&table_lock){+.+.}-{2:2}:
       lock_acquire+0x1a8/0x340
       _raw_spin_lock+0x2c/0x40
       update_routing_table+0x28/0x100
       process_packet+0x42/0x80

שאלות:

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

ב. מה סדר הנעילה שגורם לבעיה? תארו את שני ה-threads ואת סדר הנעילות שלהם.

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

ד. איך הייתם מתקנים את הבעיה?