Jak działa stronicowanie x86?

91

To pytanie ma wypełnić próżnię dobrych, bezpłatnych informacji na ten temat.

Uważam, że dobra odpowiedź będzie pasować do jednej dużej odpowiedzi TAK lub przynajmniej do kilku odpowiedzi.

Głównym celem jest dostarczenie początkującym użytkownikom wystarczającej ilości informacji, aby mogli samodzielnie zapoznać się z podręcznikiem i zrozumieć podstawowe pojęcia dotyczące systemu operacyjnego związane ze stronicowaniem.

Sugerowane wytyczne:

  • odpowiedzi powinny być przyjazne dla początkujących:
    • konkretne, ale możliwie uproszczone przykłady są bardzo ważne
    • mile widziane są zastosowania przedstawionych koncepcji
  • cytowanie przydatnych zasobów jest dobre
  • mile widziane są małe dygresje na temat tego, jak systemy operacyjne używają funkcji stronicowania
  • Mile widziane są wyjaśnienia PAE i PSE
  • mile widziane są małe dygresje do x86_64

Powiązane pytania i dlaczego uważam, że nie są oszustami:

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
źródło
1
Powinno to być oznaczone jako „faq” i oznaczone jako „community-wiki”.
Kerrek SB,
@KerrekSB Naprawdę nie wiem, jak sobie radzić z tego rodzaju pytaniami. Odpowiedzi powinny być wiki społeczności, czy to wszystko? Nie mogłem znaleźć faqtagu.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Powiedziałbym, że krótka odpowiedź brzmi: „przeczytaj tom 3, rozdział 4: Paging in the Intel Manual”. Jest całkiem jasny, zwięzły i dobrze napisany i nie staje się bardziej autorytatywny.
Kerrek SB,
4
@KerrekSB Zgadzam się, że podręcznik jest przejrzysty i autorytatywny, ale był dla mnie trochę zbyt surowy, jak na pierwszą lekturę, potrzebowałem kilku prostych i konkretnych przykładów + uzasadnienie, aby lepiej zrozumieć.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Odpowiedzi:

144

Wersja tej odpowiedzi z ładnym spisem treści i większą zawartością .

Poprawię każdy zgłoszony błąd. Jeśli chcesz wprowadzić duże modyfikacje lub dodać brakujący aspekt, wprowadź je samodzielnie, aby uzyskać zasłużoną reputację. Mniejsze zmiany można scalać bezpośrednio w.

Przykładowy kod

Minimalny przykład: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Jak wszystko inne w programowaniu, jedynym sposobem, aby to naprawdę zrozumieć, jest zabawa z minimalnymi przykładami.

To, co sprawia, że ​​jest to „trudny” temat, to fakt, że minimalny przykład jest duży, ponieważ musisz stworzyć własny mały system operacyjny.

Podręcznik firmy Intel

Chociaż nie da się tego zrozumieć bez przykładów, postaraj się jak najszybciej zapoznać się z podręcznikami.

Firma Intel opisuje stronicowanie w podręczniku Intel Podręcznik programowania systemu, tom 3 - 325384-056PL, wrzesień 2015 r., Rozdział 4 „Stronicowanie”.

Szczególnie interesujący jest rysunek 4-4 „Formaty wpisów CR3 i struktury stronicowania z 32-bitowym stronicowaniem”, który przedstawia kluczowe struktury danych.

MMU

Stronicowanie jest wykonywane przez jednostkę zarządzania pamięcią (MMU) procesora. Podobnie jak wiele innych (np. Koprocesor x87 , APIC ), na początku był to osobny chip, który później został zintegrowany z procesorem. Ale termin jest nadal używany.

Ogólne fakty

Adresy logiczne to adresy pamięci używane w „zwykłym” kodzie użytkownika (np. Zawartość rsiin mov eax, [rsi]).

Pierwsza segmentacja przekształca je na adresy liniowe, a następnie stronicowanie przekształca adresy liniowe na adresy fizyczne.

(logical) ------------------> (linear) ------------> (physical)
             segmentation                 paging

W większości przypadków możemy myśleć o adresach fizycznych jako o indeksowaniu rzeczywistych komórek pamięci RAM, ale nie jest to w 100% prawdziwe z powodu:

Stronicowanie jest dostępne tylko w trybie chronionym. Korzystanie ze stronicowania w trybie chronionym jest opcjonalne. Stronicowanie jest włączone, jeśli PGbit cr0rejestru jest ustawiony.

Paging vs segmentation

Jedną z głównych różnic między stronicowaniem a segmentacją jest to, że:

  • stronicowanie dzieli pamięć RAM na równe części zwane stronami
  • segmentacja dzieli pamięć na fragmenty o dowolnych rozmiarach

