Forum: PC-Programmierung Malloc selber schreiben


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Klaus (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hallo

Ich möchte eine malloc Funktion selber schreiben. Mein Problem dabei ist 
der Ansatz.

Meine ersten Überlegungen dazu sind:

Als Heap hab ich ein Char-array mit einer fixen Größe.
Des Weiteren braucht man einen Header pro Speicherblock indem 
festgehalten wird wie groß der Speicherblock ist und ob er frei ist oder 
nicht.
Dazu würde sich eine Struktur eigenen.

Mein Problem dabei ist nun, wie ich das Char-Array mit den Headern 
verknüpfe.
Muss in die Struktur noch ein Char-Pointer? Wird dann nicht sehr viel 
Speicher nur für die Verwaltung verbraucht?
Zudem muss man zu begin schon ein Header-Array erzeugen mit der gleich 
Anzahl an Bytes des Speichers. Dadurch wird es ja extrem ineffizient.

von moep (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Klaus schrieb:
> Ich möchte eine malloc Funktion selber schreiben

Du möchtest (Interesse/Bedarf) oder du musst (Hausaufgabe)?

Bei Bedarf: Einen bestehenden Allokator nehmen (wenn du auf einem fixen 
Buffer arbeiten möchtest z.B. den http://www.gii.upv.es/tlsf/).

Bei Interesse: Entweder selber grübeln und ausprobieren. Oder eben 
schauen was die anderen so machen(z.B. 
http://g.oswego.edu/dl/html/malloc.html). Dann endest du aber dabei 
einen anderen Allokator nachzubauen und kannst es eigentlich gleich 
lassen...

von hns (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Ich habe das vor vielen Jahren auch mal selber gemacht. Damals gab es 
nur das C Buch von Kernighan&Ritchie mit einem Beispielcode.

http://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Klaus schrieb:
> Wird dann nicht sehr viel Speicher nur für die Verwaltung verbraucht?

Von nix kommt nix.  malloc bedeutet Overhead, sowohl was Speicherplatz 
als auch was Laufzeit bei Allokation und Freigabe angeht.

> Zudem muss man zu begin schon ein Header-Array erzeugen mit der gleich
> Anzahl an Bytes des Speichers. Dadurch wird es ja extrem ineffizient.

Du kannst dir ja mal Implementationen von malloc anschauen, wobei die 
natürlich auch OS-abhängig sind.  Beispiele:

Newlib:

https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;a=blob_plain;f=newlib/libc/stdlib/malloc.c
https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;a=blob_plain;f=newlib/libc/stdlib/mallocr.c

AVR-LibC:

http://svn.savannah.nongnu.org/viewvc/*checkout*/avr-libc/trunk/avr-libc/libc/stdlib/malloc.c

GNU C Library (glibc), gleich ein ganzes Verzeichniss voll:

https://sourceware.org/git/?p=glibc.git;a=tree;f=malloc

von Andreas S. (Firma: Schweigstill IT) (schweigstill) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
Das wirklich große Problem bei der Entwicklung solch einer 
Speicherverwaltung besteht darin, die im Laufe der Zeit entstehende 
Speicherfragmentierung in den Griff zu bekommen. Ansonsten kann es 
passieren, dass plötzlich zwar 80% des Speichers ungenutzt sind, sich 
aber keine hinreichend großen Blöcke mehr allozieren lassen. Aus diesem 
Grund runden manche Allokatoren auf feste Blockgrößen auf, vorzugsweise 
in Zweipotetnzen.

Eine Betriebssysteme bieten auch die Möglichkeit, sog. Memory Pools zu 
verwenden, d.h. sich je nach Verwendungszweck aus dem einen oder anderen 
Speicher zu bedienen.

von Wilhelm M. (wimalopaan)


Bewertung
0 lesenswert
nicht lesenswert
Super schwer ist das jetzt nicht. Das Stichwort heisst in-place-Liste. 
Kurz: man verwaltet belegte Blöcke und freie Löcher in einer Liste, 
deren Listenknoten und die Nutzdaten in demselben Bereich liegen: 
oberhalb vom data-segment bis zur sog. "Bruchstelle" (break), die man 
mit bspw. dem Systemcall sbrk() verschieben kann. Das ist das Prinzip 
und überall gleich.

Man ist daran interessiert, die sog. externe Fragmentierung zu vermeiden 
(s.o.). Mögliche Allokationsstrategien sind etwa: first-fit, next-fit, 
best-fit, worst-fit. Oder ein Buddy-System mit Allokationsgrößen in 2'er 
Potenzen.

Beim free() muss/sollte man natürlich angrenzenden freie Löcher wieder 
verschmelzen.

Du kannst an den Adressen von malloc() der libc leicht erkennen, dass 
hier so gearbeitet wird mit bspw. einem Listenknoten der Größe 8 Byte.

Deine eigene Implementierung kannst Du dann ggf. mit dem ld.so 
(*nix-Systeme) in bestehende Programme injizieren.

von Klaus (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Erstmal Danke für die vielen Antworten.

moep schrieb:
> Du möchtest (Interesse/Bedarf) oder du musst (Hausaufgabe)?

Es ist wirklich nur Interesse.

Ich hab jetzt mal eine Version geschrieben.
Hab eine einfach verketteten Liste für die Verwaltung verwendet.
Leider hab ich ein Pointer-Problem.
Hier der Code:
1
static char heap[SIZE_OF_HEAP];
2
struct header *headerstart = NULL;
3
static int Size_OF_Free_Space;
4
struct  header *help = NULL;
5
void mem_init(void) {
6
7
  for (int i = 0; i < SIZE_OF_HEAP; i++) {
8
9
    heap[i] = 0;
10
  }
11
  Size_OF_Free_Space = SIZE_OF_HEAP; 
12
13
  headerstart = mem_init_alloc(sizeof(struct header));
14
  Size_OF_Free_Space -= sizeof(struct header);
15
  headerstart->size = SIZE_OF_HEAP-sizeof(struct header); // Header 12 Byte
16
  headerstart->state = 'F';
17
  headerstart->speicher = mem_init_alloc(headerstart->size);
18
  for (int i = 0; i < headerstart->size; i++) {
19
20
    headerstart->speicher[i] = 'F';
21
  }
22
  
23
24
}
25
void* mem_init_alloc(int size) {
26
  if (Size_OF_Free_Space < size) {
27
28
    return NULL;
29
  }
30
  else
31
  {
32
      
33
    return &heap[SIZE_OF_HEAP-Size_OF_Free_Space];
34
  }
35
  
36
  
37
}
38
void* mem_alloc(int size) {
39
  if (headerstart->size < size + sizeof(headerstart)) {
40
41
    return NULL; // Falls kein Speicher mehr frei ist
42
  }
43
  else {
44
    help = headerstart;
45
    
46
    
47
    while(help != NULL)
48
    {
49
      help = help->next;
50
      
51
    }
52
    if (help == NULL) {
53
      help = &heap[SIZE_OF_HEAP - Size_OF_Free_Space];
54
      Size_OF_Free_Space -= sizeof(struct header);
55
      headerstart->size = Size_OF_Free_Space;
56
      help->size = size;
57
      help->state = 'A';
58
      help->next = NULL;
59
      help->speicher = &heap[SIZE_OF_HEAP - Size_OF_Free_Space-1]; // Stringende
60
61
      for (int i = 0; i < size; i++) {
62
        help->speicher[i] = 'A';
63
64
      }
65
      help->speicher[size] = '\0';
66
      return help->speicher;
67
    
68
    
69
    }
70
    
71
72
    }
73
74
  }
75
76
void mem_dump(void) {
77
  help = headerstart;
78
  printf("Komplett freier Speicher --> %d\n", headerstart->size);
79
  while (help != NULL)
80
  {
81
    
82
      printf("%C | %d | %s \n", help->state, help->size,help->speicher);
83
      help = help->next;
84
  
85
  }
86
87
}

Headerstart zeigt immer auf den Anfang des Speichers. In der Funktion 
mem_alloc füge ich mit einem Hilfspointer einen neuen Speicherblock ein 
und weise Ihn Headerstart->next zu. Wenn ich aber nun eine Ausgabe mach 
ist der Next-pointer vom Headerstart NULL. Warum?

von Wilhelm M. (wimalopaan)


Bewertung
-1 lesenswert
nicht lesenswert
Dein Code schaut recht wirr aus, deswegen kann ich Dir auch nicht sagen, 
was darin im Moment schief läuft.

Aber:

Du hast nur eine fixe Größe des Heaps durch Deine globale Variable. 
Damit kannst Du diese maximale Größe nicht mehr ändern. Du solltest Dir 
mal sbrk() ansehen (falls Du wirklich vor hast, eine Allokator zu 
schreiben).

Initial hast Du eine leere Liste mit einem Knoten des Typs F (frei). So 
muss Du Deine Liste initialisieren. Alles weitere ist dann regulär.

Vielleicht nimmt Du auch mal ein Buch über Betriebssysteme zur Hand ...

von Clemens L. (c_l)


Bewertung
1 lesenswert
nicht lesenswert
Klaus schrieb:
> Muss in die Struktur noch ein Char-Pointer?

Üblicherweise liegt der Header im Speicher direkt vor dem Datenblock:
1
void *data = &header + 1;
(Für solche Sachen ist die Zeigerarithmetik von C mal nützlich ...)

> Wird dann nicht sehr viel Speicher nur für die Verwaltung verbraucht?

Das kommt darauf an, wie komplex deine Speicherverwaltung ist. Man kann 
noch etwas drauflegen, z.B. mit getrennten Speicherbereichen für 
verschiedene Blockgrößen (um Fragmentierung zu vermeiden), oder extra 
Verwaltungsaufwand, damit sich mehrere CPUs nicht in die Quere kommen.

Oder du implementierts einen Buddy-Allocator; der hat keinen Overhead 
für belegte Speicherblöcke (die Liste der freien Speicherblöcke kann in 
den freien Blöcken selbst gespeichert werden):
https://en.wikipedia.org/wiki/Buddy_memory_allocation
(Und nichts ist umsonst: alle Blöcke werden auf eine Zweierpotenz 
aufgerundet, und beim free() muss die Größe auch angegeben werden.)

: Bearbeitet durch User
von Tec (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
eine einfache Speicherverwaltung würde etwa so funktionieren.
(Syntax und Datenstrukturen nicht vollständig - es geht darum,
die Idee darzustellen!!)


1. Speicherblöcke auf dem Stack anlegen:
static BYTE  pool[16][64];


2. Listen anlegen
static LIST   List_freePools;
static LIST   List_usedPools;


3. Zeiger auf pools in freePools eintragen
for (i=0; i; i<16; i++)
{
  List_freePools.Add(&pool[i]);
}


4. Speicherblock allokieren
BYTE* myAlloc(int size)
{
  BYTE * p;
  if ( size < 65 )
  {
    p = List_freePools.Get();
    List_usedPools.Add(p);
    return p;
  }
}


5. Speicherblock deallokieren
void myFree(BYTE* p)
{
   //Adresse aus der Liste der benutzen Blöcke austragen
   List_usedPools.GetByAddress(p);
   //Adresse wieder in die Liste der freien Blöcke eintragen
   List_freePools.Add(p);
}

von Tec (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
...man kann auch verschieden große Blöcke anlegen, wenn man
die Verwaltungsstrukturen ntspr. erweitert.
Bei Zugriff aus verschiedenen Threads/Interrupt sind die Listen
gegen parallelen Zugriff zu schützen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.