Eşzamanlı veri yapıları düzgün şekilde nasıl test edilir

 (matklad.github.io)
2 puan yazan GN⁺ 2024-07-07 | 1 yorum | WhatsApp'ta paylaş
  • Bozuk bir Rust eşzamanlı sayaç örneği üzerinden, sıradan thread yük testlerinin kaçırdığı sorunların yeniden üretilebilir ve küçültülebilir yürütme sırası kontrolü ile nasıl ortaya çıkarılacağı gösteriliyor
  • Test amaçlı AtomicU32 sarmalayıcısı pause() ekliyor; managed thread ise atomik işlemlerden önce ve sonra durup testin seçtiği sıraya göre yeniden devam ediyor
  • Basit testlerde 100 thread’in her biri 100 kez artırma yaparak beklenen 10000 yerine 9598 gibi bir başarısızlık üretmesi mümkün, ancak bu zamanlamaya bağlı olduğundan yeniden üretmek, hata ayıklamak ve küçültmek zor
  • arbtest tabanlı özellik testi, aynı seed ile aynı interleaving’i yeniden üretip başarısızlık örneğini 0: increment, 1: increment, 0: unpause, 1: unpause düzeyine kadar küçültüyor
  • Aynı yapı exhaustigen ile genişletildiğinde en fazla 5 artırmaya kadar tüm interleaving’ler listelenebiliyor ve fetch_add düzeltmesinden sonra 81133 interleaving’in tamamı geçiyor

Atomik olmayan eşzamanlı sayaç

  • Örnek Rust’ın AtomicU32 tipini kullanıyor, ancak increment() işlemi load sonrasında store(value + 1) yaptığı için artırma işleminin kendisi atomik değil
  • Counter yapısı basit
    • value: AtomicU32
    • increment() değeri SeqCst ile okuyup, okunan değere 1 ekleyerek tekrar yazıyor
    • get() mevcut değeri SeqCst ile okuyor
  • İki thread aynı değeri okuduktan sonra aynı artırılmış sonucu yazabilir, böylece bir güncelleme kaybolur

Neden sıradan thread testleri yetersiz kalır

  • En basit doğrulama, birden çok thread’in aynı sayacı tekrar tekrar artırıp son değeri kontrol etmesidir
    • thread_count = 100
    • increment_count = 100
    • beklenen değer 10000
  • Örnek çalıştırmada left: 9598, right: 10000 ile başarısız oluyor
  • Bu yaklaşım büyük ölçüde zamanlama/scheduling detaylarına bağlı
    • Aynı hatayı deterministik biçimde yeniden üretmek zor
    • Hata ayıklaması zor
    • Thread sayısı ya da artırma sayısı azaltıldığında test şans eseri geçebilir; bu yüzden başarısızlık örneğini küçültmek zorlaşır

Özellik tabanlı test ile interleaving ele almak

  • Özellik tabanlı test (PBT), durum makinesi testleriyle iyi örtüşür
    • Rastgele girdiler üretmek kolaydır
    • Eşzamanlı çalışmanın sonucunun sıralı yürütme modeliyle aynı olması gerektiği şeklinde bir özellik tanımlanabilir
    • Başarısız girdileri küçültme ihtiyacıyla da uyumludur
  • Zorluk, gerçek OS thread’lerini istenen anda tek tek adım adım ilerletmenin kolay olmamasıdır
  • Çözüm, her turda rastgele bir thread seçip onu bir adım ilerleten bir yapıdır
    • Bir thread’in load ve store adımları arasına başka bir thread sokulabilmelidir
    • Bunun için thread’leri doğrudan kontrol eden bir managed thread API’si kuruluyor

Test amaçlı AtomicU32 ve pause ekleme

  • Test derlemesinde std::sync::atomic::AtomicU32 yerine özel managed_thread::AtomicU32 kullanılıyor
    • #[cfg(test)] use managed_thread::AtomicU32
    • #[cfg(not(test))] use std::sync::atomic::AtomicU32
  • Sarmalayıcı AtomicU32, load() ve store() öncesinde ve sonrasında pause() çağırıyor
    • load: pause() → gerçek load → pause()
    • store: pause() → gerçek store → pause()
  • Bu ekleme noktaları sayesinde test, atomik işlemlerin çevresinde thread’leri durdurup yeniden başlatarak yürütme sırasını kontrol edebiliyor

