Thema: Allgemeiner Ressourcen-Allocator

[erik.vikinger]

Hallo,

Denn was hier gemacht wird ist Symptom Bekämpfung und nicht die Ursachen beseitigen!

Die Ursache ist das der Mensch (als Programmierer) nicht perfekt ist! Daran kann man prinzipiell nichts ändern oder willst Du die Programmierer abschaffen und SW-Design nur noch den Computern selber überlassen?

Warum sollte sich denn ein Programmierer um solche Sachen wie nen Bufferoverflow kümmern, wenn das OS es doch macht und es so auch noch performanter ist? Ich will nicht die Bequemlichkeit der Programmierer unterstützen.

Menschen machen nun mal Fehler und wenn Du trotz dessen eine hohe Sicherheit erreichen willst dann funktioniert das nur wenn Du auf jeder Ebene versuchst ein Maximum an Sicherheit zu erreichen. Es bringt nichts einfach alles auf die letzte Ebene zu schieben und zu sagen "der hätte eben besser programmieren müssen"!

Wenn wir beide mit unseren OSen fertig sind können wir ja gegenseitig versuchen unsere Systeme zu knacken, mal sehen wer damit reichhaltigeren Erfolg hat.

Aber welchen Teil des virtuellen Speichers der Heap belegt, das wird halt nicht (unbedingt) im UserSpace gemacht!

Nein, normalerweise nicht, aber laut POSIX legt das OS einen Bereich im virtuellen Adressraum fest und der User-Code (die Heap-Verwaltung) kann diesen Bereich vergrößern und verkleinern (der Bereich bleibt also in einem Stück).

Das sollte eigentlich klar sein. Ich meine sowas wie ne libc von GNU und ne libc von LLVM und ne dietlibc usw. Alle können andere Algos implementieren, aber laufen auf deinem OS.

Keine derzeit existierende libc wird auf meinem OS laufen, dafür gehe ich einfach an zu vielen Stellen zu sehr andere Wege.

Anders gefragt, was für eine Datenstruktur willst du denn einsetzen, dass es nicht signifikant langsamer wird (schreib aber bitte ob das nur mit deinen Segmenten funktioniert)?

Ich werde meine Segmente als Array benutzen da ich die einfach vergrößern und verkleinern kann (um das defragmentieren im linearen Speicher kümmert sich das OS) und für jede Objekt-Größe ein eigenes Segment. Aber das funktioniert natürlich nur mit unabhängigen dynamischen Segmenten, sorry.

machst du jetzt aber die Annahme das auch Blöcke mit den Größen der 2er Potenzen reichen, kannst du schon viel schneller und einfacher sortien, nämlich in O(1).

Also ich will das schon etwas feiner unterteilen, muss aber auch dafür nicht suchen sondern nur rechnen (ein bisschen Bitschieberei usw.), bleibt also bei O(1).

Programmierer sind faul und bequem (andere Interpretation: unter enormem Zeitdruck, enormem Featuredruck und nur wenig Qualitätssicherung).

Exakt so ist es. Ich musste auch schon Abstriche machen nur um Terminvorgaben halten zu können. Ich möchte nicht wissen was bei MS die Abteilung die den Kernel entwickelt sagt wenn das Management den Auslieferungstermin des nächsten Windows festgelegt hat oder andersrum was die Manager sagen wenn das Kernel-Entwicklerteam kurz vor der Auslieferung doch noch einen Bug gefunden hat oder einen zusätzlichen Feature-Request erhält bzw. wegen Zeitmangel ablehnt.

Wozu Passwörter übers Netz mit MD5 hashen und auch noch verschlüsselt auf der Festplatte abspeichern?

Wozu überhaupt Passwörter, ich hab doch ne Wohnungstür? Oder andersrum: Warum ne Wohnungstür, ich doch nen Passwort?
Das Passwort und die Wohnungstür sind eben nur 2 verschiedene Ebenen an Sicherheit. Kein normaler Mensch würde auf die Idee kommen auch nur eine dieser beiden Ebenen zu vernachlässigen. Sicherheit entsteht auch immer zu einem guten Anteil durch Redundanz!

Ein malloc(1) dauert exakt genausolange wie ein malloc(1024*1024*1024) und ist unabhängig vom derzeitigen Zustand des physischen Speichers?

Was das malloc() betrifft ist dem so. Ich kann bei so einer Betrachtung nicht noch das OS mit einbeziehen. Denn es kann ja sein das ich gar nicht weiß wie das OS es macht oder auf welchen OS mein Code läuft. Trotzdem kann malloc() O(1) sein.

Unzulässige Vereinfachung: Dein malloc() fragt beim VMM nach und es hängt von dem - also genau dem OS - ab, ob du nun konstante Laufzeit hast oder nicht. Du kannst gern sagen, dass ein Teil deiner malloc()-Implementation (und zwar genau der systemunabhängige Teil) von der Komplexität O(1) ist, aber für das gesamte malloc() von Aufruf bis Return kannst du nicht sprechen.

Also bei meiner Heap-Verwaltung würde ich schon sagen das, unter gewissen Einschränkungen wie Objekt-Größe im Rahmen 1Byte bis 1MByte und es muss nicht das OS gebeten werden mehr Speicher zur Verfügung zu stellen, mein malloc und free mit O(1) arbeiten. Aber wenn ich das Gesamtsystem betrachte (und das muss man einfach tun) dann dürfte es wohl absolut unmöglich sein eine Heap-Verwaltung mit O(1) zu bauen.

Ich will irgendwie nicht wissen, wie groß das Array sein muss, damit Quicksort 1 MB an Rekursions-Stack braucht...

Auf jeden Fall ziemlich Groß, aber es hängt auch davon ab wie groß der Stackframe pro Funktionsaufruf ist und da kann der Compiler sicher auch etwas zu beitragen.

In meiner Welt, und offensichtlich auch in eriks, sind malloc() und VMM aber sehr eng miteinander verzahnt, sodaß eine getrennte Betrachtung nur wenig bringt.

Exakt.

Für mich sollte ein naher malloc-Verwandter bereits eine Funktion des VMM sein, die man in der libc nur noch weitergeben muss. Damit können Kernelthreads (mal abgesehen vom VMM) es auch benutzen, ohne auf eine libc-Implementation, welche eventuell Kernelthreads erfordert, angewiesen zu sein. Sonst hast du nämlich wieder eine zyklische Abhängigkeit...

Das würde aber bedeuten das malloc fast immer einen Syscall machen muss und das würde ich persönlich nicht wollen, trotzdem ist Dein Gedanke durchaus nachvollziehbar richtig.

Das kann ich allerdings im Voraus ändern, indem ich die Pages vorher benutze und davon ausgehe, dass genug RAM da ist.

Wobei Deine letzten 8 Worte auch wieder eine Annahme sind die nicht zwangsläufig zutreffen muss.


Grüße
Erik

[Svenska]

Hallo,

Für mich sollte ein naher malloc-Verwandter bereits eine Funktion des VMM sein, die man in der libc nur noch weitergeben muss. Damit können Kernelthreads (mal abgesehen vom VMM) es auch benutzen, ohne auf eine libc-Implementation, welche eventuell Kernelthreads erfordert, angewiesen zu sein. Sonst hast du nämlich wieder eine zyklische Abhängigkeit...

Das würde aber bedeuten das malloc fast immer einen Syscall machen muss und das würde ich persönlich nicht wollen, trotzdem ist Dein Gedanke durchaus nachvollziehbar richtig.

Die libc würde in der naiven Implementation immer den malloc-Syscall machen, richtig. Wenn ich jetzt allerdings bereits weiß, wie groß der Standard-Stack ist (in der libc sollte das bekannt sein, denn sie ist OS-abhängig), kann ich Kleinkram auch auf dem Stack alloziieren und diesen Fall direkt in der libc lösen. Worauf ich hinaus möchte, ist, dass ein kmalloc() aber im Kernel/VMM implementiert sein sollte (eben damit der Kernel eine full-featured-malloc-Umgebung nutzen kann) und wenn ich diese bereits im Kernel implementiert habe, kann ich sie in der libc auch einfach naiv weitergeben. Das vermeidet eine zyklische Abhängigkeit und lässt FlashBurns Wünsche nach einer austauschbaren libc-Implementation offen...

Das kann ich allerdings im Voraus ändern, indem ich die Pages vorher benutze und davon ausgehe, dass genug RAM da ist.

Wobei Deine letzten 8 Worte auch wieder eine Annahme sind die nicht zwangsläufig zutreffen muss.

Der Ausgangspunkt hatte aber eher was mit Benchmarks zu tun als mit realem Workload. Aber ich denke, eine nicht immer, aber häufig zutreffende Grundannahme kann man schon machen: Dass die Workload im Regelfall den Fähigkeiten des Systems angepasst ist (oder diese untersteigt). Schließlich werde ich auf einem Pentium 133 mit 32 MB RAM keinen Windows Server 2008 als Active Directory Server für 20000 Nutzer einsetzen...

Gruß,
Svenska

[FlashBurn]

Im Übrigen kostet ein Thread ebenfalls ein bisschen was an Speicher für Verwaltungsstrukturen und eine Sortierroutine mit stückweisem Sortieren und Multithreading macht den Code größer.

Du hast ja schon mehrmals gesagt das du es nicht so mit Threads hast, aber das was du da gesagt hast, heißt du würdest lieber einen Thread QuickSort durchführen lassen, als mehrere Threads QuickSort durchführen zu lassen?!
Sorry aber mit der Einstellung sollte man keine Programme mehr entwickeln.

