Do spisu tresci tematu 2

2.2.1 Algorytmy brk i sbrk




Spis tresci

Wprowadzenie

Struktury

W pliku pliku include/linux/sched.h zdefiniowana jest struktura task_struct, stanowiaca opis kontekstu procesu. W sklad opisu kontekstu wchodzi rowniez informacja o polozeniu i dostepnej pamieci procesu. Jest ona przechowywana w polu ww. struktury o nazwie mm typu mm_struct (definicja rowniez w include/linux/sched.h). W strukturze task_struct znajduje sie ponadto pole rlim typu rlimit[] (definicja w include/linux/resouce.h) opisujace ograniczenia procesu, m.in. ograniczenie na ilosc przylaczonej pamieci operacyjnej.

Ladowanie programu do pamieci

W wyniku wywolania funkcji systemowej exec, a takze podczas inicjacji systemu, do pamieci operacyjnej ladowany jest kod programu oraz rezerwowane jest miejsce na zmienne i stos procesu. W systemie Linux mapa wirtualnej przestrzeni adresowej dzialajacego procesu wyglada nastepujaco:

Podzial wirtualnej przestrzni adresowej

Podzial pamieci jest wyznaczny przez opis kontekstu procesu, a scislej przez jego pole mm (zob. Struktury). Na samym dole przestrzeni adresowej umieszczony jest kod wykonywalny (zazwyczaj od adresu 0, mozna jednak skompilowac jadro tak, zeby pierwsza strona (=4kB) przestrzeni adresowej byla wolna; dzieki takiemu rozwiazaniu przypisania na wskaznik o wartosci NULL powoduja zgloszenie bledu ochrony pamieci. Algorytmy ladowania kodu programu znajduja sie w plikach /fs/binfmt_aout.c oraz /fs/binfmt_elf.c). Za segmentem kodu rozpoczyna sie segment danych. Jego poczatkowa czesc stanowi blok danych inicjowanych (tj. takich, dla ktorych wartosci sa wczytywane z pliku wykonywalnego). Druga czesc to tzw. dane nieinicjowane (bss), zerowane przed uruchomieniem procesu przez system operacyjny. Podzial powyzszy jest wyznaczany przez pola struktury mm:

Zmiana wartosci break

Po co zmieniac wartosc break?

Podniesienie wartosci break jest najprostszym sposobem przydzielenia procesowi pamieci. M.in. funkcje malloc, realloc i free niejawnie zmieniaja wartosc break Opuszczenie wartosci break pozwala zwolnic zasoby (fizyczna pamiec, mapowana do tej pory na fragment wirtualnej przestrzeni adresowej zwalniajacego procesu, moze zostac przylaczona przez inny proces). Umozliwia takze wykorzystanie wirtualnej przestrzeni adresowej procesu, np. na dolaczenie segmentu pamieci dzielonej.

Jak zmieniac wartosc break?

Wartosc break mozna zmienic przy uzyciu funkcji bibliotecznych brk lub sbrk o nastepujacej semantyce:
  • int brk(void *new_brk) - ustawia nowa wartosc break, zwraca -1 w przypadku bledu,
  • void *sbrk(ptrdiff_t increment) - zmienia wartosc break o increment, zwracajac nowa otrzymana wartosc. Zadna z tych funkcji nie jest jednak prostym wywolaniem systemowej funkcji sys_brk (definicja w pliku mm/mmap.c) o semantyce:
  • unsigned long sys_brk(unsigned long brk) - sprobuj zmienic wartosc break i zwroc obowiazujaca wartosc. Jak widac, nie istnieje w systemie cos takiego, jak algorytm sbrk. Algorytmy realizujace funkcje brk i sbrk mozna zrealizowac w latwy sposob np. poprzez wywolanie sys_brk(0) w celu sprawdzenia biezacej wartosci break, a nastepnie ponowne wywolanie sys_brk z odpowiednim parametrem i przygotowanie wyniku na podstawie porownania ze stara wartoscia break

    Kiedy zmiana wartosci break moze sie nie udac?

  • podana nowa wartosc break (czyli adres wirtualny) jest zbyt mala, tzn. mniejsza od wartosci end_code (czyli: program chce oddac wiecej niz posiada).
  • po zwiekszeniu break przekroczono by limit pamieci, ktora proces moze miec przydzielona (limity przydzialu zasobow biezacego procesu sa przechowywane w w tablicy rlim w strukturze task_struct; w systemie Linux limit przylaczonej pamieci operacyjnej dla jednego procesu wynosi standardowo 2GB).
  • w wirtualna przestrzen adresowa pomiedzy stara a nowa wartoscia break jest juz mapowany fragment pamieci fizycznej, np. segment pamieci dzielonej.
  • jest zbyt malo fizycznej pamieci.

    Algorytm brk

    Algorytm jest tak prosty, ze do jego zrozumienia wystarczy skomentowany kod zrodlowy

    Pytania i odpowiedzi

    1. Z jakich plikow zrodlowych korzystalem?

    Najwazniejsze pliki, ktore analizowalem to: arch/i386/entry.S, fs/exec.c, fs/binfmt_aout.c, fs/binfmt_elf.c, include/linux/resource.h, kernel/fork.c, kernel/sched.c, mm/mmap.c

    2. Jakie struktury uwazam za najwazniejsze?

    Za najwazniejsze struktury uwazam struktury opisu kontekstu: struct task_struct, struct mm_struct

    3. Jakie rozwiazania programistyczne uwazam za najciekawsze?

    Opracowujac temat musialem siegnac do algorytmow zarzadzania pamiecia. Za bardzo ciekawe rozwiazanie uwazam zastosowanie wywazonych drzew poszukiwan AVL do przechowywania blokow pamieci przydzielonych procesowi. Za dowcipna ciekawostek uwazam definicje tzw. liczby magicznej STACK_MAGIC sluzacej do sprawdzania integralnosci systemu w momencie wykonywania funkcji exit, ktorej wartosc (w zapisie szestnastkowym) wynosi deadbeef.

    4. Jakie znalazlem ograniczenia na zasoby?

    Najistotniejsze znalezione przeze mnie ograniczenia na zasoby to: MAX_TASKS_PER_USER = 256 (liczba procesow jednego uzytkownika) MIN_TASKS_LEFT_FOR_ROOT = 4 (liczba procesow zarezerwowanych dla administratora), NR_TASKS = 512 (liczba procesow w systemie), TASK_SIZE = 3GB (maksymalny adres w wirtualnej przestrzeni adresowej procesu). Oprocz tego nie nazwany parametr przechowywany w current -> rlim okresla maksymalna ilosc pamieci przylaczonej do procesu na 2GB.

    Bibliografia

    1. Pliki zrodlowe Linuxa:
    2. Linux Kernel Hackers' Guide

    Autor: Grzegorz Jakacki