Jest to główna zaleta stronicowania, ponieważ równe fragmenty ułatwiają zarządzanie.

Stronicowanie stało się o tyle popularne, że wsparcie dla segmentacji zostało porzucone w x86-64 w trybie 64-bitowym, głównym trybie działania nowego oprogramowania, gdzie istnieje tylko w trybie zgodności, który emuluje IA32.

Podanie

Paging służy do implementacji procesów w wirtualnych przestrzeniach adresowych w nowoczesnym systemie operacyjnym. Dzięki adresom wirtualnym system operacyjny może dopasować dwa lub więcej równoczesnych procesów w jednej pamięci RAM w sposób, który:

  • oba programy nie muszą nic wiedzieć o drugim
  • pamięć obu programów może w razie potrzeby rosnąć i kurczyć się
  • przełączanie się między programami jest bardzo szybkie
  • jeden program nigdy nie ma dostępu do pamięci innego procesu

Historycznie rzecz biorąc, stronicowanie następowało po segmentacji iw dużej mierze zastępowało je w celu implementacji pamięci wirtualnej w nowoczesnych systemach operacyjnych, takich jak Linux, ponieważ łatwiej jest zarządzać fragmentami pamięci stron o stałym rozmiarze zamiast segmentami o zmiennej długości.

Implementacja sprzętu

Podobnie jak segmentacja w trybie chronionym (gdzie modyfikacja rejestru segmentowego wyzwala ładowanie z GDT lub LDT), sprzęt stronicowania używa struktur danych w pamięci do wykonywania swoich zadań (tabele stron, katalogi stron itp.).

Format tych struktur danych jest ustalany przez sprzęt , ale to system operacyjny musi prawidłowo skonfigurować te struktury danych w pamięci RAM i zarządzać nimi, a także poinformować sprzęt, gdzie je znaleźć (przez cr3).

Niektóre inne architektury pozostawiają stronicowanie prawie całkowicie w rękach oprogramowania, więc błąd TLB uruchamia funkcję dostarczoną przez system operacyjny, aby przejść przez tablice stron i wstawić nowe mapowanie do TLB. Pozostawia to format tabeli stron do wyboru przez system operacyjny, ale sprawia, że ​​jest mało prawdopodobne, aby sprzęt mógł nakładać się na sekwencje stron z wykonywaniem innych instrukcji poza kolejnością, tak jak to robi x86 .

Przykład: uproszczony schemat stronicowania jednopoziomowego

To jest przykład tego, jak stronicowanie działa na uproszczonej wersji architektury x86 w celu zaimplementowania wirtualnej przestrzeni pamięci.

Tabele stron

System operacyjny mógłby dać im następujące tabele stron:

Tabela stron podana do procesu 1 przez system operacyjny:

RAM location        physical address   present
-----------------   -----------------  --------
PT1 + 0       * L   0x00001            1
PT1 + 1       * L   0x00000            1
PT1 + 2       * L   0x00003            1
PT1 + 3       * L                      0
...                                    ...
PT1 + 0xFFFFF * L   0x00005            1

Tabela stron podana do procesu 2 przez system operacyjny:

RAM location       physical address   present
-----------------  -----------------  --------
PT2 + 0       * L  0x0000A            1
PT2 + 1       * L  0x0000B            1
PT2 + 2       * L                     0
PT2 + 3       * L  0x00003            1
...                ...                ...
PT2 + 0xFFFFF * L  0x00004            1

Gdzie:

  • PT1i PT2: początkowa pozycja tabeli 1 i 2 w pamięci RAM.

    Przykładowe wartości: 0x00000000, 0x12345678, itd.

    To system operacyjny decyduje o tych wartościach.

  • L: długość pozycji tablicy strony.

  • present: wskazuje, że strona jest obecna w pamięci.

Tabele stron znajdują się w pamięci RAM. Mogą być na przykład zlokalizowane jako:

--------------> 0xFFFFFFFF


--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1


--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2

--------------> 0x0

Początkowe lokalizacje w pamięci RAM dla obu tabel stron są dowolne i kontrolowane przez system operacyjny. Do systemu operacyjnego należy upewnienie się, że nie nakładają się one na siebie!

Każdy proces nie może bezpośrednio dotykać żadnych tabel stron, chociaż może wysyłać żądania do systemu operacyjnego, które powodują modyfikację tabel stron, na przykład prosząc o większe segmenty stosu lub sterty.

Strona to fragment 4 kB (12 bitów), a ponieważ adresy mają 32 bity, do identyfikacji każdej strony potrzeba tylko 20 bitów (20 + 12 = 32, czyli 5 znaków w notacji szesnastkowej). Ta wartość jest ustalana przez sprzęt.

Wpisy tabeli stron

Tabela stron to ... tabela wpisów tabeli stron!

