Zajęcia 6: Interfejsy wewnętrzne jądra, część 2

Data: 04.04.2023

Informacje o procesie

Podczas pisania kodu, który będzie się wykonywał w przestrzeni adresowej jądra należy cały czas pamiętać, że wątek wykonania jest związany z pewnym procesem użytkownika, w imieniu którego jądro wykonuje określone operacje. Korzystając z makra current (asm/current.h) możemy łatwo (i szybko) dotrzeć do wszystkich informacji jakie jądro przechowuje o bieżącym procesie w strukturze task_struct (linux/sched.h).

Wyjątkiem jest obsługa przerwań - o ile w trakcie wykonywania funkcji obsługi przerwania sprzętowego, makro current może wskazywać na jakiś proces, to nie należy się do niego odwoływać (nie ma on związku z tym przerwaniem) jak również nie wolno przełączać się na inne procesy (czyli nie można też wykonywać operacji blokujących).

Wymiana danych między przestrzenią adresową użytkownika i jądra

Aby z poziomu jądra odczytać/zapisać coś z/do przestrzeni pamięci programów użytkownika należy posłużyć się następującymi funkcjami (właściwie makrami):

put_user(kptr, ptr)

wpisanie bajtu/słowa/długiego słowa do pamięci programów użytkownika (spod adresu ptr); makrodefinicja działa automagicznie - rozmiar określony jest na podstawie typu, na który wskazuje kptr

get_user(kptr, ptr)

j.w., ale odczytanie

Do kopiowania większych obszarów pamięci służą funkcje:

unsigned long copy_from_user(void *to, const void __user *from, unsigned long n);
unsigned long copy_to_user(void __user *to, const void *from, unsigned long n);

Pierwsza umożliwia kopiowanie danych z przestrzeni adresowej użytkownika do przestrzeni adresowej jądra, druga odwrotnie. Ogólnie zachowują się jak memcpy, jednak trzeba pamiętać, że w przypadku błędu braku strony adresu w przestrzeni użytkownika mogą spowodować uśpienie procesu aż do momentu ściągnięcia strony z pliku wymiany. Przed kopiowaniem sprawdzana jest poprawność adresu w przestrzeni użytkownika. Jeśli początek obszaru jest poprawny, ale dalsza część nie, to kopiowany jest najdłuższy możliwy fragment.

Wartością zwracaną przez obie funkcje jest liczba NIE skopiowanych bajtów - niezerowa oznacza wystąpienie błędu przy kopiowaniu.

Funkcje i odpowiadające im makrodefinicje zdefiniowane są w pliku asm/uaccess.h. Należy zwrócić uwagę, iż funkcje dla bloków o rozmiarze potęg dwójki są zoptymalizowane.

W przypadku błedu przy kopiowaniu z/do przestrzeni użytkownika, syscalle powinny zwracać -EFAULT.

Wzajemne wykluczanie

Synchronizacja w jądrze Linuksa wraz z jego rozwojem ciągle zyskuje na ważności. Warto uważniej przeanalizować związane z tym zagadnienia opisane tutaj oraz np. w rozdziale 5 [1].

Wszystkie z poniższych funkcji działają poprawnie zarówno na systemach jedno- jak i wieloprocesorowych. Wiele z nich jest zaimplementowane wewnętrznie w dwóch wersjach, zapewniających wyższą wydajność na systemach jednoprocesorowych - np. implementacja spinlocków sprowadza się do wyłączenia wywłaszczania jądra (lub zablokowania przerwań).

Zwykłe blokady

Przedstawione na poprzednich zajęciach.

Semafory systemowe

Semafory w Linuksie służą do synchronizacji procesów i reprezentuje je struktura struct semaphore (zdefiniowana w asm/semaphore.h).

Semafory można deklarować używając makr np:

static DECLARE_SEMAPHORE_GENERIC(sem_ogolny, 11);

Dostępne są między innymi następujące operacje:

void down(struct semaphore *sem)
int down_interruptible(struct semaphore *sem)
int down_trylock(struct semaphore *sem)

Funkcje opuszczające semafor systemowy. Warianty analogiczne do zwykłych blokad.

void up(struct semaphore *sem)

