Bölüm 14:Adres Çevirisi ve TLB

Bir önceki bölümde her sanal adresin MMU tarafından çevrildiğini gördük. Şimdi o çevirinin içine gireceğiz.

Soru masum görünüyor: bir sanal adresi fiziksel adrese çevirmek için bir tabloya bakmak yeterli değil mi? Değil — çünkü o tablo, tutulacağı makinenin belleğine sığmıyor.

Bu bölümde önce bu imkânsızlığın nasıl aşıldığını, sonra da aşmanın bedelinin nasıl ödendiğini göreceğiz.

Bu bölümde neyi çözüyoruz?

• Tek bir düz sayfa tablosunun neden imkânsız olduğunu ve ağaç yapısının bunu nasıl çözdüğünü göreceğiz.
• Bir sanal adresin bit bit nasıl parçalandığını izleyeceğiz.
• TLB’nin ne olduğunu ve context switch’in neden görünmeyen bir maliyeti olduğunu anlayacağız.
• Page fault’un tek değil üç ayrı olay olduğunu ve malloc’un neden hiç başarısız olmadığını çözeceğiz.

Hierarchical Paging ve Diğer Optimizasyonlar

64-bit sistemlerde bellek adresleri 64 bit uzunluğunda olabilir; bu da teorik sanal adres alanının 16 exbibyte gibi akıl almaz bir büyüklüğe çıkabileceği anlamına gelir. Bu sayı, PiB ölçekli büyük makinelerin bile çok ötesindedir. Yani sorun “gerçek makinelerde bu kadar RAM var mı?” değil; CPU ve işletim sisteminin böylesine büyük bir adres uzayını pratik ve verimli biçimde nasıl temsil edeceğidir.

Sanal adres alanındaki her 4 KiB blok için page table’da ayrı bir girdi gerektiğini düşün. Bu durumda 4.503.599.627.370.496 page table girdisine ihtiyacın olurdu. Her girdi 8 bayt ise, sadece page table’ı saklamak için 32 pebibyte RAM gerekirdi. Evet, bu sayı gerçek makinelerdeki toplam RAM miktarından bile absürt derecede büyük.

Bir not: neden bu kadar tuhaf birimler kullanıyorum?

Bunun nadir ve biraz çirkin göründüğünü biliyorum, ama ikili tabanlı bayt boyutlarıyla (2’nin kuvvetleri) onluk SI birimlerini ayırmanın önemli olduğunu düşünüyorum. Bir kilobyte, yani kB, 1000 bayttır. Bir kibibyte, yani KiB, 1024 bayttır. CPU’lar ve bellek adresleri bağlamında sayılar çoğu zaman 2’nin kuvvetleriyle ilerlediği için bu ayrım bana anlamlı geliyor.

Sanal bellek alanının tamamı için düz bir page table tutmak imkânsız, ya da en azından korkunç derecede verimsiz olacağı için, CPU mimarileri hierarchical paging kullanır. Bu modelde, tek bir dev tablo yerine farklı ayrıntı seviyelerinde birden çok page table katmanı bulunur. Üst katmanlar büyük bellek bloklarını kapsar ve daha küçük aralıklar için alt tablolara işaret eder. 4 KiB page’lere karşılık gelen tek tek girdiler ağacın yapraklarıdır.

x86-64 tarihsel olarak 4 seviyeli hierarchical paging kullandı. Bu düzende, her page table girişi adresin bir kısmıyla indekslenir. En üst anlamlı bitler bir önek gibi davranır; böylece o girdi bu bitlerle başlayan tüm adres aralığını temsil eder. Sonra sıradaki bit kümesi alt tablonun içinde bir sonraki adımı belirler ve bu böyle devam eder.

x86-64’ün 4 seviyeli paging tasarımında sanal işaretçilerin sadece 48 biti çeviri için kullanılır. Ancak üstteki 16 bit donanım tarafından göz ardı edilmez; Canonical Addressing kuralı gereği bu bitler 47. bitin kopyası olmak zorundadır. Eğer 47. bit 0 ise üst 16 bit tamamen 0 olmalıdır; 1 ise tamamen 1 olmalıdır. Bu, toplam 256 TiB canonical sanal adres alanı demektir; pratik anlatıda düşük yarı ve yüksek yarı kabaca 128 TiB + 128 TiB gibi düşünülebilir. (Tam 64 bit kullansan sayı 16 EiB olurdu ki, gereksiz derecede büyüktür.)

