Eigenes Malloc

[Matthias (Gast)]

Hallo liebe Leute.

auf Basis dieser Seite
http://tharikasblogs.blogspot.com/p/how-to-write-your-own-malloc-and-free.html

Wollte ich das malloc mal auch für meinen AVR nachprogrammieren.

nun bin ich auf das Problem gestoßen das obwohl ich genau soviel 
myMallocs wie my rees habe, ich irgendwann kein Speicher mehr anfordern 
kann.

Meine kleinen Blocks Funktionen sagen es gäbe wohl blocks die noch 
belegt sein.

was meint ihr dazu ?

MFG
Matthias

#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <avr/io.h>
#include <avr/interrupt.h>
#include <avr/pgmspace.h>
#include <util/atomic.h>
#include <util/delay.h>


struct block{
 size_t size;
 bool free;
 struct block *next;
};


typedef struct
{
    volatile uint8_t* memory_;
    uint16_t size_;
    struct block *freeList_;
}MyHeap;




MyHeap myHeapInitialize(uint16_t heap_size);
void myHeapSplit(struct block *fitting_slot,uint16_t size);
void* myHeapMalloc(MyHeap *heap, uint16_t size);
void myHeapMerge(MyHeap *heap);
void myHeapFree(MyHeap *heap,void* ptr);

uint16_t myHeapCountBlocks(MyHeap *heap);
uint16_t myHeapCountFreeBlocks(MyHeap *heap);

uint16_t myHeapCountBlockedBlocks(MyHeap *heap);



MyHeap myHeapInitialize(uint16_t heap_size)
{

    void* heap_buffer  = (void *) calloc(heap_size,sizeof(uint8_t));
    MyHeap heap =
    {
        .memory_ = heap_buffer,
        .size_ = heap_size,
        .freeList_ = heap_buffer,
    };
    heap.freeList_->size=heap_size - sizeof(struct block);
    heap.freeList_->free=true;
    heap.freeList_->next=NULL;
    return heap;
}


void myHeapSplit(struct block *fitting_slot,uint16_t size)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    struct block *new=(void*)((void*)fitting_slot+size+sizeof(struct block));
    new->size=(fitting_slot->size)-size-sizeof(struct block);
    new->free=true;
    new->next=fitting_slot->next;
    fitting_slot->size=size;
    fitting_slot->free=false;
    fitting_slot->next=new;
    }
}


void* myHeapMalloc(MyHeap *heap, uint16_t size)
{
    void *result;
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {

    struct block *curr;
    curr=heap->freeList_;

    while((((curr->size)<size)||((curr->free)==false))&&(curr->next!=NULL)){
        //prev=curr;
        curr=curr->next;
        //printf("One block checked\n");
    }

    if((curr->size)==size){
        curr->free=false;
        result=(void*)(++curr);
        //printf("Exact fitting block allocated\n");
        return result;
    }
    else if((curr->size)>(size+sizeof(struct block))){
        myHeapSplit(curr,size);
        result=(void*)(++curr);
        //printf("Fitting block allocated with a split\n");
        return result;
    }
    else{
        result=NULL;
        PORTA.OUTSET = PIN4_bm;
        //printf("Sorry. No sufficient memory to allocate\n");
        return result;

    }
    }
    return result;
}


void myHeapMerge(MyHeap *heap)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    struct block *curr;
    curr=heap->freeList_;
    while((curr->next)!=NULL){
        if((curr->free) && (curr->next->free))
        {
            curr->size+=(curr->next->size)+sizeof(struct block);
            curr->next=curr->next->next;
        }
        else
        {
            //prev=curr;
            curr=curr->next;
        }
        //curr=curr->next;
    }
    }
}

uint16_t myHeapCountBlocks(MyHeap *heap)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    uint16_t blocks = 0;
    struct block *curr;
    curr=heap->freeList_;
    do
    {
        blocks++;
        curr=curr->next;
        if (blocks > heap->size_)
            return blocks;
    }
    while((curr->next)!=NULL);
    return blocks;
    }
    return 0;
}

uint16_t myHeapCountFreeBlocks(MyHeap *heap)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    uint16_t blocks = 0;
    struct block *curr;
    curr=heap->freeList_;
    do{
        if (curr->free)
            blocks++;
        curr=curr->next;
        if (blocks > heap->size_)
            return blocks;
    }
    while((curr->next)!=NULL);
    return blocks;
    }
    return 0;
}