managed thread API’sinin yapısı

  • Test, std::thread::scope içinde iki managed thread oluşturuyor
    • Scoped thread kullanıldığı için stack’teki yerel veriler ödünç alınabiliyor
    • spawn(scope, &counter) gibi sayaç referansı durum olarak geçiriliyor
  • Managed thread, başlangıçta sabit bir main fonksiyonu çalıştırmak yerine, kontrol thread’inin submit() ile gönderdiği closure’ı çalıştırıyor
    • t.submit(|c| c.increment())
    • Thread, kendi T durumu üzerinde bu closure’ı yürütüyor
  • Test döngüsü, entropi kaldığı sürece her thread için rastgele bir eylem seçiyor
    • Thread durmuşsa unpause()
    • Durmamışsa submit() ile increment() çalıştırılıyor
    • Sıralı model counter_model de aynı sayıda artırılıyor
  • Sonunda tüm thread’ler join() ile bekleniyor ve counter_model ile gerçek counter.get() karşılaştırılıyor

pause ve unpause uygulaması

  • pause(), test edilen Counter API’sini değiştirmemek için thread_local! kullanarak mevcut managed thread’in bağlamını buluyor
    • Bağlam Arc<SharedContext> ile paylaşılıyor
    • SharedContext, Mutex<State> ve Condvar içeriyor
  • Durumlar Ready, Running, Paused olarak ayrılıyor
    • Ready: sonraki closure’ı bekleme durumu
    • Running: managed thread çalışıyor
    • Paused: pause() noktasında durmuş durumda
  • Managed thread pause() noktasına ulaştığında durumu Runningden Pauseda çevirip condition variable ile kontrol thread’ine haber veriyor
  • unpause(), durumu Pauseddan Runninge çeviriyor, managed thread’i uyandırıyor ve yeniden Running dışına çıkana kadar bekliyor
    • Bu, kontrol thread’i ile managed thread’in aynı anda serbestçe çalışmasını engelliyor
    • Her anda yalnızca birinin çalışmasını sağlayarak belirsizliği azaltıyor

Hatanın yeniden üretilmesi ve küçültülmesi

  • arbtest çalıştırması bozuk sayaçta bir hata buluyor
    • Örnek başarısızlıkta model değeri 4, gerçek değer 3
    • Başarısızlık seed’i 0x4fd7ddff00000020
  • Aynı seed verilirse aynı interleaving yeniden elde edilebildiği için hatayı yeniden üretmek kolaylaşıyor
  • .minimize() kullanıldığında başarısızlık daha kısa bir çalıştırmaya indirgeniyor
    • Nihai minimal örneğin seed’i 0x9c2a13a600000001
    • Minimal trace dört adımdan oluşuyor
      • 0: increment
      • 1: increment
      • 0: unpause
      • 1: unpause
  • Bu minimal örnekte beklenen değer 2, gerçek değer ise 1; böylece load/store tabanlı artırmanın kusuru açığa çıkıyor

Tüm interleaving’leri listeleyerek genişletme

  • Aynı yapı, rastgele interleaving yerine listeleme tabanlı hale getirilebiliyor
  • exhaustigen kullanılarak en fazla 5 artırmaya kadar tüm interleaving’leri tarayan bir test yazılıyor
    • Test, boşuna tekrarları önlüyor ve her zaman thread’e ya unpause ya da increment gönderilecek şekilde kuruluyor
  • Bozuk uygulama aynı hatayı buluyor
    • Örnek başarısızlık left: 2, right: 1
  • Counter::increment() işlemi fetch_add(1, SeqCst) olarak düzeltilince test geçiyor
    • AtomicU32 sarmalayıcısına da fetch_add() öncesi ve sonrası için pause() ekleniyor
    • Çalıştırma çıktısı all 81133 interleavings are fine!
    • Çalışma süresi real 8.65s, CPU 8.16s, RSS 63.91mb

Zayıf bellek modeli ve model checking’e doğru genişletme

  • Mevcut oyuncak uygulamadaki AtomicU32, gerçek atomik işlemlere delege ediyor
  • Genişletme fikri, her atomik için yazılmış değerlerin kümesini tutup okuma sırasında zayıf bellek modeli ile tutarlı rastgele bir değer döndürmek
  • Interleaving araması da rastgele olmaktan daha akıllı hale getirilebilir
    • Model checking yaklaşımıyla anlamlı biçimde farklı tüm interleaving’lerin ele alınıp alınmadığı kontrol edilebilir
    • Generate All The Things yaklaşımında olduğu gibi, küçük kapsamda tüm interleaving’ler listelenebilir

Neden shrinking olmadan da küçültme mümkün

  • Kullanılan arbtest, alışıldık PRNG arayüzüne benzese de sonlu bir PRNG kullanıyor
    • Sürekli rastgele değer istendiğinde bir noktada Err(OutOfEntropy) döndürüyor
    • Bu yüzden test kodunda ? ve while !rng.is_empty() görünüyor
  • Test entropiyi tükettiğinde erken bittiği için, kullanılabilir entropi azaltıldığında test çalışması da kısalıyor
  • İç uygulama kavramsal olarak &mut &[u8] yapısına yakın
    • Her rastgele sayı isteğinde byte dilimi küçülüyor
    • Başlangıç dilimi ne kadar kısa olursa test o kadar basit oluyor
  • Bu yaklaşım sayesinde ayrıca bir shrinking mantığını elle yazmadan da başarısızlık örnekleri kısaltılabiliyor
  • Örnek kaynak kodu properly-concurrent deposunda yer alıyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-07
