זהות אובייקט והשבת זיכרון מקבילית

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

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

use std::sync::atomic::{AtomicU64, Ordering};
fn tagged(index: u32, generation: u32) -> u64 {
    (u64::from(generation) << 32) | u64::from(index)
}
fn main() {
    let plain = AtomicU64::new(1);
    let seen = plain.load(Ordering::SeqCst);
    plain.store(2, Ordering::SeqCst);
    plain.store(1, Ordering::SeqCst);
    assert!(plain.compare_exchange(seen, 3, Ordering::SeqCst, Ordering::SeqCst).is_ok());
    let head = AtomicU64::new(tagged(1, 1));
    let seen = head.load(Ordering::SeqCst);
    head.store(tagged(2, 2), Ordering::SeqCst);
    head.store(tagged(1, 3), Ordering::SeqCst);
    assert!(head.compare_exchange(seen, tagged(3, 4),
        Ordering::SeqCst, Ordering::SeqCst).is_err());
}

הדור מזהה חלק מהשינויים שהמספר לבדו מסתיר, אבל מונה סופי יכול להתגלגל. צריך להגדיר מדיניות או גבול שמונע חזרה לזהות ישנה בזמן שקורא עדיין מחזיק אותה. בנוסף, tag אינו מונע מהקורא לגשת לאובייקט שכבר הושמד לפני שניסה CAS. זיהוי ABA ושמירת חיי זיכרון הן בעיות קשורות אך שונות.

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

ב־hazard pointers קורא מפרסם את האובייקט שהוא עומד להשתמש בו, מאמת מחדש שהמקור עדיין מתאים ואז ניגש אליו. צד שמשחרר סורק את הפרסומים כדי לא להשמיד אובייקט מוגן. סדר הפרסום, האימות והסריקה הוא חלק מההוכחה; החלפת פעולות אקראית ב־Acquire ו־Release אינה מספיקה בלי טיעון מלא.

ב־epoch reclamation קוראים נכנסים לתקופת קריאה מוגנת, ואובייקטים שהוסרו ממתינים עד שלא נשאר קורא מתקופה שעלולה להתייחס אליהם. נשתמש בספרייה מוכרת כדי לראות את גבול החיים בלי לממש collector חדש. הוסיפו לפרויקט crossbeam-epoch = "=0.9.18".

use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
use std::sync::{Arc, atomic::Ordering};
fn main() {
    let current = Arc::new(Atomic::new(String::from("old")));
    let reader_state = Arc::clone(&current);
    let reader = std::thread::spawn(move || {
        let guard = &epoch::pin();
        let pointer = reader_state.load(Ordering::Acquire, guard);
        // The value is immutable; the guard protects its lifetime.
        let value = unsafe { pointer.as_ref() }.unwrap();
        assert!(value == "old" || value == "new");
    });
    {
        let guard = &epoch::pin();
        let old = current.swap(Owned::new(String::from("new")), Ordering::AcqRel, guard);
        // The old pointer was removed and is not published elsewhere.
        unsafe { guard.defer_destroy(old); }
    }
    reader.join().unwrap();
    let guard = &epoch::pin();
    let last = current.swap(Shared::null(), Ordering::AcqRel, guard);
    unsafe { guard.defer_destroy(last); }
    guard.flush();
}

הקורא מחזיק guard לאורך השימוש בהפניה. המחליף אינו קורא מיד ל־Box::from_raw או ל־drop על האובייקט הישן, אלא מעביר אותו למסלול השמדה דחויה. השימוש ב־defer_destroy עדיין דורש הוכחה שהמצביע הוסר ושלא נבצע עליו השמדה נוספת. הספרייה מספקת מנגנון, ואינה יודעת אם פרסמנו עותק גולמי במקום אחר.

הקריאה flush מסייעת להעביר עבודה דחויה לפי חוזה הספרייה, ואינה הבטחה שכל destructor כבר רץ מייד. קורא שנשאר pinned זמן רב יכול לעכב reclamation ולהגדיל זיכרון שנשמר. לכן אין להחזיק guard ללא מחשבה בזמן קלט ופלט חסום או עבודה שאינה קשורה לקריאת המבנה.

הערך המשותף בדוגמה immutable. הגנת חיים אינה מסנכרנת שינוי רגיל של String משני צדדים. אם נרצה לשנות תוכן במקום להחליף אובייקט שלם, נצטרך חוזה גישה נוסף. זאת אותה הפרדה שראינו בין Arc לבין נעילת התוכן, רק עם מנגנון אחר לשמירת חיים.

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

החוזים מפורטים בתיעוד crossbeam-epoch בגרסה שנבחרה. בסקירת מבנה lock-free נדרוש תמיד תשובה לשאלה מתי הכתובת מפסיקה להיות ניתנת לגילוי ומתי מותר להחזיר אותה למקצה.