uint16_t myHeapCountBlockedBlocks(MyHeap *heap)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    uint16_t blocks = 0;
    struct block *curr;
    curr=heap->freeList_;
    do{
        if (!curr->free)
            blocks++;
        curr=curr->next;
        if (blocks > heap->size_)
            return blocks;
    }while((curr->next)!=NULL);
    return blocks;
    }
    return 0;
}

void myHeapFree(MyHeap *heap,void* ptr)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    if(((void*)heap->memory_<=ptr)&&(ptr<=(void*)(heap->memory_ + heap->size_))){
        struct block* curr=ptr;
        --curr;
        curr->free=true;
        myHeapMerge(heap);
        ptr = NULL;
    }
    else
    {
        PORTA.OUTSET = PIN3_bm;
    }
    }
}

[g457 (Gast)]

> was meint ihr dazu ?

Langen Code anhängen, nicht inlinen. Abgesehen davon: überflüssig.

Nix für ungut.

[P. S. (namnyef)]

Srsly?

[Sebastian S. (amateur)]

Ich fände es toll, wenn einer endlich mal das Rad erfinden würde.
So geht das doch nicht weiter.

Ansonsten schau mal nach, was das Netz zum Thema Speicherfragmentierung 
hergibt.
Hast Du lauter kleine Bereiche belegt und dazwischen ein paar Blöcke 
freigegeben, in der Summe also "viel Platz", so heißt das aber immer 
noch nicht, dass da auch ein großer Block Platz findet. Ist der größte, 
zusammenhängende Block um ein Byte zu klein, so geht halt nichts. Auch 
wenn in der Summe noch jede Menge Platz vorhanden ist.

[Matthias (Gast)]

Naja das Problem scheint mir doch nicht die Speicherfragmentierung zu 
sein,
wenn nach 10 alloc und 10 free immer noch Blöcke belegt sind scheint ja 
was im Code nicht zu stimmen. Sinn und zweck ist Übung probieren und 
lernen.

Strategie is übrigens first fit so am Rande, soll nicht das mega 
effizienteste sein soll einfach nur mal richtig tun

[c-hater (Gast)]

Matthias schrieb:

> wenn nach 10 alloc und 10 free immer noch Blöcke belegt sind scheint ja
> was im Code nicht zu stimmen.

Ja, natürlich. Das passiert z.B. genau dann, wenn free nicht in der Lage 
ist, benachbarte Blöcke ehemals belegten Speichers wieder zu einem Block 
freien Speichers zu vereinen...

Es verbleiben einfach die Informationen der Speicherverwaltung als 
Artefakt...

[Markus M. (adrock)]

Auf die Schnelle ist kein Fehler zu sehen. Sicher das Deine Testfunktion 
i.O. ist?

Haben die übriggebliebenen Blöcke eine bestimmte Größe?

Ansonsten hilft nur evtl. die Testfunktion so zu verändern, dass sie 
nach JEDEM free Aufruf die Anzahl der Blöcke auf Plausibilität prüft und 
bei einer Abweichung sofort Meldung gibt bzw. Du einen Breakpoint im 
Debugger setzt und dann schaust was genau passiert.

@c-hater: Ja, aber das wird bei seiner Implementierung eigentlich nicht 
passieren. Er geht bei einem free ja die ganze Speicherliste durch und 
checkt ob etwas gemerged werden kann.

[Matthias (Gast)]

Genau das macht ja mein free, setzt jeden block auf free und zwar 
sofort.

Mh ja als der test Code ist momentan eine Queue, die hat intern ein 
counter wenn ich was hinzufüge und entferne.

Dieser ist tatsächlich auf 0 also Queue ist leer.
in diesem Fall sollte ich ja bedenkenlos beliebig solange ich die Größe 
meines heaps nicht verletzte was ein die Queue packen können....

werde den block check mal gleich nach dem merge im free ansetzen ....

danke
Matthias

[Pandur S. (jetztnicht)]

Mein Gratulation zur Erkenntnis, dass dynamischer Speicher auf so einem 
Controller ein No-go ist.
Was soll dynamischer Speicher denn bringen ?  Man kann C++ auch ohne 
dynamischer Speicher laufenlassen.

[Matthias (Gast)]

@Markus M ich hab jetzt mal schnell counter für malloc und free 
eingeführt.
und es wird zwar nur hochgezählt wenn malloc speicher vergeben konnte 
und wenn free ihn auch wieder leeren konnte.

die zählen synchron hoch  also "scheint" der darüberlegende Code somit 
I.o

also gehe ich momentan stark davon aus das beim spliten oder mergen 
etwas schiefgeht

MFG
Matthias

[Stefan A. (king-crash)]

Ich würde dir empfehlen das Ganze auf deinem PC mit einem größeren Array 
als heapersatz zu testen. Das ist dank Debugger wesentlich einfacher.

