Przed rozwiązywaniem zadań warto się zapoznać z podrozdziałami 3.3, 3.5, 10.7 z Modern Operating Systems, podrozdziałem 8.11 z APUE oraz z rozdziałami 38, 49 z Linux Programming Interface.
Próba otworzenia open(2)
pliku wykonywalnego do zapisu, kiedy ten plik jest załadowany i wykonywany w jakimś procesie, zawiedzie z błędem ETXTBSY
. Podobnie, nie możemy załadować do przestrzeni adresowej execve(2)
pliku, który jest otwarty do zapisu. Co złego mogłoby się stać w systemach implementujących stronicowanie na żądanie (ang. demand paging), gdyby system operacyjny pozwolił modyfikować plik wykonywalny, który jest uruchomiony?
Stronicowanie na żądanie (ang. demand paging) to sposób implementacji pamięci wirtualnej. Polega ono na sprowadzaniu stron do pamięci operacyjnej tylko wtedy, gdy jest ona potrzebna, dzięki czemu zmniejszana jest liczba operacji I/O oraz zapotrzebowanie na pamięć operacyjną, ponieważ nie są sporwadzane niepotrzebne strony.
W Linuxie pliki wykonywalne są stronicowane na żądanie w razie potrzeby. Plik wykonywalny na dysku staje się wtedy "pamięcią zapasową" dla procesu. Oznacza to, że nie można modyfikować pliku wykonywalnego na dysku, gdyż wpłynęłoby to na działanie uruchomionej aplikacji. Jeśli spróbowalibyśmy użyć open(2)
na pliku wykonywalnym, który jest aktualnie uruchomiony, to zwrócony zostałby błąd ETXTBSY
(text file busy). Podobnie w przypadku próby uruchomienia exec(2)
, ten sam błąd może zostać zwrócony.
Gdyby system operacyjny stosujący stronicowanie na żądanie pozwolił na modyfikację uruchomionego pliku wykonywalnego, to niepotrzebne na początku strony nie byłyby ładowane do pamięci. Później, po wykonaniu zmian na uruchomionym programie, zostałyby wczytywane strony po modyfikacji, które prawdopodobnie kolidowałyby ze sobą, przez co program stałby się niezdatny do użytku, gdyż w każdym momencie mógłby się wywalić.
Na podstawie §49.1 wyjaśnij słuchaczom różnicę między odwzorowaniami plików w pamięć (ang. memory-mapped files) i odwzorowaniami pamięci anonimowej (ang. anonymous mappings). Jaką zawartością wypełniana jest pamięć wirtualna należąca do tychże odwzorowań? Czym różni się odwzorowanie prywatne od dzielonego? W jakim celu odwzorowania prywatne wykorzystują technikę kopiowania przy zapisie? Czemu odwzorowanie prywatne plików urządzeń blokowych ma niewiele sensu?
Wskazówka: Urządzenie blokowe to na przykład: pamięć karty graficznej albo partycja dysku.
Odwzorowanie plików w pamięć (ang. memory-mapped files) to zmapowanie obszaru pliku lub zasobu plikopodobnego do pamięci wirtualnej procesu. Po zmapowaniu można bezpośrednio się dostać do zawartości poprzez operowanie na jego bajtach w odpowiadającym obszarze pamięci. Strony są automatycznie ładowane z pliku, gdy zajdzie taka potrzeba.
Odwzorowanie pamięci anonimowej (ang. anonymous mappings) to mapowanie, które nie ma odpowiadającego pliku, a strony mapowania są zainicjalizowane zerami.
Odwzorowanie prywatne (MAP_PRIVATE
) działa tak, że modyfikacje zawartości odwzorowania nie są widoczne dla innych procesów, a dla odwzorowań plików w pamięć - nie są zapisywane do pliku. Jądro dokonuje tego poprzez kopiowanie przy zapisie, a więc przy próbie modyfikacji zawartości strony przez proces, jądro tworzy nową, oddzielną kopię tej strony dla procesu. Ta technika wykorzystywana jest w bardzo prostym celu - zmiany nie mogą być widoczne dla innych procesów, a więc dopóki nie są wykonywane żadne zapisy, nie ma potrzeby kopiowania pamięci, a gdy jakiś proces spróbuje coś zapisać, zmiany będą widoczne tylko dla niego (na własnej kopii).
Odwzorowanie dzielone (MAP_SHARED
) sprawia, że modyfikacje zawartości odwzorowania są widoczne dla innych procesów dzielących to odwzorowanie oraz w przypadku odwzorowań plików w pamięć, są zapisywane do plików. Pamięć odzworowana może być dzielona z odwzorowaniami w innych procesach (wpisy tabeli stron każdego procesu wskazują na to samo miejsce w pamięci RAM) na dwa sposoby: dwa procesy odwzorowują ten sam obszar pliku lub poprzez fork(2)
(dziecko dziedziczy wszystkie odwzorowania rodzica).
Odwzorowanie prywatne plików urządzeń blokowych nie ma zbyt dużego sensu, gdyż chcemy aby zmiany wykonywane w plikach były widoczne np. na dysku (partycji).
Na podstawie opisu do tabeli 49–1 podaj scenariusze użycia prywatnych i dzielonych odwzorowań plików w pamięć albo pamięci anonimowej. Pokaż jak je utworzyć z użyciem wywołania mmap(2)
. Co się z nimi dzieje po wywołaniu fork(2)
? Czy wywołanie execve(2)
tworzy odwzorowania prywatne czy dzielone? Jeśli wystartujemy
Scenariusze użycia odwzorowań:
text
lub data
procesu z pliku wykonywalnego lub biblioteki współdzielonej.malloc(3)
, który wykorzystuje mmap(2)
.read(2)
oraz write(2)
,Aby stworzyć odwzorowanie, należy użyć procedury mmap(2)
. Zleca ona zmapowanie length
bajtów przesuniętych o offset
bajtów (0
dla pamięci anonimowej) pliku zadanego przez deskryptor fd
(-1
dla pamięci anonimowej) do pamięci pod adres addr
(jednak ten adres jest tylko propozycją i zwykle jest przekazywany jako 0
). Argument prot
opisuje oczekiwany sposób ochrony pamięci (nie może być sprzeczny z trybem otwarcia pliku). Może on być równy PROT_NONE
lub alternatywą jednego lub więcej znaczników PROT_*
: PROT_EXEC
, PROT_READ
, PROT_WRITE
, PROT_NONE
. Parametr flags
określa rodzaj mapowanego obiektu, opcje mapowania oraz czy modyfikacje powinny być prywatne czy współdzielone. Są to odpowiednio flagi MAP_FIXED
, MAP_SHARED
, MAP_PRIVATE
, jednak sam Linux obsługuje jeszcze znaczniki niestandardowe (których jest znacznie więcej). Poniżej sygnatura funkcji, jak i sposób tworzenia odwzorowań:
// sygnatura funkcji
void *mmap(void *addr, size_t length, int prot, int flags,
int fd, off_t offset);
// prywatne odwzorowanie pliku
void *private_file = mmap(NULL, [size], [prot], MAP_PRIVATE | MAP_FILE, [fd], [offset]);
// prywatne odwzorowanie anonimowe
void *private_anon = mmap(NULL, [size], [prot], MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
// dzielone odwzorowanie pliku
void *shared_file = mmap(NULL, [size], [prot], MAP_SHARED | MAP_FILE, [fd], [offset]);
// dzielone odwzorowanie anonimowe
void *shared_anon = mmap(NULL, [size], [prot], MAP_SHARED | MAP_ANONYMOUS, -1, 0);
Po wywołaniu fork(2)
wszystkie odwzorowania są dziedziczone na zasadzie kopiowania przy zapisie. Z podręcznika execve(2)
wiemy, że odzworowania pamięci nie są zachowywane.
Unix współdzieli pliki wykonywalne i biblioteki współdzielone, ponieważ ich obrazy w pamięci są dzielone między wszystkimi użytkownikami. Załóżmy, że uruchamiamy dwie instancje bash
, a w jednej z nich vim
'a. Będziemy wtedy mieli po jednej kopii bash
i vim
w pamięci (oraz jedną kopię libc
, gdyż programy te korzystają z biblioteki języka C). Jeśli uruchomimy mmap(2)
'y wskazują na jeden obszar pamięci. Informacje zaczerpnięte z tego posta na Unix StackExchange.
Pamięć wymiany (ang. swap space) to miejsce na dysku, w którym system przechowuje strony, które nie mieszczą się fizycznie w pamięci RAM. Może być ona wymagana w przypadku używania prywatnych odwzorowań plików z prawami do pisania, gdyż zmiany w odwzorowaniu prywatnym nie są zapisywane do faktycznego pliku. W przypadku stron tylko do odczytu, nie ma potrzeby przechowywania ich w pamięci wymiany, podobnie w przypadku mapowań dzielonych plików, gdyż wtedy sam plik zachowuje się jak swój swap space. Anonimowe mapowania mogą wymagać użycia pamięci wymiany. W systemach Uniksowych wspierana jest flaga MAP_NORESERVE
, dzięki której można ustalić, czy należy zarezerować miejsce w pamięci wymiany dla tworzonego mapowania.
Na podstawie slajdów do wykładu wyjaśnij w jaki sposób system Linux obsługuje błąd stronicowania. Kiedy jądro wyśle procesowi sygnał SIGSEGV
z kodem SEGV_MAPERR
lub SEGV_ACCERR
? W jakiej sytuacji wystąpi pomniejsza usterka strony (ang. minor page fault) lub poważna usterka strony (ang. major page fault)? Jaką rolę pełni bufor stron (ang. page cache)? Kiedy wystąpi błąd strony przy zapisie, mimo że pole vm_prot
pozwala na zapis do obiektu wspierającego (ang. backing object)? Kiedy jądro wyśle SIGBUS
do procesu posiadającego odwzorowanie pliku w pamięć (§49.4.3)?
Błąd strony może wystąpić gdy proces próbuje czytać z nieistniejącej strony, dostać się do strony nieznajdującej się jeszcze w pamięci lub dostać się do strony bez odpowiednich uprawnień.
Aby obsłużyć błąd strony, należy przekazać kontrolę do jądra, który zapisze kontekst, a następnie sprawdzi która strona wywołała błąd. Jeżeli adres wirtualny jest poprawny, to system wczytuje odpowiednią ramkę strony, a jeśli trzeba ją zapisać, to na czas tej akcji I/O jądro przekazuje kontrolę innemu procesowi. Jeżeli adres nie jest poprawny (np. NULL
), bądź strona nie ma odpowiednich uprawnień do wykonywanej akcji (np. zapis do strony read-only), to jądro wysyła procesowi sygnał SIGSEGV
.
Sygnał SIGSEGV
może być wysłany z kodem SEGV_MAPERR
, który mówi o tym, że strona nie była zmapowana w przestrzeni adresowej procesu lub SEGV_ACCERR
, gdy strona nie miała odpowiednich uprawnień.
Błędy stron możemy podzielić na dwa rodzaje:
Nazwy minor (drobny) oraz major (kosztowny) odnoszą się do tego jak bardzo kosztowne pod względem czasu jest obsłużenie usterek strony.
Bufor stron (ang. page cache) to fragment pamięci RAM, którego zadaniem jest przyspieszenie odczytów i zapisów na dysku. Przy zapisach zmiany zostają dokonane jedynie w buforze stron (zamiast zapisów bezpośrednio na dysk), w którym zmienione strony są oznaczone bitem dirty. Zmiany na dysk są regularnie zapisywane na dysk przy użyciu sync(2)
lub fsync(2)
. Zwiększa się też szybkość odczytów, gdyż kolejne żądania wczytania tej samej strony mogą odbyć się przez bufor stron, o ile ta strona nadal się w nim znajduje.
Błąd strony przy zapisie może wystąpić wtedy, gdy plik został otworzony z flagą O_WRONLY
, pomimo że pole vm_prot
jest ustawione na PROT_WRITE
. Dzieje się tak ze względu na to, iż część architektur sprzętu nie pozwala na dostęp write-only do stron. PROT_WRITE
implikuje użycie PROT_READ
na tych architekturach, a więc jeśli można zapisywać do stron, to mogą być one również odczytywane, jednak operacja odczytu jest niezgodna z flagą O_WRONLY
, która zapobiega ujawnieniu zawartości pliku.
Jądro może wysłać sygnał SIGBUS
do procesu posiadającego odwzorowanie pliku w pamięć, gdy proces próbuje uzyskać dostęp do części pamięci, która nie pasuje do pliku (np. dostęp poza EOF, włącznie z przypadkiem gdy inny proces uciął część pliku).
Program forksort
wypełnia tablicę long
losowymi wartościami. Następnie na tej tablicy uruchamia hybrydowy algorytm sortowania, po czym sprawdza jeden z warunków poprawności wyniku sortowania. Zastosowano algorytm sortowania szybkiego (ang. quick sort), który przełącza się na sortowanie przez wstawianie dla tablic o rozmiarze mniejszym niż INSERTSORT_MAX
.
Twoim zadaniem jest taka modyfikacja programu forksort
, żeby oddelegować zadanie sortowania fragmentów tablicy do podprocesów. Przy czym należy tworzyć podprocesy tylko, jeśli rozmiar nieposortowanej części tablicy jest nie mniejszy niż FORKSORT_MIN
. Zauważ, że tablica elementów musi być współdzielona między procesy – użyj wywołania mmap(2)
z odpowiednimi argumentami.
Porównaj zużycie procesora (ang. CPU time) i czas przebywania w systemie (ang. turnaround time) przed i po wprowadzeniu delegacji zadań do podprocesów. Na podstawie prawa Amdahla wyjaśnij zaobserwowane
różnice. Których elementów naszego algorytmu nie da się wykonywać równolegle?
Zużycie procesora (ang. CPU time) to czas jaki procesor spędził na wykonywaniu instrukcji procesów, dla procesów wielowątkowych (lub zadań wieloprocesowych) wartość może przekroczyć 100% (a więc czas procesora będzie większy, niż czas rzeczywisty). Czas przebywania w systemie (ang. turnaround time) to czas od początku do zakończenia działania procesu.
Kod programu forksort.c
:
#include "csapp.h"
static void InsertionSort(long table[], size_t left, size_t right) {
for (size_t pivot = left + 1; pivot <= right; pivot++) {
size_t insert = left;
while ((insert < pivot) && (table[insert] < table[pivot]))
insert++;
if (insert < pivot) {
size_t n = pivot - insert;
long tmp = table[pivot];
memmove(&table[insert + 1], &table[insert], n * sizeof(long));
table[insert] = tmp;
}
}
}
static void SwapElem(long table[], size_t i, size_t j) {
long tmp = table[i];
table[i] = table[j];
table[j] = tmp;
}
static size_t Partition(long table[], size_t begin, size_t end, long pivot) {
size_t left = begin;
size_t right = end;
while (left < right) {
while ((left < right) && (table[left] < pivot))
left++;
while ((left < right) && (table[right] >= pivot))
right--;
if (left < right)
SwapElem(table, left, right);
}
return left;
}
#define INSERTSORT_MAX 32
#define FORKSORT_MIN (1L << 18)
static int QuickSort(long table[], size_t left, size_t right) {
pid_t pid_left = -1, pid_right = -1, pid = -1;
/* TODO: If there is more to sort than FORKSORT_MIN start a subprocess. */
bool should_fork = (right - left >= FORKSORT_MIN);
if (should_fork) {
if ((pid = Fork()))
return pid;
}
if (left < right) {
if (right - left <= INSERTSORT_MAX) {
InsertionSort(table, left, right);
} else {
size_t pivot = left + random() % (right - left + 1);
size_t split = Partition(table, left, right, table[pivot]);
if (left == split) {
SwapElem(table, left, pivot);
split++;
} else {
pid_left = QuickSort(table, left, split - 1);
}
pid_right = QuickSort(table, split, right);
/* TODO: Wait for possible children and exit if created a subprocess. */
(void)pid_left; // leave these 2 lines to allow compiling in "older" version
(void)pid_right;
if (pid_left != -1)
Waitpid(pid_left, NULL, 0);
if (pid_right != -1)
Waitpid(pid_right, NULL, 0);
if (should_fork)
exit(0);
}
}
return pid;
}
#define NELEMS (1L << 26)
int main(void) {
/* Table size in bytes must be divisible by page size. */
size_t size = NELEMS * sizeof(long);
assert((size & (getpagesize() - 1)) == 0);
/* Initialize PRNG seed. */
struct timeval tv;
gettimeofday(&tv, NULL);
srandom(tv.tv_usec);
/* TODO: Allocate table... */
int prot = PROT_READ | PROT_WRITE;
int flags = MAP_SHARED | MAP_ANONYMOUS;
long *table = Mmap(NULL, size, prot, flags, -1, 0);
/* ... and fill it in with random elements. */
for (size_t i = 0; i < NELEMS; i++)
table[i] = random();
/* Sort it using hybrid algorithm... */
if (QuickSort(table, 0, NELEMS - 1) > 0)
Wait(NULL);
/* ... and verify if the table is actually sorted. */
long prev = LONG_MIN;
for (size_t i = 0; i < NELEMS; i++) {
assert(prev <= table[i]);
prev = table[i];
}
return 0;
}
Oryginalna wersja programu forksort
działa tylko w jednym procesie, więc czas działania jest dłuższy, niż w przypadku wersji z oddelegowanymi podprocesami. Pokazują to wyniki:
*** pierwotna wersja forksort ***
$ time ./forksort
./forksort 9.17s user 0.21s system 99% cpu 9.375 total
*** po dodaniu delegacji podprocesów ***
$ time ./forksort
./forksort 9.69s user 0.54s system 275% cpu 3.710 total
Widzimy więc, że czas działania user
był zbliżony, jednak łączny czas jest
Aby sprawdzić różnice w wydajności, skorzystałem z programu perf
do analizy wydajności. Poleceniem perf record ./forksort
mierzę wydajność, a następnie perf record
wypisuje zmierzone wartości.
Pierwotna wersja forksort
, w raporcie widać, że wiele zadań można było liczyć równolegle (stąd oddelegowanie podprocesów w ulepszonej wersji). Około
Samples: 37K of event 'cycles:uppp', Event count (approx.): 28062695037
Overhead Command Shared Object Symbol
72.17% forksort forksort [.] Partition
8.24% forksort forksort [.] InsertionSort
6.51% forksort forksort [.] SwapElem
5.42% forksort libc-2.28.so [.] __memmove_avx_unaligned_erms
2.47% forksort libc-2.28.so [.] __random_r
2.07% forksort libc-2.28.so [.] __random
1.22% forksort forksort [.] QuickSort
1.00% forksort forksort [.] main
0.34% forksort [unknown] [k] 0xffffffff8d600ae7
0.30% forksort forksort [.] memmove@plt
0.26% forksort forksort [.] random@plt
0.00% forksort ld-2.28.so [.] strcmp
Ulepszona wersja forksort
zawierająca oddelegowanie podprocesów. W tym przypadku operacje wywoływane przez zdefiniowane przez nas funkcje zajmują około
Samples: 43K of event 'cycles:uppp', Event count (approx.): 29484544256
Overhead Command Shared Object Symbol
70.33% forksort forksort [.] Partition
9.43% forksort forksort [.] SwapElem
7.63% forksort forksort [.] InsertionSort
5.16% forksort libc-2.28.so [.] __memmove_avx_unaligned_erms
2.23% forksort libc-2.28.so [.] __random_r
2.07% forksort libc-2.28.so [.] __random
1.08% forksort forksort [.] QuickSort
1.05% forksort forksort [.] main
0.56% forksort [unknown] [k] 0xffffffff8d600ae7
0.24% forksort forksort [.] random@plt
0.16% forksort forksort [.] memmove@plt
0.02% forksort libc-2.28.so [.] __run_fork_handlers
0.01% forksort ld-2.28.so [.] _dl_fixup
0.01% forksort libc-2.28.so [.] __run_exit_handlers
0.01% forksort ld-2.28.so [.] _dl_runtime_resolve_xsavec
0.01% forksort ld-2.28.so [.] strcmp
0.00% forksort ld-2.28.so [.] do_lookup_x
0.00% forksort libc-2.28.so [.] _IO_cleanup
0.00% forksort libc-2.28.so [.] __libc_start_main
0.00% forksort libc-2.28.so [.] __waitpid
0.00% forksort libc-2.28.so [.] __libc_fork
0.00% forksort libc-2.28.so [.] __call_tls_dtors
0.00% forksort ld-2.28.so [.] _dl_count_modids
0.00% forksort ld-2.28.so [.] check_match
0.00% forksort ld-2.28.so [.] _dl_fini
0.00% forksort ld-2.28.so [.] _dl_lookup_symbol_x
0.00% forksort libc-2.28.so [.] exit
0.00% forksort forksort [.] exit@plt
0.00% forksort ld-2.28.so [.] _dl_name_match_p
0.00% forksort forksort [.] Waitpid
0.00% forksort [unknown] [k] 0xffffffff8d60015f
Jak można zauważyć, około
Przyspieszenie uzyskane przez zrównoleglenie procedury QuickSort
dało nam około Partition
, InsertionSort
oraz SwapElem
, gdyż nie są one zdefiniowane rekurencyjnie (w przeciwieństwie do QuickSort
), który jest algorytmem dziel i zwyciężaj, więc całe zadanie dzielimy na mniejsze podproblemy.
Nasz serwis internetowy stał się celem ataku hakerów, którzy wykradli dane milionów użytkowników. Zostaliśmy zmuszeni do zresetowania haseł naszych klientów. Nie możemy jednak dopuścić do tego, by użytkownicy wybrali nowe hasła z listy, którą posiadają hakerzy. Listę pierwszych 10 milionów skompromitowanych haseł można pobrać poleceniem make download
.
Program hashdb
został napisany w celu utworzenia bazy danych haseł i jej szybkiego przeszukiwania. Pierwszym argumentem przyjmowanym z linii poleceń jest nazwa pliku bazy danych haseł. Program wczytuje ze standardowego wejścia hasła oddzielone znakami końca linii i działa w dwóch trybach: dodawania haseł do bazy (opcja -i
) i wyszukiwania (opcja -q
). Żeby utworzyć bazę danych z pliku zawierającego hasła należy wywołać polecenie ./hashdb -i badpw.db < passwords.txt
. Program można uruchomić w trybie interaktywnego odpytywania bazy danych: ./hashdb -q badpw.db
.
Implementacja wykorzystuje tablicę mieszającą przechowywaną w pamięci, która odwzorowuje plik bazy danych haseł. Używamy adresowania liniowego i funkcji mieszającej Jenkinsa lookup3.c
. Hasło może mieć maksymalnie ENT_LENGTH
znaków. Baza danych ma miejsce na db_rehash
. Tworzy ona na nową bazę o rozmiarze
Twoim zadaniem jest uzupełnić kod procedur db_open
, db_rehash
i doit
zgodnie z poleceniami zawartymi w komentarzach. Przeczytaj podręcznik systemowy do wywołania systemowego madvise(2)
i wyjaśnij słuchaczom co ono robi. Należy użyć odpowiednich funkcji z biblioteki libcsapp
opakowujących wywołania: unlink(2)
, mmap(2)
, munmap(2)
, madvise(2)
, ftruncate(2)
, rename(2)
i fstat(2)
.
Poniżej umieszczony kod nie został napisany przeze mnie!
/* Open (`size` = 0) or create (`size` > 0) database from `name` file. */
static void db_open(db_t *db, const char *name, size_t size)
{
assert(powerof2(size));
int fd = Open(name, O_RDWR | O_CREAT | (size ? O_EXCL : 0), DB_MODE);
if (size == 0)
{
struct stat sb;
Fstat(fd, &sb);
size = sb.st_size / sizeof(entry_t);
if (size == 0)
size = 1;
}
/* TODO: Setup DB structure, set file size and map the file into memory.
Inform OS that we're going to read DB in random order. */
Ftruncate(fd, size * sizeof(entry_t));
db->entry = Mmap(NULL, size * sizeof(entry_t), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
Madvise(db->entry, size * sizeof(entry_t), MADV_RANDOM);
db->size = size;
db->name = strdup(name);
Close(fd);
}
/* Attempt to increase size of database. */
static bool db_rehash(db_t *db, size_t new_size)
{
assert(powerof2(new_size));
/* Create new database. */
db_t new[1];
char *name = alloca(strlen(db->name) + sizeof(".reshash") + 1);
strcpy(name, db->name);
strcat(name, ".rehash");
db_open(new, name, new_size);
/* Copy everything from old database to new database. */
/* TODO: Inform OS that we're going to read DB sequentially. */
Madvise(db->entry, db->size * sizeof(entry_t), MADV_SEQUENTIAL);
for (size_t i = 0; i < db->size; i++)
{
if (!db_maybe_insert(new, db->entry[i]))
{
/* Oops... rehashing failed. Need to increase db size and try again. */
/* TODO: Remove new database, since rehashing failed. */
db_close(new);
Unlink(name);
return false;
}
}
/* TODO: Replace old database with new one, remove old database. */
Rename(new->name, db->name); // Zastąpi stary plik, o ile nie ma RENAME_NOREPLACE.
Munmap(db->entry, db->size * sizeof(entry_t));
db->entry = new->entry;
db->size = new->size;
free(new->name);
return true;
}
static void doit(const char *path, op_t mode)
{
db_t db;
db_open(&db, path, 0);
/* If input file is a terminal device then use standard reading technique. */
/* TODO: Use fstat instead to handle pipes correctly. */
struct stat st;
Fstat(STDIN_FILENO, &st);
if (!S_ISREG(st.st_mode)) // isatty?
{
char buf[ENT_LENGTH + 1];
while (fgets(buf, ENT_LENGTH + 1, stdin))
consume_line(buf, &db, mode);
}
else
{
/* TODO: Map stdin into memory, and read it line by line. */
void *buf = Mmap(NULL, st.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, STDIN_FILENO, 0);
char *end = buf;
do
{
end = consume_line(end, &db, mode);
} while (end != NULL);
Munmap(buf, st.st_size);
}
db_close(&db);
}
Wykonywanie zewnętrznego polecenia przez powłokę uniksową ma dwa warianty. Gdy w ścieżce do pliku występuje znak ukośnika /
to zakładamy, że użytkownik podał ścieżkę względną i uruchamiamy execve(2)
bezpośrednio. W przeciwnym przypadku musimy odczytać zawartość zmiennej środowiskowej PATH
przechowującej katalogi oddzielone znakiem dwukropka :
. Każdą ścieżkę katalogu sklejamy z nazwą polecenia (przyda Ci się procedura strapp
z pliku lexer.c
) i wołamy execve
. Jeśli polecenie nie zostanie znalezione na dysku to execve
wraca z błędem.
Uzupełnij ciało procedury external_command
z pliku command.c
zgodnie z powyższym opisem.
Wskazówka: Rozwiązanie wzorcowe liczy 10 wierszy. Do przetwarzania ciągów znakowych użyto funkcji strndup(3)
i strcspn(3)
.
Dopóki znajdują się ścieżki w path
(uzyskane ze zmiennej środowiskowej PATH
), to szukamy pierwszego wystąpienia :
dzielącego kolejne ścieżki, następnie korzystając ze strndup(3)
kopiujemy wszyskie znaki ze ścieżki do :
, po czym dodajemy do tej ścieżki /[nazwaprogramu]
dwoma wywołaniami strapp()
. Na końcu wywołujemy execve
na tak stworzonej ścieżce.
noreturn void external_command(char **argv) {
const char *path = getenv("PATH");
if (!index(argv[0], '/') && path) {
/* TODO: For all paths in PATH construct an absolute path and execve it. */
while (true) {
int chars_to_colon = strcspn(path, ":");
if (chars_to_colon == 0)
break;
char *absolute_path = strndup(path, chars_to_colon);
strapp(&absolute_path, "/");
strapp(&absolute_path, argv[0]);
(void)execve(absolute_path, argv, environ);
free(absolute_path);
path += 1 + chars_to_colon;
}
} else {
(void)execve(argv[0], argv, environ);
}
msg("%s: %s\n", argv[0], strerror(errno));
exit(EXIT_FAILURE);
}
Procedura do_job
w pliku shell.c
przyjmuje tablicę tokenów, zawierającą polecenie do uruchomienia i przekierowania, oraz rodzaj tworzonego zadania (pierwszoplanowe lub drugoplanowe). Najpierw sprawdza czy podane polecenie należy do zestawu poleceń wbudowanych (ang. builtin command). Jeśli nie, to przechodzi do utworzenia zadania i wykonania polecenia zewnętrznego. Po utworzeniu podprocesu i nowej grupy procesów, zadanie jest rejestrowane z użyciem addjob
i addproc
. Jeśli utworzono zadanie pierwszoplanowe, to należy poczekać na jego zakończenie przy pomocy monitorjob
.
Uzupełnij ciało procedury do_job
– wykorzystaj funkcje opakowujące wywołania: sigprocmask(2)
, sigsuspend(2)
, setpgid(2)
i dup2(2)
. Pamiętaj, że uruchomione zadanie musi prawidłowo reagowaćna sygnały: SIGTSTP
, SIGTTIN
i SIGTTOU
, a powłoka musi zamykać niepotrzebne deskryptory plików.
Wskazówka: Rozwiązanie ma około 25 wierszy. Funkcja monitorjob
konfiguruje terminal przy pomocy tcsetpgrp(3)
.
/* Execute internal command within shell's process or execute external command
* in a subprocess. External command can be run in the background. */
static int do_job(token_t *token, int ntokens, bool bg) {
int input = -1, output = -1;
int exitcode = 0;
ntokens = do_redir(token, ntokens, &input, &output);
if (!bg) {
if ((exitcode = builtin_command(token)) >= 0)
return exitcode;
}
sigset_t mask;
Sigprocmask(SIG_BLOCK, &sigchld_mask, &mask);
/* TODO: Start a subprocess, create a job and monitor it. */
pid_t pid = Fork();
if (pid == 0) {
// allow signals for the subprocess that are by default
// turned off for shell, i.e. CTRL+Z etc.
Signal(SIGTSTP, SIG_DFL);
Signal(SIGTTIN, SIG_DFL);
Signal(SIGTTOU, SIG_DFL);
// possibly open (duplicate) file descriptor that was changed
// in do_redir call (it could've changed input/output values)
if (input != -1) {
Dup2(input, STDIN_FILENO);
Close(input);
}
if (output != -1) {
Dup2(output, STDOUT_FILENO);
Close(output);
}
// finally call the command (it is surely not builtin)
external_command(token);
}
// create own process group and then a job based on it, take
// into account whether it is FG/BG process and then add the
// process to the job
Setpgid(pid, pid);
int new_job = addjob(pid, bg);
addproc(new_job, pid, token);
// close file descriptors that were possibly opened earlier
MaybeClose(&input);
MaybeClose(&output);
// based on bg value, run the job in bg or fg
if (bg)
printf("[%d] running '%s' [do_job called]\n", new_job, jobcmd(new_job));
else
monitorjob(&mask);
Sigprocmask(SIG_SETMASK, &mask, NULL);
return exitcode;
}
Przed rozwiązywaniem zadań warto się zapoznać z rozdziałami 1-3 publikacji Dynamic Storage Allocation: A Survey and Critical Review.
Systemy uniksowe udostępniają wywołania systemowe sbrk(2)
oraz parę mmap(2)
i munmap(2)
. Służą one do przydziału stron na użytek bibliotecznego algorytmu zarządzania pamięcią. Czemu implementacje malloc(3)
preferują drugą opcję? Wyjaśnij to odwołując się do mapy pamięci wirtualnej procesu.
Wskazówka: Rozważ scenariusz, w którym proces zwolnił dużo pamięci przydzielonej na początku jego życia.
Użycie funkcji sbrk(2)
przesuwa koniec sterty (program break będącym końcem segmentu danych procesu). Niestety jest to nieoptymalne podejście, gdyż jeśli najpierw zaalokujemy brk
działa podobnie do operacji push/pop na stosie. Na przedstawionym poniżej schemacie widać to zachowanie - dopóki nie zwolni się używana pamięć (zielona), to nie jesteśmy w stanie zwolnić pamięci zaalokowanej wcześniej (czerwona).
W przypadku malloc
, który używa mmap(2)
oraz munmap(2)
nie występuje taki problem - gdy zaalokowana pamięć przestaje być potrzebna, zwalniamy ją korzystając z funkcji munmap(2)
. Przedstawia to zachowanie na poniższym schemacie - po zwolnieniu pamięci p2
usuwana jest wybrana część, którą później możemy wykorzystać. Wykorzystywana wartość SIZ
to sizeof(int)
.
Wyjaśnij różnicę między fragmentacją wewnętrzną i zewnętrzną. Czemu nie można zastosować kompaktowania w bibliotecznym algorytmie przydziału pamięci? Na podstawie §2.3 opowiedz o dwóch głównych przyczynach występowania fragmentacji zewnętrznej.
Fragmentacja wewnętrzna (ang. internal fragmentation) dotyczy niewykorzystania pamięci wewnątrz przydzielonego bloku i najczęściej jest skutkiem operowania przez system większymi jednostkami, niż dokładność specyfikacji potrzeb ze strony aplikacji lub jądra systemu. Oznacza to więc, że pozostawiany jest niewykorzystany fragment przestrzeni adresowej wewnątrz przydzielonego obszaru - formalnie fragment jest zajęty, jednak w rzeczywistości nie jest wykorzystany.
Fragmentacja zewnętrzna (ang. external fragmentation) oznacza podział obszaru pamięci na rozłączne części, które nie stanowią ciągłości w przestrzeni adresowej . Występuje, gdy łączna suma wolnej pamięci jest wystarczająco duża do obsłużenia żądania alokacji pamięci, ale żaden z bloków nie jest dostatecznie duży i ich konsolidacja jest niemożliwa. Załóżmy, że w sytuacji przedstawionej poniżej chcielibyśmy użyć p4 = malloc(7*SIZ)
, jednak byłoby to niemożliwe - jest łącznie 8 wolnych bloków, natomiast najdłuższym ciągłym fragmentem jest 6 bloków.
Kompaktowanie to proces konsolidacji pofragmentowanych danych (zaalokowanej pamięci) w taki sposób, aby były obok siebie. Nie możemy kompaktować pamięci przydzielonej przez malloc(2)
, gdyż wszystkie istniejące wskaźniki by się unieważniły. Być może mamy wskaźnik do tego bloku, który chcemy przenieść, ale algorytm nie zapamiętuje w żaden sposób tego, gdzie są w pamięci wskaźniki wskazujące na ten blok. Wskaźniki wskazywałyby więc na złe miejsca w pamięci, a nie te, na które byśmy chcieli, aby wskazywały.
Głównymi przyczynami występowania fragmentacji zewnętrznej są:
Posługując się wykresem wykorzystania pamięci w trakcie życia procesu opowiedz o trzech wzorcach przydziału pamięci występujących w programach (§2.4). Na podstawie paragrafu zatytułowanego „Exploiting ordering and size dependencies” wyjaśnij jaki jest związek między czasem życia bloku, a jego rozmiarem? Wyjaśnij różnice między politykami znajdowania wolnych bloków: first-fit, next-fit i best-fit. Na podstawie §3.4 wymień ich słabe i mocne strony.
Poniżej przedstawione są trzy wzorce przydziału pamięci występujące w programach na podstawie §2.4 publikacji Dynamic Storage Allocation: A Survey and Critical Review:
Wykres przedstawia użycie pamięci dla GCC w trakcie kompilacji swojego największego pliku z kodu źródłowego - combine.c
. Sposób ten polega na podzieleniu programu na etapy - pierwszy z nich jest największy, gdyż alokowane są największe obiekty, a każdy kolejny jest coraz mniejszy. Po każdej alokacji dużych obiektów następuje ich dealokacja, a następnie alokacja bardzo wielu małych elementów. Widać również, że przez cały czas działania programu jest praktycznie takie samo użycie pamięci dla obiektów
Wykres przedstawia użycie pamięci dla programu Grobnera, który rozkłada skomplikowane wyrażenia na liniowe kombinacje wielomianów (bazy Gröbnera). Ogólnie rzecz biorąc, zużycie pamięci narasta z czasem działania programu mniej więcej w kształt równi pochyłej, z lekkimi odchyłami.
Wykres przedstawia użycie pamięci dla symulatora hiperkostki Lindsay'a. Program alokuje bardzo dużo pamięci na samym początku działania, która jest wykorzystywana przez praktycznie cały czas wykonania. W trakcie jego działania alokowana jest bardzo mała liczba obiektów małych, krótkożyjących.
Podsumowując, są trzy wzorce przydziału pamięci:
Na podstawie paragrafu Exploiting ordering and size dependencies można określić zależność między czasem życia bloku, a jego rozmiarem. Obiekty zaalokowane w tym samym czasie z dużym prawdopodobieństwem umrą w tym samym czasie, więc jeśli zostaną zaalokowane w ciągłym obszarze pamięci, a następnie jednocześnie zwolnione, to zostaną znacznie zmniejszone szanse na rozproszenie obiektów o długiej żywotności pośród tych o krótkiej żywotności. Rozmiar obiektów zwykle jest powiązany z jego typem i zastosowaniem, z tego powodu powinno się unikać przeplatania alokacji obiektów długożyjąch z krótkożyjącymi.
Znajdowanie wolnych bloków odbywa się zgodnie z politykami:
polityka | zasada działania | zalety | wady |
---|---|---|---|
first-fit | Wybierany jest pierwszy wolny blok z listy o rozmiarze wystarczającym na jego przechowanie, a jeśli blok jest za duży - zostaje podzielony. Wyszukiwanie rozpoczyna się na początku listy wolnych bloków. | Prostota działania. | Prowadzi do fragmentacji pamięci, gdyż duże bloki są rozdzielane na początku listy, ponadto duża liczba małych bloków na początku listy powstałych przez rozdzielanie sprawia, że czas wyszukiwania staje się dłuższy. |
next-fit | Wyszukiwanie kontynuowane jest od miejsca, w którym wystąpiła poprzednia alokacja. | Działa szybciej niż first-fit, gdyż zapamiętywane jest miejsce poprzedniej alokacji, przez co niepotrzebne bloki są pomijane. Zmniejsza się również ilość małych bloków na początku listy. | Obiekty z tych samych faz programu są rozrzucone w różnych miejscach w pamięci, co sprawia że fragmentacja jest większa, gdy obiekty w różnych fazach mają różne czasy życia - polityka ta jest również niekorzystna dla lokalności przestrzennej. |
best-fit | Wyszukiwany jest najmniejszy blok, który jest wystarczająco duży, aby przechować dane. | Marnowana jest najmniejsza ilość pamięci. | Działa wolniej niż first-fit i next-fit, bo należy przejrzeć więcej bloków. Nie skaluje się dobrze dla dużych stert z wieloma wolnymi blokami. |
Algorytm przydziału pamięci udostępnia funkcje o sygnaturach alloc: words -> @id
i free: @id -> void
i ma do dyspozycji obszar 50 słów maszynowych. Implementacja używa dwukierunkowej listy wolnych bloków oraz boundary tags. Wyszukiwanie wolnych bloków działa zgodnie z polityką best-fit. Operacja zwalniania gorliwie złącza bloki i wstawia wolne bloki na początek listy. Posługując się diagramem z wykładu wykonaj krokową symulację algorytmu przydziału pamięci dla poniższego ciągu żądań. Należy wziąć pod uwagę miejsce zajmowane przez struktury danych algorytmu przydziału oraz nieużytki.
alloc(5) alloc(12) alloc(15) alloc(8) free(@2) free(@1) free(@3) alloc(10)
Uwaga: Funkcja alloc
zwraca bloki o kolejnych identyfikatorach począwszy od @1
. Adresy są wyrównane do długości słowa.
Gorliwe złączanie (ang. immediate coalescing) polega na złączaniu wolnych bloków tak szybko, jak jest to możliwe, a więc po zwolnieniu pamięci przez free()
.
Korzystamy z dwukierunkowej listy wolnych bloków oraz znaczników granicznych (boundary tags). Oznacza to, że blok w pamięci wygląda tak, jak na poniższym schemacie.
Podobnie jak na wykładzie, zieloną strzałką będziemy oznaczać pierwszy element listy, a czerwoną ostatni. Kolejne operacje przydzielania i zwalniania pamięci będą się odbywać w następujący sposób. Strzałki nie mieszają się, gdyż mamy zawsze tylko jeden duży blok, więc wskaźniki wskazują na ten sam blok.
Rozważmy algorytm kubełkowy (§3.6) (ang. segregated-fit) przydziału pamięci z gorliwym złączaniem wolnych bloków. Jak przebiegają operacje malloc
i free
? Co robi malloc
, gdy na danej liście nie ma wolnego bloku żądanego rozmiaru? Jak poradzić sobie w trakcie złączania wolnych bloków w procedurze free
, jeśli chcemy usunąć ostatni element z listy? Rozważ zastosowanie leniwego złączania wolnych bloków w algorytmie kubełkowym przydziału pamięci – jakie problemy zauważasz?
Algortym kubełkowy (ang. segregated-fit) polega na przechowywaniu list wolnych bloków w taki sposób, że każda lista przechowuje bloki o wyznaczonym rozmiarze (zwykle najmniejsze wartości mają dedykowane listy, a większe listy przechowujące rozmiary od
Operacja alokacji pamięci poleceniem malloc(n)
działa następująco: wybierany jest odpowiedni najmniejszy kubełek, w razie gdy ten kubełek zawiera wolny blok, to wolny blok jest usuwany z listy wolnych bloków i oznaczany jako zajęta, na koniec zwracany jest wskaźnik na ten blok. Gdy kubełek jest już cały zajęty, to należy szukać bloku w kolejnym kubełku. W przypadku, gdy wszystkie kubełki są zajęte, alokowana jest nowa strona przeznaczona dla bloków o żądanym rozmiarze. Wtedy dla wolnego bloku wykonywany jest podział, pamięć alokowana, a pozostałe miejsce jest umieszczane na liście wolnych bloków.
Operacja zwalniania pamięci poleceniem free(ptr)
oznacza najpierw blok jako wolny, a w przypadku gdy sąsiadujący blok jest wolny, są one łączone. Następnie cały wolny blok jest przenoszony do listy wolnych bloków.
Jeśli chcemy zwolnić ostatni element z listy za pomocą free
, musimy wziąć pod uwagę, że ostatni element zawiera wskaźnik na początek większego kubełka - należy więc przepiąć wskaźniki, jednak nie jest to problematyczne, gdyż do początku kolejnego kubełka i końca poprzedniego możemy się dostać w czasie stałym
Złączanie leniwe (ang. deferred coalescing) polega na łączeniu bloków dopiero w momencie, gdy kolejny raz chcemy zaalokować pamięć i nie napotkaliśmy bloku o wystarczająco dużym rozmiarze. Gdybyśmy chcieli leniwie złączać bloki, moglibyśmy zmniejszyć czas wyszukiwania bloków przy małych alokacjach. Problemem wynikającym z tego podejścia jest zwiększenie fragmentacji:
Powyższe grafiki pochodzą z publikacji Visualising Dynamic Memory Allocators.
Dla metod przydziału pamięci użytych w poniższych zadaniach należy być przygotowanym na wyjaśnienie:
alloc
i free
?Metadane to informacje przechowywane wraz z blokiem, które go opisują. Mówią o jego rozmiarze, zajętości, przechowują wskaźniki na poprzedni/kolejny element.
Nieużytyki (ang. waste) to pamięć, która została zaalokowana, lecz nie można jej użyć.
Fragmentacja wewnętrzna i fragmentacja zewnętrzna zostały opisane w rozwiązaniu zadania 2.
Program objpool
zawiera implementację bitmapowego przydziału bloków o stałym rozmiarze. Algorytm zarządza pamięcią w obrębie aren przechowywanych na jednokierunkowej liście arenas
. Pamięć dla aren jest pobierana od systemu z użyciem wywołania mmap(2)
. Areny posiadają nagłówek przechowujący węzeł listy i dodatkowe dane algorytmu przydziału. Za nagłówkiem areny znajduje się pamięć na metadane, a także bloki pamięci przydzielane i zwalniane funkcjami alloc_block
i free_block
.
Używając funkcji opisanych w bitstring(3)
uzupełnij brakujące fragmenty procedur. Metadane w postaci bitmapy są przechowywane za końcem nagłówka areny. Ponieważ odpluskwianie algorytmu może być ciężkie, należy korzystać z funkcji assert(3)
do wymuszania warunków wstępnych procedur. Twoja implementacja algorytmu zarządzania pamięcią musi przechodzić test wbudowany w skompilowany program objpool
.
Bitmapowy przydział to sposób reprezentacji wolnych i zajętych bloków w tablicy bitów.
Strukturą danych przechowującą informacje o blokach jest tablica bitów typu bitstr_t
. Aby przechować wszystkie metadane, używane jest nitems
bitów (zaokrąglone do object_t
) oraz po nitems
, nfree
oraz wskaźnik *items
.
Operacja alokowania pamięci alloc
polega na znalezieniu pierwszej areny z wolnymi blokami, następnie znalezieniu indeksu wolnego bloku w znalezionej arenie, zmniejszeniu liczby wolnych bloków i oznaczeniu bloku jako zajętego. Na koniec zwracany jest wskaźnik na blok. Pesymistycznie operacja ta zostanie wykonana w czasie
Operacja zwalniania pamięci free
polega na znalezieniu areny o odpowiednim zakresie indeksów (wskaźników), zmiany wskaźnika na indeks bloku w danej arenie a następnie oznaczeniu bloku jako wolny i zwiększeniu liczby wolnych bloków. Pesymistyczny czas działania to
W tym systemie nie powstają żadne nieużytki, gdyż wszystkie bloki są rozmiaru struktury object_t
. Z tego powodu każdy blok jest "dobry" i może podlegać alokacji. Nietesty stworzone areny nie zostają nigdy zwolnione, więc nawet po zwolnieniu całej pamięci nie zostanie ona oddana systemowi. Fragmentacje nie są problemem, gdyż rozmiar wszystkich bloków jest taki sam.
Kod uzupełnionych funkcji z pliku objpool.c
:
static arena_t *init_arena(arena_t *ar) {
/* TODO: Calculate nitems given ARENA_SIZE, size of arena_t and object_t. */
// We need free space to calculate how much items we can store in the bitmap,
// for which we use bitstr_size (it returns number of elements of bitstr_t
// that are necessary to store nbits = (free_space / sizeof(object_t)) bits.
size_t free_space = ARENA_SIZE - sizeof(arena_t);
size_t bitmap_size = bitstr_size(free_space / sizeof(object_t));
size_t nitems = (free_space - bitmap_size) / sizeof(object_t);
ar->nitems = nitems;
ar->nfree = nitems;
/* Determine items address that is aligned properly. */
ar->items = arena_end(ar) - nitems * sizeof(object_t);
return ar;
}
static void *alloc_block(arena_t *ar) {
assert(ar->nfree > 0);
int index;
/* TODO: Calculate index of free block and mark it used, update nfree. */
// bit_ffc is used to store in the location referenced by &index of the
// first bit not set in the array ar->bitmap of ar->nitems bits and if
// all bits are set to 1, then the &index is set to -1 (that's why we
// have to use assert). Then we use bit_set to set the bit index in given
// array ar->bitmap. Afterwards we decrement number of free arenas.
bit_ffc(ar->bitmap, ar->nitems, &index);
assert(index != -1);
bit_set(ar->bitmap, index);
ar->nfree--;
return ar->items + sizeof(object_t) * index;
}
static void free_block(arena_t *ar, void *ptr) {
int index = (ptr - ar->items) / sizeof(object_t);
/* TODO: Determine if ptr is correct and mark it free, update nfree. */
// We have to assure that index we use is in the range of nitems, then
// test (using bit_test) whether given index bit is set or not. If it is
// set, then use bit_clear to clear it and increase free arenas' amount.
assert(index < ar->nitems);
assert(bit_test(ar->bitmap, index));
bit_clear(ar->bitmap, index);
ar->nfree++;
}
Zoptymalizuj procedurę alloc_block
z poprzedniego zadania. Główną przyczyną niskiej wydajności jest użycie funkcji bit_ffc
. Należy wykorzystać dwa sposoby na jej przyspieszenie:
ffs2
wyznaczającej numer pierwszego ustawionego bitu w słowie maszynowym,Komentarz: Bardzo dobry algorytm musiałby jeszcze wziąć pod uwagę strukturę pamięci podręcznej procesora.
Program stralloc
implementuje algorytm zarządzania pamięcią wyspecjalizowany pod kątem przydziału miejsca dla ciągów znakowych nie dłuższych niż MAX_LENGTH
. Ponieważ algorytm wie, że w blokach będą składowane ciągi znakowe, to nie musi dbać o wyrównanie adresu zwracanego przez procedurę stralloc
.
Podobnie jak w programie objpool
będziemy zarządzać pamięcią dostępną za nagłówkiem areny. W obszarze tym zakodujemy niejawną listę (ang. implicit list) jednokierunkową, której węzły są kodowane w pierwszym bajcie bloku. Wartość bezwzględna nagłówka bloku wyznacza jego długość, a znak dodatni i ujemny kodują to czy blok jest wolny, czy zajęty. Nagłówek bloku o wartości zero koduje koniec listy. Ponieważ domyślnie arena ma długość init_chunk
musi wypełnić zarządzany obszar wolnymi blokami nie większymi niż MAX_LENGTH+1
.
Twoim zadaniem jest uzupełnienie brakujących fragmentów procedur alloc_block
i strfree
. Pierwsza z nich jest zdecydowanie trudniejsza i wymaga obsłużenia aż pięciu przypadków. Będzie trzeba dzielić bloki (ang. splitting), złączać (ang. coalescing) lub zmieniać rozmiar dwóch występujących po sobie wolnych bloków, jeśli nie da się ich złączyć. Druga procedura jest dużo prostsza i zaledwie zmienia stan bloku upewniwszy się wcześniej, że użytkownik podał prawidłowy wskaźnik na blok.
Przed przystąpieniem do rozwiązywania przemyśl dokładnie działanie procedur. Pomyłki będą ciężkie do znalezienia. Jedyną linią obrony będzie tutaj obfite sprawdzanie warunków wstępnych funkcją assert(3)
.
Rozważ następujący scenariusz: program poprosił o blok długości
Komentarz: Celem tego zdania jest przygotowanie Was do implementacji poważniejszego algorytmu zarządzania pamięcią, który będzie treścią drugiego projektu programistycznego. Potraktujcie je jako wprawkę!
Niejawna lista (ang. implicit list) to lista, która nie przechowuje wskaźników na kolejne elementy, lecz ich rozmiar oraz to, czy dany blok pamięci jest zajęty czy wolny. Na poniższym schemacie jest widoczna przykładowa niejawna lista. Nagłówki (ang. headers) przechowują dwie informacje: rozmiar bloku oraz zajętość. Na biało oznaczone są bloki wolne, na szaro zaalokowane. Pamięć nieużywana przy bloku oznaczonym 4/1
jest opcjonalnym wypełnieniem (ang. padding). Bloki są wyrównane do długości dwóch słów.
Przechowywane dane w zadaniu są w sposób opisany powyżej, więc w jednokierunkowej liście niejawnej. Nagłówek przechowuje długość bloku i niejawnie wskazuje następnika. Metadane zajmują więc
Operacja alokacji pamięci alloc
tworzy arenę, gdy jeszcze żadna nie istnieje, a następnie próbuje alokować pamięć o danym rozmiarze len
w każdej arenie po kolei. W obrębie jednej areny mamy kilka ścieżek z możliwościami:
NULL
.*data
i jest rozmiaru len
, to oznaczamy go jako zajęty i zwracamy wskaźnik do niego.*data
wielkości len
, a druga do końca wolnego miejsca. Pierwszy blok oznaczamy jako zajęty i zwracamy wskaźnik do niego.*data
, to łączymy je i wracamy do punktu 1.Gdyby nie udało się zaalokować miejsca w arenie, to tworzymy nową i tam alokujemy pamięć. Pesymistyczny czas działania tej operacji to
Operacja zwalniania pamięci free
jest znacznie prostsza. Znajdujemy arenę, w której leży wskaźnik, a następnie oznaczamy blok jako wolny. Pesymistyczny czas działania tej operacji to
Maksymalnym rozmiarem nieużytków jest MAX_LENGTH - 1
, gdyż wtedy pomimo dostępnej pamięci na MAX_LENGTH - 1
nie będziemy mieli miejsca na przechowanie danych długości MAX_LENGTH
. W przypadku stralloc
fragmentacja zewnętrzna już jest problemem, gdyż alokowane bloki mogą mieć różne rozmiary i powstają wolne miejsca. Fragmentacja wewnętrzna nie jest problemem, gdyż wskaźniki nie muszą być wyrównywane.
Kod uzupełnionych funkcji z pliku stralloc.c
:
static void *alloc_block(int8_t *data, uint8_t len) {
void *result = NULL;
while (!END_OF_CHUNK(data)) {
if (BLOCK_USED(data)) {
/* TODO: occupied block */
MOVE_NEXT(data);
} else if (BLOCK_SIZE(data) == len) {
/* TODO: free block of exact size */
BLOCK_HEADER(data) = BLOCK_SIZE(data);
result = CURRENT_PTR(data);
break;
} else if (BLOCK_SIZE(data) > len) {
/* TODO: free block is too large */
int8_t free_space = BLOCK_SIZE(data) - len;
BLOCK_HEADER(data) = len;
NEXT_BLOCK_HEADER(data) = free_space;
result = CURRENT_PTR(data);
break;
} else if (!NEXT_BLOCK_FREE(data)) {
/* TODO: next block is occupied or does not exists */
MOVE_NEXT(data);
} else if (NEXT_BLOCK_SIZE(data) <= len - BLOCK_SIZE(data)) {
/* TODO: merge two free blocks, but do not allocate */
int8_t size = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
BLOCK_HEADER(data) = -size;
} else {
/* TODO: merge two free blocks and allocate with split */
int8_t total_size = BLOCK_SIZE(data) + NEXT_BLOCK_SIZE(data);
int8_t next_block_size = total_size - len;
BLOCK_HEADER(data) = len;
NEXT_BLOCK_HEADER(data) = -next_block_size;
result = CURRENT_PTR(data);
break;
}
}
return result;
}
static void strfree(char *str) {
if (str == NULL)
return;
int8_t *sstr = (int8_t *)str;
#if DEBUG_LEVEL > 0
assert(sstr[-1] > 0);
arena_t *ar = find_ptr_arena(&arenas, str);
assert(ar != NULL);
#if DEBUG_LEVEL > 1
int8_t *ptr = (int8_t *)ar + sizeof(arena_t);
while (ptr < sstr - 1) {
assert(*ptr != 0);
ptr += (*ptr > 0 ? *ptr : -*ptr);
}
assert(ptr == sstr - 1);
#endif
#endif
/* TODO: mark block as free */
assert (*ptr > 0);
*ptr *= -1;
}
Przed rozwiązywaniem zadań warto się zapoznać z podrozdziałem 11.4 CS:APP oraz rozdziały 2, 4, 5 i 8 z Unix Network Programming: The Sockets Networking API.
Na podstawie §2.3 i §2.4 omów różnice między: protokołem ip(7)
, datagramowym protokołem udp(7)
i połączeniowym protokołem tcp(7)
. Czym różni się komunikacja półdupleksowa od dupleksowej? Jak TCP radzi sobie z zagubieniem segmentu lub zamianą kolejności wysłanych segmentów po stronie odbierającego? Skąd protokół TCP wie kiedy połączenie zostało zerwane? Jaki problem rozwiązuje sterowanie przepływem (ang. flow control) implementowane przez TCP?
Wskazówka: Przy tłumaczeniu właściwości protokołów posłuż się analogią (np. wysyłanie listu, dzwonienie przez telefon, itp.)
Protokół internetowy (ang. Internet Protocol, IP) to zbiór ścisłych reguł oraz kroków postępowania, które są automatycznie wykonywane przez urządzenia komunikacyjne w celu nawiązania łączności i wymiany danych. Informacja o IP jest dołączona do każdego pakietu, dzięki czemu router może wysłać dane do odpowiedniego miejsca.
UWAGA!! IP to jedyny protokół siciowy, UDP i TCP to protokoły komunikacyjne.
Datagramowy protokół UDP (ang. User/Unreliable Datagram Protocol) to prosty, bezpołączeniowy protokół. Jego zaletą jest niewielki narzut danych sterujących, dodawanych w procesie enkapsulacji. Bezpołączeniowość UDP polega na tym, iż przed rozpoczęciem procesu komunikacji host źródłowy nie wysyła do hosta docelowego żadnych informacji zestawiających to połączenie. Zasada jest taka, że jeśli urządzenie źródłowe chce rozpocząć transmisję, to robi to bez wcześniejszego ustalenia.
Połączeniowy protokół TCP (ang. Transmission Control Protocol) to protokół zapewniający połączenie pomiędzy klientem a serwerem. Klient TCP nawiązuje połączenie z danym serwerem, wymienia dane z tym serwerem, a następnie kończy połączenie.
Protokół ten zapewnia niezawodność, tzn. gdy TCP wysyła dane do odbiorcy, to wymaga potwierdzenia dostarczenia ich, a gdy go nie dostanie - TCP ponownie wysyła dane i czeka dłuższy czas na potwierdzenie. Warto zauważyć, że TCP nie gwarantuje dostarczenia danych. Podsumowując: TCP zapewnia niezawodne dostarczenie danych lub niezawodne powiadomienie o niepowodzeniu.
TCP uporządkowuje dane poprzez dołączenie numeru każdego bajtu, który wysła. Załóżmy, że aplikacja pisze 2048 bajtów do gniazda TCP, powodując wysłanie dwóch segmentów (pojedyncza paczka danych o pojemności 1024 bajtów) danych przez TCP: pierwszy zawiera dane z numerami 1-1024, a drugi z 1025-2048. Gdy segment zostanie dostarczony w złej kolejności, TCP przestawi je na podstawie wysyłanych numerów, a gdy segment zostanie zagubiony, to zostaje wysłany ponownie.
Wykorzystywane przez TCP sterowanie przepływem (ang. flow control) mówi o tym, ile danych może zostać odebranych w jednym czasie. Gwarantuje to, że nadający nie może przepełnić bufora. Rozmiar ten zmienia się jednak dynamicznie, więc gdy aplikacja czyta dane z bufora, ten rozmiar może zostać powiększony. Istnieje również możliwość taka, że bufor gniazda TCP zostanie zapełniony, przez co aplikacja zostanie tymczasowo wstrzymana, aby mogła odczytać dane z bufora, a następnie odebrała kolejne dane.
Połączenie TCP jest dupleksowe, oznacza to, że aplikacja może wysyłać i odbierać dane w obu kierunkach w połączeniu o dowolnej porze. Komunikacja półdupleksowa jest ograniczona względem komunikacji dupleksowej, a więc wysyłanie i odbieranie informacji odbywa się naprzemiennie.
Połączenie TCP zostaje zerwane po wysłaniu przez jedną ze stron pakietu z ustawioną flagą FIN
(od finished), wymaga on potwierdzenia flagą ACK
. Dopuszcza się też awaryjne przerwanie połączenia pakietem z flagą RST
(reset), taki pakiet nie wymaga potwierdzenia.
Analogie do właściwości protokołów:
Funkcja | Działanie |
---|---|
socket(2) |
Stworzenie nowego gniazda (deksryptora gniazda) |
connect(2) |
Nawiązanie połączenia z gniazdem |
bind(2) |
Powiązanie gniazda z nazwą (czyli adresem IP oraz portem) |
listen(2) |
Nasłuchiwanie na połączenia |
accept(2) |
Zaakceptowanie połączenia |
sendto(2) |
Wysłanie wiadomości (danych) do gniazda |
recvfrom(2) |
Odebranie wiadomości (danych) z gniazda |
Omów diagram 4.1 komunikacji klient-serwer używającej protokołu tcp(7)
przy pomocy interfejsu gniazd strumieniowych. W którym momencie następuje związanie gniazda z adresem będącym parą (numer IP, port)? Która ze stron komunikacji używa portów efemerycznych (ang. ephemeral)? Co specyfikuje drugi argument wywołania systemowego listen(2)
? Z jakim numerem portu jest związane gniazdo przekazywane do i zwracane z accept(2)
? Skąd serwer wie, że klient zakończył połączenie?
Komunikacja klient-serwer to architektura systemu komputerowego umożliwiająca podział zadań/ról. Polega ona na ustaleniu, że serwer zapewnia usługi dla klientów, zgłaszających do serwera żądania obsługi (ang. service request).
Gniazda strumieniowe to gniazda oparte na połączeniach, umożliwiają one sekwencyjny przepływ danych z gwarancją przesłania pakietu i zachowania kolejności.
Diagram komunikacji klient-serwer używający protokołu TCP:
socket(2)
), wiąże je z jakąś nazwą (bind(2)
), po czym zaczyna nasłuchiwać połączeń (i je akceptować).connect(2)
i jeśli pomyślnie nawiąże połączenie, to gniazdo zostaje związane z adresem IP oraz unikalnym, lokalnym portem, czyli efemerycznym (ang. ephemeral). Port efemeryczny, inaczej port ulotny to port istniejący tylko na czas trwania połączenia, który wykorzystuje klient. Po zakończeniu połączenia port jest dostępny do ponownego użycia.Polecenie int listen(int sockfd, int backlog)
służy do nasłuchiwania (oczekiwania) na połączenia. Pierwszy argument sockfd
to id deskryptora pliku gniazda, a drugi backlog
to maksymalna liczba połączeń w kolejce dla deskryptora o zadanym sockfd
. W przypadku, gdy kolejka zostanie zapełniona i zostanie wysłane kolejne żądanie, klient może otrzymać błąd z flagą ECONNREFUSED
lub żądanie zostanie zignorowane.
Polecenie (serwera) int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen)
wykorzystywane jest do zaakceptowania połączenia z gniazdem o danym sockfd
. Wypełnia ono adres gniazda klienta *addr
i zwraca podłączony deskryptor, który może być wykorzystany do komunikacji z klientem, używając uniksowych operacji I/O. Gniazdo przekazywane do accept()
jest związane z serwerem, a zwracane z klientem.
Załóżmy, że mamy serwer 192.168.1.1:80
oraz dwóch klientów: 10.0.0.1
i 10.0.0.2
. Klient 10.0.0.1
chce nawiązać połączenie z serwerem na lokalnym porcie 1234
i łączy się. Wtedy serwer ma jedno gniazdo zidentyfikowane jako 10.0.0.1:1234 - 192.168.1.1:80
. Następnie łączy się drugi klient 10.0.0.2
z lokalnym portem 4321
, wtedy serwer ma ma dwa gniazda:
10.0.0.1:1234 -> 192.168.1.1:80 - protocol
10.0.0.2:4321 -> 192.168.1.1:80 - protocol
Omów diagram 8.1 komunikacji klient-serwer używającej protokołu udp(7)
przy pomocy interfejsu gniazd datagramowych. Czemu, w przeciwieństwie do TCP, serwer może rozpocząć pracę zaraz po wykonaniu funkcji bind(2)
? Z jakiej przyczyny interfejs read(2)
i write(2)
po stronie serwera jest niewystarczający? Przedstaw semantykę operacji recvfrom(2)
i sendto(2)
. Na podstawie §8.11 zreferuj efekt jaki przynosi wykonanie connect(2)
na gnieździe klienta.
Gniazda datagramowe to gniazda bezpołączeniowe. Oznacza to, że każdy pakiet jest indywidualnie adresowany i przekierowywany. Nie ma również gwarancji, że pakiet zostanie przesłany, ani że kolejność wysyłanych pakietów zostanie zachowana.
Diagram komunikacji klient-serwer używający protokołu UDP:
sendto(2)
.recvfrom(2)
do momentu otrzymania datagramu od klienta, następnie żądanie jest odsyłane do klienta poprzez sendto(2)
.recvfrom(2)
, po czym ponownie może wykonywać żądania.Serwer używający protokołu UDP może rozpocząć swoje działanie zaraz po użyciu bind(2)
, gdyż nie jest nawiązywane żadne połączenie, więc serwer nie musi na nie oczekiwać. Protokół UDP jest bezpołączeniowy, więc klient nie łączy się z serwerem, a wymiana danych odbywa się za pomocą datagramów.
Interfejs read(2)
i write(2)
jest niewystarczający, gdyż w przypadku protokołu UDP należy odczytać adres, z którego przyszły pakiety, a następnie odesłać je do konkretnego adresu. Służą do tego polecenia recvfrom(2)
oraz sendto(2)
o sygnaturach:
ssize_t recvfrom(int sockfd, void *buf, size_t len, int flags,
struct sockaddr *src_addr, socklen_t *addrlen);
ssize_t sendto(int sockfd, const void *buf, size_t len, int flags,
const struct sockaddr *dest_addr, socklen_t addrlen);
recvfrom(2)
to funkcja służąca do odbierania wiadomości. Jako argumenty przyjmuje deskryptor gniazda sockfd
, wskaźnik *buf
na miejsce, w którym powinna zostać zapisana wiadomość, długość wiadomości len
, flagi flags
specyfikujące odbiór wiadomości, adres struktury *src_addr
, w którym powinny zostać zapisane informacje o adresie wejściowym, jak i długość tej struktury *addrlen
. Po pomyślnym odbiorze wiadomości zwracana jest długość otrzymanej wiadomości w bajtach, gdy nie ma żadnej wiadomości do odebrania, zwracane jest 0
, a w pozostałych przypadkach -1
i ustawiana jest odpowiednia wartość errno
.
sendto(2)
to funkcja służąca do wysyłania wiadomości. Jako argumenty przyjmuje deskryptor gniazda sockfd
, wskaźnik *buf
na bufor z wiadomością do wysłania, jak i jej długość len
. Poza nimi są jeszcze flagi flags
, mówiące o tym jak wiadomość ma zostać wysłana, struktura z adresem odbierającego *dest_addr
, jak i rozmiar tej struktury addrlen
. Pomyślne zakończenie sendto(2)
zwraca liczbę wysłanych bajtów, jednak nie gwarantuje dostarczenia wiadomości. W przypadku błędu zwracane jest -1
i ustawiana jest odpowiednia wartość errno
.
Wykonanie connect(2)
na gnieździe klienta sprawia, że jądro sprawdza, czy nie występują jakieś błędy, np. o nieosiągalnej destynacji, ponadto zapisuje adres IP i port, po czym wraca do procesu, który je wykonał. Od tego momentu nie możemy już ustalić docelowego adresu IP ani portu dla operacji wysyłania. Oznacza to, że nie używamy już sendto(2)
, tylko write(2)
lub send(2)
. Wszystko, co zostanie zapisane do podłączonego gniazda UDP będzie automatycznie wysyłane na adres podany w connect(2)
. Podobnie, nie możemy używać recvfrom(2)
, lecz read(2)
, recv(2)
lub recvmsg(2)
.
Przyjrzyjmy się warunkom brzegowym, które występują w trakcie używania interfejsu gniazd BSD. Kiedy read(2)
i write(2)
na gniazdach strumieniowych zwracają short counts? Skąd wiemy, że odebrany datagram nie został obcięty? Z jakich przyczyn należy być przygotowanym na to, że operacje na gniazdach zwrócą EINTR
? Co się stanie, jeśli klient spróbuje zapisać do gniazda powiązanego z połączeniem, które serwer zdążył już zamknąć? Dlaczego w kodzie funkcji open_listenfd
użyto wywołania setsockopt(2)
z opcją SO_REUSEADDR
? Co by się stało gdyby programista o tym zapomniał?
Wskazówka: Zapoznaj się z §5.8 – §5.15 i §7.4.
write(2)
może zwrócić short count w sytuacji, gdy w buforze gniazda nie ma wystarczająco miejsca, oznacza to że kernel nie mógł skopiować wszystkich danych. Gdy w buforze nie ma w ogóle miejsca, to natychmiastowo zwracany jest wtedy błąd EWOULDBLOCK
. read(2)
zwróci short count, gdy w buforze nie ma wystarczająco miejsca na odczytanie wszystkich danych. Oba wywołania mogą również zwrócić short count, gdy spowodują je ograniczenia wewnętrznego buforowania lub duże opóźnienia sieci.
Datagramy IP, UDP i TCP przechowują w nagłówku informacje o tym, jak dużo informacji jest w nich wysyłanych. Na podstawie tego możemy sprawdzić, czy otrzymany datagram dotarł w pełni, czy ucięty. Inną możliwością jest obliczenie sumy kontrolnej (ang. checksum), a więc pewnej liczby uzyskanej za pomocą specjalnego algorytmu do zapewnienia integralności danych.
W idealnej sytuacji powinniśmy za każdym razem sprawdzać, czy nie został zwrócony błąd EINTR
w trakcie jakiejś operacji na gniazdach, gdyż może on zostać dostarczony w trakcie wywoływania systemowego. Część syscall'i może być bardzo długo, potencjalnie w nieskończoność w przypadku accept(2)
. Jeżeli takie polecenie zostanie przerwane, to w zależności od ustawionych flag i systemu operacyjnego, może zostać ono uruchomione ponownie lub zakończone z błędem - zwrócona wartość w takim przypadku będzie -1
i errno
zostanie ustawione na EINTR
.
Może się zdarzyć taka sytuacja, że klient spróbuje coś zapisać do gniazda powiązanego z połączeniem, które serwer już zamknął. W takim przypadku klient będzie kilkukrotnie automatycznie ponawiał próby wysłania segmentu. Jeżeli w tym czasie serwer nie zostanie uruchomiony ponownie i wysłanie danych przez klienta nie powiedzie się, to zostanie zwrócony błąd. Jeżeli nie było żadnych odpowiedzi od serwera (a więc potencjalnie scrashował), to błędem będzie ETIMEDOUT
. Gdy jakiś pośredni router ustalił, że serwer był nieosiągalny i przez ICMP zwrócił mówiącą o tym wiadomość, to błędem będzie EHOSTUNREACH
lub ENETUNREACH
.
Czym jest ICMP: ICMP (ang. Internet Control Message Protocol) to protokół sieciowy służący do diagnostyki sieci i trasowania. Jeżeli coś nie działa poprawnie w TCP/IP, to ICMP przejmuje rolę narzędzia do rozwiązywania problemów i zgłasza błędy łączności między hostami.
W kodzie funkcji open_listenfd
użyto wywołania setsockopt(2)
(służy ono do ustawiania opcji gniazda) z flagą SO_REUSEADDR
. Opcja ta służy do zezwolenia na ponowne użycie adresu przez inny proces, bez konieczności oczekiwania na jego zwolnienie. Gdyby flaga ta nie była ustawiona, oczekiwanie na zwolnienie adresu mogłoby trwać nawet kilkadziesiąt sekund.
Zmodyfikuj program hostinfo.c
w taki sposób, aby wyświetlał adresy IPv4 oraz IPv6 dla danej nazwy serwera. Dodatkowo należy przekształcić nazwę usługi przekazanej jako opcjonalny trzeci parametr programu na numer portu. Poniżej przykład:
# hostinfo www.google.com https
216.58.215.68:443
[2a00:1450:401b:803::2004]:443
Co należałoby zrobić, żeby program rozpoznawał usługę o nazwie tftp
?
#include "csapp.h"
int main(int argc, char **argv) {
struct addrinfo *p, *listp, hints;
char buf[MAXLINE], srv[MAXLINE];
int rc, flags;
// strings for arguments given by argv[]
const char *domain, *service;
if (argc == 2) { // default ./hostinfo <domain> run
domain = argv[1];
service = NULL;
} else if (argc == 3) { // handling optional argument
domain = argv[1];
service = argv[2];
} else {
app_error("usage: %s <domain name> [service (optional)]\n", argv[0]);
}
/* Get a list of addrinfo records */
memset(&hints, 0, sizeof(struct addrinfo));
// changed from AF_INET to AF_UNSPEC to handle IPv4 and IPv6
hints.ai_family = AF_UNSPEC;
// changed from SOCK_STREAM to handle tftp
hints.ai_socktype = 0;
/* Connections only */
// Changed NULL to service to get info about it
if ((rc = getaddrinfo(domain, service, &hints, &listp)) != 0)
gai_error(rc, "getaddrinfo");
/* Walk the list and display each IP address */
/* Display address string instead of domain name */
flags = NI_NUMERICHOST | NI_NUMERICSERV;
for (p = listp; p; p = p->ai_next) {
Getnameinfo(p->ai_addr, p->ai_addrlen, buf, MAXLINE,
srv, MAXLINE, flags);
if (service && p->ai_family == AF_INET6) // handle IPv6
printf("[%s]:%s\n", buf, srv);
else if (service)
printf("%s:%s\n", buf, srv);
else
printf("%s\n", buf);
}
/* Clean up */
freeaddrinfo(listp);
return EXIT_SUCCESS;
}
Aby program rozpoznawał usługę tftp
, należy zmienić ai_socktype
na 0
. Oznacza to, że zaakceptowany zostanie każdy rodzaj gniazda.
Zapoznaj się z kodem źródłowym serwera echoserver.c
i klienta echoclient.c
usługi podobnej do echo
. Twoim zadaniem jest taka modyfikacja serwera, by po odebraniu sygnału SIGINT
wydrukował liczbę bajtów odebranych od wszystkich klientów, po czym zakończył swe działanie.
Używając programu watch
uruchom polecenie netstat -ptn
, aby obserwować stan połączeń sieciowych. Wystartuj po jednym procesie serwera i klienta. Wskaż na wydruku końce połączenia należące do serwera i klienta. Następnie wystartuj drugą instancję klienta. Czemu nie zachowuje się ona tak samo jak pierwsza? Co zmieniło się na wydruku z netstat
?
Zadaniem serwera jest nasłuchiwanie na komunikaty klienta. Program działa podobnie do echo
, wysłane przez klienta wiadomości są natychmiastowo zwracane przez serwer.
Kod klienta:
#include "csapp.h"
#include "rio.h"
int main(int argc, char **argv) {
if (argc != 3)
app_error("usage: %s <host> <port>\n", argv[0]);
char *host = argv[1];
char *port = argv[2];
char buf[MAXLINE];
rio_t rio;
int clientfd;
clientfd = Open_clientfd(host, port);
rio_readinitb(&rio, clientfd);
while (Fgets(buf, MAXLINE, stdin) != NULL) {
Rio_writen(clientfd, buf, strlen(buf));
Rio_readlineb(&rio, buf, MAXLINE);
Fputs(buf, stdout);
}
Close(clientfd);
return EXIT_SUCCESS;
}
Kod serwera (uzupełniony):
#include "csapp.h"
#include "rio.h"
#define LISTENQ 1
static size_t nread = 0;
static void sigint_handler(int sig) {
/* TODO: Change control flow so that it does not return to main loop. */
safe_printf("\nTotal bytes read: %ld.\n", nread);
_Exit(0);
}
static void echo(int connfd) {
size_t n;
char buf[MAXLINE];
rio_t rio;
rio_readinitb(&rio, connfd);
while ((n = Rio_readlineb(&rio, buf, MAXLINE))) {
Rio_writen(connfd, buf, n);
nread += n;
}
}
int main(int argc, char **argv) {
if (argc != 2)
app_error("usage: %s <port>\n", argv[0]);
Signal(SIGINT, sigint_handler);
int listenfd = Open_listenfd(argv[1], LISTENQ);
/* TODO: Print bytes received after SIGINT has been received. */
// This is done in sigint_handler by printing the value of
// global variable nread, which gets changed in echo function.
while (1) {
socklen_t clientlen = sizeof(struct sockaddr_storage);
struct sockaddr_storage clientaddr; /* Enough space for any address */
char client_hostname[MAXLINE], client_port[MAXLINE];
int connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
Getnameinfo((SA *)&clientaddr, clientlen, client_hostname, MAXLINE,
client_port, MAXLINE, 0);
printf("Connected to %s:%s\n", client_hostname, client_port);
echo(connfd);
Close(connfd);
}
}
Aby sprawdzić jak zachowa się dokładnie połączenie sieciowe, należy w kilku okienkach terminala odpalić poniższe polecenia:
[1 terminal] $ ./echoserver 1234 <- ten port przekazujemy do grepa
[2 terminal] $ watch "netstat -ptn | grep 1234"
[3 terminal] $ ./echoclient localhost 1234
[4 terminal] $ ./echoclient localhost 1234
Po podłączeniu pierwszego klienta, serwer powiadomi o pierwszym połączeniu poprzez Connected to localhost:45054
:
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address Foreign Address State PID/Program name
tcp 0 0 127.0.0.1:45054 127.0.0.1:1234 ESTABLISHED 21339/./echoclient
tcp 0 0 127.0.0.1:1234 127.0.0.1:45054 ESTABLISHED 21329/./echoserver
Po uruchomieniu drugiego klienta i wysłaniu jakiejś wiadomości przez niego, nie zostanie nic do niego zwrócone przez serwer. Jest to spowodowane tym, że serwer aktualnie jest zajęty obsługą pierwszego klienta, o czym mówi poniższy wydruk:
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address Foreign Address State PID/Program name
tcp 14 0 127.0.0.1:1234 127.0.0.1:45068 ESTABLISHED -
tcp 0 0 127.0.0.1:45054 127.0.0.1:1234 ESTABLISHED 21339/./echoclient
tcp 0 0 127.0.0.1:1234 127.0.0.1:45054 ESTABLISHED 21329/./echoserver
tcp 0 0 127.0.0.1:45068 127.0.0.1:1234 ESTABLISHED 21465/./echoclient
Po wyłączeniu pierwszego klienta serwer automatycznie połączy się z drugim klientem, o czym poinformuje wysyłając wiadomość Connected to localhost:45068
. Wszystkie przesłane wiadomości przez klienta nr 2 zostaną automatycznie do niego zwrócone przez serwer.
Serwer z poprzedniego zadania nie radził sobie ze współbieżną obsługą wielu połączeń. Serwer z pliku echoclient-fork.c
naprawia to poważne ograniczenie z użyciem wywołania fork
. Zadaniem głównego procesu jest odbieranie połączeń i delegowanie ich obsługi do podprocesów.
Proces serwera musi zliczać liczbę bajtów odebranych od klientów. W tym celu przydziela dzieloną pamięć anonimową, w której przechowuje tablicę client
. Przy starcie podprocesu umieszcza w tablicy odpowiedni wpis za pomocą procedury addclient
. Żeby uniknąć wyścigów każdy podproces zwiększa własny licznik nread
. Po zakończeniu podprocesu należy wywołać procedurę delclient
, która doda zawartość prywatnego licznika klienta, do globalnego licznika serwera.
W dowolnym momencie działanie serwera może zostać przerwane przy pomocy sygnału SIGINT
. Należy wtedy poczekać na zakończenie podprocesów i wydrukować zawartość globalnego licznika serwera. Poniżej przykładowy wydruk z sesji serwera:
# ./echoserver-fork 8000
[9047] Connected to localhost:36846
[9105] Connected to localhost:36850
[9047] Disconnected!
^C
Server received quit request!
[9105] Disconnected!
Server received 22 bytes
#
#include "csapp.h"
#include "rio.h"
#define LISTENQ 10
#define MAXCLIENTS (PAGE_SIZE / sizeof(client_t))
typedef struct client {
pid_t pid; /* Client process id */
size_t nread; /* Numer of bytes received so far */
} client_t;
/* TODO: Need to define context to be used with sigsetjmp & siglongjmp. */
static client_t *client = NULL;
static sig_atomic_t nclients = 0;
static size_t nread = 0; /* number of bytest received on all connections */
static client_t *findclient(pid_t pid) {
for (int i = 0; i < MAXCLIENTS; i++)
if (client[i].pid == pid)
return &client[i];
return NULL;
}
static client_t *addclient(void) {
client_t *c = findclient(0);
if (c) {
c->pid = -1; /* XXX: must be filled in after fork */
c->nread = 0;
nclients++;
}
return c;
}
static void delclient(pid_t pid) {
client_t *c = findclient(pid);
assert(c != NULL);
nread += c->nread;
c->pid = 0;
nclients--;
}
static void sigchld_handler(int sig) {
pid_t pid;
/* TODO: Delete clients as they die. */
// just go through the list of all clients and if any of them stopped
// working, print the message and delete the client
for (int i = 0; i < MAXCLIENTS; i++) {
pid = client[i].pid;
if (pid && Waitpid(pid, NULL, WNOHANG)) {
safe_printf("[%d] Disconnected!\n", pid);
delclient(pid);
}
}
}
static void sigint_handler(int sig) {
safe_printf("Server received quit request!\n");
/* TODO: Change control flow so that it does not return to main loop. */
// we need to wait for all clients to stop working, thus we do not stop
// the server immediately, but we wait until everyone is disconnected
sigset_t mask;
sigfillset(&mask);
sigdelset(&mask, SIGCHLD);
Sigprocmask(SIG_SETMASK, &mask, NULL);
while (nclients > 0)
Sigsuspend(&mask);
safe_printf("\nTotal bytes read: %ld.\n", nread);
_Exit(0);
}
static void echo(client_t *c, int connfd) {
size_t n;
char buf[MAXLINE];
rio_t rio;
rio_readinitb(&rio, connfd);
while ((n = Rio_readlineb(&rio, buf, MAXLINE))) {
Rio_writen(connfd, buf, n);
c->nread += n;
}
}
int main(int argc, char **argv) {
if (argc != 2)
app_error("usage: %s <port>\n", argv[0]);
sigset_t sig_mask;
sigemptyset(&sig_mask);
sigaddset(&sig_mask, SIGCHLD);
Signal(SIGCHLD, sigchld_handler);
Signal(SIGINT, sigint_handler);
client = Mmap(NULL, PAGE_SIZE, PROT_READ | PROT_WRITE,
MAP_ANON | MAP_SHARED, -1, 0);
int listenfd = Open_listenfd(argv[1], LISTENQ);
/* TODO: Wait for all clients to quit and print a message with nread. */
// As in previous exercise, it is done in sigint_handler.
while (1) {
socklen_t clientlen = sizeof(struct sockaddr_storage);
struct sockaddr_storage clientaddr; /* Enough space for any address */
int connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
static char client_hostname[MAXLINE], client_port[MAXLINE];
Getnameinfo((SA *)&clientaddr, clientlen, client_hostname, MAXLINE,
client_port, MAXLINE, 0);
sigset_t mask;
Sigprocmask(SIG_BLOCK, &sig_mask, &mask);
/* TODO: Start client in subprocess, close unused file descriptors. */
client_t *client = addclient();
pid_t pid = Fork();
if (pid == 0) {
Close(listenfd);
Signal(SIGINT, SIG_IGN);
echo(client, connfd);
Close(connfd);
_Exit(0);
}
client->pid = pid;
Close(connfd);
printf("[%d] Connected to %s:%s\n", pid, client_hostname, client_port);
Sigprocmask(SIG_SETMASK, &mask, NULL);
}
}