Zadanie 3: sterownik urządzenia Ultimate HardDoom™

Data ogłoszenia: 05.05.2020

Termin oddania: 23.06.2020 (brak możliwości spóźnienia)

Materiały dodatkowe

Wprowadzenie

Zadanie polega na napisaniu sterownika do urządzenia Ultimate HardDoom™, będącego akceleratorem grafiki dedykowanym dla gry Ultimate Doom. Urządzenie dostarczane jest w postaci zmodyfikowanej wersji qemu.

Urządzenie powinno być dostępne dla użytkownika w formie urządzenia znakowego. Dla każdego urządzenia Ultimate HardDoom™ obecnego w systemie należy utworzyć urządzenie znakowe /dev/udoomX, gdzie X to numer kolejny urządzenia Ultimate HardDoom™, zaczynając od 0.

Interfejs urządzenia znakowego

Urządzenie /dev/udoom* służy do tworzenie zasobów Ultimate HardDoom™ oraz wysyłania poleceń do urządzenia Ultimate HardDoom™. Powinno ono obsługiwać następujące operacje:

  • open: alokuje nowy kontekst urządzenia (czyli wirtualną przestrzeń adresową), który będzie służył do wysyłania poleceń.

  • close: w oczywisty sposób.

  • ioctl(UDOOMDEV_IOCTL_CREATE_BUFFER): tworzy nowy bufor, który będzie można zmapować do przestrzeni adresowej urządzenia. Jako parametr tego wywołania przekazywany jest rozmiar bufora. Wynikiem tego wywołania jest nowy deskryptor pliku odnoszący się do utworzonego bufora. Utworzony bufor powinien być wypełniony zerami. Tak utworzony bufor będzie można później zmapować do kontekstu urządzenia i/lub do przestrzeni programu użytkownika.

  • ioctl(UDOOMDEV_IOCTL_MAP_BUFFER): mapuje bufor do przestrzeni adresowej urządzenia powiązanej z obecnym kontekstem. Parametrami tego wywołania są deskryptor pliku odnoszący się do mapowanego bufora, oraz tryb mapowania (0 — do odczytu i zapisu, 1 — tylko do odczytu). Sterownik powinien sam znaleźć wolny adres wirtualny w obecnym kontekście. Wynikiem wywołania jest przydzielony adres wirtualny. W razie braku możliwości zmapowania bufora przez brak wolnej przestrzeni adresowej (bądź jej nadmierną fragmentację), należy zwrócić błąd ENOMEM.

  • ioctl(UDOOMDEV_IOCTL_UNMAP_BUFFER): odmapowuje bufor z przestrzeni adresowej urządzenia powiązanej z obecnym kontekstem. Parametrem jest adres wirtualny początku mapowania, które powinno zostać usunięte. Jeśli operacja się powiedzie, należy zwrócić 0. Jeśli podany adres nie odpowiada żadnemu mapowaniu, należy zwrócić błąd ENOENT.

  • ioctl(UDOOMDEV_IOCTL_RUN): uruchamia bądź kolejkuje uruchomienie zadania na urządzeniu. Parametrami są wskaźnik na bufor poleceń (w przestrzeni wirtualnej powiązanej z obecnym kontekstem) oraz rozmiar bufora poleceń w bajtach. Jeśli operacja się powiedzie, należy zwrócić 0. Jeśli podany wskaźnik bądź rozmiar nie są wielokrotnością 4, należy zwrócić błąd EINVAL. Jeśli na kontekście wystąpił wcześniej błąd wykonania, można zwrócić błąd EIO.

  • ioctl(UDOOMDEV_IOCTL_WAIT): czeka na zakończenie wykonywania przesłanych wcześniej zadań. Parametr określa, na ile zadań do tyłu chcemy czekać — jeśli wartością parametru jest 13, należy czekać na zakończenie wszystkich zadań wysłanych na danym kontekście, z wyjątkiem ostatnich 13tu zadań. Aby poczekać na zakończenie wszystkich zadań wysłanych na danym kontekście, użytkownik wywołuje tą funkcję z parametrem 0. Operacja powinna zwrócić 0 w przypadku sukcesu, bądź EIO jeśli na tym kontekście nastąpił błąd wykonania.

