Kernel Traffic #128 For 30 Jul 2001

Mamy już całkiem fajny interfejs do tablic haszujących w BitKeeperze, który chcielibyśmy udostępnić na zasadach GPL. Zawsze myślałem, że fajnie byłoby mieć go i w jądrze -- my wykorzystujemy go wszędzie.

http://bitmover.com:8888//home/bk/bugfixes/src/src/mdbm

pozwoli Ci się mu bliżej przyjżeć. Ogólny interfejs jest zbliżony do gdbm() i dostępne są wersje opierające się zarówno na pliku jak i na pamięci. Interfejs został zaprojektowany tak, aby być użytecznym zarówno w dużych jak i w małych plikach konfiguracyjnych; o ile dobrze pamiętam możesz mieć hasza 128-bajtowego.

Przetestowałem wszystkie implementacje, żeby zobaczyć, jak sobie poradzą z indeksowaniem katalogów. Tak naprawdę są tylko dwa kryteria oceny:

1. Jak losowy jest hasz
2. Jak jest wydajny

Moich testów nie można raczej nazwać precyzyjnymi. To co głównie robię to haszowanie wielu nielosowych ciągów znaków i sprawdzanie czy ich rozkład po rozrzuceniu jest w miarę jednostajny. *Jedyną* funkcją ze zbioru Larry'ego, która dobrze działała z punktu widzenia losowości był hasz liniowy bazujący na własnościach kongruencji (,,linear congruential hash'') - był prawie tak dobry jak mój dx_hack_hash.

Niespodziewanie, przynajmniej dla mnie, okazało się, że CRC32 zachowuje się w niezwykle zmienny sposób. Z małą liczbą ,,kubełków'' (powiedzmy 100) daje sobie dobrze radę, ale przy większej ich liczbie rozkład okazuje się być dość dziwny. Oczywiście to co piszę jest zbyt mało precyzyjnym sposobem opisu tego, co się zdarzyło i powinienem się temu bliżej przyjrzeć. Nie mam odpowiednich podstaw matematycznych, aby być tego w pełni pewnym, ale podejrzewam, że CRC32 nie jest w ogóle optymalizowana z punktu widzenia losowości - jest optymalizowana ze względu na wykrywanie błędów w pojedynczych bitach i ma dobre własności w odniesieniu do sąsiadujących bitów, własności, które nie są użyteczne w funkcjach randomizujących. W każdym razie nie byłem taki znowu nieszczęśliwy widząc, że CRC32 nie zachowuje się dobrze z dwóch powodów: a) tablica xor, 1K pokazałaby 25% wzrost kodu opowiadającego za indeksowanie i b) haszowanie przez tablice zjada dodatkowe 1K cennego cache 1L.

Liniowy hasz oparty na kongruencji ze zbioru Larry'ego i mój dx_hack_hash mają wspólną cechę: obydwa kodują każdy znak przy użyciu pseudolosowego ciągu. W haszu Larry'ego jest to liniowa sekwencja kongruentna, w moim jest to zwrotne przesunięcie rejestru. Dodatkowo, używam zwielokrotnienia tak, żeby rozproszyć efekt kodowania pojedynczych znaków na szerszy zakres bitów.

Hasz Larry'ego tego nie robi i można zauważyć, że łañcuchy znaków, które różnią się tylko ostatnim znakiem nie będą rozrzucane losowo. To mogłoby działać trochę lepiej gdyby haszowanie było robione bardziej w ten sposób:

- ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
+ ((h) = 0x63c63cd9*(h + (c)) + 0x9c39c33d)

Nie próbowałem tego, ale spróbuję.

Jest paru ludzi, którzy wiedzą dużo więcej ode mnie o analizowaniu funkcji skrótu i gdzieś w mojej skrzynce pocztowej są ich nazwiska. Poproszę ich wkrótce o przetestowanie całego pakietu funkcji, które były mi w ostatnich miesiącach podsuwane. Tak czy inaczej, gdybyście jeszcze tego nie odkryli, ten rodzaj działalnosci jest naprawdę czasochłonny.

