FAT particio - readdir és stat

Ez hosszú lesz. Bőven tartalmazhat tévedést is; majd valaki kijavít. A kijelentő módot ennek fényében tessék értelmezni.

UNIX-on a directory bejegyzés tartalmához lásd a struct dirent leírását. Ez hordozhatóan csak a nevet és az inode-számot tartalmazza (ill. konkrétan linux-on + glibc-n sem tartalmazza azt, amire vágysz). Az inode-számot összepárosítva annak a device-nak az azonosítójával, amely device-on maga a könyvtár is található, fellelhető az inode (ami egyenértékű a file-lal). Az inode tartalmazza azokat a tulajdonságokat, amelyekre vágysz. (Amit az előbb írtam a device-azonosítóról, amiatt van közvetlenül az is, hogy hardlink csak device-on belül lehet).

Windows-on (msdos, fat, vfat, mittomén) a könyvtárbejegyzés tartalmazza azokat az adatokat, amire vágysz. Ezekhez a linuxos driver nem nyújt hozzáférést. A kívánt tulajdonságokat a stat() függvénycsalád tagjaival kérdezed le.

vfat-on a könyvtár "fizikailag" is listába van szervezve, vagyis egy adott bejegyzés kikeresése O(n) lépést igényel. Amikor végigmész a readdir()-rel a könyvtáron, akkor (láncolt lista) maga a következőre lépés olcsó. A readdir() csak a file nevét adja vissza, a vfat-on történetesen a bejegyzésben tárolt egyéb adatokat nem. Ezért stat()-ot kell rá hívnod. A stat() azonban fütyül rá, hogy te tudnál neki device-ot ill. inode-ot mondani (a device-ot egyszer megnéznéd a könyvtárra, az inode a dirent része), csak nevet fogad el. A nevet pedig minden egyes alkalommal elkezdi a lista legelejéről keresni. Így a teljes könyvtár végig-stat-olása O(n) + O(n^2) = O(n^2). A FindNextFile-lal bejárás ebből csak az O(n) részt igényli (és minden adatot megad, amit meg akarsz kapni, mert vfat-specifikus).

Ext3-on ez azért nem fáj neked, mert ott a könyvtár nem listába van szervezve, hanem valamilyen hatékony asszociatív (névvel címezhető) adatszerkezetbe (hash, kiegyensúlyozott keresőfa, htree, mittomén; dir_index opció). (* ide egy megjegyzés még kívánkozik majd) Tehát ott is végignyalod readdir-rel az egész könyvtárat (ami O(n)), minden egyes file-ra teljes keresést végzel (ami darabonként mondjuk O(log(n)), így összesen O(n) + O(n*log(n)) = O(n*log(n)). Ha n helyébe 10.000-ret írsz, akkor n^2 = 10^8, míg n*log_2(n) ~ 13.288.

Ha van lehetőséged beleszólni a könyvtár kialakításába, akkor csináld azt, amit a squid cache: korlátozd a lista max hosszát akkorára, hogy 1 diszk blokkba beleférjen. (Vagy valami ilyesmi.) Most mondok hasból egy számot: ez a hossz legyen 10. Csinálsz továbbá 4-szeres mélységet, vagyis ilyen könyvtárszerkezeted lesz:
[0-9]/[0-9]/[0-9]/[0-9].dat

Ebben 10000 dat file fér el, és bármelyik lookup-jához legfeljebb 10 + 10 + 10 + 10 = 40 lépésre van szükséged, így ezen gyors lesz a stat() meg az open(). (Gyakorlatilag fába szervezted, ahol az aritást (a logaritmus alapját) te határoztad meg 10-ben.) Ha a file-nevek kötöttek, akkor valami jó hash-sel érdemes a névből előállítani a prefix részeit.

Másik megoldás, hogy keresel egy olyan kernel interface-t, amivel (device, inode) alapján tudsz file-t piszkálgatni. (Azt hiszem, ez elég ronda lesz, mert az inode-ok mint olyanok vfat-on nemigen léteznek, hanem eleve valami "trükkel" generálja a kernel <- szerk: bocsánat, ez akár baromság is lehet, csak itt olvastam egy érdekeset: http://www.delorie.com/djgpp/doc/libc/libc_549.html / Implementation Notes.)

Harmadik megoldás, hogy lecsatolod a vfat fs-t, a block device-ra (vagy regular file-ra, ha loop-on volt) adsz magadnak olvasási jogot, és írsz egy saját vfat drivert, ami tudja linux alatt is a FindNextFile-t. Ez nem biztos, hogy annyira rossz ötlet, mint amennyire hangzik, az mtools csomaggal esetleg pont ezt tudnád megvalósítani. (Mondjuk az mdir kimenetét elemzed, popen(), akármi.)

Az összes file megnyitása azonban mindenképpen lassú lesz.

* Megjegyzés az ext3-hoz: szomorúan tapasztaltam, hogy ext2 alatt a 2.4-es linux kernel nem támogatta a dir_index-et (nem volt hatása). ext3-nál igen, de ott is csak akkor, ha valóban volt igazi journal is a file-rendszerhez. Sajnos a journal önmagában rosszabb teljesítményt eredményezett (szerk: tömeges file-létrehozásnál), mint a dir_index nélküli ext2, így 2.4-en ext[23]-hoz szerintem nincs használható dir_index.

További megjegyzés, hogy ext2-n a (diszken lévő) directory entry-be még további adatok is belepakolhatók (ld. mke2fs, filetype), de a readdir()-rel ahhoz sem férsz hozzá.

Irónia: a readdir() testvérei, a telldir() és a seekdir() pont azon fs-ek fejlesztőit irritálja, akik a könyvtárakat random access-re (name lookup) hegyezik ki. Az nftw() ki tud futni az engedélyezett file descriptor-okból, ilyenkor fel kell jegyeznie, hol tart (telldir()), bezárja (closedir()), majd amikor ott kell továbblépnie, opendir() és seekdir(). A szóban forgó fejlesztőket annyira irritálja, hogy fel kell tudni jegyezniük ("szerializálniuk kell") a directory pozíciót, hogy inkább még az nftw()-től is megszabadulnának (mondván: van fts). Ha jól tévedek, ezt errefelé olvastam, de most nincs türelmem ellenőrizni, mindegy.

http://www.opengroup.org/austin/mailarchives/ag/msg01074.html