gc
1.0.0
gc เป็นการนำตัวรวบรวมขยะแบบอนุรักษ์นิยม เธรดโลคอล ทำเครื่องหมายและกวาด การใช้งานจัดให้มีการแทนที่การทำงานอย่างสมบูรณ์สำหรับการโทร POSIX malloc() , calloc() , realloc() และ free() มาตรฐาน
จุดเน้นของ gc คือการนำเสนอการใช้งาน GC แบบทำเครื่องหมายและกวาดอย่างสะอาดตามแนวคิด โดยไม่ต้องเจาะลึกของการเพิ่มประสิทธิภาพเฉพาะสถาปัตยกรรมโดยเฉพาะ (ดู เช่น Boehm GC สำหรับการดำเนินการดังกล่าว) ควรเหมาะสมอย่างยิ่งสำหรับวัตถุประสงค์ในการเรียนรู้ และเปิดกว้างสำหรับการเพิ่มประสิทธิภาพทุกประเภท (ยินดีต้อนรับ PR!)
แรงจูงใจดั้งเดิมสำหรับ gc คือความปรารถนาของฉันที่จะเขียน LISP ของตัวเองในภาษา C ตั้งแต่เริ่มต้นทั้งหมด - และนั่นจำเป็นต้องมีการรวบรวมขยะ
งานนี้คงเป็นไปไม่ได้หากปราศจากความสามารถในการอ่านผลงานของผู้อื่น โดยเฉพาะอย่างยิ่ง Boehm GC, tgc ของ orangeduck (ซึ่งเป็นไปตามอุดมคติของการเป็นคนตัวเล็กและเรียบง่าย) และคู่มือการเก็บขยะ
gc ไปใช้ $ git clone [email protected]:mkirchner/gc.git
$ cd gc
ในการคอมไพล์โดยใช้คอมไพเลอร์ clang :
$ make test
หากต้องการใช้ GNU Compiler Collection (GCC):
$ make test CC=gcc
การทดสอบควรจะเสร็จสิ้นสำเร็จ หากต้องการสร้างรายงานความครอบคลุมปัจจุบัน:
$ 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 ;
} สิ่งนี้จะอธิบายเกี่ยวกับ API หลัก โปรดดูรายละเอียดเพิ่มเติมใน gc.h และ API ระดับต่ำ
ในการเริ่มต้นและเริ่มการรวบรวมขยะ ให้ใช้ฟังก์ชัน gc_start() และส่งที่อยู่ ด้านล่างสุดของสแต็ก :
void gc_start ( GarbageCollector * gc , void * bos ); bos พารามิเตอร์ที่อยู่ด้านล่างสุดของสแต็กจำเป็นต้องชี้ไปที่ตัวแปรที่จัดสรรสแต็ก และทำเครื่องหมายจุดต่ำสุดของสแต็กจากจุดเริ่มต้นการค้นหารูท (การสแกน)
การเก็บขยะสามารถหยุด หยุดชั่วคราว และดำเนินการต่อได้
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );และสามารถกระตุ้นการเก็บขยะด้วยตนเองได้ด้วย
size_t gc_run ( GarbageCollector * gc ); gc รองรับการจัดสรรหน่วยความจำสไตล์ malloc() , calloc() และ realloc() ลายเซ็นฟังก์ชันที่เกี่ยวข้องจะเลียนแบบฟังก์ชัน POSIX (ยกเว้นว่าเราต้องส่งผ่านตัวรวบรวมขยะเป็นอาร์กิวเมนต์แรก):
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 );เป็นไปได้ที่จะส่งพอยน์เตอร์ไปยังฟังก์ชัน destructor ผ่านทางอินเทอร์เฟซแบบขยาย:
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 รองรับการจัดสรรแบบคงที่ซึ่งเป็นขยะที่รวบรวมเฉพาะเมื่อ GC ปิดระบบผ่าน gc_stop() เพียงใช้ฟังก์ชันตัวช่วยที่เหมาะสม:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); การจัดสรรแบบคงที่คาดว่าจะมีตัวชี้ไปยังฟังก์ชันการสรุป เพียงตั้งค่าเป็น NULL หากไม่จำเป็นต้องทำการสรุป
โปรดทราบว่าปัจจุบัน gc ไม่รับประกันการเรียงลำดับเฉพาะเมื่อรวบรวมตัวแปรคงที่ หากจำเป็นต้องจัดสรร vars แบบคงที่ในลำดับเฉพาะ ผู้ใช้ควรเรียก gc_free() กับตัวแปรเหล่านั้นในลำดับที่ต้องการก่อนที่จะเรียก gc_stop() ดูด้านล่าง .
นอกจากนี้ยังเป็นไปได้ที่จะทริกเกอร์การจัดสรรหน่วยความจำอย่างชัดเจนโดยใช้
void gc_free ( GarbageCollector * gc , void * ptr ); การเรียก gc_free() รับประกันว่าจะ (a) สิ้นสุด/ทำลายวัตถุที่ชี้โดย ptr หากมี และ (b) เพื่อเพิ่มหน่วยความจำที่ ptr ชี้ไปที่โดยไม่คำนึงถึงกำหนดเวลาปัจจุบันสำหรับการรวบรวมขยะ และจะทำงานด้วยหาก GC ได้รับ หยุดชั่วคราวโดยใช้ gc_pause() ด้านบน
gc ยังมีการใช้งาน strdup() ที่ส่งคืนสำเนาที่รวบรวมขยะ:
char * gc_strdup ( GarbageCollector * gc , const char * s );แนวคิดพื้นฐานเบื้องหลังการรวบรวมขยะคือการทำให้วงจรการจัดสรรหน่วยความจำ/การจัดสรรคืนเป็นไปโดยอัตโนมัติ ซึ่งทำได้โดยการติดตามหน่วยความจำที่จัดสรรไว้ทั้งหมด และทริกเกอร์การจัดสรรคืนสำหรับหน่วยความจำที่ยังคงจัดสรรอยู่แต่ไม่สามารถเข้าถึงได้เป็นระยะๆ
ตัวรวบรวมขยะขั้นสูงจำนวนมากยังใช้แนวทางของตนเองในการจัดสรรหน่วยความจำ (เช่น แทนที่ malloc() ) ซึ่งมักจะช่วยให้พวกเขาจัดวางหน่วยความจำในลักษณะประหยัดพื้นที่มากขึ้นหรือเพื่อการเข้าถึงที่รวดเร็วขึ้น แต่มาพร้อมกับราคาของการใช้งานเฉพาะสถาปัตยกรรมและความซับซ้อนที่เพิ่มขึ้น gc หลีกเลี่ยงปัญหาเหล่านี้โดยย้อนกลับไปใช้งาน POSIX *alloc() และแยกการจัดการหน่วยความจำและข้อมูลเมตาการรวบรวมขยะออกจากกัน สิ่งนี้ทำให้ gc เข้าใจง่ายขึ้นมาก แต่แน่นอนว่ายังประหยัดพื้นที่และเวลาน้อยกว่าแนวทางที่ได้รับการปรับปรุงให้เหมาะสมที่สุดอีกด้วย
โครงสร้างข้อมูลหลักภายใน gc คือแผนที่แฮชที่แมปที่อยู่ของหน่วยความจำที่จัดสรรกับข้อมูลเมตาการรวบรวมขยะของหน่วยความจำนั้น:
รายการในแผนที่แฮชเป็นการจัดสรร จำลองด้วย struct Allocation :
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 ; Allocation แต่ละรายการจะมีตัวชี้ไปยังหน่วยความจำที่จัดสรร ขนาดของหน่วยความจำที่จัดสรรในตำแหน่งนั้น แท็กสำหรับการทำเครื่องหมายและกวาด (ดูด้านล่าง) ตัวชี้ทางเลือกไปยังฟังก์ชัน destructor และตัวชี้ไปยัง Allocation ถัดไป ( สำหรับการต่อโซ่แยกกัน ดูด้านล่าง)
การจัดสรรจะถูกรวบรวมใน 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 ; ที่เมื่อใช้ร่วมกับชุดฟังก์ชัน static ที่ภายใน gc.c จะจัดเตรียมความหมายแผนที่แฮชสำหรับการนำ API สาธารณะไปใช้
AllocationMap เป็นโครงสร้างข้อมูลส่วนกลางในโครงสร้าง GarbageCollector ซึ่งเป็นส่วนหนึ่งของ API สาธารณะ:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; ด้วยโครงสร้างข้อมูลพื้นฐานที่มีอยู่แล้ว คำขอการจัดสรรหน่วยความจำ gc_*alloc() ใดๆ จึงเป็นขั้นตอนสองขั้นตอน: ขั้นแรก จัดสรรหน่วยความจำผ่านฟังก์ชันระบบ (เช่น มาตรฐาน malloc() ) และประการที่สอง เพิ่มหรืออัปเดตข้อมูลเมตาที่เกี่ยวข้องไปยัง แผนที่แฮช
สำหรับ gc_free() ให้ใช้พอยน์เตอร์เพื่อค้นหาข้อมูลเมตาในแมปแฮช ตรวจสอบว่าการจัดสรรคืนต้องมีการเรียกตัวทำลายหรือไม่ โทรหากจำเป็น เพิ่มหน่วยความจำที่ได้รับการจัดการ และลบรายการข้อมูลเมตาออกจากแมปแฮช
โครงสร้างข้อมูลเหล่านี้และอินเทอร์เฟซที่เกี่ยวข้องทำให้สามารถจัดการข้อมูลเมตาที่จำเป็นในการสร้างตัวรวบรวมขยะ
gc ทริกเกอร์การรวบรวมภายใต้สองสถานการณ์: (ก) เมื่อการเรียกการจัดสรรระบบล้มเหลว (โดยหวังว่าจะจัดสรรหน่วยความจำที่เพียงพอเพื่อตอบสนองคำขอปัจจุบัน); และ (b) เมื่อจำนวนรายการในแผนที่แฮชผ่านเครื่องหมายน้ำสูงที่ปรับแบบไดนามิก
หากเกิดกรณีใดกรณีหนึ่งเหล่านี้ gc จะหยุดโลกและเริ่มการรวบรวมขยะแบบทำเครื่องหมายแล้วกวาดซึ่งดำเนินการกับการจัดสรรปัจจุบันทั้งหมด ฟังก์ชันนี้ถูกนำมาใช้ในฟังก์ชัน gc_run() ซึ่งเป็นส่วนหนึ่งของ API สาธารณะ และมอบหมายงานทั้งหมดให้กับฟังก์ชัน gc_mark() และ gc_sweep() ที่เป็นส่วนหนึ่งของ API ส่วนตัว
gc_mark() มีหน้าที่ในการค้นหารูทและติดแท็กการจัดสรรที่รู้จักทั้งหมดที่อ้างอิงจากรูท (หรือจากการจัดสรรที่อ้างอิงจากรูท เช่น แบบส่งผ่าน) เป็น "ใช้แล้ว" เมื่อการทำเครื่องหมายของเสร็จสมบูรณ์ gc_sweep() จะวนซ้ำการจัดสรรที่ทราบทั้งหมด และจัดสรรการจัดสรรที่ไม่ได้ใช้ (เช่น ไม่มีการทำเครื่องหมาย) ทั้งหมด กลับสู่ gc_run() และโลกยังคงทำงานต่อไป
gc จะเก็บการจัดสรรหน่วยความจำที่ สามารถเข้าถึงได้ และรวบรวมทุกสิ่งทุกอย่าง การจัดสรรจะถือว่าสามารถเข้าถึงได้หากข้อใดข้อหนึ่งต่อไปนี้เป็นจริง:
gc_start() (กล่าวคือ bos คือที่อยู่สแต็กที่เล็กที่สุดที่พิจารณาในระหว่างเฟสการทำเครื่องหมาย)gc_*alloc() ซึ่งชี้ไปยังเนื้อหาการจัดสรรGC_TAG_ROOTอัลกอริธึมการทำเครื่องหมายและกวาดแบบไร้เดียงสาทำงานในสองขั้นตอน ขั้นแรก ในขั้นตอน การทำเครื่องหมาย อัลกอริธึมจะค้นหาและทำเครื่องหมายการจัดสรร รูท ทั้งหมดและการจัดสรรทั้งหมดที่สามารถเข้าถึงได้จากรูท ประการที่สอง ในขั้นตอน การกวาด อัลกอริธึมจะส่งผ่านการจัดสรรที่ทราบทั้งหมด โดยรวบรวมการจัดสรรทั้งหมดที่ไม่ได้ทำเครื่องหมายไว้และถือว่าไม่สามารถเข้าถึงได้
ในตอนเริ่มต้นของขั้น ทำเครื่องหมาย ก่อนอื่นเราจะกวาดล้างการจัดสรรที่ทราบทั้งหมด และค้นหารากที่ชัดเจนด้วยชุดแท็ก GC_TAG_ROOT แต่ละรากเหล่านี้เป็นจุดเริ่มต้นสำหรับการมาร์กแบบเรียกซ้ำเชิงลึกก่อน
gc ตรวจพบรากทั้งหมดในสแต็กในเวลาต่อมา (เริ่มต้นจาก bos ตัวชี้ด้านล่างของสแต็กที่ส่งผ่านไปยัง gc_start() ) และรีจิสเตอร์ (โดยการทิ้งมันลงบนสแต็กก่อนเฟสการทำเครื่องหมาย) และใช้สิ่งเหล่านี้เป็นจุดเริ่มต้นสำหรับ การทำเครื่องหมายเช่นกัน
ด้วยการจัดสรรราก การทำเครื่องหมายประกอบด้วย (1) การตั้งค่าฟิลด์ tag ในออบเจ็กต์ Allocation เป็น GC_TAG_MARK และ (2) การสแกนหน่วยความจำที่จัดสรรเพื่อหาพอยน์เตอร์ไปยังการจัดสรรที่ทราบ โดยทำซ้ำกระบวนการซ้ำๆ
การใช้งานพื้นฐานคือการค้นหาเชิงลึกก่อนแบบเรียกซ้ำซึ่งจะสแกนเนื้อหาหน่วยความจำทั้งหมดเพื่อค้นหาการอ้างอิงที่เป็นไปได้:
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 );
}
}
} ใน gc.c นั้น gc_mark() เริ่มกระบวนการทำเครื่องหมายโดยการทำเครื่องหมายรูทที่รู้จักบนสแต็กผ่านการเรียกไปที่ gc_mark_roots() เพื่อทำเครื่องหมายราก เราทำการส่งผ่านแบบเต็มผ่านการจัดสรรที่ทราบทั้งหมด จากนั้นเราดำเนินการถ่ายโอนข้อมูลการลงทะเบียนบนสแต็ก
เพื่อให้เนื้อหาการลงทะเบียน CPU พร้อมสำหรับการค้นหารูท gc ทิ้งเนื้อหาเหล่านั้นลงบนสแต็ก สิ่งนี้ถูกนำไปใช้ในลักษณะพกพาได้โดยใช้ setjmp() ซึ่งจัดเก็บไว้ในตัวแปร jmp_buf ก่อนที่เราจะทำเครื่องหมายสแต็ก:
...
/* 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 );
... ทางเบี่ยงโดยใช้ตัวชี้ฟังก์ชัน volatile _mark_stack ไปยังฟังก์ชัน gc_mark_stack() เป็นสิ่งจำเป็นเพื่อหลีกเลี่ยงการอินไลน์ของการเรียกไปยัง gc_mark_stack()
หลังจากทำเครื่องหมายหน่วยความจำทั้งหมดที่สามารถเข้าถึงได้และอาจยังคงใช้งานอยู่ การรวบรวมการจัดสรรที่ไม่สามารถเข้าถึงได้จึงเป็นเรื่องเล็กน้อย นี่คือการใช้งานจาก 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 ;
} เราวนซ้ำการจัดสรรทั้งหมดในแมปแฮช ( for loop) ตามทุกเชน (ลูป while ด้วย chunk = chunk->next ) และ (1) ยกเลิกการทำเครื่องหมาย chunk หากมันถูกทำเครื่องหมายไว้; หรือ (2) เรียก destructor บนก้อนและปลดปล่อยหน่วยความจำหากไม่ได้ทำเครื่องหมายไว้ โดยคงจำนวนหน่วยความจำที่เราว่างไว้ทั้งหมด
นั่นเป็นการสรุปการทำเครื่องหมายและการกวาดล้าง โลกที่หยุดนิ่งกลับมาอีกครั้ง และเราพร้อมสำหรับการวิ่งครั้งต่อไป!