Chciałbym zapytać czego jeszcze brakuje aby rozpocząć prace nad serią 2.5, i dlaczego seria 2.4 nie została przekazana pod opiekę Alana Coksa.

Pytam, ponieważ uważam, że seria 2.4 jest już wystarczająco stabilna i sądzę, że należy rozpocząć rozwój 2.5.

Obecnie w serii 2.4 dołączane są jedynie małe poprawki, które bez żadnego problemu mogłyby być dokonywane przez Alana.

Czy Linus ma jakiś plan dotyczący przekazania kierownictwa nad 2.4 i rozpoczęcia prac na wspaniałym jądrem 2.5?

21 czerwca Linus wypowiedział się następująco w poście wysłanym na linux-kernel:

"Wygląda na to, że rozpoczniemy zabawę z 2.5.x za tydzieñ czy dwa, więc nie mówimy o jakiś odległych terminach".

Zatem przypuszczalnie planuje rozpoczęcie prac na 2.5.x niebawem (osobiście sądzę, że stanie się to w momencie ukazania się jądra 2.4.8, ale to tylko takie moje gdybanie :-)

Na stronie ftp://oss.sgi.com/projects/xfs/download/Release-1.0/patches/linux-2.4.2-kdb-04112001.patch.gz jest kdb v1.8 dla Red Hata 7.1. W łacie cie ma żadnych zależności od XFS, ale kdb i xfs współdzielą kilka plików, więc pewnie będziesz musiał uporać się z tym, że łata nie zaaplikuje się czysto.

Dużo łatwiej zacząć od tej łaty niż próbować dostosować łatę kdb na zwykłe jądro do jądra Red Hata. RH używa łat z serii -ac, które dość mocno zamieszały w kdb i zajęło mi kilka godzin, aby dojść do tego co RH napsuł i przygotować łatę z kdb. AFAICR, łata IKD nie pasuje zbyt dobrze do RH 7.1.

Na razie nie robię łaty z kgdb na RH7.1. Oto wyciąg z właśnie uaktualnionego FAQ na stronie.

Dlaczego tylko jedna wersja jądra jest obsługiwana? Rozwijam kgdb i piszę do niego dokumentację dość często i regularnie. Ten proces jest łatwy do przeprowadzenia z jedną wersją jądra, ponieważ mogę równolegle pracować nad samym jądrem jak i jego współpracą z kgdb. Osobiście używam kgdb do pracy w nowych jądrach nad systemami plików. Utrzymywanie kgdb dla starszych wersji jądra wymagałoby konwersji nowych rzeczy dla ich potrzeb i testowania. Zazwyczaj łata z kgdb działa z wieloma wersjami jądra, choć być może trzeba ręcznie poprawiać parę drobnych niezgodności. Gdy rozpocznie się rozwój jądra 2.5, chcę aby kgdb obsługiwało zarówno 2.4, jak i 2.5.

Wyróżnia się ext3, z powodu swej zgodności z ext2 - sprawia ona, że łatwo jest przejść z ext2 na ext3 bez utraty/przenoszenia danych. Łatwiej także przenieść napęd z jednej maszyny do innej bez obawy o to, czy w drugim jądrze wkompilowana jest obsługa reiserfs czy też inne ustrojstwa.

Jednakże słyszałem, że ext3 jest wolniejszy (najwyraźniej z powodu dodatkowych operacji zapisywania) i czasami niestabilny.

Słyszałem także, że ReiserFS jest najszybszy z całej stawki, ale przy konwersji tracone są wszystkie dane, no i oczywiście ratowanie danych i przenoszenie dysków jest utrudnione. Dołączony jest on za to w oficjalnym jądrze..