Ich will irgendwie nicht wissen, wie groß das Array sein muss, damit Quicksort 1 MB an Rekursions-Stack braucht...

Warum diskutieren wir dann

Du kannst mir nicht erzählen, dass dein beliebiges malloc() in einer libc auf jedem x-beliebigen Betriebssystem läuft - auch mit Einschränkung auf FlatMemory nicht.

So lange es mit Speicher arbeitet den es vom OS bekommt (und nicht mit Speicher den es gerne vom OS haben möchte, ich meine also nen zusammenhängenden Heap) sollte das auf jedes OS portierbar sein.

Eine identische Implementation würde ja sonst unverändert (und das ist der Punkt!) unter Windows NT, Windows 3.1 (erw.Mod.), DOS (mit Extender), Linux, Minix-386 und deinem OS laufen. Das geht nicht, weil die darunterliegende API eben nicht identisch ist.

Das ist auch nicht das was ich meine, sondern das jedes OS ne Möglichkeit bietet Speicher vom OS anzufordern und das sollte wirklich jedes OS bieten und dann sollte eigentlich jeder malloc() Algo portierbar sein.

In meiner Welt, und offensichtlich auch in eriks, sind malloc() und VMM aber sehr eng miteinander verzahnt, sodaß eine getrennte Betrachtung nur wenig bringt.

Gerade zwecks Portierbarkeit oder der Tatsache das sich am VMM mal was ändern kann, würde ich malloc() schon für sich alleine betrachten.

Für mich sollte ein naher malloc-Verwandter bereits eine Funktion des VMM sein, die man in der libc nur noch weitergeben muss.

Sehe ich 2 Probleme, wo speicherst du die Verwaltungsdaten und damit legst du den malloc() Algo ja fest und das ist "scheiße"
Wenn du dann noch Syscalls anbietest das man auch ne eigene malloc() Implementation nutzen kann, kannst du dir deins auch wieder sparen, weil warum doppelt?
Zumal ich komme im Kernel komplett ohne malloc() aus, ich nutze nur den SlabAllocator (und ja ist für mich was anderes).

Damit können Kernelthreads (mal abgesehen vom VMM) es auch benutzen, ohne auf eine libc-Implementation, welche eventuell Kernelthreads erfordert, angewiesen zu sein. Sonst hast du nämlich wieder eine zyklische Abhängigkeit...

An welche zyklische Abhängigkeit denkst du da, mir fällt jetzt keine ein?

Die Ursache ist das der Mensch (als Programmierer) nicht perfekt ist! Daran kann man prinzipiell nichts ändern oder willst Du die Programmierer abschaffen und SW-Design nur noch den Computern selber überlassen?

Wenn der PC irgendwann mal intelligent genug dafür ist, warum nicht

Wenn wir beide mit unseren OSen fertig sind können wir ja gegenseitig versuchen unsere Systeme zu knacken, mal sehen wer damit reichhaltigeren Erfolg hat. Wink

Sehr gerne, ich hoffe nur das wir dann noch in der Lage dazu sind

Nein, normalerweise nicht, aber laut POSIX legt das OS einen Bereich im virtuellen Adressraum fest und der User-Code (die Heap-Verwaltung) kann diesen Bereich vergrößern und verkleinern (der Bereich bleibt also in einem Stück).

Ich weiß nicht ob Linux sowas wie ALR hat, aber wenn ja, dann gilt das eigentlich auch nicht mehr.

Ich möchte nicht wissen was bei MS die Abteilung die den Kernel entwickelt sagt wenn das Management den Auslieferungstermin des nächsten Windows festgelegt hat oder andersrum was die Manager sagen wenn das Kernel-Entwicklerteam kurz vor der Auslieferung doch noch einen Bug gefunden hat oder einen zusätzlichen Feature-Request erhält bzw. wegen Zeitmangel ablehnt.

Als vernünftiger Mensch würde man sagen, wenn da ein Bug im Kernel ist und wir das OS ausliefern obwohl wir das wussten, dann machen wir uns keine Freunde, aber verschieben wir das lieber (kommt aber auch auf den Bug drauf an).
Das die meisten Manager wahrscheinlich nicht so denken ist mir klar, aber man sollte auch mal weiter denken und nicht immer nur bis zur nächsten Version.

Wenn ich jetzt allerdings bereits weiß, wie groß der Standard-Stack ist (in der libc sollte das bekannt sein, denn sie ist OS-abhängig), kann ich Kleinkram auch auf dem Stack alloziieren und diesen Fall direkt in der libc lösen.

Das würde mich mal interessieren, wie du das lösen möchtest. Denn dieser Bereich könnte ja irgendwann mal überschrieben werden.

[Svenska]

Hallo,

ein Thread, der Quicksort macht ist in jedem Fall wesentlich einfacher zu implementieren als eine Menge von Threads, die Quicksort machen. Wohlgemerkt: Auf einer Datenbasis!! Das erfordert sicherlich einiges an Locking/Synchronisation, außerdem ist für mich die Rekursion hinreichend schwierig zu begreifen, als dass ich das noch zusätzlich durch parallel arbeitende Prozesse fehleranfällig (weil schwer zu verstehen) machen muss. Zumal du äußerst selten einen solchen Algorithmus brauchen solltest, insbesondere nicht für interne OS-Strukturen. Da hast du normalerweise nur selten mehr als 10k Elemente.

Wenn du mir, nur weil ich es gerne in erster Instanz einfach, simpel und dumm baue, unterstellst, ich solle das Programmieren sein lassen, dann solltest du im Gegenzug mal deine Konzepte überdenken... denn dann ist irgendetwas grob falsch. Erweitern lassen sich bestimmte Dinge immer.

Über malloc() denken wir verschieden, also lassen wir die Diskussion lieber sein. Mach, wie du es für richtig hältst. Die zyklische Abhängigkeit kommt, wenn du malloc in der libc implementierst, im Kernel aber gerne ein malloc/kmalloc benutzen möchtest. Da du das nicht tust, sondern deinen Slab-Allocator benutzt, ist das für dich nicht relevant.

Wenn der PC irgendwann mal intelligent genug dafür ist, warum nicht

Denk mal nach, wer intelligent ist... der PC oder derjenige, der ihn entwickelte? Ich hoffe, dass die Singularität noch ein Weilchen weg ist. Bevorzugt bis nach meinem Tod.

Variablen, die du nur in einer Funktion benutzt, kannst du auf den Stack legen. Rufst du eine Funktion auf, wird der Rücksprungpointer dahinter gelegt, ist also egal (die Zeiger bleiben gültig), bei einem Rücksprung würdest du an die falsche Adresse (nämlich den Inhalt der Variablen) springen. Um das zu vermeiden, nutzt man Magic Cookies, die Variablen von Rücksprungadressen trennen und ein Stack-Unwinding, was vom Compiler erledigt wird.

Wenn man die Cookies zufällig erzeugt (sowohl Wert als auch Byteanzahl!), verringert sich die Angriffsfläche enorm. Inkorrektes Stack-Unwinding führt dann zu einer Exception und dem Abbruch des Programms weil das Cookie nich stimmt. Im Gegenzug für diese Komplexität brauchst du für Kleinkram keinen VMM, keinen Slab-Allocator und weil der Stack ohnehin ständig benutzt wird, ist er auch im CPU-Cache für den jeweiligen Thread vorhanden. Das bringt Performance. Speicherkosten: Codegröße, Magic Cookies.

Gruß,
ein offensichtlich inkompetenter Svenska

[FlashBurn]

ein Thread, der Quicksort macht ist in jedem Fall wesentlich einfacher zu implementieren als eine Menge von Threads, die Quicksort machen.

Kann sein das ich es mir zu einfach mache, aber wenn ich nen QuadCore habe und nen Array was ausreichend groß genug ist, dann teile ich das Array einfach in 4 halbwegs gleichgroße Stücke und jage QuickSort über jedes Stück (natürlich wird jeder Teil von einem anderen Thread sortiert). Wenn man dann jetzt die 4 sortierten Teilstücke durch ein QuickSort endgültig sortiert sollte das ja sehr schnell gehen. Zumal ich in Erinnerung habe, das gerade QuickSort sehr einfach zu parallelisieren ist.

Zumal du äußerst selten einen solchen Algorithmus brauchen solltest, insbesondere nicht für interne OS-Strukturen. Da hast du normalerweise nur selten mehr als 10k Elemente.

Wer redet hier von internen OS-Strukturen, es ging im den UserSpace und das der Stack eventuell zu klein ist um z.B. ein QuickSort auf einer größeren Datenmenge durchzuführen.

Interne OS-Strukturen würde ich in dem Sinne nie sortien, sondern immer sortiert einfügen.

Wenn du mir, nur weil ich es gerne in erster Instanz einfach, simpel und dumm baue, unterstellst, ich solle das Programmieren sein lassen, dann solltest du im Gegenzug mal deine Konzepte überdenken... denn dann ist irgendetwas grob falsch.

Sorry, aber du hast ja selbst gesagt, dass du es mit Threading nicht so hast, weil dir das zu kompliziert ist und du zeigst in deinen Antworten oft das du lieber alte Wege gehst als neue auszuprobieren.
Ich sage nicht das du dumm bist, aber was Software betrifft die irgendwo produktiv im Einsatz ist sollte die nicht so programmiert sein, das sie "alt" ist.
Denn das ist wieder genau das was ich schonmal gesagt habe, wir haben immer schnellere CPUs, immer mehr CPUs in einem System, immer mehr RAM, aber die Programme werden immer langsamer!

