heap_allocator
1.0.0
Ini adalah pengalokasi heap sederhana yang saya tulis untuk OS hobi yang sedang saya kerjakan. Saya menulis pengalokasi ini dengan sedikit riset, dan dibuat semudah mungkin untuk dipahami. Saya pikir repositori ini dapat berguna bagi mereka yang baru dalam pengembangan OS (seperti saya), atau tertarik untuk melihat versi sederhana dari fungsi seperti malloc dan gratis.
Ada dua file header yang mendefinisikan heap dan daftar tertaut. untuk mengkompilasi repositori ini:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
ini akan menjalankan demo pengalokasi dan mencetak beberapa informasi.
Untuk menginisialisasi heap ini, bagian memori harus disediakan. Dalam repositori ini, memori tersebut disediakan oleh malloc (ya, mengalokasikan heap melalui heap). Dalam pengaturan OS, beberapa halaman perlu dipetakan dan dimasukkan ke heap (satu skenario). Perhatikan bahwa bin di struct heap_t juga memerlukan alokasi memori untuknya.
Ketika fungsi init_heap dipanggil, alamat struct heap kosong (dengan pointer bin yang dialokasikan) harus disediakan. Fungsi init_heap kemudian akan membuat satu potongan besar dengan header ( node_t struct) dan footer ( footer_t struct). Untuk menentukan ukuran potongan ini, fungsinya menggunakan konstanta HEAP_INIT_SIZE . Ini akan menambahkan ini ke argumen start untuk menentukan di mana heap berakhir.
Setiap potongan memori memiliki struct node di awal dan struct footer di akhir. Node menyimpan ukuran, apakah potongannya bebas atau tidak, dan dua pointer digunakan dalam daftar tertaut ganda (berikutnya dan sebelumnya). Struktur footer hanya menyimpan penunjuk ke header (digunakan saat membebaskan potongan yang berdekatan). Bongkahan di ujung tumpukan disebut bongkahan "hutan belantara". Ini adalah potongan terbesar dan ukuran min dan maksnya ditentukan di heap.h. mengontrak dan memperluas heap semudah mengubah ukuran bongkahan hutan belantara ini. Potongan memori bebas disimpan dalam "bins", setiap bin sebenarnya hanyalah daftar node yang terhubung ganda dengan ukuran yang sama. Struktur heap menampung sejumlah bin yang ditentukan ( BIN_COUNT di heap.h). Untuk menentukan bin mana yang akan ditempatkan bongkahan, ukuran bongkahan tersebut dipetakan ke indeks bin dengan fungsi get_bin_index . Fungsi binning yang konsisten ini akan memastikan bahwa potongan dapat diakses dan disimpan dengan cara yang ditentukan. Potongan diurutkan saat dimasukkan ke dalam nampan sehingga penyisipan potongan bukan O(1) namun hal ini mempermudah untuk menemukan potongan yang paling sesuai. Perlu diperhatikan, fungsi binning dapat ditentukan sesuai keinginan pengguna heap ini. mungkin bermanfaat untuk menentukan fungsi binning yang lebih canggih untuk membantu pengambilan potongan dengan cepat.
Fungsi heap_alloc mengambil alamat heap struct yang akan dialokasikan dan ukurannya. Fungsi ini hanya menggunakan get_bin_index untuk menentukan di mana seharusnya potongan sebesar ini berada, tentu saja tidak boleh ada potongan sebesar itu. Jika tidak ada potongan yang ditemukan di nampan yang sesuai, maka nampan berikutnya akan diperiksa. Hal ini akan berlanjut sampai sebuah bongkahan ditemukan, atau nampan terakhir tercapai dan dalam hal ini sebagian memori hanya akan diambil dari bongkahan hutan belantara. Jika bongkahan yang ditemukan cukup besar maka akan dibelah. Untuk menentukan apakah suatu potongan harus dibagi, jumlah metadata (overhead) dikurangi dari apa yang tidak digunakan alokasi kami saat ini. Jika yang tersisa lebih besar atau sama dengan MIN_ALLOC_SZ berarti kita harus membagi potongan ini dan meletakkan sisanya di tempat sampah yang benar. Setelah kami siap mengembalikan potongan yang kami temukan, lalu kami mengambil alamat bidang next dan mengembalikannya. Hal ini dilakukan karena kolom next dan prev tidak digunakan saat sebuah bongkahan dialokasikan sehingga pengguna bongkahan tersebut dapat menulis data ke kolom ini tanpa memengaruhi cara kerja bagian dalam heap.
Fungsi heap_free mengambil pointer yang dikembalikan oleh heap_alloc . Ini mengurangi offset yang benar untuk mendapatkan alamat struct node. Daripada hanya menempatkan potongan ke dalam nampan yang benar, potongan yang mengelilingi potongan yang disediakan akan dicentang. Jika salah satu dari bongkahan ini bebas maka kita dapat menggabungkan bongkahan tersebut untuk membuat bongkahan yang lebih besar. Untuk menggabungkan potongan, footer digunakan untuk mendapatkan struktur simpul dari potongan sebelumnya dan struktur simpul dari potongan berikutnya. Misalnya, kita memiliki potongan bernama to_free . Untuk mendapatkan potongan sebelum potongan ini kita kurangi sizeof(footer_t) untuk mendapatkan footer dari potongan sebelumnya. Footer menyimpan penunjuk ke kepala potongan sebelumnya. Untuk mendapatkan potongan berikutnya kita cukup mendapatkan footer dari to_free dan kemudian menambahkan sizeof(footer_t) untuk mendapatkan potongan berikutnya. Setelah semua ini selesai dan ukurannya dihitung ulang, bongkahan tersebut ditempatkan kembali ke dalam wadah.
CATATAN: Kode ini awalnya dikompilasi untuk mesin 32-bit, ini berarti bahwa ketika kode ini digunakan, kode ini dapat diterima untuk memasukkan int ke sebuah pointer karena keduanya berukuran sama. Pada sistem 64-bit, kompiler akan memperingatkan Anda tentang perbedaan ukuran. Untuk membungkam peringatan ini saya telah menggunakan uintptr_t saat melakukan casting dari unsigned int ke sebuah pointer. Hal ini sedikit memperkeruh keterbacaan dan beberapa cast dan aritmatika penunjuk bertele-tele, jadi ingatlah hal itu saat membaca kode.
