Autor: Bolesław Szewczyk

Szeregowanie żądań dostępu do urządzeń blokowych

Wprowadzenie

W tym tekście omówię funkcje odpowiadające za obsługę żądań dostępu do urządzeń blokowych (chodzi o żądania odczytu i żądania zapisu), oraz struktury danych potrzebne do implementacji obsługi żądań (żądanie, kolejka żądań, itp.). Wymienię także miejsca, w których jądro korzysta z tych funkcji i struktur.

Wszystkie żądania odczytu lub zapisu do urządzeń blokowych są obsługiwane przez funkcje zdefiniowane w pliku drivers/block/ll_rw_blk.c. Skrótową nazwę "ll_rw_blk" można rozwinąć jako "low-level read-write block device operations", czyli niskopoziomowe operacje odczytu i zapisu na urządzeniach blokowych.

W pliku drivers/block/ll_rw_blk.c zadeklarowany jest spinlock io_request_lock, który ogranicza operacje na liście żądań do jednego procesora. Użyta jest także kolejka zadań tq_disk, odpowiada ona za żądania dostępu do dysku "odłożone" na później.

Spis treści

Funkcje

Omówię teraz najważniejsze funkcje zdefiniowane w drivers/block/ll_rw_blk.c.

Ll_rw_block: niskopoziomowy dostęp do urządzeń blokowych.
Deklaracja: void ll_rw_block(int rw, int nr, struct buffer_head *bhs[]).
rw - może być READ lub WRITE, a także READA (readahead - czytanie z wyprzedzeniem).
nr - rozmiar tablicy bhs, która jest parametrem.
bhs - tablica wskaźników na struktury typu buffer_head.

Ta funkcja żąda operacji wejścia/wyjścia na buforach, które są przekazane jako parametr, a robi to wywołując funkcję submit_bh, która z kolei wywołuje generic_make_request. Zapewnia dodatkową funkcjonalność, której nie daje generic_make_request. Mianowicie, dla każdego bufora na liście sprawdza czy (w przypadku operacji READ) nie został on już wcześniej odczytany (buffer_uptodate), oraz (w przypadku operacji WRITE) sprawdza czy bufor jest "czysty" (clean) i jeśli jest nie wykonuje zapisu. Ponadto sprawdza, czy inny wątek nie zajął się wcześniej buforem sprawdzając i ustawiając bit stanu bufora BH_Lock (test_and_set_bit). Ustawia wskaźnik funkcji zakończenia operacji wejścia/wyjścia na buforze (b_end_io) na funkcję end_buffer_io_sync (zdefiniowaną w buffer.c), która odblokowuje bufor i budzi czekających. Uwaga: wszystkie bufory muszą dotyczyć tego samego urządzenia, a ich rozmiar musi być wielokrotnością minimalnego rozmiaru bufora dla urządzenia.

Submit_bh: zgłoszenie bufora do urządzenia blokowego w celu późniejszego wykonania operacji wejścia/wyjścia.
Deklaracja: void submit_bh(int rw, struct buffer_head *bh).
rw - może być READ, WRITE lub READA.
bh - struktura buffer_head, która opisuje czego dotyczy operacja wejścia/wyjścia.

Submit_bh poza wywołaniem generic_make_request wyznacza prawdziwe urządzenie, którego dotyczy operacja wejścia/wyjścia (bh->b_rdev) oraz prawdziwą lokację sektora na urządzeniu (bh->b_rsector).

Generic_make_request: przekazanie struktury buffer_head do sterownika urządzenia.
Definicja: void generic_make_request (int rw, struct buffer_head *bh).
rw - READ, WRITE lub READA.
bg - struktura buffer_head, opisująca miejsce w pamięci oraz na urządzeniu.

Używana do tworzenia żądań wejścia/wyjścia. W strukturze wskazywanej przez bh muszą być poprawnie ustawione pola b_addr, b_size, b_rdev, b_rsector i b_end_io. Sterownik urządzenia może zmienić pola b_rdev i b_rsector. Funkcja dodaje żądanie do kolejki związanej z urządzeniem za pomocą funkcji make_request_fn, której adres jest elementem struktury request_queue przypisanej do urządzenia.

