aktualności

10

grudzień 2007

dział prowadzi: Remigiusz Modrzejewski l [e-mail]

Kernel

aktualności

11

www.lpmagazine.org

dział prowadzi: Remigiusz Modrzejewski [e-mail]

Kernel

O dokumentacji

Michael Kerrisk, wieloletni opiekun

dokumentacji Linuksa, wygłosił cieka-

wą mowę na szczycie LinuxConf Europe

2007. Traktował w niej o pozytyw-

nym wpływie dokumentacji na jakość

kodu, a pisząc strony podręcznika do róż-

nych podsystemów znalazł w swojej ka-

rierze kilka poważnych błędów. Naj-

poważniejszym z nich był błąd w spli-

ce(), bo można było dzięki niemu zawie-

sić program w stanie, w którym nie dało

się go zabić. Dawało to łatwą możliwość

wykonania piorunującego lokalnego ata-

ku DOS. Większe znaczenie, a także bar-

dziej specyficzne dla piszących dokumen-

tację mają znalezione przez niego niedo-

ciągnięcia projektowe. Przykładem,

którym się posłużył były mlock()

i remap_file_pages(). Oba wołania syste-

mowe przyjmują, jako wielkość pamię-

ci dowolną liczbę, potem zaokrąglają do

pełnej strony. Problem polega na tym, że

mlock() zaokrągla w górę, a remap_fi-

le_pages() w dół. Niekonsekwencje

takie, jak ta utrudniają korzystanie z in-

terfejsów, co w efekcie może prowadzić

do błędów w korzystającym z nich ko-

dzie. Prawdą jest, że dokumentowanie

to jeden z podstawowych etapów każde-

go projektu, a Linux powstaje poprzez

burzliwe dyskusje i szybkie implemen-

tacje. Może warto jednak częściej przy-

siąść i opisać spokojnie, co zamierza się

wykonać.

Sysctl() znowu w niełasce

Już w jądrze 2.6.19 miało dojść do histo-

rycznego aktu – usunięcia wołania sys-

temowego sysctl(). Historycznego nie ze

względu na wagę tego wołania, lecz zła-

manie ABI przestrzeni użytkownika. To

według założeń powinno działać wiecz-

nie, ale samo sysctl() przegrało konkuren-

cję z podsystemem /proc/sys i praktycznie

nigdy przez nikogo nie było wykorzysty-

wane. Jako kod jest nieużywany

i rzadko przeglądany, a więc może

w przyszłości ulec jakiemuś przypadko-

wemu uszkodzeniu, a to może zaowoco-

wać poważnym błędem, szkodzącym ca-

łości jądra. Dlatego też Eric Biederman

podjął kolejną próbę uporania się z tą za-

szłością i zaproponował oznaczenie sy-

sctl(), jako przeznaczonego do usunięcia

w 2010 roku. I znowu spotkał się z pro-

testami osób, trzymających się kurczo-

wo zasad. Jak wypomniał Alan Cox, jeśli

ktoś ma praktyczny powód, by w ogóle

korzystać z sysctl(), to jest on na tyle po-

ważny, by nie móc z niego zrezygnować

cokolwiek by się nie działo.

Z drugiej strony Andrew Morton przeko-

nuje, że samo oznaczenie nie jest niczym

strasznym. Przez kilka lat osoby, używa-

jące tego wołania będą konfrontowane

z ostrzeżeniami o planowym usunięciu

– na na koniec zawsze się będzie można

wycofać. Choć dobrze byłoby mieć za

sobą te cykliczne burze w szklance wody.

Większe strony, większe problemy

J

ak powszechnie wiadomo, Linux bardzo
różni się od systemu Windows, a jedną