Bufory, oprócz mapowania do przestrzeni wirtualnej urządzenia, można również zmapować do programu użytkownika funkcją mmap (z flagą MAP_SHARED).

Należy pamiętać, że użytkownik może wysłać niepoprawne polecenia. W przypadku, gdy wykonanie zadania spowoduje błąd (urządzenie zgłosi przerwanie *_ERROR bądź PAGE_FAULT_*), należy oznaczyć kontekst, który wysłał to zadanie jako “spalony” i zwracać błąd EIO na wszystkich wywołaniach UDOOMDEV_IOCTL_RUN i UDOOMDEV_IOCTL_WAIT na danym kontekście od tego momentu, po czym zresetować urządzenie i kontynuować przetwarzanie zadań wysłanych przez inne konteksty.

Sterownik powinien rejestrować swoje urządzenia w sysfs, aby udev automatycznie utworzył pliki urzadzeń o odpowiednich nazwach w /dev. Numery major i minor dla tych urządzeń są dowolne (majory powinny być alokowane dynamicznie).

Plik nagłówkowy z odpowiednimi definicjami można znaleźć tutaj: https://github.com/mwkmwkmwk/uharddoom/blob/master/udoomdev.h

Sterownik może przyjąć ograniczenie do 256 urządzeń w systemie.

Założenia interakcji ze sprzętem

Można założyć, że przed załadowaniem sterownika, urządzenie ma stan jak po resecie sprzętowym. Urządzenie należy też w takim stanie zostawić przy odładowaniu sterownika.

Pełnowartościowe rozwiązanie powinno działać asynchronicznie i używać bloku BATCH – operacje UDOOMDEV_IOCTL_RUN powinny dopisywać zadanie do bufora BATCH i wracać natychmiast do przestrzeni użytkownika bez oczekiwania na zakończenie zadania (ale jeśli bufor BATCH jest już pełny, dopuszczalne jest oczekiwanie na zwolnienie miejsca w nim). Oczekiwanie na zakończenie poleceń powinno być wykonane dopiero przy wywołaniu UDOOMDEV_IOCTL_WAIT.

Zasady oceniania

Za zadanie można uzyskać do 10 punktów. Na ocenę zadania składają się trzy części:

  • pełne wykorzystanie urządzenia (od 0 do 2 punktów):

    • operacja asynchroniczna — UDOOMDEV_IOCTL_RUN na urządzeniu nie czeka na zakończenie wysłanego zadania ani zadań wysłanych wcześniej (z rozsądnymi ograniczeniami), UDOOMDEV_IOCTL_WAIT czeka tylko na tyle zadań ile musi: 1p

    • użycie bloku BATCH: 1p

  • wynik testów (od 0 do 8 punktów)

  • ocena kodu rozwiązania (od 0 do -10 punktów)

Punktacja