Dokładny format wpisów w tabeli jest ustalany przez sprzęt .

W tym uproszczonym przykładzie wpisy tabeli stron zawierają tylko dwa pola:

bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag

więc w tym przykładzie projektanci sprzętu mogli wybrać L = 21.

Większość rzeczywistych wpisów w tabeli stron ma inne pola.

Wyrównywanie wartości na 21 bitach byłoby niepraktyczne, ponieważ pamięć jest adresowana bajtami, a nie bitami. Dlatego nawet w tym przypadku potrzeba tylko 21 bitów, projektanci sprzętu prawdopodobnie zdecydowaliby się L = 32na szybszy dostęp, a pozostałe bity zarezerwowaliby tylko do późniejszego wykorzystania. Rzeczywista wartość dla Lna x86 to 32 bity.

Tłumaczenie adresów w schemacie jednopoziomowym

Po skonfigurowaniu tablic stron przez system operacyjny translacja adresów między adresami liniowymi i fizycznymi jest wykonywana przez sprzęt .

Gdy OS chce, aby aktywować proces 1, to ustawia cr3się PT1, początek tabeli dla jednego procesu.

Jeśli Proces 1 chce uzyskać dostęp do adresu liniowego 0x00000001, obwód sprzętowy stronicowania automatycznie wykonuje następujące czynności dla systemu operacyjnego:

  • podziel adres liniowy na dwie części:

    | page (20 bits) | offset (12 bits) |
    

    Więc w tym przypadku mielibyśmy:

    • page = 0x00000
    • przesunięcie = 0x001
  • spójrz na stronę tabeli 1, ponieważ cr3wskazuje na nią.

  • wygląd wpisu, 0x00000ponieważ jest to część strony.

    Sprzęt wie, że ten wpis znajduje się pod adresem RAM PT1 + 0 * L = PT1.

  • ponieważ jest obecny, dostęp jest ważny

  • przy tabeli stron lokalizacja numeru strony 0x00000to 0x00001 * 4K = 0x00001000.

  • aby znaleźć ostateczny adres fizyczny, wystarczy dodać przesunięcie:

      00001 000
    + 00000 001
      -----------
      00001 001
    

    ponieważ 00001jest fizycznym adresem strony wyszukanej w tabeli i 001jest przesunięciem.

    Jak nazwa wskazuje, do przesunięcia zawsze dodaje się po prostu fizyczny adres strony.

  • sprzęt pobiera następnie pamięć w tej fizycznej lokalizacji.

W ten sam sposób następujące tłumaczenia miałyby miejsce dla procesu 1:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00002 000  00002 000
FFFFF 000  00005 000

Na przykład, podczas uzyskiwania dostępu do adresu 00001000, część strony to 00001sprzęt, który wie, że jego wpis tablicy stron znajduje się pod adresem RAM: PT1 + 1 * L( 1ze względu na część strony) i właśnie tam będzie jej szukał.

Gdy system operacyjny chce przełączyć się na proces 2, wystarczy, że cr3wskaże stronę 2. To takie proste!

Teraz dla procesu 2 miałyby miejsce następujące tłumaczenia:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00003 000  00003 000
FFFFF 000  00004 000

Ten sam adres liniowy przekłada się na różne adresy fizyczne dla różnych procesów , w zależności tylko od wartości wewnątrz cr3.

W ten sposób każdy program może oczekiwać, że jego dane będą zaczynać się 0i kończyć na FFFFFFFF, bez martwienia się o dokładne adresy fizyczne.

Błąd strony

Co się stanie, jeśli Proces 1 spróbuje uzyskać dostęp do adresu wewnątrz strony, której nie ma?

Sprzęt powiadamia oprogramowanie za pomocą wyjątku błędu strony.

Wtedy zwykle system operacyjny rejestruje program obsługi wyjątków, aby zdecydować, co należy zrobić.

Możliwe, że dostęp do strony, której nie ma w tabeli, jest błędem programowania:

int is[1];
is[2] = 1;

ale mogą być przypadki, w których jest to dopuszczalne, na przykład w Linuksie, gdy:

  • program chce zwiększyć swój stos.

    Po prostu próbuje uzyskać dostęp do określonego bajtu w podanym możliwym zakresie, a jeśli system operacyjny jest zadowolony, dodaje tę stronę do przestrzeni adresowej procesu.

  • strona została zamieniona na dysk.

    System operacyjny będzie musiał wykonać pewną pracę za procesami z powrotem, aby przywrócić stronę do pamięci RAM.

    System operacyjny może odkryć, że jest to przypadek na podstawie zawartości pozostałej części wpisu tablicy stron, ponieważ jeśli obecna flaga jest czysta, pozostałe wpisy wpisu tablicy stron są całkowicie pozostawione systemowi operacyjnemu do tego, czego chce.

    Na przykład w systemie Linux, gdy obecny = 0:

    • jeśli wszystkie pola wpisu tablicy stron mają wartość 0, nieprawidłowy adres.

    • w przeciwnym razie strona została zamieniona na dysk, a rzeczywiste wartości tych pól kodują położenie strony na dysku.

