Malloc selber schreiben

Klaus Gast #5008459
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.
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
moep Gast #5008477
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...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Johann L. Persönliche Seite #5008515
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andreas S. (Firma: Schweigstill IT) Persönliche Seite #5008553
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wilhelm M. #5008825
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Klaus Gast #5008952
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?
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wilhelm M. #5009012
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 ...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Clemens L. #5009143
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.)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Tec Gast #5009561
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);
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Tec Gast #5009564
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 Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren