Contoh Dynamic Memory Allocation Dengan Doubly-linked List, First-fit & Auto Left-Right Join [Part 4]

Bagian terakhir ini akan membahas tentang pembebasan memori ( Free() ). Fungsi free() sejatinya hanya mengubah field state kembali ke 0. Tapi karena tanggung jawabnya, alokator harus mengurus masalah fragmentasi internal. Ia harus memeriksa field bebas lain di sebelah kiri dan kanan chunk yang sedang dibebaskan. Apabila bebas, salah satu atau keduanya harus segera digabungkan.

int Free(void *addr){
HCHUNK *c,*p,*n;
c = (HCHUNK*)((ulong)addr - sizeof(HCHUNK));
if(c->magic != CMAGIC) return ­1;
if(c->state == 0) return ­2;
c->state = 0;
p = c->prev;
n = c->next;
if(n){
if(n->state == 0){
c->size += sizeof(HCHUNK) + n->size;
c->next = n->next;
if(n->next) n->next->prev = c;
}
}

if(p){
if(p->state == 0){
p->size += sizeof(HCHUNK) + c->size;
p->next = c->next;
if(c->next) c->next->prev = p;
}
}
return 0;
}

Proses pembebasan dan penggabungan dibantu dengan 3 buah variabel pointer

HCHUNK.
HCHUNK *c,*p,*n;

c merujuk pada HCHUNK dari alamat chunk yang sedang dibebaskan; p dan n merujuk ke chunk sebelah kiri (previous) dan kanan (next) dari chunk yang sedang dibebaskan.

Argumen addr dari fungsi ini berupa pointer chunk yang telah dialokasikan oleh Malloc() sebelumnya. Untuk mengetahui HCHUNK dari alamat tersebut, kurangi alamat addr dengan ukuran struktur HCHUNK.

c = (HCHUNK*)((ulong)addr - sizeof(HCHUNK));

Pastikan alamat chunk dari argumen addr adalah benar. Jika salah, dapat dipastikan nilai magic dari HCHUNK tidak akan bernilai valid. Jika jelas validitasnya, lanjut periksa juga field state. Jangan sampai kita menyiakan waktu untuk membebaskan chunk yang sudah bebas (state == 0).

if(c->magic != CMAGIC) return ­1;
if(c->state == 0) return ­2;

Cukup sudah. Sekarang bebaskan chunk ini.

c->state = 0;

2 langkah terakhir adalah prosedur penggabungan. Ambil pointer kedua chunk sampingnya dari field prev dan next.

p = c->prev;
n = c->next;

Mulai penggabungan dari chunk sebelah kanan. Dan lanjutkan dengan chunk sebelah kiri.

if(n){
if(n->state == 0){
c->size += sizeof(HCHUNK) + n->size;
c->next = n->next;
if(n->next) n->next->prev = c;
}
}
if(p){
if(p->state == 0){
p->size += sizeof(HCHUNK) + c->size;
p->next = c->next;
if(c->next) c->next->prev = p;
}
}

Nilai n dapat bernilai 0 apabila chunk yang baru saja dibebaskan adalah chunk terakhir. Jadi sebelum memeriksa state dari chunk n, pastikan dulu n bukan 0. Penggabungan dilakukan dengan 2 tahapan; update ukuran chunk pada field size chunk c dengan menambahkannya ukuran dari chunk n. Karena HCHUNK untuk n tidak terpakai lagi, kita juga menambahkan ukuran sejumlah ukuran struktur HCHUNK ( sizeof(HCHUNK) ) pada ukuran chunk c yang baru; kedua, update field next dari c, sehingga link antar chunk akan menjadi seperti di bawah ini.

Lakukan juga hal sama pada p dengan cara seperti sebelumnya.

Debugging
Untuk keperluan pengecekan, saya sudah buatkan fungsi dumper sederhana untuk mencetak properti semua chunk dalam HMALLOC. Kode ini self-explained, ya.

void HMallocDump(HMALLOC *h){
HCHUNK *c = h->first;
printf("HMALLOC Dump:\n");
while(c){
printf("HCHUNK size 0x%x state %x at 0x%x \
   prev 0x%x next 0x%x\n",
c->size,c->state,c, c->prev,c->next);
c = c->next;
}
}


Contoh Hasil
Hasil berikut adalah contoh implementasi Malloc() di kernel JauraOS.
https://github.com/irvanherz/jaura