Fügt free() freien Speicher eignetlich auch wieder zusammen?

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.

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.

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.)

Danke!

@ 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.