Die zyklische Abhängigkeit kommt, wenn du malloc in der libc implementierst, im Kernel aber gerne ein malloc/kmalloc benutzen möchtest. Da du das nicht tust, sondern deinen Slab-Allocator benutzt, ist das für dich nicht relevant.

Ich habe das mit der zyklischen Abhängigkeit immernoch nicht verstanden. Denn darunter verstehe ich das die untereinander abhängig sind, aber das sehe ich halt nicht bzw. nicht das Problem.
Ja ich nutze nur meinen SlabAllocator, aber was außer des Algos für die Verwaltung des Speichers unterscheidet den denn von einem normalen malloc()?

Variablen, die du nur in einer Funktion benutzt, kannst du auf den Stack legen. Rufst du eine Funktion auf, wird der Rücksprungpointer dahinter gelegt, ist also egal (die Zeiger bleiben gültig), bei einem Rücksprung würdest du an die falsche Adresse (nämlich den Inhalt der Variablen) springen. Um das zu vermeiden, nutzt man Magic Cookies, die Variablen von Rücksprungadressen trennen und ein Stack-Unwinding, was vom Compiler erledigt wird.

Was du beschreibst braucht also Support vom Compiler und ist ohne diesen nicht möglich. Was passiert wenn ein solches Programm eine Library benutzt die sowas nicht unterstützt?

Wenn man die Cookies zufällig erzeugt (sowohl Wert als auch Byteanzahl!), verringert sich die Angriffsfläche enorm. Inkorrektes Stack-Unwinding führt dann zu einer Exception und dem Abbruch des Programms weil das Cookie nich stimmt. Im Gegenzug für diese Komplexität brauchst du für Kleinkram keinen VMM, keinen Slab-Allocator und weil der Stack ohnehin ständig benutzt wird, ist er auch im CPU-Cache für den jeweiligen Thread vorhanden. Das bringt Performance. Speicherkosten: Codegröße, Magic Cookies.

Also Stack-Unwinding halte ich schonmal für Performance schädlich und den VMM brauchst du trotzdem, denn wer soll denn den Stack verwalten (Multi-Threading)?

Edit::

Ich habe mir mal bei Wikipedia den Artikel zu QuickSort angeguckt und da wird auch meine Idee genannt um zu verhindern das der Stack überläuft und einen "künstlichen" Stack zu nutzen (was die ganzen Parameter und die Funktionsaufrufe spart), was auch schneller sein sollte, da iterativ ja keine Funktionen aufruft und somit schonmal einiges gespart wird.

[erik.vikinger]

Hallo,

Wenn ich jetzt allerdings bereits weiß, wie groß der Standard-Stack ist (in der libc sollte das bekannt sein, denn sie ist OS-abhängig), kann ich Kleinkram auch auf dem Stack alloziieren und diesen Fall direkt in der libc lösen.

Hä, ich verstehe absolut nicht worauf Du hinaus möchtest. Willst Du den Stack als Heap benutzen? Das geht IMHO definitiv in die Hose, da helfen auch keine "Magic Cookies".

Worauf ich hinaus möchte, ist, dass ein kmalloc() aber im Kernel/VMM implementiert sein sollte (eben damit der Kernel eine full-featured-malloc-Umgebung nutzen kann) und wenn ich diese bereits im Kernel implementiert habe, kann ich sie in der libc auch einfach naiv weitergeben.

Und wenn ich im Kernel keine "full-featured-malloc-Umgebung" will/brauche? Gerade bei einem Micro-Kernel besteht danach absolut kein Bedarf. Ich will auch mit einem speziell für meinen Kernel optimierten SlabAllocator auskommen und sonst nichts, ich hab ja auch eine gute "full-featured-malloc-Umgebung" für den User-Space.

Aber ich denke, eine nicht immer, aber häufig zutreffende Grundannahme kann man schon machen

So lange die Verletzung dieser Annahme nicht zum Totalausfall des Systems führt (als keine erhebliche funktionale Einschränkung ist) sondern nur z.B. die Performance beeinflusst ist das auch völlig in Ordnung.

Dass die Workload im Regelfall den Fähigkeiten des Systems angepasst ist (oder diese untersteigt). Schließlich werde ich auf einem Pentium 133 mit 32 MB RAM keinen Windows Server 2008 als Active Directory Server für 20000 Nutzer einsetzen...

Ja, da hast Du sicher recht.

Das ist auch nicht das was ich meine, sondern das jedes OS ne Möglichkeit bietet Speicher vom OS anzufordern und das sollte wirklich jedes OS bieten und dann sollte eigentlich jeder malloc() Algo portierbar sein.

Mein OS muss auch die Möglichkeit bieten den Programm Speicher zur Verfügung zu stellen (geht ja wohl schlecht ohne) und trotzdem würdest nicht mal Du auf die Idee kommen auch nur den Algorithmus einer existierenden Heap-Implementierung auf mein OS zu portieren. Eine konkrete Heap-Implementierung ist von viel mehr abhängig als nur vom OS "irgendwie" Speicher zu bekommen. Viele Dinge davon sind nicht konkret durch die Syscall-API-Spezifikation geregelt sondern entstehen eher indirekt, z.B. weil der Programmierer des Heap weiß wie der VMM vom OS-Kernel arbeitet und versucht sich dem anzupassen um eine hohe Performance zu erzielen.

Gerade zwecks Portierbarkeit oder der Tatsache das sich am VMM mal was ändern kann, würde ich malloc() schon für sich alleine betrachten.

Portierbarkeit ist für eine Heap-Verwaltung nicht relevant da eh ziemlich unrealistisch. Wenn der VMM sich nur intern ändert aber die Syscall-API noch gleich bleibt dann muss die Heap-Verwaltung nicht unbedingt geändert werden aber es kann passieren das sie dann langsamer wird weil sie eben nicht mehr so gut dem VMM angepasst ist. Wenn der VMM sich so sehr ändert das die Syscall-API mit geändert werden muss dann muss auch zwangsläufig die Heap-Verwaltung mit geändert werden.

Wenn wir beide mit unseren OSen fertig sind können wir ja gegenseitig versuchen unsere Systeme zu knacken, mal sehen wer damit reichhaltigeren Erfolg hat.

Sehr gerne

Okay, abgemacht!

ich hoffe nur das wir dann noch in der Lage dazu sind

Was soll das heißen? So lange wollte ich nun auch wieder nicht brauchen. Außerdem hoffe ich das mein Verstand als letztes versagt, mein Gehirn ist IMHO das am besten trainierte Organ in meinem Körper.

Nein, normalerweise nicht, aber laut POSIX legt das OS einen Bereich im virtuellen Adressraum fest und der User-Code (die Heap-Verwaltung) kann diesen Bereich vergrößern und verkleinern (der Bereich bleibt also in einem Stück).

Ich weiß nicht ob Linux sowas wie ALR hat, aber wenn ja, dann gilt das eigentlich auch nicht mehr.

Ja, Linux kann ALR (in meinem OS möchte ich das später auch unterstützen). Und "am Stück" bedeutet nicht "an einer bestimmte Stelle".

Ich hoffe, dass die Singularität noch ein Weilchen weg ist. Bevorzugt bis nach meinem Tod.

Full ACK!
Aber ich hoffe dabei sich nicht mein Tod nach diesem Ereignis richtet sondern andersherum.


Grüße
Erik

[FlashBurn]

und trotzdem würdest nicht mal Du auf die Idee kommen auch nur den Algorithmus einer existierenden Heap-Implementierung auf mein OS zu portieren.

Das ist jetzt wieder eine deiner Antworten Ich habe deswegen ganz oft immer das Wort FlatMemory gebraucht.

Eine konkrete Heap-Implementierung ist von viel mehr abhängig als nur vom OS "irgendwie" Speicher zu bekommen. Viele Dinge davon sind nicht konkret durch die Syscall-API-Spezifikation geregelt sondern entstehen eher indirekt, z.B. weil der Programmierer des Heap weiß wie der VMM vom OS-Kernel arbeitet und versucht sich dem anzupassen um eine hohe Performance zu erzielen.

Wovon ist die Implementierung denn noch abhängig? Und was stellst du dir darunter vor das man eine Heap-Implementierung an den VMM anpasst?

Eine Heap-Implementierung lässt sich doch nur in so fern optimieren, dass das alloc() und free() schnellst möglich und mit möglichst wenig Speicherverbauch/Verschnitt passiert.

mein Gehirn ist IMHO das am besten trainierte Organ in meinem Körper.

Bei mir inzwischen leider auch

Und "am Stück" bedeutet nicht "an einer bestimmte Stelle".

Richtig, aber wenn der Adressraum von vielen benutzten Bereichen durchsetzt ist, sinkt die Wahrscheinlichkeit das man einen vorhanden Block immer weiter erweitern kann, doch sehr rapide und das war was ich damit meinte.

[Svenska]

Hallo,

Zumal du äußerst selten einen solchen Algorithmus brauchen solltest, insbesondere nicht für interne OS-Strukturen. Da hast du normalerweise nur selten mehr als 10k Elemente.

Wer redet hier von internen OS-Strukturen, es ging im den UserSpace und das der Stack eventuell zu klein ist um z.B. ein QuickSort auf einer größeren Datenmenge durchzuführen.

Richtig, ich hab das versehentlich auf eine universelle Sortierroutine verallgemeinert. Trotzdem glaube ich, dass du bei Anwendungen, die eventuell in so ein Limit laufen könnte, dies vorher weißt und den Stack im Voraus hinreichend groß machen kannst. Möglicherweise kann das sogar die Anwendung selbst tun.

Wenn du mir, nur weil ich es gerne in erster Instanz einfach, simpel und dumm baue, unterstellst, ich solle das Programmieren sein lassen, dann solltest du im Gegenzug mal deine Konzepte überdenken... denn dann ist irgendetwas grob falsch.

Sorry, aber du hast ja selbst gesagt, dass du es mit Threading nicht so hast, weil dir das zu kompliziert ist und du zeigst in deinen Antworten oft das du lieber alte Wege gehst als neue auszuprobieren.

Ich sehe halt wenig Notwendigkeit, gute, bekannte Konzepte wegzuwerfen. Wenn etwas allerdings nicht optimal funktioniert, dann suche ich auch nach neuen Konzepten. Das mag sich mit deinem Wesen beißen, aber bisher bin ich damit gut gefahren. Never touch a running system, solange es die Aufgabe vollständig erfüllt.

Ich sage nicht das du dumm bist, aber was Software betrifft die irgendwo produktiv im Einsatz ist sollte die nicht so programmiert sein, das sie "alt" ist.

Erklär das mal deiner normalen Qualitätssicherung. Und ich habe auch wenig Interesse, dass in einem Flugzeug der Autopilot neue Wege "ausprobiert". Das ist eine Frage der Stabilität. Apache geht z.B. immernoch auf 1994 zurück, wenn sich die Codebasis zwischendurch auch mehrfach verändert hat, aber nach außen ist es dasselbe.

Denn das ist wieder genau das was ich schonmal gesagt habe, wir haben immer schnellere CPUs, immer mehr CPUs in einem System, immer mehr RAM, aber die Programme werden immer langsamer!

Das liegt definitiv nicht an den ausgetretenen Konzepten, von SMP mal abgesehen. Du kannst mit simplem C und einem hinreichend antiken Vorgehen mit hinreichend antiken Werkzeugen auf moderner Hardware einen hochgradig performanten Webserver bauen. Solange der Ruf aber eben nicht nach Effizienz, sondern nach Features geht, wirst du Bloat produzieren. Das sind Dinge wie KDE, Gnome oder auch Firefox - Features ohne Ende auf Kosten der Performance.

Und solange man Features vor Optimierung stellt, wächst Software auch immer schneller als die dazugehörige Hardware. Heutige PC-Spiele sind so gebaut, dass sie mit Maximaleinstellungen auf Rechnern laufen, die erst in 1-2 Jahren existieren werden! Das ist dann auch eine Wirtschaftsfrage. "Was lange hält, bringt kein Geld." Effiziente Bürosoftware (Office 2000) reicht für 90% aller Anwendungsfälle hin, würde aber keinen neuen Rechner erforderlich machen. Das ist Absicht!

Solange es immer kleine, schnelle Alternativen gibt, habe ich damit auch kein Problem.

Die zyklische Abhängigkeit kommt, wenn du malloc in der libc implementierst, im Kernel aber gerne ein malloc/kmalloc benutzen möchtest. Da du das nicht tust, sondern deinen Slab-Allocator benutzt, ist das für dich nicht relevant.

Ich habe das mit der zyklischen Abhängigkeit immernoch nicht verstanden. Denn darunter verstehe ich das die untereinander abhängig sind, aber das sehe ich halt nicht bzw. nicht das Problem.

Der Kernel kann keine im Userspace implementierten Funktionen nutzen. Implementierst du malloc im Userspace (libc), kann der Kernel das nicht nutzen. Tut er es doch, hast du zyklische Abhängigkeiten.

Ja ich nutze nur meinen SlabAllocator, aber was außer des Algos für die Verwaltung des Speichers unterscheidet den denn von einem normalen malloc()?

Eben genau der. Es ist ein anderer.

Variablen, die du nur in einer Funktion benutzt, kannst du auf den Stack legen. Rufst du eine Funktion auf, wird der Rücksprungpointer dahinter gelegt, ist also egal (die Zeiger bleiben gültig), bei einem Rücksprung würdest du an die falsche Adresse (nämlich den Inhalt der Variablen) springen. Um das zu vermeiden, nutzt man Magic Cookies, die Variablen von Rücksprungadressen trennen und ein Stack-Unwinding, was vom Compiler erledigt wird.

Was du beschreibst braucht also Support vom Compiler und ist ohne diesen nicht möglich. Was passiert wenn ein solches Programm eine Library benutzt die sowas nicht unterstützt?

Dann findet es nicht statt. Entweder, der Compiler macht ein Stack-Unwinding (sollte er eigentlich sowieso) oder er tut es nicht. Danach richtet sich, ob dein malloc() bestimmte Dinge auf dem Stack alloziieren kann oder eben nicht.

Also Stack-Unwinding halte ich schonmal für Performance schädlich und den VMM brauchst du trotzdem, denn wer soll denn den Stack verwalten (Multi-Threading)?

Stack-Unwinding ist eigentlich nur, dass du den Stack-Pointer nicht verschiebst, ohne die Daten vorher wieder vom Stack runterzunehmen. Das heißt, dass du zusätzliche (OS-)Daten, die malloc() da hingelegt hat, auf dem Stack haben darfst und diese auch nutzen kannst - und du vor einem Rücksprung aus einer Funktion brav alle Daten wieder abräumen musst.

Willst Du den Stack als Heap benutzen? Das geht IMHO definitiv in die Hose, da helfen auch keine "Magic Cookies".

Bringt aber Performance, wenn du Variablen nur innerhalb einer Funktion und darunterliegenden Funktionen benutzt und der Stack ausreichend groß ist. Grund ist vor allem Cache-Lokalität und, dass du keinen Syscall für Speicher brauchst, dieser Speicher nicht extra vom System verwaltet werden muss (die Verwaltung dessen findet im Userspace statt, der Stack als Ganzes gehört ohnehin zum Thread).

Und wenn ich im Kernel keine "full-featured-malloc-Umgebung" will/brauche? Gerade bei einem Micro-Kernel besteht danach absolut kein Bedarf. Ich will auch mit einem speziell für meinen Kernel optimierten SlabAllocator auskommen und sonst nichts, ich hab ja auch eine gute "full-featured-malloc-Umgebung" für den User-Space.

Dann fällt natürlich alles, was ich gesagt habe, weg - wenn du etwas nicht brauchst/willst, musst du es nicht implementieren.

Eine Heap-Implementierung lässt sich doch nur in so fern optimieren, dass das alloc() und free() schnellst möglich und mit möglichst wenig Speicherverbauch/Verschnitt passiert.

Das hängt vom Anwendungsfall ab. Eine Rekursion, die in jedem Rekursionsschritt eine Integer-Hilfsvariable benutzt, optimiert sich anders als ein Videoschnittprogramm, welches für jedes Bild mit 9 MB (1920x1200x4) arbeitet und hunderte Bilder gleichzeitig im Speicher hält. Zumal "schnell" und "wenig Verschnitt" sich gegenseitig ausschließen, du also einen Kompromiss finden musst und genau der beste Kompromiss wieder vom Anwendungsfall abhängt. (Du siehst das anders.)

Gruß,
Svenska

[FlashBurn]

Ich sehe halt wenig Notwendigkeit, gute, bekannte Konzepte wegzuwerfen. Wenn etwas allerdings nicht optimal funktioniert, dann suche ich auch nach neuen Konzepten.

Definiere optimal? Ich rede davon das du einen Algo hast der nur eine CPU auslastet, du aber nen anderen Algo nutzen könntest der alle vorhandenen CPUs auslastet, dann ist das für mich nicht optimal.

Das liegt definitiv nicht an den ausgetretenen Konzepten, von SMP mal abgesehen.

Es geht mir in diesem Fall aber genau um SMP und Multithreading.

Implementierst du malloc im Userspace (libc), kann der Kernel das nicht nutzen. Tut er es doch, hast du zyklische Abhängigkeiten.

Entweder malloc() ruft eine Funktion auf die es im Kernel gar nicht gibt (weil sie nur im UserSpace als Syscall existiert) oder die Funktion ist die selbe, dann funktioniert das ganze oder ich habe dich nicht verstanden

Du meinst doch aber nicht die libc, die eventuell im UserSpace geladen ist, im Kernel zu nutzen oder?

Eben genau der. Es ist ein anderer.

Du kannst nicht von malloc() auf den Algo der dahinter steckt schließen. Schließlich kann hinter einem malloc() auch ein SlabAllocator stecken.

Stack-Unwinding ist eigentlich nur, dass du den Stack-Pointer nicht verschiebst, ohne die Daten vorher wieder vom Stack runterzunehmen. Das heißt, dass du zusätzliche (OS-)Daten, die malloc() da hingelegt hat, auf dem Stack haben darfst und diese auch nutzen kannst - und du vor einem Rücksprung aus einer Funktion brav alle Daten wieder abräumen musst.

Was du da beschreibst sind doch aber lokale Variablen die auf den Stack gepackt werden. malloc() ruft man für gewöhnlich für Sachen auf, die länger als nur eine Funktion existieren.

Zumal "schnell" und "wenig Verschnitt" sich gegenseitig ausschließen, du also einen Kompromiss finden musst und genau der beste Kompromiss wieder vom Anwendungsfall abhängt. (Du siehst das anders.)

Also ersten sehe ich letzteres genauso (hängt vom Anwendungsfall ab) und zweitens heißt nur das es noch keinen Algo gibt der beides vereinen kann, dass es den niemals gibt (das sehe ich halt anders).

Erik mit seinem Segmenten (und damit mit vergrößerbaren Arrays) hat mich nun wahrscheinlich doch dazu gebracht, das ich auch für einiges Arrays einsetzen werde.

Ich rede jetzt nur von IDs wie man sie für Threads usw. benutzt. Die Threads werden dann anhand ihrer ID in einen Baum eingetragen.
Das ganze ist zwar schön flexibel, aber weder O(1) noch Speichereffizient.
Würde ich ein großes Array nehmen, könnte ich genau anhand der ID den Pointer auf den Thread holen. Das wäre O(1) und Speichereffizient. Problem wäre halt nur das ich einen zusammenhängenden Bereich im virtuellen Adressraum belege und die Anzahl der IDs künstlich beschränken würde.

Ich habe jetzt gerade nur folgendes Problem. Ich würde die FreeList in dem Array speichern, sprich ich speichere nur die erste freie ID und in dem Arrayeintrag steht die nächste freie ID. Soweit so einfach.

Wie kann man da jetzt sortiert in diese FreeList einfügen ohne das man die gesamte Liste durchgehen müsste?

[Svenska]

Ich sehe halt wenig Notwendigkeit, gute, bekannte Konzepte wegzuwerfen. Wenn etwas allerdings nicht optimal funktioniert, dann suche ich auch nach neuen Konzepten.

Definiere optimal? Ich rede davon das du einen Algo hast der nur eine CPU auslastet, du aber nen anderen Algo nutzen könntest der alle vorhandenen CPUs auslastet, dann ist das für mich nicht optimal.

Das ist optimal, wenn nur eine CPU vorhanden/frei ist. Außerdem bringt dir Parallelität nur begrenzte Beschleunigung. Dieser Punkt (break-even) hängt von den Randbedingungen des Systems ab (z.B. HT sind zwei voneinander abhängige Kerne, du kannst nicht schnell genug parallel von der Festplatte lesen), aber auch von der inneren Struktur des Algorithmus. Jeder parallelisierbare Algorithmus lässt sich in drei Abschnitte zerlegen: (a) das Zerlegen des Problems in Teilschritte, (n) die parallele Abarbeitung dieser Teilschritte, (c) das Verbinden der Teilergebnisse zu einem einzelnen Ergebnis des Algorithmus.

Nur (b) wird parallel abgearbeitet. Ist (b) verglichen mit der Gesamtzeit von (a) und (c) klein, lohnt sich Parallelisierung nicht. Du lastest dann zwar alle CPUs aus (dein Optimalitätskriterium), erreichst aber keine Geschwindigkeitsvorteile mehr davon. Andere Optimalitätskriterien sind Einfachheit, Geschwindigkeit der Implementierung, Sicherheit, aber auch Ergebniskorrektheit.

Derzeitige 3D-Spiele, die hochgradig parallelisiert werden müssen (z.B. für Cell-Prozessoren), beschleunigt man auf ganz anderen Ebenen: Sämtliche Aktionen (Objektrendering, Physikberechnung, Eingabeverarbeitung, Housekeeping) werden in einen großen Aufgabenpuffer geworfen und auf jeder PPE (Recheneinheit) läuft ein Thread, der selbstständig eine Aufgabe aus diesem Puffer erledigt. Einzelne Algorithmen werden seltener parallelisiert, eben weil sich das nur bis zu einer bestimmten Menge an Threads/CPUs lohnt.

Im Großen und Ganzen ist das für mich aber eine Einzelfallentscheidung, die von der Gesamtlaufzeit des Algorithmus abhängt. Wird er nur einmal für die Initialisierung aufgerufen, ist mir die Geschwindigkeit egal; ist es Teil einer "hier für alles bitte nutzen"-Bibliothek, dann eher nicht.

Das liegt definitiv nicht an den ausgetretenen Konzepten, von SMP mal abgesehen.

Es geht mir in diesem Fall aber genau um SMP und Multithreading.

Du solltest aber nicht auf Teufel komm raus parallelisieren.

Du meinst doch aber nicht die libc, die eventuell im UserSpace geladen ist, im Kernel zu nutzen oder?

Denn das ist nicht möglich. Und die Userspace-libc ist auch nicht die Kernelspace-libc.

Du kannst nicht von malloc() auf den Algo der dahinter steckt schließen. Schließlich kann hinter einem malloc() auch ein SlabAllocator stecken.

Muss ich auch nicht.

Stack-Unwinding ist eigentlich nur, dass du den Stack-Pointer nicht verschiebst, ohne die Daten vorher wieder vom Stack runterzunehmen. Das heißt, dass du zusätzliche (OS-)Daten, die malloc() da hingelegt hat, auf dem Stack haben darfst und diese auch nutzen kannst - und du vor einem Rücksprung aus einer Funktion brav alle Daten wieder abräumen musst.

Was du da beschreibst sind doch aber lokale Variablen die auf den Stack gepackt werden. malloc() ruft man für gewöhnlich für Sachen auf, die länger als nur eine Funktion existieren.

Nicht nur. Es gibt genug Randfälle, wo du lokale, kurzlebige Variablen dynamisch erzeugen möchtest (z.B. Puffer, um strcpy() benutzen zu können, wenn du die Datenmenge erst zur Laufzeit bestimmen möchtest), oder wenn du temporär solche Strukturen benutzen möchtest, um sie in Unterfunktionen zu bearbeiten. Sowas kann man aus Performancegründen auch auf den Stack alloziieren.

Ich rede jetzt nur von IDs wie man sie für Threads usw. benutzt. Die Threads werden dann anhand ihrer ID in einen Baum eingetragen.
Das ganze ist zwar schön flexibel, aber weder O(1) noch Speichereffizient.
Würde ich ein großes Array nehmen, könnte ich genau anhand der ID den Pointer auf den Thread holen. Das wäre O(1) und Speichereffizient. Problem wäre halt nur das ich einen zusammenhängenden Bereich im virtuellen Adressraum belege und die Anzahl der IDs künstlich beschränken würde.

Dynamische Datenstrukturen sind nicht O(1), da du nie im Voraus weißt, wieviele Elemente du hast.

Wie kann man da jetzt sortiert in diese FreeList einfügen ohne das man die gesamte Liste durchgehen müsste?

Listen sortiert halten ist nicht möglich, ohne dir Elemente anzuschauen; dafür gibt es Bäume. Eine Alternative wären Bitfelder, aber die kann man nicht beliebig vergrößern/verkleinern und Löcher müssten halt abgebildet werden... eine andere Möglichkeit gibt es, wenn du irgendwoher einen Zeiger auf das vorherige Element besorgen kannst (gibst du einen Block frei, gehört zu diesem Block ein Zeiger in die Liste, dort fügst du ein), setzt aber die Speicherung der belegten Blöcke voraus...

Gruß,
Svenska

[FlashBurn]

Du solltest aber nicht auf Teufel komm raus parallelisieren.

Das ist klar, wenn der Aufwand für das Parallelisieren so klein ist, das er immer nicht spürbar ist, dann kann man sich den sparen, aber um beim Bsp. sortieren zu bleiben. Wenn du eine ausreichend große Datenmenge sortierst und das am besten noch oft, wird sich das schon lohnen.

Und die Userspace-libc ist auch nicht die Kernelspace-libc.

Jetzt verwirrst du mich komplett  Denn wenn du sowieso eine KernelSpace-libc und eine UserSpace-libc hast, wo ist da die Abhängigkeit?

Nicht nur. Es gibt genug Randfälle, wo du lokale, kurzlebige Variablen dynamisch erzeugen möchtest (z.B. Puffer, um strcpy() benutzen zu können, wenn du die Datenmenge erst zur Laufzeit bestimmen möchtest), oder wenn du temporär solche Strukturen benutzen möchtest, um sie in Unterfunktionen zu bearbeiten. Sowas kann man aus Performancegründen auch auf den Stack alloziieren.

Also für Strukturen gibt es lokale Variablen und für dein Bsp. mit strcpy gibt es dynamische Arrays (und die können seit C99) auch bei erst zur Laufzeit bekannten Größe auf dem Stack gemacht werden.
Der Punkt ist doch, das du hier von lokalen Sachen sprichst und ein malloc() aber eher für Sachen genutzt wird, welche langlebig sind.

Dynamische Datenstrukturen sind nicht O(1), da du nie im Voraus weißt, wieviele Elemente du hast.

Ich rede doch von einem Array und dem Zugriff und der ist nunmal O(1). Auch das bekommen einer neuen ID wäre in meinem Fall O(1) (einfach die erste freie nehmen).
Das einzige was nicht O(1) ist, ist das einfügen einer vorher benutzten ID in die FreeList.

Listen sortiert halten ist nicht möglich, ohne dir Elemente anzuschauen; dafür gibt es Bäume.

Der Satz macht für mich mal überhaupt keinen Sinn. Bei Bäumen musst du dir auch Elemente angucken um dort einfügen zu können.

Was ich noch vergessen habe zu erwähnen. Ich rede von einem Array das genau 1024 Einträge hat und bei dem die Anzahl der freien Elemente bekannt ist.
Ich möchte halt das sortierte Einfügen optimieren. 2 Fälle wären schonmal:

Das Element ist kleiner als das erste Element der Liste -> neuer Listenanfang

Das Element ist größer als das letzte Elemente der Liste -> neues Listenende (das würde halt nur vorraussetzen das ich das Listenende auch speichere)

Ich dachte daran halt daran einfach von dem Element was freigegeben wird (der Index) nach links und rechts nach einem freien Index zu suchen (kann ich machen, weil freie Elemente den Wert < 1024 und besetzte Elemente einen Wert > 0xC0000000 haben).
Es wäre halt schön die Schleifendurchläufe ein wenig zu drücken.

Um mal ein Bsp Array zu zeigen (FreeList= 0; und das Ende der FreeList hätte den Eintrag sizeof(Array)):

Code: [Auswählen]

[2][0xC0001234][4][0xC000DEAD][5]


[Svenska]

Hallo,

Du solltest aber nicht auf Teufel komm raus parallelisieren.

Das ist klar, wenn der Aufwand für das Parallelisieren so klein ist, das er immer nicht spürbar ist, dann kann man sich den sparen, aber um beim Bsp. sortieren zu bleiben. Wenn du eine ausreichend große Datenmenge sortierst und das am besten noch oft, wird sich das schon lohnen.

Definiere "ausreichend groß". Alle Felder, die ich bisher sortiert habe (gut, das waren nicht viel), ließen sich mit Quicksort rekursiv-seriell in wenigen ms (bis in Delphi nicht messbar kurzer Zeit) sortieren. Eine Datenbank, die ohnehin riesige Datenmengen verwaltet, wird ohnehin auf sie zugeschnittene Algorithmen verwenden.

Und die Userspace-libc ist auch nicht die Kernelspace-libc.

Jetzt verwirrst du mich komplett  Denn wenn du sowieso eine KernelSpace-libc und eine UserSpace-libc hast, wo ist da die Abhängigkeit?

Dann gibt es keine. Ich hab den Faden verloren.

Also für Strukturen gibt es lokale Variablen und für dein Bsp. mit strcpy gibt es dynamische Arrays (und die können seit C99) auch bei erst zur Laufzeit bekannten Größe auf dem Stack gemacht werden.

OK, ich habe mich mit C-Standards nur am Rande befasst (für den Grundlagenkram, den ich kann und brauche, ist das nicht nötig). Im Endeffekt schiebst du die ganze Problematik also auf den Compiler und dessen Stackverwaltung, was so ziemlich genau das ist, was ich auch schrieb.

Der Punkt ist doch, das du hier von lokalen Sachen sprichst und ein malloc() aber eher für Sachen genutzt wird, welche langlebig sind.

Wenn man für kurzzeitige Sachen auf nifty features vom Compiler setzen kann, dann braucht man das in der libc nicht implementieren, richtig. Wusste ich nicht, hab ich mich nie befasst.

Ich rede doch von einem Array und dem Zugriff und der ist nunmal O(1). Auch das bekommen einer neuen ID wäre in meinem Fall O(1) (einfach die erste freie nehmen).
Das einzige was nicht O(1) ist, ist das einfügen einer vorher benutzten ID in die FreeList.

Eben. Ich sehe damit aber nur begrenzt ein Problem, es sei denn, es handelt sich um extrem viele IDs, die da jede Sekunde freigegeben werden. Du wirst nicht alles auf O(1) zurückführen können.

Listen sortiert halten ist nicht möglich, ohne dir Elemente anzuschauen; dafür gibt es Bäume.

Der Satz macht für mich mal überhaupt keinen Sinn. Bei Bäumen musst du dir auch Elemente angucken um dort einfügen zu können.

Stimmt. Aber nur O(logn) statt O(n/2), sofern ich nicht irre.

Gruß,
Svenska

[FlashBurn]

OK, ich habe mich mit C-Standards nur am Rande befasst (für den Grundlagenkram, den ich kann und brauche, ist das nicht nötig). Im Endeffekt schiebst du die ganze Problematik also auf den Compiler und dessen Stackverwaltung, was so ziemlich genau das ist, was ich auch schrieb.

Nur das was du beschrieben hattest, hörte sich im ersten Moment so an als wenn du langlebige Sachen auf den Stack packen wolltest und als du dann genauer wurdest klang es für mich nach lokalen Variablen die irgendwie komisch durch Magic Cookies (sind das nicht Drogenkekse ) realisiert wurden.

Eben. Ich sehe damit aber nur begrenzt ein Problem, es sei denn, es handelt sich um extrem viele IDs, die da jede Sekunde freigegeben werden. Du wirst nicht alles auf O(1) zurückführen können. smiley

Leider nicht Ich werd erstmal Code schreiben, der zur Not 1022 Elemente anfassen muss und dann später sehen ob mir nicht noch was einfällt (ne Bitmap wäre ne Lösung, na mal sehen).

Stimmt. Aber nur O(logn) statt O(n/2), sofern ich nicht irre.

Richtig, aber was mir noch zum Array eingefallen ist, auch vom Caching her ist ein Array um Welten besser als ein Baum, denn beim Baum wird immer genau eine Page (da wo der Wert abgespeichert ist) angefasst und beim Baum kann es im worst-case eine Page pro Element sein und da steigt natürlich die Wahrscheinlichkeit das die Pages nicht im Cache ist bzw. diesen sogar noch zumüllen.

[Svenska]

Hallo,

OK, ich habe mich mit C-Standards nur am Rande befasst (für den Grundlagenkram, den ich kann und brauche, ist das nicht nötig). Im Endeffekt schiebst du die ganze Problematik also auf den Compiler und dessen Stackverwaltung, was so ziemlich genau das ist, was ich auch schrieb.

Nur das was du beschrieben hattest, hörte sich im ersten Moment so an als wenn du langlebige Sachen auf den Stack packen wolltest und als du dann genauer wurdest klang es für mich nach lokalen Variablen die irgendwie komisch durch Magic Cookies (sind das nicht Drogenkekse ) realisiert wurden.

Von mir aus darfst du es auch Magic Numbers nennen. Mir ging es an der Stelle darum, Stack-Korruption zu erkennen; das wird nämlich besonders interessant, wenn man zusätzlich zu den Rücksprungadressen auch noch Variablen/Felder auf den Stack legt. Du trennst also den Rücksprungteil von den Variablen durch ein Magic Cookie; wenn es kaputt geht, ist der Stack zerstört worden (wildgewordener Pointer oder so). Position und Wert des Cookies müssen natürlich zufällig erzeugt werden, sonst bringt es nichts.

Das implementiert man aber in der libc (und im Compiler), nicht im Kernel. Wenn der Compiler das schon intelligent tut, ist mein Gedanke hinfällig.

Stimmt. Aber nur O(logn) statt O(n/2), sofern ich nicht irre.

Richtig, aber was mir noch zum Array eingefallen ist, auch vom Caching her ist ein Array um Welten besser als ein Baum, denn beim Baum wird immer genau eine Page (da wo der Wert abgespeichert ist) angefasst und beim Baum kann es im worst-case eine Page pro Element sein und da steigt natürlich die Wahrscheinlichkeit das die Pages nicht im Cache ist bzw. diesen sogar noch zumüllen.

Das stimmt. Wenn du aber die Elemente deines Baumes durch einen Slab-Allocator erzeugst, dann liegen sie im Speicher auch relativ nah beieinander, was den Nachteil etwas abfedern dürfte.

Gruß,
Svenska

[FlashBurn]

Mir ging es an der Stelle darum, Stack-Korruption zu erkennen; das wird nämlich besonders interessant, wenn man zusätzlich zu den Rücksprungadressen auch noch Variablen/Felder auf den Stack legt.

Jetzt hast du mich wieder soweit das ich verwirrt bin

Ich dachte es ging darum kleine Anfragen an malloc() auf den Stack zu legen?

Jetzt verstehe ich aber endlich was du mit deinen Magic Cookies eigentlich erreichen wolltest, nur hat das mit dem diskutierten Problem nichts zu tun.
Die Idee ist aber trotzdem nicht schlecht, kostet halt aber auch Performance. Könnte man das nicht irgendwie performanter machen?

Obwohl wenn man beim Start des Programms einen solchen Wert (Magic Cookie) "erstellt" (wobei hier wieder das Problem der zufälligen Zahlen wäre) und an einer festen Adresse speichert. Dann muss der Compiler nur noch seinen Code so erstellen, das er, wenn Arrays verwendet werden (die auf dem Stack liegen), einfach den letzten Wert vor der Rücksprungadresse mit diesem Wert vergleicht und beim Funktions-Prolog wird dieser Magic Cookie genau nach EBP (denn das ist für den Debugger wichtig) gelegt.

Das kostet dann nur noch in den Funktionen Performance wo man auch Arrays (wie oben beschrieben) verwendet. 100% sicher ist das leider auch nicht, ersten bekommt man leider keine echten zufälligen Zahlen und es gibt die Möglichkeit, wenn auch verdammt gering, dass das Magic Cookie in Ordnung ist, aber trotzdem die Rücksprungadresse überschrieben wurde.

Wenn du aber die Elemente deines Baumes durch einen Slab-Allocator erzeugst, dann liegen sie im Speicher auch relativ nah beieinander, was den Nachteil etwas abfedern dürfte.

Normalerweise schon In meinem Fall verwende ich den AVL-Baum, aber für viele Sachen und so kommt es das die Nodes aus einem Slab für verschiedene Bäume genutzt werden und somit wieder auf viele Pages verteilt liegen.

Das mit den Caches ist mir auch erst eingefallen, an sowas denkt man normalerweise nicht, aber wenn man sich das mal durch den Kopf gehen lässt, wieviel Zeit/Takte es auf einer modernen CPU kostet wenn etwas nicht im Cache liegt. Dann kann es miteinmal sein das entweder ein spezieller Allocator besser ist oder aber eine Datenstruktur die eigentlich langsamer (oder auch speicherverschwenderischer) ist, aufgrund von Datenlokalität besser ist.

[Svenska]

Ich dachte es ging darum kleine Anfragen an malloc() auf den Stack zu legen?

Unter anderem, ja.

Jetzt verstehe ich aber endlich was du mit deinen Magic Cookies eigentlich erreichen wolltest, nur hat das mit dem diskutierten Problem nichts zu tun.
Die Idee ist aber trotzdem nicht schlecht, kostet halt aber auch Performance. Könnte man das nicht irgendwie performanter machen?

Das ist eine Frage der gewünschten Sicherheit... du tauschst Performance (zusätzliche Prüfungen) gegen Sicherheit (Erkennung von Stack-Korruption) ein.

Obwohl wenn man beim Start des Programms einen solchen Wert (Magic Cookie) "erstellt" (wobei hier wieder das Problem der zufälligen Zahlen wäre) und an einer festen Adresse speichert. Dann muss der Compiler nur noch seinen Code so erstellen, das er, wenn Arrays verwendet werden (die auf dem Stack liegen), einfach den letzten Wert vor der Rücksprungadresse mit diesem Wert vergleicht und beim Funktions-Prolog wird dieser Magic Cookie genau nach EBP (denn das ist für den Debugger wichtig) gelegt.

Pseudorandom mit zufälligem Seed sollte hinreichend sein, aber der Abstand zwischen Cookie und Daten muss ebenfalls zufällig sein (d.h. auf dem Stack gibt es eine zufällige Größe an Leerraum, da reichen vielleicht 1..100 Bytes). Sonst kannst du das Cookie einfach überspringen und damit Rücksprungadressen gezielt manipulieren.

Das kostet dann nur noch in den Funktionen Performance wo man auch Arrays (wie oben beschrieben) verwendet. 100% sicher ist das leider auch nicht, ersten bekommt man leider keine echten zufälligen Zahlen und es gibt die Möglichkeit, wenn auch verdammt gering, dass das Magic Cookie in Ordnung ist, aber trotzdem die Rücksprungadresse überschrieben wurde.

Richtig. Wenn die Anwendung aber weder weiß, wo das Cookie ist, noch wie es aussieht, dann ist das schon relativ zuverlässig. Wenn man dann noch einen Pseudozufallszahlengenerator nimmt und dessen Seed regelmäßig (z.B. alle paar Sekunden) mit echtem Zufall setzt, dann reicht das eigentlich hin. Zumal ein Angriff über ein Netzwerk immer mit der Latenz zu kämpfen hat.

Schwierig ist es halt, genug echten Zufall zu bekommen. Linux nutzt dafür in diversen Subsystemen eingebaute Routinen, die immer ein paar Bit in einen großen, allgemeinen Random-Pool (exportiert als /dev/random) einzahlen. Ich weiß es sicher vom Input-Subsystem (Maus- & Tastaturbewegungen sind zufällig) und vom alten IDE-Subsystem (Suchzeiten des Festplattenkopfes schwanken auch bei gleichen Suchmustern) und das sind immer nur ein paar Bits, die da auflaufen.

Das mit den Caches ist mir auch erst eingefallen, an sowas denkt man normalerweise nicht, aber wenn man sich das mal durch den Kopf gehen lässt, wieviel Zeit/Takte es auf einer modernen CPU kostet wenn etwas nicht im Cache liegt. Dann kann es miteinmal sein das entweder ein spezieller Allocator besser ist oder aber eine Datenstruktur die eigentlich langsamer (oder auch speicherverschwenderischer) ist, aufgrund von Datenlokalität besser ist.

Richtig, deswegen mache ich mir im Allgemeinen auch nur wenig Gedanken um Optimierung. Denn entweder man kennt sich mit den Details der Materie richtig gut aus und investiert eine Menge Arbeit oder Performance-Tracing, oder man baut erstmal etwas funktionierendes zusammen (wo man nur die gröbsten Optimierungen einbaut, z.B. Quicksort statt langsamer Algorithmen) und verlässt sich beim Optimieren auf den Compiler. Wenn es nicht "hinreichend schnell" ist, dann wird halt nochmal extra geschaut. Das ist eine Aufwandsfrage, für dich eher in Richtung Performance, für mich eher in Richtung einfach.

Wobei bei heutigen Rechengeschwindigkeiten eigentlich immer gilt: Fast alles, was klein ist, ist auch schnell. Langsam ist nur Bloat.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Das ist jetzt wieder eine deiner Antworten

Genau dafür mögt Ihr mich doch alle so sehr.

Ich habe deswegen ganz oft immer das Wort FlatMemory gebraucht.

Wo?

Das ist auch nicht das was ich meine, sondern das jedes OS ne Möglichkeit bietet Speicher vom OS anzufordern und das sollte wirklich jedes OS bieten und dann sollte eigentlich jeder malloc() Algo portierbar sein.

Mein OS muss auch die Möglichkeit bieten den Programm Speicher zur Verfügung zu stellen .....

Der Satz von Dir den ich zitiert habe enthält 2 mal "jedes OS" und dazu noch "jeder malloc() Algo", also 3 mal "jede[s/r]". Sorry, aber ich kann da keine Einschränkung auf Flat-Memory erkennen. Mir ist schon klar das Du normalerweise von Flat-Memory ausgehst aber Du versuchst da trotzdem Verallgemeinerungen auf zu stellen die eigentlich nicht funktionieren können (nur das wollte ich Dir verdeutlichen). Die Heap-Implementierung ist existenziell von der Verwaltung des virtuellen Adressraums abhängig (daraus wird ja der Heap generiert) und die macht eben meistens das OS (oder zumindest eine OS-spezifische Library). Daraus folgt nun mal das die Heap-Verwaltung vom OS abhängig ist. Klar könnte man auch für mein OS eine ganz simple Heap-Verwaltung portieren die einfach ein eigenes Segment bekommt und dort drin dann ein brk() macht das dann einfach zu einem SetSegmentLimit() umgesetzt wird, es ließe sich theoretisch 99% vom malloc-Code und damit auch der eigentliche Algorithmus unverändert übernehmen aber als Sinnvoll würde ich das nicht betrachten. Wenn Du mehr als so eine Primitiv-Lösung möchtest (und ich denke das wollen wir alle) dann kommst Du nicht drumherum Dich mit der Verwaltung des virtuellen Adressraum genauer zu befassen und da das von jedem OS anders gehandhabt werden kann ist die Heap-Implementierung immer sehr OS-spezifisch. Es gibt natürlich recht genersiche Librarys die dann aber eben auch bestimmte Syscalls erwarten und es gibt Librarys die es zwar auf vielen OSen gibt die aber immer etwas angepasst wurden (da ist zwar ein großer Teil der Algorithmen und des Quell-Codes identisch aber es sind auch viele Details sehr unterschiedlich).

Eine Heap-Implementierung lässt sich doch nur in so fern optimieren, dass das alloc() und free() schnellst möglich und mit möglichst wenig Speicherverbauch/Verschnitt passiert.

Ja, ganz recht, aber dazu muss man schon wissen wie das System arbeitet. Wenn man sich nicht für das OS interessiert dann kann man eben auch nicht optimieren und eine nicht-optimierte Heap-Implementierung will doch keiner mehr.

mein Gehirn ist IMHO das am besten trainierte Organ in meinem Körper.

Bei mir inzwischen leider auch

Wieso leider? Ich bin recht stolz darauf das mein Gehirn in einem so guten Zustand ist und gebe mir auch alle Mühe dass das so bleibt.

aber wenn der Adressraum von vielen benutzten Bereichen durchsetzt ist, sinkt die Wahrscheinlichkeit das man einen vorhanden Block immer weiter erweitern kann, doch sehr rapide und das war was ich damit meinte.

Das ist aber ein generelles Problem von Flat-Memory-Systemen, jeder Prozess hat eben nur einen einzigen und eindimensionalen Adressraum. Flat-Memory funktioniert eben nur dann bequem wenn der virtuelle Adressraum nur dünn benutzt ist bzw. wenn der virtuelle Adressraum um ein vielfaches größer ist als der tatsächliche Speicher-Bedarf so das sich immer eine passende Lücke finden lässt.


@svenska:
Objekte auf den Stack zu legen anstatt dafür den Heap zu benutzen ist eigentlich eine Entscheidung das Programmierers. Sicher kann man versuchen das der Compiler da zur compilezeit etwas optimiert oder man könnte Code einfügen lassen der zur Laufzeit ermittelt wie viel Speicher da eigentlich geholt werden soll und wenn das nicht zu viel ist (<= z.B. 64kBytes) dann wird einfach Stack benutzt. Ich denke schon das man da einiges vom Compiler optimieren lassen könnte aber ich glaube nicht dass das heutige Compiler bereits tun.
Was die "Magic Cookies" angeht so ist das einfach ein Problem der Stack-Implementierung, das der Stack nach unten wächst aber alle anderen Datenstrukturen nach oben ist einfach eine Fehlkonstruktion (zumindest aus heutiger Sicht wo der Stack einfach ein beliebiger dynamischer Bereich des Speichers ist und nicht das obere Ende eines fixen Real-Mode-Segments). Deswegen wächst mein Stack ja auch nach oben und schon ist dieses Problem nur noch halb so schlimm, trotzdem werde ich noch etwas Denkarbeit in die Realisierung von VLAs usw. investieren müssen.
Echten Zufall müsste eigentlich auch die CPU selber zur Verfügung stellen, etwa so wie VIA das macht, und schon wäre noch ein Angriffspunkt weg. Wenn der Referenzwert für die Cookies irgendwo im Speicher liegt dann ist er dort auch lesbar und vor allem auch manipulierbar. Welches OS markiert schon die Pages in denen die .const-Section liegt wirklich als Read-Only?


Grüße
Erik

[FlashBurn]

Pseudorandom mit zufälligem Seed sollte hinreichend sein, aber der Abstand zwischen Cookie und Daten muss ebenfalls zufällig sein (d.h. auf dem Stack gibt es eine zufällige Größe an Leerraum, da reichen vielleicht 1..100 Bytes). Sonst kannst du das Cookie einfach überspringen und damit Rücksprungadressen gezielt manipulieren.

Wie stellst du dir das vor, das der Cookie übersprungen werden könnte? Ich meine wir reden hier doch im Endeffekt darüber einen Buffer-Overflow zu erkennen, oder?

Wenn die Anwendung aber weder weiß, wo das Cookie ist, noch wie es aussieht, dann ist das schon relativ zuverlässig.

Irgendwo muss es doch aber gespeichert sein, damit zu einen Wert zum überprüfen hast und diese Adresse dieses Wertes muss auch bekannt sein.

@erik

Ich will jetzt nicht deinen halben Beitrag zitieren. Also ich verstehe malloc()/free() immernoch so, dass es "nur" darum geht irgendwelche Bereiche vernünftig zu verwalten. Da ist es mir egal ob der Bereich den ich vom OS bekomme zusammenhängend ist oder ob ich viele Bereiche verwalte die über den Adressraum verteilt sind (obwohl mir eine Sache einfällt, die man doch beachten muss, wenn man guckt ob Bereiche zusammengefasst werden können und man Bounday Tags benutzt, muss man aufpassen das man nicht auf einen Bereich zugreift der nicht gemappt ist).

Wieso leider? Ich bin recht stolz darauf das mein Gehirn in einem so guten Zustand ist und gebe mir auch alle Mühe dass das so bleibt.

Weil es nur noch das Gehirn ist und es "früher" (wenn ich das Wort überhaupt schon benutzten darf ) anders war.

Flat-Memory funktioniert eben nur dann bequem wenn der virtuelle Adressraum nur dünn benutzt ist bzw. wenn der virtuelle Adressraum um ein vielfaches größer ist als der tatsächliche Speicher-Bedarf so das sich immer eine passende Lücke finden lässt.

Das war ja auch zu Zeiten von Single-Threaded und static Linking noch der Fall.

Was die "Magic Cookies" angeht so ist das einfach ein Problem der Stack-Implementierung, das der Stack nach unten wächst aber alle anderen Datenstrukturen nach oben ist einfach eine Fehlkonstruktion (zumindest aus heutiger Sicht wo der Stack einfach ein beliebiger dynamischer Bereich des Speichers ist und nicht das obere Ende eines fixen Real-Mode-Segments). Deswegen wächst mein Stack ja auch nach oben und schon ist dieses Problem nur noch halb so schlimm, trotzdem werde ich noch etwas Denkarbeit in die Realisierung von VLAs usw. investieren müssen.

Theoretisch ist es auch auf x86 kein Problem den Stack nach oben wachsen zu lassen (sollte eigentlich auch kein Problem für die Compiler sein, dreht sich halt das Vorzeichen beim Zugriff auf den Stack um), wie es auf anderen Architekturen aussieht weiß ich nicht. In dem Hinblick ist die x86 Architektur eigentlich recht flexibel.

[erik.vikinger]

Hallo,

Wie stellst du dir das vor, das der Cookie übersprungen werden könnte? Ich meine wir reden hier doch im Endeffekt darüber einen Buffer-Overflow zu erkennen, oder?

Man muss ein Array nicht zwangsläufig von Index 0 bis Index X linear durchlaufen, man kann da auch Lücken lassen die dann eben übersprungen werden. Ist das selbe Problem wie mit den Guard-Pages, wenn Du weißt wo die sind und wie groß die sind dann ist es kein Problem da drüber zu kommen.

Irgendwo muss es doch aber gespeichert sein, damit zu einen Wert zum überprüfen hast und diese Adresse dieses Wertes muss auch bekannt sein.

Das ist eines der Probleme dieser Stack-Protectoren. Die schützen zwar gegen "aus versehen" fehlerhaften Code oder simple Buffer-Overflows aber nicht gegen einen gezielten und mit Köpfchen vorbereiteten Angriff.

Also ich verstehe malloc()/free() immernoch so, dass es "nur" darum geht irgendwelche Bereiche vernünftig zu verwalten.

Das stimmt auch so ungefähr aber malloc muss den Heap in flexiblen Größen verwalten und nicht in Pages ansonsten könntest Du ja einfach anstatt malloc direkt einen Syscall benutzen um Speicher zu bekommen. Die Kernaufgabe einer Heap-Verwaltung ist die das Du Speicher der vom OS in Pages kommt in beliebigen Größen weitergeben kannst und das mit möglichst wenig Verschnitt und natürlich mit bestmöglicher Performance. Dazu muss die Heap-Verwaltung den virtuellen Speicher der vom OS in Pages kommt verwalten und auch die Speicherbereiche die an den User-Code weitergegeben wurden verwalten, das erste von beiden ist natürlich einfacher wenn der virtuelle Speicher für den Heap insgesamt nur ein Stück ist.

Weil es nur noch das Gehirn ist und es "früher" (wenn ich das Wort überhaupt schon benutzten darf ) anders war.

Das heißt Du vernachlässigst den Rest Deines Körpers? Das ist auf Dauer nicht gesund!
Als Mindestausstattung an qualitativ hochwertigen Sportgeräten sollte eine Freundin vorhanden sein, da gibt es dann schon viele flexible Möglichkeiten zur körperlichen Bewegung, auch an frischer Luft. Ich meine so Dinge wie eine Fahrradtour usw.

Flat-Memory funktioniert eben nur dann bequem wenn der virtuelle Adressraum nur dünn benutzt ist bzw. wenn der virtuelle Adressraum um ein vielfaches größer ist als der tatsächliche Speicher-Bedarf so das sich immer eine passende Lücke finden lässt.

Das war ja auch zu Zeiten von Single-Threaded und static Linking noch der Fall.

Genau so ist es!
Und weil sich das bis heute grundlegend geändert hat müssen eben neue Konzepte her und da ist meine Segmentierung ganz klar der Favorit.

Theoretisch ist es auch auf x86 kein Problem den Stack nach oben wachsen zu lassen ....

Dann schau Dir mal an wie CALL/RET oder INT/IRET oder PUSH/POP oder ENTER/LEAVE funktionieren (und wie die zugehörigen OpCodes aufgebaut sind). Das der Stack auf x86 nach unten wächst ist unumstößlich fest eingebaut! Gerade die anderen Architekturen sind da viel flexibler, viele von denen haben keine spezifischen Stack-Befehle sondern benutzen einfach normale Speicherzugriffe mit autoinkrement/autodekrement und deklarieren einfach ein beliebiges Register als Stack-Pointer und auch beim Modus-Wechsel (also von User-Mode in den System-Mode und zurück) erfolgt normalerweise kein Speicherzugriff und es wird auch kein Register modifiziert sondern es werden einfach ein paar der Register gegen andere (Schattenregister) ausgetauscht. Schau Dir mal ARM an, dort sind z.B. im GAS PUSH und POP nur vordefinierte Macros.


Grüße
Erik

[FlashBurn]

Man muss ein Array nicht zwangsläufig von Index 0 bis Index X linear durchlaufen, man kann da auch Lücken lassen die dann eben übersprungen werden. Ist das selbe Problem wie mit den Guard-Pages, wenn Du weißt wo die sind und wie groß die sind dann ist es kein Problem da drüber zu kommen.

Wir reden von Buffer-Overflows und das Problem ist ja das du etwas (linear) in den Buffer schreibst, aber davon ausgehst das sich jeder an gewisse Regeln hält was die Größe betrifft und wenn er das nicht macht, wird mehr in den Buffer geschrieben, als der Buffer groß ist. Das geschiet doch aber alles, wie gesagt, linear oder?

Dann schau Dir mal an wie CALL/RET oder INT/IRET oder PUSH/POP oder ENTER/LEAVE funktionieren (und wie die zugehörigen OpCodes aufgebaut sind). Das der Stack auf x86 nach unten wächst ist unumstößlich fest eingebaut!

Ich behaupte das dem nicht so ist. Die von dir genannten Opcodes packen nur etwas auf den Stack, in welche Richtung das geschiet, wird meines Wissens nach, durch den Segment Diskriptor des Stack Segments festgelegt und da kann man auch sagen das der Stack nach oben wachsen kann.

@OffTopic

Als Mindestausstattung an qualitativ hochwertigen Sportgeräten sollte eine Freundin vorhanden sein, da gibt es dann schon viele flexible Möglichkeiten zur körperlichen Bewegung, auch an frischer Luft. Ich meine so Dinge wie eine Fahrradtour usw. Wink

Die ist vorhanden, aber leider sind immer irgendwelche Faktoren vorhanden die etwas wie eine Fahrradtour schwer bis gar nicht möglich machen vorhanden. Die andere Sportart ist leider nicht so effektiv wie gutes Kraft-/Ausdauertraining (macht aber mehr Spaß)