W każdym przypadku system operacyjny musi wiedzieć, który adres wygenerował błąd strony, aby móc poradzić sobie z problemem. Dlatego mili programiści IA32 ustawiają wartość cr2na ten adres za każdym razem, gdy wystąpi błąd strony. Program obsługi wyjątków może wtedy po prostu zajrzeć, cr2aby uzyskać adres.

Uproszczenia

Uproszczenia w rzeczywistości, które ułatwiają zrozumienie tego przykładu:

  • Wszystkie rzeczywiste obwody stronicowania używają stronicowania wielopoziomowego, aby zaoszczędzić miejsce, ale pokazało to prosty schemat jednopoziomowy.

  • tablice stron zawierały tylko dwa pola: 20-bitowy adres i 1-bitową flagę obecności.

    Rzeczywiste tabele stron zawierają łącznie 12 pól, a więc inne funkcje, które zostały pominięte.

Przykład: wielopoziomowy schemat stronicowania

Problem z jednopoziomowym schematem stronicowania polega na tym, że zajmuje on zbyt dużo pamięci RAM: 4G / 4K = 1M wpisów na proces. Jeśli każdy wpis ma 4 bajty, dałoby to 4 MB na proces , co jest za dużo nawet dla komputera stacjonarnego: ps -A | wc -lmówi, że uruchamiam teraz 244 procesy, więc zajmie to około 1 GB pamięci RAM!

Z tego powodu programiści x86 zdecydowali się na zastosowanie wielopoziomowego schematu, który zmniejsza zużycie pamięci RAM.

Wadą tego systemu jest nieco dłuższy czas dostępu.

W prostym 3-poziomowym schemacie stronicowania używanym dla procesorów 32-bitowych bez PAE, 32 bity adresu są podzielone w następujący sposób:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Każdy proces musi mieć jeden i tylko jeden powiązany z nim katalog stron, więc będzie zawierał przynajmniej 2^10 = 1Kpozycje katalogu stron, znacznie lepsze niż minimum 1M wymagane w schemacie jednopoziomowym.

Tabele stron są przydzielane tylko w razie potrzeby przez system operacyjny. Każda tabela 2^10 = 1Kstron zawiera pozycje katalogu stron

Katalogi stron zawierają ... pozycje katalogu stron! Pozycje katalogu stron są takie same jak wpisy tabeli stron, z tą różnicą, że wskazują adresy RAM tabel stron zamiast fizycznych adresów tabel . Ponieważ te adresy mają tylko 20 bitów szerokości, tablice stron muszą znajdować się na początku stron 4 KB.

cr3 teraz wskazuje na lokalizację w pamięci RAM katalogu stron bieżącego procesu zamiast tabel stron.

Wpisy tabel stron nie zmieniają się wcale od schematu jednopoziomowego.

Tabele stron różnią się od schematu jednopoziomowego, ponieważ:

  • każdy proces może mieć do 1 tys. tablic stron, po jednej na pozycję katalogu stron.
  • każda tabela stron zawiera dokładnie 1 tys. wpisów zamiast 1 mln wpisów.

Powodem używania 10 bitów na pierwszych dwóch poziomach (a nie powiedzmy 12 | 8 | 12) jest to, że każdy wpis tablicy stron ma 4 bajty. Wtedy 2 ^ 10 wpisów katalogów stron i tabel stron będzie ładnie pasować do stron 4Kb. Oznacza to, że przydzielanie i zwalnianie stron w tym celu jest szybsze i prostsze.

Tłumaczenie adresów w schemacie wielopoziomowym

Katalog stron nadany procesowi 1 przez system operacyjny:

RAM location     physical address   present
---------------  -----------------  --------
PD1 + 0     * L  0x10000            1
PD1 + 1     * L                     0
PD1 + 2     * L  0x80000            1
PD1 + 3     * L                     0
...                                 ...
PD1 + 0x3FF * L                     0