z poważniejszych niskopoziomowych róż-
nic jest zarządzanie pamięcią. Ostatnio
użytkownicy, kupujący komputery z komer-
cyjnymi systemami na pokładzie przekonu-
ją się, że mimo posiadania 4GB RAM-u
system ,,widzi” jedynie około 3GB. Co cie-
kawe problem ten występuje także w opar-
tym na Uniksie – Apple OSX. Jednak po-
ważniejszym problemem jest fragmentacja
pamięci. Użytkownicy Windows, którym
zdarza się trzymać system włączony całymi
tygodniami po pewnym czasie obserwują
coraz gorszą jego pracę. Ostatecznie nastę-
pują problemy z alokowaniem pamięci do
programów, mimo iż wolna jej ilość wie-
lokrotnie przewyższa potrzeby. Dzieje się
tak, dlatego że programy potrzebują dużych
i ciągłych obszarów pamięci, te jednak są
poszatkowane przez mniejsze zmienne,
a żaden z tych problemów nie dotyczy Li-
nuksa. Dzieje się tak ze względu na spo-
sób, w jaki Linux zarządza pamięcią. Me-
chanizm nazywa się pamięcią wirtualną,
co sugeruje od razu metodę jego działa-
nia. Programy egzystują w wirtualnej prze-
strzeni adresowej – niezależnej od rzeczy-
wistego rozkładu komórek pamięci w sprzę-
cie. Dzięki temu 32-bitowe programy nadal
są ograniczone do 4GB pamięci, ale każdy
program może zająć swoje osobne 4GB. Nie
grozi również brak ciągłej pamięci – pro-
gram zawsze ją dostanie. Programista nie
musi sobie zdawać sprawy, że to jądro skle-
ja ją z nieciągłych kawałków rzeczywistej
pamięci. Mechanizm jest stabilny i dzia-
ła poprawnie już od wielu lat, z pewnymi
zmianami praktycznie od początku. W prze-
ciągu tych lat ilość RAM-u jaką przecięt-
nie dysponujemy zwiększyła się tysiąckrot-
nie, lecz obsługiwana jest nadal tak samo.
W szczególności oznacza to wykorzysty-
wanie sprzętowych stron pamięci o rozmia-
rze 4 kilobajtów. Stronicowanie co praw-
da większości osób kojarzy się wyłącznie
z przestrzenią wymiany (ang. swap space
zarówno plik, jak i partycja), lecz w Linuk-
sie jest to właśnie podstawowy mechanizm
zarządzania wszelką pamięcią.

Mijają lata, a megabajty przekształci-

ły się w gigabajty, natomiast system zarzą-
dzania pamięcią zaczyna sapać. Nie tyl-
ko ze względu na samą obsługę pamię-
ci, która wciąż jest akceptowalnym narzu-

tem. Największym problemem są urządze-
nia wejścia/wyjścia. Karty sieciowe, prze-
znaczone do wysokich transferów w celu
ograniczenia liczby pakietów, a więc i prze-
rwań – stosują wielkie ramki. Aby przesłać
taką wielką ramkę potrzebny jest ciągły ob-
szar fizycznej pamięci, ewentualnie podzie-
lony na jakąś ograniczoną ilość mniejszych.
Systemy plików potrzebują większych blo-
ków na indeksy, aby zmniejszyć ilość ope-
racji wyszukiwania (ang. seek – najkosz-
towniejsza czasowo operacja wykonana
przez dysk) przy dostępie do dowolnego
pliku. Ostatecznie TLB (ang. Translation
Lookaside Buffer – bufor, odwzorowujący
adresy wirtualne na fizyczne wykorzysty-
wane przez pamięć podręczną) w nowych
procesorach Intel ma zaledwie 128 wpisów.
Przy czterokilobajtowej stronie pozwala to
wykorzystać zaledwie pół megabajta cache-
'u, a procesory te posiadają go nawet osiem
razy więcej.

Rozwiązanie nasuwa się samo – pod-

nieść rozmiar tych stron i po kłopocie. Roz-
sądny rozmiar wydaje się oscylować, w za-
leżności od zastosowania, między 8 a 32KB.
Tu jednak niespodzianka – procesory x86
takich rozmiarów nie obsługują. Wielkość
strony ustawić można na kilka różnych
potęg dwójki, lecz nie ma nic między 4KB
a 2MB. Niestety, pomysł ten odpada w przed-
biegach. Alokując po 2MB niezależnie, czy
potrzebny jest megabajt czy kilobajt bar-
dzo szybko zmarnowalibyśmy cały dostęp-
ny RAM. Potrzebne jest rozwiązanie cał-
kowicie programowe, a do tego najlepiej
by było niezależne od tego, na jakiej ar-
chitekturze działa. Oczywiście osoby zaan-
gażowane w rozwój systemu zarządzania
pamięcią zdawały sobie z tego sprawę od
dawna. Spotkali się niedawno na szczycie
w Cambridge, gdzie ustalili kilka sensow-
nych wyjść z tej sytuacji. Jednak, jak się
okazało później, każdy ustalił swoje – bez
wspólnego consensusu – przybliżę te po-
ważniejsze.

Najświeższy pomysł pochodzi od czło-

wieka najdłużej zaangażowanego – Andrea
Arcangeliego, twórcy znacznej części aktu-
alnego kodu pamięci wirtualnej. Jego łatka
CONFIG_PAGE_SHIFT jest realizacją pro-
stego pomysłu, sugerowanego już wcze-
śniej do jądra 2.4, pod wiele mówiącą na-
zwą large PAGE_SIZE. Jak łatwo się do-
myślić, to chodzi o separację pojęcia strony

aktualności

10

grudzień 2007

dział prowadzi: Remigiusz Modrzejewski l [e-mail]

