#lost · 2011-05-06

913 Nachrichten · Seite 3 von 5 · Original-CSV herunterladen

  1. DesLeine liste von listen von listen von.... -> Baum
  2. rizorgenau
  3. Svenskaalso mit wurzel, die auf dateieinträge zeigt. verzeichnisse sind einträge mit unterknoten
  4. Jidderkann auch ein ring sein
  5. Jidderoder schlimmer^^
  6. Svenskaund jeder dateieintrag zeigt auf die daten
  7. Svenskaich seh da keine kreisstruktur, die man mit nem ring abbilden könnte ;)
  8. rizornaja
  9. rizordie liste soll spaeter mal so aussehen:
  10. rizoreltern->kind->kind->kind->eltern
  11. DesL"sector pointer to VMGM_PGCI_UT(Menu Program Chain table): 0x2000000" man möchte kotzen :/
  12. rizorsomit ist es ein ring, wobei ich die suche nach kindern immer erst beim ersten kind beginne
  13. Svenskahm. warum keine einfache liste eltern->kind->kind->kind->NULL ?
  14. Jidderwarum nicht einen richtigen baum?
  15. Jidderwarum nicht einen b-tree oder so?
  16. rizorweil ich dafuer dann eigene datenstrukturen aufbauen muesste, habe aber mir eine generische liste geschrieben
  17. rizorwieso ein b-tree?
  18. rizormeinst du einen binaerbaum oder einen bayerbaum?
  19. Jidderweiß auch nicht. keine gute idee
  20. Jidderein baum ist keine verkettung von listen
  21. DesLein VFS auf Basis von std::vector<> - wieso fällt mir das jetzt erst ein? :D
  22. rizorwer bietet mir noch die runtime xD
  23. DesLJidder: wie meinen?
  24. rizorich habe aber noch eine andere frage
  25. JidderDesL: kommt drauf an
  26. rizorwie laesst sich das vfs am besten auf parallelitaet optimieren?
  27. DesLJidder: worauf?
  28. Jidderrizor: keine baumstruktur verwenden
  29. JidderDesL: ob die listen mehr als 2 elemente haben
  30. DesL?
  31. rizorjidder, du sprichst in raetseln ;)
  32. 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
  33. 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
  34. Svenskasowas lässt sich doch parallelisieren, oder?
  35. Jidderrizor: operationen auf bäumen sind kompliziert, wenn mehrere cpus da gleichzeitig drauf arbeiten
  36. Svenskadas ist kein baum im binärbaumsinne, sondern eine sammlung von listen
  37. rizordas ist genau mein problem, mit dem zugriff
  38. rizorwie muss ich was sichern, damit die daten konsistent bleiben
  39. DesLJidder: du gehst vom Binärbaum aus - ein VFS lässt sich damit nur schwer aufbauen
  40. Svenskaund solange du in jeder wurzel ein flag "wird jetzt benutzt" setzen kannst, ist der "teilbaum" geschützt
  41. rizorsvenska: so wollte ich es machen (halt mit meiner liste)
  42. JidderDesL: nein
  43. JidderDesL: nur das beispiel war eben ein binärbaum
  44. Jidderim allgemeinen ist ein baum keine liste von listen
  45. DesLweil.....
  46. erikGuten Abend
  47. Jidderzumindest meine bäume, bei denen mehrere operationen in O(log n) sind
  48. rizornabend
  49. Svenskaaber für sowas (das stell ich mir halt drunter vor) würde ich keine ringe nehmen, bringt nix
  50. Svenskanamd erik
  51. sfanmoin erik
  52. DesLnintel eril
  53. rizorsvenska: aber was ist mit mehrerem zugriff auf knoten, die unter diesem einen liegen
  54. rizorauf die sollte ich doch trotzdem noch zugreifen koennen, falls eine der (unter-)wurzeln nicht gerade geloescht oder veraendert wird
  55. Svenskarizor: die meisten operationen brauchen ja keinen vollzugriff auf alle teilbäume, d.h. was da unten passiert ist ja egal
  56. Svenskadu lockst also nur die ebene, die du gerade verändert - der rest bleibt ja konsistent
  57. rizorwieso?
  58. Svenskastrukturierst du den gesamten baum um, musst du natürlich alle betroffenen teilbäume locken
  59. Jidderaußer das verzeichnis /tmp
  60. Jidderda ist immer was los
  61. rizormv,cp und rm brauchen den gesamten zugriff
  62. Svenskawenn ich in \test\eins was ändere, dann ist \test\zwei davon nicht beeinflusst, muss also nicht gelockt werden
  63. rizoralso, falls die funktionen auf verzeichnissen arbeiten
  64. Svenskaebenso muss \test nicht gelockt werden, weil ich darin ja nix verändere (der verweis auf \test\eins bleibt erhalten)
  65. DesLes sei denn man entfernt /test/zwei aus /test/
  66. Svenskarichtig
  67. rizores sei denn, ich moechte test\drei erstellen, oder/
  68. Svenskarichtig, wenn ich \test\zwei lösche, muss ich \test locken, weil ich dort was ändere
  69. Svenskaaber davon ist \test\eins immernoch nicht beeinflusst
  70. Svenskad.h. ich kann gleichzeitig in \test\eins rumpfuschen wie ich will
  71. rizorstimmt
  72. rizordann habe ich da zumindest schon mal einen guten ueberblick, danke.
  73. Jidderwas nicht heißt, dass der problematische fall selten ist
  74. Svenskanein
  75. Svenskaman muss nur darauf aufpassen, den richtigen teilabschnitt zu locken
  76. 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
  77. 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
  78. Jidderwie passt man da auf?
  79. rizordie erstellen doch alle einfach temporaere dateien
  80. Svenskadie locks sind nur für verzeichnisstrukturen da
  81. rizordateien muessen aber auch gelockt werden, oder?
  82. Svenskawenn das dutzend gcc's also in /tmp/ dateien erzeugt, wird jedesmal /tmp/ gelockt
  83. DesLurgs, im File steht "00 00 00 0E" memcpy(int,file_data,4) fürht aber zu 0x0E000000 - endianess failure?
  84. Svenskaaber nur, um den _eintrag_ zu erzeugen, nicht den content
  85. Jidderdafür ist das vfs da^^
  86. rizorwieso das?
  87. JidderDesL: das ist little endian
  88. Svenskazumindest so wie ichs oben beschrieben hatte, zeigen die einträge im vfs dann auf den eigentlichen content
  89. rizorwenn ich den inhalt auf die platte schreiben moechte, muss das vfs doch verhinder, dass beide gleichzeitig den fs-treiber aufrufen, oder?
  90. Svenskanö
  91. Svenskawieso? ;-)
  92. rizorwer macht das dann?
  93. rizorder fs-treiber
  94. Svenskader fs-treiber selbst
  95. Jidderder fahrschultreiber?
  96. Svenskabzw. der plattentreiber
  97. Jidderne der nich
  98. Svenskavielleicht hab ich auch nur ne verkorkste weltsicht, keine ahnung :D
  99. erikauch der fs-treiber kann ruhig mehrere aufträge an den HDD-Controller parallel geben, gibt ja NCQ
  100. rizorder plattentreiber?
  101. Svenskaaber wenn du parallel auf dein vfs zugreifen willst, musst du das auch zulassen
  102. rizorder organisiert doch nur die anfallenden auftraege, oder?
  103. Svenskajeder pfad kann ja ein anderes dateisystem meinen
  104. rizormuss es aber nicht
  105. Svenskaund dem vfs ist erstmal total egal, ob und wie das backend geht
  106. rizorunter linux hast du ja auch nicht fuer jede datei ein fs-treiber fork
  107. Svenskader fs-treiber kann (zum lesen) auch problemlos parallel arbeiten, beim schreiben muss er entweder serialisieren oder aufpassen, dass das ergebnis stimmt
  108. Svenskaunter linux läuft das fs auch nicht im userspace ^^
  109. rizorbei mir soll es da auch nicht laufen ;)
  110. Svenskaparallel heißt nicht, dass du zwei prozesse hast. asynchrones i/o ist auch möglich
  111. Svenskaim endeffekt läuft das auf einen funktions- oder ipc-aufruf vom VFS zum FS hinaus
  112. rizoraber ist das nicht nur eine verschiebung der problematik?
  113. Svenskaklar ist es das ;)
  114. Svenskaaber du willst dein VFS nicht serialisieren, weil es dann ja nicht mehr parallel arbeiten kann
  115. rizorauf den ersten blick ist es doch egal, ob das fs oder das vfs sich darum kuemmern muss
  116. Svenskaauf den zweiten hat es im FS aber vorteile
  117. Svenskadrei VFS-zugriffe können parallel auf drei verschiedene FSse zugreifen
  118. rizorstimmt
  119. Svenskadu wirst bestimmt ramdisks haben (die sind voneinander unabhängig), du wirst bestimmt pseudo-dateisysteme haben
  120. rizordas problem habe ich nicht gesehen, dass alle ueber die wurzel serialisiert werden
  121. erikauch im FS sollte man nicht mehr seriallisieren als unbedingt nötigt, lieber mehrere Jobs parallel weiterreichen
  122. rizorso aehnlich wollte ich es auch machen
  123. Svenskaob der FS-call nun synchron funktioniert (und daher implizit serialisiert) oder in eine queue packe, die er später verwurstet, ist ja egal
  124. Svenskasolange das ergebnis stimmt. das VFS sollte darauf aber keine rücksicht nehmen müssen ^^
  125. rizorwobei die queue wahrscheinlich den durchsatz erhoeht
  126. Svenskahmm, was ich mir jetzt ausgedacht hab, notier ich mir erstmal ^^
  127. Svenskanaja, je nachdem was du mit der queue anstellst
  128. rizornaja, der fs-treiber soll dann einen eigenen scheduler besitzen
  129. rizoroder ich abstrahiere nochmal und lass erst einen io-scheduler darauf los, der dann den fs-treiber startet
  130. rizordas duerfte aber zu kompliziert sein
  131. Svenskahmm andersrum?
  132. Svenskader fs-treiber wirft dem i/o-treiber die daten vor und der sortiert
  133. rizorandersrum ist es am besten
  134. rizormuss halt jeder fs-treiber seinen scheduler mitbringen
  135. Svenskader fs-treiber weiß, wie er optimal mit seinem fs umzugehen hat
  136. Svenskaaber der eigentliche plattenzugriff (ncq und so) sollte vom plattentreiber optimiert werden
  137. rizorstimmt
  138. rizorstimmt
  139. rizordann nochmal eine andere frage
  140. rizorich wollte die identifikation der knoten ueber hashes organisieren
  141. rizorhabt ihr da einen guten algorithmus, der nicht zu viel rechnet und gleichzeitig eine geringe wahrscheinlichkeit auf gleiche hashes bei unterschiedlichem input bitet
  142. rizor*bietet
  143. Jidderüber was willst du denn hashen?
  144. erikda gibt es nichts gutes, nimm nen Patricia-Tree o.ä.
  145. rizorden pfad
  146. Jiddernimm irgendeinen
  147. rizornaja
  148. rizormd5 rechnet mir zu viel
  149. erikHashes sind extrem CPU-Intensiv
  150. Svenskawas bezweckst du damit?
  151. Jidderäh du willst damit nicht in eine hashtable indizieren?
  152. rizorja
  153. rizordann brauch ich keine string-vergleiche
  154. Jidderdann ist der pfad genauso gut wie ein hash
  155. rizorsondern kann ueber die hashes gehen
  156. Jidderdann for i = 1 to length do hash(i % 64) = hash(i % 64) + letter(i) end
  157. Jidderwobei die addition modulo 256 ist
  158. Jidderalso auf bytes
  159. erikda gibt es aber unmengen an Kollisionen
  160. Jidderer will sich string vergleiche sparen, nicht in eine hash table indizieren
  161. rizordas problem will ich gerade vermeiden
  162. rizorstimmt
  163. rizoralso es soll dann folgendes gemacht werden
  164. rizorwir haben folgende anfrage: /test/eins/datei.txt
  165. erikaber nur zum testen auf Gleichheit reichen die Hashes nicht aus
  166. rizorerster hash ist /test
  167. Jidderfür eine kollision müssen die pfade erstmal länger als 127 zeichen sein
  168. rizorzweiter ist /test/eins
  169. Jidderhm wobei ... 65 ^^
  170. rizoroder nur /eins
  171. rizorund halt immer so weiter
  172. Jidderoder 64 ^^
  173. rizor^^
  174. Svenskadu willst eine riesige hashtabelle über alle potentiellen dateinamen haben und darin rumindizieren?
  175. Jiddereben nicht
  176. rizornein
  177. rizorich moechte mir bei einer anfrage einfach die verschiedenen hashes berechnen
  178. rizorund die einzelnen knoten in meinem baum enthalten ebenfalls diese hashes
  179. rizorund dann muss ich den hash eines teilpfades nur mit den jeweiligen knoten vergleichen
  180. rizorund weisz, ob ich auf dem richtigen weg bin
  181. erikdas problem ist das Hashes nicht 100% zuverlässig sind, da können immer mal Kollisionen austreten
  182. rizorund da versuche ich gerade einen guten kompromiss aus zuverlaessigkeit und rechenaufwand finden
  183. erikdie Hashes ersparen Dir nicht die Notwendigkeit für einen String-Vergleich
  184. Jidderdas problem ist, dass ein normaler baum dafür besser wäre
  185. Jidderein trie = normaler baum
  186. Jidder^^
  187. rizorsoll ja auch einer werden ;)
  188. Jidderaber der hash taugt nicht als schlüssel
  189. rizorwieso ersparen sie mir das nicht?
  190. billyJidder: so wie krißtmaß trie?
  191. 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
  192. Jidderbilly: zurück in den keller
  193. rizordas ist klar
  194. Jiddererik häng dich doch nicht daran auf -.-
  195. rizoraber die hashes duerfen ja auch mehrfach vorkommen
  196. rizorsolange sie nicht auf der selben ebene eines teilbaums vorkommen
  197. JidderWTF
  198. erikdann must Du trotzdem Strings vergleichen
  199. Jidderrizor: hör auf hashes und bäume zu mischen
  200. rizorfalls sie entweder auf einer anderen ebene oder dem anderen teilbaum auftreten, tut mir das nicht weh