Tabele stron podane do procesu 1 przez system operacyjny w PT1 = 0x10000000( 0x10000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT1 + 0     * L   0x00001            1
PT1 + 1     * L                      0
PT1 + 2     * L   0x0000D            1
...                                  ...
PT1 + 0x3FF * L   0x00005            1

Tabele stron podane do procesu 1 przez system operacyjny w PT2 = 0x80000000( 0x80000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT2 + 0     * L   0x0000A            1
PT2 + 1     * L   0x0000C            1
PT2 + 2     * L                      0
...                                  ...
PT2 + 0x3FF * L   0x00003            1

gdzie:

  • PD1: początkowa pozycja katalogu stron procesu 1 w pamięci RAM.
  • PT1i PT2: początkowa pozycja tabeli stron 1 i tabeli stron 2 dla procesu 1 w pamięci RAM.

W tym przykładzie katalog stron i tablica stron mogą być przechowywane w pamięci RAM, na przykład:

----------------> 0xFFFFFFFF


----------------> PT2 + 0x3FF * L
Page Table 1
----------------> PT2

----------------> PD1 + 0x3FF * L
Page Directory 1
----------------> PD1


----------------> PT1 + 0x3FF * L
Page Table 2
----------------> PT1

----------------> 0x0

Przetłumaczmy 0x00801004krok po kroku adres liniowy .

Przypuszczamy cr3 = PD1, że to znaczy wskazuje na właśnie opisany katalog stron.

Binarnie adres liniowy to:

0    0    8    0    1    0    0    4
0000 0000 1000 0000 0001 0000 0000 0100

Grupowanie jako 10 | 10 | 12daje:

0000000010 0000000001 000000000100
0x2        0x1        0x4

co daje:

  • pozycja katalogu stron = 0x2
  • pozycja tablicy stron = 0x1
  • przesunięcie = 0x4

Tak więc sprzęt szuka pozycji 2 w katalogu stron.

Tabela katalogu stron mówi, że tabela stron znajduje się pod adresem 0x80000 * 4K = 0x80000000. To jest pierwszy dostęp do pamięci RAM procesu.

Ponieważ wpis tablicy stron to 0x1, sprzęt przegląda wpis 1 tablicy stron pod adresem 0x80000000, który informuje go, że strona fizyczna znajduje się pod adresem 0x0000C * 4K = 0x0000C000. To jest drugi dostęp do pamięci RAM procesu.

Na koniec sprzęt stronicujący dodaje przesunięcie, a końcowy adres to 0x0000C004.

Inne przykłady przetłumaczonych adresów to:

linear    10 10 12 split   physical
--------  ---------------  ----------
00000001  000 000 001      00001001
00001001  000 001 001      page fault
003FF001  000 3FF 001      00005001
00400000  001 000 000      page fault
00800001  002 000 001      0000A001
00801008  002 001 008      0000C008
00802008  002 002 008      page fault
00B00001  003 000 000      page fault

Błędy stron występują, jeśli nie ma pozycji katalogu stron lub pozycji tabeli stron.

Jeśli system operacyjny chce jednocześnie uruchomić inny proces, dałby drugiemu procesowi oddzielny katalog stron i łączył ten katalog z oddzielnymi tabelami stron.

Architektury 64-bitowe

64 bity to wciąż za dużo adresu dla obecnych rozmiarów pamięci RAM, więc większość architektur będzie używać mniej bitów.

x86_64 używa 48 bitów (256 TiB), a PAE trybu starszego już pozwala na 52-bitowe adresy (4 PiB).

12 z tych 48 bitów jest już zarezerwowanych dla przesunięcia, co pozostawia 36 bitów.

W przypadku podejścia dwupoziomowego najlepszy podział to dwa 18-bitowe poziomy.

Ale to oznaczałoby, że katalog stron zawierałby 2^18 = 256Kwpisy, które zajmowałyby zbyt dużo pamięci RAM: blisko stronicowania jednopoziomowego dla architektur 32-bitowych!

Dlatego architektury 64-bitowe tworzą jeszcze większe poziomy stron, zwykle 3 lub 4.

x86_64 używa 4 poziomów w 9 | 9 | 9 | 12schemacie, więc wyższy poziom zajmuje tylko 2^9wpisy wyższego poziomu.

PAE

Rozszerzenie adresu fizycznego.

Przy 32 bitach można zaadresować tylko 4 GB pamięci RAM.

To zaczęło stawać się ograniczeniem dla dużych serwerów, więc Intel wprowadził mechanizm PAE do Pentium Pro.

Aby złagodzić problem, Intel dodał 4 nowe linie adresu, aby można było zaadresować 64 GB.

Struktura tabeli stron jest również zmieniana, jeśli włączony jest PAE. Dokładny sposób, w jaki jest zmieniany, zależy od tego, czy PSE jest włączone, czy wyłączone.

PAE jest włączany i wyłączany za pomocą PAEbitu cr4.

Nawet jeśli całkowita adresowalna pamięć wynosi 64 GB, pojedynczy proces nadal może wykorzystywać tylko do 4 GB. System operacyjny może jednak umieścić różne procesy na różnych fragmentach 4 GB.

PSE

Rozszerzenie rozmiaru strony.

Pozwala, aby strony miały 4 MB (lub 2 MB, jeśli włączone jest PAE) zamiast 4K.

PSE jest włączane i wyłączane za pomocą PAEbitu cr4.

Schematy tabel stron PAE i PSE

Jeśli aktywne są PAE i PSE, stosowane są różne schematy poziomu stronicowania:

  • bez PAE i bez PSE: 10 | 10 | 12

  • bez PAE i PSE: 10 | 22.

    22 to przesunięcie w obrębie strony 4 Mb, ponieważ 22 bity adresują 4 Mb.

  • PAE i bez PSE: 2 | 9 | 9 | 12

    Projektowy powód, dla którego 9 jest używany dwa razy zamiast 10, jest taki, że teraz wpisy nie mogą już zmieścić się w 32 bitach, z których wszystkie były wypełnione 20 bitami adresu i 12 znaczącymi lub zarezerwowanymi bitami flagi.

    Powodem jest to, że 20 bitów nie wystarcza już do reprezentowania adresu tablic stron: potrzebne są teraz 24 bity z powodu 4 dodatkowych przewodów dodanych do procesora.

    Dlatego projektanci zdecydowali się zwiększyć rozmiar wpisów do 64 bitów, a aby zmieściły się w jednej tablicy stronicowej, konieczne jest zmniejszenie liczby wpisów do 2 ^ 9 zamiast 2 ^ 10.

    Początek 2 to nowy poziom strony zwany Page Directory Pointer Table (PDPT), ponieważ wskazuje na katalogi stron i wypełnia 32-bitowy adres liniowy. PDPT mają również szerokość 64 bitów.

    cr3teraz wskazuje na PDPT, które muszą znajdować się na pierwszych czterech 4 GB pamięci i być wyrównane na 32-bitowych wielokrotnościach dla wydajności adresowania. Oznacza to, że teraz cr3ma 27 znaczących bitów zamiast 20: 2 ^ 5 dla 32 wielokrotności * 2 ^ 27, aby uzupełnić 2 ^ 32 pierwszych 4 GB.

  • PAE i PSE: 2 | 9 | 21

    Projektanci zdecydowali się zachować 9-bitowe pole, aby zmieściło się na jednej stronie.

    To pozostawia 23 bity. Pozostawiając 2 dla PDPT, aby zachować jednolitość w przypadku PAE bez PSE, pozostawia 21 dla przesunięcia, co oznacza, że ​​strony mają szerokość 2M zamiast 4M.

TLB

Translation Lookahead Buffer (TLB) to pamięć podręczna dla adresów stronicowania.

Ponieważ jest to pamięć podręczna, ma wiele wspólnych problemów projektowych z pamięcią podręczną procesora, takich jak poziom asocjatywności.

W tej sekcji opisano uproszczoną, w pełni asocjacyjną TLB z 4 pojedynczymi adresami. Należy pamiętać, że podobnie jak inne pamięci podręczne, prawdziwe TLB zwykle nie są w pełni asocjacyjne.

Podstawowa operacja

Po translacji między adresem liniowym a fizycznym jest on przechowywany w TLB. Na przykład 4-wpisowy TLB zaczyna się w następującym stanie:

  valid   linear   physical
  ------  -------  ---------
> 0       00000    00000
  0       00000    00000
  0       00000    00000
  0       00000    00000

Symbol >wskazuje aktualny wpis do zastąpienia.

a po 00003przetłumaczeniu liniowego adresu strony na adres fizyczny 00005, TLB staje się:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
> 0       00000    00000
  0       00000    00000
  0       00000    00000

a po drugim przetłumaczeniu 00007na 00009to staje się:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
  1       00007    00009
> 0       00000    00000
  0       00000    00000

Teraz, jeśli 00003trzeba ponownie przetłumaczyć, sprzęt najpierw wyszukuje TLB i znajduje jego adres za pomocą pojedynczego dostępu do pamięci RAM 00003 --> 00005.

Oczywiście 00000nie ma go na TLB, ponieważ żaden ważny wpis nie zawiera 00000klucza.

Polityka wymiany

Po zapełnieniu TLB starsze adresy są nadpisywane. Podobnie jak w przypadku pamięci podręcznej procesora, polityka wymiany jest potencjalnie złożoną operacją, ale prostą i rozsądną heurystyką jest usunięcie najmniej niedawno używanego wpisu (LRU).

Z LRU, począwszy od stanu:

  valid   linear   physical
  ------  -------  ---------
> 1       00003    00005
  1       00007    00009
  1       00009    00001
  1       0000B    00003

dodanie 0000D -> 0000Adałoby:

  valid   linear   physical
  ------  -------  ---------
  1       0000D    0000A
> 1       00007    00009
  1       00009    00001
  1       0000B    00003

KRZYWKA

Korzystanie z TLB przyspiesza tłumaczenie, ponieważ początkowa translacja wymaga jednego dostępu na poziom TLB , co oznacza 2 w prostym schemacie 32-bitowym, ale 3 lub 4 na architekturach 64-bitowych.

TLB jest zwykle implementowany jako kosztowny rodzaj pamięci RAM zwanej pamięcią adresowalną treścią (CAM). CAM implementuje mapę asocjacyjną na sprzęcie, to znaczy strukturę, dla której dany klucz (adres liniowy) pobiera wartość.

Mapowania można również zaimplementować na adresach RAM, ale mapowanie CAM może wymagać znacznie mniej wpisów niż mapowanie RAM.

Na przykład mapa, na której:

  • zarówno klucze, jak i wartości mają 20 bitów (przypadek prostych schematów stronicowania)
  • za każdym razem należy przechowywać maksymalnie 4 wartości

może być przechowywany w TLB z 4 wpisami:

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
FFFFF    00000

Jednak aby zaimplementować to z pamięcią RAM, konieczne byłoby posiadanie 2 ^ 20 adresów :

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
... (from 00011 to FFFFE)
FFFFF    00000

co byłoby nawet droższe niż użycie TLB.

Unieważnianie wpisów

W przypadku cr3zmian wszystkie wpisy TLB są unieważniane, ponieważ będzie używana nowa tablica stron dla nowego procesu, więc jest mało prawdopodobne, aby którykolwiek ze starych wpisów miał jakiekolwiek znaczenie.

X86 oferuje również invlpginstrukcję, która jawnie unieważnia pojedynczy wpis TLB. Inne architektury oferują jeszcze więcej instrukcji do unieważnionych wpisów TLB, takich jak unieważnianie wszystkich wpisów w danym zakresie.

Niektóre procesory x86 wykraczają poza wymagania specyfikacji x86 i zapewniają większą spójność, niż gwarantuje, między modyfikacją wpisu w tablicy strony a użyciem go, gdy nie był on jeszcze buforowany w TLB . Najwyraźniej Windows 9x polegał na tym pod względem poprawności, ale nowoczesne procesory AMD nie zapewniają spójnych spacerów po stronach. Procesory Intela to robią, mimo że muszą wykryć błędne spekulacje, aby to zrobić. Skorzystanie z tego jest prawdopodobnie złym pomysłem, ponieważ prawdopodobnie nie ma wiele do zyskania i istnieje duże ryzyko spowodowania subtelnych problemów związanych z synchronizacją, które będą trudne do debugowania.

Użycie jądra Linux

Jądro Linuksa szeroko wykorzystuje funkcje stronicowania x86, aby umożliwić szybkie przełączanie procesów z małą fragmentacją danych.

W v4.2, spójrz pod arch/x86/:

  • include/asm/pgtable*
  • include/asm/page*
  • mm/pgtable*
  • mm/page*

Wydaje się, że nie ma zdefiniowanych struktur reprezentujących strony, tylko makra: include/asm/page_types.hjest szczególnie interesujące. Fragment:

#define _PAGE_BIT_PRESENT   0   /* is present */
#define _PAGE_BIT_RW        1   /* writeable */
#define _PAGE_BIT_USER      2   /* userspace addressable */
#define _PAGE_BIT_PWT       3   /* page write through */

arch/x86/include/uapi/asm/processor-flags.hdefiniuje CR0, aw szczególności PGpołożenie bitów:

#define X86_CR0_PG_BIT      31 /* Paging */

Bibliografia

Wolny:

  • rutgers-pxk-416 rozdział "Zarządzanie pamięcią: notatki z wykładów"

    Dobry przegląd historyczny technik organizacji pamięci używanych przez starszy system operacyjny.

Bezpłatna:

  • bovet05 rozdział "Adresowanie pamięci"

    Rozsądne wprowadzenie do adresowania pamięci x86. Brakuje dobrych i prostych przykładów.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
źródło
Świetna odpowiedź, ale nadal nie wiem, w jaki sposób podjęto decyzję o LRU. Wywoływanie systemu operacyjnego za każdym razem, gdy uzyskuje się dostęp do strony innej niż MRU, wydaje się kosztowne. Alternatywnie mogłem zobaczyć, jak sprzęt zmienia kolejność tabeli stron dla LRU, co może być niebezpieczne dla współbieżnych programów. Czy któreś z powyższych jest poprawne? Skąd system operacyjny wie, która strona jest stroną LRU w przypadku wystąpienia błędu strony?
Keynan
@Keynan Myślę, że to sprzęt, który to robi, więc czas nie jest problemem. Jeśli chodzi o współbieżność, nie wiem, jak jest zarządzana. Myślę, że jest jedna CR3 i pamięć podręczna na procesor, a system operacyjny musi tylko upewnić się, że strony pamięci nie nakładają się.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
1
real TLBs are not usually fully associativeThe TLB is usually implemented as … CAMCzy te dwa stwierdzenia nie są sprzeczne?
a3f
>>> x86_64 wykorzystuje 4 poziomy w 9 | 9 | 9 | 12 schemat, powinno być 9 | 9 | 9 | 9 | 12?
monklof
@monklof Myślę, że to prawda: 9 9 9 12 już pozwala na 512 GB pamięci RAM. 5-poziomowy schemat jest nowszym rozwiązaniem skierowanym tylko do serwerów, o czym wspomniałem w odpowiedzi na mojej stronie internetowej, która jest bardziej aktualna.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
22

Oto bardzo krótka, ogólna odpowiedź:

Procesor x86 działa w jednym z kilku możliwych trybów (z grubsza: rzeczywisty, chroniony, 64-bitowy). Każdy tryb może wykorzystywać jeden z kilku możliwych modeli adresowania pamięci (ale nie każdy tryb może wykorzystywać każdy model), a mianowicie: adresowanie w trybie rzeczywistym, adresowanie segmentowe i adresowanie płasko-liniowe.

We współczesnym świecie istotne jest tylko płasko-liniowe adresowanie w trybie chronionym lub 64-bitowym, a oba tryby są zasadniczo takie same, a główną różnicą jest rozmiar słowa maszynowego, a zatem ilość adresowalnej pamięci.

Teraz tryb adresowania pamięci nadaje znaczenie operandom pamięci instrukcji maszynowych (na przykład mov DWORD PTR [eax], 25, który przechowuje 32-bitową (aka dword) liczbę całkowitą o wartości 25 w pamięci, której adres jest przechowywany w eaxrejestrze 32-bitowym). W adresowaniu płasko-liniowym ta liczba eaxmoże przebiegać w jednym, ciągłym zakresie, od zera do wartości maksymalnej (w naszym przypadku jest to 2 32  - 1).

Jednak adresowanie płasko-liniowe może być stronicowane lub nie . Bez stronicowania adres bezpośrednio odnosi się do pamięci fizycznej. Podczas stronicowania jednostka zarządzająca pamięcią procesora (lub MMU) w sposób przejrzysty podaje żądany adres (obecnie nazywany adresem wirtualnym ) do mechanizmu wyszukiwania, tak zwanych tablic stron , i uzyskuje nową wartość, która jest interpretowana jako adres fizyczny. Oryginalna operacja działa teraz na nowym, przetłumaczonym adresie w pamięci fizycznej, mimo że użytkownik widzi tylko adres wirtualny.

Główną zaletą stronicowania jest to, że tabelami stron zarządza system operacyjny. W ten sposób system operacyjny może dowolnie modyfikować i zastępować tabele stron, na przykład podczas „przełączania zadań”. Może przechowywać całą kolekcję tablic stron, po jednej dla każdego "procesu", i kiedy tylko zdecyduje, że dany proces będzie wykonywany na danym CPU, ładuje tablice stron procesu do jednostki MMU tego CPU (każdy CPU ma swój własny zestaw tabel stron). W rezultacie każdy proces widzi własną wirtualną przestrzeń adresową, która wygląda tak samo, niezależnie od tego, które strony fizyczne były wolne, kiedy system operacyjny musiał przydzielić dla niej pamięć. Nigdy nie wie o pamięci żadnego innego procesu, ponieważ nie ma bezpośredniego dostępu do pamięci fizycznej.

Tabele stron są zagnieżdżonymi drzewiastymi strukturami danych przechowywanymi w normalnej pamięci, zapisywanymi przez system operacyjny, ale odczytywanymi bezpośrednio przez sprzęt, więc format jest ustalony. Są „ładowane” do MMU przez ustawienie specjalnego rejestru sterującego CPU, aby wskazywał tabelę najwyższego poziomu. Procesor używa pamięci podręcznej zwanej TLB do zapamiętywania wyszukiwań, więc wielokrotne dostępy do tych samych kilku stron są znacznie szybsze niż dostępy rozproszone, zarówno z powodów braku TLB, jak i zwykłych powodów dotyczących pamięci podręcznej danych. Często zdarza się, że termin „wpis TLB” odnosi się do wpisów tabeli stron, nawet jeśli nie są one przechowywane w buforze TLB.

A jeśli martwisz się, że proces może po prostu wyłączyć stronicowanie lub spróbować zmodyfikować tabele stron: jest to niedozwolone, ponieważ x86 implementuje poziomy uprawnień (zwane „pierścieniami”), a kod użytkownika jest wykonywany na poziomie uprawnień, który jest zbyt niski, aby na to pozwolić służy do modyfikowania tablic stron procesora.

Kerrek SB
źródło