Hacker News yorumları

  • Rust tarafında benzer bir yaklaşımla Temper adlı bir kütüphane geliştiriliyor: https://github.com/reitzensteinm/temper/tree/main
    Ancak Rust'ın tüm bellek modelinin ortaya çıkardığı tuhaf çıkarımları modellemek için çok daha ileri gitmek gerekiyor; her thread'in hangi yazmaları fark ettiğini izleyen bir deftere ihtiyaç var. Atomik bellek sırası, okuma/yazma fence'leri vb. durumlara bağlı olarak, X yazmasını fark ettiysen Y yazmasını da mutlaka fark etmiş olman gerektiği gibi garantiler ortaya çıkabiliyor.
    C++/Rust bellek modeli test örneklerini en çok derleyenlerden biri olduğunu düşünüyorum; kitaplarda, C++ standardında, Stack Overflow'da, bloglarda vb. bulunabilecek neredeyse her şeyi toplamış. Örneğin Mara Bos'un Rust Atomics and Locks kitabı için dosya burada: https://github.com/reitzensteinm/temper/blob/main/memlog/tes...
    Yazıda bahsedilen Loom benzer ama çok daha olgun bir kütüphane; mutex veya kuyruk gibi daha üst seviye bileşenleri kapsamlı biçimde test etmeyi sağlıyor: https://github.com/tokio-rs/loom Ancak bellek modelinin kendisini Temper kadar ayrıntılı modellemiyor; test örneklerini Loom'a taşımayı düşünüyordum.
    Will Wilson'ın FoundationDB test sunumundan esinlenildi; kendisi şu anda Antithesis'te, rastgele Docker container'ları üzerinde bu tarz testler yürüten hipervizör tabanlı bir çözüm geliştiriyor: https://www.youtube.com/watch?v=4fFDFbi3toc, https://antithesis.com/
    Önümüzdeki 10 yılda bu alanın çok daha büyüyeceğine güçlü biçimde inanıyorum. WebAssembly, rastgele yazılımları derleyebilecek kadar eksiksiz, ama Antithesis benzeri bir şey geliştirmeyi, daha önce veritabanı yayınlamış seçkin bir ekibin 5 yıllık projesi hâline getirmeyecek kadar da basit olan tam isabet bir noktada duruyor.

  • Rust ile paylaşımlı bellek atomik snapshot uyguladım ve otomatik testleri de olabildiğince ciddiye aldım: https://github.com/kaymanb/todc/tree/main/todc-mem
    Başta yazıda geçen Loom'u kullandım, ama daha sonra shuttle'a geçtim: https://github.com/tokio-rs/loom, https://github.com/awslabs/shuttle
    shuttle, Loom gibi kapsamlı arama yapmak yerine rastgeleleştirilmiş bir yaklaşım kullanıyor; yine de scheduler, hata bulma konusunda olasılıksal garantiler sağlıyor. Deneyimlerime göre shuttle daha hızlıydı ve daha karmaşık test senaryolarına ölçeklenebildi.
    Yazıdaki yönteme benzer şekilde, belirli bir schedule test hatasına yol açarsa rastgele sayı seed'i kaydedilebiliyor. Başarısız bir testi hızlıca yeniden üretebilme yeteneği çok önemli; daha önce yakalanıp düzeltilen hatalar için açık test case'leri yazmayı mümkün kılıyor: https://github.com/kaymanb/todc/blob/0e2874a70ec8beed8fae773...

  • Kotlin/Java tarafında JetBrains'in Lincheck'i bu iş için iyi bir kütüphane: https://github.com/JetBrains/lincheck
    Özellikle bildirimsel olmasını ve doğrusallaştırılabilirlik sonucunu çıktı olarak verme biçimini seviyorum.

  • C++ için de Loom benzeri bir kütüphane olup olmadığını merak ediyorum. Test etmek istediğim kilitsiz veri yapıları var.

  • Doğru anladıysam, bu yaklaşımın zayıf ilerleme garantisi konusunda sınırları var
    Metindeki hesaplama tamamen önemsiz değil, ancak gerçek donanım ve gerçek zamanlayıcılarda belirli bir CPU’da kesintiye uğrama olasılığı son derece düşük olan bir cmpxchg döngüsünü düşünebiliriz. CPU sayısı n ise en kötü durumda ilerleme olasılığı 1/n olurken, bu test yönteminde 1/t^p oluyor. Burada t görev sayısıdır ve CPU sayısından çok daha büyük olabilir; p ise o döngü gövdesindeki duraklatma sayısıdır ve kolayca 3 ya da daha fazla olabilir. Bu kadarı, pratikte çalışan bir algoritmayı bozukmuş gibi göstermeye yeter
    Tersine, zayıf ilerlemeyi bir hata olarak yakalamak için güçlü ilerleme gerektirmek isteseniz bile, bu yöntem pek kullanışlı bir araç sunuyor gibi görünmüyor
    Yine de birçok eşzamanlılık sorunu için kesinlikle faydalı

    • 1/t^p doğru gibi gelmiyor; bence sadece 1/t olarak görülmeli. Sonuçta t zaman geçtiğinde görevlerden biri mutlaka ilerlemiş olacaktır ve t görev varsa ilerleyen görevin benim görevim olma olasılığı 1/tdir
      Temel karışıklık, kesintiye uğramanın mutlaka CAS’te kaybetmek anlamına gelmemesinde gibi görünüyor

  • “Dürüst olmak gerekirse burada biraz ön bilgi var. Inline assembly ile çok lanetli işler yapmadıkça gerçek thread oluşturmayı önleyebilecekmişiz gibi görünmüyor. Bir şey pause() fonksiyonunu çağırıyor ve biz onu ileride talimat gelene kadar durmuş halde tutmak istiyorsak, bu iş testin stack’inden ayrı bir stack’i koruyan bir thread içinde gerçekleşmeli” kısmı hakkında, bir tür asenkron runtime kullanılamaz mı diye merak ediyorum
    Atomik işlemleri enstrümante ederek cooperative multitasking elde ediliyor gibi görünüyor. Daha fazla kahve içmem gerekebilir ama threadsiz yapmak daha basit görünüyor

    • Async kullanmak rahat olurdu, ancak başka bir gereksinim de test edilen yazılımın dışarıdan gözlenen API’sini değiştirmek istememek. Async “bulaşıcı” olduğundan, senkron API için senkron implementasyon kullanmak gerekir

  • Bu yaklaşımın bir dezavantajı, test edilen kodun kendisinin test koduna uyacak şekilde değiştirilmesi gerekmesi
    İki thread başlatıp ptrace ile tek adım çalıştırarak komut yürütmelerini “rastgele” araya sokarak da aynı şey yapılabilir gibi. rr’nin chaos modu gibi bir yöntem
    Ancak bazı komutlar atomik olmayabileceğinden, emülasyon olmadan mümkünse bile “atomik mikrokod” biriminde tek adım yürütmenin bir yoluna ihtiyaç var gibi görünüyor

    • Antithesis’in hipervizörü gibi geliyor

  • Loom kullanmak için koşullu derleme gerekiyor gibi ve tek bir kütüphaneyi test ederken sorun olmaz ama epey müdahaleci
    #[cfg(loom)]
    pub(crate) use loom::sync::atomic::AtomicUsize;
    #[cfg(not(loom))]
    pub(crate) use std::sync::atomic::AtomicUsize;
    Kendi zamanlayıcısını daha iyi kullanmaya izin veren bir dil var mı merak ediyorum

  • Gerçekten titiz olmak istenirse testi ptrace ile çalıştırıp thread’leri tek adım ilerleterek komut düzeyinde farklı interleaving’ler oluşturulabilir gibi. Böyle bir yöntemi gerçekten görmüş olan var mı merak ediyorum
    Buradaki gibi kodu enstrümante edemediğimiz durumlarda, kara kutu testi için bir alternatif var mı?

    • Asenkron sinyal işleyici testlerinde böyle bir yöntemi kullandım, ama orada kombinasyon sayısı çok daha elverişli. Ana thread n komut çalıştırıyorsa, sinyali araya sokmadan önce 0’dan n komuta kadar çalıştıran n çalıştırma yeterli oluyor; ardından sinyal işleyici sonuna kadar çalışıyor, sonra ana thread de sonuna kadar çalışıyor. Toplam süre O(n^2)
      Ancak her biri n komut çalıştıran t thread varsa ve her sınırda birbirlerini durdurabiliyorlarsa, gerçekçi n değerlerinde bu yaklaşıma erişmek zor. İlginç davranış gösteren işlemleri seçip simüle ederek azaltmak gerekecek gibi

  • Oldukça havalı görünüyor, bir ara denemeliyim. Ancak her tür hatayı yakalayamaz. Her pause() çağrısında thread’ler arasında senkronizasyon oluştuğu için bazı data race sorunları gizlenmez mi? Rust’ta sorun olmayabilir