İlk 16 bitin atlanması şu anlama gelir: page table’ın ilk seviyesini indeksleyen “en yüksek anlamlı bitler” aslında 63. bitten değil, 47. bitten başlar. Bu yüzden bu bölümün başındaki higher-half kernel diyagramı aslında tam doğruyu söylemiyor; işleri anlaşılır tutmak için basitleştirilmiş bir çizim. Orta nokta, tam 64-bit uzayın değil, fiilen kullanılan çok daha dar adres uzayının orta noktasıdır.

Peki bu ağaç gerçekte ne kadar yer kaplıyor? Az önceki 32 pebibyte’ın karşı sayısını verelim.

“Merhaba dünya” yazan sıradan bir programın eşlemesi tipik olarak bir PML4 tablosu ve birkaç alt tablodan ibarettir: toplam 20-30 KiB civarı. Otuz iki pebibyte’tan yirmi dört kibibyte’a. Aradaki oran milyarda bir mertebesinde.

Üstelik bu tasarruf her process için ayrı ayrı kazanılıyor. Düz bir tablo kullansaydın 32 PiB’lık maliyeti her process için ödemen gerekirdi; makinede yüz process varsa 3200 pebibyte. Hiyerarşik tabloyla aynı yüz process birkaç megabayt tutar.

Hierarchical paging alan sorununu çözer; çünkü ağacın herhangi bir seviyesinde, bir sonraki tabloya işaret eden pointer boş (0x0) olabilir. Bu sayede page table’ın tüm alt ağaçları atlanabilir; yani eşlenmemiş sanal adres alanı RAM’de yer kaplamaz. CPU, ağacın üst seviyelerinde boş bir giriş gördüğünde erişimi hızlıca başarısız sayabilir. Page table girdilerinde ayrıca “adres geçerli görünse bile kullanılamaz” demeye yarayan bayraklar da vardır.

Bir başka avantaj da, büyük sanal adres bölgelerini topluca değiştirebilmektir. Kernel, bir process için bir fiziksel bellek alanını, başka bir process içinse başka bir alanı hazır tutabilir. Process değiştirirken ağacın en üst düzeyindeki birkaç pointer’ı güncellemek yeterli olur. Eğer tüm eşleme düz bir dizi şeklinde saklansaydı, kernel’ın çok daha fazla girdiyi güncellemesi gerekirdi.

Biraz önce x86-64’ün “tarihsel olarak” 4 seviyeli paging kullandığını söyledim, çünkü yeni işlemciler 5 seviyeli paging destekliyor. Mimari açıdan 5 seviye, linear/canonical adres tarafını 57 bit’e kadar genişleterek toplam 128 PiB sanal alana ulaşmayı sağlar. Ama Linux bu geniş alanı kendiliğinden dağıtmaz: eski programların 47 bitten uzun adres beklemediğini bildiği için tahsisleri varsayılan olarak yine alt 128 TiB’ın içinde tutar. Bir program daha yüksek bir adres istediğini mmap’e açıkça söylerse kernel sınırı açar.

Bir not: fiziksel adres alanı sınırları

Tıpkı işletim sistemlerinin sanal adresler için tüm 64 biti kullanmaması gibi, CPU’lar da fiziksel adresler için tam 64 biti kullanmaz. 4 seviyeli paging döneminde x86-64 CPU’lar genelde 46 bitten fazlasını kullanmıyordu; bu da fiziksel adres alanını 64 TiB ile sınırlıyordu. 5 seviyeli paging ile bu destek 52 bite çıktı ve 4 PiB fiziksel adres alanı mümkün hâle geldi.

İşletim sistemi perspektifinden bakarsan, sanal adres alanının fiziksel adres alanından daha büyük olması avantajlıdır. Linus Torvalds’ın dediği gibi, en az iki kat büyük olması gerekir; on kat büyük olması ise daha da iyidir.

Bütün yürüyüşü tek bir şemada, adım adım izleyelim:

TLB: Çevirinin Önbelleği