Odpowiem jako obecny zarządca kodem NTFS. (-:

Jeśli przez ,,kiepską obsługę'' rozumiesz, że projekt był przez dłuższy czas nierozwijany, to rzeczywiście wiele się zmieniło. Obsługa NTFS w jądrze Linuksa i po stronie programów użytkownika jest aktywnie rozwijana. Teraz z przyjemnością otrzymuję różne łaty i przekazuję dalej do Linusa, o ile na to zasługują, bądź włączam je do mojego lokalnego jądra, aby poźniej odesłać w postaci większej łaty (zależy to od błahości łatek). Zawsze staram się jak najszybciej odpowiadać na różne zapotrzebowania/raporty o błędach/itp. Aktualnie czas reakcji waha się pomiedzy 5min. a tygodniem, w zależności od tego, jak jestem zajęty.

Jeśli przez ,,kiepską obsługę'' rozumiesz, że nie działa zbyt dobrze, to to też się znacząco poprawiło. Mamy już w pełni funkcjonalny program mkntfs po stronie używtkownika oraz ntfsfix, który naprawia szkody wyrządzane przez sterownik ntfs, co czyni pracę z ntfs pod Linuksem nieco bezpeczniejszą. Sam sterownik przez ostatnie kilka miesięcy znacznie się poprawił. Zapisywanie działa całkiem dobrze o ile działa się na systemie jednoprocesorowym, i o ile działa się na małych plikach i katalogach. Cały czas pozostaje gros pracy do wykonania, więc na razie tylko prostsze przypadki działają. Odczytywanie działa w miarę stabilnie i w zakresie odczytu atrybutów plików zarówno skompresowanych jak i nieskompresowanych większość rzeczy jest już zaimplementowana. Teraz możemy się zająć się dużymi plikami aż to górnych ograniczeñ NTFS (np. teraz walczymy z plikami o rozmiarze do 2^63 bajtów) żeby wymienić tylko jeden przykład usprawnieñ.

Gwoli podsumowania: pracujemy ciężko, ale nie wstrzymuj oddechu. NTFS ma bardzo złożoną strukturę i jest nędznie udokumentowany. Większość naszej wiedzy bazuje na reverse engineeringu i zaglądaniu bezpośrednio w struktury dyskowe przy użyciu edytorów dysku i to zajmie trochę czasu zanim otzymamy w pełni działającą i w pełni funkcjonalną implementację NTFS...

Drugie wydanie książki _Linux_Device_Drivers autorstwa Alessandro Rubiniego i mojego w koñcu jest dostępne online. Znajdziecie je pod adresem:

http://www.xml.com/ldd/chapter/book/index.html

Książka znajduje się tam w formie HTML-a, PDF-a i XML-a (DocBook). Wydana jest na licencji GNU FDL, która pozwala na jej redystrybucję i wszystkie inne fajowe rzeczy.

Kłóciłem się już o to parę lat temu z ludźmi od gcc i dali mi oni bardzo logiczny argument na uzasadnienie obecnej semantyki.

• "static inline" oznacza "musimy mieć tę funkcję, jeśli jej używasz i nie jest ona 'inline', to zrób jej statyczną wersję w tej jednosce kompilacji.
• "extern inline" oznacza, że "faktycznie _mam_ coś 'extern' dla tej funkcji, ale jeśli chcesz by była ona 'inline', to tu masz jej wersję 'inline'"

Jedyny problem z "static inline" był w _naprawdę_ starych wersjach gcc, które robiły źle, bo używały statycznych wersji funkcji w _każdej_ kompilowanej jednostce, niezależnie od tego czy było to potrzebne. Te wersje gcc i tak nie działają obecnie z jądrem, więc..

Uważam, że obecna semantyka gcc (a) daje większe możliwości niż stara (b) jest używana dostatecznie długo, więc zamiana nie będzie bolesna dla Linuksa. Krótko mówiąc, moglibyśmy nawet na tym skorzystać, a jeśli nie, to powinniśmy przerzucić wszystkich aktualnie używających "extern inline" na "static inline".