TLB Shootdown Memperluas Perubahan Page Table ke Banyak CPU

Mengubah entry page table di memori tidak otomatis menghentikan setiap translasi yang berasal dari entry tersebut. CPU yang sebelumnya memakai mapping dapat menyimpannya di translation lookaside buffer, atau TLB. Pada sistem multiprosesor, CPU lain dapat memiliki salinan cache masing-masing, sehingga perubahan mapping dapat memerlukan koordinasi di luar CPU yang mengubah page table.

Linux memperlihatkan pemisahan ini melalui interface TLB flush. Setelah state page table berubah, kode arsitektur harus membuat translasi yang terdampak tidak dapat digunakan pada setiap CPU yang relevan sebelum software bergantung pada mapping baru atau melepaskan memori yang masih dapat dijangkau mapping lama.

Page table dan TLB merupakan state yang terpisah

Page table adalah state translasi di memori yang dikelola sistem operasi. TLB adalah state cache lokal prosesor yang berasal dari tabel tersebut. Write ke page table mengubah mapping otoritatif, tetapi entry TLB yang sudah ada dapat terus menyediakan translasi sebelumnya sampai invalidasi yang ditetapkan arsitektur berlaku.

State logisnya dapat terlihat seperti ini:

page table:
virtual page V -> physical page B

TLB CPU 0:
V -> B

TLB CPU 1:
V -> A   <- stale

TLB CPU 2:
tidak ada entry

CPU 2 akan memperoleh translasi melalui mekanisme translasi normal saat berikutnya mengakses V. CPU 1 berbeda: jika entry stale tetap valid, CPU itu masih dapat mencapai page A walaupun state di memori sekarang mencatat page B.

Ini adalah persoalan koherensi translasi. Masalah tersebut terpisah dari koherensi data cache. Mesin dengan cache coherent dapat menjaga load dan store biasa tetap koheren sambil tetap memerlukan operasi arsitektural eksplisit untuk menghentikan translasi alamat yang stale.

Invalidasi lokal tidak mencakup TLB pada CPU lain

Instruksi invalidasi biasanya bekerja pada state translasi yang terkait dengan logical processor yang mengeksekusinya, sesuai scope yang ditetapkan arsitektur. Pada x86, misalnya, INVLPG menginvalidasi entry untuk page yang memuat operand pada logical processor yang mengeksekusi instruksi tersebut, dengan detail PCID dan global mapping yang ditentukan oleh arsitektur.

Aksi lokal itu tidak cukup ketika address space yang sama pernah berjalan pada CPU lain yang masih dapat menyimpan entry terkait. Sistem operasi harus mengatur agar prosesor remote yang relevan menjalankan invalidasi yang diperlukan atau memakai mekanisme lain yang didukung arsitektur dengan scope setara.

Koordinasi ini umum disebut TLB shootdown:

CPU 0 mengubah mapping
        |
        v
tentukan CPU yang mungkin menyimpannya
        |
        v
kirim permintaan invalidasi
        |
        +------> CPU 1 menginvalidasi
        |
        +------> CPU 3 menginvalidasi
        |
        v
tunggu completion yang diperlukan
        |
        v
translasi lama tidak dapat digunakan lagi

Mekanisme persisnya bergantung pada arsitektur dan kernel. Inter-processor interrupt merupakan salah satu teknik implementasi yang umum, tetapi properti correctness lebih luas daripada satu metode signaling: CPU yang mungkin memakai state translasi stale harus melewati titik invalidasi yang diwajibkan.

Pelacakan CPU membatasi scope shootdown

Mengirim permintaan invalidasi ke setiap CPU dapat benar pada banyak kondisi, tetapi scope itu terlalu luas untuk banyak perubahan mapping. Kernel melacak prosesor yang dapat memiliki state translasi untuk sebuah address space dan memakai informasi tersebut untuk membatasi pekerjaan remote.

Pelacakan ini merupakan kebijakan sistem operasi di atas primitive invalidasi arsitektural. Implementasi dapat memanfaatkan fakta seperti apakah sebuah address space pernah berjalan pada CPU tertentu, apakah CPU sedang memakainya, dan apakah state cache sebelumnya sudah dihentikan.

Optimasi tersebut tidak boleh melemahkan aturan lifetime. CPU yang tidak disertakan dalam shootdown harus tidak dapat memakai entry stale yang bertentangan dengan perubahan page table. Bookkeeping kernel karena itu menjadi bagian dari correctness, walaupun arsitektur prosesor tidak menentukan struktur data atau kebijakan scheduling Linux.