Punkty ujemne za kod można było dostać za:

  1. Brak copy_*user (-0.5)

  2. Niepoprawna obsługa wielu wątków (-0.5)

  3. Pozostawienie urządzenia włączonego po unload (-0.5)

  4. Brak zwracania wartości (return) przy funkcjach non-void (-0.1)

  5. Użycie globalnego lock zamiast powiązanego z urządzeniem (-0.1)

  6. Niepoprawny locka w obsłudze przerwania (nie spin-lock; deadlock) (-0.5)

  7. Free na wskaźniku w środek alokacji (-0.5)

  8. Błędy w zliczaniu pozostałych zadań (deadlock przy wait) (-0.5)

  9. Brak resetu urządzenia we wszystkich wymaganych przypadkach (-0.2)

  10. Brak sprawdzania czy przerwanie pochodzi z naszego urządzenia (-0.5)

  11. Pozostawianie zablokowanych mutexów po powrocie do userspace (-0.5)

  12. Nieprawidłowa maska DMA (-0.1)

  13. Nieprawidłowe kody błędów (EINVAL) zamiast (-EINVAL), etc. (-0.2)

  14. Brak sprawdzania błędu przy alokacji pamięci (dma_alloc_coherent) (-0.5)

  15. Aktywne oczekiwanie na zakończenie zadania (-0.5)

  16. Zawieszenie VM przy resume (-0.5)

  17. Przysłanie nieprzetestowanego rozwiązania (-1.0)

  18. Błędna implementacja BATCH (-1.0)

  19. Bufor odwołuje się do urządzenia poprzez kontekst (który może istnieć krócej) (-0.5)

  20. Wycieki pamięci (-0.2)

  21. Zostawianie niekompletnego mapowania w razie błędu w map_buffer (-0.1)

  22. Potencjalne spanie (kmalloc z GFP_KERNEL etc.) podczas trzymania spinlocka (-0.5)

  23. Błędna obsługa sygnałów w *_interruptible (-0.2)

  24. Brakujące locki, wyścigi ze sprzętem (-0.2)

  25. Niepoprawne rozpoznawanie bufora po deskryptorze (-0.5)

  26. Alokacja nieciągłych buforów (-1.0)

  27. Niepotrzebna alokacja kompletu tabeli stron (-0.1)

  28. Błędne sprawdzanie miejsca na mapowany bufor (-0.2)

Forma rozwiązania

Sterownik powinien zostać zrealizowany jako moduł jądra Linux w wersji 5.5.5. Moduł zawierający sterownik powinien nazywać się uharddoom.ko. Jako rozwiązanie należy dostarczyć paczkę zawierającą:

  • źródła modułu

  • pliki Makefile i Kbuild pozwalające na zbudowanie modułu

  • krótki opis rozwiązania

Paczka powinna nazywać się ab123456.tar.gz (gdzie ab123456 jest loginem na students) i po rozpakowaniu tworzyć katalog ab123456 ze źródłami. Rozwiązania prosimy nadsyłać na adres p.zuk@mimuw.edu.pl z kopią do mwk@mimuw.edu.pl. Prosimy o umieszczenie [ZSO] w tytule wiadomości.

QEMU

Do użycia urządzenia Ultimate HardDoom™ wymagana jest zmodyfikowana wersja qemu, dostępna w wersji źródłowej.

Aby skompilować zmodyfikowaną wersję qemu, należy:

  1. Sklonować repozytorium https://github.com/mwkmwkmwk/qemu

  2. git checkout uharddoom

  3. Upewnić się, że są zainstalowane zależności: ncurses, libsdl, curl, a w niektórych dystrybucjach także ncurses-dev, libsdl-dev, curl-dev (nazwy pakietów mogą się nieco różnić w zależności od dystrybucji)

  4. Uruchomić ./configure z opcjami wedle uznania (patrz ./configure --help). Oficjalna binarka była kompilowana z:

    --target-list=x86_64-softmmu

  5. Wykonać make

  6. Zainstalować wykonując make install, lub uruchomić bezpośrednio (binarka to x86_64-softmmu/qemu-system-x86_64).

Aby zmodyfikowane qemu emulowało urządzenie Ultimate HardDoom™, należy przekazać mu opcję -device uharddoom. Przekazanie tej opcji kilka razy spowoduje emulację kilku instancji urządzenia.

Aby dodać na żywo (do działającego qemu) urządzenie Ultimate HardDoom™, należy:

  • przejść do trybu monitora w qemu (Ctrl+Alt+2 w oknie qemu)

  • wpisać device_add uharddoom

  • przejść z powrotem do zwykłego ekranu przez Ctrl-Alt-1

  • wpisać echo 1 > /sys/bus/pci/rescan, aby linux zauważył

Aby udać usunięcie urządzenia:

echo 1 > /sys/bus/pci/devices/0000:<idurządzenia>/remove

Program testowy

