hrxdev#2 Świat, zapisy, powtórki i błąd ukryty w formacie zapisu
· Nick
Od pierwszego wpisu rdzeń dorobił się świata, w którym można coś umieszczać, plików do jego przechowywania i sposobu na udowodnienie, że dwa przebiegi są zgodne. Nadal bez grafiki i bez postaci. Większość tego wpisu to infrastruktura, a jedna jej część to błąd, który okazał się wart opowiedzenia.
Świat z kafelków
Świat to siatka kafelków 1×1 m na dyskretnych poziomach, numerowanych od zera w górę. Ściana albo drzwi to kafelek; schody będą specjalnym łączem między dwoma poziomami, ale schodów jeszcze nie ma. Wewnętrznie świat to zestaw płaskich warstw (podłoga, konstrukcja, flagi konstrukcji) dla całej mapy plus warstwa pochodna dla przejezdności. Mapa jest śledzona w chunkach 16×16 z licznikami wersji, żeby renderer albo wyszukiwanie ścieżek mogły zapytać „czy ten obszar się zmienił?”, bez porównywania kafelków.
Rozmiar świata wybiera się przy jego tworzeniu. Budowanie odbywa się komendami przyjmującymi prostokąt: połóż podłogę, ścianę lub drzwi na obszarze albo je usuń. Jeśli część prostokąta jest zablokowana, reszta i tak zostaje zbudowana, a komenda zgłasza, co pominęła. Na razie są trzy wbudowane rodzaje kafelków: podłoga, ściana, drzwi. Od teraz mapa jest częścią skrótu świata i zapisów. Jest sprawdzana względem powolnego, ewidentnie poprawnego modelu referencyjnego na tysiącach losowych komend.
Zapisy i powtórki
Zapis i powtórka dzielą jeden kontener plikowy. Jest podzielony na opisane sekcje, każda z typem i wersją, więc nowe części świata (postacie, potrzeby, relacje) mogą później stać się nowymi sekcjami bez psucia starych plików. Są sumy kontrolne nagłówka i treści, treść jest skompresowana, a każdy rozmiar jest sprawdzany względem limitu, zanim przydzielona zostanie jakakolwiek pamięć, więc uszkodzony lub złośliwy plik nie sprawi, że gra zje całą twoją pamięć RAM. Rodzaje kafelków są zapisywane po nazwie, a nie po numerze, więc zapis działa dalej, jeśli lista rodzajów się zmieni.
Powtórka to to, czego chciałem od początku: ziarno plus dziennik komend. Podczas nagrywania rdzeń zapisuje też skrót kontrolny co 100 ticków. Przy odtwarzaniu porównuje wynik każdej komendy i każdy skrót kontrolny po drodze i zatrzymuje się na pierwszym ticku, w którym się rozjeżdżają. Powtórka pamięta też, który build rdzenia ją nagrał, więc powtórka z innego builda jest odrzucana, a nie cicho się rozjeżdża.
Sam rdzeń nigdy nie dotyka plików: czyta i zapisuje strumienie, a to gra decyduje, gdzie leżą zapisy. Tę granicę egzekwuje ten sam mechanizm zakazanych API co wcześniej.
Jeszcze niezrobione: narzędzie wiersza poleceń odtwarzające plik powtórki oraz strona gry związana z zapisem (folder zapisów, autozapisy, bezpieczny zapis).
Dowód, że dwa przebiegi są zgodne
Test determinizmu uruchamia teraz jeden scenariusz w dwóch oddzielnych procesach: ziarno, skrypt komend budowania (część z nich celowo niepoprawna) i systemowy test, który czerpie z każdego strumienia losowego. Każdy proces przechodzi go na trzy sposoby – od początku do końca, przez zapis i odtworzenie oraz przez powtórkę nagranych bajtów – i porównuje skróty w każdym ticku. Następnie oba procesy porównują swoje skróty ze sobą co 10. tick.
Zepsułem go celowo, żeby mieć pewność, że potrafi zawieść. Random bez ziarna przemycony do ticka zaświecił test na czerwono. Losowany skrót ciągu, który .NET inicjuje inaczej w każdym procesie, w obrębie jednego procesu przeszedł niezauważony i został wykryty dopiero przy porównaniu dwóch. To jest cały powód, dla którego potrzebne są dwa procesy.
Zasada, którą zapisałem: jeden build rdzenia musi dawać te same skróty na procesorach x64 i arm64, więc powtórka nagrana na Macu z układem Apple musi dać się odtworzyć na PC z Windowsem. Przypięte skróty referencyjne oraz przykładowe pliki zapisu i powtórek istnieją właśnie do tej kontroli. Trygonometria i funkcje wykładnicze zmiennoprzecinkowe różnią się między platformami, więc są zakazane we wszystkim, co wpływa na świat; przy pierwszej potrzebie będę musiał mieć deterministyczny zamiennik. Te pliki referencyjne zmieniają się tylko świadomie: jeśli skrót odpłynie, zmianę trzeba wyjaśnić, zanim zostanie zaakceptowana.
Benchmark, który potrafi powiedzieć „nie”
Jest teraz bezgłowy runner, który przyjmuje scenariusz, ziarno i liczbę ticków i drukuje raport JSON: medianę i 99. percentyl czasu na tick, liczbę agentów, skrót świata i liczbę bajtów przydzielonych na tick. Pierwszy scenariusz buduje mapę 512×512 na 16 poziomach za pomocą około 52 000 komend budowania.
Punkt odniesienia jest przechowywany osobno dla każdego komputera, bo czasy z laptopa nic nie znaczą na desktopie. Regresją jest mediana ponad 10% powyżej punktu odniesienia albo 99. percentyl ponad 35% powyżej, i to tylko wtedy, gdy wzrost przekracza 0,05 ms, ponieważ prawie pusty tick leży na granicy rozdzielczości zegara. Jedna bramka obowiązuje na każdej maszynie: zero bajtów przydzielonych na tick. Powinienem uczciwie powiedzieć, co to dziś mierzy. Bez systemów i bez postaci tick trwa około 35 nanosekund, więc bramka czasowa w większości śpi, dopóki w kamieniu milowym ruchu nie pojawią się pierwsze prawdziwe systemy. Teraz pracę wykonuje bramka alokacji.
Niestabilny test, który nie był niestabilny
Podczas budowania benchmarku test formatu zapisu zaczął zawodzić w niektórych buildach, choć rdzeń się nie zmienił. Test po kolei przestawia każdy bajt skompresowanej powtórki i wymaga, żeby ładowarka odrzuciła każdy wariant. W jednym buildzie bajt bliski końca pliku został zaakceptowany. W poprzednim buildzie ten sam test przechodził.
Powód, dla którego to pojawiało się i znikało: powtórka niesie identyfikator builda, który ją zapisał, więc skompresowane bajty różnią się między buildami, a razem z nimi bajt, który zostaje zmieniony. Luka była tam zawsze; test zauważał ją tylko wtedy, gdy kości padły w ten sposób.
Sama luka: suma kontrolna obejmowała dane po dekompresji, a dekompresor .NET okazał się pobłażliwy. Przyjmuje strumień, który nigdy nie mówi, że się skończył, i ignoruje wszystko po końcu. Odwrócenie bitu dopełniającego w ostatnim bajcie daje inny, wciąż poprawny strumień, który dekompresuje się do tych samych danych, więc suma kontrolna się zgadzała, a uszkodzony plik ładował się jako dobry.
Poprawka to nowa wersja kontenera. Suma kontrolna obejmuje teraz bajty w takiej postaci, w jakiej są zapisane w pliku, i jest sprawdzana przed dekompresją, a dekompresja musi skończyć się dokładnie tam, gdzie mówi nagłówek. Pusta treść jest zapisywana bez kompresji, ponieważ kompresor nie zapisuje nic dla pustych danych wejściowych. Kontrole używają teraz stałych skompresowanych strumieni niezależnych od builda oraz fuzzingu uszkodzonych plików. Pliki przykładowe zostały wygenerowane na nowo dla nowej wersji; skróty świata się nie zmieniły.
Przy okazji
Strona, którą czytasz, pokazuje teraz na stronie głównej dwa liczniki odwiedzających: unikalnych łącznie i z ostatnich 24 godzin. Są liczone z dziennika stron serwera WWW, bez JavaScriptu, ciasteczek i usług zewnętrznych. Adres jest zapisywany tylko jako skrót z solą, boty są odfiltrowywane po user agencie, a liczby spóźniają się o kilka minut. Kilka osób za jedną siecią liczy się jako jedna.
Co dalej
Pierwszy kamień milowy, szkielet rdzenia, jest ukończony. Teraz M1, widok budowania w Godot: ściany, drzwi i pomieszczenia z modelu świata, przekrój pięter, kamera obracana co 90° i zwykłe sześciany zamiast grafiki. Prace jeszcze się nie zaczęły. Zobacz plan rozwoju.