Range flush mengubah profil biaya

Linux menyediakan interface TLB dengan scope berbeda, termasuk flush seluruh address space, range, dan satu page. Kode arsitektur memetakan interface tersebut ke mekanisme prosesor yang tersedia.

Invalidasi sempit dapat mempertahankan entry TLB yang tidak terkait sehingga mengurangi hilangnya translasi cache yang masih berguna. Flush luas dapat memerlukan lebih sedikit operasi invalidasi ketika region besar berubah. Dokumentasi Linux x86 menjelaskan trade-off ini secara eksplisit: invalidasi per-page menghindari pembuangan entry yang tidak terkait, sedangkan full flush dapat lebih murah daripada menjalankan banyak invalidasi spesifik page.

Tidak ada threshold tetap yang portabel. Organisasi TLB, instruksi invalidasi, PCID atau address-space tagging, heuristik kernel, dan ukuran range yang berubah semuanya memengaruhi keputusan. Hasil pengukuran pada satu model prosesor bukan jaminan arsitektural untuk model lain.

Biaya performa juga memiliki dua bagian. Ada pekerjaan koordinasi langsung, seperti meminta dan menyelesaikan invalidasi remote, serta pekerjaan refill setelah entry TLB yang berguna ikut dibuang. Biaya tersebut bergantung pada workload dan implementasi, sehingga keberadaan shootdown tidak menyiratkan penalti latensi tertentu.

Address-space tag mengurangi invalidasi yang tidak terkait

Prosesor modern dapat mengaitkan translasi cache dengan address-space identifier. Pada x86, PCID memungkinkan entry TLB dari address space berbeda tetap berada di cache melewati sebagian pergantian page table. Arsitektur lain menyediakan mekanisme tagging serupa dengan nama dan aturan berbeda.

Tag mengurangi kebutuhan membuang translasi hanya karena eksekusi berpindah antar-address space. Tag tidak menghapus kebutuhan invalidasi terhadap entry yang mapping-nya benar-benar berubah. Sebaliknya, tag membuat scope invalidasi lebih presisi: software dapat menargetkan state translasi milik address space tertentu ketika arsitektur menyediakan operasi yang sesuai.

Linux juga dapat menunda sebagian pekerjaan invalidasi sampai CPU kembali ke address space yang terdampak. Penundaan seperti ini aman hanya jika CPU tidak dapat memakai translasi stale sebelum flush tertunda dijalankan. Ini adalah strategi implementasi yang tetap tunduk pada batas arsitektural yang sama.

Penggunaan ulang memori menjadikan completion syarat lifetime

Syarat correctness paling kuat muncul ketika physical page lama akan digunakan kembali. Anggap virtual page V sebelumnya memetakan page A. Software menghapus mapping itu, mengembalikan page A ke allocator, lalu subsistem lain memberikan page A kepada data yang tidak terkait.

Jika CPU remote masih dapat menerjemahkan V ke page A, mapping stale telah melewati batas ownership. Load atau store berikutnya melalui V dapat mengakses memori yang tidak lagi menjadi bagian dari mapping lama.

Karena itu, penghapusan page table, invalidasi TLB, dan reklamasi memori membentuk urutan lifetime:

hapus atau ganti mapping
        |
hentikan translasi cache yang terdampak
        |
pastikan completion yang diwajibkan
        |
lepaskan atau gunakan ulang backing memory lama

Implementasi kernel dapat melakukan batching atau menunda sebagian pekerjaan ini jika invariant internal mengizinkannya, tetapi titik saat penggunaan ulang menjadi aman tetap harus dipertahankan.

Invalidasi translasi bukan memory barrier generik

CPU memory barrier membatasi ordering atau visibility sesuai memory model arsitektur. Barrier tidak secara generik menginvalidasi entry TLB. Demikian pula, invalidasi entry TLB bukan pengganti pemeliharaan data cache pada sistem yang memerlukan operasi cache eksplisit.

Mekanisme tersebut melindungi bentuk state yang berbeda. Sinkronisasi page table mengatur translasi alamat. Memory barrier mengatur hubungan ordering. Pemeliharaan cache mengatur visibilitas data ketika hardware coherency tidak menyediakannya secara otomatis.

Pemisahan batas ini penting pada kode level rendah. Store ke page table dapat sudah terlihat secara global sebagai data sementara CPU lain masih memiliki translasi cache valid yang berasal dari entry lama. Transisi mapping baru selesai setelah arsitektur dan sistem operasi memenuhi kontrak invalidasi translasi yang diwajibkan.