http://www.nongnu.org/avr-libc/user-manual/malloc.html Erklärt mir jedenfalls nicht, dass dies der Fall ist. Und irgendwann bekommen ich von malloc() in meinem Programm NULL oder sogar Adressen, die außerhalb des SRAMs liegen zurück. Ich habe mal schnell ein Programm zusammengehackt, welches mir die malloc, realloc, und free Befehle visualisiert und überprüft ob Anfragen übereinander liegen oder free Befehle doppelt vorkommen, was nicht der Fall zu sein scheint. Im Anhang mal eine Visualisierung (Scharz = frei, grau = Verwaltungsheader, weiß = belegt, 1 pixel = 2 Byte, Zeitachse von oben nach unten.). Kann ich dies irgendwie ändern? Weil bei meinem Anforderungs-freigebe-verhalten scheine ich ja irgendwann immer in Speicherprobleme zu rennen. Achja, das ganze bezieht sich auf avr-libc mit einem ATMega168.
Malte __ schrieb: > http://www.nongnu.org/avr-libc/user-manual/malloc.html > Erklärt mir jedenfalls nicht, dass dies der Fall ist. Doch. Da steht [quote] When calling free(), a new freelist entry will be prepared. An attempt is then made to aggregate the new entry with possible adjacent entries, yielding a single larger entry available for further allocations. That way, the potential for heap fragmentation is hopefully reduced. [/quote] Ob es tatsächlich so ist, ist eine andere Frage. Aber ich denke die Entwickler der Lib sind ja auch keine Trottel und wie man so etwas macht ist ja seit vielen Jahrzehnten bekannt. > Und irgendwann > bekommen ich von malloc() in meinem Programm NULL oder sogar Adressen, > die außerhalb des SRAMs liegen zurück. Irgendwann ist der Speicher entweder voll oder so zerstückelt, dass die Anforderung nicht mehr bedient werden kann. > Ich habe mal schnell ein Programm zusammengehackt, welches mir die > malloc, realloc, und free Befehle visualisiert und überprüft ob Anfragen > übereinander liegen oder free Befehle doppelt vorkommen, was nicht der > Fall zu sein scheint. Zeig doch mal dein Programm. Manchmal hat man nämlich auch Fehler in den Kontrollroutinen. Und die Krux bei dir ist ja, dass du die dynamische Speicherverwaltung überwachen willst, wofür du für die Kontrolldaten selbst wieder dynamische Speicherverwaltung brauchst. > Kann ich dies irgendwie ändern? Ja. Verzichte weitgehend auf malloc/free und arbeite mit konstanten statischen Allokierungen und maximalen Obergrößen, wo es auch immer irgendwie sinnvoll geht. Das vermindert auch das Risiko, dass du zur Laufzeit in Speicherprobleme läufst, weil die tatsächliche Speicherbelegung dann bereits zur Compilezeit vollständig bekannt ist.
Karl heinz Buchegger schrieb: > Und die Krux bei dir ist ja, dass du die dynamische > Speicherverwaltung überwachen willst, wofür du für die Kontrolldaten > selbst wieder dynamische Speicherverwaltung brauchst. Er könnte stattdessen die freelist selbst visualisieren.
Jörg Wunsch schrieb: > Karl heinz Buchegger schrieb: > >> Und die Krux bei dir ist ja, dass du die dynamische >> Speicherverwaltung überwachen willst, wofür du für die Kontrolldaten >> selbst wieder dynamische Speicherverwaltung brauchst. > > Er könnte stattdessen die freelist selbst visualisieren. Ja. Darum hab ich auch nach dem Code gefragt. Kennen wir doch alle: Nur weil irgendwo ein paar Pixel auftauchen, heißt das noch lange nicht, dass diese Pixel die tatsächliche Realität wiederspiegeln :-) Wenn irgendwo unerwartete 'Messergebnisse' auftauchen, dann misstraue ich als allererstes dem Messgerät :-)
Du kannst die Speicherverwaltung auch manuell aufsetzen. Zu Beginn des Programms holst du dir nen "riesen" Block Speicher, und vergibst den mittels eigener my_malloc() selbst. Reicht der Block nicht mehr, holst du dir den nächsten und baust den hintendran. So bist du frei und kannst deinen Speicher sogar bei Bedarf defragmentieren (dazu musst du aber wissen, welche Variable wo steht!) VG, /th.
Karl heinz Buchegger schrieb: > [quote] > When calling free(), a new freelist entry will be prepared. An attempt > is then made to aggregate the new entry with possible adjacent entries, > yielding a single larger entry available for further allocations. That > way, the potential for heap fragmentation is hopefully reduced. > [/quote] Ok das hatte ich übersehen. > Irgendwann ist der Speicher entweder voll oder so zerstückelt, dass die > Anforderung nicht mehr bedient werden kann. Ja, das stimmt, aber das Programm läuft halt derzeit einmal gerade so durch , dann wird sämtlicher Speicher freigegeben und der nächste Durchlauf mit den gleichen Speicheranforderungs-freigabe (unteres drittel in der Grafik) schlägt fehl. (Ein Mega328 mit 2KB RAM ist bestellt aber derzeit wohl nicht lieferbar). > Und die Krux bei dir ist ja, dass du die dynamische > Speicherverwaltung überwachen willst, wofür du für die Kontrolldaten > selbst wieder dynamische Speicherverwaltung brauchst. Ich habe für malloc, free und reallloc eine einfache mapper Funktion eingebaut, welche die ermittelten Adressen und Speichergrößen per Uart ausgibt und dann auf dem PC vollzieht ein Programm hinterher jeden Schritt nach. So dürfte dass auf dem Controller selber nur kurzzeitig ein paar Byte Stack gekosten haben.
malloc()/free() ist ganz furchtbar Implementationsabhängig, da ja im Standard nur die API beschrieben ist. Bei den meisten Implementationen wird free() Speicherblöcke immer dann zusammenfassen, wenn zwei benachbarte Blöcke frei liegen. Dadraus wird dann ein großer und ein Eintrag in der Speicherliste fällt weg. Aber free() wird mistens nicht hingehen und den Speicherbereich defragmentieren, also Speicherblöcke umherkopieren, um dadurch aus etlichen kleinen wieder ein paar große Blöcke zu konstruieren.
Malte __ schrieb: >> Und die Krux bei dir ist ja, dass du die dynamische >> Speicherverwaltung überwachen willst, wofür du für die Kontrolldaten >> selbst wieder dynamische Speicherverwaltung brauchst. > Ich habe für malloc, free und reallloc eine einfache mapper Funktion > eingebaut, welche die ermittelten Adressen und Speichergrößen per Uart > ausgibt und dann auf dem PC vollzieht ein Programm hinterher jeden > Schritt nach. So dürfte dass auf dem Controller selber nur kurzzeitig > ein paar Byte Stack gekosten haben. Ah. OK Wenn du die Auswertung auf dem PC machst, ist das natürlich was anderes.
Malte __ schrieb: > Ich habe für malloc, free und reallloc eine einfache mapper Funktion > eingebaut, welche die ermittelten Adressen und Speichergrößen per Uart > ausgibt und dann auf dem PC vollzieht ein Programm hinterher jeden > Schritt nach. In diesem Falle würden mich die detaillierten Anforderungen, die gelaufen sind, als Trace interessieren. Bitte als Anhang zu einem avr-libc-Bugreport.
Sven P. schrieb: > Aber > free() wird mistens nicht hingehen und den Speicherbereich > defragmentieren, also Speicherblöcke umherkopieren, um dadurch aus > etlichen kleinen wieder ein paar große Blöcke zu konstruieren. Das geht prinzipbedingt nicht: malloc/free haben keine Ahnung, wer sich im Programm alles den Zeiger gemerkt haben könnte. Nach einem Umkopieren müssten ja allen entsprechend nun nicht mehr aktuellen Zeiger aktualisiert werden. Dean Camera (Autor u. a. von LUFA) hat mal eine kleine Speicher- verwaltung geschrieben, die sowas kann. Dürfte sich in der Code- sammlung bei avrfreaks.net befinden.
Jörg Wunsch schrieb: > Das geht prinzipbedingt nicht: malloc/free haben keine Ahnung, wer > sich im Programm alles den Zeiger gemerkt haben könnte. Nach einem > Umkopieren müssten ja allen entsprechend nun nicht mehr aktuellen > Zeiger aktualisiert werden. Ja, deshalb bezog ich das ja auch ausdrücklich auf _free()_ und nicht auf noch alloziierte Speicherblöcke.
Sven P. schrieb: > Ja, deshalb bezog ich das ja auch ausdrücklich auf _free()_ und _nicht_ > auf noch alloziierte Speicherblöcke. Wenn du noch belegte Blöcke ausdrücklich ausschließt, warum unterscheidest du dann zwischen "benachbarte Blöcke zusammenlegen" und "defragmentieren"? Mit der gemachten Einschränkung ist doch beides das Gleiche.
Ich glaube, er hat das nur noch nicht zu Ende gedacht. Dass free() sich nach Nachbarblöcken umsieht, ist natürlich schon eine Art Defragmentierung, aber mehr als zwei Nachbarblöcke kann es (bei eindimensionalem Adressraum) halt nicht geben, und folglich kann es nicht mehr tun, als maximal diese beiden mit dem aktuell freigegebenen zu einem großen Block zu verschmelzen. Alle weitere Defragmentierung würde bedeuten, dass man auch belegte Blöcke umherschiebt, und genau das geht beim Prinzip von malloc/free nicht.
Den kompletten Code kann ich leider (bis auf weiteres) nicht veröffentlichen. Aber ich habe mal ein Beispiel aufgesetzt, bei dem man zumindest sieht, dass er nach einem realloc (verkleinern) beim nächsten malloc am ende des vorherigen malloc anfügt und eine Lücke entsteht. Aber zumindest in dem Beispiel werden in der Tat irgendwann freie Blöcke zusammengefasst. a = malloc(34); -> 318 als adresse realloc(a auf 10 byte) -> adresse bleibt gleich malloc(34) -> unnötige lücke entsteht. m 34 318 r 318 10 318 m 34 354
Malte __ schrieb: > http://www.nongnu.org/avr-libc/user-manual/malloc.html > Erklärt mir jedenfalls nicht, dass dies der Fall ist. Und irgendwann > bekommen ich von malloc() in meinem Programm NULL oder sogar Adressen, > die außerhalb des SRAMs liegen zurück. Hast Du ein korrektes Linker-Script verwendet? Sonst kennt malloc ggf. die physikalischen Grenzen nicht richtig. Wozu brauchst Du ueberhaupt malloc() auf dem AVR? Wieviel Speicher steht Dir zur Verfuegung?
Malte __ schrieb: > a = malloc(34); -> 318 als adresse > realloc(a auf 10 byte) -> adresse bleibt gleich > malloc(34) -> unnötige lücke entsteht. Ich müsste nachgucken, aber ich würde sagen, dass dieses Verhalten vom C-Standard zumindest gewünscht, wenn nicht sogar vorgeschrieben ist. Ein realloc() soll nach Möglichkeit den existierenden Block erweitern, damit kein Umkopieren nötig ist. Beim Verkleinern ist es damit logisch, dass dies immer in-place erfolgt. Die nachfolgende Lücke würde übrigens selbst mit malloc(24) nicht vergebbar sein, da malloc vor dem eigentlichen Block noch die Länge des Blocks aufzeichnen muss; erst malloc(22) könnte genau diese Lücke wieder recyclen. Wie geschrieben, wenn du eine Abfolge von malloc/realloc/free nennen kannst, die eindeutig zu buggigem Verhalten führt (Alloka- tionen überlappen sich, es entstehen Löcher im Speicherbereich, die nie wieder zugewiesen werden, Speicher jenseits von __malloc_heap_end wird ausgeteilt usw.), dann hätte ich gern einen Bugreport mit möglichst detaillierten Angaben. Dazu musst du ja keineswegs das Originalprogramm mitliefern, es genügt vollauf, wenn ein Pseudoprogramm geliefert wird, dass alle Abfolgen von malloc/realloc/free enthält, einschließlich der Randbedingungen (welcher Controllertyp, ggf. welche Linkeroptionen, statisch belegter RAM deiner eigentlichen Applikation kann ja ggf. durch ein einziges großes Array simuliert werden).
Jörg Wunsch schrieb: > Malte __ schrieb: > >> a = malloc(34); -> 318 als adresse >> realloc(a auf 10 byte) -> adresse bleibt gleich >> malloc(34) -> unnötige lücke entsteht. > > Ich müsste nachgucken, aber ich würde sagen, dass dieses Verhalten > vom C-Standard zumindest gewünscht, wenn nicht sogar vorgeschrieben > ist. Ein realloc() soll nach Möglichkeit den existierenden Block > erweitern, damit kein Umkopieren nötig ist. Beim Verkleinern ist > es damit logisch, dass dies immer in-place erfolgt. Der Knackpunkt ist doch aber das darauf folgende malloc. Der mit dem realloc frei werdende Bereich müsste ja mit dem freien Bereich dahinter verschmelzen. Warum liefert aber dann das nächste malloc einen Pointer, der dem ursprünglichen Ende von a entspricht?
Jörg Wunsch schrieb: > Ein realloc() soll nach Möglichkeit den existierenden Block > erweitern, damit kein Umkopieren nötig ist. Beim Verkleinern ist > es damit logisch, dass dies immer in-place erfolgt. Klar. > Die nachfolgende Lücke würde übrigens selbst mit malloc(24) nicht > vergebbar sein, da malloc vor dem eigentlichen Block noch die Länge > des Blocks aufzeichnen muss; erst malloc(22) könnte genau diese > Lücke wieder recyclen. Hm, ich hätte erwartet, dass er die entstehende Lücke mit dem bereits freien Speicher danach vereinigt. Also hier der 2. malloc Block an Adresse 318+10+2 beginnt. Generell muss ich in meiner Anwendung ziemlich viel mit Strings unbekannter Länge arbeiten und meine Idee war es beim Einlesen erstmal Speicher mit einer Maximallänge zu reservieren und danach die Größe des Speicherblocks auf die wirklich benötigte Größe zu kürzen. Da ich ungültige Adressen nur erhalte, wenn schon recht viel des RAMs bereits dem Heap zugeordnet ist, scheint es mir im Moment eher so, als ob der Stack in den Heap läuft und dadurch die malloc/realloc/free Funktionen durcheinander bringt.
Stefan Ernst schrieb: > Der Knackpunkt ist doch aber das darauf folgende malloc. Der mit dem > realloc frei werdende Bereich müsste ja mit dem freien Bereich dahinter > verschmelzen. OK, wenn der Bereich danach noch frei ist zu diesem Zeitpunkt, dann ist das korrekt. Ohne jetzt in den Code zu gucken, dämmert mir, was da passiert (ja, ein Bugreport wäre angebracht, auch wenn ich im Moment sicher nicht die Zeit habe, ihn zu bearbeiten): der Bereich hinter allen Allokationen wird nicht als freier Bereich gehandhabt, sondern von diesem Stück Kuchen wird nur dann was abgebissen, wenn die bislang als frei zurückgegebenen Bereiche nicht ausreichen. Nur wurden durch das realloc() aber nur 24 Bytes freigegeben. Diese bilden zu dem Zeitpunkt den einzigen Eintrag in der Freelist, und da sie nicht für die neue Anforderung von 34 Bytes genügen, wird dieser Eintrag ignoriert und stattdessen ein neues Stück Kuchen aus dem Heap ausgefasst (wobei sich dann der Zeiger erhöht, welche Adresse bislang als höchste Adresse für den Heap benutzt worden ist). Im Moment wird die Top-Adresse immer nur erhöht, nie wieder nach unten korrigiert, falls der oberste Block am Ende des Heap komplett wieder frei ist. Der Kuchen geht also nur eine Einbahnstraße. ;-) Das zu ändern ist sicher möglich, aber leider ein ziemliches Stück Arbeit, zumal man gleich noch die nötigen Schnipsel für die Testbench mit schreiben müsste, damit man einerseits sicherstellt, dass man keine neuen Bugs einbaut, andererseits überprüft, dass der entsprechende Block auch wirklich wieder zurückgegeben wird (d. h. der letztgenannte Test müsste mit dem derzeitigen Code ein FAIL ergeben, nach der Änderung dann ein PASS).
Ok, wenn die Lücken nur auftreten, wenn dahinter noch kein Speicher dem Heap zugewiesen ist, habe ich mal testeshalber am Anfang einmal 600 Byte reserviert und dann wieder freigegeben. Daraufhin wird der Speicher von hinten beginnen zugewiesen, mit der Folge, dass bei einem realloc Lücken entstehen die sich nicht nutzen lassen, weil dahinter bereits was liegt. Und weil ich sicher gehen wollte, dass nicht einfach die avr-libc von Debian veraltet ist, habe ich das ganze noch mal mit der aktuellsten WinAVR Version (in WINE) ausprobiert. -> In beiden fällen läuft der (inzwischen etwas erweiterte Test als im vorherigem Anhang) in ein Out of memory. Im Anhang ist der Erweiterte test, 4 hex Dateien deren Ausgabe und die Compilereinstellungen.
Wie schon geschrieben, hier im Forum nützt mir das nichts. Heute und morgen werde ich daran nichts tun, und wenn ich dann mal wieder geschlossen Zeit für ein paar avr-libc-Arbeiten habe, kann ich nicht erst diverse Foren durchsuchen. Bitte reiche das als avr-libc- Bugreport ein: https://savannah.nongnu.org/bugs/?group=avr-libc (Du musst dich registrieren, aber die email-Adresse wird nur benutzt, um dich ggf. bei der Bearbeitung des Bugs nochmal zu konsultieren.)
@ Jörg: Ich wollte malloc dahingehend ändern, dass beim "Kuchen abbeißen" ein direkt davor liegender freier Block miteinbezogen wird, als Übergangslösung für Malte oder auch als Patchvorschlag (sind nur ein paar zusätzliche Zeilen). Ein erster Test ging allerdings schief. Folgende Bedingung wollte nicht true werden und ich konnte mir beim besten Willen nicht erklären warum:
1 | if (fp2 && (char*)fp2 + fp2->sz + sizeof(size_t) == __brkval) { |
Also habe ich etwas tiefer gegraben und bin über einen dicken Bug in realloc als Ursache gestolpert. Bei einem Shrink setzt realloc den freien Bereich 2 Bytes zu weit vorne an, der Größenwert liegt dann also in den letzten beiden Bytes des belegten Bereichs. Ursache:
1 | cp = (char *)ptr + len; /* new next pointer */ |
ptr und len sind die beiden realloc-Parameter. cp zeigt damit auf das erste freie Byte dahinter. Daher ist das "- sizeof(size_t)" hier
1 | fp2 = (struct __freelist *)(cp - sizeof(size_t)); |
keine gute Idee. ;-) Bugreport folgt dann noch (morgen). Oder änderst du das gleich?
Stefan Ernst schrieb:
> Bugreport folgt dann noch (morgen). Oder änderst du das gleich?
Nö, heute wollte ich nichts an der avr-libc machen, bitte schreib's
kurz. Ich möchte dann auch noch einen Testcase dazu schreiben, um
sicherzustellen, dass sowas nicht später mal wieder auftaucht.
@ Malte: Hier die vorhin angekündigte Übergangslösung für dich. Die angehängte Datei enthält ein modifiziertes malloc, sowie ein korrigiertes realloc. Um sie zu benutzen, musst du die Datei deinem Projekt hinzufügen, und folgende Zeilen an geeigneter Stelle platzieren (oder als eigenen Header einbinden):
1 | void* xmalloc ( size_t size ); |
2 | void* xrealloc ( void* ptr, size_t len ); |
3 | |
4 | #define malloc xmalloc
|
5 | #define realloc xrealloc
|
Bitte teste es mal und berichte dann.
Vielen Dank Stefan. Also neue Blöcke werden jetzt wie erwartet passend in die Lücken gesteckt, damit dürfte von http://savannah.nongnu.org/bugs/?27235 1) gelöst sein. Der Realloc Fehler mit dem Speichern an der falschen Position, hat mich entweder nicht direkt getroffen, oder aber er hat immer zufällig dazu geführt, dass malloc behauptete keinen Speicher mehr zu haben (Punkt 3) der Fall, dass neuer Speicher über reserviertem angelegt worden wäre hätte mein eigenes Testprogramm wohl entdeckt. Aber ich weiß leider nicht wirklich ob dies allein für 3) verantwortlich ist. Bleibt 2), dass der Speicher von hinten nach vorne wieder benutzt wird. Das ist erstmal kein echter Bug. Aber für realloc doch recht ungünstig.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.