#lost · 2011-05-06
913 Nachrichten · Seite 3 von 5 · Original-CSV herunterladen
- DesLeine liste von listen von listen von.... -> Baum
- rizorgenau
- Svenskaalso mit wurzel, die auf dateieinträge zeigt. verzeichnisse sind einträge mit unterknoten
- Jidderkann auch ein ring sein
- Jidderoder schlimmer^^
- Svenskaund jeder dateieintrag zeigt auf die daten
- Svenskaich seh da keine kreisstruktur, die man mit nem ring abbilden könnte ;)
- rizornaja
- rizordie liste soll spaeter mal so aussehen:
- rizoreltern->kind->kind->kind->eltern
- DesL"sector pointer to VMGM_PGCI_UT(Menu Program Chain table): 0x2000000" man möchte kotzen :/
- rizorsomit ist es ein ring, wobei ich die suche nach kindern immer erst beim ersten kind beginne
- Svenskahm. warum keine einfache liste eltern->kind->kind->kind->NULL ?
- Jidderwarum nicht einen richtigen baum?
- Jidderwarum nicht einen b-tree oder so?
- rizorweil ich dafuer dann eigene datenstrukturen aufbauen muesste, habe aber mir eine generische liste geschrieben
- rizorwieso ein b-tree?
- rizormeinst du einen binaerbaum oder einen bayerbaum?
- Jidderweiß auch nicht. keine gute idee
- Jidderein baum ist keine verkettung von listen
- DesLein VFS auf Basis von std::vector<> - wieso fällt mir das jetzt erst ein? :D
- rizorwer bietet mir noch die runtime xD
- DesLJidder: wie meinen?
- rizorich habe aber noch eine andere frage
- JidderDesL: kommt drauf an
- rizorwie laesst sich das vfs am besten auf parallelitaet optimieren?
- DesLJidder: worauf?
- Jidderrizor: keine baumstruktur verwenden
- JidderDesL: ob die listen mehr als 2 elemente haben
- DesL?
- rizorjidder, du sprichst in raetseln ;)
- Jiddernaja bei zwei elementen und einer doppelt verketteten würde ich das nochmal gerade so als komplizierte form von linkes kind/rechtes kind durchgehen lassen, und es wäre damit etwas, dass gerade noch so in meine definition von baum passt
- Svenskahmm... wie wäre es mit wurzel->eins->zwei->drei->vier->NULL für das wurzelverzeichnis, die einträge zeigen entweder auf content (dateien) oder auf eine neue wurzel (verzeichnisse) mit gleichem aufbau
- Svenskasowas lässt sich doch parallelisieren, oder?
- Jidderrizor: operationen auf bäumen sind kompliziert, wenn mehrere cpus da gleichzeitig drauf arbeiten
- Svenskadas ist kein baum im binärbaumsinne, sondern eine sammlung von listen
- rizordas ist genau mein problem, mit dem zugriff
- rizorwie muss ich was sichern, damit die daten konsistent bleiben
- DesLJidder: du gehst vom Binärbaum aus - ein VFS lässt sich damit nur schwer aufbauen
- Svenskaund solange du in jeder wurzel ein flag "wird jetzt benutzt" setzen kannst, ist der "teilbaum" geschützt
- rizorsvenska: so wollte ich es machen (halt mit meiner liste)
- JidderDesL: nein
- JidderDesL: nur das beispiel war eben ein binärbaum
- Jidderim allgemeinen ist ein baum keine liste von listen
- DesLweil.....
- erikGuten Abend
- Jidderzumindest meine bäume, bei denen mehrere operationen in O(log n) sind
- rizornabend
- Svenskaaber für sowas (das stell ich mir halt drunter vor) würde ich keine ringe nehmen, bringt nix
- Svenskanamd erik
- sfanmoin erik
- DesLnintel eril
- rizorsvenska: aber was ist mit mehrerem zugriff auf knoten, die unter diesem einen liegen
- rizorauf die sollte ich doch trotzdem noch zugreifen koennen, falls eine der (unter-)wurzeln nicht gerade geloescht oder veraendert wird
- Svenskarizor: die meisten operationen brauchen ja keinen vollzugriff auf alle teilbäume, d.h. was da unten passiert ist ja egal
- Svenskadu lockst also nur die ebene, die du gerade verändert - der rest bleibt ja konsistent
- rizorwieso?
- Svenskastrukturierst du den gesamten baum um, musst du natürlich alle betroffenen teilbäume locken
- Jidderaußer das verzeichnis /tmp
- Jidderda ist immer was los
- rizormv,cp und rm brauchen den gesamten zugriff
- Svenskawenn ich in \test\eins was ändere, dann ist \test\zwei davon nicht beeinflusst, muss also nicht gelockt werden
- rizoralso, falls die funktionen auf verzeichnissen arbeiten
- Svenskaebenso muss \test nicht gelockt werden, weil ich darin ja nix verändere (der verweis auf \test\eins bleibt erhalten)
- DesLes sei denn man entfernt /test/zwei aus /test/
- Svenskarichtig
- rizores sei denn, ich moechte test\drei erstellen, oder/
- Svenskarichtig, wenn ich \test\zwei lösche, muss ich \test locken, weil ich dort was ändere
- Svenskaaber davon ist \test\eins immernoch nicht beeinflusst
- Svenskad.h. ich kann gleichzeitig in \test\eins rumpfuschen wie ich will
- rizorstimmt
- rizordann habe ich da zumindest schon mal einen guten ueberblick, danke.
- Jidderwas nicht heißt, dass der problematische fall selten ist
- Svenskanein
- Svenskaman muss nur darauf aufpassen, den richtigen teilabschnitt zu locken
- Svenskaaber wenn du locks nach unten gehen lässt, müsstest du für jede aktion den gesamten abschnitt von root bis unten durchsuchen, um ein lock zu finden
- Jidderwie geht das? wenn ich make -j ausführe ist ein dutzend gccs fleißig dabei in tmp dateien zu erstellen und zu löschen
- Jidderwie passt man da auf?
- rizordie erstellen doch alle einfach temporaere dateien
- Svenskadie locks sind nur für verzeichnisstrukturen da
- rizordateien muessen aber auch gelockt werden, oder?
- Svenskawenn das dutzend gcc's also in /tmp/ dateien erzeugt, wird jedesmal /tmp/ gelockt
- DesLurgs, im File steht "00 00 00 0E" memcpy(int,file_data,4) fürht aber zu 0x0E000000 - endianess failure?
- Svenskaaber nur, um den _eintrag_ zu erzeugen, nicht den content
- Jidderdafür ist das vfs da^^
- rizorwieso das?
- JidderDesL: das ist little endian
- Svenskazumindest so wie ichs oben beschrieben hatte, zeigen die einträge im vfs dann auf den eigentlichen content
- rizorwenn ich den inhalt auf die platte schreiben moechte, muss das vfs doch verhinder, dass beide gleichzeitig den fs-treiber aufrufen, oder?
- Svenskanö
- Svenskawieso? ;-)
- rizorwer macht das dann?
- rizorder fs-treiber
- Svenskader fs-treiber selbst
- Jidderder fahrschultreiber?
- Svenskabzw. der plattentreiber
- Jidderne der nich
- Svenskavielleicht hab ich auch nur ne verkorkste weltsicht, keine ahnung :D
- erikauch der fs-treiber kann ruhig mehrere aufträge an den HDD-Controller parallel geben, gibt ja NCQ
- rizorder plattentreiber?
- Svenskaaber wenn du parallel auf dein vfs zugreifen willst, musst du das auch zulassen
- rizorder organisiert doch nur die anfallenden auftraege, oder?
- Svenskajeder pfad kann ja ein anderes dateisystem meinen
- rizormuss es aber nicht
- Svenskaund dem vfs ist erstmal total egal, ob und wie das backend geht
- rizorunter linux hast du ja auch nicht fuer jede datei ein fs-treiber fork
- Svenskader fs-treiber kann (zum lesen) auch problemlos parallel arbeiten, beim schreiben muss er entweder serialisieren oder aufpassen, dass das ergebnis stimmt
- Svenskaunter linux läuft das fs auch nicht im userspace ^^
- rizorbei mir soll es da auch nicht laufen ;)
- Svenskaparallel heißt nicht, dass du zwei prozesse hast. asynchrones i/o ist auch möglich
- Svenskaim endeffekt läuft das auf einen funktions- oder ipc-aufruf vom VFS zum FS hinaus
- rizoraber ist das nicht nur eine verschiebung der problematik?
- Svenskaklar ist es das ;)
- Svenskaaber du willst dein VFS nicht serialisieren, weil es dann ja nicht mehr parallel arbeiten kann
- rizorauf den ersten blick ist es doch egal, ob das fs oder das vfs sich darum kuemmern muss
- Svenskaauf den zweiten hat es im FS aber vorteile
- Svenskadrei VFS-zugriffe können parallel auf drei verschiedene FSse zugreifen
- rizorstimmt
- Svenskadu wirst bestimmt ramdisks haben (die sind voneinander unabhängig), du wirst bestimmt pseudo-dateisysteme haben
- rizordas problem habe ich nicht gesehen, dass alle ueber die wurzel serialisiert werden
- erikauch im FS sollte man nicht mehr seriallisieren als unbedingt nötigt, lieber mehrere Jobs parallel weiterreichen
- rizorso aehnlich wollte ich es auch machen
- Svenskaob der FS-call nun synchron funktioniert (und daher implizit serialisiert) oder in eine queue packe, die er später verwurstet, ist ja egal
- Svenskasolange das ergebnis stimmt. das VFS sollte darauf aber keine rücksicht nehmen müssen ^^
- rizorwobei die queue wahrscheinlich den durchsatz erhoeht
- Svenskahmm, was ich mir jetzt ausgedacht hab, notier ich mir erstmal ^^
- Svenskanaja, je nachdem was du mit der queue anstellst
- rizornaja, der fs-treiber soll dann einen eigenen scheduler besitzen
- rizoroder ich abstrahiere nochmal und lass erst einen io-scheduler darauf los, der dann den fs-treiber startet
- rizordas duerfte aber zu kompliziert sein
- Svenskahmm andersrum?
- Svenskader fs-treiber wirft dem i/o-treiber die daten vor und der sortiert
- rizorandersrum ist es am besten
- rizormuss halt jeder fs-treiber seinen scheduler mitbringen
- Svenskader fs-treiber weiß, wie er optimal mit seinem fs umzugehen hat
- Svenskaaber der eigentliche plattenzugriff (ncq und so) sollte vom plattentreiber optimiert werden
- rizorstimmt
- rizorstimmt
- rizordann nochmal eine andere frage
- rizorich wollte die identifikation der knoten ueber hashes organisieren
- rizorhabt ihr da einen guten algorithmus, der nicht zu viel rechnet und gleichzeitig eine geringe wahrscheinlichkeit auf gleiche hashes bei unterschiedlichem input bitet
- rizor*bietet
- Jidderüber was willst du denn hashen?
- erikda gibt es nichts gutes, nimm nen Patricia-Tree o.ä.
- rizorden pfad
- Jiddernimm irgendeinen
- rizornaja
- rizormd5 rechnet mir zu viel
- erikHashes sind extrem CPU-Intensiv
- Svenskawas bezweckst du damit?
- Jidderäh du willst damit nicht in eine hashtable indizieren?
- rizorja
- rizordann brauch ich keine string-vergleiche
- Jidderdann ist der pfad genauso gut wie ein hash
- rizorsondern kann ueber die hashes gehen
- Jidderdann for i = 1 to length do hash(i % 64) = hash(i % 64) + letter(i) end
- Jidderwobei die addition modulo 256 ist
- Jidderalso auf bytes
- erikda gibt es aber unmengen an Kollisionen
- Jidderer will sich string vergleiche sparen, nicht in eine hash table indizieren
- rizordas problem will ich gerade vermeiden
- rizorstimmt
- rizoralso es soll dann folgendes gemacht werden
- rizorwir haben folgende anfrage: /test/eins/datei.txt
- erikaber nur zum testen auf Gleichheit reichen die Hashes nicht aus
- rizorerster hash ist /test
- Jidderfür eine kollision müssen die pfade erstmal länger als 127 zeichen sein
- rizorzweiter ist /test/eins
- Jidderhm wobei ... 65 ^^
- rizoroder nur /eins
- rizorund halt immer so weiter
- Jidderoder 64 ^^
- rizor^^
- Svenskadu willst eine riesige hashtabelle über alle potentiellen dateinamen haben und darin rumindizieren?
- Jiddereben nicht
- rizornein
- rizorich moechte mir bei einer anfrage einfach die verschiedenen hashes berechnen
- rizorund die einzelnen knoten in meinem baum enthalten ebenfalls diese hashes
- rizorund dann muss ich den hash eines teilpfades nur mit den jeweiligen knoten vergleichen
- rizorund weisz, ob ich auf dem richtigen weg bin
- erikdas problem ist das Hashes nicht 100% zuverlässig sind, da können immer mal Kollisionen austreten
- rizorund da versuche ich gerade einen guten kompromiss aus zuverlaessigkeit und rechenaufwand finden
- erikdie Hashes ersparen Dir nicht die Notwendigkeit für einen String-Vergleich
- Jidderdas problem ist, dass ein normaler baum dafür besser wäre
- Jidderein trie = normaler baum
- Jidder^^
- rizorsoll ja auch einer werden ;)
- Jidderaber der hash taugt nicht als schlüssel
- rizorwieso ersparen sie mir das nicht?
- billyJidder: so wie krißtmaß trie?
- erikim VFS würde ich als User 100% Zuverlässigkeit erwarten, ich möchte nicht das meine Datei in einem falschen verzeichnis landet nur weil das zufälligerweise den selben Hash hat
- Jidderbilly: zurück in den keller
- rizordas ist klar
- Jiddererik häng dich doch nicht daran auf -.-
- rizoraber die hashes duerfen ja auch mehrfach vorkommen
- rizorsolange sie nicht auf der selben ebene eines teilbaums vorkommen
- JidderWTF
- erikdann must Du trotzdem Strings vergleichen
- Jidderrizor: hör auf hashes und bäume zu mischen
- rizorfalls sie entweder auf einer anderen ebene oder dem anderen teilbaum auftreten, tut mir das nicht weh