Funkcja podnosi semafor systemowy.

Linux udostępnia także dostępne semafory typu czytelnicy-pisarze typu struct rw_semaphore (linux/rwsem.h).

Ćwiczenie:

Proszę zapoznać się dostępnymi dla semaforów typu czytelnicy-pisarze funkcjami: (linux/rwsem.h).

Blokady wirujące (spin locks)

Blokady wirujące mają podobne działanie do zwykłych blokad, lecz używają aktywnego oczekiwania zamiast blokowania procesu. Można ich przez to używać w miejscach, gdzie blokowanie procesu byłoby niedopuszczalne (przede wszystkim funkcje obsługi przerwań), lub gdy zwykłe blokady znacznie zmniejszałyby wydajność (tj. przy małej ilości operacji chronionych).

Należy pamiętać, że NIE można wykonywać żadnych(!) operacji blokujących po zajęciu blokady wirującej (najważniejsze z funkcji, które nie współpracują z blokadami wirującymi to: copy_to/from_user, kmalloc, down, sleep_on, mutex_lock). Przed ich wywołaniem należy zwolnić blokadę.

Podstawowe blokady wirujące

Blokady wirujące (zdefiniowane w asm/spinlock.h) w ogólnym przpadku wykorzystuje się w nastepujący sposób:

spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;

spin_lock_irqsave(&xxx_lock, flags);
/* ... sekcja krytyczna ... */
spin_unlock_irqrestore(&xxx_lock, flags);

Powyższe wywołanie jest zawsze bezpieczne (bo blokuje przerwania na lokalnym procesorze, a następnie przywraca pierwotną obsługę przerwań).

Istnieje również uproszczona wersja, której możemy użyć, gdy dana blokada NIGDY nie jest używana w funkcji obsługi przerwań:

spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;

spin_lock(&xxx_lock);
/* ... sekcja krytyczna ... */
spin_unlock(&xxx_lock);

Blokady wirujące typu czytelnicy-pisarze (reader-writer spinlocks)

Ten typ blokady wirującej (zdefiniowane w asm/spinlock.h) umożliwia odczyt bez wyłączności i wyłączność na pełny dostęp do danych (np. zapis):

rwlock_t xxx_lock = RW_LOCK_UNLOCKED;
unsigned long flags;

read_lock_irqsave(&xxx_lock, flags);
/* .. sekcja krytyczna czytająca ... */
read_unlock_irqrestore(&xxx_lock, flags);

write_lock_irqsave(&xxx_lock, flags);
/* .. sekcja krytyczna z wyłącznym dostępem ... */
write_unlock_irqrestore(&xxx_lock, flags);

Sprawdza się przy skomplikowanych strukturach danych, gdy większość operacji polega na przechodzeniu (odczycie) struktury. Tylko faktyczna zmiana (zapis) wymaga wyłączności.

Istnieje również uproszczona wersja (bez blokowaniem przerwań) blokad wirujących typu czytelnicy-pisarze do wykorzystania w sytacjach, gdy użycie tej samej blokady nie może pojawić się w programie obsługi przerwania:

rwlock_t xxx_lock = RW_LOCK_UNLOCKED;

read_lock(&xxx_lock);
/* .. sekcja krytyczna czytająca ... */
read_unlock(&xxx_lock);

write_lock(&xxx_lock);
/* .. sekcja krytyczna z wyłącznym dostępem ... */
write_unlock(&xxx_lock);

Operacje atomowe

Istnieją typy atomic_t i atomic64_t. Dla każdego z tych typów zdefiniowane są niepodzielne operacje pozwalające na:

  • zainicjowanie, np: atomic_set(&zmienna,wartosc);

  • zmianę, np: atomic_add(&zmienna, 12);

  • jednoczesną zmianę i testowanie czy nowa wartość zmiennej jest zerem,

    np: atomic64_sub_and_test(1L, &zmienna64);

Po szczegóły odsyłam do pliku asm/atomic.h. Istnieją także bitowe operacje atomowe asm/bitops.h.

Debugowanie blokad

