Eigene malloc-Funktion
Einleitung
Ich will zeigen, wie man unter Linux eine einfache malloc-Funktion implementieren kann. Mein malloc ist nicht besonders effizient, es läuft in O(n), das heißt, wenn man doppelt so viel Speicher reserviert hat (in gleichgroßen Blöcken), dauert auch alloziieren von neuem Speicher doppelt so lange. Man könnte das etwas effizienter gestalten aber das soll hier egal sein. Das original malloc wird auf der Seite von Doug Lea beschrieben. Meine malloc Funktion ist in Assembler und C geschrieben und verwendet nach außen hin nur den Linux Syscall SYS_BRK. Der Asm-Code ist 64bit Code. Eine übertragung auf 32bit ist möglich, aber dabei muss beachtet werden, dass die CallingConventions dabei andere sind! Dazu auch: Syscalls
Für Kommentare oder Fragen, nutzt bitte das Gästebuch.
Vorraussetzung: Assembler für die Syscalls
%include "syscall_64_syscall.inc"
extern cmain
global _start
global sys_exit
global sys_brk
BITS 64
section .text
_start:
call cmain
;; CLEAN UP ---
mov rdi,0
call sys_exit
;; --- CLEAN UP
sys_exit:
mov rax,_sys_exit
syscall
ret
sys_brk:
mov rax,_sys_brk
syscall
ret
section .data
section .bss
resb 1
Wichtig ist hier das "section .bss", das hier mit einem uninitialisiertem Byte gefüllt wird, weil der Heap direkt nach .bss angelegt wird.
Unterbrechung: Etwas Theorie
Es gibt drei Orte, an denen wir etwas über die Größe und den Status eines Blockes herausfinden wollen:
- Am Anfang des Blockes, um herauszufinden, ob der Block frei ist, und wo der nächste Block liegt
- Am Anfang des Datenbereiches, um herauszufinden, wie viel freigegeben werden soll, wenn free() aufgerufen wird
- Am Ende des Blockes, um herauszufinen, ob der vorherige Block auch frei ist, und die Große, falls er das ist, zum vereinigen zu einem größeren freien Block
Wir brauchen dabei zunächst ein Bit, das kennzeichnet, ob der Block belegt (0) ist, oder frei (1). Da wir in Bytes arbeiten, haben wir noch 7 Bit zur Verfügung, um eine Zahl < 128 zu Speichern. Darin Speichern wir die Größe des Blockes, sofern der Datenbereich < 126 Bytes lang ist.
[flgsze][data < 126 ... ][flgsze]
Sollten wir allerdings mal mehr als 125 Bytes Daten benötigen, speichern wir im oberene Teil des Flagbytes nur 0 und packen dafür noch zwei 64bit Integer vor und hinter den Datenbereich. Damit man das auch herausfindet, wenn man nur den Pointer auf den Datenbereich hat (free()), setzen wir das Flagbyte nochmal direkt vor den Datenbereich:
[flgnul][____________________________ size ____________________________][flgnul]
[data > 125 ... ][____________________________ size ____________________________][flgnul]
Das hat zur Folge, dass es sehr viel ineffizienter ist, 126 Byte zu alloziieren, als 125 Byte zu alloziieren. Allerdings beträgt der Overhead bei 126 Bytes nur gut 15% und nimmt bei größeren Datenmenge stark ab (1,9% bei 1 KiB, 0,0018% bei 1 MiB). Im Gegensatz dazu beträgt der Overhead bei der Reservierung einzelner Bytes 200%!
Fortsetzung: C für die Funktionen
Zu SYS_BRK ist noch zu sagen, dass es nicht direkt vergrößert oder verkleinert, sondern nur das Ende des Heaps setzt. Das aktuelle Ende des Heaps kann man mit SYS_BRK(0) herausfinden. Den Anfang des Heaps muss man sich merken!
#define int long long // unschoen, aber erfuellt seinen zweck
extern int sys_exit(int s);
extern void* sys_brk(void* s);
// Schreibe Structurdaten
// Flag in Abhaengigkeit von free und
// Datengroesse an geeignete Stelle
void insertstructure(void* ptr, unsigned int size, unsigned char free)
{
if (free)
free = 1;
if (size < 128)
{
*((unsigned char*)ptr) = (size << 1) | free;
*((unsigned char*)ptr+size-1) = (size << 1) | free;
}
else
{
*((char*)ptr) = free;
*((char*)ptr+9) = free;
*((unsigned int*)(ptr+1)) = size;
*((char*)ptr+size-1) = free;
*((unsigned int*)(ptr+size-9)) = size;
}
}
// Alloziiere an Spitze vom Heap, ohne nach freien Bloecken zu suchen
void* qmalloc(unsigned int s)
{
unsigned int size = s + (s < 126 ? 2 : 19);
void *ptr = sys_brk(0);
sys_brk(ptr+size);
insertstructure(ptr, size,0);
return ((size < 128) ? ptr+1 : ptr+10);
}
// Suche nach freien Bloecken, die gross genug sind
// ansonsten wird qmalloc aufgerufen
void* malloc(unsigned int s)
{
static void* startptr = 0;
void* ptr = sys_brk(0);
if (!startptr)
{
startptr = ptr+9;
sys_brk(startptr);
*((int*)ptr) = 0;
*((char*)ptr+8) = 0;
}
unsigned int size = s + (s < 126 ? 2 : 19);
void *moveptr;
unsigned int actualsize;
for (moveptr = startptr; moveptr < ptr; moveptr += actualsize)
{
actualsize = (*((unsigned char*)moveptr)) >> 1;
if (!actualsize)
actualsize = *((unsigned int*)(moveptr+1));
if (((*((char*)moveptr)) & 0x01) && (actualsize >= size))
{
insertstructure(moveptr, size,0);
if (actualsize != size)
{
unsigned int othersize = actualsize - size;
insertstructure(moveptr+size, othersize, 1);
}
return ((size < 128) ? moveptr+1 : moveptr+10);
}
}
return qmalloc(s);
}
// Vereinige mit anliegenden freien Bloecken
void free(void* ptr)
{
unsigned int size = (*((unsigned char*)(--ptr))) >> 1;
if (!size)
{
size = *((unsigned int*)(ptr-8));
ptr-=9;
}
//if (ptr + size > sys_brk(0))
// ggf Fehlermeldung ausgeben
if (ptr + size < sys_brk(0))
if ((*((unsigned char*)(ptr+size))) & 1)
{
unsigned int oversize = (*((unsigned char*)(ptr+size))) >> 1;
if (!oversize)
oversize = *((unsigned int*)(ptr+size+1));
size += oversize;
}
if ((*((unsigned char*)(ptr-1))) & 1)
{
unsigned int undersize = (*((unsigned char*)(ptr-1))) >> 1;
if (!undersize)
undersize = *((unsigned int*)(ptr-9));
ptr -= undersize;
size += undersize;
}
insertstructure(ptr, size, 1);
}
Ende: Zum Schluss
Noch etwas zur Laufzeitbetrachtung: Wer häufig kleine Speichermengen reserviert und nur selten freigibt, sollte versuchen, qmalloc zu benutzen, das in konstanter Zeit läuft. Mit -O3 kompiliert, ist qmalloc(60) nur noch 9 inline Maschinenbefehle lang:
<test+1>: xor edi,edi
<test+3>: call 0x40012c <sys_brk>
<test+8>: lea rdi,[rax+0x34]
<test+12>: mov rbx,rax
<test+15>: call 0x40012c <sys_brk>
<test+20>: mov BYTE PTR [rbx],0x68
<test+23>: mov BYTE PTR [rbx+0x33],0x68
<test+27>: add rbx,0x1
<test+31>: mov rax,rbx