__make_request: standardowa funkcja dodawania żądania wejścia/wyjścia do kolejki żądań urządzenia.
Definicja: static int __make_request(request_queue_t *q, int rw, struct buffer_head *bh).

Ta funkcja poza dodaniem żądania do kolejki wykorzytuje strategię windową do scalania żądań lub wstawiania żądania w odpowiednie miejsce w kolejce.

Spis treści

Struktury danych

Struktury danych używane przy szeregowaniu żądań wejścia/wyjścia definiowane są w pliku include/linux/blkdev.h.

Struktura request reprezentuje żądanie operacji wejścia/wyjścia na urządzeniu blokowym, a w przyszłości ma być używana także przy stronicowaniu. Oto jej definicja: 

struct request {
        struct list_head     queue;
        int                  elevator_sequence;
        struct list_head     table;
        volatile int         rq_status;
        kdev_t               rq_dev;
        int                  cmd;
        int                  errors;
        unsigned long        sector;
        unsigned long        nr_sectors;
        unsigned long        hard_sector, hard_nr_sectors;
        unsigned int         nr_segments;
        unsigned int         nr_hw_segments;
        unsigned long        current_nr_sectors;
        void                 *special;
        char                 *buffer;
        struct completion    *waiting;
        struct buffer_head   *bh;
        struct buffer_head   *bhtail;
        request_queue_t      *q;
};
Kolejki żądań przechowywane są w strukturach request_queue. Definicja struktury request_queue to: 
struct request_queue
{
        struct list_head    request_freelist[2];
        struct list_head    pending_freelist[2];
        int                 pending_free[2];
        struct list_head    queue_head;
        elevator_t          elevator;
        request_fn_proc     *request_fn;
        merge_request_fn    *back_merge_fn;
        merge_request_fn    *front_merge_fn;
        merge_requests_fn   *merge_requests_fn;
        make_request_fn     *make_request_fn;
        plug_device_fn      *plug_device_fn;
        void                *queuedata;
        struct tq_struct    plug_tq;
        char                plugged;
        char                head_active;
        spinlock_t          queue_lock; /* jak na razie nie używany ... */
        wait_queue_head_t   wait_for_request;
};
Struktura blk_dev_struct jest związana z każdym urządzeniem blokowym. Przechowywana jest w niej kolejka żądań, oraz funkcja "queue" zwracająca kolejkę żądań, która może zostać podmieniona przez sterownik urządzenia. Normalnie, kiedy wywołujemy blk_get_queue aby pobrać kolejkę żądań, otrzymujemy po prostu request_queue ze struktury blk_dev_struct (czytaj: normalnie, czyli wtedy kiedy wartość pola queue w blk_dev_struct jest null). Oto definicja blk_dev_struct: 
struct blk_dev_struct {
        request_queue_t    request_queue;
        queue_proc         *queue; /* musi być atomowa */
        void               *data;
};
Spis treści

Strategia windowa - elevator strategy

Za pomocą strategii windowej próbuje się osiągnąć większą efektywność dostępu do urządzeń blokowych takich jak twarde dyski. Chodzi o to, aby ruch głowicy twardego dysku przypominał ruch windy, która jak najrzadziej zmienia kierunek jazdy (góra - dół). Jeśli w danym momencie obsługujemy żądania o coraz wyższych adresach na dysku, to nowe żądanie być może będzie się dało wstawić gdzieś pomiędzy stare żądania, tak aby je obsłużyć "po drodze". Nowe żądania wstawia się do kolejki żądań w taki sposób, by jaknajwięcej żądań było obsługiwanych w kolejności rosnących lub malejących adresów.
Spis treści

Odwołania żądające dostępu do urządzeń blokowych

Z szeregowania zaimplementowanego w drivers/block/ll_rw_blk.c korzystają przede wszystkim algorytmy block_read i block_write napisane w fs/block_dev.c. Block_write i block_read zlecają odczyt lub zapis z urządzeń blokowych za pomocą funkcji ll_rw_block. Algorytmy keszowania buforów zaimplementowane przez fs/buffer.c korzystają z funkcji ll_rw_block oraz submit_bh.