Jądro posiada dość zaawansowany wbudowany kod sprawdzający poprawność blokowania, nazywany lockdep. Pozwala on wykryć potencjalne zakleszczenia przez analizę sekwencji blokad zajmowanych przez pojedyncze wątki jądra. Zakleszczenie nie musi wystąpić, aby zostać wykryte - wystarczy, że każda wymagana do zakleszczenia sekwencja została kiedykolwiek użyta przez jakiś wątek.

Wykrywane klasy błędów to proste błędy w użyciu blokad (np. niezainicjowane blokady, rekurencyjna blokada), zakleszczenia powodowane przez cykliczne zależności blokad, oraz zakleszczenia powodowane przez nieprawidłowe użycie blokad wewnątrz obsługi przerwań.

Debugowanie blokad należy jawnie włączyć w konfiguracji jądra, gdyż spowalnia ono działanie systemu.

Operacje blokujące

Kolejki oczekiwania

Proces, który musi oczekiwać na zajście pewnego zdarzenia (np. zakończenie operacji we/wy, czy pojawienie się danych w kolejce FIFO), usuwany jest z kolejki procesów gotowych i umieszczany jest w kolejce oczekiwania (waitqueues) - stan procesu zmienia się z TASK_RUNNING na TASK_INTERRUPTIBLE bądź TASK_UNINTERRUPTIBLE. Strukturą reprezentującą głowę listy, w której umieszcza się takie procesy, jest wait_queue_head_t, zdefiniowana w pliku linux/wait.h.

Wybrane operacje:

DECLARE_WAIT_QUEUE_HEAD(name)

przed użyciem wait_queue trzeba ją zainicjować

wait_event(name, cond)

umieszczenie procesu w kolejce oczekiwania w stanie odpornym na sygnały (TASK_UNINTERRUPTIBLE) i spanie, aż cond będzie zachodzić

wait_event_interruptible(name, cond)

j.w., ale przejście w stan TASK_INTERRUPTIBLE (nadejście sygnału spowoduje przejście w stan TASK_RUNNING), zwraca 0 w przypadku zajścia cond, -ERESTARTSYS w przypadku przerwania sygnałem

wait_event_timeout(name,cond,timeout)

jak wait_event, ale z budzeniem po upływie określonego czasu nawet jeśli cond nie zaszło

wait_event_interruptible_timeout(name,cond,timeout)

j.w., ale przejście w stan TASK_INTERRUPTIBLE

wake_up(name)

budzi wszystkie czekające procesy bez ustawionej flagi WQ_FLAG_EXCLUSIVE oraz jeden, który ma ustawioną. Uwaga: funkcja nie powoduje usunięcia procesu z kolejki oczekiwania - proces “usunie” się sam, po wznowieniu działania

wake_up_interruptible(name)

j.w., ale tylko dla procesów w stanie TASK_INTERRUPTIBLE

wake_up_all(name)

wstawienie wszystkich procesów (będących w stanie TASK_INTERRUPTIBLE bądź TASK_UNINTERRUPTIBLE) znajdujących się w kolejce oczekiwania do kolejki procesów gotowych

Powyższe operacje zdefiniowane są w linux/sched.h (oprócz pierwszej, zdefiniowanej w linux/wait.h).

Używając kolejek oczekiwania należy zwrócić uwagę na uniknięcie wyścigów. Jeżeli np. jesteśmy czytelnikiem i chcemy poczekać aż pisarz zapisze jakiekolwiek dane do bufora zabezpieczonego blokadą, kod oczekujący może wyglądać tak:

/* definicje */
DEFINE_MUTEX(blokada);
DECLARE_WAIT_QUEUE_HEAD(kolejka);
int poz_odczyt, poz_zapis;
char *bufor;