Kernel

aktualności

11

www.lpmagazine.org

dział prowadzi: Remigiusz Modrzejewski [e-mail]

Kernel

Sprytniejsze dławienie

Kiedy proces zapisuje coś na dysku, w rze-

czywistości oznacza jedynie pewną ilość

stron pamięci jako brudne (ang. dirty pa-

ges) – przeznaczone do transferu na fizycz-

ne urządzenie. Procesy mogą tworzyć brud-

ne strony w znacznie szybszym tempie niż

urządzenia je obsłużyć, stąd też pojawia się

konieczność dławienia zapisu (ang. write

throttling). Do tej pory działała ona na pro-

stej zasadzie – jeśli ilość brudnych stron w

systemie przekroczy jakiś z góry ustalony li-

mit, proces chcący zabrudzić kolejną stronę

zostaje uśpiony, aż trafi ona na dysk. Jednak-

że w praktyce często jest to zbytnie uprosz-

czenie. Najłatwiej sobie wyobrazić sytu-

ację, gdy mamy dwa dyski o różnych szyb-

kościach. Do jednego powstaje kolejka na

tyle potężna, że usypiane są procesy chcą-

ce pisać na prawie bezczynny drugi dysk.

Stąd też Peter Zijlstra zaproponował łatkę

wprowadzającą podział tego limitu na osob-

ne dla każdego urządzenia. Stworzył ponad-

to mechanizm adaptujący te limity do rze-

czywistych prędkości urządzeń – jeśli ja-

kieś urządzenie transferuje brudne strony

szybciej/wolniej niż to by wynikało z jego

przydziału pamięci, to zostaje on odpowied-

nio zwiększony/zmniejszony. Łatki trafiły do

testów w gałęzi

-mm

, gdzie ponoć wykaza-

ły skłonność do zawieszania systemów. Jed-

nak pomysł wydaje się dobry i jak wykazały

testy – skuteczny, więc po poprawieniu błę-

dów pewnie wejdzie do gałęzi stabilnej.

C++ jest straszne

Linus Torvalds (tłumaczenie własne):

,,C++ to straszny język. Najstraszniej-

szy ze względu na wielu poniżej-przecięt-

nych programistów w nim programują-

cych. [...] Szczerze, nawet gdyby wybór C

miał służyć jedynie odstraszeniu programi-

stów C++, to samo w sobie byłoby wystar-

czającym powodem by wybrać C”. Następ-

nie wypomina niestabilność i nieprzeność

STL i Boost oraz kiepską wydajność mode-

li abstrakcyjnych. Czyżbym ja też był poni-

żej przeciętnej?

http://article.gmane.org/

gmane.comp.version-control.git/57918

Kto napisał 2.6.23

Na pierwszym miejscu wypływa Ingo Mol-

nar z 152 przyjętymi łatkami. W znacznej

części jest to, dość szybko przyjęty, opisy-

wany już wcześniej CFS oraz... Natychmia-

stowe w nim poprawki. Najwięcej zmienio-

nych linijek przypadło Adrianowi Bunko-

wi, który zajmuje się usuwaniem z jądra ko-

du już niepotrzebnego. Jeśli chodzi o firmy,

na pierwszym miejscu plasuje się niezmien-

nie Red Hat, odpowiadający za około 12%

zmian w jądrze. Więcej linijek zmieniają

jednak hobbyści – 9% łatek, jednak aż 15%

zmian w liniach należy do nich. Sumarycz-

nie do jądra przybyło 430 000 linijek kodu,

ubyło zaś 406 000. Według uproszczonego

modelu COCOMO (http://pl.wikipedia.org/

wiki/COCOMO) samo stworzenie nowych

linijek powinno zająć 2670 osobomiesięcy.

w jądrze od strony w procesorze. Realizacja
ma być prosta – kilka sąsiednich stron fizy-
cznych tworzy jedną stronę logiczną, a wszyst-
kie rozmiary są stałe. W sposób łatwy, lekki
i przyjemny rozwiązuje to wspomniane pro-
blemy (poza niedoborami TLB w Intelach).
Prowadzi jednak do nadmiernego marno-
trawstwa i wewnętrznej fragmentacji. Pro-
blemy te mają być pominięte poprzez me-
chanizm dzielenia mało używanych stron,
lecz nie ma jeszcze do niego ogólnego
przekonania.

Od dawna zaimplementowane jest w ją-

