gc
1.0.0
gc adalah implementasi dari pengumpul sampah yang konservatif, thread-local, mark-and-sweep. Implementasinya menyediakan pengganti yang berfungsi penuh untuk panggilan POSIX malloc() , calloc() , realloc() , dan free() standar.
Fokus dari gc adalah untuk memberikan implementasi mark-and-sweep GC yang secara konseptual bersih, tanpa menggali lebih dalam optimasi spesifik arsitektur (lihat misalnya Boehm GC untuk upaya tersebut). Ini harus sangat sesuai untuk tujuan pembelajaran dan terbuka untuk semua jenis optimasi (selamat datang bagi PR!).
Motivasi awal gc adalah keinginan saya untuk menulis LISP saya sendiri di C, seluruhnya dari awal - dan itu memerlukan pengumpulan sampah.
Karya ini tidak akan mungkin terwujud tanpa kemampuan membaca karya orang lain, terutama Boehm GC, tgc orangeduck (yang juga mengikuti cita-cita menjadi kecil dan sederhana), dan Buku Panduan Pengumpulan Sampah.
gc . $ git clone [email protected]:mkirchner/gc.git
$ cd gc
Untuk mengkompilasi menggunakan kompiler clang :
$ make test
Untuk menggunakan Koleksi Kompiler GNU (GCC):
$ make test CC=gcc
Tes harus diselesaikan dengan sukses. Untuk membuat laporan cakupan saat ini:
$ make coverage
...
#include "gc.h"
...
void some_fun () {
...
int * my_array = gc_calloc ( & gc , 1024 , sizeof ( int ));
for ( size_t i = 0 ; i < 1024 ; ++ i ) {
my_array [ i ] = 42 ;
}
...
// look ma, no free!
}
int main ( int argc , char * argv []) {
gc_start ( & gc , & argc );
...
some_fun ();
...
gc_stop ( & gc );
return 0 ;
} Ini menjelaskan API inti, lihat gc.h untuk detail selengkapnya dan API tingkat rendah.
Untuk menginisialisasi dan memulai pengumpulan sampah, gunakan fungsi gc_start() dan berikan alamat tumpukan terbawah :
void gc_start ( GarbageCollector * gc , void * bos ); Parameter tumpukan terbawah bos perlu menunjuk ke variabel yang dialokasikan tumpukan dan menandai ujung bawah tumpukan tempat pencarian akar (pemindaian) dimulai.
Pengumpulan sampah dapat dihentikan, dijeda, dan dilanjutkan dengan
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );dan pengumpulan sampah manual dapat dipicu dengan
size_t gc_run ( GarbageCollector * gc ); gc mendukung alokasi memori bergaya malloc() , calloc() dan realloc() . Tanda tangan fungsi masing-masing meniru fungsi POSIX (dengan pengecualian bahwa kita harus meneruskan pengumpul sampah sebagai argumen pertama):
void * gc_malloc ( GarbageCollector * gc , size_t size );
void * gc_calloc ( GarbageCollector * gc , size_t count , size_t size );
void * gc_realloc ( GarbageCollector * gc , void * ptr , size_t size );Dimungkinkan untuk meneruskan pointer ke fungsi destruktor melalui antarmuka yang diperluas:
void * dtor ( void * obj ) {
// do some cleanup work
obj -> parent -> deregister ();
obj -> db -> disconnect ()
...
// no need to free obj
}
...
SomeObject * obj = gc_malloc_ext ( gc , sizeof ( SomeObject ), dtor );
... gc mendukung alokasi statis yang merupakan sampah yang dikumpulkan hanya ketika GC dimatikan melalui gc_stop() . Cukup gunakan fungsi pembantu yang sesuai:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); Alokasi statis mengharapkan penunjuk ke fungsi finalisasi; cukup setel ke NULL jika finalisasi tidak diperlukan.
Perhatikan bahwa gc saat ini tidak menjamin pengurutan tertentu ketika mengumpulkan variabel statis, Jika var statis perlu dibatalkan alokasinya dalam urutan tertentu, pengguna harus memanggil gc_free() dalam urutan yang diinginkan sebelum memanggil gc_stop() , lihat di bawah .
Dimungkinkan juga untuk memicu dealokasi memori eksplisit menggunakan
void gc_free ( GarbageCollector * gc , void * ptr ); Memanggil gc_free() dijamin untuk (a) menyelesaikan/menghancurkan objek yang ditunjuk oleh ptr jika berlaku dan (b) untuk mengosongkan memori yang ditunjuk ptr terlepas dari penjadwalan pengumpulan sampah saat ini dan juga akan berfungsi jika GC telah dijeda menggunakan gc_pause() di atas.
gc juga menawarkan implementasi strdup() yang mengembalikan salinan yang dikumpulkan dari sampah:
char * gc_strdup ( GarbageCollector * gc , const char * s );Ide mendasar di balik pengumpulan sampah adalah untuk mengotomatiskan siklus alokasi/dealokasi memori. Hal ini dicapai dengan melacak semua memori yang dialokasikan dan secara berkala memicu dealokasi untuk memori yang masih dialokasikan namun tidak dapat dijangkau.
Banyak pengumpul sampah tingkat lanjut juga menerapkan pendekatan mereka sendiri terhadap alokasi memori (yaitu mengganti malloc() ). Hal ini sering kali memungkinkan mereka menata memori dengan cara yang lebih hemat ruang atau untuk akses lebih cepat, namun harus mengorbankan implementasi arsitektur spesifik dan peningkatan kompleksitas. gc menghindari masalah ini dengan kembali menggunakan implementasi POSIX *alloc() dan memisahkan manajemen memori dan metadata pengumpulan sampah. Hal ini membuat gc lebih mudah dipahami namun, tentu saja, juga kurang efisien dalam ruang dan waktu dibandingkan pendekatan yang lebih optimal.
Struktur data inti di dalam gc adalah peta hash yang memetakan alamat memori yang dialokasikan ke metadata pengumpulan sampah di memori tersebut:
Item dalam peta hash adalah alokasi, dimodelkan dengan Allocation struct :
typedef struct Allocation {
void * ptr ; // mem pointer
size_t size ; // allocated size in bytes
char tag ; // the tag for mark-and-sweep
void ( * dtor )( void * ); // destructor
struct Allocation * next ; // separate chaining
} Allocation ; Setiap instance Allocation menyimpan sebuah pointer ke memori yang dialokasikan, ukuran memori yang dialokasikan di lokasi tersebut, sebuah tag untuk mark-and-sweep (lihat di bawah), sebuah pointer opsional ke fungsi destruktor dan sebuah pointer ke instance Allocation berikutnya ( untuk rangkaian terpisah, lihat di bawah).
Alokasi dikumpulkan dalam AllocationMap
typedef struct AllocationMap {
size_t capacity ;
size_t min_capacity ;
double downsize_factor ;
double upsize_factor ;
double sweep_factor ;
size_t sweep_limit ;
size_t size ;
Allocation * * allocs ;
} AllocationMap ; yang, bersama dengan serangkaian fungsi static di dalam gc.c , menyediakan semantik peta hash untuk implementasi API publik.
AllocationMap adalah struktur data pusat di struct GarbageCollector yang merupakan bagian dari API publik:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; Dengan adanya struktur data dasar, permintaan alokasi memori gc_*alloc() apa pun memerlukan prosedur dua langkah: pertama, mengalokasikan memori melalui fungsionalitas sistem (yaitu standar malloc() ) dan kedua, menambah atau memperbarui metadata terkait ke peta hash.
Untuk gc_free() , gunakan penunjuk untuk menemukan metadata di peta hash, tentukan apakah deallokasi memerlukan panggilan destruktor, panggil jika diperlukan, bebaskan memori terkelola, dan hapus entri metadata dari peta hash.
Struktur data ini dan antarmuka terkait memungkinkan pengelolaan metadata yang diperlukan untuk membangun pengumpul sampah.
gc memicu pengumpulan dalam dua keadaan: (a) ketika salah satu panggilan ke alokasi sistem gagal (dengan harapan membatalkan alokasi memori yang cukup untuk memenuhi permintaan saat ini); dan (b) ketika jumlah entri dalam peta hash melewati tanda air tinggi yang disesuaikan secara dinamis.
Jika salah satu dari kasus ini terjadi, gc akan menghentikan dunia dan memulai pengumpulan sampah mark-and-sweep pada semua alokasi saat ini. Fungsionalitas ini diimplementasikan dalam fungsi gc_run() yang merupakan bagian dari API publik dan mendelegasikan semua pekerjaan ke fungsi gc_mark() dan gc_sweep() yang merupakan bagian dari API pribadi.
gc_mark() mempunyai tugas untuk menemukan akar dan menandai semua alokasi yang diketahui yang direferensikan dari suatu akar (atau dari alokasi yang direferensikan dari suatu akar, yaitu secara transitif) sebagai "digunakan". Setelah penandaan selesai, gc_sweep() mengulangi semua alokasi yang diketahui dan membatalkan alokasi semua alokasi yang tidak digunakan (yaitu tidak ditandai), kembali ke gc_run() dan dunia terus berjalan.
gc akan menyimpan alokasi memori yang dapat dijangkau dan mengumpulkan yang lainnya. Suatu alokasi dianggap dapat dijangkau jika salah satu dari hal berikut ini benar:
gc_start() (yaitu bos adalah alamat tumpukan terkecil yang dipertimbangkan selama fase penandaan).gc_*alloc() - konten yang dialokasikan yang menunjuk ke konten alokasi.GC_TAG_ROOT .Algoritme mark-and-sweep yang naif berjalan dalam dua tahap. Pertama, pada tahap penandaan , algoritma menemukan dan menandai semua alokasi akar dan semua alokasi yang dapat dijangkau dari akar. Kedua, pada tahap penyisiran , algoritme melewati semua alokasi yang diketahui, mengumpulkan semua alokasi yang tidak ditandai sehingga dianggap tidak dapat dijangkau.
Pada awal tahap penandaan , pertama-tama kita menyapu semua alokasi yang diketahui dan menemukan akar eksplisit dengan kumpulan tag GC_TAG_ROOT . Masing-masing akar ini merupakan titik awal untuk penandaan rekursif depth-first.
gc selanjutnya mendeteksi semua akar dalam tumpukan (mulai dari bos penunjuk tumpukan terbawah yang diteruskan ke gc_start() ) dan register (dengan membuangnya ke tumpukan sebelum fase penandaan) dan menggunakannya sebagai titik awal untuk menandai juga.
Dengan adanya alokasi root, penandaan terdiri dari (1) mengatur bidang tag di objek Allocation ke GC_TAG_MARK dan (2) memindai memori yang dialokasikan untuk mencari petunjuk ke alokasi yang diketahui, dan mengulangi proses tersebut secara rekursif.
Implementasi yang mendasarinya adalah pencarian mendalam pertama yang sederhana dan rekursif yang memindai seluruh konten memori untuk menemukan referensi potensial:
void gc_mark_alloc ( GarbageCollector * gc , void * ptr )
{
Allocation * alloc = gc_allocation_map_get ( gc -> allocs , ptr );
if ( alloc && !( alloc -> tag & GC_TAG_MARK )) {
alloc -> tag |= GC_TAG_MARK ;
for ( char * p = ( char * ) alloc -> ptr ;
p < ( char * ) alloc -> ptr + alloc -> size ;
++ p ) {
gc_mark_alloc ( gc , * ( void * * ) p );
}
}
} Di gc.c , gc_mark() memulai proses penandaan dengan menandai akar yang diketahui pada tumpukan melalui panggilan ke gc_mark_roots() . Untuk menandai akarnya kita melakukan satu lintasan penuh melalui semua alokasi yang diketahui. Kami kemudian melanjutkan untuk membuang register ke tumpukan.
Agar isi register CPU tersedia untuk pencarian root, gc membuangnya ke dalam tumpukan. Ini diimplementasikan dengan cara yang agak portabel menggunakan setjmp() , yang menyimpannya dalam variabel jmp_buf tepat sebelum kita menandai tumpukan:
...
/* Dump registers onto stack and scan the stack */
void ( * volatile _mark_stack )( GarbageCollector * ) = gc_mark_stack ;
jmp_buf ctx ;
memset ( & ctx , 0 , sizeof ( jmp_buf ));
setjmp ( ctx );
_mark_stack ( gc );
... Jalan memutar menggunakan penunjuk fungsi volatile _mark_stack ke fungsi gc_mark_stack() diperlukan untuk menghindari penyebarisan panggilan ke gc_mark_stack() .
Setelah menandai semua memori yang dapat dijangkau dan oleh karena itu berpotensi masih digunakan, mengumpulkan alokasi yang tidak dapat dijangkau sangatlah mudah. Berikut implementasi dari gc_sweep() :
size_t gc_sweep ( GarbageCollector * gc )
{
size_t total = 0 ;
for ( size_t i = 0 ; i < gc -> allocs -> capacity ; ++ i ) {
Allocation * chunk = gc -> allocs -> allocs [ i ];
Allocation * next = NULL ;
while ( chunk ) {
if ( chunk -> tag & GC_TAG_MARK ) {
/* unmark */
chunk -> tag &= ~ GC_TAG_MARK ;
chunk = chunk -> next ;
} else {
total += chunk -> size ;
if ( chunk -> dtor ) {
chunk -> dtor ( chunk -> ptr );
}
free ( chunk -> ptr );
next = chunk -> next ;
gc_allocation_map_remove ( gc -> allocs , chunk -> ptr , false);
chunk = next ;
}
}
}
gc_allocation_map_resize_to_fit ( gc -> allocs );
return total ;
} Kami mengulangi semua alokasi di peta hash (perulangan for ), mengikuti setiap rantai (perulangan while dengan chunk = chunk->next ) dan (1) menghapus tanda pada potongan jika sudah ditandai; atau (2) memanggil destruktor pada potongan tersebut dan mengosongkan memori jika tidak ditandai, sehingga menjaga total jumlah memori yang kita kosongkan tetap berjalan.
Itu menyimpulkan tanda & sapuan lari. Dunia yang terhenti dilanjutkan kembali dan kami siap untuk putaran berikutnya!