Do testowania sterownika przygotowaliśmy zmodyfikowaną wersję prboom-plus, który jest uwspółcześnioną wersją silnika gry Ultimate Doom. Aby go uruchomić, należy:

  • pobrać źródła z repozytorium https://github.com/mwkmwkmwk/prboom-plus

  • wybrać branch udoomdev

  • skompilować źródła i zainstalować program (bez instalacji, program nie będzie w stanie znaleźć swojego pliku z danymi, prboom-plus.wad):

    • ./bootstrap

    • ./configure --prefix=$HOME

    • make

    • make install

  • pobrać plik z danymi gry. Można użyć dowolnego z następujących plików:

    • freedoom1.wad lub freedoom2.wad z projektu Freedoom (https://freedoom.github.io/) – klon gry Ultimate Doom dostępny na wolnej licencji.

    • doom.wad lub doom2.wad z pełnej wersji oryginalnej gry, jeśli zakupiliśmy taką.

    • doom1.wad z wersji shareware oryginalnej gry.

  • załadować nasz sterownik i upewnić się, że mamy dostęp do /dev/udoom0

  • uruchomić X11, a w nim grę: $HOME/bin/prboom-plus -iwad <dane_gry.wad>

  • w menu Options -> General -> Video mode wybrać opcję “doomdev” (domyślne ustawienie “8bit” wybiera renderowanie programowe w trybie bardzo podobnym do naszego urządzenia i można go użyć do porównania wyników).

Aby w grze działał dźwięk, należy przekazać do qemu opcję -soundhw hda i przy kompilacji jądra włączyć stosowny sterownik (Device Drivers -> Sound card support -> HD-Audio).

Wskazówki

Do tworzenia plików dla buforów polecamy użyć funkcji anon_inode_getfile lub anon_inode_getfd. Aby dostać strukturę file z deskryptora pliku, możemy użyć fdget i fdput. Aby sprawdzić, czy przekazana nam struktura jest odpowiedniego typu, wystarczy porównać jej wskaźnik na strukturę file_operations z naszą.

Jeżeli popsujemy konfigurację prboom-plus tak, że przestanie się uruchamiać w stopniu wystarczającym do zmiany ustawień, możemy znaleźć jego plik konfiguracyjny w $HOME/.prboom-plus/prboom-plus.cfg. Usunięcie go spowoduje przywrócenie ustawień domyślnych.

Użycie BATCH_WAIT

W przypadku użycia bufora BATCH, prawdopodobnie nie chcemy otrzymywać przerwań po każdym zakończeniu zadania — dobrym pomysłem jest więc użycie przerwania BATCH_WAIT by czekać tylko na wybane zadania. Ponieważ możemy chcieć jednocześnie czekać na zakończenie kilku operacji, sterownik musi mieć listę aktywnych oczekiwań i ustawić BATCH_WAIT na najwcześniejszą z nich. W szczególności, prawdopodobnie będzie konieczne oczekiwanie w następujących przypadkach:

  • wykonanie UDOOMDEV_IOCTL_WAIT

  • brak wolnego miejsca w buforze BATCH przy wywołaniu UDOOMDEV_IOCTL_RUN (trzeba czekać na zakończenie najstarszego wysłanego zadania)

  • wywołanie suspend (trzeba czekać na zakończenie najnowszego wysłanego zadania, czyli na opróżnienie bufora)

Implementacja mmap

Aby obsłużyć wywołanie mmap na buforach, należy:

  1. Napisać nasz callback mmap do struktury file_operations, który ustawi pole vm_ops w podanym vma na naszą strukturę z callbackami.

  2. W naszej strukturze vm_operations_struct wypełnić callback fault

  3. W callbacku fault:

    • zweryfikować, że pgoff mieści się w rozmiarze bufora (jeśli nie, zwrócić VM_FAULT_SIGBUS)

    • wziąć adres wirtualny (w jądrze) odpowiedniej strony bufora i przekształcić go przez virt_to_page na struct page *

    • zwiększyć licznik referencji do tej strony (get_page)

    • wstawić wskaźnik na tą strukturę do otrzymanej struktury vm_fault (pole page)

    • zwrócić 0