drze trzymanie grup stron, jako sąsiadów
w pamięci fizycznej, a jest to wykorzysty-
wane w niektórych sterownikach, lecz ra-
czej nieśmiało – nikt nie gwarantuje moż-
liwości utworzenia takiej grupy (informa-
cje o aktualnie istniejących znajdziemy
w pliku /proc/buddyinfo). Stąd też Mel Gor-
man od jakiegoś czasu pracuje nad unika-
niem fragmentacji, a ponad dotychczasowe
rozwiązania wnosi pomysł odróżniania tych
stron, które nie mogą być przeniesione od
tych, które mogą być. W momencie alokacji
grupy stron, jeśli zabraknie na nią sąsied-
nich stron wolnych, to system spróbuje po-
szukać sąsiednich stron wolnych i reloko-
walnych, a zrezygnuje dopiero nie znajdu-
jąc takich. Efekty jego pracy są sukcesyw-
nie, bo po kawałku wprowadzane do kolej-
nych wersji jądra.

Uzupełnieniem pracy Gormana ma być

zestaw łatek Cristopha Lametera, ponie-
waż zaimplementował mmap(), operują-
cy na blokach większych niż jedna stro-
na. Rozwiązuje to większość problemów
z wejściem/wyjściem i systemami plików.
Rozwiązanie to zostało poważnie oprote-
stowane. Do poprawnej pracy wymaga cią-
głej dostępności wielokrotnych stron pa-
mięci, której nikt nie gwarantuje. Nawet z
uwzględnieniem unikania fragmentacji sys-
tem może dojść do stanu, w którym nie bę-
dzie mógł przenieść nic więcej by utworzyć
nową grupę.

Łatwo sobie wyobrazić wykorzystanie

takiej podatności w ataku DOS, prowadzą-
cym do całkowitego paraliżu kluczowych
części jądra. Dlatego też, jeśli ten zestaw
łatek zostanie włączony do stabilnego ją-
dra, to będzie od początku dyskryminowa-
ny i obarczony poważnymi ostrzeżeniami
o wszystkich niebezpieczeństwach. Dlatego
pewne nadzieje na dziś wiąże się z fsblock
Nicka Piggina. Wśród zmian przez niego
wprowadzanych znajduje się umożliwienie

systemom plików korzystania z większych
bloków. Nie ma tu jednak wymogu dostęp-
ności ciągłych grup stron. Zamiast tego uży-
wane jest vmap(), aby udostępnić wirtualnie
ciągłą przestrzeń dla vmalloc(). Technika ta
wykorzystywana jest już przez XFS. Jednak
vmap() jest kosztowne samo w sobie, nie
oferując nic by usprawnić wejście/wyjście.
Dlatego też Nick planuje wykorzystywa-
nie rzeczywistych grup stron, zostawiając
vmap(), jako wyjście awaryjne w razie ich
niedostępności. Jednak łatka, którą przygo-
tował do tej pory już jest przerażająco wiel-
ka. Do tego są to zmiany fundamentalne
i dotykające bardzo wielu miejsc w kodzie
jądra. Jedynym systemem plików, dostoso-
wanym do pracy z nią jest do tej pory naj-
prostszy Minix, co i tak wymagało dość du-
żo pracy. Mimo relatywnie ciepłego przy-
jęcia minie dużo czasu zanim zobaczymy
ostateczną wersję fsblock.

Powstają i upadają inne pomysły, będą-

ce bardziej lub mniej podobnymi do przed-
stawionych. I choć dyskusja na LKML-u
(ang. Linux Kernel Mailing List, miejsce
dyskusji twórców jądra) w ostatnich dniach
ciągnęła się przez kilkaset postów, nadal
nie wiadomo, który kierunek będzie osta-
tecznie obrany. Sprawy nie ułatwia sam
Linux, a można powiedzieć, że staje oko-
niem. Przekonuje, że to na konstruktorach
procesora leży obowiązek wyposażenia go
w TLB odpowiedni do wielkości pamięci
podręcznej.

Aktualne podejście z czterokilobajto-

wymi stronami, czasami grupowanymi w pa-
ry, wydaje mu się słuszne i stabilne. Proble-
my z wydajnością powinno się rozwiązy-
wać, przechodząc na architekturę x86_64.
Na koniec, jak zawsze nie przebierając
w słowach, nazywa ludzi propagujących no-
we pomysły szaleńcami, bo nie powinno
się opierać projektów na sugestiach sza-
leńców. Z przyczyn obiektywnych należy
przypuszczać, że jakaś wariacja, któregoś
z przedstawionych pomysłów wejdzie kie-
dyś w życie. Nie stanie się to za szybko,
a nawet bez sprzeciwu Torvaldsa drobne
zmiany w systemie pamięci wirtualnej nig-
dy nie są przyjmowane szybko. Zmiana tak
fundamentalna będzie potrzebowała wielu
miesięcy testów zanim zostanie zaakcep-
towana.

http://lwn.net/Articles/250335/
http://lwn.net/Articles/250466/