Az önce hesabı yaptık: TLB olmasaydı tek bir bayt okumak beş RAM erişimi ederdi. Böyle bir sistem kullanılamaz. Bu yüzden MMU’nun içinde TLB (Translation Lookaside Buffer) adı verilen küçük ama son derece hızlı bir önbellek bulunur ve son yapılan sanal → fiziksel çevirileri saklar.

Bir bellek erişiminde MMU önce buraya bakar:

• TLB hit: Çeviri önbellekte varsa yürüyüş hiç yapılmaz; fiziksel adres anında elde edilir.
• TLB miss: Çeviri yoksa MMU tam page table walk yapar, sonucu TLB’ye yazar ve yoluna devam eder.

Sayılara bakmadan bu anlatı eksik kalıyor. Tipik bir modern x86-64 çekirdeğinde durum kabaca şöyle (mimariden mimariye değişir, mertebe olarak oku):

İlk satırdaki “paralel” kelimesi önemli: TLB isabeti neredeyse bedavadır, çünkü CPU veriyi cache’te ararken adresi de aynı anda çeviriyordur. Maliyet ancak ıskalayınca ortaya çıkar.

TLB Kapsama Alanı: Asıl Sınır

Şimdi bu bölümün en kullanışlı sayısına geliyoruz. TLB’nin kaç girdi tuttuğu tek başına bir şey ifade etmez; asıl soru ne kadar bellek alanını kapsadığıdır.

2000 girdilik bir TLB, 4 KiB’lık sayfalarla toplam 2000 × 4 KiB ≈ 8 MiB kapsar. Yani programın aktif olarak dokunduğu bellek 8 MiB’ı aşarsa TLB yetmemeye başlar ve sürekli ıskalarsın. 100 MiB’lık bir veri yapısında rastgele gezinen bir program için bu tam bir felakettir: her erişim neredeyse garantili bir yürüyüş demektir.

Aynı TLB, 2 MiB’lık büyük sayfalarla 2000 × 2 MiB ≈ 4 GiB kapsar. Beş yüz kat.

Huge page’lerin asıl kazancı işte burada; “daha az girdi gerekir” cümlesinin altındaki gerçek sayı bu. Ama bu kazancın bir bedeli olduğunu da unutma — az önceki Derinleşme panelinde konuştuğumuz iç parçalanma ve THP duraklamaları aynı madalyonun diğer yüzü.

Context Switch’in Gizli Maliyeti

TLB’nin bir yan etkisi daha var. Her process’in page table’ı farklı olduğuna göre, context switch sırasında TLB’deki çeviriler geçersiz hâle gelir; en basit çözüm TLB’yi tamamen boşaltmaktır. Ama bu, 7. bölümde konuştuğumuz “ısınma maliyeti”nin en pahalı bileşenidir: yeni process ilk binlerce erişiminde sürekli yürüyüş yapar.

Modern CPU’lar bunu hafifletmek için TLB girdilerini bir process kimliğiyle etiketler. x86-64’te bu mekanizmaya PCID (Process Context ID) denir ve 12 bitlik, yani 4096 farklı kimlik tutabilir; ARM tarafındaki karşılığı ASID’dir. Etiket sayesinde context switch’te TLB’yi boşaltmak gerekmez; başka process’in girdileri orada durur ama eşleşmediği için kullanılmaz.

Bu mekanizma Meltdown’dan sonra çok daha kritik hâle geldi. KPTI, her syscall’da kernel ile user adres alanı arasında geçiş yaptığı için TLB baskısını fiilen ikiye katladı; PCID de tam olarak bu bedeli hafifletmek için yeniden önem kazandı.

Swapping ve Demand Paging

Bellek erişimi birkaç sebeple başarısız olabilir: adres geçersiz olabilir, page table’da hiç eşlenmemiş olabilir ya da girdi “mevcut değil” olarak işaretlenmiş olabilir. Bu durumların herhangi birinde MMU, sorunu kernel’ın ele alabilmesi için page fault adlı bir donanım exception’ı üretir.

Ama “page fault” tek bir olay değil ve aralarındaki maliyet farkı beş büyüklük mertebesine varıyor. Üçünü ayırmak gerekiyor:

Aradaki uçurumu bir kez daha söyleyeyim: bir major fault, minor fault’un yüz katından fazla sürer. Bir programın “aniden takılması” çoğu zaman minor fault’ların major’a dönüşmesidir — yani makinenin belleği dolmuş, sayfalar diske gitmeye başlamıştır.

Kendi makinende bakabilirsin:

$ ps -o min_flt,maj_flt,cmd -p $$
 MINFL  MAJFL CMD
  4821      3 -bash

Muhtemelen binlerce minor, bir avuç major göreceksin. Bu oran sağlıklı bir sistemin imzasıdır; major sayısı hızla artıyorsa makinen swap’e düşmüş demektir.

Bazı durumlarda erişim gerçekten geçersizdir ya da yasaktır. Böyle olduğunda kernel büyük ihtimalle programı segmentation fault ile sonlandırır.

$ ./program
Segmentation fault (core dumped)
$

Bir not: segfault ontolojisi

“Segmentation fault” farklı bağlamlarda biraz farklı şeyler ifade eder. MMU, yetkisiz bellek erişiminde donanım seviyesinde bir hata üretir; aynı ad, işletim sisteminin bu tür geçersiz erişimler yüzünden programlara gönderdiği sinyal için de kullanılır.

Başka durumlarda ise bellek erişiminin bilerek başarısız olmasına izin verilir; böylece işletim sistemi eksik veriyi yükleyip sonra kontrolü CPU’ya geri verebilir. Örneğin işletim sistemi bir dosyayı, içeriğini daha RAM’e taşımadan sanal belleğe eşleyebilir. Adrese gerçekten erişildiğinde page fault oluşur; kernel de ilgili veriyi diskten RAM’e yükler. Buna demand paging denir.

Bu mekanizma sayesinde mmap gibi syscall’lar tüm dosyaları tembel biçimde sanal belleğe eşleyebilir. Eğer LLaMa.cpp’yi tanıyorsan, Justine Tunney kısa süre önce yükleme mantığını mmap temelli hâle getirerek bunu ciddi biçimde optimize etti. Eğer bilmiyorsan, işlerine bir göz at; Cosmopolitan Libc ve APE epey ilginç.

Bu değişiklik etrafında internette hatırı sayılır bir tartışma, devamı ve bir dalga daha döndü. Tartışmanın büyük kısmı teknik değil, lisans ve atıf üzerineydi. Buradaki teknik ders yerinde duruyor: mmap temelli yükleme, modeli RAM’e kopyalamadan çalıştırabiliyor.

Bir programı ve kütüphanelerini çalıştırdığında kernel aslında her şeyi baştan RAM’e kopyalamaz. Çoğu durumda yaptığı şey, dosya için bir mmap oluşturmak olur; CPU kodu gerçekten yürütmeye çalıştığında page fault oluşur ve kernel o page’i fiziksel bellekle doldurur.

Aynı numaranın bir başka kullanımını 16. bölümde göreceğiz ve mekanizması birebir aynı: Copy-on-Write da aslında bir page fault türüdür. fork sonrası kernel, paylaşılan sayfaları okunabilir ama yazılamaz işaretler. Process’lerden biri o sayfaya yazmaya kalktığında MMU bir fault üretir, kernel devreye girer, sayfayı kopyalar ve yeni kopyaya yazma izni verir. Program hiçbir şeyin farkında değildir; kendi belleğine yazdığını sanır.

Paylaşılan sıfır sayfası. Aynı fikrin bir başka uygulaması daha var. malloc ile yeni bellek istediğinde kernel sana gerçek RAM vermez; bütün o sayfaları, sistemde tek bir kopyası bulunan salt okunur bir sıfır sayfasına eşler. Okuduğunda hep sıfır görürsün ve tek bir bayt bile RAM harcanmamıştır. Ancak ilk yazma denemesinde fault üretilir ve kernel sana gerçek bir sayfa ayırır. Yani gigabaytlarca sıfır, RAM’de tek bir sayfa yer kaplar.

malloc Neden Hiç Başarısız Olmuyor?

Buradan çok tanıdık bir tuhaflığa varıyoruz. 16 GiB RAM’i olan bir makinede 100 GiB’lık malloc çağrısı yaparsan ne olur?