[Stefan F. (Gast)]

Stefan A. schrieb:
> Ich würde dir empfehlen das Ganze auf deinem PC mit einem größeren Array
> als heapersatz zu testen. Das ist dank Debugger wesentlich einfacher.

Ja, oder mit dem AVR Simulator im AVR Studio (bzw. Atmel Studio) 
durchsteppen.

[Matthias (Gast)]

Hallo,

Also ich kann im nachhinein nicht mehr sagen wo der Fehler lag,

Ich vermute aber im malloc,

Denn das habe ich in der neuen Version etwas verbessert mit dem tipp von 
C-hater
im malloc aufzuräumen und nicht im free.

Des weiteren wurde das first fit durch eine best /first fit als 
Strategie geändert.

läuft jetzt seit 24H durchgängig, ist natürlich kein beweiß das es 
fehlerfrei ist aber ein Indiz :)

[Theor (Gast)]

Matthias schrieb:
> Hallo,
>
> Also ich kann im nachhinein nicht mehr sagen wo der Fehler lag,
>
> Ich vermute aber im malloc,
>
> Denn das habe ich in der neuen Version etwas verbessert [...]

Ich würde Dir aber doch sehr empfehlen, den Fehler zu "finden" und Dich 
nicht damit zufrieden zu geben, dass er "irgendwie" verschwunden ist.

Es muss nämlich gleichgültig sein, ob Du das aufräumen in malloc, vor 
der Rückgabe eines neuen, leeren Blocks oder in free, nach der Freigabe 
erledigst.

Man kann durchaus auf verschiedene Arten testen und es mag u.U. sein, 
dass Du nach der Änderung lediglich für eine bestimmten Fall (oder für 
einen Teil der Fälle) den Fehler nicht mehr siehst.

Keiner weiß es, und nach Murphy fallen einem diese Art Hoffnungen 
irgendwann auf die Füsse.

[Heiko L. (zer0)]

Matthias schrieb:
> nun bin ich auf das Problem gestoßen das obwohl ich genau soviel
> myMallocs wie my rees habe, ich irgendwann kein Speicher mehr anfordern
> kann.
> ...

while((((curr->size)<size)||((curr->free)==false))&&(curr->next!=NULL))
...
if((curr->size)==size){
 ...
}
else if((curr->size)>(size+sizeof(struct block))){
 ...
} else{
 ...
}

So wie das da steht kann man den OutOfMemory Path auslösen auch wenn 
noch Speicher da wäre. Und zwar, wenn curr->size zwar größer als size 
aber kleiner als size+sizeof(struct block) ist.

[Matthias (Gast)]

vermutlich war das auch das Problem...
Das ist aber in der neuen malloc aus dem letzten Post nicht mehr der 
Fall,

@ Theor Da hast du vollkommen Recht test Funktionen die die Blocks 
auswerten laufen ja noch mit,

Bis jetzt verhält sich ja alles wie erwartet...

Das neue malloc hat ja nicht einfach nur merge übernommen ...

[c]
void* myHeapMalloc(MyHeap *heap, uint16_t size)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
    {
    uint16_t min_size = 65535-sizeof(struct block);
    struct block *current = heap->freeList_;
    struct block *best_fit_block = NULL;

    do
    {
        if(current->free && current->size == size) //exact fit
        {
           current->free = false;
           return (void*)++current;
        }

        if((current->free == true) && (current->next !=NULL) && 
(current->next->free == true)) //merge
        {
            current->size+=(current->next->size)+sizeof(struct block);
            current->next=current->next->next;
        }

        if((current->free) && (current->size > size + sizeof(struct 
block)) && (current->size < min_size + sizeof(struct block) )) //best 
fit
        {
            best_fit_block = current;
            min_size = current->size;
        }
        current = current->next;
    }while (current != NULL);

    //we neeeeeeeed split step
    if(best_fit_block != NULL)
    {
        myHeapSplit(best_fit_block,size);
        return (void*) ++best_fit_block;
    }
    }
    return NULL;
}

MFG
Matthias
[c/]

[S. R. (svenska)]

Du solltest über eine Testsuite nachdenken, mit der du deine 
Implementation testest. Da malloc/free in der libc implementiert werden, 
kannst du z.B. hier schauen: https://wiki.musl-libc.org/libc-test.html

Ansonsten ist auch OpenBSD ziemlich absurd, was den Allocator angeht. 
Ich bin mir sicher, die haben auch einen guten Stresstest rumliegen. Hab 
aber spontan nichts gefunden.