Filedeskriptoren verstehen



  • Hallo zusammen!

    Ich entwickle schon seit einige Wochen Konzepte, wie ich mein OS aufbauen will. Bisher habe ich auch schon ein kleines FS als hard-coded initrd implementiert, da ich viele Funktionen noch nicht implementiert habe. Weiß ich eigentlich wissen will, ist folgendes:

    Laut http://www.galileocomputing.de/katalog/buecher/titel/gp/titelID-1137 sind die Low-Level-Filedeskriptoren normale Integer, die für jeden Prozess in einer Tabelle gespeichert werden mit den dazugehörigen Dateien. Ich habe die FILE-Struktur vestanden und auch erfolgreich implementiert (wenn auch noch etwas redundant). Könnt ihr mir etwas zu den elementaren FDs erklären und wie man genau eine solche Tabelle effektiv implementieren kann?

    Gruß,
    Chris



  • ein file descriptor verbindet die struktur im kernel, die eine offene datei repräsentiert, mit dem user space programm. will ein programm etwas aus einer datei lesen oder in sie schreiben, gibt es im syscall die operation, die ausgeführt werden soll, zusätzliche parameter für diese operation und den file descriptor an. damit weiß der kernel, auf welche datei die operation ausgeführt werden soll. ein fd gehört immer genau zu einem prozess. die strukturen zu den offenen dateien sind im allgemeinen unabhängig von den prozessen.

    wie du das implementierst, bleibt dir überlassen. im allgemeinen haben prozesse relativ wenige dateien offen. bei server prozessen ist die anzahl der fds aber sehr hoch, da jede einzelne netzwerkverbindung durch einen fd dargestellt wird.

    es macht sinn, diese tabelle als array zu implementieren. du nimmst einfach den fd vom user space programm als index in das array. damit lässt sich auch leicht prüfen, ob der fd gültig ist. die element des arrays sind pointer zu den strukturen, die eine offene datei darstellen. wenn du mit einer größe von 16 oder 32 einträgen im array beginnst, wirst du wahrscheinlich 80% bis 90% aller programme abgedeckt haben. sollte ein programm ein tcp socket öffnen, kannst du präventiv das array vergrößern, da man erwarten kann, dass sehr viele fds gebraucht werden.



  • Wie soll ich die FD Struktur konzipieren? Momentan habe ich die echte _iobuf struct genommen und nutze diese ein bisschen. Irgendwelche Ideen, welche Bestandteile ich aufnehmen soll bzw. könnte?
    Ansonsten muss ich erstmal das Paging und malloc implementieren, da ich bisher alles nur statisch im Code verankert habe. Danach wird es mir sicher einfacher fallen dynamisch FDs zu generieren.



  • paging und malloc sind auf jeden fall vorher zu implementieren.

    ohne paging kannst du kaum echtes prozessmanagment durchführen. prozesse per segmentierung zu trennen ist sehr kompliziert. außerdem wärst du zu stark an das layout des physischen adressraums gebunden.

    ohne malloc wirst du keine dynamischen daten allokieren können. dh, du müsstest immer zur compilierzeit wissen, was du brauchen wirst. das ist zb schon im falle von strings für die pfad angabe von dateien unmöglich.



  • Ich würde mich jetzt mal in das Thema einklinken. Ich bin bei mir zwar noch nicht so weit, aber habe trotzdem schon ein "paar" Überlegungen dazu angestellt.

    Also ein Array (bzw. Vektor) zu nehmen finde ich eher unglücklich.

    Wie schon gesagt wurde, werden TCP Verbindungen (zumindest unter Unix Systemem) auch als Datei geöffnet. Die Vergrößerung und das rumkopieren des Vektors sehe ich noch nicht mal als Problem, aber das Suchen welche ID frei ist, könnte da zum Flaschenhals werden.

    Ich bin Momentan noch für nen Baum (AVL oder RedBlack), aber ne Hash-Tabelle ist bestimmt auch nicht verkehrt.



  • zum einen wollte ich ihn nicht gleich überfordern, zum anderen sehe ich nicht den vorteil in deinen datenstrukturen bei der suche nach einem freien fd. könntest du das bitte im detail erklären?



  • FlashBurn schrieb:

    Wie schon gesagt wurde, werden TCP Verbindungen (zumindest unter Unix Systemem) auch als Datei geöffnet. Die Vergrößerung und das rumkopieren des Vektors sehe ich noch nicht mal als Problem, aber das Suchen welche ID frei ist, könnte da zum Flaschenhals werden.

    Die Filedeskriptoren werden wiederverwendet und sind deswegen in der Regel alle am Stück, mit nur wenigen freien Einträgen. Ein Array ist da vermutlich nicht so blöd.

    Wenn man beim Öffnen einer Datei im Zweifelsfall mal 50 Einträge durchgehen muss, ist das auch nicht wirklich ein Beinbruch.

    Ich bin Momentan noch für nen Baum (AVL oder RedBlack), aber ne Hash-Tabelle ist bestimmt auch nicht verkehrt.

    Also eine Hashtabelle passt auf das Problem irgendwie mal überhaupt nicht... Wie findest du denn dort freie Einträge? Die ganze Tabelle durchgehen (mit vielen freien Einträgen)? Was ist daran besser als am Array?



  • Also eine Hashtabelle passt auf das Problem irgendwie mal überhaupt nicht... Wie findest du denn dort freie Einträge? Die ganze Tabelle durchgehen (mit vielen freien Einträgen)? Was ist daran besser als am Array?

    Die Mittagssonne 😉

    Erst denken dann schreiben! An die Suche nach einem freien Element habe ich in dem Fall gar nicht gedacht.

    Gilt natürlich auch für den Baum.

    Dann bleibt wirklich nur das Array.

    Wenn man beim Öffnen einer Datei im Zweifelsfall mal 50 Einträge durchgehen muss, ist das auch nicht wirklich ein Beinbruch.

    Naja, aber so wie ich mir das vorstelle, wird es nur beide Extreme geben. Entweder ne normale Anwendung wo nur wenige bis keine Dateien geöffnet werden oder ne Server-Anwendung wo dann extrem viele Dateien geöffnet werden, wo es dann wohl deutlich mehr als 50 Einträge werden die man durchgehen muss.

    Mir fällt da jetzt nicht mal ne tolle Datenstruktur ein, wie man es besser als mit nem Array lösen könnte. Ein Overkill (eventuell) wäre wenn man die freien IDs, die nicht das Array verkleinern, in einen Stack packt und neue IDs dann von dort abholt. Problem wäre dort nur das der Stack mit der Zeit natürlich ganz schön groß werden kann.

    Wenn ich mich recht entsinne, dann gab es bei einer neueren Version des Slab-Allocators irgendetwas schnell IDs zu allozieren. Wie die das gemacht haben, hatte ich aber nicht verstanden wo ich ein Dokument dazu gelesen hatte.

    Man kann das Problem eine freie ID zu finden sowieso verallgemeinern, da man das auch an anderen Stellen benötigt und dann wäre eine allgemeine Lösung doch nicht schlecht, als für jede Sache extra was zu programmieren.



  • Man könnte zum Suchen von freien File-Descriptoren eine Freelist nehmen. Zum Beispiel wäre ein Ansatz, die Ids in dem Array mit File-Decriptoren die freien Einträge zu negieren und die Indices untereinander per Linked-List miteinander zu verketten. Oder man legt sich eine weitere Linked-List an, die freie Einträge verwaltet. Vorteil der verwaltung auf dem Array -> Speichersparend ( keine Pointer auf weitere Einträge ).

    Gruß Kimmi



  • Die Idee mit dem negieren und die Einträge selbst zur Speicherung der Freelist zu nehmen find ich gut!

    Muss ich direkt mal schauen, ob ich nicht irgendwelche Fälle habe wo ich das schon nutzen könnte.



  • die idee von kimmi ist zwar nett und gut, hat aber grundsätzliche nachteile, sobald man posix konform sein will. posix verlangt, dass immer der kleinste verfügbare fd verwendet wird. außerdem gibt es da die funktion dup2, mit der man einen fd auf einen beliebigen anderen klonen kann. beide operationen sind mit einer unsortierten, single-linked freeliste nicht extrem viel performanter als das array, sofern man davon ausgeht, dass immer die gleiche menge an freien und besetzen fds vorhanden sind. ist die anzahl der freien fds klein, so kann die freeliste schon helfen. ich würde aber eher ein union verwenden:

    struct openfile;
    union fdentry {
      struct openfile* of;
      union fdentry* next;
    };
    

    ist der wert des pointers innerhalb des arrays, so ist der eintrag frei und zeigt auf den nächsten. im anderen fall zeigt der eintrag wo anders hin und auf eine openfile struktur.

    ein bitfield könnte möglicherweise die lösung des problems sein. die komplexität der suche ist zwar gleich, die implementierung kann aber beschleunigt werden. das setzen eines beliebigen fds ist O(1) und die suche nach dem kleinsten verfügbaren fd ist O(N), wobei hier eben stark optimiert werden kann (speicherzugriffe zb, aber auch die suche, wenn man zb 32 oder 64 bits gleichzeitig prüft.)

    die beste algorithmische lösung wäre eine priority queue. die meisten implementierungen sind aber relative komplex und wohl auch unnötig (bei kleinen tabellen sogar langsamer). in dem fall wäre ein baum statt der freeliste wirklich günstiger. aber eben nicht als datenstruktur für die fd tabelle sondern als index der freien fds.


Log in to reply