Başarılı döner. Anında, üstelik.

Sebebi artık tahmin edebilirsin: kernel sana RAM vermedi, yalnızca adres alanında 100 GiB’lık bir aralığı “bu senin” diye işaretledi. Fiziksel sayfa, ancak o adreslere gerçekten dokunduğunda ayrılacak. Kernel’ın verdiğinden fazlasını vaat etmesine overcommit deniyor ve varsayılan davranış budur.

Bu, üzerinde durup düşünmeye değer bir tercih. Programların çoğu istediği belleğin tamamını kullanmaz — büyük tamponlar ayırıp bir kısmına hiç dokunmamak son derece yaygındır. Kernel bunu bildiği için cömert davranır ve karşılığında makineden fiilen daha fazla iş çıkarır.

Bedeli ise sıra dışı bir hata anı doğurmasıdır. Vaatler gerçekten toplandığında, yani herkes belleğine aynı anda dokunmaya kalktığında, kernel’ın verecek sayfası kalmaz. malloc çoktan başarılı dönmüştü; hata bildirebileceği bir yer yok. Bu durumda devreye OOM killer girer: kernel çalışan process’leri puanlar ve en yüksek puanlıyı öldürür. Programın kendi hatası olmadan, hiçbir uyarı almadan sonlanmasının sebebi budur.

dmesg çıktısında Out of memory: Killed process ... satırını gördüysen, olan tam olarak buydu.

Demand paging, muhtemelen “swap” ya da “paging” adıyla duyduğun başka bir tekniği de mümkün kılar. İşletim sistemi bellek page’lerini diske yazıp sonra fiziksel RAM’den çıkarabilir; ama bunların sanal adreslerini page table’da tutmaya devam eder. Sonra aynı veri tekrar istenirse, diskten geri yükleyip erişimi yeniden mümkün kılar. Gerekirse diskten gelen sayfaya yer açmak için RAM’deki başka bir page’i swap out etmek zorunda kalabilir. Disk I/O yavaş olduğu için işletim sistemleri iyi page replacement algoritmaları ile bunu mümkün olduğunca az yapmaya çalışır.

Düşünmesi eğlenceli bir hack de şudur: page table içindeki fiziksel adres alanlarını, dosyaların diskteki konumlarını saklamak için kullanabilirsin. MMU zaten “present” biti kapalı bir girdi gördüğünde page fault üreteceği için, o alanların gerçek RAM adresi olmaması bazı tasarımlarda sorun yaratmaz. Her yerde pratik değildir ama akılda tutması keyiflidir.

Bu bölüm uzundu; toparlayalım.

• Program hiçbir zaman fiziksel RAM’i görmez. Gördüğü her adres sanaldır ve MMU tarafından çevrilir. İki process aynı adresi kullanabilir çünkü o adresler farklı yerlere çözülür.
• Sanal adres beş parçaya bölünür: dört tablo indeksi (her biri 9 bit) ve bir offset (12 bit). 9 bit tesadüf değil — 512 girdi × 8 bayt tam bir sayfa eder, yani her page table’ın kendisi bir sayfaya sığar.
• Çeviri bir yürüyüştür ve pahalıdır. CR3’ten başlayıp dört tablo dolaşmak, tek bir bayt için dört ek RAM erişimi demektir.
• TLB bu yürüyüşü ortadan kaldırır ama kapsama alanı sınırlıdır: 4 KiB sayfalarla birkaç megabayt. Büyük sayfaların asıl kazancı bu alanı yüzlerce kat büyütmesidir.
• Page fault üç ayrı olaydır: minor (ucuz), major (yüz kat pahalı, diske gider), invalid (segfault).
• Kernel tembeldir ve bu bir erdemdir. Demand paging, copy-on-write, paylaşılan sıfır sayfası ve overcommit — hepsi aynı ilkenin uygulamaları: işi gerçekten gerekene kadar erteler.

Sanal bellek, bir process’in başka bir process’in belleğine uzanmasını engelliyor. Peki ya tehdit dışarıdan değil, programın kendi içinden gelirse? Sıradaki bölümde bir programın kendi belleğini nasıl bozabildiğini ve buna karşı yıllar içinde kurulmuş savunma katmanlarını göreceğiz.