/* wczytanie bajtu */
char znak;
/* blokujemy */
mutex_lock(&blokada);
/* sprawdzamy, czy już mamy dane do przeczytania */
while (poz_odczyt == poz_zapis) {
    /* nie mamy - musimy zdjąć blokadę, aby pisarz mógł cokolwiek
     * zapisać */
    mutex_unlock(&blokada);
    /* czekamy na zapis - warunek zapewnia, że nie będziemy czekać,
       jeśli pisarz uaktualnił poz_zapis między zdjęciem przez nas
       blokady, a dodaniem nas do kolejki - w przeciwnym przypadku
       wake_up pisarza nie objęło by naszego procesu i czekalibyśmy
       znacznie dłużej (być może na zawsze). Warunek jest sprawdzany
       po dodaniu do kolejki oczekiwania, ale przed samym
       oczekiwaniem. */
    wait_event(kolejka, poz_odczyt != poz_zapis);
    /* wait_event zapewnia tylko, że w pewnym momencie od wywołania
       zaszło poz_odczyt != poz_zapis, lecz jakiś inny wątek mógł
       w międzyczasie opróżnić bufor - nie możemy niczego zakładać
       póki nie sprawdzimy tego warunku trzymając blokadę - zakładamy
       więc blokadę i sprawdzamy jeszcze raz warunek while, do skutku */
    mutex_lock(&blokada);
}
/* udało się - możemy odczytać znak */
znak = bufor[poz_odczyt++];
mutex_unlock(&blokada);

/* zapis bajtu */
mutex_lock(&blokada);
/* musimy zapewnić spełnienie warunku, na który czekają czytelnicy
 * PRZED obudzeniem czytelników */
bufor[poz_zapis++] = znak;
wake_up(kolejka);
mutex_unlock(&blokada);

Czekanie na zakończenie - wait for completion

Jest to dość dziwny wariant semafora:

  • tworzymy strukturę struct completion, która początkowo ma wartość 0

  • możemy wykonać operację complete, która zwiększa wartość struktury o 1

  • możemy wykonać operację wait_for_completion (lub jej warianty), która czeka, aż struktura będzie miała wartość dodatnią, po czym zmniejsza ją o 1

  • możemy wykonać operację complete_all, która permanentnie ustawia wartość struktury na UINT_MAX (wszystkie czekające wątki są budzone, wszystkie dalsze wykonania complete i wait_for_completion będą no-opami)

Oto typowe wykorzystanie mechanizmu “czekania na zakończenie”:

struct completion event;

init_completion(&event);

/* .. przekaż wskaźnik do event temu, kto ma budzić .. */

wait_for_completion(&event);

Ten budzący wywołuje:

complete(&event)

gdy nadejdzie odpowiednia pora.

Implementacja jest w pliku kernel/sched/completion.c, zaś sama struktura jest zadeklarowana w linux/completion.h.

Inne przydatne funkcje kernela

Biblioteka jądra zawiera wiele innych gotowych funkcji, które mogą się okazać przydatne przy pisaniu najróżniejszych sterowników. Z przydatniejszych można wymienić:

linux/idr.h

mapa int w void * z dynamiczną alokacją identyfikatorów

linux/kref.h

łatwe zliczanie referencji

linux/bitmap.h

efektywne tablice bitów

linux/btree.h

B-drzewa

linux/bug.h, asm-generic/bug.h

raportowanie krytycznych błędów w kodzie sterownika wynikających z wad kodu oraz ostrzeżeń (coś w rodzaju assert)

linux/circ_buf.h

bufory cykliczne

linux/hash.h

Proste funkcje hashujące

linux/kernel.h

Różne proste funkcje:

ALIGN(x,a)

wyrównuje x w dół do wielokrotności a (a musi być potęgą dwójki)

PTR_ALIGN(p, a)

jak wyżej, ale na wskaźnikach

IS_ALIGNED(x, a)

sprawdza, czy x już jest wyrównane

ARRAY_SIZE(arr)

rozmiar tablicy arr

DIV_ROUND_UP(n,d)

n/d, zaokrąglając w górę

roundup(x, y)

zakrągla x w górę do wielokrotności y

upper_32_bits(x), lower_32_bits(x)

jak w nazwie

might_sleep()

oznacza miejsce, w którym kod może spać, pomaga w debugowaniu (rzuca błąd jeśli debugownie spinlocków jest włączone, a trzymany jest spinlock)

min(x,y), max(x,y)

jak w nazwie

clamp(val, min, max)

val przycięte do zakresu [min, max]

linux/kobject.h

ogólny typ obiektowy ze zliczaniem referencji i widocznością w sysfs (na ich podstawie jest zrobiony m.in. cdev oraz device)

linux/parser.h

prosty parser do opcji

linux/rbtree.h

drzewa czerwono-czarne